Autocorrelation and Linkage Cause Bias in Evaluation of Relational Learners
Lecture notes in computer sciencePublished 1 January 2003
David Jensen, Jennifer Neville
Citations21
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown how linkage and autocorrelation affect estimates of model accuracy by applying FOIL to synthetic data and to data drawn from the Internet Movie Database and how a modified sampling procedure can eliminate the bias.
Abstract
Two common characteristics of relational data sets — concentrated linkage and relational auto-correlation — can cause traditional methods of evaluation to greatly overestimate the accuracy of induced models on test sets. We identify these characteristics, define quantitative measures of their severity, and explain how they produce this bias. We show how linkage and autocorrelation affect estimates of model accuracy by applying FOIL to synthetic data and to data drawn from the Internet Movie Database. We show how a modified sampling procedure can eliminate the bias.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
Journal of the Royal Statistical Society Series A (Statistics in Society)Statistics for Spatial Data.
5,160 Citations1993Mike Rees, Noel Cressie
Elsevier eBooksIrrelevant Features and the Subset Selection Problem
2,374 Citations1994George H. John, Ron Kohavi +1 more
A method for feature subset selection using cross-validation that is applicable to any induction algorithm is described, and experiments conducted with ID3 and C4.5 on artificial and real datasets are discussed.
Machine LearningLearning Logical Definitions from Relations
1,425 Citations1990J. R. Quinlan
FOIL is a system that learns Horn clauses from data expressed as relations, but extends them to a first-order formalism, which has been applied successfully to several tasks taken from the machine learning literature.
Learning Probabilistic Relational Models
941 Citations2001Lise Getoor, Nir Friedman +2 more
Learning to extract symbolic knowledge from the World Wide Web
675 Citations1998Mark Craven, Dan DiPasquo +5 more
The goal of the research described here is to automatically create a computer understandable world wide knowledge base whose content mirrors that of the World Wide Web, and several machine learning algorithms for this task are described.
Concept learning and the problem of small disjuncts
342 Citations1989Robert C. Holte, Liane Acker +1 more
Various approaches to this problem are evaluated, including the novel approach of using a bias different than the "maximum generality" bias, which prove partly successful, but the problem of small disjuncts remains open.
Iterative Classification in Relational Data
306 Citations2000Jennifer Neville, David Jensen
An iterative classification approach that uses simple Bayesian classifiers in an iterative fashion, dynamically upd ating the attributes of some objects as inferences are made about related ob jects.
Machine LearningMultiple Comparisons in Induction Algorithms
243 Citations2000David Jensen, Paul R. Cohen
This work analyzes the statistical properties of MCPs and shows how failure to adjust for these properties leads to the pathologies of induction algorithms, including attribute selection errors, overfitting, and oversearching.
Lecture notes in computer scienceCommunities of Interest
191 Citations2001Corinna Cortes, Daryl Pregibon +1 more
Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning
168 Citations2002David Jensen, Jennifer Neville
It is shown how linkage and autocorrelation affect a representative algorithm for feature selection by applying the algorithm to synthetic data and to data drawn from the Internet Movie Database.
Learning Stochastic Logic Programs
104 Citations2000Stephen Muggleton
This paper discusses how a standard Inductive Logic Programming (ILP) system, Progol, has been modified to support learning of SLPs and shows that maximising the Bayesian posterior function involves finding SLPs with short derivations of the examples.
Theoretical Computer ScienceEfficient sampling strategies for relational database operations
96 Citations1993Richard J. Lipton, Jeffrey F. Naughton +2 more
The proposed adaptive, random-sampling algorithm for general query size estimation in databases is investigated as applied to the relational database operations select, project, and join to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy.
Lecture notes in computer science1BC: A First-Order Bayesian Classifier
84 Citations1999Peter Flach, Nicolas Lachiche
1BC is presented, a first-order Bayesian Classifier to view individuals as structured terms, and to distinguish between structural predicates referring to subterms, and properties applying to one or several of these subterms.
Discovering Test Set Regularities in Relational Domains
83 Citations2000Seán Slattery, Tom M. Mitchell
This paper presents an approach to discovering additional regularities in the test set, and shows that in relational domains such test set regularities can be used to improve classification accuracy beyond that achieved using the training set alone.