2013年8月28日（水）
at Gunosy Inc.
サポートベクターマシン (SVM)
- ラージマージン分類機の一種
- ベクトル空間に基づいた機械学習法
- 訓練データ（いくつかの点を外れ値もしくはノイズとして除く）のあらゆる点から最も離れている2つのクラスの間の決定境界を見つける
SVM ...あらゆるデータ点からの距離が最大となる決定面を求める基準を定義
- 最大マージン決定超平面 (Maximum decision hyperplane) ...実線の直線
- 分離面...点線の直線?
- 分離面の マージン (margin) ...決定面から最近データ点に接するまでの距離
- サポートベクター (support vector) ...分離面の位置を定義するデータ（原点からその点までのベクトル）
マージン最大化 ...マージンが最大になるように分類面を決定すること?
- 分類に安全マージンを与える
- 分離面にわずかな誤差があっても分類誤りを引き起こさない
- b ...定数項
- w ...決定超平面法線ベクトル（重みベクトル）
- 超平面に垂直
決定超平面は b と w で定義される。その方程式は
(14.3)
となる（(14.3)式）。超平面が法線ベクトルに垂直なので、超平面上の全ての点 x は
Tw x = -b
を満たす。（これは b の符号を逆転させている?）
訓練点集合 D ={( x_i , y_i )}
- x_i ...点
- y_i ...点 x_i に対応するラベル
線形分類器は次のようになる。
(15.1)
-1という値はあるクラスを示し、1という値は別のクラスを示す。
- 関数的マージン
- 幾何学的マージン
超平面 < w , b >に関する i 番目の例 x_i の 関数的マージン を量
y_i (Tw x + b)
と定義する。
決定面に関するデータ集合の関数的マージンを、 最小の関数的マージンをもつ任意のデータ点の関数的マージンの2倍とする。
この定義には問題があり、 w と b のスケールを変えるだけでいくらでも大きくできる。
=> w のサイズに制約を課す必要がある。
- r ...点から決定境界へのユークリッド距離
- x' ...超平面上で x に最も近い点
点と超平面との最短距離は、平面への垂線であり w と平行である。 この方向の単位ベクトルは w / |w| である。 図15.3の点線は、ベクトル rw / |w| を表す。 このとき
(15.2)
が成り立つ。 さらに、 x' は決定境界にあり wx' + b = 0を満たす。 したがって
(15.3)
となる。
|w| = sqrt(Tw w) (definition of norm)
y_i = 1 / y_i (because y_i = 1 or -1)
なので、これを r について解くと
(15.4)
となる。
分類器の 幾何学的マージン (geometric margin) は、 2つのクラスのサポートベクターを分離する幅の最大値である。 すなわち、 r の最小値の2倍となる。
この定義によれば、 w と b のスケールを変えても、 w の長さで正規化されているので、幾何学的マージンは変化しない。
|w| = 1
と単位ベクトルを選べば、幾何学的マージンと関数的マージンを同じにする。
（関数的マージンは好きなだけスケールできるため、巨大SVMを解くのに都合がいいように） 全てのデータ点の関数的マージンが1以上であり、 少なくとも1つのデータベクトルで1に等しいと仮定する。 すなわち、データの全項目について、
(15.5)
として、この不等式の等式が成り立つサポートベクターが存在すると仮定する。 超平面からの各データ点からの距離は(15.4)式で決まるので、 幾何学的マージンは ρ = 2 / |w| となる(?)。この幾何学的マージンを最大化することが目的となる。
|w| = sqrt(Tw w)
であり、2 / |w| の最大化を |w| / 2の最小化に置き換えると、 最小化問題としてのSVMの標準形が次のようになる。
(15.6)
線形制約のもとで二次関数を最適化する。 二次最適化問題 は標準的な二次計画法 (QP) ライブラリを用いてSVMを作ることができる。
- 訓練データ集合は、最良の分離超平面を一意に定める
- この平面を見つけるために、二次最適化問題を用いる
- 新しい点を分類するために、(15.1)式の分類関数が用いられる
- 符号によって分類されるクラスが決定する
- 点がマージンの範囲内ならば、どちらかのクラスを返すのではなく、「わからない」と答えることもできる
- 分類関数の値は、ジグモイド関数を用いて分類確率に変換することができる
- 超高次元問題（テキスト分類など）...一般的に線形分離できない
- 分離可能でも、ノイズ的な文書を無視して、大量のデータをよりよく分離できる解が望ましい
=> 小数の誤りを許容する幅のある決定マージンを許す
外れ値またはノイズ要素のいくつかの点は、マージンの内部または間違った側にある。 間違って分類された例に対してコストを支払わなければならない。
- ξ_i...スラック変数 (ξ_i ≧ 0)
ξ_iが非ゼロ値なら x_i は、 マージンの要件に合致しなくてもξ_iの値に比例するコストを払えばよい。
スラック変数のあるSVM最適化問題はつぎのようになる。
(15.10)
ソフトマージンSVMは、マージンとのトレードオフで、訓練誤差を最小化できる。 パラメータ C は 正規化項 で、オーバーフィットを制御する手段を与える。 C が大きいときは幾何学的マージンが減り、データを尊重しなければ目的関数が大きくなってしまう。 C が小さければ、データの塊をモデル化するように大きなマージンを取りやすくなる。
- 通常、サポートベクターは訓練データのごく一部
- 問題が分離不能またはマージンが小さい場合
- 間違って分類されたデータ点またはマージン内のデータ点が増えると、非線形の場合に主な速度低下の原因となる
線形SVMの訓練及びテスト計算量
SVMの訓練時間は、QP（二次計画法）を解く時間で占められる。 QPを解く標準的な時間は、データ集合のサイズの3乗である (Kozlov et al. 1979) 。 最近の研究ではSVMの訓練に関する計算量が削減されており、その多くでは近似解を用いている。
SVMは本質的に2クラス分類器である。SVMで複数クラスを扱う方法は以下のようなものがある。
- |C| 個の1対他分類器を構築、テストデータを最大マージンで構築するクラスを選ぶ
- 一連の1対1分類器を組み立て、ほとんどの分類器が選ぶクラスにする
- |C| ( |C| - 1 ) / 2 個の分類器の構築を含む
- 各分類器の訓練データ集合は小さいので、分類器の訓練時間は減少する
- 多クラスSVMの構築
- 構造化SVM
線形分類器による分類ができないデータ集合の場合はどうすればいいのか。
1次元の場合、図15.6で考える。 上段のデータ集合は線形分類器で分離可能。 中段のデータは線形分離できない。 下段のように、2次関数を用いてデータを2次元空間に写像すれば、 線形分類器で分離することができる。
SVM及び他の線形分類器は、 カーネルトリック と呼ばれる高次元空間への写像を容易かつ効率的に行う方法を提供している。
表13.9 テキスト分類の効果指標 Dumais et al. (1998)
Dumais氏は、SVMが最良のテキスト分類器であることを示した。
表15.2 SVM分類器の損益分岐点F_1 Joachims (2002a)
Joachims氏は、Reuters-21578データの全90カテゴリーについて、 大きい順に10個のカテゴリーとマイクロ平均した性能を示した。
訓練データはどれだけあるか
- ない
- ほんの少し
- たくさん
多くの問題とアルゴリズムにおいて、各クラスに数百から数千の訓練データが 高性能分類器を作るために必要。
手書きの規則による解法
IF (wheat OR grain) AND NOT (whole OR bread) THEN c = grain
注意して書けばかなり正確になる。 実際はもっと複雑で膨大。作成するのもメンテナンスするのも大変。
バイアスの大きい分類器
- ナイーブベイズ
人々が自然な作業の中でラベル付けを行う
- メールの分類
テキスト分類について、これまで述べてきたことすべてを利用できる。
SVMを使ってよい。