分布式处理与计算：分类与回归分析

在机器学习中，分类和回归都属于“监督学习”（即用带有标签的数据去训练模型），定义区别在于输出变量的类型

回归

建立一个模型，将输入变量 $X$ 映射到一个连续的数值 $Y$ 上。输出空间是一个无限集（通常是实数集 $\mathbb{R}$ 的某个区间）。输出的值之间是有大小关系的，且可以无限细分，如线性回归。

分类

建立一个模型，将输入变量 $X$ 划分到预定义的、离散的类别 $C$ 中。输出空间是一个有限集。输出的值之间没有大小关系，只是一个标签，如逻辑回归，KNN,SVM。

一、线性回归

线性回归的目标是在自变量 $x$ 与因变量 $y$ 之间建立一个线性模型:

$y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \cdots + \beta_p x_p + \varepsilon$

写成矩阵形式时,常把截距项 $\beta_0$ 吸收进系数向量:做法是把常数项移除,并在设计矩阵 $X$ 的最前面加上一列全 1,这样模型就统一写成

$\hat{y} = X\beta$

参数可以用最小二乘估计求出闭式解:

$\hat\beta = (X^{\top}X)^{-1}X^{\top}y$

预测一个新样本 $x_{\text{new}}$ 时,直接代入 $\hat{y}_{\text{new}} = x_{\text{new}}^{\top}\hat\beta$ 即可。

二、逻辑回归

逻辑回归属于广义线性模型。广义线性模型的一般形式是通过一个联系函数 $g$ 把线性预测值 $x^{\top}\beta$ 映射到响应:

$g(y) = x^{\top}\beta$

逻辑回归取 对数几率函数 (logit)作为联系函数。把 logit 代入,就得到逻辑回归模型:

$P(y=1\mid x) = \frac{1}{1 + e^{-x^{\top}\beta}} = \frac{e^{x^{\top}\beta}}{1 + e^{x^{\top}\beta}}$

对"几率"取对数,可以得到

$\ln\frac{P(y=1\mid x)}{P(y=0\mid x)} = x^{\top}\beta$

由此可以看出,逻辑回归实际上是在用线性回归的预测结果去逼近真实标记的对数几率。

与线性回归不同,逻辑回归问题没有闭式解,只能用迭代方法(如梯度下降、牛顿法)求解。预测新样本时,算出 $P(y=1\mid x)$ ,以 $0.5$ 为阈值判类,因此分类判别线就是 $P(y=1\mid x) = 0.5$ ,等价于 $x^{\top}\beta = 0$ 。

线性判别的适用性:两种情况

情况一:两类数据分别来自两个方差相同、均值不同的高斯分布。此时,基于线性回归的判别准则基本上就是最优的——线性边界足够。
情况二:两类数据分别来自一个由 10 个高斯分布混合而成的复杂分布。此时数据结构远比一条直线复杂,基于线性回归的判别准则远远不够,需要更灵活的非线性方法。

这组对比说明了线性模型的局限:只有当类别边界本质上是线性(或近似线性)时,线性判别才好用。

三、最近邻方法(KNN)

定义:要预测一个样本属于哪一类,可以借助它周围相邻的样本来判别——"物以类聚",邻居是什么类,它大概率也是什么类。

模型形式:对样本 $x$ ,取它的 $k$ 个最近邻组成的邻域 $N_k(x)$ ,预测值为

$\hat{f}(x) = \frac{1}{k}\sum_{x_i \in N_k(x)} y_i$

判别标准:如果在 $x$ 的 $k$ 个近邻中,多数样本属于某一特定类,就把 $x$ 也判为这些近邻里占多数的那一类(多数表决)。

决策边界 的决策边界是不规则的、随数据分布而变的分段边界,不像线性回归那样是一条直线; $k$ 越小边界越弯曲(易过拟合), $k$ 越大边界越平滑。

四、期望预测误差与贝叶斯准则

在给定损失函数下,什么样的预测函数误差最小,那个最优预测就叫贝叶斯准则,对应的最小误差叫贝叶斯误差(风险) 最小化期望风险所求得的理论最优预测规则即为贝叶斯准则（回归时猜均值，分类时猜最大概率），其对应的理论下界误差称为贝叶斯误差，构成了所有实际学习算法性能的渐近极限。

平方损失函数下

平方损失: $L(y, f(x)) = (y - f(x))^2$ 。

期望预测误差(EPE):

$\text{EPE}(f) = E\big[(y - f(x))^2\big]$

它可以分解成贝叶斯误差 + 模型误差两部分。最小化 EPE,得到的最优预测函数是

$f^*(x) = E[\,y \mid x\,]$

也就是给定 $x$ 时, $y$ 的条件期望。在平方损失下,这个条件期望 $E[y\mid x]$ 就是贝叶斯准则,它带来的误差就是贝叶斯误差,即任何模型所能达到的最小误差。

0-1 损失函数下

0-1 损失:预测对了损失为 0,预测错了损失为 1,即 $L(y, f(x)) = \mathbb{1}[\,y \ne f(x)\,]$ 。

泛化误差 就是分类错误率。最小化它,得到的最优分类器是选后验概率最大的类:

$f^*(x) = \arg\max_{c} P(y = c \mid x)$

0-1 损失下的二分类问题

在二分类( $y \in \{0,1\}$ )下,期望预测误差的最小化归结为一个简单的比较:

如果 $P(y=1\mid x) > P(y=0\mid x)$ ,则判 $x$ 为第 1 类;
如果 $P(y=1\mid x) < P(y=0\mid x)$ ,则判 $x$ 为第 0 类。

于是最优判别就是"哪个后验概率大就判哪类",等价于以 $P(y=1\mid x)=0.5$ 为界。这里的最优规则又叫贝叶斯准则,它对应的最小错误率被称为贝叶斯风险。

五、支持向量机(SVM)

SVM（支持向量机）是一种追求最大间隔的几何分类器，它不仅要求将不同类别的样本正确分开，更致力于在所有可能的分界超平面中，找到一个距离两侧最近样本（即“支持向量”）最远的那一个；当数据线性不可分时，它通过引入Hinge损失和正则系数 C 构建“软间隔”来容忍部分违规，并借助拉格朗日对偶求解，使得最终的模型仅由少数关键的支持向量线性组合决定，从而在保证强泛化能力的同时实现了极其高效的稀疏表达。

标准 SVM(硬间隔)

SVM 的核心思想是找一个间隔最大的分隔超平面

分隔超平面: $w^{\top}x + b = 0$ 。

决策函数: $f(x) = \text{sign}(w^{\top}x + b)$ 。

优化问题(最大化间隔,等价于在正确分类约束下最小化 $\|w\|$ ):

$\max_{w,b}\ \frac{2}{\|w\|} \quad\Longleftrightarrow\quad \min_{w,b}\ \frac{1}{2}\|w\|^2 \quad \text{s.t.}\quad y_i(w^{\top}x_i + b) \ge 1,\ \forall i$

令函数间隔归一化(令支持向量上 $y_i(w^{\top}x_i+b)=1$ ),上述最大间隔问题就等价于这个带约束的凸二次规划。

软间隔 SVM

现实数据往往线性不可分,需要允许一部分点越界,于是引入松弛,用 Hinge 损失来度量违反程度:

$L_{\text{hinge}}(y, f(x)) = \max\big(0,\ 1 - y\,f(x)\big)$

优化问题在 Hinge 损失基础上加一个控制复杂度的正则项。若采用线性分隔超平面、正则项用 $L_2$ 正则,优化问题可写成

$\min_{w,b}\ \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{n}\max\big(0,\ 1 - y_i(w^{\top}x_i + b)\big)$

其中 $C$ 是正则系数,权衡"间隔大小"与"分类错误"。

把这个无约束问题转化为标准型(引入松弛变量 $\xi_i$ ):

$\min_{w,b,\xi}\ \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{n}\xi_i \quad \text{s.t.}\quad y_i(w^{\top}x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0$

引入拉格朗日乘子,写出拉格朗日函数

$\mathcal{L}(w,b,\xi,\alpha,\mu) = \frac{1}{2}\|w\|^2 + C\sum_i\xi_i - \sum_i\alpha_i\big[y_i(w^{\top}x_i+b) - 1 + \xi_i\big] - \sum_i\mu_i\xi_i$

对 $w$ 、 $b$ 、 $\xi$ 求偏导并令其为零,可以得到

$w = \sum_{i}\alpha_i y_i x_i, \qquad \sum_{i}\alpha_i y_i = 0, \qquad 0 \le \alpha_i \le C$

代回即得对偶问题,求解后 $w$ 只由 $\alpha_i > 0$ 的支持向量决定。

总结

线性回归:加一列全 1 吸收截距,最小二乘闭式解 $\hat\beta = (X^{\top}X)^{-1}X^{\top}y$ ;有闭式解。
逻辑回归:广义线性模型 + logit 联系函数;用线性结果逼近对数几率 $\ln\frac{p}{1-p}=x^{\top}\beta$ ;无闭式解,需迭代;判别线 $x^{\top}\beta=0$ 。
线性判别何时够:两类同方差异均值高斯 → 线性最优;10 个高斯混合 → 线性远远不够。
最近邻: $k$ 个近邻多数表决; $k$ 小边界弯(过拟合), $k$ 大边界平滑。
贝叶斯准则:平方损失下最优预测是条件期望 $E[y\mid x]$ ;0-1 损失下最优是最大后验 $\arg\max_c P(y=c\mid x)$ ;对应最小误差叫贝叶斯误差/风险。
SVM:硬间隔 $\min\frac{1}{2}\|w\|^2$ s.t. $y_i(w^{\top}x_i+b)\ge1$ ;软间隔加 Hinge 损失 + 松弛变量 $\xi_i$ + 正则系数 $C$ ;拉格朗日求导得 $w=\sum\alpha_i y_i x_i$ 、 $\sum\alpha_i y_i=0$ 、 $0\le\alpha_i\le C$ 。