180919 Log odds, odds... logistic regression란 도대체 뭘 하는 걸까?

https://en.wikipedia.org/wiki/Odds

• https://en.wikipedia.org/wiki/Logistic_regression
• https://wiki.lesswrong.com/wiki/Log_odds
• Youtube: StatQuest: Odds and Log(Odds), Clearly Explained!!!

궁금

1. 왜 odds라는 용어가 필요한 건가? odds가 뭔가?
2. log odds를 쓰는 이유는 그냥 곱하기를 더하기로 만들기 위해서인지?
3. logistic regression이 log odds를 쓰는 이유가 뭘까?

설명

1. odds: A, B 팀이 경기를 할 때, A의 odds of winning은 아래 ratio로 나타난다.

• 'A가 이기는 횟수' : 'B가 이기는 횟수'
• odds는 확률이 아니다. 확률을 이용해 odds를 계산할 수 있다. = p / (1-p)

1. odds가 대칭이면 직관적으로 분석하기 쉽다… (두 팀의 odds를 비교한다든지)

• 예를 들어, 1/6과 6/1은 log(1/6) = -log(6/1) 이므로 두 odds가 역수 관계에 있다는 것을 간단히 알 수 있다.

1. 어떤 event를 log odds의 히스토그램으로 나타내면… normal distribution 꼴이 된다.

• true / false, yes / no 등의 task를 푸는데 통계적으로 적합하다.

180913 CMU 음성인식 ppt 노트 - 27(끝). Rescoring, Nbest and Confidence

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

아무것도 모르고 쓰는 기분이 든다.

요약

1. viterbi search로 얻어낸 entries는 tree구조를 가지고 있다. 이 tree에 추가로 edge를 넣어준다. 이것이 lattice이다.
2. lattice에 대해 A* algorithm으로 best path를 찾는 것이 decoding이다.
3. A* algorithm 시 edge cost를 더 복잡한 n-gram으로 대체하여 다시 디코딩 하는것이 rescoring이다.
4. path를 구성하는 word의 confidence = posterior = (all path prob through the word)/(all path prob)

추가 설명

1.

• entry: (id, time, parent, score, word)
• edge를 넣는 방법: tree 내 start, end 시간대가 인접한 word끼리 edge로 연결해준다.

2.

• stack decoder를 쓰지 않는 이유는 stack에서 pop을 할 때 cost가 비교적 낮은 초기 node의 path만 튀어나오기 때문이다.
• A* algorithm은 path cost를 계산할 때 애초에 dijkstra 알고리즘으로 sink node까지의 cost를 미리 계산해둔 것을 반영하기 때문에 초기 node path만 stack에서 튀어나오는 경향이 덜하다.
• Dijkstra's algorithm: Directed Acyclic Graph의 특정 두 node 간 최소 cost path를 찾는 것

4.

• (all path prob through the word)를 계산하기 위해 미리 forward, backward algorithm을 사용한다.
• forward, backward algorithm: DAG의 특정 두 node 간 total path의 total cost를 구하는 것. HMM의 그것과 같다.

이제 다시 chain model 공부를 시작할 수 있을 것 같다.

180912 CMU 음성인식 ppt 노트 - 26. Exact and Inexact Search

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

세줄 요약

1. n-gram LM graph으로 디코딩 시 n이 높아지면 확률이 희박하므로 backoff transition으로 보완한다.
2. lextree에 n-gram을 fully 적용하면 이루말할 수 없이 복잡하다. 그래서 approximated(flatted) lextree를 써야 한다.
3. 실제로 n-gram LM graph를 다 만들어 사용하진 않고, (WFST에서는 다 만들어 쓰는 것 같다) viterbi search 시 transition에 반영한다.

세줄 요약의 요약

1.

• LM graph를 만들 때 backoff를 적용한 것과 원래 trigram의 score를 비교하여 더 큰 transition을 남긴다.

2.

• unigram에서 LM score를 맨 뒤 transition에 넣지 않고 굳이 앞에서 spreading하는 이유는 디코딩 시 LM score가 함께 반영되기 때문인 것 같다.
• full lextree에선 start/end를 가지는 n-gram은 있지만 silence를 가지는 n-gram은 없기 때문에 silence transition을 start, end, 각 word의 start마다 loop로 붙인다.
• flatted lextree에선 다른 phone 과 같은 방식으로 붙인다.
• full lextree는 n-gram 마다의 lextree가 따로 마련되어 있어 n-gram transition이 경합하지 않는다. flatted lextree는 하나의 lextree를 공유하기 때문에 그 반대다.

3.

• viterbi search 시 단어 entry의 score를 계산할 때마다 해당 단어의 LM score를 반영한다.
• 예를 들어 시작 이후 trellis에서 apple이라는 단어를 완성했으면 그걸 entry에 등록하기 전에 score에 P(apple | \< s >)를 적용한다.

180912 CMU 음성인식 ppt 노트 - 25. tying states

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

세줄 요약

1. n-phone HMM을 학습시킬 데이터가 부족하다. [base phone이 같은] n-phone의 [같은 index의 HMM state]끼리 tying 하자.
2. HMM state tying 시 Maximum expected likelihood, 혹은 전문가가 만든 phone 별 특징을 기준으로 state에 대한 decision tree를 만들 수 있다.
3. decision tree에 대해 pruning을 하고 남은 leaf node가 tied state에 해당한다. tied state 끼리는 GMM을 공유한다.

세줄 요약의 요약

2.

• 흔히 생각할 수 있는 질문: base phone이 같은 n-phone 끼리 모아놓아도 어차피 초기 모델은 서로 같아서 likelhood가 다 같을 거 아니냐? 구분을 어떻게 해?
• 실은 SI phone(monophone) 학습 이후 untied SD phone(n-phone)에 대해 학습을 한번 해둔다.
• 내 생각: phone 특징만 기준으로 사용하면 HMM state index에 상관없이 같은 형태의 tree가 만들어 질 것 같은데, 이후 ML도 적용해야 하지 않을까? 이 부분이 교재에선 생략된듯
• likelihood는 주어진 데이터셋을 가지고 계산한다.

3.

• GMM을 통째로 공유하는 방식도 있지만 mixture weight는 따로 가진다든지 하는 variation이 있다.
• tied state를 senone이라 부른다. 즉 phone HMM은 senone을 가지는 것이다.
• (senone이 언어학적 정의를 갖고 있는게 아닌것이었군! 검색해도 딥러닝 관련 얘기만 나온다)

180912 CMU 음성인식 ppt 노트 - 21. Subword units

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

세줄 요약

1. 단어 HMM을 그대로 학습시키자니 딱 그 단어에 맞는 데이터가 희소하다. phone HMM을 쓰면 같은 학습 데이터로도 충분하다.
2. 그냥 phone만 쓰면 될줄 알았더니 좌우 phone에 따라 locus가 달라지는 현상이 있어 n-phone 을 써야한다.
3. n-phone을 쓰면 데이터가 exponentially 필요해 진다.

세줄 요약 각각의 세줄 요약

1.

• phone을 어떤 기준으로 정해야 할까? 다 다르다. 언어학자(?)들이 정리한 것을 쓸 수도 있다.
• Zipf's Law: 일어날 횟수가 적은 event들은 엄청 많고, 일어날 횟수가 많은 event는 엄청 적다.
• 데이터셋 내 word 분포의 경우 Zipf's Law를 너무 충실히 반영해서 문제다. phone은 덜하다.

2.

• n-phone을 쓰면 앞/뒤 단어 내 end/start phone HMM 간 의존성이 생긴다. biphone의 경우 앞/뒤 단어 내 end/start phone HMM을 공유한다,
• 단어 HMM을 만들 때 non-emitting state 끼리 이어 붙일지 생략하고 붙일지의 선택지가 있다. 후자의 경우 앞뒤 phone HMM간의 transition 수가 (아주 많이) 추가로 생긴다.
• 단어 character는 같은데 phone이 다른 경우는 phone HMM을 병렬로 붙인다. 이 때 각 phone 으로의 transition끼리 normalization을 하는게 수학적으로 타당하지만 안하는게 더 잘된다.

3.

• biphone의 경우 Zipf's Law를 잘 따르지 않는다. triphone의 경우 아주 잘 따른다.
• 데이터가 없는 triphone의 경우 back-off를 쓴다.

180912 CMU 음성인식 ppt 노트 - 19. Ngrams

katz smoothing 등의 실제 ngram을 만드는 과정은 건너 뛰도록 한다.

두줄 요약

1. CFG를 쓴다 해도 모든 문장의 그래프를 만들 수는 없다. n-grams markov 모델로 근사하여 그래프를 만들자.
2. bigram, trigram 다 좋은데 그래프에서 node 간 연결할 때 ambiguity가 있으면 안된다. (한 node에 연결된 node 끼리는 history가 일치해야 한다)

180911 CMU 음성인식 ppt 노트 - 15. Backpointer tables, training with continuous speech

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

세줄 요약. 최대한 세줄로 요약할 수 있도록 노력하자. 손가락 아프다.

1. 연속음성인식에서 viterbi search를 해보자. table을 다 저장하면 아까우니까 best word가 만들어질 때마다 그걸 엔트리에 저장하자.
2. n-best를 보고 싶을 수 있으니 경쟁 단어들도 같이 저장해두자.
3. 트레이닝 발화 각각을 모델링하는 문장 HMM을 준비해서 EM을 하자. silence의 경우 얼마나 나올지 모르니 silence loop를 만들자.

세줄 요약 각각에 또 세줄 요약을 해보자.

1,2. Trellis with Complete Set of Backpointers

• 특정 시점의 best 단어를 저장할 엔트리의 구조는 (idx, time, score, parent)인 것 같다. (예: (1, t=0, scr1, p=0)) (나중 챕터에 등장한다)
• 왜 단어만 저장하나? 어차피 목표가 best 문장을 만드는 것이라면 word만 이어 붙이면 되기 때문에 trellis 같은 것은 필요없다.
• n-best 문장을 구하고 싶은 경우가 있다. 이를 위해 best-word의 경쟁 단어들도 저장하자. 어차피 이렇게 해도 그냥 table 저장보다는 효율적이다.

3. word models from continuous speech recordings and related practical issues

• 단어 HMM 사이사이에 silence HMM을 추가하여 발화 내 단어 사이의 묵음 구간을 모델링하자.
• silence HMM은 initial silence HMM이 있으면 더 잘 학습된다.
• trellis 사이즈 너무 크다. HMM 전체 EM 못한다. 높은 스코어를 가지는 partial path에 해당하는 HMM만 그때그때 남겨서 학습하자.
• (영원히 낮은 스코어를 가지는 partial path가 생겨버리면 어떡하지?)

180909 Hands-On Machine Learning with Scikit-Learn and TensorFlow 노트

link: http://shop.oreilly.com/product/0636920052289.do

1. The Machine Learning Landscape

• 머신러닝 시스템 타입에는 이것 저것… 외에 Instance-Based(kNN 같은 것들), Model-Based 가 있다.
• 머신러닝을 하는데 있어 아래 사항들이 거슬린다.
• 데이터의 양이 부족
• 트레이닝 셋이 데이터 분포를 제대로 표현하지 못하는 것 ( Nonrepresentative )
  • 샘플링 잘못하면 Sampling Bias가 생김
  • (예시: Landon과 Roosevelt의 지지율 조사 시 Literary Digest의 요청에 호의적인 구독자들이 표본집단의 대부분을 차지했음. 이 구독자들은 Republican일 가능성이 높았음)
• 데이터의 질이 떨어짐
• 의미없는 feature들이 있음
• 트레이닝 데이터에 Over(Under)fitting 됨
• 모델의 generalization을 위해 Test와 Validation을 수행하지만 There's no such thing as a free lunch.

2. End-to-End Machine Learning Project

아직은 intro라서 대강의 말만 있다.

• Data preparation pipeline을 구성하자.

• 성능 지표를 설정하자. 대표적으로 RMSE와 Mean Absolute Error(MAE)가 있다. MAE는 데이터 내에 outlier가 많을 때 유용하다.

• 가정이 뭐였는지 확인하자.

• 데이터를 시각화하자.

• Correlation을 보자. (Standard correlation coefficient를 보는 방법이 나왔지만 2차원 시각화라 딱히…)

• Scikit-Learn은 굉장히 잘 디자인된 패키지다. 제공하는 Object들은 모두 다음의 형태를 가지고 있다.

• Estimators: 데이터셋으로부터 파라미터를 추정함

• Transformers: 데이터셋을 변형해서 변형된 데이터셋을 만들어줌

• Predictors: 입력 데이터로부터 예측을 수행

• Feature Scaling

• Min-max scaling: (데이터 - min) / (max - min), 많은 사람들이 normalization이라 부름 (엥?), outlier에 취약

• Standardization: 0 mean unit variance, DNN에 넣기 좋음(DNN은 input value(아마 절대값)가 0~1 사이일 때 잘 작동하기 때문)

• Grid Search

• hyperparameter를 찾기 위해 Grid Search를 돌리자.

• hyperparameter를 어떤 값으로 해야 할지 전혀 감이 안잡히면 10승 단위로 grid를 준비하자. 그 다음에 세밀하게 튜닝하면 된다.

• Randomized Search

• hyperparameter가 여러개라면 Grid Search를 그냥 돌릴 수 없다. grid 위에서 hyperparameter를 무작위로 골라 성능을 확인하자.

• Ensemble Methods

• 7장에서 보자.

3. Classification

• 트레이닝 셋의 instance의 class에 기준으로 무작위로 섞지 않으면 오작동하는 classifier도 있다.

• 예를 들어 첫 번째 50개는 class A고, 나머지 50개는 B고 이런식으로 되면 좋지 않을 수 있다.

• MNIST에서 '5'만 맞추는 binary classifier가 있다고 하자. 이 classifier의 accuracy가 90%이다. 좋은 성능의 classifier인가?

• 무턱대고 전부 '5가 아님'이라는 예측만 해도 90%를 달성할 수 있다.

• Confusion matrix

| -- | predicted - negative | predicted - negative | |---|---|---| | Actual - Negative | TN | FP | | Actual - Positive | FN | TP |

• Precision: TP / (TP + FP), true label을 가지는 instance가 부족하거나 TP가 매우 중요할 경우

• Recall(sensitivity 혹은 true positive rate): TP / (TP + FN), FN가 매우 중요할 경우

• F1 score: Precision과 Recall의 기하평균. 어떤 metric에 비중을 둬야 할지 잘 모를 경우 이렇게 한다.

• Precision / Recall Tradeoff

• classifier가 고정된 시점에서 Threshold의 조정만으로 Precision과 Recall을 둘 다 높일 수는 없다.Trade-off가 있다.

• PR curve를 그려서 어느 지점에서 타협을 봐야 하는지 분석할 수 있다.

• ROC Curve

• sensitivity vs (1 - specificity) curve

• true negative rate(specificity): TN / (TN + FP)

• false positive rate: FP / (FP + TN)

• Area under the curve(AUC)

• ROC 혹은 PR curve의 아랫 부분이 차지하는 면적. 1에 가까울 수록 좋다.

• Multiclass Classification

• Binary classifier로 multiclass classifier를 만드는 방법

• 1. one-versus-all(OvA): 클래스 마다 그것만 맞추는 classifier를 만든다.

  • 클래스 갯수만큼 binary classifier가 필요

• 2. one-versus-one(OvO): 클래스 pair에 대해 binary classifier를 만든다.

  • 클래스 두개의 combination 만큼 binary classifier가 필요. 클래스 수가 많아지면 combination이 폭발한다…
  • SVM의 경우는 많은 데이터에 대응할 수 없기 때문에 이 방식을 쓴다.

• Error analysis

• matplotlib의 matshow() 함수로 confusion matrix를 gray scale 2d image로 다시 나타내면 그 특성을 확연히 볼 수 있다.

• 특정 클래스가 어두울 경우 데이터의 단순 부족, 혹은 해당 classifier의 낮은 성능 때문이다.

• Multilabel Classification

• multiclass는 여러 class 중 하나를 맞추는 것이고 multilabel은 답 자체가 여러개인 것이다.

• 예: 사진에 나온 인물이 누구누구인지? 맞추는 문제

• metric을 이용해 성능을 평가할 때, label 별로 weight를 다르게 줄 수도 있다.

• Multioutput Classification

• multiclass + multilabel

• 이미지 노이즈 제거 같은 task

• regression과 거의 다를 바 없음 (그나마 classification이라고 한 건 output이 discrete이니까…)

4. Traning Models

• Linear Regression

• RMSE 대신 MSE를 쓰자. sqrt 굳이 할 이유가 없다. (RMSE는 왜 쓰지? -> error와 같은 scale로 만들어서 분석하기 위해)

• The Normal Equation

  • closed-form solution을 도출 가능. （一発で得られる）
  • 하지만 feature의 갯수가 많아지면 역행렬 계산에 너무나도 많은 시간이 걸린다.

• linear regression은 데이터 갯수가 많아져도 prediction 시간이 linearly 늘어나기 때문에 계산 시간 고민을 안해도 된다.

• Batch Gradient Descent

• partial derivative와 gradient의 차이(맨날 까먹는다): partial derivative는 scalar고 gradient는 vector. gradient의 요소로 partial derivative가 있다고 보면 된다.

• Convergence Rate

• tolerance e에 수렴시키기 위한 iteration 수가 k 라면, e/10의 tolerance에 수렴시키기 위해서는 10*k 번의 iteration이 필요하다.

• Stochastic Gradient Descent

• out-of-core algorithm(데이터를 메모리에 전부 올릴 수 없는 알고리즘)에 사용하기 위한 방법이다.

• learning rate가 고정일 경우 영원히 수렴하지 못한다.

  • simulated annealing(learning rate를 점차 줄이는 방법)을 쓴다. (annealing이라고 한 이유는 담금질에서 점차 식히는(?) 과정과 비슷하기 때문)

• Mini-batch Gradient Descent

• SGD는 너무… noisy하다. mini-batch 짱짱맨

• Polynomial Regression

• feature를 polynomial feature로 만들어서 그것에 대해 linear regression 하는 것

• Learning Curves

• underfitting: validation과 training curve가 평평하고 서로 가깝고 값 자체가 클 때

• overfitting: training curve가 validation에 비해 상당히 낮고 둘 사이가 멀 때

  • 해결책: 데이터를 더 넣어라

• The Bias/Variance Tradeoff

• Bias: 모델 가정을 잘못한 경우. underfitting이 되어버린다. 예: data는 quadratic인데 linear regression을 할 경우

• Variance: 모델에 degree of freedom이 너무 커서 데이터의 작은 변화에 sensitive 할 때

• Irreducible error: 데이터 자체에 들어 있는 noise에 의한 것. 데이터를 전처리 하자.

• Regularized Linear Models

• Ridge Regression: 그냥 L2 norm을 cost function에 추가한 것 (왜 ridge일까?)

• Lasso Regression: L1 norm을 추가한 것

  • feature 차원이 training instances보다 많아지거나 서로 correlated라면 에러가 발생하기 쉽다.

• Elastic Net: L2 norm과 L1 norm을 추가한 것

• Regularization을 적용하면 데이터의 scale에 민감해지기 때문에 데이터를 미리 scaling 하자.

• Logistic Regression

• Odds를 regression하는 것

• Logit: Logarithm of odds

• Odds: 가능성. (통계학에서) P / (1-P) (그런데 위키피디아에서는 (1-P) / P 이다. (???)

• 그런데 logistic function은 1 / (1 + exp(-t))로 생겼잖아? 이거랑 Logit, Odds랑 뭔 상관이지?

• Logistic Regression은 closed-form solution이 없다. 대신 cost function이 convex이긴 하다.

• Cross Entropy

• 어떤 정보(?)를 보낼 때 필요한 평균 bits (정보에 확률을 얹어서(cross) 평균 bits를 계산함)

• Softmax와 Logistic regression의 output은 확률이기 때문에 cost function이 자연스럽게 cross entropy가 된다.

• X entropy의 두 극단이 각각 entropy, KL divergence와 대응하는데 교재 설명만으로는 일반화하기 어려울 듯. skipped

5. Support Vector Machines

• SVM은 데이터가 커지면 복잡해진다(뭐가 복잡해지지?)

• Linear SVM Classification

• SVM은 feature scale에 sensitive하다. scale이 변하면 margin도 변하기 때문

• Soft margin Classification

  • Hard margin의 경우 margin violation을 아예 허용하지 않는다. 하지만 outlier 때문에 어느정도는 타협해야 한다.
  • margin 폭을 유지하면서 margin violation인 instances를 어느 정도 허용한다(어느정도라는게 어느정도?)

• Nonlinear SVM Classification

• linearly separable이 아닌 data에 대해서는 polynomial feature를 만들어 SVM을 수행하자.

• Polynomial Kernel

• polynomial feature가 잘되긴 하는데 degree가 높아지면 계산해야 할 것들이 너무 많아진다.

• polynomial kernel을 쓰면 combination explosion이 없다.

• kernel의 degree는 어떻게 정해야 할까? Grid Search로 정한다. (초기엔 coarse, 나중엔 fine)

• Adding Similarity Features

• similarity function을 가지고 feature들을 여기에 넣어 새로운 차원에서 나타내자.

• 주로 Gaussian Radial Basis Function(RBF)를 주로 쓴다.

• RBF의 landmark는 어떻게 정할까? -> 일단 training instances 각각을 landmark로 줄 수 있다. 하지만 이렇게 하면 새로운 차원이 instances 수 만큼 되버리기 때문에 파라미터가 너무 많아진다.

• Gaussian RBF Kernel

• 위 문제를 해결하기 위해 kernel trick을 사용할 수 있다. (수식적으로는 어떻게??? landmark를 적절한 수만큼 만들어도 training instances 마다 landmark를 준 것과 비슷한 효과를 낸다는 것 같은데…)

• 다른 kernel로는 DNA나 문자열 간의 edit distance(levenstein distance)를 계산하는 String Kernel이 있다.

• SVM Regression

• Classification의 경우 margin violation을 제한하면서 margin을 넓혔다.

• Regression의 경우 margin violation을 제한하면서 최대한 많은 instances에 fitting되도록 한다.

  • (margin violation을 제한한다는게 솔직히 뭔 말인지 모르겠음)
  • margin 내에 들어오는 새로운 데이터에 대해서는 insensitive이다. (이걸 e-sensitve라 한다)(???)

• linear SVM의 경우 (Regression이든 Classification이든) dataset이 늘어나도 scale(무슨 scale?)이 linearly 증가하지만, non-linear SVM의 경우는 더 커지기 때문에 (느려진다) (어떤것이 느려지지? 무슨 교재가 이래?)

• Decision Function and Predictions

• Linear SVM classifier prediction

• y = 0 if wx + b < 0 else 1

• Training Objective

• decision function의 w의 기울기가 낮을 수록 margin이 넓어진다.

• target을 +1, -1로 정하면 margin violation에 대한 constraint를 t(wx + b) >= 1로 정할 수 있다(hard margin일 경우).

• 즉 SVM classifier objective는

  • minimize (1/2)||w||^2 : 낮은 slope, ||w|| 대신 (1/2)||w||^2를 쓴다. (미분 가능하기 때문)
  • subject to t(wx + b) >= 1 : Low margin violation

• soft margin objective의 경우, (1/2)||w||^2 + C * sum(zeta_i) 를 최소화한다.

  • 여기서 zeta는 해당 instance가 얼마나 margin violation을 허용받았는지에 대한 정도이고, slack variable이라 한다.

• Quadratic Programming

• hard, soft margin problem은 둘 다 QP problem이다. QP problem 형태의 문제는 그냥 QP solver에 넣으면 된다.

• The Dual Problem

• 주어진 primal problem(원래 problem, 여기서는 QP problem에 해당)이 어떤 조건을 만족하면 dual problem으로 새로 정의하여 풀 수도 있다. dual problem의 경우 solution에 lower bound를 부여한다(lower bound라는게???) .

• dual problem은 primal 보다 더 빠르게 풀 수 있고, kernel trick도 적용할 수 있다.

• Kernalized SVM

• 어떤 polynomial mapping pi(x) 에 대해, kernel pi(x)'pi(x)를 계산하지 않고 그냥 원래 식을 적은 연산량으로 계산하는 것을 말한다.

• Mercer's Theorem: pi(a)'pi(b)와 같은 함수 K(a,b)가 어떤 조건(symmetric 이라든지, 연속이라든지)을 만족하면 K에 대한 mapping pi(x)가 존재한다는 것. 그래서 사실 pi(x)를 알지 못하거나 무한대의 차원에 대한 mapping이라 계산이 불가능해도 그냥 K를 그대로 쓰면 mapping한 효과를 낼 수 있다.

• prediction 시 , dual에서 구한 parameter를 가지고 primal problem에서 추정해야 하는 w나 b등을 다시 계산해야 하는데, mapping pi(x)가 무한대의 차원을 가지고 있다면 w를 구할 수 없다(w * pi(x)이므로 둘다 같은 차원이어야 함). 하지만 kernel trick을 사용하면 w를 직접 구하지 않고도 prediction을 수행할 수 있다.

• dual problem에서 kernel trick을 써서 prediction을 수행하면… 수식이 아주 복잡해진다.

• Online SVMs

• Gradient Descent를 쓰기 때문에 QP를 푸는 것보다 느리다.

• cost function 내에 Hinge Loss function ( max (0, 1-t) )를 사용한다.

• hinge loss를 쓰면 margin 바깥에 위치하는 new instances에 대해서는 cost에 아예 반영하지 않는다(positively 반영하지도 않는다).

• hinge loss를 쓸 경우 미분이 안되는데, Lasso Regression 처럼 적당한 subderivative(0과 -1 사이의 어떤 값…)을 주면 된다.

6. Decision Trees

• 데이터를 준비하고 decision tree를 만들면 된다(… scikit-learn의 함수에 그냥 넣으면 됨)

• scikit-learn에서는 Classification and Regression Tree(CART) 알고리즘을 사용한다. CART의 경우 각 node가 두 개의 child nodes만을 가질 수 있다.

• fitting 된 tree중 트레이닝 어떤 class를 purely 구분할 수 있는 node도 있고, 최적의 decision threshold를 찾았지만 pure는 아닌(impure) node도 있다.

• Decision tree는 White box model에 속한다. (white box model: model을 보면 어떻게 동작하는지 직관적으로 알 수 있음)

• black box model에는 DNN이나 random forest 등이 있다.

• Decision Tree로 class probability를 계산할 수도 있다.

• The CART Training Algorithm

• 아래 cost function을 최소화하는 single feature k와 k의 threshold를 고르면 된다.

• CART cost function for classification: J(k,tk) = leftratio * leftimpurity + rightratio * right_impurity

  • (cost function은 averaged impurity라고 보면 된다)

• CART algorithm은 greedy algorithm이다.(그때 그때 하나의 k만 보고 locally optimal threshold를 정하기 때문)

• 어차피 greedy로 안하면 NP-Complete 문제라서 풀기도 어렵다(NP-complete은 따로 다시 복습…)

• Computational Complexity

• prediction의 경우: O(log2(m)), m: instances의 수

• training의 경우: O(n x mlog2(m)), n: feature 차원. training은 느리기 때문에 presorting을 하기도 한다. (하지만 이것도 느리다)

• Gini Impurity or Entropy?

• gini(지니 계수의 그 지니) impurity 대신 entropy를 쓰기도 한다.

• gini를 쓰면 'class들이 안 섞이는 것'에 집중하고, entropy를 쓰면 balanced tree를 만드는데 집중한다(뭐가 balanced인걸까).

• Regularization Hyperparameters

• Decision tree는 feature scaling을 하지 않아도 된다. 하지만 이렇게 하면 더욱 데이터 의존적이 되고 overfitting이 일어날 가능성이 크다.

• Decision tree는 parameter가 없기 때문에, decision tree에 대한 regularization은 tree의 depth를 제한하는 것이 된다.

• 다른 방법으로는 일단 학습된 tree에 대해 pruning을 실시하는 것이다. 이건 성능이 더 좋아지진 않는데 대신 필요없는 node를 없애서 의미 없는 예측을 피하기 위함이다.

• Regression

• 이 경우 CART cost function은 J(k,tk) = leftratio * leftMSE + rightratio * right_MSE 가 된다.

• Instability

• Decision tree는 orthogonal boundary만을 가지기 때문에 data의 rotation에 sensitive하다.

• PCA 등을 통해 orientation을 하면 해결할 수 있다.

• training data의 작은 variation에 취약하다.

• decision boundary와 가장 가까운 instance가 다른 값을 가지기만 해도 decision boundary가 크게 변한다.

7. Ensemble Learning and Random Forests

• 집단 지성.. 뭐 그런 motivation이 있는 것 같다.

• Voting Classifiers

• 타입이 다른 여러 classifier의 binary prediction에 대해 다수인 class로 정하는 것 (voting)

• 각 classifier는 weak learner에 해당됨(무작위보다는 좋은 classifier)

• hard voting 같은게 잘된다고…? 근데 잘됨. 왜 잘되나?

• The law of large numbers

  • 가정: voting에 쓰이는 classifier들이 각자 다른 데이터로 학습되었고(independent) uncorrelated 이라면…
  • 샘플 수가 많으면 많을 수록 이상적인 예측을 잘함. (아니 뭐 꼭 예측 뿐만이 아니라 그냥 시행 횟수가 많으면 뭐든지 잘됨)
  • (이런 대강의 설명 말고… 실제 law of large numbers는 더 진지한 것 같은데 너무 내용이 많으니 일단 패스)

• 하지만 보통 가정을 충족하는 상황이 없기 때문에 완전 잘되는 건 아님.

  • 그나마 아주 다른 타입의 classifier를 쓰면 각자 다른 타입의 error를 만들기 때문에 independency를 흉내낼 수 있고 accuracy도 높음.

• Bagging and Pasting

• bagging: 복원 추출, pasting: 비복원 추출

• bagging의 뜻: bootstrap aggregating

• bootstrap은 또 뭔가? bootstrapping

  • sample set에 대해 또 sampling을 실시하여 만든 resample set들이 마치 모집단에서 나온 여러 sample set인 것처럼… 다루는? 기법인듯 잘은 자세히 봐야 함

• 하여튼 이 방법은 bagging(or pasting)된 여러 resampled set에 대해 같은 타입의 predictor를 여러개 만들어 voting(맞겠지?) 하는 것임.

• 각 predictor는 highly biased 이지만 aggregation을 수행하면 variance, bias 둘 다 낮아짐(이거 완전 공짜 아니냐?)

• Bagging and Pasting in Scikit-Learn

• decision tree로 bagging ensemble을 해보자. (ensemble이 뭔지 아직 배우진 않았는데)

• 위에서는 bias, variance 둘 다 낮아진다고 했지만… bagging이 완료되면 전체 bias는 이전과 비슷하지만(decision tree 특징인가) ensemble의 variance는 낮아짐.

• bagging이 pasting보다 조금 더 bias가 높긴 하지만 predictor들이 서로 uncorrelated임.

  • 이는 복원추출이라 resampled set 간 dependency가 없기 때문(다른 셋에 어떤 instance가 있건 없건 상관이 없기 때문)

• Out-of-bag Evaluation

• 각 predictor들은 resampled set을 쓰기 때문에 각자마다 사용되지 않은 set이 있음(각자 다름)

• 각자 다른 resampled set에 대해 학습되기 때문에, cross validation을 하지 않아도 됨.

• Random Patches and Random Subspaces

• instance를 sampling 하는 방법도 있지만, feature의 일부를 sampling 하여 sub-feature를 가지게 하는 방법도 있음

• random patches method: instances와 features 둘 다를 sampling 하는 것(X에 대해 patch를 뜯는 것 같아 patch라고 하는 듯)

• feature를 sampling하는 것은 predictor diversity를 더 높이기 때문에, predictor 각각의 bias를 더 높이고 variance를 더 낮추는 tradeoff가 있음(어차피 ensemble 하면 다 괜찮아지는 거 아닌가? 아닌가?)

• Random Forests

• decision trees의 bagging ensemble임.

• random sub-feature 에 대해 각각의 decision tree가 다르게 학습되기 때문에, 각 tree의 best feature도 다름.

• Extra-Trees

• best feature의 threshold를 random으로 정하는 것(아니 threshold까지 random이면 그게 무슨 의미가 있어…)

• 이런것까지 randomize 하기 때문에 extremely randomized trees ensemble이라고 함.

• Feature Importance

• 학습된 random forest를 보면 중요한 feature가 뭔지 알 수 있음.

• 특정 feature가 각 tree의 root node에 가까우면, 그 feature는 중요한 것임. (반대로 leaf node에 가까우면 안 중요)

• Boosting ( hypothesis boosting )

• weak learner를 combination 하는 것

• Adaboost

• weak learner를 여러개 준비하고, learning1 -> prediction1 -> boosting -> learning2 -> pre…. 를 수행하는 것

• learning{i}: i번째 learner를 준비된 데이터를 가지고 학습 시키는 것

• prediction{i}: 준비된 데이터에 대해 i번째 learner를 가지고 predition 하는 것

• boosting: learner가 잘못 예측한 instance에 대해 weight를 더 주는 것 (즉 데이터 내의 instance 별 weight를 변화)

• 모든 learner의 학습이 끝나고 모든 learner를 가지고 prediction 할 때는 각 predictor 별 weight(따로 계산됨)를 가지고 수행

• decision stump: depth가 1인 decision tree(최소한의 decision tree. 이름이 귀엽다)

• adaboost도 overfitting이 되기 때문에 estimator(여기서는 왜 또 estimator라고 하는 걸까 헷갈리게…)의 갯수를 제한하는 것으로 regularization을 수행

• SAMME

• multiclass version of AdaBoost

• Gradient Boosting

• boosting을 하긴 하는데 데이터에 그대로 하는게 아니라 residual 자체를 데이터로 간주하여(틀린 정도만 남겨서) 다음 learning에 사용

• 이렇게 하면 hypothesis function을 만들 때 그냥 각 learner의 h(x)를 더하면 됨

  • h(x) = h1(x) + h2(x) + h3(x)

• Stacking

• 1단계: training set의 subset을 준비하여 predictor 여러개를 learning

• 2단계: 위 subset의 exclusive subset을 가지고 학습된 predictors에 넣고, 그렇게 해서 얻어낸 여러개의 prediction에 대해 blending predictor를 학습함(마치 DNN 같다)

• layer가 깊다면 이걸 반복…

• 엥 이거 완전 DNN의 RBM pretraining 아니냐? (하지만 subset을 사용하고 학습 방법이 좀 다르긴 함 어쨌든)

8. Dimensionality Reduction

• The Curse of Dimensionality

• hypercube의 차원이 높아질수록 hypercube 내의 무작위의 점은 임의의 border(면)와 매우 가깝게 위치한다.

• 즉 feature가 고차원이 될 수록 고차원 공간 내에 고르게 퍼져 있지 않고 엄청나게 쏠려 있고 sparse라는 것

• 쓸모없는 차원이 너무 많다.

• Main Approaches for Dimensionality Reduction

• Projection

  • projection으로 안되는 경우가 있다.

• Manifold Learning

  • manifold: 실제 데이터는 낮은 차원의 subspace에 있는데 이게 고차원의 space에 구불구불하게 있는 경우 그 subspace를 manifold라 함.
  • '실제로는 낮은 subspace에 있을 것이다'라는 가정이 깔려 있음.
  • (암묵적으로) 딱 보면 딱 manifold일 것 같다는 가정도 있음(하지만 이건 언제나 맞는 말은 아님).

• PCA

• Principle Components

  • PC의 방향은 데이터의 변화에 sensitive임. 대신 축 자체는 insensitive.
  • SVD로 찾아낼 수 있음.
  • PCA는 데이터셋이 origin-centerized라고 가정하기 때문에 적절한 전처리가 필요

• Explained Variance Ratio

  • 각 PC 마다 Variance Ratio를 가짐. (eigenvalue에 해당하는 그것)

• Choosing the Right Number of Dimensions

  • 적절히 고르면 됨. 예시에서는 Explained Variance(k개까지의 PC의 Variance의 합이 전체 Variance에서 차지하는 비율)가 0.95일 때의 PC 갯수를 적절하다고 봤음.

• PCA for Compression

  • MNIST의 경우 PCA를 통해 원래 데이터셋의 20%의 사이즈만 가지고도 95%의 variance를 확보할 수 있었음.

• Incremental PCA

  • mini-batch를 가지고 찾아냄. numpy의 경우 memmap을 사용하면 아주 큰 사이즈의 데이터도 incrementally 가능

• Randomzied PCA

  • d개의 PC를 랜덤하게 찾음(???? 이래도 됨?)

• Selecting a Kernel and Tuning Hyperparameters

  • 데이터 분포를 아예 못 보거나 관련 지식이 아예 없을 경우
  • 이 부분은 문장 호흡이 너무 길어서 해석이 어려움. 한 30분 걸릴 것 같음 ㅠㅠ 스킵

• Locally Linear Embedding(LLE)

• 데이터셋 내의 특정 instance xi에 대해 k개의 이웃 xj가 xi를 linear combination으로 가장 잘 나타낼 수 있는 wij를 추정.

• What = argminW(sum(|| xi - sum(wij * x_j) ||^2)) (constraint 생략)

• 근데 i = j 일 경우의 w_ij를 그냥 1로 주고 아닌 것들을 다 0으로 주면 되는데, 이게 도대체 식이 왜 이렇지? 일단 머리 싸매고 있을 수 없으니 skip

• Other Dimensionality Reduction Techniques

• Multidimentional Scaing (MDS): 차원축소를 하긴 하는데 instance 간의 거리를 유지(???? 무슨)

• Isomap: 읽어도 무슨 말인지 모름

• t-SNE: 비슷한 instance는 가깝게, 다른 것끼리는 멀게

• LDA: 생략

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와는 매우 달라질 수 있다.

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를 쓰는 것이 현실적인 방법이다.

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!