机器学习-线性回归原理推导与算法描述
1. 概念
线性回归(LinearRegression)是一种通过属性的线性组合来进行预测的线性模型,其目的是找到一条直线或者一个平面或者更高维的超平面,使得预测值与真实值之间的误差最小化。
2. 特点
优点:结果具有很好的可解释性(w直观表达了各属性在预测中的重要性),计算熵不复杂。 缺点:对非线性数据拟合不好
适用数据类型:数值型和标称型数据
3. 原理推导
-
给定数据集 D = { ( x i , y i ) } i = 1 , m D=\left\{\left(x_{i}, y_{i}\right)\right\}_{i=1,}^{m} D={(xi,yi)}i=1,m 其中 x i = ( x i 1 , x i 2 , … , x i d ) , y i ∈ R x_{i}=\left(x_{i 1}, x_{i 2}, \ldots, x_{i d}\right), y_{i} \in R xi=(xi1,xi2,…,xid),yi∈R (线性回归的输出空间是整个实数空间) 。 m 。 m 。m 是样本数, d d d 是属性维度。
线性回归试图学得:f ( x i ) = w T x i + b ( 1 ) f\left(x_{i}\right)=w^{T} x_{i}+b (1) f(xi)=wTxi+b(1)
使得 f ( x i ) ≃ y i 0 f\left(x_{i}\right) \simeq y_{i_{0}} f(xi)≃yi0为便于讨论, 使 b = w 0 ⋅ x 0 , b=w_{0} \cdot x_{0,} b=w0⋅x0, 其中 x 0 = 1 ∘ x_{0}=1_{\circ} x0=1∘ 此时, w w w 就成为了 w = ( w 0 , w 1 , … , w d ) , x w=\left(w_{0}, w_{1}, \ldots, w_{d}\right), x w=(w0,w1,…,wd),x 就成为了 x i = ( 1 , x i 1 , … , x i d ) , x_{i}=\left(1, x_{i 1}, \ldots, x_{i d}\right), xi=(1,xi1,…,xid), 期望学 得的函数为 f ( x i ) = w T x i 0 f\left(x_{i}\right)=w^{T} x_{i_{0}} f(xi)=wTxi0
-
预测值和真实值之间都肯定存在差异 ε , \varepsilon, ε, 对于每个样本:
y i = w T x i + ε i ( 2 ) y_{i}=w^{T} x_{i}+\varepsilon_{i} (2) yi=wTxi+εi(2)
假设误差 ε i \varepsilon_{i} εi 是独立同分布的,并且服从高斯分布。即:
p ( ε i ) = 1 2 π σ exp ( − ε i 2 2 σ 2 ) ( 3 ) p\left(\varepsilon_{i}\right)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\varepsilon_{i}^{2}}{2 \sigma^{2}}\right) (3) p(εi)=2π σ1exp(−2σ2εi2)(3)
将 (2) 代入 (3) 中, 得到在已知参数 w w w 和数据 w i w_{i} wi 的情况下,预测值为 y i y_{i} yi 的条件概率:
p ( y i ∣ x i ; w ) = 1 2 π σ exp ( − ( y i − w T x i ) 2 2 σ 2 ) ( 4 ) p\left(y_{i} \mid x_{i} ; w\right)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}}\right) (4) p(yi∣xi;w)=2π σ1exp(−2σ2(yi−wTxi)2)(4) -
将 (4) 连乘得到在已知参数w和数据 x x x 的情况下,预测值为 y y y 的条件概率,这个条件概率在数值上等于,P(w∣x,y), 也就是在已知现有数据的条件下,w是真正参数的概率,即似然函数 (5) :
L ( w ) = ∏ i = 1 m p ( y i ∣ x i ; w ) = ∏ i = 1 m 1 2 π σ exp ( − ( y i − w T x i ) 2 2 σ 2 ) L(w)=\prod_{i=1}^{m} p\left(y_{i} \mid x_{i} ; w\right)=\prod_{i=1}^{m} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}}\right) L(w)=i=1∏mp(yi∣xi;w)=i=1∏m2π σ1exp(−2σ2(yi−wTxi)2)
为什么要引入似然函数:为了根据样本估计参数值。
为什么要对似然函数进行log变换:由于乘法难解,通过对数可以将乘法转换为加法, 简化计算。
对数似然函数:
ℓ
(
w
)
=
log
∏
i
=
1
m
1
2
π
σ
exp
(
−
(
y
i
−
w
T
x
i
)
2
2
σ
2
)
=
∑
i
=
1
m
log
1
2
π
σ
exp
(
−
(
y
i
−
w
T
x
i
)
2
2
σ
2
)
=
∑
i
=
1
m
log
1
2
π
σ
+
∑
i
=
1
m
log
(
exp
(
−
(
y
i
−
w
T
x
i
)
2
2
σ
2
)
)
=
m
log
1
2
π
σ
−
∑
i
=
1
m
(
y
i
−
w
T
x
i
)
2
2
σ
2
=
m
log
1
2
π
σ
−
1
σ
2
1
2
∑
i
=
1
m
(
y
i
−
w
T
x
i
)
2
\begin{array}{l} \ell(w)=\log \prod_{i=1}^{m} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}}\right) \\ =\sum_{i=1}^{m} \log \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}}\right) \\ =\sum_{i=1}^{m} \log \frac{1}{\sqrt{2 \pi} \sigma}+\sum_{i=1}^{m} \log \left(\exp \left(-\frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}}\right)\right) \\ =m \log \frac{1}{\sqrt{2 \pi} \sigma}-\sum_{i=1}^{m} \frac{\left(y_{i}-w^{T} x_{i}\right)^{2}}{2 \sigma^{2}} \\ =m \log \frac{1}{\sqrt{2 \pi} \sigma}-\frac{1}{\sigma^{2}} \frac{1}{2} \sum_{i=1}^{m}\left(y_{i}-w^{T} x_{i}\right)^{2} \end{array}
ℓ(w)=log∏i=1m2π
σ1exp(−2σ2(yi−wTxi)2)=∑i=1mlog2π
σ1exp(−2σ2(yi−wTxi)2)=∑i=1mlog2π
σ1+∑i=1mlog(exp(−2σ2(yi−wTxi)2))=mlog2π
σ1−∑i=1m2σ2(yi−wTxi)2=mlog2π
σ1−σ2121∑i=1m(yi−wTxi)2
得到目标函数:
J
(
w
)
=
1
2
∑
i
=
1
m
(
y
i
−
w
T
x
i
)
2
=
1
2
∥
[
y
1
−
w
T
x
1
y
2
−
w
T
x
2
⋯
y
m
−
w
T
x
m
]
∥
2
=
1
2
∥
[
y
1
y
2
⋯
y
m
]
−
w
T
[
x
1
x
2
⋯
x
m
]
∥
2
=
1
2
∥
y
−
w
T
X
∥
2
=
1
2
(
y
−
w
T
x
)
T
(
y
−
w
T
x
)
\begin{array}{c} J(w)=\frac{1}{2} \sum_{i=1}^{m}\left(y_{i}-w^{T} x_{i}\right)^{2} \\ =\frac{1}{2}\left\|\left[\begin{array}{c} y_{1}-w^{T} x_{1} \\ y_{2}-w^{T} x_{2} \\ \cdots \\ y_{m}-w^{T} x_{m} \end{array}\right]\right\|^{2}=\frac{1}{2}\left\|\left[\begin{array}{c} y_{1} \\ y_{2} \\ \cdots \\ y_{m} \end{array}\right]-w^{T}\left[\begin{array}{c} x_{1} \\ x_{2} \\ \cdots \\ x_{m} \end{array}\right]\right\|^{2} \\ =\frac{1}{2}\left\|y-w^{T} X\right\|^{2}=\frac{1}{2}\left(y-w^{T} x\right)^{T}\left(y-w^{T} x\right) \end{array}
J(w)=21∑i=1m(yi−wTxi)2=21∥∥∥∥∥∥∥∥⎣⎢⎢⎡y1−wTx1y2−wTx2⋯ym−wTxm⎦⎥⎥⎤∥∥∥∥∥∥∥∥2=21∥∥∥∥∥∥∥∥⎣⎢⎢⎡y1y2⋯ym⎦⎥⎥⎤−wT⎣⎢⎢⎡x1x2⋯xm⎦⎥⎥⎤∥∥∥∥∥∥∥∥2=21∥∥y−wTX∥∥2=21(y−wTx)T(y−wTx)
为什么要让目标函数越小越好:似然函数表示样本成为真实的概率,似然函数越大越好, 也就是目标函数 J ( w ) J(w) J(w) 越小越好。
-
目标函数是凸函数,只要找到一阶导数为0的位置, 就找到了最优解。
因此求偏导:
∂ J ( w ) ∂ w = 1 2 ∂ ∂ w ( ( y − w T x ) T ( y − w T x ) ) = 1 2 ∂ ∂ w ( ( y − X w ) T ( y − X w ) ) = 1 2 ∂ ∂ w ( w T X T X w − 2 w T X y + y T y ) = 1 2 ( X T X w + X T X w − 2 X y ) = X T X w − X y \begin{array}{l} \frac{\partial J(w)}{\partial w}=\frac{1}{2} \frac{\partial}{\partial w}\left(\left(y-w^{T} x\right)^{T}\left(y-w^{T} x\right)\right) \\ =\frac{1}{2} \frac{\partial}{\partial w}\left((y-X w)^{T}(y-X w)\right) \\ =\frac{1}{2} \frac{\partial}{\partial w}\left(w^{T} X^{T} X w-2 w^{T} X y+y^{T} y\right) \\ =\frac{1}{2}\left(X^{T} X w+X^{T} X w-2 X y\right) \\ =X^{T} X w-X y \end{array} ∂w∂J(w)=21∂w∂((y−wTx)T(y−wTx))=21∂w∂((y−Xw)T(y−Xw))=21∂w∂(wTXTXw−2wTXy+yTy)=21(XTXw+XTXw−2Xy)=XTXw−Xy -
令偏导等于0 :
∂ J ( w ) ∂ w = 0 \frac{\partial J(w)}{\partial w}=0 ∂w∂J(w)=0
得到:
X T X w = X y X^{T} X w=X y XTXw=Xy
情况一: X T X X^{T} X XTX 可逆, 唯一解。令公式 (10) 为零可得最优解为:
w ∗ = ( X T X ) − 1 X T y w^{*}=\left(X^{T} X\right)^{-1} X^{T} y w∗=(XTX)−1XTy
学得的线性回归模型为:
y ^ = w T X = X T w = X T ( X T X ) − 1 X T y \hat{y}=w^{T} X=X^{T} w=X^{T}\left(X^{T} X\right)^{-1} X^{T} y y^=wTX=XTw=XT(XTX)−1XTy
情况二: X T X X^{T} X XTX 不可逆, 可能有多个解。选择哪一个解作为输出,将有学习算法的偏好决定, 常见的做法是增加入扰动。
w ∗ = ( X T X + λ I ) − 1 X T y w^{*}=\left(X^{T} X+\lambda I\right)^{-1} X^{T} y w∗=(XTX+λI)−1XTy
4. 算法描述
-
从数据集D出发, 构建输入矩阵X和输出向量y。
X = [ x 1 T x 2 T ⋯ x m T ] y = [ y 1 y 2 ⋯ y m ] X=\left[\begin{array}{c} x_{1}^{T} \\ x_{2}^{T} \\ \cdots \\ x_{m}^{T} \end{array}\right] \quad y=\left[\begin{array}{c} y_{1} \\ y_{2} \\ \cdots \\ y_{m} \end{array}\right] X=⎣⎢⎢⎡x1Tx2T⋯xmT⎦⎥⎥⎤y=⎣⎢⎢⎡y1y2⋯ym⎦⎥⎥⎤ -
计算伪逆(pseudo-inverse ) X + ) X^{+} )X+ 。
-
返回 w ∗ = X + y , w^{*}=X^{+} y, w∗=X+y, 学得的线性回归模型为 y ^ = w T X \hat{y}=w^{T} X y^=wTX 。
-
Γ \Gamma Γ & 线性回归
当 y y y 不再只是线性回归中用到的正态分布,而是扩大为指数族中的任一分布。这样得到的模型称为“广义线性模型” (generalized linear model ) : ): ):
y = g − 1 ( w T x + b ) y=g^{-1}\left(w^{T} x+b\right) y=g−1(wTx+b)其中函数 g (・)称为“联系函数" (link function)