机器学习笔记：LS、Rddge、Lasso、最小一乘法推导
基础概念
假设
w
\mathbf w
w是一件事情的原因，而
y
y
y是一件事情的结果。
先验概率：
p
(
w
)
p(\mathbf w)
p(w)代表原因发生的概率
似然函数验概率：
L
(
w
)
=
p
(
y
∣
w
)
L(\mathbf w) = p(y|\mathbf w)
L(w)=p(y∣w)代表已知原因的情况下由因推出相应结果的概率
后验概率：
p
(
w
∣
y
)
p(\mathbf w|y)
p(w∣y)代表已知结果的情况下由果推因的概率
贝叶斯公式：
p
(
w
∣
y
)
=
p
(
y
∣
w
)
p
(
w
)
p
(
y
)
p(\mathbf w|y) = \dfrac{p(y|\mathbf w)p(\mathbf w)}{p(y)}
p(w∣y)=p(y)p(y∣w)p(w)
最大似然估计(Maximum Likelihood, ML)：
arg max
w
L
(
w
)
=
p
(
y
∣
w
)
\argmax\limits_{\mathbf w}L(\mathbf w) = p(y|\mathbf w)
wargmaxL(w)=p(y∣w)
最大后验估计(Maxaposterio , MAP)：
arg max
w
p
(
w
∣
y
)
=
p
(
y
∣
w
)
p
(
w
)
p
(
y
)
\argmax\limits_{\mathbf w}p(\mathbf w|y) = \dfrac{p(y|\mathbf w)p(\mathbf w)}{p(y)}
wargmaxp(w∣y)=p(y)p(y∣w)p(w)，由于待估计参数是
w
\mathbf w
w，分母项与
w
\mathbf w
w无关，因此可以省略得到最大后验估计问题为
arg max
w
p
(
y
∣
w
)
p
(
w
)
=
L
(
w
)
p
(
w
)
\argmax\limits_{\mathbf w}p(y|\mathbf w)p(\mathbf w)=L(\mathbf w)p(\mathbf w)
wargmaxp(y∣w)p(w)=L(w)p(w)，可以看到最大后验估计额外需要待估计参数的先验分布。
线性回归问题
y
=
∑
j
=
1
d
=
x
T
w
+
ϵ
y=\sum_{j=1}^d = {\mathbf x}^T{\mathbf w}+\epsilon
y=j=1∑d=xTw+ϵ
其中
x
∈
R
d
×
1
{\mathbf x} \in {\mathbb R}^{d\times 1}
x∈Rd×1为输入参数，
w
∈
R
d
×
1
{\mathbf w} \in {\mathbb R}^{d\times 1}
w∈Rd×1为线性回归参数，
d
d
d为输入参数特征维度。
ϵ
\epsilon
ϵ为噪声扰动。假设线性回归的训练数据总共有
n
n
n个，即
X
=
[
x
1
,
⋯
,
x
n
]
∈
R
d
×
n
{\mathbf X}=[{\mathbf x_1},\cdots,{\mathbf x_n}]\in {\mathbb R}^{d\times n}
X=[x1,⋯,xn]∈Rd×n，则上式可以表达为
y
=
X
T
w
+
ϵ
{\mathbf y}={\mathbf X}^T{\mathbf w}+{\mathbb \epsilon}
y=XTw+ϵ
其中
ϵ
=
[
ϵ
1
,
⋯
,
ϵ
n
]
T
∈
R
d
×
1
{\mathbf \epsilon}=[\epsilon_1,\cdots,\epsilon_n]^T\in {\mathbb R}^{d\times 1}
ϵ=[ϵ1,⋯,ϵn]T∈Rd×1，这里没有考虑偏置项，这是因为偏置项也可以建模进
w
{\mathbf w}
w中作为第一项并且
x
{\mathbf x}
x的第一项为1代表将偏置加入。
采用什么方法来完成这个回归有许多种方式，常见的有LS、最小一乘法、Ridge、Lasso方法，如何选取这些方法与偏差 ϵ \epsilon ϵ的分布假设有关，同时还根据选择不同准则例如选择最大似然准则或是最大后验准则有关，也与待估计参数 w {\mathbf w} w的先验分布假设有关。
LS最小二乘法推导
假设误差
ϵ
i
∼
N
(
0
,
σ
2
)
\epsilon_i \sim N\left( {0},\sigma^2 \right)
ϵi∼N(0,σ2)是正态分布，则
y
i
∼
N
(
x
i
T
w
,
σ
2
)
y_i \sim N\left( {\mathbf x}_i^T{\mathbf w},\sigma^2 \right)
yi∼N(xiTw,σ2)。采用最大似然准则(对数似然)，则问题可以表述为
arg max
w
L
(
w
)
=
l
n
(
p
(
y
∣
w
)
)
=
l
n
∏
i
=
1
n
1
σ
2
π
e
x
p
(
−
1
2
(
y
i
−
x
i
T
w
σ
)
2
)
=
−
1
2
σ
2
∑
i
=
1
n
∣
y
i
−
x
i
T
w
∣
2
−
n
l
n
σ
2
π
=
−
1
2
σ
2
∥
y
−
X
T
w
∥
2
2
−
n
l
n
σ
2
π
\argmax\limits_{\mathbf w}L(\mathbf w) = {\rm ln}(p(y|\mathbf w))= {\rm ln}\prod_{i=1}^n\frac{1}{\sigma\sqrt{2\pi}}{\rm exp}\left(-\frac{1}{2} \left( \frac{y_i-{\mathbf x}_i^T{\mathbf w}}{\sigma} \right)^2 \right)\\ =-\frac{1}{2\sigma^2}\sum_{i=1}^n\left| y_i-{\mathbf x}_i^T{\mathbf w} \right|^2-n{\rm ln}\sigma\sqrt{2\pi}\\ =-\frac{1}{2\sigma^2}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2-n{\rm ln}\sigma\sqrt{2\pi}
wargmaxL(w)=ln(p(y∣w))=lni=1∏nσ2π
1exp(−21(σyi−xiTw)2)=−2σ21i=1∑n∣∣yi−xiTw∣∣2−nlnσ2π
=−2σ21∥y−XTw∥22−nlnσ2π
等效于一个最小二乘问题
arg min
w
∥
y
−
X
T
w
∥
2
2
\argmin\limits_{\mathbf w}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2
wargmin∥y−XTw∥22
最小一乘法
假设误差
ϵ
i
∼
L
a
p
l
a
c
e
(
0
,
σ
)
\epsilon_i \sim Laplace\left( {0},\sigma \right)
ϵi∼Laplace(0,σ)是拉普拉斯分布，则
y
i
∼
L
a
p
l
a
c
e
(
x
i
T
w
,
σ
)
y_i \sim Laplace\left( {\mathbf x}_i^T{\mathbf w},\sigma \right)
yi∼Laplace(xiTw,σ)。采用最大似然准则(对数似然)，则问题可以表述为
arg max
w
L
(
w
)
=
l
n
(
p
(
y
∣
w
)
)
=
l
n
∏
i
=
1
n
1
2
σ
e
x
p
(
−
∣
y
i
−
x
i
T
w
∣
σ
)
=
−
1
σ
∑
i
=
1
n
∣
y
i
−
x
i
T
w
∣
−
n
l
n
2
σ
=
−
1
σ
∥
y
−
X
T
w
∥
1
−
n
l
n
2
σ
\argmax\limits_{\mathbf w}L(\mathbf w) = {\rm ln}(p(y|\mathbf w))= {\rm ln}\prod_{i=1}^n\frac{1}{2\sigma}{\rm exp}\left(- \frac{\left|y_i-{\mathbf x}_i^T{\mathbf w}\right|}{\sigma} \right) \\ =-\frac{1}{\sigma}\sum_{i=1}^n\left| y_i-{\mathbf x}_i^T{\mathbf w} \right|-n{\rm ln}2\sigma\\ =-\frac{1}{\sigma}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_1-n{\rm ln}2\sigma
wargmaxL(w)=ln(p(y∣w))=lni=1∏n2σ1exp(−σ∣∣yi−xiTw∣∣)=−σ1i=1∑n∣∣yi−xiTw∣∣−nln2σ=−σ1∥y−XTw∥1−nln2σ
等效于一个最小一乘问题
arg min
w
∥
y
−
X
T
w
∥
1
\argmin\limits_{\mathbf w}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_1
wargmin∥y−XTw∥1
Ridge
假设误差
ϵ
i
∼
N
(
0
,
σ
1
2
)
\epsilon_i \sim N\left( {0},\sigma_1^2 \right)
ϵi∼N(0,σ12)是正态分布，则
y
i
∼
N
(
x
i
T
w
,
σ
2
2
)
y_i \sim N\left( {\mathbf x}_i^T{\mathbf w},\sigma_2^2 \right)
yi∼N(xiTw,σ22)。采用最大后验估计，假设先验信息是待估计参数
w
i
∼
N
(
0
,
σ
2
)
{w}_i \sim N\left( {0},\sigma^2 \right)
wi∼N(0,σ2)是正态分布，则问题可以表述为
arg max
w
L
(
w
)
=
l
n
(
p
(
y
∣
w
)
p
(
w
)
)
=
l
n
∏
i
=
1
n
1
σ
1
2
π
e
x
p
(
−
1
2
(
y
i
−
x
i
T
w
σ
1
)
2
)
⋅
∏
j
=
1
d
1
σ
2
2
π
e
x
p
(
−
1
2
(
w
j
σ
2
)
2
)
=
−
1
2
σ
1
2
∑
i
=
1
n
∣
y
i
−
x
i
T
w
∣
2
−
n
l
n
σ
1
2
π
−
1
2
σ
2
2
∑
j
=
1
d
∣
w
j
∣
2
−
d
l
n
σ
2
2
π
=
−
1
2
σ
1
2
∥
y
−
X
T
w
∥
2
2
−
1
2
σ
2
2
∥
w
∥
2
2
−
n
l
n
σ
1
2
π
−
d
l
n
σ
2
2
π
\argmax\limits_{\mathbf w}L(\mathbf w) = {\rm ln}(p(y|\mathbf w)p(\mathbf w))\\ = {\rm ln}\prod_{i=1}^n\frac{1}{\sigma_1\sqrt{2\pi}}{\rm exp}\left(-\frac{1}{2} \left( \frac{y_i-{\mathbf x}_i^T{\mathbf w}}{\sigma_1} \right)^2 \right)\cdot \prod_{j=1}^d\frac{1}{\sigma_2\sqrt{2\pi}}{\rm exp}\left(-\frac{1}{2} \left( \frac{w_j}{\sigma_2} \right)^2 \right)\\ =-\frac{1}{2\sigma_1^2}\sum_{i=1}^n\left| y_i-{\mathbf x}_i^T{\mathbf w} \right|^2-n{\rm ln}\sigma_1\sqrt{2\pi}-\frac{1}{2\sigma_2^2}\sum_{j=1}^d\left| w_j\right|^2-d{\rm ln}\sigma_2\sqrt{2\pi}\\ =-\frac{1}{2\sigma_1^2}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2-\frac{1}{2\sigma_2^2}\| {\mathbf w} \|_2^2-n{\rm ln}\sigma_1\sqrt{2\pi}-d{\rm ln}\sigma_2\sqrt{2\pi}
wargmaxL(w)=ln(p(y∣w)p(w))=lni=1∏nσ12π
1exp(−21(σ1yi−xiTw)2)⋅j=1∏dσ22π
1exp(−21(σ2wj)2)=−2σ121i=1∑n∣∣yi−xiTw∣∣2−nlnσ12π
−2σ221j=1∑d∣wj∣2−dlnσ22π
=−2σ121∥y−XTw∥22−2σ221∥w∥22−nlnσ12π
−dlnσ22π
等效于一个Ridge回归问题
arg min
w
∥
y
−
X
T
w
∥
2
2
+
λ
∥
w
∥
2
2
\argmin\limits_{\mathbf w}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2+\lambda\| {\mathbf w} \|_2^2
wargmin∥y−XTw∥22+λ∥w∥22
Lasso
假设误差 ϵ i ∼ N ( 0 , σ 2 ) \epsilon_i \sim N\left( {0},\sigma^2 \right) ϵi∼N(0,σ2)是正态分布，并且采用最大后验估计，我们假设先验信息是待估计参数 w i ∼ L a p l a c e ( 0 , σ ) {w}_i \sim Laplace\left( {0},\sigma \right) wi∼Laplace(0,σ)是拉普拉斯分布分布。
假设误差
ϵ
i
∼
N
(
0
,
σ
1
2
)
\epsilon_i \sim N\left( {0},\sigma_1^2 \right)
ϵi∼N(0,σ12)是正态分布，则
y
i
∼
N
(
x
i
T
w
,
σ
2
2
)
y_i \sim N\left( {\mathbf x}_i^T{\mathbf w},\sigma_2^2 \right)
yi∼N(xiTw,σ22)。采用最大后验估计，假设先验信息是待估计参数
w
i
∼
L
a
p
l
a
c
e
(
0
,
σ
)
{w}_i \sim Laplace\left( {0},\sigma \right)
wi∼Laplace(0,σ)是拉普拉斯分布分布，则问题可以表述为
arg max
w
L
(
w
)
=
l
n
(
p
(
y
∣
w
)
p
(
w
)
)
=
l
n
∏
i
=
1
n
1
σ
1
2
π
e
x
p
(
−
1
2
(
y
i
−
x
i
T
w
σ
1
)
2
)
⋅
∏
j
=
1
d
1
2
σ
2
e
x
p
(
−
∣
w
j
∣
σ
2
)
=
−
1
2
σ
1
2
∑
i
=
1
n
∣
y
i
−
x
i
T
w
∣
2
−
n
l
n
σ
1
2
π
−
1
σ
2
∑
j
=
1
d
∣
w
j
∣
−
d
l
n
2
σ
2
=
−
1
2
σ
1
2
∥
y
−
X
T
w
∥
2
2
−
1
σ
2
∥
w
∥
1
−
n
l
n
σ
1
2
π
−
d
l
n
2
σ
2
\argmax\limits_{\mathbf w}L(\mathbf w) = {\rm ln}(p(y|\mathbf w)p(\mathbf w))\\ = {\rm ln}\prod_{i=1}^n\frac{1}{\sigma_1\sqrt{2\pi}}{\rm exp}\left(-\frac{1}{2} \left( \frac{y_i-{\mathbf x}_i^T{\mathbf w}}{\sigma_1} \right)^2 \right)\cdot \prod_{j=1}^d\frac{1}{2\sigma_2}{\rm exp}\left(- \frac{\left| w_j \right|}{\sigma_2} \right)\\ =-\frac{1}{2\sigma_1^2}\sum_{i=1}^n\left| y_i-{\mathbf x}_i^T{\mathbf w} \right|^2-n{\rm ln}\sigma_1\sqrt{2\pi}-\frac{1}{\sigma_2}\sum_{j=1}^d\left| w_j\right|-d{\rm ln}2\sigma_2\\ =-\frac{1}{2\sigma_1^2}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2-\frac{1}{\sigma_2}\| {\mathbf w} \|_1-n{\rm ln}\sigma_1\sqrt{2\pi}-d{\rm ln}2\sigma_2
wargmaxL(w)=ln(p(y∣w)p(w))=lni=1∏nσ12π
1exp(−21(σ1yi−xiTw)2)⋅j=1∏d2σ21exp(−σ2∣wj∣)=−2σ121i=1∑n∣∣yi−xiTw∣∣2−nlnσ12π
−σ21j=1∑d∣wj∣−dln2σ2=−2σ121∥y−XTw∥22−σ21∥w∥1−nlnσ12π
−dln2σ2
等效于一个Lasso问题
arg min
w
∥
y
−
X
T
w
∥
2
2
+
λ
∥
w
∥
1
\argmin\limits_{\mathbf w}\| {\mathbf y}-{\mathbf X}^T{\mathbf w} \|_2^2+\lambda\| {\mathbf w} \|_1
wargmin∥y−XTw∥22+λ∥w∥1