Statistical predicate invention

ABSTRACT

We propose statistical predicate invention as a key problem for statistical relational learning. SPI is the problem of discovering new concepts, properties and relations in structured data, and generalizes hidden variable discovery in statistical models and predicate invention in ILP. We propose an initial model for SPI based on second-order Markov logic, in which predicates as well as arguments can be variables, and the domain of discourse is not fully known in advance. Our approach iteratively refines clusters of symbols based on the clusters of symbols they appear in atoms with (e.g., it clusters relations by the clusters of the objects they relate). Since different clusterings are better for predicting different subsets of the atoms, we allow multiple cross-cutting clusterings. We show that this approach outperforms Markov logic structure learning and the recently introduced infinite relational model on a number of relational datasets.

REFERENCES

• 1: Mark Craven , Seán Slattery, Relational learning with statistical predicate invention: better models for hypertext, Machine Learning, v.43 n.1/2, p.97-119, April/May 2001 [doi>10.1023/A:1007676901476 ]
• 2: Davis, J., Ong, I., Struyf, J., Burnside, E., Page, D., & Costa, V. S. (2007). Change of representation for statistical relational learning. Proc. IJCAI'07.
• 3: Denham, W. (1973). The detection of patterns in Alyawarra nonverbal behavior. Doctoral dissertation, Department of Anthropology, University of Washington, Seattle, WA.
• 4: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 5: Gal Elidan , Nir Friedman, Learning Hidden Variable Networks: The Information Bottleneck Approach, The Journal of Machine Learning Research, 6, p.81-127, 12/1/2005
• 6: Elidan, G., Lotner, N., Friedman, N., & Koller, D. (2001). Discovering hidden variables: A structure-based approach. NIPS'01.
• 7: Getoor, L., & Taskar, B. (Eds.). (2007). Introduction to statistical relational learning. MIT Press.
• 8: Kemp, C., Tenenbaum, J. B., Griffiths, T. L., Yamada, T., & Ueda, N. (2006). Learning systems of concepts with an infinite relational model. Proc. AAAI'06.
• 9: Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102407]
• 10: Kok, S., Sumner, M., Richardson, M., Singla, P., Poon, H., & Domingos, P. (2006). The Alchemy system for statistical relational AI (Technical Report). Department of Computer Science and Engineering, University of Washington, Seattle, WA. http://alchemy.cs.washington.edu.
• 11: Kramer, S. (1995). Predicate invention: A comprehensive view (Technical Report). Austrian Research Institute for Artificial Intelligence, Vienna, Austria.
• 12: Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wú , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143918]
• 13: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 14: McCray, A. T. (2003). An upper level ontology for the biomedical domain. Comparative and Functional Genomics, 4.
• 15: Muggleton, S., & Buntine, W. (1988). Machine invention of first-order predicates by inverting resolution. Proc. ICML'88.
• 16: Jennifer Neville , David Jensen, Leveraging Relational Autocorrelation with Latent Group Models, Proceedings of the Fifth IEEE International Conference on Data Mining, p.322-329, November 27-30, 2005 [doi>10.1109/ICDM.2005.89]
• 17: Osherson, D. N., Stern, J., Wilkie, O., Stob., M., & Smith, E. E. (1991). Default probability. Cognitive Science, 15.
• 18: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: Pitman, J. (2002). Combinatorial stochastic processes (Technical Report 621). Department of Statistics, University of California at Berkeley, Berkeley, CA.
• 20: Poon, H., & Domingos, P. (2006). Sound and efficient inference with probabilistic and deterministic dependencies. Proc. AAAI'06.
• 21: Alexandrin Popescul , Lyle H. Ungar, Cluster-based concept invention for statistical relational learning, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014137]
• 22: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 23: Roy, D., Kemp, C., Mansinghka, V. K., & Tenenbaum, J. B. (2006). Learning annotated hierarchies from relational data. NIPS'06.
• 24: Rummel, R. J. (1999). Dimensionality of nations project: attributes of nations and behavior of nation dyads, 1950--1965. ICPSR data file.
• 25: Silverstein, G., & Pazzani, M. J. (1991). Relational clichéés: Constraining constructive induction during relational learning. Proc. ICML'91.
• 26: Srinivasan, A., Muggleton, S. H., & Bain, M. (1992). Distinguishing exceptions from noise in non-monotonic learning. Proc. ILP'92.
• 27: Wogulis, J., & Langley, P. (1989). Improving efficiency by learning intermediate concepts. Proc. IJCAI'89.
• 28: Wolfe, A. P., & Jensen, D. (2004). Playing multiple roles: discovering overlapping roles in social networks. Proc. of the ICML-2004 Workshop on Statistical Relational Learning and its Connections to Other Fields.
• 29: Xu, Z., Tresp, V., Yu, K., & Kriegel, H.-P. (2006). Infinite hidden relational models. Proc. UAI'06.
• 30: Zhao Xu , Volker Tresp , Kai Yu , Shipeng Yu , Hans-Peter Kriegel, Dirichlet enhanced relational learning, Proceedings of the 22nd international conference on Machine learning, p.1004-1011, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102478]