反向求导算法

1970年01月01日人工智能算法

之前将了前向求导实现，现在就来讲一下反向求导实现

反向求导的数学基础是链式法则

即求导的过程是从函数输出层开始，逐层向前求导，直到输入层，这样就可以求出每一层的梯度

对于标量求导，即可以自动求出所有变量的梯度

比如对于函数，利用链式法则求导

$Y=F·G,F=a+b,G=b+1$
$\frac{\partial Y}{\partial a}$
$=\frac{\partial Y}{\partial F}·\frac{\partial F}{\partial a}+\frac{\partial Y}{\partial G}·\frac{\partial G}{\partial a}$
$=G + 0$
$=b + 1$

其语法树如下：

根据语法树求导,同路径下梯度相乘，不同路径梯度相加

$\mathrm{d}a = (b+1) \times 1,\mathrm{d}b=(b+1) \times 1 + (a+b) \times 1$

而不同的节点,比如加减乘除，其梯度的计算十分简单

通过把一个复杂的表达式转换为一颗只包含基本运算的语法二叉树

从上往下进行梯度迭代即可计算出每个变量的梯度

这与前向求导只能计算$\mathrm{d}Y$不同,反向求导可以算出$\frac{\partial Y}{\partial a},\frac{\partial Y}{\partial a}$

相加即可算出 $\mathrm{d}Y$

因此在工程应用时也是反向求导居多

以上就是反向求导的基本原理

现在我们来编写代码如何根据函数表达式构造语法二叉树

#include <iostream>
#include <math.h>
using namespace std;

typedef enum {
    CONST,
    VAR,
    ADD,
    SUB,
    MUL,
    DIV,
    POW,
}Operator;


class Qtype {
public:
    Operator oper=CONST;
    float val;
    float grad = 0;
    Qtype* left = nullptr;
    Qtype* right = nullptr;
    Qtype() {
        oper = CONST;
        val = 0;
    }
    Qtype(Operator oper) {
        this->oper = oper;
    }
    Qtype(float a) {
        val = a;
        oper = CONST;
    }
    Qtype(float a, Operator oper) {
        val = a;
        this->oper = oper;
    }
    Qtype(float a, float grad, Operator oper) {
        val = a;
        this->grad = grad;
        this->oper = oper;
    }
    Qtype& operator+(Qtype& other) { 
        Qtype* res = new Qtype(ADD);
        res->left = this;
        res->right = &other;
        return *res;
    }
    Qtype& operator-(Qtype& other) {
        Qtype* res = new Qtype(SUB);
        res->left = this;
        res->right = &other;
        return *res;
    }
    Qtype& operator*(Qtype& other) {
        Qtype* res = new Qtype(MUL);
        res->left = this;
        res->right = &other;
        return *res;
    }
    Qtype& operator/(Qtype& other) {
        Qtype* res = new Qtype(DIV);
        res->left = this;
        res->right = &other;
        return *res;
    }
    Qtype& operator=(Qtype& other) {
        val = other.val;
        grad = other.grad;
        oper = other.oper;
        left = other.left;
        right = other.right;
        return *this;
    }
    Qtype& operator^(Qtype& other) {
        Qtype* res = new Qtype(POW);
        res->left = this;
        res->right = &other;
        return *res;
    }
    Qtype& operator+=(Qtype& other) {
        Qtype* copy = new Qtype(*this);//将自身拷贝一份
        this->oper = ADD;
        this->left = copy;
        this->right = &other;
        return *this;
    }
    //反向求导
    void Process(float grad) {
        switch (oper) {
        case CONST:
            grad = 0;
            break;//不做任何事情
        case VAR:
            this->grad += grad;//梯度增加
            break;
        case ADD:
            left->Process(grad);
            right->Process(grad);
            break;
        case SUB:
            left->Process(grad);
            right->Process(-grad);
            break;
        case MUL:
            left->Process(right->val * grad);
            right->Process(left->val * grad);
            break;
        case DIV:
            left->Process(1 / right->val * grad);
            right->Process(-left->val / (right->val * right->val) * grad);
            break;
        case POW:
            left->Process(right->val * pow(left->val, right->val - 1) * grad);
            right->Process(val * log(left->val) * grad);
            break;
        default:
            break;
        }
    }
    //前向传播  
    void Forward() {
        switch (oper) {
        case CONST:
            break;
        case VAR:
            grad = 0;
            break;
        case ADD:
            left->Forward();
            right->Forward();
            val = left->val + right->val;
            break;
        case SUB:
            left->Forward();
            right->Forward();
            val = left->val - right->val;
            break;
        case MUL:
            left->Forward();
            right->Forward();
            val = left->val * right->val;
            break;
        case DIV:
            left->Forward();
            right->Forward();
            val = left->val / right->val;
            break;
        case POW:
            left->Forward();
            right->Forward();
            val = pow(left->val, right->val);
            break;
        default:
            break;
        }
    }

    void Backward() {
        Process(1);
    }
    //打印语法树
    void PrintTree() {
        switch (oper) {
        case CONST:
            cout << val;
            break;
        case VAR:
            cout << "x";
            break;
        case ADD:
            cout << "(";
            left->PrintTree();
            cout << "+";
            right->PrintTree();
            cout << ")";
            break;
        case SUB:
            cout << "(";
            left->PrintTree();
            cout << "-";
            right->PrintTree();
            cout << ")";
            break;
        case MUL:
            cout << "(";
            left->PrintTree();
            cout << "*";
            right->PrintTree();
            cout << ")";
            break;
        case DIV:
            cout << "(";
            left->PrintTree();
            cout << "/";
            right->PrintTree();
            cout << ")";
            break;
        case POW:
            cout << "(";
            left->PrintTree();
            cout << "^";
            right->PrintTree();
            cout << ")";
            break;
        default:
            break;
        }
    }
};

代码的复杂度与前向求导实际上差不多
同样是通过重载运算符来实现自动构造语法二叉树

测试代码如下

int main() {
    Qtype a(0, VAR), b(0, VAR),k(1);
    Qtype Y = (a + b) * (b + k);
    Y.Forward();//先前向传播一次计算各个节点的值，再反向传播计算梯度
    Y.Backward();
    Y.PrintTree();//打印语法树
    cout << endl;
    cout << a.grad << endl;//打印a的梯度
    cout << b.grad << endl;//打印b的梯度
}

输出如下

1
2
3

((x+x)*(x+1))
1
1