이번 Lecture2에서는 지난Lecture1(https://eda-ai-lab.tistory.com/120)에 이어 word2vec에 대해 자세히 알아보도록 하겠습니다. 그리고 counting 기법과 GloVe model에 대해서 살펴보도록 하겠습니다. 대부분의 내용은 파리의 언어학도의 글을 토대로 만들었습니다.
1. Review: Main idea of word2vec
지난 시간에 배운것부터 복습해보면, Word2vec는 one-hot-vector의 한계를 극복하려고 등장한 개념입니다. 중심단어가 주어졌을 때, 주변단어가 나타날 확률을 계산하고 window내의 이 확률의 곱을 최대화 하도록 학습을 하게 됩니다.
Objective function은 위의 P(o|c)가 되고, 우변의 v는 입력층과 은닉층을 잇는 가중치 행렬 W의 행벡터, u는 은닉층과 출력층을 잇는 가중치 행렬 W'의 열벡터입니다. 그리고 분모의 경우 주변단어에 등장하지 않은 단어와 중심단어의 벡터 내적(코사인 유사도)를 의미하고 분자의 경우 주변단어에 등장한 단어와 중심단어의 코사인 유사도를 의미합니다. ( 학습은 주변단어와 중심단어의 유사도는 높이면서 주변단어에 나타나지 않은 단어와 중심단어간의 유사도는 낮추는 방향으로 학습을 하게 됩니다. )
위의 구조를 파리의 언어학도님의 설명과 함께 보도록 하겠습니다. Skip-gram의 계산은 아래와 같이 진행됩니다.
문서 D로부터 사용된 단어 wt를 모두 추출하여 one-hot-encoding W를 만든다.
최종적으로 우리가 학습 할 word embedding 파라미터 V (아래그림 W, center word vector)를 랜덤 초기화.
Scoring을 위한 파라미터 U (아래그림 빨간네모 3개짜리, context word vector)를 랜덤 초기화.
파라미터 업데이트 : Gradient Descent의 결과에 따라 파라미터 V, U 업데이트
출처 : 파리의 언어학도 블로그 - 스탠포드 자연어처리 2강 자료
위의 예를 보면, 맨 왼쪽의 Vx1의 벡터는 단어의 one-hot vector를 의미하고 그 길이 V는 단어의 총 갯수로 정해집니다. 그리고 dxV는 2에서 center word의 word embedding 파라미터를 초기화한 부분입니다. 여기서 d는 embedding size이고 곱해지는 부분은 center word의 representation한 부분이라고 생각해도 됩니다. ( one-hot vector의 특성상 그 외는 0으로 곱해지고 저 부분만 1로 곱해지기 때문입니다. ) 그 이후로 Vxd의 부분에 해당하는 scoring부분이 진행되어 Output word representation을 합니다. 이 후 softmax를 취해 이를 확률 분포로 바꾸어주고 cross entropy를 진행합니다. 이 과정은 아래의 사진에 잘 나와있습니다.
그림 출처 : https://cs231n.github.io/linear-classify / 참고로 2번째 사진에서 +는 ,가 오타난것 같습니다.
위에서 출력값은 [-2.85 , 0.86, 0.28] 이었는데, 우리가가지고 있는 정답 y는 [0, 0, 1]과 같은 확률분포 이기 때문에, softmax 함수를 사용해서 0~1사이의 값을 갖는 확률 분포의 형태로 바꿔주게 됩니다. ( 파란색 1과 2를 거친 부분입니다. exp를 하는 이유는 이전에 log를 취했기 때문에 ) 이렇게 반환 된 결과 softmax(z) = [0.016, 0.631, 0.353]을 cross-entropy를 사용해서 [0, 0, 1]과의 오류에 대한 피드백을 하게 됩니다. yi의 대부분이 0이기 때문에 1인 부분만 남게 되고 -log(0.353)을 가지게 됩니다.
이후 이 값을 가지고 backward의 연산이 진행됩니다.
위의 그림을 보면 1번째 사진에서 objective function을 정의하고 이를 미분합니다. (gradient descent 계산) 그 결과는 2번째 사진인데, log의 성질로 나누기를 빼기로 바꾸고 각각에 대해 미분을 해서 결과를 얻은 것을 볼 수 있습니다. 이 과정에서는 chain rules가 들어가는데 이는 아래의 ratsgo님의 블로그글로 다시 정리해보도록 하겠습니다.
위의 복잡한 과정을 거치고 나서 Word2Vec의 결과를 구하고, 이 결과를 시각적으로 도식화하면 비슷한 단어들은 비슷한 위치에 놓이게 됩니다.
Word2vec visualization - 비슷한 단어들이 뭉쳐있는게 보임.
위의 목적함수 sentence의 전체 loss를 최소화하는 값을 찾기 위해서는 미분해서 0이 되는 값을 알아야 합니다. 이를 구하기 위해서 Gradient Descent 경사 하강법이라는 방법을 이용합니다.
경사하강법의 식은 위와 같고 아래의 설명처럼 임의의 초기값에서 Learning step만큼 진행해가면서 최소값인지 아닌지를 확인하는 방법입니다.
Cost function을 Minimize하는 방법 - take a small step을 하면서 Minimum값을 찾음.
아래는 Word2Vec의 학습파라메터인 중심단어 벡터 업데이트 과정을 수식으로 정리한건데요, 저도 정리 용도로 남겨 두는 것이니 수식이 골치 아프신 분들은 스킵하셔도 무방할 것 같습니다. 중심단어 벡터의 그래디언트는 아래와 같습니다.
이렇게 구한 중심단어 그래디언트의 반대 방향으로 조금씩 중심단어 벡터를 업데이트합니다. (여기서 알파는 사용자가 지정하는 학습률=learning rate)
sampling을 이용하여 Gradient descent를 하는 방법.
하지만 J(세타)는 각각의 중심단어가 가지는 모든 주변단어에 대해 진행해야 하므로 계산량이 많습니다. ( Gradient Descent의 단점이 Loss Function을 계산할 때 전체 train set을 사용하여 많은 계산량을 필요로 함 ). 이를 보완하기 위해 Stochastic Gradient Descent(SGD)라는 방법을 사용합니다. SGD는 loss function을 계산할 때, 전체 데이터 대신 일부의 데이터에 대해서만 loss function을 게산하는 방법입니다. 장점으로는 계산량이 적고, 학습이 빠르고 local minimum에 빠지지 않고 학습될 수 있다는 장점이 있지만, 아래의 첨부한 성능이 좋지 못한 단점이 있습니다.
Gradient Descent Optimization Algorithms at Saddle Point
그래서 보통 SGD보다는 이를 개선한 다른 알고리즘을 많이 사용하는데 강의에서는 SGD를 사용했기 때문에 그대로 진행하겠습니다. 추가적으로 다른 Gradient Descent 알고리즘에 대해서는 다음의 링크에 잘 나와있으니 참고하시기 바랍니다. 아래의 알고리즘에서는 단순하게 아래의 코드를 추가함으로서 SGD를 구현하였습니다.
window = sample_window(corpos)
하지만 window에 대해 SGD를 적용할 때, 문제가 있습니다. 우리가 가진 데이터가 매우 sparse 하다는 것 입니다. (sparse한 parameter을 업데이트해야 함.)
페이스북으로 질문 한 내용에 따르면 sparse matrix에서는 계산의 효율성 문제가 발생합니다. 실제는 2m+1의 단어만 가지고 있는데, 컴퓨터는 2dV짜리의 matrix를 주고 받아야 하기 때문입니다.
(질문) 안녕하세요. cs224n 강의에서 word2vec 부분을 보다가 막히는 부분이 있어서 질문드립니다. word2vec에서 stochastic gradients를 진행할때, 아래의 첫번째 그림처럼 gradients를 적용 한 결과가 sparse matrix입니다. 그래서 생기는 문제가 stochastic gradients는 특정 row만을 sampling해서 업데이트하는데 0값만 샘플링 되는 경우 업데이트가 되지 않는 다는 문제가 발생할 수 있게 됩니다. 강의에서는 이를 해결하기 위해서 아래의 두번째 그림처럼 Solution: either you need sparse matrix update operations to only update certain rows of full embedding matrices U and V, or you need to keep around a hash for word vectos라고 방법을 제시해주는데, 강의를 돌려봐도 무슨 뜻인지 이해가 잘 가지 않아서 질문드립니다 ㅠㅠ... (답변1) Sparse matrix 때문에 생기는 문제는 말씀하신 부분이 아니라 계산의 효율성 문제라고 생각됩니다. SGD로 단순하 계산을 하면 2dV 크기의 gradient matrix가 나오고 이를 원래 matrix에 빼주는 식으로 parameter update를 하게 되는데요, 실제로 이 안에서 update 해야하는 파라미터 수는 example 하나당 많아봤자 d(2m+1)개이기 때문에 이렇게 계산하는게 비효율적이라는 거죠. 특히 distributed computation으로 계산을 하는 경우에는 계산하는 워커와 파라미터 서버가 gradient matrix 계산한 것을 주고받아야 하는데, 2dV짜리 matrix를 주고받는 것은 V가 큰 경우에 너무 비효율적입니다.이를 해결하기 위해 단순하게 gradient matrix 전체를 계산해서 빼는 것이 아니라, 실제로 등장한 row들만 gradient를 계산하고, sparse한 matrix add / substraction으로 gradient를 update하는 방법으로 원래 SGD의 비효율성을 해결할 수 있다는 것이 요지입니다.여기 쓰여진 내용만으로는 'keep around a hash for word vectors'가 무슨 의도로 쓰여진지는 잘 모르겠네요. Hashing trick을 의도한것인지.. (답변2) NLP 처럼 feature rich 문제를 다룰때 발생하는 sparsity 에 대해 2가지 접근방법을 생각할수 있습니다. 직관적인 방법으론 feature index map (즉 feature 와 숫자의 mapping) 를 운영하는 방법이고, 다른 방법은 feature 를 hashing 하는 방법입니다. 예를들어 X 가 어떤 feature 들로 구성되었는지에 대해 각 feature 마다 유/무 (0/1) 상태를 나타낸다고 할때, 0/1 을 fea ture 갯수만큼 기록하지 않고, 1 값을 가진 feature 들의 index 들을 기록하는 방법이 첫번째 방법입니다. X 가 가질수 있는 feature 의 갯수가 전체 feature 의 갯수에 비해 아주 작다면 효율적인 방법입니다 - 문장이 가진 단어수와 사전 전체 단어수 처럼. 문제는 미리 feature index map (즉 사전) 을 구성해야하고, 그것에 없는 feature 가 나중에 관찰될 경우, map 을 update 해야하는 번거로움이 생깁니다.두번째 방법은, feature 를 제한된 숫자로 변환해 주는 함수를 사용하는 방법인데 이를 hash embedding 이라고 합니다. 여기서 hash 란 python dict 가 사용하는 hash 와는 다른 일반적인 hash 로 1-to-1 일 필요가 없습니다 — blockchain 에 쓰이는 hash 와 같은 개념입니다. 문제는 두개의 feature 가 같은 값을 갖게되는 경우인데 (collision), 보통 hash 를 잘 design 하면 collision 확률이 0 에 가까워서 큰 문제는 없습니다. 장점은 미리 전체 feature 를 indexing 할 필요도 없고 새로운 feature 를 처리하는 것도 용이합니다. 모든 X 를 max hash 길이의 vector 로 나타내어 shaping 하기도 용이하죠. hash embedding 은 종류가 여러가지고 계속 개발진행중입니다. 그중 Bloom embedding 은 NLP 에서 자주 사용됩니다. spaCy.py 처럼 NLP 특화된 module 들에서는 여러가지 hash embedding 을 쉽게 구현할수 있습니다.
Word2vec에서는 SGD말고도 효율성을 높이기 위해서 2가지 방법을 사용합니다. 아래의 내용은 ratsgo's blog의 내용을 인용하였습니다.
subsampling frequent words
Negative sampling
subsampling frequent words
Word2Vec의 파라미터는 앞서 설명한대로 W, W' 입니다. 각각 크기가 V x N, N x V 인데요. 보통 말뭉치에 등장하는 단어수가 10만개 안팎이라는 점을 고려하면 N(임베딩 차원수, 사용자 지정값)이 100차원만 되어도 2000만개(2 x 10만 x 100)나 되는 숫자들을 구해야 합니다. 단어 수가 늘어날 수록 계산량이 폭증하는 구조입니다. 이 때문에 Word2vec 연구진은 말뭉치에서 자주 등장하는 단어는 학습량을 확률적인 방식으로 줄이기로 했습니다. 등장빈도만큼 업데이트 될 기회가 많기 때문입니다. ( 자주 등장하는 단어는 어차피 다시 나타날 것이니깐 일정확률 학습에서 제외시켜버림 ) Word2vec 연구진은 i번째 단어(wi)를 학습에서 제외시키기 위한 확률을 아래와 같이 정의했습니다.
위 식에서 f(wi)는 해당 단어가 말뭉치에 등장한 비율(해당 단어 빈도/ 전체 단어수)를 말합니다. t는 사용자가 지정해주는 값인데, 연구팀에서는 0.000001을 권하고 있습니다.
만일 f(wi)가 0.01로 나타나는 빈도 높은 단어는 위 식으로 계산한 p(wi)가 0.9684로 높아서 100번의 학습 기회 가운데 96번 정도는 학습에서 제외하게 됩니다. 반대로 등장 비율이 적어 p(wi)가 0에 가깝다면 해당 단어가 나올 때마다 빼놓지 않고 학습을 시키는 구조입니다.
Negative sampling
Word2Vec은 출력층이 내놓는 스코어값에 소프트 맥스 함수를 적용해 확률값으로 변환한 후 이를 정답과 비교해 역전파(backpropagation)하는 구조입니다. 그런데 소프트맥스를 적용하려면 분모에 해당하는 값, 즉 중심단어와 나머지 모든 단어의 내적을 한 뒤, 이를 다시 exp를 취해줘야 합니다. 보통 전체 단어가 10만개 안팎으로 주어지니깐 계산량은 어마어마해집니다.
이 떄문에 소프트맥스 확률을 구할 때, 전체 단어를 대상으로 구하지 않고 일부 단어만 뽑아서 계산을 하게 되는데요. 이것이 바로 negative sampling입니다. negative sampling은 학습 자체를 아예 스킵하는 subsampling과는 다르다는 점에 유의하셔야 합니다.
negative sampling의 절차는 이렇습니다. 사용자가 지정한 윈도우 사이즈 내에 등장하지 않는 단어(negative sample)를 5~20개 정도 뽑습니다. 이를 정답단어(윈도우 사이즈 내에 등장한 단어)와 합쳐 전체 단어처럼 소프트맥스 확률을 구하는 것입니다. 바꿔 말하면 윈도우 사이즈가 5일 경우 최대 25개 단어를 대상으로만 소프트맥스 확률을 계산하고, 파라미터 업데이트도 25개 대상으로만 이뤄진다는 이야기입니다.
윈도우 내에 등장하지 않은 어떤 단어(wiwi)가 negative sample로 뽑힐 확률은 아래처럼 정의됩니다.
출처 : 파리의 언어학도 블로그 (https://blog.naver.com/jujbob/221155564430)
참고로 subsampling과 negative sampling에 쓰이는 확률값들은 고정된 값이기 때문에 학습을 시작할 때 미리 구해놓게 됩니다.
원문 : 파리의 언어학도 블로그 (https://blog.naver.com/jujbob/221155564430) 그렇다면 오른쪽의 negative sampling쪽 수식이 의미가 뭘까? 자세히 쪼개서 살펴보자. 일단 log시그마 연산을 떠올려보면 sigmoid 함수 자체가 반환하는 값이 0~1사이 값이기 때문에 log0~1사이가 된다. 바꿔 말하면 sigmoid함수를 통해 나온 값이 클수록, 다시말해 Uo^tVc값이 크면 J는 0에 가까워진다. 반대로 시그모이드(-uj^tVc)는 오답쌍에 대한 연산으로 볼수있는데 음수를 곱하기 때문에 Uo^tVc와는 반대로 연산될것이다. 얼추 감이 오지 않는가? center word(vc)와 context word(Uo^t)가 같이 나올 확률이 높으면 손실값 J는 0에 가까워지고, 반대로 랜덤으로 단어쌍이 나올확률이 낮으면 또한 J는 0과 가까워진다. 그렇다면 오답쌍 후보들(j~P(w))는 어떻게 뽑을까? 위 그림 오른쪽에 나와 있는 것처럼 U(W)^(3/4)/Z 형식의 수식을 사용하는데, 여러가지 방법이 있으나 논문에 소개 된 내용을 간략하게 이야기 하면 문장에 글로벌하게 자주 출몰하는 is와 같은단어는 실제 출현을 자주 하니깐 오답쌍 후보로 뽑으면 안되고 자주 출몰하지 않는 단어를 더 잘 뽑기위한 방법중 하나로 저런 수식을 사용했다.
Glove Model
아래부터의 내용은 window의 size를 주변 단어로만 인식하는지, 아니면 문서 전체로 인식하는지에 대한 내용입니다. window size를 늘리면 늘릴수록 각 단어는 global하게 자주 출몰하지 않는 몇개의 핵심단어에 의해 구별이 될 것입니다. 하지만, 아무리 window size를 늘린다고 해도, skipgram은 전체 단어의 동반출현 빈도수와 같은 통계 정보를 내포하지 못합니다. 이러한 정보를 global co-occurrence statistics라고 합니다. global co-occurrence statistics정보를 구하는 다른 방식은 count-based matrix를 만드는 방법입니다. 주로 해당 matrix를 만든 뒤 SVD, LSA, HAL, LSI등의 방법을 통해서 차원을 축소해서 사용합니다. 그렇지 않으면 차원이 너무 크기 때문입니다.
window의 경우, word2vec과 매우 유사하며 syntatic (POS) 와 잠재적인 정보를 잡을 수 있습니다. 좀 더 작은 범위인 단어간의 유사도(문법, 의미)를 파악하는 장점이 있다.
document의 경우, "Latent Semantic Analysis (LSA)" (잠재적 의미분석)이라는 주제로 넘어가게 됩니다. 전체적인 통계 정보를 내포하는데 유리.
예를들어, 오른쪽 그림의 예시에서 Window size를 1로 잡았을 때, co-occurrence matrix는 아래와 같습니다. I like가 2문장에서 나왔기 때문에 2의 값을 가지고, 그렇지 않은 값들은 1과 0을 가지고 있습니다.
하지만 co-occurrence vectors에 대해서도 문제가 있습니다. vocabulary size가 증가함에 따라 차원이 크게 커지게 되고, 저장공간을 많이 필요로 합니다. 그리고 위의 예를 보면 알겠지만 sparsity의 문제점도 가지고 있습니다. 이러한 문제를 해결하기 위해서 우리는 차원을 low하게 만들 필요가 있습니다.
그 방법으로 제시된것이 Singular Value Decomposition(특이값 분해) - SVD입니다. SVD의 자세한 설명은 다음의 링크1과 링크2에나와있으니 먼저 읽고 아래의 내용을 읽기 바랍니다. 간단한 내용은 ratsgo's 블로그의 아래 사진과 같습니다. 참고로 SVD의 출력값은 A행렬에 U의 전치행렬을 곱한 값과 같습니다.
Glove 모델은 이름에서 알 수 있듯이 앞서 설명한 global co-occurrence statistics 정볼르 포함한 direct prediction word embedding이라고 생각하면 된다. 한마디로, 전체적인 통계정보 + skipgram과 같은 direct prediction방식의 장점을 모두 가졌다. 학습 순서는 다음과 같다.
출처 : 파리의 언어학도 블로그
하지만 Xij의 값이 상대적으로 너무 커서 학습에 효과적이지 못하기 때문에 normalization을 해주기 위해 log를 전체적으로 추가한 수식이 바로 위 맨 왼쪽의 수식이다. 마지막으로 Xj는 가중치값으로 불 수 있는데, 이 값의 편차가 너무 커지면 이 또한 is, the와 같이 문서에 전체적으로 자주 출몰하는 단어들이 gradient update에 너무 많은 영향을 미칠 수 있기 때문에 이 값을 조정하기 위해 Xi를 함수 f(Xij)형태로 바꾼것이 위의 오른쪽 최종적인 손실함수가 된다. 논문에서는 최대값 X를 넘으면 같은 가중치를 가지도록 가중치 최대값을 조정했다.
Word embedding evaludation
일단 word embedding을 학습 시킨 이후에 우리는 어떤 모델이 좋은 모델인지 평가를 해야한다. 크게 두 가지 방법이 있는데 표에서 보는 것 처럼 내적(intrinsic) vs 외적(extrinsic)평가로 나눌 수 있다. 내적 평가는 word embedding만 가지고 평가하고 외적 평가는 word embedding을 활용해 다른 NLP시스템에 적용해 그 시스템의 성능을 평가한다.
평가분류
정의
방법
Intrinsic(내적)
only word embedding만을 이용해 내부 단어간의 유사도를 통해 평가함
1. Human judgement평가 : 사람이 직접 평가데이터를 만듬. 주로 두 단어의 유사도를 직접 점수 매김
2. Semantic(의미), syntatic(문법)을 평가함 : word2vec논문에서 소개된 데이터셋을 기준으로 cosine similarity를 평가함. (e.g 여러 captial-country 쌍의 결과들이 얼마나 비슷한가?)
extrinsic(외적)
실제 문제에 직접 적용하여 성능을 평가
각종 자연어처리 system에 embedding을 직접 사용하여 시스템의 성능을 측정. NER(개체명 인식기)가 대표적.
그렇다면 내적 평가에서 유사도 평가는 어떻게 할까? word embedding은 결국 vector이기 때문에 vector간의 유사도라 하면 코사인 유사도나 벡터간의 거리를 게산하는 유클리디안 거리를 사용한다. 즉, 예를들어 위의 표에서 설명한 수도-국가의 예제처럼 아래 그램 오른쪽에 나오는 max:woman :: king: d? 에서 최대값을 가지는 후보 d를 찾아 d의 정답인 queen을 찾는 형식으로 진행된다. 바꿔 말해 king - man + woman = queen 이게 어떻게 가능할까? 바로 분석해보자
Word embedding은 어떻게 의미와 문법정보를 내포할까?
아래 그림을 보며 설명하겠다. 우리는 앞서 word embedding을 학습시킬 때, 중심단어 C와 주변단어들 O를 활용했다. king의 주변어 royal, family, emperor 등이 예상되고 이런 단어는 마찬가지로 queen의 주변단어로 자주 등장할 것이다. 하지만 king과 queen을 구분할 수 있는 주변단어 O가 몇가지 있을 수 있는데, 아마 다음과 같은 문장들로부터 파생 될것이다. "the king was a man", "the queen was a woman" 또한 king은 man과 가까운 단어 he랑도 자주 등잘할 것이다. "he will be a man", "he will be a king", "he will be a uncle" 이처럼 중심어 king은 man, he, uncle과 문법적 그리고 의미적으로 woman, she보다 주변 단어 O가 비슷하다는 이야기이다. (물론 "she is the wife of the king"과 같은 문장이 나올 수 있으나 상대적으로 생각해야 한다.) 결과적으로, word embedding은 위에서 설명한 의미적 문법적 정보를 단어의 동반출현 빈도를 통해 상대적으로 학습한다. 아래 그림에 나오는 "royalty"와 같은 class정보는 이러한 단어의 동반 출현빈도에 따라 자동을 구분된 것이다.
그렇다면 실제 학습된 데이터의 모양은 어떨까? 위에 설명한 것처럼 서울-한국, 도쿄-일본 연산은 서로 비슷한 형태의 벡터(방향 및 크기)를 가지게 될까? 아래 그림을 보자. 왼쪽이 semantic 오른쪽이 syntatic의 예제이다.
위의 사진은 논문(Combining the best of both worlds GloVe [Pennington et al., EMNLP 2014]) 에서 Glove의 평가를 한 자료이다. dimension의 경우 ~300에서, window size는 8 근방이 가장 성능이 좋았고, 왼쪽방향으로만의 window는 성능이 좋지 않았다.
참고로 다른 논문 On the Dimensionality of Word Embedding [ZiYin and YuanyuanShen, NeurIPS2018]에서는 많은 단어들이 많은 의미들을 가지고 있는 것을 지적한다.
