Awards

AT&T Fellow, 2001

Association for Computational Linguistics Vice President-elect 2010

Publications

See here for a list of publications. Many of my papers can be found in the ACL Anthology. See here for a ranking of authors in the Anthology by h-index.

According to Google Scholar, my top 3 cited papers are:

1. Word association norms, mutual information, and lexicography 1990 (with Patrick Hanks)

2. A stochastic parts program and noun phrase parser for unrestricted text 1988

3. A program for aligning sentences in bilingual corpora 1993 (with Bill Gale)

Some recent papers with citations (according to Google Scholar)

1. Nonlinear Estimators and Tail Bounds for Dimension Reduction in l 1 Using Cauchy Random Projections 2007 (with Ping Li and Trevor J. Hastie)
2. Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data 2007 (with Ping Li and Trevor J. Hastie)
3. A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations 2007 (with Ping Li and Trevor J. Hastie)
4. Entropy of search logs: how hard is search? with personalization? with backoff? 2008 (with Qiaozhu Mei)
5. K-Best Suffix Arrays 2007 (with Bo Thiesson and Robert Ragno)

Education

Received Ph.D., MS, and SB degrees in 1983, 1980, and 1978, all from MIT in Computer Science.

Undergraduate thesis, supervised by Richard Greenblatt, on chess programming. Thanks to considerable help and encouragement from Hans Berliner, it was published in IJCAI-79 as Co-ordinate Squares: A Solution to Many Chess Pawn Endgames.

Masters thesis, supervised by Peter Szolovits, argued that a finite state machine (FSM) was sufficient, and that one did not need much more complex mechanisms (ATNs or Turing Machines) that were in vogue at the time. The thesis was originally intended to help Szolovits’ Expert System MEDG (Medical Decision Making Group) generate better explanations. Became convinced that the MEDG explanations were difficult to understand because they were full of center-embedding, a kind of recursion that requires unbounded memory to process. This argument was based on Chomsky’s 1959 proof that center-embedded characterizes the difference between push down automata and finite state machines (FSMs). The thesis ultimately evolved into a demonstration that language could be processed on a FSM by implementing a parser based on Mitch Marcus’ thesis and Kaplan-Bresnan’s Lexical-Functional Grammar, and showing that the stack did not need more than about three cells as long as one used certain compiler optimizations such as tail recursion to conserve memory.

Doctoral thesis, supervised by Jon Allen, argued that well-known parsing methods could be used help take advantage of allophonic variation in speech. The phoneme /t/, for example, is typically realized with a heavily aspirated burst at the beginning of a syllable as in Tom, but not at the end of a syllable as in atlas. At the time, these sorts of variations were seen as a kind of noise that a speech recognition machine would have to overcome. I preferred to view the speech system as consisting of two types of clues, those that varied systematically with the suprasegmental (syllable structure and stress) context such as aspiration and those that tended to be relatively invariant to contextual influences such as place, manner and voicing. Both types of clues are useful. Variant clues can be used in a parser to discover the underlying context, and therefore should not be considered noise. An abbreviated version of the thesis was published in Cognition in 1987; the complete thesis was published by Kluwer the following year.

Work Experience

1983-1990

Joined AT&T Bell Laboratories research in 1983 to work with Mitch Marcus and Mark Liberman in Osamu Fujimura’s Linguistic Research and Artificial Intelligence department. Worked on a number of problems in speech and language, especially part of speech tagging, pronunciation of surnames for speech synthesis and text analysis. Published a statistical trigram part of speech tagger in 1988. The approach has since become standard, but at the time it was believed that much more complex mechanisms such as ATNs or Turing Machines were required. (There was also a strong bias at the time against empirical/statistical approaches to language.)

My interest in text analysis grew out of a collaboration with the lexicographer Patrick Hanks. I ran into a number of lexicographers while working on letter-to-sound rules for speech synthesis. At the time, letter-to-sound rules were being used to guess when the letter “t” should be pronounced with the phoneme /t/ and when it shouldn’t. Word accuracy rates were unacceptably low. After acquiring the rights to a dictionary, word accuracy quickly climbed from about 80% to 99.9% or better. The dictionary-based approach has since become standard, but at the time there was considerable controversy over the “larger” memory requirement (0.25 megabytes). Ever since I have been acquiring data just about as fast as I have been able to acquire disks. These days, we buy disks by the terabyte.

After this successful interaction with lexicography, Patrick Hanks visited Bell Laboratories for a month in early 1989. He showed me how lexicographers were beginning to use large corpora to find collocations, words that are often found together like doctor/nurse, or save…from. We found ways to automate some of the drudgery by using well-understood statistical measures like mutual information. Began working with William Gale, a statistician at Bell Laboratories, on estimating the probability of rare events in large corpora, comparing the Good-Turing method with a held-out estimator. Over the next five years, ending with Gale’s retirement, we published a series of papers together on spelling correction, word-sense disambiguation, aligning parallel corpora, and alternatives to the Poisson for modeling the distribution of words in text.

1990-1991

Visited Ed Hovy at USC/ISI for an academic year, with support from ARPA for work on machine translation and parallel corpora (texts such as the Canadian Parliamentary debates that are published in two languages). Spent the time reading in many areas, especially in machine translation (MT) and information retrieval (IR). Started attending meetings in both areas. Became very active in corpus lexicography, publishing a number of papers with Hanks, Gale, Yarowsky and others. Also used the time to help members of the community get started in corpus-based research by serving on data collection committees such as the ACL/DCI (Association for Computational Data Collection Initiative), writing review articles (for Computational Linguistics, Machine Translation, and CACM) and tutorials (Coling-90, 1992 European Summer School, ACL-95). Taught a graduate seminar course at USC with Ed Hovy in the spring term. Started reviewing large numbers of papers for conferences, journals and funding agencies, perhaps as many as a hundred papers in some years.

1991-1994

Returned to Bell Laboratories in fall 1991 and switched into a software engineering organization, headed by Peter Weinberger. Continued my interest in large corpora, by showing how a large multi-million line program could be thought of as a large corpora, and how corpus-based techniques could be used in the discovery process, the process of reading a large program for the first time. Wrote a program with Jon Helfman called dotplot that helps find self-similarity (copied regions) in text (large corpora, source code, object code) using methods borrowed from biology for matching long sequences of DNA.

Developed the Termworks platform with AT&T Language Line, a commercial translation service. The platform was designed to help translators with technical terminology and translation reuse. Translators don’t need help with easy vocabulary and easy grammar (the focus of most machine translation research) but they do need help with technical terms like dialog box. The solutions to these terminology puzzles can be surprising, even to a native speaker of the language. Microsoft uses finestra(window) in their Italian manuals, but boite(box) in their French manuals. The tools help translators conform to house standards by extracting examples of the term and its translations from a previous release of the manual that has already been published in both languages. A statistical alignment program is used to figure out which parts of the source text correspond to which parts of the translation. The tool and its implications for machine translation research were presented at an invited talk at EACL-93. Pierre Isabelle and I edited a special issue of the journal Machine Translation (1997 12:1/2) on tool-based alternatives to machine translation.

Worked on a digital library project based on a collection of 500,000 pages of AT&T memos supplied by the Murray Hill Library in 400 dots-per-inch bitmap format (20 gigabytes). Demonstrated how off-the-shelf optical character recognition (OCR) and information retrieval (IR) programs could be used to implement a “fax-a-query” information retrieval service where both the input and output could be faxes or bitmaps or any format that could be converted to a fax or bitmap. Argued at Coling-94 that fax had advantages over proposed ascii-based standards such as SGML (availability, ease-of-use, longevity). Began work on bitmap-level matching, avoiding the need for OCR. Found that bitmap-level matching could also be used to improve up-sampling and down-sampling of documents, which is important if the scanner, the fax transmission line and the printer use different sampling rates.

1995-1996

Taught a seminar course on corpus-based methods at Penn with Mitch Marcus. Served on thesis committees for Pascale Fung and Vasileios Hatzivassiloglou, both at Columbia . In Pascale’s case, I was in a certain sense her de facto advisor. Her interest in aligning parallel and non-parallel corpora, which ultimately became her thesis, started with a summer job in my lab at AT&T. Switched into a new organization headed by Eric Sumner, focusing on network services (issues more closely aligned with the core telephone business than speech and language). Worked on some systems problems such as how to replace a billing factory with a few PCs. There is a tendency to believe that if you have a serious “big data” problem (e.g., billing, datamining), then you need a serious (=expensive) computer center full of mainframes, tape robots and bureaucracy. Attempted to show that a gang of PCs could replace a mainframe, but discovered, at least in one application (Billing Edge) that a single PC could replace a gang of mainframes.

1996-

Promoted to head a new department in research. AT&T has vast quantities of data, some is textual, but most is not. The department uses visualization and datamining, methods that have become popular in corpus-based natural language processing, to find patterns of interest. Imagine that we have a large steady stream of usage records indicating which customers are buying which services and when. This kind of data feed is usually developed for billing purposes, but many companies are discovering a broad range of other applications such as fraud detection, inventory control, provisioning scarce resources, forecasting demand, etc. The problems are challenging from a research point of view because of the massive scale. The telephone network, for example, has about 100 million customers (nodes), who purchase about 100 million calls (edges) per day. This data stream is much larger than the very large corpora that I had just a few years ago. We used to think that a billion words of text was a lot of data, but we are currently receiving a couple billion records a week.

1998-1999

Developed with Glenn Fowler and Don Caldwell a program called pzip that is like gzip, but uses an automatic training procedure to induce an optimal schema for compressing tabular data such as database records and spread sheets. Sometimes it is better to compress a table in row major order and sometimes it is better to compress a table in column major order. Pzipuses a schema to numerate the values in the table and then passes the results to gzip. Another program, pin (partition inducer), uses dynamic programming to find the optimal partition (or schema) by applying gzip to all possible partitions of a sample of the table. Pzip typically saves a factor of two in both space and time over gzip, which has been very much appreciated by several large data warehousing applications. A paper was published in SODA-2000 pdf. Won a “Circle of Excellence” award in 1998 from the AT&T CIO (Chief Information Office) for this work.

Established excellent relationships with AT&T marketing, especially the folks behind the new Lucky Dog flanker brand. My team maintains a web site that tracks sales in “real time” (faster than previously possible). This web site is changing the culture in marketing. Now that they know they can get quick feedback, they are much more willing to experiment. Try a little bit of this and a little bit of that, and do more of what works and less of what doesn’t. The web site has moved SWIFT from a research prototype into a highly visible business reality. SWIFT was a very nice demo that visualized traffic on the AT&T network on a map projected on a powerwall, a huge wall-sized terminal. The point of the demo is that we ought to be able to react to a change in the marketplace in less than a day. To make the idea a business reality, we simplified the interface so that marketing managers could drive it, and replaced the fancy powerwall hardware with a standard web browser. In addition, we worked closely with marketing managers to understand what matters to them, a task that reminded me of my days in Peter Szolovits’ expert systems group at MIT.

1999-2003

Built upon our success with Lucky Dog to establish relationships with other marketing groups, especially the launch of AT&T local service in New York and Texas. Used datamining techniques to discover considerable room for improvement in operations. Won “salesman of the month” in August 2000 for finding large numbers of sales that could be “reflowed.” This discovery played a major role in the team meeting its sales commitments.

Led a team on virtual integration that used methods such as web crawling and screen scraping to produce a view that made a bunch of disparate databases appear to be more unified than they were.

Despite my new interests in datamining, visualization, management and business, I remain active in computational linguistics, my first love. With so many responsibilities, it has been more difficult to publish, but nevertheless, together with Yamamoto, we showed how to compute term frequencies and document frequencies, two statistics used in Information Retrieval, for all substrings in a large corpus. It is well known how to compute these statistics for short substrings, e.g., unigrams, bigrams and trigrams, but we showed how to compute many of these kinds of statistics for all substrings including very long ones, e.g., million-grams. One might have thought that this would be impractical since there are n² substrings, but it turns out that the n² substrings can be grouped into n classes using a data structure called suffix arrays, and many of the statistics of interest can be computed over the n classes rather than the n² substrings. Since we were able to compute these statistics over a larger set of words and phrases than previously possible, we found an interesting new heuristic for distinguishing good keywords from general vocabulary, which seems promising for both Japanese and English. Both mutual information and a new measure called residual IDF (inverse document frequency) compare an observation to chance, but they use different notions of chance. Mutual information looks for deviations from compositionality. It grew out of work with lexicographers (Hanks) and so it isn’t surprising that it is better for finding general vocabulary, the kind of words and phrases that one would expect to find in a dictionary. On the other hand, residual IDF looks for words and phrases that are not randomly distributed across documents. It grew out of the information retrieval literature and so it isn’t surprising that it is better for finding keywords, the words and phrases that distinguish one document from another.

2003- 2009

Joined David Heckerman’s Machine Learning Group in Microsoft Research and later joined Eric Brill’s Text Mining, Search and Navigation research group (TMSN), currently headed by Chris Burges. Web logs are similar to logs of telephone calls (call detail records). Usage logs are quite a bit larger than the documents themselves. As big as the web is, there are more readers than writers, and therefore usage logs (such as click logs) tend to be even larger than the documents (web crawls). We used to think that the AP news was a large corpus, but that is just a million words a week. Telephone companies and web search engines see much larger traffic volumes (e.g., a few hundred million records per day).

Big data problems become more manageable if we can make them smaller. We used a method borrowed from the Unix Spell program for the context sensitive speller in Office-2007. For example, if you use here instead of hear in a context such as, “you should here what he said,” then Office-2007 will underline the typo with blue squiggles. The method uses a standard trigram language model, but heroic compression method were required to compress the language model down to just a few megabytes. Doug McIlroy faces a similar problem when he wrote the Unix Speller. He used Golomb coding to squeeze a 32,000 word dictionary into the address space of a PDP-11 (64k bytes). That was just 2 bytes per word. We used similar method to compress the trigram language model to just a few bytes per trigram.

Ping Li and I have written quite a few papers on dimension reduction. Methods such as random projections and sketches make it possible to find strong associations from small samples. Ping Li won a best student paper at KDD-2006 for his work on random projections. Sketches are probably even better. We should not have to look at the entire corpus (e.g., the Web) to know if two (or more) words are associated or not. Sketches were originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associations, using a maximum likelihood estimator to find the most likely contingency table given a sample and the margins (also known as document frequencies in information retrieval).

Many techniques that work well on text corpora also work well on web logs. With Qiaozhu Mei in WSDM-2009, we argued that entropy is a useful tool for estimating how hard is search, as well as the potential for personalization. We estimated the entropy of queries, urls and IP addresses, taken one at time, two at a time, and three at a time. We found that it takes 20-something bits to guess the next query, the next url or the next user. But search is easier. If we give you the query, then it takes about 3 bits to guess the url that the user will click on. Personalized search is even easier. If the search engine was given both the query and the IP address, then the entropy is cut in half. There is a huge opportunity for personalization to improve the search experience. It is much easier to answer the question if we know something about the audience. We borrowed a number of techniques from language modeling in speech and language such as Katz backoff. With lots of backoff, personalization starts to look like market segments in database marketing.

Bo Thiesson and I developed “The Wild Thing!” Users are encouraged to enter queries with wild cards. For example “C Rice” or “2#7423” is treated as a regular expression. The system returns the k-best (most popular) matches which includes: “Condoleezza Rice.” The method is particularly attractive for queries that are hard to spell, or for scenarios where it is hard to type (like mobile phones). On a phone, “2#7423” maps to “C Rice” since “C” is on the 2 key, and “R” is on the 7 key and so on. To make the matching more efficient, we introduced K-best suffix arrays, a variant on suffix arrays designed to find the K-best matches, as opposed to all matches. Best can be defined by any total order on the strings such as popularity (frequency in the logs).

With Albert Greenberg and James Hamilton, we published a paper in Hotnets-2008 comparing the mega-model and the micro-model for data centers. If we want to put a million servers in the cloud, should we deploy them in a single mega-data center, or distribute them across a large number of micro-data centers? Given how much the industry is currently investing in the mega model, the industry would do well to consider the micro alternative, especially for embarrassingly distributed applications such as web serving and email.

2009-

Chief Scientist of the Human Language Technology Center of Excellence at The Johns Hopkins University.

Community Service:

Served on editorial board of Computational Linguistics (CL), Machine Translation (MT), Quantitative Linguistics (QL), International Journal of Corpus Linguistics (IJCL). Served on program committees for numerous conferences including SIGIR and ACL, both more than once. Helped to create SIGDAT, a special interest group focusing on corpus data, and organized, chaired, or co-chaired many of its annual workshops on very large corpora, which have evolved into the EMNLP conferences with 200+ participants per meeting, about equally distributed over Europe, Asia and America . Co-chaired ACL-99, the major meeting in computational linguistics in 1999. Co-chaired the Industrial Track of KDD-2000, the major meeting in datamining in 2000.