Weighted Finite State Tranducer

Components

• the most general among FSA, FST, etc
• 6개의 튜플(tuple: 유한 개의 사물의 순서있는 열거)로 정의 된다.
• states, transitions, input, output, initial states, final states
• initial 과 final states는 states에 포함됨
• in/output에서 epsilon은 어떤 symbol도 없다는 뜻

Graph

• state는 원으로 표시하고 고유번호를 가지며 숫자가 별 의미는 없음.
• initial state는 진한 원의 0, final state은 이중원으로 표기한다.
• transition은 arc로 표시하여 state간을 연결한다.
• transition은 input:output/weight로 정의된다.
• weight는 transition뿐 아니라, state 번호 다음에도 /weight로 부여될 수 있다.

Weight

• weight는 cost로서 크면 좋지 않다. (e.g. -log10(p) in Kaldi)
• weight가 없으면 FST, input과 output이 같으면 FSA
• $\otimes$는 path를 따라 가면서 final state까지 weight를 합하는 것
• $\oplus$는 여러 가능한 경로가 존재한다면 그들 중에 제일 낮은 cost를 취하는 것.
• ac $\rightarrow$ xz (cost: 0.5+2.5+3.5=6.5) accepted.
• bc $\rightarrow$ yz (cost: 1.5+2.5+3.5=7.5) rejected.

FST vs. FSA

• FST는 하나의 tape의 입력(e.g. 문자열)을 순서대로 읽어서 또다른 tape로 출력하는 것으로 parsing에 쓰임
• FSA는 FST와 같은데 output없이 하나의 tape을 읽기만 하고, recognition, pattern matching에 쓰임
• e.g. FST: g2p, regexprep; FSA: grep, regexp
  
  

WFSA

• WFSA는 string to cost의 함수.
• 여러 paths 존재하면 가장 낮은 cost 점수의 path 선택
• cost는 arc와 final state에 부여 되는데, 합을 취하면 됨.
• weighted FSA에선 cost가 유한수 (accepted) 혹은 무한대 (rejected). cf. unweighted FSA는 cost가 0 (accepted) 혹은 무한대 (rejected).

Hosung Nam