Ridge Regression and LASSO Regression.

岭回归与LASSO回归是将正则化思想引入线性回归模型后得到的方法。

1. Ridge Regression

岭回归(Ridge Regression)是引入了L2正则化的线性回归,求解问题如下:

L(w)=Ni=1(wTx(i)y(i))2+λ||w||2=(Xwy)T(Xwy)+λwTwL(w)=Ni=1(wTx(i)y(i))2+λ||w||2=(Xwy)T(Xwy)+λwTw

岭回归通过增加对权重的限制,使得模型把有限的权重放到更重要的特征维度上;并且每个权重都不会太大,否则自变量的微小变化将会引起输入的巨大变化。

令梯度为零可以得到:

wL(w)=2XTXw2Xy+2λw=0wL(w)=2XTXw2Xy+2λw=0

该问题的解析解为:

w=(XTX+λI)1Xyw=(XTX+λI)1Xy

注意到正则化系数λλ通常大于零,故矩阵XTX+λIXTX+λI一定可逆

正则化系数λλ越大,不重要的维度的权重会减小;因此通过调整正则化系数可以实现初步的特征选择。下图给出了某岭回归模型中八个维度的权重随正则化系数的变化曲线。从图中可以看出,特征维度4和5的重要性较大,并且特征4起到正作用,特征5起到反作用。

求解岭回归问题的程序如下:

def RidgeRegression(X, Y):
    return np.dot(np.linalg.inv(np.dot(X.T,X)+lambd*np.eye(X.shape[1])), np.dot(X,Y))

⚪ 讨论:岭回归等价于噪声和先验服从高斯分布的最大后验估计

引入高斯噪声εε~N(0,σ2)N(0,σ2),对线性回归建模:

y=wTx+εy=wTx+ε

贝叶斯角度认为参数ww不再是常数,而是随机变量,假设其先验概率为N(0,σ20)N(0,σ20),

由贝叶斯定理,参数ww的后验概率:

P(w|y)=P(y|w)P(w)P(y)P(y|w)P(w)P(w|y)=P(y|w)P(w)P(y)P(y|w)P(w)

由最大后验估计:

ˆw=argmaxwlogP(w|y)=argmaxwlogP(y|w)P(w)=argmaxwlog(Ni=112πσexp((y(i)wTx(i))22σ2)12πσ0exp(wTw2σ20))=argmaxwNi=1log(12πσexp((y(i)wTx(i))22σ2)12πσ0exp(wTw2σ20))argmaxwNi=1(y(i)wTx(i))22σ2wTw2σ20=argminwNi=1(y(i)wTx(i))2+σ2σ20wTw

该问题等价于引入L2正则化的最小二乘法(岭回归)。

2. Kernel Ridge Regression

核方法引入岭回归,即可得到核岭回归(Kernelized Ridge Regression)

岭回归的目标函数:

L(w)=1NNi=1(wTx(i)y(i))2+λNwTw

根据表示定理,上述优化问题的最优解w可以表示为所有样本的线性组合

w=Nn=1βnx(n)

代入目标函数:

L(β)=1NNi=1(Nn=1βnx(n)Tx(i)y(i))2+λNNi=1Nj=1βiβjx(i)Tx(j)

引入核函数来代替样本的特征转换和内积运算,记K(x,x)=φ(x)Tφ(x),则核岭回归的损失函数为:

L(β)=1NNi=1(Nn=1βnK(x(n),x(i))y(i))2+λNNi=1Nj=1βiβjK(x(i),x(j))

上式写作矩阵形式:

L(β)=1N(yKβ)T(yKβ)+λNβTKβ

β求梯度,令其为零,(注意到K是对称矩阵)可得:

βL(β)=1N(2KTKβ2KTy)+λN2Kβ=2KTN(Kβy+λβ)=0

可解得引入核岭回归的解析解:

β=(K+λI)1y

对矩阵K+λI的讨论:

求得β后,可以得到回归函数:

y=Nn=1βnφ(x(n))Tφ(x)=Nn=1βnK(x(n),x)

3. LASSO Regression

LASSO回归是引入了L1正则化的线性回归,求解问题如下:

L(w)=Ni=1(wTx(i)y(i))2+λDd=1|wd|=(Xwy)T(Xwy)+λ||w||1

选择L1范数使得学习得到的权重更加稀疏,不重要的权重接近0

由于引入了L1正则化项,因此LASSO回归的目标函数不满足处处可到,没有闭式解;在实践中常采用梯度下降搜索法(坐标轴下降法)求解,即依次对权重wd求局部最优,使其梯度趋近于0,不断迭代直至所有权重都不产生显著变化。

LASSO回归的目标函数可写作:

L(w)=Ni=1(wTx(i)y(i))2+λDd=1|wd|=Ni=1(Dd=1wdx(i)dy(i))2+λDd=1|wd|=Ni=1((Dd=1wdx(i)d)2+(y(i))22(Dd=1wdx(i)d)y(i))+λDd=1|wd|

求上式对权重wd的梯度:

L(w)wd=Ni=1(2(Dd=1wdx(i)d)x(i)d2x(i)dy(i))+λsign(wd)=2Ni=1((Dd=1wdx(i)dy(i))x(i)d)+λsign(wd)=2xTd(wTx(i)y(i))+λsign(wd)

则可以通过梯度下降更新权重wd

wdwdα(2xTd(wTx(i)y(i))+λsign(wd))
# 坐标轴下降法
def CoordinateDescent(X, Y, epochs, lr, lam):
    N, D= X.shape
    w = np.ones([D, 1])
    # 进行 epoches 轮迭代
    for k in range(epochs):
        # 保存上一轮的w
        pre_w = copy.copy(w)
        # 逐维度进行参数寻优
        for d in range(D):
            # 在每个维度上找到最优的w_d
            for j in range(epochs):
                Y_hat = X*w
                g_d = 2*X[:,d].T*(Y_hat-Y) + lam*np.sign(w[d])
                # 进行梯度下降
                w[d] = w[d] - g_d*lr
                if np.abs(g_d) < 1e-3:
                    break
        # 计算上一轮的w和当前轮w的差值,如果每个维度的w都没有什么变化则退出
        diff_w  = np.array(list(map(lambda x:abs(x)<1e-3,pre_w-w)))
        if diff_w.all():
            break
    return w

⚪ 讨论:LASSO回归等价于噪声服从高斯分布、参数服从拉普拉斯分布的最大后验估计。

引入高斯噪声ε~N(0,σ2),对线性回归建模:

y=wTx+ε

贝叶斯角度认为参数w不再是常数,而是随机变量,假设其先验概率为拉普拉斯分布L(0,σ20):

w~L(0,σ20)=12σ20exp(|w|σ20)

由贝叶斯定理,参数w的后验概率:

P(w|y)=P(y|w)P(w)P(y)P(y|w)P(w)

由最大后验估计:

ˆw=argmaxwlogP(w|y)=argmaxwlogP(y|w)P(w)=argmaxwlog(Ni=112πσexp((y(i)wTx(i))22σ2)12σ20exp(|w|σ20))=argmaxwNi=1log(12πσexp((y(i)wTx(i))22σ2)12σ20exp(|w|σ20))argmaxwNi=1(y(i)wTx(i))22σ2|w|σ20=argminwNi=1(y(i)wTx(i))2+2σ2σ20|w|

该问题等价于引入L1正则化的最小二乘法(LASSO回归)。