Mars's Blog

机器学习

2020-10-10

阅读

1. 机器学习概论

https://www.cnblogs.com/ylHe/p/9336719.html

机器学习是人工智能三大基石之一

1推理 2知识 3学习

特点：利用经验改善系统的性能

经典机器学习定义：

蕴含特定目的的知识的获取过程，内部表现为新知识的不断建立和修正，外部表现为性能改善。

经验表现为数据和常识的形式

现代统计机器学习定义：

任何通过数据训练学习的算法都属于机器学习技术

学习系统：
image-20200722101124392

学习算法在统计学中可能是一些优化算法，比如随机梯度下降等，在机器学习的范畴中可能范围更大

机器学习算法从数据中学到模型，在模型空间中学哪个模型最合适，这个就是学得模型

三要素：

  • 输入数据
  • 模型空间
  • 机器学习算法本身

不同的数据产生不同的学习算法（数据驱动角度）

机器学习算法从数据出发，选择合适的算法，数据是第一位

模型和学习层面
模型：

  • 形式：线性/非线性

  • 体系：浅层/深层/递归

image-20200725085547934

https://www.cnblogs.com/toone/p/8574294.html

模型空间可能是SVM，决策树等

体系：神经网络层数 做NLP，语音递归

学习层面：

  • 经典（90c前）

  • 现代

    监督学习，统计学习，集成学习…

  • 混合

image-20200725092224814

机器学习是人工智能的一个分支，深度学习是机器学习的分支

学习过程

监督学习 找x到y的f(x)

  • 回归
  • 分类

系统建模和模型选择

维数灾难

随着输入维数的增加，算法需要更多的数据

所需的数据/样本空间的数据 越来越大

设随机变量服从均匀分布，如果一维空间（即数轴上的某一区间）需要N个样本才能完全覆盖，那么当二维空间下还是N个样本时，覆盖度就有所下降。随着维度的增加，覆盖度指数级下降。

在样本量一定的情况下，维度越高，样本在空间中的分布越呈现稀疏性。

数据集划分方法

留出法、交叉验证

验证集：模型的选择

测试集：模型的评估

建模相关：

  • 函数/模型的刻画

    • f(x) 怎么来？给一堆数据后，不知道如何处理因此做先验（比如对于CNN，输入输出有多少结点）

  • 找模型参数 - 定义目标/损失函数 【学习算法本身】

  • 评估泛化性能 在未知样本上的性能

模型选择

过拟合

对训练集拟合的越来越好，测试集精度会越来越大（训练样本和测试样本精度不是吻合的）

欠拟合(under-fitting) 指产生一些误分

好拟合(good-fitting)

共性问题

有限样本，模型数远远大于样本数

线性代数中的病态问题：1，3，5 ? ?

导致的问题是即使训练误差小，但泛化性能未必好

评价指标

评价指标很重要，但指标又和数据有关系，相互影响
image-20200726120242789
精度矩阵

TP （T表示预测是否正确，P表示预测的类别）读作真正例、假负例、假正例、真负例

对角线表示预测正确，不是结果正确

区别在于行列的表示刚好相反

image-20200726121002301
ROC曲线
image-20200726134416811
不平衡数据集

敏感性高=漏诊率低
特异性低=误诊率高

MCC 马修斯相关系数（衡量二分类）

F1不能衡量不平衡数据集，使用MCC来度量

image-20200726194340201

MCC（Matthews correlation coefficient）：是应用在机器学习中，用以测量二分类的分类性能的指标[83]。该指标考虑了真阳性、真阴性和假阳性和假阴性，通常认为该指标是一个比较均衡的指标，即使是在两类别的样本含量差别很大时，也可以应用它。MCC本质上是一个描述实际分类与预测分类之间的相关系数，它的取值范围为[-1,1]，取值为1时表示对受试对象的完美预测，取值为0时表示预测的结果还不如随机预测的结果，-1是指预测分类和实际分类完全不一致。

对数损失（可以来衡量多分类）
image-20200726201305581

TP曲线越高，面积越大，分类器性能越好。

测量精度

评价一个系统的工业表现：是否稳定？也就是是否有可重复性？

可重复性：（类似输入，是否产生相近输出）

测量精度类似于概率分布的方差

精度是指系统本身对一个问题的测量程度（和前面的精度不一样）

2 方差高

4 既不准，又落得很开

模型选择 - 选择一个具有良好泛化性能的模型

没有免费午餐定理

没有天生优越的学习器，充分利用了问题先验知识的模型才可能最优

四类方法：

  • 模型选择 交叉验证

  • 正则化 + 先验

    病态→良态，将解空间约束在某个范围

    正则化：规范化，防止过拟合，增加泛化能力。也就是在目标函数上加一些限制

    良态问题满足的条件：

    • 存在性
    • 唯一性
    • 连续/稳定

  • 模型的组合/集成

  • 多数据视图

机器学习都是病态问题，给定的数据有限，要求在高规模下解决

吉洪诺夫正则化（Tikhonov）

非负范函/先验/正则化来辅助

例：CNN权衰减/dropout

先验的重要性

机器学习追求泛化的最好性能

泛化 = 数据 + 知识（与领域/任务无关的叫源知识）

例：输入输出的映射应该光滑（相似输入 对应 相似输出）

丑小鸭定理 - 特征表示

与任务相关的特征才是好特征，抛开任务谈数据是没有意义的。

只有确定了任务，获得什么任务，提取什么特征才有意义。

统计学相关概念

数学概念记录下来

方差 针对单个统计量

协方差 针对两个统计量
$$
cov({𝐱_𝑖 },{𝐲_𝑖 })=𝐸({𝐱_𝑖 }−𝝁)𝐸({𝐲_𝑖 }−𝒗)
$$
协方差矩阵 针对多个统计量 对角线上是单个变量方差，非对角线是行列的两个变量的协方差。

理解协方差矩阵中对角线和非对角线上值的物理意义，=0、>0、<0的含义

=0 不相关 >0 正相关 <0 负相关

马氏距离
image-20200727102733377 image-20200727103342851

修正了欧式距离中各个维度尺度不一致且相关的问题

其中Σ是多维随机变量的协方差矩阵，μ为样本均值，如果协方差矩阵是单位向量，也就是各维度独立同分布，马氏距离就变成了欧氏距离。

协方差矩阵的用途 同时考虑均值和方差

例：某个点和其他的距离是多少？

对其他点求均值点，然后计算均值点和该点的距离。

高斯分布

单位阵：一维 非对角线都为0 中心聚集，离中心点越远，数据点越少 （单位矩阵，表示x和其他点没有关系）

对角阵：二维 同样只有对角线上有值 x1，x2方向的方差不一样就会形成椭圆形

一般阵：离散化 - 协方差所有点都有值 x1，x2等存在一定的相关性

值集中在对角线

  • 对角线全相等（1） x y轴方差相同
  • 对角线不等（2）

这里的理解可以参考马同学的解释

image-20200727174703181
先验概率

交叉区域的样本可以通过先验概率来判定。

后验概率

当知道某个特征x的取值，再判断是哪个类别 — 后验概率

贝叶斯法则 结果为后验概率

image-20200220160838284

最大化后验：甚至不需要计算分母P(Xj)，因为可以直接比较各个类别可能的概率

朴素贝叶斯分类

数据量比较少的时候，失去了统计上的显著性。

这种情况下，需要较大的样本【高维下面临的维数灾难】

做假设：每个属性假设相互独立，计算连乘

Bias - Variance 两难

y 和 f(x)有偏差（噪声的影响）

f帽 在不同数据点产生不同的值（测量精度的原因）

image-20200220162040419

尽可能让前面的bias和Variance尽可能小。

模型选择的次序：

方差小，偏差小 → 方差小，偏差大 → 方差大，偏差小 → 方差大，偏差大

2优于3的原因：方差小说明泛化性能比较稳定，偏差大是因为样本量不够。方差大说明模型就不行。

新型机器学习技术

本质（统计机器学习）

有限样本对未知数据进行建模，涉及特征，模型，优化

  • 终身/连续学习 训练完模型后不再学习，怎样在生产环境中不断地学
  • 迁移学习 训练集和测试集的分布不同
  • 强化学习 在某个场景下找出最优的策略 机理不同于传统分类、回归等
  • 对抗学习 没有足够多样本，想要生成足够逼真的样本
  • 元学习 关于学习的学习

核心技术

工业场景要求越来越小，大，深，快

  • 模型层面
  • 优化层面
    • 允许不断调整 - online
    • 分布式，并行等快速收敛
    • 凸优化
  • 数据层面

2. 神经元和感知机

2.1 脑和神经元

image-20200728194217226

连接学派 神经网络

通过节点之间的连接实现任务

Hebb法则

连接强度的调整量与输入输出的乘积成正比（需要输入、输出都强）

连接可以通过外界的方式加强

巴普洛夫：听觉细胞 - 吃的细胞 - 神经元形成了强壮的连接

长程增强机制 LTP（后天外界可以增强神经元之间的连接）

神经网络发展历史

1943 MP模型 解决可计算性问题

1969 非线性自适应网络

1982-1984 发表ANN文章

2006 推进深度学习

MP神经元

构建神经元的初步目的：解决逻辑上的OR，XOR等问题

image-20200728202721560
基本模型

偏置单元是x0，对应权值是w0

加权求和相当于突触

突破阈值后，神经元激活往外放电

神经元的输出就是w和x的向量相乘的结果，如果低于阈值，那么神经元处于抑制状态；为正则为兴奋状态。

与：x+y-2 或：x+y-1 阈值都为0

局限性

现实生活中的神经元：

  • 输入可能是非线性
  • 输出一般是脉冲序列
  • 随机异步更新（我们模型是一个时钟脉冲来更新）
  • 只存在权值为正的兴奋连接和权值为负的抑制连接，不存在正负转换
激励函数

  • 饱和型 tanh, Sigmoid （值域受限）

    缺点：

    • 梯度消失
    • 非以0为中心
    • 指数计算代价大

  • 非饱和型 ReLU 深度学习一般使用非饱和型，主要是因为指数计算代价和梯度对于深度学习影响比较大

image-20200220172617196

神经元 → 网络

因为单神经元不能学习，输入输出不变

2.2 感知器和感知学习

感知器 - 【二元】【线性】【分类】器

感知器可以在二维或者多维，学到的是二元的决策边界

二元指的是结果为y/n

与神经元的区别：

  • 神经元只有x，y的输入，而Perception有多组向量输入
  • 与逻辑，或逻辑中的权重已经设置好，而感知器不设置，“学习”从这里开始

感知器结构

MP神经元组成的集合 输出只有一个
image-20200729084604060

特点：每个神经元都是独立的，权值也可以是独立的，唯一共享的就是输入。

$$w_{ij}$$表示输入结点i到神经元j的权值

非线性前馈网络特点
  • 同一层之间没有关系
  • 不同层之间没有反馈（没有环路）
  • 输入输出为离散值

输入是随便的w，可以通过输入输出来调整w。

修正方法：
image-20200729105442390

乘$$X_i$$的原因：输入的元素可能是负的，所以权值也要为负，因此需要乘起来

c表示学习率，不能太大（网络不稳定），不能太小（花费时间过多），适中即可（0.1～0.4）

输入偏置
image-20200729105841928

偏置节点，权值表示为$$w_{0j}$$。

主要的应用场景是：假如输入全为0，可以根据调整偏置值来控制神经元是否激活

学习算法
  1. 权值初始化
  2. 输入样本对
  3. 计算输出
  4. 根据输出eg (1,0,0,0,1)调整权重
  5. 返回到步骤2输入到下一对样本，直至对所有样本的实际输出与期望输出相等
image-20200729110553247 image-20200729110604651
例题：计算更新后的权重

image-20200729111046860 image-20200729112524006

方法：

更新权重方法：$$W_{i+1} = W_i + c (t - y) X_{i+1}$$

$$X_i$$ 表示为[$$x_0$$, $$x_1$$, $$x_2$$…] （$$x_0$$一般取1）

通过样本学到分类器，分类器不唯一（学习参数，初始权值，学习样本的先后次序不同，最后的分类器可能不同，但分类效果相同）

2.3 线性可分性

OR函数

ppt的练习题 我算出来是0.2, -0.02, 0.52（偏置单元是1）

书上也有例子 p57

决策边界

决策边界为 $$w^Tx+b=y$$（可能是直线，也可能是超平面）

也叫鉴别函数 $$xw^T >=0$$

目标：找到一个权值矩阵，和x的点积。

物理解释：与x1，x2连线垂直的那条线 决策边界 $$w^Tx+b=y$$ 的法向量是 $$w$$

判断预测正确与否：$$y_i (w^Tx+b) > 0$$ （$$y_i$$表示标签，+/- 1）

补充知识：

两向量夹角锐/直/钝 痛过点乘来判断

ax + by + C = 0 法向量为(a, b)

当$$w^Tx+b>0$$在超平面法向量$$w$$所指的一侧，小于0表示在法向量的异侧。

image-20200729131848112
多分类决策边界 - 多个输出 多分类

每个输出神经元定义一个决策边界

疑问：上面的感知器模型就有多个输出神经元呀？？

感知机收敛理论

证明：给定一个线性可分数据集，感知机将在有限次迭代T后收敛到一个决策边界。

定义γ是分离超平面与最接近的数据点之间的距离，则迭代次数的界是1/γ^2

证明方法：用$$w^w$$来衡量，假设$$w^$$可以线性可分（也就是能一个决策边界），因此需要找出尽可能和$$w^*$$平行的向量，也就是夹角为0，也就是让两者的点积越来越大。因此要考察两点，1是让$$w^*w$$变大，另外w长度没有增加太多

image-20200729212203704

结论：每次权重更新比上次都会增加γ，T步就会增加tγ

再利用柯西不等式

image-20200730000243478image-20200730000826070

image-20200730000832394

感知机缺点

不能解决非线形可分的情况，如XOR。

解决办法：

  • 利用核技巧，投影到高维空间

    • 人为构造第三个维度

  • 用多层网络处理异或

    • 把单层感知机改为多层

      权重是固定的

      这个不算是感知机，是个感知器网络

      image-20200730131118086

      注：H1，H2也是两个神经元，因此他们的输出是根据激活函数来的，结果只能是0/1

感知机的表达能力

n维决策边界

❓广义布尔函数 pn个输入值至少有m个为真，则输出为真

两层神经网络可以表示所有的布尔函数

感知机缺点

感知机收敛的前提：$$w^*$$存在

如果线性不可分，只能收敛到最佳近似

感知机方法只适用在单层网络！！

3. 神经元网络

多层感知机

使用更复杂的网络，两个方法：

  • 加入向后的连接，输入输出能连接起来（造成循环网络）
  • 在输入输出之间加入神经元

隐层结点是全连接

隐层神经元

隐藏层叫法是因为不能直接检查并修正它们的值

目的：

通过权值，对输入数据做一次映射，实际上：特征检测算子，刻画训练数据的突出特征

image-20200225164240825

将四个数据压缩到三个（上图中的两行数据进行压缩）

对输入数据做一次特征变化(乘w)，再把新的数据再到输出层进行线性分割

隐藏层神经元实际为特征检测算子(feature detector)，在多层神经网络的学习过程中，隐藏层神经元开始逐步“发现”刻画训练数据的突出特征

权值的计算方法：

工作机制：向前 向后

向前：逐层计算输入输出，最后计算误差。这个也叫算法的recall 阶段。

向后（回头看）：通过输出层输出的误差来反向计算权值，逐层调整权值。属于梯度下降的一种形式。

误差反传（BP，back-propapagation)

误差定义：

  • 感知器

    image-20200225164654739

    注：经典感知机中N = 1。当有多个输出神经元的时候，如果误差一正一负，可能就抵消了。因此选择平方和误差函数。

  • 多层感知机

    image-20200225164730273 【1/2并非必须，便于求导约分】

    沿着误差梯度下降的话，误差下降最快

    image-20200731091428367
Delata规则：

找误差最小的那个点。

image-20200731093015963

c表示学习步长

误差平面指的是函数在数据集上的累积误差。每一个神经网络的权值向量表示误差平面的一个点。

要求：激励函数必须连续可微分。（跃阶函数不连续，sigmoid函数可用）

不能克服缺点（只能线性分类的缺点），但它是BP的核心。

TODO 推导可以再看看

ppt 15 课本p120

两步：

  1. 先计算Error对$$O_i$$的偏导

    image-20200731133743523

  2. 计算$$\Delta W_k$$

image-20200731133547262

比感知器多了中间激活函数导数这项（感知机阶跃函数不能求导）

注意：

c越大，权值朝最优值的速度越快。如果过大在最优值附近会震荡。

delta规则不能克服感知机的界限。但他是BP的核心（而Hebb规则做不到）原因就是他的可导性

反向传播算法

把输出层的误差往前做传播

信用分配问题：只知道输出，但不知道中间隐藏结点的输出。

多层感知机 → BP神经网络

BP神经网络的本质就是多层感知机

特点：

  • 三层或三层以上结构（输入，隐藏，输出）

  • 无反馈（反传是误差，反馈是输入输出）

  • 层内无互联（RNN，LSTM是在同一层内联系）

  • 采用误差反向传播算法

【重要】BP误差反差学习传播算法推导

教材p88

https://www.cnblogs.com/charlotte77/p/5629865.html 带了数字计算

image-20200731135733939

两种情况：

无隐藏层：

图见上方

image-20200731172436071image-20200731172641157

要计算某个权值对整个误差造成的影响，所以要计算上面这个。

局域梯度域（能复用）为：image-20200731172553351

最终结果 image-20200731172613572

有隐藏层：

❓这里的权值 $$w_{kj}$$表示j到k，但是这里明明只有一个神经元j？

image-20200731172402617

信用分配问题：隐藏神经元不能直接访问，因为隐藏结点的输出对后面的误差都有贡献

要算隐藏层的权重的话，需要先计算到$$y_j$$的偏导

image-20200731174054737 image-20200731174612330

（因为$$y_j$$对每个$$e_k$$都有贡献）

注意：网络中隐藏层和输出层中用的激励函数是否相同，对于推导结果没有影响。

image-20200731174816778 image-20200731174829947

❓有啥物理意义呢

image-20200731184738401

例题：https://blog.csdn.net/dare_kz/article/details/77603522

sigmoid导数

$$f(net) = \frac{1}{1+e^{-\lambda*net}}$$

特点：$$\lambda$$越大，区间[0,1]上越接近直线

求导结果：$$-λf(net)(1-f(net))$$

其他议题

  • 初始权值

    初始权值设定为[0, 1]中的高斯分布中选一个

    假设数据样本均匀分布，和高斯分布的权值相乘就会产生随机变量。那么隐藏层也会变成随机变量。

    独立变量和的方差 = 独立变量方差的和 如果n个权值，输出值~(0, n)。意味着高斯分布很平整

    这就意味着输出层的输入会是n这样的大值，导致输出值过大，进一步导致激活函数饱和，梯度趋近于0，学习失效。

    因此权值应该$$w~(0, \frac{1}{n^{\frac{1}{2}}})$$ n指的是输入层结点数

  • 激活函数

    分类：sigmoid

    回归：线性函数 y = h

    多分类：softmax函数

    深度学习用非饱和激活函数

  • 顺序和批量训练

    • 批量训练（所有训练样本的误差和）

      计算代价大/收敛速度快/局部极小

    • 顺序训练

      按顺序挨个计算。快/局部极小/噪声敏感

    • 小批量训练（mini batch）

      从中随机挑几个进行训练（有的样本可能挑多次）

      适用于大规模数据

  • 局部极小和冲量

    梯度为0可能是局部极小，冲力就是意味着给小球额外重量，使它产生滚动的动量。这个通过对当前点的前一个权重进行改变

    更新的时候顺便计算二阶导

    image-20200801005013602

    a是冲力常量

  • 停止机制

    • 固定迭代步数
    • 误差小于固定阈值（如果有噪声可能停不了，因此不选等于）
    • 结合

    利用验证集观察误差变化，找到合适参数。

    （先让他跑，不设定停止条件，找出误差变化规律。误差增大可能就过拟合了）

自动编码器AUTOEncoder - 最早深度学习的起源

无监督算法，目标值和输入值相等，相当于学习函数h(x)≈x。

image-20200801090553441

也就是要学到W 通过W得到低维的输出

相当于中间做的是数据的压缩

层数变多

顶层MLP的三层结构

输入 - 隐藏 - 输出

网络是对称的（输入结点数 = 输出结点数，隐层结点< 输入/出结点）

MLP中的训练样本有label，自动编码器的数据没有类标。【自监督学习】

image-20200227161401432

编码权值

解码权值

找到两个网络参数，使得经过变换后误差最小。

输入、输出是转置的关系。

只需要解一个W’

要求中间的输出尽可能稀疏（如稀疏约束）

径向基网络RBF - 有监督学习

感受野

感受野越大表示能接触到原始图像的范围越大，也意味着他可能蕴含更为全局、语义层次更高的特征；而值越小则表示其所包含的特征越趋向于局部和细节。

径向基网络

目的：相近的输入产生相同的输出，相隔很远的输入不会产生相同的输出

RBF神经元的激活和输入数据和权重空间中神经元的距离成比例

用输入与中心向量的欧式距离作为函数自变量，高斯函数作为激活函数（空间中任一点x到某一中心c之间欧氏距离的单调函数）

x 光强 w 锥状体

x在这样一个高斯函数上，是否会有输出，输出是多少

中心点：径向基位置

圆圈大小：感受野尺寸

image-20200801215109908

基：表示激活/未被激活的锥状体

RBF：是否被激活：基于距离，局部匹配。不是每个都有输出。

（MLP：基于内积，全局匹配，因为全连接，隐层都会被激活）

径向基网络的学习

需要计算的三个参数：基函数的中心，方差，隐含层到输出层的权值

因为隐藏层的输出可以被计算出来，因此RBF退化为单层网络

image-20200801232438858

Ps: 第一步有两种方法：

  • 如图中所提到的均值算法
  • 随机初始化的数据点作为中心（感知机）
image-20200801231802964
径向基网络的原理

  • 基构成隐层空间，通过确定RBF的中心点，把输入直接映射到隐空间，不需要权连接

  • 隐层的输出是线性的，网络的输出就是线性加权和

  • 隐含层的作用是从低维度映射到高维度。把低维线性不可分到高维线性可分。【核函数思想】

    • 隐藏层结点比输入层多（自编码器隐藏层结点比输入层少，起到降维的效果）

  • 优点：

    • 快，权值能直接计算不需要迭代，能避免局部最小问题（前提：基需要先固定下来，尺寸大小是什么）
RBF vs BP

  • 局部逼近 vs 全局逼近

    BP神经网络：隐藏层对输入层做了全连接。是对非线性映射的全局逼近。所有的输入都用到了权值

    RBF 局部映射：局部映射

  • 中间层数区别

    BP 可以有多个隐藏层（如果层数太多，计算量太大，梯度发散，梯度消失）

    RBF 只有一个

  • 训练速度

    RBF快：

    • 隐含层少
    • 对于一个输入x，只有部分神经元会有响应，其他的都近似为0，对应的w就不用调参了

  • 最优性

    RBF是连续函数的最佳逼近

注：如果用学习到的算法学输出层的值，那还是得用到BP算法

局部的拟合器 组合起来 效果是最佳的

https://www.cnblogs.com/pinking/p/9349695.html

image-20200801231826526
RBF vs SVM

image-20200801235809096

4. 维度约减（降维）

特征选择和降维

降维：

  • 特征选择：维度约减选择的特征是原来特征的子集

  • 特征诱导/变化：通过数据产生了新特征（比如深度学习又是一种表示学习，通过数据自动学出原来数据没有的特征。早期的实验是通过数据，构造出来一些特征，然后再做特征诱导，而深度学习是直接学特征，有端到端的优点）

目的：
  • 降维，降低over-fitting风险（低维空间下，数据量足够，就不会over-fiting了）
    • overfitting有两种方法，一种是降维，另一种是增加样本
  • 增加解释性（低维度下解释性比较强，能做到可视化）
  • 去除冗余特征

特征选择（这章不讲）

数据的特征之间是否有依赖性？

本质上是搜索问题，就是要搜一个最优的特征子集（也就是要构建搜索树）

特征评估函数

  • 过滤式

    增强特征和类的相关性，削减特征之间的相关性

    距离度量（方差为0，可以过滤掉这个特征）、信息度量（互信息熵）、

  • 封装式

    把特征选择和机器学习任务目标放在一个框架

    通过分类错误率指导特征选择（对最终任务目标提升的好坏）

  • 嵌入式

    模型正则化，再加上稀疏约束

LDA 线性判别分析 - 监督学习

ps：监督学习是因为一开始有类别标签，才能算类内类间散度

数学知识：

image-20200803105307581

投影到超平面，让样本按照类别最大程度分开（投影平面和分类平面垂直）

$$S_W$$(Within-class)组内方差 越小越好 image-20200803083253301

$$S_B$$(Between-class)组间方差 越大越好 image-20200803083309294

目标是$$\frac{S_W}{S_B}$$最小化，然后用$$w^T$$将$$x_j$$转为在直线$$w$$上的投影，也就是用$$w^Tx_j$$代替$$x_j$$

目标函数变为$$\frac{w^TS_Ww}{w^TS_Bw}$$

然后对目标函数中的w求导，令导数为0

image-20200803101759743

要求解这个，最开始思路是左乘$$S_W^{-1}$$ ，但是通常情况下$$S_W^{-1}$$无法计算，所以需要计算$$S_W^{-1}S_B$$的特征值和特征向量

算法基本流程

https://www.cnblogs.com/pinard/p/6244265.html

设d为要降到的维度

  • 计算每个类别的均值，和全局样本均值
  • 计算组间方差$$S_B$$和组内方差$$S_W$$ （聚类中的指标）
  • 对矩阵$$S_W^{-1}S_B$$做特征值分解
  • 取最大的d个特征值对应的特征向量
  • 计算投影矩阵

PCA 主成分分析 - 无监督

数学知识：

https://zhuanlan.zhihu.com/p/77151308 这篇相关数学知识讲的好

矩阵的主成分是其协方差矩阵的特征向量按照对应的特征值大小排序得到的

样本比较大的时候，协方差公式里的m-1可以直接用m来代替

协方差矩阵对角线是单个变量方差，非对角线是协方差

降维问题的优化目标：将一组 N 维向量降为 K 维，其目标是选择 K 个单位正交基，使得原始数据变换到这组基上后，各变量两两间协方差为 0（因为不相关），而变量方差则尽可能大（在正交的约束下，取最大的 K 个方差）

可以把数据映射到主轴方向

找到数据中的主要成分，并用它来表征数据。

降维是因为取出了几个特征值最大的维度（不然只是做了PCA，只做了坐标轴变换）

主成分特点
  • 最大可分性 样本点在第一主成分的离散程度大于第二主成分（方差越大越能保留更多的信息，都聚一块那信息都丢失了）
    • 从数学上来说就是要找k个基(k < N)，还要最大程度保留信息
  • 最近可重构性 样本点到第一主成分的平均距离小于到第二主成分距离
目标函数：最大化样本点在主成分投影上的方差
算法细节

https://www.cnblogs.com/xbinworld/archive/2011/11/24/pca.html

数学细节：

对随机变量来说，cov(X, Y) = E[(X-u)(Y-u)] $$cov(W^TX)=\frac{1}{m}(X-\mu)(X-\mu)^T$$

定义W为包含所有映射向量为列向量的矩阵

投影后的数据 $$x_i^TW$$： 去中心化数据后做投影，还是以0为中心

投影后数据方差：image-20200803142634934

目标是让投影后方差最大，所以就是要让协方差矩阵对角线上的迹取到$$max(tr(W^TCW))$$，并且$$W^TW=I$$(因为是正交投影)

ps: C表示协方差矩阵

最优的W是由数据协方差矩阵前k个最大的特征值对应的特征向量作为列向量

构成的PCA的输出就是Y = W’X，由X的原始维度降低到了k维

拉格朗日乘子法（用来证明要优化的目标）：

也可以直接用实对称矩阵的性质推到

image-20200803143130672

结论：x 投影后的方差就是协方差矩阵的特征值。我们要找到最大方差也就是协方差矩阵最大的特征值，最佳投影方向就是最大特征值所对应的特征向量，次佳就是第二大特征值对应的特征向量，以此类推。

算法过程
  • 样本去中心化 （每个数据都减掉样本均值，这样均值为0，所以协方差矩阵为$$xx^T$$）
  • 计算协方差矩阵 $$C = \frac{1}{m}(x-\mu)(x-\mu)^T = \frac{1}{m}xx^T $$
  • 对协方差矩阵做特征值分解
  • 将特征向量按对应特征值大小从上到下按行排列成矩阵，取前 k 行组成矩阵
  • Y = WX即为降维到 k 维后的数据
核PCA

对于呈现环状的点分布，找不到线性变换正交坐标轴

思路：用类标让他们在投影中区分出来，也就是核PCA

PCA vs LDA
PCA LDA
无监督 有监督
方差最大 SB最大，SW最小
投影后的坐标是正交的（因为选择的成分都是正交的，也就是说协方差矩阵非对角线都是0） 非正交
投影后维度数与源数据相同 投影后维度数目与类别数目相同

ICA 独立成分分析

因素分析

数据由多个物理源产生，因素分析将数据解释为不相关因素的累加

目标是找到数据源

做去中心化的预处理

目标模型是$$X = WY + \epsilon$$， 因素Y做了线性变换W，现在就是想知道W和Y分别是什么。$$\epsilon$$是噪声

模型限制：（加入限制才能可解)

  • 数据之间不相关，协方差为0

  • image-20200804095430039

    ❓ 最后一步没看懂

然后用EM算法求解

盲源分离（源未知）

数据来源于一些独立的潜在物理过程

不相关：$$cov(b_i, b_j) = 0$$

统计独立：$$E(b_i,b_j) = E(b_i)(b_j)$$ 更强的约束，满足统计独立，那肯定不相关

算法分析

$$x1 = as_1+bs_2$$

$$x2 = cs_1+ds_2$$

$$x = As$$ A表示线性变换，s表示原数据源，x表示产生的输入声音

按照一般思路求s，但A未知，所以不能求，需要加入约束：

  • 数据源独立，混合数据不独立
  • 数据源非高斯变量，混合数据服从高斯分布（中心极限定理）

$$y = W^Tx = W^T As = z^Ts$$

当z只有一项非0元素，y的非高斯性最大(意味着只保留了混合数据的一项，这样非高斯性最大)

目标函数：

熵表示了y的随机性，高斯性

负熵：$$J(y) = H(z) - H(y)$$

近似方法：$$J(y) = (E[G(y)]-E[G(x)])^2$$

所有等方差的随机变量中，高斯变量的熵最大。由中心极限定理，若干个有限方差随机变量（无论其服从何种分布）的和，其逼近高斯分布。反言之，源信号比混合信号的非高斯性更强。用负熵度量其非高斯性。

主要算法
image-20200804174608345
ICA vs PCA
PCA ICA
降维并提取不相关属性 降维并提取相互独立属性
重构误差最小 每个分量最大化独立
成分间正交 成分间独立
信息提取 解混

局部线性嵌入 LLE

局部最优，在降维时能保持样本的局部特征

https://www.cnblogs.com/pinard/p/6266408.html

image-20200805083003640

核心

  • 投射到新空间后，要保留相邻数据的关系（保持原有的结构）

  • 数据用局部近邻线性近似（自身可以用近邻点表达出来）

image-20200805082616888
近邻点的确定
  • 距离法：距离小于阈值
  • 个数法：前k个
权重约束
  • $$x_i$$周围点的权重和为1，
  • 如果某个点离$$x_i$$很远，那么$$W_{ij} = 0$$
计算方法
image-20200805084356732 image-20200805085925761

ISOMAP - 等距特征映射

目标：保留相邻数据的关系

方法：检查所有点对的距离 & 计算全局测地线

MDS 多维缩放

https://blog.csdn.net/Dark_Scope/article/details/53229427

ISOMAP = MDS + 测地线

寻找线性近似，然后投射到低维空间（类似PCA）

嵌入时要保持数据点对之间的距离（假定距离已经被测出）

欧式空间，PCA和MDS等价

已知高维上样本点两两之间的距离，尝试在低维上(通常是2维，但是可以是任意维)找到一组新的样本点，使降维后两点间的距离与它们在高维上的距离相等

目标函数
image-20200805092303236

Sammon中那个除法是为了对误差加权（举例理解：同宿舍和同楼层都属于近邻，但距离远的应该除以初始距离）

Sammon是非线性的，只能用迭代来做

经典MDS算法

去中心化后用相似度代替距离

相似度：image-20200805092636404

目标函数：

image-20200805092747415

解法：

  • 梯度下降
  • 当目标函数是线性，直接解析计算（求导求逆）

算法流程：

image-20200813093018635
流形空间

流形：任何对象都可以看作低维在高维空间的嵌入（表达）

毛巾是二维，扭转后是三维

距离

球上两点的距离是测地距离，不是欧式距离

测地线距离
image-20200805094035538

表达高维空间的距离（如AB间距离），用欧式距离不合适

计算测地线距离的方法：

根据近邻不断的寻找，近邻是用欧式距离，然后接着再找近邻的近邻。。。

  • Dijstra算法
  • BFS
ISOMAP算法
  • 创建所有点对之间的欧式距离
  • 找到每个点的近邻点
  • 通过找最短路径法计算测地线距离$$d_G$$
  • 对$$d_G$$运用MDS算法

7 优化与搜索

在机器学习之类的实际应用中，我们一般将最优化问题统一表述为求解函数的极小值问题，

数学基础

梯度：矢量，方向指向数值增长最快的方向，大小为变化率。

导数：一个值

确定目标函数是关键

求解目标函数：

  • 对问题直接进行计算
  • 凸优化，非凸优化的技术来求解

优化方法很重要

梯度下降 - 寻找导数为0的点

原理

迭代法

找目标函数的最小值，但解析法不能直接求出

  • 基于学习率的改进机制

    学习率适应梯度（梯度大的时候，学习率应该小）

    学习率 除以 梯度（平方开根保证正）

  • 基于二阶梯度的改进机制

    利用之前的梯度指导梯度下降

    （避免被局部最优影响，找二阶梯度 & 一阶梯度都大的地方，之前一阶梯度的方向得到保证，继续沿原来的方向走）

    冲量法

代表算法

冲量法

将当本次梯度下降方向与上次更新量的方向相同时，上次的更新量能够对本次的搜索起到一个正向加速的作用；反之减速。

借助变量$$V_t$$更新的时候同时更新$$\Delta W_t$$和以前的$$\Delta W_{t-1}$$…

指数平均距离

NAG

把值和方向都考虑进来

根据$$W_*$$的方向来走

image-20200806112634271
自适应梯度法

通过将learning rate除以S的平方根进行更新。S指的是历史和当前的梯度的平方的累加。

image-20200806112619507
缺点
  • 靠近极小值收敛速度减慢
  • 直线搜索会出现问题
  • 之字形下降（可能跑的方向不对）
优点

只要在当前做一阶的求导即可

牛顿法 - 寻找导数为0的点

https://zhuanlan.zhihu.com/p/37588590

迭代点处一阶导数和二阶导数对目标函数进行近似

核心：

基于函数局部就是二次曲面，在泰勒展开只需要前两项（高斯曲面才有更高阶导）

在某点处用二次函数来近似目标函数，得到导数为0的方程，求解该方程，得到下一个迭代点。因为是用二次函数近似，因此可能会有误差，需要反复这样迭代，直到到达导数为0的点处

过程：

  • 二次函数近似
  • 二次模型的极小值作为新的迭代点，并不断重复
  • 直到求得满足精度的近似最小值
算法
image-20200806133041450

ps：$$p_k$$表示搜索方向。因为可能去最大和最小，所以符号不定（不同版本课本不一样）

没有步长：能直接算出局部最小值在什么地方，所以不需要步长

牛顿法改进

阻尼牛顿法

问题：

牛顿方向不区分上升/下降，可能跑反了

对局部做的二次函数近似不知道有多大

image-20200806140917265

注：image-20200806140925013 （也就是$$x_{k+1}$$的最小对应的$$\lambda$$）

拟牛顿法

H阵和求逆复杂度太大

解决：利用一阶导数(J阵)拟合H阵，构造一个替代阵

替代阵产生方法有很多（通过一阶阵来生成替代阵）

牛顿法优点

  • 二阶收敛，收敛速度快

    牛顿法：用二次曲面拟合当前点的局部曲面

    梯度下降：用一次平面拟合

缺点
  • 计算复杂度
    • 每一步都需要求解目标函数的H矩阵的逆矩阵，计算比较复杂
  • 目标函数可导性
    • 必须一阶二阶可导，H阵须正定

最小二乘优化 - 要求fx形式

https://blog.csdn.net/fangqingan_java/article/details/48948487

具体函数形式的优化方法

目标函数： image-20200806174123316

r(x)是残差项，求的是r(x)的J阵

image-20200806184207327

image-20200806184636092

SVD分解法

$$J = USV^T$$

image-20200806190813967

转为线性最小二乘，直接求解

信赖域法

舍弃image-20200806191038466中的第二项舍弃

这样在局部就是线性最小二乘（类似拟牛顿法）

image-20200806191511481

核心：能否在局部弄个线性最小二乘替代他，如果可以，就放大一点，如果不行，就放小一点

image-20200806193023680

解释：p就是要解的位移

Levenberg-Marquardt算法

是梯度下降和牛顿法折中

image-20200806195526385

v >=0 不会改变原来的方向

取大：左边的$$J^TJ$$可以忽略，$$vI$$是个常数，就变成梯度下降。$$p = -J^Tr$$

取小：接近牛顿法 $$p = -(J^TJ)^TJ^Tr$$

算法流程

过目一下：

image-20200806200126273

注：接受$$x_{new}$$表示满足线性最小二乘

共轭梯度法

介于梯度法和牛顿法之间

特点：只需要一阶导。比一阶导快，

image-20200807002015931

ps：梯度法找的是正交方向（Z字形绿色）共轭梯度法

共轭梯度法（红色）找的是共轭方向，一步到位

数学定义

两个向量共轭，那存在对称半正定矩阵

$$p_i^T(Ap_j)=0$$ （A的目的是做个A的变换，相当于直接找到数据最主要成分，反映了局部的函数方向）

$$p_i^T$$和$$Ap_j$$正交，而$$p_i$$和$$p_j$$不正交

算法流程
image-20200814141930918

解析：求出$$x_{i+1}$$后，和当前梯度，以及前面点梯度都有关

要点

  • 步长的确定

  • 假定局部线性

  • 新共轭方向确定

    • image-20200807003333007

      假设$$p_k$$和前面k-1个$$p_i$$有关

image-20200807003441219

搜索

搜索前面的都是凸优化 找到的解就是最优解

方法：

非凸 转为 凸优化

Machine Learning最核心的亮点

  • 怎样找到目标函数，如何定义？

  • 优化算法是什么？

TSP问题 - NP完全问题

  • 穷举法 BFS 保证最优解，但是复杂度O(N!)

  • 贪婪搜索 不断重复选择最近且没有访问过的城市（每一步都在找全局最优解）复杂度O(NlogN)

    无法保证最优解

  • 爬山法 对当前解决方案的局部搜索，选择任一个选项来改善结果

    • 所有数值优化的迭代方法都是爬山法（比如梯度下降）
    可能失效的原因
    • 陷入局部最小
    • 各方同向的锅底（没有头绪）
    • 函数存在很大的平面区域（和锅底类似，不过它连梯度也没）

利用和探索 - 搜索的两种机制

机器学习常常混合这两种机制

探索 - 穷举（尝试新的）

利用 - 爬山（利用旧的）

模拟退火算法 - 启发式算法

利用的概率是玻尔兹曼分布

指数表示之前老虎机的收益

image-20200807091712218

探索和利用的trade-off

UCB算法

选择置信区间上界最大的臂

均值 + 玩了多少次

Ui反映了利用 后面反映了搜索（如果玩的次数少，说明要多玩）

8 演化学习

演化学习经常代表遗传算法。

遗传算法中有一系列的解，在自然界中形成竞争。（与以往参数模型算法的不同）

遗传算法GA - 解决非凸问题的随机优化方式（与前面优化方法的不同）

对当前最好假设的重组来产生后续假设模型

不知道当前解对未来的结果是什么样的

4个问题
  • 表示解 - 二进制
  • 解的好坏 - 适应度函数
  • 怎么选择好的解
  • 怎么通过好的解产生下一代

一般形式

image-20200310164250819
假设模型的表示
image-20200807102532954

决策属性

1 - Yes 0 - No # - No/Yes

应用实例

背包问题中，用染色体表示拿哪种物品。适应函数是物品总价值。

产生后代的方法

基于适应度函数

  • 锦标赛选择

    放回抽样，然后选择最好的一个进入子代种群

  • 截断选择

    选择适应度最高的前k个

    进行染色体复制，使子代种群达到父代种群规模

  • 轮盘赌选择

    基本思想是：各个个体被选中的概率与其适应度大小成正比

遗传算子

  1. 对当前选择的染色体进行重组，产生后代

    交叉 从交叉点开始 做片段交换

    • 单点交叉
    • 两点交叉
    • 均匀交叉

  2. 变异 选择一个候选个体 随机选择一位 然后取反

后代演化方法

  • 简易方案（也是自然方案）

    子代代替父代

  • 精英法

    每一代保留上一代最优的染色体

  • 锦标赛法

    父母染色体和子代染色体竞争，胜者到下一种群

  • 小生境法

    image-20200807113631318
举例

第0代：随机选取

第1代：取最好的4个，并且有交叉和变异

替换第0代适应度低的4个

……

如何表示解；如何评判解的好坏（适应度函数）；如何选择好的解释；通过好的解产生下一代。

优点：解很多，并行优势大

模式定理

short schemata with large fitness – increase presentation

0#10 - 0010/0110

阶

模式中确定位置的个数 O(#10##) = 2 （就是非#的数量）

长度

第一个确定的位置到最后一个确定位置之间的距离

O(##1#0) = 5-3=2

模式理论

m(s, t) 表示第t代种群中模式s的实例数量

通过m(s,t)推断t+1代中的实例数目

模式进化

轮盘赌选择image-20200807120007752（ps：最右边分母表示第t代染色体平均适应度）

image-20200807120429849
模式定理
  • 适应度越高模式影响力越大
  • 有越多#影响力越大（染色体覆盖的实例越大，泛化性能强）
  • 确定位彼此靠近的影响力越大

为什么种群一代代适应度越高呢？ — 选择算子

交叉变异倾向于产生长度短，确定位少的模式

遗传算法求解最短路径问题

  1. 选择初始种群

    从初始点开始，每次从该点的临接点中选择一个之前没有选择过的点，直到选择到终点

  2. 评估种群中每个个体的适应度

    计算每个个体（路径）的路径总和

  3. 选择排名靠前的个体来reproduce

    选择两个具有最短路径的个体（路径）

  4. 交叉和变异

    随机从两个parent路径中选择公共点进行交叉，如图所示

    image-20200810220603112

  5. 计算子类的适应度

    （也可以直接用锦标赛法，上一代和下一代，一起选择前K个就行了）

    如果子类适应度低于种群中最大的适应度，那么把子结点用最大适应度对应的结点替换

    image-20200810224132387

  6. 终止条件

    达到预先定义迭代次数停止（在网络拓扑中无法寻找全局最优解）

11 强化学习

通过ML方法，实现认知的强化

本质：奖惩与试错

交互学习：通过交互产生的样本。什么机器决定了产生什么样的样本。

学习目标

  • 决策（状态→动作的映射）
  • 最大化长期奖赏

马尔可夫决策过程

一阶马尔可夫性：未来的状态与历史状态无关

S a delta R

MDP模型

样本不是提前给的

学的不是分界平面，而是一种策略

轨迹

一次episode中，获得的经验或者轨迹。

返回函数

即时奖赏值的线性组合

  • 有限窗口 10步以内
  • 无穷窗口
    • 有折扣 最常用
    • 无折扣

动作选择

一定会

动态规划

最重要：MDP状态转换和reward一致

调整Vpi 0 最优控制

策略评估

这个策略下，获得的值函数是什么

控制

某个点等于当前状态加上后续状态集合

Mento Carlo策略评价

一直采用$$\pi$$策略，玩到底

是一种采样方法

如果采样是充分的，那么可以计算走每个分支的概率

遇到环路：

只让第一次遇到的进行平均

时差学习

样本利用是低效的

提高利用率的方法：时差学习TD 充分利用每一步的经验

代替从轨迹上获得的

监督学习 vs 强化学习

离策略 在策略

基于Q的学习

Q-学习算法
image-20200319161256969

离策略，与当前使用的策略没关系。

SARSA算法
image-20200319161314232

没有max，a’ 意味着当前使用的策略（pi指定的，即on-policy）去更新。

N步TD预测

揭示了强化学习重要特点：延迟回报

每一步都要更新原先的每一步（蒙特卡洛是更新链上的每一个）

构建一个估计，考虑到每一步（一步/两步更新）

1.初始化V(s), e(s)=0

2.对每一个episode，重复

​ 初始化s

​ 对episode中的每一步

​ 根据ε-贪心策略选择动作a

​ 执行动作a，获得r和s′

​ ∆←r+γV(s′ )-V(s)

​ e(s)←e(s)+1

​ 对于所有s

​ V(s)←V(s)+α∆e(s)

​ e(s)←γλe(s)

​ s←s^′

​ 直到s为终止状态

关系强化学习

10 树学习

符号(概念)学习和变型空间

哲学和智能是相通的

  • 演绎推理 P->Q, P真Q真【一般原则应用到具体事件】
  • 反绎推理 P->Q，Q真P真（医学，不可靠）
  • 归纳推理 已知前件为真，后件未必为真（训练集100%/假设正确，用到测试集上不一定为100%/假设正确）但不妨我使用这个假设【个别事件提取公共属性，西瓜是甜的，香瓜是甜的->所有瓜都是甜的】

符号学习是一类归纳推理，尽管不可靠，但是有用

机器学习的中心问题：从特殊的训练样例中归纳出通用式函数（管中窥豹）

概念学习

给定样例集合，以及每个样例是否属于某个概念（是否能出去玩），自动推断出概念的一般定义（什么样的情况下能出去玩）。

从某个布尔函数的输入、输出样例中推断出该布尔函数。（机器学习就是找函数-找布尔函数）

符号学习是一类归纳推理

实例集合

任务

寻找一个假设h，使得对于实例集合X中的所有x，h(x)=c(x)

c(x)表示目标概念，定义在实例集上的布尔函数 c:Xà{0,1}。（就是能获得数据的ground truth 标签）

实例空间和假设

取什么都可以

<$, $, $> 取什么都不行

做假设的时候还要加上这两种

假设空间比样本空间大（维数灾难）

假设：任一假设如果在足够大的训练样例集合中能很好的逼近目标概念函数，它也能在未见实例中很好的逼近目标概念

（也就是说没必要给出所有可能的样本集合）

搜索的概念学习

搜索能最好拟合训练样本的假设

Find-S （笨方法）- 寻找极大特殊假设

image-20200808102728182
特点

样本可能不充分，所以可能不是特殊的假设

如果出现多个极大假设，也没办法处理

变型空间 - version

包含反例

包含所有满足样本一致性的集合（包括正例和反例）

列表消除算法

穷举法

image-20200808105219990

问题：列出所有的假设是不可能的，指数级复杂度

极大泛化：G集合 最一般假设

极大特化：S集合 最特殊假设 所有的H都和样本满足，但找不到还有一个H’，比H还特化

image-20200808105557434

上图的最上方就是极大特化，最下方就是极大泛化

正例 负例的作用

正例：将S集合泛化（逐步把概念的外沿扩大）

负例：将G集合特化（缩小概念）

候选消除算法 - 爬山法

image-20200813203200973

初始化两个集合S（全为$），G（全为?）

对于正例：让S变得更一般

对于负例：修正G，排除掉负例中可能导致标签为负的属性（并且还要避免和S的冲突）

image-20200808144405813

注意：要保证G的泛化要在S的特化范围内（也就是不产生冲突）

Find-S算法只找到了S，而爬山法找到了G，最终结果就在S和G之间

归纳偏置 Inductive bias - 给定某种形式的预先假定

https://blog.csdn.net/u011938325/article/details/75173140

进行概念学习的时候，定义的假设空间可能出问题

假设空间是合取式（属性值的合取，有偏，就是把并集直接当作？），真实空间是析取式（允许或的概念）

无偏

允许析取/允许或运算

image-20200808150723015

问题：无法构造用于无偏学习的算法，因为在无偏学习中，没法进行泛化（正例就是正例，负例就是负例，什么也学不出来）

结论：归纳学习必须给定某种形式的预先假定（但学出来的模型是假定下的）

三种归纳学习算法
  • 机械式学习（没有归纳偏置没法学）
  • 候选消除 会学出一个变形空间
  • Find-S（比候选消除还有偏）eg：小女孩胆子小，没声明为正例的全是负例

有偏性越强，学习器的归纳能力越强

如何学习有析取表示的假设空间？ - 决策树

决策树算法

决策树

特点：能学习析取表达式

归纳偏置：优先选择较小的树

目标：输出深度最小的树

ID3算法

image-20200808181928927 image-20200808181947255
信息增益
image-20200808221658851
特点
  • 仅维持单一的当前假设（不同于变型空间候选消除算法 - 维持满足训练样例的所有假设）
  • 局部最优 （不进行回溯） 改进是C4.5
  • 基于统计
    • 对错误样例不敏感
    • 不适于增量处理
决策树中的归纳偏置

优先选择较短，信息增益更高的树（搜索策略决定了归纳偏置）

其他树算法

image-20200808223732101

剪枝

完全生长 -> 泛化性能弱

  • 前剪枝

11 集成学习

原理

一个预测模型的元方法，不是机器学习算法

多个学习器组合起来，结合模块输出

特点

如何分类？如何集成？

多个分类器集成起来，提高分类准确率

由训练数据构建基分类器，根据预测结果进行投票

准确度和多样性之间要有权衡
核心问题
  • 序列集成 基学习器之间的依赖关系
    • 目标：减小偏差
  • 并行集成
    • 目标：减小方差
结合策略

  • 平均法（回归）

  • 投票法（分类）

  • 学习法

    • 上两节的方法都是对弱学习器的结果做平均或者投票，相对比较简单，但是可能学习误差较大，于是就有了学习法这种方法，对于学习法，代表方法是stacking，当使用stacking的结合策略时， 我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。

      在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。

多样性策略
  • 数据层面
  • 属性层面
  • 参数层面

Bagging （Bootstrap Aggregation）

原理

有放回的采样，得到统计量分布和置信空间。

与boosting的不同：弱分类器间没有依赖关系，可以并行生成，最后将预测结果继承

bias必须大于0

image-20200809101157697

代表算法 - 随机森林

https://easyai.tech/ai-definition/random-forest/

随机森林：很多决策树构成，不同决策树之间没有关联

分类任务：输入样本进入后，让森林中的每棵决策树进行判断和分类，最后统计哪种分类结果最多，就将其作为最终结果哦

构建RF方法：

四步：

  1. 假如有N个样本，则有放回的随机选择n个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的n个样本用来训练一个决策树，作为决策树根节点处的样本。
  2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
  3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。
image-20200809111436698
优点

降低分类器方差，改善泛化

速度快（并行）

Boosting

Boosting 和 bagging 最本质的差别在于他对基础模型不是一致对待的，而是经过不停的考验和筛选来挑选出「精英」，然后给精英更多的投票权，表现不好的基础模型则给较少的投票权，然后综合所有人的投票得到最终结果。

先基于初始训练集训练一个基学习器，再根据基学习器的性能表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本来训练下一个基学习器。直至基学习器数量达到指定数目，最后将所有基学习器的结果进行加权结合。

强依赖关系，各子学习器依次训练（串行、迭代）

PAC学习理论

能否从假设空间H中学到一个好的假设h

  • 近似正确 泛化误差足够小
  • 可能正确 多大概率达到近似正确
image-20200809175448660

image-20200809173121047

在多项式时间学习到一个近似正确的结果 - 强学习器

框架

bias不一定大于0 因为可能弱模型

转化：

GBDT

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

决策树包括分类树和回归树（可以做数学运算）

算法流程

初始化弱分类器

循环

​ 对每个样本计算负梯度

​ 根据残差构建新的样本集合

​ 构建CART树

​ 计算叶子区域最佳拟合值

​ 更新得到强学习器

得到最终强学习器

Adaboost

推导过程：https://www.cnblogs.com/pinard/p/6133937.html

PAC学习理论

强弱学习器等价

可以通过boosting将弱分类器转换为

训练过程和boosting思想相同，区别是Adaboost的损失函数变成了指数损失函数

Stacking

将几个学习器的预测结果作为新的训练集（新的特征），来学习一个新的学习器

image-20200809205725222

优势：降低泛化误差，同时降低方差和偏差

image-20200809210817053

12 无监督学习

特征选取和距离度量很重要

核心：簇内相似+簇间不相似

分析没有标签的数据

从无标记的数据学特征表示/预测

【物以类聚，人以群分】

  • 聚类的好坏不存在绝对标准(depends on opinion of the user)

  • 总是能通过定义新的标准，来得到新的聚类方法（分类标准）

聚类相关概念

簇：簇内对象相似，不同簇间不相似

聚类算法：给出相似性评价标准，把数据集来划分

依据：样本->特征向量->特征空间的点，通过衡量点之间的距离来进行聚类

好的聚类算法：

  • 簇内高相似
  • 簇间低相似

聚类的目的：

对数据一无所知，目的是对数据做划分和可视化

  • 潜在的自然分组结构
  • 感兴趣的关系
影响聚类的因素：
  • 特征的选取和设计 特征对聚类很重要，选择什么特征，决定了在特征空间的分布
  • 距离函数

聚类分析的有效性：

与数据特征向量的分布形式有很大关系（特征选的好，数据分布好，不同种类的样本聚在一块的话不好聚类）

对具体数据做聚类分析的关键是 特征的选取

距离度量

度量同一类样本的相似性和不同类样本的差异性

常用度量函数

image-20200810230142564

n维空间中两个点x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)

闵可夫斯基距离：

image-20200401183852263

也可以表示为 image-20200401183956670

  • 曼哈顿 L1范数 用于L1正则化（为了矩阵可逆） Lasso回归

  • 欧式 L2范数 用于L2正则化 Ridge回归

    image-20200401183509680

机器学习中正则化项L1和L2的直观理解

  • 切比雪夫 L∞范数

  • 余弦 点积/模的乘积 衡量的是相似性

    优点：根据向量方向判断相似度，不受各个维度直接数值的影响

  • 马氏距离 M矩阵 协方差矩阵的逆矩阵

    对欧式距离的修正，修正了欧式距离中各个维度尺度不一致且相关的问题。

    协方差矩阵

    马氏距离通俗解释

    • 度量学习 通过优化算法 从数据中学M矩阵 来度量两个特征向量的距离

    单个点：

    image-20200407122557873

    两个点：

    image-20200407122623431

度量空间是一个有序对(X,d) X是集合，d是度量函数

d把X中的每一对点映射为非负实数，并且满足四条公理

  • 非负
  • 唯一
  • 对称 不满足这条，叫伪度量（eg：KL散度）
  • 三角不等式

聚类准则

类：定义有很多种，划分具有人为规定性

类定义：

d(xi, xj) <= hh为阈值

聚类需要 距离度量 和 聚类准则。(意思就是把距离为多少的归为一类)

需要一个能对聚类过程/聚类结果的优劣进行评估的准则函数。如果聚类准则函数选择的好，质量会更高。

  • 试探方法 定义阈值，按最近邻来指定属于某个聚类样别
    • 欧式距离-距离做阈值 余弦距离-相似度做阈值
  • 函数方法 聚类准则是反映类别间相似性或者分离性的函数。聚类分析转化为求准则函数极值
    • 找样本集和类别之间的函数
image-20200409152821818

聚类方法

  • 基于试探的聚类搜索方法

    • 按最近邻规则的简单试探法

      高维样本很难获得准确的先验知识，只能选不同的阈值和起点来试探

      影响因素
      • 第一个中心点位置
      • 待分类样本的排列次序
      • 阈值T
      • 样本的几何分布
      算法过程

      给定：样本集、阈值T

      基本思想：大于阈值就成为新中心，否则成为小于阈值且距离最小的那个类

      image-20200409154118285

    • 最大最小距离算法

      随机选一个聚类中心z1，然后选距离z1欧式距离最大的点作为距离中心

      过程：

      核心：找出各个样本离自己最近的中心点，然后选出距离最大的，如果超过最初两个中心距离的一定比例，那么可以作为新的中心，否则找中心结束。

      image-20200409202754823

  • 系统聚类法

    • 按距离准则逐步分类（类别由多到少，合并点）核心：形成nxn的距离矩阵，找出其中的最小元素aij，那么把i和j类进行合并；​ 更新距离矩阵​ 达到所需的聚类数目，或者矩阵中的最小分量超过给定阈值D停止。
      • 距离准则函数
        • 最短距离 两个集合所有距离的最小值
        • 最长距离 所有距离的最大值
        • 类平均距离 所有距离的平均值

  • 动态聚类法（KMeans，ISODATA）

    • KMeans

      结束条件：重新计算后聚类不发生样本所属聚类改变的情况

      影响因素

      • K
      • 初始选的K个样本点
      • 模式样本的几何性质（天然，影响最重要）

      如果数据样本可以形成若干个相距较远的孤立区域分布最好

      适合分类数目已知的情况（K）

      算法流程
      image-20200813211656786

  • KMeans++

    • K个初始聚类中心分的越开越好

      • 均匀分布的采样，选择下一个聚类中心

      KMeans++例子

      image-20200409210518936

    • ISODATA算法（迭代自组织数据分析算法）

      • 分裂和合并
      image-20200409221713498 image-20200409221924382 image-20200409221947890

      dmin(聚类中心的最小距离)和Sigma(样本的离散程度)作为是否进行合并和分裂的标准

    比较

    • K-means适合类别数目已知的聚类
    • 算法角度：相似，中心都是通过样本均值的迭代来决定
      • ISODATA加入了试探步骤，利用中间经验进行更好的分类
    • ISODATA需要指定比较多的参数，并且很难准确指定某个值，因此不太受欢迎

聚类评价

  • 聚类中心之间的距离
    • 距离过大 需要分裂
  • 聚类域中的样本数目
    • 数目少，并且聚类中心距离远，可能是噪声
  • 域内的样本方差
    • 方差太大可能不属于这一类

常用评价指标

标签未知

  • Compactness 紧密度CP（越小越紧凑）

  • Separation 间隔度SP （越大越分散）

  • DBI 戴维森堡丁指数**/**分类适确性指标 使用了CP和SP 越小越好（缺点：使用欧式距离，对环状分布聚类评价很差）

  • DVI 邓恩系数 越大越好（缺点：对离散点的聚类测评很高、对环状分布测评效果差）

标签已知（聚类结果和真实标签的差异）

聚类准确率

兰德指数

调整兰德指数

互信息

归一化互信息

可视化

二维高斯分布展示

图像分割（每个像素做聚类）

概率与学习

相关概念

凸函数：曲线在直线下方 （表示函数的斜率一直在增加） eg: e^x 有最小值

凹函数：f(x)为凸函数，那么-f(x)为凹函数 eg: logx is concave in R++（最大化对数函数时，就可以求到最大值）

判定：

  • f’’(x)>=0 -> 凸函数
  • Hessian矩阵是半正定的 -> 凸函数（正定矩阵的特征值>0)

通常情况下，损失函数建立为凸函数比较好

最小化凸函数时，有最小值，能求出最优解（凸优化）

随机变量
琴生不等式

X是随机变量，f(X)是凸函数, E(f(X)) >= f(E(X))

X是随机变量，f(X)是凹函数, E(f(X)) <= f(E(X))

高斯分布/正态分布

应用最广泛的概率分布

  • 单变量高斯分布

    方差越大，图像越矮胖

    pdf：

  • 多变量高斯分布

    均值为miu，方差为sigma（是一个协方差矩阵）

    变量如果是标量，符号是小写不加粗

    变量如果是向量，符号是小写且加粗

    pdf：sigma往往是半正定矩阵

    含有马氏距离

高斯混合模型 Gaussian Mixture Model

两个高斯分布的加权

pdf：

需要乘ai（表示属于哪个高斯分布的概率），并且权重和为1

不知道有多少个高斯分布组成（可以根据类别数假设有多少个高斯分布）

需要求解三个参数

最大似然估计 Maximum likelihood estimation MLE

算法过程

thelta：需要观测的参数

X：观测数据

i.i.d 独立同分布

乘积很小，因此取ln

期望最大化算法 Expectiation-Maximization

求解关于高斯函数的参数估计

迭代的方法

适合包含无法观测的隐变量的模型

思想

EM是一种迭代的方法，利用最大似然估计MLE对统计模型中的参数进行估计，特别是针对包含无法观测隐变量的模型

固定第一个变量，MLE求第二个；固定第二个，再使用MLE估测第一个；依次迭代直到收敛到局部最优解

E-step

利用可观测数据$$\chi$$，和参数估计$$\theta^{(t)}$$，t表示第t次迭代，估计更好的隐藏变量Z

M-step

利用可观测数据$$\chi$$和当前估计的隐藏变量Z，估计更好的参数$$\theta^{t+1}$$

Repeat

重复两个步骤，直到收敛

优化分析

为什么能求解模型参数呢？

先做了假设，对Q是什么不清楚

EM vs K-means

高斯混合模型是一个软的K-means

K-means是直接指定类别，而高斯混合模型求的是Xi属于哪个高斯分布（类）的概率

K-means背后的EM思想

聚类准则思想：

mj是类的均值，然后求解每个点到聚类中心距离的和

image-20200811103551391

概率与学习（续）

近朱者赤 近墨者黑

回顾

训练集 x - 特征向量 y - 标签（ground truth）

分类 vs 回归：输出离散值（标签属于离散数值集合） 回归输出连续值（结果属于实数集）

计算张量之间的距离（矩阵之间距离，矩阵和向量之间距离，三维tensor）

KNN

核心：分配给距离最近的N个邻居中占最大比例的类别

算法流程：

image-20200811105117640

k的取值的影响
  • 奇数，避免平局
  • 取不同值，分类结果不同（1，3，5，7，9，在具体任务中采用交叉验证选择具体的k）
  • k较小的时候，对噪声敏感，容易过拟合
  • k较大的时候，噪声不敏感，容易欠拟合（可选的特别多，每个样本都可能是我的近邻）

最近邻分类器 1-NN

选择最近的训练样本

泛化错误率

泛化错误率≤2倍的贝叶斯最优分类器错误率

K-近邻回归

选择k个最近的训练样本，将距离值的倒数作为权重，然后将k个近邻的标签值加权平均，作为回归结果。

image-20200811105522829

近邻平滑

  • 核平滑法
    • 二次核
    • 次方核
    • 高斯核

讨论

懒惰学习

K-NN是典型的懒惰学习（训练阶段仅仅是把样本保存起来，训练时间开销为0，收集到测试样本再进行处理）

SVM、CNN是急切学习（训练阶段就进行处理，尝试在训练期间构造一个函数）

优点

  • 精度高
  • 对异常值不敏感
  • 无数据输入假定

缺点

  • 计算复杂度高（扫描整个训练集，复杂度高；对于急切学习，训练好后花时间，测试阶段非常快）
  • 空间复杂度高（训练集需要存储起来）

时间复杂度

欧式距离，时间复杂度O(d)（因为要做d次计算，也就是d次向量相减）

ps：内积也是O(d)

训练阶段：0

测试阶段：O(nd+nlogk) nd是n个点的欧式距离，logk是排序

思考：

n个数字选择k个最小的，时间复杂度？

K-NN空间复杂度？

降低近邻计算

  • 特征维度 2-5 维诺图

    根据一组给定的目标，将一个平面划分成靠近每一个目标的多个区块

    真实应用中不太实用

  • 6-30 KD-Tree（K表示特征维度）

    https://zhuanlan.zhihu.com/p/23966698

    https://zhuanlan.zhihu.com/p/45346117

    训练阶段构造KD树，测试阶段对树做检索

    不断用垂直于坐标轴的超平面对K维空间切分，构成一系列的K维度超矩形区域。（每个节点对应一个K维超矩形区域）

    构造流程
    image-20200814101133933
    KD-Tree 搜索
    image-20200814104111526

    以欧式距离为半径的圆与超平面不相交意味着没有更优解

    时间复杂度
    • O(nlog^2n) 快排、堆排序、归并排序
    • O(nlogn) 用median of meddians算法来寻找中位数
    • 寻找最近邻：O(logn)

  • 高维特征

    • 降维 PCA

      原始高维属性空间 -> 低维子空间

    • 近似最近邻

      不再只局限于返回最可能的数据项（不是最精确），只要找到近似的近邻就可以

    • 哈希

      把任意长度的输入映射为固定长度的输出

      （把维度降下来，然后用0/1值来表示特征）

扩展阅读

k-NN缺点：不是建立在任何概率框架上

无法得到关于类别的后验概率，无法概率化推断近邻个数、度量参数。

小样本情况下，计算复杂度高的缺点被解决，在深度学习时代，仍然有较好的前景

SVM

回顾

机器学习的目的是得到映射 X->Y

似然。p(x|y=i)

后验 p(y=i|x)

概率框架角度

  • 生成式模型

    有先验概率和似然，用贝叶斯定理求后验概率

  • 判别式模型

    决策边界

感知机

选择最好的决线性超平面

线性SVM

间隔与支持向量

一个点的间隔margin式它到分界超平面的垂直距离

目标：最大化所有样本的最小边际margin

具有最小边际的点叫SV

只关心超平面的方向

推导。。。

TODO

soft margin

允许少数点margin比1小

yif(xi) >= 1(感知机大于0就行，但是这里要最大化最小间隔，所以要求高一些) -> yif(xi) >= 1-epsilon

惩罚机制：

把epsilon当成函数来优化

把损失加入最小函数来最小化

非支持向量，拉格朗日乘子ai 等于0

非线性SVM

映射到高维空间，使得这个样本在特征空间内线性可分

通过内积 线性和非线性联系在一起

kernal trick

将非线性函数表示为特征空间的内积

Mercer’s condition 充分必要

Kernel SVM

非线性核
超参数

也需要通过交叉验证来调参数

多类SVM

多类

转为2分类问题

构造Cn2个分类器

使用sigmod函数

投票，选择出现最多次数的类

1对多

C个分类器

不用sigmod，直接输出作为信息

以上这两种只是在训练和测试的时候改了形式，也有直接解决多类SVM的方法。

Tags: 机器学习
← C++ 数组 & 指针 P、NP、NPC、NP-Hard问题的区别 →