Statistical predicate invention is considered a key problem in statistical relational learning. SPI involves discovering new concepts, properties, and relations within structured data, extending beyond mere discovery of hidden variables within statistical models and predicate invention within ILP. An initial model for SPI is proposed, based on second-order Markov logic, wherein predicates as well as arguments can be variables, and the domain of discourse is not fully known in advance. The 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, multiple cross-cutting clusterings are allowed. This approach is shown to outperform Markov logic structure learning and the recently introduced infinite relational model on a number of relational datasets.
