Semirings in cdec

From cdec Decoder

Jump to: navigation, search

cdec implements a semiring framework using c++ templates. This enables you to write code that is both easy to read and executes very efficiently, for example:

double number_of_paths = Inside<double, TransitionCountWeightFunction>(forest);

This code snippet computes the total number of derivations in the forest (hyper)graph object using the well-known inside algorithm. The first template parameter is the c++ type used to represent values from the semiring (here, just the standard c++ type double). The second template parameter maps (hyper)edges from the forest object to a weight (i.e., a value) in the semiring. Here, TransitionCountWeightFunction assigns each edge the weight 1.0 (its definition is given as an example below).

Semirings in c++

Rather than defining an abstract semiring class with members like Multiply(...) or One(), we use standard c++ value type convention (this is more efficient, permits a number of standard c++ types, like int and double to be used as semirings, and produces concise, readable code).

semiring component c++ representation
<math>\overline{0}</math> T(), where T is the semiring value type, e.g. double
<math>\overline{1}</math> T(1)
<math>\oplus</math> operator+ (Inside<T,W> is implemented using T::operator+= only)
<math>\otimes</math> operator* (Inside<T,W> is implemented using T::operator*= only)

Note: users of the functions below must ensure that the semiring type T is, in fact, a semiring. That is, addition (+) must have identity T() and be commutative and associative. Multiplication (*) must have identity T(1) and distribute to the left over multiplication.

Weight functions

Weight functions map an object of type const Hypergraph::Edge& (which has a sparse vector of feature values and the rule from the SCFG that the edge represents). They should either be standard c++ functions or functor classes that define operator(). They take an edge object and return its value in the desired semiring.

Here is the weight function used to compute the total number of paths in the hypergraph:

struct TransitionCountWeightFunction {
  inline double operator()(const Hypergraph::Edge& e) const { return 1.0; }
};

Here is an example that returns the edge weight in a log-linear model:

struct EdgeProb {
  inline const prob_t& operator()(const Hypergraph::Edge& e) const { return e.feature_values_.dot(GlobalWeightVector()); }
};

Here is an example where the edge weight is the number of words in the e side:

struct ELengthWeightFunction {
  double operator()(const Hypergraph::Edge& e) const {
    return e.rule_->ELength() - e.rule_->Arity();
  }
};

Algorithms

The hypergraph library has three generic functions that compute quantities on a hypergraph using a user-specified weight function and semiring:

template<typename WeightType, typename WeightFunction>
WeightType Inside(const Hypergraph& hg); 

template<typename WeightType, typename WeightFunction>
void Outside(const Hypergraph& hg,
             const std::vector<WeightType>& inside_score);

template<typename PType, typename PWeightFunction, typename RType, typename RWeightFunction>
PType InsideOutside(const Hypergraph& hg,
                    RType* result_x);

Note that InsideOutside<> takes two types and two weight functions. The expression RType * PType must be valid and yield RType (thus, PType may be a scalar and RType a vector, but not vice versa). It is used to efficiently compute expected values where probability mass is expressed using PType and determined for an edge using PWeightFunction, and RType defines the type of the function whose expected value is sought. The function value of an edge is determined by applying RWeightFunction to it.

Alternatively, there is an implementation of the expectation semiring and an expectation weight function, which is parameterized by the same type pairs.

template <typename PType, typename RType> struct PRPair;

template <typename PType, typename PWeightFunction, typename RType, typename RWeightFunction>
struct PRWeightFunction;

For more information on these algorithms and expectation semirings, refer to Li and Eisner (EMNLP 2009).

Personal tools