大規模な半教師つき学習に対する最適化アプローチ

大規模な半教師つき学習に対する最適化アプローチ

Optimization Approaches for Large-Scale Semi-Supervised Learning

矢島 安敏

∗

Yasutoshi Yajima

東京工業大学経営工学専攻

Department of Industrial Engineering and Management,

Tokyo Institute of Technology

Abstract: We present optimization approaches for semi-supervised learning for classification based on the formulations of Support Vector Machine (SVM) for the conventional supervised setting. We first introduce the Laplacian of a graph and the associated graph kernels which are exploited in many semi-supervised classification methods. We will show that these methods can be naturally derived from the conventional formulations of SVMs with the graph kernels. The proposed optimization problems fully enjoy the sparse structure of the graph Laplacian, which enables us to optimize the problems with a large number of data points in a practical amount of computational time. Some numerical results indicate that our approaches achieve fairly high performance on large scale problems.

1

はじめに

Support Vector Machine(SVM)を用いた判別法は, 文書の分類や画像の認識といったさまざまの分野に応 用され, 非常に有力な判別法と考えられるようになって きている. SVM は従来の判別法と比べると, 最適化問 題を解く必要があるなど計算が複雑で, 特に大規模デー タに対しては実用的な意味で適用できないと考えられ ていた時期もあった. しかし, 計算機能力の進歩と様々 の最適化技術を取り入れた高速アルゴリズムの登場で, データマイニング手法の一つとして, 最近ではマイニ ングパッケージにも取り入れられるようになってきて いる. SVMをはじめとする従来の判別問題では, ラベルの 与えられている学習用データを用いて判別関数を構成 する「教師つき学習」が行われてきた. しかし, 実用 に際しては十分な数の学習用データが得られない場合 も少なくない. 例えば, 文書の分類の場合では, 学習用 データを作成するためには専門家などが文書を読み分 類する作業が必要であり, 通常これには相当なコスト が伴う. そのため, 少量のラベル付きデータからでも高 い判別精度を実現する判別法が求められている. 近年, ラベルの与えられていない未ラベルのデータも学習に 用いることで, 判別精度を向上させる試みがなされて いる. このような学習を「半教師つき学習」と呼んで ∗_{連絡先：東京工業大学経営工学専攻}       〒152-8552 目黒区大岡山 2-12-1       E-mail: [email protected] いる. 半教師つき学習では, 与えられたデータ間の関連性を 枝の重みとしたグラフを用いることでデータの分布の 構造を抽出し判別が行われている [12, 1, 10]. また, こ れらの手法と関連し, グラフの隣接行列あるいは枝の重 みを要素とした行列を用いカーネル行列を構成する方 法 [5, 9, 13] が提案されている. そこで, 本研究ではグ ラフ構造より導かれたカーネル行列を SVM に用いた 半教師つき学習について報告する. SVMで扱われるカーネル行列は, 次元が学習データ 数の正方行列となるため, データ数が大きな問題でも効 率よく学習が行えるよう, アルゴリズムにいくつかの工 夫がなされている. ほとんどの SVM のソルバーでは, カーネル行列の特定の列 (または要素) のみを必要に応 じて計算する, あるいはカーネル行列の一部のみを主記 憶に記憶するなどの工夫により, データ数の多い問題に 対応している. しかし, グラフ構造より導かれたカーネ ル行列の場合には, 非常に特殊な場合を除けば, 一般に は行列の特定の要素を効率的に算出することは難しい. また, カーネル行列を構成するためには, 逆行列計算な ど非常に多くの計算を必要とする. さらに, カーネル 行列は要素が非ゼロで稠密な行列である. したがって, データが数万を超えるような状況ではカーネル行列自 体を主記憶に保持することは通常では困難である. 本研究では, 従来あまり用いられていない主問題によ る SVM の定式化を用いることで, カーネル行列を陽に 求めることなく学習を行う枠組みを提案する. 提案す

る定式化の場合, 標準的な共役勾配法による最適化に適 したものであり, 特にグラフの疎構造を用いれば, デー タ数多い大規模な問題でも高速に学習を行うことが可 能である. まず, 第 2 節では 2 クラスの SVM について述べ, 第 3節ではグラフ構造を用いた半教師つき学習とそれに 関連したカーネル行列について述べる. その後, 第 4 節 でグラフ構造より導かれたカーネル行列を SVM に用 い半教師つき学習を行う定式化について述べる. また, 第 5 節では多クラス SVM への拡張を行う. 第 6 節で は, 手書き文字データ MNIST を用いた数値実験の結果 について報告する.

2

SVM

による判別

ラベル付けされた学習用データが次のように与えら れていると仮定する. {(x1, y1), (x2, y2), . . . , (xl, yl)} , (1) ただし,xj ∈ Rnは属性数が n 個の j 番目のデータ, ま た yjはデータxjに与えられたクラスラベルで, +1 あ るいは−1 の 2 値をとるものとする. SVMでの判別は, 高次元の特徴空間F に非線形変換 したデータに対して行われる. 元のデータx ∈ Rnを 特徴空間F に射影する関数を φ(·) : RN → F と表記 し, さらに, 表記を簡単にするため φ(xj) ∈ F を単に φjと表す. SVM では, 法線ベクトルw ∈ F および実数 b ∈ R により定まる線形の判別関数: f (φ(x)) =  w , φ(x)  + b (2) を仮定し, データxjとそのラベル yjに関して yj = 1ならば w , φ(xj) + b > 0 yj=−1 ならば  w , φ(xj) + b < 0 (3) となるw, b を求めることを考える. 一般的には, (3) が 常に成立するとは限らないことから, スラック変数 ξj を導入し次の二次計画問題:      最小化 1 2 w , w  + C l  j=1 ξj 制約 yj( w , φj + b) + ξj ≥ 1, j = 1, 2, . . . , l, ξj ≥ 0, j = 1, 2, . . . , l, (4) の最適化を考える. ただし, C はあらかじめ定められた 正のパラメータである. ほとんどの場合, この問題 (4) は, その双対問題を解く ことで最適化される. 今, l 個の双対変数 α1, α2,· · · , αl を導入すれば, 問題 (4) の双対問題は        最大化 −1 2 l  i=1 l  j=1 Kijyiyjαiαj+ l  j=1 αj 制約 l  j=1 yjαj = 0, 0≤ αj ≤ C, j = 1, 2, . . . , l, (5) と表現される. ただし,Kijは φiと φjの特徴空間F に おける内積 φi, φj の値である. 問題 (5) を見れば, 双 対問題を定めるためには, F での内積の値のみが必要 であり, 特徴空間の元 φi∈ F を φ(·) を陽に求める必要 がないことが分かる. 元の空間の 2 点x と xから直接内積 φ(x) , φ(x) を求めるカーネル関数K (·, ·) : RN× RN → R がいく つか知られており, 例えば, d を自然数, また σ を実数 のパラメータとして, polynomial カーネル K (x, x_{) =}_xT_{x+ 1}d_, や, RBF カーネル K (x, x_{) = exp}₋ x − x 2 σ2  , などがよく用いられる. より一般的には, K を実対称 行列で, 各要素がカーネル関数で Kij = K (xi,xj)と なるとき, 行列 K が半正定値行列となるK (·, ·) はカー ネル関数である. SVMの定式化には, いくつかのバリエーションが提 案されている. まず, SVM の最小化問題を一般的に    最小化 1 2 w , w  + C l  j=1 c(φj, yj, f (φj)) (6) と表すことにする. ここで, c(·) は loss 関数と呼ばれ, 例えば, 問題 (4) は, c(·) に hinge loss 関数: c(φj, yj, f (φj)) = max{0, 1 − yjf (φj)} (7) を用いた場合と考えることができる. 特に, この場合の 定式化は 1 ノルム SVM と呼ばれる.

loss関数として, 上の hinge loss 関数以外のものと して, 例えば, hinge loss 関数を平方した c(φj, yj, f (φj)) = max{0, 1 − yjf (φj)} 2 (8) を用いることで, より単純な双対問題として扱うことが 可能である. なお, この場合の定式化は 2 ノルム SVM と呼ばれる. さらに, 単純な square loss: c(φj, yj, f (φj)) ={1 − yjf (φj)} 2 を用いれば, これは単なる回帰と同値で制約のない関 数の最小化問題として扱うことが可能である. 一方,

Mangasarian等 [7] は loss 関数 (8) に加えて, 線形判別 関数 (2) の bias 項 b の平方を最小化する次の問題:     最小化 1 2 w , w  + b 2 +C l  j=1 max{0, 1 − yjf (φj)}2 (9) を考え, implicit Lagrangian [8] を用いることで制約の 無い最小化問題へと帰着できることを示している. さ らに, 次の logistic loss 関数 c(φj, yj, f (φj)) = ln{1 + exp(−yjf (φj))} を用いたカーネル logistic regression [11] も提案されて いる. しかし, この場合は問題 (5) のように単純な双対 問題を得ることができないため, このままでは大規模な 判別問題へ適応することは困難と思われる.

3

グラフ構造を用いた半教師つき学

習

3.1

半教師つき学習

この節では, 式 (1) で与えた l 個のラベル付けされた データに加えて, ラベルの与えられていない u 個のデー タxj ∈ Rn (j = l + 1, l + 2, . . . , l + u) を用い判別を 行う半教師つき学習を考える. なお, 以降ではデータの 総数を M = l + u と記すことにする. まず, ノード集合 V および枝集合 E からなる重みつ きグラフ G(V, E) 用いて, データ間の関連性を表現す る. V の各要素は与えられた M 個のデータに対応し, またデータ i とデータ j の類似性の程度を表す非負の 実数 bij ≥ 0 を枝 (i, j) ∈ E の重さとする. すなわち, データが類似しているほど大きな重みを付与する. 枝の重み bij の定め方にはいくつかの方法が提案さ れている. 例えば, あらかじめ正のパラメータ σ を定 め, 全てのノード間 i, j∈ V において bij = exp  − xi− xj 2/σ2  と指数関数を用いて重さを与える方法や, あるいは, 適当 なデータ間の距離を元に k 最近傍グラフを構成し, ノー ド i, j 間に枝があれば bij = 1, 枝が無ければ bij = 0 とする, などである. なお以降では, 簡単のためグラフ G(V, E)は連結であると仮定する. 重み bijを i, j 要素とする M 次の対称行列を B, ま た, B の第 i 行の和を対角要素とする M 次の対角行列 を D とする. このとき, L = D− B と定められる行列 L をラプラシアン行列 [3] と呼ぶ. Zhu 等 [12] はグラフの各ノード i = 1, 2, . . . , M に 対応する変数 fiを導入し, エネルギー関数と呼ばれる 次の二次関数 E(f) =1 2f T_{Lf (10)} を用いて判別を行った. ここで,f = (f1, f2, . . . , fM) T ∈ RM は M 次の変数ベクトルである. 彼等は, ラベルが 付与されているノード j = 1, 2, . . . , l に対して変数 fj を 0− 1 の値のラベル ˆyj = (yj+ 1)/2に固定した上で, エネルギー関数 (10) を最小化する次の問題:    最小化 E(f) = 1 2f T Lf, 制約 fj= ˆyj, j = 1, 2, . . . , l (11) を解き, ラベルの与えられていない変数 fj (j = l + 1, l + 2, . . . , M を定めラベルを判定することを提案し ている. エネルギー関数は, E(f) =1 2 M  i=1 M  j=1 bij(fi− fj) 2 と書き換えられることから, 問題 (11) を解けば, bijの 大きな類似しているデータには, 値の等しいラベルが付 与されることが期待される. また, Belkin [1] 等は, 次の最小化化問題    最小化 1 2f T Lf +C 2 l  j=1 (fj− ˆyj) 2 (12) を解き, 未ラベルの変数を定めることを提案している. なお, これらの問題 (11), (12) はいずれも制約の無い 最小化問題であり, 線形方程式を解くことで最適解を求 めることが可能である. 例えば, 問題 (12) の場合であ れば, ˆ yT = (ˆy1, ˆy2, . . . , ˆyl, 0, . . . , 0)∈ RM, とし, また Ilを M 次の対角行列で Il= diag(1, . . . , 1_ l , 0, . . . , 0   u ) と定めれば, 最適解は f∗=  Il+ 1 CL −1 ˆ y (13) と求められる.

3.2

グラフラプラシアンとカーネル行列

ラプラシアン行列 L を用いてさまざまのカーネル行 列を構成する方法が提案されている. Fouss等 [4] は, ラプラシアン行列 L の一般化逆行列 L+ をカーネル行列として用いることを提案してる. e を要素が全て 1 のベクトルとすれば, Le = 0 となることから, ラプラシアン行列 L は正則とはなら ない. しかし, 対応したグラフ G が連結であればその 一般化逆行列は L+=  L−ee T M −1 +ee T M , (14) と計算ができることが知られている. また, L が半正定 値行列 [3] であることから L+も半正定値行列となり, よってカーネル行列として用いることが可能である. 特 に, L+_{は commute time カーネル行列 [4] と呼ばれる.} 今, L の固有値と固有ベクトルをそれぞれ, λ1, λ2, . . . , λM およびv1,v2, . . . ,vM ∈ RM とする. L は L = M  i=1 λi(vivTi ) と固有値分解することが可能である. このとき, 固有値 に 0 がある場合も考慮して, その逆数を λ+ =  λ−1 if λ= 0 0 if λ = 0 と記せば, L の一般化逆行列は L+= M  i=1 λ+_i (vivTi) (15) と構成することも可能である. 式 (15) をさまざまに変更することで, 異なるカーネ ル行列が構成可能である. 例えば, 正則化ラプラシアン カーネル行列 [13] は, t を正のパラメータとして M  i=1 (1 + tλi)−1vivTi = (I + tL)−1, (16) と定められる. さらに, 固有値を基準化したラプラシア ン行列 ˜ L≡ D−1/2LD−1/2 に対して同様の変形を行った I + t ˜L ₋₁ (17) や exp(−σ 2 ˜ L) (18) などもカーネルとして用いることが可能である [9].

4

SVM

を用いた半教師つき学習

この節では, (6) で示した SVM の定式化に, (14) や (16)などのグラフ構造を用いて構成されるカーネル行 列を用いることで, 半教師つき学習を行うことを考える. 一般的には, 式 (5) に示したような双対問題を作り, その中でカーネル行列を扱いw などが定められている. しかし, 例えば, 式 (16) のカーネル行列の場合には, ま ず逆行列の計算を行いカーネル行列を算出する必要が ある. データの個数がカーネル行列のサイズであるこ とを考えると, データ数が数万を超えるような大規模 な問題では, カーネル行列自体を陽に計算することが 困難で, 双対問題の枠組みで扱うことができない. そこ で, 以降の節では, 主問題の定式化を用いることで, 大 規模な問題に対しても実行可能な定式化を導出する.

4.1

ラプラシアンカーネル

この節では, hinge losss を用いた標準的な定式化 (4) において, 正則化ラプラシアンカーネル行列 (16) を用 いた半教師つき学習について考える. なお, ここでは簡 単のため, 線形関数 (2) の bias 項 (b) を取り除き f (φ(x)) =  w , φ(x)  (19) とした問題について考えることにする. まず, M 個の変数α = (α1,· · · , αM)T を導入し, 求 めたい線形関数 (19) の係数w ∈ F が M 個のデータ の線形結合で表現される, すなわち w = M  j=1 αjφj (20) と考える. この式 (20) を問題 (4) に代入すると        最小化 1 2  _M  j=1 αjφj, M  j=1 αjφj  + C l  j=1 ξj 制約 yj  _M  i=1 αiφi, φj  + ξj≥ 1, j = 1, 2, . . . , l, ξj ≥ 0, j = 1, 2, . . . , l (21) が得られる. 今, K を M× M のカーネル行列, すなわち K = (I + tL)−1 とする. K の i− j 要素は, データ φi と φj の内積  φi, φj であることかから  _M  j=1 αjφj, M  j=1 αjφj  =αTKα

と書き換えることが可能である. このような変形を制 約式に対しても行えば, 問題 (21) は      最小化 1 2α T_{Kα + C} l  j=1 ξj 制約 yj(Kα)_j+ ξj≥ 1, j = 1, 2, . . . , l, ξj ≥ 0, j = 1, 2, . . . , l, (22) と書きかえられる. ただし, (Kα)j はベクトル Kα ∈ RM の j 番目の要素を表すものとする. このような問題の書き換えは常に可能であるが, 問題 (22)は目的関数と制約式の双方にカーネル行列 K を含 む形となっており, 特に K のサイズが大きな場合には, 最適化を容易に行うことはできない. しかし, 例えば正則化ラプラシアンカーネル行列 (16) のように K が正則の場合には, 新たに M 個の変数β = (β1, . . . , βM)T ∈ RM,を導入し, β ≡ Kα (23) と定義すれば, αT_{Kα = β}T K−1β と変形が可能である. ゆえに, 問題 (22) は      最小化 1 2β T K−1β + C l  j=1 ξj 制約 yjβj+ ξj ≥ 1, j = 1, 2, . . . , l, ξj≥ 0, j = 1, 2, . . . , l. (24) と書き換えることが可能である. この問題の最適解を β∗ _{= (β}∗ 1, β2∗, . . . , β∗M)T ∈ R M とすれば, ラベルが未 知のデータ j = l + 1, . . . , M に対して, β∗j > 0であれ ば ˜yj = 1,そうでないのであれば, ˜yj =−1 と判別を 行うこととなる. ここで, カーネル行列 K を正則化ラプラシアンカー ネル行列 (16) とすれば, その逆行列が K−1= (I + tL) となることを用いると次の定理を得る. 定理 1 問題 (24) の最適解を (β∗,ξ∗)とする. K を正 則化ラプラシアンカーネル行列 (16) とすれば, −1 ≤ β∗ j ≤ 1, ∀j = 1, 2, . . . , M. となる最適解が存在する. 証明 Karush–Kuhn–Tucker (KKT) 条件より, 非負 の Lagrangian 乗数 vj (j = 1, . . . , l)が存在し, 最適解 (β∗,ξ∗)は ((I + tL)β∗)_j =  yjvj, j = 1, 2, . . . , l, 0, j = l + 1, l + 2, . . . , M, (25) を満たす. また, 相補性条件より vj  yjβj∗+ ξj∗− 1  = 0, ∀j = 1, . . . , l となる. なお, 行列 L の定義から式 (25) の左辺は ((I + tL)β∗)_j= β∗_j + t M  i=1 bji  β_j∗− β_i∗ と変形できる. 以下では, βj∗≤ 1, (j = 1, 2, . . . , M) であることを背 理法により示す. そこで, β_k∗≡ maxβ∗_j | j = 1, 2, . . . , M> 1 となる添え字 k が存在したと仮定する. このとき ((I + tL)β∗)_k= β∗_k+ t M  i=1 bki(βk∗− β∗i) > 1 (26) が成り立つことより, 式 (25) を満たすためには添え字 kは k≤ l でなくてはならない. また, 同時に yk= 1で ある. さらに ξk∗≥ 0 であるから ykβ∗k+ ξk∗− 1 > 0 と厳密に正である. ここで, 相補性条件を使えば, この 不等式に対応する Lagrangian 乗数は vk = 0となり, (25)より, ((I + tL)β∗)_k= 0 である. これは矛盾である. 同様にして,−1 ≤ βj∗ であることも証明できる. 2 問題 (24) は, hinge loss 関数を用いたものであるか ら, 最適解では ξ∗_j = max0, 1− yjβj∗  , ∀j = 1, 2, . . . , l が満たされている. 定理 1 を用いれば, 最適解では ξj = 1− yjβj, ∀j = 1, 2, . . . , l (27) が成立することが分かる. そこで, この式 (27) を問題 (24) に代入すれば変数 ξj が消去でき, 次の問題:     最小化 1 2β T (I + tL)β + C l  j=1 (1− yjβj) 制約 yjβj ≤ 1, j = 1, 2, . . . , l (28) を得る. さらに, 新たな変数u = (u1, u2, . . . , uM)∈ RM,を 導入し uj ≡  1− yjβj, j = 1, 2, . . . , l, βj, j = l + 1, l + 2, . . . , M.

と変数変換を施せば, 問題 (28) は非負制約のみの二次 計画問題に書き換えることが可能である. すなわち, M 次の 0− 1 ベクトル el_{≡ (1, . . . , 1}   l , 0, . . . , 0   u )T ∈ RM および, M× M の対角行列 Y ≡ diag(y_1, . . . , yl l ,−1, . . . , −1   u )∈ RM×M として Q≡ I + tY LY, および c ≡ ((C − 1)I − tY LY ) el を定義すれば, 問題 (28) は,    最小化 1 2u T_{Qu + c}T_u 制約 uj ≥ 0, j = 1, 2, . . . , l, (29) と変形される. この問題のように, 変数の非負制約のみ からなる二次計画問題は, implicit Lagrangian [8] を用 いることで制約の無い二次計画問題へと帰着すること が可能である [7].

2ノルム SVM の利用 loss関数として hinge loss 関 数を平方した (8) を用いた場合, SVM は     最小化 1 2 w , w  + C l  j=1 ξ_j2 制約 yj w , φj + ξj ≥ 1, j = 1, 2, . . . , l, (30) と定式化される. 変数 ξjの平方を考えたことで, 問題 (4)と比べると非負制約が不要になる. したがって, 式 (23)と同様に変数β を導入すれば,     最小化 1 2β T_{K−1β + C} l  j=1 ξ2_j 制約 yjβj+ ξj ≥ 1, j = 1, 2, . . . , l (31) と書き換えることが可能である. この場合も, カーネル行列として正則化ラプラシアン カーネル行列 (16) を用いると, 定理 1 と同様な性質を 導くことができ, 最適解では, ξ_j2= (1− yjβj)2= (yj− βj)2, ∀j = 1, 2, . . . , l が成立する. これを代入して ξj を消去すれば, (31) は,    最小化 1 2β T (I + tL)β + C l  j=1 (yj− βj) 2 (32) となり, 制約の無い二次関数最小化問題へと帰着される.

4.2

他の手法との関連

カーネル行列として commute time カーネル行列 (14) を用いた場合も, 前節とほぼ同様な変形が可能である. しかし, L+ _{が正則でないため, 式 (23) のような変数変} 換が行えない. そこで, 変数β を β ≡  L+−ee T M  α と定義すれば同様の変換が可能となる. Le = L+_{e = 0} であることを用いると, 4.1 節で述べた方法と同様な変 形でき, hinge loss 関数を用いた 1 ノルムの定式化 (6) からは次の最小化問題:     最小化 1 2β T Lβ + C l  j=1 (1− yjβj) 制約 yjβj ≤ 1, j = 1, 2, . . . , l (33) が得られ, また 2 ノルムの定式化からは, 制約の無い最 小化問題:    最小化 1 2β T_{Lβ + C} l  j=1 (1− yjβj) 2 (34) が得られる. 特にこの問題で, fj = βj+ 1 2 , j = 1, 2, . . . , M と変数変換をすれば, 問題 (12) と同値な問題であるこ とが分かる. また, これらの問題でパラメータ C を十分大きくす れば, 最適解として β_j∗= yj, j = 1, 2, . . . , l となるものが得られ, これは問題 (11) で示したエネル ギー関数の最小化と同値である.

5

多クラス

SVM

への拡張

前節では, 2 クラスの SVM に対してグラフカーネル を用いた半教師つき学習アルゴリズムを構築した. こ こで行った枠組みは, 多クラスの SVM(MSVM) に容易 に拡張可能である.

5.1

多クラス SVM

この節では, 学習データが h のクラスに分類されて いると仮定する. すなわち, データ φjにラベル yj ∈ {1, . . . , h} が付与されていると考える.

それぞれのクラス i = 1, 2, . . . , h に対しベクトル wi _{∈ F を考え, 線形関数 f}i_{(φ(x)) =}_wi_{, φ(x)} が クラス i のデータを他の h− 1 個のクラスから分離す るようwi_{を定めることを考える. すなわち全てのデー} タ φjで次の不等式  wyj_{, φ} j ≥  wi_{, φ} j  + 1, ∀i ∈ {1, 2, . . . , h} \ {yj} (35) を満たすw1_,w2_{, . . . ,w}h_{を定めることである.} しかし, 一般には (35) を満たすwi _{が必ずしも存在} するとは限らない. そのため, 2 クラスの場合と同様, 誤分類が行われた場合のペナルティーとして loss 関数 を導入し最適化問題を定義する. 本研究では, 最適化が 容易に実行できることを考慮して, hinge loss を平方し た関数 c(φj, yj,wyj,wi) = max0, 1− wyj_{, φ} j −  wi_{, φ} j 2 (36) を用いて, 次の最適化問題を考える.      最小化 1 2 h  i=1  wi_{, w}i +C l  j=1  i=yj c(φj, yj,wyj,wi). (37)

5.2

半教師つき多クラス判別

問題 (37) をラベル付けされていない u 個のデータ φl+1, φl+2, . . . , φl+u を考慮した半教師つき学習へと拡 張する. 2クラスの場合と同様に, ベクトルwi_{∈ F は全ての} データ φj (j = 1, 2, . . . , M )の線形結合で表現される と考える. すなわち, 各クラス i に関して M 次元の変 数ベクトル αi₌_αi 1, α i 2, . . . , α i M T ∈ RM_{, i = 1, 2, . . . , h} を導入し, wi₌ M  j=1 αi_jφj, i = 1, 2, . . . , h (38) とする. ここで, カーネル行列を K とすれば,  wi_,wi_=αiT_Kαi_{, i = 1, 2, . . . , h,} となり, また loss 関数も変数αi_{で表現でき,} max  0, 1− (Kαyj₎ j−  Kαi_j 2 となる. さらに, K を (16) あるいは (17) で示されるような 正則なカーネル行列とすれば, 新たな変数 βi =β₁i, βi₂, . . . , β_Mi T ∈ RM, i = 1, 2, . . . , h を使いβi= Kαi _{と変数変換をすれば, 問題 (37) は}      最小化 1 2 h  i=1 βiT_K−1βi +C l  j=1  i=y_j max0, 1− (β_jyj − β_ji)2 (39) と書き換えることが可能となる. なお, この問題の最適 解をβ1∗,β2∗, . . . ,βh∗とすれば, ラベルが未知のデー タxjのクラスは, argmax  β_ji∗|i = 1, 2, . . . , h  と求められることとなる. 3節で示したように, (16) や (17) のカーネル行列は その逆行列が陽に与えられている. さらに, ラプラシア ン行列 L を k 最近傍グラフを用いて構成した場合には, 問題 (39) は非常にスパースな最適化問題である. さらに, 問題 (39) の目的関数を F (β1,β2, . . . ,βh)と し, また, 表記を簡単にするため, sij≡ max{0, 1 − (β yj j − β i j)} と記せば, loss 関数 (36) が微分可能であることから, 関 数 F (·) は ∂F (β1,β2, . . . ,βh) ∂βi j = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (K−1βi)j+ 2Csij if j = 1, 2, . . . , l, i= yj, (K−1βi)j− 2C  k_=yjs k j if j = 1, 2, . . . , l, i = yj, (K−1βi)j if j = l + 1, l + 2, . . . , m (40) と微分を求めることが可能である. 行列 K−1がスパー スな行列であれば, K−1βiは高速に計算可能であり, こ のような問題に対しては, 共役勾配法 [2] を用いた最適 化が有効であると考えられる.

6

数値実験

手書き文字データ MNIST[6] を用いて数値実験を行っ た. このデータセットは, 0 から 9 までの手書き数字を

表 1: MNIST データを用いた比較結果 ラベル付データの数 100 200 500 1000 正解率 提案手法 (32) 0.953 0.966 0.975 0.978 Zhu等 [12] 0.801 0.928 0.972 0.979 反復数 提案手法 (32) 20.7 21.0 21.0 21.0 Zhu等 [12] 110.5 96.4 71.8 53.9 CPU秒 提案手法 (32) 1.62 1.65 1.64 1.64 Zhu等 [12] 12.1 10.6 7.83 5.85 28× 28 ピクセルのイメージ画像として取り込んだも ので, データ数は 70,000 である. したがって, 各データ xj (j = 1, 2, . . . , 70000)は 28× 28 = 784 次元のベク トルとして表現されている. データxi,xjの距離をそ のなす角の余弦 cos θ = x T i xj xi xj とし, k 最近傍グラフを構築した. 枝の重みは全て 1 と し, ラプラシアン行列を求め実験に使用した. なお, 以 降での述べる結果は k = 5 の最近傍グラフを用いた. こ れは, グラフが連結となる最小の近傍数である. 実験は, 偶数の文字のデータをクラス +1, 奇数の文字のデータ をクラス−1 とした 2 クラスの判別を行った. なお, ク ラス毎のデータ数はほぼ等しい. ラベルを与えるデータをランダムにサンプリングし, 残りの全てのデータに対する判別精度を計算した. 実 験は異なるサンプリングで 10 回繰り返し, それらの 平均値を報告する. 計算は Pentium4 (3.8Ghz, 1.0GB RAM)で行った. 表 1 は, 提案する手法 (32) と Zhu 等 [12] による問題 (11)を解いて得られた結果を比較したものである. な お, 問題 (32) のパラメータは t = 2.0, C = 1.0 と設定し た. どちらの問題も, 共役勾配法を用いて計算を行った. この表から, 提案手法は正解率, 計算時間とも問題 (11)を用いた場合より優れていることが分かる. ラベ ル付きデータの数が増加するにつれ, 両者の精度の差 は小さくなるが, 計算時間では数倍の開きがある. これ は, 行列 L が正則で無いため, 問題 (11) では, 条件数の 悪い行列を扱わなくてはならいためと考えられる.

7

おわりに

本研究では, ラプラシアン行列をもとに構成された カーネル行列を用いた SVM において, 半教師つき学習 を行う方法について述べた. 特に k 最近傍グラフのラプラシアン行列から作られた 正則化ラプラシアンカーネル行列, あるいは commute time カーネル行列を用いた場合には, 適当な変数変換 を行うことで, SVM の主問題がスパースな最適化問題 へと帰着されることを示した. 共役勾配法用いたアル ゴリズムを実行した結果, データ数が数万を超える問題 に対しても高速に学習が可能であることが確認された.

参考文献

[1] M. Belkin, I. Matveeva, and P. Niyogi. Regulariza-tion and semi-supervised learning on large graphs. In

COLT, 2004.

[2] D. Bertsekas, editor. Nonlinear Programming.

Athena Scientific, 1999.

[3] F. R. Chung. Spectral Graph Theory. American Mathematical Society, 1997.

[4] F. Fouss, A. Pirotte, and M. Saerens. A novel way of computing dissimilarities between nodes of a graph, with application to collaborative filtering. In 15th

European Conference on Machine Learning (ECML 2004); Proceedings of the Workshop on Statistical Approaches for Web Mining (SAWM), pages 26–37,

2004.

[5] R. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In ICML, 2002.

[6] Y. LeCun, L. D. Jackel, L. Bottou, A. Brunot, C. Cortes, J. S. Denker, H. Drucker, I. Guyon, U. A. M¨uller, E. S¨ackinger, P. Simard, and V. Vapnik. Comparison of learning algorithms for handwritten digit recognition. In F. Fogelman-Souli´e and P. Gal-linari, editors, Proceedings ICANN’95 – International

Conference on Artificial Neural Networks, pages 53–

60. Nanterre, France, 1995.

[7] O. L. Mangasarian and D. R. Musicant. Lagrangian support vector machines. J. Mach. Learn. Res.,

1(3):161–177, 2001.

[8] O. L. Mangasarian and M. V. Solodov. Non-linear complementarity as unconstrained and con-strained minimization. Math. Programming, 62(2,

Ser. B):277–297, 1993.

[9] A. Smola and I. Kondor. Kernels and regularization on graphs. In B. Sch¨olkopf and M. Warmuth, editors,

Proceedings of the Annual Conference on Computa-tional Learning Theory, Lecture Notes in Computer

Science. Springer, 2003.

[10] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Sch¨olkopf. Learning with local and global con-sistency. Advances in Neural Information Processing

Systems, 16:321–328, 2004.

[11] J. Zhu and T. Hastie. Kernel logistic regression and the import vector machine. In NIPS, pages 1081– 1088, 2001.

[12] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and har-monic functions. In ICML, pages 912–919, 2003. [13] X. Zhu, J. Lafferty, and Z. Ghahramani.

Semi-supervised learning: From Gaussian fields to Gaus-sian processes. Technical Report CMU-CS-03-175, Carnegie Mellon University, 2003.