カバーの定理

カバーの定理は計算学習理論における定理であり、機械学習アプリケーションにおける非線形カーネル法の利用の主要な理論的動機の一つです。情報理論家トーマス・M・カバーが1965年に提唱した「計数関数定理」にちなんで名付けられました。

定理

次元における同次的に線形分離可能な点集合の個数を、点の数と次元数の計数関数として定義する。定理は であることを述べている。 ${\displaystyle N}$ ${\displaystyle d}$ ${\displaystyle C(N,d)}$ ${\displaystyle N}$ ${\displaystyle d}$ ${\displaystyle C(N,d)=2\sum _{k=0}^{d-1}{\binom {N-1}{k}}}$

必要十分条件として、点が一般的な位置にあることが求められます。簡単に言えば、これは点が可能な限り線形独立（非整列）であるべきであることを意味します。この条件は、ランダムな点集合の場合、「確率1」、つまりほぼ確実に満たされますが、実際のデータでは容易に破られる可能性があります。なぜなら、実際のデータはデータ空間内でより低次元の多様体に沿って構造化されていることが多いからです。

関数は、との関係に応じて 2 つの異なる領域に従います。 ${\displaystyle C(N,d)}$ ${\displaystyle N}$ ${\displaystyle d}$

• の場合、関数は において指数関数的である。これは本質的に、一般的な位置にあり、その数が次元数 + 1 以下の任意のラベル付き点の集合は線形分離可能であることを意味する。専門用語では、線形分類器はの任意の点集合を粉砕すると言われる。この限界量は、線形分類器のVapnik-Chervonenkis次元とも呼ばれる。${\displaystyle N\leq d+1}$ ${\displaystyle N}$ ${\displaystyle N\leq d+1}$

• の場合、計数関数は指数関数よりも小さい値で増加し始めます。これは、サンプルサイズが固定されている場合、次元が大きいほど、ラベル付き点のランダムな集合が線形分離可能である可能性が高くなることを意味します。逆に、次元が固定されている場合、サンプルサイズが大きいほど、線形分離可能なランダムな点の集合の数は少なくなります。言い換えれば、線形分離可能なサンプルを見つける確率は とともに減少します。${\displaystyle N>d+1}$ ${\displaystyle N}$ ${\displaystyle d}$ ${\displaystyle N}$

定理の帰結として、線形に分離できないトレーニング データ セットが与えられた場合、何らかの非線形変換を介して高次元空間に投影することで、高い確率で線形に分離可能なトレーニング セットに変換できる、つまり次のようになります。

複雑なパターン分類問題を高次元空間に非線形に投影すると、その空間が密集していない限り、低次元空間の場合よりも線形に分離できる可能性が高くなります。

証拠

再帰的関係 を用いた帰納法 を固定した状態で、の増加によって点の集合が分離不可能から分離可能へと変化することを示すために、決定論的な写像を用いることができる。点があるとする。それらを次元実空間の単体の頂点上に持ち上げる。サンプルを2つの集合に分割するすべての分割は線形セパレータによって分離可能であるため、この性質は成り立つ。$${\displaystyle C(N+1,d)=C(N,d)+C(N,d-1).}$$ ${\displaystyle N}$ ${\displaystyle d}$ ${\displaystyle N}$ ${\displaystyle N-1}$

左の図は、2次元実空間における100個の点を示しており、円領域の内側か外側かによってラベルが付けられています。これらのラベル付き点は線形分離可能ではありませんが、カーネルトリックを用いて3次元空間に持ち上げると、線形分離可能になります。この場合や他の多くのケースでは、説明で想定されているように点を99次元空間に持ち上げる必要はないことに注意してください。

その他の定理

1965 年の論文には複数の定理が含まれています。

定理6: が-空間の -一般位置にあるとします。この場合、 は、すべての -曲面のクラスに対するの二分法に関して曖昧です。 ${\textstyle X\cup \{y\}=\left\{x_{1},x_{2},\cdots ,x_{N},y\right\}}$ ${\textstyle \phi }$ ${\textstyle d}$ ${\textstyle \phi =\left(\phi _{1},\phi _{2},\cdots ,\phi _{d}\right)}$ ${\textstyle y}$ ${\textstyle C(N,d-1)}$ ${\textstyle X}$ ${\textstyle \phi }$

系:の - 分離可能な二分法のそれぞれが等しい確率を持つ場合、のランダムな - 分離可能な二分法に関してが曖昧である確率はです。 ${\textstyle \phi }$ ${\textstyle X}$ ${\textstyle A(N,d)}$ ${\textstyle y}$ ${\textstyle \phi }$ ${\textstyle X}$ ${\displaystyle {\frac {C(N,d-1)}{C(N,d)}}}$

の場合、 の極限でこの確率は に収束します。 ${\displaystyle N/d\to \beta }$ ${\displaystyle N\to \infty }$ ${\displaystyle \lim _{N}A(N,d)={\begin{cases}1,&0\leq \beta \leq 2\\{\frac {1}{\beta -1}},&\beta \geq 2\end{cases}}}$

これは、単一のパーセプトロンユニットの記憶容量の上限として解釈できます。 はパーセプトロンへの入力重みの数です。この式は、 が大きい限界において、パーセプトロンはほぼ確実に2値ラベルまで記憶できますが、それ以上のラベルはほぼ確実に記憶できないことを示しています。( MacKay 2003 , p. 490) ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle 2d}$

参照

• サポートベクターマシン
• カーネル法

参考文献

• ヘイキン、サイモン（2009年）『ニューラルネットワークと学習機械』（第3版）アッパーサドルリバー、ニュージャージー州：ピアソン・エデュケーション社、pp.  232– 236、ISBN 978-0-13-147139-9。
• Cover, TM (1965). 「線形不等式システムの幾何学的および統計的性質とパターン認識への応用」(PDF) . IEEE Transactions on Electronic Computers . EC-14 (3): 326– 334. doi : 10.1109/pgec.1965.264137 . S2CID  18251470.オリジナル(PDF)から2019年12月20日にアーカイブ。
• Mehrotra, K.; Mohan, CK; Ranka, S. (1997). 『人工ニューラルネットワークの要素』（第2版）. MIT Press. ISBN 0-262-13328-8。（セクション3.5）
• MacKay, David JC (2003). 「40. 単一ニューロンの容量」.情報理論、推論、学習アルゴリズム. ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-0-521-64298-9。