Matematika Pembelajaran Mesin Berbasis Kisi

Ini adalah artikel ketiga dalam serangkaian makalah (tautan ke makalah pertama dan kedua ) yang menggambarkan sistem pembelajaran mesin berdasarkan teori kisi, yang berjudul "VKF-system". Ini menggunakan pendekatan struktural (teori-kisi) untuk presentasi contoh pelatihan dan fragmennya, yang dianggap sebagai penyebab properti target. Sistem menghitung fragmen-fragmen ini sebagai kesamaan antara beberapa himpunan bagian dari contoh pelatihan. Ada teori aljabar dari representasi seperti yang disebut Analisis Konsep Formal (AFP).

Namun, sistem yang dijelaskan menggunakan algoritma probabilistik untuk menghilangkan kelemahan dari pendekatan tanpa batas. Detail di bawah ...

pengantar

Kami akan mulai dengan menunjukkan pendekatan kami sebagaimana diterapkan pada masalah sekolah.

, .

, : ( ) .

, , ( ).

— .

, :

" " (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\}'$.

. .. . .. .

, . "-" . .. .

.

. , , , .

.