Online binary classification from similar and dissimilar data

Senlin Shu, Haobo Wang, Zhuowei Wang, Bo Han, Tao Xiang, Bo An, Lei Feng*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

Abstract

Similar-dissimilar (SD) classification aims to train a binary classifier from only similar and dissimilar data pairs, which indicate whether two instances belong to the same class (similar) or not (dissimilar). Although effective learning methods have been proposed for SD classification, they cannot deal with online learning scenarios with sequential data that can be frequently encountered in real-world applications. In this paper, we provide the first attempt to investigate the online SD classification problem. Specifically, we first adapt the unbiased risk estimator of SD classification to online learning scenarios with a conservative regularization term, which could serve as a naive method to solve the online SD classification problem. Then, by further introducing a margin criterion for whether to update the classifier or not with the received cost, we propose two improvements (one with linearly scaled cost and the other with quadratically scaled cost) that result in two online SD classification methods. Theoretically, we derive the regret, mistake, and relative loss bounds for our proposed methods, which guarantee the performance on sequential data. Extensive experiments on various datasets validate the effectiveness of our proposed methods.

Original languageEnglish
JournalMachine Learning
DOIs
Publication statusE-pub ahead of print - 20 Dec 2023

Scopus Subject Areas

  • Software
  • Artificial Intelligence

User-Defined Keywords

  • Online learning
  • Passive-aggressive method
  • Similar-dissimilar classification
  • Unbiased risk estimator

Fingerprint

Dive into the research topics of 'Online binary classification from similar and dissimilar data'. Together they form a unique fingerprint.

Cite this