Multimedia IR-Alan F. Smeaton

Multimedia Information Retrieval

Alan F. Smeaton

Centre for Digital Video Processing & Adaptive Information Cluster

Dublin City University

Technological developments have allowed easy creation, storage, transmission, rendering and archiving of multimedia. Often text IR method is augmented to media-specific retrieval facilities.

IR on Audio-Speech

Complexities

Speaker variability e.g. Speed of delivery, stressing, volume, background noise etc.

Acoustic Ambiguity e.g. Homophones (to, two and too), small acoustic distinctions (bee and pea).

Context-dependency e.g. Phones can be produced a number of ways depending on its context.

Computational cost of recognizing large vocabulary of words

IR on Audio-Music

MIDI is easy as notes are available and indexing terms are n-gram of notes. But with other forms such as MP3 it is complex.

Image Retrieval

Retrieval from photos, technical drawings, legal documents etc.

Generally there are two types:

Text-based Image Search

Based on Manual Annotation or Automatic Annotation (by google)

Content-based Image Search

Extract low level features such as colour and texture and extract semantic objects. This is done for each object in the collection. Similar process is carried out for any query image(s) and distance between query and indexed images are calculated. This produces the rank list.

Query

User specifies the required colours, textures, features and/or enters keywords.

User can also draw in the requirements such as spatial arrangements.

User can also query by providing image(s) with similar composition.

Video

• Use metadata and browse keyframes

Medata includes title, date, actor(s), producer(s) etc. coupled with keyframe/storyboard previews.

• Use text from speech-Automatic Speech Recognition (ASR)-captions-video OCR
• Match keyframes vs query images

Keyframes extracted as shot representatives can be used for retrieval

• Use semantic video features

Involves pre-processing of video or keyframes to detect features.

Use video/image objects as queries

Read More

NLP for IR-Maarten de Rijke

Natural Language Processing for Information Retrieval

Maarten de Rijke

ISLA, University of Amsterdam

Basic NLP is commonly used in IR e.g. tokenizing, stopping, stemming. More advanced technique is also common e.g. phrase identification, named entity extraction. But advanced NLP can be problematic for IR because IR is not about semantics or syntactic structure; it is about statistical properties of text. IR problems can be reworked so that NLP is potentially useful e.g. question answering, sentimental analysis, biomedical text analysis etc.

Question Answering

People do ask questions that may belong to these categories:

• Factoids e.g. Where does moss grow?
• Definition(oid)s e.g. What is a rational number?
• Procedures e.g. How to speed up XP?

There are some which are difficult to categorize e.g. How to understand woman?

Anatomy of a question

Question type

Idiomatic categorization of questions:

TREC 2003: factoid, list, definition

Answer type

The class of object sought by the question:

Person (Who..?), Place (Where..?), Date (When..?), Number (How Many..?)

Question focus

The property or entity that is being sought by the question:

In what state is the Grand Canyon?

What is the population of Bulgaria?

Question topic

The object or event that the question is about:

What is the height of Mt. Everest?

Here, height is the focus and Mt. Everest is the topic.

Historically QA approaches have seen the movement of corpus from database (1970s), encyclopedias (1990s) to the web (2000-).

Evaluation Measures

MRR of top N candidates given by the system, N=5,3,1

Precision@1

Confidence Weighted Score (CWS)= 1/N (Summation_i=1^N(#correct up to rank i/i))

QA at TREC and CLEF

TREC-8

Answers can be 50 or 250 bytes long

Systems return up to 5 answers

Answers had to be justified (supply supporting docs

Scored by MRR

TREC-10

No answer questions introduced (NIL questions)

TREC-11

Only 1 answer

Exact answer only

Scored by CWS

TREC-12

Definition and list questions

TREC-13

Scenario based

TREC-15

ciQA: complex, interactive QA

TREC-16

ciQA

Doc collection consist of newspaper and blogs

CLEF 2006

Answer validation exercise, real-time exercise

WiQA (QA using Wikipedia)

CLEF 2007

Mixed corpus (Newspaper and Wikipedia)

Notes:

QA could benefit from structured retrieval

Some interesting issues: Mapping question to (set of) queries

Read More

IR and Context-Ian Ruthven

Information Retrieval and Context

Ian Ruthven

Department of Computer and Information Sciences

University of Strathclyde

ir@cis.strath.ac.uk

Why context is important

• Our information activities take place within a context

For e.g. what we already know influences what we expect and how we assess information

• Context changes our expectations from searching

Different Views

• Socio-technical systems

Context is too complex

We can use context to explain but not predict

Instead system should support searcher reasoning about context

• Context sensitive computing

Context implies adaptation based on inputs/world model

Model of input - context helps system make more accurate decisions

e.g. location aware systems

Model of a situation – context describes state

e.g. query formulation vs scanning an index

• Model of a task – Context describes task

e.g. image retrieval vs shopping

Some contextual factors

• Technical e.g. availability of data, device (memory, screen size etc.)
• Physical e.g. location time etc.
• Social e.g. Environment, culture etc.
• Personal e.g. experiental, motivational, physical etc.
• Task e.g. novelty,complexity etc.

Contextual distinctions

• Objective context (e.g. location) vs Subjective context (e.g. affective states)
• Group based (e.g. collaborative filtering) vs Individual (e.g. personalization)
• Meaningful (e.g. language) vs Incidental (e.g. colour of the walls)
• Extrinsic (e.g. document use) vs Intrinsic (e.g. document type)
• Visible (e.g. MS Office Assistant) vs Hidden (e.g. relevance feedback)
• Rule-based (e.g. user models) vs Statistical-based (data mining)

Read More

Structure/XML Retrieval-Mounia Lalmas

Structure/XML Retrieval

By

Mounia Lalmas

Queen Mary, University of London

Documents can be considered structured according to (among others):

• Linear order of words (e.g. sentence, paragraphs etc.)

• Hierarchical (e.g. book’s chapter, sections etc.)

• Links, cross references

• Temporal and spatial relationships in multimedia documents

XML: eXtensible Mark-up Language

• Meta-language-adopted as document format language by W3C

• Used to describe content and structure but not layout

• XML documents are trees

Data-centric view:

– XML as exchange format for structured data

– Used for messaging between enterprise applications

– Mainly a recasting of relational data

Document-centric view:

– XML as format for representing the logical structure of documents

– Rich in text

XML allows the users to retrieve document parts relevant to information need and not the entire document.

Queries

Content-only (CO) queries

• Standard IR queries, but here we are retrieving document components

– “Zidane headbutting Materazzi”

Content-and-structure (CAS) queries

• Put constraints on which types of components are to be retrieved

– “Sections of an article in the Times about Zidane headbutting Materazzi”

XML query languages:

• Four “levels” of expressiveness

– Keyword search (CO Queries): e.g. “xml”

– Tag + Keyword search: e.g. book: xml

– Path Expression + Keyword search (CAS Queries): e.g. /book[./title about “xml db”]

– XQuery + Complex full-text search

for $b in /book

let score $s := $b ftcontains “xml” && “db”

distance 5

XML Retrieval Challenges:

1. Term Statistics

How to calculate tf and idf for XML

2. Relationship Statistics

Which sub-elements best contribute to the content of its parent element and vice-versa?

How to estimate relationship statistics (e.g. size, no. of children, depth, etc.)?

3. Structure Statistics

Which element is a good retrieval unit?

How to estimate structure statistics (frequency, user studies, size, depth)?

4. Overlapping Elements

Which one to return in case of more than one relevant elements (whether to return parent or the child)?

5. Interpreting Structural Constraints

Problem of many DTs, DTDs/schema not known in advance etc.

Need to identify similar tags/elements

Evaluation of XML retrieval: INEX

Two types of topics:

• Content-only (CO) topics

ignore document structure (simulates users, who do not have any knowledge of

the document structure or who choose not to use such knowledge)

• Content-and-structure (CAS) topics

contain conditions referring both to content and structure of the sought elements (simulate users who do have some knowledge of the structure of the searched collection)

Relevance Assessment:

• find smallest component (àspecificity) that is highly relevant (àexhaustivity)

• specificity: extent to which a document component is focused on the information need, while being an informative unit.

• exhaustivity: extent to which the information contained in a document component satisfies the information need.

Read More

Evaluation in IR-Stephen Robertson

Evaluation in Information Retrieval

by

Stephen Robertson

Microsoft Research Ltd., Cambridge, U.K.

and City University, London, U.K.

Why Evaluate:

• To challenge ideas about what makes for good search
• To prove that your ideas are better than someone else’s
• To decide between alternative methods
• To tune/train/optimize a system
• To discover points of failure

What is a good (relevant) document:

• Traditionally, one judged (by an expert) to be on the topic
• More properly, one judged by the user to be helpful in resolving her/his problem

Assuming binary relevance and an input-output system, the function of the system is:

1. To retrieve relevant documents

Measurement of performance for this is:

Recall=No. of relevant docs retrieved/total relevant in the collection

2. Not to retrieve non-relevant documents

Measure of performance for this is:

Precision=No. of relevant docs retrieved/Total retrieved

Various problems (interpolation/extrapolation; averaging over requests)

• Dealing with incomplete judgements
• Choosing which documents to judge

trec_eval: program by Chris Buckley used for TREC

Note: Measures like recall and precision are somewhat crude as diagnostic tools

Some other performance measure:

• Mean Average Precision
• Mean Reciprocal rank
• Success @ n
• Cumulative gain
• Normalized Discounted Cumulative Gain (NDCG)

Note: Some are more user oriented than others e.g. precision@5

IR Experiments:

• Traditionally run different systems on same set of document and requests

Good for comparison of mechanisms (Not so good for many user experiments)

The Text Retrieval Conference (TREC):

• Competition/collaboration between IR research groups worldwide
• Run by NIST, just outside Washington DC
• Common tasks, common test materials, common measures, common evaluation procedures

Some User Issues:

• Interaction
• Relevance

Relevance should be judged in relation to needs not requests

• The cognitive view

– An information need arises from an anomalous state of knowledge (ASK);

– The process of resolving an ASK is a cognitive process on the part of the user;

– Information seeking is part of that process;

– Users’ models of information seeking are strongly influenced by systems.

Some Conflicts:

• In a lab test, we try to control variables (i.e. separate the different factors)

– But in interactive searching, the user has access to a range of interactive mechanisms.

• In a lab test, we try to keep user outside the system.

– But in interactive searching, the user/searcher is inside (part of ) the system

• In a lab test, we can repeat an experiment, with variations, any number of times

– But in interactive searching, repetition is difficult and expensive and unlikely to produce identical results.

Routing/filtering experiments at TREC:

The task

– Incoming stream of documents

– Persistent user profile

– Task: send appropriate incoming documents to the user

– Learn from user relevance feedback

Batch routing:

– Take a fixed time point, with a ‘history’ and a ‘future’

– Optimise query in relation to history

– Evaluate against future (in particular, evaluate by ranking the test set)

– Results: excellent performance, but some danger of overfitting

Adaptive filtering:

– Start from scratch

• text query

• possibly one or two examples of relevant documents

– Binary decision by system

– Feedback only on those items ‘sent’ to the user

– For scoring systems, thresholding is critical

Note: Evaluation measures are more difficult

Read More