Models

Boolean Retrieval

  • Document: Set of words
  • Query:
    • Propositional formula with (AND, OR, NOT)
  • Processing:
    • Convert query to disjunctive normal form
    • Use inverted index
    • Intersect posting lists (sorted, \( O(N) \))
    • Optimization: Start with smallest intermediate result / sort terms by increasing document frequency
  • Advantages
    • Easy to understand
    • Theoretically powerful (every possible subset can be retrieved)
  • Disadvantages
    • No ranking
    • No similarity queries
    • Low recall (e.g., synonyms)

Fuzzy retrieval model

  • Motivation
    • Index terms are not equally important/characteristic (e.g., synonyms, multiple incidences)
    • Assign weight to terms
  • Idea
    • Based on boolean retrieval
    • Use fuzzy result sets (continuous degree of membership)
  • Central questions
    • How to answer queries?
    • How to get the membership degrees?
  • Advantages
    • Support for non-binary assignment of index terms
    • Support for synonyms/related terms
    • Ranking
  • Disadvantages
    • Difficult computation
    • Un-intuitive querying

Representation

  • Query:
    • Propositional formula (as in boolean retrieval)
    • Alternative operators: t-Norm, t-Conorm
  • Document:
    • Bag-of-words (set-of-words makes more sense)
    • Each term has a membership degree
    • Terms in the document have degree \( \mu(t) = 1 \)
    • Additional terms have degree \( \mu(t) \leq 1 \)
  • Processing:
    • Use Zadeh operators
    • Problem: Strange behavior a={x/0.4, y/0.4} b={x/0.3, y/1.0} q=x AND y r={x/0.4, y/0.3}

Membership degree

  • Ogawa et al., 1991
  • Use co-occurrence of terms
  • Jaccard index \( J(t_1, t_2) \)
    • Also called term-term correlation coefficient
    • Problem: Jaccard index does not mention the documents not containing any of the two terms
    • \( J(t_1, t_2) = \frac{df(t_1\land t_2)}{df(t_1 \oplus t_2)} \)
  • Computation:
    • \( W(d, t) = 1- \Pi_{u\in d} (1-J(t,u)) \)
  • Idea:
    • \( 1-J(t,u) \) measures dissimilarity of \( t \) and \( u \)
    • The more often a term co-occurs with all terms of a document, the more similar is the term to the document

Coordination level matching

  • Luhn
  • Idea:
    • User sketches document
    • Document with an overlap of terms of size \( n \) is more relevant than a document with overlap of size \( n-1 \)
  • Query:
    • Bag-of-words (virtual document)
  • Document:
    • Bag-of-words
  • Processing:
    • Compute coordination level (size of overlap)
    • Ranking with the coordination level
    • Alternative: Scalar product of binary term incidence vectors
  • Advantages
    • Easy comparison
  • Disadvantage
    • No support for synonyms

Vector space model

  • Salton, 1975
  • Idea:
    • Represent documents as points in space (as in libraries)
    • Use proximity as similarity measure
  • Document:
    • \( d\in \mathbb{R}^{n} \)
    • Index term spans own dimension
    • Term weighting approaches
      1. Binary incidence (set-of-words)
      2. Fuzzy membership degree
      3. Term-frequency (bag-of-words)
      4. Term-frequency and term discrimination
  • Processing:
    • Convert query to binary-incidence-vector
    • Scan postings lists for each query term
    • Sum up scores for each document
      • e.g., term frequency, TF-IDF
    • Similarity measure: Scalar product (ranking)
  • Important questions
    • Which similarity measure to use?
    • How to assign weights to terms?
  • Applications
    • Scoring/retrieving documents
    • Document classification
    • Document clustering
  • Advantages
    • Simple/clear
    • Intuitive querying
    • Customizable (similarity, normalization, term weighting)
    • High retrieval quality
    • Relevance feedback (e.g., Rocchio)
  • Disadvantages
    • High dimensionality (curse of dimensionality)
    • Word order is lost
    • Implicit assumptions
      • Cluster hypothesis
      • Independence/orthogonality assumption

Similarity

  • Measure \( s:X\times X\rightarrow [0,1] \)
    • \( s(x,y) = 1 \): Maximal similar
    • \( s(x,y)=0 \): Maximal dissimilar
  • Example:
    • Cosine similarity
    • \( s(x,y) = cos(\measuredangle(x,y)) = \frac{x*y}{||x||*||y||} \)
  • Choice of similarity measure
    • Depends on application
    • Options:
      • Cosine similarity
      • Euclidean distance

Normalization

  • Why?
    • Euclidean distance depends on vector length
    • Cosine similarity does not depend on length
  • Approaches
    • Divide by length / normalize to unit length
    • Divide by max. coordinate
    • Divide by sum of coordinates
  • Advantage Divide by length
    • Vector norm equals \( 1 \)
    • Computation of cosine similarity is cheaper (unit length)
    • Rank created by euclidean distance is the same as for cosine similarity
  • Problem: Longer documents are more in-depth
  • Solutions:
    1. Compute result normally and boost long documents
    2. Measure effect of document length on relevance and adjust ranking

../_images/normalization.png

Term weighting

  • Term frequency \( tf(d, t) \)
    • Luhn, 1961
    • Repetition of words is an indication of emphasis
  • Discrimination \( disc(t) \)
    • Not every term equally important (e.g., stop words)
    • Approaches
      • TF-IDF
      • Document structure
  • Idea:
    • High term frequency -> High term weight
    • High discriminative power -> High term weight
    • \( w(t) \propto tf(d,t) * disc(t) \)

TF-IDF

  • Spärck Jones, 1972
  • Idea:
    • Term specificity as term discrimination
    • The more specific a term is, the larger its discriminative power is
    • Normalize with respect to collection size
  • Use inverse document frequency \( df(t)^{-1} \)
  • Relationship specificity and inverse document frequency is logarithmic
  • Formula:
    • \( tf(d,t) * \log(\frac{N + 0.5}{df(t) + 0.5}) \)

Document structure

  • Idea:
    • Use structure of document collection
    • Removing a highly discriminative term leads to large change in average document similarity
    • Remove a non-discriminative terms leads to small change in average document similarity
  • Formalization:
    • \( s \): Similarity measure between documents
    • \( s_{avg} \)
      • Average similarity across all documents
      • \( s_{avg} =\frac{1}{N^2} \sum_ {d,e\in C}s(d,e) \)
    • \( s_{avg,t} \)
      • Average similarity across all documents
      • Remove dimension corresponding to term \( t \)
    • \( disc(t) = s_{avg} - s_{avg,t} \)
  • Problem: Expensive computation
  • Solution: Heuristics (compute average document, leads to linear runtime)

Comparison to boolean and fuzzy retrieval

  • Vector space model has better average precision using fixed recall

Probabilistic retrieval

  • Base of probabilistic IR: Probabilistic ranking principle
  • Models
    • Probabilistic indexing
    • Binary Independence model (+ extensions)
    • Poisson model
    • Belief networks
  • Advantages
    • Good in experiments
    • Intuitive measure
    • Well-defined mathematical foundations
    • Explicit assumptions
  • Disadvantages
    • Parameter estimation difficult
    • Doubtful assumptions (e.g., independence)
    • Less flexible than vector space model
    • Complicated

Probabilistic Ranking Principle

  • Robertson, 1977
  • Principle:
    • If result list is ordered decreasingly by probability of usefulness, the effectiveness of the system is the best that is obtainable
    • Important: Probability of usefulness is estimated as accurately as possible on the given data
  • Usefulness: Hard to define
  • Relevant documents:
    • \( R_q = \{d\in C\mid \text{d relevant w.r.t q}\} \)
  • Task:
    • Input: Query \( q \), document \( d \)
    • Output: \( P(d\in R_q) \) (Bayesian interpretation)
    • \( R_q \) is unknown, estimate using other probabilities

Probabilistic Indexing model

  • Maron/Kuhns, 1960
  • Idea: Improve search on manually indexed collections
  • Notion:
    • \( k \) index terms
    • Document \( d\in [0,1]^k \) (weighted)
    • Query \( q\in \{0,1\}^k \) (binary)
    • Task: Estimate \( P(d\in R_q) \)
    • Random variable \( Q \)
      • Over all possible queries
      • Distribution given by query logs
    • Random set of documents \( R_Q \)
  • Formula: \( P(d\in R_q) = c(q) * P(d\in R_Q) * \Pi_{i\in \{i,...,k\}, q_i=0} (1-d_i) * \Pi_{i\in \{i,...,k\}, q_i=1} d_i \)
  • Important assumptions
    • Independence
    • Maron’s and Kuhn’s argument

Estimation

Overview
  1. Assume \( P(d\in R_q) = P(d\in R_Q\mid Q=q) \)
  2. Apply Bayes’ theorem
  3. Replace \( P(Q=q) \) with constant \( c(q) \)
    • \( P(Q=q) \) equal for all documents
  4. Estimate \( P(d\in R_Q) \) with relevance feedback
    • Model for general relevance
    • Relative frequency of positive ratings
    • Proportional to \( P(d\in R_q) \)
  5. Assume independence of query terms
    • Not reasonable (co-occurrence, synonyms)
  6. Split product and use complementary events
  7. Maron/Kuhns’ argument
    • Use term weight for probability \( P(Q_i=1\mid d\in R_Q) \)
    • Assigned by human indexer
    • Indexer knows relevance to topics
  8. Optional: Ignore non-occurrence
    • Most users leave out query terms
Estimation of \( P(Q=q\mid d\in R_Q) \)
  1. Independence of query terms
    • \( = \Pi_{i=1}^k P(Q_i=q_i\mid d\in R_Q) \)
  2. Split product
    • \( = \Pi_{i\in \{i,...,k\}, q_i=0} P(Q_i=0\mid d\in R_Q) * \Pi_{i\in \{i,...,k\}, q_i=1} P(Q_i=1\mid d\in R_Q) \)
  3. Complementary events
    • \( = \Pi_{i\in \{i,...,k\}, q_i=0} (1-P(Q_i=1\mid d\in R_Q)) * \Pi_{i\in \{i,...,k\}, q_i=1} P(Q_i=1\mid d\in R_Q) \)
  4. Maron and Kuhns’ argument
    • \( = \Pi_{i\in \{i,...,k\}, q_i=0} (1-d_i) * \Pi_{i\in \{i,...,k\}, q_i=1} d_i \)

Binary independence model

  • Rijsbergen, 1977
  • Notion:
    • \( k \) index terms
    • Document \( d\in \{0,1\}^k \) (binary)
    • Query \( q\in \{0,1\}^k \) (binary)
    • Random variable \( D \)
      • Uniformly distributed over all documents in collection
      • \( P(d\in R_q) = P(D\in R_q\mid D=d) \)
      • Only look at events where \( D \) equals \( d \)
  • Ranking: \( O(d\in R_q) \approx \Pi_{i\in \{i,...,k\}, d_i=1, q_i=1} (\frac{P(D_i=1\mid D\in R_q)}{1-P(D_i)=1\mid D\in R_q)}*\frac{N}{df(t_i)}) \)
  • Important assumptions
    • Linked dependence (weights assigned by indexer)
    • Equal term distribution for non-query-terms for relevant and non-relevant documents
    • Number of non-relevant documents is approximately \( N \)

Estimation

  1. Use odds for ranking (strong monotony)
    1. Apply Bayes’ Theorem
    2. Replace \( P(D\in R_q) \) with constant \( c(q) \)
    3. Reduce the fraction by \( P(D=d) \) (fraction is known but numerically useless)
    4. Intermediate: \( O(d\in R_q)=c(q)*\frac{P(D=d\mid D\in R_q)}{P(D=d\mid D\notin R_q)} \)
  2. Assume linked dependence
    • \( \frac{P(D=d\mid D\in R_q)}{P(D=d\mid D\notin R_q)} = \Pi_{i=1}^k \frac{P(D_i=d_i\mid D\in R_q)}{P(D_i=d_i\mid D\notin R_q)} \)
    • Not reasonable (e.g., synonyms)
  3. Split up by \( d \)
  4. Use complementary probability
    • \( P(D_i=0\mid D\in R_q) = 1-P(D_i=1\mid D\in R_q) \)
  5. Split up by \( q \)
  6. Assume identical term distributions for non-query terms for relevant and non-relevant documents
    • User queries relevant terms
    • \( q_i=0 \Rightarrow P(D_i=1\mid D\in R_q) = P(D_i=1\mid D\notin R_q) \)
    • Reduce fraction
  7. Multiply by 1
    • \( 1=\Pi_{i\in\{1,...,k\}, d_i=1,q_i=1} \frac{1-P(D_i=1\mid D\in R_q)}{1-P(D_i=1\mid D\notin R_q)} * \frac{1-P(D_i=1\mid D\notin R_q)}{1-P(D_i=1\mid D\in R_q)} \)
  8. Replace document-independent block by constant (merge \( d_i=0 \) with \( d_i=1 \)
  9. Regroup
  10. Assume \( P(D_i=1\mid D\notin R_q)\approx P(D_i=1) \)
    1. Number of non-relevant documents is approximately \( N \)
    2. \( P(D_i=1) \approx \frac{df(t_i)}{N} \)
    3. Assume \( N >> df(t_i) \)
    4. Estimate \( \frac{1-P(D_i=1\mid D\notin R_q)}{P(D_i=1\mid D\notin R_q)} \approx \frac{N}{df(t_i)} \)
  11. Estimate \( P(D_i=1\mid D\in R_q) \)
    • User feedback/initial query results
    • Croft/Harper (1979): Constant 0.9
    • Greiff (1998): \( \frac{df(t_i)}{N} \)

Language models

Motivation

  • Observation:
    • Different styles of writing
    • Documents use different vocabulary
  • Idea:
    • Represent document by language model (generative model)
    • Each topic/document has a specific language
    • Find document which language model generates the query
  • Approaches
    • Formal grammars
    • Statistical language models
    • Probabilistic context-free grammars (not considered)

Formal grammars

  • Describe correct syntax
  • Problem: Does not capture style
    • Writing style depends on statistical properties
  • Solution: Add probability distribution over terms

Statistical language models

  • Idea:
    • Ignore syntax/grammar
    • Focus on statistical regularities
    • Use generative model
  • Central questions
    • Which language model to use for documents?
    • How to estimate the language model for each document?
  • Applications
    • Document generation
    • Document recognition
      • Use generation probabilities
      • e.g. OCR, speech recognition
  • Advantages
    • Clear statistical foundation
    • No ad-hoc weighting
    • Better than vector space model
  • Disadvantages
    • Independence assumption (unigram model)
    • Relevance feedback difficult
    • No explicit notion of relevance

Assumptions

  • Each document has (unknown) statistical document model
  • Document is random sample
  • Query is random sample of language model of the user’s information need

Definition

  • A statistical language model is a probability distribution over sequence of words
  • Document \( (w_1,...,w_n) \) gets probability of generation \( P(w_1,...,w_n) \)
  • Document length \( n \)

Query processing

  1. Estimate language model for each document
  2. For each model, compute the probability of generation for the query
  3. Rank by probability \( P(q\mid M_d) \)

Models

  • Unigram model
    • Statistical independence assumed / no context
    • \( P(w_1,...,w_n) = P(w_1)*...*P(w_n) \)
  • Bigram model
    • Context: Previous term
    • \( P(w_1,...,w_n) = P(w_1)*P(w_2|w_1)*...*P(w_n|w_{n-1}) \)
  • Trigram model
    • \( P(w_1,...,w_n) = P(w_1)*P(w_2|w_1)*P(w_3|w_1,w_2)...*P(w_n|w_{n-2},w_{n-1}) \)

Model selection

  • Use unigram model
    • Reduced computational complexity
    • Reduced model complexity (bias-variance tradeoff)
    • Losses from data sparseness (short documents, not enough information for conditional probability)
    • Sufficient for IR to judge topic

Probability estimation

Maximum likelihood estimator
  • \( P(w_i) = \frac{tf(d, w_i)}{n} \)
  • Problem: Document often too small
    • Missing terms have zero probability
    • Occurring terms are overestimated (occurrence by chance)
  • Solution: Smoothing
    • Add probability to missing terms
    • Move probability to collection mean
Smoothing
  • Additive smoothing / Laplace smoothing
    • Add \( \alpha \) to term frequency (used in TF-IDF)
    • Renormalize (to reach sum of one)
  • Linear smoothing
    • Blend between overall probability of term occurrence and document-specific probability (useful for homogeneous collections)
    • \( P(w_i)= \lambda \frac{tf(d, w_i)}{n} + (1-\lambda)\frac{cf(w_i)}{N} \)
    • \( \lambda \in [0,1] \): Weighting parameter
  • Ponte and Croft (1998)
    • Use collection data to stabilize model
    • For absent term: Estimate probability over collection (MLE for collection)
    • For present term: Smooth MLE with average MLE

Latent Semantic Indexing

  • Naive approach: Manual indexing of topics (better: automatically)
  • Called Latent Semantic Analysis
  • Advantages
    • Good quality
    • Use synonyms and polysemy
    • Mathematical foundation
    • Enhancing data quality (removing noise)
    • Document can be folded into the latent space
  • Disadvantages
    • No negations
    • No boolean conditions
    • Computationally expensive
  • Based on Reduced Singular Value Decomposition
    • \( S=U\Sigma V^T \)
    • \( U \) contains term coordinates
    • \( V^T \) contains document coordinates

Motivation

  • Vector space doesn’t represent Synonymy and Polysemy
    • Synonymy: Two words have the same meaning (document with “car” and “automobile” would be underestimated)
    • Polysemy: One word has multiple meanings (document with “charge” would be overestimated)
    • Reason: Words assumed to be independent (each word one dimension)
  • Idea
    • Change basis to dimensions with variance
      • Use \( k \) latent topics instead of terms
      • Called Semantic space
    • Exploit underlying structure of terms and documents
    • Connect terms, documents and query with these topics
    • Group related terms together (reorder columns/rows) to find components
    • Use interrelationships of terms using transitive co-occurrence (car/driver and auto/driver but not car/auto)

Low-rank approximation

  • Use low rank approximation of the SVD of term-document matrix
  • Effects
    • Terms with high co-occurrences move together in low dimensional space (synonyms, Why?)
    • Terms with several meanings are assigned to several topics (polysemes)
    • Noise is removed for correct \( k \)
  • \( S \) can be a term-document-matrix with binary incidence
  • \( SS^T \) is term-term co-occurrence matrix
    • Symmetric matrix
    • Cell \( s_{i,j} \) indicates in how many documents terms \( t_i \) and \( t_j \) co-occur (\( S \) binary incidence matrix)
    • Reorder high-valued components to get topics

Optimization

  • Move singular values into left- and right singular vectors
  • \( U_k' = U_k * \sqrt{\Sigma_k} \)
  • \( (V_k^T)' = \sqrt{\Sigma_k} * V_k^T \)
  • Row of \( U_k * \sqrt{\Sigma_k} \) contains term coordinates
  • Column of \( \sqrt{\Sigma_k} * V_k^T \) contains document coordinates

Querying

  • Like in vector space
    1. Map query \( q \) to latent query \( q' \)
    2. Compare to documents (in latent space)
  • Query
    • \( q = (U_k^T)' q' \)
    • \( q' = \Sigma_k^{-1} * (U_k^T)' * q \)
  • Documents in latent space
    • \( \sqrt{\Sigma_k} * V^T_k \)

Computation

  • Expensive/difficult (even for medium term-document matrix)
  • Parameter \( k \) hard to estimate
    • Depends on collection
    • Too low: Some topics not covered
    • Too high: Performance degradation, noisy data
    • Optimal: Guess number of topics

Evaluation

  • Dumais/Landauer (1993, 1995)
    • TREC corpus
    • SVD computing using Lanczos algorithm
    • Results
      • Reducing \( k \) improves recall
      • \( k \) in the low hundreds increases precision for some queries (remove noise)
  • Netflix Prize