务实而深入地理解机器学习的几个经典算法

向作者提问
北京林业大学硕士研究生,工作三年多,现在某工业互联网公司从事算法研究,参与多个项目和公司产品研发,乐于知识分享,创办机器学习,深度学习相关的系统入门学习之微信公众号《算法channel》。
查看本场Chat

1. 背景介绍

现实问题错综复杂,仅仅调调 Sklearn 或 TensorFlow 的 API 就能把事做好? 应该没那么简单?!通常先务实地学几个经典算法,体会其思想,最好能编写源码实现它们,然后再勇往直前。

2. 带着10个问题踏入机器学习

  1. ML 的算法框架,通常包括哪几部分?
  2. 海量的数据 feed 到 ML 算法模型后,如何高效地利用它们?最终学到了什么? 让它们停下来的策略都有哪些?
  3. OLS 线性回归的误差项为什么要满足高斯分布?最大似然估计原理如何通俗理解和灵活运用?
  4. OLS 的直接求解是必然还是偶然?
  5. OLS 的梯度下降如何实施?包括不调包的源码实现
  6. 线性回归到逻辑回归,Sigmoid 映射起到了什么作用?
  7. 实战逻辑回归任务,包括不调包的梯度下降源码实现。
  8. 决策树的算法思想是什么?
  9. 从数据结构看,基本的二叉树如何演化成了决策树?
  10. 实战决策树做回归任务,包括不调包的源码实现。

2.1 机器学习算法的一般框架

机器学习的算法求解这块,通常可以分为两步走:

  1. 建立模型(比如线性回归时选用线性模型);
  2. 根据目标函数求出参数(比如求出线性回归的参数)

目标函数表示为如下,其中等号右侧第一项表示所有样本点的误差和,第二项表示惩罚项(我们知道,惩罚项是用来使得预测的模型不那么复杂的方法,这也是为了提高模型的泛化能力),目标函数的形式一般如下:

enter image description here

比如,脊回归的目标函数为(二次惩罚项):

套索回归的目标函数为(一次惩罚项):

总之,我们就是要让预测值接近真实值,同时要让模型尽可能的简单。

2.2 feed数据

海量的数据 feed 到 ML 算法模型后,如何高效地利用它们?最终学到了什么? 让它们停下来的策略都有哪些?

先谈一谈如何高效地利用这些数据(一般地训练样本数比较大)。比如在线性回归任务,利用梯度下降求解目标函数的最小值时,利用训练集的策略通常有3种:

1)每次迭代只使用随机的一个样本(极限情况1),这种情况下,每次修正方向以各自样本的梯度方向修正,横冲直撞,难以达到收敛。

2) 每次迭代使用所有样本(极限情况2),计算效率很低,任务收敛耗时比较长。

3)批处理(中间情况),mini-batch,每次选取一定数量的样本进行训练,能避免情况1的出现,也能在迭代效率上有所提升,在这种情况下,权重参数和偏置项用批处理表示为如下,

机器学习模型,通过一定次数的迭代求解并收敛后,学习到了使得目标函数最优的参数,在测试集上,利用这些学到的参数,预测任务。

收敛的策略,一般可以选用:

  1. 达到指定的迭代次数后,停止收敛;
  2. 目标函数达到指定的阈值,停止收敛;

2.3 最小二乘法和最大似然估计

OLS 线性回归的误差项为什么要满足高斯分布?最大似然估计原理如何通俗理解和灵活运用?

如下式所示,为线性回归最小二乘法的带有误差项的公式,第 i 个样本的真实值等于第 i 个样本的预测值加上第 i 个样本的误差项:

enter image description here

如果误差分布没有满足某个规律,这个就很难做出预测了,我们假设任何一个样本的误差项满足独立同分布,并且经过归一化处理后,服从均值为0方差为一定值的高斯分布,这样我们的模型才能选用线性回归模型,模型才有可能收敛。

最大似然估计的通俗理解

本质便是根据已有的大量样本(实际上就是利用已知的条件)来推断事件本身的一些属性参数的方法,最大估计更是最能反映这些出现的样本的,所以这个参数值也是最可靠和让人信任的,得到这个参数值后,等来了一个新样本 X(i+1) 后,我们可以预测它的标签值。

如果上面这段理解起来,还是费劲的话,不妨这样极限地想一下,比如抛掷一枚硬币,只抛掷一次,出现正面,那么根据最大似然估计的精神,一共抛掷了1次,且出现了正面,我们就认为这枚硬币出现正面的概率为1 ,尽管这听起来有些疯狂,因为我们只抛掷了一次,如果再抛掷1000次,出现了501次正面,这样出现正面的概率不就更符合实际了吗。

最大似然估计的使用

首先构建似然函数 L( theta | x) ,假设一共有 m 个房屋相关样本,那么进一步得到似然函数(它是参数为自变量的函数,这个一定要注意了,似然函数将概率转化为似然,这个还是似然的强大之处了):

根据最大似然估计的原理,所有样本出现的概率最大,并且这些样本间满足独立同分布,所以它们都出现就是它们的概率相乘,然后最大吧,也就是求上式的最大值,一般地,会将上个式子化为对数似然,变为对数的和,求解,这样还能防止计算机在迭代时数据的溢出。

2.4 OLS 的直接求解是必然还是偶然?

OLS最小二乘法的直接求解时数学上的偶然现象,不是必然的。

因为是线性模型,并且在假定独立同分布(高斯分布),利用最大似然估计求解时,正好能得出参数的直接求解公式:

但是,对于大多数机器学习问题,不能得到求解参数的数学公式,而往往要采用朝着正确的方向(梯度下降的方法),多次迭代求解,直至收敛,达到某个阈值后,获得最优解。

2.5 OLS 的梯度下降如何实施?包括不调包的源码实现

2.5.1 梯度下降实施策略

在用梯度求解时的代价函数要除以样本个数,言外之意,我们的代价函数不会因为样本个数太多,而变得越大吧,应该不受样本个数的影响:

直接对代价函数求偏导:

上式的反方向,就是梯度下降的方向,这样朝着这个方向,每次调整一点点,不能一次调整太多,调整的系数,我们称为学习率,因此每次参数的调整迭代公式可以写为如下所示:

样本使用方法,采取上面讲的,mini-batch SGD方法,即选取样本中的一小批来参与本时步的迭代计算,比如每次随机选取20个样本点,再乘以一个学习率,即下面的公式:

2.5.2 线性回归的梯度下降代码实现

数据集:预处理后得到的数据前10条展示如下,选择两个特征:其中第一列为房屋的面积,第二列为房屋使用年限,第三列为房屋的价值,是标签值,这些值都已经经过预处理了。

   房屋面积        使用年限           价值

   [[ 0.35291809,  0.16468428,  0.35774628],

   [-0.55106013, -0.10981663,  0.25468008],

   [-0.65439632, -0.71406955,  0.1061582 ],

   [-0.19790689,  0.61536205,  0.43122894],

   [-0.00171825,  0.66827656,  0.44198075],

   [-0.2739687 , -1.16342739,  0.01195186],

   [ 0.11592071, -0.18320789,  0.29397728],

   [-0.02707248, -0.53269863,  0.21784183],

   [ 0.7321352 ,  0.27868019,  0.42643361],

   [-0.76680149, -0.89838545,  0.06411818]]

梯度下降的回归思路如下:

  • 'model' 建立的线性回归模型

  • 'cost' 代价函数

  • 'gradient' 梯度公式

  • 'theta update' 参数更新公式

  • 'stop stratege' 迭代停止策略:代价函数小于阈值法

下面分别写出以上五步的具体实现代码:

'model'

def model(theta,X):

    theta = np.array(theta)

    return X.dot(theta)

'cost'

def cost(m,theta,X,y):

    'print(theta)'

    ele = y - model(theta,X)

    item = ele**2

    item_sum = np.sum(item)

    return item_sum/2/m

'gradient'

def gradient(m,theta,X,y,cols):

    grad_theta = []

    for j in range(cols):

        grad = (y-model(theta,X)).dot(X[:,j])

        grad_sum = np.sum(grad)    

        grad_theta.append(-grad_sum/m)

    return np.array(grad_theta)

'theta update'

def theta_update(grad_theta,theta,sigma):

    return theta - sigma * grad_theta

'stop stratege'

def stop_stratege(cost,cost_update,threshold):

    return cost-cost_update < threshold

'OLS algorithm'

def OLS(X,y,threshold):

    start = time.clock()

    '样本个数'

    m=100

    '设置权重参数的初始值'

    theta = [0,0,0]

    '迭代步数'

    iters = 0;

    '记录代价函数的值'

    cost_record=[]

    '学习率'

    sigma = 0.0001

    cost_val = cost(m,theta,X,y)

    cost_record.append(cost_val)

    while True:

        grad = gradient(m,theta,X,y,3)

        '参数更新'

        theta = theta_update(grad,theta,sigma)

        cost_update = cost(m,theta,X,y)

        if stop_stratege(cost_val,cost_update,threshold):

            break

        iters=iters+1

        cost_val = cost_update

        cost_record.append(cost_val)

    end = time.clock()

    print("OLS convergence duration: %f s" % (end - start))

    return cost_record, iters,theta

结果显示经过,OLS梯度下降经过如下时间得到初步收敛,OLS convergence duration: 7.456927 s,经过3万多个时步迭代,每个时步计算代价函数的取值,如下图所示:

收敛时,得到的权重参数为:

array([ 0.29921652, 0.09754371, 0.1867609 ])

2.6 线性回归到逻辑回归,Sigmoid 映射起到了什么作用?

逻辑回归最神奇的那个映射函数长什么样子呢? 这个前人都给我们想好了,直接拿过来用就行,这就是站在巨人的肩上啊,感谢他们。

在Jupyter Notebook中绘制了这个函数: f(x) = 1/(1+np.exp(-x)),简称为Sigmoid函数,它的自变量取值范围为负无穷到正无穷,值域为0~1,其中f(0) = 0.5 。

通常在做二分类时,设定一个阈值 gamma,如果小于gamma,设为 0 类,否则为 1类,如下图所示:设定阈值为0.3,则小于0.3的都为 0 类,大于0.3的都为 1 类。

2.7 实战逻辑回归任务,包括不调包的梯度下降源码实现

下面推导逻辑回归的模型和目标函数,然后给出梯度下降的实现代码。

2.7.1 逻辑回归的模型,目标函数推导

线性回归模型的模型如下:

逻辑回归的模型定义如下:

其中,

因此,逻辑回归的最终模型为:

这就是从线性回归模型映射到最终的逻辑回归模型的预测表达式,我们的最终任务是二分类吧,假定上个表达式是等于类 1 的概率,自然等于类 0 的概率等于1减去等于类 1 的概率,如下所述:

这里有个小的trick,就是将上面两个式子整合为下面一个公式,这就是终极的逻辑回归的模型了,一个公式综合了以上两种情况:

逻辑回归需要优化的目标函数为:

求偏导,梯度方向为下式的相反数:

2.7.2 逻辑回归的梯度下降求解

首先看下生成的用于模拟的数据集长得样子,它有两个特征w1,w2组成,共有200个样本点,现在的任务是要对这个数据集进行分类。

假定模型的决策边界为线性模型,梯度下降求逻辑回归模型的权重参数的基本思路如下:

  • 'model' 建立的逻辑回归模型:包括Sigmoid映射

  • 'cost' 代价函数

  • 'gradient' 梯度公式

  • 'theta update' 参数更新公式

  • 'stop stratege' 迭代停止策略:代价函数小于阈值法

不要忘记初始化一列偏置项,做一个偏移量和2个特征的组合。

'model'

def sigmoid(x):

    return 1/(1+ np.exp(-x))

def model(theta,X):

    theta = np.array(theta)

    return sigmoid( X.dot(theta) )

'cost'
def cost(m,theta,X,y):

    ele = y*np.log(model(theta,X)) + (1-y)*np.log(1-model(theta,X))

    item_sum = np.sum(ele)

    return -item_sum/m

'gradient'
def gradient(m,theta,X,y,cols):

    grad_theta = []

    for j in range(cols):

        grad = (model(theta,X) - y).dot(X[:,j])

        grad_sum = np.sum(grad)    

        grad_theta.append(grad_sum/m)

    return np.array(grad_theta)

'theta update'

def theta_update(grad_theta,theta,sigma):

    return theta - sigma * grad_theta

'stop stratege'

def stop_stratege(cost,cost_update,threshold):
    return cost-cost_update < threshold

'逻辑回归算法'
def LogicRegression(X,y,threshold,m,xcols):

    start = time.clock()

    '设置权重参数的初始值'

    theta = np.zeros(xcols)

    '迭代步数'

    iters = 0;

    '记录代价函数的值'

    cost_record=[]

    '学习率'

    sigma = 0.01

    cost_val = cost(m,theta,X,y)

    cost_record.append(cost_val)

    while True:

        grad = gradient(m,theta,X,y,xcols)

        '参数更新'

        theta = theta_update(grad,theta,sigma)

        cost_update = cost(m,theta,X,y)

        if stop_stratege(cost_val,cost_update,threshold):

            break

        iters=iters+1

        cost_val = cost_update

        print("cost_val:%f" %cost_val)

        cost_record.append(cost_val)

    end = time.clock()

    print("LogicRegressionconvergence duration: %f s" % (end - start))

    return cost_record, iters,theta

调用逻辑回归函数:LogicRegression(data[:,[0,1,2]],data[:,3],0.00001,200,3)

结果显示经过,逻辑回归梯度下降经过如下时间得到初步收敛,LogicRegression convergence duration:18.076398 s,每个时步计算代价函数的取值,如下图所示:

分类结果:

2.8 决策树的算法思想是什么?

决策树算法采取贪心思想,每次分裂选取使熵值降低最大的特征和对应的取值。根据这一原则,直至达到某些前提假定下的分类和回归,最终的分类和回归的结果反映在叶子节点上。

2.9 从数据结构看,基本的二叉树如何演化成了决策树?

基本的二叉树,其数据结构一般为:

public class BinaryTree
{
     public T data {get;set;}
     public BinaryTree Left {get;set;}
     public BinaryTree Right {get;set;}
}

决策树本质上也是一个二叉树,只不过,它的节点上会增多一些变量,比如,该节点的特征选择了众多特征中的哪一个,以及对应的取值等于多少,sklearn中还给出了基尼系数,样本个数,长得样子大概如下:

public class DecisionTree
{
     public AttributeCollectin  whichAttribute{get;set}
     public object attributeVal {get;set;}    
     public decimal gini {get;set;}     
     public int sampleCount {get;set;}

     public BinaryTree Left {get;set;}
     public BinaryTree Right {get;set;}
}

下面是在sklearn中可视化决策树后,每个节点长的样子:

enter image description here

可以看到,叶子节点上保存着最终的分类结果,class=0, class = 1等。

2.10 实战决策树做回归任务,包括不调包的源码实现

先用易懂的文字阐述下决策树的回归算法的实现思路。比如,一个数据集有3个特征,对应的目标值不再是整数,0,1,2,3,这种分类值,而是0.1,0.23,1.4等这种小数值。那么,怎么用决策树的模型做回归呢?

首先,依次遍历每个特征,然后,遍历每个特征的取值,注意,特征的取值可能有很多种,根据定义的最佳分割点的方法,找出当前特征的最佳分割点,内层循环结束后即可找到当前特征的最佳分割点,等外层循环遍历结束时,找到所有特征中的最佳分割点。

import numpy as np



#求得mat的最后一列,也就是目标值的平均值

def regLeaf(mat):

    return np.mean(mat[:,-1])



#定义误差计算方法:mat最后一列(目标值)的方差乘以个数

def regErr(mat):

    return np.var(mat[:,-1]) * np.shape(mat[:,-1])[0]       



#生成回归决策树,给出一个元参数:

# 第一个表示分割后误差下降的大小未超过此值,直接作为叶节点输出(带有目标值)    

# 第二个参数表示某个节点内含有的节点个数,必须大于这个值,才会进一步分裂          

def decisionTreeRegressor(dataSet,ops=(0.0001,3)):

    feat,val = chooseBestSplit(dataSet,leafType,regErr,ops)

    if feat==None:

        return val

    retTree={}

    retTree['spIndex'] = feat

    retTree['spValue'] = val

    lSet,rSet = binSplitDataSet(dataSet,feat,val)

    retTree['left'] = createTree(lSet,leafType,regErr,ops)

    retTree['right'] = createTree(rSet,leafType,regErr,ops)

    return retTree



 #根据最佳索引和取值,将数据集分开

def binSplitDataSet(dataSet,bestIndex,bestValue):

    mat0 = dataSet[np.array(dataSet)[:,bestIndex]<bestValue]

    mat1 = dataSet[np.array(dataSet)[:,bestIndex]>=bestValue]

    return mat0,mat1



#选择最佳切分属性及其对应的属性值

#所有的属性遍历后,如果误差减少不大,生成叶子节点

# 得到叶节点的条件有3个,标红色的代码

def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr,ops=(0.0001,3)):

    tolS = ops[0]

    tolN = ops[1]

    #所有的样本对应的目标值都相等,则

    if len(set(dataSet[:,-1].T.tolist())) ==1:

        return None, leafType(dataSet)

    m,n = np.shape(dataSet)

    S = errType(dataSet)

    bestS = np.inf

    bestIndex = 0

    bestValue = 0

    for featIndex in range(n):

        for splitVal in set(dataSet[:,featIndex]):

            mat0,mat1 = binSplitDataSet(dataSet,featIndex,splitVal)

            #这个条件约束了分割后的区间长度都不能小于tolN

            if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0]<tolN):

                continue

            #求出分割后的两部分均方误差的和

            newS = errType(mat0) + errType(mat1)

            #如果newS更小,则让它成为bestS

            if newS < bestS:

                bestIndex = featIndex

                bestValue = splitVal

                bestS = newS

    #说明误差下降的不大

    if S - bestS < tolS:

        return None,leafType(dataSet)

    #根据最优特征和其对应的取值划分数据集

    mat0,mat1 = binSplitDataSet(dataSet,bestIndex,bestValue)

    #满足这种情况,只能是所有的样本点个数小于tolN

    #此时只给出当前样本的均方误差

    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):

        return None, leafType(dataSet[:,bestIndex])

    return bestIndex, bestValue

写好了以上代码,调用上面 decisionTreeRegressor,看看回归决策树的回归效果,为了展示方便,特意将满足分裂的条件加大,即内含节点个数大些。

当 ops[1] = 6时,即节点内含样本数大于6才做分裂,待回归的样本如下:

enter image description here

此时调用接口做回归,得到的决策树的示意图如下:

enter image description here

回归后的结果如下:

enter image description here

当 ops[1] = 5 时,即节点内含样本数大于5才做分裂,得到的决策树示意图和回归图如下,

enter image description here

enter image description here

为了容易理解,特意让树的结构不至于特别复杂,这样才容易看出决策树回归的思路,最核心的还是选择特征和取值,在这里实际上是运用了最小均方差来选择。

3. 总结

以上就是机器学习的几个经典算法,希望大家通过这些算法,能初步理解机器学习解决问题的大致思路。主要包括如何构建模型,如何定义模型对应的优化目标函数,然后如何求出目标函数的最优解,比如通过梯度下降迭代求解。

最后,谢谢大家的阅读,祝大家在探索AI的道路上,持之一恒,勇攀高峰!


本文首发于GitChat,未经授权不得转载,转载需与GitChat联系。

微信扫描登录