东北大学《人工智能的数学基础》,笔者自学参考教材为
人工智能的数学基础(冯朝路等)

特征向量与矩阵分析

有右逆行满秩,左逆列满秩
非方阵:n×k,若n>k,其n维体积为0,k维体积不为0

MDS

保持变换前后空间内距离保持不变
代码参考:https://0809zheng.github.io/2021/07/28/mds.html

def MDS(data, k):
    d, N = data.shape
    D = np.zeros([N, N])
    # 计算距离矩阵D
    for i in range(N):
        for j in range(N):
            D[i, j] = np.sqrt(np.sum((data[:,i]-data[:,j])**2))
    # 计算内积矩阵B
    T1 = np.sum(D**2, axis=0, keepdims=True)/N
    T2 = np.sum(D**2, axis=1, keepdims=True)/N
    T3 = np.sum(D**2, keepdims=True)/N**2
    B = (T1+T2-T3-D**2)/2
    # 计算特征值和特征向量
    eig_values, eig_vectors = np.linalg.eig(B)
    # 选择前k个最大的特征值标号
    index = np.argsort(-eig_values)[:k]
    # 选择对应的特征值和特征向量
    MDS_values = eig_values[index]
    MDS_vectors = eig_vectors[:, index] # (N, k)
    # 降维
    reduced_data = np.diagflat(MDS_values**0.5).dot(MDS_vectors.T) # (k, N)
    return reduced_data

step
1.构建距离矩阵D(也叫不相似矩阵)
2.计算降维后的内积矩阵B( $B=-\frac{1}{2}HD^2H\text{ where }H=I-\frac{1}{N}ii^T$ ),i为全1列向量,H称为中心化矩阵
乘上中心化矩阵正好将数据中心化,左乘减去行均值,右乘减去列均值
3.特征值分解并选择最大的k个特征值

dimension reduction(PCA)

问题描述

对独立同分布向量(假设均值为0向量)构成的矩阵,其协方差矩阵为 $S=\frac{1}{N}\mathop{\sum}\limits_{n=1}\limits^{N}x_nx_n^T$
我们假设其存在低维表示 $z_n=B^Tx_n\in \mathbb{R}^M$
并且投影矩阵 $B\in \mathbb{R}^{D\times M}$ 列正交
目标是找到投影后的向量或者投影矩阵来使其与原数据尽可能相似
(可将B视为解码器，其转置视为编码器)

最大方差视角 (Maximum Variance Perspective)

如果我们将数据包含的信息视为它“填充空间”的程度，就可以通过观察数据的分散程度来判断信息量的大小，即方差 (Variance)。

假设数据已经过中心化处理（均值为0），第一主成分方向 $b_1$ 的投影方差 $V_1$ 定义如下：

$V_1 = \frac{1}{N} \sum_{n=1}^{N} z_{1n}^2 = b_1^T \left( \frac{1}{N} \sum_{n=1}^{N} x_n x_n^T \right) b_1$

约束条件：注意到单纯增加 $b_1$ 的长度会盲目增大方差，但这对寻找方向没有意义。因此我们限制 $\|b_1\|_2 = 1$ （即 $b_1^T b_1 = 1$ ）。

这是一个受限优化问题。通过拉格朗日乘数法可以证明： $b_1$ 必须是协方差矩阵的特征向量，而对应的方差 $V_1$ 恰好就是对应的特征值。

为了研究第一主成分的影响，我们可以将坐标投影回原空间：

$\tilde{x}_{1n} = b_1 z_{1n} = b_1 b_1^T x_{1n}$

Tips：尽管投影结果是一个 $D$ 维向量，但它实际上只需要一个关于基向量的坐标就能描述。

寻找后续主成分

假设我们已经找到了前 $m-1$ 个主成分，为了找到第 $m$ 个主成分，需要先从原始矩阵中减去前 $m-1$ 个主成分的影响（即减去它们解释过的方差）：

$\hat{X} := X - \sum_{i=1}^{m-1} b_i b_i^T X$

注意：为了公式表达方便，此处设定数据矩阵 $X$ 的维度为 $D \times N$ （每一列代表一个样本），而不是传统的 $N \times D$ 。

相似性度量

以下均研究两个特征向量之间的相似性

闵氏距离(minkowski distance):
$d(x,y)=(\sum_{i=1}^{n}|x_i-y_i|^p)^{\frac{1}{p}}$ ,p>0为可变的阶数,它没有消除不同量纲的影响
曼哈顿距离(manhattan distance):
p=1时的闵氏距离
欧几里得距离(enclidean distance):
p=2时的闵氏距离
切比雪夫距离(chebyshev distance):
$p\rightarrow \infty$
曼哈顿和切比雪夫可以互相转化,并且变换为线性变换
马氏距离(Mahalanobis Distance):
标准化:将特征向量各分量视为独立同分布,计算各分量的分布特性控制参数并将其转移到相同参数(不一定独立)
独立化:消除线性相关性,使得保留单个分量值的向量相互正交(为此可以直接进行旋转变换)
独立化step:中心化旋转:将PCA获得的主成分方向旋转至坐标轴主方向上缩放:主成分缩放使其方差为1
缺点:可能极大程度上放大了噪声
马氏距离实际上就是考虑了上述修正的欧氏距离
$d(x_i,x_j)=\sqrt{(x_i-x_j)\Sigma^{-1}(x_i-x_j)^T}\text{ where }\Sigma=(X-\bar{X})(X-\bar{X})^T$
注意分块乘法成立条件
余弦距离:
范围0~2
$d=1-\frac{xy^T}{\sqrt{xx^T}\sqrt{yy^T}}$
汉明距离(hamming distance):
实际上衡量了两个向量不相等的分量个数
严格定义: $d=\sum_{i=1}^n sgn(|x_i-y_i|)$
松弛定义就是计数差大于某个数而不是严格为0
杰卡德距离(jaccard distance):
杰卡德相似系数的严格定义: $s=\frac{1}{n}\sum_{i=1}^{n}(1-sgn(|x_i-y_i|))$
距离就是1-系数
皮尔森相关系数(pearson correlation coefficient)(中心化的余弦相似度)
$s=\frac{(x-\bar{x})(y-\bar{y})}{\sqrt{(x-\bar{x})(x-\bar{x})^T}\sqrt{(y-\bar{y})(y-\bar{y})^T}}$
d=1-|s|
只能衡量线性相关性,易受异常数据的影响
斯皮尔曼距离(spearman distance)
相关系数:
s=两个向量秩值的皮尔森相关系数
向量第i个分量按分量间从小到大排第j,则 $r(x_i)=j$ ,相等的分量值平分秩值
实际上衡量了变化的一致性
d=1-|s|
肯德尔距离(kendall distance)

函数与泛函分析

线性判别分析(LDA):寻找数据投影,使其类内散度(方差)最小,类间散度(均值差)最大
第二个公式也叫fisher 判别(其中w即为所求投影向量)

$max\frac{(m_1-m_2)^2}{s_1^2+s_2^2} J_f=\frac{wS_bw^T}{wS_ww^T}=\frac{w(\sigma_1^2+\sigma_2^2)w^T}{w(\mu_1-\mu_2)^T(\mu_1-\mu_2)w^T}$

支持向量机(SVM):不只是将数据线性可分,并且要最大化间隔
距超平面最近的点称为支持向量
n维空间点到超平面的距离

$\begin{aligned} S=\frac{|w^Tx+b|}{||w||}\\ \begin{cases} \frac{w^Tx+b}{||w||d}\ge 1,y=1\\ \frac{w^Tx+b}{||w||d}\le -1,y=-1\\ \end{cases} \end{aligned}$

$\begin{aligned} y(w^Tx+b)-1+\xi \ge 0\\ max (2\times \frac{y(w^Tx+b)}{||w||})\\ \end{aligned}$

有一个松弛变量用于软化,对于支持向量,目标分子为1,优化问题变为最小化w的模长+松弛参数

集合与区间

凸集分离定理
凸集

$\theta x+(1-\theta)y\in C\text{ for all }x,y\in C$

凸函数

$f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y)$

凸集:对一个集合,其中任意两点的连线仍然在集合中的集合称为凸集
凸集分离定理:对n维实数空间中的两个不相交的非空凸集,存在一个超平面将其分开(线性可分)

$\begin{aligned} ws_1^T\ge 0,\forall s_1\in S_1\\ ws_2^T\le 0,\forall s_2\in S_2 \end{aligned}$

区间是具有特定属性的实数集合
取等的边界:上(下)确界
不取等的边界:上(下)界
区间的算术:对区间进行四则运算得到的区间就是元素四则运算得到的所有结果
凸函数与严格凸函数:严格凸函数就是不取等
凸函数的一阶充要条件

$f(x_2)\ge f(x_1)+\nabla f(x_1)(x_2-x_1)$

二阶充要条件就是黑塞矩阵为半正定

曲率:取x0左右邻接点确定一个圆,邻接点接近x0即为密切圆,密切圆圆心轨迹称渐趋线,函数称为密切圆的圆心轨迹的渐伸线

$\kappa(x_0)=\frac{|f^{\prime\prime}(x_0)|}{(1+f^{\prime}(x_0)^2)^{\frac{3}{2}}}$

泛函分析

以函数为自变量的函数,称为泛函
将区间n等分,则函数可由对应点的函数值构成的n维向量近似,n接近无穷的时候可认为函数与向量相等

函数内积

$<f,g>=\int f(x)g(x)dx$

特征函数与特征值

$\begin{aligned} \int K(x,y)\phi(y)dy=\lambda \phi(x)\\ K(x,y)=\sum_{i=1}^{\infty}\lambda_i \phi_i(x)\phi_i(y) \end{aligned}$

则称一元函数是二元函数的特征函数,对应系数即为特征值(存在无穷多的特征值和特征向量)

二元函数可视为无限维的矩阵

对称半正定

$\int\int f(x)K(x,y)f(y)dxdy\ge 0$

则称K为对称半正定

线性空间与线性映射
各概念与向量类似
希尔伯特再生空间(RKHS)

$\begin{aligned} K(x,y)=\sum_{i=1}^{\infty}\lambda_i \phi_i(x)\phi_i(y)\\ K(x,:)=[\sqrt{\lambda_i}\phi_i(x),...](基)\\ <K(x,:),k(:,y)>_{\mathcal{H}}=K(x,y)\\ f=\sum_{i=1}^{\infty}a_i\phi_i\\ ||f||^2_{origin}=\int |f(x)|^2dx=\sum_{i=0}^{\infty}a_i^2 \\ ||f||^2_{RKHS}=\sum_{i=0}^{\infty}\frac{a_i^2}{\lambda_i}\\ <f,g>_{\mathcal{H}}=\sum_{i=1}^\infty \frac{a_ib_i}{\lambda_i}\text{ for function }f(t)=\sum a_i\phi_i (t) \text{ and }g(t)=\sum b_i \phi_i(t) \end{aligned}$

度量空间(matric space)

度量空间:集合配上一个距离函数(非负性,对称性,三角不等式)
赋范线性空间:集合配上一个范数函数,可以很自然转化为度量空间
巴纳赫空间(banach space):完备赋范向量空间
- 完备:空间任意向量的柯西序列收敛至良定义的空间内部
- 柯西序列:
- 比如有理数轴就不符合定义:有理数组成的柯西序列收敛至无理数
希尔伯特空间(Hilbert Spaces)：完备的内积空间(带有内积的完备矢量空间)
内积的构造推广了欧几里得空间中的距离和角的概念

一个巴纳赫空间的范数只有满足平行四边形法则才能由内积导出,从而形成希尔伯特空间

$||u+v||^2+||u-v||^2=2(||u||^2+||v||^2)$

线性算子(linear operator)

线性算子
算子就是从一个空间映射到另一个空间的规则,如果满足线性性即可称为线性算子:本质上线性算子就是矩阵在更大空间的推广
线性泛函
线性空间到对应标量域的映射线性映射(V为域k的线性空间,该映射从V到k)
e.g:函数在某点的特定的值,函数在一个区域内的定积分
解读:类似一个测量装置将一个很多特征的物体,提取某个特定特征出来
有界性与连续性(赋范空间)
有界必连续
后者被称为算子范数,衡量拉伸倍数

$\begin{aligned} T:X\rightarrow Y,\exists M,||Tx||\le M||x||\\ ||T||=sup_{||x||=1}||Tx|| \end{aligned}$

对偶空间(dual space)

对偶空间就是在原始向量空间上的所有表现良好(即连续)的线性泛函:提供了从外部研究空间的方法

hahn-banach定理
- 1.对空间中两个不相同的点,一定存在一个有界线性泛函在两点的取值不同
- 2.若在X子空间上定义了一个有界线性泛函,则我们可以将其延拓到整个空间并保持范数不变

设n维线性空间的一组基为 $\epsilon_i,f_i(\epsilon_j)=1(when\text{ }i=j)$
对s中任意向量

$\begin{aligned} \alpha=\sum_{i=1}^{n}x_i\epsilon_i\\ x_i=f_i(\alpha) \end{aligned}$

Riesz 表示定理 (Riesz Representation Theorem)
在希尔伯特空间中,任何一个有界线性泛函都可以写成与某个唯一向量的内积,即

$f(x)=<x,y_f>$

,并且泛函的范数等于那个向量的范数,这意味着任何一种抽象的测量都可以对应为与一个模板做对应

伴随算子(adjoint operator)
每个内积空间的线性算子都有伴随算子,满足

$<Ax,y>=<x,A^*y>$

两者范数相等

谱理论(spectual theory)

核心直觉：什么是“谱” (The Spectrum)？

在线性代数中，我们研究特征值 $\lambda$ 。在泛函分析中，特征值只是“谱”的一部分。

从方程出发：考虑算子方程 $(T - \lambda I)x = y$ $(T - λ I) x = y$ 。
- 在有限维中，这个方程要么有唯一解（ $\lambda$ 不是特征值），要么没有唯一解（ $\lambda$ 是特征值）。
- 在无穷维中，情况变得复杂。即便 $\lambda$ 不是特征值（算子是一对一的），方程的解 $x = (T - \lambda I)^{-1}y$ 可能会出现无界、不连续或定义域不全的情况。
定义：使 $(T - \lambda I)$ 变得“表现不好”（不可逆、不连续或不完备）的所有 $\lambda$ 的集合，就叫 谱 $\sigma(T)$ 。
AI 视角：谱描述了一个模型（算子）的稳定性和能量分布。例如，如果一个神经网络层的算子谱半径（最大的特征值模长）大于 1，信号在传递时就会呈指数级放大，导致梯度爆炸。

紧算子 (Compact Operators)：无穷维中的“有限维化”

这是理解谱理论在 AI 中应用的关键。

定义：如果一个算子能把空间中的有界集（比如单位球）映射成一个相对紧集（其闭包每个序列都有收敛子列），它就是紧算子。
形象理解：“平滑效应”。
- 紧算子就像是一个“低通滤波器”。它能把杂乱无章、无限维度的输入，压缩成一个有秩序、主要维度清晰的输出。
- 例子：神经网络中常见的积分变换、高斯模糊。
谱的奇迹：紧算子的谱非常简单。
1. 几乎全是特征值：除了 0 以外，谱里的每一个点都是实打实的特征值。
2. 可数性：特征值是一串离散的数字，不会填满一个区间。
3. 趋向于 0：如果特征值有无穷多个，它们必须排队走向 0。
AI 意义：这解释了为什么主成分分析 (PCA) 或自编码器 (Autoencoder) 能够工作。因为数据的主要信息集中在少数几个大的特征值对应的方向上，而无穷无尽的微小维度（噪声）都随着特征值趋向于 0 而消失了。

自伴算子 (Self-adjoint)：无穷维的“对称性”

定义：满足 $\langle Tf, g \rangle = \langle f, Tg \rangle$ 。
形象理解：它是**“物理上可观测”**的。
- 自伴算子在无穷维中扮演着对称矩阵的角色。
两大特性：
1. 谱是实的：特征值永远是实数，没有虚部。这保证了模型测量的结果是有物理意义的数值。
2. 正交性：不同特征值对应的特征函数（特征向量）是完全垂直的。

紧自伴算子的谱定理：完美的终极分解

当一个算子既是紧的又是自伴的时，我们得到了泛函分析中最美丽的结论：谱定理。

结论：你可以找到一组标准正交基 $\{e_n\}$ ，使得算子 $T$ 在这个基下完全“对角化”。
分解公式： $Tf = \sum \lambda_n \langle f, e_n \rangle e_n$ 。
这意味着什么？
- 任何复杂的输入 $f$ ，都可以分解为一束正交的“光”（特征函数 $e_n$ ）。
- 算子 $T$ 的作用，仅仅是调节每束光的亮度（乘以 $\lambda_n$ ）。

谱理论在 AI 中的深度应用实例

(1) 核方法中的 Mercer 定理 (Mercer’s Theorem)
这是谱定理在机器学习中的直接体现。

如果我们定义一个核函数 $K(x, y)$ ，它诱导的积分算子通常是紧且自伴的。
Mercer 定理说：这个核可以分解为 $K(x, y) = \sum \lambda_n \phi_n(x) \phi_n(y)$ 。
这就是为什么我们可以把复杂的非线性映射，转化为在希尔伯特空间中的线性操作。

(2) 扩散模型 (Diffusion Models) 与拉普拉斯谱
扩散模型模拟噪声的消失过程。

这个过程由拉普拉斯-贝尔特拉米算子 (Laplace-Beltrami Operator) 支配。
该算子是自伴的，它的特征函数（谱）对应于图像的不同频率。
谱理论解释：扩散过程本质上是按照谱的顺序（特征值的大小），先抹除高频噪声（对应小的特征值），保留低频结构（对应大的特征值）。生成过程则是这个谱演化的逆过程。

(3) 谱归一化 (Spectral Normalization)
在训练稳定的 GANs 时，我们强制要求每一层权重矩阵 $W$ 的谱范数（最大特征值）等于 1。

原理：根据谱理论，这保证了该算子是一个 利普希茨连续 (Lipschitz Continuous) 映射，防止了模型在更新时梯度剧烈抖动，确保了算子的“有界性”。

条件概率和贝叶斯

gamma函数可以认为是阶乘在实数域上的拓展

gamma distribution

$f(x)=\frac{\lambda^{\alpha}x^{\alpha -1}e^{-\lambda x}}{\Gamma(\alpha)},x>0$

熵最大原理:正态分布是确定均值和方差之后熵最大的分布
推导:
alt text

最小错误率贝叶斯决策

$P(e)=\int_{R_1}P(w_2|x)f(x)dx+\int_{R_2}P(w_1|x)f(x)dx$

求其argmin的过程即定义了最小错误率贝叶斯决策(错误率最小其实等价于选后验概率最大)
也可以表示为

$argmax_i(P(w_i|x))$

多分类决策就是将特征空间分割为更多的区域,为减少计算量通常采用错误率=1-平均正确率

最小风险贝叶斯
最小错误率实际上将所有的正确判断和误判的损失认为相同
计alpha为决策结论,lambda为给定样本和决策结论的损失

$\begin{aligned} R(\alpha(x)|x)=\sum_{i=1}^{C}\lambda(\alpha(x),w_i)P(w_i|x)\\ argmin_{\alpha} R(\alpha)=argmin_{\alpha}(\int R(\alpha(x)|x)f(x)dx) \end{aligned}$

朴素贝叶斯分类
后验概率最大等价于类先验概率和条件概率的乘积最大
由特征属性的条件独立假设:我们可以将类条件概率写为

$P(x|y_k)=\prod_{i=1}^dP(x_i|y_k)$

可使用训练集中的各类样本出现的比例估计类先验概率和类条件概率
属性离散时可以直接估计,属性连续时,一种方法是离散化,另一种是将其视为某种分布
为了增强鲁棒性,等效扩大样本数

$P(x_i|y_k)=\frac{n_i+mp}{m+n}$

最小二乘估计
最小化预测值和真实值的误差

$argmin_{\hat{w}}(\hat{w}X-y)(\hat{w}X-y)^T$

若X与自身转置的乘积为正定则有唯一解

最大似然估计
最小错误率贝叶斯决策,就是最大化后验概率,就是最大似然(本质其实和最小二乘等价)
最大后验概率估计:最大似然估计是先验为均匀分布的最大后验估计
贝叶斯估计

信息论与熵

特征的选择和抽取:其实就是一种压缩编码
one hot 编码:n种取值一共就有n个维度,i维取1表示值取i
dummy encode(哑编码):n种取值,n-1维也可以,第n维表示可以是全零
有些时候,连续变量也可以离散化来进行编码,这样参数更多,非线性能力更强

特征选择
信息增益:遍历所有特征,算信息增益来选择

$G(B)=Ent(D)-\sum_{i=1}^v\frac{|D_i|}{|D|}Ent(D_i)$

稀疏编码
一份文档不可能涵盖字典中的所有汉字,所以其统计频率的特征向量有多个0分量

$min\sum_{i=1}^m(||x_i-y_iB||_2^2+\lambda||y_i||_1)$

其中x为原向量,y为压缩后的

压缩感知

$\begin{aligned} y=x\Phi\\ x=s\Psi\\ y=s\Psi\Phi \end{aligned}$

变换将x变为低维向量y,可以选择恰当的基向量使s为稀疏的,这样可以解

决策编码和决策解码

多分类学习的基本思路是拆分法
一种方法是训练多个分类器,每个分类器将其中一些视为正例,另一些视为反例

纠错输出码(error correcting output codes,ECOC)
二元码:分成正例或反例(三元码还有一个停用类)
一对一(OvO):一共(n-1)n/2个分类器,每个分类器识别一种正例和一种反例
一对其余(OvR):n个分类器,一种作为该分类器的正例,其他全是反例
多对多(MvM):若干正例若干反例
其决策解码:
各分类器对测试用例的判断构成决策向量,将向量和各类别向量比较(采用各种距离度量)

自编码

自编码器由一个编码器和一个解码器构成,编码器将原始映射为隐藏表示,解码器从原始映射重构
限制隐藏表示维度小于原始数据:欠完备自编码(剔除冗余特征)

$\begin{aligned} arg min_{g,f} L(x,g(f(x)))&(欠完备)\\ arg min_{g,f} (L(x,g(f(x)))+R(f(x)))&(稀疏自编码,R常取f(x)的范数)\\ arg min_{g,f} (L(x,g(f(x)))+R(f(x),x))&(收缩自编码,比如取梯度范数,要求对扰动鲁棒)\\ \end{aligned}$

熵

度量不确定性

$Ent(x)=-\int f(x)log_a(f(x))dx$

联合熵
各变量联合熵大于任意一个变量的熵,一定小于所有变量的熵的和

$Ent(X,Y)=-\int\int f(x,y)log_a(f(x,y))dxdy$

条件熵

$Ent(X|Y)=-\int\int f(x,y)log_a(f(x|y))dxdy$

交叉熵

$\begin{aligned} Ent(f_0,f_1)=-\int f_0(x)log_a(f_1(x))dx\\ D_{KL}(f_0||f_1)=\int f_0(x)log_a(\frac{f_0(x)}{f_1(x)})dx=Ent(f_0,f_1)-Ent(f_0) \end{aligned}$

互信息

给定提示信息X,Y的不确定性的减少量

$\begin{aligned} I(Y;X)=Ent(Y)-Ent(Y|x)=D_{KL}(f(x,y)||f(x)f(y))\\ g(x,y)=log_a(\frac{f(x,y)}{f(x)f(y)})PMI(点互信息) \end{aligned}$

alt text

线性分析和卷积

卷积

卷积具有交换,分配,结合律
时域卷积=频域乘积

$\begin{aligned} F(f(t)*g(t))=F(w)G(w)\\ g(x)=\int f(x-\tau)h(\tau)d\tau \text{ convolution}\\ F(w)=\int f(t)e^{-i\omega t}dt \text{ fourier transform}\\ f*g=\sum_{\tau}\sum_{\eta}f(x-\tau,y-\eta)g(\tau,\eta)\text{ 2d conv }\\ g(x)=r(\cup_{\tau =-b}^{+b}f(x-\tau))\text{ pooling } \end{aligned}$

边界填充:补零,扩展(填边界),镜像
步长:步长大于1又称空洞卷积
池化:下采样,但是并没有引入学习的参数的同时增大了卷积核的感受野

反卷积

一种上采样,本质上是补零后再卷积

$\begin{aligned} o&=\lfloor\frac{i+2p-k}{s}\rfloor + 1\\ o^{\prime}&=s(i^{\prime}-1)+a+k-2p\text{ where }a=(i+2p-k)modS \end{aligned}$

矩阵视角

alt text
其实又叫常对角矩阵,卷积就可以视为和矩阵的乘法
1D直接就是向量,2D通常展开后乘矩阵

正则化和范数

硬正则化

归一化:

$x^{\prime}=\frac{x-x_{min}}{x_{max}-x_{min}}$

标准化:减均值除方差
early stop
权重共享(实际上是直接置0)
池化
随机失效(dropout,用掩码)
集成学习:h为其中一个模型,G为平均,f为真实目标
支持向量机

软正则化

(损失函数)

logistic loss(f为实际标签,h为其为预测标签)

$L(h,f)=-f(x)log(P(h(x)=1))-(1-f(x))log(P(h(x)=0))$

hinge(支持向量机)

$L(h(x),f(x))=max(0,1-f(x)h(x))$

风险
期望风险:损失函数在真实值函数取值空间的积分(理想化,用不了)
经验风险:直接就是训练集的损失求和

VC维(度量模型复杂度,可以无穷大):
d维超平面的VC维是d+1,实际上就是n个点任意的类别情况,该维度都有分类器分开

范数

等价:对任意同一个向量的两种范数的比值始终具有常数下界和上界

矩阵范数:
所有元素绝对值之和:L1范数
所有元素平方之和开根:L2范数(Frobenius范数),也可写为与自身转置乘积的迹开根
Luv范数

$||W||_{L_{uv}}=||[...,||W_{:,i}||_u,...]||_v$

其中1-范数指列模(列元素和的最大值),无穷-范数指行模,2-范数也叫谱范数,与自身转置乘积的最大特征值再开根
核范数:奇异值的和
alt text

最优化

最优化理论与方法：拟牛顿法专题笔记

第一部分：最优化基础与牛顿法

目标问题定义

数学模型： $\min_{\theta \in \Theta} f(\theta)$ ，受限于等式约束 $g_j(\theta)=0$ 和不等式约束 $h_i(\theta) \le 0$ 。
最优性条件：
- 一阶必要条件 (FONC)：驻点满足 $\nabla f(\theta^*) = 0$ 。
- 第一充分条件:在驻点去心邻域一阶导
- 二阶充分条件 (SOSC)：在驻点处，Hessian 矩阵 $H(\theta) = \nabla^2 f(\theta)$ 必须是正定的（ $H > 0$ ）。

牛顿法 (Newton’s Method)

核心思想：对 $f(\theta)$ 进行二阶泰勒展开：
$f(\theta+\Delta\theta) \approx f(\theta) + \nabla f(\theta)^T \Delta\theta + \frac{1}{2} \Delta\theta^T H(\theta) \Delta\theta$
迭代公式： $\theta_{k+1} = \theta_k - \eta[H(\theta_k)]^{-1} \nabla f(\theta_k)$
最速下降法: $\eta_k=argmin_{\eta}f(\theta_k-\eta\nabla f(\theta_k))$
优缺点：
- 优点：具有二阶收敛速度。
- 缺点：每一轮迭代都需要计算 $H$ 矩阵（ $n^2$ 个二阶导）并进行矩阵求逆（复杂度 $O(n^3)$ ），在海量参数下不可行。

第二部分：拟牛顿法 (Quasi-Newton) 核心思想

基本初衷
不直接计算 $H$ 及其逆，而是通过迭代公式构造一个近似矩阵 $B_k \approx H$ 或 $G_k \approx H^{-1}$ 。
拟牛顿方程 (Secant Equation)
这是所有拟牛顿算法的数学根基。定义位移 $s_k$ 和梯度差 $y_k$ ：

$s_k = \theta_{k+1} - \theta_k$
$y_k = \nabla f(\theta_{k+1}) - \nabla f(\theta_k)$
方程： $y_k \approx H_{k+1} s_k$ $\Rightarrow$ $B_{k+1} s_k = y_k$ 或 $s_k = G_{k+1} y_k$

第三部分：数学引擎——Sherman-Morrison 公式
它是将“矩阵更新”转化为“逆矩阵更新”的桥梁。

公式内容：若 $A$ 为可逆矩阵， $u, v$ 为向量，满足 $1 + v A^{-1} u^T \neq 0$ ，则：
$(A + u^T v)^{-1} = A^{-1} - \frac{A^{-1} u^T v A^{-1}}{1 + v A^{-1} u^T}$
证明逻辑：
通过证明 $(A + u^T v) \cdot [A^{-1} - \dots] = E$ （单位矩阵）。
展开后利用 $A A^{-1} = E$ 以及标量可以自由移动的性质，中间项会互相抵消。
算法应用：拟牛顿法的更新通常是“原矩阵 + 秩-1（或秩-2）修正”。有了这个公式，我们可以直接更新 $G$ （逆矩阵），从而把复杂度从 $O(n^3)$ 降到 $O(n^2)$ 。

第四部分：拟牛顿修正公式分类

秩-1 修正 (SR1 - Symmetric Rank 1)

公式： $G_{k+1} = G_k + \frac{(s_k - G_k y_k)(s_k - G_k y_k)^T}{y_k^T (s_k - G_k y_k)}$
评价：形式简单，但不能保证正定性，容易由于分母趋近于 0 导致算法不稳定。
推导:
$G_{k+1}=G_k+u^Tv$
解出来v回代,为了保证对称性令u=带入后第二项的分子

秩-2 修正：DFP 与 BFGS (对偶双子星)
这是拟牛顿法的精髓，两者具有高度的数学对称性。
(DFP)

$G_{k+1}=G_k+\frac{s_k^Ts_k}{y_ks_k^T}-\frac{G_ky_k^Ty^kG_k}{y_kG_ky_k^T}$

推导:
$s_k=y_k(G_k+\alpha u^Tu+\beta v^Tv)$
再令后两项的系数为1,-1,u,v分别等于sk和ykgk
BFGS就是把G和B,s和y互换

特性	DFP 算法	BFGS 算法
出发点	直接近似 Hessian 的逆 $G$	先近似 Hessian $B$
满足方程	$G_{k+1} y_k = s_k$	$B_{k+1} s_k = y_k$
对偶关系	$G \leftrightarrow B, s \leftrightarrow y$	与 DFP 完全对称
稳定性	容易受到线搜索精度的影响	数值稳定性极佳（业界主流）

第五部分：BFGS 算法的演变路径 (看图总结)

第一步 (Hessian 近似)：先推导出 $B_{k+1}$ 的更新公式（右上角路径）。
第二步 (求逆应用)：利用 Sherman-Morrison 公式（或者更通用的 Woodbury 公式），将 $B$ 的秩-2 修正公式转化为 $G$ 的更新公式（垂直向下路径）。
终极公式 (BFGS 逆公式)：
$G_{k+1} = G_k + \left(1 + \frac{y_k^T G_k y_k}{s_k^T y_k}\right) \frac{s_k s_k^T}{y_k^T s_k} - \frac{G_k y_k s_k^T + s_k y_k^T G_k}{s_k^T y_k}$
- 该公式保证了只要初始 $G_0$ 正定且满足 $s_k^T y_k > 0$ ，后续所有 $G_k$ 永远正定。

复习必背结论（重点中的重点）

牛顿法快但贵，拟牛顿法通过秩修正实现快且省。
拟牛顿法的数学核心是满足拟牛顿方程。
BFGS 是 DFP 的对偶，因为其数值稳定性更好，成为了实际应用（如 Python 的 scipy.optimize）中的默认选择。
正定性是保证算法收敛到极小值（而非极大值或鞍点）的关键，BFGS 能够很好地维持这一性质。

约束优化

KKT条件:其实是对最优解的约束(其中g表示不等式约束,h表示等式约束)
alt text
理解:当最优解在小于零的可行域内,相当于系数lambda不起作用,当最优解在等于零的线上,乘积还是等于0

存在一个对偶误差:若两者取等则称强对偶
强对偶条件（原函数与不等约束均是凸函数、定义域是凸
开集、等式约束是仿射变换、存在一个绝对可行解）

e.g:对支持向量机的优化可以转化为一个二次规划问题
alt text
每次找两个alpha,固定其他变量来构建多个规划问题

$(\sum_i a_i)(\sum_j b_j)=\sum_i \sum_j a_ib_j$

核函数映射

待识别对象线性可分:可被低一维的超平面分割

cover and mercer定理

cover定理,普通位置点集满足下式

$\begin{aligned} C(m,n)&=C(m-1,n)+C(m-1,n-1)\\ C(m,n)&=2\sum_{i=0}^{n-1}\binom{m-1}{i}\text{ ways m points can be divided in n-dimensional } \end{aligned}$

待识别对象个数m确定的时候,其特征向量维度n越大,越可能线性可分
普通位置点集:n维空间中,该点集任意n+1个点不在同一个n-1维超平面中

kernal function
正常直接使用函数映射到更高维后算内积(计算量很大)
一种方法是直接使用核函数将原本的点变换为升维后的内积
mercer定理:一个函数可以作为核函数的充要条件是与其对应的核函数矩阵(就是把所有样本对带入核函数的结果排成的矩阵)为半正定矩阵
可结合拓展性
两半正定核函数的线性组合和乘积也是核函数
两个的元素乘积也是核函数

$\kappa(x_i,x_j)=g(x_i)\kappa_1(x_i,x_j)g(x_j)$

也是核函数

常见的核函数

多项式核

$\kappa(x,y)=(<x,y>+c)^q$

齐次有序单项式向量空间
n维向量的d阶单项式就是任取d个分量的乘积,认为乘积顺序有影响的就是有序
特征向量的所有d阶其次有序单项式组成向量

$C_d(x)=[x_{k_1}x_{k_2}...x_{k_d}|k_1,k_2,...k_d \in {1,2..n}]$

两个d阶齐次有序单项式组成的向量的内积等于原向量内积的d次方
特征向量x的0到d阶有序单项式各自与实数相乘构成的向量叫其d阶有序单项式向量(记为D)
D张成的空间就叫x的d阶有序单项式空间
在恰当选择系数的条件下

$<D_d(x),D_d(y)>=(<x,y>+1)^d$

齐次无序单项式向量空间
无序就是相乘的顺序不重要,各结论基本均和有序一致(单项式向量维数从d的排列降低为d的组合)

对多项式核:c为0退化为齐次,q为0退化为线性核,均为0就是核映射的幺元
多项式核均和一个齐次单项式空间内的内积对应,它是具有一定的可解释性的

径向基核

也叫RBF(radical basis function):因变量仅依赖自变量到原点距离的

高斯核函数
本质就是0到无穷阶的多项式核的和,令x=y得映射结果的范数恒为1,所以映射结果就是半径为1的超球面

$\kappa(x,y)=exp(- \frac{||x-y||^2}{2\sigma^2})$

理论上能任意线性可分,但是复杂,容易过拟合

幂指数核
数值更低,映射结果更分散,不敏感

$\kappa(x,y)=exp(- \frac{||x-y||}{2\sigma^2})$

拉普拉斯核:就是把幂指数核的分母换成sigma

sigmoid核

也叫多层感知器核,注意区分sigmoid激活函数

$\kappa(x,y)=tanh(\beta xy^T+r)$

性能度量

交叉验证
通过划分训练集和验证集选择最好的模型

简单交叉:通常8:2
k折交叉:分成k份每次取k-1个作训练,剩下的作验证
留一法:令k等于样本数
自助法:m个样本中随机抽一个,重复m次构造训练集,没抽到过的作验证集

混淆矩阵:真实标签和预测标签的矩阵c(i,j)表示实际是i而预测为j的样本数
PR曲线:预测时取不同阈值的precision-recall曲线
ROC:TPR-FPR(false precision rate)曲线

$\begin{aligned} TPR=\frac{TP}{TP+FN} FPR=\frac{FP}{FP+TN} \end{aligned}$

AUC:ROC曲线下的面积