Conference Proceeding Article
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.
Selective sampling, Active learning
Databases and Information Systems | Software Engineering
Data Management and Analytics
Uncertainty In Artificial Intelligence: Proceedings of the Thirty-Second Conference: New Jersey, 2016 July 25-19
City or Country
YANG, Peng; ZHAO, Peilin; HAI, Zhen; LIU, Wei; HOI, Steven C. H.; and LI, Xiao-Li.
Efficient multi-class selective sampling on graphs. (2016). Uncertainty In Artificial Intelligence: Proceedings of the Thirty-Second Conference: New Jersey, 2016 July 25-19. 805-814. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3441
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.