[模式识别与机器学习] 非线性分类器

1283 字

6 分钟

[模式识别与机器学习] 非线性分类器

2026-06-17

模式识别与机器学习

模式识别

/

机器学习

距离函数#

欧氏距离#

d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}

曼哈顿距离#

d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^n |x_i - y_i|

明氏距离#

d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{1/p}

马氏距离#

d(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x} - \mathbf{y})^T \mathbf{\Sigma}^{-1} (\mathbf{x} - \mathbf{y})}

$\mathbf{\Sigma}$ ：协方差矩阵，反映数据的分布和相关性
$\mathbf{\Sigma}=\mathbf{I}$ 时，马氏距离退化为欧氏距离
Cholesky分解： $\mathbf{\Sigma} = \mathbf{L}\mathbf{L}^T$ ， $\mathbf{L}^{-1}\mathbf{x}$ 的欧氏距离等价于 $\mathbf{x}$ 的马氏距离

海明距离#

d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^n \delta(x_i, y_i)

其中 $\delta(x_i, y_i)$ 是一个指示函数，当 $x_i \neq y_i$ 时为 1，否则为 0。

角度相似函数#

d(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x}^T\mathbf{y}}{\|\mathbf{x}\| \|\mathbf{y}\|}

多层感知机(MLP)#

反向传播算法#

设输入层有 $n$ 个神经元，隐藏层有 $h$ 个神经元，输出层有 $m$ 个神经元。

我们需要得到第 $i$ 层的梯度 $\frac{\partial J}{\partial \mathbf{W}^{(i)}}$ ，其中 $J$ 是损失， $\mathbf{W}^{(i)}$ 是第 $i$ 层的权重。

根据链式法则：

\frac{\partial J}{\partial \mathbf{W}^{(i)}} = \frac{\partial J}{\partial \mathbf{z}^{(i)}} \cdot \frac{\partial \mathbf{z}^{(i)}}{\partial \mathbf{W}^{(i)}}

$\mathbf{z}^{(i)}$ 是第 $i$ 层的线性输出， $\mathbf{z}^{(i)} = \mathbf{W}^{(i)} \mathbf{a}^{(i-1)} + \mathbf{b}^{(i)}$ ，其中 $\mathbf{a}^{(i-1)}$ 是第 $i-1$ 层的激活输出（也是第 $i$ 层的输入）。

所以：

\frac{\partial \mathbf{z}^{(i)}}{\partial \mathbf{W}^{(i)}} = \mathbf{a}^{(i-1)}

则：

\frac{\partial J}{\partial \mathbf{W}^{(i)}} = \frac{\partial J}{\partial \mathbf{z}^{(i)}} \cdot \mathbf{a}^{(i-1)}

$\dfrac{\partial J}{\partial \mathbf{z}^{(i)}}$ 被称作第 $i$ 层的局部误差

若 $i$ 是最后一层时，则 $\frac{\partial J}{\partial \mathbf{z}^{(i)}}$ 可以直接计算；若 $i$ 不是最后一层，则从最后一层开始，逐层向前计算 $\frac{\partial J}{\partial \mathbf{z}^{(i)}}$ ，直到计算到第 $i$ 层。

\begin{aligned} \frac{\partial J}{\partial \mathbf{z}^{(i-1)}} &= \frac{\partial J}{\partial \mathbf{z}^{(i)}} \cdot \frac{\partial \mathbf{z}^{(i)}}{\partial \mathbf{a}^{(i-1)}} \cdot \frac{\partial \mathbf{a}^{(i-1)}}{\partial \mathbf{z}^{(i-1)}} \\ &= (\mathbf{W}^{(i)})^T \cdot \frac{\partial J}{\partial \mathbf{z}^{(i)}} \cdot \sigma'(\mathbf{z}^{(i-1)}) \end{aligned}

TIP
$\dfrac{\partial \mathbf{a}^{(i-1)}}{\partial \mathbf{z}^{(i-1)}}$ 就是激活函数的导数
$z^{(i)} = W^{(i)} a^{(i-1)} + b^{(i)}$ ，所以 $\dfrac{\partial \mathbf{z}^{(i)}}{\partial \mathbf{a}^{(i-1)}} = W^{(i)}$

决策树#

一直问”是A还是B”来缩小范围，叶节点就是答案。

信息增益(ID3)#

选让分完后数据最不混乱的那个特征来分类

熵衡量混乱程度（详见特征提取），数据集 $D$ 的熵：

H(D) = -\sum_{k} p_k \log_2 p_k

$p_k$ 是第 $k$ 类占的比例。熵越大越乱，全是同一类时熵=0。

按特征 $A$ 的每个取值 $v$ 把数据分成若干子集 $D^v$ ，各子集的熵加权平均就是条件熵：

H(D|A) = \sum_{v} \frac{|D^v|}{|D|} H(D^v)

$|D|$ ：总样本数
$|D^v|$ ：特征 $A=v$ 的样本子集的样本数
$\dfrac{|D^v|}{|D|}$ ： $A=v$ 的样本占全部的比重
$H(D^v)$ ：样本子集自己的熵

信息增益 = 划分前熵 - 划分后熵，越大说明这个特征分得越好：

\text{Gain}(D, A) = H(D) - H(D|A)

增益率(C4.5)#

ID3的缺点：过于偏好取值多的特征（比如”编号/ID”这种每个样本值都不同，增益直接拉满但不泛化）。C4.5引入固有值来惩罚取值多的特征，增益除以它进行校正：

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

基尼指数(CART)#

CART用基尼值代替熵 $H(D)$ ，计算更简单：

\text{Gini}(D) = 1 - \sum_k p_k^2 \\[1em] \text{Gini}{(D|A)} = \sum_v \frac{|D^v|}{|D|} \text{Gini}(D^v)

纯的类基尼=0（全是同一类），最乱时接近0.5。

核方法#

根据线性分类器的判别函数(非增广形式)：

g(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + w_0

又根据感知器算法和SVM算法的权重更新规则：

w_0 \leftarrow w_0 + \eta y_i

\mathbf{w} \leftarrow \mathbf{w} + \eta y_i \mathbf{x}_i

可以发现最优解 $\mathbf{w}$ 和 $w_0$ 可以表示为训练样本的线性组合：

\mathbf{w} = \sum_{i=1}^N \alpha_i \mathbf{x}_i

SVM时大多数 $\alpha_i=0$ ，只有支持向量对应的 $\alpha_i$ 非零

将 $\mathbf{w}$ 代入判别函数：

\begin{aligned} g(\mathbf{x}) &= \left (\sum_{i=1}^N \alpha_i \mathbf{x}_i \right )^T \mathbf{x} + w_0 \\[1em] &= \sum_{i=1}^N \alpha_i(\mathbf{x}^T \mathbf{x}_i) + w_0 \end{aligned}

因此只要得到训练样本之间的内积 $\mathbf{x}^T \mathbf{x}_i$ ，就可以计算判别函数的值。

为了处理非线性可分问题，可以将输入空间映射到一个高维特征空间：

\phi: \mathbb{R}^n \rightarrow \mathbb{R}^m

但是这个映射的计算非常昂贵。核方法的核心思想是引入一个核函数 $K(\mathbf{x}, \mathbf{y})$ ，直接计算输入空间中的内积在特征空间中的值：

K(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x})^T \phi(\mathbf{y})

常用的核函数包括：

线性核： $K(\mathbf{x}, \mathbf{y}) = \mathbf{x}^T \mathbf{y}$
多项式核(Polynomial Kernel)： $K(\mathbf{x}, \mathbf{y}) = (\mathbf{x}^T \mathbf{y} + c)^d$
径向基函数核(Gaussian RBF)： $K(\mathbf{x}, \mathbf{y}) = \exp(-\gamma \|\mathbf{x} - \mathbf{y}\|^2)$
Sigmoid核： $K(\mathbf{x}, \mathbf{y}) = \tanh(\kappa \mathbf{x}^T \mathbf{y} + c)$
Inverse Multiquadratic核： $K(\mathbf{x}, \mathbf{y}) = \frac{1}{\sqrt{\|\mathbf{x} - \mathbf{y}\|^2 + c^2}}$

TIP
$\tanh(x) = \dfrac{e^x - e^{-x}}{e^x + e^{-x}}$
当输入较大时，输出接近1；当输入较小时，输出接近-1

使用核函数后，判别函数可以表示为：

g(\mathbf{x}) = \sum_{i=1}^N \alpha_i K(\mathbf{x}, \mathbf{x}_i) + w_0

基于核方法的Logistic回归#

\begin{aligned} P(G=k|\mathbf{x}) &= \frac{\exp(\beta_{k0} + \sum_{i=1}^N \alpha_{ki} K(\mathbf{x}_i, \mathbf{x}))}{1 + \sum_{l=1}^{K-1} \exp(\beta_{l0} + \sum_{i=1}^N \alpha_{li} K(\mathbf{x}_i, \mathbf{x}))} \\[1em] P(G=K|\mathbf{x}) &= \frac{1}{1 + \sum_{l=1}^{K-1} \exp(\beta_{l0} + \sum_{i=1}^N \alpha_{li} K(\mathbf{x}_i, \mathbf{x}))} \end{aligned}

[模式识别与机器学习] 非线性分类器

https://alkaid114.github.io/posts/ml/nonlinear_classifier/

作者

Alkaid114

发布于

2026-06-17

许可协议

CC BY-NC-SA 4.0

[模式识别与机器学习] 特征提取

[计算机视觉] 斑点检测

距离函数#

欧氏距离#

曼哈顿距离#

明氏距离#

马氏距离#

海明距离#

角度相似函数#

最近邻分类器#

k-最近邻算法#

Voronoi网格#

多层感知机(MLP)#

反向传播算法#

决策树#

信息增益(ID3)#

增益率(C4.5)#

基尼指数(CART)#

核方法#

基于核方法的Logistic回归#