サポートベクターマシン(Support Vector Machine: SVM)は、1960年代にウラジーミル・ヴァプニクとAlexey Ya. Chervonenkisによって線形分類器として提案され、1990年代にBernhard E. Boser、Isabelle M. Guyon、ヴァプニクによって非線形分類にも拡張された機械学習アルゴリズムです。現在では、その高い分類精度と汎化性能から、データ分析や機械学習の分野で広く活用されています。
SVMの最大の特徴は「マージン最大化」という考え方にあります。異なるクラスのデータ点を分ける決定境界（超平面）を、両クラスのデータ点からできるだけ離れた位置に設定することで、未知のデータに対しても高い分類性能を発揮します。この決定境界に最も近いデータ点をサポートベクトルと呼び、SVMの名前の由来となっています。
SVMの核心となる「マージン最大化」は、数学的に非常に美しい概念です。2クラスのデータを分類する場合、無数の決定境界が考えられますが、SVMはその中でも両クラスのデータ点から最も遠い位置に境界を設定します。
具体的には、決定境界を表す超平面は以下の式で表されます。
w・x + b = 0
ここで、wは重みベクトル、bはバイアス項、xはデータ点を表します。この超平面からデータ点までの距離（マージン）を最大化するように、wとbを最適化します。
この最適化問題は、ラグランジュの未定乗数法とKKT条件を用いて、凸二次計画問題として定式化されます。
最小化：||w||²/2
制約条件：yi(w・xi + b) ≥ 1 (すべてのデータ点i)
ここで、yiはデータ点xiのクラスラベル（+1または-1）を表します。
この最適化問題を解くことで、マージンを最大化する決定境界が得られます。特に重要なのは、最終的な決定境界がサポートベクトルと呼ばれる一部のデータ点のみによって決定されるという点です。これにより、計算効率が向上し、過学習を防ぐ効果もあります。
実世界のデータは、単純な直線や平面では分離できないことが多いです。SVMでは「カーネル法」を用いることで、非線形の分類問題にも対応できます。
カーネル法の基本的なアイデアは、元の低次元空間のデータを高次元空間に写像し、その高次元空間内で線形分離を行うというものです。例えば、2次元平面上で円形に分布するデータは線形分離できませんが、3次元空間に写像すると線形分離可能になることがあります。
しかし、高次元空間への明示的な写像は計算コストが高くなります。そこで「カーネルトリック」と呼ばれる手法を用います。カーネルトリックでは、高次元空間での内積計算を元の低次元空間で直接計算できるカーネル関数K(x, y)を使用します。
K(x, y) = φ(x)・φ(y)
ここで、φ(x)は高次元空間への写像関数です。
代表的なカーネル関数には以下のようなものがあります。
カーネル関数の選択は問題の性質に依存し、適切なカーネルを選ぶことでSVMの性能が大きく向上します。特にRBFカーネルは汎用性が高く、多くの問題に適用できることが知られています。
実際のデータには、ノイズやはずれ値が含まれることが多く、完全な線形分離が不可能な場合があります。そのような状況に対応するため、SVMでは「ソフトマージン」という概念が導入されています。
ソフトマージンSVMでは、一部のデータ点が決定境界を越えることを許容します。ただし、境界を越えるデータ点にはペナルティを課し、できるだけ多くのデータ点を正しく分類することを目指します。
数学的には、以下のような最適化問題として定式化されます。
最小化：||w||²/2 + C∑ξi
制約条件：yi(w・xi + b) ≥ 1 - ξi, ξi ≥ 0 (すべてのデータ点i)
ここで、ξiはスラック変数と呼ばれ、データ点xiがマージンをどれだけ侵害しているかを表します。Cはハイパーパラメータで、マージン最大化と誤分類の許容度のバランスを調整します。
適切なC値の選択は、交差検証などを用いて行うことが一般的です。ソフトマージンの導入により、SVMはノイズに対してより頑健になり、汎化性能が向上します。
SVMの学習は、前述の最適化問題を解くことで行われますが、大規模なデータセットに対しては計算コストが高くなります。そこで、効率的に最適化を行うためのアルゴリズムが開発されています。
代表的なアルゴリズムとして、SMO（Sequential Minimal Optimization）があります。SMOは、大きな最適化問題を小さなサブ問題に分解し、逐次的に解くことで効率的に最適解を求めます。
SMOの基本的なアイデアは以下の通りです。
この方法により、メモリ使用量を抑えつつ、大規模なデータセットに対しても効率的に学習を行うことができます。
また、SVMの学習における計算量は、サンプル数nに対してO(n²)〜O(n³)となりますが、スパースカーネルを用いたり、近似アルゴリズムを適用したりすることで、さらに効率化することも可能です。
SVMは基本的には2クラス分類のアルゴリズムですが、多クラス分類問題にも拡張することができます。代表的な方法として、以下の2つのアプローチがあります。
各クラスとそれ以外のクラスを分ける二項分類器をk個（クラス数）構築し、新しいデータに対して最も高いスコアを出した分類器のクラスに分類します。
可能なすべてのクラスペアについて二項分類器を構築し（k(k-1)/2個）、新しいデータに対して最も多く「勝った」クラスに分類します。
OvO法はOvR法と比較して、各分類器が扱うデータ量が少なくなるため学習が速い傾向がありますが、分類器の数が多くなるというトレードオフがあります。
多クラスSVMの数学的定式化も研究されており、Crammer-Singerの多クラスSVMなど、直接多クラス分類を行うアプローチも提案されています。
これらの拡張により、SVMは画像認識、テキスト分類、生体情報解析など、様々な多クラス分類問題に応用されています。
SVMの美しさは、その幾何学的解釈にもあります。マージン最大化は、幾何学的には「2つのクラスの凸包（convex hull）の間の最短距離を最大化する」問題と等価です。
また、SVMの最適化問題は、主問題（primal problem）と双対問題（dual problem）という2つの視点から捉えることができます。
主問題。
最小化：||w||²/2 + C∑ξi
制約条件：yi(w・xi + b) ≥ 1 - ξi, ξi ≥ 0
双対問題。
最大化：∑αi - (1/2)∑∑αiαjyiyjK(xi, xj)
制約条件：0 ≤ αi ≤ C, ∑αiyi = 0
ここで、αiはラグランジュ乗数です。双対問題を解くことで、サポートベクトル（αi > 0となるデータ点）を特定し、決定境界を求めることができます。
双対形式の利点は、カーネル関数を直接適用できることと、最適化の計算効率が良いことです。特に、サポートベクトルの数がデータ点の総数よりも少ない場合、双対問題を解く方が効率的です。
この双対性の理解は、SVMの理論的背景を深く理解するだけでなく、効率的な実装にも役立ちます。
SVMは様々な分野で応用されています。
SVMの強みは以下の点にあります。
一方で、以下のような限界もあります。
これらの限界に対処するため、確率的出力を提供するPlatt Scalingや、計算効率を向上させるLinear SVMなどの拡張が提案されています。また、SVMの考え方を回帰問題に適用したSVR（Support Vector Regression）も広く使われています。
SVMの実践的ガイドライン（パラメータ選択など）
SVMは、その数学的な美しさと実用性から、機械学習の基礎を学ぶ上で重要なアルゴリズムです。特に、少量のデータでも高い性能を発揮できる点や、過学習を防ぐ理論的な保証がある点は、実践的な応用においても大きな利点となっています。
数学的な観点からSVMを理解することで、機械学習の他のアルゴリズムへの理解も深まり、より効果的なデータ分析が可能になるでしょう。