Accurate Methods for the Statistics of Surprise and Coincidence. Ted Dunning. Computational Linguistics 1993.

• Ideas
• "ordinary words are 'rare', any statistical work with texts must deal with the reality of rare events ... Unfortunately, the foundational assumption of most common statistical analyses used in computational linguistics is that the events being analyzed are relatively common."
• Counting a word w can be viewed as a series of Bernoulli trials. Each token is tested to see if it is w. Assuming a uniform probability p that it is w, the count is distributed binomially and, for np(1-p)>5 (where n=number of tokens), it is distributed almost normally. But this is not true when np(1-p)<1.
• Given outcomes k, propose a model with parameters w. The likelihood of the parameter value w is P(k|w). A hypothesis is a subset of the parameter space W.
• The likelihood ratio of the hypothesis (parameter subspace) W0 = LR = max_{w \in W0} P(k|w) / max_{w \in W} P(k|w).
• Fact: -2 log LR ~ \Chi^2(dim W - dim W0).
• References
• More info on parametric and distribution-free tests: Bradley (1968), and Mood, Graybill, and Boes (1974).
• Likelihood ratio tests: Mood et al. (1974)

Statistical Extraction and Comparison of Pivot Words for Bilingual Lexicon Extension. Daniel Andrade, Takuya Matsuzaki, Jun'ichi Tsuji. TALIP 2012

• Ideas
• Use only statistically significant context---determined using Bayesian estimate of PMI
• "calculate a similarity score ... using the probability that the same pivots [(words from the seed lexicon)] will be extracted for both the query word and the translation candidate."
• "several context [features] ... a bag-of-words of one sentence, and the successors, predecessors, and siblings with respect to the dependency parse tree of the sentence."
• "In order to make these context positions comparable across Japanese and English ... we use several heuristics to adjust the dependency trees appropriately."
• Comments
•  "the degree of association is defined as a measurement for finding words that co-occur, or which do not co-occur, more often than we would expect by pure chance [e.g.] Log-Likelihood-Ratio ... As an alternative, we suggest to use the statistical significance of a positive association"
• Heuristics to make dependency trees comparable are language-pair-specific (for EN-JP only)
• Related work
• Standard approach
• Fix corpora in two languages, and pivot words (seed lexicon)
• For each query word, construct vector of pivot words, and compare.
• Construct vector: some measure of association between query word and pivot word
• Compare: some similarity measure suitable for association measure
• "Context" is a bag-of-words, usually a sentence (or doc?).
• Variations of standard approach
• Peters and Picchi 1997: PMI
• Fung 1998: tf.idf and cosine similarity
• Rapp 1999: log-likelihood ratio and Manhattan distance
• Koehn and Knight 2002: Spearman correlation
• Pekar et al 2006: conditional probability
• Laroche and Langlais 2010: log-odds-ratio and cosine similarity
• Variations incorporating syntax
• Rapp 1999: use word order (assumes word ordering is similar for both languages)
• Pekar et al 2006: use verb-noun dependency
• Otero & Campos 2008: POS tag the corpus and use lexico-syntactic patterns as features; e.g. extract (see, SUBJ, man) from "A man sees a dog." and use (see, SUBJ, *) to find translations for "man".
• Garera et al 2009: use predecessors and successors in dependency graph (and do not use bag-of-words at all)
• Variations incorporating non-pivot words (to overcome the "seed lexicon bottleneck")
• Gaussier et al 2004: construct vector of all words (and not just pivot words) for the query word and each pivot word. Now construct vector of pivot words, and instead of association measure between query and pivot, use the similarity between all-words query vector and all-words pivot vector.
• Dejean et al 2002: use domain-specific multilingual thesaurus
• Variations incorporating senses
• Ismail and Manandhar 2010: construct query vector "given" another word (the sense-disambiguator (SD) word, say). For a query word, one can construct different vectors given different SD words. For each vector, find translation.
• Probabilistic approach
• Haghighi et al 2008: use a generative model where source and target words are generated from a common latent subspace. Maximize likelihood in the graphical model to learn the source-target matchings.
• "suffers from high computational costs ... They did not compare [with] ...  standard context vector approaches, which makes it difficult to estimate the possible gains from their method."
• Graph-based approach
• Laws et al 2010
• one graph per language, words as nodes, 3 types of nodes (adjectives, verbs, nouns) and 3 types of edges (adjectival modification, verb-object relation, noun coordination), edge weights represent strength of correlation
• seed lexicon for connecting the two graphs
• node pair similarity computed using SimRank-like algorithm

Attended a literature review on Question Answering by Akihiro Katsura. Some interesting references.

• Green, Chomsky, et al. 1961. The BASEBALL system.
• rule-based
• Isozaki et al. 2009.
• machine learning-based
• Methodology of QA
• Question analysis
• Xue et al. SIGIR 2008. Retrieval  models for QA archives.
• Text retrieval
• Jones et al. IPM 2000. ---Okapi/BM25
• Berger et al. SIGIR 2000.---Bridging the lexical chasm (OOV problem)
• Brill et al. TREC 2001.---Data intensive QA
• Answer candidate extraction
• Lafferty et al. ICML 2001.---CRF
• Ravichandran & Hovy. ACL 2002.---Surface text patterns for QA
• Answer selection
• Clarke et al. SIGIR 2001.---Redundancy in QA
• Other related work
• Cao et al. WWW 2008.---Recommending questions
• Wang et al. SIGIR 2009.---Similar questions
• Wang et al. SIGIR 2009.---answer ranking
• Jeon et al. SIGIR 2006.---answer ranking with non-textual features (votes, etc.)

Identifying Word Translations from Comparable Documents Without a Seed Lexicon. Reinhard Rapp, Serge Sharoff, Bogdan Babych. LREC 2012

• Idea
• Assume only document-aligned comparable corpora (and no seed lexicon---"typically comprising at least 10,000 words")
• Characterize each article by a set of keywords
• "Formulate translation identification as a variant of the word alignment problem in a noisy setting"
• actually solved using a neural net-style algorithm by Rumelhart & McClelland (1987)
• Comments
• "If ... in language A two words co-occur more often than expected by chance, then their translated equivalents in language B should also co-occur more frequently than expected."
• Experiments
• Preprocessing
• lemmatization (of corpora and evaluation pairs)
• "we use the log-likelihood score as a measure of keyness [or salience of words in a document], since it has been shown to be robust to small [documents] ... the threshold of 15.13 for the log-likelihood score is a conservative recommendation for statistical significance."
• "[we] applied a threshold of five [occurrences] ... [and] added all words of the ... gold standard(s) [even if they were below the threshold]"
• Gold standard
• "The source language words in the gold standard were supposed to be systematically derived from a large corpus, covering a wide range of frequencies, parts of speech, and variances of their
  distribution. In addition, the corpus from which the gold standard was derived was supposed to be completely separate from the development set (Wikipedia)."
• "list of words extracted from the British National Corpus (BNC) by Adam Kilgarriff for the purpose of examining distributional variability." http://kilgarriff.co.uk/bnc-readme.html
• 
  

A Linguistically Grounded Graph Model for Bilingual Lexicon Extraction. Florian Laws, Lukas Michelbacher, Beate Dorow, Christian Scheible, Ulrich Heid, Hinrich Schutze. COLING 2010

• TOREAD

Addressing polysemy in bilingual lexicon extraction from comparable corpora. Darja Fiser, Nikola Ljubesic, Ozren Kubelka. LREC 2012

• Idea
• Get source word senses (using sense tagger), construct context vectors for each sense, and then find target translation.
• To compute sense-specific vectors: split occurrences of source word into groups, and build context vectors separately for each group.
•  Translate context vectors into target language using seed lexicon
• Combine info from several taggers to improve accuracy.
• Take only those words where the tags of both taggers agree.
• Comments (on the classical approach, using a context vector of words)
• "The main idea behind [the classical] approach is the assumption that a source word and its translation appear in similar contexts in their respective languages, so that in order to identify them their contexts are compared via a seed dictionary (Fung, 1998; Rapp, 1999)"
• "[the classical approach] approach gives good results for a specialized domain even though the seed dictionary is quite small (Fiser et al., 2011)."
• "... for closely related languages, ... the same quality of the results can be achieved by exploiting the lexical overlap between the languages instead of using a seed dictionary (Ljubesic and Fiser, 2011).

A Wikipedia-Based Multilingual Retrieval Model. Martin Potthast, Benno Stein, and Maik Anderka. ECIR 2008

• Key idea
• Use aligned Wiki articles (concepts) in two languages to map words/documents in different languages into a common concept space.
• Comments
• "A reasonable trade-off between retrieval quality and runtime is achieved for a concept space dimensionality between 1000 and 10000."

Wikipedia-based Semantic Interpretation for Natural Language Processing. Evgeniy Gabrilovich, Shaul Markovitch. JAIR 2009

(Noting here the details not mentioned in the entry for the IJCAI paper...)

• Corpus preprocessing
• Discard articles that have fewer than 100 non stop words or fewer than 5 incoming and outgoing links; discard articles that describe specific dates, as well as Wikipedia disambiguation pages, category pages and ``the like''; remove stop words and rare words (occurring in fewer than 3 articles), and stem the remaining words.
• For text categorization: Document text is first tokenized, and title words are replicated twice to emphasize their importance. Then, stop words, numbers and mixed alphanumeric strings are removed, and the remaining words are stemmed. The bag of words is next merged with the set of features generated for the document ... and rare features occurring in fewer than 3 documents are removed. ... The generated features ... undergo feature selection using the information gain criterion.
• Concept vector preprocessing
• "The algorithm for pruning the inverted index operates as follows. We first sort all the concepts for a given word according to their TFIDF weights in decreasing order. We then scan the resulting sequence of concepts with a sliding window of length 100, and truncate the sequence when the difference in scores between the first and last concepts in the window drops below 5% of the highest-scoring concept for this word (which is positioned first in the sequence). This technique looks for fast drops in the concept scores, which would signify that the concepts in the tail of the sequence are only loosely associated with the word"
• Ideas
• Use link structure---called "second order model"
• Keep only general concepts
• Comments
• "using a larger knowledge base is beneficial for ESA"
• "We evaluated the effect of using second-order interpretation for computing semantic relatedness of texts, but it only yielded negligible improvements. We hypothesize that the reason for this finding is that computing semantic relatedness essentially uses all available Wikipedia concepts, so second-order interpretation can only slightly modify the weights of existing concepts ... [in] the application of ESA to text categorization, we trim the interpretation vectors for the sake of efficiency, and only consider a few highest-scoring concepts ... In this scenario, second-order interpretation does have a positive effect and actually improves the accuracy of text categorization ... This happens because only a few selected Wikipedia concepts are used ... and the second-order approach selectively adds highly related concepts identified by analyzing Wikipedia links."
• Evaluation
• Data sets for text categorization: 
• Reuters-21578 with the ModApte split
• 20 Newsgroups (20NG): noisy.
• Movie Reviews (Movies) (Pang, Lee, & Vaithyanathan, 2002)---sentiment (rather than topical) classification
• Reuters Corpus Volume I (RCV1) (Lewis, Yang, Rose, & Li, 2004)
• OHSUMED, a subset of MEDLINE. 
• Reporting results
• "precision-recall break-even point (BEP) to measure text categorization performance"
• "we report both micro- and macro-averaged BEP, since their categories differ in size significantly. Micro-averaged BEP operates at the document level and is primarily affected by categorization performance on larger categories ... macro-averaged BEP averages results for individual categories, and thus small categories with few training examples have large impact on the overall performance."
• "[for] a fixed train/test split [we] used macro sign test (S-test) (Yang & Liu, 1999) to assess the statistical significance of differences in classifier performance... [for] 4-fold cross-validation [we] used paired t-test ... [we] used the non-parametric Wilcoxon signed-ranks test (Demsar, 2006) to compare ... classifiers over multiple data sets. 
• Interesting
• Analysis using examples: "For example, given ... phrase "scientific article" ... ESA determines ... the following Wikipedia concepts ... among the top 20"
• Related work
• Distributional similarity methods (Lee, 1999) compute the similarity of a pair of words w1 and w2 by comparing the distributions of other words given these two, e.g., by comparing vectors of probabilities P(v|w1) and P(v|w2) for a large vocabulary V of words (v \in V ). 
• LSA [manipulates] a vector of ... latent concepts ... obtained through SVD ... of a word-by-document matrix. ... CYC represents semantics of words through an elaborate network of interconnected and richly-annotated concepts ... [and] depend[s] on manual encoding of inference rules.
• With the exception of LSA, most prior approaches to semantic interpretation explicitly represent semantics of individual words, and require an extra level of sophistication to represent longer texts.
• Sahami and Heilman (2006) ... send two snippets as queries to a search engine, and compares the bags of words for the two sets of returned documents. ... it is only applicable to short texts, because sending a long text as a query to a search engine is likely to return few or even no results at all.
• "The above-mentioned based techniques are inherently limited to individual words, and their adaptation for comparing longer texts requires an extra level of complexity (Mihalcea et al., 2006)."
• Text categorization: Zelikovitz and Hirsh (2000) [use] unlabeled examples as intermediaries in comparing testing examples with the training ones. ... when an unknown test instance does not appear to resemble any labeled training instances, unlabeled examples that are similar to both may be used as "bridges." ... [when] the training and the test  document have few or no words in common ... unlabeled documents are utilized to define a cosine similarity metric, which is then used by the KNN algorithm for actual text categorization.
• Potthast, Stein, and Anderka (2008) and Sorg and Cimiano (2008) adapted ESA for multi-lingual and cross-lingual information retrieval.
• Zesch, Mueller, and Gurevych (2008) proposed to use Wiktionary for computing semantic relatedness.