CS229-Linear Regression and Gradient Descent Lecture2

Linear Regression

选择参数是 learning algorithm 里很重要的一部分。

To perform supervised learning, we must decide how we’re going to represent functions/hypotheses h in a computer. As an initial choice, let’s say we decide to approximate y as a linear function of x

$$h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2$$

θ 就是参数，也被称为权重。

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

Now, given a training set, how do we pick, or learn, the parameters θ? To formalize this, we will define a function that measures, for each value of the θ’s, how close the h(x(i))’s are to the corresponding y(i)’s.

没错，就是 cost function：

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

与最小二乘的 cost function 有些熟悉，让我们继续。

LMS algorithm

We want to choose θ so as to minimize J(θ)。

Specifically, let’s consider the gradient descent algorithm, which starts with some initial θ, and repeatedly performs the update:

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

α is called the learning rate.This is a very natural algorithm that repeatedly takes a step in the direction of steepest decrease of J.

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

For a single training example, this gives the update rule:

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

The rule is called the LMS update rule (LMS stands for “least mean squares”), and is also known as the Widrow-Hoff learning rule.

magnitude of update 与 error term $(y^{(i)}-h_{\theta }(x^{(i)}))$

有更大的 error 将会对参数发生巨大改变。

有两种方法来修改这个方法对于多于一个 example 的训练集。第一种便是上面的 LMS update rule。

第二种是：

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

This method looks at every example in the entire training set on every step, and is called batch gradient descent.

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

在这个算法中，我们更新参数只根据 error 相对于单个的 example。This algorithm is called stochastic gradient descent (also incremental gradient descent).

Often, stochastic gradient descent gets θ “close” to the minimum much faster than batch gradient descent.

Least squares revisited

因为$h_{\theta }(x^{(i)})=(x^{(i)}{)}^T\theta$​​,我们可以轻易地用矩阵表示

$$X\theta -\overrightarrow{y}=\left[\begin{array}{c}(x^{(1)}{)}^T\theta \\ ⋮\\ (x^{(n)}{)}^T\theta \end{array}\right]-\left[\begin{array}{c}{y}^{(1)}\\ ⋮\\ y^{(n)}\end{array}\right]=\left[\begin{array}{c}{h}_{\theta }(x^{(1)})-y^{(1)}\\ ⋮\\ h_{\theta }(x^{(n)})-y^{(n)}\end{array}\right]$$

同时，用这个公式$z^{T}z=\sum _i{z}_i^2$​​，我们能进一步推

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

最后，为了minimize J，让我们进一步推出它的梯度

$$\begin{array}{rl}{\mathrm{\nabla }}_{\theta }J(\theta )& ={\mathrm{\nabla }}_{\theta }\frac{1}{2}(X\theta -\overrightarrow{y}{)}^T(X\theta -\overrightarrow{y})\\ & =\frac{1}{2}{\mathrm{\nabla }}_{\theta }((X\theta {)}^{T}X\theta -(X\theta {)}^T\overrightarrow{y}-{\overrightarrow{y}}^T(X\theta )+{\overrightarrow{y}}^T\overrightarrow{y})\\ & =\frac{1}{2}{\mathrm{\nabla }}_{\theta }({\theta }^T(X^{T}X)\theta -{\overrightarrow{y}}^T(X\theta )-{\overrightarrow{y}}^T(X\theta ))\\ & =\frac{1}{2}{\mathrm{\nabla }}_{\theta }({\theta }^T(X^{T}X)\theta -2(X^T\overrightarrow{y}{)}^T\theta )\\ & =\frac{1}{2}(2X^{T}X\theta -2X^T\overrightarrow{y})\\ & =X^{T}X\theta -X^T\overrightarrow{y}\end{array}$$

为了minimize J,我们将它的梯度设置成0，因此得到normal equations

$$X^{T}X\theta =X^T\overrightarrow{y}$$

同时，得到θ的值 $\theta =(X^{T}X{)}^{-1}{X}^T\overrightarrow{y}$

Probabilistic interpretation

In this section,你将看到一系列的probabilistic assumptions，在这之下，least-squares regression将会十分自然的衍生出来。

$$y^{(i)}={\theta }^T{x}^{(i)}+{ϵ}^{(i)}$$

在这里面，${ϵ}^{(i)}$​是error(unmodeled effects or random noise)。我们可以用正态分布来表示这个assumption。

$$p({ϵ}^{(i)})=\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{({ϵ}^{(i)}{)}^2}{2{\sigma }^2})$$

这意味着

$$p(y^{(i)}|x^{(i)};\theta )=\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})$$

注意：$\theta$不是一个随机变量

因此，根据上面的assumption，我们可以进一步推出$p(\vec{y}

X;\theta)$,我们会将它称为likelihood function

$$L(\theta )=L(\theta ;X,\overrightarrow{y})=p(\overrightarrow{y}|X;\theta )$$

根据独立性，这也可以被写为

$$L(\theta )=\prod _{i=1}^{n}p(y^{(i)}|x^{(i)};\theta )=\prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})$$

对于我们如何选择最好的参数，我们可以用maximum likelihood法则，也就是选择一个参数来使得data的概率越高越好。

也就是，我们要挑选一个参数来maximize $L(\theta )$

我们可以maximize任意strictly increasing function of $L(\theta )$。比如，我们可以使用 log likelihood 来替代。

$$\begin{array}{rl}\log L(\theta )& =\log (\prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2}))\\ & =\sum _{i=1}^n\log (\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2}))\\ & =\sum _{i=1}^n(\log \left(\frac{1}{\sqrt{2\pi }\sigma }\right)-\frac{1}{{\sigma }^2}\cdot \frac{1}{2}(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2)\\ & =n\log \left(\frac{1}{\sqrt{2\pi }\sigma }\right)-\frac{1}{{\sigma }^2}\cdot \frac{1}{2}\sum _{i=1}^n(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2\end{array}$$

所以，我们要maximize$L(\theta )$只需要minimize:

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

这就是被称为$J(\theta )$的函数，也就是我们最初的least squares cost function.

注意，我们对于参数的选择不取决于${\sigma }^2$,且事实上我们可能得到相同的结果即使${\sigma }^2$​是未知的

Locally weighted linear regression