roboptim-commit Mailing List for RobOptim (Page 92)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hello,
I have  pushed a modification in roboptim-core that change how finite
difference gradients are computed.
It breaks the current interface but the update is trivial.

* Idea / implementation

Before, the gradient was computed directly in FiniteDifferenceGradient
class and has been changed several times
to enhance the last algorithm comes from the GNU Scientific Library
and use the five points rules. The advantage is
that it is extremely precise but on the other hand it is costly to compute.
As usually the naive fast algorithm is fast enough, I have changed the
interface so that one can choose what algorithm
will be used.

The implementation idea comes from the well-known Andrei Alexandescu's
policy based design pattern.
See:
- http://en.wikipedia.org/wiki/Policy-based_design
- http://erdani.org/

In practice, it means the gradient computation algorithm is in a
separate class and the finiteDifferenceGradient
class is just a facade templated by the algorithm type.

I.e.:
FiniteDiffrerenceGradient<FiniteDifferenceGradientPolicies::Simple>
simple (/* FIXME */);
FiniteDiffrerenceGradient<FiniteDifferenceGradientPolicies::FivePointsRule>
compex (/* FIXME */);

The first line declare an object that uses a simple gradient
computation, the second a complex one.

The header fwd.hh contains pre-declarations and declare FivePointsRule
as the default policy,
so one can write:
FiniteDifferenceGradient<> myGradient (/* FIXME */);

...and in this case the complex algorithm is used.

Rationale:
1/ this commit does not change program's behavior as the complex
algorithm was the only one available
previously,
2/ a default behavior has to be correct. If one wants to choose speed
over correctness, he has to do it explicitly.

BTW anyone can declare a new gradient computation algorithm by doing
class MyNewGradientComputationAlgorithm
{
 void computeGradient (/* FIXME - argument are the same than other policies */)
 {
// compute gradient here.
 }
};
FiniteDifferenceGradient<MyNewGradientComputationAlgorithm> (/* FIXME */);

* How to update your code to new interface

Just add change FiniteDifferenceGradient into
``FiniteDifferenceGradient<>'' (of course you can precise a policy
if you want).

On Mon, Aug 31, 2009 at 6:55 PM, Thomas
Moulard<tho...@us...> wrote:
> This is an automated email from the git hooks/post-receive script. It was
> generated because a ref change was pushed to the repository containing
> the project "roboptim-core".
>
> The branch, master has been updated
>       via  26ad52ac15f29ca16d282688e26a03b773c09345 (commit)
>      from  4e051e05e1b1b5789c59e39d36bc7bb35f61f6d6 (commit)
>
> Those revisions listed above that are new to this repository have
> not appeared on any other notification email; so we list those
> revisions in full, below.
>
> - Log -----------------------------------------------------------------
> commit 26ad52ac15f29ca16d282688e26a03b773c09345
> Author: Thomas Moulard <tho...@gm...>
> Date:   Mon Aug 31 11:54:54 2009 +0900
>
>    Add policies to finite-difference gradients computation.
>
>        * include/Makefile.am: Distribute new header.
>        * include/roboptim/core/finite-difference-gradient.hh:
>        Add policies and template FiniteDifferenceGradient by them.
>        * include/roboptim/core/finite-difference-gradient.hxx: New.
>        * include/roboptim/core/fwd.hh: Update forward declaration,
>        make FivePointsRule the default policy.
>        * src/finite-difference-gradient.cc: Implement policies,
>        update free functions.
>        * tests/finite-difference-gradient.cc: Use new interface,
>        check both policies.
>
>    Signed-off-by: Thomas Moulard <tho...@gm...>
>
> diff --git a/ChangeLog b/ChangeLog
> index d81d8aa..5dc817b 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,17 @@
> +2009-08-31  Thomas Moulard  <tho...@gm...>
> +
> +       Add policies to finite-difference gradients computation.
> +       * include/Makefile.am: Distribute new header.
> +       * include/roboptim/core/finite-difference-gradient.hh:
> +       Add policies and template FiniteDifferenceGradient by them.
> +       * include/roboptim/core/finite-difference-gradient.hxx: New.
> +       * include/roboptim/core/fwd.hh: Update forward declaration,
> +       make FivePointsRule the default policy.
> +       * src/finite-difference-gradient.cc: Implement policies,
> +       update free functions.
> +       * tests/finite-difference-gradient.cc: Use new interface,
> +       check both policies.
> +
>  2009-08-30  Thomas Moulard  <tho...@gm...>
>
>        Fix error in return type.
> diff --git a/include/Makefile.am b/include/Makefile.am
> index 2c744c6..c78b902 100644
> --- a/include/Makefile.am
> +++ b/include/Makefile.am
> @@ -9,6 +9,7 @@ nobase_include_HEADERS =                                \
>        roboptim/core/function.hh                       \
>        roboptim/core/fwd.hh                            \
>        roboptim/core/finite-difference-gradient.hh     \
> +       roboptim/core/finite-difference-gradient.hxx    \
>        roboptim/core/generic-solver.hh                 \
>        roboptim/core/identity-function.hh              \
>        roboptim/core/indent.hh                         \
> diff --git a/include/roboptim/core/finite-difference-gradient.hh b/include/roboptim/core/finite-difference-gradient.hh
> index d2bd7fa..da3efbc 100644
> --- a/include/roboptim/core/finite-difference-gradient.hh
> +++ b/include/roboptim/core/finite-difference-gradient.hh
> @@ -81,6 +81,29 @@ namespace roboptim
>   /// \return output stream
>   ROBOPTIM_DLLAPI std::ostream& operator<< (std::ostream& o, const BadGradient& f);
>
> +  namespace finiteDifferenceGradientPolicies
> +  {
> +    struct ROBOPTIM_DLLAPI Simple
> +    {
> +      void computeGradient
> +      (const Function& adaptee,
> +       Function::value_type epsilon,
> +       Function::result_t& gradient,
> +       const Function::argument_t& argument,
> +       Function::value_type idFunction) const throw ();
> +    };
> +
> +    struct ROBOPTIM_DLLAPI FivePointsRule
> +    {
> +      void computeGradient
> +      (const Function& adaptee,
> +       Function::value_type epsilon,
> +       Function::result_t& gradient,
> +       const Function::argument_t& argument,
> +       Function::value_type idFunction) const throw ();
> +    };
> +  } // end of namespace policy.
> +
>
>   /// \addtogroup roboptim_function
>   /// @{
> @@ -98,7 +121,10 @@ namespace roboptim
>   /// \f[f'(x)\approx {f(x+\epsilon)-f(x)\over \epsilon}\f]
>   /// where \f$\epsilon\f$ is a constant given when calling the class
>   /// constructor.
> -  class ROBOPTIM_DLLAPI FiniteDifferenceGradient : public DerivableFunction
> +  template <typename FdgPolicy>
> +  class FiniteDifferenceGradient
> +    : public DerivableFunction,
> +      private FdgPolicy
>   {
>   public:
>     /// \brief Instantiate a finite differences gradient.
> @@ -155,4 +181,5 @@ namespace roboptim
>
>  } // end of namespace roboptim
>
> +# include <roboptim/core/finite-difference-gradient.hxx>
>  #endif //! ROBOPTIM_CORE_FINITE_DIFFERENCE_GRADIENT_HH
> diff --git a/include/roboptim/core/finite-difference-gradient.hxx b/include/roboptim/core/finite-difference-gradient.hxx
> new file mode 100644
> index 0000000..371c91c
> --- /dev/null
> +++ b/include/roboptim/core/finite-difference-gradient.hxx
> @@ -0,0 +1,62 @@
> +// Copyright (C) 2009 by Thomas Moulard, AIST, CNRS, INRIA.
> +//
> +// This file is part of the roboptim.
> +//
> +// roboptim is free software: you can redistribute it and/or modify
> +// it under the terms of the GNU Lesser General Public License as published by
> +// the Free Software Foundation, either version 3 of the License, or
> +// (at your option) any later version.
> +//
> +// roboptim is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +// GNU Lesser General Public License for more details.
> +//
> +// You should have received a copy of the GNU Lesser General Public License
> +// along with roboptim.  If not, see <http://www.gnu.org/licenses/>.
> +
> +#ifndef ROBOPTIM_CORE_FINITE_DIFFERENCE_GRADIENT_HXX
> +# define ROBOPTIM_CORE_FINITE_DIFFERENCE_GRADIENT_HXX
> +
> +namespace roboptim
> +{
> +  template <typename FdgPolicy>
> +  FiniteDifferenceGradient<FdgPolicy>::FiniteDifferenceGradient (const Function& adaptee,
> +                                                                value_type epsilon)
> +    throw ()
> +    : DerivableFunction (adaptee.inputSize (), adaptee.outputSize ()),
> +      FdgPolicy (),
> +      adaptee_ (adaptee),
> +      epsilon_ (epsilon)
> +  {
> +    // Avoid meaningless values for epsilon such as 0 or NaN.
> +    assert (epsilon != 0. && epsilon == epsilon);
> +  }
> +
> +  template <typename FdgPolicy>
> +  FiniteDifferenceGradient<FdgPolicy>::~FiniteDifferenceGradient () throw ()
> +  {
> +  }
> +
> +  template <typename FdgPolicy>
> +  void
> +  FiniteDifferenceGradient<FdgPolicy>::impl_compute (result_t& result,
> +                                                    const argument_t& argument)
> +    const throw ()
> +  {
> +    adaptee_ (result, argument);
> +  }
> +
> +  template <typename FdgPolicy>
> +  void
> +  FiniteDifferenceGradient<FdgPolicy>::impl_gradient
> +  (gradient_t& gradient,
> +   const argument_t& argument,
> +   size_type idFunction) const throw ()
> +  {
> +    this->computeGradient (adaptee_, epsilon_, gradient, argument, idFunction);
> +  }
> +
> +} // end of namespace roboptim
> +
> +#endif //! ROBOPTIM_CORE_FINITE_DIFFERENCE_GRADIENT_HXX
> diff --git a/include/roboptim/core/fwd.hh b/include/roboptim/core/fwd.hh
> index 5760b16..11f3d2d 100644
> --- a/include/roboptim/core/fwd.hh
> +++ b/include/roboptim/core/fwd.hh
> @@ -33,6 +33,15 @@ namespace roboptim
>   class ConstantFunction;
>   class DerivableFunction;
>   class DummySolver;
> +
> +  namespace finiteDifferenceGradientPolicies
> +  {
> +    class Simple;
> +    class FivePointsRule;
> +  }; // end of finiteDifferenceGradientPolicies
> +
> +  template <typename FdgPolicy =
> +           finiteDifferenceGradientPolicies::FivePointsRule>
>   class FiniteDifferenceGradient;
>   class Function;
>   class GenericSolver;
> diff --git a/src/finite-difference-gradient.cc b/src/finite-difference-gradient.cc
> index 8fba1e5..edc4ce1 100644
> --- a/src/finite-difference-gradient.cc
> +++ b/src/finite-difference-gradient.cc
> @@ -62,31 +62,6 @@ namespace roboptim
>   }
>
>
> -
> -  FiniteDifferenceGradient::FiniteDifferenceGradient (const Function& adaptee,
> -                                                     value_type epsilon)
> -    throw ()
> -    : DerivableFunction (adaptee.inputSize (), adaptee.outputSize ()),
> -      adaptee_ (adaptee),
> -      epsilon_ (epsilon)
> -  {
> -    // Avoid meaningless values for epsilon such as 0 or NaN.
> -    assert (epsilon != 0. && epsilon == epsilon);
> -  }
> -
> -  FiniteDifferenceGradient::~FiniteDifferenceGradient () throw ()
> -  {
> -  }
> -
> -  void
> -  FiniteDifferenceGradient::impl_compute (result_t& result,
> -                                         const argument_t& argument)
> -    const throw ()
> -  {
> -    adaptee_ (result, argument);
> -  }
> -
> -
>   namespace detail
>   {
>     void
> @@ -154,54 +129,83 @@ namespace roboptim
>     }
>   }
>
> -  void
> -  FiniteDifferenceGradient::impl_gradient (gradient_t& gradient,
> -                                          const argument_t& argument,
> -                                          size_type idFunction) const throw ()
> +  namespace finiteDifferenceGradientPolicies
>   {
> -    assert (outputSize () - idFunction > 0);
> -
> -    value_type h = epsilon_ / 2.;
> -    value_type r_0 = 0.;
> -    value_type round = 0.;
> -    value_type trunc = 0.;
> -    value_type error = 0.;
> -
> -    for (unsigned j = 0; j < argument.size (); ++j)
> -      {
> -       detail::compute_deriv (adaptee_, j, h,
> -                              r_0, round, trunc,
> -                              argument, idFunction);
> -       error = round + trunc;
> -
> -       if (round < trunc && (round > 0 && trunc > 0))
> -         {
> -           value_type r_opt = 0., round_opt = 0., trunc_opt = 0., error_opt = 0.;
> -
> -           /* Compute an optimised stepsize to minimize the total error,
> -              using the scaling of the truncation error (O(h^2)) and
> -              rounding error (O(1/h)). */
> -
> -           value_type h_opt =
> -             h * std::pow (round / (2. * trunc), 1. / 3.);
> -
> -           detail::compute_deriv (adaptee_, j, h_opt,
> -                                  r_opt, round_opt, trunc_opt,
> -                                  argument, idFunction);
> -           error_opt = round_opt + trunc_opt;
> -
> -           /* Check that the new error is smaller, and that the new derivative
> -              is consistent with the error bounds of the original estimate. */
> -
> -           if (error_opt < error && std::fabs (r_opt - r_0) < 4. * error)
> -             {
> -               r_0 = r_opt;
> -               error = error_opt;
> -             }
> -         }
> -
> -       gradient (j) = r_0;
> -      }
> +    void
> +    Simple::computeGradient
> +    (const Function& adaptee,
> +     Function::value_type epsilon,
> +     Function::result_t& gradient,
> +     const Function::argument_t& argument,
> +     Function::value_type idFunction) const throw ()
> +    {
> +      typedef Function::value_type value_type;
> +      assert (adaptee.outputSize () - idFunction > 0);
> +
> +      Function::result_t res = adaptee (argument);
> +      for (unsigned j = 0; j < adaptee.inputSize (); ++j)
> +       {
> +         Function::argument_t xEps = argument;
> +         xEps[j] += epsilon;
> +         Function::result_t resEps = adaptee (xEps);
> +         gradient (j) = (resEps[idFunction] - res[idFunction]) / epsilon;
> +       }
> +    }
> +
> +    void
> +    FivePointsRule::computeGradient
> +    (const Function& adaptee,
> +     Function::value_type epsilon,
> +     Function::result_t& gradient,
> +     const Function::argument_t& argument,
> +     Function::value_type idFunction) const throw ()
> +    {
> +      typedef Function::value_type value_type;
> +
> +      assert (adaptee.outputSize () - idFunction > 0);
> +
> +      value_type h = epsilon / 2.;
> +      value_type r_0 = 0.;
> +      value_type round = 0.;
> +      value_type trunc = 0.;
> +      value_type error = 0.;
> +
> +      for (unsigned j = 0; j < argument.size (); ++j)
> +       {
> +         detail::compute_deriv (adaptee, j, h,
> +                                r_0, round, trunc,
> +                                argument, idFunction);
> +         error = round + trunc;
> +
> +         if (round < trunc && (round > 0 && trunc > 0))
> +           {
> +             value_type r_opt = 0., round_opt = 0., trunc_opt = 0., error_opt = 0.;
> +
> +             /* Compute an optimised stepsize to minimize the total error,
> +                using the scaling of the truncation error (O(h^2)) and
> +                rounding error (O(1/h)). */
> +
> +             value_type h_opt =
> +               h * std::pow (round / (2. * trunc), 1. / 3.);
> +
> +             detail::compute_deriv (adaptee, j, h_opt,
> +                                    r_opt, round_opt, trunc_opt,
> +                                    argument, idFunction);
> +             error_opt = round_opt + trunc_opt;
> +
> +             /* Check that the new error is smaller, and that the new derivative
> +                is consistent with the error bounds of the original estimate. */
> +
> +             if (error_opt < error && std::fabs (r_opt - r_0) < 4. * error)
> +               {
> +                 r_0 = r_opt;
> +                 error = error_opt;
> +               }
> +           }
> +
> +         gradient (j) = r_0;
> +       }
> +    }
>   }
>
>
> @@ -211,7 +215,7 @@ namespace roboptim
>                 const Function::vector_t& x,
>                 Function::value_type threshold) throw ()
>   {
> -    FiniteDifferenceGradient fdfunction (function);
> +    FiniteDifferenceGradient<> fdfunction (function);
>     DerivableFunction::gradient_t grad = function.gradient (x, i);
>     DerivableFunction::gradient_t fdgrad = fdfunction.gradient (x, i);
>
> @@ -228,7 +232,7 @@ namespace roboptim
>                         Function::value_type threshold)
>     throw (BadGradient)
>   {
> -    FiniteDifferenceGradient fdfunction (function);
> +    FiniteDifferenceGradient<> fdfunction (function);
>     DerivableFunction::gradient_t grad = function.gradient (x, i);
>     DerivableFunction::gradient_t fdgrad = fdfunction.gradient (x, i);
>
> diff --git a/tests/finite-difference-gradient.cc b/tests/finite-difference-gradient.cc
> index d765a76..6ada2ed 100644
> --- a/tests/finite-difference-gradient.cc
> +++ b/tests/finite-difference-gradient.cc
> @@ -151,7 +151,7 @@ displayGradient (const DerivableFunction& function,
>                 const Function::vector_t& x,
>                 int i)
>  {
> -  FiniteDifferenceGradient fdfunction (function);
> +  FiniteDifferenceGradient<> fdfunction (function);
>   DerivableFunction::gradient_t grad = function.gradient (x, i);
>   DerivableFunction::gradient_t fdgrad = fdfunction.gradient (x, i);
>
> @@ -200,10 +200,11 @@ int run_test ()
>
>   Gnuplot gnuplot = Gnuplot::make_interactive_gnuplot ();
>
> -  FiniteDifferenceGradient fg_fd (fg, 10.);
> +  FiniteDifferenceGradient<> fg_fd (fg, 10.);
>
>   Polynomial p;
> -  FiniteDifferenceGradient p_fd (p, 10.);
> +  FiniteDifferenceGradient<finiteDifferenceGradientPolicies::Simple>
> +    p_fd (p, 10.);
>
>   Function::discreteInterval_t interval (-100., 100., 1.);
>
>
> -----------------------------------------------------------------------
>
> Summary of changes:
>  ChangeLog                                          |   14 ++
>  include/Makefile.am                                |    1 +
>  .../roboptim/core/finite-difference-gradient.hh    |   29 ++++-
>  .../roboptim/core/finite-difference-gradient.hxx   |   62 ++++++++
>  include/roboptim/core/fwd.hh                       |    9 ++
>  src/finite-difference-gradient.cc                  |  152 ++++++++++----------
>  tests/finite-difference-gradient.cc                |    7 +-
>  7 files changed, 196 insertions(+), 78 deletions(-)
>  create mode 100644 include/roboptim/core/finite-difference-gradient.hxx
>
>
> hooks/post-receive
> --
> roboptim-core
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> roboptim-commit mailing list
> rob...@li...
> https://lists.sourceforge.net/lists/listinfo/roboptim-commit
>

-- 
Thomas Moulard
http://www.linkedin.com/in/moulard

2009	Jan	Feb	Mar	Apr	May	Jun (62)	Jul (62)	Aug (36)	Sep (24)	Oct (41)	Nov (182)	Dec (8)
2010	Jan (12)	Feb (13)	Mar (104)	Apr (95)	May (90)	Jun (90)	Jul (93)	Aug (97)	Sep (91)	Oct (93)	Nov (90)	Dec (95)
2011	Jan (96)	Feb (84)	Mar (94)	Apr (91)	May (93)	Jun (91)	Jul (93)	Aug (93)	Sep (107)	Oct (93)	Nov (58)	Dec
2012	Jan (8)	Feb (4)	Mar	Apr (3)	May	Jun	Jul	Aug	Sep	Oct (1)	Nov (6)	Dec (5)
2013	Jan (16)	Feb (22)	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec

roboptim-commit Mailing List for RobOptim (Page 92)

roboptim-commit — Commit mailing-list (high volume)