监督学习应用(LinearRegression)与梯度下降

• 监督学习应用(LinearRegression)与梯度下降
  • 变量定义
  • 算法流程
  • Linear Regression
  • 一种更加广泛的表达方式

变量定义

m = 训练数据数目
x = 输入变量（特征） features
y = 输出变量（目标） target
(x, y) 训练数据
ith$i^{th}$ trainning example= {x(i),y(i)$x^{(i)},y^{(i)}$} 第i份训练数据

算法流程

graph TD

A[Trainning Set]-->B[Learning Algorithm]
B-->C[H, hypothesis 目标函数]

subgraph 

D[X_test]-->C
C-->E[Y_test]

end

Linear Regression

假设x0=1$x_0=1$, 则：
线性回归的假设函数为：

{h(x)=∑ni=0θixi=ΘTXn=features 特征数目$$\{\begin{array}{l}h(x)=\sum _{i=0}^n{\theta }_i{x}_i={\mathrm{\Theta }}^{T}X\\ n=features\text{ 特征数目}\end{array}$$

于是，我们的目标就是使得：

∑i=1m(hθ(x(i))−y(i))2$$\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$

最小
为了后期的计算方便，我们的目标修改为：

J(θ)=12∑i=1m(hθ(x(i))−y(i))2$$J(\theta )=\frac{1}{2}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$

search Algorithm使得J(θ)$J(\theta )$最小

1. 假设，初始化Θ=0⃗ $\mathrm{\Theta }=\overrightarrow{0}$
2. 保持改变Θ$\mathrm{\Theta }$，直到使得J(θ)$J(\theta )$最小

那么，如何改变Θ$\mathrm{\Theta }$ ??

梯度下降算法

为了使得J(θ)$J(\theta )$最小，我们求其偏导，则可以以此确定每一个参数的前进方向。
Θi:=Θi−αddΘiJ(Θi)${\mathrm{\Theta }}_i:={\mathrm{\Theta }}_i-\alpha \frac{\mathrm{d}}{d{\mathrm{\Theta }}_i}J({\mathrm{\Theta }}_i)$

简单的推导：

dJ(Θi)dΘidJ(Θi)dΘi=2⋅12∑i=1m(hθ(x(i))−y(i))d∑mi=1(hθ(x(i))−y(i))dΘi∵h(x)=∑i=0nθixi=ΘTX,y is real∴d∑mi=1(hθ(x(i))−y(i))dΘi=xi=∑i=1m(hθ(x(i)−y(i)))xi$$\begin{array}{rl}\frac{\mathrm{d}J({\mathrm{\Theta }}_i)}{\mathrm{d}{\mathrm{\Theta }}_i}& =2\cdot \frac{1}{2}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})\frac{\mathrm{d}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})}{\mathrm{d}{\mathrm{\Theta }}_i}\\ & \because h(x)=\sum _{i=0}^n{\theta }_i{x}_i={\mathrm{\Theta }}^{T}X,\text{y is real}\\ & \therefore \frac{\mathrm{d}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})}{\mathrm{d}{\mathrm{\Theta }}_i}=x_i\\ \frac{\mathrm{d}J({\mathrm{\Theta }}_i)}{\mathrm{d}{\mathrm{\Theta }}_i}& =\sum _{i=1}^m(h_{\theta }(x^{(i)}-y^{(i)}))x_i\end{array}$$

从而：
Θi:=Θi−α∑mi=1(hθ(x(i)−y(i)))xi${\mathrm{\Theta }}_i:={\mathrm{\Theta }}_i-\alpha \sum _{i=1}^m(h_{\theta }(x^{(i)}-y^{(i)}))x_i$
其中α$\alpha$是控制“步长”，控制前进的幅度。

如何确定J(θ)$J(\theta )$已经最小？
当J(θ)$J(\theta )$的值变化不大或者足够小的时候，我们可以认为他已经收敛，那么算法停止。

随机梯度下降算法（增量梯度下降算法）

当m很大的时候，梯度下降算法将消耗大量的时间和内存。而增量梯度下降算法则是可以节约大量的时间。

Repeat}{for j=1 to m{for all i Θi:=Θi−α(hθ(x(j))−y(j))x(j)}$$\begin{array}{rl}Repeat& \{\\ & \text{for j=1 to m}\{\\ & \text{for all i }\\ & {\mathrm{\Theta }}_i:={\mathrm{\Theta }}_i-\alpha (h_{\theta }(x^{(j)})-y^{(j)})x^{(j)}\\ \}\\ & \}\end{array}$$

随机梯度算法通常得到一个接近于全局最优解的可行解，但是一般不会差距太大。

一种更加广泛的表达方式

令：

ΔθJ=⎡⎣⎢⎢⎢dJdθ0⋮dJdθn⎤⎦⎥⎥⎥$${\mathrm{\Delta }}_{\theta }J=\left[\begin{array}{c}\frac{dJ}{d{\theta }_0}\\ ⋮\\ \frac{dJ}{d{\theta }_n}\end{array}\right]$$

则：
{Θ:=Θ−αΔθJ Θ∈Rn+1 ΔθJ∈Rn+1$\{\begin{array}{l}\mathrm{\Theta }:=\mathrm{\Theta }-\alpha {\mathrm{\Delta }}_{\theta }J\mathrm{\Theta }\in R^{n+1}{\mathrm{\Delta }}_{\theta }J\in R^{n+1}\end{array}$

设函数f$f$是一个m×n$m\times n$空间到一维空间的映射：

f:Rm×n↦R ,则f(A),A∈Rm×n$$f:R^{m\times n}\mapsto R\text{ ,则}f(A),A\in R^{m\times n}$$

ΔAf(A)=⎡⎣⎢⎢⎢⎢dfdA11⋮dfdAm1⋯⋱⋯dfdA1n⋮dfdAmn⎤⎦⎥⎥⎥⎥$${\mathrm{\Delta }}_{A}f(A)=\left[\begin{array}{ccc}\frac{df}{d{A}_{11}}& \cdots & \frac{df}{d{A}_{1n}}\\ ⋮& \ddots & ⋮\\ \frac{df}{d{A}_{m1}}& \cdots & \frac{df}{d{A}_{mn}}\end{array}\right]$$

tr(A)=∑ni=1Aii ,也写作：trA$tr(A)=\sum _{i=1}^n{A}_{ii}\text{ ,也写作：}trA$

Facts:trAB=trBAtrABC=trCAB=trBCAf(A)=trABΔAtrAB=BTtrA=trATΔAtrABATC=CAB+CTABT$$\begin{array}{rl}& Facts:\\ & trAB=trBA\\ & trABC=trCAB=trBCA\\ & f(A)=trAB{\mathrm{\Delta }}_{A}trAB=B^T\\ & trA=tr{A}^T\\ & {\mathrm{\Delta }}_{A}trAB{A}^{T}C=CAB+C^{T}A{B}^T\end{array}$$

由以上的定理，我们可以进行以下的推导：

X⋅Θ=⎡⎣⎢⎢(x(1))T⋮(x(n))T⎤⎦⎥⎥Θ=⎡⎣⎢⎢⎢x(1)TΘ⋮x(n)TΘ⎤⎦⎥⎥⎥=⎡⎣⎢⎢hθ(x(1))⋮hθ(x(m))⎤⎦⎥⎥$$\begin{array}{rl}X\cdot \mathrm{\Theta }& =\left[\begin{array}{c}(x^{(1)}{)}^T\\ ⋮\\ (x^{(n)}{)}^T\end{array}\right]\mathrm{\Theta }\\ & =\left[\begin{array}{c}{x^{(1)}}^T\mathrm{\Theta }\\ ⋮\\ {x^{(n)}}^T\mathrm{\Theta }\end{array}\right]=\left[\begin{array}{c}{h}_{\theta }(x^{(1)})\\ ⋮\\ h_{\theta }(x^{(m)})\end{array}\right]\end{array}$$

同理，

y⃗ =⎡⎣⎢⎢(y(1))⋮(y(n))⎤⎦⎥⎥$,则：$X⋅Θ−y⃗ =⎡⎣⎢⎢h(x(1)−y(1))⋮h(x(m)−y(m))⎤⎦⎥⎥$$\overrightarrow{y}=\left[\begin{array}{c}(y^{(1)})\\ ⋮\\ (y^{(n)})\end{array}\right]\$,则：\$X\cdot \mathrm{\Theta }-\overrightarrow{y}=\left[\begin{array}{c}h(x^{(1)}-y^{(1)})\\ ⋮\\ h(x^{(m)}-y^{(m)})\end{array}\right]$$

矩阵转置再相乘：12(X⋅Θ−y⃗ )T(X⋅Θ−y⃗ )=12∑mi=1(h(x(i))−y(i))2$\frac{1}{2}{(X\cdot \mathrm{\Theta }-\overrightarrow{y})}^T(X\cdot \mathrm{\Theta }-\overrightarrow{y})=\frac{1}{2}\sum _{i=1}^m(h(x^{(i)})-y^{(i)}{)}^2$
于是：

ΔθJ(θ)=Δθ12(XΘ−y⃗ )T(XΘ−y⃗ )=12Δθ(ΘTXTXΘ−ΘTXTy⃗ −y⃗ TXΘ+y⃗ Ty⃗ )=12Δθtr(ΘTXTXΘ−ΘTXTy⃗ −y⃗ TXΘ+y⃗ Ty⃗ )=12Δθ(trΘTXTXΘ−2try⃗ TXΘ)=12(XTXΘ+XTXΘ−XTy⃗ )=XTXΘ−XTy⃗ $$\begin{array}{rl}{\mathrm{\Delta }}_{\theta }J(\theta )& ={\mathrm{\Delta }}_{\theta }\frac{1}{2}(X\mathrm{\Theta }-\overrightarrow{y}{)}^T(X\mathrm{\Theta }-\overrightarrow{y})\\ & =\frac{1}{2}{\mathrm{\Delta }}_{\theta }({\mathrm{\Theta }}^T{X}^{T}X\mathrm{\Theta }-{\mathrm{\Theta }}^T{X}^T\overrightarrow{y}-{\overrightarrow{y}}^{T}X\mathrm{\Theta }+{\overrightarrow{y}}^T\overrightarrow{y})\\ & =\frac{1}{2}{\mathrm{\Delta }}_{\theta }tr({\mathrm{\Theta }}^T{X}^{T}X\mathrm{\Theta }-{\mathrm{\Theta }}^T{X}^T\overrightarrow{y}-{\overrightarrow{y}}^{T}X\mathrm{\Theta }+{\overrightarrow{y}}^T\overrightarrow{y})\\ & =\frac{1}{2}{\mathrm{\Delta }}_{\theta }(tr{\mathrm{\Theta }}^T{X}^{T}X\mathrm{\Theta }-2tr{\overrightarrow{y}}^{T}X\mathrm{\Theta })\\ & =\frac{1}{2}(X^{T}X\mathrm{\Theta }+X^{T}X\mathrm{\Theta }-X^T\overrightarrow{y})\\ & =X^{T}X\mathrm{\Theta }-X^T\overrightarrow{y}\end{array}$$

因为目标是使得Jθ$J_{\theta }$最小，则，我们令其最小为0：

XTXΘΘ=XTy⃗ =XTy⃗ XTX$$\begin{array}{rl}{X}^{T}X\mathrm{\Theta }& =X^T\overrightarrow{y}\\ \mathrm{\Theta }& =\frac{X^T\overrightarrow{y}}{X^{T}X}\end{array}$$

参考自【斯坦福】机器学习（Machine Learning）- 吴恩达（Andrew Ng）