Conditional entropy optimisation
Haskell commentary on the implementation of Tractable and Practicable Inducers/Conditional entropy optimisation
Sections
Limited-dimension conditional entropy tuple set list minimiser
Limited-dimension conditional entropy fud decompositions tree searcher
Limited-dimension conditional entropy tuple set list minimiser
Given a histogram $A$ and a set of query variables $K \subset V$, the scaled label entropy is the degree to which the histogram is ambiguous or non-causal in the query variables, $K$. It 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)) \]
The scaled label entropy is also known as the scaled query conditional entropy, \[ \begin{eqnarray} &&\sum_{R \in (A\%K)^{\mathrm{FS}}} (A\%K)_R \times \mathrm{entropy}(A * \{R\}^{\mathrm{U}}~\%~(V \setminus K)) \\ &=&-\sum_{S \in A^{\mathrm{FS}}} A_S \ln \frac{A_S}{(A\%K * V^{\mathrm{C}})_S} \\ &=&-\sum_{S \in A^{\mathrm{FS}}} A_S \ln (A/(A\%K))_S \\ &=&z \times \mathrm{entropy}(A) - z \times \mathrm{entropy}(A\%K) \end{eqnarray} \] When the histogram, $A$, is causal in the query variables, $\mathrm{split}(K,A^{\mathrm{FS}}) \in K^{\mathrm{CS}} \to (V \setminus K)^{\mathrm{CS}}$, the label entropy is zero because each slice is an effective singleton, $\forall R \in (A\%K)^{\mathrm{FS}}~(|A^{\mathrm{F}} * \{R\}^{\mathrm{U}}|=1)$. In this case the label state is unique for every effective query state. By contrast, when the label variables are independent of the query variables, $A = Z * \hat{A}\%K * \hat{A}\%(V \setminus K)$, the label entropy is maximised. See Entropy and alignment and Model entropy.
Given a set of label variables, $L \subset V$, an optimisation of tuple subsets of the query variables $K \subset V \setminus L$ that minimise the query conditional entropy or label entropy can be defined. Define the limited-dimension conditional entropy tuple set list minimiser \[ Z_{P,A,\mathrm{L}} = \mathrm{maximiseLister}(X_{P,A,\mathrm{L}},P_{P,A,\mathrm{L}},\mathrm{top}(\mathrm{omax}),R_{P,A,\mathrm{L}}) \] where (i) the optimiser function is \[ \begin{eqnarray} X_{P,A,\mathrm{L}} &=& \{(K,-(\mathrm{entropy}(A~\%~(K \cup L))-\mathrm{entropy}(A~\%~K))) : K \subseteq V \setminus L\} \end{eqnarray} \] and (ii) the neighbourhood function is \[ \begin{eqnarray} &&P_{P,A,\mathrm{L}}(M) = \{(J,X_{P,A,\mathrm{L}}(J)) : \\ &&\hspace{2em}(K,\cdot) \in M,~w \in V \setminus L \setminus K,~J = K \cup \{w\},~|J| \leq \mathrm{kmax}\} \end{eqnarray} \] and (iii) the initial subset is \[ \begin{eqnarray} R_{P,A,\mathrm{L}} &=& \{(\{w\},X_{P,A,\mathrm{L}}(\{w\})) : w \in V \setminus L\} \end{eqnarray} \] Then the conditional entropy optimised limited-dimension conditional entropy tuple set list, $M$, is (Haskell) (Python) \[ \begin{eqnarray} M &=& \mathrm{topd}(\mathrm{qmax})(\mathrm{elements}(Z_{P,A,\mathrm{L}})) \subset \mathrm{P}(V \setminus L) \end{eqnarray} \]
Limited-dimension conditional entropy fud decompositions tree searcher
The limited-dimension conditional entropy fud decompositions tree searcher chooses an immediate super-decomposition from the conditional entropy optimised tuple set lists of the children slices until the leaf slices have zero conditional entropy. The fuds are singletons of the self partition transforms of the conditional entropy tuples. Define the limited-dimension conditional entropy fud decompositions tree searcher \[ Z_{P,A,\mathrm{L,D,F}} = \mathrm{searchTreer}(\mathcal{D}_{\mathrm{F},\infty,U,V},P_{P,A,\mathrm{L,D,F}},R_{P,A,\mathrm{L,D,F}}) \] where the neighbourhood function returns a singleton \[ \begin{eqnarray} &&P_{P,A,\mathrm{L,D,F}}(D) = \{E : \\ &&\hspace{2em}(\cdot,S,G,L) \in \mathrm{maxd}(\mathrm{order}(D_{\mathbf{Q} \times \mathrm{S} \times \mathcal{X}^2},\{(e,S,G,L) : \\ &&\hspace{4em}(L,Y) \in \mathrm{places}(D),\\ &&\hspace{4em}R_L = \bigcup \mathrm{dom}(\mathrm{set}(L)),~H_L = \bigcup \mathrm{ran}(\mathrm{set}(L)),\\ &&\hspace{4em}(\cdot,F) = L_{|L|},~W=\mathrm{der}(F),\\ &&\hspace{4em}S \in W^{\mathrm{CS}} \setminus \mathrm{dom}(\mathrm{dom}(Y)),\\ &&\hspace{4em}B = \mathrm{apply}(V_A,V_A,\mathrm{his}(H_L) \cup \{\{R_L \cup S\}^{\mathrm{U}}\},A),\\ &&\hspace{4em}e = \mathrm{size}(B) * \mathrm{entropy}(B~\%~L),~e>0,\\ &&\hspace{4em}K \in \mathrm{maxd}(\mathrm{elements}(Z_{P,A,\mathrm{L}})),\\ &&\hspace{4em}G = \{K^{\mathrm{CS\{\}T}}\}\})),\\ &&\hspace{2em}M=L \cup \{(|L|+1,(S,G))\},\\ &&\hspace{2em}E = \mathrm{tree}(\mathrm{paths}(D) \setminus \{L\} \cup \{M\})\} \end{eqnarray} \] where \[ \begin{eqnarray} &&R_{P,A,\mathrm{L,D,F}} = \{\{((\emptyset,G),\emptyset)\} : \\ &&\hspace{2em}G \in \mathrm{maxd}(\mathrm{order}(D_{\mathrm{F}},\{G : \\ &&\hspace{4em}K \in \mathrm{maxd}(\mathrm{elements}(Z_{P,A,\mathrm{L}})),\\ &&\hspace{4em}G = \{K^{\mathrm{CS\{\}T}}\}\}))\} \end{eqnarray} \] The fud decomposition is $D$ where $\{D\} = \mathrm{leaves}(\mathrm{tree}(Z_{P,A,\mathrm{L,D,F}}))$, (Haskell).