Notes on COLING 2012 - Part 3

Grammarless Parsing for Joint Inference. Jason Naradowsky Tim Vieira, David A. Smith

• Problem: Jointly do grammar and NER (rather do one after the other, in the hope that they may help each other, e.g. an NE span suggests there is a noun phrase)
• Approach: New to the methods applied in this area. Need background to make sense.
• Interesting papers:
• Finkel, J. R. and Manning, C. D. Joint parsing and named entity recognition. NAACL-HLT 2009
• Sarawagi, S. and Cohen, W. W. Semi-Markov conditional random fields for information extraction. NIPS 2004

Text Reuse Detection Using a Composition of Text Similarity Measures. Daniel Bär, Torsten Zesch, Iryna Gurevych.

• Problem: Measure similarity of two pieces of text (for e.g. plagiarism detection)
• Key idea: Previous efforts used content-based measures; they use in addition structure and style as features.
• content: words, synonyms, semantically related words, LSA representations
• structure: stopword/POS n-grams
• style: type/token ratio, function word frequency, token/sentence length
• Use above as features for a machine-learned classifier (Naive Bayes, and decision tree)
• Comments
• Experiments on each corpus discussed separately, including error analysis.
• Report confusion matrix when discussing classification performance.
• Interesting papers:
• Lin, D. An information-theoretic definition of similarity. ICML 1998
• Gabrilovich, E. and Markovitch, S. Computing Semantic Relatedness using Wikipedia-based Explicit Semantic Analysis. IJCAI 2007
• Artstein, R. and Poesio, M. Inter-Coder Agreement for Computational Linguistics. CL 2008

Notes on COLING 2012 - Part 2

Inducing Crosslingual Distributed Representations of Words. Alexandre Klementiev, Ivan Titov, Binod Bhattarai.

• Problem: Learning a semantic space where points represent words, and similar words are nearby
• Key ideas:
•  Use deep learning (neural network-based) to learn low-dimensional (d) representation of words (d fixed arbitrarily). 
• Do the above in a multi-talk learning setting to learn the low-d representation that holds across languages.
• Use a parallel corpus to learn a similarity matrix between words---used for training the multi-task+neural-net model.
• Found several interesting papers that might be worth reading (esp. starred ones)
• * Täckström, O., McDonald, R., and Uszkoreit, J. Cross-lingual word clusters for direct transfer of linguistic structure. NAACL 2012
• * Turian, J., Ratinov, L., and Bengio, Y. Word representations: a simple and general method for semi-supervised learning. ACL 2010
• * Fouss, F., Pirotte, A., Renders, J., and Saerens, M. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE KDE 2007
• Cavallanti, G., Cesa-bianchi, N., and Gentile, C. Linear algorithms for online multitask classification. JMLR 2010
• Socher, R., Huang, E. H., Pennin, J., Ng, A. Y., and Manning, C. D. Dynamic pooling and unfolding recursive autoencoders for paraphrase detection. NIPS 2011
• Huang, E., Socher, R., Manning, C., and Ng, A. Improving word representations via global context and multiple word prototypes. ACL 2012
• Callison-Burch, C., Koehn, P Monz, C., Post, M., Soricut, R., and Specia, L. Findings of the 2012 workshop on statistical machine translation. WMT ACL 2012. (see for preprocessing steps)
• Shi, L., Mihalcea, R., and Tian, M. Cross language text classification by model translation and semi-supervised learning. EMNLP 2010
• Titov, I. Domain adaptation by constraining inter-domain variability of latent feature representation. ACL 2011
• Glorot, X., Bordes, A., and Bengio, Y. Domain adaptation for large-scale sentiment classification: A deep learning approach. ICML 2011
• Zhang, D., Mei, Q., and Zhai, C. Cross-lingual latent topic extraction. ACL 2010
• Fortuna, B. and Shawe-Taylor, J. The use of machine translation tools for cross-lingual text mining. Workshop on Learning with Multiple Views, ICML 2005

Long-tail Distributions and Unsupervised Learning of Morphology. Qiuye Zhao, Mitch Marcus

• Problem: Learning unsupervised morphological analyzers. Previous work assumed power-law distributions for rank-frequency of morph units. They propose log-normal distribution instead.
• Comments: Current approaches to morph analysis have moved beyond ILP and finite state machines. Need to do background reading to understand this work, e.g. Chan, E. Structures and distributions in morphology learning. PhD thesis 2008.

Graph-based Multi-tweet Summarization Using Social Signals. LIU XiaoHua LI Yi Tong WEI FuRu ZHOU Ming.

• Problem: Given a set of tweets, find one that is representative of the lot.
• Approach: Uses scoring functions and features tailored for the problem taking into account saliency, readibility, tweeter diversity, and uses existing work on multi-document summarization and on tweets.
• Comments: Check out user study.

To Exhibit is not to Loiter: A Multilingual, Sense-Disambiguated Wiktionary for Measuring Verb Similarity. Christian M. Meyer, Iryna Gurevych

• Problem:
• Given links between words, identify which senses of the words are actually (supposed to have been) linked.
• Given links between senses of words, infer new links, e.g. between words in different languages.
• Given links between senses of words, compute verb similarity.
• Key Ideas: Start with a dictionary with partial sense information. Disambiguate (remove incorrect) and infer (add new) links.
• Comments: Check out resources created.
• Interesting papers mentioned
• computing semantic relatedness by measuring path lengths (Budanitsky and Hirst, 2006)

Notes on COLING 2012 - Part 1

Extraction of domain-specific bilingual lexicon from comparable corpora: compositional translation and ranking. Estelle DELPECH, Béatrice DAILLE, Emmanuel MORIN, Claire LEMAIRE

• Problem: Extract translations of phrases (not just single words). Focus on fertile translations---target has more words than source.
• Key ideas: 
• split source term into morphemes (helps handle the multi-word case, and also fertility.)
• translate morphemes (A key assumption here is that the parts of the source phrase are compositional)
• recompose into target phrase. This creates several candidates (e.g. by permutation, which are ranked.

Multi-way Tensor Factorization for Unsupervised Lexical Acquisition. Tim Van de Cruys, Laura Rimell, Thierry Poibeau, Anna Korhonen

• Problem: Cluster verbs in a corpus, based on (a) what arguments it can take (b) what arguments it prefers (among those possible), and (c) do the first two jointly.
• Key idea: Use non-negative tensor factorization (Shashua, A. and Hazan, T. Non-negative tensor factorization with applications to statistics and computer vision. ICML 2005) to cluster the verbs.

Incremental Learning of Affix Segmentation. Wondwossen Mulugeta, Michael Gasser, Baye Yimam

• Problem: Affix segmentation (or morpho-analysis) for Amharic (whose morphology seems as complex as Indian languages).
• Approach: Directly used Inductive Logic Programming as described in [Manandhar, S. , Džeroski, S. and Erjavec, T. Learning multilingual morphology with CLOG. ILP 1998]
• Given data of the form: stem([s,e,b,e,r,k,u,l,h],[s,e,b,e,r] [1,1,1,2]). [seber is the stem of seberkulh]
• Learn a set of rules of the form "p :- q" meaning "Do p, if q is true". Example of p: stem(Word, Stem, [1, 2, 7, 0]):-
  set_affix(Word, Stem, [y], [], [u], []),
  feature([1, 2, 7, 0], [simplex, imperfective, tppn, noobj]),
  template(Stem, [1, 0, 1, 1]).
• The order of training data matters a lot. First simpler examples should be given, followed by more complex ones.

Talk on crowdsourcing at CSA

Interesting talk today by Sriganesh Madhvanath from HP Labs on the research problems in crowdsourcing. Many aspects were introduced:

• What should be automated, and what should be crowdsourced?
• How can we guarantee SLO's (service level objectives) when offering services to customers based on crowdsourcing?
• The three axes for trade-off: Error (Accuracy) vs. Time vs. Cost (trying to reduce one causes the others to increase).
• How to reduce the task into small sizes, which can be crowdsourced?
• How to design the user interface to improve the chances of task completion?
• How to combine the results of the crowdsourcing (majority vote, etc.)? 
• How to learn the quality of workers? How to recruit for a given task?
• etc.

Hindi Stop Words List

I found two sources of Hindi stop word lists online: sarai.net, and UniNE. Srivaths R, an undergrad student (from NITK) I am working with, extended the first list to this.

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.)