PRML总复习

[TOC]

TODO：

Chapter 2

五步：数据获取，预处理，特征提取与选择，学习器设计，应用部署

机器学习：从样本集学习一个假设$f(x)$使得$f(x)$是问题世界模型$F(x)$的一个近似。

kNN

略

解决过拟合

获取更多数据
调整模型选择(比如加一些惩罚)

经验误差，泛化误差

前者是在训练集上，后者是在测试集上；前者反映问题难易和学习器拟合能力，后者反映模型对未知数据的预测能力。样本足够多时，两者趋于一致。

经验误差大，泛化误差也大：欠拟合

经验误差小，泛化误差大：过拟合

构建验证集

验证集作用：帮助选择模型，确定参数超参数

留出法
交叉验证(分K个也叫K折交叉验证)
自助法(不中概率趋向于$\frac{1}{e}$)

性能度量

回归：均方误差；分类：错误率与准确率

PR曲线

查准率： \[ P = \frac{TP}{TP+FP} \] 查全率： \[ R = \frac{TP}{TP+FN} \] 可以根据这个绘制P-R曲线。曲线越靠右上角越好

ROC曲线

真正例率(TPR) = 灵敏度 \[ \frac{TP}{TP+FN} \] 假正例率(FPR) = 1 - 特异度 \[ \frac{FP}{FP+TN} \] FPR为横轴，TPR为纵轴可绘制ROC曲线，越靠近左上角越好

两者关系

在样本不均衡情况下，ROC曲线保持不变，适合对学习器整体评估

PR曲线聚焦于正例，受影响比较大，适合对正例率敏感的问题

两者在空间上存在对应关系

实际应用

在问题中，定义 \[ AP = \int P(r)dr \]

体现准确度。

在语义分割任务中，通过IoU来体现

泛化误差的理论分析

可以证明泛化误差： \[ E(f;\mathcal{D}) = var(x) + bias^2(x) + \varepsilon^2 \] 分解为方差、偏差与噪声之和。

偏差：刻画学习算法本身拟合能力

方差：刻画数据扰动造成的影响

噪声：刻画学习问题本身的难度

欠拟合时，偏差大，通常方差也大

过拟合时，方差很大

三个经典原理

没有免费的午餐：不存在某种算法对所有问题都有效
丑小鸭定理：分类标准是主管定义的，评估与问题定义关联
奥卡姆剃刀定理：PRML系统不应选择比“必要”更复杂的系统

Chapter 3

线性模型

形式化 \[ f(x) = w_1x_1 + w_2x_2 + \cdots + w_dx_d + b \] 向量表示 \[ f(x) = w^Tx + b \] 我们讨论回归任务和分类任务。

回归任务：（基于最小平方误差准则）

一元线性回归
多元线性回归

分类任务：

线性判别分析(二/多分类) （基于Fisher准则）
感知机（基于感知机准则）
Logistic回归， Softmax回归

一元线性回归

试图学习： \[ f(x_i) = wx_i +b\;\;使得\;\;f(x_i)\approx y_i \] 定义损失函数 \[ E_{(w,b)} = \sum_{i=1}^n (y_i -wx_i -b)^2 \] 分别对$w, b$求导令其为0，解得 \[ w = \frac{\sum_i y_i (x - \bar{x})}{\sum_i x_i^2 - \frac{1}{n}(\sum_{i}x_i)^2} \]

\[ b = \frac{1}{n}\sum_i (y_i - wx_i) \]

多元线性回归

试图学习： \[ f(x_i) = W^T x_i + b = w_1x_{i1} + \cdots + w_dx_{id} + b \] 表示成矩阵 \[ X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \\ \vdots & & \ddots & & \vdots \\ x_{n1} & x_{n2} & \cdots & x_{nd} & 1 \end{pmatrix} \]

\[ \hat{W} = (w;b) \]

\[ y = (y_1; y_2; \cdots ;y_n) \]

则有 \[ y = X\hat{w} \] 定义损失函数 \[ E_{\hat{W}} = (y-X\hat{W})^T(y-X\hat{W}) \] 对$W$求导，可得 \[ 2X^T(X\hat{W} - y) = 0 \] 若$X^TX$满秩，则有 \[ \hat{W}^* = (X^TX)^{-1}X^Ty \]

如果出现非满秩矩阵情况，说明存在多个最优解
面对多个最优解，可以加入正则化，如L1, L2

广义线性回归

如果有很明显的非线性关系，可以考虑 \[ g(y) = w^Tx + b \] 则有 \[ y = g^{-1}(w^Tx+b) \] 比如可以取$g(\cdot) = \ln(\cdot)$, 则有 \[ y = e^{w^Tx+b} \]

接下来看看分类问题

Logistic回归

回顾广义线性模型，令$g^{-1}(z) = \frac{1}{1+e^{-z}}$，则有 \[ y = \frac{1}{1+e^{-(w^Tx+b)}} \] 将$y$视为$x$属于正类的概率$p(y=1|x)$，则有 \[ p(y=1|x) = \frac{e^{w^Tx+b}}{1+e^{w^Tx + b}} \] 对于二分类，可以用二值交叉熵来作为损失函数 \[ J(w) = -\frac{1}{n}\sum_{i=1}^n \left[y_i \ln{p(y=1|x_i)}+(1-y_i)\ln{(1-p(y=1|x_i))}\right] \] 为了便于讨论，令$\hat{x} = (x;1)\;\;\beta = (w;b)$，则有$w^Tx+b = \beta^T\hat{x}$，则 \[ p_1(\hat{x};\beta) = p(y=1|\hat{x};\beta) = \frac{e^{\beta^T\hat{x}}}{1+e^{\beta^T\hat{x}}} \] 则 \[ J(\beta) = -\frac{1}{n} \sum_{i=1}^n [y_i\ln{p_1(\hat{x_i};\beta)+(1-y_i)\ln{(1-p_1(\hat{x_i};\beta)}})] \]

梯度下降法

\[ \beta^{t+1} = \beta^{t} - \eta \frac{\partial J(\beta)}{\partial \beta} \]

其中 \[ \frac{\partial J(\beta)}{\partial \beta} = -\sum_{i=1}^n \hat{x_i}[y_i - p_1(\hat{x_i};\beta)] \]

牛顿法

\[ \beta^{t+1} = \beta^t - (\frac{\partial^2J(\beta)}{\partial\beta\partial\beta^T})^{-1}\frac{\partial J(\beta)}{\partial\beta} \]

Softmax回归

适用于多分类问题

描述$x$属于第$y = j$类的概率： \[ p(y = j|x;W) = \frac{e^{w_j^Tx + b_j}}{\sum_{k=1}^ce^{w_k^T+b_k}} \] 同样的，为了方便 \[ \hat{x_i} = (x_i;1) \\ \hat{w_j} = (w_j;b_j) \\ W = [\hat{w_1}, \hat{w_2}, \cdots , \hat{w_c}] \] 则有 \[ w_j^T x + b_j = \hat{w_j^T} \hat{x}\\ p_j(\hat{x};\hat{W}) = p(y=j|\hat{x};\hat{W}) = \frac{e^{\hat{w}_j^T\hat{x}}}{\sum_{k=1}^c e^{\hat{w}_k^T\hat{x}}} \]

\[ f(\hat{x}; \hat{W}) = \frac{1}{\sum_{k=1}^c e^{\hat{w}_k^T\hat{x}}} \begin{bmatrix} e^{\hat{w}_1^T\hat{x}} \\ \vdots \\ e^{\hat{w}_c^T\hat{x}} \end{bmatrix} \]

将交叉熵函数作为损失函数： \[ J(\hat{W}) = -\frac{1}{n} \sum_{i=1}^n \left[\sum_{j=1}^c\delta(y_i = j)\ln{p_j(\hat{x_i};\hat{W}})\right] \] 可以用SGD来求解

线性判别分析(Fisher判别分析)

LDA

基本思想：设法将样例投影到一条直线上，使得同样样例的投影点尽量接近，不同类的互相远离

$X_i, n_i, \mu_i, S_{w_i}$分别表示第i类样本的集合、样本数、均值、类内散度

两类为例，想要：

使得类内散度尽可能小，即$w^TS_{w_0}w+w^TS_{w_1}w$尽可能小
使得类间离散度尽可能大，即 $||w^T\mu_0 - w^T\mu_1||_2^2$尽可能大

最大化目标函数： \[ J = \frac{||w^T\mu_0 - w^T\mu_1||_2^2}{w^TS_{w_0}w+w^TS_{w_1}w} \] 简化计算 \[ J = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(S_{w_0}+S_{w_1})w} \] 定义类间散度矩阵 \[ S_b =(\mu_0-\mu_1)(\mu_0-\mu_1)^T \] 定义类内散度矩阵 \[ S_w = S_{w0} + S_{w1} = \sum_{x\in w_0}(x-\mu_0)(x-\mu_0)^T + \sum_{x\in w_1}(x-\mu_1)(x-\mu_1)^T \] 则最大化目标 \[ J = \frac{w^TS_bw}{w^TS_ww} \] 用拉格朗日乘子法计算计算计算，最后得到 \[ w = S_w^{-1}(\mu_0-\mu_1) \] 多分类LDA

有n个类

定义全局散度矩阵$S_t$，类内散度矩阵$S_w$，类间散度矩阵$S_b$

最大化目标函数： \[ J(W) = \frac{\Pi_{diag}W^TS_bW}{\Pi_{diag}W^TS_WW} = \Pi_{i=1}^k \frac{w_i^TS_bw_i}{w_i^TS_ww_i} \]

感知器准则

目标：把两类分开，利用线性判别函数 \[ g(x) = w^Tx + b \] 增广向量：$y_i = (1;x_{i1}; \cdots ; x_{id})$, $a = (b; w_1;\cdots;w_d)$

则有 \[ g(y) = a^Ty \] 定义线性可分性：

存在权向量$a$ 使得 \[ \forall y \in w_1 \Rightarrow a^Ty >0 \\ \forall y \in w_2 \Rightarrow a^Ty < 0 \] 则为线性可分

规范化，让所有属于$w_2$的$y$取相反数，这样所有的元素都要$a^Ty>0$

这样可以得到解向量$a$的一个解空间，越靠近解区中间越准确。下面定义损失函数 \[ J_P(a) = \sum_{y\in Y} (-a^Ty) \] 其中$Y$为错分样本的集合

利用SGD更新参数： \[ a_{k+1} = a_k - \eta_k\frac{\partial J_P(a)}{\partial a } = a_k + \eta_k \sum_{y\in Y_k}y \] 也有几个不同的更新方法：

固定增量的单样本修正方法每次只考虑一个错分样本$y^k$, 改写为$a_{k+1} = a_k + y^k$
可变增量单样本修正方法 $a_{k+1} = a_k + \eta_ky^k$

[这边可以出计算题]

多分类问题

几个方法

每次只保留两类，训练一个分类器
每次处理一个类别时，把其他所有类别看作一类
可以把几个看作一类，几个看作一类进行分类

类别不平衡问题

阈值移动

认为若$\frac{y}{1-y} > \frac{m^+}{m^-}$则预测为正样本

或者说，比较时缩放：$\frac{y'}{1-y'} = \frac{y}{1-y}\times \frac{m^-}{m^+}$

如果正样本数量过少

过采样：增加正例
欠采样：去除一些负例
数据增广：对正例进行一些变换而不改变语义

Chapter 4

从线性到非线性

之前提到过的：广义线性。但是拟合能力弱，泛化性不强。
分段线性：简单，多个超平面适应性强。但是依赖手工设计。

将提出:

神经网络
SVM

神经网络

MP神经元

最经典的神经元模型，略

Hebb学习规则

核心思想：突触前神经元$j$向突触后神经元$i$的重复持续的刺激可以导致突出传递效能增加，即$j$到$i$的权值得到加强 \[ \Delta w_{ij} = \eta a_j o_i \] $a_j$ 为突触前神经元输入值，$o_i$为突触后神经元输出值

单层感知机

之前介绍过，不赘述。

可用于处理与或非的问题，不能处理异或问题。

多层前馈神经网络

每层与下一层全连接，在网络拓扑上不存在环与回路

万有逼近定理：单一隐层，任意宽度，使用S型函数作为激活函数的前馈神经网络，可以以任意精度来近似任何从一个有限维空间到另一个有限维空间的Borel可测函数

误差反向传播算法（BP）

常见神经网络

前馈神经网络
反馈神经网络
循环神经网络
RBF网络径向基函数网络，用一个径向基函数作为隐层神经元激活函数。比如高斯径向基函数

\[ R(x-c_i) = \exp{(-\frac{1}{2\sigma^2}||x-c_i||^2)} \]

LeNet5 典型的卷积神经网络，手写识别
Hopfield网络属于反馈神经网络，提供了一个理解人类记忆的模型，有联想记忆的功能
Boltzmann机基于能量的模型，为网络定义能量，能量最小化达到理想状态
Elman网络针对语音处理，具有局部记忆单元和局部循环连接的循环神经网络
LSTM 长短期记忆网络
SOM网络自组织映射网络：竞争学习类型的无监督神经网络输出是一个二维的神经元网格，输入代表真实世界的模式。可以用于求解旅行商问题
级联相关网络结构自适应网络。将网络结构作为训练目标之一，开始只有输入输入层，后面逐渐加入新的隐层结点从而创建层级结构

SVM

Chapter 5

概率模型

一些概率论的基础不再赘述，看一眼多元高斯密度函数 \[ p(x) = \frac{1}{(2\pi)^{d/2} |\Sigma|^{1/2}}e^{[-\frac{1}{2} (x-\mu)^T\Sigma^{-1}(x-\mu)]} \] 其中$\mu$为均值， $\Sigma$为协方差

贝叶斯分类器

贝叶斯决策理论

\[ p(w|x) = \frac{p(x|w)p(w)}{\sum_wp(w, x)} \]

最小错误贝叶斯决策

\[ minP(e) = \int P(e|x)p(x)dx \]

一些定义：

第一类错误率 $\alpha = \frac{FP}{FP+TN}$ 假阳
第二类错误率 $\beta = \frac{FN}{FN+TP}$ 假阴
灵敏度 $S_n = \frac{TP}{FN+TP} = 1-\beta$ 真阳中检测出多少阳
特异度 $S_p = \frac{TN}{FP+TN} = 1-\alpha$ 真阴中检测出多少阴

##### 最小风险贝叶斯决策

定义对于实际状态为$w_j$的样本，采取策略$a_i$带来的损失为$\lambda(a_i, w_j)$

对于每一个样本x，期望损失为 \[ R(a_i| x) = \sum_{j = 1}^c \lambda(a_i, w_j)p(w_j|x) \] 为了最小化决策期望损失$R(a) = \int R(a(x)|x)p(x)dx$

只要对每一个样本最小化$R(a_i|x)$

判别函数

线性判别函数： $g_i(x) = w_i^Tx +w_{i0}$

对于二分类问题，若$g_1(x) \ge g_2(x)$则认为属于第一类，否则属于第二类。称$g(x) = g_1(x) - g_2(x)$确定的平面为决策面

现在回到原来的贝叶斯决策分类器，看最小错误率决策，那么我们以广义似然度作为判别函数： \[ g_i(x) = p(x|w_i)p(w_i) \] 其正比于后验概率。

类似的，也可以采用对数似然的形式简化计算： \[ g_i(x) = \log{p(x|w_i)} + \log{p(w_i)} \] 分类决策： \[ arg\max_i\;g_i(x) \]

正态分布下的判别函数

TODO

概率密度函数估计

贝叶斯决策目的是计算最大后验概率，但是先验概率和类条件概率不一定知道。要通过样本估计

估计概率密度函数：

参数方法
非参数方法

估计有效性：需要样本充足，能代表样本的真实分布，独立同分布

参数估计

最大似然估计
贝叶斯估计

最大似然估计

样本D \[ L(\theta) = p(D|\theta) = p(x_1, \cdots, x_N|\theta) = \Pi_{i=1}^np(x_i|\theta) \]

\[ \hat{\theta} = argmax_{\theta}p(D|\theta) \]

\[ l(\theta) = \sum_{i=1}^N \ln{p(x_i|\theta)} \]

求最大值，求导为0即可。

高斯情况下的最大似然估计：

TODO

贝叶斯估计

记$\lambda(\hat\theta, \theta)$为估计的损失，条件风险为$R(\hat{\theta}|x) = \int \lambda(\hat{\theta}, \theta)p(\theta|x)d\theta$

在平方损失函数下，可以证明 \[ \hat{\theta} = \int \theta p(\theta|D)d\theta \] 流程：

求先验分布$p(\theta)$
求联合分布$p(D|\theta) = \Pi_{i=1}^Np(x_i|\theta)$
求$\theta$后验概率分布$p(\theta |D)$
计算$\hat{\theta} = \int \theta p(\theta|D)d\theta$

高斯情况下的贝叶斯估计：

TODO

非参数估计

直方图方法

N个样本，把$x$分成$k$个等间隔小窗，形成$k^d$个小舱，小舱体积为$V$

统计进入小舱的样本数$q_i$

相应小窗的概率密度为$\frac{q_i}{NV}$

随着样本数增加，小舱体积应该尽可能小，但是小舱内有充分多样本，这些样本是所有样本中很小的一部分。

换个样子写： \[ \hat{p}(x) = \frac{k}{NV} \] $V$为指定的区域，$k$为区域中样本数。选取合适的$k, V$

Parzen 窗法：固定V，变化k
K-近邻法：固定k，变化V

朴素贝叶斯分类器

贝叶斯公式后验概率： \[ P(c|x) = \frac{p(c)p(x|c)}{p(x)} \] 想象x是很多属性，c是某个最终判定的类别。所有属性的联合概率难以直接从训练样本估计，为了简化假设它们独立 \[ P(c|x) = \frac{P(c)}{P(x)}\Pi_{i=1}^d P(x_i|c) \] 其中 \[ P(c) = \frac{|D_c|}{D}, P(x_i|c) = \frac{|D_{c, x_i|}}{D_c} 或 P(x_i|c) = \frac{1}{\sqrt{2\pi} \sigma_{c, i}}e^{(-\frac{(x_i - \mu_{c, i})^2}{2\sigma_{c, i}^2})} \] TODO：看看书里的例题

拉普拉斯修正： \[ P(c) = \frac{|D_c|+1}{D+1}, P(x_i|c) = \frac{|D_{c, x_i}|+1}{D_c + N_i} \]

半朴素贝叶斯分类器

考虑一部分属性之间的相互关系。假设各属性在类别之外最多只依赖于一个其他属性。 \[ P(c|x) 正比于 P(c)\Pi_{i=1}^dP(x_i|c,pa_i) \] 确定各个属性的父属性的方法：

SPODE 假定各属性都依赖于同一属性（超父），再通过模型选择确定最终超父属性
TAN 通过两属性条件互信息反映相关性强弱，继而保留相关属性之间的依赖性
AODE 与SPODE相比不进行模型选择，采用集成各种模型的思路

TODO：计算

贝叶斯网

有向无环图模型，节点表示随机变量，箭头表示因果关系

贝叶斯方法延展

贝叶斯决策和贝叶斯估计都基于贝叶斯定理，解决不同问题。贝叶斯决策的任务是学习一个分类器，贝叶斯估计的目的是学习概率模型中的参数。

过拟合的时候，可以考虑引入正则化。

最大似然估计：参数的值看作给定量，只是不知道

贝叶斯估计：参数也看成随机变量

决策树（没写完）

定义：一种非参数监督的分类与回归方法，推理过程与人类进行分类的机制类似，根据对象属性分情况进行讨论

对于一个样本，决策树的推理过程对应于一条从根节点到某一叶节点的路径，也即一个判定测试序列。

if-then 序列，互斥且完备。将特征空间划分为矩形平行区域

优点：易于理解，可以处理离散连续数据，层次反映信息量，需要数据少
缺点：不稳健，数据变化造成结构大幅改变，贪心算法不能保证返回最优决策树，用分段近似不平滑不连续

决策树的生成是一个递归问题，三个终止条件。

属性选择：

根据信息增益

\[ Gain(D,x) = H(D) - H(D|x) \]

根据信息增益率

\[ GainRatio(D, A) = \frac{Gain(D, A)}{IV(A)}\\ IV(A) = -\sum_{v=1}^V \frac{|D^v|}{|D|}\log{\frac{|D^v|}{|D|}} \]

信息增益率对可取值数目较小比较小的属性有所偏好。为了避免过度偏好，C4.5算法启发式：先从候选划分属性中找出信息增益高的，再选信息增益率高的。

基尼指数

基尼值：(越小纯度越高) \[ Gini(D) = \sum_{k=1}^{|y|}p_k(1-p_k) = 1-\sum_{i=1}^{|y|}p_k^2 \] 基尼指数：(约小划分性能越好) \[ GiniIndex(D,a) = \sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v) \] 可以看作信息熵的一阶泰勒近似

剪枝的思想：

预剪枝

生成过程中判断当前节点划分后能否提升决策树泛化能力。不能，停止划分，标记为叶节点

后剪枝

先训练为完整的树，自底向上对非叶节点考察，若将该节点对应的子树替换为叶节点能提升泛化性能，则替换

都用留出法来评估

优点：降低过拟合风险，减少训练时间和测试时间开销

缺点：可能有欠拟合风险

后剪枝比预剪枝条保留了更多分支，欠拟合风险小，泛化性能往往更好，但是后剪枝训练时间开销更大

对于连续值的处理：

二分法处理

若有n个不同的取值：

候选划分点：n-1个，取中间值
计算各个划分点信息增益
选取信息增益最大的为最终划分点

对于属性缺失情况的处理：

训练时缺失：

给定划分属性，若样本在该属性上缺失——按照概率划分到不同分支

划分属性时：计算信息增益要给缺失的加一个权重(就相当于之前的概率)让它影响变小

测试时缺失：

根据训练样本的统计分布决定放到哪个分支

概率图模型

概率图模型是一类用图来表示变量间因果或相关关系的概率模型，按图的结构可分有向图、无向图模型。

隐马尔可夫模型：关于时序的生成式有向图模型，建模观测序列和状态序列的联合分布
马尔可夫随机场：生成式无向图模型，联合概率可分解为所有极大团势函数乘积
条件随机场：判别式无向图模型，看作给定观测值条件下的马尔可夫随机场，建模的是给定观测值下的条件分布
精确推理
- 变量消去：无向图模型，两两向量当作极大团
- 信念传播：无环概率图模型，先从叶节点到根节点传递消息，再从根节点到叶节点传递消息
近似推理
- 采样法：比如拒绝采样
- 变分法：用简易分布近似复杂的真实分布
话题模型：生成式有向图模型，主要处理离散数据的集合

Chapter 6

集成学习

Bagging

\[ H(x) = \frac{1}{T}\sum_{t=1}^Th_t(x) \]

自助采样法得到数据，训练，而后各个弱分类器投票得到结果 \[ H(x) = arg\max_{y\in \mathcal{Y}}\sum_{t=1}^T 1(h_t(x) = y) \] 包外估计：

用训练好的模型估计没有采样到的数据的结果，用结果来计算泛化误差的估计

随机森林

自助采样样本和属性，构建不同的决策树形成森林，最后决策为各个决策树投票的结果

回顾之前的：偏差大意味着欠拟合，方差大意味着过拟合。Bagging算法可以降低方差。

Boosting

\[ H(x) = \sum_t \alpha_t h_t(x) \]

通过迭代更新训练样本的权重分布。对弱分类器重新加权得到强分类器，串行生成。

重点介绍Adaboost算法

训练集：$D = {(x_1, y_1), , (x_N, y_N) } $ 其中$y_i \in \mathcal{Y} =\{-1, +1 \}$

初始化训练数据权重分布$D_1 = (w_{11}, \cdots, w_{1i}, \cdots, w_{1n})$，其中$w_{1i} = \frac{1}{n}$

对于$t = 1, 2, \cdots, T$:

选择一个弱分类器$h_t(x)$

\[ h_t(x) = arg\min_{h_j\in H}[\varepsilon_j = \sum_{i=1}^nw_{t,i} \cdot 1[y_i \ne h_j(x_i)]] \]

也就是说从弱分类器中选错误率最小的一个作为初始的分类器

$\alpha_t = \frac{1}{2}\log{(\frac{1-\varepsilon_t}{\varepsilon_t})}$ 也就是说错的约多$\alpha$越小
$w_{t+1,i} = \frac{w_{t, i}\exp{(-\alpha_ty_ih_t(x_i))}}{Z_t}$, $Z_t = \sum_{i=1}^Nw_{t,i}\exp{(-\alpha_ty_ih_t(x_i))}$ 也就是说，某个样本已经被分得越好，权重越小

最后输出 \[ H(x) = \sum_t \alpha_t h_t(x) \] 此算法可以降低偏差。

TODO：算算例题

Stacking

常见的结合策略有：简单平均、加权平均、绝对多数投票法、相对多数投票法、加权投票法

接下来介绍学习法。

应用实例：

TODO

Chapter 7

无监督学习

聚类问题
降维问题
生成式问题

无监督聚类

k均值聚类算法

思想：首先随机初始化聚类中心，而后不断更新聚类中心、更新聚类样本直到收敛

有N个样本，K个类别。定义准则函数 \[ J = \sum_{i=1}^K \sum_{x\in C_i} ||x-\mu_i||^2 = \sum_{i = 1}^N \sum_{k=1}^K r_{ik}||x-\mu_i||^2 \] 其中$r_{ik}$表示$x_i$属于第$k$个聚类。

第一步，初始化$\mu_k$, 按照最优化准则产生$r_{ik}$
第二步，根据$r_{ik}$按照最优化准则产生$\mu_k = \frac{\sum_i r_{ik}x_i}{\sum_{i}r_{ik}}$
第三步，根据$\mu_k$产生新的$r_{ik}$

k值选择：找拐点

优点：高效，迭代收敛

缺点：k要指定，无法处理噪声和离群数据，不利于非凸数据

TODO：做例题

学习向量化方法

有标签，但是不一定准确

LVQ 算法

样本$D = \{(x_1, y_1), \cdots, (x_N, y_N) \}$, 每个样本由n个属性描述：$(x_{j1}; x_{j2}; \cdots;x_{jn})$

输出：学习一组n维原型向量$p_1, p_2, \cdots, p_q$每个原型向量代表一个聚类簇，簇标记为$t_i$

准则函数： \[ J = arg\min_{0\le i\le q} ||x-p_i||^2 \] 关键步骤：

对于每个样本$x_j$找到最接近的原型$p_i$

若两点相同，把$p_i$拉向$x_j$ : $p_i' = p_i +\eta (x_j - p_i)$
两点不同，相反：$p_i' = p_i -\eta (x_j - p_i)$

TODO: 做例题

高斯混合聚类算法（不会）

（？？？）

层次化聚类算法

有两种方法

自顶向下：从单个集群的所有数据开始，考虑将集群一分为二的所有可能方法选择最好的划分，对两边递归操作。
自底向上：从样本自己的集群中开始，找到最好的一对以合并到一个新的集群之中。重复直到所有的簇融合在一起

以自底向上为例：

初始化：每个样本为一簇
合并：计算任意两簇之间距离，最小的合并，记录
重复

簇划分：可以手动选择阈值

密度聚类

聚类结构不是球状时，基于聚类的算法聚类效果不好

密度聚类：基于密度的聚类，假设聚类结构能通过样本分布的紧密程度来确定

典型算法：DBSCAN

若一个点的$\varepsilon$邻域包含至少$MinPts$个样本，则称其为一个核心点
密度直达（不对称）
密度可达（不对称）
密度相连（对称）

DBSCAN算法: 从核心对象出发，找到所有密度可达的构成簇。重复。

优点：对噪声、离群点鲁棒，可以构成非凸簇

缺点：多超参敏感，不适用一个簇内多密度情况

降维学习

维度灾难：增加维度，所需训练样本数量呈指数级增加，否则过拟合

线性方法
- PCA
- LDA
非线性方法
- 保留局部特征
  - 重建权值LLE
  - 邻接图LE
  - 切空间Hession LLE
- 保留全部特征
  - 基于距离
    - 基于欧氏距离MDS
    - 基于测地线距离ISOMAP
  - 基于核
    - 核PCA

主成分分析（PCA）

是一种无监督的数据降维技术，是数据从高维空间到低维子空间的正交投影变换，使得投影数据的方差最大化频率。

通过线性变化，使得一组正交向量来表示原特征，新的特征向量是原特征向量的线性组合，转换后这组向量叫做主成分。

核心思想：

降维后方差尽量大
降维后数据均方误差尽可能小

在相关性最强的方向建立坐标。

线性判别分析

Fisher判别

核Fisher判别：将样本通过核函数映射到新的特征空间中

流形学习

低维流形嵌入到了高维空间，在局部上仍然具有欧氏空间的性质

多维尺度变换MDS：找到一个低维空间使得样本间的距离和在高维空间中的基本一致

等距映射ISOMAP：引入测地距离。保持测地距离

局部线性嵌入LLE：给定数据集，通过最近邻等方式构造一个数据图，然后在每一个局部区域，高维空间中样本线性重构关系在低维空间中均得以保持

拉普拉斯特征映射LE：在高维空间中距离近的点在低维空间中也近，LE将问题转化为求解图拉普拉斯算子的广义特征值问题

Chapter 8

半监督

有一些有标注的数据和大量无标注的数据

半监督学习：让学习器不依赖外界交互、自动地利用未标记样本来提升模型的学习性能

三大假设：

平滑假设
聚类假设
流形假设

归纳式半监督学习：学习一个函数来适用于训练过程中未观察到的数据

直推式半监督学习：学习一个函数来预测训练集中未标记样本的数据

自训练方法

得到有标记数据$\mathcal{L} = \{(x_i, y_i)\}$, 无标记数据$\mathcal{U} = \{y_i\}_{j=l+1}^{l+u}$，训练出一个模型
用模型预测无标记数据，得到伪标签
选择伪标记中置信度较高的，认定为有标记
循环

评价：构成分离的簇，置信度较高的往往正确；正确标记大多样本才能提升精度，否则可能错上加错

半监督生成方法

假设所有数据都是一个潜在的模型生成的，比如高斯混合模型
根据最大化后验概率来预测每个样本的标签
通过期望最大化(EM)迭代更新高斯混合模型的参数
不断迭代到收敛

评价：要求对数据分布做出假设，可以被视为一种软标签的自训练方法，所有无标记数据都被用来更新模型

半监督支持向量机

试图找到将两类标记分开且穿过数据低密度区域的超平面

著名方法：TSVM

利用有标记样本学得一个SVM
对未标记数据进行标记指派，将预测结果作为伪标记
求出新的划分超平面和松弛向量
找两个标记不同且很有可能出错的，交换
重新求解更新后划分超平面和松弛向量
增大未标记样本的重要性来提高影响
重复3-6直到重要程度一致

基于图的半监督学习

构建连接相似样本的图结构，根据边的权重，将标签赋予图中未标记的节点

亲和矩阵，权重大表示两个标签相同

可以定义能量函数，最后实现标记传播。

基于图的半监督学习属于直推学习，但是新增测试样本无法直接预测标签，需要归纳式半监督学习。可以通过引入正则化，允许偏离真实标签，惩罚偏离程度。(流形正则化问题)

概念上很清晰
计算开销大

基于分歧的方法

借助学习器之间的“分歧”来利用未标记数据

协同学习：多个学习器互相学习共同进步

基本假设：

数据拥有两个充分且条件独立的视图(充分：每个视图包含足以产生最优学习器的信息；条件独立：给定类别标记下两个视图独立)
不同视图有相容性(相容性：不同视图包含的关于输出空间的信息是一致的)

例如：网页中，文字和图片的关系

一起训练，都觉得之心度高，就从伪标注样本中去除

评价：简单有效，适用范围广。但是要使用这个方法，需要显著分歧的学习器，在有标记样本少、数据没有多视图时难以做到

Chapter 9

特征提取与选择

LBP特征

看一个3x3，以中间为基准，不考虑强度绝对值，只考虑相对大小。写成0，1，以左上角为起始位置，每个3x3可以写成8位二进制编码。

拓展：可以把3x3推广到任意邻域

解决旋转不变性：循环将每个位置作为起始点编码，选取编码最小的作为最终结果

考虑多尺度：取一块块的区域，区域内像素取均值，以块为单位来比较

减少编码空间：用跳变数区分，大大减少编码空间

SIFT特征

尺度不变特征。检测图像的关键点用以表征和匹配成对的图像。应当与位置、光照、噪声等无关。

检测关键点位置——通过尺度金字塔DoG
精细化关键点位置——过滤低对比度点、边缘点
计算关键点方向——统计得到区域主方向
计算关键点描述子——堆叠多个元胞方向直方图

特征选择

避免维度灾难
降低计算代价
排除无关干扰
降低学习难度

提升选择特征的效率：

更高效的特征子集评价方式，避免完整交叉验证
更高效特征子集搜索方式，避免枚举遍历全部子集

评价指标

基于距离的：类内散度小，类间距离大
基于信息熵：信息熵越小，越容易区分

特征搜索战略

迭代搜索（不断寻找更好的特征子集划分，直到达到要求或限制）

贪心
- 前向搜索：每次都从剩下的特征中搜索选择一个最佳的
- 后向搜索：每次从已选特征中排除一个最差的，直到满足条件
- 双向搜索：每次加入若干特征同时剔除若干特征

贪心搜索不一定是全局最优解

随机
- 遗传算法：以染色体适应度为概率选择个体，进行交叉、变异，直到满足条件

综合方法

将评价指标与搜索策略相结合

过滤式特征选择与学习器学习独立如Relief 选取指定个数的最大相关统计量的特征或选取相关度高于一定阈值的特征与猜中近邻的距离小则相关统计量大，与猜错近邻的距离大则相关统计量大优点：复杂度正比于采样数、样本数、特征维度，效率高不足：只能处理两类问题拓展到多分类：猜中近邻为相同样本最近邻，猜错近邻为每一不同类别样本最近邻
包裹式特征选择与学习器关联，直接利用学习器的性能作为特征子集评价准则如LVW。随机产生特征子集，交叉验证评估特征子集质量，选择是否接受（性能更好或者性能一样但是维度更低）优点：直接用目标分类器评估，量身定做缺点：代价比较高
嵌入式

特征选择与学习器融为一体，可以同时优化——自动舍弃不对的。还可以用正则项来约束经典方法：LASSO L1范数更容易获得稀疏解(画图可以理解)

老师说的重点

基本概念，概念间的关系

重要的人和事，华人

理论流派。

几个技术的背景知识，跟设计题有关。

系统层面的模式识别和机器学习的定义

五个环节要考，数据获取预处理特征提取选择学习器设计部署

模型的评估与选择：经验误差泛化误差的意义

知道为什么要做模型评估与选择，构建验证集，3个方法

性能度量：常见任务，混淆矩阵，PR，ROC

泛化误差的方差偏差的分解

小结中的结论要掌握

计算题：SVM，聚类

线性模型的评价策略，概念

优势：简单，可解释性强，是通往非线性模型的基础。

模型的评价策略：最小平方误差准则，Fisher准则，感知机准则，其他准则（logistic，softmax）

机器学习三要素，优势劣势

三要素：模型，策略，算法。模型：定义函数集合。策略：函数拟合评价。算法：最优函数选择。

评价策略：三个策略

logistic，softmax，线性判别：概念要知道。

线性判别分析的核心思想优化目标，如何扩展到多分类和非线性

核心思想：投影到一条直线上，同类尽可能接近，不同尽可能原理

类内散度要小，类间距离要大

拓展到多分类: 不只是投影到直线，而是一个超平面(???)

思想和优势要掌握

线性不可分什么的不考了

历史还是在第一章）

感知机是重点，能干什么不能干什么，优缺点，万有逼近

可以与或非不能异或

万有逼近：单一隐层，任意宽度，用S型函数作为激活函数的前馈神经网络可以用任意精度近似任何一个从有限维空间到另一个有限维空间的Borel可测函数（有阶梯函数、连续函数、分段连续函数等等）

BP了解下就好

常见神经网络需要掌握。

MP，Hebb(突触增强)

前馈：RBF网络(径向基函数作为激活函数)。LeNet:卷积神经网络

反馈：Hopfield网络(记忆，可以将输入图片和记忆图片关联) 波尔兹曼机(基于前者，能量，随机递归神经网络)

循环：LSTM，Elman网络(局部记忆和局部循环)

其他：SOM(竞争学习，无监督，旅行商)，级联相关网络

给你一个模型一段描述是不是合理。前馈反馈什么的对应什么模型，不同的网络解决了什么问题有什么结构

支持向量机要计算，例题中选一个。如果是对偶问题会给参考公式。不会考核

核函数的思想要知道，但是不会考计算

思想：将低维样本映射到高维空间。而且映射只以内积形式出现，所以可以直接设计核函数

核函数：将两个d维样本映射为一个实数值的对称连续函数

多分类：成对，一对多

5.1不考

最小错误率和最小风险掌握啥掌握怎么算

5.2.2概率密度函数估计只需要了解

5.2.3了解一下

169页的总结要看

一开始是概率模型，结合了先验知识和预测后，贝叶斯决策。如果难以获得先验概率和类条件概率，则用概率密度估计。

认为不同属性条件概率独立：朴素贝叶斯。至多允许和一个属性相关：半朴素贝叶斯。考虑更多属性的因果关系：贝叶斯网络。

判别模型：线性模型，回归，神经网络，svm，决策树，boosting

生成模型：高斯模型，贝叶斯学习，直方图，Parzen窗，knn，隐马尔科夫，混合高斯

决策树要考，和随机森林的关系要知道

信息论什么的了解

概率图模型大题里面不考

为什么要做集成学习？

集成学习：通过构建并结合多个个体学习器(弱分类器)完成学习任务。流程：按照特定策略训练一组弱分类器，再通过某种策略将其结合形成强分类器

集成简单分类器获得更好效果。单一模型的偏差较大

学习器结合的三大好处：

统计上：假设空间大，减少单一学习器误选导致的泛化性能不佳

计算上：降低进入局部极小点的风险

表示上：结合多个学习器扩大假设空间，进行更好的近似

三个方法，异同

bagging：个体学习器之间不存在强依赖关系，可同时生成的并行化方法。自助采样，投票。可以用包外估计。可以降低方差。每个学习器都相对较强。

boosting：个体学习器之间存在强依赖关系，需要串行生成的序列化方法。每个学习器可以很弱。学习一个弱分类器、对其加权、根据错误率调整样本分布，循环，最终根据加权获得强分类器。可以降低偏差。

stacking：个体学习器的输出作为特征输入到次级分类器

要求：个体学习器要好而不同。准确性，多样性

bagging 和 boosting的差别：

样本选择：前者独立后者依赖于上一次结果

样本权重：前者均匀，后者调整

预测函数：前者权重相等，后者不等

并行：前者是，后者否

偏差方差：前者降低方差后者降低偏差

弱分类器和强分类器的概念要掌握

弱分类器：识别错误率小于1/2，就是说只比随机猜测强一点

强分类器：识别准确率很高而且能在多项式时间内完成的分类器

随机森林要考，和决策树的区别

随机森林：属于bagging。随机自助采样样本和属性，构造很多决策树基分类器。用多棵决策树来生成最后的输出结果

adaboost了解思想

误差率越小的分类器最终占比越大，误分类样本将在下一轮中起更大作用

bagging和boosting的区别什么的总结

stacking的策略

训练初级学习器，输出作为样例输入特征形成新的数据集，训练次级学习器

K-means 或层次化计算

19页无监督学习和监督学习对比

监督学习：目标明确，需要带标签的训练数据，基于标签计算准确率

无监督学习：目标不明确，不需要带标签的训练数据，基于任务设计特定估计指标

聚类的目标：分别朝两个方向最优化

将数据集D中样本划分成几个通常不相交子集，簇内相似度高，簇间相似度低

聚类的性能好坏的度量：掌握

定义度量距离。簇内平均距离，簇内最远距离，簇间最近距离，簇间中心距离

DB：簇内方差和/每个簇质心之间的距离

Dunn：不同集群个例最小距离/集群内最大距离

外部指标：Jaccard，FM，Rand

常用聚类方法要了解，列举，知道思想

高斯混合聚类不考计算题！

给点，推断一下

DBSCAN 概念有缺点

优点：噪声、离群点鲁棒，形成非凸簇

缺点：多超参数敏感，不适合一簇内多种密度情况

降维：PCA，LDA

维度灾难的定义，核心思想

数据量一定的情况下，特征维度超过一定值的时候，分类器的效果反而下降

另一方面，增加特征维度，为了覆盖训练样本同样的特征范围、防止过拟合，所需训练样本数量呈指数增长

方式：特征选择，降维

PCA要掌握

PCA是一种线性方法。无监督数据降维，从高维投影到低维使得1. 方差尽可能大 2. 均方误差尽可能小

为了这样，要选择最大的特征值

步骤：

对数据集中心化并求出协方差矩阵S

求S的特征值特征向量

特征值从大往小排，前M个对应的特征向量构成投影矩阵W

输出这个投影矩阵

总结：

优点：基于特征向量，不需要参数训练，不用迭代，不会陷入局部最优

缺点：仅限二阶统计量，仅限线性投影

LDA

类内散度小，类间离散度大

核：将样本通过核函数映射到新的特征空间中，再对样本做fisher判别分析。

流形学习：了解基本概念

通过非线性投影将高维数据降低到低维非线性结构。

流形具有在局部与欧氏空间同胚的空间，能用欧式距离来计算。因此低维流形嵌入到了高维空间在局部上仍然有欧氏空间的性质

MDS：找到一个低维空间使得样本间的距离在高维和低维基本一致

优点：计算容易不用先验知识，保持数据距离

缺点：数据量大时计算慢，无法区分各个维度重要性

127页总结要重点关注

半监督学习

和无监督学习的区别。

有标记无标记。有标记远少于无标记

三大假设是什么。

平滑，聚类，流形

几个学习方法了解一下就好。重点看86页总结

半监督学习背景：极少标注

归纳式直推式对比

三大假设

学习方法：自训练，生成，svm，图，分歧(多个学习器，利用数据不同视图)

重点。

LBP，SIFT 特点，优缺点

LBP

利用相邻像素提取稳定特征可以进行8位编码

进阶：扩展到任意邻域，旋转不变性(循环选择起始点，选编码最小的)，多尺度(整块的平均，当作一个大像素)，等价模式(跳变次数来编码)

总结：光照不变形——仅考虑相对强度；尺度、旋转不变性——多尺度、循环编码

优点：计算速度快效率高缺点：太简单，鲁棒性差

SIFT：手工设计的关键点检测特征

检测图像的关键点，用以表征和匹配成对图像

要点：显著点、位置无关、光照噪声鲁棒

检测关键点位置：提取尺度金字塔，通过极大极小值检测比较DoG值(高斯核卷积出来的)判断是否是局部极大/极小值

精细化关键点位置：为去除低对比度关键点，二阶泰勒展开，更新。为去除边上关键点，用hessian矩阵找边缘点

计算关键点方向：计算点的梯度，做直方图统计，得到区域主方向。

计算关键点描述子：特征点附近2x2元胞窗口，统计每个的梯度直方图，旋转到主关键点方向。归一处理得到结果

优点：鲁棒，旋转、光照、尺度不变性

缺点：复杂，调参极多，难以穷尽各种变换的差异

我们希望的目标：鲁棒，变换不变，区分性强，计算复杂度低

特征选择的重要性：掌握。

对于特征好坏的评价标准要了解

搜索策略了解一下

综合方法要考，概念和思想

在上面

C10

10.2网络优化的方法要掌握

#notes

[Review] PRML

http://jamil-yu.github.io/2023/06/12/PRML/

Author

Jamil Yu

Posted on

June 12, 2023

Licensed under

[Record] 服务器使用记录1 Previous

[Record] 在Ubuntu22.04上配置qt5.12.3 Next