工作笔记：Finite State Transducer（FST）in NLP

有限状态转移机在自然语言处理上的应用
原文地址：http://infolocata.com/mirovia/finite-state-transducers-for-natural-language-processing/
在自然语言处理中，经常会遇到一些针对某些内容法则做出修改的操作，比如说：如果c的后面紧接x的话，则把c变为b，FST则是基于这些规则上的mathematical操作，比如说把若干个规则整合成一个single pass或mega rule，这样做呢，就可以很有效的提高rule-based system的效率。
首先，先来大概的了解一下有限状态机（FSM）
有限状态机呢就是一个由一堆状态（当然啦，有限的嘛），还有一堆转移条件组成的‘鸡’。英文定义是这样的：a FSM is an abstract mathematical model of computation that is capable of storing a status or state and changing this state based on input. 我的理解大概这个FSM就是一个基于某些状态和某些规则而构造的一个模型。比如原文作者就丧心病狂的给他的小白鼠构造了下面这个“我的一天”的模型。
                
                
所以呢，我们大致可以看出来这个Mirovia的小白鼠每天的生活就是困了睡、饿了吃、无聊了就开始搞基……
在NLP中，FSM包含一个起始节点和一个终止结点，然后通过all possible combination of condition labels，就能去generate, recognize language了。
而FST呢，就是一种special type of FSM. 具体的来说，FST会有一个input string和一个output string, 对比起对于某种状态我要么接受条件做出转移，要么我就原地不动的FSM来说，FST是将这个input string转移成output string了，也就是说，it accepts a string on its input tape and generate another string on its output tape.
FST在一些NLP task里面特别有用，比如说我给出以下三个规则：
1) 当c后紧接x时，将c变为b cx→bx
2) 当a前面是rs时，将a变为b rsa→rsb
3) 当b前面是rs，后面是xy时,将b变为a rsbxy→rsaxy
所以当我们的input string是rsaxyrscxy时，根据以上三个规则，我们就可以做出以下的变换：
rsaxyrscxy→rsaxyrsbxy
rsaxyrsbxy→rsbxyrsbxy
rsbxyrsbxy→rsaxyrsaxy
然后大家就会发现，第二步做的变换的第三步又变回去了！搞毛啊！浪费我们程序猿宝贵的时间和精力啊！于是FST就出现了， FST provides a path to eliminate these inefficiencies.
首先呢，我们把每一个rule都用一个FST表示出来，每个状态间的link表示接收input character以及相应的output character. 表示方式是input/output. 所以针对上面的3个rules，我们可以得到以下三个FST：
                
                
接下来，我们就要去extending 这些FST了，为什么要extending他们呢？原文是这么说的： FST would be of little use in matching against an input string as each is designed to process exactly the context window described in its corresponding rule.我的理解是这样的，比如说第一个rule，当rsaxyrscxy进来后，先判断第一个字符r，rule 1就识别不出来了，因为他只知道c和b的事嘛。所以为了让FST能适用于任何任意长度的string而且能够根据rules进行必要的操作，我们就要extend FST. 就拿刚刚的rule 1来说吧，他只是为了变换cx到bx，但是他也要能handle得了其前面的‘rsaxyrs’这些characters还有他后面的那个y啊，所以呢，我们可以简单的把这些貌似与规则暂时无关的characters列在一个its own individual edge上面, labeled with ?/?. 然后用ε表示无输出，我们来看一下刚刚那三个FST扩展后的结果先：
                
                
好的，就以第一个图来讲解一下
首先输入rsaxyrscxy，然后c前面的这一串‘rsaxyrs’，由于他们和我规则没有半毛钱关系，所以他们是什么就还是什么，然后遇到c字符了，我们就用c/ε 来表示“暂时无输出，跳入下一个字符”，所以我们看到了1那个节点，这个节点分别有三个link指出去，，x/bx表示输入x的话，那就输出bx；?/c?表示输入为非x外的任意字符，则原样输出嘛；c/c表示输入c，输出c(相当于继续判断我后面那个是什么)。
然后呢，就要去把上面这一堆合成一个single FST了，这个时候作者说了一句“A full explanation of the FST composition algorithm is beyond the scope of this write-up”，咳咳，same reason吧，大家比划比划应该能搞出下面这个composed FST:
                
                
这个final FST能达到那三个rule的效果，而且重点是the transformation required only a single pass though the FST and did not result in any efficient transformations. 原来这些rule的task耗费的时间与他们的rule number啊，窗长啊，input string字符数啊都有关系，而现在FST耗费的时间只与input string字符数有关了，perfect啊！
（完）