Knowledge discovery of semantic relationships between words using nonparametric bayesian graph model

ABSTRACT

We developed a model based on nonparametric Bayesian modeling for automatic discovery of semantic relationships between words taken from a corpus. It is aimed at discovering semantic knowledge about words in particular domains, which has become increasingly important with the growing use of text mining, information retrieval, and speech recognition. The subject-predicate structure is taken as a syntactic structure with the noun as the subject and the verb as the predicate. This structure is regarded as a graph structure. The generation of this graph can be modeled using the hierarchical Dirichlet process and the Pitman-Yor process. The probabilistic generative model we developed for this graph structure consists of subject-predicate structures extracted from a corpus. Evaluation of this model by measuring the performance of graph clustering based on WordNet similarities demonstrated that it outperforms other baseline models.

REFERENCES

• 1: D. Aldous. Exchangeability and related topics. Lecture Notes in Math, 1117, 1985.
• 2: Antoniak. Mixtures of dirichlet processes with applications to bayesian nonparametric problems. The Annals of Statistics, 2(6), 1974.
• 3: C. Biemann. A random text model for the generation of statistical language invariants. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, 2007.
• 4: Beate Dorow , Dominic Widdows, Discovering corpus-specific word senses, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary [doi>10.3115/1067737.1067753]
• 5: B. Dorow, D. Widdows, K. Ling, J.-P. Eckmann, D. Sergi, and E. Moses. Using curvature and markov clustering in graphs for lexical acquisition and word sense discrimination. In MEANING, 2005.
• 6: Escobar and West. Bayesian density estimation and inference using mixtures. Journal of the American Statistical Association, 90, 1995.
• 7: Ferguson. A bayesian analysis of some nonparametric problems. The Annals of Statistics, 1(2), 1973.
• 8: D. Gfeller, J.-C. Chappelier, and P. D. L. Rios. Synonym dictionary improvement through markov clustering and clustering stability. In In Proceedings of Applied Stochastic Models and Data Analysis, 2005.
• 9: Masato Hagiwara , Yasuhiro Ogawa , Katsuhiko Toyama, Selection of effective contextual information for automatic synonym acquisition, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.353-360, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220220]
• 10: C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda. Learning systems of concepts with an infinite relational model. In In Proceedings of the 21st National Conference on Artificial Intelligence, 2006.
• 11: Dekang Lin, Automatic retrieval and clustering of similar words, Proceedings of the 17th international conference on Computational linguistics, p.768-774, August 10-14, 1998, Montreal, Quebec, Canada
• 12: S. McDonald and M. Ramscar. Testing the distributional hypothesis: The influence of context on judgements of semantic similarity. In In Proceedings of the 23rd Annual Conference of the Cognitive Science Society, 2001.
• 13: M. E. J. Newman and E. A. Leicht. Mixture models and exploratory analysis in networks. In In Proceedings of National Academy of Sciences of the United States of America, 2007.
• 14: J. Pitman and M. Yor. The two-parameter poisson-dirichlet distribution derived from a stable subordinator. Annals of Probability, 25, 1997.
• 15: Sethuraman. A constructive definition of dirichlet priors. Statistica Sinica, 4, 1994.
• 16: Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(476):1566--1581, 2006.
• 17: S. van Dongen. Graph clustering by flow simulation. PhD thesis, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

General Terms:
Algorithms

Keywords:
graph clustering, nonparametric bayes, probabilistic generative model, text mining