Rare category exploration with noisy labels

Highlights

• We define and address the rare category exploration problem with noisy labels.

• We propose a compactness based similarity matrix for RCE.

• Experimental evaluation demonstrates the effectiveness of our two methods.

• We prove the effectiveness of our methods via theoretical analysis.

Abstract

Starting from a few labelled data examples as the seeds, rare category exploration (RCE) aims to find out the target rare category hidden in the given dataset. However, the performance of conventional RCE approaches is very sensitive to noisy labels while the presence of noises in manually generated labels is almost inevitable. To address this deficiency of traditional RCE approaches, this paper investigates the RCE process in the presence of noisy labels, which to the best of our knowledge has not yet been intensively studied by previous research. Based on the assumption that only one labelled data example of the rare category is correctly labelled while the other few data examples may be wrongly labelled, we first propose a label propagation based algorithm SLP to extract the coarse shape of a rare category. Then, we refine the result by proposing a mixture-information based propagation model, RLP. Extensive experiments have been conducted on six real-world datasets, which show that our method outperforms the state-of-the-art RCE approaches. We also show that even with 20% noisy labels, our method is able to achieve a satisfactory accuracy.

Introduction

Rare categories were first proposed by Pelleg and Moore in Pelleg and Moore (2004), where a rare category was defined as tiny clusters of similar anomalies. Such rare categories are pervasive in real life. For instance, in cyber security, a rare category can be seen as a cluster of a specific kind of network attacks (Gu, Perdisci, Zhang, & Lee, 2008). Rare category examples (e.g., network attacks) are usually of higher significance than that of data examples from the major category (e.g., normal network accesses). Hence, rare category exploration (RCE) is proposed to conduct a comprehensive analysis on interesting rare categories.

RCE is formally formulated as finding the remaining data examples of a rare category from a few seeds of labelled data examples belonging to this rare category. That is, extracting data examples of the rare category with the help of a few labels. The RCE technique can be widely used in many real-world applications. For example, in the area of financial transactions, a rare category may correspond to a small fraction of malicious transactions (Bay, Kumaraswamy, Anderle, Kumar, & Steier, 2006). Finding out all the malicious transactions can help us analyze the specific security leaks in a financial system.

Driven by the wide applications of RCE, researchers have explored various possibilities to solve the RCE task. A thread of the existing RCE algorithms relies on a few labelled data examples for model building and training (He, Tong, Carbonell, 2010, Liu, Huang, He, Chiew, Gao, 2015). He el al. proposed an optimization based solution to train a rare category classifier (He et al., 2010). Liu et al. utilized wavelet transformation for rare category exploration (Liu et al., 2015). Another thread of RCE algorithms concentrates on extracting a rare category only from one single correctly labelled data example from this rare category (Huang, Chiew, Gao, He, & Li, 2014).

Though various solutions have been proposed for the RCE task, the following challenges still remain in many real-world applications. First, in practice, it is quite common that there may be some erroneous labels (referred to as noisy labels henceforth). These noisy labels are generated from many ways, including the false tagging by crowd sourcing (Kazai, Kamps, Milic-Frayling, 2013, Krishna, Hata, Chen, Kravitz, Shamma, Fei-Fei, Bernstein, 2016), the misdiagnoses by domain experts (Rebbapragada, Brodley, Sulla-Menashe, Friedl, 2012, Song, Wang, Zhang, Sun, Yang, 2015), and even the adversarial countermeasures by attackers (Nelson, Rubinstein, Huang, Joseph, Lau, Lee, Rao, Tran, Tygar, 2010, Wang, Wang, Zheng, Zhao, 2014). However, most of the existing methods assume the labels are 100% correct and reliable. It seems that the performance of these algorithms will unfortunately degrade substantially in practical RCE scenarios. Second, rare categories are usually complex-shaped and even overlapped with major categories in some special cases. Therefore, such approaches that extract a rare category only from one correct label may wrongly identify some of the data examples located at the boundary of the rare category, due to the lack of sufficient label information.

To address the above challenges, we investigate an RCE scenario in the presence of noisy labels based on the following two basic assumptions, namely (1) the label for the seed of the objective rare category is correct, and (2) noisy labels exist across the other few labelled data examples from both rare and major categories. To this end, we first propose a label propagation based algorithm known as SLP (seed label propagation) to identify the coarse shape of the objective rare category from a seed. Equipped with a compactness based similarity matrix, SLP propagates the seed label along the high density areas of the objective rare category. Then, we develop a mixture-information based propagation model termed as RLP to extract the latent and useful information in the other few labels while explicitly addressing the noisy label issue. Specifically, RLP first refines the noisy labels and the coarse shape; then, it propagates the refined labels over the whole dataset to find those data examples not included in the coarse shape. Without any rigid assumption on the structure of a rare category, our algorithms can find complex-shaped rare categories in the presence of noisy labels.

In brief, the key contributions of this work are:

• To our knowledge we are the first to explicitly define and address the rare category exploration problem in the presence of noisy labels.

• We propose a compactness based similarity matrix among data examples for capturing the characteristics of rare categories. To handle a dataset with complex shaped rare categories, we propose the kernelized version of this compactness based similarity matrix.

• Extensive experiments have been conducted on six real world datasets. Experimental results show that our proposed methods can achieve a relatively satisfactory performance even when 20% noisy labels are presented. As another contribution, we have proven the effectiveness of the proposed approaches via theoretical analysis.

The remaining sections are organized as follows. We review the related work in Section 2, and give the problem formulation and assumptions in Section 3. In Section 4, we first introduce the construction of the compactness based similarity matrix and its kernelized version, and then present the label propagation based algorithm SLP and the label-noise robust algorithm RLP. Finally, we report the experimental results and findings in Section 5 and conclude the paper in Section 6.