机器学习思维导图模板_ProcessOn思维导图、流程图

学习理论

计算假设的目标就是使: 理论误差最小

理论误差是什么

理论误差无法直接使用, 使用经验误差

如何评判一个模型, 以及根据这个模型计算出来的假设

一个模型泛化能力强, 即根据这个模型计算出来的假设的理论误差小. "理论误差"就是"误差的数学期望"

理论误差又叫泛化错误率

我们都是根据经验误差最小的方式来计算出某个假设. "经验误差" 就是 "误差的样本均值"

假定: 某个假设"对单个样本分类错误"的概率服从伯努利分布

理论误差就等于该伯努利分布的期望

经验误差就等于该伯努利分布的样本均值

对于某一个假设, 经验误差和理论误差相差多少

根据hoeffding不等式可得: P( |经验误差 - 理论误差| > r ) > 1 - 2*exp(-2r*r*m)

m为样本个数

r 为经验误差跟理论误差之差

在某个概率下, 该模型所有假设的经验误差和理论误差, 相差多少

假设该模型有k个假设

例如线性模型, 根据各个系数的取值不同, 一共有k中情况

一个模型可以看作一个假设集合

根据上式可得: P( 该模型内所有假设都满足: |经验误差 - 理论误差| < r ) >= 1 - 2*k*exp(-2*r*r*m)

对于这个模型来说: 根据经验误差最小找到的假设和理论误差最小的假设, 他们的泛化能力差多少, 换言之他们的理论误差相差多少

根据经验误差最小找到的假设的经验误差: 叫该模型的训练错误率

该模型的理论误差最小的假设的理论误差: 叫该模型的泛化错误率

经验假设的理想误差 <= 经验假设的经验误差 + r

经验假设的经验误差 <= 理想假设的经验误差

根据经验误差最小计算出的肯定是经验假设

理想假设在现有样本下, 可能经验误差大些

理想假设的经验误差 <= 理想假设的理想误差 + r

所以: 经验假设的理想误差 <= 理想假设的理想误差 + 2r

由此做出我们的策略

可以确定样本个数: 使得该模型的泛化错误率和训练错误率之差在r之内

m >= (1/2*r*r) log(2*k / (1-P))

如何选择模型

由于: 经验假设的理想误差 <= 理想假设的理想误差 + 2r = 理想假设的理想误差+ 2*开方( log(2k/(1-P)) / 2m)

复杂的模型会使右边第一项变小, 但由于k很大会使右边第二项变大. 即经验假设跟理想假设的理想误差偏离太大

加强学习

数学理论

求极值

无条件函数计算极值（凸函数）

单变量函数

梯度下降法

缺点

如果迭代速率设置得太小, 会导致迭代次数过多

如果迭代速率设置得太大, 会导致在极致处震荡

沿梯度方向（或反方向），以规定步长距离点进行迭代搜索

导数为0

牛顿法

使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根

直接计算解析解

多变量函数

一般方法是整体迭代至收敛

每次迭代所有变量更新一遍

或者有选择的更新某些对全局影响最大的变量

更新某个变量的时候有两种策略

1 采用梯度下降法或牛顿法, 走一步

2 直接计算出函数最小时该变量的值

有条件限制的, 连续函数求极值

标准拉格朗日乘数法

思想: 构造一个无条件限制的函数(拉格朗日函数)

计算出来的极值包含原问题的极值

其中某个极值, 对于某个变量来说, 是极大值还是极小值是不一定的.

分支主题

极值处: 拉格朗日方程的值 = 原函数的值

等0约束式的系数不能为0, 如果为0, 约束条件就无效了

扩展的拉格朗日乘数

问题描述采用凸优化问题中的标准表示方法

计算最小值

最优解: 指明是最大值还是最小值, 而不是简单计算极值极值

目标函数和不等式约束都是凸函数

不等式约束都是 <= 0

另外加上等式约束

凸优化问题

https://zh.wikipedia.org/wiki/%E5%87%B8%E5%84%AA%E5%8C%96

kkt 条件

讨论了广义拉格朗日乘数法, 有最优解的必要条件和充分条件

没有提及充要条件

充分条件: 使广义拉格朗日乘数有解的充分条件

如果是计算最大值, 目标函数是凹函数(向下弯). 如果计算最小值, 目标函数是凸函数(向上弯)

不等式约束是凸函数

等式约束是仿射函数

仿射函数：线性映射 + 截距

必要条件: 广义拉格朗日乘数的解

拉格朗日方程对原函数变量的偏导为0

原变量的极值

使等式约束的部分为0

对等式约束的系数的偏导为0

即：等式约束 = 0

使拉格朗日函数的极值等于原函数的极值

使不等式约束的部分为0

要么不等式约束 = 0 ，要么不等式系数 = 0

使拉格朗日函数比原函数范围更宽（拉格朗日乘数函数的极小值必须小于等于原函数的极小值）

不等式约束 <=0

这个是约定好的

不等式约束的系数 >= 0

标准拉格朗日乘数是解一个方程组, 这里为什么没用解方程组的方法

参考网页

https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

计算极值时kkt 条件的使用

化解：kkt条件中的 "不等式约束 <=0"，因为数值趋紧的计算方式不能处理情况。

先以原变量为当前变量，计算拉格朗日函数的最小值

这一步是解析解。

再以约束系数为变量，计算拉格朗日函数的最大值

拉格朗日方程实际上是一个函数族。

每个函数的极小值都 <= 原函数的极小值。

只有极小值符合kkt条件的函数的极小值 == 原函数的极小值

所以我们计算出所有函数的极小值，找到最大的那个，就是原函数的极小值。

剩下的对单个变量的范围限制，在更新约束式系数时使用。

每次都选择不满足kkt条件的系数来更新，因为满足kkt条件的系数已经到达极值点了。

计算最终数值解的方法

拉格朗日各个变量的偏导为0, 解一个方程组

如果能化简为只剩一个变量

只剩一个变量的方程，牛顿法求解

只剩一个变量的拉格朗日函数, 利用数值趋紧的方式求解

如果上一步无法做到, 只能每次选择最合适的变量，改变它们使函数取得最大（小）值。不断循环直至收敛。这个算法称为：坐标上升（下降）法。

如果多个系数相互关联，每次选两个系数

下界函数趋近

适用于情况: 可以找到一个下界函数, 该下界函数的极值很容易计算(例如: 可以直接求得解析解)

计算过程: 不断更新这个下界函数, 使下界函数的极值点逐渐接近原函数的极值点

原因是: 一步找到合适的下界函数是困难的, 我们只能逐步修正下界函数

方法是: 在旧的下界函数极值点处, 令新的下界函数值等于原函数的值, 计算新下界函数的极值. 直到下界函数在极值点处与原函数重合

该方法可行的理由(自己归纳,不太严谨):

先假定原函数和下界函数都是平滑的.

最终结果需要满足两个条件

是下界函数的极值点

是下界函数和原函数的重合点

理由

下界函数的极值点如果跟原函数有重合点, 肯定是相切而不是相交. 否则就不能称之为下界函数了.

所以两者的切点, 要么是在两者的极值处, 要么都不在极值处. (切点处导数相同)

迭代过程不断接近最终结果

下界函数计算极值: 更接近原函数极值

更新下界函数: 新下界函数与原函数相切, 其极值点比切点更接近原函数极值点

对下界函数的要求

形状接近: 下界函数的凹凸性与原函数相同

在某个点与原函数相等

计算过程需要

概率

概率中的逗号表示两个都是随机变量，联合概率分布。分号表示后一个是固定值，作为概率分布的参数出现

监督学习: 基于标记数据的学习

回归问题

研究一个变量(因变量)关于另一些变量(自变量)的依赖关系

一般是有大量数据，但函数参数较少

所谓回归分析法，是在掌握大量观察数据的基础上，利用数理统计方法建立因变量与自变量之间的回归关系函数表达式

回归分析中，又依据描述自变量与因变量之间因果关系的函数表达式是线性的还是非线性的，分为线性回归分析和非线性回归分析。通常线性回归分析法是最基本的分析方法，遇到非线性回归问题可以借助数学手段化为线性回归问题处理

利用最小均方差估计寻找最佳函数匹配

利用最小二乘法寻找最佳的函数匹配

它通过最小化误差的平方和寻找数据的最佳函数匹配

要求：y的条件概率呈正态分布。 E(y) = f (x)

包括

普通最小二乘法

加权最小二乘法

计算方差的时候, 根据距离要预测的点的远近,给予一个权值

非线性最小二乘法

线性回归

假设因变量和自变量呈线性关系

如果真实函数不是线性函数，我们用线性拟合效果就很差。这样我们就做一个"凑合"的线形拟合，使某些点接近这条线，某些点可以不太接近。

使用加权最小二乘法，使尽量多的点接近目标直线

权值是距离平方的负指数函数(类似正态分布形状)

利用最大似然估计寻找最佳函数匹配

广义线性模型

如果x->y有对应关系，按照概率是 Beta*x -> E(y)

扩展一下，把E(y) = beta * x 改成 E(y) = f (Beta *x ) ，就变成了广义线性模型

一般把f换成字母g， E(y) =g (Beta*x) = h(x)

为什么用g，g是h的前一个字母吗？

如何找到f，换句话说 Beta * X 如何影响y的分布，再换句话说Beta*X 在 y的概率分布函数中可以充当哪个参数

f 和期望相关

连续概率分布的参数：要么和期望相关，要么和方差相关。

离散概率分布的参数：应该包括每一个随机变量取值的概率。

如y属于指数分布族，将其转化为指数分布族的通用形式

是否必须是"Natural exponential family"

https://en.wikipedia.org/wiki/Exponential_family

为什么使用指数分布族的通用形式，而不是具体形式（例如伯努利分布）

使用指数分布族的形式，进行最大似然估计，是最容易计算的

指数分布族的形式，把解释期望的参数和解释的方差相参数分开了。我们不关心方差，只关心期望。剥离了无关因素

https://zh.wikipedia.org/wiki/%E5%BB%A3%E7%BE%A9%E7%B7%9A%E6%80%A7%E6%A8%A1%E5%9E%8B

指数分布族中，参数与函数的其它部分相互做的形式最简单：仅有一个相乘（如果是矢量就是点积）

指数分布族的其它特征

https://en.wikipedia.org/wiki/Exponential_family

如果y不属于指数分布族，例如studuent分布，该怎么办

是否可用指数族分布来近似

使用Beta *x 充当指数分布族的正则参数Theta

这里有个问题，利用exp(Beta *x), (Beta*x)^2..... 等其它关于Beta*x的函数充当正则参数，并不是不可以，只是没有必要。

机器学习中，任何一种模型都不是万金油，都是在合理的猜测。再没有充分理由的情况下，不要增加模型复杂度

正则参数 = f（原来的概率分布参数）：该函数叫正则响应函数

原来的参数 = f（正则参数）：该函数叫正则关联函数

利用最大似然估计，计算出Beta的值

广义线性模型的特例

y服从高斯分布

正则参数就是期望，最大似然估计的过程就是线性回归

y服从伯努利分布

正则参数 = ln(u / ( 1 - u))

伯努利分布，计算最大似然估计的过程，成为 logistic 回归

最大似然估计

最大似然估计函数在采样样本总数趋于无穷的时候达到最小方差（其证明可见于Cramer-Rao lower bound）。当最大似然估计非偏时，等价的，在极限的情况下我们可以称其有最小的均方差。对于独立的观察来说，最大似然估计函数经常趋于正态分布。

利用最大后验概率寻找最佳类型匹配

生成学习算法

对两个类别分别建模，新样本匹配两个分类，匹配度较高的作为新样本的类别。

利用贝叶斯公式计算后验概率

p（x| y）：条件概率

p(y) :先验概率。

在分类问题是，都是使用多项式分布

有别的问题吗？

以上两者，是由对(x,y)的联合概率密度进行最大似然估计，计算得出

注意与广义线性回归区分，广义线性回归中x是作为y分布的一个参数出现的。

拉普拉斯平滑

如果在训练集中，一个随机变量某个值没有出现，其概率也不能为零。再人为增加一组样本，每个值出现一次。新增的样本仅占极小的比例，不影响其概率分布。

处理方式是：所有计算出的概率：分子加1，分母加k （k为可能值的个数）

p(y |x ): 新样本所属类别，后验概率

p(y|x) = p(x|y)*p(y) / p(x)

高斯判别分析（GDA）

条件概率p(x|y) 是一个多维高斯分布， x的每一个分量是一个维度

p(y) 服从伯努利分布

计算p(x|y) 的时候，利用最大似然估计

后验概率的条件加上其它参数以后变成了： p(y=1|x; fi, u0, u1, 方差) = 1／（1 + exp(-theta X)）

实际上，只要先验分布属于指数分布族。p(y=1|x; 其它参数) 都是一个logistic函数

logstic 回归鲁棒性更强。 GDA更精确、需要的数据更少

朴素贝叶斯模型（适合x维度非常高的情况）

假定前提：给定y后，x的各个分量的概率分布是相互独立的

p(x1,x2,x3...|y) = p(x1|y)*p(x2|y)*...

如此一来：高维空间的分布，可以有低维空间各个维度的分布简单计算出来。

利用联合概率密度的最大似然估计，计算出给定y下x的每个分量的每个值的概率，以及y的每个值的概率密度。

由于处理的都是离散值，计算过程中完全不涉及x、y分布的解析形式

x每个分量可以有任意有限个值。甚至可以把连续的x离散化，利用朴素贝叶斯建模

把整空间网格化，计算出每一个网格的概率

示例

多元伯努利事件模型（NB-MBEM）

x的第j个分量的值：字典中第j个单词是否存在

多项式事件模型（NB-MEM）

x的第j个分量的值：文章中第j个单词，在字典中的序号

由于x各个分量互不相关，所以文章的性质和单词出现的顺序无关

与多元伯努利模型相比

都是利用了某个类别下每个单词出现的概率

该模型考虑了单词出现的频率

分类问题

感知器算法

神经网络

如果数据不是线性可分的，即不存在一条直线或一个超平面，能把数据分成两部分。就在中间插入一次层中间值。

一个x向量经过多个sigmoid函数，变成一个中间向量，中间向量再经过一个sigmoid函数，得到最终结果。

这几个sigmoid函数互不相同

因为是分成两部分，所以是sigmoid函数。是否有其它情况，使用其它函数

成本函数为误差的平方和

成本函数就是计算最小值的函数

由于最终的目标函数是由多个函数复合而来，非常复杂，所以y的误差符合标准正态分布

利用梯度下降算法计算成本函数最小值的过程叫"反向传播"

支持向量机

计算方法

一个超平面, 把所有的点分开的效果最好

超平面上方的是一类, 超平面下方的是一类

利用所有点到超平面的几何距离的最小值, 找到一个超平面使这个最小距离最大

经过简化, 去掉非凸约束, 变成计算一个有多个凸性不等式约束的极小值的问题

调整

如果超平面效果不好, 把低维向量映射成高维向量, 根据高维向量的超平面计算

由于需要频繁计算向量的内积, 而计算高维向量的内积需要: 两次映射函数计算 + 一次内积计算, 计算量很多大, 就引入了核函数

定义核函数K(x, z) 的值等于 "内积( 映射函数(x), 映射函数(z))" 的值

但是核函数的计算复杂度要少很多, 因为核函数的包含变量的最外层操作一般是乘积操作

而在机器学习中, 大家比较关心内积的值, 而不关心映射函数的具体形式是否准确

因为机器学习就是一个不断凑数的过程, 映射函数只要大致合理即可

所以先找到一个核函数用来代替内积运算, 计算出高维超平面的各个系数.

预测新样本的时候, 要先映射到高维空间, 然后看高维向量在高维超平面的上方还是下方

映射到高维空间的具体形式不用管，最后还是计算内积。所以核函数对应的映射函数不用考虑

常用的核函数

普通内积: 相当于映射到自身

(内积 + t)^d : 映射到一个最高阶为d, 的变量组合

高斯核

映射函数是啥

如果即使映射成高维向量也不能线性可分, 适当放宽条件

不等式约束放宽一点: 原不等式左边 + 小量 > 0

svm模型，没有等式约束。如果有等式约束，是否要放宽

小量为正值

实际是允许某些点穿过超平面一小段距离

为了使所有小量整体最小（整体放宽的尽量小）：原函数变成：原函数 + 所有小量和

每个放宽的小量作为新的变量, 仍旧是一个凸约束极小值问题

利用SMO 计算最大值

https://zh.wikipedia.org/wiki/%E5%BA%8F%E5%88%97%E6%9C%80%E5%B0%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95

TODO

无监督学习(初识数据没有标记数据):

整体思想

先设定参数初始值

根据参数, 标记样本或计算出每个样本的每个标记值的概率

根据标记结果, 重新计算参数: 称为 m-step

以上两步反复, 直到收敛

K-Means法

思路

优化目标是样本距离聚类中心的距离之平方和最短

类比的最小二乘法

过程

设定参数初值

先给初识化K个聚类中心

由于优化目标不是凸函数, 所以可以随机初始化多次, 取最优结果

根据参数标记样本

每个样本离哪个聚类中心最近, 就标记为该聚类

根据标记结果重新计算参数

每个聚类根据其内部样本, 更新中心位置(数据的平均值)

上两部不断循环, 直至聚类中心的位置不变. 迭代过程中剔除空聚类

EM算法: Expectation-Maximization

思路

每个样本的标记数据为: 样本和聚类的联合概率

优化目标: 样本的整体出现概率最大 ( 样本出现的概率之积最大)

每个样本出现的概率 = 样本与聚类的联合概率, 对聚类加和

过程

设定参数初值

所有概率分布的参数

标记样本

根据标记结果重新计算参数

数学技巧

上两部不断循环, 直至聚类中心的位置不变. 迭代过程中剔除空聚类

混合高斯分布

假设条件

每个聚类在所有聚类中的概率分布类型: 多项式分布

要求: 样本覆盖全面, 能反应出聚类的分布状况.

每个聚类出现某个样本的概率分布类型: 多维正态分布

在此条件下, 使用一个简单的优化目标:

联合概率之积最大

各个参数可以计算出解析解

计算结果符合 "频度约等于概率" 规律

聚类的分布: 某个聚类的概率 = 所有样本属于这个聚类的概率的平均值

聚类中样本的分布

期望 = 样本属于该聚类的概率作为权重, 对样本值的加权平均

方差 = 样本属于该聚类的概率作为权重, 对样本与聚类中心的距离的平方的加权平均

一般形式

假设某个样本属于某个聚类的一组参数为theta

最大似然函数 = 样本求和( log( 聚类求和()))

EM 算法的一般好形式

分支主题

todo

em 的一般模型

最大似然估计,标记数据: 在样本特征数据下, 属于哪个聚类

em模型, 标记数据是: 在样本特征数据下, 属于每个聚类的概率

从最大似然估计到em

把指示函数换成概率

三组数据

聚类的概率参数

要计算的值

作为每次迭代的初识条件

聚类下, 特征数据的概率参数

要计算的值

作为每次迭代的初识条件

特征数据下, 聚类的概率 (某个样本属于某个聚类的概率)

标记数据的值

根据以上两组数据, 计算这组数据; 然后再根据最大似然估计, 更新以上两组数组

混合高斯模型三组数据的迭代

已知特征数据下, 聚类的概率: 利用贝叶斯公式: 联合概率 / (所有聚类下特征数据的概率之和)

聚类的概率更新公式:

某个聚类的概率 = 每个样本属于该聚类的概率之和 / 样本总数

聚类下, 特征数据的概率参数 (高斯分布的参数)

聚类中心(高斯模型的期望) = 特征数据的加权平均值 (权重就是: 特征数据下该聚类的概率)

方差呢

混合朴素贝叶斯模型三组数据的迭代

(假设只有两个聚类, 每个样本是N维向量, 每个分量只有0, 1两种情况

已知特征数据下, 聚类的概率: 利用贝叶斯公式: 联合概率 / (所有聚类下特征数据的概率之和)

聚类的概率更新公式:

某个聚类的概率 = 每个样本属于该聚类的概率之和 / 样本总数

聚类下, 特征数据的概率参数

已知聚类下, 每个分量概率之积

em一般形式里

不断用下界函数的极值趋紧似然估计函数的极值

e-step: 下界函数上移的过程(使新下界函数与似然函数在当前当前下界函数极值点处相切)

m-step: 计算下界函数极值

公式的语言描述是什么

路上考虑