Budgeted algorithm for linearized confidence-weighted learning

Yu Shiou Lin, Chung Hao Wu, Henry Horng Shing Lu*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

This paper presents a novel algorithm for performing linearized confidence-weighted (LCW) learning on a fixed budget. LCW learning has been applied to solve online classification problems in recent years. To make better classification performance, it is common to combine with kernel functions through the kernel trick. However, the trick makes the LCW learning vulnerable to the curse of kernelization that causes unlimited growth in memory usage and run-time. To address this issue, we first re-interpret the LCW learning by using a resource perspective deeming every instance as a potential resource to exploit. Based on the perspective, we then propose a budgeted algorithm that approximates the LCW learning under a finite constraint on the number of available resources. The proposed algorithm enjoys finite complexities of time and space and thus is able to break the curse. Experiments on several open datasets show that the proposed algorithm approximates the LCW learning well and is competitive to state-of-the-art budgeted algorithms.

Original languageEnglish
Title of host publicationICCBDC 2019 - Proceedings of 2019 3rd International Conference on Cloud and Big Data Computing
PublisherAssociation for Computing Machinery
Pages6-10
Number of pages5
ISBN (Electronic)9781450371650
DOIs
StatePublished - 28 Aug 2019
Event3rd International Conference on Cloud and Big Data Computing, ICCBDC 2019 - Oxford, United Kingdom
Duration: 28 Aug 201930 Aug 2019

Publication series

NameACM International Conference Proceeding Series

Conference

Conference3rd International Conference on Cloud and Big Data Computing, ICCBDC 2019
CountryUnited Kingdom
CityOxford
Period28/08/1930/08/19

Keywords

  • Binary classification
  • Budget
  • Confidence
  • Kernel
  • Online learning
  • Resource

Fingerprint Dive into the research topics of 'Budgeted algorithm for linearized confidence-weighted learning'. Together they form a unique fingerprint.

Cite this