線形分離可能性

ユークリッド幾何学において、線形分離可能性は 2 つの点の集合の特性です。これは、2 次元 (ユークリッド平面) で、一方の点の集合を青色、もう一方の点の集合を赤色と考えることによって、最も簡単に視覚化できます。平面内に少なくとも 1 本の線が存在し、その線の片側にすべての青色の点があり、反対側にすべての赤色の点がある場合、これらの 2 つの集合は線形分離可能です。この概念は、線を超平面に置き換えると、高次元のユークリッド空間にすぐに一般化されます。

一対の集合が線形分離可能かどうかを判定し、分離可能な場合は分離超平面を見つけるという問題は、いくつかの分野で発生します。統計学と機械学習では、特定の種類のデータを分類することが問題であり、この概念に基づいた優れたアルゴリズムが存在します。

と をn次元ユークリッド空間の 2 つの点の集合とします。このとき、すべての点がを満たし、すべての点がを満たすようなn + 1 個の実数が存在する場合、と は線形分離可能です。ここで は の- 番目の要素です。 ${\displaystyle X_{0}}$${\displaystyle X_{1}}$${\displaystyle X_{0}}$${\displaystyle X_{1}}$${\displaystyle w_{1},w_{2},...,w_{n},k}$${\displaystyle x\in X_{0}}$${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>k}$${\displaystyle x\in X_{1}}$${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle x}$

同様に、2つの集合は、それぞれの凸包が互いに素である（口語的に言えば、重なり合わない）ときに、まさに線形分離可能である。^[1]

単純な 2D では、線形変換を受ける点の集合が直線に収束し、その直線上に、一方の点の集合が収まる値 k と、もう一方の点の集合が収まる値 k が存在することも考えられます。

2 つのクラス (「+」と「-」) 内の3 つの非共線点は、2 次元では常に線形に分離可能です。これは、次の図の 3 つの例で示されています (すべて「+」の場合は示されていませんが、すべて「-」の場合と似ています)。

ただし、4 点のセットすべてが 2 次元で線形に分離できるわけではありません (同一直線上にある 3 点も含みます)。次の例では2 本の直線が必要なので、線形に分離できません。

同一直線上にあり、「+ ⋅⋅⋅ — ⋅⋅⋅ +」という形式の 3 つの点も線形に分離できないことに注意してください。

K次元でN個の点を（一般的な位置で）線形に分離する方法の数を とすると、 ^[2] Kが大きい場合、のときは 1 に非常に近くなりますが、 のときは 0 に非常に近くなります。つまり、 のときは 1 つのパーセプトロンユニットが N 個の点のバイナリ ラベルのランダム割り当てをほぼ確実に記憶できますが、 のときはほぼ確実に記憶できません。 ${\displaystyle T(N,K)}$$${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}}\right)&K<N\end{array}}\right.}$$${\displaystyle T(N,K)/2^{N}}$${\displaystyle N\leq 2K}$${\displaystyle N>2K}$${\displaystyle N\leq 2K}$${\displaystyle N>2K}$

n変数のブール関数は、 n次元のブール超立方体の各頂点に0または1を割り当てるものと考えることができます。これにより、頂点が 2 つの集合に自然に分割されます。ブール関数は、これらの 2 つの点の集合が線形に分離可能である場合、線形に分離可能であると言われます。異なるブール関数の数は、関数に渡される変数の数nです。 ^[3]${\displaystyle 2^{2^{n}}}$

このような関数は線形閾値論理、またはパーセプトロンとも呼ばれる。古典理論はクヌースが主張するように^[4]に要約されている。^[5]

値はケースまでしか正確に分かっていませんが、大きさの順序はかなり正確に分かっています。上限と下限があります。^[6]${\displaystyle n=9}$${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$${\displaystyle 2^{n^{2}-n\log _{2}nO(n)}}$

選言正規形または連言正規形で与えられたブール関数が線形分離可能かどうかを判断することは共NP完全である。 ^[6]

データの分類は、機械学習における一般的なタスクです。2 つのセットのいずれかに属するいくつかのデータ ポイントが与えられ、新しいデータ ポイントがどちらのセットに含まれるかを決定するモデルを作成するとします。サポート ベクター マシンの場合、データ ポイントはp次元ベクトル ( p 個の数値のリスト) と見なされ、そのようなポイントを ( p  − 1) 次元の超平面で分離できるかどうかを確認します。これは線形分類器と呼ばれます。データを分類 (分離) できる超平面は多数あります。最適な超平面として妥当な選択の 1 つは、2 つのセット間の最大の分離、つまりマージンを表す超平面です。したがって、各側の最も近いデータ ポイントまでの距離が最大になるように超平面を選択します。このような超平面が存在する場合、それは最大マージン超平面と呼ばれ、それが定義する線形分類器は最大マージン分類器と呼ばれます。

より正式には、ある訓練データが与えられた場合、次の形式の n個の点の集合が${\displaystyle {\mathcal {D}}}$

${\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}$

ここで、y _{i は}1 または −1 で、点が属する集合を示します。それぞれはp次元の実数ベクトルです。を持つ点と を持つ点を分ける最大マージン超平面を見つけたいとします。任意の超平面は、次を満たす 点の集合として表すことができます。${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle y_{i}=1}$${\displaystyle y_{i}=-1}$${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,}$

ここで、 はドット積と超平面への法線ベクトル（必ずしも正規化されていない）を表します。 パラメータは、法線ベクトルに沿った原点からの超平面のオフセットを決定します。 ${\displaystyle \cdot}$${\displaystyle {\mathbf {w} }}$${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$${\displaystyle {\mathbf {w} }}$

トレーニング データが線形に分離可能な場合は、データを分離し、その間にポイントがないように 2 つの超平面を選択し、それらの距離を最大化するようにすることができます。

• クラスタリング（統計）
• 超平面分離定理
• キルヒベルガーの定理
• パーセプトロン
• ヴァプニク – チェルボネンキス次元