Non-Asymptotic Analysis of Relational Learning with One Network
Peng Ju He, Changshui Zhang · 2014
This theoretical paper is concerned with a rigorous non-asymptotic analysis of relation-al learning applied to a single network. Under suitable and intuitive conditions on features and clique dependencies over the network, we present the first probably approximately cor-rect (PAC) bound for maximum likelihood estimation (MLE). To our best knowledge, this is the first sample complexity result of this problem. We propose a novel combina-tional approach to analyze complex depen-dencies of relational data, which is crucial to our non-asymptotic analysis. The con-sistency of MLE under our conditions is al-so proved as the consequence of our sample complexity bound. Finally, our combination-al method for analyzing dependent data can be easily generalized to treat other general-ized maximum likelihood estimators for rela-tional learning. 1