文件名称:
Weighted Finite-State Transducers Important Algorithms
开发工具:
文件大小: 9mb
下载次数: 0
上传时间: 2019-07-28
详细说明：Weighted Finite-State Transducers
Important Algorithms
University of Tokyomonoid Is an algebr
Semirings ()
structure that supports a sin
associative binary operation and
identity element. (wikipedia)
WFSTs and WfSt-based operations are underpinned b
algebraic objects called semirings
Definition A semiring is a system(K, 0, 0, 0, 1)such that
(1)(K,e, O)is a commutative monoid with 0 as the identity
element for⊕
(2)(K,&, 1) is a monoid with 1 as the idnetity element for
3) distributes over for all a, b
K
(ab)⑧c=(ac)(
⑧(ab)=(c⑧a)⊕(c⑧b)
(4)0 is an annihilator for∞:∈K,a0=0∞a=0
Speech Recognition with Weighted Finite-SLaLe Transducers, Mohri et
This has implications for optimization, scarch, and combination
algorithms such as determinization, shortest-path, and
composition
4
Semirings (ll
o a varicty of semirings exist but there arc two that arc of
particular interest for NLP and asr applications
e log semiring
o Isomorphic to the real semiring high numerical stability
e The tropical semiring
o Convenient for shortest-path algorithms because global path weights are
guaranteed to be monotonic non-decreasing, viterbi approximation is fast
SEMIRING
SET
Boolean
{0,1}
V∧
000
Probability∪{+∞
×
RU{-∞,+∞H1++∞|0
Tropical
R+∪{+∞}mm+|+∞0
TABLE 1. Semiring examples. Log is defined by: E N d Finite-state Transducers, Mohriet al
=log(e+ y
Speech Recognition with Weight
Semiring frameworks and algorithms for shortest-distance problems
Mohri2002 for more details
Semirings(example)
Tropical semiring example
e Simple, but unintuitive
Operation Definitions
Trivial Examples
ab=atb
5G3=3
ab=min(a, b)
4④27=2
1=0
(3∞4)6=6
0=+0
1∞5=6
(1Q5)(2∞4)=6
3(1冷3④0令0
3∞1今3∞0分>3
6
Transducers and Acceptors
Definition a wfst is defined as an8 tuple,T=(∑,△,,l,F,E,入,p)
Here 2 represents the finite alphabet of input symbols, A represents
the finite output alphabet, Q represents the finite set of states, IcQ
the set of initial state, FcQ the set of final states,EsQ×(∑∪{e})
×(△∪{e)×K× Q a finite set of state-to-state transitions,入:Ⅰ>K
the initial weight function, and p: F,k the final weight function
mapping f to K
Speech Recognition with Weighted Finite-State Transducers, Mohri et
A WFSA is simply a WfST where the output labels have been
omitted
Similarly fsas and fsts lack weights on the arcs or states
Basic examples
Finite-State Acceptor(FSA)
Bob
like
sushi
ramen
o Weighted Finite-State Acceptor(WFSA
Bob
likes
sushi/0 3
ramen/0.7
o Finitc-Statc Transducer(FST)
: sushi 8
9
10)iy
b: Bob
I: likes
s(6)s-(7)r
r:ramen
12
o Weighted Finite-State Transducer (West)
: sushi/0.3+8
sh:
10
0
I: like
ramen/0.
+(12)-+13)m(14)+(15
8
WEST Practice
test,fSt。七x七
test·syms
test
0
Openfst(www.opeNfsT.org)
012
test
h
test 1
eh 3
s emacs test fst.txt
4
s emacs test. syms
s fstcompile --isymbols=test. syms --osymbols=test. syms test fst.txt
fstdraw --isymbols-=test. syms -symbols=test. syms --portrait=true
dot -fpdf test pdf
t: test
test2, fst. txt
0
4
test2.syms
o 1 write 3
o 1 right .7
right
write 2
s emacs test2. fst. txt
s emacs test2. syms
.s fstcompile --acceptor=true --isymbols=test2. syms test2. fst.txt
Estdraw --portrait=true --acceptor=true --isymbols=test2. symsdot
fpdf test2 pdf
write/0.3
right/0.7
Important algorithms
There exists a wide variety of algorithms that operate on
Weighted Finite-State Transducers
composition, determinization, minimization, epsilon-removal
epsilon-normalization, synchronization, weight pushing,
reversal, projcction, shortest-path, connection, closure,
concatenation, pruning, re-weighting, union, etc
Arguably the most important opcrations are composition
determinization, epsilon-removal, weight-Pushing, and
minimization
Composition ()
10
o Fundamental operation for combining related transducers
(1o2)(x,y)=m1(x,2)8T2(2,)
z∈△*
Used to iteratively combine multiple related knowledge sources to produce a
single integrated result
aa0.6
b503↓2)ab0.5
b
ab/03
b:a/05
b/o
bb/0.4
3/0.了7
b:b/0.1
a:b/04
3/0.6
a:b/0.2
a:a/04(0,1)
a:a02
ab/,01
(0,0)
b:a/08
b:a/06
a:b/,24
a:a/0
(3,1)
(3,3)/42
(2,1)
Fig. 6. Weighted transducers(a)T1 and(b) T2 over the probability semiring.(c)
Illustration of composition of T1 and T2, 71012. Some states might, be constructed
during the execution of the algorithm that are not co-accessible, e. g,(3, 2). Such
states and the related transitions can be removed by a trimming (or connection)
algorithm in linear-time
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
