06_Information_Retrieval

Vector Space Model

• Idea: Relevant documents are those that are most similar to the query
• Represent query and documents as vectors, and compare them using vector-similarity measures 

• Fields:
  • For structured collections. E.g.: term in book title more important than in description
• Zones:
  • For semi-structured collections, such as HTML documents. E.g. term in <h1>-Tag more important than in text; terms in certain frames irrelevant
• Static document weights:
  • Some documents are more trusted than others, independent of query. Leads to tiered indices: separate indices for documents with high, medium and low ranks

• In light of the subjectivity of relevance:
  • have n>1 annotators independently perform relevance judgments for many queries
  • compare the agreement of annotators
    • High agreement means: annotation results are reliable
      • assign relevance labels by majority vote
      • use the average of judgments to define a ranking

• Annotation Schemata
  • hard for annotators:
    • judge the (graded) absolute relevance of a document, given a query
  • easier for annotators:
    • judge relatively, which of two documents is more relevant, given a query.
      • Disadvantage: more judgments because of pairings

• Result sets (unordered):
  • Returned documents = sub-set of all documents
  • Binary relevance feature: in/out
• Result lists (ordered):
  • Returned documents = sub-set of all documents, ordered/ranked according to their relevance for the topic
• Relevance judgments
  • 5-point-scale judgments for top-n results
  • specific to (commercial) search engine

• P, R and F measure the quality of the result set accurately.
• But in a real user setting:
  • Result is looked at sequentially in a ranked list
• Users look at top k documents only

Result Lists: P@k

Precision= relevant retrieved / all retrieved (=k)

• Engine A: 
  • P@5 = 2/5 = 0.4

• IR deals with finding in a document collection as many relevant and as little nonrelevant documents as possible for a query
• Relevance is a property of a document in relation to an information need
  • Often subjective
  • In IR research / evaluation, established by means of gold standard data
• A query is a textual representation of a particular information need
• For reasons of efficiency, documents are stored in an Inverted Index:
  • Term --> linked list of documents it appears in
  • Tf-idf, the most common term weighting scheme in IR
• Documents and queries can be represented as vectors in a high-dimensional space (Vector Space Model): One dimension per term
• Comparison by means of cosine similarity of vectors
• VSM retrieval: Returning docs most similar to query, ranked by similarity
• Evaluation measures: Precision and Recall not suited for web search scenario,
  • better: MAP, NDCG

1. Start with a processing queue containing the URL of ‘seed pages’
2. get next URL form processing queue
3. parse, extract outlinks (URLs), store page and link info
4. mark current URL as processed
5. put still unprocessed newly found outlinks into processing queue
6. run until all URLs are processed, restart periodically

• The web contains a lot of pages with duplicate content
• For retrieval, only one page should be indexed
• Duplicates have to be detected after crawling and before indexing
• Exact duplicates are not very frequent
• More important (and more difficult to detect) :
  • Near-duplicates, e.g.
    • Slightly human-edited text pages
• Para- or re-phrasing can also produce 'identical' documents
  • Undetectable by these methods; topic of plagiarism detection

• Non-trivial IR involves at least some linguistic analysis, e.g.
  • Stemming
  • Lemmatization
  • POS-Tagging
  • ..
• Many of these processing steps are computationally expensive.

• Link structure provides information to measure 'importance' of a page
• Web = directed graph
• Inlinks: Pages that contain links to a page (in-degree)
• Outlinks: Other pages that a page contains links to (out-degree)
• Page rank PR(i) of a page i increases with the number and page rank of the pages linking to it.

• When indexing a document D, include anchor text from links pointing to D.
• Anchor text is often a better description of a page’s content than the page itself.
• Anchor text can be weighted more highly than document text. (based on the Assumption 1 & 2)
• Can score anchor text with weight depending on the authority of the anchor page’s website
  • To reduce risk of Google bombs

Assumption 1: A hyperlink is a quality signal.

Assumption 2: The anchor text describes the content of d2.

• State-of-the-art setup: Machine learned function (Neural Net, Boosted Decision Trees) on the basis of 1000+ features
  • static features (per page): PageRank, Index Tier, Number of inlinks, document length, language, language quality… 
  • dynamic features (per page+query): TF-IDF and variants, language model scores, anchor text, query expansion techniques, personalized PageRank, clicklogs, session logs …
  • query features (per query): length of query, known bigrams, number of ‘stopwords’, names etc.

• Search engine click logs contain very valuable information for optimizing the relevance of search results and ads: the number of clicks on a search result is highly correlated with its relevance
• A/B testing (aka flighting):
  • A small number of users gets an experimental page/ranking function/toolbar color.
    • If satisfaction/click rate/interaction/etc. increase, roll out to all users

• Click-through
• Browser action
• Time
• Explicit judgement

Clicks are biased towards high positions

• Clicks on lower positions are more informative 

• Informational queries:
  • user wants to learn about something (40%-65% of volume)
    • arab spring
    • justin bieber
• Navigational:
  • user wants to go to a specific page (15%-25%)
    • lufthansa
    • tagesschau
• Transactional:
  • user wants to use a web-mediated service, e.g. download, shopping (20%-35%)
    • italy weather forecast
    • HDMI camcorder
• Other:
  • exploratory search, find a good hub
    • Copenhagen hotels

• Database Approach (early advertising systems like Overture)
  • Ads are database records
  • Matching strategies for query q:
    • Exact match
    • Advanced match
• IR Approach (today’s standard)
  • Ads are documents in an ad index
  • on query q, run an index search and return matching ad documents
  • no distinction between exact and advanced match
  • difference to web IR:
    • more recall-oriented, especially for tail queries

• Goal: Search engine ‘understands’ user better
• Handling of polysemy, synonymy and hyponymy
• Approaches
  • ontology-based (Semantic Web)
  • NLP-based: During indexing, documents are analyzed with syntactic and semantic processing steps

• Almost impossible to determine intended sense in short keyword queries
• “query word collocation effect”
  • Combination of query words disambiguate each other
• Semantic Search:
  • Synonym matching through index expansion

• Web IR is more oriented towards precision than recall
• Web Spiders for finding and crawling web pages
• Ranking in commercial search engines uses many features, e.g.
  • PageRank
  • Anchor Text
  • Click-log Analysis
• Computational Advertising is a subfield of IR.
• Main challenge: Place ads for tail queries
• Semantic Search: leaving the keyword world