### 基本概念
首先看一下基本的概念与符号。$x^{(i)}$表示输入变量，也就是**特征**，$y^{(i)}$表示输出变量，也被称为**标签**或**目标**。二者组成的元组$(x^{(i)},y^{(i)})$就表示一个训练样本，而$n$个这样的训练样本就组成了训练集，即$\{(x^{(i)} , y^{(i)} ); i = 1, \cdots , n\}$。此外，我们使用$\mathcal{X}$表示输入值的空间，用$\mathcal{Y}$表示输出值的空间。将输入值映射到输入值的函数被称为**假设**（hypothesis），这些映射函数构成的集合被称为**假设集**，表示为$h: \mathcal{X} \mapsto \mathcal{Y}$。以线性函数为例，一个可能的假设为：
$$
h_\theta(x) = \theta_0 + \theta_{1}x_1 + \theta_2 x_2
$$
其中，$\theta_i$是假设的参数（或称之为权重）。显然，对于不同的假设，其参数是不同的。
机器学习的流程就是在训练集上运行学习算法，从假设集中找到一个“好”的假设$h^*$，以根据输入值预测输出值。如果我们需要预测的输出值是连续的，那么我们称之为**回归问题**；如果需要预测的值是离散的，那么就是**分类问题**。接下来，我们需要解决两个问题。第一个问题就是**如何衡量假设的“好”与“坏”**？第二个问题是**怎样找到一个“好”的假设**？
### 损失函数
先来看一下第一个问题，如何衡量假设的“好”与“坏”。显然，一种直观的想法是在训练集上，预测值$h_\theta(x)$与真实值$y$之间的误差越小越好。因此，我们定义一个函数来衡量不同参数$\theta$下每个样本的预测值$h_\theta(x^{(i)})$和真实值$y^{(i)}$之间的差距。这个函数就是**损失函数**。在回归问题中，常用的损失函数为平方误差函数：
$$
J(\theta) = \frac {1}{2n} \sum _{i=1}^n \left (h_\theta (x_{i}) - y_{i} \right)^2
$$
### 参数学习
我们已经知道如何度量假设的“好”与“坏”，下面就需要解决第二个问题：如何找到“好”的假设，换句话说，就是如何学习出“好”的参数$\theta$。我们希望学到的参数能够使损失函数$J(\theta)$最小化。下面介绍两种学习参数的方法。
#### 梯度下降法
梯度下降是一种最优化方法。它首先将参数初始化，然后求解对应目标函数的梯度，沿着梯度下降最快的方向更新参数，直到目标函数收敛到最小值。单步更新的公式如下：
$$
\theta_j \coloneqq \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta)
$$
其中$\alpha$是**学习率**，也叫做**步长**。实现梯度下降的关键是求解$J(\theta)$对$\theta_j$的偏导数：
$$
\begin{aligned}
\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}\left(\sum_{i=0}^{d}\theta_i x_i - y\right)\\
&=(h_\theta(x) - y)x_j
\end{aligned}
$$
因此，单个训练样本的更新规则如下：
$$
\theta_j \coloneqq \theta_j - \alpha\left(h_\theta(x^{(i)})-y^{(i)}\right)x_j^{(j)},\forall j\in\{0,1,\cdots,d\}
$$
也可以写成：
$$
\theta \coloneqq \theta - \alpha\left(h_\theta(x^{(i)})-y^{(i)}\right)x^{(i)}
$$
在使用梯度下降算法时，要进行特征缩放及归一化。这两步操作使所有的特征值处于相近的范围内，以保证损失函数$J(\theta)$不是偏斜的。
#### 正规方程法
因为最小化$J(\theta)$是一个凸优化问题，所以$J(\theta)$有全局唯一的最小值。这就意味着我们可以直接计算出该问题的解析解。
为了求解该问题，我们需要构造一个由所有训练样本组成的矩阵$X$，矩阵的每一行表示一个训练样本，每一列表示不同的特征。这里$X$是一个$n\times (d+1)$维的矩阵（包含截距项）：
$$
X=\begin{bmatrix}
—(x^{(1)})^T — \\
—(x^{(2)})^T —\\
\vdots \\
—(x^{(n)})^T—
\end{bmatrix}
$$
令$\vec{y}$为所有真实值组成的$n$维向量：
$$
\vec{y} = \begin{bmatrix}
y^{(1)}\\
y^{(2)}\\
\vdots\\
y^{(n)}\\
\end{bmatrix}
$$
因为$h_\theta(x^{(i)}) = (x^{(i)})^T\theta$，其中$\theta$是一个$d+1$维向量，所以有如下形式：
$$
\begin{aligned}
X\theta -\vec{y} &=\begin{bmatrix}
(x^{(1)})^T\theta\\
\vdots\\
(x^{(n)})^T\theta\\
\end{bmatrix}-\begin{bmatrix}
y^{(1)}\\
\vdots\\
y^{(n)}\\
\end{bmatrix}\\
&=\begin{bmatrix}
h_\theta(x^{(1)})-y^{(1)}\\
\vdots\\
h_\theta(x^{(n)})-y^{(n)}\\
\end{bmatrix}
\end{aligned}
$$
对于任意向量$z$，我们有$z^Tz = \sum_{i}z_i^2$。因此，可以将$J(\theta)$写成矩阵形式：
$$
\begin{aligned}
J(\theta)&= \frac{1}{2}\sum_{i=1}^{n}\left(h_\theta(x^{(i)})-y^{(i)}\right)^2\\ &=\frac{1}{2} (X\theta-\vec{y})^T(X\theta-\vec{y})
\end{aligned}
$$
对$J(\theta)$求导得：
$$
\begin{aligned}
\nabla_\theta J(\theta) &= \nabla_\theta \frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y})\\
&= \frac{1}{2}\left((X\theta)^TX\theta-(X\theta)^T\vec{y}-\vec{y}^T(X\theta)+\vec{y}^T\vec{y}\right)\\
&= \frac{1}{2}\left(\theta^T(X^TX)\theta-\vec{y}^T(X\theta)-\vec{y}^T(X\theta)\right)\\
&=\frac{1}{2}\left(\theta^T(X^TX)\theta- 2(\vec{y}^TX)\theta\right)\\
&= \frac{1}{2}\left(\theta^T(X^TX)\theta-2(X^T\vec{y})^T\theta\right)\\
&= \frac{1}{2}(2X^TX\theta-2X^T\vec{y})\\
&= X^TX\theta-X^T\vec{y}
\end{aligned}
$$
为了求解$J(\theta)$的最小值，令其导数等于0，得到正规方程：
$$
X^TX\theta = X^T\vec{y}
$$
因此，$J(\theta)$最小值的闭式解为：
$$
\theta = (X^TX)^{-1}X^T\vec{y}
$$
当$X^TX$不可逆时，我们需要仔细检查训练集的特征，去除相关性较强的冗余特征；或者使用正则化技术。此外，还可以求解$X^TX$的伪逆。
