Incremental and decremental max-flow for online semi-supervised learning
Loading...
Supplementary material
Other Title
Authors
Zhu, Lei
Pang, Shaoning
Sarrafzadeh, Hossein
Ban, Tao
Inoue, Daisuke
Pang, Shaoning
Sarrafzadeh, Hossein
Ban, Tao
Inoue, Daisuke
Author ORCID Profiles (clickable)
Degree
Grantor
Date
2016-04-13
Supervisors
Type
Journal Article
Ngā Upoko Tukutuku (Māori subject headings)
Keyword
graph mincuts
data modelling
online semi-supervised learning
max-flow
augmenting path
incremental decremental max-flow
residual graph
algorithms
data modelling
online semi-supervised learning
max-flow
augmenting path
incremental decremental max-flow
residual graph
algorithms
ANZSRC Field of Research Code (2020)
Citation
Zhu, L., Pang, S., Sarrafzadeh, A., Ban, T., & Inoue, D. (2016). Incremental and Decremental Max-flow for Online Semi-supervised Learning. IEEE Transactions on Knowledge and Data Engineering, 28, pp.1-13.
Abstract
Max-flow has been adopted for semi-supervised data modelling, yet existing algorithms were derived only for the learning from static data. This paper proposes an online max-flow algorithm for the semi-supervised learning from data streams. Consider a graph learned from labelled and unlabelled data, and the graph being updated dynamically for accommodating online data adding and retiring. In learning from the resulting non stationary graph, we augment and de-augment paths to update max-flow with a theoretical guarantee that the updated max-flow equals to that from batch retraining. For classification, we compute min-cut over current max-flow, so that minimized number of similar sample pairs are classified into distinct classes. Empirical evaluation on real-world data reveals that our algorithm outperforms state-of-the-art stream classification algorithms.
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Permanent link
Link to ePress publication
DOI
Copyright holder
Institute of Electrical and Electronics Engineers (IEEE)
Copyright notice
All rights reserved