老饼讲解-神经网络
自实现-径向基神经网络
径向基
OLS正交最小二乘法
作者 : 老饼 日期 : 2022-06-16 09:49:38 更新 : 2022-08-10 12:07:12
本站原创文章,转载请说明来自《老饼讲解-BP神经网络》bp.bbbdata.com


OLS(Orthogonal least squares) 正交最小二乘算法,

它是基于最小二乘法的基础上,一种贪婪式选择子集的算法,

是径向基神经网络常用的经典算法。

本文讲述OLS的思路、推导与算法流程,代码另行参考《OLS算法代码Demo》


本文主要参考自《Orthogonal leastsquares methods and their application to non-linear system identification》

S.Chen,S.A.Billings and W.Luo,Int.J.Control.,Vol.50,No.5,PP.1873-1896, 

思想上保持一致,但为便于理解,思路细节有所出入,感谢阅读!



  01. OLS算法解决什么问题  


  问题  


现有A与y,我们希望求一x使Ax与y的最小二乘误差最小,即Ax最佳逼近y,这个问题使用最小二乘解法即可:
 
现问题来了,有时A有很多很多列,我们希望最小二乘误差在允许范围内的条件下,尽量使用A更少的列(即求A的一个列子集As)。
OLS正交最小二乘法正是解决这个问题的方法。



  OLS思路与难点  


OLS的思路是,
将A的列逐个添加到As, 
然后用最小二乘法求得As与y的最小二乘误差,
满足条件就不再添加。
问题的难点在于,每次该选哪一列,才能使误差最大下降?




  02. A为单位正交列时的选择方法  


  单位正交列时的最小二乘解  


我们知道 ,最小二乘的解是
 

在 A 为单位正交列矩阵时( 即列列之间正交,且每列长度为1,即)
那么上式则为



假设现在已选出的列组成  ,则  



  添加新列前后最小预测误差  


未添加新列时,预测值 与  的最小二乘误差为 


添加新的一列a之后,最小二乘误差则为
 



  误差变化量与列的选择  




●  误差下降量



则 加入a带来的误差下降量为:
 
  
 
 
因此,我们每次添加新列时,只要算出选择池里各列的
 最大的列,就是能使误差下降最快的列。 


   

● 关于误差下降占比


也可以使用误差下降占比来选择列,
老饼个人认为没有必要,但如果是作为终止条件,倒是可以考虑。

误差占比是这样的:
在使用最小二乘法求得x后,x一定是让E最小的解,则有:

即误差上限就是(也可以理解为未添加任何列时的误差)。

则定义 误差下降占比为:


  






  03. 非单位正交列的选择方法  


A一般不是非单位正交列,因此我们需要添加一些处理。

 

1、将子集映射成单位正交集


记已选出的列组成的矩阵为 As,
记As中加入新的一列a后组成的矩阵为Asn,Asn= [As,a]。

As列正交并单位化后记为As',
 Asn列正交并单位化后为Asn' ,

Asn'并不是唯一的,这里我们取Asn'=[As',a'] ,
其中,a’由a与As'正交并单位化生成。


2、子集误差增长与单位正交集一致


由于,As与As'所表示的空间是一样的,所以As与As'到y的距离相同。
( 即用As求得的最小二乘误差与 As'求得的最小二乘误差一致)

同理, Asn与Asn'求得的最小二乘误差也相同。

因此,在As的基础上,添加列a的误差,与在As'的基础上添加a'的误差一致。


3、在单位正交集找出误差下降最大列


(1)算出对应的单位正交集:
由As算出As',再算出选择池P中的每一列p与As'正交并单位化后的p'

(2)计算在单位正交集As'中,加入哪列使误差下降最快
计算每个p'的 ,取 最大的列,就是能使误差下降最快的列。

(3)对应的,使单位正交集As'误差下降最快的列p'对应的p,就是令原集合As误差下降最快的列。




  04. 多个输出时的选择方法  



y往往并不是列向量,而是多个列向量,我们这里把以上结果拓展到y为多列的情况。


以下为老饼个人的拓展推导,仅供参考:


  第一种拓展方法  


可以把多列问题转为单列
例如y为两列:可以转为单列问题:




列a带来的下降误差则为



因此,y为多列的时候,只要使用 

来选择列即可。

如果考虑到每列的误差量级不同,则可以使用误差下降占比。


  第二种拓展方法  


把每列输出各自看待,假设有n列,则定义下降误差为:
 


下降误差占比为:
 


   两种拓展方法比较  


第一种方法是谨遵误差定义,真正意义上误差下降最快的变量。
而第二种拓展方法,是强行合并各个y的误差,而非真实整体误差。
但第二种方法的好处是,把每个y独立处理,改为下降误差占比什么的,非常方便,可以完全照搬y一维的任何方法。



  05. 算法流程  

  符号说明  


已选列池S(select):从A中选出的列子集,用于拟合y                                                                                
待选列池R(rest):所有未被选入的列的集合                                                                                              
单位正交待选列池sR( standar Rest):由待选列池所有列,对已选列池中所有列进行正交,并单位化后得到


  流 程  





1、初始化已选列池,待选列池,单位正交待选列池


S:初始化已选列池S为空,
R:初始化待选列池为A,  
sR:将待选列池各列单位化,作为单位正交待选列池sR的初始化


2、计算待选列的误差下降量


通过公式,计算单位正交待选列池各列的误差下降量,

y为单列时:
 

y为多列时可以参考使用:
  


3、选择使误差下降最大的列


(1) 获取本次选择的列: 
通过比较各列的 ,得到使误差下降最大的列,假设为k,

(2) 更新待选列池R、已选列池S:
  将待选列池的第k列移到已选列池。

(3) 更新单位正交待选列池sR:   
 
理论上将sR的第k列移除,将sR各列与正交化后的S进行正交化,但事实不必如此。
由于之前sR已经与未加入新列的S正交化了,因此,只需将sR对新列正交化即可。


将sR各列(第k列除外)对第k列进行正交化,并单位化,然后移除第k列。

PASS :
 用向量a生成与向量b的正交量d的公式为:
 (即a减去a在b的投影向量) 
 




4、检查是否满足终止条件,否则继续步骤2、3


终止条件:
(1) 计算S的最小二乘误差,如果小于目标误差,则终止。
(2) 待选列池为空,则终止。                                           

          


5、输出结果


输出已选列池S和最终误差

具体代码查看《OLS算法代码Demo》




  05. 与原论文中OLS的差异  


大方面的差异主要有两点:


1、推导过程避开QR分解


原论文中,OLS只要求列与列正交,而不要求列单位化,从而使推导中要使用QR分解等手段,这样对理解带来极大的不便。
本文直接先要求正交并单位化,这样理解上非常简洁。反正最后都要拓展到一般形式(非正交非单位化),所以在结论上并无出入。


2、优先使用误差下降量


原文中,使用的是误差下降占比,但笔者认为,使用误差下降量更为直接,所以先引入误差下降量,再添加误差下降占比的定义。


对于这样的修改,主要是考虑到,笔者是从事教学,而非学术,如果为了强行完全遵循原学术论文,而使用过于复杂的思路,这样过于刻板。

如果需要理解原版思路,请直接查看原paper。








 End 










联系小饼