首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习10:梯度优化与L正则化稀疏性

机器学习10:梯度优化与L正则化稀疏性

作者头像
用户5473628
发布2019-08-08 14:59:25
1.9K0
发布2019-08-08 14:59:25
举报
文章被收录于专栏:MiningAlgorithmsMiningAlgorithms

目录:

1,剃度验证

2,随机梯度下降(SGD)

3,小批量梯度下降法(Mini-Batch Gradient Descent)

4,随机梯度下降法的加速:

4.1,动量(Momentum)法

4.2,AdaGrad法

4.3,Adam方法

4.4,其他SGD优化方法

5,模型参数的稀疏性与L1正则化:

5.1,解空间形状

5.2,函数叠加

5.3,贝叶斯先验

6,代码实现:

6.1,梯度优化

6.2,剃度验证

6.3,SGD

6.4,梯度下降法优化线性回归模型

1,剃度验证:

在用梯度下降法求解优化问题时,最重要的操作就是计算目标函数的梯度。对于一些比较复杂的机器学习模型,如深度神经网络,目标函数的梯度公式也非常复杂,很容易写错。因此,在实际应用中,写出计算梯度的代码之后,通常需要验证自己写的代码是否正确。

当h充分小时,pi和qi都很接近0,可以近似认为h2项前面的系数是常数M,因此近似式的误差为:

在实际应用中,我们随机初始化θ,取h为较小的数(例如10−7),并对 i=1,2,...,n,依次验证:

是否成立。如果对于某个下标i,该不等式不成立,则有以下两种可能:

(1)该下标对应的M过大。

(2)该梯度分量计算不正确。

此时可以固定θ,减小h为原来的10−1,并再次计算下标i对应的近似误差,若近似误差约减小为原来的10−2,则对应于第一种可能,我们应该采用更小的h重新做一次梯度验证;否则对应于第二种可能,我们应该检查求梯度的代码是否有错误。

2,随机梯度下降(SGD):

经典的优化方法,如梯度下降法,在每次迭代时需要使用所有的训练数据,这给求解大规模数据的优化问题带来了挑战。

梯度下降法对模型参数的更新公式为:

经典的梯度下降法在每次对模型参数进行更新时,需要遍历所有的训练数据。当M很大时,这需要很大的计算量,耗费很长的计算时间,在实际应用中基本不可行。

为了解决该问题,随机梯度下降法(Stochastic Gradient Descent,SGD)用单个训练样本的损失来近似平均损失,即:

因此,随机梯度下降法用单个训练数据即可对模型参数进行一次更新,大大加快了收敛速率。该方法也非常适用于数据源源不断到来的在线更新场景。

3,小批量梯度下降法(Mini-Batch Gradient Descent):

为了降低随机梯度的方差,从而使得迭代算法更加稳定,也为了充分利用高度优化的矩阵运算操作,在实际应用中我们会同时处理若干训练数据,该方法被称为小批量梯度下降法(Mini-Batch GradientDescent)。假设需要同时处理m个训练数据(m <M),则目标函数及其梯度为:

对于小批量梯度下降法的使用,有以下三点需要注意的地方。

(1)如何选取参数m?在不同的应用中,最优的m通常会不一样,需要通过调参选取。一般m取2的幂次时能充分利用矩阵运算操作,所以可以在2的幂次中挑选最优的取值,例如32、64、128、256等。

(2)如何挑选m个训练数据?为了避免数据的特定顺序给算法收敛带来的影响,一般会在每次遍历训练数据之前,先对所有的数据进行随机排序,然后在每次迭代时按顺序挑选m个训练数据直至遍历完所有的数据。

(3)如何选取学习速率α?为了加快收敛速率,同时提高求解精度,通常会采用衰减学习速率的方案:一开始算法采用较大的学习速率,当误差曲线进入平台期后,减小学习速率做更精细的调整。最优的学习速率方案也通常需要调参才能得到。

综上,通常采用小批量梯度下降法解决训练数据量过大的问题。每次更新模型参数时,只需要处理m个训练数据即可,其中m是一个远小于总数据量M的常数,这样能够大大加快训练过程。

4,随机梯度下降法的加速:

提到深度学习中的优化方法,人们通常会想到随机梯度下降法。但是,随机梯度下降法并不是万金油,有时候反而会成为一个坑。当你设计出一个深度神经网络时,如果只知道用随机梯度下降法来训练模型,那么当你得到一个比较差的训练结果时,你可能会放弃在这个模型上继续投入精力。然而,造成训练效果差的真正原因,可能并不是模型的问题,而是随机梯度下降法在优化过程中失效了。

想象一下,你正在下山,视力很好,能看清自己所处位置的坡度,那么沿着坡向下走,最终你会走到山底。如果你被蒙上双眼,只能凭脚底踩石头的感觉判断当前位置的坡度,精确性就大大下降,有时候你认为的坡,实际上可能并不是坡,走上一段时间发现没有下山,或者曲曲折折走了好多弯路才下山。

类似地,批量梯度下降法(BatchGradient Descent,BGD)就好比正常下山,而随机梯度下降法就好比蒙着眼睛下山。具体介绍一下两种方法。

批量梯度下降法在全部训练集(M)上计算准确的梯度,即:

而随机梯度下降法则采样单个样本来估计的当前梯度。

可以看出,为了获取准确的梯度,批量梯度下降法的每一步都把整个训练集载入进来进行计算,时间花费和内存开销都非常大,无法应用于大数据集、大模型的场景。相反,随机梯度下降法则放弃了对梯度准确性的追求,每步仅仅随机采样一个(或少量)样本来估计当前梯度,计算速度快,内存开销小。但由于每步接受的信息量有限,随机梯度下降法对梯度的估计常常出现偏差,造成目标函数曲线收敛得很不稳定,伴有剧烈波动,有时甚至出现不收敛的情况。下图展示了两种方法在优化过程中的参数轨迹,可以看出,批量梯度下降法稳定地逼近最低点,而随机梯度下降法的参数轨迹曲曲折折简直是“黄河十八弯”。

4.1,动量(Momentum)法:

为了解决随机梯度下降法山谷震荡和鞍点停滞的问题,我们做一个简单的思维实验。想象一下纸团在山谷和鞍点处的运动轨迹,在山谷中纸团受重力作用沿山道滚下,两边是不规则的山壁,纸团不可避免地撞在山壁,由于质量小受山壁弹力的干扰大,从一侧山壁反弹回来撞向另一侧山壁,结果来回震荡地滚下;如果当纸团来到鞍点的一片平坦之地时,还是由于质量小,速度很快减为零。纸团的情况和随机梯度下降法遇到的问题简直如出一辙。直观地,如果换成一个铁球,当沿山谷滚下时,不容易受到途中旁力的干扰,轨迹会更稳更直;当来到鞍点中心处,在惯性作用下继续前行,从而有机会冲出这片平坦的陷阱。因此,有了动量方法,模型参数的迭代公式为:

具体来说,前进步伐−vt由两部分组成。一是学习速率η乘以当前估计的梯度gt;二是带衰减的前一次步伐vt−1。这里,惯性就体现在对前一次步伐信息的重利用上。类比中学物理知识,当前梯度就好比当前时刻受力产生的加速度,前一次步伐好比前一时刻的速度,当前步伐好比当前时刻的速度。为了计算当前时刻的速度,应当考虑前一时刻速度和当前加速度共同作用的结果,因此vt直接依赖于vt−1和gt,而不仅仅是gt。另外,衰减系数γ扮演了阻力的作用。

4.2,AdaGrad法:

惯性的获得是基于历史信息的,那么,除了从过去的步伐中获得一股子向前冲的劲儿,还能获得什么呢?我们还期待获得对周围环境的感知,即使蒙上双眼,依靠前几次迈步的感觉,也应该能判断出一些信息,比如这个方向总是坑坑洼洼的,那个方向可能很平坦。

随机梯度下降法对环境的感知是指在参数空间中,根据不同参数的一些经验性判断,自适应地确定参数的学习速率,不同参数的更新步幅是不同的。例如,在文本处理中训练词嵌入模型的参数时,有的词或词组频繁出现,有的词或词组则极少出现。数据的稀疏性导致相应参数的梯度的稀疏性,不频繁出现的词或词组的参数的梯度在大多数情况下为零,从而这些参数被更新的频率很低。在应用中,我们希望更新频率低的参数可以拥有较大的更新步幅,而更新频率高的参数的步幅可以减小。AdaGrad方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性,取值越小表明越稀疏,具体的更新公式表示为:

其中θt+1,i表示(t+1)时刻的参数向量θt+1的第i个参数,gk,i表示k时刻的梯度向量gk的第i个维度(方向)。另外,分母中求和的形式实现了退火过程,这是很多优化技术中常见的策略,意味着随着时间推移,学习速率(gk,i前面的系数)越来越小,从而保证了算法的最终收敛。

4.3,Adam方法:

Adam方法将惯性保持和环境感知这两个优点集于一身。一方面,Adam记录梯度的一阶矩(firstmoment),即过往梯度与当前梯度的平均,这体现了惯性保持;另一方面,Adam还记录梯度的二阶矩(second moment),即过往梯度平方与当前梯度平方的平均,这类似AdaGrad方法,体现了环境感知能力,为不同参数产生自适应的学习速率。一阶矩和二阶矩采用类似于滑动窗口内求平均的思想进行融合,即当前梯度和近一段时间内梯度的平均值,时间久远的梯度对当前平均值的贡献呈指数衰减。具体来说,一阶矩和二阶矩采用指数衰退平均(exponentialdecay average)技术,计算公式为:

其中β1,β2为衰减系数,mt是一阶矩,vt是二阶矩。

一阶矩相当于估计:由于当下梯度gt是随机采样得到的估计结果,因此更关注它在统计意义上的期望;二阶矩相当于估计,这点与AdaGrad方法不同,不是gt2从开始到现在的加和,而是它的期望。它们的物理意义是,当||mt||大且vt大时,梯度大且稳定,这表明遇到一个明显的大坡,前进方向明确;当||mt||趋于零且vt大时,梯度不稳定,表明可能遇到一个峡谷,容易引起反弹震荡;当||mt||大且vt趋于零时,这种情况不可能出现;当||mt||趋于零且vt趋于零时,梯度趋于零,可能到达局部最低点,也可能走到一片坡度极缓的平地,此时要避免陷入平原(plateau)。另外,Adam方法还考虑了mt,vt在零初始值情况下的偏置矫正。具体来说,Adam的更新公式为:

其中:

4.4,其他SGD优化方法:

除了上述三种随机梯度下降法变种,研究者还提出了以下几种方法。

(1)Nesterov Accelerated Gradient。该方法扩展了动量方法,顺着惯性方向,计算未来可能位置处的梯度而非当前位置的梯度,这个“提前量”的设计让算法有了对前方环境预判的能力。

(2)AdaDelta和RMSProp。这两个方法非常类似,是对AdaGrad方法的改进。AdaGrad方法采用所有历史梯度平方和的平方根做分母,分母随时间单调递增,产生的自适应学习速率随时间衰减的速度过于激进。针对这个问题,AdaDelta和RMSProp采用指数衰退平均的计算方法,用过往梯度的均值代替它们的求和。

(3)AdaMax。该方法是基于Adam方法的一个变种方法,对梯度平方的处理由指数衰退平均改为指数衰退求最大值。

(4)Nadam。该方法可看成Nesterov AcceleratedGradient版的Adam。

5,模型参数的稀疏性与L1正则化:

模型参数具有稀疏性有那些优点:稀疏性,说白了就是模型的很多参数是0。这相当于对模型进行了一次特征选择,只留下一些比较重要的特征,提高模型的泛化能力,降低过拟合的可能。

5.1,解空间形状:

上图从解空间形状角度展示了L1正则化与模型参数稀疏性关系:L1“棱角分明”的解空间显然更容易与目标函数等高线在角点碰撞,从而产生稀疏解。

5.2,函数叠加:

上图从函数叠加角度展示了L1正则化与模型参数稀疏性关系:目标函数变成L(w)+C|w|,其函数曲线为绿色。此时,最小值点在红点处,对应的w是0,产生了稀疏性。

加入L1正则项后,对带正则项的目标函数求导,正则项部分产生的导数在原点左边部分是−C,在原点右边部分是C,因此,只要原目标函数的导数绝对值小于C,那么带正则项的目标函数在原点左边部分始终是递减的,在原点右边部分始终是递增的,最小值点自然在原点处。

在一些在线梯度下降算法中,往往会采用截断梯度法来产生稀疏性,这同L1正则项产生稀疏性的原理是类似的。

考虑加上L2正则化项,目标函数变成L(w)+Cw2,其函数曲线为黄色。此时,最小值点在黄点处,对应的w*的绝对值减小了,但仍然非0。L2正则项在原点处的导数是0,只要原目标函数在原点处的导数不为0,那么最小值点就不会在原点,所以L2只有减小w绝对值的作用,对解空间的稀疏性没有贡献。

5.3,贝叶斯先验:

上图从函数叠加角度展示了L1正则化与模型参数稀疏性关系:L1正则化相当于对模型参数w引入了拉普拉斯先验,L2正则化相当于引入了高斯先验,而拉普拉斯先验使参数为0的可能性更大。

拉普拉斯分布在极值点(0点)处是一个尖峰,所以拉普拉斯先验分布中参数w取值为0的可能性要更高。

高斯分布在极值点(0点)处是平滑的,也就是高斯先验分布认为w在极值点附近取不同值的可能性是接近的。这就是L2正则化只会让w更接近0点,但不会等于0的原因。

6,代码实现:

6.1,梯度优化:

1),Gradient descent;2),将上述过程对象化;3),测试不同的学习率对结果的影响;4),增加最大迭代次数的限制,再次对象化;5),再次设定eta=1.1的情况,比较与上面的区别。

# 一、梯度下降:
# 1,Gradient descent:
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-1., 6, 141)
y = (x - 2.5) ** 2 - 1.

plt.plot(x, y)
plt.show()

epsilon = 1e-8  # 每步最小移动,小于这个说明达到收敛
eta = 0.1  # 学习率
def J(x):
    return (x - 2.5) ** 2 - 1.
def dJ(x):
    return 2 * (x - 2.5)
theta = 0
history_theta = [theta]
while True:
    gradient = dJ(theta)
    last_theta = theta
    theta = theta - eta * gradient
    history_theta.append(theta)
    if abs(J(last_theta) - J(theta)) < epsilon:
        break

plt.plot(x, J(x))
plt.plot(np.array(history_theta), J(np.array(history_theta)), color='r', marker='+')
plt.show()

# 2,将上述过程对象化:
history_theta = []

def gradient_descent(initial_theta, eta, epsilon=1e-8):
    theta = initial_theta
    history_theta.append(theta)
    
    while True:
        gradient = dJ(theta)
        last_theta = theta
        theta = theta - eta * gradient
        history_theta.append(theta)
        if abs(J(last_theta) - J(theta)) < epsilon:
            break

def print_history():
    plt.plot(x, J(x))
    plt.plot(np.array(history_theta), J(np.array(history_theta)), color='r', marker='+')
    plt.show()

# 3,测试不同的学习率对结果的影响:
history_theta = []
eta = 0.01
gradient_descent(0, eta)
print_history()

history_theta = []
eta = 1.1
gradient_descent(0, eta)
print_history()


# 4,增加最大迭代次数的限制,再次对象化:
history_theta = []

def gradient_descent(initial_theta, eta, n_iters = 1e4, epsilon=1e-8):
    theta = initial_theta
    history_theta.append(theta)
    i_iter = 0
    while i_iter < n_iters:
        gradient = dJ(theta)
        last_theta = theta
        theta = theta - eta * gradient
        history_theta.append(theta)
        if abs(J(last_theta) - J(theta)) < epsilon:
            break
        i_iter += 1
    return

def print_history():
    plt.plot(x, J(x))
    plt.plot(np.array(history_theta), J(np.array(history_theta)), color='r', marker='+')
    plt.show()

# 5,再次设定eta=1.1的情况,比较与上面的区别:
history_theta = []
eta = 1.1
gradient_descent(0, eta, n_iters=10)
print_history()

6.2,剃度验证:

1,定义一个梯度检验函数;2,验证。

# 二、梯度验证:
import numpy as np
import random

# 1,定义一个梯度检验函数:
def grad_check_naive(f, theta, h):
    """
    梯度检查器
    :param f: 输入theta,可返回(原损失函数值和对应梯度值构成的元组)
    :param theta: 入参(n维向量)
    :param h: 极限中所取的一个很小的值
    :return:
    """
    f_theta, grad = f(theta)
    it = np.nditer(theta, flags=['multi_index'], op_flags=['readwrite'])
    while not it.finished:
        index = it.multi_index
        theta_i = theta[index]
        f_res1 = f(theta_i + h)[0]
        f_res2 = f(theta_i - h)[0]
        res = (f_res1 - f_res2) / (2 * h)

        reldiff = abs(res - grad[index])
        if reldiff > h:
            print("校验失败...")
            print("首次校验失败index为:", index)
            print("实际求出的梯度为:%f,校验求出的梯度为:%f" % (grad[index], res))
            return

        it.iternext()

    print("校验通过...")

def sanity_check():
    """
    Some basic sanity checks.
    """
    quad = lambda x: (np.sum(x ** 2), x * 2)

    print("Running sanity checks...")
    grad_check_naive(quad, np.array(123.456), 1e-4)  # scalar test
    grad_check_naive(quad, np.random.randn(3, ), 1e-4)  # 1-D test
    grad_check_naive(quad, np.random.randn(4, 5), 1e-4)  # 2-D test
    print("")


def my_sanity_checks():
    def sigmoid(x):
        return 1. / (1 + np.exp(-x))

    def sigmoid_grad(x):
        return sigmoid(x) * (1 - sigmoid(x))

    quad = lambda x: (sigmoid(x), sigmoid_grad(x))
    print("Running my sanity checks...")
    grad_check_naive(quad, np.random.randn(1, 10), 1e-4)  # scalar test
    print("my check is pass ...")

# 2,验证:
sanity_check()
my_sanity_checks()

6.3,SGD:

对比梯度下降与随即梯度下降用时差异:1,梯度下降法;2,随机梯度下降。

# 三、SGD: 比较梯度下降与随即梯度下降用时
import numpy as np
import matplotlib.pyplot as plt

m = 100000

x = np.random.normal(size=m)
X = x.reshape(-1, 1)
y = 4. * x + 3 + np.random.normal(0, 3, size=m)

plt.scatter(x, y)
plt.show()


# 1,梯度下降法:
def J(theta, X_b, y):
    try:
        return np.sum((y - X_b.dot(theta)) ** 2) / len(y)
    except:
        return float('inf')
    
def dJ(theta, X_b, y):
    res = np.empty(len(theta))
    res[0] = np.sum(X_b.dot(theta) - y)
    for i in range(1, len(theta)):
        res[i] = (X_b.dot(theta) - y).dot(X_b[:,i])
    
    return res * 2 / len(X_b)

def gradient_descent(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):

    theta = initial_theta
    cur_iter = 0

    while cur_iter < n_iters:
        gradient = dJ(theta, X_b, y)
        last_theta = theta
        theta = theta - eta * gradient
        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):
            break

        cur_iter += 1

    return theta

X_b = np.hstack([np.ones((len(X), 1)), X])
initial_theta = np.zeros(X_b.shape[1])
eta = 0.01
%%time
theta = gradient_descent(X_b, y, initial_theta, eta)


# 2,随机梯度下降法:
def dJ_sgd(theta, X_b_i, y_i):
    return 2 * X_b_i.T.dot(X_b_i.dot(theta) - y_i)

def sgd(X_b, y, initial_theta, n_iters):
    # 此处是为了让学习率越来越小,避免直接跳过最优解
    # 这是由于SGD本身的特性决定的
    # t0和t1是两个超参数,可自行调节
    t0, t1 = 5, 50
    def learning_rate(t):
        return t0 / (t + t1)
    
    theta = initial_theta
    for cur_iter in range(n_iters):
        # 随机取一个数据
        rand_i = np.random.randint(len(X_b))
        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])
        # 我们选用的是当前步数的倒数作为学习率,这样就实现了学习率越来越小
        # 但是为了防止一开始学习率过大,我们分子和分母各增加参数进行调节
        theta = theta - learning_rate(cur_iter) * gradient
    return theta

%%time
X_b = np.hstack([np.ones((len(X), 1)), X])
initial_theta = np.zeros(X_b.shape[1])
theta = sgd(X_b, y, initial_theta, n_iters=m//3)
print(theta)

6.4,梯度下降法优化线性回归模型:

1, 定义自己的线性回归模型;2,对比sklearn中的线性回归。

# 四、用梯度下降法,解决一个线性回归的优化问题:
import numpy as np
import matplotlib.pyplot as plt

# 设定一个随机种子,保证我们每次得到的结果一致
np.random.seed(666)
x = 2. * np.random.random(size=100)
y = x * 3. + 4. + np.random.normal(size=100)

plt.scatter(x, y)
plt.show()

# 1, 定义自己的线性回归模型:
# 定义线性回归的损失函数:
def J(theta, X_b, y):
    try:
        return np.sum((y - X_b.dot(theta)) ** 2) / len(X_b)
    except:
        return float('inf')

def dJ(theta, X_b, y):
    res = np.empty(len(theta))
    res[0] = np.sum(X_b.dot(theta) - y)
    for i in range(1, len(theta)):
        res[i] = (X_b.dot(theta) - y).dot(X_b[:,i])
    
    return res * 2 / len(X_b)

def gradient_descent(X_b, y, initial_theta, eta, n_iters = 1e4, epsilon=1e-8):
    
    theta = initial_theta
    cur_iter = 0

    while cur_iter < n_iters:
        gradient = dJ(theta, X_b, y)
        last_theta = theta
        theta = theta - eta * gradient
        if(abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):
            break
            
        cur_iter += 1

    return theta

X_b = np.hstack([np.ones((len(x), 1)), x.reshape(-1,1)])
initial_theta = np.zeros(X_b.shape[1])
eta = 0.01
theta = gradient_descent(X_b, y, initial_theta, eta)

# 2,对比sklearn中的线性回归:
from sklearn.linear_model import LinearRegression
lr = LinearRegression()
lr.fit(X_b, y)
print(lr.coef_, lr.intercept_)

Reference:

《百面机器学习》

https://www.jianshu.com/p/6bd07708e608

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-04-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 MiningAlgorithms 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档