局部加权线性回归
参数学习算法和非参数学习算法
在机器学习中，我们有参数学习算法和非参数学习算法
参数学习算法是指对具有特定参数的模型进行拟合的算法。
在该算法中，模型具有一组已知的参数。也就是说，我们明确知道“模型的表示形式”——例如对于下面这个散点图，我们一眼就能看出模型应该形如\(y = \theta x\)。
算法的主要任务是：基于训练数据集来估计这些参数的值，以使模型能够预测未来的数据。也就是说，模型训练完成之后，训练集（数据）就可以从计算机内存中“扔掉”，只需要保留模型的参数值即可完成后续预测任务。
常见的参数学习算法：一元线性回归
非参数学习算法是指对没有特定参数的模型进行拟合的算法。
在该算法中，模型没有固定的参数，因此它们能够学习和适应数据的不同特征和复杂性。也就是说，我们不知道“模型的表示形式”——例如下面这个散点图，我们一眼无法看出哪一种模型拟合的最好。
每一次预测都需要用到所有的数据
常见的非参数学习算法：局部加权线性回归、决策树等等
局部加权线性回归
局部加权线性回归的基本思想是：如果要预测 \(x^*\)对应的 label, 我们可以根据其附近的数据点进行拟合。最简单的方式是，根据 x 附近的数据点拟合一条直线（当然是在 x 维度为1的前提下），根据这条直线对 \(x^*\) 进行预测。如下图所示
此时，局部加权线性回归的成本函数我们可以写作——
\[
J(\theta) = \sum_{i=1}^m w^{(i)}(y^{(i)} - \theta^Tx^{(i)})^2
\]
可以看出，和线性回归的成本函数相比，该成本函数的每一项都乘了一个权重\(w^{(i)}\)。
根据局部加权线性回归的思想，我们需要更加关注 \(x^*\)
(需要预测的数据)附近的数据点。因此，\(x^{*}\) 附近的数据点 \(x^{(i)}\)
我们应该赋予更高的权重，也就是更关注该数据点处的“损失”。一种常用的\(w^{(i)}\) 的计算方式是：
\[
w^{(i)} = \exp{(-\frac{(x^{(i)} - x^*)^2}{2})}
\]
显然，当 \(x^{(i)}\) 距离 \(x^*\) 非常近的时候，\(w^{(i)}\) 接近 1；当 \(x^{(i)}\) 距离 \(x^*\) 非常远的时候，\(w^{(i)}\) 接近 0。\(w\) 的图像如下图所示:
有的时候，我们想要控制这个图像的“胖瘦”——即有的时候我们需要更大范围内的"邻居"，有的时候我们只需要非常靠近\(x^*\)的"邻居"。此时，我们可以在\(w^{(i)}\)中增加一个带宽（bandwidth）参数\(\sigma\)，通过\(\sigma\) 来控制：
\[
w^{(i)} = \exp{(-\frac{(x^{(i)} - x^*)^2}{2 \sigma^2})}
\]
适用范围
当数据量比较大，且特征值比较少时（例如n=2, 3），我们可以采用加权线性回归。
线性回归的概率解释
问题引入
我们在线性回归中，使用“所有误差的平方和”作为成本函数，即：
\[
J(\theta) = \frac{1}{2} \sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})^2
\]
在这里我们为什么要采用平方，而不是采用四次方，或者直接取绝对值呢？
概率解释
对于每一个数据点\((x^{(i)},
y^{(i)})\) ，我们可以写作
\[
y^{(i)} = \theta^Tx^{(i)} + \varepsilon^{(i)}
\]
其中，\(\varepsilon^{(i)}\)
是误差项。在这里，我们假设\(\varepsilon^{(i)}\) 服从“均值为0,
方差为\(\sigma^2\)
”的正态分布，即$^{(i)} (0, ^2) $ 。且所有的\(\varepsilon^{(i)}\)
都是独立同分布的（i.i.d.）。
\[
P(\epsilon^{(i)}) = \frac{1}{\sqrt{2\pi} \sigma} \exp
(-\frac{(\varepsilon^{(i)})^2}{2 \sigma^2})
\]
根据前面的假设，有
\[
P(y^{(i)} \mid x^{(i)}; \theta) = \frac{1}{\sqrt{2\pi} \sigma} \exp
(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2 \sigma^2})
\]
我们的目标是根据训练数据，得到最佳的参数值，也就是\(\theta\)。我们可以根据最大似然估计的思想，“固定”训练数据（即把训练数据当做已知量），得到
\(\theta\) 的似然函数 \(\mathcal{L}(\theta)\)：
\[
\begin{aligned}
\mathcal{L}(\theta) &= P(Y \mid X; \theta) \\
&= \prod_{i=1}^{m} P(y^{(i)} \mid x^{(i)}; \theta) \\
&= \prod_{i=1}^{m} \frac{1}{\sqrt{2\pi} \sigma} \exp
(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2 \sigma^2}) \\
\end{aligned}
\]
通常情况下，为了便于求解，我们经常对\(\mathcal{L}(\theta)\) 取对数，得到\(\ell(\theta)\)
\[
\begin{aligned}
\ell(\theta) &= \log (\mathcal{L}(\theta)) \\
&= \log(\prod_{i=1}^{m} \frac{1}{\sqrt{2\pi} \sigma} \exp
(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2 \sigma^2})) \\
&=\sum_{i=1}^m \log(\frac{1}{\sqrt{2 \pi} \sigma} ) - \frac{1}{2
\sigma^2} \sum_{i=1}^m (y^{(i)} - \theta^Tx^{(i)})^2
\end{aligned}
\]
根据最大似然估计，我们应该找到一个\(\theta\)，使得最大化\(\mathcal{L}(\theta)\)，也就是最大化\(\ell(\theta)\)。因此有
\[
\theta = \mathop{\arg\max}\limits_{\theta} \ \ell(\theta)
\]
根据\(\ell(\theta)\) 的表示，很容易可以看出，我们只需要 \(\sum_{i=1}^m (y^{(i)} - \theta^Tx^{(i)})^2\) 最大即可。这不就是线性回归成本函数\(J(x)\)的表示嘛！
当然了，还是需要注意——所有的推导都是基于一开始的假设：误差\(\varepsilon^{(i)}\)服从“均值为0, 方差为\(\sigma^2\) ”的正态分布，即$^{(i)} (0, ^2) $。尽管这看上去非常理想，但是在实践中通常拟合的很好（满足中心极限定律）。
似然（likehood）和概率（probably）的区别：
- 似然是参数的似然，数据是固定的
- 概率是数据的概率，参数是固定的
Logistics 回归
基本形式
Logistics 回归主要是为了解决二分类问题。在分类问题中， y 是离散的，如 \(y \in \{0, 1\}\) 。 对于二分类问题，一个典型的散点图如下所示（我们可以将它应用于肿瘤性质的预测 —— x 表示肿瘤的大小， y 表示肿瘤是恶性还是良性）
很显然，我们不能简单的用线性回归来拟合它，因为线性拟合很容易受到“离群值”的影响。在这里我们使用
Logistics 回归来拟合它，函数 \(h_\theta(x)\) 可以表示为
\[
h_\theta(x) = g(\theta^Tx) = \frac{1}{1+e^{-\theta^Tx}} \\
g(z) = \frac{1}{1 + e^{-z}}
\]
其中函数 \(g(z)\) 我们称为 Logistics
函数，函数图像如下所示
不难看出\(h_\theta \in [0, 1]\)。当\(h_\theta(x) > 0.5\) 时，我们可以认为预测值为 1；当\(h_\theta(x) \leq 0.5\) 时，我们可以认为预测值为 0 。
损失函数
利用\(h_\theta(x)\)
的定义，我们可以写出“给定 x 时 y = 1 的概率” 以及 “给定 x 时 y = 0
的概率”：
\[
P(y = 1 \mid x; \theta) = h_\theta(x) \\
P(y = 0 \mid x; \theta) = 1 - h_\theta(x)
\]
因为 \(y \in \{0, 1\}\)
，所以我们可以利用这一点将上面两个式子合成一个：
\[
P(y \mid x;\theta) = h_\theta(x)^{y} \cdot (1 - h_\theta(x))^{1-y}
\]
我们继续用极大似然估计来推导损失函数。似然函数可以写作
\[
\begin{aligned}
\mathcal{L}(\theta) &= P(Y \mid X; \theta) \\
&= \prod_{i=1}^{m} P(y^{(i)} \mid x^{(i)}; \theta) \\
&= \prod_{i=1}^{m} h_\theta(x^{(i)})^{y^{(i)}} \cdot (1 -
h_\theta(x^{(i)}))^{1-y^{(i)}}
\end{aligned}
\]
同样为了便于计算，需要对 \(\mathcal{L}(\theta)\) 取对数
\[
\begin{aligned}
\ell(\theta) &= \log (\mathcal{L}(\theta)) \\
&= \log(\prod_{i=1}^{m} h_\theta(x^{(i)})^{y^{(i)}} \cdot (1 -
h_\theta(x^{(i)}))^{1-y^{(i)}}) \\
&=\sum_{i=1}^m y^{(i)} \cdot \log(h_\theta(x^{(i)})) + (1 -
y^{(i)}) \cdot \log(1 - h_\theta(x^{(i)}))
\end{aligned}
\]
\(\theta\) 的最优值应该使得 \(\ell(\theta)\) 最大化。因此，成本函数\(J(\theta)\)可以定义为
\[
J(\theta) = \sum_{i=1}^m - \ y^{(i)} \cdot \log(h_\theta(x^{(i)})) -
(1 - y^{(i)}) \cdot \log(1 - h_\theta(x^{(i)}))
\]
当\(J(\theta)\) 最小时，\(\ell(\theta)\) 最大，此时\(\theta\)
是最优值。接下来，我们同样可以使用梯度下降求解 \(\theta\)
\[
\theta_j := \theta_j - \alpha \frac{\partial \
J(\theta)}{\partial\ \theta_j} \ \\ \tt{(repeat \ until \ convergence)}
\]
将\(\frac{\partial \
J(\theta)}{\partial\ \theta_j}\) 的值计算并代入，即可得到
\[
\theta_j := \theta_j - \alpha \sum_{i=1}^m (h_\theta(x
^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \
\]
牛顿法
问题引入
无论是线性回归，还是 Logistics
回归，他们的局部最优值就是全局最优值。也就是说，他们的似然函数 \(\ell(\theta)\)
的唯一极值也就是最值。因此，我们可以直接对似然函数对\(\theta\) 求导数，并令导数等于0，即
\[
\ell^{\prime}(\theta) = 0
\]
对于\(\ell(\theta)\)
，求导数是很容易的，但是求解 \(\ell^{\prime}(\theta)\)
的零点却不简单。
基本思想
我们可以采用牛顿法来解决上述问题。假设我们求解的方程是
\[
f(x) = 0
\]
牛顿方法的基本过程是：
- 随机挑选一个 x 值 ，设定一个终止误差值\(\varepsilon\)
- 找到\(f(x)\) 在 x 处的切线，该切线与 x 轴交于一点 m
- 当 \(|x - m| < \varepsilon\) 时，结束迭代，反之令 x = m ，继续第2步...
整个过程可以用下图来表示
该过程可以形式化表示为
\[
x := x - \frac{f(x)}{f^{\prime}(x)}
\]
将牛顿法应用到求解\(\ell^{\prime}(\theta)\)
零点的问题上，则\(\theta\)
目标值的求解过程可以形式化的表示为
\[
\theta := \theta -
\frac{\ell^{\prime}(\theta)}{\ell^{\prime\prime}(\theta)} \\ \tt{(repeat
\ until \ convergence)}
\]
上述公式只是适用于\(\theta\)
是0维的时候。当\(\theta\)
为一个向量时，牛顿法可以扩展为
\[
\theta := \theta - H^{-1} \nabla_{\theta}\ell(\theta)
\]
其中\(H\) 表示Hession矩阵。这个方法也叫牛顿-拉普森法（Newton-Raphson）。
牛顿法具有二次收敛的特性，即每次迭代有效数字的位数加倍，因此和梯度下降相比有很高的迭代速度。但是，每次迭代的开销比梯度下降要高很多，因为要计算 \(n \times n\) 规模的 \(H\) 矩阵。 所以，牛顿法适用于参数量不是很大的情况（也就是\(\theta\) 的分量数），参数量在 10~50 之间比较适合。如果参数量比较大，梯度下降法比较适合。
