Study on relational classification learning bound

Currently, there is some lack of knowledge about learning bound in relational classification model. In this study, some learning bounds for relational classification are proposed. First, two bounds are deduced for finite and infinite hypothesis space of the relational classification model respectively. Further, a complexity metric called relational dimension is proposed to measure the linking ability of the relational classification model. The relation between the complexity and growth function is proofed, and the learning bound for finite VC dimension and relational dimension is obtained. Afterwards, the condition of learnable, non-trivial, and the feasibility of the bound is analyzed. Finally, the learning progress of relational classification model based on Markov logic network is analyzed with some examples. The experimental result on a real dataset has demonstrated that the proposed bounds are useful in some practical problems.