[PDF] Function Sequence Table User Manual - Emerson

View - Download Function Sequence Table User Manual - Emerson

Previous PDF

Next PDF

A tutorial

on ?nite-state text processing

Kyle Gorman

City University of New York

Google Inc.

Outline

Formal preliminaries

OpenFst and friends:

the past... ...and the future...

Key FST algorithms

A few worked examples

Formal preliminaries

(image: credit: Wikimedia Commons) Sets A set is an abstract, unordered collection of distinct objects, the membersof that set. By convention capital italic letters denote sets and lowercase letters to denote their members. Set membership is indicated with the2symbol; e.g.,x2Xis read "xis a member ofX". The empty set is denoted by?.

Subsets

A setXis said to be asubsetof another setYjust in the case that every member ofXis also a member ofY. The subset relationship is indicated with thesymbol; e.g.,XYis read as "Xis a subset ofY".

Union and intersection

Theunionof two sets,X[Y, is the set that contains just those elements which are members ofX,Y, or both.

X[Y:=fx:x2X_x2Yg

Theintersectionof two sets,X\Y, is the set that contains just those elements which are members of bothXandY.

X\Y:=fx:x2X^x2Yg

Strings

Letbe analphabet(i.e., a ?nite set of symbols). Astring(orword) is any ?nite ordered sequence of symbols such that each symbol is a member of. By convention typewriter text is used to denote strings. The empty string is denoted by. String sets are also known as languages.

Concatenation and closure

Theconcatenationof two languages,X Y, consists of all strings formed by concatenating a string inXwith a string inY.

X Y:=fx y:x2X;y2Yg

Theclosureof a language,X, is an in?nite language consisting of zero or more "self-concatenations" ofXwith itself. X :=fg [X?[X?[X?::: :=fg [X[X X[X X X:::

Regular languages (Kleene, ????)

The empty language?is a regular language.

The empty string languagefgis a regular language.

Ifs2, then the singleton languagefsgis a regular language. IfXis a regular language, then its closureXis a regular language.

IfX;Yare regular languages, then:

their concatenationX Yis a regular language, and their unionX[Yis a regular language.

Other languages are not regular languages.

Regular languages in the ??th century

Regular languages were ?rst de?ned by Kleene (????) and popularized in part by their discussion in the context of theChomsky(-Schützenberger) hierarchy (e.g. Chomsky and Miller, ????). Not long afterwards this was followed by two seemingly negative results: Traditional phrase structure grammars belong to a higher class in the hierarchy, thecontext-free languages The class of regular languages are not "learnable" under Gold"s (????) notion oflanguage identi?cation in the limit.

Regular languages in the ??st century

However, an enormous amount of linguistically-interesting phenomena can be described in terms of regular languages (and regular relations)... And, many of these phenomena fall into provably learnable subsets of the regular languages (e.g. Heinz, ????; Rogers et al., ????; Chandlee et al., ????; Jardine and Heinz, ????; Chandlee et al., ????).

Finite-state acceptors (after Mohri, ????)

An?nite-state acceptor(FSA) is a ?-tuple consisting of: a set of statesQ, a initial (or "start") states2Q, a set of ?nal statesFQ, an alphabet, and a transition relationmappingQ ¹[ fgºontoQ.

Acceptance

Let us extendusing the following recurrence:

Then, a stringw2isacceptedby the FSA just in the case that

¹s;wº 2F.

Regular relations

In many cases we are not interested in sets of strings so much as relations or functions between sets of strings. Thecross-productof two languages,XYis one such relation: it maps any string inXonto any string inY.

XY=fx7!y:x2X;y2Yg

Subsets of the cross-product of two regular languages are known as regular relations.

Finite-state transducers

A?nite-state transducer(FST) is a ?-tuple consisting of: a set of statesQ, a initial (or "start") states2Q, a set of ?nal statesFQ, an input alphabet, an output alphabet, a transition relationmappingQ ¹[ fgºontoQ. an output relationmappingQ ¹[ fgºonto.

Transduction

We can similarly extendusing the following recurrence: As before, a stringw2istransducedjust in the case that¹s;wº 2F, and in this case the output is given by¹s;wº; that is,w7!¹s;wº.

Weights

We can also add weights to transitions (and ?nal states) subject so long as the weights and their operations de?ne asemiring(Mohri, ????).

OpenFst and friends

Ancient forebears

The Xerox toolkit (XFST; Beesley and Karttunen ????)

The AT&T toolkit (FSM; Mohri et al. ????)

Competitors (see Gorman, ????)

Carmel (Knight and Graehl, ????)

HFST (Lindén et al., ????)

Foma (Hulden, ????)

Kleene (Beesley, ????)

OpenFst (Allauzen et al., ????)

OpenFst is a open-source C???? library for weighted ?nite state transducers developed at Google. Among other things, it is used in: Speech recognizers (e.g., Kaldi and many commercial products)

Speech synthesizers (as part of the "front-end")

Input method engines (e.g., mobile text entry systems)

OpenFst design

There are (at least) four layers to OpenFst:

A C?? template/header library in?fst/*.h?

A C?? "scripting" library in?fst/script/*.{h,cc}?

CLI programs in/usr/local/bin/fst*

A Python extension modulepywrapfst

OpenFst extensionsI

./configure... -enable-compress(Mohri et al., ????): FST compression -enable-linear-fsts(Wu et al., ????): encodes linear models as WFSTs -enable-pdt(Allauzen and Riley, ????): pushdown transducer reprsentations and algorithms -enable-ngram-fsts(Sorensen and Allauzen, ????): LOUDS compression for n-gram models encoded as WFSAs

OpenGrmI

Baum-Welch (Gorman, forthcoming): CLI tools and libraries for performing expectation maximization on WFSTs NGram (Roark et al., ????): CLI tools and libraries for building conventional n-gram language models encoded as WFSTs Thrax (Roark et al., ????): DSL-based compiler for WFST-based grammar development SFst (Allauzen and Riley, ????): CLI tools and libraries for building stochastic FSTs All these are available under an Apache ?.? license, and all use the same binary serialization as OpenFst.

OpenFst conventionsI

FST and symbol table objects implement copy-on-write (COW) semantics; copy methods and constructors make shallow copies and run in constant-time.

Iterators are invalidated by mutation operations.

Both acceptors and transducers, weighted or unweighted, are represented as weighted transducers.

FST state IDs are integers starting at zero.

At most one state can be designated as a start state; an empty

FST-one with no states-has a start state of -?.

Arc labels are non-negative integers; ? is reserved forand negative integers are reserved for implementation. Every state is associated with a?nal weight; non-?nal states have an in?nite ?nal weight

Ý? and ?nal states have a non-Ý? weight.

Pynini conventions

Some algorithms are inherentlyconstructive; others are naturaly destructive. Pynini adopts the following conventions: Constructive algorithms are implemented as module-level functions which return a new FST. Destructive algorithms are implemented as instance methods which mutate the instance they"re invoked on. Furthermore: where possible, destructive methods returnselfso that they can be chained, and destructive algorithms also can be invoked constructively using module-level functions.

WFST algorithms

Concatenation

The concatenationABcan computed destructively (onA) using A.concat(B)or constructively usingA ? B. The algorithm works by adding an-arc from every ?nal state inAto the initial state ofB. Union The unionAjBcan be computed destructively (onA) using A.union(B)or constructively usingA | B. The algorithm introduces an-arc from the initial state ofAto the initial state ofB.

Closure

The closureAcan be computed destructively usingA.closure(), or constructively usingclosure(A). The algorithm introduces-arcs from all ?nal states to the initial state.

Composition

The compositionABcan be computed constructively usingA @ Bor compose(A, B). By default, non-(co)accessible states are trimmed.

Cross-product

The cross-product functiontransducerconstructively computes the

cross-product transducerT=AB. It is de?ned roughly as follows:def_transducer(ifst?: Fst, ifst?: Fst) -? Fst:

upper ? arcmap(ifst?, map_type? output_epsilon lower ? arcmap(ifst?, map_type? input_epsilon return compose(upper.rmepsilon(), lower.rmepsilon(), compose_filter? match

Optimization

An WFST is said to be optimal if it isminimal. Minimization algorithms, in turn, require that their input also bedeterministic(and they preserve that property). In Pynini,Fstobjects have a built-in method optimizewhich applies a generic routine for optimization.

Optimization for unweighted acceptors

def _optimize(fst: Fst) -? Fst: opt_props ? NO_EPSILONS | I_DETERMINISTIC props ? fst.properties(opt_props, True) fst ? fst.copy() if not props | NO_EPSILONS: fst.rmepsilon() if not props | I_DETERMINISTIC: fst ? determinize(fst) return fst.minimize() This will produce an optimal FSA for any acyclic acceptor over an idempotent semiring.

Advanced optimization

However,some weighted cyclic FSAs are not determinizable(Mohri, ????, ????). Therefore we determinize and minimize the FSAas if it were an unweighted acceptor. Similarly,not all transducers are determinizable. We instead determinize and minimize the WFSTas if it were an unweighted acceptor. In both cases, we also performarc-sum mappingas a post-process.

Rewrite rule compilation

The context-dependent rewrite rule compilation functioncdrewrite constructively expands an SPE-like phonological rule speci?cation into a transducer using the Mohri and Sproat (????) algorithm.

Shortest path

Theshortest pathfunctionshortestpathconstructively computes the (n-)shortest paths in a WFST. In case of ties, library behavior is deterministic but implementation-de?ned. Unique paths can be obtained by determinizing the WFST on the ?y.

Examples

Rule-based g?p

Consider a simple example: (Latin American, mainland) Spanish grapheme-to-phoneme conversion: https://gist.github.com/kylebgorman/

Pair n-gram g?p

Following Novak et al. (????):

Train a unigram grapheme-to-phoneme aligner using expectation maximization Using the unigram aligner, decode the training data using the shortest-path algorithm to obtain best alignments

Encode the alignments as an unweighted acceptor

Train a conventional high-order n-gram model on the encoded alignments Decode the alignments to obtain a weighted transducerquotesdbs_dbs17.pdfusesText_23

[PDF] fst settat cours

[PDF] fst settat cycle d'ingénieur

[PDF] fst settat inscription 2017 2018

[PDF] fst settat licence professionnelle

[PDF] fst settat licence professionnelle 2017

[PDF] fst settat resultat preselection 2017

[PDF] fst tanger inscription 2017 2018

[PDF] fstbm inscription 2017

[PDF] fste errachidia site officiel

[PDF] fstg marrakech ac ma

[PDF] fstm les list principale bcg 2016 2017

[PDF] fstm liste admis 2017

[PDF] fstm mohammedia inscription en ligne 2017

[PDF] fstm préinscription 2017

[PDF] fsts inscription 2017