Learning Label Structure for Compressed Sensing Based Multilabel Classification

We present a compressed sensing based approach to multilabel classification that exploits the label structure present in many multilabel applications. The compressed sensing method exploits the sparsity in the label vector. The label vector is projected to a lower dimensional space by a random projection matrix. From the training data we learn how to predict the projected vector directly from the features of the samples. For a new test sample, we first predict the projected vector and then use compressed sensing recovery algorithm to estimate the sparse label vector. For many practical scenarios the label vector is not only sparse but the active labels represent a context or theme; hence have a structure. In this paper we propose to learn the label structure instead of considering the individual labels to be independent and identically distributed. We assume a Bayesian model for the labels and model the label structure as latent tree. We learn the label structure from the training data and use the learned structure during estimation of the label vector from predicted projections. Furthermore, we propose a new structure learning approach where we hash the labels into smaller number of buckets and learn the structure from these buckets. This significantly reduces the computational complexity without sacrificing accuracy. We present numerical results to demonstrate this approach and its benefit.