VC-Dimension Based Generalization Bounds for Relational Learning
In many applications of relational learning, the available data can be seen as a sample from a larger relational structure (e.g. we may be given a small fragment from some social network). In this paper we are particularly concerned with scenarios in which we can assume that (i) the domain elements appearing in the given sample have been uniformly sampled without replacement from the (unknown) full domain and (ii) the sample is complete for these domain elements (i.e. it is the full substructure induced by these elements). Within this setting, we study bounds on the error of sufficient statistics of relational models that are estimated on the available data. As our main result, we prove a bound based on a variant of the Vapnik-Chervonenkis dimension which is suitable for relational data.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsRelational ReasoningSimilar Papers 제목 키워드 기반
Understanding Domain-Size Generalization in Markov Logic Networks
We study the generalization behavior of Markov Logic Networks (MLNs) across relational structures of different sizes. Multiple works have noticed that MLNs learned on a given domain generalize poorly across domains of di…
Data-dependent Generalization Bounds via Variable-Size Compressibility
In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework that we introduce newly here. In this framework, the generalizatio…
Generalization BoundsDimensionality-Dependent Generalization Bounds for $k$-Dimensional Coding Schemes
The $k$-dimensional coding schemes refer to a collection of methods that attempt to represent data using a set of representative $k$-dimensional vectors, and include non-negative matrix factorization, dictionary learning…
ClusteringDictionary LearningGeneralization BoundsQuantizationRelational Marginal Problems: Theory and Estimation
In the propositional setting, the marginal problem is to find a (maximum-entropy) distribution that has some given marginals. We study this problem in a relational setting and make the following contributions. First, we …
Reducing the Rank in Relational Factorization Models by Including Observable Patterns
Tensor factorizations have become popular methods for learning from multi-relational data. In this context, the rank of a factorization is an important parameter that determines runtime as well as generalization ability.…