#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
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures false
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style tufte
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Messaging
\end_layout
\begin_layout Abstract
Thoughts about messaging and a relationship to grammar.
Some old ideas, rephrased, some new ideas, incomplete.
\end_layout
\begin_layout Section*
Introduction
\end_layout
\begin_layout Standard
Two almost inrelated ideas, and one theme.
\end_layout
\begin_layout Standard
Lets start with an obvious observation: natural language is used to transmit
messages, from one human mind to another.
Language carries messages.
Painfully obviously.
Now pair this with another idea: message-passing algorithms are a good
way of solving NP-complete graphical constraint satisfaction problems.
This pairing suggests a wild insight: that a collection of human minds,
working together, are using message passing as a technique for collectively
solving some difficult problem.
To what degree can this insight be developed into a formal theory of the
mind, and speciffically, a formalm theory of the collective, social mind?
I don't know, and what follows below will be mostly unrelated to that,
and will instead tackle grammar again, the grammar of natural language.
\end_layout
\begin_layout Subsection*
Grammar via Belief Propagation
\end_layout
\begin_layout Standard
This is a reprise of a recurring theme.
The goal is to find effective and tractable computational strategies for
extracting meaning from natural language.
The current work concerns itself with a very basic layer, that of extracting
a lexical grammar, describing the syntax of the language, and a crude level
of semantics that follows there from.
By a
\begin_inset Quotes eld
\end_inset
lexical grammar
\begin_inset Quotes erd
\end_inset
, it is meant that sentences of the language can be broken down into words,
and that the relatioinship between words can be obtained from a lexicon,
that is, from a dictionary where each word can be looked up to discover
the grammatical relationships that word can engage in.
It is useful to note that such lexicons are redily extended to include
idioms, set phrases, institutional expressions, colocations; such multi-word
constructions do not alter the underlying concept.
\end_layout
\begin_layout Standard
Lexicality implies that language can be analyzed in terms of words (or set
phrases,
\emph on
etc.
\emph default
).
But language is also fundamentally statistical and probabilisitic: there
is no ultimate, final truth to syntax and semantics, but only likely meanings
and interpretations.
In this setting, lexicality means not only that language can be viewed
as a graph of relationships between words, but also that the graph can
be factored into local components.
Specifically, each local component consists of a word, and the other nearby
words that it may interact with: a word, and its syntactico-semantically-neares
t neighbors.
\end_layout
\begin_layout Standard
Modern probability theory has a standard formulation using the terminology
and notation of statistical mechanics.
In this formulation, one begins by asserting that the universe is described
by a summation over all possibilities: everything that might happen, can
happen, with some associated probability.
This sum is called the partition function; it is symbolized by
\begin_inset Formula $Z$
\end_inset
, and the partitioning is simply the statement each possibility has a probabilit
y.
For natural language, this just means that every possible sequence of words
(a
\begin_inset Quotes eld
\end_inset
sentence
\begin_inset Quotes erd
\end_inset
) occurs with some probability; ungrammatical sentences have a low, approximatel
y vanishing probability.
\end_layout
\begin_layout Standard
It is a theorem of Boltzmann that partition functions can be written as
sums over exponentials, and that the most likely possibility is given by
maximizing the entropy.
This is not an assumption that has to be artificially forced onto the system;
rather, it is the factual statement that, if you believe in probability,
then there is no other way: it is a theorem.
Combining natural language with probability then suggests that it is fruitful
to articulate the statistical mechanics thereof.
\end_layout
\begin_layout Standard
In what follows, the formal grammar of choice is Link Grammar.
\begin_inset CommandInset citation
LatexCommand cite
key "Sleator1991,Sleator1993"
literal "true"
\end_inset
This choice is made for several reasons.
First, one may argue that the actual choice of a grammar formalism is immateria
l, as all grammars are effectvely inter-convertable between one-another
by algorithmic means.
Thus, the choice of formalism boils down to convenience; what notational
system is most convenient? Here, Link Grammar stands out.
First, it is effectively a form of dependency grammar, and so is natural
to linguists trained in that tradition.
Second, by expressing grammar in terms of link types, it leverages type
theory, and has a very natural bridge to categorial grammars and pregroup
grammars: link types are just the type-theoretical types of the relationships
that categorial grammars articulate.
As categorial grammars are normally considered to be a form of phrase-structure
grammars, exposing the relationships as types provides the natural bridge
between the phrase-structure and dependency grammar schools of thought.
Finally, Link Grammar is appealing from the tradition of mathematics: Link
Grammar is a tensor algebra.
Lexical entries are tensors, and lexical entries are composed into sentences
in exactly the same way that one composes tensors in a tensor algebra.
It is precisely this tensorial nature that then enables Curry–Howard correspond
ance; Link Grammar is the
\begin_inset Quotes eld
\end_inset
internal language
\begin_inset Quotes erd
\end_inset
of monoidal categories.
\end_layout
\begin_layout Standard
The next section articulates the statistical mechanics Link Grammar.
This presents Link Grammar as both a constraint-statistfaction problem
as well as a maximum entropy problem.
This is followed by a section looking at the belief-propagation aglorithm,
inspired by and developed along the lines described by Mézard and Mora
\begin_inset CommandInset citation
LatexCommand cite
key "Mezard2008"
literal "true"
\end_inset
.
\end_layout
\begin_layout Subsection*
A Frequentist Model of Language
\end_layout
\begin_layout Standard
The goal of this section is to formulate a model of language, simultaneously
invoking both its graph-theoretical and statistical properties.
This mostly requires the introduction and review of fairly mainstream ideas
and notation, and an articulation of the notation so that it's meaning
becomes clear.
\end_layout
\begin_layout Standard
Consider first a word sequence
\begin_inset Formula $\underline{w}=\left(w_{1},\cdots,w_{n}\right)$
\end_inset
which can be taken to be a sentence that is
\begin_inset Formula $n$
\end_inset
words long; it need not be grammatical; that is, it need not be a valid
sentence.
One possible way of defining the statistics of language is to claim that
the probability of this word sequence is
\end_layout
\begin_layout Standard
\begin_inset Formula
\begin{equation}
P\left(\underbar{w}\right)=\lim_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}\delta\left(\underbar{w},\underbar{w}_{i}\right)\label{eq:frequentist}
\end{equation}
\end_inset
where
\begin_inset Formula $N$
\end_inset
is the number of sentences in a sample corpus representative of the language,
so that each
\begin_inset Formula $\underbar{w}_{i}$
\end_inset
is a grammatically valid sentence.
The above states that, basically, a word sequence
\begin_inset Formula $\underbar{w}$
\end_inset
is valid if and only if it occurs in the sample corpus; else it is not.
This is a naive and simplistic definition of language, dounded on a frequentist
view of probability.
It is inadequate on multiple fronts.
It's worth articulating these, lest they become an impediement later.
\end_layout
\begin_layout Itemize
The notation above assigned a fixed sentence length of
\begin_inset Formula $n$
\end_inset
.
This seems to be a notational inconvenience, rather than a fundamental
limitation.
From here on, sentences are assumed to be varying in length, and can be
chosen as desired.
\end_layout
\begin_layout Itemize
Morphology is ignored.
For the most part, this should not be an impediment; Link Grammar is able
to deal adequately with morpho-syntax, and even enforce phonetic agreement,
so this presents no particular stumbling block.
\end_layout
\begin_layout Itemize
Semantic structure on a scale larger than one sentence is ignored.
Most of what follows will be focused on syntax, and the lower reaches of
semantics, and so this simplification seems reasonable at this time.
\end_layout
\begin_layout Itemize
Corpora are assumed to be finite in size.
This is naturally the case for natural language, but it can cause difficulties
for certain mathematical approaches, which are more naturally expressed
in the continuum limit.
This is also glossed over, as it rarely presents any practical difficulties.
By contrast, formal languages with generative grammars are capable of producing
infinite corpora, and so the distinction between finite and infinite can
be blurred.
\end_layout
\begin_layout Itemize
The above definition completely ignores the obvious fact that language is
compositional: one can form sentences from sentence fragments; phrases
can have meanings; language is a collection of recurring word-patterns
plainly visible at a sub-sentence level.
Yet, one of the goals of research into linguistics is to elucidate the
compositional structure of language.
\end_layout
\begin_layout Standard
For all of these various reasons, the above probabilistic description of
language is patently absurd.
Yet it is often quoted as a foundational cornerstone, and so is worth repeating
here.
Despite these abusrdities, one might like the final formulation of language
be such that eqn
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:frequentist"
\end_inset
, or at least something similar, can arise naturally from the theory.
\end_layout
\begin_layout Standard
For the remainder of this section, the assumption is made that the compostional
nature of language can be adequately captured by means of a lexis.
This is closely related too the assumption that language is syntactic,
but is, in some sense, strictly weaker, or, at least, should be interpreted
in a broader setting.
A lexical description of language is one where each word is associated
with a collection of properties and relations that specify how that word
can occur in grammatical contexts, and how rough, basic meaning can be
pinned down.
This is in contrast to
\begin_inset Quotes eld
\end_inset
syntax
\begin_inset Quotes erd
\end_inset
, which is usually taken to be synonym for the existence of a (planar) parse
tree.
The point here is that the graphical structure of language need not be tree-like
: the parse may contain loops; it may contain non-planar edges between words,
and it may contain relations operating at different conceptual levels.
For example, graphical relations enforcing phonetic agreement might typically
operate at a different level than count and tense agreement, and that in
turn operates at a different level than anaphora agreement.
\end_layout
\begin_layout Standard
It is possible that natural language has structure that cannot be captured
by probabilistic graphical representations.
That author, however, is currently unable to imagine what this might be.
Therefore, in all that follows, the assumption is made that the entirety
of meaning and structure in language can be captured by graphs that encode
functions and relations with statistical, probabilistic properties.
\end_layout
\begin_layout Subsection*
Link Grammar
\end_layout
\begin_layout Standard
The remainder of this paper assumes that Link Grammar is well suited to capture
most of the lexical, syntactic properties of language.
There are multiple reasons that this assumption seems justified.
These include:
\end_layout
\begin_layout Itemize
The Link Grammar formalism can be more-or-less directly related to dependency
grammars; it can be taken as a certain kind of dependency grammar, and
is rich enough that it can be mapped or translated to different styles
of dependency.
\end_layout
\begin_layout Itemize
The Link Grammar formalism can be directly related to categorial and pregroup
grammar-style grammars; insofar as those can be taken as examples of phrase-str
ucture grammar, a route exists to map Link Grammar into phrase structure,
and the kinds of phenomena exhibited there.
\end_layout
\begin_layout Itemize
Link Grammar bridges naturally to Lambek calculus.
The link types of Link Grammar can be interpreted as the types of type
theory; the
\begin_inset Quotes eld
\end_inset
disjuncts
\begin_inset Quotes erd
\end_inset
of Link Grammar are manifestly tensorial, and so Link Grammar can be taken
as a kind of tensor algebra.
As such, it can be understood via category theory: Link Grammar is the
\begin_inset Quotes eld
\end_inset
internal language
\begin_inset Quotes erd
\end_inset
of a monoidal category.
This makes it simultaneously very general, and abstractly powerful.
\end_layout
\begin_layout Standard
To summarize, the Link Grammar formalism lies at the nexus of a multitude
of different viewpoints and theories of language.
One need not go very far, or work particularly hard, to see how it captures
different linguistic (and mathematical) phenomena and theories.
\end_layout
\begin_layout Subsection*
Statistical Mechanics of Link Grammar
\end_layout
\begin_layout Standard
Lexical entries are then of the form
\begin_inset Formula
\[
\left(\left(w,d\right),h\right)
\]
\end_inset
where
\begin_inset Formula $w$
\end_inset
is a word,
\begin_inset Formula $d$
\end_inset
is a disjunct
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
A definition of
\begin_inset Quotes eld
\end_inset
disjunct
\begin_inset Quotes erd
\end_inset
will be given shortly; the next few paragraphs do not rely on a precise
definition, and hold true generally for any lexical formulation.
In particular, one can imagine that a disjunct is an n-gram or a skip-gram;
this is useful, as it makes contact with nueral-net/deep-learning approaches
to language.
\end_layout
\end_inset
describing one of the grammatical relationships the word can engage in,
and
\begin_inset Formula $h$
\end_inset
is a
\begin_inset Quotes eld
\end_inset
cost
\begin_inset Quotes erd
\end_inset
or entropy associated with this word-disjunct pair.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
A single word might be associated with multiple disjuncts.
During grammatical analysis, only one of these may be used at a time; thus
the disjuncts are disjoined from one-another, whence the name.
\end_layout
\end_inset
It is convenient to write the cost as a function of the word-disjunct pair:
\begin_inset Formula $h=h\left(w,d\right)$
\end_inset
as only the lowest cost is meaningful, and it does not make sense for a
given disjunct to have more than one cost.
Impossible word-disjunct pairs have infinite cost, rendering their probability
zero.
That is, the probability of a word-disjunct pair, up to an overall normalizatio
n, can be taken as
\begin_inset Formula
\[
P\left(w,d\right)\sim\exp-h\left(w,d\right)
\]
\end_inset
\end_layout
\begin_layout Standard
The probability of a word sequence
\begin_inset Formula $\underbar{w}$
\end_inset
is then
\begin_inset Formula
\[
P\left(\underbar{w}\right)=\frac{1}{Z}\sum_{\left(d_{1},\cdots,d_{n}\right)}\prod_{j=1}^{n}P\left(w_{j},d_{j}\right)\Delta\left(d_{1},\cdots,d_{n}\right)
\]
\end_inset
where the formal grammar is encoded as a boolean satisfiability factor
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is just the indicator function for a predicate.
Common alternate notation is
\begin_inset Formula $\mathbb{I}$
\end_inset
or
\begin_inset Formula $\mathbf{1}$
\end_inset
.
There is an implicit assumption that a parse, if it exists, is unique.
If this is not the case, and multiple distinct parses exist with a given
fixed
\begin_inset Formula $\underbar{d}$
\end_inset
, then
\begin_inset Formula $\Delta$
\end_inset
needs to count these with multiplicity.
\end_layout
\end_inset
\begin_inset Formula
\[
\Delta\left(d_{1},\cdots,d_{n}\right)=\begin{cases}
1 & \left(d_{1},\cdots,d_{n}\right)\mbox{ is a valid parse}\\
0 & \mbox{otherwise}
\end{cases}
\]
\end_inset
The probabilistic aspects, that some parses are more likely than others,
are encoded in the lexical factors
\begin_inset Formula $P\left(w,d\right)$
\end_inset
.
Replacing probabilities by their logs, one can equivalently write
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
P\left(\underbar{w}\right)=\frac{1}{Z}\sum_{\underbar{d}}\Delta\left(\underbar{d}\right)\exp-\mathcal{A}\left(\underbar{w},\underbar{d}\right)
\]
\end_inset
using as shorthand
\begin_inset Formula $\underbar{d}=\left(d_{1},\cdots,d_{n}\right)$
\end_inset
as the string of
\begin_inset Formula $n$
\end_inset
disjuncts associated with the
\begin_inset Formula $n$
\end_inset
words
\begin_inset Formula $\underbar{w}=\left(w_{1},\cdots,w_{n}\right)$
\end_inset
.
The sum is taken over all possible lists
\begin_inset Formula $\underbar{d}$
\end_inset
of disjuncts
\begin_inset Formula $d_{j}$
\end_inset
; the
\begin_inset Formula $\Delta$
\end_inset
term excludes those sequences that do not correspond to valid parses in
the formal grammar.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The summation
\begin_inset Formula $\sum_{\underbar{d}}\Delta\left(\underbar{d}\right)$
\end_inset
has the form that makes it clear that
\begin_inset Formula $\Delta$
\end_inset
has the form of an integration measure.
An obvious generalization is to replace it by a fuzzy or fractional measure.
\end_layout
\end_inset
The normalization
\begin_inset Formula $Z$
\end_inset
is famously known as the partition function.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
See Wikipedia.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
The
\begin_inset Formula $\mathcal{A}$
\end_inset
is the
\begin_inset Quotes eld
\end_inset
action
\begin_inset Quotes erd
\end_inset
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This word comes from physics, specifically, the Lagrangian formulation of
classical mechanics.
\end_layout
\end_inset
, given by
\begin_inset Formula
\[
\mathcal{A}\left(\underbar{w},\underbar{d}\right)=\sum_{j=1}^{n}h\left(w_{j},d_{j}\right)
\]
\end_inset
As the cost
\begin_inset Formula $h$
\end_inset
is infinite for those words-disjunct pairs that do not occur in the lexis,
this sum excludes impossible pairings; no additional effort is needed to
otherwise exclude them.
\end_layout
\begin_layout Standard
Although the above formulation uses the word
\begin_inset Quotes eld
\end_inset
disjunct
\begin_inset Quotes erd
\end_inset
for
\begin_inset Formula $d_{j}$
\end_inset
, it was intentionally vague; none of the development required a more precise
definition.
In a lexical formulation, the term
\begin_inset Formula $\Delta\left(\underbar{d}\right)$
\end_inset
can also be factorized locally, as it is determined by a product of lexical
elements.
In the Link Grammar formulation, the lexical elements are explicitly graphical:
a vertex surrounded by half-edges or connectors, with two half-edges required
to make a full edge (link) connecting two vertices.
Algebraically, a disjunct is a list of connectors, which either can connect,
or not.
That is, an arity-
\begin_inset Formula $m$
\end_inset
disjunct is a conjunction of connectors
\begin_inset Formula $c$
\end_inset
written as
\begin_inset Formula
\[
d=c_{1}\&\cdots\&c_{m}
\]
\end_inset
with each connector being a half-link, that is, a link with a direction
indicator:
\begin_inset Formula
\[
c=\left(\ell,\sigma\right)
\]
\end_inset
with
\begin_inset Formula $\ell\in L$
\end_inset
being one of the Link Grammar link types, and
\begin_inset Formula $\sigma\in\left\{ -,+\right\} $
\end_inset
being a direction indicator.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
In standard link grammar, these direction indicators point to the left and
right, respectively, and encode the directional dependence of word order.
For languages with free word-order, it is convenient to use symbols for
head and tail instead of, or in addition to the direction indicators.
Head/tail markings are also useful for indicating dependency directions,
when these are desired, or for indicating catena.
\end_layout
\end_inset
Define the conjugate direction indicator
\begin_inset Formula $\bar{\sigma}$
\end_inset
as
\begin_inset Formula
\[
\bar{\sigma}=\begin{cases}
- & \mbox{if }\sigma=+\\
+ & \mbox{if }\sigma=-
\end{cases}
\]
\end_inset
Thus, two connectors
\begin_inset Formula $c_{a}$
\end_inset
and
\begin_inset Formula $c_{b}$
\end_inset
connect if the link types match, and the direction indicators are conjugate.
Thus, one may define
\begin_inset Formula
\[
\delta\left(c_{a},c_{b}\right)=\delta\left(\ell_{a},\ell_{b}\right)\delta\left(\sigma_{a},\bar{\sigma}_{b}\right)
\]
\end_inset
A sentence is parsable when all connectors are connectable, and so
\begin_inset Formula
\begin{equation}
\Delta\left(\underbar{d}\right)=\Delta\left(d_{1},\cdots,d_{n}\right)=\prod_{d_{j}=\left(c_{j1}\&\cdots\&c_{jm}\right)}\delta\left(c_{jk},c_{j^{\prime}k^{\prime}}\right)\label{eq:factor-graph}
\end{equation}
\end_inset
with the product being over all of the individual connectors in each disjunct.
That is,
\begin_inset Formula $\Delta=1$
\end_inset
if and only if every connector can be uniquely paired with some other connector
, and no dangling connectors remain.
To avoid double-counting, the product is meant to extend only over the
links (edges) in the graph, with one term per edge.
\end_layout
\begin_layout Standard
It is from this that the interpretation as a tensor algebra arises: Each
disjunct
\begin_inset Formula $d=d_{j}$
\end_inset
can be thought of as a tensor having
\begin_inset Formula $m$
\end_inset
indexes on it; each index must be contracted with some other index on some
other tensor.
The tensor indexes are always contracted pair-wise, and once connected
(consumed) cannot be connected to any other index.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is the content of the
\begin_inset Quotes eld
\end_inset
no cloning
\begin_inset Quotes erd
\end_inset
theorem.
\end_layout
\end_inset
A parse is valid if and only if
\begin_inset Formula $\Delta$
\end_inset
is a scalar, having no remaining uncontracted indexes.
Unlike symmetric tensor algebras, the connectors are directional: they
can contract only to the left, or to the right.
\end_layout
\begin_layout Standard
Implicit in the above is a further constraint that the parse graph be a
planar graph,
\emph on
i.e.
\emph default
that there is a no-links-crossing constraint.
This constraint is very useful for controlling the combinatorial explosion
of possible parses; unfortunately, it is a non-local constraint, and thus
cannot be easily written in a factorizable manner.
Rather than tackling the difficulty of obtaining an adequate notation for
such a non-local constraint, it is easier, for now, to implicitly keep
this in the background.
There are multiple techniques that can be used when dealing with this;
these, and planarity in general, are for now secondary concerns.
\end_layout
\begin_layout Standard
Taking the logarithm, so as to turn products into sums, the constraint can
be written in the form
\begin_inset Formula
\[
\Delta\left(\underbar{d}\right)=\Delta\left(d_{1},\cdots,d_{n}\right)=\exp-\left[\sum_{d_{j}=\left(c_{j1}\&\cdots\&c_{jm}\right)}\Xi\left(c_{jk},c_{j^{\prime}k^{\prime}}\right)\right]
\]
\end_inset
where
\begin_inset Formula $\Xi$
\end_inset
can be interpreted as a kinetic term, having a value of zero when
\begin_inset Formula $c_{jk}$
\end_inset
can be contracted with
\begin_inset Formula $c_{j^{\prime}k^{\prime}}$
\end_inset
and is infinite otherwise.
\end_layout
\begin_layout Standard
In this form, the constraint can be pulled into the action
\begin_inset Formula $\mathcal{A}$
\end_inset
, redefining it as a summation of local interactions:
\begin_inset Formula
\[
\mathcal{A}\left(\underbar{w},\underbar{d}\right)=\sum_{j=1}^{n}\left[h\left(w_{j},d_{j}\right)+\sum_{d_{j}=\left(c_{j1}\&\cdots\&c_{jm}\right)}\Xi\left(c_{jk},c_{j^{\prime}k^{\prime}}\right)\right]
\]
\end_inset
The intended reading of the above expression is that it is a summation over
Feynmann diagrams, with
\begin_inset Formula $h$
\end_inset
corresponding to a
\begin_inset Formula $m$
\end_inset
-point vertex (when the disjunct
\begin_inset Formula $d_{j}$
\end_inset
has arity
\begin_inset Formula $m$
\end_inset
), and the
\begin_inset Formula $\Xi$
\end_inset
terms corresponding to propagators connecting vertices.
The propagators are exactly the Link Grammar links, weighted in such a
way that they contribute zero to the action, when the link is allowed,
and otherwise contributing infinity.
\end_layout
\begin_layout Standard
The partition function can then be formally written as
\begin_inset Formula
\[
Z=\sum_{\underbar{w},\underbar{d}}\exp-\mathcal{A}\left(\underbar{w},\underbar{d}\right)
\]
\end_inset
with the summation over
\begin_inset Formula $\underbar{w}$
\end_inset
running over all possible word-sequences of arbitrary length.
As is conventional in partition function formulations, it is convenient
to introduce external currents
\begin_inset Formula $\underbar{J}$
\end_inset
so that variational principles can be used to extract quantities of interest.
Thus, for example, writing
\begin_inset Formula
\[
Z\left[J\right]=\sum_{\underbar{w},\underbar{d}}\exp-\mathcal{A}\left(\underbar{w},\underbar{d}\right)+\underbar{J}\cdot\underbar{w}
\]
\end_inset
and taking a variation
\begin_inset Formula $\delta J$
\end_inset
along the direction
\begin_inset Formula $\underbar{w}$
\end_inset
, the limit of the logarithmic derivative gives the probability:
\begin_inset Formula
\[
P\left(\underbar{w}\right)=\frac{1}{Z}\left.\frac{\delta Z\left[J\right]}{\delta J}\right|_{J=0}=\frac{1}{Z}\sum_{\underbar{d}}\exp-\mathcal{A}\left(\underbar{w},\underbar{d}\right)
\]
\end_inset
The
\begin_inset Quotes eld
\end_inset
current
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $J$
\end_inset
is just an algebraic device, a trick, used to single out one particular
word-sequence out of the infinite sum.
It is convenient to also introduce other currents coupling to other parts
of the action, so that the variational principle can be used to extract
other quantities of interest.
The logarithm of the partition function
\begin_inset Formula $-\ln Z$
\end_inset
is the free energy; standard algebraic variations can be used to extract
an entire zoo of
\begin_inset Quotes eld
\end_inset
thermodynamic
\begin_inset Quotes erd
\end_inset
variables, including correlation functions, mean values, mean-square deviations
and the like.
\end_layout
\begin_layout Subsection*
Grammar via Belief Propagation
\end_layout
\begin_layout Standard
The learning task begins by noting that the valid disjuncts are not known
\emph on
a priori
\emph default
, they must be discovered.
To accomplish this,
\begin_inset CommandInset citation
LatexCommand cite
key "Braunstein2002"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
Its a constraint-satisfaction problem.
Equation
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:factor-graph"
\end_inset
defines a factorization of the constraints, that is, a factor-graph.
For a given parse, the factor graph is a bipartite graph, connecting elements
\begin_inset Formula $d\in D$
\end_inset
(the disjuncts) to elements
\begin_inset Formula $\ell\in L$
\end_inset
(the links).
In the factor graph, each link
\begin_inset Formula $\ell$
\end_inset
corresponds to a vertex, and, of course, links are always arity-2.
To be precise, the vertices of the factor graph are taken from
\begin_inset Formula $V=D\cup L$
\end_inset
and the edges are taken from
\begin_inset Formula $E=\left\{ \left(d,\ell\right)|d\in D\mbox{ and }d=c_{1}\&\cdots\&c_{m}\mbox{ and }c_{k}\in\ell\right\} $
\end_inset
.
This last just states that an edge in the factor graph must connect some
connector (half-link) on a disjunct to the link (as links are just pairs
of half-links).
\end_layout
\begin_layout Standard
XXX Need figure here XXX.
\end_layout
\begin_layout Standard
Here are the belief-prop eqns:
\end_layout
\begin_layout Standard
The first step is to replace each possible connection-pair
\begin_inset Formula $\delta\left(c_{jk},c_{j^{\prime}k^{\prime}}\right)$
\end_inset
by a belief of the possibility
\begin_inset Formula $p\left(c_{jk},c_{j^{\prime}k^{\prime}}\right)$
\end_inset
of such a connection being present, interpreted as a probability:
\begin_inset Formula $0\le p\le1$
\end_inset
with the goal of eventually driving each connectable pair to be zero or
one.
Similarly
\end_layout
\begin_layout Standard
x
\end_layout
\begin_layout Standard
if only one link-type, then its an unlablled dependency parse, and the solution
is mean-field or Markovian.
To make it tractable use the page-rank algorithm...
\end_layout
\begin_layout Standard
x
\end_layout
\begin_layout Standard
x but the shafiness of it all ....
\end_layout
\begin_layout Standard
x
\end_layout
\begin_layout Standard
x if multiple link types....
\end_layout
\begin_layout Standard
x
\end_layout
\begin_layout Standard
The other thing to point out is due to loops, etc.
it won't be naive belief propagation, but it will be Survey Propagation,
as mentioned there...
\end_layout
\begin_layout Section*
The End
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "lang"
options "tufte"
\end_inset
\end_layout
\end_body
\end_document