Regularization Paths for Generalized Linear Models via Coordinate Descent

February 19, 2022

ラッソ、リッジ、またはその両方をくみあわせるelastictnetを正則化項とする一般化線形モデルの学習を高速化した座標降下法である。座標降下法を単純に実装すると、スパースで次元数の多い特徴だと学習に時間がかかる。表題の手法は、その単純なパラメタの更新式の一部を、説明変数の内積におきかえ、学習データの数や次元数に対して学習時間を短縮する。

目的変数を$Y \in \mathbb{R}$, 説明変数を$X\in \mathbb{R}^p$, $N$件の学習データを$(x_i, y_i)$として、説明のために線形回帰$E(Y\mid X=x)=\beta_0 + x^\top\beta$を導入する。簡単のために、$j=1, \dots , p$について、$x_{i,j}$は、$\sum^N_{i=1}x_{i,j}=0, \frac{1}{N}\sum^{N}_{i=1}x^2_{i,j}=1$で標準化されていると仮定する。このとき、$P_\alpha$をelastic-net penaltyにもつelasticnetの学習は、つぎの問題をとく。

$$ \begin{align} \min\_{\beta\_0, \beta\in \mathbb{R}^{p+1}}R\_\lambda(\beta\_0, \beta) &= \min\_{(\beta\_0, \beta)\in\mathbb{R}^{p+1}}\left[\frac{1}{2N}\sum\_{i=1}^{N}(y\_i-\beta\_0-x^{\top}\_i\beta)^2 + \lambda P\_\alpha (\beta)\right]\\\\ P\_{\alpha}(\beta) &= (1-\alpha)\frac{1}{2}\mid\mid \beta\mid\mid^2\_{l\_2}+\alpha\mid\mid\beta\mid\mid\_{l\_1}\\\\ &=\sum^p\_{j=1}\left[\frac{1}{2}(1-\alpha)\beta^2\_j+\alpha\mid\beta\_j\mid\right] \end{align} $$

このとき、座標降下法で次元$j$の係数$\tilde{\beta}_j$を以下の式で更新できる。

$$ \begin{align} \tilde{\beta}\_j&\leftarrow\frac{S\left(\frac{1}{N}\sum^N\_{i=1}x\_{ij}(y\_i-\tilde{y}\_i^{(j)}), \lambda\alpha\right)}{1+\lambda (1-\alpha)}\\\\ \tilde{y}\_i^{(j)}&=\tilde{\beta}\_0 + \sum\_{l\neq j}x\_{il}\tilde{\beta}\_l \end{align} $$

$$ S(z, \gamma) = \begin{cases} z-\gamma & \text{if }z>0 \text{ and }\gamma <\mid z\mid\\\\ z+\gamma & \text{if } z < 0 \text{ and } \gamma < \mid z \mid \\\\ 0 &\text{if } \gamma \ge \mid z \mid \end{cases} $$

ここで、$\hat{y}_i$をサンプル$i$の現在の予測値、$r_i$を残差とすると

$$ \begin{align} y\_i-\tilde{y}\_i^{(j)}&=y\_i-\hat{y}\_i+x\_{ij}\tilde{\beta}\_j\\\\ &=r\_i+x\_{ij}\tilde{\beta}\_j \end{align} $$

であり、$x_j$を平均0で標準化しているため

$$ \frac{1}{N}\sum^N\_{i=1}x\_{ij}(y\_i-\tilde{y}\_i^{(j)})=\frac{1}{N}\sum^N\_{i=1}x\_{ij}r\_i+\tilde{\beta}\_j $$

この場合、各次元の係数を一回ずつ更新するときの計算量は$O(pN)$になり、説明変数の次元数がおおいと計算に時間がかかる。そこで、$\langle x_j,y\rangle = \sum^N_{i=1}x_{ij}y_i$とすると説明変数の内積により

$$ \begin{align} \sum\_{i=1}^Nx_{ij}r\_j &=\sum\_i^{N}(y\_i-\tilde{y\_i}^{(j)}-x\_{ij}\tilde{\beta}\_j)x\_{ij}\\\\ &=\sum\_i^{N}x\_{ij}y\_i-\sum^N\_{i=1}x\_{ij}(\tilde{y}\_i^{(j)}+x\_{ij}\tilde{\beta}\_j)\\\\ &=\langle x\_j,y\rangle - \sum\_{i=1}^Nx\_{ij}(\tilde{\beta}\_0 + \sum\_{l\neq j}x\_{il}\tilde{\beta}\_l + x\_{ij}\tilde{\beta}\_j)\\\\ &=\langle x\_j,y\rangle - \sum\_{i=1}^Nx\_{ij}(\tilde{\beta}\_0 + \sum\_{k=1}^px\_{ik}\tilde{\beta}\_k)\\\\ &=\langle x\_j,y\rangle - \sum\_{k:\mid\tilde{\beta}\_k\mid > 0}\langle x\_j,x\_k\rangle \tilde{\beta}\_k \end{align} $$

に変形できる。 $\langle x_j,y\rangle$は係数を更新に影響しないので一度だけ計算すればよい。係数のひとつが更新されたときに各勾配を$O(p)$で更新できる。したがって、あたらしい説明変数が追加されず、0でない項が$m$あれば各次元の係数を更新するときにかかる計算量は$O(pm)$になる。

論文をこちらからダウンロードできます。