#机器学习# 文章列表 浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

梯度下降法


#机器学习#


2014-09-18

偏导数与梯度

有时候,遇到的数学公式会有多个变量,例如:

[latex]
f(x,y) = x+x^2+y^2 [/latex]

将变量y看做常量,对x进行求导,可得:

[latex]
1+2x [/latex]

这个结果可以就是f(x,y)关于x的偏导数,可以写成:

[latex]
\frac{\partial f}{\partial x} = 1+2x [/latex]

同理,可以得到f(x,y)关于y的偏导数: [latex]
\frac{\partial f}{\partial y} = 2y [/latex]

我们画一下f(x,y)的mesh图:

%% matlab
x=-10:0.1:10;
y=x;
[X,Y]=meshgrid(x,y);
Z = X + X.^2 +Y.^2;
mesh(X,Y,Z);
xlabel('x');
ylabel('y');
zlabel('z');

结果如下:

说白了,偏导数就是斜率。以点(x,y,z)=(1,1,3)为例,我们找到过点(1,1,3)且与x轴、z轴都平行的那个唯一的平面,曲面f(x,y)与这个平面相交得到一曲线。这个曲线在y=1处的斜率就是f(x,y)在点(1,1)处关于y的偏导数的值。

如果把f(x,y)这个多元函数退化成一元函数f(x),只能得到一个偏导数,且就是斜率。

将[latex]\frac{\partial f}{\partial x}[/latex]和[latex]\frac{\partial f}{\partial y}[/latex]整合起来,称作梯度

梯度指明了局部范围内在哪个方向上函数增长最快,可以用来快速的得到局部最大值/最小值。

梯度上升和梯度下降

换个抛物线函数作为示例: [latex]
f(x) = x^2 [/latex]

有: [latex]
\frac{\partial f}{\partial x} = 2x [/latex]

plot下f(x):

当x=2时,f(x)=4,对于这个点,关于x的偏导数的值为4,即梯度为4,也就是说如果x沿着+4的方向改变,那么f(x)的值将增大,这就是梯度上升;相反,如果x沿着-4的方向改变,那么f(x)的值将减小,这意味着我们可以通过这种方式来得到f(x)的最小值以及相应的x,这就是梯度下降和它的意义。当然,如果将f(x)关于x轴反过来,梯度上升可以帮助我们得到最大值。

现在只说梯度下降。一般,开始时随机地选择一个种子点,从这个种子点开始,种子点沿着其梯度的相反方向下降。下降的方向是可以求的,下降的程度(即“步长”)需要根据经验指定,例如x下降的方向是-4,步长可以是0.1,于是x会由2变成2-0.1*4=1.6。这个过程需要重复多次,当觉得已经达到最小值的目标时,就可以结束了。可以通过下面的方法判断是否达到目标:

  1. 迭代次数达到指定的值。
  2. 相邻的两次的结果达到某个可以允许的误差范围。
  3. 下一次的运行结果大于这一次的运行结果。
  4. 梯度非常接近0时。

下面理一下[latex]f(x) = x^2[/latex]使用梯度下降法时迭代的过程(假定步长一直为0.1):

  1. x=2,梯度为2*2=4。
  2. x=2-0.1*4 = 1.6,梯度为2*1.6 = 3.2。
  3. x = 1.6 - 0.1*3.2 = 1.28,梯度为2*1.28 = 2.56。
  4. ……

注意,考虑到一个函数可能有多个极小值/极大值,以及种子点是随机选取的,用梯度上升/下降法得到的结果只能说是局部最优。

梯度下降也可以用来解非线性函数,请移步http://en.wikipedia.org/wiki/Gradient_descent

使用梯度下降法训练线性单元

假设在一个平面上有两类点,可以用一条直线将它们划分开来,那么如何求这根直线?如果是高维空间中有两类点可以用一个超平面(类似二维空间的线)区分开,如何求这个超平面?

在二维空间中,直线的表达式是:
[latex]
w_{1}x_{1}+w_{2}x_{2}+b = 0 [/latex] 其中,[latex]x_{1}, x_{2}[/latex]分别代表一个维度,[latex]w_{1}, w_{2}[/latex]是权重,b是偏置项,线性回归的目的是求得权重和偏置项。

将这个公式延伸到n维空间,就变成了寻找合适的超平面: 在二维空间中,直线的表达式是:
[latex]
w_{1}x_{1}+w_{2}x_{2}+...+w_{n}x_{n}+b = 0 [/latex]

假设我们将这些点所属的类分别叫做类+1和类-1,其实我们要找的就是这样一个函数:

[latex]
O(\vec{x}) = \vec{w}\vec{x} +b =\sum_{i=1}^{n}w_{i}x_{i} + b [/latex]

向量[latex]\vec{x}[/latex]代表n空间中的一个点。[latex]O(\vec{x})[/latex]若大于0,则认为[latex]\vec{x}[/latex]属于类+1的可能性较大,若小于0,则属于类-1的可能性较大。

令[latex]x_{0}=1, w_{0}=b[/latex],那么可以将上面的[latex]O(\vec{x})[/latex]简化为:

[latex]
O(\vec{x}) = \vec{w}\vec{x} +b =\sum_{i=0}^{n}w_{i}x_{i} [/latex]

这相当于给[latex]\vec{x}[/latex]增加了一个维度,且值都为1。

我们需要一个标准来衡量计算出的[latex]\vec{w}[/latex]的好坏,一般可以采用平方误差:

[latex]
E(\vec{w}) = \frac{1}{2}\sum_{d \in D}(t_{d}-o_{d})^2 [/latex]

D是数据集合,[latex]t_{d}[/latex]是点d的目标输出(即类别-1或者+1),[latex]o_{d}[/latex]则是我们计算出的类别(但这个类别可能是小数,例如0.2,代表更有可能是+1类)。很明显,上面的公式是关于向量[latex]\vec{w}[/latex]的二次函数,所以必然有一个确定的[latex]\vec{w}[/latex],是的平方误差最小。

在开始时,给权重向量中的每个权重一个随机值,接着,我们要找出这个向量的每个值应该沿着哪个梯度的负方向前进。

以[latex]w_{i}[/latex]为例:

[latex]
\frac{\partial E}{\partial w_{i}} \\
= \frac{\partial}{\partial w_{i}} [\frac{1}{2}\sum_{d \in D}(t_{d}-o_{d})^2] \\
= \frac{1}{2}\sum_{d \in D}\frac{\partial}{\partial w_{i}}(t_{d}-o_{d})^2 \\
= \frac{1}{2} \sum_{d \in D} 2 (t_{d}-o_{d}) \frac{\partial}{\partial w_{i}}(t_{d}-o_{d}) \\
= \sum_{d \in D}(t_{d}-o_{d}) \frac{\partial}{\partial w_{i}}(t_{d}-\vec{w} \vec{x}_{d}) \\
= \sum_{d \in D}(t_{d}-o_{d}) (-\vec{x}_{di}) [/latex]

其中,[latex]\vec{x}_{di}[/latex]是向量[latex]\vec{x}_{d}[/latex]的第i个分量,是一个标量。由上面的求导结果可以看出,对于[latex]w_{i}[/latex],要最小化[latex]E(\vec{w})[/latex],[latex]w_{i}[/latex]需要朝下面的方向前进:

[latex]
\sum_{d \in D}(t_{d}-o_{d})\vec{x}_{di} [/latex]

我们把已被分类的点记做[latex]<\vec{x}, t>[/latex],[latex]t[/latex]是[latex]\vec{x}[/latex]的类别(class),设步长为[latex]\eta[/latex],这里步长也可以叫做学习率。综上,可以得到相应的梯度下降算法:

// 梯度下降

将[latex]\vec{w}[/latex]中的每个权值[latex]w_{i}[/latex]取随机值;

WHILE 没有达到某个终止条件之前 DO {

    初始化每个[latex]\Delta w_{i}=0[/latex];

    FOR 每个已分类的数据点[latex]<\vec{x}, t>[/latex] DO {

        根据公式[latex]O(\vec{x}) = \sum_{i=0}^{n}w_{i}x_{i}[/latex],计算[latex]\vec{x}[/latex]的目标输出[latex]o[/latex];

        对于每个[latex]\Delta w_{i}[/latex],更新为[latex]\Delta w_{i}=\Delta w_{i}+\eta (t-o)x_{i}[/latex];

    }

    对每个[latex]\Delta w_{i}[/latex]进行更新,即[latex]w_{i} = w_{i} + \Delta w_{i}[/latex]

}

上面的梯度下降算法有两个问题:

1、收敛过程可能很慢 2、E(w)存在一个最小值,但也可能存在存在多个极小值,上面的算法不一定能找到最小值。

为了缓解上面提出的问题,可以使用增量梯度下降算法(也叫随机梯度下降算法):

//增量梯度下降

将[latex]\vec{w}[/latex]中的每个权值[latex]w_{i}[/latex]取随机值;

WHILE 没有达到某个终止条件之前 DO {

    FOR 每个已分类的数据点[latex]<\vec{x}, t>[/latex] DO {

        根据公式[latex]O(\vec{x}) = \sum_{i=0}^{n}w_{i}x_{i}[/latex],计算[latex]\vec{x}[/latex]的目标输出[latex]o[/latex];

        对于每个[latex]w_{i}[/latex],更新为[latex]w_{i}=w_{i}+\eta (t-o)x_{i}[/latex];

    }

}

注意:数据点的类别也可以使用其他数字表示,梯度下降也可以用于多类问题。


( 本文完 )