2018년 9월 9일 일요일

180909 CMU 음성인식 ppt 노트 - 11. Continuous Speech

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

6일 동안 읽은거 주말 일요일에 한번에 정리하자.

솔직히 다시 정리하기 귀찮은데 아예 안하자니 기분좋게 아는 느낌만 들고 아무 기억도 안날 것 같아서 최소한 이것만은 해야 겠다.

Spell Checking, The Trellis as a Product

  • spell check를 어떻게 할 건지 생각해보자.
  • 입력이 UROP 이고, 가지고 있는 템플릿은 ON, OR, DROP 세 개라고 하자.
  • 이 경우 입력과 세 템플릿에 대해 각각 거리를 구하여 가장 거리가 작은 템플릿을 선택하는 것으로 잘못된 spell을 교정할 수 있다.
  • 거리를 구하는 연산을 Product라고 한다. 벡터로 따지면 inner product 같은 것이다.

Continuous text: Looping around, Lextree, Continuous text with arbitrary spaces, Models with optional spaces

  • ON, OR, DROP 템플릿 세 개에 대한 state 모델을 만들고 start, end state를 공유하도록 하여 모델 세개를 병렬로 묶자.
  • ON, OR, DROP로만 이루어진 연속 텍스트를 모델링 하기 위해서는 end-start state 사이에 loop-back edge를 추가하면 된다. start, end state를 따로 두지 말고 하나로 합치자
  • loop-back edge에 적절한 페널티를 주면 연속 텍스트 모델이 단어 간의 경계를 더 잘 찾거나 혹은 더 안 찾도록 유도할 수 있다.
  • 페널티의 디폴트 값은 insertion(-> 방향) 페널티와 같은 값을 주는데, 이는 경계를 잘 구분하든 아니든 같은 cost가 들도록 한 것이다.
  • 템플릿 단어 간 겹치는 글자를 공유하여 lextree를 구성할 수 있다. (예: horrible과 horse는 hor를 공유한다)
  • 여기서 설명하고 있는 모델의 경우 space가 들어 있지 않은 입력(예: helloworld)만을 고려한 것이다. space가 들어 있는 텍스트의 경우에는 어떻게 할까?
  • 모델에 space (" ")를 넣는다.

Isolated Word vs Continuous Speech, Templates for "Sentences",

  • 연속음성인식을 하기 위한 템플릿은 어떻게 만들까? 고립 단어 템플릿을 가지고 전부 조합해서 준비하면 될까?
  • 특정한 문장만이 필요한 경우는 상관 없지만 고립단어로부터 가능한 문장의 수는 무한이다.

Other Issues with Continuous Speech

  • 사람마다 말하는 속도가 다르다.
  • 문장으로 구성되었을 경우 발음이 변하는 경우가 있다(예: Did you -> Dijjou)
  • 구어체, 즉흥 발화의 경우 아무 의미도 없는 단어나 잘못된 단어, 비문이 나올 수 있다.

Treat it as a series of isolated word recognition problems?, Recording only Word Templates

  • 입력 음성을 통해 "thiscar" 라는 텍스트를 얻어냈다. 이걸 this car로 인식해야 할까 the scar로 인식해야 할까?
  • th iscar 같은 것은 어떤가?
  • 세 단어로 이루어져 있을 수도 있는데, 몇 개의 단어로 구성되어 있는지는 어떻게 알까?

A Simple Solution, Building Sentence Templates, Handling Silence, Sentence HMM with Optional Silences, Composing HMMs for Word Sequences

  • word template들을 준비하고, word templates을 가지고 sentence templates를 만들자(composition). 만들 때 온갖 변수를 고려하여 만들자.
  • red, green, blue라는 word template이 있다면, 이걸 가지고 그냥 이어서(???) redgreenblue라는 문장 템플릿을 만들 수 있다.
  • 이렇게 만들면 사람이 끊어 말할 때 인식이 잘 안되므로 "silence" state를 만들어 단어 사이사이에 '옵션으로' 넣자.
    • silence state는 묵음 구간에 대해 학습시킨 것이다.
  • 그냥 red, green 모델을 이어 붙이면 red의 마지막 state(loop를 가지고 있음) 와 green의 시작 state는 어떻게 붙여야 할까? transition 확률을 정할 수가 없다!
    • 각 단어 모델에 대해 loop가 없는 start, end state를 추가하여 각자의 시작과 끝을 책임지게끔 하자. start, end state는 non-emitting state이다.

Connecting Words with Final NULL States, Retaining a non-emitting state between words, Viterbi with NULL states

  • 이제 word1과 word2 모델을 붙일 때 word1의 end state만 떼면 word2에 자연스럽게 붙일 수 있다.
  • 하지만 word1의 end state를 남겨둔 채로 붙이는 게 더 유용하다. (왜?)
    • word2로 진입하는 확률이 무조건 1이 되고, non-emitting state에서만 word2로 갈 수 있기 때문(? 이라고 한다)
  • non-emitting state는 viterbi decoding에 영향을 미친다.
  • state segmentation을 얻는 과정에 영향을 미친다 (어떻게?)
  • 이는 실제 word sequence를 인식할 때 중요히다 (왜?)
    • (내 생각) non-emitting state를 남겨두면 유용한 이유는 단지 수식적으로 다루기 편해서 그런 것 같다. 그림 상으로만 보면 솔직히 왜 좋다는지 이해가 잘 안된다. non-emitting state를 없애버리고 viterbi decoding 수식을 다시 쓰면 '이전 단어'에 대한 표시를 해줘야 한다. 즉 이전 단어에 의존적인 식이 되어버리는 것이다. 하지만 non-emitting state를 그대로 사용한다면 viterbi 수식상으로 이전단어가 뭐든 개의치 않고 그냥 non-emitting state에서 오는 확률 term을 추가해주기만 하면 된다. 이러면 queue를 사용한다든지 재사용을 한다든지 여러 이점이 있을 것 같다(그냥 그럴 것 같은 느낌만 있다)

Speech Recognition as Bayesian Classification, Statistical pattern classification, Isolated Word Recognition as Bayesian Classification

  • 듣지 않아도 알 수 있는 것들이 있다. 살면서 SEE와 ZEE 중 당연히 SEE를 더 많이 듣는다.
  • Basic DTW는 word prior에 대해 고려하지 않았다.

Computing P(X|word), Factoring in a priori probability into Trellis, Time-Synchronous Trellis

Why Scores and not Probabilities

  • score(log probability)를 쓰면 곱셈을 안해도 된다. 그리고 underflow도 없다.
  • Deeper reason
  • score를 쓰면 trellis를 덜 쓸 수 있다(메모리 절약).
  • 어차피 forward probability를 사용할 수 없다.

Statistical classification of word sequences ~ Decoding to classify between word sequences

  • close file 이라는 문장을 delete file보다 보통 더 많이 사용한다. (무슨 이런 예를 들지…)
  • 이 부분은 trellis 그림이 대부분이라 스킵한다
  • 중간에 max(max(dogstar), max(rockstar)) = max(max(dogstar1, rockstar1), … )가 가능한 이유는 argmax가 commutative라서 가능하다는데 이게 commutative와 뭔 상관인지 모르겠다.
  • dogstar와 rockstar의 경우 star가 겹치고 synchronous state들의 경우 star의 start state부터는 path가 겹치기 때문에 미리 max로 비교해도 된다(?)

The Real "Classes"

  • Dog Star, Rock Star class가 따로 있는게 아니라 합쳐진 형태의 Dog,Rock - Star 가 하나 있는 것이라고 생각해야 한다(이제부터는 정말로 그렇게 생각해야 한다)
  • 이런 식의 reduced graph로 나타낼 수 있는 이유는 viterbi 알고리즘에 따라 best path score만 사용하고 있기 때문이고 forward propbability를 사용할 수 없기 때문이다.

Language-HMMs for fixed length word sequences

  • word graph가 나타낼 수 있는 모든 가능한 word sequences를 "language"라고 한다(의미심장…)
  • word graph도 HMM이라 볼 수 있다.

Where does the graph come from

  • 인식 어플리케이션에 따라 graph를 정해줘야 한다.

Language HMMs for arbitrary long word sequences

  • word graph로부터 임의의 길이를 가지는 word sequence도 만들 수 있어야 한다. 이러려면 word-graph 자체에 loop가 필요하다.
  • 자연어를 대상으로 하는 음성인식이 아니라면 constrained vocabulary를 쓰는 것이 현실적인 방법이다.

2018년 9월 2일 일요일

180902 CMU 음성인식 ppt 노트 - 8. HMMs

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

The scalar gaussian function

  • gaussian의 장점: 샘플 데이터로부터 평균과 분산을 구할 수 있음 (이 이유 때문에 쓰는 건가?? Central Limit Theorem 때문이 아닌가?)

The HMM as a generator

  • 제목 그대로

Viterbi and DTW

  • Viterbi 알고리즘은 DTW에서 수행하던 알고리즘과 같다

Training by segmentation: Hard assignment with Gaussian mixtures

  • HMM의 파라미터 재추정을 위해 앞서 DTW에서 봤던 segmental K-means 알고리즘을 적용할 수 있다.
  • 템플릿을 가지고 트레이닝 데이터에 대해 best path를 찾아 segmentation 하고, 그걸로 템플릿의 각 segment를 모델링하고, 다시 best path를 찾고, 다시 segment를 모델링하고…
  • hard assignment로 진행된다.
    • 한 segment를 모델링하기 위해 사용되는 feature set은 다른 segment에는 사용되지 않음
  • 그런데 segment가 Gaussian이 아니라 GMM이면 어떻게 모델링할 수 있을까?

Gaussian mixtures: a "hard" perspective

The K-means algorithm

  • 초기 K개의 클러스터(mixture)를 정하고, 주어진 feature들에 대해 거리를 계산하여 가장 가까운 클러스터에 속하게 한다.
  • 주어진 모든 feature에 대해 수행하고, 각 클러스터에 속한 feature들에 대해 평균과 분산을 다시 계산한다

A better technique

  • Segmental K-means 알고리즘은 주어진 특정 feature가 어떤 state에 가장 가까운 거리면 '당연히 100%' 속하는 것으로 봤다
  • 하지만 특정 feature가 100% 어떤 state에 속할리가 없다. 확률적으로 '어느 정도로만' 속한다고 봐야 한다
  • Soft assignment를 사용한 segmentation을 하자

Training by segmentation: soft assignment(1 Gaussian case)

  • state의 gaussian의 평균을 구할 때 feature들을 그냥 더하지 않고 state, 시간별로 확률 값 f를 다르게 주어 구하자.
  • 그럼 이 f는 어떻게 구하나?
  • f = P(state(t) = s, x1, x2, … , x_T) 가 된다.
    • 이거 완전 forward/backward algorithm으로 alpha, beta 구하라는 소리다
    • 이게 Baum-welch다

Case 2: State output densities are Gaussian mixtures

  • GMM으로 가면 mixture weight까지 추정해야 한다
  • 음… 수식이 너무 커서(그냥 너무 크다) 솔직히 한 30분 동안 쳐다보지 않으면 파악 못할 것 같아서 이 부분은 스킵한다
  • 병렬적으로 충분통계량을 계산할 수 있는 장점이 있다
  • iteration을 돌면서 mixture 하나가 너무 큰 variance를 가지면 그걸 둘로 쪼갠다.
  • 이 때 mixture weight는 둘로 쪼개진 각각의 mixture가 반씩 가지는 것으로 한다.

Transition by soft counting

  • state의 분포말고 transition probability도 hard/soft counting이 있다
  • hard는 관찰 결과가 best path의 한 state에서만 나왔다고 보는 것이고, soft는 확률적으로 나왔다고 보는 것이다.

Implementation of BW: underflow

  • forward, backward algorithm에서 alpha(혹은 beta)를 계산하려면 많은 곱셈이 필요하여 underflow가 일어나 버린다.
  • 각 time step마다 alpha를 스케일링 한다(이래도 되나?)
  • log domain에서 alpha와 beta를 계산하는 방법도 있다. 확실치는 않다
  • (CTC 책에 소개된 바 있다)

Implementation of BW: pruning

  • forward, backward 알고리즘 계산은 매우 부담이 되므로, 각 time step마다 pruning을 적용하여 해결한다
  • convergence 판정과 테스트 성능에 영향을 미칠 수 있다(자세한 내용은 뒤에…)

How many Gaussians

  • 경험적으로 고립단어 인식에 최소 4개는 필요하다

Isolated word recognition: Final thoughts

  • 이 내용은 고립단어인식에만 국한된 것이다. 연속음성인식에 대해서는 아무 얘기도 하지 않았다(;;;)

180902 CMU 음성인식 ppt 노트 - 7. Templates to HMMs

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

Improving the templates

  • 한 단어당 여러 template들을 합쳐서 나타내면 generalized template을 얻을 수 있다.
  • 단순히 여러 template들의 평균을 내면 될 것이다.
  • 각 template들의 길이가 다른데, master template을 정해서 그걸 가지고 다른 template들에 대해 DTW를 적용하면 된다.
  • master template은 어떻게 정할까? -> trial and error

Template size reduction

  • template 갯수만 줄이지 말고 한 template 내의 segment(예를 들어 알파벳 하나)를 나타내는 feature sequence를 하나의 feature로 나타내자
  • 이것 역시 그냥 한 글자에 해당하는 feature sequence를 평균내면 된다.
  • 그런데 segment마다 평균으로 퉁치면 다 해결될까? segment 마다 feature의 variation 이 다를 수 있다.
  • 공분산을 고려하자(covariance)
  • 평균과 공분산까지 있으면 이제 input feature에 대해 각 segment에 대응하는 cost를 계산할 수 있다
    • mahalanobis distance
    • 혹은 negative gaussian log likelihood

Segmental K-means

  • 근데 segment는 어떻게 정했나? 그냥 uniformly segmentation 해서 쓰면 될까?
  • ㄴㄴ training set에 대해 스스로 DTW를 돌리고 다시 segment마다의 평균과 공분산을 구하고… 반복하자
  • 어디서 많이 봤다 (EM algorithm)

DTW with multiple models

  • input feature sequence에 대해 path를 찍다가 특정 segment에 오래 머물러서 나오질 않는 경우가 있다
  • 그 segment가 원래 정답이든 아니든 그냥 특성상 웬만한 feature와 거리가 가깝게 나올 수 있다. 하지만 이래선 곤란하다
  • 특정 state에 계속 있을 경우(즉 loop를 돌 경우) insertion panelty를 주자
  • 한 segment에서 다음 segment로 넘어갈 때의 transition score도 주자
  • (panelty라고 쓸 땐 그냥 작은 score라고 생각하면 될 것 같다)
  • transition score는 어때야 할까?
  • negative log를 쓰자. 낮은 확률에 대해 아주 큰 페널티를 주는 효과가 있다

Modified segmental K-means AKA Viterbi training

  • 초기 segment에 대한 score는 어떻게 줄까?
  • 일단은 uniformly 주고, training set 자기 자신에 대한 DTW를 진행할 때마다 segment가 나타난 횟수를 다시 세서 만들자
  • 이거 완전히 HMM에서 하는 것과 비슷하다
  • 이제부터는 segment를 state로 부르기로 하자

Determining the number of states

  • 원래 문제로 돌아가서, word 하나는 state 몇개로 나타내야 할까?
  • segment의 갯수가 작을수록 좋지만 최소 단어 하나당 하나는 있어야 할 것 같다(단어마다 구분은 해야지)
  • 알파벳마다 하나의 state를 줄 수도 있다.
  • 일본어의 경우 발음 하나가 한 state에 해당하게 할 수도 있다.
    • (입문용 내용이라 지금의 이론과는 다를 수 있습니다)

What about the transition structure

  • left-to-right Markov chain이면 된다.
  • 이것을 Bakis topology라고 한다

180902 CMU 음성인식 ppt 노트 - 5. Dynamic Time Warping

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

Class 5 - DTW

Sequence matching on recorded speech

  • Template: example recording
  • Isolated word recognition

DTW

Every input frame must be matched to one of the templates

  • Different from the Levenshtein distance where there are insertions and deletions
  • No vertical transition (this is less often used because it makes their costs not easily comparable (How?))
  • All symbols must be compared with the template for getting cost

No edge(transition) cost

  • node costs only

Dissimilarity measure between an input frame and template frame

  • (simply) Euclidean distance
  • Or Manhattan metric, L1 norm, Weighted Minkowski norms(generalized version of LX norm)

Handling Surrounding Silence

  • The transition structure does not allow a region shrinking more than 1/2
  • Warping transition needed

Time synchronous search

  • Parallel computing on trellises
  • Enables real-time

Confidence scoring, confidence estimation

  • Is the lowest cost path always answer?
  • confidence threshold needed
  • There is no applicable cost measure. So we need to determine a threshold
  • Recognizing many samples -> Training confidence classifier(how?)

번거로우니까 그냥 한글로 쓴다. 영어로 쓰니까 시간이 너무 많이 걸리네

Confidence scoring for string match

  • string matching에서는 적당히 fixed threshold 정하면 됐다.
  • Application 따라 적당히 정하면 된다.

Confidence scoring for DTW

  • 하지만 DTW의 경우 threshold를 정해도 그게 무슨 의미가 있는 값은 아니다.
  • 즉 confidence classifier 같은 것을 학습하는 것이 필요
  • 높은 confidence로 제대로 맞춘 sample 들과 낮은 confidence로 못 맞춘 sample들 간의 적절한 confidence threshold를 알아보면 된다.
  • confidence threshold를 정하는 방법
  • 많은 training sample에 대해 confidence 내보고
  • threshold 다시 정하고 (retraining)
  • test
  • threshold 정하기 전 DTW cost는 normalization 되어야 한다.
  • 솔직히 confidence threshold로 쳐내는 방법은 잘 안된다. (correct, incorrect 분포 간에 많이 겹친다)

N-best list

  • 스마트폰으로 글을 쓸 때 여러 후보를 자동으로 추천해주듯이, best path 하나 말고 여러개를 보여줘서 사용자가 선택하게끔 하는 것

Improving accuracy: multiple templates

  • 한 단어 당 template을 하나만 사용하니까 문제가 발생한다.
  • 다른 화자에 대해 취약
  • template을 여러개 사용하면 된다
    • template을 여러개 사용하면 계산량이 많아진다

Pruning

  • 계산량을 줄이기 위해 pruning을 하자

  • diagonal의 width를 고정해서 하자

  • width를 뛰어 넘을 수도 있는 warp를 가진 path가 죽을수도 있다.

  • 그리고 speech에 대해서 diagonal에 해당하는 개념이 무엇인가? 모호하다

  • fixed cost threshold

  • 유연하지 못하다

  • relative fixed beam

  • 특정 시점의 best cost node의 값에 대해 상대적으로 가까운 K개만 남기고 다 쳐내자

  • K개만 살아남는다

  • Beam search

  • 특정 시점의 best cost node의 값에 대해 상대적으로 T 이내에 들어오는 cost를 가진 path는 전부 살리자

  • 살아남는 path가 아주 많아질수도 있다(인식률이 낮을 때 beam search 방식에서 디코딩 시간이 많이 느려지는 이유)

  • 계산 시간 예측이 안된다

  • T는 휴리스틱으로 정한다 (주로 WER이 consistently 낮아지기 시작하는 부분에서 정한다)

  • 그래도 지금까지 가장 많이 쓰인다

  • 하여튼 pruning을 쓰면 word 당 template의 갯수가 늘어나도 상관없이 연산 시간이 일정하다(완전 그런건 아닌 것 같은데…)

  • pruning을 쓰면 trellis를 많이 저장할 필요가 없어지기 때문에, 추가로 요구되는 메모리도 별로 없다

  • 그래도 book-keeping overhead는 필요하다(특별히 book-keeping 이란 단어를 쓴 이유라도?)

  • pruning을 쓰면 globally best path가 완전히 나온다고 할 수는 없다 (locally sub-optimal path)

180902 CMU 음성인식 ppt 노트 - 4. Text matching

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

Class 4 - Text matching

Edit distance

  • How do we compute minimum distance between template 'ABBAAACBADDA' and input 'CBBBACCCBDDDDA'?
  • It also called 'cost, 'Levenshtein distance'

Insertion

  • template: DDA
  • input: DDDDA
  • insertion: DD(DD)A

Deletion

  • template: AACB
  • input: CB
  • deletion: (AA)CB

Substitution

  • template: BBA
  • input: CBA
  • substitution: (C)BA

Find the minimum edit distance!

  • But it is computationally intractable. (possible paths exponentially increase)

To get minimum edit distance, use dynamic programming(DP)

  • DP allows using the previous result(minimum edit distance at the previous stage).
  • Of course, DP needs a back-pointer to track an optimal path.

Memory cost for string matching

  • 2 columns only needed
  • In most cases using in-place, only 1 column needed

Parallel computation

  • Stacking trellises along with columns, Then all trellis can be computed concurrently.

Trellis sharing -> template sharing -> lexical trees (!!!)

  • Having one sub-trellis belonging several trellises

Pruning

  • Heuristic, the right threshold should be found

Pruning by limiting search path

  • Having a width on diagonal
  • Cons: hard to imagine diagonal on lexical tree

Pruning by limiting path cost

  • kill partial paths which have large cost
  • Cons: how can we define the threshold?
  • the absolute cost increases along with the length of the path!

Beam search

  • Thresholding with relative cost T
  • How can we define the threshold? -> heuristically -> It works great to many cases!