Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2016

Abstract

A graph-based multi-class classification problem is typically converted into a collection of binary classification tasks via the one-vs.-all strategy, and then tackled by applying proper binary classification algorithms. Unlike the one-vs.-all strategy, we suggest a unified framework which operates directly on the multi-class problem without reducing it to a collection of binary tasks. Moreover, this framework makes active learning practically feasible for multi-class problems, while the one-vs.-all strategy cannot. Specifically, we employ a novel randomized query technique to prioritize the informative instances. This query technique based on the hybrid criterion of "margin" and "uncertainty" can achieve a comparable mistake bound with its fully supervised counterpart. To take full advantage of correctly predicted labels discarded in traditional conservative algorithms, we propose an aggressive selective sampling algorithm that can update the model even if no error occurs. Thanks to the aggressive updating strategy, the aggressive algorithm attains a lower mistake bound than its conservative competitors in expectation. Encouraging experimental results on real-world graph databases show that the proposed technique by querying an extremely small ratio of labels is able to accomplish better classification accuracy.

Keywords

Selective sampling, Active learning

Discipline

Databases and Information Systems | Software Engineering

Publication

Uncertainty In Artificial Intelligence: Proceedings of the Thirty-Second Conference: New Jersey, 2016 July 25-19

First Page

805

Last Page

814

ISBN

9780996643115

Publisher

AUAI Press

City or Country

Corvallis, USA

Additional URL

http://auai.org/uai2016/proceedings/uai-2016-proceedings.pdf

Download

Share

COinS