• Login
    View Item 
    •   Research Bank Home
    • Study Areas
    • Computing
    • Computing Journal Articles
    • View Item
    •   Research Bank Home
    • Study Areas
    • Computing
    • Computing Journal Articles
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Incremental and decremental max-flow for online semi-supervised learning

    Zhu, Lei; Pang, Shaoning; Sarrafzadeh, Hossein; Ban, Tao; Inoue, Daisuke

    Thumbnail
    Share
    View fulltext online
    Incremental and Decremental Max-flow for.pdf (5.987Mb)
    Date
    2016-04-13
    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.
    Permanent link to Research Bank record:
    https://hdl.handle.net/10652/3582
    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.
    Keywords:
    graph mincuts, data modelling, online semi-supervised learning, max-flow, augmenting path, incremental decremental max-flow, residual graph, algorithms
    ANZSRC Field of Research:
    080109 Pattern Recognition and Data Mining
    Copyright Holder:
    Institute of Electrical and Electronics Engineers (IEEE)
    Rights:
    This digital work is protected by copyright. It may be consulted by you, provided you comply with the provisions of the Act and the following conditions of use: Any use you make of these documents or images must be for research or private study purposes only, and you may not make them available to any other person. You will recognise the author's and publishers rights and give due acknowledgement where appropriate.
    Metadata
    Show detailed record
    This item appears in
    • Computing Journal Articles [50]

    Library home
    Send Feedback
    Research publications
    Unitec
    Moodle
    © Unitec Institute of Technology, Private Bag 92025, Victoria Street West, Auckland 1142
     

     

    Usage

    Downloads, last 12 months
    253
     
     

    Usage Statistics

    For this itemFor the Research Bank

    Share

    About

    About Research BankResearch at UnitecContact us

    Help for authors  

    How to add researchOpen Access GuideVersions Toolkit

    Register for updates  

    LoginRegister

    Browse Research Bank  

    EverywhereAcademic study areasAuthorDateSubjectTitleType of researchSupervisorThis CollectionAuthorDateSubjectTitleType of researchSupervisor

    Library home
    Send Feedback
    Research publications
    Unitec
    Moodle
    © Unitec Institute of Technology, Private Bag 92025, Victoria Street West, Auckland 1142