MIT OCW, Machine Learning 05日目 線形回帰

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.

Lecture 5. Linear Regression, Active Learning

regression (回帰)とは,exampleに対して,labelではなく連続なresponse(観測値)を推測することであって,ここでは実数とする. またここではlinear regression modelのみを扱うが,これは簡単にlinearでないmodelに拡張できる(次章).

$\mathbf{x} \mapsto E[y|\mathbf{x}]=\theta^T \mathbf{x}+\theta_0$という写像がlinear regression modelであって,つまりdecision boundaryの直線が推測値になる. また,推測値の周りの観測値の分布が問題となるが,ここではresponseを期待値として,$\mathbf{x}$に依存しない分散$\sigma^2$の正規分布を使う. PDFは
$$N(y; \mu, \sigma^2) = \frac{1}{\sqrt{2\pi \sigma^2}} \exp \left(-\frac{1}{2\sigma^2}(y-\mu)^2 \right)$$
ここで,$\mu= \theta^T \mathbf{x} + \theta_0$だから,
$$P(y|\mathbf{x}, \theta, \theta_0) = N(y; \theta^T\mathbf{x}+\theta_0, \sigma^2)$$
となる.
training data $\{(\mathbf{x}_1, y_1), ..., (\mathbf{x}_n, y_n)\}$について,conditional likelihoodを最大化することで最適なパラメータ$\theta, \theta_0, \sigma^2$を見つける.
$$L(\theta, \theta_0, \sigma^2) = \prod_{t=1}^n \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)$$
がLikelihoodであって, またlogをとって,
$$\begin{aligned} l(\theta, \theta_0, \sigma^2) &= \sum_{t=1}^n \log \left[ -\frac{1}{2\sigma^2} (y_t-\theta^T \mathbf{x}_t -\theta_0)^2 \right] \\ &= \sum \left[ -\frac{1}{2}\log(2\pi) - \frac{1}{2} \log \sigma^2 - \frac{1}{2\sigma^2} (y_t - \theta^T \mathbf{x}_t - \theta_0^2) \right] \\ &= \text{const. } - \frac{n}{2}\log \sigma^2 - \frac{1}{2\sigma^2} \underline{\sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0^2)}_{\text{MSE}} \end{aligned}$$
まずは$\sigma^2$に関係なく. mean squared error(MSE)
$$\sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0)^2$$
を最大化する$\theta, \theta_0$をみつける.
これは行列
$\mathbf{X} = \left(\begin{array}{} \mathbf{x}_1^{(1)} & \mathbf{x}_1^{(2)} &\cdots & \mathbf{x}_1^{(d)} & 1 \\ \mathbf{x}_2^{(1)} & \mathbf{x}_2^{(2)} & \cdots & \mathbf{x}_2^{(d)} & 1 \\ \vdots \\ \mathbf{x}_n^{(1)} & \cdots & \cdots & \mathbf{x}_n^{(d)} & 1 \end{array} \right)$ ( $\mathbf{x}_t^{i}$はtraining data の$t$番目のexampleの第$i$次元とする)
と$\mathbf{y} = (y_1, ..., y_n)^T$を使うと,
$$\begin{aligned} \text{MSE } = \sum_{t=1}^n \left(y_t - \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] \right)^2 &= \sum \left( y_t - [\mathbf{x}_t^T, 1] \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \right)^2 \\ &= \left\| \left[\begin{array}{} y_1 \\ \vdots \\ y_n \end{array} \right] - \left[ \begin{array}{} \mathbf{x}_1^T, 1 \\ \vdots \\ \mathbf{x}_n^T, 1 \end{array} \right] \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \right\|^2 \\ &= \left\| \mathbf{y} - \mathbf{X}\left[\begin{array}{} \theta \\ \theta_0\end{array} \right] \right\|^2 \\ &= \mathbf{y}^T \mathbf{y} - 2 \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \mathbf{X}^T \mathbf{y} + \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \mathbf{X}^T \mathbf{X} \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \end{aligned}$$
となる.これを最小化する解を$\hat{\theta}, \hat{\theta_0}$とすると,
$$\left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0}\end{array} \right] = \mathbf{(X^T X)^{-1} X^T y} \ \ \ \ (14)$$
である. これが$\mathbf{y}$の関数と考えると線形であり,この性質は後で使う.
$\hat{\sigma^2}$は, $\hat{\theta}, \hat{\theta_0}$をによってMSEの最小値を与えられた後で,
$$\hat{\sigma^2} = \frac{1}{n} \sum (y_t - \hat{\theta}^T \mathbf{x}_t - \hat{\theta_0})^2$$
で決定できる.

Bias and Variance of the Parameter Estimates

$\mathbf{x}, y$が,未知のパラメータ$\theta^*, \theta_0^*, \sigma^*$の線形モデルに従っていて,(14)で計算した$\hat{\theta}, \hat{\theta_0}$がどれほど適切なのかを議論する. このとき$\hat{\theta}, \hat{\theta_0}$は$\theta^*, \theta_0^*$の推測と考えることが出来る.仮定より
$$y_t = \theta^{*T} \mathbf{x}_t + \theta^*_0 + \epsilon_t, \ \epsilon_t \sim N(0, \sigma^{*2})$$
が成り立つ.
$$\mathbf{y} = \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{e},\ \mathbf{e} = (\epsilon_1, ... , \epsilon_n)^T$$
と行列表示する.$E[\mathbf{e}]=0, E[\mathbf{ee^T}] = \sigma^{*2} \mathbf{I}$で,また$\mathbf{X}$と$\mathbf{e}$は独立である. (14)に代入して,
$$\begin{aligned} \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] &= (\mathbf{X^T X})^{-1} \mathbf{X}^T ( \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{e}) \\ &=(\mathbf{X^T X})^{-1} \mathbf{X}^T \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + (\mathbf{X^T X})^{-1} \mathbf{X}^T \mathbf{e} \\ &= \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{(X^TX)^{-1} X^T e} \end{aligned}$$
である. $E[\mathbf{e}] = \mathbf{0}$だから, 両辺の期待値を取れば,
$$E\left[ \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right]\right] = \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right]$$
である. このように,推測値の期待値が真の値に一致するとき, 推測はunbiased(不偏)であるという.
さらに,
$$\begin{aligned} cov[ \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] | \mathbf{X}] = \sigma^{*2} (\mathbf{X}^T \mathbf{X})^{-1} \end{aligned}$$
であって,つまり$\hat{\theta}, \hat{\theta_0}$は$\mathbf{X}$のノイズを受け継ぎ,そのノイズがどのような形をしているかは$\mathbf{X}$の関数として書ける.
さて,
$$\begin{aligned} E[\|\mathbf{z}-\mathbf{z}^*\|^2] &= E[ \|\mathbf{z}-E[\mathbf{z}] + E[\mathbf{z}] - \mathbf{z}^* \| ^2 \\ &=E[\|\mathbf{z}-E[\mathbf{z}]\|^2] + 2E[(\mathbf{z} - E[\mathbf{z}])^T](E[\mathbf{z}] - \mathbf{z}^*) + \|E[\mathbf{z}] - \mathbf{z}^*\|^2 \\ &= \underline{E[\|\mathbf{z}-E[\mathbf{z}]]\|^2}_{\text{variance}^2} + \underline{\|E[\mathbf{z}] - \mathbf{z}^*\|^2}_{\text{bias}^2} \end{aligned}$$
が任意の$\mathbf{z}$に $\mathbf{z}^*$を固定するたびに成り立つ. さらにvarianceは
$$\begin{aligned}E[\|\mathbf{z}-E[\mathbf{z}]\|^2] &= E[(\mathbf{z}-E[\mathbf{z}])^T (\mathbf{z} - E[\mathbf{z})] \\ &=E\left[ Tr [(\mathbf{z}-E[\mathbf{z}])][\mathbf{z}-E[\mathbf{z}]]^T \right] \\ &= Tr\left[ E\left[ (\mathbf{z}-E[\mathbf{z}])(\mathbf{z} -E[\mathbf{z}])^T \right]\right] \\ &= Tr[cov(\mathbf{z})] \end{aligned}$$

以上から, biasが$\mathbf{0}$であることを考えれば
$$\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}$$
さらに,
$$\begin{aligned} \mathbf{X^TX} &= \sum_{t=1}^n \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] [\mathbf{x}^T_t, 1] \\ &= n \cdot \frac{1}{n}\sum_{t=1}^n \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] [\mathbf{x}^T_t, 1] \\ &\sim n \cdot E_{\mathbf{x} \sim P} \left[ \left[\begin{array}{} \mathbf{x} \\ 1 \end{array} \right] [\mathbf{x}^T, 1]\right] = n \cdot \mathbf{C} \\ (\mathbf{C} : &\text{もとの分布によって決まる定数行列}) \end{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] \sim \frac{\sigma^{*2}}{n} \cdot Tr[\mathbf{C}^{-1}]$$
すなわち,$n$が十分大きいとき,推定したパラメータの分散は$\frac{\sigma^{*2}}{n} \cdot Tr[\mathbf{C}^{-1}]$である.