東京大学 情報理工学系研究科 コンピュータ科学専攻 2020年8月実施 専門科目 問題4 Author zephyr
Description Let R \mathbb{R} R T \mathbf{T} T w = ( w 1 , w 2 , … , w d ) T ∈ R d \mathbf{w} = (w_1, w_2, \ldots, w_d)^\mathbf{T} \in \mathbb{R}^d w = ( w 1 , w 2 , … , w d ) T ∈ R d d d d ∥ w ∥ 2 \|\mathbf{w}\|_2 ∥ w ∥ 2 ∥ w ∥ 2 = w 1 2 + w 2 2 + … + w d 2 \|\mathbf{w}\|_2 = \sqrt{w_1^2 + w_2^2 + \ldots + w_d^2} ∥ w ∥ 2 = w 1 2 + w 2 2 + … + w d 2 x 1 , x 2 ∈ R d \mathbf{x}_1, \mathbf{x}_2 \in \mathbb{R}^d x 1 , x 2 ∈ R d x 1 T x 2 ∈ R \mathbf{x}_1^\mathbf{T} \mathbf{x}_2 \in \mathbb{R} x 1 T x 2 ∈ R d × d d \times d d × d A ∈ R d × d \mathbf{A} \in \mathbb{R}^{d \times d} A ∈ R d × d ∥ w ∥ A = w T A w \|\mathbf{w}\|_{\mathbf{A}} = \sqrt{\mathbf{w}^\mathbf{T} \mathbf{A} \mathbf{w}} ∥ w ∥ A = w T Aw t r ( B ) \mathbf{tr}(\mathbf{B}) tr ( B ) B \mathbf{B} B
Consider the problem of predicting a real-valued label y ∈ R y \in \mathbb{R} y ∈ R d d d x ∈ R d \mathbf{x} \in \mathbb{R}^d x ∈ R d n n n
{ ( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , 2 , … , n } \{(\mathbf{x}_i, y_i) \mid \mathbf{x}_i \in \mathbb{R}^d, y_i \in \mathbb{R}, i = 1, 2, \ldots, n\} {( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , 2 , … , n } are given where ( x i , y i ) (\mathbf{x}_i, y_i) ( x i , y i ) y i y_i y i x i \mathbf{x}_i x i d d d w ∗ ∈ R d \mathbf{w}^* \in \mathbb{R}^d w ∗ ∈ R d ϵ i ( i = 1 , 2 , … , n ) \epsilon_i (i = 1, 2, \ldots, n) ϵ i ( i = 1 , 2 , … , n )
y i = w ∗ T x i + ϵ i ( i = 1 , 2 , … , n ) , y_i = \mathbf{w}^{*\mathbf{T}} \mathbf{x}_i + \epsilon_i \quad (i = 1, 2, \ldots, n), y i = w ∗ T x i + ϵ i ( i = 1 , 2 , … , n ) , where the expectation E [ ϵ i ] = 0 \mathbb{E}[\epsilon_i] = 0 E [ ϵ i ] = 0 V [ ϵ i ] = σ 2 > 0 ( i = 1 , … , n ) \mathbb{V}[\epsilon_i] = \sigma^2 > 0 \quad (i = 1, \ldots, n) V [ ϵ i ] = σ 2 > 0 ( i = 1 , … , n )
X = [ x 1 , … , x n ] T ∈ R n × d , Y = [ y 1 , … , y n ] T ∈ R n , ϵ = [ ϵ 1 , … , ϵ n ] T ∈ R n . \mathbf{X} = [\mathbf{x}_1, \ldots, \mathbf{x}_n]^\mathbf{T} \in \mathbb{R}^{n \times d}, \quad \mathbf{Y} = [y_1, \ldots, y_n]^\mathbf{T} \in \mathbb{R}^n, \quad \mathbf{\epsilon} = [\epsilon_1, \ldots, \epsilon_n]^\mathbf{T} \in \mathbb{R}^n. X = [ x 1 , … , x n ] T ∈ R n × d , Y = [ y 1 , … , y n ] T ∈ R n , ϵ = [ ϵ 1 , … , ϵ n ] T ∈ R n . We also use the symbol Φ = 1 n X T X ∈ R d × d \mathbf{\Phi} = \frac{1}{n} \mathbf{X}^\mathbf{T} \mathbf{X} \in \mathbb{R}^{d \times d} Φ = n 1 X T X ∈ R d × d Φ \mathbf{\Phi} Φ E ϵ [ ⋅ ] \mathbb{E}_{\mathbf{\epsilon}}[\cdot] E ϵ [ ⋅ ]
We formulate the learning of a predictor f ( x ) = w ^ T x f(\mathbf{x}) = \hat{\mathbf{w}}^\mathbf{T} \mathbf{x} f ( x ) = w ^ T x
w ^ = arg min w ∈ R d L ( w ) \mathbf{\hat{w}} = \mathop{\arg\min}\limits_{\mathbf{w} \in \mathbb{R}^d} L(\mathbf{w}) w ^ = w ∈ R d arg min L ( w ) L ( w ) = 1 2 n ∑ i = 1 n ( y i − w T x i ) 2 = 1 2 n ∥ Y − X w ∥ 2 2 . L(\mathbf{w}) = \frac{1}{2n} \sum_{i=1}^{n} (y_i - \mathbf{w}^\mathbf{T} \mathbf{x}_i)^2 = \frac{1}{2n} \|\mathbf{Y} - \mathbf{Xw}\|_2^2. L ( w ) = 2 n 1 i = 1 ∑ n ( y i − w T x i ) 2 = 2 n 1 ∥ Y − Xw ∥ 2 2 . Answer the following questions. Describe not only an answer but also the derivation process.
(1) Express w ^ \mathbf{\hat{w}} w ^ X , Y , Φ \mathbf{X}, \mathbf{Y}, \mathbf{\Phi} X , Y , Φ n n n
(2) Suppose we wish to express E ϵ [ L ( w ) ] \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w})] E ϵ [ L ( w )] 1 2 ∥ w − w ∗ ∥ A 2 + b \frac{1}{2} \|\mathbf{w} - \mathbf{w}^*\|_{\mathbf{A}}^2 + b 2 1 ∥ w − w ∗ ∥ A 2 + b A ∈ R d × d \mathbf{A} \in \mathbb{R}^{d \times d} A ∈ R d × d b > 0 b > 0 b > 0 Φ \mathbf{\Phi} Φ σ 2 \sigma^2 σ 2
(3) Suppose we wish to express E ϵ [ L ( w ^ ) ] − E ϵ [ L ( w ∗ ) ] \mathbb{E}_{\mathbf{\epsilon}}[L(\hat{\mathbf{w}})] - \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w^*})] E ϵ [ L ( w ^ )] − E ϵ [ L ( w ∗ )] σ 2 2 n t r ( B ) \frac{\sigma^2}{2n} \mathbf{tr}(\mathbf{B}) 2 n σ 2 tr ( B ) B ∈ R d × d \mathbf{B} \in \mathbb{R}^{d \times d} B ∈ R d × d X \mathbf{X} X
(4) Explain what problem arises when Φ \mathbf{\Phi} Φ
Kai (1)
To find the optimal weight vector w ^ \mathbf{\hat{w}} w ^ L ( w ) L(\mathbf{w}) L ( w )
L ( w ) = 1 2 n ∑ i = 1 n ( y i − w T x i ) 2 = 1 2 n ∥ Y − X w ∥ 2 2 . L(\mathbf{w}) = \frac{1}{2n} \sum_{i=1}^{n} (y_i - \mathbf{w}^\mathbf{T} \mathbf{x}_i)^2 = \frac{1}{2n} \|\mathbf{Y} - \mathbf{Xw}\|_2^2. L ( w ) = 2 n 1 i = 1 ∑ n ( y i − w T x i ) 2 = 2 n 1 ∥ Y − Xw ∥ 2 2 . To minimize L ( w ) L(\mathbf{w}) L ( w ) L ( w ) L(\mathbf{w}) L ( w ) w \mathbf{w} w
∇ L ( w ) = − 1 n X T ( Y − X w ) = 0. \nabla L(\mathbf{w}) = -\frac{1}{n} \mathbf{X}^\mathbf{T} (\mathbf{Y} - \mathbf{Xw}) = 0. ∇ L ( w ) = − n 1 X T ( Y − Xw ) = 0. Solving for w \mathbf{w} w
X T Y = X T X w . \mathbf{X}^\mathbf{T} \mathbf{Y} = \mathbf{X}^\mathbf{T} \mathbf{X} \mathbf{w}. X T Y = X T Xw . Thus, the optimal weight vector w ^ \mathbf{\hat{w}} w ^
w ^ = ( X T X ) − 1 X T Y = Φ − 1 ( 1 n X T Y ) . \mathbf{\hat{w}} = (\mathbf{X}^\mathbf{T} \mathbf{X})^{-1} \mathbf{X}^\mathbf{T} \mathbf{Y} = \mathbf{\Phi}^{-1} \left( \frac{1}{n} \mathbf{X}^\mathbf{T} \mathbf{Y} \right). w ^ = ( X T X ) − 1 X T Y = Φ − 1 ( n 1 X T Y ) . (2)
To express E ϵ [ L ( w ) ] \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w})] E ϵ [ L ( w )] L ( w ) L(\mathbf{w}) L ( w )
L ( w ) = 1 2 n ( Y − X w ) T ( Y − X w ) . L(\mathbf{w}) = \frac{1}{2n} (\mathbf{Y} - \mathbf{Xw})^\mathbf{T} (\mathbf{Y} - \mathbf{Xw}). L ( w ) = 2 n 1 ( Y − Xw ) T ( Y − Xw ) . Using the data generation model y i = w ∗ T x i + ϵ i y_i = \mathbf{w}^{*\mathbf{T}} \mathbf{x}_i + \epsilon_i y i = w ∗ T x i + ϵ i Y = X w ∗ + ϵ \mathbf{Y} = \mathbf{X} \mathbf{w}^* + \mathbf{\epsilon} Y = X w ∗ + ϵ
E ϵ [ L ( w ) ] = 1 2 n E ϵ [ ( X w ∗ + ϵ − X w ) T ( X w ∗ + ϵ − X w ) ] . \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w})] = \frac{1}{2n} \mathbb{E}_{\mathbf{\epsilon}}\left[(\mathbf{X} \mathbf{w}^* + \mathbf{\epsilon} - \mathbf{X} \mathbf{w})^\mathbf{T} (\mathbf{X} \mathbf{w}^* + \mathbf{\epsilon} - \mathbf{X} \mathbf{w})\right]. E ϵ [ L ( w )] = 2 n 1 E ϵ [ ( X w ∗ + ϵ − Xw ) T ( X w ∗ + ϵ − Xw ) ] . Expanding and using the properties of expectation:
E ϵ [ L ( w ) ] = 1 2 n [ ( w − w ∗ ) T X T X ( w − w ∗ ) + E ϵ [ ϵ T ϵ ] ] . \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w})] = \frac{1}{2n} \left[(\mathbf{w} - \mathbf{w}^*)^\mathbf{T} \mathbf{X}^\mathbf{T} \mathbf{X} (\mathbf{w} - \mathbf{w}^*) + \mathbb{E}_{\mathbf{\epsilon}}[\mathbf{\epsilon}^\mathbf{T} \mathbf{\epsilon}]\right]. E ϵ [ L ( w )] = 2 n 1 [ ( w − w ∗ ) T X T X ( w − w ∗ ) + E ϵ [ ϵ T ϵ ] ] . Since E [ ϵ ] = 0 \mathbb{E}[\mathbf{\epsilon}] = 0 E [ ϵ ] = 0 E [ ϵ ϵ T ] = σ 2 I \mathbb{E}[\mathbf{\epsilon}\mathbf{\epsilon}^\mathbf{T}] = \sigma^2 \mathbf{I} E [ ϵ ϵ T ] = σ 2 I
E ϵ [ L ( w ) ] = 1 2 ∥ w − w ∗ ∥ Φ 2 + σ 2 2 . \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w})] = \frac{1}{2} \|\mathbf{w} - \mathbf{w}^*\|_{\mathbf{\Phi}}^2 + \frac{\sigma^2}{2}. E ϵ [ L ( w )] = 2 1 ∥ w − w ∗ ∥ Φ 2 + 2 σ 2 . Here, the matrix A \mathbf{A} A Φ \mathbf{\Phi} Φ b b b σ 2 2 \frac{\sigma^2}{2} 2 σ 2
(3)
We have:
E ϵ [ L ( w ^ ) ] = σ 2 2 n . \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{\hat{w}})] = \frac{\sigma^2}{2n}. E ϵ [ L ( w ^ )] = 2 n σ 2 . Thus:
E ϵ [ L ( w ^ ) ] − E ϵ [ L ( w ∗ ) ] = 1 2 ( w ^ − w ∗ ) T Φ ( w ^ − w ∗ ) + σ 2 2 − σ 2 2 n . \mathbb{E}_{\mathbf{\epsilon}}[L(\hat{\mathbf{w}})] - \mathbb{E}_{\mathbf{\epsilon}}[L(\mathbf{w^*})] = \frac{1}{2} (\hat{\mathbf{w}} - \mathbf{w}^*)^\mathbf{T} \mathbf{\Phi} (\hat{\mathbf{w}} - \mathbf{w}^*) + \frac{\sigma^2}{2} - \frac{\sigma^2}{2n}. E ϵ [ L ( w ^ )] − E ϵ [ L ( w ∗ )] = 2 1 ( w ^ − w ∗ ) T Φ ( w ^ − w ∗ ) + 2 σ 2 − 2 n σ 2 . Therefore, the matrix B \mathbf{B} B Φ \mathbf{\Phi} Φ
(4)
When Φ \mathbf{\Phi} Φ w ^ \mathbf{\hat{w}} w ^
A common remedy is to add a regularization term to the loss function, which is known as Ridge Regression . The modified loss function becomes:
L ( w ) = 1 2 n ∥ Y − X w ∥ 2 2 + λ 2 ∥ w ∥ 2 2 , L(\mathbf{w}) = \frac{1}{2n} \|\mathbf{Y} - \mathbf{Xw}\|_2^2 + \frac{\lambda}{2} \|\mathbf{w}\|_2^2, L ( w ) = 2 n 1 ∥ Y − Xw ∥ 2 2 + 2 λ ∥ w ∥ 2 2 , where λ > 0 \lambda > 0 λ > 0
w ^ = ( Φ + λ I ) − 1 ( 1 n X T Y ) . \mathbf{\hat{w}} = (\mathbf{\Phi} + \lambda \mathbf{I})^{-1} \left( \frac{1}{n} \mathbf{X}^\mathbf{T} \mathbf{Y} \right). w ^ = ( Φ + λ I ) − 1 ( n 1 X T Y ) . Knowledge 机器学习 线性回归 最小二乘法 岭回归
解题技巧和信息
在回归问题中，当自变量之间存在共线性问题时，使用岭回归可以增加模型的稳定性并避免参数过大。理解最小二乘法的优化问题如何转化为矩阵求解问题是非常重要的。此外，加入正则化项可以有效地解决过拟合问题。
重点词汇
trace (迹) - 矩阵对角线元素之和regular matrix (正规矩阵) - 具有满秩的矩阵，即矩阵的行列式非零regularization (正则化) - 添加到损失函数的额外项，以约束模型复杂度并提高泛化能力
参考资料
The Elements of Statistical Learning , Trevor Hastie, Robert Tibshirani, and Jerome Friedman, Chap. 3Pattern Recognition and Machine Learning , Christopher Bishop, Chap. 4