机器学习三要素：模型、学习准则、优化算法

贝叶斯公式

最小错误率贝叶斯决策

后验概率 $P(\omega_1 | x) = \dfrac{P(x|\omega_1)P(\omega_1)}{\sum P(x|\omega_j)P(\omega_j)}$
$P(\omega_1)$ ——先验概率， $P(x|\omega_1)$ ——似然概率

最小风险贝叶斯决策

考虑不同决策带来的损失 $R(\alpha_i|x) = \sum \lambda_{ij}P(\omega_j|x)$

ROC曲线

真阳性率TPR~假阳性率FPR

	识别为真	识别为假
正样本	TP	FN
负样本	FP	TN

$TPR = \dfrac{TP}{TP+ FN}$

$FPR = \dfrac{FP}{FP+ FN}$

作用：

确定似然比
比较两种分类判别方法的性能
作为特征与类别相关性的度量
越靠近左上角越好（计算面积——AUC分数）

概率密度函数估计（求解先验概率）

极大似然估计 $\theta$ 是确定的、未知的

原理：使样本集出现的概率最大

步骤：

构造似然函数 $l( \theta ) = \Pi P(x_i|\theta)$
取对数 $\ln l(\theta)$
求偏导，求最大值

非参数估计 $P(x) = \frac{K_N}{NV_N}$

$K_N$ 是 $N$ 个样本落 $V_N$ 的样本数

收敛条件：

$\lim\limits_{N\to\infty}V_N = 0$
$\lim\limits_{N\to\infty}K_N = \infty$
$\lim\limits_{N\to\infty}\dfrac{K_N}{N} = 0$

Parzen 窗口估计法

样本足够多才能有较好估计

对 $V_N$ 作限制，如 $V_N = \dfrac{h}{\sqrt{n}}$
$P_N = \dfrac{1}{N} \sum\limits_{i=1}^N\dfrac{1}{V_N}\varphi (\frac{x-x_i}{h_N})$

$K_N$ 近邻法

$K_N$ 作限制，如 $K_N = \sqrt{N}$ , $V_N = \frac{V_1}{\sqrt{N}}$

线性分类器

设计线性判别函数 $g(x) = w^Tx+ w_0$

Fisher 线性判别分析

思路：类内离散度尽可能小，类间离散度尽可能大

方法：拉格朗日乘数法

准则函数 $J(w) = \dfrac{w^TS_bw}{w^TS_ww}$

步骤：

求均值 $m_i = \dfrac{1}{N}\sum x$
求类内离散度矩阵 $S_i = \sum (x -m_i)(x - m_i)^T$
总类内离散度矩阵 $S_w = S_1+ S_2$

类间离散度矩阵 $S_b = (m_1 -m_2)(m_1 - m_2)^T$
求 $w^* = S^{-1}_w(m_1-m_2)$
求 $w_0 = -\frac{1}{2}w^{*T}(m_1+ m_2)$
判别函数 $g(x) = w^{*T}x + w_0$

感知器

样本线性可分

$y\in w_1$ 时, $g(x)>0$
$y\in w_2$ 时, $g(x)<0$

步骤：

增广化——添加一维并设置为1— $(1,0,1) \to (1,0,1,1)$
规范化 $y' = \left\{\begin{matrix} y &\text{if} ~~~~ y\in w_1 \\ -y &\text{if} ~~~~ y\in w_2 \\ \end{matrix}\right.$
将样本带入 $g(x) = \alpha^T y$ , 若 $g(x) > 0$ 则不变，若 $g(x)<0$ 则修正 $\alpha_{i+ 1} = \alpha_i + \rho y_k$

线性支持向量机

最优分类超平面

能够将训练样本没有错误地分开且两类训练样本中离平面最近的超平面之间的距离最大（分类间隔）

支持向量

决定最优分类超平面的样本

线性回归

单变量线性回归
- 方法：最小二乘法
- 性能评价：均方误差
多元线性回归
- $E(\hat{w})=(Y-X\hat{w})^T(Y-X\hat{w})$
- $\hat{w} = (X^TX)^{-1}X^TY$
- 当逆不存在时，使用岭回归
  - $E(\hat{w})=(Y-X\hat{w})^T(Y-X\hat{w})+\frac{1}{2}\lambda\hat{w}^T\hat{w}$
  - $\hat{w} = (\lambda I+X^TX)^{-1}X^TY$

其他分类方法

K-近邻法(KNN)

在所 $N$ 个样本中找到与测试样 $k$ 个最近邻的样本
选取类别频率最高者作为决策

决策树

内部结点——一个特征

叶子结点——分类

特征值选取

选信息增益最大的属性 $g(D,A) = H(D) - H(D|A)$

决策树生成——使用训练样本

ID3算法
- 计算数据集分类前的熵 $H(D) = -\sum\limits_{k=1}^K\dfrac{|C_k|}{|D|}\log_2{\dfrac{|C_k|}{|D|}}$
- 计算特征A对数据集D的条件熵（子类熵的加权和 $H(D|A)=\sum\limits_{i=1}^n\dfrac{|D_i|}{|D|}H(D_i)$
- 计算信息增益 $g(D,A) = H(D) - H(D|A)$
- 选信息增益最大的属性作为结点
C4.5算法
- 求特征A的熵 $H_A(D) = -\sum\limits_{i=1}^n\dfrac{|D_i|}{|D|}\log_2{\dfrac{|D_i|}{|D|}}$
- 求信息增益率 $g_R(D,A) = \dfrac{g(D,A)}{H_A(D)}$
CART算法
- 尼基系数 $Gini(D) = 1 - \sum(\dfrac{|C_k|}{|D|})^2$
- 选基尼指数最小的特征 $Gini(D,A) = \sum\dfrac{|D_i|}{|D|} Gini(D_i)$

决策树剪枝 ——使用测试样本

预剪枝
- 容易欠拟合
- 从根节点开始
后剪枝
- 从叶子节点开始
判断剪枝后是否正确率是否提升，来决定是否删除该节点

随机森林——构建多个决策树

原理：将样本输入到每个决策树中进行分类，选所有决策中较多决策的结果。

每棵决策树随机选择一个子集进行训练。

特征选择

判据：

基于类内类间距离的可分性判据
基于概率可分的可分性判据
基于熵的可分性判据

分支定界法

从包含所有候选特征开始，自顶向上，逐步去掉不被选中的特征。
要求：判据对特征具有单调性，某节点函数值小于B直接回溯

特征提取

基于类别可分性判据的特征提取

求最优的变换矩阵 $w^*$ $w^{*}$ ,使可分性判据 $J(x)$ $J (x)$ 最大
- 求均值 $m_i = \dfrac{1}{N}\sum x$
- 类内离散度矩阵 $S_i = \sum\limits_{i-1}^C P_i\sum\limits_{k=1}^{n_i} (x^i -m_i)(x^i - m_i)^T$
  类间离散度矩阵 $S_b = \sum\limits_{i-1}^C(m_1 -m)(m_1 - m)^T$
- 求 $A = S_w^{-1}S_b$
- 求特征值并按从大到小排序
- 求 $A$ 的特征向量
- 选取 $d$ 个作为新的特征 $W=[x_1,x_2,\cdots,x_d]$
主成分分析法
K-L变换（主成分分析的监督实现）
- 求产生矩阵
  - 类别未知
    
    $\varphi=E\left[x x^T\right]$
    
    $\varphi=E\left[(x-\mu)(x-\mu)^T\right]$ ——PCA方法
  - 类别已知
    
    $\varphi =S_w = \sum\limits_{i=1}^CP_iE\left[(x^i-\mu_i)(x^i-\mu_i)^T\right]$
  - 后续同第一点

非监督——无标签样本分类

动态聚类算法——c均值算法
分级聚类
- 初始化每个样本形成一个类
- 计算两类之间的距离——定义类间距离（最近、最远、均值）
- 选择最小距离的两类进行合并

多分类问题

多对多
- 对每类样本编码，并比较测试样本与其的距离，选取距离最小者的类别为分类结果
一对一
- 训练多个二分类器投票决定
一对多
- 预测是否为 $C_i$

HMM（隐马尔可夫）模型

三要素：

初始状态分布 $\pi$
状态转移矩阵 $A$
观测概率矩阵 $B$

两个基本假设

齐次马尔可夫性假设
系统在任意时刻 $t$ 的隐藏状态 $q_t$ 只依赖于其前一时刻的隐藏状态 $q_{t−1}$ ，与更早的状态及观测值无关。
观测独立性假设
任意时刻t的观测值 $O_t$ 仅依赖于该时刻的隐藏状态 $q_t$ ，与其他时刻的隐藏状态或观测值无关。

三个基本问题

计算问题：求观测 $P(O|\lambda)$
学习问题：只有观察数据求模型
解码问题：求状态 $P(I|O,\lambda)$

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。