Implementing a simple autodiff demo with Cpp
Implemented a simple autodiff demo with Cpp, the idea comes from Andrej karpathy’s micrograd.
I feel the uniqueness of Andrej’s implementation is that in his data structure design, the owner of the computation graph are the nodes that have been constructed.
Implementing in higher level language like Python would have let me ignore the issue, while in Cpp, I have to consider the lifetime of the graph.
To do this, we need a Node structure representing the real data, and use a wrapper Value to refer Node and keep it alive by using shared_ptr (which implements reference count).
There should be another way to viewing this, for example, in MLIR, computation graphs are represented in Regions, Blocks and Operations.
That is, instead of using Node as the owner, we can have a outter container such as a Graph to own Operations, and each Operation owns operands, result and operator.
#include <cassert>
#include <cmath>
#include <iostream>
#include <memory>
enum class BinaryOperator { ADD, MUL, LEAF };
struct Node {
double_t val;
BinaryOperator op;
std::shared_ptr<Node> lhs;
std::shared_ptr<Node> rhs;
Node(double_t val) : val(val), op(BinaryOperator::LEAF) {};
Node(double_t val, BinaryOperator op, std::shared_ptr<Node> lhs,
std::shared_ptr<Node> rhs)
: val(val), op(op), lhs(lhs), rhs(rhs) {};
};
struct Value {
std::shared_ptr<Node> node;
explicit Value(double_t val) { node = std::make_shared<Node>(val); }
explicit Value(std::shared_ptr<Node> node) : node(node) {};
static Value create_value(double_t val, BinaryOperator op, const Value &lhs,
const Value &rhs) {
auto new_node = std::make_shared<Node>(val, op, lhs.node, rhs.node);
return Value(new_node);
};
double_t get_val() const { return this->node->val; }
BinaryOperator get_op() const { return this->node->op; }
double_t partial_derivate(const Value &a) const {
if (this->node == a.node) {
return 1.0;
}
double_t d = 0;
if (node->op != BinaryOperator::LEAF) {
Value o1(node->lhs);
Value o2(node->rhs);
if (get_op() == BinaryOperator::ADD) {
d = o1.partial_derivate(a) + o2.partial_derivate(a);
} else if (get_op() == BinaryOperator::MUL) {
d = o1.get_val() * o2.partial_derivate(a) +
o2.get_val() * o1.partial_derivate(a);
}
}
return d;
}
};
Value operator+(const Value &lhs, const Value &rhs) {
return Value::create_value(lhs.get_val() + rhs.get_val(), BinaryOperator::ADD,
lhs, rhs);
}
Value operator+(double_t lhs, const Value &rhs) {
Value lhs_value(lhs);
return operator+(lhs_value, rhs);
}
Value operator+(const Value &lhs, double_t rhs) {
Value rhs_value(rhs);
return operator+(lhs, rhs_value);
}
Value operator*(const Value &lhs, const Value &rhs) {
return Value::create_value(lhs.get_val() * rhs.get_val(), BinaryOperator::MUL,
lhs, rhs);
}
Value operator*(double_t lhs, const Value &rhs) {
Value lhs_value(lhs);
return operator*(lhs_value, rhs);
}
Value operator*(const Value &lhs, double_t rhs) {
Value rhs_value(rhs);
return operator*(lhs, rhs_value);
}
Value create_example(Value a, Value b) {
auto c = a + b;
auto d = a * b;
auto e = a * c;
auto f = c + d;
auto g = f + e;
return g;
}
// g = a + b + a * b + a * (a + b) = a + b + ab + aa + ab = aa + 2ba + a + b
// dg/da = 2a + 2b + 1
// dg/db = 2a + 1
int main() {
Value a(2.0);
Value b(3.0);
auto g = create_example(a, b);
Value delta(0.01);
std::cout << "gradient of a by numerical: "
<< (create_example(a + delta, b).get_val() - g.get_val()) /
delta.get_val()
<< '\n';
std::cout << "gradient of a by autodiff: " << g.partial_derivate(a) << '\n';
std::cout << "gradient of b by numerical: "
<< (create_example(a, b + delta).get_val() - g.get_val()) /
delta.get_val()
<< '\n';
std::cout << "gradient of b by autodiff: " << g.partial_derivate(b) << '\n';
}
If you have any feedback to this article, feel free to comment here or send an email to me