サポートベクターマシンの概要
小野田 崇
肺‖………刷‖‖鼎‖‖刷‖‖…削‖‖‖川‖‖川‖‖‖州…削‖服‖…酬‖川帖‖川削‖‖‖‖川‖‖州‖…削‖刷‖‖川‖l冊‖‖l騨‖…州‖州‖‖…州…削‖…酬‖l服‖州舶l‖…州‖l酬‖‖附‖‖附‖‖川‖‖仙1． はじめに
本稿では機械学習の研究領域で，最近注目をされているパターン認識の一手法であるSuppor七VectorMachine（以下，SVM）［1］の概要について述べる．SVMの研究は，80年代から90年代にかけて注目されたニューラルネットワークに比べて優れたパターン認識結果が報告（参考文献［2jなど）されて以来，数多くの理論的な研究が急速に行なわれてきた［3］．本稿では，Boser，Guyon，Vapnikの文献［4］，Guyon，Boser，Vapnikの文献［5］，Cortes，Vapnikの文献［6］およびVapnikの文献［7，1］に基づき，SVMのアルゴリズムを中心に紹介する．

図1：線形識別関数

以下，第2章では識別関数の構造とVC次元との関連について述べる．第3章では，線形SVMについて図1のようになる。図1は2次元の観測空間にデータHardMarginの場合とSoftMarginの場合に分けて紹が観測された様子を表している．ここで，白い円と黒介する．第4章では，第3章の線形SVMの非線形へのい円とを分類したいとする．しかし，式（1）からだけ拡張と2クラス分類問題で議論されるSVMを多クラでは図1の実線や破線のように，いくつもの線形識別ス分類問題へ適用する場合について簡単に紹介する．

関数が導かれてしまう．

第5章「おわりに」では，最近のSVM関連研究情報

そこで，以下の式で表現される制約を加えることにの収集が可能なウエツブサイトを紹介する．

よって，識別関数となる超平面を（w，ら）∈ダ×Rを有2．起平面集合の構造する関数に一意に決める．

本章では，Struc七ualRiskMinimizationの概念［7，1］nl（W・勘）＋らl＝1・（2）j＝1…．，rから導出されるひとつの学習アルゴリズムとその関つまり，この制約によってwとあは距離1川可lを持数構造について述べる．

つ超平面に最も接近するデータ点を表現することとまず，SVMの中核をなす超平面識別関数の構造について考える．いま，内積空間ダおよびパターンベなる．その様子を示したのが図2である．従って，2クトル集合名l，…，Zγが与えられたとすると，任意のクラス分類問題の場合，超平面間を垂直に測ったマー

超平面識別関数は次のように表現される．

ジン（開き）1は少なくとも2／l】w】lとなる．この超平面集合上の岬一つの構造の存在は，Vapnikの導出した‡z∈ダ‥（w・Z）＋あ＝0‡，（1）

以下の結果により確認することができる［7］．

この式（1）は，自由度として係数wと非負債であるらをパラメータとして有している．式（1）を図示すると

命題1月 を点（笈1，…，Zγ‡を含む最も小さい球βR（a）＝（z∈ダ：l】z−at】＜属‡（a∈ダ）の半径とし，おのだ たかし（財）電力中央研究所情報研究所〒20ト8511狛江市岩戸北2−11−1

1以下，「マージン上」と言う場合は、マージン（開き）を測定する際の超平面上を意味する．
2001年5月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（3）225

凱 線形SV恥宜凱且 斑a訂d至沌argimSVM
訓練サンプル（冨1，yl），‥．，（zで，yで），ご壱∈ダ，y壱∈（±1）
が与えられ，次式を満たす識別関数ん，ら＝Sgn（（W・盗）＋ら）を推定する問題を考える，ん，あ（z盲）＝机，豆＝1，…，ぞ・（5）この関数が存在すれば，式（2）の制約は次のように表現できる。
机・（（z壱・W）＋あ）≧1，五＝1，…フβ・（6）（w，ら），（−W，−あ）のようにwとらの方向の違いにより，

図2：制約付線形識別関数

同じ超平面識別関数の式が2つ存在することとなる．
しかし，式（5）と式（6）によって識別関数は一意に定次式がこれらの点を定義する識別関数であるとする。
ふ再＝Sgn（（w・Z）＋ら）

めることができる。
（3）

命題1によって，汎化能力の高い識別関数は式（6）で表現されるの制約条件の下，次式を最小化することそのとき，関数集合（ふ再：l㈲l≦A）は次式を満たで推定できる．

すVC一次元んを有する。
r（w）＝妄l柵ん＜属2ノ42＋1．

（7）

（4）

この凸最適化問題を解くため，式（7）のLagrangianを上記定理において，条件】lwll≦Aを省くとVC一次元計算するとがArF＋1となる関数の集合を導くことができる．ただg掬あ，α）＝喜】l叫【2¶∑α壱（財胸。W）＋ら）功（8） 壱

し，八「Fは空間グの次元を表す．つまり，条件IIw＝≦A＝1

によりArFより小さなVC一次元を得ることが可能であり，結果的に高次元空間で識別問題を取り扱うことがここで，α壱 ≧ 0はLagrange乗数である。このLa−grangianをα主について最大化し，Wとらについて最できる。

小化する。パラメータwとらについてのエの導関数

命題1は次のように解釈できる．

は鞍点において次式のように0にならなければならな
1．マージンと憂l酬が反比例の関係にあるので，小いので，さいマージンを大きくできれば，小さいVC一次元物ら，α）＝0，ェ何ら，α）＝0・となることが式（4）からわかる．

2．識別を小さなマージンで行なう場合，より大きいクラスの識別問題を扱うことができる．
訓練サンプルから高い汎化能力2を有する学習機械を実現するには，訓練サンプルに対する誤識別とVC一次元の両方を小さくする必要がある［7】。つまり，超平式（9）から次式が成立する．

ぞ 二・リ′ ‖、I、

w＝∑理路・（11）

豆＝1

結局，Wは訓練サンプルの展開式となる．wの解はた訓練サンプルを識別できる関数である必要がある。こだ一つに決まるが，係数α盲はその必要がない．

第3章で述べる．

（10）盲＝1

面識別関数はマージンを最大化し，同時に可能な限りのマージン最大化と訓練サンプルの学習については（9）

Karush−KulmーTucker条件により，鞍点においてLa，grange乗数α盲は式（6）を正確に表現し直した次式の制約条件に対して非ゼロでなくてはならない．

2非訓練サンプルの識別に対しても高い識別能力を持つということ．

226（4）

α盲・［机（（盟主澗）＋ら）−1］＝0，五＝1，…，β・（12）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

α盲＞0を有するパターン勘を飢朋研一土陥c抽、βと呼この緩和変数の導入によって，式（7）と式（6）で表現

ぶ．式（12）より，β叩pO7、￡仇c紬でβはマージン上に存される凸最適化問題が次式のようになる．

在することとなる．β叩pOア、土仇cま0†−β以外の訓練サンプ

慧チぎ T（w，g）＝…1湘＋7∑ J＝＝1

ルは凸最適化問題の解法には関係のないものとなる．
つまり，β叩pOrま沌cねrβ以外の訓練サンプルは式（6）ぞSubject七0 眺（（z壱。W）＋ら）≧1−∈盲，の制約条件を自動的に満たし，式（11）の展開項の部

オ＝1，…，β．

分には現れないのである．

（17）

目的関数の右辺第一項は，識別関数クラスのVC一次元

この凸最適化問題を解いて得られる超平面識別関の最小化に関連することが式（4）よりわかる．一方，数の汎化能力については，以下の命題が成立する［1］．

∑ぎ＝1モ。は訓練サンプル中で誤識別されるパターンの命題2サンプル数βの訓練サンプルから得られる上限値である．適切な正定数7を選択できるとすれ

g叩pOγ￡椀cれげβ数の期待値をβ−1で割った値は，非ば，式（17）で表現される凸最適化問題は任意の関数訓練サンプルに対する誤識別率の上限である．

集合におけるStruCtualRisk Minimizatioilの概念の実践的な方法となる［7］．

式（8）のLagrangianに式（10）、式（11）の条件を代訓練サンプルが完全に分離できる場合の式（11）と入すると，双対問題となる次の凸最適化問題を得るこ

同様に，式（17）の最適解において，Wは次式のようとができる．に訓練サンプルの展開式となる．
ぞ． （、（、Ⅹ∑宣−

1

盲＝1

Subjectto

w＝∑瑚㈱
ここで，係数α盲が非ゼロとなるのは、訓練サンプル

2−ノ＝1

α盲≧0，云＝1，…，g，
ど

（18）

盲＝1

∑町αJy勅（z盲・ZJ）（z盲，封室）が制約条件式（16）を満たす場合である．式（17）で表現される最適化問題の双対問題となる以下の凸∑α盲y盲＝0・（13）

二次計画問題を解くことで，係数α盲を求めることがj＝1できる．

式（11）の展開式を識別関数の式（5）に代入することによって，式（5）の識別関数を分類されるパターンと＿（5叩pOr土陥cねγβとの内積で評価される次式に書き換、1Xえることができる．

∑α盲−∑叫αノダ勅（勘・ZJ）

壱＝1l，J＝1

Subjectto O≦αi≦7，i＝17．．．フe，（14）（（妾′（Z）＝Sgnαjy盲（z・Z冊）・∑α盲y盲＝0・

（19）

盲＝1

以上より，式（13）で表現される凸二次計画問題を解KarusトKuhn−Tucker条件から，式（19）で表現されくことで，識別関数ん，る（ヱ）＝Sgn（（w・Z）＋ら）を得る

る凸二次計画問題の最適解は次の条件を満たす．

ことができる．これが基本となる線形SVMである．
α盲＝0 ⇒ 苫〟（z壱）≧1

3．2 So氏MarginSVM0≦勘≦7 ＝⇒ 3扉（z盲）＝0

現実問題としては，訓練サンプルを完全に分離でき

α壱＝＝↑ ⇒ y盲J（石室）≦1

る超平面は存在しない場合が多い．そのような場合，この条件より，識別結果sgn（J（勘））が机と一致してい次式で表現される緩和変数を導入して式（6）を満たさて，マージン値y査′（zj）が1より大きいサンプルに対か−訓練サンプルが存在しても良いようにする［6］．
古壷≧0，云＝1，…，β・に緩和できる．

4．線形SVMの拡張
4．1 非線形SVMへの拡張
第3章では線形SVMについて述べた．しかし，線机（（z盲・W）＋あ）≧1一ぞ哀，壱＝1，t‥，ぞ． （16）2001年5月号

応するα盲は0になることがわかる．
（15）

この緩和変数を使って式（6）の制約条件を次式のよう（20）形SVMは線形分維可能な場合には高い汎化能力を達© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）227

ガ且感

inputspssce

ガ盟

⑳

形写像

＝

‡ニ：ニ：、・・・ご丁ご‡

00⑳飴auturespace⊥・−・

御＝画細か㈲掛㈲路職刷

図3：非線形SV乱4の原理

成できるが，実際の問題では線形分離可能な場合は多このカーネル関数を用いると，高次元特徴空間での式くない。そこで，より一般的な識別関数を推定するた（14）に相当する識別関数は次のようになる。

め，前処理として入力ベクトルⅩ1，…，Ⅹぞを次式のよ

凝

うに高次元特徴空間に写像し，その後，その特徴空間∫（Ⅹ）＝Sg血輌）十ら）・（24）で線形SV加‡を行うという方法が考えられる．

結局，ユークリッド◎：Ⅹ壱トヰ盟主．

（21）

空間の内積に代わって適切なカーネル関数んを選択できれば、このカーネル関数ん

本章で用いる勘と第3章で用いた勘とは異なり，Z盲に基づく非線形SVMにほ，前章で述べた線形SVMのほ観測された入力パターンⅩiを高次元特徴空間に写特性が全て適用できる。図3に非線形SVMの原理を像した結果であることに注意されたい．

示す・図3では，入力空間（ここでは風2）上のデー（上図左）を非線形の写像を使ってより高次の特徴空間

式（19）で表現される凸二次計画問題の目的関数を最大化し，式（14）で表現される識別関数を推定するに（ここでは風3）にマッピングし，特徴空間上で分離可は，高次元空間での以下の内積を計算する必要がる。

能な超平面を作成することで（下図左），入力空間では非線形の識別関数になる（下図右）SVM（上図右）が構（◎（Ⅹ）・◎（Ⅹ誹・（22）成できる様子を示している．

また，非線形SVMは様々なカーネル関数を利用し式（22）で表現される内積の計算には膨大な計算が必て，多様な学習機械を構成できる．図4に非線形SVM要となる。Mercerの条件の下，元の観測空間で定義さの構造を示した．図4中のカーネル関数んには，以下れる次式を満たすカーネル関数を用いて，膨大な計算で述べるようなカーネル関数を利用することが可能を削減できる。

である。また，SVMを構成するためのパラメータは（◎（Ⅹ）・◎（Ⅹ壱））＝ん（Ⅹ，Ⅹ壱）．

望2恩（6）（23）

凸二次計画問題を解くことで推定することが可能で© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチタ図4：非線形SVMの構造ある．図4中の第一層のⅩ盲は訓練サンプル集合の補にカーネル関数たは一致する必要がある．このことか集合（β叩pOr±仇cわγβ）であり，第二層の人はLagrange

ら，∬盲メ＝（y盲yメん（ⅩわⅩJ））盲ノは正催行列となる．つま乗数α盲から入＝封iα盲で計算できる．以下に一般的にり，で利用されているカーネル関数を紹介しておく．

∑勘α調J妬，ⅩJ）

Polynomialカーネル関数

盲，ノ＝1（た（Ⅹ，Ⅹ吏）＝（Ⅹ・Ⅹ≦）d．

≧0・（29）∑αJリノ◎（−ⅩJ

（25）

．ノ＝1）

Radialbasisカーネル関数
ん（Ⅹ，Ⅹj）＝

式（16）から∈J＝0であるβ叩pOrま拘c±orxJに対し，次式が成立する．

exp卜】lx−Ⅹ州2
（26）

t、

∑y盲α盲・た（ⅩJ，Ⅹり＋ら＝0・Sigmoidカーネル関数

（30）

j＝＝1

以上より，変数あは次式のように，0≦αJ≦7とな
た（Ⅹ，Ⅹ盲）＝tanh（K・（Ⅹ・Ⅹ盲）＋β）・（27）るαメを有する恥肝油月毎加の平均によって得ることができる．

式（24）で表現される識別関数を求めるには，以下の最適化問題を解けばよい．

（、ら＝択一∑脚盲・た（ⅩJ，Ⅹi）・「＿ （（31）

壱＝1

1

瑠Ⅹ ∑α壱−た1

ワ ∑α盲αJy勒ん（Ⅹ盲・XJ）
z，ノ＝1

Subjectto O≦α壱≧7，五＝1，．‥，β，ゼ∑αiy壱＝0・

ここまでは，全て2クラス分類問題の場合についての議論である．本節では，多クラス問題をSVMで扱（28）

う一般的な方法について簡単に紹介する．

ま＝1

カーネル関数たはMercerの条件を満たす必要がある。つ，まり，式（23）のように高次元特徴空間での内積

2001年5月号

4。2 多クラス問題への拡張たクラスの分類問題を解くため，SVMでは1クラスとその他の残りのクラスとを識別する2クラス分© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）229類SVMの集合Jl，…，∫たを生成する。そして，符合

radialbasis壬hnctionclassiBers．IEEE升αnS．Si9n．

関数を適用する前に，次式のような最大出力に従っ

P7−OCeββ壱†7タ，Vol．45，pp．2758−2765，1997・て多クラス分類を行ない，2クラス分類SVMの集合［3］小野田崇．電気事業における最新機械学習技術の∫1，…，J■んを統合しておく。

適用可能性．調査報告書，（財）電力中央研究軌？rgmaXタJ（Ⅹ），

1999，

（32）

J＝1…‥た［4］B・E・Boser，Ⅰ・M・Guyon，andV・N・Vapnik・AtrainM

ここで，gJ（Ⅹ）は次式で表現される．

lng algorithm fbr opも1nlalmargln Classi且ers・In（、タメ（Ⅹ）＝∑y壱αさ・ゐ（Ⅹ，ⅩJ）＋らJ・

D．Haussler，editor，5thArmualACMWorkshopon（33）

COLT，PP．144−152，Pittsburgh，PA71992・ACM

盲＝1

最終的に符合関数を適用する際は，以下のようにな

Press．

る．

［5］B・E・Boser，Ⅰ・M・Guyon7andV・N・Vapnik・Auto−∫J（Ⅹ）＝Sgn（タメ（Ⅹ））・

matic capacity tuning ofverylarge vc−dimension（34）

classifiers．In S，J．Hanson，J．D．Cowan，and

興味深いことにこの式（33）で表される関数タブ（Ⅹ）の値

C．L Giles，editors，Adγα陀Ceβ哀れⅣe祝アーαgJγゆr7れ・α−は，棄却決定にも適用することができる．例えば，識tionProcessm9Systems5，PP・147−155，SanMateo，

別の信頼性測定として，関数タブ（Ⅹ）の値の最大値と2CA，1993・MorganKauhann・番目に大きい値との差を考えれば，その差に基づき棄却決定を行なうことができるのである。

【6］C・CortesandV・Vapnik・Supportvectornetworks・
几飽cん去れeムeαrγ？Z柁タ，Vol．20，pp・273−297，1995・

5。 ぁわりに
本稿で最新の機械学習手法の一つとして紹介した［7］Ⅴ．N・Vapnik・rゐeⅣα加げe OJβねま盲βま盲cαgエeαγn吉相タ

SVMは，ニューラルネットワークに比べて優れたパrゐeoγy．Springer，1995・

ターン認識結果が報告されて以来，様々な研究者に注目され，盛んに理論的研究がなされてきた．しかし，最適化理論の立場から機械学習を扱う研究は，まだ未開拓であり，様々な研究課題が残されている。
本稿での解説はSVMのさわりに過ぎない，SVMと最適化手法との関連の研究についての詳細を知りたい方は，WWW．kerneトmachines．orgを参照されたい。
このホームページにはSVMに関する研究の論文やSVM用の最適化手法のプログラムなどが掲載されている．また，最適化手法に関わる他の機械学習手法について知りたい方は，boosting，Orgを参照されたい。
このホームページには，本稿では触れなかった最新機
械学習法の一つアンサンブル学習と最適化問題との関連についての論文が充実している．
参考文献［1］V．N．Vapnik・StatislicalLearnin9Theory・Wiley，
NewYork，1998■［2］B・Sch61kopf，K・Sung，C・Burges，F・Girosi，P，Niyogi，T．PogglO，andV・Vapnik・Comparing

supporもvectormachineswithgaussiankernelsto

望3⑬（8）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ