boosting.h

Go to the documentation of this file.

// -*- C++ -*-
#ifndef __LEMGA_AGGREGATING_BOOSTING_H__
#define __LEMGA_AGGREGATING_BOOSTING_H__

#include <numeric>
#include <utility>
#include "aggregating.h"
#include "cost.h"

#define BOOSTING_OUTPUT_CACHE   1

namespace lemga {

struct _boost_gd;

class Boosting : public Aggregating {
protected:
    std::vector<REAL> lm_wgt;   
    bool convex;                

    // runtime parameters
    bool grad_desc_view;        
    REAL min_cst, min_err;

public:
    const cost::Cost& cost_functor;

    explicit Boosting (bool cvx = false, const cost::Cost& = cost::_cost);
    Boosting (const Aggregating&);
    explicit Boosting (std::istream& is): cost_functor(cost::_cost)
    { is >> *this; }

    virtual const id_t& id () const;
    virtual Boosting* create () const { return new Boosting(); }
    virtual Boosting* clone () const { return new Boosting(*this); }

    bool is_convex () const { return convex; }
    REAL model_weight (UINT n) const { return lm_wgt[n]; }
    void use_gradient_descent (bool gd = true) { grad_desc_view = gd; }
    void set_min_cost (REAL mincst) { min_cst = mincst; }
    void set_min_error (REAL minerr) { min_err = minerr; }
    virtual REAL margin_norm () const;
    virtual REAL margin_of (const Input&, const Output&) const;
    virtual REAL margin (UINT) const;

    virtual bool support_weighted_data () const { return true; }
    virtual void train ();
    virtual void reset ();
    virtual Output operator() (const Input&) const;
    virtual Output get_output (UINT) const;

#if BOOSTING_OUTPUT_CACHE
    virtual void set_train_data (const pDataSet&, const pDataWgt& = 0);

private:
    mutable std::vector<UINT> cache_n;
    mutable std::vector<Output> cache_y;
protected:
    inline void clear_cache (UINT idx) const {
        assert(idx < n_samples && cache_n.size() == n_samples);
        cache_n[idx] = 0;
        cache_y[idx].clear();
    }
    inline void clear_cache () const {
        cache_n.clear(); cache_y.clear();
        cache_n.resize(n_samples, 0);
        cache_y.resize(n_samples);
    }
#endif

protected:
    REAL model_weight_sum () const {
        return std::accumulate
            (lm_wgt.begin(), lm_wgt.begin()+n_in_agg, REAL(0));
    }

    pLearnModel train_with_smpwgt (const pDataWgt&) const;



    REAL assign_weight (const DataWgt& sw, const LearnModel& l) {
        assert(n_samples == sw.size());
        return convex? convex_weight(sw, l) : linear_weight(sw, l);
    }

    pDataWgt update_smpwgt (const DataWgt& sw, const LearnModel& l) {
        assert(n_in_agg > 0 && lm[n_in_agg-1] == &l);
        assert(n_samples == sw.size());
        DataWgt* pdw = new DataWgt(sw);  // create a separate copy
        convex? convex_smpwgt(*pdw) : linear_smpwgt(*pdw);
        return pdw;
    }

    virtual REAL convex_weight (const DataWgt&, const LearnModel&);
    virtual REAL linear_weight (const DataWgt&, const LearnModel&);
    virtual void convex_smpwgt (DataWgt&);
    virtual void linear_smpwgt (DataWgt&);

protected:
    virtual bool serialize (std::ostream&, ver_list&) const;
    virtual bool unserialize (std::istream&, ver_list&, const id_t& = NIL_ID);

public:
    friend struct _boost_gd;
    REAL cost () const;

protected:
    virtual void train_gd ();       
    pDataWgt sample_weight () const;

public:
    class BoostWgt {
        std::vector<pLearnModel> lm;
        std::vector<REAL> lm_wgt;

    public:
        BoostWgt () {}
        BoostWgt (const std::vector<pLearnModel>& _lm,
                  const std::vector<REAL>& _wgt)
            : lm(_lm), lm_wgt(_wgt) { assert(lm.size() == lm_wgt.size()); }

        UINT size () const { return lm.size(); }
        const std::vector<pLearnModel>& models () const { return lm; }
        const std::vector<REAL>& weights () const { return lm_wgt; }
        void clear () { lm.clear(); lm_wgt.clear(); }

        BoostWgt& operator+= (const BoostWgt&);
        BoostWgt& operator*= (REAL);
        BoostWgt operator- () const;
#ifndef NDEBUG
        bool operator== (const BoostWgt& w) const {
            return (lm == w.lm && lm_wgt == w.lm_wgt);
        }
#endif
    };
};

struct _boost_gd {
    Boosting* b;
    UINT max_step;
    explicit _boost_gd (Boosting* pb) : b(pb)
    { max_step = b->max_n_model - b->size(); }

    REAL cost () const { return b->cost(); }

    Boosting::BoostWgt weight () const {
        return Boosting::BoostWgt(b->lm, b->lm_wgt);
    }

    void set_weight (const Boosting::BoostWgt& bw) const {
#if BOOSTING_OUTPUT_CACHE
        b->clear_cache();
#endif
        b->lm = bw.models(); b->lm_wgt = bw.weights();
        b->n_in_agg = b->lm.size();
        assert(b->lm.size() == b->lm_wgt.size());
        for (UINT i = 0; i < b->lm.size(); ++i)
            b->set_dimensions(*(b->lm[i]));
    }

    Boosting::BoostWgt gradient () const {
        std::vector<pLearnModel> lm = b->lm;
        std::vector<REAL> wgt(lm.size(), 0);

        lm.push_back(b->train_with_smpwgt(b->sample_weight()));
        wgt.push_back(-1);
        return Boosting::BoostWgt(lm, wgt);
    }

    bool stop_opt (UINT step, REAL cst) const {
        return (step >= max_step || cst < b->min_cst);
    }
};

namespace op {

template <typename R>
R inner_product (const Boosting::BoostWgt& w1, const Boosting::BoostWgt& w2) {
#ifndef NDEBUG
    std::vector<REAL> w1t(w1.size()); w1t.back() = -1;
    assert(w1.weights() == w1t);
    std::vector<REAL> w2t(w2.size()); w2t.back() = -1;
    assert(w2.weights() == w2t);
#endif
    LearnModel& g1 = *w1.models().back();
    LearnModel& g2 = *w2.models().back();

    UINT n = g1.train_data()->size();
    assert(g1.train_data() == g2.train_data());
    R sum = 0;
    for (UINT i = 0; i < n; ++i)
        sum += g1.get_output(i)[0] * g2.get_output(i)[0];
    return sum / n;
}

} // namespace lemga::op
} // namespace lemga

#ifdef  __BOOSTING_H__
#warning "This header file may conflict with another `boosting.h' file."
#endif
#define __BOOSTING_H__
#endif

---