One of my earlier notes from NAACL talked about discovering relations among words or concepts. As I mentioned, this seems to be growing area of interest in NLP based on the number of times it came up at NAACL both during talks, and in casual conversation. In fact, here's a link to that note:
http://groups.yahoo.com/group/nlpatumd/message/415 A closely coupled problem is that of discovering sets of words that are related. It is sometimes the case that you first discover various sets of related words, and then you try and establish IS-A or other relations between those sets. (You can think of these sets as clusters of words.) In this note I'd like to try and highlight some of the interesting work in discovering sets of related words, and make a few general points about the problem. This seems to be an increasingly popular problem to be pursuing, and various of our projects touch upon it - in particular Amruta's SenseClusters package, Prath's google-hack project, and Sid and Jason's WordNet::Similarity package. There are several general approaches to discovering sets of related words from a large corpus of text. Some methods are purely distributional, and just rely on co--occurrence information. Other methods use syntactic filters or clues, and then a third style uses a bootstrapping style approach, where it is given a few seed concepts and other words are added to that seed to form a class. ======================================================================== The purely distributional approach is much like unsupervised learning or clustering, and relies on discovering regularities in raw text without knowing ahead of time what classes or categories are to be discovered. Good examples of such work include: Peter F. Brown; Peter V. deSouza; Robert L. Mercer; T. J. Watson; Vincent J. Della Pietra; Jenifer C. Lai, 1990. Class-Based n-gram Models of Natural Language, Computational Linguistics. http://acl.ldc.upenn.edu/J/J92/J92-4003.pdf Fernando Pereira, Naftali Tishby and Lillian Lee, 1993. DISTRIBUTIONAL CLUSTERING OF ENGLISH WORDS. Proceedings of ACL-1993. http://acl.ldc.upenn.edu/P/P93/P93-1024.pdf ======================================================================== While the following approaches are very much oriented towards clustering and/or distributional methods, rather than only using raw text as input, they start with a parsed or chunked corpus and/or use syntactic features as the foundation of their distributional methods, which makes them somewhat hybrid distributional - syntactic approaches: Hindle, Donald, 1990. NOUN CLASSIFICATION FROM PREDICATE-ARGUMENT STRUCTURES. Proceedings of ACL-1990. http://acl.ldc.upenn.edu/P/P90/P90-1034.pdf. Lin, Dekang, 1998. Automatic Retrieval and Clustering of Similar Words. Proceedings of ACL-1998. http://acl.ldc.upenn.edu/P/P98/P98-2127.pdf Sharon A. Caraballo, 1999. Automatic construction of a hypernym-labeled noun hierarchy from text. Proceedings of ACL-1999. http://acl.ldc.upenn.edu/P/P99/P99-1016.pdf Patrick Pantel and Dekang Lin. 2002. Discovering Word Senses from Text. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD-02). pp. 613-619. Edmonton, Canada. http://www.isi.edu/~pantel/Download/Papers/kdd02.pdf [The Caraballo work is an example of an approach that finds both the sets of related words, and then the relationships between those sets. The sets of words are found using syntactic clues, particularly conjunctions of noun phrases (Dr. Jones is Professor, Department Head, and holder of the Toyota Endowed Chair) as well as appositives (Ted Pedersen, Associate Professor of Computer Science, said today that class was cancelled.). >From these examples you might guess that Professor, Department Head, and Toyota Endowed Chair be put into a set, and that Ted Pedersen and Associate Professor might be grouped together...The use of conjunctions of noun phrases to discover is-a relations was introduced in earlier work by Hearst, which was mentioned in my other note but bears repeating: Marti Hearst, 1992. Automatic acquisition of hyponyms from large text corpora. Proceedings of the 14th International Conference on Computational Linguistics (COLING-92). http://www.sims.berkeley.edu/~hearst/papers/coling92.pdf ======================================================================== Bootstrapping approaches use seed words as exemplars or even the name of a class. The objective of such techniques is often to build a thesaurus or lexicon automatically. So you provide categories like "Animals" and "Machines", and then words that are related to those categories are found. This is different than either of the above style of approach, where one doesn't actually know what sets or clusters are being found. The following approaches use a combination of information sources, including syntactic clues and distributional techniques in order to create these sets of related words. Examples include: Phillips, W. and Riloff, E. (2002) "Exploiting Strong Syntactic Heuristics and Co-Training to Learn Semantic Lexicons", (postscript, pdf), Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002). http://www.cs.utah.edu/~riloff/psfiles/emnlp02-phillips.pdf Brian Roark and Eugene Charniak, 1998. Noun-phrase co-occurrence statistics for semi-automatic semantic lexicon construction. Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (COLING-ACL), 1998, pages 1110-1116 http://arxiv.org/abs/cs.CL/0008026 The following bootstrapping approach relies more strictly on distributional information and doesn't use other sources of information. It still starts with seed words or concepts however, so it's not quite the same as the purely distributional methods such as those of Brown, et. al. or Pereira, et. al. Riloff, E. and Shepherd, J., (1999) "A Corpus-Based Bootstrapping Algorithm for Semi-Automated Semantic Lexicon Construction", Journal of Natural Language Engineering , 1999, Vol. 5, No. 2, pp. 147-156. http://www.cs.utah.edu/~riloff/psfiles/jnle-semlex.pdf ==================================================================== So, above you see examples of three kinds of approaches to finding related words: 1) distributional methods 2) syntactic-distributional methods 3) bootstrapping methods The lines between these approaches might blur a bit, but generally speaking 1 and 2 are purely unsupervised, where 3 is very weakly supervised by providing seed words. All of the above are learning from large samples of text however. 1) is learning from raw text, while 23 is learning from part of speech tagged, chunked, or parsed text. 3) can be from either raw text or syntactically processed text. Now, the WordNet::Similarity package was mentioned above, and that's rather different since you wouldn't actually be learning from text, but rather using the structure of WordNet (perhaps augmented by information content values) to identify sets of related words. Also, sometimes WordNet is used as a point of comparison for evaluation - so you look at a set of related words discovered by a clustering method, and then compare it to WordNet and see if the words in the set are related according to WordNet (which is another way that WordNet::Similarity could come into play). Finally, there is an emerging class of techniques that are illustrated by Prath's thesis work and Google Sets. These attempt to find sets of related words based on the output of a web search engine, and possibly using information that is unique to the web (such as the links between documents). You can find Google Sets at http://labs.google.com/sets and Praths' system is available at http://google-hack.sourceforge.net. Right now we don't have a web based interface to the package, but that is something Prath plans to work on over the summer. Anyway, I guess you can tell I think this is a pretty interesting issue. If you have made it this far, congratulations, and let me know if you have any questions! Ted -- Ted Pedersen http://www.d.umn.edu/~tpederse ------------------------ Yahoo! Groups Sponsor ---------------------~--> Yahoo! Domains - Claim yours for only $14.70 http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/x3XolB/TM ---------------------------------------------------------------------~-> Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/nlpatumd/ <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
