CS224N - 03.Word Window Classification, Neural Networks, and Matrix Calculus

CS224N의 3주차 강의, Word Window Classification, Neural Networks, and Matrix Calculus을 보고 정리한 글입니다.
1. Classification setup and notation
2. Neural Network Classifiers
3. Named Entity Recognition (NER)
4. Binary true vs. corrupted word window classification
5. Matrix Calculus

Classification setup and notation

일반적으로 샘플들로 구성된 Training dataset을 갖고 있음.
- x_i
  - d차원의 Inputs!
  - ex. words, sentences, documents 등
- y_i
  - 예측하려고 하는 Label (여러 클래스들 중 하나의 값)
  - classes: sentiment, named entities, buy/sell decision

고전적인 기계학습 및 통계 알고리즘

결정경계(Decision Bounddary)를 결정하기 위해 softmax/logistic regression weights W를 훈련
$W \in \mathbb{R}^{C \times d}$
방법: x에 대해 각 클래스의 확률을 예측(Predict)
$p(y|x) = \frac{exp(W_y \cdot x)}{\sum_{c=1}^C exp(W_c \cdot x)}$
- Predict Procedure: 2 steps
  - step1: W의 y번째 row와 x를 곱한다.
    - c=1,…,C 이고 모든 f_c를 계산
    - f_y: 일종의 score! (그 예시가 특정 클래스에 속할 확률이 얼마나 되며, 여기에 softmax를 취함)
  - step2: Softmax function을 적용한다.
    $p(y|x) = \frac{exp(f_y)}{\sum_{c=1}^C exp(f_c)} = softmax(f_y)$
학습방향
- class y를 옳게 분류할 확률을 Maximize하기
  = 그 class의 negative log probability를 Minimize하기
  $-log p(y|x) = -log(\frac{exp(f_y)}{\sum_{c=1}^C exp(f_c)})$

여기서 잠깐, ‘Cross entropy’ loss/error란?
- ‘cross entropy’의 개념은 정보이론으로부터 나옴
- p를 True probability distribution, q를 computed model probability라고 하면, cross entropy는 다음과 같이 정의돌 수 있음.
  $H(p,q) = -\sum_{c=1}^C p(c) log q(c)$
- 이 때, 옳은 class에만 1을 부여한다면, p의 ground truth probability는 다음과 같이 표현해볼 수 있을 것
  p = [0, 0, …, 0, 1, 0, 0, …, 0]
  -> one-hot p 때문에, cross entropy에서 남는 항은 true class의 negative log probabilty 뿐이다!
- 위 사실을 ‘Full’ dataset에 대해 적용해보면, Information Theory를 공부하는 사람들이 종종 Cross entropy rate라고도 부르기도 하는, Cross entropy loss function은 다음과 같이 정의할 수 있다.
  $J(\theta) = \frac{1}{N} \sum_{i=1}^N -log(\frac{e^{f_{y_i}}}{\sum_{c=1}^C e^{f_c}})$
- 아래의 식을
  $f_y = f_y(x)= W_y \cdot x = \sum_{j=1}^d W_{yj}x_j$
  아래와 같은 matrix form으로 더 간단하게 표기할 수 있음.
  $f=Wx$

Optimization? (역시 Traditional method 선상에서의 사고)
- W의 column들로 구성되어 있는, Θ 파라미터 학습
  (각 클래스 별로, d-dim의 input vector와 곱해져서(dot-product) class를 결정하게 만드는 d-dim의 weight vector들이 존재하고 이들을 학습)
- 결국, $\bigtriangledown _\theta J(\theta)$ 을 통해 Decision boundary를 업데이트하게 될 것

Neural Network Classifiers

그런데, 위의 softmax 혹은 logistic regression 만을 사용한 고전적인 접근 방법은 그닥 powerful 하지 않음.
- 고전적인 접근 방법의 Decision boundary는 Linear하기 때문.
- 필연적으로 데이터를 잘 classify 할 수 없는 경우들이 생긴다.
  - 당연히 좀 더 Complex한 모델이 필요하게 되며, linear한 decision boundary로는 어떤 식으로든 개선이 불가능함.
NN이 해결책이 될 수 있다!
- More complex functions + Nonlinear Decision boundary!
NLP에서의 NN?
좀 더 advanced된 classification 결과를 얻기 위해서, 해볼 수 있는 일이 두 가지가 있음.
- 1. Word Vector도 학습을 한다!
    - 생각해보면, 고전적 방법에서는 (물론 Non-linear한 학습을 하지 못하는 것도 있지만) Weigth Matrix W만을 학습
    - 반면, NLP에서는 Weight Matrix와 함께, wort vector x까지 한 번에 학습을 한다!
      (= conventional parameter 뿐만 아니라 word representation 또한 학습)
    - 기존에 학습해야 할 파라미터의 개수가 Cd개 였다면, NLP에서는 Cd+Vd개!
- 1. Layer를 더 깊게 쌓아볼 수 있다. (Deeper MLP)
    - NN에서는 깊게 Layer들을 쌓으면서 효율적인 학습이 가능한 반면, 기존의 linear function들은, linear function에 아무리 linear function을 더하고 더해도, Rotate & Stretch 일 뿐, non-linearity를 학습할 수 없음.

Named Entity Recognition (NER)

‘텍스트 내에서 이름들을 찾고, 이 이름들을 분류해보고 싶다’ (find & classify)
다양한 목적들이 있을 수 있음.
- Document들 내에서 특정 Entities의 언급을 추적한다거나
- 질답 문제에서, 질문에 대한 답은 보통 named-entities
- 얻고 싶은 정보들 중의 많은 부분은 named entites간의 관계에 대한 것인 경우도 많고
- 똑같은 테크닉이 slot-filling classification 같은 것으로도 확장될 수 있음.
- 때때로는, Knowledge Base 문제의 Named Entity Linking/Canonicalization 문제로 확장되기도 함.
다음과 같은 텍스트가 있다고 하자.
- NER은 다음과 같이 분류를 한다고 함.
근데 NER은 정말 어려운 문제임
- 왜냐하면 Entity를 Boundary를 정한다는 것이 상당히 어렵기 때문.
- 예를 들어
```
First National Bank Donates 2 Vans To Future School Of Fort Smith
```
  라는 글귀.
  -> 인간인 나도 첫번째 entity가 ‘First National Bank’인지 ‘Nation Bank’인지 알기 어려움.

Binary true vs. corrupted word window classification

Binary word window classification

word classification은 보통 context 내에서 이루어지지, single word만 갖고 이루어지는 경우는 상당히 드물다.
하지만, context 상에도 여러 문제가 생길 수 있음.
- auto-antonyms
  - ex. To sanction: To permit, To punish라는 뜻 둘다를 갖고 있다.
  - ex. To seed: To place seeds, To remove seeds라는 뜻 둘 다를 갖고 있다.

Window classification

아이디어: 단어를 그 근처의 단어들의 context window 내에서 classify하라.
- ex) Person, Location, Organization, None
가장 단순한 방법 중의 하나는 -> 한 window 내의 단어 벡터들을 average & 그 average vector에 따라 classify
-> 문제는 이렇게 average를 해버리면 Position Information을 잃는다.

Window Classification: Softmax

‘한 window 내에서 word vector와 그 neighbor들을 concatenate한 후 softmax classifier를 훈련하여 분류를 해보자!’
예를 들어

여기에, 앞에서 했던대로 그대로 Softmax를 적용
Interest
X_Paris가 ‘Location’으로 분류될 수 있는지를 알고 싶다.
Word2vec과 유사하게 corpus 내의 모든 position들을 훑을 것.
실제 NER Location을 갖는 위치가 center 위치일 때만이 ‘True’ Position으로서 높은 점수를 얻게 될 것
- 예: ‘Not all museums in Paris are amazing/’ 이라는 문장
  - 오직 ‘museums in Paris are amazing’ 이라는 하나의 window만이 Paris가 center에 있기 때문에 ‘True’ window가 될 것.
  - 그 외의, 예를 들어 ‘Not all museums in Pares’와 같은 window들은 모두 ‘Corrupt’ window가 될 것.
이제 score를 얻기 위해 3 layer의 NN을 적용
- 두번째 Layer가 Non-linear Interaction을 학습한다!
이 Process들을 그림으로 표현하면 다음과 같음

The max-margin loss

True window의 score는 크게, corrupt window의 socre는 작게 학습하고 싶다!
- s=score(museums in Paris are amazing)
- s_c=score(Not all museums in Paris)
다음을 Minimize하라!
$J = max(0, 1-s+s_c)$

Matrix Calculus

앞서 우리의 모델로 돌아오면
구하고 싶은 것은 단연
$\frac{\partial s}{\partial W} \ \& \frac{\partial s}{\partial \mathbf{b}}$
저 둘을 구함에 있어서, 빨간색 네모 상자 부분은 겹친다!

이 겹치는 부분은 둘을 계산하는 데에 있어서 Re-Use할 수 있고, 이 부분을 Local Error Signal (δ) 이라고 함.
Chain Rule 및 미분 성질을 이용하면 다음과 같이 정리될 수 있다.

References

CS224N: Word Window Classification, Neural Networks, and Matrix Calculus

Classification setup and notation

고전적인 기계학습 및 통계 알고리즘

Neural Network Classifiers

Named Entity Recognition (NER)

Binary true vs. corrupted word window classification

Binary word window classification

Window classification

Window Classification: Softmax

The max-margin loss

Matrix Calculus

References

Share this post