inebriated, but sped up inside/outside pruning and made cube poplimit scale with promise of nodes from previous global pruning, if --promise_power=N for N>0.

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@219 ec762483-ff6d-05da-a07a-a48fb63a330f

1 files changed, 86 insertions, 23 deletions

diff --git a/decoder/inside_outside.h b/decoder/inside_outside.h
index 62daca1f..128d89da 100644
--- a/decoder/inside_outside.h
+++ b/decoder/inside_outside.h
@@ -34,8 +34,9 @@ WeightType Inside(const Hypergraph& hg,
   const int num_nodes = hg.nodes_.size();
   std::vector<WeightType> dummy;
   std::vector<WeightType>& inside_score = result ? *result : dummy;
+  inside_score.clear();
   inside_score.resize(num_nodes);
-  std::fill(inside_score.begin(), inside_score.end(), WeightType());
+//  std::fill(inside_score.begin(), inside_score.end(), WeightType()); // clear handles
   for (int i = 0; i < num_nodes; ++i) {
     const Hypergraph::Node& cur_node = hg.nodes_[i];
     WeightType* const cur_node_inside_score = &inside_score[i];
@@ -61,14 +62,17 @@ template<typename WeightType, typename WeightFunction>
 void Outside(const Hypergraph& hg,
              std::vector<WeightType>& inside_score,
              std::vector<WeightType>* result,
-             const WeightFunction& weight = WeightFunction()) {
+             const WeightFunction& weight = WeightFunction(),
+             WeightType scale_outside = WeightType(1)
+  ) {
   assert(result);
   const int num_nodes = hg.nodes_.size();
   assert(inside_score.size() == num_nodes);
   std::vector<WeightType>& outside_score = *result;
+  outside_score.clear();
   outside_score.resize(num_nodes);
-  std::fill(outside_score.begin(), outside_score.end(), WeightType());
-  outside_score.back() = WeightType(1);
+//  std::fill(outside_score.begin(), outside_score.end(), WeightType()); // cleared
+  outside_score.back() = scale_outside;
   for (int i = num_nodes - 1; i >= 0; --i) {
     const Hypergraph::Node& cur_node = hg.nodes_[i];
     const WeightType& head_node_outside_score = outside_score[i];
@@ -94,6 +98,80 @@ void Outside(const Hypergraph& hg,
   }
 }
 
+template <class K> // obviously not all semirings have a multiplicative inverse
+struct OutsideNormalize {
+  bool enable;
+  OutsideNormalize(bool enable=true) : enable(enable) {}
+  K operator()(K k) { return enable?K(1)/k:K(1); }
+};
+template <class K>
+struct Outside1 {
+  K operator()(K) { return K(1); }
+};
+
+template <class KType>
+struct InsideOutsides {
+//  typedef typename KWeightFunction::Weight KType;
+  typedef std::vector<KType> Ks;
+  Ks inside,outside;
+  KType root_inside() {
+    return inside.back();
+  }
+  InsideOutsides() {  }
+  template <class KWeightFunction>
+  KType compute(Hypergraph const& hg,KWeightFunction const& kwf=KWeightFunction()) {
+    return compute(hg,Outside1<KType>(),kwf);
+  }
+  template <class KWeightFunction,class O1>
+  KType compute(Hypergraph const& hg,O1 outside1,KWeightFunction const& kwf=KWeightFunction()) {
+    typedef typename KWeightFunction::Weight KType2;
+    assert(sizeof(KType2)==sizeof(KType)); // why am I doing this?  because I want to share the vectors used for tropical and prob_t semirings.  should instead have separate value type from semiring operations?  or suck it up and split the code calling in Prune* into 2 types (template)
+    typedef std::vector<KType2> K2s;
+    K2s &inside2=reinterpret_cast<K2s &>(inside);
+    Inside<KType2,KWeightFunction>(hg, &inside2, kwf);
+    KType scale=outside1(reinterpret_cast<KType const&>(inside2.back()));
+    Outside<KType2,KWeightFunction>(hg, inside2, reinterpret_cast<K2s *>(&outside), kwf, reinterpret_cast<KType2 const&>(scale));
+    return root_inside();
+  }
+// XWeightFunction::Result is result
+  template <class XWeightFunction>
+  typename XWeightFunction::Result expect(Hypergraph const& hg,XWeightFunction const& xwf=XWeightFunction())  {
+    typename XWeightFunction::Result x;      // default constructor is semiring 0
+    for (int i = 0,num_nodes=hg.nodes_.size(); i < num_nodes; ++i) {
+      const Hypergraph::Node& cur_node = hg.nodes_[i];
+      const int num_in_edges = cur_node.in_edges_.size();
+      for (int j = 0; j < num_in_edges; ++j) {
+        const Hypergraph::Edge& edge = hg.edges_[cur_node.in_edges_[j]];
+        KType kbar_e = outside[i];
+        const int num_tail_nodes = edge.tail_nodes_.size();
+        for (int k = 0; k < num_tail_nodes; ++k)
+          kbar_e *= inside[edge.tail_nodes_[k]];
+        x += xwf(edge) * kbar_e;
+      }
+    }
+    return x;
+  }
+  template <class V,class VWeight>
+  void compute_edge_marginals(Hypergraph const& hg,std::vector<V> &vs,VWeight const& weight) {
+    vs.resize(hg.edges_.size());
+    for (int i = 0,num_nodes=hg.nodes_.size(); i < num_nodes; ++i) {
+      const Hypergraph::Node& cur_node = hg.nodes_[i];
+      const int num_in_edges = cur_node.in_edges_.size();
+      for (int j = 0; j < num_in_edges; ++j) {
+        int edgei=cur_node.in_edges_[j];
+        const Hypergraph::Edge& edge = hg.edges_[edgei];
+        V x=weight(edge)*outside[i];
+        const int num_tail_nodes = edge.tail_nodes_.size();
+        for (int k = 0; k < num_tail_nodes; ++k)
+          x *= inside[edge.tail_nodes_[k]];
+        vs[edgei] = x;
+      }
+    }
+  }
+
+};
+
+
 // this is the Inside-Outside optimization described in Li and Eisner (EMNLP 2009)
 // for computing the inside algorithm over expensive semirings
 // (such as expectations over features).  See Figure 4.
@@ -105,25 +183,10 @@ KType InsideOutside(const Hypergraph& hg,
                     XType* result_x,
                     const KWeightFunction& kwf = KWeightFunction(),
                     const XWeightFunction& xwf = XWeightFunction()) {
-  const int num_nodes = hg.nodes_.size();
-  std::vector<KType> inside, outside;
-  const KType k = Inside<KType,KWeightFunction>(hg, &inside, kwf);
-  Outside<KType,KWeightFunction>(hg, inside, &outside, kwf);
-  XType& x = *result_x;
-  x = XType();      // default constructor is semiring 0
-  for (int i = 0; i < num_nodes; ++i) {
-    const Hypergraph::Node& cur_node = hg.nodes_[i];
-    const int num_in_edges = cur_node.in_edges_.size();
-    for (int j = 0; j < num_in_edges; ++j) {
-      const Hypergraph::Edge& edge = hg.edges_[cur_node.in_edges_[j]];
-      KType kbar_e = outside[i];
-      const int num_tail_nodes = edge.tail_nodes_.size();
-      for (int k = 0; k < num_tail_nodes; ++k)
-        kbar_e *= inside[edge.tail_nodes_[k]];
-      x += xwf(edge) * kbar_e;
-    }
-  }
-  return k;
+  InsideOutsides<KType> io;
+  io.compute(hg,kwf);
+  *result_x=io.expect(hg,xwf);
+  return io.root_inside();
 }
 
 #endif