Misc Research Stuff

Dealing with large scale graphs

2009-07-03T13:01:00.000-07:00

To a hammer everything looks like a nail but one great hammer to have in your toolbox is the graph. The ACL anthology alone lists more than 300 results for the query "graph based". Graphs based formalisms allow us to write down solutions in succinct linear algebra representation. However implementation of such solutions for large problems, or even for small datasets with blown-up graph representations can be challenging in limited resource environments. While some go for interesting approximate solutions, an alternative solution is to pool in several limited resource nodes into a map-reduce cluster and design a parallel algorithm to conquer scale with concurrency. This is easier said than done since designing some parallel algorithms requires a different perspective of the problem. This is well worth the effort as the new insights gained will reveal connections between things you already knew. For instance, in our TextGraphs 2009 paper we started out scaling up Label Propagation but eventually the connection to PageRank became obvious. To me this was a bigger learning moment than getting Label Propagation work for large graphs. [Preprint Copy]

For the actual implementation, we used Hadoop (surprise!) although bulk synchronous parallel models make more sense given the locality of the operations in most graph algorithms.

Sentiment Analysis is AI-Hard

2009-03-31T15:04:00.000-07:00

In a breezy article on sentiment analysis, Alex Wright quotes Bo Pang saying:

We are dealing with sentiment that can be expressed in subtle ways.

This is so true with the examples I've encountered while working and my favorite is this one I saw on iTunes recently.

While I commend Alex for writing an informative yet accessible article on the topic, I disagree with the article's opinion that sentiment analysis is a series of "filters". That is clearly an euphemism. Any working sentiment analysis system is actually an engineering feat often consisting of a series of hacks duct-taped by a glue handling special cases.

The article also seems to suggest that extracting factual information is somehow easier than opinions. I invite them to participate here.

On the way to Brewer's Art

2009-02-28T09:02:00.000-08:00

Never mind how we got to this topic:

me: Parsing is for fogies.

Markus: What?

Jason: I think he means crusty old linguists.

Markus: You should probably use a shallow parser.

me: I'm shallower than that; I use n-grams.

EACL Reading

2008-12-19T11:45:00.000-08:00

EACL 2009 accepted paper list is up. Here's my reading list:

WEAKLY SUPERVISED PART-OF-SPEECH TAGGING FOR RESOURCE-SCARCE LANGUAGES
Kazi Saidul Hasan and Vincent Ng

USING CYCLES AND QUASI-CYCLES TO DISAMBIGUATE DICTIONARY GLOSSES
Roberto Navigli

SYNTACTIC AND SEMANTIC KERNELS FOR SHORT TEXT PAIR CATEGORIZATION
Alessandro Moschitti

SENTIMENT SUMMARIZATION: EVALUATING AND LEARNING USER PREFERENCES
Kevin Lerman, Sasha Blair-Goldensohn and Ryan McDonald

PERSON IDENTIFICATION FROM TEXT AND SPEECH GENRE SAMPLES
Jade Goldstein-Stewart, Ransom Winder and Roberta Sabin

OUTCLASSING WIKIPEDIA IN OPEN-DOMAIN INFORMATION EXTRACTION: WEAKLY-SUPERVISED ACQUISITION OF ATTRIBUTES OVER CONCEPTUAL HIERARCHIES
Marius Pasca

GROWING FINELY-DISCRIMINATING TAXONOMIES FROM SEEDS OF VARYING QUALITY AND SIZE
Tony Veale, Guofu Li and Yanfen Hao

GENERATING A NON-ENGLISH SUBJECTIVITY LEXICON: RELATIONS THAT MATTER
Valentin Jijkoun and Katja Hofmann

CONTEXTUAL PHRASE-LEVEL POLARITY ANALYSIS USING LEXICAL AFFECT SCORING AND SYNTACTIC N-GRAMS
Apoorv Agarwal, Fadi Biadsy and Kathleen Mckeown

COMPANY-ORIENTED EXTRACTIVE SUMMARIZATION OF FINANCIAL NEWS
Katja Filippova, Mihai Surdeanu, Massimiliano Ciaramita and Hugo Zaragoza

ANALYSING WIKIPEDIA AND GOLD-STANDARD CORPORA FOR NER TRAINING
Joel Nothman, Tara Murphy and James R. Curran

And we're back ...

2008-12-02T16:08:00.000-08:00

Sometime back I wrote about Wordle to visualize textual information using frequency counts. Change.gov, Obama's transition team website uses it on the comments in response to their health care system. This is very interesting but I think Wordle should display top 100 collocations instead of top 100 words. But oh, we also learnt at last ACL how to learn collocation information from unigram frequencies.

Too many cooks?

2008-07-17T05:10:00.000-07:00

Computational Linguistics is becoming like the Science or Nature. For instance, see this paper in the current issue: (In this case, the broth wasn't spoiled ;-)

Guess which paper has the largest number of authors on the ACL anthology?

To theory or not to theory

2008-07-08T10:55:00.000-07:00

I stumbled upon this paper "Reflections after Refereeing Papers for NIPS" by Leo Breiman that gives some really candid insights into theory papers. (Unfortunately, I could not find a soft copy to share, except this link.) Some noteworthy observations:

"No theorems" implies "No theory"

"... more than 99% of the published papers are useless exercises."

"Mathematical theory is not critical to development of machine learning."

"Our fields would be better off with far fewer theorems, less emphasis on faddish stuff, and much more into scientific inquiry and engineering."

I really liked this article, especially coming from someone who has been working in theory all his life but I would still prefer reading papers giving theoretical insight, however useless, than pages and pages of feature engineering & experimentation using classifier X on problem Y -- the current trend at ACL.

A quick scan at ACL

2008-07-07T06:49:00.000-07:00

Mendicant Bug informs about a new tag-cloud service called Wordle. Here is a look at this year's ACL. Gives a clear idea of what is going on! A larger image is available here.

Powerset Natural Language Search

2008-05-11T22:43:00.000-07:00

Powerset, a company we only remember seeing as conference sponsors, now actually has something working. After receiving an email from them, I tried out several queries. At best, it seems to answer most Wh-questions and certain whole-part relations.

Try out the same query on Google.

Writing style

2008-04-03T20:35:00.000-07:00

The sweetest thing ever written in a paper: "The reader who is unfamiliar with this field or who has allowed his or her facility with some of its concepts to fall into disrepair may profit from a brief perusal of Feller (1950) and Gallagher (1968)."

- Brown et. al., "Class based n-gram Models of Natural Language.", Computational Linguistics, 1990

Searching ACL anthology

2008-03-28T11:54:00.000-07:00

If you are looking up the ACL anthology regularly, my friend Markus has a nice firefox search plugin to do that. You can get that and others from this page.

ACL accepted papers

2008-03-27T21:26:00.000-07:00

Hal posted a while back about the ACL accepted papers that I just read now -- I've been living under a rock for some time. You can get a printer friendly version here. I know, my paper did not make it to that list :(

New additions to my reading list:

Distributional Identification of Non-Referential Pronouns
Shane Bergsma, Dekang Lin and Randy Goebel

An Unsupervised Approach to Biography Production using Wikipedia
Fadi Biadsy, Julia Hirschberg and Elena Filatova

Resolving Personal Names in Email Using Context Expansion
Tamer Elsayed, Douglas Oard and Galileo Namata

Mining Wiki Resources for Multilingual Named Entity Recognition
Alexander Richman and Patrick Schone

Inducing Gazetteers for Named Entity Recognition by Large-scale Clustering of Dependency Relations
Jun'ichi Kazama and Kentaro Torisawa

Name Translation in Statistical Machine Translation - Learning When to Transliterate
Ulf Hermjakob, Kevin Knight and Hal Daume

The Tradeoffs Between Open and Traditional Relation Extraction
Michele Banko and Oren Etzioni

(Longest paper title)
Unsupervised Discovery of Generic Relationships Using Pattern Clusters and its Evaluation by Automatically Generated SAT Analogy Questions
Dmitry Davidov and Ari Rappoport

Finding Contradictions in Text
Marie-Catherine de Marneffe, Anna Rafferty and Christopher Manning

Extracting Question-Context-Answer Triples from Online Forums
Shilin Ding, Gao Cong, Chin-Yew Lin and Xiaoyan Zhu

EM Can Find Pretty Good HMM POS-Taggers (When Given a Good Start)
Yoav Goldberg, Meni Adler and Michael Elhadad

Extraction of Entailed Semantic Relations Through Syntax-based Comma Resolution
Vivek Srikumar, Roi Reichart, Mark Sammons, Ari Rappoport and Dan Roth

Learning Bigrams from Unigrams
Xiaojin Zhu, Andrew Goldberg, Michael Rabbat and Robert Nowak

Evaluating Roget's Thesauri
Alistair Kennedy and Stan Szpakowicz

Randomized Language Models via Perfect Hash Functions
David Talbot and Thorsten Brants

Solving Relational Similarity Problems Using the Web as a Corpus
Preslav Nakov and Marti Hearst

What do you do?

2008-02-24T17:50:00.001-08:00

As a grad student working on NLP how do you explain what you are working on, to friends and family? I inevitably end up referring to the Google search engine even though what I do is quite far from IR. Actually, thats not true. These days IR seems to consume everything but thats another story.

This reminds me of a funny conversation at CLSP recently:

Sanjeev is telling us about an incident where a concerned parent of a young child with a speaking disability is asking him for his opinion. Apparently, she is confused about "Language and Speech Processing" in CLSP.

Keith butts in: "Run a few more iterations of EM and he'll be fine."

A song on parsing

2008-02-14T01:23:00.000-08:00

We all know Jason's love for parsing from his work but it takes a different level of dedication to write a Valentine's Day song about parsing.

As Jason says, "Parsers just want to be appreciated, like everyone else."

Funny bone

2007-10-17T17:07:00.000-07:00

The frequentist exclaimed, "All your Bayes are belong to us!" to which the Bayesian responded, "Well, it depends."

NIPS papers are out

2007-09-20T22:58:00.000-07:00

For a full list see here. Some papers I want to read based on my current interests:

Random Projections for Manifold Learning
Chinmay Hegde, Michael Wakin, Richard Baraniuk

The Distribution Family of Similarity Distances
Gertjan Burghouts, Arnold Smeulders, Jan-Mark Geusebroek

Manifold Sculpting
Michael Gashler, Dan Ventura, Tony Martinez

A learning framework for nearest neighbor search
Lawrence Cayton, Sanjoy Dasgupta

Learning Bounds for Domain Adaptation
John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, Jennifer Wortman

Convex Relaxations of EM
Yuhong Guo, Dale Schuurmans

A Randomized Algorithm for Large Scale Support Vector Learning
Krishnan Kumar, Chiru Bhattacharya, Ramesh Hariharan

Bundle Methods for Machine Learning
Alex Smola, S V N Vishwanathan, Quoc Le

Regularized Boost for Semi-Supervised Learning
Ke Chen, Shihai Wang

Learning the structure of manifolds using random projections
Yoav Freund, Sanjoy Dasgupta, Mayank Kabra, Nakul Verma

A complexity measure for intuitive theories
Charles Kemp, Noah Goodman, Joshua Tenenbaum

NLP and Global Warming

2007-08-18T00:40:00.000-07:00

Those of us who were at EMNLP-CONLL 2007 remember the "NLP and Global Warming" exchange between James Clarke, Jason Eisner, and Dan Bikel at the Q/A session of the Clarke and Lapata paper. The transcript of this funny conversation is now online, thanks to Jason.

I really liked Hal's ending remark.

People Search on the Web

2007-08-15T16:16:00.001-07:00

Wired has an article about spock.com, a people search engine that combines crawled and user added content. From the few searches I did, looks like this is good for celebrity names than a regular person with web content. For instance, searching a name like "David Smith" produces these results. Of the top 10 results, only 3 of them actually have the name "David Smith" or something closer and the first result is not one of them. Compare this with a general purpose search engine like Google. Among a dozen random NLP/ML academic names (professors) I tried, it only got Jason Eisner and Tom Mitchell correct. One reason for this poor recall is probably they don't get content from user home pages.
(Some sites where this data is derived from include MySpace, Friendster, IMDB, Wikipedia, ratemyprofessors.com, etc.)

Nevertheless, this website is a representative of interesting KDD-style problems that one could do with people names. It is also interesting as people names that we look for fall in the "long tail" without sufficient data to support calling for clever machine learning techniques.

Digital Reasoning awarded contextual similarity patent?

2007-08-12T12:30:00.000-07:00

I was lead to this article on Forbes via Damien's post. The article is about a company Digital Reasoning getting patent on what sounded to me as contextual similarity. Their "white paper" makes reference to a patent number 7249117 (via USPTO). Unlike research papers, reading the patent document was so difficult. Will get to it sometime later but here is an extract from their press release about what their technology can do.

* Learn the meanings of words, classes of words, and other symbols based on how they are used in context in natural language
* Create and manipulate models of this "meaning" - i.e. the mathematical patterns of usage - including the detection of groups or similar categories of words or development of hierarchies or creation of relationships between words
* Improve the models based on human feedback or using other structured information after model construction
* The representation or sharing of this model or learning in an ontology, graph structure, or programming languages

Anyone from the ACL/ML/AI community can immediately recognize this and start citing their favorite papers on these topics starting from at least a decade ago. A promotional video from the company on YouTube can be found here. Excerpt from the video: "... We treat the text representation of human language as a signal ... ".

I think everyone should stop taking patents seriously. Wishful thinking?

Recommending scientific papers

2007-08-02T19:40:00.000-07:00

I noticed a new feature in Citeseer which tries suggest an "alternate document" for a paper.

Clearly it does not do what it implies to do and it doesn't show up for all papers. (Experimental?) So, an interesting question is how does one recommend scientific papers? Something more than mere document similarity is required. If I am reading a CRF paper then there is no point in listing all papers containing similar words. Just listing nodes connected to inward and outward links of the paper in the citation graph wont suffice either. Ideal recommendations for a paper would depend on the role the user is playing. When I am reading a paper about some new topic, I would like to get pointed to original papers on the topic, some recent papers on the topic, and may be some survey papers or books. On the other hand when I am writing a paper, I would like to be pointed to all papers related to the topic (recall important than precision here to avoid reviewer comments on "missing reference") in some magical order that puts papers more relevant to your work above. Also these papers might not be related in directly through citations. If there is a recent related work in the Annals of Statistics, for instance, then it should show up when I am working on, say, approximate inference methods for graphical models. (Possible to deduce this from my previous queries?)

In spite of more information being present in a scientific paper than its text, recommending or ranking papers appears to be quite challenging.

Google allows data binging for researchers

2007-07-26T22:14:00.000-07:00

Google now opened access to university researchers to its search and MT systems in today's announcement on their research blog. The search API documentation does not mention any restriction on the number of queries that can be posted for search (The earlier limit was 1000). Whatever the number is I am guessing it will be large (Drinking from the firehose?). However, the MT API allows 1000 queries per day with the documentation hinting that this need not be a hard limit.

Looking at the search API output, two things I really miss is the number of hits and the snippet for each search result. The number of hits has been used in several papers for interesting results. The other useful feature is snippets. Every search result from Google is accompanied by a small snippet extracted from the page, as shown below for an example query "Dekang Lin".

The information in the snippets can be used as informative features in different tasks like this one in person name disambiguation. (BTW, Dekang is now at Google)

Despite these minor quibbles, these new APIs will be quite useful to all of us and will certainly result in more papers on Googleology.

Later addition: Turns out we can sort of get the counts by simply counting the number of search results by repeatedly executing the request (only ten results per request) but the API caps this limit to 100. That means you could get a maximum of 1000 results. Which is not quite the same as "Results 1 - 10 of about 779,000,000". Though that number is approximate, it is still indicative of how strong the query is w.r.t the web. For example GoogleCount("Horse+animal") >> GoogleCount("Horse+truck").

Readings from SIGIR 2007

2007-07-24T09:53:00.000-07:00

SIGIR 2007 is happening now at Amsterdam!

Latent Concept Expansion Using Markov Random Fields, Donald Metzler, Bruce Croft

Random Walks on the Click Graph, Nick Craswell, Martin Szummer

Towards Automatic Extraction of Event and Place Semantics from Flickr Tags, Tye Rattenbury, Nathaniel Good, Mor Naaman

Clustering of Documents with Local and Global Regularization, Fei Wang, Changshui Zhang, Tao Li

Detecting, Categorizing and Clustering Entity Mentions in Chinese Text, Wenjie Li, Donglei Qian, Chunfa Yuan, Qin Lu

Principles of Hash-based Text Retrieval, Benno Stein

DiffusionRank: A Possible Penicillin for Web Spamming, Haixuan Yang, Irwin King, Michael R. Lyu

Context Sensitive Stemming for Web Search, Fuchun Peng, Nawaaz Ahmed, Xin Li, Yumao Lu

Combining Content and Link for Classification using Matrix Factorization, Shenghuo Zhu, Kai Yu, Yun Chi, Yihong Gong

ARSA: A Sentiment-Aware Model for Predicting Sales Performance Using Blogs, Yang Liu, Jimmy Huang, Aijun An, Xiaohui Yu

Heavy-Tailed Distributions and Multi-Keyword Queries, Arnd Konig, Surajit Chaudhuri, Liying Sui, Kenneth Church

Readings from AAAI 2007

2007-07-23T15:56:00.000-07:00

AAAI 2007 is now going on at Vancouver. Here is my selection of NLP and Learning papers I would like to know more about.

Deriving a Large-Scale Taxonomy from Wikipedia, Simone Paolo Ponzetto, Michael Strube

Relation Extraction from Wikipedia Using Subtree Mining, Dat P. T. Nguyen, Yutaka Matsuo, Mitsuru Ishizuka

Finding Related Pages Using Green Measures: An Illustration with Wikipedia, Yann Ollivier, Pierre Senellart

Graph Partitioning Based on Link Distributions, Bo Long, Mark (Zhongfei) Zhang, Philip S. Yu

Semi-supervised Learning by Mixed Label Propagation, Wei Tong, Rong Jin

Semi-Supervised Learning with Very Few Labeled Training Examples, Zhi-Hua Zhou, De-Chuan Zhan, Qiang Yang

Clustering with Local and Global Regularization, Fei Wang, Changshui Zhang, Tao Li

Isometric Projection, Deng Cai, Xiaofei He, Jiawei Han

Improving Similarity Measures for Short Segments of Text, Wen-tau Yih, Christopher Meek

Topic Segmentation Algorithms for Text Summarization and Passage Retrieval: An Exhaustive Evaluation, Gaël Dias, Elsa Alves. José Gabriel Pereira Lopes

Robust Estimation of Google Counts for Social Network Extraction, Yutaka Matsuo, Hironori Tomobe, Takuichi Nishimura

Harvesting Relations from the Web - Quantifiying the Impact of Filtering Functions, Sebastian Blohm, Philipp Cimiano, Egon Stemle

Template-Independent News Extraction Based on Visual Consistency, Shuyi Zheng, Ruihua Song, Ji-Rong Wen

Comprehending and Generating Apt Metaphors: A Web-driven, Case-based Approach to Figurative Language, Tony Veale, Yanfen Hao

Mobile Service for Reputation Extraction from Weblogs - Public Experiment and Evaluation, Takahiro Kawamura, Shinichi Nagano, Masumi Inaba, Yumiko Mizoguchi

The Impact of Time on the Accuracy of Sentiment Classifiers Created from a Web Log Corpus, Kathleen T. Durant, Michael D. Smith

Nectar: Learning by Combining Observations and User Edits, Vittorio Castelli, Lawrence Bergman, Daniel Oblinger

Multi-Label Learning by Instance Differentiation, Min-Ling Zhang, Zhi-Hua Zhou

Extracting Influential Nodes for Information Diffusion on a Social Network, Masahiro Kimura, Kazumi Saito, Ryohei Nakano

Temporal and Information Flow Based Event Detection from Social Text Streams, Qiankun Zhao, Prasenjit Mitra, Bi Chen

Analyzing Reading Behavior by Blog Mining, Tadanobu Furukawa, Mitsuru Ishizuka, Yutaka Matsuo, Ikki Ohmukai, Koki Uchiyama

Reading List from KDD 2007

2007-07-18T12:57:00.000-07:00

KDD 2007 will be on Aug 12-15 in the neighborhood at San Jose. Here is my selection:

"Extracting Semantic Relations from Query Logs", Ricardo Baeza-Yates and Alessandro Tiberi

"Efficient Incremental Clustering with Constraints", Ian Davidson, S.S. Ravi, and Martin Ester

"A Probabilistic Framework for Relational Clustering", Bo Long, Zhongfei Zhang, and Philip S. Yu

"Tracking Multiple Topics for Finding Interesting Articles", Raymond Pon, Alfonso Cardenas, David Buttler, and Terence Critchlow

"Feature Selection Methods for Text Classification", Anirban Dasgupta, Petros Drineas, Boulos Harb, Vanja Josifovski, and Michael Mahoney

"Hierarchical Mixture Models: a Probabilistic Analysis", Mark Sandler

"Information distance from a question to an answer", Xian Zhang, Yu Hao, Xiaoyan Zhu, and Ming Li

"Statistical Change Detection for Multi-Dimensional Data", Xiuyao Song, Mingxi Wu, Chris Jermaine, and Sanjay Ranka

"Constraint-Driven Clustering", Rong Ge, Martin Ester, Wen Jin, and Ian Davidson

"Enhancing Semi-Supervised Clustering: A Feature Projection Perspective", Wei Tang, Hui Xiong, Shi Zhong, and Jie Wu

NLP in India?

2007-07-17T18:40:00.000-07:00

I was surprised to see Alex's post to which I don't agree fully.

... because NLP is so underdeveloped in India, even undergraduate-level projects may be contributing to the cutting edge of research.

Turns out he was referring to this post from an undergrad which tries to give "the Indian perspective", rather inaccurately. Having worked on NLP at one of the IITs I am compelled to write from a grad student perspective. Sunayana's post is interesting as it brings out several issues in Indic computing.

1. Lack of annotation data - corpora, treebanks, and aligned texts which are sinews and bones of any language processing system. Resources exist, largely due to the efforts of CIIL, various universities and other government agencies but these are dwarfed compared to resources that exist for other languages, like English or the European languages.

However, the rich morphology in Indian languages can be exploited to mitigate the amount of annotation data required for certain tasks, for instance POS tagging.

2. Encoding issues - As rightly pointed by Sunayana, before the adoption of unicode, several data sources were locked up in the fonts they use. But things are changing, there is more and more Indian language content in unicode today than ever. Websites like BBC and Wikipedia are spewing out a lot of content in unicode for those interested in collecting monolingual, comparable corpora. A cursory glance at Wikipedia statistics shows the number of articles in, say Hindi or Tamil for example, has more than doubled in the past six months.

3. Visibility - While there has been an increasing trend to publish in reputed conferences like ICML or ACL, more participation is certainly desirable. IJCAI 2007 was held in India and I highly recommend, if you are around, to submit (sub. deadline: Jul 31st) and/or attend IJCNLP 2008.

This is an exciting time to do NLP research on Indian languages. There is both corporate as well as government motivations which translate to grants and support to universities. The group at IIT Bombay, for example, implemented and deployed, local language based systems for helping farmers. Similar efforts have been taken by other institutes. Microsoft research at Bangalore, and IBM research at New Delhi and Bangalore are working on various projects on Indian Languages, including speech recognition.

At the end of all this, I must partially agree with the quote I made from Alex's blog. Yes, some undergrads do make brilliant contributions which is just because of what they have in their bones. This is true for any country or university.

Effect of Spouses on PhD

2007-07-17T09:42:00.000-07:00

Joseph Price studies the effect of marriage on graduation in his paper, "Does a Spouse Slow You Down?: Marriage and Graduate Student Outcomes".

Here is a quick abstract:

Using data on 11,000 graduate students from 100 departments over a 20 year period, I test whether graduate student outcomes (graduation rates, time to degree, publication success, and initial job placement) differ based on a student’s gender and marital status. I find that married men have better outcomes across every measure than single men. Married women do no worse than single women on any measure and actually have more publishing success and complete their degree in less time. The outcomes of cohabiting students generally fall between those of single and married students.

Papers from COLT: Occam's Hammer

2007-07-02T10:57:00.000-07:00

John Langford recommends:

Gilles Blanchard and François Fleuret, Occam’s Hammer. When we are interested in very tight bounds on the true error rate of a classifier, it is tempting to use a PAC-Bayes bound which can (empirically) be quite tight. A disadvantage of the PAC-Bayes bound is that it applies to a classifier which is randomized over a set of base classifiers rather than a single classifier. This paper shows that a similar bound can be proved which holds for a single classifier drawn from the set. The ability to safely use a single classifier is very nice. This technique applies generically to any base bound, so it has other applications covered in the paper.

ICML 2007 reading list

2007-07-02T10:47:00.001-07:00

Some papers I would like reading right away:

Discriminative Learning for Differing Training and Test Distributions
Steffen Bickel - Max Planck Institute for Computer Science, Germany
Michael Brüeckner - Max Planck Institute for Computer Science, Germany
Tobias Scheffer - Max Planck Institute for Computer Science, Germany

Sparse Eigen Methods by D.C. Programming
Bharath Sriperumbudur - University of California, San Diego, USA
David Torres - University of California, San Diego, USA
Gert Lanckriet - University of California, San Diego, USA

Graph Clustering With Network Structure Indices
Matthew J. Rattigan - University of Massachusetts Amherst, USA
Marc Maier - University of Massachusetts Amherst, USA
David Jensen - University of Massachusetts Amherst, USA

Fast and Effective Kernels for Relational Learning from Texts
Alessandro Moschitti - University of Trento, Italy
Fabio Massimo Zanzotto - University of Rome, Italy

Three New Graphical Models for Statistical Language Modelling
Andriy Mnih - University of Toronto, Canada
Geoffrey Hinton - University of Toronto, Canada

Simple, Robust, Scalable Semi-supervised Learning via Expectation Regularization
Gideon S. Mann - University of Massachusetts, USA
Andrew McCallum - University of Massachusetts, USA

The Rendezvous Algorithm: Multiclass Semi-Supervised Learning with Markov Random Walks
Arik Azran - University of Cambridge, UK

Information-Theoretic Metric Learning (one of the best paper awardees)
Jason V. Davis - University of Texas at Austin, USA
Brian Kulis - University of Texas at Austin, USA
Prateek Jain - University of Texas at Austin, USA
Suvrit Sra - University of Texas at Austin, USA
Inderjit S. Dhillon - University of Texas at Austin, USA

Agnostic Active Learning - not from ICML 2007 but exciting as it was discovered last year, theoretical bounds were proved this year in ICML 2007.
http://hunch.net/~jl/projects/agnostic_active/agnostic-active.pdf

A Bound on the Label Complexity of Agnostic Active Learning
Steve Hanneke - Carnegie Mellon University, USA

Learning about Kernels

2007-07-02T09:53:00.000-07:00

Stumbled on Alekh Agarwal's tech report on Kernels. A good survey on kernel methods that includes recent work on this topic.

http://www.cse.iitb.ac.in/~alekh/seminar/report.pdf

Another place to begin would be Thomas Gartner's SIGKDD explorations survey paper.

UMASS Statistical NLP reading list

2007-06-07T13:35:00.000-07:00

http://ciir.cs.umass.edu/~fuchun/readlist_all/readlist.pdf

Reading List from EMNLP 2007

2007-04-30T13:33:00.000-07:00

A GRAPH-BASED APPROACH TO NAMED ENTITY CATEGORIZATION IN WIKIPEDIA
USING CONDITIONAL RANDOM FIELDS
Yotaro Watanabe, Masayuki Asahara and Yuji Matsumoto

A TOPIC MODEL FOR WORD SENSE DISAMBIGUATION
Jordan Boyd-Graber, Xiaojin Zhu and David Blei

BOOTSTRAPPING INFORMATION EXTRACTION FROM FIELD BOOKS
Sander Canisius and Caroline Sporleder

CROSS-LINGUAL DISTRIBUTIONAL PROFILES OF CONCEPTS FOR MEASURING
SEMANTIC DISTANCE
Saif Mohammad, Iryna Gurevych, Graeme Hirst and Torsten Zesch

CRYSTAL: ANALYZING PREDICTIVE OPINIONS ON THE WEB
Soo-Min Kim and Eduard Hovy

EXPLORATIONS IN AUTOMATIC BOOK SUMMARIZATION
Rada Mihalcea and Hakan Ceylan

LARGE SCALE NAMED ENTITY DISAMBIGUATION BASED ON WIKIPEDIA DATA
Silviu Cucerzan

LEXICAL SEMANTIC RELATEDNESS WITH RANDOM GRAPH WALKS
Thad Hughes and Daniel Ramage

TOWARDS ROBUST UNSUPERVISED PERSONAL NAME DISAMBIGUATION
Ying Chen and James Martin

WORD SENSE DISAMBIGUATION INCORPORATING LEXICAL AND STRUCTURAL SEMANTIC
INFORMATION
Takaaki Tanaka, Francis Bond, Timothy Baldwin, Sanae Fujita and Chikara
Hashimoto

LaTex cool!

2007-04-15T17:47:00.000-07:00

The constant is defined as
For more details on the setup, refer here.

Swivel: For cool looking graphs

2007-03-22T21:26:00.000-07:00

Internet Language Resources

2007-03-21T20:12:00.000-07:00

....

Bafia (Mbam Cameroon)                        Wayumbe
Bagesu (Central Africa)                      Watulire?
Bagesu (Central Africa) [answer]             Natulire nili mlahi
Bajawa (Indonesia) ['where are you going']   Male de?
Bakitara (Central Africa) [morning]          Oirwota?
Bakitara (Central Africa) [answer]           Ndabanta
Bakitara (Central Africa) [after absense]    Mirembe
Bakweri (Cameroon) [morning]                 O wusi
Balanta (Guinea-Bissau)                      Abala, lite utchole
Balinese (Bali)                              Om swastyastu
Balinese (Bali) [reply]                      Om shanti shanti shanti
Balti (India, Pakistan)                      Yang chi halyo?
Balti (India, Pakistan) [answer]             Lyakhmo

....

That was "hello" in some languages. Jennifer Runner has this page with "Hello" and other pleasantries in a large number of languages. Don't forget to check her Internet Language Resources page.

Khau bulyghyz!

Job with "The Company"

2007-03-18T21:34:00.000-07:00

Showed up while reading my regular mails. Notice the typo in the headline.

Interesting papers from NAACL and WWW 2007

2007-03-18T20:42:00.000-07:00

NAACL

Computing Semantic Similarity between Skill Statements for Approximate Matching
Feng Pan and Robert Farrell

Extracting Appraisal Expressions
Kenneth Bloom, Shlomo Argamon and Navendu Garg

Unsupervised Resolution of Objects and Relations on the Web
Alexander Yates and Oren Etzioni

Near-Synonym Choice in an Intelligent Thesaurus
Diana Inkpen

Using Wikipedia for Automatic Word Sense Disambiguation
Rada Mihalcea

An integrated approach to measuring Semantic Similarity between Words using Information available on the Web
Danushka Bollegala, Yutaka Matsuo and Mitsuru Ishizuka

Improving Relation Extraction Using Domain Information
Alfio Massimiliano Gliozzo, Marco Pennacchiotti and Patrick Pantel

High-Performance, Language-Independent Morphological Segmentation
Sajib Dasgupta and Vincent Ng

A Systematic Exploration of The Feature Space for Relation Extraction
Jing Jiang and ChengXiang Zhai

Data-Driven Graph Construction for Semi-Supervised Graph-Based Learning in NLP
Andrei Alexandrescu and Katrin Kirchhoff

WWW

Towards Domain-Independent Information Extraction from Web Tables
Wolfgang Gatterbauer, Paul Bohunsky, Marcus Herzog, Bernhard Kroepl, Bernhard Pollak

Organizing and Searching the World Wide Web of Facts - Step Two: Harnessing the Wisdom of the Crowds
Marius Pasca

A New Suffix Tree Similarity Measure for Document Clustering
Hung Chim, Xiaotie Deng

Scaling Up All-Pairs Similarity Search
Roberto Bayardo, Yiming Ma, Ramakrishnan Srikant

Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography
Lars Backstrom, Cynthia Dwork, Jon Kleinberg

Topic Sentiment Mixture: Modeling Facets and Opinions in Weblogs
Qiaozhu Mei, Xu Ling, Matthew Wondra, Hang Su, ChengXiang Zhai

Measuring Semantic Similarity between Words Using Web Search Engines
Danushka Bollegala, Yutaka Matsuo, Mitsuru Ishizuka

Using Google Distance to weight approximate ontology matches
Risto Risto Gligorov, Zharko Aleksovski, Warner ten Kate, Frank van Harmelen

NLP on VVLC

2007-03-18T20:38:00.000-07:00

Papers to read
1. Banko and Brill, ACL 2001
2. Deepak Ravichandran, ACL 2005

Beryl, Oh yeah!

2007-01-26T21:41:00.000-08:00

After much struggling with my ubuntu, I got Beryl finally on my laptop.
Getting it work with ATI was always a problem (for me) until this guide.

Incidentally, this is just a few days from the Vista launch. Who cares about Vista anymore?

Multibabel

2007-01-25T19:06:00.000-08:00

Ever wondered what happened when a message is converted from one language to another and so on and finally back to the source language?

Try: http://www.tashian.com/multibabel

Even a simple sentence, I am fine, gets distorted as:

They are much bond.They are much plugging.They are covering much.Uses BabelFish underneath, I wouldn't be surprised if Google or any other MT system also shows similar output.

Interesting ML notes

2007-01-18T16:33:00.000-08:00

Machine Leaning. Where are we heading? Tom Mitchell says it all - machine learning != statistics.

How to write a machine learning paper?
http://www-csli.stanford.edu/icml2k/craft.html

Back from IJCAI

2007-01-18T15:08:00.000-08:00

I spent much of the fall break attending IJCAI 2007 and ICON 2007. IJCAI had a record attendance of 1500 plus participants.

Book Review: Geometry and Meaning

2006-12-26T15:28:00.000-08:00

Title: Geometry and Meaning
Author: Dominic Widdows
URL : http://infomap.stanford.edu/book/

This is an excellent book for even high school students to learn about IR. However, if you have read a few papers in this field then reading this book is a waste of time, except for the jewels in boxes throughout the book.

semantic ambiguity?

2006-12-21T17:09:00.000-08:00

lectures on cognitive computing

2006-12-21T13:03:00.000-08:00

A series of twelve lectures from the conference on cognitive computing at IBM's Almaden
Research lab with topics ranging from memory to consciousness to thought.

Lecture videos

smoothing

2006-12-21T00:55:00.000-08:00

A good review article on smoothing by Stan Chen and Roni Rosenfeld.
A thorough treatment can be found here.

Accuracy vs. Perplexity

2006-12-20T18:39:00.000-08:00

If model A has higher accuracy than model B, does it necessarily imply
perplexity(A) < perplexity(B)?

Jason's reply:

No, that is not implied.
Accuracy = how correct is the highest-probability hypothesis?
Perplexity = how probable is the correct hypothesis?
(or more generally, how probable is the observed data?)

So they are really measuring different things.
Accuracy is what you really care about, in a sense,
but (1) it is only defined if you have supervised data,
(2) it requires an evaluation method for measuring degree
of correctness, (3) it is usually not a continuous function
of the parameters (since an epsilon change in the parameters
may not change which hypothesis has the highest probability)
and is therefore hard to optimize.

I usually recommend reporting both, which has become
the convention in speech recognition, where people report
WER (word error rate) and perplexity.

Finding concordances on the web

2006-12-20T16:50:00.000-08:00

A cool website that does this: http://www.webcorp.org.uk
Allows using patterns but awfully slow.

TKDE special issue on semantic web

2006-12-20T09:18:00.000-08:00

Its here ... slurrrp! yum yum.

Interesting papers to my general reading list:
1. From Wrapping to Knowledge
2. Mining Generalized Associations of Semantic Relations from Textual Web Content
3. A Taxonomy Learning Method and Its Application to Characterize a Scientific Web Community

You can access all articles here

New IR book

2006-12-18T16:25:00.000-08:00

Just discovered this book by Chris Manning, Prabhakar Raghavan, and Hinrich Schütze.
This is going to be in my reading list for the IR Course, next spring.

Hidden Markov Models

2006-12-18T15:21:00.000-08:00

After a brief venture in developing HMMs for sequence labeling at the NLP class, I am planning to use the HTK toolkit for more fun!

Get it today from: http://htk.eng.cam.ac.uk/
A tutorial style manual on HTK can be obtained here.

Also don't forget to read Hal's wonderful writeup on sequence labeling.

Update: If you are planning to write a HMM tagger of your own, in addition to the above handout, have a look at the following:

1. A practical Part-of-Speech tagger
A general introduction. Involves right mix of math and implementation details.
2. Equations for Part-of-Speech tagging
Derives all equations for PoS tagging using HMMs from first principles
(smoothing & EM included)

Though not related to HMMs, TagChunk by Hal Daume is another way for sequence labeling (software included)

Adversarial Information Retrieval 2007

2006-12-18T07:42:00.000-08:00

Contents:

1. AIRWeb'07 Topics
2. Web Spam Challenge
3. Timeline
4. Organizers and Program Committee

1. AIRWEB'07 TOPICS

Adversarial Information Retrieval addresses tasks such as gathering,
indexing, filtering, retrieving and ranking information from collections
wherein a subset has been manipulated maliciously. On the Web, the
predominant form of such manipulation is "search engine spamming" or
spamdexing, i.e., malicious attempts to influence the outcome of ranking
algorithms, aimed at getting an undeserved high ranking for some items
in the collection.

We solicit both full and short papers on any aspect of adversarial
information retrieval on the Web. Particular areas of interest include,
but are not limited to:

* Link spam
* Content spam
* Cloaking
* Comment spam
* Spam-oriented blogging
* Click fraud detection
* Reverse engineering of ranking algorithms
* Web content filtering
* Advertisement blocking
* Stealth crawling
* Malicious tagging

Proceedings of the workshop will be included in the ACM Digital Library.
Full papers are limited to 8 pages; work-in progress will be permitted 4
pages.

For more information, see

2. WEB SPAM CHALLENGE

This year, we are introducing a novel element: a Web Spam Challenge for
testing web spam detection systems. We will be using the WEBSPAM-UK2006
collection for Web Spam Detection .

The collection includes large set of web pages, a web graph, and
human-provided labels for a set of hosts. We will also provide a set of
features extracted from the contents and links in the collection, which
may be used by the participant teams in addition to any automatic
technique they choose to use.

We ask that participants of the Web Spam Challenge submit predictions
(normal/spam) for all unlabeled hosts in the collection. Predictions
will be evaluated and results will be announced at the AIRWeb 2007
workshop.

For more information, see

3. TIMELINE

- 7 February 2007: E-mail intention to submit a workshop paper
(optional, but helpful)
- 15 February 2007: Deadline for workshop paper submissions
- 15 March 2007: Notification of acceptance of workshop papers
- 30 March 2007: Camera-ready copy due
- 30 March 2007: Challenge submissions due
- 8 May 2007: Date of workshop

...

eye candy for developers

2006-12-16T21:25:00.000-08:00

This is not directly related to research but if you are like me, spending a long time in front of the screen staring at the console (coding or even playing hangman!), check out the cool new fonts that come with vista. Although I have been windows free (just like my lab) for a year now, these vista fonts are something I can vouch for. Search Google for "six new vista fonts" to download them. Since they are in TTF, they work perfectly on my Ubuntu (not sure if this is right, heck I enjoy the font. Thanks Bill!).

I have been using the Consolas font for my Gnome terminal and it rocks!

MIT EECS Matlab tutorial

2006-12-16T20:47:00.001-08:00

Nice introduction to Matlab

Graphical models reading group

2006-12-16T20:40:00.000-08:00

Collection of some basic reading material on the subject. Warning: its old (2004)
http://www.cs.cmu.edu/~zhuxj/courseproject/graphical.html

The Dragon Tooolkit

2006-12-14T06:13:00.000-08:00

The Dragon Tooolkit is Java-based development package for academic research use in language modeling (LM) and information retrieval (IR). Language modeling has recently emerged as an attractive new framework for text information retrieval and text mining (TM). However, most Java-based free search engines such as Lucene does not support LM very well. The Lemur toolkit is designed for LM and IR, but written in C and C++, which may be a hindrance to people who prefer Java programming. Basically, the dragon toolkit is tailored for researchers who work on large-scale LM and IR and prefer Java programming. Moreover, different from Lucene and Lemur, it provides built-in supports for semantic-based IR and TM. The dragon tookit seamlessly intergrates and implements a set of NLP tools, which enable the toolkit to index text collections with various representation schemes including words, phrases, ontology-based concepts and relationships. However, to minimize the learning time, we intentionally keep the package small and simple. The toolkit does not have some features including distributed IR and cross-language IR which are part of Lemur toolkit.

How to Cite Dragon Toolkit

If you are using the Dragon Toolkit for research work, please cite it in your published papers:

Zhou, X., Zhang, X., and Hu, X., The Dragon Toolkit, Data Mining & Bioinformatics Lab, iSchool at Drexel University, http://www.ischool.drexel.edu/dmbio/dragontool

Download Dragon Toolkit

Get the Dragon Toolkit source code and binary libraries (including external libraries) and necessary supporting data. Click http://www.ischool.drexel.edu/dmbio/dragontool/default.asp to download.

Graph-based Methods for Natural Language Processing

2006-12-14T06:12:00.000-08:00

NAACL/HLT 2007 Workshop
Graph-based Methods for Natural Language Processing

http://www.textgraphs.org/ws07

Rochester, NY, April 26, 2007
.................................................

Recent years have shown an increased interest in bringing the field of
graph theory into Natural Language Processing. In many NLP
applications entities can be naturally represented as nodes in a graph
and relations between them can be represented as edges. Recent
research has shown that graph-based representations of linguistic
units as diverse as words, sentences and documents give rise to novel
and efficient solutions in a variety of NLP tasks, ranging from part
of speech tagging, word sense disambiguation and parsing to
information extraction, semantic role assignment, summarization and
sentiment analysis.

This workshop builds on the success of the first TextGraphs workshop at

HLT-NAACL 2006. The aim of this workshop is to bring together researchers

working on problems related to the use of graph-based algorithms for natural
language processing and on the theory of graph-based methods.
It will address a broader spectrum of research areas to foster
exchange of ideas and help to identify principles of using the graph
notions that go beyond an ad-hoc usage.
Unveiling these principles will give rise to applying generic graph
methods to many new problems that can be encoded in this framework.

We invite submissions of papers on graph-based methods applied to
NLP-related problems. Topics include, but are not limited to:

- Graph representations for ontology learning and word sense disambiguation
- Graph algorithms for Information Retrieval, text mining and understanding
- Graph matching for Information Extraction
- Random walk graph methods and Spectral graph clustering
- Graph labeling and edge labeling for semantic representations
- Encoding semantic distances in graphs
- Ranking algorithms based on graphs
- Small world graphs in natural language
- Semi-supervised graph-based methods
- Statistical network analysis and methods for NLP

Submission format:

Submissions will consist of regular full papers of max. 8 pages and
short papers of max. 4 pages, formatted following the NAACL 2007
guidelines. Papers should be submitted using the online submission
form: http://www.cs.rochester.edu/meetings/hlt-naacl07/workshops.shtml

Important dates:

Regular paper submission January 29
Short paper submissions February 4
Notification of acceptance February 22
Camera-ready papers March 1
Workshop April 26

AAAI 2007 track on AI and the Web

2006-12-14T06:10:00.001-08:00

AAAI 2007 (July 22-26, Vancouver CN) will have a special
technical track on Artificial Intelligence and the Web. The
track seeks research papers on AI techniques, systems and
concepts involving or applied to the Web. Papers should
describe Web related research or clearly explain how the
work addresses problems, opportunities or issues underlying
the Web or Web-based systems. See [1] for suggested topics
and more track information and [2] for information on the
conference and details on submitting. Relevant deadlines are:

- Jan 25: student abstracts
- Feb 1: technical paper abstracts
- Feb 2: doctoral consortium applications
- Feb 6: technical papers
- Feb 27: nectar and senior member papers
- Apr 3: intelligent systems demo proposals

[1] http://cs.umbc.edu/aaai07/
[2] http://www.aaai.org/Conferences/AAAI/aaai07.php

CoNLL Shared Task 2007: multilingual dependency parsing

2006-12-14T06:06:00.000-08:00

CoNLL Shared Task 2007

Pre-Announcement

Keeping up the successful tradition, the Conference on
Computational Natural Language Learning (CoNLL) 2007 will
as usual include a shared task. For the second year running,
the task will be multilingual dependency parsing. The first
call for participation is scheduled to appear in later in
December with release of training data in late January and
submission of test results in late March. The CoNLL
conference scheduled to take place in June 2007.

The website for the shared task will be
http://nextens.uvt.nl/depparse-wiki/SharedTaskWebsite.

Enquiries about the shared task can be sent to
conll07st@uvt.nl.

The organizers

Joakim Nivre
Johan Hall
Sandra KŸbler
Ryan McDonald
Jens Nilsson
Sebastian Riedel
Deniz Yuret

The congressional speech corpus

2006-12-14T06:03:00.000-08:00

The "congressional speech" corpus and associated graph information
used in our "Get out the vote: Determining support or opposition from
Congressional floor-debate transcripts" EMNLP 2006 paper is now
available.

Specifically, the data includes speeches as individual documents,
together with:

* automatically-derived labels for whether the speakers supported
the legislation under discussion or not, allowing for
experiments with this kind of sentiment analysis

* indications of which debate each speech comes from (and the
position within the debate), allowing for consideration of
conversational structure

* indications of by-name references between speakers, allowing for
experiments with agreement classification (if one determines the
"true" labels from the support/oppose labels assigned to the
pair of speakers in question)

* the edge weights and other information we derived to create the
graphs we used for our experiments upon this data, facilitating
implementation of alternative graph-based classification methods
upon the graphs we constructed

The download site is:
http://www.cs.cornell.edu/home/llee/data/convote.html

Matt Thomas, Bo Pang, and Lillian Lee