diff options
author | jfouet <jfouet@1f5c12ca-751b-0410-a591-d2e778427230> | 2008-05-20 16:42:11 +0400 |
---|---|---|
committer | jfouet <jfouet@1f5c12ca-751b-0410-a591-d2e778427230> | 2008-05-20 16:42:11 +0400 |
commit | 6ee40847971da74c87992237b95db33a4365b53a (patch) | |
tree | dff01bc6013cebaedf8f1fe65bba0b3fb9db5f40 /mert | |
parent | 39cf94984c3dddf85824bf0a08df438f5fb23b4a (diff) |
simplification of LineOptimizer code (same behaviour)
git-svn-id: https://mosesdecoder.svn.sourceforge.net/svnroot/mosesdecoder/trunk@1784 1f5c12ca-751b-0410-a591-d2e778427230
Diffstat (limited to 'mert')
-rw-r--r-- | mert/Optimizer.cpp | 230 |
1 files changed, 108 insertions, 122 deletions
diff --git a/mert/Optimizer.cpp b/mert/Optimizer.cpp index 332a86c1e..7e02251b1 100644 --- a/mert/Optimizer.cpp +++ b/mert/Optimizer.cpp @@ -67,16 +67,36 @@ float intersect (float m1, float b1,float m2,float b2){ return((b2-b1)/(m1-m2)); } +map<float,diff_t >::iterator AddThreshold(map<float,diff_t >& thresholdmap,float newt,pair<unsigned,unsigned> newdiff){ + map<float,diff_t>::iterator it=thresholdmap.find(newt); + if(it!=thresholdmap.end()){ + //the threshold already exists!! this is very unlikely + if(it->second.back().first==newdiff.first) + it->second.back().second=newdiff.second;//there was already a diff for this sentence, we change the 1 best; + else + it->second.push_back(newdiff); + }else{ + //normal case + pair< map<float,diff_t >::iterator,bool > ins=thresholdmap.insert(threshold(newt,diff_t(1,newdiff))); + assert(ins.second);//we really inserted something + it=ins.first; + } + return it; +}; + + statscore_t Optimizer::LineOptimize(const Point& origin,const Point& direction,Point& bestpoint)const{ - // we are looking for the best Point on the line y=Origin+x*direction +// we are looking for the best Point on the line y=Origin+x*direction float min_int=0.0001; - typedef pair<unsigned,unsigned> diff;//first the sentence that changes, second is the new 1best for this sentence - typedef pair<float,vector<diff> > threshold; - list<threshold> thresholdlist; - thresholdlist.push_back(threshold(MIN_FLOAT,vector<diff>())); - vector<unsigned> first1best;//the vector of nbrests for x=-inf + //typedef pair<unsigned,unsigned> diff;//first the sentence that changes, second is the new 1best for this sentence + //list<threshold> thresholdlist; + + map<float,diff_t> thresholdmap; + thresholdmap[MIN_FLOAT]=diff_t(); + vector<unsigned> first1best;//the vector of nbests for x=-inf for(int S=0;S<size();S++){ + map<float,diff_t >::iterator previnserted=thresholdmap.begin(); //first we determine the translation with the best feature score for each sentence and each value of x //cerr << "Sentence " << S << endl; multimap<float,unsigned> gradient; @@ -88,140 +108,107 @@ statscore_t Optimizer::LineOptimize(const Point& origin,const Point& direction,P } //now lets compute the 1best for each value of x - vector<pair<float,unsigned> > onebest; + // vector<pair<float,unsigned> > onebest; - multimap<float,unsigned>::iterator it=gradient.begin(); - float smallest=it->first;//smallest gradient + + multimap<float,unsigned>::iterator gradientit=gradient.begin(); multimap<float,unsigned>::iterator highest_f0=gradient.begin(); - + + float smallest=gradientit->first;//smallest gradient //several candidates can have the lowest slope (eg for word penalty where the gradient is an integer ) - it++; - while(it!=gradient.end()&&it->first==smallest){ - // cerr<<"ni"<<it->second<<endl;; - //cerr<<"fos"<<f0[it->second]<<" "<<f0[index]<<" "<<index<<endl; - if(f0[it->second]>f0[highest_f0->second]) - highest_f0=it;;//the highest line is the one with he highest f0 - it++; + + gradientit++; + while(gradientit!=gradient.end()&&gradientit->first==smallest){ + // cerr<<"ni"<<gradientit->second<<endl;; + //cerr<<"fos"<<f0[gradientit->second]<<" "<<f0[index]<<" "<<index<<endl; + if(f0[gradientit->second]>f0[highest_f0->second]) + highest_f0=gradientit;//the highest line is the one with he highest f0 + gradientit++; } - it = highest_f0; - onebest.push_back(pair<float,unsigned>(MIN_FLOAT,it->second));//first 1best is the lowest gradient. + + gradientit = highest_f0; + first1best.push_back(gradientit->second); + //now we look for the intersections points indicating a change of 1 best //we use the fact that the function is convex, which means that the gradient can only go up - while(it!=gradient.end()){ - map<float,unsigned>::iterator leftmost=it; - float m=it->first; - float b=f0[it->second]; - multimap<float,unsigned>::iterator it2=it; - it2++; + while(gradientit!=gradient.end()){ + map<float,unsigned>::iterator leftmost=gradientit; + float m=gradientit->first; + float b=f0[gradientit->second]; + multimap<float,unsigned>::iterator gradientit2=gradientit; + gradientit2++; float leftmostx=MAX_FLOAT; - for(;it2!=gradient.end();it2++){ - //cerr<<"--"<<d++<<' '<<it2->first<<' '<<it2->second<<endl; + for(;gradientit2!=gradient.end();gradientit2++){ + //cerr<<"--"<<d++<<' '<<gradientit2->first<<' '<<gradientit2->second<<endl; //look for all candidate with a gradient bigger than the current one and find the one with the leftmost intersection float curintersect; - if(m!=it2->first){ - curintersect=intersect(m,b,it2->first,f0[it2->second]); + if(m!=gradientit2->first){ + curintersect=intersect(m,b,gradientit2->first,f0[gradientit2->second]); //cerr << "curintersect: " << curintersect << " leftmostx: " << leftmostx << endl; if(curintersect<leftmostx){ - //we have found and intersection to the left of the leftmost we had so far. + //we have found an intersection to the left of the leftmost we had so far. leftmostx=curintersect; - leftmost=it2;//this is the new reference + leftmost=gradientit2;//this is the new reference } } } - if (leftmost == it) { + if (leftmost == gradientit) { //we didn't find any more intersections - break; + //the rightmost bestindex is the one with the highest slope. + assert(abs(leftmost->first-gradient.rbegin()->first)<0.0001);//they should be egal but there might be + //a small difference due to rounding error + break; } //we have found the next intersection! - /* Require that the intersection Point be at least min_int - to the right of the previous one. If not, we replace the - previous intersection Point with this one. Yes, it can even - happen that the new intersection Point is slightly to the - left of the old one, because of numerical imprecision. We - don't check that the new Point is also min_interval to the - right of the penultimate one. In that case, the Points would - switch places in the sort, resulting in a bogus score for - that interval. */ - if(abs(leftmostx-onebest.back().first)<min_int) { - onebest.back()=pair<float,unsigned>(leftmostx,leftmost->second);//leftmost->first is the gradient, we are interested in the value of the intersection - } else { //normal case: we add a new threshold - onebest.push_back(pair<float,unsigned>(leftmostx,leftmost->second)); - //cerr << "Intersect: x " << leftmostx << endl; + pair<unsigned,unsigned> newd(S,leftmost->second);//new onebest for Sentence S is leftmost->second + + if(leftmostx-previnserted->first<min_int){ + /* Require that the intersection Point be at least min_int + to the right of the previous one(for this sentence). If not, we replace the + previous intersection Point with this one. Yes, it can even + happen that the new intersection Point is slightly to the + left of the old one, because of numerical imprecision. + we do not check that we are to the right of the penultimate point also. it this happen the 1best the inteval will be wrong + */ + thresholdmap.insert(threshold(leftmostx,previnserted->second));//copy the diffs that were stored on previnserted + assert( thresholdmap[leftmostx].back().first==newd.first);//the last sentence of current.second should be S + thresholdmap[leftmostx].back()=newd;//replace last diff by the new one + thresholdmap.erase(previnserted);//erase previous + previnserted=thresholdmap.find(leftmostx); + }else{//normal insertion process + previnserted=AddThreshold(thresholdmap,leftmostx,newd); } - it=leftmost; - } - //we have the onebest list and the threshold for the current sentence. - //now we update the thresholdlist: we add the new threshold and the value of the onebest. - -/* - cerr << "Sentence: " << S << endl; - for (size_t i = 0; i < onebest.size(); ++i) { - cerr << "x: " << onebest[i].first << " i: " << onebest[i].second << " "; - } - cerr << endl; -*/ - - - //add the 1best for x=-inf to the corresponding threshold - // (this first threshold is the same for everybody) - first1best.push_back(onebest[0].second); - assert(first1best.size()==S+1); - - list<threshold >::iterator current=thresholdlist.begin(); - list<threshold >::iterator lit; - - - unsigned prev1best=onebest[0].second; - for(int t=1;t<onebest.size();t++){ - float ref=onebest[t].first; - for( lit=current;lit!=thresholdlist.end()&&ref>lit->first;lit++) - ; - //we have found where we must insert the new threshold(before lit) - if(lit==thresholdlist.end()){ - thresholdlist.push_back(threshold(ref,vector<diff>())); - lit--; - } - else - if(ref!=lit->first)//normal case - lit=thresholdlist.insert(lit,threshold(ref,vector<diff>())); - //if ref==lit->first:unlikely (but this is the reason why we have a vector of diff); in that case the threshold is already created - //lit is at the right place now we add the diff pair - lit->second.push_back(diff(S,onebest[t].second)); - current=lit;//we will continue after that point - current++; - prev1best=onebest[t].second; - }//loop on onebest.size() - }//loop on S + gradientit=leftmost; + } //while(gradientit!=gradient.end()){ + } //loop on S //now the thresholdlist is up to date: //it contains a list of all the parameter_ts where the function changed its value, along with the nbest list for the interval after each threshold - //last thing to do is compute the Stat score (ie BLEU) and find the minimum -/* - cerr << "Thresholds: " << endl; - for (list<threshold>::iterator i = thresholdlist.begin(); - i != thresholdlist.end(); ++i) { - cerr << "x: " << i->first << " diffs"; - for (size_t j = 0; j < i->second.size(); ++j) { - cerr << " " << i->second[j].first << "," << i->second[j].second; - } - cerr << endl; + map<float,diff_t >::iterator thrit; + if(verboselevel()>5){ + cerr << "Thresholds:(" <<thresholdmap.size()<<")"<< endl; + for (thrit = thresholdmap.begin();thrit!=thresholdmap.end();thrit++){ + cerr << "x: " << thrit->first << " diffs"; + for (size_t j = 0; j < thrit->second.size(); ++j) { + cerr << " " <<thrit->second[j].first << "," << thrit->second[j].second; + } + cerr << endl; + } } -*/ - - // cerr<<"thesholdlist size"<<thresholdlist.size()<<endl; - list<threshold>::iterator lit2=thresholdlist.begin(); - ++lit2; - vector<vector<diff> > diffs; - for(;lit2!=thresholdlist.end();lit2++) - diffs.push_back(lit2->second); + //last thing to do is compute the Stat score (ie BLEU) and find the minimum + thrit=thresholdmap.begin(); + ++thrit;//first diff corrrespond to MIN_FLOAT and first1best + diffs_t diffs; + for(;thrit!=thresholdmap.end();thrit++) + diffs.push_back(thrit->second); vector<statscore_t> scores=GetIncStatScore(first1best,diffs); - lit2=thresholdlist.begin(); + thrit=thresholdmap.begin(); statscore_t bestscore=MIN_FLOAT; float bestx=MIN_FLOAT; - assert(scores.size()==thresholdlist.size());//we skipped the first el of thresholdlist but GetIncStatScore return 1 more for first1best + assert(scores.size()==thresholdmap.size());//we skipped the first el of thresholdlist but GetIncStatScore return 1 more for first1best for(int sc=0;sc!=scores.size();sc++){ //cerr << "x=" << lit2->first << " => " << scores[sc] << endl; if (scores[sc] > bestscore) { @@ -235,16 +222,16 @@ statscore_t Optimizer::LineOptimize(const Point& origin,const Point& direction,P //take x to be the last interval boundary + 0.1, and for the leftmost //interval, take x to be the first interval boundary - 1000. //These values are taken from cmert. - float leftx = lit2->first; - if (lit2 == thresholdlist.begin()) { + float leftx = thrit->first; + if (thrit == thresholdmap.begin()) { leftx = MIN_FLOAT; } - ++lit2; + ++thrit; float rightx = MAX_FLOAT; - if (lit2 != thresholdlist.end()) { - rightx = lit2->first; + if (thrit != thresholdmap.end()) { + rightx = thrit->first; } - --lit2; + --thrit; //cerr << "leftx: " << leftx << " rightx: " << rightx << endl; if (leftx == MIN_FLOAT) { bestx = rightx-1000; @@ -255,11 +242,9 @@ statscore_t Optimizer::LineOptimize(const Point& origin,const Point& direction,P } //cerr << "x = " << "set new bestx to: " << bestx << endl; } - ++lit2; - - - + ++thrit; } + if(abs(bestx)<0.00015){ bestx=0.0;//the origin of the line is the best point!we put it back at 0 so we do not propagate rounding erros //finally! we manage to extract the best score; @@ -269,11 +254,12 @@ statscore_t Optimizer::LineOptimize(const Point& origin,const Point& direction,P } if(verboselevel()>3) cerr<<"end Lineopt, bestx="<<bestx<<endl; - bestpoint=direction*bestx+origin; + bestpoint=direction*bestx+origin; bestpoint.score=bestscore; return bestscore; }; + void Optimizer::Get1bests(const Point& P,vector<unsigned>& bests)const{ assert(FData); bests.clear(); |