diff options
author | Chris Dyer <redpony@gmail.com> | 2014-03-18 01:41:17 -0400 |
---|---|---|
committer | Chris Dyer <redpony@gmail.com> | 2014-03-18 01:41:17 -0400 |
commit | 8e60188039211c9a585625dd8309f2ba57b0cbb2 (patch) | |
tree | 0ad14a94164d30f8b477958c06b14b9b7cccbbe3 /utils | |
parent | 6c04595f968f7a9c047c5941113752a7c7280b45 (diff) |
star function
Diffstat (limited to 'utils')
-rw-r--r-- | utils/Makefile.am | 2 | ||||
-rw-r--r-- | utils/exp_semiring.h | 64 | ||||
-rw-r--r-- | utils/logval.h | 12 | ||||
-rw-r--r-- | utils/star.h | 12 |
4 files changed, 90 insertions, 0 deletions
diff --git a/utils/Makefile.am b/utils/Makefile.am index a22b6727..c0ce3509 100644 --- a/utils/Makefile.am +++ b/utils/Makefile.am @@ -27,6 +27,7 @@ libutils_a_SOURCES = \ citycrc.h \ corpus_tools.h \ dict.h \ + exp_semiring.h \ fast_sparse_vector.h \ fdict.h \ feature_vector.h \ @@ -49,6 +50,7 @@ libutils_a_SOURCES = \ show.h \ small_vector.h \ sparse_vector.h \ + star.h \ static_utoa.h \ stringlib.h \ tdict.h \ diff --git a/utils/exp_semiring.h b/utils/exp_semiring.h new file mode 100644 index 00000000..7572ccf5 --- /dev/null +++ b/utils/exp_semiring.h @@ -0,0 +1,64 @@ +#ifndef _EXP_SEMIRING_H_ +#define _EXP_SEMIRING_H_ + +#include <iostream> +#include "star.h" + +// this file implements the first-order expectation semiring described +// in Li & Eisner (EMNLP 2009) + +// requirements: +// RType * RType ==> RType +// PType * PType ==> PType +// RType * PType ==> RType +// good examples: +// PType scalar, RType vector +// BAD examples: +// PType vector, RType scalar +template <class PType, class RType> +struct PRPair { + PRPair() : p(), r() {} + // Inside algorithm requires that T(0) and T(1) + // return the 0 and 1 values of the semiring + explicit PRPair(double x) : p(x), r() {} + PRPair(const PType& p, const RType& r) : p(p), r(r) {} + PRPair& operator+=(const PRPair& o) { + p += o.p; + r += o.r; + return *this; + } + PRPair& operator*=(const PRPair& o) { + r = (o.r * p) + (o.p * r); + p *= o.p; + return *this; + } + PType p; + RType r; +}; + +template <class P, class R> +std::ostream& operator<<(std::ostream& o, const PRPair<P,R>& x) { + return o << '<' << x.p << ", " << x.r << '>'; +} + +template <class P, class R> +const PRPair<P,R> operator+(const PRPair<P,R>& a, const PRPair<P,R>& b) { + PRPair<P,R> result = a; + result += b; + return result; +} + +template <class P, class R> +const PRPair<P,R> operator*(const PRPair<P,R>& a, const PRPair<P,R>& b) { + PRPair<P,R> result = a; + result *= b; + return result; +} + +template <class P, class R> +const PRPair<P,R> star(const PRPair<P,R>& x) { + const P pstar = star(x.p); + return PRPair<P,R>(pstar, pstar * x.r * pstar); +} + +#endif diff --git a/utils/logval.h b/utils/logval.h index ec1f6acd..7f1e1024 100644 --- a/utils/logval.h +++ b/utils/logval.h @@ -11,6 +11,7 @@ #include <cassert> #include "semiring.h" #include "show.h" +#include "star.h" //TODO: template for supporting negation or not - most uses are for nonnegative "probs" only; probably some 10-20% speedup available template <class T> @@ -242,4 +243,15 @@ bool operator>=(const LogVal<T>& lhs, const LogVal<T>& rhs) { template <class T> std::size_t hash_value(const LogVal<T>& x) { return x.hash_impl(); } +template <class T> +LogVal<T> star(LogVal<T> x) { + if (x.is_0()) return x; + if (x.v_ >= 0) { + x.v_ = std::numeric_limits<T>::infinity(); + } else { + x.v_ = -log1p(-x.as_float()); + } + return x; +} + #endif diff --git a/utils/star.h b/utils/star.h new file mode 100644 index 00000000..3295112c --- /dev/null +++ b/utils/star.h @@ -0,0 +1,12 @@ +#ifndef _STAR_H_ +#define _STAR_H_ + +template <typename T> +T star(const T& x) { + if (!x) return T(); + if (x > T(1)) return std::numeric_limits<T>::infinity(); + if (x < -T(1)) return -std::numeric_limits<T>::infinity(); + return T(1) / (T(1) - x); +} + +#endif |