Rademacher complexity bounds for a penalized multiclass semi-supervised algorithm

Yury Maximov, Massih Reza Amini, Zaid Harchaoui

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

    Abstract

    We propose Rademacher complexity bounds for multi-class classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing ? predominant classes using the labeled training examples such that the proportion of their non-predominant classes is below a fixed threshold stands for clustering consistency. In the second step, a classifier is trained by minimizing a margin empirical loss over the labeled training set and a penalization term measuring the disability of the learner to predict the ? predominant classes of the identified clusters. The resulting data-dependent generalization error bound involves the margin distribution of the classifier, the stability of the clustering technique used in the first step and Rademacher complexity terms corresponding to partially labeled training data. Our theoretical result exhibit convergence rates extending those proposed in the literature for the binary case, and experimental results show empirical evidence that supports the theory.

    Original languageEnglish
    Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
    EditorsJerome Lang
    PublisherInternational Joint Conferences on Artificial Intelligence
    Pages5637-5641
    Number of pages5
    ISBN (Electronic)9780999241127
    Publication statusPublished - 2018
    Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
    Duration: 13 Jul 201819 Jul 2018

    Publication series

    NameIJCAI International Joint Conference on Artificial Intelligence
    Volume2018-July
    ISSN (Print)1045-0823

    Conference

    Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
    Country/TerritorySweden
    CityStockholm
    Period13/07/1819/07/18

    Fingerprint

    Dive into the research topics of 'Rademacher complexity bounds for a penalized multiclass semi-supervised algorithm'. Together they form a unique fingerprint.

    Cite this