Generalized Large Margin kNN for Partial Label Learning

To deal with noises in partial label learning (PLL), existing approaches try to perform disambiguation either by identifying the ground-truth label or by averaging the candidate labels. However, these methods can be easily misled by the false-positive noisy labels in the candidate set, and fail to generalize well in testing. When labeling information is ambiguous, learning paradigms should depend more on the underlying data structure. Large margin nearest neighbour (LMNN) is a popular strategy to consider instance and class correlations in supervised learning, but can not be directly used in weakly-supervised PLL due to the ambiguity of labeling information. In this paper, we propose a novel Generalized Large Margin kNN for Partial Label Learning (GLMNN-PLL), which employs the principle of LMNN to adapt the framework to PLL by generalizing the constraint from the same class to similarly-labeled. Generally, GLMNNPLL aims to learn a new metric and perform disambiguation by reorganizing the underlying data structure, that is, making similarly labeled instances closer to each other while making differently labeled instances separated by a large margin. As two close instances with shared labels do not necessarily belong to the same class, we put a weight on each instance pair. An efficient algorithm is designed to optimize the proposed method and the convergence is analyzed in this paper. Moreover, we present a theoretical analysis of the generalization error bound for GLMNN-PLL. Comprehensive experiments on controlled UCI datasets as well as real-world partial label datasets from various domains demonstrate the superiorities of the proposed method.