カバーの定理

カバーの定理は、計算学習理論における定理であり、機械学習アプリケーションで非線形カーネル法を使用する主な理論的動機の 1 つです。情報理論家Thomas M. Coverが 1965 年にこれを「計数関数定理」と呼んで述べたことにちなんで名付けられました。

この定理は、次元における同次的に線形分離可能な点の集合の数を、点の数と次元数の明示的な計数関数として表現します。 ${\displaystyle N}$${\displaystyle D}$${\displaystyle C(N,D)}$${\displaystyle N}$${\displaystyle D}$

必要かつ十分な条件として、点が一般的な位置にあることが必要です。簡単に言えば、これは点が可能な限り線形独立 (非整列) である必要があることを意味します。この条件は、ランダムな点集合に対しては「確率 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}$

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

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

カバーの計数関数定理の証明は、再帰関係から得られる。

${\displaystyle C(N+1,D)=C(N,D)+C(N,D-1).}$

を固定した場合、 を増やすと点の集合が分離不可能から分離可能になることを示すために、決定論的マッピングを使用できます。点があるとします。それらを 次元の実空間の単体の頂点に持ち上げます。サンプルを 2 つの集合に分割するすべての分割は線形セパレータによって分離可能であるため、この特性が成り立ちます。 ${\displaystyle N}$${\displaystyle D}$${\displaystyle N}$${\displaystyle N-1}$

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

• ヘイキン、サイモン (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。2019-12-20に オリジナル(PDF)からアーカイブ。
• Mehrotra, K.; Mohan, CK; Ranka, S. (1997). 人工ニューラルネットワークの要素 (第 2 版). MIT プレス. ISBN 0-262-13328-8。（セクション3.5）