Linear Regression with One Variable (a.k.a univariate linear regression)

---

在学习机器学习的过程中，我发现即使有代数和统计的基础，不靠具体的例子就想深入理解每个算法到底在干什么是比较困难的。在这份重新整理的笔记中，我会以案例开头，以加深对每个算法应用场景的了解。当然，数学推导还是不能少的。

Task: Give a training set of (x,y)=(housing size, housing price), predict y given a new x.

---

1. Model

1.1 Notation

m=number of training examples
x=”input” variable/features
y=”output” variable/”target” variable
(x(i),y(i))=ith$(x^{(i)},y^{(i)})=i^{th}$ training example

1.2 Hypothesis

在上述房价预测问题中，我们很自然地会想到建立如下猜想：

这就是一个典型的单变量线性回归问题(linear regression with one variable)，问题的求解关键在于如何找到合适的θ0,θ1${\theta }_0,{\theta }_1$.

1.3 Cost function

To estimate the model built above, the idea is to choose parameters θ0${\theta }_0$, θ1${\theta }_1$ so that hθ(x)$h_{\theta }(x)$ is close to y for our training examples(x,y). In practice, we minimize the cost function:

hθ(x(i))−y(i)$h_{\theta }(x^{(i)})-y^{(i)}$是残差，∑mi=1(hθ(x(i))−y(i))2$\sum _{i=1}^m{\left(h_{\theta }(x^{(i)})-y^{(i)}\right)}^2$是残差平方和（SSR）。常数项12m${\displaystyle \frac{1}{2m}}$不影响参数估计结果，但习惯上我们在残差平方和的基础上除以样本量m，以计算平均值，再除以2，方便之后的求导计算（对参数求导后1/2会被消去）。完整的目标函数J(θ0,θ1)$J({\theta }_0,{\theta }_1)$即为代价函数（cost function），也称损失函数（loss function）。代价函数有多种类型，以上这种在回归问题里最常用。

1.4 Goal

线性回归的代价函数为严格凸函数(convex function)，上图最底端为唯一的最优点，此时∂∂θ0J(θ0,θ1)=∂∂θ1J(θ0,θ1)=0$\frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_0}J({\theta }_0,{\theta }_1)=\frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_1}J({\theta }_0,{\theta }_1)=0$.

Contour Plot: A graph that contains many contour lines

2. Parameter Learning

2.1 Gradient Descent 梯度下降

Have some function J(θ0,θ1)$J({\theta }_0,{\theta }_1)$
Want minθ0,θ1J(θ0,θ1)$\underset{{\theta }_0,{\theta }_1}{min}J({\theta }_0,{\theta }_1)$

梯度下降是机器学习中常用的参数优化算法，它的用途非常广泛，不仅可用于单变量线性回归的参数优化，还可用于多变量回归、逻辑回归、神经网络等多种场合。以单变量线性回归为例，梯度下降的主要思想是：

• Start with some θ0,θ1${\theta }_0,{\theta }_1$
• Keep changing θ0,θ1${\theta }_0,{\theta }_1$ to reduce J(θ0,θ1)$J({\theta }_0,{\theta }_1)$ until we hopefully end up
  at a minimum

下面我们通过一张图直观地理解梯度下降到底是在做什么：

黑色线条展示了一种可能的下降路径，它以左上角记号点为起始点，右下角记号点为终点，下降步骤包括：
Step1:随机初始化参数
Step2:找到下降最快的方向迈出一小步
Step3:不断重复步骤2
Step4:到达局部最优点

注意：梯度下降法不一定会找到全局最优解。起始点不同，可能会得到不同的局部最优解。

2.2 Gradient Descent Algorithm

repeat until convergence {
θj:=θj−α∂∂θjJ(θ0,θ1)${\theta }_j:={\theta }_j-\alpha \frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_j}J({\theta }_0,{\theta }_1)$ (for j=0 and j=1)
}
where := denotes assignment operator, α denotes learning rate, which is a positive number and controls how big a step we take when updating parameters.

为了正确实现梯度下降，我们需要对参数进行同步更新(simultaneous update)：

Correct: Simultaneous update	Incorrect:
temp0:=θ0−α∂∂θ0J(θ0,θ1)temp1:=θ1−α∂∂θ1J(θ0,θ1)θ0:=temp0θ1:=temp1$$\begin{gathered} temp0:={\theta }_0-\alpha \frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_0}J({\theta }_0,{\theta }_1) \\ temp1:={\theta }_1-\alpha \frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_1}J({\theta }_0,{\theta }_1) \\ {\theta }_0:=temp0 \\ {\theta }_1:=temp1 \end{gathered}$$	temp0:=θ0−α∂∂θ0J(θ0,θ1)θ0:=temp0temp1:=θ1−α∂∂θ1J(θ0,θ1)θ1:=temp1$$\begin{gathered} temp0:={\theta }_0-\alpha \frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_0}J({\theta }_0,{\theta }_1) \\ {\theta }_0:=temp0 \\ temp1:={\theta }_1-\alpha \frac{\mathrm{\partial }}{\mathrm{\partial }{\theta }_1}J({\theta }_0,{\theta }_1) \\ {\theta }_1:=temp1 \end{gathered}$$

2.3 Gradient Descent for Linear Regression

简单起见，我们只考虑单变量线性回归的情况，且假设θ0${\theta }_0$固定，仅对θ1${\theta }_1$进行优化。代价函数简化为θ1${\theta }_1$的函数J(θ1)=aθ21+bθ1+c(a>0)$J({\theta }_1)=a{\theta }_1^2+b{\theta }_1+c(a>0)$，其大致图像为

θ1:=θ1−αddθ1J(θ1)α>0${\theta }_1:={\theta }_1-\alpha \frac{d}{d{\theta }_1}J({\theta }_1)\alpha >0$
假设A为初始点，此时斜率ddθ1J(θ1)>0$\frac{d}{d{\theta }_1}J({\theta }_1)>0$，因此θ1${\theta }_1$会逐渐收敛至最优点P。当初始点为B点时，斜率为负，θ1${\theta }_1$依然逐渐向P点移动。

关于学习率的注意事项：
1. 如果α太小，梯度下降的速度会非常慢；
2. 如果α太大，梯度下降可能会跳过最优解（如从A点直接到B点），可能会导致算法无法收敛，甚至发散；
3. 即使不改变α的值，梯度下降仍可收敛到局部最优解，因为当接近局部最优时，梯度下降的步长会自动变小

在实践中，为了选择合适的α，Ng给出的建议是尝试以下值，并依次扩大三倍：
0.001,…0.003…,0.01,…0.03…,0.1,…0.3…,1……

这种梯度下降的方法又称批量梯度下降算法(Batch gradient descent)，因为下降的每一步都用到了所有训练样本。