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

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()

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