Implementation of Lattice sampling (Chatterjee and Cancedda, emnlp 2010)

git-svn-id: https://mosesdecoder.svn.sourceforge.net/svnroot/mosesdecoder/trunk@4295 1f5c12ca-751b-0410-a591-d2e778427230

8 files changed, 222 insertions, 17 deletions

diff --git a/moses/src/Manager.cpp b/moses/src/Manager.cpp
index c4ca7093c..9ceda2f84 100644
--- a/moses/src/Manager.cpp
+++ b/moses/src/Manager.cpp
@@ -25,6 +25,7 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 #include <ext/hash_set>
 #endif
 
+#include <algorithm>
 #include <limits>
 #include <cmath>
 #include "Manager.h"
@@ -257,6 +258,152 @@ void Manager::CalcNBest(size_t count, TrellisPathList &ret,bool onlyDistinct) co
   }
 }
 
+struct SGNReverseCompare {
+  bool operator() (const SearchGraphNode& s1, const SearchGraphNode& s2) const {
+    return s1.hypo->GetId() > s2.hypo->GetId();
+  }
+};
+
+/**
+  * Implements lattice sampling, as in Chatterjee & Cancedda, emnlp 2010
+  **/
+void Manager::CalcLatticeSamples(size_t count, TrellisPathList &ret) const {
+  
+  vector<SearchGraphNode> searchGraph;
+  GetSearchGraph(searchGraph);
+
+  //Calculation of the sigmas of each hypothesis and edge. In C&C notation this is
+  //the "log of the cumulative unnormalized probability of all the paths in the
+  // lattice for the hypothesis to a final node"
+  typedef pair<int, int> Edge;
+  map<const Hypothesis*, float> sigmas;
+  map<Edge, float> edgeScores;
+  map<const Hypothesis*, set<const Hypothesis*> > outgoingHyps;
+  map<int,const Hypothesis*> idToHyp;
+  map<int,float> fscores;
+
+  //Iterating through the hypos in reverse order of id gives  a reverse 
+  //topological order. We rely on the fact that hypo ids are given out 
+  //sequentially, as the search proceeds.
+  //NB: Could just sort by stack. 
+  sort(searchGraph.begin(), searchGraph.end(), SGNReverseCompare());
+
+  //first task is to fill in the outgoing hypos and edge scores.
+  for (vector<SearchGraphNode>::const_iterator i = searchGraph.begin();
+    i != searchGraph.end(); ++i) {
+    const Hypothesis* hypo = i->hypo;
+    idToHyp[hypo->GetId()] = hypo;
+    fscores[hypo->GetId()] = i->fscore;
+    if (hypo->GetId()) {
+      //back to  current
+      const Hypothesis* prevHypo = i->hypo->GetPrevHypo();
+      outgoingHyps[prevHypo].insert(hypo);
+      edgeScores[Edge(prevHypo->GetId(),hypo->GetId())] = 
+        hypo->GetScore() - prevHypo->GetScore();
+    }
+    //forward from current
+    if (i->forward >= 0) {
+      map<int,const Hypothesis*>::const_iterator idToHypIter = idToHyp.find(i->forward);
+      assert(idToHypIter != idToHyp.end());
+      const Hypothesis* nextHypo = idToHypIter->second;
+      outgoingHyps[hypo].insert(nextHypo);
+      map<int,float>::const_iterator fscoreIter = fscores.find(nextHypo->GetId());
+      assert(fscoreIter != fscores.end());
+      edgeScores[Edge(hypo->GetId(),nextHypo->GetId())] = 
+        i->fscore - fscoreIter->second;
+    }
+  }
+
+
+  //then run through again to calculate sigmas
+  for (vector<SearchGraphNode>::const_iterator i = searchGraph.begin();
+    i != searchGraph.end(); ++i) {
+
+    if (i->forward == -1) {
+      sigmas[i->hypo] = 0;
+    } else {
+      map<const Hypothesis*, set<const Hypothesis*> >::const_iterator outIter = 
+        outgoingHyps.find(i->hypo);
+      
+      assert(outIter != outgoingHyps.end());
+      float sigma = 0;
+      for (set<const Hypothesis*>::const_iterator j = outIter->second.begin();
+        j != outIter->second.end(); ++j) {
+        map<const Hypothesis*, float>::const_iterator succIter = sigmas.find(*j);
+        assert(succIter != sigmas.end());
+        map<Edge,float>::const_iterator edgeScoreIter = 
+          edgeScores.find(Edge(i->hypo->GetId(),(*j)->GetId()));
+        assert(edgeScoreIter != edgeScores.end());
+        float term = edgeScoreIter->second + succIter->second; // Add sigma(*j)
+        if (sigma == 0) {
+           sigma = term;
+        } else {
+          sigma = log_sum(sigma,term);
+        }
+      }
+      sigmas[i->hypo] = sigma;
+    }
+  }
+
+  //The actual sampling!
+  const Hypothesis* startHypo = searchGraph.back().hypo;
+  assert(startHypo->GetId() == 0);
+  for (size_t i = 0; i < count; ++i) {
+    vector<const Hypothesis*> path;
+    path.push_back(startHypo);
+    while(1) {
+      map<const Hypothesis*, set<const Hypothesis*> >::const_iterator outIter = 
+        outgoingHyps.find(path.back());
+      if (outIter == outgoingHyps.end() || !outIter->second.size()) {
+        //end of the path
+        break;
+      }
+      //score the possibles
+      vector<const Hypothesis*> candidates;
+      vector<float> candidateScores;
+      float scoreTotal = 0;
+      for (set<const Hypothesis*>::const_iterator j = outIter->second.begin();
+        j != outIter->second.end(); ++j) {
+        candidates.push_back(*j);
+        assert(sigmas.find(*j) != sigmas.end());
+        Edge edge(path.back()->GetId(),(*j)->GetId());
+        assert(edgeScores.find(edge) != edgeScores.end());
+        candidateScores.push_back(sigmas[*j]  + edgeScores[edge]);
+        if (scoreTotal == 0) {
+          scoreTotal = candidateScores.back();
+        } else {
+          scoreTotal = log_sum(candidateScores.back(), scoreTotal);
+        }
+      }
+
+      //normalise
+      transform(candidateScores.begin(), candidateScores.end(), candidateScores.begin(), bind2nd(minus<float>(),scoreTotal));
+      //copy(candidateScores.begin(),candidateScores.end(),ostream_iterator<float>(cerr," "));
+      //cerr << endl;
+
+      //draw the sample
+      float random = log((float)rand()/RAND_MAX);
+      size_t position = 1;
+      float sum = candidateScores[0];
+      for (; position < candidateScores.size() && sum < random; ++position) {
+        sum = log_sum(sum,candidateScores[position]);
+      }
+      //cerr << "Random: " << random << " Chose " << position-1 << endl;
+      const Hypothesis* chosen =  candidates[position-1];
+      path.push_back(chosen); 
+    }
+    //cerr << "Path: " << endl;
+    //for (size_t j = 0; j < path.size(); ++j) {
+     // cerr << path[j]->GetId() <<  " " << path[j]->GetScoreBreakdown() << endl;
+    //}
+    //cerr << endl;
+
+    //Convert the hypos to TrellisPath
+    ret.Add(new TrellisPath(path));
+    //cerr << ret.at(ret.GetSize()-1).GetScoreBreakdown() << endl;
+  } 
+
+}
 
 
 
diff --git a/moses/src/Manager.h b/moses/src/Manager.h
index 40b4c2caa..4b45414ee 100644
--- a/moses/src/Manager.h
+++ b/moses/src/Manager.h
@@ -130,6 +130,7 @@ public:
   const Hypothesis *GetBestHypothesis() const;
   const Hypothesis *GetActualBestHypothesis() const;
   void CalcNBest(size_t count, TrellisPathList &ret,bool onlyDistinct=0) const;
+  void CalcLatticeSamples(size_t count, TrellisPathList &ret) const;
   void PrintAllDerivations(long translationId, std::ostream& outputStream) const;
   void printDivergentHypothesis(long translationId, const Hypothesis* hypo, const std::vector <const TargetPhrase*> & remainingPhrases, float remainingScore , std::ostream& outputStream) const;
   void printThisHypothesis(long translationId, const Hypothesis* hypo, const std::vector <const TargetPhrase* > & remainingPhrases, float remainingScore , std::ostream& outputStream) const;
diff --git a/moses/src/Parameter.cpp b/moses/src/Parameter.cpp
index 109175e9c..d84bc701a 100644
--- a/moses/src/Parameter.cpp
+++ b/moses/src/Parameter.cpp
@@ -62,6 +62,7 @@ Parameter::Parameter()
   AddParam("max-trans-opt-per-coverage", "maximum number of translation options per input span (after applying mapping steps)");
   AddParam("max-phrase-length", "maximum phrase length (default 20)");
   AddParam("n-best-list", "file and size of n-best-list to be generated; specify - as the file in order to write to STDOUT");
+  AddParam("lattice-samples", "generate samples from lattice, in same format as nbest list. Uses the file and size arguments, as in n-best-list");
   AddParam("n-best-factor", "factor to compute the maximum number of contenders (=factor*nbest-size). value 0 means infinity, i.e. no threshold. default is 0");
   AddParam("print-all-derivations", "to print all derivations in search graph");
   AddParam("output-factors", "list of factors in the output");
diff --git a/moses/src/StaticData.cpp b/moses/src/StaticData.cpp
index d5f2520b0..a9a521cb8 100644
--- a/moses/src/StaticData.cpp
+++ b/moses/src/StaticData.cpp
@@ -81,8 +81,8 @@ StaticData::StaticData()
   ,m_numInputScores(0)
   ,m_detailedTranslationReportingFilePath()
   ,m_onlyDistinctNBest(false)
-  ,m_lmEnableOOVFeature(false)
   ,m_factorDelimiter("|") // default delimiter between factors
+  ,m_lmEnableOOVFeature(false)
   ,m_isAlwaysCreateDirectTranslationOption(false)
 {
   m_maxFactorIdx[0] = 0;  // source side
@@ -169,7 +169,7 @@ bool StaticData::LoadData(Parameter *parameter)
     m_nBestSize = Scan<size_t>( m_parameter->GetParam("n-best-list")[1] );
     m_onlyDistinctNBest=(m_parameter->GetParam("n-best-list").size()>2 && m_parameter->GetParam("n-best-list")[2]=="distinct");
   } else if (m_parameter->GetParam("n-best-list").size() == 1) {
-    UserMessage::Add(string("ERROR: wrong format for switch -n-best-list file size"));
+    UserMessage::Add(string("wrong format for switch -n-best-list file size"));
     return false;
   } else {
     m_nBestSize = 0;
@@ -180,6 +180,17 @@ bool StaticData::LoadData(Parameter *parameter)
     m_nBestFactor = 20;
   }
 
+  //lattice samples
+  if (m_parameter->GetParam("lattice-samples").size() ==2 ) {
+    m_latticeSamplesFilePath = m_parameter->GetParam("lattice-samples")[0];
+    m_latticeSamplesSize = Scan<size_t>(m_parameter->GetParam("lattice-samples")[1]);
+  } else if (m_parameter->GetParam("lattice-samples").size() != 0 ) {
+    UserMessage::Add(string("wrong format for switch -lattice-samples file size"));
+    return false;
+  } else {
+    m_latticeSamplesSize = 0;
+  }
+
   // word graph
   if (m_parameter->GetParam("output-word-graph").size() == 2)
     m_outputWordGraph = true;
diff --git a/moses/src/StaticData.h b/moses/src/StaticData.h
index 74a01b20f..706c8ec7c 100644
--- a/moses/src/StaticData.h
+++ b/moses/src/StaticData.h
@@ -112,6 +112,7 @@ protected:
   m_maxHypoStackSize //! hypothesis-stack size that triggers pruning
   , m_minHypoStackDiversity //! minimum number of hypothesis in stack for each source word coverage
   , m_nBestSize
+  , m_latticeSamplesSize
   , m_nBestFactor
   , m_maxNoTransOptPerCoverage
   , m_maxNoPartTransOpt
@@ -121,7 +122,7 @@ protected:
   std::string
   m_constraintFileName;
 
-  std::string									m_nBestFilePath;
+  std::string									m_nBestFilePath, m_latticeSamplesFilePath;
   bool                        m_fLMsLoaded, m_labeledNBestList,m_nBestIncludesAlignment;
   bool m_dropUnknown; //! false = treat unknown words as unknowns, and translate them as themselves; true = drop (ignore) them
   bool m_wordDeletionEnabled;
@@ -407,12 +408,20 @@ public:
     return m_nBestFilePath;
   }
   bool IsNBestEnabled() const {
-    return (!m_nBestFilePath.empty()) || m_mbr || m_useLatticeMBR || m_outputSearchGraph || m_useConsensusDecoding
+    return (!m_nBestFilePath.empty()) || m_mbr || m_useLatticeMBR || m_outputSearchGraph || m_useConsensusDecoding || !m_latticeSamplesFilePath.empty()
 #ifdef HAVE_PROTOBUF
            || m_outputSearchGraphPB
 #endif
            ;
   }
+  size_t GetLatticeSamplesSize() const {
+    return m_latticeSamplesSize;
+  }
+
+  const std::string& GetLatticeSamplesFilePath() const {
+    return m_latticeSamplesFilePath;
+  }
+
   size_t GetNBestFactor() const {
     return m_nBestFactor;
   }
diff --git a/moses/src/TrellisPath.cpp b/moses/src/TrellisPath.cpp
index f2a84d4ab..f50d57af4 100644
--- a/moses/src/TrellisPath.cpp
+++ b/moses/src/TrellisPath.cpp
@@ -41,6 +41,25 @@ TrellisPath::TrellisPath(const Hypothesis *hypo)
   }
 }
 
+void TrellisPath::InitScore() {
+  m_totalScore		= m_path[0]->GetWinningHypo()->GetTotalScore();
+  m_scoreBreakdown= m_path[0]->GetWinningHypo()->GetScoreBreakdown();
+
+  //calc score
+  size_t sizePath = m_path.size();
+  for (size_t pos = 0 ; pos < sizePath ; pos++) {
+    const Hypothesis *hypo = m_path[pos];
+    const Hypothesis *winningHypo = hypo->GetWinningHypo();
+    if (hypo != winningHypo) {
+      m_totalScore = m_totalScore - winningHypo->GetTotalScore() + hypo->GetTotalScore();
+      m_scoreBreakdown.MinusEquals(winningHypo->GetScoreBreakdown());
+      m_scoreBreakdown.PlusEquals(hypo->GetScoreBreakdown());
+    }
+  }
+
+
+}
+
 TrellisPath::TrellisPath(const TrellisPath &copy, size_t edgeIndex, const Hypothesis *arc)
   :m_prevEdgeChanged(edgeIndex)
 {
@@ -60,22 +79,20 @@ TrellisPath::TrellisPath(const TrellisPath &copy, size_t edgeIndex, const Hypoth
     prevHypo = prevHypo->GetPrevHypo();
   }
 
-  // Calc score
-  m_totalScore		= m_path[0]->GetWinningHypo()->GetTotalScore();
-  m_scoreBreakdown= m_path[0]->GetWinningHypo()->GetScoreBreakdown();
+  InitScore();
+}
+
+TrellisPath::TrellisPath(const vector<const Hypothesis*> edges) 
+:m_prevEdgeChanged(NOT_FOUND)
+{
+  m_path.resize(edges.size());
+  copy(edges.rbegin(),edges.rend(),m_path.begin());
+  InitScore();
+
 
-  size_t sizePath = m_path.size();
-  for (size_t pos = 0 ; pos < sizePath ; pos++) {
-    const Hypothesis *hypo = m_path[pos];
-    const Hypothesis *winningHypo = hypo->GetWinningHypo();
-    if (hypo != winningHypo) {
-      m_totalScore = m_totalScore - winningHypo->GetTotalScore() + hypo->GetTotalScore();
-      m_scoreBreakdown.MinusEquals(winningHypo->GetScoreBreakdown());
-      m_scoreBreakdown.PlusEquals(hypo->GetScoreBreakdown());
-    }
-  }
 }
 
+
 void TrellisPath::CreateDeviantPaths(TrellisPathCollection &pathColl) const
 {
   const size_t sizePath = m_path.size();
diff --git a/moses/src/TrellisPath.h b/moses/src/TrellisPath.h
index e746fafa1..166a58e7f 100644
--- a/moses/src/TrellisPath.h
+++ b/moses/src/TrellisPath.h
@@ -41,6 +41,7 @@ class TrellisPathList;
 class TrellisPath
 {
   friend std::ostream& operator<<(std::ostream&, const TrellisPath&);
+  friend class Manager;
 
 protected:
   std::vector<const Hypothesis *> m_path; //< list of hypotheses/arcs
@@ -51,7 +52,13 @@ protected:
   ScoreComponentCollection	m_scoreBreakdown;
   float m_totalScore;
 
+  //Used by Manager::LatticeSample()
+  TrellisPath(const std::vector<const Hypothesis*> edges);
+
+  void InitScore();
+
 public:
+
   TrellisPath(); // not implemented
 
   //! create path OF pure hypo
diff --git a/moses/src/Util.h b/moses/src/Util.h
index 93ba536aa..af4021e14 100644
--- a/moses/src/Util.h
+++ b/moses/src/Util.h
@@ -346,6 +346,18 @@ double GetUserTime();
 // dump SGML parser for <seg> tags
 std::map<std::string, std::string> ProcessAndStripSGML(std::string &line);
 
+template<class T>
+T log_sum (T log_a, T log_b)
+{
+  T v;
+  if (log_a < log_b) {
+    v = log_b+log ( 1 + exp ( log_a-log_b ));
+  } else {
+    v = log_a+log ( 1 + exp ( log_b-log_a ));
+  }
+  return ( v );
+}
+
 }
 
 #endif