entropy.lyx

#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