对于有限差分，梯度下降是否较慢？

Question

在梯度下降中，我们更新了每个参数\theta_i，使函数f(\theta_1,\theta_2,\dots,\theta_N)通过执行\theta_1 \leftarrow \theta_1 - \alpha \frac{\partial f}{\partial \theta_1}(\theta_1,\theta_2,\dots,\theta_N)最小化。

\theta_2 \leftarrow \theta_2 - \alpha \frac{\partial f}{\partial \theta_2}(\theta_1,\theta_2,\dots,\theta_N)

\vdots

\theta_N \leftarrow \theta_N - \alpha \frac{\partial f}{\partial \theta_N}(\theta_1,\theta_2,\dots,\theta_N).

如果我们有N参数，那么它将涉及到N评估。

如果可能的话，很明显，我们想使用梯度的分析形式。

当然，我们可以用有限差分来近似，

\theta_1 \leftarrow \theta_1 - \alpha \frac{f(\theta_1+\varepsilon,\theta_2,\dots,\theta_N)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}

\theta_2 \leftarrow \theta_2 - \alpha \frac{f(\theta_1,\theta_2+\varepsilon,\dots,\theta_N)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}

\vdots

\theta_N \leftarrow \theta_N - \alpha \frac{f(\theta_1,\theta_2,\dots,\theta_N+\varepsilon)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}

这涉及到N+1评估，如果N很大，可以忽略不计，就像深度神经网络一样。

显然，解析梯度更准确，避免了由于\varepsilon过大或过小而引起的数值问题。

我的问题是:我听说人们声称，使用梯度下降与分析导数比近似导数更快。这是真的吗？在我看来，这只会避免额外的评估。

编辑:实际示例：

假设我们有

y=\sigma(ax)

z=by，其中a和b是我们要优化的参数。

梯度

使用梯度，我们将有\nabla=\left(\frac{\partial z}{\partial a},\frac{\partial z}{\partial b} \right) = \left(bx\sigma(ax)(1-\sigma(ax)), \sigma(ax)\right)

(我希望我在那里没有犯错误。\frac{\partial z}{\partial a}=\frac{\partial z}{\partial y}\frac{\partial y}{\partial a}=bx\sigma'(ax)=bx\sigma(ax)(1-a\sigma(ax))。)

对于每一个反向传播，我们需要对a和b：\nabla(a,b)进行两个评估，这样我们就可以执行.

以下是所需的计算：

a \leftarrow a-\alpha bx\sigma(ax)(1-\sigma(ax))

b \leftarrow b-\alpha \sigma(ax)

有限差分

我们有不同的\Delta=\left((z(a+\varepsilon,b)-z(a,b))/\varepsilon, (z(a,b+\varepsilon)-z(a,b))/\varepsilon \right)

z(a,b)=\color{blue}{b\sigma(ax)}

z(a+\varepsilon,b) = \color{blue}{b\sigma(ax)} + b\sigma(\epsilon x)

z(a,b+\varepsilon) = \color{blue}{b\sigma(ax)} + \varepsilon\sigma(ax)

以下是所需的计算：

a \leftarrow a-\alpha b\sigma(\varepsilon x)/\varepsilon

b \leftarrow b-\alpha \sigma(ax)

蓝色的术语在图表中分散，因为它们是被自己减去的。

Answer 1

(对评论的答复)

考虑使用标签+1/-1的logistic回归，其中函数是f(x) = \sum log(1 + \exp(-y * (x \theta)))。采用有限差分需要计算每个变量的\sum log(1 + \exp(-y * (x (\theta + \epsilon_n)))) (其中\epsilon_n是一个变量的小值)(在每个计算中，还需要插入所有其他变量的当前值)。分析解决方案是\sum residual \theta -您只需要插入当前值两次。您可以保留一个\theta x和来保存计算(在差分方法中还有更多的计算)，但是随着函数变得更加非线性，在变量之间预计算的可能性就更小了--例如，如果您有3个隐藏单元，更改第一个单元将不允许您为其他变量重复使用计算。

在大-哦符号方面，如果你看的是评估的数量，并且你认为梯度值是O(n) (记住向量化会产生不同)，我想你不会看到太大的差别，但是如果你看看其他方面，你会发现解析解需要更少的计算。

此外，如果不使用精确的梯度，像L-BFGS这样的优化技术将无法工作。

Answer 2

如果您有许多变量，您将不得不分别计算每个变量的有限差分(意思是:用所有其他变量计算函数)，而通常可以以更快的方式计算所有变量的分析梯度。

Answer 3

OP的问题是:什么更快？反传算法中导数或解析导数的逼近？我将以原始海报(OP)为例说明，在反向传播中，近似的计算复杂度高于解析导数的计算复杂度。

OP示例这里我使用了带有隐藏层的sigmoid激活函数的原始海报(OP)的例子。

假设我们有

t=ax

y=\sigma(t)

z=by，其中a和b是我们要优化的参数。

分析衍生物

\frac{\partial z}{\partial b} = y

\frac{\partial z}{\partial a} =\frac{\partial z}{\partial y}\frac{\partial y}{\partial a} =\frac{\partial z}{\partial y}\frac{\partial y}{\partial \sigma}\frac{\partial \sigma}{\partial t}\frac{\partial t}{\partial a} =b\cdot 1 \cdot \sigma(t) \cdot (1-\sigma(t)) \cdot x

考虑到z=b \cdot \sigma(t)和y=\sigma(t)，我们得到了以下内容：

\frac{\partial z}{\partial a} = z\cdot (1-y)\cdot x

这些是我们的衍生产品：

a：z(1-y)x

b：y

有限差分

z(a,b)=z

z(a,b+\varepsilon) = (b+\varepsilon)\sigma(ax) = b\sigma(ax)+ \varepsilon\sigma(ax) = z + \varepsilon y

z(a+\varepsilon,b) = b\sigma((a+\varepsilon)x) =b\frac{1}{1+e^{-(a+\varepsilon)x}} =b\frac{1}{1+e^{-t-\varepsilon x}}

我们以前计算过e^{-t}。让我们命名u=e^{-t}

z(a+\varepsilon,b) =b\frac{1}{1+ue^{-\varepsilon x}}

在这里，\sigma(a+b)不等于\sigma(a)+\sigma(b)，所以您不能轻松地编写z+...，至少我没有找到一种将z值取出来的方法。

\frac{z(a,b+\varepsilon)-z(a,b)}{\varepsilon} = y，这和OP计算中的导数一样。

\frac{z(a+\varepsilon,b)-z(a,b)}{\varepsilon} = \frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}

这些是我们的导数近似：

a：\frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}

b：y

比较

在这两种情况下，您都需要在点上计算z函数。对于b的计算是相同的。a的导数近似比解析导数要复杂得多。

\frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}对z(1-y)x