Machine Learning Foundations 9: Linear Regression | Cheney Shen

Technology blog

Machine Learning Foundations 9: Linear Regression


 
 

内容:

  1. Linear regression 的原理和推导过程,就是求解Ein最小化的解。极其重要!
  2. Linear regression 的理论 Ein/Eout 平均错误是 2(d+1)/N
  3. 证明 linear regression 这个方法可以被用在classification 求解上面,只要其错误衡量是classification的上限

 
 


 
 

上一节我们讲了再前面花力气证明的二元的VC Bound可以扩展用在各种情况下,也包括这里面要讲的linear regression的情况。

 
 

我们来看看演算法上面我们要怎样去设计。

 
 


 
 

回过头来看银行发信用卡的例子。这里考虑的不是银行要不要给顾客发信用卡,而是要给用户发多少额度的信用卡。

 
 

可以继续用前面二元分类使用的learning流程,改动的地方在于学习公式变成了一个输出实数的公式,输出的是给顾客的信用额度数值。

 
 

regression问题的特征就是:输出空间是整个实数。

 
 


 
 

那么我们来考虑到底Hypothesis到底长什么样子输出的才会是实数。

 
 

比如例子:顾客资料分数的加权值 和 给用户的信用额度是需要接近的。

和原来perception的区别在于,原来perception算完分数后为了回答正负的问题,需要取正负号来获得最终的结果,而这里直接算完分数就是一个实数,而regression要得就是实数。

 
 


 
 

如图来表示 linear hypothese:

 
 

如果我们今天输入是一维的话,就如左图,x是一个维度,y就是结果,而衡量标准就是最能fit这些(x,y)的线,找出这线的一个方法就是所有点到线的距离总和最小。

如果是二维输入的话,就如右图,这里我们的衡量标准就是一个平面。

 
 

找出衡量标准这就是 linear regression要做的事情。实际点到预测平面(线or其他)的差就是余数(residuals/误差),这个余数总和尽量是越小越好。

 
 


 
 

那么我们怎么去衡量余数总和到底是小还是不小?

 
 

这个问题就是错误衡量方式,传统做法就是错误的平方和,这样 Ein/Eout的求解公式就会如上图。

 
 

到这边就已经知道了如何去衡量Ein,下一步就是考虑我们如何去使得Ein最小化。

这里大家可以回顾一下1-8课讲的内容,这里的流程完全fit以前讲的流程。

 
 


 
 

小测验。

 
 


 
 

列出Ein的公式,考虑我们怎么样求到一个w,使得Ein最小化。

 
 

WXn:实际的预测是什么样子

Yn:期望的预测会是什么样子

平方就是错误的衡量方式:取错误的平方

1/N:为了化简

 
 

第一步 是 W转置*Xn 变成 Xn转置*W 交换一下,目的只是让大家看得更清楚。

第二步 这是一个连加公式,可以写成向量形式

第三步 化简向量,提出公用的部分W

第四步 红色的部分就是一个X矩阵,紫色部分就是一个y向量,整理一下就是一个简单的式子。

 
 


 
 

上面得到的式子,化简后如上式。

这个式子中唯一的变量就是W,这是一个可微的凸函数!如示意图。

也就是说最低点就是梯度(做微分)值为0!如右边公式。

 
 

所以:我们现在的任务变成了 希望找到一个wi希望其梯度为0.

 
 


 
 

求解:

上面公式中的平方展开,得到三个项命名为:A矩阵, b向量, c常数。

 
 

假设w是一个维度,整个就是一元二次方程式,就可以直接求解,如左边公式。

如果w是一个向量,解就如右边公式(见线性代数的内容)。

 
 

最终要求的梯度就如上面的公式。

 
 


 
 

我们要得就是梯度 = 0

这个式子里面我们唯一不知道的就是w,整个其实就是一元一次方程组。

 
 

也就是说X存在反矩阵就可以直接求解得到w。(实际上大部分情况下X都存在反矩阵,因为只要满足 N 大于等于 d+1 就行,这个基本都满足的。不满足的时候线性代数也能求解,具体不详细说明了,参见pseudo-inverse函数实现。)

 
 


 
 

所以 linear regression 算法总结一下要做的分为三步:

 
 

第一步 通过资料获得两个矩阵;

第二步 从X算 pseudo-inverse矩阵;

第三步 pseudo-inverse矩阵和y乘起来,就是你要回传的权重,就是结果。

 
 


 
 

小测验。

 
 


 
 

上面这个真的是一个机器学习算法么?

 
 

  1. 不是:上面是一个 analytic solution,就是一步就算出结果了,没看到学习过程,没有观察到进步的过程。
  2. 是:有一个好的Ein,保证有好的Eout,看起来是一步登天,实际上算pseudo-inverse的过程就是学习的过程。Pseudo-inverse矩阵运算的时候也是一个高斯收敛的过程。

 
 

只要保证 Eout 是好的,就是学习算法。

 
 


 
 

来说明怎样保证 Eout 是好的,看 Ein 的平均来分析 linear regression 可以work的很好。

 
 

现列出 Ein 平均的公式,计算一下会如上式 (噪声 * (1 – 自由度d+1/资料量N))。

具体推算如蓝色部分,prediction y可以用资料代替掉,就会得到上面的推导结果。

 
 

X * X(serudo-inverse) 叫做帽子矩阵(hat matrix)

 
 


 
 

上面是线性代数的复习,图讲的是:

粉红色:X的各个分量的展开,w的作用就是让x的风量来做所有的组合。

Linear regression 要做的就是 y 和 y_ 差别越小越好,就是y要投影到这个线性空间里面,就是上面的绿色线最小。

H表示的就是投影,I-H 表示的是余数的部分,我们关心的就是余数最小。

 
 

Trace(I – H)[就是I – H结果的对角线的部分] = N – (d + 1)

这个的物理意义:N个自由度的向量投影到d+1维的空间取余数,余数的自由度最多最多就是 N – (d+1)。

 
 


 
 

再来看 Ein 的平均,就可以用上面的推导拿过来,蓝色框内的推导可以那么改写。

也就可以得到黄色的结果。

 
 

类似的 Eout 也可以那么去得到。

 
 


 
 

从上面 Ein / Eout 的式子可以得到 learning curve 图,描述的是我们的资料量和错误率。

 
 

sigma平方就是 noise

平均错误率就是 2倍的(d+1)/N

 
 

这里说的事平均的情况是什么样,以前讨论的VC bound则是考虑的最坏情况,但是结果类似。

 
 

因此学习其实真的已经发生了。

 
 

上面整个部分数学推倒不那么重要,但是其物理意义要理解。

 
 


 
 

小测验。

 
 


 
 

Linear classification

输出是正负,求解比较困难

 
 

Linear regression

输出是实数,很好求解

 
 

正负1也是一种实数,那么能不能直接用linear regression来求解classification?

 
 


 
 

Linear classification/regression 最大的差别在于错误的衡量方式。

 
 

如图所示的例子,左边假设想要1,右边假设想要-1,错误用红色和蓝色线表示.你会发现不管怎么衡量,平方的错误一定比01错误来得大。

 
 


 
 

VC bound 曾经告诉我们:

classification Eout <= classification Ein + …

 
 

上面一页则告诉我们:

Classification Ein <= regression Ein + …

 
 

也就有

Classification Eout <= regression Ein + …

 
 

所以可以回答一开始的问题,可以用linear regression来求解classification,这是对的。

 
 

也可以解释成:

因为 01错误 不好求解,因此换一个 平方错误 作为hat来求解(宽松一点的bound),也可以得到一样的结果,这是对的。【应用up bound】

 
 


 
 

小测验:上面三个都对应很重要的机器学习演算法

 
 


 
 

小结:

 
 

介绍了linear regression演算法。从问题出发:找一个平面或者函数来描述我们所看到的实数的资料是怎么样的;讲了他的演算法,非常简单一步到位得到解析解;我们做了分析得到其平均来说的错误率是2(d+1)/N;最后我们证明了linear regression这个方法可以被用在classification上面,只要其错误衡量是classification的上限。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags