C++ 反向自动微分图

Question

我正在尝试用 C++ 制作 reverse mode automatic differentiation。

我想出的想法是，对一个或两个其他变量进行操作后产生的每个变量将把梯度保存在一个向量中。

这是代码：

class Var {
    private:
        double value;
        char character;
        std::vector<std::pair<double, const Var*> > children;

    public:
        Var(const double& _value=0, const char& _character='_') : value(_value), character(_character) {};
        void set_character(const char& character){ this->character = character; }

        // computes the derivative of the current object with respect to 'var'
        double gradient(Var* var) const{
            if(this==var){
                return 1.0;
            }

            double sum=0.0;
            for(auto& pair : children){
                // std::cout << "(" << this->character << " -> " <<  pair.second->character << ", " << this << " -> " << pair.second << ", weight=" << pair.first << ")" << std::endl;
                sum += pair.first*pair.second->gradient(var);
            }
            return sum;
        }

        friend Var operator+(const Var& l, const Var& r){
            Var result(l.value+r.value);
            result.children.push_back(std::make_pair(1.0, &l));
            result.children.push_back(std::make_pair(1.0, &r));
            return result;
        }

        friend Var operator*(const Var& l, const Var& r){
            Var result(l.value*r.value);
            result.children.push_back(std::make_pair(r.value, &l));
            result.children.push_back(std::make_pair(l.value, &r));
            return result;
        }

        friend std::ostream& operator<<(std::ostream& os, const Var& var){
            os << var.value;
            return os;
        }
};

我试过运行这样的代码 :

int main(int argc, char const *argv[]) {
    Var x(5,'x'), y(6,'y'), z(7,'z');

    Var k = z + x*y;
    k.set_character('k');

    std::cout << "k = " << k << std::endl;
    std::cout << "∂k/∂x = " << k.gradient(&x) << std::endl;
    std::cout << "∂k/∂y = " << k.gradient(&y) << std::endl;
    std::cout << "∂k/∂z = " << k.gradient(&z) << std::endl;

    return 0;
}

需要构建的计算图如下：

       x(5)   y(6)              z(7)
         \     /                 /
 ∂w/∂x=y  \   /  ∂w/∂y=x        /
           \ /                 /
          w=x*y               /
             \               /  ∂k/∂z=1
              \             /
      ∂k/∂w=1  \           /
                \_________/
                     |
                   k=w+z

然后，如果我想计算 ∂k/∂x，我必须乘以边缘之后的梯度，然后对每条边缘的结果求和。这是由 double gradient(Var* var) const 递归完成的。所以我有 ∂k/∂x = ∂k/∂w * ∂w/∂x + ∂k/∂z * ∂z/∂x.

问题

如果我在这里进行中间计算，例如x*y，就会出错。当 std::cout 取消注释时，输出为：

k = 37
(k -> z, 0x7ffeb3345740 -> 0x7ffeb3345710, weight=1)
(k -> _, 0x7ffeb3345740 -> 0x7ffeb3345770, weight=1)
(_ -> x, 0x7ffeb3345770 -> 0x7ffeb33456b0, weight=0)
(_ -> y, 0x7ffeb3345770 -> 0x7ffeb33456e0, weight=5)
∂k/∂x = 0
(k -> z, 0x7ffeb3345740 -> 0x7ffeb3345710, weight=1)
(k -> _, 0x7ffeb3345740 -> 0x7ffeb3345770, weight=1)
(_ -> x, 0x7ffeb3345770 -> 0x7ffeb33456b0, weight=0)
(_ -> y, 0x7ffeb3345770 -> 0x7ffeb33456e0, weight=5)
∂k/∂y = 5
(k -> z, 0x7ffeb3345740 -> 0x7ffeb3345710, weight=1)
(k -> _, 0x7ffeb3345740 -> 0x7ffeb3345770, weight=1)
(_ -> x, 0x7ffeb3345770 -> 0x7ffeb33456b0, weight=0)
(_ -> y, 0x7ffeb3345770 -> 0x7ffeb33456e0, weight=5)
∂k/∂z = 1

它打印哪个变量连接到哪个变量，然后是它们的地址，以及连接的权重（应该是梯度）。

问题是 weight=0 在 x 和保存 x*y 结果的中间变量之间（我表示为 w 在我的图表中）。我不知道为什么这个是零而不是连接到 y.

的另一个权重

我注意到的另一件事是，如果您像这样切换 operator* 中的行：

result.children.push_back(std::make_pair(1.0, &r));
result.children.push_back(std::make_pair(1.0, &l));

然后是 y 个连接取消了。

在此先感谢您的帮助。

Answer 1

行：

Var k = z + x*y;

调用 operator*，其中 returns 一个 Var 临时的，然后用于 operator+ 的 r 参数，其中一个 pair 存储临时地址。该行完成后，k children 包含一个指针，指向临时曾经所在的位置，但它不再存在。

虽然它不能防止上述错误，但您可以通过避免未命名的临时文件来创建预期的行为...

Var xy = x * y;
xy.set_character('*');
Var k = z + xy;
k.set_character('k');

...您的程序生成：

k = 37
∂k/∂x = 6
∂k/∂y = 5
∂k/∂z = 1

更好的解决方法可能是按值捕获子项。

作为捕获此类错误的一般提示...当您的程序似乎在做一些莫名其妙的事情（and/or 崩溃）时，请尝试运行它在内存错误检测器下，例如 valgrind。对于您的代码，报告以：

开头

==22137== Invalid read of size 8
==22137==    at 0x1090EA: Var::gradient(Var*) const (in /home/median/so/deriv)
==22137==    by 0x109109: Var::gradient(Var*) const (in /home/median/so/deriv)
==22137==    by 0x108E12: main (in /home/median/so/deriv)
==22137==  Address 0x5b82cd0 is 0 bytes inside a block of size 32 free'd
==22137==    at 0x4C3123B: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22137==    by 0x109FC1: __gnu_cxx::new_allocator<std::pair<double, Var const*> >::deallocate(std::pair<double, Var const*>*, unsigned long) (in /home/median/so/deriv)
==22137==    by 0x109CDD: std::allocator_traits<std::allocator<std::pair<double, Var const*> > >::deallocate(std::allocator<std::pair<double, Var const*> >&, std::pair<double, Var const*>*, unsigned long) (in /home/median/so/deriv)
==22137==    by 0x109963: std::_Vector_base<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::_M_deallocate(std::pair<double, Var const*>*, unsigned long) (in /home/median/so/deriv)
==22137==    by 0x1097BC: std::_Vector_base<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::~_Vector_base() (in /home/median/so/deriv)
==22137==    by 0x1095EA: std::vector<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::~vector() (in /home/median/so/deriv)
==22137==    by 0x109161: Var::~Var() (in /home/median/so/deriv)
==22137==    by 0x108D95: main (in /home/median/so/deriv)
==22137==  Block was alloc'd at
==22137==    at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22137==    by 0x10A153: __gnu_cxx::new_allocator<std::pair<double, Var const*> >::allocate(unsigned long, void const*) (in /home/median/so/deriv)
==22137==    by 0x10A060: std::allocator_traits<std::allocator<std::pair<double, Var const*> > >::allocate(std::allocator<std::pair<double, Var const*> >&, unsigned long) (in /home/median/so/deriv)
==22137==    by 0x109F03: std::_Vector_base<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::_M_allocate(unsigned long) (in /home/median/so/deriv)
==22137==    by 0x109A8D: void std::vector<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::_M_realloc_insert<std::pair<double, Var const*> >(__gnu_cxx::__normal_iterator<std::pair<double, Var const*>*, std::vector<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > > >, std::pair<double, Var const*>&&) (in /home/median/so/deriv)
==22137==    by 0x1098CF: void std::vector<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::emplace_back<std::pair<double, Var const*> >(std::pair<double, Var const*>&&) (in /home/median/so/deriv)
==22137==    by 0x10973F: std::vector<std::pair<double, Var const*>, std::allocator<std::pair<double, Var const*> > >::push_back(std::pair<double, Var const*>&&) (in /home/median/so/deriv)
==22137==    by 0x109520: operator*(Var const&, Var const&) (in /home/median/so/deriv)
==22137==    by 0x108D6F: main (in /home/median/so/deriv)

捕获它的另一种方法是在析构函数中添加日志记录，以便您知道日志记录中提到的对象地址何时不再有效。

C++ 反向自动微分图

C++ reverse automatic differentiation with graph

c++

automatic-differentiation

问题