#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}
\end_preamble
\use_default_options true
\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 true
\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
\leftmargin 11page%
\topmargin 8pheight%
\rightmargin 11page%
\bottommargin 10pheight%
\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
Purely Symbolic Induction of Structure
\end_layout
\begin_layout Date
February 2022
\end_layout
\begin_layout Author
Linas Vepštas
\end_layout
\begin_layout Abstract
Techniques honed for the induction of grammar from text corpora can be extended
to visual, auditory and other sensory domains, providing a structure for
such senses that can be understood in terms of symbols and grammars.
This simultaneously solves the classical
\begin_inset Quotes eld
\end_inset
symbol grounding problem
\begin_inset Quotes erd
\end_inset
while also providing a pragmatic approach to developing practical software
systems that can articulate the world around us in a symbolic, communicable
fashion.
\end_layout
\begin_layout Section*
Introduction
\end_layout
\begin_layout Standard
The symbolic approach to cognition is founded on the idea that observed
nature can be categorized into distinct entities which are involved in
relationships with one another.
In this approach, the primary challenges are to recognize entities, and
to discover what relationships there are between them.
\end_layout
\begin_layout Standard
The recognition problem is to be applied to sensory input.
That is, we cannot know nature directly, as it is, but only by means of
observation and sensing.
Conventionally, this can be taken to be the classical five senses: hearing,
touch, smell, vision, taste; or, more generally, scientific instruments
and engineered detectors.
Such sensors generate collections of data; this may be time-ordered, or
simply a jumbled bag of data-points.
\end_layout
\begin_layout Standard
Out of this jumble of data, the goal of entity detection is to recognize
groupings of data that
\emph on
always
\emph default
occur together.
The adverb
\begin_inset Quotes eld
\end_inset
\emph on
always
\emph default
\begin_inset Quotes erd
\end_inset
here is key: entities are those things that are not events: they have existence
over extended periods of time (Heidegger's
\begin_inset Quotes eld
\end_inset
Dasein
\begin_inset Quotes erd
\end_inset
).
The goal of relationship detection is to determine both the structure of
entities (part-whole relationships) as well as events (statistical co-occurrenc
es and causation).
\end_layout
\begin_layout Standard
If one is somehow able to detect and discern entities, and observe frequent
relationships between them, then the path to symbolic processing becomes
accessible.
Each entity can be assigned a symbol (thus resolving the famous
\begin_inset Quotes eld
\end_inset
symbol grounding problem
\begin_inset Quotes erd
\end_inset
), and conventional ideas about information theory can be applied to perform
reasoning, inference and deduction.
Here, the words
\begin_inset Quotes eld
\end_inset
information theory
\begin_inset Quotes erd
\end_inset
are taken in the broadest sense: not just signal processing and finite
state transducers, but also Bayesian nets, theorem provers and Turing machines;
the whole of what is computationally accessible in the current era.
\end_layout
\begin_layout Standard
The goal of this paper is to develop a general theory for the conversion
of sensory data into symbolic relationships.
It is founded both on a collection of mathematical formalisms and also
on a collection of experimental results.
The experimental results are presented in a companion text; this text focuses
on presenting the mathematical foundations in as simple and direct a fashion
as possible.
\end_layout
\begin_layout Standard
The organization is as follows.
First, the general relationship between graphs and grammars is sketched
out, attempting to illustrate just how broad, general and all-encompassing
this is.
Next, it is shown how this symbolic structure can be extended to visual
and auditory perception.
After this comes a mathematical deep-dive, reviewing how statistical principles
can be used to discern relationships between entities.
Working backwards, a practical algorithm is presented for extracting entities
themselves.
To conclude, a collection of hypothesis and wild speculations are presented.
\end_layout
\begin_layout Section*
From Graphs to Grammar
\end_layout
\begin_layout Standard
Assuming that sensory data can be categorized into entities and relationships,
the natural information-theoretic setting would seem to be graphs: each
entity is represented by a vertex, each relationship is represented by
an edge.
In the most simplistic terms, vertexes are labeled with symbols, and edges
with symbol pairs.
An example of this kind of naive symbolic graphical relationship is illustrated
below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/sparse-cut.eps
lyxscale 70
width 40col%
\end_inset
\end_layout
\begin_layout Standard
The figure on the left shows a graph-theoretic sparse graph of relationships
between entities.
On the right is the same graph, with some of the edges cut into half-edges,
with the half-edge connectors labeled with what they can connect to.
The connectors are drawn with distinct shapes, intended to convey what
they are allowed to connect to.
Such vertices, together with a collection of connectors, can be imagined
to be jigsaw puzzle pieces, waiting to be connected.
\end_layout
\begin_layout Standard
The simplicity of the above diagram is deceptive.
In fact, there is a deep and broad mathematical foundation for them.
Such jigsaw pieces are the elements of a category-theoretic
\begin_inset Quotes eld
\end_inset
monoidal category
\begin_inset Quotes erd
\end_inset
.
The connectors themselves are type-theoretic types.
The puzzle pieces themselves are the syntactical elements of a grammar,
formally defined.
These last three statements arise from a relatively well-known generalization
of Curry–Howard correspondence: for every category, there is a type theory,
a grammar and a logic; from each, the others can be determined.
\begin_inset CommandInset citation
LatexCommand cite
key "Baez2009"
literal "false"
\end_inset
The mathematics of these relationships is foundational and quite challenging
to the uninitiated.
\end_layout
\begin_layout Standard
The paradigm of jigsaw pieces has long been known in linguistics, and has
been repeatedly rediscovered.
The diagram below is taken from the first paper describing Link Grammar,
a kind of dependency grammar.
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991"
literal "false"
\end_inset
Grammatically-valid (syntactically valid) sentences are formed whenever
jigsaw connectors can be mated, leaving non unconnected.
This fashion of specifying a syntax and a grammar may feel a bit foreign
and unusual; be aware that such grammars can be automatically (i.e.
algorithmically) transformed into equivalent HPSG, DG, CG, LFG,
\emph on
etc.
\emph default
style grammars.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/link-grammar.png
lyxscale 60
width 85col%
\end_inset
\end_layout
\begin_layout Standard
The jigsaw paradigm is not infrequently rediscovered.
\begin_inset CommandInset citation
LatexCommand cite
key "Nida97"
literal "false"
\end_inset
A recent rediscovery of the jigsaw-puzzle paradigm can be found in the
work of Bob Coecke.
\begin_inset CommandInset citation
LatexCommand cite
key "Coecke2010"
literal "false"
\end_inset
Notable results include a linear-time quantum algorithm for parsing natural
language.
\begin_inset CommandInset citation
LatexCommand cite
key "Coecke2016"
literal "false"
\end_inset
This work is notable in that it provides a good bridge between concepts
in linguistics and the hard science of mathematics.
It is not the first such; perhaps one of the earliest formal algebraic
treatments of linguistics can be found in Marcus.
\begin_inset CommandInset citation
LatexCommand cite
key "Marcus1967"
literal "false"
\end_inset
\end_layout
\begin_layout Subsection*
Compositionality and Sheaves
\end_layout
\begin_layout Standard
The naive replacement of entities by vertexes and relationships by edges
seems to itself have a problem with well-foundedness.
If an entity is made of parts, does this mean that a vertex is made of
parts? What are those parts made of? Is there an infinite regress? How
might one indicate the fact that some entity has a composite structure?
The answers to these questions are resolved by observing that a partially-assem
bled jigsaw puzzle resembles a singular jigsaw piece: it externalizes some
number of unconnected connectors, while also describing the connectivity
of the fully-assembled territory.
This is how the part-whole relationship is established: the
\begin_inset Quotes eld
\end_inset
whole
\begin_inset Quotes erd
\end_inset
entity is a partially assembled jigsaw; the parts are the individual pieces,
and the way that the entity can interact with other entities is through
the as-yet unconnected connectors.
\end_layout
\begin_layout Standard
Sheaf theory is the branch of axioms that explores how such part-whole structure
s behave.
The
\begin_inset Quotes eld
\end_inset
sheaf axioms
\begin_inset Quotes erd
\end_inset
provide a handful of simple rules that describe how a valid sheaf can be
created.
In simplistic terms, the sheaf axioms describe how jigsaw pieces connect.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2017sheaves"
literal "false"
\end_inset
When sheaf theory is taken in its full glory, it has been offered up as
an alternative to set theory as a foundation for all of mathematics.
\begin_inset CommandInset citation
LatexCommand cite
key "MacLane1992"
literal "false"
\end_inset
This is because the sheaf axioms suffice not only to be a foundation for
topology (as a generalization of frames and locales), but also for logic
(via the extended Curry–Howard correspondence mentioned above).
These are formidable claims with an impeccable mathematical pedigree; the
general mathematical theory seems entirely adequate as a foundation for
AGI.
Armed with this, one can move forward.
\end_layout
\begin_layout Standard
In philosophy, the question of part-whole relationships, identity, existence
and thing-ness is studied under the name of mereology.
\begin_inset CommandInset citation
LatexCommand cite
key "Varzi2003"
literal "false"
\end_inset
Some of the key concepts of mereology include ideas such as
\begin_inset Quotes eld
\end_inset
contact
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
fastentation
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
cohesion
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
fusion
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
brutal composition
\begin_inset Quotes erd
\end_inset
.
A shallow understanding of these concepts is enough to convince one that
jigsaw pieces fit the bill.
\begin_inset CommandInset citation
LatexCommand cite
key "Vepstas2020mere"
literal "false"
\end_inset
Why mention philosophy in the same breath as mathematics? The function
of philosophy is to wrestle with vague, phantasmic questions, to thrash
about in the fog, hoping to find a purchase on something solid.
Whenever such contact can be made, the scientists take over: this is how
\begin_inset Quotes eld
\end_inset
natural philosophy
\begin_inset Quotes erd
\end_inset
morphed into
\begin_inset Quotes eld
\end_inset
physics
\begin_inset Quotes erd
\end_inset
.
Insofar as AGI wishes to be a foundational theory of cognitive-everything,
the role of philosophy in suggesting where to look remains invaluable.
In this particular case, the ideas of mereology provide the requisite bridge
from the abstract to the concrete.
\end_layout
\begin_layout Subsection*
Pervasiveness
\end_layout
\begin_layout Standard
After becoming familiar with the jigsaw paradigm, it becomes evident that
it is absolutely pervasive.
This is illustrated in the two figures below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/citric-acid-cycle.png
lyxscale 50
width 28col%
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset Graphics
filename ../reco-image/puzzle.eps
lyxscale 50
width 30col%
\end_inset
\end_layout
\begin_layout Standard
The figure on the left is the Krebs cycle (the citric acid cycle in biochemistry
).
It has an obvious graphical structure, and it is not difficult to see how
it is to be decomposed into jigsaw pieces.
What is notable here is that some of the jigsaw pieces find a literal embodimen
t in the three-dimensional shape of molecules.
Diagrams of DNA are often shown with jigsaw connectors standing in for
the amino acids ATGC.
\end_layout
\begin_layout Standard
The diagram on the left is more abstract, and is meant to illustrate composition
or beta reduction in term algebra.
A term is
\begin_inset Formula $f\left(x\right)$
\end_inset
or an
\begin_inset Formula $n$
\end_inset
-ary function symbol
\begin_inset Formula $f\left(x_{1},x_{2},\cdots,x_{n}\right)$
\end_inset
.
Variables are denoted as
\begin_inset Formula $x,y,z,\cdots$
\end_inset
while constants are type instances, such as
\begin_inset Formula $42$
\end_inset
or the string
\begin_inset Quotes eld
\end_inset
foobar
\begin_inset Quotes erd
\end_inset
.
Beta reduction is the act of
\begin_inset Quotes eld
\end_inset
plugging in
\begin_inset Quotes erd
\end_inset
:
\begin_inset Formula $f\left(x\right):42\mapsto f\left(42\right)$
\end_inset
.
Re-interpreted as jigsaw connectors, the term
\begin_inset Formula $f\left(x\right)$
\end_inset
is the jigsaw on the left, and 42 is the jigsaw on the right.
In order to connect, the two types must match.
The type-theoretical type of the variable
\begin_inset Formula $x$
\end_inset
must match the type of of what is plugged in.
This kind of plugging-in or composition is rampant throughout mathematics.
Prime examples can be found in proof theory,
\begin_inset CommandInset citation
LatexCommand cite
key "Troelstra1996"
literal "false"
\end_inset
lambda calculus,
\begin_inset CommandInset citation
LatexCommand cite
key "Barendregt1981"
literal "false"
\end_inset
term algebras
\begin_inset CommandInset citation
LatexCommand cite
key "Baader1998"
literal "false"
\end_inset
and model theory.
\begin_inset CommandInset citation
LatexCommand cite
key "Hodges1997"
literal "false"
\end_inset
\end_layout
\begin_layout Subsection*
Vision and Sound
\end_layout
\begin_layout Standard
Shapes have a structural grammar, too.
The connectors can specify location, color, shape, texture.
The key point of this structural decomposition is that it is
\emph on
not about pixels
\emph default
! The structural decomposition is scale-invariant (more or less, unless
some connector fixes the scale) and rotationally invariant (unless some
connector fixes direction).
The structural grammar captures the morphology of the shape, its general
properties, omitting details when they are impertinent, and capturing them
when they are important.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/traffic-lights.jpg
lyxscale 80
width 5col%
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset Graphics
filename ../reco-image/traffic-light-grammar.eps
width 25col%
\end_inset
\end_layout
\begin_layout Standard
Not only do two-dimensional photographs have a structure grammar, but so
do sounds.
On the left is a spectrogram of a whale song.
It is ostensibly
\begin_inset Quotes eld
\end_inset
one-dimensional
\begin_inset Quotes erd
\end_inset
, with time as the primary dimension, but is more accurately multi-dimensional:
the vertical axis shows frequency, the colors encode a third dimension,
the intensity.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/noaa-fisheries-humpback.jpg
width 40col%
\end_inset
\begin_inset space \qquad{}
\end_inset
\begin_inset Graphics
filename ../reco-image/audio-graph.eps
width 15col%
\end_inset
\end_layout
\begin_layout Standard
On the right is a graphical representation of the midsection of the song.
It shows the number of repetitions (six), as well as the shape of the frequency
distribution (its a chirp, which can be discovered with a chirp filter,
a certain kind of digital signal processing filter.) Individual repetitions
can be spotted with a finite impulse response filter.
The point here is that basic sensory information can also be described
in grammatical terms.
\end_layout
\begin_layout Section*
Symbolic Learning
\end_layout
\begin_layout Standard
In order for a graphical, sheaf-theoretic, grammatical theory of structure
to serve as a foundation stone for AGI, there most be a practical algorithm
for extracting such structure from sensory data.
Such an algorithm is sketched below.
It consists of three interacting parts.
The first step is chunking, the division of sensory data into candidate
entities and candidate interactions that might possibly be identified as
entities or interactions by the second step.
The second step takes a collection of candidate graphs, splits them into
jigsaw pieces, and then attempts to classify jigsaw pieces into common
categories, based on their commonalities.
The third step is a recursive step, to repeat the process again, but this
time taking the discovered structure as the sensory input.
It is meant to be a hierarchical crawl up the semantic ladder.
\end_layout
\begin_layout Standard
Experimentally, the second step has been the most thoroughly explored.
An implementation exists within the OpenCog system,
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See the
\begin_inset Quotes eld
\end_inset
\begin_inset CommandInset href
LatexCommand href
name "learn project"
target "https://github.com/opencog/learn"
literal "false"
\end_inset
\begin_inset Quotes erd
\end_inset
in github.
\end_layout
\end_inset
with extensive research diaries logging results.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See the
\begin_inset CommandInset href
LatexCommand href
name "diaries"
target "https://github.com/opencog/learn/tree/master/learn-lang-diary"
literal "false"
\end_inset
in the aforementioned project.
\end_layout
\end_inset
A summary of these results is presented as a companion paper to this one.
Explorations of the first and third steps have hardly begun.
It is easiest to describe the second step first.
\end_layout
\begin_layout Subsection*
Grammatical Induction
\end_layout
\begin_layout Standard
In linguistics, one is presented with a pre-chunked sequence of words; the
conversion of raw sound into phonemes and then words is presumed to have
already occurred.
The task is to extract a more-or-less conventional grammar given a corpus
of text.
The first step is to perform a Maximum Spanning Trees (MST) parse; the
second step is to split the MST parse into jigsaw pieces, and classify
those pieces into lexical vectors.
The generation of the MST parse requires collecting statistics on a corpus,
based on maximum entropy principles; this has a long and deep tradition
in Corpus Linguistics, going as far back as Biblical Concordances in earlier
centuries, before linguistics was a distinct field of study.
Lexical semantics also a deep and broad research literature, much more
modern.
Of note here is that this vector-based description has more than a few
similarities to the theory of neural-nets, and yet is fundamentally different,
because it is ultimately lexical (
\emph on
i.e.
\emph default
is symbolic.) It is not obvious if deep-learning techniques can be applied
to obtain these lexical vectors; what is described below is a simpler,
plainer approach.
\end_layout
\begin_layout Subsubsection*
Maximum Planar Graph Parsing
\end_layout
\begin_layout Standard
The MST parsing algorithm is described by Yuret, as follows.
\begin_inset CommandInset citation
LatexCommand cite
key "Yuret1998"
literal "false"
\end_inset
Starting with a corpus, maintain a count
\begin_inset Formula $N\left(u,w\right)$
\end_inset
of nearby word-pairs
\begin_inset Formula $\left(u,w\right)$
\end_inset
.
Here,
\begin_inset Quotes eld
\end_inset
nearby
\begin_inset Quotes erd
\end_inset
usually means
\begin_inset Quotes eld
\end_inset
in a window of width six
\begin_inset Quotes erd
\end_inset
.
A frequentist probability
\begin_inset Formula $p\left(u,w\right)=N\left(u,w\right)/N\left(*,*\right)$
\end_inset
is just the count of a given word-pair divided by the total count of all
word-pairs.
The star indicates a marginal sum or marginal probability, so that
\begin_inset Formula $p\left(u,*\right)=\sum_{w}p\left(u,w\right)=\sum_{w}N\left(u,w\right)/N\left(*,*\right)=N\left(u,*\right)/N\left(*,*\right)$
\end_inset
.
Given these frequencies, defines the Lexical Attraction between word-pairs
as
\begin_inset Formula
\[
MI\left(u,w\right)=\log_{2}\frac{p\left(u,w\right)}{p\left(u,*\right)p\left(*,w\right)}
\]
\end_inset
This lexical attraction is just the mutual information (MI); it has a somewhat
unusual form, as word-pairs are necessarily not symmetric:
\begin_inset Formula $\left(u,w\right)\ne\left(w,u\right)$
\end_inset
and conventional texts on probability theory usually do not address this
non-symmetric situation.
Note that the MI may be negative! The range of values depends on the size
of the corpus; for a
\begin_inset Quotes eld
\end_inset
typical
\begin_inset Quotes erd
\end_inset
corpus, it ranges from -10 to +30.
\end_layout
\begin_layout Standard
Given a table of
\begin_inset Formula $MI\left(u,w\right)$
\end_inset
obtained by counting, one obtains an MST parse of a sentence by considering
all possible trees that connect all of the words, and selecting the one
tree that has the largest possible total
\begin_inset Formula $MI$
\end_inset
.
An example of such a tree is shown below, taken from Yuret's thesis.
The numbers in the links are the MI between the indicated words.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/Yuret.png
width 40col%
\end_inset
\end_layout
\begin_layout Standard
There exist a number of fast algorithms for obtaining maximal spanning trees.
Variants include those that generate only planar trees, or even planar
graphs (graphs with loops, but no intersecting links).
Maximal planar graphs (MPG) appear to offer experimentally-observable advantage
s over trees, as they appear to constrain the grammar more tightly.
In this sense, they offer some of the advantages seen in catena-based linguisti
c theory.
\begin_inset CommandInset citation
LatexCommand cite
key "Osborne2012"
literal "false"
\end_inset
\end_layout
\begin_layout Standard
At any rate, the point here is that the MST parses are linguistically plausible:
it is fairly straightforward to verify that they correspond, more or less,
to what trained linguists would write down for a parse.
The accuracy is reasonably high.
For the present algorithms, perfect accuracy is not needed, as later stages
make up for this.
Yuret indicates that the best results are obtained when one accumulates
at least a million sentences.
This is not outrageous: work in child psychology indicates that human babies
hear several million sentences by the age of two years.
\end_layout
\begin_layout Subsubsection*
Lexical Entries
\end_layout
\begin_layout Standard
Given an MST or MPG parse, the lexis is constructed by chopping up the parse
into jigsaw pieces, and then accumulating the counts on the jigsaw pieces.
This is shown below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/disjunct-cut.eps
lyxscale 60
width 32col%
\end_inset
\end_layout
\begin_layout Standard
There are multiple different notations possible for the above.
There is a tensorial notation, popular in quantum approaches; the lexical
entry would be written as
\begin_inset Formula $\mbox{ball}:\left|\overleftarrow{\mbox{the}}\right\rangle \otimes\left|\overleftarrow{\mbox{throw}}\right\rangle $
\end_inset
while in Link Grammar, it is denoted as
\begin_inset Formula $\mathtt{ball:the-\&\;throw-}$
\end_inset
where the minus signs indicate connections to the left.
The ampersand is the conjunction operator from a fragment of linear logic;
it demands that both connectors be present.
Linear logic is the logic of tensor algebras (by the aforementioned Curry–Howar
d correspondence.) Unlike tensor algebras, natural language has a distinct
left-right asymmetry, and so the corresponding logic (of the monoidal category
of natural language) is just a fragment of linear logic.
Note that all of quantum mechanics lies inside of the tensor algebra; this
explains why assorted quantum concepts seem to recur in natural language
discussions.
\end_layout
\begin_layout Standard
The connector sequences
\begin_inset Formula $\mathtt{the-\&\;throw-}$
\end_inset
or
\begin_inset Formula $\left|\overleftarrow{\mbox{the}}\right\rangle \otimes\left|\overleftarrow{\mbox{throw}}\right\rangle $
\end_inset
often called
\begin_inset Quotes eld
\end_inset
disjuncts
\begin_inset Quotes erd
\end_inset
: different connector sequences
\begin_inset Formula $d$
\end_inset
are disjoined from one-another.
Given a word
\begin_inset Formula $w$
\end_inset
, a lexical entry consists of all word-disjunct pairs
\begin_inset Formula $\left(w,d\right)$
\end_inset
together with their observed count
\begin_inset Formula $N\left(w,d\right)$
\end_inset
.
Given this count, one may define a frequency
\begin_inset Formula $p\left(w,d\right)=N\left(w,d\right)/N\left(*,*\right)$
\end_inset
where this time,
\begin_inset Formula $N\left(*,*\right)$
\end_inset
is the sum over all word-disjunct pairs.
A lexical entry is thus a sparse skip-gram-like vector:
\begin_inset Formula
\[
\overrightarrow{w}=p\left(w,d_{1}\right)\widehat{e_{1}}+\cdots+p\left(w,d_{n}\right)\widehat{e_{n}}
\]
\end_inset
One can use the logical disjunction
\begin_inset Quotes eld
\end_inset
or
\begin_inset Quotes erd
\end_inset
in place of the plus sign; this would be the
\begin_inset Quotes eld
\end_inset
choice
\begin_inset Quotes erd
\end_inset
operator in linear logic (as in
\begin_inset Quotes eld
\end_inset
menu choice
\begin_inset Quotes erd
\end_inset
: pick one or another).
The basis vectors
\begin_inset Formula $\widehat{e_{k}}$
\end_inset
are one and the same thing as the skip-gram disjuncts
\begin_inset Formula $\left|\overleftarrow{\mbox{the}}\right\rangle \otimes\left|\overleftarrow{\mbox{throw}}\right\rangle $
\end_inset
, just offering a short-hand notation.
\end_layout
\begin_layout Subsubsection*
Similarity
\end_layout
\begin_layout Standard
The lexis generated above contains individual words with connectors to other,
specific words.
Although each vector is sparse, and the lexis, as a whole, taken as a matrix
is sparse, it is still quite large.
By contrast, conventional linguistic grammars talk about nouns and verbs
and adjectives.
Part of the learning process is then to automatically find similar categories:
to organize words into groups based on similarities.
A very conventional similarity metric is the cosine distance, given as
\begin_inset Formula
\[
\cos\theta=\overrightarrow{w}\cdot\overrightarrow{v}=\sum_{d}p\left(w,d\right)p\left(v,d\right)
\]
\end_inset
This similarity metric fails.
The space spanned by these vectors is
\emph on
not Euclidean space
\emph default
! It does not have rotational symmetry! Properly, it is a probability space,
a simplex, as one must preserve unit-length probability vectors:
\begin_inset Formula $1=\sum_{w,d}p\left(w,d\right)$
\end_inset
.
The correct information-theoretic similarity is the mutual information:
\begin_inset Formula
\[
MI\left(w,v\right)=\log_{2}\frac{\overrightarrow{w}\cdot\overrightarrow{v}}{\left(\overrightarrow{w}\cdot\overrightarrow{*}\right)\left(\overrightarrow{*}\cdot\overrightarrow{v}\right)}
\]
\end_inset
where
\begin_inset Formula
\[
\overrightarrow{w}\cdot\overrightarrow{*}=\sum_{d}p\left(w,d\right)p\left(*,d\right)
\]
\end_inset
Unlike the MI for word-pairs, this MI is symmetric:
\begin_inset Formula $MI\left(w,v\right)=MI\left(v,w\right)$
\end_inset
.
Experimentally, the distribution of the MI for word pairs appears to be
Gaussian, as shown below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../en-sims-p3/mi-dist-tsup.eps
width 30col%
\end_inset
\end_layout
\begin_layout Standard
The above is obtained from MPG parsing and statistics gathering as described
above.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See the Language Learning Diary Part Three,
\emph on
op.
cit.
\end_layout
\end_inset
Note the graph is on a semi-log scale: normal distributions become parabolas
when graphed this way.
\end_layout
\begin_layout Subsubsection*
Classification
\end_layout
\begin_layout Standard
Clustering words into grammatical categories based on similarity may seem
straight-forward, but can founder on several different details.
First, the MI, as defined above, has the property that words with the very
highest MI tend to be very infrequent, rare.
As a practical detail, one wishes to first cluster the most frequent words.
To do this, one must add some kind of offset, so as to recommend common
words first.
Such an offset is provided by the average of the logarithm of the frequency
of the two words.
This leads to the definition of
\begin_inset Formula
\begin{align*}
MI_{\mbox{ranked}}\left(w,v\right)= & MI\left(w,v\right)+\frac{1}{2}\left[\log_{2}p\left(w,*\right)+\log_{2}p\left(v,*\right)\right]\\
= & \log_{2}\frac{\overrightarrow{w}\cdot\overrightarrow{v}}{\sqrt{\left(\overrightarrow{w}\cdot\overrightarrow{*}\right)\left(\overrightarrow{*}\cdot\overrightarrow{v}\right)}}
\end{align*}
\end_inset
The shape of the Gaussian above is unaffected, although it is shifted to
the right; clearly, the ranking is completely different.
\end_layout
\begin_layout Subsubsection*
Word-sense disambiguation
\end_layout
\begin_layout Standard
A second practical difficulty arising during clustering is that of word-sense
disambiguation.
Once two words have been judged similar enough to be merged into a common
class, this does not imply that all disjuncts are to be dumped into that
common class, as well.
Instead, a given vector is to be decomposed into two: a part to be merged,
and a part that is left over.
The part to be merged will share disjuncts in common with the other word-vector
being merged.
The parts that are not shared presumably belong to distinct word-senses.
For example, parts of the word-vector for
\begin_inset Quotes eld
\end_inset
saw
\begin_inset Quotes erd
\end_inset
can be clustered with other cutting tools, while the remainder can be clustered
with viewing verbs.
\end_layout
\begin_layout Standard
Splitting the word-vectors in this way prevents the use of off-the-shelf
clustering algorithms that can be found on the Internet (as these in general
perform an all-or-nothing merge.)
\end_layout
\begin_layout Standard
A further difficulty is that connectors must also be merged.
The rewriting of connector sequences is subtle, as it affects word-vectors
outside of those being merged (the merged connectors might appear
\begin_inset Quotes eld
\end_inset
anywhere
\begin_inset Quotes erd
\end_inset
).
To maintain coherency,
\begin_inset Quotes eld
\end_inset
detailed balance
\begin_inset Quotes erd
\end_inset
must be preserved: the grand total counts must remain the same both before
and after.
This is much the same as detailed balance in chemistry, where the grand-total
number of atoms (and their specific types) in a chemical reaction is preserved,
even as the number of molecules, and the connections change.
Again, this is a place where the sheaf axioms make an appearance.
\end_layout
\begin_layout Subsubsection*
Factorization
\end_layout
\begin_layout Standard
The clustering described above can be understood to be a form of matrix
factorization.
The word-disjunct matrix
\begin_inset Formula $p\left(wd\right)$
\end_inset
is factorized into three matrices
\begin_inset Formula $LCR$
\end_inset
as
\begin_inset Formula
\[
p\left(w,d\right)=\sum_{g,g^{\prime}}p_{L}\left(w,g\right)p_{C}\left(g,g^{\prime}\right)p_{R}\left(g^{\prime},d\right)
\]
\end_inset
where
\begin_inset Formula $g$
\end_inset
is a
\begin_inset Quotes eld
\end_inset
word class
\begin_inset Quotes erd
\end_inset
and
\begin_inset Formula $g^{\prime}$
\end_inset
is a
\begin_inset Quotes eld
\end_inset
grammatical relation
\begin_inset Quotes erd
\end_inset
.
These two are commonly conflated in linguistic theory; here, they will
be distinguished.
The reason for this is that this is the
\emph on
de facto
\emph default
organization of the Link Grammar dictionaries for English, Russian and
other languages.
Examples of grammatical relations are
\begin_inset Quotes eld
\end_inset
subject
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
object
\begin_inset Quotes erd
\end_inset
,
\begin_inset Quotes eld
\end_inset
modifier
\begin_inset Quotes erd
\end_inset
; examples of word classes are
\begin_inset Quotes eld
\end_inset
common noun
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
preposition
\begin_inset Quotes erd
\end_inset
.
The matrices
\begin_inset Formula $L$
\end_inset
and
\begin_inset Formula $R$
\end_inset
are very sparse, which
\begin_inset Formula $C$
\end_inset
is compact, dense and highly connected.
This sparse-dense factorization is visualized below.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../skimage/factor.eps
lyxscale 50
width 40col%
\end_inset
\end_layout
\begin_layout Standard
For the current Link Grammar English dictionary, there are about 100K words,
2K word classes, several hundred grammatical relations (LG
\begin_inset Quotes eld
\end_inset
macros
\begin_inset Quotes erd
\end_inset
) and 30 million disjuncts.
This dictionary is hand-curated; it is an example of what can be accomplished
\begin_inset Quotes eld
\end_inset
by hand
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
Neural networks accurately capture the dense, interconnected central region;
this is
\emph on
why
\emph default
they work.
They necessarily perform dimensional reduction on the sparse left and right
factors.
By erasing/collapsing the sparse factors, neural nets become uninterpretable;
an opaque mass of weight vectors.
Interpretability is all about regaining (factoring back out) the sparse
factors! This is exactly what the symbolic learning algorithm does.
\end_layout
\begin_layout Section*
Chunking
\end_layout
\begin_layout Standard
By working with text, we got lucky.
Sounds have been pre-chunked into words.
The vocabulary of words is relatively small.
Working with raw audio or raw video does not provide such chunked data.
How can it be arrived at? One possibility is to carefully engineer hand-crafted
transducers, from sounds to phonemes and syllables and words.
Another is to automate the creation of such transducers.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/filters.eps
lyxscale 50
width 35col%
\end_inset
\end_layout
\begin_layout Standard
The above illustrates a pair of transducers in block-diagram form.
Each block corresponds to a digital signal processing (DSP) function.
The automation of their discovery can proceed as follows.
Randomly generate a collection of a few hundred filter sequences.
Each takes audio-in, and generates a single-bit output.
Each such filter sequence can be thought of as a
\begin_inset Quotes eld
\end_inset
feature recognizer
\begin_inset Quotes erd
\end_inset
: it detects certain features in the input, responding with a one if the
feature is present, else responding with a zero.
To join up with the symbolic learning algorithm described above, each such
filter sequence can be thought of as a
\begin_inset Quotes eld
\end_inset
candidate word
\begin_inset Quotes erd
\end_inset
.
As it was a randomly generated filter, it probably does not correspond
to anything meaningful.
However, by applying all of these filters on a corpus of sounds, correlations
in their output can be observed.
Large correlations have a high MI, otherwise not.
\end_layout
\begin_layout Standard
To obtain better filter sequences, more meaningful, random perturbations
and extensions of the most highly correlated filters can be explored.
This is a form of genetic program learning.
Each block in the block diagram corresponds to a DSP function, plus its
parameters.
Random genetic mutations are those that alter parameters.
Genetic cross-overs are those that re-arrange blocks and reconnect parameters.
The OpenCog system has already explored this kind of genetic program learning
system; it is called MOSES.
\begin_inset CommandInset citation
LatexCommand cite
key "Looks2006,Looks2007"
literal "false"
\end_inset
That particular system is designed for supervised training on a table of
inputs; the blocks in that system are logical and arithmetic operators,
and a handful of simple functions.
The proposal here is to apply a similar training schedule, but one for
which the blocks are audio (or video) DSP units, and the table of inputs
is replaced by a corpus of audio snippets (or of photographs), and the
reinforcement learning aspect is replaced by an entropy-maximization function.
\end_layout
\begin_layout Standard
The above is a research proposal; it has not been implemented.
There is considerable experience with the genetic program learning subsystem,
and it works quite well.
The software would have to be completely redesigned to be able to manipulate
program trees representing DSP functions.
\end_layout
\begin_layout Standard
An unresolved theoretical issue is that of common mode rejection.
That is, it is quite possible to learn two very different filter sequences,
yet these both detect exactly the same features.
For audio, this is less of a problem, as one can compare time-shifted outputs.
For still photographs, such as of the stop-light, the goal is to learn
three filters, for red, yellow and green disks, and not three different
filters all detecting a red disk.
Resolving this issue, and doubtlessly many more, is effectively impossible
without hands-on experimentation.
\end_layout
\begin_layout Subsection*
The Symbol Grounding Problem and the Frame Problem
\end_layout
\begin_layout Standard
An old problem in philosophy (dating back to Socrates) is the symbol grounding
problem.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See the Stanford Encyclopedia of Philosophy,
\begin_inset Quotes eld
\end_inset
Frame Problem
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
Embodied Cognition
\begin_inset Quotes erd
\end_inset
.
\end_layout
\end_inset
When one says the word
\begin_inset Quotes eld
\end_inset
chair
\begin_inset Quotes erd
\end_inset
, what does that mean? One can attempt to make extensional lists of things
one can sit on, but that list can never be complete.
One can make intensional lists of the properties of a chair; such a list
invariably fails to encompass all the possibilities.
There is in fact a third, commonly overlooked possibility: that of discovering
affordances.
What must an object be like, to be sit-on-able? The filter sequence is
precisely an affordance-detector.
\end_layout
\begin_layout Standard
Lets take a simpler example.
If someone says
\begin_inset Quotes eld
\end_inset
I hear whistling in the distance
\begin_inset Quotes erd
\end_inset
, what does the word
\begin_inset Quotes eld
\end_inset
whistling
\begin_inset Quotes erd
\end_inset
actually mean? How to describe it? What is the grounding for the symbol
\begin_inset Quotes eld
\end_inset
whistling
\begin_inset Quotes erd
\end_inset
? Well, in the above, the grounding is explicitly manifest: it is a certain
kind of hi-pass filter attached to a chirp filter with a certain finite
impulse response time.
That is what
\begin_inset Quotes eld
\end_inset
whistling
\begin_inset Quotes erd
\end_inset
is.
What else could it possibly be? Is the filter sequence an infallible detector
of whistling? Well, no.
Obviously, birds are taken in by fake bird calls; doing better requires
higher intelligence and better hearing.
\end_layout
\begin_layout Standard
Might there be an affordance-detector for chairs? That is, a certain filter
that examines photos, and responds with a yes/no answer to
\begin_inset Quotes eld
\end_inset
can I sit on that
\begin_inset Quotes erd
\end_inset
? Sure.
How can it be learned? Direct, embodied experience: one looks at things,
and then tries to sit on them.
One learns.
But what about the Frame Problem? That is, of all the stimuli, all the
things going on around, which ones are relevant to actually sitting? Well,
but this is precisely what the entropy-maximizing training of filter sequences
is doing: it is using constructs like mutual information to focus on what
is important, and discard what is irrelevant.
At this stage of research, this is but hand-waving.
What is new here is that the above describes an algorithm that can actually
be implemented, and is well-founded on known mathematics and existing,
practical software design principles.
\end_layout
\begin_layout Section*
Abstraction and Recursion
\end_layout
\begin_layout Standard
The development above has focused on a very low level: either parsing in
natural language, or sensory input.
What about common-sense reasoning, one of the Holy Grails of AGI? It is
easily argued that additional methods and techniques are needed to reach
such heights.
But is that actually the case? The author wishes to argue that the techniques
described so far are essentially all that is needed to reach up into the
highest levels of abstraction and general intelligence.
\end_layout
\begin_layout Standard
To get a feeling for the next few rungs of the ladder, it is easiest to
return to the domain of linguistics.
In lexical semantics, there is an idea of
\begin_inset Quotes eld
\end_inset
lexical implication rules
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "Ostler1991"
literal "false"
\end_inset
.
These are rules that control how words used in one context can be used
in a different context.
Can the discovery of these rules be automated? It would seem so: each rule
can be described as a jigsaw-piece; if a certain set of connectors match
the conditions on the input of the rule, then the rule fires, producing
or controlling output.
\end_layout
\begin_layout Standard
This works because rules (in the sense of a rule-engine) can be interpreted
as jigsaw pieces.
Of course, a single rule is just olde-fashioned stimulus-response AI (SRAI).
The difference here is that we have a practical mechanism for learning
rules (out of
\begin_inset Quotes eld
\end_inset
nothing at all
\begin_inset Quotes erd
\end_inset
) as well as a practical mechanism for assembling them.
Jigsaw assembly is parsing: given a set of constraints (a sequence of words)
parsing is the act of finding jigsaw pieces that fit the word-sequence.
Parsing technologies are well-understood.
If a sequence of jigsaw pieces need to be stacked deeper, there are relatively
well-understood technologies for that as well: automated theorem-proving.
A collection of sequents, such as
\begin_inset Formula
\[
L\vee\frac{A,\Gamma\Rightarrow C\quad B,\Gamma\Rightarrow C}{A\vee B,\Gamma\Rightarrow C}\quad\quad R\forall\frac{\Gamma\Rightarrow A\left[x/y\right]}{\Gamma\Rightarrow\forall xA}
\]
\end_inset
can be understood as certain specific jigsaw pieces, with the premises above
the line being
\begin_inset Quotes eld
\end_inset
input
\begin_inset Quotes erd
\end_inset
connectors, conclusions below the line being connectors as well, and theorem-pr
oving (and all of its subtleties, such as cut elimination and efficiency
in general) is the assembly of these jigsaw pieces in a syntactically valid
fashion.
\end_layout
\begin_layout Standard
The concept of lexical implication rules generalizes to that of
\begin_inset Quotes eld
\end_inset
lexical functions
\begin_inset Quotes erd
\end_inset
(LF) of Meaning-Text Theory (MTT).
\begin_inset CommandInset citation
LatexCommand cite
key "Kahane2003"
literal "false"
\end_inset
The MTT is a very well-developed theory of the
\begin_inset Quotes eld
\end_inset
semantic
\begin_inset Quotes erd
\end_inset
layer of linguistics, sitting atop the syntactic layer described above.
What makes it
\begin_inset Quotes eld
\end_inset
semantic
\begin_inset Quotes erd
\end_inset
, and how might it be learned? MTT describes the
\begin_inset Quotes eld
\end_inset
semantic
\begin_inset Quotes erd
\end_inset
layer as a collection of concepts which can be expressed through various
alternative word-choices.
How might these be learned? Such an algorithm is described by Poon & Domingos
\begin_inset CommandInset citation
LatexCommand cite
key "Poon2009"
literal "false"
\end_inset
.
Their algorithm learns synonymous phrases.
it is not unlike what is described above; the only issue there is that
they make the disastrous choice of using lambda-calculus notation for describin
g jigsaw pieces! This appears to lead to pointless complexity and confusion;
a tensorial, type-theoretic function would have been more appropriate.
\end_layout
\begin_layout Standard
Another example for deriving meaning based on connectivity can be found
in the Mihalcea algorithm for associating WordNet word senses to individual
words in a given sentence.
\begin_inset CommandInset citation
LatexCommand cite
key "Mihalcea2005"
literal "false"
\end_inset
Her algorithm is phrased in terms of the Page-Rank algorithm, to flow weights
along edges along a fully connected graph.
Looked at more carefully, this is a probabilistic parsing algorithm: discoverin
g what is connected to what by altering weights on the matrix, until certain
edges are ruled out, are deemed
\begin_inset Quotes eld
\end_inset
unconnectable
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
Texts are not single sentences: texts are paragraphs and pages.
To navigate through a text, one must perform anaphora resolution, or, more
generally, reference resolution, determining when two words in a text refer
to the same entity.
But, in a certain sense, we already have that: the pair-MI algorithm given
earlier can provide a rough cut for how related two things are.
The relation can be sharped by discovering context via MST parsing (although
at this level, it more closely resembles the Michalcea algorithm).
Specificity can is then further heightened in the clustering step.
Rinse, repeat.
\end_layout
\begin_layout Subsection*
Common Sense
\end_layout
\begin_layout Standard
Can this be used to learn common sense? I believe so.
How might this work? Let me illustrate by explaining an old joke:
\begin_inset Quotes eld
\end_inset
Doctor Doctor, it hurts when I do this! Well, don't do that!
\begin_inset Quotes erd
\end_inset
.
The explanation is in the form of a rule, such as those drawn in proof-theory.
The thick horizontal bar separates the premises from the conclusions.
It is labeled as
\begin_inset Quotes eld
\end_inset
Joke
\begin_inset Quotes erd
\end_inset
to indicate what kind of rule it is.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../reco-image/reasoning-joke.eps
lyxscale 60
width 30page%
\end_inset
\end_layout
\begin_layout Standard
The
\begin_inset Quotes eld
\end_inset
sequent
\begin_inset Quotes erd
\end_inset
here is the anaphora connector, which connects the word
\begin_inset Quotes eld
\end_inset
this
\begin_inset Quotes erd
\end_inset
to a specific motor sequence.
Which motor sequence? Well, presumably one that was learned, by automatic
process, to move a limb.
All of the components of this diagram are jigsaw pieces.
All of the pieces can be discovered probabilistically.
All of the connectors can be connected probabilistically.
The learning algorithm shows how to discern structure from what is superficiall
y seems like a chaotic stream of sensory input.
Common sense can be learned.
\end_layout
\begin_layout Standard
\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