{"id":252,"date":"2014-10-27T21:54:53","date_gmt":"2014-10-27T21:54:53","guid":{"rendered":"http:\/\/www.marekrei.com\/blog\/?p=252"},"modified":"2019-09-27T23:36:30","modified_gmt":"2019-09-27T23:36:30","slug":"linguistic-regularities-word-representations","status":"publish","type":"post","link":"https:\/\/www.marekrei.com\/blog\/linguistic-regularities-word-representations\/","title":{"rendered":"Linguistic Regularities in Word Representations"},"content":{"rendered":"

In 2013, Mikolov et al. (2013) published a paper showing that complicated semantic analogy problems could be solved simply by adding and subtracting vectors learned with a neural network. Since then, there has been some more investigation into what is actually behind this method, and also some suggested improvements.\u00a0This post is a summary\/discussion of\u00a0the paper “Linguistic Regularities in Sparse and Explicit Word Representations<\/a>“, by Omer Levy and Yoav Goldberg, published at ACL 2014.<\/p>\n

The Task<\/h2>\n

The task under consideration is analogy recovery. These are questions in the form:<\/p>\n

a<\/em>\u00a0is to b<\/em>\u00a0as c<\/em>\u00a0is to\u00a0d<\/em><\/strong><\/p>\n

In a usual setting, the system is given words a, b, c<\/em>, and it needs to find d<\/em>. For example:<\/p>\n

‘apple’<\/em> is to ‘apples’<\/em> as ‘car’<\/em> is to ?<\/em><\/strong><\/p>\n

where the correct answer is ‘cars’<\/em>. Or the\u00a0well-known\u00a0example:<\/p>\n

‘man’<\/em> is to ‘woman’<\/em> as ‘king’<\/em> is to ?<\/em><\/strong><\/p>\n

where the desired answer is\u00a0‘queen’<\/em>.<\/p>\n

While methods such as relation extraction would also be completely reasonable approaches to this problem, the research is mainly focused on solving it by using vector similarity methods. This means we create vector representations for each\u00a0of the words, and then use their positions in the high-dimensional feature space to determine what the missing word should be.<\/p>\n

<\/p>\n

Vector Spaces<\/h2>\n

As the first step, we need to create feature vectors for each word in our vocabulary. The two main ways of doing this, which are also considered by this paper, are:<\/p>\n

    \n
  1. BOW<\/strong>: The bag-of words approach. We count all the words that a certain word appears with, treat the counts as features in a vector, and weight them using something like positive pointwise mutual information (PPMI).<\/li>\n
  2. word2vec<\/strong>: Vectors created using the word2vec<\/a> toolkit. Low-dimensional dense vector representations are learned for each word using a neural network.<\/li>\n<\/ol>\n

    If you want to learn more details about these models, take a look at an earlier post about comparing both of these models<\/a>.<\/p>\n

    Analogy Artihmetic<\/h2>\n

    We have the vectors, but how can we find the correct words in the analogy task?<\/p>\n

    The idea of\u00a0Mikolov et al. (2013) was that the vector offset of vectors should reflect their relation:<\/p>\n

    \\(a – b \\approx c – d\\)
    \n\\(man -woman \\approx king -queen\\)<\/p>\n

    We can rearrange this to find d<\/em>:<\/p>\n

    \\(d \\approx c – a +b\\)
    \n\\(queen \\approx king -man +woman\\)<\/p>\n

    Therefore, we can calculate the vector for\u00a0\\(c – a + b\\), compare it to the vectors of all words in our vocabulary, and return the highest-scoring word as the answer.<\/p>\n

    \\(d_w =\u00a0arg max_{d_w’ \\in V}(cos(d’, c – a +b))\\)<\/p>\n

    I’m using \\(d_w\\) here to denote the actual word, whereas the \\(d\\) stands for the vector representation of \\(d_w\\). \\(V\\) is our whole vocabulary. \\(cos()\\) is the cosine similarity between two vectors.\u00a0Let’s refer to this as the addition<\/strong>\u00a0method.\"regularities_equation\"<\/p>\n

    An alternative to this is to consider the directions of the offset directly. We find the word that has the most similar offset (in terms of direction), compared to the offset of the sample words.<\/p>\n

    \\(d_w =\u00a0arg max_{d’_w \\in V}(cos(a – b, c – d’))\\)<\/p>\n

    It only looks at the direction of the relational step, ignoring the actual magnitude of this step. We’ll see later that sometimes this is good, sometimes not so much. We’ll refer to this method as direction<\/strong>. Apparently this method was actually used by Mikolov in some experiments, although it wasn’t included in the paper.<\/p>\n

    Now onto the modification proposed by Levy & Goldberg (2014). The addition\u00a0method basically looks for a word that is similar to c<\/em> and b<\/em>, and not similar to a<\/em>, with each contributing\u00a0equally. This can lead to cases where one large term dominates the equation, especially if the magnitudes of the similarities are very different. Therefore, the authors have proposed that instead of adding these similarities, they could be multiplied:<\/p>\n

    \\(d_w =\u00a0arg max_{d’_w \\in V}\\frac{cos(d’, c) cos(d’, b)}{cos(d’, a) + \\epsilon}\\)<\/p>\n

    If the vectors are normalised (unit length), then this formula actually becomes a multiplication of their scalar products:<\/p>\n

    \\(d_w =\u00a0arg max_{d’_w \\in V}\\frac{(d’\u00a0\\cdot c) \\times (d’\u00a0\\cdot\u00a0b)}{(d’\u00a0\\cdot\u00a0a) + \\epsilon}\\)<\/p>\n

    \\(\\epsilon\\) is set to 0.001 to avoid division by zero. Also, the formula doesn’t handle negative similarity scores, whereas cosine (and the scalar product) can be negative. Therefore, the values are transformed into a positive range by doing \\(x_{new} = (x + 1)\/2\\). We’ll\u00a0refer to this as the\u00a0multiplication<\/strong>\u00a0method.<\/p>\n

    Evaluation<\/h2>\n

    The alternative methods are evaluated on the task of analogy recovery, using three different datasets:<\/p>\n

      \n
    1. The MSR dataset<\/a> containing 8,000 analogy questions.<\/li>\n
    2. The GOOGLE dataset<\/a> with 19,544 analogy questions.<\/li>\n
    3. The SEMEVAL dataset<\/a>, covering 79 distinct relation types.<\/li>\n<\/ol>\n

      In the MSR and GOOGLE datasets, the system needs to find the correct answer from an open vocabulary. In contrast, the SEMEVAL task provides candidates for each relation that need to be reranked. Accuracy is used as the evaluation metric on all datasets.<\/p>\n

      The word vectors were trained on 1.5 billion words of English Wikipedia. The vocabulary was restricted to contain only words that occurred at least 100 times in the corpus, resulting in 189,533 words.<\/p>\n

      Results<\/h2>\n

      \"regularities_results\"<\/a><\/p>\n

       <\/p>\n

      Some observations based on the results:<\/p>\n