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

  统计/机器学习 回归分析 监督式学习 开放问题    浏览次数:3407        分享
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个回答 
7

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
你好,上述解释中,当迭代第一次时,z_0=0,学习步长设置为1,那么condition number不就是X的condition么,即S中的非零最大项除以S中的非零最小项,那应该是等于未正则化时的condition number的不是么,也就是说刚开始迭代condition number不是应该最大才对么? - CE_PAUL   2019-11-29 18:54
解的condition number c1是系统函数A的condition number c0的倒数。c0在等号左边,c1在等号右边。为了和c0区别,c1应该叫inverse condition number。在刚开始迭代欠拟合时c0最大,c1最小。 - Zealing   2019-11-30 00:32
你好,请问等号左边右边的由奇异值组成的对角矩阵不是互为逆的关系么,又因为是对角矩阵,因而就是每个元素互为倒数,那么其实最大值处以最小值结果不是想等么?请问倒数(inverse condition number)是哪里推导出来的呢? 这样看难道说随着迭代过程,其对应的系统的病态性在下降,而解却趋向于过拟合? - CE_PAUL   2019-11-30 01:37
我前面说错了。c0=c1。不是倒数。随着迭代,系统条件数增加,趋于过拟合。 - Zealing   2019-12-03 15:13
多谢多谢 - CE_PAUL   2019-12-07 01:35
1

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

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

WinJ   2019-02-27 11:11

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


  相关讨论

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

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

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

L0 norm 正则是什么意思?

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

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

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

为什么很少用L0范数惩罚正则项?

如何简单理解正则化

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

  随便看看

T检验的effect size是什么?有什么含义吗?

如果样本不是正态分布,还能用t-test或者z-test吗?

如何获取pyspark DataFrame的行数和列数?

两个独立的正态随机变量的乘积服从什么分布?

Resnet-18, Resnet-50, Resnet-101这些模型里的数字是什么意思?