格子ベースの機械学習数学

これは、「VKF-system」というタイトルの、ラティス理論に基づく機械学習システムを説明する一連の論文（1番目と2番目の論文へのリンク）の3番目の記事です。ターゲットプロパティの原因と見なされるトレーニング例とそのフラグメントのプレゼンテーションに、構造（格子理論）アプローチを使用します。システムは、これらのフラグメントをトレーニング例の一部のサブセット間の類似度として計算します。このような表現には、Formal Concept Analysis（AFP）と呼ばれる代数理論があります。

ただし、説明されているシステムは、確率的アルゴリズムを使用して、無制限のアプローチの欠点を排除します。以下の詳細...

前書き

まず、学校の問題に適用されるアプローチを説明します。

, .

, : ( ) .

, , ( ).

— .

, :

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

. .. . .. .

この投稿では、格子理論に基づく機械学習システムの主な数学的特性について説明します。著者は、彼の教師教授に敬意を表して「VKFシステム」と名付けました。VK。フィナ。

シリーズの最後の記事では、ここで説明する学習マシンを適用するためのさまざまなタイプの機能を持つオブジェクトの表現について説明します。

ディスクリート機能でも、AFPテクニックが必要になります。連続フィーチャには、ロジスティック回帰、範囲をサブインターバルに分割するエントロピー原理、および類似性が計算されるインターバルの凸包を生成する表現が必要です。

著者はこの機会に彼の同僚と学生に彼らのサポートとインセンティブに感謝することを嬉しく思います。