expectation-weight.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2 
1
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6//     http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13//
14// Copyright 2005-2010 Google, Inc.
15// Author: krr@google.com (Kasturi Rangan Raghavan)
16// Inspiration: shumash@google.com (Masha Maria Shugrina)
17// \file
18// Expectation semiring as described by Jason Eisner:
19// See: doi=10.1.1.22.9398
20// Multiplex semiring operations and identities:
21//    One: <One, Zero>
22//    Zero: <Zero, Zero>
23//    Plus: <a1, b1> + <a2, b2> = < (a1 + a2) , (b1 + b2) >
24//    Times: <a1, b1> * <a2, b2> = < (a1 * a2) , [(a1 * b2) + (a2 * b1)] >
25//    Division: Undefined (currently)
26//
27// Usually used to store the pair <probability, random_variable> so that
28// ShortestDistance[Fst<ArcTpl<ExpectationWeight<P, V> > >]
29//    == < PosteriorProbability, Expected_Value[V] >
30
31#ifndef FST_LIB_EXPECTATION_WEIGHT_H_
32#define FST_LIB_EXPECTATION_WEIGHT_H_
33
34#include<string>
35
36#include <fst/pair-weight.h>
37
38
39namespace fst {
40
41// X1 is usually a probability weight like LogWeight
42// X2 is usually a random variable or vector
43//    see SignedLogWeight or SparsePowerWeight
44//
45// If X1 is distinct from X2, it is required that there is an external
46// product between X1 and X2 and if both semriring are commutative, or
47// left or right semirings, then result must have those properties.
48template <class X1, class X2>
49class ExpectationWeight : public PairWeight<X1, X2> {
50 public:
51  using PairWeight<X1, X2>::Value1;
52  using PairWeight<X1, X2>::Value2;
53
54  using PairWeight<X1, X2>::Reverse;
55  using PairWeight<X1, X2>::Quantize;
56  using PairWeight<X1, X2>::Member;
57
58  typedef X1 W1;
59  typedef X2 W2;
60
61  typedef ExpectationWeight<typename X1::ReverseWeight,
62                            typename X2::ReverseWeight> ReverseWeight;
63
64  ExpectationWeight() : PairWeight<X1, X2>(Zero()) { }
65
66  ExpectationWeight(const ExpectationWeight<X1, X2>& w)
67      : PairWeight<X1, X2> (w) { }
68
69  ExpectationWeight(const PairWeight<X1, X2>& w)
70      : PairWeight<X1, X2> (w) { }
71
72  ExpectationWeight(const X1& x1, const X2& x2)
73      : PairWeight<X1, X2>(x1, x2) { }
74
75  static const ExpectationWeight<X1, X2> &Zero() {
76    static const ExpectationWeight<X1, X2> zero(X1::Zero(), X2::Zero());
77    return zero;
78  }
79
80  static const ExpectationWeight<X1, X2> &One() {
81    static const ExpectationWeight<X1, X2> one(X1::One(), X2::Zero());
82    return one;
83  }
84
85  static const ExpectationWeight<X1, X2> &NoWeight() {
86    static const ExpectationWeight<X1, X2> no_weight(X1::NoWeight(),
87                                                     X2::NoWeight());
88    return no_weight;
89  }
90
91  static const string &Type() {
92    static const string type = "expectation_" + X1::Type() + "_" + X2::Type();
93    return type;
94  }
95
96  PairWeight<X1, X2> Quantize(float delta = kDelta) const {
97    return PairWeight<X1, X2>::Quantize();
98  }
99
100  ReverseWeight Reverse() const {
101    return PairWeight<X1, X2>::Reverse();
102  }
103
104  bool Member() const {
105    return PairWeight<X1, X2>::Member();
106  }
107
108  static uint64 Properties() {
109    uint64 props1 = W1::Properties();
110    uint64 props2 = W2::Properties();
111    return props1 & props2 & (kLeftSemiring | kRightSemiring |
112                              kCommutative | kIdempotent);
113  }
114};
115
116template <class X1, class X2>
117inline ExpectationWeight<X1, X2> Plus(const ExpectationWeight<X1, X2> &w,
118                                      const ExpectationWeight<X1, X2> &v) {
119  return ExpectationWeight<X1, X2>(Plus(w.Value1(), v.Value1()),
120                                   Plus(w.Value2(), v.Value2()));
121}
122
123
124template <class X1, class X2>
125inline ExpectationWeight<X1, X2> Times(const ExpectationWeight<X1, X2> &w,
126                                       const ExpectationWeight<X1, X2> &v) {
127  return ExpectationWeight<X1, X2>(Times(w.Value1(), v.Value1()),
128                                   Plus(Times(w.Value1(), v.Value2()),
129                                        Times(w.Value2(), v.Value1())));
130}
131
132template <class X1, class X2>
133inline ExpectationWeight<X1, X2> Divide(const ExpectationWeight<X1, X2> &w,
134                                        const ExpectationWeight<X1, X2> &v,
135                                        DivideType typ = DIVIDE_ANY) {
136  FSTERROR() << "ExpectationWeight::Divide: not implemented";
137  return ExpectationWeight<X1, X2>::NoWeight();
138}
139
140}  // namespace fst
141
142#endif  // FST_LIB_EXPECTATION_WEIGHT_H_
143