Project 3, part 2: Searching using TF-IDF

Due

In parts 2 and 3, you will use the data structures and algorithms you implemented so far to build a basic search engine similar to Google Search or Microsoft Bing.

Note that we have NOT covered the algorithm for doing this in class: part of the challenge is figuring out how to implement new algorithms based mainly on a written description. If you're running into issues or have questions, we strongly encourage you to come to office hours.

General overview

High-level context

A search engine is, in a nutshell, an algorithm that accepts a query from the user and computes how relevant a given document is to that query.

In our case, a query is whatever the user types into our search engine, and each individual web page is a single document.

Industrial strength search engines work by combining hundreds of different algorithms for computing relevance, but we will implement just two: Term Frequency and Inverse Document Frequency (TF-IDF) with Cosine Similarity ranking, and (in part 3) PageRank.

Detailed descriptions of these algorithms are included later in this spec.

Getting webpages

Our search engine won't be capable of searching the entire internet: we need to download a copy of every single webpage in existence to do that, which is probably not feasible.

Instead, we'll have our search engine work against a much smaller subset of the internet that we've downloaded for you. Take a look at your project3/data folder. It contains several different folders: each one represents a different "snapshot" or "fraction" of the internet.

When setting up your search engine, you must pick one of these "snapshots": your engine will search for only the documents listed in that folder. These snapshots vary in size. The smaller ones (such as 'simple-web-xx') folders are meant to help with testing, the larger ones (such as 'wikipedia') are meant to help with stress-testing.

You can find more info about each snapshots in the project3/data/README.md file.

Part 2a: Run the search engine

Task: make sure you can run the search engine.

We will first start by making sure you can run the search engine so you can test your results as you go.

First, open the Main.java file, which is located within the search package. The only thing you really need to care in this file is the first DATA_FOLDER_NAME constant at the top of the class.

This constant must be the name of one of the folders in the project3/data folder. You should change this constant when testing your code, but for now, it's ok to leave it alone.

Next, run Main.java (which is located inside the search package). It may take a few seconds for the search engine to load the files, depending on which data folder you're looking at. Once it's ready, visit the link printed to the console in your web browser – it should be something like http://localhost:8080.

Hopefully, you should see a working website! Make sure everything works by running a few queries. Since we haven't implemented the actual search algorithm yet, the results will be in no particular order, but you should see some results appear nearly instantaneously.

Dealing with out-of-memory errors or slow loading times

For some of the larger datasets ("wikipedia" and "wikipedia-with-spam"), you may run into out-of-memory issues or very slow loading times – specifically, you may see Java throw an java.lang.OutOfMemoryError.

This error can occur because our search engine will attempt to load all of the web pages in the dataset into memory -- if we want to load many data pages, we may end up needing to allocate more memory then Java permits by default.

To fix this, do the following:

  1. In the top bar in Eclipse, click Run then Run Configurations.
  2. On the left pane, under Java Applications, select the application that's giving you the error. Here, it's the Main application.
  3. One you have selected the right application, click the Arguments tab on the right.
  4. Under VM Arguments, add the text "-Xmx4G" (without quotation marks). This will allow Eclipse to grow the heap size up to 4 GB of memory.
  5. Click Run. This will save the setting and run your program again.

What is "localhost"? What is a port?

The URL you're asked to visit ("http://localhost:8080") may look a little different then what you're used to.

First, notice that we're using the word "localhost" instead of the name of some website. This is because we're running your search engine locally on your computer: the word "localhost" is a shorthand for "this computer".

Next, we add a colon and some numbers to the end. Those numbers are a port. In short, every program that wants to communicate over the network (games, your email client, chat clients...) must select a unique port number. Then, when somebody wants to send data to a particular program, they need to include that port number with the data. That way, when the operating recieves the data packet, it knows which program to send that packet to.

Websites, by convention, will use specific ports (port 80 for HTTP websites and port 443 for HTTPS), but using those ports typically requires special permission from the operating system.

(This is why we can normally omit the port number when typing web addresses: our web browsers are smart enough to automatically use one of these two default port numbers.)

This can be a hassle, so we configured our search engine to use an arbitrary port number (8080) that doesn't require permissions from your operating system to use and that (hopefully) no other program is currently using.

Part 2b: Implement code to generate a TF-IDF vector

Task: Finish implementing TfIdfAnalyzer's constructor (and all associated helper methods).

The first ranking metric we will write is Term Frequency and Inverse Document Frequency (TF-IDF) ranking. We will start by implementing a method that produces a TF-IDF vector for each document we were given. Each TF-IDF vector contains data on how "important" a given word was to that document.

Core algorithm

To compute the TF-IDF vector for a single document (a webpage), we take that document and compute the TF-IDF score for each unique word. For each unique word, or term, we:

  1. Compute TF: Term Frequency

    The term frequency (TF) is a measure of how frequently a term appears in a document. We compute it using this formula:

    $$\text{TF}(\text{term}, \text{document}) = \frac {\text{Number of times the term appears in doc}} {\text{Total number of words in a doc}}$$

    Notice the more the term appears in the document, the higher the TF score. This hopefully makes intuitive sense: if the user's search query is "donuts" and if the word "donuts" appears many times in the webpage, then the webpage is probably all about donuts and is something the user will want to read.

  2. IDF: Inverse Document Frequency

    The inverse document frequency (IDF) measures how frequently a term appears in all documents using this formula. (Note: here, \(\ln\) is \(\log\) base \(e\)).

    $$\text{IDF}(\text{term}) = \begin{cases} 0 & \text{if term doesn't appear in any doc} \\ \ln\left(\frac {\text{Total number of docs}} {\text{Number of docs containing the term}} \right) & \text{Otherwise} \end{cases} $$

    Note that when computing the TF for a particular term, we'll obtain a different TF per each document. In contrast, when computing IDF, we do so by looking at every single document, rather then any single one.

    Also notice that if a word appears in many different documents, the IDF score is smaller. This is because we don't want really common words like "the" or "of" to really be distinguishing factor of any document.

    We take the log because it seems to work well in practice: statistically, only a small handful of words will be common across a majority of documents and we want to penalize those words more.

    (If you'd like to learn more about the underlying theoretical justification for IDF's formula, see this research paper.)

  3. Combined TF-IDF score

    Finally, we compute the final TF-IDF relevance score for the term by multiplying the two above numbers together:

    $$\text{Relevance}(\text{term}, \text{document}) = \text{TF}(\text{term}, \text{document}) \times \text{IDF}(\text{term})$$

We store each term and its corresponding TF-IDF score for a particular document inside a IDictionary<String, Double>. This dictionary is the TF-IDF vector.

The TfIdfAnalyzer.computeAllDocumentTfIdf(...) method is responsible for computing the TF-IDF vector for every document: it should return a IDictionary<URI, IDictionary<String, Double>>.

We will store the resulting dictionary in a field for later use.

Example

Let's try running through an example of computing TF-IDF in action.

Suppose our search engine contained the following three documents (a.k.a. three webpages):

We compute the TF-IDF vector for each document like so:

$$ \newcommand{\Relevance}[2]{\text{Relevance}(\text{#1},\, \text{Doc}_{#2})} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\logp}[1]{\ln\left(#1\right)} \newcommand{\expr}[4]{\f{#1}{#2} \times \logp{\f{#3}{#4}}} $$

Ultimately, we'll obtain a unique TF-IDF vector for each document. We'll use these vectors in the next subpart.

Other notes and hints.

Computing the TF and IDF scores for a single document can be somewhat expensive: not only do we need to loop through the entire document word-by-word to compute the TF, we need to loop through every single document in our search engine to compute the IDF.

To help make this more efficient, you should precompute as much information as possible. For more details on how to do so, see the comments in TfIdfAnalyzer's constructor.

Part 2c: Implement cosine similarity

Task: Finish implementing TfIdfAnalyzer.computeRelevance(...).

Next, we will implement the logic to actually determine how relevant an algorithm is to a query.

Core logic

To compare a query against a document, we will need to perform three steps:

  1. Find the TF-IDF vector for the document. This should be an easy, \(O(1)\) lookup since we already computed the TF-IDF vector for that document in part 2b.

  2. Compute the TF-IDF vector for the query. You should be able to reuse the bulk of the code you wrote in part 3b to do this (though you may have to do some mild refactoring).

    Note: technically, we are treating the query as if it were a new document. However, you should not recompute the IDF values: just use the ones you computed earlier.

  3. Compute the cosine similarity between the document vector and the query vector.

    We will do this by comparing the TF-IDF vector for your query against all the document TF-IDF vectors and compute how similar your query vector is to each document by exploiting properties of the cosine function and the dot product.

    However, since not everybody may have taken math classes about this kind of material, we will instead just provide you with the pseudocode for this material instead:

    double computeRelevance(query, pageUri):
    documentVector = look up document TF-IDF vector using pageUri
    queryVector = compute query TF-IDF vector

    numerator = 0.0
    foreach word in query:
        docWordScore = if   documentVector.containsKey(word)
                       then documentVector.get(word) 
                       else 0.0
        queryWordScore = queryVector.get(word)
        numerator += docWordScore * queryWordScore
    
    denominator = norm(documentVector) * norm(queryVector)

    if   denominator != 0
    then return numerator / denominator
    else return 0.0

double norm(vector):
    output = 0.0
    foreach pair in vector:
        score = pair.getValue()
        output += score * score
    return sqrt(output)

  4. Make the pseudocode more efficient.

    However, the pseudocode we gave you is not particularly efficient: you should be able to combine several loops and precompute some pieces of information needed by this method.

    When implementing this method, you should add at least one other field to your TfIdfAnalyzer class containing information you can precompute. Modify your constructor to precompute and store this information.

Why is this called "cosine" similarity? Why does this work?

Ok, here's what's actually happening.

The document and query vectors we're computing are in reality vectors of length \(n\), where \(n\) is the number of unique words across all the documents and the current query. Each "index" of the vector corresponds to a specific word and stores the TF-IDF score for that term.

We represent this vector using a dictionary because our vector is likely to be sparse: if we have many documents, an arbitrary vector is likely to contain zero scores for most of the \(n\) words.

On a higher level, what we've basically done is figured out how to convert our (text) document and query into mathematical vectors. We can now apply loads of interesting mathematical properties to manipulate this representation of our document in query.

In particular, we're interested in trying to measure how "similar" two vectors are. We'll do so by attempting to find the "angle" between our query and document vectors: the smaller the angle, the more similar the two are.

To do this, we can take advantage of the following identity:

$$ \textbf{a} \cdot \textbf{b} = ||\textbf{a}|| \, ||\textbf{b}|| \cos(\theta) $$

...where \(\textbf{a}\) and \(\textbf{b}\) are vectors, the \(\cdot\) operation is the dot product, and \(||\textbf{a}||\) is the magnitude of the vector (we take the Euclidean norm here).

We then rearrange and compute the following:

$$ \cos(\theta) = \frac{\textbf{a} \cdot \textbf{b}}{||\textbf{a}|| \, ||\textbf{b}||} $$

We then use the computed value for \(\cos(\theta)\) as our similarity score.

We don't bother taking the arccosine of this quantity because it'll just perform the same transformation on all of our scores, which is a waste of time. We also get to preserve the property that similar vectors will have a higher score, and that all scores will fall between 0.0 and 1.0 (since every score in our vector is positive).

We must, however, handle one edge case: where one or both of the norms are equal to zero. This happens when the user query uses completely unique words that were never before seen in any document, for example. In this case, the output of the cosine similarity metric is undefined, since we're dividing by zero. However, if the query contains no previously seen words, we're not going to be able to classify anything anyways, so we effectively give up and just return 0.0 as a placeholder value.

Part 2d: Re-run your search engine

Task: Try running your search engine again.

After completing the previous parts, try running your search engine again on the different data folders.

As before, it may take some time for your search engine to finish loading all the pages and finish setting up your TF-IDF analyzer. However, once everything is set up, your search engine should be able to answer queries nearly instantaneously.

But unlike before, your engine should be doing much better this time! You should be getting back mostly reasonable results. The one exception should be if you select the "wikipedia-with-spam" data folder. If you try picking this folder, you may see links to a few spam websites interspersed with the wikipedia links we care about.

More specifically, we've inserted two spam webpages – one related to computer science, and another related to Seattle. Try running searches related to those two things! (E.g. try searching "computer science", "seattle", "seattle times", etc). Our fake spam pages won't necessarily be the very first result, but they should consistently appear near the top.

You should think about why that is. What are these webpages doing to artifically inflate their ranking results?

You'll implement an algorithm to deal with this problem in part 3 of this project.

Deliverables

The following deliverables are due on .

A single person from your partnership should turn in a zip file containing the entire contents of your src folder on Canvas.

Please follow the above instructions EXACTLY. In particular, DO NOT rename your "src" folder before zipping it or modify the folder structure in any way.

Before submitting, be sure to double-check and make sure that...