サポートベクターマシン：最適耳ヒからのアプローチ
津田 宏治

Il……ll…llll川…lll…lllll…llll…＝‖‖‖＝‖‖＝＝‖‖‖＝‖‖‖＝＝‖‖‖‖‖‖‖＝‖‖鮎Ill…附‖…＝‖‖‖＝‖‖‖＝‖‖‖＝＝‖‖州‖＝＝＝‖‖榊‖……ll…＝‖‖‖＝‖‖‖服‖川‖＝‖‖＝＝‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖＝‖‖‖‖‖‖潮‖lll‖冊Ill……llll…

1． はじめにっている解のことを指す。このような解を出力する学

サポートベクターマシンとは、90年代に有名になったパターン認識の一手法である［18］。従来法、特に80年代から90年代にかけて注目されたMultト
1ayerPerceptron（いわゆるニューラルネット）に比べて優れた結果が次々と報告され（例えば［13］）、それに呼応して多くの理論的な研究もなされている。SVMに関する理論的な研究には、次のようなアプローチがある。

習手法は、スパースな方法と呼ばれる。
スパースな解の利点は大きく分けて三つある。第一には、未知サンプルに対する出力の計算が容易になることである。例えば、SVMのように、カーネル関数の線形結合が識別関数であり、パラメータが各カーネル関数の重みであるような場合には、重みが0のところのカーネル関数は計算しなくていい。第二には、スパース性を用いることによって、高速な学習アルゴリズムが得られることである。SVMの最適化問題は、◎学習理論からのアプローチ：SVMの汎化誤差の二次計画問題として定式化できるが、係数行列は一推定や、それに基づく新しい学習基準の設定など般に巨大でかつ密であるので、高速に解くためには、を課題とする研究（例えば［20］）。

解のスパース性をうまく用いる必要がある。第三に、●関数解析からのアプローチ：SVMが表現する識別関数に注目し、再生核ヒルベルト空間の理論などと結びつけて議論する研究（例えば［19］）。

学習結果の解釈が容易になることである。例えば、複数の種類の特徴をまとめて学習する場合には、どの特徴の重みパラメータが非ゼロになったかを分析することによって、識別に重要な特徴を知ることができる。

○最適化からのアプローチ：学習に必要な最適化問

このような利点のために、他の非スパースな手法にス題の高速な解法の提案や、「スパース」な解を導パース性を付加しようという研究が現在盛んである

く学習法の研究など。

［8，15，16］。

本誌の読者には最適化のエキスパートが多いと思わ

本稿では、まず、SVMとそのスパース性についてれるので、本解説では、第三のアプローチを扱う。特の説明から始め（第2章）、スパース性を生かして学に最近の機械学習の研究において一つのキーワード習を高速化する方法について述べる（第3車）。さらとなっているスパースな解を導く手法について中心的に、第4章では、SVMのスパース性を向上させる方に述べる。他のアプローチに関しては、［21，22］を参法について述べる。次に、学習法のスパース化の一例照していただきたい。

として、伝統的な識別法である線形判別分析のスパース化を取り上げる（第5章）。さらに、スパース性とは学習機械は、一般に複数のパラメータ（パラメータ直接関係はないが、最適化問題との関連から、Bayesベクトル）を持つ。訓練サンプルが与えられたとき、Poin七Machineを紹介する（第6章）。第7章はまとめ学習手法によってパラメータベクトルの最適解が与えである。

られる。ここで、スパースな解（SparseSolution）とは、パラメータベクトルのうち、多くの要素の億が0にな

2．SVMとスパース解
2．1 線形SVM

つだ こうじ
産業技術総合研究所生ノ命情報科学研究センター〒135−0064 東京都江東区青梅二丁目41番地6
2001年5月号

まず線形SVMの定式化を行う。ごい…，ご沌∈沢dを訓練サンプルとし、yl，…，y陀∈（1，−1‡をクラスラベ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）2卑9ルとする。線形SVMの識別関数は、パラメータベク

このような ◎が存在すると仮定し、況ヴにおいて、

トルをぴ∈況d，ら∈況とすると、SVMを通用しよう。このとき、識別関数は、
7tプレ）＝ ぴT畔）＝∑α沖（げ◎（ユ：′）∫け）＝∽γご＋ら（1）（9）

壱＝1†lと表される。学習においては、次の最適化問題を解＝ ∑α舶，ご′）

く。

（10）

ブ＝1と書ける。また、学習の最適化問題は、次のようにな霊nc（柚），折掴‡2（2）る。

盲＝1篭n∫（舶）＋人αr∬α

ここで、l恒‖2は、過学習を防ぐための正則化項であり、入は、正則化パラメータと呼ばれる定数である。

（11）

ここで、∬は、訓練サンプル間のカーネル関数の値かまた、Cは、Softmargin損失関数

ら成るれ×和行列である。この最適化問題も、（2）とCり （∬），y）＝maX（1−yJい：），0）

同様に二次計画問題に書きかえられる。
（3）γl 溜X ∑α吏一芸藍α棚胸，ごノ）である。この間題の最適解においては、Representer定7＝1

理［7］により、∽は次のように分解できる。

壷，j＝1

Subjectto O≦αi≦C，i＝1，…，n，（12）Tl∑芸10′壱封盲＝0・′・・−ご・iノ・

（13）

（4）

2．3 SV］Ⅶのスパース性

t＝1

また、最適化問題（2）は、αをパラメータとする次のKarush−Kuhn−Tucker条件から、問題（13）の最適解凸二次計画間置と等価となる。

は、次の条件を満たす［18］‥
γl＿γ乙

1・＼

ニーニ・・二伸′り．り′・′・ト′

盲＝1！，ノ＝1

α壱＝0 ⇒ y壱ノー（ご壱）≧10＜α盲＜C ⇒ y盲∫（ご盲）＝1

Subjec七to O≦αi≦C，i＝1，…，n，（5）α盲＝C ⇒ 封げ（∬盲）≦1∑≡1α潮＝0・（6）

この条件より、識別結果sgn∫（ご）が机と一致してい

ここで、Cは、入の代わりに正則化の度合を制御するて、また、マージン借財げ（ユ：）が開催1より大きいサンパラメータである。

プルに対応するα壱は0になることがわかる。幾何的には、図1のように表される。図の○、□は、それぞれ

望．慧 カーネルトリックによる非線型への拡張

異なるクラスの訓練サンプルを表す。また、実線は識別面を表し、破線はノー（ご）＝士1の面を表す。討壱∫（∬）＝

線形SVMは、2クラスが線形分離可能な場合には、高い認識率を達成できるが、実際にはそうでない場合1の面（図の点線）より境界側に存在する点に相応すが多い。そこで、前処理として、非線型な写像を用いるパラメータのみが非ゼロとなり、残りのパラメータて、より高次元の空間に写像を行い、線形分離性を高は0となる。図では、非ゼロになるパラメータに対応めることが考えられる。

するサンプルを塗りつぶして示している。

一般に低次元空間に多くのサンプルがある場合に◎‥紀d→紀曾（7）は、0になるパラメータの数が多くなる傾向がある

ただし、この写像は、元の空間におけるサンプル同士が、高次元に少数しかない場合には、0になるサンプの距離関係をある程度保存する必要がある。そうでルの割合は小さくなってしまうことが知られている。

ないと、クラス内のまとまりが無くなって、識別が困

高次元空間で、よりスパースな解を得るためには、4．

難になるからである。そこで、元の空間で定義される章で述べる方法を用いる必要がある。

カーネル関数ゐ（∬，ご′）を用意して、◎は次の条件を満凱 SVで沌の学習における最適化手法たすと仮定する。
◎（げ◎（ご′）＝ん（ご，ご′）25①（28）

一般に、二次計画問題を高速に解く手法に関しては（8）

多くの文献があり、また、フリーや商用のパッケージ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

3．2 Decomposi七ionMe七hod

DecompositioェーMe七hodは、二次計画問題を繰り返し解く点はChunki喝に類似しているが、各副問題のサイズが固定されているところが異なる。この手法は、各二次計画問題が、一つでもKKT条件を満たさないα壱を含んでいれば、結局最適解に達することができるという性質に立脚している。ここでは、副問題のサイズを固定して、各ステップにおいて、α壱を一つづつ入れ替えていく方法がとられる。しかし、実際には、この手法の収束は非常に遅い。実用的には、入れかえる変数を選ぶための良いヒューリスティックと、高速なキャッシングの方法が必要になる。SVMlight［5］では、このような改良を施して、実際にDecomposi−tionMethodを使っており、数千の非ゼロα壷を含む問題を高速に解くことができる。

図1：SVMのスパース性
3．3 SMOも普及している［2］。しかし、従来の手法には、小規模な問題にしか適用できなかったり、また、係数行列が疎であることを仮定するものが多い。SVMにおいては、係数行列は巨大であり、また、疎でもない。このような困難にもかかわらず、少ない記憶量で、高速に大規模な問題を解ける手法がいくつか提案されている。本章では、このようなSVMに特化した手法を紹介する。ここで紹介する手法はすべて上に述べた解のスパース性を利用している。

SequenもialMinimumOptimization［10］は、I）ecom−postionMetl−Odの最も極端な場合として捉えることができる。各ステップでは、2変数の二次計画問題が解かれる。この最適化は、解析的に行うことができるので、二次計画問題を解くパッケージは必要ない。

SMOでは、最も重要な問題は、この2変数をどのように選ぶかという点にある。文献［10】で示されたヒューリスティックは、KKT条件に基づくシンプルなものであるが、その改良版も提案されている［6］。提案されたときには分類問題だけを対象としていたが、回帰3．1 C‡1unking

問題に適用できる手法も提案されている［14］。

ほとんどの問題においては、最適なα盲は0またはCである。もしもどのα盲が0になるかを知っていれば、それに対応する係数行列の行と列を、目的関数の値を変えることなく取り除くことができる。また、最適解

4．gl正則化項によるスパース解
従来から、正則化項として、β1ノルム、すなわち、がKKT条件14を満たすという点も変化がない。文献［17］で提案されたChunkingという手法では、スパー

妾‡α壱・（15）

ス性と、KKT条件を用いて高速化を行う。Chunking
においては、各ステップで、すべての非ゼロα盲と、を用いることによって、スパースな解を得られること

KKT条件を満たさない数個のα古からなる副問題が解が知られている［1］。従って、SVMの正則化項（式11）かれる。各ステップにおいて、副問題のサイズは異なを、β1ノルムと入れ替えれば、よりスパースな解を得るが、最終的には其の非ゼロα盲の数に一致する。こることが期待される。このような手法は、LinearPro−の手法をもちいれば、ある程度の大きさの問題を扱う

grammingMachineと呼ばれる［3］・この最適化問題ことができるが、非ゼロαjの割合が高い場合には、やは、αをはり大きな二次計画問題を解かなければならないという欠点がある。

2001年5月号

α壱＝αJ−α「，αJ≧0，α「≧0© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（16）（29）2引のように分割することにより、線形計画法で解くこと

ここで、卵ゐ ＝ができる。

∑た＝1，2！五l鮎材牒＝卵2−軌フ〟＝脚r，勒＝11孟7∬1た，Ar ＝ 方正r−（◎（ユT壱）・◎（勺））＝ん（ご盲，ごJ）である。（20）の最適化問題？1ご∴。一∴ 二■−∴‡・ニにスパース性を付加するためにゼ1ノルム正則化項をsubjectto yif（1：i）≧1N∈

加えると、
71

α∴α「，∈壱≧0（23）瑠Ⅹ−J（α）＋入∑l可盲＝1

この方法により、識別性能を大きく下げずに、解のス

この最適化問題は、次のように書きかえられる［8】。

パース性を大幅に向上させることができる。

5。線形判別分析をスパースに（24）

γも 芸言語Il釧2＋C芸lα盲I

前章のようにβ1ノルムを正則化項に用いれば、様々Subjecもto Hα＋1b＝y＋蜜な手法にスパース性を付加することができる。本章

1訂雷＝Ofbrん＝1，2

では、長い歴史を持つ線形識別器である線形判別分析にスパース性を付加する方法について述べる。ここで

ここで、芭∈舵㍑，わ，C′∈紀である。雷，あは、補助的には、まず、線形判別分析法をカーネルトリックを用い用いられるスラツク変数であり、Cは人に変わって正て、非線型に拡張し、その上でスパースにする。

則化の度合いを制御するためのパラメータである。線

まず、線形判別分析法について説明する。この手法

形判別分析は、もともと全くスパースでない手法であでは、線形識別関数ノ （ご）＝ぴTごによって、訓練サンるので、この改良によるスパース化の効果は絶大であ

プルを射影したとき、最も2クラスが分離されるようる。データセットによっては、パラメータ全体の97％にwを決定する。分離度は、次のRayleighCoe氏cientが0になった事例も報告されている［8］。

他の手法に関しては、KernelPCAのスパース化がによって定義される。

報告されている［16］。同様にして、因子分析、クラス坤）＝7（19）

ここで、ぶβ，ぶⅣは、それぞれクラス間、クラス内分散を表し、汀蟻をクラスんのサンプル平均、左をクラスんタリングの諸手法などもスパース化できるとL考えられる。

臥 迅aye＄㌘￠畳汲もP沌a油量meのインデックス集合とすると、次のように表される。

SVMの関連研究においては、大規模な問題に相応
gβ＝（m2−ml）（m2−−γnl）rさせるために、線形計画問題か、二次計画問題に帰着させるのが一般的であるが、理論的な立場から、よりgⅣ＝∑∑（ユ‥壱−m抽壱≠mた）r・複雑な最適化を必要とするものもある。ここでは、そた＝1，2盲∈乱のなかから、BayesPoin七Machine［11，4］を紹介する。

そして、ぴは、この分経度を最大にするように決定さ

BayesPoin七Machineは、線形識別器であるので、識れる。

別関数は（1）で表される。但し、il可l＝1，ら＝0とす
し1i一・・／刷（20）

カーネル特徴空間で線形判別分析を行うため、特徴る。このとき、すべての訓練サンプルを正しく分類する∽の集合は、空間での分離度を定義しよう。SVMと同様に、ぴを、
y＝‡叫y査∫（ご壱）＞0；宣＝1，…，㍑，】恒＝＝1）
特徴空間に写像された訓練サンプルの線形結合で表と表される。この集合yは、Ⅵrsionspaceと呼ばれすと、［11］、SVMの解は、VersionspaceのTchebychef萱●中心71

ぴ＝∑α婚（ユて盲）・（21）

壱＝1られている［11】。しかし、理論的に最適な点は、Bayes（19）の中のご盲￥を、◎（ご盲）で置き換え、ぴには、（21）pointと呼ばれる点であり、これは、VersionSpaceのを代入すると、分離度は次のように書ける。

重心によってよく近似される［9］。VersionSpaceは、図（αr卵）2 αr〟αJ（α）＝

芝52（30）αγ∧rα αrⅣα7（yに含まれる最大の球の中心）に対応することが知（22）2，3のように、半径1の球の一部分として表される。

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

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

ネットワークにおいて、目的関数が複雑になりすぎ、
●●

●
●

●●●

◆

数理計画法特有の道具を用いて、学習の問題に取り組● ●◆むこともできる。

●●◆

最適化理論から学習を扱う研究は、未だ未開拓であ●‥●・．ご・るので、さまざまな研究課題が考えられる。例えば、◆●●◆●

一げ ㌧ヽ ∵◆●▲● ●′V．．

●●●●●

あり、また、実用的にも高速である。KKT条件など、

● ●●●

◆◆

◆

●●▲

●

●●●．．ヽ

●●●◆●●◆′◆● 〜●●、●●● ●◆● ◆●1′傭

●

● ●

●

●●●●●●◆一■●ヽヽ

√ン． ◆■

ヽ●
●

●

● ●●

●●●●

●

■

●●

数理計画法は、勾配降下法に比べて、理論的に明確で

◆ ◆●◆

●●●●

⇔

深刻な局所解の問題を生じたことの反省からである。

・●■ ●●●●■．．

●

●−

●◆

−・︑◆

∴十●●●● ●．

◆◆ ● ●●●

へ

正則化パラメータの倍とスパース性の関係など、未だよく分かっていない問題もあるので、最適化の専門家の機械学習分野への貢献は重要であろうと思われる。

図2：SVMがうまく働くVersionSpaceの例。重心（◇）
参考文献がSVMの解（×）に近い。

［1］K．P．BennettandO．L．Mangasarian．Robustlin−

ear programmlng discrimination of twolinearlyごinseparablesets．OptimizationMethodsandSoルー．

●．●・．● l●● ヽ●◆●●●‥J：：●．

●．

▲ ▲ ヽ ●● ●Ⅶαre，1：23−34，1992．

▲ ● ●●1−−●
■

ヽ◆●

●◆

●

◆●

●

［2］D．P．Ber七sekas．NonlinearPro9ramming．Athena

●．︑

●

一▲M●◆

●●

◆●●

∵⁚

●◆

●●．イ′●● ′ ●●Scienti負c，Belmont，MA，1995．

■．．．．．‥・．．
●

●●●．
．

●′●●

⁚●●●●〜●●●●●●■・⁚∵⁚．∴．ヽ●′′●

●◆●
◆．

．．．・．

［3］T．Graepel，R・Herbrich，B．Sch61kopf，A．J，Smola，P．L．Bartlet七，K．−R．Maller，K．Obemayer，and R．C．Williamson．Classification on
PrOXimityda七awithLP−maChines．InD．Willshaw

図3：SVMがうまく働かないVersionSpaceの例。Ver−sionSpaceが一方向に長く、重心（◇）は、SVMの解（×）から離れている。

andA．Murray，editors，Proceedin9SOfICANN

99，

VOlumel，PageS304−309・IEEPress，1999，［4］R．HerbrichandT．Graepel．IjargeSCaleBayespointmachines．In AdりαれCeβ去れⅣe≠γα〜Jゆrmα一

もしも、VersionSpaceが図2のような形をしていれ
ば、SVMの解は、重心と近くなるが、図3のように、

tion System Processm918，2001．accepted fbrpublication．

一方向に長い形をしていると、SVMの解は、重心から遠くなってしまう。BayesPointMachineでは、この［5］T．Joachims．Makinglarge−SCale SVMlearning

間題に対処するため、Billiard法［12］を用いてⅥrsion

PraCtical．In B．Sch61kopf，C．J．C．Burges，aSpaceの中心を近似的に求める。この方法は、いくつ

A．J．Smola，ediもors，AdvαれCeβ盲㍑∬emもeg〟e兢odβ

かのベンチマークでSVMを上回る結果を出している−β呼pOrま沌cれげエeαrγ抑タ，pageS169−184，Cam−［11］。

bridge，MA，1999．MITPress．

ア． ぁわりに［6］S．S，Keerthi，S．K．Shevade，C．Bhattacharyya，

本稿で紹介した多くの手法では、数理計画法が学習

K．R．K．Murもhy・Improvements to Platts SMOのために用いられている。特に、線形計画問題や、凸algori七hm董brSVMclassi負erdesign．TechnicalRe−

二次計画問題のように、確実に大局的最適解を求めら

POrtCD◆99−14，NationalUniversityofSingapore，れる手法が好まれている。これは、かつてニューラル

1999．hモモp：／／guppy．mpe．n11S．edu・Sg／〜mpessk．

2001年5月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）253［7］G．S．KimeldorfandG・Wahba・Acorrespondence［17］Ⅴ．N・1もpnik・且油壷・α去盲omβ∫かepeγlde？もCeββαβedbetween Bayesian es七imation on sもochastic pro−
CeSSeS and smoothing by splines．Arm・Math．

onEm・PZ7、icalDaia．Springer−Verlag，Berlin，1982．

［18］V．N・Vapnik・StatisticalLearnin9Theory・Wiley，

βまα土壱βま．，2：495−502，1971．

NewYork，1998．

［8］S．Mika，G・Ratsch，andK．−R・Mii11er・AmathMematicalprogrammlng aPPrOaCh toもhe Kernel［19］G．Wahba・Suppor七vec七ormachines，rePrOduc−

1ngkernelhilbertspaces，andrandomizedGACV・

Fislleralgorithm．In』duαれCeβ盲71Ⅳe祝γαg坤r−

InB．Sch61kopf，C・J．C，Burges，andA・J・Smola，

mαま盲0γもProceββ名花夕軸βまemβJβ，2001・tOappear・‥1ミ．川・ト‥ト∴・・ご・…・ヾり・〜、■・′・＝7．−イ√′−ん…／・ヾ ・一亘H仙・／［9］M．OpperandD・Haussler・Generaliza七ionperfbr〜

l々cior Learrun9，PageS69−87，Cambridge，MA，

mance ofBayes opもimalclassi五caもionalgoriもhm

1999．丸ヰIT Press．

fbrlearnlng a PerCePtrOn．Phys富CalReview Let−
［20］R．C．Williamson，AJ．Smola，andB・Sch61kopf・

まerβ，66：2677，1991．

Generalizationper壬brmanceofregulariza七ionnet−［10］J．Plat七．Fas七training of support vector ma−

works and support vector machines via entropy

chinesusingsequentialminimaloptimiza七ion・‡nnumbers of compac七 opera七OrS・ NeuroCOIJT

B．Sch61kopf，CrJ．C．Burges，andA・J・Smola，edト TechnicalReporもNC−TR−98−019，RoyalHolloway

セors，Adγα陀Ceβ五和∬e門甘eg〟e土んodβ−β叩ダOrま拘c−College，Universi七yo壬●London，UK，1998・Toap−

tor Learnin9，PageS185−208，Cambridge，MA，

pearinJgβ屈升αれβαCま盲0柁β0れムゆ7−mα去盲0陀アゐe−1999．MIT Press．

1‖て／・［11］T．GraepelR・HerbrichandC・Campbell・Bayes［21］津田宏治．サポートベクターマシンとは何か．電point machines：Estimating the bayes pointin

子情報通信学会誌，83（6）：460−466，2000・

kernelspace．InProceedin9S OfL7CAIWorkshop飢朋研一土仇cわr肋cん去れeβ，pageS23【27，1999・［22］赤穂昭太郎and津田宏治，サポートベクター
マシン：基本的仕組みと最近の発展．数理科学，［12］P．Rujan・Playingbilliardinversionspace・Neural38（6）‥52−58，2000・

Coγr準祝≠αま去抑，9：197【238，1996・［13］B．Sch61kopf，K．−K．Sung，C・J・C・Burges，

F．Girosi，P・Niyogl，andV．N・Vapnik・Compar−

ingsupportvectormachineswi七hgaussiankernels
七o radialbasisfunction classi点ers．1EEE Tl−ans−αC￡去0れβ0㍑β盲タれαg Proceββ去れダ，45（11）：2758−2765，
1997．
［14］A．Smolaand］〕・Sch61kopf．A七utorialonsupporもvectorregression．StatisticsandCom・Putin9，2001・
R）rthcomlng．
［15］A．J．SmolaandP．L・Bartlett．Sparsegreedygaus−

Sian process regression．In Advancesin Neural
Jゆァ、mαま盲0†lPァ、oCeββ去mタ鞄β土emβJβ，2001・七oap−
pear・［16］M・Tipping・Sparsekernelprincipalcomponenもanalysis．InA血α陀Ceβ去れⅣe祝γαg坤r7乃α土査0柁Pro−
CeSSm9Systems18．MIT−Press，2001・tOaPPear・25卑（32）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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