Robust Bloom Filters for Large Multilabel Classification Tasks
This paper presents an approach to multilabel classification (MLC) with a large number of labels. Our approach is a reduction to binary classification in which label sets are represented by low dimensional binary vectors. This representation follows the principle of Bloom filters, a space-efficient data structure originally designed for approximate membership testing. We show that a naive application of Bloom filters in MLC is not robust to individual binary classifiers' errors. We then present an approach that exploits a specific feature of real-world datasets when the number of labels is large: many labels (almost) never appear together. Our approach is provably robust, has sublinear training and inference complexity with respect to the number of labels, and compares favorably to state-of-the-art algorithms on two large scale multilabel datasets.
This is a well-written paper that makes an interesting 
      contribution to an important topic. In fact, the idea of using Bloom 
      filters for dimensionality reduction in multi-label classification is 
      intriguing. This seems to be a companion paper of another paper, in which 
      this idea has already been introduced. The contribution of this paper is 
      to improve the encoding scheme used in the Bloom filter. To this end, the 
      structure of the label space is exploited by means of clustering methods. 
      As claimed by the authors, this encoding makes the filter more robust. 
      While I'm essentially fine with the idea of the method and 
      theoretical part of the paper, I am much less convinced of the empirical 
      study. First, given the goal of efficiency, one would certainly expect an 
      empirical analysis of runtime in the experimental part, not only 
      predictive accuracy. Moreover, the two data sets used in the 
      experiments are somewhat debatable, especially due to their extremely low 
      label cardinality (it would be interesting to see the marginal label 
      distribution). In addition to the sparsity, the distribution will probably 
      be skewed, so that most of the labels will almost never occur. In fact, 
      one may wonder whether such data sets are sufficiently representative to 
      provide an idea of how the authors' approach performs. Indeed, the 
      performance of this approach (like the performance of other compression 
      schemes) strongly depends on the label distribution, which is very 
      specific for the data sets used. Moreover, losses like Hamming, 
      which the authors focus on, are debatable in such cases, especially since 
      always predicting negative will already yield an extremely low loss. For 
      example, the author report a Hamming loss of 0.000734 for SBF and "only" 
      0.000705 for RBF. Is this tiny difference of any meaning? Hard to say, 
      especially since no standard deviations are reported.