c++ - 试图理解 adadelta 算法

Question

我正在尝试将 adadelta 实现到我的简单前馈神经网络 但我认为我在理解这篇文章时遇到了一些麻烦。 http://arxiv.org/pdf/1212.5701v1.pdf
这是一篇解释/介绍 adadelta 算法的小文章。 只有 1 个半页专注于公式。

从部分开始:

Algorithm 1 Computing ADADELTA update at time t

---

问题 1 部分:'3:计算梯度:gt'

这里我究竟如何计算梯度？ 我的方法是否正确:

/* calculating gradient value for neuron what is inside the hidden layer
gradient = sum of ( outcoming connection target's gradient * outcoming connection's weight ) * derivative function */
double CalculatHiddenGradient() {
    double sum = 0.0;
    for (int i = 0; i < OutcomingConnections.size(); i++) {
        sum += OutcomingConnections[i]->weight * OutcomingConnections[i]->target->gradient;
    }
    return (1.0 - output * output) * sum; // tanh's derivative function
}

// calculating gradient value for output neurons where we know the desired output value
double CalculatGradient(double TargetOutput) {
    return (TargetOutput - output) * (1.0 - output * output);
}

---

问题 2 部分:'5:计算更新:Δxt'

公式(14) 说如下:

∆xt = -( RMS[∆x]t−1) / RMS[g]t) * gt;

是RMS[Δx]t−1计算如下:

RMS[∆x]t−1 = sqrt( E[∆x²]t-1 + e )

从公式(9)中取体？

---

根据我目前的理解，我能够写出这段代码:

class AdaDelta {
private:
    vector<double> Eg; // E[g²]
    vector<double> Ex; // E[∆x²]
    vector<double> g; // gradient
    int windowsize;
    double p; // Decay rate ρ
    double e; // Constant e, epsilon?

public:
    AdaDelta(int WindowSize = 32, double DecayRate = 0.95, double ConstantE = 0.001) { // initalizing variables
        Eg.reserve(WindowSize + 1);
        Ex.reserve(WindowSize + 1);

        Eg.push_back(0.0); // E[g²]t
        Ex.push_back(0.0); // E[∆x²]t
        g.push_back(0.0); // (gradient)t

        windowsize = WindowSize; // common value:?

        p = DecayRate; // common value:0.95
        e = ConstantE; // common value:0.001
    }

    // Does it return weight update value?
    double CalculateUpdated(double gradient) {
        double dx; // ∆xt
        int t;

        // for t = 1 : T do %% Loop over # of updates
        for (t = 1; t < Eg.size(); t++) {

            // Accumulate Gradient
            Eg[t] = (p * Eg[t - 1] + (1.0 - p) * (g[t] * g[t]));

            // Compute Update
            dx = -(sqrt(Ex[t - 1] + e) / sqrt(Eg[t] + e)) * g[t];

            // Accumulate Updates
            Ex[t] = Ex[t - 1] + (1.0 - p) * (dx * dx);
        }

        /* calculate new update
        =================================== */
        t = g.size();
        g.push_back(gradient);

        // Accumulate Gradient
        Eg.push_back((p * Eg[t - 1] + (1.0 - p) * (g[t] * g[t])));

        // Compute Update
        dx = -(sqrt(Ex[t - 1] + e) / sqrt(Eg[t] + e)) * g[t];

        // Accumulate Updates
        Ex.push_back(Ex[t - 1] + (1.0 - p) * (dx * dx));

        // Deleting adadelta update when window has grown bigger than we allow
        if (g.size() >= windowsize) {
            Eg[1] = 0.0;
            Ex[1] = 0.0;
            Eg.erase(Eg.begin());
            Ex.erase(Ex.begin());
            g.erase(g.begin());

        }
        return dx;
    }
};

---

问题三
在反向传播中，更新权重是这样的

target's gradient * source's output * learning rate

但是在 adadelta 算法中我没有看到那个 Action 。 我应该在调用之前将源的输出与目标的梯度混合吗 CalculateUpdated() 函数还是我应该将输出与返回值混合以获得新的权重值？

---

问题四
一路让我困惑的一部分

3.2. Idea 2: Correct Units with Hessian Approximation

我不太明白我们在这里更新了哪些公式部分或发生了什么变化。 我们在哪里应用下面的公式？

公式(13) ∆x = (∆x/∂f)/∂x;

---

问题 5
式(13)中的Δx、∂f、∂x分别代表什么？

---

谢谢!

Answer 1

关于 AdaDelta，您需要了解的是在线机器学习的一般背景。 在线机器学习是您一次获取一个数据的地方(因此必须在数据传入时更新模型的参数)，而不是批量机器学习，您可以在其中生成机器学习模型，同时访问整个数据集。

基本上，您有一组数据点以及您试图在表单中预测的目标

D = {(A_1,b_1), (A_2,b_2), (A_3,b_3), ...}

其中A_k是第k条训练数据，b_k是正确答案。您通常希望您的机器学习模型(例如分类器或回归器，例如神经网络或线性模型)更新其内部参数

x = (x_1, x_2, ..., x_n)

因为它一次读取一个数据点 (A_k,b_k)，即您希望模型在数据进入时“实时”更新 x。这与批处理学习相反，您的模型可以同时访问整个数据集 D。

现在，我们通常有一个“成本”的概念——在线性回归中，我们试图最小化的成本函数是预测目标值与实际值之间的差异的均方根 (RMS)目标值。

回顾一下在线线性回归的定义，你有一个stochastic gradient descent基于更新步骤，其中参数 x 根据模型到目前为止看到的所有数据进行更新:

x_new <- x_old - gradient(RMS[predicted-actual])

像 AdaGrad 和 AdaDelta 这样的更新规则所做的是提供一种“更好”的方式来执行更新——这可能意味着确保参数更快地收敛到它们的最佳值，或者在 AdaDelta 的情况下，这意味着参数 x 以适当大小的步长“更接近”它们的最佳值，步长大小根据过去的表现而变化。

让我们逐一解决您的问题，一次一个问题:

• 问题 1:

更高维度的梯度(即当 x 由数组表示时)定义为

gt = (∂f/∂x_1, ∂f/∂x_2, ..., ∂f/∂x_n) (xt)

其中 f(x1,x2,...,x_n) 是您要最小化的函数；在大多数情况下，它是单个示例中的成本函数作为模型参数 x 的函数。换句话说:取成本函数的导数，然后在当前参数 xt 下对其进行评估。

• 问题 2:

根据我的理解，delta-x的RMS定义为

RMS[\Delta x]_{t-1} = \sqrt{ E[\Delta x^2]_{t-1} + \epsilon },

在哪里

E[\Delta x^2]_t = \rho E[\Delta x^2]_{t-1} + (1-\rho) g^2_T,

初始化为

E[\Delta x^2]_0 = 0.

• 问题 3:

AdaDelta 纯粹是一个更新规则。一般结构是这样的:

(new_weights @ T) := (old_weights @ T-1) - [adaptive_learning_rate] * (gradient @ T)

在哪里

adaptive_learning_rate := -(RMS[Delta-x] @ T-1)/(RMS[gradient] @ T)

因为AdaDelta的目的是让学习率成为一个动态值，而不是一开始就强制我们为它选择一个任意值。

• 问题 4:

“用 Hessian 近似校正单位”背后的想法在某种意义上来自物理直觉；也就是说，如果您为每个变量指定某种单位(长度/米、时间/秒、能量/焦耳等)，那么 Hessian 矩阵就有适当的单位来更正更新项，以便进行量纲分析。

• 问题 5:

Delta-x 是更新后 x 的差异。因此，如果 x_i 是更新前的参数，x_{i+1} 是更新后的参数，则 Delta-x 是 (x_{i+1} - x_i)。

(∂f/∂x) 是您要最小化的函数的导数(通常在 ML 中，f 是成本函数)。