Conditional entropy optimisation
Haskell commentary on the implementation of Tractable and Practicable Inducers/Haskell Implementation/Conditional entropy optimisation
Sections
Conditional entropy tuple set builder
Conditional entropy fud decomper
Conditional entropy tuple set builder
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 (Text)
\[
\begin{eqnarray}
M &=& \mathrm{topd}(\mathrm{qmax})(\mathrm{elements}(Z_{P,A,\mathrm{L}})) \subset \mathrm{P}(V \setminus L)
\end{eqnarray}
\]
The conditional entropy tuple set builder parametersBuilderConditionalVars is defined in module AlignmentPracticable.
parametersBuilderConditionalVars ::
Integer -> Integer -> Integer -> Set.Set Variable -> Histogram ->
Maybe (Map.Map (Set.Set Variable) Double)
parametersBuilderConditionalVars kmax omax qmax ll aa
| kmax < 0 || omax < 0 || qmax < 0 = Nothing
| otherwise = Just $ bot qmax $ buildc rr rr
where
vvk = vars aa `minus` ll
rr = bot omax $ llmm [(sgl w, ent (aa `red` (ll `add` w)) - ent (aa `red` (sgl w))) | w <- qqll vvk]
buildc qq nn = if mm /= Map.empty then buildc mm (nn `Map.union` mm) else nn
where
pp = llqq [jj | (kk,e) <- mmll qq, e > 0, w <- qqll (vvk `minus` kk), let jj = kk `add` w]
mm = bot omax $ llmm [(jj, ent (aa `red` (ll `union` jj)) - ent (aa `red` jj)) |
jj <- qqll pp, card jj <= kmax]
...
For example,
let buildcond vvl aa kmax omax qmax = sort $ map (\(a,b) -> (b,a)) $ Map.toList $ fromJust $ parametersBuilderConditionalVars kmax omax qmax vvl aa
let (kmax,omax,qmax) = (1, 5, 5)
rpln $ buildcond vvl aa kmax omax qmax
"(6.445777995546464e-2,{odor})"
"(0.3593018375305004,{spore-print-color})"
"(0.4034743011923405,{gill-color})"
"(0.47206538234114515,{ring-type})"
"(0.49514434957356657,{stalk-surface-above-ring})"
let (kmax,omax) = (2, 10, 10)
rpln $ buildcond vvl aa kmax omax qmax
"(2.082990753054048e-2,{odor,spore-print-color})"
"(3.6279340021870166e-2,{cap-color,odor})"
"(3.849645066616292e-2,{gill-color,odor})"
"(4.566068343589347e-2,{odor,stalk-shape})"
"(4.619210440231036e-2,{odor,stalk-color-below-ring})"
"(4.6657422349796196e-2,{habitat,odor})"
"(4.909372014653002e-2,{odor,stalk-surface-below-ring})"
"(5.1254420042391224e-2,{odor,population})"
"(5.16165100197532e-2,{cap-shape,odor})"
"(5.3577275552557424e-2,{odor,stalk-color-above-ring})"
let (kmax,omax) = (3, 10, 10)
rpln $ buildcond vvl aa kmax omax qmax
"(6.893838773649907e-3,{habitat,odor,spore-print-color})"
"(8.190808632908553e-3,{gill-size,odor,spore-print-color})"
"(8.190808632908997e-3,{odor,ring-number,spore-print-color})"
"(8.951100722878191e-3,{odor,spore-print-color,stalk-surface-below-ring})"
"(9.454387885879711e-3,{habitat,odor,stalk-root})"
"(9.511843838571288e-3,{cap-color,odor,spore-print-color})"
"(9.58215032701304e-3,{cap-color,odor,stalk-root})"
"(9.812725049147542e-3,{odor,spore-print-color,stalk-color-below-ring})"
"(1.1450498672664011e-2,{bruises,habitat,odor})"
"(1.2142896254066393e-2,{cap-color,odor,population})"
Conditional entropy fud decomper
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}}))$, (Text).
The decomper is defined in module AlignmentPracticable,
parametersSystemsDecomperConditional ::
Integer -> Integer -> System -> Set.Set Variable -> Histogram ->
Maybe (System, DecompFud)
as
parametersSystemsDecomperConditional kmax omax uu ll aa
...
| otherwise = Just $ decomp uu emptyTree 1
where
decomp uu zz f s
| zz == emptyTree && nnr == [] = (uu, decompFudEmpty)
| zz == emptyTree = decomp uur zzr (f+1)
| mm == [] = (uu, zzdf (zztrim zz))
| otherwise = decomp uuc zzc (f+1)
where
nnr = lenter kmax omax 1 ll aa
[(kkr,_)] = nnr
ffr = if nnr /= [] then vvff uu kkr f else fudEmpty
uur = uu `uunion` fsys ffr
zzr = tsgl (stateEmpty,ffr)
mm = [(e,nn,ss,bb) | (nn,yy) <- qqll (treesPlaces zz),
let rrc = llsthis nn, let hhc = llfhis nn, let (_,ff) = last nn, ff /= fudEmpty,
ss <- qqll (cart uu (fder ff) `minus` dom (treesRoots yy)),
let xx = hhc `union` rrc `add` unit (sgl ss),
let bb = apply vv vv xx aa,
let e = fromRational (size bb) * ent (bb `red` ll)
e > 0]
(_,nn,ss,bb) = last $ sort mm
nnc = lenter kmax omax 1 ll bb
[(kkc,_)] = nnc
ffc = if nnr /= [] then vvff uu kkc f else fudEmpty
uuc = uu `uunion` fsys ffc
zzc = pathsTree $ treesPaths zz `add` (nn ++ [(ss,ffc)])
lenter kmax omax qmax ll aa = mmll $ fromJust $ parametersBuilderConditionalVars kmax omax qmax ll aa
...
For example,
let decompercond vvl aa kmax omax = fromJust $ parametersSystemsDecomperConditional kmax omax (sys aa) vvl aa
let (kmax,omax) = (1, 2)
let (uu1,df) = decompercond vvl aa kmax omax
rp $ dfund df
"{cap-color,gill-size,habitat,odor,spore-print-color}"
rp $ fder $ dfff df
"{<<1,1>,1>,<<2,1>,1>,<<3,1>,1>,<<4,1>,1>,<<5,1>,1>}"
let dfll = qqll . treesPaths . dfzz
rpln $ map (map (fund.snd)) $ dfll df
"[{odor},{spore-print-color},{habitat},{cap-color}]"
"[{odor},{spore-print-color},{habitat},{gill-size}]"
rpln $ map (map (fvars.snd)) $ dfll df
"[{odor,<<1,1>,1>},{spore-print-color,<<2,1>,1>},{habitat,<<3,1>,1>},{cap-color,<<4,1>,1>}]"
"[{odor,<<1,1>,1>},{spore-print-color,<<2,1>,1>},{habitat,<<3,1>,1>},{gill-size,<<5,1>,1>}]"
let ff = fromJust $ systemsDecompFudsNullablePracticable uu1 df 1
let uu2 = uu `uunion` (fsys ff)
let hh = aahr uu aa
let hhb = hrfmul uu2 ff hh
let hrlent uu hh ww vvl = ent (hhaa $ hrhh uu $ hh `hrhrred` (ww `union` vvl)) - ent (hhaa $ hrhh uu $ hh `hrhrred` ww)
hrlent uu2 hhb (fder ff) vvl
-4.440892098500626e-16
rpln $ qqll $ ssplit (fvars ff) $ states $ hhaa $ hrhh uu2 $ hhb `hrhrred` (fder ff `union` vvl)
"({(<<1,n>,1>,1),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,2),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,3),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,4),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,5),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,6),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,1),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,2),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,3),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,4),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,5),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,6),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,1),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,1),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,3),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,9),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,10),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,4),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,6),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,7),(<<4,n>,1>,null),(<<5,n>,1>,1)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,7),(<<4,n>,1>,null),(<<5,n>,1>,2)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,9),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,8),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,9),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
or, re-arranged to show the decomposition,
"({(<<1,n>,1>,1),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,2),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,3),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,4),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,5),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,6),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,8),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,9),(<<2,n>,1>,null),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,1),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,2),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,3),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,4),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,5),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,6),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,9),(<<3,n>,1>,null),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,1),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,4),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,6),(<<4,n>,1>,null),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,1),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,3),(<<5,n>,1>,null)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,9),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,2),(<<4,n>,1>,10),(<<5,n>,1>,null)},{(edible,poisonous)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,7),(<<4,n>,1>,null),(<<5,n>,1>,1)},{(edible,edible)})"
"({(<<1,n>,1>,7),(<<2,n>,1>,8),(<<3,n>,1>,7),(<<4,n>,1>,null),(<<5,n>,1>,2)},{(edible,poisonous)})"