180828 CTC 책 노트

배경지식

• (https://en.wikipedia.org/wiki/Connectionism)
• (https://en.wikipedia.org/wiki/Connectionism#Connectionismvs.computationalism_debate)
• (http://www.aistudy.com/neural/connectionism.htm)

1. Introduction

• 음성인식에는 alignment가 필요한데 RNN은 그걸 못하기 때문에 HMM의 도움을 받았다

2. Supervised Sequence Labeling

• 강화학습(reinforcement learning)과 supervised learning의 차이점: 강화학습 시에는 scalar reward만 주어진다(정말?)

2.2.2 Training Probabilistic Classifiers

• predictive distribution은 구하기 어렵다 (bishop책 3장을 보면 온통 라이너 전개와 라플라스 근사로 도배되어 있다)
• 그래서 그냥 MAP을 구하는 것으로 근사한다.
• MAP의 posterior 중 prior는 weight decay이기도 하다. 'Occam's razor'에 따라 큰 weight에 대해 페널티를 준다(정말로 Occam's razor 때문에 그렇다고?)

2.2.3 Generative and Discriminative Methods

• p(C|x)(posterior)를 한 방에 구하는게 discriminative 방식이다.
• (bishop책을 보면 discriminative를 한 방에 구하는 것보다는 likelihood와 prior를 나눠서 구하는게 더 유용하다고는 한다)
• generative 방식은 원래 데이터의 분포인 prior를 구하는 것이다.
• (근데 어차피 음성인식 얘기를 하고 있으므로 원래 데이터의 분포 같은걸 알아낼 필요도 없고), 성능 상으로도 discriminative가 더 좋다.

2.3 Sequence Labelling

• sequence가 iid라고 가정한다.
• sequence labelling task는 세 가지로 나뉜다.
• Temporal Classification: weakly target(예를 들어 문장)만 가지고 학습해야 하는 것. 가장 어렵다
• Segment Classification: segment 단위로 잘 정리된 label로 학습하는 것
• Sequence Classification: label이 한 덩어리인 것(예를 들어 A, B이런것들)

2.3.2 Segment Classification

• 자연어처리나 생물정보학에서는 input들이 discrete해서 쉽게 쪼갤 수 있다(can be trivially segmented)
• 가장 쉽게 생각해볼 수 있는 measure는 segment error rate인데, 걍 잘못 맞춘 segment들의 비율을 구하는 것이다.
• segment error rate 구하는 과정엔 두 sequence 간의 hamming distance를 구하게 된다.
  • (이 과정에서 두 시퀀스의 길이가 같으니까 substitution 에러를 고려할 것 같은데, 어떻게 하는지는 잘 모름)

2.3.3 Temporal Classification

• 여기서는 segment error rate를 쓸 수 없으므로 label error rate를 써야 한다.
• label error rate = 평균(edit distance): edit distance는 substitution, deletion, insertion으로 이루어져 있다.
• (substitution, deletion, insertion을 구하는 과정은 CMU 2013년도 봄학기 음성인식 강의 자료 4장에 나와 있다)
• edit distance 이외에 transposition이나 연산의 상대적 중요도(relative importance of the operator)를 고려할 수도 있다.
• operator라는 건 (substitution, deletion, insertion)을 말하는 것 같다. 잘은 모르겠다.

3. Neural Networks

3.1.1 Forward Pass

• activation function은 대개 무한대의 range를 유한하게 만들어주기 때문에, squashing function이라 부르기도 한다.

3.2.4 Bidirectional Networks

3.2.4.1 Causal Tasks

• bidirectional networks는 causality를 어긴다. (네비게이션이나 주가 예측 등에 쓸 수 없다)
• 하지만 솔직히 causality를 위반해도 되는 task들이 있다. (단백질 구조 분석이라든지…)

3.2.5 Sequential Jacobian

• 어떤 network를 학습했다고 치자. 그때의 Jacobian은 input에 대한 output의 sensitivity라 할 수 있다. Jacobian은 output과 별로 관련이 없는 input을 알아내는데 쓸 수 있다.
• (neural network는 비선형 모델이기 때문에 어떤 input의 변화에 대한 output의 변화가 Jacobian을 통해 근사적으로만 계산될 수 있다)(bishop책 5.3.4)
• Jacobian을 통해 구한 output derivative값이 크다고 해서 민감하다는 것은 아니다. output derivative끼리 상대적으로 고려했을 때 얼마나 변했는지가 sensitivity의 척도가 된다.
• 근데 또 그렇다고 해서 sensitivity가 importance를 의미하지는 않는다;;; (가령, 이미지를 letter box로 만들었을 때 까만 패딩 부분에 대해서는 sensitivity가 높지만 아무 정보가 없기 때문에 중요하진 않다고 할 수 있다)
• Jacobian은 원래 2차원인데, RNN의 경우는 input이 sequence이므로 Jacobian에 해당하는 것은 4차원이 된다. 이것을 Sequential Jacobian이라 한다.

7. Connectionist Temporal Classification

• CTC라는 이름은 그냥 지은게 아니다.

7.1 Background

• 94년에 Bourlard와 Morgan은 connectionist 방식으로는 ASR(연속음성인식)을 다룰 수 없다고 했다.
• segmentation이 모호한 경우에는 target function을 정의할 수 없기 때문
• 하지만 CTC를 사용하면 Temporal Classification에 대한 target function을 정의할 수 있다.

7.2 From Outputs to Labellings

7.2.1 Role of the Blank Labels

• 초기 CTC는 blank label이 없어서 같은 label이 연속되는 경우를 학습할 수 없었다.

7.2.2 Bidirectional and Unidirectional Networks

• CTC를 쓰면 bidirectional RNN을 쓰지 않아도 성능이 덜 떨어진다.

7.3 Forward-Backward Algorithm

• HMM의 그것과 비슷하다.
• unidirectional과 bidirectional의 output을 비교해보면, unidirectional의 output이 약간 더 delay되어 있다.
• (bidirectional은 causality를 어기기 때문에 input이 다 들어오기도 전에 맞추는 것 처럼 나타난다) 
• HMM의 Alpha에 해당하는 것을 계산하한다. U 축에서 이전 label이 같은 경우, stride가 2인 connection은 없다.
• (예시로 보여준 figure에서는 그 부분이 없어 직접 그렸다)

7.3.1 Log Scale

• underflow를 방지하고자 Log Scale에서 연산을 수행한다.
• 원래 덧셈이었던 연산은 Log Scale을 빠져나왔다가 다시 들어가야 하는 문제는 아래와 같이 해결할 수 있다.
• ln(a + b) = ln(a) + ln(1 + exp(ln(b) - ln(a)))
• log scale. always.

7.4 Loss Function

• pi: target 문장
• z: pi를 u domain에서 나타낸 sequence (u domain이 좀 더 길기 때문에 가능한 sequence는 여러개이다)
• z': expanded z (z의 앞뒤와 label 간 blank를 넣은 sequence. len(z) = U 라면 len(z') = 1 + 2U)
• x: input sequence (MFCC sequence 같은 것들. t domain)
• Loss(x,z) = -ln(sum(alpha(t,u) * beta(t,u)) for u in range(z'))
• 특정 X(t,u)를 가지는 모든 path에 대해 marginalization 한 것이라 보면 된다.
• (u에 대해서만 sum했는데 Loss에서 t도 없어지는 것은 u와 t가 독립적인 index가 아니기 때문에 u에 대해 더하면 u에 해당하는 t도 자동으로 고려되어서 그런 것 같다. 잘은 모르겠다)
• 특정 X(t,u)에 대한 alpha(t,u) * beta(t,u)를 나타내면 아래와 같다. (eq 7.25)

7.4.1 Loss Gradient

• u: z에서 label 'k'가 나타난 위치 (eq 7.31)
• 다행히도 Loss Gradient는 alpha, beta를 이용해 나타낼 수 있다.

7.5 Decoding

• CTC라고 해서 decoding 과정에 뭐가 딱히 있지는 않다. (intractable)

7.5.1 Best Path Decoding

• 각 path 중 가장 확률이 높은 path를 고르는 것이다.
• 계산하기는 쉽지만 best path가 최적의 답은 아니다.
• blank를 '-'라 표기하고 어느 문자 A가 있다고 하자.
• 이 때 p(--) > p(AA) 인 경우가 있는데 사실 pi(char. domain)에서 보면 p(-)와 p(A)를 비교해야 하는 문제가 된다.
• best path 방식으로 해버리면 p(--) < p(AA)이기 때문에 '-'가 선택되는데, p(-) > p(A) = p(AA) + p(A-) + p(-A) 이면 사실 p(A)를 만드는 path들이 선택되어야 한다.

7.5.2 Prefix Search Decoding

• (여기부터는 솔직히 이해가 잘 안된다)
• 이 방식은 best alpha를 보면서 decoding을 진행한다. t domain에서 한 칸씩 진행하면서 best children을 선택한다.
• 시간이 아주 많아서 모든 children의 chlidren의 children을 다 볼 수 있다면 좋겠지만… 불가능하기 때문에 heuristic을 쓴다(예를 들어 beam width를 정해 쳐낸다든지…?). heuristic으로도 잘 된다.
• fig 7.6

7.5.3 Constrained Decoding

• 미리 준비한 Grammar를 가지고 Decoding에 사용할 수도 있다.

• 이 경우 Grammar에 없는 단어들을 쳐낼 수 있다.

• Grammar를 쓰면 CTC의 기본 가정을 위배한다(input sequence가 iid).

• l: 위에서 언급한 z와 같음 (u domain에서 나타낸 문장)

• l': best l

• G: Grammar

• l' = argmax( p(l|x, G) )

• 여기서 근사적으로 p(l|x, G) = p(l|x)p(l|G) / p(l) 이다.

• (x와 G가 사실 아예 독립은 아니다. 왜냐면 화자는 자신이 알고 있는 문법에 맞춰 문장을 말했을 것이므로)

• 하지만 문법이라는게 사실 어떤 개인에게 속한다기 보다는 Global한 것이기 때문에, 독립이라고 봐도 된다.

• (그리고 외부 데이터를 통해 만든 Grammar를 쓰면 독립이라고 봐도 된다)

• 여기서 가능한 l의 갯수가 유한하기 때문에, p(x)와 p(G)에 equal probability를 적용해도 improper prior가 되지 않는다.

  • (sum 했을 때 1이 아니게 될 수도 있다든가 하는 위험이 없다) improper prior

7.5.3.1 CTC Token Passing Algorithm

• HMM의 token passing과 비슷하다.
• HMM의 token passing은 HTK book의 1.6 Continuous Speech Recognition 에 자세히 나와 있지만, 솔직히 만들어보지 않고는 알 수 없는 수준이다.
• Kaldi 소스코드에도 token passing을 볼 수 있는데(lattice-faster-decoder.cc), 사용 목적의 프로그램 소스코드에서 한 6 단계 정도 아래로 내려가야(…) 볼 수 있기 때문에 코드만 봐서도 이해하기 어렵다. 대충 그림으로 나타내면 아래와 같다.

7.5.3.2 Computional Complexity

• bigram을 쓰는 CTC token passing은 최악의 경우 O(TW^2)이지만, token을 매번 sorting 한다면 O(TWlogW)가 된다.

7.7 Discussion

• HMM과 LSTM-CTC를 비교해보자. (저자분께서 작정한 것 같다)
• HMM은 generative이고, LSTM-CTC는 discriminative이다. discriminative method가 더 성능이 좋다. 그 이유는 원래 데이터 분포 같은 것보다 classification에만 집중하기 때문이다.
• LSTM-CTC가 HMM보다 훨씬 flexible이다.
• standard HMM의 state들은 discrete이고 single value를 가진다. 반면 RNN의 state는 vector이다. RNN이 훨씬 더 복잡한 정보를 표현할 수 있다.
• (HMM variant 같은걸로 되지 않나…)
• HMM은 continuous input sequence를 hidden states로 나타내는데 한계가 있다(예를 들어 필기체 인식).
• state를 많이 늘리면 그만큼 각 state의 확률이 exponentially 줄어든다. (음… 반만 이해된다)
• 하지만 CTC는 state를 더 늘릴 필요가 없다. continuous 값을 가지는 vector니까
• HMM은 현재 state에 대한 observation만 다루기 때문에(context dependency를 반영할 수 없기 때문에) triphone 같은 것을 사용하는 짓을 한다. triphone 같은걸 쓰면 파라미터가 exponentially 늘어난다. 그 수많은 파라미터를 학습시키려면 수 많은 데이터가 필요하다. (이것 역시 반만 이해된다)