00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "LatticeMBR.h"
00011 #include "moses/StaticData.h"
00012 #include <algorithm>
00013 #include <set>
00014
00015 using namespace std;
00016
00017 namespace Moses
00018 {
00019
00020 size_t bleu_order = 4;
00021 float UNKNGRAMLOGPROB = -20;
00022 void GetOutputWords(const TrellisPath &path, vector <Word> &translation)
00023 {
00024 const std::vector<const Hypothesis *> &edges = path.GetEdges();
00025
00026
00027 for (int currEdge = (int)edges.size() - 1 ; currEdge >= 0 ; currEdge--) {
00028 const Hypothesis &edge = *edges[currEdge];
00029 const Phrase &phrase = edge.GetCurrTargetPhrase();
00030 size_t size = phrase.GetSize();
00031 for (size_t pos = 0 ; pos < size ; pos++) {
00032 translation.push_back(phrase.GetWord(pos));
00033 }
00034 }
00035 }
00036
00037
00038 void extract_ngrams(const vector<Word >& sentence, map < Phrase, int > & allngrams)
00039 {
00040 for (int k = 0; k < (int)bleu_order; k++) {
00041 for(int i =0; i < max((int)sentence.size()-k,0); i++) {
00042 Phrase ngram( k+1);
00043 for ( int j = i; j<= i+k; j++) {
00044 ngram.AddWord(sentence[j]);
00045 }
00046 ++allngrams[ngram];
00047 }
00048 }
00049 }
00050
00051
00052
00053 void NgramScores::addScore(const Hypothesis* node, const Phrase& ngram, float score)
00054 {
00055 set<Phrase>::const_iterator ngramIter = m_ngrams.find(ngram);
00056 if (ngramIter == m_ngrams.end()) {
00057 ngramIter = m_ngrams.insert(ngram).first;
00058 }
00059 map<const Phrase*,float>& ngramScores = m_scores[node];
00060 map<const Phrase*,float>::iterator scoreIter = ngramScores.find(&(*ngramIter));
00061 if (scoreIter == ngramScores.end()) {
00062 ngramScores[&(*ngramIter)] = score;
00063 } else {
00064 ngramScores[&(*ngramIter)] = log_sum(score,scoreIter->second);
00065 }
00066 }
00067
00068 NgramScores::NodeScoreIterator NgramScores::nodeBegin(const Hypothesis* node)
00069 {
00070 return m_scores[node].begin();
00071 }
00072
00073
00074 NgramScores::NodeScoreIterator NgramScores::nodeEnd(const Hypothesis* node)
00075 {
00076 return m_scores[node].end();
00077 }
00078
00079 LatticeMBRSolution::LatticeMBRSolution(const TrellisPath& path, bool isMap) :
00080 m_score(0.0f)
00081 {
00082 const std::vector<const Hypothesis *> &edges = path.GetEdges();
00083
00084 for (int currEdge = (int)edges.size() - 1 ; currEdge >= 0 ; currEdge--) {
00085 const Hypothesis &edge = *edges[currEdge];
00086 const Phrase &phrase = edge.GetCurrTargetPhrase();
00087 size_t size = phrase.GetSize();
00088 for (size_t pos = 0 ; pos < size ; pos++) {
00089 m_words.push_back(phrase.GetWord(pos));
00090 }
00091 }
00092 if (isMap) {
00093 m_mapScore = path.GetFutureScore();
00094 } else {
00095 m_mapScore = 0;
00096 }
00097 }
00098
00099
00100 void LatticeMBRSolution::CalcScore(map<Phrase, float>& finalNgramScores, const vector<float>& thetas, float mapWeight)
00101 {
00102 m_ngramScores.assign(thetas.size()-1, -10000);
00103
00104 map < Phrase, int > counts;
00105 extract_ngrams(m_words,counts);
00106
00107
00108 m_score = thetas[0] * m_words.size();
00109
00110
00111 for (map < Phrase, int >::iterator ngrams = counts.begin(); ngrams != counts.end(); ++ngrams) {
00112 float ngramPosterior = UNKNGRAMLOGPROB;
00113 map<Phrase,float>::const_iterator ngramPosteriorIt = finalNgramScores.find(ngrams->first);
00114 if (ngramPosteriorIt != finalNgramScores.end()) {
00115 ngramPosterior = ngramPosteriorIt->second;
00116 }
00117 size_t ngramSize = ngrams->first.GetSize();
00118 m_ngramScores[ngramSize-1] = log_sum(log((float)ngrams->second) + ngramPosterior,m_ngramScores[ngramSize-1]);
00119 }
00120
00121
00122 for (size_t i = 0; i < m_ngramScores.size(); ++i) {
00123 m_ngramScores[i] = exp(m_ngramScores[i]);
00124 m_score += thetas[i+1] * m_ngramScores[i];
00125 }
00126
00127
00128
00129 m_score += m_mapScore*mapWeight;
00130 }
00131
00132
00133 void pruneLatticeFB(Lattice & connectedHyp, map < const Hypothesis*, set <const Hypothesis* > > & outgoingHyps, map<const Hypothesis*, vector<Edge> >& incomingEdges,
00134 const vector< float> & estimatedScores, const Hypothesis* bestHypo, size_t edgeDensity, float scale)
00135 {
00136
00137
00138 VERBOSE(2,"Pruning lattice to edge density " << edgeDensity << endl);
00139 const Hypothesis* emptyHyp = connectedHyp.at(0);
00140 while (emptyHyp->GetId() != 0) {
00141 emptyHyp = emptyHyp->GetPrevHypo();
00142 }
00143 connectedHyp.push_back(emptyHyp);
00144
00145
00146 for (size_t i = 0; i < connectedHyp.size(); ++i) {
00147 if (connectedHyp[i]->GetId() > 0 && connectedHyp[i]->GetPrevHypo()->GetId() == 0)
00148 outgoingHyps[emptyHyp].insert(connectedHyp[i]);
00149 }
00150
00151
00152 multimap<float, const Hypothesis*> sortHypsByVal;
00153 for (size_t i =0; i < estimatedScores.size(); ++i) {
00154 sortHypsByVal.insert(make_pair(estimatedScores[i], connectedHyp[i]));
00155 }
00156
00157 multimap<float, const Hypothesis*>::const_iterator it = --sortHypsByVal.end();
00158 float bestScore = it->first;
00159
00160 sortHypsByVal.insert(make_pair(bestScore, emptyHyp));
00161
00162
00163 IFVERBOSE(3) {
00164 for (multimap<float, const Hypothesis*>::const_iterator it = --sortHypsByVal.end(); it != --sortHypsByVal.begin(); --it) {
00165 const Hypothesis* currHyp = it->second;
00166 cerr << "Hyp " << currHyp->GetId() << ", estimated score: " << it->first << endl;
00167 }
00168 }
00169
00170
00171 set <const Hypothesis*> survivingHyps;
00172
00173 VERBOSE(2, "BEST HYPO TARGET LENGTH : " << bestHypo->GetSize() << endl)
00174 size_t numEdgesTotal = edgeDensity * bestHypo->GetSize();
00175 size_t numEdgesCreated = 0;
00176 VERBOSE(2, "Target edge count: " << numEdgesTotal << endl);
00177
00178 float prevScore = -999999;
00179
00180
00181 for (multimap<float, const Hypothesis*>::const_iterator it = --sortHypsByVal.end(); it != --sortHypsByVal.begin(); --it) {
00182 float currEstimatedScore = it->first;
00183 const Hypothesis* currHyp = it->second;
00184
00185 if (numEdgesCreated >= numEdgesTotal && prevScore > currEstimatedScore)
00186 break;
00187
00188 prevScore = currEstimatedScore;
00189 VERBOSE(3, "Num edges created : "<< numEdgesCreated << ", numEdges wanted " << numEdgesTotal << endl)
00190 VERBOSE(3, "Considering hyp " << currHyp->GetId() << ", estimated score: " << it->first << endl)
00191
00192 survivingHyps.insert(currHyp);
00193
00194
00195 if (survivingHyps.find(currHyp->GetPrevHypo()) != survivingHyps.end()) {
00196 vector <Edge>& edges = incomingEdges[currHyp];
00197 Edge winningEdge(currHyp->GetPrevHypo(),currHyp,scale*(currHyp->GetScore() - currHyp->GetPrevHypo()->GetScore()),currHyp->GetCurrTargetPhrase());
00198 edges.push_back(winningEdge);
00199 ++numEdgesCreated;
00200 }
00201
00202
00203 const ArcList *arcList = currHyp->GetArcList();
00204 if (arcList != NULL) {
00205 ArcList::const_iterator iterArcList;
00206 for (iterArcList = arcList->begin() ; iterArcList != arcList->end() ; ++iterArcList) {
00207 const Hypothesis *loserHypo = *iterArcList;
00208 const Hypothesis* loserPrevHypo = loserHypo->GetPrevHypo();
00209 if (survivingHyps.find(loserPrevHypo) != survivingHyps.end()) {
00210 double arcScore = loserHypo->GetScore() - loserPrevHypo->GetScore();
00211 Edge losingEdge(loserPrevHypo, currHyp, arcScore*scale, loserHypo->GetCurrTargetPhrase());
00212 vector <Edge>& edges = incomingEdges[currHyp];
00213 edges.push_back(losingEdge);
00214 ++numEdgesCreated;
00215 }
00216 }
00217 }
00218
00219
00220 map < const Hypothesis*, set < const Hypothesis* > >::const_iterator outgoingIt = outgoingHyps.find(currHyp);
00221
00222 if (outgoingIt != outgoingHyps.end()) {
00223 const set<const Hypothesis*> & outHyps = outgoingIt->second;
00224 for (set<const Hypothesis*>::const_iterator outHypIts = outHyps.begin(); outHypIts != outHyps.end(); ++outHypIts) {
00225 const Hypothesis* succHyp = *outHypIts;
00226
00227 if (survivingHyps.find(succHyp) == survivingHyps.end())
00228 continue;
00229
00230
00231 if (succHyp->GetPrevHypo() == currHyp) {
00232 vector <Edge>& succEdges = incomingEdges[succHyp];
00233 Edge succWinningEdge(currHyp, succHyp, scale*(succHyp->GetScore() - currHyp->GetScore()), succHyp->GetCurrTargetPhrase());
00234 succEdges.push_back(succWinningEdge);
00235 survivingHyps.insert(succHyp);
00236 ++numEdgesCreated;
00237 }
00238
00239
00240 const ArcList *arcList = succHyp->GetArcList();
00241 if (arcList != NULL) {
00242 ArcList::const_iterator iterArcList;
00243
00244 for (iterArcList = arcList->begin() ; iterArcList != arcList->end() ; ++iterArcList) {
00245 const Hypothesis *loserHypo = *iterArcList;
00246 const Hypothesis* loserPrevHypo = loserHypo->GetPrevHypo();
00247 if (loserPrevHypo == currHyp) {
00248 vector <Edge>& succEdges = incomingEdges[succHyp];
00249 double arcScore = loserHypo->GetScore() - currHyp->GetScore();
00250 Edge losingEdge(currHyp, succHyp,scale* arcScore, loserHypo->GetCurrTargetPhrase());
00251 succEdges.push_back(losingEdge);
00252 ++numEdgesCreated;
00253 }
00254 }
00255 }
00256 }
00257 }
00258 }
00259
00260 connectedHyp.clear();
00261 for (set <const Hypothesis*>::iterator it = survivingHyps.begin(); it != survivingHyps.end(); ++it) {
00262 connectedHyp.push_back(*it);
00263 }
00264
00265 VERBOSE(2, "Done! Num edges created : "<< numEdgesCreated << ", numEdges wanted " << numEdgesTotal << endl)
00266
00267 IFVERBOSE(3) {
00268 cerr << "Surviving hyps: " ;
00269 for (set <const Hypothesis*>::iterator it = survivingHyps.begin(); it != survivingHyps.end(); ++it) {
00270 cerr << (*it)->GetId() << " ";
00271 }
00272 cerr << endl;
00273 }
00274
00275
00276 }
00277
00278 void calcNgramExpectations(Lattice & connectedHyp, map<const Hypothesis*, vector<Edge> >& incomingEdges,
00279 map<Phrase, float>& finalNgramScores, bool posteriors)
00280 {
00281
00282 sort(connectedHyp.begin(),connectedHyp.end(),ascendingCoverageCmp);
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294 map<const Hypothesis*, float> forwardScore;
00295 forwardScore[connectedHyp[0]] = 0.0f;
00296 set< const Hypothesis *> finalHyps;
00297
00298 NgramScores ngramScores;
00299
00300 for (size_t i = 1; i < connectedHyp.size(); ++i) {
00301 const Hypothesis* currHyp = connectedHyp[i];
00302 if (currHyp->GetWordsBitmap().IsComplete()) {
00303 finalHyps.insert(currHyp);
00304 }
00305
00306 VERBOSE(3, "Processing hyp: " << currHyp->GetId() << ", num words cov= " << currHyp->GetWordsBitmap().GetNumWordsCovered() << endl)
00307
00308 vector <Edge> & edges = incomingEdges[currHyp];
00309 for (size_t e = 0; e < edges.size(); ++e) {
00310 const Edge& edge = edges[e];
00311 if (forwardScore.find(currHyp) == forwardScore.end()) {
00312 forwardScore[currHyp] = forwardScore[edge.GetTailNode()] + edge.GetScore();
00313 VERBOSE(3, "Fwd score["<<currHyp->GetId()<<"] = fwdScore["<<edge.GetTailNode()->GetId() << "] + edge Score: " << edge.GetScore() << endl)
00314 } else {
00315 forwardScore[currHyp] = log_sum(forwardScore[currHyp], forwardScore[edge.GetTailNode()] + edge.GetScore());
00316 VERBOSE(3, "Fwd score["<<currHyp->GetId()<<"] += fwdScore["<<edge.GetTailNode()->GetId() << "] + edge Score: " << edge.GetScore() << endl)
00317 }
00318 }
00319
00320
00321 for (size_t j =0 ; j < edges.size(); ++j) {
00322 Edge& edge = edges[j];
00323 const NgramHistory & incomingPhrases = edge.GetNgrams(incomingEdges);
00324
00325
00326 for (NgramHistory::const_iterator it = incomingPhrases.begin(); it != incomingPhrases.end(); ++it) {
00327 const Phrase& ngram = it->first;
00328 const PathCounts& pathCounts = it->second;
00329 VERBOSE(4, "Calculating score for: " << it->first << endl)
00330
00331 for (PathCounts::const_iterator pathCountIt = pathCounts.begin(); pathCountIt != pathCounts.end(); ++pathCountIt) {
00332
00333 const Path& path = pathCountIt->first;
00334
00335 float score = forwardScore[path[0]->GetTailNode()];
00336 for (size_t i = 0; i < path.size(); ++i) {
00337 score += path[i]->GetScore();
00338 }
00339
00340
00341 size_t count = posteriors ? 1 : pathCountIt->second;
00342 for (size_t k = 0; k < count; ++k) {
00343 ngramScores.addScore(currHyp,ngram,score);
00344 }
00345 }
00346 }
00347
00348
00349 for (NgramScores::NodeScoreIterator it = ngramScores.nodeBegin(edge.GetTailNode());
00350 it != ngramScores.nodeEnd(edge.GetTailNode()); ++it) {
00351 const Phrase & currNgram = *(it->first);
00352 float currNgramScore = it->second;
00353 VERBOSE(4, "Calculating score for: " << currNgram << endl)
00354
00355
00356 if (!posteriors || incomingPhrases.find(currNgram) == incomingPhrases.end()) {
00357 float score = edge.GetScore() + currNgramScore;
00358 ngramScores.addScore(currHyp,currNgram,score);
00359 }
00360 }
00361
00362 }
00363 }
00364
00365 float Z = 9999999;
00366
00367
00368 for (set< const Hypothesis *>::iterator finalHyp = finalHyps.begin(); finalHyp != finalHyps.end(); ++finalHyp) {
00369 const Hypothesis* hyp = *finalHyp;
00370
00371 for (NgramScores::NodeScoreIterator it = ngramScores.nodeBegin(hyp); it != ngramScores.nodeEnd(hyp); ++it) {
00372 const Phrase& ngram = *(it->first);
00373 if (finalNgramScores.find(ngram) == finalNgramScores.end()) {
00374 finalNgramScores[ngram] = it->second;
00375 } else {
00376 finalNgramScores[ngram] = log_sum(it->second, finalNgramScores[ngram]);
00377 }
00378 }
00379
00380 if (Z == 9999999) {
00381 Z = forwardScore[hyp];
00382 } else {
00383 Z = log_sum(Z, forwardScore[hyp]);
00384 }
00385 }
00386
00387
00388
00389 for (map<Phrase, float>::iterator finalScoresIt = finalNgramScores.begin(); finalScoresIt != finalNgramScores.end(); ++finalScoresIt) {
00390 finalScoresIt->second = finalScoresIt->second - Z;
00391 IFVERBOSE(2) {
00392 VERBOSE(2,finalScoresIt->first << " [" << finalScoresIt->second << "]" << endl);
00393 }
00394 }
00395
00396 }
00397
00398 const NgramHistory& Edge::GetNgrams(map<const Hypothesis*, vector<Edge> > & incomingEdges)
00399 {
00400
00401 if (m_ngrams.size() > 0)
00402 return m_ngrams;
00403
00404 const Phrase& currPhrase = GetWords();
00405
00406 for (size_t start = 0; start < currPhrase.GetSize(); ++start) {
00407 for (size_t end = start; end < start + bleu_order; ++end) {
00408 if (end < currPhrase.GetSize()) {
00409 Phrase edgeNgram(end-start+1);
00410 for (size_t index = start; index <= end; ++index) {
00411 edgeNgram.AddWord(currPhrase.GetWord(index));
00412 }
00413
00414 vector<const Edge*> edgeHistory;
00415 edgeHistory.push_back(this);
00416 storeNgramHistory(edgeNgram, edgeHistory);
00417 } else {
00418 break;
00419 }
00420 }
00421 }
00422
00423 map<const Hypothesis*, vector<Edge> >::iterator it = incomingEdges.find(m_tailNode);
00424 if (it != incomingEdges.end()) {
00425 vector<Edge> & inEdges = it->second;
00426
00427 for (vector<Edge>::iterator edge = inEdges.begin(); edge != inEdges.end(); ++edge) {
00428 const NgramHistory & edgeIncomingNgrams = edge->GetNgrams(incomingEdges);
00429 for (NgramHistory::const_iterator edgeInNgramHist = edgeIncomingNgrams.begin(); edgeInNgramHist != edgeIncomingNgrams.end(); ++edgeInNgramHist) {
00430 const Phrase& edgeIncomingNgram = edgeInNgramHist->first;
00431 const PathCounts & edgeIncomingNgramPaths = edgeInNgramHist->second;
00432 size_t back = min(edgeIncomingNgram.GetSize(), edge->GetWordsSize());
00433 const Phrase& edgeWords = edge->GetWords();
00434 IFVERBOSE(3) {
00435 cerr << "Edge: "<< *edge <<endl;
00436 cerr << "edgeWords: " << edgeWords << endl;
00437 cerr << "edgeInNgram: " << edgeIncomingNgram << endl;
00438 }
00439
00440 Phrase edgeSuffix(ARRAY_SIZE_INCR);
00441 Phrase ngramSuffix(ARRAY_SIZE_INCR);
00442 GetPhraseSuffix(edgeWords,back,edgeSuffix);
00443 GetPhraseSuffix(edgeIncomingNgram,back,ngramSuffix);
00444
00445 if (ngramSuffix == edgeSuffix) {
00446 size_t edgeInNgramSize = edgeIncomingNgram.GetSize();
00447
00448 for (size_t i = 0; i < GetWordsSize() && i + edgeInNgramSize < bleu_order ; ++i) {
00449 Phrase newNgram(edgeIncomingNgram);
00450 for (size_t j = 0; j <= i ; ++j) {
00451 newNgram.AddWord(GetWords().GetWord(j));
00452 }
00453 VERBOSE(3, "Inserting New Phrase : " << newNgram << endl)
00454
00455 for (PathCounts::const_iterator pathIt = edgeIncomingNgramPaths.begin(); pathIt != edgeIncomingNgramPaths.end(); ++pathIt) {
00456 Path newNgramPath = pathIt->first;
00457 newNgramPath.push_back(this);
00458 storeNgramHistory(newNgram, newNgramPath, pathIt->second);
00459 }
00460 }
00461 }
00462 }
00463 }
00464 }
00465 return m_ngrams;
00466 }
00467
00468
00469 void Edge::GetPhraseSuffix(const Phrase& origPhrase, size_t lastN, Phrase& targetPhrase) const
00470 {
00471 size_t origSize = origPhrase.GetSize();
00472 size_t startIndex = origSize - lastN;
00473 for (size_t index = startIndex; index < origPhrase.GetSize(); ++index) {
00474 targetPhrase.AddWord(origPhrase.GetWord(index));
00475 }
00476 }
00477
00478 bool Edge::operator< (const Edge& compare ) const
00479 {
00480 if (m_headNode->GetId() < compare.m_headNode->GetId())
00481 return true;
00482 if (compare.m_headNode->GetId() < m_headNode->GetId())
00483 return false;
00484 if (m_tailNode->GetId() < compare.m_tailNode->GetId())
00485 return true;
00486 if (compare.m_tailNode->GetId() < m_tailNode->GetId())
00487 return false;
00488 return GetScore() < compare.GetScore();
00489 }
00490
00491 ostream& operator<< (ostream& out, const Edge& edge)
00492 {
00493 out << "Head: " << edge.m_headNode->GetId()
00494 << ", Tail: " << edge.m_tailNode->GetId()
00495 << ", Score: " << edge.m_score
00496 << ", Phrase: " << edge.m_targetPhrase << endl;
00497 return out;
00498 }
00499
00500 bool ascendingCoverageCmp(const Hypothesis* a, const Hypothesis* b)
00501 {
00502 return (a->GetWordsBitmap().GetNumWordsCovered()
00503 <
00504 b->GetWordsBitmap().GetNumWordsCovered());
00505 }
00506
00507 void getLatticeMBRNBest(const Manager& manager, const TrellisPathList& nBestList,
00508 vector<LatticeMBRSolution>& solutions, size_t n)
00509 {
00510 std::map < int, bool > connected;
00511 std::vector< const Hypothesis *> connectedList;
00512 map<Phrase, float> ngramPosteriors;
00513 std::map < const Hypothesis*, set <const Hypothesis*> > outgoingHyps;
00514 map<const Hypothesis*, vector<Edge> > incomingEdges;
00515 vector< float> estimatedScores;
00516 manager.GetForwardBackwardSearchGraph(&connected, &connectedList,
00517 &outgoingHyps, &estimatedScores);
00518 LMBR_Options const& lmbr = manager.options()->lmbr;
00519 MBR_Options const& mbr = manager.options()->mbr;
00520 pruneLatticeFB(connectedList, outgoingHyps, incomingEdges, estimatedScores,
00521 manager.GetBestHypothesis(), lmbr.pruning_factor, mbr.scale);
00522 calcNgramExpectations(connectedList, incomingEdges, ngramPosteriors,true);
00523
00524 vector<float> mbrThetas = lmbr.theta;
00525 float p = lmbr.precision;
00526 float r = lmbr.ratio;
00527 float mapWeight = lmbr.map_weight;
00528 if (mbrThetas.size() == 0) {
00529
00530 mbrThetas.push_back(-1);
00531 mbrThetas.push_back(1/(bleu_order*p));
00532 for (size_t i = 2; i <= bleu_order; ++i) {
00533 mbrThetas.push_back(mbrThetas[i-1] / r);
00534 }
00535 }
00536 IFVERBOSE(2) {
00537 VERBOSE(2,"Thetas: ");
00538 for (size_t i = 0; i < mbrThetas.size(); ++i) {
00539 VERBOSE(2,mbrThetas[i] << " ");
00540 }
00541 VERBOSE(2,endl);
00542 }
00543 TrellisPathList::const_iterator iter;
00544 size_t ctr = 0;
00545 LatticeMBRSolutionComparator comparator;
00546 for (iter = nBestList.begin() ; iter != nBestList.end() ; ++iter, ++ctr) {
00547 const TrellisPath &path = **iter;
00548 solutions.push_back(LatticeMBRSolution(path,iter==nBestList.begin()));
00549 solutions.back().CalcScore(ngramPosteriors, mbrThetas, mapWeight);
00550 sort(solutions.begin(), solutions.end(), comparator);
00551 while (solutions.size() > n) {
00552 solutions.pop_back();
00553 }
00554 }
00555 VERBOSE(2,"LMBR Score: " << solutions[0].GetScore() << endl);
00556 }
00557
00558 vector<Word> doLatticeMBR(const Manager& manager, const TrellisPathList& nBestList)
00559 {
00560
00561 vector<LatticeMBRSolution> solutions;
00562 getLatticeMBRNBest(manager, nBestList, solutions,1);
00563 return solutions.at(0).GetWords();
00564 }
00565
00566 const TrellisPath doConsensusDecoding(const Manager& manager, const TrellisPathList& nBestList)
00567 {
00568 static const int BLEU_ORDER = 4;
00569 static const float SMOOTH = 1;
00570
00571
00572 const StaticData& staticData = StaticData::Instance();
00573 std::map < int, bool > connected;
00574 std::vector< const Hypothesis *> connectedList;
00575 map<Phrase, float> ngramExpectations;
00576 std::map < const Hypothesis*, set <const Hypothesis*> > outgoingHyps;
00577 map<const Hypothesis*, vector<Edge> > incomingEdges;
00578 vector< float> estimatedScores;
00579 manager.GetForwardBackwardSearchGraph(&connected, &connectedList, &outgoingHyps, &estimatedScores);
00580 LMBR_Options const& lmbr = manager.options()->lmbr;
00581 MBR_Options const& mbr = manager.options()->mbr;
00582 pruneLatticeFB(connectedList, outgoingHyps, incomingEdges, estimatedScores,
00583 manager.GetBestHypothesis(), lmbr.pruning_factor, mbr.scale);
00584 calcNgramExpectations(connectedList, incomingEdges, ngramExpectations,false);
00585
00586
00587
00588 float ref_length = 0.0f;
00589 for (map<Phrase,float>::const_iterator ref_iter = ngramExpectations.begin();
00590 ref_iter != ngramExpectations.end(); ++ref_iter) {
00591
00592
00593 if (ref_iter->first.GetSize() == 1) {
00594 ref_length += exp(ref_iter->second);
00595
00596 }
00597 }
00598
00599 VERBOSE(2,"REF Length: " << ref_length << endl);
00600
00601
00602 TrellisPathList::const_iterator iter;
00603 TrellisPathList::const_iterator best = nBestList.end();
00604 float bestScore = -100000;
00605
00606 for (iter = nBestList.begin() ; iter != nBestList.end() ; ++iter) {
00607 const TrellisPath &path = **iter;
00608 vector<Word> words;
00609 map<Phrase,int> ngrams;
00610 GetOutputWords(path,words);
00611
00612
00613
00614
00615
00616 extract_ngrams(words,ngrams);
00617
00618 vector<float> comps(2*BLEU_ORDER+1);
00619 float logbleu = 0.0;
00620 float brevity = 0.0;
00621 int hyp_length = words.size();
00622 for (int i = 0; i < BLEU_ORDER; ++i) {
00623 comps[2*i] = 0.0;
00624 comps[2*i+1] = max(hyp_length-i,0);
00625 }
00626
00627 for (map<Phrase,int>::const_iterator hyp_iter = ngrams.begin();
00628 hyp_iter != ngrams.end(); ++hyp_iter) {
00629 map<Phrase,float>::const_iterator ref_iter = ngramExpectations.find(hyp_iter->first);
00630 if (ref_iter != ngramExpectations.end()) {
00631 comps[2*(hyp_iter->first.GetSize()-1)] += min(exp(ref_iter->second), (float)(hyp_iter->second));
00632 }
00633
00634 }
00635 comps[comps.size()-1] = ref_length;
00636
00637
00638
00639
00640
00641
00642 float score = 0.0f;
00643 if (comps[0] != 0) {
00644 for (int i=0; i<BLEU_ORDER; i++) {
00645 if ( i > 0 ) {
00646 logbleu += log((float)comps[2*i]+SMOOTH)-log((float)comps[2*i+1]+SMOOTH);
00647 } else {
00648 logbleu += log((float)comps[2*i])-log((float)comps[2*i+1]);
00649 }
00650 }
00651 logbleu /= BLEU_ORDER;
00652 brevity = 1.0-(float)comps[comps.size()-1]/comps[1];
00653 if (brevity < 0.0) {
00654 logbleu += brevity;
00655 }
00656 score = exp(logbleu);
00657 }
00658
00659
00660 if (score > bestScore) {
00661 bestScore = score;
00662 best = iter;
00663 VERBOSE(2,"NEW BEST: " << score << endl);
00664
00665
00666
00667
00668 }
00669 }
00670
00671 assert (best != nBestList.end());
00672 return **best;
00673
00674
00675
00676 }
00677
00678 }
00679
00680