Efficient Estimation of Word Representations in Vector Space

[chullhwan-song]

https://arxiv.org/abs/1301.3781 시차를 두고 여기저기 붙이다보니 두서없이 써놓은 경향이 있음.

[chullhwan-song]

Abstract

• 연속적인 단어에 대한 재표현할수 있는벡터을 계산할수 있는 2가지 새로운 방법을 제시
• 이들 재표현된 벡터의 퀄리티의 측정방법은 word 유사성 task에서
• 이 방법으로 이전다른 방법과 비교하여 best performance
• 학습속도도 빠르게
• 자기네들이 최신 데이터셋도 제공

  Introduction

• 현재 많은 NLP 시스템 및 기술들은
  • word를 하나의 작은 단위로 취급
  • voc의 index로 치환
  • word사이의 유사성관련 notion은 들어가지 않음.
  • 위의 선택하는 이유는 simplicity, robustness, observation
    • simple models trained on huge amounts of data outperform complex systems trained on less data.
  • 이러한 대표적 방법은 N-gram이다. (통계학적인 언어 모델링을 위해 많이 사용)
• 위의 설명과 같이 대용량의 데이터로 가지고 단순한 모델로 학습한 모델이 위의 제시된 모델보다 훨씬 좋음.
• 이 논문에서,
  • 수십억의 단어와 어휘집에 존재하는 수백만의 단어들로 이루어진 매우 많은 데이터로 부터 높은 수준의 단어 벡터 학습을 하는 기술 소개
  • 어떤 이전의 논문들도 단어 벡터의 차원을 보통의 50- 100 차원으로하며, 수백만의 단어보다 많은 데이터를 이용해 성공적으로 훈련하지 못했음.
  • 가까운 (비슷한) 단어들의 근접성 & 단어가 다수의 유사도(multiple degrees of similarity)를 갖도록함.
    • 굴절어(라틴어 등등)의 문맥에서 먼저 관측
    • 예를 들어, 유사한 단어를 찾을때, 명사는 다양한 어미를 가지는데, 비슷한 어미를 갖는 단어들이 나올수 있다. 이게 유사한 단어인가?
    • 제시한 방법은 이러한 문제점을 뛰어넘는 '유사도를 발견할수 있음.
    • 단어 간격 기술을 이용해 단어 벡터의 대수적 연산(algebraic operations are performed on the word vectors)을 실행 > ‘King’ - ‘Man’ + ‘Woman’ = ‘Queen’

      Model Architectures

• "continuous representations of word"에 대한 이전 잘알려진 방법중에는 Latent Semantic Analysis (LSA) ,Latent Dirichlet Allocation (LDA) 있음.
  • 이런 모델은 topic model이라고 해서, 이전 딥러닝 이전에 핫하게 연구되고 있었음. doc 이나 image안에 특정 latent를 예측하는 모델, 즉 topic 이라는 개념을 도입
  • 하지만, 이런 모델은 very expensive
• 따라서 우리는 "Strategies for Training Large Scale Neural Network Language Models" 연구와 비슷하게, 모든 학습된 모델에 대해 접근가능토록 "the number of parameters"를 계산하도록 정의한다.
  • computational complexity가 최소화하도록 시도하고, accuracy를 max가 되도록 한다.
  • 그래서, the training complexity를 다음과 같이 정의
    • E는 epochs, T는 training set의 word 수, Q는 모델 구조
    • epochs = 3`50, T는 1 billon
    • 모든 모델은 stochastic gradient descent & backpropagation 이용하여 학습

      구조

• 컴퓨터가 어떤 단어에 대해 인지할 수 있게 하기 위해서는 수치적인 방식으로 단어를 표현
  • problem) 수치화를 통해 단어의 개념적 차이를 나타내기가 힘듬
  • 이 한계를 극복하기 전, 많이 사용하는 방식이 "one-hot encoding"
  • 예) Naive Bayes를 이용한 스팸 분류기에 사용한 방식
  • 나름 좋은 성능을 내었고, 지금까지도 사용
  • 문제) 컴퓨터 자체가 ‘단어가 본질적으로 다른 단어와 어떤 차이점을 가지는 지 이해할 수가 없다’ 는 아주 큰 단점이 존재
  • 벡터화 - one-hot encoding 단점을 해결하기 위해 고안
  • 장점
    • 각 단어들 사이의 유사도를 측정
    • 여러 개의 단어에 대해 다룰 때도 더해서 평균을 내는 등 수치적으로 쉽게 다룰수 있음.
    • 의미 자체가 벡터로 수치화되어 있기 때문에, 벡터 연산을 통해서 추론을 내릴 수가 있다는 점
    • 추론 데모 : http://w.elnn.kr/search/
  • 방법
    • NNLM, RNNLM, CBOW, Skip-gram 등이 있음.
    • 이를 발전시켜 -> word2vec
    • Feed-Forward Neural Net Language Model (NNLM) : Neural Network 이용한 방법
    • Input Layer, Projection Layer, Hidden Layer, Output Layer 구성
    • 입력 - N개의 one hot vector, dictionary size : V -> 1개의 Vector는 V 차원
    • Projection Layer P이면, VxP(Projection Matrix) -> Hidden Layer 으로 넘기게된다.
      • 실제 역할은? dimension reduction 역할인가?
      • P 는 임의의 수인가?
      • 실제 INPUT 크기(?)
      • 그림에서는 그냥 합치는정도인데.ㅎ
• word2vec
  • Distributional_Hypothesis 개념하에서 이루어짐
  • 비슷한 분포를 가진 단어들은 비슷한 의미를 가진다란 개념
    • 여기서 비슷한 분포를 가졌다는 것은 기본적으로 단어들이 같은 문맥에서 등장한다는 것을 의미
  • 대표적인 방법
  • CBOW(Continuous Bag-of-Words)
    • only one word에 대한 CBOW 모델
    • V : vocabulary(dictionary) size
    • N : hidden layer size
    • W : input layer와 hidden layer 사이의 weight = VxN
    • input/hidden/output layer로 구성
    • hidden layer는 projection layer에 더 가까움
      • why?) weight를 곱해주는 layer가 아닌, 단순히 projection 역할에 더 가깝기 때문
    • C -> CxN -> NxV
      • C : 단어
      • N : Hidden layer의 크기
      • V : 사전의 크기
    • 이전방법보다 엄청나게 계산량을 줄임.
      
    • multi-word에 대한 CBOW 모델
    • when computing the hidden layer output,
      • instead of directly copying the input vector of the input context word,
      • the CBOW model takes the average of the vectors of the input context words
  • Skip-gram
    • CBOW모델의 반대
    • 현재 주어진 단어 하나를 가지고 주위에 등장하는 나머지 몇 가지의 단어들의 등장 여부를 유추하는 것.
    • Skip-gram이 CBOW에 비해 전체적으로 다소 좋은 결과를 내는 추세
• ref
  • http://solarisailab.com/archives/374
  • hword2vec 관련 이론 정리 : 링크
  • https://medium.com/@jameschen_78678/social-behavior-analytics-201-523199badba0

[chullhwan-song]

others 1 : Skip-Gram model > 텐서플로우(TensorFlow)를 이용해 자연어를 처리하기(NLP) – Word Embedding(Word2vec)

• http://solarisailab.com/archives/374
• Noise-Contrastive 트레이닝를 이용한 Scaling Up
  • 이전의 히스토리 h (“history”)가 주어졌을때 다음에 이어지는 목표 단어 w_t (“target”)의 확률을 최대화하기 위해서 소프트맥스 함수를 사용한다. 현재 콘텍스트 h에서 단어 w_t의 적합성을 나타낸다. (보통 내적을 이용한다.) 우리는 학습셋에서 log-likelihood를 최대화하는 방향으로 학습을 진행, 즉, 아래의 식을 최대화
  • 이런 모델은 언어 모델링(language)을 위한 적당히 정규화된 확률 모델(normalized probabilistic model)을 산출
  • 하지만 이 모델은 계산 비용이 매우 크다. 왜냐하면 모든 트레이닝 스텝에서, 현재 콘텍스트 h에서 어휘(Vocab)에 포함된 모든 단어 w’에 대한 확률을 계산하고 정규화해야하기 때문이다.
  • 이에 반해, word2vec을 이용한 특징 학습(feature learning) 방법에서는 전체 확률 모델이 필요하지 않다.
  • CBOW와 skip-gram 모델은 이진 분류 (binary classification) 방법(로지스틱 회귀분석-logistic regression)을 이용
  • 같은 콘텍스트에서 k개의 상상의 (noise) 단어 ~w와 진짜 타겟 단어 w_t를 식별
  • 는 데이터셋 D에서 콘텍스트 h에서 관찰한 단어가 w일 이진 로지스틱 회귀분석에서의 확률이다. 이는 학습된 embedding vectors theta 를 이용해서 계산(즉, 몬테 카를로 평균을 계산한다.)
  • 이 목적함수는 모델이 실제 단어에는 높은 확률을 부여하고 노이즈 단어들에는 낮은 확률을 부여하면 최대화
  • 기술적으로, 이런 방법을 Negative Sampling
  • 계산 비용의 측면에서, 이런 방식은 매우 효율적이다.
    • 왜냐하면 전체 어휘 V를 계산하는 것이 아니라 우리가 선택한 k개의 noise 단어들만 계산하면 되기 때문
  • noise-contrastive estimation (NCE) 손실 함수를 사용할 것 > tf.nn.nce_loss() 함수를 이용 (이거 사용한다는 말을 하려고.ㅠ)

[chullhwan-song]

others 2 : https://shuuki4.wordpress.com/2016/01/27/word2vec-%EA%B4%80%EB%A0%A8-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC/ 읽으면서 정리

dict 크기 즉, 단어가 아주 많을때는 어떻게 처리하는 방법이 따로 있는가?

• CBOW와 Skip-gram 모델을 그대로 구현해서 돌릴 경우 생각보다 학습이 오래 걸리는 것을 확인할 수 있을 것
  • 즉, 사전의 크기가 엄청나게 크면 문제가 생김.
  • 디테일하게 가면, Output Layer에서 Softmax 계산를 위해 전체 단어를 위해 normalized 계산을 하게되어 계산량이 엄청나게 많아짐.
  • 이런한 방법을 해결하기 위한 방법이 바로 Hierarchical Softmax vs Negative Sampling\

dict 크기 즉, 단어가 아주 많을때는 어떻게 처리하는 방법이 따로 있는가?

• Hierarchical Softmax
  • 빠르게 계산가능한 multinomial distribution function
    • 각 단어들을 leaves로 가지는 binary tree를 하나 만들어놓은 다음, 해당하는 단어의 확률을 계산할 때 root에서부터 해당 leaf로 가는 path에 따라서 확률을 곱해나가는 식으로 해당 단어가 나올 최종적인 확률을 계산
    • L(w)는 w라는단어가 leaf에 도달하기 까지의 path의 길이를 의미
    • n(w, i) : w라는 leaf에 도달하는 path에서, i번째 노드를 의미 예를 들어, n(w, 1)은 루트이고, n(w, L(w))는 w가 된다.
    • ch(node): node의 고정된 임의의 한 자식을 의미, 여기서는 단순하게 node의 왼쪽 자식이라고 생각해도 무방.
    • [[x]] 는 x가 true일 경우 1, false일 경우 -1을 반환하는 함수
    • Hierarchial Softmax를 사용할 경우 기존 CBOW나 Skip-gram에 있던 W’ matrix를 사용하지 않게 된다. 대신, V-1개의 internal node가 각각 길이 N짜리 weight vector를 가지게 된다. 이를 v’_i 라고 하고 학습에서 update 해준다.
    • h는 hidden layer의 값 벡터
    • sigma(x)는 sigmoid function 1/(1+exp(-x))
  • 위의 식 p(w)를 계산한다면,
    • 각 스텝마다 길이 N짜리 벡터 두 개의 내적이 일어나므로 계산량 N이 필요
    • binary tree는 평균적으로 루트로부터 leaf까지의 거리는 평균 O(lnV) 그래서, N번시도한다면, 총 N x lnV의 계산량만으로 특정 단어가 나올 확률을 계산
    • 네트워크의 Error Function을 Categorical Cross-entropy 로 사용할 경우(뜬금없이 이런단어가 나와서 이해안가지만) , 최종 Error를 계산하기 위해서 해당하는 단어에 대해서만 확률을 계산하면 되므로, 다른 추가적인 연산 없이 O(N x lnV)의 계산량만으로 계산이 끝난다.
    • 특정 hidden layer 값에 대해 모든 단어들의 확률을 더한 sigma p(w_i | hidden layer) 를 생각
      • v_node와 h의 내적 값을 x 라고 하고
      • 특정 node에서 왼쪽 자식으로 갈 때의 확률 = sigmoid(x)
      • 특정 node에서 오른쪽 자식으로 갈 때의 확률 = sigmoid(-x) = 1-sigmoid(x)
      • 특정 노드에서 왼쪽, 오른쪽 자식으로 갈 확률을 더하면 1(sigmoid(x)+1-sigmoid(x)) 이를 이용하면, sigma p(w_i | hidden layer) 값이 1 (?? 모든 단어의..가 빠진듯것이 아니라 위의 식에서 볼때, 그 step에서의..)
      • softmax function의 계산이 오래 걸렸던 것은 확률 계산을 위해 모든 결과에 대한 합을 1로 만들어주기 위함
      • 이 과정에서 최종적으로 나온 output값에 대해 일일히 계산을 해주어서 전체 합으로 normalize를 해주었기 때문에 V 만큼의 계산이 더 필요했던 것
      • Hierarchical Softmax를 사용하면 전체 확률에 대한 계산 없이 전체 합을 1로 만들어 줄 수 있어 좋은 multinomial distribution function으로 사용할 수 있게 되는 것
      • word2vec 논문에서는 이러한 Binary Tree로 Binary Huffman Tree를 사용했다고 한다. Huffman Tree를 사용할 경우 자주 등장하는 단어들은 보다 짧은 path로 도달할 수 있기 때문에 전체적인 계산량이 더 낮아지는 효과를 볼 수 있을 것이다. 또한 Huffman Tree는 Full Binary Tree이기 때문에 Hierarchical Softmax의 조건에도 부합

빈도가 아주 많은 단어 와 빈도가 극히 낮은(=1정도)단어들은 어떻게 전처리를 할까?

• Hierarchical Softmax와 Negative Sampling은 모델 자체의 계산복잡도를 줄이기 위한 테크닉이었다. 여기서 추가적인 방법으로, 논문에서는 ‘the’, ‘a’, ‘in’ 등 자주 등장하는 단어들을 확률적으로 제외하여 학습 속도를 향상시켰을 뿐만 아니라 성능까지 향상시켰다. 단어 w의 등장 빈도를 f(w)라고 할 때, 학습할 때 각 단어는
  • 의 확률로 제외된다. 이 때 t는 빈도가 일정값 이상일 때만 제외하겠다는 느낌의 threshold 값인데, 논문에서는 t = 10^-5 의 값을 사용했을 때 가장 좋은 결과를 얻을 수 있었다고 한다.