Assigning several labels to digital data is becoming easier because we can perform it in a collaborative manner with Internet users. However, some suitable labels may be missed and may not be attached to the data leading to inaccuracies in classification. In this paper, we propose a novel graphbased multi-label classifier to support the multi-labeling task. The core process of our algorithm is to update label weights of labeled data from their top-k similar data in each label propagation step. We report that our algorithm is more stable for F-scores compared to the state-of-the-art ones even though the some correct labels are missed.
©2018. Copyright for the individual papers remains with the authors. Copying permitted for private and academic purposes.
WII’18, March 11, 2018, Tokyo, Japan 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 latter Wikipedia article. Moreover, these three categories are not assigned to another article 3. Thus, even though these articles report the same topic, the attached categories are not the same.
The missing of labels is a very serious issue to achieve good accuracy because almost all classifiers assume that labeled data prepared by people are correct. We show how the missing correct labels worsens the accuracies of SVM, random forest and label propagation on a multi-label dataset called the SIAM 2007 Text Mining Competition dataset 4, whose documents are assigned 3.4 labels on average in Fig. 1. We can see that if only one label is missed, all their micro-averaged F-scores worsen by about 5%. If more than two labels are missing, the scores can decrease by about 10%.
In this paper, we propose a novel graph-based algorithm for
multi-label classification, label propagation using amendable
clamping (LPAC), in order to decrease the impact of missing
labels on accuracy. Our algorithm enhances cluster assumption
[
Contributions: The core contribution of this paper is to update label weights of labeled data in order to make label propagations for missed labels in each label propagation step. This process takes cluster assumption in clamping; in other words, even though some suitable labels in labeled data are missed, 3https://en.wikipedia.org/wiki/Bombing_of_Sandhurst_Road_ School 4https://catalog.data.gov/dataset/ siam-2007-text-mining-competition-dataset our algorithm adds the weight from their similar data after propagating labels.
The original LP algorithm also takes the cluster assumption,
but we enhance it by adding weights of top-k nearest
neighbors. Some researchers improve the original LP algorithm
to take label correlation [
In this section, we describe the well-known LP algorithm [
The entire algorithm for LP is as follows: first, the two initial matrices, P and Y , are constructed. Then, the multiplication of them is repeated until all elements are fixed, or the iterative process achieves a certain number. During the iteration, values of Y l are reset before invoking the next iteration–this is known as clamping. This clamping assumes that all the labeled data are perfectly assigned suitable labels.
We extend the traditional LP to make label propagations for missed labels by adding the following two steps: 1. Enhancing propagating label values of similar documents. 2. Updating Y l from labels of similar documents. For the first extension, we add (M P) Yt in matrix multiplication where is the Hadamard product and M 2 NjNj jNj is a matrix representing KNN of the data; Mi j is 1 if the ith data is in the top-k similar ones of the jth data, otherwise it is 0. We call this extension local-propagation because M P allows propagating label values only for top-k similar data. In contrast, we call P Yt , which is used in traditional LP, global-propagation. To adjust the balance between local- and global-propagations, we introduce a hyper-parameter b as follows:
Propt = b P Yt + (1 b )(M
P) Yt We then take cluster assumption, which means that the data tend to form discrete clusters, and points in the same cluster are more likely to share a label. For this, we calculate the averages from the top-k similar documents, and set them as the result of label propagation. The following equation invokes this process.
M Propt
k Ytl+1 =
M Ytl+1 k For the second extension (updating the values of labeled data by similar data), we perform KNN again. Then, we calculate the average values of the top-k similar data for each label. These values are set before invoking the next iteration as follows: Finally, we show our entire algorithm in Alg. 1. Lines 4 and 6 correspond to the above two extensions, respectively. Algorithm 1 Label propagation using amendable clamping 1: Construct a probablistic transition matrix P and M defined. 2: Let Y0 = [Y0l : 0] 3: for t = 1 to T 1 do 4: Propt = b P Yt + (1 5: Yt+1 = M Propt =k 6: Ytl+1 = M Ytl+1=k 7: end for 8: return YT b )(M
P) Yt
Dataset. We used the SIAM 2007 Text Mining Competition dataset, which is a subset of the Aviation Safety Reporting System (ASRS) dataset. It provides various types of aviation safety events reported by pilots, controllers, mechanics, flight attendants, and dispatchers. In this dataset, there are 4,819 labeled data, 4,819 unlabeled data, and 22 classes. On average, a labeled data is assigned 3.41 labels.
We first extract some data from this dataset to remove labels;
we then remove labels for the data. Both the extraction ratio
and removal ratio are increased from 10% to 100%, in 10%
increments, and are selected at random. For all the cases, we
check the Micro-averaged F-scores measured by the 10-fold
cross-validation of classifiers that are trained on the dataset.
As our demonstration focuses on document classification, we
apply latent dirichlet allocation (LDA) [
Algorithms. We compared LPAC with five baselines: LP,
dynamic LP (DLP) [
Parameters. We set T (the iteration number of LP), the
dimension of the LDA and b to 1,000, 1,000 and 0.1 respectively.
All these values were empirically chosen based on analyzing
the results on the small held-out development dataset. Note
here that DLP uses two additional parameters (l and a ). We
set them to the same values used in [
We show the results in Fig. 2. We can see that LPAC outperforms the comparative algorithms. Figs. 2 (a) (f) show the accuracies of each classifier trained on datasets in which 0% 100% of the documents do not have correct labels. The accuracies of the LPAC almost match the result achieved when the classifier is trained on a dataset in which 10% of the documents have missing labels. In contrast, all baselines tend to provide decreased accuracy once the ratio of missing-label documents exceeds 30%. In particular, once the missing-label ratio reaches 50%, accuracies of DLP, Random Forest and SVM rapidly decrease from about 10% to 50%. Note that LNP and LP also tend to keep their accuracies, but the scores are lower than LPAC.
To better enable comparison between all classifiers, Fig. 3 shows their F-scores in the cases that we extracted 50% and 70% of documents for removing labels, respectively. When the ratio of documents had missing labels reaches 40%, the F-scores of three baselines (DLP, Random Forest and SVM) begin to more early decrease compared with 0 40%. Moreover, when the ratio is 70%, SVM and random forest sharply fall accuracies. In the case of 70% of documents extracted, the accuracies of almost all baselines begin to decrease when the ratio of missing labels exceeds 20%. Conversely, we can see that LPAC maintains a stable accuracy for all ratios of missing labels.
Next, we show the correlation between F-scores and the number of labeled documents for LPAC in Fig. 4. We plot results of three cases where 0%, 50% and 70% of documents had missing labels. Fig. 4 shows that there is a positive correlation between them. Indeed, the correlation coefficiencies of them are 0.76, 0.72 and 0.75, respectively. Thus, we can say that the more there are correct labels are assigned to training data, the better accuracy we can obtain.
Next, we show how many iterations each LP-based algorithm needs to convergence the propagating labels in Fig. 5. As this figure shows, LPAC is the lowest of the four LP-based algorithms. This is because that LPAC makes label propagation by averaging label values of not only all data but also ones of similar documents in order to enhance take cluster assumption during propagating labels.
70 60 50 40 30 20 10 0
Finally, we show the analyzing time of LP and LPAC in Fig. 6. We can see that both of the two lines draw exponential growth. The analyzing time of LPAC is about twice as slow as the one of LP if we use 10,000 data; however, it is not problem for many objectives since the LPAC’s analyzing time is about two minutes.
In this paper, we proposed a novel graph-based multi-label classification (LPAC) to apply to a moderately challenging multi-labeling task. LPAC enforces label propagations by two extensions: propagating labels according to top-k similar data and updating labeled data by taking cluster assumption. As demonstrated in our experiments, these two extensions make the F-score of LPAC stable compared to those of algorithms proposed by previous studies.
Future work will identify (a) the effective utilization of label correlation. Once our algorithm is extended to take care of label correlation, we can implement label recommendations. This suggestion should be helpful especially in the case that there are many labels such as Wikipedia category system. Future work will also identify (b) how effectively our algorithm works on a real dataset that contains missing labels data like Wikipedia as discussed in Introduction. Finally, as a future work we will study (c) establishing algorithm that can be trained on dataset including both of wrong and missing. Although this paper assumes that there are no data attached any wrong labels, real datasets might contain both of the two kinds of labels at the same time. We will explore how to reduce the noises.
Acknowledgments. This work was supported in part by MEXT Grant-in-Aid (#17K12792).