# Aligned Induction

## Maximum Entropy

Haskell implementation of the Overview/Maximum Entropy

Let $X \subset \mathcal{X}$ be a finite set of micro-states, $0 < |X| < \infty$. Consider a system of $n$ distinguishable particles, each in a micro-state. The set of states of the system is the set of micro-state functions of particle identifier, $\{1 \ldots n\} :\to X$. The cardinality of the set of states is $|X|^n$.

let states xx n = foldl mul [[]] [1..n]
where
mul rr i = [jj ++ [(i,x)] | jj <- rr, x <- Set.toList xx]

let xx = Set.fromList ['a'..'c']

rp xx
"{'a','b','c'}"

let ss = states xx 6

length ss
729

3^6
729

rpln $take 10$ ss
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'a')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'b')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'c')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'a')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'b')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'c')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'a')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'b')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'c')]"
"[(1,'a'),(2,'a'),(3,'a'),(4,'b'),(5,'a'),(6,'a')]"


Each state implies a distribution of particles over micro-states, $\begin{eqnarray} I &=& \big\{(R,\{(x,|C|) : (x,C) \in R^{-1}\}) : R \in \{1 \ldots n\} :\to X\big\} \end{eqnarray}$ That is, a state $R \in \{1 \ldots n\} :\to X$ has a particle distribution $I(R) \in X \to \{1 \ldots n\}$ such that $\sum_{x \in X} I(R)(x) = n$,

let inv = Map.toList . functionsInverse . Map.fromList

let ii = [(rr, [(x, Set.size cc) | (x,cc) <- inv rr]) | rr <- ss]

rpln $take 10$ ii
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'a')],[('a',6)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'b')],[('a',5),('b',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'a'),(6,'c')],[('a',5),('c',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'a')],[('a',5),('b',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'b')],[('a',4),('b',2)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'b'),(6,'c')],[('a',4),('b',1),('c',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'a')],[('a',5),('c',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'b')],[('a',4),('b',1),('c',1)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'a'),(5,'c'),(6,'c')],[('a',4),('c',2)])"
"([(1,'a'),(2,'a'),(3,'a'),(4,'b'),(5,'a'),(6,'a')],[('a',5),('b',1)])"

nub [sum (snd (unzip nn)) | (_,nn) <- ii]
[6]


The cardinality of states for each particle distribution, $I(R)$, is the multinomial coefficient, $\begin{eqnarray} W &=& \{(N,|D|) : (N,D) \in I^{-1}\} &=& \{(N,\frac{n!}{\prod_{(x,\cdot) \in N} N_x!}) : (N,\cdot) \in I^{-1}\} \end{eqnarray}$ That is, there are $W(I(R))$ states that have the same particle distribution, $I(R)$, as state $R$,

let ww = [(nn, Set.size dd) | (nn,dd) <- inv ii]

rpln ww
"([('a',1),('b',1),('c',4)],30)"
"([('a',1),('b',2),('c',3)],60)"
"([('a',1),('b',3),('c',2)],60)"
"([('a',1),('b',4),('c',1)],30)"
"([('a',1),('b',5)],6)"
"([('a',1),('c',5)],6)"
"([('a',2),('b',1),('c',3)],60)"
"([('a',2),('b',2),('c',2)],90)"
"([('a',2),('b',3),('c',1)],60)"
"([('a',2),('b',4)],15)"
"([('a',2),('c',4)],15)"
"([('a',3),('b',1),('c',2)],60)"
"([('a',3),('b',2),('c',1)],60)"
"([('a',3),('b',3)],20)"
"([('a',3),('c',3)],20)"
"([('a',4),('b',1),('c',1)],30)"
"([('a',4),('b',2)],15)"
"([('a',4),('c',2)],15)"
"([('a',5),('b',1)],6)"
"([('a',5),('c',1)],6)"
"([('a',6)],1)"
"([('b',1),('c',5)],6)"
"([('b',2),('c',4)],15)"
"([('b',3),('c',3)],20)"
"([('b',4),('c',2)],15)"
"([('b',5),('c',1)],6)"
"([('b',6)],1)"
"([('c',6)],1)"


The function combinationMultinomial is defined in AlignmentUtil,

combinationMultinomial :: Integer -> [Integer] -> Integer


So

let mult n nn = combinationMultinomial (toInteger n) [toInteger y | (_,y) <- nn]

and [mult 6 nn == toInteger d | (nn,d) <- ww]
True


The normalisation of the state distribution over particle distributions is a probability function, $\hat{W} \in ((X \to \{1 \ldots n\}) \to \mathbf{Q}_{>0}) \cap \mathcal{P}$,

let norm nn = Set.toList $relationsNormalise$ Set.fromList [(x, toRational y) | (x,y) <- nn]

rpln $norm ww "([('a',1),('b',1),('c',4)],10 % 243)" "([('a',1),('b',2),('c',3)],20 % 243)" "([('a',1),('b',3),('c',2)],20 % 243)" "([('a',1),('b',4),('c',1)],10 % 243)" "([('a',1),('b',5)],2 % 243)" "([('a',1),('c',5)],2 % 243)" "([('a',2),('b',1),('c',3)],20 % 243)" "([('a',2),('b',2),('c',2)],10 % 81)" "([('a',2),('b',3),('c',1)],20 % 243)" "([('a',2),('b',4)],5 % 243)" "([('a',2),('c',4)],5 % 243)" "([('a',3),('b',1),('c',2)],20 % 243)" "([('a',3),('b',2),('c',1)],20 % 243)" "([('a',3),('b',3)],20 % 729)" "([('a',3),('c',3)],20 % 729)" "([('a',4),('b',1),('c',1)],10 % 243)" "([('a',4),('b',2)],5 % 243)" "([('a',4),('c',2)],5 % 243)" "([('a',5),('b',1)],2 % 243)" "([('a',5),('c',1)],2 % 243)" "([('a',6)],1 % 729)" "([('b',1),('c',5)],2 % 243)" "([('b',2),('c',4)],5 % 243)" "([('b',3),('c',3)],20 % 729)" "([('b',4),('c',2)],5 % 243)" "([('b',5),('c',1)],2 % 243)" "([('b',6)],1 % 729)" "([('c',6)],1 % 729)"  In the case where the number of particles is large,$n \gg \ln n$, the logarithm of the multinomial coefficient of a particle distribution$N \in X \to \{1 \ldots n\}$approximates to the scaled entropy, $\begin{eqnarray} \ln \frac{n!}{\prod_{(x,\cdot) \in N} N_x!} &\approx& n \times \mathrm{entropy}(N) \end{eqnarray}$ so the probability of the particle distribution varies with its entropy,$\hat{W}(N) \sim \mathrm{entropy}(N)$, let ent nn = entropy [toRational y | (_,y) <- nn] rpln$ sort [(d, nn, ent nn) | (nn,d) <- ww]
"(1,[('a',6)],-0.0)"
"(1,[('b',6)],-0.0)"
"(1,[('c',6)],-0.0)"
"(6,[('a',1),('b',5)],0.45056120886630463)"
"(6,[('a',1),('c',5)],0.45056120886630463)"
"(6,[('a',5),('b',1)],0.45056120886630463)"
"(6,[('a',5),('c',1)],0.45056120886630463)"
"(6,[('b',1),('c',5)],0.45056120886630463)"
"(6,[('b',5),('c',1)],0.45056120886630463)"
"(15,[('a',2),('b',4)],0.6365141682948128)"
"(15,[('a',2),('c',4)],0.6365141682948128)"
"(15,[('a',4),('b',2)],0.6365141682948128)"
"(15,[('a',4),('c',2)],0.6365141682948128)"
"(15,[('b',2),('c',4)],0.6365141682948128)"
"(15,[('b',4),('c',2)],0.6365141682948128)"
"(20,[('a',3),('b',3)],0.6931471805599453)"
"(20,[('a',3),('c',3)],0.6931471805599453)"
"(20,[('b',3),('c',3)],0.6931471805599453)"
"(30,[('a',1),('b',1),('c',4)],0.8675632284814612)"
"(30,[('a',1),('b',4),('c',1)],0.8675632284814612)"
"(30,[('a',4),('b',1),('c',1)],0.8675632284814612)"
"(60,[('a',1),('b',2),('c',3)],1.0114042647073518)"
"(60,[('a',1),('b',3),('c',2)],1.0114042647073518)"
"(60,[('a',2),('b',1),('c',3)],1.0114042647073518)"
"(60,[('a',2),('b',3),('c',1)],1.0114042647073516)"
"(60,[('a',3),('b',1),('c',2)],1.0114042647073518)"
"(60,[('a',3),('b',2),('c',1)],1.0114042647073516)"
"(90,[('a',2),('b',2),('c',2)],1.0986122886681096)"


The least probable particle distributions are singletons, $\begin{eqnarray} \mathrm{mind}(W) &=& \big\{\{(x,n)\} : x \in X\big\} \end{eqnarray}$ because they have only one state, $\forall x \in X~(W(\{(x,n)\}) = 1)$. The entropy of a singleton distribution is zero, $\mathrm{entropy}(\{(x,n)\}) = 0$,

"(1,[('a',6)],-0.0)"
"(1,[('b',6)],-0.0)"
"(1,[('c',6)],-0.0)"


In the case where the number of particles per micro-state is integral, $n/|X| \in \mathbf{N}_{>0}$, the modal particle distribution is the uniform distribution, $\begin{eqnarray} \mathrm{maxd}(W) &=& \big\{\{(x,n/|X|) : x \in X\}\big\} \end{eqnarray}$ The entropy of the uniform distribution is maximised, $\mathrm{entropy}(\{(x,n/|X|) : x \in X\}) = \ln |X|$,

"(90,[('a',2),('b',2),('c',2)],1.0986122886681096)"

log 3
1.0986122886681098


The normalisation of a particle distribution $N \in X \to \{1 \ldots n\}$ is a micro-state probability function, $\hat{N} \in (X \to \mathbf{Q}_{\geq 0}) \cap \mathcal{P}$, which is independent of the number of particles, $\mathrm{sum}(\hat{N}) = 1$.

So in the case where a problem domain is parameterised by an unknown micro-state probability function otherwise arbitrarily chosen from a known subset $Q \subseteq (X \to \mathbf{Q}_{\geq 0}) \cap \mathcal{P}$, where the number of particles is known to be large, the maximum likelihood estimate $\tilde{P} \in Q$ is the probability function with the greatest entropy, $\forall P \in Q~(\mathrm{entropy}(\tilde{P}) \geq \mathrm{entropy}(P))$ or $\tilde{P} \in \mathrm{maxd}(\{(P,\mathrm{entropy}(P)) : P \in Q\})$,

rpln \$ sort [(ent nn, norm nn) | (nn,d) <- ww]
"(-0.0,[('a',1 % 1)])"
"(-0.0,[('b',1 % 1)])"
"(-0.0,[('c',1 % 1)])"
"(0.45056120886630463,[('a',1 % 6),('b',5 % 6)])"
"(0.45056120886630463,[('a',1 % 6),('c',5 % 6)])"
"(0.45056120886630463,[('a',5 % 6),('b',1 % 6)])"
"(0.45056120886630463,[('a',5 % 6),('c',1 % 6)])"
"(0.45056120886630463,[('b',1 % 6),('c',5 % 6)])"
"(0.45056120886630463,[('b',5 % 6),('c',1 % 6)])"
"(0.6365141682948128,[('a',1 % 3),('b',2 % 3)])"
"(0.6365141682948128,[('a',1 % 3),('c',2 % 3)])"
"(0.6365141682948128,[('a',2 % 3),('b',1 % 3)])"
"(0.6365141682948128,[('a',2 % 3),('c',1 % 3)])"
"(0.6365141682948128,[('b',1 % 3),('c',2 % 3)])"
"(0.6365141682948128,[('b',2 % 3),('c',1 % 3)])"
"(0.6931471805599453,[('a',1 % 2),('b',1 % 2)])"
"(0.6931471805599453,[('a',1 % 2),('c',1 % 2)])"
"(0.6931471805599453,[('b',1 % 2),('c',1 % 2)])"
"(0.8675632284814612,[('a',1 % 6),('b',1 % 6),('c',2 % 3)])"
"(0.8675632284814612,[('a',1 % 6),('b',2 % 3),('c',1 % 6)])"
"(0.8675632284814612,[('a',2 % 3),('b',1 % 6),('c',1 % 6)])"
"(1.0114042647073516,[('a',1 % 3),('b',1 % 2),('c',1 % 6)])"
"(1.0114042647073516,[('a',1 % 2),('b',1 % 3),('c',1 % 6)])"
"(1.0114042647073518,[('a',1 % 6),('b',1 % 3),('c',1 % 2)])"
"(1.0114042647073518,[('a',1 % 6),('b',1 % 2),('c',1 % 3)])"
"(1.0114042647073518,[('a',1 % 3),('b',1 % 6),('c',1 % 2)])"
"(1.0114042647073518,[('a',1 % 2),('b',1 % 6),('c',1 % 3)])"
"(1.0986122886681096,[('a',1 % 3),('b',1 % 3),('c',1 % 3)])"


top