西瓜书学习随记

绪论

NFL(No-Free-Lunch) 定理

假设样本空间 $\mathcal{X}$ 和假设空间 $\mathcal{H}$ 都是离散的，令 $P(h \mid X, \Sigma_a)$ 代表算法 $\Sigma_a$ 基于训练数据 $X$ 产生假设 $h$ 的概率，再令 $f$ 代表我们希望学习的真实目标函数。$\Sigma_a$ 的“训练集外误差”，即 $\Sigma_a$ 在训练集之外的所有样本上的误差为

$$
E_{ote}(\Sigma_a \mid X, f) = \sum_h \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x}) \mathbb{I}(h(\vec{x}) \neq f(\vec{x})) P(h \mid X, \Sigma_a)
$$
$\mathbb{I}(x)$ 是一个指示函数，意义是：若 $x$ 为真，则 $\mathbb{I}(x) = 1$，否则反之

以上公式的含义很显然：对样本空间中不在训练集的样本($\vec{x} \in \mathcal{X} - X$)，先求出算法产生的所有假设与真实函数不符的概率期望；再用样本分布 $P(\vec{x})$ 加权有训练集外样本求和，得到这个算法的总误差期望。

这个总误差期望与算法无关，推导如下

考虑二分类问题，且真实目标函数可以是任何函数 $\mathcal{X} \mapsto {0,1}$，函数空间为 ${0,1}^{|\mathcal{X}|}$。对所有可能的 $f) 按均匀分布对误差求和：

$$
\sum_f E_{ote}(\Sigma_a \mid X, f)
= \sum_f \sum_h \sum_{\vec{x} \in \mathcal{X}-X} P(x) \mathbb{I}(h(\vec{x}) \neq f(\vec{x})) P(h \mid X, \Sigma_a)
\
= \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x}) \sum_h P(h \mid X, \Sigma_a) \sum_f \mathbb{I}(h(\vec{x}) \neq f(\vec{x}))
$$

由于 $f$ 是均匀分布的，对于任意固定的 $\vec{x}$ 和 $h(\vec{x})$，有一半的 $f$ 使得 $f(\vec{x})= h(\vec{x})$，另一半使得 $f(\vec{x}) \neq h(\vec{x})$。因此：

$$
\sum_f \mathbb{I}(h(\vec{x}) \neq f(\vec{x})) = \frac{1}{2} \cdot 2^{|\mathcal{X}|}
$$

代入得：

$$
\sum_f E_{ote}(\Sigma_a \mid X, f)
= \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x}) \sum_h P(h \mid X, \Sigma_a) \cdot \frac{1}{2} \cdot 2^{|\mathcal{X}|}
= \frac{1}{2} \cdot 2^{|\mathcal{X}|} \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x}) \sum_h P(h \mid X, \Sigma_a)
$$

利用概率归一化条件 $\sum_h P(h \mid X, \Sigma_a) = 1$，得：

$$
\sum_f E_{ote}(\Sigma_a \mid X, f)
= \frac{1}{2} \cdot 2^{|\mathcal{X}|} \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x}) \cdot 1
= \frac{1}{2} \cdot 2^{|\mathcal{X}|} \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x})
$$

最终结论：总误差与算法 $\Sigma_a$ 无关

$$
\therefore \sum_f E_{ote}(\Sigma_a \mid X, f) = \frac{1}{2} \cdot 2^{|\mathcal{X}|} \sum_{\vec{x} \in \mathcal{X}-X} P(\vec{x})
$$

这不意味着机器学习没有意义。因为NFL定理成立的前提是所有的问题同等重要、出现机会等同，然而实际上我们很多时候只关注某个具体问题，为某个具体问题找到一个最佳的解决方案，并不关心这个方案对其他问题的好坏。一个学习算法的好坏必须结合实际具体问题来谈

模型评估与选择

数据集划分

要评估模型，自然需要将数据集划分为训练集和测试集，用测试集来评估

留出法，直接将数据集 $D$ 划分为两个互斥的集合：训练集 $S$ 和测试集 $T$
交叉验证法就是将数据集化成 $k$ 个大小相似的互斥子集，每次用 $k-1$ 个子集作为训练集，另一个作为测试集。称为 $k$ 折交叉验证

这里若取 $k = m$，$m$ 为数据集 $D$ 的样本数，则此时为交叉验证法的特例：留一法，优点是评估结果往往比较准确可置信，缺点是训练计算开销大

自助法就是有放回地随机抽取 $m$ 次，$m$ 为数据集 $D$ 的样本数。如此得到和 $D$ 等大的训练集 $S$。需要注意的是可以做一个简单的估计，样本在 $m$ 次采样中始终不被采到的概率是 $(1 - \frac{1}{m})^m$ , 取极限得到概率约为 $\frac{1}{e}$，越有占比 $0.368$ 的样本未出现在 $S$，这些样本恰作为测试集 $T$

性能度量

回归任务最常用的性能度量是均方误差：对于数据分布 $\mathcal{D}$ 、学习器 $f$ 和概率密度函数 $p(\vec{x})$，把学习器预测结果 $f(\vec{x})$ 与真实标记 $\vec{y}$ 进行比较.
$$
E(f; \mathcal{D}) = \int_{\vec{x} \sim \mathcal{D}} (f(\vec{x}) - \vec{y})^2 p(\vec{x}) \mathrm{d}\vec{x}
$$
分类任务采用的性能度量如下：

错误率与精度

对样例集 $D$（共 $m$ 个样本），错误率是分类错误的样本数占样本总数的比例，精度是分类正确的样本数占样本总数的比例，二者互补：

$$
E(f; D) = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\big(f(\vec{x}_i) \neq \vec{y}i\big),
acc(f; D) = \frac{1}{m}\sum{i=1}^{m}\mathbb{I}\big(f(\vec{x}_i) = \vec{y}_i\big) = 1 - E(f; D)
$$

它们既适用于二分类也适用于多分类

查准率、查全率与 F1

对二分类问题，样例按真实类别与预测类别的组合分成四种情形，即“混淆矩阵”：

真实情况 / 预测结果	正例	反例
正例	TP（真正例）	FN（假反例）
反例	FP（假正例）	TN（真反例）

查准率 $P$ 关心“挑出来的正例中有多少是真的”，查全率 $R$ 关心“真正的正例有多少被挑了出来”：

$$
P = \frac{TP}{TP + FP}, \qquad R = \frac{TP}{TP + FN}
$$

两者互相矛盾：多挑一些（放宽标准）查全率会上升，但混进来的错误会拉低查准率；只挑最有把握的则相反

若把样例按“最可能是正例”到“最不可能是正例”排序，逐个划为正例并每次都算出一对 $(R, P)$，以 $R$ 为横轴、$P$ 为纵轴作图就得到 P-R 曲线。

一条曲线被另一条完全包住时后者更优；两条曲线交叉时无法一般性地判定优劣，只能比曲线下面积，或用“平衡点”BEP（$P = R$ 处的取值）作粗略判据。

更常用的是 $F1$，它是查准率与查全率的调和平均，因而更重视两者中较小的那个：

$$
F1 = \frac{2 \times P \times R}{P + R} = \frac{2 \times TP}{\text{样例总数} + TP - TN}
$$

一般形式 $F_\beta$ 可以表达对二者的不同偏好，或者说调节惩罚力度，$\beta > 1$ 时查全率影响更大（如逃犯信息检索），$\beta < 1$ 时查准率影响更大（如商品推荐）：

$$
F_\beta = \frac{(1 + \beta^2) \times P \times R}{(\beta^2 \times P) + R}
$$

多次训练/测试、多个数据集，或多分类任务中每两两类别的组合，都会得到 $n$ 个混淆矩阵，此时有两种汇总方式：先在各混淆矩阵上分别算出 $(P_i, R_i)$ 再取平均，得到宏查准率、宏查全率与宏 $F1$；或者先把各混淆矩阵的 $TP, FP, TN, FN$ 分别取平均，再基于这些平均值算出微查准率、微查全率与微 $F1$

ROC 与 AUC

很多学习器输出的是实值或概率，与一个分类阈值比较后才给出类别；这样，分类过程就相当于在实值或者概率排序中以某个”截断点”(cut point)将样本分为两部分，前一部分判作正例，后一部分则判作反例

排序本身的质量好坏，体现了综合考虑学习器在不同任务下的”期望泛化性能”的好坏，我们需要一个指标来评估它

ROC 的纵轴是真正例率 $TPR = \frac{TP}{TP + FN}$（即查全率），横轴是假正例率 $FPR = \frac{FP}{TN + FP}$。

绘制方法是：先把阈值设为最大，即所有样例都判为反例，在 $(0,0)$ 处标记一点；然后依次把每个样例划为正例，若当前样例是真正例则向上移动 $\frac{1}{m^+}$，若是假正例则向右移动 $\frac{1}{m^-}$（$m^+$、$m^-$ 分别为样本中的正例、反例数），最后用线段连接相邻点

比较曲线下面积：也就是 AUC 来判定 ROC 曲线的好坏，将其视为一个个小的梯形切片，可估算为：
$$
\mathrm{AUC} = \frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1} - x_i)(y_i + y_{i+1})
$$
AUC 与排序误差有直接联系。给定 $m^+$ 个正例和 $m^-$ 个反例，排序“损失”定义为

$$
\ell_{rank} = \frac{1}{m^+ m^-}\sum_{\vec{x}^+ \in D^+}\sum_{\vec{x}^- \in D^-}\left[\mathbb{I}\big(f(\vec{x}^+) < f(\vec{x}^-)\big) + \frac{1}{2}\mathbb{I}\big(f(\vec{x}^+) = f(\vec{x}^-)\big)\right]
$$

也就是逐对考察正、反例：正例的预测值小于反例记一个罚分，二者相等记半个罚分。$\ell_{rank}$ 恰是 ROC 曲线上方的面积，故有 $\mathrm{AUC} = 1 - \ell_{rank}$。

代价敏感错误率与代价曲线

前面的度量都隐含地假设各类错误的代价相同，而现实中并非如此。我们需要给错误赋予非均等代价 $\mathrm{cost}{ij}$，它表示把第 $i$ 类样本预测为第 $j$ 类的代价，一般 $cost{ii} = 0$，而且重要的是代价之间的比值而非绝对值。此时我们不再是最小化错误次数，而是最小化总体代价。以第 0 类为正类、第 1 类为反类，代价敏感错误率为

$$
E(f; D; \mathrm{cost}) = \frac{1}{m}\left(\sum_{\vec{x}_i \in D^+}\mathbb{I}\big(f(\vec{x}i) \neq \vec{y}i\big) \times \mathrm{cost}{01} + \sum{\vec{x}_i \in D^-}\mathbb{I}\big(f(\vec{x}_i) \neq \vec{y}i\big) \times \mathrm{cost}{10}\right)
$$

在非均等代价下 ROC 曲线不能直接反映学习器的期望总体代价，代价曲线则可以

代价曲线的横轴是取值为 $[0,1]$ 的正例概率代价
$$
P(+){cost} = \frac{p \times \mathrm{cost}{01}}{p \times \mathrm{cost}{01} + (1 - p) \times \mathrm{cost}{10}}
$$

纵轴是取值为 $[0,1]$ 的归一化代价

$$
\mathrm{cost}{norm} = \frac{实际期望代价}{最坏期望代价} = \frac{FNR \times p \times \mathrm{cost}{01} + FPR \times (1 - p) \times \mathrm{cost}{10}}{p \times \mathrm{cost}{01} + (1 - p) \times \mathrm{cost}_{10}}
$$

其中 $p$ 是样例为正例的概率，$FNR = 1 - TPR$ 是假反例率，$FPR$ 是假正例率。ROC 曲线上的每一点 $(TPR, FPR)$ 都对应代价平面上一条从 $(0, FPR)$ 到 $(1, FNR)$ 的线段，每条线段下的面积就是该条件下的期望总体代价；取所有线段的下界，围成的面积即为所有条件下学习器的期望总体代价

比较检验

有了评估方法和性能度量，也不能直接把结果拿来比大小：我们想比较的是泛化性能，实际拿到的却是某个测试集上的测试性能；测试集本身的选择会带来差异；很多算法还带有随机性，相同参数在同一测试集上多次运行结果也不相同

统计假设检验提供了判断依据——若在测试集上观察到学习器 A 比 B 好，A 的泛化性能是否在统计意义上更优，以及这个结论的把握有多大（本小节以错误率为性能度量，记为 $E$）

基本是概率论学习过的内容并且有些繁琐，姑且先照搬：

二项检验：泛化错误率为 $\epsilon$ 的学习器在 $m$ 个测试样本上恰有 $\vec{E} \times m$ 个被误分类的概率为 $P(\vec{E}; \epsilon) = \binom{m}{\vec{E} \times m}\epsilon^{\vec{E} \times m}(1 - \epsilon)^{m - \vec{E} \times m}$，它遵从二项分布，并在 $\epsilon = \vec{E}$ 时取最大值。对假设 “$\epsilon \le \epsilon_0$”，可由 $\sum_{i = \bar{\epsilon}m + 1}^{m}\binom{m}{i}\epsilon_0^i(1 - \epsilon_0)^{m - i} < \alpha$ 解出 $1 - \alpha$ 置信度内所能观测到的最大错误率 $\bar{\epsilon}$；若测试错误率 $\vec{E} < \bar{\epsilon}$，则在该显著度下不能拒绝该假设
t 检验：多次留出法或交叉验证会得到 $k$ 个测试错误率 $\vec{E}_1, \dots, \vec{E}_k$，可看作泛化错误率 $\epsilon_0$ 的独立采样，其均值 $\mu$ 与方差 $\sigma^2$ 如常计算，则变量 $\tau_t = \frac{\sqrt{k}(\mu - \epsilon_0)}{\sigma}$ 服从自由度为 $k - 1$ 的 t 分布。给定显著度 $\alpha$，若 $|\mu - \epsilon_0|$ 落在临界值范围内，则不能拒绝 “$\mu = \epsilon_0$”，即可用 $1 - \alpha$ 的置信度认为泛化错误率就是 $\epsilon_0$
交叉验证 t 检验：比较两个学习器 A、B 时，它们在同一个第 $i$ 折训练/测试集上的结果之差为 $\Delta_i = E_i^A - E_i^B$；若两者性能相同，这些差值的均值应为零，于是可用 $\tau_t = \left|\frac{\sqrt{k}\mu}{\sigma}\right|$（$\mu$、$\sigma^2$ 为差值的均值与方差）与临界值 $t_{\alpha/2, k-1}$ 比较。需要注意的是，样本有限时不同轮次的训练集会有重叠，测试错误率并不独立，这会高估“假设成立”的概率；为此可采用 5×2 交叉验证（做 5 次 2 折交叉验证，每次之前重新打乱数据，使 5 次划分互不重复），取第一次 2 折两个差值的均值 $\mu = \frac{1}{2}(\Delta_1^1 + \Delta_1^2)$，同时对每次 2 折的结果都算出方差 $\sigma_i^2$，则变量 $\tau_t = \frac{\mu}{\sqrt{0.2\sum_{i=1}^{5}\sigma_i^2}}$ 服从自由度为的 t分布
McNemar 检验：用留出法还能得到两个学习器分类结果的差别，即列联表（两者都正确 $e_{00}$、A 对 B 错 $e_{01}$、A 错 B 对 $e_{10}$、都错 $e_{11}$）。若两学习器性能相同，应有 $e_{01} = e_{10}$，此时变量 $\tau_{\chi^2} = \frac{(|e_{01} - e_{10}| - 1)^2}{e_{01} + e_{10}}$ 服从自由度为 1 的 $\chi^2$ 分布（即标准正态分布变量的平方）；它小于临界值则不能拒绝“性能相同”
Friedman 检验与 Nemenyi 后续检验：要在一组数据集上比较多个算法时，先在各数据集上按测试性能由好到坏排名、赋予序值（性能相同则平分序值），设第 $i$ 个算法在 $N$ 个数据集上的平均序值为 $r_i$（共比较 $k$ 个算法），则 $r_i$ 的均值与方差分别为 $\frac{k+1}{2}$ 与 $\frac{k^2-1}{12}$；在 $k$、$N$ 都较大时，变量 $\tau_{\chi^2} = \frac{12N}{k(k+1)}\left(\sum_{i=1}^{k}r_i^2 - \frac{k(k+1)^2}{4}\right)$ 服从自由度为 $k - 1$ 的 $\chi^2$ 分布。原始 Friedman 检验过于保守，通常改用 $\tau_F = \frac{(N-1)\tau_{\chi^2}}{N(k-1) - \tau_{\chi^2}}$，它服从自由度为 $k-1$ 和 $(k-1)(N-1)$ 的 F 分布。若“所有算法性能相同”被拒绝，则用 Nemenyi 后续检验判断两两之间是否有显著差别：平均序值之差超过临界值域 $CD = q_\alpha\sqrt{\frac{k(k+1)}{6N}}$ 的两个算法才算有显著差别

偏差与方差

偏差-方差分解回答的是学习算法“为什么”具有这样的泛化性能，做法是把期望泛化误差拆开。

对测试样本 $\vec{x}$，令 $\vec{y}_D$ 为 $\vec{x}$ 在数据集中的标记（可能存在标注错误等等误差），$\vec{y}$ 为 $\vec{x}$ 的真实标记，$f(\vec{x}; D)$ 为训练集 $D$ 上学得的模型在 $\vec{x}$ 上的预测输出，以回归任务为例：
$$
\bar{f}(\vec{x}) = \mathbb{E}_D\big[f(\vec{x}; D)\big]
$$

$$
var(\vec{x}) = \mathbb{E}_D\Big[\big(f(\vec{x}; D) - \bar{f}(\vec{x})\big)^2\Big], \qquad
\varepsilon^2 = \mathbb{E}_D\big[(\vec{y}_D - \vec{y})^2\big], \qquad
bias^2(\vec{x}) = \big(\bar{f}(\vec{x}) - \vec{y}\big)^2
$$

三者的含义分别是：

方差度量同样大小的训练集的变动所导致的性能变化，即数据扰动造成的影响；
噪声表达当前任务上任何学习算法所能达到的期望泛化误差下界，即学习问题本身的难度；
偏差度量期望预测与真实结果的偏离程度，即学习算法本身的拟合能力

假定噪声期望为零，即 $\mathbb{E}_D[\vec{y}_D - \vec{y}] = 0$，把期望泛化误差展开并合并，交叉项为零，最终得到

$$
E(f; D) = \mathbb{E}_D\big[(f(\vec{x}; D) - \vec{y})^2\big] = bias^2(\vec{x}) + var(\vec{x}) + \varepsilon^2
$$

即泛化误差可分解为偏差、方差与噪声之和，泛化性能由学习算法的能力、数据的充分性以及学习任务本身的难度共同决定。给定任务，要取得好的泛化性能，就需使偏差较小（能充分拟合数据）且方差较小（数据扰动的影响小）

偏差与方差通常是冲突的，这称为偏差-方差窘境：训练不足时拟合能力不够，训练数据的扰动不足以使学习器产生显著变化，偏差主导泛化错误率；随着训练程度加深，拟合能力逐渐增强，数据扰动渐渐被学到，方差开始主导；训练程度充足后，训练数据自身的、非全局的特性也会被学进去，于是发生过拟合。这也从另一个角度解释了欠拟合与过拟合

线性模型

基本形式

线性模型试图学得一个通过属性的线性组合来进行预测的函数。给定由 $d$ 个属性描述的示例 $\vec{x} = (x_1; x_2; \dots; x_d)$，其中 $x_i$ 是 $\vec{x}$ 在第 $i$ 个属性上的取值：

$$
f(\vec{x}) = w_1x_1 + w_2x_2 + \dots + w_dx_d + b = \vec{w}^T\vec{x} + b
$$

其中 $\vec{w} = (w_1; w_2; \dots; w_d)$，$\vec{w}$ 与 $b$ 学得后模型就确定了。线性模型形式简单、易于建模，$\vec{w}$ 直观表达了各属性在预测中的重要性，因此有很好的可解释性；许多功能更强的非线性模型都是在线性模型的基础上通过引入层级结构或高维映射得到的。

线性回归

线性回归要学得一个线性模型以尽可能准确地预测实值输出标记。先看输入属性只有一个的情形，数据集 $D = {(x_i, y_i)}_{i=1}^{m}$（此时 $x_i$ 是实数）。确定 $w$ 和 $b$ 的关键是衡量预测值 $f(x_i)$ 与真实标记 $y_i$ 的差别，而均方误差是回归任务最常用的性能度量，于是令其最小化：

$$
(w^, b^) = \arg\min_{(w, b)} \sum_{i=1}^{m}(y_i - wx_i - b)^2
$$

均方误差有明确的几何意义，它对应欧氏距离，因此这种基于均方误差最小化来求解模型的方法称为“最小二乘法”。

上式关于 $w$ 和 $b$ 是凸函数，分别对二者求导并令其为零，可得闭式解
$$
w = \frac{\sum_{i=1}^{m}y_i(x_i - \bar{x})}{\sum_{i=1}^{m}x_i^2 - \frac{1}{m}\left(\sum_{i=1}^{m}x_i\right)^2}, \qquad b = \bar{y} - w\bar{x}
$$

其中 $\bar{x} = \frac{1}{m}\sum_i x_i$ 是 $x$ 的均值。分母恰是 $\sum_i (x_i - \bar{x})^2$，分子恰是 $\sum_i (x_i - \bar{x})(y_i - \bar{y})$，这说明 $w$ 只由属性的离差与标记的离差决定，是二者协方差与属性方差之比

更一般的情形是样本由 $d$ 个属性描述，即“多元线性回归”

也就是
$$
f(\vec{x_i}) = \vec{w}^T\vec{x_i} + b
$$
如上， $m$ 个这样的方程。

为便于讨论，把 $w$ 与 $b$ 吸收入向量 $\tilde{\vec{w}} = (\vec{w}; b)$，并把数据集表示成 $m \times (d+1)$ 的矩阵 $X$，每行对应一个示例，该行前 $d$ 个元素是属性值、最后一个元素恒为 $1$；把标记写成向量 $\vec{y} = (y_1; y_2; \dots; y_m)$（$y_i$ 也就是 $f(\vec{x_i})$），如下图

再把标记也写成向量形式 $\vec{y}=(y_1; y_2;… ;y_m)$，如下
$$
\tilde{\vec{w}}^* = \arg\min_{\tilde{\vec{w}}} (\vec{y} - X\tilde{\vec{w}})^T(\vec{y} - X\tilde{\vec{w}})
$$

记 $E_{\tilde{\vec{w}}} = (\vec{y} - X\tilde{\vec{w}})^T(\vec{y} - X\tilde{\vec{w}})$，对 $\tilde{\vec{w}}$ 求导得 $\frac{\partial E_{\tilde{\vec{w}}}}{\partial \tilde{\vec{w}}} = 2X^T(X\tilde{\vec{w}} - \vec{y})$，令其为零即得

$$
\tilde{\vec{w}}^* = (X^TX)^{-1}X^T\vec{y} \quad (\text{当 } X^TX \text{ 为满秩矩阵或正定矩阵时})
$$

现实任务中 $X^TX$ 往往不是满秩矩阵，例如变量数目超过样例数时 $X$ 的列数多于行数，此时可解出多个 $\tilde{\vec{w}}$，它们都能使均方误差最小；选择哪一个由学习算法的归纳偏好决定，常见做法是引入正则化项

线性模型还有丰富的变化：若希望模型预测值逼近 $y$ 的衍生物，例如认为输出标记在指数尺度上变化，可令 $\ln y = \vec{w}^T\vec{x} + b$，这称为“对数线性回归”，它形式上仍是线性回归，实质上是在求输入空间到输出空间的非线性映射（用 $e^{\vec{w}^T\vec{x}+b}$ 逼近 $y$）；

更一般地，对单调可微函数 $g(\cdot)$，令 $y = g^{-1}(\vec{w}^T\vec{x} + b)$，就得到“广义线性模型”，$g$ 称为“联系函数”，显然对数线性回归是 $g(\cdot) = \ln(\cdot)$ 时的特例

对数几率回归

要做分类任务，只需在广义线性模型中找一个单调可微函数，把分类任务的真实标记 $y$ 与线性回归产生的预测值 $z = \vec{w}^T\vec{x} + b$ 联系起来。用单调可微的“对数几率函数”：
$$
y = \frac{1}{1 + e^{-z}} = \frac{1}{1 + e^{-(\vec{w}^T\vec{x} + b)}}
$$

对数几率函数是一种 Sigmoid 函数，它把 $z$ 映射到 $(0, 1)$ 作为正类概率，且在 $z = 0$ 附近变化很陡。把上式变形可得

$$
\ln\frac{y}{1 - y} = \vec{w}^T\vec{x} + b
$$

$y$ 为样本 $\vec{x}$ 为正例的可能性，则 $1 - y$ 是其为反例的可能性，二者之比 $\frac{y}{1-y}$ 称为“几率”，反映了 $\vec{x}$ 作为正例的相对可能性，对几率取对数即为“对数几率”。所以上式是在用线性回归的预测结果去逼近真实标记的对数几率，对应的模型称为“对数几率回归”（名字里虽有“回归”，实际是一种分类学习方法）

它的好处是：直接对分类可能性建模，无需事先假设数据分布；不是只给出类别，而是给出近似概率预测；对率函数是任意阶可导的凸函数，许多数值优化算法都可直接用来求最优解。

下面看 $\vec{w}$ 和 $b$ 怎么确定。把 $y$ 视为类后验概率估计 $p(y=1 \mid \vec{x})$，则可以解出

$$
p(y=1 \mid \vec{x}) = \frac{e^{\vec{w}^T\vec{x}+b}}{1 + e^{\vec{w}^T\vec{x}+b}}, \qquad p(y=0 \mid \vec{x}) = \frac{1}{1 + e^{\vec{w}^T\vec{x}+b}}
$$

用概率论中学过的极大似然法估计参数

令上式子概率最大也就是让每个样本 $\vec{x_i}$ 属于其真实标记 $y_i$ 的概率越大越好。取对数即：
$$
\ell(\vec{w}, b) = \sum_{i=1}^{m}\ln p(y_i \mid \vec{x}_i; \vec{w}, b)
$$
令 $\vec{\beta} = (\vec{w}; b)$、$\tilde{\vec{x}}_i = (\vec{x}_i; 1)$（与多元线性回归中把 $b$ 吸入向量的做法一样），则 $\vec{w}^T\vec{x}_i + b$ 可简写为 $\vec{\beta}^T\tilde{\vec{x}}_i$，并记 $p_1 = p(y=1 \mid \tilde{\vec{x}}; \vec{\beta})$、$p_0 = 1 - p_1$，则似然项可写成
$$
p(y_i \mid \tilde{\vec{x}}_i; \vec{\beta}) = y_i,\ln [p_1(\vec{x_i};\beta)] + (1 - y_i),\ln p_0[(\vec{x_i};\beta)]
$$
把 $p_1, p_0$ 的表达式 $p_1(\vec{x_i};\beta) = \frac{e^{\vec{\beta}^T\tilde{\vec{x}}_i}}{1+e^{\vec{\beta}^T\tilde{\vec{x}}_i}}, p_0(\vec{x_i};\beta) = \frac{1}{1+e^{\vec{\beta}^T\tilde{\vec{x}}i}}$ 代入
$$
\ell(\vec{w}; b) = -\sum{i=1}^{m}\left(-y_i\vec{\beta}^T\tilde{\vec{x}}_i + \ln\left(1 + e^{\vec{\beta}^T\tilde{\vec{x}}_i}\right)\right)
$$

则求其最大似然也就是最小化：
$$
\ell(\vec{\beta}) = \sum_{i=1}^{m}\left(-y_i\vec{\beta}^T\tilde{\vec{x}}_i + \ln\left(1 + e^{\vec{\beta}^T\tilde{\vec{x}}_i}\right)\right)
$$
这里因为原书符号有点问题，这里$\ell(\vec{\beta})$ 和 $\ell(\vec{w}; b)$ 是一个东西，但为了下面公式表述方便还是用 $\ell(\vec{\beta})$ 表示 $-\ell(\vec{w}; b)$

它是关于 $\vec{\beta}$ 的高阶可导连续凸函数，用梯度下降法、牛顿法等都能求得最优解。以牛顿法为例，第 $t+1$ 轮迭代的更新公式为
$$
\vec{\beta}^{t+1} = \vec{\beta}^{t} - \left(\frac{\partial^2 \ell(\vec{\beta})}{\partial \vec{\beta},\partial \vec{\beta}^T}\right)^{-1}\frac{\partial \ell(\vec{\beta})}{\partial \vec{\beta}}
$$

其中一阶导与二阶导分别是

$$
\frac{\partial \ell(\vec{\beta})}{\partial \vec{\beta}} = -\sum_{i=1}^{m}\tilde{\vec{x}}_i\left(y_i - p_1(\tilde{\vec{x}}i; \vec{\beta})\right), \qquad
\frac{\partial^2 \ell(\vec{\beta})}{\partial \vec{\beta},\partial \vec{\beta}^T} = \sum{i=1}^{m}\tilde{\vec{x}}_i\tilde{\vec{x}}_i^T, p_1(\tilde{\vec{x}}_i; \vec{\beta})\left(1 - p_1(\tilde{\vec{x}}_i; \vec{\beta})\right)
$$

这里大致含义就是不断往梯度下降的方向走，梯度本身变化的快则走得慢，梯度变化的慢则走得快一些

线性判别分析

线性判别分析（LDA，二分类时亦称 Fisher 判别分析）的思想很朴素：把样例投影到一条直线上，使同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；对新样本，也投影到这条直线上，再根据投影点的位置确定类别

给定数据集 $D = {(\vec{x}i, y_i)}{i=1}^{m}$，$y_i \in {0,1}$，令 $X_i$、$\vec{\mu}_i$、$\Sigma_i$ 分别表示第 $i$ 类示例的集合、均值向量与协方差矩阵

对随机变量 (X,Y)：
$$
\operatorname{Cov}(X,Y)=\mathbb{E}\big[(X-\mathbb{E}X)(Y-\mathbb{E}Y)\big]
$$
对随机向量 (\vec{x}\in\mathbb{R}^d)，均值 (\boldsymbol{\mu}=\mathbb{E}[\vec{x}])，协方差矩阵：
$$
\Sigma=\mathbb{E}\big[(\vec{x}-\boldsymbol{\mu})(\vec{x}-\boldsymbol{\mu})^\top\big]
$$

若把数据投影到直线 $\vec{w}$ 上，则两类中心在直线上的投影分别是 $\vec{w}^T\vec{\mu}_0$ 与 $\vec{w}^T\vec{\mu}_1$，两类样本的投影协方差分别是 $\vec{w}^T\Sigma_0\vec{w}$ 与 $\vec{w}^T\Sigma_1\vec{w}$（直线是一维空间，所以这些都是实数）

设投影方向为 (\vec{w})，投影标量：
$$
y=\vec{w}^\top\vec{x}
$$
均值：
$$
\mathbb{E}[y]=\vec{w}^\top\boldsymbol{\mu}
$$
方差：
$$
\begin{aligned}
\operatorname{Var}(y)
&=\mathbb{E}\big[(y-\mathbb{E}[y])^2\big] \
&=\mathbb{E}\big[(\vec{w}^\top(\vec{x}-\boldsymbol{\mu}))^2\big] \
&=\mathbb{E}\big[\vec{w}^\top(\vec{x}-\boldsymbol{\mu})(\vec{x}-\boldsymbol{\mu})^\top\vec{w}\big] \
&=\vec{w}^\top \mathbb{E}\big[(\vec{x}-\boldsymbol{\mu})(\vec{x}-\boldsymbol{\mu})^\top\big]\vec{w} \
\end{aligned}
$$
协方差矩阵定义就是：$\Sigma=\mathbb{E}\big[(\vec{x}-\boldsymbol{\mu})(\vec{x}-\boldsymbol{\mu})^\top\big]$ 因此投影后直线上一类样本的协方差为：
$$
\boxed{\operatorname{Var}(y)=\vec{w}^\top\Sigma\vec{w}}
$$

“同类尽可能近”就是让 $\vec{w}^T\Sigma_0\vec{w} + \vec{w}^T\Sigma_1\vec{w}$ 尽量小
“异类尽可能远”就是让 $|\vec{w}^T\vec{\mu}_0 - \vec{w}^T\vec{\mu}_1|_2^2$ 尽量大

二者同时考虑，即得最大化的目标：
$$
J = \frac{|\vec{w}^T\vec{\mu}_0 - \vec{w}^T\vec{\mu}_1|_2^2}{\vec{w}^T\Sigma_0\vec{w} + \vec{w}^T\Sigma_1\vec{w}} = \frac{\vec{w}^T(\vec{\mu}_0 - \vec{\mu}_1)(\vec{\mu}_0 - \vec{\mu}_1)^T\vec{w}}{\vec{w}^T(\Sigma_0 + \Sigma_1)\vec{w}} = \frac{\vec{w}^TS_b\vec{w}}{\vec{w}^TS_w\vec{w}}
$$

其中类内散度矩阵 $S_w = \Sigma_0 + \Sigma_1 = \sum_{\vec{x} \in X_0}(\vec{x} - \vec{\mu}_0)(\vec{x} - \vec{\mu}0)^T + \sum{\vec{x} \in X_1}(\vec{x} - \vec{\mu}_1)(\vec{x} - \vec{\mu}_1)^T$，类间散度矩阵 $S_b = (\vec{\mu}_0 - \vec{\mu}_1)(\vec{\mu}_0 - \vec{\mu}_1)^T$。$J$ 就是 $S_b$ 与 $S_w$ 的广义瑞利商

注意到 $J$ 的分子分母都是关于 $\vec{w}$ 的二次型

矩阵的二次型 $\vec{x}^{T}A\vec{x}$ 就是向量 $\vec{x}$ 的各分量经过矩阵 $A$ 加权后的二次齐次多项式，它衡量了 $A$ 在方向 $\vec{x}$ 上的“大小”或“能量”。在协方差中，它正好表示数据沿该方向的方差

它的解与 $\vec{w}$ 的长度无关、只与方向有关，因此不妨令 $\vec{w}^TS_w\vec{w} = 1$，于是最大化 $J$ 等价于
$$
\min_{\vec{w}} -\vec{w}^TS_b\vec{w}，s.t.\space\vec{w}^TS_w\vec{w} = 1
$$
由拉格朗日乘子法可得，求
$$
\min(-\vec{w}^TS_b\vec{w} + \lambda(\vec{w}^TS_w\vec{w}-1))
$$
即
$$
\frac{\partial[-\vec{w}^TS_b\vec{w} + \lambda(\vec{w}^TS_w\vec{w}-1)]}{\partial\vec{w}} = S_{b}\vec{w} - \lambda S_{w}\vec{w} = 0
$$
得到 $S_b\vec{w} = \lambda S_w\vec{w}$，其中 $\lambda$ 是拉格朗日乘子。又因 $S_b\vec{w} = (\vec{\mu}_0 - \vec{\mu}_1)(\vec{\mu}_0 - \vec{\mu}_1)^T\vec{w}$，而 $(\vec{\mu}_0 - \vec{\mu}_1)^T\vec{w}$ 是实数，所以 $S_b\vec{w}$ 的方向恒为 $\vec{\mu}_0 - \vec{\mu}_1$，不妨令 $S_b\vec{w} = \lambda(\vec{\mu}_0 - \vec{\mu}_1)$，代入上式即得
$$
\vec{w} = S_w^{-1}(\vec{\mu}_0 - \vec{\mu}_1)
$$

对 $S_{w}$ 实践上可能很困难，所以通常对 $S_w$ 做奇异值分解 $S_w = U\Sigma V^T$，再由 $S_w^{-1} = V\Sigma^{-1}U^T$ 得到 $S_w^{-1}$

值得一提的是，从贝叶斯决策理论的角度可以证明：当两类数据同先验、满足高斯分布且协方差相等时，LDA 可达到最优分类

LDA 也可推广到多分类。假定有 $N$ 个类，第 $i$ 类示例数为 $m_i$，定义全局散度矩阵

$$
S_t = S_b + S_w = \sum_{i=1}^{m}(\vec{x}_i - \vec{\mu})(\vec{x}_i - \vec{\mu})^T
$$

其中 $\vec{\mu}$ 是所有示例的均值向量；把类内散度矩阵重定义为各类散度矩阵之和 $S_w = \sum_{i=1}^{N}S_{w_i}$，$S_{w_i} = \sum_{\vec{x} \in X_i}(\vec{x} - \vec{\mu}_i)(\vec{x} - \vec{\mu}i)^T$，于是 $S_b = S_t - S_w = \sum{i=1}^{N}m_i(\vec{\mu}_i - \vec{\mu})(\vec{\mu}_i - \vec{\mu})^T$。常见的优化目标是

$$
\max_{W}\frac{tr(W^TS_bW)}{tr(W^TS_wW)}
$$

其中 $W \in \mathbb{R}^{d \times (N-1)}$，$tr(\cdot)$ 表示矩阵的迹；它可通过广义特征值问题 $S_bW = \lambda S_wW$ 求解，$W$ 的闭式解是 $S_w^{-1}S_b$ 的 $N-1$ 个最大广义特征值所对应的特征向量组成的矩阵。把 $W$ 视为投影矩阵，多分类 LDA 就把样本投影到 $N-1$ 维空间（通常远小于原属性数），且投影过程中用到了类别信息，因此 LDA 也常被视为一种经典的监督降维技术

多分类学习

现实中常有多分类任务，其基本思路是“拆解法”：把多分类任务拆为若干个二分类任务，为每个二分类任务训练一个分类器，测试时再对这些分类器的预测结果进行集成。实践中这种做法可能比较少见到，这里就简单介绍一下拆分策略：

“一对一”（OvO）：把 $N$ 个类别两两配对，产生 $N(N-1)/2$ 个二分类任务，例如为区分类别 $C_i$ 与 $C_j$ 而训练的分类器把 $C_i$ 类样例作为正例、$C_j$ 类样例作为反例。测试时新样本同时提交给所有分类器，得到 $N(N-1)/2$ 个结果，最终由投票产生——被预测得最多的类别即为结果
“一对其余”（OvR）：每次把一个类的样例作为正例、所有其他类的样例作为反例，共训练 $N$ 个分类器。测试时若仅有一个分类器预测为正类，则该类的标记即为结果；若有多个分类器预测为正类，则通常取预测置信度最大的类别

“多对多”（MvM）：每次将若干个类作为正类、若干个其他类作为反类，OvO 与 OvR 都是它的特例。MvM 通过编码矩阵让每个类别对应一个二进制码，每个二分类器负责区分码位上不同的类别组合。预测时，用所有二分类器的输出组成一个码，再与各类别的码比较，距离最小的类别即为预测结果

如上图是最常见的二元码和三元码编码方式，前者将每个类别分别指定为正类和反类，后者在正、反类之外，还可指定”停用类；

测试示例经过所有二分类器预测后，得到一个编码向量 $\vec{y}$。每个类别 $C_i$ 也有一个预定义的编码向量 $\vec{c_i}$；分别计算 $\vec{y}$ 与各个 $\vec{c_i}$ 间的海明距离和欧式距离

距离最小的类别即为预测结果

OvR 只需训练 $N$ 个分类器，OvO 需训练 $N(N-1)/2$ 个，因此 OvO 的存储开销与测试时间开销通常更大；但 OvR 的每个分类器都用全部训练样例，OvO 的每个分类器只用两个类的样例，所以类别很多时 OvO 的训练时间开销通常更小。预测性能则取决于具体的数据分布，多数情形下两者差不多

类别不平衡问题

前面的分类方法都有一个共同的基本假设：不同类别的训练样例数目相当。若差别很大，学习过程就会受困扰——例如有 998 个反例、2 个正例，学习器只要永远预测反例就能达到 99.8% 的精度，但它预测不出任何正例，毫无价值。这种不同类别训练样例数目差别很大的情况称为“类别不平衡”

从线性分类器看最容易理解：用 $y = \vec{w}^T\vec{x} + b$ 对新样本分类（这里的 $y$ 指对率回归输出的预测值），实际上是在拿预测值 $y$ 与一个阈值比较（通常 $y > 0.5$ 判为正例），而 $y$ 表达了正例的可能性，$\frac{y}{1-y}$ 则是正例与反例可能性之比，阈值取 $0.5$ 恰好意味着分类器认为正、反例可能性相同，即决策规则为

$$
\text{若 } \frac{y}{1-y} > 1 \text{ 则预测为正例}
$$

然而训练集中正、反例数目不同时，正例数 $m^+$ 与反例数 $m^-$ 之比才是观测几率；若假设训练集是真实样本总体的无偏采样，观测几率就代表了真实几率，于是只要预测几率高于观测几率就应判为正例：

$$
\text{若 } \frac{y}{1-y} > \frac{m^+}{m^-} \text{ 则预测为正例}
$$

只需令

$$
\frac{y’}{1-y’} = \frac{y}{1-y} \times \frac{m^-}{m^+}
$$

这样调整一下决策的阈值；这就是类别不平衡学习的基本策略“再缩放”

但是“训练集是无偏采样”这个假设往往并不成立。现有技术大体有三类做法

欠采样，直接去掉一些反例使正、反例数目接近后再学习，其时间开销通常远小于过采样（训练集变小了），但随机丢弃反例可能丢失重要信息，代表性算法 EasyEnsemble 利用集成学习机制把反例划分为若干集合供不同学习器使用，从而在全局上不丢失信息；
过采样，增加一些正例使数目接近，注意不能简单重复采样否则会招致严重过拟合，代表性算法 SMOTE 通过对正例插值来产生额外的正例；
阈值移动，直接基于原始训练集学习，但在预测时使用上面的再放缩过的式子来进行分类决策，此时也就是基于正负类的实际比例来移动了预测分类的阈值

再缩放也是代价敏感学习的基础：把上式中的 $\frac{m^-}{m^+}$ 换成 $\frac{cost_+}{cost_-}$ 即可，其中 $cost_+$ 是把正例误分为反例的代价，$cost_-$ 是把反例误分为正例的代价

决策树

基本流程

决策树基于树结构进行决策：叶结点对应决策结果，其他每个结点对应一个属性测试，每个结点包含的样本集合根据属性测试结果被划分到子结点中，根结点包含样本全集。从根结点到每个叶结点的路径对应一个判定测试序列

决策树学习的目的是为了产生一棵泛化能力强的决策树；决策树的生成是一个递归的“分而治之”过程——从当前样本集里挑一个最优属性来划分，再对每个分支得到的样本子集递归处理

有三种情形会导致递归返回：

当前结点包含的样本全属于同一类别，无需划分
当前属性集为空，或所有样本在所有属性上取值相同，无法划分
当前结点包含的样本集合为空，不能划分

情形 (2) 的处理是把当前结点标记为叶结点、类别取为该结点所含样本最多的类别，这实际上是在利用当前结点的后验分布；情形 (3) 同样标记为叶结点，但类别取为其父结点所含样本最多的类别，因为此时结点里没有样本可用，只能把父结点的样本分布当作当前结点的先验分布。

划分选择

决策树学习的关键是如何选择最优划分属性。随着划分不断进行，我们希望分支结点包含的样本尽可能属于同一类别，即结点的“纯度”越来越高，于是需要一种能度量纯度、并能比较不同属性划分效果的指标

信息熵是度量样本集合纯度最常用的指标。设当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$（$k = 1, 2, \dots, |\mathcal{Y}|$）：

$$
\mathrm{Ent}(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k
$$

（约定若 $p = 0$ 则 $p\log_2 p = 0$）$\mathrm{Ent}(D)$ 的值越小，$D$ 的纯度越高，它的最小值是 $0$、最大值是 $\log_2|\mathcal{Y}|$。

假设某事件概率为 $p$ ，其信息量为 $I(p)$，则应满足：

$p$ 越小 $I(p)$ 越大；通俗理解就是事件更难被预测，一旦发生，消除的不确定性更多

对于独立事件 $p1$ 和 $p2$ 满足 $I(p1p2) = I(p1) + I(p2)$

则一个很自然的函数就是 $I(p) = -\log_2(p)$

那么以上信息熵公式就是计算 $D$ 中的平均信息量：熵越小，说明样本越纯、越可预测；熵越大，说明类别越混杂、越难猜

假定离散属性 $a$ 有 $V$ 个可能取值 ${a^1, a^2, \dots, a^V}$，用 $a$ 划分就会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含 $D$ 中所有在 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$。用信息熵来度量纯度、并考虑到各分支结点样本数不同（样本越多影响越大，故按 $\frac{|D^v|}{|D|}$ 加权），就得到用属性 $a$ 划分所获得的“信息增益”：
$$
\mathrm{Gain}(D, a) = \mathrm{Ent}(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)
$$

前一项是划分前信息熵，后一项是划分后各子集的信息熵按样本占比的加权平均，两者之差就是不确定性下降的幅度

信息增益越大，说明用 $a$ 划分带来的“纯度提升”越大，因此可选 $a^* = \arg\max_{a \in A}\mathrm{Gain}(D,a)$ 作为划分属性；这就是ID3决策树学习算法

不过每个子集 $D^{v}$ 越小，子集内部就越纯，$\mathrm{Ent}(D^v)$ 就越小；也就是可能产生过度分支、泛化能力很弱的决策树

为减少这种偏好的不利影响，C4.5决策树算法改用“增益率”：
$$
\mathrm{Gain_ratio}(D, a) = \frac{\mathrm{Gain}(D, a)}{IV(a)}, \qquad
IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
$$

其中 $IV(a)$ 称为属性 $a$ 的“固有值”，$a$ 的可能取值数目越多（$V$ 越大），$IV(a)$ 通常越大，于是惩罚了过多的分支

但增益率反过来又会偏好可取值数目较少的属性，所以 C4.5 的做法是一个折中的启发式：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

CART 决策树则使用“基尼指数”：

$$
\mathrm{Gini}(D) = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k’ \neq k}p_kp_{k’} = 1 - \sum_{k=1}^{|\mathcal{Y}|}p_k^2
$$

$\mathrm{Gini}(D)$ 显然就是从 $D$ 中随机抽取两个样本、其类别标记不一致的概率，因此越小纯度越高；据此，基尼指数定义为：
$$
\mathrm{Gini_index}(D, a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Gini}(D^v)
$$
在候选属性集合 $A$ 中选择使划分后基尼指数最小者，即 $a^* = \arg\min_{a\in A}\mathrm{Gini_index}(D,a)$

信息熵与基尼指数只是纯度的两种度量，二者实际差别不大

剪枝处理

剪枝是决策树对付过拟合的主要手段

为了尽可能正确分类训练样本，结点划分会不断重复，有时分支过多，以致把训练集自身的一些特点当成所有数据都具有的一般性质。剪枝就是主动去掉一些分支来降低过拟合风险

预剪枝是在决策树生成过程中，对每个结点在划分前先进行估计：若当前结点的划分不能带来决策树泛化性能提升，就停止划分并将当前结点标记为叶结点

但预剪枝基于“贪心”本质，有些分支的当前划分虽不能提升泛化性能、甚至可能暂时下降，在其基础上进行的后续划分却可能显著提高性能，预剪枝禁止了这些分支展开，从而带来欠拟合的风险

后剪枝是先由训练集生成一棵完整的决策树，然后自底向上地考察非叶结点：若将该结点领衔的子树替换为叶结点能带来泛化性能提升，就把该子树替换成叶结点

后剪枝通常比预剪枝保留了更多的分支，一般情形下欠拟合风险很小、泛化性能往往优于预剪枝；代价是它要在生成完整决策树之后、自底向上地对所有非叶结点逐一考察，训练时间开销比未剪枝决策树和预剪枝决策树都要大得多

连续属性值的处理

连续属性的可取值数量不是有限可取的，不能直接根据取值来划分结点，因此需要先做离散化，最简单的策略是二分法：

给定样本集 $D$ 和连续属性 $a$，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，从小到大排序为 ${a^1, a^2, \dots, a^n}$。对相邻取值 $a^i$ 与 $a^{i+1}$ 来说，划分点 $t$ 在区间 $[a^i, a^{i+1})$ 中取任意值所产生的划分结果都相同，因此可只考察包含 $n-1$ 个元素的中位点集合：

$$
T_a = \left{\frac{a^i + a^{i+1}}{2} \mid 1 \le i \le n-1\right}
$$

然后像离散属性值一样考察这些划分点，选取使信息增益最大的划分点：
$$
\mathrm{Gain}(D,a) = \max_{t\in T_a}\mathrm{Gain}(D,a,t)
$$
其中
$$
\mathrm{Gain}(D,a,t) = \mathrm{Ent}(D) - \sum_{\lambda \in {-,+}}\frac{|D_t^\lambda|}{|D|}\mathrm{Ent}(D_t^\lambda)
$$
$D_t^-$ 与 $D_t^+$ 分别是属性 $a$ 取值不大于 $t$、大于 $t$ 的样本子集。注意与离散属性不同：若当前结点划分属性为连续属性，该属性还可在其后代结点中继续作为划分属性使用（因为它还可以有别的划分点）

缺失属性值的处理

现实任务中样本往往在某些属性上没有取值，这带来两个问题：如何在属性值缺失的情况下选择划分属性，以及给定划分属性后如何划分取值缺失的样本。

解决办法是给每个样本赋予一个权重 $w_{\vec{x}}$（根结点中各样本权重初始化为 $1$），并只依据在属性 $a$ 上没有缺失值的样本来判断 $a$ 的优劣：令 $\tilde{D}$ 表示 $D$ 中在 $a$ 上无缺失值的样本子集，$\tilde{D}^v$ 表示 $\tilde{D}$ 中在 $a$ 上取值为 $a^v$ 的样本子集，$\tilde{D}k$ 表示 $\tilde{D}$ 中属于第 $k$ 类的样本子集，再定义
$$
\rho = \frac{\sum{\vec{x}\in\tilde{D}}w_{\vec{x}}}{\sum_{\vec{x}\in D}w_{\vec{x}}}, \qquad
\tilde{p}k = \frac{\sum{\vec{x}\in\tilde{D}k}w{\vec{x}}}{\sum_{\vec{x}\in\tilde{D}}w_{\vec{x}}}, \qquad
\tilde{r}v = \frac{\sum{\vec{x}\in\tilde{D}^v}w_{\vec{x}}}{\sum_{\vec{x}\in\tilde{D}}w_{\vec{x}}}
$$

三者分别是无缺失样本所占的比例、无缺失样本中第 $k$ 类所占的比例、无缺失样本中在 $a$ 上取值为 $a^v$ 的样本所占的比例。把信息增益的公式改成

$$
\mathrm{Gain}(D, a) = \rho \times \mathrm{Gain}(\tilde{D}, a) = \rho \times \left(\mathrm{Ent}(\tilde{D}) - \sum_{v=1}^{V}\tilde{r}_v,\mathrm{Ent}(\tilde{D}^v)\right)
$$

其中
$$
\mathrm{Ent}(\tilde{D}) = -\sum_{k=1}^{|\mathcal{Y}|} \tilde{p}_k \log_2 \tilde{p}k
$$
即可用它来选择划分属性，通俗来看就是先排除存在缺失值的样本的干扰来计算信息增益，然后乘以无缺样本和全体样本的比例系数以合理化其在全体样本中的影响。至于如何划分样本：若样本 $\vec{x}$ 在划分属性 $a$ 上的取值已知，就把它划入与其取值对应的子结点，权值保持为 $w{\vec{x}}$；若取值未知，就把 $\vec{x}$ 同时划入所有子结点，并在与属性值 $a^v$ 对应的子结点中把权值调整为 $\tilde{r}v \cdot w{\vec{x}}$ ：直观地说，就是让同一个样本以不同的概率划入到不同的子结点中去。

多变量决策树

姑且了解一下其思想

把每个属性视为坐标空间中的一个坐标轴，$d$ 个属性描述的样本就对应 $d$ 维空间中的一个数据点，对样本分类就意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即分类边界由若干个与坐标轴平行的分段组成

这种边界的好处是每一段划分都直接对应某个属性的取值，学习结果有较好的可解释性；但当真实分类边界比较复杂时，必须用很多段划分才能获得较好的近似，此时的决策树会相当复杂，又因要进行大量属性测试，预测时间开销也很大

若能使用斜的划分边界，决策树模型将大为简化。“多变量决策树”（亦称“斜决策树”）就是能实现这种斜划分、甚至更复杂划分的决策树：它的非叶结点不再是仅对某个属性进行测试，而是对属性的线性组合进行测试，即每个非叶结点是一个形如

$$
\sum_{i=1}^{d} w_i x_i + b = 0
$$

的线性分类器，其中 $w_i$ 是属性 $x_i$ 的权重，$w_i$ 与 $b$ 可在该结点所含的样本集和属性集上学得

于是与传统的“单变量决策树”不同，多变量决策树的学习过程不再是为每个非叶结点寻找一个最优划分属性，而是试图为该结点建立一个合适的线性分类器（例如 OC1 先贪心地寻找各属性的最优权值，再对分类边界做随机扰动以图更好）