この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。
概要
こんにちは、yoshimです。当エントリは「Machine Learning Advent Calendar 2017」の13日目のエントリです。
今回は教師あり学習の１手法である「サポートベクターマシーン（support vector machine,SVM）」をご紹介します。
目次
1.SVMとは
「SVM」は「分類」、「回帰」の両方に利用可能な教師あり学習です。
ロジスティック回帰等のモデルと比較すると高い識別性能が得られるというメリットがある一方、データの前処理やパラメーターの調整、結果の解釈が難しいというデメリットもあります。しかしながら、SVMは「識別能力が高く、非線形識別をするための実装が容易」なことを背景として人気の高いアルゴリズムになります。
また、SVMについてここでの説明だけでは不足（特に数式について）な方には、ベタではございますが下記の書籍がオススメです。
はじめてのパターン認識
2.処理の概要
処理の概要については、下記の弊社のブログの「SVMとは」を参照していただいて、今回のエントリーではその中身についてもう少し細かく説明していこうと思います。
3.特徴
以下に、SVMの特徴について列挙します。
a.教師あり学習であり、「分類」、「回帰」のいずれにも利用可能。
SVMは使い方によって、「分類」、「回帰」のいずれにも応用可能です。また、Pythonで実装する場合は、コードの書き方もほぼほぼ同じものになります。
b.データの前処理とパラメーターの調整が難しい。
前処理としての「特徴量のスケーリング」や、「誤分類をどれだけ許容するか」といったパラメータの指定が必要となります。 さらに、パラメータの指定のために交差検証法等を実施する必要があります。
c.「マージン」という「距離のような概念」の最大化を目的としている。
（識別超平面と、その超平面に最も近い点とのマージンが最大になるような超平面を選ぶこと） なぜマージンを最大化するのかというと、「汎化誤差の減少」のためです。 （マージンが小さいと過学習に陥りがちです）
d.平均や分散を使わないので新しいデータが入ってきても全体の再計算は不要。
これはその通りの意味ですね。
e.線形分離が不可能な場合は、「非線形変換を施したうえでより高次元特徴空間に写像」することで対応できる。
ちょっとわかりづらいですが、まず最初にSVMを利用する際は、「線形」で分割しようとすることが多いかと思います。しかしながら、現実のデータが「線形」で綺麗に分割しきれない場合があるのも事実です。そういった場合は特徴量を増やしたり、非線形の特徴量を利用することによってデータを分割する手法を採用することがあります。これは、「カーネルトリック法」と呼ばれる手法を使うことが多いそうです。
4.マージンの計算方法についてざっくり説明
SVMでは「識別超平面と一番近くのデータ点とのマージン」を最大化することを目的としているので、マージンの求め方を理解しておくことは重要です。また、クラス分類をする際は「誤分類」が存在するものですが、「誤分類」に対してのペナルティをどの程度にするか、ということを指定することも必要です。（識別超平面関数の複雑さ、に対するペナルティも指定するアルゴリズムもありますが、今回はこちらについては考慮しません）今回は色々と前提条件を置いた上で、マージンの計算方法についてざっくり説明していきます。 (下記からちょっと読むのが面倒臭くなると思いますので、手っ取り早くマージンについて把握したい方は、(4-3)式と太字の部分を呼んでください。)
・前提条件
(1)データを2つのクラス（クラス1,-1の２クラス）に分類するSVM、におけるマージンの計算方法について説明する
(2)クラス1に存在する各データ点を正例と呼び、xPOSと表現する。また、クラス-1に存在する各データ点を負例と呼び、xNEGと表現する。
(3)識別関数の係数ベクトルとバイアス項をマージンで正規化したものを、それぞれw,w0と表現する。
(4）wTは識別関数の係数ベクトルを転置したものであり、行列計算の都合上転置しているだけであり、中身の数値には影響がない。
(5)決定境界に沿った正例の超平面を[latex]w0 + wT * xPOS = 1[/latex]負例の超平面を[latex]w0 + wT * xNEG = -1[/latex]と表現する。
(6)識別関数の係数ベクトルwの長さを、[latex]\sqrt{（||w||^2）}[/latex]と定義する。
(7)サンプルが全て正しく分類されている。つまり、各データ点をxiとした時、|wT * xi + w0| >= 1が常に成り立つ。
上記の前提条件下で、最適化すべきマージンは下記の通りである。これは正例の超平面-負例の超平面間の距離と判断することができる。 [latex] (最適化すべきマージン) = （正例の超平面-識別超平面間の距離） + (負例の超平面-識別超平面間の距離) [/latex] [latex] (右辺) = \frac{{（w0 + wT * xPOS） - (w0 + wT * xNEG)}}{||w||} [/latex] [latex] (右辺) = \frac{2}{||w||} .....(4-1) [/latex]
SVMでは「マージン最大化」を目指すことになるので、2 / ||w||を最大化することを目指す。これは||w||を最小化することと同義である。また、計算の都合上||w||ではなく、1/2||w||^2を最小化することを目指すことが多い。（この後微分することになるので、こちらの方が計算の都合がいい。計算の都合上形式を変えただけなので、本質的には変わらない） というわけで、求めるマージンは、前提条件を全て満たした状態で、下記の式（以降、評価関数と表記）を最小化したものになる。
[latex] （評価関数） = 1/2||w||^2 .....(4-2) [/latex]
しかし現実的にこれで実装しようとすると、前提条件（7）があまりにも非現実的である。なので、「誤分類を許容しつつも、誤分類に対してはペナルティを科す」という考え方の方が現実的に良いモデルになるであろう。このような考え方に対応するために、(4-2)の評価関数に「スラック変数（ε）」という変数を導入する。スラック変数は誤分類時やマージン境界を越えた場合に正の値をとる変数である。「スラック変数（ε）」を導入した後の評価関数は下記の通りである。
[latex] （評価関数) = 1/2||w||^2 + （全てのデータ点におけるスラック変数の和） [/latex]
[latex] (右辺) = 1/2||w||^2 + C\sum_{i=1}^{N} ε(i) .....(4-3) [/latex]
ここで出てくる「C」という変数ですが、これを制御することで誤分類に対するペナルティをコントロールできます。（4-3）式の右辺第一項が「識別関数の係数ベクトルの大きさ（モデルの複雑さ）」、第二項が「誤分類に対するペナルティの強さ」を意味しています。SVMではこの評価関数を最小化することを目的とするので、この評価関数では「モデルの複雑さ」と「誤分類」のトレードオフを調整することができています。
以上から、(4-3)の評価関数を最小化した際のwを用いることでマージンを求めることができます。 （今回ご紹介したアルゴリズムはは「c-SVM」と呼ばれるアルゴリズムですが、他にも「係数ベクトルの複雑さ」も評価関数の計算要素に含めた「v-SVM」アルゴリズムも有名です）
5.マージンの計算方法についてもう少し説明
マージンの計算方法について、もう少しだけ説明します。
A.係数ベクトルの長さ（ノルム）の最小化
SVMではマージン計算の時点で、「識別関数の係数ベクトルが大きくなりすぎないような制約」が入っています。 係数ベクトルが大きくなりすぎると、「モデルが複雑」になりすぎてしまい汎化性能が減少する傾向があるので、係数ベクトルの長さを小さくする過程が必要なのです。
B.スラック変数 スラック変数は0以上の値をとる変数ですが、もう少し具体的にどのような値になるのかというと下記の通りです。
マージン内で正しく分類できている場合: ε = 0 正しく分類できているが、マージン境界を越える場合: 0 < ε <= 1 誤分類の場合: 1 < ε
C.最適化するうえでの制約の設定
スラック変数の導入に際して、「誤分類に対するペナルティ」をどれくらいの強さにするか、という部分について人間が指定する必要があります。具体的には、式（4-3）におけるCを指定する必要があります。 では、このCに対してどのような値を指定すればいいのかという点についてですが、に交差検証法という手法を使い、パラメータを変えつつ何回かSVMを実行し、どのパラメータがいいかを確認する、という手法がよく使われるようです。 このパラメーターには「C」という文字が使われることが多いので、この時のSVMは「CーSVM」と呼ばれています。（つまり、今回ご紹介したのは、SVMの中の「C-SVM」というアルゴリズムでした）
6.まとめ
長くなってしまいましたが、これで「サポートベクターマシーン（SVM）」についての解説を終わります。 SVMは、アルゴリズムの理解やパラメータの調整が大変ですが、非線形分類問題に対応するための実装が容易な点が特徴的です。 今回ご紹介したSVMは解がデータの線型結合で表される識別超平面になりましたが、識別境界が線形関数では表せない場合もあります。そういった場合は、「非線形変換でより高次元特徴空間へ写像」することで線形分離することができる可能性があります。この時に、SVMに「カーネル」というものを利用したアルゴリズムを採用することになるのですが、このアルゴリズムについては後日エントリーが上がりますので、もしよろしかったらご覧ください。
明日はSVMを実際にPythonで実行してみようと思います。
14
