5 ms·

> Automatic differentiation This is extremely cool. The documentation seems to be a WIP on this, can anyone comment on what kind of cost functions are supporte

by ot 15y ago

> Automatic differentiation This is extremely cool. The documentation seems to be a WIP on this, can anyone comment on what kind of cost functions are supported by automatic differentiation? EDIT: it would be also interesting to see how this compares to Theano [1], which also does symbolic differentiation and can JIT to native code and GPU. It is a largely more generic framework, but I'm not sure how well it can handle large sparse problems. [1] http://deeplearning.net/software/theano/ http://deeplearning.net/software/theano/

sandwichmaker 15y ago
You can define define arbitrary functions. You are only limited by the operator overloads defined in jet.h. Let us know if you think something is missing.
- ot 15y ago
  I guess you mean arbitrary expressions, just using arithmetic operations and the overloaded functions (I see that abs, log, sin, cos, ... are supported). What happens if I try to use an if-then or a for loop depending on one of the variables?
  - sandwichmaker 15y ago
    We have conditionals overloaded which allow you to compare with other jets, and doubles, which boil down to a comparison with the "value" part of the jet. So conditionals are not a problem. Loops I would stay away from, since they would destroy the inlining. But if you have an example of a dynamic loop, we would like to hear about it.
  - mierle 15y ago
    It's not just expressions; it's any computation you normally would do with doubles. Take a look at the simple bundle adjustment example: http://code.google.com/p/ceres-solver/source/browse/examples/simple_bundle_adjuster.cc http://code.google.com/p/ceres-solver/source/browse/examples... In particular, search for "SnavelyReprojectionError". In this case there are no loops or if statements, but they work fine too. The only issue with branches is that you can make the cost function discontiguous, which can cause issues. The way this works is that you write your cost functions templated on T. For pure-cost evaluation, this is a double. For cost and jacobian, T is replaced with the "Jet" object, found in jet.h. However, you never see this; Ceres does the substitution for you. There are some caveats; for example, sqrt(0) doesn't work on autodiff objects since the derivative is undefined. You have to use a taylor approximation or similar if the argument to sqrt is exactly zero. If you want to see some more complicated code that runs with autodiff, check out the included rotation.h header. We use that internally for 3D reconstruction type cost functions: http://code.google.com/p/ceres-solver/source/browse/include/ceres/rotation.h http://code.google.com/p/ceres-solver/source/browse/include/...
ArbitraryLimits 15y ago
It means automatic numerical differentiation, not symbolic.
- mierle 15y ago
  No, this is not true. Autodiff != numeric diff. While we do support numeric differentiation, we don't suggest you use it. What we have is automatic differentiation, which is a technique to take exact derivatives without resorting to symbolic differentation. Check out he jet.h file which is the core implementation of this: http://code.google.com/p/ceres-solver/source/browse/include/ceres/jet.h http://code.google.com/p/ceres-solver/source/browse/include/... The header comment has a nice description of autodiff. In summary, Ceres supports three ways to compute derivatives: (1) Automatic differentiation (easiest, fastest, most accurate) (2) Numeric differentiation (easy, but worse convergence and hazardous) (3) User-supplied jacobian (use a pen and paper then implement the jacobian for your residual manually)
  - mierle 15y ago
    I forgot an important technique that is somewhere between numeric differentiation and automatic differentiation: (4) Complex-step differentiation http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.8002 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.... The technique is clever: they add an finite difference along the imaginary axis, and this turns out to give a more accurate derivative than normal forward differences. We don't support this in Ceres and suggest autodiff instead.
  - xxbondsxx 15y ago
    Interesting; this is the first I've heard of automatic differentiation and it's quite elegant and exact. Do you know why it's not covered more in academia?
    - mierle 15y ago
      I've wondered the same myself. It's rather popular in industry. I hadn't head of it until coming to Google. Fun fact: backpropagation for neural networks, which is really just a fancy word for computing the derivatives of the cost, is equivalent to reverse mode autodiff.
sandwichmaker 15y ago
From a very brief look Theano is an expression evaluator. It optimizes expressions, it does not solve numerical optimization problems. I think it can be used as a backend in Ceres to push computations to the GPU, but as it stands it is a different category of software than Ceres.

by ot 15y ago

sandwichmaker 15y ago

You can define define arbitrary functions. You are only limited by the operator overloads defined in jet.h. Let us know if you think something is missing.

ot 15y ago
I guess you mean arbitrary expressions, just using arithmetic operations and the overloaded functions (I see that abs, log, sin, cos, ... are supported). What happens if I try to use an if-then or a for loop depending on one of the variables?
- sandwichmaker 15y ago
  We have conditionals overloaded which allow you to compare with other jets, and doubles, which boil down to a comparison with the "value" part of the jet. So conditionals are not a problem. Loops I would stay away from, since they would destroy the inlining. But if you have an example of a dynamic loop, we would like to hear about it.
- mierle 15y ago
  It's not just expressions; it's any computation you normally would do with doubles. Take a look at the simple bundle adjustment example: http://code.google.com/p/ceres-solver/source/browse/examples/simple_bundle_adjuster.cc http://code.google.com/p/ceres-solver/source/browse/examples... In particular, search for "SnavelyReprojectionError". In this case there are no loops or if statements, but they work fine too. The only issue with branches is that you can make the cost function discontiguous, which can cause issues. The way this works is that you write your cost functions templated on T. For pure-cost evaluation, this is a double. For cost and jacobian, T is replaced with the "Jet" object, found in jet.h. However, you never see this; Ceres does the substitution for you. There are some caveats; for example, sqrt(0) doesn't work on autodiff objects since the derivative is undefined. You have to use a taylor approximation or similar if the argument to sqrt is exactly zero. If you want to see some more complicated code that runs with autodiff, check out the included rotation.h header. We use that internally for 3D reconstruction type cost functions: http://code.google.com/p/ceres-solver/source/browse/include/ceres/rotation.h http://code.google.com/p/ceres-solver/source/browse/include/...

ArbitraryLimits 15y ago

It means automatic numerical differentiation, not symbolic.

mierle 15y ago
No, this is not true. Autodiff != numeric diff. While we do support numeric differentiation, we don't suggest you use it. What we have is automatic differentiation, which is a technique to take exact derivatives without resorting to symbolic differentation. Check out he jet.h file which is the core implementation of this: http://code.google.com/p/ceres-solver/source/browse/include/ceres/jet.h http://code.google.com/p/ceres-solver/source/browse/include/... The header comment has a nice description of autodiff. In summary, Ceres supports three ways to compute derivatives: (1) Automatic differentiation (easiest, fastest, most accurate) (2) Numeric differentiation (easy, but worse convergence and hazardous) (3) User-supplied jacobian (use a pen and paper then implement the jacobian for your residual manually)
- mierle 15y ago
  I forgot an important technique that is somewhere between numeric differentiation and automatic differentiation: (4) Complex-step differentiation http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.8002 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.... The technique is clever: they add an finite difference along the imaginary axis, and this turns out to give a more accurate derivative than normal forward differences. We don't support this in Ceres and suggest autodiff instead.
- xxbondsxx 15y ago
  Interesting; this is the first I've heard of automatic differentiation and it's quite elegant and exact. Do you know why it's not covered more in academia?
  - mierle 15y ago
    I've wondered the same myself. It's rather popular in industry. I hadn't head of it until coming to Google. Fun fact: backpropagation for neural networks, which is really just a fancy word for computing the derivatives of the cost, is equivalent to reverse mode autodiff.

sandwichmaker 15y ago

From a very brief look Theano is an expression evaluator. It optimizes expressions, it does not solve numerical optimization problems. I think it can be used as a backend in Ceres to push computations to the GPU, but as it stands it is a different category of software than Ceres.