JGradient.hh

Go to the documentation of this file.

#ifndef __JFIT__JGRADIENT__
#define __JFIT__JGRADIENT__
 
#include <limits>
#include <vector>
#include <cmath>
#include <memory>
#include <ostream>
#include <iomanip>
#include <vector>
 
#include "JLang/JManip.hh"
#include "JLang/JException.hh"
#include "Jeep/JMessage.hh"
 
 
/**
 * \author mdejong
 */
 
namespace JFIT {}
namespace JPP { using namespace JFIT; }
 
namespace JFIT {
 
  /**
   * Auxiliary data structure for fit parameter.
   */
  struct JParameter_t {
    /**
     * Virtual destructor.
     */
    virtual ~JParameter_t()
    {}
 
    /**
     * Apply step.
     *
     * \param  step              step
     */
    virtual void apply(const double step) = 0;
  };
 
 
  /**
   * Auxiliary data structure for editable parameter.
   */
  struct JModifier_t :
    public std::shared_ptr<JParameter_t>
  {
    /**
     * Constructor.
     *
     * \param  name              name
     * \param  parameter         parameter
     * \param  value             value
     */
    JModifier_t(const std::string& name,
                JParameter_t*      parameter,
                const double       value) :
      std::shared_ptr<JParameter_t>(parameter),
      name (name),
      value(value)
    {}
 
    std::string name;
    double      value;
  };
  
 
  /**
   * Conjugate gradient fit.
   */
  struct JGradient :
    public std::vector<JModifier_t>
  {
    /**
     * Constructor.
     *
     * The number of iterations and epsilon refer to the number of steps and 
     * the distance to the minimum, respectively.\n
     * The number of extra steps can be used to overcome a possible hurdle on the way.
     *
     * \param  Nmax              maximum number of iterations
     * \param  Nextra            maximum number of extra steps
     * \param  epsilon           epsilon
     * \param  debug             debug
     */
    JGradient(const size_t Nmax     = std::numeric_limits<size_t>::max(),
              const size_t Nextra   = 0,
              const double epsilon  = 1.0e-4,
              const int    debug    = 3) :
      Nmax   (Nmax),
      Nextra (Nextra),
      epsilon(epsilon),
      debug  (debug)
    {}
 
 
    /**
     * Fit.
     *
     * The template parameter should provide for the following function operator.
     * <pre>
     *    double operator()(int option);
     * </pre>
     * The value of the option corresponds to the following cases.
     *  - 0 => step wise improvement of the chi2;
     *  - 1 => evaluation of the chi2 before the determination of the gradient of the chi2; and
     *  - 2 => evaluation of the derivative of the chi2 to each fit parameter.
     *
     * \param  getChi2           chi2 function
     * \return                   chi2
     */
    template<class T>
    double operator()(const T& getChi2)
    {
      using namespace std;
      using namespace JPP;
 
      vector<double> chi2(5, numeric_limits<double>::max());
 
      if (this->empty()) {
        return numeric_limits<double>::max();
      }
 
      chi2[0] = this->evaluate(getChi2);
      
      const size_t N = this->size();
 
      vector<double> H(N);
      vector<double> G(N);
 
      for (size_t i = 0; i != N; ++i) {
        G[i] = -1.0 * gradient[i];
        H[i] = G[i];
        gradient[i] = H[i];
      }
 
      numberOfIterations = 0;
 
      for ( ; numberOfIterations != Nmax; ++numberOfIterations) {
 
        DEBUG("chi2[0]  " << setw(4) << numberOfIterations << ' ' << FIXED(12,5) << chi2[0] << endl);
 
        // minimise chi2 in direction of gradient
 
        chi2[1] = chi2[0];
        chi2[2] = chi2[1];
 
        size_t m = 0;
        
        for (double ds = 1.0; ds > 1.0e-3; ) {
 
          this->move(+1.0 * ds);
 
          chi2[3] = getChi2(0);
 
          DEBUG("chi2[3]  " << setw(4) << m << ' ' << FIXED(12,5) << chi2[3] << ' ' << FIXED(12,5) << ds << endl);
 
          if (chi2[3] < chi2[2]) {
 
            chi2[1] = chi2[2];
            chi2[2] = chi2[3];
 
            m = 0;
            
            continue;
          }
 
          if (ds == 1.0) {
 
            if (m == 0) {
              chi2[4] = chi2[3];
            }
 
            if (m != Nextra) {
 
              ++m;
 
              continue;
 
            } else {
 
              for ( ; m != 0; --m) {
                this->move(-1.0 * ds);
              }
 
              chi2[3] = chi2[4];
            }
          }
 
          this->move(-1.0 * ds);
 
          if (chi2[2] < chi2[3]) {
 
            // final step based on parabolic interpolation through following points
            //
            // x1 = -1 * ds  ->  chi2[1]
            // x2 =  0 * ds  ->  chi2[2]
            // x3 = +1 * ds  ->  chi2[3]
 
            const double f21 = chi2[2] - chi2[1];   // f(x2) - f(x1)
            const double f23 = chi2[2] - chi2[3];   // f(x2) - f(x3)
 
            const double xs  =  0.5 * (f21 - f23) / (f23 + f21);
 
            this->move(+1.0 * xs * ds);
 
            chi2[3] = getChi2(0);
            
            if (chi2[3] < chi2[2]) {
 
              chi2[2] = chi2[3];
 
            } else {
 
              this->move(-1.0 * xs * ds);
 
              chi2[2] = getChi2(0);
            }
 
            DEBUG("chi2[2]  " << setw(4) << numberOfIterations << ' ' << FIXED(12,5) << chi2[2] << ' ' << SCIENTIFIC(12,5) << ds << endl);
 
            break;
 
          } else {
 
            ds *= 0.5;
          }
        }
 
        if (fabs(chi2[2] - chi2[0]) < epsilon * (absolute ? 1.0 : 0.5 * (fabs(chi2[0]) + fabs(chi2[2])))) {
 
          chi2[0] = chi2[2];
 
          break;
        }
 
        chi2[0] = this->evaluate(getChi2);
 
        double gg  = 0.0;
        double dgg = 0.0;
 
        for (size_t i = 0; i != N; ++i){
          gg  +=  G[i]*G[i];
          dgg += (gradient[i] + G[i]) * gradient[i];
        }
 
        if (gg == 0.0) {
          break;
        }
 
        dgg /= gg;
 
        for (size_t i = 0; i != N; ++i){
          G[i] = -1.0 * gradient[i];
          H[i] =  G[i] + dgg * H[i];
          gradient[i] = H[i];
        }
      }
 
      DEBUG("chi2[0]  " << setw(4) << numberOfIterations << ' ' << FIXED(12,5) << chi2[0] << endl);
 
      return chi2[0];
    }
 
 
    /**
     * Make scan at current position.
     *
     * \param  out               output stream
     * \param  getChi2           chi2 function
     * \param  xs                set of steps
     */
    template<class T>
    void operator()(std::ostream& out, const T& getChi2, const std::vector<double>& xs) const
    {
      using namespace std;
 
      out << "scan: ";
 
      for (const auto& i : *this) { 
        out << i.name << ' ';
      }
 
      out << "chi2" << endl;
 
      std::vector<double> ys;
 
      scan(out, getChi2, xs, ys);
    }
 
 
    size_t  Nmax;              //!< maximum number of iterations
    size_t  Nextra;            //!< maximum number of extra steps
    double  epsilon;           //!< epsilon
    int     debug;             //!< debug
 
    bool    absolute  = false; //!< absolute chi2
    bool    normalise = false; //!< normalise gradient
 
    size_t  numberOfIterations;
 
  private:
    /**
     * Evaluate gradient.
     *
     * \return                   chi2
     */
    template<class T>
    double evaluate(const T& getChi2)
    {
      using namespace std;
      using namespace JPP;
 
      const size_t N = this->size();
 
      gradient.resize(N);
 
      for (std::vector<double>::iterator i = gradient.begin(); i != gradient.end(); ++i) {
        *i = 0.0;
      }
      
      const double x0 = getChi2(1);
 
      size_t width = 1;
 
      for (size_t i = 0; i != N; ++i) {
        if ((*this)[i].name.size() > width) {
          width = (*this)[i].name.size();
        }
      }
 
      double V = 0.0;
 
      for (size_t i = 0; i != N; ++i) {
 
        if ((*this)[i].value != 0.0) {
 
          (*this)[i]->apply(+0.5 * (*this)[i].value);
 
          const double x1 = getChi2(2);
 
          (*this)[i]->apply(-0.5 * (*this)[i].value);
          (*this)[i]->apply(-0.5 * (*this)[i].value);
 
          const double x2 = getChi2(2);
 
          gradient[i] = x1 - x2;
        
          (*this)[i]->apply(+0.5 * (*this)[i].value);
 
          DEBUG(setw(width) << left << (*this)[i].name << right << ' ' << FIXED(12,5) << (*this)[i].value << ' ' << FIXED(12,5) << gradient[i] << endl);
          
        } else {
 
          gradient[i] = 0.0;
        }
 
        V += gradient[i] * gradient[i];
      }
 
      V = sqrt(V);
 
      DEBUG(setw(width) << left << "|gradient|" << right << ' ' << FIXED(12,5) << V << endl);
 
      if (normalise) {
        for (size_t i = 0; i != N; ++i) {
          gradient[i] /= V;
        }
      }
 
      return x0;
    }
    
 
    /**
     * Move.
     *
     * \param  factor            factor
     */
    void move(const double factor)
    {
      if        (factor > 0.0) {
        for (size_t i = 0; i != this->size(); ++i) {
          (*this)[ i ]->apply((*this)[ i ].value * gradient[ i ] * factor);
        }
      } else if (factor < 0.0) {
        for (size_t i = this->size(); i != 0; --i) {
          (*this)[i-1]->apply((*this)[i-1].value * gradient[i-1] * factor);
        }
      }
    }
 
 
    /**
     * Scan.
     *
     * \param  out               output stream
     * \param  getChi2           chi2 function
     * \param  xs                set of steps
     * \param  ys                set of current steps
     */
    template<class T>
    void scan(std::ostream& out, const T& getChi2, const std::vector<double>& xs, std::vector<double>& ys) const
    {
      using namespace std;
 
      if (ys.size() == this->size()) {
 
        for (size_t i = 0; i != this->size(); ++i) {
          (*this)[ i ]->apply(+ys[ i ]);
        }
 
        for (const double y : ys) {
          out << FIXED(12,5) << y << ' ';
        }
 
        out << FIXED(12,5) << getChi2(1) << endl; 
 
        for (size_t i = this->size(); i != 0; --i) {
          (*this)[i-1]->apply(-ys[i-1]);
        }
 
      } else {
 
        for (const double x : xs) {
 
          ys.push_back(x * (*this)[ys.size()].value);
 
          scan(out, getChi2, xs, ys);
 
          ys.pop_back();
        }
      }
    }
    
    std::vector<double> gradient;
  };
}
 
#endif