180909 CMU 음성인식 ppt 노트 - 13. Grammars

Link: http://www.cs.cmu.edu/afs/cs/user/bhiksha/WWW/courses/11-756.asr/spring2013/

Syntax and Semantics

• 음성인식을 다루고 있으므로 Syntax 까지만 고려하고 Semantics는 틀려도 상관 없는 걸로 하자 (예를 들어 Apple ate banana 같은 문장도 문법적으로는 맞으니까 인정)

Finite State Grammar

• state가 유한개라서 그림으로 그릴 수 있다.
• initial, terminal state가 있다.
• Transition에 probability를 부여할 수 있다. (WFST와 비슷)
• FSG로부터 나올 수 있는 모든 문장의 집합을 "language"라 하자.
• (주의) node가 아니라 edge에 word가 표시되어 있다.

Decoding with Finite State Grammars

• FSG의 edge를 word HMM으로 바꾸자.
• 그 다음 time synchronous viterbi search를 적용하자.

Language HMMs from FSGs

• FSG의 edge를 HMM으로 바꾸는데, 이때 HMM의 start, end state도 그대로 유지하자.
• 원래 FSG에 있는 node도 사라지는 것이 아니다. 즉 node of FSG -> start state of HMM -> … end state of HMM -> node of FSG 이 되는 것이다.
• FSG의 원래 node(이것도 state이다)들은 모두 non-emitting state가 된다.
• (내 생각)아하 WFST 이전 음성인식에서는 전부 HMM으로 나타냈던 것이었구나
• silence state는 어디다 끼워넣을까?
• 각 FSG node에 loop 형태로 끼워넣는다(silence로 교체하는 것이 아니라 node에 loop를 만들고 그 loop에 올려놓는 것이다)

ROBOT0 Cross Word Transitions

• (중간에 무슨 정렬을 해야 한다는데 이해를 못함)

Words and Word Instances

• FSG states(nodes)는 음향 HMM과는 별개의 것이므로 미리 준비되어 있어야 한다.
• 단어는 똑같은데 다른 transition을 가지는 것들이 있다(같은 ten이라도 "ten centimeters"와 "rotate ten"에 쓰이는 것처럼 graph의 형태에 따라 각각 다른 path에 속할 수 있음). 이 경우 해당 word HMM을 각각 복사해줘야 한다(실제로는 복사하지 않겠지)

Creation of Application FSGs

• 작은 규모의 FSG는 그냥 손으로 만들 수 있다.

Example Application: Reading Tutor

• 학생의 올바른 낭독(?)을 지도하기 위한 음성인식기 예제
• "once upon a time a"라는 문장에 대해 FSG word graph를 만들어보자.
• 각 단어 사이의 node에…
• 이전 node로 돌아가는 null transition를 추가하면 학생이 같은 단어를 반복해서 말하는 경우를 잡아낼 수 있다.
• node 자기 자신에 대해 "on", "up" 등의 부분 단어에 해당하는 edge를 추가하면 더듬거리면서 말하는 경우를 잡아낼 수 있다.
• 이전 node로 돌아가는 OOV(교재에서는 ???로 표현) edge를 추가하면 정답과 전혀 관련 없는 단어를 말하는 경우를 잡아낼 수 있다.
• 한 node에서 다음 node로 곧장 가는 null transition를 추가하면 특정 단어를 건너뛰고 말하는 경우를 잡아낼 수 있다.
• node 자기 자신에 대해 silence edge를 추가하면 단어 사이사이의 묵음을 허용할 수 있다.
• 그 외에 dynamic fine tuning을 사용하면(어떻게 하는진 모르겠지만)
  • FSG의 start state에 대한 transition 확률을 조정하면 문장 중간부터 시작하는 경우도 잡아낼 수 있다.
  • 학생마다 낭독 패턴이 다양한데, 이것을 반영하여 HMM을 재 학습 시킬 수 있다.

FSG Representation

• 이제 컴퓨터에게 FSG를 준비시켜보자. 그런데 컴퓨터는 그림으로 된 graph 같은건 읽을 수 없다. 그나마 텍스트 파일은 읽을 수 있다.
• tabular(표 형태) 또는 rule-based(미리 규칙을 정해놓고)로 된 파일을 건네줄 수 있다.

Recursive Transition Networks

• 한 FSG를 다른 FSG와 합칠 수 있을까?
• 이런 network를 RTN이라 한다. (서로 참조하거나 자기 자신을 참조하는 경우 graph가 recursively 만들어지기 때문)
• Grammar가 recursively 정의될 수 있는 것이다.

Nested FSGs, Flattening Composite FSGs for Decoding

• < date >"라는 FSG를 생각해보자. 이게 < day-of-week > - < date-in-month > - < month >로 표현되어 있다면, "< >"에 해당하는 건 다른 FSG들을 embedding(혹은 plugging in)할 수 있는 edge이다.
• "< >" 를 FSG reference라 한다.
• FSG reference를 하나도 갖고 있지 않은 FSG는 flattened FSG 또는 regular FSG라 부른다. regular FSG의 edge에는 이제 HMM을 넣어주면 된다.
• Composition을 한다 해서 전부 Flat해지는 것은 아니다. RTN이 되어버리면 FSG로 정의할 수 없다. 이건 CFG로 나타내야 한다.

Recursion in Grammar Netoworks

• 로봇에게 내릴 명령 문장의 graph를 < command-list >라 하자. 그리고 < command-list >는 graph edge 내에 < command-list >에 대한 reference를 가지고 있다고 하자.
• 이 경우 flattening을 수행하면 graph가 무한대로 확장되고 만다.

Context Free Grammars

• CFG는 FSG의 superset이다.
• "Context Free"의 뜻: 다른 grammar에 embedding 될 때 그 grammar가 무엇이든 상관없이 적용 가능함
• 즉 grammar 중 가장 원형에 속하는 grammar라 할 수 있다(마치 순수 클래스 처럼?).
• 특성 상 graphical representation이 안된다.
• 대신 production rules로 나타낼 수 있다.

Probabilistic Context Free Grammars

• CFG의 production rule에 확률을 붙이면 CFG를 확률적으로(?) 만들 수 있다.
• recognition hypothesis의 전체 likelihood를 계산하는데 사용할 수 있다(이건 잘 이해 안됨)

Context Free Grammars: Another View

• non-terminal들은 (graph로 나타낼 수 없으므로 edge라 할 수 없지만 CFG의 edge에 해당) 프로그래밍 언어에서 function에 해당한다.
• (function을 recursively 호출하면 터지는 것처럼…)

CFG Based Decoding

• 다음과 같은 CFG가 있다 치자.
• S ::= aSb | c
• 이렇게 되면 S는 자기 자신을 호출하기 때문에 무한대의 깊이를 가지는 call tree가 만들어진다.
• CFG를 그대로 사용하는 것은 불가능하기 때문에 FSG로 근사하여 나타내자.

FSG Approximation to CFGs

• 다음과 같은 CFG가 있다 치자.
• S ::= aSb | c | e
• aSb는 풀어쓰면 aaa…S…bbb에 해당한다(좌우 a, b의 갯수는 같음).
• FSG 관점에서 aSb의 S는 c 와 e로 embedding 될 수 있으므로 c와 e를 넣자(aSb도 해당되지만 이건 넣지 말자).
• a와 b edge 양 끝에 되돌아가는 null transition을 추가하자.
• 이렇게 하면 aaa…S…bbb를 흉내낼 수 있다.
  • (하지만 좌우 a, b의 갯수는 같지 않을 수 있기 때문에 근사적으로 같다 -> illegal하다)
• start, end node를 추가하자.

Another FSG Approximation to CFGs

• call tree의 허용 깊이를 정하자.

FSG Optimization

• 첫번째 근사 방법은 null transition을 너무 많이 만든다.
• 이렇듯 manually 만들어진 FSG들을 그대로 쓰는건 redundant가 너무 많아 매우 비효율적이다.
• optimization을 통해 불필요한 state를 줄여야 한다(여기서는 다루지 않음).

Optimizing Language Weight

• P(X|W)P(W)^k 꼴이다.
• language weight가 증가하면 path score의 LM 부분은 급격히 작아지기 때문에 beam pruning에 걸려 탈락할 위험이 크다. -(잘 살아있다가도 LM 때문에 바로 사라져 버리는 token들이 있다는 말 같음)
• language weight를 올리면 active state(token들이 머물러 있는 state)의 수가 감소하고, 어느시점부터 WER이 증가하기 시작한다.

Rationale for the Language Weight

• weight를 부여하는 방법은 이론적으로 뭐가 있는 방법은 아니기 때문에 논쟁의 여지가 있다.

• 첫 번째 issue

• 음향 HMM의 likelihood는 density value이기 때문에, range가 0,1 사이에 있지 않다.

• LM 확률 값의 경우는 1보다 작은 값들을 가진다. (discrete probability distribution이기 때문인듯)

• 두 번째 issue

• 음향 HMM의 likelhood는 frame 각각의 output probability를 독립으로 보고 계산한다.

• 그래서 두 issue를 고려해보면 음향 HMM의 likelihood는 under(혹은 over) estimation될 수 있고 dynamic range도 LM의 range와는 매우 달라질 수 있다.