包含北航机器学习考试的大部分考点

一、概述

1. 研究的问题：分类、聚类、回归、降维
2. 学习方式：监督学习、无监督学习
3. 监督学习根据输出变量类型主要分为分类与回归两类
4. 监督学习目标：最小化均方误差或错误率，常用于回归、分类任务

• 均方误差：$\frac{1}{N}\sum_{i=1}^N(y_n-g(x_n))^2$
• 错误率：$\frac{1}{N}\sum_{i=1}^N\mathbb{I}(y_n\neq g(x_n))$

1. 模型的泛化误差为偏差、方差和噪声之和：$E(f:D) =noise^2+bias^2(x) + var(x)$

• 偏差：度量学习算法f在训练集D上的预测结果与真实结果y的偏离程度，刻画学习算法本身对于训练集的拟合性能
• $bias^2(x) = (\bar{f}(x) -y)^2$
• 方差 ：度量同样大小的差异训练集导致模型性能的变化，刻画训练数据扰动造成的影响
• $var(x) = E_D[(f(x;D)-\bar{f}(x))^2]$
• 其中$\bar{f}(x) = E_D[f(x;D)]$，是模型对应预测结果的期望

1. 过拟合和欠拟合

• 欠拟合：模型复杂度低，不足以拟合训练数据，无法表征所有的相关类别特性，在训练集和测试集上误差都很大
  • 高偏差、低方差
  • 训练误差高、测试误差高
• 过拟合：模型复杂度高，过度拟合训练数据，训练集上误差小而测试集上误差大
  • 高方差、低偏差
  • 训练误差低、测试误差高

1. 除了增加训练样本的数量，还可以采用正则化方法缓解过拟合，对较大值的系数进行惩罚

• $E(w) = \frac{1}{2}\sum_{n=1}^N{y(x_n,w)-t_n}^2+\frac{\lambda}{2}

  w

  ^2$

二、数学基础

1. 贝叶斯公式：$P(B_i

   A) = \frac{P(A

   B_i)P(B_i)}{\sum_{j=1}^n P(B_j)P(A

   B_j)}$

• 当n=1时，$P(B

  A) = \frac{P(A

  B)P(B)}{P(A)}$，$P(B

  A)$为后验概率，$P(B)$为先验概率，$P(A

  B)$为似然概率，$P(A)$为证据因子

1. 概率密度函数估计

• 参数化方法：已知概率密度函数的形式，只是其中几个参数未知（可以写成某些参数的函数，如典型分布），依据样本估计这些未知参数的值
  • 最大似然估计
  • 贝叶斯估计
• 非参数化方法：概率密度函数的形式非已知（不能写成某些参数的函数，非典型分布），直接依据样本估计总体分布
  • Parzen窗法
  • $k_n$近邻法

1. 最大似然估计：最大化 $l(\theta) = \prod_{i=1}^np(x_i:\theta)$

• 无偏性、有效性、一致性

1. 非参数估计的基本方法：直方图方法

• 基本思路：要估计某点的密度，可把所有样本在该点的“贡献”相加近似作为其概率密度，进而得到p(x)
• 把 x 的每个分量分成 k 个等间隔小窗，统计落入各个小舱内的样本数 $q_i$，各小舱概率密度为 $\frac{q_i}{NV}$

1. Parzen 窗法：使区域体积序列 $V_N$ 以 N 的某个函数的关系不断缩小，同时限制 $k_N$ 和 $\frac{k_N}{N}$，有限的N、V 选择很敏感

• $p(x) = \frac{1}{N}\sum_{i=1}^Nk(x,x_i)$
• $k(x,x_i)$反映 $x_i$ 对 p(x) 的贡献，实现小区域选择
• 窗宽选择原则：样本数多则选小些；样本数少则选大些
• 问题：核和体积固定，若样本分布不均匀，则不能得到满意估计
• 解决办法：不使用固定区域，而是固定落在区域内的样本数；即通过控制小区域内的样本数 $k_n$ 来确定小区域大小

1. $k_n$近邻法：使落入区域样本数 $k_N$ 为 N 的某个函数，选择 $V_N$ 使区域包含 x 的 $k_N$ 个近邻，动态变化 V 的取值

三、模型评估和选择

1. 误差：算法模型的实际预测输出与样本的真实输出之间的差异

• 训练误差/经验误差：学习器在训练集上的误差
• 测试误差：学习器在新（测试）样本上的误差

1. 数据集划分

• 保持/留出法：给定数据随机地划分到两个独立的集合：训练集和测试集，使用训练集导出模型，用测试集来估计泛化误差
  • 优点 ：简单
  • 缺点 ：受数据划分影响大
• 随机子抽样：保持方法的一种变形随机地选择训练集和测试集将保持方法重复 k 次，总准确率估计取每次迭代准确率的平均值
  • 问题：每个样本用于训练的次数不同
• k 折交叉验证：初始数据被划分成 k 个大小相似、互不相交的子集/折。训练和测试 k 次；在第 i 次迭代，第 i 折用作测试集，其余的子集都用于训练学习，取 k 次测试结果的均值
  • 每个样本用于训练的次数相同并且用于检验一次
• 留一法：是 k 折交叉确认的特殊情况，其中 k 设置为初始样本数。用 k -1 个样本作为训练集，每次只给检验集留出一个样本，由此设计一个模型。从 k 个样本中选 k-1 个样本有 k 中选择，所以可用不同的大小为 k -1 训练样本重复进行 k 次
  • 优点 ：训练集比数据集只少一个样本 比较准确

  • 缺点 ：由于要设计 k=

    D

    个不同的模型并对其进行比较，当

    D

    较大时，这种方法计算量很大

• 自助法：与留一法相同是随机采样，不同在于自助法从初始样本 D 有放回 地均匀抽样；即每当选中一个样本，它等可能地被再次选中并再次添加到训练集中；采样

  D

  次后 即可获取大小为

  D

  的训练样本集；没有进入训练集的数据样本形成测试集

  • 样本在

    D

    次采样中始终不被采到的概率为 $\frac{1}{e}$，将未被采到的样本作为测试集

  • 优势：可产生多个不同训练样本集；对于小数据集，自助法效果胜过K折交叉验证；能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处
  • 缺点：改变了数据集分布，会引入估计偏差

方法	适用场景	方差	偏差
留出法	数据量较大	训练、测试集的分布不同时，会导致模型方差较高	当数据量不足时，会导致模型偏差较高
自助法	数据量较小	模型方差较低	改变了初始分布，会导致模型偏差较高
交叉验证法	数据量较小	模型方差较低	模型偏差较低

1. 错误率和准确率

• 优点：理解直观、计算简单
• 问题：
  • 数据类别不均衡时，占比大类别成为影响准确率的最主要因素
  • 仅能评估是否正确分类，无法提供更详细评估

1. 混淆矩阵：用来作为分类规则特征的表示，它包括了每一类的样本个数，包括正确的和错误的分类

• 主对角线给出了每一类正确分类的样本的个数，非对角线上的元素则表示未被正确分类的样本个数

1. 性能度量

真实类别\预测结果	正例P	负例P
正例P	真正例TP	假负例FN
负例P	假正例FP	真负例TN

• 准确率/识别率：评估分类器正确识别正、负样本的能力
  • $ accuracy = \frac{TP + TN}{P + N} $
• 错误率：评估分类器错误识别正、负样本的能力
  • $ ErrorRate = \frac{FP + FN}{P + N} $
• 真阳性率 (TPR)/敏感性：评估分类器正确识别正样本的能力
  • $ SN = \frac{TP}{P} = \frac{TP}{TP + FN} $
• 真阴性率 (TNR)/特异性：评估分类器正确识别负样本的能力
  • $ SP = \frac{TN}{N} = \frac{TN}{TN + FP} $
• 精度/查准率：评估预测正样本中的真正样本
  • $ precision = \frac{TP}{TP + FP} $
• 召回率/查全率/敏感性：评估分类器正确识别正样本的能力
  • $ recall = \frac{TP}{TP + FN} $
• $F_1$度量：查准率和查全率的调和平均
  • $F_1 = \frac{2 \times precision \times recall}{precision + recall}$
• $F_{\beta}$度量：利用参数$\beta$控制查全率对查准率的相对重要性
  • $F_{\beta} = \frac{(1 + \beta^2) \times precision \times recall}{\beta^2 \times precision + recall}$
  • $\beta = 1$时，退化为$F_1$
  • $\beta > 1$时，查全率影响更大，模型更倾向于减少漏报，适合查全率更重要的场景，如疾病筛查
  • $\beta < 1$时，查准率影响更大，模型更倾向于减少误报，适合查准率更重要的场景，如垃圾邮件过滤
• 查准率和查全率互相矛盾：查准率高则查全率低；反之亦然

真实结果\预测结果	正例	反例
正例	0	CostFN
反例	CostFP	0

$E(f;D) = \frac{1}{d} \left( \sum_{x_i \in D^+} \mathbb{I}(f(x_i) \neq y_i) \times \text{cost}{FN} + \sum{x_i \in D^-} \mathbb{I}(f(x_i) \neq y_i) \times \text{cost}_{FP} \right)$

四、贝叶斯决策

1. 最小错误率贝叶斯决策：根据贝叶斯公式计算后验概率，基于最大后验概率进行判决

• $x \in w_k \text{ iff } k = \arg \max_i {P(w_i

  X)}$

• $P(w_i

  X) = \frac{P(X

  w_i) P(w_i)}{\sum_{j = 1}^{c} P(X

  w_j) P(w_j)}$

1. 最小风险贝叶斯决策：

• 利用后验概率与损失函数，计算条件风险：$R(\alpha_i

  x) = \sum_{j = 1}^{c} \lambda(\alpha_i, \omega_j)P(\omega_j

  x), i = 1, 2, \ldots, a$

• 决策：$R(\alpha_k

  x) = \min_{i = 1, 2, \ldots, a} R(\alpha_i

  x)$

• 最小错误率贝叶斯决策就是在0-1损失函数条件下的最小风险贝叶斯决策

1. 朴素贝叶斯决策

• 类条件概率$P(x

  w_i ) $是所有属性上的联合概率，难以从有限的训练样本直接估计得到

• 属性条件独立性假设：对于已知类别，假设所有属性相互独立；即假设各属性独立地对分类结果发生影响
• 好处：降低样本集大小需求；降低复杂度
• 贝叶斯公式 + 属性独立性条件

  • $P(w

    x) = \frac{P(w)P(x

    w)}{P(x)} = \frac{P(w)}{P(x)} \prod_{i = 1}^{d} P(x_i

    w)$

• 朴素贝叶斯决策

  • $w_k = \arg \max_j P(w_j) \prod_{i = 1}^{d} P(x_i

    w_j)$

1. 贝叶斯估计

• 把待估计参数看做是符合某种先验概率分布的随机变量
• 对样本进行观测的过程，就是把先验概率密度转化为后验概率密度，从而利用样本信息修正参数的初始估计值

五、线性回归

1. 损失函数

• $J(w) = \frac{1}{2} \sum_{i = 1}^{N} (f(x_i) - y_i)^2$
• $\hat{w} = \arg \min_w \left[ \frac{1}{2} \sum_{i = 1}^{N} (f(x_i) - y_i)^2 \right]$

1. 标准方程组

• $J(w) = \frac{1}{2} \sum_{i = 1}^{N} (w^Tx_i - y_i)^2 = \frac{1}{2}(Xw-y)^T(Xw-y)$
• $\frac{\partial }{\partial w}J(w) = X^T(Xw-y) = 0$
• $\hat{w} = (X^TX)^{-1}X^Ty$

1. 梯度下降法：梯度下降法是一个最优化算法，是求解无约束优化问题最简单和最基础的方法之一，以负梯度方向为搜索方向，越接近目标值，步长越小，前进越慢

• 给定初始值$w^0$
• 更新$w$使得$J(w)$越来越小
  • $w_j^t = w_j^{t - 1}-\alpha\frac{\partial}{\partial w_j}J(w)$
  • $\frac{\partial}{\partial w_j}J(w)=\sum_{i = 1}^{N}(f(x_i)-y_i)\cdot x_{i,j}$
  • $f(x_i)=[w^{t - 1}]^T x_i$
• $\alpha$为学习率或更新步长

1. 梯度下降方法：

• 批处理梯度下降：在梯度下降方法中，每次更新都利用所有数据，对于凸函数，可以达到全局最优，在大样本条件下，批处理梯度下降的迭代速度很慢
• 随机梯度下降：每次只用一个样本，收敛速度较快，对大样本数据较有效，对于更复杂的优化目标，可以跳出局部最优解

方法	特点	适用情况
梯度下降法	需要选择α 需要迭代多次 需要数据归一化 样本量非常大时也适用	样本量较大时
标准方程组	不需要选择α 不需要迭代多次 无需数据归一化 样本量大时不适用（需要计算(XXT)-1）	样本量较小时

1. 线性判别函数：将分类器设计问题转化为求准则函数极值的问题

• 判别函数g(x)可以看成是特征空间中某点x到超平面H距离的一种代数度量，$r=\frac{g(x)}{

  w

  }$

• 齐次简化：$g(x) = w_0 + \sum_{i = 1}^{d} w_i x_i = \sum_{i = 1}^{d} a_i y_i = a^T y$
• 广义线性判别函数：利用线性函数的简单性解决复杂问题，但维数大大增加，不适用于非凸和多连通区域划分

1. 准则函数：分类器设计的某些要求的函数形式

• Fisher准则/LDA算法：
  • 考虑把d 维空间的样本投影到一条直线上形成一维空间。在一般情况下总可以找到某个方向，使样本在这个方向的直线上的投影分开得最好。Fisher准则就是要解决如何根据实际情况找到这条最好的、最易于分类的投影线的问题
  • 希望投影后在一维Y空间中各类样本尽可能分开，即两类均值之差越大越好；同时希望各类样本内部尽量密集，即类内离散度越小越好
  • $J_F (w) = \frac{(\tilde{m}1 - \tilde{m}_2)^2}{S_1^2 + S_2^2} = \frac{w^T S_b w}{w^T S{w} w}$
  • $w^* = S_w^{-1}(m_1-m_2)$
• 感知机准则
  • $J_P(a)=\sum_{y \in \eta^k}(-a^T y)$
  • $ \nabla J_P(a) = \frac{\partial J_P(a)}{\partial a} = \sum_{y \in \eta^k} (-y) $
  • $ a(k + 1) = a(k) - \rho_k \nabla J = a(k) + \rho_k \nabla \sum_{y \in \eta^k} y $
  • 结果不唯一且在线性不可分情况下不收敛
• 最小二乘准则
  • $a^Ty_n = b_n > 0 \Rightarrow Ya=b$
  • $J_s(a)=|e|^2 = |Ya - b|^2=\sum_{n = 1}^{N}(a^T y_n - b_n)^2$
  • $ a^* = (Y^T Y)^{-1} Y^T b = Y^+ b $
  • b各维度依次取$N_i$个$\frac{N}{N_i}$时，等价于Fisher解，b各维度取1时，以最小均方误差逼近贝叶斯判别函数
  • 要求$Y^TY$非奇异，计算量大同时可能引入较大误差
  • 梯度下降求解：$ \nabla J_s(a) = 2Y^T(Ya - b) $
  • $ a(k + 1) = a(k) - \rho_k Y^T(Ya - b) $
  • 对于异常值非常敏感

六、决策树

1. 基本思想：采用自顶向下的递归方法，构造一棵由结点和有向边组成的树 ，每个叶节点中的实例都属于同一类
2. 分类依据：

• ID3算法：信息增益
  • 以信息熵为度量，用于决策树节点的属性选择，每次优先选取 信息增益最大的属性 ，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为 0。此时，每个叶子节点对应的实例集中的实例属于同一类
  • 熵表示随机变量不确定性的大小，是度量样本集合纯度最常用的一种指标，熵定义了概率密度函数到一个值的映射 p
  • 信息量：具有确定概率事件的信息的定量度量，$I(x)=-\text{log}_2p(x)$
  • 信息熵：事件集合的信息量的平均值，$H(x) = -\sum_ip(x_i)\text{log}_2p(x_i)$

  • 经验信息熵：$H(D) = -\sum_{i=1}^C \frac{

    D_c

    }{

    D

    }\text{log}_2p\frac{

    D_c

    }{

    D

    }$

  • 条件熵：$H(Y

    X )$ 表示在已知随机变量X 的条件下，随机变量Y的不确定性，$H(Y

    X )=-\sum_{i=1}^np_iH(Y

    X=x_i) = H(X,Y)-H(X)$

  • 经验条件熵：$H(D

    a) = \sum_{i=1}^N \frac{

    D^n

    }{

    D

    }H(D^n)$

  • 信息增益：$G(D,a) = H(D) -\sum_{n=1}^N\frac{

    D^n

    }{

    D

    }H(D^n)$

  • 从一类无序、无规则的事物概念中推理出 决策树表示的分类规则，属于有监督学习
  • 信息增益偏好取值多的属性，可能会受噪声或小样本影响，易出现过拟合问题，无法处理连续值的属性，无法处理属性值不完整的训练数据，无法处理不同代价的属性
• C4.5算法：信息增益率
  • $G_{ratio}(D,a) = \frac{G(D,a)}{H(a)}$，缓解信息增益准则对可取值数目较多的属性的偏好
• CART算法：基尼指数

  • $ Gini(D) = 1 - \sum_{c=1}^{C} p_c^2 = 1 - \sum_{c=1}^{C} \left( \frac{

    D_c

    }{

    D

    } \right)^2 $

  • 直观反映了从数据集中随机抽取两个样本，其类别不一致的概率；因此，Gini(D) 越小，则数据集 D 的纯度越高

  • $ Gini(D, a) = \sum_{n=1}^{N} \frac{

    D^n

    }{

    D

    } Gini(D^n) $

  • $ a^* = \arg\min_{a \in A} Gini(D, a) $

1. 剪枝算法

• 预剪枝：决策树生成过程中，对每个节点在划分前进行估计，若划分不能带来决策树泛化性能提升，则停止划分，并将该节点设为叶节点
  • 优势： 预剪枝“剪掉了”很多没必要展开的分支，降低了过拟合的风险，并且显著减少了决策树的训练时间开销和测试时间开销
  • 劣势： 有些分支的当前划分有可能不能提高甚至降低泛化性能，但后续划分有可能提高泛化性能；预剪枝禁止这些后续分支的展开，可能会导致欠拟合
• 后剪枝：先利用训练集生成决策树，自底向上对非叶节点进行考察，若将该叶节点对应子树替换为叶节点能带来泛化性能提升，则将该子树替换为叶节点
  • 优势：测试了所有分支，比预剪枝决策树保留了更多分支，降低了欠拟合的风险，泛化性能一般优于预剪枝决策树
  • 劣势：后剪枝过程在生成完全决策树后在进行，且要自底向上对所有非叶节点逐一评估；因此，决策树的训练时间开销要高于未剪枝决策树和预剪枝决策树

1. 连续值处理：采用二分法进行离散化，分别计算候选划分点集合中每一个划分点对应的信息增益
2. 缺失值处理

• 信息增益计算：仅可利用没有属性缺失的样本，$G(D,a) = \rho G(D, \tilde{a})$
• 含有缺失属性的样本的划分
  • 若样本 x 在属性 a 上的取值已知：将 x 划入与其取值对应的子节点，且样本权值保持为 $w_x$
  • 若样本 x 在属性 a 上的取值未知：将 x 划入所有子节点，且其在与属性值对应的子节点中的权值根据属性 a 上已知样本的比例调整为 $ \tilde{r}_n \cdot w_x $

1. 不同代价属性的处理

• $G_{Cost}(D, a) = \frac{G(D, a)}{Cost(a)}$
• $G_{Cost}(D, a) = \frac{2^{G(D, a)} - 1}{(Cost(a) + 1)^w}$

七、支持向量机

1. 最优分类面：要求分类线不但能将两类正确分开，且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面，并且使训练集中的点距离分类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域最大
2. 支持向量机：

• 样本集任意一点到分类面的距离 $\frac{t_n(w^Tx_n+b)}{

  w

  }$，且$t_ny(x_n)>0$

• 优化w和b使空白区域最大，$\arg\max_{w,b} \left{ \frac{1}{|w|} \min_n \left[ t_n (w^T x_n + b) \right] \right}$
• $w\rightarrow kw，b\rightarrow kb$，对于离超平面最近的点$t_n(w^Tx_n+b) = 1$，那么所有点大于等于1

• 原问题转化为二次规划问题 $\min_{w,b} \frac{1}{2}

  w

  ^2 \space \space\text{s.t. } t_n(w^T x_n + b) \geq 1$

• 使用拉格朗日乘子法将上述二次规划问题转化为等价的对偶问题进行简化求解：$L(w, b, a) = \frac{1}{2} |w|^2 - \sum_{n=1}^N a_n \left{ t_n (w^T x_n + b) - 1 \right}$
• 拉格朗日求极值：$\max_{a} \sum_{n=1}^N a_n - \frac{1}{2} (\sum_{n=1}^N a_nt_nx_n)^2 $
• $\text{s.t. } a_n \geq 0,\ n=1,\dots,N,\ \sum_{n=1}^N a_n t_n = 0$
• 得到超平面为：$y(x) = \sum_{n=1}^N a_n t_n x_n^T x + b,\ b = \frac{1}{N_S} \sum_{n \in S} \left( t_n - \sum_{m \in S} a_m t_m x_n^T x_m \right)$
• KKT条件
  • 拉格朗日梯度条件：梯度为0
  • 互补松弛条件：最优解处，若某个不等式约束未起作用，则其对应的乘子为0；若乘子大于0，则约束必须严格起作用
  • 对偶可行性：不等式约束对应的拉格朗日乘子非负
  • 原问题可行性：约束条件本身在最优解处成立
• 支持向量：$t_n(w^Tx+b)=1, a_n>0$
• 非支持向量：$t_n(w^Tx+b)>1，a_n=0$
• 只有支持向量决定分类超平面， 非支持向量与其无关
• 由于样本中不可避免地存在噪声和离群点，可能导致硬间隔求解的最优分类面泛化性能差

1. 软间隔：

• $t_ny(x_n)\ge 1-\xi_n$

• 优化：$\min_{w,b} \frac{1}{2}

  w

  ^2 + C\sum_{n=1}^N\xi_n \space \space \text{s.t. } t_n(w^T x_n + b) \geq 1-\xi_n, \xi_n\geq 0$

• 对偶问题：$ \max_{a} \sum_{n=1}^N a_n - \frac{1}{2} (\sum_{n=1}^N a_nt_nx_n)^2 $
• $\text{s.t. } 0 \leq a_n \leq C,\ n=1,\dots,N,\ \sum_{n=1}^N a_n t_n = 0$
• 支持向量：$t_n(w^Tx+b)-1+\xi_n=0, a_n>0, \mu_n\xi_n=0$
• 非支持向量：$a_n=0$，样本$x_n$不受约束
• $a_n<C, \mu_n>0,\xi_n=0$样本$x_n$在最大分隔边界上
• $a_n=C, \mu_n=0$，$u_n$不再约束$\xi_n$
  • $\xi_n\le1$样本$x_n$在最大分隔内且未被错分
  • $\xi_n>1$样本$x_n$被错分

	软间隔	硬间隔
允许错分	允许对噪声/离群点有一定错分	不允许错分
间隔与泛化	最大间隔更大，泛化性更好	最大间隔小，泛化性差
优化目标	含惩罚项（超参 $ C $ 及求和项）	无惩罚项
求解难度	含超参，求解较复杂	求解过程较简单
综合特点	权衡泛化性和准确性的综合选择	准确性高，泛化性差

1. 非线性支持向量机：把样本x映射到某个高维特征空间，并在其中使用线性分类器，利用一个固定的非线性映射将数据映射到特征空间学习的线性分类器等价于基于原始数据学习的非线性分类器
2. 核函数：在特征空间中直接计算数据映射后的内积，就像在原始输入数据的函数中计算一样，大大简化了计算过程，直接在原来的低维空间中进行计算不需要显式地写出映射后的结果，避免了先映射到高维空间中然后再根据内积的公式进行计算
3. 序列最小优化算法

• 支持向量机的学习问题可以形式化为求解具有全局最优解的凸二次规划问题。许多方法可以用于求解这一问题，但当训练样本容量很大时，这些算法往往效率较低，以致无法使用。
• 思想：如果所有变量都满足此优化问题的KKT条件，那么这个问题的解就得到了
• 特点：不断地将原二次规划问题分解为只有两个变量的二次规划问题，并对子问题进行解析求解，直到所有变量都满足KKT条件为止。因为子问题解析解存在，所以每次计算子问题都很快

八、神经网络

1. 逻辑回归：逻辑回归是概率型非线性回归 ，但其本质是线性回归，只是在特征到结果的映射中加入了一层函数映射，即先把特征线性求和，再使用 sigmoid 函数预测

• 表达式$p=\frac{1}{1+e^{-w^Tx}}$，将p视为样本x作为正例的可能性​，$\text{ln}\frac{p}{1-p}=w^Tx$，是在用线性回归模型的预测结果去逼近真实标记的对数几率 ，故逻辑回归又称对数几率回归
• $\sigma(-a)=1-\sigma(a), a=\text{ln}\frac{\sigma}{1-\sigma},\frac{d\sigma}{da}=\sigma(1-\sigma)$

• 将后验概率表示为作用于变量 x 的线性函数中的 Logistic Sigmoid：$p(C_1

  x)=y(x)=\sigma(w^Tx),p(C_2

  x)= 1-p(C_1

  x)$

• 似然函数 $p(t

  w) = \prod_{i=1}^N y_n^{t_n}(1-y_n)^{1-t_n}, y_n=p(C_1

  x_n)$

• 误差函数：交叉熵损失函数 $E(w)=-\text{ln}p(t

  w)=-\sum_{i=1}^N{t_n\text{ln}y_n+(1-t_n)\text{ln}(1-y_n)}$

• $\nabla E(w)=\sum_{i=1}^N(y_n-t_n)x_n=0$

1. 生成式模型和判别式模型

维度	生成式模型	判别式模型
定义核心	先建模类条件密度 $ p(x	C_k) $ / 联合分布 $ p(x,C_k) $，再通过贝叶斯定理推导后验概率 $ p(C_k	x) $	直接对后验概率 $ p(C_k	x) $ 建模
优点	信息丰富；单类问题灵活性强；支持增量学习；可合成缺失数据	类间差异清晰；分类边界灵活；学习过程简单；分类性能较优
缺点	学习过程复杂；为匹配数据分布，可能牺牲分类性能	无法反映数据特性；需全量数据训练，不支持增量学习
相互关系	生成式模型可推导得到判别式模型	判别式模型无法反推出生成式模型

1. 反向传播算法：从后向前反向逐层传播输出层的误差以间接计算隐层的误差。算法可以分为两个阶段：

• 前馈（正向过程）：从输入层经隐层逐层正向计算各单元的输出
• 学习（反向过程）：由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权值
• 局限性
  • 用梯度法求非线性函数极值，有可能陷入局部极小点，不能收敛到全局极小点
  • 如果权值初值都相同，隐层各单元无差异，运算不能正常进行。通常用较小随机数作为权值初值。初值对收敛有影响，当计算不收敛时，可以改变初始值调试

1. 其他神经网络

• 径向基函数神经网络：只有一个隐层，隐层单元采用径向基函数作为其输出函数，输入层到隐层之间的权值均固定为 1 ；输出节点为线性求和单元，隐层到输出节点之间的权值可调，因此，输出为隐层的加权求和
• Hopfield网络：是一种反馈网络。反馈网络具有一般非线性系统的许多性质，如稳定性问题等，在某些情况下还有随机性、不可预测性。因此它比前馈网络的内容复杂，具有权值对称、无自反馈的特点
• 自适应共振理论神经网络：通过反复将输入学习模式由输入向输出层自下而上短时记忆和由输出向输入层自上而下长期记忆和比较来实现。当记忆和比较达到共振时，输出矢量可正确反映输入学习模式的分类，且网络原有记忆不受影响
  • 能将任意维输入模式在输出层映射成一或二维离散图形，并保持拓扑结构不变
  • 在输出层，获胜神经元邻域内的神经元在不同程度上都得到兴奋，而在邻域外的神经元都被抑制
  • 邻域可为任意形状，但一般是对称的。邻域是时间的函数，随时间增大而减小，最后可能剩下一个或一组神经元。最终得到的区域反映了一类输入模式的属性

九、深度学习

1. 卷积神经网络：仿照生物的视觉感知机制，是一类包含卷积及计算、具有深度结构的前馈神经网络，是深度学习的代表方法之一

• 局部卷积操作：滑动窗口，边缘填充
• 共享权重参数：不同位置的局部窗口使用相同的卷积核权重参数
• 多卷积核运算：为了充分提取特征，可以使用多个卷积核，特征图叠加形成通道
• 池化处理：对不同空间位置的特征值进行聚合统计
  • 降维
  • 克服过拟合
  • 在图像识别领域，池化可提供平移和旋转不变性
• 多层处理：单层卷积及池化仅学到局部特征。层数越多，所学特征越全局。通过多层处理，低级特征可以形成更高级特征
  • 由卷积层、子采样层、全连接层交叉堆叠而成，趋向于小卷积、大深度
  • 线性整流激活函数

1. 深度神经网络训练：

• 每个训练轮次使用单个样本的梯度进行参数更新，叫随机梯度下降
  • 引起梯度震荡、相似样本，冗余计算
• 使用所有样本的梯度和进行参数更新，叫批梯度下降
  • 计算量大、易陷入局部极小值
• 使用一部分样本梯度和进行参数更新，叫小批量梯度下降
  • 计算小批量数据的梯度更加高效、收敛更稳定、样本使用更灵活
  • 目前最常用的策略。在使用中，这种方法通常被称为SGD

1. 学习率调节：

• 自适应学习率：线性衰减、指数衰减
• Adagrad：对稀疏参数进行大幅更新和对频繁参数进行小幅更新、适合处理稀疏数据
• RMSprop：用滑动平均代替全局累积梯度平方和，避免学习率过早衰减
• Adadelta：使用前一次的梯度开方代替初始学习率
• 动量SGD：引入动量momentum，抑制梯度的震荡
• Nesterov梯度：具有一定的预测性，在计算当前梯度前，先按历史动量更新一次参数
• Adam：最常用的方法

1. 训练问题

• 梯度消失：随着隐含层增加，反向传播传递给较低层的信息会减少。实际上，由于信息向前反馈，不同层间的梯度开始消失，对网络中权重的影响也会变小
• 过度拟合：模型非常复杂。会导致对训练数据有非常好的识别效果，而对真实样本的识别效果非常差

1. 如何有效训练神经网络

• 线性整流激活函数：避免了梯度爆炸和梯度消失问题；简化计算过程；训练稀疏网络
• Dropout 机制：随机关闭一些神经元，避免深度神经网络过拟合，降低模型参数，强制使网络有鲁棒的表示
• Batch Normalization：对激活后的输出归一化，可以选择较大的学习率，可以减少或不使用 dropout，缓解梯度消失、爆炸问题
• 残差神经网络：在输入和输出之间加入“捷径”连接，构造更深的神经网络，易收敛，不退化，Block 内部取消 pooling，用更小的卷积核

1. 循环神经网络

• 既能处理序列输入，也能得到序列输出
• RNN由输入，隐状态、及输出三部分组成
• 当t与k间隔较远时，梯度会很快的变的很大或很小

1. LSTM

• 遗忘门选择哪些信息应该被遗忘
• Cell不断更新新状态并输出

1. Transformer：

• 传统 CNN 和 RNN 存在的问题：
  • 长距离依赖问题：RNN 随着序列长度的增加，模型很难捕捉到序列开始和结束之间的依赖关系
  • 并行计算问题：RNN 必须按序列顺序逐个处理元素，这限制了训练过程的并行化
  • 上下文建模问题：传统模型如 RNN 和 CNN 通常具有固定的窗口或范围来捕捉上下文信息
• Transformer 网络
  • 摒弃循环神经网络：完全依赖注意力机制
  • 能够更加高效灵活的建模序列数据
  • 查询 ( Query)：查询项，自主提示，即主观意识的特征向量
  • 键 ( Key )：被比对项，非自主提示，即物体的突出特征向量
  • 值 ( Value )：代表物体本身的特征向量，通常和 Key 成对出现
  • 步骤1：查询(query)与键(key)计算注意力评分，通过softmax函数得到不同的显著性值
  • 步骤2：根据不同的注意力权重，对值(value)进行加权求和
• 自注意力机制：
  • 注意力机制的变体
  • 减少对外部信息的依赖，更擅长捕捉数据或特征的 内部相关性
  • 注意力机制的 Query 和 Key 是 不同来源的，自注意机制的 Query 和 Key 来自同一组的元素
• 编码器结构
  • 自注意力模块：类似于拆解对照表
  • 前馈网络：根据权重完成一次变形
    • 归一化：稳定反向传播梯度
    • 残差链接：避免梯度消失
    • FFN ：已有信息之间的并行融合，总结高级语义特征
• 编解码注意力机制
  • Query和Key来自Encoder输出，Value来自Decoder的上一层
• 多头注意力机制
  • 将查询(Query)、键(Key)和值(Value)通过不同的注意力结构
  • 不同注意力头关注的重点不同
• 输入编码：将输入 Token 序列转为特征序列
• 位置编码：引入序列相对位置信息
  • 绝对位置编码：对序列的绝对位置（第几个字符）进行差异化编码
  • 相对位置编码：根据词间的相对位置进行编码
  • 旋转位置编码：实现统一的绝对、相对位置编码
• 模型输出层
  • 输出通过线性层映射到词表大小
  • SoftMax 层将向量转化为概率值
• 模型训练：并行训练过程，串行自回归推理

1. 自编码机

• 学习一个输入输出相同的“恒等函数”，无监督
• 只有一个隐含层的时候，其原理相当于主成分分析
• 用于无监督特征提取、图像增强、去噪，数据降维

1. 生成对抗网络

• 生成模型主要步骤：密度估计、采样
• 另一种生成数据的思路： 生成对抗
• 生成网络 从潜在空间中随机采样作为输入，其输出结果需要尽量模仿训练集中的真实样本
• 判别网络 的输入则为真实样本或生成网络的输出，其目的是将生成网络的输出从真实样本中尽可能分辨出来
• 对抗学习
  • 生成网络要尽可能地欺骗判别网络
  • 判别网络将生成网络生成的样本与真实样本中尽可能区分出来
  • 两个网络相互对抗、不断调整参数，最终目的是使判别网络无法判断生成网络的输出结果是否真实

十、聚类

1. 性能度量

• a：真实标签相同（属于同一真实类别），且聚类预测标签也相同（被聚为同一类）的样本对数量
• b：真实标签相同（属于同一真实类别），但聚类预测标签不同（被分成不同类）的样本对数量
• c：真实标签不同（属于不同真实类别），但聚类预测标签相同（被合并为同一类）的样本对数量

• d：真实标签不同（属于不同真实类别），且聚类预测标签也不同（被分成不同类）的样本对数量

• 外部指标：将聚类结果与某个“参考模型”进行比较
  • Jaccard系数：$JC=\frac{a}{a+b+c}$
  • FMI指数：$FMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}}$
  • Rand指数：$RI=\frac{2(a+b)}{m(m-1)}$

• 簇 $ C $ 内样本间的平均距离：$ avg(C) = \frac{2}{

  C

  (

  C

  - 1)} \sum_{1 \leq i \leq j \leq

  C

  } dist(x_i, x_j) $

• 簇 $ C $ 内样本间的最远距离（直径：$ diam(C) = \max_{1 \leq i \leq j \leq

  C

  } dist(x_i, x_j) $

• 簇 $ C_i $ 与簇 $ C_j $ 最近样本间的距离：$ d_{\text{min}}(C_i, C_j) = \min_ dist(x_i, x_j) $

• 簇 $ C_i $ 与簇 $ C_j $ 中心点间的距离（其中 $\mu_k = \frac{1}{

  C_k

  } \sum_{1 \leq i \leq

  C_k

  } x_i $ 为簇 $C_k$ 的中心）：$ d_{\text{cen}}(C_i, C_j) = dist(\mu_i, \mu_j) $

• 内部指标：直接考察聚类结果而不用任何参考模型
  • DB指数：$DBI = \frac{1}{k} \sum_{i=1}^{k} \max_{j \neq i} \left( \frac{avg(C_i) + avg(C_j)}{d_{cen}(\mu_i, \mu_j)} \right)$
  • Dunn指数：$DI = \min_{1 \leq i \leq k} \left{ \min_{j \neq i} \left( \frac{d_{min}(C_i, C_j)}{\max_{1 \leq l \leq k} diam(C_l)} \right) \right}$

1. K均值算法

• 最小化准则函数：$E = \sum_{i=1}^{k} \sum_{x \in C_i} | x - \mu_i |_2^2$ ，其中，$\mu_i$ 是簇 $C_i$ 的均值向量，E刻画簇内样本围绕簇均值的紧密程度，E越小，簇内样本相似度越高
• 初始化选择K个初始聚类中心
• 将每个数据点划分给最近的聚类中心 $\mu_k$, 得到聚类标注 $r_n$
• 最小化准则函数, 重新计算均值向量，作为聚类中心 $\mu_k$，直到均值向量不变

1. K-means改进

• Kmeans++：在选取第 n +1 个中心时： 距离当前 n 个聚类中心越远的点会有更高的概率被选为第n +1 个聚类中心，即聚类中心离得越远越好
• Kernel Kmeans：参照支持向量机中核函数的思想，将所有样本映射到另外一个特征空间中再进行聚类
• 迭代自组织数据分析算法：在 K 均值算法的基础上，增加对聚类结果的“合并和分裂”两个操作，并设定算法运行控制参数的一种聚类算法，通过设定初始参数而引入人的决策，当某两类聚类中心距离小于某阈值时，将它们合并为一类，当某类标准差大于某一阈值或其样本数目超过某阈值时，将其分裂为两类。在某类样本数目少于某阈值时，需将其取消
• 层次聚类算法：试图在不同层次对数据集进行划分，从而形成树形的聚类结构，数据集划分既可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略
  • AGNES算法：自底向上的层次聚类算法。首先，将样本中的每个样本看做一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇的个数

十一、主成分分析

1. 降维：在原始的高维空间中，包含冗余信息和噪声信息，会在实际应用中引入误差，影响准确率；而降维可以提取数据内部的本质结构，减少冗余信息和噪声信息造成的误差，提高应用中的精度
2. 主成分分析：将原有众多具有一定相关性的指标重新组合成一组少量互相无关的综合指标，使得降维后样本的方差尽可能大，使得降维后数据的均方误差尽可能小
3. 最大方差思想

• 使用较少的数据维度保留住较多的原数据特性
• 首先考虑M=1，定义这个空间的投影方向为D维向量$u_1$，设$u_1^Tu_1=1$
• 投影后样本方差表示为$\frac{1}{N}\sum_{i=1}^N{u_1^Tx_n-u_1^T\bar{x}}=u_1^TSu_1$
• 其中原样本方差$S=\frac{1}{N}(x_n-\bar{x})(x_n-\bar{x})^T$
• 目标是最大化投影后样本方差，利用拉格朗日乘子法得$u_1$是S的拓展向量，$u_1$是S最大特征值对应的特征向量时方差取到极大值，称$u_1$为第一主成分
• 考虑更一般性的情况，新空间中数据方差最大的最佳投影方向由协方差矩阵S的M个特征向量定义, 其分别对应M个最大的特征值
• 首先获得方差最大的1维，生成该维的补空间；继续在补空间中获得方差最大的1维，生成新的补空间；依次循环下去得到M维的空间

1. 最小均方误差思想

• 使原数据与降维后的数据（在原空间中的重建）的误差最小
• 定义一组D个正交的D维基向量，且$u_i^Tu_j=\delta_{ij}$，那么$x_n=\sum_{i=1}^D(x_n^Tu_i)u_i$
• 在M维变量生成的空间中对其进行表示，$\tilde{x}n=\sum{i=1}^Mz_{ni}u_i+\sum_{i=M+1}^Db_iu_i$

• 目标最小化 $J=\frac{1}{N}\sum_{i=1}^N

  x_n-\tilde {x_n}

  $

• 求导结果同最大方差思想，对应失真度为$J=\sum_{i=M+1}^D\lambda_i$
• J最小时取D-M个最小的特征值，主子空间对应M个最大特征值

1. 优缺点

• 优点
  • 具有很高普适性，最大程度地保持了原有数据的信息
  • 可对主元的重要性进行排序并根据需要略去部分维数，达到降维从而简化模型或对数据进行压缩的效果
  • 完全无参数限制，在计算过程中不需要人为设定参数或是根据任何经验模型对计算进行干预，最终结果只与数据相关
• 局限性
  • 假设模型是线性的，也就决定了它能进行的主元分析之间的关系也是线性的
  • 假设数据具有较高信噪比，具有最高方差的一维向量被看作是主元，而方差较小的变化被认为是噪声

1. PCA与LDA（Fisher准则）

• PCA追求降维后能够最大化保持数据内在信息，并通过衡量在投影方向上的数据方差来判断其重要性。但这对数据的区分作用并不大 ，反而可能使得数据点混杂在一起
• LDA 所追求的目标与 PCA 不同，不是希望保持数据最多的信息，而是希望数据在降维后能够很容易地被区分开

1. Kernel PCA：将主成分分析的线性假设一般化使之适应非线性数据
2. 等距映射：保持数据点内在几何性质(测地距离)

• ISO-Metric Mapping
  • 构造临近关系图：对每一个点，将它与指定半径邻域内所有点相连或与指定个数最近邻相连
  • 计算最短路径：计算临近关系图所有点对之间的最短路径，得到距离矩阵
  • 多尺度分析：将高维空间中的数据点投影到低维空间，使投影前后的距离矩阵相似度最大
  • 求矩阵$L=-\frac{1}{2}HSH$的特征值和特征向量，其中H是中心矩阵，S是距离矩阵的平方
• 优点：非线性、非迭代、全局最优、参数可调节
• 缺点：容易受噪声干扰、在大曲率区域存在短路现象、不适用于非凸参数空间、大样本训练速度慢

1. 局部线性嵌入：保持数据点的原有流形结构

• 前提假设：采样数据所在的低维流形在局部是线性的，每个采样点可以用它的近邻点线性表示
• 学习目标：在低维空间中保持每个邻域中的权值不变，即假设嵌入映射在局部是线性的条件下，最小化重构误差
• 对每个点用K个近邻进行重建，确定一组权值$w_{ij}$，求$M=(I-W)^T(I-W)$的特征值和特征向量

十二、集成学习

1. 集成学习：通过构建并结合多个学习器完成学习任务，也称为多分类器系统，通过将多个学习器进行集成，常可获得比单一学习器显著优越的泛化性能，这对弱学习器尤为明显

• 弱学习器：准确率仅比随机猜测略高的学习器，其训练通常更简单，容易得到
• 强学习器：准确率高并能在多项式时间内完成的学习器其训练往往非常复杂，不容易得到
• 在一定条件下，随着集成分类器数目的增加，集成的错误率将指数级下降，最终趋向于 0

1. 多样性度量：用于度量集成中个体学习器的多样性，考虑个体学习器的两两相似/不相似性

	$ h_i = +1 $	$ h_i = -1 $
$ h_j = +1 $	$ a $	$ c $
$ h_j = -1 $	$ b $	$ d $

其中，$ a + b + c + d = m $

• 不合度量：$ dis_{ij} = \frac{b + c}{m} $，值域 [0, 1]，值越大多样性越大
• 相关系数：值域[-1, 1]，学习器无关值为0；正相关值为正，否则为负，$ \rho_{ij} = \frac{ad - bc}{\sqrt{(a + b)(a + c)(c + d)(b + d)}} $

• Q-统计量：$ Q_{ij} = \frac{ad - bc}{ad + bc} $，$ Q_{ij} $与相关系数$ \rho_{ij} $符号相同，且$

  Q_{ij}

  \leq

  \rho_{ij}

  $

• k 统计量：$k=\frac{p_1-p_2}{1-p_2}$
  • $p_1$：$h_ih_j$ 一致概率，$p_1=\frac{a+d}{m}$
  • $p_2$：$h_ih_j$ 偶然一致概率（$h_ih_j$独立），$p_2=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^2}$
  • 通常非负，学习器完全一致时值为1；偶然一致时值为 0 ，一致概率低于偶然时取负值

1. 多样性增强：在学习过程引入随机性

• 数据样本扰动：通常是基于采样法
  • Bagging 中的自助采样
  • Adaboost 中的序列采样
  • 对数据样本扰动敏感的基学习器（不稳定基学习器）效果明显，如决策树、神经网络
  • 对数据样本扰动不敏感的基学习器 （稳定基学习器）效果不明显，如线性学习器，支持向量机，朴素贝叶斯， K 近邻等
• 输入属性扰动：不同子空间提供观察数据的不同视角
  • 对包含大量冗余属性数据，可产生多样性大的个体学习器，还因属性数减少会大幅节省时间开销
  • 若数据只含少量属性或冗余属性较少，则不宜使用
• 输出表示扰动：操纵输出表示
  • 翻转法：对训练样本的类标记稍作变动，随机改变一些训练样本的标记（噪声，增强模型泛化性）
  • 输出调制法：对输出表示进行转化，将分类输出转为回归输出构建个体学习器
  • ECOC 法：将原任务拆解为多个可同时求解的子任务，利用纠错输出码将多分类任务拆解为一系列二分类任务训练基学习器
• 算法参数扰动：参数扰动：随机设置不同的参数或环节
  • 参数较多时：负相关法，显式地通过正则化项强制个体神经网络使用不同参数
  • 参数较少时：例如将决策树使用的属性选择机制用其他类似方式代替，信息增益、信息增益率、基尼指数等
• 不同的多样性增强机制也可一起使用
  • Adaboost：加入了数据样本扰动
  • 随机森林：同时加入了数据样本扰动和输入属性扰动
• 单一学习器利用交叉验证对参数寻优，事实上相当于使用了不同参数训练学习器，最后仅选择了一个；而集成学习相当于把所有学习器都利用起来

1. 优点

• 统计方面：减小误选假设空间导致泛化性能不佳的几率
• 计算方面：降低陷入坏局部极小点影响泛化性能的风险
• 表示方面：扩大假设空间(域)学习对于真实空间更好近似

1. 组合策略

• 平均法：数值型输出最常见的结合策略
  • 简单平均法：个体学习器性能相近时适用
  • 加权平均法：个体学习器性能迥异时适用
  • 加权平均法是集成学习的基本出发点，各种结合方法都可视为其特例或变体，不同的集成学习方法是通过不同的方式确定加权平均法中基学习器的权重
• 投票法：标签型输出最常见的结合策略，分为硬投票（类标签）和软投票（类概率）
  • 绝对多数投票法：得票超半数
  • 相对多数投票法：得票最多
  • 加权投票法：加权后得票最多
• 学习法：当训练数据很多时采用另一个学习器进行结合
  • 从初始数据集训练初级学习器，生成次级数据集：初级学习器的输出被当作样例输入特征，继承初始样本标记从次级数据集训练次级学习器

1. 学习方法

• 串行化方法：个体学习器间存在强依赖关系
  • 提升 Boosting 算法：一族可将弱学习器提升为强学习器的算法
    • 每次调整训练数据的样本分布
    • 先从初始数据集训练一个基学习器，再根据其对训练样本分布（权重）进行调整，使先前错分样本在后续受到更多关注 ，然后基于调整后的样本分布训练下一个基学习器重复进行直至基学习器数目达到预先指定值；最终将这些基学习器加权结合
    • 重赋权法：在每轮根据样本分布为每个训练样本重新赋予权重
    • 重采样法：在每轮根据样本分布对训练集重新采样形成新的训练集
    • Boosting 每轮检查当前生成的基学习器是否满足优于随机猜测的基本条件，若不满足，此基学习器被抛弃，学习过程停止
  • 基本思想是用贪心法最小化损失函数
  • 主要关注降低偏差： 顺序串行地最小化损失函数，基于弱学习器逐步构造出很强的集成学习器 bias 自然逐步下降
  • 但是由于模型的相关性很强，因此不能显著降低方差，主要靠降低偏差来提升预测精度
  • 基学习器特点：高偏差、低方差的弱模型
• 并行化方法： 个体学习器间不存在强依赖关系
  • 装袋 Bagging 算法
    • 利用自助法采样（Bootstrap）可构造 T 个含 m 个训练样本的采样集，基于每个采样集训练出一个基学习器，再将它们进行结合
    • 在对预测输出结合时，通常对分类任务使用简单投票法，对回归任务使用简单平均法
    • 时间复杂度低：集成与直接训练一个学习器复杂度同阶
    • 可包外估计泛化性能：将从未被采样过的样本作为测试集
  • 主要关注 降低方差，即通过多次重复训练提高稳定性，在易受样本扰动的学习器上效用更为明显，如不剪枝的决策树、神经网络等
  • 在 Bagging 中每个模型的偏差方差近似相同，但是互相相关性不太高，因此 一般不能降低偏差
  • 对噪声数据相对鲁棒
  • 基学习器特点：低偏差、高方差，通常用强学习器
  • 随机森林 Random Forest ：Bagging 方法的一种扩展变体，以决策树为基学习器
    • 数据集的随机选择 ：自助采样法
    • 待选属性的随机选择：对基决策树的每个结点，先从该结点的 d 个属性集合中随机选择一个包含 k 个属性的子集，再从这个子集选择一个最优属性用于划分，一般情况下推荐 $k =\text{log}_2d$
    • 最后如果是分类问题，则按照投票的方式选取票数最多的类作为结果返回；如果是回归问题，则按照平均法选取所有决策树预测的平均值作为结果返回
  • 基学习器多样性通过样本扰动和属性扰动实现
  • 算法简单、容易实现、计算开销小，训练效率优于 Bagging
  • 性能强大，被誉为“代表集成学习技术水平的方法”

十三、半监督学习

1. 监督学习：需要大量已标记的训练样本，大规模人工标注耗时、难度大、代价高（隐私、安全），标注数据通用性较弱，但未标注数据很容易获得，但未利用
2. 无监督学习：无已标记（监督信息）样本，基于未标记样本间的相似度，对样本进行类别归纳，如聚类和降维，但无监督学习完全基于无标记样本学习，精度难以保证，且未利用有可能有的少量有标记样本
3. 基本假设

• 聚类假设：数据存在簇结构，同一簇的样本属于同一类别
  • 处在相同聚类中的样本有较大可能拥有相同标记
  • 决策边界应尽量通过数据较稀疏的地方，避免把稠密聚类中的数据分到决策边界两侧
  • 大量未标记样本的作用就是帮助探明样本空间中数据分布的稠密和稀疏区域，指导对决策边界进行调整
• 流形假设（局部）：数据分布在一个流形结构上，邻近样本有相似输出值
  • 流形：局部具有欧几里得空间性质的空间
  • 处于很小局部区域内的样本有相似性质，因此标记也相似
  • 和聚类假设着眼整体特性不同，流形假设主要考虑模型的局部特性，反映决策函数的局部平滑性
  • 大量未标记示例的作用就是让数据空间变得更加稠密，从而有助于更加准确地刻画局部区域的特性，使得决策函数能够更好地进行数据拟合
  • 可看做是聚类假设的推广，对输出值没有限制（可以是相近的连续值），应用更广泛

1. 学习算法分类

• 直推学习：封闭世界假设，仅试图对学习过程中观察到的未标记样本进行预测
• 纯半监督学习：开放世界假设，学得模型能适用于训练过程中未观察到的未标记数据进行预测

1. 半监督学习算法分类

• 自学习方法：分类器递归拟合时，每次递归仅将满足设定置信度阈值，即置信度高的样本纳入已标记样本集中，参与递归拟合
• 半监督SVM
  • S3VM 是标准 SVM 方法在未标记样本上的一种推广，其中直推式支持向量机 T-SVM 是最典型的算法
  • 基本思想：针对二分类问题，同时利用标记和未标记样本，通过尝试将每个未标记样本分别作为正例和反例来寻找最优分类边界，来得到原始数据中两类样本的最大分类间隔（最小错误率），即寻找穿过数据低密度分布区域的分类面

  • $\min_{w, b, \hat{y}, \xi} \frac{1}{2}

    w

    2^2 + C_l \sum{i=1}^l \xi_i + C_u \sum_{i=l+1}^m \xi_i$

  • $\text{s.t.} \space \space y_i \left( w^\top x_i + b \right) \geq 1 - \xi_i, \space \space i=1,\dots,l$
  • $\hat{y}_i \left( w^\top x_i + b \right) \geq 1 - \xi_i, \quad i=l+1,\dots,m$
  • $\xi_i \geq 0, \space \space i=1,\dots,m $
  • 其中 $C_i$ 和 $C_u$ 分别表示已标记样本和未标记样本的惩罚因子，用于调整不同样本的权重
  • 尝试未标记样本的各种标记指派是一个穷举遍历过程，未标记样本数太大时不能直接求解
  • 采用局部搜索迭代求近似解，通过局部搜索和调整指派为异类且可能错误的标记指派，使目标函数值不断下降
  • 局部搜索$x_i，x_j$，将两者指派为不同标签，求解对应超平面和松弛变量，如果$\xi_i+\xi_j>2$，证明可能错误，互换标记再次求解
  • 初始时未标记样本的伪标记不准确，对应的$C_u$系数要小，逐渐增大$C_u$提高未标记样本贡献
  • 搜寻标记指派出错的每一对未标记样本并进行调整，是一个复杂的大规模优化问题
• 半监督聚类
  • 第一种类型是必连与勿连约束，前者是指样本必属于同一个簇，后者则是指样本必不属于同一个簇
    • 约束 K 均值算法：该算法是 K 均值算法的扩展
    • 它在聚类过程中要确保必连关系集合与勿连关系集合中的约束得以满足，否则将返回错误提示
    • 如果不冲突，那么将点划分近最近的簇，否则，再尝试次近的簇
  • 第二种类型的监督信息则是少量的有标记样本
    • 约束种子K 均值算法：假设少量有标记样本属于 K 个聚类簇，直接将它们作为种子，用它们初始化 K 均值算法的 K 个聚类中心，并且在聚类簇迭代更新过程中，不改变种子样本的簇隶属关系
• 半监督学习的抗干扰性比较弱
  • 现有算法多针对无噪声干扰样本数据，而实际数据通常存在噪声干扰
  • 需综合考虑噪声干扰下未标记样本数据分布的不确定性及复杂性