diff options
Diffstat (limited to 'utils/maxent.h')
| -rw-r--r-- | utils/maxent.h | 402 |
1 files changed, 402 insertions, 0 deletions
diff --git a/utils/maxent.h b/utils/maxent.h new file mode 100644 index 00000000..b1efd88e --- /dev/null +++ b/utils/maxent.h @@ -0,0 +1,402 @@ +/* + * $Id: maxent.h,v 1.1.1.1 2007/05/15 08:30:35 kyoshida Exp $ + */ + +#ifndef __MAXENT_H_ +#define __MAXENT_H_ + +#include <string> +#include <vector> +#include <list> +#include <map> +#include <algorithm> +#include <iostream> +#include <string> +#include <cassert> +#include "mathvec.h" + +#define USE_HASH_MAP // if you encounter errors with hash, try commenting out + // this line. (the program will be a bit slower, though) +#ifdef USE_HASH_MAP +#include <unordered_map> +#endif + +// +// data format for each sample for training/testing +// +struct ME_Sample { + public: + ME_Sample() : label("") {}; + ME_Sample(const std::string& l) : label(l) {}; + void set_label(const std::string& l) { label = l; } + + // to add a binary feature + void add_feature(const std::string& f) { features.push_back(f); } + + // to add a real-valued feature + void add_feature(const std::string& s, const double d) { + rvfeatures.push_back(std::pair<std::string, double>(s, d)); + } + + public: + std::string label; + std::vector<std::string> features; + std::vector<std::pair<std::string, double> > rvfeatures; + + // obsolete + void add_feature(const std::pair<std::string, double>& f) { + rvfeatures.push_back(f); // real-valued features + } +}; + +// +// for those who want to use load_from_array() +// +typedef struct ME_Model_Data { + char* label; + char* feature; + double weight; +} ME_Model_Data; + +class ME_Model { + public: + void add_training_sample(const ME_Sample& s); + int train(); + std::vector<double> classify(ME_Sample& s) const; + bool load_from_file(const std::string& filename); + bool save_to_file(const std::string& filename, const double th = 0) const; + int num_classes() const { return _num_classes; } + std::string get_class_label(int i) const { return _label_bag.Str(i); } + int get_class_id(const std::string& s) const { return _label_bag.Id(s); } + void get_features( + std::list<std::pair<std::pair<std::string, std::string>, double> >& fl); + void set_heldout(const int h, const int n = 0) { + _nheldout = h; + _early_stopping_n = n; + }; + void use_l1_regularizer(const double v) { _l1reg = v; } + void use_l2_regularizer(const double v) { _l2reg = v; } + void use_SGD(int iter = 30, double eta0 = 1, double alpha = 0.85) { + _optimization_method = SGD; + SGD_ITER = iter; + SGD_ETA0 = eta0; + SGD_ALPHA = alpha; + } + bool load_from_array(const ME_Model_Data data[]); + void set_reference_model(const ME_Model& ref_model) { + _ref_modelp = &ref_model; + }; + void clear(); + + ME_Model() { + _l1reg = _l2reg = 0; + _nheldout = 0; + _early_stopping_n = 0; + _ref_modelp = NULL; + _optimization_method = LBFGS; + } + + public: + // obsolete. just for downward compatibility + int train(const std::vector<ME_Sample>& train); + + private: + enum OPTIMIZATION_METHOD { + LBFGS, + OWLQN, + SGD + } _optimization_method; + // OWLQN and SGD are available only for L1-regularization + + int SGD_ITER; + double SGD_ETA0; + double SGD_ALPHA; + + double _l1reg, _l2reg; + + struct Sample { + int label; + std::vector<int> positive_features; + std::vector<std::pair<int, double> > rvfeatures; + std::vector<double> ref_pd; // reference probability distribution + bool operator<(const Sample& x) const { + for (unsigned int i = 0; i < positive_features.size(); i++) { + if (i >= x.positive_features.size()) return false; + int v0 = positive_features[i]; + int v1 = x.positive_features[i]; + if (v0 < v1) return true; + if (v0 > v1) return false; + } + return false; + } + }; + + struct ME_Feature { + enum { + MAX_LABEL_TYPES = 255 + }; + + // ME_Feature(const int l, const int f) : _body((l << 24) + f) { + // assert(l >= 0 && l < 256); + // assert(f >= 0 && f <= 0xffffff); + // }; + // int label() const { return _body >> 24; } + // int feature() const { return _body & 0xffffff; } + ME_Feature(const int l, const int f) : _body((f << 8) + l) { + assert(l >= 0 && l <= MAX_LABEL_TYPES); + assert(f >= 0 && f <= 0xffffff); + }; + int label() const { return _body & 0xff; } + int feature() const { return _body >> 8; } + unsigned int body() const { return _body; } + + private: + unsigned int _body; + }; + + struct ME_FeatureBag { +#ifdef USE_HASH_MAP + typedef std::unordered_map<unsigned int, int> map_type; +#else + typedef std::map<unsigned int, int> map_type; +#endif + map_type mef2id; + std::vector<ME_Feature> id2mef; + int Put(const ME_Feature& i) { + map_type::const_iterator j = mef2id.find(i.body()); + if (j == mef2id.end()) { + int id = id2mef.size(); + id2mef.push_back(i); + mef2id[i.body()] = id; + return id; + } + return j->second; + } + int Id(const ME_Feature& i) const { + map_type::const_iterator j = mef2id.find(i.body()); + if (j == mef2id.end()) { + return -1; + } + return j->second; + } + ME_Feature Feature(int id) const { + assert(id >= 0 && id < (int)id2mef.size()); + return id2mef[id]; + } + int Size() const { return id2mef.size(); } + void Clear() { + mef2id.clear(); + id2mef.clear(); + } + }; + + struct hashfun_str { + size_t operator()(const std::string& s) const { + assert(sizeof(int) == 4 && sizeof(char) == 1); + const int* p = reinterpret_cast<const int*>(s.c_str()); + size_t v = 0; + int n = s.size() / 4; + for (int i = 0; i < n; i++, p++) { + // v ^= *p; + v ^= *p << (4 * (i % 2)); // note) 0 <= char < 128 + } + int m = s.size() % 4; + for (int i = 0; i < m; i++) { + v ^= s[4 * n + i] << (i * 8); + } + return v; + } + }; + + struct MiniStringBag { +#ifdef USE_HASH_MAP + typedef std::unordered_map<std::string, int, hashfun_str> map_type; +#else + typedef std::map<std::string, int> map_type; +#endif + int _size; + map_type str2id; + MiniStringBag() : _size(0) {} + int Put(const std::string& i) { + map_type::const_iterator j = str2id.find(i); + if (j == str2id.end()) { + int id = _size; + _size++; + str2id[i] = id; + return id; + } + return j->second; + } + int Id(const std::string& i) const { + map_type::const_iterator j = str2id.find(i); + if (j == str2id.end()) return -1; + return j->second; + } + int Size() const { return _size; } + void Clear() { + str2id.clear(); + _size = 0; + } + map_type::const_iterator begin() const { return str2id.begin(); } + map_type::const_iterator end() const { return str2id.end(); } + }; + + struct StringBag : public MiniStringBag { + std::vector<std::string> id2str; + int Put(const std::string& i) { + map_type::const_iterator j = str2id.find(i); + if (j == str2id.end()) { + int id = id2str.size(); + id2str.push_back(i); + str2id[i] = id; + return id; + } + return j->second; + } + std::string Str(const int id) const { + assert(id >= 0 && id < (int)id2str.size()); + return id2str[id]; + } + int Size() const { return id2str.size(); } + void Clear() { + str2id.clear(); + id2str.clear(); + } + }; + + std::vector<Sample> _vs; // vector of training_samples + StringBag _label_bag; + MiniStringBag _featurename_bag; + std::vector<double> _vl; // vector of lambda + ME_FeatureBag _fb; + int _num_classes; + std::vector<double> _vee; // empirical expectation + std::vector<double> _vme; // empirical expectation + std::vector<std::vector<int> > _feature2mef; + std::vector<Sample> _heldout; + double _train_error; // current error rate on the training data + double _heldout_error; // current error rate on the heldout data + int _nheldout; + int _early_stopping_n; + std::vector<double> _vhlogl; + const ME_Model* _ref_modelp; + + double heldout_likelihood(); + int conditional_probability(const Sample& nbs, + std::vector<double>& membp) const; + int make_feature_bag(const int cutoff); + int classify(const Sample& nbs, std::vector<double>& membp) const; + double update_model_expectation(); + int perform_QUASI_NEWTON(); + int perform_SGD(); + int perform_GIS(int C); + std::vector<double> perform_LBFGS(const std::vector<double>& x0); + std::vector<double> perform_OWLQN(const std::vector<double>& x0, + const double C); + double backtracking_line_search(const Vec& x0, const Vec& grad0, + const double f0, const Vec& dx, Vec& x, + Vec& grad1); + double regularized_func_grad(const double C, const Vec& x, Vec& grad); + double constrained_line_search(double C, const Vec& x0, const Vec& grad0, + const double f0, const Vec& dx, Vec& x, + Vec& grad1); + + void set_ref_dist(Sample& s) const; + void init_feature2mef(); + + double FunctionGradient(const std::vector<double>& x, + std::vector<double>& grad); + static double FunctionGradientWrapper(const std::vector<double>& x, + std::vector<double>& grad); +}; + +#endif + +/* + * $Log: maxent.h,v $ + * Revision 1.1.1.1 2007/05/15 08:30:35 kyoshida + * stepp tagger, by Okanohara and Tsuruoka + * + * Revision 1.24 2006/08/21 17:30:38 tsuruoka + * use MAX_LABEL_TYPES + * + * Revision 1.23 2006/07/25 13:19:53 tsuruoka + * sort _vs[] + * + * Revision 1.22 2006/07/18 11:13:15 tsuruoka + * modify comments + * + * Revision 1.21 2006/07/18 10:02:15 tsuruoka + * remove sample2feature[] + * speed up conditional_probability() + * + * Revision 1.20 2006/07/18 05:10:51 tsuruoka + * add ref_dist + * + * Revision 1.19 2005/12/23 10:33:02 tsuruoka + * support real-valued features + * + * Revision 1.18 2005/12/23 09:15:29 tsuruoka + * modify _train to reduce memory consumption + * + * Revision 1.17 2005/10/28 13:02:34 tsuruoka + * set_heldout(): add default value + * Feature() + * + * Revision 1.16 2005/09/12 13:51:16 tsuruoka + * Sample: list -> vector + * + * Revision 1.15 2005/09/12 13:27:10 tsuruoka + * add add_training_sample() + * + * Revision 1.14 2005/04/27 11:22:27 tsuruoka + * bugfix + * ME_Sample: list -> vector + * + * Revision 1.13 2005/04/27 10:20:19 tsuruoka + * MiniStringBag -> StringBag + * + * Revision 1.12 2005/04/27 10:00:42 tsuruoka + * remove tmpfb + * + * Revision 1.11 2005/04/26 14:25:53 tsuruoka + * add MiniStringBag, USE_HASH_MAP + * + * Revision 1.10 2004/10/04 05:50:25 tsuruoka + * add Clear() + * + * Revision 1.9 2004/08/09 12:27:21 tsuruoka + * change messages + * + * Revision 1.8 2004/08/04 13:55:19 tsuruoka + * modify _sample2feature + * + * Revision 1.7 2004/07/29 05:51:13 tsuruoka + * remove modeldata.h + * + * Revision 1.6 2004/07/28 13:42:58 tsuruoka + * add AGIS + * + * Revision 1.5 2004/07/28 05:54:14 tsuruoka + * get_class_name() -> get_class_label() + * ME_Feature: bugfix + * + * Revision 1.4 2004/07/27 16:58:47 tsuruoka + * modify the interface of classify() + * + * Revision 1.3 2004/07/26 17:23:46 tsuruoka + * _sample2feature: list -> vector + * + * Revision 1.2 2004/07/26 15:49:23 tsuruoka + * modify ME_Feature + * + * Revision 1.1 2004/07/26 13:10:55 tsuruoka + * add files + * + * Revision 1.18 2004/07/22 08:34:45 tsuruoka + * modify _sample2feature[] + * + * Revision 1.17 2004/07/21 16:33:01 tsuruoka + * remove some comments + * + */ |