机器学习
2017-02-09 00:58:21 91 举报AI智能生成
机器学习笔记，未完待续
作者其他创作
大纲/内容
机器学习
学习理论
计算假设的目标就是使: 理论误差最小
理论误差是什么
理论误差 又叫 泛化错误率
我们都是根据经验误差最小的方式来计算出某个假设. "经验误差" 就是 "误差的样本均值"
假定: 某个假设"对单个样本分类错误"的概率服从伯努利分布
理论误差就等于该伯努利分布的期望
经验误差就等于该伯努利分布的样本均值
根据hoeffding不等式可得: P( |经验误差 - 理论误差| > r ) > 1 - 2*exp(-2r*r*m)
m为样本个数
r 为经验误差跟理论误差之差
假设该模型有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)
加强学习
数学理论
求极值
无条件函数计算极值（凸函数）
单变量函数
梯度下降法
缺点
沿梯度方向（或反方向），以规定步长距离点进行迭代搜索
导数为0
牛顿法
使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根
直接计算解析解
多变量函数
一般方法是整体迭代至收敛
每次迭代所有变量更新一遍
或者有选择的更新某些对全局影响最大的变量
更新某个变量的时候有两种策略
2 直接计算出函数最小时该变量的值
标准拉格朗日乘数法
思想: 构造一个无条件限制的函数(拉格朗日函数)
计算出来的极值包含原问题的极值
分支主题
极值处: 拉格朗日方程的值 = 原函数的值
扩展的拉格朗日乘数
问题描述采用凸优化问题中的标准表示方法
计算最小值
目标函数 和不等式约束都是 凸函数
不等式约束都是 <= 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条件的系数已经到达极值点了。
计算最终数值解的方法
如果能化简为只剩一个变量
只剩一个变量的方程，牛顿法求解
如果多个系数相互关联，每次选两个系数
下界函数趋近
先假定 原函数和下界函数都是平滑的.
最终结果需要满足两个条件
是下界函数的极值点
是下界函数和原函数的重合点
理由
迭代过程不断接近最终结果
下界函数计算极值: 更接近原函数极值
对下界函数的要求
形状接近: 下界函数的凹凸性与原函数相同
在某个点与原函数相等
计算过程需要
概率
概率中的逗号表示两个都是随机变量，联合概率分布。分号表示后一个是固定值，作为概率分布的参数出现
监督学习: 基于标记数据的学习
回归问题
研究一个变量(因变量)关于另一些变量(自变量)的依赖关系
一般是有大量数据，但函数参数较少
所谓回归分析法，是在掌握大量观察数据的基础上，利用数理统计方法建立因变量与自变量之间的回归关系函数表达式
回归分析中，又依据描述自变量与因变量之间因果关系的函数表达式是线性的还是非线性的，分为线性回归分析和非线性回归分析。通常线性回归分析法是最基本的分析方法，遇到非线性回归问题可以借助数学手段化为线性回归问题处理
利用最小均方差估计寻找最佳函数匹配
利用最小二乘法寻找最佳的函数匹配
它通过最小化误差的平方和寻找数据的最佳函数匹配
要求：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
指数分布族中，参数与函数的其它部分相互做的形式最简单：仅有一个相乘（如果是矢量就是点积）
指数分布族的其它特征
如果y不属于指数分布族，例如studuent分布，该怎么办
是否可用指数族分布来近似
使用Beta *x 充当指数分布族的正则参数Theta
机器学习中，任何一种模型都不是万金油，都是在合理的猜测。再没有充分理由的情况下，不要增加模型复杂度
正则参数 = f（原来的概率分布参数）： 该函数叫正则响应函数
原来的参数 = f（正则参数）： 该函数叫正则关联函数
利用最大似然估计，计算出Beta的值
广义线性模型的特例
y服从高斯分布
正则参数就是期望， 最大似然估计的过程就是线性回归
y服从伯努利分布
正则参数 = ln(u / ( 1 - u))
伯努利分布，计算最大似然估计的过程，成为 logistic 回归
最大似然估计
最大似然估计函数在采样样本总数趋于无穷的时候达到最小方差（其证明可见于Cramer-Rao lower bound）。当最大似然估计非偏时，等价的，在极限的情况下我们可以称其有最小的均方差。 对于独立的观察来说，最大似然估计函数经常趋于正态分布。
利用最大后验概率寻找最佳类型匹配
生成学习算法
对两个类别分别建模，新样本匹配两个分类，匹配度较高的作为新样本的类别。
利用贝叶斯公式计算后验概率
p（x| y）： 条件概率
p(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; 其它参数) 都是一个logistic函数
logstic 回归鲁棒性更强。 GDA更精确、需要的数据更少
朴素贝叶斯模型（适合x维度非常高的情况）
假定前提：给定y后，x的各个分量的概率分布是相互独立的
如此一来：高维空间的分布，可以有低维空间各个维度的分布简单计算出来。
利用联合概率密度的最大似然估计，计算出给定y下x的每个分量的每个值的概率，以及y的每个值的概率密度。
由于处理的都是离散值，计算过程中完全不涉及x、y分布的解析形式
x每个分量可以有任意有限个值。甚至可以把连续的x离散化，利用朴素贝叶斯建模
把整空间网格化，计算出每一个网格的概率
示例
多元伯努利事件模型（NB-MBEM）
x的第j个分量的值： 字典中第j个单词是否存在
多项式事件模型（NB-MEM）
x的第j个分量的值： 文章中第j个单词，在字典中的序号
由于x各个分量互不相关，所以文章的性质和单词出现的顺序无关
与多元伯努利模型相比
都是利用了某个类别下每个单词出现的概率
该模型考虑了单词出现的频率
分类问题
感知器算法
神经网络
如果数据不是线性可分的，即不存在一条直线或一个超平面，能把数据分成两部分。就在中间插入一次层中间值。
一个x向量经过多个sigmoid函数，变成一个中间向量，中间向量再经过一个sigmoid函数，得到最终结果。
这几个sigmoid函数互不相同
因为是分成两部分，所以是sigmoid函数。是否有其它情况，使用其它函数
成本函数为误差的平方和
成本函数就是计算最小值的函数
由于最终的目标函数是由多个函数复合而来，非常复杂，所以y的误差符合标准正态分布
利用梯度下降算法计算成本函数最小值的过程叫"反向传播"
支持向量机
计算方法
调整
映射到高维空间的具体形式不用管，最后还是计算内积。所以核函数对应的映射函数不用考虑
常用的核函数
普通内积: 相当于映射到自身
高斯核
映射函数是啥
不等式约束放宽一点: 原不等式左边 + 小量 > 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
无监督学习(初识数据没有标记数据):
整体思想
先设定参数初始值
K-Means法
思路
优化目标是样本距离聚类中心的距离之平方和最短
类比的最小二乘法
过程
设定参数初值
先给初识化K个聚类中心
根据参数标记样本
根据标记结果重新计算参数
EM算法: Expectation-Maximization
每个样本的标记数据为: 样本和聚类的联合概率
优化目标: 样本的整体出现概率最大 ( 样本出现的概率之积最大)
所有概率分布的参数
标记样本
数学技巧
混合高斯分布
假设条件
每个聚类在所有聚类中的概率分布类型: 多项式分布
每个聚类出现某个样本的概率分布类型: 多维正态分布
联合概率之积最大
各个参数可以计算出解析解
计算结果符合 "频度约等于概率" 规律
聚类的分布: 某个聚类的概率 = 所有样本属于这个聚类的概率 的 平均值
聚类中样本的分布
一般形式
假设某个样本属于某个聚类的一组参数为theta
最大似然函数 = 样本求和( log( 聚类求和()))
EM 算法的一般好形式
todo
em 的一般模型
从最大似然估计到em
把指示函数换成概率
三组数据
聚类的概率参数
要计算的值
作为每次迭代的初识条件
标记数据的值
混合高斯模型三组数据的迭代
聚类的概率更新公式:
某个聚类的概率 = 每个样本属于该聚类的概率之和 / 样本总数
聚类中心(高斯模型的期望) = 特征数据的加权平均值 (权重就是: 特征数据下该聚类的概率)
方差呢
混合朴素贝叶斯模型三组数据的迭代
em一般形式里
不断用下界函数的极值趋紧似然估计函数的极值
e-step: 下界函数上移的过程(使新下界函数与似然函数在当前当前下界函数极值点处相切)
m-step: 计算下界函数极值
公式的语言描述是什么
路上考虑
0 条评论
回复 删除
下一页
