coursera/text-retrieval-and-search-engines/notes/week5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 5 Overview\n",
    "\n",
    "During this week's lessons, you will learn feedback techniques in information retrieval, including the Rocchio feedback method for the vector space model, and a mixture model for feedback with language models. You will also learn how web search engines work, including web crawling, web indexing, and how links between web pages can be leveraged to score web pages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key Phrases and Concepts\n",
    "\n",
    "- Relevance feedback\n",
    "- Pseudo-relevance feedback\n",
    "- Implicit feedback\n",
    "- Rocchio feedback\n",
    "- Kullback-Leiber divergence (KL-divergence) retrieval function\n",
    "- Mixture language model\n",
    "- Scalability and efficiency\n",
    "- Spams\n",
    "- Crawler, focused crawling, and incremental crawling\n",
    "- Google File System (GFS)\n",
    "- MapReduce\n",
    "- Link analysis and anchor text\n",
    "- PageRank and HITS "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Goals and Objectives\n",
    "\n",
    "* Explain the similarity and differences in the three different kinds of feedback, i.e., relevance feedback, pseudo-relevance feedback, and implicit feedback.\n",
    "* Explain how the Rocchio feedback algorithm works.\n",
    "* Explain how the Kullback-Leibler (KL) divergence retrieval function generalizes the query likelihood retrieval function.\n",
    "* Explain the basic idea of using a mixture model for feedback.\n",
    "* Explain some of the main general challenges in creating a web search engine.\n",
    "* Explain what a web crawler is and what factors have to be considered when designing a web crawler.\n",
    "* Explain the basic idea of Google File System (GFS).\n",
    "* Explain the basic idea of MapReduce and how we can use it to build an inverted index in parallel.\n",
    "* Explain how links on the web can be leveraged to improve search results.\n",
    "* Explain how PageRank and HITS algorithms work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Guiding Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain the similarity and differences in the three different kinds of feedback, i.e., relevance feedback, pseudo-relevance feedback, and implicit feedback.\n",
    "\n",
    "**Feedback** is any new inputs that caused search engine to learn how to improve relevant of retrieved documents.\n",
    "\n",
    "![Feedback](images/feedback.png)\n",
    "\n",
    "- **Relevance Feedback**: Also known as explicit feedback. User judgement of all retrieved documents from the search engine. In this case, there is no one unjudged document.\n",
    "- **Pseudo Relevance Feedback**: Also known as blind or automatic feedback. This technique assumed that *top k documents always relevant*, then the other documents will be optionally judged.\n",
    "- **Implicit Feedback**: This technique contrast with *Relevance feedback*. This technique collect user activities to make inference how users selecting relevant document or skipping un-relevant document. One simple implementation is *user clickthroughs* which assumed that clicked documents are relevant and skipped documents are un-relevant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain how the Rocchio feedback algorithm works.\n",
    "\n",
    "Let:\n",
    "\n",
    "- $D_r$ is set of relevant document vectors, such as $\\{\\vec{d_i}, ..., \\vec{d_n}\\}$\n",
    "- $D_n$ is set of non relevant document vectors, such as $\\{\\vec{d_i}, ..., \\vec{d_n}\\}$\n",
    "- $\\vec{q}$ is a initial query vector.\n",
    "- $\\vec{q}_m$ is a modified query vector.\n",
    "\n",
    "We know that:\n",
    "\n",
    "- All vectors projected into two dimensional space.\n",
    "- $D_r$ may spread in the space and some of them grouping together as **cluster of relevant $C_r$**\n",
    "- $D_n$ may spread in the space and some of them grouping together as **cluster of non relevant $C_n$**\n",
    "\n",
    "Then:\n",
    "\n",
    "- A Rocchio feedback algorithm aimed to produce $\\vec{q}_m$ from $\\vec{q}$ by moving $\\vec{q}_m$ toward $C_r$.\n",
    "- A basic Rocchio feedback algorithm used linear progression to move $\\vec{q}$ toward $C_r$:\n",
    "\n",
    "$$\\vec{q}_m = \\alpha * \\vec{q} + \\frac{\\beta}{|D_r|} * \\sum\\limits_{\\vec{d_j} \\in D_r} \\vec{d_j} - \\frac{\\gamma}{|D_n|} * \\sum\\limits_{\\vec{d_j} \\in D_n} \\vec{d_j}$$\n",
    "- $\\alpha$, $\\beta$, and $\\gamma$ are weights that control the $\\vec{q}$ acceleration toward $C_r$.\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "**Example**\n",
    "\n",
    "Let:\n",
    "\n",
    "- $V$ is current vocabulary used by search engine.\n",
    "- $V$ is fixed-length term vector.\n",
    "- $\\vec{q}$ contains quantified of term occurences, such that $\\vec{q} = \\{t_1, ..., t_n \\ | \\ t \\in [0,1]\\}$\n",
    "\n",
    "Assume:\n",
    "\n",
    "- $V = \\{\\text{text}, \\text{mining}, \\text{algorithm}, \\text{information}, \\text{retrieval}\\}$\n",
    "- $\\vec{q} = \\{1, 1, 1, 0, 0\\}$\n",
    "- We are give five feedback documents with their term weights, where + indicate relevant, and - indicate non relevant:\n",
    "\n",
    "relevant | document | $\\{ text, mining, algorithm, information, retrieval \\}$ |\n",
    "---------|----------|-------------------------------------------------------|\n",
    "- | $d_1$ | $\\{0.2, 0.2, 2.0, 1.5, 1.0\\}$ |\n",
    "- | $d_2$ | $\\{0.2, 0.2, 1.5, 1.0, 1.0\\}$ |\n",
    "+ | $d_3$ | $\\{1.5, 1.0, 0.5, 0.5, 0.5\\}$ |\n",
    "+ | $d_4$ | $\\{1.5, 1.5, 0.5, 0.2, 0.5\\}$ |\n",
    "+ | $d_5$ | $\\{1.5, 1.5, 0.5, 0.2, 0.2\\}$ |\n",
    "\n",
    "Then:\n",
    "\n",
    "- The centroid of relevant document $C_r$ and non relevant document $C_n$ given below:\n",
    "\n",
    "relevant | centroid | $\\{ text, mining, algorithm, information, retrieval \\}$ |\n",
    "---------|----------|-------------------------------------------------------|\n",
    "+| $C_r$ | $\\big\\{ \\frac{1.5*3}{3}, \\frac{1.0*(1.5*2)}{3}, \\frac{0.5*3}{3}, \\frac{0.5*(0.2*2)}{3}, \\frac{0.2*(0.5*2)}{3} \\big\\}$ |\n",
    "-| $C_n$ | $\\big\\{ \\frac{0.2*2}{2}, \\frac{0.2*2}{2}, \\frac{2.0+1.5}{2}, \\frac{1.5+1.0}{2}, \\frac{1.0*2}{2} \\big\\}$ |\n",
    "\n",
    "- Then compute $\\vec{q}_m$ using Rocchio relevant feedback:\n",
    "\n",
    "$\\eqalign{\n",
    "    \\vec{q}_m &= \\alpha * \\vec{q} + \\beta * C_r - \\gamma * C_n \\\\\n",
    "              &= \\{ \\alpha + 1.5 * \\beta - 0.2 * \\gamma, \\alpha + 1.0 * \\beta - 0.2 * \\gamma, \\alpha + 0.5 * \\beta - 1.75 * \\gamma, \\alpha + 0.0666 * \\beta - 1.25 * \\gamma, \\alpha + 0.02 * \\beta - 1.0 * \\gamma \\}\n",
    "}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain how the Kullback-Leibler (KL) divergence retrieval function generalizes the query likelihood retrieval function.\n",
    "\n",
    "Let:\n",
    "\n",
    "- Query Likehood is sum of TF-IDF weighting for each word mathed in documents and queries plus document length normalization:\n",
    "\n",
    "$f(q,d) = \\sum\\limits_{w \\in d,q} c(w,q) \\big[ log \\frac{P_{seen}(w|d)}{\\alpha_d P(w|C)} \\big] + n \\ log \\ \\alpha_d$\n",
    "\n",
    "- KL-divergence measure the divergence between two distributions of Document Language Model and Query Language Model $P(w|\\hat{\\theta}_Q)$:\n",
    "\n",
    "$f(q,d) = \\sum\\limits_{w \\in d,P(w|\\theta_Q)>0} P(w|\\hat{\\theta}_Q) \\ log \\frac{P_{seen}(w|d)}{\\alpha_d P(w|C)} + log \\ \\alpha_d$\n",
    "\n",
    "Where:\n",
    "\n",
    "- Document language model is produced by Query Likehood Estimation.\n",
    "\n",
    "- Query language model contains current query vector $\\theta$ and learned query model $\\hat{\\theta}$:\n",
    "\n",
    "$P(w|\\hat{\\theta}_Q) = \\frac{c(w,Q)}{|Q|}$\n",
    "\n",
    "Then, **KL Divergence is generalization of query likehood model** because:\n",
    "\n",
    "- KL Divergence used query likehood model for initial retrieval model which eliminate $n$ by subtitute $n = |Q|$. This means that we set query language model to be relative to frequency of word in query, not in collection.\n",
    "- KL Divergence used feedback language model to learn new weighted query $\\hat{\\theta}$ from feedback given by users.\n",
    "\n",
    "---\n",
    "\n",
    "Feedback language model used linear interpolation which work similar to Rocchio Feedback:\n",
    "\n",
    "- $D(.||.)$ is simplified notation of KL-divergence.\n",
    "- $\\alpha \\in [0,1]$ is parameter to control the strngth of feedback documents, such that:\n",
    "$\\alpha \\begin{cases}\n",
    "0 \\ \\text{means no feedback},\\\\\n",
    "1 \\ \\text{means full feedback}\n",
    "\\end{cases}$\n",
    "\n",
    "Since that two condition is not desirable, we expect that $\\alpha \\in (0,1)$\n",
    "\n",
    "- $\\theta_F$ is feedback language model.\n",
    "\n",
    "![Model based feedback](images/model-based-feedback.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain the basic idea of using a mixture model for feedback.\n",
    "\n",
    "Let:\n",
    "\n",
    "- $\\lambda$ is mixing parameter of two distributions, such that: $\\lambda P_1$ and $(1 - \\lambda) P_2$.\n",
    "- $P(w|C)$ is background model as first distribution.\n",
    "- $P(w|\\theta)$ is topic model as second distribution.\n",
    "- $F$ is feedback documents.\n",
    "\n",
    "We want:\n",
    "\n",
    "- Choose probability $\\lambda$ to control two model distributions, such that: $(1-\\lambda)P(w|\\theta)+\\lambda P(w|C)$.\n",
    "- Choose $\\lambda$ which reduce noise in the feedback documents $F$ where $\\lambda$ = noise.\n",
    "\n",
    "Assume:\n",
    "\n",
    "- $\\lambda$ will be fixed in a single value (always convergence).\n",
    "\n",
    "Then:\n",
    "\n",
    "- Feedback document $F$ fit to word probabilities $\\theta$ similar to unigram language model.\n",
    "- We need some iteration to find best $\\lambda$ to describe maximum likehood of $\\theta$ by using EM algorithm.\n",
    "- Feedback language model is optimization problem of two distributions controlled by parameter $\\lambda$:\n",
    "\n",
    "$$\\eqalign{\n",
    "    \\theta_F &= arg \\ max_{\\theta} \\ log \\ P(F|\\theta)\\\\\n",
    "             &= arg \\ max_{\\theta} \\ \\sum\\limits_{d \\in F} \\sum\\limits_{w} \\ c(w,d) * log[(1-\\lambda) * P(w|\\theta) + \\lambda * P(w|C)]\n",
    "}$$\n",
    "\n",
    "![Mixture language model](images/mixture-language-model.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain some of the main general challenges in creating a web search engine.\n",
    "\n",
    "- **Scalability**<br>\n",
    "    - Question:\n",
    "        - How to store big data?\n",
    "        - How to serve many users quickly?\n",
    "    - Answer:\n",
    "        - Using **Google's MapReduce frawework**.\n",
    "- **Low quality information and spam**\n",
    "    - Question:\n",
    "        - How to prevent low quality informations such as repreated text have high score?\n",
    "        - How to prevent spams to get high ranking score?\n",
    "        - How to identify new spams?\n",
    "    - Answer:\n",
    "        - Use wide variety of signals to rank pages.\n",
    "- **Dynamics of the web**:\n",
    "    - Question:\n",
    "        - How to prioritize links, which need to be fresh periodically, which need to be update rarely?\n",
    "        - How to crawl in dynamic content since desktop and web layout have different layout?\n",
    "        - How to avoid crawler from being back to old link?<br>\n",
    "    - Answer:\n",
    "        - Implement **link analysis** which improve search result by leveraging extra information about the networked nature of the web.\n",
    "        - Use multiple features for ranking, such as web page layout and anchor text."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain what a web crawler is and what factors have to be considered when designing a web crawler.\n",
    "\n",
    "Crawler also called as spider is program that crawls (traverses, parses, and downloads) pages on the web.\n",
    "\n",
    "Factors have to be considered when designing a web crawler:\n",
    "\n",
    "- Avoid heavy requests to the server and prevent *denial of service*. For example: Implement breadth search to keep serve load balanced.\n",
    "- Optimize crawling speed and maximize throughput. For example: Implement parallel algorithm and distributed crawler.\n",
    "- Implement focused crawling if possible. For example: Crawl any web page that matched only with specific topic and crawler system that support user query search.\n",
    "- Built effective graph algorithm to improve crawler ability to follow any new links. For example: Find new links in a web site that not directly linked to any old pages.\n",
    "- Implement artificial intelligent algorithms to make crawler behave like human, easy to maintenance and can learn from experiences. For example: Avoid unnecessary crawling, such as avoid crawling to fresh links, can decide crawler interval for specific web sites, such as daily for news site and hourly for social media, and prioritize some popular web site to be always fresh by analyze web sites popularity using HITS algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain the basic idea of Google File System (GFS).\n",
    "\n",
    "GFS is distributed file system using large clusters of commodity hardware. The GFS divided a big file into several fixed-size chunks of 64 MB. Each chunks is fixed-size means new chunk will be appended to the next allocation sector. GFS cluster consists of multiple nodes of one **Master Node** and large number of **Chunck Servers**. Each data indexed as tuple of `(key, value)`, where `key` contains unique identifier and `value` contains data itself. Group of `(key, value)` called as chunk and each chunk then stored in each server node or chunk server. For example using range of chunk algorithm: If there are 1,000,000 keys, 1/4 of all `(key, value)` required 64 MB allocation and four chunk servers connected, then each chunk server will store 250,000 `(key, value)`. Each chunk assigned with 64-bit unique label by master node and logical mapping of files to constituent chucks are maintened. To ensure reliability, each chunk may be replicated several times in separated chunk servers. The replication factor of each chunk may vary depend on demand, but the default is three times. A master node not stored actual chunk, but store all metadatas associated with chunks. Heart-beat messages is communicaton between master node and chunk servers to ensure al metadata always up to date. \n",
    "\n",
    "![Google FS](images/google fs1.png)\n",
    "\n",
    "More information, please read [GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The google file system](https://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain the basic idea of MapReduce and how we can use it to build an inverted index in parallel.\n",
    "\n",
    "MapReduce is data aggregation technique using parallel programming. Basically, MapReduce consists of `Map()` function and `Reduce()` function. `Map()` should executed first, then feed the output to `Reduce()`. Each function described below:\n",
    "\n",
    "- **Map()** route query to corresponding servers, pull and merge-sort collected data.\n",
    "- **Reduce()** do data transformation such as fltering and grouping.\n",
    "\n",
    "![Map Reduce](images/map reduce.png)\n",
    "\n",
    "We can easily build an inverted index using MapReduce by write our inverted index algorithm into `Map()` and `Reduce()` functions. MapReduce will execute `Map()` in parallel. Here an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Mapper:\n",
    "    def Map(docid, doc):\n",
    "        H = {}\n",
    "        for term in doc:\n",
    "            # Execute in parallel\n",
    "            if term in H.keys():\n",
    "                H[term] = 1\n",
    "            else:\n",
    "                H[term] = H[term] + 1\n",
    "        for term, count in H.items():\n",
    "            Emit(term, (docid, count))\n",
    "\n",
    "class Reducer:\n",
    "    def reduce(term, postings):\n",
    "        posting = []\n",
    "        for _posting in postings:\n",
    "            posting.append(_posting)\n",
    "        posting.sort()\n",
    "        Emit(term, posting)\n",
    "        \n",
    "class Emit:\n",
    "    def __init__(self, term, posting):\n",
    "        self.db = DB.pull()\n",
    "        self.db.push(term, posting)\n",
    "\n",
    "class DB:\n",
    "    @staticmethod\n",
    "    def pull():\n",
    "        \"\"\"Pull all data from databases\"\"\"\n",
    "        pass\n",
    "    \n",
    "    @staticmethod\n",
    "    def push(term, posting):\n",
    "        \"\"\"Push inverted index into databases\"\"\"\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain how links on the web can be leveraged to improve search results.\n",
    "\n",
    "Graph algorithm tells us about two type of links of Digraph (Directed Graph):\n",
    "\n",
    "- **Outlink** is an edge that point to other node.\n",
    "- **Inlink** is an edge that point to origin node.\n",
    "\n",
    "Link anaysis tells us about two types of web page:\n",
    "\n",
    "- **Hub** page is a web page that have so many *outlinks*. Hub page became a gateway to explore and mining more links since it points to many other pages.\n",
    "- **Authority** page is a web page that received so many *inlinks*. Authority page is important web page since many other pages are pointing to this page.\n",
    "\n",
    "![Link analysis](images/link analysis.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explain how PageRank and HITS algorithms work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**PageRank** algorithm used by Google for doing link analysis. Basically, PageRank is **edge weighted digraph** algorithm that count outlinks and inlinks of a web page. The idea behind it is *popularity of a web page can be quantified by count its inlinks, more inlinks than more popular the web page is*. PageRank algorithm measure the popularity of specific web page not only by count inlinks of individul web page, but recursively accumulate all inlinks from neighbor web pages. So, *popularity of web page $d_i$ will inherited to web page $d_j$*.\n",
    "\n",
    "**Random Surfer Model** is original model adapted by Sergey Brin and Larry Page in the development of PageRank Algorithm. Random surfer model try to quantify two assumptions about user behavior: User may keep to following links or get distracted caused to randomly jumping to random web page that not connected directly to current web page. This model similar to **Markov Chain Model**. A good visualization of markov chain can be found at [here](http://setosa.io/ev/markov-chains/).. Below the formal definition:\n",
    "\n",
    "---\n",
    "\n",
    "Let:\n",
    "\n",
    "- $M$ is Transition Matrix.\n",
    "- $M$ represent edge weighted digraph.\n",
    "- $d_i$ is a web page in $M_{row}$ and $d_j$ is a web page in $M_{column}$.\n",
    "- Weight of edge is probability of how likely a node connected to other node. Thus, $M$ is also stochastic matrix, where sum of each row in $M$ should be one:\n",
    "\n",
    "$$M_{ij} = \\text{Probability of going from } d_i \\text{ to } d_j$$\n",
    "\n",
    "$$\\sum\\limits_{j=1}^N M_{ij} = 1$$\n",
    "\n",
    "Suppose:\n",
    "\n",
    "- A simple graph of web page below:\n",
    "\n",
    "![simple graph](images/simple-graph.png)\n",
    "\n",
    "- Then the transition matrix $M$:\n",
    "\n",
    "$$M = \\begin{bmatrix}\n",
    "    0 & 0 & 1/2 & 1/2 \\\\\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & 1 & 0 & 0 \\\\\n",
    "    1/2 & 1/2 & 0 & 0 \\\\\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Assume:\n",
    "\n",
    "- Users may keep to follow links from current web page $d_i$ to connected web pages $d_j$.\n",
    "- Users may distracted and decide to go another web page $d_j$ which not connected directly from current web page $d_i$.\n",
    "- Random process is uniformly distributed, thus all web pages have equal probability for being visited. So, the probability of jump to web page $d_j$ is $1/N$, where $N$ is numbers of all web pages.\n",
    "\n",
    "We know that:\n",
    "\n",
    "- Some web pages may have new incoming links. Thus at certain time, transition matrix $M$ may get updated.\n",
    "\n",
    "Then:\n",
    "\n",
    "- The probability of user visiting page $d_j$ at time $t+1$ is linear propagation of two possibilities: users may following links connected from $d_i$ or users randomly jumping to reach page $d_j$:\n",
    "\n",
    "$$\\eqalign{\n",
    "    p_{t+1} (d_j) &= \\text{possibility of following links} + \\text{possibility of random jumping}\\\\\n",
    "    p_{t+1} (d_j) &= (1 - \\alpha) \\sum\\limits_{i=1}^N M_{ij} p_t (d_i) + \\alpha \\sum\\limits_{i=1}^N \\frac{1}{N} p_t (d_i)\n",
    "}$$\n",
    "\n",
    "- $\\alpha$ also called as **damping factor** is probability of users choose random jumping. Based on Sergey Brin and Larry Page paper [The Anatomy of a Large Scale Hypertextual.pdf](https://web.archive.org/web/20150927004511/http://infolab.stanford.edu/pub/papers/google.pdf), $\\alpha$ usually set to be 0.85.\n",
    "- $p_t (d_i)$ in unknown probability of user being in web page $d_i$ in the current time $t$.\n",
    "- $p_{t+1}$ is also called as **Equilibrium equation** for single linear sistem $i$.\n",
    "\n",
    "---\n",
    "\n",
    "To find unkown probability $p_t (d_i)$, we use linear system equation that work similar to dynamic system, but with parameter $\\alpha$:\n",
    "\n",
    "---\n",
    "\n",
    "Let:\n",
    "\n",
    "- Compute expected probabilites for all $p(d_j)$ in left hand side and for all $p(d_i)$ in right hand side. Thus $p(d_j)$ and $p(d_i)$ are vector of probabilities $\\vec{p}$.\n",
    "- $I$ is uniform matrix of random jumping probabilities. Since it is uniform, then probability of jumping to all $d_{ij}$ are $1/N$, such that:\n",
    "$$I_{ij} = \\frac{1}{N} \\quad \\forall i,j$$\n",
    "- Probability of users go to web page $d_j$ is independent for each step, thus user behavior can be modeled using **random walk**.\n",
    "\n",
    "Then:\n",
    "\n",
    "- since $size(\\vec{p}) = N$, then the equation became linear system of $N$ variables:\n",
    "$$p(d_j) = \\sum\\limits_{i=1}^N \\Big[ \\frac{1}{N} \\alpha + (1-\\alpha) M_{ij} \\Big] * p(d_i) \\rightarrow \\vec{p} = (\\alpha I + (1-\\alpha)M)^T \\ \\vec{p}$$\n",
    "- Since $size(I) = size(A) = N$, then we can merge them into singular matrix $A$.\n",
    "- We have linear system of $N$ varables:\n",
    "$$\\begin{bmatrix}\n",
    "    p_{t+1}(d_1) \\\\\n",
    "    . \\\\\n",
    "    . \\\\\n",
    "    . \\\\\n",
    "    p_{t+1}(d_N)\n",
    "\\end{bmatrix}        = A^T\n",
    "\\begin{bmatrix}\n",
    "    p_{t}(d_1) \\\\\n",
    "    . \\\\\n",
    "    . \\\\\n",
    "    . \\\\\n",
    "    p_{t}(d_N)\n",
    "\\end{bmatrix}$$\n",
    "simplify it:\n",
    "$$y = A^T * v$$\n",
    "$v$ is eigenvector, so exist a eigenvalue $\\lambda$, such that:\n",
    "$$A^T * v = y = \\lambda * v$$\n",
    "\n",
    "- $v$ is unkown eigenvector. Use **Power Iteration** method to find $v$. Power iteration is eigenvalue algorithms which used recurent relation mechanism to compute eigenvector until it convergence. The idea is, since $A$ is stochastic matrix, then there is exist greatest eigenvalue $\\lambda$ of nonzero eigenvector $v$. Below the power iteration algorithm use to find PageRank vector (eigenvector): \n",
    "    1. Set threshold $h$ to identify greatest $\\lambda$ and stop the iteration.\n",
    "    2. $v$ is unkown eigenvector which can be set randomly or uniformly at first iteration.\n",
    "    3. Compute eigenvalue of $A.v$, such that $\\lambda_i = eig(A.v)$.\n",
    "    4. For each step, compute $\\hat{v}$ by normalize dot product of $A.v$\\:\n",
    "    $$\\hat{v} = \\frac{A.v}{||A.v||}$$\n",
    "    5. $\\hat{v}$ is unit vector in normalized vector space, such that magnitude of $v$ normalized to 1, but direction of $v$ unchanged. More information, please read [this explanation in linear algebra](http://freetext.org/Introduction_to_Linear_Algebra/Basic_Vector_Operations/Normalization/).\n",
    "    6. Compte new eigenvalue $A.\\hat{v}$, such that $\\lambda_j = eig(A.\\hat{v})$.\n",
    "    7. Compute distance between $\\lambda$, such that $\\delta(\\lambda) = \\lambda_j - \\lambda_i$.\n",
    "    8. If $\\delta(\\lambda) > h$, then stop the iteration.\n",
    "    9. If $\\delta(\\lambda) < h$, then update $v$ and $\\lambda$ simultaneusly, such that $v = \\hat{v}$ and $\\lambda = \\lambda_i$. Then continue the iteration.\n",
    "\n",
    "For further explanation about power iteration, please read [wikipedia](https://en.wikipedia.org/wiki/Power_iteration) or [ML wiki](http://mlwiki.org/index.php/Power_Iteration).\n",
    "\n",
    "For more information about PageRank algorithm in three different point of views (dynamic models, linear algebra, and random surfer), please read [this lecture note](http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html).\n",
    "\n",
    "-----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's implement power_iteration method to find PageRank vector in python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def eigenvalue(A, v):\n",
    "    \"\"\"\n",
    "    @param A: Matrix.\n",
    "    @param v: Eigen vector.\n",
    "    @return: Eigen value.\n",
    "    \"\"\"\n",
    "    vt = v.transpose()\n",
    "    ev = vt.dot(A.dot(v)) / vt.dot(v)\n",
    "    return ev[0,0]\n",
    "\n",
    "def power_iteration(A, h=1e-9):\n",
    "    \"\"\"\n",
    "    @param A: matrix.\n",
    "    @param h: treshold\n",
    "    @return: The eigenvector and eigenvalue\n",
    "    \"\"\"\n",
    "    n, m = A.shape\n",
    "    \n",
    "    v = np.ones([m, 1]) / m  # Eigen vector at first iteration\n",
    "    l = eigenvalue(A, v)     # Eigen value at first iteration\n",
    "    \n",
    "    # Repeat until converge\n",
    "    while True:\n",
    "        Av = A.dot(v)\n",
    "        vNorm = Av.A / np.linalg.norm(v)\n",
    "        l1 = eigenvalue(A, vNorm)\n",
    "        \n",
    "        if np.abs(l1 - l) < h:\n",
    "            break\n",
    "            \n",
    "        v = vNorm\n",
    "        l = l1\n",
    "    \n",
    "    return v, l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Should produce 3: 3.0\n",
      "Should produce 3: 3.0\n"
     ]
    }
   ],
   "source": [
    "# Test eigenvalue()\n",
    "print(\"Should produce 3\", end=': ')\n",
    "A = np.matrix([[1,0], [2,3]])\n",
    "v = np.array([[0], [1]])\n",
    "print(eigenvalue(A,v))\n",
    "\n",
    "print(\"Should produce 3\", end=': ')\n",
    "A = np.matrix([[1,0], [2,3]])\n",
    "v = np.array([[0], [1]])\n",
    "print(eigenvalue(A.transpose(),v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eigenvector (v)\n",
      "[[-1.8973666 ]\n",
      " [-0.63245553]]\n",
      "\n",
      "Eigenvalue (lambda)\n",
      "-2.0000000016142927\n",
      "\n",
      "A . v\n",
      "[[3.7947332 ]\n",
      " [1.26491107]]\n",
      "\n",
      "lambda . v\n",
      "[[3.7947332 ]\n",
      " [1.26491107]]\n"
     ]
    }
   ],
   "source": [
    "# Test power_iteration()\n",
    "A = np.matrix([[2, -12], [1, -5]])\n",
    "B = power_iteration(A)\n",
    "print(\"Eigenvector (v)\")\n",
    "print(B[0])\n",
    "\n",
    "print()\n",
    "print(\"Eigenvalue (lambda)\")\n",
    "print(B[1])\n",
    "\n",
    "print()\n",
    "C = A.dot(B[0])\n",
    "print(\"A . v\")\n",
    "print(C)\n",
    "\n",
    "print()\n",
    "D = B[0] * B[1]\n",
    "print(\"lambda . v\")\n",
    "print(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**HITS (Hypertext-Induced Topic Search)** algorithm is designed to compute both inlinks and outlinks, thus HITS measure the importance of authority and alos hub pages. HITS algorithm use **reinforcement mechanism** to help improve scoring for both hubs and authorities. HITS algorithm assume that good authority always pointed by good hub and vice versa:\n",
    "\n",
    "Let:\n",
    "\n",
    "- $A$ is adjacency matrix of undirected graph, such that:\n",
    "\n",
    "$$A_{ij} = \\begin{cases}\n",
    "1 \\ \\text{if } d_i \\rightarrow d_j\\\\\n",
    "0 \\ \\text{if } d_i \\not\\rightarrow d_j,\n",
    "\\end{cases}$$\n",
    "\n",
    "- $h(d_i)$ is hub score of web page $d_i$:\n",
    "\n",
    "$$h(d_i) = \\sum\\limits_{d_j \\in OUT(d_i)} a(d_j)$$\n",
    "\n",
    "- $a(d_i)$ is authority score of web page $d_i$:\n",
    "\n",
    "$$h(d_i) = \\sum\\limits_{d_j \\in IN(d_i)} h(d_j)$$\n",
    "\n",
    "\n",
    "By vectorization, we got:\n",
    "\n",
    "- Hub vector $\\vec{h}$ is product of adjacency matrix $A$ and authority vector $\\vec{a}$:\n",
    "\n",
    "$$\\vec{h} = A \\vec{a}$$\n",
    "\n",
    "- Authority vector $\\vec{a}$ is product of transposed adjacency matrix $A$ and hub vector $\\vec{h}$:\n",
    "\n",
    "$$\\vec{a} = A^T \\vec{h}$$\n",
    "\n",
    "\n",
    "By back substitution, we can:\n",
    "\n",
    "- Compute hub vector $\\vec{h}$ without knowing authority vector $\\vec{a}$:\n",
    "\n",
    "$$\\vec{h} = A \\cdot A^T \\cdot \\vec{h}$$\n",
    "\n",
    "- Compute authority vector $\\vec{a}$ without knowing hub vector $\\vec{h}$:\n",
    "\n",
    "$$\\vec{a} = A^T \\cdot A \\cdot \\vec{a}$$\n",
    "\n",
    "\n",
    "Then:\n",
    "\n",
    "- The initial weight of $\\sum \\vec{h} = 1$ and $\\sum \\vec{a} = A^T . \\vec{h}$, such that for every $d_i$:\n",
    "\n",
    "$$\\vec{h}_0 = \\begin{bmatrix}\n",
    "1\\\\\n",
    "1\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "1\n",
    "\\end{bmatrix} \\quad \\text{and} \\quad \\vec{a}_0 =  A^T \\cdot \\begin{bmatrix}\n",
    "1\\\\\n",
    "1\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "1\n",
    "\\end{bmatrix} $$\n",
    "Simplify:\n",
    "$$a(d_i) = h(d_i) = 1$$\n",
    "\n",
    "- For each $d_i$ at time $t$, iteratively update $\\vec{h}$ and $\\vec{a}$ by traversing all nodes in graph:\n",
    "\n",
    "$$HITS_{t} = \\begin{cases}\n",
    "\\vec{a}_t = (A^T \\cdot A) \\cdot \\vec{a}_{t-1}\\\\\n",
    "\\vec{h}_t = (A \\cdot A^T) \\cdot \\vec{h}_{t-1}\\\\\n",
    "\\end{cases}$$\n",
    "\n",
    "\n",
    "For further explanation about HITS algorithm, can be found at [here](http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture4/lecture4.html).\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets implement HITS algorihm in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def hits(A, h, maxIter):\n",
    "    \"\"\"\n",
    "    The convergence of HITS is problematic since hard to find the equilibrium solution.\n",
    "    \n",
    "    @param A: Transition matrix\n",
    "    @param h: Hub vector\n",
    "    @return: Authority vector and Hub vector\n",
    "    \"\"\"\n",
    "\n",
    "    for i in range(maxIter):\n",
    "        a = A.T.dot(h)\n",
    "        h = A.dot(a)\n",
    "        \n",
    "    return a, h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Authority vectors\n",
      "[[   0]\n",
      " [   0]\n",
      " [1024]]\n",
      "\n",
      "Hub vector\n",
      "[[1024]\n",
      " [1024]\n",
      " [   0]]\n"
     ]
    }
   ],
   "source": [
    "A = np.matrix([[0, 0, 1], [0, 0, 1], [0, 0, 0]])\n",
    "h = np.array([[1], [1], [1]])\n",
    "\n",
    "h = hits(A, h, 10)\n",
    "\n",
    "print(\"Authority vectors\")\n",
    "print(h[0])\n",
    "\n",
    "print(\"\\nHub vector\")\n",
    "print(h[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Additional Readings and Resources\n",
    "\n",
    "- C. Zhai and S. Massung. Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining, ACM Book Series, Morgan & Claypool Publishers, 2016. Chapters 7 & 10By "
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}