模式识别与机器学习

考试题型

一、单项选择：8道5分=40分
二、简答题：10*6=60
QKV，交叉注意力，Q、K、V分别是什么？

零、简介

模式识别与机器学习 (Pattern Recognition & Machine Learning)

1.自学内容

(1)机器学习

机器学习直接来源于早期的人工智能领域，传统的算法包括决策树、聚类、贝叶斯分类、支持向量机、EM、Adaboost等等。
从学习方法上来分，机器学习算法可以分为监督学习、无监督学习、半监督学习、集成学习、深度学习和强化学习。

1.机器学习包含的模型：
线性模型、树模型、支持向量机、人工神经网络模型

2.强化学习是一种机器学习模型的学习方式(强化学习是一种机器学习方法)，目前机器学习主流学习方式大致有三种：有监督学习、无监督学习和强化学习

(2)机器学习和统计学中常见的流程

建模 → 学习(参数设计) → 预测

1.建模：
建模是根据问题需求构建一个数学模型或算法框架，用于描述数据特性和预测目标。这个阶段回答了“用什么模型来描述和解决问题”。
①线性模型：如线性回归、逻辑回归，适用于简单数据和线性关系。
②非线性模型：如决策树、支持向量机（SVM）、神经网络，适用于复杂数据。
③概率模型：如朴素贝叶斯、隐马尔可夫模型，适用于概率推断任务。

2.学习
(1)目标函数：
①回归问题：均方误差(MSE)
②分类问题：交叉熵损失
③其他任务：如强化学习中的奖励函数
(2)优化算法
梯度下降(Gradient Descent)算法：批量梯度下降、随机梯度下降(SGD)
(3)超参数调整
模型设计中无法直接从数据中学习的参数(如学习率、正则化系数)。
通过交叉验证或网格搜索选择最佳超参数。

3.预测
预测阶段是用训练好的模型对新数据进行推断或预测的过程。这个阶段回答了“模型如何解决实际问题”。
输入新数据、模型推断、评估预测效果、应用

(3)导数 vs 梯度

(4)KL散度

1.概念：两个概率分布之间的差异或信息损失的衡量方式
KL散度（Kullback-Leibler Divergence），又称为相对熵，是信息论和概率论中的一个重要概念，用来衡量两个概率分布之间的差异。KL散度被广泛用于机器学习、信息检索和统计学中。

2.定义：基于Jensen不等式

当且仅当 P(x)=Q(x) 时，KL 散度等于 0。

3.KL散度的非负性证明

4.应用
深度学习和概率模型中，用 KL散度衡量模型分布和真实分布之间的差异。
如变分自编码器(VAE)、生成对抗网络(GAN)等。

(5)凸优化问题

1.凸优化问题的标准形式
$$\underset{x}{\min }f(x)$$
f(x)是一个凸函数，定义在一个凸集C上
x是待优化的变量
约束条件可以是线性或非线性的，但是通常需要这些约束形成一个凸集。例如，线性约束$Ax\le b$或非线性约束$g_i(x)\le 0$ (其中$g_i(x)$是凸函数)

2.常见凸优化技术
(1)梯度下降法 (Gradient Descent)
梯度下降法是最常见的凸优化技术之一，特别适用于可微分且凸的目标函数。其基本思路是从某个初始点开始，沿着目标函数的负梯度方向（即下降最快的方向）逐步调整解的值，直到收敛到最优解。
$$x_{k+1}=x_k-\alpha ▽f(x_k)$$
(2)牛顿法（Newton’s Method）
(3)内点法（Interior Point Method）
(4)对偶方法（Dual Methods）
(5)分布式优化（Distributed Optimization）

凸优化问题：
用户提到的贪心策略问题，通常发生在非凸优化或离散优化中。

2.基本概念

数据 > 模型

训练集、测试集

分类、回归

损失：最小二乘线性回归

过拟合：模型太复杂 / 数据量太少，模型相对于数据复杂。训练集好，测试集差(Loss高)。 (泛化性差，只学到了表面，没有学到本质)

正则化(Regularization)：正则化是通过在模型的损失函数中添加额外项，以对模型的复杂性进行约束，防止过拟合。常用的正则化方法有L1正则化和L2正则化

机器学习方法：
(1)近邻法

(2)集成学习方法

(3)主动学习

3.典型的机器学习系统

1.医学图像诊断

2.时间序列识别

3.对话系统
①领域任务型对话系统：
以完成一项具体的领域任务为目标，如车载导航机器人和各公司的智能客服等
②开放域对话系统：
目的是满足用户的闲聊需求或者常识性问答需求，以产生内容丰富且有意义的问答，如闲聊型对话机器人等

4.异常检测

4.前沿研究方向举例

1.多视图机器学习

2.强化学习
(1)监督学习 vs 强化学习：
(2)适合强化学习：下棋、游戏AI

(3)离线强化学习

端到端：给输入，直接输出。中间过程不可知。
自动驾驶：CARLA(Car Learning to Act)

4.可信人工智能
对抗攻击：分类模型，加噪声，人发现没变化，机器却无法识别了。

一、逻辑回归

1.线性回归

1.最小二乘线型回归求解
2.概率线性回归
3.最小二乘与最大似然
(1)稀疏解：减少过拟合(1范数、2范数)、特征选择

L1范数(对应L1正则化)：绝对值之和
L2范数(对应L2正则化)：平方和开根

2.逻辑回归

逻辑回归是判别式的

逻辑回归可以加正则化。L2范数可微分，用梯度下降。L1用次梯度。

1.二类逻辑回归
逻辑函数也称为Sigmoid函数

2.多类逻辑回归

3.随堂练习

解析：
1.线性回归

2.逻辑回归
D.逻辑回归是线性分界面

二、贝叶斯学习基础

1.贝叶斯公式

概率分类：

贝叶斯公式：
$$P(A|B)=\frac{P(AB)}{P(B)}=\frac{P(B|A)\cdot P(A)}{\sum _{A}P(A)\cdot P(B|A)}$$

2.贝叶斯决策

贝叶斯决策（Bayesian decision）是概率框架下实施决策的基本方法，它通过综合考虑决策的后验分布和错误决策的损失来做出决策。其中，贝叶斯公式被用于计算后验分布。
贝叶斯决策的前提是假设：

贝叶斯决策分类：最小错误率、最小风险

召回率：召回率回答了这样一个问题：模型在所有需要找到的目标中，成功找到了多少？

最小风险贝叶斯决策会选择条件风险最小的类别

3.分类器的概念

1.概念
二类分类问题：要机器来判断一张图像是大熊猫还是小熊猫
多类分类问题：区分一张图片是大熊猫、小熊猫还是棕熊

分类器是一个计算系统，它通过计算出一系列判别函数的值做出分类决策，实现对输入数据进行分类的目的。
判别函数是一个从输入特征映射到决策的函数，其结果可以直接用于做出分类决策。
分类问题中，分类器会把输入空间划分成多个决策区域，这些决策区域之间的边界称作决策面或决策边界

2.构建方法
分类器的构建方法有很多种，常用的方法大致可以分为三大类，这里按照复杂度依次降低的顺序罗列。其中生成式模型和判别式模型都是基于概率框架，生成式模型构建所有观测的联合分布，而判别式模型只关心给定输入数据时输出数据的条件分布。

生成式模型 vs 判别式模型
①生成式模型：
②判别式模型：

3.分类器的错误率计算通常有三种方法：
①根据错误率的定义按照公式进行计算
②计算错误率的上界
③通过在测试数据上进行分类实验来估计错误率

4.基于高斯分布的贝叶斯分类器

5.朴素贝叶斯分类器

概念：
应用：适合文本分类、垃圾邮件检测。
属于：生成式

6.参数估计

(1)最大后验估计 MAP

最大后验估计(Maximum A Posteriori Estimation，简称 MAP)是统计学和机器学习中用来估计未知参数的一种方法。它是贝叶斯推断的核心方法之一，通过结合先验知识和观测数据进行参数估计。

最大后验估计的目标是找到使后验概率最大的参数值，即：

(2)期望最大化算法 (EM，expectation maximization)

对数联合关于后验的期望

(1)后验分布 ：$q(z)=p(z|x,\theta )$
它表示在给定观测数据 x和当前模型参数 θ的情况下，隐变量 z的分布。
给定观测数据x和当前参数θ，隐变量z的概率分布。这一分布的引入和使用是 EM 算法的核心所在。

它是EM算法中E步的核心，用于计算期望并指导参数更新(M步)

$$\mathrm{argmax}\ln \int p(x|z,\theta )\cdot p(z)dz\ge \int p(z|x)\cdot \ln p(x,z|\theta )dz-\int p(z|x)\ln p(z|x)dz$$

KL散度：

E步：

M步：

3.蒙特卡罗EM(Monte Carlo EM) 和 变分EM(Variational EM)

变分EM，最大化q，最大化θ，再最大化q…

7.随堂练习

(1)问题1：关于概率运算下面说法正确的是：
A.先验概率*似然概率=后验概率
B.联合概率/边缘概率=条件概率
C.贝叶斯分类决策中，通常类别作为先验概率，类条件概率作为似然概率
D.贝叶斯决策通常根据先验概率制定决策

解析：
A.要除一个条件
D.贝叶斯模型、朴素贝叶斯模型都是生成式模型，而不是判别式模型
答案：BC

(2)下面说法正确的是
A. 贝叶斯决策就是最小错误率决策
B. 贝叶斯决策中是否假设先验与最后决策结果无关
C.最小风险贝叶斯决策也需要计算类别的后验概率
D.朴素贝叶斯决策通常假设每个类别中的特征是相互独立的

答案：CD

(3)下面说法正确的是
A. 最大似然参数估计与最大后验参数估计得到的结果相同
B. EM算法仅适用于最大似然估计
C.EM算法中通常为了解决模型中有隐含变量时的参数估计问题
D.EM算法是交替执行求期望和求最大的运算

解析：
A.取决于先验
D.EM 算法包括两个步骤：
①E-step(期望步骤)：基于当前参数估计，计算隐含变量的期望。对数联合关于后验的期望。
②M-step(最大化步骤)：优化模型参数，使得对数似然函数最大化。

答案：CD

三、人工神经网络

1.感知机

2.多层神经网络

(1)神经元

1.多个输入，一个输出
2.线性之间，要有一个非线性的激活函数，否则全是wx+b，例如 w(w(wx+b)x+b)x+b，最后还是wx+b

(2)多层神经网络

1.常用的激活函数：
(1)Sigmoid：二分类、多个独立二分类
(2)tanh
(3)ReLU
(4)softmax：多分类
(5)恒等函数：回归问题

(3)反向传播算法

1.概念
反向传播算法（Backpropagation，简称BP）是神经网络中的一种常用算法，主要用于通过梯度下降法优化神经网络的权重，训练神经网络。它通过计算网络输出误差对每个权重的梯度，并将这个误差从输出层反向传播到输入层，从而调整每个权重的值，最终达到最小化误差的目的。

反向传播（Backpropagation）是神经网络训练中的一种重要算法，它通过计算损失函数相对于网络中每个参数的梯度，来更新神经网络的参数，以最小化损失函数。反向传播通常依赖链式法则来计算梯度，确保误差信息能够从输出层逐层传递到输入层，从而调整每一层的权重和偏置。

2.反向传播算法的工作原理
(1)前向传播
(2)计算输出层的误差
(3)反向传播误差
(4)更新权重

3.优点
反向传播算法通过链式法则的应用减少了计算量。具体来说，反向传播通过局部计算和逐层传播误差的方式，大大降低了计算复杂度，尤其是在深层神经网络中

4.反向传播的局限性
(1)局部最小值问题
(2)梯度消失问题

反向传播算法的核心公式：

3.深层神经网络

(1)浅层与深度神经网络

深度学习 效果优于 宽度学习

相同的参数，深度学习的错误率 比 宽度学习 更低，效果更好

前面几层在提取特征，类别共享。
理论上，宽度学习也能拟合任意函数，但是宽度学习需要的数据量比起深度学习大得多。

(2)过拟合问题

1.概念
过拟合问题是深度神经网络的主要挑战之一，其主要原因是模型过于复杂或者训练集过少。

2.解决
(1)早停止：
早停止是指在模型训练过程中，可通过观察验证集上的预测性能来
决定何时停止对参数的优化，从而可以在产生过拟合之前停止训练。
(2)权重衰减：
权重衰减是指为了防止得到的权重参数过大，而采取的在每步迭代中少量减少权重的方法
(3)丢弃法：
丢弃法是指在深度神经网络的训练过程中，对于网络中的神经单元(包括节点以及与之连接的边)，按照一定的概率将其暂时从网络中丢弃

(3)局部极值问题

1.多次随机初始化
2.随机梯度下降 (更快更好)
3.基于动量的梯度下降

(4)梯度消失问题

当使用反向传播方法求解梯度时，使用sigmoid函数或者tanh函数作为激活函数的深度神经网络随着网络层数的增加，从输出层到网络最初几层的反向传播得到的梯度的幅度值可能会急剧增大(梯度爆炸)或减小(梯度消失)

激活函数f的导数是0-1之间的数(sigmoid激活函数)，其连乘后，结果会变的很小，导致梯度消失。若初始化的w是很大的数，w大到乘以激活函数的导数都大于1，那么连乘后，可能会导致梯度爆炸。

4.常用的深度神经网络

(1)自编码网络

1.稀疏自编码
2.去噪自编码

(2)卷积神经网络 CNN

1.卷积层、卷积核(convolution kernel)
2.池化(pooling)：均值池化(average pooling)、最大池化(max pooling)
3.感受野
4.UNet：卷积+反卷积，图像分割、语义分割

卷积、激活、池化→卷积、激活、池化 (Input→Convolution→Activation→Pooling→…)

(3)循环神经网络 RNN：循环连接、顺序处理

1.概念：
循环神经网络（recurrent neural networks，RNN。
顺序处理：RNN 是一种顺序计算模型，它在处理每个时间步时，都依赖前一个时间步的计算结果。它是一个逐步的过程，即先处理第一个元素，再处理第二个元素，依此类推。这使得 RNN 在长序列上训练时容易受到梯度消失或梯度爆炸问题的影响。

2.原理、结构
①智能填空，与上下文有关.
②自回归
③循环连接

3.缺点
梯度消失问题，类似传话筒，文本很长时，传递消息就会出现较大误差

4.应用
①多对一：时序分类，如情感分析，行为识别
②一对多：时序生成，如图像描述
③多对多（对齐）：时序标注，如实体识别，填空
④多对多（非对齐）：机器翻译

①长短期记忆网络 (long short-term memory，LSTM)

遗忘门：决定了哪些信息被遗忘。
输入门：决定了哪些新的信息被加入到状态中。
输出门：决定了当前的隐藏状态输出哪些信息

②Seq2Seq

1.概念
Seq2Seq (Sequence-to-Sequence) 模型是基于RNN的一种深度学习架构，主要用于处理序列到序列的任务 (机器翻译、语音识别、文本摘要)等.

2.结构
①编码器 (Encoder)
②解码器 (Decoder)

在现代深度学习中，Transformer已经逐渐取代了传统的RNN架构，成为处理序列任务的主流方法。

(4)Transformer：自注意力机制、并行处理

1.概念
注意力，就是权重，加权

Transformer是一种seq2seq模型，其核心思想是使用注意力 (attention) 和自注意力 (self-attention) 机制。
注意力机制用于捕获输入序列和输出序列之间的关系。
自注意力机制用于捕获文本序列内部的依赖关系，构建对原始文本的语义表示。
其中的自注意力是一种特殊的注意力模型。

(1)注意力
注意力作为组件被嵌入在seq2seq神经机器翻译模型中，用于学习序列到序列的对齐关系
(2)自注意力
所谓自注意力，是指输入序列中的每个单词(或字)都要和该序列中的所有单词(或字)进行注意力计算。好处是学习序列内部的单词(或字)的依赖关系，捕获句子的内部结构。

2.原理
引入了Q K V：查询(query)、键(key)、值(value)

Transformer是并行的。
GPT不是并行的。

(5)变分自编码器 VAE

$$p(x)=\int p(x|z)p(z)dz$$

变分分布：通常用q(z∣x) 是对潜在变量 z 的一个近似后验分布

变分下界(ELBO)的推导：

最大似然 = 重建损失 - KL散度

重参数化：$z=\mu (x)+\sigma (x)\cdot ϵ$

(6)对抗生成网络 GAN：生成

1.组成
生成器(Generator) 和 判别器(Discriminator)

CNN是GAN的重要组成部分。CNN 是 GAN 架构中的关键组件，特别是在图像生成和图像分类等任务中。CNN 用于提取图像的空间特征、进行图像合成和生成，以及判断图像的真实性

2.GAN的应用：
①超分辨率重建(SR，Super-Resolution Reconstruction)
②Deepfake换脸

3.例子
G和D对抗，如：印钞机和验钞机

4.公式

5.CircleGAN

(7)扩散模型 SD：生成

预测原本的噪声

Stable Diffusion

5.随堂练习

(1)神经网络

解析：
C.不一定相同。取决于用的是什么激活，什么池化
D.也可以大于

答案：B

(2)变分自编码 VAE

解析：
A.是编码网络

答案：BCD

(3)生成对抗网络 GAN

解析：
A.应该是打分是0.5
B.不需要
C.等价，但效果不一样

答案：D

VAE和GAN，分别实现风格迁移：如自然场景生成梵高的画风：
①条件生成，条件VAE：要求训练集必须是配对好的
②循环GAN：不需要配对，只要有A风格和B风格，内容不一样也可以

四、支持向量机

0.概念

支持向量机(SVM，support vector machine)，又称大间隔分类器

1.大间隔原理

H1 分界面 (超平面) 的 泛化性 更好：离分界面距离最小的点，距离分界面的距离尽可能地大
(边界离两个数据集都比较远，再来新的点，不容易被误分。)

找到一个最宽的板子，分开红豆和绿豆

分界面、间隔面、支持向量

1.分界面：划分两类
2.间隔面：离分界面最近的点，对分界面作平行线

蓝色线是间隔面，红色线是分界面。
蓝色线之外：α=0，ξ=0，β>0
蓝色线上：0<α<C
两个蓝色线内：α=C，ξ>0，β=0

3.支持向量：
支持向量是那些位于分类间隔边界上或间隔内部的样本点，对应 拉格朗日乘子${\alpha }_i>0$

2.基本分类模型

1.基本分类模型

2.大间隔思想
1.二范数（Euclidean norm），其定义为向量各个分量的平方和的平方根。
$$||w|{|}_2=\sqrt{w_1^2+w_2^2+...+w_n^2}$$
2.假设直线为 $w_1{x}_1+w_2{x}_2+b$

s.t. 是"subject to"的缩写，表示“在…条件下”，即“约束条件是…”

解约束条件：
①$\min f(x_1,x_2,...,x_n)$，s.t. $x\ge 0$：可用重参数化技巧：令 $x=e^y$
②$\min f(x_1,x_2,...,x_n)$，s.t. $\sum _{i=1}^n{x}_i=C$：先求两个，其他为常数，就解出来了一个x。以此类推。

3.拉格朗日对偶优化

(1)概念

凸优化问题：极值点就是最值点

max (maximum，最大值)：是一个点
min (minimum，最小值)：是一个点
sup (supremum，上确界)：可能仍是一个函数
inf (infimum，下确界)：可能仍是一个函数

(2)拉格朗日对偶函数、弱对偶

1.拉格朗日对偶函数： $$g(\lambda ，\mu )=\underset{x}{\inf }L(x,\lambda ,\mu )$$
永远小于$f_0(x)$，即是拉格朗日函数关于原问题的下界

2.弱对偶：
对偶函数取最大值，近似逼近 $f_0(x)$的最小值

根据 拉格朗日弱对偶性，对于任意的拉格朗日乘子 $\lambda \ge 0$和$\mu$，对偶函数值$g(\lambda ,\mu )$总是小于等于原问题最优值 $p^{\ast }$，即 $$g(\lambda ,\mu )\le p^{\ast }$$
这是拉格朗日对偶方法的基础性质，适用于任何优化问题，无论是否是凸优化问题。

类似 鞍点

(3)强对偶

①互补松弛条件

互补松弛条件 (Complementary Slackness)：两项相乘为0，则至少有一项为0 (另一项就可以松弛，不为零)

②KKT条件

KKT条件（Karush-Kuhn-Tucker 条件）是非线性优化问题中一种非常重要的必要条件，广泛应用于求解带有约束的优化问题，尤其是在 约束优化 和 凸优化 中。KKT条件为最优解的判定提供了必要条件，尤其适用于非线性规划问题。

1.概念
KKT条件：约束优化问题的最优解的判定条件

2.KKT条件的组成
①可行性条件
②拉格朗日乘数条件
③互补松弛条件
④梯度条件

3.KKT条件与强对偶
满足强对偶，则一定满足KKT条件；
但是满足KKT条件，不一定满足强对偶。
即KKT条件是强对偶的必要不充分条件。
例外：在满足 Slater 条件的凸优化问题中，两者可以等价

③强对偶

强对偶：原问题的最优值等于对偶问题的最优值，即 $p^{\ast }=d^{\ast }$

p*：原问题的最优值
d*：对偶问题的最优值

弱对偶性：矮个子里最高的 ≤ 高个子里最矮的

4.线性不可分数据的分类

(1)松弛变量ξ

1.松弛变量ξ：有一定的容错，代表容错率。${\xi }_i$是支持向量机中的 松弛变量，用于表示分类点偏离分隔超平面的程度。

①ξ=0：完全正确分类，可能不属于支持向量
②0<ξ<1：正确分类，但位于分类间隔内，是支持向量
③ξ>1：分类错误

2.折衷参数C
折衷参数C：C越大，则松弛变量ξ越小，容错越小，容易过拟合，表现为 训练集效果好，测试集效果差。
C越小，则松弛变量ξ越大，容错越大，容易欠拟合，表现为 训练集效果差，测试集效果也差。

点到分界面的距离：$\frac{1}{||w||}$

3.拉格朗日乘子：${\alpha }_i$、${\beta }_i$
(1)${\alpha }_i$：用于处理 分类约束条件 的拉格朗日乘子变量
${\alpha }_i$的作用：控制分类约束是否被满足。
(2)${\beta }_i$：用于处理 松弛变量非负性约束 的拉格朗日乘子变量
${\beta }_i$的作用：确保松弛变量非负。
(3)值是$f(x^{\ast })=w^T{x}^{\ast }+b$

(2)核方法

1.核方法：通过将数据从原始空间映射到一个高维特征空间，在这个高维空间中，使得非线性问题变得线性可分。

核方法的前提：优化目标中要有样本的内积。$x_i^T{x}_j$，即 $kernel(x_i,x_j)$

在许多问题中，数据在低维空间中是非线性不可分的，但在更高维度的特征空间中可能变得线性可分。核方法通过引入一个核函数（Kernel Function）来隐式地完成这种映射，而无需明确地计算高维特征空间中的坐标。

2.映射

将原始输入空间 X 的样本点映射到一个高维（甚至无限维）的特征空间 F。

3.核函数
核函数$K(x,z)$是原始空间中的一个函数，它等价于高维空间中两个样本点的内积：

核方法的核心在于，直接利用核函数$K(x,z)$来计算，而不需要显式地进行高维映射$ф(x)$。

并不是所有的距离函数都可以作为核函数。一个函数要成为合法的核函数，必须满足 Mercer 定理，即其对应的核矩阵必须是 半正定的（positive semi-definite, PSD）

4.核方法的核心思想：
通过核技巧（Kernel Trick）避免显式地将数据映射到高维空间，而是在低维空间中通过计算核函数$K(x,z)=ф(x{)}^Tф(z)$代替高维内积计算，从而有效解决高维计算复杂性问题。

5.支持向量机回归

SVM：①基本只能做二分类 ②泛化性好，不容易过拟合

上文讲的是SVM用于分类问题 (尤其是二分类)，其实最大间隔的思想同样适用于回归问题。

6.模型扩展

双平面SVM：
两个分布的分界面的角平分线

7.随堂练习

(1)核方法、核函数

解析：
C.并不是所有的距离函数都可以作为核函数。一个函数要成为合法的核函数，必须满足 Mercer 定理，即其对应的核矩阵必须是 半正定的(positive semi-definite, PSD)。C错误。

答案：ABD

(2)拉格朗日对偶优化

解析：
B.注意是小于等于，不是小于。B正确。

答案：ABC

(3)支持向量机优化

解析：
A.SVM的SMO优化算法。A错误。
B.当使用核方法时，支持向量机不再显式地计算$\omega$，而是通过核函数$K(x_i,x_j)$，间接计算数据点之间的相似性。具体来说，模型的决策函数依赖于对偶参数${\alpha }_i$和核函数的线性组合，而不是直接计算$\omega$。因此，无法显式求解$\omega$的具体数值。B正确。
C.互补松弛条件是支持向量机优化问题中的重要性质，用于连接对偶变量${\alpha }_i$、约束条件和松弛变量${\xi }_i$，通过互补松弛条件：${\alpha }_i(y_i(w^T{x}_i+b)-1+{\xi }_i)=0$。可以根据支持向量点的状态，求解出偏置项b。C正确。
D.对偶参数alpha>0的样本才是支持向量。D错误。

答案：BC

五、聚类

本讲学习目标：
①理解聚类的两大类方法
②掌握K-均值聚类方法，理解模糊K-均值聚类的原理
③掌握谱聚类方法
④掌握高斯混合模型聚类方法
⑤掌握DBSCAN聚类方法

1.K-means聚类

K-means聚类 (K-均值聚类)

(1)算法介绍

①概念

1.聚类任务：
①在相同簇中的数据尽可能相似
②在不同簇中的数据尽可能不同

2.聚类方法：
①基于数据间相似度的方法
②基于密度估计的方法

3.K-均值（K-means）：
将K个聚类簇的中心作为簇的代表，希望所有数据点与其所在聚类中心
的距离总和最小

②算法步骤

K-means的具体实现包括以下步骤：
(1)初始化
①从数据集中随机选择k个数据点作为初始簇中心。
②也可以通过优化方法(如K-means++)选择初始中心以提升算法性能。
(2)分配数据点到簇

(3)更新簇中心

(4)重复迭代
重复步骤 2 和 3，直到簇中心不再发生显著变化或达到预设的迭代次数

③公式讲解

某个簇，这个簇走了一个样本点，那么该簇的总损失会下降。
同理，一个簇增加了一个样本点，该簇的总损失上升。

K-means的目标就是不断移动各个样本点，不断迭代，使得让所有簇的总损失最小。

1.公式
K-means的目标函数
目标函数是最小化簇内误差平方和，公式如下：
$$J=\sum _{k=1}^K\sum _{n=1}^{N}I(z_n=k)||x_n-{\mu }_k|{|}^2$$
K：簇的数量
N：数据点的总数
$x_n$：第n个数据点
${\mu }_k$：第k个簇的中心
$I(z_n=k)$：一个指示函数，若数据点$x_n$属于簇$k$，，则取值为1，否则为0

目标是找到最佳的簇中心${\mu }_k$ ，使得所有数据点到其对应簇中心的距离平方和$J$最小

2.均值μ的变化：
(1)数据点离开簇$i$

(2)数据点加入簇$j$

(2)模糊K-均值聚类 (Fuzzy K-Means)：加权

在每个组里都有兼职
即该样本点在多个簇中，只占部分比例，要有一个加权系数

①聚类数目的确定：类数K越多，损失越小

误差会随着聚类数目K的增多（假设从当前聚类结果中取出一个数据点为新簇）而逐渐减小，但是减小的幅度在变化。
通常情况下，在聚类数目较少时，误差会随着数目的增加而大幅度减小，但是在聚类数目达到某个值后，误差减小速度会变缓，这个值可定为聚类数目。

手肘法：如图，应选K=4。因为从K=4开始，损失下降速度已不明显，边际效益递减。

2.谱聚类

谱聚类是一种基于图论的聚类算法，与K-means、模糊K均值等方法不同，它不直接在样本的原始特征空间中进行聚类，而是通过对样本间的相似度关系构造图，利用图的谱（特征值和特征向量）信息实现聚类。
谱聚类特别适合处理非凸形状簇或复杂数据分布，在处理非线性分布数据时表现优异。

(1)概念：谱聚类 (Spectral Clustering)

①预处理：构建代表数据集的无向图并计算相似度矩阵
②谱表示：构造相应的拉普拉斯矩阵，并且计算拉普拉斯矩阵的特征值和特征向量，其中一个或多个特征向量构成了所有数据点在新的空间中的表示
③聚类：使用聚类算法（如𝐾-均值）对新的数据表示进行聚类

当我们的数据具有紧凑性、凸数据，K-means效果好
但是具有连接结构的数据，K-means就失效了，应该用谱聚类，谱表示

(2)步骤

①定义最优切割的优化目标

1.首先，定义最优切割的优化目标：要求切割后两个簇的相似性最低 (看起来像是相互之间的距离尽可能地大)

相似度矩阵𝑊和度矩阵𝐷：

2.构造相似图

3.最优切割的优化问题通常有两种表达方式：
①比率切割 (ratio cut)
②归一化切割 (normalized cut)

②计算图拉普拉斯矩阵

投影到一个维度空间，在新的空间用K-means聚类。
特征值分解
拉普拉斯矩阵是根据相似度矩阵来定义的

要求是个正交阵，即 $s.t.H^{T}H=I$
H是特征向量矩阵。I是正交矩阵(orthogonal matrix)。

Q是正交矩阵
I 或 E是单位矩阵

根据构造的相似图，计算图的拉普拉斯矩阵L。常见的拉普拉斯矩阵形式：
未归一化拉普拉斯矩阵：$L=D-W$

<1>比率切割：每个簇的个数不能太少

<2>归一化切割(Normalized Cut)：一种图划分算法

3.高斯混合模型(GMM) 聚类

高斯混合模型（Gaussian Mixture Model, GMM）是一种基于概率的聚类方法，是混合模型的一种特例，用于描述一个数据集由多个高斯分布组成的情况。GMM通过优化混合参数来拟合数据分布，并将数据点划分为不同的类别。以下从多个角度详细介绍GMM的概念、原理、优缺点以及应用。

(1)模型表示

(2)模型推理与参数估计

1.后验概率：
$$p(z_n|x_n)=\frac{p(x_n|z_n)\cdot p(z_n)}{p(x_n)}$$

2.步骤：
(1)参数估计(最大似然估计)
(2)EM算法

③EM算法的步骤 (复习)

(1)初始化
(2)E步 (期望步骤)： 计算每个数据点属于第k个高斯分布的责任值
(3)M步 (最大化步骤)：更新模型参数 ${\pi }_k，{\mu }_k，{\sum }_k$
(4)重复迭代

(3)GMM与K-means的区别

GMM：除了衡量每个点到我的中心的距离，还要考虑这个簇的方差

马氏距离（Mahalanobis Distance）是以 印度统计学家普拉萨特·马哈拉诺比斯（Prasanta Chandra Mahalanobis，1893-1972） 的名字命名的。他是现代统计学的重要奠基人之一，也是印度统计研究所（Indian Statistical Institute）的创始人。
马哈拉诺比斯提出了马氏距离，用以衡量数据点与数据分布之间的距离。与欧几里得距离不同，马氏距离考虑了数据的协方差结构，因此在处理高维数据和相关变量时具有重要的应用价值。

(4)GMM的应用场景

GMM因其灵活性和概率模型的特点，广泛应用于以下领域：
①图像分割：如背景与前景分离。
②模式识别：人脸识别、语音识别中的特征建模。
③异常检测：通过概率分布识别数据中的异常点。
④数据降维与分类：结合PCA等方法对复杂数据集进行特征提取和分类。

4.DBSCAN聚类

DBSCAN 不需要事先指定聚类的数量，能够有效识别任意形状的簇，并可以自动区分噪声点。

1.概念
Density-Based Spatial Clustering of Applications with Noise (DBSCAN) 一种基于密度，对噪声鲁棒的空间聚类算法。
基于密度，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

2.特点
①对远离密度核心的噪声点鲁棒。
②无需知道聚类簇的数量。
③可以发现任意形状的聚类簇。

3.应用
DBSCAN通常适合于对较低维度数据进行聚类分析

4.思想

5.三类数据点
①核心点 (Core Point)
②边界点 (Border Point)
③噪声点 (Noise Point)

6.四类关系

7.利用数据关系聚类

8.DBSCAN的步骤
①临时簇
②合并临时簇

9.DBSCAN的缺点
维度高了不行

5.随堂练习

(1)K-means

C.模糊K-均值聚类，必须需要全部的样本点。(因为要每个点在所有簇中都要占据一定的比例)

答案：AC

(2)高斯混合模型聚类

答案：ABCD

(3)谱聚类

解析：
B.

答案：ABCD

六、强化学习

1.基本概念与理论基础

(0)策略学习：同策略、异策略

(1)有环境模型、无环境模型

有环境模型(model-based)：智能体能够获取环境变化信息，能够提
前知道奖励和后续状态。Eg., 已知迷宫地图，走迷宫（可在脑中预演）
无环境模型(model-free)：智能体只有执行策略，通过与环境交互，
才能知道奖励和后续状态。Eg., 不知迷宫地图，走迷宫
五子棋和王者荣耀游戏控制是有环境模型还是无环境模型呢？

看你能否提前获得

(2)马尔可夫决策过程

当前的行为与前面n个有限的状态有关。

(3)贝尔曼期望方程

动作价值函数 (Action-Value Function)
①Q (Quality)：动作值函数，评估状态-动作对的期望回报。
②V (Value)：状态值函数，评估单个状态的期望回报。
③π (Policy)：策略，定义了智能体在每个状态下采取动作的概率分布。

①状态值函数 (State Value Function)：$V^{\pi }(s)$

状态值函数 $V^{\pi }(s)$ 表示在给定策略π下，从某一状态s开始，能获得的期望累计回报。
它衡量的是一个状态的“好坏”程度，具体定义为：

从状态 s 开始，遵循策略 π 行动。

②动作值函数 (Action Value Function)：$Q^{\pi }(s,a)$

动作值函数 $Q^{\pi }(s,a)$ 表示在给定策略 π 下，从某一状态s开始采取动作a后，能获得的期望累计回报。
它衡量的是在特定状态下采取特定动作的“好坏”程度，具体定义为：

③策略 $\pi (a\mid s)$

目的：学习一个好的策略π

(4)状态动作值函数

状态动作值函数，简称动作值函数

(5)最优策略的评估、贝尔曼最优策略：异策略

2.规划：有环境模型的评估与控制

GridWorld: Dynamic Programming Demo：https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html

3.无环境模型的控制：基于值函数

(1)蒙特卡洛控制：异策略

(2)时序差分控制：SARSA：同策略

(3)基于 Q学习(q-learning) 的异策略控制

Q学习 (Q-Learning)，基于贝尔曼最优方程，是异策略，目标是通过逐步更新 Q(s,a) 值，逐渐接近最优。
q-learning 中有两个重要的概念，一个是状态，一个是动作：
$$Q_{\pi }(s,a)=Q_{\pi }(s,a)+\alpha [r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)]$$
s：当前状态
a：当前动作
s’：下一状态
r：即时奖励
α：学习率
γ：折扣因子
$\underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })$：从下一状态s’开始所能获得的最大值

Q Learning 介绍：https://wizardforcel.gitbooks.io/learn-dl-with-pytorch-liaoxingyu/content/7.1.html

$Q(3,1)=R_{3,1}+\gamma \cdot \max (Q(1,3)，Q(1,5))=0+0.8\ast 0=0$
$Q(1,5)=...$

Q-Learning与Dijkstra的区别：

(4)基于Q学习的深度Q网络控制

4.无环境模型的控制：基于策略

(1)蒙特卡洛策略梯度法 和 REINFORCE算法

(2)行动者-评论者算法

基于值函数：
基于策略：有一个策略网络

5.随堂练习

(1)状态值函数、状态动作值函数

解析：
C.只能获得下一个状态动作值，不能获得当前的状态动作值

答案：BD

(2)策略迭代算法、值迭代算法

C.不需要交替
D.不改进

答案：AB

(3)强化学习

答案：AC

(4)强化学习

(1)基于策略的方法：
B. Actor-Critic 算法
D. 蒙特卡洛策略梯度

(2)非基于策略的方法：
A. 深度 Q 学习
C. 蒙特卡洛控制 [基于值]

(1)基于贝尔曼最优方程的算法是：
①值迭代
②Q学习

(2)基于贝尔曼期望方程的算法：
①策略迭代
②SARSA

七、主成分分析、相关的谱方法

主成分分析(PCA)：无监督的
线性判别分析(LDA)：有监督的

1.主成分分析 PCA

PCA投影完后，特征相互独立。

①特征选择：L1正则化
②特征提取：乘一个矩阵d×D
$X\in R^D\to \tilde{X}\in R^D$
$\tilde{X}=W^T\cdot X，W\in R^{D\times d}$，W称为投影矩阵，u称为投影向量

(1)最大化方差

①概念

①协方差矩阵S：D×D，是对称矩阵，$S\in R^{D\times D}$
②投影向量u：D×1
③谱聚类拉普拉斯矩阵：n×n
④Kernel矩阵：n×n

一维刻画方差，向量刻画协方差。
空间相互独立，协方差矩阵就是对角阵。只有自己和自己有一个自协方差，即是方差

②协方差矩阵S

1.协方差矩阵S的定义为：
$$S=\frac{1}{N}\sum _{i=1}^N(x_i-m(x))(x_i-m(x){)}^T$$
$D$：数据的维度
$N$：样本数量，即数据点的总数

其中：
$x_i$：第i个观测数据点，属于$R^D$
$m(x)$：数据的均值向量，计算公式为：$m(x)=\frac{1}{N}\sum _{i=1}^N{x}_i$，是一个D维向量

2.协方差矩阵S的意义：
协方差矩阵S是主成分分析(PCA)的核心：
①PCA的目标是将数据投影到一个子空间，使得投影后的数据方差最大化。
②协方差矩阵的特征值和特征向量决定了最佳投影方向（主成分），对应于最大化方差的方向。

③m维度

$\max Tr[U^T]SU$

①中心化：所有数据都减去均值
②标准化：除以标准差s，即除方差的开根
③归一化：让所有数据都压缩到[0,1]

④讲义

$S{u}_1=\lambda u_1$，即投影向量u1是协方差矩阵S的特征向量。

(2)最小化误差

主成分分析的另一种定义方法以最小化原始数据与投影后数据的距离平方和误差为优化目标。

①最小化误差的思想，是如何将原始数据点 $x_n$ 从原始 D-维空间A转换到一个新的D-维空间B 中，同时最小化投影误差。
②核心思想：用新空间的正交基U表示原空间的数据，同时最小化误差。

(3)主成分分析与K-L变换

总类内散度矩阵

2.概率PCA （PPCA）

(1)概念

概率PCA(Probabilistic PCA, 简称 PPCA)是一种基于概率模型的主成分分析(PCA)，由Tipping和Bishop于1999 年提出。它将PCA解释为一个线性高斯生成模型，并提供了PCA的概率框架。

与传统PCA不同，PPCA：
①将数据的生成过程建模为 潜变量(latent variables) 和噪声的组合。
②基于最大似然估计（MLE）或贝叶斯推断来求解主成分方向。

(2)概率PCA与传统PCA的区别

PPCA与PCA的关系：当噪声方差 ${\sigma }^2\to 0$ 时，PPCA退化为传统PCA。

(3)概率PCA的优点

①概率解释：PPCA提供了一个明确的概率模型，能够量化不确定性。
②噪声建模：PPCA显式地建模了观测数据中的噪声。
③撒播缺失数据处理：由于PPCA是基于概率的，可以通过期望最大化（EM）算法处理缺失数据。
④与PCA的关系：当噪声方差 ${\sigma }^2\to 0$ 时，PPCA退化为传统PCA。

(4)PPCA的计算过程

(5)潜变量z

1.概念
潜变量(Latent Variables)是数据中隐藏的、不直接观测到的变量，用于解释观测数据的结构或特征。
在概率主成分分析(PPCA)中，潜变量z是一个低维空间中的向量，用来表示高维观测数据x在低维空间中的投影。

2.定义
PPCA假设数据x是通过潜变量z通过一个线性变换生成的，表达式为：$x=Wz+\mu +ϵ$
其中：
$W$：投影矩阵 (从潜变量到观测空间的线性变换)
$\mu$：测数据的均值。
$ϵ$：高斯噪声，$ϵ\sim$

3.潜变量z的作用
①降维
②特征表示
③生成模型
④数据重建

(6)讲义

3.核PCA (kernel PCA)

(1)概念

核主成分分析(Kernel PCA)是一种非线性数据降维方法，它是主成分分析(PCA)的扩展，通过引入核技巧(kernel trick)，可以捕捉数据的非线性结构。

普通的PCA假设数据分布在一个线性子空间中，而核PCA通过将数据映射到一个高维的特征空间，在特征空间中执行PCA，从而能够处理非线性数据。

(2)核心思想

(3)核PCA与普通PCA的比较

(4)讲义

当前样本点和所有的相似度，很像样本之间的注意力
通过它跟其他的关联性，去刻画一种新的表示

4.相关的谱方法

(1)线性判定分析 (LDA)

0.概念

(1)线性判别分析(LDA，Linear Discriminant Analysis)。

(2)LDA：
①类间：最大化均值距离
②类内：最小化类内散度

(3)概念
LDA是一种统计方法，主要用于分类和降维。它通过投影将数据从高维空间映射到低维空间，同时最大化类间的可分性(类间方差)并最小化类内的紧凑性(类内方差)

线性判别分析（LDA）是一种有监督的降维方法，主要用于分类和数据降维任务。LDA通过投影将数据从高维空间映射到低维空间，目标是最大化类间可分性并最小化类内分散性，以便在降维后的空间中实现更好的分类效果。

(4)LDA的目标函数

(5)LDA的核心思想

①二类数据的线性判别分析

②多类数据的线性判别分析

<1>类间散度矩阵$S_B$

类间散度描述的是每个类别的均值相对于整体均值的散布：
$$S_B=\sum _{c=1}^C{N}_c(m_c-m)(m_c-m{)}^T$$
其中：
$m_c$：第c类的均值
$m$：所有数据的全局均值
$N_c$：第c类的样本数

<2>类内散度矩阵$S_W$

类内散度描述的是每个类别内部样本的散布（偏离其类别均值的程度）：
$$S_W=\sum _{c=1}^C\sum _{n=1}^{N_c}(x_n^c-m_c)(x_n^c-m_c{)}^T$$
其中：
$x_n^c$：属于第c类的样本

(2)典型相关分析 (CCA)

CCA是前融合

Clip模型：语义一致，相关性高

5.随堂练习

(1)PCA

答案：ACD

(2)线性判别分析LDA

解析：
A.PCA是无监督的，LDA是有监督的
B.PCA可以降维到任意维，LDA有限制
D.PCA投影后是对角阵，而LDA不一定

答案：AC