CS 410 Exam 2

What is the goal of Web Search?

Find small relevant data from massive web data

What are key components of a search engine?

Crawler, indexer, ranking, query processing

What is a crawler?

Program that traverses web pages and collects data

Toy crawler vs real crawler

Simple traversal vs handling scale, politeness, duplicates, dynamic pages

What challenges exist in web search?

Scale, spam, dynamic content, ranking quality, latency

What is indexing?

Organizing documents for efficient retrieval

What is link analysis?

Using hyperlinks to determine importance of pages

What is PageRank intuition?

Important pages are linked by other important pages

What is the random surfer model?

User randomly follows links or jumps to random pages

What is $α$ (alpha) in PageRank?

Probability of random jump

What happens with probability $(1 - α)$?

Follows links

What is PageRank score?

Probability of visiting a page

What is the transition matrix M?

Represents link probabilities between pages

What is the PageRank equation?

$$p=\alpha I+(1-\alpha)M)^{T}p$$

How is PageRank computer?

Power iteration until convergence

Why is PageRank an eigenvector problem?

$p = Ap$ form

What problem does random jump solve

Dead ends + spider traps

What happens if a page has no outgoing links?

It distributes probability uniformly

What are hubs?

Pages that link to many authoritative pages

What are authorities?

Pages linked by many hubs

What is HITS idea?

Mutual reinforcement between hubs and authorities

What is the difference between PageRank and HITS?

Global vs. query-dependent

What is Learning to Rank?

ML approach to combine ranking features

Why use Learning to Rank?

Combines signals like TF-IDF, PageRank

What types of features are used in Learning to Rank?

Content, link, user behavior

What are the approaches for Learning to Rank?

Pointwise, pairwise, listwise

What is text mining?

Extracting actionable knowledge from text

What is the difference between text mining and retrieval?

Discover knowledge vs. find docs

What are 4 text mining perspectives?

Language, content, user, prediction

Why is text representation important?

Determines what analysis is possible

What is paradigmatic relation?

Words substitutable (same class) (eg. cat ↔ dog)

What is syntagmatic relation?

Words co-occur (semantic relation) (eg. eat ↔ food)

How do you detect paradigmatic?

Context similarity

How do you detect syntagmatic?

Co-occurence frequency

Why are word associations useful?

Improves NLP + retrieval tasks

What is logistic regression?

Classification model that outputs probabilities

What does logistic regression output?

Probability between 0 and 1

What is logit?

Log odds of probability

What is sigmoid function?

$$\frac{1}{1+e^{-x}}$$

Why use logistic instead of linear regression?

It outputs probabilities for classification

What is a decision boundary?

Surface that separates different classes

What is a hyperplane?

Generalized linear boundary separating classes in higher dimensions

What is relationship between decision boundary and hyperplane?

The decision boundary is represented by a hyperplane

What defines the decision boundary?

$$w\cdot x + b = 0$$

What is an artificial neuron?

Weighted sum of inputs plus activation function

Neuron formula

$$y=\phi\left(wx+b\right)$$

What are components of a neuron?

Weights, bias, activation function

What is an activation function?

Non linear transformation

Examples of activation functions

Sigmoid, ReLU, tanh

What is a hidden layer?

Layer that transforms inputs into new features

What is a deep neural network?

Neural network with multiple hidden layers

What is backpropagation?

Method to compute gradients and update weights

Steps of backpropagation

Forward pass compute loss backward pass update weights

Why is backpropagation needed?

To learn model parameters

What is an RNN?

Neural network with loops for sequential data

What does RNN capture?

Sequential dependencies

What is hidden state?

Memory of previous inputs

What problem do RNNs have?

Vanishing gradients

Why were LSTMs introduced?

To solve vanishing gradient problem

What are LSTM gates?

Mechanisms that control information flow

What are the three main LSTM gates?

Forget, input, and output gates

What is cell state in LSTM?

Long term memory

Key idea of LSTM

Selective memory control using gates

What is GRU?

Simplified version of LSTM

What gates does GRU have?

Update and reset gates

Difference between GRU and LSTM

Faster vs. more expressive

Why are RNNs slow?

They process sequences, sequentially $O(n)$

Why do RNNs struggle with long text?

Long dependencies and gradient issues

Why are RNNs hard to parallelize?

Each step depends on previous step

Why were transformers introduced?

To solve RNN limitations

Key idea of transformers

Use attention instead of sequence processing

Main advantage of transformers

Parallelization and long range dependencies

What is attention?

Mechanism that focuses on relevant words

Key idea of attention

Query relevant information from sequence

Attention can be viewed as what?

A fuzzy lookup table

What are Q K V in attention?

Query, key, and value vectors

How is attention computed?

$$Attention(Q,K,V)=softmax\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V$$

What is self attention?

$Q$ $K$ and $V$ come from the same sequence

Steps of self attention

Compute $Q$ $K$ $V$, compute similarity, apply softmax, compute weighted sum

What are main components of transformer architecture

Self attention feed forward network residual connections layer normalization

What is multi head attention

Multiple attention mechanisms in parallel

Why use multi head attention

To capture different relationships

What is feed forward network in transformer

Adds non linear transformation

Why use residual connections

Stabilize training

Why use layer normalization

Improve training stability

Why is positional encoding needed

Transformers do not encode order naturally

How is positional encoding implemented

Using sine and cosine functions

What problems does attention have

Loss of order, loss of non linearity, loss of sequential constraints

How do transformers fix loss of order

Positional encoding

How do transformers fix loss of non linearity

Add feed forward layers

How do transformers fix sequential prediction

Mask future tokens

What type of model is GPT

Decoder only transformer

What direction does GPT use

Left to right

What is GPT used for

Text generation

What type of model is BERT

Encoder only transformer

What direction does BERT use

Bidirectional

What is BERT used for

Text understanding

What is CLS token

Special token representing whole sequence

What is SEP token

Separator between sentences

What is MASK token

Used to hide words during training