Auto-correlation Dependent Bounds for Relational Data
Amit Dhurandhar · 2013
A large portion of the data that is collected in various application domains such as online social networking, nance, biomedicine, etc. is relational in nature. A subeld of Machine Learning namely; Statistical Relational Learning (SRL) is concerned with performing statistical inference on relational data. A dening property of relational data that separates it from independently and identically distributed data (i.i.d.) is the existence of correlations between individual datapoints. A major portion of the theory developed in machine learning assumes the data is i.i.d. In this paper we develop theory for the relational setting. In particular, we derive distribution free bounds for the relational setting where the class of data generation models we consider are inspired from the type joint distributions that are represented by relational classication models developed by the SRL community. A key aspect of the bound we derive is that the tightness of the bound is a function of the strength of dependence between related datapoints, with the bound reducing to the standard Hoeding’s or McDiarmid’s