rambo

Linear Regression and Logistic Regression

回归问题是有监督学习的一种方法。核心思想是从离散的训练数据中得到一个数学模型,用于预测或者分类。

1、问题介绍

首先引入一个预测房屋价格的问题。给定一组销售数据,如图x轴为房屋面积,y轴为房屋价格。如果输入一个新的面积如何去预测其价格?可以用一条曲线(即多项式拟合)去拟合这些数据。这里我们采用一条直线去拟合。

QQ截图20150630131715

QQ截图20150630131730

x_{(j)}表示输入变量(特征),y_{(j)}表示输出或者目标变量。(x^{i},y^{i})为训练样本,i=1,...,l。上例中令x^{i}\in X=R^n,y^{i}\in Y \in R

Part I、Linear Regression

线性回归假设特征和结果满足关系。其实线性关系的表达能力非常强大,每个特征 对结果的影响强弱可以有前面参数体现,而且每个特征变量可以首先映射到一个函然后再参与线性计算。(multiple kernel learning) 这样就可以表达特征结果之间的非线性关系。

x_{(1)},x_{(2)},...,x_{(n)}描述 feature里面的分量,比如x_{(1)}= 房间的 面积, x_{(2)}= 房间的朝向 等,用一个估计函数h(x)=<\theta,x>=\theta^{'}x={\sum_{j=0}^{n} }{\theta_{(j)}x_{(j)}}=\theta_{(0)}+\theta_{(1)}x_{(1)}+...+\theta_{(n)}x_{(n)}\theta在这里就表示feature中每个分量的权重,即决定房屋的面积更重要还是房屋的地段更重要。

需要一个机制去评价\theta是否选取的比较好,所以说需要对g函数进行 评估,一般这个函数称为损失函数( loss function)或者错误函数(error function)。

\xi=(y-g(x))为误差,f((x,y))=\lvert{y-g(x)}\rvert=\lvert{\xi} \rvert,寻找一个映射函数使得训练误差最小。通常选择误差的平方和\rm{J}(\theta)=\frac{1}{2}{\sum_{i=1}^{m} (y^{j}-g((x^{j}))^2},寻找\theta使得训练误差总和(collective loss)最小。

如何调整 \theta 以使得J(\theta)取得最小值有很多方法,其中有最小二乘法(min square),是一种完全是数学描述的方法,和梯度下降法。

1、优化求解方法

1)最小二乘法

将训练特征表示为 X 矩阵,结果表示成 y列 向量,仍然是线性回归模型,误差函数不变。那么\theta可以由下面公式得出 :

\theta=(X^{'}X)^{-1}X^{'}y

具体推导戳 本文的推导,以及其对偶形式,和在X^{'}X非奇异时的岭回归问题的解形式。

2)梯度下降法

在选定线性回归模型后,只需要确定参数 \theta ,就可以将模型用来预测。然而\theta 需要在J(\theta) 最小的情况下才能确定。因此问题归结为求极小值问题,使用梯度下降法。梯度下降法最大的问题是求得有可能是全局极小值,这与初始点的选取有关。

梯度下降法是按下面的流程进行的:
1)首先对\theta 赋值,这个值可以是随机的,也可以让\theta 是一个全零的向量。

2)改变\theta 的值,使得 J(\theta) 按梯度下降的方向进行减少。

梯度方向由 J(\theta)\theta 的偏导数确定,由于求的是极小值,因此梯度方向是偏导数的反方向。结果为

\theta_{(j)}:=\theta_{(j)}-\alpha\frac{\eth}{\eth\theta_{(j)}}J(\theta)

 \alpha为学习率。当只有一个训练样本时,忽略sum项,求解如下:QQ截图20150630210803

更新规则如下QQ截图20150630211017由这个式子可以看到,每个分量的更新的大小与误差项(y^{i}-h_{\theta}(x^{i}))成正比,即当遇到预测值非常接近y^{i}的训练样本时,几乎没有必要去更改参数;而如果预测值与实际值误差较大时,则需要较大程度的更改参数。

对于训练样本集(不再是只有一个训练样本),迭代更新的方式有两种,一种是批梯度下降(batch gradient descent),也就是对全部的训练数据求得误差后再对\theta 进行更新,另外一种是增量梯度下降(stochastic gradient descent),每扫描一步都要对\theta 进行更新。前一种方法能够不断收敛,后一种方法结果可能不断在收敛处徘徊。

注意:梯度下降法一般非常易于落入局部最小(susceptible to local minima in general),详细说明戳无约束优化方法。对于线性回归的优化问题只有一个全局最小点(假定学习率\alpha不是过大),没有其他局部最优。J(\theta)是一个凸二次函数,下图表示用于该问题的梯度下降示意。初始点为(48,30)。

QQ截图20150630212838

批梯度下降:

QQ截图20150630141444

增量梯度下降:

QQ截图20150630141455

增量梯度下降只使用一个数据对函数参数进行更新,这样往往只通过一部分数据更新参数就会收敛,相比批梯度下降速度大大加快(当训练数据很多时)。尽管其可能不会趋近于极小值,在附近振荡,但实际上most of the values near the minimum will be reasonably good approximations to the true minimum.(While it is more common to run stochastic gradient descent as we have described it and with a fixed learning rate , by slowly letting the learning rate decrease to zero as the algorithm runs, it is also possible to ensure that the parameters will converge to the global minimum rather then merely oscillate around the minimum.)也就是说让学习率\alpha不断减小至0,也可以保证增量梯度下降的收敛性。

2、概率角度解释

令样本(x^{(i)},y^{(i)}),对样本的预测\hat y^{(i)}|_\boldsymbol{\theta}表示该预测依赖于参数\theta的选取。我们有

\boldsymbol{y^{(i)}}=\boldsymbol{\hat y^{(i)}|_\theta}+\boldsymbol{\epsilon^{(i)}}=\theta^{T}x^{(i)}+\epsilon^{(i)}

其中,\epsilon^{(i)}是一个误差函数,我们通常认为其服从高斯正态分布(独立同分布布)即

\boldsymbol{\epsilon^{(i)} }\sim N(0,\sigma^2)

QQ截图20150630225034

QQ截图20150630224335

注意,我们不能对\theta算条件概率,即p(y^{(i)}|x^{(i)},\theta),因为\theta不是随机变量。

因此有

\begin{aligned}\boldsymbol{y^{(i)}}-\boldsymbol{\hat y^{(i)}|_\theta}&\sim N(0,\sigma^2)\\ \boldsymbol{y^{(i)}}&\sim N(\boldsymbol{\hat y^{(i)}|_\boldsymbol{\theta}},\sigma^2)\end{aligned}

要求\theta的极大似然估计,即是说,我们现在得到的这个真实存在的y\theta不同的取值下,出现概率最大。给定训练样本矩阵X,计算下面这个概率(更专业的叫做似然函数)

L(\boldsymbol{\theta})=P(\boldsymbol{y}|\boldsymbol{X};\boldsymbol{\theta})=\prod_{i=1}^mP(\boldsymbol{y^{(i)}}|\boldsymbol{x^{(i)}};\boldsymbol{\theta})=\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(y^{(i)}-\hat y^{(i)}|_\boldsymbol{\theta})^2}{2\sigma})

为了求解方便定义对数似然函数:

\begin{aligned}l(\boldsymbol{\theta})&=\log L(\boldsymbol{\theta})\\&=m\log \frac{1}{\sqrt{2\pi}}+\sum_{i=0}^m-\frac{(y^{(i)}-\hat y^{(i)}|_\boldsymbol{\theta})^2}{2\sigma}\end{aligned}

最大似然估计的准则就是选择\theta让数据有尽可能高的可能性,即选择\theta要让L(\theta)最大,即需让l(\theta)最大,即让\sum_{i=0}^m(y^{(i)}-\hat y^{(i)}|_\boldsymbol{\theta})^2取到最小值。那么,这其实也就是最小二乘方法的优化目标。

  综上,当误差函数定为平方时,参数\theta是样本的极大似然估计。\theta的选择与\sigma^{2}的选择无关。注意,这里的概率假设对于最小二乘估计不是必须的,也可以由其他的假设用来验证这个结论。

Part II、Logistic Regression

一般来说,回归模型不能用在分类问题上,因为回归是连续型模型,受噪声影响比较大。这里采用对数回归来解决分类问题。

对数回归本质上还是线性回归,但是值得注意的是其在特征到结果的映射中加入了一层函数映射,即先把特征线性求和,然后通过映射函数把连续值映射到0和1。

h_{\theta}(x)=g(\theta^{T}x)=\frac{1+e^{-\theta^{T}x}{1}</p>
<p style=Logistic distribution:?X????????X??Logistic distribution??X?????????????

QQ??20150630232222

???" />\mu??????\gamma>0$$为形状参数。

QQ截图20150630232323

参考资料:

1、Andrew Ng CS229 Lecture notes

2、JerryLead 对回归方法的认识