平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野大規模スパースモデルの最適化におけるセーフスクリーニング学籍番号 24413515 氏名小川晃平指導教員名竹内一郎准教授 1 はじめにに分割すると、最適化問題 (1) における最適性条件は以下のように書ける: 昨今のビックデータ時代において大規模データに対するスパースモデルが実用的に有用であるとされている. スパースモデルではそれを表現するために要不要であるデータが区別され、新たなデータの評価やモデルの保存を効率的に行える. そのような特性がある一方、スパースモデルの学習には入力である大規模なデータをすべて用いる必要があり、しばしば大きな計算的資源的コストがかかってしまう. その問題に対して、最近スクリーニングと呼ばれる技術が注目されている. 本論文では入力データのうち、不必要である特徴の一部を学習の事前に検出する従来のスクリーニング手法 [1] に対して、不必要な標本の一部を検出する手法を提案する [2, 3]. これらのスクリーニング手法によって、スパースモデルの学習コストの削減が見込まれる. 2 サポートベクトルマシン学習データとして {(xi , yi )}i∈Nn が与えられているとする. ここで、xi ∈ X ⊆ Rd , yi ∈ {−1, +1}、および、Nn := {1, 2, . . . , n} である. 本論文では以下の様なバイアス項のない分類モデルを考える: f (x) = w⊤ x. 本論文では以下の最適化問題を解くことにより、SVM 分類器を学習することを目的とする: ∑ 1 ∗ w[C] := arg min ∥w∥2 + C [1 − yi f (xi )]+ (1) d w∈R 2 i∈Nn ここで、C > 0 は正則化係数、∥ · ∥ はユークリッドノルム、[1 − yi f (xi )]+ := max(0, 1 − yi f (xi )) はヒンジ損失と呼ばれる損失関数である. 最適なラグランジュ未定乗数 α ∈ [0, C]n を用いると、SVM の分類器は、 ∑ αj yj K(xi , xj ) f (xi ) = j∈Nn と表される. 以下、最適解におけるラグランジュ未定乗数を α∗ と表す. n 個の学習インスタンスを以下の 3 種類のインデックス集合 R := {i ∈ Nn |yi f (xi ) > 1}, E := {i ∈ Nn |yi f (xi ) = 1}, L := {i ∈ Nn |yi f (xi ) < 1} i∈R ⇒ αi = 0, (2a) i∈E ⇒ αi ∈ [0, C], (2b) i∈L ⇒ αi = C. (2c) SVM における解のスパース性とは、最適な双対変数 α の一部が零値を取る性質のことを指す. 現在提案されている様々な SVM の最適化手法はこの解のスパース性を用いることで、高速な学習を行うものが多い. そういった SVM の最適化手法では主に各インスタンスが最適解においてどのインデックス集合に属するかを探索することに多くの計算資源を費やしている. ここでもし R に含まれるインスタンスを学習の事前に知ることが出来れば、それらに対応する αi を 0 に固定し、インスタンス i を削除することで最適化問題のスケールを小さくすることが出来る. これにより、学習の高速化が見込まれる. 以下ではある仮定の下、αi = 0 となるインスタンス (標本) の一部を学習前に安全に同定するための基準 (ルール) を提案する. ここで「安全」とは、αi = 0 と予測されたインスタンスの集合が R、の部分集合となるという意味である. 本論文ではこのような同定を行うためのルールを (標本) スクリーニングルールと呼ぶ. 標本スクリーニングルール 3 本節では SVM における安全なスクリーニングの為のルールを具体的に構築していく. 3.1 基本方針 ∗ ある正則化係数 C における最適解 w[C] を含む部分 ∗ 領域 ΘC (∋ w[C] ) が得られているとする. この時、 ⊤ ∗ min yi x⊤ i w ≥ 1 ⇒ yi xi w[C] > 1 ⇒ αi = 0 w∈ΘC (3) が成り立つ. この事実より、yi x⊤ i w の下限値が 1 以上 ∗ であるインスタンスに関しては、最適解 w[C] を用いることなく (2a) を満たすと知ることが出来る. 3.2 Ball Test ΘC が超球の場合、(3) において yi x⊤ i w の下限値を求める問題はただ一つの二次制約を持つ最適化問題に帰着され、その解は閉じた形で求まる. 平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野補題 1 (Ball Test) ΘC が中心を m ∈ Rd に持つ半径 r ∈ R の超球であるとする. つまり、ΘC = {w| ∥w − m∥ ≤ r} である時、 ℓi := min yi x⊤ i w = yi x⊤ i m − r∥xi ∥ w∈ΘC が成り立ち、ℓi > 1 ⇒ αi = 0 である. 補題 1 は幾何的に解釈することが出来る (図 1). 解空間における超平面 P (z) = {w|z ⊤ w = 1} と開半空間 H(z) = {w|z ⊤ w > 1} を考える. 部分領域 ΘC が P (yi xi ) と接することなく H(yi xi ) に含まれる場合、 ∗ w[C] も P (yi xi ) 上にないことが分かる. このため、(3) によって、インスタンス i がスクリーニングされることとなる. ΘC が超級の場合には、それが P (yi xi ) と接するか |y x⊤ m−1| i 否かを超球の中心と超平面の距離 i ∥x を超球の i∥ 半径 r と比較することで判定できる. つまり、 yi x⊤ i m−1 >r ∥xi ∥ (4) a1 > 0 の時、以下が成り立つ: ∗ (6) ∧ (7) ⇒ w[C] ∈ {w | ∥w − m∥ ≤ r } . (8) √ ただし、r := ∥m∥2 − a11 (c1 + c2 )、m := − 2a11 (b1 + b2 ) とした. これより、(6)、(7) を満たす a1 、b1 、b2 、c1 、c2 と対応する超球が ΘC として適用可能であることが分かる. ∗ ∗ 本研究では C0 < C における解 (w[C , ξ[C ) を用い 0] 0] ることで、2 つの仮定 (6)、(7) を満たし、それに対応する Ball Test を提案する. 4 数値例本節では 2 次元人工データに対して、提案した標本スクリーニングがどのような結果を示すかを調べる. 図 4 にその結果を記す. ここで、オレンジと青の領域で示した部分がスクリーニングによってモデルの構築に不要であると判断される. 実際にそれらを除いたデータによって学習した分類器 (実線) のマージン (点線) の外側に分布していることからその安全性が確認できる. が成り立つならば、ΘC は P (yi xi ) と接することなく、 H(yi xi ) に完全に含まれることが分かる. これは補題 1 と等価なスクリーニングルールとなる. 2 x2 1 0 -1 -2 -3 (a) スクリーニング成功例. (b) スクリーニング失敗例. -2 -1 0 x1 1 2 図 2: 2 次元人工データに対するスクリーニング. 図 1: Ball Test の幾何的解釈. 3.3 5 ΘC の構築 SVM において用いることのできる ΘC を具体的に構築するために (1) と等価な以下の問題を考える: 1 ∥w∥2 + Cξ 2 ∑ si (1 − yi f (xi )) ∀s ∈ {0, 1}n . s.t. ξ ≥ ∗ ∗ (w[C] , ξ[C] ) := arg min まとめ本論文では SVM を含む様々なスパースモデルに対する安全なスクリーニングルールについて考察し、計算機実験を通してその実用的有効性の検証とその発展研究の提案を行う. w,ξ∈R 参考文献 i∈Nn この最適化問題は Structural SVM と類似の問題であり、ある正則化係数 C に対して、(1) と全く等しい分類器が得られる. ここで、ある a1 , c1 , c2 ∈ R、b1 , b2 ∈ Rd において、以下の 2 つの仮定が満たされているとする. ∗ ∗ ∗ a1 ∥w[C] ∥2 + b⊤ 1 w[C] + c1 + ξ[C] ∗ b⊤ 2 w[C] + c2 ≤ 0, ≤ ∗ ξ[C] (6) (7) [1] L. El Ghaoui, V. Viallon, and T. Rabbani. safe feature elimination in sparse supervised learning. arXiv, 2012. [2] K. Ogawa, Y. Suzuki, and I. Takeuchi. Safe screening of non-support vectors in pathwise SVM computation. In Proceedings of the 30th International Conference on Machine Learning, 2013. [3] K. Ogawa, Y. Suzuki, S. Suzumura, and I. Takeuchi. Safe sample screening for support vector machines. arXiv:1401.6740, 2014.