Statistical predicate invention

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We propose statistical predicate invention as a key problem for statistical relational learn- ing. SPI is the problem of discovering new concepts, properties and relations in struc- tured 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 it- eratively refines clusters of symbols based on the clusters of symbols they appear in atoms with (e.g., it clusters relations by the clus- ters of the objects they relate). Since dier- ent clusterings are better for predicting dif- ferent 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. explicitly representing the uncertainty in the discov- ered predicates. These can in turn be used as a ba- sis for discovering new predicates, which is potentially much more powerful than learning based on a fixed set of simple primitives. Essentially all the concepts used by humans can be viewed as invented predicates, with many levels of discovery between them and the sensory percepts they are ultimately based on. In statistical learning, this problem is known as hidden or latent variable discovery, and in relational learning as predicate invention. Both hidden variable discovery and predicate invention are considered quite important in their respective communities, but are also very dif- ficult, with limited progress to date. One might question the need for SPI, arguing that structure learning is sucient. Such a question can