From 3a802d691a34fe4a75af110fc8c4a771f18b7641 Mon Sep 17 00:00:00 2001 From: graehl Date: Thu, 23 Sep 2010 00:10:52 +0000 Subject: pausing earley best-first fsa work git-svn-id: https://ws10smt.googlecode.com/svn/trunk@656 ec762483-ff6d-05da-a07a-a48fb63a330f --- decoder/apply_fsa_models.cc | 141 +++++++++++++++++++++++++++++++------------- decoder/oracle_bleu.h | 1 + graehl/NOTES.earley | 4 ++ utils/agenda.h | 17 +++++- utils/d_ary_heap.h | 16 +++++ 5 files changed, 137 insertions(+), 42 deletions(-) diff --git a/decoder/apply_fsa_models.cc b/decoder/apply_fsa_models.cc index 6031dbab..3e93cadd 100755 --- a/decoder/apply_fsa_models.cc +++ b/decoder/apply_fsa_models.cc @@ -165,6 +165,16 @@ struct PrefixTrieEdge { struct PrefixTrieNode { best_t p; // viterbi (max prob) of rule this node leads to - when building. telescope later onto edges for best-first. // bool final; // may also have successors, of course. we don't really need to track this; a null dest edge in the adj list lets us encounter the fact in best first order. + void p_delta(int next,best_t &p) const { + p*=adj[next].p; + } + void inc_adj(int &next,best_t &p) const { + p/=adj[next].p; //TODO: cache deltas + ++next; + p*=adj[next].p; + } + + typedef TrieBackP BP; typedef std::vector BPs; void back_vec(BPs &ns) const { @@ -249,7 +259,7 @@ public: // assert(edge.p.is_1()); // actually, after done_building, e will have telescoped dest->p/p. NTHandle n=-edge.w; assert(n>=0); - SHOWM3(DPFSA,"index_lhs",i,edge,n); +// SHOWM3(DPFSA,"index_lhs",i,edge,n); v[n]=edge.dest; } } @@ -428,24 +438,6 @@ private: }; -// these should go in a global best-first queue -struct ItemPrio { - // NOTE: sum = viterbi (max) - ItemPrio() : priority(init_0()),inner(init_0()) { } - best_t priority; // includes inner prob. (forward) - /* The forward probability alpha_i(X[k]->x.y) is the sum of the probabilities of all - constrained paths of length i that end in state X[k]->x.y*/ - best_t inner; - /* The inner probability beta_i(X[k]->x.y) is the sum of the probabilities of all - paths of length i-k that start in state X[k,k]->.xy and end in X[k,i]->x.y, and generate the input symbols x[k,...,i-1] */ - template - void print(O &o) const { - o<x.y) is the sum of the probabilities of all + constrained paths of length i that end in state X[k]->x.y*/ + best_t inner; + /* The inner probability beta_i(X[k]->x.y) is the sum of the probabilities of all + paths of length i-k that start in state X[k,k]->.xy and end in X[k,i]->x.y, and generate the input symbols x[k,...,i-1] */ + template + void print(O &o) const { + o<=0; + } + explicit Item(FFState const& state,NodeP dot,best_t prio,int next=0) : ItemPrio(prio),ItemKey(dot,state),trienext(next),from(0) INIT_LOCATION - { } + { +// t=ADJ; +// if (dot->adj.size()) + dot->p_delta(next,priority); +// SHOWM1(DFSA,"Item(state,dot,prio)",prio); + } typedef std::queue Predicted; - Predicted predicted; // this is empty, unless this is a predicted L -> .asdf item, or a to-complete L -> asdf . +// Predicted predicted; // this is empty, unless this is a predicted L -> .asdf item, or a to-complete L -> asdf . int trienext; // index of dot->adj to complete (if dest==0), or predict (if NT), or scan (if word). note: we could store pointer inside adj since it and trie are @ fixed addrs. less pointer arith, more space. ItemP from; //backpointer - 0 for L -> . asdf for the rest; L -> a .sdf, it's the L -> .asdf item. ItemP predicted_from() const { @@ -518,6 +547,7 @@ struct Item : ItemPrio,ItemKey { template void print(O &o) const { o<< '['; + o< A; A a; - void best_first(unsigned kbest=1) { + + /* had to stop working on this for now - it's garbage/useless in this form - see NOTES.earley */ + + // p_partial is priority*p(rule) - excluding the FSA model score, and predicted + void succ(Item const& from,int adji,best_t p_partial) { + PrefixTrieEdge const& te=from.dot->adj[adji]; + NodeP dest=te.dest; + if (te.is_final()) { + // complete + return; + } + WordID w=te.w; + if (w<0) { + NTHandle lhs=-w; + } else { + + } + } + + void extend1() { BetterP better; - assert(kbest==1); //TODO: k-best via best-first requires revisiting best things again and adjusting desc. tricky. - while(!a.empty()) { - ItemP top=a.pop(); - best_t b=a.best(); // remember; best_t apriority; - best_t trie_stop_p=topb/b; - NodeP d=top->dot; - PrefixTrieNode::Adj const& adj=d->adj; - int n=top->trienext; - for (int m=adj.size();nadj; + int n=t.trienext,m=adj.size(); + SHOWM3(DFSA,"popped",t,tp,pstop); + for (;n::ApplyEarley() Chart chart(cfg,smeta,fsa); // don't need to uniq - option to do that already exists in cfg_options //TODO: + chart.best_first(); *oh=hgcfg.ih; } diff --git a/decoder/oracle_bleu.h b/decoder/oracle_bleu.h index 145c84d1..b3b1fd17 100755 --- a/decoder/oracle_bleu.h +++ b/decoder/oracle_bleu.h @@ -114,6 +114,7 @@ struct OracleBleu { } OracleBleu(int doc_size=10) { set_oracle_doc_size(doc_size); + show_derivation=false; } ScoreP doc_score,sentscore; // made from factory, so we delete them diff --git a/graehl/NOTES.earley b/graehl/NOTES.earley index 4156063a..0953708c 100755 --- a/graehl/NOTES.earley +++ b/graehl/NOTES.earley @@ -105,3 +105,7 @@ vs. 3) * -> x . * with 3, we predict all sorts of useless items - that won't give us our goal A and may not partcipate in any parse. this is not a good option at all. + +====== + +-LM forest may have many in-edges per V. (many rules per NT lhs). so instead of generating all successors for scan/predict, i wanted to have them in sorted (admissable) -LM cost order and postpone once the prefix+rule part is more expensive than something else in the agenda. question: how many such postponed successor things diff --git a/utils/agenda.h b/utils/agenda.h index 1dbcd7bb..d4f13696 100755 --- a/utils/agenda.h +++ b/utils/agenda.h @@ -107,14 +107,27 @@ struct Agenda : intern_pool { } // no need to destroy the canon. item because we want to remember the best cost and reject more expensive ways of using it). ItemC pop() { - DBG_AGENDA(assert(!empty())); ItemC r=q.top(); q.pop(); return r; } + void pop_discard() { + q.pop(); + } + + ItemC top() { + DBG_AGENDA(assert(!empty())); + return q.top(); + } + agenda_best_t best() const { - return priomap[q.top()]; //TODO: cache/track the global best? + return q.best(); //TODO: cache/track the global best? } + + agenda_best_t second_best() const { + return q.second_best(); + } + // add only if worse than queue current best, otherwise evaluate immediately (e.g. for early stopping w/ expensive to compute additional cost). return true if postponed (added) bool postpone(ItemP i) { if (better(priomap[i],best())) return false; diff --git a/utils/d_ary_heap.h b/utils/d_ary_heap.h index 3a071772..1270638a 100644 --- a/utils/d_ary_heap.h +++ b/utils/d_ary_heap.h @@ -283,6 +283,22 @@ return false; } + distance_type best(distance_type null=0) const { + return empty() ? null : get(distance,data[0]); + } + distance_type second_best(distance_type null=0) const { + if (data.size()<2) return null; + int m=std::min(data.size(),Arity+1); +// if (m>=Arity) m=Arity+1; + distance_type b=get(distance,data[1]); + for (int i=2;i