Mathématiques d'apprentissage automatique basées sur un treillis

Il s'agit du troisième article d'une série d'articles (liens vers les premier et deuxième articles) décrivant un système d'apprentissage automatique basé sur la théorie des treillis, intitulé "VKF-system". Il utilise une approche structurelle (théorie du réseau) pour la présentation d'exemples d'apprentissage et de leurs fragments, considérés comme les causes de la propriété cible. Le système calcule ces fragments comme des similitudes entre certains sous-ensembles des exemples d'apprentissage. Il existe une théorie algébrique de ces représentations appelée Analyse de Concept Formelle (AFP).

Cependant, le système décrit utilise des algorithmes probabilistes pour éliminer les inconvénients de l'approche illimitée. Détails ci-dessous ...

introduction

Nous commencerons par démontrer notre approche appliquée à un problème scolaire.

, .

, : ( ) .

, , ( ).

— .

, :

" " (A),

" " (B),

" " (C),

" " (D),

" " (E).

.

( ) ( ) .

$$

$$\langle\{,\}, \{E\}\rangle,$$

( , ), — .

$$$\{E\}$ $$$\{A,C,E\}$, , .. . -. ( ), , .

:

$$

$$\langle\{,\}, \{D\}\rangle,$$

, .

.., .., .. (.). . 2: , M.: URSS, 2020, 238 . ISBN 978-5-382-01977-2

, " -", $$$\{D\}$ $$$\{A,C,D,E\}$ ().

1.

- . , " - ". . ( ) , .

(= ) — $$$(G,M,I)$, $$$G$ $$$M$ — , $$$I \subseteq G \times M$. $$$G$ $$$M$ , . , $$$gIm$ $$$\langle g,m\rangle \in I$, , $$$g$ $$$m$.

$$$A\subseteq G$ $$$B\subseteq M$

$$

$$A' = \{ m \in M | \forall g \in A (gIm) \}, \\ B' = \{ g \in G | \forall m \in B (gIm) \};$$

$$$A'$ — , $$$A$, $$$B'$ — , $$$B$. $$$(\cdot)': 2^G \rightarrow 2^M$ $$$(\cdot)':2^M\rightarrow 2^G$ (= ) $$$(G,M,I)$.

(= ) $$$(G,M,I)$ $$$\langle A,B \rangle$, $$$A\subseteq G$, $$$B\subseteq M$, $$$A'=B$ $$$B'=A$. $$$A$ $$$\langle A,B \rangle$ (=) , $$$B$ (=). $$$(G,M,I)$ $$$L(G,M,I)$.

, $$$L(G,M,I)$

$$

$$\langle A_{1},B_{1}\rangle\vee\langle A_{2},B_{2}\rangle= \langle(A_{1}\cup A_{2})'',B_{1}\cap B_{2}\rangle, \\ \langle A_{1},B_{1}\rangle\wedge\langle A_{2},B_{2}\rangle= \langle A_{1}\cap A_{2},(B_{1}\cup B_{2})''\rangle.$$

: $$$\langle A,B \rangle\in L(G,M,I)$, $$$g\in G$ $$$m\in M$

$$

$$CbO(\langle A,B\rangle,g) = \langle(A\cup\{g\})'',B\cap\{g\}'\rangle,\\ CbO(\langle A,B\rangle,m) = \langle A\cap\{m\}',(B\cup\{m\})''\rangle.$$

CbO, "--" (Close-by-One (CbO)), $$$L(G,M,I)$.

CbO

$$$(G,M,I)$ — , $$$\langle A_{1},B_{1}\rangle, \langle A_{2},B_{2}\rangle\in L(G,M,I)$, $$$g\in G$ $$$m\in M$.

$$

$$\langle A_{1},B_{1}\rangle\leq \langle A_{2},B_{2}\rangle\Rightarrow CbO(\langle A_{1},B_{1}\rangle,g)\leq CbO(\langle A_{2},B_{2}\rangle,g), \\ \langle A_{1},B_{1}\rangle\leq\langle A_{2},B_{2}\rangle\Rightarrow CbO(\langle A_{1},B_{1}\rangle,g)\leq CbO(\langle A_{2},B_{2}\rangle,g).$$

2.

, :

1. ( ) .

   
   
   

2. (NP-).

   
   
   

3. .

   
   
   

4. '' , .

   
   
   

1 , ( ):

, $$$\langle G\setminus \{g_{i_{1}},\ldots,g_{i_{k}}\},\{m_{i_{1}},\ldots,m_{i_{k}}\}\rangle$ . $$$2^n$ .

, , $$$n=32$, 128 , $$$2^n$ $$$2^{37}$ , .. 16 !

2 . .. (- ).

3 4 . , "" -, . — , , "" -

$$

$$1-e^{-a}-a\cdot{e^{-a}}\cdot\left[1-e^{-c\cdot\sqrt{a}}\right],$$

( ... ) $$$p=\sqrt{a/n}\to 0$, - $$$m=c\cdot\sqrt{n}\to\infty$, $$$n\to\infty$.

, $$$1-e^{-a}-a\cdot{e^{-a}}$ , , $$$a$ >1.

.

3.

- . ( - ).

, , , .

(, , , ). .

, , (-).

input:  (G,M,I),   CbO( , )
result:   <A,B>
X=G U M; 
A = M'; B = M;  
C = G; D = G';
while (A!=C || B!= D) {
           x  X;
        <A,B> = CbO(<A,B>,x);
        <C,D> = CbO(<C,D>,x);
}

. , ( )

$$

$$\frac{(n+k)^2}{2k\cdot n}=2+\frac{(n-k)^2}{2k\cdot n} \geq 2$$

, $$$n$ — , $$$k$ — .

, .. .

4. -

, , .

$$$(G,M,I)$. $$$O$ - ( -).

$$$T$ .

, $$$\langle A,B\rangle\in L(G,M,I)$. - VKF-hypothesis $$$\langle A,B\rangle$, - $$$o\in O$, $$$B\subseteq \{o\}'$.

input:  N -  
result:   S   
while (i<N) {
           <A,B>  (G,M,I);
        hasObstacle = false;
        for (o in O) {
            if (B   {o}') hasObstacle = true;
        }
        if (hasObstacle == false) {
                S = S U {<A,B>};
                i = i+1;
        }
}

$$$B\subseteq\{o\}'$ $$$B$ $$$\langle{A,B}\rangle$ ( ) - $$$o$.

, -.

(, "--") , - .

.

input:  T       
input:   S   -
for (x in T) {
        target(x) = false;
        for (<A,B> in S) {
            if (B is a part of {x}') target(x) = true;
        }
}

, - .

$$$x$ $$$\varepsilon$-, - $$$\langle A,B\rangle$ $$$B\subseteq\{x\}'$ $$$\varepsilon$.

$$$N$ , .

$$$n=\left|{M}\right|$, $$$\varepsilon>0$ $$$1>\delta>0$ $$$S$ -

$$

$$N\geq{\frac{2\cdot(n+1)-2\cdot\log_{2}{\delta} }{\varepsilon}}$$

$$$>{1-\delta}$ , $$$\varepsilon$- $x$ - $$$\langle A,B\rangle\in{S}$, .. $$$B\subseteq\{x\}'$.

. .. . .. .

, . "-" . .. .

.

. , , , .

.