如何理解“迭代步骤本身就是一个正则化的过程”

  统计/机器学习 回归分析 监督式学习 开放问题    浏览次数:465        分享
0

在王彦飞的《反问题的计算方法及其应用》当中,在介绍迭代的Tikhonov正则化的章节中提到,“其实迭代过程本身就具备有正则化的效果”,这个思想该怎么去理解呢,是不是对面一个线性回归问题:

X*w=Y, X是M×N矩阵,w是N×1向量,Y是M×1向量

此时若将该式子写作迭代式:

X*(w_(k+1)-w_k)=Y-w_k

进而使用各类正则化算法(Tikhonov、TV、L1、... ...)去求解,这样通过迭代过程就都可以强化正则化的效果?


 

CE_PAUL   2019-02-25 16:38



   2个回答 
6

1.目标:

$w$对应的condition number可以作为正则化强度的测量,值越大说明正则化越弱。

2.方法:

如何得到$w$对应的condition number。

令数据矩阵$X$有SVD,$X=USV^T$。

带L2norm的OLS解:

$$w_{OLS-reg}=(X^TX+b)^{-1}XTy=V(S^{-2}+b)SU^Ty$$

带L2norm的Gradient Descent解:

$$w_{k}=(1-aX^TX-ab)w_{k-1}+aX^Ty=V(1-ab-aS^2)V^Tw_{k-1}+VaSU^Ty$$

 假设$w_0=0$,可把$w_{k-1}$分解到$X$的range space $w_{k-1}=Vz_{k-1}U^Ty$

有$w_{k}=V((1-ab-aS^2)z_{k-1}+aS)U^Ty$。

$z_{k}=(1-ab-aS^2)z_{k-1}+aS$

其中$a$为学习步长,$b$为L2norm的权重,当$b=0$时无正则项。

$condition number(w_k)=\frac{max(z_k)}{min(z_k)}$

3.实验:

做实验把OLS/GD,带/不带L2norm这四种情况的condition number,以及在range space上投影 $z_k$画出来


4.结论:

GD的condition number增大,并收敛于OLS。绿色收敛于紫色,蓝色收敛于红色。GD迭代过程可理解为有一个逐渐变弱正则化。当迭代无穷步时,正则化消失。越早early stopping,正则化越强。所以early stopping=正则化

Regularization_wiki上有差不多的结论。

import numpy as np
import matplotlib.pyplot as plt
n=2000 # number of iterations
s=np.array([1.,1.E-3])*1. # singular values of X
a=0.01 # step size
b=.5   # L2 regularizer weight

c_OLS=s[0]/s[1]
c_OLS_reg=(s[1]/(s[1]**2+b))/(s[0]/(s[0]**2+b))

z=np.zeros([n,2])
c=np.zeros([n,1])
z_reg=np.zeros([n,2])
c_reg=np.zeros([n,1])

t1=1.-0*a-a*np.power(s,2)
t1_reg=1.-b*a-a*np.power(s,2)
t2=a*s
np.random.seed(0)
# z starts at the orginal point
z[0]=t2
z_reg[0]=t2
## z starts at a random point
# z[0]=np.random.rand(2)*1
# z_reg[0]=np.random.rand(2)*1

for i in range(1,n):
  z[i]=np.multiply(t1,z[i-1])+t2
  z_reg[i]=np.multiply(t1_reg,z_reg[i-1])+t2
  
for i in range(n):
  c[i]=z[i,1]/z[i,0]
  c_reg[i]=z_reg[i,1]/z_reg[i,0]
  
tt=np.arange(0,n)
tt1=np.ones([n,1])
plt.figure(figsize=[15,5])
plt.subplot(131)
plt.plot(c,'-o',label='GD no reg')    
plt.plot(c_reg,'-^',label='GD with reg')
plt.plot(tt,c_OLS*tt1,'-.',label='OLS no reg')
plt.plot(tt,c_OLS_reg*tt1,'--',label='OLS with reg')
plt.yscale('log')
plt.legend()
plt.title('Condition number')
plt.xlabel('Iteration')

plt.subplot(132)
plt.plot(z[:,0],'-o',label='GD no reg')      
plt.plot(z_reg[:,0],'-^',label='GD with reg')
plt.plot(tt,1/s[0]*tt1,'-.',label='OLS no reg')
plt.plot(tt,s[0]/(s[0]**2+b)*tt1,'--',label='OLS with reg')
plt.yscale('log')
plt.legend()
plt.title('z0')
plt.xlabel('Iteration')

plt.subplot(133)
plt.plot(z[:,1],'-o',label='GD no reg')     
plt.plot(z_reg[:,1],'-^',label='GD with reg')
plt.plot(tt,1/s[1]*tt1,'-.',label='OLS no reg')
plt.plot(tt,s[1]/(s[1]**2+b)*tt1,'--',label='OLS with reg')
plt.yscale('log')
plt.legend()
plt.title('z1')
plt.xlabel('Iteration')
plt.show()
SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2019-02-26 06:04

十分十分感谢! - CE_PAUL   2019-02-26 08:57
1

笼统地讲,迭代的过程就是模型学习数据的过程,也是从欠拟合到过拟合的过程。所以及时停止迭代可以看作一种正则效果,防止模型过拟合。

SofaSofa数据科学社区DS面试题库 DS面经

WinJ   2019-02-27 11:11

感谢 - CE_PAUL   2019-02-27 22:43


  相关主题

为什么正则项通常都是用L1或者L2,而不是其他的?   2回答

L1范数回归与TV正则化哪个的回归效果更好?   1回答

L0 norm 正则是什么意思?   2回答

Lasso和岭回归的正则项包含截距(常数项)吗?   2回答

L1正则化和L2正则化的区别?L1为啥具有稀疏性?   5回答

最小角回归是天然的LASSO化?正则化参数怎么体现?   3回答

如何简单理解正则化   4回答

正则项里的L1,L2是什么意思?   1回答

xgboost有正则项为什么还会过拟合呢?   4回答

XGBoost损失函数中正则项的理解   1回答

无监督学习(比如K Means)里怎么加正则项来防止过拟合   3回答

为什么过拟合不好?   8回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!