# Aligned Induction

## Transform entropy

Python implementation of the Overview/Transform entropy

### Sections

Definitions

Model entropy

Example - a weather forecast

### Definitions

Let $T$ be a one functional transform, $T \in \mathcal{T}_{U,\mathrm{f},1}$, having underlying variables $V = \mathrm{und}(T)$. Let $A$ be a histogram, $A \in \mathcal{A}$, in the underlying variables, $\mathrm{vars}(A) = V$, having size $z = \mathrm{size}(A) > 0$. The underlying volume is $v = |V^{\mathrm{C}}|$. The derived volume is $w = |T^{-1}|$.

Consider the deck of cards example,

def lluu(ll):
return listsSystem([(v,sset(ww)) for (v,ww) in ll])

[suit,rank] = map(VarStr, ["suit","rank"])
[hearts,clubs,diamonds,spades] = map(ValStr, ["hearts","clubs","diamonds","spades"])
[jack,queen,king,ace] = map(ValStr, ["J","Q","K","A"])

uu = lluu([
(suit, [hearts,clubs,diamonds,spades]),
(rank, [jack,queen,king,ace] + list(map(ValInt,range(2,10+1))))])

vv = sset([suit, rank])

uu
# {(rank, {A, J, K, Q, 2, 3, 4, 5, 6, 7, 8, 9, 10}), (suit, {clubs, diamonds, hearts, spades})}

vv
# {rank, suit}

aa = unit(cart(uu,vv))

rpln(aall(aa))
# ({(rank, A), (suit, clubs)}, 1 % 1)
# ({(rank, A), (suit, diamonds)}, 1 % 1)
# ({(rank, A), (suit, hearts)}, 1 % 1)
# ({(rank, A), (suit, spades)}, 1 % 1)
# ({(rank, J), (suit, clubs)}, 1 % 1)
# ({(rank, J), (suit, diamonds)}, 1 % 1)
# ...
# ({(rank, 9), (suit, hearts)}, 1 % 1)
# ({(rank, 9), (suit, spades)}, 1 % 1)
# ({(rank, 10), (suit, clubs)}, 1 % 1)
# ({(rank, 10), (suit, diamonds)}, 1 % 1)
# ({(rank, 10), (suit, hearts)}, 1 % 1)
# ({(rank, 10), (suit, spades)}, 1 % 1)


Also consider a game of cards which has a special deck such that spades and clubs are pip cards and hearts and diamonds are face cards. The suit and the rank are no longer independent,

bb = unit(sset(
[llss([(suit,s),(rank,r)]) for s in [spades,clubs] for r in [ace] + list(map(ValInt,range(2,10+1)))] +
[llss([(suit,s),(rank,r)]) for s in [hearts,diamonds] for r in [jack,queen,king]]))

rpln(aall(bb))
# ({(rank, A), (suit, clubs)}, 1 % 1)
# ({(rank, A), (suit, spades)}, 1 % 1)
# ({(rank, J), (suit, diamonds)}, 1 % 1)
...
# ({(rank, 9), (suit, spades)}, 1 % 1)
# ({(rank, 10), (suit, clubs)}, 1 % 1)
# ({(rank, 10), (suit, spades)}, 1 % 1)


Consider the transform relating the suit to the colour,

colour = VarStr("colour")
red = ValStr("red")
black = ValStr("black")

xx = llaa([(llss([(suit, u),(colour, w)]),1) for (u,w) in [(hearts, red), (clubs, black), (diamonds, red), (spades, black)]])

rpln(aall(xx))
# ({(colour, black), (suit, clubs)}, 1 % 1)
# ({(colour, black), (suit, spades)}, 1 % 1)
# ({(colour, red), (suit, diamonds)}, 1 % 1)
# ({(colour, red), (suit, hearts)}, 1 % 1)

ww = sset([colour])

kk = vars(xx) - ww

tt = trans(xx,ww)

ttaa(tt) == xx
# True

und(tt) == kk
# True

der(tt) == ww
# True


In order to compare the sized derived entropies of the two decks, we shall add together two special decks, $B + B$, to have the same size as whole deck, $A$,

size(aa)
# 52 % 1

size(bb)
# 26 % 1

bb = mul(scalar(2),unit(sset(
[llss([(suit,s),(rank,r)]) for s in [spades,clubs] for r in [ace] + list(map(ValInt,range(2,10+1)))] +
[llss([(suit,s),(rank,r)]) for s in [hearts,diamonds] for r in [jack,queen,king]])))

size(bb)
# 52 % 1

rpln(aall(bb))
# ({(rank, A), (suit, clubs)}, 2 % 1)
# ({(rank, A), (suit, spades)}, 2 % 1)
# ({(rank, J), (suit, diamonds)}, 2 % 1)
# ...
# ({(rank, 9), (suit, spades)}, 2 % 1)
# ({(rank, 10), (suit, clubs)}, 2 % 1)
# ({(rank, 10), (suit, spades)}, 2 % 1)

rpln(aall(tmul(aa,tt)))
# ({(colour, black)}, 26 % 1)
# ({(colour, red)}, 26 % 1)

rpln(aall(tmul(bb,tt)))
# ({(colour, black)}, 40 % 1
# ({(colour, red)}, 12 % 1)


The derived entropy or component size entropy is $\begin{eqnarray} \mathrm{entropy}(A * T) &:=& -\sum_{(R,\cdot) \in T^{-1}} (\hat{A} * T)_R \times \ln~(\hat{A} * T)_R \end{eqnarray}$

ent = histogramsEntropy

ent (tmul(aa,tt))
# 0.6931471805599453

ent (tmul(bb,tt))
# 0.5402041423888608


The derived entropy is positive and less than or equal to the logarithm of the derived volume, $0 \leq \mathrm{entropy}(A * T) \leq \ln w$,

w = len(states(ared(xx,der(tt))))

w
# 2

log(w)
# 0.6931471805599453

ent(tmul(aa,tt)) <= log(w)
# True

ent(tmul(bb,tt)) <= log(w)
# True


Complementary to the derived entropy is the expected component entropy, $\begin{eqnarray} \mathrm{entropyComponent}(A,T) &:=& \sum_{(R,C) \in T^{-1}} (\hat{A} * T)_R \times \mathrm{entropy}(A * C)\\ &=&\sum_{(R,\cdot) \in T^{-1}} (\hat{A} * T)_R \times \mathrm{entropy}(\{R\}^{\mathrm{U}} * T^{\odot A}) \end{eqnarray}$

transformsHistogramsEntropyComponent :: Transform -> Histogram -> Double


For example,

def cent(aa,tt):
return transformsHistogramsEntropyComponent(tt,aa)

cent(aa,tt)
# 3.2580965380214835

cent(bb,tt)
# 2.7178923956326213


The cartesian derived entropy or component cardinality entropy is $\begin{eqnarray} \mathrm{entropy}(V^{\mathrm{C}} * T) &:=& -\sum_{(R,\cdot) \in T^{-1}} (\hat{V}^{\mathrm{C}} * T)_R \times \ln~(\hat{V}^{\mathrm{C}} * T)_R \end{eqnarray}$

vvc = unit(cart(uu,vv))

ent(tmul(vvc,tt))
# 0.6931471805599453


In the case of the whole deck of cards, the histogram is cartesian, $A = V^{\mathrm{C}}$, so the component cardinality entropy equals the derived entropy, $V^{\mathrm{C}} * T = A * T$,

ent(tmul(vvc,tt)) == ent(tmul(aa,tt))
# True


The cartesian derived entropy is positive and less than or equal to the logarithm of the derived volume, $0 \leq \mathrm{entropy}(V^{\mathrm{C}} * T) \leq \ln w$,

ent(tmul(vvc,tt)) <= log(w)
# True


The cartesian derived derived sum entropy or component size cardinality sum entropy is $\begin{eqnarray} \mathrm{entropy}(A * T) + \mathrm{entropy}(V^{\mathrm{C}} * T) \end{eqnarray}$

ent(tmul(aa,tt)) + ent(tmul(vvc,tt))
# 1.3862943611198906

ent(tmul(bb,tt)) + ent(tmul(vvc,tt))
# 1.2333513229488062


The component size cardinality cross entropy is the negative derived histogram expected normalised cartesian derived count logarithm, $\begin{eqnarray} \mathrm{entropyCross}(A * T,V^{\mathrm{C}} * T) &:=& -\sum_{(R,\cdot) \in T^{-1}} (\hat{A} * T)_R \times \ln~(\hat{V}^{\mathrm{C}} * T)_R \end{eqnarray}$

histogramsHistogramsEntropyCross :: Histogram -> Histogram -> Double


For example,

crent = histogramsHistogramsEntropyCross

crent(tmul(aa,tt),tmul(vvc,tt))
# 0.6931471805599453

crent(tmul(bb,tt),tmul(vvc,tt))
# 0.6931471805599453


The component size cardinality cross entropy is greater than or equal to the derived entropy, $\mathrm{entropyCross}(A * T,V^{\mathrm{C}} * T) \geq \mathrm{entropy}(A * T)$,

crent(tmul(aa,tt),tmul(vvc,tt)) >= ent(tmul(aa,tt))
# True

crent(tmul(bb,tt),tmul(vvc,tt)) >= ent(tmul(bb,tt))
# True


The component cardinality size cross entropy is the negative cartesian derived expected normalised derived histogram count logarithm, $\begin{eqnarray} \mathrm{entropyCross}(V^{\mathrm{C}} * T,A * T) &:=& -\sum_{(R,\cdot) \in T^{-1}} (\hat{V}^{\mathrm{C}} * T)_R \times \ln~(\hat{A} * T)_R \end{eqnarray}$

crent(tmul(vvc,tt),tmul(aa,tt))
# 0.6931471805599453

crent(tmul(vvc,tt),tmul(bb,tt))
# 0.864350666630459


The component cardinality size cross entropy is greater than or equal to the cartesian derived entropy, $\mathrm{entropyCross}(V^{\mathrm{C}} * T,A * T) \geq \mathrm{entropy}(V^{\mathrm{C}} * T)$,

crent(tmul(vvc,tt),tmul(aa,tt)) >= ent(tmul(aa,tt))
# True

crent(tmul(vvc,tt),tmul(bb,tt)) >= ent(tmul(bb,tt))
# True


The component size cardinality sum cross entropy is $\begin{eqnarray} \mathrm{entropy}(A * T + V^{\mathrm{C}} * T) \end{eqnarray}$

ent(add(tmul(aa,tt),tmul(vvc,tt)))
# 0.6931471805599453

ent(add(tmul(bb,tt),tmul(vvc,tt)))
# 0.6564535237245771


The component size cardinality sum cross entropy is positive and less than or equal to the logarithm of the derived volume, $0 \leq \mathrm{entropy}(A * T + V^{\mathrm{C}} * T) \leq \ln w$,

ent(add(tmul(aa,tt),tmul(vvc,tt))) <= log(w)
# True

ent(add(tmul(bb,tt),tmul(vvc,tt))) <= log(w)
# True


In all cases the cross entropy is maximised when high size components are low cardinality components, $(\hat{A} * T)_R \gg (\hat{V}^{\mathrm{C}} * T)_R$ or $\mathrm{size}(A * C)/z \gg |C|/v$, and low size components are high cardinality components, $(\hat{A} * T)_R \ll (\hat{V}^{\mathrm{C}} * T)_R$ or $\mathrm{size}(A * C)/z \ll |C|/v$, where $(R,C) \in T^{-1}$. To show this consider another transform $T’$,

tt1 = trans(cdaa([[1,1,1],[1,2,2],[1,3,2],[2,1,2],[2,2,1],[2,3,2],[3,1,2],[3,2,2],[3,3,1]]), sset([VarInt(3)]))

rpln(aall(ttaa(tt1)))
# ({(1, 1), (2, 1), (3, 1)}, 1 % 1)
# ({(1, 1), (2, 2), (3, 2)}, 1 % 1)
# ({(1, 1), (2, 3), (3, 2)}, 1 % 1)
# ({(1, 2), (2, 1), (3, 2)}, 1 % 1)
# ({(1, 2), (2, 2), (3, 1)}, 1 % 1)
# ({(1, 2), (2, 3), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 1), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 2), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 3), (3, 1)}, 1 % 1)


Let $A’$ be a scaled regular diagonal histogram plus a scaled regular cartesian histogram,

aa1 = resize(9,add(norm(regdiag(3,2)),norm(regcart(3,2))))

rpln(aall(aa1))
# ({(1, 1), (2, 1)}, 2 % 1)
# ({(1, 1), (2, 2)}, 1 % 2)
# ({(1, 1), (2, 3)}, 1 % 2)
# ({(1, 2), (2, 1)}, 1 % 2)
# ({(1, 2), (2, 2)}, 2 % 1)
# ({(1, 2), (2, 3)}, 1 % 2)
# ({(1, 3), (2, 1)}, 1 % 2)
# ({(1, 3), (2, 2)}, 1 % 2)
# ({(1, 3), (2, 3)}, 2 % 1)

vvc1 = regcart(3,2)

rpln(aall(vvc1))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)

rpln(aall(tmul(aa1,tt1)))
# ({(3, 1)}, 6 % 1)
# ({(3, 2)}, 3 % 1)

rpln(aall(tmul(vvc1,tt1)))
# ({(3, 1)}, 3 % 1)
# ({(3, 2)}, 6 % 1)


The derived entropy equals the cartesian derived entropy,

ent(tmul(aa1,tt1))
# 0.6365141682948128

ent(tmul(vvc1,tt1))
# 0.6365141682948128


but the cross entropy is greater than either,

ent(add(tmul(aa1,tt1),tmul(vvc1,tt1)))
# 0.6931471805599453

crent(tmul(aa1,tt1),tmul(vvc1,tt1))
# 0.8675632284814613

crent(tmul(vvc1,tt1),tmul(aa1,tt1))
# 0.8675632284814613


The cross entropy is minimised when the normalised derived histogram equals the normalised cartesian derived, $\hat{A} * T = \hat{V}^{\mathrm{C}} * T$ or $\forall (R,C) \in T^{-1}~(\mathrm{size}(A * C)/z = |C|/v)$. In this case the cross entropy equals the corresponding component entropy,

ent(add(tmul(vvc1,tt1),tmul(vvc1,tt1)))
# 0.6365141682948128

crent(tmul(vvc1,tt1),tmul(vvc1,tt1))
# 0.6365141682948128


The component size cardinality relative entropy is the component size cardinality cross entropy minus the component size entropy, $\begin{eqnarray} \mathrm{entropyRelative}(A * T,V^{\mathrm{C}} * T) &:=& \sum_{(R,\cdot) \in T^{-1}} (\hat{A} * T)_R \times \ln\frac{(\hat{A} * T)_R}{(\hat{V}^{\mathrm{C}} * T)_R}\\ &=& \mathrm{entropyCross}(A * T,V^{\mathrm{C}} * T)~-~\mathrm{entropy}(A * T) \end{eqnarray}$ The component size cardinality relative entropy is positive, $\mathrm{entropyRelative}(A * T,V^{\mathrm{C}} * T) \geq 0$,

crent(tmul(aa,tt),tmul(vvc,tt)) - ent(tmul(aa,tt))
# 0.0

crent(tmul(bb,tt),tmul(vvc,tt)) - ent(tmul(bb,tt))
# 0.15294303817108446

crent(tmul(aa1,tt1),tmul(vvc1,tt1)) - ent(tmul(aa1,tt1))
# 0.2310490601866485


The component cardinality size relative entropy is the component cardinality size cross entropy minus the component cardinality entropy, $\begin{eqnarray} \mathrm{entropyRelative}(V^{\mathrm{C}} * T,A * T) &:=& \sum_{(R,\cdot) \in T^{-1}} (\hat{V}^{\mathrm{C}} * T)_R \times \ln\frac{(\hat{V}^{\mathrm{C}} * T)_R}{(\hat{A} * T)_R}\\ &=& \mathrm{entropyCross}(V^{\mathrm{C}} * T,A * T)~-~\mathrm{entropy}(V^{\mathrm{C}} * T) \end{eqnarray}$ The component cardinality size relative entropy is positive, $\mathrm{entropyRelative}(V^{\mathrm{C}} * T,A * T) \geq 0$,

crent(tmul(vvc,tt),tmul(aa,tt)) - ent(tmul(vvc,tt))
# 0.0

crent(tmul(vvc,tt),tmul(bb,tt)) - ent(tmul(vvc,tt))
# 0.17120348607051372

crent(tmul(vvc1,tt1),tmul(aa1,tt1)) - ent(tmul(vvc1,tt1))
# 0.2310490601866485


The size-volume scaled component size cardinality sum relative entropy is the size-volume scaled component size cardinality sum cross entropy minus the size-volume scaled component size cardinality sum entropy, $\begin{eqnarray} (z+v) \times \mathrm{entropy}(A * T + V^{\mathrm{C}} * T)~-~z \times \mathrm{entropy}(A * T)~-~v \times \mathrm{entropy}(V^{\mathrm{C}} * T) \end{eqnarray}$ The size-volume scaled component size cardinality sum relative entropy is positive and less than the size-volume scaled logarithm of the derived volume, $(z+v) \ln w$,

z = size(aa)

v = vol(uu,vv)

(z+v) * ent(add(tmul(aa,tt),tmul(vvc,tt))) - z * ent(tmul(aa,tt)) - v * ent(tmul(vvc,tt))
# 0.0

(z+v) * ent(add(tmul(bb,tt),tmul(vvc,tt))) - z * ent(tmul(bb,tt)) - v * ent(tmul(vvc,tt))
# 4.136897674018108

(z+v) * log(w)
# 72.0873067782343

z1 = 9
v1 = 9
w1 = 2

(z1+v1) * ent(add(tmul(aa1,tt1),tmul(vvc1,tt1))) - z1 * ent(tmul(aa1,tt1)) - v1 * ent(tmul(vvc1,tt1))
# 1.0193942207723854

(z1+v1) * log(w1)
# 12.476649250079015

(z1+v1) * ent(add(tmul(vvc1,tt1),tmul(vvc1,tt1))) - z1 * ent(tmul(vvc1,tt1)) - v1 * ent(tmul(vvc1,tt1))
# 0.0


In all cases the relative entropy is maximised when (a) the cross entropy is maximised and (b) the component entropy is minimised. That is, the relative entropy is maximised when both (i) the component size entropy, $\mathrm{entropy}(A * T)$, and (ii) the component cardinality entropy, $\mathrm{entropy}(V^{\mathrm{C}} * T)$, are low, but low in different ways so that the component size cardinality sum cross entropy, $\mathrm{entropy}(A * T + V^{\mathrm{C}} * T)$, is high.

### Model entropy

Let histogram $A$ have a set of variables $V = \mathrm{vars}(A)$ which is partitioned into query variables $K \subset V$ and label variables $V \setminus K$. Let $T \in \mathcal{T}_{U,\mathrm{f},1}$ be a one functional transform having underlying variables equal to the query variables, $\mathrm{und}(T) = K$. As shown above, given a query state $Q \in K^{\mathrm{CS}}$ that is effective in the sample derived, $R \in (A * T)^{\mathrm{FS}}$ where $\{R\} = (\{Q\}^{\mathrm{U}} * T)^{\mathrm{FS}}$, the probability histogram for the label is $\begin{eqnarray} \{Q\}^{\mathrm{U}} * T * T^{\odot A}~\%~(V \setminus K) &\in& \mathcal{A} \cap \mathcal{P} \end{eqnarray}$ In the deck of cards example, the model of the colours of the suits does not tell us anything about the rank given the suit in the case where the histogram is the entire deck,

qq = unit(sset([llss([(suit,clubs)])]))

vk = vv - kk

rpln(aall(norm(ared(mul(mul(tmul(qq,tt),xx),aa),vk))))
# ({(rank, A)}, 1 % 13)
# ({(rank, J)}, 1 % 13)
# ({(rank, K)}, 1 % 13)
# ({(rank, Q)}, 1 % 13)
# ({(rank, 2)}, 1 % 13)
# ({(rank, 3)}, 1 % 13)
# ({(rank, 4)}, 1 % 13)
# ({(rank, 5)}, 1 % 13)
# ({(rank, 6)}, 1 % 13)
# ({(rank, 7)}, 1 % 13)
# ({(rank, 8)}, 1 % 13)
# ({(rank, 9)}, 1 % 13)
# ({(rank, 10)}, 1 % 13)


So the entropy is high,

ent(ared(mul(mul(tmul(qq,tt),xx),aa),vk))
# 2.5649493574615376


In the case of the special deck, however, our model aligns the suit to the rank via colour, so a query on clubs is always a pip card,

rpln(aall(norm(ared(mul(mul(tmul(qq,tt),xx),bb),vk))))
# ({(rank, A)}, 1 % 10)
# ({(rank, 2)}, 1 % 10)
# ({(rank, 3)}, 1 % 10)
# ({(rank, 4)}, 1 % 10)
# ({(rank, 5)}, 1 % 10)
# ({(rank, 6)}, 1 % 10)
# ({(rank, 7)}, 1 % 10)
# ({(rank, 8)}, 1 % 10)
# ({(rank, 9)}, 1 % 10)
# ({(rank, 10)}, 1 % 10)


and the entropy is lower,

ent(ared(mul(mul(tmul(qq,tt),xx),bb),vk))
# 2.3025850929940455


Similarly, a query on hearts is always a face card,

qq = unit(sset([llss([(suit,hearts)])]))

rpln(aall(norm(ared(mul(mul(tmul(qq,tt),xx),bb),vk))))
# ({(rank, J)}, 1 % 3)
# ({(rank, K)}, 1 % 3)
# ({(rank, Q)}, 1 % 3)


which has still lower entropy,

ent(ared(mul(mul(tmul(qq,tt),xx),bb),vk))
# 1.0986122886681096


If the normalised histogram, $\hat{A} \in \mathcal{A} \cap \mathcal{P}$, is treated as a probability function of a single-state query, the scaled expected entropy of the modelled transformed conditional product, or scaled label entropy, is $\begin{eqnarray} &&\sum_{(R,C) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(A * C~\%~(V \setminus K))\\ &=&\sum_{(R,\cdot) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(\{R\}^{\mathrm{U}} * T^{\odot A}~\%~(V \setminus K)) \end{eqnarray}$

setVarsTransformsHistogramsEntropyLabel :: Set.Set Variable -> Transform -> Histogram -> Double


For example,

def tlent(kk,aa,tt):
return setVarsTransformsHistogramsEntropyLabel(kk,tt,aa)

tlent(sset(),aa,tt)
# 169.42101997711714

tlent(kk,aa,tt)
# 133.37736658799994

tlent(sset(),bb,tt)
# 141.3304045728963

tlent(kk,bb,tt)
105.28675118377913


This is similar to the definition of the scaled expected component entropy, above, $\begin{eqnarray} z \times \mathrm{entropyComponent}(A,T) &:=& \sum_{(R,C) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(A * C)\\ &=&\sum_{(R,\cdot) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(\{R\}^{\mathrm{U}} * T^{\odot A}) \end{eqnarray}$ but now the component is reduced to the label variables, $V \setminus K$,

def cent(aa,tt):
return transformsHistogramsEntropyComponent(tt,aa)

z = size(aa)

z * cent(aa,tt)
# 169.42101997711714

z * cent(bb,tt)
# 141.3304045728963


The label entropy, may be contrasted with the alignment between the derived variables, $W$, and the label variables, $V \setminus K$, $\begin{eqnarray} \mathrm{algn}(A * \mathrm{his}(T)~\%~(W \cup V \setminus K)) \end{eqnarray}$

algn(ared(mul(aa,ttaa(tt)),ww|vk))
# 0.0

algn(ared(mul(bb,ttaa(tt)),ww|vk))
# 17.15244186319102


The alignment varies against the scaled label entropy or scaled query conditional entropy. Let $B = A * \mathrm{his}(T)~\%~(W \cup V \setminus K)$, $\begin{eqnarray} &&\mathrm{algn}(A * \mathrm{his}(T)~\%~(W \cup V \setminus K)) \\ &&\hspace{5em}=\mathrm{algn}(B) \\ &&\hspace{5em}\approx z \times \mathrm{entropy}(B^{\mathrm{X}}) - z \times \mathrm{entropy}(B) \\ &&\hspace{5em}\sim z \times \mathrm{entropy}(B\%W) + z \times \mathrm{entropy}(B\%(V \setminus K)) - z \times \mathrm{entropy}(B) \\ &&\hspace{5em}\sim -(z \times \mathrm{entropy}(B) - z \times \mathrm{entropy}(B\%W)) \\ &&\hspace{5em}= -\sum_{R \in (B\%W)^{\mathrm{FS}}} (B\%W)_R \times \mathrm{entropy}(B * \{R\}^{\mathrm{U}}~\%~(V \setminus K))\\ &&\hspace{5em}= -\sum_{(R,C) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(A * C~\%~(V \setminus K)) \end{eqnarray}$ The label entropy, may also be compared to the slice entropy, which is the sum of the sized entropies of the contingent slices reduced to the label variables, $V \setminus K$, $\sum_{R \in (A\%K)^{\mathrm{FS}}} (A\%K)_R \times \mathrm{entropy}(A * \{R\}^{\mathrm{U}}~\%~(V \setminus K))$

def lent(kk,aa):
return size(aa) * (ent(aa) - ent(ared(aa,sset(kk))))

lent(sset(),aa)
# 205.46467336623434

lent(kk,aa)
# 133.37736658800003

lent(sset(),bb)
# 169.42101997711714

lent(kk,bb)
# 105.28675118377922


In the case where the relation between the derived variables and the label variables is functional or causal, $\begin{eqnarray} \mathrm{split}(W,(A * \mathrm{his}(T)~\%~(W \cup V \setminus K))^{\mathrm{FS}}) &\in& W^{\mathrm{CS}} \to (V \setminus K)^{\mathrm{CS}} \end{eqnarray}$ the label entropy is zero, $\begin{eqnarray} \sum_{(R,C) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(A * C~\%~(V \setminus K)) &=& 0 \end{eqnarray}$ This would be the case, for example, for a deck consisting of 26 ace of spades and 26 queen of hearts,

cc = mul(scalar(26),unit(sset([
llss([(suit,spades),(rank,ace)]),
llss([(suit,hearts),(rank,queen)])])))

rpln(aall(cc))
# ({(rank, A), (suit, spades)}, 26 % 1)
# ({(rank, Q), (suit, hearts)}, 26 % 1)

rpln(aall(tmul(cc,tt)))
# ({(colour, black)}, 26 % 1)
# ({(colour, red)}, 26 % 1)

rpln(aall(ared(mul(cc,ttaa(tt)),ww|vk)))
# ({(colour, black), (rank, A)}, 26 % 1
# ({(colour, red), (rank, Q)}, 26 % 1)

ssplit = setVarsSetStatesSplit

rpln(ssplit(ww,states(ared(mul(cc,ttaa(tt)),ww|vk))))
# ({(colour, black)}, {(rank, A)})
# ({(colour, red)}, {(rank, Q)})

tlent(kk,cc,tt)
# 0.0

algn(ared(mul(cc,ttaa(tt)),ww|vk))
# 32.31474810951032


Now the model predicts the rank given the suit,

qq = unit(sset([llss([(suit,clubs)])]))

rpln(aall(norm(ared(mul(mul(tmul(qq,tt),xx),cc),vk))))
# ({(rank, A)}, 1 % 1)

qq = unit(sset([llss([(suit,hearts)])]))

rpln(aall(norm(ared(mul(mul(tmul(qq,tt),xx),cc),vk))))
# ({(rank, Q)}, 1 % 1)


So label entropy is a measure of the ambiguity in the relation between the derived variables and the label variables. Negative label entropy may be viewed as the degree to which the derived variables of the model predict the label variables. In the cases of low label entropy, or high causality, the derived variables and the label variables are correlated and therefore aligned, $\mathrm{algn}(A * \mathrm{his}(T)~\%~(W \cup V \setminus K)) > 0$. In these cases the derived histogram tends to the diagonal, $\mathrm{algn}(A * T) > 0$.

### Example - a weather forecast

Some of the concepts above regarding transform entropy can be demonstrated with the sample of some weather measurements created in States, histories and histograms,

def lluu(ll):
return listsSystem([(v,sset(ww)) for (v,ww) in ll])

def llhh(vv,ev):
return listsHistory([(IdInt(i), llss(zip(vv,ll))) for (i,ll) in ev])

def red(aa,ll):
return setVarsHistogramsReduce(sset(ll),aa)

def ssplit(ll,aa):
return setVarsSetStatesSplit(sset(ll),states(aa))

def aarr(aa):
return [(ss,float(q)) for (ss,q) in aall(aa)]

def lltt(kk,ww,qq):
return trans(unit(sset([llss(zip(kk + ww,ll)) for ll in qq])),sset(ww))

def query(qq,tt,aa,ll):
return norm(red(mul(mul(tmul(qq,tt),ttaa(tt)),aa),ll))

[pressure,cloud,wind,rain] = map(VarStr,["pressure","cloud","wind","rain"])

[low,medium,high,none,light,heavy,strong] = map(ValStr,["low","medium","high","none","light","heavy","strong"])



uu = lluu([
(pressure, [low,medium,high]),
(cloud,    [none,light,heavy]),
(wind,     [none,light,strong]),
(rain,     [none,light,heavy])])

vv = uvars(uu)

hh = llhh([pressure,cloud,wind,rain],[
(1,[high,none,none,none]),
(2,[medium,light,none,light]),
(3,[high,none,light,none]),
(4,[low,heavy,strong,heavy]),
(5,[low,none,light,light]),
(6,[medium,none,light,light]),
(7,[low,heavy,light,heavy]),
(8,[high,none,light,none]),
(9,[medium,light,strong,heavy]),
(10,[medium,light,light,light]),
(11,[high,light,light,heavy]),
(12,[medium,none,none,none]),
(13,[medium,light,none,none]),
(14,[high,light,strong,light]),
(15,[medium,none,light,light]),
(16,[low,heavy,strong,heavy]),
(17,[low,heavy,light,heavy]),
(18,[high,none,none,none]),
(19,[low,light,none,light]),
(20,[high,none,none,none])])

aa = hhaa(hh)

uu
# {(cloud, {heavy, light, none}), (pressure, {high, low, medium}), (rain, {heavy, light, none}), (wind, {light, none, strong})}

vv
# {cloud, pressure, rain, wind}

rpln(aall(aa))
# ({(cloud, heavy), (pressure, low), (rain, heavy), (wind, light)}, 2 % 1)
# ({(cloud, heavy), (pressure, low), (rain, heavy), (wind, strong)}, 2 % 1)
# ({(cloud, light), (pressure, high), (rain, heavy), (wind, light)}, 1 % 1)
# ({(cloud, light), (pressure, high), (rain, light), (wind, strong)}, 1 % 1)
# ({(cloud, light), (pressure, low), (rain, light), (wind, none)}, 1 % 1)
# ({(cloud, light), (pressure, medium), (rain, heavy), (wind, strong)}, 1 % 1)
# ({(cloud, light), (pressure, medium), (rain, light), (wind, light)}, 1 % 1)
# ({(cloud, light), (pressure, medium), (rain, light), (wind, none)}, 1 % 1)
# ({(cloud, light), (pressure, medium), (rain, none), (wind, none)}, 1 % 1)
# ({(cloud, none), (pressure, high), (rain, none), (wind, light)}, 2 % 1)
# ({(cloud, none), (pressure, high), (rain, none), (wind, none)}, 3 % 1)
# ({(cloud, none), (pressure, low), (rain, light), (wind, light)}, 1 % 1)
# ({(cloud, none), (pressure, medium), (rain, light), (wind, light)}, 2 % 1)
# ({(cloud, none), (pressure, medium), (rain, none), (wind, none)}, 1 % 1)

size(aa)
# 20 % 1


We considered the case where we wish to predict the rain given the pressure, cloud and wind in Transforms, by creating a transform which related cloud and wind,

cloud_and_wind = VarStr("cloud_and_wind")

tt = lltt([cloud,wind],[cloud_and_wind],[
[none, none, none],
[none, light, light],
[none, strong, light],
[light, none, light],
[light, light, light],
[light, strong, light],
[heavy, none, strong],
[heavy, light, strong],
[heavy, strong, strong]])



The derived, $A * T$, is

rpln(aall(tmul(aa,tt)))
# ({(cloud_and_wind, light)}, 12 % 1)
# ({(cloud_and_wind, none)}, 4 % 1)
# ({(cloud_and_wind, strong)}, 4 % 1)

rpln(aarr(norm(tmul(aa,tt))))
# ({(cloud_and_wind, light)}, 0.6)
# ({(cloud_and_wind, none)}, 0.2)
# ({(cloud_and_wind, strong)}, 0.2)


The derived entropy, $\mathrm{entropy}(A * T)$, is

ent = histogramsEntropy

ent(tmul(aa,tt))
# 0.9502705392332347


The derived entropy is positive and less than or equal to the logarithm of the derived volume, $0 \leq \mathrm{entropy}(A * T) \leq \ln w$,

w = 3

log(w)
# 1.0986122886681098


Complementary to the derived entropy is the expected component entropy, $\mathrm{entropyComponent}(A,T)$,

cent = transformsHistogramsEntropyComponent

cent(tt,aa)
# 1.603411018796562


The cartesian derived, $V^{\mathrm{C}} * T$, is

vvc = unit(cart(uu,vv))

size(vvc)
# 81 % 1

rpln(aall(tmul(vvc,tt)))
# ({(cloud_and_wind, light)}, 45 % 1)
# ({(cloud_and_wind, none)}, 9 % 1)
# ({(cloud_and_wind, strong)}, 27 % 1)

rpln(aarr(norm(tmul(vvc,tt))))
# ({(cloud_and_wind, light)}, 0.5555555555555556)
# ({(cloud_and_wind, none)}, 0.1111111111111111)
# ({(cloud_and_wind, strong)}, 0.3333333333333333)


The cartesian derived entropy, $\mathrm{entropy}(V^{\mathrm{C}} * T)$, is

ent(tmul(vvc,tt))
# 0.9368883075390159


The component size cardinality cross entropy, $\mathrm{entropyCross}(A * T,V^{\mathrm{C}} * T)$, is

crent = histogramsHistogramsEntropyCross

crent(tmul(aa,tt),tmul(vvc,tt))
# 1.0118393721421373

crent(tmul(aa,tt),tmul(vvc,tt)) >= ent(tmul(aa,tt))
# True


The component cardinality size cross entropy, $\mathrm{entropyCross}(V^{\mathrm{C}} * T,A * T)$, is

crent(tmul(vvc,tt),tmul(aa,tt))
# 0.9990977520629283

crent(tmul(vvc,tt),tmul(aa,tt)) >= ent(tmul(aa,tt))
# True


The sum of the derived and cartesian derived, $A * T + V^{\mathrm{C}} * T$, is

rpln(aall(add(tmul(aa,tt),tmul(vvc,tt))))
# ({(cloud_and_wind, light)}, 57 % 1)
# ({(cloud_and_wind, none)}, 13 % 1)
# ({(cloud_and_wind, strong)}, 31 % 1)

rpln(aarr(norm(add(tmul(aa,tt),tmul(vvc,tt)))))
# ({(cloud_and_wind, light)}, 0.5643564356435643)
# ({(cloud_and_wind, none)}, 0.12871287128712872)
# ({(cloud_and_wind, strong)}, 0.3069306930693069)


The component size cardinality sum cross entropy, $\mathrm{entropy}(A * T + V^{\mathrm{C}} * T)$, is

ent(add(tmul(aa,tt),tmul(vvc,tt)))
# 0.9492604450332509

ent(add(tmul(aa,tt),tmul(vvc,tt))) <= log(w)
# True


The component size cardinality relative entropy, $\mathrm{entropyRelative}(A * T,V^{\mathrm{C}} * T)$, is the component size cardinality cross entropy minus the component size entropy, $\mathrm{entropyCross}(A * T,V^{\mathrm{C}} * T)~-~\mathrm{entropy}(A * T)$,

crent(tmul(aa,tt),tmul(vvc,tt)) - ent(tmul(aa,tt))
# 0.06156883290890258


The component cardinality size relative entropy, $\mathrm{entropyRelative}(V^{\mathrm{C}} * T,A * T)$, is the component cardinality size cross entropy minus the component cardinality entropy, $\mathrm{entropyCross}(V^{\mathrm{C}} * T,A * T)~-~\mathrm{entropy}(V^{\mathrm{C}} * T)$,

crent(tmul(vvc,tt),tmul(aa,tt)) - ent(tmul(vvc,tt))
# 0.062209444523912416


The size-volume scaled component size cardinality sum relative entropy is the size-volume scaled component size cardinality sum cross entropy minus the size-volume scaled component size cardinality sum entropy, $\begin{eqnarray} (z+v) \times \mathrm{entropy}(A * T + V^{\mathrm{C}} * T) - z \times \mathrm{entropy}(A * T) - v \times \mathrm{entropy}(V^{\mathrm{C}} * T) \end{eqnarray}$

z = size(aa)

v = vol(uu,vv)

(z+v) * ent(add(tmul(aa,tt),tmul(vvc,tt))) - z * ent(tmul(aa,tt)) - v * ent(tmul(vvc,tt))
# 0.9819412530333693

(z+v) * log(w)
# 110.95984115547908


Define the abbreviation rent for the size-volume scaled component size cardinality sum relative entropy,

def rent(aa,bb):
a = size(aa)
b = size(bb)
return (a+b) * ent(add(aa,bb)) - a * ent(aa) - b * ent(bb)

rent(tmul(aa,tt),tmul(vvc,tt))
# 0.9819412530333693


It was shown that the alignment between cloud_and_wind and rain is greater than the alignments between any of cloud, wind or pressure and rain,

algn(red(aa,[pressure,rain]))
# 4.278766678519384

algn(red(aa,[cloud,rain]))
# 6.4150379630063465

algn(red(aa,[wind,rain]))
# 3.930131313218345

algn(red(mul(aa,ttaa(tt)),[cloud_and_wind,rain]))
# 6.743705969634357


Define the abbreviation tlalgn for the alignment of the derived variables and the label variables,

def ared(aa,vv):
return setVarsHistogramsReduce(vv,aa)

def tlalgn(tt,aa,ll):
return algn(ared(mul(aa,ttaa(tt)),der(tt)|sset(ll)))

tlalgn(tt,aa,[rain])
# 6.743705969634357


The alignments are all zero for a cartesian sample,

algn(vvc)
# 0.0

algn(tmul(vvc,tt))
# 0.0


and for the independent and formal,

algn(ind(aa))
# 0.0

algn(tmul(ind(aa),tt))
# 0.0


In the case of medium pressure, heavy cloud and light winds, the forecast for rain is heavy,

qq1 = hhaa(llhh([pressure,cloud,wind],[(1,[medium,heavy,light])]))

rpln(aarr(query(qq1,tt,aa,[rain])))
# ({(rain, heavy)}, 1.0)


So the entropy for this query is zero,

ent(query(qq1,tt,aa,[rain]))
# -0.0


Compare this to the cartesian where all outcomes are equally probable,

rpln(aarr(query(qq1,tt,vvc,[rain])))
# ({(rain, heavy)}, 0.3333333333333333)
# ({(rain, light)}, 0.3333333333333333)
# ({(rain, none)}, 0.3333333333333333)

ent(query(qq1,tt,vvc,[rain]))
# 1.0986122886681096


For some queries the model is ambiguous. For example, when the pressure is low, but there is no cloud and winds are light, the forecast is usually for light rain, but not always,

qq2 = hhaa(llhh([pressure,cloud,wind],[(1,[low,none,light])]))

rpln(aarr(query(qq2,tt,aa,[rain])))
# ({(rain, heavy)}, 0.16666666666666666)
# ({(rain, light)}, 0.5833333333333334)
# ({(rain, none)}, 0.25)


In this case the entropy is higher,

ent(query(qq2,tt,aa,[rain]))
# 0.9596147939120492


but still lower than for the cartesian,

ent(query(qq2,tt,vvc,[rain]))
# 1.0986122886681096


If the normalised histogram, $\hat{A} \in \mathcal{A} \cap \mathcal{P}$, is treated as a probability function of a single-state query, the scaled label entropy, is $\begin{eqnarray} \sum_{(R,C) \in T^{-1}} (A * T)_R \times \mathrm{entropy}(A * C~\%~(V \setminus K)) \end{eqnarray}$

def tlent(tt,aa,ll):
return setVarsTransformsHistogramsEntropyLabel(vars(aa)-sset(ll),tt,aa)

tlent(tt,aa,[rain])
# 11.51537752694459


An idea of the scale of the label entropy can be obtained from the cartesian,

z/v * tlent(tt,vvc,[rain])
# 21.97224577336219


This is similar to the definition of the scaled expected component entropy, $z \times \mathrm{entropyComponent}(A,T)$,

z * cent(tt,aa)
# 32.06822037593124

z * cent(tt,vvc)
# 69.15121694266844


The label entropy, may be contrasted with the alignment between the derived variables, $W$, and the label variables, $V \setminus K$, $\mathrm{algn}(A * \mathrm{his}(T)~\%~(W \cup V \setminus K))$

algn(red(mul(aa,ttaa(tt)),[cloud_and_wind,rain]))
# 6.743705969634357


or

tlalgn(tt,aa,[rain])
# 6.743705969634357


This may be compared to the diagonalised for an idea of scale,

algn(resize(size(aa),regdiag(3,2)))
# 15.413144235093519


The label entropy, may also be compared to the slice entropy, which is the sum of the sized entropies of the contingent slices reduced to the label variables, $V \setminus K$, $\sum_{R \in (A\%K)^{\mathrm{FS}}} (A\%K)_R \times \mathrm{entropy}(A * \{R\}^{\mathrm{U}}~\%~(V \setminus K))$

def lent(aa,ll):
return size(aa) * (ent(aa) - ent(ared(aa,vars(aa)-sset(ll))))

lent(aa,[rain])
# 1.3862943611198908

z/v * lent(vvc,[rain])
# 21.972245773362047


That is, the model label entropy is much higher than the sample label entropy, but model queries may be applied to ineffective sample states.

Now let us compare the entropy properties of several models. First redefine the cloud_and_wind model as $T_{\mathrm{cw}}$,

ttcw = tt


Now consider a model $T_{\mathrm{c}}$ which consists of a literal reframe of the cloud variable,

cloud2 = VarStr("cloud2")

ttc = lltt([cloud],[cloud2],[
[none, none],
[light, light],
[heavy, heavy]])

rpln(aarr(norm(tmul(aa,ttc))))
# ({(cloud2, heavy)}, 0.2)
# ({(cloud2, light)}, 0.35)
# ({(cloud2, none)}, 0.45)

ent(tmul(aa,ttc))
# 1.0486537893593546


So the simpler model, $T_{\mathrm{c}}$, has higher derived entropy than $T_{\mathrm{cw}}$.

Consider the relative entropy,

rent(tmul(aa,ttc),tmul(vvc,ttc))
# 0.8099580712542576


Now consider the alignment between the derived variable and the label variable,

tlalgn(ttc,aa,[rain])
# 6.4150379630063465

algn(red(aa,[cloud,rain]))
# 6.4150379630063465


So the simpler model, $T_{\mathrm{c}}$, has both lower relative entropy and lower label alignment than $T_{\mathrm{cw}}$.

Now consider queries on the model,

qq1 = hhaa(llhh([pressure,cloud,wind],[(1,[medium,heavy,light])]))

rpln(aarr(query(qq1,ttc,aa,[rain])))
# ({(rain, heavy)}, 1.0)

qq2 = hhaa(llhh([pressure,cloud,wind],[(1,[low,none,light])]))

rpln(aarr(query(qq2,ttc,aa,[rain])))
# ({(rain, light)}, 0.3333333333333333)
# ({(rain, none)}, 0.6666666666666666)

tlent(ttc,aa,[rain])
# 12.418526752441055


So the simpler model, $T_{\mathrm{c}}$, has higher label entropy than $T_{\mathrm{cw}}$. In short, the simpler model, $T_{\mathrm{c}}$, is generally a worse predictor of label than $T_{\mathrm{cw}}$.

Consider if a better predictor of the rain can be made by constructing a transform $T_{\mathrm{cp}}$ that relates cloud and pressure,

algn(red(aa,[pressure,cloud]))
# 4.6232784937782885

cloud_and_pressure = VarStr("cloud_and_pressure")

ttcp = lltt([cloud,pressure],[cloud_and_pressure],[
[none, high, none],
[none, medium, light],
[none, low, light],
[light, high, light],
[light, medium, light],
[light, low, light],
[heavy, high, strong],
[heavy, medium, strong],
[heavy, low, strong]])

rpln(aarr(norm(tmul(aa,ttcp))))
# ({(cloud_and_pressure, light)}, 0.55)
# ({(cloud_and_pressure, none)}, 0.25)
# ({(cloud_and_pressure, strong)}, 0.2)

ent(tmul(aa,ttcp))
# 0.9972715231823841


So the simpler model, $T_{\mathrm{cp}}$, has higher derived entropy than $T_{\mathrm{cw}}$, but not as high as $T_{\mathrm{c}}$.

Consider the relative entropy,

rent(tmul(aa,ttcp),tmul(vvc,ttcp))
# 1.4736881918377236


Now consider the alignment between the derived variable and the label variable,

tlalgn(ttcp,aa,[rain])
# 8.020893995655356


So the new model, $T_{\mathrm{cp}}$, has both higher relative entropy and higher label alignment than $T_{\mathrm{cw}}$, although the derived entropy is higher.

Now consider queries on the model,

rpln(aarr(query(qq1,ttcp,aa,[rain])))
# ({(rain, heavy)}, 1.0)

rpln(aarr(query(qq2,ttcp,aa,[rain])))
# ({(rain, heavy)}, 0.18181818181818182)
# ({(rain, light)}, 0.6363636363636364)
# ({(rain, none)}, 0.18181818181818182)

tlent(ttcp,aa,[rain])
# 9.982888235155102


So the new model, $T_{\mathrm{cp}}$, has lower label entropy than $T_{\mathrm{cw}}$. In short, the new model, $T_{\mathrm{cp}}$, is generally a better predictor of label than $T_{\mathrm{cw}}$.

To summarise,

[ent(tmul(aa,tt)) for tt in [ttc, ttcw, ttcp]]
# [1.0486537893593546, 0.9502705392332347, 0.9972715231823841]

[cent(tt,aa) for tt in [ttc, ttcw, ttcp]]
# [1.5050277686704419, 1.603411018796562, 1.5564100348474128]

[rent(tmul(aa,tt),tmul(vvc,tt)) for tt in [ttc, ttcw, ttcp]]
# [0.8099580712542576, 0.9819412530333693, 1.4736881918377236]

[tlalgn(tt,aa,[rain]) for tt in [ttc, ttcw, ttcp]]
# [6.4150379630063465, 6.743705969634357, 8.020893995655356]

[tlent(tt,aa,[rain]) for tt in [ttc, ttcw, ttcp]]
# [12.418526752441055, 11.51537752694459, 9.982888235155102]


The weather forecast example continues in Functional definition sets.

top