#专题分享会第一期# 逻辑回归模型介绍以及优化算法

陈超群 发表了文章 • 1 个评论 • 257 次浏览 • 2016-11-14 20:04 • 来自相关话题

我目前最熟悉的是逻辑回归模型,因此这篇文章主要是对逻辑回归模型进行了一个简单的介绍,同时阐述了一下为什么在逻辑回归模型中要使用sigmoid函数,以及逻辑回归模型的优化算法,梯度下降和拟牛顿法,公式太多,我不喜欢编辑公式,所以大部分内容都是在网上复制的啦,不要嫌弃我……
 引言:
逻辑回归(Logistic Regression, LR)模型其实仅在线性回归的基础上,套用了一个逻辑函数,使因变量的输出值在[0,1]区间,将它用于二元分类。
 
一.逻辑回归模型的提出
在分类问题中,我们尝试预测的是结果是否属于某一个类
1.邮件:垃圾邮件/非垃圾邮件?
2.在线交易:是否欺诈(是/否)?
3.肿瘤:恶性/良性?
以上问题可以称之为二分类问题,可以用如下形式定义:




其中0称之为负例,1称之为正例。

假设有一个乳腺癌分类问题,自变量是瘤的大小,因变量是是否患乳腺癌{0,1},如下图,我们可以用线性回归的方法求出一条适合数据的直线:




根据线性回归模型我们只能预测连续的值,然而对于分类问题,我们需要输出 0 或 1,于是我们可以预测:
当 hθ大于等于 0.5 时,预测  y=1
当 hθ小于 0.5 时,预测 y=0 
对于上图所示的数据,这样的一个线性模型似乎能很好地完成分类任务。但是假使我们又观测到一个非常大尺寸的恶性肿瘤,将其作为实例加入到我们的训练集中来,这将使得我们获得一条新的直线。 




这时,再使用 0.5 作为阀值来预测肿瘤是良性还是恶性便不合适了。可以看出,线性回归模型,因为其预测的值可以超越[0,1]的范围,并不适合解决这样的问题。
 
于是我们引入一个新的模型,逻辑回归,该模型的输出变量范围始终在 0 和 1之间。
 
二.逻辑回归模型的假设函数
逻辑回归模型的假设是:




其中:X表示特征向量,θ表示参数,g代表逻辑函数,是一个sigmoid函数,取值范围[0,1]
公式:




 
图像:




合起来,我们得到逻辑回归模型的假设:




 hθ(x)的作用是,对于给定的输入变量,根据选择参数计算输出变量=1的可能性,即




例如,如果对于给定的 x,通过已经确定的参数计算得出 hθ(x)=0.7,则表示有 70%的几率y为正向类,相应地 y为负向类的几率为1-0.7=0.3。 
 
三.判断边界












  
四.代价函数
逻辑回归概览:
逻辑回归是一种有监督的学习方法,因此有训练集:




对于这m个训练样本来说,每个样本都包含n+1个特征:












我们知道,线性回归的Cost Function是凸函数,具有碗状的形状,而凸函数具有良好的性质:对于凸函数来说局部最小值点即为全局最小值点,因此只要能求得这类函数的一个最小值点,该点一定为全局最小值点。




因此,上述的Cost Function对于逻辑回归是不可行的,我们需要其他形式的Cost Function来保证逻辑回归的成本函数是凸函数。
监督学习问题是在假设空间F中选取模型f作为决策函数,对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致,用一个损失函数(loss function)或代价函数(cost function)来度量预测错误的程度。损失函数是f(X)和Y的非负实值函数,记作L(Y, f(X)).
统计学习中常用的损失函数有以下几种:




逻辑回归的Cost Function:
基于上节的描述和补充,这里我们选择对数似然损失函数作为逻辑回归的Cost Function:




直观的来解释这个Cost Function,首先看当y=1的情况:












于是逻辑回归模型的代价函数是:





五.参数求解
求解模型参数的问题转化为求解使得代价函数最小值的参数问题。
最小化代价函数是一个无约束优化问题,即在不对定义域与值域做任何限制的情况下,求解函数J( )的最小值。
受限于算法复杂度,目前大部分无约束优化算法只能保证求局部最小值,不过在上述问题中,我们已经说明了逻辑回归模型的代价函数是一个凸函数,局部最小值即全局最小值。
下面介绍逻辑回归模型常用的求解方法:
梯度下降(gradient descent)
Gradient descent 又叫 steepest descent,是利用一阶的梯度信息找到函数局部最优解的一种方法,也是机器学习里面最简单最常用的一种优化方法。它的思想很简单,和我开篇说的那样,要找最小值,我只需要每一步都往下走(也就是每一步都可以让代价函数小一点),然后不断的走,那肯定能走到最小值的地方,例如下图所示:





但,我同时也需要更快的到达最小值啊,怎么办呢?我们需要每一步都找下坡最快的地方,也就是每一步我走某个方向,都比走其他方法,要离最小值更近。而这个下坡最快的方向,就是梯度的负方向了。
对logistic Regression来说,梯度下降算法新鲜出炉,如下:





其中,参数α叫学习率,就是每一步走多远,这个参数蛮关键的。如果设置的太多,那么很容易就在最优值附加徘徊,因为你步伐太大了。例如要从广州到上海,但是你的一步的距离就是广州到北京那么远,没有半步的说法,自己能迈那么大步,是幸运呢?还是不幸呢?事物总有两面性嘛,它带来的好处是能很快的从远离最优值的地方回到最优值附近,只是在最优值附近的时候,它有心无力了。但如果设置的太小,那收敛速度就太慢了,向蜗牛一样,虽然会落在最优的点,但是这速度如果是猴年马月,我们也没这耐心啊。所以有的改进就是在这个学习率这个地方下刀子的。我开始迭代是,学习率大,慢慢的接近最优值的时候,我的学习率变小就可以了。所谓采两者之精华啊!
梯度下降算法的伪代码如下:
################################################
初始化回归系数为1
重复下面步骤直到收敛{
        计算整个数据集的梯度
        使用alpha x gradient来更新回归系数
}
返回回归系数值
################################################
2.2、随机梯度下降SGD (stochastic gradient descent)
      梯度下降算法在每次更新回归系数的时候都需要遍历整个数据集(计算整个数据集的回归误差),该方法对小数据集尚可。但当遇到有数十亿样本和成千上万的特征时,就有点力不从心了,它的计算复杂度太高。改进的方法是一次仅用一个样本点(的回归误差)来更新回归系数。这个方法叫随机梯度下降算法。由于可以在新的样本到来的时候对分类器进行增量的更新(假设我们已经在数据库A上训练好一个分类器h了,那新来一个样本x。对非增量学习算法来说,我们需要把x和数据库A混在一起,组成新的数据库B,再重新训练新的分类器。但对增量学习算法,我们只需要用新样本x来更新已有分类器h的参数即可),所以它属于在线学习算法。与在线学习相对应,一次处理整个数据集的叫“批处理”。
        随机梯度下降算法的伪代码如下: 
################################################
初始化回归系数为1
重复下面步骤直到收敛{
        对数据集中每个样本
               计算该样本的梯度
                使用alpha xgradient来更新回归系数
 }
返回回归系数值
################################################
2.3、改进的随机梯度下降
评价一个优化算法的优劣主要是看它是否收敛,也就是说参数是否达到稳定值,是否还会不断的变化?收敛速度是否快?




上图展示了随机梯度下降算法在200次迭代中(请先看第三和第四节再回来看这里。我们的数据库有100个二维样本,每个样本都对系数调整一次,所以共有200*100=20000次调整)三个回归系数的变化过程。其中系数X2经过50次迭代就达到了稳定值。但系数X1和X0到100次迭代后稳定。而且可恨的是系数X1和X2还在很调皮的周期波动,迭代次数很大了,心还停不下来。产生这个现象的原因是存在一些无法正确分类的样本点,也就是我们的数据集并非线性可分,但我们的logistic regression是线性分类模型,对非线性可分情况无能为力。然而我们的优化程序并没能意识到这些不正常的样本点,还一视同仁的对待,调整系数去减少对这些样本的分类误差,从而导致了在每次迭代时引发系数的剧烈改变。对我们来说,我们期待算法能避免来回波动,从而快速稳定和收敛到某个值。
 
对随机梯度下降算法,我们做两处改进来避免上述的波动问题:
1)在每次迭代时,调整更新步长alpha的值。随着迭代的进行,alpha越来越小,这会缓解系数的高频波动(也就是每次迭代系数改变得太大,跳的跨度太大)。当然了,为了避免alpha随着迭代不断减小到接近于0(这时候,系数几乎没有调整,那么迭代也没有意义了),我们约束alpha一定大于一个稍微大点的常数项,具体见代码。
2)每次迭代,改变样本的优化顺序。也就是随机选择样本来更新回归系数。这样做可以减少周期性的波动,因为样本顺序的改变,使得每次迭代不再形成周期性。
       改进的随机梯度下降算法的伪代码如下:
################################################
初始化回归系数为1
重复下面步骤直到收敛{
       对随机遍历的数据集中的每个样本
              随着迭代的逐渐进行,减小alpha的值
              计算该样本的梯度
              使用alpha x gradient来更新回归系数
    }
返回回归系数值
################################################




比较原始的随机梯度下降和改进后的梯度下降,可以看到两点不同:
1)系数不再出现周期性波动。
2)系数可以很快的稳定下来,也就是快速收敛。这里只迭代了20次就收敛了。而上面的随机梯度下降需要迭代200次才能稳定。
 
此外,常用的凸优化的方法都可以用于求解该问题。例如共轭梯度下降,牛顿法,LBFGS等。
因为这些算法都比较复杂,我查阅了大量资料,其中介绍牛顿法以及拟牛顿法的这篇博文是我觉得写得最清楚的,因为文章是图片形式,大家访问下面的网址即可:
http://blog.csdn.net/itplus/article/details/21896453                               
对于共轭梯度下降算法,我目前还没有理解,等理解清楚了再补充


最后,介绍一下为什么逻辑回归模型要使用sigmoid函数?
我们假设我们的模型最后分别以一定概率输出 1 和 -1,假设输出 1 的概率是p,输出 -1 的概率是1-p




总结逻辑回归的数学模型和求解都相对比较简洁,实现相对简单。通过对特征做离散化和其他映射,逻辑回归也可以处理非线性问题,是一个非常强大的分类器。因此在实际应用中,当我们能够拿到许多低层次的特征时,可以考虑使用逻辑回归来解决我们的问题。
 
参考:
1.http://www.cnblogs.com/sparkwen/p/3441197.html
2.http://52opencourse.com/125/co ... ssion
3.http://tech.meituan.com/intro_ ... .html
4.http://blog.csdn.net/itplus/ar ... 96453
5.斯坦福大学机器学习课程
  查看全部
我目前最熟悉的是逻辑回归模型,因此这篇文章主要是对逻辑回归模型进行了一个简单的介绍,同时阐述了一下为什么在逻辑回归模型中要使用sigmoid函数,以及逻辑回归模型的优化算法,梯度下降和拟牛顿法,公式太多,我不喜欢编辑公式,所以大部分内容都是在网上复制的啦,不要嫌弃我……
 引言:
逻辑回归(Logistic Regression, LR)模型其实仅在线性回归的基础上,套用了一个逻辑函数,使因变量的输出值在[0,1]区间,将它用于二元分类。
 
一.逻辑回归模型的提出
在分类问题中,我们尝试预测的是结果是否属于某一个类
1.邮件:垃圾邮件/非垃圾邮件?
2.在线交易:是否欺诈(是/否)?
3.肿瘤:恶性/良性?
以上问题可以称之为二分类问题,可以用如下形式定义:
1.png

其中0称之为负例,1称之为正例。

假设有一个乳腺癌分类问题,自变量是瘤的大小,因变量是是否患乳腺癌{0,1},如下图,我们可以用线性回归的方法求出一条适合数据的直线:
2.jpg

根据线性回归模型我们只能预测连续的值,然而对于分类问题,我们需要输出 0 或 1,于是我们可以预测:
当 hθ大于等于 0.5 时,预测  y=1
当 hθ小于 0.5 时,预测 y=0 
对于上图所示的数据,这样的一个线性模型似乎能很好地完成分类任务。但是假使我们又观测到一个非常大尺寸的恶性肿瘤,将其作为实例加入到我们的训练集中来,这将使得我们获得一条新的直线。 
3.jpg

这时,再使用 0.5 作为阀值来预测肿瘤是良性还是恶性便不合适了。可以看出,线性回归模型,因为其预测的值可以超越[0,1]的范围,并不适合解决这样的问题。
 
于是我们引入一个新的模型,逻辑回归,该模型的输出变量范围始终在 0 和 1之间。
 
二.逻辑回归模型的假设函数
逻辑回归模型的假设是:
4.png

其中:X表示特征向量,θ表示参数,g代表逻辑函数,是一个sigmoid函数,取值范围[0,1]
公式:
5.jpg

 
图像:
6.jpg

合起来,我们得到逻辑回归模型的假设:
7.jpg

 hθ(x)的作用是,对于给定的输入变量,根据选择参数计算输出变量=1的可能性,即
8.png

例如,如果对于给定的 x,通过已经确定的参数计算得出 hθ(x)=0.7,则表示有 70%的几率y为正向类,相应地 y为负向类的几率为1-0.7=0.3。 
 
三.判断边界
9.png

10.png

11.png

  
四.代价函数
逻辑回归概览:
逻辑回归是一种有监督的学习方法,因此有训练集:
12.png

对于这m个训练样本来说,每个样本都包含n+1个特征:
13.png

14.png

15.png

我们知道,线性回归的Cost Function是凸函数,具有碗状的形状,而凸函数具有良好的性质:对于凸函数来说局部最小值点即为全局最小值点,因此只要能求得这类函数的一个最小值点,该点一定为全局最小值点。
16.png

因此,上述的Cost Function对于逻辑回归是不可行的,我们需要其他形式的Cost Function来保证逻辑回归的成本函数是凸函数。
监督学习问题是在假设空间F中选取模型f作为决策函数,对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致,用一个损失函数(loss function)或代价函数(cost function)来度量预测错误的程度。损失函数是f(X)和Y的非负实值函数,记作L(Y, f(X)).
统计学习中常用的损失函数有以下几种:
17.png

逻辑回归的Cost Function:
基于上节的描述和补充,这里我们选择对数似然损失函数作为逻辑回归的Cost Function:
18.png

直观的来解释这个Cost Function,首先看当y=1的情况:
19.png

20.png

22.png

于是逻辑回归模型的代价函数是:
23.jpg


五.参数求解
求解模型参数的问题转化为求解使得代价函数最小值的参数问题。
最小化代价函数是一个无约束优化问题,即在不对定义域与值域做任何限制的情况下,求解函数J( )的最小值。
受限于算法复杂度,目前大部分无约束优化算法只能保证求局部最小值,不过在上述问题中,我们已经说明了逻辑回归模型的代价函数是一个凸函数,局部最小值即全局最小值。
下面介绍逻辑回归模型常用的求解方法:
梯度下降(gradient descent)
Gradient descent 又叫 steepest descent,是利用一阶的梯度信息找到函数局部最优解的一种方法,也是机器学习里面最简单最常用的一种优化方法。它的思想很简单,和我开篇说的那样,要找最小值,我只需要每一步都往下走(也就是每一步都可以让代价函数小一点),然后不断的走,那肯定能走到最小值的地方,例如下图所示:
23.png


但,我同时也需要更快的到达最小值啊,怎么办呢?我们需要每一步都找下坡最快的地方,也就是每一步我走某个方向,都比走其他方法,要离最小值更近。而这个下坡最快的方向,就是梯度的负方向了。
对logistic Regression来说,梯度下降算法新鲜出炉,如下:
24.png


其中,参数α叫学习率,就是每一步走多远,这个参数蛮关键的。如果设置的太多,那么很容易就在最优值附加徘徊,因为你步伐太大了。例如要从广州到上海,但是你的一步的距离就是广州到北京那么远,没有半步的说法,自己能迈那么大步,是幸运呢?还是不幸呢?事物总有两面性嘛,它带来的好处是能很快的从远离最优值的地方回到最优值附近,只是在最优值附近的时候,它有心无力了。但如果设置的太小,那收敛速度就太慢了,向蜗牛一样,虽然会落在最优的点,但是这速度如果是猴年马月,我们也没这耐心啊。所以有的改进就是在这个学习率这个地方下刀子的。我开始迭代是,学习率大,慢慢的接近最优值的时候,我的学习率变小就可以了。所谓采两者之精华啊!
梯度下降算法的伪代码如下:
################################################
初始化回归系数为1
重复下面步骤直到收敛{
        计算整个数据集的梯度
        使用alpha x gradient来更新回归系数
}
返回回归系数值
################################################
2.2、随机梯度下降SGD (stochastic gradient descent)
      梯度下降算法在每次更新回归系数的时候都需要遍历整个数据集(计算整个数据集的回归误差),该方法对小数据集尚可。但当遇到有数十亿样本和成千上万的特征时,就有点力不从心了,它的计算复杂度太高。改进的方法是一次仅用一个样本点(的回归误差)来更新回归系数。这个方法叫随机梯度下降算法。由于可以在新的样本到来的时候对分类器进行增量的更新(假设我们已经在数据库A上训练好一个分类器h了,那新来一个样本x。对非增量学习算法来说,我们需要把x和数据库A混在一起,组成新的数据库B,再重新训练新的分类器。但对增量学习算法,我们只需要用新样本x来更新已有分类器h的参数即可),所以它属于在线学习算法。与在线学习相对应,一次处理整个数据集的叫“批处理”。
        随机梯度下降算法的伪代码如下: 
################################################
初始化回归系数为1
重复下面步骤直到收敛{
        对数据集中每个样本
               计算该样本的梯度
                使用alpha xgradient来更新回归系数
 }
返回回归系数值
################################################
2.3、改进的随机梯度下降
评价一个优化算法的优劣主要是看它是否收敛,也就是说参数是否达到稳定值,是否还会不断的变化?收敛速度是否快?
25.png

上图展示了随机梯度下降算法在200次迭代中(请先看第三和第四节再回来看这里。我们的数据库有100个二维样本,每个样本都对系数调整一次,所以共有200*100=20000次调整)三个回归系数的变化过程。其中系数X2经过50次迭代就达到了稳定值。但系数X1和X0到100次迭代后稳定。而且可恨的是系数X1和X2还在很调皮的周期波动,迭代次数很大了,心还停不下来。产生这个现象的原因是存在一些无法正确分类的样本点,也就是我们的数据集并非线性可分,但我们的logistic regression是线性分类模型,对非线性可分情况无能为力。然而我们的优化程序并没能意识到这些不正常的样本点,还一视同仁的对待,调整系数去减少对这些样本的分类误差,从而导致了在每次迭代时引发系数的剧烈改变。对我们来说,我们期待算法能避免来回波动,从而快速稳定和收敛到某个值。
 
对随机梯度下降算法,我们做两处改进来避免上述的波动问题:
1)在每次迭代时,调整更新步长alpha的值。随着迭代的进行,alpha越来越小,这会缓解系数的高频波动(也就是每次迭代系数改变得太大,跳的跨度太大)。当然了,为了避免alpha随着迭代不断减小到接近于0(这时候,系数几乎没有调整,那么迭代也没有意义了),我们约束alpha一定大于一个稍微大点的常数项,具体见代码。
2)每次迭代,改变样本的优化顺序。也就是随机选择样本来更新回归系数。这样做可以减少周期性的波动,因为样本顺序的改变,使得每次迭代不再形成周期性。
       改进的随机梯度下降算法的伪代码如下:
################################################
初始化回归系数为1
重复下面步骤直到收敛{
       对随机遍历的数据集中的每个样本
              随着迭代的逐渐进行,减小alpha的值
              计算该样本的梯度
              使用alpha x gradient来更新回归系数
    }
返回回归系数值
################################################
26.png

比较原始的随机梯度下降和改进后的梯度下降,可以看到两点不同:
1)系数不再出现周期性波动。
2)系数可以很快的稳定下来,也就是快速收敛。这里只迭代了20次就收敛了。而上面的随机梯度下降需要迭代200次才能稳定。
 
此外,常用的凸优化的方法都可以用于求解该问题。例如共轭梯度下降,牛顿法,LBFGS等。
因为这些算法都比较复杂,我查阅了大量资料,其中介绍牛顿法以及拟牛顿法的这篇博文是我觉得写得最清楚的,因为文章是图片形式,大家访问下面的网址即可:
http://blog.csdn.net/itplus/article/details/21896453                               
对于共轭梯度下降算法,我目前还没有理解,等理解清楚了再补充


最后,介绍一下为什么逻辑回归模型要使用sigmoid函数?
我们假设我们的模型最后分别以一定概率输出 1 和 -1,假设输出 1 的概率是p,输出 -1 的概率是1-p
34.png

总结逻辑回归的数学模型和求解都相对比较简洁,实现相对简单。通过对特征做离散化和其他映射,逻辑回归也可以处理非线性问题,是一个非常强大的分类器。因此在实际应用中,当我们能够拿到许多低层次的特征时,可以考虑使用逻辑回归来解决我们的问题。
 
参考:
1.http://www.cnblogs.com/sparkwen/p/3441197.html
2.http://52opencourse.com/125/co ... ssion
3.http://tech.meituan.com/intro_ ... .html
4.http://blog.csdn.net/itplus/ar ... 96453
5.斯坦福大学机器学习课程
 

#专题分享会第一期# GBDT & LASSO

王开新 发表了文章 • 0 个评论 • 110 次浏览 • 2016-11-14 16:31 • 来自相关话题

不太好取标题,要交流的内容比较零散,虽然之前发了博客链接,但可能不好对应上,所以在这儿整理一下。
 
0:挑一个最熟悉的模型介绍一下

              贝叶斯与多项式拟合​
              介绍了线性回归的概率解释,以及与贝叶斯理论的联系。严格来说,这不算一个模型。选这个主题是因为当时在PRML上读到这部分内容时,受到的撼动很大,感觉以前学的线性回归只是皮毛,有很多的内容待学习。相信这篇文章也可以给其它正在入门的同学带来启发,而不是简单地灌输一个模型,所以选了这篇。
 
 
3:怎么判断是否出现过拟合,如何避免或者出现了如何处理?L1和L2的区别?L1如何进行梯度下降?

               对第一个问题地研究较少,主要重心放在了第二个问题上。
               对第一个问题可以参考机器学习教材(PRML,周志华老师的书,EOSL)都会有的一章——Bias Variance Tradeoff,应该会有启发。我还没系统阅读,所以不敢仅仅参考网上的博客就乱讲。
               对第二个问题,L2,L1范数均用来正则化,用L2范数也被称为岭回归,属于收缩技术的一种。(收缩技术是一种防止过拟合的策略,包含很多内容,还在整理中)。L1范数不仅可以用来防止过拟合,还可以用来进行特征筛选,因为使用L1范数容易产生稀疏解(即很多feature取值为0)。使用L1范数进行正则化,也称为LASSO。求解LASSO可以使用一种近端梯度下降的技术(还未整理完),也可以通过更一般化的推广LARS来进行求解,见这一篇和这一篇​。
 
 
4:RF和GBDT的区别?决策树如何并行化?RF如何并行化?GBDT如何进行并行化?

               RF和BOOST在这一篇中有介绍,GBDT在这一篇​中有详细介绍。RF的并行化很好理解,网上资源也很多,暂未整理。由于BOOSTING 整体是一个串行的过程,GBDT的并行化只能对基学习器训练时进行并行。XGboost是GBDT并行化的代表,相关的内容还在整理中。
 
 --------------------------------------------------------------------
时间仓促,一个小主题就需要查很多资料,一个问题又牵出另一个问题,所以很多东西都还没有做完。这应该也是学习机器学习的过程吧,没有什么知识是孤立的。不过,对于写完的博客,我可以保证理解了相关的内容,如果有什么问题欢迎发邮件和我讨论(ohmduniu@outlook.com)。
 
这几天应该会抽时间把XGBoost的写完,近端梯度下降估计要继续往后推了(各门课都要开始写大作业了T T) 查看全部
不太好取标题,要交流的内容比较零散,虽然之前发了博客链接,但可能不好对应上,所以在这儿整理一下。
 
0:挑一个最熟悉的模型介绍一下

              贝叶斯与多项式拟合
              介绍了线性回归的概率解释,以及与贝叶斯理论的联系。严格来说,这不算一个模型。选这个主题是因为当时在PRML上读到这部分内容时,受到的撼动很大,感觉以前学的线性回归只是皮毛,有很多的内容待学习。相信这篇文章也可以给其它正在入门的同学带来启发,而不是简单地灌输一个模型,所以选了这篇。
 
 
3:怎么判断是否出现过拟合,如何避免或者出现了如何处理?L1和L2的区别?L1如何进行梯度下降?

               对第一个问题地研究较少,主要重心放在了第二个问题上。
               对第一个问题可以参考机器学习教材(PRML,周志华老师的书,EOSL)都会有的一章——Bias Variance Tradeoff,应该会有启发。我还没系统阅读,所以不敢仅仅参考网上的博客就乱讲。
               对第二个问题,L2,L1范数均用来正则化,用L2范数也被称为岭回归,属于收缩技术的一种。(收缩技术是一种防止过拟合的策略,包含很多内容,还在整理中)。L1范数不仅可以用来防止过拟合,还可以用来进行特征筛选,因为使用L1范数容易产生稀疏解(即很多feature取值为0)。使用L1范数进行正则化,也称为LASSO。求解LASSO可以使用一种近端梯度下降的技术(还未整理完),也可以通过更一般化的推广LARS来进行求解,见这一篇这一篇​。
 
 
4:RF和GBDT的区别?决策树如何并行化?RF如何并行化?GBDT如何进行并行化?

               RF和BOOST在这一篇中有介绍,GBDT在这一篇​中有详细介绍。RF的并行化很好理解,网上资源也很多,暂未整理。由于BOOSTING 整体是一个串行的过程,GBDT的并行化只能对基学习器训练时进行并行。XGboost是GBDT并行化的代表,相关的内容还在整理中。
 
 --------------------------------------------------------------------
时间仓促,一个小主题就需要查很多资料,一个问题又牵出另一个问题,所以很多东西都还没有做完。这应该也是学习机器学习的过程吧,没有什么知识是孤立的。不过,对于写完的博客,我可以保证理解了相关的内容,如果有什么问题欢迎发邮件和我讨论(ohmduniu@outlook.com)。
 
这几天应该会抽时间把XGBoost的写完,近端梯度下降估计要继续往后推了(各门课都要开始写大作业了T T)

#专题分享会第一期# 如何处理正负样本不均衡

郜梦蕊 发表了文章 • 0 个评论 • 99 次浏览 • 2016-11-14 15:30 • 来自相关话题

    分类学习方法都有一个共同的基本假设,即不同类别的训练样例书目相当。如果不同类别的训练样例书目稍有差别,通常影响不大,但若差别很大,则会对学习过程造成困扰。例如有998个反例,2个正例,那么学习方法只需返回一个永远将新样本预测为反例的学习器,就能达到99.8%的精度;然而这样的学习器往往没有价值,因为它不能预测出任何正例。
    类别不均衡就是指分类任务中不同类别的训练样例数目差别很大的情况。
 
    我们先假定正例较少,反例较多。
    从线性分类器的角度讨论容易理解





  事实上是在用预测出的y值与一个阈值进行比较,例如通常在y>0.5时判别为正例,否则为反例。y实际上表达了正例的可能性,几率y/1-y反映了正例与反例可能性之比值,阈值设置为0.5恰表明分类器认为真实正、反例可能性相同,即分类器决策规则(式1)为:






则预测为正例
    然而当训练集中正反例数目不同时,令m+表示正例数目,m-表示反例数目,则观测几率是m+/m-,由于我们通常假设真实样本总体的无偏采样,因此观测几率就代表了真实几率。于是只要分类器的预测几率高于观测几率就应判定为正例。即下式:




则预测为正例。
    但是,我们的分类器基于式1进行决策,因此需要对决策值进行调整,只需令




    这就是类别不平衡的一个基本策略,称为“再缩放”
 
    现有技术大体上有三类做法:
   (1)直接对训练集里的反例进行“欠采样”,即去除一些反例使得正、反例数目接近,然后再进行学习;
   (2)对训练集里的正例进行“过采样”,即增加一些正例使得正、反例数目接近,然后再进行学习;
   (3)直接基于原始训练集进行学习,但在用训练好的分类器进行预测时,将式子嵌入到其决策过程中,称为“阈值移动”

    评价:欠采样法的时间开销远小于过采样法,因为前者丢弃了很多反例,使得分类器训练集远小于初始训练集,而过采样法增加了很多正例,其训练集大于初始训练集。
    需要注意的是,过采样法不能简单地对初始正例样本进行重复采样,否则会招致严重的过拟合;采样法的代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例
    另一方面,欠采样法若随机丢弃反例,可能丢失一些重要信息;欠采样法的代表性算法EasyEnsemble利用集成学习机制,将反例划分为若干个集合供不同学习器使用,这样对每个学习器来看都进行了欠采样,但在全局来看就不会丢失重要信息。
 
参考:周志华《机器学习》3.6 类别不平衡问题
  查看全部
    分类学习方法都有一个共同的基本假设,即不同类别的训练样例书目相当。如果不同类别的训练样例书目稍有差别,通常影响不大,但若差别很大,则会对学习过程造成困扰。例如有998个反例,2个正例,那么学习方法只需返回一个永远将新样本预测为反例的学习器,就能达到99.8%的精度;然而这样的学习器往往没有价值,因为它不能预测出任何正例。
    类别不均衡就是指分类任务中不同类别的训练样例数目差别很大的情况。
 
    我们先假定正例较少,反例较多。
    从线性分类器的角度讨论容易理解

正负1.png

  事实上是在用预测出的y值与一个阈值进行比较,例如通常在y>0.5时判别为正例,否则为反例。y实际上表达了正例的可能性,几率y/1-y反映了正例与反例可能性之比值,阈值设置为0.5恰表明分类器认为真实正、反例可能性相同,即分类器决策规则(式1)为:

正负2.png


则预测为正例
    然而当训练集中正反例数目不同时,令m+表示正例数目,m-表示反例数目,则观测几率是m+/m-,由于我们通常假设真实样本总体的无偏采样,因此观测几率就代表了真实几率。于是只要分类器的预测几率高于观测几率就应判定为正例。即下式:
正负3.png

则预测为正例。
    但是,我们的分类器基于式1进行决策,因此需要对决策值进行调整,只需令
正负4.png

    这就是类别不平衡的一个基本策略,称为“再缩放”
 
    现有技术大体上有三类做法:
   (1)直接对训练集里的反例进行“欠采样”,即去除一些反例使得正、反例数目接近,然后再进行学习;
   (2)对训练集里的正例进行“过采样”,即增加一些正例使得正、反例数目接近,然后再进行学习;
   (3)直接基于原始训练集进行学习,但在用训练好的分类器进行预测时,将式子嵌入到其决策过程中,称为“阈值移动”

    评价:欠采样法的时间开销远小于过采样法,因为前者丢弃了很多反例,使得分类器训练集远小于初始训练集,而过采样法增加了很多正例,其训练集大于初始训练集。
    需要注意的是,过采样法不能简单地对初始正例样本进行重复采样,否则会招致严重的过拟合;采样法的代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例
    另一方面,欠采样法若随机丢弃反例,可能丢失一些重要信息;欠采样法的代表性算法EasyEnsemble利用集成学习机制,将反例划分为若干个集合供不同学习器使用,这样对每个学习器来看都进行了欠采样,但在全局来看就不会丢失重要信息。
 
参考:周志华《机器学习》3.6 类别不平衡问题
 

#专题分享会第一期# 特征降维

郜梦蕊 发表了文章 • 0 个评论 • 133 次浏览 • 2016-11-14 15:19 • 来自相关话题

1.特征降维与特征选择的区别
特征降维:一般指的是维数约简,将原始高维特征空间里的点向低维空间投影,维数减少,这这个过程中,特征发生了根本性变化特征选择:从原始特征中选取一个特征子集。
 
2.特征降维
机器学习领域中所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数 f : x->y,其中x是原始数据点的表达,目前最多使用向量表达形式。 y是数据点映射后的低维向量表达,通常y的维度小于x的维度(当然提高维度也是可以的)。f可能是显式的或隐式的、线性的或非线性的。在原始的高维空间中,包含有冗余信息以及噪音信息,特征降维的目的在于减少冗余信息所造成的误差,提高识别的精度。


3.主成分分析法
Principal Component Analysis(PCA)是最常用的线性降维方法,它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构)

4.LDA(Linear Discriminant Analysis 或者 Fisher Linear Discriminant)
LDA是一种有监督的线性降维算法,与PCA保持数据信息不同,LDA是为了使降维后的数据点尽可能地容易被区分。假设原始数据表示为X,(m*n矩阵,m是维度,n是sample的数量).既然是线性的,那么就是希望找到映射向量a, 使得 a‘X后的数据点能够保持以下两种性质:
    (1)同类的数据点尽可能的接近(within class)
    (2)不同类的数据点尽可能的分开(between class)

5.局部线性嵌入(LLE,Locally linear embedding)
LLE是一种非线性降维算法,它能够使降维后的数据较好地保持原有流型结构。





如上图所示,使用LLE将三维数据(b)映射到二维(c)之后,映射后的数据仍能保持原有的数据流形(红色的点互相接近,蓝色的也互相接近),说明LLE有效地保持了数据原有的流行结构。但是LLE在有些情况下也并不适用,如果数据分布在整个封闭的球面上,LLE则不能将它映射到二维空间,且不能保持原有的数据流形。那么我们在处理数据中,首先假设数据不是分布在闭合的球面或者椭球面上。

6.Laplacian Eigenmaps 拉普拉斯特征映射
它的直观思想是希望相互间有关系的点(在图中相连的点)在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。Laplacian Eigenmaps也通过构建相似关系图(对应的矩阵为W)来重构数据流形的局部结构特征。Laplacian Eigenmaps算法的主要思想是,如果两个数据实例i和j很相似,那么i和j在降维后目标子空间中应该尽量接近。
 
  7.参考文献
[1] http://www.36dsj.com/archives/26723
[2] 百度文库:主成分分析法的原理应用及计算步骤
http://wenku.baidu.com/link%3F ... vD39e
[3] http://www.cnblogs.com/lyfruit ... .html
[4] http://blog.csdn.net/xbinworld 查看全部
1.特征降维与特征选择的区别
  • 特征降维:一般指的是维数约简,将原始高维特征空间里的点向低维空间投影,维数减少,这这个过程中,特征发生了根本性变化
  • 特征选择:从原始特征中选取一个特征子集。

 
2.特征降维
  • 机器学习领域中所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数 f : x->y,其中x是原始数据点的表达,目前最多使用向量表达形式。 y是数据点映射后的低维向量表达,通常y的维度小于x的维度(当然提高维度也是可以的)。f可能是显式的或隐式的、线性的或非线性的。
  • 在原始的高维空间中,包含有冗余信息以及噪音信息,特征降维的目的在于减少冗余信息所造成的误差,提高识别的精度。



3.主成分分析法
  • Principal Component Analysis(PCA)是最常用的线性降维方法,它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。
  • 通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构)


4.LDA(Linear Discriminant Analysis 或者 Fisher Linear Discriminant)
  • LDA是一种有监督的线性降维算法,与PCA保持数据信息不同,LDA是为了使降维后的数据点尽可能地容易被区分。
  • 假设原始数据表示为X,(m*n矩阵,m是维度,n是sample的数量).既然是线性的,那么就是希望找到映射向量a, 使得 a‘X后的数据点能够保持以下两种性质:

    (1)同类的数据点尽可能的接近(within class)
    (2)不同类的数据点尽可能的分开(between class)

5.局部线性嵌入(LLE,Locally linear embedding)
  • LLE是一种非线性降维算法,它能够使降维后的数据较好地保持原有流型结构。


1.LLE_.jpg

  • 如上图所示,使用LLE将三维数据(b)映射到二维(c)之后,映射后的数据仍能保持原有的数据流形(红色的点互相接近,蓝色的也互相接近),说明LLE有效地保持了数据原有的流行结构。
  • 但是LLE在有些情况下也并不适用,如果数据分布在整个封闭的球面上,LLE则不能将它映射到二维空间,且不能保持原有的数据流形。那么我们在处理数据中,首先假设数据不是分布在闭合的球面或者椭球面上。


6.Laplacian Eigenmaps 拉普拉斯特征映射
  • 它的直观思想是希望相互间有关系的点(在图中相连的点)在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。Laplacian Eigenmaps也通过构建相似关系图(对应的矩阵为W)来重构数据流形的局部结构特征。
  • Laplacian Eigenmaps算法的主要思想是,如果两个数据实例i和j很相似,那么i和j在降维后目标子空间中应该尽量接近。

 
  7.参考文献
[1] http://www.36dsj.com/archives/26723
[2] 百度文库:主成分分析法的原理应用及计算步骤
http://wenku.baidu.com/link%3F ... vD39e
[3] http://www.cnblogs.com/lyfruit ... .html
[4] http://blog.csdn.net/xbinworld

#专题分享会第一期# 特征选择

郜梦蕊 发表了文章 • 0 个评论 • 106 次浏览 • 2016-11-14 14:18 • 来自相关话题

1.特征选择概念
属性即特征;分为相关特征与无关特征冗余特征:包含的信息能从其他特征中推演出来,比如说立体的底面积,可以从底面长、底面宽推导出来。特征选择:从相关子集中选择出相关特征子集的过程,是重要的数据预处理过程
  注意:必须确保不丢失重要特征
如果想从初始的特征集合中选取一个包含了所有重要信息的特征子集,若没有任何领域知识作为先验假设,只能遍历所有可能的子集,在计算上不可行,会遭遇组合爆炸。 可行做法:产生一个“候选子集”,评价其好坏,给予评价结果,产生下一个候选子集,再进行评价,直至无法找到更好的候选子集为止。特征选择的过程可以分为两个关键问题:
    (1)如何根据评价结果获取下一个候选特征子集?——子集搜索问题
    (2)如何评价候选特征子集的好坏?——子集评价问题
那么特征选择的过程可以用下图进行表示:





图1 特征选择过程
2.子集搜索问题
 
2.1 全局最优搜索策略的特征选择方法
   n个特征里可能的特征子集个数:




   当n不大时,可以采用枚举法选择最优特征子集
   存在问题:n较大时,不适用
   算法:广度优先搜索、分支限界搜索、定向搜索、最优优先搜索
2.2 随机搜索策略
将概率推理和采样过程结合,基于对分类估计的有效性,对每个特征赋予一定的权重;然后根据用户自定义或自适应的阈值来对特征重要性进行评价,当特征所对应的权重超出了这个阈值,它便被选中作为重要的特征来训练分类器。算法:随机产生序列算法(RGSS)、模拟退火算法(SA)、遗传算法(GA)存在问题:具有较高的不确定性,只有当总循环次数较大时,才可能找到较好的结果。在随机搜索策略中,可能需要对一些参数进行设置,参数选择的合适与否,对最终结果的好坏起着很大的作用。
2.3 启发式搜索
   给定特征集合{a1,a2,a3,a4,a5,a6,,,aN}
前向搜索:将每个特征看成是一个候选子集,对这N个候选单特征子集进行评价,假定a1最优,于是将a1作为第一轮的选定集;然后再上一轮的选定集中加入一个特征,构成包含两个特征的候选子集,假定在N-1个候选两特征集中,{a1,a5}最优,且优于{a1},则将{a1,a5}作为本轮的选定集;假设在第K+1轮中,最优的候选(k+1)特征子集不如上一轮的候选集,则停止生成候选子集,并将上一轮的K特征集合作为特征选择结果后向搜索:从完整的特征集合开始,每次尝试去掉一个无关特征,逐渐减少特征数量双向搜索:每一轮,增加选定特征,同时减少无关特征算法:序列前向选择(SFS),序列后向选择(SBS),双向搜索(BDS),增L去R算法(LRS),序列浮动选择(前向SFFS,后向SFBS),决策树存在问题:启发式搜索策略虽然效率高,但是它以牺牲全局最优为代价

2.4 总结
  每种搜索策略各有优缺点,在实际应用过程中可以根据具体环境和准则函数寻找最佳平衡点。
特征数较少,可采用全局最优;不要求全局最优,但要求计算速度快,可采用启发式;
需要高性能的子集,不介意计算时间,可采用随机时;

3.子集评价问题 
  下面简单介绍常见的评价函数。 
(1) 相关性 ( Correlation)
  运用相关性来度量特征子集的好坏是基于这样一个假设:好的特征子集所包含的特征应该是与分类的相关度较高(相关度高),而特征之间相关度较低的(亢余度低)。
   可以使用线性相关系数(correlation coefficient) 来衡量向量之间线性相关度。





 
(2) 距离 (Distance Metrics )
   运用距离度量进行特征选择是基于这样的假设:好的特征子集应该使得属于同一类的样本距离尽可能小,属于不同类的样本之间的距离尽可能远。
   常用的距离度量(相似性度量)包括欧氏距离、标准化欧氏距离、马氏距离等。 
(3) 信息增益( Information Gain )      
   假设存在离散变量Y,Y中的取值包括{y1,y2,....,ym} ,yi出现的概率为Pi。则Y的信息熵定义为:






   信息熵有如下特性:若集合Y的元素分布越“纯”,则其信息熵越小;若Y分布越“紊乱”,则其信息熵越大。在极端的情况下:若Y只能取一个值,即P1=1,则H(Y)取最小值0;反之若各种取值出现的概率都相等,即都是1/m,则H(Y)取最大值log2m。
   给定数据集D,假定D中第i类样本所占的比例为Pi(i=1,2,...,|y|)
   假定样本属性均为离散型,对属性子集A,假定根据其取值将D分成了V个子集
   假设每个属性有V个可能取值,则
   



   这可能是一个很大的值,因此实践过程中通常是从子集搜索过程中前一轮属性子集的评价值出发来进行计算。{D1,D2,D3,D4,…,Dv}
   每个子集上的样本在A上取值相同,于是我们可计算属性子集A的信息增益
   
   


 
   其中信息熵定义为
   



    
   信息增益Gain(A)越大,意味着特征子集A包含的有助于分类的信息越多。于是,对每个候选子集,我们可基于训练数据集D来计算其信息增益,以此作为评价准则。
 
    特征子集A实际上确定了对数据集D上的一个划分,每个划分区域对应着A上的一个取值,而样本标记信息Y则对应着对D的真实划分,通过估算这两个划分的差异,就能对A进行评价。与Y对应的划分的差异越小,则说明A越好,信息熵仅是判断这个差异的一种途径,其他能判断两个划分差异的机制都能用于特征子集评价。
 
 (4)一致性( Consistency )
    若样本1与样本2属于不同的分类,但在特征A、 B上的取值完全一样,那么特征子集{A,B}不应该选作最终的特征集。
 (5)分类器错误率 (Classifier error rate ) 
    使用特定的分类器,用给定的特征子集对样本集进行分类,用分类的精度来衡量特征子集的好坏。
    
    以上5种度量方法中,相关性、距离、信息增益、一致性属于筛选器,而分类器错误率属于封装器。

4.分类
  将特征子集搜索机制与子集评价机制相结合,即可得到特征选择方法。常见的特征选择方法可分为三类:
过滤式(filter),包裹式(wrapper),嵌入式(embedding)
(1)过滤式选择

   先对数据集进行特征选择,然后再训练学习器,特征学习过程与后续学习器无关,这相当于先用特征选择过程对初始特征进行过滤,再用过滤后的特征来训练模型。





图2 Filter原理(Ricardo Gutierrez-Osuna 2008 ) 
(2)包裹式选择
   与过滤式特征选择不考虑后续学习器不同,包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之,包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
    一般而言,包裹式直接针对给定学习器优化,从最终学习器性能来看,比过滤式更好,另一方面,由于在特征选择过程中需要多次训练学习器,因而计算开销通常比过滤式大得多。





图3. Wrapper原理 (Ricardo Gutierrez-Osuna 2008 )
(3)嵌入式选择与L1正则化
   将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。

5.参考文献
[1]姚旭, 王晓丹, 张玉玺, 等. 特征选择方法综述[J]. 控制与决策, 2012, 27(2): 161-166.
[2] 苍梧.特征选择常用算法综述
http://www.cnblogs.com/heaad/a ... .html
[3] 周志华.《机器学习》,清华大学出版社
[4] http://www.cnblogs.com/heaad/a ... .html 

  查看全部
1.特征选择概念
  • 属性即特征;分为相关特征与无关特征
  • 冗余特征:包含的信息能从其他特征中推演出来,比如说立体的底面积,可以从底面长、底面宽推导出来。
  • 特征选择:从相关子集中选择出相关特征子集的过程,是重要的数据预处理过程

  注意:必须确保不丢失重要特征
  • 如果想从初始的特征集合中选取一个包含了所有重要信息的特征子集,若没有任何领域知识作为先验假设,只能遍历所有可能的子集,在计算上不可行,会遭遇组合爆炸。 
  • 可行做法:产生一个“候选子集”,评价其好坏,给予评价结果,产生下一个候选子集,再进行评价,直至无法找到更好的候选子集为止。
  • 特征选择的过程可以分为两个关键问题:

    (1)如何根据评价结果获取下一个候选特征子集?——子集搜索问题
    (2)如何评价候选特征子集的好坏?——子集评价问题
  • 那么特征选择的过程可以用下图进行表示:


1特征选择过程.png

图1 特征选择过程
2.子集搜索问题
 
2.1 全局最优搜索策略的特征选择方法
   n个特征里可能的特征子集个数:
2_CNN.png

   当n不大时,可以采用枚举法选择最优特征子集
   存在问题:n较大时,不适用
   算法:广度优先搜索、分支限界搜索、定向搜索、最优优先搜索
2.2 随机搜索策略
  • 将概率推理和采样过程结合,基于对分类估计的有效性,对每个特征赋予一定的权重;然后根据用户自定义或自适应的阈值来对特征重要性进行评价,当特征所对应的权重超出了这个阈值,它便被选中作为重要的特征来训练分类器。
  • 算法:随机产生序列算法(RGSS)、模拟退火算法(SA)、遗传算法(GA)
  • 存在问题:具有较高的不确定性,只有当总循环次数较大时,才可能找到较好的结果。在随机搜索策略中,可能需要对一些参数进行设置,参数选择的合适与否,对最终结果的好坏起着很大的作用。

2.3 启发式搜索
   给定特征集合{a1,a2,a3,a4,a5,a6,,,aN}
  • 前向搜索:将每个特征看成是一个候选子集,对这N个候选单特征子集进行评价,假定a1最优,于是将a1作为第一轮的选定集;然后再上一轮的选定集中加入一个特征,构成包含两个特征的候选子集,假定在N-1个候选两特征集中,{a1,a5}最优,且优于{a1},则将{a1,a5}作为本轮的选定集;假设在第K+1轮中,最优的候选(k+1)特征子集不如上一轮的候选集,则停止生成候选子集,并将上一轮的K特征集合作为特征选择结果
  • 后向搜索:从完整的特征集合开始,每次尝试去掉一个无关特征,逐渐减少特征数量
  • 双向搜索:每一轮,增加选定特征,同时减少无关特征
  • 算法:序列前向选择(SFS),序列后向选择(SBS),双向搜索(BDS),增L去R算法(LRS),序列浮动选择(前向SFFS,后向SFBS),决策树
  • 存在问题:启发式搜索策略虽然效率高,但是它以牺牲全局最优为代价


2.4 总结
  每种搜索策略各有优缺点,在实际应用过程中可以根据具体环境和准则函数寻找最佳平衡点。
  • 特征数较少,可采用全局最优;
  • 不要求全局最优,但要求计算速度快,可采用启发式;

  • 需要高性能的子集,不介意计算时间,可采用随机时;


3.子集评价问题 
  下面简单介绍常见的评价函数。 
(1) 相关性 ( Correlation)
  运用相关性来度量特征子集的好坏是基于这样一个假设:好的特征子集所包含的特征应该是与分类的相关度较高(相关度高),而特征之间相关度较低的(亢余度低)。
   可以使用线性相关系数(correlation coefficient) 来衡量向量之间线性相关度。

3_相关性.png

 
(2) 距离 (Distance Metrics )
   运用距离度量进行特征选择是基于这样的假设:好的特征子集应该使得属于同一类的样本距离尽可能小,属于不同类的样本之间的距离尽可能远。
   常用的距离度量(相似性度量)包括欧氏距离、标准化欧氏距离、马氏距离等。 
(3) 信息增益( Information Gain )      
   假设存在离散变量Y,Y中的取值包括{y1,y2,....,ym} ,yi出现的概率为Pi。则Y的信息熵定义为:

4_信息增益.png


   信息熵有如下特性:若集合Y的元素分布越“纯”,则其信息熵越小;若Y分布越“紊乱”,则其信息熵越大。在极端的情况下:若Y只能取一个值,即P1=1,则H(Y)取最小值0;反之若各种取值出现的概率都相等,即都是1/m,则H(Y)取最大值log2m。
   给定数据集D,假定D中第i类样本所占的比例为Pi(i=1,2,...,|y|)
   假定样本属性均为离散型,对属性子集A,假定根据其取值将D分成了V个子集
   假设每个属性有V个可能取值,则
   
5_信息增益.png

   这可能是一个很大的值,因此实践过程中通常是从子集搜索过程中前一轮属性子集的评价值出发来进行计算。{D1,D2,D3,D4,…,Dv}
   每个子集上的样本在A上取值相同,于是我们可计算属性子集A的信息增益
   
   
6_信息增益.png
 
   其中信息熵定义为
   
7_信息增益.png

    
   信息增益Gain(A)越大,意味着特征子集A包含的有助于分类的信息越多。于是,对每个候选子集,我们可基于训练数据集D来计算其信息增益,以此作为评价准则。
 
    特征子集A实际上确定了对数据集D上的一个划分,每个划分区域对应着A上的一个取值,而样本标记信息Y则对应着对D的真实划分,通过估算这两个划分的差异,就能对A进行评价。与Y对应的划分的差异越小,则说明A越好,信息熵仅是判断这个差异的一种途径,其他能判断两个划分差异的机制都能用于特征子集评价。
 
 (4)一致性( Consistency )
    若样本1与样本2属于不同的分类,但在特征A、 B上的取值完全一样,那么特征子集{A,B}不应该选作最终的特征集。
 (5)分类器错误率 (Classifier error rate ) 
    使用特定的分类器,用给定的特征子集对样本集进行分类,用分类的精度来衡量特征子集的好坏。
    
    以上5种度量方法中,相关性、距离、信息增益、一致性属于筛选器,而分类器错误率属于封装器。

4.分类
  将特征子集搜索机制与子集评价机制相结合,即可得到特征选择方法。常见的特征选择方法可分为三类:
过滤式(filter),包裹式(wrapper),嵌入式(embedding)

(1)过滤式选择

       先对数据集进行特征选择,然后再训练学习器,特征学习过程与后续学习器无关,这相当于先用特征选择过程对初始特征进行过滤,再用过滤后的特征来训练模型。

    8过滤式原理.png

    图2 Filter原理(Ricardo Gutierrez-Osuna 2008 ) 
    (2)包裹式选择
       与过滤式特征选择不考虑后续学习器不同,包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之,包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
        一般而言,包裹式直接针对给定学习器优化,从最终学习器性能来看,比过滤式更好,另一方面,由于在特征选择过程中需要多次训练学习器,因而计算开销通常比过滤式大得多。

    9包裹式原理.png

    图3. Wrapper原理 (Ricardo Gutierrez-Osuna 2008 )
    (3)嵌入式选择与L1正则化
       将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。

    5.参考文献
    [1]姚旭, 王晓丹, 张玉玺, 等. 特征选择方法综述[J]. 控制与决策, 2012, 27(2): 161-166.
    [2] 苍梧.特征选择常用算法综述
    http://www.cnblogs.com/heaad/a ... .html
    [3] 周志华.《机器学习》,清华大学出版社
    [4] http://www.cnblogs.com/heaad/a ... .html 

     

    #专题分享会第二期# word2vec

    王腾飞 发表了文章 • 0 个评论 • 116 次浏览 • 2016-11-10 13:51 • 来自相关话题

    词嵌入(word embedding)就是指得到distributed representation形式的词向量。
    词嵌入与one-hot编码
    传统one-hot编码(“天气”: (1,0,0…,0),“气候”: (0,1,0,…0) )
    维度高(几千–几万维稀疏向量),数据稀疏
    难以计算词之间相似度
    难以做模糊匹配
    词嵌入
    维度低(100 –500维)
    连续向量,方便机器学习模型处理
    无监督学习,不需去掉停用词(stopwords)
    天然有聚类后的效果
    罕见词:“风姿绰约”≈“漂亮”
     
    在NLP中,词向量的one-hot representation(1个维度是1,其余维度是0),与之不同的是,word2vec得到的词向量是distributed representation,维度在数百维左右,含有更丰富的语义信息,各个维度都是实数(不一定是0),此时可以用两个词向量的cos距离表示两个词向量的相似度。如果训练效果很好,可以达到如下的效果
      v(“国王”)表示国王的词向量
      v(“国王”) –v(“王后”)≈v(“男”) –v(“女”)
     
     

    word2vec 是 Google 于 2013 年开源推出的一个用于获取 word vector 的工具包,它简单、高效,因此引起了很多人的关注。
    Word2Vec的学习任务:
    对于每一个word(该word未知),使用该word周围的word来预测当前word生成的概率。(对应CBOW模型)
    对于每一个word(该word已知),使用该word本身来预测生成其他word的概率。(对应skim-gram模型)
    两个任务共同的限制条件是:对于相同的输入,输出每个可能的word的概率之和为1。
    在这个学习的过程中,副产物是词向量。这其实是最重要的。
     
     
    word2vec含单隐层神经网络。具体的训练过程参见下面链接(实在很复杂,我就偷懒用别人的博客)
    http://blog.csdn.net/itplus/article/details/37969519
    这是一个系列,链接指向该系列的第一篇。
     
    http://blog.csdn.net/mytestmy/article/details/26961315
    http://blog.csdn.net/mytestmy/article/details/26969149 
    这是另一个博主的博客,有2篇。 查看全部
    词嵌入(word embedding)就是指得到distributed representation形式的词向量。
    词嵌入与one-hot编码
    传统one-hot编码(“天气”: (1,0,0…,0),“气候”: (0,1,0,…0) )
    维度高(几千–几万维稀疏向量),数据稀疏
    难以计算词之间相似度
    难以做模糊匹配
    词嵌入
    维度低(100 –500维)
    连续向量,方便机器学习模型处理
    无监督学习,不需去掉停用词(stopwords)
    天然有聚类后的效果
    罕见词:“风姿绰约”≈“漂亮”
     
    在NLP中,词向量的one-hot representation(1个维度是1,其余维度是0),与之不同的是,word2vec得到的词向量是distributed representation,维度在数百维左右,含有更丰富的语义信息,各个维度都是实数(不一定是0),此时可以用两个词向量的cos距离表示两个词向量的相似度。如果训练效果很好,可以达到如下的效果
      v(“国王”)表示国王的词向量
      v(“国王”) –v(“王后”)≈v(“男”) –v(“女”)
     
     

    word2vec 是 Google 于 2013 年开源推出的一个用于获取 word vector 的工具包,它简单、高效,因此引起了很多人的关注。
    Word2Vec的学习任务:
    对于每一个word(该word未知),使用该word周围的word来预测当前word生成的概率。(对应CBOW模型)
    对于每一个word(该word已知),使用该word本身来预测生成其他word的概率。(对应skim-gram模型)
    两个任务共同的限制条件是:对于相同的输入,输出每个可能的word的概率之和为1。
    在这个学习的过程中,副产物是词向量。这其实是最重要的。
     
     
    word2vec含单隐层神经网络。具体的训练过程参见下面链接(实在很复杂,我就偷懒用别人的博客)
    http://blog.csdn.net/itplus/article/details/37969519
    这是一个系列,链接指向该系列的第一篇。
     
    http://blog.csdn.net/mytestmy/article/details/26961315
    http://blog.csdn.net/mytestmy/article/details/26969149 
    这是另一个博主的博客,有2篇。

    #专题分享会第一期# 梯度提升(Gradient Boosting)

    王开新 发表了文章 • 1 个评论 • 83 次浏览 • 2016-11-04 18:28 • 来自相关话题

    例行转载
    http://keson96.github.io/2016/11/04/2016-11-04-Gradient-Boosting/

    #专题分享会第一期# LARS与Lasso和Forward Stagewise

    王开新 发表了文章 • 0 个评论 • 79 次浏览 • 2016-10-28 11:38 • 来自相关话题

    http://keson96.github.io/2016/10/28/lars&lasso&stagewise/
    例行转载
     

    最小角回归(Least Angle Regression)

    王开新 发表了文章 • 0 个评论 • 96 次浏览 • 2016-10-26 22:20 • 来自相关话题

    http://keson96.github.io/2016/10/26/2016-10-26-Least-Angle-Regression/
     
    例行转载
    话说LARS真的好难好难,看了很久
    http://keson96.github.io/2016/10/26/2016-10-26-Least-Angle-Regression/
     
    例行转载
    话说LARS真的好难好难,看了很久

    #专题分享会第一期# EM算法的应用与关键步骤分析

    李新春 发表了文章 • 0 个评论 • 139 次浏览 • 2016-10-15 23:02 • 来自相关话题

        EM算法由两步组成,E-step求期望(expectation),与M-step求极大(maximization),故EM算法就是期望极大算法(expectation maximization)。有的概率模型既含有观测变量,也含有隐变量。假设概率模型只含有观测变量的话,只要给定训练集,就可以使用极大似然估计等方法估计模型参数,但是如果含有隐变量的话,那么利用这些方法将是不可行的。所以EM算法就是含有隐变量的概率模型参数的极大似然估计,或极大后验概率估计法。
        所以下面先介绍什么是隐变量,这将是理解EM算法的关键前提。下面给出两个例子具体说明什么是隐变量。其中例1出自斯坦福大学公开课,例2出自李航《统计学习方法》第9章。
        例1:给定如下图的训练集合,‘X’和‘O’代表两类的标签,分别代表1和0。因为给定了模型的标签,所以对这两类用高斯判别分析模型来建模,即得到了以下模型:




       即y服从伯努利分布,x|y=0和x|y=1这两类分别服从一个高斯分布,习惯上取二者的协方差相同,均值不同。对该模型利用极大似然估计等方法进行求解得到优化参数,进而得到的判别模型的图形如下:




      从上图,若给出一个新的样例x=10.5的话,则可以看出x=10.5属于类‘X’的概率远大于属于‘O’的概率,表现在图中即为在10.5处,红色线在蓝色线上方。这样在给定训练集(有标签)之后就可以利用高斯判别分析完成对已有数据的建模以及对新数据的预测。但是假设该题目的训练集中事先没有给出标签呢?这样可以利用高斯混合模型对数据进行建模,其中求解过程就用到了EM算法。
      在这个例子中,我们发现训练集只是由x组成,并没有输出结果,这种过程属于无监督学习,所以EM算法在无监督学习中的应用十分广泛。其重要程度和logistic回归、贝叶斯估计与支持向量机一样重要。
      例2:(三硬币模型)假设有3枚硬币,分别是A、B、C,抛掷硬币出现正面的概率分别为π,p,q。现在进行如下实验:先抛掷硬币A,根据其结果选择抛掷B或C,正面选择B,反面选择C;然后抛掷硬币,记录结果,正面为1,反面为0;进行n=10次实验,观测结果如下:1,1,0,1,0,0,1,0,1,1。假设只能观测到抛掷硬币的最后结果,不能看到过程,试着估计三硬币正面出现的概率,即参数π,p,q。
      问题分析:首先,如果结果除了给出n=10次抛掷B或C硬币的正反结果,还给出了在这之前抛掷硬币A的结果,比如假设有如下表格:




      表格第一行代表了投掷A的结果,1为正,0为反。下面两行给出了对应的投掷B或C的结果。根据贝叶斯估计不难估计出π=2/10=0.2,p=1/2=0.5,q=5/8=0.615。
      但是题目中并没有给出最终结果序列对应的抛掷A的结果,即A的抛掷结果被“隐藏”了,那么这种情况下该如何对问题进行分析?这就是EM算法应用之处。
      总结以上的例子可以了解到什么是隐变量,有无隐变量的两类问题之间的差别,以及EM算法的应用。下面正式介绍EM算法的具体步骤。
      EM算法具体步骤:问题简述为P(X,Z; theta)是要求解的模型,X为输入,Z为隐变量,theta为所要优化的参数,给定训练集(样本数目为m),利用极大似然估计得到目标优化函数为:




      直接对以上函数求偏导求极值是一件很困难的事情,故这里就利用放缩的方法将该函数放缩为一个稍微小于该函数的函数g,g可以很容易得到最优值,找到最优值后更新参数 theta。然后重复利用这个过程即可得到原来似然函数的最优值的近似。将该过程用图表示如下:




      对上图的详细解释如下:横坐标代表参数theta,假设题目中所要优化的原函数的形状为曲线L,初始迭代的值为 theta1,此时选取一个函数来近似原函数,曲线如图L1,L与L1交于点A,然后对函数L1求极大,得到极大值对应的横坐标theta2,然后在 处再利用一个函数L2进行近似L,如此迭代可得最优参数theta3…最终将得到近似最优的参数解。
    介绍完EM算法的基本思想后,来介绍具体的EM算法步骤:
      E-step: 对每一个i=1,2,…,m,重复如下步骤:




      M-step: 更新参数 的值:




      EM算法的详细推导过程和具体公式请参见斯坦福大学公开课与《统计学习方法》第九章,其中在EM算法的推导过程中用到了Jenson不等式和相关概率论知识,希望阅读本文章的读者去了解相关内容。
     
    参考文献:
    [1] 斯坦福大学公开课(链接:斯坦福大学公开课
    http://open.163.com/special/op ... .html)
    [2] 李航.统计学习方法[M].北京: 清华大学出版社 ,2013:155-165
      查看全部
        EM算法由两步组成,E-step求期望(expectation),与M-step求极大(maximization),故EM算法就是期望极大算法(expectation maximization)。有的概率模型既含有观测变量,也含有隐变量。假设概率模型只含有观测变量的话,只要给定训练集,就可以使用极大似然估计等方法估计模型参数,但是如果含有隐变量的话,那么利用这些方法将是不可行的。所以EM算法就是含有隐变量的概率模型参数的极大似然估计,或极大后验概率估计法。
        所以下面先介绍什么是隐变量,这将是理解EM算法的关键前提。下面给出两个例子具体说明什么是隐变量。其中例1出自斯坦福大学公开课,例2出自李航《统计学习方法》第9章。
        例1:给定如下图的训练集合,‘X’和‘O’代表两类的标签,分别代表1和0。因为给定了模型的标签,所以对这两类用高斯判别分析模型来建模,即得到了以下模型:
    1.png

       即y服从伯努利分布,x|y=0和x|y=1这两类分别服从一个高斯分布,习惯上取二者的协方差相同,均值不同。对该模型利用极大似然估计等方法进行求解得到优化参数,进而得到的判别模型的图形如下:
    2.png

      从上图,若给出一个新的样例x=10.5的话,则可以看出x=10.5属于类‘X’的概率远大于属于‘O’的概率,表现在图中即为在10.5处,红色线在蓝色线上方。这样在给定训练集(有标签)之后就可以利用高斯判别分析完成对已有数据的建模以及对新数据的预测。但是假设该题目的训练集中事先没有给出标签呢?这样可以利用高斯混合模型对数据进行建模,其中求解过程就用到了EM算法。
      在这个例子中,我们发现训练集只是由x组成,并没有输出结果,这种过程属于无监督学习,所以EM算法在无监督学习中的应用十分广泛。其重要程度和logistic回归、贝叶斯估计与支持向量机一样重要。
      例2:(三硬币模型)假设有3枚硬币,分别是A、B、C,抛掷硬币出现正面的概率分别为π,p,q。现在进行如下实验:先抛掷硬币A,根据其结果选择抛掷B或C,正面选择B,反面选择C;然后抛掷硬币,记录结果,正面为1,反面为0;进行n=10次实验,观测结果如下:1,1,0,1,0,0,1,0,1,1。假设只能观测到抛掷硬币的最后结果,不能看到过程,试着估计三硬币正面出现的概率,即参数π,p,q。
      问题分析:首先,如果结果除了给出n=10次抛掷B或C硬币的正反结果,还给出了在这之前抛掷硬币A的结果,比如假设有如下表格:
    3.png

      表格第一行代表了投掷A的结果,1为正,0为反。下面两行给出了对应的投掷B或C的结果。根据贝叶斯估计不难估计出π=2/10=0.2,p=1/2=0.5,q=5/8=0.615。
      但是题目中并没有给出最终结果序列对应的抛掷A的结果,即A的抛掷结果被“隐藏”了,那么这种情况下该如何对问题进行分析?这就是EM算法应用之处。
      总结以上的例子可以了解到什么是隐变量,有无隐变量的两类问题之间的差别,以及EM算法的应用。下面正式介绍EM算法的具体步骤。
      EM算法具体步骤:问题简述为P(X,Z; theta)是要求解的模型,X为输入,Z为隐变量,theta为所要优化的参数,给定训练集(样本数目为m),利用极大似然估计得到目标优化函数为:
    4.png

      直接对以上函数求偏导求极值是一件很困难的事情,故这里就利用放缩的方法将该函数放缩为一个稍微小于该函数的函数g,g可以很容易得到最优值,找到最优值后更新参数 theta。然后重复利用这个过程即可得到原来似然函数的最优值的近似。将该过程用图表示如下:
    5.png

      对上图的详细解释如下:横坐标代表参数theta,假设题目中所要优化的原函数的形状为曲线L,初始迭代的值为 theta1,此时选取一个函数来近似原函数,曲线如图L1,L与L1交于点A,然后对函数L1求极大,得到极大值对应的横坐标theta2,然后在 处再利用一个函数L2进行近似L,如此迭代可得最优参数theta3…最终将得到近似最优的参数解。
    介绍完EM算法的基本思想后,来介绍具体的EM算法步骤:
      E-step: 对每一个i=1,2,…,m,重复如下步骤:
    6.png

      M-step: 更新参数 的值:
    7.png

      EM算法的详细推导过程和具体公式请参见斯坦福大学公开课与《统计学习方法》第九章,其中在EM算法的推导过程中用到了Jenson不等式和相关概率论知识,希望阅读本文章的读者去了解相关内容。
     
    参考文献:
    [1] 斯坦福大学公开课(链接:斯坦福大学公开课
    http://open.163.com/special/op ... .html
    [2] 李航.统计学习方法[M].北京: 清华大学出版社 ,2013:155-165