今日のうちのチームの輪読会で"A Safe Screening Rule for Sparse Logistic Regression" (Wang et al., NIPS2014)を読んできた*1ので、その時の資料をついでにこちらにもupしておきます。
なお、この論文の筆者のGitHubとかに実装上がってないかなーと思って見に行ったんですが、
やっぱりまだないみたいですorz ええ、欲しかったらとりあえず自分でスクラッチから組めってことですね。。。ということでお後がよろしいようで。
概要
L1正則化ロジスティック回帰(これを筆者らは「スパースロジスティック回帰」と称している)は分類と特徴選択を同時にやれる手法として広く使われているが、高次元データへの適用には依然として大きな課題がある。そこでこの論文では高速かつ効率的に0に落ちる特徴量を同定するSlores (Sparse Logistic Regression Screening Rules)というものを提案する。Sloresの最大のメリットは、データセットを読み込む回数が1回で済むこと、そしてL1正則化ロジスティック回帰そのものの求解法とは独立して使えること。よって従来手法と自由に組み合わせてパフォーマンスを最大化できる。
1 Introduction
みんな大好きロジスティック回帰。だがその説明変数がスパースだったり、分類精度に意味のある説明変数が少ない場合にL1正則化をかけようとすると、これが大規模データだったりするとスケールしないことも多く課題となっていた。
そこで予め"inactive"な特徴量を見つけてスクリーニングして捨てるというやり方が複数編み出され、例えばSAFE [21], strong rules [22], DOME [26]などがある。しかしこれらの手法には非ゼロの特徴量を誤って削除してしまったり必要な評価基準の一般化が難しかったりと問題があった。
この論文では、新たに別のスクリーニングルールを考案した。今回考案した手法では、各々の特徴ベクトル同士の内積の上界を推定することによってinactiveな特徴量を検出し、未知の解である正則化ロジスティック回帰の"dual optimal solution"を推定する。この方法論では、特徴量同士の内積の上界の推定問題を制約付き凸問題として定式化し、閉形式解(解析的に得られる解のことですね)を得る。
2 Basics and Motivations
ここでは正則化ロジスティック回帰の基礎を振り返り、KKT条件のもとにスクリーニングルールを立てることとする。まず正則化ロジスティック回帰は、学習データサンプルと教師ラベル、全てのに対して、のもとで
(LRP)
ただし, は偏回帰係数及び切片、、そしては正則化パラメータ。ここではデータマトリクスで、行目はに当たり、列目はに当たる。
次に、およびに対してとする。この時(LRP)の双対問題は
(LRD)
と置ける。ここで求める解はとなる。
以下単純のため(LRD)を、およびを(LRP)、(LRD)の最適解とする。筆者らの文献[10]により、を適切に選べばどちらも陽的に解けることが示されている。ならびにをそれぞれの濃度(cardinality)として、
(1)
ただしこの時
(2)
文献[10]からであれば常にかつである。
]である時、(LRD)は唯一の最適解をもつ。(LRP)と(LRD)のKKT条件は以下のように書ける。
(3)
この(3)式から以下が言える。
(R1)
言い換えると、もしであれば、KKT条件は以下を示していることになる:最適解におけるの偏回帰係数は0に落ち、その場合j番目の特徴量カラムは(LRP)の最適化プロセスから「安全に」削除できる。
しかしながら、一般的にはなる場合はに関する知識がない限りは(R1)を適用することができない。この場合、を含む領域を推定することで対処する。結果として、もしであれば、(R1)により_j = 0 ]と結論付けることができる。これまた言い換えると、(R1)は以下のように緩和できる。
(R1')
この論文では(R1')をSlores構築の基礎と置く。これまでの論理展開から分かるように、が小さければ小さいほどバリバリ特徴量を落としていくことになり、を正確に求めるためには領域の推定がキーとなり、の上界を求めることが最重要だということになる。これは3節で凸最適化計画の解として得られることが示される。4節ではその解が陽に与えられることを示し、5節で具体的なSloresの導出を行う。
3 Estimating the Upper Bound via Solving a Convex Optimization Problem
この節ではの上界を推定する新たな枠組みを示す。以下、パラメータとそれに対応する双対最適解が与えられているとする。
まずの推定問題を制約付き凸最適化問題として定式化する。
双対関数に対し、となる。は対角行列であるため、 となる(Iは単位行列)。これによりは係数のもとで強く凸である(文献[16])。これは以下の補題に拠っている。
Lemma 1.
およびとすると、
a) (4)
b) の時、(4)式の不等式からは等号がなくなる(必ず大小の関係になる)
である時、ももに属することは容易に言える。それゆえ、Lemma 1はに関する知識のもとでの境界を与える上で有用なツールとなる。これは以下の定理に拠っている。
Theorem 2.
とすると、
a) (5)
b) の時、(5)式の不等式からは等号がなくなる
Theorem 2はが以下の半径を伴うを中心とする球体の中に存在することを示している。(6)
ここで改めてSloresが非常にゴリゴリ特徴量を削っていくタチのルールであることを思い出されたい。の上界はできるだけ精確に求める必要がある。このため、の可能領域であるにもさらに制約をかけることが望ましい。明らかに、
(7)
である(LRDのもとでが実現可能であるため)。一方、ここでなる集合をの"active set"と呼ぶことにする。このactive setに対して以下の補題が成り立つ。
Lemma 3.
LRDに対する最適解が与えられた場合、active set は ]の時、空集合にならない
であるため、Lemma 3に従っては空集合にはならない。ここで、なるおよび集合(8)
を取り上げる。この時となる。LRDのもとでが実現可能であるため、は以下を満たす。
(9)
結果として、Theorem 2, (7), (9)式からが以下の集合に含まれることが示される。
であるため、が言える。ゆえに、(R1')は以下の上界
(UBP)
がより小さければ、でありはLRPから削除できると結論付けられる。
4 Solving the Convex Optimization Problem (UBP)
この節では今までちょくちょく取り上げてきた例の凸最適化計画(何故か上界問題=UBPと略しているので注意)がラグランジュの未定乗数法を用いて陽に解けることを示す。まず、UBPを2つの凸最小化問題UBP'に変換し、そのUBP'には強い双対性があることを示す。この双対性こそがラグランジュの未定乗数法の適用可能性を担保するというロジックである。
UBPを解く前に、次の式のポイントを押さえておく必要がある → この式のは射影作用素である。ここで以下の定理が成り立つ。
Theorem 4.
とし、なおかつは既知とする。この時に対して であれば、 である。
(R1')により、ただちに以下の帰結を得る。
Corollary 5.
かつとする。であれば、である。
のような一般的なケースでは、以下のように置く。(10)
明らかに以下を得る。
(11)
ゆえに、UBPは(10)の2つの副問題を解くことで解ける。
とする。すると(10)は以下のように書き下せる。
(UBP)
ラグランジュの未定乗数法を用いて一般的な最小化問題に書き下したいので、以下のように書き換える。
(UBP')
Lemma 6.
なおかつを既知とする。この時UBP'には強い双対性がある。またUBP'は最適解を与える。
そこでこの双対問題を解き、次にKKT条件を通じて主問題の最適解を復元することにする。
Lemma 7.
なおかつを既知とする。この時に対して であれば、 として、
a) もしであれば、双対問題UBP'は以下と等価である。
(UBD')
さらに、はの最大値を与える。
b) もしであれば、双対問題UBP'は以下と等価である。
(UBD'')
ここに、UBP'は以下の定理によって解くことができる。
Theorem 8.
なおかつを既知とする。この時 かつ であれば、 とする。
a) もしであれば、
; (12)
b) もしであれば、
, (13)
ただしここでは
(14)
5 The proposed Slores Rule for Regularized Logistic Regression
(R1')により、ようやく正則化ロジスティック回帰のためのSloresを構築することができる。最後の定理として、以下を用いる。
Theorem 9 (Slores)
かつは既知とする。
もしであれば、である。
もしであれば、以下のうちいずれかが成り立つ。
(a)
(b)
これをアルゴリズムに落としたものが以下。
アルゴリズムにしてしまえば簡単である。これで不要なj列を削除することができる。ポイントは冒頭でも書かれているように、列方向に向かってとたった1回だけスキャンして都度if文で判定するだけで従来手法より確度高く不要な列を削除できること(射影作用素があくまでもj列と学習ラベルとの内積だけで構成されている点も重要)。これにより高効率かつ高精度な変数選択を実現している。
6 Experiments
TeX書いてるだけで精根尽き果てたので略orz はむかずさんが今年1月のNIPS2014読み会で解説していらした(A Safe Rule for Sparse Logistic Regression)ようで、6節の解説はこちらの方が充実しているのでそちらをどうぞ。
(※頻出する文献[10]はhttp://web.stanford.edu/~boyd/papers/pdf/l1_logistic_reg.pdf)
とりあえず、全ての定理や補題が最後のアルゴリズムにたどり着くまで一直線につながるロジックの論文だったので、途中のプロセスをほとんど割愛できなかったのが読んでて辛かったです。。。でもこれだけゴリゴリやればナイスなアルゴリズム書けるのかなぁ(妄想)、ってか今回はとにかくTeX書いてるだけで精根尽き果てました。。。
追記
気が付いてなかったんですが、うちのチームの同僚氏から「この論文の元のarXivにAppendixが載ってるよ」と教わったので、リンク張っておきます。途中の式展開で訳の分からないところはそちらを見れば大体分かるはずです。
*1:実は読み終わらなかったので来週も続きをやる予定