第一章: 绪论
- 机器学习：机器利用数据学习人类经验，不断提高性能的过程
- 应用：搜索引擎、自动汽车驾驶、帮助奥巴马胜选、AlphaGO、视频理解……
- 人工智能的发展历史阶段：(60-70) 推理期 (80 年代中期) 知识期 (90 年代中期) 学习期
- 人工智能的寒冬：低估智能的复杂性；脱离现实问题
- 可能的未来：稳健机器学习
- 机器学习是(计算机视觉, 自然语言处理, 模式识别)的核心技术，xxx 是机器学习的重要应用；统计学是机器学习的重要理论基础；机器学习发展过程中受神经科学思想的启发，不会借鉴它的基础技术
- 期刊：AIJ, JMLR, TPAMI, TKDE, etc. 会议：ICML, NeurIPS, KDD, AAAI, IJCAI, ICLR, MLA, etc.
- 根本目标：模型具有泛化能力
- No Free Lunch: 一个算法数学公式: $\mathfrak{L}_a$ 若在某些问题上比另一个算法 $\mathfrak{L}_b$ 好，必存在另一些问题 $\mathfrak{L}_b$ 比 $\mathfrak{L}_a$ 好
第二章: 模型评估和选择
经验误差与过拟合
过拟合，⽋拟合
- 泛化误差: 在"未来"样本上的误差, 越小越好
- 经验误差: 在训练集上的误差, 亦称"训练误差", 并非越小越好, 会出现"过拟合"
- 没有严重的过拟合, 欠拟合时, 经验误差和泛化误差可以互相界定
评估⽅法
留出法，交叉验证
- 留出法
- 将数据集划分为互斥的集合: 训练集和验证集
- 保持分布一致: 分层采样保持类别比例一致, 若干次随机划分取平均
- 交叉验证
- 分层采样为 k 个大小相似的互斥子集, 每次用 k-1 个的并集训练, 余下的验证集, 返回 k 个测试结果的均值
- p 次 k 折交叉验证: 划分互斥子集的时候进行 p 次随机划分。
性能度量
均⽅误差，精度，查准率/查全率/F1，AUC
均方误差: 回归任务 $$E(f;D)=\frac{1}{m}\sum_{i=1}^m(f(x_i)-y_i)^2$$
分类错误率, 精度: 分类任务 $$E(f;D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(f(x_i)-y_i)$$ $$acc(f;D)=1-E(f;D)$$
查准率, 查全率, F1 $$P=\frac{TP}{TP+FP}$$ $$R=\frac{TP}{TP+FN}$$ $$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{N + TP-TN}$$ $$F_\beta=\frac{1+\beta^2\times P \times R}{(\beta^2\times P) + R}, \beta控制偏重$$
ROC 曲线: 遍历真正例率(TP)和假正例率(FP), 绘制曲线
AUC 值: ROC 曲线下的面积, 可估算为$\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_i)\cdot(y_i + y_{i+1})$
⽐较检验
T-检验
- T-检验: 假定得到了$k$个测试错误率, $\epsilon_i$, 假设$\epsilon=\epsilon_0$对于显著度$\alpha$, 若$[t_{-\frac{\alpha}{2} }, t_{\frac{\alpha}{2} }]$位于临界范围$|\mu-\epsilon_0|$内, 则假设不能被拒绝, 即可认为泛化错误率$\epsilon=\epsilon_0$, 其置信度为$1-\alpha$
偏差与⽅差
了解基本原理
- 对回归任务, 泛化误差通过"偏差-方差分解"拆解为 3 部分 $$E(f;D)=bias^2(x)+var(x) + \varepsilon^2$$
- 学习算法的能力: 期望输出与真实输出的差别 $$bias^2(x)=(\bar{f}(x)-y) ^2$$
- 数据的充分性: 同样大小的训练集变动, 导致的性能变化 $$var(x)=\mathbb{E}_D[(f(x;D)-\bar{f}(x))^2]$$
- 学习任务本身的难度: 当前任务上任何算法的泛化误差下界, 即训练样本标记与真实标记的区别 $$\varepsilon^2=\mathbb{E}_D[(y_D-y)^2]$$
第三章: 线性模型
回归任务
掌握最⼩⼆乘法原理和推导
最小二乘法
- 参数估计方法: 最小化均方误差 $$E(w,b)=\sum_{i=1}^m(y_i-wx_i-b)^2$$
- 分别求导, 可得 $$\frac{\partial E}{\partial w}=2(w\sum x_i^2-\sum(y_i-b)x_i)$$ $$\frac{\partial E}{\partial b}=2(mb-\sum(y_i-wx_i))$$
- 得到闭式解 $$w=\frac{\sum y_i(x_i-\bar{x})}{\sum x_i^2-\frac{1}{m}(\sum x_i)^2 }$$ $$b=\frac{1}{m}\sum(y_i-wx_i)$$
- 其中 $$\bar{x}=\frac{1}{m}\sum x_i$$
多元线性回归: 最小二乘法
- 齐次表达: 将$b$吸收到$w$中, $\hat{w}=(w;b)$ $$\hat{w}^*=\arg\min_{\hat{w} }(y - X\hat{w})^T(y - X\hat{w})$$
- 求导 $$\frac{\partial E}{\partial \hat{w} }=2X^T(X\hat{w}-y)$$
- 满秩讨论: 满秩则闭式解, 否则需正则化 $$\hat{w}^*=(X^TX)^{-1}X^Ty$$
⼆分类任务
熟悉对数⼏率回归
- 对数几率函数 $$y=\frac{1}{1+e^{-z} }$$
- 对数几率回归: 以对数几率函数为联系函数 $$y=\frac{1}{1+e^{-z} }=\frac{1}{1+e^{-(w^Tx+b)} }$$
- 即 $$\ln\frac{y}{1-y}=w^Tx+b$$
- 对数几率回归: 极大似然法 $$\ln\frac{p(y=1|x)}{p(y=0|x)}=w^Tx+b$$ $$p(y=1|x)=\frac{e^{(w^Tx+b)} }{1+e^{(w^Tx+b)} }$$ $$p(y=0|x)=\frac{1}{1+e^{(w^Tx+b)} }$$
- 极大似然法
- 给定数据集${(x_i,y_i)}_{i=1}^m$
- 最大化样本属于真实标记的概率 $$l(w,b)=\sum\ln p(y_i|x_i;w_i,b)$$
- 转化为最小化负对数似然函数求解 $$w^Tx+b=\beta^T\hat{x}, \beta=(w;b),\hat{x}=(x;1)$$
- 再令 $$p_1(\hat{x}_i;\beta)=p(y=1|\hat{x};\beta)$$ $$p_0(\hat{x}_i;\beta)=p(y=0|\hat{x};\beta)=1-p_1(\hat{x}_i;\beta)$$ $$p(y_i|x_i;w_i,b)=y_ip_1(\hat{x}_i;\beta)+(1-y_i)p_0(\hat{x}_i;\beta)$$
- 重写似然项, 等价于最小化下式 $$l(\beta)=\sum(-y_i\beta^T\hat{x}_i+\ln(1+e^{\beta^T\hat{x}_i}))$$
- 牛顿法更新
多分类任务
熟悉⼀对⼀、⼀对其余、多对多的原理
- 一对一
- 训练
- 拆分: N 个类别两两配对
- 各个二分类任务学习分类器
- 测试
- 新样本给每个分类器预测
- 投票产生最终分类, 票数最高的为最终结果
- 训练
- 一对其余
- 训练
- 拆分: 某一类正例, 其余反例
- 各个二分类任务学习分类器
- 测试
- 新样本给每个分类器预测
- 置信度最大的类别作为最终类别
- 训练
- 一对一 vs 一对其余
- 一对一: 存储和测试开销大, 训练时间短
- 一对其余: 存储和测试开销小, 训练时间长
- 多对多
- 若干类作为正, 若干类作为负
- 纠错输出码
- 对 N 个类做 M 次划分, 若干正若干反: M 个二分类任务, 得到 M 长度的编码
- 测试样本交给 M 个分类器预测: 长度为 M 的编码预测, 距离最小的为最终类别
- ECOC 编码
- 编码越长, 纠错能力越强
- 同等长度, 类别间的距离越远, 纠错能力越强
线性模型的优缺点
- 优点
- 形式简单, 容易建模
- 有一定的可解释性
- 缺陷
- 难以处理非线性问题(例如异或)
第四章: 支持向量机
间隔和⽀持向量
- 超平面选择: “正中间"的最好, 鲁棒性好, 泛化能力强
- 超平面方程: $w^Tx+b=0$
- 正例一侧: $w^Tx+b\geq1$
- 负例一侧: $w^Tx+b\leq-1$
- 样本距离: $r=\frac{|w^Tx+b|}{||w||}$
- 间隔: $\gamma=\frac{2}{||w||}$
- 支持向量: 位于$\pm1$的直线上
⽀持向量机基本型
- 最大化间隔: 寻找参数$w$和$b$, 使得$\gamma$最大
- 优化问题: 转为凸二次规划问题 $$\arg\max_{w,b}\frac{2}{||w||}\Leftrightarrow\arg\min_{w,b}\frac{||w||^2}{2}$$
- $s.t.\quad y_i(w^Tx+b)\geq 1, i=1,2,\cdots,m$
⽀持向量机对偶型
引入拉格朗日乘子$\alpha_i\geq 0$得到拉格朗日函数 $$L(w,b,\alpha)=\frac{||w||^2}{2} + \sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))$$
令$L(w,b,\alpha)$对$w$和$b$偏导数为 0 $$w=\sum_i\alpha_iy_ix_i\quad 0=\sum_i\alpha_iy_i$$
回代可得 $$\max_{\alpha}\sum_i\alpha_i-\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_j y_iy_j x_i^Tx_j$$
基本型和对偶型都可以使用数值优化得到全局最优解
基本型善于处理低维数据和高维度稀疏数据; 对偶型善于处理高维稠密数据和吸收核函数进行非线性分类
特征空间映射
- 原空间是有限维, 则一定存在一个高维空间使样本线性可分
核函数
- 设计核函数 $$\kappa(x_i,x_j)=\phi(x_i)^T\phi(x_i)$$
- 若一个对称函数对应的核矩阵半正定, 则他就能作为核函数使用
- 线性核: $x_i^Tx_j$
- 多项式核: $(x_i^Tx_j)^T, d次数$
- 高斯核: $\exp(-\frac{||x_i^Tx_j||^2}{2\delta^2}), \delta 带宽$
- 拉普拉斯核: $\exp(-\frac{||x_i^Tx_j||}{\delta})$
- sigmoid 核: $\tanh(\beta x_i^Tx_j + \theta),\beta>0, \theta\lt 0$
软间隔⽀持向量机
软间隔不再假设线性可分或核线性可分, 引入损失函数,最大化间隔的同时最小化损失 $$\arg\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i}l_{0/1}(y_i(w^T\phi(x_i) + b)-1)$$ $$ l_{0/1}=\begin{cases} 1 & \text{if } z \lt 0\ % & is your “\tab”-like command (it’s a tab alignment character) 0 & \text{otherwise.} \end{cases} $$
hinge 损失函数: 代替$l_{0/1}$
- $l_{\mathrm{hinge}}(z)=\max(0,1-z)$
- $l_{\mathrm{exp}}(z)=\exp(-z)$
- $l_{\mathrm{log}}(z)=\log(1+\exp(-z))$
基本型和对偶型
- 类似一般支持向量机, 替换$x_i^Tx_j$为核函数
正则化
- 正则化项: 结构风险 + 经验风险
$$min_{f}(\Omega(f)+C\sum l(f_(x_i), y_i))$$
- 结构风险: 描述模型本身的性质
- 经验风险: 描述模型与数据的契合程度
- 理解为"罚函数”: 对不希望的结果加以惩罚
- 理解为贝叶斯估计: 为模型提供了先验概率
第五章: 神经网络
神经元模型
熟悉
- M-P 神经元模型
- 输入: 来自其他 n 个神经元的信号
- 处理: 通过带权重的连接进行传递, 总值与神经元的阈值比较
- 输出: 通过激活函数得到输出 $$y=f(\sum_{i}w_ix_i - \theta)$$
- 激活函数
- 理想激活函数是阶跃函数
$$
\mathrm{sgn}=\begin{cases}
1 & \text{if } x \geq 0 \
0 & \text{if } x \lt 0 \end{cases} $$ - 常用 sigmoid 函数, 可导且光滑 $$\mathrm{sigmoid}(x)=\frac{1}{1+e^{-x} }$$
- 理想激活函数是阶跃函数
$$
\mathrm{sgn}=\begin{cases}
1 & \text{if } x \geq 0 \
感知机与多层网络
熟悉
- 感知机: 2 层神经元组成
- 输入层: 接受外界输入信号传递给输出层
- 输出层: M-P 神经元(阈值逻辑单元)
- 可以实验逻辑与或非
- 学习能力
- 当两类模式线性可分时, 则感知机的学习过程一定会收敛
- 否则感知机的学习过程将会发生震荡
- 单层感知机的学习能力有限, 只能解决线性可分问题
- 隐层或隐含层
- 输出层与输入层之间的一层神经元
- 隐含层和输出层神经元都是具有激活函数的功能神经元
- 多层前馈神经网络
- 定义：每两层神经元全互联，不存在同层连接和跨层连接
- 前馈：接受外界输入信号，隐含层与输出层神经元对信号进行加工输出
- 学习：根据训练数据调整神经元的“连接权”以及功能神经元的“阈值”
- 多层网络：包含隐层的网络
误差逆传播算法
熟悉
记号
- 输出层神经元阈值: $\theta_j$
- 隐含层神经元阈值: $\gamma_h$
- 输入层与隐层神经元之间的权重: $v_{ih}$
- 隐层与输出层神经元之间的权重: $w_{hj}$
前向计算
- $b_h=f(\alpha_h-\gamma_h), \alpha_h=\sum_{i=1}^dv_{ih}x_i$
- $\hat{y}j^k=f(\beta_j-\theta_j), \beta_j=\sum{i=1}^qw_{hj}b_h$
- $E_k=\frac{1}{2}\sum_{j=1}^l(\hat{y}_j^k-y_j^k)^2$
参数数目
- 权重: $v_{ih}$, $w_{hj}$
- 阈值: $\theta_j$, $\gamma_h$
- 共有: $(d+l+1)q + l$个参数需要优化
参数优化
- 迭代学习算法, $v\leftarrow v+\Delta v$
误差逆传播算法
- 梯度下降策略
$$\Delta w_{hj} = -\eta\frac{\partial E_k}{\partial w_{hj} }$$
$$
\frac{\partial E_k}{\partial w_{hj} } = \frac{\partial E_k}{\partial \hat{y}_j^k }\cdot \frac{\partial \hat{y}_j^k}{\partial \beta_j }\cdot\frac{\partial \beta_j}{\partial w_{hj} }
$$
$$
\begin{align}
g_j &= -\frac{\partial E_k}{\partial \hat{y}_j^k }\cdot \frac{\partial \hat{y}_j^k}{\partial \beta_j } \
&= -(\hat{y}_j^k - y_j^k)f'(\beta_j-\theta_j) \
&= \hat{y}_j^k(1-\hat{y}_j^k)(\hat{y}_j^k - y_j^k) \end{align} $$ $$ \begin{align} e_h &= -\frac{\partial E_k}{\partial b_h }\cdot \frac{\partial b_h}{\partial \alpha_h } \
&= -\sum_{j=1}^l \frac{\partial E_k}{\partial \beta_j}\cdot\frac{\partial \beta_j}{\partial b_h}f'(\alpha_h - \gamma_h) \
&= -\sum_{j=1}^lw_{hj}g_jf'(\alpha_h - \gamma_h) \
&= b_n(1-b_n)\sum_{i=1}^lw_{hj}g_j
\end{align} $$ - 以误差率为目标，计算负梯度方向, 对参数进行调整 $$\frac{\partial \beta_j}{\partial w_{hj} }=b_h$$ $$\Delta w_{hj}=\eta g_j b_h$$ $$\Delta \theta_j=-\eta g_j$$ $$\Delta v_{hj}=\eta e_h x_i$$ $$\Delta \gamma_h=-\eta e_h$$
- 学习率$\eta$控制着算法每一轮迭代中的更新步长, 若太长则让容易震荡, 太小则收敛速度又会过慢.
- 梯度下降策略
$$\Delta w_{hj} = -\eta\frac{\partial E_k}{\partial w_{hj} }$$
$$
\frac{\partial E_k}{\partial w_{hj} } = \frac{\partial E_k}{\partial \hat{y}_j^k }\cdot \frac{\partial \hat{y}_j^k}{\partial \beta_j }\cdot\frac{\partial \beta_j}{\partial w_{hj} }
$$
$$
\begin{align}
g_j &= -\frac{\partial E_k}{\partial \hat{y}_j^k }\cdot \frac{\partial \hat{y}_j^k}{\partial \beta_j } \
实现
- 标准 BP 算法: 每次对单个训练样例更新权值与阈值；单次计算开销小，但参数更新频繁, 不同样例对参数更新可能会相互冲抵，迭代次数较多
- 累计 BP 算法: 最小化整个训练集上的累计误差; 读取整个训练集后对更新参数，参数更新频率低，但单次计算开销大 $$E=\frac{1}{m}\sum_{k=1}^m E_k$$
- 数据很大时标准 BP 更好
多层前馈网络优缺点
- 优点: 具有强大的学习能力: 包含足够多神经元的隐层, 多层前馈神经网络能以任意精度逼近任意复杂度的连续函数
- 缺点
- 络由于强大的表示能力, 经常遭遇过拟合
- 如何设置隐层神经元个数是难题
- 缓解过拟合
- 早停：在训练过程中, 若训练误差降低, 但验证误差升高, 则停止训练
- 正则化: 在误差目标函数中增加一项描述网络复杂程度的成分, 防止模型过于复杂，例如连接权值与阈值的平方和
全局最⼩与局部最⼩
了解
- 学习过程: 参数寻优, 在参数空间中寻找最优参数, 使得误差最小
- 全局最小: 只有一个最优的
- 局部极小: 存在多个, 需要跳出
- 不同的初始参数, 模拟退火, 随机扰动, 遗传算法
深度学习
了解
- 深度学习模型
- 是具有很多个隐层的神经网络
- 计算能力的大幅提高缓解了训练效率
- 训练数据的大幅增加降低了过拟合风险
- 增加模型复杂程度的方法
- 宽度: 增加隐层神经元的数目
- 深度: 增加隐层数目
- 实际: 增加深度比增加宽度更有效
- 复杂模型的困难
- 梯度消失
- 训练方法
- 预训练+微调
- 预训练: 逐层监督, 每次训练时将上一层输出作为输入, 本层节点输出为输出, 仅训练一层
- 微调: 预训练完成后, 整个网络微调
- 无监督预训练+BP 微调
- 权共享
- 一组神经元使用相同的连接权值(例如 CNN)
- 预训练+微调
- 卷积神经网络 CNN
- 卷积层：每个卷积层包含多个特征映射, 每个特征映射通过一种卷积滤波 器提取一种数据的特征
- 采样层：亦称“汇合层”, 其作用是基于局部相关性原理进行亚采样, 从而 在减少数据量的同时保留有用信息
- 连接层：每个神经元被全连接到上一层每个神经元, 本质就是传统的神经 网络, 其目的是通过连接层和输出层的连接完成识别任务
- 激活函数: $f(x) = \max(0,x)$
- 训练: 使用 BP 进行训练, 但在训练中, 将卷积层和采样层的每一组神经元约定为相同的连接权, 从而大幅减少了参数数目
- 理解深度学习
- 特征工程由人类专家根据现实任务来设计, 特征提取与识别是分开的两个阶段
- 特征学习通过深度学习自动产生有益于分类的特征, 是一个端到端的学习框架
第六章: 决策树
决策树简介（基本流程）
掌握决策树基本流程和原理
- 策略: 分而治之, 每个节点选择一个属性, 划分样本
- 停止条件
- 当前节点全部属于同一类别, 无需划分
- 当前属性集为空, 或所有样本的在所有属性上取值均相同, 无法划分
- 当前节点包含的样本集合为空, 不能划分
决策树算法的关键：划分选择
熟悉划分准则
- 关键: 选择最优划分标准
- 直觉: 纯度越高越好, 即分支节点所包含的样本尽可能属于同一类别
- 经典方法: 信息增益/增益率
- 信息增益
- 增益: $\mathrm{Gain}=\mathrm{Ent}(D) - \sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$
- 信息熵: $\mathrm{Ent}(D)=-\sum_{k=1}^{|\mathcal{y}|}p_k\log_2 p_k, p_k样本比例$
- 增益率
- $\mathrm{Gain_ratio}(D, a)=\frac{\mathrm{Gain}(D, a)}{\mathrm{IV}(a)}$
- $\mathrm{IV}(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$
- 对比
- 信息增益偏好取值数多的属性
- 增益率准则偏好取值数较少的属性, 相当于给信息增益做了一个规范化
克服过拟合的问题：剪枝处理
预剪枝 vs 后剪枝
- 决策树的不⾜: 过拟合
- 决策树决策分⽀过多，以致于把训练集⾃⾝的⼀些特点, 当做所有数据都具有的⼀般性质, ⽽导致的过拟合
- 剪枝的基本策略
- 预剪枝：边建树，边剪枝
- 后剪枝：先建树，后剪枝
- 判断决策树泛化性能是否提升的⽅法
- 留出法：预留⼀部分数据⽤作“验证集”以进⾏性能评估
- 预剪枝
- 思路
- 决策树⽣成过程中，对每个结点在划分前先进⾏估计
- 若当前结点的划分不能带来决策树泛化性能提升，则停⽌划分并将当前结点记为叶结点
- 其类别标记为训练样例数最多的类别
- 优点
- 降低过拟合⻛险
- 显著减少训练时间和测试时间开销
- 缺点: ⽋拟合⻛险
- 预剪枝基于“贪⼼”本质禁⽌这些分⽀展开
- 有些分⽀的当前划分不能提升泛化性能，后续划分却有可能导致性能显著提⾼
- 思路
- 后剪枝
- 思路
- 决策树生成后, 考察中间节点
- 若将其领衔的分支剪除, 即将其替换为叶, 验证集精度提高, 则剪枝
- 优点: ⽋拟合⻛险⼩
- 后剪枝⽐预剪枝保留了更多的分⽀，泛化性能往往优于预剪枝决策树
- 缺点: 训练时间开销⼤
- 在⽣成完全决策树之后进⾏的，需要⾃底向上对所有⾮叶结点逐⼀考察；其训练时间要远⼤于预剪枝决策树
- 思路
决策树的变体：多变量决策树
了解基本原理
- 单变量决策树分类边界: 与轴平⾏
- 非叶节点不再是仅对某个属性,而是对属性的线性组合
- 每个非叶结点是一个线性分类器
- 其需要在所处的集合当中学习得到
第七章: 贝叶斯分类器
⻉叶斯决策论
掌握⻉叶斯决策论
- 基本理论
- 给定$N$个类别, 令$\lambda_{ij}$代表将第$j$类样本误分类为$i$类产生的损失, 则基于后验概率, 将样本$x$分到第$i$类的条件风险为: $$R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x)$$
- 贝叶斯判定准则 $$h^*(x)=\arg\min_{c\in \mathcal{Y} }R(c|x)$$
- $h^*$称为贝叶斯最优分类器, 其总体风险称为贝叶斯风险, 反映学习性能的理论上限
朴素⻉叶斯（拉普拉斯修正）
熟悉朴素⻉叶斯（拉普拉斯修正）
朴素贝叶斯分类器 $$P(c|x)=\frac{P(c)P(x|c)}{P(x)}$$
- 基本思路: 假定属性相互独立 $$P(c|x)=\frac{P(c)P(x|c)}{P(x)}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)$$
- $P(x)$对所有类别相同, 于是 $$h_{nb}=\arg\max_{c\in\mathcal{Y} }P(c)\prod_{i=1}^dP(x_i|c)$$
估计
- 估计$P(c)=\frac{|D_c|}{|D|}$
- 估计$P(x|c)$
- 对于离散属性, 令$D_{c,x_i}$表示$D_c$中在第$i$个属性上取值为$x_i$的样本组成的集合, 则 $$P(x_i|c) = \frac{|D_{c,x_i}|}{|D_c|}$$
- 对于连续属性, 考虑概率密度函数, 假设$p(x_i|c)\sim \mathcal{N}(\mu_{c,i},\sigma_{c,i}^2)$ $$p(x_i, c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i} }\exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2})$$
拉普拉斯修正
- 若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，因为概率连乘将“抹去”其他属性提供的信息
- 假设属性值随类别呈均匀分布(给每个 属性-类别 组合添加一个样本) $$\hat{P}(c)=\frac{|D_c|+1}{|D| + N}, \quad \hat{P}(x_i|c)=\frac{|D_{c,x_i}| + 1}{|D_c|+N_i}$$
朴素贝叶斯分类器的使用
- 对预测速度要求高: 预计算所有概率估值, 使用时查表
- 数据更新频繁: 不进行任何训练, 收到预测请求时再估值
- 懒惰学习
- 若数据不断增加: 基于现有估值, 对新样本涉及的概率估值进行修正
- 增量学习
半朴素⻉叶斯
掌握半朴素⻉叶斯
半朴素贝叶斯分类器: 考虑一部分属性间的相互依赖
- 最常用策略: 独依赖估计(ODE)假设每个属性在类别之外最多仅依赖一个其他属性 $$P(c|x)\propto P(c)\prod_{i=1}^d P(x_i|c,pa_i), pa_i父属性$$
SPODE: 假设所有属性都依赖于同一属性, 超父, 通过交叉验证等模型选择超父
TAN: 利用属性间的条件"互信息"为边的权重, 构建完全图; 之后使用最大权生成树算法, 仅保留强相关属性间的依赖性
AODE
- 尝试将每个属性作为超父构建 SPODE
- 将拥有足够数据支撑的 SPODE 集成起来作为最终结果 $$P(c|x)\propto \sum_{i=1,|D_{x,i}\geq m'|}^dP(c,x_i)\prod_{j=1}^dP(x_j|c,x_i), m’阈值常数$$
高阶依赖
- 能否通过考虑属性间的高阶依赖来进一步提升泛化性能
- ODE->kDE: 将父属性替换为属性集合
- 障碍: 所需的样本数指数级增加
⻉叶斯网
了解⻉叶斯网
贝叶斯网
- $\lt G,\Theta \gt$, 结构和参数
- 有向无环图(vs 马尔可夫网: 无向图模型)
- 给定父结点集，贝叶斯网假设每个属性与其非后裔属性独立 $$P_B(x_1,\cdots, x_d)=\prod_{i=1}^dP_B(x_i|\pi_i)=\prod_{i=1}^d\theta+{x_i|pi_i}, \pi_i父节点集$$
三变量的典型依赖关系
- 同父结构: 条件独立性, x1->x3, x1->x4 $$x_3\perp x_4 | x_1$$
- V 型结构: 边际独立性, x1->x4, x2->x4 $$x_1\perp!!!!\perp x_2 $$
- 顺序结构: 条件独立性, z->x->y $$y\perp z | x$$
分析条件独立性
- 先将有向图转变为无向图
- V 型结构父结点相连
- 有向边变成无向边
- 若 x 和 y 能在图上被 z 分入两个连通分支，则有$x\perp y|z$
- 得到条件独立性关系之后，估计出条件概率表，就得到了最终网络
- 先将有向图转变为无向图
第八章: 集成学习
- 一会儿再写
个体与集成
知道个体分类器的定义和集成学习的定义
- 集成学习: 通过多学习器来提升性能
- 关键：好而不同
- 关键假设：基学习器的误差相互独立
- 个体学习器的“准确性”和“多样性”本身就存在冲突
Boosting
Boosting 思想和 adaboost 的实现
- 定义
- 每次调整训练数据的样本分布
- 串行生成, 个体学习器存在强依赖关系
- Adaboost 实现
输入：训练数据集，其中
；弱学习算法
输出：分类器
1. 初始化训练数据的权值分布
2. 对
2.1 使用具有权值分布的训练数据集学习，得到基本分类器
2.2 计算在训练数据集上的分类误差率
2.3 计算的系数
2.4 更新训练数据集的权值分布
其中，是规范化因子
3. 构建基本分类器的线性组合
得到最终分类器
- 数据分布的学习
- 重赋权法、重采样法
- 重启动，避免训练过程过早停止
- 降低偏差，可对泛化性能相当弱的学习器构造出很强的集成
Bagging 与随机森林
思想和实现⽅式
定义
- 个体学习器不存在强依赖关系
- 并行化生成
- 自助采样法
优点: 时间复杂度低, 可使用包外估计
包外估计
- 仅考虑那些未使用样本$x$训练的基学习器在$x$上的预测 $$H^{oob} = \arg\max_{y\in\mathcal{Y} }\sum_{t=1}^T\mathbb{I}(h_t(x)=y)\cdot \mathbb{I}(x\notin D_t)$$
- Bagging 泛化误差的包外估计为 $$\epsilon^{oob}=\frac{1}{|D|}\sum_{(x,y)\in D}\mathbb{I}(H^{oob}(x)\ne y)$$
从偏差-方差的角度：降低方差，在不剪枝的决策树、神经网络等受样本影响的学习器上效果更好
随机森林
- 不断递归(随机选择属性 -> 划分样本集合)
- 采样的随机性 + 属性选择的随机性
结合策略
⼏种常用策略以及 stacking 的优缺点, 平均法, 投票法, 学习法
- 平均法 / 加权平均法
- 集成学习中的各种结合方法都可以看成是加权平均法的变种或特例
- 加权平均法未必一定优于简单平均法
- 投票法
- 绝对多数投票法
- 相对多数投票法
- 加权投票法
- 学习法 Stacking
- 第一层学习器: 分类任务
- 第二层学习器: 用第一层在未见过的样本上, 产生的输出作为输入, 训练结合学习器
- 优点: 性能?
- 缺点: 次级学习器的输入属性表示和次级学习算法对 Stacking 集成的泛化性能有很大影响
多样性
多样性扰动的⼏种办法, 误差-分歧分解, 多样性度量, 多样性扰动
- 误差-分歧分解
- 集成误差 = 平均基学习器误差 - 基学习器分歧
- 多样性增强
- 数据样本扰动
- 通常是基于采样法: Bagging 自助采样, Adaboost 序列采样
- 对样本敏感: 决策树, 神经网络
- 对样本不敏感: 线性, SVM, 朴素贝叶斯, k 近邻
- 输入属性扰动
- 随机子空间算法: 随机选一部分维度
- 输出表示扰动
- 翻转法(Flipping Output): 随机改变输入样本的标记
- 输出调剂法(Output Smearing): 分类输出改为回归输出得到分类器
- ECOC 法: 多类任务分解为一系列两类任务来求解
- 算法参数扰动
- 负相关法: 强制要求个体神经网络采用不同的参数
- 不同的多样性增强机制同时使用
- 数据样本扰动
第九章: 聚类
聚类任务
能够清晰说出聚类任务是什么
- 定义: 将数据样本划分为若干个通常不相交的“簇”(cluster)
- 即可找寻数据内在的分布结构, 也作为分类学习任务中提取特征、判断类别的重要支撑
- 硬聚类: 不相交的簇
- 软聚类: 可相交的簇
性能度量
能够⼤体说出度量的核⼼是什么，有哪些考虑
- 聚类性能度量，亦称聚类“有效性指标”(validity index)
- 基本思路: 簇内相似度高, 簇间相似度低
- 指标
- 外部指标: 与"参考模型"比较
- 如 Jaccard 系数，FM 指数，Rand 指数
- 内部指标: 直接考察聚类结果
- 如 DB 指数，Dunn 指数等
- 外部指标: 与"参考模型"比较
- 聚类本身没有好坏之分；当用于具体任务时，根据效果如何，有好坏之分
距离计算
能够说出距离计算对聚类的意义
意义: 聚类来自于分组，分组来自于合理度量，度量来自于距离；因此距离对聚类很本质
距离度量基本性质
- 非负性: $\mathrm{dist}(x_i, x_j) \geq 0$
- 同一性: $\mathrm{dist}(x_i, x_j) = 0 \iff x_i=x_j$
- 对称性: $\mathrm{dist}(x_i, x_j) = \mathrm{dist}(x_j, x_i)$
- 直递性: $\mathrm{dist}(x_i, x_j) \geq \mathrm{dist}(x_i, x_k) + \mathrm{dist}(x_k, x_j)$
常用形式: 闵可夫斯基距离 $$\mathrm{dist}{mk}(x_i, x_j)=(\sum{u=1}^n |x_{iu} - x_{ju}|^p)^{\frac{1}{p} }$$
- $p=1$, 曼哈顿距离
- $p=2$, 欧氏距离
对于无序属性
- 令$m_{u,a}$表示属性$u$上取值为$a$的样本数, $m_{u,a,i}$表示在第$i$个样本簇中在属性$u$上取值为$a$的样本数, $k$为样本簇数, 则属性$u$上两个离散值$a$与$b$的 VDM 距离为 $$\mathrm{VDM}_p(a,b)=\sum_{i=1}^{k}|\frac{m_{u,a,i} }{m_{u,a} } - \frac{m_{u,b,i} }{m_{u,b} }|^p$$
对于混合属性
使用 MinkovDM
$$\mathrm{MinkovDM}_p(x_i, x_j)=(\Phi)^{\frac{1}{p} }$$$$\Phi=\sum_{u=1}^{n_c}|x_{iu} - x_{ju}|^p + \sum_{u=n_c + 1}^n\mathrm{VDM}_p(x_{iu}, x_{ju})$$
原型聚类
能够说出思路和代表性算法
假设：聚类结构能通过一组原型刻画
过程：先对原型初始化，然后对原型进行迭代更新求解
代表：k 均值聚类，学习向量量化(LVQ)，高斯混合聚类
k-Means
- 每个簇中心以该簇中所有样本点的“均值”表示
- 步骤
- Step1: 随机选取 k 个样本点作为簇中心
- Step2: 将其他样本点根据其与簇中心的距离，划分给最近的簇
- Step3: 更新各簇的均值向量，将其作为新的簇中心
- Step4: 若所有簇中心未发生改变，则停止；否则执行 Step 2
学习向量量化(LVQ)
- 也是试图找到一组原型向量来刻画聚类结构，但数据样本带有类别标记
- 通过聚类来形成类别的“子类”结构；每个聚类对应于类别的一个子类
高斯混合聚类
- 采用高斯概率分布来表达聚类原型，簇中心=均值，簇半径=方差
- 其假设样本由高斯混合分布生成
$$p_M(x)=\sum_{i=1}^k\alpha_i\cdot p(x|\mu_i, \Sigma_i)$$
- 根据$\alpha_i$定义的先验分布选择高斯混合成分, 其中$\alpha_i$为选择第$i$个混合成分的概率
- 然后, 根据被选择的混合成份的概率密度函数进行采样, 从而生成对应的样本
- 样本由第$i$个高斯混合成分生成的后验概率为
$$p_M(z_j-i|x_i)=\frac{P(z_J=i)p_M(x_j|z_j=i)}{p_M(x_j)}=\frac{\alpha_i p(x_j|\mu_i,\Sigma_i)}{\sum_{l=1}^k\alpha_i p(x_j|\mu_l,\Sigma_l)}=\gamma_{ji}$$
- 采用极大似然进行参数估计 $$LL(D)=\ln(\prod_{j=1}^mp_M(x_j))=\sum_{j=1}^m\ln(\prod_{i=1}^k\alpha_ip(x_j|\mu_i,\Sigma_i))$$
- EM 算法
- E 步: 根据当前参数计算每个样本属于每个高斯成分的后验概率$\gamma_{ji}$
- M 步: 更新模型参数${(\alpha_i, \mu_i, \Sigma_i)|1\leq i\leq k}$
密度聚类
能够说出思路和代表性算法
- 假设：聚类结构能通过样本分布的紧密程度确定
- 过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇
- 代表：DBSCAN, OPTICS, DENCLUE
- DBSCAN
- 通过邻域建立样本的可达路径，形成等价类（连通分支）
- 核心对象: 若$x_j$的$\epsilon$邻域至少包含$\mathrm{MinPts}$个样本, 即$|N_\epsilon(x_j)|\geq\mathrm{MinPts}$, 则$x_j$是一个核心对象
- 密度直达: 若$x_j$位于$x_i$的$\epsilon$邻域中, 且$x_i$是核心对象, 则称$x_j$由$x_i$密度直达
- 密度可达: 对$x_i$与$x_j$, 若存在样本序列$p_1,\cdots p_n$,其中$p_1=x_i$, $p_n=x_j$且$p_{i+1}$由$p_i$密度直达, 则称$x_j$由$x_i$密度可达
- 密度直连: 对$x_i$与$x_j$, 若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达, 则称$x_i$与$x_j$密度相连
层次聚类
能够说出思路和代表性算法
- 假设：能够产生不同粒度的聚类结果
- 过程：在不同层次对数据集进行划分，从而形成树形的聚类结构
- 代表：AGNES (自底向上)，DIANA (自顶向下)
- AGNES
- 从最细的粒度开始（一个样本一个簇），逐渐合并相似的簇，直到最粗的粒度（所有样本一个簇）
- 步骤
- Step1: 将每个样本点作为一个簇
- Step2: 合并最近的两个簇
- Step3: 若所有样本点都存在与一个簇中，则停止；否则转到 Step2
第十章: 降维与度量学习
k-近邻学习
知道怎么实现，以及知道它重要的理论性质和现实不可⾏之原因
- 懒惰学习 (lazy learning) 的代表: 事先没有分类器，见到测试样本再开始准备分类器
- 基本思路: 近朱者赤，近墨者黑, 使用投票法
- 性质: 最近邻分离器的泛化错误率 不会超过 贝叶斯最优分类器错误率 的两倍
$$
\begin{align}
P(err) &= 1-\sum_{c\in\mathcal{Y}}P(c|x)P(c|z) \
&\backsimeq 1- \sum_{c\in\mathcal{Y}}P^2(c|x) \
&\leq 1-P^2(c^*|x) \
&= (1+P(c^*|x))(1-P(c^*|x)) \
&\leq 2\times (1-P(c^*|x)) \end{align} $$ - 维数灾难
- 密采样假设: 样本的每个$\epsilon$邻域都有近邻
- 高维空间给距离计算带来很大的麻烦
- 当维数很高时，甚至连计算内积都不再容易
- 样本变得稀疏，近邻容易不准
- 进行降维: 数据样本虽是高维的，但与学习任务相关的仅是某个低维空间，即高维空间中的一个低维“嵌入”
低维嵌⼊
知道 MDS 的思路和能够回答为什么
- 多维缩放方法 MDS
- 思路: 内积保距: 寻找一个低维子空间，使得距离和样本原有距离近似不变
- 技巧: 特征值分解$B=V\Lambda V^T$
- 谱分布长尾：存在相当数量的小特征值, 删除对距离影响不大
流形学习
知道 ISOMAP 和 LLE 是怎么实现（核⼼思路）
- ISOMAP
- 思路: 测地线距离（近似）、保距
- 步骤
- 构造近邻图
- 基于最短路径算法近似任意两点之间的测地线(geodesic)距离
- 基于距离矩阵通过 MDS 获得低维嵌入
- LLE
- 思路: 重构权值
- 为每个样本构造近邻集合$Q_i$
- 为每个样本计算基于$Q_i$的线性重构系数 $$\min_{w_1,…,w_m}\sum_{i=1}^m||x_i-\sum_{j\in Q_i}w_{ij}x_j||_2^2\quad s.t.\quad\sum_{j\in Q_i}w_{ij} = 1$$
- 在低维空间中保持$w_{ij}$不变, 求解下式 $$\min_{z_1,…,z_m}\sum_{i=1}^m||z_i-\sum_{j\in Q_i}w_{ij}z_j||_2^2$$
度量学习
知道度量学习的主要思路——学习参数化⻢⽒距离
距离度量学习: 直接“学出”合适的距离
马氏距离 $$\mathrm{dist}_{mah}^2(x_i, x_j)=(x_i-x_j)^TM(x_i-x_j)=||x_i-x_j||^2_M$$
- $M$为度量矩阵, 对其进行学习
- 欧氏距离的缺陷: 各个方向同等重要
马氏距离目标函数
- 目标 1: 结合具体分类器的性能, 以近邻分类器的性能为目标，则得到经典的 NCA 算法
- 目标 2: 若已知“必连”(must-link)约束集合$\mathcal{M}$ 与“勿连”(cannot-link)约束集合 $\mathcal{C}$，则可通过求解下述凸优化问题得到$M$ $$\min_M\sum_{(x_i,x-j)\in \mathcal{M} }||x_i-x_j||^2_M\quad s.t.\quad\sum_{(x_i,x-j)\in \mathcal{C} }||x_i-x_j||^2_M\geq 1 \ M\succeq 0$$
NCA
- 近邻分类器在进行判别时通常使用多数投票法, 替换为概率投票法. 对于任意样本$x_j$, 它对$x_i$分类结果影响的概率为 $$p_{ij}=\frac{\exp(-||x_i-x_j||^2_M)}{\sum_l\exp(-||x_i-x_l||^2_M)}$$
- 样本的 LOO 正确率 $$p_i=\sum_{j\in\Omega_i}p_{ij}$$
- 训练集上的 LOO 正确率 $$\sum_{i=1}^m p_i=\sum_{j\in\Omega_i}p_{i}=\sum_{i=1}^m\sum_{j\in\Omega_i}p_{ij}$$
- NCA 优化目标 $$M=PP^T$$ $$\min_P 1-\sum_{i=1}^m\sum_{j\in\Omega_i}\frac{\exp(-||P^Tx_i-P^Tx_j||_2^2)}{\sum_l\exp(-||P^Tx_i-P^Tx_l||_2^2)}$$
PCA
PCA 原理和计算
- 思路: 如何使用一个超平面对所有样本进行恰当的表达
- 最近重构性: 样本点到这个超平面的距离都足够近
- 最大可分性: 样本点在这个超平面上的投影能尽可能分开
- 主成分分析的两种等价推导
- 最近重构性
- 对样本进行中心化: $\Sigma_i x_i=0$
- 假定投影变换后得到的新坐标系为${w_i}$, 其中$w_i$是标准正交基向量 $$||w_i||_2=1, w_i^Tw_j=0(i\ne j)$$
- 若丢弃其中的部分坐标, 将维度降低到$d'\lt d$, 则样本的投影是 $$z_i=(z_{i1},…,z_{id'}),z_{ij}=w_j^Tx_i$$
- 基于$z_i$重构$x_i$, 则得到$\hat{x}i=\sum{j=1}^{d'}z_{ij}w_j$
- 优化目标 $$\min_W-\mathrm{tr}(W^TXX^TW)\quad s.t.\quad W^TW=I$$
- 思路: 重构误差
- 最大可分性
- 样本点$x_i$在新空间中超平面上的投影是$W^Tx_i$，若所有样本点的投影能尽可能分开，则应该使得投影后样本点的方差最大化 $$方差=\sum_i Wx_ix_i^TW$$
- 优化目标: 同上
- 思路: 子空间方差
- 求解
- 使用: 拉格朗日乘子法 $$XX^TW=\lambda W$$
- 对协方差矩阵$XX^T$进行特征值分解, 求得的特征值排序, 取最大的$d'$个特征值对应的特征向量组成$W$, 得到解
- $d'$的设置: 用户指定, 交叉验证, 或设置阈值(百分比)
- PCA 是最常用的降维方法，在不同领域有不同的称谓
- 因为若将前$d'$‘个特征值对应的特征向量还原为图像，则得到特征脸
第十一章: 特征选择与稀疏学习
特征选择
定义，动机, 常⻅的⽅法和原理
- 特征: 描述物体的属性
- 相关特征: 对当前学习任务有用的属性
- 无关特征: 与当前学习任务无关的属性
- 冗余特征: 其所包含信息能由其他特征推演出来
- 特征选择: 从给定的特征集合中选出任务相关特征子集, 不丢弃重要特征
- 优势: 减轻维度灾难, 降低学习难度
- 方法: 子集搜索 + 子集评价
- 子集搜索: 用贪心策略选择包含重要信息的特征子集
- 前向搜索：逐渐增加相关特征
- 后向搜索：从完整的特征集合开始，逐渐减少特征
- 双向搜索：每一轮逐渐增加相关特征，同时减少无关特征
- 子集评价
- 思路:
- 特征子集确定了对数据集的一个划分
- 样本标记对应着对数据集的真实划分
- 通过估算这两个划分的差异，就能对特征子集进行评价；差异越小越好
- 用信息熵进行子集评价
- 计算标记划分和特征子集划分之间的信息增益
- 思路:
- 子集搜索: 用贪心策略选择包含重要信息的特征子集
- 常见的特征选择方法
- 过滤式: 先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型；特征选择过程与后续学习器无关
- Relief 方法
- 思路
- 为每个初始特征赋予一个“相关统计量”，度量特征的重要性
- 特征子集的重要性由子集中每个特征所对应的相关统计量之和决定
- 设计一个阈值，然后选择比阈值大的相关统计量分量所对应的特征
- 或者指定欲选取的特征个数，然后选择相关统计量分量最大的指定个数特征
- 相关统计量
- 猜中近邻: 同类样本中的最近邻
- 猜错近邻: 异类样本中的最近邻(多分类时每个其他类找一个)
- 猜对近邻比猜错近邻越近，即属性对区分对错越有用
- Relief 方法的时间开销随采样次数以及原始特征数线性增长，运行效率很高
- 思路
- Relief 方法
- 包裹式: 把最终使用的学习器性能作为特征子集的评价准则
- 目的: 给定学习器选择最有利于其性能、“量身定做”的特征子集
- 优点: 从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好
- 缺点: 需多次训练学习器，计算开销通常比过滤式特征选择大得多
- LVW 包裹式特征选择方法
- 在循环的每一轮随机产生一个特征子集
- 在随机产生的特征子集上通过交叉验证推断当前特征子集的误差
- 进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解
- 嵌入式: 在学习器训练过程中自动地进行特征选择
- 线性回归模型，以平方误差为损失函数，并引入 L2 范数正则化项防止过拟合 $$\min_w \sum_i (y_i-w^Tx_i)^2+\lambda ||w||_2^2$$
- L2 替换为 L1, 得到 LASSO $$\min_w \sum_i (y_i-w^Tx_i)^2+\lambda ||w||_1$$
- 使用 L1 范数正则化易获得稀疏解
- 目标优化的解要在平方误差项与正则化项之间折中,即出现在图中平方误差项等值线与正则化等值线相交处
- L1 范数时, 交点常出现在坐标轴上,即产生一些$w_i$为 0 的稀疏解
- 过滤式: 先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型；特征选择过程与后续学习器无关
稀疏表⽰
动机，基本⽅法的原理
- 动机: 矩阵中有很多零元素，且非整行整列出现
- 优势: 文本数据线性可分, 存储高效
- 字典学习: 普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示
- 给定数据集${x_i}, x_i\in\mathbb{R}^{n\times k}$
- 学习字典矩阵$B\in\mathbb{R}^{d\times k}$以及稀疏表示$\alpha_i\in\mathbb{R}^k$
- $k$称为字典的词汇量，通常由用户指定
- 最简单的字典学习的优化形式为 $$\min_{B,\alpha_i}\sum_{i=1}^m||x_i-B\alpha_i||_2^2+\lambda\sum_{i=1}^m||\alpha_i||_1$$
- 矩阵补全
- 从得到的部分信号, 基于压缩感知的思想恢复出完整信号
- 优化形式: 秩, NP 难问题 $$\min_X \mathrm{rank}(X)\quad s.t.\quad X_{ij}=A_{ij}, (i,j)\in\Omega$$
第十二章: 半监督学习
未标记样本
熟悉
- 潜在假设
- 聚类假设: 假设数据存在簇结构, 同一簇的样本属于同一类别
- 流形假设: 假设数据分布在一个流形结构上, 临近的样本具有相似的输出值
生成式方法
掌握
- 假设样本由高斯混合模型生成, 且每个类别对应一个高斯混合成分 $$\ln_{p}(D_l\cup D_u)=\sum_{(x_j, y_j)\in D_l}\ln(\sum_{i=1}^k\alpha_i\cdot p(x_j|\mu_i,\Sigma_i)\cdot p(y_j|\Theta=i, x_j)) + \sum_{(x_j, y_j)\in D_u}\ln(\sum_{i=1}^k\alpha_i\cdot p(x_j|\mu_i,\Sigma_i))$$
- 高斯混合的参数估计使用 EM 算法求解, 迭代更新
- E 步: 用模型参数计算未标记样本$x_j$属于各个混合成分$i$的概率$\gamma_{ji}$
- M 步: 基于$\gamma_{ji}$更新模型参数
- 拓展: 将高斯混合模型换成混合专家模型, 朴素贝叶斯模型等, 可推到出其他生成式半监督方法
- 优点: 简单, 易于实现
- 缺点: 模型假设必须准确, 否则影响泛化性能
半监督 SVM
掌握
- TSVM: 局部搜索, 迭代寻找近似解
- 有标记样本训练 SVM, 给无标记样本打伪标记, 混入数据继续训练
- 有标记样本训练 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$$
$$
\begin{align}
s.t.\quad & y_i(w^Tx_i+b)\geq 1 - \xi_i, i=1,…,l \
& \hat{y}_i(w^Tx_i+b)\geq 1 - \xi_i, i=l,…,m \
& \xi_i \geq 0 , i=1,…,m \end{align} $$
- 算法
- 用$D_l$训练 SVM, 给$D_u$打标记$\hat{y}$
- 初始化$C_u \lt\lt C_l$, 折中参数, 伪标记不准确
- 循环, 当$C_u \lt C_l$
- 求解上式, 得到$(w,b), \xi$
- 若存在$i,j$, $(\hat{i}\hat{j} \le 0)\wedge(\xi_i \gt 0)\wedge(\xi_j \gt 0)\wedge(\xi_i + \xi_j \gt 2)$, $\hat{i}\hat{j}$均取负, 并重新训练
- $C_u = \min{2C_u, C_l}$
- 问题
- 标记指派可能出现类别不平衡问题: 拆分$C_u$为$C_u^+,C_u^-$
- 搜寻标记指派出错的样本, 涉及巨大计算开销
图半监督学习
掌握
思路: 将数据映射为图
- 相似度对应边, 相似度大小对应边的强度
- 有标记样本有染色, 学习过程对应这些颜色在图上扩散的过程
- 图对邻接矩阵, 基于矩阵运算进行推导
算法
- 构建图亲和矩阵(邻接矩阵), 节点集$V={x_1,…,x_l, x_{l+1}, …, x_{l+u}}$ $$W_{ij} = \exp(\frac{-||x_i-x_j||_2^2}{2\sigma^2}), \mathrm{if}\ i\ne j$$
- 相似的样本应当具有相似的标记, 即得到最优的结果于是定义关于$f$的能量函数, $f:V\to \mathbb{R}$是图学习的结果 $$E(f)=\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^mW_{ij}(f(x_i)-f(x_j))^2 = f^T(D-W)f$$ $$D=\mathrm{diag}(d_i), d_i=\sum_{j=1}^{l+u}(W_{ij})$$
- 换成分块矩阵表示 $$E(f)=f_l^T(D_{ll}-W_{ll})f_l - 2f_u^TW_{ul}f_l + f_u^T(D_{uu})f_u$$
- 通过$\frac{\partial E(f)}{\partial f_u}=0$, 求$f_u$
$$
\begin{align}
f_u &=(D_{uu}-W_{uu})^{-1}W_{ul}f_l \
&=(D_{uu}(I-D_{uu}^{-1}W_{uu}))^{-1}W_{ul}f_l \
&=(I-P_{uu})^{-1}P_{ul}f_l \
P&=D^{-1}W \end{align} $$
适用于多分类的迭代式标记传播方法: 略
优点: 概念清晰, 易于使用矩阵分析探索算法性质
缺点: 存储开销高, 建图仅考虑训练样本集, 难以预知新样本在图中的位置
基于分歧的方法
掌握
- 概念
- 使用多学习器 / 多视图
- 每轮迭代, 每个视图训练出来的学习器, 将最确信样本给其他学习器, 加入下一轮训练
- 优点: 视图充分且条件独立, 则可达到任意高泛化精度
- 缺点: 有标记样本少是时, 不容易做到有分歧
- 变体, 单视图: 不同算法, 不同数据采样, 不同模型参数
- 理论研究: 不一定需要多视图, 只需要弱学习器之间有显著的分歧
半监督聚类
了解
- 获得的监督信息
- 必连, 勿连约束, 参考马氏距离
- 有监督样本: 作为种子, 用他们初始化寻找 k-means 聚类中心
- 约束 k-means
- 聚类过程中确保必连, 勿连约束
- 不冲突, 则选择最近的簇
- 冲突, 则尝试次近的簇