#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}
\usepackage{slashed}
%%% \usepackage{fontspec}
%%% \newfontfamily\DejaSans{DejaVu Sans}
\usepackage{tikzsymbols}
\end_preamble
\use_default_options false
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding utf8
\fontencoding global
\font_roman "times" "default"
\font_sans "helvet" "default"
\font_typewriter "cmtt" "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 true
\pdf_pdfborder true
\pdf_colorlinks true
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 0
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 0
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\listings_params "basicstyle={\ttfamily},basewidth={0.45em}"
\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
Factoring with Statistical Linguistics
\end_layout
\begin_layout Date
January 2023
\end_layout
\begin_layout Author
Linas Vepštas
\end_layout
\begin_layout Abstract
An attempt is made to develop a mathematical formalism for factoring large
language graphs into factors that have a symbolic interpretation.
The OpenCog language learning effort has been attempting to induce grammar,
syntax and semantics from corpora.
Most of this work is purely experimental,
\begin_inset Quotes eld
\end_inset
seat of the pants
\begin_inset Quotes erd
\end_inset
exploration.
This document attempts to provide a mathematical foundatation for that
work, thus perhaps making it clearer and easier to grasp.
\end_layout
\begin_layout Abstract
The primary focus is on exploring the nature of probability in extremely
high-dimensional spaces (
\begin_inset Quotes eld
\end_inset
hyperspaces
\begin_inset Quotes erd
\end_inset
), and how traditional linguistic ideas can be applied to factorize probability
distributions into components.
\end_layout
\begin_layout Section*
Introduction
\end_layout
\begin_layout Standard
A probabilistic description of natural language posits that probability
theory can be validly applied to word-sequences.
Given a sequence of words
\begin_inset Formula $\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
representing a sentence, a paragraph, or a longer text..., one make the
\emph on
a priori
\emph default
assumption that it is possible to assign a probability
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
to this sequence.
It is not philosophically or scientifically obvious that this is a valid
assumption: the collection of say-able sentences is presumably infinite;
language changes over time; ever human speaker internalizes slightly different
grammars and idiomatic expressions.
Vocabularies are different for technical texts and literary texts.
While it is true that present-day computers can gather up billions of sentences
by scraping the web, it can hardly be assumed that these are converging
to some overall stable probability distribution
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
.
Thus, assuming that
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
exists is intellectually dangerous.
\end_layout
\begin_layout Standard
None-the-less, we make this assumption, for two reasons.
First, it is useful.
Second, if a specific finite-sized corpus is selected and fixed, it is
a simple and unambiguous matter of counting words and phrases to obtain
frequency distributions.
However, even in this case, one should not be naive: the probability space
of of all sentences in a modest sized corpus is immense.
It would be nice if one could work with smaller factors.
Linguists have already exposed what these factors could be: nouns, verbs,
grammatical relationships.
One goal of this text is to formalize the relationship between grammar
and probability spaces, using mathematical notation rather than hot air.
It is hoped this will make things clearer.
Another goal is to extend this analysis into the domain of semantics and
\begin_inset Quotes eld
\end_inset
common sense
\begin_inset Quotes erd
\end_inset
.
This second goal won't be met, other than to suggest that exactly the same
methods that allowed low-level syntactic factorization to be performed,
can also be applied, again, at more abstract levels.
A third goal is to use this mathematical machinery to guide the development
of software for performing this analysis, to guide future experiments,
and to provide a better theoretical foundation for what has so far been
a seat-of-the-pants effort.
\end_layout
\begin_layout Subsection*
Parsing
\end_layout
\begin_layout Standard
The seat-of-the-pants effort so far has been focused on the automated extraction
of a grammar from a text corpus.
Issues of text segmentation are completely avoided: it is assumed that
the corpus consists of words, unambiguously separated by blank spaces.
These are avoided because segmentation is a deep, difficult and interesting
problem, and tackling it takes us afield.
Likewise, issues of morphology are also ignored.
Both of these are fundamentally important.
It is hoped (believed by the author) that the techniques described here
will also be applicable there.
But for now, its easiest to presume that there is a text corpus, consisting
of well-defined
\begin_inset Quotes eld
\end_inset
words
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
One statistical approach to parsing is to simply count word-pairs in the
sample corpus, and then to compute the pairwise point mutual information
\begin_inset Formula $MI\left(u,w\right)$
\end_inset
for all pairs.
This mutual information can be used to create a Maximum Spanning Tree (MST)
parse: to consider all possible trees spanning all words in a sentence
(or block of text) and then select the one that maximizes the grand total
MI, summed over the word-pairs in the tree.
It is also useful to consider the Maximal Planar Graph (MPG) parse: starting
with the MST tree, add edges to create cycles (loops), while still maximizing
the total MI.
That such MST parses correspond to reasonable linguistic structure has
been widely explored over several decades.
\end_layout
\begin_layout Standard
A grammar can be extracted by taking such MST/MPG parses and cutting each
edge in half, and retaining, as a
\begin_inset Quotes eld
\end_inset
connector label
\begin_inset Quotes erd
\end_inset
, what word that edge used to connect to.
The result of such chopping-up are the so-called
\begin_inset Quotes eld
\end_inset
disjuncts
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
jigsaw puzzle pieces
\begin_inset Quotes erd
\end_inset
of Link Grammar.
These can be reassembled again, to obtain syntactic parses of sentences.
Link Grammar works: there are extensive hand-curated dictionaries for English,
Russian and Thai, with smaller dictionaries for another dozen natural languages.
The English dictionary might be the most accurate/sophisticated parsing
system currently available.
\end_layout
\begin_layout Standard
Link Grammar grammars can be converted to other formalisms;
\emph on
e.g.
\emph default
Head-Phrase Structure Grammar (HPSG) and so on.
It can be shown that Link Grammar is
\begin_inset Quotes eld
\end_inset
isomorphic
\begin_inset Quotes erd
\end_inset
to Combinatory Categorial Grammars (CCG).
The quotes around
\begin_inset Quotes eld
\end_inset
isomorphic
\begin_inset Quotes erd
\end_inset
have less to do about the math, than what a typical linguist might find
acceptable in the mapping.
For the remainder of this text, we assume that any grammar formalism is
acceptable, and that they are all inter-convertible, interchangeable with
one another, at least weakly, if not strongly.
The goal of this text is to expose the relationship between statistics
and grammar, rather than to quibble the finer points of linguistics.
When the text below says things like
\begin_inset Quotes eld
\end_inset
a relationship
\begin_inset Formula $r\left(w_{1},w_{2},w_{3}\right)$
\end_inset
between three words
\begin_inset Formula $\left(w_{1},w_{2},w_{3}\right)$
\end_inset
\begin_inset Quotes erd
\end_inset
you are free to imagine any grammar formalism that you wish, involving
subjects, verbs and objects and so on.
However, Link Grammar will remain the touchstone, as it is the most compatible
with probability theory.
Thus, a general acquaintance with Link Grammar is strongly recommended.
\end_layout
\begin_layout Subsection*
Literature Review
\end_layout
\begin_layout Standard
The goal of the present text is to talk about the factorization of graphs,
in general.
There has been, of course, much related prior work.
Is it even possible to provide a literature review?
\end_layout
\begin_layout Standard
The idea of statistical parsing
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Statistical parsing"
target "https://en.wikipedia.org/wiki/Statistical_parsing"
literal "false"
\end_inset
.
\end_layout
\end_inset
has been around for decades.
Among the earliest work is Charniak's Maximum Entropy Parser.
\begin_inset CommandInset citation
LatexCommand cite
key "Charniak2000"
literal "false"
\end_inset
Better idea: just look at the Wikipedia article, instead.
\end_layout
\begin_layout Standard
The idea of matrix factorization is central to large consumer businesses,
who wish to estimate future shopping patterns as a function of prior behavior.
Vast numbers of papers have been written...
\end_layout
\begin_layout Standard
Hypervectors are a relatively newer approach to computing ...
\end_layout
\begin_layout Section*
Factorization
\end_layout
\begin_layout Standard
The notion of factorization is to take some large blob, and pick it apart
into components: to factor a matrix into block-diagonal components, to
factor an integer into primes.
Probability distributions over statistically independent variables factorize
trivially: this is what is meant by the words
\begin_inset Quotes eld
\end_inset
statistically independent
\begin_inset Quotes erd
\end_inset
.
Probability distributions over language are not, of course, statistically
independent, and thus are not strictly factorizable.
None-the-less, they are almost so; the goal is to identify the strongly
connected components and separate them from one-another, identifying the
weaker connections.
\end_layout
\begin_layout Standard
Lets try to capture this idea using mathematical notation.
To recap the story so far: Let
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
be the probability of observing
\begin_inset Formula $n$
\end_inset
words in a sentence (or block of text).
The space of sequences
\begin_inset Formula $\left\{ \left(w_{1},w_{2},\cdots,w_{n}\right)\right\} $
\end_inset
is a Cartesian product space, and
\begin_inset Formula $p$
\end_inset
is a measure upon that space.
\end_layout
\begin_layout Standard
The goal of factorization is to approximate this measure by factorizing
it into parts, where the parts are given by parsing via conventional linguistic
theory.
That is, we presume that relations
\begin_inset Formula $r_{i}$
\end_inset
between small sets of words can be found, such that the following holds,
approximately:
\begin_inset Formula
\[
p\left(w_{1},w_{2},\cdots,w_{n}\right)\approx p\left(r_{1}\left\{ w\right\} \right)p\left(r_{2}\left\{ w\right\} \right)\cdots p\left(r_{k}\left\{ w\right\} \right)
\]
\end_inset
where
\begin_inset Formula $r_{1},r_{2},\cdots,r_{k}$
\end_inset
are syntactic relations (subject, verb, object...) and the
\begin_inset Formula $\left\{ w\right\} $
\end_inset
are the set of words taking part in that particular relationship.
For example, the relation might be a subject-verb-object relationship;
the set
\begin_inset Formula $\left\{ w\right\} $
\end_inset
then consists of only three words.
The point here is that the
\begin_inset Formula $r_{i}$
\end_inset
are
\begin_inset Quotes eld
\end_inset
small
\begin_inset Quotes erd
\end_inset
, whereas
\begin_inset Formula $\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
is
\begin_inset Quotes eld
\end_inset
large
\begin_inset Quotes erd
\end_inset
.
The goal is to grapple with complexity be finding suitable recurring patterns.
Linguists have already shown what these patterns should be; now the task
is to actually extract them from text.
\end_layout
\begin_layout Standard
The factorization is successful if
\begin_inset Formula
\[
\log_{2}\frac{p\left(w_{1},w_{2},\cdots,w_{n}\right)}{p\left(r_{1}\right)p\left(r_{2}\right)\cdots p\left(r_{k}\right)}\approx0
\]
\end_inset
With such a factorization in hand, one can now aim for higher and more abstract
levels of structure, using the
\begin_inset Formula $r_{i}$
\end_inset
as the building blocks, rather than individual words.
One should imagine a perturbative structure, each level giving a foundation
for the next.
\end_layout
\begin_layout Subsection*
Example: the Binomial MI Formula
\end_layout
\begin_layout Standard
As a concrete example of the above, consider the mutual information
\begin_inset Formula $MI\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
over
\begin_inset Formula $n$
\end_inset
variables.
It is defined as
\begin_inset Formula
\begin{equation}
MI\left(w_{1},w_{2},\cdots,w_{n}\right)=\sum_{k=0}^{n}\left(-1\right)^{n-k}\sum_{w\backslash k}\log_{2}p\left(\left\{ w\backslash k\right\} \right)\label{eq:binomial-MI}
\end{equation}
\end_inset
where
\begin_inset Formula $\left\{ w\backslash k\right\} $
\end_inset
is the set of words
\begin_inset Formula $\left\{ w\right\} =\left\{ w_{1},w_{2},\cdots,w_{n}\right\} $
\end_inset
with
\begin_inset Formula $k$
\end_inset
of them removed.
The sum over
\begin_inset Formula $w\backslash k$
\end_inset
is a sum over every combinatoric possibility of removal.
By
\begin_inset Quotes eld
\end_inset
removed
\begin_inset Quotes erd
\end_inset
, it is meant
\begin_inset Quotes eld
\end_inset
summed over
\begin_inset Quotes erd
\end_inset
, so that, for example, if
\begin_inset Formula $w_{2}$
\end_inset
is removed, then
\begin_inset Formula
\[
p\left(\left\{ w\backslash w_{2}\right\} \right)=p\left(w_{1},*,w_{3},\cdots,w_{n}\right)=\sum_{w_{2}}p\left(w_{1},w_{2},w_{3},\cdots,w_{n}\right)
\]
\end_inset
The
\begin_inset Formula $*$
\end_inset
is the wild-card; it just denotes that
\begin_inset Quotes eld
\end_inset
anything
\begin_inset Quotes erd
\end_inset
can occupy that slot, and that, for probabilities, that slot should be
summed over.
Formally,
\begin_inset Formula $\left\{ w\backslash w_{2}\right\} =\left(w_{1},*,w_{3},\cdots,w_{n}\right)$
\end_inset
is called a
\begin_inset Quotes eld
\end_inset
cylinder set
\begin_inset Quotes erd
\end_inset
and
\begin_inset Formula $p\left(\left\{ w\backslash w_{2}\right\} \right)$
\end_inset
is a cylinder set measure.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\xout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset CommandInset href
LatexCommand href
name "Cylinder set"
target "https://en.wikipedia.org/wiki/Cylinder_set"
literal "false"
\end_inset
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\xout default
\uuline default
\uwave default
\noun default
\color inherit
and
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\xout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset CommandInset href
LatexCommand href
name "Cylinder set measure"
target "https://en.wikipedia.org/wiki/Cylinder_set_measure"
literal "false"
\end_inset
.
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\xout default
\uuline default
\uwave default
\noun default
\color inherit
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The sum over
\begin_inset Formula $w\backslash k$
\end_inset
for
\begin_inset Formula $k=1$
\end_inset
is then a sum over all possible wildcard locations, for a single wildcard:
\begin_inset Formula
\[
\sum_{w\backslash1}\log_{2}p\left(\left\{ w\backslash1\right\} \right)=\sum_{i=1}^{n}\log_{2}p\left(\left\{ w\backslash w_{i}\right\} \right)
\]
\end_inset
Likewise, for
\begin_inset Formula $k=2$
\end_inset
wildcards,
\begin_inset Formula
\[
\sum_{w\backslash2}\log_{2}p\left(\left\{ w\backslash2\right\} \right)=\sum_{i=1}^{n}\sum_{j=1;j\ne i}^{n}\log_{2}p\left(\left\{ w\backslash\left\{ w_{i},w_{j}\right\} \right\} \right)
\]
\end_inset
and so on.
\end_layout
\begin_layout Standard
The alternating sign is such that the singletons
\begin_inset Formula $p\left(w_{j}\right)=p\left(*,*,\cdots,w_{j},\cdots,*\right)$
\end_inset
always have a minus sign in front of their log, while the first term is
for the total space
\begin_inset Formula $p\left(\left\{ w\backslash w\right\} \right)=p\left(\left\{ \varnothing\right\} \right)=p\left(*,*,\cdots,*\right)$
\end_inset
.
If
\begin_inset Formula $p\left(\left\{ \varnothing\right\} \right)=1$
\end_inset
is a conventional probability, then of course
\begin_inset Formula $\log_{2}p\left(\left\{ \varnothing\right\} \right)=0$
\end_inset
.
However, this MI sum works just fine if
\begin_inset Formula $p\left(\left\{ \varnothing\right\} \right)\ne1$
\end_inset
.
For example, the binomial formula eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:binomial-MI"
plural "false"
caps "false"
noprefix "false"
\end_inset
still holds if
\begin_inset Formula $N$
\end_inset
a count is used instead of
\begin_inset Formula $p$
\end_inset
.
This is because the normalizing factor
\begin_inset Formula $N\left(\left\{ \varnothing\right\} \right)$
\end_inset
can be pulled back through all of the terms.
\end_layout
\begin_layout Standard
The size of the set
\begin_inset Formula $\left\{ w\backslash k\right\} $
\end_inset
is given by the binomial coefficient:
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Binomial coefficient"
target "https://en.wikipedia.org/wiki/Binomial_coefficient"
literal "false"
\end_inset
\end_layout
\end_inset
\begin_inset Formula
\[
\left|\left\{ w\backslash k\right\} \right|={n \choose k}
\]
\end_inset
Note the resemblance of the formula for MI to the binomial theorem.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Binomial Theorem"
target "https://en.wikipedia.org/wiki/Binomial_theorem"
literal "false"
\end_inset
\end_layout
\end_inset
This is not accidental; it is a generalization of the binomial formula
that holds for non-uniform intervals and non-independent correlations.
It reduces to exactly the binomial formula if all probabilities are independent
and uniform in size,
\emph on
i.e.
\emph default
if
\begin_inset Formula $p\left(a,b\right)=p\left(a\right)p\left(b\right)$
\end_inset
and if
\begin_inset Formula $p\left(w_{j}\right)=1/n$
\end_inset
.
In this case, it becomes
\begin_inset Formula
\begin{align*}
MI\left(w_{1},w_{2},\cdots,w_{n}\right)= & \sum_{k=0}^{n}\left(-1\right)^{n-k}{n \choose k}\log_{2}\frac{1}{n^{k}}\\
= & -\log_{2}n\cdot\sum_{k=0}^{n}\left(-1\right)^{n-k}k{n \choose k}\\
= & 0
\end{align*}
\end_inset
The last part follows from
\begin_inset Formula
\[
\frac{d}{dx}\left(1+x\right)^{n}=n\left(1+x\right)^{n-1}=\sum_{k=1}^{n}k{n \choose k}x^{k-1}
\]
\end_inset
and setting
\begin_inset Formula $x=-1$
\end_inset
.
\end_layout
\begin_layout Standard
More generally, the binomial-MI formula follows from the Cartesian-product
nature of the topology of sequences.
It is a formula that holds generically for cylinder set measures; there
is nothing language-specific in this example.
\end_layout
\begin_layout Standard
The point of this example is to show that something seemingly
\begin_inset Quotes eld
\end_inset
large
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
complex
\begin_inset Quotes erd
\end_inset
, such as
\begin_inset Formula $MI\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
can be reduced into smaller, perhaps more manageable components, which
can then be recombined back into the whole, with an exact (not approximate)
expression, a summation over pieces-parts.
\end_layout
\begin_layout Standard
But there is also a second lesson here: the binomial MI formula is not suitable
for natural language tasks.
Although it is an exact expression, and individual words and word pairs
appear in the lower summation terms, one gains no insight applying this
to natural language.
MI values can be both negative and positive; the alternating sign introduces
more chaos into the mix.
Basically, one has a series of small and large terms summing up and mostly
canceling one-another.
(Literally: try this experimentally, if possible.
You will find that the various MI's bounce around, getting large and small,
and that the sum is almost always smaller than the largest term.) The quest
is to find a similar expression, ideally, an exact expression, where most
of the terms are strictly positive.
This would allow the structure, the factorization to be approached perturbative
ly, as a strictly convergent sequence of corrections, each applied to the
last.
\end_layout
\begin_layout Subsection*
Example: Syntactic Factorization
\end_layout
\begin_layout Standard
Parses imply factorizations.
Consider a sentence with a fixed single parse.
Suppose that there is a location
\begin_inset Formula $i$
\end_inset
in this parse, such that when considering the block of all words to the
left of
\begin_inset Formula $i$
\end_inset
, and the block of all words to the right of
\begin_inset Formula $i$
\end_inset
, there is only a single edge connecting the two sides.
For example, this might be the edge connecting word
\begin_inset Formula $w_{i}$
\end_inset
, say, the verb, to word
\begin_inset Formula $w_{j}$
\end_inset
, say, the object.
(One cannot assume that
\begin_inset Formula $j=i+1$
\end_inset
since the object might have adjectives and determiners that precede it.
One should assume that
\begin_inset Formula $i<j$
\end_inset
.) Then this parse implies a factorization
\begin_inset Formula
\[
p\left(w_{1},w_{2},\cdots,w_{n}\right)\approx p\left(w_{1},\cdots,w_{i}\right)p\left(r\left\{ w_{i},w_{j}\right\} \right)p\left(w_{i+1},\cdots,w_{n}\right)
\]
\end_inset
The is, the likelihood of the block of words to the left is effectively
independent of the block of words on the right.
\end_layout
\begin_layout Standard
This factorization follows from the intuitive grammatical structure of natural
language.
Consider the sentence fragment
\begin_inset Quotes eld
\end_inset
On alternate Tuesdays, John goes ...
\begin_inset Quotes erd
\end_inset
How can it be completed? One imagines almost anything can complete it:
\begin_inset Quotes eld
\end_inset
...
fishing in Georgetown.
\begin_inset Quotes erd
\end_inset
\begin_inset Quotes eld
\end_inset
...
to the doctor.
\begin_inset Quotes erd
\end_inset
That is, the completion of the sentence seems independent of the start
of the sentence, and so the probability expression should factor like this
as well.
\end_layout
\begin_layout Standard
Yet, this is just an approximation.
Realizing that the first half of the sentence implies activity undertaken
by a human, then the last half of the sentence must be an activity that
humans can perform.
So there is a linkage, a connection between these two parts of the sentence
that extend beyond the grammatical relations between pairs of words.
So again: the proposal here is to first factor according to syntax, providing
a baseline, and then consider corrections to that initial factorization.
\end_layout
\begin_layout Standard
The above was written with a factor
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)$
\end_inset
specifically tying together the two specific words
\begin_inset Formula $w_{i},w_{j}$
\end_inset
connected by the parse edge.
This factor is made explicit because one imagines that the specific word-choice
connecting the left and right halves helps further isolate or make independent
these two halves.
In the example, it is presumed that
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)$
\end_inset
might capture at least some of the idea that the left side of the sentence
is about humans, and the right side is about human activities.
\end_layout
\begin_layout Standard
Note that
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)\ne p\left(w_{i},w_{j}\right)$
\end_inset
and that the probability depends on the relation
\begin_inset Formula $r$
\end_inset
.
That is, this factor is presumed to not be a simple word-pair co-occurrence
probability
\begin_inset Formula $p\left(\mbox{"goes"},\mbox{"fishing"}\right)$
\end_inset
, but also includes a weighting for this word-pair being an auxiliary-verb
pair.
This now gives a first hint of the appearance of semantics in a syntactic
discussion: The
\begin_inset Formula $p\left(w_{i},w_{j}\right)$
\end_inset
captures a syntactic relation between a pair of words; the
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)$
\end_inset
captures something more.
\end_layout
\begin_layout Standard
The notation
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)$
\end_inset
may feel strange; a more conventional approach would be to write this as
a conditional probability:
\begin_inset Formula $\left(w_{i},w_{j}\vert r\right)$
\end_inset
and read this as
\begin_inset Quotes eld
\end_inset
the pair
\begin_inset Formula $\left(w_{i},w_{j}\right)$
\end_inset
conditioned on the relation
\begin_inset Formula $r\left(w_{i},w_{j}\right)$
\end_inset
\begin_inset Quotes erd
\end_inset
.
But this seems awkward, and invites inappropriate applications of Bayes
theorem.
For the present case, the non-standard notation used here seems easier
to write and more direct to think about.
It can always be re-imagined as conditional probabilities, on an as-needed
basis.
\end_layout
\begin_layout Subsubsection*
Connectors and Disjuncts
\end_layout
\begin_layout Standard
Syntactic relations are not just pair-wise connections, though.
Syntactic elements have more complex structure.
Thus, the above factorization might be more correctly written as
\begin_inset Formula
\begin{align*}
p\left(w_{1},w_{2},\cdots,w_{n}\right)\approx & \left[p\left(w_{1},\cdots,w_{i}\right)\sqrt{p\left(r\left\{ w_{i},w_{j}\right\} \right)}\right]\times\\
& \qquad\qquad\left[\sqrt{p\left(r\left\{ w_{i},w_{j}\right\} \right)}p\left(w_{i+1},\cdots,w_{n}\right)\right]
\end{align*}
\end_inset
so that half of
\begin_inset Formula $p\left(r\left\{ w_{i},w_{j}\right\} \right)$
\end_inset
rides along with the left side, as the probability of making a connection,
and the other half rides with the other side.
This square root term
\begin_inset Formula
\[
\sqrt{p\left(r\left\{ w_{i},w_{j}\right\} \right)}
\]
\end_inset
can be referred to as the
\begin_inset Quotes eld
\end_inset
connector probability
\begin_inset Quotes erd
\end_inset
.
The
\begin_inset Quotes eld
\end_inset
connectors
\begin_inset Quotes erd
\end_inset
are then locations in the factorized tensor that have the potential to
make a connection.
This apportions the probability away from the actual connection, from the
actual linkage, and moves it to the two endpoints of the connection.
\end_layout
\begin_layout Standard
Of course, real grammatical relations are more complex; they are not just
a compendium of pair-wise relationships.
For example, a transitive verb
\emph on
must
\emph default
make a connection to both a subject on the left and an object on the right.
This is effectively a triple
\begin_inset Formula $\left(S,V,O\right)$
\end_inset
.
Any factorizations involving transitive verbs should be factored in terms
of a tri-variable
\begin_inset Formula $p\left(\mbox{TrVb}\left\{ S,V,O\right\} \right)$
\end_inset
.
A transitive verb
\begin_inset Formula $V$
\end_inset
has the possibility of connecting to a subject
\begin_inset Formula $S$
\end_inset
, and the possibility of connecting to an object
\begin_inset Formula $O$
\end_inset
.
\end_layout
\begin_layout Standard
This last paragraph is a sneaky introduction to Link Grammar.
The specific grammatical relation is
\begin_inset Formula $\mbox{TrVb}\left\{ S,V,O\right\} =\mathtt{V:S-\,\&\,O+}$
\end_inset
.
The right-hand side is the conventional Link Grammar notation stating that
the lexical entry
\begin_inset Formula $\mathtt{V}$
\end_inset
has the connector
\begin_inset Formula $\mathtt{S-}$
\end_inset
pointing to the left, and the connector
\begin_inset Formula $\mathtt{O+}$
\end_inset
pointing to the right.
The combined expression
\begin_inset Formula $\mathtt{S-\,\&\,O+}$
\end_inset
is called a
\begin_inset Quotes eld
\end_inset
disjunct
\begin_inset Quotes erd
\end_inset
; the name stems from it's being disjoined from other lexical entries for
the verb
\begin_inset Formula $\mathtt{V}$
\end_inset
.
\end_layout
\begin_layout Standard
The other sneaky thing being done above is to introduce the idea of a
\begin_inset Quotes eld
\end_inset
word class
\begin_inset Quotes erd
\end_inset
(subjects, verbs, objects).
Thus, during factorization, we expect to see indicator functions, such
as
\begin_inset Formula $p\left(w_{j}\in\mathtt{V}\right)$
\end_inset
which takes a value of 1 if
\begin_inset Formula $w_{j}$
\end_inset
is verb, and zero, otherwise.
Keep in mind, though, that it might be useful to assign fractional values
to
\begin_inset Formula $p\left(w_{j}\in\mathtt{V}\right)$
\end_inset
, for any number of technical reasons.
It is premature to sketch these reasons, just yet.
\end_layout
\begin_layout Standard
The intended factorization, for transitive verbs, is to say that a tri-variable
probability
\begin_inset Formula $p\left(\mbox{TrVb}\left\{ w_{i,}w_{j},w_{k}\right\} \right)$
\end_inset
can be factored into a a probability
\begin_inset Formula $p\left(w_{i}\in\mathtt{S+}\right)$
\end_inset
of
\begin_inset Formula $w_{i}$
\end_inset
belonging to some (any) class of words that can make subject-type connections,
a probability
\begin_inset Formula $p\left(w_{k}\in\mathtt{O-}\right)$
\end_inset
of
\begin_inset Formula $w_{k}$
\end_inset
belonging to some (any) class of words that can make object-type connections,
a probability
\begin_inset Formula $p\left(w_{j}\in\mathtt{V}\right)$
\end_inset
of
\begin_inset Formula $w_{j}$
\end_inset
belonging explicitly to the transitive verb class
\begin_inset Formula $\mathtt{V}$
\end_inset
, and an overall probability of observing the relation
\begin_inset Formula $p\left(\mathtt{V:S-\,\&\,O+}\right)$
\end_inset
.
How should this be written? The resulting factorization must be consistent
with the notion of
\begin_inset Quotes eld
\end_inset
connector probabilities
\begin_inset Quotes erd
\end_inset
.
It must also be consistent with the lexical entry
\begin_inset Formula $\mathtt{N:S+\,or\,O-}$
\end_inset
, which states that there is a word-class of common nouns that can act as
a subject, when to the left of a verb, or as an object, when to the right
of a verb.
But this is not the only such lexical entry with
\begin_inset Formula $\mathtt{S+}$
\end_inset
or with
\begin_inset Formula $\mathtt{O-}$
\end_inset
connectors: certainly, pronouns can make these connections as well.
This is the reason for writing
\begin_inset Formula $p\left(w_{i}\in\mathtt{S+}\right)$
\end_inset
instead of
\begin_inset Formula $p\left(w_{i}\in\mathtt{N}\right)$
\end_inset
: what matters is not that
\begin_inset Formula $w_{i}$
\end_inset
is a noun, but that
\begin_inset Formula $w_{i}$
\end_inset
can serve as the subject of a sentence.
\end_layout
\begin_layout Standard
One concludes that transitive verbs contribute a factor
\begin_inset Formula
\begin{align*}
p\left(\mbox{TrVb}\left\{ w_{i,}w_{j},w_{k}\right\} \right)= & p\left(\mathtt{V:S-\,\&\,O+}\right)\times\\
& \qquad p\left(w_{j}\in\mathtt{V}\right)p\left(w_{i}\in\mathtt{S+}\right)p\left(w_{k}\in\mathtt{O-}\right)\times\\
& \qquad\qquad\sqrt{p\left(\mathtt{S}\left\{ w_{i},w_{j}\right\} \right)p\left(\mathtt{O}\left\{ w_{j,}w_{k}\right\} \right)}
\end{align*}
\end_inset
where each of the first four
\begin_inset Formula $p$
\end_inset
's can be imagined to be zero or one, exactly, and a square-root probability
for each word participating in a specific linkage.
The square-root appears because there is a corresponding square root at
the other side of the link.
\end_layout
\begin_layout Standard
To complete the example, consider the case where the subject and object
are common nouns.
Then these are covered by the lexical entry
\begin_inset Formula $\mathtt{N:S+\,or\,O-}$
\end_inset
consisting of two disjoined disjuncts: one that says common nouns can act
as a subject:
\begin_inset Formula $\mathtt{N:S+}$
\end_inset
and another where they act as objects:
\begin_inset Formula $\mathtt{N:O-}$
\end_inset
.
That is, for the subject,
\begin_inset Formula
\[
p\left(\mbox{Subj}\left\{ w_{i,}w_{j}\right\} \right)=p\left(\mathtt{N:S+}\right)p\left(w_{i}\in\mathtt{N}\right)p\left(w_{j}\in\mathtt{S-}\right)\sqrt{p\left(\mathtt{S}\left\{ w_{i},w_{j}\right\} \right)}
\]
\end_inset
and similarly for the object.
A three-word sentence
\begin_inset Formula $\left(w_{1},w_{2},w_{3}\right)$
\end_inset
which has
\emph on
exactly one parse
\emph default
as SVO then has the probability
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
p\left(w_{1,}w_{2},w_{3}\right)=p\left(\mbox{Subj}\left\{ w_{1,}w_{2}\right\} \right)p\left(\mbox{TrVb}\left\{ w_{1,}w_{2},w_{3}\right\} \right)p\left(\mbox{Obj}\left\{ w_{2,}w_{3}\right\} \right)
\]
\end_inset
A longer sentence, say, one with adverbs, adjectives and determiners, having
a transitive verb will then have a block factor
\begin_inset Formula $p\left(w_{i,}w_{j},w_{k}\right)$
\end_inset
of this same form.
\end_layout
\begin_layout Standard
The goal here is to describe factorization along the lines of conventional
linguistic grammars.
Although an explicit Link Grammar notation is used, the arguments above
can be transposed to any grammatical theory.
The building blocks are simply the vertexes and edges that are drawn by
that grammatical theory.
The factorization above is two-fold.
First, a graph corresponding to the links drawn by a (single) parse in
that grammatical theory, in terms of grammatical classes, and an adjustment
for the actual words employed.
\end_layout
\begin_layout Subsubsection*
Phrase Structure
\end_layout
\begin_layout Standard
The descriptions above are primarily couched in a Dependency Grammar
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Dependency grammar"
target "https://en.wikipedia.org/wiki/Dependency_grammar"
literal "false"
\end_inset
.
\end_layout
\end_inset
setting.
A few words are in order about Chomsky-style production grammars, such
as Phrase-Structure Grammars
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Phrase sturcture grammar"
target "https://en.wikipedia.org/wiki/Phrase_structure_grammar"
literal "false"
\end_inset
.
\end_layout
\end_inset
.
Such grammars consist of production rules, the first of which is conventionally
\begin_inset Formula $S\to NP,S\backslash NP$
\end_inset
, stating that a sentence
\begin_inset Formula $S$
\end_inset
consists of a noun phrase
\begin_inset Formula $NP$
\end_inset
and the rest of the sentence
\begin_inset Formula $S\backslash NP$
\end_inset
.
This can be directly mapped to the assertion that
\begin_inset Formula
\[
p\left(w_{1},w_{2},\cdots,w_{n}\right)=p\left(NP\left\{ w_{1},\cdots,w_{i}\right\} \right)p\left(S\backslash NP\left\{ w_{i+1},\cdots,w_{n}\right\} \right)
\]
\end_inset
for some yet-to-be-determined word index
\begin_inset Formula $i$
\end_inset
.
Such phrase structure grammars are necessarily trees, as production rules
do not allow the creation of graphs with loops.
The leaves of these trees are necessarily the words in the (fully-parsed)
sentence.
These trees, however, are not strict dependency trees: they also have non-leaf
vertexes, labeled by the production rule that produced everything below.
This does nothing to change the overall conception of factorization: in
the example above, the factor
\begin_inset Formula $p\left(\mathtt{V:S-\,\&\,O+}\right)$
\end_inset
plays the same role as a production rule vertex.
\end_layout
\begin_layout Subsubsection*
Cliques and Spanning Trees
\end_layout
\begin_layout Standard
What if there are multiple parses? How should this be understood? In short,
as a many-worlds summation.
\end_layout
\begin_layout Standard
Given
\begin_inset Formula $n$
\end_inset
words in a sentence, consider first the clique or complete graph
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Complete graph"
target "https://en.wikipedia.org/wiki/Complete_graph"
literal "false"
\end_inset
.
\end_layout
\end_inset
of degree
\begin_inset Formula $n$
\end_inset
: this is the graph where every word, a vertex, is joined to every other
word by an edge.
A specific parse of the sentence then corresponds to a spanning tree
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Spanning tree"
target "https://en.wikipedia.org/wiki/Spanning_tree"
literal "false"
\end_inset
.
\end_layout
\end_inset
of this graph.
This tree can be described in terms of an indicator function
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Indicator function"
target "https://en.wikipedia.org/wiki/Indicator_function"
literal "false"
\end_inset
.
\end_layout
\end_inset
on the edges of the clique.
That is, make a list
\begin_inset Formula $\left\{ E\right\} $
\end_inset
of all of the edges
\begin_inset Formula $E$
\end_inset
in the complete graph, and then provide a function
\begin_inset Formula $\delta\left(E\right)$
\end_inset
that is zero or one on each edge.
A specific parse
\begin_inset Formula $T$
\end_inset
then corresponds to a specific indicator function
\begin_inset Formula $\delta_{T}:\left\{ E\right\} \to\left\{ 0,1\right\} $
\end_inset
.
As a block factorization, one has that
\begin_inset Formula
\[
p\left(T\left\{ w_{1},w_{2},\cdots,w_{n}\right\} \right)=\prod_{\left(w_{i},w_{j}\right)\in T}p\left(r\left\{ w_{i},w_{j}\right\} \right)
\]
\end_inset
where
\begin_inset Formula $T$
\end_inset
is the set of edges where the indicator function is one.
The per-edge factors
\begin_inset Formula $p\left(w_{i},w_{j}\right)$
\end_inset
may be indicator functions themselves, or may be weighted, or may be the
result of a more complex factorization, as described in the previous section.
That is, some of the pair-wise terms in the product should have been written
as triples or quads:
\begin_inset Formula
\begin{equation}
p\left(T\left\{ w_{1},w_{2},\cdots,w_{n}\right\} \right)=\prod_{r\in T}p\left(r\left\{ w_{i},w_{j},\cdots,w_{k}\right\} \right)\label{eq:factorization}
\end{equation}
\end_inset
\end_layout
\begin_layout Standard
If there is more than one possible parse of a sentence, then presumably
one parse is preferred over another, and each can be weighted, with some
probability
\begin_inset Formula $p\left(T\right)$
\end_inset
for each parse
\begin_inset Formula $T$
\end_inset
.
Each of these contributes to the overall analysis of the sentence:
\begin_inset Formula
\begin{equation}
p\left(w_{1},w_{2},\cdots,w_{n}\right)=\sum_{T\in\left\{ T\right\} }p\left(T\left\{ w_{1},w_{2},\cdots,w_{n}\right\} \right)\label{eq:summation}
\end{equation}
\end_inset
\end_layout
\begin_layout Standard
This summation implies that, in general,
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
probably cannot be factored into blocks, although each term in the sum
is explicitly block-factored.
It might happen that all parses have a common sub-block; in this case,
the sub-block can be pulled out of the summation, leaving only the ambiguous
part inside the summation.
Classic ambiguous parses are
\begin_inset Quotes eld
\end_inset
I saw the man with the telescope
\begin_inset Quotes erd
\end_inset
, and so on.
\end_layout
\begin_layout Subsubsection*
Deformation Retracts
\end_layout
\begin_layout Standard
In mathematics, Homotopy Theory
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Homotopy theory"
target "https://en.wikipedia.org/wiki/Homotopy_theory"
literal "false"
\end_inset
.
\end_layout
\end_inset
concerns the structure of spaces with non-trivial topologies.
In the present situation, the primary concern is how to work with graphs
that have cycles (loops) in them, as opposed to those that do not.
Trees are the prototypical example of a graph that has a trivial homotopy:
the edges can always be shortened, until the two end-points have been collapsed
into one.
This is termed a
\begin_inset Quotes eld
\end_inset
deformation retract
\begin_inset Quotes erd
\end_inset
.
In the present case, it can be understood to mean that the factorization
of a graph along an edge can be written as if the edge has shrunk to a
point.
Explicitly:
\begin_inset Formula
\begin{align*}
p\left(w_{1},\cdots,w_{i}\right)p\left(r\left\{ w_{i},w_{j}\right\} \right) & p\left(w_{i+1},\cdots,w_{j},\cdots,w_{n}\right)=\\
& \quad p\left(w_{1},\cdots,K\right)p\left(K\right)p\left(w_{i+1},\cdots,K,\cdots,w_{n}\right)
\end{align*}
\end_inset
where a new kind of
\begin_inset Quotes eld
\end_inset
word
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $K$
\end_inset
has been introduced.
It's a compound word, a multi-word expression, a set phrase, a phraseme,
an idiomatic expression, an institutional expression.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Phraseme"
target "https://en.wikipedia.org/wiki/Phraseme"
literal "false"
\end_inset
and
\begin_inset CommandInset href
LatexCommand href
name "Multiword expression"
target "https://en.wikipedia.org/wiki/Multiword_expression"
literal "false"
\end_inset
and
\begin_inset CommandInset href
LatexCommand href
name "Idiom"
target "https://en.wikipedia.org/wiki/Idiom"
literal "false"
\end_inset
.
\end_layout
\end_inset
Collections of words can be
\begin_inset Quotes eld
\end_inset
retracted
\begin_inset Quotes erd
\end_inset
, congealed down to single lexical units.
\end_layout
\begin_layout Subsubsection*
Twines
\end_layout
\begin_layout Standard
A more problematic situation arises for graphs that have cycles.
Although conventional phrase-structure and and dependency parses are trees,
loops can appear in dependency parses.
The very simplest case would be an HSV parse, where H is the left-wall
or head of the parse, S is the subject, a noun, and V is a verb: this forms
a triangle: there are three edges.
H is used to indicate both the dominant noun (the subject) and also the
dominant verb.
\end_layout
\begin_layout Standard
Perhaps this can be seen more clearly in dependent or relative clauses.
An example from the Link Grammar documentation:
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See the Link Grammar Guide-to-Links
\begin_inset CommandInset href
LatexCommand href
name "Section R"
target "https://www.abisource.com/projects/link-grammar/dict/section-R.html"
literal "false"
\end_inset
,
\begin_inset CommandInset href
LatexCommand href
name "Section B"
target "https://www.abisource.com/projects/link-grammar/dict/section-B.html"
literal "false"
\end_inset
,
\begin_inset CommandInset href
LatexCommand href
name "Section S"
target "https://www.abisource.com/projects/link-grammar/dict/section-S.html"
literal "false"
\end_inset
, and
\begin_inset CommandInset href
LatexCommand href
name "Section C"
target "https://www.abisource.com/projects/link-grammar/dict/section-C.html"
literal "false"
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
+--B------+
\end_layout
\begin_layout Plain Layout
+-R-+--S--+
\end_layout
\begin_layout Plain Layout
| | |
\end_layout
\begin_layout Plain Layout
The dog I chased was black
\end_layout
\end_inset
\end_layout
\begin_layout Standard
In the above the R link points at the head noun of the relative clause;
the B link connects to the head verb of the relative clause, and the S
link is the conventional subject-verb link.
Loops may be larger than triangles:
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
+-----B------+
\end_layout
\begin_layout Plain Layout
+-R--+C-+-S--+
\end_layout
\begin_layout Plain Layout
| | | |
\end_layout
\begin_layout Plain Layout
The dog who I chased was black
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The C link connects head nouns to subordinating conjunctions.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wiktionary,
\begin_inset CommandInset href
LatexCommand href
name "subordinating conjunction"
target "https://en.wiktionary.org/wiki/subordinating_conjunction"
literal "false"
\end_inset
.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Such loops present a potential complication to factoring.
In order to factor a block of text into a left and a right component, there
are now two links to be cut.
There are several ways in which to imagine this issue.
One is to presume that the relative clause is an irreducible block of the
form
\begin_inset Formula
\[
p\left(\mbox{RelCl}\left\{ w_{i},w_{j};w_{k},w_{m}\right\} \right)
\]
\end_inset
with
\begin_inset Formula $i,j$
\end_inset
linking to the left-hand block and
\begin_inset Formula $k,m$
\end_inset
linking to the right.
In the last example, it would be
\begin_inset Formula $w_{i}=\mathtt{dog}$
\end_inset
,
\begin_inset Formula $w_{j}=\mathtt{who}$
\end_inset
,
\begin_inset Formula $w_{k}=\mathtt{I}$
\end_inset
and
\begin_inset Formula $w_{m}=\mathtt{chased}$
\end_inset
, so that the entire loop of the relative clause is unreduced, and has four
connectors grand-total, emanating from it:
\end_layout
\begin_layout Standard
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/loop-4-legs.eps
width 17text%
\end_inset
\begin_inset VSpace defskip
\end_inset
\end_layout
\begin_layout Standard
Alternately, this loop is clearly composed four three-point vertexes and
so following the earlier conventions, there is a pair probability for each
linkage (there are four links: R,B,C and S), a square-root for each exposed
connector (there are two: D for determiner, and S), and a vertex factor
for each vertex:
\begin_inset Formula
\begin{align*}
p\left(\mbox{RelCl}\left\{ w_{i},w_{j};w_{k},w_{m}\right\} \right)= & p\left(\mathtt{R}\left\{ w_{i},w_{j}\right\} \right)p\left(\mathtt{C}\left\{ w_{j},w_{k}\right\} \right)\times\\
& \qquad p\left(\mathtt{S}\left\{ w_{k},w_{m}\right\} \right)p\left(\mathtt{B}\left\{ w_{i},w_{m}\right\} \right)\times\\
& \qquad p\left(\mbox{Vertex}\right)\times\\
& \qquad\sqrt{p\left(\mathtt{D}\left\{ \mathtt{the},w_{i}\right\} \right)p\left(\mathtt{S}\left\{ w_{i,}\mathtt{was}\right\} \right)}
\end{align*}
\end_inset
the factors of which follows from the fuller diagram:
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
+----------S-------+
\end_layout
\begin_layout Plain Layout
+------B------+ |
\end_layout
\begin_layout Plain Layout
+-D-+-R-+-C-+--S--+ |
\end_layout
\begin_layout Plain Layout
| | | | | |
\end_layout
\begin_layout Plain Layout
the dog who I chased was black
\end_layout
\end_inset
\end_layout
\begin_layout Standard
In order to not clog the above, the vertex factor was separated out:
\begin_inset Formula
\begin{align*}
p\left(\mbox{Vertex}\right)= & p\left(\mathtt{who:R-\,\&\,C+}\right)\times\\
& \quad p\left(\mathtt{I:C-\,\&\,S+}\right)\times\\
& \quad p\left(\mathtt{chased:S-\,\&\,B-}\right)\times\\
& \quad p\left(\mathtt{dog:D-\,\&\,R+\,\&\,B+\,\&\,S+}\right)
\end{align*}
\end_inset
As before, the individual word-mentions could have been pulled out into
grammatical classes, so that, for example:
\begin_inset Formula
\[
p\left(\mathtt{chased:S-\,\&\,B-}\right)=p\left(\mathtt{chased}\in\mathtt{V}\right)p\left(\mathtt{V:S-\,\&\,B-}\right)
\]
\end_inset
and so on.
\end_layout
\begin_layout Subsubsection*
Summary
\end_layout
\begin_layout Standard
In this way, and ordinary seven-word sentence
\begin_inset Quotes eld
\end_inset
the dog I chased was black
\begin_inset Quotes erd
\end_inset
, having a joint probability
\begin_inset Formula $p\left(w_{1},\cdots,w_{7}\right)$
\end_inset
can be factored into independent blocks.
This factorization is more complex than a conventional Hidden Markov Model,
and properly should be called a Markov random field.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Hidden Markov model"
target "https://en.wikipedia.org/wiki/Hidden_Markov_model"
literal "false"
\end_inset
,
\begin_inset CommandInset href
LatexCommand href
name "Markov random field"
target "https://en.wikipedia.org/wiki/Markov_random_field"
literal "false"
\end_inset
and
\begin_inset CommandInset href
LatexCommand href
name "Bayesian network"
target "https://en.wikipedia.org/wiki/Bayesian_network"
literal "false"
\end_inset
.
\end_layout
\end_inset
We stop short of calling this a Bayesian Network, because we've stopped
short of using any Bayesian priors
\begin_inset Formula $p\left(\theta\right)$
\end_inset
, nor of combining them with likelihoods
\begin_inset Formula $p\left(x\vert\theta\right)$
\end_inset
to obtain posteriors
\begin_inset Formula $p\left(\theta\vert x\right)\sim p\left(x\vert\theta\right)p\left(\theta\right)$
\end_inset
.
\end_layout
\begin_layout Standard
One reason to avoid Bayesian priors is to instead allow the use of Gibbs
measure
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Gibbs measure"
target "https://en.wikipedia.org/wiki/Gibbs_measure"
literal "false"
\end_inset
.
\end_layout
\end_inset
and so to rephrase the probabilities in terms of entropies (or free energies):
\begin_inset Formula
\[
p\left(x_{i}\right)=\frac{1}{Z}e^{-\beta_{i}E_{i}}
\]
\end_inset
This also distinguishes the graphs here from the concept of Conditional
Random Fields
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Conditional random field"
target "https://en.wikipedia.org/wiki/Conditional_random_field"
literal "false"
\end_inset
.
\end_layout
\end_inset
which are conventionally formulated in terms of priors.
Another reason to avoid Bayesian formulations is the problem of ambiguity,
sketched below.
\end_layout
\begin_layout Subsubsection*
Many Worlds
\end_layout
\begin_layout Standard
The factorizations being described above are
\emph on
not those of maximum entropy approaches
\emph default
!
\emph on
Nor are they Bayesian
\emph default
! We must now be careful not to discard the baby with the bathwater: most
of the equations above are a stream of bathwater; the baby is eqn.
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:summation"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
That is, we are
\emph on
not pursing a singular and best parse
\emph default
(arrived by via MaxEnt or via Bayesian inference.) The goal is to explicitly
avoid a single model.
Avoid some Bayesian distribution over likelihoods.
The central and key idea that we are struggling to expose is that one must
insist that all of the various likelihoods are not only possible, but are
intertwined.
There is no one true reality that is merely unknown and needs to be found
out; there are many, and they are necessarily tangled together.
\end_layout
\begin_layout Standard
Perhaps this sounds like philosophical quantum woo.
It is not meant to be; it needs to be unpacked.
Linguistics is relatively arid, but there are a few examples: again , the
classic
\begin_inset Quotes eld
\end_inset
I saw the man with the telescope.
\begin_inset Quotes erd
\end_inset
In a spy thriller, perhaps the protagonist is looking through the telescope.
In the biography of a famous astronomer, the protagonist may be standing
in an observatory.
Without that context, it is ambiguous.
\begin_inset Quotes eld
\end_inset
Ah ha!
\begin_inset Quotes erd
\end_inset
you may say,
\begin_inset Quotes eld
\end_inset
but eventually it becomes clear, one or the other! And we can update our
priors when it becomes clear!
\begin_inset Quotes erd
\end_inset
.
Alas, it will never become clear.
I will not tell you which context I am actually thinking of; you will be
left hanging.
I won't tell you, not because I'm secretive or coy, but because this is
a meta-conversation about linguistics and not about telescopes.
In this situation, it is fundamentally impossible for you to update your
priors.
\end_layout
\begin_layout Standard
Poetry provides a richer example: what was the poet thinking, when he, she,
wrote those verses? What did they want you, the reader, to think? A good
poet will want you to think of a multitude of things, to feel many emotions,
all at once, at the same time.
The name of the game is not to update our Bayesian priors and select one
and only one emotion on which we will fiercely focus (unless, of course,
it is nationalistic poetry
\begin_inset ERT
status open
\begin_layout Plain Layout
{
\backslash
dSmiley
\backslash
nolinebreak
\backslash
dSmiley}
\end_layout
\end_inset
).
\end_layout
\begin_layout Standard
More broadly, ambiguity is primal to common sense: our visual field is filled
with a myriad of items, a rainbow of events and happenings.
There's (usually) no particular reason for focus attention on one or another;
the brain, in default mode, wanders across the field of possibilities.
A mathematical formulation of AGI must also capture this freedom to wander
about.
And yet, also, some things are distinct.
Distinctness is captured in eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorization"
plural "false"
caps "false"
noprefix "false"
\end_inset
: my coffee cup is distinct from my coffee.
The world of possibilities is captured in eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:summation"
plural "false"
caps "false"
noprefix "false"
\end_inset
: there are many and they compete with one-another.
\end_layout
\begin_layout Standard
If one is given only the string
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
and the task of factoring it, then sure, use eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factorization"
plural "false"
caps "false"
noprefix "false"
\end_inset
and be prepared to lose, whenever there are any admixtures of anything
else in there.
But there always will be admixtures of something else! Those admixtures
cloud the factors, because the admixtures are entangled into the total.
In the end, all language is necessarily poetry, an artful attempt to capture
vague thoughts and set them into words, in such a way that someone else
might happen upon them, and perhaps extract something meaningful, perhaps
what the author meant, and yet unavoidably unclear, because the author
was never precise enough, and the reader was never clever enough to understand.
This is the human condition.
\end_layout
\begin_layout Standard
To reiterate: the goal here is both to factor, to obtain factors that are
relatively unambiguous, and then at the same time, bracket the ambiguities
so that they are each corralled in their own paddock, and can be recombined
as needed.
This need is what makes the machinery daunting.
\end_layout
\begin_layout Standard
Although neuroscientists will eventually find the neurological basis for
human ambiguity, the origin of ambiguity is not the human mind.
Ambiguity is fundamental, in nature, as it stands.
This is the message delivered by eqn.
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:binomial-MI"
plural "false"
caps "false"
noprefix "false"
\end_inset
and eqn.
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:summation"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
\end_layout
\begin_layout Subsection*
MST Factorization
\end_layout
\begin_layout Standard
The sections above provide theoretical arguments.
Let quickly review the experimental situation.
The Yuret-style MST factorization being used in the language-learning effort
is effectively the presumption that
\begin_inset Formula
\[
MI\left(w_{1},w_{2},\cdots,w_{n}\right)\approx\sum_{\left(w_{i},w_{j}\right)\in MST}MI\left(w_{i},w_{j}\right)
\]
\end_inset
This sum runs only over the maximum spanning tree, and contains only
\begin_inset Formula $n-1$
\end_inset
links.
The corresponding complete graph would have
\begin_inset Formula $n\left(n-1\right)/2$
\end_inset
links in it, and so most of these are ignored.
Specifically, the presumption is that these ignored links actually cancel
higher-order terms in the full MI expansion.
\end_layout
\begin_layout Standard
Put more plainly, it appears that
\begin_inset Formula
\[
\log_{2}\frac{p\left(w_{1},w_{2},\cdots,w_{n}\right)}{p\left(w_{1}\right)p\left(w_{2}\right)\cdots p\left(w_{n}\right)}
\]
\end_inset
is, in general,
\begin_inset Quotes eld
\end_inset
freakishly high
\begin_inset Quotes erd
\end_inset
, and that much of it can be
\begin_inset Quotes eld
\end_inset
knocked down to size
\begin_inset Quotes erd
\end_inset
by using the MST, instead.
\end_layout
\begin_layout Standard
Lacking is a coherent theoretical argument as to
\emph on
why
\emph default
an MST parse provides a reasonable approximation to the factorization.
Also lacking is any comprehensive experimental exploration comparing the
full, formal factorization to the MST approximation.
Gut feel implies that MST is OK or even
\begin_inset Quotes eld
\end_inset
pretty good
\begin_inset Quotes erd
\end_inset
, but no one has characterized the structure of the difference
\begin_inset Formula
\[
\Delta_{MST}\left(w_{1},w_{2},\cdots,w_{n}\right)=MI\left(w_{1},w_{2},\cdots,w_{n}\right)-\sum_{\left(w_{i},w_{j}\right)\in MST}MI\left(w_{i},w_{j}\right)
\]
\end_inset
\end_layout
\begin_layout Standard
When is
\begin_inset Formula $\Delta$
\end_inset
small? When is it large? What does it mean, when it is large? Are there
tricks that can describe such deviations?
\end_layout
\begin_layout Standard
The next step is, of course, to use disjuncts: a Link Grammar parse, resulting
in word-disjunt pairs
\begin_inset Formula $MI\left(w_{i},d_{i}\right)$
\end_inset
.
A basic premise here is that
\begin_inset Formula
\[
\Delta_{LG}\left(w_{1},w_{2},\cdots,w_{n}\right)<\Delta_{MST}\left(w_{1},w_{2},\cdots,w_{n}\right)
\]
\end_inset
where
\begin_inset Formula $\Delta_{LG}$
\end_inset
is the disjunctive parse:
\begin_inset Formula
\[
\Delta_{LG}\left(w_{1},w_{2},\cdots,w_{n}\right)=MI\left(w_{1},w_{2},\cdots,w_{n}\right)-\sum_{\left(w_{i},d_{i}\right)\in LG}MI\left(w_{i},d_{i}\right)
\]
\end_inset
However, this is a premise, a hypothesis, a
\begin_inset Quotes eld
\end_inset
gut feel
\begin_inset Quotes erd
\end_inset
.
That
\begin_inset Formula $\Delta_{LG}<\Delta_{MST}$
\end_inset
must be true is a foundation-stone of the last seventy years of the linguistics
of natural language.
Linguistics is
\begin_inset Quotes eld
\end_inset
nothing more
\begin_inset Quotes erd
\end_inset
than the filling in of details of exactly how this works, in various special
cases.
What is lacking is any clear mathematical argument about why the disjuncts
provide a good approximation to the higher order terms in the sum of binomial-M
I equation
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:binomial-MI"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
\end_layout
\begin_layout Standard
More precisely, the binomial-MI equation is correct, but unwieldy, because
it contains large canceling terms.
What is unclear is why these terms cancel, and how to best obtain a diagonalize
d, factorized perturbative expansion.
The MST->disjunct path is just a gut-feel approach to obtaining that perturbati
ve expansion.
It lacks formal justification for why it works.
\end_layout
\begin_layout Section*
Factorization as Dimensional Embedding
\end_layout
\begin_layout Standard
Syntax alone is not enough to convey the meaning of an expression, and so
the above approximations, of working with parses, are necessarily mediocre.
The factorization we are groping for should more properly be written as
a change of variable
\begin_inset Formula
\[
p\left(w_{1},w_{2},\cdots,w_{n}\right)\approx p\left(r_{1},r_{2},\cdots,r_{k}\right)
\]
\end_inset
where the variables
\begin_inset Formula $r_{1},r_{2},\cdots,r_{k}$
\end_inset
are in some sense
\begin_inset Quotes eld
\end_inset
more independent
\begin_inset Quotes erd
\end_inset
than the word-sequence
\begin_inset Formula $w_{1},w_{2},\cdots,w_{n}$
\end_inset
.
\end_layout
\begin_layout Standard
Note that in general,
\begin_inset Formula $k\ne n$
\end_inset
.
For spanning tree parses, the
\begin_inset Formula $r_{i}$
\end_inset
are understood to be links between word-pairs, and so
\begin_inset Formula $k$
\end_inset
is counting the number of links in the parse.
Thus
\begin_inset Formula $k=n-1$
\end_inset
for word-pair relationships.
If the parse has fundamental cycles (loops), then
\begin_inset Formula $k=n-1+\ell$
\end_inset
where
\begin_inset Formula $\ell$
\end_inset
is the number of fundamental cycles (
\emph on
e.g.
\emph default
in an MPG parse).
\end_layout
\begin_layout Standard
Note that parsing performs a
\begin_inset Quotes eld
\end_inset
dimensional oxidation
\begin_inset Quotes erd
\end_inset
: there are far more
\begin_inset Formula $r_{i}$
\end_inset
's than there are
\begin_inset Formula $w_{i}$
\end_inset
's.
If the size of the base vocabulary is
\begin_inset Formula $\mathcal{O}\left(\left|w\right|\right)\sim N$
\end_inset
then
\begin_inset Formula $\mathcal{O}\left(\left|r\right|\right)\sim N^{2}$
\end_inset
where I'm using
\begin_inset Formula $\mathcal{O}$
\end_inset
notation because counting the size of the vocabulary is hard, when vocabulary
words have a Zipfian distribution.
Also, the claim that
\begin_inset Formula $\mathcal{O}\left(\left|r\right|\right)\sim N^{2}$
\end_inset
is somewhat misleading.
Its actually more like
\begin_inset Formula $\mathcal{O}\left(\left|r\right|\right)\sim N^{\gamma}$
\end_inset
for some
\begin_inset Formula $\gamma<2$
\end_inset
because this is what the Zipfian distributions do to us.
We've seen this experimentally, when we measure the sparsity and rarity,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See e.g.
page 34 or Diary Part Five for rarity.
I could have sworn I had this in other tables, but I can't find it right
now.
\end_layout
\end_inset
but we haven't explicitly measured this.
\end_layout
\begin_layout Standard
Thus, MST parsing is a form of dimensional embedding, where the strings
living in the relatively low-dimensional space
\begin_inset Formula $\mathcal{O}\left(\left|\left(w_{1},w_{2},\cdots,w_{n}\right)\right|\right)\sim N^{n}$
\end_inset
are embedded into the vastly larger space
\begin_inset Formula $\mathcal{O}\left(\left|r_{1},r_{2},\cdots,r_{k}\right|\right)\sim N^{2k}$
\end_inset
.
\end_layout
\begin_layout Standard
In Link Grammar parsing, the embedding is not into a word-pair space, but
into a disjunct space, which is explosively larger.
That is, the relations
\begin_inset Formula $r$
\end_inset
are actually disjuncts
\begin_inset Formula $d$
\end_inset
.
I assume its
\begin_inset Formula $\mathcal{O}\left(\left|d\right|\right)\sim N^{\gamma}$
\end_inset
for some
\begin_inset Formula $\gamma>2$
\end_inset
, but again, we've monitored this size without actually ever measuring it's
scaling dependence.
This is an experimental to-do: got to fix that.
\end_layout
\begin_layout Subsection*
Paths in hyperspace
\end_layout
\begin_layout Standard
Lets try to paint a mental image of this.
Consider a vector space of dimension
\begin_inset Formula $N$
\end_inset
, with
\begin_inset Formula $N$
\end_inset
the size of the vocabulary.
Each
\begin_inset Formula $w_{k}$
\end_inset
is then a unit vector
\begin_inset Formula $e_{k}$
\end_inset
in this space.
The word-sequence
\begin_inset Formula $w_{1},w_{2},\cdots,w_{n}$
\end_inset
is a path in this space.
The probabilities
\begin_inset Formula $p\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
are hard to factorize, because there are many of these paths, and they
overlap a lot.
\end_layout
\begin_layout Standard
Consider now a vector space of dimension
\begin_inset Formula $D$
\end_inset
, with
\begin_inset Formula $D$
\end_inset
being the number of disjuncts.
Very roughly,
\begin_inset Formula $D\sim N^{\gamma}$
\end_inset
for some
\begin_inset Formula $\gamma>2$
\end_inset
or something like that.
So this is a much larger space.
A single Link Grammar parse of a sentence
\begin_inset Formula $S=\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
provides a unique sequence of disjuncts
\begin_inset Formula $G=\left(d_{1},d_{2},\cdots,d_{n}\right)$
\end_inset
fixed by that parse.
As before,
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
specifies a path through the disjunct space.
However, this time, the space is much larger, and so the accidental intersectio
n of two different paths is much less likely.
There's disambiguation.
\end_layout
\begin_layout Standard
Another difference is that the path
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
is constrained.
A syntactically valid path
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
is necessarily one where
\emph on
all
\emph default
of the connectors on all of the disjuncts
\begin_inset Formula $d_{i}$
\end_inset
in that path are fully connected.
Other paths are simply not valid.
This stands in sharp contrast to word sequences
\begin_inset Formula $w_{1},w_{2},\cdots,w_{n}$
\end_inset
which are unconstrained: one is free to write any word-sequence, even if
it's nonsense.
\end_layout
\begin_layout Subsection*
Metric spaces
\end_layout
\begin_layout Standard
The space of words is endowed with several metrics.
One of the simplest ones is given by the word-pair MI.
Fixing a word
\begin_inset Formula $w$
\end_inset
, consider the vector
\begin_inset Formula $\vec{w}$
\end_inset
of length
\begin_inset Formula $2N$
\end_inset
, whose vector components are given by
\begin_inset Formula $x_{j}=MI\left(w,w_{j}\right)$
\end_inset
for
\begin_inset Formula $j<N$
\end_inset
and by
\begin_inset Formula $x_{j}=MI\left(w_{j},w\right)$
\end_inset
for
\begin_inset Formula $N\le j<2N$
\end_inset
.
That is, using entirely conventional notation, write
\begin_inset Formula $\vec{w}=\sum_{j}x_{j}\hat{e}_{j}$
\end_inset
with the
\begin_inset Formula $x_{j}$
\end_inset
being just real numbers, and the
\begin_inset Formula $\hat{e}_{j}$
\end_inset
being the unit basis vector for the vector space.
\end_layout
\begin_layout Standard
Experimentally, it has been seem that the distribution of the MI of word-pairs
is approximately Gaussian, perhaps even to a surprising degree.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Diary part Five, Part Nine, the 2008 word-pairs report and also the
AGI 2022 paper.
\end_layout
\end_inset
This implies that the word vectors
\begin_inset Formula $\vec{w}$
\end_inset
are uniformly randomly distributed on a unit sphere: that is, the word-vectors
form a Gaussian Orthogonal Ensemble (GOE).
Because these vectors are distributed on a sphere, the cosine distance
between the vectors can be used as a metric.
Intuitively, this metric judges two words to be similar, when they have
similar neighbors.
\end_layout
\begin_layout Standard
This is not the only such metric.
One can construct a different word-pair MI, from disjuncts.
This is obtained by considering a pair-wise correlation
\begin_inset Formula $f\left(w_{i},w_{j}\right)=\sum_{d}p\left(w_{i},d\right)p\left(w_{j},d\right)$
\end_inset
and then constructing an MI from
\begin_inset Formula $f$
\end_inset
.
The sum over
\begin_inset Formula $d$
\end_inset
is the sum over disjuncts.
This, too, appears to be described by a GOE.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is reviewed in Diary Part Eight, if I recall correctly.
\end_layout
\end_inset
Intuitively, this metric judges two words to be similar, when they appear
in similar grammatical contexts.
This is a bit stronger and more constrained than saying the words have
similar neighbors: they must also be grammatically similar.
Experimentally, these two different distances are correlated; I don't have
r-values offhand.
\end_layout
\begin_layout Standard
Presumably, the metric obtained from disjuncts is semantically more accurate,
although we don't have any way of measuring semantic similarity.
\end_layout
\begin_layout Subsection*
Nearby paths
\end_layout
\begin_layout Standard
These word-pair metrics, together with disjunct sequences, provide an opportunit
y to explore similar sentences.
Given a grammatically correct sentence
\begin_inset Formula $w_{1},w_{2},\cdots,w_{n}$
\end_inset
one can now explore other nearby words to obtain other sequences.
In general, though, these other nearby strings will not be grammatically
correct.
Several possibilities exist.
One is to just sample such sequences, parse them, and hope to stumble across
a sequence that parses.
\end_layout
\begin_layout Standard
A more clever approach is to start with the path
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
, as this is already grammatically correct.
For any fixed
\begin_inset Formula $d_{i}$
\end_inset
, one then examines the set of words
\begin_inset Formula
\[
\left\{ w\vert\left(w,d_{i}\right)\mbox{ exists}\right\}
\]
\end_inset
and order these according to the cosine distance between
\begin_inset Formula $w$
\end_inset
and
\begin_inset Formula $w_{i}$
\end_inset
.
The result is then necessarily a grammatically correct sentence.
In fact, it will have exactly the same parse as the original sentence.
This is perhaps overly strict: it turns into an exercise of finding synonyms
that can work as drop-in syntactic replacements.
By necessity, the resulting sentence will also be of exactly the same length,
as only a word-for-word substitution is done.
BTW, this assumes that connectors have been classified into grammatical
classes, as otherwise the set
\begin_inset Formula $\left\{ w\vert\left(w,d_{i}\right)\mbox{ exists}\right\} $
\end_inset
will contain exactly one element.
\end_layout
\begin_layout Standard
Syntactically similar sentences, with a different number of words, can be
obtained by means of idioms and
\begin_inset Quotes eld
\end_inset
institutional phrases
\begin_inset Quotes erd
\end_inset
.
These would be word-sequences that, taken as a unit, have a disjunct
\begin_inset Formula $d_{i}$
\end_inset
.
That is, all of the unconnected connectors on the idiom provide
\begin_inset Formula $d_{i}$
\end_inset
.
Thus, we expand the set of nearby words to nearby phrases:
\begin_inset Formula $\left\{ \mbox{phr}\vert\left(\mbox{phr},d_{i}\right)\mbox{ exists}\right\} $
\end_inset
.
Fishing from this set allows syntactically identical sentences to be constructe
d, with varying numbers of words (syntactically identical, ignoring syntactic
structure in the phrase itself).
\end_layout
\begin_layout Standard
Loosening the concept of idiom to, say a
\begin_inset Quotes eld
\end_inset
common noun with a adjective
\begin_inset Quotes erd
\end_inset
, or a
\begin_inset Quotes eld
\end_inset
verb with an adverb
\begin_inset Quotes erd
\end_inset
, we can consider the set
\begin_inset Formula $\left\{ w\vert\left(w,c_{A}-\&\,d_{i}\right)\mbox{ exists}\right\} $
\end_inset
where
\begin_inset Formula $c_{A}-$
\end_inset
is an adjectival connector.
That is, the
\begin_inset Formula $d_{i}$
\end_inset
connects to the rest of the sentence, as before, but that now, there is
an adjective connector, to which an adjective can be connected.
Thus, again, we explore the space of nearby sentences, but now with locations
that can be
\begin_inset Quotes eld
\end_inset
decorated
\begin_inset Quotes erd
\end_inset
with extra words.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The word
\begin_inset Quotes eld
\end_inset
decorated
\begin_inset Quotes erd
\end_inset
here is similar to the idea of mutation in genetic programming.
There, one takes an existing expression tree, and randomly adds
\begin_inset Quotes eld
\end_inset
knobs
\begin_inset Quotes erd
\end_inset
to it, in various places.
The
\begin_inset Quotes eld
\end_inset
knobs
\begin_inset Quotes erd
\end_inset
can be
\begin_inset Quotes eld
\end_inset
turned
\begin_inset Quotes erd
\end_inset
to have different settings, and the fitness of the expression tree, with
a given knob-setting is then evaluated.
The fitness is used for evolutionary guidance of a population of individuals.
In the present case, the
\begin_inset Quotes eld
\end_inset
knob
\begin_inset Quotes erd
\end_inset
would be the vacant slot for an adjective.
The knob setting would be the selection of a specific adjective.
The fitness can be evaluated extrinsically:
\begin_inset Quotes eld
\end_inset
does this new sentence express the idea better?
\begin_inset Quotes erd
\end_inset
or intrinsically:
\begin_inset Quotes eld
\end_inset
does the mutual information of the total sentence increase?
\begin_inset Quotes erd
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Now, most of what has been written in the three paragraphs above is old
hat; ideas such as this have been articulated in linguistic theory for
many decades.
What is different here (what I hope is different) is the provision of an
actual metric, a way of actually measuring the distances between sentences
that moves beyond the concepts of a Hamming distance or a Levenshtein distance,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia,
\begin_inset CommandInset href
LatexCommand href
name "Hamming distance"
target "https://en.wikipedia.org/wiki/Hamming_distance"
literal "false"
\end_inset
and
\begin_inset CommandInset href
LatexCommand href
name "Levenshtein distance"
target "https://en.wikipedia.org/wiki/Levenshtein_distance"
literal "false"
\end_inset
.
\end_layout
\end_inset
and gets us closer to a semantic distance.
\end_layout
\begin_layout Standard
The metric above is a
\begin_inset Quotes eld
\end_inset
syntax-respecting distance
\begin_inset Quotes erd
\end_inset
.
Lets write down a formal formula for it.
Given two strings
\begin_inset Formula $W=\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
and
\begin_inset Formula $V=\left(v_{1},v_{2},\cdots,v_{n}\right)$
\end_inset
having the same parse
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
, the syntax-respecting distance srd is
\begin_inset Formula
\[
\mbox{srd}\left(W,V\right)=\sum_{i}f\left(w_{i},v_{i}\right)
\]
\end_inset
where
\begin_inset Formula $f$
\end_inset
is a word-pair distance, presumably just the MI between the two words (which
is why it is summed, instead of e.g.
taking the Euclidean sum-of-squares distance.) This strict distance can
even be extended to accommodate idioms, adjectives, etc.
as described above.
\end_layout
\begin_layout Standard
Note that the MI tools also allow the definition of
\begin_inset Formula $MI\left(d_{i},d_{j}\right)$
\end_inset
so that, for any given disjunct
\begin_inset Formula $d_{i}$
\end_inset
, there is also a local neighborhood of
\begin_inset Quotes eld
\end_inset
similar
\begin_inset Quotes erd
\end_inset
disjuncts
\begin_inset Formula $d_{j}$
\end_inset
.
However, these are necessarily grammatically different.
Thus, one cannot take a syntactically valid parse, and just substitute
\begin_inset Formula $d_{i}\mapsto d_{j}$
\end_inset
without braking the parse.
But perhaps this can be rescued in some way.
At this time, there is no experimental characterization of
\begin_inset Formula $MI\left(d_{i},d_{j}\right)$
\end_inset
beyond the fact that it is distributed as a Gaussian (and so again is a
GOE).
Experimental results remain a bottleneck to theorizing.
\end_layout
\begin_layout Standard
Consider a concrete example:
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
This is no accident.
\end_layout
\begin_layout Plain Layout
This is not accidental.
\end_layout
\end_inset
These two are more or less semantically equivalent.
But, in terms of classical linguistics, they differ syntactically:
\begin_inset Quotes eld
\end_inset
no accident
\begin_inset Quotes erd
\end_inset
is an object (
\begin_inset Quotes eld
\end_inset
accident
\begin_inset Quotes erd
\end_inset
is a noun); whereas
\begin_inset Quotes eld
\end_inset
not accidental
\begin_inset Quotes erd
\end_inset
is a predicative adjective (an adjective modifying the subject of
\begin_inset Quotes eld
\end_inset
to be
\begin_inset Quotes erd
\end_inset
).
Given some dataset, the distance metric above will provide a numeric distance
between this pair of sentences.
But what is that distance actually measuring? Syntax? Semantics? A combination?
Something else?
\end_layout
\begin_layout Standard
Of course, the verb
\begin_inset Quotes eld
\end_inset
to be
\begin_inset Quotes erd
\end_inset
is a copula; these sentences express an intensional quality of some referenced
\begin_inset Quotes eld
\end_inset
this
\begin_inset Quotes erd
\end_inset
.
But we are not told what
\begin_inset Quotes eld
\end_inset
this
\begin_inset Quotes erd
\end_inset
is; at this stage of the analysis, reference resolution is not yet available.
At this stage, the most we can find out about the two sentences above is
that they have a high four-word MI, higher than the MST parse.
These two sentences are
\begin_inset Quotes eld
\end_inset
set phrases
\begin_inset Quotes erd
\end_inset
.
That is,
\begin_inset Formula
\[
MI\left(\mbox{this},\mbox{is},\mbox{no},\mbox{accident}\right)\gg\sum_{\left(w_{i},w_{j}\right)\in MST\left(\mbox{this is no accident}\right)}MI\left(w_{i},w_{j}\right)
\]
\end_inset
mostly because the copula
\begin_inset Formula $MI\left(w_{i},\mbox{is}\right)$
\end_inset
and
\begin_inset Formula $MI\left(\mbox{is},w_{j}\right)$
\end_inset
will be small, and likewise
\begin_inset Formula $MI\left(\mbox{this},w_{k}\right)$
\end_inset
will be small.
The most we can hope for is that
\begin_inset Formula $MI\left(\mbox{no},\mbox{accident}\right)$
\end_inset
is large, but this won't be enough to capture the reality that
\begin_inset Quotes eld
\end_inset
this is no accident
\begin_inset Quotes erd
\end_inset
is a set phrase.
That is, MST parses alone are insufficient to capture idiomatic expressions.
It seems unlikely that disjunctive parses do any batter: viz.
it seems likely that
\begin_inset Formula
\[
MI\left(\mbox{this},\mbox{is},\mbox{no},\mbox{accident}\right)\gg\sum_{\left(w_{i},d_{i}\right)\in LG\left(\mbox{this is no accident}\right)}MI\left(w_{i},d_{i}\right)
\]
\end_inset
for a disjunctive parse.
\end_layout
\begin_layout Subsection*
Representing ideas with word sequences
\end_layout
\begin_layout Standard
Consider the task of a writer who wishes to express an idea.
At the basic level, this requires a search for different collections of
sentences that convey the same meaning.
At this point, we do not have any precise definition of what
\begin_inset Quotes eld
\end_inset
an idea
\begin_inset Quotes erd
\end_inset
is, or how to thread sentences through it.
Presumably, an
\begin_inset Quotes eld
\end_inset
idea
\begin_inset Quotes erd
\end_inset
is some region of space, a volume, and an expression of the idea is a collectio
n of sentences, paragraphs, that form a space-filling curve through this
space.
The sentences are the flight of a moth about a light-bulb, filling the
surrounding space with a trajectory.
\end_layout
\begin_layout Standard
Given the present set of developments, what could an
\begin_inset Quotes eld
\end_inset
idea
\begin_inset Quotes erd
\end_inset
be? Well, per usual, a concept:
\begin_inset Quotes eld
\end_inset
a chair
\begin_inset Quotes erd
\end_inset
, with all of it's extensive and intensive properties: has legs, can be
sat on, is movable, has a flat surface, etc.
This can be treated as a
\begin_inset Quotes eld
\end_inset
bag of words
\begin_inset Quotes erd
\end_inset
: {legs, sit, movable, flat}, a primary word
\begin_inset Quotes eld
\end_inset
chair
\begin_inset Quotes erd
\end_inset
, the associated relations: {has, can be, is}.
The description & expression of a chair is then the threading of this space
by strings of words, visiting all of the space, without repetition.
These last two:
\begin_inset Quotes eld
\end_inset
visit all of the space
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
without repetition
\begin_inset Quotes erd
\end_inset
, require a metric space.
For the first,
\begin_inset Quotes eld
\end_inset
visit all of the space
\begin_inset Quotes erd
\end_inset
, some Hausdorff topology of balls, with a sense of the volume of the balls:
the metric gives us this.
For the second, a sense of separation or distance, to maximize distance
between sentence-strings (while staying within the concept-space).
We want two sentences to repel each other, when they get too close.
Again, this is provided by the metric.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Would it be better to have a
\begin_inset Quotes eld
\end_inset
Pauli exclusion principle
\begin_inset Quotes erd
\end_inset
? To disallow two sentences from occupying the same space? This is not the
same as saying that two sentences are repulsive, when they are too near
each other.
How might this work? I am not aware of any description of any (measure-preservi
ng) dynamical system that exhibits or makes use of some exclusion principle.
In Riemannian geometry, the exclusion principle arises from fermions, which
provide a certain square-root of a connection, i.e.
a
\begin_inset Quotes eld
\end_inset
spin manifold
\begin_inset Quotes erd
\end_inset
or a
\begin_inset Quotes eld
\end_inset
spin structure
\begin_inset Quotes erd
\end_inset
as mild generalizations of Riemannian manifolds.
But we have not defined this
\begin_inset Quotes eld
\end_inset
space of words and sentences
\begin_inset Quotes erd
\end_inset
closely enough to map it into the machinery of fiber bundles and connections,
from which we could describe spin structures.
So, for the moment, this idea remains out of grasp.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection*
Recursive relationships
\end_layout
\begin_layout Standard
The ultimate hypothesis presented here is that these ideas can be applied
recursively.
Starting with word-pair MI, we arrive at MST parses.
Starting with MST parses, we arrive at disjuncts and structural analysis
of sentences.
This process can be repeated again.
Specifically, the
\begin_inset Formula $MI\left(d_{i},d_{j}\right)$
\end_inset
between a pair of disjuncts is directly available, from direct observation.
Given a parse
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
of a sentence, we can now obtain the MST parse of
\begin_inset Formula $d_{1},d_{2},\cdots,d_{n}$
\end_inset
.
Where does this lead? In what sense does this provide the higher-order
perturbative expansion of the original object of study,
\begin_inset Formula $MI\left(w_{1},w_{2},\cdots,w_{n}\right)$
\end_inset
?
\end_layout
\begin_layout Standard
Let's not lose sight of the meta-goals.
At short range, we wish to obtain structure across multiple sentences,
at the paragraph level.
Insofar as human communication is about topics, then the goal is to identify
a common theme.
This can be reduced to collecting assertions made about objects: a very
traditional KR task.
At longer range, the grammatical relationships between objects is nothing
other than
\begin_inset Quotes eld
\end_inset
common sense
\begin_inset Quotes erd
\end_inset
: if you hit your thumb with a hammer, it will hurt.
This is not a
\begin_inset Quotes eld
\end_inset
logical deduction
\begin_inset Quotes erd
\end_inset
, this is the perception of a structural relationship in sensory data.
Is the procurement of MST parses of disjuncts the next step in the automated
extraction of common sense?
\end_layout
\begin_layout Standard
The answer is cloudy.
Certainly, hypothesis can be readily cooked up for all of this.
We can limit the kinds of hypothesis to those involving MI analysis across
larger expanses of text.
But still, there are many of these; which work best? Can we go meta at
this level, also? To ask for an algorithm that generates hypothesis, involving
the factorizations of MI, that automatically explores the various alternatives?
Perhaps.
For me, the limiting factors are not an ability to hypothesize and theorize,
but to perform actual experiments and measure results.
This is in turn limited by lack of suitable infrastructure.
The degree to which this aligns with the meta-goal of AGI remains unknown.
\end_layout
\begin_layout Section*
The End
\end_layout
\begin_layout Standard
This is the end of the factoring paper, for now.
Perhaps more will be added, later.
A suitable conclusion must be written.
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
btprint "btPrintCited"
bibfiles "lang"
options "tufte"
\end_inset
\end_layout
\end_body
\end_document