[Stanford 강의] Assignment2

 

Stanford대학교의 nlp강의 cs224n수업의 2주차에 해당하는 과제이다.

 

과제 문서는 이 링크에서 확인할 수 있다.

https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1246/assignments/a2.pdf

 

이번 과제는 word2vec의 수학적 원리를 알아보고, neural dependency parser를 만들어보는, 총 두 개의 큰 주제로 나눠져 있다.

아래의 내 답은 틀릴 수 있다는 것을 감안해야한다.

 

---

1. Understanding word2vec

skip-gram에 대해 다시 기억을 되짚어 보면,

중심단어가 주어졌을 때 주변단어가 올 확률을 높이는 방식으로 학습했다는 것을 기억할 수 있다.

다만 실제로는 확률을 최대화 하는 대신 손실함수를 최소화하는 방식으로 학습한다.

 

중심단어 $c$와 주변단어 $o$에 대해 확률은 아래처럼 정의했었다.

$u$는 주변단어일 때의 단어벡터, $v$는 중심단어일 때의 단어벡터를 나타낸다.

 

$y$는 중심단어 $c$가 주어졌을 때, 어떤 주변단어 $o$에 대해 실제로 주변에 있는지를 나타내는 벡터이다.

원핫 방식으로, 해당 $o$단어의 인덱스만 1이 되고 나머지는 0이다.

$\hat{y}$은 중심단어가 $c$일 때, 주변단어가 $o$일 확률을 나타낸다. 즉 위의 확률식의 결과값이다.

 

이 두 값에 대해 cross entropy를 적용해 손실함수를 계산한다. 원래 식은 아래와 같지만,

우리의 경우 $y$가 원핫이기 때문에 $-log \hat{y}_o$와 같아진다.

즉 특정 중심단어,주변단어 쌍에 대해 아래 식처럼 간단히 만들 수 있다.

 

문제 1-a. cross entropy loss가 위의 naive-softmax loss와 같다는 것을 증명하시오.

방금 위에서 설명한 그대로이다.

문제의 요구대로 한줄의 식으로 간단히 답을 작성하면,

 

문제 1-b-i. $J$를 $v_c$에 대해 미분해라.

먼저 기본 식을 계산이 쉽도록 변형한다.

이후 $v_c$에 대해 미분한다.

$U$는 각 단어들의 벡터의 행렬이므로 아래처럼 나타낼 수 있다.

 

1-b-ii. 언제 이 미분값이 0이 되는가?

이 미분값이 0이 되게 하는 조건은 '$u_o$와 전체 단어를 확률로 가중 평균낸 값과 같을 때' 이다.

 

1-b-iii. 이 미분값이 $v_c$에서 빼질 때, 각 두 항이 어떻게 학습을 시키는지 해석해라.

이 값을 $v_c$에서 뺀다면 $v_c$는 정답인 $u_o$쪽으로 이동하고, 다른 벡터들의 값은 잘못 판단된 정도(확률)가 강할수록 $v_c$에서 더 강하게 빼지게 된다.

즉 정답 단어 벡터와 중심 단어 벡터가 가까워지게 하는것이다.

 

1-c. L2정규화를 할 경우 어떤 경우에 유용한 정보가 사라지는지, 어떤 경우에 사라지지 않는지 서술하시오.

구(phrase)가 긍정적인지 부정적인지 판단하는 방법을 주고, $u_x = \alpha u_y$인 경우에 대해 설명하라고 추가 설명이 주어진다.

이 문제에서 구 분석시 구성 단어들의 임베딩을 더해 양수인지 음수인지를 통해 판단한다고 가정이 되어있다.

 

$\alpha$가 양수일 때 두 벡터가 같아진다.

good과 very good처럼 단어의미의 세기가 두 단어의 중요한 차이일 때는 이 차이가 사라지게 된다.

반대로 car와 automobile처럼 두 단어가 거의 비슷한 의미를 가지고 있으면 정규화가 일어나도 차이가 없다.

 

1-d. 주변 단어 벡터$u_o,u_w$에 대한  $J$의 미분을 구하시오.

이 미분은 아래 글에서 이미 계산했었다.

[자연어처리(NLP)] - [Stanford 강의] Lecture 1 : Intro and Word Vectors

따라서 바로 아래의 결과를 가져올 수 있다.

문제에서 $y, \hat{y}, v_c$를 사용해 나타내라고 했으므로 아래 결과를 변형해보자.

정답$u_o$과 오답$u_x$에 대해 $y$의 값은 각각 1,0이므로 아래처럼 최종 식의 모양을 통일시킬 수 있다.

1-e. $U$에 대한 $J$의 미분을 구하시오.

이전 문제의 결과를 바탕으로 아래의 결과를 얻을 수 있다.

2. Machine Learning & Neural Networks

2-a-i. adam optimizer - momentum의 효과를 설명하시오.

기존의 Stochastic Gradient Descent(SGD) update는 아래처럼 이루어진다.

이를 개선하기 위해 나온 adam optimizer라는 방식은 아래처럼 update를 진행한다.

SGD와는 다르게 이전 step에서의 파라미터 학습 방향을 어느정도 반영해 새 학습방향을 정한다.

보통 $\beta _1$은 0.9 정도의 값을 사용한다.

파라미터를 조정하는 방향을 이전 학습의 방향의 90%에 새로운 방향 10%만 적용시키는 것이다.

SGD는 몇개의 샘플을 뽑아 학습시키는 방식이라서 방향이 튈 가능성이 있는데, 이 방식은 이런 경우에도 학습의 방향의 안정성을 어느정도 보장한다.

 

2-a-ii. adam optimizer - Adaptive Learning Rates의 효과를 설명하시오.

위 식에서 $\alpha$는 상수이지만 adaptive learning rates까지 도입된 방식에서는 $\alpha / \sqrt{v_{t+1}}$라는 변하는 값을 사용한다. 이를 통해 각 파라미터에 대해 개별적인 학습률을 적용할 수 있다.

아래 식을 통해 계산된다.

gradient가 클 때는 조금씩 움직여도 충분한 변화가 이루어지기 때문에 $m$에 작은 수를 곱하는 것이 좋고, 반대의 경우에는 큰 수를 곱하는 것이 좋다.

그래서 $v$로 나눠 이를 구현했다.

 

2-b-i. Dropout 정규화를 했을 때  $\mathbf{E}_{p_{\text{drop}}}[\mathbf{h}_{\text{drop}}]_i = h_i$ 이 성립하기 위한 $\gamma$의 값은 무엇인가

dropout정규화는 훈련하는 동안 hidden layer의 일부 원소를 $p_{drop}$의 확률에 따라 0으로 만들어버리는 것이다.

나머지 살아남은 원소에 대해서 $\gamma$라는 상수를 곱해준다.

 

따라서 살아남은 항들은 $(1-p_{drop})$의 확률로 살아남았을 것이다. 그리고 $\gamma$이 곱해지므로 

$\gamma (1 - p_{\text{drop}}) h_i = h_i$이고 답은 $\gamma = \frac{1}{1 - p_{\text{drop}}}$가 된다.

 

2-b-ii. Dropout을 훈련 때만 적용해야하고 실제 평가시에는 적용하지 않아야 하는 이유는 무엇인가

과적합 방지 : 어떤 뉴런이 다른 뉴런에게 과하게 영향받는 것을 없애준다.

앙상블 효과 : 매번 다른 얇은 신경망을 학습 시키는 것과 같은 효과이다. 이 여러 네트워크들의 예측을 평균내서 골고루 사용할 수 있다.

평가 시 : dropout이 적용되면 매번 결과가 달라지기 때문에 적용하면 안된다.

 

---

3. Neural Transition-Based Dependency Parsing

3-a.아래 예시에 대해 parsing을 진행하시오.

 

Stack	Buffer	적용한 Transition	Dependency Added
[ROOT]	[I, presented, my, ...]		[ ]
[ROOT, I]	[presented, my, ...]	SHIFT	[ ]
[ROOT, I, presented]	[my, findings, at, the,...]	SHIFT	[ ]
[ROOT, presented]	[my, findings, at, the,...]	LEFT-ARC	(presented → I)
[ROOT, presented, my]	[findings, at, the, ...]	SHIFT	[ ]
[ROOT, presented, my, findings]	[at, the, NLP, conference]	SHIFT	[ ]
[ROOT, presented, findings]	[at, the, NLP, conference]	LEFT-ARC	(findings → my)
[ROOT, presented]	[at, the, NLP, conference]	RIGHT-ARC	(presented → findings)
[ROOT, presented, at]	[the, NLP, conference]	SHIFT	[ ]
[ROOT, presented, at, the]	[NLP, conference]	SHIFT	[ ]
[ROOT, presented, at, the, NLP]	[conference ]	SHIFT	[ ]
[ROOT, presented, at, the, NLP, conference]	[ ]	SHIFT	[ ]
[ROOT, presented, at, the, conference]	[ ]	LEFT-ARC	(conference → NLP)
[ROOT, presented, at, conference]	[ ]	LEFT-ARC	(conference → the)
[ROOT, presented, conference]	[ ]	LEFT-ARC	(conference → at)
[ROOT, presented]	[ ]	RIGHT-ARC	(presented → conference)
[ROOT]	[ ]	LEFT-ARC	(ROOT → presented)

 

3-b. n개의 단어를 가진 문장은 얼마나 많은 단계를 거쳐 파싱되는가

한 단어가 스택으로 오기 위해서 shift한번, dependency가 생기기 위해 left-arc또는 right-arc연산을 한번 해서 총 2번의 transition이 필요하다.

따라서 전체 문장을 위해서는 2n번의 단계가 필요하다.

 

3-c. [코딩 과제] 제공된 파일 중 parser_transitions.py의 __init__, parse_step함수 구현하기

https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1246/

제공되는 파일은 여기서 받아볼 수 있다.

 

1) PartialParse클래스의 __init__함수 구현

위에서 계속 사용했던 스택, 버퍼, 의존성 표현을 초기화하는 코드를 작성하면 된다.

아래 세 줄로 완성할 수 있다.

        self.stack=["ROOT"]
        self.buffer=sentence.copy()
        self.dependencies=[]

 

2) PartialParse클래스의 parse_step함수 구현

parsing이 이루어질 때 각 선택지(shift, left-arc, right-arc)에 따른 변화를 반영하는 코드를 작성하면 된다.

        if transition=="S":
            self.stack.append(self.buffer.pop(0))
        elif transition=="LA":
            self.dependencies.append((self.stack[-1],self.stack.pop(-2)))
        elif transition=="RA":
            self.dependencies.append((self.stack[-2],self.stack.pop(-1)))

 

3-d. [코딩 과제] 제공된 파일 중 parser_transitions.py의 minibatch_parse함수 구현하기

문장마다 하나의 PartialParse 객체가 만들어진다.

아직 파싱이 끝나지 않은 리스트 unfinished_parses를 만들고 이 안에 더이상 원소가 없을 때까지 반복한다.

반복문 안에서는 10개의 문장에 대해 같이 한 단계씩 파싱을 진행한다.

문장의 길이가 다르므로 먼저 끝나는 문장이 있을 수 있는데, 이러면 다음 문장을 바로 가져온다.

    partial_parses = [PartialParse(sentence) for sentence in sentences] #(스택,버퍼,의존관계)의 리스트
    
    unfinished_parses=partial_parses[:]
    while len(unfinished_parses)>0:
        minibatch = unfinished_parses[:batch_size]#10개
        transitions = model.predict(minibatch)#각 10개에 대한 전이 선택지

        for pp, transition in zip(minibatch, transitions):#각 10개에 대해
            pp.parse_step(transition)#전이 선택지 적용
        unfinished_parses = [pp for pp in unfinished_parses if len(pp.buffer) > 0 or len(pp.stack) > 1]
    dependencies = [pp.dependencies for pp in partial_parses]

 

3-e. 어떤 전이를 수행할지 예측하는 모델 만들기 (parser_model.py)

모델의 구조는 아래 그림을 참고하면 된다.

아래 그림은 단일 샘플에 대한 모델의 작동 설명이다.

실제로 우리는 미니배치(10개)를 사용할 것이므로 이 경우 1 대신 10이 들어가면 된다.

1) parser_model클래스의 __init__ 구현

아래의 코드를 사용해 각 가중치 행렬, 편향행렬 등의 차원을 위 그림처럼 설정한다.

        self.embed_to_hidden_weight = nn.Parameter(torch.empty(self.n_features * self.embed_size, self.hidden_size))#(36*임베딩size)*hidden_size
        self.embed_to_hidden_bias = nn.Parameter(torch.empty(self.hidden_size))
        self.dropout = nn.Dropout(self.dropout_prob)
        self.hidden_to_logits_weight = nn.Parameter(torch.empty(self.hidden_size, self.n_classes))#hidden_size*3
        self.hidden_to_logits_bias = nn.Parameter(torch.empty(self.n_classes))

이 행렬들의 초기화는 문제에서 요구한 함수를 사용했다.

        nn.init.xavier_uniform_(self.embed_to_hidden_weight)
        nn.init.uniform_(self.embed_to_hidden_bias)
        nn.init.xavier_uniform_(self.hidden_to_logits_weight)
        nn.init.uniform_(self.hidden_to_logits_bias)

 

2) parser_model클래스의 embedding_lookup 구현

단어 인덱스들의 행렬 w를 입력으로 받아 그 단어들의 임베딩을 가져오는 역할을 하는 함수이다.

w.view(-1)로 w를 1차원으로 펼친다.

index_select를 사용해 이 w에 있는 인덱스들의 단어를 가져온다.

그 이후 다시 view를 사용해 차원을 맞춰준다.

        x = torch.index_select(self.embeddings, 0, w.view(-1)) #w를 flatten한 후 index_select
        x = x.view(w.size(0), -1) #차원 맞추기

 

3) parser_model클래스의 forward 구현

위에서 구현한 함수들을 사용해 실제 모델을 만드는 과정이다.

        x = self.embedding_lookup(w)
        x = torch.matmul(x, self.embed_to_hidden_weight) + self.embed_to_hidden_bias #x*W + b
        x = F.relu(x)#ReLU
        x = self.dropout(x)#dropout
        logits = torch.matmul(x, self.hidden_to_logits_weight) + self.hidden_to_logits_bias #x*W + b

 

i) $h$의 $x$에 대한 미분을 계산하시오

ReLU안의 값이 0이 아닐때만 따져보면,

$$\frac{\partial h_i}{\partial x_j} = \frac{\partial}{\partial x_j} (\sum_{k=1} x_k W_{ki} +b_i) = W_{ji}$$

 

ii) $J(\theta)$를 $\textbf{l}_i$에 대해 미분하시오

이 전에 softmax의 미분에 대해 잠깐 알아봐야한다.

softmax미분

Softmax 함수의 $i$번째 출력 $\hat{y}_i$는 다음과 같이 정의된다.

$$\hat{y}_i = \frac{e^{l_i}}{\sum_{k=1}^{K} e^{l_k}}$$

softmax미분-case1 : $i = j$ 

$$\frac{\partial \hat{y}_i}{\partial l_i} = \frac{\partial}{\partial l_i} \left( \frac{e^{l_i}}{\sum_k e^{l_k}} \right)$$

분수 함수 미분을 적용하면,

$$\frac{e^{l_i} \sum_k e^{l_k} - e^{l_i} e^{l_i}}{(\sum_k e^{l_k})^2}$$

$$\frac{e^{l_i}}{\sum_k e^{l_k}} \left( \frac{\sum_k e^{l_k}}{\sum_k e^{l_k}} - \frac{e^{l_i}}{\sum_k e^{l_k}} \right) = \hat{y}_i (1 - \hat{y}_i)$$

최종적으로 아래처럼 나타낼 수 있다.

$$\frac{\partial \hat{y}_i}{\partial l_i} = \hat{y}_i (1 - \hat{y}_i)$$

 

softmax미분-case2 : $i \ne j$ 

$$\frac{\partial \hat{y}_i}{\partial l_j} = \frac{\partial}{\partial l_j} \left( \frac{e^{l_i}}{\sum_k e^{l_k}} \right)$$

$$\frac{\partial \hat{y}_i}{\partial l_j} = \frac{0 \cdot \sum_k e^{l_k} - e^{l_i} \cdot \frac{\partial e^{l_j}}{\partial l_j}}{(\sum_k e^{l_k})^2} = \frac{-e^{l_i} e^{l_j}}{(\sum_k e^{l_k})^2}$$

이 경우도 같은 방식으로 아래의 식을 얻을 수 있다.

$$\frac{\partial \hat{y}_i}{\partial l_j} = -\hat{y}_i \hat{y}_j$$

 

이제 원래 문제를 풀어보자.

$$\frac{\partial J}{\partial l_i} = \sum_{j=1}^{K} \frac{\partial J}{\partial \hat{y}_j} \frac{\partial \hat{y}_j}{\partial l_i}$$

첫 항은 아래처럼 계산된다.

$$\frac{\partial J}{\partial \hat{y}_j} = \frac{\partial}{\partial \hat{y}_j} (-\sum_{k} y_k \log \hat{y}_k) = -y_j \frac{1}{\hat{y}_j}$$

따라서 식은 다음과 같다.

$$\frac{\partial J}{\partial l_i} = \sum_{j=1}^{K} \left( -\frac{y_j}{\hat{y}_j} \right) \frac{\partial \hat{y}_j}{\partial l_i}$$

여기서 두번째 항은 방금 계산한 소프트맥스 함수의 미분이다.

 

 

$i=j$일 때는 $\left( -\frac{y_i}{\hat{y}_i} \right) \cdot \hat{y}_i (1 - \hat{y}_i) = -y_i (1 - \hat{y}_i)$

$i \ne j$일 때는 $\sum_{j \ne i} \left( -\frac{y_j}{\hat{y}_j} \right) \cdot (-\hat{y}_i \hat{y}_j) = \sum_{j \ne i} y_j \hat{y}_i$이고,

따라서 전체 식은 $\frac{\partial J}{\partial l_i} = -y_i (1 - \hat{y}_i) + \sum_{j \ne i} y_j \hat{y}_i$이다.

 

만약 $i=c$라면 두번째 항에서 $y_j=0$이므로 $-(y_i-\hat{y}_i)=\hat{y}_i-y_i$,

만약 $i \ne c$라면 첫번째 항이 0이 되고 두번째(시그마)항에서 $j=c$인 항 하나만 살아남으므로, $1\cdot \hat{y}_i= \hat{y}_i-y_i$

따라서 $i$가 $c$인지 여부에 상관없이 $\frac{\partial J}{\partial l_i} = \hat{y}_i - y_i$이다.

 

3-f. 파싱 오류 찾기

아래 4가지 오류 중 어떤 것에 해당하는 오류를 가지고 있는지 찾는 문제이다.

 

전치사구 연결 오류 (Prepositional Phrase Attachment Error).
동사구 연결 오류 (Verb Phrase Attachment Error).
수식어 연결 오류 (Modifier Attachment Error).
등위 접속 연결 오류 (Coordination Attachment Error).

 

1. acquisition -> citing 삭제

citing -> university으로 수정

동사구 연결 오류

 

2.element -> crucial 삭제

crucial -> most 으로 수정

수식어 연결 오류

3. declined -> decision 삭제

reason -> decision 으로 수정

전치사구 연결 오류

4. affects -> one 삭제

plants -> one 으로 수정

등위 접속 연결 오류