Wnma's Blogs
0%

SPSA随机优化算法

发表于 更新于 分类于

SPSA(Simultaneous Perturbation Stochastic Approximation)是一种随机优化算法,可用于神经网络的训练。其基于随机梯度来逼近真实梯度。无法直接得到精确梯度,收敛速度较慢,但节省计算资源。

SPSA算法简介

SPSA是一种随机优化算法,可以用于神经网络模型的训练。它的主要思想是同时随机扰动所有参数,基于损失函数在扰动后的变化来估计梯度。

相比确定性的梯度下降法,SPSA依靠随机性搜索最优解,可以更好地跳出局部最优,具有全局搜索能力。另外,SPSA只需要前向传播就可以更新参数,省去了存储反向传播所需的计算图,计算开销较小。

PyTorch实现SPSA训练神经网络

要在PyTorch中实现SPSA算法训练神经网络,主要分以下几个步骤:

  1. 构建神经网络模型

    可以构建一个多层全连接网络,例如在MNIST数据集上进行图像分类任务:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import torch.nn as nn

    class Net(nn.Module):
        def __init__(self):
            super(Net, self).__init__()
            self.fc1 = nn.Linear(784, 100)
            self.fc2 = nn.Linear(100, 10)

        def forward(self, x):
            x = F.relu(self.fc1(x))
            x = self.fc2(x)
            return F.log_softmax(x, dim=1)

  2. 定义损失函数和优化器

    使用交叉熵损失函数和SGD优化器:

    1
    2
    criterion = nn.CrossEntropyLoss()
    optimizer = torch.optim.SGD(net.parameters(), lr=0.1)

  3. 实现SPSA算法

    根据SPSA的公式,可以实现计算随机梯度的函数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def SPSA_step(net, criterion, x, y, a, c, k):
        delta = 2 * (torch.randint(0, 2, net.parameters().__len__()) - 0.5)
        perturbation = c * delta
        loss1 = criterion(net(x + a*perturbation), y)
        loss2 = criterion(net(x - a*perturbation), y)
        gradient = (loss1 - loss2) / (2 * a * perturbation)

        for param, grad in zip(net.parameters(), gradient):
            param.data.add_(k * grad * delta)

        return net

  4. 训练神经网络

    在训练循环中调用SPSA_step函数计算梯度并更新参数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for epoch in range(10):
        running_loss = 0

        for i, data in enumerate(trainloader, 0):
            inputs, labels = data
            

            net = SPSA_step(net, criterion, inputs, labels, 0.01, 0.005, 0.01)
    				optimizer.zero_grad()
            optimizer.step()

        print('[%d] loss: %.3f' % (epoch + 1, running_loss / len(trainloader)))

前向传播与反向传播的比较

使用前向传播计算梯度时,需要使用两点式差分来估计梯度:

1
gradient = (loss1 - loss2) / (2 * a * perturbation)

其中loss1和loss2分别对应参数做微小正负扰动时的损失。这只能得到梯度的近似值,收敛速度较慢。

而反向传播可以通过动态计算图高效地得到每个参数的精确梯度,使得网络可以更快收敛。但需要额外的存储空间保存计算图,计算复杂度也更高。

所以在训练神经网络时,通常选择反向传播来获取精确梯度信息,以保证收敛速度。SPSA更适用于一些计算资源受限但需要求解最优参数的场景。

Q & A

问题1:SPSA算法与随机梯度下降(SGD)的区别是什么?

SPSA和SGD都依赖于随机性来达到优化目的,主要区别在于:

  • SGD每次只随机扰动一个参数,SPSA同时扰动所有参数
  • SPSA使用有限差分法估计梯度,SGD使用反向传播计算精确梯度
  • SPSA可能更能避免局部最优,SGD收敛速度更快

使用前向传播和反向传播的主要不同是在计算梯度的方式上。

使用反向传播时，我们首先通过前向传播计算网络的输出，然后将输出与实际标签计算损失函数，然后通过反向传播计算每个参数对损失函数的梯度。这使得我们能够有效地更新模型参数，并最小化损失函数。

而如果只使用前向传播进行神经网络的更新，则无法直接计算每个参数对损失函数的梯度。相反，我们可以考虑使用“两点式差分”来近似计算梯度。具体地，我们采用以下公式：

\[\nabla f(x) \approx \frac{f(x+\Delta x) - f(x-\Delta x)}{2\Delta x}\]

其中，\(\Delta x\)代表一个微小的扰动，\(x\)是输入数据，\(f(x)\)为损失函数。我们根据这个公式对每个参数进行微小的扰动，然后计算对应的损失函数。在此基础上，我们可以使用公式计算梯度并更新参数。

使用前向传播进行更新相比使用反向传播的优势在于，它减少了内存占用和计算时间，并且不需要存储计算图。但是，由于它只是使用一阶近似来计算梯度，因此可能会导致更新不如反向传播精确。

问题2:SPSA算法适用于哪些场景?

SPSA算法适用于以下场景:

  • 目标函数无法明确表达,无法求导
  • 参数空间高维,难以精确计算梯度
  • 需要避免陷入局部最优
  • 计算资源受限,无法存储大规模计算图

问题3:SPSA算法的两大超参数a和c表示什么?

  • a是步长(perturbation size),表示参数扰动大小
  • c是抖动幅度(perturbation distribution),控制扰动值波动范围

a可类比SGD中的学习率,c越大随机性越强。两者需要均衡调节,既保证足够探索又不失稳定性。

问题4:SPSA算法如何保证收敛性?

SPSA可以通过以下手段保证收敛:

  1. 同时扰动参数：在每个迭代中，SPSA使用两个随机向量对参数进行扰动，这样可以避免局部极小值点，并且使得算法更容易跳出局部最小值。
  2. 适应性调整步长：SPSA具有自适应学习率机制，即根据当前估计的梯度大小和先前的步长大小来更新步长。这确保了算法收敛时步长逐渐减小。
  3. 随机性：SPSA在每个迭代中都使用随机扰动来估计梯度，这有助于避免陷入局部最小值并提高全局搜索的能力。
  4. 理论保证：SPSA有理论上保证的收敛性，这意味着只要满足一些条件（例如随机扰动独立同分布），就可以保证算法最终会收敛到正确的解。

问题5:相较于反向传播。为什么SPSA没有被广泛应用？

  1. 相对较少的理论支持：与反向传播等算法相比，SPSA算法的理论分析较少，因此我们不能完全了解其性能或收敛速度。
  2. 需要大量的迭代次数：SPSA算法需要使用更多的迭代次数才能获得较好的结果，这可能会使其在实际使用中变得过于耗时。
  3. 参数设置困难：SPSA算法本身有很多参数需要调节，例如步长、抖动幅度等，如果这些参数设置不当，则可能导致算法无法收敛或收敛非常缓慢。