Chapter 0 对偶

对偶问题

考虑最优化目标为：
$$\min\quad f_0(x)$$
$$\text{s.t.}\quad f_i(x)\leq0\quad\forall i=1,\cdots,n$$
$$\quad\quad g_i(x)=0\quad\forall i=1,\cdots,m$$
于是写出拉格朗日函数为：
$$L(x;\lambda,v)=f_0(x)+\sum_{i=1}^n\lambda_if_i(x)+\sum_{i=1}^mv_ig_i(x)$$
由此得到对偶函数为：
$$g(\lambda,v)=\min_{x}L(x;\lambda,v)$$
于是对偶问题为：
$$\min\quad g(\lambda,v)$$
$$\text{s.t.}\quad \lambda_i\geq 0\quad \forall i=1,\cdots,n$$

KKT条件

对于凸优化问题，有：
$$f_i(x)\leq 0,\quad g_i(x)=0,\quad \lambda_i\geq 0,\quad \lambda_if_i(x)=0$$
$$\nabla f_0(x)+\sum_{i=1}^n\lambda_i\nabla f_i(x)+\sum_{i=1}^mv_i\nabla g_i(x)=0$$

Chapter 1 绪论

概念

假设空间：输出向量的向量空间
归纳偏好：在无法断定假设之间的优劣时，模型表现出的倾向性。举例：SVM中假设好的分类器应该最大化类别边界距离、KNN中假设特征空间中相邻的样本倾向于属于同一类

Chapter 2 模型评估与选择

评估方法

留出法：验证集的朴素划分
$k$ 折交叉验证：均分为 $k$ 份，轮流令每一份为验证集、其余为训练集，平均得到结果
自助法：可重复地随机挑选一个样本，加入不可重集合 $S$ 作为验证集；重复 $m$ 次

性能度量

均方误差：$E=\frac1m \sum_{i=1}^m (f(x_i)-y_i)^2$
错误率：$E(f;D)=\frac1m \sum_{i=1}^m \mathbb{I}(f(x_i)\neq y_i)$
精度：$acc(f;D)=1-E(f;D)$
混淆矩阵：$XY$，其中 $X=T/F$ 代表你的分类是否正确，$Y=P/N$ 代表你的分类器输出
查准率：在你判断为 $T$ 的样本中有多少真正为 $T$，$P=\frac{TP}{TP+FP}$
查全率：在所有真正的 $T$ 中你查出来多少，$R=\frac{TP}{TP+FN}$
$F1$ 度量：查准率和查全率的调和平均数，$F1=\frac{2\times P\times R}{P+R}$（$F_\beta=\frac{(1+\beta)\times P\times R}{(\beta^2\times P)+R}$）
宏查准/全率：对于多个混淆矩阵，先计算查准/全率，再取平均
微查准/全率：对于多个混淆矩阵，先加和为一张混淆矩阵，再计算查准/全率
宏/微 $F1$ 度量：使用宏/微查准/全率得到的 $F1$ 值
真正例率：同查全率，$TPR=\frac{TP}{TP+FN}$
假正例率：查全率的反面，$FPR=\frac{FP}{TN+FP}$
$ROC$：纵轴为 $TPR$、横轴为 $FPR$ 的曲线，一般高于 $y=x$；绘制方法：先把分类阈值调到最大使得不存在正例，此时位于原点，然后逐步调低阈值，若出现真正例则 $y$ 增加 $\frac{1}{m^+}$，若出现假正例则 $x$ 增加 $\frac{1}{m^-}$
$AUC$：$ROC$ 曲线下方的面积，面积越大（离 $0.5$ 越远）说明性能越好；从另一个视角考虑：对于每一个正反阈值颠倒的样例给予 $1$ 的处罚、对于每一个正反阈值相等的样例给予 $0.5$ 的处罚，则有：$$l_{rank}=\frac{1}{m^+m^-}\sum_{x^+\in D^+}\sum_{x^-\in D^-}(\mathbb{I}(f(x^+)<f(x^-))+\frac12\mathbb{I}(f(x^+)=f(x^-)))=1-AUC$$

Chapter 3 线性模型

最小二乘法

模型：$y_i=w^\top x_i+b_i$，即 $y=w^\top \mathbf{X}+b$
目标：最小化均方误差
结果：$w^*=(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top y$

对数几率回归

考虑 Sigmoid 函数 $g(x)=\frac{1}{1+e^{-x}}$
模型：$y_i=g^{-1}(w^\top x_i+b_i)=1/(1+\text{exp}(-w^\top x_i-b_i))$
结果由极大似然估计得到，使用迭代法计算

线性判别分析

思想：最小化类内散度、最大化类间散度
类内散度：$S_w = \Sigma_0+\Sigma_1=\sum_{x\in X_0}(x-\mu_0)^\top(x-\mu_0)+\sum_{x\in X_1}(x-\mu_1)^\top(x-\mu_1)$
类间散度：$S_b=(\mu_0-\mu_1)^\top (\mu_0-\mu_1)$
优化目标：$\max J=\frac{w^\top S_b w}{w^\top S_w w}$，不失一般性，可令 $w^\top S_w w=0$

多分类学习

$OvO$：One vs One，对于每两个类别之间均训练一个分类器，共计 $C_n^2$ 个
$OvR$：One vs Rest，分别对于每个类别与其他所有类别之间训练一个分类器，共计 $n$ 个
比较：$OvO$ 的训练开销小，$OvR$ 的存储开销和测试时间小；具体表现看数据
$MvM$：Multiple vs Multiple，每次把一些特征的组合划为正例，另一些划为反例
$ECOC$ 码：对于每一类，规定其在每一个分类器下的期望输出。最终以与类别所期望的输出的汉明距离或欧式距离进行分类

类别不平衡

欠采样：去除一些较多的一类；会使训练数据集变小，有可能丢失重要信息
过采样：多采样较少的一类；可能导致严重的过拟合
阈值移动

Chapter 4 决策树

概念（ps. 这个记号真离谱吧完全没有遵从信息论的约定）

熵：$\text{Ent}(D)=H(D)=-\sum_{x\in D}p(x)\log p(x)$
信息增益（互信息）：$\text{Gain}(D,a)=I(D;a)=H(D)-H(D|a)=\text{Ent}(D)-\sum_{v=1}^V \frac{|D^v|}{|D|}\text{Ent}(D^v)$
增益率：$\text{Gain_Ratio}(D,a)=\frac{\text{Gain}(D;a)}{\text{IV}(a)}=\frac{I(D;a)}{H(a)}$，其中 $H(a)=-\sum_{v=1}^V \frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$
基尼系数：$\text{Gini}(D)=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k\neq k’}p_kp_{k’}=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2$，即随机抽取两个样本其类别不一致的概率
基尼指数：$\text{Gini_index}(D;a)=\mathbb{E}[\text{Gini}(D^v)]=\sum_{v=1}^V \frac{|D^v|}{|D|}\text{Gini}(D^v)$

决策树

$ID3$ 算法：选择信息增益最大的特征
$C4.5$ 算法：选择增益率最大的特征
$CART$ 算法：选择使得划分后基尼系数最小的特征

剪枝

预剪枝：若本次划分后，在本节点处的验证集精度没有严格更优，那么就不进行本次划分
后剪枝：先生成整棵树，然后从叶子节点向上，使用同样的决策方法判断是否剪枝

Chapter 5 神经网络

概念

$MP$ 神经元：接受多个输入 $\mathop{x}\limits^\rightarrow$，接受阈值 $b$ 调控，以权重 $\mathop{w}\limits^\rightarrow$ 线性组合后通过激活函数输出 $y$
多层感知机：神经网络
反向传播
缓解过拟合的方法：正则化、Dropout、数据增强等

Chapter 6 支持向量机

对偶问题的推导过程均略，懒得写主要是

原版SVM

考虑间隔 $\gamma=\frac{2}{|w|}$ 的支持向量机：
$$\min_{w,b}\quad \frac12|w|^2$$
$$\text{s.t.}\quad y_i(w^\top x_i+b)\geq 1$$

软间隔SVM

$hinge$ 损失：$l(z)=\max(0,1-z)$
指数损失：$l(z)=\exp(-z)$
对率损失：$l(z)=\log(11+\exp(-z))$
考虑使用 $hinge$ 损失（线性损失）的软间隔支持向量机：
$$\min_{w,b}\quad\frac12|w|^2+C\sum_{i=1}^m\max(0,1-y_i(w^\top x_i+b))$$
我们允许部分样本不满足 $y_i(w^\top x_i+b)\geq 1$，但是会对不满足的程度施加惩罚。在引入松弛变量后，可以改写为：
$$\min_{w,b}\quad\frac12|w|^2+C\sum_{i=1}^m\xi_i$$
$$\text{s.t.}\quad y_i(w^\top x_i+b)\geq 1-\xi_i,\quad \xi_i\geq 0$$

核函数

思想：考虑修改模型为 $y_i=w^\top \phi(x_i)+b$，则在核函数 $\kappa$ 的意义上定义内积 $\langle \phi(x),\phi(z)\rangle=\kappa(x,z)$
定义：对于定义在 $\mathcal{X}\times\mathcal{X}$ 上的对称函数 $\kappa(\cdot,\cdot)$，其为核函数当且仅当其核矩阵 $\mathbf{K}={\kappa(x_i,x_j)}_{ij}$ 对于任意数据集 $D={x_1,x_2,\cdots,x_m}$ 总是半正定的
线性核/多项式核：$\kappa(x_i,x_j)=(x_i^\top x_j)^d$，其中 $d\geq 1$
高斯核：$\kappa(x_i,x_j)=\exp(-|x_i-x_j|^2/\sigma^2)$，其中 $\sigma>0$
拉普拉斯核：$\kappa(x_i,x_j)=\exp(-|x_i-x_j|/\sigma)$，其中 $\sigma>0$
$\text{Sigmoid}$ 核：$\kappa(x_i,x_j)=\tanh(\beta x_i^\top x_j+\theta)$，其中 $\beta>0,\theta<0$
若 $\kappa_1$ 和 $\kappa_2$ 均为核函数，则其线性组合和直积均为核函数
若 $\kappa_1$ 为核函数，则对于任意函数 $g(x)$，有 $\kappa(x,z)=g(x)\kappa_1(x,z)g(z)$ 为核函数

Chapter 7 贝叶斯分类器

朴素贝叶斯分类器

假设：不同标签之间的分布独立
预测：$P(x\in D)=P(D)\times \prod_{v=1}^V p(x_v|x\in D)$
拉普拉斯修正：给每一类都加一个元素，具体而言，分子 $+1$，分母加类别数

EM算法

考虑 $X$ 为已观测向量集，$Z$ 为隐变量集，$\Theta$ 为模型参数。则 $EM$ 算法的目标为：最大化对数似然函数 $LL(\Theta|X:Z)=\ln Pr[X,Z|\Theta]$
由于隐变量 $Z$ 不可求解，因此考虑最大化边际似然：$\ln \sum_Z Pr[X,Z|\Theta]$
$E$ 步：使用当前参数 $\Theta^t$ 推测 $Z$，并计算对数似然函数对于 $Z$ 的期望：$$Q(\Theta|\Theta^t)=\mathbb{E}_{Z|X,\Theta^t}LL(\Theta|X,Z)$$
$M$ 步：求解使得边际似然函数最大的参数 $\Theta$ 作为 $\Theta^{t+1}$：$$\Theta^{t+1}=\arg\max_\Theta Q(\Theta|\Theta^t)$$

Chapter 8 集成学习

基本思想

使用多个弱学习器组合为一个强学习器
集成个体需要“好而不同”（好：强于随机；不同：多样性）

Boosting

思想：先训练一个学习器，再调整训练样本的分布，使得先前被做错的样本在之后获得更多关注；如此串行迭代得到 $T$ 个学习器，将其加权结合为最终的集成学习器
$AdaBoost$：考虑学习器之间线性加权组合、最小化指数损失

Bagging

思想：使用自助法取出 $T$ 组包含 $m$ 个数据的数据集，分别构建学习器；随后组合答案并输出
随机森林：在 Bagging 的基础上，在构建决策树时，每一次展开只从随机的 $k$ 个类别中进行选择（若 $k=d$ 则与传统决策树无差别）；往往在决策树数量较少时表现较差，这是因为引入了随机的 $k$ 使得其性能下降。另一方面，这也导致决策树之间产生了差异性，使得适合集成学习。

Chapter 9 聚类

距离计算

非负性、同一性（自距离为 $0$）、对称性、直递性（三角不等式）

K-means

先随机选出 $k$ 个点的坐标作为均值向量（分类基点）
按照距离的定义进行聚类
在每个类内分别重新计算，得到 $k$ 个新的均值向量
重复直到收敛

Chapter 10 数据降维

k近邻算法

$1$近邻算法的泛化错误率不超过贝叶斯最优分类器的 $2$ 倍

PCA

目标：最大化投影方差：$$\min_W-\text{tr}(W^\top XX^\top W)\quad \text{s.t.}W^\top W=I$$
算法：中心化、计算协方差矩阵 $C=XX^\top$、取 $C$ 的特征值最大的 $k$ 个特征向量组合为投影向量 $W^*$、使用 $W^*$ 作为 $W$ 的低维替代