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


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
Pages (from-to)3463–3484
Number of pages22
JournalMachine Learning
Issue number6
Early online date20 Dec 2023
Publication statusPublished - Jun 2024

Scopus Subject Areas

  • Software
  • Artificial Intelligence

User-Defined Keywords

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


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

Cite this