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
39 namespace 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.
48 template <class X1, class X2>
49 class 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
ExpectationWeight()64 ExpectationWeight() : PairWeight<X1, X2>(Zero()) { }
65
ExpectationWeight(const ExpectationWeight<X1,X2> & w)66 ExpectationWeight(const ExpectationWeight<X1, X2>& w)
67 : PairWeight<X1, X2> (w) { }
68
ExpectationWeight(const PairWeight<X1,X2> & w)69 ExpectationWeight(const PairWeight<X1, X2>& w)
70 : PairWeight<X1, X2> (w) { }
71
ExpectationWeight(const X1 & x1,const X2 & x2)72 ExpectationWeight(const X1& x1, const X2& x2)
73 : PairWeight<X1, X2>(x1, x2) { }
74
Zero()75 static const ExpectationWeight<X1, X2> &Zero() {
76 static const ExpectationWeight<X1, X2> zero(X1::Zero(), X2::Zero());
77 return zero;
78 }
79
One()80 static const ExpectationWeight<X1, X2> &One() {
81 static const ExpectationWeight<X1, X2> one(X1::One(), X2::Zero());
82 return one;
83 }
84
NoWeight()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
Type()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
Reverse()100 ReverseWeight Reverse() const {
101 return PairWeight<X1, X2>::Reverse();
102 }
103
Member()104 bool Member() const {
105 return PairWeight<X1, X2>::Member();
106 }
107
Properties()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
116 template <class X1, class X2>
Plus(const ExpectationWeight<X1,X2> & w,const ExpectationWeight<X1,X2> & v)117 inline 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
124 template <class X1, class X2>
Times(const ExpectationWeight<X1,X2> & w,const ExpectationWeight<X1,X2> & v)125 inline 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
132 template <class X1, class X2>
133 inline 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