Linear Regression

1. OLS

$$h(x)=\sum _{i=0}^n{\theta }_i{x}_i={\theta }^{T}x.$$

其中称 $\theta$ 为参数; 特别地, ${\theta }_0$ 称为截距项 (intercept term), 其对应的 $x$ 为 $1$.

1.1 OLS Cost Function

$$J(\theta )=\frac{1}{2}\sum _{i=1}^n(h_{\theta }(x^{(i)})-y^{(i)}{)}^2.$$

1.2 Gradient Descent

Gradient descent 的一般形式:

$${\theta }_j:={\theta }_j-\alpha \frac{\partial }{\partial {\theta }_j}J(\theta ).$$

其中 $j=1,2,\dots ,p$, 也就是同步更新所有的特征.

1.2.1 OLS Case

对损失函数关于某个特征求偏导有:

$$\begin{array}{rl}\frac{\partial }{\partial {\theta }_j}J(\theta )& =\frac{\partial }{\partial {\theta }_j}\frac{1}{2}{\left(h_{\theta }(x)-y\right)}^2\\ & =2\cdot \frac{1}{2}\left(h_{\theta }(x)-y\right)\cdot \frac{\partial }{\partial {\theta }_j}\left(h_{\theta }(x)-y\right)\\ & =\left(h_{\theta }(x)-y\right)\cdot \frac{\partial }{\partial {\theta }_j}\left(\sum _{i=0}^n{\theta }_i{x}_i-y\right)\\ & =\left(h_{\theta }(x)-y\right)\cdot x_j.\end{array}$$

因此对于一个样本 $i$ 的每个特征 $j$, 梯度下降的更新公式为:

$${\theta }_j:={\theta }_j+\alpha \left(y^{(i)}-h_{\theta }(x^{(i)})\right)\cdot x_j^{(i)}.$$

这一更新公式符合最小均方误差 (MSE), 因此也称为 LMS (least mean square) 更新规则, 或 Widrow-Hoff 规则.

1.2.2 Batch Gradient Descent

算法描述:

Repeat until convergence {
  θ := θ + α Σᵢ₌₁ⁿ (y⁽ⁱ⁾ - hθ(x⁽ⁱ⁾))x⁽ⁱ⁾
}

对应更新式为:

$$\theta :=\theta +\alpha \sum _{i=1}^n(y^{(i)}-h_{\theta }(x^{(i)}))x^{(i)}.$$

批量梯度下降法每次迭代都要用到所有训练样本, 所以当训练集很大时会很慢.

1.2.3 Stochastic Gradient Descent

算法描述:

Loop {
  for i = 1 to n {
    θ := θ + α(y⁽ⁱ⁾ - hθ(x⁽ⁱ⁾))x⁽ⁱ⁾
  }
}

对应更新式为:

$$\theta :=\theta +\alpha (y^{(i)}-h_{\theta }(x^{(i)}))x^{(i)}.$$

随机梯度下降法每次只用一个样本来更新参数, 而不是用所有样本.

2. Matrix Calculus Notes

定义:

$${\nabla }_{A}f(A)=\left[\begin{array}{cccc}\frac{\partial f}{\partial A_{11}}& \frac{\partial f}{\partial A_{12}}& \cdots & \frac{\partial f}{\partial A_{1n}}\\ \frac{\partial f}{\partial A_{21}}& \frac{\partial f}{\partial A_{22}}& \cdots & \frac{\partial f}{\partial A_{2n}}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial f}{\partial A_{m1}}& \frac{\partial f}{\partial A_{m2}}& \cdots & \frac{\partial f}{\partial A_{mn}}\end{array}\right].$$

例如, 若 $f(A)=\frac{2}{3}{A}_{11}+5A_{12}^2+A_{21}{A}_{22}$, 则

$${\nabla }_{A}f(A)=\left[\begin{array}{cc}\frac{2}{3}& 10A_{12}\\ A_{22}& A_{21}\end{array}\right].$$

Note: Source omission

The original note marks the later statistics discussion as omitted.

Related Notes

• Locally Weighted Linear Regression
• Regularization
• Linear Models for Classification