机器学习笔记

统计学习方法

赫尔伯特.西蒙：”如果一个系统能够通过执行某个过程改进它的性能，这就是学习。“

1.1 统计学习 基本概念

• 对象： 数据
• 目的： 对数据预测与分析
• 方法： 监督学习，无监督学习，强化学习
• 三要素： 模型，策略，算法

1.2 统计学习分类

1.2.1监督学习：

学习输入到输出的统计规律。

1. 输入空间，输出空间，特征空间：输入与输出对成为样本
2. 联合概率分布：假设输入X输出Y遵循联合分布概率P（X，Y），表示分布密度函数
3. 假设空间：学习范围的确定
4. 模型：用训练数据集学习一个模型，再用模型对测试样本集进行预测。由学习系统和预测系统完成。

1.2.2无监督学习：

从无标注数据中学习预测模型，学习数据中的统计规律或潜在结构。

1. 使用无标注数据学习或训练
2. 可以用于对已有数据的分析，也可以对未来数据预测

1.2.3强化学习

智能系统在与环境的连续互动中学习最优行为策略的机器学习问题，本质为学习最优的序贯决策

1. 智能系统与环境互动：在每一步t，智能系统在环境中观测到一个状态st和一个奖励rt，采取一个动作at。环境根据智能体选择的动作，决定t+1的状态与奖励。目标是长期奖励的最大化。
2. 马尔可夫决策过程

1.2.4半监督学习与主动学习

半监督学习，使用少量标注数据与大量未标注数据
主动学习，机器不断主动给出实例让教师进行标注，然后利用标注数据学习预测模型

1.3 按模型分类

1. 概率模型与非概率模型：
   • 概率模型：决策树，朴素贝叶斯，隐马尔可夫，条件随机场，概率潜在语义分析，潜在迪利克雷分配，高斯混合模型
   • 非概率模型：感知机，支持向量机，k近邻，adaboost，kmeans，潜在语义分析，神经网络
     在监督学习中，概率模型是生成模型，非概率模型是判别模型
     概率模型可用基本概率加法和乘法模型进行概率推理。
2. 线性模型与非线性模型：
   • 针对非概率模型，如果y=f（x）或z=g（x）是线性函数，则称模型为线性模型
   • 否则为非线性模型
3. 参数化模型与非参数化模型：
   • 参数化模型假设模型参数维度固定，模型可用有限维数刻画
   • 非参数化：维数不固定或无穷大，随训练数据量增大而增大

1.4按算法分类

1. 在线学习：每次接受一个样本进行预测，之后学习模型
2. 批量学习：一次接受所有数据，学习模型之后进行预测

1.5三要素

1. 模型：模型的假设空间包含所有可能的条件概率或决策函数
2. 策略：在假设空间中寻找最优模型
   • 损失和风险函数：经验风险是模型关于训练样本集的平均损失记作Rexp（f）当样本容量趋于无穷时，经验风险趋于期望风险。
   • 经验风险最小化和结构风险最小化
   • 过拟合：为了减少训练误差而使得模型复杂度增加，导致测试误差增大（M次多项式拟合问题）
3. 算法：模型的具体计算方法

1.6正则化与交叉验证

1. 正则化：在经验风险上加一个正则化项，模型越复杂，正则化数越大。
2. 交叉验证：给定的数据切分，组合成为训练集与测试集，反复训练

1.7泛化能力

• 指由该方法学习到的模型对未知数据的预测能力
• 设学到的模型为f

$$R_{exp}(\widehat{f})=E_{p}[L(Y,\widehat{f}(X))]=\int_{\chi * \gamma }^{}L(y,\widehat{f}(x))P(x,y)d_{x}d_{y}$$

1.8生成模型与判别模型（在监督学习中）

1. 生成方法：由数据学习联合概率分布P（X，Y），求出P（Y|X）作为预测的模型： $$P(Y|X)=P(X,Y)/P(X)$$
   • 因为模型表示了给定输入X产生输出Y的生成关系
   • e.g.朴素贝叶斯，隐马尔可夫
   • 特点：可以还原出联合分布概率P（X，Y），收敛速度更快
2. 判别方法：直接学习决策函数f（x）或条件概率分布P（X，Y）作为预测的模型。关心的是对给定的输入X，应预测什么样的输出Y
   • 特点：直接面对预测，直接学习P（Y|X）或决策函数f（X），可以对数据进行各种程度上的抽象、定义特征并使用特征，可以简化学习问题。

1.9 监督学习应用

1. 分类问题
2. 标注问题
   • 学习一个模型，使它能够对观测序列给出标记序列作为预测（单词序列预测，词性标注）
3. 回归问题
   • 预测输入变量与输出变量之间的关系，特别是输入变量的值发生变化时，输出变量随之发生的变化。

2.1感知机模型

• 感知机是二类分类的线性分类模型，输入为特征向量输出为类别，取+1，-1.将实例划分为正负两类分离超平面属于判别模型。 $$f(x)=sign(\omega x+b)$$
• $\omega$叫做权值向量，b叫做偏置 $$sign(x)=\left\{\begin{matrix} +1 &x\geqslant 0 \\ -1& x<0 \\ \end{matrix}\right.$$
• 假设空间是特征空间中所有线性分类模型
• 训练数据集：实例的特征向量及类别（xi，yi）

2.2感知机学习策略

1. 线性可分性：存在某个超平面S：$\omega x+b=0$能够将数据集的正负实例点完全正确划分到超平面的两侧，称数据集为线性可分数据集
2. 感知机学习策略：目标是求得一个能够将训练集正实例点和负实例点完全正确分开的超平面。确定$\omega$和b，使损失最小化。
   • 损失函数：误分类点到超平面的总距离 $$L(\omega ,b)=-\sum_{xi\in M}^{} y_{i}(\omega x_{i}+b)$$

2.3感知机学习算法

• 随机梯度下降：学习率$\eta$(步长）（0-1），

1. 任选取超平面w0，b0，
2. 选取数据（xi，yi）
3. 若$y_{i}(\omega x_{i}+b)\leqslant 0$ $$\omega<=\omega +\eta y_{i}x_{i}$$ $$b<=b+\eta y_{i}$$
4. 跳回（2），直到没有误分类点

2.4感知器学习算法的对偶形式

• 基本想法，将w和b表示为实例xi和标记yi的线性组合的形式，通过解其系数球的w和b。初始w和b为0，经过对误分类点的修改后，最后学习到的w和b可以表示为：(这里$\alpha$i=ni$\eta$) $$\omega=\sum_{i=1}^{N} \alpha _{i}x_{i}y_{i}$$ $$b=\sum_{i=1}^{N} \alpha _{i}y_{i}$$
  1. a=0,b=0
  2. 在训练集中选取数据（xi，yi）
  3. 如果$y{i}(\sum{j=1}^{N}\alpha {j}y{j}x{j}\cdot x{i}+b)\leqslant 0$ : $$\alpha_{i}<=\alpha _{i}+\eta$$ $$b<=b+\eta y_{i}$$
  4. 转到2直到没有误分类数据

3.1k近邻算法

• 给定一个训练数据集，对于新的训练实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例多数属于某个类，就把该输入实例分为这个类。

3.2k近邻模型

1. 模型：根据训练集，距离度量，k值，以及决策规则，将特征空间划分为一些子空间。
2. 距离度量：点xi与xj的Lp距离： $$L_{p}(x_{i},x_{j})=(\sum_{l=1}^{n}\left|x_{i}^{(l)}- x_{j}^{(l)}\right|^{p})^{\frac{1}{p}}$$
   • p=2,欧氏距离

$$L_{2}(x_{i},x_{j})=(\sum_{l=1}^{n}\left|x_{i}^{(l)}- x_{j}^{(l)}\right|^{2})^{\frac{1}{2}}$$

• p=1,曼哈顿距离 $$L_{1}(x_{i},x_{j})=\sum_{l=1}^{n}\left|x_{i}^{(l)}- x_{j}^{(l)}\right|$$
• p=无穷 $$L_{\infty }(x_{i},x_{j})=max\left|x_{i}^{(l)}- x_{j}^{(l)}\right|$$
• 不同距离度量确定的最近邻点是不同的

k值的选择

• k比较小，模型复杂容易过拟合
• k大，学习误差小，模型简单

3.3k近邻的实现：kd树（未理解）

• kd树的构造：
  1. 开始，构造根节点，由根节点生成深度为1的左右子节点。。。将落在切分超平面上的实例点保存在根节点
  2. 重复：对深度为j的结点选择x(l)为切分的坐标轴，l=j(mod k)+1,以该节点对应的区域中所有实例x(l)坐标的中位数为切分点。切分通过切分点并与坐标轴x(l)垂直的超平面实现。将落在切分超平面上的实例点保存在该节点。
  3. 直到两个子区域没有实例时停止。
• kd树搜索：

4.1朴素贝叶斯

1. 基本方法：x为N维向量，y为类标记（class label），P（X，Y）为x和y的联合概率分布，训练数据集$T=\begin{Bmatrix} (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) \end{Bmatrix}$
   由P（X，Y）独立同分布产生。
   • 通过训练数据集学习联合分布概率P（X，Y）。先学习先验概率分布及条件概率分布：$P(Y=c_{k}),k=1,2,...,K$
   • 由于条件概率分布P（X=x，Y=ck）有指数量级的参数，不宜计算。朴素贝叶斯对条件概率分布作了条件独立性的假设： $$P(X=x|Y=c_{k})=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_{k})$$ $$=\prod_{j=1}^{n}P(X^{(j)} =x^{(j)}|Y=c_{k})$$
   • 由学习到生成数据的机制，属于生成模型。条件独立假设等于说用于分类的特征在类确定条件下都是条件独立的。这一假设使朴素贝叶斯变得简单，有时牺牲准确率。
   • 后验概率计算根据贝叶斯定理： $$P(Y=c_{k}|X=x)=\frac{P(X=x|Y=c_{k})P(Y=c_{k})}{\sum_{k}^{}P(X=x|Y=c_{k})P(Y=c_{k})}$$ 将以上假设带入得到朴素贝叶斯分类基本公式： $$P(Y=c_{k}|X=x)=\frac{P(X=x|Y=c_{k})\prod_{j=1}^{n}P(X^{(j)} =x^{(j)}|Y=c_{k})}{\sum_{k}^{}\prod_{j=1}^{n}P(X^{(j)} =x^{(j)}|Y=c_{k})P(Y=c_{k})}$$
   • 朴素贝叶斯分类器可表示为 $$y=f(x)=argmaxP(Y=c_{k}|X=x)$$ $$=\prod_{j=1}^{n}P(X^{(j)} =x^{(j)}|Y=c_{k})$$ 2.后验概率最大化的含义：为了使期望风险函数（条件期望）最小化，推导出后验概率最大化。

4.2朴素贝叶斯的参数估计

1. 极大似然估计：
   极大似然估计，通俗理解来说，就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值！换句话说，极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。
2. 朴素贝叶斯算法：
   • 计算先验概率及条件概率 $$P(Y=c_{k})=\frac{\sum_{i=1}^{N}I(y_{i}=c_{k})}{N},k=1,2,...K$$ $$P(X^{(j)}=a_{jl}|Y=c_{k})=\frac{\sum_{i=1}^{N}I(x_{i}^{(j)}=a_{jl},y_{i}=c_{k})}{\sum_{i=1}^{N}I(y_{i}=c_{k})}$$ j=1,2,…n;l=1,2,…Sj;k=1,2…K
   • 对于给定的实例$x=(x^{(1)},x^{(2)},...x^{(n)})$ $$P(Y=c_{k})\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_{k})$$
   • 通过计算上式在$P(Y=c_{k})$为何值时取得最大，得出实例x的类。
3. 贝叶斯估计：用极大似然估计可能会出现所求概率值为0的情况。会影响后验概率的计算结果，使分类产生偏差。$P(X^{(j)}=a_{jl}|Y=c_{k})=\frac{\sum_{i=1}^{N}I(x_{i}^{(j)}=a_{jl},y_{i}=c_{k})+\lambda }{\sum_{i=1}^{N}I(y_{i}=c_{k})+\lambda S_{j}}$在随机变量各个取值的频数上赋予一个正数$\lambda$,常取1.成为拉普拉斯平滑。Sj为x所有可能总数量。同样，先验概率的贝叶斯估计是：$P(Y=c_{k})=\frac{\sum_{i=1}^{N}I(y_{i}=c_{k})+\lambda }{N+K\lambda },k=1,2,...K$K为所有y可能取值的总数量

5支持向量机

支持向量机是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。支持向量机的学习策略是间隔最大化，可形式化为一个求解凸二次规划的问题，等价于正则化的合页损失函数的最小化问题。

5.1线性可分支持向量机与硬间隔最大化

1. 假设输入空间与特征空间为两个不同的空间。线性可分支持向量机假设这两个空间的元素一一对应，将输入空间中的输入映射为特征空间中的特征向量。假定给定一个特征空间上的训练数据集：$T=\begin{Bmatrix} (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) \end{Bmatrix}$
   其中：$x_{i}\in \chi =R^{n},y_{i}\in \gamma =\begin{Bmatrix} +1,-1\end{Bmatrix},i=1,2,...N$
   yi=1,称xi为正例；yi=-1，称xi为负例。假设训练数据是线性可分的，学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应方程wx+b=0，由法向量w和截距决定。法向量指向的一侧为正类，一侧为负类。
   当训练数据集线性可分时，由于存在无穷个分离超平面。感知机利用误分类最小的策略，，解有无穷多个；线性可分支持向量机利用间隔最大化求解最优分离超平面，这时，解是唯一的。
   超平面：$\omega^{*} x+b^{*}=0$
   相应的分类决策函数： $$f(x)=sign(\omega^{*} x+b^{*})$$

2. 函数间隔和几何间隔
   一般来说，一个点距离超平面的远近可以表示分类预测的确信程度。在超平面$\omega x+b=0$
   确定的情况下，用$\left| \omega x+b\right|$来相对表示x距离超平面的远近。$\omega x+b=0$的符号与标记y的符号是否一致来表示分类是否正确。
   对于某一样本点的函数间隔：

   $$\widehat{\gamma _{i}}=y_{i}(\omega x_{i}+b)$$
   • 定义：超平面 （w，b）关于训练集T的函数间隔为超平面（w，b）关于T中所有样本点（xi，yi）的函数间隔的最小值： $$\widehat{\gamma }=min\widehat{\gamma _{i}}$$ 函数间隔可以表示分类预测的正确性和确信度。但如果等比例改变w和b，超平面没有改变，但是函数间隔变化。因此，我们要对分离超平面的法向量w加以约束，如规范化||w||=1，使得间隔是确定的，这时间隔为几何间隔： $$\widehat{\gamma _{i}}=y_{i}(\frac{\omega}{\begin{Vmatrix} \omega \end{Vmatrix}} x_{i}+\frac{b}{\begin{Vmatrix} \omega \end{Vmatrix}})$$ 同理，定义超平面（w，b）关于训练数据集T的几何间隔为各样本几何间隔最小值。 $$\widehat{\gamma }=min\widehat{\gamma _{i}}$$
3. 硬间隔最大化：
   • 最大间隔分离超平面： $$\underset{\omega ,b}{min} \frac{1}{2}\begin{Vmatrix} \omega \end{Vmatrix}^{2}$$ $$s.t.\ \ y_{i}(\omega x_{i}+b)-1\geqslant 0,i=1,2,...N$$ 凸二次规划问题
4. 支持向量与间隔边界：在线性可分发情况下，训练样本数据集中的样本点中与分离超平面距离最近的样本点的实例成为支持向量.支持向量是使下式成立的点。$y_{i}(\omega x_{i}+b)-1= 0$对yi=+1的正例点，支持向量在超平面$H1:\omega x+b=1$对于yi=-1的负例点，支持向量在超平面$H2:\omega x+b=-1$在H1和H2上的点就是支持向量。

5.2软间隔最大化

6神经网络

• 简介（以下由chatgpt生成）
  神经网络算法是一类基于生物神经系统思维方式和人工智能技术的计算模型，被广泛应用于机器学习、图像识别、自然语言处理、语音识别、控制系统等领域。常用的神经网络算法包括以下几种：

1. 前馈神经网络（Feedforward Neural Networks）：是最基本、最常用的神经网络算法，其特点是信息传递是单向的，不具有反馈和循环。可以通过调节网络的层数、神经元数量和权重等参数进行训练和优化。

2. 卷积神经网络（Convolutional Neural Networks）：主要用于图像识别和计算机视觉等领域，其结构由多层卷积层、池化层和全连接层构成，可以有效地提取图像特征。

3. 循环神经网络（Recurrent Neural Networks）：具有时间依赖性，可以处理序列数据、自然语言处理、语音识别等任务。其具有循环结构，可以记住过去的状态信息，并且通过反馈机制将当前状态与前面的状态相连。

4. 长短期记忆网络（Long Short-Term Memory Networks）：是一种特殊的循环神经网络，能够有效地解决长时间依赖问题，主要应用于自然语言处理、语音识别、机器翻译等领域。

5. 自编码器（Autoencoders）：是一种无监督学习方法，可以用于数据压缩、特征提取、图像去噪等任务，其原理是通过学习数据的低维表示来重构输入数据。

神经网络算法的优点是能够进行大规模并行计算、处理非线性问题、具有自适应性和学习能力等，但也存在训练难度大、容易陷入局部最优解等问题。
当人们谈论神经网络时，通常指的是深度神经网络（Deep Neural Networks，DNNs），它们是一种人工神经网络（Artificial Neural Networks，ANNs）的变种。在深度学习中，神经网络是最流行的算法之一，用于解决各种任务，包括图像识别、自然语言处理和语音识别。

神经网络算法的基本原理是通过学习数据的规律来构建一个函数，将输入映射到输出。这个函数由神经网络的各个层组成，每个层都由多个神经元（或称为节点）组成。每个神经元接收到来自前一层的输入，并通过一些权重和偏置来计算输出。

神经网络的训练过程通常使用反向传播算法（Backpropagation）来优化神经元的权重和偏置。这个算法通过计算损失函数的梯度来更新神经元的权重和偏置，以使模型的预测更加准确。损失函数通常是一个衡量模型预测值与真实值之间差距的函数。

底层逻辑方面，神经网络是一种前馈网络，即数据从输入层开始流向输出层，中间没有反馈或循环。神经网络中每个神经元的输出是通过对它们的输入进行一系列数学运算来计算得出的。这些运算通常包括对输入进行加权求和，然后使用激活函数来转换成神经元的输出。

在深度神经网络中，通常有多个隐藏层，每个隐藏层都有多个神经元。每个隐藏层可以看作是对输入的一种抽象表示，它将输入中的一些特征提取出来并传递给下一层，最终得到输出。通过增加隐藏层和神经元的数量，神经网络可以学习更加复杂的模式和规律。

7最速下降法

• 输入：目标函数f（x），梯度函数$g(x)=\triangledown f(x)$,精度$\varepsilon$.
• 输出：f（x）的极小值点x*

1. 取初始值$x^{(0)}$,置k=0
2. 计算$f(x^{(k)})$
3. 计算梯度$g{k}=g(x^{(k)})$,当$\begin{Vmatrix}g{k}\end{Vmatrix}<\varepsilon$时停止迭代，令x^{*}=x^{(k)}，否则令$p{k}=-g(x^{(k)})$,求$\lambda{k}$,,使： $$f(x^{(k)}+\lambda _{k}p_{k})=\underset{\lambda \geqslant 0}{min}f(x^{(k)}+\lambda p_{k})$$
4. 置$x^{(k+1)}=x^{(k)}+\lambda {k}p{k}$,计算 $f(x^{(k+1)})$
   当 $\begin{Vmatrix}f(x^{(k+1)}-f(x)^{(k)})\end{Vmatrix}<\varepsilon$ 或： $\begin{Vmatrix}x^{(k+1)}-x^{(k)}\end{Vmatrix}<\varepsilon$ 时，停止迭代，令 $x^{*}=x^{(k+1)}$
5. 否则，令k=k+1，转到3.
   计算量小，存储量小，必收敛
   局部最优，收敛速度慢，大多数条件下线性收敛

8牛顿法

• 优点：收敛速度快，大多数情况下超线性收敛
• 缺点：二阶梯度正定时才下降，计算量大，当牛顿法无法产生下降方向时，用最速下降法代替