Online Vocabulary Adaptation using Limited Adaptation Data

C. E. Liu, K. Thambiratnam, F. Seide. InterSpeech 2007.

Application: Given an audio clip, and some text metadata, generate terms that should be used to index the clip.

Problem: Given the text metadata, adapt the vocabulary using an external corpus (e.g. the internet), and then choose indexing terms from the adapted vocabulary. More precisely, look at an external corpus and guess which words have been mentioned in the audio but are not present in the vocabulary of the indexer (and also, of course, in the metadata).

Highlights:

• Use text metadata to query internet search engine. Pick useful words from retrieved document set, and update the vocabulary. Also use the retrieved document set for adapting the language model.
• Distinguish between term frequency TF_td = c(t,d)/\sum{t'} c(t',d), and tapered term frequency TTF_td = 1+log(TF_td). In the Stanford NLP course, they define TF_td = 1 + log(c(t,d)). Which one is used when?
• Similar to the above, they define TFIDF and TTFIDF.
• Problem reduces to this: for each word in each retrieved document, classify it as a candidate OOV term (i.e. predict that it has been mentioned in the audio) or not. To do this, build a classifier as usual, using audio transcripts as the ground truth training data. The feature vector for a word consisted of its TF, TFIDF, TTF, TTFIDF, POS, etc.

Notes from ECIR 2012

quantum computing
- lattice (set theory)
- spectral theorem


designing search
- design depends on the context, which comprises
    - user (expert, novice, disabled, etc.)
    - task (adhoc, targeted, transactional, etc.)
    - environment (at home, on the move, on a desktop, on an phone, etc.)
- prioritize design goals
    - who am i designing for?
    - who am i _not_ designing for?
- faceted browsing: facets should be
    - exhaustive
    - consistent (e.g. (N.India, S.India) is ok, but (N.India, Bangalore) or (N.India, > Rs.10000) is not ok)
    - Orthogonal / Non-overlapping
    - Of roughly the same size


Paolo Boldi
    - centrality measures; empirical study of how it correlates to node importance
    - has open software on his website for this (HyperANF at ...unimi.it)
    - geodesic, centrality
    - centrality measures (first 3 are geometric indexes)
        - based on degree
        - based on no. of paths
        - based on how close it is to others
        - spectral indexes   
    - Lin centrality, harmonic centrality
    - Kendall's tau
    - computing centrality using diffusion
    - Pregel implementation
    - whitelist
    - naturalistic study


- neyman pearson lemma
- probability ranking principle (stephen robertson)


Explaining query modifications: An alternative interpretation of term addition and removal
- how and why do users modify queries
- what do they assume about how the search engine works





Predicting the Future Impact of News Events
- use various attributes to predict the various attributes
- use std ML techniques (SVR, feature selection)

Detection of News Feeds Items Appropriate for Children
- classify an article as 'appropriate' or 'not'
- use BBC data (labeled 'for children', and 'for adults')
- std readability measures (use info gain for feature selection)
    - ARI, flesch-kincaid


Yoelle Marak
- usage data
    - query log
    - click data
    (- mouse track
     -eye track)
- searchwiki
- demographics of web search. wsdm 2011
- anatomy of the long tail. wsdm 2010


- B-cubed precision and recall: to evaluate soft-clustering

- kdd 2006. "... center ... graph ... extraction ..."

- trustRank (pagerank with bias towards inlinks from reliable pages)

- unique sets ratio

- Geometric MAP, instead if MAP

- statistical significance testing
    - parametric tests (eg. T-test)
    - non-parametric tests
   
- TREC. Banks. Variance due to topics.
- Chi-square test: to check if disribution is Normal
- Shapiro-Wilks test

- BoxCox transformation
- ACE algo (alternating conditional expectation)


- axiomatic approach. fang et al. sigir 2004

- 'bursty' distribution

- Lemur, Terrier systems

Leif Azzopardi et al. top-K retrieval.
    Chen and Karger. SIGIR 2006. Top-K retrieval.
    Prob Ranking Principle. Robertson.
    MMR. Carbonell and Goldstein. 1998
    modern portfolio theory. wang and zhu. ecir 2009
    quantum prob ranking principle. zuccon and azzopardi. ecir 2010
    comparison of ranking principles. zuccon, azzopardi, van rijsbergen. ictir 2011
    gollapudi and sharma. 2009. facilities placement and top-k
- language model with dirichlet smoothing
- alpha-nDCG@10
- diversification
    - kuland and kee, santos et al


latent variable model
- max margin latent variable model, for inducing relevance functions
- log linear model p(x) = e^h(x) / sum_x' e^h(x')
- subgradient method for parameter estimation
- data sets (image)    - SUN, MIR Flickr
- Global SVM, Transductive SVM


1000 search engines
- problem of search
    - many data sources: www, wiki, news, patents, tweet
    - many result types: docs, temp, curr, people
    - many relevances: topical, recency
- probabilistic relational algebra (PRA)

context aware recommendation
- tensor factorization
- ndcg, auc, loss functions
- stochastic GD, alternating least squares, bundle methods

TagME
- tagme.dl.unipi.it
- milne and witten 2008
- earthmover distance (on graphs?)
- "combinatorial"
- wsdm 2012 paper on result clustering
- Lingo, Lingo 3G
- Carpineto, Osinski, et al. ACM Comp Surv 2009
- Carpineto et al. SIGIR 2010.
    - Optimal seach results clustering
    - kSSL (method for evaluating search result clustering), AMBIENT (data set)
- relative mean difference
- TreeNet tool
- Boosted decision trees

* Listen to all talks, to guage the audience. Then tune own presentation accordingly. (Dont say things that everyone knows. Dont forget to say things that most dont know.)

How to review research papers (in CS)

Some links giving advice on how to review research papers in computer science:

• http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=55470
• http://www.cse.lehigh.edu/~jic207/pub/Cormode_SIGMOD09.pdf
• http://people.inf.ethz.ch/troscoe/pubs/review-writing.pdf
• http://www.markbernstein.org/elements/Reviewing.pdf
• http://cs-www.cs.yale.edu/homes/dna/talks/naughtonicde.pdf

SIGIR Poster on Multi-Document Summarization

I read the poster MSSF: A Multi-Document Summarization Framework based on Submodularity (SIGIR 2011). It talked solving the problem using a budgeted maximum coverage problem based on submodularity. Some points to read about

• Let E be a finite set. The function f:Pow(E)->R is submodular if, for any S \subset T \subset E, and s \in E \ T we have

f(T U {s}) - f(T) <= f(S U {s}) - f(S).
Submodular functions are closed under non-negative linear combinations.

• Budgeted Maximum Coverage Problem (NP-Hard): Given a set E of sentences, where each subset S has an influence i(S) and a cost c(S), and a budget b, find a subset S of E which has the larget possible influence while the total cost does not exceed b.
• For example, b is the maximum number of sentences in the summary, c(S) = number of sentences in S, and i(S) is a submodular function measuring the influence of the summary S, then there exist algorithms to solve this problem approximately. Different functions i(S) were proposed in the poster, for different settings (simple summarization, query-focused ~, update ~, comparitive ~). For the simple case

i(S) = \sum{s_i \in E\S} \sum{s_j \in S} sim(s_i, s_j) - \sum{s_i,s_j\in S, s_i != s_j} sim(s_i, s_j) = f1(S) - f2(S)

• f1(S) measures to what degree S represents E, and f2(S) measures redundancies within S. f1(S) and -f2(S) are both submodular, so i(S) is also submodular.

Things to look up

• Budgeted Maximum Coverage Problem. Khuller, Moss, Naor. 1999, Minoux 1978.
• Maximum Marginal Relevance, Update summarization, Comparitive summarization, Query-focused summarization

I am attending a School on Network Science at ECE, IISc, organized as part of the IMI, and funded by ICTS. I jotted down some points for revision/future look-up.

Networks, Rumours, and Epidemics [Dr Ayalvadi Ganesh]
References

• Grimmett and Frieze
• Damon Mosk-Aoyoma and Devavrat Shah. Distributed Computation of Separable Functions. IEEE Trans. Info. Theory. 2008
• Consensus. de Groot et al.
• Voter model. Hassin and Peleg, James Cruise and Ganesh Ayalvadi
• Wright-Fisher model, Morale model
• Wisdom of Crowds. Golub and Jackson
• Acemoglu, Dahleh, Lobel, Ozdaglar
• Kermack and McKendrick. Epidemic model using ODEs
• Ganesh Ayalvadi, Moussalie, Tousley. Effect effect of network topology on epidemic spread. IEEE InfoComm. 2005
• Draief, Ganesh, Moussalie. thresholds for Virus Spread on Nertworks. Ann. Appl. Prob. 2008

Topics

• Coupon Collector Problem
• Stochastic Domination, Strassen's Theorem
• Markov Chains---irreducible, aperiodoc, ergodic, balance equations, invariant distribution, etc.
• Markov Process (continuous time)
• Poisson Process---thinning
• Martingales, stopping time, Optional Stopping Theorem
• Binary Entropy function, Conditional entropy
• Random walks---coalescing RW
• Coupling from the past in MCMC
• Erdos-Renyi graphs, scale-free graphs, expander/ing graphs, unimodular graphs
• Linear recurrences, harmonic functions
• Lattices---infinite lattice
• Perron-Frobenius Theorem---sprectral radius, Perron eigenvalue
• Eigenvalue of e^A, where A is a matrix
• Generalized isoperimetric constant

Ising Models [Andrea Montanari]
Topics

• Hammersley-Clifford Theorem
• Inclusion-Exclusion Principle
• Union bound
• Measures, Concentration
• Gibbs sampling, MCMC, Metropolis
• Constrastive Divergence (Hinton)
• Glauber Markov Chain
• tanh, atanh---properties
• "One-dimensional recursion"
• Inequalities---Markov, Chebyshev, ...
• Sterling number---as related to enumerating number of graphs with p vertices and Cp edges 
• Belief propagation, Generalized BP
• Contraction (on graphs)

I recently started reading the book Introduction to Information Retrieval by Manning, Raghavan and Schuetze. It's a wonderful book. I plan to jot down some notes here from time to time.

Chap. 5 is about  index compression. There are 3 motivations for this-

• reduce disk space required to store the index
• reduce transfer time between memory and disk
• make it possible to store parts of the index in main memory (with on-the-fly decompression when it is used)

 Statistical properties of the index are interesting, as they enable estimation of quantities such as number of terms, number of postings, average number of postings, etc. This in turn helps in the choice of appropriate compression algorithms. Two laws are discussed, both power laws.

• Heap's Law: to estimate the number of (unique) terms (M)
• M = k T^b, where T is the number of tokens, and k and b are constants.
• b>0. We get a straight line with positive slope in the log-log scale.
• Roughly speaking, this implies that the vocabulary keeps growing as the size of the corpus grows---it does not level off.
• Zipf's Law: to estimate the size of the postings lists (f, for frequency/no. of occurrences in the collection)
• f = k r^b, where r is the rank of the term (ordered by frequency), and k and b are constants (b<0).
• Roughly speaking, this implies that the r^th most frequent word occurs 1/r times the most frequent word.

Dictionary compression allows us to keep the dictionary in memory, leading to faster query processing (by avoiding one disk seek).

• The simplest case is no compression. Store records of the form <term, pointer to postings list>, where the term field is restricted to a certain length. Look for terms using binary search.
• Dictionary as a string: Store the terms in the form <t1,t2,t3,...> as one long string. Then store records of the form <termPtr, postingsPtr>. termPtr is an offset from the beginning of the string where a particular term begins. The number of characters to be read is calculated by subtracting from the next termPtr. Look for terms using binary search.
• Blocks of strings: Fix a block size k. Store strings as <l1,t1,l2,t2,l3,t3,l4,t4,...> where li is the length of ti stored in a single byte, and (l1,t1,...lk,tk) constitutes a block. Then store records of the form <blkPtr, postingsPtr1, ..., postingsPtrk>. blkPtr is an offset from the beginning of the string where a particular block begins. Look for terms using binary search to identify the block, and using sequential search within the block.
• Front coding: Suppose the block coding string is <6,drawee, 6,drawer, 7,drawing, 5,drawl>, then instead use <6,draw*ee, 2,#er, 3,#ing, 1,#l>. That is, identify a prefix for a subsequence of the dictionary string, and use a special character (#) for that prefix.
• Minimal perfect hashing: Choose a minimal perfect hash function h() for the vocabulary. Store records of the form <n, postingsPtr> where n = h(t) is the integer that the term hashes to. Looking for a term is a straightforward hash calculation. This method is not suited when the set of terms keeps changing.
• If the dictionary cannot be stored in memory even after compression, store them on disk and add the first term of each disk page to a B tree. Looking for a term will require at most one disk seek.

 Postings compression saves disk space, allows faster reads from disk, and allows caching of postings of popular terms in memory.

• With no compression, the postings list looks like <docId1, docId2, ...>. If there are N documents in the collection, storing each docId requires logN bits. However, storing the gap between consecutive docIds requires fewer bits. For example, suppose there are 1024 documents, then storing <3, 7, 36, 49> requires log1024*4 = 40 bits. But if we knew that consecutive docIds are never more than 32 apart, then storing the offsets as <3, +4, +29, +13> requires 10 + 3*log32 = 25 bits.
• Variable Byte encoding: In the example above, the offsets are stored in 5-bits. In principle, an offset can be as large as N, and require logN bits. But most offsets are much smaller. Hence, a variable length encoding of offsets is used as follows. Given the postings list <824, 829, 215406>, the `gap list' is <-, +5, +214577>. In binary, this looks like <110 0111000, 101, 1101 0001100 0110001>. In the encoding, it is stored as <00000110 10111000, 10000101, 00001101 00001100 10110001>. The 0 and 1 indicate whether this is the last byte of the encoding or not. The underlined sections how where 7-bit pieces from the binary form of the number are stored in the encoding.
• The unit of encoding can be changed from 8 bytes to 4 or 16 or 32. Larger units lead to lesser bit manipulation but results in less effective compression.
• Gamma coding: Suppose the offset is 13 (i.e. 1101). Then store 1110101. This is got by removing the leading bit and taking the rest (101)---called the offset, and prepending it with the length of the offset (3) stored in unary (1110). While reading a gamma code, read upto the first 0---this is the length of the offset that follows. Read the offset and prepend a 1 to it. 
• The optimality of the encoding depends on the data. It can be shown that gamma codes take at most twice as many bits as the optimal encoding for any data.
• Gamma codes are prefix free (no code is a prefix of another, so that no delimiters are required) and parameter free (no parameters to fit/estimate before encoding can begin; also no re-estimation required when the postings lists change).

Gamma codes gives better compression than variable byte encoding but are more expensive to decode.

I recently started reading the book Introduction to Information Retrieval by Manning, Raghavan and Schuetze. It's a wonderful book. I plan to jot down some notes here from time to time.

The Chap. 3 (Dictionaries and Tolerant Retrieval) is about data structures for storing terms, and spelling correction/suggestion.

• A simple way to store terms is in a binary search tree.
• If the terms keep changing (additions/deletions), use a B-tree instead.

Wild-card queries need special data structures.

• For queries like `sch*', the binary/B tree suffices.
• For queries like `*tze', a reversed tree can be used. Comment: Start with the original term set, reverse each term, and use the usual algorithm for tree construction.
• For queries like `sch*tze', use both the trees to get terms with matching prefix/suffix, and then intersect the two sets.
• For general queries like `sch*zen*ger', we need other data structures.
• Permuterm indexes: Augment each term `abc' to `abc$'. Construct a B-tree index where all rotations (abc$, $abc, c$ab, bc$a, ...) point to `abc'. Rotate the query to `sch'$zen*ger*', look in the B-tree index for `ger$sch*', get all matches. In this set, match the complete wild card expression to get correct matches. Comment: It seems that this can be done directly with the tree + reversed tree combination. What is the advantage of the permuterm index?
• k-gram indexes: For each term `disco', add its k-grams $di, dis, isc, sco, co$ (assuming k=3) to the index. Each k-gram points to words that contain it. Given a query `sch*zen*ger', use the query `$sc AND sch AND zen AND ger AND er$' to get matches. In this set, match the complete wild card expression to get correct matches. Comment: All matches for the Boolean query need not be correct; e.g. `ded*' gives `$de AND ded' which matches `deluded', which is not a match for the original wild-card expression.

Spelling correction requires a notion of closeness between strings, and a way to choose the best one among nearby strings.

• Closeness between strings: This is measured in terms of edit distance or Levenshtein distance, which is computed using dynamic programming.
• Finding the nearest strings
• One simple way is to look through all terms in the dictionary, and compute the edit distance to each, and take the closest ones.
• When the dictionary is big, assume the first character is correct and then look. Or, consider all rotations of the query, and look for a fixed size prefix of each rotation in a permuterm index, and collect all the terms found. Or, consider all k-grams of the query, look for them in a k-gram index, and intersect the postings lists (which contain terms, btw).
• We can be tolerant and say "I don't need all k-grams to match" (which is what an intersection of posting lists does). So, we could say e.g. "I want at least 2 k-grams to match". For this, go through the posting lists and for each term, compare its set of k-grams with the k-grams of the query. More generally, use the Jaccard coefficient between the two sets of k-grams (of the term in the postings list, and the query) to decide whether to keep the term or not.
• All the above methods treat each query term in isolation. For context-sensitive spelling correction, do the following. Find the nearest strings for each query term in isolation (as explained above). Try all combinations of the candidates for the different query terms. By `try', we mean query the index with each combination of terms, and rank them based on the number of document matched (highest first). Comment: The set of candidates for each query term can be pruned by `try'ing them too. Also, the pruning can be done stage-wise, i.e. if the query is `were eegles dare', first get candidates for `were' and prune to get {`were', `where', `wire'}. Then get candidates for each of {`were eegles', `where eegles', `wire eegles'} and prune to get {`were eagles', `where eagles', ...). Finally get candidates  for each of {`were eagles dare', `where eagles dare', ...} and prune to get the final list.
• Phonetic closeness between strings: This is usually measured using Soundex algorithms. The basic idea is as follows. Hash every term into a 4-character string and build an inverted index for that (postings are the terms). Hash the query too, and search in the index. An example of a hash function is:
• Retain the first letter. Change AEIOUHWY->0, BFPV->1, CGJKQSXZ->2, DT->3, L->4, MN->5, R->6. Compress consecutive identical digits to one. Then remove 0s, and return the first 4 positions (padded with 0 if required). For example, Manning -> M5055052 -> M505052 -> M5552 -> M555. Comment: It seems that Soundex is not a very good idea in general, especially for non-European languages/scripts.
• Probabilistic models for spelling correction by Toutanova and Moore (2002) are the state of the art, and include ways to model edit distance, phonetic similarity, closeness on the keyboard, and data from popular spelling mistakes.