#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass beamer
\begin_preamble
% Uncomment to print out only slides and overlays
%
%\onlyslides{\slides}
% Uncomment to print out only notes
%
%\onlynotes{\notes}
\end_preamble
\use_default_options false
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures false
\graphics none
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Subtitle
Experimental Results
\end_layout
\begin_layout Title
Automated Grammar Induction
\end_layout
\begin_layout Author
Linas Vepštas
\end_layout
\begin_layout Institute
AGI 2022
\end_layout
\begin_layout Date
19 August 2022
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Word-pair Mutual Information
\end_layout
\end_deeper
\begin_layout Frame
Basic definitions:
\end_layout
\begin_deeper
\begin_layout Itemize
Word Pair:
\begin_inset Formula $\left(u,w\right)$
\end_inset
\end_layout
\begin_layout Itemize
Count:
\begin_inset Formula $N\left(u,w\right)$
\end_inset
\end_layout
\begin_layout Itemize
Frequentist probability:
\begin_inset Formula $p\left(u,w\right)=N\left(u,w\right)/N\left(*,*\right)$
\end_inset
\end_layout
\begin_layout Itemize
Star == wildcard sum over all entries in that location
\end_layout
\begin_layout Itemize
Lexical Attraction (MI):
\begin_inset Formula
\[
MI\left(u,w\right)=\log_{2}\frac{p\left(u,w\right)}{p\left(u,*\right)p\left(*,w\right)}
\]
\end_inset
\end_layout
\begin_layout Itemize
Not symmetric:
\begin_inset Formula $\left(u,w\right)\ne\left(w,u\right)$
\end_inset
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Characterizing Word–Pair Data Sets
\end_layout
\end_deeper
\begin_layout Frame
Sparse matrix with global properties
\end_layout
\begin_deeper
\begin_layout Itemize
Log width and height:
\begin_inset Formula $\log_{2}N_{L}$
\end_inset
and
\begin_inset Formula $\log_{2}N_{R}$
\end_inset
\end_layout
\begin_layout Itemize
Log total number of nonzero entries:
\begin_inset Formula $\log_{2}D_{\mathrm{Tot}}$
\end_inset
\end_layout
\begin_layout Itemize
Log total number of observations:
\begin_inset Formula $\log_{2}N_{\mathrm{Tot}}$
\end_inset
\end_layout
\begin_layout Itemize
Sparsity:
\begin_inset Formula $-\log_{2}D_{\mathrm{Tot}}/N_{L}\times N_{R}$
\end_inset
\end_layout
\begin_layout Itemize
Rarity:
\begin_inset Formula $\log_{2}D_{\mathrm{Tot}}/\sqrt{N_{L}\times N_{R}}$
\end_inset
is independent of dataset size!
\end_layout
\begin_layout Itemize
Entropy:
\begin_inset Formula $H_{\mathrm{Tot}}=\sum_{w,v}p\left(w,v\right)\log_{2}p\left(w,v\right)$
\end_inset
\end_layout
\begin_layout Itemize
Marginal Entropy:
\begin_inset Formula $H_{\mathrm{Left}}=\sum_{w}p\left(w,*\right)\log_{2}p\left(w,*\right)$
\end_inset
\end_layout
\begin_layout Itemize
Total MI:
\begin_inset Formula
\[
MI=H_{\mathrm{Tot}}-H_{\mathrm{Left}}-H_{\mathrm{Right}}=\sum_{w,v}p\left(w,v\right)\log_{2}\frac{p\left(w,v\right)}{p\left(w,*\right)p\left(*,v\right)}
\]
\end_inset
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Example Word-Pair Data Sets
\end_layout
\end_deeper
\begin_layout Frame
\begin_inset Tabular
<lyxtabular version="3" rows="11" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Corpus
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}N_{L}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
16.678
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
17.097
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
18.214
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
18.600
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
19.019
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}N_{R}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
16.690
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.117
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.228
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.620
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
19.039
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}D_{\mathrm{Tot}}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
23.224
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
23.797
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
24.748
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
25.180
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
25.627
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Sparsity
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.144
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.416
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
11.693
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
12.040
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
12.431
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Rarity
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.540
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.690
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.527
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.570
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.598
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}N_{\mathrm{Tot}}/D_{\mathrm{Tot}}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4.779
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.079
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.128
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.235
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.335
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Total Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.827
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.889
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.378
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.503
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.631
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Left Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.7963
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.8102
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.069
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.109
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.148
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Right Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.5884
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.5463
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.8321
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.8801
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.9265
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
MI
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.5572
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.4677
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.5227
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.4863
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.4431
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Sample Size Effects
\end_layout
\end_deeper
\begin_layout Frame
Vertex degree: For word
\begin_inset Formula $w$
\end_inset
, how many pairs
\begin_inset Formula $\left(u,w\right)$
\end_inset
is it in?
\end_layout
\begin_layout Frame
\begin_inset Graphics
filename ../p6-density/degree-fine.eps
width 65col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
Zipfian, with exponent
\begin_inset Formula $\gamma\approx1.6$
\end_inset
.
\end_layout
\begin_layout Itemize
Left side: 2/3rds of the data-set contains junk: bad punctuation, typos,
bad quote segmentation, stray markup.
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
MI Distribution
\end_layout
\end_deeper
\begin_layout Frame
28 Million word-pairs
\end_layout
\begin_layout Frame
\begin_inset Graphics
filename ../p6-density/pair-fmi-signal.eps
width 65col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
Sum of two curves: Gaussian and Log–Normal
\end_layout
\begin_layout Itemize
Theory: ??? Gaussian is presumably
\begin_inset Quotes eld
\end_inset
common-mode noise
\begin_inset Quotes erd
\end_inset
\end_layout
\begin_layout Itemize
Uniform random under-sampling of pairs -> Gaussian
\end_layout
\begin_layout Itemize
Same for Mandarin Chinese
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
MST Parsing
\end_layout
\end_deeper
\begin_layout Frame
Maximum Spanning Tree Parse of English.
\end_layout
\begin_layout Frame
\begin_inset Graphics
filename ../reco-image/Yuret.png
width 95col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
Cutting each edge in half yields jigsaws (
\begin_inset Quotes eld
\end_inset
disjuncts
\begin_inset Quotes erd
\end_inset
)
\end_layout
\begin_layout Itemize
Count these – Count word-jigsaw pairs
\begin_inset Formula $\left(w,d\right)$
\end_inset
\end_layout
\begin_layout Itemize
Repeat the matrix game.
\end_layout
\begin_layout Itemize
Matrix is (very) rectangular
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Jigsaw Data Sets Characterization.
\end_layout
\end_deeper
\begin_layout Frame
\begin_inset Tabular
<lyxtabular version="3" rows="11" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Trim cuts
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
full set
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1-1-1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2-2-2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5-2-2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10-4-2
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}N_{\mathrm{words}}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
18.526
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
15.542
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
13.644
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
12.889
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
12.249
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}N_{\mathrm{disjuncts}}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
24.615
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
20.599
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.662
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.447
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.369
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\log_{2}D_{\mathrm{Tot}}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
24.761
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
20.967
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
19.247
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
19.086
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.443
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Sparsity
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.380
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
15.174
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
13.058
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
12.251
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
11.175
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Rarity
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.191
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2.896
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.095
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.418
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.634
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset space \space{}
\end_inset
\begin_inset Formula $\log_{2}N_{\mathrm{Tot}}/D_{\mathrm{Tot}}$
\end_inset
\begin_inset space \space{}
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0.356
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2.248
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.384
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.461
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.889
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Total Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
24.100
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
19.486
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.711
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
17.508
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
16.875
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Left Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
23.494
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
18.346
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
16.417
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
16.163
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
15.379
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Right Entropy
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10.157
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7.937
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7.280
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7.268
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7.258
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
MI
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9.550
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.796
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.987
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.923
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5.763
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Distribution of Jigsaw (Disjunct) MI
\end_layout
\end_deeper
\begin_layout Frame
\begin_inset Graphics
filename ../p6-djmi/r4-djmi.eps
width 70col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
This is
\begin_inset Formula $MI\left(w,d\right)$
\end_inset
for word
\begin_inset Formula $w$
\end_inset
and jigsaw
\begin_inset Formula $d$
\end_inset
\end_layout
\begin_layout Itemize
Unclean.
Obscure meaning.
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Distribution of Similarity
\end_layout
\end_deeper
\begin_layout Frame
\begin_inset Graphics
filename ../en-sims-p3/mi-dist.eps
width 75col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
Wow! Gaussian!
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Similarity Metrics
\end_layout
\end_deeper
\begin_layout Frame
\end_layout
\begin_deeper
\begin_layout Itemize
Inner product:
\begin_inset Formula $i\left(w,v\right)=\sum_{d}p\left(w,d\right)p\left(v,d\right)$
\end_inset
\end_layout
\begin_layout Itemize
MI of inner product:
\begin_inset Formula
\[
MI\left(w,v\right)=\log_{2}\frac{i\left(w,v\right)i\left(*,*\right)}{i\left(w,*\right)i\left(v,*\right)}
\]
\end_inset
\end_layout
\begin_layout Itemize
Variation of Information (VI):
\begin_inset Formula
\[
VI\left(w,v\right)=\log_{2}\frac{i\left(w,v\right)}{\sqrt{i\left(w,*\right)i\left(v,*\right)}}
\]
\end_inset
\end_layout
\begin_layout Itemize
Various Jacquard distances...
\end_layout
\begin_layout Itemize
\emph on
Not the cosine distance!!! Its terrible!
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Spin Glasses
\end_layout
\end_deeper
\begin_layout Frame
\end_layout
\begin_deeper
\begin_layout Standard
Gaussian Orthogonal Ensemble
\end_layout
\begin_layout Itemize
A high–dimensional sphere.
\end_layout
\begin_layout Itemize
With a uniform random distribution on it.
\end_layout
\begin_layout Itemize
Dimension of space == size of vocabulary.
\end_layout
\begin_layout Itemize
A vector for word
\begin_inset Formula $w$
\end_inset
has direction
\begin_inset Formula $MI\left(w,u\right)$
\end_inset
.
\end_layout
\begin_layout Itemize
Each vector corresponds to the syntactic usage of that word.
\end_layout
\begin_layout Itemize
Syntax is maximally leveraged by English speakers!
\end_layout
\begin_layout Itemize
Probably holds in other languages, too.
\end_layout
\begin_layout Itemize
This is about the effectiveness of grammar in communications.
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Similarity and Clustering
\end_layout
\end_deeper
\begin_layout Frame
Clustering generalizes from specifics
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features islongtable="true" headTopDL="true" headBottomDL="true" longtabularalignment="center">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Top–ranked Clusters
\end_layout
\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\xout off
\uuline off
\uwave off
\noun off
\color none
+ — “ ” _
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
? .
!
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
must would
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\xout off
\uuline off
\uwave off
\noun off
\color none
, ;
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
He It I There
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
he she
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
was is
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
of in to from
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
are were
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
but and that as
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
has was is had could
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
might should will may
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_deeper
\begin_layout Standard
Not
\begin_inset Quotes eld
\end_inset
just
\begin_inset Quotes erd
\end_inset
similar words, but also:
\end_layout
\begin_layout Itemize
Similar grammatical behavior.
\end_layout
\begin_layout Itemize
Similar structure.
\end_layout
\begin_layout Itemize
Similar semantics.
\end_layout
\end_deeper
\begin_layout Frame
\end_layout
\begin_layout Frame
\end_layout
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Word-sense Disambiguation
\end_layout
\end_deeper
\begin_layout Frame
Each word–vector is a linear sum of multiple word-senses
\end_layout
\begin_layout Frame
\begin_inset Graphics
filename ../p4-en-clique/in-migrp-size.eps
width 47col%
\end_inset
\begin_inset Graphics
filename ../p4-en-clique/ingroup-middle.eps
width 47col%
\end_inset
\end_layout
\begin_deeper
\begin_layout Itemize
Exclusive club, Common interests
\end_layout
\begin_layout Itemize
How exclusive?
\end_layout
\begin_deeper
\begin_layout Itemize
There's a natural threshold to nearest neighbors.
\end_layout
\end_deeper
\begin_layout Itemize
Common interests?
\end_layout
\begin_deeper
\begin_layout Itemize
Disjuncts not shared by majority are different word senses
\end_layout
\end_deeper
\end_deeper
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\begin_layout Frame
\begin_inset Argument 4
status open
\begin_layout Plain Layout
Experimental Results
\end_layout
\end_inset
\end_layout
\begin_deeper
\begin_layout FrameSubtitle
Conclusion
\end_layout
\end_deeper
\begin_layout Frame
We've learned:
\end_layout
\begin_deeper
\begin_layout Itemize
Information–theoretic foundations are central.
\end_layout
\begin_layout Itemize
Experimental confirmation is central.
\end_layout
\begin_layout Itemize
Structure can be extracted from undifferentiated samples.
\end_layout
\begin_layout Itemize
Structure is a synonym for grammar.
\end_layout
\begin_layout Itemize
Recursion: structure defines a new random, uniform sampling.
\end_layout
\begin_layout Itemize
So sample again, to find differences and structure at the next level.
\end_layout
\end_deeper
\begin_layout Frame
\end_layout
\begin_layout Standard
\begin_inset Newpage newpage
\end_inset
\end_layout
\end_body
\end_document