机器学习中的梯度下降法

来自: Datartisan数据工匠(微信号: shujugongjiang)

链接:http://datartisan.com/article/detail/99.html

最优化问题是机器学习算法中非常重要的一部分,几乎每一个机器学习算法的核心都是在处理最优化问题。

本文中我讲介绍一些机器学习领域中常用的且非常掌握的最优化算法,看完本篇文章后你将会明白:
  • 什么是梯度下降法?
  • 如何将梯度下降法运用到线性回归模型中?
  • 如何利用梯度下降法处理大规模的数据?
  • 梯度下降法的一些技巧

让我们开始吧!

梯度下降法
梯度下降法是一个用于寻找最小化成本函数的参数值的最优化算法。当我们无法通过分析计算(比如线性代数运算)求得函数的最优解时,我们可以利用梯度下降法来求解该问题。

梯度下降法的直觉体验

想象一个你经常用来吃谷物或储存受过的大碗,成本函数的形状类似于这个碗的造型。

碗表面上的任一随机位置表示当前系数对应的成本值,碗的底部则表示最优解集对应的成本函数值。梯度下降法的目标就是不断地尝试不同的系数值,然后评估成本函数并选择能够降低成本函数的参数值。重复迭代计算上述步骤直到收敛,我们就能获得最小成本函数值对应的最优解

梯度下降法的过程

梯度下降法首先需要设定一个初始参数值,通常情况下我们将初值设为零(coefficient=0coefficient=0),接下来需要计算成本函数 cost=f(coefficient)cost=f(coefficient) 或者 cost=evaluate(f(coefficient))cost=evaluate(f(coefficient))。然后我们需要计算函数的导数(导数是微积分的一个概念,它是指函数中某个点处的斜率值),并设定学习效率参数(alpha)的值。

coefficient=coefficient−(alpha∗delta) coefficient=coefficient−(alpha∗delta) 重复执行上述过程,直到参数值收敛,这样我们就能获得函数的最优解。

你可以看出梯度下降法的思路多么简单,你只需知道成本函数的梯度值或者需要优化的函数情况即可。接下来我将介绍如何将梯度下降法运用到机器学习领域中。

批量梯度下降法
所有的有监督机器学习算法的目标都是利用已知的自变量(X)数据来预测因变量(Y)的值。所有的分类和回归模型都是在处理这个问题。

机器学习算法会利用某个统计量来刻画目标函数的拟合情况。虽然不同的算法拥有不同的目标函数表示方法和不同的系数值,但是它们拥有一个共同的目标——即通过最优化目标函数来获取最佳参数值。
线性回归模型和逻辑斯蒂回归模型是利用梯度下降法来寻找最佳参数值的经典案例。
我们可以利用多种衡量方法来评估机器学习模型对目标函数的拟合情况。成本函数法是通过计算每个训练集的预测值和真实值之间的差异程度(比如残差平方和)来度量模型的拟合情况。
我们可以计算成本函数中每个参数所对应的导数值,然后通过上述的更新方程进行迭代计算。
在梯度下降法的每一步迭代计算后,我们都需要计算成本函数及其导数的情况。每一次的迭代计算过程就被称为一批次,因此这个形式的梯度下降法也被称为批量梯度下降法。

批量梯度下降法是机器学习领域中常见的一种梯度下降方法。

随机梯度下降法
处理大规模的数据时,梯度下降法的运算效率非常低。

因为梯度下降法在每次迭代过程中都需要计算训练集的预测情况,所以当数据量非常大时需要耗费较长的时间。
当你处理大规模的数据时,你可以利用随机梯度下降法来提高计算效率。
该算法与上述梯度下降法的不同之处在于它对每个随机训练样本都执行系数更新过程,而不是在每批样本运算完后才执行系数更新过程。
随机梯度下降法的第一个步骤要求训练集的样本是随机排序的,这是为了打乱系数的更新过程。因为我们将在每次训练实例结束后更新系数值,所以系数值和成本函数值将会出现随机跳跃的情况。通过打乱系数更新过程的顺序,我们可以利用这个随机游走的性质来避免模型不收敛的问题。
除了成本函数的计算方式不一致外,随机梯度下降法的系数更新过程和上述的梯度下降法一模一样。

对于大规模数据来说,随机梯度下降法的收敛速度明显高于其他算法,通常情况下你只需要一个小的迭代次数就能得到一个相对较优的拟合参数。

梯度下降法的一些建议
本节列出了几个可以帮助你更好地掌握机器学习中梯度下降算法的技巧:

  • 绘制成本函数随时间变化的曲线:收集并绘制每次迭代过程中所得到的成本函数值。对于梯度下降法来说,每次迭代计算都能降低成本函数值。如果无法降低成本函数值,那么可以尝试减少学习效率值。
  • 学习效率:梯度下降算法中的学习效率值通常为0.1,0.001或者0.0001。你可以尝试不同的值然后选出最佳学习效率值。
  • 标准化处理:如果成本函数不是偏态形式的话,那么梯度下降法很快就能收敛。隐蔽你可以事先对输入变量进行标准化处理。
  • 绘制成本均值趋势图:随机梯度下降法的更新过程通常会带来一些随机噪声,所以我们可以考虑观察10次、100次或1000次更新过程误差均值变化情况来度量算法的收敛趋势。
总结 
本文主要介绍了机器学习中的梯度下降法,通过阅读本文,你了解到:

  • 最优化理论是机器学习中非常重要的一部分。
  • 梯度下降法是一个简单的最优化算法,你可以将它运用到许多机器学习算法中。
  • 批量梯度下降法先计算所有参数的导数值,然后再执行参数更新过程。
  • 随机梯度下降法是指从每个训练实例中计算出导数并执行参数更新过程。

计算几何常用算法,ACM竞赛必备~

来自2010年百度文库

原作者不详

1、矢量减法

设二维矢量 P = (x1,y1) ,Q = (x2,y2)
则矢量减法定义为: P – Q = ( x1 – x2 , y1 – y2 )
显然有性质 P – Q = – ( Q – P )
如不加说明,下面所有的点都看作矢量,两点的减法就是矢量相减;

2、矢量叉积

设矢量P = (x1,y1) ,Q = (x2,y2)
则矢量叉积定义为: P × Q = x1*y2 – x2*y1   得到的是一个标量
显然有性质 P × Q = – ( Q × P )   P × ( – Q ) = – ( P × Q )
如不加说明,下面所有的点都看作矢量,点的乘法看作矢量叉积;
叉乘的重要性质:
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向 > 若 P × Q = 0 , 则P 与Q共线,但可能同向也可能反向

3、判断点在线段上

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:
( Q – P1 ) × ( P2 – P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内

4、判断两线段是否相交

我们分两步确定两条线段是否相交:

(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相
交,显然两线段不会相交;

(2)跨立试验
如果两线段相交,则两线段必然相互跨立对方,如图1所示。在图1中,P1P2跨立Q1Q2 ,则
矢量 ( P1 – Q1 ) 和( P2 – Q1 )位于矢量( Q2 – Q1 ) 的两侧,即
( P1 – Q1 ) × ( Q2 – Q1 ) * ( P2 – Q1 ) × ( Q2 – Q1 ) < 0 上式可改写成 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当 ( P1 – Q1 ) × ( Q2 – Q1 ) = 0 时,说明   ( P1 – Q1 ) 和 ( Q2 – Q1 )共线,

但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 – Q1 ) ×(
P2 – Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是:
( Q1 – P1 ) × ( P2 – P1 ) * ( P2 – P1 ) × ( Q2 – P1 ) ≥ 0
至此已经完全解决判断线段是否相交的问题。

5、判断线段和直线是否相交

如果线段 P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0

6、判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中
因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

6、判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

7、判断圆是否在矩形中

圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最
小值。

8、判断点是否在多边形中

以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,
考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多
边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的
交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交,有些情况下交点只能计算一个
,有些情况下交点不应被计算(你自己画个图就明白了);如果L和多边形的一条边重合,
这条边应该被忽略不计。为了统一起见,我们在计算射线L和多边形的交点的时候,1。对
于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属
的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判
断P属于多边行。由此得出算法的伪代码如下:

1、count ← 0;
2、以P为端点,作从右向左的射线L;
3、for 多边形的每条边s
4、do if P在边s上
5、then return true;
6、if s不是水平的
7、then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9、then count ← count+1
10、else if s和L相交
11、then count ← count+1;
12i、f count mod 2 = 1
13、then return true
14、else return false;

其中做射线L的方法是:设P’的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),
则P和P’就确定了射线L。这个算法的复杂度为O(n)。

9、判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内;
如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点)
,因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交

线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个
顶点和线段相交,还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序,这样相邻的两个点就是
在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形
内。证明如下:
命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P’ 也在多边形内,则P1, P2之间的所有点
都在多边形内。
证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P’之间,因为多边形是闭
合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P’属于多边性
内部,P1-Q-P’完全连续,所以P1Q和QP’一定跨越多边形的边界,因此在P1,P’之间至少还
有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕
由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多
边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多
边形内。

在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若
线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内
交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段
上就可以了。
至此我们得出算法如下:
1、f 线端PQ的端点不都在多边形内
2、hen return false;
3、点集pointSet初始化为空;
4、for 多边形的每条边s
5、do if 线段的某个端点在s上
6、then 将该端点加入pointSet;
7、else if s的某个端点在线段PQ上
8、then 将该端点加入pointSet;
9、else if s和线段PQ相交           // 这时候可以肯定是内交
10、 then return false;
11、将pointSet中的点按照X-Y坐标排序,X坐标小的排在前面,对于X坐标相同的点,Y坐
标小的排在前面;
12、for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13、do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14、then return false;
15、return true;

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n,所
以最多是常数级的复杂度,几乎可以忽略不计。

10、判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,
则复杂度为O(m*n)。

11、判断多边形是否在多边形内
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个
有n个顶点的多边形内复杂度为O(m*n)。

12、判断矩形是否在多边形内

将矩形转化为多边形,然后再判断是否在多边形内。

13、判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形
内。计算圆心到多边形每条边最短距离的算法在后文阐述。

14、判断点是否在圆内

计算圆心到该点的距离,如果小于等于半径则该点在圆内。

15、判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

16、判断圆是否在圆内

设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r
117、计算点到线段的最近点

如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,
然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;
如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt
2,斜率为:
k = ( pt2.y – pt1. y ) / (pt2.x – pt1.x );
该直线方程为:
y = k* ( x – pt1.x) + pt1.y
其垂线的斜率为 – 1 / k,
垂线方程为:
y = (-1/k) * (x – point.x) + point.y
联立两直线方程解得:
x = ( k^2 * pt1.x + k * (point.y – pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x – pt1.x) + pt1.y;
然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足
的距离,选择距离垂足较近的端点返回。

18、计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

19、计算点到圆的最近距离
如果该点在圆心,则返回UNDEFINED
连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为
centerPoint.x – radius 或 centerPoint.x + radius, 如图4 (a)所示;如果如果PO平
行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius
或 centerPoint.y – radius, 如图4 (b)所示。
如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,如图4(c)所示。这时直线PO斜率为

k = ( P.y – O.y )/ ( P.x – O.x )
直线PO的方程为:
y = k * ( x – P.x) + P.y
设圆方程为:
(x – O.x ) ^2 + ( y – O.y ) ^2 = r ^2,
联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

20、计算两条共线的线段的交点

对于两条共线的线段,它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点;图5 (b) 和 (d) 中两条线段有无穷焦点;图5 (c) 中两条线
段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了
line2的两个端点,则是图5(d)的情况,两线段有无穷交点;如果line1只包含line2的一个
端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图5(c)的情况
,这时两线段只有一个交点,否则就是图5(c)的情况,两线段也是有无穷的交点;如果li
ne1不包含line2的任何端点,则是图5(a)的情况,这时两线段没有交点。

21、计算线段或直线与线段的交点
设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

1、首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说
明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。
2、如果P1和P2横坐标相同,即L0平行于Y轴
a) 若L1也平行于Y轴,
i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交
点纵坐标;
3、如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q
1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;
4、如果P1和P2纵坐标相同,即L0平行于X轴
a) 若L1也平行于X轴,
i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交
点横坐标;
5、如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q
1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;
6、剩下的情况就是L1和L0的斜率均存在且不为0的情况
a) 计算出L0的斜率K0,L1的斜率K1 ;
b) 如果K1 = K2
i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话
可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c) 联立两直线的方程组可以解出交点来

说明:这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单
独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉
乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部
看作直线来考虑。

22、求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

23、求线段或直线与圆的交点

设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。
1、如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步
2、如果L平行于Y轴,
a) 计算圆心到L的距离dis
b) 如果dis > r 则L和圆没有交点;
c) 利用勾股定理,可以求出两交点坐标,如图6(a)所示;但要注意考虑L和圆的相切情况
3、如果L平行于X轴,做法与L平行于Y轴的情况类似;
4、如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;
5、如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

旧金山大学数据结构和算法的可视化学习工具

来源:伯乐在线 – 资源频道

链接:http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

 

简介

理解复杂数据结构的最佳方法就是看它们的实际操作。旧金山大学计算机系的助理教授  David Galles  在 2011 年开发了一套用于学习数据结构和算法的交互工具。这个可视化工具是用 JavaScript 编写,用上了 HTML5 画布元素,兼容所有现代浏览器。iPhone 和 iPad 等 iOS 设备和 Kindle 上的浏览器都支持。

(编注:建议在非手机设备上使用,这个工具并不是自适应的,屏幕过小不利于操作和查看。)

 

如何使用

以链表队列为例,进入网页后,上方有一个操作按钮的工具栏。最左侧可输入队列元素,然后进行入队(Enqueue)和出队(Dequeue)操作。

下方是另外一个操作按钮的工具栏,用于设置动画参数等操作。

其他

这个工具的源码已公开,感兴趣的计算机课程教师,请参阅这个网页,然后可基于 David 的代码编写自己的教程动画。

官方网站:http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一文读懂机器学习,大数据/自然语言处理/算法全有了

来自: 计算机的潜意识 – 博客园

链接:http://www.cnblogs.com/subconscious/p/4107357.html

在本篇文章中,我将对机器学习做个概要的介绍。本文的目的是能让即便完全不了解机器学习的人也能了解机器学习,并且上手相关的实践。这篇文档也算是EasyPR开发的番外篇,从这里开始,必须对机器学习了解才能进一步介绍EasyPR的内核。当然,本文也面对一般读者,不会对阅读有相关的前提要求。

在进入正题前,我想读者心中可能会有一个疑惑:机器学习有什么重要性,以至于要阅读完这篇非常长的文章呢?

我并不直接回答这个问题前。相反,我想请大家看两张图,下图是图一:

图1 机器学习界的执牛耳者与互联网界的大鳄的联姻

这幅图上上的三人是当今机器学习界的执牛耳者。中间的是Geoffrey Hinton, 加拿大多伦多大学的教授,如今被聘为“Google大脑”的负责人。右边的是Yann LeCun, 纽约大学教授,如今是Facebook人工智能实验室的主任。而左边的大家都很熟悉,Andrew Ng,中文名吴恩达,斯坦福大学副教授,如今也是“百度大脑”的负责人与百度首席科学家。这三位都是目前业界炙手可热的大牛,被互联网界大鳄求贤若渴的聘请,足见他们的重要性。而他们的研究方向,则全部都是机器学习的子类–深度学习。

下图是图二:

图2 语音助手产品

这幅图上描述的是什么?Windows Phone上的语音助手Cortana,名字来源于《光环》中士官长的助手。相比其他竞争对手,微软很迟才推出这个服务。Cortana背后的核心技术是什么,为什么它能够听懂人的语音?事实上,这个技术正是机器学习。机器学习是所有语音助手产品(包括Apple的siri与Google的Now)能够跟人交互的关键技术。

通过上面两图,我相信大家可以看出机器学习似乎是一个很重要的,有很多未知特性的技术。学习它似乎是一件有趣的任务。实际上,学习机器学习不仅可以帮助我们了解互联网界最新的趋势,同时也可以知道伴随我们的便利服务的实现技术。

机器学习是什么,为什么它能有这么大的魔力,这些问题正是本文要回答的。同时,本文叫做“从机器学习谈起”,因此会以漫谈的形式介绍跟机器学习相关的所有内容,包括学科(如数据挖掘、计算机视觉等),算法(神经网络,svm)等等。本文的主要目录如下:

1、一个故事说明什么是机器学习

2、机器学习的定义

3、机器学习的范围

4、机器学习的方法

5、机器学习的应用–大数据

6、机器学习的子类–深度学习

7、机器学习的父类–人工智能

8、机器学习的思考–计算机的潜意识

9、总结

10、后记

1、一个故事说明什么是机器学习

机器学习这个词是让人疑惑的,首先它是英文名称Machine Learning(简称ML)的直译,在计算界Machine一般指计算机。这个名字使用了拟人的手法,说明了这门技术是让机器“学习”的技术。但是计算机是死的,怎么可能像人类一样“学习”呢?

传统上如果我们想让计算机工作,我们给它一串指令,然后它遵照这个指令一步步执行下去。有因有果,非常明确。但这样的方式在机器学习中行不通。机器学习根本不接受你输入的指令,相反,它接受你输入的数据! 也就是说,机器学习是一种让计算机利用数据而不是指令来进行各种工作的方法。这听起来非常不可思议,但结果上却是非常可行的。“统计”思想将在你学习“机器学习”相关理念时无时无刻不伴随,相关而不是因果的概念将是支撑机器学习能够工作的核心概念。你会颠覆对你以前所有程序中建立的因果无处不在的根本理念。

下面我通过一个故事来简单地阐明什么是机器学习。这个故事比较适合用在知乎上作为一个概念的阐明。在这里,这个故事没有展开,但相关内容与核心是存在的。如果你想简单的了解一下什么是机器学习,那么看完这个故事就足够了。如果你想了解机器学习的更多知识以及与它关联紧密的当代技术,那么请你继续往下看,后面有更多的丰富的内容。

这个例子来源于我真实的生活经验,我在思考这个问题的时候突然发现它的过程可以被扩充化为一个完整的机器学习的过程,因此我决定使用这个例子作为所有介绍的开始。这个故事称为“等人问题”。

我相信大家都有跟别人相约,然后等人的经历。现实中不是每个人都那么守时的,于是当你碰到一些爱迟到的人,你的时间不可避免的要浪费。我就碰到过这样的一个例子。

对我的一个朋友小Y而言,他就不是那么守时,最常见的表现是他经常迟到。当有一次我跟他约好3点钟在某个麦当劳见面时,在我出门的那一刻我突然想到一个问题:我现在出发合适么?我会不会又到了地点后,花上30分钟去等他?我决定采取一个策略解决这个问题。

要想解决这个问题,有好几种方法。第一种方法是采用知识:我搜寻能够解决这个问题的知识。但很遗憾,没有人会把如何等人这个问题作为知识传授,因此我不可能找到已有的知识能够解决这个问题。第二种方法是问他人:我去询问他人获得解决这个问题的能力。但是同样的,这个问题没有人能够解答,因为可能没人碰上跟我一样的情况。第三种方法是准则法:我问自己的内心,我有否设立过什么准则去面对这个问题?例如,无论别人如何,我都会守时到达。但我不是个死板的人,我没有设立过这样的规则。

事实上,我相信有种方法比以上三种都合适。我把过往跟小Y相约的经历在脑海中重现一下,看看跟他相约的次数中,迟到占了多大的比例。而我利用这来预测他这次迟到的可能性。如果这个值超出了我心里的某个界限,那我选择等一会再出发。假设我跟小Y约过5次,他迟到的次数是1次,那么他按时到的比例为80%,我心中的阈值为70%,我认为这次小Y应该不会迟到,因此我按时出门。如果小Y在5次迟到的次数中占了4次,也就是他按时到达的比例为20%,由于这个值低于我的阈值,因此我选择推迟出门的时间。这个方法从它的利用层面来看,又称为经验法。在经验法的思考过程中,我事实上利用了以往所有相约的数据。因此也可以称之为依据数据做的判断。

依据数据所做的判断跟机器学习的思想根本上是一致的。刚才的思考过程我只考虑“频次”这种属性。在真实的机器学习中,这可能都不算是一个应用。一般的机器学习模型至少考虑两个量:一个是因变量,也就是我们希望预测的结果,在这个例子里就是小Y迟到与否的判断。另一个是自变量,也就是用来预测小Y是否迟到的量。假设我把时间作为自变量,譬如我发现小Y所有迟到的日子基本都是星期五,而在非星期五情况下他基本不迟到。于是我可以建立一个模型,来模拟小Y迟到与否跟日子是否是星期五的概率。见下图:

图3 决策树模型

这样的图就是一个最简单的机器学习模型,称之为决策树。当我们考虑的自变量只有一个时,情况较为简单。如果把我们的自变量再增加一个。例如小Y迟到的部分情况时是在他开车过来的时候(你可以理解为他开车水平较臭,或者路较堵)。于是我可以关联考虑这些信息。建立一个更复杂的模型,这个模型包含两个自变量与一个因变量。

再更复杂一点,小Y的迟到跟天气也有一定的原因,例如下雨的时候,这时候我需要考虑三个自变量。

如果我希望能够预测小Y迟到的具体时间,我可以把他每次迟到的时间跟雨量的大小以及前面考虑的自变量统一建立一个模型。于是我的模型可以预测值,例如他大概会迟到几分钟。这样可以帮助我更好的规划我出门的时间。在这样的情况下,决策树就无法很好地支撑了,因为决策树只能预测离散值。我们可以用节2所介绍的线型回归方法建立这个模型。

如果我把这些建立模型的过程交给电脑。比如把所有的自变量和因变量输入,然后让计算机帮我生成一个模型,同时让计算机根据我当前的情况,给出我是否需要迟出门,需要迟几分钟的建议。那么计算机执行这些辅助决策的过程就是机器学习的过程。

机器学习方法是计算机利用已有的数据(经验),得出了某种模型(迟到的规律),并利用此模型预测未来(是否迟到)的一种方法。

通过上面的分析,可以看出机器学习与人类思考的经验过程是类似的,不过它能考虑更多的情况,执行更加复杂的计算。事实上,机器学习的一个主要目的就是把人类思考归纳经验的过程转化为计算机通过对数据的处理计算得出模型的过程。经过计算机得出的模型能够以近似于人的方式解决很多灵活复杂的问题。

下面,我会开始对机器学习的正式介绍,包括定义、范围,方法、应用等等,都有所包含。

2、机器学习的定义

从广义上来说,机器学习是一种能够赋予机器学习的能力以此让它完成直接编程无法完成的功能的方法。但从实践的意义上来说,机器学习是一种通过利用数据,训练出模型,然后使用模型预测的一种方法。

让我们具体看一个例子。

图4 房价的例子

拿国民话题的房子来说。现在我手里有一栋房子需要售卖,我应该给它标上多大的价格?房子的面积是100平方米,价格是100万,120万,还是140万?

很显然,我希望获得房价与面积的某种规律。那么我该如何获得这个规律?用报纸上的房价平均数据么?还是参考别人面积相似的?无论哪种,似乎都并不是太靠谱。

我现在希望获得一个合理的,并且能够最大程度的反映面积与房价关系的规律。于是我调查了周边与我房型类似的一些房子,获得一组数据。这组数据中包含了大大小小房子的面积与价格,如果我能从这组数据中找出面积与价格的规律,那么我就可以得出房子的价格。

对规律的寻找很简单,拟合出一条直线,让它“穿过”所有的点,并且与各个点的距离尽可能的小。

通过这条直线,我获得了一个能够最佳反映房价与面积规律的规律。这条直线同时也是一个下式所表明的函数:

房价 = 面积 * a + b

上述中的a、b都是直线的参数。获得这些参数以后,我就可以计算出房子的价格。

假设a = 0.75,b = 50,则房价 = 100 * 0.75 + 50 = 125万。这个结果与我前面所列的100万,120万,140万都不一样。由于这条直线综合考虑了大部分的情况,因此从“统计”意义上来说,这是一个最合理的预测。

在求解过程中透露出了两个信息:

1、房价模型是根据拟合的函数类型决定的。如果是直线,那么拟合出的就是直线方程。如果是其他类型的线,例如抛物线,那么拟合出的就是抛物线方程。机器学习有众多算法,一些强力算法可以拟合出复杂的非线性模型,用来反映一些不是直线所能表达的情况。

2、如果我的数据越多,我的模型就越能够考虑到越多的情况,由此对于新情况的预测效果可能就越好。这是机器学习界“数据为王”思想的一个体现。一般来说(不是绝对),数据越多,最后机器学习生成的模型预测的效果越好。

通过我拟合直线的过程,我们可以对机器学习过程做一个完整的回顾。首先,我们需要在计算机中存储历史的数据。接着,我们将这些 数据通过机器学习算法进行处理,这个过程在机器学习中叫做“训练”,处理的结果可以被我们用来对新的数据进行预测,这个结果一般称之为“模型”。对新数据 的预测过程在机器学习中叫做“预测”。“训练”与“预测”是机器学习的两个过程,“模型”则是过程的中间输出结果,“训练”产生“模型”,“模型”指导 “预测”。

让我们把机器学习的过程与人类对历史经验归纳的过程做个比对。

图5 机器学习与人类思考的类比

人类在成长、生活过程中积累了很多的历史与经验。人类定期地对这些经验进行“归纳”,获得了生活的“规律”。当人类遇到未知的问题或者需要对未来进行“推测”的时候,人类使用这些“规律”,对未知问题与未来进行“推测”,从而指导自己的生活和工作。

机器学习中的“训练”与“预测”过程可以对应到人类的“归纳”和“推测”过程。通过这样的对应,我们可以发现,机器学习的思想并不复杂,仅仅是对人类在生活中学习成长的一个模拟。由于机器学习不是基于编程形成的结果,因此它的处理过程不是因果的逻辑,而是通过归纳思想得出的相关性结论。

这也可以联想到人类为什么要学习历史,历史实际上是人类过往经验的总结。有句话说得很好,“历史往往不一样,但历史总是惊人的相似”。通过学习历史,我们从历史中归纳出人生与国家的规律,从而指导我们的下一步工作,这是具有莫大价值的。当代一些人忽视了历史的本来价值,而是把其作为一种宣扬功绩的手段,这其实是对历史真实价值的一种误用。

3、机器学习的范围

上文虽然说明了机器学习是什么,但是并没有给出机器学习的范围。

其实,机器学习跟模式识别,统计学习,数据挖掘,计算机视觉,语音识别,自然语言处理等领域有着很深的联系。

从范围上来说,机器学习跟模式识别,统计学习,数据挖掘是类似的,同时,机器学习与其他领域的处理技术的结合,形成了计算机视觉、语音识别、自然语言处理等交叉学科。因此,一般说数据挖掘时,可以等同于说机器学习。同时,我们平常所说的机器学习应用,应该是通用的,不仅仅局限在结构化数据,还有图像,音频等应用。

在这节对机器学习这些相关领域的介绍有助于我们理清机器学习的应用场景与研究范围,更好的理解后面的算法与应用层次。

下图是机器学习所牵扯的一些相关范围的学科与研究领域。

图6 机器学习与相关学科

模式识别

模式识别=机器学习。两者的主要区别在于前者是从工业界发展起来的概念,后者则主要源自计算机学科。在著名的《Pattern Recognition And Machine Learning》这本书中,Christopher M. Bishop在开头是这样说的“模式识别源自工业界,而机器学习来自于计算机学科。不过,它们中的活动可以被视为同一个领域的两个方面,同时在过去的10年间,它们都有了长足的发展”。

数据挖掘

数据挖掘=机器学习+数据库。这几年数据挖掘的概念实在是太耳熟能详。几乎等同于炒作。但凡说数据挖掘都会吹嘘数据挖掘如何如何,例如从数据中挖出金子,以及将废弃的数据转化为价值等等。但是,我尽管可能会挖出金子,但我也可能挖的是“石头”啊。这个说法的意思是,数据挖掘仅仅是一种思考方式,告诉我们应该尝试从数据中挖掘出知识,但不是每个数据都能挖掘出金子的,所以不要神话它。一个系统绝对不会因为上了一个数据挖掘模块就变得无所不能(这是IBM最喜欢吹嘘的),恰恰相反,一个拥有数据挖掘思维的人员才是关键,而且他还必须对数据有深刻的认识,这样才可能从数据中导出模式指引业务的改善。大部分数据挖掘中的算法是机器学习的算法在数据库中的优化。

统计学习

统计学习近似等于机器学习。统计学习是个与机器学习高度重叠的学科。因为机器学习中的大多数方法来自统计学,甚至可以认为,统计学的发展促进机器学习的繁荣昌盛。例如著名的支持向量机算法,就是源自统计学科。但是在某种程度上两者是有分别的,这个分别在于:统计学习者重点关注的是统计模型的发展与优化,偏数学,而机器学习者更关注的是能够解决问题,偏实践,因此机器学习研究者会重点研究学习算法在计算机上执行的效率与准确性的提升。

计算机视觉

计算机视觉=图像处理+机器学习。图像处理技术用于将图像处理为适合进入机器学习模型中的输入,机器学习则负责从图像中识别出相关的模式。计算机视觉相关的应用非常的多,例如百度识图、手写字符识别、车牌识别等等应用。这个领域是应用前景非常火热的,同时也是研究的热门方向。随着机器学习的新领域深度学习的发展,大大促进了计算机图像识别的效果,因此未来计算机视觉界的发展前景不可估量。

语音识别

语音识别=语音处理+机器学习。语音识别就是音频处理技术与机器学习的结合。语音识别技术一般不会单独使用,一般会结合自然语言处理的相关技术。目前的相关应用有苹果的语音助手siri等。

自然语言处理

自然语言处理=文本处理+机器学习。自然语言处理技术主要是让机器理解人类的语言的一门领域。在自然语言处理技术中,大量使用了编译原理相关的技术,例如词法分析,语法分析等等,除此之外,在理解这个层面,则使用了语义理解,机器学习等技术。作为唯一由人类自身创造的符号,自然语言处理一直是机器学习界不断研究的方向。按照百度机器学习专家余凯的说法“听与看,说白了就是阿猫和阿狗都会的,而只有语言才是人类独有的”。如何利用机器学习技术进行自然语言的的深度理解,一直是工业和学术界关注的焦点。

可以看出机器学习在众多领域的外延和应用。机器学习技术的发展促使了很多智能领域的进步,改善着我们的生活。

4、机器学习的方法

通过上节的介绍我们知晓了机器学习的大致范围,那么机器学习里面究竟有多少经典的算法呢?在这个部分我会简要介绍一下机器学习中的经典代表方法。这部分介绍的重点是这些方法内涵的思想,数学与实践细节不会在这讨论。

1、回归算法

在大部分机器学习课程中,回归算法都是介绍的第一个算法。原因有两个:一.回归算法比较简单,介绍它可以让人平滑地从统计学迁移到机器学习中。二.回归算法是后面若干强大算法的基石,如果不理解回归算法,无法学习那些强大的算法。回归算法有两个重要的子类:即线性回归和逻辑回归。

线性回归就是我们前面说过的房价求解问题。如何拟合出一条直线最佳匹配我所有的数据?一般使用“最小二乘法”来求解。“最小二乘法”的思想是这样的,假设我们拟合出的直线代表数据的真实值,而观测到的数据代表拥有误差的值。为了尽可能减小误差的影响,需要求解一条直线使所有误差的平方和最小。最小二乘法将最优问题转化为求函数极值问题。函数极值在数学上我们一般会采用求导数为0的方法。但这种做法并不适合计算机,可能求解不出来,也可能计算量太大。

计算机科学界专门有一个学科叫“数值计算”,专门用来提升计算机进行各类计算时的准确性和效率问题。例如,著名的“梯度下降”以及“牛顿法”就是数值计算中的经典算法,也非常适合来处理求解函数极值的问题。梯度下降法是解决回归模型中最简单且有效的方法之一。从严格意义上来说,由于后文中的神经网络和推荐算法中都有线性回归的因子,因此梯度下降法在后面的算法实现中也有应用。

逻辑回归是一种与线性回归非常类似的算法,但是,从本质上讲,线型回归处理的问题类型与逻辑回归不一致。线性回归处理的是数值问题,也就是最后预测出的结果是数字,例如房价。而逻辑回归属于分类算法,也就是说,逻辑回归预测结果是离散的分类,例如判断这封邮件是否是垃圾邮件,以及用户是否会点击此广告等等。

实现方面的话,逻辑回归只是对对线性回归的计算结果加上了一个Sigmoid函数,将数值结果转化为了0到1之间的概率(Sigmoid函数的图像一般来说并不直观,你只需要理解对数值越大,函数越逼近1,数值越小,函数越逼近0),接着我们根据这个概率可以做预测,例如概率大于0.5,则这封邮件就是垃圾邮件,或者肿瘤是否是恶性的等等。从直观上来说,逻辑回归是画出了一条分类线,见下图。

图7 逻辑回归的直观解释

假设我们有一组肿瘤患者的数据,这些患者的肿瘤中有些是良性的(图中的蓝色点),有些是恶性的(图中的红色点)。这里肿瘤的红蓝色可以被称作数据的“标签”。同时每个数据包括两个“特征”:患者的年龄与肿瘤的大小。我们将这两个特征与标签映射到这个二维空间上,形成了我上图的数据。

当我有一个绿色的点时,我该判断这个肿瘤是恶性的还是良性的呢?根据红蓝点我们训练出了一个逻辑回归模型,也就是图中的分类线。这时,根据绿点出现在分类线的左侧,因此我们判断它的标签应该是红色,也就是说属于恶性肿瘤。

逻辑回归算法划出的分类线基本都是线性的(也有划出非线性分类线的逻辑回归,不过那样的模型在处理数据量较大的时候效率会很低),这意味着当两类之间的界线不是线性时,逻辑回归的表达能力就不足。下面的两个算法是机器学习界最强大且重要的算法,都可以拟合出非线性的分类线。

2、神经网络

神经网络(也称之为人工神经网络,ANN)算法是80年代机器学习界非常流行的算法,不过在90年代中途衰落。现在,携着“深度学习”之势,神经网络重装归来,重新成为最强大的机器学习算法之一。

神经网络的诞生起源于对大脑工作机理的研究。早期生物界学者们使用神经网络来模拟大脑。机器学习的学者们使用神经网络进行机器学习的实验,发现在视觉与语音的识别上效果都相当好。在BP算法(加速神经网络训练过程的数值算法)诞生以后,神经网络的发展进入了一个热潮。BP算法的发明人之一是前面介绍的机器学习大牛Geoffrey Hinton(图1中的中间者)。

具体说来,神经网络的学习机理是什么?简单来说,就是分解与整合。在著名的Hubel-Wiesel试验中,学者们研究猫的视觉分析机理是这样的。

图8 Hubel-Wiesel试验与大脑视觉机理

比方说,一个正方形,分解为四个折线进入视觉处理的下一层中。四个神经元分别处理一个折线。每个折线再继续被分解为两条直线,每条直线再被分解为黑白两个面。于是,一个复杂的图像变成了大量的细节进入神经元,神经元处理以后再进行整合,最后得出了看到的是正方形的结论。这就是大脑视觉识别的机理,也是神经网络工作的机理。

让我们看一个简单的神经网络的逻辑架构。在这个网络中,分成输入层,隐藏层,和输出层。输入层负责接收信号,隐藏层负责对数据的分解与处理,最后的结果被整合到输出层。每层中的一个圆代表一个处理单元,可以认为是模拟了一个神经元,若干个处理单元组成了一个层,若干个层再组成了一个网络,也就是”神经网络”。

图9 神经网络的逻辑架构

在神经网络中,每个处理单元事实上就是一个逻辑回归模型,逻辑回归模型接收上层的输入,把模型的预测结果作为输出传输到下一个层次。通过这样的过程,神经网络可以完成非常复杂的非线性分类。

下图会演示神经网络在图像识别领域的一个著名应用,这个程序叫做LeNet,是一个基于多个隐层构建的神经网络。通过LeNet可以识别多种手写数字,并且达到很高的识别精度与拥有较好的鲁棒性。

图10 LeNet的效果展示

右下方的方形中显示的是输入计算机的图像,方形上方的红色字样“answer”后面显示的是计算机的输出。左边的三条竖直的图像列显示的是神经网络中三个隐藏层的输出,可以看出,随着层次的不断深入,越深的层次处理的细节越低,例如层3基本处理的都已经是线的细节了。LeNet的发明人就是前文介绍过的机器学习的大牛Yann LeCun(图1右者)。

进入90年代,神经网络的发展进入了一个瓶颈期。其主要原因是尽管有BP算法的加速,神经网络的训练过程仍然很困难。因此90年代后期支持向量机(SVM)算法取代了神经网络的地位。

3、SVM(支持向量机)

支持向量机算法是诞生于统计学习界,同时在机器学习界大放光彩的经典算法。

支持向量机算法从某种意义上来说是逻辑回归算法的强化:通过给予逻辑回归算法更严格的优化条件,支持向量机算法可以获得比逻辑回归更好的分类界线。但是如果没有某类函数技术,则支持向量机算法最多算是一种更好的线性分类技术。

但是,通过跟高斯“核”的结合,支持向量机可以表达出非常复杂的分类界线,从而达成很好的的分类效果。“核”事实上就是一种特殊的函数,最典型的特征就是可以将低维的空间映射到高维的空间。

例如下图所示:

图11 支持向量机图例

我们如何在二维平面划分出一个圆形的分类界线?在二维平面可能会很困难,但是通过“核”可以将二维空间映射到三维空间,然后使用一个线性平面就可以达成类似效果。也就是说,二维平面划分出的非线性分类界线可以等价于三维平面的线性分类界线。于是,我们可以通过在三维空间中进行简单的线性划分就可以达到在二维平面中的非线性划分效果。

图12 三维空间的切割

支持向量机是一种数学成分很浓的机器学习算法(相对的,神经网络则有生物科学成分)。在算法的核心步骤中,有一步证明,即将数据从低维映射到高维不会带来最后计算复杂性的提升。于是,通过支持向量机算法,既可以保持计算效率,又可以获得非常好的分类效果。因此支持向量机在90年代后期一直占据着机器学习中最核心的地位,基本取代了神经网络算法。直到现在神经网络借着深度学习重新兴起,两者之间才又发生了微妙的平衡转变。

4、聚类算法

前面的算法中的一个显著特征就是我的训练数据中包含了标签,训练出的模型可以对其他未知数据预测标签。在下面的算法中,训练数据都是不含标签的,而算法的目的则是通过训练,推测出这些数据的标签。这类算法有一个统称,即无监督算法(前面有标签的数据的算法则是有监督算法)。无监督算法中最典型的代表就是聚类算法。

让我们还是拿一个二维的数据来说,某一个数据包含两个特征。我希望通过聚类算法,给他们中不同的种类打上标签,我该怎么做呢?简单来说,聚类算法就是计算种群中的距离,根据距离的远近将数据划分为多个族群。

聚类算法中最典型的代表就是K-Means算法。

5、降维算法

降维算法也是一种无监督学习算法,其主要特征是将数据从高维降低到低维层次。在这里,维度其实表示的是数据的特征量的大小,例如,房价包含房子的长、宽、面积与房间数量四个特征,也就是维度为4维的数据。可以看出来,长与宽事实上与面积表示的信息重叠了,例如面积=长 × 宽。通过降维算法我们就可以去除冗余信息,将特征减少为面积与房间数量两个特征,即从4维的数据压缩到2维。于是我们将数据从高维降低到低维,不仅利于表示,同时在计算上也能带来加速。

刚才说的降维过程中减少的维度属于肉眼可视的层次,同时压缩也不会带来信息的损失(因为信息冗余了)。如果肉眼不可视,或者没有冗余的特征,降维算法也能工作,不过这样会带来一些信息的损失。但是,降维算法可以从数学上证明,从高维压缩到的低维中最大程度地保留了数据的信息。因此,使用降维算法仍然有很多的好处。

降维算法的主要作用是压缩数据与提升机器学习其他算法的效率。通过降维算法,可以将具有几千个特征的数据压缩至若干个特征。另外,降维算法的另一个好处是数据的可视化,例如将5维的数据压缩至2维,然后可以用二维平面来可视。降维算法的主要代表是PCA算法(即主成分分析算法)。

6、推荐算法

推荐算法是目前业界非常火的一种算法,在电商界,如亚马逊,天猫,京东等得到了广泛的运用。推荐算法的主要特征就是可以自动向用户推荐他们最感兴趣的东西,从而增加购买率,提升效益。推荐算法有两个主要的类别:

一类是基于物品内容的推荐,是将与用户购买的内容近似的物品推荐给用户,这样的前提是每个物品都得有若干个标签,因此才可以找出与用户购买物品类似的物品,这样推荐的好处是关联程度较大,但是由于每个物品都需要贴标签,因此工作量较大。

另一类是基于用户相似度的推荐,则是将与目标用户兴趣相同的其他用户购买的东西推荐给目标用户,例如小A历史上买了物品B和C,经过算法分析,发现另一个与小A近似的用户小D购买了物品E,于是将物品E推荐给小A。

两类推荐都有各自的优缺点,在一般的电商应用中,一般是两类混合使用。推荐算法中最有名的算法就是协同过滤算法。

7、其他

除了以上算法之外,机器学习界还有其他的如高斯判别,朴素贝叶斯,决策树等等算法。但是上面列的六个算法是使用最多,影响最广,种类最全的典型。机器学习界的一个特色就是算法众多,发展百花齐放。

下面做一个总结,按照训练的数据有无标签,可以将上面算法分为监督学习算法和无监督学习算法,但推荐算法较为特殊,既不属于监督学习,也不属于非监督学习,是单独的一类。

监督学习算法:线性回归,逻辑回归,神经网络,SVM

无监督学习算法:聚类算法,降维算法

特殊算法:推荐算法

除了这些算法以外,有一些算法的名字在机器学习领域中也经常出现。但他们本身并不算是一个机器学习算法,而是为了解决某个子问题而诞生的。你可以理解他们为以上算法的子算法,用于大幅度提高训练过程。其中的代表有:梯度下降法,主要运用在线型回归,逻辑回归,神经网络,推荐算法中;牛顿法,主要运用在线型回归中;BP算法,主要运用在神经网络中;SMO算法,主要运用在SVM中。

5、机器学习的应用–大数据

说完机器学习的方法,下面要谈一谈机器学习的应用了。无疑,在2010年以前,机器学习的应用在某些特定领域发挥了巨大的作用,如车牌识别,网络攻击防范,手写字符识别等等。但是,从2010年以后,随着大数据概念的兴起,机器学习大量的应用都与大数据高度耦合,几乎可以认为大数据是机器学习应用的最佳场景。

譬如,但凡你能找到的介绍大数据魔力的文章,都会说大数据如何准确准确预测到了某些事。例如经典的Google利用大数据预测了H1N1在美国某小镇的爆发。

图13 Google成功预测H1N1

百度预测2014年世界杯,从淘汰赛到决赛全部预测正确。

图14 百度世界杯成功预测了所有比赛结果

这些实在太神奇了,那么究竟是什么原因导致大数据具有这些魔力的呢?简单来说,就是机器学习技术。正是基于机器学习技术的应用,数据才能发挥其魔力。

大数据的核心是利用数据的价值,机器学习是利用数据价值的关键技术,对于大数据而言,机器学习是不可或缺的。相反,对于机器学习而言,越多的数据会越 可能提升模型的精确性,同时,复杂的机器学习算法的计算时间也迫切需要分布式计算与内存计算这样的关键技术。因此,机器学习的兴盛也离不开大数据的帮助。 大数据与机器学习两者是互相促进,相依相存的关系。

机器学习与大数据紧密联系。但是,必须清醒的认识到,大数据并不等同于机器学习,同理,机器学习也不等同于大数据。大数据中包含有分布式计算,内存数据库,多维分析等等多种技术。单从分析方法来看,大数据也包含以下四种分析方法:

1、大数据,小分析:即数据仓库领域的OLAP分析思路,也就是多维分析思想。

2、大数据,大分析:这个代表的就是数据挖掘与机器学习分析法。

3、流式分析:这个主要指的是事件驱动架构。

4、查询分析:经典代表是NoSQL数据库。

也就是说,机器学习仅仅是大数据分析中的一种而已。尽管机器学习的一些结果具有很大的魔力,在某种场合下是大数据价值最好的说明。但这并不代表机器学习是大数据下的唯一的分析方法。

机器学习与大数据的结合产生了巨大的价值。基于机器学习技术的发展,数据能够“预测”。对人类而言,积累的经验越丰富,阅历也广泛,对未来的判断越准确。例如常说的“经验丰富”的人比“初出茅庐”的小伙子更有工作上的优势,就在于经验丰富的人获得的规律比他人更准确。而在机器学习领域,根据著名的一个实验,有效的证实了机器学习界一个理论:即机器学习模型的数据越多,机器学习的预测的效率就越好。见下图:

图15 机器学习准确率与数据的关系

通过这张图可以看出,各种不同算法在输入的数据量达到一定级数后,都有相近的高准确度。于是诞生了机器学习界的名言:成功的机器学习应用不是拥有最好的算法,而是拥有最多的数据!

在大数据的时代,有好多优势促使机器学习能够应用更广泛。例如随着物联网和移动设备的发展,我们拥有的数据越来越多,种类也包括图片、文本、视频等非结构化数据,这使得机器学习模型可以获得越来越多的数据。同时大数据技术中的分布式计算Map-Reduce使得机器学习的速度越来越快,可以更方便的使用。种种优势使得在大数据时代,机器学习的优势可以得到最佳的发挥。

6、机器学习的子类–深度学习

近来,机器学习的发展产生了一个新的方向,即“深度学习”。

虽然深度学习这四字听起来颇为高大上,但其理念却非常简单,就是传统的神经网络发展到了多隐藏层的情况。

在上文介绍过,自从90年代以后,神经网络已经消寂了一段时间。但是BP算法的发明人Geoffrey Hinton一直没有放弃对神经网络的研究。由于神经网络在隐藏层扩大到两个以上,其训练速度就会非常慢,因此实用性一直低于支持向量机。2006年,Geoffrey Hinton在科学杂志《Science》上发表了一篇文章,论证了两个观点:

1、多隐层的神经网络具有优异的特征学习能力,学习得到的特征对数据有更本质的刻画,从而有利于可视化或分类;

2、深度神经网络在训练上的难度,可以通过“逐层初始化” 来有效克服。

图16 Geoffrey Hinton与他的学生在Science上发表文章

通过这样的发现,不仅解决了神经网络在计算上的难度,同时也说明了深层神经网络在学习上的优异性。从此,神经网络重新成为了机器学习界中的主流强大学习技术。同时,具有多个隐藏层的神经网络被称为深度神经网络,基于深度神经网络的学习研究称之为深度学习。

由于深度学习的重要性质,在各方面都取得极大的关注,按照时间轴排序,有以下四个标志性事件值得一说:

  • 2012年6月 ,《纽约时报》披露了Google Brain项目,这个项目是由Andrew Ng和Map-Reduce发明人Jeff Dean共同主导,用16000个CPU Core的并行计算平台训练一种称为“深层神经网络”的机器学习模型,在语音识别和图像识别等领域获得了巨大的成功。Andrew Ng就是文章开始所介绍的机器学习的大牛(图1中右者)。
  • 2012年11月, 微软在中国天津的一次活动上公开演示了一个全自动的同声传译系统,讲演者用英文演讲,后台的计算机一气呵成自动完成语音识别、英中机器翻译,以及中文语音合成,效果非常流畅,其中支撑的关键技术是深度学习;
  • 2013年1月 ,在百度的年会上,创始人兼CEO李彦宏高调宣布要成立百度研究院,其中第一个重点方向就是深度学习,并为此而成立深度学习研究院(IDL)。
  • 2013年4月 ,《麻省理工学院技术评论》杂志将深度学习列为2013年十大突破性技术(Breakthrough Technology)之首。

图17 深度学习的发展热潮

文章开头所列的三位机器学习的大牛,不仅都是机器学习界的专家,更是深度学习研究领域的先驱。因此,使他们担任各个大型互联网公司技术掌舵者的原因不仅在于他们的技术实力,更在于他们研究的领域是前景无限的深度学习技术。

目前业界许多的图像识别技术与语音识别技术的进步都源于深度学习的发展,除了本文开头所提的Cortana等语音助手,还包括一些图像识别应用,其中典型的代表就是下图的百度识图功能。

图18 百度识图

深度学习属于机器学习的子类。基于深度学习的发展极大的促进了机器学习的地位提高,更进一步地,推动了业界对机器学习父类人工智能梦想的再次重视。

7、机器学习的父类–人工智能

人工智能是机器学习的父类。深度学习则是机器学习的子类。如果把三者的关系用图来表明的话,则是下图:

图19 深度学习、机器学习、人工智能三者关系

毫无疑问,人工智能(AI)是人类所能想象的科技界最突破性的发明了,某种意义上来说,人工智能就像游戏最终幻想的名字一样,是人类对于科技界的最终梦想。从50年代提出人工智能的理念以后,科技界,产业界不断在探索,研究。这段时间各种小说、电影都在以各种方式展现对于人工智能的想象。人类可以发明类似于人类的机器,这是多么伟大的一种理念!但事实上,自从50年代以后,人工智能的发展就磕磕碰碰,未有见到足够震撼的科学技术的进步。

总结起来,人工智能的发展经历了如下若干阶段,从早期的逻辑推理,到中期的专家系统,这些科研进步确实使我们离机器的智能有点接近了,但还有一大段距离。直到机器学习诞生以后,人工智能界感觉终于找对了方向。基于机器学习的图像识别和语音识别在某些垂直领域达到了跟人相媲美的程度。机器学习使人类第一次如此接近人工智能的梦想。

事实上,如果我们把人工智能相关的技术以及其他业界的技术做一个类比,就可以发现机器学习在人工智能中的重要地位不是没有理由的。

人类区别于其他物体,植物,动物的最主要区别,作者认为是 “智慧”。而智慧的最佳体现是什 么?

是计算能力么,应该不是,心算速度快的人我们一般称之为天才。

是反应能力么,也不是,反应快的人我们称之为灵敏。

是记忆能力么,也不是,记忆好的人我们一般称之为过目不忘。

是推理能力么,这样的人我也许会称他智力很高,类似“福尔摩斯”,但不会称他拥有智慧。

是知识能力么,这样的人我们称之为博闻广,也不会称他拥有智慧。

想想看我们一般形容谁有大智慧?圣人,诸如庄子,老子等。智慧是对生活的感悟,是对人生的积淀与思考,这与我们机器学习的思想何其相似?通过经验获取规律,指导人生与未来。没有经验就没有智慧。

图20 机器学习与智慧

那么,从计算机来看,以上的种种能力都有种种技术去应对。

例如计算能力我们有分布式计算,反应能力我们有事件驱动架构,检索能力我们有搜索引擎,知识存储能力我们有数据仓库,逻辑推理能力我们有专家系统,但是,唯有对应智慧中最显著特征的归纳与感悟能力,只有机器学习与之对应。这也是机器学习能力最能表征智慧的根本原因。

让我们再看一下机器人的制造,在我们具有了强大的计算,海量的存储,快速的检索,迅速的反应,优秀的逻辑推理后我们如果再配合上一个强大的智慧大脑,一个真正意义上的人工智能也许就会诞生,这也是为什么说在机器学习快速发展的现在,人工智能可能不再是梦想的原因。

人工智能的发展可能不仅取决于机器学习,更取决于前面所介绍的深度学习,深度学习技术由于深度模拟了人类大脑的构成,在视觉识别与语音识别上显著性的突破了原有机器学习技术的界限,因此极有可能是真正实现人工智能梦想的关键技术。无论是谷歌大脑还是百度大脑,都是通过海量层次的深度学习网络所构成的。也许借助于深度学习技术,在不远的将来,一个具有人类智能的计算机真的有可能实现。

最后再说一下题外话,由于人工智能借助于深度学习技术的快速发展,已经在某些地方引起了传统技术界达人的担忧。真实世界的“钢铁侠”,特斯拉CEO马斯克就是其中之一。最近马斯克在参加MIT讨论会时,就表达了对于人工智能的担忧。“人工智能的研究就类似于召唤恶魔,我们必须在某些地方加强注意。”

图21 马斯克与人工智能

尽管马斯克的担心有些危言耸听,但是马斯克的推理不无道理。“如果人工智能想要消除垃圾邮件的话,可能它最后的决定就是消灭人类。”马斯克认为预防此类现象的方法是引入政府的监管。在这里作者的观点与马斯克类似,在人工智能诞生之初就给其加上若干规则限制可能有效,也就是不应该使用单纯的机器学习,而应该是机器学习与规则引擎等系统的综合能够较好的解决这类问题。因为如果学习没有限制,极有可能进入某个误区,必须要加上某些引导。正如人类社会中,法律就是一个最好的规则,杀人者死就是对于人类在探索提高生产力时不可逾越的界限。

在这里,必须提一下这里的规则与机器学习引出的规律的不同,规律不是一个严格意义的准则,其代表的更多是概率上的指导,而规则则是神圣不可侵犯,不可修改的。规律可以调整,但规则是不能改变的。有效的结合规律与规则的特点,可以引导出一个合理的,可控的学习型人工智能。

8、机器学习的思考–计算机的潜意识

最后,作者想谈一谈关于机器学习的一些思考。主要是作者在日常生活总结出来的一些感悟。

回想一下我在节1里所说的故事,我把小Y过往跟我相约的经历做了一个罗列。但是这种罗列以往所有经历的方法只有少数人会这么做,大部分的人采用的是更直接的方法,即利用直觉。那么,直觉是什么?其实直觉也是你在潜意识状态下思考经验后得出的规律。就像你通过机器学习算法,得到了一个模型,那么你下次只要直接使用就行了。那么这个规律你是什么时候思考的?可能是在你无意识的情况下,例如睡觉,走路等情况。这种时候,大脑其实也在默默地做一些你察觉不到的工作。

这种直觉与潜意识,我把它与另一种人类思考经验的方式做了区分。如果一个人勤于思考,例如他会每天做一个小结,譬如“吾日三省吾身”,或者他经常与同伴讨论最近工作的得失,那么他这种训练模型的方式是直接的,明意识的思考与归纳。这样的效果很好,记忆性强,并且更能得出有效反应现实的规律。但是大部分的人可能很少做这样的总结,那么他们得出生活中规律的方法使用的就是潜意识法。

举一个作者本人关于潜意识的例子。作者本人以前没开过车,最近一段时间买了车后,天天开车上班。我每天都走固定的路线。有趣的是,在一开始的几天,我非常紧张的注意着前方的路况,而现在我已经在无意识中就把车开到了目标。这个过程中我的眼睛是注视着前方的,我的大脑是没有思考,但是我手握着的方向盘会自动的调整方向。也就是说。随着我开车次数的增多,我已经把我开车的动作交给了潜意识。这是非常有趣的一件事。在这段过程中,我的大脑将前方路况的图像记录了下来,同时大脑也记忆了我转动方向盘的动作。经过大脑自己的潜意识思考,最后生成的潜意识可以直接根据前方的图像调整我手的动作。假设我们将前方的录像交给计算机,然后让计算机记录与图像对应的驾驶员的动作。经过一段时间的学习,计算机生成的机器学习模型就可以进行自动驾驶了。这很神奇,不是么。其实包括Google、特斯拉在内的自动驾驶汽车技术的原理就是这样。

除了自动驾驶汽车以外,潜意识的思想还可以扩展到人的交际。譬如说服别人,一个最佳的方法就是给他展示一些信息,然后让他自己去归纳得出我们想要的结论。这就好比在阐述一个观点时,用一个事实,或者一个故事,比大段的道理要好很多。古往今来,但凡优秀的说客,无不采用的是这种方法。春秋战国时期,各国合纵连横,经常有各种说客去跟一国之君交流,直接告诉君主该做什么,无异于自寻死路,但是跟君主讲故事,通过这些故事让君主恍然大悟,就是一种正确的过程。这里面有许多杰出的代表,如墨子,苏秦等等。

基本上所有的交流过程,使用故事说明的效果都要远胜于阐述道义之类的效果好很多。为什么用故事的方法比道理或者其他的方法好很多,这是因为在人成长的过程,经过自己的思考,已经形成了很多规律与潜意识。如果你告诉的规律与对方的不相符,很有可能出于保护,他们会本能的拒绝你的新规律,但是如果你跟他讲一个故事,传递一些信息,输送一些数据给他,他会思考并自我改变。他的思考过程实际上就是机器学习的过程,他把新的数据纳入到他的旧有的记忆与数据中,经过重新训练。如果你给出的数据的信息量非常大,大到调整了他的模型,那么他就会按照你希望的规律去做事。有的时候,他会本能的拒绝执行这个思考过程,但是数据一旦输入,无论他希望与否,他的大脑都会在潜意识状态下思考,并且可能改变他的看法。

如果计算机也拥有潜意识(正如本博客的名称一样),那么会怎么样?譬如让计算机在工作的过程中,逐渐产生了自身的潜意识,于是甚至可以在你不需要告诉它做什么时它就会完成那件事。这是个非常有意思的设想,这里留给各位读者去发散思考吧。

9、总结

本文首先介绍了互联网界与机器学习大牛结合的趋势,以及使用机器学习的相关应用,接着以一个“等人故事”展开对机器学习的介绍。介绍中首先是机器学习的概念与定义,然后是机器学习的相关学科,机器学习中包含的各类学习算法,接着介绍机器学习与大数据的关系,机器学习的新子类深度学习,最后探讨了一下机器学习与人工智能发展的联系以及机器学习与潜意识的关联。经过本文的介绍,相信大家对机器学习技术有一定的了解,例如机器学习是什么,它的内核思想是什么(即统计和归纳),通过了解机器学习与人类思考的近似联系可以知晓机器学习为什么具有智慧能力的原因等等。其次,本文漫谈了机器学习与外延学科的关系,机器学习与大数据相互促进相得益彰的联系,机器学习界最新的深度学习的迅猛发展,以及对于人类基于机器学习开发智能机器人的一种展望与思考,最后作者简单谈了一点关于让计算机拥有潜意识的设想。

机器学习是目前业界最为Amazing与火热的一项技术,从网上的每一次淘宝的购买东西,到自动驾驶汽车技术,以及网络攻击抵御系统等等,都有机器学习的因子在内,同时机器学习也是最有可能使人类完成AI dream的一项技术,各种人工智能目前的应用,如微软小冰聊天机器人,到计算机视觉技术的进步,都有机器学习努力的成分。作为一名当代的计算机领域的开发或管理人员,以及身处这个世界,使用者IT技术带来便利的人们,最好都应该了解一些机器学习的相关知识与概念,因为这可以帮你更好的理解为你带来莫大便利技术的背后原理,以及让你更好的理解当代科技的进程。

10、后记

这篇文档花了作者两个月的时间,终于在2014年的最后一天的前一天基本完成。通过这篇文章,作者希望对机器学习在国内的普及做一点贡献,同时也是作者本人自己对于所学机器学习知识的一个融汇贯通,整体归纳的提高过程。作者把这么多的知识经过自己的大脑思考,训练出了一个模型,形成了这篇文档,可以说这也是一种机器学习的过程吧(笑)。

作者所在的行业会接触到大量的数据,因此对于数据的处理和分析是平常非常重要的工作,机器学习课程的思想和理念对于作者日常的工作指引作用极大,几乎导致了作者对于数据价值的重新认识。想想半年前,作者还对机器学习似懂非懂,如今也可以算是一个机器学习的Expert了(笑)。但作者始终认为,机器学习的真正应用不是通过概念或者思想的方式,而是通过实践。只有当把机器学习技术真正应用时,才可算是对机器学习的理解进入了一个层次。正所谓再“阳春白雪”的技术,也必须落到“下里巴人”的场景下运用。目前有一种风气,国内外研究机器学习的某些学者,有一种高贵的逼格,认为自己的研究是普通人无法理解的,但是这样的理念是根本错误的,没有在真正实际的地方发挥作用,凭什么证明你的研究有所价值呢?作者认为必须将高大上的技术用在改变普通人的生活上,才能发挥其根本的价值。一些简单的场景,恰恰是实践机器学习技术的最好地方。

《台大机器学习基石》Linear Regression

By Kubi Code

Source: http://kubicode.me/2015/08/19/Machine%20Learning/Linear-Regression/

Linear Regression

现在相对比于之前的Perceptron Learning Algorithm算法,假如我们现在时的问题不是解决是否发行用卡,而是该发多少额度的问题

也就是输出空间属于一个实数,那么就需要一个回归算法来解决该问题!

那么我们其实可以直接使用特征属性与权重的加权求和来表示需要发的信用额度即可(与PLA类似,但是没有激活函数:二值判断逆函数)

上图中表示的就是为线性回归(Linear Regression),其中wTx就是表示为全部的假设空间(hypothesis set)

如果当前的特征是一维的,那么这里的hypothesis set就表示一条线,(因为总体的特征向量里面还有一个常数值)

如果当前的特征是二维的,那么这里的hypothesis set就一个平面

当然特征更加多得话,最终hypothesis set表示一个超平面
其中图上红色的部分叫做误差(视频里面叫做余数),那么回归分析的目标就是将所有的误差降到最小越好
这里使用平方误差来衡量整体的误差

那么从机器学习的角度来说,这里的误差就可以看做(下面这个表达式就很熟悉了)

相应的

表示这个分类器在未来未训练数据集中产生的误差是多少
那么现在的线性回归的问题就是转为将Ein(w)优化到最小。

Ein(w)最小化

现将上面小节的中的Ein转为矩阵的运算

  1. 向量内积可交换,将wTx转为xTw
  2. 将连加转为向量形式的长度(应该是二范数)
  3. w单独提出来(相当于隔离出了一个特征属性向量的矩阵)
  4. 最终使用缩写来进行整理

到了这一步我们可以发现Ein(w)只与w有关,那么他们的关系图是

可以发现Ein(w)是连续可导,还有它是凸的
那么用Ein(w)w求偏导即可求导最优值(梯度为0的位置)

这样现在问题又转为了 求

首先将
现在对其求偏导

完了之后再将A,b替换回去

进一步将问题转换为
式子中XTXXTy都是已知的,唯一不知道的就是w,这样就变为了一个一次的方程式

  1. 假如有(XTX)-1反矩阵的存在,那么就可以直接得到解了,并且是唯一的
  2. 但是如果(XTX)-1反矩阵不存在,那么得到的解可能就不唯一了

所以这里的核心就是计算虚假的反矩阵(pseudo-inverse),听林老师说这个的计算很多工具都是由现成的^_^

刚刚求Ein(w)最小化的过程中看似直接用公式代替可到,但是其中的pseudo-inverse计算起来麻烦,最终在计算的时候还是需要迭代,然后会触发Ein(w)Eout(w)的变化,是一个深度隐含的学习过程(这种是叫做Analytic Solution)。

Learning happened

那么该如果保证Eout可以是小的呢?
我们先来看一下Ein的平均

其中nosie level表示样本中噪声的一个情况,d+1表示模型的自由度,N表示样本的容量
其中单独表示Ein(w)的话为

这样就形成了两项1-XX+y,也就是相当于将输入喝输出进行了一个分离,其中XX+叫做hat matrix
关于这个hat matrix,它的意义是这样纸的

  1. 红色区块表示向量X的一个扩散,而y^就是落在这个空间上
  2. 目标就是求y-y^的最小化,也就是图种的绿色那条线(y^)向下投影的线
  3. H就是表示这个空间上yy^的一个投影
  4. I-H就是表示误差部分y-y^

相应的会有trace(I-H)=N-(d+1)

好,现在再来看Ein的平均到底是什么意思

  1. 其中如果f(x)为目标函数,那么目标值y就相当于在f(x)上添加噪声
  2. 然后这个噪声通过I-H就可以转为y-y^

现在对噪声作评价的话,那么就可以得到
此时
这两个式子哲学上的意思是Ein的平均是可以看到的,所以当存在噪声的时候看到的线会偏向于噪声方向,而在Eout的平均是未知的,比最好的那个线还要向右边偏一点(没听懂-_-)

他们俩会形成如下的关系线

它描述的是当前的样本量与平均的EinEout的关系,随着样本量N的增长,最终会趋向于nosie level

那么就可以得到

说明N足够大,然后他的noise level够小时,说明了Learning happened

总结

  1. 线性回归最终求出的是一个加权求和的值.
  • 线性回归的Ein的采用的是最小平方误差.
  • 在计算Ein的最小化时,可以将问题转为矩阵之后就逆矩阵相关即可.
  • 通过Ein平均的计算,说明了Learning happened.
  • 其实线性回归去坐分类问题也是可以的^_^,第9课第4个小视频.

参考

  • 《台湾国立大学-机器学习基石》第九讲

配图均来自《台湾国立大学-机器学习基石》

机器学习常见算法个人总结

By:kubiCode

Source: http://kubicode.me/2015/08/16/Machine%20Learning/Algorithm-Summary-for-Interview/

朴素贝叶斯

参考[1]

事件AB同时发生的概率为在A发生的情况下发生B或者在B发生的情况下发生A

P(AB)=P(A)P(B|A)=P(B)P(A|B)

“>[Math Processing Error]
所以有:

P(A|B)=P(B|A)P(A)P(B)

“>[Math Processing Error]

对于给出的待分类项,求解在此项出现的条件下各个目标类别出现的概率,哪个最大,就认为此待分类项属于哪个类别

工作原理

  1. 假设现在有样本x=(a1,a2,a3,an)

    “>[Math Processing Error]

这个待分类项(并认为x

“>[Math Processing Error]

  • 里面的特征独立)
  • 再假设现在有分类目标Y={y1,y2,y3,y4..yn}

    “>[Math Processing Error]

  • 那么max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))

    “>[Math Processing Error]

  • 就是最终的分类类别
  • P(yi|x)=p(x|yi)P(yi)P(x)

    “>[Math Processing Error]

  • 因为x

    “>[Math Processing Error]

对于每个分类目标来说都一样,所以就是求max(P(x|yi)p(yi))

“>[Math Processing Error]

  • P(x|yi)p(yi)=p(yi)i(P(ai|yi))

    “>[Math Processing Error]

  • 而具体的p(ai|yi)

    “>[Math Processing Error]

p(yi)

“>[Math Processing Error]都是能从训练样本中统计出来
p(ai|yi)

“>[Math Processing Error]表示该类别下该特征出现的概率
p(yi)

“>[Math Processing Error]

 

  1. 表示全部类别中这个这个类别出现的概率
  2. 好的,就是这么工作的^_^

工作流程

  1. 准备阶段
    确定特征属性,并对每个特征属性进行适当划分,然后由人工对一部分待分类项进行分类,形成训练样本。
  2. 训练阶段
    计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计
  3. 应用阶段
    使用分类器进行分类,输入是分类器和待分类样本,输出是样本属于的分类类别

属性特征

  1. 特征为离散值时直接统计即可(表示统计概率)
  2. 特征为连续值的时候假定特征符合高斯分布:g(x,n,u)

    “>[Math Processing Error]

那么p(ak|yi)=g(xk,ni,ui)

“>[Math Processing Error]

Laplace校准(拉普拉斯校验)

当某个类别下某个特征划分没有出现时,会有P(a|y)=0

“>[Math Processing Error]

,就是导致分类器质量降低,所以此时引入Laplace校验,就是对没类别下所有划分的计数加1。

遇到特征之间不独立问题

参考改进的贝叶斯网络,使用DAG来进行概率图的描述

优缺点

朴素贝叶斯的优点:

  1. 对小规模的数据表现很好,适合多分类任务,适合增量式训练。
    缺点:
  2. 对输入数据的表达形式很敏感(离散、连续,值极大极小之类的)。

逻辑回归和线性回归

参考[2,3,4]

LR回归是一个线性的二分类模型,主要是计算在某个样本特征下事件发生的概率,比如根据用户的浏览购买情况作为特征来计算它是否会购买这个商品,抑或是它是否会点击这个商品。然后LR的最终值是根据一个线性和函数再通过一个sigmod函数来求得,这个线性和函数权重与特征值的累加以及加上偏置求出来的,所以在训练LR时也就是在训练线性和函数的各个权重值w

hw(x)=11+e(wTx+b)

“>[Math Processing Error]

关于这个权重值w一般使用最大似然法来估计,假设现在有样本{xi,yi}

“>[Math Processing Error]

,其中xi

“>[Math Processing Error]表示样本的特征,yi{0,1}

“>[Math Processing Error]表示样本的分类真实值,yi=1

“>[Math Processing Error]的概率是pi

“>[Math Processing Error],则yi=0

“>[Math Processing Error]的概率是1pi

“>[Math Processing Error],那么观测概率为:

p(yi)=piyi(1pi)1yi

“>[Math Processing Error]
则最大似然函数为:

(hw(xi)yi(1hw(xi))1yi)

“>[Math Processing Error]

对这个似然函数取对数之后就会得到的表达式

L(w)=i(yiloghw(xi)(1yi)log(1hw(xi)))=i(yi(wTxi)log(1+ewTxi))

“>[Math Processing Error]
估计这个L(w)

“>[Math Processing Error]的极大值就可以得到w

“>[Math Processing Error]

的估计值。

实际操作中一般会加个负号 改为求最小

所以求解问题就变成了这个最大似然函数的最优化问题,这里通常会采样随机梯度下降法和拟牛顿迭代法来进行优化

梯度下降法

LR的损失函数为:

J(w)=1Ni=1N(yilog(hw(xi))+(1yi)log(1hw(xi)))

“>[Math Processing Error]
这样就变成了求min(J(w))

“>[Math Processing Error]

其更新w的过程为

w:=wαJ(w)w:=wα1Ni=1N(hw(xi)yi)xi)

“>[Math Processing Error]
其中α

“>[Math Processing Error],直到J(w)

“>[Math Processing Error]

不能再小时停止

梯度下降法的最大问题就是会陷入局部最优,并且每次在对当前样本计算cost的时候都需要去遍历全部样本才能得到cost值,这样计算速度就会慢很多(虽然在计算的时候可以转为矩阵乘法去更新整个w值)
所以现在好多框架(mahout)中一般使用随机梯度下降法,它在计算cost的时候只计算当前的代价,最终cost是在全部样本迭代一遍之求和得出,还有他在更新当前的参数w的时候并不是依次遍历样本,而是从所有的样本中随机选择一条进行计算,它方法收敛速度快(一般是使用最大迭代次数),并且还可以避免局部最优,并且还很容易并行(使用参数服务器的方式进行并行)

w:=wα(hw(xj)yj)xi);j1 Nandrandomly

“>[Math Processing Error]

这里SGD可以改进的地方就是使用动态的步长

α=0.04(1.0+n+i)+r

“>[Math Processing Error]

其他优化方法

  • 拟牛顿法(记得是需要使用Hessian矩阵和cholesky分解)
  • BFGS
  • L-BFGS

优缺点:无需选择学习率α,更快,但是更复杂

关于LR的过拟合问题:

如果我们有很多的特性,在训练集上拟合得很好,但是在预测集上却达不到这种效果

  1. 减少feature个数(人工定义留多少个feature、算法选取这些feature)
  2. 正则化(为了方便求解,L2使用较多)
    添加正则化之后的损失函数为: J(w)=1Ni=1N(yilog(hw(xi))+(1yi)log(1hw(xi)))+λ||w||2

    “>[Math Processing Error]

同时w的更新变为w:=wα(hw(xj)yj)xi)2αwj

“>[Math Processing Error]
注意:这里的w0

“>[Math Processing Error]

  1. 不受正则化影响

关于LR的多分类:softmax

假设离散型随机变量Y的取值集合是{1,2,..,k},则多分类的LR为

P(Y=a|x)=exp(wax)(i=1k(wix));1<a<k

“>[Math Processing Error]

这里会输出当前样本下属于哪一类的概率,并且满足全部概率加起来=1

关于softmax和k个LR的选择

如果类别之间是否互斥(比如音乐只能属于古典音乐、乡村音乐、摇滚月的一种)就用softmax
否则类别之前有联系(比如一首歌曲可能有影视原声,也可能包含人声,或者是舞曲),这个时候使用k个LR更为合适

优缺点:
Logistic回归优点:

  1. 实现简单;
  2. 分类时计算量非常小,速度很快,存储资源低;

缺点:

  1. 容易欠拟合,一般准确度不太高
  2. 只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;

ps 另外LR还可以参考这篇以及多分类可以看这篇

KNN算法

给一个训练数据集和一个新的实例,在训练数据集中找出与这个新实例最近的k个训练实例,然后统计最近的k个训练实例中所属类别计数最多的那个类,就是新实例的类

三要素:

  1. k值的选择
  2. 距离的度量(常见的距离度量有欧式距离,马氏距离等)
  3. 分类决策规则 (多数表决规则)

k值的选择

  1. k值越小表明模型越复杂,更加容易过拟合
  2. 但是k值越大,模型越简单,如果k=N的时候就表明无论什么点都是训练集中类别最多的那个类

所以一般k会取一个较小的值,然后用过交叉验证来确定
这里所谓的交叉验证就是将样本划分一部分出来为预测样本,比如95%训练,5%预测,然后k分别取1,2,3,4,5之类的,进行预测,计算最后的分类误差,选择误差最小的k

KNN的回归

在找到最近的k个实例之后,可以计算这k个实例的平均值作为预测值。或者还可以给这k个实例添加一个权重再求平均值,这个权重与度量距离成反比(越近权重越大)。

优缺点:

KNN算法的优点:

  1. 思想简单,理论成熟,既可以用来做分类也可以用来做回归;
  2. 可用于非线性分类;
  3. 训练时间复杂度为O(n);
  4. 准确度高,对数据没有假设,对outlier不敏感;

缺点:

  1. 计算量大;
  2. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);
  3. 需要大量的内存;

KD树

KD树是一个二叉树,表示对K维空间的一个划分,可以进行快速检索(那KNN计算的时候不需要对全样本进行距离的计算了)

构造KD树

在k维的空间上循环找子区域的中位数进行划分的过程。
假设现在有K维空间的数据集T={x1,x2,x3,xn}

“>[Math Processing Error]

,xi={a1,a2,a3..ak}

“>[Math Processing Error]

  1. 首先构造根节点,以坐标a1

    “>[Math Processing Error]

的中位数b为切分点,将根结点对应的矩形局域划分为两个区域,区域1中a1<b

“>[Math Processing Error],区域2中a1>b

“>[Math Processing Error]

  • 构造叶子节点,分别以上面两个区域中a2

    “>[Math Processing Error]

  • 的中位数作为切分点,再次将他们两两划分,作为深度1的叶子节点,(如果a2=中位数,则a2的实例落在切分面)
  • 不断重复2的操作,深度为j的叶子节点划分的时候,索取的ai

    “>[Math Processing Error]

i=j%k+1

“>[Math Processing Error]

 

  1. ,直到两个子区域没有实例时停止

KD树的搜索

  1. 首先从根节点开始递归往下找到包含x的叶子节点,每一层都是找对应的xi
  2. 将这个叶子节点认为是当前的“近似最近点”
  3. 递归向上回退,如果以x圆心,以“近似最近点”为半径的球与根节点的另一半子区域边界相交,则说明另一半子区域中存在与x更近的点,则进入另一个子区域中查找该点并且更新”近似最近点“
  4. 重复3的步骤,直到另一子区域与球体不相交或者退回根节点
  5. 最后更新的”近似最近点“与x真正的最近点

KD树进行KNN查找

通过KD树的搜索找到与搜索目标最近的点,这样KNN的搜索就可以被限制在空间的局部区域上了,可以大大增加效率。

KD树搜索的复杂度

当实例随机分布的时候,搜索的复杂度为log(N),N为实例的个数,KD树更加适用于实例数量远大于空间维度的KNN搜索,如果实例的空间维度与实例个数差不多时,它的效率基于等于线性扫描。

后来自己有实现过KD树,可以看KNN算法中KD树的应用

SVM、SMO

对于样本点(xi,yi)

“>[Math Processing Error]

以及svm的超平面:wTxi+b=0

“>[Math Processing Error]

  • 函数间隔:yi(wTxi+b)

    “>[Math Processing Error]

 

  • 几何间隔:yi(wTxi+b)||w||

    “>[Math Processing Error]

,其中||w||

“>[Math Processing Error]为w

“>[Math Processing Error]

 

  • 的L2范数,几何间隔不会因为参数比例的改变而改变

svm的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面。

线性SVM问题

先来看svm的问题:

argmaxw,bγst.yi(wTxi+b)||w||γ

“>[Math Processing Error]

那么假设γ^=γ||w||

“>[Math Processing Error]

则将问题转为:

argmaxw,bγ^||w||st.yi(wTxi+b)1

“>[Math Processing Error]

由于γ^

“>[Math Processing Error]

的成比例增减不会影响实际间距,所以这里的取γ^=1

“>[Math Processing Error],又因为max(1||w||)=min(12||w||2)

“>[Math Processing Error]
所以最终的问题就变为了

argminw,b12||w||2st.yi(wTxi+b)1

“>[Math Processing Error]

这样就变成了一个凸的二次规划化,可以将其转换为拉格朗日函数,然后使用对偶算法来求解

对偶求解

引进拉格朗日乘子α={α1,α2..αn}

“>[Math Processing Error]

,定义拉格朗日函数:

L(w,b,a)=12||w||2i=1N(αiyi(wTxi+b))+(αi)

“>[Math Processing Error]

根据对偶性质 原始问题就是求对偶问题的极大极小

maxαminw,bL(w,b,α)

“>[Math Processing Error]
先求L对w,b

“>[Math Processing Error]的极小,再求对α

“>[Math Processing Error]的极大。
minw,bL(w,b,α)

“>[Math Processing Error],也就是相当于对w,b

“>[Math Processing Error]求偏导并且另其等于0

wL(w,b,α)=wi=1N(αiyixi)=0bL(w,b,α)=i=1N(aiyi)=0

“>[Math Processing Error]
代入后可得

minw,bL(w,b,α)=12i=1Nj=1N(αiαjyiyj(xixj))+i=1Nαi

“>[Math Processing Error]
minw,bL(w,b,α)

“>[Math Processing Error]对α

“>[Math Processing Error]的极大,即是对偶问题:

maxα12i=1Nj=1N(αiαjyiyj(xixj))+i=1Nαist.i=1N(aiyi)=0α0,i=1,2,3N

“>[Math Processing Error]
将求最大转为求最小,得到等价的式子为:

minα12i=1Nj=1N(αiαjyiyj(xixj))i=1Nαist.i=1N(aiyi)=0α0,i=1,2,3N

“>[Math Processing Error]

假如求解出来的α

“>[Math Processing Error]

α=(α1,α2,αn)

“>[Math Processing Error]
则得到最优的w,b

“>[Math Processing Error]分别为

w=i=1N(αiyixi)b=yji=1N(αiyi(xixj))

“>[Math Processing Error]
所以,最终的决策分类面为

f(x)=sign(i=1N(αiyi(xxi)+b)

“>[Math Processing Error]
也就是说,分类决策函数只依赖于输入x

“>[Math Processing Error]

与训练样本的输入的内积

ps:上面介绍的是SVM的硬间距最大化,还有一种是软间距最大化,引用了松弛变量ζ

“>[Math Processing Error]

,则次svm问题变为:

argminw,b12||w||2+Ci=1Nζist.yi(wTxi+b)1ζiζi0,i=1,2N

“>[Math Processing Error]

其余解决是与硬间距的一致~

还有:与分离超平面最近的样本点称为支持向量

损失函数

损失函数为(优化目标):

i=1N[1yi(wTxi+b)]++λ||w||2

“>[Math Processing Error]
其中[1yi(wTxi+b)]+

“>[Math Processing Error]称为折页损失函数,因为:

[1yi(wTxi+b)]+={0if1yi(wTxi+b)01yi(wTxi+b)otherwise

“>[Math Processing Error]

为什么要引入对偶算法

  1. 对偶问题往往更加容易求解(结合拉格朗日和kkt条件)
  2. 可以很自然的引用核函数(拉格朗日表达式里面有内积,而核函数也是通过内积进行映射的)

核函数

将输入特征x(线性不可分)映射到高维特征R空间,可以在R空间上让SVM进行线性可以变,这就是核函数的作用

  • 多项式核函数:K(x,z)=(xz+1)p

    “>[Math Processing Error]

 

  • 高斯核函数:K(x,z)=exp((xz)2σ2)

    “>[Math Processing Error]

 

  • 字符串核函数:貌似用于字符串处理等

SVM优缺点

优点:

  1. 使用核函数可以向高维空间进行映射
  2. 使用核函数可以解决非线性的分类
  3. 分类思想很简单,就是将样本与决策面的间隔最大化
  4. 分类效果较好

缺点:

  1. 对大规模数据训练比较困难
  2. 无法直接支持多分类,但是可以使用间接的方法来做

SMO

SMO是用于快速求解SVM的
它选择凸二次规划的两个变量,其他的变量保持不变,然后根据这两个变量构建一个二次规划问题,这个二次规划关于这两个变量解会更加的接近原始二次规划的解,通过这样的子问题划分可以大大增加整个算法的计算速度,关于这两个变量:

  1. 其中一个是严重违反KKT条件的一个变量
  2. 另一个变量是根据自由约束确定,好像是求剩余变量的最大化来确定的。

SVM多分类问题

  1. 直接法
    直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该优化就可以实现多分类(计算复杂度很高,实现起来较为困难)
  2. 间接法
    1. 一对多
      其中某个类为一类,其余n-1个类为另一个类,比如A,B,C,D四个类,第一次A为一个类,{B,C,D}为一个类训练一个分类器,第二次B为一个类,{A,C,D}为另一个类,按这方式共需要训练4个分类器,最后在测试的时候将测试样本经过这4个分类器f1(x)

      “>[Math Processing Error]

,f2(x)

“>[Math Processing Error],f3(x)

“>[Math Processing Error]和f4(x)

“>[Math Processing Error]

    1. ,取其最大值为分类器(这种方式由于是1对M分类,会存在偏置,很不实用)
    2. 一对一(libsvm实现的方式)
      任意两个类都训练一个分类器,那么n个类就需要n*(n-1)/2个svm分类器。
      还是以 A,B,C,D为例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}为目标共6个分类器,然后在预测的将测试样本通过 这6个分类器之后进行投票选择最终结果。(这种方法虽好,但是需要n*(n-1)/2个分类器代价太大,不过有好像使用循环图来进行改进)

决策树

决策树是一颗依托决策而建立起来的树。

ID3

  1. 首先是针对当前的集合,计算每个特征的信息增益
  2. 然后选择信息增益最大的特征作为当前节点的决策决策特征
  3. 根据特征不同的类别划分到不同的子节点(比如年龄特征有青年,中年,老年,则划分到3颗子树)
  4. 然后继续对子节点进行递归,直到所有特征都被划分

S(C,ai)=i(pilog(pi))

“>[Math Processing Error]一个属性中某个类别的熵 pi=P(yi|ai)

“>[Math Processing Error], pi

“>[Math Processing Error]表示ai

“>[Math Processing Error]情况下发生yi

“>[Math Processing Error]

的概率,也即是统计概率。

S(C,A)=i(P(A=ai)S(ai))

“>[Math Processing Error]

整个属性的熵,为各个类别的比例与各自熵的加权求和。

Gain(C,A)=S(C)S(C,A)

“>[Math Processing Error]

增益表示分类目标的熵减去当前属性的熵,增益越大,分类能力越强
(这里前者叫做经验熵,表示数据集分类C的不确定性,后者就是经验条件熵,表示在给定A的条件下对数据集分类C的不确定性,两者相减叫做互信息,决策树的增益等价于互信息)。
比如说当前属性是是否拥有房产,分类是是否能偿还债务
现在:

  • 有用房产为7个,4个能偿还债务,3个无法偿还债务
  • 然后无房产为3个,其中1个能偿还债务,2个无法偿还债务

然后
有房子的熵:S(have_house)=(47log47+37log37)

“>[Math Processing Error]

无房子的熵:S(no_house)=(13log13+23log23)

“>[Math Processing Error]
分类的熵:S(classifier)=(510log510+510log510)

“>[Math Processing Error]
最终的增益=S(classifier)(710S(have_house)+310S(no_house))

“>[Math Processing Error]

最大越好

关于损失函数
设树的叶子节点个数为T

“>[Math Processing Error]

t

“>[Math Processing Error]为其中一个叶子节点,该叶子节点有Nt

“>[Math Processing Error]个样本,其中k

“>[Math Processing Error]类的样本有Ntk

“>[Math Processing Error]个,H(t)

“>[Math Processing Error]为叶子节点上的经验熵,则损失函数定义为

Ct(T)=(NtH(t))+λ|T|

“>[Math Processing Error]
其中

H(t)=(NtkNtlog(NtkNt))

“>[Math Processing Error]
代入可以得到

Ct(T)=((Ntklog(Ntk/Nt)))+λ|T|

“>[Math Processing Error]

λ|T|

“>[Math Processing Error]

为正则化项,λ

“>[Math Processing Error]

是用于调节比率
决策树的生成只考虑了信息增益

C4.5

它是ID3的一个改进算法,使用信息增益率来进行属性的选择

splitInformation(S,A)=i(|Si||S|log2(|Si||S|))GainRatio(S,A)=Gain(S,A)splitInformation(S,A)

“>[Math Processing Error]

优缺点:
准确率高,但是子构造树的过程中需要进行多次的扫描和排序,所以它的运算效率较低

Cart

分类回归树(Classification And Regression Tree)是一个决策二叉树,在通过递归的方式建立,每个节点在分裂的时候都是希望通过最好的方式将剩余的样本划分成两类,这里的分类指标:

  1. 分类树:基尼指数最小化(gini_index)
  2. 回归树:平方误差最小化

分类树:

  1. 首先是根据当前特征计算他们的基尼增益
  2. 选择基尼增益最小的特征作为划分特征
  3. 从该特征中查找基尼指数最小的分类类别作为最优划分点
  4. 将当前样本划分成两类,一类是划分特征的类别等于最优划分点,另一类就是不等于
  5. 针对这两类递归进行上述的划分工作,直达所有叶子指向同一样本目标或者叶子个数小于一定的阈值

gini用来度量分布不均匀性(或者说不纯),总体的类别越杂乱,GINI指数就越大(跟熵的概念很相似)

gini(ai)=1i(pi2)

“>[Math Processing Error] pi

“>[Math Processing Error]当前数据集中第i类样本的比例
gini越小,表示样本分布越均匀(0的时候就表示只有一类了),越大越不均匀
基尼增益

gini_gain=i(NiNgini(ai))

“>[Math Processing Error] 表示当前属性的一个混乱 NiN

“>[Math Processing Error]

表示当前类别占所有类别的概率
最终Cart选择GiniGain最小的特征作为划分特征

以ID3中的贷款的那棵树为样例:
基尼指数有房产:gini(have_house)=1((37)2+(47)2)

“>[Math Processing Error]

基尼指数无房产:gini(no_house)=1((13)2+(23)2)

“>[Math Processing Error]
基尼增益为:gini_gain=710gini(have_house)+310gini(no_house)

“>[Math Processing Error]

回归树:

回归树是以平方误差最小化的准则划分为两块区域

  1. 遍历特征计算最优的划分点s,
    使其最小化的平方误差是:min{min(R1.sigma((yic1)2))+min(R2.sigma((yic2)2))}

    “>[Math Processing Error]

计算根据s划分到左侧和右侧子树的目标值与预测值之差的平方和最小,这里的预测值是两个子树上输入xi样本对应yi

“>[Math Processing Error]

  • 的均值
  • 找到最小的划分特征j以及其最优的划分点s,根据特征j以及划分点s将现有的样本划分为两个区域,一个是在特征j上小于等于s,另一个在在特征j上大于s

    R1(j)={x|x(j)s}R2(j)={x|x(j)>s}

    “>[Math Processing Error]

 

  1. 进入两个子区域按上述方法继续划分,直到到达停止条件

这里面的最小化我记得可以使用最小二乘法来求

关于剪枝:用独立的验证数据集对训练集生长的树进行剪枝(事后剪枝)。

停止条件

  1. 直到每个叶子节点都只有一种类型的记录时停止,(这种方式很容易过拟合)
  2. 另一种时当叶子节点的记录树小于一定的阈值或者节点的信息增益小于一定的阈值时停止

关于特征与目标值

  1. 特征离散 目标值离散:可以使用ID3,cart
  2. 特征连续 目标值离散:将连续的特征离散化 可以使用ID3,cart
  3. 特征离散 目标值连续

决策树的分类与回归

  • 分类树
    输出叶子节点中所属类别最多的那一类
  • 回归树
    输出叶子节点中各个样本值的平均值

理想的决策树

  1. 叶子节点数尽量少
  2. 叶子节点的深度尽量小(太深可能会过拟合)

解决决策树的过拟合

  1. 剪枝
    1. 前置剪枝:在分裂节点的时候设计比较苛刻的条件,如不满足则直接停止分裂(这样干决策树无法到最优,也无法得到比较好的效果)
    2. 后置剪枝:在树建立完之后,用单个节点代替子树,节点的分类采用子树中主要的分类(这种方法比较浪费前面的建立过程)
  2. 交叉验证
  3. 随机森林

优缺点

优点:

  1. 计算量简单,可解释性强,比较适合处理有缺失属性值的样本,能够处理不相关的特征;
    缺点:
  2. 单颗决策树分类能力弱,并且对连续值变量难以处理;
  3. 容易过拟合(后续出现了随机森林,减小了过拟合现象);

随机森林RF

随机森林是有很多随机得决策树构成,它们之间没有关联。得到RF以后,在预测时分别对每一个决策树进行判断,最后使用Bagging的思想进行结果的输出(也就是投票的思想)

学习过程

  1. 现在有N个训练样本,每个样本的特征为M个,需要建K颗树
  2. 从N个训练样本中有放回的取N个样本作为一组训练集(其余未取到的样本作为预测分类,评估其误差)
  3. 从M个特征中取m个特征左右子集特征(m<
  4. 对采样的数据使用完全分裂的方式来建立决策树,这样的决策树每个节点要么无法分裂,要么所有的样本都指向同一个分类
  5. 重复2的过程K次,即可建立森林

预测过程

  1. 将预测样本输入到K颗树分别进行预测
  2. 如果是分类问题,直接使用投票的方式选择分类频次最高的类别
  3. 如果是回归问题,使用分类之后的均值作为结果

参数问题

  1. 这里的一般取m=sqrt(M)
  2. 关于树的个数K,一般都需要成百上千,但是也有具体的样本有关(比如特征数量)
  3. 树的最大深度,(太深可能可能导致过拟合??)
  4. 节点上的最小样本数、最小信息增益

泛化误差估计

使用oob(out-of-bag)进行泛化误差的估计,将各个树的未采样样本作为预测样本(大约有36.8%),使用已经建立好的森林对各个预测样本进行预测,预测完之后最后统计误分得个数占总预测样本的比率作为RF的oob误分率。

学习算法

  1. ID3算法:处理离散值的量
  2. C45算法:处理连续值的量
  3. Cart算法:离散和连续 两者都合适?

关于CART

Cart可以通过特征的选择迭代建立一颗分类树,使得每次的分类平面能最好的将剩余数据分为两类

gini=1(pi2)

“>[Math Processing Error]

,表示每个类别出现的概率和与1的差值,
分类问题:argmax(GiniGiniLeftGiniRight)

“>[Math Processing Error]
回归问题:argmax(VarVarLeftVarRight)

“>[Math Processing Error]

查找最佳特征f已经最佳属性阈值th 小于th的在左边,大于th的在右边子树

优缺点

  1. 能够处理大量特征的分类,并且还不用做特征选择
  2. 在训练完成之后能给出哪些feature的比较重要
  3. 训练速度很快
  4. 很容易并行
  5. 实现相对来说较为简单

GBDT

GBDT的精髓在于训练的时候都是以上一颗树的残差为目标,这个残差就是上一个树的预测值与真实值的差值。

比如,当前样本年龄是18岁,那么第一颗会去按18岁来训练,但是训练完之后预测的年龄为12岁,差值为6,
所以第二颗树的会以6岁来进行训练,假如训练完之后预测出来的结果为6,那么两棵树累加起来就是真实年龄了,
但是假如第二颗树预测出来的结果是5,那么剩余的残差1就会交给第三个树去训练。

Boosting的好处就是每一步的参加就是变相了增加了分错instance的权重,而对已经对的instance趋向于0,这样后面的树就可以更加关注错分的instance的训练了

Shrinkage

Shrinkage认为,每次走一小步逐步逼近的结果要比每次迈一大步逼近结果更加容易避免过拟合。

y(1i)=y(1i1)+stepyi

“>[Math Processing Error]

就像我们做互联网,总是先解决60%用户的需求凑合着,再解决35%用户的需求,最后才关注那5%人的需求,这样就能逐渐把产品做好.

调参

  1. 树的个数 100~10000
  2. 叶子的深度 3~8
  3. 学习速率 0.01~1
  4. 叶子上最大节点树 20
  5. 训练采样比例 0.5~1
  6. 训练特征采样比例 sqrt(num)

优缺点:

优点:

  1. 精度高
  2. 能处理非线性数据
  3. 能处理多特征类型
  4. 适合低维稠密数据
    缺点:
  5. 并行麻烦(因为上下两颗树有联系)
  6. 多分类的时候 复杂度很大

BP

最小二乘法

最小二乘法是一种数学的优化技术,通过求最小化平方误差来寻找最佳的函数匹配
假设现在有二维的观测数据(x1,y1),(x2,y2)(xn,yn)

“>[Math Processing Error]

,求y=a+bx

“>[Math Processing Error]

的拟合。

现设yi=a+bxi+ki

“>[Math Processing Error]

如果有a,b

“>[Math Processing Error]能得到i=1N(|ki|)

“>[Math Processing Error]最小,则该线比较理想
所以先变为求min(i=1N(ki))

“>[Math Processing Error] ,这个与min(i=1N(ki2))

“>[Math Processing Error]等价
ki=yi(a+bxi)

“>[Math Processing Error]
那么现设f=i=1N((yi(a+bxi))2)

“>[Math Processing Error]

求其最小即可

上述就是最小二乘原则,估计a,b

“>[Math Processing Error]

的方法称为最小二乘法

先求f

“>[Math Processing Error]

a,b

“>[Math Processing Error]的偏导:

af=2i=1N(yi(a+bxi))=0

“>[Math Processing Error]

bf=2xii=1N(yi(a+bxi))=0

“>[Math Processing Error]
现设:

X=i=1NxiNY=i=1NyiN

“>[Math Processing Error]
则代入上述偏导:

aN+bNX=NYaNX+bi=1N(xi2)=i=1N(xiyi)

“>[Math Processing Error]
求该行列式:

|NNXNXi=1Nxi2|=Ni=1N((xiX))!=0

“>[Math Processing Error]

所以有唯一解

最后记:

l(xx)=i=1N(xiX)2l(yy)=i=1N(yiY)2l(xy)=i=1N((xiX)(yiY))

“>[Math Processing Error]

b=l(xy)l(xx)a=YbX

“>[Math Processing Error]

百度文库-最小二乘法

EM

EM用于隐含变量的概率模型的极大似然估计,它一般分为两步:第一步求期望(E),第二步求极大(M),
如果概率模型的变量都是观测变量,那么给定数据之后就可以直接使用极大似然法或者贝叶斯估计模型参数。
但是当模型含有隐含变量的时候就不能简单的用这些方法来估计,EM就是一种含有隐含变量的概率模型参数的极大似然估计法。

应用到的地方:混合高斯模型、混合朴素贝叶斯模型、因子分析模型

Bagging

  1. 从N样本中有放回的采样N个样本
  2. 对这N个样本在全属性上建立分类器(CART,SVM)
  3. 重复上面的步骤,建立m个分类器
  4. 预测的时候使用投票的方法得到结果

Boosting

boosting在训练的时候会给样本加一个权重,然后使loss function尽量去考虑那些分错类的样本(比如给分错类的样本的权重值加大)

凸优化

在机器学习中往往是最终要求解某个函数的最优值,但是一般情况下,任意一个函数的最优值求解比较困难,但是对于凸函数来说就可以有效的求解出全局最优值。

凸集

一个集合C是,当前仅当任意x,y属于C且0Θ1

“>[Math Processing Error]

,都有Θx+(1Θ)y

“>[Math Processing Error]

属于C
用通俗的话来说C集合线段上的任意两点也在C集合中

凸函数

一个函数f其定义域(D(f))是凸集,并且对任意x,y属于D(f)和0Θ1

“>[Math Processing Error]

都有

f(Θx+(1Θ)y)Θf(x)+(1Θ)f(y)

“>[Math Processing Error]

用通俗的话来说就是曲线上任意两点的割线都在曲线的上方

常见的凸函数有:

  • 指数函数f(x)=ax;a>1

    “>[Math Processing Error]

 

  • 负对数函数logax;a>1,x>0

    “>[Math Processing Error]

 

  • 开口向上的二次函数等

凸函数的判定:

  1. 如果f是一阶可导,对于任意数据域内的x,y满足f(y)f(x)+f(x)(yx)

    “>[Math Processing Error]

  1. 如果f是二阶可导,

凸优化应用举例

  • SVM:其中由max|w|

    “>[Math Processing Error]

转向min(12|w|2)

“>[Math Processing Error]

  • 最小二乘法?
  • LR的损失函数(yilog(hw(xi))+(1yi)(log(1hw(xi))))

    “>[Math Processing Error]

 

参考

[1]. http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html
[2]. http://www.cnblogs.com/biyeymyhjob/archive/2012/07/18/2595410.html
[3]. http://blog.csdn.net/abcjennifer/article/details/7716281
[4]. http://ufldl.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92
[5]. 《统计学习方法》.李航

备注

资料主要来源于网络或者《统计学习方法》,还有自己一小部分的总结,如果错误之处敬请指出


本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可,我的博客欢迎复制共享,但在同时,希望保留我的署名权kubiCode,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言

DeepMind成员、谷歌资深员工:神经网络序列学习突破及发展

2016-05-02 新智元

文章来源:O’Reilly 报告《The Future of Machine Intelligence)

作者:David Beyer

题目:Oriol : Sequence-to-Sequence Machine Learning

下载: future-of-machine-intelligence

【新智元导读】谷歌CEO在给投资人的信中写道谷歌搜索将更具有情景意识,其关键技术自然是深度学习。本文中,谷歌资深员工、DeepMind 成员 Oriol Vinyals 全面剖析神经网络序列学习的优势、瓶颈及解决方案。他指出机器翻译实质上是基于序列的深度学习问题,其团队希望用机器学习替代启发式算法,最后推测机器阅读并理解文本将在未来几年实现。

文章来源:O’Reilly 报告《The Future of Machine Intelligence)

作者:David Beyer

题目:Oriol Vinyals: Sequence-to-Sequence Machine Learning

关注新智元公众号,回复“0502”下载报告全文

受访者 Oriol Vinyals 是 Google 的研究科学家,在 DeepMind 团队工作,曾前在 Google Brain 团队工作。他在加州大学伯克利分校拿到 EECS 博士学位,在加州大学圣地亚哥分校拿到硕士学位。

要   点
使用神经网络的序列到序列学习(Sequence-to-sequence learning)在一些领域拥有最前沿的表现,比如机器翻译。

虽然很强大,序列到序列的学习方法也受到一些因素的制约,包括计算能力。长短期记忆(LSTM)在推动该领域前进方面作了很大贡献。

除了图像和文本理解,深度学习模型可以学会为一些著名的算法难题“编写”解决方案,其中包括邮差问题(Salesman Problem)。

机器翻译是基于序列的深度学习问题

【O’Reilly】让我们先了解一下你的背景吧。

【Oriol Vinyals】我来自西班牙巴塞罗那,在那里我完成了数学和通信工程的本科学习。很早,我就知道自己想要到美国学习 AI。我在卡耐基梅隆大学待了9个月,在那里我完成了本科毕业论文。之后我在加州大学圣地亚哥分校拿到硕士学位,然后 2009年在伯克利拿到博士学位。

读博期间,在 Google 实习时,我遇到了 Geoffrey Hinton 并和他一起工作;这段经历催化了我对深度学习的兴趣。加上我在微软和 Google 愉快的实习经历,当时我便下定决心要在产业界工作。2013 年我全职加入 Google。我起初对语音识别和优化 (重点放在自然语言处理和理解上) 有着浓厚的兴趣,后来转到使用深度学习解决这些以及别的问题这方面,包括最近基于数据来让算法自动学习的工作。

【O’Reilly】能不能谈一下你的关注点的变化,既然你离开了语言识别领域。现在最让你兴奋的是哪些领域?

【Oriol Vinyals】我的语言识别背景激发了我对序列的兴趣。最近,Ilya Sutskever, Quoc Le,还有我发表了一篇文章,是关于序列到序列映射的,可以使用循环神经网络(recurrent neural net) 进行从法语到英语的机器翻译

作为背景,监督学习在输入和输出是矢量的情形下取得了成功。往这些经典的模型输入图片,可以输出相应的类别标签。直到不久前,我们还不能通过输入图片就得到一个单词序列作为对这幅图片的描述。目前的快速进展是得益于可以获取带有图片描述的高质量数据集 (MSCOCO),以及与此并行的循环神经网络的复兴。

我们的工作把机器翻译问题重塑为基于序列的深度学习问题。结果表明深度学习可以把英语的单词序列映射为西班牙语的单词序列。由于深度学习令人吃惊的能力,我们可以相当快地达到领域前沿水平。这些结果本身暗示了新的应用,比如,自动把视频提炼成四个描述性句子。

序列到序列的瓶颈及解决方法 

【O’Reilly】序列到序列这种方法在什么地方工作得不好?

 

【Oriol Vinyals】假设你要把一个英语句子翻译成法语。你可以使用一个巨大的政治言论和辩论语料库作为训练数据。应用得当的话,你可以把政治言论转化为任何别的语言。但是,当你试图把——比如说——莎士比亚式的英语——翻译成法语的时候,你会遇到问题。这种领域切换对深度学习方法压力比较大,而传统机器翻译系统是基于规则的,这让它们能适应这种切换。

还有更多的难点。当序列长度超过一定值时,我们缺乏相应的计算能力。当前的模型可以把长度为 200 的序列与对应的同样长度的序列匹配。当序列变长,运行时间也变长。虽然目前我们被局限于相对较短的文档,我相信随着时间推移这个限制会越来越宽松。正如 GPU 压缩了大而复杂的模型的运行时间,内存和计算能力的提高会让可计算的序列越来越长。

除了计算的瓶颈,更长的序列还带来了有趣的数学问题。若干年前 Hochreiter 引入了梯度消失的概念。当你阅读数千个单词,你很容易忘掉三千个单词前的信息;如果不记得第三章的关键情节转换,(小说的) 结局就失去意义。从结果上讲,挑战来自记忆。循环神经网络一般能记住 10 到 15 个词。但如果你把一个矩阵乘 15 次,输出会收缩到 0。换句话说,梯度消失,学习变得不可能。

 

这个问题的一种重要解决方案依赖于长短期记忆 (LSTM)。这种结构对循环神经网络做了聪明的修改,让它们能记住远超正常极限的东西。我见过能记住 300 到 400 个词的 LSTM。虽然已经相当长了,这样的增长只是个开始,以后的神经网络将能处理日常生活规模的文本。

退一步讲,近几年我们看到出现了一些处理记忆问题的模型。我个人尝试过添加这种记忆到神经网络:与其把所有东西塞进循环神经网络的隐含态,记忆让你回忆起之前见过的词,从而帮助解决手头的优化任务。虽然这些年进展迅速,更深层的、关于知识表达究竟意味着什么这一挑战仍然存在,并且其本身仍旧是一个开放问题。尽管如此,我相信接下来我们会看到沿着这些方向的重大进展。

用机器学习代替启发式算法

【O’Reilly】让我们换个话题,谈谈你在算法生成方面的工作。你能不能讲讲这些努力背后的历史和动机?

【Oriol Vinyals】一个展示监督学习能力的经典练习涉及到把一些给定点分割为不同类别:这是 A 类,这是 B 类,等等。XOR (异或) (the“exclusive or” logical connective) 问题特别有教益。目标是要学会异或操作,也就是,给定两个二进制位作为输入,学习正确的输出。精确地讲,这涉及到两个位也就是四个实例:00,01,10,11。对于这些例子,输出是 0,1,1,0。这个问题不是线性模型能解决的,但深度学习可以。即便如此,目前计算能力的限制排除了更复杂的问题。

 

最近,Wojciech Zaremba (我们组的一个实习生) 发表了一篇文章,标题是“Learningto Execute”,描述了一个基于循环神经网络的从 Python 程序到执行这些程序的结果的映射。这个模型可以仅仅通过阅读源代码来预测 Python 程序的结果。这个问题虽然看起来简单,提供了一个良好开端。于是我把注意力转向一个 NP-hard 问题。

 

我们考虑的是一个高度复杂且资源需求高的方法,用来求解经过所有点的最短路径的问题,也就是著名的邮差问题。这个问题从提出开始,就吸引了大量解法;人们发明了各种启发式算法,在效率和精度之间求得平衡。在我们的情形,我们研究了深度学习系统是否能仅仅基于训练数据推断出与已有文献比肩的启发式算法。

出于效率的考虑,我们只考虑 10 个城市,而不是常见的10000 或 100000 个。我们的训练集输入城市位置,输出最短路径。就这样。我们不想让网络知晓任何别的关于这个问题的假设。

成功的神经网络应该能再现遍历所有点且最小化路程的行为。事实上,在一个可以称作奇迹的时刻,我们发现它能做到。

我应该补充一下,输出可能不是最优,因为毕竟是概率性的;但这是个好的开始。我们希望把这个方法应用到一些新问题。目标不是为了替换现有的、人工编码的解决方案,而是,我们要用机器学习代替启发式算法。

【O’Reilly】这会最终让我们成为更好的程序员吗?

【Oriol Vinyals】比如在编程竞赛中。开始是一段问题陈述,用直白的英语写:“在这个程序中,你需要找出 A,B,C,在 X,Y,以及 Z 的前提下。” 你编码你的解决方案,然后在服务器上测试。与此不同的是,想象一下,一个神经网络读入这样一个自然语言写的问题陈述,然后学到一个至少能给出近似解的算法,甚至能给出精确解。这个图景可能听起来太遥远。记住,仅仅几年前,读入 Python 程序然后输出答案也是听起来相当不靠谱的。

 未来几年机器能阅读并理解文本

【O’Reilly】你怎么看待接下来五年你的工作会如何进展?最大的未解决问题有哪些?

【Oriol Vinyals】也许五年的时间有点紧,但机器阅读并理解一本书这样的事不会离我们很远。类似地,我们可以预期看到机器通过从数据学习来回答问题,而不是基于给定的规则集合。现在如果我问你一个问题,你打开 Google 开始搜索;几次尝试后你可能得到答案。跟你一样,机器应该能返回一个答案作为对某个问题的响应。我们已经有沿着这个方向基于紧凑数据集的模型。更往前的挑战是深刻的:你如何区分正确和错误的答案?如何量化正确和错误?这些以及别的重要问题决定未来研究的进程。

谷歌搜索算法如何排名医疗广告?

2016-05-02 新智元

 新智元原创1

【新智元导读】青年魏则西的不幸病逝激起了国内公众对搜索引擎虚假医疗网络广告问题的热议。提到搜索引擎,必须想到谷歌,那么谷歌是如何处理医疗广告的呢,答案是使用机器学习的RankBrain算法。

青年魏则西的不幸病逝,激起了国内公众对搜索引擎虚假医疗网络广告问题的热议。根据《商业价值》微信公众号今日文章《谷歌也曾涉足医疗广告,美国司法是如何监管的呢?》,可以发现在谷歌搜索“滑膜肉瘤”也会出医疗广告,但都有明显的“Ad”标识。同时,与百度相比,谷歌的付费广告并不影响排名。

谷歌关于滑膜肉瘤治疗的搜索广告,有明确的广告标志。来源:商业价值

此外,《商业价值》文中提到,根据谷歌的搜索广告政策,要投放药品广告需要获得 FDA 以及美国药房理事会(NABP)认证。也就是说,只有获得政府审批的正规网上药店、药品与治疗才能在网站投放药品类广告。同时,谷歌的自动广告过滤机制,在很大程度上也能有效杜绝虚假医疗广告出现。根据谷歌发布的报告,他们 2015 年总计预先屏蔽了 7.8 亿条违规广告,封杀 21.4 万家广告商,其中包括 1250 万条违规的医疗和药品广告,涉及药品未获批准或者虚假误导性宣传等原因。

谷歌如何用算法排名

据统计,每天向 Google 提交的查询中有约 15% 是其未曾见过的。公司的资深研究科学家 Greg Corrado 透露,为了更好回答这些问题,Google 利用了 RankBrain 来将海量的书面语嵌入到计算机可以理解的向量里面。

如果 RankBrain 看到自己不熟悉的单词或短语,它会去猜测其类似的意思并对结果进行相应过滤,从而有效地处理一些从未见过的搜索查询。比方说 RankBrain 能够有效回答 “What’ s the title of the consumer at the highest level of a food chain?(食物链当中最高级的消费者的头衔叫做什么?)” 这样的问题。

对于 Google 的搜索处理机制来说,RankBrain 只是为其搜索算法提供输入的数百个信号之一,但这种信号跟别的信号的不同之处在于它懂得学习,而别的只是别人在信息获取中的发现和洞察。Google 内部曾让做算法的工程师人工去猜测搜索算法会选择哪个页面作为排名第一的结果,其准确率为 70%,然后 RankBrain 去做了同样的事情,准确率达到了 80%,超过了做算法的工程师的平均水平。

随着时间的推移,RankBrain 可能能够处理越来越多的当前通过手写代码分析来改善 Google 算法的各种各样的信号。Google 的各项业务也会发展地越来越智能。机器学习将会以各种有意义的方式整合进 Google 的搜索引擎中。Google 这所有的举动将会继续保持其搜索引擎的领头地位。

RankBrain 运行原理解析

RankBrain 是 Google 蜂鸟搜索算法的一部分。蜂鸟是整个搜索算法,就好比车里面有个引擎。引擎本身可能由许多部分组成,比如滤油器、燃油泵、散热器等。同理,蜂鸟也由多个部分组成,RankBrain就是其中一个组成部分。

蜂鸟同时包含其他的部分,这些名字对 SEO圈的人来说已经耳熟能详了,比如 Panda、 Penguin 和 Payday 用于垃圾邮件过滤, Pigeon 用于优化本地结果, Top Heavy 用于给广告太多的页面降级,Mobile Friendly 用于给移动友好型页面加分,Pirate 用于打击版权侵犯。

Google 用于排序的“信号”是什么?

Google 使用信号来决定如何为网页排序。比如,它会读取网页上的词语,那么词语就是一个信号。如果某些词语是粗体,那么这又是一个值得注意的信号。计算的结果作为PageRank的一部分,给一个网页设定一个PageRank分数,这作为一个信号。如果一张网页被检测到是移动友好型的,那么这又会成为一个信号。所有的这些信号都由蜂鸟算法中的各个部分处理,最后决定针对不同搜索返回哪些网页。

一共有多少种信号?

Google 称进行评估的主要排序信号大约有 200多种,反过来, 可能有上万种变种信号或者子信号。如果你想有一个更直观的排序信号向导,来看看 Google SEO成功因素元素周期表:

RankBrain到底做什么?

从与 Google 的来往电子邮件之中,RankBrain 主要用于翻译人们可能不清楚该输入什么确切词语的搜索词条。

Google 很早就找到不根据具体词条搜索页面的方式。比如,许多年前,如果你输入“鞋”(shoe), Google 可能不会找到那些有“鞋”(shoes)的页面,因为从技术上来说这是两个不同的词汇,但是“stemming”使得 Google 变得更聪明,让引擎了解shoes的词根是shoe,就像“running”的词根是“run”。 Google 同样了解同义词,因此,如果你搜索“运动鞋”,它可能知道你想找“跑鞋”。它甚至有概念性的知识,知道哪些网页是关于“苹果”公司,哪些是关于水果“苹果”的。

参考资料:

http://mp.weixin.qq.com/s?__biz=MTA2MTMwNjYwMQ==&mid=2650693625&idx=1&sn=8ab532faa66e69cc447e250f58807dda&scene=1&srcid=0502LFwayyLBIMhASaZX4zrt#rd

10 种机器学习算法的要点

2015-10-24 伯乐在线 程序员的那些事

前言

谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和机器人受到了许多媒体关注,但是这家公司真正的未来在于机器学习,一种让计算机更聪明、更个性化的技术。

也许我们生活在人类历史上最关键的时期:从使用大型计算机,到个人电脑,再到现在的云计算。关键的不是过去发生了什么,而是将来会有什么发生。

工具和技术的民主化,让像我这样的人对这个时期兴奋不已。计算的蓬勃发展也是一样。如今,作为一名数据科学家,用复杂的算法建立数据处理机器一小时能赚到好几美金。但能做到这个程度可并不简单!我也曾有过无数黑暗的日日夜夜。

谁能从这篇指南里受益最多?

我今天所给出的,也许是我这辈子写下的最有价值的指南。

这篇指南的目的,是为那些有追求的数据科学家和机器学习狂热者们,简化学习旅途。这篇指南会让你动手解决机器学习的问题,并从实践中获得真知。我提供的是几个机器学习算法的高水平理解,以及运行这些算法的 R 和 Python 代码。这些应该足以让你亲自试一试了。

我特地跳过了这些技术背后的数据,因为一开始你并不需要理解这些。如果你想从数据层面上理解这些算法,你应该去别处找找。但如果你想要在开始一个机器学习项目之前做些准备,你会喜欢这篇文章的。

广义来说,有三种机器学习算法

1、 监督式学习

工作机制:这个算法由一个目标变量或结果变量(或因变量)组成。这些变量由已知的一系列预示变量(自变量)预测而来。利用这一系列变量,我们生成一个将输入值映射到期望输出值的函数。这个训练过程会一直持续,直到模型在训练数据上获得期望的精确度。监督式学习的例子有:回归、决策树、随机森林、K – 近邻算法、逻辑回归等。

2、非监督式学习

工作机制:在这个算法中,没有任何目标变量或结果变量要预测或估计。这个算法用在不同的组内聚类分析。这种分析方式被广泛地用来细分客户,根据干预的方式分为不同的用户组。非监督式学习的例子有:关联算法和 K – 均值算法。

3、强化学习

工作机制:这个算法训练机器进行决策。它是这样工作的:机器被放在一个能让它通过反复试错来训练自己的环境中。机器从过去的经验中进行学习,并且尝试利用了解最透彻的知识作出精确的商业判断。 强化学习的例子有马尔可夫决策过程。

常见机器学习算法名单

这里是一个常用的机器学习算法名单。这些算法几乎可以用在所有的数据问题上:

  • 线性回归
  • 逻辑回归
  • 决策树
  • SVM
  • 朴素贝叶斯
  • K最近邻算法
  • K均值算法
  • 随机森林算法
  • 降维算法
  • Gradient Boost 和 Adaboost 算法

1、线性回归

线性回归通常用于根据连续变量估计实际数值(房价、呼叫次数、总销售额等)。我们通过拟合最佳直线来建立自变量和因变量的关系。这条最佳直线叫做回归线,并且用 Y= a *X + b 这条线性等式来表示。

理解线性回归的最好办法是回顾一下童年。假设在不问对方体重的情况下,让一个五年级的孩子按体重从轻到重的顺序对班上的同学排序,你觉得这个孩子会怎么做?他(她)很可能会目测人们的身高和体型,综合这些可见的参数来排列他们。这是现实生活中使用线性回归的例子。实际上,这个孩子发现了身高和体型与体重有一定的关系,这个关系看起来很像上面的等式。

在这个等式中:

  • Y:因变量
  • a:斜率
  • x:自变量
  • b :截距

系数 a 和 b 可以通过最小二乘法获得。

参见下例。我们找出最佳拟合直线 y=0.2811x+13.9。已知人的身高,我们可以通过这条等式求出体重。

线性回归的两种主要类型是一元线性回归和多元线性回归。一元线性回归的特点是只有一个自变量。多元线性回归的特点正如其名,存在多个自变量。找最佳拟合直线的时候,你可以拟合到多项或者曲线回归。这些就被叫做多项或曲线回归。

Python 代码

#Import Library
#Import other necessary libraries like pandas, numpy...
from sklearn import linear_model
#Load Train and Test datasets
#Identify feature and response variable(s) and values must be numeric and numpy arrays
x_train=input_variables_values_training_datasets
y_train=target_variables_values_training_datasets
x_test=input_variables_values_test_datasets
# Create linear regression object
linear = linear_model.LinearRegression()
# Train the model using the training sets and check score
linear.fit(x_train, y_train)
linear.score(x_train, y_train)
#Equation coefficient and Intercept
print('Coefficient: n', linear.coef_)
print('Intercept: n', linear.intercept_)
#Predict Output
predicted= linear.predict(x_test)

R代码

#Load Train and Test datasets
#Identify feature and response variable(s) and values must be numeric and numpy arrays
x_train <- input_variables_values_training_datasets
y_train <- target_variables_values_training_datasets
x_test <- input_variables_values_test_datasets
x <- cbind(x_train,y_train)
# Train the model using the training sets and check score
linear <- lm(y_train ~ ., data = x)
summary(linear)
#Predict Output
predicted= predict(linear,x_test)

2、逻辑回归

别被它的名字迷惑了!这是一个分类算法而不是一个回归算法。该算法可根据已知的一系列因变量估计离散数值(比方说二进制数值 0 或 1 ,是或否,真或假)。简单来说,它通过将数据拟合进一个逻辑函数来预估一个事件出现的概率。因此,它也被叫做逻辑回归。因为它预估的是概率,所以它的输出值大小在 0 和 1 之间(正如所预计的一样)。

让我们再次通过一个简单的例子来理解这个算法。

假设你的朋友让你解开一个谜题。这只会有两个结果:你解开了或是你没有解开。想象你要解答很多道题来找出你所擅长的主题。这个研究的结果就会像是这样:假设题目是一道十年级的三角函数题,你有 70%的可能会解开这道题。然而,若题目是个五年级的历史题,你只有30%的可能性回答正确。这就是逻辑回归能提供给你的信息。

从数学上看,在结果中,几率的对数使用的是预测变量的线性组合模型。

odds= p/ (1-p) = probability of event occurrence / probability of not event occurrence
ln(odds) = ln(p/(1-p))
logit(p) = ln(p/(1-p)) = b0+b1X1+b2X2+b3X3....+bkXk

在上面的式子里,p 是我们感兴趣的特征出现的概率。它选用使观察样本值的可能性最大化的值作为参数,而不是通过计算误差平方和的最小值(就如一般的回归分析用到的一样)。

现在你也许要问了,为什么我们要求出对数呢?简而言之,这种方法是复制一个阶梯函数的最佳方法之一。我本可以更详细地讲述,但那就违背本篇指南的主旨了。

Python代码

#Import Library
from sklearn.linear_model import LogisticRegression
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create logistic regression object
model = LogisticRegression()
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Equation coefficient and Intercept
print('Coefficient: n', model.coef_)
print('Intercept: n', model.intercept_)
#Predict Output
predicted= model.predict(x_test)

R代码

x <- cbind(x_train,y_train)
# Train the model using the training sets and check score
logistic <- glm(y_train ~ ., data = x,family='binomial')
summary(logistic)
#Predict Output
predicted= predict(logistic,x_test)

更进一步:

你可以尝试更多的方法来改进这个模型:

  • 加入交互项
  • 精简模型特性
  • 使用正则化方法
  • 使用非线性模型

3、决策树

这是我最喜爱也是最频繁使用的算法之一。这个监督式学习算法通常被用于分类问题。令人惊奇的是,它同时适用于分类变量和连续因变量。在这个算法中,我们将总体分成两个或更多的同类群。这是根据最重要的属性或者自变量来分成尽可能不同的组别。想要知道更多,可以阅读:简化决策树。

来源: statsexchange

在上图中你可以看到,根据多种属性,人群被分成了不同的四个小组,来判断 “他们会不会去玩”。为了把总体分成不同组别,需要用到许多技术,比如说 Gini、Information Gain、Chi-square、entropy。

理解决策树工作机制的最好方式是玩Jezzball,一个微软的经典游戏(见下图)。这个游戏的最终目的,是在一个可以移动墙壁的房间里,通过造墙来分割出没有小球的、尽量大的空间。

因此,每一次你用墙壁来分隔房间时,都是在尝试着在同一间房里创建两个不同的总体。相似地,决策树也在把总体尽量分割到不同的组里去。

更多信息请见:决策树算法的简化

Python代码

#Import Library
#Import other necessary libraries like pandas, numpy...
from sklearn import tree
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create tree object
model = tree.DecisionTreeClassifier(criterion='gini') # for classification, here you can change the algorithm as gini or entropy (information gain) by default it is gini
# model = tree.DecisionTreeRegressor() for regression
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Predict Output
predicted= model.predict(x_test)

R语言

library(rpart)
x <- cbind(x_train,y_train)
# grow tree
fit <- rpart(y_train ~ ., data = x,method="class")
summary(fit)
#Predict Output
predicted= predict(fit,x_test)

4、支持向量机

这是一种分类方法。在这个算法中,我们将每个数据在N维空间中用点标出(N是你所有的特征总数),每个特征的值是一个坐标的值。

举个例子,如果我们只有身高和头发长度两个特征,我们会在二维空间中标出这两个变量,每个点有两个坐标(这些坐标叫做支持向量)。

现在,我们会找到将两组不同数据分开的一条直线。两个分组中距离最近的两个点到这条线的距离同时最优化。

上面示例中的黑线将数据分类优化成两个小组,两组中距离最近的点(图中A、B点)到达黑线的距离满足最优条件。这条直线就是我们的分割线。接下来,测试数据落到直线的哪一边,我们就将它分到哪一类去。

更多请见:支持向量机的简化

将这个算法想作是在一个 N 维空间玩 JezzBall。需要对游戏做一些小变动:

  • 比起之前只能在水平方向或者竖直方向画直线,现在你可以在任意角度画线或平面。
  • 游戏的目的变成把不同颜色的球分割在不同的空间里。
  • 球的位置不会改变。

Python代码

#Import Library
from sklearn import svm
#Assumed you have, X (predic
tor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create SVM classification object
model = svm.svc() # there is various option associated with it, this is simple for classification. You can refer link, for mo# re detail.
# Train the model using the training sets and check score
model.fit(X, y)
model.score(X, y)
#Predict Output
predicted= model.predict(x_test)

R代码

library(e1071)
x <- cbind(x_train,y_train)
# Fitting model
fit <-svm(y_train ~ ., data = x)
summary(fit)
#Predict Output
predicted= predict(fit,x_test)

5、朴素贝叶斯

在预示变量间相互独立的前提下,根据贝叶斯定理可以得到朴素贝叶斯这个分类方法。用更简单的话来说,一个朴素贝叶斯分类器假设一个分类的特性与该分类的其它特性不相关。举个例子,如果一个水果又圆又红,并且直径大约是 3 英寸,那么这个水果可能会是苹果。即便这些特性互相依赖,或者依赖于别的特性的存在,朴素贝叶斯分类器还是会假设这些特性分别独立地暗示这个水果是个苹果。

朴素贝叶斯模型易于建造,且对于大型数据集非常有用。虽然简单,但是朴素贝叶斯的表现却超越了非常复杂的分类方法。

贝叶斯定理提供了一种从P(c)、P(x)和P(x|c) 计算后验概率 P(c|x) 的方法。请看以下等式:

在这里,

  • P(c|x) 是已知预示变量(属性)的前提下,类(目标)的后验概率
  • P(c) 是类的先验概率
  • P(x|c) 是可能性,即已知类的前提下,预示变量的概率
  • P(x) 是预示变量的先验概率

例子:让我们用一个例子来理解这个概念。在下面,我有一个天气的训练集和对应的目标变量“Play”。现在,我们需要根据天气情况,将会“玩”和“不玩”的参与者进行分类。让我们执行以下步骤。

步骤1:把数据集转换成频率表。

步骤2:利用类似“当Overcast可能性为0.29时,玩耍的可能性为0.64”这样的概率,创造 Likelihood 表格。

步骤3:现在,使用朴素贝叶斯等式来计算每一类的后验概率。后验概率最大的类就是预测的结果。

问题:如果天气晴朗,参与者就能玩耍。这个陈述正确吗?

我们可以使用讨论过的方法解决这个问题。于是 P(会玩 | 晴朗)= P(晴朗 | 会玩)* P(会玩)/ P (晴朗)

我们有 P (晴朗 |会玩)= 3/9 = 0.33,P(晴朗) = 5/14 = 0.36, P(会玩)= 9/14 = 0.64

现在,P(会玩 | 晴朗)= 0.33 * 0.64 / 0.36 = 0.60,有更大的概率。

朴素贝叶斯使用了一个相似的方法,通过不同属性来预测不同类别的概率。这个算法通常被用于文本分类,以及涉及到多个类的问题。

Python代码

#Import Library
from sklearn.naive_bayes import GaussianNB
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create SVM classification object model = GaussianNB() # there is other distribution for multinomial classes like Bernoulli Naive Bayes, Refer link
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R代码

library(e1071)
x <- cbind(x_train,y_train)
# Fitting model
fit <-naiveBayes(y_train ~ ., data = x)
summary(fit)
#Predict Output
predicted= predict(fit,x_test)

6、KNN(K – 最近邻算法)

该算法可用于分类问题和回归问题。然而,在业界内,K – 最近邻算法更常用于分类问题。K – 最近邻算法是一个简单的算法。它储存所有的案例,通过周围k个案例中的大多数情况划分新的案例。根据一个距离函数,新案例会被分配到它的 K 个近邻中最普遍的类别中去。

这些距离函数可以是欧式距离、曼哈顿距离、明式距离或者是汉明距离。前三个距离函数用于连续函数,第四个函数(汉明函数)则被用于分类变量。如果 K=1,新案例就直接被分到离其最近的案例所属的类别中。有时候,使用 KNN 建模时,选择 K 的取值是一个挑战。

更多信息:K – 最近邻算法入门(简化版)

我们可以很容易地在现实生活中应用到 KNN。如果想要了解一个完全陌生的人,你也许想要去找他的好朋友们或者他的圈子来获得他的信息。

在选择使用 KNN 之前,你需要考虑的事情:

  • KNN 的计算成本很高。
  • 变量应该先标准化(normalized),不然会被更高范围的变量偏倚。
  • 在使用KNN之前,要在野值去除和噪音去除等前期处理多花功夫。

Python代码

#Import Library
from sklearn.neighbors import KNeighborsClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create KNeighbors classifier object model
KNeighborsClassifier(n_neighbors=6) # default value for n_neighbors is 5
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R代码

library(knn)
x <- cbind(x_train,y_train)
# Fitting model
fit <-knn(y_train ~ ., data = x,k=5)
summary(fit)
#Predict Output
predicted= predict(fit,x_test)

7、K 均值算法

K – 均值算法是一种非监督式学习算法,它能解决聚类问题。使用 K – 均值算法来将一个数据归入一定数量的集群(假设有 k 个集群)的过程是简单的。一个集群内的数据点是均匀齐次的,并且异于别的集群。

还记得从墨水渍里找出形状的活动吗?K – 均值算法在某方面类似于这个活动。观察形状,并延伸想象来找出到底有多少种集群或者总体。

K – 均值算法怎样形成集群:

  • K – 均值算法给每个集群选择k个点。这些点称作为质心。
  • 每一个数据点与距离最近的质心形成一个集群,也就是 k 个集群。
  • 根据现有的类别成员,找出每个类别的质心。现在我们有了新质心。
  • 当我们有新质心后,重复步骤 2 和步骤 3。找到距离每个数据点最近的质心,并与新的k集群联系起来。重复这个过程,直到数据都收敛了,也就是当质心不再改变。

如何决定 K 值:

K – 均值算法涉及到集群,每个集群有自己的质心。一个集群内的质心和各数据点之间距离的平方和形成了这个集群的平方值之和。同时,当所有集群的平方值之和加起来的时候,就组成了集群方案的平方值之和。

我们知道,当集群的数量增加时,K值会持续下降。但是,如果你将结果用图表来表示,你会看到距离的平方总和快速减少。到某个值 k 之后,减少的速度就大大下降了。在此,我们可以找到集群数量的最优值。

Python代码

#Import Library
from sklearn.cluster import KMeans
#Assumed you have, X (attributes) for training data set and x_test(attributes) of test_dataset
# Create KNeighbors classifier object model
k_means = KMeans(n_clusters=3, random_state=0)
# Train the model using the training sets and check score
model.fit(X)
#Predict Output
predicted= model.predict(x_test)

8、随机森林

随机森林是表示决策树总体的一个专有名词。在随机森林算法中,我们有一系列的决策树(因此又名“森林”)。为了根据一个新对象的属性将其分类,每一个决策树有一个分类,称之为这个决策树“投票”给该分类。这个森林选择获得森林里(在所有树中)获得票数最多的分类。

每棵树是像这样种植养成的:

  1. 如果训练集的案例数是 N,则从 N 个案例中用重置抽样法随机抽取样本。这个样本将作为“养育”树的训练集。
  2. 假如有 M 个输入变量,则定义一个数字 m<
  3. 尽可能大地种植每一棵树,全程不剪枝。

若想了解这个算法的更多细节,比较决策树以及优化模型参数,我建议你阅读以下文章:

  1. 随机森林入门—简化版
  2. 将 CART 模型与随机森林比较(上)
  3. 将随机森林与 CART 模型比较(下)
  4. 调整你的随机森林模型参数

Python

#Import Library
from sklearn.ensemble import RandomForestClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create Random Forest object
model= RandomForestClassifier()
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R代码

library(randomForest)
x <- cbind(x_train,y_train)
# Fitting model
fit <- randomForest(Species ~ ., x,ntree=500)
summary(fit)
#Predict Output
predicted= predict(fit,x_test)

9、降维算法

在过去的 4 到 5 年里,在每一个可能的阶段,信息捕捉都呈指数增长。公司、政府机构、研究组织在应对着新资源以外,还捕捉详尽的信息。

举个例子:电子商务公司更详细地捕捉关于顾客的资料:个人信息、网络浏览记录、他们的喜恶、购买记录、反馈以及别的许多信息,比你身边的杂货店售货员更加关注你。

作为一个数据科学家,我们提供的数据包含许多特点。这听起来给建立一个经得起考研的模型提供了很好材料,但有一个挑战:如何从 1000 或者 2000 里分辨出最重要的变量呢?在这种情况下,降维算法和别的一些算法(比如决策树、随机森林、PCA、因子分析)帮助我们根据相关矩阵,缺失的值的比例和别的要素来找出这些重要变量。

想要知道更多关于该算法的信息,可以阅读《降维算法的初学者指南》。

Python代码

#Import Library
from sklearn import decomposition
#Assumed you have training and test data set as train and test
# Create PCA obeject pca= decomposition.PCA(n_components=k) #default value of k =min(n_sample, n_features)
# For Factor analysis
#fa= decomposition.FactorAnalysis()
# Reduced the dimension of training dataset using PCA
train_reduced = pca.fit_transform(train)
#Reduced the dimension of test dataset
test_reduced = pca.transform(test)
#For more detail on this, please refer this link.

R Code

library(stats)
pca <- princomp(train, cor = TRUE)
train_reduced <- predict(pca,train)
test_reduced <- predict(pca,test)

10、Gradient Boosting 和 AdaBoost 算法

当我们要处理很多数据来做一个有高预测能力的预测时,我们会用到 GBM 和 AdaBoost 这两种 boosting 算法。boosting 算法是一种集成学习算法。它结合了建立在多个基础估计值基础上的预测结果,来增进单个估计值的可靠程度。这些 boosting 算法通常在数据科学比赛如 Kaggl、AV Hackathon、CrowdAnalytix 中很有效。

更多:详尽了解 Gradient 和 AdaBoost

Python代码

#Import Library
from sklearn.ensemble import GradientBoostingClassifier
#Assumed you have, X (predictor) and Y (target) for training data set and x_test(predictor) of test_dataset
# Create Gradient Boosting Classifier object
model= GradientBoostingClassifier(n_estimators=100, learning_rate=1.0, max_depth=1, random_state=0)
# Train the model using the training sets and check score
model.fit(X, y)
#Predict Output
predicted= model.predict(x_test)

R code

library(caret)
x <- cbind(x_train,y_train)
# Fitting model
fitControl <- trainControl( method = "repeatedcv", number = 4, repeats = 4)
fit <- train(y ~ ., data = x, method = "gbm", trControl = fitControl,verbose = FALSE)
predicted= predict(fit,x_test,type= "prob")[,2]

结语GradientBoostingClassifier 和随机森林是两种不同的 boosting 树分类器。人们常常问起这两个算法之间的区别。

现在我能确定,你对常用的机器学习算法应该有了大致的了解。写这篇文章并提供 Python 和 R 语言代码的唯一目的,就是让你立马开始学习。

如果你想要掌握机器学习,那就立刻开始吧。做做练习,理性地认识整个过程,应用这些代码,并感受乐趣吧!

国内云计算的缺失环节: GPU并行计算

2016-05-03 祁海江博士 智能投资研究院

祁海江:青岛五脉泉信息有限公司技术主管,宾夕法尼亚大学博士,南京大学硕士。多年从事图形图像、3D视觉、神经计算、机器学习等算法研究。

【IT时代周刊编者按】云计算特有的优点和巨大的商业前景,让其成为了近年来的IT界最热门词汇之一。当然,这也与中国移动互联网的繁荣紧密相关,它们需要有相应的云计算服务作为支撑。但本文作者祁海江结合自身的经验,对国内目前的云计算服务进行观察后认为,国内云服务商多数采用过于简单粗放的“远程机房+移动大硬盘”模式,不能满足并行图形处理的计算需求,“应认清技术潮流,整合前沿计算工具,尽快推进云GPU并行计算服务,促进中国移动互联网整体技术水准攀升。”那么云GPU并行计算服务有多重要?作者在文中作了深入浅出的解读,字里行间也能一窥国内云服务的夸大与事实上的落后现状。

很长时间以来,云计算成了一个热闹词汇。那么到底什么是云计算呢?它本质上是一种社会智力资源的共享,通过云端的技术封包,降低了难度门槛,使得更多用户可以采用各种原本“很难很先进”的技术。

这种技术可以应用到什么地方呢?我们看到现在中国的移动互联新经济高度繁荣,这就需要有相应技术高度的云计算服务作为龙骨支撑。但现在中国的云服务商多数采用过于简单粗放的“远程机房+移动大硬盘”模式,不能满足并行图形处理的计算需求。按照当今计算技术的趋向看——“视频音图+3D+规模机器学习+大数据分析=》高强度计算任务=》云GPU并行运算”,运营商应尽快认清技术潮流,整合前沿计算工具,尽快推进云GPU并行计算服务。这是因为:

1:现行的图形、图像及3D计算在各种视频游戏、电影产业、工业设计、医疗成像、空间探索、远程通讯等方面有着广泛的应用。

        随着计算机技术的发展,人们对图形和图像的处理要求也越来越高,尤其现在兴起的3D技术,使图形图像处理和3D计算已经应用到了各种视频游戏,电影产业,医疗成像,空间探索,远程通信等各个方面。

现在风靡的大型3D游戏,诸如《使命召唤》《极品飞车》等,这些游戏画面逼真,3D特效强烈,所以要求计算机对图形图像的处理能力要求也非常高。 2010年放映的电影《阿凡达》开创了动画形象代替了演员的3D电影的先河,它完美的运用了3D立体画面的创造了逼真的效果使画面美轮美奂。在工业设计上,有很多广为人们熟知的3D处理软件,例如AutoCAD,Maya,SolidWorks等知名软件。在医疗成像方面,3D/4D立体成像技术,使医护人员可以获得从传统平面显示无法捕捉到的信息数据,能够360度全方位立体读取影像信息,为临床诊断提供了更丰富、精准的影像资料,大幅度降低了对病灶的漏诊,提高了诊疗质量,必将掀起医疗影像信息处理的一次技术革命。

伴随着IT互联网以及手持终端的发展和普及,要处理的数据量的爆发式增长,手机上也出现了3D游戏的发展趋势,这些都对数据图像和3D计算提出了更多的需求。

由此看来,目前对图形图像以及3D计算的巨大需求,已经要求计算机需要具备强大的3D建模能力,然而CPU的串行处理能力远不能满足高效的处理图像以及3D计算的能力,因此并行计算技术的使用日益广泛。

2:以美国NVIDIA公司图形显示卡的CUDA运算包为代表的GPU并行运算技术,已成为工作站、服务器、个人电脑的标准组件。

       GPU是电脑图形显示卡上负责图像运算工作的微处理器。著名的显示卡公司NVIDIA为其主流显卡产品设计了专门的GPU并行计算工具包,称之为CUDA(ComputeUnifiedDeviceArchitecture,统一计算架构)。

以GeForce8800GTX为例,其核心拥有128个内处理器。利用CUDA技术,就可以将那些内处理器串通起来,成为线程处理器去解决数据密集的计算。而各个内处理器能够交换、同步和共享数据。利用NVIDIA的C-编译器,通过驱动程序,就能利用这些功能。亦能成为流处理器,让应用程序利用进行运算。GeForce8800GTX显示卡的运算能力可达到520GFlops,如果建设SLI系统,就可以达到1TFlops。

有软件厂商利用CUDA技术,研发了一个AdobePremierePro的插件。通过插件,用户就可以利用显示核心去加速H.264/MPEG-4AVC的编码速度。速度是单纯利用CPU作软件加速的7倍左右。

NVIDIA从所有基于G80及之后架构的民用与专业显卡或运算模块皆支持CUDA技术。整体运算能力比单纯利用CPU的速度提高7倍甚至更高。TeslaGPU是针对工作站和服务器的加速器,与消费级显卡和专业图形卡相比,具有完整的双精度浮点运算性能,具备双DMA引擎可满足双向PCIe通信,板载内存达到12G(TeslaK40GPU),具有专门的Linux补丁、InfiniBand驱动程序以及CUDA驱动程序,针对Windows 操作系统的CUDA驱动程序可实现更高性能,TCC驱动程序可减少CUDA内核的系统总开销并支持远程桌面(WindowsRemoteDesktop) 以及Windows服务。

3:以CUDA为代表的GPU并行计算技术,在多个领域已发挥重要作用。

  • 在科研界,CUDA应用广泛。例如,CUDA现已能够对AMBER进行加速。AMBER是一款分子动力学模拟程序,全世界在学术界与制药企业中有超过60,000名研究人员使用该程序来加速新药的探索工作。
  • 在金融市场,Numerix以及CompatibL针对一款全新的对手风险应用程序发布了CUDA支持并取得了18倍速度提升。Numerix为近400家金融机构所广泛使用。
  • 在消费级市场上,几乎每一款重要的消费级视频应用程序都已经使用CUDA加速或很快将会利用CUDA来加速,其中不乏ElementalTechnologies公司、MotionDSP公司以及LoiLo公司的产品。

4:NVIDIA公司非常重视GPU并行计算在云服务器上的嫁接,美国已有数家云服务商提供GPU并行的云计算服务

  • 2009年10月20日,NVIDIA与Mentalimages联合推出一款基于云计算的高端服务器——RealityServer。
  • 2012年5月17日,NVIDIA推出利用GPU加速云计算技术。
  • 2012年10月17日,NVIDIA推出了首款云计算虚拟GPU加速平台——VGXK2。
  • 2013年GTC大会上,NVIDIA带来了在云计算领域最新的产品服务器平台——NVIDIAGRID。

随后几年时间里,美国多家服务器厂商推出了各自的基于GPU并行计算的云服务平台。现在提供GPU云计算的服务提供商主要有Amazon,Nimbix,Peer1Hosting,SoftLayer, PenguinComputing等。

5:一个让人十分费解的局面是,国内各大云服务提供商(诸如阿里云、盛大云、万网云)似乎对GPU并行计算没有任何动作。

        自从云计算的概念提出,迅速在中国IT界形成了热点,大大小小的云服务商如雨后春笋般出现。几大云服务商以各种名目强调自身特色的云计算服务组合,如阿里云的“飞天”平台;百度BAE云平台;浪潮集团建立的HPC/IDC、媒体云、教育云;华为公司弹性云计算FusionCloud战略;腾讯云生态系统;华云数据公司推出的运营型PaaS平台。

然而在形形色色的各种名号之下,各家公司的服务内容非常同质化,基本都是网络存储 + 虚拟CPU计算时段租用的模式。对用户真正的运算需求理解挖掘不够,往往只是把一些浅层的PC功能简单转移到云端,对于复杂度高、维护难度大的运算功能未能提供虚拟层的解决方案。换句话说,凡是用户在PC端已经能轻松愉快做的事(比如办公软件),云服务商不厌其烦的去劝说用户将其转移到云端,而中小企业用户感到力不从心、真正需要帮助的具有技术难度的运算功能,云服务商就一问三不知了。

近期,笔者单位由于为客户开发的应用涉及高强度的数据处理,需要并行运算。我们与多个云服务商接洽,均未见有提供GPU并行运算服务。这是一个让人难以理解的局面,电话联系云服务商相关工作人员,他们的典型反应如下:

(客服人员)“这个我们不是很清楚,帮你转接技术人员”。

(技术支持)“没怎么听说过,这个国内好像还没有吧?”

(技术经理)“我们的服务器能不能加载GPU并行运算不清楚,不太了解市场有没有这样的需求”。

高性能并行计算主要采用CPU+GPU的异构模式,这种构架已经成功的在云服务器端实现资源虚拟化。但令人迷惑的是,中国国内各大云服务商的官网连 GPU并行运算的影子都看不到,甚至接触过的各大公司技术服务及营销人员似乎对GPU并行运算毫无概念。以下我们分别就几个问题,探讨这一尴尬局面的成因:

(1)难道GPU并行运算目前在国内没有市场?

(2)虚拟化GPU并行运算在国内的实施遇见技术上的困难?

(3)各大云服务公司管理层,是否对计算需求缺乏了解、对高性能技术发展不敏感?

(4)亦或是商务决策层与先进技术圈形成脱节?

        对上述的第(1)点市场因素:如前所述,随着图形图像、动画视频、3D运算、及大数据分析的广泛应用,对GPU并行运算的需求很高;而玩儿转这种高大上的前沿计算,普通中小企业在系统搭建、程序开发及维护都缺乏足够档次的常备技术队伍,因此非常需要云服务商的界入,降低此类技术的使用门槛,提供包括IaaS、PaaS、SaaS等整套共享租用服务。因此国内的市场需求是非常旺盛的。

        关于上述的第(2)点技术实施因素:虚拟化GPU运用于云计算服务的技术也早已成熟。如前所述,NVIDIA公司CUDA体系与云服务器已经有了完美的对接,在此基础上美国Amazon,Google,Joyent等公司均已提供相应的商业云计算租用服务。

2014年1月,曙光公司、NVIDIA公司、思杰公司合作推出“云图”(W760-G10),具备GPU硬件虚拟化的能力;虽然尚未见有明确的云租用服务,但是可以看出,技术实现并非阻碍所在。

       对上述的(3)管理层因素:近年成长起来的国内明星公司,如腾讯、阿里等,都经历了一个极短时间内的快速膨胀,很多早期人员随之自然升入高级管理层。然而,早期人员许多在自身的知识基础、学习能力方面存着严重的不足。大专生去面试本科生、研究生的现象实属常见。随着公司业务的拓展,整体技术积淀不足的弱点显露出来,管理层对技术的理解力与敏感度不够。

       对上述的第(4)点因素:中国IT及互联网的发展,曾长期奉行技术“拷贝主义”,精力心思多用于摸索中国土壤上的营利模式。中国企业对于应用层面的市场敏感度是相当出色的。但是,对于深层的技术策源动向,一直是忽视的。商务决策层需倚靠技术管理层的建议,而技术管理层或者自身够不着技术前沿、或者早已脱离技术前沿;中国高校科研机构以纯文章数为导向的研究风气,培养不出既尖端又实用的新鲜血液给企业,也鲜有学术专家真正花心思做好企业顾问。种种原因,商务决策层和先进技术圈是脱节的。

因此我们认为,对GPU并行云计算的市场需求和技术实现都不是问题所在。中国有志于做好云计算服务的各个公司,有必要进一步提升其技术管理层的技术素养、商务决策层的技术意识。

【IT时代周刊批注】虽然全球云计算市场保持着平稳增长的态势,但也应看到,各个国家间的云计算产业、市场和服务现况相距非常大。以中国为例,除了上述云服务企业存在的技术和服务因素外,传统的网络安全也不容忽视。有专家就指出,国内云服务商在网络安全方面的防护措施仍比较薄弱。国内典型云服务企业发生的安全事件中有50%是传统网络攻击造成的,占比达53%,随着我国云服务用户规模的不断扩大,安全问题数量也将迅速增长。

6:云计算商应脚踏实地、聚焦本质价值:帮助众多中小公司运用前沿计算工具,提升中国移动互联新经济的技术档次。

中国过去三十多年的经济奇迹,是从无到有、从低到高的迅速变换过程。在经济层次迅速攀升的年代,昨日的成功者、今日的弄潮儿,难免不受以往经验与习惯思维的影响。出于习惯,凡起商业项目,重视商业渠道的争夺、善于造势,对于产品内涵价值的挖掘却很欠缺。此种做生意的方式,不可否认在以往也取得过巨大的成功,但是我们也看到,每当新流行概念出现,就呈现“众口一词、一拥而上、简单复制、同质单一”的局面。善于热炒,而不扎实做事,不深入挖掘概念的内涵价值,如纳米、物联、机器人、3D打印等等流行热点比比皆是。概念固然很好,不做实做真,终究增加不了硬实力。

云计算服务,通过将繁琐的技术维护的移至云端,把“很难很先进”的技术功能打包封装,降低用户使用的技术门槛,实现社会智力资源共享。而现今中国的大大小小云服务商,简单讲就是个“远程机房+移动大硬盘”模式,意义着实有限。当今世界经济几乎唯中国一枝独秀,中国名企牛气冲天,何以搞个云计算却停留在如此低的层次?归根结底还在于商务观念未脱落低水平市场中粗放竞争的历史烙印,不习惯通过深挖技术内涵,发挥内在价值而建立商务优势的路线。

云计算作为一个“很实在很技术”东西,服务对象是商业应用型公司,具有理智化决策的行为特征。脑白金式的蒙蔽营销手法登峰造极,放在这里却未必有效。中国的移动互联新经济在应用层面,欣欣向荣,活力四射,全世界数一数二。相应的,云计算服务作为其龙骨支撑,不跟上是不行的。大量的视频音图+3D+ 规模机器学习+大数据分析=》高强度计算任务=》云GPU并行运算,这是一个非常简单明了的推导链条。何必瞻前顾后,剪不断理还乱?

【IT时代周刊编后】作者的这篇文章直接点出了国内云计算与先进国家的差距。在美国,以微软、谷歌、亚马逊等巨头为代表的IT企业,正在不断巩固自身在云服务上的优势地位,而且不断向海外市场拓展。有数据显示,全球前100个云计算企业中,超过80家是美国企业。而相比之下,国内云计算市场的体量虽说也在不断增大,但云服务企业的技术和服务有待提高、服务易用性、安全性、数据的迁移与分配等都有非常大的提高的空间,要做出调整和改进,首先需要改变以硬件采购为主的市场结构才行。