Object Representation for Lattice-Based Machine Learning

This is the fourth article in a series (links to the first , second and thirdarticles), devoted to the machine learning system based on the theory of lattices, called "VKF-system". The program uses algorithms based on Markov chains to generate the causes of the target property by calculating a random subset of similarities between some groups of learning objects. This article describes the representation of objects through bit strings in order to compute the similarities by bitwise multiplication of the corresponding representations. Objects with discrete features require some technique from Formal Concept Analysis. The case of objects with continuous features uses logistic regression, dividing the area of ​​change into subintervals using information theory and a representation corresponding to the convex hull of the compared intervals.

1 Discrete signs

, , - . , ""/"". 'null' ( '_' ), () .

. . , .

( , ), () .

$$$\langle{L,\wedge,\vee}\rangle$ $$$G$ () $$$\wedge$- $$$M$ () $$$\vee$- . $$$gIm\Leftrightarrow{g\geq{m}}$ $$$(G,M,I)$ $$$L(G,M,I)$, $$$\langle{L,\wedge,\vee}\rangle$.

$$$x\in{L}$ $$$\langle{L,\wedge,\vee}\rangle$ $$$\vee$-, $$$x\neq\emptyset$ $$$y,z\in{L}$ $$$y<x$ $$$z<x$ $$$y\vee{z}<x$.

$$$x\in{L}$ $$$\langle{L,\wedge,\vee}\rangle$ $$$\wedge$-, $$$x\neq\textbf{T}$ $$$y,z\in{L}$ $$$x<y$ $$$x<z$ $$$x<y\wedge{z}$.

$$$\wedge$- , , $$$\vee$- , .

( . $$$(L,L,\geq)$)

, .

, 121 , 24 !

, :

1. .
2. $$$\geq$ , ( $$$\vee$- ).
3. ($$$\vee$-) .
4. .

CPython-: 'vkfencoder' vkfencoder.XMLImport 'vkf' vkf.FCA. — : vkf.FCA MariaDB, vkfencoder.XMLImport XML .

2

. C4.5 .

, .

, , , . .

2.1

, . .

$$$E=G\cup{O}$ $$$G$ - $$$O$. $$$[a,b)\subseteq\textbf{R}$ $$$V:G\to\textbf{R}$ $$$G[a,b)=\lbrace{g\in{G}: a\leq{V(g)}<b}\rbrace,$ $$$O[a,b)=\lbrace{g\in{O}: a\leq{V(g)}<b}\rbrace$

$$$E[a,b)=\lbrace{g\in{E}: a\leq{V(g)}<b}\rbrace$.

$$$[a,b)\subseteq\textbf{R}$ $$$V:G\to\textbf{R}$

$$

$${\rm{ent}}[a,b)=-\frac{\vert{G[a,b)}\vert}{\vert{E[a,b)}\vert}\cdot\log_{2}\left(\frac{\vert{G[a,b)}\vert}{\vert{E[a,b)}\vert}\right)-\frac{\vert{O[a,b)}\vert}{\vert{E[a,b)}\vert}\cdot\log_{2}\left(\frac{\vert{O[a,b)}\vert}{\vert{E[a,b)}\vert}\right)$$

$$$a<r<b$ $$$[a,b)\subseteq\textbf{R}$ $$$V:G\to\textbf{R}$

$$

$${\rm{inf}}[a,r,b)=\frac{\vert{E[a,r)}\vert}{\vert{E[a,b)}\vert}\cdot{\rm{ent}}[a,r)+\frac{\vert{E[r,b)}\vert}{\vert{E[a,b)}\vert}\cdot{\rm{ent}}[r,b).$$

— $$$V=r$ .

$$$V:G\to\textbf{R}$ $$$a=\min\{V\}$ $$$v_{0}$, $$$v_{l+1}$ , $$$b=\max\{V\}$. $$$\lbrace{v_{1}<\ldots<v_{l}}\rbrace$ .

2.2

$$$2l$, $$$l$ — . ()

$$

$$\delta_{i}^{V}(g)=1 \Leftrightarrow V(g)\geq{v_{i}} \\ \sigma_{i}^{V}(g)=1 \Leftrightarrow V(g)<v_{i},$$

$$$1\leq{i}\leq{l}$.

$$$\delta_{1}^{V}(g)\ldots\delta_{l}^{V}(g)\sigma_{1}^{V}(g)\ldots\sigma_{l}^{V}(g)$ $$$V$ $$$g\in{E}$.

, — .

$$$\delta_{1}^{(1)}\ldots\delta_{l}^{(1)}\sigma_{1}^{(1)}\ldots\sigma_{l}^{(1)}$ $$$v_{i}\leq{V(A_{1})}<v_{j}$ $$$\delta_{1}^{(2)}\ldots\delta_{l}^{(2)}\sigma_{1}^{(2)}\ldots\sigma_{l}^{(2)}$ $$$v_{n}\leq{V(A_{2})}<v_{m}$.

$$

$$(\delta_{1}^{(1)}\cdot\delta_{1}^{(2)})\ldots(\delta_{l}^{(1)}\cdot\delta_{l}^{(2)})(\sigma_{1}^{(1)}\cdot\sigma_{1}^{(2)})\ldots(\sigma_{l}^{(1)}\cdot\sigma_{l}^{(2)})$$

$$$\min\lbrace{v_{i},v_{n}}\rbrace\leq{V((A_{1}\cup{A_{2}})'')}<\max\lbrace{v_{j},v_{m}}\rbrace$.

, $$$0\ldots00\ldots0$ $$$\min\{V\}\leq{V((A_{1}\cup{A_{2}})'')}\leq\max\{V\}$.

2.3

. ( 1). . , .

$$$p_{i_{1}}\vee\ldots\vee{p_{i_{k}}}$ $$$p_{i_{1}}+\ldots+{p_{i_{k}}}>\sigma$ $$$0<\sigma<1$.

,

— $$$c:$R$$$^{d}\to\lbrace{0,1}\rbrace$, $$$\textbf{R}^{d}$ — ( $$$d$ ) $$$\lbrace{0,1}\rbrace$ — .

, $$$\langle{\vec{X},K}\rangle\in\text{R}^{d}\times\lbrace{0,1}\rbrace$,

$$

$$p_{\vec{X},K}(\vec{x},k)=p_{\vec{X}}(\vec{x})\cdot{p_{K\mid\vec{X}}(k\mid\vec{x})},$$

$$$p_{\vec{X}}(\vec{x})$ — () , a $$$p_{K\mid\vec{X}}(k\mid\vec{x})$ — , .. $$$\vec{x}\in\text{R}^{d}$

$$

$$p_{K\mid\vec{X}}(k\mid\vec{x})=\textbf{P}\lbrace{K=k\mid\vec{X}=\vec{x}}\rbrace.$$

$$$c:\textbf{R}^{d}\to\lbrace{0,1}\rbrace$

$$

$$R(c)=\textbf{P}\left\lbrace{c(\vec{X})\neq{K}}\right\rbrace.$$

$$$b:\textbf{R}^{d}\to\lbrace{0,1}\rbrace$ $$$p_{K\mid\vec{X}}(k\mid\vec{x})$

$$

$$b(\vec{x})=1 \Leftrightarrow p_{K\mid\vec{X}}(1\mid\vec{x})>\frac{1}{2}>p_{K\mid\vec{X}}(0\mid\vec{x})$$

$$$b$ :

$$

$$\forall{c:\textbf{R}^{d}\to\lbrace{0,1}\rbrace}\left[R(b)=\textbf{P}\lbrace{b(\vec{X})\neq{K}}\rbrace\leq{R(c)}\right]$$

$$

$$p_{K\mid\vec{X}}(1\mid\vec{x})=\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace+p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}= \\ =\frac{1}{1+\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}}=\frac{1}{1+\exp\lbrace{-a(\vec{x})}\rbrace}=\sigma(a(\vec{x})),$$

$$$a(\vec{x})=\log\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}$ $$$\sigma(y)=\frac{1}{1+\exp\lbrace{-y}\rbrace}$ — .

2.4

$$$a(\vec{x})=\log\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}$ $$$\vec{w}^{T}\cdot\varphi(\vec{x})$ $$$\varphi_{i}:\textbf{R}^{d}\to\textbf{R}$ ($$$i=1,\ldots,m$) $$$\vec{w}\in\textbf{R}^{m}$.

$$$\langle\vec{x}_{1},k_{1}\rangle,\dots,\langle\vec{x}_{n},k_{n}\rangle$ $$$t_{j}=2k_{j}-1$.

$$

$$\log\lbrace{p(t_{1},\dots,t_{n}\mid\vec{x}_{1},\ldots,\vec{x}_{n},\vec{w})}\rbrace=-\sum_{j=1}^{n}\log\left[1+\exp\lbrace{-t_{j}\sum_{i=1}^{m}w_{i}\varphi_{i}(\vec{x}_{j})}\rbrace\right].$$

,

$$

$$L(w_{1},\ldots,w_{m})=-\sum_{j=1}^{n}\log\left[1+\exp\lbrace{-t_{j}\sum_{i=1}^{m}w_{i}\varphi_{i}(\vec{x}_{j})}\rbrace\right]\to\max$$

.

-

$$

$$\vec{w}_{t+1}=\vec{w}_{t}-(\nabla_{\vec{w}^{T}}\nabla_{\vec{w}}L(\vec{w}_{t}))^{-1}\cdot\nabla_{\vec{w}}L(\vec{w}_{t}).$$

$$$s_{j}=\frac{1}{1+\exp\lbrace{t_{j}\cdot{(w^{T}\cdot\Phi(x_{j}))}}\rbrace}$

$$

$$\nabla{L(\vec{w})}=-\Phi^{T}{\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}, \nabla\nabla{L(\vec{w})}=\Phi^{T}R\Phi,$$

$$$R={\rm{diag}}(s_{1}(1-s_{1}), s_{2}(1-s_{2}), \ldots, s_{n}(1-s_{n}))$ —

$$$s_{1}(1-s_{1}), s_{2}(1-s_{2}), \ldots, s_{n}(1-s_{n})$ $$${\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}$ — $$$t_{1}s_{1}, t_{2}s_{2}, \ldots, t_{n}s_{n}$.

$$

$$\vec{w}_{t+1}=\vec{w}_{t}+\left(\Phi^{T}R\Phi\right)^{-1}\Phi^{T}{\rm{diag}}(t)\vec{s}= (\Phi^{T}R\Phi)^{-1}\Phi^{T}R\vec{z},$$

$$$\vec{z}=\Phi\vec{w}_{t}+R^{-1}{\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}$ — .

, - -

$$

$$\vec{w}_{t+1}=(\Phi^{T}R\Phi+\lambda\cdot{I})^{-1}\cdot(\Phi^{T}R\vec{z}).$$

"-" : 1 .

, . :

- $$$V_{k}$ ,

$$

$$R^{2}=1-\exp\lbrace{2(L(w_{0},\ldots, w_{k-1})-L(w_{0},\ldots,w_{k-1},w_{k}))/n}\rbrace\geq\sigma$$

$$$V_{k}$ ,

$$

$$1-\frac{L(w_{0},\ldots,w_{k-1},w_{k})}{L(w_{0},\ldots,w_{k-1})}\geq\sigma$$

"-" Wine Quality ( . ). . ( >7), .

( 2.3) "" "". ( ) , 0 1. " " "" .

But the situation with the pair ("pH", "alcohol") was radically different. The "alcohol" weight was positive while the "pH" weight was negative. But with the help of an obvious logical transformation, we got the implication ("pH"$$$\Rightarrow$ "alcohol").

The author would like to thank his colleagues and students for their support and incentives.