Notes

FST와 ASR에 대한 내용은 "Speech Recognition with Weighted Finite-State Transducers" by Mohri, Pereira and Riley (in Springer Handbook on SpeechProcessing and Speech Communication, 2008) 을 참조. 이곳에 Kaldi가 사용하는 일반적인 접근 방식이 설명되어 있지만, 구체적으로 disambiguation symbols를 처리하는 방법과 weight-pushing을 처리하는 방법과 관련하여 일부 세부 사항이 다르다.

Overview of graph creation

디코딩 그래프 생성을위한 전반적인 overview는 그래프 HCLG = H o C o L o G를 구성하는 것이다. 각각의 심볼의 의미는 다음과 같다.

G는 grammar 또는 language model을 인코딩하는 acceptor (즉, 입력 및 출력 기호가 동일함)
L은 lexicon 입니다. output symbols 는 단어이고 input symbols 는 phones
C는 context-dependent 을 나타냄 : 
	출력 심볼은 phones 이고 
    입력 심볼은 context-dependent phones , 
    즉 N phones 의 windows 를 나타내고; 발음 문맥 창을 참조.
H는 HMM 정의를 포함한다. 
	출력 기호는 상황에 따른 phones 를 나타내며 
    입력 기호는 전이 ID이며 pdf-id 및 기타 정보를 인코딩한다 
    (TransitionModel에서 사용되는 정수 식별자 참조).

세부적인 내용은 밑에서 계속해서 설명한다. 출력을 결정하고 최소화하기 위해 HCLG를 결정하려면 disambiguation symbol를 삽입해야한다.

또한 HCLG가 가능한 한 stochastic 이길 원하고, 이것은 기존 레시피에선 "weight-pushing" 동작으로 수행된다. stochacity를 보장하기위한 Kaldi의 접근 방식은 다르며, no graph creation step "takes away" stochasticity보장한다. 자세한 내용은 이곳에서 확인 (Preserving stochasticity and testing it)

한 줄로 요약하면, 다음과 같을 것이다.

HCLG = asl(min(rds(det(H' o min(det(C o min(det(L o G))))))))

where asl=="add-self-loops",
      rds=="remove-disambiguation-symbols", 
      H' == H without the self-loops

weight-pushing 는 레시피의 일부가 아니다. 대신 우리는 G가 stochastic이라면 graph creation sate 가 확률적 결과를 막지 않도록하는 것을 목표로한다. 물론, G는 backoff 기능이있는 Arpa 언어 모델이 FST로 표현되는 방식 때문에, 일반적으로 상당히 stochastic이지 않지만, 적어도 우리의 접근 방식은 non-stochasticity "stays put" 를 유지하고 시작했을 때보다 더 나빠지지 않도록한다. 접근 방식은 weight-pushing 작업이 실패하거나 상황을 악화시키는 위험을 피한다.

Disambiguation symbols

Disambiguation symbols는 lexicon에서,phonemene sequences의 끝에 삽입되는 기호 #1, #2, #3 같은 것들이다.

1) phonemene sequences가 lexicon에서 다른 phonemene sequences의 prefix (접두어) 이거나

2) 둘 이상의 단어로 나타나는 경우, 뒤에 이 기호 중 하나를 추가해야한다.

-> 이 Disambiguation symbols은 the product (L o G)가 determinizable위해 필요하다.

3) LM model G의 backoff arcs 에 symbol #0 를 놓는다. 이를 통해 determinizable알고리즘이 epsilons을 제거하기 때문에 epsilons을 제거한 후 G를 결정할 수 있다(determinizable).

4) 우리는 utterance의 시작 부분에서 symbols을 출력하기 전에 context FST (C)의 왼쪽에 나타나는 epsilons대신에 symbol #1을 놓는다. empty phonetic representation이 있는 단어 (예 : 문장 기호 <s> 및 </ s>의 시작과 끝)가 있을 때 발생하는, 다소 작은 문제를 해결하는 데 필요하다.

다음은 Graph compilation의 중간 단계 (예 : LG, CLG, HCLG)가 결정 가능(determinizable)하다는 것을 공식적으로 증명하는 방법에 대한 overview이다. 이는 레시피가 절대 실패하지 않도록하는 데 중요하다.

일반적인 설정은 다음과 같다.

1) G를 결정할 수 있어야 한다. 그렇기 때문에 #0 기호가 필요하다 (G는 실제로 결정적이므로 결정 가능하다). 2) 그런 다음 L을 결정 가능한 G에 대해 L o G를 결정할 수 있도록 한다. [G 대신 오른쪽에 L o G가있는 C도 마찬가지입니다.] 여전히 이론에 대한 많은 세부 사항이 있지만, L이 다음과 같은 두 가지 property을 갖는 것으로 충분하다고 생각한다.

1) 

은 작동해야만 한다

- equivalently: any input-sequence on L must induce a unique output-sequence

- equivalently: for any linear acceptor A, A o L is a linear transducer or empty.

2) L has the twins property, i.e. there are no two states reachable with the same input-symbol sequence, that each have a cycle with the same input sequence but different weight or output sequence.

C Transducer 에도 동일하게 적용된다. 우리는 스크립트와 프로그램이 현재 생성하는 변환기는 이러한 property를 가지고 있다.

The ContextFst Object

ContextFst 객체 (C)는 context-dependent phones 에서 context-independent phones로의 transducer를 나타내는 동적으로 생성 된 FST object 이다. 이 object의 목적은 context 에서 가능한 모든 phones를 열거 해야하는 것을 피하기 위한 것이다. context 에서 가능한 모든 phones를 열거 해야하는 것은 Context width (N) 또는 phones의 개수가 클 때 어려울 수 있다.

생성자 ContextFst::ContextFst는 context-width (N)과 central-position (P)를 필요하다(triphone 시스템에 각각 N=3과 P=1). (추가설명:Phonetic context windows)

또한 모든 phones을 본 후 FST에서 N-P-1을 출력하는 특수 기호 인 "subsequential symbol"(위에서 '$'라고 함)의 integer ID가 필요하다 (이로 인해 context FST is output-deterministic이 보장됨). 이 외에도 integer id's of the phones및 disambiguation symbol 목록이 필요하다.

ContextFst의 출력 측 vocabulary는 set of phones및 disambiguation symbols와 subsequential symbol로 구성된다.

입력측의 vocabulary는 동적으로 생성되며 (사용되지 않는 epsilon제외) phones in context, disambiguation symbols 그리고 "전통적인 레시피"에서 "#에서 엡실론을 대신하는 #-1로 쓰는 특수 기호(다른 disambiguation symbol로 취급(예 : 엡실론 제거 등 선호하는 의미에서 결정성을 보장하는 데 필요함) 에 해당한다. The vocabulary on the input side is dynamically generated and (apart from epsilon, which is not used), corresponds to phones in context, disambiguation symbols, and a special symbol that we write as #-1 that takes the place of epsilon in the "traditional recipe", but which we treat as any other disambiguation symbol (it is necessary to ensure determinizability in the sense we prefer, i.e. with epsilon removal).

전통적인 레시피에서와 같이 subsequential symbol'$'는 입력측에 해당하는 것이 없다. 입력측에서 disambiguation symbols에 대응하는 symbol id's는, 대응하는 심볼에 대한 출력측에서 사용되는 integer 식별자와 반드시 동일하지는 않다.

ContextFst 객체에는 std :: vector <std :: vector <int32> 유형의 객체에 대한 참조를 반환하는 함수 ILabelInfo()가 있으며, 이를 통해 사용자는 입력 측에서 각 심볼의 "의미"를 계산할 수 있다. 이 객체의 올바른 해석은 The ilabel_info object에 자세히 설명되어 있다.

ContextFst와 관련된 composition알고리즘에 사용하기위한 ContextMatcher라는 특수한 "Matcher" object가있다 (Matcher는 OpenFst의 composition알고리즘이 arc lookup에 사용하는 것이다. ContextMatcher는 필요한 것보다 더 많은 상태의 할당을 피함으로써 ContextFst 객체의 사용을 보다 효율적으로 만든다 (문제는 normal matcher를 사용하면 state에서 arc를 원할 때마다 대상을 할당해야한다는 것이다) 해당 상태에서 다른 모든 아크의 상태).

composition에 대한 left hand argument가 ContxtFst 유형 인 경우 FST 컴포지션을 수행하는 관련 함수 ComposeContextFst ()가 있고, Matcher를 사용한다. ComposeContext () 함수도 있는데, 이 함수는 비슷하지만 ContextFst 객체 자체를 만든다.

Avoiding weight pushing

weight-pushing는 각 상태의 arc 확률이 적절한 의미로 "sum to one(합계)"되는 것을 보장하는 FST operation이다. Kaldi는 전통적인 레시피와는 약간 다른 방식으로 weight-pushing 문제를 다룬다. log semiring(반올림)에서weight-pushing는 검색 속도를 높이는 데 도움이 될 수 있다. 그러나 경우에 따라 weight-pushing는 나쁜 영향을 줄 수 있다. 문제는 FST로 표현 될 때 통계 언어모델이 일반적으로 ""add up to more than one (하나 이상으로 합산)"하기 때문에 일부 단어는 직접적으로 backoff arcs를 통해 두 번 계산되기 때문이다.

우리는 절대로 pushing weights하지 않기로 했고, 대신 다른 방식으로 처리한다. 첫째, Definition: 우리는 weight가 1에 해당하는 "stochastic"FST를 호출하고 reader는 "log semiring"에 대해 이야기하고 있다고 가정 한다. "sum to one"를 의미하며 "take the max" 이 아니다.

그래프 생성의 각 단계는 이전 단계가 stochastic이라면 다음 단계가 stochastic이라는 특성을 갖는다. 즉, G가 stochastic이라면 LG는 stochastic이다. LG가 stochastic이라면 det(LG)는 stochastic이다. det(LG)가 stochastic이면 min(det(LG))은 stochastic등이다. 이것은 각각의 개별 작업이 적절한 의미에서 "preserve stochasticity"해야한다는 것을 의미한다. 예를 들어, 예를 들어 weight-push 알고리즘을 시도해 볼 수 있으며 원래 G fst가 둘 이상으로 합산되어 실패한 것으로 판단되면 실패를 내뱉는다.

우리는 더 강력한 의미로 stochasticity을 유지하려고 한다. 즉, G에 대해 모든 states에 대한 최소값과 최대값을 먼저 측정한다 (arc probabilities plus final-prob). 이것이 우리의 프로그램 "fstisstochastic"이 수행하는 일이다. G가 stochastic이라면,이 두 숫자는 모두 1이 된다 (실제로 로그 공간에서 작동하기 때문에 실제로 프로그램에서 0을 보게 될 것이다. 이것이 "log semiring" 이다). 우리는 다음과 같은 의미에서 확률을 유지하려고 한다.이 최소값과 최대 값은 "get worse" 않는다. 즉, 그들은 결코 1에서 더 멀어지지 않는다. 실제로 이것은 "local" 방식으로 확률을 유지하는 알고리즘이있을 때 자연스럽게 일어난다. stochasticity을 보존하기 위해 필요한 다음과 같은 다양한 알고리즘이 있다.

These properties are true of C, L and H, at least if everything is properly normalized (i.e. if the lexicon weights sum to one for any given word, and if the HMMs in H are properly normalized and we don't use a probability scale). However, in practice in our graph creation recipes we use a probability scale on the transition probabilities in the HMMs (similar to the acoustic scale). This means that the very last stages of graph creation typically don't preserve stochasticity. Also, if we are using a statistical language model, G will typically not be stochastic in the first place. What we do in this case is we measure at the start how much it "deviates from stochasticity" (using the program fstisstochastic), and during subsequent graph creation stages (except for the very last one) we verify that the non-stochasticity does not "get worse" than it was at the beginning.

[1] https://kaldi-asr.org/doc/graph.html