2019年2月10日星期日

why-what-how方式的机器学习总结之三

采样方法


why


采样方法最常用的场景是用来求一些不好计算原函数的积分,或者求一些分布的期望值,关键词蒙特卡洛积分。













比如上面这张图,正方形的面积很容易知道,计算绿点占所有采样点的比例乘以正方形面积就可以得到f(x)曲线下方的面积也就是f(x)从a到b的定积分。

还可以从期望的角度来看采样法,假设g(x)不好求积分,令





把g∗(Xi)看成新的独立同分布的随机变量,其密度函数是fx(x),所以可以得到期望,






再由大数定理期望等于均值,





所以只需要按照分布fx(x)大量采样求均值就可以得到g(x)的积分。

这个地方fx(x)是我们自己变换出来的,所以可以随意选择,我们可以选择成在区间[a,b]上的均匀分布,那么剩下的就容易解决了。详细可看蒙特卡洛(Monte Carlo)法求定积分

如果要求一个分布的期望,可能就需要直接对目标分布进行采样,而这是一个难点,所以会有很多采样的方法,比如逆采样,接受-拒绝采样,重要性采样,MCMC采样以及吉布斯采样等等。

what


1.逆采样(Inverse Sampling)

逆采样是想通过均匀分布变换目标分布的采样,如下图


(1)如左图纵坐标,从 Uniform(0,1) 中随机生成一个值用 u 表示。

(2)计算的值 x,则 x 就是从 f(x) 中得出的一个采样点。这个过程就是上图中红线表示的,F(x)是累积分布函数CDF。

更多细节参考逆采样(Inverse Sampling)和拒绝采样(Reject Sampling)原理详解,数学原理可以参考维基百科,这里不展开了,逆采样需要能求CDF的反函数,有时候会很困难。

2.接受-拒绝采样












如上图,红色的p(x)可能采样太困难,我们找一个比较好采样的函数q(x),并且让kq(x)的曲线能包住p(x)。采样过程,
(1)x 轴方向:从 q(x) 分布抽样得到 a。
(2)y 轴方向:从均匀分布(0, kq(a)) 中抽样得到 u。
(3)如果刚好落到灰色区域: u > p(a), 拒绝, 否则接受这次抽样。
(4)重复以上过程。

在高维的情况下,Rejection Sampling 会出现两个问题,第一是合适的 q 分布比较难以找到,第二是很难确定一个合理的 k 值。这两个问题会导致拒绝率很高,无用计算增加。

3.重要性抽样(Importance sampling)

和接受-拒绝采样类似,也是通过较容易采样的分布来解决问题。









如上图对p(z)做了简单的变换,采样的目标分布是q(z),可以吧p(z)/q(z)看成一个样本点的重要性。

这种方法的问题是在高维空间里找到一个这样合适的 q 非常难。更详细的可以看随机采样方法整理与讲解(MCMC、Gibbs Sampling等)


4.MCMC(Markov Chain Monte Carlo)

MCMC采样的基本原理马尔科夫链和马尔科夫稳态的基本原理可以看随机采样方法整理与讲解(MCMC、Gibbs Sampling等),这里只整理一下基本逻辑。

(1)样本按照某个转移矩阵P不断进行转移跳转,最终一定会到达一个马尔科夫稳态再进行跳转也不会发生变化,要求这个转移矩阵P的任意两个状态都是连通的。

(2)马尔科夫稳态有一个特点是满足细致平稳条件,一般的转移矩阵是不太会满足这个条件的,所以我们想把一个一般的转移矩阵P改造得满足细致平稳条件。

(3)改造的方法是按照对称性制造一个接受矩阵,按一定的接受率接受跳转。

(4)实际工作方式按个人理解是采样的过程是先初始化n个采样点,然后对每个采样点做马尔科夫跳转,这个跳转是指转移到其它的状态,而这个跳转概率在我们要求的转移矩阵里面,直到最后不再跳转为止,跳转的方法由细致平稳条件推出的那个跳转公式来决定。

(5)上面的方法存在一个问题是可能会拒绝大量的跳转导致收敛太慢,所以MH方法来优化这个过程。MH方法只是放大了接收率。

(6)实际应用中高维数据很常见,高维下如果固定一个维度做跳转是能满足细致平稳条件的,所以就有了轮换固定维度跳转的Gibbs Sampling,应用非常广泛。

主题模型


why


我们希望机器学习能帮我们自动理解一篇文章,最简单的观点是把文章看成一组单词的无序组合,这个就是词袋模型(BOW)。但是BOW实在太简单,稀疏生僻词,一词多义,同义词等等问题都无法描述,所以我们在词袋模型中引入了主题(Topic)这个概念,认为一篇文章在描述多个主题,每个主题又包含多个单词。

主题模型这里主要记录一下,LSA,PLSA和LDA。之前我认为可以用主题模型搞定评价的标签词分析的,后来发现不合适,评价这样的每篇文档都太短,而且标签词实际上是短语。

what


1.LSA(潜在语义分析)

LSA的工作方式是对Term-Document矩阵做SVD分解,详细可参考LSA,pLSA原理及其代码实现,感觉还是比较简单粗暴,有不少问题,比如一词多义就无法解决。

2.PLSA(概率潜在语义分析)

和LSA不同,PLSA是一种概率模型。PLSA是这样看一篇文章的生成过程的,首先找k个主题,然后对于每个主题按照主题-词语的概率随机生成多个词语,所有这些词语组成文章。

可以看到PLSA并没有考虑词语的顺序以及位置等关系,所以还是词袋模型。这个模型里面doc-topic是随机选择的而topic-word是个多项分布也是我们需要求解的。

每个词语的生成概率是,






对于第m篇文档的n个词语的生成概率是,





有了文档的概率就可以写出最大似然函数然后用EM方法求解了,详细的可参考LDA数学八卦

3.LDA(Latent Dirichlet Allocation)

PLSA是属于频率学派的模型而LDA是属于贝叶斯学派的模型。在PLSA里面文档对应的主题θ,主题对应单词φ都是模型的参数,这些参数都是有确定的值我们求解这些值就可以了。在LDA里面θ和φ都是概率分布,那它们的概率分布是什么呢?由于在PLSA里面θ和φ都是多项分布的参数,所以对应到贝叶斯模型在LDA里面 θ和φ 的先验分布就可以选多项分布的共轭分布Drichlet分布。

LDA一篇文档生成过程大致如下,

(1)通过Drichlet分布(参数α)生成doc-topic多项分布的参数θ。
(2)接下来生成一个词,先用多项分布(θ)生成一个topic编号z。
(3)通过Drichlet分布(参数β)生成k个topic-word多项分布的参数φ1...φk。
(4)挑选出参数φz,然后用多项分布(φz)生成一个词。
(5)重复步骤2和4生成n个词,注意步骤3不用重复做。
(6)生成新的文档的时候需要重做步骤1。

这整个过程中有M+K个独立的Dirichlet-Multinomial共轭结构,其中M对应M篇文档,K对应所有M篇文档相关的K个topic。模型的图解如下。












M篇文档中topics的生成概率是









M篇文档中词的生成概率是









联合概率是







有了联合概率就可以用EM法来求解了,不过解起来相当复杂还需要用到变分法,另一种方法就是用吉布斯采样来解。吉布斯采样的目标是估算模型中的参数φ1...φk和θ1...θm,注意不是α,β,它们是先验参数可以预先指定。

采样的过程如下,
(1)随机初始化,对语料中每篇文档中的每个词随机赋予一个topic编号z。
(2)重新扫描整个语料库,按吉布斯采样公式重新计算topic并在语料库中更新。
(3)重复上面的过程直到收敛。
(4)统计语料库中topic-word共现频率矩阵,就可以得到我们需要估算的参数。

 如果来了一篇新文档需要我们分析对应的topic,那我们只需要求参数θ,同样可以用吉布斯采样过程直到收敛,然后统计文档中的topic分布就能得到θ。

最后剩下的是吉布斯采样公式,就只记录结果了,详细推导过程可以看LDA数学八卦






神经网络和深度学习


why


神经网络要解决的问题和一些基础的机器学习方法相同,也主要是分类问题和回归问题。不同的地方是像逻辑回归,朴素贝叶斯这些本质上来说都是线性模型,而n维线性模型的vc维是n+1也就是说要增加模型的容量只能增加维度。而神经网络尤其是深度神经网络是非线性的,神经网络的vc维是每一层的节点数(维度)的乘积,所以增加神经网络的深度可以很轻易的获得非常高的模型容量,这也是深度学习很火的重要原因。

what


1.神经元是组成神经网络的基本单位,如下图(来自神经网络--反向传播详细推导过程)








这个神经元是以x1,x2,x3以及b=1作为输入的运算单元,其输出是



其中f被称作激活函数,比如可以用sigmoid函数作为激活函数,当使用sigmoid的时候这个神经元实际上是在做逻辑回归。激活函数还有其他的选择,详细可参考《深度学习》,6.3节。

2.多个神经元联接起来就可以组成神经网络,










上图中的输出是单个值,输出也可以是多个值组成一个向量。

3.前向传播,就是通过输入得到输出以及网络中任意一个节点值的过程,比如上图中的神经网络就可以这样计算,







4.反向传播(详细可看深度学习:神经网络中的前向传播和反向传播算法推导),是指在训练的时候把训练误差反馈到神经网络的权值参数矩阵的过程。比如下面的网络,
















每个权重对误差的影响可以通过下图直观的看到,主要也就是一个链式求偏导数的过程,












how


1.神经网络这个牛逼的名字是怎么来的?可以看看这篇科普神经网络浅讲:从神经元到深度学习,神经网络的神经元确实有点模仿人脑神经元的结构,输入可以类比为神经元的树突,而输出可以类比为神经元的轴突,计算则可以类比为细胞核。还有一点仿生的地方在激活函数,激活函数也像人脑神经元一样达到某个临界状态后就一直处于工作状态,否则就一直是休眠状态。再有就是神经网络的反向传播机制也和人脑的反馈机制比较相似。

2.为什么有激活函数?除了仿生之外激活函数在神经网络中的功能即通过对加权的输入进行非线性组合产生非线性决策边界。

3.神经网络牛逼的理论依据?万能近似定理(universal approximation theorem)(Hornik et al., 1989;Cybenko, 1989) 表明,一个前馈神经网络如果具有线性输出层和至少一层具有任何一种‘‘挤压’’ 性质的激活函数(例如logistic sigmoid激活函数)的隐藏层,只要给予网络足够数量的隐藏单元,它可以以任意的精度来近似任何从一个有限维空间到另一个有限维空间的Borel 可测函数。详细可见《深度学习》6.4.1节。

4.为啥需要深度神经网络?这个用vc维可以解释,如果用浅层的神经网络描述精度要求非常高的函数可能需要的隐藏单元的数量是指数级,深度神经网络可以把指数化简到深度。

5.深度学习仅仅就是深度神经网络么?答案当然是no,深度学习有三个核心概念,多层组合,端到端学习以及分布式表示,参考深度学习究竟是个啥?。多层组合比较好理解,神经网络就是一种多层组合。端到端学习是指不用做特征工程,由算法自动学习数据中的特征,卷积神经网络就是一个典型的例子,只用给原始的图像二进制数据和最后需要的分类结果就可以了。而分布式表示则需要重点说一下。

6.分布式表示,比如“你有一辆大的蓝色福特汽车”用分布式表示就是尺寸+颜色+品牌,我个人的理解就是一种正交的本质的表示方式。因为深度学习可以用函数复合的方式来实现分布式表示,我突然想到函数式编程也是这么个玩法,函数式编程也是能做到高度的抽象能提炼出系统本质的东西,主要的区别是函数式编程是靠人去建立这种分布式表示吧。

7.那怎么学习到分布式表示呢?《深度学习》 里面说k-means,决策树,高斯混合模型等等都不是基于分布式表示的学习算法。有一种里程碑式的学习算法叫无监督预训练,简单的说就是多层训练,每一层用自编码器或者受限玻尔兹曼机自动抽取特征,然后把上一层的输出作为下一层的输入。具体可以看《深度学习》15.1节以及浅谈深度学习分布式表示以及不同结构

8.深度神经网络的Batch Normalization(详情见Batch Normalization导读)
(1)深层神经网络的在层次较深的地方输入会逐渐靠近极大和极小值使得梯度消失,BN就是通过一定的规范化手段,把每层神经网络任意神经元这个输入值的分布强行拉回到均值为0方差为1的标准正态分布。
(2)变换的结果是让梯度变大,但是又可能会让函数接近线性化使得多层的意义减弱,因为多层线性网络和单层线性网络等价,所以BN对每层又会做调整y=scale*x+shift,来综合梯度和线性问题,这一步非常非常关键,而且scale和shift都是要通过学习得来的又叫变换重构

9.tf.clip_by_global_norm,是一种处理梯度爆炸或消失的一种方法,实际上就是每层传播的时候对梯度进行缩放,然后按照这个缩放的比例之后去更新参数,详细可见 tf.clip_by_global_norm理解



卷积神经网络(CNN)


关于CNN,这篇吴恩达的课程笔记第四门课 卷积神经网络,写得非常清楚详细,我简单的做一下摘要帮助快速索引。

why


CNN最典型的应用是图像识别,比如图片分类判断一张图片是不是猫。那为什么不用普通的深度神经网络来做呢?这就要提到CNN的三个重要特点参数共享,稀疏连接和等变标识。

1.参数共享是说CNN会用一个过滤器处理图像中所有的部分,比如下图中的3×3的过滤器检测垂直边缘。










2.稀疏连接如下图,绿圈这个0是通过3×3的卷积计算得到的,它只依赖于这个3×3的输入的单元格,右边这个输出单元(元素0)仅与36个输入特征中9个相连接,红圈这个30也是这样。而且其它像素值都不会对输出产生任影响,这就是稀疏连接的概念。这个和普通神经网络对比很鲜明,普通神经网络是全连接的,也就是说下一层中的一个值会和上一层所有的值发生连接。











3.等变表示指的是,图像中某一元素/成分的移动,在上层神经元中也表现为一定的移动。这是由参数共享直接带来的,因为移动过程中卷积核的参数不变。这种等变表示使得图像的平移不会对分类预测结果产生太大的影响,使得学习算法能够对相同内容不同位置的图像较为准确的识别。

what


1.卷积的概念,知乎上一个比较通俗的解释是加权叠加,一个更通俗的理解是以一个固定的速率殴打某人,那他承受的伤害就是一个叠加的过程。稍微数学一点的理解可以看如何通俗易懂地解释卷积?。实际上加权叠加的理解对于CNN就基本够用了。

2.卷积核,就是指过滤矩阵,比如下图就是一个用于检测图片边缘的卷积核,卷积核的作用在于特征提取因为做了加权求和所以突出了一些重点。










3.Padding,因为卷积操作会让图像变小丢失一些信息,所以需要在原始图像周围填充一圈默认值。

4.卷积步长,是指卷积操作一次移动几个格子,这个比较直观。

5.池化层,用来缩减模型的大小,提高计算速度,同时提高所提取特征的鲁棒性,也比较直观,比如下图是最大池化的例子。







6.Dropout,是正则化的手段的一种为了提高模型的泛化能力,直观的理解就是以一定的概率关闭某些神经元,如下图。








举个小栗子吧,假如有两个特征,有一只耳朵,有尾巴,假如这两个特征同时出现的时候,能判定它是一只猫,当只有有尾巴这个特征的时候,也能判定它是一只猫,但只有有一只耳朵这个特征的时候,就不能判定它是一只猫,那神经网络就知道有一只耳朵这个特征在分类是否是猫这个问题时,是个冗余信息,那分类的时候就不用它了嘛(来自(CNN)卷积神经网络(四)dropout)。

7.全部放一起的一段代码表示,
stride = 1  # output is 28x28
Y1 = tf.nn.relu(tf.nn.conv2d(X, W1, strides=[1, stride, stride, 1], padding='SAME') + B1)
stride = 2  # output is 14x14
Y2 = tf.nn.relu(tf.nn.conv2d(Y1, W2, strides=[1, stride, stride, 1], padding='SAME') + B2)
stride = 2  # output is 7x7
Y3 = tf.nn.relu(tf.nn.conv2d(Y2, W3, strides=[1, stride, stride, 1], padding='SAME') + B3)

# reshape the output from the third convolution for the fully connected layer
YY = tf.reshape(Y3, shape=[-1, 7 * 7 * M])

Y4 = tf.nn.relu(tf.matmul(YY, W4) + B4)
Ylogits = tf.matmul(Y4, W5) + B5
Y = tf.nn.softmax(Ylogits)



循环神经网络(RNN,LSTM)


why


RNN适合处理序列类型的数据,比如,当我们在理解一句话意思时,孤立的理解这句话的每个词是不够的,我们需要处理这些词连接起来的整个序列; 当我们处理视频的时候,我们也不能只单独的去分析每一帧,而要分析这些帧连接起来的整个序列。

CNN不太适合处理很长的序列问题,因为CNN擅长的是捕捉局部的相邻的特征,距离较远的关联信息CNN不太适合处理。在循环网络中使用的参数共享的前提是相同参数可用于不同时间步的假设,这个关系应该不随时间去改变。

RNN当序列较长的时候有梯度消失的问题,所以就出现了LSTM。

what


1.RNN可以用下面这张图来表示,









RNN最关键的是在模型中加入了状态S然后状态可以随着时间传播下来所以有了记忆功能,整体的定义如下









2.梯度爆炸和梯度消失(详细可看LSTM原理分析)





上面的式子是误差传递的过程,可以看到后面的连乘项对一个结构反复相乘,如果这个结构的值大于1就是梯度爆炸,反之就会梯度消失。

3.LSTM的解决方案是原始RNN的隐藏层只有一个状态,即h,它对于短期的输入非常敏感。那么,假如我们再增加一个状态,即c,让它来保存长期的状态,那么问题不就解决了么?如下图所示:







按照时间维度展开








加上输入门和遗忘门来控制c的内容就有了这张经典图











详细的分析可看深度学习笔记(八)LSTM长短期记忆网络









2019年2月2日星期六

why-what-how方式的机器学习总结之二

EM算法


主要还是跟着吴恩达的讲义(笔记),用混合高斯分布来说明一下EM算法。

why


em算法要解决的是模型中存在隐含变量(无法在训练数据中直接观察到)的问题。

what


1.先简单说一下混合高斯分布(MoG),MoG是一种聚类模型,说到聚类模型可能一般会先想到K-means,但如果各个类别的尺寸不同,聚类间有相关关系的时候可能MoG会更合适。直观的看如下图,


















MoG包含多个正态分布,数据属于哪个正态分布可以看成一个隐含变量z。这个z符合多项式分布,




当z给定之后,x服从正态分布即条件概率p(x|z)服从正态分布,可以写出似然函数以及估计结果。












可以看到上面的计算结果里面都包含着z这个隐含变量,所以需要em算法。

2.EM(Expectation-Maximum,简称EM)算法的大致步骤是


  
在E-step中








上面式子算的是z的后验概率,分子是样本xi属于zj的概率,分母是样本xi属于每个zi的概率之和,因为有了参数确定的条件所以分母是个边缘分布而不是等于1。

M-step就是根据之前最大似然的结果把z的概率代入计算即可。这个过程实际上是固定z,然后最大化似然函数L(θ)求解对应的θ。

EM算法能收敛,但可能会收敛到局部最大值,如果函数是凸函数才能保证收敛到全局最大值。


how


EM的推导过程有点长,这里只记录关键过程







这个过程用了几个技巧
(1)分子分母同时增加了Q(z)项
(2)不等号这里用到了Jensen不等式
(3)第一步和最后一步都用到了期望的定义

根据Jensen不等式等号成立的条件有






Q(z)是一个概率分布所以有∑zQi(z(i))=1,这个Q是我们自己添加的项可以这样选择Q





这个就是zi的后验概率,也就是E-step中计算的目标

所以EM算法实际上是在E-step对于当前的参数θ,找到让不等式等号成立的Q分布,在M-step对似然函数下界进行最大似然估计得到新的参数。








这个过程的图形化表示(来自从最大似然到EM算法浅解)











矩阵相关

上大学的时候线性代数学得不好很重要的一个原因是不知道线性代数在干啥,所以这里仔细的分析一下矩阵的why吧。

矩阵是什么?

第一个问题是矩阵是干啥用的?矩阵用来表示线性变换,可以看随记:我们需要怎样的数学教育?





















矩阵表示线性变换有个前置条件“选定一组基”,完整的描述是“矩阵是线性空间中的线性变换的一个描述。在一个线性空间中,只要我们选定一组基,那么对于任何一个线性变换,都能够用一个确定的矩阵来加以描述”。   

基是刻画向量空间的基本工具,n维向量空间中的n个向量如果任意其它向量都能被这n个向量线性表示,那这n个向量就是空间的基,比如最基本的是(1,0,0),(0,1,0),(0,0,1)这样的,但是也有其它的表示法比如(1,1,0),(1,0,1)...这样的。基可以看作线性空间的坐标系。

为了表示一个线性变换T:V-> W,我们选择V的一组基向量v1,...,vn,再选择W的一组基向量w1,...,wm,接着,把T(vk)用wk表示出来,就搞定了!就是要得到表示,




这个式子描述了V的第k个基向量被变换到W中之后的位置。









把每一个T(vk)写成基向量wi的线性组合,所需要的系数就构成了矩阵的第k列。这些是摘录自线性变换的矩阵为什么要强调在这组基下?

行列式

实际上就是线性变换的放大率,比如三维空间一个立方体经过变换以后体积变大或者变小的比率

矩阵乘法

A * B = C 两个线性变换的复合先B后A

对角化矩阵

一个线性变换T对于标准基(或者其他某个基)的矩阵为A;而我们为了更清楚地通过矩阵看出这个线性变换的效果,就把A对角化:



这个过程是先把标准基换成特征向量组成的基,然后乘上常数(对角矩阵),再转换回标准基。
所以对角化其实就是要用一组比标准基更好的基来描述线性变换,也就是由特征向量组成的基。

矩阵相似

定义是存在可逆矩阵X满足则我们说A和B是相似的。

矩阵相似就是同一个线性变换的不同的矩阵标识形式,之所以会有这个不同是因为两个线性变换面对的向量的基不一样。公式中X的含义是两个基之间存在线性关系能做线性变换。

逆矩阵

逆的含义是两个基下面的坐标间存在线性变换关系,也就是能变过去也能变回来。a,b是A和B的基,有b=aP,对应坐标的关系是x2=P^-1*x1。

特征值特征向量

定义,向量x与变换A满足Ax=λx,则称向量x是变换A的一个特征向量,λ是相应的特征值。

说明一个事实,A变换只是拉伸了向量x,并没有改变x的方向,所有具有相同特征值λ的特征向量加上零向量组成一个向量空间称作这个线性变换A的特征空间。

特征值是λ可以理解成拉伸程度,一个对角矩阵的特征值就是对角线上那些值,相似矩阵的特征值是相同的但特征向量一般不相同我感觉是因为基底不同。还有一层理解是因为特征向量在其它维度上是0,所以可以忽略A在其它维度上的变换所以才能等同于乘以一个常数。

特征值分解

定义,令 A 是一个 N×N 的方阵,且有 N 个线性无关的特征向量。这样, A 可以被分解为

特征值分解的意义是寻找对该线性变换更好的表示。计算方法对于较简单的矩阵可以让|λE-A|=0然后解方程组计算,详见矩阵特征值和特征向量求解——特征值分解。对于复杂的矩阵可以用QR分解,具体见QR分解求矩阵全部特征值

SVD分解(奇异值分解)

定义,假设A是一个N * M的矩阵,将A分解成,得到的U是一个N * N的方阵(里面的向量是正交的,U里面的向量称为左奇异向量),Σ是一个N * M的矩阵(除了对角线的元素都是0,对角线上的元素称为奇异值),V’(V的转置)是一个N * N的矩阵,里面的向量也是正交的,V里面的向量称为右奇异向量),从图片来反映几个相乘的矩阵的大小可得下面的图片,来自SVD分解技术详解









奇异值和特征值的关系,矩阵A乘以A的转置矩阵会得到一个方阵,这个方阵的特征值满足

这里的v就是右奇异向量,还可以得到










这里的σ就是上面说的奇异值,u就是上面说的左奇异向量。SVD的计算也可以通过这个关系转换成特征值分解的计算。

SVD可以用于PCA降维,这是因为在矩阵Σ中也是从大到小排列,而且σ的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了,所以我们只需要保留前10%或者更少的信息就可以近似表示全部信息了。

直观理解SVD的过程,A矩阵代表的变换是从\sigma 代表的空间旋转,缩放,投影到\mu 代表的空间,奇异值分解把这三种混在一起的效果给分解出来了。详见矩阵的奇异值与特征值有什么相似之处与区别之处?


NMF分解(非负矩阵分解)


矩阵分解还有另一种做法就是NMF分解,V≈W(权重矩阵)*H(特征矩阵) ,要求V,W,H都是非负的。

NMF可以用损失函数+梯度下降的方式来求近似解,加上正则化项如下式





NMF和SVD都可以用在推荐系统,文档主题模型等等场景。区别是NMF比SVD要快一些,而且简单好理解一些。详细可参考文本主题模型之非负矩阵分解(NMF)

最后感觉如果能多从实际意义思考一下矩阵,大学线性代数就不会学的那么差了,像线性代数的本质这样的文章就给了我很多启发。


降维


why


1.减少计算量。
2.便于数据可视化处理。
3.本质上说是提取真正有效的信息,过滤掉无用的信息。

what


降维的方法主要有因子分析模型,主成分分析(PCA),独立成分分析(ICA),自编码器等等。

how


1.因子分析模型

因子分析的基本目的就是用少数几个因子去描述许多指标或因素之间的联系,即将相关比较密切的几个变量归在同一类中,每一类变量就成为一个因子,以较少的几个因子反映原资料的大部分信息。

模型定义











模型假设训练数据是按下面的过程生成的,

(1)在低维空间生成m个隐变量,这m个隐变量符合多元高斯分布。



(2)用变换矩阵λ将隐含变量z由低维映射到高维。










(3)加上偏移量μ进行平移。











(4)加上随机扰动即可得到最终的训练数据。











举个因子分析模型降维的实例,消费者可以通过一个24个指标构成的评价体系来评价百货商场24个方面的优劣。但消费者主要关心的是商场的环境,服务和价格,可以用因子分析法在24个维度的数据中找出环境,服务,价格的三个潜在因子,达到降维的作用。

计算过程的关键点
(1)首先要得到x的边际分布




(2)得到训练数据对应的似然函数









(3)这个似然函数很难求解,由于存在隐变量z,所以可以用em法求解。具体细节可参考
斯坦福ML公开课笔记13B-因子分析模型及其EM求解以及因子分析


2.主成分分析(PCA)

用数学的方式描述是 其中z为低维矩阵,x为高维矩阵。

PCA解决的问题的一个实例是假设x代表一辆车的属性可能有最高时速,每公里耗油量等等,如果x包含了以公里为单位的最大时速和以英里为单位的最大时速,那这两个速度肯定是成比例的,x包含的信息量需要减去一个维度。PCA就是要解决去掉这样多余维度的问题。

还有一个case是飞行员的驾驶技能和对驾驶的兴趣,这两者显然是相关的,这两个属性按坐标表示如下图,















可见u1表示了两个属性的相关性,我们称之为主方向,u2则是主方向之外的噪声。

在计算寻找主方向之前,首先要对数据做预处理包括平均值归零和方差归一。

寻找主方向的过程

(1)先考虑最简化的二维空间,u是从原点出发的单位向量,每个数据点都在u方向的直线有一个投影点,寻找主方向就是想让这些投影点的方差最大化。这是因为方差最大化相当于保留了最多的信息。

(2)之所以要从原点出发是为了简化计算,这也是之前要做预处理的原因。

(3)实际情况应该是高维空间而且降维后的空间也是高维的。所以我们的做法是先找到一个主方向,再把数据集往这个主方向上投影消除掉这个主方向的影响,然后再找下一个主方向。

下面的图中,中间图投影点的方差最大。








数学表达

方差最大化可以形式化为下式最大化,





这是一个有约束 的优化问题,用拉格朗日乘子法可以得到该问题的解就是矩阵 的特征向量,最后就是一个矩阵求特征向量的问题了。详见斯坦福ML公开课笔记14——主成分分析


这个问题还可以更简化,直接对训练数据的n*m的矩阵做奇异值分解,然后留下奇异值最大的r列,最终效果就是PCA想要的。如下图A矩阵的定义






因子分析法和主成分分析的区别是主成分分析仅仅做的是变量变换,而因子分析法是用假想的隐变量和随机影响变量的线性组合来表示原变量,是一种依靠概率密度的方法。主成分分析注重解释各个变量的总方差而因子分析法注重各个变量间的协方差。

还有个和PCA基本等价的概念叫流形学习,比如一个圆边界上所有的点本质上是一维的,流形学习就是学的这个映射。


3.独立成分分析(ICA)

要解决的问题是,鸡尾酒会问题:n 个人在一个 party 上同时说话,n 个麦克风放置在房间的不同位置,因为每个麦克风跟每个人的距离都不一样,所以它们记录的说话者重叠的声音也不一样。根据麦克风记录的声音,如何分离出 n 个说话者的声音呢?

问题形式化一下就是我们有x=As,x是n个麦克风采样到的声音,s是每个发言者独立发出的声音。设 W是A的逆,为一个分离矩阵,我们的目标就是找到 W,这样就能根据麦克风记录的声音 x(i),来恢复声源 s(i)=Wx(i)。

如果A和s都是不确定的,我们无法得到精确解,因为一种情况A放大两倍s就缩小两倍,另一种情况s符合高斯分布也不行这种情况把A乘一个正交阵x变成x'结果还是满足的。

所以实际求解的时候给p(s)指定了一个密度,si的cdf需要从0到1单调递增,又不能是高斯函数所以就选择sigmoid有,
求导后 

求p(x)





求似然函数






对W求导(注意这是矩阵微积分)之后得到最后的梯度下降规则。具体细节见斯坦福ML公开课笔记15—隐含语义索引、奇异值分解、独立成分分析


4.自编码器









如上图编码器对原始数据通过函数映射成一种中间标识,然后再通过解码器映射回原始数据空间,然后比较原始数据和解码的数据作为损失函数。自编码器的特点

(1)编码器和解码器一般是通过神经网络实现的

(2)自编码器是有损的

(3)自动编码器是从数据样本中自动学习的,这意味着很容易对指定类的输入训练出一种特定的编码器,而不需要做任何新工作

(4)目前自编码器的应用主要有两个方面,第一是数据去噪,第二是为进行可视化而降维。配合适当的维度和稀疏约束,自编码器可以学习到比PCA等技术更有意思的数据投影

(5)自编码器使用的神经网络可以是深度网络从而可以达到任意精度的编码

(6)自编码器有很多种,比如稀疏自编码器,去噪自编码器等等,主要的区别在于使用了不同的损失函数和正则化项

关于自编码器更多内容可以参考深度学习之自编码器AutoEncoder


5.稀疏编码

有个和降维比较类似的概念叫稀疏编码,稀疏编码的概念来自于神经生物学。生物学家提出,哺乳类动物在长期的进化中,生成了能够快速,准确,低代价地表示自然图像的视觉神经方面的能力。我们直观地可以想象,我们的眼睛每看到的一副画面都是上亿像素的,而每一副图像我们都只用很少的代价重建与存储。我们把它叫做稀疏编码,即Sparse Coding。

和pca比较类似,都是线性变换把原始数据表达成一组特征,但是pca是降维,稀疏编码的基向量的个数可能比输入的维度大,但是有稀疏性即只有少数系数远大于零学习的过程可以是拿到一副图像,然后得到一个基向量的稀疏表示。

更多详细内容可参考深度学习浅层理解(四)-- 稀疏编码


最大熵模型


why


最大熵模型是一个分类模型解决的是多分类问题。在自然语言处理里面经常见到,比如。










上面的英汉翻译中如果没有任何限制,take的七种翻译概率是相等的。但如果引入某些限制或者上下文信息,比如take后面接着一个bus那翻译成乘坐的概率就非常大。最大熵模型就是运用最大熵原理来解决这种带这某些条件或者限制的模型,这种条件或者限制称作特征函数,是个二值函数。参考最大熵模型(MaxEnt):万法归宗(上)






what


1.最大熵原理

在已知部分知识的前提下,关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断。主要体现在(1)满足已知信息(约束条件)  (2)不做任何假设(概率均等)

2.条件熵

定义如下,详细可看通俗理解条件熵,和普通的信息熵的区别主要是在x维度又做了一次划分。







3.最大熵模型









可以看到最大熵模型是个判别模型,唯一的约束就是x,y有某种关联f(x,y),这个f(x,y)可以理解成x和y的亲密度的一种形式,参考如何理解最大熵模型里面的特征?


how


最大熵模型的推导详情可参考最大熵模型(MaxEnt):万法归宗(下) 这里记录要点。

1.因为我们要得到的是p(y|x)条件分布,所以要利用最大熵原理我们需要使用条件熵。

2.利用最大熵模型我们需要优化的问题可以表示成,








把正负号反一下转换成求最小值的形式

3.由拉格朗日乘子法和对偶原理我们要求解的问题变成




要注意这里的P是个变量,是我们要求解的目标

4.对偶问题的内层极小值问题可以表示为





求L(P,w)对P(y|x)的偏导数,并让导数等于0,经过一系列代数变换就可以得到我们的最大熵模型。


5.对偶问题的外层是




用拉格朗日乘子法最初的公式表达是



P(Y|X)的对数似然函数表示为




经过一些列代数表换最后可以得到




所以有结论最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计

6.有了模型如何求解呢?《统计学习方法》里面介绍了改进迭代尺度法(IIS)以及拟牛顿法。

(1)IIS基本思路还是不断更新参数让似然函数尽量大,关键是每次更新参数的尺度是通过一个方程由当前参数计算出来,细节不列了。

(2)拟牛顿法的基本思路是找一个矩阵b代替hassian矩阵,b通过b0+δ(b)的方式迭代得到,迭代公式的细节也不列了。

隐马尔科夫模型


why


隐马尔科夫模型要做的事情是“根据可观察状态的序列找到一个最可能的隐藏状态序列”,拿中文分词做例子。

中文分词,就是给一个汉语句子作为输入,以“BEMS”组成的序列串作为输出,然后再进行切词,进而得到输入句子的划分。其中,B代表该字是词语中的起始字,M代表是词语中的中间字,E代表是词语中的结束字,S则代表是单字成词。

比如下面的句子,

小明硕士毕业于中国科学院计算所

得到BEMS组成的序列为

BEBEBMEBEBMEBES

因为句尾只可能是E或者S,所以得到切词方式为

BE/BE/BME/BE/BME/BE/S

进而得到的分词结果是

小明/硕士/毕业于/中国/科学院/计算/所

这就是隐马尔科夫模型(HMM)要解决的典型的问题,我们想得到的是每个字的位置属性,但是看到的只是字本身,每个字的状态还和它之前的字的状态有关,所以我们需要根据可观察状态的序列找到一个最可能的隐藏状态序列。更详细的可以参考一个隐马尔科夫模型的应用实例:中文分词

what


1.HMM有两个重要假设,有限历史性假设和独立输出假设。如下面这张图。








(1)拿自然语言识别来看,一个词发生的概率应该是之前所有词发生情况下的条件概率但是马尔科夫链做了简化可以只算这个词前面那个词发生情况下的条件概率。状态转移的概率只依赖前一个状态。





(2)独立输出假设是说第 i 时刻的接收信号 oi 只由发送信号 si 决定。






2.HMM 有5个要素。

观测序列-O:小明硕士毕业于中国科学院计算所  

状态序列-S:BEBEBMEBEBMEBES  

初始状态概率向量-π:句子的第一个字属于{B,E,M,S}这四种状态的概率









状态转移概率矩阵-A:如果前一个字位置是B,那么后一个字位置为BEMS的概率各是多少








观测概率矩阵-B:在状态B的条件下,观察值为耀的概率,取对数后是-10.460








3.HMM需要解决的问题有3类

(1)似然度(概率计算)问题:参数(O,π,A,B)已知的情况下,求(π,A,B)下观测序列O出现的概率。(Forward-backward算法)。这里O已知是指我们已经得到了一个观测序列O={o1,o2...ot}。

(2)解码(预测)问题:参数(O,π,A,B)已知的情况下,求解状态值序列S。(viterbi算法)

(3)学习问题:参数(O)已知的情况下,求解(π,A,B)。(Baum-Welch算法)

4.需要注意HMM是个生成模型,对状态序列分布本身p(x)和给定状态之后的观测值p(y|x)都进行了建模。


how


1.概率计算问题,直观的做法是列举所有可能出现长度为T的状态序列,然后计算对应的概率再求和得到观察序列的概率,但是复杂度是指数级所以不可行。

前向算法是个动态规划算法,关键是建立递推关系






后向算法类似,可以参考《统计学习方法》

2.解码问题是要求t时刻最可能出现的状态i,是个最优路径问题,所以也可以用动态规划算法(viterbi算法)求解,关键是建立递推关系






3.HMM的训练可以用最大似然来做,需要训练数据由大量长度相同的观测序列和状态序列组成{(O1,I1),(O2,I2),...(Os,Is)}。但这种方法人工标注成本太高,所以一般会用非监督学习的Baum-Welch算法来搞。

当训练数据只有观测序列{O1,O2...Os}的时候我们可以把状态序列看做隐变量,那隐马尔科夫模型就变成了含隐变量的模型




这样就可以用EM算法来求解了,细节参考《统计学习方法》



条件随机场


why


首先条件随机场(CRF)的应用和HMM类似,也是解决自然语言识别中的各种词性标注,分词这些问题。但是HMM的两个假设过强,使得当前位置的词(观测)只可以利用当前的状态(词性),当前位置的状态又只能利用上一位置的状态,所以模型必要会丢掉不少信息。而CRF 的特征函数中,输入包含 (yi-1,yi,x,i) ,对于当前位置 i 来说可以利用完整的 x 信息,所以CRF可以表现得更优秀。NLP —— 图模型(二)条件随机场(Conditional random field,CRF)这篇文章里面有更详细的比较。

条件随机场这个名字听着很玄,来解读一下。

(1)随机场是由若干个位置组成的整体,当给每一个位置中按照某种分布随机赋予一个值之后,其全体就叫做随机场。还是举词性标注的例子:假如我们有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在我们已知的词性集合(名词,动词...)中去选择。当我们为每个词选择完词性后,这就形成了一个随机场。

(2)马尔科夫随机场是随机场的特例,它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关,和与其不相邻的位置的赋值无关。继续举十个词的句子词性标注的例子: 如果我们假设所有词的词性只和它相邻的词的词性有关时,这个随机场就特化成一个马尔科夫随机场。比如第三个词的词性除了与自己本身的位置有关外,只与第二个词和第四个词的词性有关。

(3)CRF是马尔科夫随机场的特例,它假设马尔科夫随机场中只有X和Y两种变量,X一般是给定的,而Y一般是在给定X的条件下我们的输出。这样马尔科夫随机场就特化成了条件随机场。在我们十个词的句子词性标注的例子中,X是词,Y是词性。因此,如果我们假设它是一个马尔科夫随机场,那么它也就是一个CRF。设X与Y是随机变量,P(Y|X)是给定X时Y的条件概率分布,若随机变量Y构成的是一个马尔科夫随机场,则称条件概率分布P(Y|X)是条件随机场。

更详细的解读请看条件随机场CRF(一)从随机场到线性链条件随机场

what


1.演变

CRF是马尔科夫随机场的特例,马尔科夫随机场是概率无向图模型,其定义为,设有联合概率分布 P(V) 由无向图 G=(V, E) 表示,图 G 中的节点表示随机变量,边表示随机变量间的依赖关系。如果联合概率分布 P(V) 满足成对、局部或全局马尔可夫性,就称此联合概率分布为概率无向图模型或马尔可夫随机场。

成对,局部,全局马尔科夫性理解比较简单,主要就独立性,整体的联合分布能拆解成部分概率的乘积,详见NLP —— 图模型(二)条件随机场(Conditional random field,CRF)

有了马尔科夫性就可以做无向图的因子分解,给定无向图 G ,其最大团为 C ,那么联合概率分布 P(Y) 可以写作图中所有最大团 C 上的势函数(potential function) ψC(YC) 的乘积形式:












加入条件概率分布模型 P(Y|X)的马尔科夫随机场就演变成CRF,我们关注的是线性链条件随机场(linear chain conditional CRF),是由输入序列来预测输出序列的判别式模型。









下面这张图是几个常见模型之间的演变关系,概率图模型体系:HMM、MEMM、CRF这篇文章讲得很精彩





2.定义


条件随机场正式的定义是,如果随机变量 Y 构成一个由无向图 G=(V, E) 表示的马尔可夫随机场,对任意节点 v∈V 都成立,即

P(Yv|X,Yw,w≠v)=P(Yv|X,Yw,w∼v)

对任意节点 v 都成立,则称 P(Y|X) 是条件随机场。式中 w≠v 表示 w 是除 v 以外的所有节点,w∼v 表示 w 是与 v 相连接的所有节点。

线性链条件随机场的定义为

P(Yi|X,Y1,...,Yi−1,Yi+1,...,Yn)=P(Yi|X,Yi−1,Yi+1),i=1,...,n

其中当 i 取 1 或 n 时只考虑单边。


3.参数化形式

给定一个线性链条件随机场 P(Y|X) ,当观测序列为 x=x1x2⋯ 时,状态序列为 y=y1y2⋯ 的概率可写为








上面的式子中有两个特征函数,

转移特征 tk(yi−1,yi,x,i) 是定义在边上的特征函数(transition),依赖于当前位置 i 和前一位置 i-1 ;对应的权值为 λk 。
状态特征 sl(yi,x,i) 是定义在节点上的特征函数(state),依赖于当前位置 i ;对应的权值为 μl 。
一般来说,特征函数的取值为 1 或 0 ,当满足规定好的特征条件时取值为 1 ,否则为 0 。
k和l个人理解是超参数,和状态数以及y的取值没有直接关联。

特征函数的实例可以看概率图模型体系:HMM、MEMM、CRF,从特征函数可以看到CRF比HMM强大的地方在于 CRF 的特征函数中,输入包含 (yi−1,yi,x,i) ,对于当前位置 i 来说可以利用完整的 x 信息。

4.简化形式

用统一的形式表达转移函数t和状态函数s,可以得到简化形式






5.矩阵形式







矩阵表达方式和参数化形式等价,矩阵行索引是上一个状态的所有可能取值,矩阵列索引是当前状态的所有可能取值。


how


CRF的计算和HMM一样也是要解决3个问题,概率计算问题,解码问题和学习训练问题。

1.概率计算

使用的是和HMM类似的前向后向算法,定义了前向向量α和后向向量β
          ·





要注意的点一个是α是个非规范化概率和我们要求的p(y|x)差着归一化常量,第二是α是个向量,在标记问题中如果有m种标记,yi就可能有m种取值那αi(x)就是个m维向量。

另外我们还要有归一化因子,对应着α(yi)的m个值的求和。




利用前向向量和后向向量可以得到







2.解码

同样是用维特比算法求解,关键在于建立递推公式





δi(l),表示在位置i标记l各个可能取值(1,2...m)对应的非规范化概率的最大值,局部状态Ψi+1(l)来记录使δi+1(l)达到最大的位置i的标记取值。

3.学习训练

先得到似然函数













然后对w求导,通过梯度下降或者IIS以及拟牛顿法求解。

4.YY一下,crf的条件概率公式虽然和最大熵模型很像,但实际上是通过独立最大团假设的过程推导过来的。两个公式虽然很像,但实际上crf有两层,外层求和是n个状态,内层求和是k个特征函数,所以实际上是不一样的。但是简化的crf概率公式由于是n个状态求和,也可以看做是整体y的状态,这样就只有k个特征公式,这样就可以按最大熵模型的方式去看了。


决策树和随机森林


相对简单一些就不用why-what-how来分析了。

1.决策树是一个分类模型,其优点是分类路径很清晰。
2.决策树构建,用每一列的每一种取值可能来对集合做一个划分,然后比较所有划分方式的熵减少。取到熵减少最多的把集合划成两拨,然后递归这个过程。
3.随机森林,进行决策树划分的时候不是取所有属性的最优而是随机取k个属性然后在这k个属性中取最优,重复m次形成m颗树,然后m颗树加权做出决策。
4.随机森林是一种bagging的做法,也就是用多次采样的数据训练多个不同的算法然后叠加生成结论。这种是可以并行的。

Boost方法


why


Boosting算法是将“弱学习算法“提升为“强学习算法”的过程,主要思想是“三个臭皮匠顶个诸葛亮”。一般来说,找到弱学习算法要相对容易一些,然后通过反复学习得到一系列弱分类器,组合这些弱分类器得到一个强分类器。更详细的参考AdaBoost原理详解

what


常见的boost方法有AdaBoost,GBDT,XGBoost等等。

how


1.AdaBoost详细见AdaBoost原理详解
(1)基本原理是用比较简单的分类算法比如逻辑回归或者单层决策树去组合成比较复杂的分类算法,组合的方式就是用加权求和。
(2)训练的过程是首先给每个样本一个默认权值,然后用最简单的分类器去得到一个最佳分类,最佳分类的损失函数就是分错类的样本的权值和。
(3)分类器的权值是损失值的一个log函数,这个log函数很容易用损失函数求导获得,然后更新每个训练样本的权值,训练样本的权值是个指数函数。
(4)每轮迭代用最后的加权函数做分类,如果效果足够好就结束。

(1)GBDT是前向分布算法用多颗树组成最终的算法








(2)第m次迭代我们需要优化的损失函数如下





(3)如果我们用平方误差作为损失函数,就可以得到对残差r进行拟合的形式






(4)对于多数损失函数不太适合残差的方式,可以用损失函数的负梯度来拟合。第m次迭代时,计算当前要拟合的残差rmi。






以rmi为输出值,对rmi拟合一个回归树(此时只是确定了树的结构,但是还未确定叶子节点中的输出值),然后通过最小化当前的损失函数,并求得每个叶子节点中的输出值cmj,j表示第j个叶子节点





更新当前的模型fm(x)为:





(5)最终的模型,其中M表示基学习器的个数,J表示叶子节点的个数








3.XGBoost详细见xgboost的原理没你想像的那么难通俗、有逻辑的写一篇说下Xgboost的原理,供讨论参考,下面简单列一下和GBDT的区别。
(1)将树模型的复杂度加入到正则项中,来避免过拟合,因此泛化性能会由于GBDT。
(2)损失函数是用泰勒展开式展开的,同时用到了一阶导和二阶导,可以加快优化速度。
(3)和GBDT只支持CART作为基分类器之外,还支持线性分类器,在使用线性分类器的时候可以使用L1,L2正则化。
(4)引进了特征子采样,像RandomForest那样,这种方法既能降低过拟合,还能减少计算
(5)在寻找最佳分割点时,考虑到传统的贪心算法效率较低,实现了一种近似贪心算法,用来加速和减小内存消耗,除此之外还考虑了稀疏数据集和缺失值的处理,对于特征的值有缺失的样本,XGBoost依然能自动找到其要分裂的方向
(6)XGBoost支持并行处理,XGBoost的并行不是在模型上的并行,而是在特征上的并行,将特征列排序后以block的形式存储在内存中,在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能,其次在进行节点分裂时,计算每个特征的增益,最终选择增益最大的那个特征去做分割,那么各个特征的增益计算就可以开多线程进行。