数据挖掘机器学习中的一些数学方法教材.docx
- 文档编号:13884996
- 上传时间:2023-06-18
- 格式:DOCX
- 页数:59
- 大小:1.80MB
数据挖掘机器学习中的一些数学方法教材.docx
《数据挖掘机器学习中的一些数学方法教材.docx》由会员分享,可在线阅读,更多相关《数据挖掘机器学习中的一些数学方法教材.docx(59页珍藏版)》请在冰点文库上搜索。
数据挖掘机器学习中的一些数学方法教材
FROM:
机器学习中的数学
(1)-回归(regression)、梯度下降(gradientdescent)
版权声明:
本文由LeftNotEasy所有,发布于。
如果转载,请注明出处,在未经作者同意下将本文用于商业用途,将追究其法律责任。
前言:
上次写过一篇关于贝叶斯概率论的数学,最近时间比较紧,coding的任务比较重,不过还是抽空看了一些机器学习的书和视频,其中很推荐两个:
一个是stanford的machinelearning公开课,在verycd可下载,可惜没有翻译。
不过还是可以看。
另外一个是prml-patternrecognitionandmachinelearning,Bishop的一部反响不错的书,而且是2008年的,算是比较新的一本书了。
前几天还准备写一个分布式计算的系列,只写了个开头,又换到写这个系列了。
以后看哪边的心得更多,就写哪一个系列吧。
最近干的事情比较杂,有跟机器学习相关的,有跟数学相关的,也有跟分布式相关的。
这个系列主要想能够用数学去描述机器学习,想要学好机器学习,首先得去理解其中的数学意义,不一定要到能够轻松自如的推导中间的公式,不过至少得认识这些式子吧,不然看一些相关的论文可就看不懂了,这个系列主要将会着重于去机器学习的数学描述这个部分,将会覆盖但不一定局限于回归、聚类、分类等算法。
回归与梯度下降:
回归在数学上来说是给定一个点集,能够用一条曲线去拟合之,如果这个曲线是一条直线,那就被称为线性回归,如果曲线是一条二次曲线,就被称为二次回归,回归还有很多的变种,如locallyweighted回归,logistic回归,等等,这个将在后面去讲。
用一个很简单的例子来说明回归,这个例子来自很多的地方,也在很多的opensource的软件中看到,比如说weka。
大概就是,做一个房屋价值的评估系统,一个房屋的价值来自很多地方,比如说面积、房间的数量(几室几厅)、地段、朝向等等,这些影响房屋价值的变量被称为特征(feature),feature在机器学习中是一个很重要的概念,有很多的论文专门探讨这个东西。
在此处,为了简单,假设我们的房屋就是一个变量影响的,就是房屋的面积。
假设有一个房屋销售的数据如下:
面积(m^2) 销售价钱(万元)
123 250
150 320
87 160
102 220
… …
这个表类似于帝都5环左右的房屋价钱,我们可以做出一个图,x轴是房屋的面积。
y轴是房屋的售价,如下:
如果来了一个新的面积,假设在销售价钱的记录中没有的,我们怎么办呢?
我们可以用一条曲线去尽量准的拟合这些数据,然后如果有新的输入过来,我们可以在将曲线上这个点对应的值返回。
如果用一条直线去拟合,可能是下面的样子:
绿色的点就是我们想要预测的点。
首先给出一些概念和常用的符号,在不同的机器学习书籍中可能有一定的差别。
房屋销售记录表-训练集(trainingset)或者训练数据(trainingdata),是我们流程中的输入数据,一般称为x
房屋销售价钱-输出数据,一般称为y
拟合的函数(或者称为假设或者模型),一般写做y=h(x)
训练数据的条目数(#trainingset),一条训练数据是由一对输入数据和输出数据组成的
输入数据的维度(特征的个数,#features),n
下面是一个典型的机器学习的过程,首先给出一个输入数据,我们的算法会通过一系列的过程得到一个估计的函数,这个函数有能力对没有见过的新数据给出一个新的估计,也被称为构建一个模型。
就如同上面的线性回归函数。
我们用X1,X2..Xn去描述feature里面的分量,比如x1=房间的面积,x2=房间的朝向,等等,我们可以做出一个估计函数:
θ在这儿称为参数,在这儿的意思是调整feature中每个分量的影响力,就是到底是房屋的面积更重要还是房屋的地段更重要。
为了如果我们令X0=1,就可以用向量的方式来表示了:
我们程序也需要一个机制去评估我们θ是否比较好,所以说需要对我们做出的h函数进行评估,一般这个函数称为损失函数(lossfunction)或者错误函数(errorfunction),描述h函数不好的程度,在下面,我们称这个函数为J函数
在这儿我们可以做出下面的一个错误函数:
这个错误估计函数是去对x(i)的估计值与真实值y(i)差的平方和作为错误估计函数,前面乘上的1/2是为了在求导的时候,这个系数就不见了。
如何调整θ以使得J(θ)取得最小值有很多方法,其中有最小二乘法(minsquare),是一种完全是数学描述的方法,在stanford机器学习开放课最后的部分会推导最小二乘法的公式的来源,这个来很多的机器学习和数学书上都可以找到,这里就不提最小二乘法,而谈谈梯度下降法。
梯度下降法是按下面的流程进行的:
1)首先对θ赋值,这个值可以是随机的,也可以让θ是一个全零的向量。
2)改变θ的值,使得J(θ)按梯度下降的方向进行减少。
为了更清楚,给出下面的图:
这是一个表示参数θ与误差函数J(θ)的关系图,红色的部分是表示J(θ)有着比较高的取值,我们需要的是,能够让J(θ)的值尽量的低。
也就是深蓝色的部分。
θ0,θ1表示θ向量的两个维度。
在上面提到梯度下降法的第一步是给θ给一个初值,假设随机给的初值是在图上的十字点。
然后我们将θ按照梯度下降的方向进行调整,就会使得J(θ)往更低的方向进行变化,如图所示,算法的结束将是在θ下降到无法继续下降为止。
当然,可能梯度下降的最终点并非是全局最小点,可能是一个局部最小点,可能是下面的情况:
上面这张图就是描述的一个局部最小点,这是我们重新选择了一个初始点得到的,看来我们这个算法将会在很大的程度上被初始点的选择影响而陷入局部最小点
下面我将用一个例子描述一下梯度减少的过程,对于我们的函数J(θ)求偏导J:
(求导的过程如果不明白,可以温习一下微积分)
下面是更新的过程,也就是θi会向着梯度最小的方向进行减少。
θi表示更新之前的值,-后面的部分表示按梯度方向减少的量,α表示步长,也就是每次按照梯度减少的方向变化多少。
一个很重要的地方值得注意的是,梯度是有方向的,对于一个向量θ,每一维分量θi都可以求出一个梯度的方向,我们就可以找到一个整体的方向,在变化的时候,我们就朝着下降最多的方向进行变化就可以达到一个最小点,不管它是局部的还是全局的。
用更简单的数学语言进行描述步骤2)是这样的:
倒三角形表示梯度,按这种方式来表示,θi就不见了,看看用好向量和矩阵,真的会大大的简化数学的描述啊。
总结与预告:
本文中的内容主要取自stanford的课程第二集,希望我把意思表达清楚了:
)本系列的下一篇文章也将会取自stanford课程的第三集,下一次将会深入的讲讲回归、logistic回归、和Newton法,不过本系列并不希望做成stanford课程的笔记版,再往后面就不一定完全与stanford课程保持一致了。
机器学习中的数学
(2)-线性回归,偏差、方差权衡
版权声明:
本文由LeftNotEasy所有,发布于。
如果转载,请注明出处,在未经作者同意下将本文用于商业用途,将追究其法律责任。
如果有问题,请联系作者wheeleast@
前言:
距离上次发文章,也快有半个月的时间了,这半个月的时间里又在学习机器学习的道路上摸索着前进,积累了一点心得,以后会慢慢的写写这些心得。
写文章是促进自己对知识认识的一个好方法,看书的时候往往不是非常细,所以有些公式、知识点什么的就一带而过,里面的一些具体意义就不容易理解了。
而写文章,特别是写科普性的文章,需要对里面的具体意义弄明白,甚至还要能举出更生动的例子,这是一个挑战。
为了写文章,往往需要把之前自己认为看明白的内容重新理解一下。
机器学习可不是一个完全的技术性的东西,之前和部门老大在outing的时候一直在聊这个问题,机器学习绝对不是一个一个孤立的算法堆砌起来的,想要像看《算法导论》这样看机器学习是个不可取的方法,机器学习里面有几个东西一直贯穿全书,比如说数据的分布、最大似然(以及求极值的几个方法,不过这个比较数学了),偏差、方差的权衡,还有特征选择,模型选择,混合模型等等知识,这些知识像砖头、水泥一样构成了机器学习里面的一个个的算法。
想要真正学好这些算法,一定要静下心来将这些基础知识弄清楚,才能够真正理解、实现好各种机器学习算法。
今天的主题是线性回归,也会提一下偏差、方差的均衡这个主题。
线性回归定义:
在上一个主题中,也是一个与回归相关的,不过上一节更侧重于梯度这个概念,这一节更侧重于回归本身与偏差和方差的概念。
回归最简单的定义是,给出一个点集D,用一个函数去拟合这个点集,并且使得点集与拟合函数间的误差最小。
上图所示,给出一个点集(x,y),需要用一个函数去拟合这个点集,蓝色的点是点集中的点,而红色的曲线是函数的曲线,第一张图是一个最简单的模型,对应的函数为y=f(x)=ax+b,这个就是一个线性函数,
第二张图是二次曲线,对应的函数是y=f(x)=ax^2+b。
第三张图我也不知道是什么函数,瞎画的。
第四张图可以认为是一个N次曲线,N=M-1,M是点集中点的个数,有一个定理是,对于给定的M个点,我们可以用一个M-1次的函数去完美的经过这个点集。
真正的线性回归,不仅会考虑使得曲线与给定点集的拟合程度最好,还会考虑模型最简单,这个话题我们将在本章后面的偏差、方差的权衡中深入的说,另外这个话题还可以参考我之前的一篇文章:
贝叶斯、概率分布与机器学习,里面对模型复杂度的问题也进行了一些讨论。
线性回归(linearregression),并非是指的线性函数,也就是
x0,x1…表示一个点不同的维度,比如说上一节中提到的,房子的价钱是由包括面积、房间的个数、房屋的朝向等等因素去决定的。
而是用广义的线性函数:
wj是系数,w就是这个系数组成的向量,它影响着不同维度的Φj(x)在回归函数中的影响度,比如说对于房屋的售价来说,房间朝向的w一定比房间面积的w更小。
Φ(x)是可以换成不同的函数,不一定要求Φ(x)=x,这样的模型我们认为是广义线性模型。
最小二乘法与最大似然:
这个话题在此处有一个很详细的讨论,我这里主要谈谈这个问题的理解。
最小二乘法是线性回归中一个最简单的方法,它的推导有一个假设,就是回归函数的估计值与真实值间的误差假设是一个高斯分布。
这个用公式来表示是下面的样子:
,y(x,w)就是给定了w系数向量下的回归函数的估计值,而t就是真实值了,ε表示误差。
我们可以接下来推出下面的式子:
这是一个简单的条件概率表达式,表示在给定了x,w,β的情况下,得到真实值t的概率,由于ε服从高斯分布,则从估计值到真实值间的概率也是高斯分布的,看起来像下面的样子:
贝叶斯、概率分布与机器学习这篇文章中对分布影响结果这个话题讨论比较多,可以回过头去看看,由于最小二乘法有这样一个假设,则会导致,如果我们给出的估计函数y(x,w)与真实值t不是高斯分布的,甚至是一个差距很大的分布,那么算出来的模型一定是不正确的,当给定一个新的点x’想要求出一个估计值y’,与真实值t’可能就非常的远了。
概率分布是一个可爱又可恨的东西,当我们能够准确的预知某些数据的分布时,那我们可以做出一个非常精确的模型去预测它,但是在大多数真实的应用场景中,数据的分布是不可知的,我们也很难去用一个分布、甚至多个分布的混合去表示数据的真实分布,比如说给定了1亿篇网页,希望用一个现有的分布(比如说混合高斯分布)去匹配里面词频的分布,是不可能的。
在这种情况下,我们只能得到词的出现概率,比如p(的)的概率是0.5,也就是一个网页有1/2的概率出现“的”。
如果一个算法,是对里面的分布进行了某些假设,那么可能这个算法在真实的应用中就会表现欠佳。
最小二乘法对于类似的一个复杂问题,就很无力了
偏差、方差的权衡(trade-off):
偏差(bias)和方差(variance)是统计学的概念,刚进公司的时候,看到每个人的嘴里随时蹦出这两个词,觉得很可怕。
首先得明确的,方差是多个模型间的比较,而非对一个模型而言的,对于单独的一个模型,比如说:
这样的一个给定了具体系数的估计函数,是不能说f(x)的方差是多少。
而偏差可以是单个数据集中的,也可以是多个数据集中的,这个得看具体的定义。
方差和偏差一般来说,是从同一个数据集中,用科学的采样方法得到几个不同的子数据集,用这些子数据集得到的模型,就可以谈他们的方差和偏差的情况了。
方差和偏差的变化一般是和模型的复杂程度成正比的,就像本文一开始那四张小图片一样,当我们一味的追求模型精确匹配,则可能会导致同一组数据训练出不同的模型,它们之间的差异非常大。
这就叫做方差,不过他们的偏差就很小了,如下图所示:
上图的蓝色和绿色的点是表示一个数据集中采样得到的不同的子数据集,我们有两个N次的曲线去拟合这些点集,则可以得到两条曲线(蓝色和深绿色),它们的差异就很大,但是他们本是由同一个数据集生成的,这个就是模型复杂造成的方差大。
模型越复杂,偏差就越小,而模型越简单,偏差就越大,方差和偏差是按下面的方式进行变化的:
当方差和偏差加起来最优的点,就是我们最佳的模型复杂度。
用一个很通俗的例子来说,现在咱们国家一味的追求GDP,GDP就像是模型的偏差,国家希望现有的GDP和目标的GDP差异尽量的小,但是其中使用了很多复杂的手段,比如说倒卖土地、强拆等等,这个增加了模型的复杂度,也会使得偏差(居民的收入分配)变大,穷的人越穷(被赶出城市的人与进入城市买不起房的人),富的人越富(倒卖土地的人与卖房子的人)。
其实本来模型不需要这么复杂,能够让居民的收入分配与国家的发展取得一个平衡的模型是最好的模型。
最后还是用数学的语言来描述一下偏差和方差:
E(L)是损失函数,h(x)表示真实值的平均,第一部分是与y(模型的估计函数)有关的,这个部分是由于我们选择不同的估计函数(模型)带来的差异,而第二部分是与y无关的,这个部分可以认为是模型的固有噪声。
对于上面公式的第一部分,我们可以化成下面的形式:
这个部分在PRML的1.5.5推导,前一半是表示偏差,而后一半表示方差,我们可以得出:
损失函数=偏差^2+方差+固有噪音。
下图也来自PRML:
这是一个曲线拟合的问题,对同分布的不同的数据集进行了多次的曲线拟合,左边表示方差,右边表示偏差,绿色是真实值函数。
lnlambda表示模型的复杂程度,这个值越小,表示模型的复杂程度越高,在第一行,大家的复杂度都很低(每个人都很穷)的时候,方差是很小的,但是偏差同样很小(国家也很穷),但是到了最后一幅图,我们可以得到,每个人的复杂程度都很高的情况下,不同的函数就有着天壤之别了(贫富差异大),但是偏差就很小了(国家很富有)。
机器学习中的数学(3)-模型组合(ModelCombining)之Boosting与GradientBoosting
版权声明:
本文由LeftNotEasy发布于,本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@
前言:
本来上一章的结尾提到,准备写写线性分类的问题,文章都已经写得差不多了,但是突然听说最近Team准备做一套分布式的分类器,可能会使用RandomForest来做,下了几篇论文看了看,简单的randomforest还比较容易弄懂,复杂一点的还会与boosting等算法结合(参见iccv09),对于boosting也不甚了解,所以临时抱佛脚的看了看。
说起boosting,强哥之前实现过一套GradientBoostingDecisionTree(GBDT)算法,正好参考一下。
最近看的一些论文中发现了模型组合的好处,比如GBDT或者rf,都是将简单的模型组合起来,效果比单个更复杂的模型好。
组合的方式很多,随机化(比如randomforest),Boosting(比如GBDT)都是其中典型的方法,今天主要谈谈GradientBoosting方法(这个与传统的Boosting还有一些不同)的一些数学基础,有了这个数学基础,上面的应用可以看Freidman的GradientBoostingMachine。
本文要求读者学过基本的大学数学,另外对分类、回归等基本的机器学习概念了解。
本文主要参考资料是prml与GradientBoostingMachine。
Boosting方法:
Boosting这其实思想相当的简单,大概是,对一份数据,建立M个模型(比如分类),一般这种模型比较简单,称为弱分类器(weaklearner)每次分类都将上一次分错的数据权重提高一点再进行分类,这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。
上图(图片来自prmlp660)就是一个Boosting的过程,绿色的线表示目前取得的模型(模型是由前m次得到的模型合并得到的),虚线表示当前这次模型。
每次分类的时候,会更关注分错的数据,上图中,红色和蓝色的点就是数据,点越大表示权重越高,看看右下角的图片,当m=150的时候,获取的模型已经几乎能够将红色和蓝色的点区分开了。
Boosting可以用下面的公式来表示:
训练集中一共有n个点,我们可以为里面的每一个点赋上一个权重Wi(0<=i 上图中绿色的线就是表示依次训练模型,可以想象得到,程序越往后执行,训练出的模型就越会在意那些容易分错(权重高)的点。 当全部的程序执行完后,会得到M个模型,分别对应上图的y1(x)…yM(x),通过加权的方式组合成一个最终的模型YM(x)。 我觉得Boosting更像是一个人学习的过程,开始学一样东西的时候,会去做一些习题,但是常常连一些简单的题目都会弄错,但是越到后面,简单的题目已经难不倒他了,就会去做更复杂的题目,等到他做了很多的题目后,不管是难题还是简单的题都可以解决掉了。 GradientBoosting方法: 其实Boosting更像是一种思想,GradientBoosting是一种Boosting的方法,它主要的思想是,每一次建立模型是在之前建立模型损失函数的梯度下降方向。 这句话有一点拗口,损失函数(lossfunction)描述的是模型的不靠谱程度,损失函数越大,则说明模型越容易出错(其实这里有一个方差、偏差均衡的问题,但是这里就假设损失函数越大,模型越容易出错)。 如果我们的模型能够让损失函数持续的下降,则说明我们的模型在不停的改进,而最好的方式就是让损失函数在其梯度(Gradient)的方向上下降。 下面的内容就是用数学的方式来描述GradientBoosting,数学上不算太复杂,只要潜下心来看就能看懂: ) 可加的参数的梯度表示: 假设我们的模型能够用下面的函数来表示,P表示参数,可能有多个参数组成,P={p0,p1,p2….},F(x;P)表示以P为参数的x的函数,也就是我们的预测函数。 我们的模型是由多个模型加起来的,β表示每个模型的权重,α表示模型里面的参数。 为了优化F,我们就可以优化{β,α}也就是P。 我们还是用P来表示模型的参数,可以得到,Φ(P)表示P的likelihood函数,也就是模型F(x;P)的loss函数,Φ(P)=…后面的一块看起来很复杂,只要理解成是一个损失函数就行了,不要被吓跑了。 既然模型(F(x;P))是可加的,对于参数P,我们也可以得到下面的式子: 这样优化P的过程,就可以是一个梯度下降的过程了,假设当前已经得到了m-1个模型,想要得到第m个模型的时候,我们首先对前m-1个模型求梯度。 得到最快下降的方向,gm就是最快下降的方向。 这里有一个很重要的假设,对于求出的前m-1个模型,我们认为是已知的了,不要去改变它,而我们的目标是放在之后的模型建立上。 就像做事情的时候,之前做错的事就没有后悔药吃了,只有努力在之后的事情上别犯错: 我们得到的新的模型就是,它就在P似然函数的梯度方向。 ρ是在梯度方向上下降的距离。 我们最终可以通过优化下面的式子来得到最优的ρ: 可加的函数的梯度表示: 上面通过参数P的可加性,得到了参数P的似然函数的梯度下降的方法。 我们可以将参数P的可加性推广到函数空间,我们可以得到下面的函数,此处的fi(x)类似于上面的h(x;α),因为作者的文献中这样使用,我这里就用作者的表达方法: 同样,我们可以得到函数F(x)的梯度下降方向g(x) 最终可以得到第m个模型fm(x)的表达式: 通用的GradientDescentBoosting的框架: 下面我将推导一下GradientDescent方法的通用形式,之前讨论过的: 对于模型的参数{β,α},我们可以用下面的式子来进行表示,这个式子的意思是,对于N个样本点(xi,yi)计算其在模型F(x;α,β)下的损失函数,最优的{α,β}就是能够使得这个损失函数最小的{α,β}。 表示两个m维的参数: 写成梯度下降的方式就是下面的形式,也就是我们将要得到的模型fm(x)的参数{αm,βm}能够使得fm的方向是之前得到的模型Fm-1(x)的损失函数下降最快的方向: 对于每一个数据点xi都可以得到一个gm(xi),最终我们可以得到一个完整梯度下降方向 为了使得fm(x)能够在gm(x)的方向上,我们可以优化下面的式子得到,可以使用最小二乘法: 得到了α的基础上,然后可以得到βm。 最终合并到模型中: 算法的流程图如下 之后,作者还说了这个算法在其他的地方的推广,其中,Multi-classlogisticregressionandclassification就是GBDT的一种实现,可以看看,流程图跟上面的算法类似的。 这里不打算继续写下去,再写下去就成论文翻译了,请参考文章: GreedyfunctionApproximation–AGradientBoostingMachine,作者F
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 挖掘 机器 学习 中的 一些 数学 方法 教材