ヤコビ核主成分分析

本小節では，ヤコビ核主成分分析[8]の枠組みであて はめ問題を核関数で表現する．

本稿では微分可能な核関数k(x,y) =F(x)^⊤F(y)及 びその微分であるヤコビ核（Jacobian kernel）[8]

k(x,y)

(m×1)

= ∂k(x,y)

∂x^⊤ =J_F(x)^⊤F(y)

を用いる．またaの存在範囲としてF_[d]の線型結合 a

(n×1) = ∑

p

α_[d]F_[d]= F

(n×D) α

(D×1)

だけを考える⁶．ここでD×D行列Kを (K)_ij =k(x_[i],x_[j]), K=

(K[1] · · · K[D]

)

で定義し，また，D×m行列K[d]を k_[i][j] = k(x_[i],x_[j]),

K[d] = (

k[d][1] · · · k[d][D]

)_⊤

で定義すると，

K[d] =F^⊤F_[d], K[d]=F^⊤J_F[d]

が成立する．このとき，式(9)について a^⊤

[ F_[d]F_[d]^⊤

]

a = α^⊤K[d]K^⊤[d]α, a^⊤G_[d]⁺a = α^⊤K[d]G⁻_[d]¹K^⊤[d]α

である．このとき式(9)は，写像F を含まない E^′(α) =

∑D

d=1

α^⊤K[d]K_[d]^⊤α

α^⊤K[d]G⁻_[d]¹K^⊤[d]α (10)

6赤穂[2]はa=Φα+

∑D

d=1

β^⊤_[d]

(∂F(x)

∂x )_⊤

[d]

の範囲でaを探索 し，そのためK(x,y) =JF(x)^⊤JF(y)も定義される．この核関数 を計量核（metric kernel）と名付ける．

となり，これを最小にするαを求めることとなる．

この最小化問題は式(9)の最小化と同様に解ける．

今，αの近似値αb が得られたとし，λ[d]及びΛを λ_[d] = αb^⊤K[d]G⁻_[d]¹K^⊤[d]αb,

Λ = diag{λ_[1], . . . , λ_[D]}, と定義すると，エネルギー関数は

E^′(α)≈α^⊤[

KΛ⁻¹K] α

と近似できるので，

α=UnitMinEigenVec[

KΛ⁻¹K] が成立する．よってアルゴリズムは以下の通り：

(1) 初期値{λ^[0]_[d]}^Dd=1を計算⁷．

(2) (a)及び(b)を収束するまで繰り返し：

(a) αb^[k+1]:=UnitMinEigenVec[K(Λ^[k])⁻¹K] (b) λ^[k+1]_[d] := (αb^[k+1])^⊤K[d]G⁻_[d]¹K^⊤[d](αb^[k+1]).

8 _{核関数と標本特徴空間}

先程のF = (F_[1] · · · F_[D])と特徴写像ϕ7→F(ϕ) を用いて標本特徴写像（sample feature map）を

K:ϕ7→ K(ϕ) =F^⊤F(ϕ)∈R^D

によって定義し，K(ϕ)の属する空間R^Dを標本特徴空 間（sample feature space）と呼ぶことにする．この とき，標本特徴写像のヤコビ行列がK=F^⊤J_F となる ことに注意すると，標本特徴空間でのSLS基準による 超平面α^⊤K(ϕ) = 0のあてはめ問題は式(10)の最小化 となる．

つまり，核関数を用いたあてはめ問題の書換えは，特 徴空間におけるあてはめ問題を標本特徴空間におけるあ てはめ問題へと書換えたことに対応することがわかる．

この書換えによってヒルベルト空間の問題を，標本数で 定まる有限次元の問題に帰着していることがカーネルト リックの一つの意味であると考えることができる．

なお，標本特徴空間における欧氏化が核関数を用いた 場合の欧氏化に対応することとなり，1階欧氏化である

r²= (α^⊤K[d])² α^⊤K[d]G⁻_[d]¹K^⊤[d]α

をスカラー行列で近似した r²= (α^⊤K[d])²

α^⊤{(DetK[d]G⁻_[d]¹K^⊤[d])^1/nI_D}α,

7この結果は核主成分分析[9]を行なったことに相当する．

が0階欧氏化となる．

これらを初期値としてレイリー商の和を最小とするα を求めれば良い．

9 おわりに

本稿では，一次元正規分布の集合に線型助変数で記述 される曲線群をダイバージェンスの和の近似値を最小化 するようにあてはめる手法を提案した．提案手法は近似 距離の最小化であるから，データの構造，すなわちあて はめるべき曲線族を決定する特徴写像F(ϕ)がデータに 相応しくない場合はあてはまりが悪くなるため，（非線 型PCA一般に言えることであるが）特徴写像の選び方 が重要な問題となる．

References

[1] S. Akaho, “Curve fitting that minimizes the mean square of perpendicular distances from sample points,”

In Proc. of SPIE93, Vision Geometry II, Vol.2060, (1993).

[2] 赤穂昭太郎, “入力空間でのマージンを最大化するサポー トベクタマシン,”信学論D-II, vol. J86-D-II, no. 7, pp.

934-942, 2003.

[3] S. Akaho, “The e-PCA and m-PCA: dimension reduc-tion by informareduc-tion geometry,” In Proc. of Int. Joint Conf. on Neural Networks (IJCNN2004), pp. 129-134, 2004.

[4] S. Amari, Differential Geometrical Methods in Statis-tics, Springer-Verlag, 1985.

[5] S. Amari, H. Nagaoka,Methods of Information Geom-etry, AMS and Oxford university press, 2000.

[6] W. Chojnacki, M. J. Brooks, A. van den Hengel and D. Gawley, “On the fitting of surfaces to data with covariances,” IEEE Trans. Patt. Anal. Mach. Intell., vol.22, no.11, pp.1294.1303, Nov. 2000.

[7] J. Fujiki and S. Akaho, “Small hypersphere fitting by Spherical Least Square,” In Proc. of ICONIP05, pp.439-444, (2005).

[8] 藤木淳，赤穂昭太郎, 入力空間での計量に基づいた核主 成分分析,信学技報, vol. 108, no. 327, pp. 69-74, Nov.

2008.

[9] B. Sch¨olkopf, A. Smola and K.-R. M¨uller, “Nonlinear component analysis as a kernel eigenvalue problem,”

Neural Computation, vol. 10, pp. 1299-1319, 1998.

[10] G. Taubin, “Estimation of planar curves, surfaces and, non-planar space curves defined by implicit equations with applications to edge and rage image segmenta-tion,” IEEE Trans. Patt. Anal. Mach. Intell., vol.13, no.11, pp.1115.1138, 1991.

[11] 津田宏治, “ヒルベルト空間における部分空間法,”電子情 報通信学会論文誌D-II, vol.J82-D-II, no.4, pp.592-599, Apr. 1999.

情報論的学習理論テクニカルレポート2009

Technical Report on Information-Based Induc-tion Sciences 2009 (IBIS2009)

行と列の生成による線形計画ブースティング

Linear Programming Boosting by Column and Row Generation

畑埜 晃平

^∗

Kohei Hatano

瀧本 英二

^†

Eiji Takimoto

Abstract: We propose a new boosting algorithm based on a linear programming formu-lation. Our algorithm can take advantage of the sparsity of the solution of the underlying optimization problem. In preliminary experiments, our algorithm outperforms a state-of-the-art LP solver and LPBoost especially when the solution is given by a small set of relevant hypotheses and support vectors.

Keywords: ブースティング，ソフトマージン，線形計画法

1 ^はじめに

近年，機械学習や関連分野において踈な分類器が注目 を集めている．例えばテキスト分類においては，特徴の サイズが１０万以上になるがそのうち重要な特徴はほん のごく一部となるとなることがある．このような場合，

踈な分類器は分類だけでなく特徴選択にも有効である．

踈な分類器を学習する主なアプローチとして，1 ソ フトマージン最適化問題として定式化する方法が挙げ られる．この問題では，マージンを大きくするような線 形分類器を重みの¹ノルムを正則化することによって 求める．マージンを用いた一般化誤差の研究によって，

このアプローチは分類において頑健であることが保証 されている[12, 5]．また，近年，¹ ソフトマージン最 適化問題は類似性指標を用いた学習にも応用されてい る[6, 8, 1, 14]．

¹ ソフトマージン最適化問題は線形計画問題である ため，シンプレックス法や内点法など標準的な最適化手 法によって解くことが可能である．しかし，特徴や例の サイズが１万以上の場合，多大な計算時間を要すること がある．

LPBoostは Demirizらによって提案されたよく知ら れたブースティング手法であり，¹ ソフトマージン最

∗九州大学大学院システム情報科学研究院情報学部門,〒819-0395 福岡市西区元岡744, tel. 092-802-3787, e-mail [email protected],

Department of Informatics, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Japan

†九州大学大学院システム情報科学研究院情報学部門, 〒 819-0395福岡市西区元岡744, tel. 092-802-3782, e-mail [email protected]

Department of Informatics, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Japan

適化問題を解くように設計されている [5]．LPBoostに おけるブースティングの繰り返し回数の上限は知られ ておらず，また，最悪時の繰り返し回数の下界は他の ブースティング手法よりも指数的に悪いことがわかって いるものの（後述），実際多くの場合十分に高速である

（LPBoostのハードマージン最適化問題に関する初期の 結果については[7]が知られている）．

定義域X 上 のm 個のラベル付き事例(x¹, y¹), . . . , (xm, ym) (xi∈ X,yi∈ {−1,+1})とn個の仮説（特徴）

h¹, . . . , hn(hj :X →[−1,+1])が与えられたとする. 直 接ソフトマージン最適化問題を解く代わりに，LPBoost は以下の操作を繰り返す：(1)各繰り返しtにおいて，事 例上の現在の分布dtに対して よい仮説 htを見つけ る．(2)仮説の集合を{h1, . . . , ht}に制限した 小さな ソフトマージン最適化問題を解くことによって次の分布 dt+1を構成する．最終的な仮説は過去に選ばれた仮説の 線形結合である，ただし，各仮説の係数は最後に解いた 小さな ソフトマージン最適化問題のラグランジュ乗数 によって与えられる．ここで，m×nの行列を考える. 行 列の各成分はuij=yih(xi) (i= 1, . . . , m, j= 1, . . . , n) とする. ここで，各行が事例に，各列が仮説に対応して いる．この行列は¹ ソフトマージン最適化問題の制約 行列を表しており，行列の視点から見れば，LPBoostは 列を生成しながら線形計画問題を繰り返し解いているこ とになる．実際，LPBoostはColumn Generation [11]

と呼ばれる最適化手法における古典的なテクニックを用 いた線形計画問題の解法と見なすこともできる.

しかしながら，LPBoost は問題の疎性を十分に活か しきれていない．実際，¹ソフトマージン最適化問題に は２種類の疎性がある．最初の疎性は仮説間に現れる．

すなわち，最適解においては， 重要な 仮説のみが非 負の係数を持つ．そして，もう１つの疎性は事例間に現 れる．より正確には，いくつかの 重要な 事例（しば しば サポートベクター とも呼ばれる）だけが，最 適解に影響し,それら以外の事例を取り除いても最適解 は変化しない．

本稿では，我々は仮説間と事例間の両方の疎性を利用 した新しいブースティング手法を提案する．本提案手法 Sparse LPBoostは行と列の両方を生成するアプローチ を取る．Sparse LPBoostは 重要そうな 列（仮説）

と行（事例）を選択しながら線形計画問題を繰り返し解 く．我々は，精度パラメータε >0 が与えられたとき，

Sparse LPBoostはソフトマージンが γ^∗−ε 以上で あるような仮説の線形結合を出力することを示す，ここ で，γ^∗ は最適なソフトマージンである．

本稿では，人工データおよび実データにおける準備的 な実験において，Sparse LPBoostが，従来手法である 線形計画ソルバや LPBoost よりも¹ ソフトマージン 最適化問題をより高速に解くことを示す．特に，事例や 仮説の総数が１万以上であるような大規模なデータにお いて，Sparse LPBoostは他の手法に比べて数倍以上の 高速化を達成した．

いくつかの関連研究を挙げておく．Warmuthらは En-tropy Regularized LPBoost [16]と呼ばれるLPBoostの 改良版を提案している．Entropy Regularized LPBoost も¹ ソフトマージン最適化問題を近似的に解くことが 可能であり，繰返し回数O(log(m/ν)/ε²)で実行できる ことが示されている．一方，LPBoostの繰り返し回数の 最悪時の下界はΩ(m)であることも知られている [15]．

この手法もLPBoostと同様，仮説間の疎性を利用して いる．

Mangasarian [10] や Sra [13] の手法は元の線形計画 問題を目的関数に２次の項を加えることにより，２次計 画問題に変換しそれぞれニュートン法やBregman法[3]

を用いて解を求める．彼らの手法は仮説間，事例間のい ずれの疎性も利用していない．

BradleyとMangasarian [2]は，本手法と同様に，元 の線形計画問題をより小さな問題に分解して解く手法を 提案している．しかしながら，この手法はLPBoostと 同様に行（仮説）だけを生成する．

以上，いずれの既存手法も，本手法のように事例間，

仮説間両方の疎性を利用しているわけではない．

2 ^準備

事例の空間を X とする．与えられた事例の集合を S= ((x1, y1), . . . ,(xm, ym))とする，ここで，各事例x

はX に属し，各ラベルyi は−1または+1の値をとる とする(i= 1, . . . , m)．仮説の集合をHとする，ただし，

各仮説 h∈ Hは事例の空間X から [−1,+1]への関数 とする．自然数kに対して，P^k をk次元の確率分布の 集合，つまり，P^k ={p∈[0,1]^k : _k

i=1pi= 1} とお く．仮説の（正規化された）重み付けα∈ Pⁿ に対する ラベル付き事例 (x, y)のマージンを yi_n

j=1αjhj(xi) と定義する．事例の集合上の分布d ∈ P^m に対する仮 説 h∈ Hのエッジを_m

i=1yidih(xi)と定義し，γd(h) と表記する．

2.1

1

ソフトマージン最適化問題

1 ソフトマージン最適化問題は以下のように定式化 される（例えば，[5, 16]など参照）．

ρ,maxα^,ξρ−1 ν

m i=1

ξi (1) sub.to yi

j

αjhj(xi)≥ρ−ξi (i= 1, . . . , m), α∈ Pⁿ, ξ≥0,

minγ,d γ (2) sub.to γd(hj) =

i

diyihj(xi)≤γ(j= 1, . . . , n), d≤ 1

ν1, d∈ P^m,

ただし主問題は(1)，双対問題は(2)でそれぞれ表され る．これらの問題は線形計画問題であり，主問題(1)の 最適解を(ρ^∗,α^∗,ξ^∗)，双対問題(2)の最適解を(γ^∗,d^∗) とすると，双対性により，ρ^∗−¹_νm

i=1ξ_i^∗=γ^∗となる ことが知られている．また，本稿ではそれぞれの目的関 数項をソフトマージンと呼ぶことにする．

注目すべき最適解の性質は疎ということである．KKT 条件により，最適解は次のような性質を満たす．

d^∗_i

⎛

⎝yi

j

α^∗_jhj(xi)−ρ^∗+ξ^∗_i

⎞

⎠= 0 (i= 1, . . . , m).

d^∗_i ≥0, yi

j

α^∗_jhj(xi)−ρ^∗+ξ_i^∗≥0 (i= 1, . . . , m). ξ^∗_i (1/ν−d^∗_i) = 0, ξ_i^∗≥0, d^∗_i ≤1/ν (i= 1, . . . , m).

この性質から，以下が成り立つ．

• yi

jα^∗_jhj(xi)> ρ^∗ ならば，d^∗_i = 0．

• 0< d^∗_i <1/νnならば，yi

jα^∗_jhj(xi) =ρ^∗．

• ξ^∗_i >0 ならば，d^∗_i = 1/ν.

特に，ラベル付き事例(xi, yi)の対応する重みdi が非 ゼロであるとき，(xi, yi)をサポートベクターと呼ぶ．こ こで，マージンがρ^∗ 未満（つまりξ_i^∗>0）であるよう なラベル付き事例は高々ν 個であることに注意してほ しい．なぜなら，そうでない場合，

id^∗_i >1 となり矛 盾するからである．

さらに，主問題の最適解も疎な性質をもつ．

• γd^∗(hj)< γ^∗ ならば，α^∗_j = 0.

対応する係数αj が正であるとき，仮説hj が重要であ ると言うことにする．以上から，最適解はサポートベク ターと重要な仮説のみを用いて再現することができるこ とがわかる．

3 ^{アルゴリズム}

本節では，双対問題(2)を解く手法について詳しく述 べる．

ドキュメント内 COE SITAIE- ICE IEICE IEICE IEICE IEICE (PRMU) () IEEE Committee Members of IT Society Japan ChapterIEEE Computational Intelligence Society Japan Chap (ページ 85-89)