{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true, "jupyter": { "outputs_hidden": true } }, "source": [ "# Programming Assignment 3: Information Retrieval (Winter 2026)\n", "\n", "In this assignment you will be improving upon a rather poorly-made information retrieval system. You will build an inverted index to quickly retrieve documents that match queries and then make it even better by using term-frequency inverse-document-frequency weighting and cosine similarity to compare queries to your data set. Your IR system will be evaluated for accuracy on the correct documents retrieved for different queries and the correctly computed tf-idf values and cosine similarities." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Data\n", "\n", "You will be using your IR system to find relevant documents among a collection of sixty books sourced from Project Gutenberg. The training data is located in the `data/` directory under the subdirectory `ProjectGutenberg/`. Within this directory you will see yet another directory `raw/`. This contains the raw text files of the sixty books. The `data/` directory also contains the files `dev_queries.txt` and `dev_solutions.txt`. We have provided these to you as a set of development queries and their expected answers to use as you begin implementing your IR system." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Your Task\n", "\n", "Improve upon the given IR system by implementing the following features:\n", "\n", "Inverted Index: Implement an inverted index, which maps words to the documents in which they occur and their count in each document.\n", "\n", "TF-IDF: Compute and store the term-frequency inverse-document-frequency value for every word-document co-occurrence.\n", "\n", "Cosine Similarity: Implement cosine similarity in order to improve upon the ranked retrieval system, which currently retrieves documents based upon the Jaccard coefficient between the query and each document. Note that when computing $w_{t, q}$ (i.e. the weight for the word 𝑤 in the query), do not include the idf term. That is, $w_{t, q} = 1 + \\log_{10} \\text{tf}_{t, q}$. Normalize by both the query and document vector lengths.\n", "\n", "Dense Retrieval: Use pre-computed BERT embeddings to implement dense retrieval. You will implement cosine similarity for dense vectors and a function to retrieve the top-k most similar documents given a query embedding.\n", "\n", "Reflection: Compare TF-IDF and dense retrieval methods, reflecting on their strengths and weaknesses." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Evaluation\n", "\n", "Your IR system will be evaluated on a small development set of queries as well as a held-out set of queries. The development queries are encoded in the file `dev_queries.txt`. These are:\n", "\n", "- chest of drawers\n", "- machine learning is cool\n", "- the cold breeze\n", "- pacific coast\n", "- pumpkin pies\n", "- i completed fizzbuzz\n", "\n", "We test your system based on five components: the inverted index (term counts), getting postings lists, computing the correct TF-IDF values, implementing cosine similarity using the TF-IDF values, and dense retrieval. The provided development queries contain words that appear frequently in the corpus (e.g., \"the\"), words that appear infrequently (e.g., \"drawers\"), and words that do not appear in any document (e.g., \"fizzbuzz\"). Some of the query phrases are found verbatim in the book dataset, and some are not. Your system should be able to correctly handle all of these cases." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Environment Check\n", "\n", "Before we do anything else, let's quickly check that you're running the correct\n", "version of Python and are in the right environment!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import os\n", "assert os.environ['CONDA_DEFAULT_ENV'] == \"cs124\"\n", "\n", "import sys\n", "assert sys.version_info.major == 3 and sys.version_info.minor == 10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If the above cell complains, it means that you're using the wrong environment\n", "or Python version!\n", "\n", "If so, please exit this notebook, kill the notebook server with CTRL-C, and\n", "try running\n", "\n", "$ `conda activate cs124`\n", "\n", "then restarting your notebook server with\n", "\n", "$ `jupyter notebook`\n", "\n", "If that doesn't work, you should go back and follow the installation\n", "instructions in PA0." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Getting Started!\n", "\n", "We will first start by importing some modules and setting up our IR system class.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import json\n", "import os\n", "import re\n", "import sys\n", "import math\n", "import numpy as np\n", "from collections import defaultdict\n", "from collections import Counter\n", "\n", "from porter_stemmer import PorterStemmer" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem:\n", " def __init__(self):\n", " # For holding the data - initialized in read_data()\n", " self.titles = []\n", " self.docs = []\n", " self.vocab = []\n", " # For the text pre-processing.\n", " self.alphanum = re.compile('[^a-zA-Z0-9]')\n", " self.p = PorterStemmer()\n", "\n", " def get_uniq_words(self):\n", " uniq = set()\n", " for doc in self.docs:\n", " for word in doc:\n", " uniq.add(word)\n", " return uniq\n", "\n", " def __read_raw_data(self, dirname):\n", " print(\"Stemming Documents...\")\n", "\n", " titles = []\n", " docs = []\n", " os.mkdir('%s/stemmed' % dirname)\n", " title_pattern = re.compile('(.*) \\d+\\.txt')\n", "\n", " # make sure we're only getting the files we actually want\n", " filenames = []\n", " for filename in os.listdir('%s/raw' % dirname):\n", " if filename.endswith(\".txt\") and not filename.startswith(\".\"):\n", " filenames.append(filename)\n", "\n", " for i, filename in enumerate(filenames):\n", " title = title_pattern.search(filename).group(1)\n", " print(\" Doc %d of %d: %s\" % (i + 1, len(filenames), title))\n", " titles.append(title)\n", " contents = []\n", " f = open('%s/raw/%s' % (dirname, filename), 'r', encoding=\"utf-8\")\n", " of = open('%s/stemmed/%s.txt' % (dirname, title), 'w',\n", " encoding=\"utf-8\")\n", " for line in f:\n", " # make sure everything is lower case\n", " line = line.lower()\n", " # split on whitespace\n", " line = [xx.strip() for xx in line.split()]\n", " # remove non alphanumeric characters\n", " line = [self.alphanum.sub('', xx) for xx in line]\n", " # remove any words that are now empty\n", " line = [xx for xx in line if xx != '']\n", " # stem words\n", " line = [self.p.stem(xx) for xx in line]\n", " # add to the document's conents\n", " contents.extend(line)\n", " if len(line) > 0:\n", " of.write(\" \".join(line))\n", " of.write('\\n')\n", " f.close()\n", " of.close()\n", " docs.append(contents)\n", " return titles, docs\n", "\n", " def __read_stemmed_data(self, dirname):\n", " print(\"Already stemmed!\")\n", " titles = []\n", " docs = []\n", "\n", " # make sure we're only getting the files we actually want\n", " filenames = []\n", " for filename in os.listdir('%s/stemmed' % dirname):\n", " if filename.endswith(\".txt\") and not filename.startswith(\".\"):\n", " filenames.append(filename)\n", "\n", " if len(filenames) != 60:\n", " msg = \"There are not 60 documents in ../data/ProjectGutenberg/stemmed/\\n\"\n", " msg += \"Remove ../data/ProjectGutenberg/stemmed/ directory and re-run.\"\n", " raise Exception(msg)\n", "\n", " for i, filename in enumerate(filenames):\n", " title = filename.split('.')[0]\n", " titles.append(title)\n", " contents = []\n", " f = open('%s/stemmed/%s' % (dirname, filename), 'r',\n", " encoding=\"utf-8\")\n", " for line in f:\n", " # split on whitespace\n", " line = [xx.strip() for xx in line.split()]\n", " # add to the document's conents\n", " contents.extend(line)\n", " f.close()\n", " docs.append(contents)\n", "\n", " return titles, docs\n", "\n", " def read_data(self, dirname):\n", " \"\"\"\n", " Given the location of the 'data' directory, reads in the documents to\n", " be indexed.\n", " \"\"\"\n", " # NOTE: We cache stemmed documents for speed\n", " # (i.e. write to files in new 'stemmed/' dir).\n", "\n", " print(\"Reading in documents...\")\n", " # dict mapping file names to list of \"words\" (tokens)\n", " filenames = os.listdir(dirname)\n", " subdirs = os.listdir(dirname)\n", " if 'stemmed' in subdirs:\n", " titles, docs = self.__read_stemmed_data(dirname)\n", " else:\n", " titles, docs = self.__read_raw_data(dirname)\n", "\n", " # Sort document alphabetically by title to ensure we have the proper\n", " # document indices when referring to them.\n", " ordering = [idx for idx, title in sorted(enumerate(titles),\n", " key=lambda xx: xx[1])]\n", "\n", " self.titles = []\n", " self.docs = []\n", " numdocs = len(docs)\n", " for d in range(numdocs):\n", " self.titles.append(titles[ordering[d]])\n", " self.docs.append(docs[ordering[d]])\n", "\n", " # Get the vocabulary.\n", " self.vocab = [xx for xx in self.get_uniq_words()]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Text Preprocessing\n", "\n", "Before we build our information retrieval system, we need to understand **text preprocessing** — the steps we take to normalize text before indexing and searching.\n", "\n", "Our IR system applies the following preprocessing pipeline to all documents and queries:\n", "\n", "1. **Lower case**: Convert all text to lower case (\"The\" → \"the\")\n", "2. **Tokenization**: Split text into individual words on whitespace\n", "3. **Remove non-alphanumeric**: Strip punctuation and special characters\n", "4. **Stemming**: Reduce words to their root form using the Porter Stemmer\n", "\n", "### Why Stemming?\n", "\n", "Stemming is often used as part of information retrieval. Consider the query \"running shoes\":\n", "- Without stemming: information retrieval can only matches documents containing exactly \"running\"\n", "- With stemming: \"running\" → \"run\", which also matches \"runs\", \"ran\", \"runner\"\n", "\n", "This dramatically improves **recall**, or our ability to find all relevant documents. The Porter Stemmer we use applies rules like:\n", "- \"running\" → \"run\"\n", "- \"machines\" → \"machin\"\n", "- \"learning\" → \"learn\"\n", "\n", "The preprocessing is already implemented in the `IRSystem` class above. When you build your inverted index, you'll be working with tokens that have already been stemmed." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 1: Inverted Index\n", "\n", "You will build an inverted index — a data structure that maps words to the documents that contain them and how many times they occur. We simply need to track the **term frequency** (count) of each word in each document.\n", "\n", "The inverted index should be structured as a nested dictionary like the following:\n", "\n", "`{word1: {doc1: 3}, word2: {doc2: 4}}`\n", "\n", "In the inverted index above, word 1 appeared 3 times in document 1, and word 2 appeared 4 times in document 2. You should be able to access the term count of a word in a particular document using this syntax: `inv_index[word][doc_id] = term_count`. For example, if \"drawer\" appears 8 times in document 24, then: `inv_index[\"drawer\"][24] = 8`\n", "\n", "The documents will have already been read in at this point. The following instance variables are available: `self.titles` (a list of strings), `self.docs` (a list of lists of strings), and `self.vocab` (a list of strings)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def index(self):\n", " \"\"\"\n", " Build an index of the documents.\n", " \"\"\"\n", " print(\"Indexing...\")\n", " # ------------------------------------------------------------------\n", " # TODO: Create an inverted index.\n", " # This index should map words to documents and store the count\n", " # of how many times each word appears in each document.\n", " # Some helpful instance variables:\n", " # * self.docs = List of documents\n", " # * self.titles = List of titles\n", "\n", " # Note: To avoid having to initialize inv_index manually, we import\n", " # defaultdict from collections.\n", " \n", " # Structure: inv_index[word][doc_id] = term_count\n", " # Example: inv_index[\"drawer\"] = {24: 8, 33: 2, 7: 1, ...}\n", " inv_index = defaultdict(lambda: defaultdict(int))\n", " \n", " # TODO: Generate inverted index here\n", " for i in range(len(self.docs)):\n", " pass\n", "\n", " self.inv_index = inv_index\n", "\n", " # ------------------------------------------------------------------\n", "\n", " # turn self.docs into a map from ID to bag of words\n", " id_to_bag_of_words = {}\n", " for d, doc in enumerate(self.docs):\n", " bag_of_words = set(doc)\n", " id_to_bag_of_words[d] = bag_of_words\n", " self.docs = id_to_bag_of_words" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Spot Check: `index()`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# === Spot Check: Inverted Index ===\n", "# Run this cell after implementing index() to verify your implementation\n", "\n", "# Create a temporary test instance\n", "_test_ir = IRSystem()\n", "_test_ir.read_data('./data/ProjectGutenberg')\n", "_test_ir.index()\n", "\n", "# Check 1: inv_index should exist\n", "assert hasattr(_test_ir, 'inv_index'), \"ERROR: inv_index not found! Make sure you create self.inv_index\"\n", "\n", "# Check 2: A known word should be in the index\n", "assert \"drawer\" in _test_ir.inv_index, \"ERROR: 'drawer' not found in inv_index\"\n", "\n", "# Check 3: \"drawer\" should appear in doc 24 (Metamorphosis - Franz Kafka)\n", "assert 24 in _test_ir.inv_index[\"drawer\"], \"ERROR: 'drawer' should appear in document 24\"\n", "\n", "# Check 4: \"drawer\" should appear 8 times in doc 24\n", "count = _test_ir.inv_index[\"drawer\"][24]\n", "assert count == 8, f\"ERROR: Expected count of 8 for 'drawer' in doc 24, got {count}\"\n", "\n", "# Check 5: \"drawer\" should appear 9 times in doc 33 (The Adventures of Sherlock Holmes)\n", "count = _test_ir.inv_index[\"drawer\"][33]\n", "assert count == 9, f\"ERROR: Expected count of 9 for 'drawer' in doc 33, got {count}\"\n", "\n", "print(\"All spot checks passed for index()!\")\n", "del _test_ir # Clean up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 2: Get Posting\n", "\n", "Now implement `get_posting` which returns the list of document IDs (sorted) in which a given word occurs. This uses your inverted index from Part 1." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def get_posting(self, word):\n", " \"\"\"\n", " Given a word, this returns the list of document indices (sorted) in\n", " which the word occurs.\n", " \"\"\"\n", " # ------------------------------------------------------------------\n", " # TODO: return the list of postings for a word.\n", " posting = []\n", "\n", " return posting\n", " # ------------------------------------------------------------------\n", " \n", " def get_posting_unstemmed(self, word):\n", " \"\"\"\n", " Given a word, this *stems* the word and then calls get_posting on the\n", " stemmed word to get its postings list. You should *not* need to change\n", " this function. It is needed for submission.\n", " \"\"\"\n", " word = self.p.stem(word)\n", " return self.get_posting(word)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# === Spot Check: get_posting() ===\n", "# Run this cell after implementing get_posting() to verify your implementation\n", "\n", "# Create a temporary test instance\n", "_test_ir = IRSystem()\n", "_test_ir.read_data('./data/ProjectGutenberg')\n", "_test_ir.index()\n", "\n", "# Check 1: \"drawer\" should appear in 18 documents\n", "posting = _test_ir.get_posting(\"drawer\")\n", "assert len(posting) == 18, f\"ERROR: 'drawer' should appear in 18 docs, got {len(posting)}\"\n", "\n", "# Check 2: Posting list should be sorted\n", "assert posting == sorted(posting), \"ERROR: Posting list should be sorted\"\n", "\n", "# Check 3: Should include doc 24 (Metamorphosis) and doc 33 (The Adventures of Sherlock Holmes)\n", "assert 24 in posting, \"ERROR: Doc 24 should be in posting list for 'drawer'\"\n", "assert 33 in posting, \"ERROR: Doc 33 should be in posting list for 'drawer'\"\n", "\n", "# Check 4: First few docs should match expected\n", "expected_start = [2, 7, 9, 10, 13]\n", "assert posting[:5] == expected_start, f\"ERROR: First 5 docs should be {expected_start}, got {posting[:5]}\"\n", "\n", "# Check 5: Non-existent word should return empty list\n", "posting = _test_ir.get_posting(\"fizzbuzz\")\n", "assert posting == [], f\"ERROR: 'fizzbuzz' not in corpus, should return [], got {posting}\"\n", "\n", "print(\"All spot checks passed for get_posting()!\")\n", "del _test_ir # Clean up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 3: TF-IDF\n", "\n", "Now we will compute and store the TF-IDF values. `compute_tfidf` computes and stores the TF-IDF values for words and documents. For this you will probably want to be aware of the class variable `self.vocab`, which holds the list of all unique words, as well as the inverted index you created earlier.\n", "\n", "Similar to the inverted index, you will store your TF-IDF values in a nested dictionary structure, where you can access the TF-IDF value of a given word in a document by calling `self.tfidf[word][doc] = tf_idf_value`. For example: `self.tfidf[\"drawer\"] = {24: 0.912, 33: 1.021, ...}`\n", "\n", "You must also implement `get_tfidf` to return the TF-IDF weight for a particular word and document ID. Make sure you correctly handle the case where the word isn't present in your vocabulary!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def compute_tfidf(self):\n", " \"\"\"\n", " Compute and store TF-IDF values for words and documents.\n", " Recall: TF-IDF = (1 + log10(tf)) * log10(N/df)\n", " where tf = term frequency, N = number of documents, df = document frequency\n", " \"\"\"\n", " print(\"Calculating tf-idf...\")\n", " self.tfidf = {}\n", " \n", " # ------------------------------------------------------------------\n", " # TODO: Compute TF-IDF values for all word-document pairs.\n", " # Store the results in self.tfidf as a nested dictionary:\n", " # self.tfidf[word][doc_id] = tfidf_value\n", " # \n", " # Useful values:\n", " # * self.vocab = list of all unique words\n", " # * self.inv_index = inverted index (word -> doc -> count)\n", " # * len(self.docs) = number of documents (N)\n", "\n", " # YOUR CODE HERE\n", "\n", " # ------------------------------------------------------------------\n", "\n", " def get_tfidf(self, word, document):\n", " \"\"\"\n", " Return the TF-IDF weight for a word in a specific document.\n", " \"\"\"\n", " # ------------------------------------------------------------------\n", " # TODO: Return the TF-IDF value for the given word and document index.\n", " # Return 0 if the word is not in the vocabulary or not in\n", " # the specified document.\n", " tfidf = 0.0\n", " # ------------------------------------------------------------------\n", " return tfidf\n", "\n", " def get_tfidf_unstemmed(self, word, document):\n", " \"\"\"\n", " Given a word, this *stems* the word and then calls get_tfidf on the\n", " stemmed word to get its TF-IDF value. You should *not* need to change\n", " this function. It is needed for submission.\n", " \"\"\"\n", " word = self.p.stem(word)\n", " return self.get_tfidf(word, document)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Spot Check: TF-IDF" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# === Spot Check: TF-IDF ===\n", "# Run this cell after implementing compute_tfidf() and get_tfidf()\n", "\n", "# Create a temporary test instance\n", "_test_ir = IRSystem()\n", "_test_ir.read_data('./data/ProjectGutenberg')\n", "_test_ir.index()\n", "_test_ir.compute_tfidf()\n", "\n", "epsilon = 1e-4\n", "\n", "# Check 1: tfidf should exist\n", "assert hasattr(_test_ir, 'tfidf'), \"ERROR: tfidf not found! Make sure you create self.tfidf\"\n", "\n", "# Check 2: TF-IDF for \"drawer\" in doc 24 should be approximately 0.995\n", "tfidf = _test_ir.get_tfidf(\"drawer\", 24)\n", "expected = 0.9950853045539215\n", "assert abs(tfidf - expected) < epsilon, f\"ERROR: TF-IDF for 'drawer' in doc 24 should be ~{expected}, got {tfidf}\"\n", "\n", "# Check 3: TF-IDF for \"drawer\" in doc 33 should be approximately 1.022\n", "tfidf = _test_ir.get_tfidf(\"drawer\", 33)\n", "expected = 1.0218318713091326\n", "assert abs(tfidf - expected) < epsilon, f\"ERROR: TF-IDF for 'drawer' in doc 33 should be ~{expected}, got {tfidf}\"\n", "\n", "# Check 4: TF-IDF for non-existent word should return 0\n", "tfidf = _test_ir.get_tfidf(\"fizzbuzz\", 0)\n", "assert tfidf == 0, f\"ERROR: TF-IDF for non-existent word should be 0, got {tfidf}\"\n", "\n", "# Check 5: TF-IDF for word not in document should return 0\n", "tfidf = _test_ir.get_tfidf(\"drawer\", 0)\n", "assert tfidf == 0, f\"ERROR: TF-IDF for word not in document should be 0, got {tfidf}\"\n", "\n", "print(\"All spot checks passed for compute_tfidf() and get_tfidf()!\")\n", "del _test_ir # Clean up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 4: Rank Retrieve\n", "\n", "Now, we will implement `rank_retrieve`. This function returns a rank-ordered list of the top documents for a given query using **cosine similarity** between the query and document TF-IDF vectors.\n", "\n", "**Cosine Similarity Formula:** `cosine(q, d) = (q · d) / (||q|| × ||d||)`\n", "\n", "where `q` is the query vector, `d` is the document vector, and `||·||` denotes the L2 norm (length) of the vector.\n", "\n", "You should:\n", "1. Compute TF weights for query terms: `tf_query = 1 + log10(count)`\n", "2. Use TF-IDF weights for document terms (from Part 3)\n", "3. Normalize by both the query AND document vector lengths (L2 norms)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def rank_retrieve(self, query):\n", " \"\"\"\n", " Given a query (a list of words), return a rank-ordered list of\n", " documents (by ID) and score for the query.\n", " \"\"\"\n", " scores = [0.0 for xx in range(len(self.titles))]\n", " # ------------------------------------------------------------------\n", " # TODO: Implement cosine similarity between a document and a list of\n", " # query words.\n", "\n", " # Right now, this code is a placeholder that simply gets the score by\n", " # taking the Jaccard similarity between the query and every document. \n", " # Please replace with your implementation of cosine similarity-based \n", " # retrieval.\n", " # HINT: you can make use of Counter from collections\n", " words_in_query = set()\n", " for word in query:\n", " words_in_query.add(word)\n", "\n", " for d, words_in_doc in self.docs.items():\n", " scores[d] = len(words_in_query.intersection(words_in_doc)) \\\n", " /float(len(words_in_query.union(words_in_doc)))\n", " # ------------------------------------------------------------------\n", "\n", " ranking = [idx for idx, sim in sorted(enumerate(scores),\n", " key=lambda xx: xx[1],\n", " reverse=True)]\n", " results = []\n", " for i in range(10):\n", " results.append((ranking[i], scores[ranking[i]]))\n", " return results" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Spot Check: `rank_retrieve()`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# === Spot Check: rank_retrieve() (Cosine Similarity) ===\n", "# Run this cell after implementing rank_retrieve() to verify your implementation\n", "\n", "# Create a temporary test instance\n", "_test_ir = IRSystem()\n", "_test_ir.read_data('./data/ProjectGutenberg')\n", "_test_ir.index()\n", "_test_ir.compute_tfidf()\n", "\n", "# Helper to stem a query string\n", "def stem_query(ir, query_str):\n", " query = query_str.lower().split()\n", " return [ir.p.stem(word) for word in query]\n", "\n", "epsilon = 1e-4\n", "\n", "# Check 1: \"chest of drawers\" top result should be doc 24 (Metamorphosis)\n", "query = stem_query(_test_ir, \"chest of drawers\")\n", "results = _test_ir.rank_retrieve(query)\n", "top_doc, top_score = results[0]\n", "assert top_doc == 24, f\"ERROR: Top doc for 'chest of drawers' should be 24, got {top_doc}\"\n", "\n", "# Check 2: Score should be approximately 0.0331 (vanilla cosine)\n", "expected_score = 0.033118100770043575\n", "assert abs(top_score - expected_score) < epsilon, f\"ERROR: Score should be ~{expected_score}, got {top_score}\"\n", "\n", "# Check 3: \"pumpkin pies\" top result should be doc 41 (Legend of Sleepy Hollow)\n", "query = stem_query(_test_ir, \"pumpkin pies\")\n", "results = _test_ir.rank_retrieve(query)\n", "top_doc, top_score = results[0]\n", "assert top_doc == 41, f\"ERROR: Top doc for 'pumpkin pies' should be 41, got {top_doc}\"\n", "\n", "# Check 4: Score should be approximately 0.0777 (vanilla cosine)\n", "expected_score = 0.07769755389348589\n", "assert abs(top_score - expected_score) < epsilon, f\"ERROR: Score should be ~{expected_score}, got {top_score}\"\n", "\n", "# Check 5: Results should be in descending order by score\n", "query = stem_query(_test_ir, \"the cold breeze\")\n", "results = _test_ir.rank_retrieve(query)\n", "scores = [score for doc, score in results]\n", "assert scores == sorted(scores, reverse=True), \"ERROR: Results should be sorted by score descending\"\n", "\n", "print(\"All spot checks passed for rank_retrieve()!\")\n", "del _test_ir # Clean up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 5: Dense Retrieval\n", "\n", "Modern information retrieval systems often use **dense retrieval** — representing documents and queries as dense vectors (embeddings) from neural language models like BERT, rather than sparse TF-IDF vectors.\n", "\n", "We have pre-computed BERT embeddings for all 60 books and the development queries. These embeddings capture semantic meaning, so documents about similar topics will have similar embeddings even if they don't share exact words.\n", "\n", "Your task:\n", "1. Implement `cosine_similarity_dense` to compute cosine similarity between two dense vectors\n", "2. Implement `dense_retrieve` to return the top-k documents most similar to a query embedding" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "# Load pre-computed BERT embeddings\n", "# doc_embeddings: shape (60, 384) - one embedding per book\n", "# query_embeddings: shape (num_queries, 384) - one embedding per dev query\n", "# query_texts: list of query strings corresponding to query_embeddings\n", "\n", "doc_embeddings = np.load('./data/embeddings/doc_embeddings.npy')\n", "query_embeddings = np.load('./data/embeddings/query_embeddings.npy')\n", "with open('./data/embeddings/query_texts.txt', 'r') as f:\n", " query_texts = [line.strip() for line in f.readlines()]\n", "\n", "print(f\"Loaded {doc_embeddings.shape[0]} document embeddings of dimension {doc_embeddings.shape[1]}\")\n", "print(f\"Loaded {query_embeddings.shape[0]} query embeddings\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def cosine_similarity_dense(self, vec1, vec2):\n", " \"\"\"\n", " Compute the cosine similarity between two dense vectors.\n", " \n", " Args:\n", " vec1: numpy array of shape (d,)\n", " vec2: numpy array of shape (d,)\n", " \n", " Returns:\n", " float: cosine similarity between vec1 and vec2\n", " \"\"\"\n", " # ------------------------------------------------------------------\n", " # TODO: Implement cosine similarity for dense vectors.\n", " # Hint: This should be ~1-2 lines of code using numpy operations.\n", " # Remember: cosine_similarity = (a · b) / (||a|| * ||b||)\n", " \n", " return 0.0\n", " # ------------------------------------------------------------------\n", "\n", "\n", " def dense_retrieve(self, query_embedding, doc_embeddings, titles, k=5):\n", " \"\"\"\n", " Given a query embedding and document embeddings, return the top-k \n", " most similar documents.\n", " \n", " Args:\n", " query_embedding: numpy array of shape (d,) - the query vector\n", " doc_embeddings: numpy array of shape (n, d) - all document vectors\n", " titles: list of document titles (length n)\n", " k: number of top documents to return\n", " \n", " Returns:\n", " list of tuples: [(doc_id, title, score), ...] for top-k documents,\n", " sorted by similarity score (highest first)\n", " \"\"\"\n", " # ------------------------------------------------------------------\n", " # TODO: Implement dense retrieval.\n", " # 1. Compute cosine similarity between query and all documents\n", " # 2. Find the top-k documents by similarity\n", " # 3. Return list of (doc_id, title, score) tuples\n", " # Hint: Consider using np.argsort() and remember to sort descending!\n", " \n", " results = []\n", " \n", " return results\n", " # ------------------------------------------------------------------" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Spot Check: Dense Retrieval" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# === Spot Check: Dense Retrieval ===\n", "# Run this cell after implementing cosine_similarity_dense() and dense_retrieve()\n", "\n", "# Create a temporary test instance\n", "_test_ir = IRSystem()\n", "_test_ir.read_data('./data/ProjectGutenberg')\n", "_test_ir.index()\n", "\n", "epsilon = 1e-4\n", "\n", "# Check 1: Cosine similarity of identical vectors should be 1.0\n", "vec1 = np.array([1.0, 0.0, 0.0])\n", "vec2 = np.array([1.0, 0.0, 0.0])\n", "sim = _test_ir.cosine_similarity_dense(vec1, vec2)\n", "assert abs(sim - 1.0) < epsilon, f\"ERROR: Cosine similarity of identical vectors should be 1.0, got {sim}\"\n", "\n", "# Check 2: Cosine similarity of orthogonal vectors should be 0.0\n", "vec1 = np.array([1.0, 0.0, 0.0])\n", "vec2 = np.array([0.0, 1.0, 0.0])\n", "sim = _test_ir.cosine_similarity_dense(vec1, vec2)\n", "assert abs(sim - 0.0) < epsilon, f\"ERROR: Cosine similarity of orthogonal vectors should be 0.0, got {sim}\"\n", "\n", "# Check 3: Cosine similarity of opposite vectors should be -1.0\n", "vec1 = np.array([1.0, 0.0, 0.0])\n", "vec2 = np.array([-1.0, 0.0, 0.0])\n", "sim = _test_ir.cosine_similarity_dense(vec1, vec2)\n", "assert abs(sim - (-1.0)) < epsilon, f\"ERROR: Cosine similarity of opposite vectors should be -1.0, got {sim}\"\n", "\n", "# Check 4: dense_retrieve for query 0 (\"chest of drawers\") should return doc 14 as top result\n", "results = _test_ir.dense_retrieve(query_embeddings[0], doc_embeddings, _test_ir.titles, k=1)\n", "top_doc_id, top_title, top_score = results[0]\n", "assert top_doc_id == 14, f\"ERROR: Top doc for query 0 should be 14, got {top_doc_id}\"\n", "\n", "# Check 5: Score should be approximately 0.2902\n", "expected_score = 0.29019150137901306\n", "assert abs(top_score - expected_score) < epsilon, f\"ERROR: Score should be ~{expected_score}, got {top_score}\"\n", "\n", "# Check 6: Results should have correct format (doc_id, title, score)\n", "results = _test_ir.dense_retrieve(query_embeddings[0], doc_embeddings, _test_ir.titles, k=3)\n", "assert len(results) == 3, f\"ERROR: Should return 3 results, got {len(results)}\"\n", "assert isinstance(results[0][0], (int, np.integer)), \"ERROR: First element of tuple should be int (doc_id)\"\n", "assert isinstance(results[0][1], str), \"ERROR: Second element of tuple should be str (title)\"\n", "assert isinstance(results[0][2], (float, np.floating)), \"ERROR: Third element of tuple should be float (score)\"\n", "\n", "print(\"All spot checks passed for dense retrieval!\")\n", "del _test_ir # Clean up" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's also add a few methods that given a string, will process and then return the list of matching documents for the different methods you have implemented. You do not need to add any additional code here." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem): \n", " def process_query(self, query_str):\n", " \"\"\"\n", " Given a query string, process it and return the list of lowercase,\n", " alphanumeric, stemmed words in the string.\n", " \"\"\"\n", " # make sure everything is lower case\n", " query = query_str.lower()\n", " # split on whitespace\n", " query = query.split()\n", " # remove non alphanumeric characters\n", " query = [self.alphanum.sub('', xx) for xx in query]\n", " # stem words\n", " query = [self.p.stem(xx) for xx in query]\n", " return query\n", "\n", " def query_rank(self, query_str):\n", " \"\"\"\n", " Given a string, process and then return the list of the top matching\n", " documents, rank-ordered.\n", " \"\"\"\n", " query = self.process_query(query_str)\n", " return self.rank_retrieve(query)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "irsys = IRSystem()\n", "irsys.read_data('./data/ProjectGutenberg')\n", "irsys.index()\n", "irsys.compute_tfidf()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's compare your TF-IDF cosine similarity results with dense retrieval results on the same queries. This will help you see how the two approaches differ in what they consider \"similar\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def compare_retrieval_methods(irsys, query_text, query_embedding, doc_embeddings, k=5):\n", " \"\"\"\n", " Compare TF-IDF and dense retrieval results for the query \"machine learning is cool\".\n", " \"\"\"\n", " print(\"=\" * 80)\n", " print(\"COMPARING TF-IDF vs DENSE RETRIEVAL\")\n", " print(\"=\" * 80)\n", " \n", " print(f\"\\nQuery: '{query_text}'\")\n", " print(\"-\" * 40)\n", " \n", " # TF-IDF results\n", " tfidf_results = irsys.query_rank(query_text)[:k]\n", " print(f\"\\nTF-IDF Top-{k}:\")\n", " for rank, (doc_id, score) in enumerate(tfidf_results, 1):\n", " print(f\" {rank}. {irsys.titles[doc_id]} (score: {score:.4f})\")\n", " \n", " # Dense retrieval results\n", " dense_results = irsys.dense_retrieve(query_embedding, doc_embeddings, irsys.titles, k=k)\n", " print(f\"\\nDense Retrieval Top-{k}:\")\n", " for rank, (doc_id, title, score) in enumerate(dense_results, 1):\n", " print(f\" {rank}. {title} (score: {score:.4f})\")\n", " print(\"=\" * 80)\n", "\n", "# Run the comparison with just \"machine learning is cool\"\n", "compare_retrieval_methods(irsys, \"machine learning is cool\", query_embeddings[1], doc_embeddings)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 6: Comparing Retrieval Methods\n", "\n", "Look at the results above for the query \"machine learning is cool\".\n", "\n", "**Your task:** In 3-5 sentences, reflect on the differences between TF-IDF and dense retrieval. What are the strengths and weaknesses of each approach? When might you prefer one over the other?\n", "\n", "*Hint: Think about the difference between **lexical matching** (matching based on exact words) and **semantic matching** (matching based on meaning). How does each method decide what counts as a \"match\"?*" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def reflection_on_retrieval_methods(self):\n", " # TODO: Place your response into the response string below\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 7: Running the Full IR System\n", "\n", "You can use the `run_tests` and `run_query` functions to test your code. `run_tests` tests how different components of your search engine code perform on a small set of queries and checks whether or not it matches up with our solution's results. `run_query` can be used to test your code on individual queries. \n", "\n", "Note that the first run for either of these functions might take a little while, since it will stem all the words in every document and create a directory named `stemmed/` in `../data/ProjectGutenberg/`. This is meant to be a simple cache for the stemmed versions of the text documents. Later runs will be much faster after the first run since all the stemming will already be completed. However, this means that **if something happens during this first run and it does not get through processing all the documents, you may be left with an incomplete set of documents in `../data/ProjectGutenberg/stemmed/`. If this happens, simply remove the `stemmed/` directory and re-run!**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def run_tests(irsys):\n", " print(\"===== Running tests =====\")\n", "\n", " ff = open('./data/dev_queries.txt')\n", " questions = [xx.strip() for xx in ff.readlines()]\n", " ff.close()\n", " ff = open('./data/dev_solutions.txt')\n", " solutions = [xx.strip() for xx in ff.readlines()]\n", " ff.close()\n", "\n", " epsilon = 1e-4\n", " for part in range(5):\n", " points = 0\n", " num_correct = 0\n", " num_total = 0\n", "\n", " prob = questions[part]\n", " soln = json.loads(solutions[part])\n", " \n", "\n", " if part == 0: # inverted index test (counts)\n", " print(\"Inverted Index Test\")\n", " queries = prob.split(\"; \")\n", " queries = [xx.split(\", \") for xx in queries]\n", " queries = [(xx[0], int(xx[1])) for xx in queries]\n", " for i, (word, doc) in enumerate(queries):\n", " num_total += 1\n", " # Get count from inverted index\n", " word_stemmed = irsys.p.stem(word)\n", " count = irsys.inv_index.get(word_stemmed, {}).get(doc, 0)\n", " if count == soln[i]:\n", " num_correct += 1\n", "\n", " elif part == 1: # get postings test\n", " print(\"Get Postings Test\")\n", " words = prob.split(\", \")\n", " for i, word in enumerate(words):\n", " num_total += 1\n", " posting = irsys.get_posting_unstemmed(word)\n", " if posting == soln[i]:\n", " num_correct += 1\n", "\n", " elif part == 2: # tfidf test\n", " print(\"TF-IDF Test\")\n", " queries = prob.split(\"; \")\n", " queries = [xx.split(\", \") for xx in queries]\n", " queries = [(xx[0], int(xx[1])) for xx in queries]\n", " for i, (word, doc) in enumerate(queries):\n", " num_total += 1\n", " guess = irsys.get_tfidf_unstemmed(word, doc)\n", " if guess >= float(soln[i]) - epsilon and \\\n", " guess <= float(soln[i]) + epsilon:\n", " num_correct += 1\n", "\n", " elif part == 3: # cosine similarity test\n", " print(\"Cosine Similarity Test\")\n", " queries = prob.split(\", \")\n", " for i, query in enumerate(queries):\n", " num_total += 1\n", " ranked = irsys.query_rank(query)\n", " top_rank = ranked[0]\n", " if top_rank[0] == soln[i][0]:\n", " if top_rank[1] >= float(soln[i][1]) - epsilon and \\\n", " top_rank[1] <= float(soln[i][1]) + epsilon:\n", " num_correct += 1\n", "\n", " elif part == 4: # dense retrieval test\n", " print(\"Dense Retrieval Test\")\n", " queries = prob.split(\", \")\n", " for i, query in enumerate(queries):\n", " num_total += 1\n", " results = irsys.dense_retrieve(query_embeddings[i], doc_embeddings, irsys.titles, k=1)\n", " if len(results) > 0:\n", " top_result = results[0] # (doc_id, title, score)\n", " if top_result[0] == soln[i][0]:\n", " if top_result[2] >= float(soln[i][1]) - epsilon and \\\n", " top_result[2] <= float(soln[i][1]) + epsilon:\n", " num_correct += 1\n", "\n", " feedback = \"%d/%d Correct. Accuracy: %f\" % \\\n", " (num_correct, num_total, float(num_correct) / num_total)\n", "\n", " if part == 1:\n", " if num_correct == num_total:\n", " points = 2\n", " elif num_correct >= 0.5 * num_total:\n", " points = 1\n", " else:\n", " points = 0\n", " else:\n", " if num_correct == num_total:\n", " points = 3\n", " elif num_correct > 0.75 * num_total:\n", " points = 2\n", " elif num_correct > 0:\n", " points = 1\n", " else:\n", " points = 0\n", "\n", " print(\" Score: %d Feedback: %s\" % (points, feedback))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Run this cell to run the tests\n", "run_tests(irsys)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def run_query(query):\n", " irsys = IRSystem()\n", " irsys.read_data('./data/ProjectGutenberg')\n", " irsys.index()\n", " irsys.compute_tfidf()\n", " \n", " print(\"Best matching documents to '%s':\" % query)\n", " results = irsys.query_rank(query)\n", " for docId, score in results:\n", " print(\"%s: %e\" % (irsys.titles[docId], score))\n", " \n", "# Run any query you want!\n", "run_query(\"My very own query\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For reference, you can run the cell below to see the titles of all the documents in our dataset. As spot checks, you can try tailoring your queries in `run_query` to output certain titles and/or checking what IR system outputs against the list of titles to see if the results make sense (i.e. the book _Great Pianists on Piano Playing_ should probably be among the top results if the query is \"pianists play piano\")." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Prints full list of book titles in dataset (in alphabetical order)\n", "for i in range(len(irsys.titles)):\n", " print(\"%d. %s\" % (i + 1, irsys.titles[i]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 8: Ethics" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Identity & Representation\n", "\n", "Safiya Umoja Noble's Algorithms of Oppression (2018) argues that search engines are not neutral portals of information; rather, they can reinforce racist and sexist biases through their ranking systems. Noble demonstrates how prejudice against black women is embedded into search engine ranked results. These biases are apparent in both Google search’s autosuggestions and the first page of Google results. For example, for years, image searches for the word \"hacker\" predominantly showed white men in hoodies, while searches for \"CEO\" rarely featured women or people of color. These results are influential in how we construct and perceive our own identities." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1.) Choose a term that describes an aspect of your identity or a role you embody (e.g., your race, gender, major, extracurriculars, or a specific community). Make a prediction as to what groups or characteristics will be strongly represented in the first page of a Google Search of this term. Then, perform the Google search and look at the first set of results. How do these results compare to your predictions? Are they representative of your lived experiences? Do they reflect the full diversity of people you see in this group in real life? How might this influence people’s conceptions of people who hold this identity? How might this be good or bad? " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def algorithmic_bias_in_IR_systems(self):\n", " # TODO: Place your response into the response string below\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2.) Some argue that a search engine's outputs should act as a \"mirror\": reflecting the world exactly as it is, meaning it is okay for outputs to be represented proportional to how they exist in the real world. Others think this could be too narrow, reinforcing the world’s existing inequalities, and instead argue for \"aspiration\" as a different form of representation: deliberately boosting diverse results to provide a more inclusive view. What do you think should be the default from search engine results? Should people be able to manually control these defaults? Make a convincing argument (2-3 sentences) as to why. If you are pair programming you may surface different perspectives from your partner, which is also a fine thing to talk about! Remember to be respectful! " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def mirror_vs_aspiration(self):\n", " # TODO: Place your response into the response string below\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Filter Bubbles & Personalized Ranking\n", "\n", "In this assignment, your IR system ranks documents identically for every user. However, commercial search engines use personal data (browsing history, location, interests) to tailor results. While this can increase relevance, it can trap users in a filter bubble, where they only see information that confirms their existing beliefs.\n", "\n", "1.) Compare search results for a localized or debated term (e.g., \"best hair salon,\" \"is coffee healthy,\" or \"impact of [current news event]\") with a peer or by using an incognito window.
\n", " • What differences do you notice in the top 5 results?
\n", " • How might these differences arise from leveraging personal data in the ranking algorithm?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def filter_bubble_experience(self):\n", " # TODO: Place your response into the response string below\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2.) As a developer, how much tailoring is too much? PageRank and TF-IDF are mathematical foundations, but the weights chosen for personalization are ethical, value-laden choices.
\n", " • What kinds of personal data should be allowed to influence a ranking algorithm for news or social issues?
\n", " • Should a system be allowed to make inferences about your own identities? Which ones? Should it have to provide justification for this?
\n", " • Should an algorithm be required to allow users to \"break out\" of their filter bubble by intentionally inserting dissenting or diverse viewpoints into their top results?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class IRSystem(IRSystem):\n", " def personalization_ethics(self):\n", " # TODO: Place your response into the response string below\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once you're ready to submit, you can run the cell below to prepare and zip\n", "up your solution:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%%bash\n", "\n", "if [[ ! -f \"./pa3.ipynb\" ]]\n", "then\n", " echo \"WARNING: Did not find notebook in Jupyter working directory. This probably means you're running on Google Colab. You'll need to go to File->Download .ipynb to download your notebook and other files, then zip them locally. See the README for more information.\"\n", "else\n", " echo \"Found notebook file, creating submission zip...\"\n", " rm -f submission.zip\n", " zip -r submission.zip pa3.ipynb deps/\n", "fi" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If you're running on Google Colab, see the README for instructions on\n", "how to submit.\n", "\n", "__Best of luck!__\n", "\n", "__Some reminders for submission:__\n", "* If you have any extra files required for your implementation to work, make\n", " sure they are in a `deps/` folder on the same level as `pa3.ipynb` and\n", " include that folder in your submission zip file.\n", " * Make sure you didn't accidentally change the name of your notebook file,\n", " (it should be `pa3.ipynb`) as that is required for the autograder to work.\n", "* Go to Gradescope (gradescope.com), find the PA3 IR assignment and\n", "upload your zip file (`submission.zip`) as your solution.\n", "* Wait for the autograder to run (it should only take a minute or so) and check\n", "that your submission was graded successfully! If the autograder fails, or you\n", "get an unexpected score it may be a sign that your zip file was incorrect." ] } ], "metadata": { "kernelspec": { "display_name": "cs124", "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.10.19" } }, "nbformat": 4, "nbformat_minor": 1 }