---
# System prepended metadata

title: esun study group kaldi chapter 5 (2021.04.20)

---

# 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:
    - ![](https://i.imgur.com/LCZJNpL.png)

- G.fst from monogram
    - ![](https://i.imgur.com/7yYfvdV.png)
- G.fst from 3gram
    - ![](https://i.imgur.com/3JcqyAU.png)


### 5.4 狀態圖的建置

- WFST 重點操作
    - ![](https://i.imgur.com/OG7b2IY.png)


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

- lexicon -> L.fst
- cmu dict
- yes/am 作為範例建立 L.fst
    - yes : y eh s
    - am : ae m
    - ![](https://i.imgur.com/t7IGcBY.png)


#### 5.4.2 WFST 的複合運算

- composition
    - 概念：AｏB
        - 根據 A 的 output 跟 B 的 input 合併
- fst A:
    - ![](https://i.imgur.com/R2919n7.png)
- fst B
    - ![](https://i.imgur.com/qwY4u0N.jpg)
- AｏB
    - ![](https://i.imgur.com/XPgLETo.png)


#### 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
    - ![](https://i.imgur.com/VkBB5jh.png)
    - 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 的過程
    - 讓圖遇到一種輸入，只會對應到一種路徑
    - ![](https://i.imgur.com/gHup6FP.png)
    - 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
    - 可以提早把低分路徑踢掉
    - ![](https://i.imgur.com/n5dzOom.png)
    - 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
    - ![](https://i.imgur.com/HnXSnoi.png)
- 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)：
        - ![](https://i.imgur.com/6lArnR3.png)
- 在產生的 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 需要很多參數
        - ![](https://i.imgur.com/q5ILjy7.png)
        - 純 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.
        - 由台大李宏毅老師團隊開發

