#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 true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\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 plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Entropy
\end_layout
\begin_layout Abstract
The language-learning diary entertains a recurring theme of entropy and
various related principles.
Although there are many, many, many resources for these concepts, it seems
convenient to put them here, all in one place, in an overview form, as
a handy quick-reference and refresher.
The content here is extracted from various texts.
\end_layout
\begin_layout Section
Fast Overview
\end_layout
\begin_layout Standard
A generic fast overview.
The rest of this text is organized as ...
\end_layout
\begin_layout Subsection
Partition Function
\end_layout
\begin_layout Standard
See Wikipedia
\begin_inset Quotes eld
\end_inset
Partition function
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "WP-Partition"
literal "true"
\end_inset
for more.
\end_layout
\begin_layout Itemize
States denoted by
\begin_inset Formula $\sigma$
\end_inset
(spins, from Ising model) with distribution
\begin_inset Formula $p\left(\sigma\right)$
\end_inset
.
\end_layout
\begin_layout Itemize
In machine learning, one writes
\begin_inset Formula $x$
\end_inset
for
\begin_inset Formula $\sigma$
\end_inset
.
In probability theory, one writes
\begin_inset Formula $X=x$
\end_inset
for
\begin_inset Formula $\sigma$
\end_inset
, where
\begin_inset Formula $X$
\end_inset
is distribution, and
\begin_inset Formula $x$
\end_inset
is a specific sampling of that distribution.
That is,
\begin_inset Formula $p\left(\sigma\right)$
\end_inset
is the same thing as
\begin_inset Formula $P\left(X=x\right)$
\end_inset
.
\end_layout
\begin_layout Itemize
\begin_inset Formula $\sigma$
\end_inset
is an indexed set, with
\begin_inset Formula $N$
\end_inset
elements.
As such, one can pretend that it is an
\begin_inset Formula $N$
\end_inset
–dimensional vector, which is fine
\begin_inset Quotes eld
\end_inset
for most practical purposes
\begin_inset Quotes erd
\end_inset
, but in rare cases can lead to confusion.
\end_layout
\begin_layout Itemize
One is often (usually) interested in the large–
\begin_inset Formula $N$
\end_inset
limit, i.e.
\begin_inset Formula $N\gg1$
\end_inset
i.e.
\begin_inset Formula $N\to\infty$
\end_inset
states.
\end_layout
\begin_layout Itemize
The
\begin_inset Quotes eld
\end_inset
energy
\begin_inset Quotes erd
\end_inset
of a state is
\begin_inset Formula $E\left(\sigma\right)=-\log p\left(\sigma\right)+\mbox{const}.$
\end_inset
\end_layout
\begin_layout Itemize
The density of states is:
\begin_inset Formula $\rho(E)=\sum_{\sigma}\delta(E-E(\sigma))$
\end_inset
\end_layout
\begin_layout Itemize
Total entropy is
\begin_inset Formula $S\left(E\right)=\log\rho\left(E\right)$
\end_inset
\end_layout
\begin_layout Itemize
Both the energy and the entropy contain the leading large-
\begin_inset Formula $N$
\end_inset
term i.e.
they are extensive properties.
\end_layout
\begin_layout Itemize
Without loss of generality, can write the Boltzmann distribution
\begin_inset Formula
\[
p\left(\sigma|\beta\right)=\frac{1}{Z\left(\beta\right)}\exp-N\sum_{i}\beta_{i}H_{i}\left(\sigma\right)
\]
\end_inset
where there are
\begin_inset Formula $M$
\end_inset
parameters
\begin_inset Formula $\beta_{i}$
\end_inset
called order parameters, Lagrange multipliers, etc.
and the
\begin_inset Formula $H_{i}\left(\sigma\right)$
\end_inset
are constants of motion.
\begin_inset Quotes eld
\end_inset
Without loss of generality
\begin_inset Quotes erd
\end_inset
means that any probability distribution can always be written in the above
form.
\end_layout
\begin_layout Itemize
In probability theory and information geometry, one often writes
\begin_inset Formula $\theta$
\end_inset
instead of
\begin_inset Formula $\beta$
\end_inset
as the parameter, and
\begin_inset Formula $f_{i}$
\end_inset
instead of
\begin_inset Formula $H_{i}$
\end_inset
.
\end_layout
\begin_layout Itemize
In machine learning, one often writes
\begin_inset Formula $w$
\end_inset
instead of
\begin_inset Formula $\beta$
\end_inset
.
In this case,
\begin_inset Formula $w$
\end_inset
is a
\begin_inset Quotes eld
\end_inset
weight vector
\begin_inset Quotes erd
\end_inset
, allowing a neural-net interpretation.
\end_layout
\begin_layout Itemize
The partition function is
\begin_inset Formula
\[
Z\left(\beta\right)=\sum_{\sigma}\exp-N\sum_{i}\beta_{i}H_{i}\left(\sigma\right)
\]
\end_inset
\end_layout
\begin_layout Itemize
The above describes a
\begin_inset Quotes eld
\end_inset
pure state
\begin_inset Quotes erd
\end_inset
, where the parameters
\begin_inset Formula $\beta{}_{i}$
\end_inset
are fixed constants.
This is in contrast to a
\begin_inset Quotes eld
\end_inset
mixed state
\begin_inset Quotes erd
\end_inset
, which is a distribution over
\begin_inset Formula $\beta$
\end_inset
.
\end_layout
\begin_layout Subsection
Fisher Information Metric
\end_layout
\begin_layout Standard
See Wikipedia,
\begin_inset Quotes eld
\end_inset
Fisher Information Metric: for details.
For a finite set of probabilities, we have
\end_layout
\begin_layout Itemize
Normalization:
\begin_inset Formula $\sum_{i}p_{i}=1$
\end_inset
\end_layout
\begin_layout Itemize
Entropy:
\begin_inset Formula $H=\sum_{i}p_{i}\log p_{i}$
\end_inset
\end_layout
\begin_layout Itemize
Metric: write
\begin_inset Formula $\psi_{i}=\sqrt{p_{i}}$
\end_inset
Then the normalization becomes
\begin_inset Formula $\sum_{i}\psi_{i}^{2}=1$
\end_inset
is an octant of a sphere.
The flat space Eucliden metric, projected onto the sphere, is the Fisher
information metric.
\end_layout
\begin_layout Section
Various definitions of entropy
\end_layout
\begin_layout Standard
XXX TODO there are other entropies, e.g.
microcanonincal, etc.
define them too.
\end_layout
\begin_layout Section
Geometric interpretations of Entropy
\end_layout
\begin_layout Standard
Confused attempts to find gemoetric interpretations.
\end_layout
\begin_layout Subsection
From Banach norms
\end_layout
\begin_layout Standard
I've never seen the below set into writing before.
I'm not sure what it means.
Given a set of probabilities
\begin_inset Formula $p_{i}$
\end_inset
, define the sum
\begin_inset Formula
\[
s_{q}=\sum_{i}p_{i}^{q}
\]
\end_inset
for some number
\begin_inset Formula $q$
\end_inset
.
The first derivative is
\begin_inset Formula
\begin{align*}
\left.\frac{d}{dq}s_{q}\right|_{q=1}= & \left.\frac{d}{dq}\sum_{i}\exp q\log p_{i}\right|_{q=1}\\
= & \left.\sum_{i}p_{i}^{q}\log p_{i}\right|_{q=1}\\
= & \sum_{i}p_{i}\log p_{i}
\end{align*}
\end_inset
which is the conventional entropy.
The Banach space
\begin_inset Formula $\ell_{q}$
\end_inset
norm is
\begin_inset Formula
\[
\ell_{q}=\left[s_{q}\right]^{1/q}
\]
\end_inset
and so
\begin_inset Formula
\begin{align*}
\frac{d}{dq}\ell_{q}= & \frac{d}{dq}\exp\frac{1}{q}s_{q}\\
= & \ell_{q}\frac{d}{dq}\frac{s_{q}}{q}\\
= & \ell_{q}\left(\frac{-s_{q}}{q^{2}}+\frac{1}{q}\frac{ds_{q}}{dq}\right)
\end{align*}
\end_inset
Then evaluating at
\begin_inset Formula $q=1$
\end_inset
one gets
\begin_inset Formula
\begin{align*}
\left.\frac{d}{dq}\ell_{q}\right|_{q=1}= & -\left(\sum_{i}p_{i}\right)^{2}+\sum_{i}p_{i}\log p_{i}\\
= & -1+\sum_{i}p_{i}\log p_{i}
\end{align*}
\end_inset
assuming that
\begin_inset Formula $\sum_{i}p_{i}=1$
\end_inset
for conventional probabilities.
\end_layout
\begin_layout Standard
This reinterprets the entropy as a kind of tangent vector.
What is the interpretation of that tangent vector? What does it
\begin_inset Quotes eld
\end_inset
mean
\begin_inset Quotes erd
\end_inset
?
\end_layout
\begin_layout Section
Zipf's Law, Hidden variable models
\end_layout
\begin_layout Standard
Zipf's law can arise whenever one has that some (not necessarily all) of
the order parameters are
\begin_inset Quotes eld
\end_inset
rapidly fluctuating
\begin_inset Quotes erd
\end_inset
, or are
\begin_inset Quotes eld
\end_inset
unknown
\begin_inset Quotes erd
\end_inset
, or are
\begin_inset Quotes eld
\end_inset
latent
\begin_inset Quotes erd
\end_inset
and must be
\begin_inset Quotes eld
\end_inset
averaged over
\begin_inset Quotes erd
\end_inset
to obtain a distribution.
The primary reference for this section is Schwab,
\emph on
et al
\emph default
,
\begin_inset Quotes eld
\end_inset
Zipf’s law and criticality in multivariate data without fine-tuning
\begin_inset Quotes erd
\end_inset
.
\begin_inset CommandInset citation
LatexCommand cite
key "Schwab2014"
literal "true"
\end_inset
See also Aitchison
\emph on
et al
\emph default
.,
\begin_inset Quotes eld
\end_inset
Zipf's Law Arises Naturally When There Are Underlying, Unobserved Variables
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "Aitchison2016"
literal "true"
\end_inset
for a less physics-oriented exposition.
\end_layout
\begin_layout Standard
Both Aitchison and also Mora
\emph on
etal
\emph default
.
\begin_inset Quotes eld
\end_inset
Are biological systems poised at criticality?
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "Mora2011"
literal "true"
\end_inset
articulate relationships to Ising models.
\end_layout
\begin_layout Subsection
Zipf's Law
\end_layout
\begin_layout Standard
A quick articulation of Zipf's law, based on
\begin_inset CommandInset citation
LatexCommand cite
key "Aitchison2016"
literal "true"
\end_inset
and
\begin_inset CommandInset citation
LatexCommand cite
key "Mora2011"
literal "true"
\end_inset
:
\end_layout
\begin_layout Itemize
Zipf's law is the statement that
\begin_inset Formula $p\left(\sigma\right)\sim1/\mbox{rank}\left(\sigma\right)$
\end_inset
.
\end_layout
\begin_layout Itemize
Converting to energy notation, where
\begin_inset Formula $E=E\left(\sigma\right)=-\log p\left(\sigma\right)$
\end_inset
as before, one can write Zipf's law as
\begin_inset Formula
\[
\log\mbox{ rank}\left(E\right)=E+const
\]
\end_inset
\end_layout
\begin_layout Itemize
The rank of a given, fixed state
\begin_inset Formula $\sigma$
\end_inset
can directly understood as the number of states
\begin_inset Formula $n\left(E\right)$
\end_inset
with energy less than
\begin_inset Formula $E=E\left(\sigma\right)$
\end_inset
.
That is,
\begin_inset Formula
\[
\mbox{rank}\left(\sigma\right)=n\left(E\left(\sigma\right)\right)=\int_{-\infty}^{E\left(\sigma\right)}dE^{\prime}\rho\left(E^{\prime}\right)
\]
\end_inset
where
\begin_inset Formula $\rho(E)$
\end_inset
is the density of states, as before.
\end_layout
\begin_layout Itemize
Equivalently, the derivative of the rank is exactly the density of states:
\end_layout
\begin_layout Itemize
\begin_inset Formula
\[
\frac{d\mbox{ rank}\left(E\right)}{dE}=\rho(E)=\sum_{\sigma}\delta(E-E(\sigma))
\]
\end_inset
\end_layout
\begin_layout Itemize
Combining the above expressions and solving gives that
\begin_inset Formula
\[
\log\mbox{ rank}\left(E\right)=E+\log P_{s}\left(E\right)
\]
\end_inset
where
\begin_inset Formula $P_{s}\left(E\right)=e^{-E}n\left(E\right)$
\end_inset
is a smoothed, energy-weighted probability of states.
This relation is exact (i.e.
is independent of Zipf's law).
\end_layout
\begin_layout Itemize
Zipf's law can thus be written as
\begin_inset Formula
\[
P_{s}\left(E\right)=const.
\]
\end_inset
This enables practical calculations on distributions (next section).
\end_layout
\begin_layout Itemize
Equivalently, Zipf's law may be written as
\begin_inset Formula
\[
n\left(E\right)\sim\exp E
\]
\end_inset
That is, the number of states below energy
\begin_inset Formula $E$
\end_inset
is expanding exponentially.
\end_layout
\begin_layout Subsection
Deriving Zipf's Law
\end_layout
\begin_layout Standard
The derivation of Zipf's law from latent variables is given by Schwab
\emph on
etal
\emph default
.
\begin_inset CommandInset citation
LatexCommand cite
key "Schwab2014"
literal "true"
\end_inset
and is summarixed below.
Aitchison
\emph on
etal
\emph default
.
\begin_inset CommandInset citation
LatexCommand cite
key "Aitchison2016"
literal "true"
\end_inset
claim to have a more general proof.
\end_layout
\begin_layout Itemize
A
\begin_inset Quotes eld
\end_inset
latent variable
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $\theta$
\end_inset
(or a set
\begin_inset Formula $\theta_{i}$
\end_inset
of them) are hidden parameters that govern the observed distribution; namely,
that
\begin_inset Formula
\[
p\left(\sigma\right)=\int d\theta\,p\left(\sigma|\theta\right)p\left(\theta\right)
\]
\end_inset
\end_layout
\begin_layout Itemize
Assume that some (maybe all, but at least one) of the order parameters
\begin_inset Formula $\beta_{i}$
\end_inset
is a latent variable
\begin_inset Formula $\theta_{i}$
\end_inset
.
That is, write
\begin_inset Formula $\theta_{i}$
\end_inset
for
\begin_inset Formula $\beta_{i}$
\end_inset
when
\begin_inset Formula $\beta_{i}$
\end_inset
is latent.
\end_layout
\begin_layout Itemize
Resuming the notation from the revious section, if the order parameter has
some distribution
\begin_inset Formula $p\left(\theta\right)$
\end_inset
, then one has a
\begin_inset Quotes eld
\end_inset
mixed state
\begin_inset Quotes erd
\end_inset
and must write
\begin_inset Formula
\[
p\left(\sigma\right)=\int d\theta\,p\left(\theta\right)e^{-N\mathcal{H}\left(\sigma,\beta\right)}
\]
\end_inset
where the integral is over the
\begin_inset Formula $K$
\end_inset
latent parameters:
\begin_inset Formula $\int d\theta=\int d\theta_{1}d\theta{}_{2}\cdots d\theta_{K}$
\end_inset
and
\begin_inset Formula $\mathcal{H}\left(\sigma,\beta\right)=\sum_{i}\beta_{i}H_{i}\left(\sigma\right)+\frac{1}{N}\log Z\left(\beta\right)$
\end_inset
.
\end_layout
\begin_layout Standard
With some mild assumptions, one can approximate the above integral
\end_layout
\begin_layout Itemize
If
\begin_inset Formula $p\left(\theta\right)$
\end_inset
is smooth, if
\begin_inset Formula $p\left(\theta\right)$
\end_inset
does not depend on
\begin_inset Formula $N$
\end_inset
and if
\begin_inset Formula $p\left(\theta\right)$
\end_inset
has non-vanishing support at the saddle point
\begin_inset Formula $\beta^{*}$
\end_inset
, then the above can be approximated using saddle-point methods, giving
\begin_inset Formula
\[
E\left(\sigma\right)=-\frac{1}{N}\log p\left(\sigma\right)=\sum_{i}\beta_{i}^{*}H_{i}\left(\sigma\right)+\frac{1}{N}\log Z\left(\beta^{*}\right)
\]
\end_inset
\end_layout
\begin_layout Itemize
The saddle point
\begin_inset Formula $\beta^{*}$
\end_inset
is the solution to
\begin_inset Formula
\[
\frac{1}{N}\left.\frac{\partial\log Z\left(\beta\right)}{\partial\beta_{i}}\right|_{\beta^{*}}=-H_{i}\left(\sigma\right)
\]
\end_inset
when
\begin_inset Formula $\beta_{i}=\theta_{i}$
\end_inset
is one of the hidden variables, and otherwise is just the overt, non-hidden
value
\begin_inset Formula $\beta_{i}$
\end_inset
.
\end_layout
\begin_layout Itemize
Note that
\begin_inset Formula $\beta^{*}=\beta^{*}\left(\sigma\right)$
\end_inset
that is,
\begin_inset Formula $\beta^{*}$
\end_inset
is a function of
\begin_inset Formula $\sigma$
\end_inset
.
This comes from the right-hand-side, above.
\end_layout
\begin_layout Itemize
The microcanonical entropy is given by
\begin_inset Formula
\[
S\left(\left\{ H_{i}\left(\sigma\right)\right\} \right)=\inf_{\beta}\left[\sum_{i}\beta_{i}H_{i}\left(x\right)+c\left(\beta\right)\right]
\]
\end_inset
\end_layout
\begin_layout Itemize
The
\begin_inset Quotes eld
\end_inset
multi-dimensional form of the Gartner-Ellis theorem
\begin_inset Quotes eld
\end_inset
(see
\begin_inset CommandInset citation
LatexCommand cite
key "Schwab2014"
literal "true"
\end_inset
) states that the microcanonical ensemble is given as the
\begin_inset Quotes eld
\end_inset
Legendre-Fenchel transform of the cumulant generating function
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Itemize
The cumulant generating function is
\begin_inset Formula
\[
c\left(\beta\right)=\lim_{N\to\infty}\frac{1}{N}\log Z\left(\beta\right)-C
\]
\end_inset
where
\begin_inset Formula $C=\frac{1}{N}\log\int d\sigma$
\end_inset
\end_layout
\begin_layout Itemize
Up to the overall constant
\begin_inset Formula $C$
\end_inset
, one thus has Zipf's law
\begin_inset Formula
\[
S\left(\left\{ H_{i}\left(\sigma\right)\right\} \right)=E\left(\sigma\right)
\]
\end_inset
\end_layout
\begin_layout Standard
The above is a quick proof that Zipf's law arises when there are one or
more hidden variables, allowing the energy to be written as a mixture of
multiple different
\begin_inset Quotes eld
\end_inset
models
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $H_{i}\left(\sigma\right)$
\end_inset
, each of which might not, in itself, be Zipfian.
\end_layout
\begin_layout Subsection
Proportion of Explained Energy Variance (PEEV)
\end_layout
\begin_layout Standard
The derivation above required that the distribution of the latent variables
\begin_inset Formula $p\left(\theta\right)$
\end_inset
be non-zero smooth near the fixed point.
The degree to which these need to be smooth depends inversely in how peaked
the components
\begin_inset Formula $p\left(\sigma|\theta\right)$
\end_inset
are.
Aitchison
\emph on
etal
\emph default
.
\begin_inset CommandInset citation
LatexCommand cite
key "Aitchison2016"
literal "true"
\end_inset
articulate how PEEV works to blend together latent distributions.
\end_layout
\begin_layout Section
Graph Factorization and Belief Propagation
\end_layout
\begin_layout Standard
The graph factorization problem can be posed as a constraint problem.
When there are relatively few constraints, or when the coupling is weak,
this can be solved in
\begin_inset Formula $\mathcal{O}\left(N\right)$
\end_inset
time by belief propagation or message passing.
The general setting is outlined by Mezard and Mora in a very readable paper,
\begin_inset CommandInset citation
LatexCommand cite
key "Mezard2008"
literal "true"
\end_inset
recaped here.
\end_layout
\begin_layout Standard
A factorizable graph is written in the form
\begin_inset Formula
\[
p\left(\vec{x}\right)=\frac{1}{Z}\prod_{a}\psi_{a}\left(x_{i_{1}\left(a\right)},x_{i_{2}\left(a\right)},\cdots,x_{i_{k\left(a\right)}\left(a\right)}\right)
\]
\end_inset
Here, the vector
\begin_inset Formula $\vec{x}=\left(x_{1},x_{2},\cdots,x_{N}\right)$
\end_inset
describes the state of the system, so that each
\begin_inset Formula $x_{i}$
\end_inset
is some variable.
Thus,
\begin_inset Formula $p\left(\vec{x}\right)$
\end_inset
describes the probability of finding the system in state
\begin_inset Formula $\vec{x}$
\end_inset
.
Its is assumed that the system must satisfy a set of constraints, which
are reflected in the
\begin_inset Formula $\psi_{a}$
\end_inset
, with the index
\begin_inset Formula $a$
\end_inset
running over the set of constraints.
The constraints are assumed to run over only a subset of the full vector
\begin_inset Formula $\vec{x}$
\end_inset
, so that, for fixed
\begin_inset Formula $a$
\end_inset
, only
\begin_inset Formula $k=k\left(a\right)$
\end_inset
variables are involved.
Which of these variables are involved are indicated by the indicator function
\begin_inset Formula $\vec{i}\left(a\right)=\left(i_{1}\left(a\right),i_{2}\left(a\right),\cdots,i_{k}\left(a\right)\right)$
\end_inset
.
The indicated variables for constraint
\begin_inset Formula $a$
\end_inset
are then
\begin_inset Formula $x_{i_{1}\left(a\right)},x_{i_{2}\left(a\right)},\cdots,x_{i_{k}\left(a\right)}$
\end_inset
.
\end_layout
\begin_layout Standard
Mezard describes how belief propagation can be used to quickly solve graph
factorization problems.
\begin_inset CommandInset citation
LatexCommand cite
key "Mezard2008"
literal "true"
\end_inset
\end_layout
\begin_layout Standard
I'm confused; belief propagation can also solve problems that don't have
a factorization, e.g.
single-layer perceptrons.
So, really, the point is that belief propagation can be used to solve for
probability distributions, and it works well on factorizable distributions,
too.
Which is kind-of the only point of the quoted paper.
They illustrate for the specific case of the Ising mode.
\end_layout
\begin_layout Standard
XXX TODO: clean up this section.
\end_layout
\begin_layout Section
Ising Models and Markov Random Fields
\end_layout
\begin_layout Standard
Ising models are a simple case of MRF.
So cover them first.
\end_layout
\begin_layout Subsection
Ising Models
\end_layout
\begin_layout Standard
Ising models with more than two states are called Potts models.
\end_layout
\begin_layout Standard
The Ising Hamlitonian can be derived as a minimum entropy model, by applying
constraints that the probability of singletons and pairs must produce the
actual, observed frequency distribution of singletons and pairs.
The technique for forcing this agreement is called
\begin_inset Quotes eld
\end_inset
lagrange multipliers
\begin_inset Quotes erd
\end_inset
.
XXX TODO find a reference that explains how the below is actually done.
\end_layout
\begin_layout Standard
The primary issue is that the
\begin_inset Formula $H_{i}\left(\sigma\right)$
\end_inset
depend on the full
\begin_inset Formula $\sigma$
\end_inset
, which in general makes the problem intractable.
So instead, write the entropy as
\begin_inset Formula
\[
S=-\sum_{\sigma}p\left(\sigma\right)\log p\left(\sigma\right)
\]
\end_inset
and write
\begin_inset Formula $\sigma$
\end_inset
as an indexed set; that is,
\begin_inset Formula $\sigma=\left(\sigma_{1},\sigma_{2},\cdots,\sigma_{N}\right)$
\end_inset
.
Each
\begin_inset Formula $\sigma_{i}$
\end_inset
can be interpreted as a value at position
\begin_inset Formula $i$
\end_inset
, for example, a word at position
\begin_inset Formula $i$
\end_inset
in a sentence, an amino acid in position
\begin_inset Formula $i$
\end_inset
in a protein,
\emph on
etc
\emph default
.
In a basic Potts model, one has observed frequencies
\begin_inset Formula $f_{a}\left(i\right)$
\end_inset
which counts the frequency at which the location
\begin_inset Formula $i$
\end_inset
had the value
\begin_inset Formula $\sigma_{i}=a$
\end_inset
and the pair frequencies
\begin_inset Formula $f_{ab}\left(i,j\right)$
\end_inset
that location
\begin_inset Formula $i$
\end_inset
had
\begin_inset Formula $\sigma_{i}=a$
\end_inset
and also location
\begin_inset Formula $j$
\end_inset
had
\begin_inset Formula $\sigma_{j}=b$
\end_inset
.
...
Its common to ignore the position dependence, i.e.
to observe only the averages, independent of position...
\end_layout
\begin_layout Standard
The goal is to create a model such that the singleton constraints
\begin_inset Formula
\[
f_{a}\left(i\right)=\sum_{\sigma_{1}}\sum_{\sigma_{2}}\cdots\sum_{\sigma_{N}}p\left(\sigma_{1},\sigma_{2},\cdots,\sigma_{N}\right)\delta_{\sigma_{i},a}
\]
\end_inset
and the pairwise constraints
\begin_inset Formula
\[
f_{ab}\left(i,j\right)=\sum_{\sigma_{1}}\sum_{\sigma_{2}}\cdots\sum_{\sigma_{N}}p\left(\sigma_{1},\sigma_{2},\cdots,\sigma_{N}\right)\delta_{\sigma_{i},a}\delta_{\sigma_{j},b}
\]
\end_inset
are obeyed.
Here, the
\begin_inset Formula $\delta_{\sigma_{i},a}$
\end_inset
is the Dirac delta function, such that
\begin_inset Formula
\[
\delta_{\sigma_{i},a}=\begin{cases}
1 & \mbox{ if }\sigma_{i}=a\\
0 & \mbox{ otherwise}
\end{cases}
\]
\end_inset
This is done by
\begin_inset Quotes eld
\end_inset
adding a multiple of zero
\begin_inset Quotes erd
\end_inset
...
etc.
XXXTODO show how this is done.
\end_layout
\begin_layout Standard
This causes the model probability to factorize:
\begin_inset Formula
\[
p\left(\sigma\right)=p\left(\sigma_{1},\sigma_{2},\cdots,\sigma_{N}\right)=\frac{1}{Z}\prod_{i}\phi\left(\sigma_{i}\right)\prod_{jk}\phi\left(\sigma_{j},\sigma_{k}\right)
\]
\end_inset
where each factor is given by a Boltzmann model
\begin_inset Formula
\[
\phi\left(\sigma_{i}\right)=\exp-H_{i}\left(\sigma_{i}\right)
\]
\end_inset
and
\begin_inset Formula
\[
\phi\left(\sigma_{i},\sigma_{j}\right)=\exp-H_{ij}\left(\sigma_{i},\sigma_{j}\right)
\]
\end_inset
which now satisfies the constraints on the observed frequency counts.
\end_layout
\begin_layout Subsection
Gauge fixing
\end_layout
\begin_layout Standard
The frequencies are not independent; one has constraints
\begin_inset Formula
\[
f_{a}\left(i\right)=\sum_{j,b}f_{ab}\left(i,j\right)
\]
\end_inset
which means that there's ambiguity in how the Hamiltonian is split up, i.e.
there is gauge invariance; and so one needs gauge fixing.
This is usually done by forcing
\begin_inset Formula
\[
0=\sum_{i}H_{i}\left(\sigma_{i}\right)
\]
\end_inset
and
\begin_inset Formula
\[
0=\sum_{i,j}H_{ij}\left(\sigma_{i},\sigma_{j}\right)
\]
\end_inset
XXX show the details of this; firm it up.
\end_layout
\begin_layout Subsection
Markov Random Fields
\end_layout
\begin_layout Standard
See Wikipedia,
\begin_inset Quotes eld
\end_inset
Markov Random Field
\begin_inset Quotes erd
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "WP-MarkovField"
literal "true"
\end_inset
for more.
\end_layout
\begin_layout Standard
Factorization of the Hamiltonian into cliques.
\end_layout
\begin_layout Standard
Cliques correspond to synonyms.
i.e.
words (and word-phrases) that are synonymous (i.e.
can replace one-another with low energy.)
\end_layout
\begin_layout Standard
Cliques are the base-space for the sheaves; sheaves project down to cliques.
\end_layout
\begin_layout Standard
TODO flesh all this out.
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "lang"
options "plain"
\end_inset
\end_layout
\end_body
\end_document