From b89a1d3cb72ac36c137d6ae342f48ab9b8ee6655 Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Mon, 18 Jun 2012 20:28:42 -0400 Subject: add non-const iterators to sparse vector, speed up model1 code --- dtrain/dtrain.cc | 4 +-- training/model1.cc | 61 ++++++++++++++++++--------------- training/mpi_flex_optimize.cc | 2 +- training/ttables.h | 17 ++++----- utils/ccrp_onetable.h | 2 +- utils/corpus_tools.cc | 20 +++++++++++ utils/corpus_tools.h | 4 +++ utils/fast_sparse_vector.h | 80 ++++++++++++++++++++++++++++++++++++++++++- utils/sampler.h | 16 ++++++++- 9 files changed, 164 insertions(+), 42 deletions(-) diff --git a/dtrain/dtrain.cc b/dtrain/dtrain.cc index 8b1fc953..d9bce843 100644 --- a/dtrain/dtrain.cc +++ b/dtrain/dtrain.cc @@ -593,12 +593,12 @@ main(int argc, char** argv) o.precision(17); o << _np; if (average) { - for (SparseVector::const_iterator it = w_average.begin(); it != w_average.end(); ++it) { + for (SparseVector::iterator it = w_average.begin(); it != w_average.end(); ++it) { if (it->second == 0) continue; o << FD::Convert(it->first) << '\t' << it->second << endl; } } else { - for (SparseVector::const_iterator it = lambdas.begin(); it != lambdas.end(); ++it) { + for (SparseVector::iterator it = lambdas.begin(); it != lambdas.end(); ++it) { if (it->second == 0) continue; o << FD::Convert(it->first) << '\t' << it->second << endl; } diff --git a/training/model1.cc b/training/model1.cc index 73104304..19692b9a 100644 --- a/training/model1.cc +++ b/training/model1.cc @@ -5,7 +5,7 @@ #include #include "m.h" -#include "lattice.h" +#include "corpus_tools.h" #include "stringlib.h" #include "filelib.h" #include "ttables.h" @@ -19,6 +19,7 @@ bool InitCommandLine(int argc, char** argv, po::variables_map* conf) { opts.add_options() ("iterations,i",po::value()->default_value(5),"Number of iterations of EM training") ("beam_threshold,t",po::value()->default_value(-4),"log_10 of beam threshold (-10000 to include everything, 0 max)") + ("bidir,b", "Run bidirectional alignment") ("no_null_word,N","Do not generate from the null token") ("write_alignments,A", "Write alignments instead of parameters") ("favor_diagonal,d", "Use a static alignment distribution that assigns higher probabilities to alignments near the diagonal") @@ -51,6 +52,15 @@ bool InitCommandLine(int argc, char** argv, po::variables_map* conf) { return true; } +// src and trg are source and target strings, respectively (not really lattices) +double PosteriorInference(const vector& src, const vector& trg) { + double llh = 0; + static vector unnormed_a_i; + if (src.size() > unnormed_a_i.size()) + unnormed_a_i.resize(src.size()); + return llh; +} + int main(int argc, char** argv) { po::variables_map conf; if (!InitCommandLine(argc, argv, &conf)) return 1; @@ -74,8 +84,8 @@ int main(int argc, char** argv) { return 1; } - TTable tt; - TTable::Word2Word2Double was_viterbi; + TTable s2t, t2s; + TTable::Word2Word2Double s2t_viterbi; double tot_len_ratio = 0; double mean_srclen_multiplier = 0; vector unnormed_a_i; @@ -96,14 +106,11 @@ int main(int argc, char** argv) { ++lc; if (lc % 1000 == 0) { cerr << '.'; flag = true; } if (lc %50000 == 0) { cerr << " [" << lc << "]\n" << flush; flag = false; } - ParseTranslatorInput(line, &ssrc, &strg); - Lattice src, trg; - LatticeTools::ConvertTextToLattice(ssrc, &src); - LatticeTools::ConvertTextToLattice(strg, &trg); + vector src, trg; + CorpusTools::ReadLine(line, &src, &trg); if (src.size() == 0 || trg.size() == 0) { cerr << "Error: " << lc << "\n" << line << endl; - assert(src.size() > 0); - assert(trg.size() > 0); + return 1; } if (src.size() > unnormed_a_i.size()) unnormed_a_i.resize(src.size()); @@ -113,13 +120,13 @@ int main(int argc, char** argv) { vector probs(src.size() + 1); bool first_al = true; // used for write_alignments for (int j = 0; j < trg.size(); ++j) { - const WordID& f_j = trg[j][0].label; + const WordID& f_j = trg[j]; double sum = 0; const double j_over_ts = double(j) / trg.size(); double prob_a_i = 1.0 / (src.size() + use_null); // uniform (model 1) if (use_null) { if (favor_diagonal) prob_a_i = prob_align_null; - probs[0] = tt.prob(kNULL, f_j) * prob_a_i; + probs[0] = s2t.prob(kNULL, f_j) * prob_a_i; sum += probs[0]; } double az = 0; @@ -133,7 +140,7 @@ int main(int argc, char** argv) { for (int i = 1; i <= src.size(); ++i) { if (favor_diagonal) prob_a_i = unnormed_a_i[i-1] / az; - probs[i] = tt.prob(src[i-1][0].label, f_j) * prob_a_i; + probs[i] = s2t.prob(src[i-1], f_j) * prob_a_i; sum += probs[i]; } if (final_iteration) { @@ -150,7 +157,7 @@ int main(int argc, char** argv) { if (probs[i] > max_p) { max_index = i; max_p = probs[i]; - max_i = src[i-1][0].label; + max_i = src[i-1]; } } if (write_alignments) { @@ -159,13 +166,13 @@ int main(int argc, char** argv) { cout << (max_index - 1) << "-" << j; } } - was_viterbi[max_i][f_j] = 1.0; + s2t_viterbi[max_i][f_j] = 1.0; } } else { if (use_null) - tt.Increment(kNULL, f_j, probs[0] / sum); + s2t.Increment(kNULL, f_j, probs[0] / sum); for (int i = 1; i <= src.size(); ++i) - tt.Increment(src[i-1][0].label, f_j, probs[i] / sum); + s2t.Increment(src[i-1], f_j, probs[i] / sum); } likelihood += log(sum); } @@ -186,9 +193,9 @@ int main(int argc, char** argv) { cerr << " perplexity: " << pow(2.0, -base2_likelihood / denom) << endl; if (!final_iteration) { if (variational_bayes) - tt.NormalizeVB(alpha); + s2t.NormalizeVB(alpha); else - tt.Normalize(); + s2t.Normalize(); } } if (testset.size()) { @@ -199,23 +206,21 @@ int main(int argc, char** argv) { string ssrc, strg, line; while (getline(in, line)) { ++lc; - ParseTranslatorInput(line, &ssrc, &strg); - Lattice src, trg; - LatticeTools::ConvertTextToLattice(ssrc, &src); - LatticeTools::ConvertTextToLattice(strg, &trg); + vector src, trg; + CorpusTools::ReadLine(line, &src, &trg); double log_prob = Md::log_poisson(trg.size(), 0.05 + src.size() * mean_srclen_multiplier); if (src.size() > unnormed_a_i.size()) unnormed_a_i.resize(src.size()); // compute likelihood for (int j = 0; j < trg.size(); ++j) { - const WordID& f_j = trg[j][0].label; + const WordID& f_j = trg[j]; double sum = 0; const double j_over_ts = double(j) / trg.size(); double prob_a_i = 1.0 / (src.size() + use_null); // uniform (model 1) if (use_null) { if (favor_diagonal) prob_a_i = prob_align_null; - sum += tt.prob(kNULL, f_j) * prob_a_i; + sum += s2t.prob(kNULL, f_j) * prob_a_i; } double az = 0; if (favor_diagonal) { @@ -228,7 +233,7 @@ int main(int argc, char** argv) { for (int i = 1; i <= src.size(); ++i) { if (favor_diagonal) prob_a_i = unnormed_a_i[i-1] / az; - sum += tt.prob(src[i-1][0].label, f_j) * prob_a_i; + sum += s2t.prob(src[i-1], f_j) * prob_a_i; } log_prob += log(sum); } @@ -240,16 +245,16 @@ int main(int argc, char** argv) { if (write_alignments) return 0; - for (TTable::Word2Word2Double::iterator ei = tt.ttable.begin(); ei != tt.ttable.end(); ++ei) { + for (TTable::Word2Word2Double::iterator ei = s2t.ttable.begin(); ei != s2t.ttable.end(); ++ei) { const TTable::Word2Double& cpd = ei->second; - const TTable::Word2Double& vit = was_viterbi[ei->first]; + const TTable::Word2Double& vit = s2t_viterbi[ei->first]; const string& esym = TD::Convert(ei->first); double max_p = -1; for (TTable::Word2Double::const_iterator fi = cpd.begin(); fi != cpd.end(); ++fi) if (fi->second > max_p) max_p = fi->second; const double threshold = max_p * BEAM_THRESHOLD; for (TTable::Word2Double::const_iterator fi = cpd.begin(); fi != cpd.end(); ++fi) { - if (fi->second > threshold || (vit.count(fi->first) > 0)) { + if (fi->second > threshold || (vit.find(fi->first) != vit.end())) { cout << esym << ' ' << TD::Convert(fi->first) << ' ' << log(fi->second) << endl; } } diff --git a/training/mpi_flex_optimize.cc b/training/mpi_flex_optimize.cc index a9ead018..b52decdc 100644 --- a/training/mpi_flex_optimize.cc +++ b/training/mpi_flex_optimize.cc @@ -356,7 +356,7 @@ int main(int argc, char** argv) { gg.clear(); gg.resize(FD::NumFeats()); if (gg.size() != cur_weights.size()) { cur_weights.resize(gg.size()); } - for (SparseVector::const_iterator it = g.begin(); it != g.end(); ++it) + for (SparseVector::iterator it = g.begin(); it != g.end(); ++it) if (it->first) { gg[it->first] = it->second; } g.clear(); double r = ApplyRegularizationTerms(regularization_strength, diff --git a/training/ttables.h b/training/ttables.h index bf3351d2..9baa13ca 100644 --- a/training/ttables.h +++ b/training/ttables.h @@ -4,6 +4,7 @@ #include #include +#include "sparse_vector.h" #include "m.h" #include "wordid.h" #include "tdict.h" @@ -68,18 +69,18 @@ class TTable { } return *this; } - void ShowTTable() { - for (Word2Word2Double::iterator it = ttable.begin(); it != ttable.end(); ++it) { - Word2Double& cpd = it->second; - for (Word2Double::iterator j = cpd.begin(); j != cpd.end(); ++j) { + void ShowTTable() const { + for (Word2Word2Double::const_iterator it = ttable.begin(); it != ttable.end(); ++it) { + const Word2Double& cpd = it->second; + for (Word2Double::const_iterator j = cpd.begin(); j != cpd.end(); ++j) { std::cerr << "P(" << TD::Convert(j->first) << '|' << TD::Convert(it->first) << ") = " << j->second << std::endl; } } } - void ShowCounts() { - for (Word2Word2Double::iterator it = counts.begin(); it != counts.end(); ++it) { - Word2Double& cpd = it->second; - for (Word2Double::iterator j = cpd.begin(); j != cpd.end(); ++j) { + void ShowCounts() const { + for (Word2Word2Double::const_iterator it = counts.begin(); it != counts.end(); ++it) { + const Word2Double& cpd = it->second; + for (Word2Double::const_iterator j = cpd.begin(); j != cpd.end(); ++j) { std::cerr << "c(" << TD::Convert(j->first) << '|' << TD::Convert(it->first) << ") = " << j->second << std::endl; } } diff --git a/utils/ccrp_onetable.h b/utils/ccrp_onetable.h index 1fe01b0e..abe399ea 100644 --- a/utils/ccrp_onetable.h +++ b/utils/ccrp_onetable.h @@ -183,7 +183,7 @@ class CCRP_OneTable { assert(has_discount_prior() || has_alpha_prior()); DiscountResampler dr(*this); ConcentrationResampler cr(*this); - for (int iter = 0; iter < nloop; ++iter) { + for (unsigned iter = 0; iter < nloop; ++iter) { if (has_alpha_prior()) { alpha_ = slice_sampler1d(cr, alpha_, *rng, 0.0, std::numeric_limits::infinity(), 0.0, niterations, 100*niterations); diff --git a/utils/corpus_tools.cc b/utils/corpus_tools.cc index d17785af..191153a2 100644 --- a/utils/corpus_tools.cc +++ b/utils/corpus_tools.cc @@ -8,6 +8,26 @@ using namespace std; +void CorpusTools::ReadLine(const string& line, + vector* src, + vector* trg) { + static const WordID kDIV = TD::Convert("|||"); + static vector tmp; + src->clear(); + trg->clear(); + TD::ConvertSentence(line, &tmp); + unsigned i = 0; + while(i < tmp.size() && tmp[i] != kDIV) { + src->push_back(tmp[i]); + ++i; + } + if (i < tmp.size() && tmp[i] == kDIV) { + ++i; + for (; i < tmp.size() ; ++i) + trg->push_back(tmp[i]); + } +} + void CorpusTools::ReadFromFile(const string& filename, vector >* src, set* src_vocab, diff --git a/utils/corpus_tools.h b/utils/corpus_tools.h index 97bdaa94..f6699d87 100644 --- a/utils/corpus_tools.h +++ b/utils/corpus_tools.h @@ -7,6 +7,10 @@ #include "wordid.h" struct CorpusTools { + static void ReadLine(const std::string& line, + std::vector* src, + std::vector* trg); + static void ReadFromFile(const std::string& filename, std::vector >* src, std::set* src_vocab = NULL, diff --git a/utils/fast_sparse_vector.h b/utils/fast_sparse_vector.h index e86cbdc1..6e5dfb14 100644 --- a/utils/fast_sparse_vector.h +++ b/utils/fast_sparse_vector.h @@ -66,6 +66,60 @@ BOOST_STATIC_ASSERT(sizeof(PairIntT) == sizeof(std::pair) template class FastSparseVector { public: + struct iterator { + iterator(FastSparseVector& v, const bool is_end) : local_(!v.is_remote_) { + if (local_) { + local_it_ = &v.data_.local[is_end ? v.local_size_ : 0]; + } else { + if (is_end) + remote_it_ = v.data_.rbmap->end(); + else + remote_it_ = v.data_.rbmap->begin(); + } + } + iterator(FastSparseVector& v, const bool, const unsigned k) : local_(!v.is_remote_) { + if (local_) { + unsigned i = 0; + while(i < v.local_size_ && v.data_.local[i].first() != k) { ++i; } + local_it_ = &v.data_.local[i]; + } else { + remote_it_ = v.data_.rbmap->find(k); + } + } + const bool local_; + PairIntT* local_it_; + typename std::map::iterator remote_it_; + std::pair& operator*() const { + if (local_) + return *reinterpret_cast*>(local_it_); + else + return *remote_it_; + } + + std::pair* operator->() const { + if (local_) + return reinterpret_cast*>(local_it_); + else + return &*remote_it_; + } + + iterator& operator++() { + if (local_) ++local_it_; else ++remote_it_; + return *this; + } + + inline bool operator==(const iterator& o) const { + if (o.local_ != local_) return false; + if (local_) { + return local_it_ == o.local_it_; + } else { + return remote_it_ == o.remote_it_; + } + } + inline bool operator!=(const iterator& o) const { + return !(o == *this); + } + }; struct const_iterator { const_iterator(const FastSparseVector& v, const bool is_end) : local_(!v.is_remote_) { if (local_) { @@ -77,12 +131,21 @@ class FastSparseVector { remote_it_ = v.data_.rbmap->begin(); } } + const_iterator(const FastSparseVector& v, const bool, const unsigned k) : local_(!v.is_remote_) { + if (local_) { + unsigned i = 0; + while(i < v.local_size_ && v.data_.local[i].first() != k) { ++i; } + local_it_ = &v.data_.local[i]; + } else { + remote_it_ = v.data_.rbmap->find(k); + } + } const bool local_; const PairIntT* local_it_; typename std::map::const_iterator remote_it_; const std::pair& operator*() const { if (local_) - return *reinterpret_cast*>(local_it_); + return *reinterpret_cast*>(local_it_); else return *remote_it_; } @@ -160,6 +223,9 @@ class FastSparseVector { bool nonzero(unsigned k) const { return static_cast(value(k)); } + inline T& operator[](unsigned k) { + return get_or_create_bin(k); + } inline void set_value(unsigned k, const T& v) { get_or_create_bin(k) = v; } @@ -283,6 +349,18 @@ class FastSparseVector { } return o; } + iterator find(unsigned k) { + return iterator(*this, false, k); + } + iterator begin() { + return iterator(*this, false); + } + iterator end() { + return iterator(*this, true); + } + const_iterator find(unsigned k) const { + return const_iterator(*this, false, k); + } const_iterator begin() const { return const_iterator(*this, false); } diff --git a/utils/sampler.h b/utils/sampler.h index b237c716..3e4a4086 100644 --- a/utils/sampler.h +++ b/utils/sampler.h @@ -12,6 +12,7 @@ #include #include #include +#include #include #include #include @@ -76,6 +77,18 @@ struct RandomNumberGenerator { return boost::poisson_distribution(lambda)(m_random); } + double NextGamma(double shape, double scale = 1.0) { + boost::gamma_distribution<> gamma(shape); + boost::variate_generator > vg(m_generator, gamma); + return vg() * scale; + } + + double NextBeta(double alpha, double beta) { + double x = NextGamma(alpha); + double y = NextGamma(beta); + return x / (x + y); + } + bool AcceptMetropolisHastings(const prob_t& p_cur, const prob_t& p_prev, const prob_t& q_cur, @@ -123,11 +136,12 @@ size_t RandomNumberGenerator::SelectSample(const SampleSet& ss, double T const bool anneal = (T != 1.0); F sum = F(0); if (anneal) { - for (int i = 0; i < ss.m_scores.size(); ++i) + for (unsigned i = 0; i < ss.m_scores.size(); ++i) sum += pow(ss.m_scores[i], annealing_factor); // p^(1/T) } else { sum = std::accumulate(ss.m_scores.begin(), ss.m_scores.end(), F(0)); } + //std::cerr << "SUM: " << sum << std::endl; //for (size_t i = 0; i < ss.m_scores.size(); ++i) std::cerr << ss.m_scores[i] << ","; //std::cerr << std::endl; -- cgit v1.2.3