Word2vec이다!! 어마어마한 수식이 기다리고 있으니 기대해도 좋다. 이번 포스팅에서는 Word2vec을 간략하게 설명한 후 Word2vec의 한 model인 continuous bag of words(CBOW)를 수학적으로 설명할 예정이다.

우선 word2vec이 무엇이냐? text classification을 하기 위해 만들어진 것이다. word2vec을 통해서 우리는 비슷한 부류에 있는 단어들을 모을 수 있다. 예를 들어, Apple, Samsung은 서로 가까이 있을 것이고, BMW, Audi도 서로 가까이 있을 것이다. word2vec의 유명한 예로 "man과 woman의 비슷함은 queen과 king의 비슷함과 비슷할 것이다" 이런 것도 있다. 다음의 예시 문장을 보자.

the king loves the queen

the queen loves the king

the dwarf hates the king

the queen hates the dwarf

the dwarf poisons the king

the dwarf poisons the queen

기술적인 것을 모두 잊어버리고 한번 생각해보자. 

the king ______ the dwarf

빈 칸에 알맞은 것은 무엇인가? 음 loves는 아닌 것 같고. 문맥상 보면 hates가 들어가야 맞다. 지금 이거는 the king dwarf를 보고 우리가 유추한 것이다. 그러면 반대로 이렇게도 할 수 있다.

____ ____ dwarf ____ ____

dwarf라는 단어를 바탕으로 주변 단어를 추측하는 것. 

word2vec은 이렇게 크게 두 가지 형태의 model을 가지고 있다. 첫번째 예제처럼 여러 단어로부터 한 단어를 추측하는 것을 CBOW : continous bag of words model이라고 하고, 두번째 예제처럼 한 단어로부터 여러 단어를 추측하는 형태의 model을 skip gram model이라고 한다. 

이번 포스팅에서는 continuous bag of words model에 대해서 공부해보려고 한다. 이 CBOW 모델을 제대로 알기 위해서는 이 model을 어떻게 train을 하는지 알아야 되고, 그리고 어떻게 사용을 하는지 알아야 된다. 우선 여기서는 어떻게 train하는지를 알아보고 그 다음에 어떻게 사용하는지를 알아보자.

우선 train을 어떻게 하는지 알아보자. train을 하기 위해서는 이전 포스팅에서 공부했었던 ANN과 gradient decent가 사용된다. 다른 것이 있다면, ANN 포스팅에서 나왔던 activation function이 hidden layer에는 적용되지 않고, output layer에만 적용된 다는 것. 그리고 ANN 포스팅에서는 activation function으로 sigmoid function을 사용했으나 여기서는 softmax function을 사용할 것이라는 점이 다르다.

activation function 이 hidden layer에는 적용되지 않기 때문에 아래와 같은 형태의 ANN을 갖게 될 것이다.

x와 w와의 matrix 곱이 바로 (activation function 거치지 않고) w'에 적용되어 w'와의 곱이 u로 나오게 된다. 그리고 이 u에 우리는 softmax function을 적용시킬 것이다. 자꾸 softmax softmax하는데 그게 어떤 식인지 알아보자.

P(wO|wI)가 softmax function의 결과물이다. 즉, conditional probability를 구하는 함수가 되는데, 어떤 단어(e.g. dwarf)가 input으로 들어왔을 때, output으로 e.g. hates가 될 확률을 구하는 것이다. 뭔가 식만 보면 어떻게 하라는 것인지 잘 모르겠으므로, 실제 예를 봐보자. V는 unique한 단어의 개수라는 점과 N은 단어를 표현하고 싶은 dimension이라고 보면 된다. 위의 사용했던 문장을 다시 봐보자.

the king loves the queen

the queen loves the king

the dwarf hates the king

the queen hates the dwarf

the dwarf poisons the king

the dwarf poisons the queen

unique words : the king loves queen dwarf hates poissons

여기서 unique words를 전문용어로 bag of words라고 한다. 그러면 이 bag of words의 길이는 7이다. 그래서 V = 7로 놓고, 난 각 단어를 3차원으로 표현하고 싶으므로 N = 3으로 놓을 것이다. 그리고 input word는 dwarf, output word는 hates라고 해보자.

위와 같이 softmax function을 사용하면 된다. 위의 결과를 해석해보면 위와 같은 w와 w'이 주어졌을 때, p('hates'|'dwarf')의 확률이 0.1428이라는 것이다. 자 여기서 질문!! 저기 w와 w'은 어떻게 구한 것일까? 답은 그냥 랜덤이다. 그냥 말그대로 랜덤 함수를 통해 0과 1사이의 값을 찍어낸 것이다. 그런데 그렇게 하면 당연히 확률이 좋을 리가 없다. 그래서 gradient decent가 나오는 것이다. ANN에서는 error를 minimize하는데 목표를 두었으나, 여기서는 softmax function의 결과값을 maximize하는 것을 목표로 둔다. 아래와 같이 구할 수 있다.

ipad에 써서 손글씨가 엉망이다.(원래 그렇기도 하다) 아무튼 p(wO|wI)를 maximize한다는 말은 그것의 log를 취한 값을 maximize하는 것과도 같기 때문에 위와 같은 식이 나온다. 이제 우리는 E를 알았으니 이것을 w와 w'로 미분을 해주도록 하자. w'로 미분을 먼저 해보자. 지금부터 조금 복잡해질 수 있다. 그래서 기본식으로 아래를 먼저 이해하고 가자.

위의 그림과 ANN을 이해했다면 무리없이 이해할 수 있는 식이다. E를 w'로 미분할 때는 chain rule을 이용하여 아래와 같이 미분한다.

앞에 dE/duj는 아래와 같고

(위의 식에서 tN은 tN이 실제 output일 경우에만 1이다. 이 부분 조금 어려울 수 있으나 잘 생각해보면 알 수 있다.)

뒤에 duj/dwij는 식 (2)를 전개하여 미분하면 hi라는 것을 쉽게 알 수 있다.

자 그러면 마지막으로 update!! 

(저기 ejhi앞에 있는 것은 learning rate이다.)

다음에는 dE/dwij를 구할 차례다. 이전 것보다 조금 더 복잡하니 집중해서 보자.

앞에 dE/dhi는 아래와 같이 구할 수 있다.

(식이 조금 복잡하므로 EHi ~ EHn으로 치환한것이다.)

뒤에 dhi/dwji는 식(1)을 전개하여 미분해보면 xj라는 것을 쉽게 알 수 있다. 자 이제 update 남았다. 

xj 가 어디갔냐고 물어보는 사람이 있을 것이다. 없어진거 아니다.

위의 식에서 x1 xV까지를 잘 생각해보면, V개 중에 하나만 1이다. 따라서 V row 중 하나만 1이고, 1은 곱하나마나이므로, 한 row가 EH1부터 EHn가 되고 나머지는 모두 0이 되는 것이다. 그렇다 결국 wji를 미분한 결과는 old wji의 한 row만 변경시키게 되는 것이다.

ANN에서 말했듯이 이 과정을 엄청엄청 많이 반복해서 w와 w'를 계속 optimize하는 것이다. 지금까지 w와 w'를 update하는 과정을 살펴봤는데, 한 가지 덧붙일 것이 있다. 지금까지는 input word 하나로 output word 하나를 예측해왔는데, input word가 여러 개일 수도 있다. 그럴 때는 아래와 같이 계산하면 된다. 원리는 같으나 합해서 평균내주는 부분이 조금 추가되었다. 

input word = "queen", "loves"

target word = "king"

w'을 우선 update 해줘야 되는데, 그러려면 h를 알아야 된다. h는 hidden layer의 output인데, 우리는 input word가 두 개 있으니까 그 hidden layer output도 두 개 나올 것이다. 

결과물로 나온 loves와 queens 두 개를 더해서 2로 나눠주면 h가 나오게 된다. 그 h를 이용해서 w'를 update해준다. w'new = w'old - learning_rate * error * h 하면 된다. 우리는 단어가 7개 있으니까 이 식을 각 7개의 단어에 대해서 반복해주면 되는데, 이 식에서의 error는 현재 작업하고 있는 word와 target word가 같을 경우에는 1 - p, 그렇지 않을 경우에는 0 - p가 되겠다. 

그 다음에는 w를 update 해줘야 되는데, 위에서 설명했을 때, input word가 하나 일 때는 한 row만 빼주게 되는 결과가 나타난다고 했다. 이번에는 input word가 두 개니까 두번 수행해주면 된다. 한 가지 유의할 점은 식이 w_new = w_old - (1/C) * learning_rate * EH 라는 점이다. 1/C를 곱해주고 빼는 것을 잊지 말자. (단 C는 context 개수, 여기서는 2가 된다) 자 이렇게 w까지 update 해줬다.

input word가 여러 개 있을 경우에는 이와 같이 해주면 된다. 아 힘들다. 자 마지막으로 어떻게 쓰는지에 대해서 써보자. 쓰는 방법은 사실 한 가지가 아니다. 여러 방법으로 적용시켜주면 된다. 예를 들어 나는 이런 식으로 써봤다.

예를 들어 w가 위와 같이 있다고 해보자. 그리고 내가 할 일은 아래의 문장들에 대해서 positive negative를 추측하는 것이다.

train set으로 Naive Bayes Classifier로 training을 할 것이고 그 모델을 가지고 test sentence를 test 할 것이다. train하기 전에 w(7x3) word vector를 가지고 무언가를 할 것이다. 바로 각 문장을 vector화 해줄 것이다.

첫번째 sentence "the king kills the dwarf" 에서는 the, king, dwarf를 위의 w word vector에서 찾을 수 있다. 다 더해서 3으로 나눠주자.(못 찾은 kills는 무시해주면 된다.) 이런 식으로 각각의 train에 대해서 진행하면 아래와 같은 word vector:sentiment를 얻을 수 있다.

위의 세 train sentence를 dimension 1, 2, 3으로 vector화 했고, 그것의 sentiment를 가지고 있다. 이 train set으로 여러가지 classifier를 적용시키는 것이다. 그렇게 model을 training했을 때, test sentence의 vector [0.542085479, 0.458401841, 0.420776285]는 negative? positive? 예측을 하는 것이다. 이런 식으로 쓰일 수 있다는 것이다.

참고로 위의 내용은

http://www-personal.umich.edu/~ronxin/pdf/w2vexp.pdf

http://www.folgertkarsdorp.nl/word2vec-an-introduction/

여기에서 확인할 수 있으니 참고하길 바란다.

이번 포스팅은 Back propagation에 대해서 적어보려고 한다. 어마어마한 양의 식이 포스팅될 예정이다. 후 이거 공부하려고 오늘 하루 다 썼다.

우선 back propagation이 뭔지부터 설명해보자. back propagation은 ANN를 training하는 과정이다. 우리가 이전 포스팅에서 ANN의 단 한번의 forwarding으로는 전혀 그럴 듯한 결과를 얻지 못한다고 했었다. 그래서 weight을 update한다고 했었다. 그 weight update하는 과정을 우리는 미분을 써서 dJ/dw가 0이 되는 지점을 찾는다고 했다. 즉 weight을 update하면서 J는 최소값으로 가까워진다는 말이다. 이것을 하는 과정이 back propagation이다. 즉 ANN의 training하는 알고리즘 중 하나가 back propagation algorithm이다.

자 그러면 미분을 시작해보자. 우선 뭘 어떻게 해야하는지 outline을 잡고 시작해보자. 우선 우리는 dJ/dw를 구할 것인데 우리가 예제로 삼고 있는 XOR ANN은 두 개의 weight vector가 있다.

하나 W(1)은 Input layer에서 Hidden layer로 갈 때 사용하는 weight vector이고, 또 다른 하나 W(2)는 Hidden layer에서 Output layer로 갈 때 사용하는 weight vector이다.

이전의 J를 위의 w(1)과 w(2)로 미분을 하면 아래와 같다.

우리는 dJ/dw(1)와 dJ/dw(2)를 구해야 되는데 먼저 dJ/dw(2)를 구하도록 하자. 밑에 식에서 시그마(sum)는 일단 잠깐 빼고 시작하자.

아래의 식은 https://www.youtube.com/watch?v=GlcnxUlrtek 여기에서 나오는 식과 같다. 이 영상과 밑의 식을 같이 보시길 바란다. notation에 있는 숫자도 조금 틀릴 수 있다.

y와 yHat 그리고 z(3) 미분한 값은 각각 아래와 같다.

dz(3)/dw(2)는 왜 저 행렬이 될까? 간단하다. z(3) = aw(2)이기 때문에 w(2)로 미분해주면 a만 남는 것이다. 여기서 우리가 처음에 잠깐 생략했었던 sigma를 다시 넣어준다. 어떻게 넣어줄까? 바로 행렬 곱셈이다. 지금까지는 전부 스칼라 곱이었으나, 마지막에 행렬곱셈으로 바꿔주므로서 아래와 같이 summation을 할 수 있다. 

시그마(3) = -(y-yHat) f'(z(3))는 3x1 행렬이므로 위의 식을 행렬 곱셈으로 바꿔주기 위해서는 3x3 행렬을 시그마(3) 앞에 곱해줘야 되고, 적절한 순서로 summation해주기 위해 transpose matrix로 바꿔준다. 이 부분을 잘 이해해야 된다.

행렬곱셈으로 바꿔주므로서 우리는 앞서 생략했었던 summation도 다시 적용시켰다. 자 이제 dJ/w(1)을 구할 차례다. 이 값도 비슷하게 구할 수 있다. J를 w(1)으로 미분하여 시작하면 된다.

위의 식에서 w(2)^T = dz(3)/da(2) 이 부분.. 이 부분 나도 잘 모르겠다. 대충은 알겠는데, 왜 Transpose를 해줘야 되는지 정확하게는 모르겠다. 그거 빼고는 위의 식은 이전에 dJ/dw(2) 했을 때를 생각하면 이해가 될 것이다.

이제 dJ/dw(2)과 dJ/dw(1)을 구했으니 실제로 weight vector를 업데이트해주면 된다. 이 때 새로운 변수가 들어간다. 바로 learning rate이다.

new w(1) = old w(1) + (learning rate) * dJ/dw(1)

new w(2) = old w(2) + (learning rate) * dJ/dw(2)

이 식으로 w(1)과 w(2)를 update해준다. 이렇게 하면 이제 하나의 epoch가 끝난 것이다. w(1)과 w(2)가 update되었으니 x1과 x2를 update된 w(1)과 w(2)에 집어넣어서 위의 과정을 또 하면 된다. ANN은 이 과정을 무수히 많이 반복하여 error rate을 최대한 작아지게 만든다.(Training) 그 과정을 눈으로 보고 싶다면 아래의 링크를 통해 보면 된다.

http://www.emergentmind.com/neural-network

epoch를 반복반복반복할 수록 XOR 계산에 대한 predicted value가 정확히 0과 1은 아니지만 0.2 0.3 또는 0.97, 0.98로 가까워지는 것을 볼 수 있다. 이걸 만든 사람이 자기 개인 포스팅도 해놓았더라. 

http://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/

우와. 정말 engineer다. engineer는 이래야 된다.ㅠㅠ 도무지 실제 예제를 설명해둔 것을 찾을 수가 없어서 자기가 직접 했덴다. 정말 나도 이런 engineer가 되어야 되는데...

아무튼 우리는 back propagation은 이만 끝내고 다음 포스팅으로 넘어가보자. 아마 다음 포스팅은 Word2Vec이 되지 않을까 싶다. 참고로 back propagation에 대한 실제 값을 통한 예제도 언젠간 반드시 포스팅할 거다. 

왜 분명히 배운 것들인데 왜 복습을 하는 것 조차 이틀이나 걸리는 것인가. 솔직히 지금도 헛깔린다. 아무튼 Artificial Neural Network(ANN)을 공부해보도록 하자.

ANN에서는 data들을 어찌어찌 처리하여 그 data에 대한 predicted value를 만들어낸다. 예를 들어, 간단하게 XOR 함수를 놓고 생각해보자. x1과 x2가 1이면 그 값은 0이 된다. 우리가 이것을 ANN을 통해 예측해보려고 한다. 그러면 x1과 x2가 각각 1이니까, 이 값들을 어찌어찌 하여 output을 0으로 혹은 1으로 추측해보려고 한다. 어떻게 추측을 할까? weight을 곱해서 알아보는 것이다. 

위의 그림에서 x1, x2는 1이고 w1, w2는 각각 x1과 x2에 대한 weight이다. (x1, x2)와 (w1, w2)의 dot product을 구하면 o1이 나온다. Artificial Neural Network에서 Neural이 위의 그림 저것이다. Neural Network는 저것들이 여러개 모였다는 것이다. 즉, 우리의 XOR 예를 가지고 생각해보자면, XOR를 예측하기 위해 여러개의 Neural Network를 만들었다고 보면 된다. Neural Network는 아래와 같은 형태를 띄게 된다.

위의 그림에서 notation부터 정리를 해보자. 우선 각각 원i에서 원j으로의 weight을 wij로 표시했다. 그리고 원은 1부터 6까지 있다. 그리고 원i에서 나오는 output을 oi로 표시했다. 자 위의 그림에서라면 우리는 x1과 x2의 XOR을 예측하기 위해 아래와 같은 일을 해야된다.

여기서 중요한 용어를 한번 정리해보자. 바로 Input layer, hidden layer, output layer이다. (사실 위의 식은 틀린 것이다. 중요한 과정을 하나 빼먹은 과정인데, 조금만 더 읽어보면 뭐가 빠졌는지 알 수 있다.)

여기서 Hidden layer는 무슨 말이냐면, 말 그대로 감춰진 layer라는 것이다. 무슨 일이 벌어지는지 모른다는 것이다. 여기서 Hidden layer는 하나 밖에 없지만, 실제로는 더욱 깊은(deep) 여러 층의 hidden layer가 있는데, 여기에서의 deep이 deep learning의 deep이라고 한다.

자, 자세한건 일단 제쳐두고 w13부터 w56까지 특정 값을 가지고 있다고 했을 때, 이제 우리는 x1과 x2만 있으면 o6를 구할 수 있다. 그러면 그 값이 0이나 1로 정확히 나올까? o6를 구하기 위해서 우리는 dot product를 input layer에서 hidden layer로 3번하고 hidden layer에서 output layer로 1번, 총 4번을 하는데, 그 dot product의 결과가 0이나 1로 딱 떨어질까? 그럴리는 거의 없다고 보면 된다. 그럼 어떻게 할까? 사실 우리는 지금까지 설명 안한 과정이 한 부분 있다. 그 부분을 포함하면 각 neural은 아래의 그림이 된다.

dot product 결과 z1을 Activation function에 집어넣어야 된다. 이 Activation function은 어떤 함수를 택하느냐에 따라 o1의 값이 바뀔 수 있는데, 가장 일반적으로 sigmoid function을 택한다. (어느 순간부터 가장 일반적으로 ReLu 함수를 많이 사용한다.)

sigmoid function은 그 값이 0과 1 사이(probability 구할 때 유용)라는 특징이 있는 "미분 가능한" 함수이다. ("미분 가능한"을 강조한 이유는 다음 포스팅 backpropagation을 설명할 때 같이 설명하겠다) 자 이제 우리는 o6를 구하는 올바른 식을 알아보자.

이제 o6는 무조건 0과 1사이의 값이 된다. 우리가 x1, x2를 가지고 위의 계산 과정을 거쳤을 때, 마지막 o6의 값이 0.8이 나왔다면 그 값은 1이 될 확률이 클 것이고, 0.2가 나왔다면 그 값은 0일 확률이 크다는 의미가 될 것이다.

우리가 지금까지 한 것은 ANN에서 forwarding이라고 한다. 즉 주어진 X의 값으로 그 ANN의 최종 output을 만들어내는 과정이다. 그렇다면 여기서 한 가지 질문을 해보면, 이거 한번 계산하면 정말 쓸만한 classifier가 되냐? 당연히 아니다. weight이 어떤 값이냐에 따라 결과는 아주아주 많이 바뀔 것이다. 그럼 우리는 가장 좋은 weight을 찾아야 된다. 그것은 어떻게 찾을까? cost function(J)을 통해 구하면 된다. 

여기서 y_hat은 우리가 구한 predicted value이다. 즉 predicted y와 실제 y의 차이를 구해서 제곱을 한 후 그것을 반으로 나눠준다는 것이다. 왜 절반으로 나누냐? 다음 포스팅 back propagation에서 위의 식을 미분할 것인데 그 때 제곱의 2가 밑으로 떨어지면서 1로 상쇄되면 계산하기 편하니까 이다. 이유가 못 마땅하다는 생각을 하는 사람이 많을 것이다. "수학이 뭐.. 편할 거 같은 숫자로 아무렇게나 하면 되는거야?" 이런 생각을 내가 했었고 그것 때문에 1/2를 곱해주는 이유에 대해서 꽤나 찾아봤었는데 결론은... 사실 뭘 곱해도 상관 없다 여기서는... 어짜피 우리한테 중요한 것은 두 개의 차이가 중요한 것이니까. 그 외의 상수는 뭐든 좋다는 것이다.

자 다시 본론으로 돌아가서, 이 cost function의 값이 가장 작도록 하는 weight을 찾아야 되는데, 가령 1부터 1000까지 일일이 weight을 설정하여 나온 값의 최소값을 구하면 아주 아주 아주 시간이 오래 걸릴 것이다. 그래서 우리는 여기서 미분을 한다. weight으로 미분을 해주는 것이다. cost function을 J로 놓으면 우리는 dJ/dw를 구해서 그 값이 0이 되는 방향으로 계속 weight을 update해줄 것이다. 이렇게 최소값을 찾는 과정을 gradient decent라고 한다.

마치 게임할 때 적절한 능력치를 올려줘서 balance를 맞춰주는 것처럼, 혹은 오디오에서 여러가지 음향 효과 버튼을 돌려서 최적의 소리를 세팅하는 것처럼, 각각의 weight(w13부터 w56까지)의 weight "버튼"을 적절히 돌려서 cost function이 최소화되는 그 바로 그 순간을 찾는 것이다.

위의 그림은 아래의 동영상의 일부를 캡쳐한 것이다. 정말 잘 만든 동영상이다.

https://www.youtube.com/watch?v=5u0jaA3qAGk

여기서 한가지만 더 쓰고 포스팅을 마치자. 만일 cost function이 아래와 같이 non-convex이면 어떻게 할까?

우리가 진짜 원하는 것은 global minimum인데 우리가 구한 값이 local minimum일 수도 있다는 이야기이다. 요약하면, 상관없다 이다. local minimum이여도 충분히 쓸만하다고 한다. 조금 어이없지만 그렇다고 한다. (마치 Naive Bayes에서 각 사건을 독립인 것처럼 전부 곱해버리는 데도 불구하고 실제로 꽤나 괜찮은 효율을 내는 것과 비슷하다.)

이것으로 이번 포스팅을 마치려고 한다. 다음 포스팅은 back propagation algorithm이다.