{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/dbamman/anlp25/blob/main/3.embeddings/DistributionalSimilarity.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!wget --no-check-certificate https://raw.githubusercontent.com/dbamman/anlp25/main/data/wiki.10K.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook explores distribitional simliarity in a dataset of 10,000 Wikipedia articles (4.4M words), building high-dimensional, sparse representations for words from the distinct contexts they appear in.  These representations allow for analysis of the most similar words to a given query, and are interpretable with respect to the specific contexts that are most important for determining that two words are similar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict, Counter\n",
    "import math\n",
    "import operator\n",
    "import gzip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "window = 2\n",
    "vocab_size = 10000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filename = \"wiki.10K.txt\"\n",
    "wiki_data = open(filename, encoding=\"utf-8\").read().lower().split(\" \")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We'll only create word representation for the most frequent K words\n",
    "\n",
    "def create_vocab(data):\n",
    "    word_representations = {}\n",
    "    vocab = Counter(data)\n",
    "\n",
    "    top_k = [word for word, counts in vocab.most_common(vocab_size)]\n",
    "    for k in top_k:\n",
    "        word_representations[k] = defaultdict(float)\n",
    "    return word_representations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# word representation for a word = its unigram distributional context (the unigrams that show\n",
    "# up in a window before and after its occurence)\n",
    "\n",
    "def count_unigram_context(data, word_representations):\n",
    "    for i, word in enumerate(data):\n",
    "        if word not in word_representations:\n",
    "            continue\n",
    "        start = i - window if i - window > 0 else 0\n",
    "        end = i + window + 1 if i + window + 1 < len(data) else len(data)\n",
    "        for j in range(start, end):\n",
    "            if i != j:\n",
    "                word_representations[word][data[j]] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_directional_context(data, word_representations):\n",
    "    for i, word in enumerate(data):\n",
    "        if word not in word_representations:\n",
    "            continue\n",
    "        start = i - window if i - window > 0 else 0\n",
    "        end = i + window + 1 if i + window + 1 < len(data) else len(data)\n",
    "        left=\"L: %s\" % ' '.join(data[start:i])\n",
    "        right=\"R: %s\" % ' '.join(data[i+1:end])\n",
    "        \n",
    "        word_representations[word][left] += 1\n",
    "        word_representations[word][right] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# normalize a word representation vector such that its L2 norm is 1.\n",
    "# we do this so that the cosine similarity reduces to a simple dot product\n",
    "\n",
    "def normalize(word_representations):\n",
    "    for word in word_representations:\n",
    "        total = 0\n",
    "        for key in word_representations[word]:\n",
    "            total += word_representations[word][key] * word_representations[word][key]\n",
    "            \n",
    "        total = math.sqrt(total)\n",
    "        for key in word_representations[word]:\n",
    "            word_representations[word][key] /= total\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dictionary_dot_product(dict1, dict2):\n",
    "    dot = 0\n",
    "    for key in dict1:\n",
    "        if key in dict2:\n",
    "            dot += dict1[key] * dict2[key]\n",
    "    return dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_sim(word_representations, query):\n",
    "    if query not in word_representations:\n",
    "        print(\"'%s' is not in vocabulary\" % query)\n",
    "        return None\n",
    "    \n",
    "    scores = {}\n",
    "    for word in word_representations:\n",
    "        cosine = dictionary_dot_product(word_representations[query], word_representations[word])\n",
    "        scores[word] = cosine\n",
    "    return scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Find the K words with highest cosine similarity to a query in a set of word_representations\n",
    "def find_nearest_neighbors(word_representations, query, K):\n",
    "    scores = find_sim(word_representations, query)\n",
    "    if scores != None:\n",
    "        sorted_x = sorted(scores.items(), key=lambda x: x[1], reverse=True)\n",
    "        for idx, (k, v) in enumerate(sorted_x[:K]):\n",
    "            print(\"%s\\t%s\\t%.5f\" % (idx,k,v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explore the difference between `count_unigram_context` and `count_directional_context` for determining what counts as \"context\".  `count_unigram_context` counts an individual unigram in the bag of words around a target as a \"context\" variable, while `count_directional_context` counts the sequence of words before and after the word as a single \"context\"--and specifies the direction it occurs (to the left or right of the word)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "word_representations = create_vocab(wiki_data)\n",
    "count_directional_context(wiki_data, word_representations)\n",
    "normalize(word_representations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_nearest_neighbors(word_representations, \"actor\", 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's find the contexts shared between two words that have the most contribution\n",
    "# to the cosine similarity\n",
    "\n",
    "def find_shared_contexts(word_representations, query1, query2, K):\n",
    "    if query1 not in word_representations:\n",
    "        print(\"'%s' is not in vocabulary\" % query1)\n",
    "        return None\n",
    "    \n",
    "    if query2 not in word_representations:\n",
    "        print(\"'%s' is not in vocabulary\" % query2)\n",
    "        return None\n",
    "    \n",
    "    context_scores = {}\n",
    "    dict1 = word_representations[query1]\n",
    "    dict2 = word_representations[query2]\n",
    "    \n",
    "    for key in dict1:\n",
    "        if key in dict2:\n",
    "            score = dict1[key] * dict2[key]\n",
    "            context_scores[key] = score\n",
    "\n",
    "    sorted_x = sorted(context_scores.items(), key=lambda x: x[1], reverse=True)\n",
    "    for idx, (k, v) in enumerate(sorted_x[:K]):\n",
    "        print(\"%s\\t%s\\t%.5f\" % (idx,k,v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_shared_contexts(word_representations, \"actor\", \"politician\", 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see here that the single feature that has the most impact on similarity between these parts is the directional ngram \". he\" (which would appear in text like \"John is an actor **. He** ...\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Activity**: Find the nearest neighbors for other words above (in the `find_nearest_neighbors` cell); then find the shared contexts for a pair of nearest neighbors (as we did for actor/politician).  What does this reveal about what drives similarity?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}