こんにちは。 その１でラッソの概要と大きな特徴であるスパース性を確認しました。 今回からはラッソ実装に向けて数学を頑張りましょう。

Notationのについて

  • Obj (objective function)
  • OLS (Ordinary least squares) (回帰の残差平方和)
  • m: データ数
  • n: 次元(特徴)
  • \theta_j: j番目の特徴\theta
  • x_j^{(i)}: i番目の観測データxのうちjに対応するもの

目的関数について

今回、つまりラッソの目的関数は以下の通り

    \[Obj(\theta) & = OLS(\theta) + \lambda | \theta |_1^1\]

    \[= \frac{1}{2} \sum_{i=1}^m \left[y^{(i)} - \sum_{j=0}^n \theta_j x_j^{(i)}\right]^2 + \lambda \sum_{j=0}^n |\theta_j|\]

(OLS)の勾配について

上の目的関数は微分できません。なのでひとまず置いておいて OLSをいつも通り微分して微分を計算します。 後々のため、今回は勾配でなく、\theta_jでの微分を計算します。

    \[\frac{\partial }{\partial \theta_j} OLS(\theta) & = - \sum_{i=1}^m x_j^{(i)} \left[y^{(i)} - \sum_{j=0}^n \theta_j x_j^{(i)}\right]\]

    \[= - \sum_{i=1}^m x_j^{(i)} \left[y^{(i)} - \sum_{k \neq j}^n \theta_k x_k^{(i)} - \theta_j x_j^{(i)}\right]\]

    \[= - \sum_{i=1}^m x_j^{(i)} \left[y^{(i)} - \sum_{k \neq j}^n \theta_k x_k^{(i)} \right] + \theta_j \sum_{i=1}^m (x_j^{(i)})^2\]

簡単のためこれを次のように表します。

    \[:= - \rho_j + \theta_j z_j\]

L1-normの微分について

L_1-normは微分できないとわかりました。なので 微分できるように、微分という概念を拡張します。そこで出てくるのが
　劣勾配(Subgradient)　
です。wikiのリンク
定義（劣微分） 　Convex f: I \rightarrow \mathbb{R} の点 x_0 における劣微分は次の条件を満たす c \in \mathbb{R} で定義する。 (簡単のため\mathbb{R}^1についてはなし、微分の代わりに勾配という言葉を使っている)

    \[\frac{\partial f }{\partial x}\bigg |<em>{x=x_0} = { c \in \mathbb{R} : f(x) \geq f(x_0) + c(x - x_0) , \forall x \in I }\]

書き換えると x_0における劣勾配は次の閉区間の集合である。a \leq b

    \[a = \lim</em>{x \rightarrow -x_0} \frac{f((x) - f(x_0)}{x - x_0}\]

    \[b = \lim_{x \rightarrow +x_0} \frac{f((x) - f(x_0)}{x - x_0}\]

    \[\frac{\partial f }{\partial x}\bigg |_{x=x_0} = [a,b]\]

これが勾配の拡張になっていることは微分可能な点においてその劣勾配が一点集合になることからわかる
実はこれは簡単で、場合分けして綺麗に微分できるところの間を１つの微分の集合と見るのです。 今回のL_1ノルム、つまり

    \[f(x) = |x|\]

を例にとると、

(1)   \begin{align*} \texttt{if } x > 0 ~~ , ~~ \frac{\partial f}{\partial x} = 1 \end{align*}

(2)   \begin{align*} \texttt{if } x < 0 ~~ , ~~ \frac{\partial f}{\partial x} = -1 \end{align*}

そしてこの間の集合を0での微分とするのが劣勾配

(3)   \begin{align*} \texttt{if } x = 0 ~~ , ~~ \frac{\partial f}{\partial x} = [-1,1] \end{align*}

次のはイメージ図 ではこの劣勾配を使って今回の目的関数の第２項を微分してゼロとおきます。

(4)   \begin{align*} \frac{\partial }{\partial \theta_j} Obj(\theta) = \frac{\partial }{\partial \theta_j} OLS(\theta) + \frac{\partial }{\partial \theta_j} \lambda | \theta |_1^1 \end{align*}

(5)   \begin{align*} 0 = -\rho_j + \theta_j z_j + \frac{\partial }{\partial \theta_j} \lambda | \theta_j |_1^1 \end{align*}

ここで先ほどと同様に場合分けを行って

(6)   \begin{align*} \texttt{if } \theta_j < 0 ~~ , ~~ 0 = -\rho_j + \theta_j z_j - \lambda \end{align*}

(7)   \begin{align*} \texttt{if } \theta_j > 0 ~~ , ~~ 0 = -\rho_j + \theta_j z_j + \lambda \end{align*}

そして、

(8)   \begin{align*} \texttt{if } \theta_j = 0 ~~ , ~~ 0 = [-\rho_j - \lambda ,-\rho_j + \lambda ] \end{align*}

ですね。文字が多くなってしまったので再確認ですが、目標は\theta_jを求めることです。上の２つの式は簡単に求まりますが、３つ目の式については閉区間に0が含まれるという条件で考えましょう。なので

(9)   \begin{align*} 0 \in [-\rho_j - \lambda ,-\rho_j + \lambda ] \end{align*}

(10)   \begin{align*} -\rho_j - \lambda \leq 0 \end{align*}

(11)   \begin{align*} -\rho_j + \lambda \geq 0 \end{align*}

なので

(12)   \begin{align*} - \lambda \leq \rho_j \leq \lambda \end{align*}

まとめると

(13)   \begin{align*} \texttt{for } \rho_j < - \lambda ~~ , ~~ \theta_j = \frac{\rho_j + \lambda}{z_j} \end{align*}

(14)   \begin{align*} \texttt{for } - \lambda \leq \rho_j \leq \lambda ~~ , ~~ \theta_j = 0 \end{align*}

(15)   \begin{align*} \texttt{for } \rho_j > \lambda ~~ , ~~ \theta_j = \frac{\rho_j - \lambda}{z_j} \end{align*}

となります。ちなみにこの場合分けからSoft thresholding functionという関数が定義されます。 最後に劣微分と一緒にplotを見てみましょう。
微分できなくてよく使う関数をたまたま思い出しました。ニューラルネットワークで使うRELU fucntionですね。 – 活性化関数ReLUとその類似関数 他にも色々あるようです。 色々計算づくしでしたが微分を計算できました。あとは最適化のみですが今までは勾配法を使っていましたが「微分不可能な場合は勾配法は無理」なので他の最適化法が必要です。そこでLassoの問題ではいくつかのメジャーな方法があります。
  • Coordinate descent（座標降下法）
  • ISTA (メジャライザー最小化)
  • FISTA (高速化)
です。もっとも簡単なのは座標降下法です。メジャライザーはテイラー展開を用いて上界を扱うものですがこれらについては次回解説します。 でわ。

READMORE