Home | History | Annotate | Download | only in fst 
      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 (at) google.com (Kasturi Rangan Raghavan)
     16 // Inspiration: shumash (at) 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 
     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 
    116 template <class X1, class X2>
    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>
    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