#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 article
\begin_preamble
\usepackage{url}
\end_preamble
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding utf8
\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 default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder true
\pdf_colorlinks true
\pdf_backref page
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\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 1
\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 Title
Neural-Net vs.
Symbolic Machine Learning
\end_layout
\begin_layout Author
Linas Vepstas
\begin_inset script superscript
\begin_layout Plain Layout
*
\end_layout
\end_inset
\end_layout
\begin_layout Date
6 July 2018; working draft of 29 October 2018
\end_layout
\begin_layout Address
\begin_inset script superscript
\begin_layout Plain Layout
*
\end_layout
\end_inset
Hanson Robotics; SingularityNET
\end_layout
\begin_layout Abstract
This text provides a broad sketch of how deep-learning/neural-net approaches
are quite similar to symbolic approaches to machine learning, knowledge
representation and AI.
Taken from the right viewpoint, they can be seen to be two variants of
the same structure.
\end_layout
\begin_layout Abstract
To keep the development focused and concrete, the presentation is limited
models of natural language, and thus compares Word2Vec, SkipGram or AdaGram-sty
le vector-space approaches to traditional symbolic linguistics approaches.
To maintain concreteness, Link Grammar is used as a stand-in for a prototypical
dependency grammar.
Superficially, these systems appear to have nothing in common.
On closer examination, it becomes evident that both employ a vector representat
ion of words-in-context.
The context is an N-gram, skip-gram or adagram, in the neural-net case,
and a dependency linkage disjunct in the symbolic case.
\end_layout
\begin_layout Abstract
The similarity becomes most apparent when the word+context is viewed as
a bipartite graph, with words on the left side interconnected to contexts
on the right.
This bipartite graph can be factored into three parts, with words sorted
into buckets of word-sense-disambiguated synonyms on the left, buckets
of similar grammatical contexts on the right, and a tightly integrated
central factor.
Different approaches to factorization are explored, including low-rank
matrix factorization algorithms, information-theoretic clustering, and,
most importantly co-clustering.
\end_layout
\begin_layout Abstract
Although vector spaces are linear, semantics isn't; not really.
Vector spaces (representing the different grammatical contexts associated
with each word) can be stitched together into a unified whole, using concepts
from sheaf theory.
This completes the exposition here.
\end_layout
\begin_layout Abstract
DRAFT: This is NOT the final form of this text; it is an unfinished WORKING
DRAFT.
The last 1/4th of this text needs a do-over.
\end_layout
\begin_layout Address
ACM Subject Classification:
\begin_inset Newline newline
\end_inset
Theory of computation—Theory and algorithms for application domains—Machine
learning theory—Unsupervised learning and clustering;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Machine learning—Machine learning approaches—Neural
networks;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Machine learning—Machine learning approaches—Logical
and relational learning—Statistical relational learning;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Machine learning—Machine learning approaches—Learning
in probabilistic graphical models—Maximum entropy modeling;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Machine learning—Machine learning approaches—Learning
latent representations;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Artificial intelligence—Natural language processing;500,
\begin_inset Newline newline
\end_inset
Computing methodologies—Machine learning—Learning paradigms—Unsupervised
learning—Dimensionality reduction and manifold learning;300
\end_layout
\begin_layout Section
Introduction
\end_layout
\begin_layout Standard
Deep learning and neural nets are all the rage, today, and have displaced
symbolic AI systems in most applications.
It’s commonly believed that the two approaches have nothing to do with
each other; that they’re just completely different, and that’s that.
But this is false: there are some profound similarities; they are not only
variants of one-another, but, in a deep way, they have commonalities that
render them essentially identical.
This text attempts to explain how.
\end_layout
\begin_layout Standard
The clearest starting point for seeing this seems to be natural language,
where neural net methods have made great strides, but have not surpassed
traditional (symbolic) linguistic theory.
However, once this similarity is understood, it can be ported over to other
domains, including deep-learning strongholds such as vision.
To keep the discussion anchored, and to avoid confusing abstractions, most
of what follows will focus on linguistics; it is up to you, the reader,
to imagine other, more general settings.
\end_layout
\begin_layout Standard
The starting point for probabilistic approaches (including deep learning)
is the Bayesian network
\begin_inset CommandInset citation
LatexCommand cite
key "WP-BayesNet"
literal "true"
\end_inset
: a probability
\begin_inset Formula $P(x_{1},x_{2},…,x_{n})$
\end_inset
of observing
\begin_inset Formula $n$
\end_inset
events.
For language, the
\begin_inset Formula $x_{k}$
\end_inset
are taken to be words, and
\begin_inset Formula $n$
\end_inset
is the length of the sentence, so that
\begin_inset Formula $P(x_{1},x_{2},…,x_{n})$
\end_inset
is the “probability” of observing the sequence
\begin_inset Formula $x_{1},x_{2},…,x_{n}$
\end_inset
of words.
The technical problem with this viewpoint is the explosively large space:
if one limits oneself to a vocabulary of 10 thousand words (and many people
don’t) and sentences of 20 words or less, that’s
\begin_inset Formula $(10^{4})^{20}=10^{80}=2^{270}$
\end_inset
probabilities, an absurdly large number even for Jupiter-sized computers.
If
\begin_inset Formula $n$
\end_inset
is the length of this text, then it really seems impossible.
The key, of course, is to realize that almost all of these probabilities
are effectively zero; the goal of machine learning is to find a format,
a representation for grammar (and meaning) that effortlessly avoids that
vast ocean of zero entries.
\end_layout
\begin_layout Standard
Traditional linguistics has done exactly that: when one has a theory of
syntax, one has a formulation that clearly states which sentences should
be considered to be grammatically valid, and which ones not.
The trick is to provide a lexis (a lookup table), and some fairly small
number of rules that define how words can be combined; i.e.
arranged to the left and right of one-another.
You look up a word in the lexis (the dictionary) to find a listing of what
other words are allowed to surround it.
Try every possible combination of rules until you find one that works,
where all of the words can hook up to one-another.
For the purposes here, the easiest and the best way to visualize this is
with Link Grammar
\begin_inset CommandInset citation
LatexCommand cite
key "WP-LinkGrammar,Sleator1991,Sleator1993"
literal "true"
\end_inset
, a specific kind of dependency grammar.
All theories of grammar will constrain allowed syntax; but Link Grammar
is useful for this comparison because it explicitly identifies words to
the left, and words to the right.
Each lexical entry is like a template, a fill-in-the-blanks form, a jigsaw-puzz
le piece, telling you exactly what other words are allowed to the left,
and to the right, of the given word.
This left-right sequence makes it directly comparable to what neural-net
approaches, such as Word2Vec
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Word2Vec,Bengio2003"
literal "true"
\end_inset
or SkipGram
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013b,Mikolov2013a"
literal "true"
\end_inset
do.
\end_layout
\begin_layout Standard
What does Word2Vec do? Clearly, the
\begin_inset Formula $2^{270}$
\end_inset
probabilities in a twenty-word sentence is overwhelming; one obvious simplifica
tion is to look only at
\begin_inset Formula $N$
\end_inset
-grams: that is, to only look at the closest neighboring words, working
in a window that is
\begin_inset Formula $N$
\end_inset
words wide.
For
\begin_inset Formula $N=5$
\end_inset
, this gives
\begin_inset Formula $(10^{4})^{5}=10^{20}=2^{65}$
\end_inset
which is still huge, but is bearable.
When scanning actual text, almost all of these combinations won’t be observed;
this is just an upper bound.
In practice, a table of 5-grams fit in latter-day computer RAM.
The statistical model is to map each
\begin_inset Formula $N$
\end_inset
-gram to a vector, use that vector to define a Boltzmann distribution (
\begin_inset Formula $P=\exp(\overrightarrow{v}\cdot\overrightarrow{w})/Z$
\end_inset
), and then use gradient ascent (hill-climbing) to adjust the vector coefficient
s, so as to maximize find a maximum of the probability
\begin_inset Formula $P$
\end_inset
.
\end_layout
\begin_layout Standard
How are Word2Vec and Link Grammar similar? The above description of Link
Grammar should have already planted the idea that each lexical entry is
a lot like an
\begin_inset Formula $N$
\end_inset
-gram.
Each lexical entry tells you which words can appear to the right, and which
words to the left of a given word.
Its a bit less constrained than an
\begin_inset Formula $N$
\end_inset
-gram: there’s no particular distance limitation on the dependency links.
It can also skip over words: a lexical entry is more like a skip-gram.
Although there is no distance limitation, lexical entries still have a
small-
\begin_inset Formula $N$
\end_inset
-like behavior, not in window size, but in attachment complexity.
Determiners have a valency
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Valency"
literal "true"
\end_inset
of 1; nouns a valency of 2 or 3 (a link to a verb, to an adjective, to
a determiner); verbs a valency of 2, 3 or 4 (subject, object, etc.).
So lexical entries are like skip-grams: the window size is effectively
unbounded, but the size of the context remains small (
\begin_inset Formula $N$
\end_inset
is small).
\end_layout
\begin_layout Standard
Are there other similarities? Yes, but first, a detour.
What happened to the
\begin_inset Formula $2^{270}$
\end_inset
probabilities? A symbolic theory of grammar, such as Link Grammar, is saying
that nearly all of these are zero; the only ones that are not zero are
the ones that obey the rules of the grammar.
Consider the verb “throw” (“Kevin threw the ball”).
A symbolic theory of grammar effectively states that the only non-vanishing
probabilities are those of the form
\begin_inset Formula
\[
P(x_{1},x_{2},\cdots,x_{k}=\mbox{noun},\cdots,x_{m}=\mbox{throw},\cdots,x_{p}=\mbox{object},\cdots,x_{n})
\]
\end_inset
and that all the others must be zero.
Now, since nouns make up maybe 1/2 of all words (the subject and object
are both nouns), this constraint eliminates
\begin_inset Formula $10^{4}\times10^{4}/(2\times2)=2^{24}$
\end_inset
possibilities (shrinking
\begin_inset Formula $2^{270}$
\end_inset
to
\begin_inset Formula $2^{270-24}=2^{246}$
\end_inset
).
Nothing to sneeze at, given that its just one fairly simple rule.
But this is only one rule: there are others, which say things like “singular
count nouns must be preceded by a determiner” (so, “the ball”).
These constraints are multiplicative: if the determiner is missing, then
the probability is exactly zero.
There are only a handful of determiners, so another factor of
\begin_inset Formula $10^{4}=2^{13}$
\end_inset
is vaporized.
And so on.
A relatively small lexis quickly collapses the set of possibilities.
Can we make a back of the envelope estimate? A noun-constraint eliminates
half the words (leaving 5K of 10K possibilities).
A determiner constraint removes all but 10 possibilities.
Many grammatical classes have only a few hundred members in them (“throw”
is like “hit”, but is not like “smile”).
So, realistically, each
\begin_inset Formula $x_{k}$
\end_inset
can have only about 100 possibilities; there are only about
\begin_inset Formula $100^{20}=10^{40}=2^{130}$
\end_inset
grammatically valid sentences that are 20 words long, and these can be
encoded fairly accurately with a few thousand lexical entries.
\end_layout
\begin_layout Standard
In essence, a symbolic theory of grammar, and more specifically, dependency
grammars, accomplish the holy grail of Bayesian networks: factorizing the
Bayesian network.
The lexical rules state that there is a node in the network, for example,
\begin_inset Formula
\[
P(x_{1},x_{2},\cdots,x_{k}=\mbox{noun},\cdots,x_{m}=\mbox{throw},\cdots,x_{p}=\mbox{object},\cdots,x_{n})
\]
\end_inset
and that the entire sentences is a product of such nodes: The probability
of “Kevin threw the ball” is the product
\begin_inset Formula
\begin{multline*}
P(x_{1}=\mbox{Kevin},x_{2}=\mbox{verb},\cdots,x_{n})\\
P(x_{1},x_{2},\cdots,x_{k}=\mbox{noun},\cdots,x_{m}=\mbox{throw},\cdots,x_{p}=\mbox{object},\cdots,x_{n})\\
P(x_{1},x_{2},\cdots,x_{i}=\mbox{the},\cdots,x_{p}=\mbox{noun},\cdots,x_{n})\\
P(x_{1},x_{2},\cdots,x_{n}=\mbox{ball})
\end{multline*}
\end_inset
Stitch them all together, you’ve got a sentence, and its probability.
(In Link Grammar,
\begin_inset Formula $-\log P$
\end_inset
is called the “cost”, and costs are additive, for parse ordering.) To be
explicit: lexical entries are exactly the same thing as the factors of
a factorized Bayesian network.
What’s more, figuring out which of these factors come to play in analyzing
a specific sentence is called “parsing”.
One picks through the lookup table of possible network factors, and wires
them up, so that there are no dangling endpoints.
Lexical entries are look like subsets of a graph: a vertex, and some dangling
edges hanging from the vertex.
Pick out the right vertices (one per word), wire them together so that
there are no dangling unconnected edges, and viola! One has a graph: the
graph is the Bayesian network.
Linguists use a different name: they call it a dependency parse.
\end_layout
\begin_layout Standard
The Word2Vec/SkipGram model also factorizes, in much the same way! First,
note that the above parse can be written as a product of factors of the
form
\begin_inset Formula $P(\mbox{word}|\mbox{context})$
\end_inset
, the product running over all of the words in the sentence.
For a dependency grammar, the context expresses the dependency relations.
The Word2Vec factorization is identical; the context is simpler.
In it’s most naive form, its just a bag of the
\begin_inset Formula $N$
\end_inset
nearest words, ignoring the word-order.
But the word-order is ignored for practical reasons, not theoretical ones:
it reduces the size of the computational problem; it speeds convergence.
Smaller values of
\begin_inset Formula $N$
\end_inset
mean that long-distance dependencies are hard to discover; the skipgram
model partly overcomes this by keeping the bag small, while expanding the
size of the window.
If one uses the SkipGram model, with a large window size, and also keep
track of the word-order, and restrict to low valencies, then one very nearly
has a dependency grammar, in the style of Link Grammar.
The only difference is that such a model does not force any explicit dependency
constraints; rather, they are implicit, as the words must appear in the
context.
Compared to a normal dependency grammar, this might allow some words to
be accidentally double-linked, when they should not have been.
Dependency grammar constraints are sharper than merely asking for the correct
context.
To summarize: the notions of context are different, but there’s a clear
path from one to the other, with several interesting midway points.
\end_layout
\begin_layout Standard
The next obvious difference between Link Grammar and Word2Vec/SkipGram are
the mechanisms for obtaining the probabilities.
But this is naive: in fact, they are much more similar than it first appears.
In both systems, the starting point is (conceptually) a matrix, of dimension
\begin_inset Formula $W\times K$
\end_inset
, with
\begin_inset Formula $W$
\end_inset
the size of the vocabulary, and
\begin_inset Formula $K$
\end_inset
the size of the context.
In general,
\begin_inset Formula $K$
\end_inset
is much much larger than
\begin_inset Formula $W$
\end_inset
; for Word2Vec,
\begin_inset Formula $K$
\end_inset
could get as large as
\begin_inset Formula $W^{N}$
\end_inset
for a window size of
\begin_inset Formula $N$
\end_inset
, although, in practice, only a tiny fraction of that is observed.
Both Link Grammar and Word2Vec perform approximate matrix factorization
on this matrix.
The way the approximations are done is different.
In the case of Word2Vec, one picks some much smaller dimension
\begin_inset Formula $M$
\end_inset
, typically around
\begin_inset Formula $M=200$
\end_inset
, or maybe twice as large; this is the number of “neurons” in the middle
layer.
Then, all of
\begin_inset Formula $W$
\end_inset
is projected down to this
\begin_inset Formula $M$
\end_inset
-dimensional space (with a linear projection matrix).
Separately, the
\begin_inset Formula $K$
\end_inset
-dimensional context is also projected down.
Given a word, let its projection be the (
\begin_inset Formula $M$
\end_inset
-dimensional) vector
\begin_inset Formula $\vec{u}$
\end_inset
.
Given a context, let it’s projection be the vector
\begin_inset Formula $\vec{v}$
\end_inset
.
The probability of a word-in-context is given by a Boltzmann distribution,
as
\begin_inset Formula $\exp\left(\vec{u}\cdot\vec{v}\right)/Z$
\end_inset
where
\begin_inset Formula $\vec{u}\cdot\vec{v}$
\end_inset
is the dot product and
\begin_inset Formula $Z$
\end_inset
is a scale factor (called the
\begin_inset Quotes eld
\end_inset
partition function
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Partition"
literal "true"
\end_inset
).
The basis elements in this
\begin_inset Formula $M$
\end_inset
-dimensional space have no specific meaning; the grand-total vector space
is rotationally invariant (only the dot product matters, and dot products
are scalars).
\end_layout
\begin_layout Standard
The primary task for Word2Vec/SkipGram is to discover the two projection
matrices.
This can be done by gradient ascent (hill-climbing), looking to maximize
the probability.
The primary output of Word2Vec are the two projection matrices: one that
is
\begin_inset Formula $W\times M$
\end_inset
-dimensional, the other that is
\begin_inset Formula $M\times K$
\end_inset
-dimensional.
In general, neither of these matrices are sparse (that is, most entries
are non-zero).
\end_layout
\begin_layout Standard
Link Grammar also performs a dimensional reduction, but not quite exactly
by using projection matrices.
Rather, a word can be assigned to several different word-categories (there
are
\emph on
de facto
\emph default
about 2300 of these in the hand-built English dictionaries).
Associated with each category is a list of dozens to thousands of “disjuncts”
(dependency-grammar dependencies), which play the role analogous to “context”.
However, there are far, far fewer disjuncts than there are contexts.
This is because every (multi-word) context is associated with a handful
of disjuncts, in such a way that each disjunct stands for hundreds to as
many as millions of different contexts.
Effectively, the lexis of Link Grammar is a sparse
\begin_inset Formula $C\times D$
\end_inset
-dimensional matrix, with
\begin_inset Formula $C$
\end_inset
grammatical categories, and
\begin_inset Formula $D$
\end_inset
disjuncts, and most entries in this
\begin_inset Formula $C\times D$
\end_inset
dimensional matrix being zero.
(The upper bound on
\begin_inset Formula $D$
\end_inset
is
\begin_inset Formula $L^{V}$
\end_inset
, where
\begin_inset Formula $L$
\end_inset
is the number of link types, and
\begin_inset Formula $V$
\end_inset
is the maximum valency – about 5 or 6.
In practice,
\begin_inset Formula $D$
\end_inset
is in the tens of thousands.) The act of parsing selects a single entry
from this matrix for each word in the sentence.
The probability associated to that word is
\begin_inset Formula $\exp(-c)$
\end_inset
where
\begin_inset Formula $c$
\end_inset
is the “cost”, the numerical value stored at this matrix entry.
\end_layout
\begin_layout Standard
Thus, both systems perform a rather sharp dimensional reduction, to obtain
a much-lower dimensional intermediate form.
Word2Vec is explicitly linear, Link Grammar is not exactly.
However (and this is important, but very abstract) Link Grammar can be
described by a (non-symmetric) monoidal category.
This category is similar to that of the so-called “pregroup grammar”, and
is described in a number of places
\begin_inset CommandInset citation
LatexCommand cite
key "Marcus1967"
literal "true"
\end_inset
(some predating both Link Grammar an pregroup grammar).
The curious thing is that linear algebra is also described by a monoidal
category.
One might say that this “explains” why Word2Vec works well: it is using
the same underlying structural framework (monoidal categories) as traditional
symbolic linguistics.
The precise details are too complex to sketch here, and must remain cryptic,
for now, although they are open to those versed in category theory.
The curious reader is encouraged to explore category-theoretic approaches
to grammar, safe in the understanding that they provide a foundational
understanding, no matter which detailed theory one works in.
At the same time, the category-theoretic approach suggests how Word2Vec
(or any other neural-net or vector-based approach to grammar) can be improved
upon: it shows how syntax can be restored, with the result still looking
like a funny/unusual kind of sparse neural-net.
These are not conflicting approaches; they have far far more in common
than meets the eye.
A draft discussion is presented in
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017sheaves"
literal "true"
\end_inset
.
\end_layout
\begin_layout Standard
A few words about word-senses and semantics are in order.
The most common computational approach to semantics are
\begin_inset Quotes eld
\end_inset
vector space models
\begin_inset Quotes erd
\end_inset
(VSM).
\begin_inset CommandInset citation
LatexCommand cite
key "Turney2010"
literal "true"
\end_inset
The Word2Vec model is in many ways a VSM; sharing many common properties.
Perhaps most annoying is that the “semantics” is encoded in some opaque
way.
VSMs can distinguish different word-senses, based on context, but exactly
what part of that context
\begin_inset Quotes eld
\end_inset
matters
\begin_inset Quotes erd
\end_inset
is unclear.
Link Grammar disjuncts can also distinguish word-senses; but now the
\begin_inset Quotes eld
\end_inset
reason why
\begin_inset Quotes erd
\end_inset
becomes understandable, or human-auditable.
So, in Link Grammar, when a word is used in a specific context, the result
of parsing selects a single disjunct.
That disjunct can be thought of as a hyper-fine grammatical category; but
these are strongly correlated with meaning.
Synonyms can be discovered in the same way that they are in VSM's: if two
different words all share a lot of the same disjuncts, they are effectively
synonymous, and can be used interchangeably in sentences.
\end_layout
\begin_layout Standard
Similarly, given two different words in Word2Vec/SkipGram, if they both
project down to approximately the same vector in the intermediate layer,
they can be considered to be synonymous.
This illustrates yet another way that Link Grammar and Word2Vec/SkipGram
are similar: the list of all possible disjuncts associated with a word
is also a vector, and, if two words have almost co-linear disjunct vectors,
they are effectively synonymous.
That is, disjunct-vectors behave almost exactly like neuron intermediate-layer
vectors.
They encode similar kinds of information into a vector format.
\end_layout
\begin_layout Standard
This is also where we have the largest, and the most important difference
between Link Grammar and other vector-space models.
In the neural net approach, the intermediate neuron layer is a black box,
completely opaque and unanalyzable, just some meaningless collection of
floating-point numbers.
In Link Grammar, the disjunct vector is clear, overt, and understandable:
you can see exactly what it is encoding, because each disjunct tells you
exactly the syntactic relationship between a word, and its neighbors.
This is the great power of symbolic approaches to natural-language: they
are human-auditable, human understandable in a way that other vector-space
models are not.
(Currently; I think that what this essay describes is an effective sketch
for a technique for prying open the lid of the black box of neural nets.
But that’s for a different day.)
\end_layout
\begin_layout Standard
The remainder of this essay is structured as follows: Section 2 provides
a very quick sketch of Link Grammar, emphasizing how dependency grammars
have vector-like aspects to them.
Section 3 reviews the based CBOW, SkipGram and neural net models, setting
up some basic notation.
Section 4 defines a graph network model of language, emphasizing that statistic
al physics provides a well-developed toolset for working with graph networks.
Section 5 reviews several different techniques by which statistical information
can be gathered, and the graphical structure can be inferred, given a large
\begin_inset Quotes eld
\end_inset
flat
\begin_inset Quotes erd
\end_inset
corpus of text.
Section 6...
is the triumphant section...
\end_layout
\begin_layout Standard
Many thanks and appreciation to Hanson Robotics for providing the time to
think and write about such things.
\end_layout
\begin_layout Section
Link Grammar as a Model of Language
\begin_inset CommandInset label
LatexCommand label
name "sec:Link-Grammar"
\end_inset
\end_layout
\begin_layout Standard
One of the barriers to understanding the commonality between symbolic and
vector approaches is the notational difference.
This section provides a highly abbreviated review of the Link Grammar
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991,Sleator1993"
literal "true"
\end_inset
notation, followed by a simple modification so that it's vector-like form
becomes more apparent.
\end_layout
\begin_layout Standard
The figure below represents a (simplified) parse of the sentence
\begin_inset Quotes eld
\end_inset
Kevin threw the ball
\begin_inset Quotes erd
\end_inset
:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename skimage/parse.ps
lyxscale 160
width 30col%
\end_inset
\end_layout
\begin_layout Standard
\noindent
\align left
The labeling is prototypical of a dependency grammar: the arc labeled
\begin_inset Quotes eld
\end_inset
S
\begin_inset Quotes erd
\end_inset
denotes a subject-verb dependency;
\begin_inset Quotes eld
\end_inset
O
\begin_inset Quotes erd
\end_inset
a verb-object dependency, and
\begin_inset Quotes eld
\end_inset
D
\begin_inset Quotes erd
\end_inset
links a noun to a determiner.
The required lexical entries, in alphabetical order, are
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ball: D- & O-;
\end_layout
\begin_layout Plain Layout
Kevin: S+;
\end_layout
\begin_layout Plain Layout
the: D+;
\end_layout
\begin_layout Plain Layout
threw: S- & O+;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\noindent
The capital letters, together with a
\family typewriter
+
\family default
/
\family typewriter
-
\family default
sign, are called
\begin_inset Quotes eld
\end_inset
connectors
\begin_inset Quotes erd
\end_inset
; a pair of connectors form a
\begin_inset Quotes eld
\end_inset
link
\begin_inset Quotes erd
\end_inset
.
The
\family typewriter
+
\family default
/
\family typewriter
-
\family default
sign indicates a left-right directionality: for example, the
\family typewriter
S+
\family default
connector can only connect to the right; it must mate with an
\family typewriter
S-
\family default
connector to form an
\family typewriter
S
\family default
link.
A valid parse exists if and only if all available connectors are paired
up.
The construction
\family typewriter
S+ & O-
\family default
is called a
\begin_inset Quotes eld
\end_inset
disjunct
\begin_inset Quotes erd
\end_inset
; the name has a historical basis that is of no particular concern here.
During parsing, all connectors in a disjunct must be satisfied.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Not immediately obvious from this abbreviated sketch is that the Link Grammar
formulation of a dependency grammar is sufficiently strong to encode long-range
coordination or enforce the correct usage of set phrases/phrasemes with
\begin_inset Quotes eld
\end_inset
holes
\begin_inset Quotes erd
\end_inset
in them.
It can.
There is a set of effects that can be encoded in this way, from phonetic
structure to to morphology.
The referenced sources open the doors to understanding how this can be
done.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Each lexical entry is a word-disjunct pair; they are of the general form
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
word: A- & B+ & C+ & ...;
\end_layout
\end_inset
Because every link connects a pair of words, it can be thought of as the
set of all possible word-pairs allowed by that connector.
Thus, in the example above, the link
\family typewriter
O
\family default
is effectively equivalent to the singleton set
\family typewriter
{threw-ball}.
\family default
The above dictionary is so simple, that there are no other word-pairs in
this set; in general, this is not the case.
Thus, the capital-letter link types are actual types, in the type-theoretic
sense.
\end_layout
\begin_layout Standard
At this point, it is notationally convenient to replace each type by the
set, like so:
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ball: {the-ball}- & {threw-ball}-;
\end_layout
\begin_layout Plain Layout
Kevin: {Kevin-threw}+;
\end_layout
\begin_layout Plain Layout
the: {the-ball}+;
\end_layout
\begin_layout Plain Layout
threw: {Kevin-threw}- & {threw-ball}+;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\noindent
Each lexical entry above redundantly repeats one of the words in each word-pair.
To obtain a more compact notation, drop the redundant word, to get
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ball: the- & threw-;
\end_layout
\begin_layout Plain Layout
Kevin: threw+;
\end_layout
\begin_layout Plain Layout
the: ball+;
\end_layout
\begin_layout Plain Layout
threw: Kevin- & ball+;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\noindent
This is encoding represents the exact same dictionary as the first one,
but now using the attachment-words as connectors, instead of single letters.
The resulting sentence parse is exactly the same as before.
The link types appear to be lost; these can be partly restored, as long
as some other location records that
\family typewriter
{threw-ball}
\family default
should be replaced by the link
\family typewriter
O
\family default
.
\end_layout
\begin_layout Standard
The above representation for the dictionary is verbose, and is not very
practical for hand-crafted dictionaries.
Link types really are much more convenient.
However, the above representation helps make it brutally clear that disjuncts
effectively resemble adaptive N-gram word-contexts.
The pseudo-disjunct, where the connector types are replaced by instances
of individual words, can be used as a word-in-context.
For example, a quick glance at the pseudo-disjunct
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ran: girl- & home+;
\end_layout
\end_inset
makes it clear that it might be observed in a sentence such as
\begin_inset Quotes eld
\end_inset
the girl ran home
\begin_inset Quotes erd
\end_inset
.
Neither the subject nor the object are explicitly labeled; however, one
can maintain statistical observation counts using this method.
It provides a direct bridge from dependency grammars to corpus linguistics.
The vectorial representation arises naturally when accumulating observation
counts of different disjuncts.
A word-vector is then simply a count of all the different observed pseudo-disju
ncts.
For example, one might observe the vector
\begin_inset Formula $\vec{v}_{\mbox{ran}}$
\end_inset
, which may be represented as
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ran: 3(girl- & home+) + 2(girl- & away+);
\end_layout
\end_inset
This will naturally arise if the sentence
\begin_inset Quotes eld
\end_inset
the girl ran home
\begin_inset Quotes erd
\end_inset
was observed three times, and
\begin_inset Quotes eld
\end_inset
the girl ran away
\begin_inset Quotes erd
\end_inset
was observed twice.
\end_layout
\begin_layout Standard
From this point on, the standard panoply of vector-based techniques become
available.
Normalizing vectors to be of unit-length implies that the frequency-counts
can be re-interpreted as frequency-probabilities.
Once in possession of vectors, the standard tricks of vectorially-based
semantic similarity apply.
For example, a different vector
\begin_inset Formula $\vec{v}_{\mbox{walked}}$
\end_inset
represented as
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
walked: 2(girl- & home+) + 3(girl- & away+);
\end_layout
\end_inset
suggests that the cosine-product
\begin_inset Formula $\cos\left(\vec{v}_{\mbox{ran}},\vec{v}_{\mbox{walked}}\right)$
\end_inset
between the two might be used to judge word-similarity:
\begin_inset Quotes eld
\end_inset
ran
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
walked
\begin_inset Quotes erd
\end_inset
can be used in syntactically similar ways.
Syntactic similarity is generally associated with semantic similarity (synonymy
).
Later in this text, it is strongly argued that cosine-products are
\emph on
not
\emph default
the correct way to measure similarity (synonymy), and that the information-theo
retic Kullback-Leibler divergence is much more appropriate.
A precise formulation will be given then.
For now, it is enough to note that the availability of a vector means that
all usual vector tricks can be applied.
\end_layout
\begin_layout Standard
However, unlike (adaptive) N-gram techniques, the disjunct approach also
enables a very different kind of vector to be defined.
Given the above corpus of five sentences, one can formulate a different
vector, for the word
\begin_inset Quotes eld
\end_inset
home
\begin_inset Quotes erd
\end_inset
, as follows.
Unlike the earlier examples, the representation is a bit more awkward:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
3(ran: girl- & home+) + 2(walked: girl- & home+)
\end_layout
\end_inset
Note that the counts, here, of 3 and 2, are identical to the counts above:
all of these counts are derived from the same observational dataset.
What differs is the choice of the attachment-point for which the vector
is to be formed.
The attachment-point or
\begin_inset Quotes eld
\end_inset
germ
\begin_inset Quotes erd
\end_inset
can be high-lighted by replacing it with a star:
\end_layout
\begin_layout Standard
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
3(ran: girl- & *+) + 2(walked: girl- & *+)
\end_layout
\end_inset
This is a fundamentally different kind of vector than the earlier examples.
The ordinary (adaptive) N-gram vectors do not have this kind of representationa
l ability; they all collapse down to the same representation.
\end_layout
\begin_layout Standard
This difference turns out to be important, and has deep repercussions.
A quick sketch can be given.
These two different vector types can be distinguished by employing superscripts
\begin_inset Formula $D$
\end_inset
and
\begin_inset Formula $C$
\end_inset
:
\emph on
viz
\emph default
.
write
\begin_inset Formula $\vec{v}_{\mbox{ran}}^{D}$
\end_inset
for the disjunct-based vector, and
\begin_inset Formula $\vec{v}_{\mbox{home}}^{C}$
\end_inset
for the connector-based vector.
Given any word
\begin_inset Formula $w$
\end_inset
, there will in general always be vectors
\begin_inset Formula $\vec{v}_{w}^{D}$
\end_inset
and also
\begin_inset Formula $\vec{v}_{w}^{C}$
\end_inset
.
Even more: there will be several forms of
\begin_inset Formula $\vec{v}_{w}^{C}$
\end_inset
, with the word occupying different slots in the disjunct, thus
\begin_inset Formula $\vec{v}_{w}^{C_{1}}$
\end_inset
and
\begin_inset Formula $\vec{v}_{w}^{C_{2}}$
\end_inset
and
\begin_inset Formula $\vec{v}_{w}^{C_{3}}$
\end_inset
and so on.
So, since the germ was located in the second slot, one should write
\begin_inset Formula $\vec{v}_{\mbox{home}}^{C_{2}}$
\end_inset
instead of
\begin_inset Formula $\vec{v}_{\mbox{home}}^{C}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status collapsed
\begin_layout Plain Layout
\begin_inset Caption Standard
\begin_layout Plain Layout
Rhizome
\begin_inset CommandInset label
LatexCommand label
name "fig:Rhisome"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Plain Layout
\align center
\begin_inset Graphics
filename skimage/rhizome.jpg
lyxscale 50
width 80col%
\end_inset
\end_layout
\begin_layout Plain Layout
This image illustrates the general concept of a rhizome.
It is meant only to provide a suggestive inspiration for visualizing a
graphical sheaf.
Lines correspond to dependency grammar link constraints between tangent
vector spaces.
Since any given word in a sentence can have dependency relationships to
a number of other words, each vertex here (a word) has multiple edges attached
to it.
Any grammatically valid dependency parse is then a subtree of this image.
This image is at best only suggestive; a true sheaf would have stalks,
missing in this illustration, with stalks corresponding to the vectors
(sections) above a point in the base space (points in the base space being
words).
\size footnotesize
(Photograph of a sculpture at the Copenhagen Art Musem; photo credit Jenny
Mackness (2014).
License: Attribution-NonCommercial-ShareAlike 2.0 Generic (CC BY-NC-SA 2.0)
(
\begin_inset CommandInset href
LatexCommand href
name "Flickr"
target "https://www.flickr.com/photos/jennymackness/13388466333/in/set-72157642869468164"
literal "false"
\end_inset
))
\end_layout
\begin_layout Plain Layout
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
These vectors can be taken together as
\begin_inset Formula $\vec{v}_{w}^{D}\oplus\vec{v}_{w}^{C_{1}}\oplus\vec{v}_{w}^{C_{2}}\oplus\cdots$
\end_inset
which inhabit orthogonal subspaces of
\begin_inset Formula $\vec{V}^{D}\oplus\vec{V}^{C_{1}}\oplus\vec{V}^{C_{2}}\oplus\cdots$
\end_inset
.
The dependency-grammar constraints embodied in the connectors imply that
these vector spaces can be
\begin_inset Quotes eld
\end_inset
glued together
\begin_inset Quotes erd
\end_inset
; the dependency-grammar constraints imply that these vector subspaces can
be glued together or stitched together in a highly non-linear fashion.
The rules for gluing are in fact identical to the gluing axioms of sheaf
theory and algebraic topology.
In essence, the algebra of natural language is the algebra of a sheaf.
The disjunct vectors can be understood as a kind-of germ or stalk, similar
to the
\begin_inset Quotes eld
\end_inset
tangent vector
\begin_inset Quotes erd
\end_inset
of a kind-of
\begin_inset Quotes eld
\end_inset
manifold
\begin_inset Quotes erd
\end_inset
of natural language.
Unfortunately, algebraic geometry is a somewhat abstract branch of mathematics,
and is normally quite distant from linguistics.
This text is not appropriate for further exploration; see
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017sheaves"
literal "true"
\end_inset
for details.
\end_layout
\begin_layout Standard
To simplify these last claims somewhat, they effectively say this: the correct
conceptual model for the observational data is that of a large network
graph, with vectors of observation counts attached to each vertex.
When the vectors are consistently glued to one-another, so that only the
syntactically-allowed sentences are possible, the network begins to look
more like a bramble or rhizome, with each thread in the rhizome corresponding
to a grammatically-correct sentence.
The algebraic structure of this rhizome is a sheaf, explicitly in the sense
of sheaf theory.
Figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Rhisome"
\end_inset
illustrates a rhizome.
\end_layout
\begin_layout Section
Statistical Network Models
\end_layout
\begin_layout Standard
The task of language learning is commonly taken to be one of estimating
the probability of a text, consisting of a sequence of words.
One common model assumes that the probability of the text can be approximated
by the product of the conditional probabilities of individual words, and
specifically, of how each word conditionally depends on all of the previous
ones:
\begin_inset CommandInset citation
LatexCommand cite
key "Bengio2003"
literal "true"
\end_inset
\begin_inset Formula
\[
\widehat{P}\left(w_{1}^{T}\right)=\prod_{t=1}^{T}P\left(w_{t}\left|w_{1}^{t-1}\right.\right)
\]
\end_inset
Here, the text is presumed to consist of
\begin_inset Formula $T$
\end_inset
words
\begin_inset Formula $w_{t}$
\end_inset
occurring in sequential order.
The notation
\begin_inset Formula $w_{i}^{n}$
\end_inset
is used to denote a sequence of words, that is,
\begin_inset Formula $w_{i}^{n}=\left(w_{i},w_{i+1},\cdots,w_{n}\right)$
\end_inset
.
Thus, the text as a whole is denoted by
\begin_inset Formula $w_{1}^{T}$
\end_inset
, and so
\begin_inset Formula $\widehat{P}\left(w_{1}^{T}\right)$
\end_inset
is an approximate model for the probability
\begin_inset Formula $P\left(w_{1}^{T}\right)$
\end_inset
of observing the text (the carat over
\begin_inset Formula $P$
\end_inset
serving to remind that approximations are being made; that the model is
an approximation for the
\begin_inset Quotes eld
\end_inset
true
\begin_inset Quotes erd
\end_inset
probability.)
\end_layout
\begin_layout Standard
Although this statistical model is commonly taken as gospel, it is, of course,
wrong: we know, a priori, that sentences are mentally constructed nearly
whole before being written or spoken, and so the current word also depends
on future words, ones that follow it in the text.
This is the case not just at the sentence-level, but also at the level
of the entire text, as the writer already has a theme in mind.
To estimate the probability of a word at a given location, one must look
at words to both the left and right of the given location.
\end_layout
\begin_layout Standard
At any rate, for
\begin_inset Formula $T$
\end_inset
greater than a few dozen words, the above becomes computationally intractable,
and so instead one approximates the conditional probabilities by limiting
the word-sequence to a sliding window of length
\begin_inset Formula $N$
\end_inset
.
It is convenient, at this point, to also allow words on the left, as well
as those on the right, to determine the conditional probability.
Following Mikolov
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013b"
literal "true"
\end_inset
, one may write the probability
\begin_inset Formula
\[
p\left(w_{t}\left|w_{t-c},\cdots w_{t-1},w_{t+1},\cdots w_{t+c}\right.\right)
\]
\end_inset
of observing a word
\begin_inset Formula $w_{t}$
\end_inset
, at location
\begin_inset Formula $t$
\end_inset
in the text, as being conditioned on a local context (sliding window) of
\begin_inset Formula $N=2c$
\end_inset
surrounding words, to the left and right, in the text.
The probability of the text is then modeled by
\begin_inset Formula
\begin{equation}
\widehat{P}\left(w_{1}^{T}\right)=\prod_{t=1}^{T}p\left(w_{t}\left|w_{t-c},\cdots w_{t-1},w_{t+1},\cdots w_{t+c}\right.\right)\label{eq:bayes-factorize}
\end{equation}
\end_inset
The smaller window does make the computation more tractable.
Here, the window is written in a manifestly symmetric fashion; in general,
one might ponder a window with a different number of words to the left
or right.
\end_layout
\begin_layout Standard
The above contains another key simplification: the total probability is
assumed to factor into the product of single-word probabilities, and each
single-word probability is translationally invariant; that is, the probability
has no explicit dependence on the index
\begin_inset Formula $t$
\end_inset
.
This is commonly taken to be a reasonable simplification, but again, it
is, of course,
\begin_inset Quotes eld
\end_inset
obviously
\begin_inset Quotes erd
\end_inset
wrong.
At the sentence level, in English, we commonly do not start sentences with
verbs.
At the text level, the words at the end of a text occur with different
probabilities than those at the beginning; for example, in a dramatic story,
a new character may appear mid-way, or the setting may move from indoors
to outdoors, so that furniture-words become uncommon, while nature-words
occur more frequently.
The translational invariance only becomes plausible in the limit of
\begin_inset Formula $N\to\infty$
\end_inset
where one is considering
\begin_inset Quotes eld
\end_inset
all human language
\begin_inset Quotes erd
\end_inset
.
This too, is preposterous; first, because not everything that can be said
has been said; second, because different individuals speak differently,
and third, because new words are invented regularly, as others become archaic.
\end_layout
\begin_layout Standard
In general, it seems reasonable to assume that the distribution of words,
when taken over sliding windows of different sizes, varies in a scale-free
fashion with the window size.
So, consider a long book, and a sliding window of width
\begin_inset Formula $N=1000$
\end_inset
.
The distribution of the words within that window will be Zipfian; as the
window slides from scene to scene, the probability distribution will be
sensitive to that scene (indoors/outdoors, with/without some character...)
The positional non-uniformity persists at all window-sizes
\begin_inset Formula $N$
\end_inset
.
\end_layout
\begin_layout Standard
In what follows, we are primarily concerned with the grammatical structure
of single sentences, and not the narrative structure of longer texts.
Effectively, it is enough to work with a value of
\begin_inset Formula $N$
\end_inset
that is less than a few dozen.
The fact that sentences typically do not start with verbs can be
\begin_inset Quotes eld
\end_inset
explained
\begin_inset Quotes erd
\end_inset
by the rules of syntax; no explicit factorization for single-word probabilities
is required.
Thus, the translation-invariant
\begin_inset Quotes eld
\end_inset
Bayesian network
\begin_inset Quotes erd
\end_inset
factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:bayes-factorize"
\end_inset
is appropriate and suitable for the current task.
As will be seen in later chapters, this factorization can be improved on,
and performed much more cleanly and elegantly.
\end_layout
\begin_layout Subsection
N-Gram Model
\end_layout
\begin_layout Standard
Without any further elaboration, and taken at face value, the above defines
what is more-or-less the
\begin_inset Quotes eld
\end_inset
classic
\begin_inset Quotes erd
\end_inset
N-gram model.
The general property is that there is a sliding window of
\begin_inset Formula $N$
\end_inset
words in width, and one is using all of those words to make a prediction.
Because of the combinatorial explosion in the size of the vocabulary,
\begin_inset Formula $N$
\end_inset
is usually kept small:
\begin_inset Formula $N=3$
\end_inset
(trigrams) or
\begin_inset Formula $N=5$
\end_inset
.
That is, for a vocabulary of
\begin_inset Formula $W$
\end_inset
words, there are
\begin_inset Formula $W^{N}$
\end_inset
probabilities
\begin_inset Formula $p$
\end_inset
that must be computed (trained) and remembered.
For
\begin_inset Formula $W=10^{4}$
\end_inset
and
\begin_inset Formula $N=3$
\end_inset
, this requires up to
\begin_inset Formula $W^{N}=10^{12}=2^{40}$
\end_inset
probabilities to be maintained: even if most 3-word sequences are never
observed, this is still clearly near the edge of what is possible with
present-day computers.
\end_layout
\begin_layout Standard
The model can be made computationally tractable in various ways.
One well-discussed variant is to blend together, in varying proportions,
the models for
\begin_inset Formula $N=0$
\end_inset
,
\begin_inset Formula $N=1$
\end_inset
and
\begin_inset Formula $N=2$
\end_inset
.
Such an approach is of no particular interest for the subsequent development;
grammar happens at larger values of
\begin_inset Formula $N$
\end_inset
, and the goal is to create effective factorizations that encompass grammar.
\end_layout
\begin_layout Subsection
Model Building
\end_layout
\begin_layout Standard
The combinatorial explosion can be avoided by proposing models that
\begin_inset Quotes eld
\end_inset
guess
\begin_inset Quotes erd
\end_inset
, in an
\emph on
a priori
\emph default
fashion, that some of these probabilities are zero, or that they are (approxima
tely) equal to one-another, or that they can be grouped or summed in some
other ways.
More correctly, one hypothesizes that the vast majority of the probabilities
are either zero or fall into classes where they are equal.
If one can find a model that captures that all but one in ten-thousand
such probabilities are zero, then that model becomes computationally tractable
again.
An alternate model is to hypothesize that certain linear combinations of
the probabilities are all equal to one-another.
The latter approach is exactly that of the neural net and deep learning
approaches: the linear combinations of equivalent probabilities are the
ones represented by various layers in the neural net.
\end_layout
\begin_layout Standard
There is a fairly rich variety of such models.
Reviewed immediately below are two foundational models: the so-called CBOW
model, and the SkipGram model.
The general goal of this paper is to demonstrate that Link Grammar, and
thus dependency grammars in general, can be understood to also fit into
this same class of probabilistic models.
What differs is the mechanism by which the models are trained; the Link
Grammar training algorithm, already sketched above, is not a hill-climbing/deep
-learning technique.
A proper comparison of training algorithms will be made after the initial
review of the CBOW and SkipGram models.
\end_layout
\begin_layout Subsection
CBOW
\begin_inset CommandInset label
LatexCommand label
name "subsec:CBOW"
\end_inset
\end_layout
\begin_layout Standard
Mikolov,
\emph on
etal
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013a,Mikolov2013b"
literal "true"
\end_inset
\emph default
propose a model termed as the
\begin_inset Quotes eld
\end_inset
continuous bag-of-words
\begin_inset Quotes erd
\end_inset
model.
It is presented as a simplification of neural net models that have been
proposed earlier.
As a simplification, it makes sense to present it first; neural net models
are reviewed below.
\end_layout
\begin_layout Standard
In the CBOW model, each (input) word
\begin_inset Formula $w$
\end_inset
is represented by an
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
vector
\begin_inset Formula $\vec{v}_{w}$
\end_inset
of relatively small dimension.
One does the same in an ordinary bag-of-words model, but with much higher
dimension.
In an ordinary bag-of-words model, one considers a vector space of dimension
\begin_inset Formula $W$
\end_inset
, with
\begin_inset Formula $W$
\end_inset
being the size of the vocabulary.
One then makes frequentist observations, counting how often each word is
observed in some text.
The result of this counting is a vector living in a
\begin_inset Formula $W$
\end_inset
-dimensional space.
Different texts correspond to different vectors.
However, nothing about the grammar of individual sentences or words is
learned in this process.
\end_layout
\begin_layout Standard
In the CBOW model, the dimension of the space in which the vector
\begin_inset Formula $\vec{v}_{w}$
\end_inset
lives is set to a much smaller value
\begin_inset Formula $D\ll W$
\end_inset
.
Commonly used values for
\begin_inset Formula $D$
\end_inset
are in the range of 50–300; by contrast, typical vocabulary sizes
\begin_inset Formula $W$
\end_inset
range from
\begin_inset Formula $10^{4}$
\end_inset
to
\begin_inset Formula $10^{6}$
\end_inset
.
The mismatch of dimensions results in the mapping sometimes being called
\begin_inset Quotes eld
\end_inset
dimensional reduction
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
In the CBOW model, the mapping from the space of words to the space of vectors
\begin_inset Formula $\vec{v}_{w}$
\end_inset
is linear; there are no non-linear functions, as there would be in a neural
net.
That is, the mapping is given by a matrix
\begin_inset Formula $\pi$
\end_inset
of dimension
\begin_inset Formula $D\times W$
\end_inset
.
Maps from higher to lower dimensional spaces are called
\begin_inset Quotes eld
\end_inset
projections
\begin_inset Quotes erd
\end_inset
.
(The notation of the lower-case Greek letter
\begin_inset Formula $\pi$
\end_inset
for projection is common-place in the mathematical literature, but uncommon
in the machine-learning world.
It's convenient here, as it avoids burning yet another roman letter.) The
projection matrix
\begin_inset Formula $\pi$
\end_inset
is unknown at the outset; the goal of training is to determine it.
\end_layout
\begin_layout Standard
The CBOW is a model of the conditional probability
\begin_inset Formula
\[
p\left(w_{t}\left|w_{t-c},\cdots w_{t-1},w_{t+1},\cdots w_{t+c}\right.\right)
\]
\end_inset
As already mentioned, it projects each word down to a lower-dimensional
space.
To get the output word
\begin_inset Formula $w_{t}$
\end_inset
, one has to
\begin_inset Quotes eld
\end_inset
unproject
\begin_inset Quotes erd
\end_inset
back out, which is conventionally done with a different projection matrix
\begin_inset Formula $\pi^{\prime}$
\end_inset
.
To establish some notation: let
\begin_inset Formula $\hat{e}_{w}$
\end_inset
be a
\begin_inset Formula $W$
\end_inset
-dimensional unit vector that is all-zero, except for a single, solitary
1 in the
\begin_inset Formula $w$
\end_inset
'th position (this is sometimes called the
\begin_inset Quotes eld
\end_inset
one-hot
\begin_inset Quotes erd
\end_inset
vector in machine learning).
Then one has that
\begin_inset Formula $\vec{v}_{w}=\pi\hat{e}_{w}$
\end_inset
is the projection of
\begin_inset Formula $w$
\end_inset
– equivalently, it is the
\begin_inset Formula $w$
\end_inset
'th column of the matrix
\begin_inset Formula $\pi$
\end_inset
.
For the reverse projection, let
\begin_inset Formula $\vec{u}_{w}=\pi^{\prime}\hat{e}_{w}$
\end_inset
.
(Many machine-learning texts write
\begin_inset Formula $\vec{v}_{w}^{\prime}$
\end_inset
for
\begin_inset Formula $\vec{u}_{w}$
\end_inset
; we use a different letter here, instead of a prime, to help maintain distinctn
ess.
Almost all machine-learning texts avoid putting the vector arrow over the
letters; here, they serve to remind the reader where the vector is, so
as to avoid confusion in later sections.)
\end_layout
\begin_layout Standard
Let
\begin_inset Formula $I$
\end_inset
be the set of context (or
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
) word subscript offsets; to be consistent with the above, one would have
\begin_inset Formula $I=\left\{ -c,-c+1,\cdots,-1,+1,\cdots,+c\right\} $
\end_inset
.
By abuse of notation, one might also write, for offset
\begin_inset Formula $t$
\end_inset
or for word
\begin_inset Formula $w_{t}$
\end_inset
, that
\begin_inset Formula
\[
I=\left\{ t-c,t-c+1,\cdots t-1,t+1,\cdots,t+c\right\}
\]
\end_inset
or that
\begin_inset Formula
\[
I=w_{I}=\left\{ w_{t-c},w_{t-c+1},\cdots,w_{t-1},w_{t+1},\cdots,w_{t+c}\right\}
\]
\end_inset
Exactly which of these sets is intended will hopefully be clear from context.
\end_layout
\begin_layout Standard
The CBOW model then uses the Boltzmann distribution obtained from a certain
partition function, sometimes called the
\begin_inset Quotes eld
\end_inset
softmax
\begin_inset Quotes erd
\end_inset
model.
The model is given by
\begin_inset Formula
\begin{equation}
p\left(w_{t}\left|w_{I}\right.\right)=\frac{\exp\,\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}}{\sum_{j\in W}\exp\,\sum_{i\in I}\vec{u}_{j}\cdot\vec{v}_{i}}\label{eq:CBOW}
\end{equation}
\end_inset
The sum in the numerator runs over all words in the input set
\begin_inset Formula $I$
\end_inset
; the sum in the denominator runs over all words in the vocabulary
\begin_inset Formula $W$
\end_inset
.
The sum in the denominator explicitly normalizes the probability to be
a unit probability.
That is, for fixed
\begin_inset Formula $w_{I}$
\end_inset
, one has that
\begin_inset Formula $1=\sum_{j}p\left(w_{j}\left|w_{I}\right.\right)$
\end_inset
.
\end_layout
\begin_layout Standard
Computation of the matrices
\begin_inset Formula $\pi$
\end_inset
and
\begin_inset Formula $\pi^{\prime}$
\end_inset
is done by explicitly expanding them in the expression above, and then
performing hill-climbing, attempting to maximize the probability.
To provide a nicer landscape for hill-climbing, it is usually done on the
\begin_inset Quotes eld
\end_inset
loss function
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $E=-\log p\left(w_{t}\left|w_{I}\right.\right)$
\end_inset
.
One works with the gradient
\begin_inset Formula $\nabla_{\pi,\pi^{\prime}}E$
\end_inset
and takes small steps uphill.
The detailed mechanics for doing this does not concern this essay; it is
widely covered in many other texts
\begin_inset CommandInset citation
LatexCommand cite
key "Minnaar2015b"
literal "true"
\end_inset
.
\end_layout
\begin_layout Standard
By convention,
\begin_inset Formula $\pi$
\end_inset
and
\begin_inset Formula $\pi^{\prime}$
\end_inset
are taken to be two distinct projection matrices.
I do not currently know of any theoretical reason nor experimental result
why this should be done, instead of taking
\begin_inset Formula $\pi=\pi^{\prime}$
\end_inset
.
Knowledgeable readers are encouraged to correct my misperception.
\end_layout
\begin_layout Subsection
SkipGram
\end_layout
\begin_layout Standard
The SkipGram model is very similar to the CBOW model, and is commonly presented
as it's opposite.
It uses essentially the same Boltzmann distribution as CBOW, except that
it is now looking at the probability
\begin_inset Formula $p\left(w_{I}\left|w_{t}\right.\right)$
\end_inset
of the context
\begin_inset Formula $I$
\end_inset
given the target word
\begin_inset Formula $w_{t}$
\end_inset
.
Explicitly, the model is given by
\begin_inset Formula
\begin{equation}
p\left(w_{I}\left|w_{t}\right.\right)=\frac{\exp\,\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}}{\sum_{I\in W^{N}}\exp\,\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}}\label{eq:SkipGram}
\end{equation}
\end_inset
That is, the word
\begin_inset Formula $w_{t}$
\end_inset
is held fixed, and the sum ranges over all possible
\begin_inset Formula $N$
\end_inset
-tuples
\begin_inset Formula $I$
\end_inset
in the (now much larger) space
\begin_inset Formula $W^{N}$
\end_inset
(as always,
\begin_inset Formula $N$
\end_inset
is the width of the sliding window).
\end_layout
\begin_layout Standard
As in the CBOW model, the projection matrices
\begin_inset Formula $\pi$
\end_inset
and
\begin_inset Formula $\pi^{\prime}$
\end_inset
are computed by means of hill-climbing the loss-function.
The important contribution of of Mikolov
\emph on
et al
\emph default
.
is not only to describe this model, but also to propose several algorithmic
variations to minimize the RAM footprint, and to improve the speed of convergen
ce.
\end_layout
\begin_layout Standard
Both SkipGram and CBOW are sometimes called
\begin_inset Quotes eld
\end_inset
neural net
\begin_inset Quotes erd
\end_inset
models, but this is perhaps slightly misleading, as neither make use of
the sigmoid function that is characteristic of neural nets.
Given that the characteristic commonality is that the probabilities are
obtained by hill-climbing, it seems more appropriate to simply call these
\begin_inset Quotes eld
\end_inset
deep learning
\begin_inset Quotes erd
\end_inset
models.
The distinction is made more clear in the next section.
\end_layout
\begin_layout Subsection
Perceptrons and Neural Nets
\end_layout
\begin_layout Standard
The neural net model proposed by Bengio
\begin_inset CommandInset citation
LatexCommand cite
key "Bengio2003"
literal "true"
\end_inset
is worth reviewing, as it places the CBOW and SkipGram models in context.
It builds on the same basic mechanics, except that it now replaces the
dot-product
\begin_inset Formula $\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}$
\end_inset
by a
\begin_inset Quotes eld
\end_inset
hidden
\begin_inset Quotes erd
\end_inset
feed-forward (perceptron) neural layer.
\end_layout
\begin_layout Standard
The perceptron consists of another projection, this time called the
\begin_inset Quotes eld
\end_inset
weight matrix
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $h$
\end_inset
, and a non-linear sigmoid function
\begin_inset Formula $\sigma\left(x\right)$
\end_inset
, which is commonly taken to be
\begin_inset Formula $\sigma\left(x\right)=\tanh x$
\end_inset
or
\begin_inset Formula $\sigma\left(x\right)=1/\left(1+e^{-x}\right)$
\end_inset
or similar, according to taste.
\end_layout
\begin_layout Standard
The input to the weight matrix is the vector
\begin_inset Formula $\vec{v}_{I}$
\end_inset
which is a Cartesian product of the input vectors
\begin_inset Formula $\vec{v}_{i}$
\end_inset
for the
\begin_inset Formula $i\in I$
\end_inset
.
That is,
\begin_inset Formula
\[
\vec{v}_{I}=\vec{v}_{t-c}\times\vec{v}_{t-c+1}\times\cdots\times\vec{v}_{t+c}
\]
\end_inset
where, for illustration, we've taken the same
\begin_inset Formula $I$
\end_inset
as given in the previous sections.
This vector is
\begin_inset Formula $ND$
\end_inset
-dimensional, where, as always,
\begin_inset Formula $N$
\end_inset
is the cardinality of
\begin_inset Formula $I$
\end_inset
and
\begin_inset Formula $D$
\end_inset
is the dimension of the projected space.
\end_layout
\begin_layout Standard
The input vector
\begin_inset Formula $\vec{v}_{I}$
\end_inset
is then sent through a weight matrix
\begin_inset Formula $h$
\end_inset
to a
\begin_inset Quotes eld
\end_inset
hidden
\begin_inset Quotes erd
\end_inset
neuron layer consisting of
\begin_inset Formula $H$
\end_inset
neurons.
That is, the matrix
\begin_inset Formula $h$
\end_inset
has dimensions
\begin_inset Formula $ND\times H$
\end_inset
.
An offset vector
\begin_inset Formula $\vec{d}$
\end_inset
(of dimension
\begin_inset Formula $H$
\end_inset
) is used to properly center the result in the sigmoid.
The output of the perceptron is then the
\begin_inset Formula $H$
\end_inset
-dimensional vector
\begin_inset Formula
\[
\vec{s}=\sigma\left(h\vec{v}+\vec{d}\right)
\]
\end_inset
where the sigmoid is understood to act component by component; that is,
the
\begin_inset Formula $k$
\end_inset
'th component
\begin_inset Formula $\left[\vec{s}\right]_{k}$
\end_inset
of the vector
\begin_inset Formula $\vec{s}$
\end_inset
is given by
\begin_inset Formula
\[
\left[\vec{s}\right]_{k}=\sigma\left(\left[h\vec{v}+\vec{d}\right]_{k}\right)
\]
\end_inset
This is then passed through the
\begin_inset Quotes eld
\end_inset
anti-
\begin_inset Quotes erd
\end_inset
projection matrix
\begin_inset Formula $\pi^{\prime}$
\end_inset
, as before, except that here,
\begin_inset Formula $\pi^{\prime}$
\end_inset
must be
\begin_inset Formula $H\times W$
\end_inset
-dimensional.
Maintaining the notation from earlier sections, the perceptron model is
then
\begin_inset Formula
\[
p\left(w_{t}\left|w_{I}\right.\right)=\frac{\exp\,\vec{u}_{t}\cdot\vec{s}}{\sum_{j\in W}\exp\,\vec{u}_{j}\cdot\vec{s}}
\]
\end_inset
Just as in the CBOW/SkipGram model, training can be accomplished by hill-climbin
g, this time by taking not only
\begin_inset Formula $\pi$
\end_inset
and
\begin_inset Formula $\pi^{\prime}$
\end_inset
as free parameters, but also
\begin_inset Formula $h$
\end_inset
and
\begin_inset Formula $\vec{d}$
\end_inset
.
\end_layout
\begin_layout Standard
Typical choices for the dimension
\begin_inset Formula $H$
\end_inset
is in the 500–1000 range, and is thus comparable to the size of
\begin_inset Formula $ND$
\end_inset
, making the weight matrix
\begin_inset Formula $h$
\end_inset
approximately square.
That is, the weight matrix
\begin_inset Formula $h$
\end_inset
does a minimal amount of, if any at all, dimensional reduction.
\end_layout
\begin_layout Section
Graph Network Models of Language
\begin_inset CommandInset label
LatexCommand label
name "sec:Network Models"
\end_inset
\end_layout
\begin_layout Standard
Superficially, the graphical approach of a symbolic dependency grammar,
such as Link Grammar, seems to have no resemblance at all to the probabilistic
approach of neural network models.
The previous sections hinted at the presence of vectors in both systems;
but the vectors are superficially different, and the role of probability
in either remained less than entirely clear.
The differences are less than they seem; different notation obscures similarity
; different traditions emphasize different aspects so strongly that even
minor hints of similarity are lost.
This section attempts to articulate the commonality.
\end_layout
\begin_layout Standard
Both the neural network and the symbolic graphical approaches to language
could be termed to two different faces of a common graphical network model
of language.
The structure of graph networks are a part of the standard curriculum of
physics and statistical mechanics.
This section begins with a reiteration that Link Grammar disjuncts resemble
the factors of a factored Bayesian network.
Next, the loss functions of the CBOW/SkipGram model can be seen as a manifestat
ion of standard (statistical mechanics) maximum entropy principles.
Equipped with this insight, one can proceed along a common track in physics:
derive the statistical models from a partition function.
The partition function encodes
\begin_inset Quotes eld
\end_inset
all possible knowledge
\begin_inset Quotes erd
\end_inset
of a network graph; specific factors of this graph are called
\begin_inset Quotes eld
\end_inset
Feynman diagrams
\begin_inset Quotes erd
\end_inset
.
With the tools of physics thus deployed, a dependency parse, when obtained
statistically, can be recognized as a kind of Feynman diagram.
The dependency grammars of natural language are Feynman diagrams of statistical
physics.
\end_layout
\begin_layout Standard
This section sets the stage for the next, which reviews several different
approaches for obtaining the statistical information needed to correctly
factor a graph network.
\end_layout
\begin_layout Subsection
Disjuncts as Context
\end_layout
\begin_layout Standard
Consider the probability
\begin_inset Formula
\[
p\left(w_{t}\left|w_{t-c},\cdots w_{t-1},w_{t+1},\cdots w_{t+c}\right.\right)
\]
\end_inset
This is meant to indicate the probability of observing the word
\begin_inset Formula $w_{t}$
\end_inset
, given
\begin_inset Formula $c$
\end_inset
words that occur before it, and
\begin_inset Formula $c$
\end_inset
words that occur after it.
Let
\begin_inset Formula $c=1$
\end_inset
and let
\begin_inset Formula $w_{t}=\mbox{ran}$
\end_inset
,
\begin_inset Formula $w_{t-1}=\mbox{girl}$
\end_inset
and
\begin_inset Formula $w_{t+1}=\mbox{home}$
\end_inset
.
This clearly resembles the Link Grammar disjunct
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ran: girl- & home+;
\end_layout
\end_inset
One difference is the Link Grammar disjunct notation does not provide any
location at which to attach a probability.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The Link Grammar software does provide a device, called the
\begin_inset Quotes eld
\end_inset
cost
\begin_inset Quotes erd
\end_inset
, which is an additive floating point number that represents the penalty
of using a particular disjunct.
It can be thought of as being the same thing as
\begin_inset Formula $-\log p\left(w|d\right)$
\end_inset
.
The hand-crafted dictionaries provide hand-crafted estimates for this cost/log-
likelihood.
\end_layout
\end_inset
This can be remedied in a straight-forward manner: write
\begin_inset Formula $d$
\end_inset
for the disjunct,
\begin_inset Formula $\mbox{girl- \& home+}$
\end_inset
in this example.
One can then define the probability
\begin_inset Formula
\[
p\left(w|d\right)=\frac{p\left(w,d\right)}{p\left(*,d\right)}
\]
\end_inset
where
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is the probability of observing the pair
\begin_inset Formula $\left(w,d\right)$
\end_inset
, while
\begin_inset Formula
\[
p\left(*,d\right)=\sum_{w=1}^{W}p\left(w,d\right)
\]
\end_inset
is simply the sum over all words in the vocabulary.
\end_layout
\begin_layout Standard
The resemblance, at this point, should be obvious: the disjunct
\begin_inset Formula $d$
\end_inset
plays the role of the
\begin_inset Formula $N$
\end_inset
-gram context.
Abusing the existing notation, one should understand that
\begin_inset Formula
\[
d\approx w_{t-c},\cdots w_{t-1},w_{t+1},\cdots w_{t+c}
\]
\end_inset
The abuse of notation was partly cured by writing
\begin_inset Formula $w_{I}$
\end_inset
for the
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
words of the CBOW/SkipGram models, so that
\begin_inset Formula $I$
\end_inset
was a set of relative indexes into the text.
The disjunct notation does everything that the index notation can do: it
specifies a fixed order of words, to the left, and to the right of the
target (
\begin_inset Quotes eld
\end_inset
output
\begin_inset Quotes erd
\end_inset
) word
\begin_inset Formula $w_{t}$
\end_inset
.
More precisely, the disjunct notation actively skips over some of the words
in the context.
Rather than specifying a fixed offset from the target word, the disjunct
provides a relative sequential ordering of the context-words, left to right,
without specifying distance.
\end_layout
\begin_layout Standard
This change of notation allows the disjunct to do more than the index set
notation: the disjunct effectively encodes syntactic information.
How this is done was already detailed in section
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Link-Grammar"
\end_inset
.
With this seemingly minor change of notation, from indexes to sequential
lists, one gains access to grammatical information.
Do keep in mind that by working with disjunct notation, nothing is lost:
if one wished, one could take the disjunct as being a sequence of words,
with no gaps allowed between the words.
If this is done, then the disjunct
\begin_inset Formula $d$
\end_inset
becomes fully compatible with the index set
\begin_inset Formula $I$
\end_inset
and one can legitimately write that
\begin_inset Formula $d=w_{I}$
\end_inset
are just two notations for saying the same thing.
The disjunct encodes
\begin_inset Quotes eld
\end_inset
more information
\begin_inset Quotes erd
\end_inset
, in the information-theoretic sense of encoding
\begin_inset Quotes eld
\end_inset
more bits of info
\begin_inset Quotes erd
\end_inset
than the index notation can.
\end_layout
\begin_layout Subsection
Skip-Grams and Syntactic Structure
\end_layout
\begin_layout Standard
The above explicit identification of
\begin_inset Formula $d=w_{I}$
\end_inset
suggests that CBOW and SkipGram models already encode grammatical information,
and that finding it is as simple as re-interpreting
\begin_inset Formula $w_{I}$
\end_inset
as a disjunct.
That is, given either form
\begin_inset Formula $p\left(w_{t}\left|w_{I}\right.\right)$
\end_inset
or
\begin_inset Formula $p\left(w_{I}\left|w_{t}\right.\right)$
\end_inset
, simply re-interpret
\begin_inset Formula $w_{I}$
\end_inset
as specifying left-going and right-going connectors.
The Link Grammar cost is nothing other than the
\begin_inset Quotes eld
\end_inset
loss function
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $E=-\log p\left(w_{t}\left|w_{I}\right.\right)$
\end_inset
; they are one and the same thing.
One could do this immediately, today: given a SkipGram dataset, one can
just write an export function, and dump the contents into a Link Grammar
dictionary.
All that remains would be to evaluate the quality of the results.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
These statements are also perhaps misleading: conventional systems really
do use a
\begin_inset Quotes eld
\end_inset
bag of words
\begin_inset Quotes erd
\end_inset
, ignoring the word-order.
Yet word-order is needed to write a disjunct.
Thus, existing off-the-shelf software would have to be modified to track
word-order, and this modification will require an order of magnitude more
storage, possibly rendering the computation intractably large or slow.
Keeping track of word order is theoretically interesting, but entirely
misses the tractability issue that these models were invented to solve.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Disjuncts are intended to capture the dependency grammar description of
a language.
A dependency grammar naturally
\begin_inset Quotes eld
\end_inset
skips
\begin_inset Quotes erd
\end_inset
over words, and
\begin_inset Quotes eld
\end_inset
adaptively
\begin_inset Quotes erd
\end_inset
sizes the context to be appropriate.
Consider the dependency parse of
\begin_inset Quotes eld
\end_inset
The girl, upset by the taunting, ran home in tears.
\begin_inset Quotes erd
\end_inset
There are four words, and two punctuation symbols separating the word
\begin_inset Quotes eld
\end_inset
girl
\begin_inset Quotes erd
\end_inset
from the word
\begin_inset Quotes eld
\end_inset
ran
\begin_inset Quotes erd
\end_inset
.
Dependency grammars do not have any difficulty in arranging for the attachment
of the words
\begin_inset Quotes eld
\end_inset
girl–ran
\begin_inset Quotes erd
\end_inset
, skipping over the post-nominal modifier phrase
\begin_inset Quotes eld
\end_inset
upset by the taunting
\begin_inset Quotes erd
\end_inset
, which attaches to the noun, and not the verb: it's the girl who is upset,
not the running.
\end_layout
\begin_layout Standard
Such long-distance attachments are problematic for CBOW or Skip-Grams, in
several ways.
One is that the window
\begin_inset Formula $N$
\end_inset
would have to be quite large to skip over the post-nominal modifier.
Counting punctuation, one must look at least seven words to the right,
in the above example.
If the window is symmetric about the target word, this calls for
\begin_inset Formula $N\ge14$
\end_inset
, which is a bit larger than currently reported results; for example, Mikolov
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013b"
literal "true"
\end_inset
reports results for
\begin_inset Formula $N=5$
\end_inset
.
The point here is that
\begin_inset Formula
\[
p\left(w_{t}=\mbox{girl}\left|w_{t-1}=\mbox{the },w_{t+1}=\mbox{ran}\right.\right)
\]
\end_inset
can be trivially re-interpreted as the dictionary entry
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
girl: the- & ran+;
\end_layout
\end_inset
However, that is not what is needed to parse
\begin_inset Quotes eld
\end_inset
The girl, upset by the taunting, ran home in tears.
\begin_inset Quotes erd
\end_inset
What is needed, instead, is the dictionary entry
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
girl: the- & upset+ & ran+;
\end_layout
\end_inset
which is invisible with an
\begin_inset Formula $N=5$
\end_inset
window.
The punctuation is also important for the post-nominal modifier; somewhere
one must also find
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
upset: girl- & ,- & by+ & ,+;
\end_layout
\end_inset
which also does not fit in an
\begin_inset Formula $N=5$
\end_inset
window; it requires at least
\begin_inset Formula $N=9$
\end_inset
.
Long-distance attachments present a problem for the simpler, less sophisticated
deep-learning models.
\end_layout
\begin_layout Standard
Another difficulty in a naive correspondence with index notation is that
dependency grammars are naturally
\begin_inset Quotes eld
\end_inset
adaptive
\begin_inset Quotes erd
\end_inset
by design: verbs tend to have more attachments that nouns, which have more
attachments than determiners or adjectives.
That is, dependency grammars already
\begin_inset Quotes eld
\end_inset
know
\begin_inset Quotes erd
\end_inset
that the correct size of the context for determiners and adjectives is
one: a determiner can typically modify only one noun.
One expects the entry
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
the: girl+;
\end_layout
\end_inset
The size of the context for the word
\begin_inset Quotes eld
\end_inset
the
\begin_inset Quotes erd
\end_inset
is just
\begin_inset Formula $N=1$
\end_inset
; more is not needed.
If the deep-learning model fails to explicitly contain an entry of the
form
\begin_inset Formula
\[
p\left(w_{t}=\mbox{the}\left|w_{t+1}=\mbox{girl}\right.\right)
\]
\end_inset
with no other context words present, then one will have trouble building
a suitable dictionary.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
I assume that Parsey McParseFace overcomes all of these problems ins some
way; I have not studied it.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Statistical Mechanics and the Partition Function
\end_layout
\begin_layout Standard
The CBOW and SkipGram models of language, namely equations
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
and SkipGram
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
, are commonly discussed as optimization problems, and the utility functions
are sometimes called
\begin_inset Quotes eld
\end_inset
softmax
\begin_inset Quotes erd
\end_inset
functions, or
\begin_inset Quotes eld
\end_inset
loss functions
\begin_inset Quotes erd
\end_inset
.
From the point of view of statistical mechanics, these utility functions
can be easily recognized as Gibbs distributions.
This allows all of the traditional intuition and tools of statistical mechanics
to be brought to bear on the language problem.
Specifically, the probabilities are obtainable from a partition function.
\end_layout
\begin_layout Standard
Given that equations
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
and
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
are conditional probabilities, one can deduce that the joint probability
in these models is given by
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
p\left(w_{t},w_{I}\right)=\frac{\exp\,\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}}{\sum_{w\in W}\sum_{I\in W^{N}}\exp\,\sum_{i\in I}\vec{u}_{w}\cdot\vec{v}_{i}}
\]
\end_inset
This can be obtained by applying variational principles to the partition
function
\begin_inset Formula
\begin{equation}
Z\left[J\right]=\sum_{w\in W}\sum_{I\in W^{N}}\exp\,\left(\sum_{i\in I}\vec{u}_{w}\cdot\vec{v}_{i}+J_{wI}\right)\label{eq:Partition function}
\end{equation}
\end_inset
In physics literature, the
\begin_inset Formula $J_{w_{t},I}$
\end_inset
are called
\begin_inset Quotes eld
\end_inset
sources
\begin_inset Quotes erd
\end_inset
or the
\begin_inset Quotes eld
\end_inset
current
\begin_inset Quotes erd
\end_inset
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Mathematically, they resemble electric charges or currents.
\end_layout
\end_inset
, and can be understood as parameters that are nominally zero.
That is, they are set to zero
\begin_inset Quotes eld
\end_inset
in the real world
\begin_inset Quotes erd
\end_inset
, but serve as placeholders within the partition function so that variational
principles can be applied.
Doing so yields the standard Boltzmann distribution:
\begin_inset Formula
\[
p\left(w_{t},w_{I}\right)=\left.\frac{\delta\ln Z\left[J\right]}{\delta J_{w_{t},I}}\right|_{J=0}
\]
\end_inset
In other words, CBOW/SkipGram fit squarely into the standard framework of
maximum entropy principles.
This is no accident, of course; the
\begin_inset Quotes eld
\end_inset
softmax
\begin_inset Quotes erd
\end_inset
function was used precisely because it gives the maximum entropy distribution.
\end_layout
\begin_layout Standard
The last statement can be made even more precise.
A language model is a probability distribution
\begin_inset Formula $p(w_{1},w_{2},\cdots)$
\end_inset
defined over a sequence of words
\begin_inset Formula $w_{1},w_{2},\cdots$
\end_inset
.
The set of all such sequences is termed (in the historical literature of
physics and thermodynamics) an
\begin_inset Quotes eld
\end_inset
ensemble
\begin_inset Quotes erd
\end_inset
.
The entropy of a particular language model is a sum over the ensemble
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
S\left[p\right]=-\sum_{w_{1},w_{2},\cdots}p\left(w_{1},w_{2},\cdots\right)\log_{2}p\left(w_{1},w_{2},\cdots\right)
\]
\end_inset
The principle of maximum entropy states that the above should be solved
to find the probability distribution
\begin_inset Formula $p$
\end_inset
that maximizes the entropy
\begin_inset Formula $S\left[p\right]$
\end_inset
.
This can be solved without the need to provide any additional statements
or constraints.
Standard texts on statistical mechanics exhibit the solution; it is the
Boltzmann distribution, namely
\begin_inset Formula
\begin{equation}
p\left(w_{1},w_{2},\cdots\right)=\frac{1}{Z}\exp-E\left(w_{1},w_{2},\cdots\right)\label{eq:boltzmann}
\end{equation}
\end_inset
with the partition function
\begin_inset Formula $Z$
\end_inset
being given by
\begin_inset Formula
\[
Z=\sum_{w_{1},w_{2},\cdots}\exp-E\left(w_{1},w_{2},\cdots\right)
\]
\end_inset
To make ends meet with eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:Partition function"
\end_inset
, one writes
\begin_inset Formula $Z=Z\left[J=0\right]$
\end_inset
so that if the current
\begin_inset Formula $J$
\end_inset
is zero, one simply does not write it, as it is just a device handy for
algebraic manipulations, but having no particularly deep significance for
the language model.
\end_layout
\begin_layout Standard
Thus, a maximum entropy model of natural language is any model that provides
an energy function
\begin_inset Formula $E\left(w_{1},w_{2},\cdots\right)$
\end_inset
for a sequence of words
\begin_inset Formula $w_{1},w_{2},\cdots$
\end_inset
.
Clearly, CBOW/SkipGram is such a model.
There are others.
\end_layout
\begin_layout Subsection
Ising Models of Grammar
\end_layout
\begin_layout Standard
The vector product
\begin_inset Formula $\sum_{i\in I}\vec{u}_{w}\cdot\vec{v}_{i}$
\end_inset
appearing in the partition function
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:Partition function"
\end_inset
, and indirectly in the CBOW and SkipGram models
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
and
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
is pretty much the grand-total extent or content of these language models.
The statement is effectively that vectors provide a pretty good model of
natural language, and the vectors are able to capture important features
of natural language, including semantics and compositionality (such as
the
\begin_inset Quotes eld
\end_inset
King
\begin_inset Quotes erd
\end_inset
-
\begin_inset Quotes eld
\end_inset
man
\begin_inset Quotes erd
\end_inset
+
\begin_inset Quotes eld
\end_inset
woman
\begin_inset Quotes erd
\end_inset
=
\begin_inset Quotes eld
\end_inset
Queen
\begin_inset Quotes erd
\end_inset
example
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013a,Mikolov2013b"
literal "true"
\end_inset
).
This is an interesting effect, because the vectors themselves seem to be
some kind of effectively structureless black boxes; they capture some kind
of latent structure of language, but how this is captured is entirely opaque.
This is entirely at odds with traditional theories of syntax, as developed
by more than half a century of linguistics research.
How can the latent content of the feature vectors be reconciled with structural
theories of syntax?
\end_layout
\begin_layout Standard
The notion of the Ising model can be used to bridge this gap.
In the original formulation of the Ising model, the loss function (the
Hamiltonian; the energy) was written as
\begin_inset Formula
\[
E\left(\sigma\right)=\sum_{i}h_{i}\sigma_{i}+\sum_{i,j}J_{ij}\sigma_{i}\sigma_{j}
\]
\end_inset
with the
\begin_inset Formula $\sigma_{i}$
\end_inset
being the value of a
\begin_inset Quotes eld
\end_inset
spin
\begin_inset Quotes erd
\end_inset
at a
\begin_inset Quotes eld
\end_inset
lattice position
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $i$
\end_inset
, the
\begin_inset Formula $h_{i}$
\end_inset
being the
\begin_inset Quotes eld
\end_inset
magnetic field
\begin_inset Quotes erd
\end_inset
(at lattice position
\begin_inset Formula $i$
\end_inset
), and the
\begin_inset Formula $J_{ij}$
\end_inset
being the interaction energy between neighbors (typically, the nearest
neighbors, and typically dependent only on the distance
\begin_inset Formula $\left|i-j\right|$
\end_inset
between neighbors).
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The
\begin_inset Formula $J_{ij}$
\end_inset
used here has no relationship whatsoever to the current
\begin_inset Formula $J$
\end_inset
of the previous section; rather, there are not enough letters in the alphabet,
and by convention,
\begin_inset Formula $J$
\end_inset
is used for both tasks.
\end_layout
\end_inset
In the present context, the
\begin_inset Formula $\sigma_{i}$
\end_inset
are to be reinterpreted as
\begin_inset Formula $w_{i}$
\end_inset
, the word at position
\begin_inset Formula $i$
\end_inset
in a sentence.
\end_layout
\begin_layout Standard
The Ising model is usually taken to be
\begin_inset Quotes eld
\end_inset
translation invariant
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
shift invariant
\begin_inset Quotes erd
\end_inset
, dependent only on relative positions between points in the lattice, rather
than their absolute position.
For the one-dimensional Ising model, where the lattice points are in a
linear sequence, the shift invariance implies a number of interesting connectio
ns to Markov chains, shift sequences, and finite state machines.
This, in turn, implies that the Ising model, or a variant thereof, occurs
in many natural models.
One example is the distribution of sequences of amino acids in Zebrafish
antibodies.
\begin_inset CommandInset citation
LatexCommand cite
key "Mora2010"
literal "true"
\end_inset
In that model, each
\begin_inset Formula $\sigma_{i}$
\end_inset
can be one of twenty-one different amino acids, and one is interested in
describing the distribution of a wide variety of different sequences that
antibodies employ to fight off infection.
Another example is that of protein sequences, specifically, of sensor kinase
and response regulator proteins in bacteria
\begin_inset CommandInset citation
LatexCommand cite
key "Weigt2009"
literal "true"
\end_inset
, where the goal is to identify which sensor amino-acid sequences directly
trigger response proteins, as opposed to merely being correlated with a
response.
\end_layout
\begin_layout Standard
The point to be made here is that the Ising model also provides a natural
way to unify the syntactic structure of language with the syntax-free vector
models.
The reinterpretation is that lattice position
\begin_inset Formula $i$
\end_inset
corresponds to the
\begin_inset Formula $i$
\end_inset
'th word in a linear text.
The spin
\begin_inset Formula $\sigma_{i}$
\end_inset
is to be reinterpreted as the word instance
\begin_inset Formula $w_{i}$
\end_inset
located there.
The correct interpretation of the one-point function
\begin_inset Formula $h_{i}$
\end_inset
(the
\begin_inset Quotes eld
\end_inset
magnetic field
\begin_inset Quotes erd
\end_inset
) is explored in the next section; for now, it can be ignored (taken to
be zero).
The part of the model responsible for grammar are the two-point functions
\begin_inset Formula $J_{ij}$
\end_inset
, which need to be generalized into
\begin_inset Formula $n$
\end_inset
-point functions that capture the grammatical relationships between words.
Given a sequence of lattice values
\begin_inset Formula $\sigma_{i},\sigma_{i+1},\cdots$
\end_inset
(that is, a sequence of words
\begin_inset Formula $w_{i},w_{i+1},\cdots$
\end_inset
) one has an
\begin_inset Quotes eld
\end_inset
interaction energy
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $J_{w_{i},w_{i+1},\cdots}$
\end_inset
that is small when the sequence of words
\begin_inset Formula $w_{i},w_{i+1},\cdots$
\end_inset
is likely, and is large (or infinite) when the sequence of words is grammatical
ly incorrect.
In effect,
\begin_inset Formula
\[
J_{w_{i},w_{i+1},\cdots}=-\log p\left(w_{i},w_{i+1},\cdots\right)
\]
\end_inset
is the loss function.
This is just eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:boltzmann"
\end_inset
in slightly different form.
\end_layout
\begin_layout Standard
The statement that Ising model provides a model of natural language might
superficially appear to be content-free, an empty and trite statement (there's
a
\begin_inset Quotes eld
\end_inset
so what
\begin_inset Quotes erd
\end_inset
aspect to it:
\begin_inset Quotes eld
\end_inset
show me something I did not already know
\begin_inset Quotes erd
\end_inset
, as the Ising model just seems to be a standard maximum entropy model in
faint disguise.) What makes it not entirely trivial is the claim that the
interaction energies (loss functions) are additive.
That is, given a sequence of words
\begin_inset Formula $w_{i},w_{i+1},\cdots$
\end_inset
, the
\begin_inset Quotes eld
\end_inset
grammatical validity
\begin_inset Quotes erd
\end_inset
of that sequence can be described in terms of (statistically) independent,
single real-valued numbers
\begin_inset Formula $J_{w_{i},w_{i+1},\cdots}$
\end_inset
which are additive: they are to be summed (and not combined in some other,
more complex way).
\end_layout
\begin_layout Standard
The additive model of grammatical structure also exposes the limit of this
language model: we do not speak in a word-salad of grammatically valid
sentences; rather, there is always a message conveyed in an utterance.
The statistically independent numbers
\begin_inset Formula $J_{w_{i},w_{i+1},\cdots}$
\end_inset
are sufficient to capture the grammar and syntactic structure of the language,
but not (at this level) to capture the message itself.
The
\begin_inset Formula $n$
\end_inset
-point functions
\begin_inset Formula $J_{w_{i},w_{i+1},\cdots}$
\end_inset
are to be taken as the coding of the language, in the sense of
\begin_inset Quotes eld
\end_inset
coding theory
\begin_inset Quotes erd
\end_inset
of signal processing; they convert plaintext to cryptext.
The plaintext is a bag-of-concepts; the cryptext is the word-sequence that
encodes the plaintext.
\end_layout
\begin_layout Subsection
MST models of Language
\begin_inset CommandInset label
LatexCommand label
name "subsec:MST-parsing"
\end_inset
\end_layout
\begin_layout Standard
The importance of the additive aspect of the Ising model of natural language
is best illustrated by reverting to the simpler two-point model of natural
language, by restricting the interaction
\begin_inset Formula $J$
\end_inset
to occur only between pairs of words.
This effectively gives the Maximum Spanning Tree (MST) model of language,
explored by Yuret
\begin_inset CommandInset citation
LatexCommand cite
key "Yuret1998"
literal "true"
\end_inset
and by McDonald
\begin_inset CommandInset citation
LatexCommand cite
key "McDonald2005,McDonald2006"
literal "true"
\end_inset
.
Here, the relationship between words is presumed to be entirely pair-wise;
after somehow obtaining pair-wise word statistics
\begin_inset Formula $p\left(w_{left},w_{right}\right)$
\end_inset
, one constructs a maximum-spanning-tree parse so as to maximize the total
entropy.
\end_layout
\begin_layout Standard
The use of a maximum spanning tree, such as the supervised training models
of McDonald
\emph on
etal
\emph default
., is a key insight.
McDonald states this in terms of a score
\begin_inset Formula $s(x,y)$
\end_inset
that the sentence
\begin_inset Formula $x$
\end_inset
is described by parse tree
\begin_inset Formula $y$
\end_inset
.
The score is taken to be additive over word pairs:
\begin_inset Formula
\[
s\left(x,y\right)=\sum_{\left(i,j\right)\in y}s\left(i,j\right)
\]
\end_inset
so that the sum ranges over all words-pairs
\begin_inset Formula $\left(i,j\right)$
\end_inset
occurring in the parse-tree
\begin_inset Formula $y$
\end_inset
(and the individual words
\begin_inset Formula $i,j$
\end_inset
being the words of sentence
\begin_inset Formula $x$
\end_inset
).
How does one obtain the score
\begin_inset Formula $s\left(i,j\right)$
\end_inset
? McDonald
\emph on
etal.
\emph default
propose a supervised training algorithm, where the score is induced by
means of a gradient descent from an
\emph on
a priori
\emph default
training corpus of parse trees.
\end_layout
\begin_layout Standard
It is here that Yuret does one better: he proposes that the score be given
by the mutual information (MI) between word-pairs; that is (aligning the
different notation)
\begin_inset Formula
\begin{equation}
s\left(i,j\right)=MI\left(w_{i},w_{j}\right)=\log_{2}\frac{p\left(w_{i},w_{j}\right)}{p\left(w_{i},*\right)p\left(*,w_{j}\right)}\label{eq:word-pair-MI}
\end{equation}
\end_inset
How does this square with the Ising model? Superficially, it seems to be
quite different: the Ising model suggests that one should have only pair-wise
interactions
\begin_inset Formula $J_{ij}=\log p\left(w_{i},w_{j}\right)$
\end_inset
whereas the mutual information has an additional funny denominator.
This can be reconciled by saying that there is a bulk interaction: each
individual word-site
\begin_inset Formula $i$
\end_inset
also interacts with the
\begin_inset Quotes eld
\end_inset
bulk
\begin_inset Quotes erd
\end_inset
of all possible other words that could ever occur in some other speakable,
grammatically correct sentence.
\end_layout
\begin_layout Standard
Put differently, there are two bulk
\begin_inset Quotes eld
\end_inset
magnetic fields
\begin_inset Quotes erd
\end_inset
, or one-point interactions
\begin_inset Formula $h\left(w_{i},*\right)=-\log_{2}p\left(w_{i},*\right)$
\end_inset
and
\begin_inset Formula $h\left(*,w_{j}\right)=-\log_{2}p\left(*,w_{j}\right)$
\end_inset
that enter into the Ising model Hamiltonian, so that, for sentence
\begin_inset Formula $x$
\end_inset
and parse tree
\begin_inset Formula $y$
\end_inset
, one has a
\begin_inset Quotes eld
\end_inset
score
\begin_inset Quotes erd
\end_inset
(following McDonald) or
\begin_inset Quotes eld
\end_inset
energy
\begin_inset Quotes erd
\end_inset
(following statistical physics) of
\begin_inset Formula
\begin{eqnarray*}
s\left(x,y\right) & = & \sum_{i\in x}h_{i}+\sum_{\left(i,j\right)\in y}s\left(i,j\right)\\
& = & \sum_{i\in x}\left[h\left(w_{i},*\right)+h\left(*,w_{i}\right)\right]+\sum_{\left(i,j\right)\in y}\log_{2}p\left(w_{i},w_{j}\right)
\end{eqnarray*}
\end_inset
When Yuret chooses to look for the spanning tree that maximizes the sum
of the mutual information between word-pairs, what he is actually doing
is looking for the parse tree that maximizes the entropy within the background
context (the
\begin_inset Quotes eld
\end_inset
bulk magnetic field
\begin_inset Quotes erd
\end_inset
) of the language model.
This is an absolutely key, fundamental insight of the Ising model of language:
the relationship between words matters not so much because of the individual
relationships, but because these relationships have to be taken with regards
to the background of the entire language, in full.
\end_layout
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status collapsed
\begin_layout Plain Layout
\align center
\begin_inset Caption Standard
\begin_layout Plain Layout
Feynman Diagrams in Language
\begin_inset CommandInset label
LatexCommand label
name "fig:Feynman-Diagrams"
\end_inset
\end_layout
\end_inset
\begin_inset Graphics
filename skimage/feynman.eps
width 45col%
\end_inset
\end_layout
\begin_layout Plain Layout
This figure illustrates the energy functional for a particular English language
sentence, chosen out of the statistical ensemble of all possible English
language sentences.
The arcs above the sentence show the standard unlabeled dependency parse
of the sentence.
It is conventional to consider such a parse as standing alone, implicitly
with some language model that is not diagrammatically represented.
When drawn stand-alone, the arcs are presumed to have some unspecified
cost, such that the desired parse tree is preferentially selected.
Here, the arcs are intended to very explicitly correspond to
\begin_inset Quotes eld
\end_inset
propagators
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
Feynman rules
\begin_inset Quotes erd
\end_inset
with a value of
\begin_inset Formula $h=\log_{2}p\left(w_{i},w_{j}\right)$
\end_inset
.
The two vacuum bubbles below the sentence, and the straight lines connecting
each word to each vacuum are used to explicitly represent the language
model.
The straight lines connecting to the left vacuum are explicitly given by
the propagator
\begin_inset Formula $h=-\log_{2}p\left(*,w\right)$
\end_inset
while those going to right vacuum are given by
\begin_inset Formula $h=-\log_{2}p\left(w,*\right)$
\end_inset
.
The total action (Hamiltonian, in this case) is given by
\begin_inset Formula $H_{total}=\sum_{arcs}h$
\end_inset
with the sum being over all lines and arcs (with appropriate multiplicity).
This summation makes explicit what is otherwise an implicit language model:
namely, that
\begin_inset Formula
\[
H_{total}=\sum_{arcs}h=\sum_{\left(w_{i},w_{j}\right)\in tree}MI\left(w_{i},w_{j}\right)
\]
\end_inset
where the right-hand side is the sum over mutual information between word-pairs.
That is, the total mutual information in a parse tree is exactly equivalent
to the total entropy of that parse tree, taken within the context of the
entire language model.
\end_layout
\begin_layout Plain Layout
\begin_inset space \qquad{}
\end_inset
The use of the name of Feynman in this context is not meant to be some vague,
hand-waving abuse of terminology, peacock feathering on the part of the
author.
The rules given here are
\emph on
bona fide
\emph default
Feynman rules, in the strict, straight and narrow sense.
They are a set of rules used to give explicit numerical values to a hand-drawn
diagram, making express that the diagram is the same thing as a specific
equation.
Here, by applying the rules, one can see that the diagram is an explicit
representation of the equation that states that
\begin_inset Formula $H_{total}$
\end_inset
is the total energy, given as the sum over all arcs in the diagram.
\end_layout
\begin_layout Plain Layout
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"
\end_inset
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Feynman-Diagrams"
\end_inset
attempts to drive this point home, by explicitly showing the vacuum contributio
n (the
\begin_inset Quotes eld
\end_inset
bulk magnetic field
\begin_inset Quotes erd
\end_inset
contribution) of the language model.
By convention, when linguists draw dependency-parse diagrams, they omit
the bottom half of this figure.
This is a reasonable omission: it not only clutters the diagram, but, from
the point of view of linguistics, it almost seems like tautological nonsense.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The word
\begin_inset Quotes eld
\end_inset
vacuum
\begin_inset Quotes erd
\end_inset
comes from quantum field theory, where there was a similar realization
that the tautologically-empty vacuum is not so empty after all, but has
explicit contributions to the probabilities of various physical processes.
The vacuum is an implicit context for physical processes, which on occasion
must be made explicit in order to get correct predictions.
\end_layout
\end_inset
Of course a language model is taken within the context of the language.
However, in order to bridge from a purely linguistic model, to a statistical
model based on probabilities taken from first principles from Boltzmann
distributions derived from partition functions, those implicit terms must
be made explicit.
The single-point propagators have an explicit numerical effect in the determina
tion of the best parse tree for a given sentence.
\end_layout
\begin_layout Subsection
Vacuum Contributions and Exact Solutions
\end_layout
\begin_layout Standard
Pair-wise mutual information is not the same thing as the two-point function
\begin_inset Formula $J_{ij}$
\end_inset
; the MI includes one-point terms in it.
For many applications, including chemistry, the one-point vacuum contributions
to the MI are clearly inappropriate.
Atoms, amino acids and proteins don't respond to other atoms that
\begin_inset Quotes eld
\end_inset
might have been there, but weren't
\begin_inset Quotes erd
\end_inset
.
For those applications, MI can only provide a rough approximation for a
starting point for a more accurate solution of the
\begin_inset Quotes eld
\end_inset
true
\begin_inset Quotes erd
\end_inset
Ising model, one which contains a two-point function, but no one-point
functions.
That is, MI is not a substitute for accurately solving the Ising model,
when a solution of the Ising model is actually needed.
\end_layout
\begin_layout Standard
For example, for protein folding and protein mating, the solution to the
Ising model obtained by message passing becomes a very accurate predictor
of the three-dimensional physical structure of the protein, and indicates
which amino acids actually become physically close to one-another.
It is considerably more accurate than the MI-based estimate.
\begin_inset CommandInset citation
LatexCommand cite
key "Weigt2009"
literal "true"
\end_inset
There are several different algorithms for solving the Ising model, including
Monte Carlo and message passing algorithms.
\begin_inset CommandInset citation
LatexCommand cite
key "Mezard2008,Weigt2009"
literal "true"
\end_inset
\end_layout
\begin_layout Subsection
\begin_inset Formula $n$
\end_inset
-point Functions and Word-Sense Disambiguation
\end_layout
\begin_layout Standard
The preceding two sections potentially sow a point of confusion: Should
one consider a
\begin_inset Quotes eld
\end_inset
pure
\begin_inset Quotes erd
\end_inset
Ising model of natural language, one which omits the one-point contributions?
Would it be more accurate than an MST-parse? Maybe.
And maybe not.
The author is not aware of any pure-Ising models of natural language that
could be compared to the results of MST parsing.
\end_layout
\begin_layout Standard
For natural language, most words have valencies of 3, 4 or 5, and so it
seems that they would be better described by 3-point, 4-point or 5-point
Ising interaction energies, as opposed to a bag of 2-point interactions.
How true is this? Consider a transitive verb: it has a subject and an object.
If the subject and object are truly independent of one-another, then two
pair-wise interactions would be enough: a noun-verb link for the subject,
and a verb-noun link for the object.
Are subjects and objects independent of one-another? Consider the verb
\begin_inset Quotes eld
\end_inset
throw
\begin_inset Quotes erd
\end_inset
, and a sentence of the form
\begin_inset Quotes eld
\end_inset
subject throws object
\begin_inset Quotes erd
\end_inset
.
In this case,
\begin_inset Quotes eld
\end_inset
subject
\begin_inset Quotes erd
\end_inset
can only be chosen from the class of animate beings, capable of throwing
things.
The object must be chosen from the class of physical objects that can be
thrown.
Although these two classes are fairly narrow, they still seem uncorrelated.
This illusion can be broken: further restricting the class of subjects
to humans forces the restriction of objects to the class of physical items
weighing between a few grams and ten kilograms.
But there is only one word
\begin_inset Quotes eld
\end_inset
throw
\begin_inset Quotes erd
\end_inset
, and not some hypothetical
\begin_inset Formula $\mbox{throw}_{1}$
\end_inset
and
\begin_inset Formula $\mbox{throw}_{2}$
\end_inset
and
\begin_inset Formula $\mbox{throw}_{3}$
\end_inset
, where
\begin_inset Formula $\mbox{throw}_{2}$
\end_inset
is used only with human subjects.
The verb subjects and objects are correlated; when this is the case, a
pair of two-point functions is not enough; these require a three-point
function for an accurate description.
\end_layout
\begin_layout Standard
Perhaps, after word-sense disambiguation, one can discover multiple word
senses, so that, for example,
\begin_inset Formula $\mbox{throw}_{1}$
\end_inset
applies to metal machines that throw heavy objects,
\begin_inset Formula $\mbox{throw}_{2}$
\end_inset
pertains to human subjects, and
\begin_inset Formula $\mbox{throw}_{3}$
\end_inset
applies to horses.
In this case, the three-point function might indeed factorize.
Written as an algebraic expression, one might be able to observe the factorizat
ion
\begin_inset Formula
\begin{align*}
p\left(w_{subj},\mbox{throw},w_{obj}\right)= & p\left(w_{machine},\mbox{throw}_{1}\right)p\left(\mbox{throw}_{1},w_{heavy}\right)\\
+ & p\left(w_{human},\mbox{throw}_{2}\right)p\left(\mbox{throw}_{2},w_{graspable}\right)\\
+ & p\left(w_{horse},\mbox{throw}_{3}\right)p\left(\mbox{throw}_{3},w_{rider}\right)
\end{align*}
\end_inset
so that any kind of machine can
\begin_inset Formula $\mbox{throw}_{1}$
\end_inset
any kind of heavy object, in a statistically uncorrelated sense, whereas
any human can
\begin_inset Formula $\mbox{throw}_{2}$
\end_inset
any object that can be grasped by hand, with there being no statistical
correlation between the human subject and the human-thrown object.
The third factorization is likewise: only horses or other mountable creatures
can
\begin_inset Formula $\mbox{throw}_{3}$
\end_inset
their riders, but there is no statistical correlation (no three-point function)
between the thrower, and the rider.
\end_layout
\begin_layout Standard
This kind of factorization into components might even provide a plausible
automated means of performing word-sense disambiguation, given only the
undifferentiated, measured 3-point frequency
\begin_inset Formula $p\left(w_{subj},\mbox{throw},w_{obj}\right)$
\end_inset
.
Exactly how far this can be pushed, without grinding into the floor of
statistically noisy data is unclear: only horses throw cowboys, and only
elephants throw maharajahs.
\end_layout
\begin_layout Subsection
Disjunct Models of Language
\end_layout
\begin_layout Standard
Although Yuret's thesis clearly demonstrates that pair-wise word interactions
give a reasonable model of natural language, it also demonstrates that
the model is imperfect.
Link Grammar
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991,Sleator1993"
literal "true"
\end_inset
provides a much better model of language, and it is anchored on top of
half a century of tradition in linguistics research into structure.
To place it within the current context, the key leap being taken is to
replace the pair-wise word-interactions
\begin_inset Formula $J_{ij}=-\log p\left(w_{i},w_{j}\right)$
\end_inset
by disjuncts
\begin_inset Formula
\[
J_{ijk\cdots}=-\log p\left(w_{i};w_{left\,connected};w_{right\,connected}\right)
\]
\end_inset
The notation above is awkward: the idea here is that some word
\begin_inset Formula $w_{i}$
\end_inset
can connect to other words on the left, by means of left-pointing connectors
(or links) and it can connect to words on the right, with right-pointing
connectors.
These are distinct sets, or sequences, since the word-order matters.
\end_layout
\begin_layout Standard
There are multiple ways of overcoming the notational awkwardness of the
above; these are reviewed in a later section.
In particular, the notation above differs sharply from that used in Link
Grammar; this is a notational issue, and not a conceptual issue.
\end_layout
\begin_layout Standard
Before proceeding, the remark of
\begin_inset Quotes eld
\end_inset
resting on a tradition of linguistics
\begin_inset Quotes erd
\end_inset
should be clarified.
Link Grammar proposes a dependency-grammar model of language.
Other popular models of language include constituency-tree grammars, such
as Head-Phrase Structure Grammar (HPSG).
Grammars such as Categorial Grammar (CG) combine aspects of constituency
with aspects of dependency.
There are others.
In principle, each of these different grammar frameworks are convertible
to one-another by fixed algorithms that terminate in finite time.
That is, given a lexis in one grammar framework, there is a purely mechanical
means of translating that lexis into the lexis required by a different
theoretical framework.
This perhaps over-simplifies the situation: different theories of grammar
are often founded on subtle distinctions; for example Dick Hudson's Word
Grammar
\begin_inset CommandInset citation
LatexCommand cite
key "Hud84,Hud07"
literal "true"
\end_inset
replaces the no-links-crossing constraint of dependency grammars by a notion
of landmark transitivity.
We sweep such details under the rug, for now, wishing to rest on the broader
statement that all grammar frameworks can be converted into one-another,
while acknowledging that some frameworks give better insight into certain
aspects of language than others.
\end_layout
\begin_layout Standard
The primary point here is that Link Grammar is interesting because it provides
a bridge to both traditional, symbolic structural linguistics (per above)
and while also allowing an interpretation as an Ising model of language.
Following Yuret's Ansatz, one includes energy terms of not only
\begin_inset Formula $J_{ijk\cdots}$
\end_inset
in the Hamiltonian, but also bulk terms, indicating how disjuncts interact
in the background.
In practice, what this means is that one should associate to each word-disjunct
pair a mutual information
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
MI\left(w,d\right)=\log_{2}\frac{p\left(w,d\right)}{p\left(w,*\right)p\left(*,d\right)}
\]
\end_inset
with
\begin_inset Formula $p\left(w,d\right)$
\end_inset
being the joint probability of observing disjunct
\begin_inset Formula $d$
\end_inset
on word
\begin_inset Formula $w$
\end_inset
.
The most likely parse of a sentence is one where the sum over mutual informatio
n is maximized.
\end_layout
\begin_layout Standard
The term
\begin_inset Formula $p\left(w,*\right)$
\end_inset
looks uneventful, but hides a more complex structure.
One has
\begin_inset Formula
\begin{eqnarray*}
p\left(w,*\right) & = & \sum_{d}p\left(w,d\right)\\
& = & \sum_{c}p\left(w;c\right)+\sum_{c_{1},c_{2}}p\left(w;c_{1},c_{2}\right)+\sum_{c_{1},c_{2},c_{3}}p\left(w;c_{1},c_{2},c_{3}\right)+\cdots
\end{eqnarray*}
\end_inset
where the sums over
\begin_inset Formula $c_{k}$
\end_inset
are sums over all connectors appearing in some disjunct.
Keep in mind that each connector can connect to the left or to the right:
a connector is a word, plus a direction indicator.
To bridge the notation back to that of the Ising model, one would write
for the loss function
\begin_inset Formula
\[
J_{ijk\cdots}=-\log_{2}p\left(w,d\right)=-\log_{2}p\left(w;\left(w_{i},x_{i}\right),\left(w_{j},x_{j}\right),\left(w_{k},x_{k}\right),\cdots\right)
\]
\end_inset
where
\begin_inset Formula $c_{k}=\left(w_{k},x_{k}\right)$
\end_inset
is a connector with word
\begin_inset Formula $w_{k}$
\end_inset
and direction
\begin_inset Formula $x_{k}$
\end_inset
.
Clearly, writing
\begin_inset Formula $d$
\end_inset
for a disjunct is much simpler than writing out the mass of connectors;
yet the notation can be deceiving because it hides the complexity of the
model.
\end_layout
\begin_layout Section
Graph Algorithms vs.
Gradient Descent
\end_layout
\begin_layout Standard
The previous sections illustrate that the CBOW/SkipGram model is a form
of a maximum-entropy model, and that the disjunct model of natural language
is a natural variant.
In one case, the word-context is an N-gram; in the other, it is a disjunct;
but these are not so unlike one-another, they have much in common.
Both language models are faced with a common task: finding an energy functional
that correctly models the observed probability distribution.
\end_layout
\begin_layout Standard
There are several generic classes of algorithms that can be applied to obtain
the energy functional.
One class comprises Monte Carlo methods, driving either hill-climbing,
gradient descent or
\begin_inset Quotes eld
\end_inset
relaxation
\begin_inset Quotes erd
\end_inset
algorithms; deep learning algorithms fall in this class.
The other class of algorithms can be loosely called
\begin_inset Quotes eld
\end_inset
graph algorithms
\begin_inset Quotes erd
\end_inset
; these attempt to infer generic network relationships, as opposed to the
dense, highly-symmetric bipartite graph typical of neural networks.
A characteristic approach, elaborated here, is to accumulate frequency
counts on low-arity observed relationships, and use the logarithm of these
frequencies as a surrogate for the energy functional.
The low-arity (low connectivity) of a node in a network graph makes such
graphs feel more
\begin_inset Quotes eld
\end_inset
sparse
\begin_inset Quotes erd
\end_inset
, as as compared to the high arity (high connectivity) in a neural-net,
where a node in one layer is connected to
\emph on
every
\emph default
node in another.
\end_layout
\begin_layout Standard
Besides connectivity, there are other differences: the class of Monte Carlo
methods can be said to be
\begin_inset Quotes eld
\end_inset
global
\begin_inset Quotes erd
\end_inset
, in that they are trying to navigate an extremely large energy functional
landscape through random sampling.
By contrast, the graph algorithms are manifestly local, and re-assemble
the global landscape explicitly by summing together contributions from
different Feynman diagrams, including vacuum contributions, as illustrated
in figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Feynman-Diagrams"
\end_inset
.
The graphical algorithms expose the graph network structure immediately;
in the above examples, as maximum spanning trees that can be found using
greedy algorithms applied to pair-wise relationships.
The Monte Carlo algorithms do not provide any manifest graphical structure,
although perhaps a graph structure could be discerned
\emph on
post facto
\emph default
, by applying some sort of thresholding to eliminate weak links.
Indeed, thresholding, using sigmoid functions to prune unwanted, weak weights
from a neural net is a characteristic of most deep-learning models.
Even so, the resulting weight vectors and weight matrices tend to be cryptic
amorphous masses: large blocks of uninterpretable numbers whose precise
role and importance seems impossible to discern.
\end_layout
\begin_layout Standard
This section attempts to better characterize the general idea of a
\begin_inset Quotes eld
\end_inset
graph algorithm
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Subsection
Graph Algorithms vs.
Monte Carlo for Word Pairs
\end_layout
\begin_layout Standard
The difference between graphical and Monte Carlo methods is perhaps best
illustrated by example.
Yuret (implicitly) assumes an Ising model of natural language, and considers
only pair-wise word relationships.
To obtain an energy functional, it suffices to count the frequency
\begin_inset Formula $N\left(w_{left},w_{right}\right)$
\end_inset
of word-pairs, and then to take for granted that the energy functional
is accurately estimated by
\begin_inset Formula
\[
E\left(w_{left},w_{right}\right)=-\log_{2}\left[\frac{N\left(w_{left},w_{right}\right)}{N\left(*,*\right)}\right]
\]
\end_inset
To obtain dependency parses that agree with those deemed acceptable by professio
nal linguists, maximum spanning trees are constructed, taking into account
the important role of the left and right marginal frequencies
\begin_inset Formula $N\left(*,w\right)$
\end_inset
and
\begin_inset Formula $N\left(w,*\right)$
\end_inset
.
The result is an explicit dependency graph for every possible sentence.
That the ensemble is an explicit Boltzmann distribution is a primary point
of figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Feynman-Diagrams"
\end_inset
.
\end_layout
\begin_layout Standard
One could have approached this problem from the Monte Carlo direction as
well, as is done by McDonald
\begin_inset CommandInset citation
LatexCommand cite
key "McDonald2005,McDonald2006"
literal "true"
\end_inset
: one trains up a model by defining a cost function, and then performs hill
climbing or gradient descent on it.
The result is still a pair-wise cost function, and a dependency parse is
obtained by searching for an MST tree, just as before.
For McDonald, there is no overt relationship to the principle of maximum
entropy; it is either covert, or perhaps one could say its
\begin_inset Quotes eld
\end_inset
more general
\begin_inset Quotes erd
\end_inset
by not constraining to fit the cost function to a probabilistic framework.
The need for this generality does not seem to be well-supported.
There does not appear to be any data to indicate if some other pair-wise
cost function provides a superior MST-tree, as compared to using the MI.
Although this is an open question, there's no particular hint that this
could be a fruitful direction to take.
\end_layout
\begin_layout Subsection
Graph Algorithms vs.
Gradient Descent for N-grams
\end_layout
\begin_layout Standard
Another strong comparison of the difference between graph algorithm and
gradient descent approaches is manifest at the disjunct/N-gram level.
The goal in both cases is to obtain a Bayesian-network factorization of
language, as in eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:bayes-factorize"
\end_inset
, and then to describe each of the factors as compactly as possible.
In both cases, some
\emph on
a priori
\emph default
model of language is proposed, and a search is performed to obtain the
factors in compact form.
\end_layout
\begin_layout Standard
The Monte Carlo approach presumes that the
\emph on
a priori
\emph default
model consists of a high-dimensional space of hidden parameters, and that
the space must be searched to find those parameters that best reproduce
the observed probabilities.
For example, eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
or eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
can be taken as the model of language; the vectors
\begin_inset Formula $\vec{u}_{t}$
\end_inset
and
\begin_inset Formula $\vec{v}_{i}$
\end_inset
are the hidden, unknown parameters, and hill-climbing (as an example of
a Monte Carlo method) is used to find them, with the goal of accurately
reproducing the observed probability
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
of word
\begin_inset Formula $w$
\end_inset
surrounded by the N-gram context
\begin_inset Formula $w_{I}$
\end_inset
.
This is a reasonable approach to modeling language; the primary critique
here is that the CBOW/SkipGram models are not graphical, at least, not
in the sense of providing an explicit symbolic, syntactic representation
of language.
\end_layout
\begin_layout Standard
The can be contrasted with the OpenCog language learning project
\begin_inset CommandInset citation
LatexCommand cite
key "Goertzel2014"
literal "true"
\end_inset
, which is overtly graphical at each step, and does produce a symbolic,
syntactic representation of language at its conclusion.
The procedure replaces the directly observed probability
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
with the hidden, indirectly observed probability
\begin_inset Formula $p\left(w,d\right)$
\end_inset
of a disjunct
\begin_inset Formula $d$
\end_inset
occurring on word
\begin_inset Formula $w$
\end_inset
.
The previous sections have already extensively argued that the probability
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is very much like the probability
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
, except that
\begin_inset Formula $p\left(w,d\right)$
\end_inset
can be explicitly understood as syntax, while
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
cannot.
That is, the
\begin_inset Formula $p\left(w,d\right)$
\end_inset
, with no further modification, redefinition or processing, can be used
with a parser to obtain a syntactic parse.
The probabilities
\begin_inset Formula $p\left(w,d\right)$
\end_inset
are the
\emph on
de facto
\emph default
lexical entries in the Link grammar parser
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991,Sleator1993"
literal "true"
\end_inset
.
The existing parser implementation can use the probabilities
\begin_inset Formula $p\left(w,d\right)$
\end_inset
directly, to obtain a syntactic parse.
\end_layout
\begin_layout Standard
How are the
\begin_inset Formula $p\left(w,d\right)$
\end_inset
obtained? One way is through direct counting.
Given an observational count
\begin_inset Formula $N\left(w,d\right)$
\end_inset
of how often the word
\begin_inset Formula $w$
\end_inset
is associated with the disjunct
\begin_inset Formula $d$
\end_inset
, one computes a normalized frequency of observations:
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
p\left(w,d\right)=\frac{N\left(w,d\right)}{N\left(*,*\right)}
\]
\end_inset
so that the frequency is properly normalized:
\begin_inset Formula $p\left(*,*\right)=1$
\end_inset
.
The energy functional is explicitly
\begin_inset Formula
\[
E\left(w,d\right)=-\log_{2}p\left(w,d\right)
\]
\end_inset
No parameter fitting is required to obtain this.
\end_layout
\begin_layout Standard
However, the
\begin_inset Formula $N\left(w,d\right)$
\end_inset
need to be obtained somehow.
A number of ways of doing this are possible.
Some of these are sketched in the immediately following subsection.
There is also another, distinct problem: even with
\begin_inset Formula $p\left(w,d\right)$
\end_inset
in hand, it is potentially a very large matrix.
It's been argued that
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is a lot like
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
, and so that if the latter can be reduced to a much smaller model, then
so can the former.
In fact, the same set of algorithms can be applied to simplify either of
them; and specifically, CBOW/SkipGram can be applied to
\begin_inset Formula $p\left(w,d\right)$
\end_inset
just as readily as
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
.
Conversely, a completely different set of algorithms, suitable for
\begin_inset Formula $p\left(w,d\right)$
\end_inset
, might be portable to
\begin_inset Formula $p\left(w,w_{I}\right)$
\end_inset
.
Except for the next section, the remainder of this paper is dedicated to
the task of finding adequate algorithms for smaller, factored representations
of
\begin_inset Formula $p\left(w,d\right)$
\end_inset
.
\end_layout
\begin_layout Subsection
Obtaining Disjunct Counts
\end_layout
\begin_layout Standard
How should one obtain the counts
\begin_inset Formula $N\left(w,d\right)$
\end_inset
of word-disjunct pairs? Unlike the N-gram counts, there is a direct assumption
that
\begin_inset Formula $d$
\end_inset
encodes syntactic information.
That is, it should be possible to use
\begin_inset Formula $N\left(w,d\right)$
\end_inset
to obtain partly or mostly-accurate parses.
\end_layout
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\begin_inset Caption Standard
\begin_layout Plain Layout
Disjuncts from Dependency Parses
\begin_inset CommandInset label
LatexCommand label
name "fig:Disjuncts-from-Dependency"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Plain Layout
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Plain Layout
\align center
\begin_inset Graphics
filename skimage/disjunct.eps
width 60col%
\end_inset
\end_layout
\begin_layout Plain Layout
The upper diagram represents an unlabeled dependency parse, such as might
be obtained from MST parsing.
The lower-left diagram shows two links being cut; the lower-right diagram
shows one of the resulting disjuncts.
In Link Grammar notation, it would be written
\begin_inset listings
lstparams "basicstyle={\ttfamily}"
inline false
status open
\begin_layout Plain Layout
ball: the- & threw-;
\end_layout
\end_inset
indicating both the connectors, and the order in which they must be satisfied.
\end_layout
\begin_layout Plain Layout
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Disjuncts-from-Dependency"
\end_inset
shows one possible way of obtaining a disjunct: obtain an unlabeled dependency
parse, in some way, and then cut each link to obtain connector pairs.
The resulting words, with the attached connectors are then
\begin_inset Formula $\left(w,d\right)$
\end_inset
pairs, which can be counted to obtain
\begin_inset Formula $N\left(w,d\right)$
\end_inset
.
This may seem to put the cart before the horse, but for two reasons: the
dependency parse does not have to be labeled, and, most importantly, it
doesn't have to have a high accuracy.
It needs only to have a accuracy that is better than random chance.
The law of large numbers should allow correct disjunct to accumulate large
counts, while the rest wash out into background noise.
\end_layout
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\begin_inset Caption Standard
\begin_layout Plain Layout
Dependency Clique
\begin_inset CommandInset label
LatexCommand label
name "fig:Dependency-Clique"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Plain Layout
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Plain Layout
\align center
\begin_inset Graphics
filename skimage/clique.eps
width 35col%
\end_inset
\end_layout
\begin_layout Plain Layout
A dependency clique.
All words are joined by edges to all other words.
\end_layout
\begin_layout Plain Layout
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
One way to obtain a fairly accurate unlabeled dependency parse is by performing
MST parsing (Maximum Spanning Tree parsing), and is described in
\begin_inset CommandInset citation
LatexCommand cite
key "Yuret1998"
literal "true"
\end_inset
.
It is a form of a greedy graph algorithm.
One begins by considering the graph clique (shown in figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Dependency-Clique"
\end_inset
), wherein every word in the sentence is related (joined by an edge) to
every other word in a sentence.
Each edge is associated with a numerical weight.
In canonical MST, this weight is the mutual information of the word-pair.
Other weights are possible.
For example, de Souza
\emph on
etal
\emph default
.
\begin_inset CommandInset citation
LatexCommand cite
key "deSousa2015"
literal "true"
\end_inset
suggest an additional entropy factor, based on the vertex degree in the
final chosen dependency graph.
Other factors are possible.
For example, natural language tends to be close to the theoretical minimum
possible dependency distance,
\begin_inset CommandInset citation
LatexCommand cite
key "Temper2008,Temper2007,Ferrer2006"
literal "true"
\end_inset
suggesting that weighting should incorporate dependency distance as a factor.
Other factors are possible, including
\begin_inset Quotes eld
\end_inset
hubbiness
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "Ferrer2013"
literal "true"
\end_inset
(although this might be equivalent to a weight based on entropy from vertex
degree).
\end_layout
\begin_layout Standard
Given a dependency clique, one wishes to select a subset of the edges, so
as to call that subset the
\begin_inset Quotes eld
\end_inset
unlabeled dependency graph
\begin_inset Quotes erd
\end_inset
.
Several choices are possible:
\end_layout
\begin_layout Itemize
Apply a greedy algorithm, and keep only the edges of the highest quality,
until a spanning tree is found, spanning all words in the sentence.
\end_layout
\begin_layout Itemize
Apply a greedy algorithm with additional weighting factors, such as entropy
obtained from vertex degree (de Souza
\emph on
etal
\emph default
.)
\end_layout
\begin_layout Itemize
Apply thresholding, and discard all edges that have a weak, low quality
connection.
The result of thresholding may be a disconnected graph, or a multiply-connected
graph.
The threshold may depend on the graph.
\end_layout
\begin_layout Itemize
A combination of techniques, allowing both disconnected regions, and cycles.
\end_layout
\begin_layout Standard
There does not appear to be any published comprehensive comparison of these
or other techniques.
\end_layout
\begin_layout Standard
A few remarks are in order, concerning disconnected trees and dependency
graphs with cycles in them.
In traditional theories of grammar, grammatical relations are always trees,
and every word appears in the tree.
There are several reasons for this: standard formulations of phrase structure
grammars are always presented in terms of production rules; production
rules necessarily generate directed, acyclic trees.
Most dependency grammars also insist on dependencies described by trees,
and usually, with an additional planarity constraint (projectivity or no-edges-
crossing constraint).
Since every word in a sentence is presumed to have some important role,
grammars always connect all words, in some way.
\end_layout
\begin_layout Standard
Practical experience suggests that this outlook is perhaps too strict.
Non-planar dependency graphs have been observed in many languages,
\begin_inset CommandInset citation
LatexCommand cite
key "Havelka2007"
literal "true"
\end_inset
although this is (objectively) rare.
\begin_inset CommandInset citation
LatexCommand cite
key "Ferrer2017"
literal "true"
\end_inset
(That is, although long sentences tend to have more crossings, the fraction
drops sharply in proportion to the number they could have had.) When there
are crossings, they are
\begin_inset Quotes eld
\end_inset
well nested
\begin_inset Quotes erd
\end_inset
: a link is crossed only once, almost never more than once.
\begin_inset CommandInset citation
LatexCommand cite
key "Havelka2007"
literal "true"
\end_inset
Dick Hudson has proposed the concept of
\begin_inset Quotes eld
\end_inset
landmark transitivity
\begin_inset Quotes erd
\end_inset
as a way of describing the link-crossing phenomenon.
\begin_inset CommandInset citation
LatexCommand cite
key "Hud84,Hud07"
literal "true"
\end_inset
Full connectivity is not always meaningful: writing is filled with typographica
l and grammatical errors that defy strict grammatical analysis; for example,
if a word is accidentally repeated twice, this has no particular significance.
Spoken language is almost always less syntactically coherent than written
language.
Direct experience with Link Grammar shows that cycles in graphs are very
useful for enforcing additional grammatical constraints, and disambiguating
competing parses.
That is, there may be two equally-plausible competing dependency-tree parses;
the ability to add an arc to form a loop can often be critical to establish
the correctness of a parse.
Examples include cycles formed in relative clauses, with one link to the
subject of the relative clause, another link to the head-verb of the relative
clause, and, completing the cycle, a link between the subject and verb
of the relative clause.
Only when all three links can be clearly identified, can one be confident
that the parse is correct.
\end_layout
\begin_layout Standard
Neither the acyclic condition, nor the connectivity condition need to be
satisfied, when the goal is to obtain statistical counts of disjuncts.
The reasons for this should be clear: the frequency count of spurious,
incorrect disjuncts will remain low, disappearing in the noise.
Ungrammatical sentences in the input corpus require no special treatment.
Cycles in dependency graphs are important for providing constraints.
Not all dependencies are planar or projective.
Thus, the mechanism for generating disjuncts, so that they can be statistically
counted, need not be subjected to any particularly strong theory of grammar.
A weak, frequently-correct unlabeled dependency graph should be enough.
Weaker systems might take longer to converge, but should also perhaps introduce
less
\emph on
a priori
\emph default
bias.
\end_layout
\begin_layout Subsection
Summary
\end_layout
\begin_layout Standard
By observing disjuncts, one is observing an explicit graphical structure.
The disjunct is overt, in the foreground, explicitly demonstrated.
It is obtained by explicitly searching for a graphical structure.
Dependency structures are a form of explicit thresholding: of all of the
possible edges in a clique (figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Dependency-Clique"
\end_inset
) only some are selected; the weights of all other edges are expressly zero.
\end_layout
\begin_layout Standard
The alternative, proposed by neural-net approaches, avoids ever explicitly
setting the weight of any edge in the clique to zero.
By means of hill-climbing, relaxation or some other Monte Carlo or deep-learnin
g technique, many edges eventually become weak.
But they are never explicitly forced to zero.
The failure of these techniques to drive an unlikely proposition to complete
falsehood (zero probability) prevents these techniques from having any
simple, direct symbolic representation.
In practice, this can also result in a cluttered data-space, where many
small-but-non-zero probabilities and weights require compute storage.
\end_layout
\begin_layout Section
Model Building and Vector Representations
\end_layout
\begin_layout Standard
The key driver behind the deep-learning models is the replacement of intractable
probabilistic models by those that are computationally efficient.
This is accomplished in several stages.
First, the full-text probability function
\begin_inset Formula $P\left(\mbox{sentence}\left|\mbox{ fulltext}\right.\right)$
\end_inset
is replaced by the much simpler probability function
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ fulltext}\right.\right)$
\end_inset
.
The former probability function is extremely high-dimensional, whereas
the later is less so.
Its still computationally infeasible, so there are two directions one can
go in.
The traditional bag-of-words model replaces
\begin_inset Quotes eld
\end_inset
fulltext
\begin_inset Quotes erd
\end_inset
by
\begin_inset Quotes eld
\end_inset
set of words in the fulltext
\begin_inset Quotes erd
\end_inset
AKA the
\begin_inset Quotes eld
\end_inset
bag
\begin_inset Quotes erd
\end_inset
, and so one computes
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ bag}\right.\right)$
\end_inset
which is computationally feasible.
Algorithms such as TF-IDF, and many others accomplish this.
The characteristic idea here is to ignore the (syntactic) structure of
the full-text, completely erasing all indication of word-order.
\end_layout
\begin_layout Standard
The bag, however, loses syntactic and semantic structure, and so goes to
far.
An alternate route is to start with
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ fulltext}\right.\right)$
\end_inset
and simplify it by using instead a sliding-window probability function
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ window}\right.\right)$
\end_inset
, thus giving the N-gram model.
The characteristic idea here is to explicitly set
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ other-words}\right.\right)=0$
\end_inset
whenever the other-words are not in the window.
\end_layout
\begin_layout Standard
The N-gram model is still computationally intractable for
\begin_inset Formula $N\ge3$
\end_inset
and so the deep-learning models propose that yet more entries in
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ window}\right.\right)$
\end_inset
can be ignored or conflated.
Conceptually, the models propose computing
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ context}\right.\right)$
\end_inset
with the context being a projection to a low-dimensional space.
These ideas can be illustrated more precisely.
Let
\begin_inset Formula
\[
\vec{v}_{I}=\vec{v}_{t-c}\times\vec{v}_{t-c+1}\times\cdots\times\vec{v}_{t+c}
\]
\end_inset
be the context, with
\begin_inset Formula $\vec{v}_{w}=\pi\hat{e}_{w}$
\end_inset
the projection of the unit vector of the word down to the low-dimensional
\begin_inset Quotes eld
\end_inset
hidden layer
\begin_inset Quotes erd
\end_inset
vector space.
This projection can be written as
\begin_inset Formula $\vec{v}_{I}=\left[\pi\oplus\cdots\oplus\pi\right]\left(\hat{e}_{t-c}\times\hat{e}_{t-c+1}\times\cdots\times\hat{e}_{t-c}\right)$
\end_inset
where
\begin_inset Formula $\pi\oplus\cdots\oplus\pi$
\end_inset
is the block-diagonal matrix
\begin_inset Formula
\[
\pi\oplus\cdots\oplus\pi=\begin{bmatrix}\pi & 0\\
0 & \pi\\
& & \ddots\\
& & & \pi & 0\\
& & & 0 & \pi
\end{bmatrix}
\]
\end_inset
and so the off-block-diagonal entries are explicitly assumed to be zero,
as an
\emph on
a priori
\emph default
built-in assumption.
Note that the zero entries in this matrix greatly outnumber the non-zero
entries.
Almost all entries are zero.
\end_layout
\begin_layout Standard
Its useful to keep tabs on these sizes.
The matrix
\begin_inset Formula $\pi$
\end_inset
was
\begin_inset Formula $D\times W$
\end_inset
-dimensional, with
\begin_inset Formula $W$
\end_inset
the number of vocabulary words (as always) and
\begin_inset Formula $D$
\end_inset
the
\begin_inset Quotes eld
\end_inset
hidden
\begin_inset Quotes erd
\end_inset
dimension.
For a window of size
\begin_inset Formula $N$
\end_inset
, the matrix
\begin_inset Formula $\pi\oplus\cdots\oplus\pi$
\end_inset
has dimensions
\begin_inset Formula $ND\times NW$
\end_inset
.
Of these, only
\begin_inset Formula $NDW$
\end_inset
are non-zero, the remaining
\begin_inset Formula $N\left(N-1\right)DW$
\end_inset
are zero.
That's a lot of zeros.
\end_layout
\begin_layout Standard
One can do one of several things with the vector
\begin_inset Formula $\vec{v}_{I}$
\end_inset
.
In the SkipGram and CBOW models, one sums over words; that is, one creates
the vector
\begin_inset Formula $\sum_{i\in I}\vec{v}_{i}$
\end_inset
.
Its worth writing this out, matrix style.
One has that
\begin_inset Formula
\[
\sum_{i\in I}\vec{v}_{i}=S\vec{v_{I}}
\]
\end_inset
where the matrix
\begin_inset Formula $S$
\end_inset
is a concatenation of identity matrices.
\begin_inset Formula
\[
S=\left[\left|\begin{array}{cccc}
1 & 0\\
0 & 1\\
& & \ddots\\
& & & 1
\end{array}\right|\left|\begin{array}{cccc}
1 & 0\\
0 & 1\\
& & \ddots\\
& & & 1
\end{array}\right|\cdots\left|\begin{array}{cccc}
1 & 0\\
0 & 1\\
& & \ddots\\
& & & 1
\end{array}\right|\right]
\]
\end_inset
The reason for writing it out in this way to understand that there is another
dimensional reduction: again, almost all entries in this matrix are zero.
Each identity matrix was
\begin_inset Formula $D\times D$
\end_inset
dimensional, and there are
\begin_inset Formula $N$
\end_inset
of them, so that
\begin_inset Formula $S$
\end_inset
has dimensions
\begin_inset Formula $D\times ND$
\end_inset
.
Of these, there are only
\begin_inset Formula $ND$
\end_inset
non-zero entries; the remaining
\begin_inset Formula $ND\left(D-1\right)$
\end_inset
are all zero.
The reduction is huge.
\end_layout
\begin_layout Standard
For the perceptron model of Bengio, the matrix
\begin_inset Formula $S$
\end_inset
is replaced by a weight matrix
\begin_inset Formula $h$
\end_inset
projecting to the perceptron layer.
All of the entries in the matrix
\begin_inset Formula $h$
\end_inset
are, by assumption, non-zero.
This perhaps helps make it clear just how much more complex the perceptron
model is.
Since
\begin_inset Formula $h$
\end_inset
is an approximately square matrix, this implies a large-number of non-zero
entries.
\end_layout
\begin_layout Standard
Its worth getting an intuitive feeling for the size of these numbers: following
Mikolov, assume that
\begin_inset Formula $W=10^{4}$
\end_inset
although this sharply underestimates the size of the vocabulary of English.
Assume
\begin_inset Formula $N=5$
\end_inset
and
\begin_inset Formula $D=300$
\end_inset
.
The size of the input vector space is thus
\begin_inset Formula $W^{N}=10^{20}$
\end_inset
, this is being modeled by a vector space of size 300.
The sparsity is thus
\begin_inset Formula
\[
\log_{2}\frac{10^{20}}{300}=31.3\mbox{ bits}
\]
\end_inset
A truly vast amount of potential information is being discarded by this
language model.
Of course, the claim is that the English language never carried this much
information in the first place: almost all five-word sequences are meaningless
non-sense; only a very small number of these are syntactically valid, and
somewhat fewer are semantically meaningful.
\end_layout
\begin_layout Standard
This exposes the real question: just how meaningful are the CBOW/SkipGram
models, and can one find better models that also have
\begin_inset Quotes eld
\end_inset
lots of zero entries
\begin_inset Quotes erd
\end_inset
, but distribute them in a more accurate way?
\end_layout
\begin_layout Subsection
Sparsity
\begin_inset CommandInset label
LatexCommand label
name "subsec:Sparsity"
\end_inset
\end_layout
\begin_layout Standard
The last question can be answered by noting that the Link Grammar disjunct
representation is also a very highly sparse matrix; however, it is sparse
in a very different way, and does NOT have the block-diagonal structure
of the deep-learning systems.
The can be explicitly illustrated and numerically quantified.
\end_layout
\begin_layout Standard
At the end of one stage of training, one obtains a matrix of observation
counts
\begin_inset Formula $N\left(w,d\right)$
\end_inset
, which are easily normalized to probabilities
\begin_inset Formula $p\left(w,d\right)$
\end_inset
.
This is, in fact, a very sparse matrix.
Four datasets can be quoted: for English, the so-called
\begin_inset Quotes eld
\end_inset
en_mtwo
\begin_inset Quotes erd
\end_inset
dataset, and the
\begin_inset Quotes eld
\end_inset
en_cfive
\begin_inset Quotes erd
\end_inset
dataset; for Mandarin, the
\begin_inset Quotes eld
\end_inset
zen
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
zen_three
\begin_inset Quotes erd
\end_inset
datasets.
Please refer to the diary
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2013"
literal "true"
\end_inset
for a detailed description of these datasets.
The dimensions and sparsity are summarized in the table below.
\begin_inset Separator latexpar
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features tabularvalignment="middle">
<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
name
\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
\begin_inset Formula $W$
\end_inset
\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
\begin_inset Formula $\left|d\right|$
\end_inset
\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
sparsity
\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
en_mtwo
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
137K
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.24M
\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.60 bits
\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
en_cfive
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
445K
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
23.4M
\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.32 bits
\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
zen
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
60K
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
602K
\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.46 bits
\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
zen_three
\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
85K
\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.88M
\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
15.85 bits
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Standard
Here, as always,
\begin_inset Formula $W=\left|w\right|$
\end_inset
is the number of observed vocabulary words,
\begin_inset Formula $\left|d\right|$
\end_inset
is the number of observed disjuncts, and the sparsity is the log of number
of non-zero pairs
\begin_inset Formula $\left(w,d\right)$
\end_inset
, measured in bits:
\begin_inset Formula
\[
\mbox{sparsity}=-\log_{2}\frac{\left|\left(w,d\right)\right|}{\left|w\right|\left|d\right|}
\]
\end_inset
Notable in the above report is that the measured sparsity seems to be approximat
ely language-independent, and dataset-size independent.
\end_layout
\begin_layout Standard
Some of the observed sparsity is due to a lack of a sufficient number of
observations of language use.
Some of the sparsity is due to the fact that certain combinations really
are forbidden: one really cannot string words in arbitrary order.
What fraction of the sparsity is due to which effect is unclear.
Curiously, increasing the number of observations (en_cfive vs.
en_mtwo) increased the sparsity; but this could also be due to the much
larger vocabulary, which is now even more rarely observed.
A significant part of the expanded vocabulary includes Latin and other
foreign-language words, which, of necessity, will be very infrequent, and
when they occur, they will be in set phrases that readers are expected
to recognize.
The point here is that one cannot induce a foreign-language grammar from
a small number of set phrases embedded in English text.
A major portion of the expanded vocabulary are geographical place names,
product names and the like, which are also inherently sparse.
Unlike the foreign phrases, this does not mean that they are inflexible
in grammatical usage: one can use the name of a small town in a vast number
of sentences, even if the observed corpus uses it in only a few.
\end_layout
\begin_layout Standard
Two more factors compound the confusion.
One is that the observed text will necessarily contain grammatically-incorrect
text: the occasional mis-spelled word, the occasional awkwardly worded
phrase; omitted determiners, incorrect number, tense agreement.
A far more serious issue is that the disjuncts are constructed by means
of MST parsing, which has a reasonably large error rate: based on reports
from Yuret
\begin_inset CommandInset citation
LatexCommand cite
key "Yuret1998"
literal "true"
\end_inset
and others, one can expect parses that are 80% to 90% accurate; the fraction
of incorrect disjuncts may range from 5% to 20%.
Incorrect disjuncts decrease the observed sparsity: they make some observations
more frequent than they should be, but only because they're wrong.
\end_layout
\begin_layout Standard
Compared to the back-of-the-envelope estimate of sparsity for SkipGrams,
the numbers reported above are much lower.
There are several ways to interpret this: the simple disjunct model, as
presented above, fails to compress sufficiently well, or the SkipGram model
compresses too much.
Its likely that both situations are the case.
\end_layout
\begin_layout Subsubsection
No Large Data Limit
\begin_inset CommandInset label
LatexCommand label
name "subsec:Zipf's-Law;-Noise"
\end_inset
\end_layout
\begin_layout Standard
Natural language does not have a large-data limit.
More generally, Zipf distributions cannot have a large-data limit.
This is in contrast to normal distributions, where the large-data limit
is a Gaussian.
\end_layout
\begin_layout Standard
Ignoring
\begin_inset Quotes eld
\end_inset
natural
\begin_inset Quotes erd
\end_inset
sparsity due to forbidden grammatical constructions, it is also the case
that the input dataset
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is both noisy and incomplete.
It is noisy because the sample size is not sufficiently large to adequately
approach a large-sample-size limit.
Reaching this limit is fundamentally impossible, from first principles,
if one assumes the Zipf distribution (as is the case here).
For a Zipf distribution, half the dataset necessarily consists of
\emph on
hapax legomena
\emph default
.
Another 15% to 20% are
\emph on
dis
\emph default
and
\emph on
tris legomena
\emph default
.
Increasing the number of observations do not change these ratios: the more
one observes, the more singular phenomena one will find.
Noise in the dataset is unavoidable.
Furthermore, implicit in this is that the dataset is necessarily incomplete:
if half the dataset consists of events that were observed just once; there
are
\begin_inset Quotes eld
\end_inset
even more
\begin_inset Quotes erd
\end_inset
events, that were never observed.
\end_layout
\begin_layout Standard
Consider, for example, the set of short sentences.
One might think that, if one was able to observe every sentence ever spoken
or written, one might eventually observe ever grammatically valid noun-verb
combination.
This is not so.
The sentence
\begin_inset Quotes eld
\end_inset
green ideas sleep furiously
\begin_inset Quotes erd
\end_inset
is quite common, as it is a stock example sentence in linguistics.
However, the similar sentence
\begin_inset Quotes eld
\end_inset
blue concepts wilt skillfully
\begin_inset Quotes erd
\end_inset
probably has never been written down before, until just now.
The law of large numbers does not apply to the Zipfian distribution.
The matrix
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is necessarily noisy and incomplete, no matter how large the sample size.
What is not clear is what fraction of the sparsity is due to the Zipf distribut
ion, and what fraction is the sparsity is due to forbidden grammatical construct
ions.
\end_layout
\begin_layout Subsection
Word Classes
\end_layout
\begin_layout Standard
In operational practice, dependency grammars work with word-classes, and
not with words.
That is, one carves up the set of words into grammatical classes, such
as nouns, verbs, adjectives, etc.
and then assign words to each.
Each grammatical class is associated with a set of disjuncts that indicate
how a word in that class can attach to words in other classes.
This can be made notationally precise.
\end_layout
\begin_layout Standard
Given a word
\begin_inset Formula $w$
\end_inset
and the disjunct
\begin_inset Formula $d$
\end_inset
it was observed with, the goal is to classify it into some grammatical
category
\begin_inset Formula $g$
\end_inset
.
The probability of this usage is
\begin_inset Formula $p(w,d,g)$
\end_inset
, and it should factorize into two distinct parts:
\begin_inset Formula
\[
p\left(w,d,g\right)=p^{\prime}\left(w|g\right)p^{\prime\prime}\left(g,d\right)
\]
\end_inset
None of the three probabilities above are known, a priori, and not even
the number of grammatical classes are known at the outset.
Instead, one has the observational data, that
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
p\left(w,d\right)=p\left(w,d,*\right)=\sum_{g\in G}p\left(w,d,g\right)
\]
\end_inset
where
\begin_inset Formula $G$
\end_inset
is the set of all grammatical classes.
The goal is then to determine the set
\begin_inset Formula $G$
\end_inset
and to perform the matrix factorization
\begin_inset Formula
\begin{equation}
p\left(w,d\right)\approx\sum_{g\in G}p^{\prime}\left(w|g\right)p^{\prime\prime}\left(g,d\right)\label{eq:factorize}
\end{equation}
\end_inset
Ideally, the size of the set
\begin_inset Formula $G$
\end_inset
is minimal, in some way, so that the matrices
\begin_inset Formula $p^{\prime}(w|g)$
\end_inset
and
\begin_inset Formula $p^{\prime\prime}(g,d)$
\end_inset
are of low rank.
In the extreme case of
\begin_inset Formula $G$
\end_inset
having only one element, total, the factorization is the same as the outer
product, or tensor product, of two vectors.
\end_layout
\begin_layout Standard
In the following, the prime-superscripts are dropped, and the joint probabilitie
s are written as
\begin_inset Formula $p(w,g)$
\end_inset
and
\begin_inset Formula $p(g,d)$
\end_inset
.
These are two different probabilities; which in turn are not the same as
\begin_inset Formula $p\left(w,d\right)$
\end_inset
.
Which one is which should be apparent from context.
The probability
\begin_inset Formula $p\left(w|g\right)$
\end_inset
is a conditional probability:
\begin_inset Formula $p\left(w|g\right)=p\left(w,g\right)/p\left(*,g\right)$
\end_inset
.
This is used to ensure that the factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
, as well as the factors, all behave correctly as a joint probabilities:
\begin_inset Formula
\begin{eqnarray*}
p\left(*,d\right) & = & \sum_{w}p\left(w,d\right)\\
& = & \sum_{w}\sum_{g}p\left(w|g\right)p\left(g,d\right)\\
& = & \sum_{w}\sum_{g}\frac{p\left(w,g\right)}{p\left(*,g\right)}p\left(g,d\right)\\
& = & \sum_{g}p\left(g,d\right)
\end{eqnarray*}
\end_inset
and all joint probabilities normalize correctly:
\begin_inset Formula $p\left(*,*\right)=1$
\end_inset
.
\end_layout
\begin_layout Standard
There are two ways of performing the factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
: by applying graphical methods (such as clustering) or by applying gradient
descent methods (typically associated with neural net algorithms).
These two approaches are explored below.
\end_layout
\begin_layout Subsubsection
Learning Word Senses
\end_layout
\begin_layout Standard
The goal of the factorization is to capture semantic information along with
syntactic information.
Typically, any given
\begin_inset Formula $\left(w,d\right)$
\end_inset
pair might belong to only one grammatical category.
So, for example, the pair
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
girl: the-;
\end_layout
\end_inset
would be associated with
\begin_inset Formula $g=\mathtt{<common-count-nouns>}$
\end_inset
.
This captures the idea that girls, boys, houses and birds fall into the
same class, and require the use of a determiner when being directly referenced.
This is distinct from mass nouns, which do not require determiners.
This suggests that, to a large degree, the factorization might be approximately
block-diagonal, at least for the words; that
\begin_inset Formula $p\left(w,g\right)$
\end_inset
might usually have only one non-zero entry for a fixed word
\begin_inset Formula $w$
\end_inset
.
\end_layout
\begin_layout Standard
But this assumption should break down, the larger the size of the set
\begin_inset Formula $G$
\end_inset
.
Suppose one had classes
\begin_inset Formula $g=\mathtt{<cutting-actions>}$
\end_inset
and
\begin_inset Formula $g=\mathtt{<looking-verbs>}$
\end_inset
; the assignment of
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
saw: I- & wood+;
\end_layout
\end_inset
would have non-zero probabilities for both
\begin_inset Formula $g$
\end_inset
's.
For a large number of classes, one might expect to find many distinctions:
girls and boys differ from houses and birds, and one even might expect
to find sex differences: girls pout, and boys punch, while houses and birds
do neither.
\end_layout
\begin_layout Standard
Put differently, one expects different classes to not only differentiate
crud syntactic structure, but also to indicate intensional properties.
Based on practical experience, we expect that most words would fall into
at most ten, almost always less than twenty different classes: this can
be seen by cracking open any dictionary, and counting the number of word
senses for a given word.
Likewise for intentional properties: birds sing, tweet and fly and a few
other verbs.
Houses mostly are, or get something (get built, get destroyed).
That is, we expect
\begin_inset Formula $p\left(w,g\right)$
\end_inset
to be sparse: there might be thousands (or more!) elements in
\begin_inset Formula $G$
\end_inset
, but no more than a few dozen
\begin_inset Formula $p\left(w,g\right)$
\end_inset
, and often much less, will be non-zero, for a fixed word
\begin_inset Formula $w$
\end_inset
.
\end_layout
\begin_layout Subsection
Clustering
\end_layout
\begin_layout Standard
A side effect of the matrix factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
is that it is a
\emph on
de facto
\emph default
form of clustering.
Whenever one has
\begin_inset Formula $p(w,g)>0$
\end_inset
, one can effectively say
\begin_inset Quotes eld
\end_inset
word
\begin_inset Formula $w$
\end_inset
has been assigned to cluster
\begin_inset Formula $g$
\end_inset
\begin_inset Quotes erd
\end_inset
.
Thus, solving eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
can be seen as an alternative to deploying a clustering algorithm to assign
words to word classes.
\end_layout
\begin_layout Subsubsection
Multiple class membership
\end_layout
\begin_layout Standard
One important distinction between traditional clustering and matrix factorizatio
n is that traditional clustering algorithms naively assign a word to only
a single cluster, whereas here, one can have multiple
\begin_inset Formula $p(w,g)>0$
\end_inset
.
One can partly overcome this difficulty with traditional clustering by
decomposing the input vector into two: a component parallel to the cluster
centroid, and a perpendicular component, and assigning the parallel component
to the cluster, while leaving behind the perpendicular component to be
assigned to other clusters.
The decomposition need not be strict about parallelism: one might choose
to merge the component that lies within some angle (or distance) of the
cluster centroid.
Each such merge then gradually shifts the centroid over.
If the left-over perpendicular component is sufficiently small, it can
be discarded as noise, or treated as an anomaly awaiting additional data.
\end_layout
\begin_layout Standard
This splitting of a vector into components, and then placing each component
in a different cluster might perhaps be reminiscent of fuzzy clustering,
where one object may be placed into two clusters.
However, what is proposed above is
\emph on
not
\emph default
fuzzy clustering.
The goal is disambiguate a word precisely into the intended sense, and
to assign that sense to a cluster.
The goal is not to say
\begin_inset Quotes eld
\end_inset
oh, maybe it is this, and maybe it is that.
\begin_inset Quotes erd
\end_inset
A more precise formulation of this statement is taken up in a later section.
\end_layout
\begin_layout Subsubsection
\begin_inset Formula $k$
\end_inset
-means clustering
\end_layout
\begin_layout Standard
Clustering, and in particular,
\begin_inset Formula $k$
\end_inset
-means clustering, can be shown to be equivalent to matrix factorization.
\begin_inset CommandInset citation
LatexCommand cite
key "Ding2005"
literal "true"
\end_inset
In particular, the equations that define
\begin_inset Formula $k$
\end_inset
-means as a relaxation problem, of aligning vectors to the closes centroids,
can be written explicitly as matrices.
This equivalence is reviewed in the section after the next, after a sufficient
amount of other mathematical devices have been set up.
Most important of these is the choice of an appropriate information metric
(instead of cosine distance) for the clustering norm, together with a justifica
tion of why this is necessary.
This needs to be coupled to an appropriate mechanism for performing multiple
class membership.
\end_layout
\begin_layout Standard
Once this is done, clustering can be re-interpreted as more of a graphical
method, as opposed to an optimization method.
\end_layout
\begin_layout Subsubsection
MST (Agglomerative) Clustering
\end_layout
\begin_layout Standard
MST clustering is a form of greedy clustering, attempting to first connect
all points in the dataset with a tree that minimizes the the distance between
the points, and then removing some of the longest edges, leaving behind
a set of connected components.
MST clustering can be fairly efficient, as one can find provisionally minimal
trees with a fairly small number of distance evaluations, using a greedy
algorithm; the provisional minimal tree can then be adjusted using local
relaxation.
\end_layout
\begin_layout Standard
Grygorash
\emph on
et al
\begin_inset CommandInset citation
LatexCommand cite
key "Grygorash2006"
literal "true"
\end_inset
\emph default
review multiple variants for deciding which edges to remove from an MST
graph, and describe several particularly effective variants.
Standard MST removes the longest edges; but one can instead remove edges
that differ the most from their neighbors; or one can remove edges that
are outliers from the typical edge-length mean.
\end_layout
\begin_layout Subsubsection
Non-issues
\end_layout
\begin_layout Standard
There are a variety of criticisms of different clustering algorithms, pointing
at various drawbacks.
Some of these criticisms do not apply to the current problem, and so are
not to be used in selecting a better algorithm.
\end_layout
\begin_layout Itemize
Convex clusters.
This is a standard criticism leveled against
\begin_inset Formula $k$
\end_inset
-means clustering: the clusters can only ever be convex.
This is important criticism, when working with low-dimensional data (2D,
3D data) where perhaps most practical examples require clusters that are
not convex.
For the language learning problem, the data lives in an extremely high-dimensio
nal space, with clusters that are almost surely convex.
\end_layout
\begin_layout Subsection
Low Rank Matrix Approximation
\end_layout
\begin_layout Standard
Factorizations of the form of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
are not uncommon in machine learning.
They generally go under the name of Low Rank Matrix Approximation (LRMA).
The rank refers to the size of the set
\begin_inset Formula $G$
\end_inset
– it is the rank of the matrices in the factorization.
The factorization is only an approximation to the original data; thus,
one says LRMA and not LRMF.
\end_layout
\begin_layout Standard
Closely related is the concept of non-negative matrix factorization (NMF
or NNMF),
\begin_inset CommandInset citation
LatexCommand cite
key "WP-NNMF"
literal "true"
\end_inset
where the focus is on keeping matrix entries positive, as would be appropriate
for probabilities.
Furthermore, a matrix of probabilities is not just non-negative; it also
has non-negative rank;
\emph on
viz
\emph default
.
every non-negative linear combination of the rows or columns must also
be non-negative.
\end_layout
\begin_layout Standard
It is known that the factorization of non-negative matrices with non-negative
rank is an NP-hard problem.
Factorization can be seen as generalizing
\begin_inset Formula $k$
\end_inset
-means clustering, which is known to be NP-complete.
\end_layout
\begin_layout Standard
A variety of techniques for performing this factorization have been developed.
A lightning review is given below.
The point of the review is less to edify the reader, than it is to point
out which techniques, formulas and metrics are the most appropriate for
the present situation, namely, eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
for probabilities, coupled to the need for fairly crisp word-sense disambiguati
on.
\end_layout
\begin_layout Standard
Of these, perhaps the most important point is that the space of joint probabilit
ies is not the same as Euclidean space.
This is a terminological issue that unintentionally becomes a technical
issue.
Properly speaking, frequency counts are multisets or bags; these resemble
vectors, and are commonly thought of and treated as vectors; they are not.
The risk of envisioning vectors is that it leads one to think of dot-products,
cosine angles and rotational invariance.
These are all valid concepts for Euclidean space; but probability does
not live in a Euclidean space.
The shape of the space
\begin_inset Formula $\sum_{i}p_{i}=1$
\end_inset
is a convex polytope; a rotation applied to a point in this space will
typically rotate it out.
That is, bags/multisets are neither rotationally invariant, nor rotationally
covariant.
Yet, many matrix factorization frameworks assume rotational invariance.
This creates issues, and so is a point to focus on in what follows.
\end_layout
\begin_layout Subsubsection
Probabilistic Matrix Factorization
\end_layout
\begin_layout Standard
Probabilistic matrix factorization (PMF) (alternately, stochastic matrix
factorization (SMF)) assumes that the observation counts
\begin_inset Formula $N\left(w,d\right)$
\end_inset
are normally distributed (i.e.
are Gaussian).
The factorization is then obtained by minimizing the Frobenius norm of
the difference of the left and right sides.
That is, one defines the error matrix (or residual matrix)
\begin_inset Formula
\[
E\left(w,d\right)=\left|p\left(w,d\right)-\sum_{g\in G}p\left(w|g\right)p\left(g,d\right)\right|
\]
\end_inset
and from this, the objective function
\begin_inset Formula
\[
U=\sum_{w,d}\left|E\left(w,d\right)\right|^{2}
\]
\end_inset
After fixing the dimension
\begin_inset Formula $\left|G\right|$
\end_inset
, one searches for the matrices
\begin_inset Formula $p\left(w|g\right)$
\end_inset
and
\begin_inset Formula $p\left(g,d\right)$
\end_inset
that minimize the objective function.
\end_layout
\begin_layout Standard
The primary drawbacks of probabilistic matrix factorization is that it does
not provide any guarantees or mechanism to keep the factor
\begin_inset Formula $p\left(w|g\right)$
\end_inset
sparse.
It's not built on information-theoretic infrastructure: it is not leveraging
the idea that the
\begin_inset Formula $p$
\end_inset
's are probabilities; it does not consider the information content of the
problem.
From first principles, it would seem that information maximization would
be a desirable property.
\end_layout
\begin_layout Standard
The assumption that the matrix entries are normally distributed are also
in a direct collision course with the known fact that the distribution
of the matrix entries are Zipfian, as argued in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Zipf's-Law;-Noise"
\end_inset
.
Although one can compute a mean or expectation value for the
\begin_inset Formula $p\left(w,d\right)$
\end_inset
, creating a histogram around this mean value will not reveal a curve in
the shape of a Gaussian.
\end_layout
\begin_layout Standard
Some words occur with frequencies that are many orders of magnitude larger
than others.
The Frobenius norm then becomes very strict for the former, and very loose
for the latter.
It leads to a situation where improving the factorization by 1% for a high
frequency word is equivalent to being wrong by factors of 2 or 3 on low-frequen
cy words.
This does not seem like a plausible weighting scheme.
The Frobenius norm seems less than ideal for the problem at hand.
\end_layout
\begin_layout Subsubsection
Nuclear Norm
\end_layout
\begin_layout Standard
Whenever the error matrix
\begin_inset Formula $E\left(w,d\right)$
\end_inset
can be decomposed into a set
\begin_inset Formula $\left\{ \sigma_{i}\right\} $
\end_inset
of singular values, then the trace of the decomposition is
\begin_inset Formula $t=\sum_{i}\sigma_{i}$
\end_inset
.
The trace can be treated as the objective function to be minimized, leading
to a valid factorization, differing from that obtained by PMF.
\end_layout
\begin_layout Standard
The word
\begin_inset Quotes eld
\end_inset
nuclear
\begin_inset Quotes erd
\end_inset
comes from operator theory, where the definition of a nuclear operator
as one that is of trace-class, i.e.
having a trace that is invariant under orthogonal or unitary transformations.
In such cases, there is an explicit assumption that the operator lives
in some homogeneous space,
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Homogenous-space"
literal "true"
\end_inset
where orthogonal or unitary transformations can be applied.
From an initial, naive point of view, this seems appropriate for machine
learning.
In machine learning, the spaces are always finite dimensional, and are
usually explicitly assumed to be real Euclidean space
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
– that is, the spaces behave like actual vector spaces, so that concepts
like Principle Component Analysis (PCA) and Singular Value Decomposition
(SVD) can be applied.
SVD is particularly appealing, as it provides the best possible approximate
decomposition of a given rank.
Fixing the rank
\begin_inset Formula $\left|G\right|$
\end_inset
, the SVD is that decomposition which minimizes the mean square error for
that rank; that is, it minimizes the objective function
\begin_inset Formula $U$
\end_inset
.
\end_layout
\begin_layout Standard
The subtle point here is that the space in which
\begin_inset Formula $p\left(w,d\right)$
\end_inset
lives is
\emph on
not
\emph default
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
(nor is it
\begin_inset Formula $\mathbb{R}^{\left|W\right|\times\left|D\right|}$
\end_inset
, if one is a stickler about dimensions).
Rather,
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is constrained to live inside of a simplex (of dimension
\begin_inset Formula $\left|W\right|\times\left|D\right|$
\end_inset
).
Sure, one can blur one's eyes and imagine that this simplex is a subspace
of
\begin_inset Formula $\mathbb{R}^{\left|W\right|\times\left|D\right|}$
\end_inset
, and that is not entirely wrong.
However, the only transformations that can be applied to points in a simplex,
that keep the points inside the simplex, are Markov matrices.
Any other transformations will typically move points into the inside from
the outside, and move inside points to the outside.
In particular, rotations (orthogonal transformations) cannot be applied
to a probability, such that the result is still a probability.
Applying the notion of a trace, which is implicitly defined as being invariant
under orthogonal transformations, is inappropriate for the problem at hand.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Perhaps this explains why results based on SVD are often underwhelming as
compared to others.
See, for example
\begin_inset CommandInset citation
LatexCommand cite
key "Levy2014"
literal "true"
\end_inset
for precisely such a report: the conception that SVD could have or should
have given a better result, followed by the disappointment of noting that
it does not.
Of course, other explanations are also possible: one is that SVD behaves
poorly when some matrix elements are missing or unknown.
This shortcoming is one reason why PMF, above, and LLORMA, below, have
been proposed.
\end_layout
\end_inset
What would be appropriate is some sort of trace-like invariant that transforms
as a scalar under Markov transformations.
\end_layout
\begin_layout Subsubsection
Non-Negative Matrix Factorization
\end_layout
\begin_layout Standard
Non-negative matrix factorization (NMF) is similar to PMF, but with the
additional constraint that the result has a non-negative rank.
The non-negative rank constraint requires that not only do the factor matrices
have non-negative values in them, but also that non-negative linear combination
s are also non-negative.
This appears be an appropriate restriction for probabilities.
\end_layout
\begin_layout Standard
A reasonable review of NMF is given in
\begin_inset CommandInset citation
LatexCommand cite
key "Eggert2004"
literal "true"
\end_inset
, which also describes how one can control the sparsity of the resulting
factors.
Control over sparsity is one reason that clustering techniques are interesting;
something as fast or faster that offers control over sparsity is appealing.
\end_layout
\begin_layout Standard
NMF using the Kullback-Leibler divergence is equivalent to Probabilistic
Latent Semantic Indexing (PLSI), although the two commonly used algorithms
for each are quite different, and each is able to climb out of local minima
of the other.
\begin_inset CommandInset citation
LatexCommand cite
key "Ding2008"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
The error term that needs to be minimized is the matrix-factorized form
of the mutual information, which is just the Kullback-Leibler divergence
between the factored and unfactored matrices:
\begin_inset Formula
\begin{equation}
MI_{\mbox{factor}}=\sum_{w,d}p\left(w,d\right)\log\frac{p\left(w,d\right)}{\sum_{g\in G}p\left(w|g\right)p\left(g,d\right)}\label{eq:KL-MI-factorization-loss}
\end{equation}
\end_inset
In essence, this measures the information loss in moving from the full distribut
ion
\begin_inset Formula $p\left(w,d\right)$
\end_inset
to the factorized version; for a good factorization, one wishes to minimize
this information loss.
\end_layout
\begin_layout Subsubsection
Projective Probability Amplitudes
\end_layout
\begin_layout Standard
The previous sections argue that when vectors are interpreted as probabilities,
then dot-products and invariance under orthogonal transformations are inappropr
iate, because these transform probabilities into things that cannot be interpret
ed as probabilities.
Intuitively, information-theoretic manipulations that preserve the probability
aspects seem wiser.
However, there is another possibility: work with probability amplitudes.
\end_layout
\begin_layout Standard
A vector is a probability, if one has that
\begin_inset Formula
\[
\sum_{n}p_{n}=1
\]
\end_inset
That is, a point
\begin_inset Formula $\vec{p}$
\end_inset
is constrained to live on the surface of a simplex.
One can apply a simple trick: just write
\begin_inset Formula $a_{n}=\sqrt{p_{n}}$
\end_inset
and then the constraint becomes
\begin_inset Formula
\[
\sum_{n}a_{n}^{2}=1
\]
\end_inset
Clearly, the point
\begin_inset Formula $\vec{a}$
\end_inset
is constrained to live on the surface of a sphere.
Now, orthogonal rotations do not violate this constraint.
\end_layout
\begin_layout Standard
This implies that nuclear norms, or Frobenius norms might be quite appropriate,
if, instead of working with
\begin_inset Formula $\vec{p}$
\end_inset
, one worked with
\begin_inset Formula $\vec{a}$
\end_inset
.
To be more specific, define
\begin_inset Formula $a\left(w,d\right)=\sqrt{p\left(w,d\right)}$
\end_inset
and then define an error matrix (residual matrix)
\begin_inset Formula
\[
E\left(w,d\right)=\left|a\left(w,d\right)-\sum_{g\in G}a\left(w;g\right)a\left(g;d\right)\right|
\]
\end_inset
and then, to assign word
\begin_inset Formula $w$
\end_inset
to word-sense cluster
\begin_inset Formula $g$
\end_inset
, seek to minimize the objective function
\begin_inset Formula
\[
U=\sum_{w,d}\left|E\left(w,d\right)\right|^{2}
\]
\end_inset
This seems like a plausible objective function, if the
\begin_inset Formula $a\left(w,d\right)$
\end_inset
are normally distributed.
But, as argued in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Zipf's-Law;-Noise"
\end_inset
, this is a faulty assumption.
As noted before, this error matrix causes high-frequency words to strongly
dominate over low-frequency words in the factorization.
Again, this seems like an implausible objective function for natural language
or any Zipfian distributions.
\end_layout
\begin_layout Subsubsection
Local Low Rank Matrix Factorization
\end_layout
\begin_layout Standard
Local Low Rank Matrix Factorization (LLORMA)
\begin_inset CommandInset citation
LatexCommand cite
key "Lee2016"
literal "true"
\end_inset
is a matrix factorization algorithm exhibiting accuracy and performance
at near state-of-the-art levels.
It uses a combination of two techniques: kernel smoothing
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Kernel-smoother"
literal "true"
\end_inset
and local regression (LOESS)
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Local-regression"
literal "true"
\end_inset
to obtain smooth estimates for the two factors
\begin_inset Formula $p\left(w,g\right)$
\end_inset
and
\begin_inset Formula $p\left(g,d\right)$
\end_inset
.
\end_layout
\begin_layout Standard
These two techniques, combined, prove to be almost ideal, when faced with
incomplete data, and when the data is noisy.
Specifically, the idea of incompleteness is that some values of the input
dataset
\begin_inset Formula $p\left(w,d\right)$
\end_inset
are zero not because they fundamentally should be (i.e.
are forbidden by the grammar and syntax of natural language), but are zero
simply because they have not yet been observed; some appropriate sentence
does not occur in the sample dataset.
\end_layout
\begin_layout Standard
Thus, the use of the smoothing techniques seems highly appropriate, given
that the input dataset
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is both noisy and incomplete, as discussed in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Zipf's-Law;-Noise"
\end_inset
.
Unfortunately, the use of LLORMA, as strictly described, seems inappropriate,
but only because the use of the Frobenius norm or the nuclear norm is inappropr
iate for this dataset.
The correct norm must be that of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:KL-MI-factorization-loss"
\end_inset
.
It seems reasonable to believe that combining kernel smoothing with local
regression and the information-theoretic norm might yield an excellent
algorithm for factoring joint probabilities.
As an algorithm, it belongs to the gradient-descent class.
\end_layout
\begin_layout Subsubsection
Other factorizations
\end_layout
\begin_layout Standard
There are other techniques for factorization, including
\end_layout
\begin_layout Itemize
NTN (Neural Tensor Network)
\end_layout
\begin_layout Itemize
I-RBM (Restricted Boltzmann Machine)
\end_layout
\begin_layout Itemize
I-AutoRec
\end_layout
\begin_layout Itemize
Neural networks
\begin_inset CommandInset citation
LatexCommand cite
key "Dzuigaite2015"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
These are not reviewed here.
\end_layout
\begin_layout Subsection
Neural Networks as Matrix Factorization
\end_layout
\begin_layout Standard
The need to perform a matrix factorization, of the form of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
was arrived at indirectly, by making an explicit appeal to grammatical
categories and semantics.
To recap: it was argued that N-grams and SkipGrams resemble grammatical
disjuncts.
Grammatical disjuncts can in turn be understood as extremely fine-grained
parts-of-speech.
That parts of speech are correlated with semantic meaning dates back to
the earliest dictionaries.
These arguments, combined together, motivated the correctness of factorization;
they explain why factorization is meaningful and desirable, and why it
aligns with natural, intuitive notions of grammatical category.
\begin_inset CommandInset citation
LatexCommand cite
key "Nida97"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
One can skip this round-about route, ignoring the philosophical ruminations
and motivations, and skip directly to matrix factorization.
Levy and Goldberg do so, by observing that maximization of the SkipGram
objective function is mathematically equivalent to matrix factorization.
\begin_inset CommandInset citation
LatexCommand cite
key "Levy2014"
literal "true"
\end_inset
More generally, Qui
\emph on
et al.
\emph default
show that a number of different neural network techniques, used to embed
very large network graphs into low-dimensional vector spaces, are formally
equivalent to low-rank matrix factorizations.
\begin_inset CommandInset citation
LatexCommand cite
key "Qiu2017"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
In practice, rather than working with an objective function defined directly
from eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
or
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
, Mikolov
\emph on
etal.
\emph default
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013b"
literal "true"
\end_inset
explain that it is more effective to work with a variant involving a sigmoid
function, together with a
\begin_inset Quotes eld
\end_inset
negative sampling
\begin_inset Quotes erd
\end_inset
term, designed to suppress word-context pairings that are not observed.
The negative-sampling term helps draw a sharper distinction between word-contex
t pairings that are infrequently observed, and those that are never observed.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Other work
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017connectors"
literal "true"
\end_inset
suggests that infrequently-observed word-context pairings play an (unexpectedly
) important role in classification, and that explicit filtering to remove
infrequently observed pairings causes significant damage to the quality
of the results.
Thus, rather than discarding infrequent observations, adding a
\begin_inset Quotes eld
\end_inset
negative sampling
\begin_inset Quotes erd
\end_inset
to guess at those pairings that can
\emph on
never
\emph default
happen does indeed seem like a reasonable tactic.
\end_layout
\end_inset
The suitably revised objective function (using the notation from section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:CBOW"
\end_inset
) is built from the observation counts
\begin_inset Formula $N(w_{t},w_{i})$
\end_inset
of a target word
\begin_inset Formula $w_{t}$
\end_inset
and a context word
\begin_inset Formula $w_{i}\in I$
\end_inset
, together with the dimensionally reduced vectors
\begin_inset Formula $\vec{u}_{t}$
\end_inset
and
\begin_inset Formula $\vec{v}_{i}$
\end_inset
.
It is not reviewed here; the details are readily available in
\begin_inset CommandInset citation
LatexCommand cite
key "Mikolov2013b"
literal "true"
\end_inset
and
\begin_inset CommandInset citation
LatexCommand cite
key "Levy2014"
literal "true"
\end_inset
.
\end_layout
\begin_layout Standard
The remarkable result of Levy and Goldberg
\begin_inset CommandInset citation
LatexCommand cite
key "Levy2014"
literal "true"
\end_inset
is that the maximization of this objective function is mathematically identical
to the factorization of the word-pair mutual information of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:word-pair-MI"
\end_inset
.
The explicit result is that the dimensionally reduced vectors
\begin_inset Formula $\vec{u}_{t}$
\end_inset
and
\begin_inset Formula $\vec{v}_{i}$
\end_inset
are related to the mutual information as
\begin_inset Formula
\[
\vec{u}_{t}\cdot\vec{v}_{i}=MI\left(w_{t},w_{i}\right)-\log k
\]
\end_inset
with
\begin_inset Formula $k$
\end_inset
the negative-sampling weighting coefficient.
Just so that importance of this sinks in, it is worth stating again, with
different words: the SkipGram technique is equivalent to a low-rank matrix
factorization of the mutual information between word-pairs.
\end_layout
\begin_layout Standard
This can be used as yet a different vindication of the MST parsing of the
Yuret approach, described in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:MST-parsing"
\end_inset
.
Summations over context words, of the form
\begin_inset Formula
\[
\sum_{i\in I}\vec{u}_{t}\cdot\vec{v}_{i}
\]
\end_inset
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
appearing in eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:CBOW"
\end_inset
or
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:SkipGram"
\end_inset
are nothing more than summations over the mutual information between a
word and it's context.
It now becomes readily apparent that perhaps a summation that discards
low MI values, while also taking into account the entire sentence, can
perhaps yield a superior result.
The two approaches buttress one-another, and mutually explain one-another.
The effectiveness of the SkipGram model is explained by it's resemblance
to MST parsing with word-pair MI, which in turn has strong connections
to symbolic approaches to linguistics.
Grammatical structure as given in the symbolic approach to linguistics
is intellectually overt and comprehensible.
It now appears that the
\begin_inset Quotes eld
\end_inset
sub-symbolic
\begin_inset Quotes erd
\end_inset
, neural network approach, at first seemingly opaque and hidden in a black
box of neural net weights, can be seen as a somewhat obfuscated form of
traditional symbolic linguistics.
\end_layout
\begin_layout Subsection
Clustering as Matrix Factorization
\begin_inset CommandInset label
LatexCommand label
name "subsec:Clustering-as-Matrix"
\end_inset
\end_layout
\begin_layout Standard
One may show that
\begin_inset Formula $k$
\end_inset
-means clustering is equivalent to a rank-
\begin_inset Formula $k$
\end_inset
matrix decomposition with an extra orthogonality condition enforced; this
is developed by Ding
\emph on
et al.
\emph default
\begin_inset CommandInset citation
LatexCommand cite
key "Ding2005"
literal "true"
\end_inset
The orthogonality condition can be loosened, as the process of factorization
is driven by a minimization condition that drives towards approximate orthogona
lity.
In effect,
\begin_inset Formula $k$
\end_inset
-means clustering is a special case of matrix factorization: its factorization
with extra constraints.
\end_layout
\begin_layout Standard
Ding
\emph on
et al
\emph default
examine several forms of
\begin_inset Formula $k$
\end_inset
-means clustering.
The simplest form of clustering assigns vectors to clusters, and stops
there.
This is equivalent to assigning words to word-classes, without making any
specific statements about what happened to the disjuncts.
Alternately, one could say that the disjuncts just went along for the ride:
they were associated with some word before-hand, and they are now still
associated with that word, thrown into a bucket with the other disjuncts
of similar words.
\end_layout
\begin_layout Standard
Bipartite graph clustering (aka
\begin_inset Quotes eld
\end_inset
co-clustering
\begin_inset Quotes erd
\end_inset
) recognizes that the input data can be viewed as a bipartite graph (fig
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Factorization"
\end_inset
, left image), and that one can perform separate, distinct, but simultaneous
clustering on the columns, and separately, the rows.
This is closer to the desired factorization model for language, and so
the proof is reviewed here.
It is still
\begin_inset Formula $k$
\end_inset
-means clustering, just that one performs two clusterings, not one, on the
columns, and on the rows.
\end_layout
\begin_layout Standard
The matrix to be factorized is
\begin_inset Formula $B$
\end_inset
and the desired factorization is
\begin_inset Formula $B\approx LR^{T}$
\end_inset
.
Comparing this to the factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
, the matrix elements of
\series bold
\begin_inset Formula $B$
\end_inset
\series default
are
\begin_inset Formula $p\left(w,d\right)$
\end_inset
; those of
\begin_inset Formula $L$
\end_inset
are
\begin_inset Formula $p\left(w|g\right)$
\end_inset
; those of
\begin_inset Formula $R^{T}$
\end_inset
are
\begin_inset Formula $p\left(g,d\right)$
\end_inset
.
Key to the proof is the reinterpretation of
\begin_inset Formula $L$
\end_inset
and
\begin_inset Formula $R$
\end_inset
as membership matrices, so that each row and column indicate the membership
of a vector to a cluster.
That is
\begin_inset Formula $L$
\end_inset
consists of column vectors
\begin_inset Formula $L=\left[\vec{l}_{1},\vec{l}_{2},\cdots,\vec{l}_{k}\right]$
\end_inset
where each column vector is of the form
\begin_inset Formula
\[
\vec{l}_{j}=\left(0,0,\cdots0,1,1,\cdots,1,0,\cdots,0\right)^{T}
\]
\end_inset
with the
\begin_inset Formula $1$
\end_inset
's indicating the cluster membership.
That is, the matrix elements of
\begin_inset Formula $L$
\end_inset
are
\begin_inset Formula
\[
L_{ij}=\begin{cases}
1 & \mbox{ item }i\mbox{ belongs to cluster }j\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
Hard clustering means that any given
\begin_inset Formula $i$
\end_inset
belongs to only one
\begin_inset Formula $j$
\end_inset
, and so one trivially has that
\begin_inset Formula $\sum_{j}L_{ij}=1$
\end_inset
, which is a key property of a Markov matrix.
That is, hard clustering has the Markov property.
Equivalently, the factorization for the hard-clustering of words into single
classes is
\begin_inset Formula
\[
p\left(w|g\right)=\begin{cases}
1 & \mbox{ word }w\mbox{ belongs to wordclass }g\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
That is, every word belongs to some class, with 100% probability.
\end_layout
\begin_layout Standard
The optimization problem is then to find the maxima of two objective functions,
subject to some constraints:
\begin_inset Formula
\[
\max_{L\ge0;L^{T}L\sim I}\mbox{tr}L^{T}BB^{T}L\;\mbox{ and }\;\max_{R\ge0;R^{T}R\sim I}\mbox{tr}R^{T}B^{T}BR
\]
\end_inset
The constraint
\begin_inset Formula $L^{T}L\sim I$
\end_inset
means that not only should
\begin_inset Formula $L^{T}L$
\end_inset
be a diagonal matrix, but that it should be a multiple of the identity
matrix
\begin_inset Formula $I$
\end_inset
– that is, have equal values along the diagonal.
Here, the tr operator is the matrix trace.
The trace of a matrix is, of course, equal to the sum of the eigenvalues
of the matrix; thus, optimizing the above is equivalent to performing a
singular value decomposition (SVD) of the traced matrix, and then summing
the singular values.
This is, of course, just the nuclear norm discussed previously.
\end_layout
\begin_layout Standard
With some relatively straightforward algebraic manipulation, the above can
be shown to be equivalent to optimizing
\begin_inset Formula
\[
\min\left\Vert B-LR^{T}\right\Vert ^{2}
\]
\end_inset
subject to the same constraints.
The norm
\begin_inset Formula $\left\Vert \cdot\right\Vert ^{2}$
\end_inset
is the Frobenius norm.
In this sense, hard
\begin_inset Formula $k$
\end_inset
-means clustering is identical to matrix factorization.
Removing some of the constraints shows that
\begin_inset Formula $k$
\end_inset
-means clustering is a special case of the more general factorization problem.
Ding
\emph on
et al
\emph default
show that if one removes the orthogonality constraints, the resulting factors
are still approximately orthogonal, since the Frobenius norm contains terms
that drive the factors towards orthogonality.
\end_layout
\begin_layout Standard
Three previously identified issues arise with the above:
\end_layout
\begin_layout Itemize
The hard-clustering assignment of a word to only a single word-class prevents
words from having multiple meanings, and thus forces word-sense disambiguation
to somehow happen somewhere else.
\end_layout
\begin_layout Itemize
The use of the Frobenius norm (or the nuclear norm) implicitly forces assumption
s of rotational invariance, in the form of orthogonality constraints on
the membership indicator matrices
\begin_inset Formula $L$
\end_inset
,
\begin_inset Formula $R$
\end_inset
.
As discussed previously, rotational invariance (and thus, orthogonality)
is inappropriate when
\begin_inset Formula $L$
\end_inset
and
\begin_inset Formula $R$
\end_inset
are interpreted as joint probability distributions.
\end_layout
\begin_layout Itemize
There is no room for a central factor matrix
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
which can capture the non-sparse complexities of the language.
The need; indeed, the inevitability of such a matrix is developed in the
next section.
\end_layout
\begin_layout Standard
The proposed fix to these issues is multi-fold:
\end_layout
\begin_layout Itemize
Use an information-theoretic similarity, namely, the Kullback-Leibler divergence
of the factored solution to the input data.
\end_layout
\begin_layout Itemize
Perform greedy clustering, so as to minimize the number of number of non-zero
entries in the left and right factor matrices
\end_layout
\begin_layout Itemize
Decompose vectors into components that align with clusters, so that clusters
correspond to word-senses, and word-sense disambiguation (WSD) is an inherent,
inbuilt part of the clustering step.
\end_layout
\begin_layout Subsection
Factorization Ambiguity
\end_layout
\begin_layout Standard
When considering the factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
, the sum
\begin_inset Formula $\sum_{g\in G}$
\end_inset
can be seen as a specific function,
\emph on
viz
\emph default
, the inner product of two vectors
\begin_inset Formula $\left(\vec{w}\right)_{g}=p\left(w|g\right)$
\end_inset
and
\begin_inset Formula $\left(\vec{d}\right)_{g}=p\left(g,d\right)$
\end_inset
.
Aside from considering just the function
\begin_inset Formula $f\left(\vec{w},\vec{d}\right)=\vec{w}\cdot\vec{d}$
\end_inset
, one might consider other functions
\begin_inset Formula $f\left(\vec{w},\vec{d}\right)$
\end_inset
of
\begin_inset Formula $\vec{w}$
\end_inset
and
\begin_inset Formula $\vec{d}$
\end_inset
.
For example, a single-layer feed-forward linear neural net would consist
of a
\begin_inset Formula $\left|G\right|\times\left|G\right|$
\end_inset
-dimensional weight matrix
\begin_inset Formula $M$
\end_inset
such that
\begin_inset Formula
\[
f\left(\vec{w},\vec{d}\right)=\vec{w}^{T}\cdot M\cdot\vec{d}
\]
\end_inset
This, in itself, because it is linear, does not accomplish much, because
the matrix
\begin_inset Formula $M$
\end_inset
can be re-composed on the left or the right, to re-define the vectors
\begin_inset Formula $\vec{w}$
\end_inset
or
\begin_inset Formula $\vec{d}$
\end_inset
.
That is, one may write
\begin_inset Formula $\vec{w}^{\prime}=M^{T}\vec{w}$
\end_inset
to get a different product
\begin_inset Formula $\vec{w}^{\prime}\cdot\vec{d}$
\end_inset
, or, alternately
\begin_inset Formula $\vec{d}^{\prime}=M\vec{d}$
\end_inset
for a product
\begin_inset Formula $\vec{w}\cdot\vec{d}^{\prime}$
\end_inset
.
The dot-product in the factorization is ambiguous; the point is that the
factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
is not unique.
\end_layout
\begin_layout Standard
The low-rank matrix-factorization literature expresses this idea by noting
that a dot-product is invariant under orthogonal rotations, and so one
can choose an arbitrary orthogonal matrix
\begin_inset Formula $O$
\end_inset
with
\begin_inset Formula $O^{T}O=I$
\end_inset
and write
\begin_inset Formula
\[
\vec{w}\cdot\vec{d}=\left(\vec{w}O^{T}\right)\cdot\left(O\vec{d}\right)=\vec{w}^{\prime}\cdot\vec{d}^{\prime}
\]
\end_inset
Since the vectors
\begin_inset Formula $\vec{v}$
\end_inset
and
\begin_inset Formula $\vec{d}$
\end_inset
are naturally probabilities, the above is exactly what we do
\emph on
not
\emph default
what to do! As already noted, orthogonal rotations applied to a probability
turn it into something that is not a probability.
Instead, we want to stick to a single (ambiguous) matrix
\begin_inset Formula $M$
\end_inset
that is Markovian, so that, when contracted to the left or to the right,
the resulting vectors are still probabilities.
\end_layout
\begin_layout Standard
This becomes more clear if written in in components:
\begin_inset Formula
\[
p\left(w,d\right)=\sum_{g}\sum_{g^{\prime}}p\left(w|g\right)M\left(g,g^{\prime}\right)p\left(g^{\prime},d\right)
\]
\end_inset
This shows that the factorization is ambiguous; as long as
\begin_inset Formula $M$
\end_inset
is Markovian, preserving the sums of probabilities over rows and columns,
it can be contracted to the left or the right.
Indeed:
\begin_inset Formula $M$
\end_inset
itself can be factored into an arbitrary product of Markovian matrices,
which can then be merged to the left and right.
\end_layout
\begin_layout Standard
Thus, to get a meaningful factorization, one can must introduce additional
constraints.
A seemingly natural one, to be developed later, is to choose
\begin_inset Formula $M$
\end_inset
such that
\begin_inset Formula $p\left(w,g\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
are both maximally sparse.
One would like to assign a word to at most a handful of different word-classes,
corresponding to the synonym classes for each word-sense attached to that
word.
\end_layout
\begin_layout Standard
A quick review of the concept of a Markovian matrix is in order.
A matrix can be Markovian on the left side, the right side, or both.
It is Markovian on the right if
\begin_inset Formula
\[
1=\sum_{g}M\left(g,g^{\prime}\right)\mbox{ for all }g^{\prime}
\]
\end_inset
This assures that a transformed joint probability
\begin_inset Formula
\[
p^{\prime}\left(g,d\right)=\sum_{g^{\prime}}M\left(g,g^{\prime}\right)p\left(g^{\prime},d\right)
\]
\end_inset
is still a valid joint probability distribution; namely, that
\begin_inset Formula $p^{\prime}\left(*,*\right)=1$
\end_inset
.
\end_layout
\begin_layout Standard
If one has such a factorization, so that
\begin_inset Formula $p\left(w,g\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
are maximally sparse, then the matrix
\begin_inset Formula $M$
\end_inset
will likely be very highly connected, i.e.
will have many or most of its matrix entries be non-zero.
Conceptually, one can visualize the matrix
\begin_inset Formula $M$
\end_inset
as a highly connected graph, while the factors
\begin_inset Formula $p\left(w,g\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
are low-density feeder tree-branches that connect into this tightly-coupled
central component.
This is visualized in figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Factorization"
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status collapsed
\begin_layout Plain Layout
\align center
\begin_inset Caption Standard
\begin_layout Plain Layout
Factorization
\begin_inset CommandInset label
LatexCommand label
name "fig:Factorization"
\end_inset
\end_layout
\end_inset
\begin_inset Graphics
filename skimage/factor.eps
lyxscale 65
width 90col%
\end_inset
\end_layout
\begin_layout Plain Layout
This figure attempts to illustrate the process of factorization.
The left-most image is meant to illustrate
\begin_inset Formula $p\left(w,d\right)$
\end_inset
as a sparse matrix.
Edges indicate those values where
\begin_inset Formula $p\left(w,d\right)$
\end_inset
is not zero.
Not every
\begin_inset Formula $w$
\end_inset
is connected to every
\begin_inset Formula $d$
\end_inset
, but there are a sufficient number of connections that the overall graph
is confused and tangled.
The middle image is meant to illustrate the factorization
\begin_inset Formula $\sum_{g}p\left(w,g\right)p\left(g,d\right)$
\end_inset
.
In this factorization, the matrix
\begin_inset Formula $p\left(w,g\right)$
\end_inset
not only becomes more sparse, but has a very low out-degree for fixed
\begin_inset Formula $w$
\end_inset
: only one or a handful of entries in
\begin_inset Formula $p\left(w,g\right)$
\end_inset
are non-zero for fixed
\begin_inset Formula $w$
\end_inset
.
The rightmost image attempts to illustrate the factorization
\begin_inset Formula $\sum_{g,g^{\prime}}p\left(w,g\right)M\left(g,g^{\prime}\right)p\left(g^{\prime},d\right)$
\end_inset
.
Here, the factor
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
has low in-degree for any fixed
\begin_inset Formula $d$
\end_inset
.
All of the tangle and interconnectedness has been factored out into the
matrix
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
connecting word-classes to disjunct-classes.
\end_layout
\begin_layout Plain Layout
In hard-clustering, these low-degree requirements are automatically satisfied:
a word
\begin_inset Formula $w$
\end_inset
can belong to only one word-cluster
\begin_inset Formula $g$
\end_inset
, and so there is only one line in the figure connecting
\begin_inset Formula $w$
\end_inset
to anything.
Likewise, a disjunct
\begin_inset Formula $d$
\end_inset
can only be assigned to one cluster
\begin_inset Formula $g^{\prime}$
\end_inset
.
Due to the fact that words are combinations of word-senses, hard-clustering
in this fashion is undesirable; by contrast, it seems that word-senses
could be validly hard-clustered.
\end_layout
\begin_layout Plain Layout
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"
\end_inset
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
In the above factorization, matrix
\begin_inset Formula $M$
\end_inset
was made explicitly Markovian, so as to preserve the left and right factors
as joint probabilities.
However, it seems to be particularly important to the semantic structure
of the language: it captures the complexity of language, whereas the left
and right factors merely funnel spelled-out word-strings into the actual
semantic categories.
Thus, it is convenient to instead write the left and write factors as Markov
matrices, while taking the central factor to be a joint probability.
This can be achieved by factoring as
\begin_inset Formula
\begin{equation}
p\left(w,d\right)=\sum_{g}\sum_{g^{\prime}}p\left(w|g\right)p\left(g,g^{\prime}\right)p\left(d|g^{\prime}\right)\label{eq:central-decomposition}
\end{equation}
\end_inset
where the left and right factors are conditional probabilities.
That is,
\begin_inset Formula
\[
p\left(w|g\right)=\frac{p\left(w,g\right)}{p\left(*,g\right)}
\]
\end_inset
and likewise for
\begin_inset Formula $p\left(d|g^{\prime}\right)=p\left(g^{\prime},d\right)/p\left(g^{\prime},*\right)$
\end_inset
.
These are explicitly Markovian, in that
\begin_inset Formula
\[
\sum_{g}p\left(w|g\right)=1
\]
\end_inset
and likewise
\begin_inset Formula $\sum_{g^{\prime}}p\left(d|g^{\prime}\right)=1$
\end_inset
.
This factorization is just a rescaling of the earlier factorization:
\begin_inset Formula
\[
p\left(g,g^{\prime}\right)=p\left(*,g\right)M\left(g,g^{\prime}\right)p\left(g^{\prime},*\right)
\]
\end_inset
and is done so that
\begin_inset Formula $p\left(g,g^{\prime}\right)$
\end_inset
can be seen as a joint probability:
\begin_inset Formula
\[
\sum_{g,g^{\prime}}p\left(g,g^{\prime}\right)=1
\]
\end_inset
\end_layout
\begin_layout Standard
The ambiguity of the matrix
\begin_inset Formula $M$
\end_inset
is removed, if one assumes hard clustering.
In this case, each
\begin_inset Formula $w$
\end_inset
can belong to only one
\begin_inset Formula $g$
\end_inset
, and each
\begin_inset Formula $d$
\end_inset
to just one
\begin_inset Formula $g^{\prime}$
\end_inset
, and, once the clusters are chosen, there is no confusion about the left
and right factors, and thus, the central factor is fixed.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
In physics, such an ambiguity of factorization is known as a global gauge
symmetry; fixing a gauge removes the ambiguity.
In natural language, the ambiguity is spontaneously broken: words have
only a few senses, and are often synonymous, making the left and right
factors sparse.
For this reason, the analogy to physics is entertaining but mostly pointless.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
A factorization of this sort is known as co-clustering, bi-clustering or
sometimes block clustering.
An explicit development of this, including an explicit iterative algorithm
guaranteed to converge, is given by Dhillon et al.
\begin_inset CommandInset citation
LatexCommand cite
key "Dhillon2003"
literal "true"
\end_inset
and is reviewed in a subsection below.
Of course, for natural language, we want to decompose words into word-senses,
and so naive hard-clustering will not work.
It does, however, illuminate the path ahead.
\end_layout
\begin_layout Subsubsection
Factorization in Link Grammar
\begin_inset CommandInset label
LatexCommand label
name "subsec:Factorization-in-Link"
\end_inset
\end_layout
\begin_layout Standard
This factorization is
\emph on
de facto
\emph default
observed in the hand-built dictionaries for Link Grammar.
Examination of the
\family typewriter
4.0.dict
\family default
file in the Link Grammar file distribution will clearly show how words
are grouped into word-classes.
For example,
\family typewriter
words.n.2.s
\family default
is a list of plural count-nouns.
The Link Grammar costs are very rough approximations for the log probability
\begin_inset Formula $-\log p$
\end_inset
, and so the contents of
\family typewriter
words.n.2.s
\family default
is effectively a representation of the matrix
\begin_inset Formula $p\left(w,g\right)$
\end_inset
for
\begin_inset Formula $g=\left\langle \mbox{plural-count-nouns}\right\rangle $
\end_inset
and a uniform probability across this class.
The file
\family typewriter
4.0.dict
\family default
also defines a large number of
\begin_inset Quotes eld
\end_inset
macros
\begin_inset Quotes erd
\end_inset
, with names such as
\family typewriter
<noun-main-p>
\family default
.
These macros are stand-ins for lists of disjuncts, often given equal weight,
but also not uncommonly assigned different costs.
In essence,
\family typewriter
<noun-main-p>
\family default
should be understood as an example of
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
for
\begin_inset Formula $g^{\prime}=\mbox{\left\langle noun\negthinspace-\negthinspace main\negthinspace-\negthinspace p\right\rangle }$
\end_inset
.
It appears multiple times throughout the file.
In one case, it is associated with the word-list
\family typewriter
words.n.2.s
\family default
, which makes sense, as
\family typewriter
<noun-main-p>
\family default
is describing one of the linkage behaviors of plural common nouns.
The contents of the file
\family typewriter
4.0.dict
\family default
should be understood to be a specification of
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
, although it is not so cleanly organized: it also includes all of the
\begin_inset Quotes eld
\end_inset
macros
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
and also includes word-lists when these are small.
\end_layout
\begin_layout Standard
A more careful examination of the use of the macros in
\family typewriter
4.0.dict
\family default
shows that these are often cascaded into one-another.
For example,
\family typewriter
<noun-main-s>
\family default
is used in the definition of
\family typewriter
<proper-names>,
\family default
\family typewriter
<entity-entire>
\family default
and
\family typewriter
<common-noun>
\family default
, each of which service word classes that are similar and yet differ syntactical
ly and semantically.
This is not just some strange artifact of hand-building a dictionary encoding
grammar.
It is
\emph on
prima facie
\emph default
evidence of important substructures inside of
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
, essentially pointing at the idea that
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
can be further factored into smaller, tightly-connected blocks;
\emph on
viz
\emph default
., that the graph of
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
contains strongly-coupled bipartite cliques.
\end_layout
\begin_layout Standard
This explicit co-clustering in Link Grammar is not driven by any sort of
theoretical arguments or foundation.
Rather, it is a natural, intuitive outcome of how the linguists who author
the dictionaries wish to tackle the problem.
A good factorization saves time and effort for the author, and is easier
to debug.
The urge to factorize is not limited to English: a look at any of the dictionar
ies shows this structure clearly.
It becomes even more pronounced in dictionaries with morphology, e.g.
in the Russian dictionaries, where word-stems (which carry most of the
meaning) are factored away from the suffixes (which provide the needed
tense, gender, number and person agreement across sentences).
\end_layout
\begin_layout Subsubsection
Tensor Product Factorization
\end_layout
\begin_layout Standard
The idea that
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
contains important substructures is important enough to point out a second
time.
Based on explicit experience with Link Grammar, those substructures are
likely to require a tensor product factorization (as opposed to a matrix
product factorization) to make sense of them.
Its possible to speculate that a Tucker factorization may provide a reasonable
first approximation to this factorization.
Nothing further on this can be said at this point, until a reliable way
to obtain a stable, reproducible and accurate
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
is in hand.
\end_layout
\begin_layout Subsubsection
Rank and Dimension
\end_layout
\begin_layout Standard
Based on the example of the actual English lexis in Link Grammar, there
is no need to assume that the number of word classes
\begin_inset Formula $\left|G\right|$
\end_inset
should somehow be equal to the number of syntactic usage patterns
\begin_inset Formula $\left|G^{\prime}\right|$
\end_inset
.
Indeed, the dimension of the matrix
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
has to be
\begin_inset Formula $\left|G\right|\times\left|G^{\prime}\right|$
\end_inset
; but these two dimensions are not known from any
\emph on
a priori
\emph default
principles.
\end_layout
\begin_layout Standard
More careful vocabulary is needed here: one can say that
\emph on
\begin_inset Formula $\left|G\right|$
\end_inset
\emph default
is the number of
\begin_inset Quotes eld
\end_inset
word classes
\begin_inset Quotes erd
\end_inset
.
The number of of syntactic usage patterns
\begin_inset Formula $\left|G^{\prime}\right|$
\end_inset
could be called the number of
\begin_inset Quotes eld
\end_inset
grammatical classes
\begin_inset Quotes erd
\end_inset
, although historic usage conflates these two terms.
Thus, the term
\begin_inset Quotes eld
\end_inset
syntactic classes
\begin_inset Quotes erd
\end_inset
for
\begin_inset Formula $G^{\prime}$
\end_inset
seems the most appropriate.
\end_layout
\begin_layout Standard
The number of word classes
\emph on
\begin_inset Formula $\left|G\right|$
\end_inset
\emph default
must surely be fairly high, as they must capture not only the predicate-argument
structure,
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Predicate,WP-Argument"
literal "true"
\end_inset
but the resulting syntax constraints must force the selection of the predicate-
argument structure.
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Selection"
literal "true"
\end_inset
Roughly speaking, the number of word classes should correspond to the number
of different synonym classes one might expect to find.
This is confused by the situation of common nouns: there are vast numbers
of these, and while most are not synonyms, most are syntactically interchangeab
le, even when forcing predicate-argument agreement.
\end_layout
\begin_layout Standard
The appropriate number of syntactic classes
\begin_inset Formula $\left|G^{\prime}\right|$
\end_inset
is presumably a lot lower.
At a minimum, it corresponds to the number of classical head-phrase structure
grammar non-terminals, such as
\family sans
S, NP, VP, PP, D, A, V, N,
\family default
\emph on
etc
\emph default
.
A more complete set can be found in the dependency grammar relations
\family sans
subj, obj, iobj, det, amod, advmod, psubj, pobj,
\family default
\emph on
etc
\emph default
.
but even this seems too low.
There are just over 100 different link types in Link Grammar, growing to
the thousands, when one considers various subtypes (subscripts).
However, the number of distinct macros in the English lexis provides a
different lower bound.
At any rate, the size of
\begin_inset Formula $\left|G^{\prime}\right|$
\end_inset
cannot be smaller than 100 for a realistic model of the English language,
and an accurate model is likely to require
\begin_inset Formula $\left|G^{\prime}\right|$
\end_inset
of at least a few thousand.
\end_layout
\begin_layout Subsubsection
Akaike Information Criterion
\end_layout
\begin_layout Standard
How many word classes and syntactic classes should there be? Aside from
making various
\emph on
a priori
\emph default
guesses, one can apply the Akaike information criterion (AIC).
Essentially, the grammatical classes can be taken as the parameters of
the model.
The AIC can be used as a guide to determine how many of them are required.
This is easy to say in principle; a computationally efficient mechanism
is not yet clear.
\end_layout
\begin_layout Subsubsection
Removing Ambiguity in Factorization
\end_layout
\begin_layout Standard
As noted in the earlier subsection, the ambiguity in the factorization can
be removed by hard clustering.
Practical experience with hands-on similarity measures in language data
indicate that there should not be much of a problem: most words that are
similar are obviously-so, using an appropriate pair-wise similarity function.
\end_layout
\begin_layout Standard
Suppose this was not easily the case? To guide the factorization, and to
maximize the sparsity of the left and the right factors, while maximizing
the complexity of the central factor, one can appeal to Tegmark's formulation
of Tononi integrated information as a guide.
That is, one wishes to factorize in such a way that the total amount of
integrated information in the left and right factors are minimized, while
the integrated information of the central factor is maximized.
\end_layout
\begin_layout Standard
In essence, factorization is a reorganization of the graph so as to always
maximize the integrated information of an important central core.
All edges where mutual information is weak are to be pruned away.
\end_layout
\begin_layout Subsubsection
Information Loss
\end_layout
\begin_layout Standard
The goal of the factorization is to minimize the information loss between
the input data and the factorization.
The objective function is then The Kullback-Leibler divergence, a minor
variant on the previous eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:KL-MI-factorization-loss"
\end_inset
:
\begin_inset Formula
\begin{equation}
MI_{Loss}=\sum_{w,d}p\left(w,d\right)\log_{2}\frac{p\left(w,d\right)}{\sum_{g\in G}\sum_{g^{\prime}\in G^{\prime}}p\left(w|g\right)p\left(g,g^{\prime}\right)p\left(d|g^{\prime}\right)}\label{eq:full-factor-loss}
\end{equation}
\end_inset
By minimizing this divergence, one minimizes the total loss incurred by
the factorization.
\end_layout
\begin_layout Standard
The above information loss estimate is identical to that described by Dhillon
\emph on
et al
\emph default
.
\begin_inset CommandInset citation
LatexCommand cite
key "Dhillon2003"
literal "true"
\end_inset
in their treatment of hard co-clustering.
That reference provides an extensive and detailed review of the factorization
problem being addressed in this section, with the exception that the current
need for word-sense disambiguation violates their hard-clustering assumption.
Words cannot be hard-clustered; word-vectors must be decomposed into word-sense
vectors first.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
Nonetheless, many formulas are still relevant, and the reference gives
detailed motivation for them, and provides multiple articulations and derivatio
ns.
Various results are recapped here.
\end_layout
\begin_layout Standard
For the special case of hard clustering, where each word or disjunct is
assigned to only one word class/grammatical class, one has that (eqn (6)
of Dhillon)
\begin_inset Formula
\begin{equation}
p\left(g,g^{\prime}\right)=\sum_{w\in g}\sum_{d\in g^{\prime}}p\left(w,d\right)\label{eq:central factor}
\end{equation}
\end_inset
From this, it follows that (eqn (4) of Dhillion)
\begin_inset Formula
\[
MI_{Loss}=MI\left(W,D\right)-MI\left(G,G^{\prime}\right)
\]
\end_inset
and so eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:full-factor-loss"
\end_inset
really is the information loss from factorization.
For hard clustering, the loss can be written in terms of only the left,
or the right clusters, so that (lemma 4.1 of Dhillon)
\begin_inset Formula
\begin{eqnarray*}
MI_{Loss} & = & \sum_{g}\sum_{w\in g}p\left(w,*\right)\sum_{d}p\left(d|w\right)\log_{2}\frac{p\left(d|w\right)}{p\left(d|g\right)}\\
& = & \sum_{g}\sum_{w\in g}\sum_{d}p\left(w,d\right)\log_{2}\frac{p\left(w,d\right)}{p\left(w,*\right)}\,\frac{p\left(g,*\right)}{p\left(g,d\right)}
\end{eqnarray*}
\end_inset
This allows an iterative algorithm to be performed, clustering only rows
(or only columns), that is, only words (or only disjuncts).
\end_layout
\begin_layout Subsubsection
Biclustering
\begin_inset CommandInset label
LatexCommand label
name "subsec:Biclustering"
\end_inset
\end_layout
\begin_layout Standard
It is worth reviewing the algorithm that Dhillion
\emph on
etal
\emph default
present.
It is an iterative hill-climbing algorithm, alternating between three steps:
the computation of marginals, and the assignment of new row clusters, and
the assignment of new column clusters.
The marginals are recomputed after every reclustering.
Dhillon provides a proof that, for hard clustering, the information loss
is monotonically decreasing; viz, that iteration always moves to a better
solution.
\end_layout
\begin_layout Standard
Given provisional cluster assignments
\begin_inset Formula $G$
\end_inset
and
\begin_inset Formula $G^{\prime}$
\end_inset
, so that every word and every disjuncts can be placed into some specific
cluster, all three factors
\begin_inset Formula $p\left(w,g\right)$
\end_inset
,
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
are available (are computable) given the cluster assignments.
The central factor is given by eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:central factor"
\end_inset
.
The left and right factors are obtained as marginals:
\begin_inset Formula
\[
p\left(w,g\right)=\begin{cases}
p\left(w,*\right) & \mbox{ if }w\in g\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
and
\begin_inset Formula
\[
p\left(g^{\prime},d\right)=\begin{cases}
p\left(*,d\right) & \mbox{ if }d\in g^{\prime}\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
The above are always known and well-defined, since, by assumption, the provision
al cluster assignments
\begin_inset Formula $G$
\end_inset
and
\begin_inset Formula $G^{\prime}$
\end_inset
are known at each step of the iteration.
The conditional probabilities are as noted before:
\begin_inset Formula
\[
p\left(w|g\right)=\frac{p\left(w,g\right)}{p\left(*,g\right)}
\]
\end_inset
and likewise
\begin_inset Formula
\[
p\left(d|g^{\prime}\right)=\frac{p\left(g^{\prime},d\right)}{p\left(g^{\prime},*\right)}
\]
\end_inset
where
\begin_inset Formula $p\left(*,g\right)=\sum_{w\in g}p\left(w,g\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},*\right)=\sum_{d\in g^{\prime}}p\left(g^{\prime},d\right)$
\end_inset
.
\end_layout
\begin_layout Standard
The new cluster assignments are obtained by minimizing the information loss,
once for the rows, and once for the columns.
In one step, one searches for cluster assignments
\begin_inset Formula $w\in g$
\end_inset
such that
\begin_inset Formula
\[
MI_{word\,loss}=\sum_{d}p\left(d|w\right)\log_{2}\frac{p\left(d|w\right)}{p\left(d|g^{\prime}\right)p\left(g^{\prime}|g\right)}
\]
\end_inset
is minimized.
After recomputing marginals, one then reclusters the disjuncts, by searching
for the clustering
\begin_inset Formula $d\in g^{\prime}$
\end_inset
that minimizes the loss
\begin_inset Formula
\[
MI_{disjunct\,loss}=\sum_{w}p\left(w|d\right)\log_{2}\frac{p\left(w|d\right)}{p\left(w|g\right)p\left(g|g^{\prime}\right)}
\]
\end_inset
This looks like an entirely reasonable algorithm, concrete and specific
and implementable, until one refers back to the table in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Sparsity"
\end_inset
.
There are in excess of
\begin_inset Formula $10^{5}$
\end_inset
words to provisionally assign to clusters, and
\begin_inset Formula $10^{7}$
\end_inset
or more disjuncts.
Each provisional clustering requires extensive re-computation of marginal
probabilities.
Exhaustive search for the best clustering clearly cannot scale to the current
datasets.
One might be able to make some forward progress by means of genetic algorithms,
as one is performing hill-climbing on a well-defined utility function.
The hard cluster membership can be encoded as a very long bit-string: this
is exactly the scenario for which genetic algorithms were designed to solve:
optimizing large bit strings, given a utility function on them.
\end_layout
\begin_layout Standard
But never mind: the assumption of hard clustering breaks word-sense disambiguati
on.
Genetic algorithms are not enough.
Back to the drawing board.
\end_layout
\begin_layout Subsubsection
Word-Sense Disambiguation
\begin_inset CommandInset label
LatexCommand label
name "subsec:Word-Sense-Disambiguation"
\end_inset
\end_layout
\begin_layout Standard
The primary issue with hard clustering is that it fails to correctly disentangle
different word senses.
There is an opportunity to do better.
\end_layout
\begin_layout Standard
A prototype example is given by the word
\begin_inset Quotes eld
\end_inset
saw
\begin_inset Quotes erd
\end_inset
.
It could be the noun, referring to the cutting tool; it could be the verb
synonymous to cutting; it could be the past tense of the verb
\begin_inset Quotes eld
\end_inset
to see
\begin_inset Quotes erd
\end_inset
.
The observational data consists of occurrence counts
\begin_inset Formula $N\left(\mbox{"saw"},d\right)$
\end_inset
.
The goal of word-sense disambiguation is to somehow factor this into three
grammatical classes
\begin_inset Formula $g$
\end_inset
, so that
\begin_inset Formula
\[
N\left(\mbox{"saw"},d\right)=N\left(\left\langle \mbox{tool}\right\rangle ,d\right)+N\left(\left\langle \mbox{cutting}\right\rangle ,d\right)+N\left(\left\langle \mbox{seeing}\right\rangle ,d\right)
\]
\end_inset
The general problem of how to accomplish this, and several tactics are discussed
in
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
.
That presentation focuses on cosine distances.
This section provides an information-theoretic variant.
\end_layout
\begin_layout Standard
The actual observed frequencies
\begin_inset Formula $p\left(w,d\right)$
\end_inset
are, by definition, sums of word
\begin_inset Formula $w$
\end_inset
used with every different possible word-sense
\begin_inset Formula $s_{k}$
\end_inset
that the word could have.
That is, explicitly, one has that
\begin_inset Formula
\[
p\left(w,d\right)=\sum_{k}p\left(s_{k},d\right)
\]
\end_inset
In poetry and in word-play, a word might be used in such a way that multiple
senses are simultaneously applied.
The assumption above is that this is not the case: that the text assigns
only a single meaning to each word use.
In any given use, the word
\begin_inset Quotes eld
\end_inset
saw
\begin_inset Quotes erd
\end_inset
is either a noun, or one of the verbs; it cannot be some mixture of all
of them.
\end_layout
\begin_layout Standard
Each word-sense can then be hard-clustered into a single grammatical category:
\begin_inset Quotes eld
\end_inset
saw
\begin_inset Quotes erd
\end_inset
-the-noun belongs to just one grammatical category, the one that holds synonyms
for cutting tools.
Thus, the hard-clustering formula applies:
\begin_inset Formula
\[
p\left(s,g\right)=\begin{cases}
p\left(s,*\right) & \mbox{ if }s\in g\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
The intent of the sense label
\begin_inset Formula $s$
\end_inset
is that it is uniquely associated with just one word, and no others.
The number of word-senses is strictly larger than the vocabulary: every
vocabulary word has at least one sense.
That is,
\begin_inset Formula $p\left(*,s\right)=p\left(w,s\right)$
\end_inset
holds for all
\begin_inset Formula $s\in w$
\end_inset
.
Thus, the conditional probability is
\begin_inset Formula
\[
p\left(w|s\right)=\frac{p\left(w,s\right)}{p\left(*,s\right)}=\begin{cases}
1 & \mbox{ if }s\in w\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
The decomposition of words into senses is then (restating the earlier formula
in slightly different notation:
\begin_inset Formula
\begin{eqnarray*}
p\left(w,d\right) & = & \sum_{s}p\left(w|s\right)p\left(s,d\right)\\
& = & \sum_{s\in w}p\left(s,d\right)
\end{eqnarray*}
\end_inset
To be consistent with the central factorization
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:central-decomposition"
\end_inset
, one must have
\begin_inset Formula
\[
\sum_{s\in w}p\left(s,g\right)=p\left(w,g\right)
\]
\end_inset
and
\begin_inset Formula
\[
\sum_{s\in w}p\left(s|g\right)=p\left(w|g\right)
\]
\end_inset
Since a word-sense is associated with just one word, the notation
\begin_inset Formula $\sum_{s\in w}$
\end_inset
is superfluous: one can unambiguously write
\begin_inset Formula $\sum_{s}$
\end_inset
as all other entries are zero.
\end_layout
\begin_layout Standard
The central factorization now has the form
\begin_inset Formula
\[
p\left(w,d\right)=\sum_{s}p\left(s,d\right)=\sum_{s}\sum_{g}\sum_{g^{\prime}}p\left(s|g\right)p\left(g,g^{\prime}\right)p\left(d|g^{\prime}\right)
\]
\end_inset
Not much has changed: the word-senses can now be legitimately hard-clustered;
but the decomposition of words into word-senses is unknown.
The clustering algorithm reviewed in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Biclustering"
\end_inset
is very nearly unaffected: one replaces the provisional clustering guesses
of
\begin_inset Formula $w\in g$
\end_inset
by provisional guesses
\begin_inset Formula $s\in w$
\end_inset
and
\begin_inset Formula $s\in g$
\end_inset
.
The feasibility of the algorithm is further challenged by the fact that
there are more word-senses than there are words, further increasing the
computational space.
\end_layout
\begin_layout Subsection
Graph Algorithms vs.
Gradient Descent
\end_layout
\begin_layout Standard
In the previous section, the Word2Vec style algorithms were characterized
as
\begin_inset Quotes eld
\end_inset
gradient descent algorithms
\begin_inset Quotes erd
\end_inset
, and were contrasted with
\begin_inset Quotes eld
\end_inset
graph algorithms
\begin_inset Quotes erd
\end_inset
that explicitly and overtly focus on the graphical relationships between
items.
The same contrast can be made here: clustering is a form of a graph algorithm,
whereas the matrix factorization algorithms are all driven by a form of
gradient descent.
\end_layout
\begin_layout Standard
The difference can be highlighted by noticing that cluster assignment is
essentially a form of greedy algorithm: One looks for the best-fitting
cluster, and accepts that first, effectively ignoring all of the other
clusters.
The relationship of word-to-cluster is explicit and overt; by contrast,
the matrix factorization is only implicit: a cluster relationship exists
whenever a matrix element is large.
\end_layout
\begin_layout Standard
In the current state of the art, the gradient-descent algorithms tend to
outperform the clustering algorithms, when the size of hidden layers is
limited to a computationally tractable size.
This can be interpreted in several ways: for small hidden layers, the clusterin
g algos just might be
\begin_inset Quotes eld
\end_inset
too greedy
\begin_inset Quotes erd
\end_inset
, applying too strong a discrimination.
Gradient descent algorithms also organize compute cycles differently, removing
certain repeated calculations out of a tight loop.
\end_layout
\begin_layout Standard
One advantage of the clustering approach is that, since it makes the graph
structure explicit, it provides a mechanism for controlling the shape of
the graph.
Another is that it seems to perhaps be more scalable, when the size of
the hidden layers are not suitably small.
\end_layout
\begin_layout Subsubsection
Control of Graphical Structure
\end_layout
\begin_layout Standard
The goal of the matrix factorization, illustrated in figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Factorization"
\end_inset
, is to not only obtain the three factors
\begin_inset Formula $p\left(w,g\right)$
\end_inset
,
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
and
\begin_inset Formula $p\left(g^{\prime},d\right)$
\end_inset
, but to obtain them such that the first and last components contain essentially
no bipartite cliques, and all of the structural complexity is limited to
\begin_inset Formula $M\left(g,g^{\prime}\right)$
\end_inset
.
A naive gradient descent does not seem to achieve this; it will provide
numerical values, but will not go out of its way to maximally set as many
of the
\begin_inset Formula $p\left(w,g\right)$
\end_inset
values to zero as possible.
In keeping with the general trend: the goal here is to set as many matrix
entries to zero as possible, thereby getting the greatest amount of data
compression as possible.
Yet, fidelity has to be maintained: just the right entries should be non-zero.
\end_layout
\begin_layout Standard
The point here is that it is the graph structure that is the most important;
the actual numerical values associated with each edge are far less important.
They are nice, and useful for improving accuracy and parse ranking, but
provide little insight in and of themselves.
The graph structure dominates.
This is made clear in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Factorization-in-Link"
\end_inset
, where a huge amount of progress can be made by means of manual factorization,
and setting all edge weights to essentially just one value: present or
absent.
\end_layout
\begin_layout Standard
Greedy clustering essentially provides a mechanism for controlling this
structure: it inherently limits the number of grammatical classes that
a word can belong to.
It dis-incentivizes the partitioning of a word into a large number of grammatic
al categories.
\end_layout
\begin_layout Subsection
TODO
\end_layout
\begin_layout Standard
This: PMI stuff.
\end_layout
\begin_layout Itemize
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski.
2016.
A latent variable model approach to pmi-based word embeddings.
TACL 4 (2016), 385–399.
\end_layout
\begin_layout Itemize
Tatsunori B Hashimoto, David Alvarez-Melis, and Tommi S Jaakkola.
2016.
Word embeddings as metric recovery in semantic spaces.
TACL 4 (2016), 273–286.
\end_layout
\begin_layout Standard
Arghhh.
\end_layout
\begin_layout Section
Factorizing the language model
\end_layout
\begin_layout Standard
The above developments now provide enough background to clearly state the
problem.
Inspired by the factorization of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorize"
\end_inset
, one wishes to find a collection of word classes, assigning words to a
handful of classes, according to the in-context word-sense.
The proper factorization needs to be of the form of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:central-decomposition"
\end_inset
, as illustrated in figure
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Factorization"
\end_inset
.
The appropriate measure of quality is to minimize the information loss
in the factorization, as given by eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:full-factor-loss"
\end_inset
.
\end_layout
\begin_layout Standard
More precisely, the factorization of the language model appears to require
three important ingredients:
\end_layout
\begin_layout Itemize
A way of decomposing word-vectors into sums of word-sense vectors,
\end_layout
\begin_layout Itemize
A way of performing biclustering, so as to split the bipartite graph
\begin_inset Formula $p\left(w,d\right)$
\end_inset
into left, central and right components, holding the left and right parts
to be sparse,
\end_layout
\begin_layout Itemize
Using an information-theoretic similarity metric, to preserve the probabilistic
interpretation of the contingency table
\begin_inset Formula $p\left(w,d\right)$
\end_inset
.
\end_layout
\begin_layout Standard
Combining all these parts in one go is daunting.
Smaller steps towards the ultimate goal can be taken.
One easy first step is to perform clustering using an information metric,
instead of the cosine distance.
This is done in the section below.
\end_layout
\begin_layout Standard
A second step is to replace hard clustering by an algorithm that treats
word-vectors as sums of (as yet unknown) distinct word senses.
Because this is a substantial topic in itself, this is handled in a distinct
tract; see
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
.
\end_layout
\begin_layout Subsection
Information-theoretic Clustering
\end_layout
\begin_layout Standard
The previous section uses the words
\begin_inset Quotes eld
\end_inset
information theoretic
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
clustering
\begin_inset Quotes erd
\end_inset
in close proximity.
This is a
\begin_inset Quotes eld
\end_inset
thing
\begin_inset Quotes erd
\end_inset
, and so a lighting review of the literature is warranted.
Two observations pop out:
\end_layout
\begin_layout Itemize
None of the systems described in the literature assume that the input data
can already be interpreted as a probability; rather, the clustering is
being performed on data naturally occurring in some Euclidean space, typically,
some space of low dimension (e.g.
two-dimensional image data).
\end_layout
\begin_layout Itemize
Most approaches to information-theoretic clustering use the mutual information
between members of a cluster and the cluster label.
Unfortunately, this has an ambiguity: the information content is conserved
by any Markov matrix that reassigns the cluster labels, so, for example,
a permutation matrix that just shuffles the cluster labels.
Ver Steeg
\emph on
et al.
\begin_inset CommandInset citation
LatexCommand cite
key "VerSteeg2014"
literal "true"
\end_inset
\emph default
propose a solution to this ambiguity: a return to first principles, requiring
that information loss due to coarse-graining be minimized.
\end_layout
\begin_layout Standard
Several other notable points are discussed below.
\end_layout
\begin_layout Subsubsection
Renyi Information Divergence
\end_layout
\begin_layout Standard
Gokcay and Principe
\begin_inset CommandInset citation
LatexCommand cite
key "Gokcay2002"
literal "true"
\end_inset
propose the Renyi entropy as an information divergence.
It is essentially minus the logarithm of the cosine metric.
Given two vectors
\begin_inset Formula $\vec{u}$
\end_inset
and
\begin_inset Formula $\vec{v}$
\end_inset
, the information divergence is defined as
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
D_{CEF}\left(\vec{u},\vec{v}\right)=-\log\cos\left(\vec{u},\vec{v}\right)=-\log\hat{u}\cdot\hat{v}=-\log\frac{\vec{u}\cdot\vec{v}}{\left\Vert \vec{u}\right\Vert \left\Vert \vec{v}\right\Vert }
\]
\end_inset
where
\begin_inset Formula $\left\Vert \cdot\right\Vert $
\end_inset
is the
\begin_inset Formula $l_{2}$
\end_inset
-norm.
Although this is widely cited in the literature pertaining to information-theor
etic clustering, there is no particular reason to believe that it offers
any advantage at all over the ordinary cosine metric, when applied to the
task of clustering grammatical categories.
In particular, it suffers from the same defects previously identified:
it contains an inbuilt assumption that the data presents in a Euclidean,
rotationally symmetric space, which is very much not the case for the language
data.
The vectors of in the contingency table that the language data is organized
in are not Euclidean vectors: they are joint probabilities.
They transform not under orthogonal rotations, but under Markov matrices.
\end_layout
\begin_layout Standard
There are also some practical, language-related reasons to lose interest
in the above information divergence: When examining actual language data,
as is done in
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017connectors"
literal "true"
\end_inset
, it becomes quite clear that there is a practical, common-sense cutoff
for similarity.
If two words
\begin_inset Formula $w_{1}$
\end_inset
and
\begin_inset Formula $w_{2}$
\end_inset
have a similarity of
\begin_inset Formula $\cos\left(w_{1},w_{2}\right)\lesssim0.5$
\end_inset
, they are very nearly unrelated; for a similarity of
\begin_inset Formula $\cos\left(w_{1},w_{2}\right)\lesssim0.1$
\end_inset
, they are fantastically unrelated.
It would be crazy to assign anything with such low similarities to a common
cluster.
Extending the notion of similarity to truly wee values, as the logarithm
enables, is meaningless.
For cosine values greater than 1/2, the logarithm is essentially linear:
\begin_inset Formula $-\log\cos\,x\approx1-\cos\,x$
\end_inset
in the region of interest.
The appearance of the logarithm does nothing to advance the situation.
\end_layout
\begin_layout Subsubsection
Consistency Under Coarse-graining
\end_layout
\begin_layout Standard
To deal with the problem of factorization ambiguity, Ver Steeg
\emph on
et al
\begin_inset CommandInset citation
LatexCommand cite
key "VerSteeg2014"
literal "true"
\end_inset
\emph default
revert to first principles, and propose that the information divergence
should be approximately invariant under the coarse-graining of the input
data.
\end_layout
\begin_layout Standard
There is some appeal in this idea for the language problem: a large cluster
of approximate synonyms should be factorisable into smaller clusters of
more tightly-related synonyms.
Conversely, one should be able to consolidate small blocks into bigger
ones, with a minimum of information loss.
However, based on the explorations in
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017connectors"
literal "true"
\end_inset
, this does not appear to be a problem that needs to be externally forced
onto the system.
Pair-wise word similarities seem to be of high quality; it would take some
work to have this wrecked by the clustering algorithm.
Still ...
additional consideration might be warranted.
\end_layout
\begin_layout Subsection
Information-driven Clustering
\end_layout
\begin_layout Standard
As shown by Ding
\emph on
et al
\begin_inset CommandInset citation
LatexCommand cite
key "Ding2005"
literal "true"
\end_inset
\emph default
and reviewed in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Clustering-as-Matrix"
\end_inset
,
\begin_inset Formula $k$
\end_inset
-means clustering can be seen as a special case of matrix factorizing.
This section generalizes to an information metric, as opposed to the usual
cosine metric.
The first subsection reviews the simpler single-sided form of clustering,
as it would be applied to just words, instead of the bipartite clustering.
The second subsection presents the information metric.
\end_layout
\begin_layout Subsubsection
Cosine clustering
\end_layout
\begin_layout Standard
The usual metric for judging similarity is the cosine metric:
\begin_inset Formula
\[
\cos\left(\vec{u},\vec{v}\right)=\hat{u}\cdot\hat{v}=\frac{\vec{u}\cdot\vec{v}}{\left\Vert \vec{u}\right\Vert \left\Vert \vec{v}\right\Vert }
\]
\end_inset
where
\begin_inset Formula $\left\Vert \cdot\right\Vert $
\end_inset
is the
\begin_inset Formula $l_{2}$
\end_inset
-norm.
If the input data is taken as a collection of (row) vectors, then the input
can be viewed as a matrix
\begin_inset Formula $X=\left[\vec{v}_{1},\vec{v}_{2},\cdots,\vec{v}_{n}\right]$
\end_inset
.
The product matrix
\begin_inset Formula $S=XX^{T}$
\end_inset
then has matrix entries
\begin_inset Formula $S_{ij}=\vec{v}_{i}\cdot\vec{v}_{j}$
\end_inset
.
If the vectors are already normalized, then the matrix entries
\begin_inset Formula $S_{ij}$
\end_inset
are just the cosine distances between
\begin_inset Formula $i$
\end_inset
and
\begin_inset Formula $j$
\end_inset
.
This is used to accomplish
\begin_inset Formula $k$
\end_inset
-means clustering by finding a
\begin_inset Formula $n\times k$
\end_inset
matrix membership indicator matrix
\begin_inset Formula $F$
\end_inset
such that the objective function
\begin_inset Formula
\[
U=\mbox{tr}F^{T}SF
\]
\end_inset
is minimized.
Some basic algebra (again, see
\begin_inset CommandInset citation
LatexCommand cite
key "Ding2005"
literal "true"
\end_inset
) shows that this is equivalent to minimizing the Frobenius norm
\begin_inset Formula
\[
U=\left\Vert X-FF^{T}\right\Vert ^{2}
\]
\end_inset
which in turn is identical to minimizing the distance between cluster centroids
\begin_inset Formula $\vec{m}_{i}$
\end_inset
and each member
\begin_inset Formula $j\in C_{i}$
\end_inset
of the
\begin_inset Formula $i$
\end_inset
'th cluster.
\begin_inset Formula
\[
U=\sum_{i=1}^{k}\sum_{j\in C_{i}}\left\Vert \vec{v}_{j}-\vec{m}_{i}\right\Vert ^{2}
\]
\end_inset
The centroid
\begin_inset Formula $\vec{m}_{i}$
\end_inset
is the arithmetic mean of all of the vectors in the
\begin_inset Formula $i$
\end_inset
'th cluster:
\begin_inset Formula
\[
\vec{m}_{i}=\frac{1}{\left|C_{i}\right|}\sum_{j\in C_{i}}\vec{v}_{j}
\]
\end_inset
where
\begin_inset Formula $\left|C_{i}\right|$
\end_inset
is the number of members in the
\begin_inset Formula $i$
\end_inset
'th cluster.
\end_layout
\begin_layout Subsubsection
Pair-wise Information Divergence
\end_layout
\begin_layout Standard
The cosine was built from the dot product
\begin_inset Formula $\vec{u}\cdot\vec{v}$
\end_inset
normalized by the vector lengths.
For information-based clustering, the normalization is changed, so as to
use the Kullback-Leibler divergence between the vector-pair, and the individual
vectors:
\begin_inset Formula
\[
MI\left(\vec{u},\vec{v}\right)=\log_{2}\frac{\vec{u}\cdot\vec{v}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\vec{v}_{i}\cdot\vec{v}_{j}\right)}{\left(\sum_{i=1}^{n}\vec{u}\cdot\vec{v_{i}}\right)\left(\sum_{j=1}^{n}\vec{v}_{j}\cdot\vec{v}\right)}
\]
\end_inset
This unusual-looking expression can be made more recognizable by changing
notation back to the joint probabilities
\begin_inset Formula $p\left(w,d\right)$
\end_inset
of observing word
\begin_inset Formula $w$
\end_inset
with disjunct
\begin_inset Formula $d$
\end_inset
(of course, this would also work if the disjunct
\begin_inset Formula $d$
\end_inset
was replaced by the
\begin_inset Formula $N$
\end_inset
-gram context of
\begin_inset Formula $w$
\end_inset
).
Write for
\begin_inset Formula $S_{ij}=\vec{v}_{i}\cdot\vec{v}_{j}$
\end_inset
in the equivalent form
\begin_inset Formula
\[
S\left(w_{1},w_{2}\right)=\sum_{d}p\left(w_{1},d\right)p\left(w_{2},d\right)
\]
\end_inset
The information divergence
\begin_inset Formula $MI\left(\vec{u},\vec{v}\right)$
\end_inset
is then
\begin_inset Formula
\[
MI\left(w_{1},w_{2}\right)=\log_{2}\frac{S\left(w_{1},w_{2}\right)S\left(*,*\right)}{S\left(w_{1},*\right)S\left(*,w_{2}\right)}
\]
\end_inset
where, as always, the stars
\begin_inset Formula $*$
\end_inset
denote the wild-card sums:
\begin_inset Formula
\[
S\left(w_{1},*\right)=\sum_{w_{2}}S\left(w_{1},w_{2}\right)
\]
\end_inset
By normalizing, one gets an expression that looks just like a joint probability:
\begin_inset Formula
\[
Q\left(w_{1},w_{2}\right)=\frac{S\left(w_{1},w_{2}\right)}{S\left(*,*\right)}
\]
\end_inset
with
\begin_inset Formula
\begin{equation}
MI\left(w_{1},w_{2}\right)=\log_{2}\frac{Q\left(w_{1},w_{2}\right)}{Q\left(w_{1},*\right)Q\left(*,w_{2}\right)}\label{eq:pairwise-info-divergence}
\end{equation}
\end_inset
Intuitively.
this can be thought of the information gain of bringing two vectors together,
as compared to the entire dataset of all other vectors.
\end_layout
\begin_layout Standard
This global aspect makes this function very different from the cosine distance.
The cosine distance is defined independently of all other vectors in the
system; it is independent of the number of other vectors, and the directions
in which they are pointing.
On could have a system with 42 vectors, or with 23 thousand of them: the
cosine metric doesn't care.
One could have a system with two vectors pointing one way, and another
six hundred pointing in the opposite direction: cosine doesn't care.
The pair-wise MI above compares two vectors, within the context of what
all of the other vectors in the system.
\end_layout
\begin_layout Standard
A different way to think of the pair-wise MI is that, by incorporating all
other vectors into its value, it is effectively attempting to spread all
of the (other) vectors into as uniform distribution as possible, magnifying
and expanding those regions where cosine would say there are lots of densely
packed vectors, while shrinking those regions where there is low density.
\end_layout
\begin_layout Standard
One way the above can be visualized is to consider two vectors, roughly
collinear, and another six hundred, also all roughly collinear, but almost
orthogonal to the first two.
Consider then the MI values for different pairs chosen from this collection.
Two vectors which might have the same cosine angle will have very different
MI values, in this kind of dataset.
\end_layout
\begin_layout Subsubsection
Scale invariance
\end_layout
\begin_layout Standard
The information divergence
\begin_inset Formula $MI\left(w_{1},w_{2}\right)$
\end_inset
is scale invariant: replacing
\begin_inset Formula $p\left(w,d\right)$
\end_inset
by
\begin_inset Formula $kp\left(w,d\right)$
\end_inset
for some constant
\begin_inset Formula $k$
\end_inset
does not alter the divergence.
In particular, replacing the joint probability
\begin_inset Formula $p\left(w,d\right)$
\end_inset
by the conditional probability
\begin_inset Formula $p\left(d|w\right)=p\left(w,d\right)/p\left(w,*\right)$
\end_inset
does not alter the information divergence.
\end_layout
\begin_layout Subsubsection
Arithmetic and Geometric Means
\end_layout
\begin_layout Standard
For vectors obtained from natural language, there is good reason to believe
that the natural clusters are convex, rather than being oddly shaped.
Therefore, it is meaningful to ask about and talk about the centroid of
a cluster.
\end_layout
\begin_layout Standard
For a Euclidean space, possessing rotational invariance and some notion
of uniform distribution, the arithmetic mean of the vectors in a cluster
would be a natural choice for the centroid.
However, as is being repeatedly noted, vectors taken from a joint probability
distribution do not live in a Euclidean, rotationally symmetric space.
The arithmetic mean does not make sense.
There are several candidates that are more suitable.
\end_layout
\begin_layout Standard
One is the geometric mean.
The centroid for word-cluster
\begin_inset Formula $g$
\end_inset
might be expressed by
\begin_inset Formula
\[
m\left(g,d\right)=\sqrt[\frac{1}{\left|g\right|}]{\prod_{w\in g}p\left(w,d\right)}
\]
\end_inset
This has the peculiar property that, if for any word
\begin_inset Formula $w$
\end_inset
in the cluster,
\begin_inset Formula $p\left(w,d\right)=0$
\end_inset
, then
\begin_inset Formula $m\left(g,d\right)=0$
\end_inset
.
The support for the vector
\begin_inset Formula $m\left(g,d\right)$
\end_inset
is the intersection of the supports for the vectors
\begin_inset Formula $p\left(w,d\right)$
\end_inset
.
In itself, this is not terribly objectionable or bad, but for one thing:
The
\begin_inset Formula $p\left(w,d\right)$
\end_inset
are observational frequencies, and are not theoretical distributions.
Thus, one might have that
\begin_inset Formula $p\left(w,d\right)=0$
\end_inset
simply because it has not been observed, and not because it is grammatically
forbidden.
This was already noted in section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Sparsity"
\end_inset
: contingency tables fundamentally cannot distinguish between rare linguistic
phenomena and grammatically forbidden phenomena.
The Zipfian distribution prohibits this.
\end_layout
\begin_layout Standard
One can imagine several work-arounds.
One would be to apply some form of kernel smoothing, or to apply some sort
of local regression.
How this might work is unclear.
Consider instead the logarithm of the geometric mean:
\begin_inset Formula
\begin{equation}
\log_{2}m\left(g,d\right)=\frac{1}{\left|g\right|}\sum_{w\in g}\log_{2}p\left(w,d\right)\label{eq:cluster mean}
\end{equation}
\end_inset
To be consistent with the previous expression, if
\begin_inset Formula $p\left(w,d\right)$
\end_inset
has not been observed, one should take
\begin_inset Formula $\log_{2}p\left(w,d\right)=-\infty$
\end_inset
.
From the missing-data perspective, it would actually be better to take
\begin_inset Formula $\log_{2}p\left(w,d\right)=0$
\end_inset
– missing observations contribute nothing.
Continuing in this vein of thinking, that infrequently-observed phenomena
are being unfairly punished and are not being given due weight, one might
consider the centroid to be described by
\begin_inset Formula
\[
\log_{2}m_{\alpha}\left(g,d\right)=\frac{1}{\left|g\right|}\sum_{w\in g}\left(\log_{2}p\left(w,d\right)\right)^{\alpha}
\]
\end_inset
for some
\begin_inset Formula $\alpha\le1$
\end_inset
, thus effectively making rare phenomena seem less rare, while common phenomena
become less common.
\end_layout
\begin_layout Standard
An intuitive feel for the geometric mean can be argued: probabilities can
only be added if they are truly independent, and here they are not; but
probabilities, taken as discrete events, can always be multiplied.
For a a probability distribution
\begin_inset Formula $P\left(X\right)$
\end_inset
on a space
\begin_inset Formula $X$
\end_inset
, the frequentist interpretation of probability is founded on individual
observations in the sequence space (aka the Cantor space)
\begin_inset Formula $X^{\omega}=X\times X\times\cdots$
\end_inset
that is the Cartesian product of an infinite number of copies of
\begin_inset Formula $X$
\end_inset
.
Frequentist probabilities are sigma-measures on the Borel set of cylinder
sets on the Cantor space.
Cylinder sets are the elements of the coarse topology on the product space.
Cylinder sets correspond to the limits of the pushout diagram
\begin_inset Formula $\centerdot\leftarrow\centerdot\rightarrow\centerdot$
\end_inset
that defines the Cartesian product.
\end_layout
\begin_layout Subsubsection
Agglomerative Clustering
\end_layout
\begin_layout Standard
The primary reason to propose a pair-wise information divergence is to enable
agglomerative clustering.
The reason for this was made clear earlier: the sheer scale and quantity
of data makes hill-climbing and gradient descent algorithms untenable.
The search space is simply too large.
\end_layout
\begin_layout Standard
As a corollary, the results of hill-climbing or gradient-descent algorithms
are insufficiently sparse; one wishes to approximate the sparsity that
hard-clustering offers, with less overhead and complexity in finding the
clusters.
\end_layout
\begin_layout Subsection
Word-Sense Disambiguation
\end_layout
\begin_layout Standard
The section
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Word-Sense-Disambiguation"
\end_inset
describes the general, global framework for discussing word-senses in the
factorization model.
The challenge of agglomerative clustering is to obtain some estimate of
word-sense assignments, given as a starting point the pairwise information
divergence of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pairwise-info-divergence"
\end_inset
.
This is where things start to get truly interesting.
\end_layout
\begin_layout Subsubsection
Mihalcea Algorithm
\end_layout
\begin_layout Standard
Rada Mihalcea describes a word-sense disambiguation algorithm
\begin_inset CommandInset citation
LatexCommand cite
key "Mihalcea2004,Mihalcea2005,Mihalcea2007"
literal "true"
\end_inset
that fits very naturally with the framework being discussed here.
However, it requires whole-sentence contexts.
For each instance
\begin_inset Formula $w_{j}$
\end_inset
of the
\begin_inset Formula $j$
\end_inset
'th word in a sentence, one assigns an (unknown) vector of word-senses
\begin_inset Formula $p\left(w_{j},s_{k}\right)$
\end_inset
with the set of possible senses
\begin_inset Formula $s_{k}$
\end_inset
given externally, as an
\emph on
a priori
\emph default
set, for example, taken from WordNet.
In addition, one also assumes an externally provided
\emph on
a priori
\emph default
measure of similarity
\begin_inset Formula $d\left(s_{k},s_{m}\right)$
\end_inset
of word-senses; again, this can be provided by WordNet.
One then considers the full graph clique of all possible word-senses that
might appear in the sentence, and their relation all other possible word-senses.
That is, one considers the graph
\begin_inset Formula $M\left(s_{k},s_{m}\right)$
\end_inset
with the
\begin_inset Formula $k$
\end_inset
and
\begin_inset Formula $m$
\end_inset
indexes corresponding to word-positions in the sentence; the matrix entries
are just
\begin_inset Formula $d\left(s_{k},s_{m}\right)$
\end_inset
normalized so that
\begin_inset Formula $M$
\end_inset
is a Markov matrix (Markov chain).
One then solves this chain to find the stationary vector
\begin_inset Formula $\pi$
\end_inset
.
This stationary vector can be interpreted as the desired word-sense assignment
\begin_inset Formula $p\left(w_{j},s_{k}\right)$
\end_inset
of the probability that the
\begin_inset Formula $j$
\end_inset
'th word has the
\begin_inset Formula $k$
\end_inset
'th sense.
\end_layout
\begin_layout Standard
The algorithm readily generalizes to any system that can provide logical
inference on concepts: one replaces the similarity-distance
\begin_inset Formula $d\left(s_{k},s_{m}\right)$
\end_inset
by the likelihood of some particular logical inference performed over the
sentence.
Taken over multiple sentences, this can provide anaphora resolution and
reference resolution.
\end_layout
\begin_layout Standard
The primary drawback of this algorithm is that the word senses must be externall
y supplied.
For this project, this is even a fatal drawback: the goal is to infer word-sens
es.
\end_layout
\begin_layout Subsubsection
Word-sense Similarity
\end_layout
\begin_layout Standard
Assume, for a moment, that distinct word senses can be inferred from raw
text, in an unsupervised fashion.
That is, assume that a joint probability
\begin_inset Formula $p\left(s,d\right)$
\end_inset
can be inferred from the text data.
It is OK if this probability is of low quality, and generally inaccurate:
disappointingly inaccurate, even.
If this probability exceeds pure random chance, then the Mihalcea algorithm
can be run
\begin_inset Quotes eld
\end_inset
in reverse
\begin_inset Quotes erd
\end_inset
, to infer the joint probabilities
\begin_inset Formula $p\left(s,s^{\prime}\right)$
\end_inset
between different senses
\begin_inset Formula $s$
\end_inset
and
\begin_inset Formula $s^{\prime}$
\end_inset
.
One does so by assuming that, given the specific words in a specific sentence,
that the word-senses between them are necessarily highly-related.
Given that the sentence can be parsed into a string of disjuncts
\begin_inset Formula $d$
\end_inset
, one can use
\begin_inset Formula $p\left(s,d\right)$
\end_inset
to assign a provisional probability
\begin_inset Formula $s$
\end_inset
to each word, and then collect observational statistics
\begin_inset Formula $N\left(s,s^{\prime}\right)$
\end_inset
on a sentence-by-sentence basis, incrementing
\begin_inset Formula $N$
\end_inset
by one for each observed pair
\begin_inset Formula $\left(s,s^{\prime}\right)$
\end_inset
in a sentence.
After observing a large number of sentences, one has a (sparse) database
of sense-pair frequencies
\begin_inset Formula $p\left(s,s^{\prime}\right)$
\end_inset
.
\end_layout
\begin_layout Standard
The goal of doing this is to amplify the signal-to-noise ratio.
This is in more-or-less complete analogy to the case for word-pairs: given
a small number of observations, they are noisy and inaccurate.
Increasing the number of observations causes the noise to cancel out, and
for a signal to emerge.
\end_layout
\begin_layout Standard
At this point, one can start doing some intriguing things: one can attempt
to perform maximum-spanning-tree parses, to determine how one given word-sense
is related to all other word-senses in a given sentence.
That is, one repeats the process of extracting disjuncts, but this time,
the connectors on the disjuncts are not words, but word-senses.
\end_layout
\begin_layout Standard
The reason for extracting sense-disjuncts is that they provide the doorway
to obtaining the
\begin_inset Quotes eld
\end_inset
Lexical Functions
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Lexical-function"
literal "true"
\end_inset
of Meaning-Text Theory (MTT).
\begin_inset CommandInset citation
LatexCommand cite
key "Mel'cuk1987,Kahane2003"
literal "true"
\end_inset
From there, one can extract the
\series bold
DSyntR
\series default
structure of a sentence, which provides the natural input into a reasoning
system based on formal logic.
That is, one can now begin to assemble logical proofs by inferring sequences
of deductions applied to sense-disjuncts.
Or rather, more importantly, once can now start to infer the set of valid
logical deductions that can be applied, rather than taking different forms
of logical inference as being given
\emph on
a priori
\emph default
.
To be more blunt: this provides the pathway for inferring the rules of
Goertzel's PLN, or for inferring the rules Pei Wang's Non-Axiomatic Logic,
rather than taking these rules as externally imposed.
\end_layout
\begin_layout Subsubsection
Word-sense Factoring
\end_layout
\begin_layout Standard
Given a pair-wise information divergence, how can one infer word senses?
This is addressed in the companion text.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
.
However, that text is currently written in terms of the cosine-distance;
it needs to be re-expressed using the information divergence, and, in particula
r, by the use of eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:cluster mean"
\end_inset
for the cluster mean.
\end_layout
\begin_layout Standard
So XXX TODO.
Unfinished things begin here.
\end_layout
\begin_layout Section
Unfinished Thoughts
\end_layout
\begin_layout Standard
Everything below here is incoherent and incomplete.
Sorry; under construction.
\end_layout
\begin_layout Subsubsection
Ising Model
\end_layout
\begin_layout Standard
Solving the Ising model by gradient descent can be done; a good way to do
this is by using message passing.
\begin_inset CommandInset citation
LatexCommand cite
key "Mezard2008"
literal "true"
\end_inset
This is a particularly quickly-convergent mean-field method.
The problem is that it fails to converge when the coupling is strong –
in other words, when the network is glassy (in the sense of
\begin_inset Quotes eld
\end_inset
spin glass
\begin_inset Quotes erd
\end_inset
).
The question: is language in a spin-glass state? Hypothesis: yes, it is.
Question: how can this be demonstrated?
\end_layout
\begin_layout Subsubsection
Surprisal Analysis
\end_layout
\begin_layout Standard
The basic idea is this formula:
\begin_inset Formula
\[
-\log\frac{P(x)}{P_{0}(x)}=\sum_{\alpha}\lambda_{\alpha}G\left(\alpha\right)
\]
\end_inset
The
\begin_inset Formula $G$
\end_inset
's are the constraints.
The
\begin_inset Formula $\lambda$
\end_inset
's are the Lagrange multipliers.
When there is only one
\begin_inset Formula $G$
\end_inset
, then it is conventionally called
\begin_inset Quotes eld
\end_inset
the energy
\begin_inset Quotes erd
\end_inset
, and the
\begin_inset Formula $\lambda$
\end_inset
is called
\begin_inset Quotes eld
\end_inset
the (inverse) temperature
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
There is a set of word-classes
\begin_inset Formula $C=\left\{ c\right\} $
\end_inset
and two projection matrices
\begin_inset Formula $\pi^{W}$
\end_inset
and
\begin_inset Formula $\pi^{D}$
\end_inset
such that
\begin_inset Formula $\vec{\eta}_{w}=\pi^{W}\hat{e}_{w}$
\end_inset
is a vector that classifies the word
\begin_inset Formula $w$
\end_inset
into one or more word-classes
\begin_inset Formula $c$
\end_inset
.
That is,
\begin_inset Formula $\vec{\eta}_{w}$
\end_inset
is a
\begin_inset Formula $C$
\end_inset
-dimensional vector.
In many cases, all but one of the entries in
\begin_inset Formula $\vec{\eta}_{w}$
\end_inset
will be zero: we expect the word
\begin_inset Formula $w=\mbox{the}$
\end_inset
to belong to only one class, the class of determiners.
By contrast,
\begin_inset Formula $w=\mbox{saw}$
\end_inset
has to belong to at least three classes: the past-tense of the verb
\begin_inset Quotes eld
\end_inset
to see
\begin_inset Quotes erd
\end_inset
, the noun for the cutting tool, and the verb approximately synonymous to
the verb for cutting.
The hand-built dictionary for English Link Grammar has over a thousand
distinct word-classes; one might expect a similar quantity from an unsupervised
algorithm.
\end_layout
\begin_layout Standard
The projection matrix
\begin_inset Formula $\pi^{D}$
\end_inset
performs a similar projection for the disjuncts.
That is
\begin_inset Formula $\vec{\zeta}_{d}=\pi^{D}\hat{e}_{d}$
\end_inset
, so that each disjunct is associated with a
\begin_inset Formula $C$
\end_inset
-dimensional vector
\begin_inset Formula $\vec{\zeta}_{d}$
\end_inset
.
Most of the entries in this vector will likewise be zero.
This vector basically states that any give disjunct is typically associated
with just one, or a few word classes.
So, for example, the disjunct
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
the-
\end_layout
\end_inset
is always associated with (the class of) common nouns.
The only non-zero entry in
\begin_inset Formula $\vec{\zeta}_{\mbox{the-}}$
\end_inset
.
will therefore be
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
<common-nouns>: the-;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Given these two projection matrices, the probability can then be decomposed
as an inner product:
\begin_inset Formula
\[
E\left(w,d\right)=\vec{\eta}_{w}\cdot\vec{\zeta}_{d}
\]
\end_inset
The word-classes
\end_layout
\begin_layout Section*
Sheaves
\end_layout
\begin_layout Standard
The previous section begins by stating that, ideally, one wants to wants
to model the probability
\begin_inset Formula $P\left(\mbox{sentence}\left|\mbox{ fulltext}\right.\right)$
\end_inset
, but due to the apparent computational intractability, one beats a tactical
retreat to computing
\begin_inset Formula $P\left(\mbox{word}\left|\mbox{ context}\right.\right)$
\end_inset
in the CBOW/SkipGram model, and something analogous in the Link Grammar
model.
However, by re-casting the problem in terms of disjuncts, however, one
can do better.
Dependency parsing allows one to easily create low-cost, simple computational
models for
\begin_inset Formula $P\left(\mbox{phrase}\left|\mbox{ context}\right.\right)$
\end_inset
or even
\begin_inset Formula $P\left(\mbox{sentence}\left|\mbox{ context}\right.\right)$
\end_inset
.
This is because disjuncts are compositional: they can be assembled, like
jigsaw-puzzle pieces, into larger assemblages.
If this is further enhanced with reference resolution, one has a direct
path towards a computationally tractable model of
\begin_inset Formula $P\left(\mbox{sentence}\left|\mbox{ fulltext}\right.\right)$
\end_inset
, with, at the outset, seemed hopelessly intractable.
\end_layout
\begin_layout Standard
TODO flesh out this section.
\end_layout
\begin_layout Standard
The important parts of the sheaves idea are already covered in the
\begin_inset Quotes eld
\end_inset
stitching
\begin_inset Quotes erd
\end_inset
paper.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
They need to be transcribed here.
\end_layout
\begin_layout Subsection*
Gluing axioms
\end_layout
\begin_layout Standard
The language-learning task requires one to infer the structure of language
from a small number of instances and examples.
Bengio
\emph on
etal.
\begin_inset CommandInset citation
LatexCommand cite
key "Bengio2003"
literal "true"
\end_inset
\emph default
describe this for continuous probabilistic models.
First, one imagines some continuous, uniform space.
Example sentences form a training corpus are associated with single points
in this space: the probability mass is initially located at a collection
of points.
One then imagines that generalization consists of smearing out those points
over an extended volume, thereby assigning non-zero probability weights
to other
\begin_inset Quotes eld
\end_inset
nearby
\begin_inset Quotes erd
\end_inset
sentences.
This suggests that there is a choice as to how this smearing-out is done:
one can spread the probabilities uniformly, in all
\begin_inset Quotes eld
\end_inset
directions
\begin_inset Quotes erd
\end_inset
, or one can preferentially spread probabilities only along certain directions.
Bengio suggests that higher-quality learning and generalization can be
achieved by finding and appropriately non-uniform way of smearing the probabili
ty masses from training.
\end_layout
\begin_layout Standard
This description seems like a useful and harmless way of guiding one's thoughts.
But it leaves open and vague several undefined concepts: that of the
\begin_inset Quotes eld
\end_inset
space
\begin_inset Quotes erd
\end_inset
: is this some topological space, perhaps linear, or something else? That
of
\begin_inset Quotes eld
\end_inset
nearby sentences
\begin_inset Quotes erd
\end_inset
: the presumption (the axiom?) that the space is endowed with a metric that
measures distances.
Finally, the concept of
\begin_inset Quotes eld
\end_inset
direction
\begin_inset Quotes erd
\end_inset
, or at least, a local tangent manifold at each point of the space.
It seems reasonable to assert that language lives on a manifold, but then,
the structure of that manifold needs to be elucidated and demonstrated.
In particular, the
\begin_inset Quotes eld
\end_inset
non-uniform spreading
\begin_inset Quotes erd
\end_inset
of probability weights suggests confusion or inconsistency: Perhaps the
spreading appears to be non-uniform, because the initial metric assigned
to the space is incorrect? In geometry, one usually works with normalized
tangent vectors, so that when one extends them to geodesics, each geodesic
moves with unit velocity.
It seems plausible to spread out probability weights the same way: spread
them uniformly, and adjust the shape of the underlying space so that this
results in a high-quality language model.
\end_layout
\begin_layout Section
Conclusion
\end_layout
\begin_layout Standard
A naive comparison of neural net and symbolic approaches to AI suggest that
these are entirely unrelated approaches, competing descriptions of observed
reality.
In fact, the two approaches are quite similar.
Neural nets are quite obviously linear and tensorial.
Symbolic systems are quite obviously graphical.
Taking a more abstract view, that of category theory, and specifically
that of monoidal categories, exposes the similarities.
\end_layout
\begin_layout Standard
Linear algebra, tensor algebra, Hilbert spaces, in any of their guises,
are known to be governed by symmetric monoidal categories.
\begin_inset CommandInset citation
LatexCommand cite
key "Baez2009"
literal "true"
\end_inset
Natural language has a long history of being described in algebraic and
categorial terms.
\begin_inset CommandInset citation
LatexCommand cite
key "Marcus1967"
literal "true"
\end_inset
The commonality between these two are the monoidal categories, necessarily
non-symmetric, as evinced by the pregroup grammars.
Grasping the non-symmetric monoidal structure in both reveals the commonality.
\end_layout
\begin_layout Standard
One can go farther: linearity and non-linearity commonly work hand-in-hand;
for example, curved manifolds have tangent vector spaces that are manifestly
linear.
There are many approaches to gluing together linear spaces to arrive at
curved structures; the formalism that seems to be the most appropriate
to graphical representations of knowledge is that of sheaf theory.
Small subsets of graphs: a vertex, and all of it's nearest neighbors, can
be stitched together to form a larger graph.
The vertex, and all of its nearest neighbors, is effectively just a Link
Grammar disjunct.
The stitching-together obeys the axioms of sheaf theory.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017sheaves"
literal "true"
\end_inset
Sheaves have long provided a useful, if rather abstract tool in other branches
of mathematics for assembling larger complex structures out of simpler,
easier to comprehend parts; it appears that they can also be used for knowledge
representation.
\end_layout
\begin_layout Standard
That appears to be the view from up-on-high.
Paying a bit more attention to the details, one is forced to reconcile
the concept of hill-climbing or gradient descent commonly used in neural-net
models, with the a statistical counting approach used in symbolic models.
Here, the apparent resolution is to understand that different practitioners
use different names for similar, if not identical concepts.
The “softmax model” of neural-net training appears to be nothing other
than a Markov model to statisticians, and a Gibbs measure to physicists.
The machine learning crowd looks at Gibbs measures, and defines Bayesian
networks (when not Markov networks) according to them, and calls the whole
idea the “principle of maximum entropy”.
A bit farther away, the physicists, chemists and biologists look at such
networks as a generalizing of Ising models, which have a well-described
perturbative field theory, and a much more poorly understood set of non-perturb
ative solutions.
What is missing from the entire enterprise seems to be a dictionary that
translates and crosses over argot and ideas used in different academic
fields, a cross-reference for language that describes the same thing.
This text attempts to provide some portion of that cross-over.
\end_layout
\begin_layout Standard
What can be learned by comparing different ways of talking about the same
thing? Perhaps the most important lesson learned in this text is the distinctio
n between cosine distance and mutual information.
When one works only with linear vector spaces, there is a very strong desire
to treat those spaces as having rotational symmetry.
This is only natural: physicists have known for many centuries that space
is rotationally symmetric; mathematicians state that the symmetry group
of real Euclidean space
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
is the special orthogonal rotation group
\begin_inset Formula $\mbox{SO}(\mathbb{R},n)$
\end_inset
.
Taking the inner product between vectors – the dot product, is natural.
The cosine distance follows naturally: it characterizes the geodesic distance
between points on the manifold of
\begin_inset Formula $\mbox{SO}(\mathbb{R},n)$
\end_inset
.
What seems not to have been asked, in many quarters, is whether real Euclidean
space
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
is the correct representation of the data? By comparing to statistical
techniques, ranging from statistical physics to machine learning to maximum
entropy, the answer seems to be no.
The systems under study do NOT live in
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
and the vectors are actually points in a space of probabilities.
Probabilities are described by a “vector”
\begin_inset Formula $\vec{p}=\left(p_{1},p_{2,}\cdots,p_{n}\right)$
\end_inset
, but this is not rotationally symmetric, first because
\begin_inset Formula $\sum_{i}p_{i}=1$
\end_inset
and because each of the
\begin_inset Formula $p_{i}$
\end_inset
must be greater than zero.
Yet the need to have something like the cosine distance between vectors
is overwhelming; the correct answer seems to be that the mutual information
plays that role.
If progress with linear models of data seems to be sometimes stalled, if
may very well be due to this one important detail.
\end_layout
\begin_layout Standard
A unified theory of semantic meaning based on graphical representations
does not yet exist.
Many important details remain unclear.
For natural language understanding, perhaps the most important step is
to get the details of word-sense similarity worked out correctly.
For the language learning project
\begin_inset CommandInset citation
LatexCommand cite
key "Goertzel2014"
literal "true"
\end_inset
, an attempt to apply these ideas has been described,
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2018stiching"
literal "true"
\end_inset
but the work remains incomplete.
A sensation exists that applying the principles described in this text
can go quite very far: unify gradient descent with statistical approaches
by means of monoidal categories and sheaves; consistently apply Gibbs-entropy
principles in such a framework, using mutual information as the proper
metric, and then factorize and dimensionally reduce to extract general
conclusions from specific commonly occurring examples.
The future seems bright.
\end_layout
\begin_layout Subsection*
Post-publication remarks
\end_layout
\begin_layout Standard
Since this was written, a paper by Lin, Tegmark & Rolnick
\begin_inset Quotes eld
\end_inset
Why does deep and cheap learning work so well?
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "Lin2017"
literal "false"
\end_inset
was brought to my attention.
After even the quickest skim, it appears to be in substantial agreement
with what I am trying to say, above.
It would seem to provide a suitable foundation on which to build.
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "lang"
options "tufte"
\end_inset
\end_layout
\end_body
\end_document