2018년 9월 12일 수요일

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가 일치해야 한다)

2018년 9월 11일 화요일

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가 생겨버리면 어떡하지?)

2018년 9월 9일 일요일

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