Extreme Classification Methods have become of paramount importance, particularly for Information Retrieval (IR) problems, owing to the development of smart algorithms that are scalable to industry challenges. One of the prime class of models that aim to solve the memory and speed challenge of extreme multi-label learning is Group Testing. Multi-label Group Testing (MLGT) methods construct label groups by grouping original labels either randomly or based on some similarity and then train smaller classifiers to first predict the groups and then recover the original label vectors. Recently, a novel approach called MACH (Merged Average Classifiers via Hashing) was proposed which projects the huge label vectors to a small and manageable count-min sketch (CMS) matrix and then learns to predict this matrix to recover the original prediction probabilities. Thereby, the model memory scales O(logK) for K classes. MACH is a simple algorithm which works exceptionally well in practice. Despite this simplicity of MACH, there is a big gap between the theoretical understanding of the trade-offs with MACH. In this paper we fill this gap. Leveraging the theory of count-min sketch we provide precise quantification of the memory-identifiablity tradeoffs. We extend the theory to the case of multi-label classification, where the dependencies make the estimators hard to calculate in closed forms. To mitigate this issue, we propose novel quadratic approximation using the Inclusion-Exclusion Principle. Our estimator has significantly lower reconstruction error than the typical CMS estimator across various values of number of classes K, label sparsity and compression ratio. Extreme Classification has taken center-stage of Data Mining and Information Retrieval research in the past few years (Zamani et al., 2018; Prabhu et al., 2018b; Jain et al., 2019; Choromanska & Langford, 2015) . It refers to the vanilla multiclass and multilabel classification problems where the number of classes K is significantly large. A large number of classes K brings a new set of computational and memory challenges in training and deploying classifiers. There have been several paradigms of models that tackle the scale challenge of Extreme Classification like 1-vs-all methods (Prabhu et al., 2018b; Jain et al., 2019; Babbar & Schölkopf, 2017) , tree based methods (Prabhu et al., 2018a; Jain et al., 2016) , embedding models (Nigam et al., 2019; Bhatia et al., 2015) , etc. (as noted on the popular Extreme Classification Repository). One of the recent approaches proposed to alleviate the scale challenge of Multilabel Classification is Group Testing (Ubaru & Mazumdar, 2017; Ubaru et al., 2016; Vem et al., 2017) . In this method, all labels are grouped randomly into m groups/clusters. Each label may go into more than one group. We first train a classifier that predicts which of these clusters the input belongs to (treating each cluster as a separate label in a multilabel setting). For any given input, we first predict the clusters into which the true labels of the input may have been pooled. We can then identify all the true labels by taking an intersection over the inverted clusters. This approach suffers from a critical problem that even tree based approaches have, i.e., hard assignment of clusters. Since the recovery of true labels depends solely on hard-prediction of clusters, a mistake in the cluster prediction can cost us dearly in the final label prediction. Also, since the labels are pooled randomly, each individual meta-classifier is a weak and noisy one. In a recent development, Merged Average Classifiers via Hashing (MACH) (Medini et al., 2019) was proposed that alleviates the hard-prediction problem in Group Testing methods by identifying the best labels based on the sum of prediction probabilities of the respective groups for a given input. In the hindsight, MACH subtly learns to predict a count-min sketch (CMS) (Cormode & Muthukrishnan, 2005 ) matrix of the original probability vector. For the case of multiclass classification (every input having just a single label unlike multilabel), MACH proposes an unbiased estimator to recover the original K dimensional probability vector from the predicted CMS matrix. Multiclass classification naturally fits into the count-min sketch setting as no two labels can appear simultaneously for a given input. But the proposed theory does not naturally extend to multilabel learning. Further, the variance and error bounds for multiclass classification rely heavily on the choice of number of hash tables and the size of each hash table. That aspect has not been explored in prior work. Our Contributions: In this work we broadly make the following contributions: 1) We revisit MACH with a thorough analysis of proposed reconstruction estimator for multiclass learning. In particular, we prove that the variance of estimation is inversely proportional to the product of product of number of hash tables and size of each hash table (in theorem 2). 2) We also obtain a lower bound on hash table hyperparametrs given a tolerance to prediction error (in Theorems 4 and 5). 3) We propose a novel reconstruction estimator for the case of multilabel learning using InclusionExclusion principle (in theorem 6). This estimator comes out as a solution to a quadratic equation (hence we code-name it as 'quadratic estimator'). 4) We simulate multilabel learning setting by generating K dimensional probability vectors and their proxy CMS measurements. We then reconstruct the probability vector using both the mean estimator and the quadratic estimator and show that the reconstruction Mean-Squared Error (MSE) is significantly lower for the new estimator. Following the above steps, we show the comparison of our proposed quadratic estimator in theorem 6 against the plain mean estimator by varying the values of K, B, V and base prob in figure 3 . We can infer the following insights from the plots : • As K increases, the MSE grows. This is expected because the reconstructed vector has a small non-zero probability for many of the K classes and this induces noise and hence MSE grows. But the top classes are still retrieved with high certainty. • For any K, V, base prob, the MSE decreases when B increases which is expected (fewer collisions of classes and hence less noisier predictions). As the MSE gets lower, the gains from the square-root estimator are also low. This is good because in scenarios where B and R are small, we can do much better recovery using the proposed estimator. • For any K, B, base prob the MSE increases with V . This is again natural because larger V induces more 'true' class collisions and hence the retrieval becomes fuzzy. • For any K, B, V the MSE decreases with base prob, albeit with much little difference than previous cases. This is interesting because a high base prob means that we have few but highly confident 'true' classes among K. On the other hand, lower base prob indicates that 'true' classes are scattered among a larger subset among K classes. Yet, MACH recovers the original probabilities with commendably low MSE. Varying B for K = 10000 Varying base prob for K = 10000 Varying B for K = 100000 Varying V for K = 100000 Varying base prob for K = 100000 Varying B for K = 1000000 Varying B for K = 1000000 Varying base prob for K = 1000000 Figure 3: Reconstruction Error (MSE) comparison between 1) vanilla mean estimator (plotted in magenta) and 2) proposed square-root estimator (plotted in green); for various configurations of K,B and V. The value of K varies as 10000, 100000, 1000000 for the 1 st , 2 nd and 3 rd rows respectively. In each row, the first plot fixes V, base prob and compares various values of B. The 2 nd plot fixes B, base prob and compares different values of B. The 3 rd one fixes B, V and compares different values of base prob. In all cases, we notice that the square-root estimator is consistently and significantly lower in MSE than the corresponding mean estimator. We perform a rigorous theoretical analysis of using Count-Min-Sketch for Extreme Classification and come up with error bounds and hyper-parameter constraints. We identify a critical shortcoming of reconstruction estimators proposed in prior research. We overcome the shortcoming by treating each bucket in a hash table as a union of merged original classes. Using inclusion-exclusion principle and a controlled label sparsity assumption, we come up with an approximate estimator to reconstruct original probability vector from the predicted Count-Min Sketch measurements. Our new estimator has significantly lower reconstruction MSE than the prior estimator.
How to estimate original probability vector for millions of classes from count-min sketch measurements -  a theoretical and practical setup.
{"src": "scitldr-AIC_train", "paper_id": "S1evKR4KvB"}