notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Language\n",
    "\n",
    "So far in the course, we needed to shape tasks and data such that an AI\n",
    "will be able to process them. Today, we will look at how an AI can be\n",
    "constructed to process human language.\n",
    "\n",
    "**Natural Language Processing** spans all tasks where the AI gets human\n",
    "language as input. The following are a few examples of such tasks:\n",
    "\n",
    "- automatic summarization, where the AI is\n",
    "    given text as input and it produces a summary of the text as output.\n",
    "- information extraction, where the AI is\n",
    "    given a corpus of text and the AI extracts data as output.\n",
    "- language identification, where the AI is\n",
    "    given text and returns the language of the text as output.\n",
    "- machine translation, where the AI is\n",
    "    given a text in the origin language and it outputs the translation\n",
    "    in the target language.\n",
    "- named entity recognition, where the AI is\n",
    "    given text and it extracts the names of the entities in the text\n",
    "    (for example, names of companies).\n",
    "- speech recognition, where the AI is given\n",
    "    speech and it produces the same words in text.\n",
    "- text classification, where the AI is\n",
    "    given text and it needs to classify it as some type of text.\n",
    "- word sense disambiguation, where the AI\n",
    "    needs to choose the right meaning of a word that has multiple\n",
    "    meanings (e.g. bank means both a financial institution and the\n",
    "    ground on the sides of a river)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Syntax and Semantics\n",
    "\n",
    "**Syntax** is sentence structure. As native speakers of some human\n",
    "language, we don’t struggle with producing grammatical sentences and\n",
    "flagging non-grammatical sentences as wrong. For example, the sentence\n",
    "“Just before nine o’clock Sherlock Holmes stepped briskly into the room”\n",
    "is grammatical, whereas the sentence “Just before Sherlock Holmes nine\n",
    "o’clock stepped briskly the room” is non-grammatical. Syntax can be\n",
    "grammatical and ambiguous at the same time, as in “I saw the man with\n",
    "the telescope.” Did I see (the man with the telescope) or did I see (the\n",
    "man), doing so by looking through the telescope? To be able to parse\n",
    "human speech and produce it, the AI needs to command syntax.\n",
    "\n",
    "**Semantics** is the meaning of words or sentences. While the sentence\n",
    "“Just before nine o’clock Sherlock Holmes stepped briskly into the room”\n",
    "is syntactically different from “Sherlock Holmes stepped briskly into\n",
    "the room just before nine o’clock,” their content is effectively\n",
    "identical. Similarly, although the sentence “A few minutes before nine,\n",
    "Sherlock Holmes walked quickly into the room” uses different words from\n",
    "the previous sentences, it still carries a very similar meaning.\n",
    "Moreover, a sentence can be perfectly grammatical while being completely\n",
    "nonsensical, as in Chomsky’s example, “Colorless green ideas sleep\n",
    "furiously.” To be able to parse human speech and produce it, the AI\n",
    "needs to command semantics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Context-Free Grammar\n",
    "\n",
    "**Formal Grammar** is a system of rules for generating sentences in a\n",
    "language. In **Context-Free Grammar**, the text is abstracted from its\n",
    "meaning to represent the structure of the sentence using formal grammar.\n",
    "Let’s consider the following example sentence:\n",
    "\n",
    "- She saw the city.\n",
    "\n",
    "This is a simple grammatical sentence, and we would like to generate a\n",
    "syntax tree representing its structure.\n",
    "\n",
    "We start by assigning each word its part of speech. *She* and *city* are\n",
    "nouns, which we will mark as N. *Saw* is a verb, which we will mark as\n",
    "V. *The* is a determiner, marking the following noun as definite or\n",
    "indefinite, and we will mark it as D. Now, the above sentence can be\n",
    "rewritten as\n",
    "\n",
    "- N V D N\n",
    "\n",
    "So far, we have abstracted each word from its semantic meaning to its\n",
    "part of speech. However, words in a sentence are connected to each\n",
    "other, and to understand the sentence we must understand how they\n",
    "connect. A noun phrase (NP) is a group of words that connect to a noun.\n",
    "For example, the word *she* is a noun phrase in this sentence. In\n",
    "addition, the words *the city* also form a noun phrase, consisting of a\n",
    "determiner and a noun. A verb phrase (VP) is a group of words that\n",
    "connect to a verb. The word *saw* is a verb phrase in itself. However,\n",
    "the words *saw the city* also make a verb phrase. In this case, it is a\n",
    "verb phrase consisting of a verb and a noun phrase, which in turn\n",
    "consists of a determiner and a noun. Finally, the whole sentence (S) can\n",
    "be represented as follows:\n",
    "\n",
    "![Syntactic Tree](https://cs50.harvard.edu/ai/2024/notes/6/syntactictree.png)\n",
    "\n",
    "Using formal grammar, the AI is able to represent the structure of\n",
    "sentences. In the grammar we have described, there are enough rules to\n",
    "represent the simple sentence above. To represent more complex\n",
    "sentences, we will have to add more rules to our formal grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## nltk\n",
    "\n",
    "As is often the case in Python, multiple libraries have been written to\n",
    "implement the idea above. nltk (Natural Language Toolkit) is one such\n",
    "library. To analyze the sentence from above, we will provide the\n",
    "algorithm with rules for the grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "\n",
    "grammar = nltk.CFG.fromstring(\n",
    "    \"\"\"\n",
    "    S -> NP VP\n",
    "\n",
    "    NP -> D N | N\n",
    "    VP -> V | V NP\n",
    "\n",
    "    D -> \"the\" | \"a\"\n",
    "    N -> \"she\" | \"city\" | \"car\"\n",
    "    V -> \"saw\" | \"walked\"\n",
    "\"\"\"\n",
    ")\n",
    "\n",
    "parser = nltk.ChartParser(grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar to what we did above, we define what possible components could\n",
    "be included in others. A sentence can include a noun phrase and a verb\n",
    "phrase, while the phrases themselves can consist of other phrases,\n",
    "nouns, verbs, etc., and, finally, each part of speech spans some words\n",
    "in the language."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         S              \n",
      "  _______|___            \n",
      " |           VP         \n",
      " |    _______|___        \n",
      " NP  |           NP     \n",
      " |   |        ___|___    \n",
      " N   V       D       N  \n",
      " |   |       |       |   \n",
      "she saw     the     city\n",
      "\n"
     ]
    }
   ],
   "source": [
    "sentence = input(\"Sentence: \").split()\n",
    "try:\n",
    "    for tree in parser.parse(sentence):\n",
    "        tree.pretty_print()\n",
    "except ValueError:\n",
    "    print(\"No parse tree possible.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After giving the algorithm an input sentence split into a list of words,\n",
    "the function prints the resulting syntactic tree (pretty_print) and also\n",
    "generates a graphic representation (draw).\n",
    "\n",
    "![Syntactic Trees](https://cs50.harvard.edu/ai/2024/notes/6/trees.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     S                                     \n",
      "  ___|___________                           \n",
      " |               VP                        \n",
      " |    ___________|________                  \n",
      " |   |       |            PP               \n",
      " |   |       |        ____|___              \n",
      " |   |       NP      |        NP           \n",
      " |   |    ___|___    |     ___|______       \n",
      " NP  |   |       NP  |    |          NP    \n",
      " |   |   |       |   |    |          |      \n",
      " N   V   D       N   P    D          N     \n",
      " |   |   |       |   |    |          |      \n",
      "she saw the     dog with the     binoculars\n",
      "\n",
      "     S                                     \n",
      "  ___|_______                               \n",
      " |           VP                            \n",
      " |    _______|___                           \n",
      " |   |           NP                        \n",
      " |   |    _______|____                      \n",
      " |   |   |            NP                   \n",
      " |   |   |    ________|___                  \n",
      " |   |   |   |            PP               \n",
      " |   |   |   |    ________|___              \n",
      " |   |   |   |   |            NP           \n",
      " |   |   |   |   |         ___|______       \n",
      " NP  |   |   |   |        |          NP    \n",
      " |   |   |   |   |        |          |      \n",
      " N   V   D   N   P        D          N     \n",
      " |   |   |   |   |        |          |      \n",
      "she saw the dog with     the     binoculars\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "\n",
    "grammar = nltk.CFG.fromstring(\n",
    "    \"\"\"\n",
    "    S -> NP VP\n",
    "\n",
    "    AP -> A | A AP\n",
    "    NP -> N | D NP | AP NP | N PP\n",
    "    PP -> P NP\n",
    "    VP -> V | V NP | V NP PP\n",
    "\n",
    "    A -> \"big\" | \"blue\" | \"small\" | \"dry\" | \"wide\"\n",
    "    D -> \"the\" | \"a\" | \"an\"\n",
    "    N -> \"she\" | \"city\" | \"car\" | \"street\" | \"dog\" | \"binoculars\"\n",
    "    P -> \"on\" | \"over\" | \"before\" | \"below\" | \"with\"\n",
    "    V -> \"saw\" | \"walked\"\n",
    "\"\"\"\n",
    ")\n",
    "\n",
    "parser = nltk.ChartParser(grammar)\n",
    "\n",
    "sentence = input(\"Sentence: \").split()\n",
    "try:\n",
    "    for tree in parser.parse(sentence):\n",
    "        tree.pretty_print()\n",
    "except ValueError:\n",
    "    print(\"No parse tree possible.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## n-grams\n",
    "\n",
    "An *n*-gram is a sequence of *n* items from a sample of text. In a\n",
    "**character *n*-gram**, the items are characters, and in a **word\n",
    "*n*-gram** the items are words. A *unigram*, *bigram*, and *trigram* are\n",
    "sequences of one, two, and three items. In the following sentence, the\n",
    "first three *n*-grams are “how often have,” “often have I,” and “have I\n",
    "said.”\n",
    "\n",
    "“How often have I said to you that when you have eliminated the\n",
    "impossible whatever remains, however improbable, must be the truth?”\n",
    "\n",
    "*n*-grams are useful for text processing. While the AI hasn’t\n",
    "necessarily seen the whole sentence before, it sure has seen parts of\n",
    "it, like “have I said.” Since some words occur together more often than\n",
    "others, it is possible to also predict the next word with some\n",
    "probability. For example, your smartphone suggests words to you based on\n",
    "a probability distribution derived from the last few words you typed.\n",
    "Thus, a helpful step in natural language processing is breaking the\n",
    "sentence into n-grams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading data...\n",
      "1158: ('of', 'the')\n",
      "879: ('in', 'the')\n",
      "521: ('it', 'was')\n",
      "498: ('to', 'the')\n",
      "463: ('it', 'is')\n",
      "457: ('i', 'have')\n",
      "405: ('that', 'i')\n",
      "378: ('at', 'the')\n",
      "370: ('and', 'i')\n",
      "332: ('and', 'the')\n"
     ]
    }
   ],
   "source": [
    "!python ngrams/ngrams.py 2 ngrams/holmes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tokenization\n",
    "\n",
    "Tokenization is the task of splitting a sequence of characters into\n",
    "pieces (tokens). Tokens can be words as well as sentences, in which case\n",
    "the task is called **word tokenization** or **sentence tokenization**.\n",
    "We need tokenization to be able to look at *n*-grams, since those rely\n",
    "on sequences of tokens. We start by splitting the text into words based\n",
    "on the space character. While this is a good start, this method is\n",
    "imperfect because we end up with words with punctuation, such as\n",
    "“remains,”. So, for example, we can remove punctuation. However, then we\n",
    "face additional challenges, such as words with apostrophes (e.g.\n",
    "“o’clock”) and hyphens (e.g. “pearl-grey). Additionally, some\n",
    "punctuation is important for sentence structure, like periods. However,\n",
    "we need to be able to tell apart between a period at the end of the word\n",
    "“Mr.” and a period in the end of the sentence. Dealing with these\n",
    "questions is the process of tokenization. In the end, once we have our\n",
    "tokens, we can start looking at *n*-grams."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Markov Models\n",
    "\n",
    "As discussed in previous lectures, Markov models consist of nodes, the\n",
    "value of each of which has a probability distribution based on a finite\n",
    "number of previous nodes. Markov models can be used to generate text. To\n",
    "do so, we train the model on a text, and then establish probabilities\n",
    "for every *n*-th token in an *n*-gram based on the *n* words preceding\n",
    "it. For example, using trigrams, after the Markov model has two words,\n",
    "it can choose a third one from a probability distribution based on the\n",
    "first two. Then, it can choose a fourth word from a probability\n",
    "distribution based on the second and third words. To see an\n",
    "implementation of such a model using nltk, refer to generator.py in the\n",
    "source code, where our model learns to generate Shakespeare-sounding\n",
    "sentences. Eventually, using Markov models, we are able to generate text\n",
    "that is often grammatical and sounding superficially similar to human\n",
    "language output. However, these sentences lack actual meaning and\n",
    "purpose."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Farewell, my dearest Thisby dear.\n",
      "\n",
      "Sir, you and other LORDS; at another, with hers OBERON.\n",
      "\n",
      "This is the greatest men in Kendal green came at my back to school in Wittenberg, It is requir'd You do it With sweet rehearsal of my friend, faithful and anointed queen.\n",
      "\n",
      "Methinks I so should term them- and the aerial blue An indistinct regard.\n",
      "\n",
      "I have found'red nine score and the rest.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "!python markov/generator.py markov/shakespeare.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bag-of-Words Model\n",
    "\n",
    "Bag-of-words is a model that represents text as an unordered collection\n",
    "of words. This model ignores syntax and considers only the meanings of\n",
    "the words in the sentence. This approach is helpful in some\n",
    "classification tasks, such as sentiment analysis (another classification\n",
    "task would be distinguishing regular email from spam email). Sentiment\n",
    "analysis can be used, for instance, in product reviews, categorizing\n",
    "reviews as positive or negative. Consider the following sentences:\n",
    "\n",
    "1. “My grandson loved it! So much fun!”\n",
    "2. “Product broke after a few days.”\n",
    "3. “One of the best games I’ve played in a long time.”\n",
    "4. “Kind of cheap and flimsy, not worth it.”\n",
    "\n",
    "Based only on the words in each sentence and ignoring the grammar, we\n",
    "can see that sentences 1 and 3 are positive (“loved,” “fun,” “best”) and\n",
    "sentences 2 and 4 are negative (“broke,” “cheap,” “flimsy”)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Naive Bayes\n",
    "\n",
    "Naive Bayes is a technique that can be used in sentiment analysis with\n",
    "the bag-of-words model. In sentiment analysis, we are asking “What is\n",
    "the probability that the sentence is positive/negative given the words\n",
    "in the sentence.” Answering this question requires computing conditional\n",
    "probability, and it is helpful to recall Bayes’ rule from lecture 2:\n",
    "\n",
    "![Bayes' Rule](https://cs50.harvard.edu/ai/2024/notes/6/bayesrule.png)\n",
    "\n",
    "Now, we would like to use this formula to find P(sentiment \\| text), or,\n",
    "for example, P(positive \\| “my grandson loved it”). We start by\n",
    "tokenizing the input, such that we end up with P(positive \\| “my”,\n",
    "“grandson”, “loved”, “it”). Applying Bayes’ ruled directly, we get the\n",
    "following expression: P(“my”, “grandson”, “loved”, “it” \\|\n",
    "positive)\\*P(positive)/P(“my”, “grandson”, “loved”, “it”). This\n",
    "complicated expression will give us the precise answer to P(positive \\|\n",
    "“my”, “grandson”, “loved”, “it”).\n",
    "\n",
    "However, we can simplify the expression if we are willing to get an\n",
    "answer that’s not equal, but proportional to P(positive \\| “my”,\n",
    "“grandson”, “loved”, “it”). Later on, knowing that the probability\n",
    "distribution needs to sum up to 1, we can normalize the resulting value\n",
    "into an exact probability. This means that we can simplify the\n",
    "expression above to the numerator only: P(“my”, “grandson”, “loved”,\n",
    "“it” \\| positive)\\*P(positive). Again, we can simplify this expression\n",
    "based on the knowledge that a conditional probability of *a* given *b*\n",
    "is proportional to the joint probability of *a* and *b*. Thus, we get\n",
    "the following expression for our probability: P(positive, “my”,\n",
    "“grandson”, “loved”, “it”)\\*P(positive). Calculating this joint\n",
    "probability, however, is complicated, because the probability of each\n",
    "word is conditioned on the probabilities of the words preceding it. It\n",
    "requires us to compute P(positive)\\*P(“my” \\| positive)\\*P(“grandson” \\|\n",
    "positive, “my”)\\*P(loved \\| positive, “my”, “grandson”)\\*P(“it” \\|\n",
    "positive, “my”, “grandson”, “loved”).\n",
    "\n",
    "Here is where we use Bayes’ rules naively: we assume that the\n",
    "probability of each word is independent from other words. This is not\n",
    "true, but despite this imprecision, Naive Bayes’ produces a good\n",
    "sentiment estimate. Using this assumption, we end up with the following\n",
    "probability: P(positive)\\*P(“my” \\| positive)\\*P(“grandson” \\|\n",
    "positive)\\*P(“loved” \\| positive)\\*P(“it” \\| positive), which is not\n",
    "that difficult to calculate. P(positive) = the number of all positive\n",
    "samples divided by the number of total samples. P(“loved” \\| positive)\n",
    "is equal to the number of positive samples with the word “loved” divided\n",
    "by the number of positive samples. Let’s consider the example below,\n",
    "with smiling and frowning emojies substituting the words “positive” and\n",
    "“negative”:\n",
    "\n",
    "![Naive Bayes](https://cs50.harvard.edu/ai/2024/notes/6/naivebayes.png)\n",
    "\n",
    "On the right we are seeing a table with the conditional probabilities of\n",
    "each word on the left occurring in a sentence given that the sentence is\n",
    "positive or negative. In the small table on the left we are seeing the\n",
    "probability of a positive or a negative sentence. On the bottom left we\n",
    "are seeing the resulting probabilities following the computation. At\n",
    "this point, they are in proportion to each other, but they don’t tell us\n",
    "much in terms of probabilities. To get the probabilities, we need to\n",
    "normalize the values, arriving at P(positive) = 0.6837 and P(negative) =\n",
    "0.3163. The strength of naive Bayes is that it is sensitive to words\n",
    "that occur more often in one type of sentence than in the other. In our\n",
    "case, the word “loved” occurs much more often in positive sentences,\n",
    "which makes the whole sentence more likely to be positive than negative.\n",
    "To see an implementation of sentiment assessment using Naive Bayes with\n",
    "the nltk library, refer to sentiment.py.\n",
    "\n",
    "One problem that we can run into is that some words may never appear in\n",
    "a certain type of sentence. Suppose none of the positive sentences in\n",
    "our sample had the word “grandson.” Then, P(“grandson” \\| positive) = 0,\n",
    "and when computing the probability of the sentence being positive we\n",
    "will get 0. However, this is not the case in reality (not all sentences\n",
    "mentioning grandsons are negative). One way to go about this problem is\n",
    "with **Additive Smoothing**, where we add a value α to each value in our\n",
    "distribution to smooth the data. This way, even if a certain value is 0,\n",
    "by adding α to it we won’t be multiplying the whole probability for a\n",
    "positive or negative sentence by 0. A specific type of additive\n",
    "smoothing, **Laplace Smoothing** adds 1 to each value in our\n",
    "distribution, pretending that all values have been observed at least\n",
    "once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Positive: 0.9241\n",
      "Negative: 0.0759\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import sys\n",
    "\n",
    "import nltk\n",
    "\n",
    "\n",
    "def main():\n",
    "\n",
    "    # Read data from files\n",
    "    if len(sys.argv) != 2:\n",
    "        sys.exit(\"Usage: python sentiment.py corpus\")\n",
    "    positives, negatives = load_data(\"sentiment/corpus\")\n",
    "\n",
    "    # Create a set of all words\n",
    "    words = set()\n",
    "    for document in positives:\n",
    "        words.update(document)\n",
    "    for document in negatives:\n",
    "        words.update(document)\n",
    "\n",
    "    # Extract features from text\n",
    "    training = []\n",
    "    training.extend(generate_features(positives, words, \"Positive\"))\n",
    "    training.extend(generate_features(negatives, words, \"Negative\"))\n",
    "\n",
    "    # Classify a new sample\n",
    "    classifier = nltk.NaiveBayesClassifier.train(training)\n",
    "    s = input(\"s: \")\n",
    "    result = classify(classifier, s, words)\n",
    "    for key in result.samples():\n",
    "        print(f\"{key}: {result.prob(key):.4f}\")\n",
    "\n",
    "\n",
    "def extract_words(document):\n",
    "    return set(\n",
    "        word.lower()\n",
    "        for word in nltk.word_tokenize(document)\n",
    "        if any(c.isalpha() for c in word)\n",
    "    )\n",
    "\n",
    "\n",
    "def load_data(directory):\n",
    "    result = []\n",
    "    for filename in [\"positives.txt\", \"negatives.txt\"]:\n",
    "        with open(os.path.join(directory, filename), encoding=\"utf-8\") as f:\n",
    "            result.append([extract_words(line) for line in f.read().splitlines()])\n",
    "    return result\n",
    "\n",
    "\n",
    "def generate_features(documents, words, label):\n",
    "    features = []\n",
    "    for document in documents:\n",
    "        features.append(({word: (word in document) for word in words}, label))\n",
    "    return features\n",
    "\n",
    "\n",
    "def classify(classifier, document, words):\n",
    "    document_words = extract_words(document)\n",
    "    features = {word: (word in document_words) for word in words}\n",
    "    return classifier.prob_classify(features)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Positive: 0.0438\n",
      "Negative: 0.9562\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Word Representation\n",
    "\n",
    "We want to represent word meanings in our AI. As we’ve seen before, it\n",
    "is convenient to provide input to the AI in the form of numbers. One way\n",
    "to go about this is by using **One-Hot Representation**, where each word\n",
    "is represented with a vector that consists of as many values as we have\n",
    "words. Except for a single value in the vector that is equal to 1, all\n",
    "other values are equal to 0. How we can differentiate words is by which\n",
    "of the values is 1, ending up with a unique vector per word. For\n",
    "example, the sentence “He wrote a book” can be represented as four\n",
    "vectors:\n",
    "\n",
    "- $1, 0, 0, 0$ (he)\n",
    "- $0, 1, 0, 0$ (wrote)\n",
    "- $0, 0, 1, 0$ (a)\n",
    "- $0, 0, 0, 1$ (book)\n",
    "\n",
    "However, while this representation works in a world with four words, if\n",
    "we want to represent words from a dictionary, when we can have 50,000\n",
    "words, we will end up with 50,000 vectors of length 50,000. This is\n",
    "incredibly inefficient. Another problem in this kind of representation\n",
    "is that we are unable to represent similarity between words like “wrote”\n",
    "and “authored.” Instead, we turn to the idea of **Distributed\n",
    "Representation**, where meaning is distributed across multiple values in\n",
    "a vector. With distributed representation, each vector has a limited\n",
    "number of values (much less than 50,000), taking the following form:\n",
    "\n",
    "- $-0.34, -0.08, 0.02, -0.18, …$ (he)\n",
    "- $-0.27, 0.40, 0.00, -0.65, …$ (wrote)\n",
    "- $-0.12, -0.25, 0.29, -0.09, …$ (a)\n",
    "- $-0.23, -0.16, -0.05, -0.57, …$ (book)\n",
    "\n",
    "This allows us to generate unique values for each word while using\n",
    "smaller vectors. Additionally, now we are able to represent similarity\n",
    "between words by how different the values in their vectors are.\n",
    "\n",
    "“You shall know a word by the company it keeps” is an idea by J. R.\n",
    "Firth, an English linguist. Following this idea, we can come to define\n",
    "words by their adjacent words. For example, there are limited words that\n",
    "we can use to complete the sentence “for \\_\\_\\_ he ate.” These words are\n",
    "probably words like “breakfast,” “lunch,” and “dinner.” This brings us\n",
    "to the conclusion that by considering the environment in which a certain\n",
    "word tends to appear, we can infer the meaning of the word."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## word2vec\n",
    "\n",
    "word2vec is an algorithm for generating distributed representations of\n",
    "words. It does so by **Skip-Gram Architecture**, which is a neural\n",
    "network architecture for predicting context given a target word. In this\n",
    "architecture, the neural network has an input unit for every target\n",
    "word. A smaller, single hidden layer (e.g. 50 or 100 units, though this\n",
    "number is flexible) will generate values that represent the distributed\n",
    "representations of words. Every unit in this hidden layer is connected\n",
    "to every unit in the input layer. The output layer will generate words\n",
    "that are likely to appear in a similar context as the target words.\n",
    "Similar to what we saw in last lecture, this network needs to be trained\n",
    "with a training dataset using the backpropagation algorithm.\n",
    "\n",
    "![Skip-Gram Architecture](https://cs50.harvard.edu/ai/2024/notes/6/sgarchitecture.png)\n",
    "\n",
    "This neural network turns out to be quite powerful. At the end of the\n",
    "process, every word ends up being just a vector, or a sequence of\n",
    "numbers. For example,\n",
    "\n",
    "book: $[-0.226776 -0.155999 -0.048995 -0.569774 0.053220 0.124401\n",
    "-0.091108 -0.606255 -0.114630 0.473384 0.061061 0.551323 -0.245151\n",
    "-0.014248 -0.210003 0.316162 0.340426 0.232053 0.386477 -0.025104\n",
    "-0.024492 0.342590 0.205586 -0.554390 -0.037832 -0.212766 -0.048781\n",
    "-0.088652 0.042722 0.000270 0.356324 0.212374 -0.188433 0.196112\n",
    "-0.223294 -0.014591 0.067874 -0.448922 -0.290960 -0.036474 -0.148416\n",
    "0.448422 0.016454 0.071613 -0.078306 0.035400 0.330418 0.293890 0.202701\n",
    "0.555509 0.447660 -0.361554 -0.266283 -0.134947 0.105315 0.131263\n",
    "0.548085 -0.195238 0.062958 -0.011117 -0.226676 0.050336 -0.295650\n",
    "-0.201271 0.014450 0.026845 0.403077 -0.221277 -0.236224 0.213415\n",
    "-0.163396 -0.218948 -0.242459 -0.346984 0.282615 0.014165 -0.342011\n",
    "0.370489 -0.372362 0.102479 0.547047 0.020831 -0.202521 -0.180814\n",
    "0.035923 -0.296322 -0.062603 0.232734 0.191323 0.251916 0.150993\n",
    "-0.024009 0.129037 -0.033097 0.029713 0.125488 -0.018356 -0.226277\n",
    "0.437586 0.004913]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-2.807500e-02,  1.389900e-01, -1.247990e-01, -6.530260e-01,\n",
       "       -9.997000e-03,  4.460050e-01, -4.330270e-01, -5.738260e-01,\n",
       "       -8.352800e-02,  5.572320e-01,  1.770960e-01,  5.558660e-01,\n",
       "       -2.561450e-01,  2.667560e-01, -1.030250e-01,  3.036520e-01,\n",
       "        2.375330e-01,  2.188730e-01,  3.600540e-01,  2.499900e-01,\n",
       "       -3.761940e-01,  6.574720e-01,  9.664000e-02, -5.642030e-01,\n",
       "       -1.094780e-01, -6.022120e-01,  1.047600e-02, -1.510490e-01,\n",
       "        1.123330e-01, -3.909700e-02,  4.213900e-02,  6.661100e-02,\n",
       "       -1.172780e-01,  7.880700e-02, -3.891830e-01, -3.143310e-01,\n",
       "        2.120360e-01, -3.989880e-01, -2.841770e-01, -2.219240e-01,\n",
       "       -1.530810e-01,  4.205950e-01,  2.302700e-02,  2.656270e-01,\n",
       "       -1.786180e-01, -7.330000e-04, -8.099100e-02,  2.130000e-02,\n",
       "        1.757470e-01,  1.006242e+00,  4.782700e-01, -1.995300e-01,\n",
       "       -5.899500e-02, -1.358600e-01, -1.480700e-02, -4.497000e-02,\n",
       "        2.570150e-01, -2.532290e-01, -1.901030e-01,  7.539600e-02,\n",
       "       -3.092270e-01, -8.611500e-02, -5.799090e-01, -4.079630e-01,\n",
       "        2.027140e-01,  1.035400e-01,  4.474260e-01,  1.341270e-01,\n",
       "       -4.936000e-03,  3.169560e-01,  2.962200e-02, -3.665200e-02,\n",
       "        3.351400e-02, -2.034150e-01,  3.198540e-01,  3.540500e-02,\n",
       "       -2.890330e-01,  3.036660e-01, -7.442160e-01,  2.947550e-01,\n",
       "        4.552740e-01, -3.378620e-01,  2.740200e-01, -7.113560e-01,\n",
       "        1.819190e-01, -1.458400e-01, -2.496370e-01,  2.203900e-01,\n",
       "        3.314080e-01,  1.969190e-01,  1.335200e-01, -9.748300e-02,\n",
       "        1.683990e-01, -3.545960e-01,  1.482530e-01,  1.195520e-01,\n",
       "       -1.700290e-01, -8.414800e-02,  3.639250e-01, -3.021800e-01])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from vectors.vectors import *\n",
    "\n",
    "words[\"books\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By themselves, these numbers don’t mean much. But by finding which other\n",
    "words in the corpus have the most similar vectors, we can run a function\n",
    "that will generate the words that are the most similar to the word\n",
    "*book*. In the case of this network it will be: book, books, essay,\n",
    "memoir, essays, novella, anthology, blurb, autobiography, audiobook.\n",
    "This is not bad for a computer! Through a bunch of numbers that don’t\n",
    "carry any specific meaning themselves, the AI is able to generate words\n",
    "that really are very similar to *book* not in letters or sounds, but in\n",
    "meaning! We can also compute the difference between words based on how\n",
    "different their vectors are. For example, the difference between *king*\n",
    "and *man* is similar to the difference between *queen* and *woman*. That\n",
    "is, if we add the difference between *king* and *man* to the vector for\n",
    "*woman*, the closest word to the resulting vector is *queen*! Similarly,\n",
    "if we add the difference between *ramen* and *japan* to *america*, we\n",
    "get *burritos*. By using neural networks and distributed representations\n",
    "for words, we get our AI to understand semantic similarities between\n",
    "words in the language, bringing us one step closer to AIs that can\n",
    "understand and produce human language."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5026172435744487"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(words[\"books\"], words[\"novel\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7500175287917794"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(words[\"books\"], words[\"breakfast\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2006302059301045"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(words[\"lunch\"], words[\"breakfast\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['book',\n",
       " 'books',\n",
       " 'essay',\n",
       " 'memoir',\n",
       " 'essays',\n",
       " 'novella',\n",
       " 'anthology',\n",
       " 'blurb',\n",
       " 'autobiography',\n",
       " 'audiobook']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "closest_words(words[\"book\"])[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'queen'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "closest_word(words[\"king\"] - words[\"man\"] + words[\"woman\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Neural Networks\n",
    "\n",
    "Recall that a **neural network** takes some input, passes it to the\n",
    "network, and creates some output. By providing the network with training\n",
    "data, it can do more and more of an accurate job of translating the\n",
    "input into an output. Commonly, machine translation uses neural\n",
    "networks. In practice, when we are translating words, we want to\n",
    "translate a sentence or paragraph. Since a sentence is a fixed size, we\n",
    "run into the problem of translating a sequence to another sequence where\n",
    "sizes are not fixed. If you have ever had a conversation with an AI\n",
    "chatbot, it needs to understand a sequence of words and generate an\n",
    "appropriate sequence as output.\n",
    "\n",
    "**Recurrent neural networks** can re-run the neural network multiple\n",
    "times, keeping track of a state that holds all relevant information.\n",
    "Input is taken into the network, creating a hidden state. Passing a\n",
    "second input into the encoder, along with the first hidden state,\n",
    "produces a new hidden state. This process is repeated until an end token\n",
    "is passed. Then, a decoding state begins, creating hidden state after\n",
    "hidden state until we get the final word and another end token. Some\n",
    "problems, however, arise. One problem in the encoder stage where all the\n",
    "information from the input stage must be stored in one final state. For\n",
    "large sequences, it’s very challenging to store all that information\n",
    "into a single state value. It would be useful to somehow combine all the\n",
    "hidden states. Another problem is that some of the hidden states in the\n",
    "input sequence are more important than others. Could there be some way\n",
    "to know what states (or words) are more important than others?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Attention\n",
    "\n",
    "**Attention** refers to the neural network’s ability to decide what\n",
    "values are more important than others. In the sentence “What is the\n",
    "capital of Massachusetts,” attention allows the neural network to decide\n",
    "what values it will pay attention to at each stage of generating the\n",
    "output sentence. Running such a calculation, the neural network will\n",
    "show that when generating the final word of the answer, “capital” and\n",
    "“Massachusetts” are the most important to pay attention to. By taking\n",
    "the attention score, multiplying them by the hidden state values\n",
    "generated by the network, and adding them up, the neural network will\n",
    "create a final context vector that the decoder can use to calculate the\n",
    "final word. A challenge that arises in calculations such as these is\n",
    "that recurrent neural networks require sequential training of word after\n",
    "word. This takes a lot of time. With the growth of large language\n",
    "models, they take longer and longer to train. A desire for parallelism\n",
    "has steadily grown as larger and larger datasets need to be trained.\n",
    "Hence, a new architecture has been introduced."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transformers\n",
    "\n",
    "**Transformers** is a new type of training architecture whereby each\n",
    "input word is passed through a neural network simultaneously. An input\n",
    "word goes into the neural network and is captured as an encoded\n",
    "representation. Because all words are fed into the neural network at the\n",
    "same time, word order could easily be lost. Accordingly, **position\n",
    "encoding** is added to the inputs. The neural network, therefore, will\n",
    "use both the word and the position of the word in the encoded\n",
    "representation. Additionally, a **self-attention** step is added to help\n",
    "define the context of the word being inputted. In fact, neural networks\n",
    "will often use multiple self-attention steps such that they can further\n",
    "understand the context. This process is repeated multiple times for each\n",
    "of the words in the sequence. What results are encoded representations\n",
    "that will be useful when it’s time to decode the information.\n",
    "\n",
    "In the decoding step, the previous output word and its positional\n",
    "encoding are given to multiple self-attention steps and the neural\n",
    "network. Additionally, multiple attention steps are fed the encoded\n",
    "representation from the encoding process and provided to the neural\n",
    "network. Hence, words are able to pay attention to each other. Further,\n",
    "parallel processing is possible, and the calculations are fast and\n",
    "accurate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summing Up\n",
    "\n",
    "We have looked at artificial intelligence in a wide array of contexts.\n",
    "We looked at search problems in how AI can look for solutions. We looked\n",
    "at how AI represents knowledge and create knowledge. We looked at\n",
    "uncertainty when it does not know things for sure. We looked at\n",
    "optimization, maximizing and minimizing function. We looked at machine\n",
    "learning, finding patterns by looking at training data. We learned about\n",
    "neural networks and how they use weights to go from input to output.\n",
    "Today, we looked at language itself and how we can get the computer to\n",
    "understand our language. We have just scratched the surface of this\n",
    "process. We truly hope you enjoyed this journey with us. This was\n",
    "Introduction to Artificial Intelligence with Python."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}