# esun study group kaldi chapter 5 (2021.04.20)

## Chap 5 構圖和解碼

- decoding in kaldi
1. make decoding graph
2. find best path in graph

### 5.1 N 元文法語言模型

- decoded result = best path in graph
- i.e. find path that has minimum cost
- i.e. find path that has max -(AM score + LM score)
- 當 AM 一樣 => it's LM that make difference
- decoded phone sequence : r ae k ah n ai s p ii ch
- best path depends on : $max(P(wreck\ a\ nice\ speech), P(recognize\ speech))$
- ngram LM: count based
- $P(W_i|W_{i-N+1}W_{i-N+2}...W{i-1}) = \frac{count(W_{i-N+1}...W_i)}{count(W_{i-N+1}...W_{i-1})}$
- $P(fly|like\ to) = \frac{count(like\ to\ fly)}{count(like\ to)}$
- issue of ngram : data sparsity due to unseen events
- 當 N 越大，很可能多數的 event 並不會出現
- e.g. 5-gram, vocab=10000 => 有 $10000^5$ 種 5-gram
- smoothing
- 給予沒出現過的 event 一個機率
- add 1 smoothing
- 沒出現過的 count 就當作 1
- back-off smoothing
- ngram 沒有 count => 參考 (n-1)gram
- interpolation smoothing
- $\bar{P_n}=bP_n+(1-b)\bar{P_{n-1}}$
- 可以用來做 LM adaption
- general domain LM adapt 到 domain LM
- Good-turing smoothing
- share counts
- 出現 1 次的所有 events share 給 0 次的 events，出現 2 次的所有 events share 給 1 次的 events，etc.
- Katz's smoothing
- 修改 Good-Turing
- 高 count 的 event 不調整
- 要 smooth 的低 count event 在 share 時，count 打折扣再去 share
- e.x. $3$ 次的 event 數共有 $100$ 個 events，要 share 給 2 次 => $100*(3-d_3)$, $d_3: discount$
- Absolute discount interpolation
- $P_{absdiscount}(W_i|W_{i-1})=\frac{c(W_{i-1}, W_{i})-d}{c(W_{i-1})}+\lambda(w_{i-1})P(W)$
- 根據觀察， gt based discounting 減去的 d 約是 0.75 => 直接指定 d
- Kneser-Ney
- diversity of history
- 以 absolute discount interpolation 為例，直接用 unigram 可能產生問題
- >I can't see without my reading ___
- _glasses_ or _Francisco_?
- _Francisco_ 可能會因為 _San Francisco_ 很多次，導致 _Francisco_ 的 unigram 比 _glasses_ 好
- KN : "how likely is w to have a novel continuation" instead of "how likely is w"
- 把結尾是 Francisco 的 bigram 種類統計，對所有 bigram 種類 normalize 作為 Francisco 的 backoff unigram
- $P_{continuation}(W)=\frac{|\{W_{i-1}:count(W_{i-1},W_i)>0\}|}{|\{(W_{j-1},W_j):c(W_{j-1},W_j)>0\}|}$
- $P_{KN}(W_{i}|W_{i-1})=\frac{max(count(W_{i-1},W_i)-d, 0)}{count(W_{i-1})}+\lambda{W_{i-1}}P_{continuation}(W_i)$
- more general：
- ref : https://www.youtube.com/watch?v=cbAxvpBFyNU
- Witten Bell
- diversity of predicted words
- 假設 2gram，其中：$count(spite)=count(constant)=993$
- spite 後面的 word 只有 9 種
- $1-\lambda_{spite}=\frac{9}{9+993}=0.00898$
- constant 後面的 word 有 415 種
- $1-\lambda_{constant}=\frac{415}{415+993}=0.29474$
- P(constant) 會得到比較高的權重
- https://www.statmt.org/book/slides/07-language-models.pdf
- 常用：{kndiscount, wbdiscount} x interpolation

#### SEE ALSO

- Fundamentals of Information Theory
- Perplexity

### 5.2 加權有限狀態轉換器

- 加權 有限 狀態 轉換器 <=> Weighted Finite State Transducer

#### 5.2.1 概述

- 1997 由 M. Mohri 提出可應用於語音辨識
- WFST 可由數學證明圖的最小化
- semiring
- $\dots$

#### 5.2.2 OpenFst

- c++ command line api
- 格式：
- arc: ```state_id_src state_id_dst input output [cost]```
- end state: ```state_id [cost]```

### 5.3 用 WFST 表示語言模型

- 透過 kaldi 之 arpa2fst 把 srilm 的 arpa 格式 ngram 轉為 fst 格式

#### example

- training text:
- 

- G.fst from monogram
- 
- G.fst from 3gram
- 

### 5.4 狀態圖的建置

- WFST 重點操作
- 

#### 5.4.1 用 WFST 表示發音辭典

- lexicon -> L.fst
- cmu dict
- yes/am 作為範例建立 L.fst
- yes : y eh s
- am : ae m
- 

#### 5.4.2 WFST 的複合運算

- composition
- 概念：AｏB
- 根據 A 的 output 跟 B 的 input 合併
- fst A:
- 
- fst B
- 
- AｏB
- 

#### 5.4.3 詞圖的按發音展開

- 用 compose 可以把 L.fst 跟 G.fst 合成 LG.fst，整合兩種 model

#### 5.4.4 LG 圖對上下文展開

- 再跟 context dependent phones 合成
- C.fst o LG.fst = CLG.fst

#### 5.4.5 用 WFST 表示 HMM 拓墣結構

- H.fst o CLG.fst = HCLG.fst

### 5.5 圖的結構最佳化

- remove epsilon
- 
- reference: [Lecture 10 Introduction to 5 Basic Operations for WFST Epsilon Removal](https://www.youtube.com/watch?v=sp5SwulVjUw)

#### 5.5.1 確定化

- non determinized fst 變成 determinized fst 的過程
- 讓圖遇到一種輸入，只會對應到一種路徑
- 
- reference: [Lecture 11 Introduction to 5 Basic Operations for WFST Determinization](https://www.youtube.com/watch?v=QYSASah11SM)

#### 5.5.2 最小化

- weight pushing
- 把 weight 往前 push 到 inital state
- 可以提早把低分路徑踢掉
- 
- reference: [Lecture 12 Introduction to 5 Basic Operations for WFST Weight Pushing](https://www.youtube.com/watch?v=blZnw69cB2k&t=76s)
- minimization
- 很多種演算法

#### 5.5.3 圖的 stochastic 性質

- fst 之所有 transition 權重滿足 semiring + 操作後為 1 則為 stochastic
- 「效率比較好」
- 特性：stochastic 過的 fst，經過任意 compose 還會是 stohcastic

### 5.6 最後狀態圖的產生

- kaldi 中產生最後 decoding graph 步驟
- $HCLG = asl(min(rds(det(H'ｏmin(det(Cｏ(det(LｏG))))))))$
- asl : add self loop
- rds : remove disambiguation symbol

### 5.7 以權杖傳遞為基礎的維特比搜尋

- Viterbi 的陽春版
- $matrix:T \times S, T: time, S:States$
- 從 $t=0$ 到 $t=1$，找出最低 cost 之 state sequence
- 
- token passing
- token：記錄路徑，每個走過的路徑都有一個 token
- 每個 state 往下走，有 n 條選擇就複製 n 個 token
- 多個權杖進同一 state，只保留最好的即可，因為 viterbi 是 optimal
- 透過 pruning 可以刪掉不夠好的 token
- 到達 final state 時，挑選最好的 token 之路徑的 label 即為辨識的結果。

### 5.8 SimpleDecoder

- decode 結果是 linear output
- a.k.a. 1-best
- acoustic score 與 decoder 解耦，故可以用任何 source 的 model (GMM, nnet3, pyTorch, TensorFlow) 產生 acoustic score

### 5.9 Kaldi 解碼器家族

- 種類
- SimpleDecoder
- FasterDecoder
- 比 SimpleDecoder 更好的 pruning policy
- **align 時的 decoder 是 G.fst 以 transcription 產生的 FasterDecoder**
- online 版：OnlineFasterDecoder
- LatticeFasterDecoder
- online 版：LatticeFasterOnlineDecoder

### 5.10 帶詞網格產生的解碼

- 詞網格：word lattice
- input 的 cost 是 pair
- (graph score, am score)
- i.e. LatticeFasterDecoder
- 以 LatticeSimpleDecoder 為例
- 產生新的 token 後，與舊的 token 連結
- prune 掉分數低的路徑
- 到所有 state 處理完即有一個 word lattice
- 範例 [source](https://www.researchgate.net/figure/Diagram-of-a-word-lattice-resulting-from-recognition-of-audio-utterance-I-like-this_fig3_308786485)：
- 
- 在產生的 word lattice 進行最小成本路徑搜索，即可獲得辨識結果
- lattice-best-path
- 產生的 lattice 可依據需求搭配各種 scaling 進行 best path search
- kaldi 標準辨識流程
- step 1: 產生 lattice
- step 2: 根據 AM, LM scaling factor，產升辨識結果

### 5.11 用語言模型重評分提升辨識率

- 當 ngram 很大，G 跟 HCLG 會跟著變大
- e.x.
- case 1 : 17MB 3gram -> 92MB G.fst -> 411MB HCLG.fst
- case 2 : 90MB 7gram -> 235MB G.fst -> 1.8GB HCLG.fst
- 方法 1: 可以透過 pruning 方法踢掉比較不重要的 entry
- srilm
- ```-prune threshold``` : 某個 entry 踢掉對整體表現影響低於 _threshold_ 的話就踢掉。預設是 0，即不做 pruning
- ```-min-prune n``` : order 低於 _n_ 的 ngram 就不會執行 pruning。預設為 2，也就是 unigram (1gram) 不會做 pruning
- 方法 2: two pass decode
- 用小 LM 合出 HCLG.fst 產生 lattice (1st-pass )，在用大的 LM 做 rescore (2nd-pass)
- 小的 LM decode 時可提高 beam 值，讓 lattice 大一點，保留多一點選擇給大 LM
- 小 LM: 2gram 或 prune 過的 3gram (或 4gram?)
- 大 LM: 4,5,6,7gram，RNNLM，transformer LM
- NNLM
- rnnlm
- suppose 無限 context，可以解決 ngram 的問題
- 1. data sparsity，即長 context 的 ngram 出現的 data 很少，只靠 smoothing 效果有限
- 2. context 變長 ngram 需要很多參數
- 
- 純 rnnlm 會有梯度消失問題，後來都用 lstm 來實作來減緩此問題
- versions of rnnlm in kaldi
- Mikolov rnnlm
- rnnlm 作者
- proposed in 2012
- yandex's faster rnnlm
- yandex rnnlm
- tensorflow rnnlm
- 整合 tensorflow
- kaldi nnet3 rnnlm
- lstm x 3
- 也有 bilstm
- 較難支援 online decoding
- transformer LM
- "A Parallelizable Lattice Rescoring Strategy with Neural Language Models", Li Ke, Daniel Povey, Sanjeev Khudanpur
- 整合 pytorch 的 transformer LM
- version on kaldi-asr github: ```376281caa2e42085f157889dca8484dfef42ebee```
- WER 約提升 0.1%
- 10.3 -> 10.2 in Hub5,00 task
- 6.6 -> 6.5 in swbd task
- 14.0 -> 13.9 in callhm task
- rescore 實作 : ```lattice-lmrescore```
- 把舊的 G.fst 跟 lattice 做 fst compose，透過 --lm-scale 設成 -1，可以把 lattice 上的 lm score 減掉，加上新的機率道理相同
- e.g. log 減等價機率除
- 智金處 rnnlm：
- kaldi 的 nnet3 架構
- 訓練時間：4/11-4/13
- machine 14u
- CPU: 16
- GPU: 1080Ti * 4
- corpora
| 語料 | 類別 | 大小 |
| :--: | :--: | :--: |
| asr_esun | 行內 asr 語料之文本 | 12MB |
| asr_no_esun | 非行內 asr 語料之文本 | 137MB |
| esun_common_sense | 玉山銀行相關公開文件 | 1.4MB |
| esun_other | elang 新聞 | 1.7GB |
| ptt_domain | 從 ptt 爬入，跟金融或銀行業領域相關看板 | 272MB |
| ptt_general | 從 ptt 爬入，不含 ptt_domain 之看板 | 2.9GB |
- 效果
- esun_200hr: 14.9% -> 14.27%
- esun_overdue: 33.77% -> 33.18%
- matbn: 18.63% -> 13.58%
- esun_ceo: 8.19% -> 6.82%

### 5.xx appendix

- discriminative training
- MCE (Minimium Classification Error)
- MBR (Minimium Bayes Risk)
- c.f. MBR decode
- MPE (Minimium Phone Error)
- sMBR (state level Minimium Bayes Risk)
- ASR 軍備競賽區
- [speechbrain](https://speechbrain.github.io/about.html)
- [k2](https://github.com/k2-fsa/k2)
- kaldi x pytorch
- fst base decoder
- k2 為辨識核心，另有處理 data 的 [lohtse](https://pypi.org/project/lhotse/)，與類似 kaldi/egs 的 [snowfall](https://github.com/k2-fsa/snowfall)
- [s3prl](https://github.com/s3prl/s3prl)
- Self-Supervised Speech Pre-training and Representation Learning Toolkit.
- 由台大李宏毅老師團隊開發