[机器学习笔记#1]从 Logistic Regression 讲讲分类器和机器学习

分类( Classification) 以及分类器( Classifier)是机器学习和传统统计学里边一个很重要的概念,可能是我们日常生活中接触到的最多的一种机器学习应用。垃圾邮件过滤,人脸识别,手写字符识别,都是利用了分类的知识。

在这些任务中,我们往往希望给定一个具体输入,通过分类器的处理,能自动将其划到我们预先定义的某个类别中去。比如垃圾邮件过滤,给定邮件内容作为输入,输出 “是垃圾”,“不是垃圾” 两种状态之一;人脸识别,给定照片的特定区域,输出“是我”,“是路人甲”,“是路人A”,等等等等。

但实现这种自动分类功能往往并不简单,举例说,上述提到的几种输入数据,在概率上都是非常随机和分散的,难以抽取出一个统一的分类标准。具体一点,垃圾邮件的内容可能会千奇百怪,关键字五花八门;人脸更不用说,同样是两个鼻子一张嘴,但世间相貌岂止千万种,我自己作为脸盲患者就深感人脸识别不是一件易事;而人的字体和书写习惯也是非常难提炼出一个统一的标准,同样一个字,不同人写出来会非常不同。

但好在我们人类作为万物之灵,处理起这种任务起来虽然偶尔会有困难,但大部分时候可谓是得心应手,原因估计不说大家也知道,因为我们有学习能力。垃圾邮件收得多了,只看一个开头便随手扔进垃圾箱;在人事部混上一年,公司上下几百号面孔一个个熟络得不行;学习了书法鉴赏,几百张字帖看下来,看狂草也一点不虚。

但具体让你讲你怎么做到的,多数人也讲不出个所以然,认识很多张脸的人并不会说:”啊,其实我记下了每个的头围、眼间距、鼻子长度等等的详细尺寸,每次靠精确测量来一一对上号。“

所以,人类的这种学习分类的能力,是一种模糊的过程,是在经历了足够多的输入作为训练样本后,慢慢总结、归纳出的一种概率模型,而非死板的映射。

机器学习中的分类器,就是通过数学工具,让机器也具备这种归纳总结数据的能力。而提到通过数学工具归纳总结数据,难免会让人想到工程学中我们早已熟知的另一个概念——“拟合”。相信大部分人做过这种实验,先测量一堆数据,然后在坐标纸上一个一个画点,然后勾勾画画,这么就弄出来了一条曲线或者直线的模型。顺便一提,回想我大学,最令人发指的是学校竟然让用铅笔跟纸来做这个!美其名曰“熟悉具体步骤”,导致很多人一直到大四毕业设计才知道有 MATLAB 的拟合工具箱这个东西。

所以其实机器学习的很多理念,本质上还是在做拟合( fitting),Andrew Ng 曾在一个讲座上开玩笑说,他最开始接触人工智能的时候,以为自己会接触各种神乎其技的科幻小说里的知识,结果发现他一直在做各种拟合。

而在他的CS229课程中,他讲的第一个线性分类器就是线性回归( Linear Regression ),没错,就是线性回归,高中考纲,而且的的确确是有效果的。我硕士期间修的课程上,教授布置的第一个作业也是用线性回归预测总统大选( 用的伪数据)。

[修改于 3 年前 - 2016-07-21 11:07:15]

+1  学术分    nkc   2016-07-23   机器学习方面的第一个学术分。
来自 机器学习
 
1
2016-7-13 12:36:04
Cirno(作者)
1楼

而在这个笔记中,我想谈的是 Logistic Regression( 逻辑回归)。

假定我们有如下两个clusters的数据,一堆是红的那些点,一堆是绿色的那堆,它们拥有如下的分布:

output_2_1.png

我们规定,其中绿色的点代表了某种正逻辑,用“1” 表示;红色代表负逻辑,用“0"表示,称为数据的标定(label)。显而易见,这两个clusters在特征空间(feature space)上是线性可分的( 不可分的以后会提及)。意味着我们可以用类似如下的一条直线来分开两个clusters,这样再有一个新的未归类的点出现,我们可以根据它落在线的哪一边来给它着色,也就是分类。
output_3_1.png

既然是叫 Logistic Regression,那么肯定是要从这堆数据中想办法拟合出这条线最合理的位置和走向的,但具体怎么实现呢? 我们再接着看,假如我们沿着如图的垂线方向来看点的label值的分布。
output_4_1.png

理想情况下应该会是如下这样的一个阶越分布,即线的一边全是正样本,一边全是负样本,记住绿=1,红=0:
output_5_0.png

看上去很美好,但头疼的是这玩意在关键的分隔点上不可导,会给我们后面的工作带来一系列麻烦( 但实际上仍然有分类器利用了这种分布,叫 perceptron)。
于是我们祭出了一条祖传的无比优雅的近似曲线——Logistic function:
$$h(x)=\frac{1}{1+e^{-x}}$$
output_6_0.png

其导数形式如下,有兴趣者自行推导:
$$h'(x)=h(x)(1-h(x))$$

[修改于 3 年前 - 2016-07-13 22:56:26]

折叠评论
加载评论中,请稍候...
折叠评论
2016-07-15 10:22:28
2016-7-15 10:22:28
Cirno(作者)
5楼

假设这条直线方程是:
$$wx+b=0$$ 那么如下的式子可以看作对任意数据点\(x\)离开这条直线垂直距离:
$$\theta=w^Tx+b$$ 所以这里我们得到一个式子:
$$P(y=1|x)=h(w^Tx+b)$$ 这里的\(P(y=1|x)\)是,当给定一个输入数据x时,x属于正样本区间y=1的后验概率分布,也就是我们这里的classification所需要的映射关系。顺便一提,这种研究\(P(y|x)\)而非\(P(y,x)\)的机器学习方法,被称作***Discriminative model***,而后者被称作***Generative model***,这两者的区别和特点是非常有趣的一个话题,现按下不表。

\(P(y=1|x)\)显而易见是w,b的函数,所以我们写作\(P(y=1|x;w,b)\)。实际训练过程,可以看作对w,b的取值进行优化,使\(P(y=1|x;w,b)\)最符合我们的训练集数据\( \{x_i,y_i \}\)。

于是问题来了,如何描述这种符合程度?

这里引入了损失函数(loss function)的概念。

对所有的\(x_i\)和\(y_i\),我们希望以下这个总概率最大化(参考高中数学知识,独立随机事件的总概率):

$$P(Y|X)=\Pi_i P(y=y_i|x_i)$$ 即:
$$w,b=argmax_{w,b}\Pi_i P(y=y_i|x_i;w,b)$$

\(P(y=y_i|x_i;w,b)\)实际上可以写成如下表示:
$$P(y=y_i|x_i;w,b)=h(w^Tx_i+b)^y_i(1-h(w^Tx_i+b))^{1-y_i}$$ 请自己体会。
但处于某种原因,直接对\(P(Y|X)\)是很困难的,于是我们使用了如下的trick(认真上过高数课的同学并不会陌生),转而优化\(L(w,b)\):
$$L(w,b)=-\sum_i log(h(w^Tx_i+b)^{y_i}(1-h(w^Tx_i+b))^{1-y_i})$$ 但同时优化两个参数w,b是㯊麻烦的(求两遍导,更新两个参量),所以又使用了如下的 bias trick:
$$w'=[w,b], x'=[x,1]$$ $$w^Tx+b=w'^Tx'$$ 简化后有没有神清气爽?
$$L(w)=-\sum_i log(h(w^Tx_i)^{y_i}(1-h(w^Tx_i))^{1-y_i})$$

[修改于 3 年前 - 2016-07-15 12:41:07]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
6楼

拿到了\(L(w)\)的表达式,下面该如何找到正确的w,使得\(L(w)\)最小呢(注意,求最大变成了求最小)?

祭出凸优化中神挡杀神,佛挡杀佛的梯度下降法(gradient descent)。

contours_evaluation_optimizers.gif


图片来源
思路简单说就是,虽然我不知道w取坐标轴上什么位置好,但我可以一小步一小步的挪过去,每挪一步都向着当前所在位置坡度最陡的地方去。于是我们就这样慢慢的圆润的滚道谷底了。

可以证明,“坡度最陡”的方向,就是该点导数方向的反方向,这本书的这个章节有极好的详述。于是我们要对\(L(w)=-\sum_i log(h(w^Tx_i)^{y_i}(1-h(w^Tx_i))^{1-y_i})\)求导:
$$\frac{\partial L(w)}{\partial w}=\sum_i (h(w^Tx_i)-y_i)x_i$$ 得益于sigmoid函数良好的求导特性和log函数的特性,这个导数表达非常简洁。

在实际程序中,我们只需要算出每个数据点对应的\((h(w^Tx_i)-y_i)x_i\),然后求和,就能得到当前w的导数表达。

但是这样真的好吗?

首先训练集的数据量一般都非常大,达到成千上万的地步,对如此大的数组频繁反复求和从计算的角度讲是非常不利的。其次,更重要的一点,我们无法保证整个数据集的数据都是有效数据,其中必然包含噪声,而把这些噪声算入我们每次计算的导数中,是非常危险的。

于是,这里我们使用另一个思路(所以我觉得机器学习里边的方法论实在是占据太多地盘了。。),每次求导时从整个数据集中随机抽取一小部分数据,用这一小部分数据作为样本来计算导数

这就是在各种机器学习算法中一路通杀的大名鼎鼎的 stochastic gradient descent,简称SGD,这种形式也叫 mini batch 法。无论是简单如Logistic regression,还是复杂如深度学习网络,优化思路基本上都是用SGD,或者说没有脱离SGD的模子。

[修改于 3 年前 - 2016-07-15 12:41:58]

折叠评论
加载评论中,请稍候...
折叠评论
Cirno(作者)
7楼

光说不练从来不是科创的风格,下面讲一讲 Logistic Regression 的程序实现和实验。

在实验中我使用 Python,在 scientific computing 上,Python一直是主流,机器学习也不能免俗,而 numpy 提供的便捷的向量化运算,给诸多机器学习的算法实施提供了便利。另外强烈推荐ML新手装 sklearn 这个package。

导入库:

import numpy as np
from numpy import linalg as LA
import matplotlib.pyplot as plt
import sklearn.datasets
import sklearn.cross_validation

以下是计算梯度的函数,使用了numpy的向量化计算特性:

def calculate_gradient(w,x_batch,y_batch):
    sigmoid=1/(1+np.dot(x_batch,np.transpose(w)))
    dL=np.dot(sigmoid-y_batch,x_batch)/y_batch.size
    return dL

计算Loss function,注意,数据溢出是Logistic Regression程序实现的一个主要问题,因为exp函数的输出,用float 表示时,实际上输入被限制在[-750,750]这个区间内,不做处理的话基本上肯定会上溢。这个问题的解决同样在这本书中有讲

def calculate_loss(w,x_all,y_all):
    ### Avoid Overflow! ###
    pos_index=np.where(y_all==1)    
    neg_index=np.where(y_all==0)
    Loss=np.sum(-np.log(1+np.exp(-np.dot(x_all[pos_index,:],np.transpose(w)))))+np.sum(-np.log(1+np.exp(-np.dot(x_all[pos_index,:],np.transpose(w)))))
    return Loss   

训练过程主循环,注意对learning rate采用了annealing,在SGD过程中分段一点点减小步长,不然很容易最后变成在global minimum周围反复徘徊难以收敛:

def train(x_train,y_train,alpha,batch_sz,loss_thresh,Max_iter,w0):
    ### bias trick ###
    w=w0
    data_sz=y_train.size
    x_train_b=np.concatenate((x_train,np.ones((data_sz,1))),axis=1)
    Loss_old=0
    Loss=[]
    stepCnt=0
    ### Run SGD ###
    for iter in range(1,Max_iter):
        ### sample a mini batch ###
        batch=np.arange(data_sz)
        np.random.shuffle(batch)
        x_batch=x_train_b[batch[:batch_sz],:]
        y_batch=y_train[batch[:batch_sz]]
        ### update weight ###
        dL=calculate_gradient(w,x_batch,y_batch)
        w-=alpha*dL
        ### record loss changes ###
        Loss.append(calculate_loss(w,x_train_b,y_train))
        ### learning rate annealing ###
        stepCnt+=1
        if stepCnt==10:
            stepCnt=0
            alpha*=0.8

        ### Check if converge ###
        if abs(Loss[-1]-Loss_old)<loss_thresh:
            break
        Loss_old=Loss[-1]

    return w,Loss

使用了sklearn的数据生成函数,之前的图表数据皆来源于此:

def make_data():
    centers = [(-10, -10),(10, 10)]
    x, y = sklearn.datasets.make_blobs(n_samples=2000, n_features=2, cluster_std=5.0,
                  centers=centers, shuffle=False, random_state=100)
    x_train, x_test, y_train, y_test = sklearn.cross_validation.train_test_split(x, y, test_size=.4)
    return x_train, x_test, y_train, y_test

主函数,w被初始化为全零向量,mini batch size 是50 :

def main():
    alpha=0.5
    batch_sz=50
    Max_iter=2000
    loss_thresh=1e-5
    w0=[0,0,0]
    x_train, x_test, y_train, y_test = make_data()
    w,Loss = train(x_train,y_train,alpha,batch_sz,loss_thresh,Max_iter,w0)
    plt.plot(Loss)

以下是记录的学习过程中 Loss function 的收敛过程。

output_9_1.png

得到的w的值为[ 123.01618818 125.42445694 11.78221087]。

画成直线可以看出,跟理想情况非常近似
result.png

[修改于 3 年前 - 2016-07-15 12:47:35]

折叠评论
加载评论中,请稍候...
折叠评论
2017-12-18 16:05:16
2017-12-18 16:05:16
9楼
楼主,请问在定义梯度下降函数时,用的sigmoid=1/(1+np.dot(x_batch,np.transpose(w)))
为什么不用带exp啊,
折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png