MIT OCW, Machine Learning 07日目 リッジ回帰

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Penalized Log-Likelihood and Ridge Regression

training dataが,その各exampleの次元$d$に対して十分に大きくないときには,パラメータをregularizeすることが多い. prior distributionを$P(\theta, \theta_0)$にassign することで,どのようにregularizeすればよいかを見る. prior distributionは, パラメータの推測値の絶対値を小さくするために導入する.
prior distributionを平均0のnormal distributionとする.つまり
$$P(\theta, \theta_0, \sigma^{'2})=N(\theta_0;0, \sigma^{'2})$$
をlikelihood $L$に追加すると
$$\begin{aligned}l'(\theta, \theta_0, \sigma^2) &= \sum_{t=1}^n \log \left[\frac{1}{\sqrt{2\pi \sigma^2}} \exp \left(-\frac{1}{2\sigma^2} (y_t-\theta^T \mathbf{x}_t - \theta_0)^2 \right) \right] + \log P(\theta, \theta_0; \sigma^{`2}) \\ &= \text{const.} - \frac{n}{2} \log \sigma^2 - \frac{1}{2\sigma^2} \sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0)^2 \\ &-\frac{1}{2\sigma^{'2}}(\theta_0^2 + \sum_{j=1}^d \theta_j^2) - \frac{d+1}{2} \log \theta^{'2} \end{aligned}$$
また,$\sigma^{'2}=\sigma^2/ \lambda$とすることも多い. $\sigma^2$が小さいときにはoverfittingのおそれがあるので,よりpenallityを大きくしてパラメータを0に近づけるのである. training dataが小さいときには$\sigma^2$が小さくなりなちなので,この節のはじめに説明したregularizationをする動機と合目的である.
$\sigma^{'2}=\sigma^2/\lambda$を$l'$に代入すると
$$\begin{aligned} l'(\theta, \theta_0, \sigma^2) &= \text{const.} - \frac{n}{2}\log \sigma^2 - \frac{1}{2\sigma^2}\sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0)^2 \\ &-\frac{\lambda}{2\sigma^2}(\theta^2_0 + \sum_{j=1}^d \theta_j^2) - \frac{d+1}{2} \log (\sigma^2/ \lambda) \\ &= \text{const.} - \frac{n+d+1}{2} \log\sigma^2 + \frac{d+1}{2} \log \lambda \\ &-\frac{1}{2\sigma^2} \left[ \sum_{t=1}^n (y_t-\theta^T \mathbf{x}_t - \theta_0)^2 + \lambda (\theta^2_0 + \sum_{j=1}^d \theta^2_j)\right]\end{aligned}$$
このregularization problemの解を求めることをRidge regressionという.
その解$\hat{\theta}, \hat{\theta_0}$は,
$$\left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] = (\lambda \mathbf{I} + \mathbf{X^TX})^{-1} \mathbf{Xy}$$
で与えられる.
$$\begin{aligned}E \left[\left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right]|\mathbf{X} \right] &=(\lambda \mathbf{I}+\mathbf{X^TX})^{-1}\mathbf{X^TX} \left[\begin{array}{}{\theta^*} \\ {\theta_0^*} \end{array} \right] \\&=(\lambda \mathbf{I} +\mathbf{X^TX})^{-1} (\mathbf{X^TX + \lambda I -\lambda I})\left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \\ &= \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] - \lambda(\lambda \mathbf{I} + \mathbf{X^TX})^{-1} \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \\ &= (\mathbf{I} - \lambda(\lambda \mathbf{I} + \mathbf{X^TX})^{-1}) \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \end{aligned}$$
だから,$\hat{\theta}, \hat{\theta_0}$はbiasedな推測である. また$(\mathbf{I} - \lambda(\lambda \mathbf{I} + \mathbf{X^TX})^{-1})$は固有値が1未満の正定値行列で,$\lambda$が大きくなるとともに$\theta, \theta_0$は$0$へと近づいていく. 以前やったのと同じ方法で MSEを計算すると,
$$\begin{aligned} E\left[ \left\| \left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] - \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \right\| | \mathbf{X} \right] &= \sigma^{*2} \cdot Tr[(\lambda \mathbf{I} + \mathbf{X^TX})^{-1} - \lambda(\lambda \mathbf{I} + \mathbf{X^TX})^{-2}] \\& +\lambda^2 \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right]^T (\lambda \mathbf{I} + \mathbf{X^TX})^{-2}\left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \end{aligned}$$
であって,これはregularizationを考えない場合のMSE $\sigma^{*2} \cdot Tr[(\mathbf{X^TX})^{-1}]$よりも小さく出来る.

Active Learning

training data $\{\mathbf{x}_1, ..., \mathbf{x}_n\}$を能動的に選んでestimation errorを小さくすることを,active learning問題という. 例えば画像の分類で,すでにたくさんのtraining dataのもととなるlabelなしの画像データが有るが,そこからできるだけ少なくデータを選んでラベル付けし(ときにラベル付は画像そのものの収集よりコストがかかる),training dataとする状況を考える. 推測の正確性を犠牲にせずに,できるだけ選ぶ画像データを少なくする方法を考えるのである.
この問題を考察するため,regularizationの無い場合のestimation errorを再掲する.
$$\begin{aligned} E\left[ \left\| \left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] - \left[\begin{array}{} {\theta}^* \\ {\theta_0}^* \end{array} \right] \right\| | \mathbf{X} \right] =\sigma^{*2} Tr[(\mathbf{X^TX})^{-1}] \end{aligned}$$
$\sigma^{*2}$はtraining dataの選び方によらないので,$Tr[(\mathbf{X^TX})^{-1}]$が小さくなるようにすれば良い. ただし,この方法はexampleと推定値の写像の線形性を仮定しているから,そうでない場合には使えない.