From a04b6a955f49f5f72e2a27f388e581734b213204 Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Thu, 9 Oct 2014 14:14:33 -0400 Subject: fix header names in util/ --- utils/alias_sampler.h | 4 ++-- utils/alignment_io.h | 4 ++-- utils/b64tools.h | 4 ++-- utils/corpus_tools.h | 4 ++-- utils/exp_semiring.h | 4 ++-- utils/fast_sparse_vector.h | 4 ++-- utils/fdict.h | 4 ++-- utils/feature_vector.h | 4 ++-- utils/filelib.h | 4 ++-- utils/kernel_string_subseq.h | 4 ++-- utils/m.h | 4 ++-- utils/murmur_hash3.h | 4 ++-- utils/perfect_hash.h | 4 ++-- utils/prob.h | 4 ++-- utils/small_vector.h | 4 ++-- utils/sparse_vector.h | 4 ++-- utils/star.h | 4 ++-- utils/tdict.h | 4 ++-- utils/timing_stats.h | 4 ++-- utils/verbose.h | 4 ++-- utils/weights.h | 4 ++-- utils/wordid.h | 4 ++-- 22 files changed, 44 insertions(+), 44 deletions(-) (limited to 'utils') diff --git a/utils/alias_sampler.h b/utils/alias_sampler.h index 81541f7a..0f9d3f6d 100644 --- a/utils/alias_sampler.h +++ b/utils/alias_sampler.h @@ -1,5 +1,5 @@ -#ifndef _ALIAS_SAMPLER_H_ -#define _ALIAS_SAMPLER_H_ +#ifndef ALIAS_SAMPLER_H_ +#define ALIAS_SAMPLER_H_ #include #include diff --git a/utils/alignment_io.h b/utils/alignment_io.h index 63fb916b..ec70688e 100644 --- a/utils/alignment_io.h +++ b/utils/alignment_io.h @@ -1,5 +1,5 @@ -#ifndef _ALIGNMENT_IO_H_ -#define _ALIGNMENT_IO_H_ +#ifndef ALIGNMENT_IO_H_ +#define ALIGNMENT_IO_H_ #include #include diff --git a/utils/b64tools.h b/utils/b64tools.h index c821fc8f..130a9102 100644 --- a/utils/b64tools.h +++ b/utils/b64tools.h @@ -1,5 +1,5 @@ -#ifndef _B64_TOOLS_H_ -#define _B64_TOOLS_H_ +#ifndef B64_TOOLS_H_ +#define B64_TOOLS_H_ namespace B64 { bool b64decode(const unsigned char* data, const size_t insize, char* out, const size_t outsize); diff --git a/utils/corpus_tools.h b/utils/corpus_tools.h index f6699d87..3ccaf6ef 100644 --- a/utils/corpus_tools.h +++ b/utils/corpus_tools.h @@ -1,5 +1,5 @@ -#ifndef _CORPUS_TOOLS_H_ -#define _CORPUS_TOOLS_H_ +#ifndef CORPUS_TOOLS_H_ +#define CORPUS_TOOLS_H_ #include #include diff --git a/utils/exp_semiring.h b/utils/exp_semiring.h index 26a22071..164286e3 100644 --- a/utils/exp_semiring.h +++ b/utils/exp_semiring.h @@ -1,5 +1,5 @@ -#ifndef _EXP_SEMIRING_H_ -#define _EXP_SEMIRING_H_ +#ifndef EXP_SEMIRING_H_ +#define EXP_SEMIRING_H_ #include #include "star.h" diff --git a/utils/fast_sparse_vector.h b/utils/fast_sparse_vector.h index 6e2a77cd..1e0ab428 100644 --- a/utils/fast_sparse_vector.h +++ b/utils/fast_sparse_vector.h @@ -1,5 +1,5 @@ -#ifndef _FAST_SPARSE_VECTOR_H_ -#define _FAST_SPARSE_VECTOR_H_ +#ifndef FAST_SPARSE_VECTOR_H_ +#define FAST_SPARSE_VECTOR_H_ // FastSparseVector is a integer indexed unordered map that supports very fast // (mathematical) vector operations when the sizes are very small, and reasonably diff --git a/utils/fdict.h b/utils/fdict.h index eb853fb2..94763890 100644 --- a/utils/fdict.h +++ b/utils/fdict.h @@ -1,5 +1,5 @@ -#ifndef _FDICT_H_ -#define _FDICT_H_ +#ifndef FDICT_H_ +#define FDICT_H_ #ifdef HAVE_CONFIG_H #include "config.h" diff --git a/utils/feature_vector.h b/utils/feature_vector.h index a7b61a66..bf77b5ac 100644 --- a/utils/feature_vector.h +++ b/utils/feature_vector.h @@ -1,5 +1,5 @@ -#ifndef _FEATURE_VECTOR_H_ -#define _FEATURE_VECTOR_H_ +#ifndef FEATURE_VECTOR_H_ +#define FEATURE_VECTOR_H_ #include #include "sparse_vector.h" diff --git a/utils/filelib.h b/utils/filelib.h index 4fa69760..90620d05 100644 --- a/utils/filelib.h +++ b/utils/filelib.h @@ -1,5 +1,5 @@ -#ifndef _FILELIB_H_ -#define _FILELIB_H_ +#ifndef FILELIB_H_ +#define FILELIB_H_ #include #include diff --git a/utils/kernel_string_subseq.h b/utils/kernel_string_subseq.h index 516e8b89..00ee7da7 100644 --- a/utils/kernel_string_subseq.h +++ b/utils/kernel_string_subseq.h @@ -1,5 +1,5 @@ -#ifndef _KERNEL_STRING_SUBSEQ_H_ -#define _KERNEL_STRING_SUBSEQ_H_ +#ifndef KERNEL_STRING_SUBSEQ_H_ +#define KERNEL_STRING_SUBSEQ_H_ #include #include diff --git a/utils/m.h b/utils/m.h index dc881b36..bd82c305 100644 --- a/utils/m.h +++ b/utils/m.h @@ -1,5 +1,5 @@ -#ifndef _M_H_ -#define _M_H_ +#ifndef M_H_HEADER_ +#define M_H_HEADER_ #include #include diff --git a/utils/murmur_hash3.h b/utils/murmur_hash3.h index a125d775..e8a8b10b 100644 --- a/utils/murmur_hash3.h +++ b/utils/murmur_hash3.h @@ -2,8 +2,8 @@ // MurmurHash3 was written by Austin Appleby, and is placed in the public // domain. The author hereby disclaims copyright to this source code. -#ifndef _MURMURHASH3_H_ -#define _MURMURHASH3_H_ +#ifndef MURMURHASH3_H_ +#define MURMURHASH3_H_ //----------------------------------------------------------------------------- // Platform-specific functions and macros diff --git a/utils/perfect_hash.h b/utils/perfect_hash.h index 29ea48a9..8c12c9f0 100644 --- a/utils/perfect_hash.h +++ b/utils/perfect_hash.h @@ -1,5 +1,5 @@ -#ifndef _PERFECT_HASH_MAP_H_ -#define _PERFECT_HASH_MAP_H_ +#ifndef PERFECT_HASH_MAP_H_ +#define PERFECT_HASH_MAP_H_ #include #include diff --git a/utils/prob.h b/utils/prob.h index bc297870..32ba9a86 100644 --- a/utils/prob.h +++ b/utils/prob.h @@ -1,5 +1,5 @@ -#ifndef _PROB_H_ -#define _PROB_H_ +#ifndef PROB_H_ +#define PROB_H_ #include "logval.h" diff --git a/utils/small_vector.h b/utils/small_vector.h index 280ab72c..c8cbcb2c 100644 --- a/utils/small_vector.h +++ b/utils/small_vector.h @@ -1,5 +1,5 @@ -#ifndef _SMALL_VECTOR_H_ -#define _SMALL_VECTOR_H_ +#ifndef SMALL_VECTOR_H_ +#define SMALL_VECTOR_H_ /* REQUIRES that T is POD (can be memcpy). won't work (yet) due to union with SMALL_VECTOR_POD==0 - may be possible to handle movable types that have ctor/dtor, by using explicit allocation, ctor/dtor calls. but for now JUST USE THIS FOR no-meaningful ctor/dtor POD types. diff --git a/utils/sparse_vector.h b/utils/sparse_vector.h index 049151f7..13601376 100644 --- a/utils/sparse_vector.h +++ b/utils/sparse_vector.h @@ -1,5 +1,5 @@ -#ifndef _SPARSE_VECTOR_H_ -#define _SPARSE_VECTOR_H_ +#ifndef SPARSE_VECTOR_H_ +#define SPARSE_VECTOR_H_ #include "fast_sparse_vector.h" #define SparseVector FastSparseVector diff --git a/utils/star.h b/utils/star.h index 21977dc9..01433d12 100644 --- a/utils/star.h +++ b/utils/star.h @@ -1,5 +1,5 @@ -#ifndef _STAR_H_ -#define _STAR_H_ +#ifndef STAR_H_ +#define STAR_H_ // star(x) computes the infinite sum x^0 + x^1 + x^2 + ... diff --git a/utils/tdict.h b/utils/tdict.h index bb19ecd5..eed33c3a 100644 --- a/utils/tdict.h +++ b/utils/tdict.h @@ -1,5 +1,5 @@ -#ifndef _TDICT_H_ -#define _TDICT_H_ +#ifndef TDICT_H_ +#define TDICT_H_ #include #include diff --git a/utils/timing_stats.h b/utils/timing_stats.h index 0a9f7656..69a1cf4b 100644 --- a/utils/timing_stats.h +++ b/utils/timing_stats.h @@ -1,5 +1,5 @@ -#ifndef _TIMING_STATS_H_ -#define _TIMING_STATS_H_ +#ifndef TIMING_STATS_H_ +#define TIMING_STATS_H_ #include #include diff --git a/utils/verbose.h b/utils/verbose.h index 73476383..e39e23cb 100644 --- a/utils/verbose.h +++ b/utils/verbose.h @@ -1,5 +1,5 @@ -#ifndef _VERBOSE_H_ -#define _VERBOSE_H_ +#ifndef VERBOSE_H_ +#define VERBOSE_H_ extern bool SILENT; diff --git a/utils/weights.h b/utils/weights.h index 920fdd75..0bd4c2d9 100644 --- a/utils/weights.h +++ b/utils/weights.h @@ -1,5 +1,5 @@ -#ifndef _WEIGHTS_H_ -#define _WEIGHTS_H_ +#ifndef WEIGHTS_H_ +#define WEIGHTS_H_ #include #include diff --git a/utils/wordid.h b/utils/wordid.h index 714dcd0b..3aa6cc23 100644 --- a/utils/wordid.h +++ b/utils/wordid.h @@ -1,5 +1,5 @@ -#ifndef _WORD_ID_H_ -#define _WORD_ID_H_ +#ifndef WORD_ID_H_ +#define WORD_ID_H_ #include -- cgit v1.2.3 From 8c0e4a5c1f168a419b3a236a94815c97164bddbc Mon Sep 17 00:00:00 2001 From: "Wu, Ke" Date: Sun, 12 Oct 2014 16:30:02 -0400 Subject: Cherry picked Mr.MIRA compatibility mode code --- decoder/decoder.cc | 39 ++++++++++++++++++++++++++++------- decoder/oracle_bleu.h | 37 +++++++++++++++++++++++++-------- utils/Makefile.am | 3 ++- utils/b64featvector.cc | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++ utils/b64featvector.h | 12 +++++++++++ 5 files changed, 130 insertions(+), 16 deletions(-) create mode 100644 utils/b64featvector.cc create mode 100644 utils/b64featvector.h (limited to 'utils') diff --git a/decoder/decoder.cc b/decoder/decoder.cc index c384c33f..93282576 100644 --- a/decoder/decoder.cc +++ b/decoder/decoder.cc @@ -17,6 +17,7 @@ namespace std { using std::tr1::unordered_map; } #include "fdict.h" #include "timing_stats.h" #include "verbose.h" +#include "b64featvector.h" #include "translator.h" #include "phrasebased_translator.h" @@ -195,7 +196,7 @@ struct DecoderImpl { } forest.PruneInsideOutside(beam_prune,density_prune,pm,false,1); if (!forestname.empty()) forestname=" "+forestname; - if (!SILENT) { + if (!SILENT) { forest_stats(forest," Pruned "+forestname+" forest",false,false); cerr << " Pruned "< > rng; int sample_max_trans; bool aligner_mode; - bool graphviz; + bool graphviz; bool joshua_viz; bool encode_b64; bool kbest; @@ -301,6 +302,7 @@ struct DecoderImpl { bool feature_expectations; // TODO Observer bool output_training_vector; // TODO Observer bool remove_intersected_rule_annotations; + bool mr_mira_compat; // Mr.MIRA compatibility mode. boost::scoped_ptr incremental; @@ -414,7 +416,8 @@ DecoderImpl::DecoderImpl(po::variables_map& conf, int argc, char** argv, istream ("vector_format",po::value()->default_value("b64"), "Sparse vector serialization format for feature expectations or gradients, includes (text or b64)") ("combine_size,C",po::value()->default_value(1), "When option -G is used, process this many sentence pairs before writing the gradient (1=emit after every sentence pair)") ("forest_output,O",po::value(),"Directory to write forests to") - ("remove_intersected_rule_annotations", "After forced decoding is completed, remove nonterminal annotations (i.e., the source side spans)"); + ("remove_intersected_rule_annotations", "After forced decoding is completed, remove nonterminal annotations (i.e., the source side spans)") + ("mr_mira_compat", "Mr.MIRA compatibility mode (applies weight delta if available; outputs number of lines before k-best)"); // ob.AddOptions(&opts); po::options_description clo("Command line options"); @@ -666,6 +669,7 @@ DecoderImpl::DecoderImpl(po::variables_map& conf, int argc, char** argv, istream get_oracle_forest = conf.count("get_oracle_forest"); oracle.show_derivation=conf.count("show_derivations"); remove_intersected_rule_annotations = conf.count("remove_intersected_rule_annotations"); + mr_mira_compat = conf.count("mr_mira_compat"); combine_size = conf["combine_size"].as(); if (combine_size < 1) combine_size = 1; @@ -699,6 +703,24 @@ void Decoder::AddSupplementalGrammarFromString(const std::string& grammar_string static_cast(*pimpl_->translator).AddSupplementalGrammarFromString(grammar_string); } +static inline void ApplyWeightDelta(const string &delta_b64, vector *weights) { + SparseVector delta; + DecodeFeatureVector(delta_b64, &delta); + if (delta.empty()) return; + // Apply updates + for (SparseVector::iterator dit = delta.begin(); + dit != delta.end(); ++dit) { + int feat_id = dit->first; + union { weight_t weight; unsigned long long repr; } feat_delta; + feat_delta.weight = dit->second; + if (!SILENT) + cerr << "[decoder weight update] " << FD::Convert(feat_id) << " " << feat_delta.weight + << " = " << hex << feat_delta.repr << endl; + if (weights->size() <= feat_id) weights->resize(feat_id + 1); + (*weights)[feat_id] += feat_delta.weight; + } +} + bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { string buf = input; NgramCache::Clear(); // clear ngram cache for remote LM (if used) @@ -709,6 +731,10 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { if (sgml.find("id") != sgml.end()) sent_id = atoi(sgml["id"].c_str()); + // Add delta from input to weights before decoding + if (mr_mira_compat) + ApplyWeightDelta(sgml["delta"], init_weights.get()); + if (!SILENT) { cerr << "\nINPUT: "; if (buf.size() < 100) @@ -947,7 +973,7 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { if (kbest && !has_ref) { //TODO: does this work properly? const string deriv_fname = conf.count("show_derivations") ? str("show_derivations",conf) : "-"; - oracle.DumpKBest(sent_id, forest, conf["k_best"].as(), unique_kbest,"-", deriv_fname); + oracle.DumpKBest(sent_id, forest, conf["k_best"].as(), unique_kbest,mr_mira_compat, smeta.GetSourceLength(), "-", deriv_fname); } else if (csplit_output_plf) { cout << HypergraphIO::AsPLF(forest, false) << endl; } else { @@ -1078,7 +1104,7 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { if (conf.count("graphviz")) forest.PrintGraphviz(); if (kbest) { const string deriv_fname = conf.count("show_derivations") ? str("show_derivations",conf) : "-"; - oracle.DumpKBest(sent_id, forest, conf["k_best"].as(), unique_kbest,"-", deriv_fname); + oracle.DumpKBest(sent_id, forest, conf["k_best"].as(), unique_kbest, mr_mira_compat, smeta.GetSourceLength(), "-", deriv_fname); } if (conf.count("show_conditional_prob")) { const prob_t ref_z = Inside(forest); @@ -1098,4 +1124,3 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { o->NotifyDecodingComplete(smeta); return true; } - diff --git a/decoder/oracle_bleu.h b/decoder/oracle_bleu.h index d2c4715c..75db61e8 100644 --- a/decoder/oracle_bleu.h +++ b/decoder/oracle_bleu.h @@ -21,6 +21,7 @@ #include "kbest.h" #include "timing_stats.h" #include "sentences.h" +#include "b64featvector.h" //TODO: put function impls into .cc //TODO: move Translation into its own .h and use in cdec @@ -253,18 +254,28 @@ struct OracleBleu { bool show_derivation; template - void kbest(int sent_id,Hypergraph const& forest,int k,std::ostream &kbest_out=std::cout,std::ostream &deriv_out=std::cerr) { + void kbest(int sent_id, Hypergraph const& forest, int k, bool mr_mira_compat, + int src_len, std::ostream& kbest_out = std::cout, + std::ostream& deriv_out = std::cerr) { using namespace std; using namespace boost; typedef KBest::KBestDerivations K; K kbest(forest,k); //add length (f side) src length of this sentence to the psuedo-doc src length count float curr_src_length = doc_src_length + tmp_src_length; - for (int i = 0; i < k; ++i) { + if (mr_mira_compat) kbest_out << k << "\n"; + int i = 0; + for (; i < k; ++i) { typename K::Derivation *d = kbest.LazyKthBest(forest.nodes_.size() - 1, i); if (!d) break; - kbest_out << sent_id << " ||| " << TD::GetString(d->yield) << " ||| " - << d->feature_values << " ||| " << log(d->score); + kbest_out << sent_id << " ||| "; + if (mr_mira_compat) kbest_out << src_len << " ||| "; + kbest_out << TD::GetString(d->yield) << " ||| "; + if (mr_mira_compat) + kbest_out << EncodeFeatureVector(d->feature_values); + else + kbest_out << d->feature_values; + kbest_out << " ||| " << log(d->score); if (!refs.empty()) { ScoreP sentscore = GetScore(d->yield,sent_id); sentscore->PlusEquals(*doc_score,float(1)); @@ -279,10 +290,17 @@ struct OracleBleu { deriv_out<<"\n"< > >(sent_id,forest,k,ko.get(),oderiv.get()); + kbest > >( + sent_id, forest, k, mr_mira_compat, src_len, ko.get(), oderiv.get()); else { - kbest(sent_id,forest,k,ko.get(),oderiv.get()); + kbest(sent_id, forest, k, mr_mira_compat, src_len, + ko.get(), oderiv.get()); } } @@ -305,7 +325,8 @@ void DumpKBest(std::string const& suffix,const int sent_id, const Hypergraph& fo { std::ostringstream kbest_string_stream; kbest_string_stream << forest_output << "/kbest_"< +#include +#include "b64tools.h" +#include "fdict.h" + +using namespace std; + +static inline void EncodeFeatureWeight(const string &featname, weight_t weight, + ostream *output) { + output->write(featname.data(), featname.size() + 1); + output->write(reinterpret_cast(&weight), sizeof(weight_t)); +} + +string EncodeFeatureVector(const SparseVector &vec) { + string b64; + { + ostringstream base64_strm; + { + ostringstream strm; + for (SparseVector::const_iterator it = vec.begin(); + it != vec.end(); ++it) + if (it->second != 0) + EncodeFeatureWeight(FD::Convert(it->first), it->second, &strm); + string data(strm.str()); + B64::b64encode(data.data(), data.size(), &base64_strm); + } + b64 = base64_strm.str(); + } + return b64; +} + +void DecodeFeatureVector(const string &data, SparseVector *vec) { + vec->clear(); + if (data.empty()) return; + // Decode data + size_t b64_len = data.size(), len = b64_len / 4 * 3; + boost::scoped_array buf(new char[len]); + bool res = + B64::b64decode(reinterpret_cast(data.data()), + b64_len, buf.get(), len); + assert(res); + // Apply updates + size_t cur = 0; + while (cur < len) { + string feat_name(buf.get() + cur); + if (feat_name.empty()) break; // Encountered trailing \0 + int feat_id = FD::Convert(feat_name); + weight_t feat_delta = + *reinterpret_cast(buf.get() + cur + feat_name.size() + 1); + (*vec)[feat_id] = feat_delta; + cur += feat_name.size() + 1 + sizeof(weight_t); + } +} diff --git a/utils/b64featvector.h b/utils/b64featvector.h new file mode 100644 index 00000000..6ac04d44 --- /dev/null +++ b/utils/b64featvector.h @@ -0,0 +1,12 @@ +#ifndef _B64FEATVECTOR_H_ +#define _B64FEATVECTOR_H_ + +#include + +#include "sparse_vector.h" +#include "weights.h" + +std::string EncodeFeatureVector(const SparseVector &); +void DecodeFeatureVector(const std::string &, SparseVector *); + +#endif // _B64FEATVECTOR_H_ -- cgit v1.2.3 From e0b225782a239c217da585001c12c4de169d8f0c Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Sat, 18 Oct 2014 21:46:49 -0400 Subject: test sparse vector serialization --- utils/sv_test.cc | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 'utils') diff --git a/utils/sv_test.cc b/utils/sv_test.cc index 67df8c57..b006e66d 100644 --- a/utils/sv_test.cc +++ b/utils/sv_test.cc @@ -1,7 +1,12 @@ #define BOOST_TEST_MODULE WeightsTest #include #include +#include +#include +#include +#include #include "sparse_vector.h" +#include "fdict.h" using namespace std; @@ -33,3 +38,29 @@ BOOST_AUTO_TEST_CASE(Division) { x /= -1; BOOST_CHECK(x == y); } + +BOOST_AUTO_TEST_CASE(Serialization) { + string arc; + FD::dict_.clear(); + { + SparseVector x; + x.set_value(FD::Convert("Feature1"), 1.0); + x.set_value(FD::Convert("Pi"), 3.14); + ostringstream os; + boost::archive::text_oarchive oa(os); + oa << x; + arc = os.str(); + } + FD::dict_.clear(); + FD::Convert("SomeNewString"); + { + SparseVector x; + istringstream is(arc); + boost::archive::text_iarchive ia(is); + ia >> x; + cerr << x << endl; + BOOST_CHECK_CLOSE(x.get(FD::Convert("Pi")), 3.14, 1e-9); + BOOST_CHECK_CLOSE(x.get(FD::Convert("Feature1")), 1.0, 1e-9); + } +} + -- cgit v1.2.3 From 2bb5f3f4c3c347a2474392993c17cc62653dd133 Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Sun, 19 Oct 2014 05:24:21 -0400 Subject: stop switch to boost serialization for hypergraph IO --- decoder/decoder.cc | 4 +- decoder/forest_writer.cc | 4 +- decoder/hg.h | 52 +++++++++++ decoder/hg_io.cc | 101 +++------------------ decoder/hg_io.h | 5 +- decoder/hg_test.cc | 39 +++++--- decoder/rule_lexer.ll | 1 + python/cdec/hypergraph.pxd | 3 +- training/dpmert/mr_dpmert_generate_mapper_input.cc | 2 +- training/dpmert/mr_dpmert_map.cc | 4 +- training/minrisk/minrisk_optimize.cc | 2 +- training/pro/mr_pro_map.cc | 2 +- training/rampion/rampion_cccp.cc | 2 +- training/utils/grammar_convert.cc | 5 +- utils/small_vector.h | 16 ++++ utils/small_vector_test.cc | 30 ++++++ 16 files changed, 156 insertions(+), 116 deletions(-) (limited to 'utils') diff --git a/decoder/decoder.cc b/decoder/decoder.cc index 3cc77d27..f8214f5f 100644 --- a/decoder/decoder.cc +++ b/decoder/decoder.cc @@ -930,7 +930,7 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { Hypergraph new_hg; { ReadFile rf(writer.fname_); - bool succeeded = HypergraphIO::ReadFromJSON(rf.stream(), &new_hg); + bool succeeded = HypergraphIO::ReadFromBinary(rf.stream(), &new_hg); if (!succeeded) abort(); } HG::Union(forest, &new_hg); @@ -1023,7 +1023,7 @@ bool DecoderImpl::Decode(const string& input, DecoderObserver* o) { Hypergraph new_hg; { ReadFile rf(writer.fname_); - bool succeeded = HypergraphIO::ReadFromJSON(rf.stream(), &new_hg); + bool succeeded = HypergraphIO::ReadFromBinary(rf.stream(), &new_hg); if (!succeeded) abort(); } HG::Union(forest, &new_hg); diff --git a/decoder/forest_writer.cc b/decoder/forest_writer.cc index 6e4cccb3..c072e599 100644 --- a/decoder/forest_writer.cc +++ b/decoder/forest_writer.cc @@ -11,13 +11,13 @@ using namespace std; ForestWriter::ForestWriter(const std::string& path, int num) : - fname_(path + '/' + boost::lexical_cast(num) + ".json.gz"), used_(false) {} + fname_(path + '/' + boost::lexical_cast(num) + ".bin.gz"), used_(false) {} bool ForestWriter::Write(const Hypergraph& forest, bool minimal_rules) { assert(!used_); used_ = true; cerr << " Writing forest to " << fname_ << endl; WriteFile wf(fname_); - return HypergraphIO::WriteToJSON(forest, minimal_rules, wf.stream()); + return HypergraphIO::WriteToBinary(forest, wf.stream()); } diff --git a/decoder/hg.h b/decoder/hg.h index 256f650f..124eab86 100644 --- a/decoder/hg.h +++ b/decoder/hg.h @@ -18,6 +18,7 @@ #include #include #include +#include #include "feature_vector.h" #include "small_vector.h" @@ -69,6 +70,18 @@ namespace HG { short int j_; short int prev_i_; short int prev_j_; + template + void serialize(Archive & ar, const unsigned int version) { + ar & head_node_; + ar & tail_nodes_; + ar & rule_; + ar & feature_values_; + ar & i_; + ar & j_; + ar & prev_i_; + ar & prev_j_; + ar & id_; + } void show(std::ostream &o,unsigned mask=SPAN|RULE) const { o<<'{'; if (mask&CATEGORY) @@ -149,6 +162,24 @@ namespace HG { WordID NT() const { return -cat_; } EdgesVector in_edges_; // an in edge is an edge with this node as its head. (in edges come from the bottom up to us) indices in edges_ EdgesVector out_edges_; // an out edge is an edge with this node as its tail. (out edges leave us up toward the top/goal). indices in edges_ + template + void save(Archive & ar, const unsigned int version) const { + ar & node_hash; + ar & id_; + ar & TD::Convert(-cat_); + ar & in_edges_; + ar & out_edges_; + } + template + void load(Archive & ar, const unsigned int version) { + ar & node_hash; + ar & id_; + std::string cat; ar & cat; + cat_ = -TD::Convert(cat); + ar & in_edges_; + ar & out_edges_; + } + BOOST_SERIALIZATION_SPLIT_MEMBER() void copy_fixed(Node const& o) { // nonstructural fields only - structural ones are managed by sorting/pruning/subsetting node_hash = o.node_hash; cat_=o.cat_; @@ -492,6 +523,27 @@ public: void set_ids(); // resync edge,node .id_ void check_ids() const; // assert that .id_ have been kept in sync + template + void save(Archive & ar, const unsigned int version) const { + unsigned ns = nodes_.size(); ar & ns; + unsigned es = edges_.size(); ar & es; + for (auto& n : nodes_) ar & n; + for (auto& e : edges_) ar & e; + int x; + x = edges_topo_; ar & x; + x = is_linear_chain_; ar & x; + } + template + void load(Archive & ar, const unsigned int version) { + unsigned ns; ar & ns; nodes_.resize(ns); + unsigned es; ar & es; edges_.resize(es); + for (auto& n : nodes_) ar & n; + for (auto& e : edges_) ar & e; + int x; + ar & x; edges_topo_ = x; + ar & x; is_linear_chain_ = x; + } + BOOST_SERIALIZATION_SPLIT_MEMBER() private: Hypergraph(int num_nodes, int num_edges, bool is_lc) : is_linear_chain_(is_lc), nodes_(num_nodes), edges_(num_edges),edges_topo_(true) {} }; diff --git a/decoder/hg_io.cc b/decoder/hg_io.cc index eb0be3d4..67760fb1 100644 --- a/decoder/hg_io.cc +++ b/decoder/hg_io.cc @@ -6,6 +6,10 @@ #include #include +#include +#include +#include + #include "fast_lexical_cast.hpp" #include "tdict.h" @@ -271,97 +275,16 @@ bool HypergraphIO::ReadFromJSON(istream* in, Hypergraph* hg) { return reader.Parse(in); } -static void WriteRule(const TRule& r, ostream* out) { - if (!r.lhs_) { (*out) << "[X] ||| "; } - JSONParser::WriteEscapedString(r.AsString(), out); +bool HypergraphIO::ReadFromBinary(istream* in, Hypergraph* hg) { + boost::archive::binary_iarchive oa(*in); + hg->clear(); + oa >> *hg; + return true; } -bool HypergraphIO::WriteToJSON(const Hypergraph& hg, bool remove_rules, ostream* out) { - if (hg.empty()) { *out << "{}\n"; return true; } - map rid; - ostream& o = *out; - rid[NULL] = 0; - o << '{'; - if (!remove_rules) { - o << "\"rules\":["; - for (int i = 0; i < hg.edges_.size(); ++i) { - const TRule* r = hg.edges_[i].rule_.get(); - int &id = rid[r]; - if (!id) { - id=rid.size() - 1; - if (id > 1) o << ','; - o << id << ','; - WriteRule(*r, &o); - }; - } - o << "],"; - } - const bool use_fdict = FD::NumFeats() < 1000; - if (use_fdict) { - o << "\"features\":["; - for (int i = 1; i < FD::NumFeats(); ++i) { - o << (i==1 ? "":","); - JSONParser::WriteEscapedString(FD::Convert(i), &o); - } - o << "],"; - } - vector edgemap(hg.edges_.size(), -1); // edges may be in non-topo order - int edge_count = 0; - for (int i = 0; i < hg.nodes_.size(); ++i) { - const Hypergraph::Node& node = hg.nodes_[i]; - if (i > 0) { o << ","; } - o << "\"edges\":["; - for (int j = 0; j < node.in_edges_.size(); ++j) { - const Hypergraph::Edge& edge = hg.edges_[node.in_edges_[j]]; - edgemap[edge.id_] = edge_count; - ++edge_count; - o << (j == 0 ? "" : ",") << "{"; - - o << "\"tail\":["; - for (int k = 0; k < edge.tail_nodes_.size(); ++k) { - o << (k > 0 ? "," : "") << edge.tail_nodes_[k]; - } - o << "],"; - - o << "\"spans\":[" << edge.i_ << "," << edge.j_ << "," << edge.prev_i_ << "," << edge.prev_j_ << "],"; - - o << "\"feats\":["; - bool first = true; - for (SparseVector::const_iterator it = edge.feature_values_.begin(); it != edge.feature_values_.end(); ++it) { - if (!it->second) continue; // don't write features that have a zero value - if (!it->first) continue; // if the feature set was frozen this might happen - if (!first) o << ','; - if (use_fdict) - o << (it->first - 1); - else { - JSONParser::WriteEscapedString(FD::Convert(it->first), &o); - } - o << ',' << it->second; - first = false; - } - o << "]"; - if (!remove_rules) { o << ",\"rule\":" << rid[edge.rule_.get()]; } - o << "}"; - } - o << "],"; - - o << "\"node\":{\"in_edges\":["; - for (int j = 0; j < node.in_edges_.size(); ++j) { - int mapped_edge = edgemap[node.in_edges_[j]]; - assert(mapped_edge >= 0); - o << (j == 0 ? "" : ",") << mapped_edge; - } - o << "]"; - if (node.cat_ < 0) { - o << ",\"cat\":"; - JSONParser::WriteEscapedString(TD::Convert(node.cat_ * -1), &o); - } - char buf[48]; - sprintf(buf, "%016lX", node.node_hash); - o << ",\"node_hash\":\"" << buf << "\""; - o << "}"; - } - o << "}\n"; +bool HypergraphIO::WriteToBinary(const Hypergraph& hg, ostream* out) { + boost::archive::binary_oarchive oa(*out); + oa << hg; return true; } diff --git a/decoder/hg_io.h b/decoder/hg_io.h index 5a2bd808..5ba86f69 100644 --- a/decoder/hg_io.h +++ b/decoder/hg_io.h @@ -18,10 +18,11 @@ struct HypergraphIO { // see test_data/small.json.gz for an email encoding static bool ReadFromJSON(std::istream* in, Hypergraph* out); + static bool ReadFromBinary(std::istream* in, Hypergraph* out); + static bool WriteToBinary(const Hypergraph& hg, std::ostream* out); + // if remove_rules is used, the hypergraph is serialized without rule information // (so it only contains structure and feature information) - static bool WriteToJSON(const Hypergraph& hg, bool remove_rules, std::ostream* out); - static void WriteAsCFG(const Hypergraph& hg); // Write only the target size information in bottom-up order. diff --git a/decoder/hg_test.cc b/decoder/hg_test.cc index 5cb8626a..25eddcec 100644 --- a/decoder/hg_test.cc +++ b/decoder/hg_test.cc @@ -1,6 +1,11 @@ #define BOOST_TEST_MODULE hg_test #include #include +#include +#include +#include +#include +#include #include #include "tdict.h" @@ -427,19 +432,29 @@ BOOST_AUTO_TEST_CASE(TestGenericKBest) { } } -BOOST_AUTO_TEST_CASE(TestReadWriteHG) { +BOOST_AUTO_TEST_CASE(TestReadWriteHG_Boost) { std::string path(boost::unit_test::framework::master_test_suite().argc == 2 ? boost::unit_test::framework::master_test_suite().argv[1] : TEST_DATA); - Hypergraph hg,hg2; - CreateHG(path, &hg); - hg.edges_.front().j_ = 23; - hg.edges_.back().prev_i_ = 99; - ostringstream os; - HypergraphIO::WriteToJSON(hg, false, &os); - istringstream is(os.str()); - HypergraphIO::ReadFromJSON(&is, &hg2); - BOOST_CHECK_EQUAL(hg2.NumberOfPaths(), hg.NumberOfPaths()); - BOOST_CHECK_EQUAL(hg2.edges_.front().j_, 23); - BOOST_CHECK_EQUAL(hg2.edges_.back().prev_i_, 99); + Hypergraph hg; + Hypergraph hg2; + std::string out; + { + CreateHG(path, &hg); + hg.edges_.front().j_ = 23; + hg.edges_.back().prev_i_ = 99; + ostringstream os; + boost::archive::text_oarchive oa(os); + oa << hg; + out = os.str(); + } + { + cerr << out << endl; + istringstream is(out); + boost::archive::text_iarchive ia(is); + ia >> hg2; + BOOST_CHECK_EQUAL(hg2.NumberOfPaths(), hg.NumberOfPaths()); + BOOST_CHECK_EQUAL(hg2.edges_.front().j_, 23); + BOOST_CHECK_EQUAL(hg2.edges_.back().prev_i_, 99); + } } BOOST_AUTO_TEST_SUITE_END() diff --git a/decoder/rule_lexer.ll b/decoder/rule_lexer.ll index d4a8d86b..8b48ab7b 100644 --- a/decoder/rule_lexer.ll +++ b/decoder/rule_lexer.ll @@ -356,6 +356,7 @@ void RuleLexer::ReadRules(std::istream* in, RuleLexer::RuleCallback func, const void RuleLexer::ReadRule(const std::string& srule, RuleCallback func, bool mono, void* extra) { init_default_feature_names(); + scfglex_fname = srule; lex_mono_rules = mono; lex_line = 1; rule_callback_extra = extra; diff --git a/python/cdec/hypergraph.pxd b/python/cdec/hypergraph.pxd index 1e150bbc..9780cf8b 100644 --- a/python/cdec/hypergraph.pxd +++ b/python/cdec/hypergraph.pxd @@ -63,7 +63,8 @@ cdef extern from "decoder/viterbi.h": cdef extern from "decoder/hg_io.h" namespace "HypergraphIO": # Hypergraph JSON I/O bint ReadFromJSON(istream* inp, Hypergraph* out) - bint WriteToJSON(Hypergraph& hg, bint remove_rules, ostream* out) + bint ReadFromBinary(istream* inp, Hypergraph* out) + bint WriteToBinary(Hypergraph& hg, ostream* out) # Hypergraph PLF I/O void ReadFromPLF(string& inp, Hypergraph* out) string AsPLF(Hypergraph& hg, bint include_global_parentheses) diff --git a/training/dpmert/mr_dpmert_generate_mapper_input.cc b/training/dpmert/mr_dpmert_generate_mapper_input.cc index 199cd23a..3fa2f476 100644 --- a/training/dpmert/mr_dpmert_generate_mapper_input.cc +++ b/training/dpmert/mr_dpmert_generate_mapper_input.cc @@ -70,7 +70,7 @@ int main(int argc, char** argv) { unsigned dev_set_size = conf["dev_set_size"].as(); for (unsigned i = 0; i < dev_set_size; ++i) { for (unsigned j = 0; j < directions.size(); ++j) { - cout << forest_repository << '/' << i << ".json.gz " << i << ' '; + cout << forest_repository << '/' << i << ".bin.gz " << i << ' '; print(cout, origin, "=", ";"); cout << ' '; print(cout, directions[j], "=", ";"); diff --git a/training/dpmert/mr_dpmert_map.cc b/training/dpmert/mr_dpmert_map.cc index d1efcf96..2bf3f8fc 100644 --- a/training/dpmert/mr_dpmert_map.cc +++ b/training/dpmert/mr_dpmert_map.cc @@ -83,7 +83,7 @@ int main(int argc, char** argv) { istringstream is(line); int sent_id; string file, s_origin, s_direction; - // path-to-file (JSON) sent_ed starting-point search-direction + // path-to-file sent_ed starting-point search-direction is >> file >> sent_id >> s_origin >> s_direction; SparseVector origin; ReadSparseVectorString(s_origin, &origin); @@ -93,7 +93,7 @@ int main(int argc, char** argv) { if (last_file != file) { last_file = file; ReadFile rf(file); - HypergraphIO::ReadFromJSON(rf.stream(), &hg); + HypergraphIO::ReadFromBinary(rf.stream(), &hg); } const ConvexHullWeightFunction wf(origin, direction); const ConvexHull hull = Inside(hg, NULL, wf); diff --git a/training/minrisk/minrisk_optimize.cc b/training/minrisk/minrisk_optimize.cc index da8b5260..a2938fb0 100644 --- a/training/minrisk/minrisk_optimize.cc +++ b/training/minrisk/minrisk_optimize.cc @@ -178,7 +178,7 @@ int main(int argc, char** argv) { ReadFile rf(file); if (kis.size() % 5 == 0) { cerr << '.'; } if (kis.size() % 200 == 0) { cerr << " [" << kis.size() << "]\n"; } - HypergraphIO::ReadFromJSON(rf.stream(), &hg); + HypergraphIO::ReadFromBinary(rf.stream(), &hg); hg.Reweight(weights); curkbest.AddKBestCandidates(hg, kbest_size, ds[sent_id]); if (kbest_file.size()) diff --git a/training/pro/mr_pro_map.cc b/training/pro/mr_pro_map.cc index da58cd24..b142fd05 100644 --- a/training/pro/mr_pro_map.cc +++ b/training/pro/mr_pro_map.cc @@ -203,7 +203,7 @@ int main(int argc, char** argv) { const string kbest_file = os.str(); if (FileExists(kbest_file)) J_i.ReadFromFile(kbest_file); - HypergraphIO::ReadFromJSON(rf.stream(), &hg); + HypergraphIO::ReadFromBinary(rf.stream(), &hg); hg.Reweight(weights); J_i.AddKBestCandidates(hg, kbest_size, ds[sent_id]); J_i.WriteToFile(kbest_file); diff --git a/training/rampion/rampion_cccp.cc b/training/rampion/rampion_cccp.cc index 1e36dc51..1c45bac5 100644 --- a/training/rampion/rampion_cccp.cc +++ b/training/rampion/rampion_cccp.cc @@ -136,7 +136,7 @@ int main(int argc, char** argv) { ReadFile rf(file); if (kis.size() % 5 == 0) { cerr << '.'; } if (kis.size() % 200 == 0) { cerr << " [" << kis.size() << "]\n"; } - HypergraphIO::ReadFromJSON(rf.stream(), &hg); + HypergraphIO::ReadFromBinary(rf.stream(), &hg); hg.Reweight(weights); curkbest.AddKBestCandidates(hg, kbest_size, ds[sent_id]); if (kbest_file.size()) diff --git a/training/utils/grammar_convert.cc b/training/utils/grammar_convert.cc index 5c1b4d4a..000f2a26 100644 --- a/training/utils/grammar_convert.cc +++ b/training/utils/grammar_convert.cc @@ -43,7 +43,7 @@ void InitCommandLine(int argc, char** argv, po::variables_map* conf) { po::notify(*conf); if (conf->count("help") || conf->count("input") == 0) { - cerr << "\nUsage: grammar_convert [-options]\n\nConverts a grammar file (in Hiero format) into JSON hypergraph.\n"; + cerr << "\nUsage: grammar_convert [-options]\n\nConverts a grammar file (in Hiero format) into serialized hypergraph.\n"; cerr << dcmdline_options << endl; exit(1); } @@ -254,7 +254,8 @@ void ProcessHypergraph(const vector& w, const po::variables_map& conf, c if (w.size() > 0) { hg->Reweight(w); } if (conf.count("collapse_weights")) CollapseWeights(hg); if (conf["output"].as() == "json") { - HypergraphIO::WriteToJSON(*hg, false, &cout); + cerr << "NOT IMPLEMENTED ... talk to cdyer if you need this functionality\n"; + // HypergraphIO::WriteToBinary(*hg, &cout); if (!ref.empty()) { cerr << "REF: " << ref << endl; } } else { vector onebest; diff --git a/utils/small_vector.h b/utils/small_vector.h index c8cbcb2c..f16bc898 100644 --- a/utils/small_vector.h +++ b/utils/small_vector.h @@ -15,6 +15,7 @@ #include #include #include +#include //sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1 @@ -297,6 +298,21 @@ public: return hash_range(data_.ptr,data_.ptr+size_); } + template + void save(Archive & ar, const unsigned int) const { + ar & size_; + for (unsigned i = 0; i < size_; ++i) + ar & (*this)[i]; + } + template + void load(Archive & ar, const unsigned int) { + uint16_t s; + ar & s; + this->resize(s); + for (unsigned i = 0; i < size_; ++i) + ar & (*this)[i]; + } + BOOST_SERIALIZATION_SPLIT_MEMBER() private: union StorageType { T vals[SV_MAX]; diff --git a/utils/small_vector_test.cc b/utils/small_vector_test.cc index a4eb89ae..9e1a148d 100644 --- a/utils/small_vector_test.cc +++ b/utils/small_vector_test.cc @@ -3,6 +3,10 @@ #define BOOST_TEST_MODULE svTest #include #include +#include +#include +#include +#include #include #include @@ -128,3 +132,29 @@ BOOST_AUTO_TEST_CASE(Small) { cerr << sizeof(SmallVectorInt) << endl; cerr << sizeof(vector) << endl; } + +BOOST_AUTO_TEST_CASE(Serialize) { + std::string in; + { + SmallVectorInt v; + v.push_back(0); + v.push_back(1); + v.push_back(-2); + ostringstream os; + boost::archive::text_oarchive oa(os); + oa << v; + in = os.str(); + cerr << in; + } + { + istringstream is(in); + boost::archive::text_iarchive ia(is); + SmallVectorInt v; + ia >> v; + BOOST_CHECK_EQUAL(v.size(), 3); + BOOST_CHECK_EQUAL(v[0], 0); + BOOST_CHECK_EQUAL(v[1], 1); + BOOST_CHECK_EQUAL(v[2], -2); + } +} + -- cgit v1.2.3 From b6dd5a683db9dda2d634dd2fdb76606819594901 Mon Sep 17 00:00:00 2001 From: "Wu, Ke" Date: Wed, 17 Dec 2014 16:00:04 -0500 Subject: Combine everything related to maxent to a single file --- decoder/ff_const_reorder_common.h | 6 +- training/const_reorder/trainer.cc | 4 +- utils/Makefile.am | 5 - utils/lbfgs.cpp | 108 ---------- utils/lbfgs.h | 20 -- utils/mathvec.h | 87 -------- utils/maxent.cpp | 427 +++++++++++++++++++++++++++++++++++++- utils/maxent.h | 95 ++++++++- utils/owlqn.cpp | 127 ------------ utils/sgd.cpp | 193 ----------------- 10 files changed, 516 insertions(+), 556 deletions(-) delete mode 100644 utils/lbfgs.cpp delete mode 100644 utils/lbfgs.h delete mode 100644 utils/mathvec.h delete mode 100644 utils/owlqn.cpp delete mode 100644 utils/sgd.cpp (limited to 'utils') diff --git a/decoder/ff_const_reorder_common.h b/decoder/ff_const_reorder_common.h index b124ce47..755fd948 100644 --- a/decoder/ff_const_reorder_common.h +++ b/decoder/ff_const_reorder_common.h @@ -1081,7 +1081,7 @@ typedef std::unordered_map::iterator Iterator; struct Tsuruoka_Maxent { Tsuruoka_Maxent(const char* pszModelFName) { if (pszModelFName != NULL) { - m_pModel = new ME_Model(); + m_pModel = new maxent::ME_Model(); m_pModel->load_from_file(pszModelFName); } else m_pModel = NULL; @@ -1093,7 +1093,7 @@ struct Tsuruoka_Maxent { void fnEval(const char* pszContext, std::vector& vecOutput) const { std::vector vecContext; - ME_Sample* pmes = new ME_Sample(); + maxent::ME_Sample* pmes = new maxent::ME_Sample(); SplitOnWhitespace(std::string(pszContext), &vecContext); vecOutput.clear(); @@ -1113,7 +1113,7 @@ struct Tsuruoka_Maxent { } private: - ME_Model* m_pModel; + maxent::ME_Model* m_pModel; }; // an argument item or a predicate item (the verb itself) diff --git a/training/const_reorder/trainer.cc b/training/const_reorder/trainer.cc index e22a8a66..89bd7479 100644 --- a/training/const_reorder/trainer.cc +++ b/training/const_reorder/trainer.cc @@ -10,7 +10,7 @@ void Tsuruoka_Maxent_Trainer::fnTrain(const char* pszInstanceFName, strcmp(pszAlgorithm, "sgd") == 0 || strcmp(pszAlgorithm, "SGD") == 0); FILE* fpIn = fopen(pszInstanceFName, "r"); - ME_Model* pModel = new ME_Model(); + maxent::ME_Model* pModel = new maxent::ME_Model(); char* pszLine = new char[100001]; int iNumInstances = 0; @@ -30,7 +30,7 @@ void Tsuruoka_Maxent_Trainer::fnTrain(const char* pszInstanceFName, iNumInstances++; - ME_Sample* pmes = new ME_Sample(); + maxent::ME_Sample* pmes = new maxent::ME_Sample(); char* p = strrchr(pszLine, ' '); assert(p != NULL); diff --git a/utils/Makefile.am b/utils/Makefile.am index fabb4454..e0221e64 100644 --- a/utils/Makefile.am +++ b/utils/Makefile.am @@ -38,11 +38,8 @@ libutils_a_SOURCES = \ have_64_bits.h \ indices_after.h \ kernel_string_subseq.h \ - lbfgs.h \ - lbfgs.cpp \ logval.h \ m.h \ - mathvec.h \ maxent.h \ maxent.cpp \ murmur_hash3.h \ @@ -50,8 +47,6 @@ libutils_a_SOURCES = \ named_enum.h \ null_deleter.h \ null_traits.h \ - owlqn.cpp \ - sgd.cpp \ perfect_hash.h \ prob.h \ sampler.h \ diff --git a/utils/lbfgs.cpp b/utils/lbfgs.cpp deleted file mode 100644 index bd26f048..00000000 --- a/utils/lbfgs.cpp +++ /dev/null @@ -1,108 +0,0 @@ -#include -#include -#include -#include -#include "mathvec.h" -#include "lbfgs.h" -#include "maxent.h" - -using namespace std; - -const static int M = LBFGS_M; -const static double LINE_SEARCH_ALPHA = 0.1; -const static double LINE_SEARCH_BETA = 0.5; - -// stopping criteria -int LBFGS_MAX_ITER = 300; -const static double MIN_GRAD_NORM = 0.0001; - -double ME_Model::backtracking_line_search(const Vec& x0, const Vec& grad0, - const double f0, const Vec& dx, - Vec& x, Vec& grad1) { - double t = 1.0 / LINE_SEARCH_BETA; - - double f; - do { - t *= LINE_SEARCH_BETA; - x = x0 + t * dx; - f = FunctionGradient(x.STLVec(), grad1.STLVec()); - // cout << "*"; - } while (f > f0 + LINE_SEARCH_ALPHA * t * dot_product(dx, grad0)); - - return f; -} - -// -// Jorge Nocedal, "Updating Quasi-Newton Matrices With Limited Storage", -// Mathematics of Computation, Vol. 35, No. 151, pp. 773-782, 1980. -// -Vec approximate_Hg(const int iter, const Vec& grad, const Vec s[], - const Vec y[], const double z[]) { - int offset, bound; - if (iter <= M) { - offset = 0; - bound = iter; - } else { - offset = iter - M; - bound = M; - } - - Vec q = grad; - double alpha[M], beta[M]; - for (int i = bound - 1; i >= 0; i--) { - const int j = (i + offset) % M; - alpha[i] = z[j] * dot_product(s[j], q); - q += -alpha[i] * y[j]; - } - if (iter > 0) { - const int j = (iter - 1) % M; - const double gamma = ((1.0 / z[j]) / dot_product(y[j], y[j])); - // static double gamma; - // if (gamma == 0) gamma = ((1.0 / z[j]) / dot_product(y[j], y[j])); - q *= gamma; - } - for (int i = 0; i <= bound - 1; i++) { - const int j = (i + offset) % M; - beta[i] = z[j] * dot_product(y[j], q); - q += s[j] * (alpha[i] - beta[i]); - } - - return q; -} - -vector ME_Model::perform_LBFGS(const vector& x0) { - const size_t dim = x0.size(); - Vec x = x0; - - Vec grad(dim), dx(dim); - double f = FunctionGradient(x.STLVec(), grad.STLVec()); - - Vec s[M], y[M]; - double z[M]; // rho - - for (int iter = 0; iter < LBFGS_MAX_ITER; iter++) { - - fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, -f, _train_error); - if (_nheldout > 0) { - const double heldout_logl = heldout_likelihood(); - fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, - _heldout_error); - } - fprintf(stderr, "\n"); - - if (sqrt(dot_product(grad, grad)) < MIN_GRAD_NORM) break; - - dx = -1 * approximate_Hg(iter, grad, s, y, z); - - Vec x1(dim), grad1(dim); - f = backtracking_line_search(x, grad, f, dx, x1, grad1); - - s[iter % M] = x1 - x; - y[iter % M] = grad1 - grad; - z[iter % M] = 1.0 / dot_product(y[iter % M], s[iter % M]); - x = x1; - grad = grad1; - } - - return x.STLVec(); -} diff --git a/utils/lbfgs.h b/utils/lbfgs.h deleted file mode 100644 index 4d706f7a..00000000 --- a/utils/lbfgs.h +++ /dev/null @@ -1,20 +0,0 @@ -#ifndef _LBFGS_H_ -#define _LBFGS_H_ - -#include - -// template -// std::vector -// perform_LBFGS(FuncGrad func_grad, const std::vector & x0); - -std::vector perform_LBFGS( - double (*func_grad)(const std::vector &, std::vector &), - const std::vector &x0); - -std::vector perform_OWLQN( - double (*func_grad)(const std::vector &, std::vector &), - const std::vector &x0, const double C); - -const int LBFGS_M = 10; - -#endif diff --git a/utils/mathvec.h b/utils/mathvec.h deleted file mode 100644 index f8c60e5d..00000000 --- a/utils/mathvec.h +++ /dev/null @@ -1,87 +0,0 @@ -#ifndef _MATH_VECTOR_H_ -#define _MATH_VECTOR_H_ - -#include -#include -#include - -class Vec { - private: - std::vector _v; - - public: - Vec(const size_t n = 0, const double val = 0) { _v.resize(n, val); } - Vec(const std::vector& v) : _v(v) {} - const std::vector& STLVec() const { return _v; } - std::vector& STLVec() { return _v; } - size_t Size() const { return _v.size(); } - double& operator[](int i) { return _v[i]; } - const double& operator[](int i) const { return _v[i]; } - Vec& operator+=(const Vec& b) { - assert(b.Size() == _v.size()); - for (size_t i = 0; i < _v.size(); i++) { - _v[i] += b[i]; - } - return *this; - } - Vec& operator*=(const double c) { - for (size_t i = 0; i < _v.size(); i++) { - _v[i] *= c; - } - return *this; - } - void Project(const Vec& y) { - for (size_t i = 0; i < _v.size(); i++) { - // if (sign(_v[i]) != sign(y[i])) _v[i] = 0; - if (_v[i] * y[i] <= 0) _v[i] = 0; - } - } -}; - -inline double dot_product(const Vec& a, const Vec& b) { - double sum = 0; - for (size_t i = 0; i < a.Size(); i++) { - sum += a[i] * b[i]; - } - return sum; -} - -inline std::ostream& operator<<(std::ostream& s, const Vec& a) { - s << "("; - for (size_t i = 0; i < a.Size(); i++) { - if (i != 0) s << ", "; - s << a[i]; - } - s << ")"; - return s; -} - -inline const Vec operator+(const Vec& a, const Vec& b) { - Vec v(a.Size()); - assert(a.Size() == b.Size()); - for (size_t i = 0; i < a.Size(); i++) { - v[i] = a[i] + b[i]; - } - return v; -} - -inline const Vec operator-(const Vec& a, const Vec& b) { - Vec v(a.Size()); - assert(a.Size() == b.Size()); - for (size_t i = 0; i < a.Size(); i++) { - v[i] = a[i] - b[i]; - } - return v; -} - -inline const Vec operator*(const Vec& a, const double c) { - Vec v(a.Size()); - for (size_t i = 0; i < a.Size(); i++) { - v[i] = a[i] * c; - } - return v; -} - -inline const Vec operator*(const double c, const Vec& a) { return a * c; } - -#endif diff --git a/utils/maxent.cpp b/utils/maxent.cpp index 0f49ee9d..fd772e08 100644 --- a/utils/maxent.cpp +++ b/utils/maxent.cpp @@ -3,12 +3,15 @@ */ #include "maxent.h" + +#include +#include #include #include -#include "lbfgs.h" using namespace std; +namespace maxent { double ME_Model::FunctionGradient(const vector& x, vector& grad) { assert((int)_fb.Size() == x.size()); @@ -601,6 +604,428 @@ vector ME_Model::classify(ME_Sample& mes) const { return vp; } +// template +// std::vector +// perform_LBFGS(FuncGrad func_grad, const std::vector & x0); + +std::vector perform_LBFGS( + double (*func_grad)(const std::vector &, std::vector &), + const std::vector &x0); + +std::vector perform_OWLQN( + double (*func_grad)(const std::vector &, std::vector &), + const std::vector &x0, const double C); + +const int LBFGS_M = 10; + +const static int M = LBFGS_M; +const static double LINE_SEARCH_ALPHA = 0.1; +const static double LINE_SEARCH_BETA = 0.5; + +// stopping criteria +int LBFGS_MAX_ITER = 300; +const static double MIN_GRAD_NORM = 0.0001; + +// LBFGS + +double ME_Model::backtracking_line_search(const Vec& x0, const Vec& grad0, + const double f0, const Vec& dx, + Vec& x, Vec& grad1) { + double t = 1.0 / LINE_SEARCH_BETA; + + double f; + do { + t *= LINE_SEARCH_BETA; + x = x0 + t * dx; + f = FunctionGradient(x.STLVec(), grad1.STLVec()); + // cout << "*"; + } while (f > f0 + LINE_SEARCH_ALPHA * t * dot_product(dx, grad0)); + + return f; +} + +// +// Jorge Nocedal, "Updating Quasi-Newton Matrices With Limited Storage", +// Mathematics of Computation, Vol. 35, No. 151, pp. 773-782, 1980. +// +Vec approximate_Hg(const int iter, const Vec& grad, const Vec s[], + const Vec y[], const double z[]) { + int offset, bound; + if (iter <= M) { + offset = 0; + bound = iter; + } else { + offset = iter - M; + bound = M; + } + + Vec q = grad; + double alpha[M], beta[M]; + for (int i = bound - 1; i >= 0; i--) { + const int j = (i + offset) % M; + alpha[i] = z[j] * dot_product(s[j], q); + q += -alpha[i] * y[j]; + } + if (iter > 0) { + const int j = (iter - 1) % M; + const double gamma = ((1.0 / z[j]) / dot_product(y[j], y[j])); + // static double gamma; + // if (gamma == 0) gamma = ((1.0 / z[j]) / dot_product(y[j], y[j])); + q *= gamma; + } + for (int i = 0; i <= bound - 1; i++) { + const int j = (i + offset) % M; + beta[i] = z[j] * dot_product(y[j], q); + q += s[j] * (alpha[i] - beta[i]); + } + + return q; +} + +vector ME_Model::perform_LBFGS(const vector& x0) { + const size_t dim = x0.size(); + Vec x = x0; + + Vec grad(dim), dx(dim); + double f = FunctionGradient(x.STLVec(), grad.STLVec()); + + Vec s[M], y[M]; + double z[M]; // rho + + for (int iter = 0; iter < LBFGS_MAX_ITER; iter++) { + + fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, -f, _train_error); + if (_nheldout > 0) { + const double heldout_logl = heldout_likelihood(); + fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, + _heldout_error); + } + fprintf(stderr, "\n"); + + if (sqrt(dot_product(grad, grad)) < MIN_GRAD_NORM) break; + + dx = -1 * approximate_Hg(iter, grad, s, y, z); + + Vec x1(dim), grad1(dim); + f = backtracking_line_search(x, grad, f, dx, x1, grad1); + + s[iter % M] = x1 - x; + y[iter % M] = grad1 - grad; + z[iter % M] = 1.0 / dot_product(y[iter % M], s[iter % M]); + x = x1; + grad = grad1; + } + + return x.STLVec(); +} + +// OWLQN + +// stopping criteria +int OWLQN_MAX_ITER = 300; + +Vec approximate_Hg(const int iter, const Vec& grad, const Vec s[], + const Vec y[], const double z[]); + +inline int sign(double x) { + if (x > 0) return 1; + if (x < 0) return -1; + return 0; +}; + +static Vec pseudo_gradient(const Vec& x, const Vec& grad0, const double C) { + Vec grad = grad0; + for (size_t i = 0; i < x.Size(); i++) { + if (x[i] != 0) { + grad[i] += C * sign(x[i]); + continue; + } + const double gm = grad0[i] - C; + if (gm > 0) { + grad[i] = gm; + continue; + } + const double gp = grad0[i] + C; + if (gp < 0) { + grad[i] = gp; + continue; + } + grad[i] = 0; + } + + return grad; +} + +double ME_Model::regularized_func_grad(const double C, const Vec& x, + Vec& grad) { + double f = FunctionGradient(x.STLVec(), grad.STLVec()); + for (size_t i = 0; i < x.Size(); i++) { + f += C * fabs(x[i]); + } + + return f; +} + +double ME_Model::constrained_line_search(double C, const Vec& x0, + const Vec& grad0, const double f0, + const Vec& dx, Vec& x, Vec& grad1) { + // compute the orthant to explore + Vec orthant = x0; + for (size_t i = 0; i < orthant.Size(); i++) { + if (orthant[i] == 0) orthant[i] = -grad0[i]; + } + + double t = 1.0 / LINE_SEARCH_BETA; + + double f; + do { + t *= LINE_SEARCH_BETA; + x = x0 + t * dx; + x.Project(orthant); + // for (size_t i = 0; i < x.Size(); i++) { + // if (x0[i] != 0 && sign(x[i]) != sign(x0[i])) x[i] = 0; + // } + + f = regularized_func_grad(C, x, grad1); + // cout << "*"; + } while (f > f0 + LINE_SEARCH_ALPHA * dot_product(x - x0, grad0)); + + return f; +} + +vector ME_Model::perform_OWLQN(const vector& x0, + const double C) { + const size_t dim = x0.size(); + Vec x = x0; + + Vec grad(dim), dx(dim); + double f = regularized_func_grad(C, x, grad); + + Vec s[M], y[M]; + double z[M]; // rho + + for (int iter = 0; iter < OWLQN_MAX_ITER; iter++) { + Vec pg = pseudo_gradient(x, grad, C); + + fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, -f, _train_error); + if (_nheldout > 0) { + const double heldout_logl = heldout_likelihood(); + fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, + _heldout_error); + } + fprintf(stderr, "\n"); + + if (sqrt(dot_product(pg, pg)) < MIN_GRAD_NORM) break; + + dx = -1 * approximate_Hg(iter, pg, s, y, z); + if (dot_product(dx, pg) >= 0) dx.Project(-1 * pg); + + Vec x1(dim), grad1(dim); + f = constrained_line_search(C, x, pg, f, dx, x1, grad1); + + s[iter % M] = x1 - x; + y[iter % M] = grad1 - grad; + z[iter % M] = 1.0 / dot_product(y[iter % M], s[iter % M]); + + x = x1; + grad = grad1; + } + + return x.STLVec(); +} + +// SGD + +// const double SGD_ETA0 = 1; +// const double SGD_ITER = 30; +// const double SGD_ALPHA = 0.85; + +//#define FOLOS_NAIVE +//#define FOLOS_LAZY +#define SGD_CP + +inline void apply_l1_penalty(const int i, const double u, vector& _vl, + vector& q) { + double& w = _vl[i]; + const double z = w; + double& qi = q[i]; + if (w > 0) { + w = max(0.0, w - (u + qi)); + } else if (w < 0) { + w = min(0.0, w + (u - qi)); + } + qi += w - z; +} + +static double l1norm(const vector& v) { + double sum = 0; + for (size_t i = 0; i < v.size(); i++) sum += abs(v[i]); + return sum; +} + +inline void update_folos_lazy(const int iter_sample, const int k, + vector& _vl, + const vector& sum_eta, + vector& last_updated) { + const double penalty = sum_eta[iter_sample] - sum_eta[last_updated[k]]; + double& x = _vl[k]; + if (x > 0) + x = max(0.0, x - penalty); + else + x = min(0.0, x + penalty); + last_updated[k] = iter_sample; +} + +int ME_Model::perform_SGD() { + if (_l2reg > 0) { + cerr << "error: L2 regularization is currently not supported in SGD mode." + << endl; + exit(1); + } + + cerr << "performing SGD" << endl; + + const double l1param = _l1reg; + + const int d = _fb.Size(); + + vector ri(_vs.size()); + for (size_t i = 0; i < ri.size(); i++) ri[i] = i; + + vector grad(d); + int iter_sample = 0; + const double eta0 = SGD_ETA0; + + // cerr << "l1param = " << l1param << endl; + cerr << "eta0 = " << eta0 << " alpha = " << SGD_ALPHA << endl; + + double u = 0; + vector q(d, 0); + vector last_updated(d, 0); + vector sum_eta; + sum_eta.push_back(0); + + for (int iter = 0; iter < SGD_ITER; iter++) { + + random_shuffle(ri.begin(), ri.end()); + + double logl = 0; + int ncorrect = 0, ntotal = 0; + for (size_t i = 0; i < _vs.size(); i++, ntotal++, iter_sample++) { + const Sample& s = _vs[ri[i]]; + +#ifdef FOLOS_LAZY + for (vector::const_iterator j = s.positive_features.begin(); + j != s.positive_features.end(); j++) { + for (vector::const_iterator k = _feature2mef[*j].begin(); + k != _feature2mef[*j].end(); k++) { + update_folos_lazy(iter_sample, *k, _vl, sum_eta, last_updated); + } + } +#endif + + vector membp(_num_classes); + const int max_label = conditional_probability(s, membp); + + const double eta = + eta0 * pow(SGD_ALPHA, + (double)iter_sample / _vs.size()); // exponential decay + // const double eta = eta0 / (1.0 + (double)iter_sample / + // _vs.size()); + + // if (iter_sample % _vs.size() == 0) cerr << "eta = " << eta << + // endl; + u += eta * l1param; + + sum_eta.push_back(sum_eta.back() + eta * l1param); + + logl += log(membp[s.label]); + if (max_label == s.label) ncorrect++; + + // binary features + for (vector::const_iterator j = s.positive_features.begin(); + j != s.positive_features.end(); j++) { + for (vector::const_iterator k = _feature2mef[*j].begin(); + k != _feature2mef[*j].end(); k++) { + const double me = membp[_fb.Feature(*k).label()]; + const double ee = (_fb.Feature(*k).label() == s.label ? 1.0 : 0); + const double grad = (me - ee); + _vl[*k] -= eta * grad; +#ifdef SGD_CP + apply_l1_penalty(*k, u, _vl, q); +#endif + } + } + // real-valued features + for (vector >::const_iterator j = s.rvfeatures.begin(); + j != s.rvfeatures.end(); j++) { + for (vector::const_iterator k = _feature2mef[j->first].begin(); + k != _feature2mef[j->first].end(); k++) { + const double me = membp[_fb.Feature(*k).label()]; + const double ee = (_fb.Feature(*k).label() == s.label ? 1.0 : 0); + const double grad = (me - ee) * j->second; + _vl[*k] -= eta * grad; +#ifdef SGD_CP + apply_l1_penalty(*k, u, _vl, q); +#endif + } + } + +#ifdef FOLOS_NAIVE + for (size_t j = 0; j < d; j++) { + double& x = _vl[j]; + if (x > 0) + x = max(0.0, x - eta * l1param); + else + x = min(0.0, x + eta * l1param); + } +#endif + } + logl /= _vs.size(); +// fprintf(stderr, "%4d logl = %8.3f acc = %6.4f ", iter, logl, +// (double)ncorrect / ntotal); + +#ifdef FOLOS_LAZY + if (l1param > 0) { + for (size_t j = 0; j < d; j++) + update_folos_lazy(iter_sample, j, _vl, sum_eta, last_updated); + } +#endif + + double f = logl; + if (l1param > 0) { + const double l1 = + l1norm(_vl); // this is not accurate when lazy update is used + // cerr << "f0 = " << update_model_expectation() - l1param * l1 << " + // "; + f -= l1param * l1; + int nonzero = 0; + for (int j = 0; j < d; j++) + if (_vl[j] != 0) nonzero++; + // cerr << " f = " << f << " l1 = " << l1 << " nonzero_features = " + // << nonzero << endl; + } + // fprintf(stderr, "%4d obj = %7.3f acc = %6.4f", iter+1, f, + // (double)ncorrect/ntotal); + // fprintf(stderr, "%4d obj = %f", iter+1, f); + fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, f, + 1 - (double)ncorrect / ntotal); + + if (_nheldout > 0) { + double heldout_logl = heldout_likelihood(); + // fprintf(stderr, " heldout_logl = %f acc = %6.4f\n", + // heldout_logl, 1 - _heldout_error); + fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, + _heldout_error); + } + fprintf(stderr, "\n"); + } + + return 0; +} + +} // namespace maxent + /* * $Log: maxent.cpp,v $ * Revision 1.1.1.1 2007/05/15 08:30:35 kyoshida diff --git a/utils/maxent.h b/utils/maxent.h index b1efd88e..74d13a6f 100644 --- a/utils/maxent.h +++ b/utils/maxent.h @@ -5,21 +5,95 @@ #ifndef __MAXENT_H_ #define __MAXENT_H_ -#include -#include -#include -#include #include #include +#include +#include #include +#include +#include + #include -#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 -#endif +namespace maxent { +class Vec { + private: + std::vector _v; + + public: + Vec(const size_t n = 0, const double val = 0) { _v.resize(n, val); } + Vec(const std::vector& v) : _v(v) {} + const std::vector& STLVec() const { return _v; } + std::vector& STLVec() { return _v; } + size_t Size() const { return _v.size(); } + double& operator[](int i) { return _v[i]; } + const double& operator[](int i) const { return _v[i]; } + Vec& operator+=(const Vec& b) { + assert(b.Size() == _v.size()); + for (size_t i = 0; i < _v.size(); i++) { + _v[i] += b[i]; + } + return *this; + } + Vec& operator*=(const double c) { + for (size_t i = 0; i < _v.size(); i++) { + _v[i] *= c; + } + return *this; + } + void Project(const Vec& y) { + for (size_t i = 0; i < _v.size(); i++) { + // if (sign(_v[i]) != sign(y[i])) _v[i] = 0; + if (_v[i] * y[i] <= 0) _v[i] = 0; + } + } +}; + +inline double dot_product(const Vec& a, const Vec& b) { + double sum = 0; + for (size_t i = 0; i < a.Size(); i++) { + sum += a[i] * b[i]; + } + return sum; +} + +inline std::ostream& operator<<(std::ostream& s, const Vec& a) { + s << "("; + for (size_t i = 0; i < a.Size(); i++) { + if (i != 0) s << ", "; + s << a[i]; + } + s << ")"; + return s; +} + +inline const Vec operator+(const Vec& a, const Vec& b) { + Vec v(a.Size()); + assert(a.Size() == b.Size()); + for (size_t i = 0; i < a.Size(); i++) { + v[i] = a[i] + b[i]; + } + return v; +} + +inline const Vec operator-(const Vec& a, const Vec& b) { + Vec v(a.Size()); + assert(a.Size() == b.Size()); + for (size_t i = 0; i < a.Size(); i++) { + v[i] = a[i] - b[i]; + } + return v; +} + +inline const Vec operator*(const Vec& a, const double c) { + Vec v(a.Size()); + for (size_t i = 0; i < a.Size(); i++) { + v[i] = a[i] * c; + } + return v; +} + +inline const Vec operator*(const double c, const Vec& a) { return a * c; } // // data format for each sample for training/testing @@ -309,6 +383,7 @@ class ME_Model { static double FunctionGradientWrapper(const std::vector& x, std::vector& grad); }; +} // namespace maxent #endif diff --git a/utils/owlqn.cpp b/utils/owlqn.cpp deleted file mode 100644 index c3a0f0da..00000000 --- a/utils/owlqn.cpp +++ /dev/null @@ -1,127 +0,0 @@ -#include -#include -#include -#include -#include "mathvec.h" -#include "lbfgs.h" -#include "maxent.h" - -using namespace std; - -const static int M = LBFGS_M; -const static double LINE_SEARCH_ALPHA = 0.1; -const static double LINE_SEARCH_BETA = 0.5; - -// stopping criteria -int OWLQN_MAX_ITER = 300; -const static double MIN_GRAD_NORM = 0.0001; - -Vec approximate_Hg(const int iter, const Vec& grad, const Vec s[], - const Vec y[], const double z[]); - -inline int sign(double x) { - if (x > 0) return 1; - if (x < 0) return -1; - return 0; -}; - -static Vec pseudo_gradient(const Vec& x, const Vec& grad0, const double C) { - Vec grad = grad0; - for (size_t i = 0; i < x.Size(); i++) { - if (x[i] != 0) { - grad[i] += C * sign(x[i]); - continue; - } - const double gm = grad0[i] - C; - if (gm > 0) { - grad[i] = gm; - continue; - } - const double gp = grad0[i] + C; - if (gp < 0) { - grad[i] = gp; - continue; - } - grad[i] = 0; - } - - return grad; -} - -double ME_Model::regularized_func_grad(const double C, const Vec& x, - Vec& grad) { - double f = FunctionGradient(x.STLVec(), grad.STLVec()); - for (size_t i = 0; i < x.Size(); i++) { - f += C * fabs(x[i]); - } - - return f; -} - -double ME_Model::constrained_line_search(double C, const Vec& x0, - const Vec& grad0, const double f0, - const Vec& dx, Vec& x, Vec& grad1) { - // compute the orthant to explore - Vec orthant = x0; - for (size_t i = 0; i < orthant.Size(); i++) { - if (orthant[i] == 0) orthant[i] = -grad0[i]; - } - - double t = 1.0 / LINE_SEARCH_BETA; - - double f; - do { - t *= LINE_SEARCH_BETA; - x = x0 + t * dx; - x.Project(orthant); - // for (size_t i = 0; i < x.Size(); i++) { - // if (x0[i] != 0 && sign(x[i]) != sign(x0[i])) x[i] = 0; - // } - - f = regularized_func_grad(C, x, grad1); - // cout << "*"; - } while (f > f0 + LINE_SEARCH_ALPHA * dot_product(x - x0, grad0)); - - return f; -} - -vector ME_Model::perform_OWLQN(const vector& x0, - const double C) { - const size_t dim = x0.size(); - Vec x = x0; - - Vec grad(dim), dx(dim); - double f = regularized_func_grad(C, x, grad); - - Vec s[M], y[M]; - double z[M]; // rho - - for (int iter = 0; iter < OWLQN_MAX_ITER; iter++) { - Vec pg = pseudo_gradient(x, grad, C); - - fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, -f, _train_error); - if (_nheldout > 0) { - const double heldout_logl = heldout_likelihood(); - fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, - _heldout_error); - } - fprintf(stderr, "\n"); - - if (sqrt(dot_product(pg, pg)) < MIN_GRAD_NORM) break; - - dx = -1 * approximate_Hg(iter, pg, s, y, z); - if (dot_product(dx, pg) >= 0) dx.Project(-1 * pg); - - Vec x1(dim), grad1(dim); - f = constrained_line_search(C, x, pg, f, dx, x1, grad1); - - s[iter % M] = x1 - x; - y[iter % M] = grad1 - grad; - z[iter % M] = 1.0 / dot_product(y[iter % M], s[iter % M]); - - x = x1; - grad = grad1; - } - - return x.STLVec(); -} diff --git a/utils/sgd.cpp b/utils/sgd.cpp deleted file mode 100644 index 8613edca..00000000 --- a/utils/sgd.cpp +++ /dev/null @@ -1,193 +0,0 @@ -#include "maxent.h" -#include -#include - -using namespace std; - -// const double SGD_ETA0 = 1; -// const double SGD_ITER = 30; -// const double SGD_ALPHA = 0.85; - -//#define FOLOS_NAIVE -//#define FOLOS_LAZY -#define SGD_CP - -inline void apply_l1_penalty(const int i, const double u, vector& _vl, - vector& q) { - double& w = _vl[i]; - const double z = w; - double& qi = q[i]; - if (w > 0) { - w = max(0.0, w - (u + qi)); - } else if (w < 0) { - w = min(0.0, w + (u - qi)); - } - qi += w - z; -} - -static double l1norm(const vector& v) { - double sum = 0; - for (size_t i = 0; i < v.size(); i++) sum += abs(v[i]); - return sum; -} - -inline void update_folos_lazy(const int iter_sample, const int k, - vector& _vl, - const vector& sum_eta, - vector& last_updated) { - const double penalty = sum_eta[iter_sample] - sum_eta[last_updated[k]]; - double& x = _vl[k]; - if (x > 0) - x = max(0.0, x - penalty); - else - x = min(0.0, x + penalty); - last_updated[k] = iter_sample; -} - -int ME_Model::perform_SGD() { - if (_l2reg > 0) { - cerr << "error: L2 regularization is currently not supported in SGD mode." - << endl; - exit(1); - } - - cerr << "performing SGD" << endl; - - const double l1param = _l1reg; - - const int d = _fb.Size(); - - vector ri(_vs.size()); - for (size_t i = 0; i < ri.size(); i++) ri[i] = i; - - vector grad(d); - int iter_sample = 0; - const double eta0 = SGD_ETA0; - - // cerr << "l1param = " << l1param << endl; - cerr << "eta0 = " << eta0 << " alpha = " << SGD_ALPHA << endl; - - double u = 0; - vector q(d, 0); - vector last_updated(d, 0); - vector sum_eta; - sum_eta.push_back(0); - - for (int iter = 0; iter < SGD_ITER; iter++) { - - random_shuffle(ri.begin(), ri.end()); - - double logl = 0; - int ncorrect = 0, ntotal = 0; - for (size_t i = 0; i < _vs.size(); i++, ntotal++, iter_sample++) { - const Sample& s = _vs[ri[i]]; - -#ifdef FOLOS_LAZY - for (vector::const_iterator j = s.positive_features.begin(); - j != s.positive_features.end(); j++) { - for (vector::const_iterator k = _feature2mef[*j].begin(); - k != _feature2mef[*j].end(); k++) { - update_folos_lazy(iter_sample, *k, _vl, sum_eta, last_updated); - } - } -#endif - - vector membp(_num_classes); - const int max_label = conditional_probability(s, membp); - - const double eta = - eta0 * pow(SGD_ALPHA, - (double)iter_sample / _vs.size()); // exponential decay - // const double eta = eta0 / (1.0 + (double)iter_sample / - // _vs.size()); - - // if (iter_sample % _vs.size() == 0) cerr << "eta = " << eta << - // endl; - u += eta * l1param; - - sum_eta.push_back(sum_eta.back() + eta * l1param); - - logl += log(membp[s.label]); - if (max_label == s.label) ncorrect++; - - // binary features - for (vector::const_iterator j = s.positive_features.begin(); - j != s.positive_features.end(); j++) { - for (vector::const_iterator k = _feature2mef[*j].begin(); - k != _feature2mef[*j].end(); k++) { - const double me = membp[_fb.Feature(*k).label()]; - const double ee = (_fb.Feature(*k).label() == s.label ? 1.0 : 0); - const double grad = (me - ee); - _vl[*k] -= eta * grad; -#ifdef SGD_CP - apply_l1_penalty(*k, u, _vl, q); -#endif - } - } - // real-valued features - for (vector >::const_iterator j = s.rvfeatures.begin(); - j != s.rvfeatures.end(); j++) { - for (vector::const_iterator k = _feature2mef[j->first].begin(); - k != _feature2mef[j->first].end(); k++) { - const double me = membp[_fb.Feature(*k).label()]; - const double ee = (_fb.Feature(*k).label() == s.label ? 1.0 : 0); - const double grad = (me - ee) * j->second; - _vl[*k] -= eta * grad; -#ifdef SGD_CP - apply_l1_penalty(*k, u, _vl, q); -#endif - } - } - -#ifdef FOLOS_NAIVE - for (size_t j = 0; j < d; j++) { - double& x = _vl[j]; - if (x > 0) - x = max(0.0, x - eta * l1param); - else - x = min(0.0, x + eta * l1param); - } -#endif - } - logl /= _vs.size(); -// fprintf(stderr, "%4d logl = %8.3f acc = %6.4f ", iter, logl, -// (double)ncorrect / ntotal); - -#ifdef FOLOS_LAZY - if (l1param > 0) { - for (size_t j = 0; j < d; j++) - update_folos_lazy(iter_sample, j, _vl, sum_eta, last_updated); - } -#endif - - double f = logl; - if (l1param > 0) { - const double l1 = - l1norm(_vl); // this is not accurate when lazy update is used - // cerr << "f0 = " << update_model_expectation() - l1param * l1 << " - // "; - f -= l1param * l1; - int nonzero = 0; - for (int j = 0; j < d; j++) - if (_vl[j] != 0) nonzero++; - // cerr << " f = " << f << " l1 = " << l1 << " nonzero_features = " - // << nonzero << endl; - } - // fprintf(stderr, "%4d obj = %7.3f acc = %6.4f", iter+1, f, - // (double)ncorrect/ntotal); - // fprintf(stderr, "%4d obj = %f", iter+1, f); - fprintf(stderr, "%3d obj(err) = %f (%6.4f)", iter + 1, f, - 1 - (double)ncorrect / ntotal); - - if (_nheldout > 0) { - double heldout_logl = heldout_likelihood(); - // fprintf(stderr, " heldout_logl = %f acc = %6.4f\n", - // heldout_logl, 1 - _heldout_error); - fprintf(stderr, " heldout_logl(err) = %f (%6.4f)", heldout_logl, - _heldout_error); - } - fprintf(stderr, "\n"); - } - - return 0; -} -- cgit v1.2.3