最小角回归法

最小角回归相当于前向选择法和前向梯度法的一个折中算法，简化了前项梯度法因(epsilon)的迭代过程，并在一定程度的保证了前向梯度法的精准度。

通常用最小角回归法解决线性模型的回归系数。对于一个有(m)个样本，每个样本有(n)个特征的训练集而言，假设可以拟合一个线性模型(Y=omega^TX)，其中(Y)是(m*1)的向量，(X)是(m*n)的矩阵，(omega)是(n*1)的向量。即可通过最小角回归法求得最小化该模型的参数(omega)。

首先把矩阵(X)看成(n)个(m*1)的向量(X_i quad(i=1,2,cdots,n))，之后选择与向量(Y)余弦相似度最大，即与(Y)最为接近的一个变量(X_i)，使用类似于前向选择法中的残差计算方法得到新的目标(Y_{err})，此时不同于前向梯度法的一小步一小步走，而是走到出现一个(X_jquad(j=1,2,i-1,i+1,cdots,n))的时候，此时(X_i)和(Y_{err})的余弦相似度等于(X_j)和(Y_{err})的余弦相似度，这个时候残差(Y_{err})沿着(X_i)和(X_j)的角平分线方向走，知道出现第三个特征(X_k)和(Y_{err})的相关度等于(X_i)和(Y_{err})的余弦相似度等于(X_j)和(Y_{err})的余弦相似度的时候，使用这三者的共同角平分线，作为残差(Y_{err})的路径方向，直到所有变量取完了，停止算法，即可得到(omega)。

一、举例

# 举例图例
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
%matplotlib inline
font = FontProperties(fname='/Library/Fonts/Heiti.ttc')

# X1*w1
plt.annotate(xytext=(2, 5), xy=(8, 5), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='r'))
plt.text(6, 4.5, s='$X_1*omega_1$', color='g')
# X1
plt.annotate(xytext=(2, 5), xy=(4, 5), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='k'))
plt.text(2.5, 4.5, s='$X_1$', color='g')
# X2
plt.annotate(xytext=(2, 5), xy=(3, 7), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='k'))
plt.text(2, 6, s='$X_2$', color='g')
# Y
plt.annotate(xytext=(2, 5), xy=(12, 8), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='k'))
plt.text(5, 7.5, s='$Y$', color='g')

# X1
plt.annotate(xytext=(8, 5), xy=(10, 5), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='r'))
plt.text(8.5, 4.5, s='$X_1$', color='g')
# X2
plt.annotate(xytext=(8, 5), xy=(9, 7), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='r'))
plt.text(8, 6, s='$X_2$', color='g')
# w2(X1+X2)
plt.annotate(xytext=(8, 5), xy=(12, 8), s='', color='r',
             arrowprops=dict(arrowstyle="->", color='gray'))
plt.text(10.5, 6.3, s='$(X_1+X_2)omega_2$', color='g')


plt.xlim(0, 13)
plt.ylim(2, 13)
plt.title('最小角回归法举例', fontproperties=font, fontsize=20)
plt.show()

png

上图假设(X)为(2)维，首先可以看出，离(Y)最接近的是(X_1)，首先在(X_1)上走一段距离，知道残差和(X_1)的相关度等于残差和(X_2)的相关度，即残差在(X_1)和(X_2)的角平分线上，由于(X)为(2)维，此时沿着角平分线走，直到残差足够小时停止，如果此时(X)不是(2)维，则继续选择第3个、第4个特征走下去。

二、最小角回归法优缺点

2.1 优点

特别适合特征维度高于样本数的情况

2.2 缺点

迭代方向是根据目标的残差定的，所以算法对训练集中的噪声特别敏感

三、小结

前向选择法由于涉及到投影，只能给出一个近似解；前向梯度法则需要自己手动调试一个很好的(epsilon)参数；最小角回归法结合了两者的优点，但是至于算法具体好坏害的取决于训练集，即算法的稳定性无法保证。

对算法具体计算有兴趣的同学，可以参考Bradley Efron的论文《Least Angle Regression》，https://pan.baidu.com/s/10if9FGdkwEZ4_BolzCGszA ，如果你下载看了，恭喜你入坑。