Basics

Meaning

  • Definition Webster dictionary: Idea represented by a word
  • WordNet
    • Encode meaning for computer
    • Synonym/hypernym set
    • Hand-crafted
    • Problem:
      • Subjective
      • Missing new meanings
  • Idea: Represent words as vectors

Word vectors

  • One-hot vectors:
    • Vector over complete vocabulary
    • Problem: Orthogonal vectors / no natural similarity
    • No context
    • Solution: Encode similarity in vectors/add context
  • Context:
    • Words meaning given by the word co-occurring with it (J. R. Firth)
    • Use word vector/word embedding/word representation

Word2Vec

  • Mikolov et al., 2013
  • Idea:
    • Use context/surrounding words for word vectors
    • Use similarity of center word and context words
    • Calculate probability of context word given a center word
    • Maximize probability (on large text corpus)
    • \( P(w_{t+1}\mid w_t) \)
  • Model variants
    • Skip-gram (predict context outside words with center word, independent of order)
    • Continuous Bag-of-words (CBOW, predict center word from bag-of-words)

Objective function

  • Skip-gram model
  • Likelihood: \( L(\theta) =\Pi_{t=1}^T \Pi_{-m \leq j \leq m, j \neq 0} P(w_{t+j}\mid w_t;\theta) \)
  • Objective function:
    • Minimize average negative log likelihood
    • \( J(\theta) = - \frac{1}{T} \log L(\theta) \)
  • \( \Theta \): Model parameter
    • \( \theta \in \mathbb{R}^{2\cdot d \cdot V} \)
    • Each word has two vectors

Calculation

  • Skip-gram model, naive softmax
  • Each word gets two vectors (as context and center word)
    • Use \( v_w \) if \( w \) is center word
    • Use \( u_w \) if \( w \) is context word
    • Reason: Simpler computation
  • Additional efficiency: Negative sampling
    • Naïve softmax simpler, but expensive
    • Binary logistic regression
    • Sample negative words
  • Minimize objective function / maximize probability
  • Probability
    • \( P(o\mid c) = \frac{exp(u_o^T v_c)}{\sum_{w\in V} exp(u_w^T v_c)} \)
    • \( o \): Context word (outside)
    • \( c \): Center word
    • Probability distribution (example of softmax function)
  • Gradient derivation
    • \( \frac{\partial}{\partial v_c} \log P(o\mid c)= u_o - \sum_{x\in V} P(x\mid c) \cdot u_x \)

Optimization

  • Gradient descent: Move into direction of negative gradient
  • \( \theta_{\text{new}} = \theta_{\text{old}} - \alpha \nabla_\theta J(\theta) \)
  • Stochastic Gradient Descent:
    • Evaluate over sample window instead of complete corpus
    • Faster
    • Why?
    • \( \theta \) has \( 2m+1 \) vectors (therefore, very sparse)