机器学习
2018-01-15 18:35:34 47 举报AI智能生成
ASCHS
作者其他创作
大纲/内容
数据挖掘模型
图挖掘模型
现代信息检索模型
主题模型
LSA(ProbabilisticLatent Semantic Analysis)
LDA(Latent Dirichlet Allocation)
机器学习步骤
1.针对特定问题构造独立同分布数据，并进行数据清洗与预处理
数据处理：如何处理缺失数据（missing value）? 各种处理方法有什么利弊？
类不平衡处理
2.利用特征工程对原数据进行表达
特征工程
特征构造
根据业务知识构造
深度学习
特征选择
方式
过滤式
适合
特征向量各维度独立
缺点
只有数据概率分布不重叠的时候才适用
评价
可分性准则Gk=(类间均值向量的只差)^2/(类内方差)
包裹式
适合
特征向量各维度不独立
优点
不受模式分布形式的限制，但得有足够训练数据才有效
评价
类内散布矩阵Sw和类间散布矩阵Sb, |Sw^-1 Sb| 或者 tr(Sw^-1 Sb)
嵌入式
评价准则
直接准则
分类错误率最小
间接准则
最大信息增益等原理
测度G
散步矩阵形式的J1，J2
特征变换
降维
好处
使数据集更易使用
降低很多算法的计算开销
去除噪声
使结果易懂
K_L变换
思想
根据训练数据，用尽量少的正交向量来尽可能多地反映各类模式之间的差异
适合
K-L变换是一种适合于任意概率密度的变换
步骤
K-L展开式系数可如下求得：
1.求随机向量x的自相关矩阵：R = E{xxT}
2.求出矩阵R的特征值λj和对应的特征向量φj，j = 1,2,…,n，得矩阵：
3.计算展开式系数：a = ΦTx
1.求随机向量x的自相关矩阵：R = E{xxT}
2.求出矩阵R的特征值λj和对应的特征向量φj，j = 1,2,…,n，得矩阵：
3.计算展开式系数：a = ΦTx
由此可以看出，λj值越小，误差也越小。前提是E(x)=0，则Cx=E(xx^T)=R。即若自相关矩阵R(X,X^T)等于协方差矩阵COV(X,X^t),则K-L变换等同于PCA
PCA
Principal Component Analysis
主成分分析
概念
以方差的大小来决定新的维度，方差越大信息量越大
优化目标
优点
降低数据的复杂性
识别最重要的多个特征
缺点
不一定需要
可能损失有用信息
适用
数值型
案例
半导体制造数据降维
LDA
概念
最大化类间距离，最小化类内距离
又称“Fisher”线性判别
最后维度是C-1，C为类别数量
优化目标
SVD
Singular Value Decomposition
奇异值分解
概念
从噪声数据中抽取相关特征
还是不懂！
矩阵分解
m行n列矩阵分解成三个矩阵相乘，分别m行m列，m行n列，n行n列
中间那个m行n列矩阵只有对角元素，且对角元素从大到小排列
对角元素称为奇异值
在某个奇异值的数据（r个）之后，其他奇异值都置为0
数据集中只有r个重要特征
优点
简化数据
去除噪声
提高算法结果
缺点
数据的转换可能难于理解
适用
数值型
案例
隐性语义索引
LSI/LSA
抽取文档中的概念
解决同义词问题
推荐系统
先利用SVD构建主题空间
再在该空间下计算相似度
图像压缩
保留奇异值
NMF矩阵分解
3.模型选择与训练
机器学习算法分类
监督学习
从损失优化角度看待
问题简介
机器学习的目标是选择期望风险最小的模型，但由于联合分布P(X,Y)是未知的，期望风险无法直接计算。实时上如果知道了联合分布P(X,Y),就可以从联合分布直接求得条件概率分布P(Y|X)了，也就不需要学习了。监督学习其实是个病态问题。虽然不能求得期望损失，但根据大数定律，我们可以用经验损失来逼近期望损失
四要素
1.独立同分布数据
2.模型函数的三种选择
判别模型
判别函数类型，拟合得到 f(X)
概率判别模型，直接是拟合得到P(Y|X),运用时直接算得P(Yi|X)，进行判断
生成模型
先学习P(X,Y),再通过贝叶斯展开算得P(Y|X)，运用时需要求出使得P(Yi|X)最大的Yi
3.损失函数L(Y,f(X))
回归
真实损失函数是误差平方
分类
真实损失函数
0-1损失函数
近视逼近损失函数
Hinge合页损失函数
SVM
对数损失函数
logistic回归
指数损失函数
Adaboost
误分类点到超平面的距离
感知机(采用ERM)
4.风险最小化
三种风险最小化
期望风险(机器学习真正面向的优化目标)
理论上模型f(X)关于联合分布P(X,Y)的平均意义下的损失，称为期望损失，Rexp=Ep(L(Y, f(X)))
经验分风险最小化(基于大数定律逼近期望风险)
基本了解
由于现实中训练样本数目有限，甚至很小，所以用经验风险估计期望风险往往不理想，容易过拟合等。因此引入结构风险概念，对经验风险进行一定矫正
适合
样本容量足够大，即足够代表测试数据集时
缺点
当样本容量很小时，即该数据集不能代表测试集，经验风险最小化容易过拟合
模型f(X)关于训练数据集的平均损失称为经验风险或经验损失，Remp(f)=1/N(累加 L(yi, f(xi)))
结构风险最小化(加入L1，L2正则项，增强经验误差法的泛化能力)
基本了解
结构风险最小化等于正则化，结构风险在经验风险上加上表示模型复杂度的正则化项或罚项
结构风险最小化需要经验风险或模型复杂度同时小，符合Occase剃须刀原理
适合
样本容量较小或较大的时候都适用。
机器学习四要素经典模板框架（具体化，实例化）
最小化ERM(当数据量够大时使用)
判别函数角度
概念：当损失函数是误差的平方的时候，经验风险最小化即为最小均方误差
最小均方误差LMS
例子
线性回归、广义线性回归
备注：在判别函数角度下的MLE
概率角度
概念：当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计(与MLE仅仅差一个负号，本质一样，起了个好听的名字罢了)
极大似然估计法MLE
例子
广义线性模型
如果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 回归
logistic回归分类
备注：在概率角度下的LMS
最小化SRM(数据量不够的时候使用)
判别函数角度
概念：损失函数采用误差的平方，加入了W 的 L2正则项，采用SRM
最小化结构化均方误差
备注：等价于在判别函数角度下的MAP
概率角度
概念：当模型是条件概率分布，损失函数时对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计(与MAP仅仅差一个负号，本质与MAP一样，MAP起了个好听的名字罢了)
极大后验概率MAP
例子
朴素贝叶斯
备注：等价于在概率角度下的正则化LMS
以问题导向划分
回归
基本概念
用函数拟合数值型数据集
算法
线性回归
优点
易于理解
计算不复杂
缺点
对非线性数据拟合不好
适用
数值型
标称型(标称型数据将被转化成二或多值型数据)
数据特征比样本多
岭回归
lasso
前向逐步回归
树回归
概念
对数据进行二元切分
节点为数值或线性函数
优点
可以对复杂和非线性数据建模
缺点
结果不易理解
适用
数值型
标称型
广义线性回归(多项式回归)
局部线性回归
四要素
1.独立同分布数据
2.f(x)-线性或者广义线性
3.平方损失
4.经验损失(当误差符合高斯分布时候，相当于MLE)；结构损失(当误差符合高斯分布时候，加上P(w相当于MAP)
分类问题
四要素
1.独立同分布数据
2.模型函数的三种选择
判别模型
判别函数类型，拟合得到 f(X)
概率判别模型，直接是拟合得到P(Y|X),运用时直接算得P(Yi|X)，进行判断
生成模型
先学习P(X,Y),再通过贝叶斯展开算得P(Y|X)，运用时需要求出使得P(Yi|X)最大的Yi
之所以叫生成模型是因为学习了P(X,Y),可以拿来生成数据
3.常见损失函数L(Y,f(X))
真实损失函数
0-1损失函数
近视逼近损失函数
Hinge合页损失函数
SVM
对数损失函数
logistic回归
指数损失函数
Adaboost
4.经验损失；结构损失
传统算法
感知器算法
概念
思想
对错误数据进行权值惩罚，正确分类数据权值不变
线性可分情况下收敛
学习算法
SGD学习
适合
二分类问题
特点
判别函数模型
分离超平面
模型要素
2.模式函数选择
线性分类平面
3.损失函数
误分类点到超平面的距离
4. 采用经验损失函数ERM
误分类点集到分类平面的距离之和
k-近邻算法（kNN）
概念
采用测量不同特征值之间的距离方法进行分类
适用
多类分类，回归
特点
判别函数模型
特征空间，样本点
优缺点
优点
精度高
对异常值不敏感
无数据输入假定
缺点
计算复杂度高
空间复杂度高
案例
约会网站效果匹配
手写识别
朴素贝叶斯
概念
思想
模型使用
采取极大化后验概率
y=argmax_YiP(Yi|X)，选取使得后验概率最大的Yi 作为当前分类
如果P(Y|X)是真实分布，则等价于最大化期望损失，但是P(Y|X)是根据数据估计得到的，故实际只是最大化经验损失
假定特征相互独立P(X|Y)=P(X1|Y)P(X2|Y)...P(Xn|Y)
强假设条件
学习算法
采用极大似然函数法估计P(X) P(Y|X)，并获得计算公式
通过贝叶斯估计引入了拉普拉斯平滑，避免0概率出现
默认了类分布和特征分布式均匀分布，模型实际使用时候，数据量够大，则该影响忽略
EM算法
特点
生成式模型
典型的生成学习方法（由训练数据学习联合概率分布P(X,Y)，然后求得后验概率分布P(Y|X)）。具体来说，利用训练数据学习P(X|Y)和P(Y)的估计，得到联合概率分布：P(X,Y)=P(Y)P(X|Y)
学习的是P(Y)，P(X|Y),采用极大似然估计或贝叶斯估计
贝叶斯估计引入了拉普拉斯平滑
通过贝叶斯估计引入了拉普拉斯平滑，避免0概率出现
默认了类分布和特征分布式均匀分布，模型实际使用时候，数据量够大，则该影响忽略
计算某一点落在不同群落里的概率
优缺点
优点
在数据较少情况下仍然有效
可以处理多类别问题
即使特征之间的独立性条件不成立，模型任然有就好准确率，鲁棒性强
缺点
对输入数据的准备方式较敏感
四要素
角度一
2.采用生成时式模型，P(Y|X)
3.对数损失函数
对数损失函数
4.采用ERM，即优化对数似然函数损失
角度二
模型使用
采取极大化后验概率y=argmax_YiP(Yi|X)，选取使得后验概率最大的Yi 作为当前分类
参数的学习采用极大似然函数法
注意模型的使用时极大后验概率法
模型要素
2.函数模型
适用
标称型(text data中常见)
案例
垃圾邮件检测
高斯判别分析GDA
概念
特点
生成模型
如果特征向量是离散的用NB朴素贝叶斯，如果向量是连续数值型，采用GDA替代NB
支持向量机
概念
概念
思想
求解能够正确划分训练数据集并且几何间隔最大化的分离超平面
硬间隔和软间隔
学习算法
利用SMO 计算最大值
1.利用SMO算法求解α*
2.利用α*求解w*和b*
特点
判别函数模型
分离超平面
核函数技巧
将数据映射到高维空间更容易被分类
核函数对数据进行隐性的高维映射，即计算代价维低维，但是实际特征被映射到高维空间
径向基函数
流行核函数
SVM对偶形式
优缺点
优点
泛化错误率低
计算开销不大
结果易理解
核技巧
缺点
对参数调节和核函数的选择敏感
原始分类器不加修改仅适用于处理二类问题
适用
数值型
标称型
案例
手写识别
模型要素
2.模式函数选择
线性判别界面函数
3.损失函数
合页损失函数HInge
4.采用SRM
采用SRM，即加入||W||正则化，变为软边距SVM
调整
如果超平面效果不好, 把低维向量映射成高维向量, 根据高维向量的超平面计算
由于需要频繁计算向量的内积, 而计算高维向量的内积需要: 两次映射函数计算 + 一次内积计算, 计算量很多大, 就引入了核函数
定义核函数K(x, z) 的值 等于 "内积( 映射函数(x), 映射函数(z))" 的值
但是核函数的计算复杂度要少很多, 因为核函数的包含变量的最外层操作一般是乘积操作
而在机器学习中, 大家比较关心内积的值, 而不关心映射函数的具体形式是否准确
因为机器学习就是一个不断凑数的过程, 映射函数只要大致合理即可
所以先找到一个核函数用来代替内积运算, 计算出高维超平面的各个系数.
预测新样本的时候, 要先映射到高维空间, 然后看高维向量在高维超平面的上方还是下方
映射到高维空间的具体形式不用管，最后还是计算内积。所以核函数对应的映射函数不用考虑
常用的核函数
普通内积: 相当于映射到自身
(内积 + t)^d : 映射到一个最高阶为d, 的变量组合
高斯核
映射函数是啥
如果即使映射成高维向量也不能线性可分, 适当放宽条件
不等式约束放宽一点: 原不等式左边 + 小量 > 0
svm模型，没有等式约束。如果有等式约束，是否要放宽
小量为正值
实际是允许某些点穿过超平面一小段距离
为了使所有小量整体最小（整体放宽的尽量小）： 原函数 变成： 原函数 + 所有小量和
每个放宽的小量作为新的变量, 仍旧是一个凸约束极小值问题
元算法
AdaBoost
AdaBoost
概念
思想
通过改变训练样本的权重，学习多个弱分类器，并将这些分类器进行线性加权组合，得到强分类器
弱分类器的权重等于1/2log((1-em)/em),em为第m个弱分类器在训练数据在权值分布Dm上的分类误差率
根据αm计算得到下一轮的数据权重分布Dm
核心问题
1.在每一轮训练中如何改变训练数据的权值或概率分布
2.如何将每一轮训练到的弱分类器组合成强分类器
推广(前向分布算法的特例)
前向分布算法
思想
学习的是加法模型
如果能够从前向后，每一步只学习一个基函数及其系数，那么就可以逐步逼近优化目标函数，简化学习算法复杂度
AdaBoost
前向分布算法的特例
基本分类器的加法模型，损失函数是指数函数
优点
不容易出现overfiting过拟合现象
training error从高降低到0的过程中，test error一直下降，不存在上升拐点
较低的泛化误差
训练误差率指数下降，自适应各弱分类器的训练误差率
改善分类器的正确率
可以配合多个分类器算法使用
缺点
对奇异值点很敏感，因为异常点容易分错， 会逐级影响后面的产生的弱分类器
适合
二分类问题
特点
判别模型
弱分类器的线性组合
模型要素
2,.模型函数选择
由基本分类器组成的加法模型
选择的弱分类器最好是偏差小方差大的分类器，应为adaboost的加权求和方式能降低整体方差
对于每个特定的训练数据集，基本分类器的性能不能过于复杂。且1/2-错误率要大一些。不能过大，不能过弱，凭经验。
3.损失函数
指数损失函数，exp[-yi*（fm-1(X)+αGm(Xi,γ)）]
采用前向分布算法，每一步都是极小化加法模型的中指数损失函数，学习得到一个基函数及其系数
4.采用前向分步算法，每一步极小化经验风险ERM
决策树
概念
不用角度的理解
从训练树中归纳出的一组分类规则
基于特征空间划分的类的条件概率模型
深浅不同的决策树对应着不同复杂度的概率模型
学习算法
1.特征选择
信息增益information gain最大化
考虑选择哪个特征来对当前的特征空间进行划分最好，信息增益能够描述哪个特征具有更好的分类能力
IG(X|A)=IG(A|X)=H(X)-H(X|A)=H(X)+H(A)-H(X,A)
H(A,X)=H(A)+H(X|A)
信息增益比
信息增益存在偏向于选择取值较多的特征的问题，信息增益比可以抑制这种问题
2.决策树生成
ID3
基于信息增益最大化准则构建决策树
缺点：只有树的生成过程，没有剪枝，容易产生过拟合
C4.5
基于信息增益比最大化准测构建决策树
CART
分类回归二合一
回归树
基于平方误差最小化准则进行划分变量和划分点的选择
分类树
基于基尼指数最小化准则进行特征及其切分点的选择，构建决策树
基尼指数类似于熵，都是衡量随机遍历的不确定性
3.决策树减枝
优点
模型具有可读性
分类速度快
计算复杂度不高
对中间值的缺失不敏感
可以处理不相关特征数据
最大信息增益准则能够将不相关特征识别出来
缺点
可能会过度匹配
适用
数值型
寻找阈值，将数值划分为(两个)多个区间；按照信息增益最大化标准来选择阈值
标称型
案例
眼部状况和适配的隐形眼镜类型
集成学习
思想
三个臭皮匠，胜过一个诸葛亮。追求模型中基学习器和个体学习器的“好而不同”。学习器不能太坏，并且要有多样性
集成对泛化误差的好处？
方法
Boosting
GDBT
思想特点
基分类器
以CART作为基分类器
集成方法Boosting
使用提升学习，每一棵树学的是之前所有树结论和的预测结论与真实结果的残差(回归问题，提升树的特点)
优化过程
在优化时用到一阶导数信息,即以损失函数的负梯度，对f_m-1(x)求导，估计残差(回归问题)
收敛速度更快
适合一般的问题，只要损失函数一阶可导
子节点分裂
回归树
平方误差最小准则
分类树
基尼指数(类似熵，能表征变量的不确定性)最小准则
损失函数
回归问题，平方误差
分类问题，在生成节点的时候没有考虑损失函数，在减枝的时候引入基尼指数做预测误差，叶子节点数作为正则项
剪枝
等树构造完成后，在预测误差中加入叶子节点树作为正则项目，从低往上构造子树序列，用验证集合进行选取最优剪枝结果
Xgboost(GDBT的改进)
思想特点
基分类器
以CART或线性分类器作为基分类器
集成方法Boosting
使用提升学习，由于引入了正则项，每一颗数拟合的不仅是残差，还要考虑正则项
优化过程
xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数
子节点分裂
使用打分函数
该打分函数可以先不考虑类别值而进行左右分裂，分裂后再回头确定选择的特征，因此可以处理缺失值。以后如果预测的时候特征值缺失，则分到右边
随机特征集话划分，集合内选最优
xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性
Shrinkage
相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间
损失函数
损失函数引入正则项，正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和
特征值的处理
对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
剪枝
由于损失函数加入了正则项，所以在生成过程中进行了一定程度的剪枝，泛化性能更好
等树生成后，任然进行了回头剪枝
支持并行，并行是体现在特征部分
参数
General parameters
Bagging
随机森林
思想
在Bagging基础上加入属性扰动
结合策略
平均法
加权平均法
投票法
学习法
stacking
Logistic回归
概念
划分两个数据集之间的分界线，类似回归
梯度下降算法
随机梯度下降
减少计算量
优缺点
优点
计算代价不高
易于理解和实现
缺点
容易欠拟合
分类精度可能不高
适用
数值型
标称型
案例
从病症预测死亡率
特点
判别模型
四元素
角度一
2.采用判别概率模型
模式函数是P(Y=1|X)=exp(W*X)/(1+exp(W*X))
3.对数损失函数
4.采用ERM，基最小化对数似然函数损失
角度二
极大化对数似然函数
高斯判别分析GDA
现流行算法
神经网络
如果数据不是线性可分的，即不存在一条直线或一个超平面，能把数据分成两部分。就在中间插入一次层中间值。
一个x向量经过多个sigmoid函数，变成一个中间向量，中间向量再经过一个sigmoid函数，得到最终结果。
这几个sigmoid函数互不相同
因为是分成两部分，所以是sigmoid函数。是否有其它情况，使用其它函数
成本函数为误差的平方和
成本函数就是计算最小值的函数
由于最终的目标函数是由多个函数复合而来，非常复杂，所以y的误差符合标准正态分布
利用梯度下降算法计算成本函数最小值的过程叫"反向传播"
神经网络
概率图模型
贝叶斯网络(有向概率图模型)
马尔可夫模型
三大问题
1.模型预测Y=argmax_YP(Y|X,λ)
维特比算法（借助动态规划算法）
2.概率计算，P(X|λ)
3. λ=(A,B,π) 学习
马尔可夫随机场(无向概率图模型)
线性链条件随机场
词性标注
话题模型LDA
排序问题
无监督学习(聚类问题):
整体思想
先设定参数初始值
根据参数, 标记样本 或计算出 每个样本的每个标记值 的概率
根据标记结果, 重新计算参数: 称为 m-step
以上两步反复, 直到收敛
常见算法
K-Means法
概念
设定簇个数
随机确定初始簇心
寻找各点最近的簇心
避免收敛到局部最小
度量效果
SSE误差平方和
后处理
将最大SSE簇拆分
合并
最近质心
使SSE增加最小的两个质心
二分K-均值
有一个簇不断一分为二
思路
优化目标是样本距离聚类中心的距离之平方和最短
类比的最小二乘法
过程
设定参数初值
先给初识化K个聚类中心
由于优化目标不是凸函数, 所以可以随机初始化多次, 取最优结果
根据参数标记样本
每个样本离哪个聚类中心最近, 就标记为该聚类
根据标记结果重新计算参数
每个聚类根据其内部样本, 更新中心位置(数据的平均值)
上两部不断循环, 直至聚类中心的位置不变. 迭代过程中剔除空聚类
评价
优点
易实现
缺点
可能收敛到局部最小值
在大数据集上收敛较慢
适用
数值型
案例
对地图上的点进行聚类
GMM(高斯混合模型)
概念
将数据分布视为是多个高斯分布的叠加
EM算法: Expectation-Maximization
思路
每个样本的标记数据为: 样本和聚类的联合概率
优化目标: 样本的整体出现概率最大 ( 样本出现的概率之积最大)
每个样本出现的概率 = 样本与聚类的联合概率, 对聚类加和
过程
设定参数初值
所有概率分布的参数
标记样本
根据标记结果重新计算参数
数学技巧
上两部不断循环, 直至聚类中心的位置不变. 迭代过程中剔除空聚类
混合高斯分布
假设条件
每个聚类在所有聚类中的概率分布类型: 多项式分布
要求: 样本覆盖全面, 能反应出聚类的分布状况.
每个聚类出现某个样本的概率分布类型: 多维正态分布
在此条件下, 使用一个简单的优化目标:
联合概率之积最大
各个参数可以计算出解析解
计算结果符合 "频度约等于概率" 规律
聚类的分布: 某个聚类的概率 = 所有样本属于这个聚类的概率 的 平均值
聚类中样本的分布
期望 = 样本属于该聚类的概率作为权重, 对样本值的加权平均
方差 = 样本属于该聚类的概率作为权重, 对样本与聚类中心的距离的平方的 加权平均
一般形式
假设某个样本属于某个聚类的一组参数为theta
最大似然函数 = 样本求和( log( 聚类求和()))
FP-growth算法
概念
基于Apriori
结合树模型建模
比Apriori快
优点
快于Apriori算法
缺点
实现困难
在某些数据集上性能会下降
适用
标称型
案例
从微博中发现共现词
新闻报道被查看的集合
Apriori算法(关联规则)
概念
关联分析
频繁项集
关联规则
优点
易实现
缺点
在大数据集上较慢
适用
数值型
标称型
案例
过会投票的模式
毒蘑菇相似特征
半监督学习
强化学习
状态到行动的映射
学习训练算法
梯度下降
随机梯度下降SGD
批量梯度下降BGD
牛顿法
EM算法
概念
思想
通过不断求解下界的极大化逼近求解对数似然函数的极大化算法
是一种近似计算含隐变量概率模型的极大似然估计的方法
步骤
1.确定隐变量，写出完全数据的对数似然函数
2.求解当轮的Q函数，Q(θ，θi)=累加Z（P(Z|Y,θi) logP(Z,Y|θ)）
Z为隐变量
θi 为已知量，θ为未知量
3.求解θi+1=argmax_θ[ Q(θ，θi) ]
注意
EM算法不能保证找到全局最优
适合
含有隐变量的概率模型参数的极大似然估计
应用
高斯混合模型
非监督学习中，将隐变量视为是标签变量，即可学习生成模型的联合概率密度P(X,Y)，X为观测数据，Y为未观测数据
4.模型评估
理论
学习理论
计算假设的目标就是使: 理论误差最小
理论误差是什么
理论误差无法直接使用, 使用经验误差
如何评判一个模型, 以及根据这个模型计算出来的假设
一个模型泛化能力强, 即根据这个模型计算出来的假设的理论误差小. "理论误差"就是"误差的数学期望"
理论误差 又叫 泛化错误率
我们都是根据经验误差最小的方式来计算出某个假设. "经验误差" 就是 "误差的样本均值"
注意，为了增强泛化能力，也引入了结构误差
假定: 某个假设"对单个样本分类错误"的概率服从伯努利分布
理论误差就等于该伯努利分布的期望
经验误差就等于该伯努利分布的样本均值
对于某一个假设, 经验误差和理论误差 相差多少
根据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, 解一个方程组
如果能化简为只剩一个变量
只剩一个变量的方程，牛顿法求解
只剩一个变量的拉格朗日函数, 利用数值趋紧的方式求解
如果上一步无法做到, 只能每次选择最合适的变量，改变它们使函数取得最大（小）值。不断循环直至收敛。这个算法称为： 坐标上升（下降）法。
如果多个系数相互关联，每次选两个系数
下界函数趋近
适用于情况: 可以找到一个下界函数, 该下界函数的极值很容易计算(例如: 可以直接求得解析解)
计算过程: 不断更新这个下界函数, 使下界函数的极值点逐渐接近原函数的极值点
原因是: 一步找到合适的下界函数是困难的, 我们只能逐步修正下界函数
方法是: 在旧的下界函数极值点处, 令新的下界函数值等于原函数的值, 计算新下界函数的极值. 直到下界函数在极值点处与原函数重合
该方法可行的理由(自己归纳,不太严谨):
先假定 原函数和下界函数都是平滑的.
最终结果需要满足两个条件
是下界函数的极值点
是下界函数和原函数的重合点
理由
下界函数的极值点如果跟原函数有重合点, 肯定是相切而不是相交. 否则就不能称之为下界函数了.
所以两者的切点, 要么是在两者的极值处, 要么都不在极值处. (切点处导数相同)
迭代过程不断接近最终结果
下界函数计算极值: 更接近原函数极值
更新下界函数: 新下界函数与原函数相切, 其极值点比切点更接近原函数极值点
对下界函数的要求
形状接近: 下界函数的凹凸性与原函数相同
在某个点与原函数相等
计算过程需要
概率
概率中的逗号表示两个都是随机变量，联合概率分布。分号表示后一个是固定值，作为概率分布的参数出现
学习资源
scikit-learn
quick start
Iris dataset
digits dataset
scikit 传统机器学习算法选择步骤图
中文quick start
深度学习
caffee
tutorial PPT
Flickr PARK or BIRD
paper
demo
demo
图片识别
article: 中文
articles: 深度学习笔记
ANN
会议刊物
ICML
NIPS
JMLR
0 条评论
下一页
