"A Safe Screening Rule for Sparse Logistic Regression" (Wang et al., NIPS2014) メモランダム - 渋谷駅前で働くデータサイエンティストのブログ

今日のうちのチームの輪読会で"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な特徴量を検出し、未知の解である $\ell_1$ 正則化ロジスティック回帰の"dual optimal solution"を推定する。この方法論では、特徴量同士の内積の上界の推定問題を制約付き凸問題として定式化し、閉形式解（解析的に得られる解のことですね）を得る。

2 Basics and Motivations

ここでは $\ell_1$ 正則化ロジスティック回帰の基礎を振り返り、KKT条件のもとにスクリーニングルールを立てることとする。まず $\ell_1$ 正則化ロジスティック回帰は、学習データサンプル $\{\mathbf{x}_i\}^m_{i=1}$ と教師ラベル $\mathbf{b} \in \mathfrak{R}^m$ 、全ての $i \in {1, \cdots , m}$ に対して $b_i \in \{1, -1\}$ 、のもとで
$min_{\beta, c} \frac{1}{m} \displaystyle\sum^m_{i=1} log (1 + exp(- \langle \beta, \overline{\mathbf{x}}_i \rangle - b_i c) + \lambda \| \beta \|_1$ (LRP $_\lambda$ )

ただし $\beta \in \mathfrak{R}^p$ , $c \in \mathfrak{R}$ は偏回帰係数及び切片、 $\overline{\mathbf{x}_i} = b_i \mathbf{x}_i$ 、そして $\lambda > 0$ は $\ell_1$ 正則化パラメータ。ここで $\overline{\mathbf{X}} \in \mathfrak{R}^{m \times p}$ はデータマトリクスで、 $i^{th}$ 行目は $\overline{\mathbf{x}}_i$ に当たり、 $j^{th}$ 列目は $\overline{\mathbf{x}}^j$ に当たる。

次に、 $\cal{C} = {\theta \in \mathfrak{R}^m ~ : ~ \theta_i \in (0,1), i = 1, \cdots , m}$ および $y \in (0,1)$ に対して $f(y) = y log(y) + (1-y) log (1-y)$ とする。この時(LRP $_\lambda$ )の双対問題は
$min_{\theta} \left \{ g(\theta) = \frac{1}{m} \displaystyle\sum^m_{i=1} f(\theta_i) ~ : ~ \| \overline{\mathbf{X}}^T \theta \|_{\infty} \leq m \lambda, \langle \theta, \mathbf{b} \rangle = 0, \theta \in \cal{C} \right \}$ (LRD $_\lambda$ )
と置ける。ここで求める解は $\theta$ となる。

以下単純のため(LRD $_\lambda$ )を $\cal{F}_\lambda$ 、 $(\beta^*_\lambda, c^*_\lambda)$ および $\theta^*_\lambda$ を(LRP $_\lambda$ )、(LRD $_\lambda$ )の最適解とする。筆者らの文献[10]により、 $\lambda$ を適切に選べばどちらも陽的に解けることが示されている。 $\cal{P} = \{ i ~ : ~ b_i = 1 \}, ~ \cal{N} = \{ i ~ : ~ b_i = -1 \}$ ならびに $m^{+}, ~ m^{-}$ をそれぞれ $\cal{P}, ~ \cal{N}$ の濃度(cardinality)として、

$\lambda_{max} = \frac{1}{m} \| \overline{\mathbf{X}}^T \theta^*_{\lambda_{max}} \|_{\infty}$ (1)
ただしこの時
$[ \theta^*_{\lambda_{max}} ]_i = \left \{ \begin{array} ~ \frac{m^{-}}{m}, ~ {if} ~ i \in \cal{P} \\ \frac{m^+}{m}, ~ {if} ~ i \in \cal{N} \end{array} \right .$ $i = 1, \cdots, m$ (2)
文献[10]から $\lambda \geq \lambda_{max}$ であれば常に $\beta^*_{\lambda} = 0$ かつ $\theta^*_{\lambda} = \theta^*_{\lambda_{max}}$ である。
$\lambda \in (0, \lambda_{max}$ ]である時、(LRD $_\lambda$ )は唯一の最適解をもつ。(LRP $_\lambda$ )と(LRD $_\lambda$ )のKKT条件は以下のように書ける。

$\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle \in \left \{ \begin{array} ~ m\lambda ~ if ~ [\beta^*_{\lambda}]_j > 0, \\ -m\lambda ~ if ~ [\beta^*_{\lambda}]_j < 0, \\ [-m\lambda, m\lambda] ~ if ~ [\beta^*_{\lambda}]_j =0, \end{array} \right. ~ j = 1, \cdots , p$ (3)
この(3)式から以下が言える。
$|\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle| < m\lambda \Rightarrow [\beta^*_{\lambda}]_j = 0$ (R1)

言い換えると、もし $|\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle| < m\lambda$ であれば、KKT条件は以下を示していることになる：最適解 $\beta^*_{\lambda}$ における $\overline{\mathbf{x}}^j$ の偏回帰係数は0に落ち、その場合j番目の特徴量カラムは(LRP $_\lambda$ )の最適化プロセスから「安全に」削除できる。

しかしながら、一般的には $\lambda < \lambda_{max}$ なる場合は $\theta^*_{\lambda}$ に関する知識がない限りは(R1)を適用することができない。この場合、 $\theta^*_{\lambda}$ を含む領域 $\cal{A}_{\lambda}$ を推定することで対処する。結果として、もし $max_{\theta \in \cal{A}_{\lambda}} |\langle \theta_{\lambda}, \overline{\mathbf{x}}^j \rangle| < m\lambda$ であれば、(R1)により $[\beta^*_{\lambda}$ _j = 0 ]と結論付けることができる。これまた言い換えると、(R1)は以下のように緩和できる。
$T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j) := max_{\theta \in \cal{A}_{\lambda}} |\langle \theta_{\lambda}, \overline{\mathbf{x}}^j \rangle| < m\lambda \Rightarrow [\beta^*_{\lambda}]_j = 0$ (R1')
この論文では(R1')をSlores構築の基礎と置く。これまでの論理展開から分かるように、 $T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j)$ が小さければ小さいほどバリバリ特徴量を落としていくことになり、 $T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j)$ を正確に求めるためには領域 $\cal{A}_{\lambda}$ の推定がキーとなり、 $\cal{A}_{\lambda}$ の上界を求めることが最重要だということになる。これは3節で凸最適化計画の解として得られることが示される。4節ではその解が陽に与えられることを示し、5節で具体的なSloresの導出を行う。

3 Estimating the Upper Bound via Solving a Convex Optimization Problem

この節では $|\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle|$ の上界 $T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j)$ を推定する新たな枠組みを示す。以下、パラメータ $\lambda_0$ とそれに対応する双対最適解 $\theta^*_{\lambda_0}$ が与えられているとする。

まず $T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j)$ の推定問題を制約付き凸最適化問題として定式化する。

双対関数 $g(\theta)$ に対し、 $[\nabla g(\theta)]_i = \frac{1}{m} log (\frac{\theta_i}{1 - \theta_i}), ~ [\nabla^2 g(\theta)]_{i,i} = \frac{1}{m} \frac{1}{\theta_i (1-\theta_i)} \geq \frac{4}{m}$ となる。 $\nabla^2 g(\theta)$ は対角行列であるため、 $\nabla^2 g(\theta) \succeq \frac{4}{m} I$ となる（Iは単位行列）。これにより $g(\theta)$ は係数 $\mu = \frac{4}{m}$ のもとで強く凸である（文献[16]）。これは以下の補題に拠っている。

Lemma 1.

$\lambda > 0$ および $\theta_1, \theta_2 \in \cal{F}_\lambda$ とすると、
a) $g(\theta_2) - g(\theta_1) \geq \langle \nabla g(\theta_1), \theta_2 - \theta_1 \rangle + \frac{2}{m} \| \theta_2 - \theta_1 \|^2_2$ (4)
b) $\theta_1 \neq \theta_2$ の時、(4)式の不等式からは等号がなくなる（必ず大小の関係になる）

$\lambda \in (0, \lambda_0]$ である時、 $\theta^*_\lambda$ も $\theta^*_{\lambda_0}$ も $\cal{F}_{\lambda_0}$ に属することは容易に言える。それゆえ、Lemma 1は $\theta^*_{\lambda_0}$ に関する知識のもとで $\theta^*_{\lambda}$ の境界を与える上で有用なツールとなる。これは以下の定理に拠っている。

Theorem 2.

$\lambda_{max} \geq \lambda_0 > \lambda > 0$ とすると、
a) $\| \theta^*_{\lambda} - \theta^*_{\lambda_0} \|^2_2 \leq \frac{m}{2} \left [ g(\frac{\lambda}{\lambda_0} \theta^*_{\lambda_0}) - g(\theta^*_{\lambda_0}) + (1 - \frac{\lambda}{\lambda_0}) \langle \nabla g(\theta^*_{\lambda_0}), \theta^*_{\lambda_0} \rangle \right ]$ (5)
b) $\theta^*_{\lambda} \neq \theta^*_{\lambda_0}$ の時、(5)式の不等式からは等号がなくなる

Theorem 2は $\theta^*_{\lambda}$ が以下の半径を伴う $\theta^*_{\lambda_0}$ を中心とする球体の中に存在することを示している。
$r = \sqrt{ \frac{m}{2} \left [ g(\frac{\lambda}{\lambda_0} \theta^*_{\lambda_0}) - g(\theta^*_{\lambda_0}) + (1 - \frac{\lambda}{\lambda_0}) \langle \nabla g(\theta^*_{\lambda_0}), \theta^*_{\lambda_0} \rangle \right ] }$ (6)

ここで改めてSloresが非常にゴリゴリ特徴量を削っていくタチのルールであることを思い出されたい。 $|\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle|$ の上界 $T( \theta^*_{\lambda}, \overline{\mathbf{x}}^j)$ はできるだけ精確に求める必要がある。このため、 $\theta^*_{\lambda}$ の可能領域である $\cal{A}_{\lambda}$ にもさらに制約をかけることが望ましい。明らかに、
$\langle \theta^*_{\lambda}, \mathbf{b} \rangle = 0$ (7)
である（LRD $_{\lambda}$ のもとで $\theta^*_{\lambda}$ が実現可能であるため）。一方、ここで $\cal{I}_{\lambda_0} = \{ j ~ : ~ \langle \theta^*_{\lambda_0}, \overline{\mathbf{x}}^j \rangle = | m \lambda_0 |, j = 1, \cdots, p \}$ なる集合を $\theta^*_{\lambda_0}$ の"active set"と呼ぶことにする。このactive setに対して以下の補題が成り立つ。

Lemma 3.

LRD $_{\lambda}$ に対する最適解 $\theta^*_{\lambda}$ が与えられた場合、active set $\cal{I}_{\lambda} = \{ j ~ : ~ \langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle = | m \lambda |, j = 1, \cdots, p \}$ は $\lambda \in (0, \lambda_{max}$ ]の時、空集合にならない

$\lambda_0 \in (0, \lambda_{max}]$ であるため、Lemma 3に従って $\cal{I}_{\lambda_0}$ は空集合にはならない。ここで、 $j_0 \in \cal{I}_{\lambda_0}$ なる $j_0$ および集合
$\overline{\mathbf{x}}^* = sign ( \langle \theta^*_{\lambda_0}, \overline{\mathbf{x}}^{j_0} \rangle ) \overline{\mathbf{x}}^{j_0}$ (8)
を取り上げる。この時 $\langle \overline{\mathbf{x}}^*, \theta^*_{\lambda_0} \rangle = m \lambda_0$ となる。LRD $_{\lambda}$ のもとで $\theta^*_{\lambda}$ が実現可能であるため、 $\theta^*_{\lambda}$ は以下を満たす。

$\langle \theta^*_{\lambda}, \overline{\mathbf{x}}^* \rangle \leq m \lambda$ (9)

結果として、Theorem 2, (7), (9)式から $\theta^*_{\lambda}$ が以下の集合に含まれることが示される。

$\cal{A}^{\lambda}_{\lambda_0} := \{ \theta ~ : ~ \| \theta - \theta^*_{\lambda_0} \|^2_2 \leq r^2, \langle \theta, \mathbf{b} \rangle = 0, \langle \theta, \overline{\mathbf{x}}^* \rangle \leq m \lambda \}$

$\theta^*_{\lambda} \in \cal{A}^{\lambda}_{\lambda_0}$ であるため、 $| \langle \theta^*_{\lambda}, \overline{\mathbf{x}}^j \rangle | \leq max_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} | \langle \theta, \overline{\mathbf{x}}^j \rangle |$ が言える。ゆえに、(R1')は以下の上界
$T (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}) := max_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} | \langle \theta, \overline{\mathbf{x}}^j \rangle |$ (UBP)
が $m \lambda$ より小さければ、 $[\beta^*_{\lambda}]_j = 0$ であり $\overline{\mathbf{x}}^j$ はLRP $_\lambda$ から削除できると結論付けられる。

4 Solving the Convex Optimization Problem (UBP)

この節では今までちょくちょく取り上げてきた例の凸最適化計画（何故か上界問題＝UBPと略しているので注意）がラグランジュの未定乗数法を用いて陽に解けることを示す。まず、UBPを2つの凸最小化問題UBP'に変換し、そのUBP'には強い双対性があることを示す。この双対性こそがラグランジュの未定乗数法の適用可能性を担保するというロジックである。

UBPを解く前に、次の式のポイントを押さえておく必要がある → $\mathbf{P}\overline{\mathbf{x}}^j = \overline{\mathbf{x}}^j - \frac{\langle \overline{\mathbf{x}}^j , \mathbf{b} \rangle}{\| \mathbf{b} \|^2} \mathbf{b} = 0$ 　この式の $\mathbf{P}$ は射影作用素である。ここで以下の定理が成り立つ。

Theorem 4.

$\lambda_{max} \geq \lambda_0 > \lambda > 0$ とし、なおかつ $\theta^*_{\lambda_0}$ は既知とする。この時 $j \in \left \{ 1, \cdots, p \right \}$ に対して $\mathbf{P} \overline{\mathbf{x}}^j = 0$ であれば、 $T ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = 0$ である。

(R1')により、ただちに以下の帰結を得る。

Corollary 5.

$\lambda \in (0, \lambda_{max}]$ かつ $j \in \left \{ 1, \cdots, p \right \}$ とする。 $\mathbf{P} \overline{\mathbf{x}}^j = 0$ であれば、 $[\beta^*_{\lambda}]_j = 0$ である。

$\mathbf{P} \overline{\mathbf{x}}^j \neq 0$ のような一般的なケースでは、以下のように置く。
$T_+ (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}) := max_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} \langle \theta +\overline{\mathbf{x}}^j \rangle, ~ T_- (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}) := max_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} \langle \theta -\overline{\mathbf{x}}^j \rangle$ (10)
明らかに以下を得る。
$T ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = max \{ T_+ (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}), ~ T_- (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}) \}$ (11)
ゆえに、UBPは(10)の2つの副問題を解くことで解ける。
$\xi \in \{ +1, -1 \}$ とする。すると(10)は以下のように書き下せる。
$T_{\xi} ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = max_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} \langle \theta, \xi \overline{\mathbf{x}}^j \rangle$ (UBP $_s$ )
ラグランジュの未定乗数法を用いて一般的な最小化問題に書き下したいので、以下のように書き換える。
$- T_{\xi} ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = min_{\theta \in \cal{A}^{\lambda}_{\lambda_0}} \langle \theta, - \xi \overline{\mathbf{x}}^j \rangle$ (UBP')

Lemma 6.

$\lambda_{max} \geq \lambda_0 > \lambda > 0$ なおかつ $\theta^*_{\lambda_0}$ を既知とする。この時UBP'には強い双対性がある。またUBP'は最適解 $\cal{A}^{\lambda}{\lambda_0}$ を与える。

そこでこの双対問題を解き、次にKKT条件を通じて主問題の最適解を復元することにする。

Lemma 7.

$\lambda_{max} \geq \lambda_0 > \lambda > 0$ なおかつ $\theta^*_{\lambda_0}$ を既知とする。この時 $j \in \left \{ 1, \cdots, p \right \}$ に対して $\mathbf{P} \overline{\mathbf{x}}^j \neq 0$ であれば、 $\overline{\mathbf{x}} = - \xi \overline{\mathbf{x}}^j$ として、
$\cal{U}_1 = \{ (u_1, u_2 ~ : ~ u_1 > 0, u_2 \geq 0 \} ~ and ~ \cal{U}_2 = \left \{ (u_1, u_2) ~ : ~ u_1 = 0, u_2 = - \frac{\langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle}{\| \mathbf{P} \overline{\mathbf{x}}^* \|^2_2} \right \}$
a) もし $\frac{\langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle}{\| \mathbf{P} \overline{\mathbf{x}} \|_2\| \mathbf{P} \overline{\mathbf{x}}^* \|_2} \in (-1, 1]$ であれば、双対問題UBP'は以下と等価である。
$max_{(u_1, u_2) \in \cal{U}_1} \overline{g} (u_1, u_2) = - \frac{1}{2 u_1} \| \mathbf{P}\overline{\mathbf{x}} + u_2 \mathbf{P}\overline{\mathbf{x}}^* \|^2_2 + u_2 m (\lambda_0 - \lambda) + \langle \theta^*_{\lambda_0}, \overline{\mathbf{x}} \rangle - \frac{1}{2}u_2 r^2$ (UBD')
さらに、 $\overline{g} (u_1, u_2)$ は $\cal{U}_1$ の最大値を与える。
b) もし $\frac{\langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle}{\| \mathbf{P} \overline{\mathbf{x}} \|_2\| \mathbf{P} \overline{\mathbf{x}}^* \|_2} = -1$ であれば、双対問題UBP'は以下と等価である。
$max_{(u_1, u_2) \in \cal{U}_1 \cup \cal{U}_2} \overline{\overline{g}} (u_1, u_2) = \left \{ \begin{array} \overline{g}(u_1, u_2) ~ if ~ (u_1, u_2) \in \cal{U}_1 \\ - \frac{\| \mathbf{P} \overline{\mathbf{x}} \|_2}{\| \mathbf{P} \overline{\mathbf{x}}^* \|} m \lambda ~ if ~ (u_1, u_2) \in \cal{U}_2 \end{array} \right .$ (UBD'')

ここに、UBP'は以下の定理によって解くことができる。

Theorem 8.

$\lambda_{max} \geq \lambda_0 > \lambda > 0, ~ d = \frac{m (\lambda_0 - \lambda)}{r \| \mathbf{P} \overline{\mathbf{x}}^* \|_2}$ なおかつ $\theta^*_{\lambda_0}$ を既知とする。この時 $j \in \left \{ 1, \cdots, p \right \}$ かつ $\mathbf{P} \overline{\mathbf{x}}^j \neq 0$ であれば、 $\overline{\mathbf{x}} = - \xi \overline{\mathbf{x}}^j$ とする。
a) もし $\frac{\langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle}{\| \mathbf{P} \overline{\mathbf{x}} \|_2\| \mathbf{P} \overline{\mathbf{x}}^* \|_2} \geq d$ であれば、
$T_{\xi} ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = r \| \mathbf{P} \overline{\mathbf{x}} \|_2 - \langle \theta^*_{\lambda_0}, \overline{\mathbf{x}} \rangle$ ; (12)
b) もし $\frac{\langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle}{\| \mathbf{P} \overline{\mathbf{x}} \|_2\| \mathbf{P} \overline{\mathbf{x}}^* \|_2} < d$ であれば、
$T_{\xi} ( \theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0} ) = r \| \mathbf{P} \overline{\mathbf{x}} + u^*_2 \mathbf{P} \overline{\mathbf{x}}^* \|_2 - u^*_2 m (\lambda_0 - \lambda) - \langle \theta^*_{\lambda_0}, \overline{\mathbf{x}} \rangle$ , (13)
ただしここでは
$u^*_2 = \frac{-a_1 + \sqrt{\mathbf{\Delta}}}{2 a_2},$
$a_2 = \| \mathbf{P} \overline{\mathbf{x}}^* \|^4_2 (1 - d^2),$
$a_1 = 2 \langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle \| \mathbf{P} \overline{\mathbf{x}}^* \|^2_2 ( 1 - d^2),$
$a_0 = \langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle^2 - d^2 \| \mathbf{P} \overline{\mathbf{x}} \|^2_2 \| \mathbf{P} \overline{\mathbf{x}}^2 \|^2_2,$
$\mathbf{\Delta} = a^2_a - 4 a_2 a_0 = 4 d^2 ( 1 - d^2 ) \| \mathbf{P} \overline{\mathbf{x}}^* \|^4_2 ( \| \mathbf{P} \overline{\mathbf{x}} \|^2_2 \| \mathbf{P} \overline{\mathbf{x}}^* \|^2_2 - \langle \mathbf{P} \overline{\mathbf{x}}, \mathbf{P} \overline{\mathbf{x}}^* \rangle^2 )$ (14)

5 The proposed Slores Rule for $\ell_1$ Regularized Logistic Regression

(R1')により、ようやく $\ell_1$ 正則化ロジスティック回帰のためのSloresを構築することができる。最後の定理として、以下を用いる。

Theorem 9 (Slores)

$\lambda_0 > \lambda > 0$ かつ $\theta^*_{\lambda_0}$ は既知とする。
もし $\lambda \geq \lambda_{max}$ であれば、 $\beta^*_{\lambda}=0$ である。
もし $\lambda_{max} \geq \lambda_0 > \lambda > 0$ であれば、以下のうちいずれかが成り立つ。
(a) $\mathbf{P} \overline{\mathbf{x}}^j = 0,$
(b) $max \{ T_{\xi} (\theta^*_{\lambda}, \overline{\mathbf{x}}^j; \theta^*_{\lambda_0}) ~ : ~ \xi = \pm1 \} < m \lambda, ~ then ~ [ \beta^*_{\lambda} ] = 0$

これをアルゴリズムに落としたものが以下。

アルゴリズムにしてしまえば簡単である。これで不要なj列を削除することができる。ポイントは冒頭でも書かれているように、列方向に向かって $j ~ = ~ 1, \cdots, p$ とたった1回だけスキャンして都度if文で判定するだけで従来手法より確度高く不要な列を削除できること（射影作用素 $\mathbf{P}$ があくまでも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書いてるだけで精根尽き果てました。。。