Combining link and content for collective active learning

Published 26 October 2010

Lixin Shi, Yuhang Zhao, Jie Tang

Citations9

TL;DR

This paper defines an objective function based on three criteria and presents an efficient algorithm to optimize the objective function with a bounded approximation rate and results on a real-world data sets demonstrate the effectiveness of the proposed approach.

Abstract

In this paper, we study a novel problem Collective Active Learning, in which we aim to select a batch set of "informative" instances from a networking data set to query the user in order to improve the accuracy of the learned classification model. We perform a theoretical investigation of the problem and present three criteria (i.e., minimum redundancy, maximum uncertainty and maximum impact) to quantify the informativeness of a set of selected instances. We define an objective function based on the three criteria and present an efficient algorithm to optimize the objective function with a bounded approximation rate. Experimental results on a real-world data sets demonstrate the effectiveness of our proposed approach.

Keywords

Computer Science

ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

12,978 Citations2001John Lafferty, Andrew McCallum +1 more

This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.

View PDF

Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I

4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more

It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.

AI MagazineCollective Classification in Network Data

3,287 Citations2008Prithviraj Sen, Galileo Namata +4 more

This article introduces four of the most widely used inference algorithms for classifying networked data and empirically compare them on both synthetic and real-world data.

View PDF

Semi-supervised learning with graphs

649 Citations2005Xiaojin Zhu, John Lafferty +1 more

A series of novel semi-supervised learning approaches arising from a graph representation, where labeled and unlabeled instances are represented as vertices, and edges encode the similarity between instances are presented.

Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

471 Citations2003Xiaojin Zhu, John Lafferty +1 more

The active learning scheme requires a much smaller number of queries to achieve high accuracy compared with random query selection, and the semi-supervised learning scheme requires a much smaller number of queries to achieve high accuracy compared with random query selection.

Journal of Machine Learning ResearchClassification in Networked Data: A Toolkit and a Univariate Case Study

447 Citations2007Sofus A. Macskassy, Foster Provost

The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked data.

Why collective inference improves relational classification

256 Citations2004David Jensen, Jennifer Neville +1 more

This work describes the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data, and characterizes different types of statistical models used for making inference in relational data.

Using graph-based metrics with empirical risk minimization to speed up active learning on networked data

49 Citations2009Sofus A. Macskassy

A novel hybrid approach of using of community finding and social network analytic centrality measures to identify good candidates for labeling and then using ERM to find the best instance in this candidate set is described.

Cluster Analysis and Optimization in Color-Based Clustering for Image Abstract

37 Citations2007Jing He, Guangyan Huang +2 more

Examples show generally the greater the abstract degree is, the less is the fidelity and GOC- DBSCAN outperforms HSV-DBSCAN when they are evaluated by the two optimization criteria.

A large-scale active learning system for topical categorization on the web

13 Citations2010Suju Rajan, Dragomir Yankov +2 more

This paper describes a successfully deployed end-to-end system that starts from a biased training sample and makes use of several state-of-the-art machine learning algorithms working in tandem, including a powerful active learning component, in order to achieve a good classification system.