OpenFst Forum 2008 Archive

Patch for GNU autotools including libtool for OpenFst 20080422

DavidShao - 28 Dec 2008 - 00:41

patch -p1 -E < ../toautotools_openfst_20080422_20081227.diff
autoreconf --install --force
./configure --prefix=$HOME/busr CPPFLAGS="-I/opt/local/include" LDFLAGS="-L/opt/local/lib"
make
make check
make install

I have enabled make check using tests already provided in OpenFst so that one can test whether modules can be dlopened. All tests pass for all platforms except Cygwin on Windows XP. Even for Cygwin on Windows XP, this patch enables a dynamic linked library to be built such that OCRopus is able to use it to pass its own OpenFst tests. (There is an additional failure of one OCRopus test, test-fst-search2.lua, on Mac OS X and FreeBSD.)

My preliminary investigation for Cygwin on Windows XP appears to show that something is going wrong with reinterpret_cast-ing the read() function so that it can be recovered using a map in both fst/lib/register.h and fst/bin/main.h. The pointer to this function appears to be immediately recovered if the map is accessed right after it is stored, but a later GetEntry() returns a null pointer.

I believe that using GNU autotools to provide dynamic linked libraries is an essential step to helping more wide distribution of OpenFst through standard platform package or port managers. I think the current patch just about finishes this task other than the above problem for Cygwin. I also have not tested this patch on any 64-bit platforms other than an Intel Macbook running Mac OS X.

DavidShao - 28 Dec 2008 - 00:42

Determinize, Sequentialize, Subsequentialize

KennethRBeesley - 11 Nov 2008 - 14:17

Any mind-tuning that you could offer would be much appreciated.

Ken

CyrilAllauzen - 13 Nov 2008 - 14:15

In the weighted automaton case, the implementation follows exactly Mohri's paper. The weighted transducer is dealt by considering weighted transducer over seminiring K as weighted automaton over the semiring obtained by taking the cross product of the string semiring and the semiring K.

Cyril

Determinize and functional transducers

KennethRBeesley - 11 Nov 2008 - 14:10

Thanks,

Ken

CyrilAllauzen - 13 Nov 2008 - 16:35

Best, Cyril

ThomasDeniau - 11 Nov 2009 - 00:06

Request: Determinize in place

KennethRBeesley - 10 Sep 2008 - 23:44

Thanks,

Ken

CyrilAllauzen - 24 Sep 2008 - 17:27

KennethRBeesley - 24 Sep 2008 - 21:46

In my own work (a programming language built on top of OpenFst) an assignment statement like

$net = a*b+[w-z]? ;

causes the right-hand side to be evaluated (by calling various functions in the OpenFst library) and in a symbol table the name $net is bound to a Java Fst object that stores (as a Java long int) the pointer to the resulting C++ Fst object. That pointer is my handle from the Java world to the Fst object in the C++ universe. If I then type

$net2 = $net ;

then $net2 becomes an alias for the same Java Fst object that contains the pointer to the original C++ Fst object. (If I really want to make a copy, I've got a copy function that relies on the Map() function in the OpenFst library.)

With RmEpsilon(&A), I can remove the epsilons from the original C++ Fst object in place, and both $net and $net2 still reference the same Java Fst object that still contains the pointer to the original C++ Fst object. If I could (at least superficially) also Determinize() that original Fst object in place, life would be a bit easier for me. With the existing Determinize(A, &B), a new C++ Fst object B is created, which usually causes my language to create a new Java Fst object to wrap it; and I've got to worry about changing the pointer in the original Java Fst object (the value, in the symbol table, of $net and any aliases like $net2) and deleting the original C++ object A to prevent a kind of memory leak.

So I now understand why Determinize(A, &B) is as it is, but I do still suggest that I and perhaps others would find a new Determinize(&A) useful and intuitively parallel to RmEpsilon(&A) and Minimize(&A), so that all could be performed "in place".

Best,

Ken

CyrilAllauzen - 14 Oct 2008 - 11:59

I understand that what you describe is a rather unsastisfying way of wrapping. However, I not sure I understand why this is the only of wrapping. Anyhow, you can easily add a Determinize(&A) as follows:

template <class Arc>
void Determinize(MutableFst<Arc> *fst) {
  *fst = DeterminizeFst<Arc>(*fst, 
                             DeterminizeFstOptions(CacheOptions(true, 0)));
}

Best, Cyril

StateIterator and the Start state

KennethRBeesley - 21 Aug 2008 - 14:28

for (StateIterator<StdFst> siter(fst); !siter.Done(); siter.Next()) {
     StateId state_id = siter.Value() ;
     ...
}

is the first state_id returned from the Iterator always the Start state of the Fst?

Thanks,

Ken

CyrilAllauzen - 02 Sep 2008 - 11:39

Best, Cyril

Failure transitions

ChrisHarris - 21 Jul 2008 - 14:56

Great effort to build this library - there are so many uses - it's very nice to have such knowledgeable people building this for everyone. Thank you!

I'm interested in doing some language modeling with this library which I anticipate will require backoff weights that are commonly going to build paths which will be "better" than the proper path for certain n-grams.

I know you guys implemented failure transitions in the GRM library for LM purposes, and later an algorithm to replace them with epsilon transitions along with some compression heuristics to reduce the size of the final machines to address this exact problem.

My question is: What's the best route to take to implement this for the OpenFST project? If I take this on myself... should I create a new FST class to implement failure transitions? Or can I get away with just building a new Arc class which can trick the search functions for composition?

Thanks again for your help!

Chris

CyrilAllauzen - 21 Jul 2008 - 16:56

There is an undocumented support for failure transitions in composition. This feature is not documented and the handling of failure transitions will change significantly in the next version of the library.

For now, you can label failure transitions with kPhiLabel (you will need to use the C++ library for this, Fsts containing transitions labeled by kPhiLabel cannot be written to a file).

To perform composition with failure transitions, you need to use

ComposeFst<Arc>(fst1, fst2, ComposeFstOptions<COMPOSE_FST1_PHI>())

ComposeFst<Arc>(fst1, fst2, ComposeFstOptions<COMPOSE_FST2_PHI>())

Best, Cyril

ChrisHarris - 21 Jul 2008 - 20:03

Out of curiosity, what's the new implementaiton going to be? Something along the lines of a custom Arc/State/Fsm class?

Chris

ChrisHarris - 23 Jul 2008 - 19:39

I noticed that during composition with failure transitions, the composition does not chase down the transitive closure of both epsilon and failure transitions.

You can reproduce the behavior by having a state with a failure transition lead to a state with an epsilon transition - which in turn leads to a state with a real symbol arc on it. For example an FSA with the following makeup: 0 1 -2 -2 1 2 0 0 2 3 1 1 3

When you do composition with an FST containing only that real symbol (symbol 1 in the above case) - I would expect it to yield a connected machine (failure -> epsilon -> symbol) - which it does not. Instead it looks through the state with the failure transition and sees no matching symbol (only an epsilon transition) and aborts composition.

I tried to fix the problem, but couldn't quite figure out a good way to do so. The logic to chase down the transitive closure of failure transitions is making assumptions on the structure of the FST (deterministic w.r.t. failure transitions, or at least that they're all equally good, because it takes the first one it finds which yields a match) which probably means any fix I make will be short lived anyway.

If you'd like more information, please let me know, otherwise I'll just try another workaround - but I don't think fixing it in the current implementation is worthwhile... do you?

Chris

CyrilAllauzen - 31 Jul 2008 - 18:42

Indeed, I should have mentioned this: failure and epsilon transitions do not work together. You should also have at most 1 failure transition at a given state.

Cyril

Interactive manual testing of an FST

KennethRBeesley - 07 Jul 2008 - 11:53

CyrilAllauzen - 09 Jul 2008 - 18:11

You could benefit from lazy operations when the number of strings in ResultFst is large and you don't want to display all these strings (or even don't want to compute all of ResultFst). Instead, you could rewrite your code to generate all paths to work for a non-expanded FST and to stop once a fixed number of strings have been found (you could even ask to the user if he wants to see more strings then).

Best, Cyril

Easy way to query the number of paths in an FST?

// Mapper from StdArc to LogArc.
// orig. from lib/map.h
// struct StdToLogMapper {
struct ModifiedStdToLogMapper {
 typedef StdArc FromArc;
 typedef LogArc ToArc;

 // orig
 //LogArc operator()(const StdArc &arc) const {
 // return LogArc(arc.ilabel, arc.olabel, arc.weight.Value(), arc.nextstate);
 //}

 // KRB, change weight of all arcs to LogWeight::One()
 LogArc operator()(const StdArc &arc) const {
 return LogArc(arc.ilabel, arc.olabel, LogWeight::One(), arc.nextstate);
 }

 // KRB: also need to change the exit weight of all final states to
 // LogWeight::One()

 // KRB, will this do it?
 MapFinalAction FinalAction() const { return MAP_REQUIRE_SUPERFINAL; }

 // MAP_NO_SUPERFINAL, the final weight is mapped to a final weight
 //
 // MAP_ALLOW_SUPERFINAL, final weight mapped to an arc to the
 // superfinal state, if the result cannot be represented as a final
 // weight (see below?); superfinal state created only if needed)
 //
 // MAP_REQUIRE_SUPERFINAL, final weight mapped to an arc to the
 // superfinal state, unless the weight can be represented as a final
 // weight of weight Zero(). superfinal state always created. (N.B. the
 // weight of the superfinal state is set to Weight::One())

 uint64 Properties(uint64 props) const { return props; }
};

#include "fst/lib/fstlib.h"
#include <iostream>
// iostream gives access to cout

using namespace fst ;

// From map.h
// Mapper to map all non-Zero() weights to One().
//template <class A, class B = A>
//struct RmWeightMapper {
//  typedef A FromArc;
//  typedef B ToArc;
//  typedef typename FromArc::Weight FromWeight;
//  typedef typename ToArc::Weight ToWeight;
//  B operator()(const A &arc) const {
//    ToWeight w = arc.weight != FromWeight::Zero() ?
//                   ToWeight::One() : ToWeight::Zero();
//    return B(arc.ilabel, arc.olabel, w, arc.nextstate);
//  }

//  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }

//  uint64 Properties(uint64 props) const {
//    return props & kWeightInvariantProperties | kUnweighted;
//  }
//}

typedef VectorFst<LogArc> LogVectorFst ;
typedef Fst<LogArc>       LogFst ;
typedef LogArc::StateId StateId ;

// pathCount  return the number of paths in an FST
// (this version assumes that the input is a StdVectorFst)

int pathCount(const StdVectorFst &sfst) {
        // if the fst has loops, then the language or relation 
   // encoded by the FST is infinite, just return -1
   if (sfst.Properties(kCyclic, true)) {
      return -1 ;
   }
   // copy the FST input to a new unweighted network, 
   // over the Log Semiring
   LogVectorFst lfst ;

   // for each original StdArc, if the weight is _not_
   // TropicalWeight::Zero() then change it to LogWeight::One(),
   // else (when the weight is TropicalWeight::Zero()) change it to
   // LogWeight::Zero().  This is handily done with
   // RmWeightMapper(), which is in the library.

   Map(sfst, &lfst, RmWeightMapper<StdArc, LogArc>()) ;

   vector<LogArc::Weight> distance ;
   ShortestDistance(lfst, &distance, true) ;

   // from the distance vector, get the weight for the start state
   LogArc::Weight w = distance[lfst.Start()] ;

   // w.Value() is the -log of the number of paths
   // cout << "Weight from pathCount(): " << w << endl ;
   // so make w positive and get the exp()
   int paths = exp((double)(-1.0 * w.Value())) ;
   // cout << "Paths from pathCount(): " << paths << endl ; 
   return paths ;
}

// a trivial main() that tests pathCount()
//
int main() {
  // Create a little FST over the Tropical Semiring

  StdVectorFst fst ;
  fst.AddState() ;  // will be state 0
  fst.SetStart(0) ;

  fst.AddState() ;  // will be state 1
  fst.AddState() ;  // will be state 2

  // add some arcs
  fst.AddArc(0, StdArc(1, 1, 0.693, 1)) ; // arc from 0 to 1
  fst.AddArc(0, StdArc(2, 2, 0.693, 1)) ; // arc from 0 to 1
  fst.AddArc(0, StdArc(7, 7, 0.0, 1)) ;

  fst.AddArc(1, StdArc(3, 3, 0.693, 2)) ; // arc from 1 to 2
  fst.AddArc(1, StdArc(4, 4, 0.693, 2)) ; // arc from 1 to 2
  fst.AddArc(1, StdArc(5, 5, 0.693, 2)) ;
  fst.AddArc(0, StdArc(8, 8, 0.0, 2)) ;
  // Uncomment the following line to create a cycle/loop,
  // which makes the language or relation infinite.
  //fst.AddArc(1, StdArc(5, 5, 0.0, 1)) ;

  fst.SetFinal(2, 0.693) ;

  int count = pathCount(fst) ;
  cout << "Path Count from main(): " << count << endl << endl ;
  return 0 ;
}

About Factoring Algorithm of WFST

Here is a patch to use CMake for builds (tested on Linux and Mac OS X)

Performs build, tests, and installation. Could generate for Cygwin and even Visual Studio; might work with the former, but code is of course UNIX-specific, so won't build with the latter. Can't upload here, so download from: http://lemurz.org/io/wp-content/uploads/2008/05/OpenFst-beta-20080422-cmakep1.patch.gz	TomMurray	12 May 2008 - 17:42
Small update to install header files with 'make install': http://lemurz.org/io/wp-content/uploads/2008/05/OpenFst-beta-20080422-cmakep2.patch.gz	TomMurray	12 May 2008 - 19:03

SymbolTable::size()

Efficient Way of Taking the Union of Several FSTs

possible bug in fstdeterminize in case of log semiring

cat test.txt
4 0 74 0 0.00274658203
4 1 74 0 5.89324951
4 3 20364 0 0.0282592773
4 2 20364 0 3.57971692
4 5 0 1 -1.0986321
0 5 0 1 -4.69826591e-06
0 2 20364 0 3.68112183
0 3 20364 0 0.0255126953
1 5 0 1
1 2 20364 0
2 5 0 1
3 5 0 1
5

fstcompile --arc_type=log test.txt | fstdeterminize | fstprint
0 1 0 1 -1.0986321
0 2 74 0 -1.51862259e-05
0 3 20364 0 -1.98714133e-05
1
2 1 0 1 0.000163570745
2 3 20364 0 0.000163570745
3 1 0 1 4.95321437e-05

fsmcompile -t -s log test.txt | fsmdeterminize | fsmprint 
0 1 0 1 -1.0986321
0 2 74 0 -1.51862259e-05
0 3 20364 0 -1.98714133e-05
1 
2 1 0 1 -4.6852183e-06
2 3 20364 0 -4.68526787e-06
3 1 0 1 -7.15111692e-10

LM using FST

 fsmprint lm.fsm | fstcompile > lm.fst 

compilation gotcha with spaces in directory names

Input and output alphabets

Interpreting complement character ranges

Mindtuning: value of separate input and output symbol tables?

OpenFst allows the use of separate input and output symbol tables for mapping symbol names (strings) to the integers used as labels on an Fst. So, for examples, the label 2 on the input side could be mapped to 'a', and the label 2 on the output side could be mapped to 'b'. 1. What's the perceived value of allowing separate input and output mappings? 2. In practice, is it most common to use the same symbol table for both sides? Thanks, Ken	KennethRBeesley	04 Mar 2008 - 11:53
Actually, it is very common to have different symbol tables for each side. For instance, if you a lexicon that maps prononciation of words, i.e. sequence of phonemes, to words. The input symbol table would contains "phonemes" and the output table words. This is a real example from speech recognition (cf. this paper)	CyrilAllauzen	04 Mar 2008 - 11:59
Yes, that's a good example. Thanks. In my own work, at least, I would tend to want individual alphabetic symbols like 'a', 'b' and 'c' to be stored (by default) on arcs with their standard Unicode code point values, including IPA symbols in a speech application; and any symbols with multicharacter print names (including whole words, as in the speech-recognition example) would be stored with code point values from a Unicode Private Use Area. Unicode currently offers 137,468 Private Use code points--is that enough for all the words and other multicharacter symbols (e.g. ngrams of phoneme characters) used in a typical speech application?	KennethRBeesley	05 Mar 2008 - 15:43
Unfortunately, this solution would not be satisfying for speech recognition. Some very large vocabulary speech recognition systems use vocabularies consisting of several million words (i.e. multicharacter symbols). Allowing users to define their own input and output symbol tables is the most general approach. For your work, the approach you describe may be more than adequate, and the library indeed allows you to have the same symbol table used as both input and output table for all your FSTs. Cyril	CyrilAllauzen	06 Mar 2008 - 10:55

"Normalizing" arc/final weights on an FST?

I am using FSTs to represent probabilistic finite-state automata and there are various situations in which I need to "normalize" them--that is, scale the arc weights such that the probability of arcs leading out of a state (plus the probability of state finality) sums to 1 for each state. I am having trouble, however, figuring out how to modify the weights on arcs of an FST. I have tried the following code, and while this modifies the final weight appropriately, it doesn't affect the arc weights at all: void makeProper(VectorFst<StdArc> &fst) { using fst::TropicalWeight; for(StateIterator<VectorFst<StdArc> > siter(fst); !siter.Done(); siter.Next()) { int s = siter.Value(); float tot = pow(2, -1 * fst.Final(s).Value()); for(ArcIterator<VectorFst<StdArc> > aiter(fst,s); ! aiter.Done(); aiter.Next()) { StdArc arc = aiter.Value(); float contribution = pow(2, -1 * arc.weight.Value()); tot += contribution; } float adjustment = -1 * log(tot) / log(2); float newFinal = fst.Final(s).Value() - adjustment; fst.SetFinal(s,TropicalWeight(newFinal)); for(ArcIterator<VectorFst<StdArc> > aiter(fst,s); ! aiter.Done(); aiter.Next()) { StdArc arc = aiter.Value(); float newWeight = arc.weight.Value() - adjustment; arc.weight = TropicalWeight(0.0); } } } How can I modify the arc weights? Or is there some other functionality I haven't noticed yet that performs this normalization on its own? Many thanks once again, Roger	RogerLevy	02 Mar 2008 - 23:34
Ahh...my naive attempt to use ... was not entirely successful. My full query with properly-indented code can be found here: http://idiom.ucsd.edu/~rlevy/normalize_fst_weights Roger	RogerLevy	02 Mar 2008 - 23:37
Hi Roger, 1. In order to modify an arc, you need to use a MutableArcIterator instead of an ArcIterator. Then do aiter.SetValue(arc) at the end of your last for loop. The constructor of aiter should then also take &fst as an argument instead of fst. 2. There is an operation to normalize the weights in the way you describe. It is call pushing: Push(&fst, REWEIGHT_TO_INITIAL) However, pushing is defined using the semiring operation, hence in your case you'll need to push in the log semiring. VectorFst<StdArc> fst; VectorFst<LogArc> log_fst; Map(fst, &log_fst, StdToLogMapper()); Push(&log_fst, REWEIGHT_TO_INITIAL); Map(log_fst, &fst, LogToStdMapper()); The total weight will still be present at the initial state. You can remove it by doing after calling Push: vector<LogWeight> distance; ShortestDistance(log_fst, &distance, true); LogWeight total = distance[log_fst->Start()]; MutableArcIterator< VectorFst<LogArc> > aiter(&log_fst, log_fst->Start()); for (; !aiter.Done(); aiter.Next()) { LogArc arc = aiter.Value(); arc.weight = Divide(arc.weight, total); aiter.SetValue(); } P.S. I didn't compile the code so there might be some typos. P.P.S. I fixed the formating of your original post.	CyrilAllauzen	04 Mar 2008 - 11:25
Many thanks once more, Cyril. (The last call needed to be aiter.SetValue(arc) but that was easy enough to figure out.) The approach I was taking had an error in it, anyway, so Push is much better. Best Roger	RogerLevy	04 Mar 2008 - 22:50
One other question: is there an easy way of making LogArc and LogWeight operate in base 2 logs rather than in natural logs? Roger	RogerLevy	05 Mar 2008 - 17:52
Unfortunately, they are no easy way to do this. Cyril	CyrilAllauzen	06 Mar 2008 - 10:44
Got it. Also, I notice that RealWeight and RealArc are not yet implemented, is this correct? (they would be convenient for transparent post-hoc inspection of normalized log-semiring FSTs.) Best Roger	RogerLevy	08 Mar 2008 - 15:56
No RealWeight yet. The reason was we never used the real semiring for anything else than toy example with the FSM library. But, we might decide to add it to the next release since people seem to request it. Best, Cyril	CyrilAllauzen	11 Mar 2008 - 11:59

Natural code for printing all strings accepted by an FST?

void printAllStrings(VectorFst<StdArc> &fst) {
  vector<int> str(0);
  printAllStringsHelper(fst, 0, str, 0.0);
}
void printAllStringsHelper(VectorFst<StdArc> &fst, int state, vector<int> str, float cost) {
  if(fst.Final(state).Value() < 100000)
    cout << vectorToString(str) << " with cost " << (cost + fst.Final(state).Value()) << endl;
  for(ArcIterator<VectorFst<StdArc> > aiter(fst,state); ! aiter.Done(); aiter.Next()) {
    StdArc arc = aiter.Value();
    str.push_back(arc.ilabel);
    printAllStringsHelper(fst, arc.nextstate, str, cost + arc.weight.Value());
    str.pop_back();
  }
}
string itos(int i) {   // convert int to string; from Bjarne Stroustrup's FAQ
  stringstream s;
  s << i;
  return s.str();
}
string vectorToString(vector<int> v) {
  if(v.size() == 0)
    return "<>";
  string result = "<" + itos(v[0]);
  for(int i = 1; i < v.size(); i++) {
    result +=  "," + itos(v[i]);
  }
  return result + ">";
}

if (fst.Final(state) == Weight::Zero()) // if state is not final 

TropicalWeight cost

  Times(cost, arc.weight) 

Why is TropicalWeight considered standard?

In another word, why does StdArc use TropicalWeight instead of FloatWeight or LogWeight. Is there some material that explains the significance of TropicalWeight? Also, what's the reason that there are Plus(), Times() and Divide() implemented for FloatWeight()? Because it is too trivial?	JiaPu	29 Feb 2008 - 18:57
sorry, type. It should read: ".... there are NOT Plus() ..."	JiaPu	29 Feb 2008 - 18:58
sorry, typo. It should read: ".... there are NOT Plus() ..."	JiaPu	29 Feb 2008 - 18:58
StdArc use TropicalWeight and LogArc use LogWeight. StdArc could have been call TropicalArc, but since it is the most commonly used [it correspond to the Viterbi approximation] a shorter name like StdArc was prefered. If you don't like it, you can still do: typedef StdArc TropicalArc; FloatWeight is just an abstract class from which LogWeight and TropicalWeight are derived. It does not correspond to a semiring, that's why it does not have Plus(), Times(), ...	CyrilAllauzen	04 Mar 2008 - 11:43
For the significance of the tropical semiring, you can check out the papers in FstBackground or this paper or that one.	CyrilAllauzen	04 Mar 2008 - 11:50
Cyril, Please give me an algebra 101. According to the definition of semiring on wiki, float (or rational number) is a semiring. And when authorizing finite state grammar for speech recognition, it is more natural to use float as weight. Although, internally log weight is preferred.	JiaPu	04 Mar 2008 - 15:23
Float in FloatWeight only means than the underlying representation is a C/C++ float type. TropicalWeight and LogWeight both use C/C++ float to represent real numbers, hence they are both derived from the partially abstract type FloatWeight. Of course, the real number with as operation the usual plus and times is also a semiring. It is not implemented in the library for now because it is not very commonly used. We might add it in a future version. If we do, it will also be as a type derived from FloatWeight. Float just defines the set, it is not enough to define a semiring. Different times and plus operations would lead to different semiring sharing the same set of elements. Finally, you didn't have to all the way to wikipedia, there is some documentation on here on this website.	CyrilAllauzen	04 Mar 2008 - 19:10

Compiler error on Determinize().

New Release of OpenFst?

StdVectorFst in;
StdVectorFst out;
Map(in, &out, IdentityMapper<StdArc>());

Another newbie question

Access control:

• Set ALLOWTOPICCHANGE = AllAuthUsersGroup