模式识别领域关注的是利⽤计算机算法自动发现数据中的规律，以及使⽤这些规律采取将数据分类等⾏动。而为了实现这一个目的，首先需要一些基础的理论知识，本文参考自《模式识别与机器论文》第一章，介绍模式识别的三类基础知识：概率论、决策论与信息论。
1 概率论
在模式识别领域的⼀个关键概念是不确定性的概念。它可以由测量的误差引起，也可以由数据集的有限⼤⼩引起。
- 乘法规则和加法规则：
$$
Sum\ rual:\ p\left( X \right) = \sum_{Y}^{}{p\left( X,Y \right)}
$$
$$
\ Product\ rual:\ p\left( X,Y \right) = p\left( Y\mid X \right)p\left( X \right)
$$
其中，$p\left( X,Y \right)$ 是联合概率，$p\left( Y\mid X \right)$是条件概率。
- 贝叶斯定理：
$$
p\left( Y\mid X \right) = \frac{p\left( X\mid Y \right)p\left( Y \right)}{p\left( X \right)} = \frac{p\left( X\mid Y \right)p\left( Y \right)}{\sum_{Y}^{}{p\left( X\mid Y \right)p\left( Y \right)}}
$$
先验概率与后验概率：$p\left( Y \right)$为先验概率，$p\left( Y\mid X \right)$称为后验概率，这是观察了$X$的结果后对$Y$的估计。
- X和Y 相互独⽴：
$$
p\left( X,Y \right) = p\left( X \right)p\left( Y \right)
$$
1.1 概率密度
- 概率密度函数：
$$
p\left( x \in \left( a,b \right) \right) = \int_{a}^{b}{p\left( x \right)\mathrm{d}}x
$$
满足$p\left( x \right) > 1$,$\ \int_{- \infty}^{+ \infty}{p\left( x \right)\mathrm{d}}x = 1$
- 随机变量的非线性变化$x = f\left( y \right)$：
$$
p_{y}\left( y \right) = p_{x}\left( x \right)\left| \frac{\mathrm{d}x}{\mathrm{d}y} \right| = p_{x}\left( g\left( y \right) \right)\left| g^{‘}\left( y \right) \right|
$$
- 累计分布函数：
$$
P\left( z \right) = \int_{- \infty}^{z}{p\left( x \right)\mathrm{d}}x
$$
联合概率密度：$x$为一个向量
运算规则：加和规则、乘积规则、贝叶斯规则
1.2 期望与协方差
- 期望：加权平均：
$$
E\left\lbrack f \right\rbrack = \sum_{x}^{}{p\left( x \right)f\left( x \right)}
$$
$$
E\left\lbrack f \right\rbrack = \int_{}^{}{p\left( x \right)f\left( x \right)\mathrm{d}}x
$$
- 估计：
$$
E\left\lbrack f \right\rbrack \simeq \frac{1}{N}\sum_{n = 1}^{N}{f\left( x_{n} \right)}
$$
- 条件期望：
$$
E_{x}\left\lbrack f\mid y \right\rbrack = \sum_{x}^{}{p\left( x\mid y \right)f\left( x \right)}
$$
- 方差度量了$f\left( x \right)$在均值附近变化的大小：
$$
\text{var}\left\lbrack f \right\rbrack = E\left\lbrack \left( f\left( x \right) - E\left\lbrack f\left( x \right) \right\rbrack \right)^{2} \right\rbrack = E\left\lbrack f\left( x \right)^{2} \right\rbrack - E\left\lbrack f\left( x \right) \right\rbrack^{2}
$$
- 协方差度量两个随机变量的关联性：
$$
c\text{ov}\left\lbrack x,y \right\rbrack = E_{x,y}\left\lbrack { x - E\left\lbrack x \right\rbrack}{ y - E\left\lbrack y \right\rbrack} \right\rbrack = E_{x,y}\left\lbrack \text{xy} \right\rbrack - E\left\lbrack x \right\rbrack E\left\lbrack y \right\rbrack
$$
协方差矩阵：
已知了数据$X$，每一行为一个样本，每一列为一个随机变量$c_i$，协方差矩阵：
$$
\text{covMatrix} = \frac{1}{m - 1}\begin{bmatrix}
\text{cov}\left( c_{1},c_{1} \right) & \text{cov}\left( c_{1},c_{2} \right) & \cdots & \text{cov}\left( c_{1},c_{n} \right) \
\text{cov}\left( c_{2},c_{1} \right) & \text{cov}\left( c_{2},c_{2} \right) & \cdots & \text{cov}\left( c_{2},c_{n} \right) \
\vdots & \vdots & \vdots & \vdots \
\text{cov}\left( c_{n},c_{1} \right) & \text{cov}\left( c_{n},c_{2} \right) & \cdots & \text{cov}\left( c_{n},c_{n} \right) \
\end{bmatrix} = \frac{1}{m - 1}X^{T}X
$$
补充 ：方差的估计中，为什么除以$n - 1$:
首先，对于全体样本，方差的计算中除以$n$；但是在用一组样本对总体进行估计时，由于均值本身就是通过估计得到的，因此自由度$- 1$，所以为了得到无偏估计，方差计算中除以$n - 1$。
1.3 贝叶斯概率
$$
p(\mathbf{w} \mid \mathcal{D}) = \frac{p(\mathcal{D} \mid \mathbf{w})p(\mathbf{w})}{p(\mathcal{D})}
$$
在观察到数据之前，我们有⼀些关于参数$w$的假设，这以先验概率$p\left( w \right)$的形式给出。观测数据$D$的效果可以通过条件概率$p(\mathcal{D} \mid \mathbf{w})$表达，其中$p(\mathcal{D} \mid \mathbf{w})$叫做似然函数，表达了在不同的参数向量$w$下，观测数据可能出现的大小。似然函数的负对数被叫做误差函数，
1、频率学派vs贝叶斯学派：
| 频率学派 | 贝叶斯学派 | |
|---|---|---|
| 参数估计 | 参数虽然未知，但是存在客观的固定值 | 参数本身是随机变量，先假定一个先验分布后通过后验修正 |
| 代表方法 | 最大似然：$w$的值是使似然函数$p(D!w)$最⼤值的$w$ | 最大后验：$w$的值是使似然函数$p(w!D)$最⼤值的$w$ |
| 优缺点 | 缺点：方差估计比真实值小 | 优：包含先验概率； 缺：但是先验概率的选择通常是为了计算的⽅便，造成结果不准 |
| 例子（曲线拟合） | 目标函数为平方和 | 目标函数为正则化的平方和 |
1.4 高斯分布
$$
\mathcal{N}\left( x \mid \mu,\sigma^{2} \right) = \frac{1}{\left( 2\pi\sigma^{2} \right)^{\frac{1}{2}}}\exp\left{ - \frac{1}{2\sigma^{2}}(x - \mu)^{2} \right}
$$
其中，$\beta = \frac{1}{\sigma^{2}}$称为精度。向量的高斯分布：
$$
\mathcal{N}(\mathbf{x} \mid \mathbf{\mu},\mathbf{\Sigma}) = \frac{1}{(2\pi)^{\frac{D}{2}}}\frac{1}{|\mathbf{\Sigma}|^{\frac{1}{2}}}\exp\left{ - \frac{1}{2}(\mathbf{x} - \mathbf{\mu})^{T}\mathbf{\Sigma}^{- 1}(\mathbf{x} - \mathbf{\mu}) \right}
$$
维数为$D$，$\sum_{}^{}{}$为协方差矩阵。
1.5 重新考察曲线拟合问题
假定给定x，t满足高斯分布：
$$
p(t \mid x,\mathbf{w},\beta) = \mathcal{N}\left( t \mid y(x,\mathbf{w}\mathbf{),}\beta^{- 1} \right)
$$
最大先验：
$$
p(\mathbf{t} \mid \mathbf{x},\mathbf{w},\beta) = \prod_{n = 1}^{N}\mspace{2mu}\mathcal{N}\left( t_{n} \mid y\left( x_{n},\mathbf{w} \right),\beta^{- 1} \right)
$$
取对数，分别求解$w,\beta$，得到在⾼斯噪声的假设下，平⽅和误差函数是最⼤化似然函数的⼀个⾃然结果；确定⾼斯条件分布的精度参数$\beta$后即可得到概率分布的预测分布：
$$
p\left( t \mid x,\mathbf{w}{\text{ML}},\beta{\text{ML}} \right) = \mathcal{N}\left( t \mid y\left( x,\mathbf{w}{\text{ML}} \right),\beta{\text{ML}}^{- 1} \right)
$$
最大后验：
引⼊在多项式系数$w$上的先验分布：
$$
p(\mathbf{w} \mid \alpha) = \mathcal{N}\left( \mathbf{w} \mid \mathbf{0},\alpha^{- 1}\mathbf{I} \right) = \left( \frac{\alpha}{2\pi} \right)^{\frac{M + 1}{2}}\exp\left{ - \frac{\alpha}{2}\mathbf{w}^{T}\mathbf{w} \right}
$$
$\beta$是分布的精度，$M\ + \ 1$是对于$M$阶多项式的向量$w$的元素的总数。
采用贝叶斯定理，$w$的后验概率正⽐于先验分布和似然函数的乘积：
$$
p(\mathbf{w} \mid \mathbf{x},\mathbf{t},\alpha,\beta) \propto p(\mathbf{t} \mid \mathbf{x},\mathbf{w},\beta)p(\mathbf{w} \mid \alpha)
$$
最终计算得到，最大后验等价于：
$$
\frac{\beta}{2}\sum_{n = 1}^{N}\mspace{2mu}\left{ y\left( x_{n},\mathbf{w} \right) - t_{n} \right}^{2} + \frac{\alpha}{2}\mathbf{w}^{T}\mathbf{w}
$$
即：最⼤化后验概率等价于最⼩化正则化的平⽅和误差函数
1.6 贝叶斯曲线拟合
⼀个纯粹的贝叶斯⽅法中，我们应该⾃始⾄终地应⽤概率的加和规则和乘积规则。
2 维数灾难
我们用输入数据将空间切分为无数个单元格，预测类别的时候，我们⾸先判断它属于哪个单元格，然后我们寻找训练集中落在同⼀个单元格中的训练数据点，测试点的类别就是测试点所在的单元格中数量最多的训练数据点的类别。但是为了保证单元格不空，我们所需要指数级的训练数据。
在多项式拟合中，对于D个输入变量，三阶多项式形式为：
$$
y\left( \mathbf{x},\mathbf{w} \right) = w_{0} + \sum_{i = 1}^{D}\mspace{2mu} w_{i}x_{i} + \sum_{i = 1}^{D}\mspace{2mu}\sum_{j = 1}^{D}{w_{\text{ij}}x_{i}x_{j}} + \sum_{i = 1}^{D}\mspace{2mu}\sum_{j = 1}^{D}\mspace{2mu}\sum_{k = 1}^{}\mspace{2mu} w_{\text{ijk}}x_{i}x_{j}x_{k}
$$
参数的数量随着$D^{3}$的速度增加，因此实际使用中不方便。
此外，高纬空间中的球体的大部分体积都汇聚在表面附近的薄球壳上。⾼维空间产⽣的这种困难有时被称为维度灾难（curse of dimensionality）。
在模式识别中，这种问题并不能阻止我们寻找适用于高纬空间的有效技术。原因有两⽅⾯。第⼀，真实的数据经常被限制在有着较低的有效维度的空间区域中，特别地，在⽬标值会发⽣重要变化的⽅向上也会有这种限制。第⼆，真实数据通常⽐较光滑（⾄少局部上⽐较光滑），因此⼤多数情况下，对于输⼊变量的微⼩改变，⽬标值的改变也很⼩，因此对于新的输⼊变量，我们可以通过局部的类似于插值的技术来进⾏预测。
3 决策论
推断（inference）：从训练数据集中确定$p\left( x,t \right)$。
决策（decision）：对t采取预测或者采取一定的动作。
3.1 最⼩化错误分类率
为了尽可能的减少分类错误率，我们使用一个规则将输入空间切分成不同的区域$R_k$，这种区域被称为决策区域，每个区域$R_k$中的点被分到$C_k$类中。我们的目的是为了减少错误分类率，假设有两类：
$$
\begin{matrix}
p(mistake) = p\left( \mathbf{x} \in \mathcal{R}{1},\mathcal{C}{2} \right) + p\left( \mathbf{x} \in \mathcal{R}{2},\mathcal{C}{1} \right)
= \int_{\mathcal{R}{1}}^{}\mspace{2mu} p\left( \mathbf{x},\mathcal{C}{2} \right)d\mathbf{x} + \int_{\mathcal{R}{2}}^{}\mspace{2mu} p\left( \mathbf{x},\mathcal{C}{1} \right)d\mathbf{x} \
\end{matrix}
$$
为了使得上式最小，需要最小化两个积分，因此，对于给定的x值，如果$\mathbf{p}\left( \mathbf{x}\mathbf{;}\mathbf{C}\mathbf{1} \right)\mathbf{>}\mathbf{p}\left( \mathbf{x}\mathbf{;}\mathbf{C}\mathbf{2} \right)$，那么就把x分类到$\mathbf{C}_{\mathbf{1}}$中。根据乘积规则$p\left( \mathbf{x};Ck \right) = p\left( Ck|\ \mathbf{x} \right)p\left( \mathbf{x} \right)$，也就等价于分到后验概率最大的类别中。
对于更一般的情况同理，最终也是得到，每个x应该被分到有着最大后验概率的类别中。
3.2 最小化期望损失
对于一些问题，我们的目标不单纯是最小化错误分类的数量，而是要考虑每种错误分类的情况下，可能造成的损失。例如把没有患癌症的病人分为有癌症，肯定比把患癌症的病人分为没有癌症的损失来的大，此时我们的目标是最小化期望损失。
假设对于新的x的值，真实的类别为$$C_k$$，我们把x分类为$$C_j$$（其中j可能与k相等，也可能不相等）。这样做的结果是，我们会造成某种程度的损失，记作$$L_{kj}$$，它可以看成损失矩阵（loss matrix）的第$k,j$个元素。损失函数为
$$
\mathbb{E}\lbrack L\rbrack = \sum_{k}^{}\mspace{2mu}\sum_{j}^{}\mspace{2mu}\int_{\mathcal{R}{j}}^{}\mspace{2mu} L{\text{kj}}p\left( \mathbf{x},\mathcal{C}_{k} \right)d\mathbf{x}
$$
3.3 拒绝选项
当$p(C_k | \mathbf{x})$的值近似时，难以做出正确的选择，此时可以设置一个阈值$\theta$，拒绝后验概率$p(C_k\ |\ \mathbf{x})$的最大值小于等于$\theta$的那些输入x。
令$x = 1$会使所有的样本都被拒绝，⽽如果有k个类别，那么令$x\ < \ 1/K$将会确保没有样本被拒绝。
3.4 决策和推断
我们已经把分类问题划分成了两个阶段：推断（inference）阶段和决策（decision）阶段。在推断阶段，我们使⽤训练数据学习$p\left( C_{k} \middle| x \right)$的模型。在接下来的决策阶段，我们使⽤这些后验概率来进⾏最优的分类。另⼀种可能的⽅法是，同时解决两个问题，即简单地学习⼀个函数，将输⼊x直接映射为决策。这样的函数被称为判别函数（discriminant function）。
三种不同的⽅法来解决决策问题:
- 生成式模型：
⾸先对于每个类别$C_{k}$，独⽴地确定类条件密度$p(x| C_k)$。这是⼀个推断问题，然后，推断先验类概率$p | C_k )$，之后，使⽤贝叶斯定理：
$$
p\left( \mathcal{C}{k} \mid \mathbf{x} \right) = \frac{p\left( \mathbf{x} \mid \mathcal{C}{k} \right)p\left( \mathcal{C}_{k} \right)}{p(\mathbf{x})}
$$
求出后验概率。或者先求出联合概率密度$p\left( \mathcal{C}_{k},\mathbf{x} \right)$，在进行归一化最后得到后验概率，得到后验概率后采用决策论进行判别。通过取样，可以人为生成输入空间的数据。
- 判别式模型：
⾸先解决确定后验类密度$p\left( C_{k} \middle| x \right)$这⼀推断问题，接下来使⽤决策论来对新的输⼊x进⾏分类。直接对后验概率建模。
- 判别函数
这个函数把每个输⼊x直接映射为类别标签，例如对于二分类问题，f直接输出等于0或1，此时概率不起作用。
| 决策问题的方法 | 描述 | 优缺点 | 例子 |
|---|---|---|---|
| 生成式模型 | 先定先验$p(x!C_k)$再确定后验$p(C_k!x)$，最后判别 | 需要求解的东西最多； 能够通过公式求出数据的边缘概率密度$p(x)$，用于检测模型中具有低概率的新数据点 | 朴素贝叶斯，隐马尔可夫模型 |
| 判别模型 | 直接定后验$p(C_x!x)$，最后判别 | LR，SVM，FNN | |
| 判别函数 | 直接计算$f(x)$得到结果 | 得到不后验概率；不能进行最小化风险，拒绝选择，补偿先验概率，以及模型组合 | 线性判别函数 |
3.5 回归问题的损失函数
前面用分类问题讨论了决策论，后面看一下回归问题的损失函数。对于每个x，有一个估计y(x)，对应的损失为L，期望损失：
$$
\mathbb{E}\lbrack L\rbrack = \iint L(t,y(\mathbf{x}))p(\mathbf{x},t)d\mathbf{x}dt
$$
回归问题常损失一般为平方损失：$L(t,y(\mathbf{x})) = { y(\mathbf{x}) - t}^{2}$，对于任意的y(x)，采用变分法解方程，最终得到的$\mathbf{y}(\mathbf{x}) = \mathbb{E}_{t}\lbrack\mathbf{t} \mid \mathbf{x}\rbrack$，即最⼩化了期望平⽅损失的回归函数y(x)由条件概率分布$p\left( t \middle| x \right)$的均值给出。或者我们也可以直接展开上式，最终得到：
$$
\mathbb{E}\lbrack L\rbrack = \int{ y(\mathbf{x}) - \mathbb{E}\lbrack t \mid \mathbf{x}\rbrack}^{2}p(\mathbf{x})d\mathbf{x} + \int\text{var}\lbrack t \mid \mathbf{x}\rbrack p(\mathbf{x})d\mathbf{x}
$$
也是有三种方法解决回归问题：
⾸先解决确定联合概率密度p(x, t)的推断问题，之后计算条件概率密度p(t | x)，最后求均值
直接确定条件概率密度p(t |x)，然后求均值
直接从训练数据中寻找⼀个回归函数y(x)
和分类时相同。
4 信息论
信息量：
对于一个随机变量，信息量的意思是学习x的值时候的惊讶程度，也就是x越小信息量越大（不确定性越强）；信息量的表达式：
$$
h(x) = - \log_{2}p(x)
$$
2为底的时候，单位是bit，e为底的时候单位是nat。
- 熵：衡量随机变量的不确定性大下的，在0.5的时候熵最大，等于0或1时候最小。
$$
H\lbrack x\rbrack = - \sum_{x}^{}\mspace{2mu} p(x)\log_{2}p(x)
$$
- KL散度（相对熵）：描述两个变量之间的区别大小的，当两个分布相同时，散度为0。
$$
\begin{matrix}
\text{KL}(p \parallel q)& = - \int p(\mathbf{x})\ln q(\mathbf{x})d\mathbf{x} - \left( - \int p(\mathbf{x})\ln p(\mathbf{x})d\mathbf{x} \right) \
& = - \int p(\mathbf{x})\ln\left{ \frac{q(\mathbf{x})}{p(\mathbf{x})} \right} d\mathbf{x} \
\end{matrix}
$$
- 互信息：由于知道了y值造成的x的不确定性的减少：
$$
= - \iint_{}^{}{p\left( \mathbf{x},\mathbf{y} \right)l\operatorname{n}{\left( \frac{p\left( \mathbf{x} \right)p\left( \mathbf{y} \right)}{p\left( \mathbf{x},\mathbf{y} \right)} \right)d}}\mathbf{x}d\mathbf{y}
$$
$$
= H\left\lbrack \mathbf{x} \right\rbrack - H\left\lbrack \mathbf{x}\mid\mathbf{y} \right\rbrack = H\left\lbrack \mathbf{y} \right\rbrack - H\left\lbrack \mathbf{y}\mid\mathbf{x} \right\rbrack
$$