Lecture 1 Recap Q&A

Information Retrieval is the task of identifying and retrieving information that is relevant to an information need, usually expressed as a search query. The system returns a ranked list of results ordered by relevance.

Examples: web search engines (Google, Bing), email search, Google Scholar. The core challenge is measuring relevance — what makes a document a good match for a query?

(a)

$$P = \frac{60}{80} = 0.75 \qquad R = \frac{60}{200} = 0.30$$

(b)

he weighted harmonic mean of $P$ and $R$ with weights $w_P$ and $w_R$ is: $$H = \frac{w_P + w_R}{\dfrac{w_P}{P} + \dfrac{w_R}{R}}$$ Set $w_P=1$, $w_R=\beta^2$: $$F_\beta = \frac{(1+\beta^2)\,PR}{\beta^2 P + R}$$ Check: $\beta=1 \Rightarrow F_1=\dfrac{2PR}{P+R}$ ✓

(c)

Precision should carry twice the weight of recall $\Rightarrow \beta^2=\tfrac{1}{2} \Rightarrow \beta=\tfrac{1}{\sqrt{2}}\approx 0.707$. $$F_{1/\sqrt{2}} = \frac{1.5\times0.75\times0.30}{0.5\times0.75+0.30} = \frac{0.3375}{0.675} = 0.50$$

• Term Frequency (TF): the more a term appears in a document, the more representative it is.
• Inverse Document Frequency (IDF): the less a term appears across the collection, the more discriminative it is.

Raw counts treat very common words and discriminative ones as equally informative. TF-IDF down-weights ubiquitous words: $$\text{tf-idf}(t,d) = \text{tf}(t,d)\times\log\!\left(\frac{|D|}{|\{d'\in D:\text{tf}(t,d')>0\}|}\right)$$

(a) Eliminating Euclidean distance

Let $D_2=2D_1$ (same topics, twice as long). Then $d_E(q,D_1)\neq d_E(q,D_2)$ in general — Euclidean distance has a length bias.

Both B and C are scale-invariant: for $\alpha,\beta>0$, $d_N(\alpha x,\beta y)=d_N(x,y)$ and $\cos(\alpha x,\beta y)=\cos(x,y)$.

(b) Identical rankings

Since $\hat{x},\hat{y}$ are unit vectors: $$d_N(x,y)^2=\|\hat{x}-\hat{y}\|_2^2=1+1-2\cos(x,y)$$ $$\boxed{d_N(x,y)=\sqrt{2(1-\cos(x,y))}}$$ The map $t\mapsto\sqrt{2(1-t)}$ is strictly decreasing, so ascending $d_N$ order equals descending $\cos$ order. Cosine is preferred — normalisation is handled in the formula itself.

Keyword stuffing: inserting many repetitions of keywords (sometimes hidden) to inflate TF-IDF scores without genuine content. TF-IDF only sees word frequencies — it cannot distinguish a quality article from a keyword-stuffed page.

(Klienberg, 1998) and (Page & Brin, 1998) uses the web's link structure: a link from A to B is an endorsement. Pages receiving many links from authoritative pages are ranked higher.

(a)

Recall how $\tilde{G}$ is built from the raw transition matrix $G$ ($G_{ij} = 1/\deg^+(j)$ if $j \to i$, else $0$): $$\tilde{G}_{ij} = \begin{cases} G_{ij} & \text{if page } j \text{ has at least one outgoing link} \\ 1/N & \text{if page } j \text{ is a dangling node (column of } G \text{ is all-zero)} \end{cases}$$ For non-dangling pages, column $j$ of $G$ already sums to 1 (it is a probability distribution over destinations). For dangling pages, the column is replaced by the uniform distribution $\tfrac{1}{N}\mathbf{1}$, which also sums to 1. In both cases every column of $\tilde{G}$ sums to 1 and all entries are $\geq 0$, so $\tilde{G}$ is column-stochastic. Every column of $U$ sums to $N \cdot \tfrac{1}{N} = 1$, so $U$ is column-stochastic. For column $j$ of $M$: $$\mathbf{1}^\top M_{:j} = d\,\underbrace{\mathbf{1}^\top \tilde{G}_{:j}}_{=\,1} + (1-d)\,\underbrace{\mathbf{1}^\top U_{:j}}_{=\,1} = d + (1-d) = 1$$ All entries of $M$ are non-negative ($d \geq 0$, $1-d \geq 0$, $\tilde{G}_{ij} \geq 0$, $U_{ij} > 0$). Hence $M$ is column-stochastic. If $\pi^{(k)}$ is a probability vector ($\mathbf{1}^\top \pi^{(k)} = 1$, entries $\geq 0$), then: $$\mathbf{1}^\top \pi^{(k+1)} = \mathbf{1}^\top M \pi^{(k)} = (\mathbf{1}^\top M)\,\pi^{(k)} = \mathbf{1}^\top \pi^{(k)} = 1$$ because every entry of $\mathbf{1}^\top M$ equals 1. The iteration preserves total probability mass, and the Perron–Frobenius theorem guarantees convergence to a unique stationary distribution.

(b)

Three pages: pages 1 and 2 each link only to page 3, and page 3 is dangling (no outgoing links). The transition matrix $G$ (where $G_{ij} = 1/\deg^+(j)$ if $j \to i$, and note this is the transpose of the usual adjacency matrix) is: $$G = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \end{pmatrix}$$ Columns 1 and 2 each sum to 1 (each page has one outgoing link to page 3). Column 3 sums to 0 — not column-stochastic. Form $M_{\text{bad}} = d\,G + (1-d)\,U$ with $d = 0.85$: $$\text{column 3 of } M_{\text{bad}} = 0.85 \begin{pmatrix}0\\0\\0\end{pmatrix} + 0.15\begin{pmatrix}1/3\\1/3\\1/3\end{pmatrix} = \begin{pmatrix}0.05\\0.05\\0.05\end{pmatrix} \quad \Rightarrow \text{sum} = 0.15 \neq 1$$ Start from $\pi_0 = \bigl[\tfrac{1}{3},\,\tfrac{1}{3},\,\tfrac{1}{3}\bigr]^\top$. After one step: $$G\pi_0 = \begin{pmatrix}0\\0\\\tfrac{1}{3}+\tfrac{1}{3}\end{pmatrix} = \begin{pmatrix}0\\0\\\tfrac{2}{3}\end{pmatrix} \quad \text{(the \(\tfrac{2}{3}\) mass concentrated on dangling page 3 vanishes!)}$$ $$\pi_1 = 0.85\begin{pmatrix}0\\0\\\tfrac{2}{3}\end{pmatrix} + 0.15\begin{pmatrix}\tfrac{1}{3}\\\tfrac{1}{3}\\\tfrac{1}{3}\end{pmatrix} = \begin{pmatrix}0.05\\0.05\\0.617\end{pmatrix} \qquad \mathbf{1}^\top\pi_1 \approx 0.717 \neq 1$$

• What pages to add to the frontier? — Specifically, how to avoid revisiting the same page twice. This is solved with a hash set of visited URLs: hashing gives O(1) average-case lookup, so checking membership in a collection of N URLs costs O(1) rather than O(N) for a direct search.
• Which page to crawl next? — This is the traversal-order decision. Two classical strategies:
  • BFS uses a FIFO queue. It discovers pages level by level — all pages at distance 1 before distance 2, etc. Preferred for web crawling because it finds high-level pages (which tend to be broadly linked) early.
  • DFS uses a stack (LIFO). It dives deep into one branch before backtracking. Poor for web crawling because it can get stuck exploring one corner of the web indefinitely.

(a)

Model $h$ as a random permutation. The minimum over $A\cup B$ is equally likely to be any element; it satisfies $m(A)=m(B)$ iff it lies in $A\cap B$: $$\Pr[m(A)=m(B)]=\frac{|A\cap B|}{|A\cup B|}=J\quad\checkmark$$

(b)

With $k$ independent hash functions, $\hat{J}_{\text{MH}} = \tfrac{1}{k}\sum_{i=1}^k \mathbf{1}[m_i(A) = m_i(B)]$ is the average of $k$ different 0-1 random variables, each of which is one when $m_i(A) = m_i(B)$ and zero otherwise: $$\mathbb{E}[\hat{J}_{\text{MH}}] = J \quad \Rightarrow \quad \text{Bias} = 0$$ $$\operatorname{MSE}(\hat{J}_{\text{MH}}) = \operatorname{Var}(\hat{J}_{\text{MH}}) = \frac{J(1-J)}{k}$$ The MSE vanishes as $k \to \infty$ independently of $|A|$ and $|B|$: to achieve $\operatorname{MSE} \leq \varepsilon^2$, it suffices to take $k \geq J(1-J)/\varepsilon^2$.

(c)

Let $|A| = |B| = n$, $|A \cap B| = m$, $|A \setminus B| = |B \setminus A| = n - m$, so $J = m/(2n-m)$.

(c.1) Expected numerator

Consider an element $x \in A \cap B$. The two samples are drawn independently: $S_A$ from $A$ and $S_B$ from $B$. Since $x$ belongs to both sets, it can be selected by either draw: $$\Pr[x \in S_A] = \frac{k}{n}, \qquad \Pr[x \in S_B] = \frac{k}{n}$$ For $x$ to land in the **intersection** $S_A \cap S_B$ it must be selected by **both** independent draws: $$\Pr[x \in S_A \cap S_B] = \frac{k}{n} \cdot \frac{k}{n} = \frac{k^2}{n^2}$$ Elements in $A \setminus B$ can never enter $S_B$, and elements in $B \setminus A$ can never enter $S_A$, so they contribute $0$ to the intersection. By linearity of expectation: $$\mathbb{E}[|S_A \cap S_B|] = m \cdot \frac{k^2}{n^2}$$

(c.2) Expected denominator

We always draw exactly $k$ elements into $S_A$ and $k$ into $S_B$. Every element we pick is by definition in the union, so by inclusion–exclusion on the two fixed-size samples: $$|S_A \cup S_B| = |S_A| + |S_B| - |S_A \cap S_B| = 2k - |S_A \cap S_B|$$ Taking expectations: $$\mathbb{E}[|S_A \cup S_B|] = 2k - \mathbb{E}[|S_A \cap S_B|] = 2k - \frac{mk^2}{n^2}$$ For $k \ll n$ the second-order term $mk^2/n^2$ is negligible, so: $$\mathbb{E}[\hat{J}_{\text{S}}] \approx \frac{mk^2/n^2}{2k} = \frac{mk}{2n^2}$$ Since $J \approx m/(2n)$ (for $m \ll n$), this simplifies to: $$\mathbb{E}[\hat{J}_{\text{S}}] \approx J \cdot \frac{k}{n}$$

MinHash's entire error is variance (zero bias), shrinking as $1/k$ regardless of $n$. Sampling has an irreducible bias that only vanishes when $k\approx n$.

(a)

Set $w(p)=\text{PR}(p)$. PageRank captures universal authority independently of topic — pages that many authoritative pages link to are crawled first, front-loading the highest-value content within a limited budget.

(b)

PageRank requires the full link graph, which is still being built. Two workarounds:

• Periodic recomputation on the partial graph, reordering the frontier every $K$ pages.
• OPIC: Consider an online estimation of Page Rank.