Compressive Feature Learning
This paper addresses the problem of unsupervised feature learning for text data. Our method is grounded in the principle of minimum description length and uses a dictionary-based compression scheme to extract a succinct feature set. Specifically, our method finds a set of word k-grams that minimizes the cost of reconstructing the text losslessly. We formulate document compression as a binary optimization task and show how to solve it approximately via a sequence of reweighted linear programs that are efficient to solve and parallelizable. As our method is unsupervised, features may be extracted once and subsequently used in a variety of tasks. We demonstrate the performance of these features over a range of scenarios including unsupervised exploratory analysis and supervised text categorization. Our compressed feature space is two orders of magnitude smaller than the full k-gram space and matches the text categorization accuracy achieved in the full feature space. This dimensionality reduction not only results in faster training times, but it can also help elucidate structure in unsupervised learning tasks and reduce the amount of training data necessary for supervised learning.
The method consists of compressing documents for 
      accelerating the document processing in other tasks, such as 
      classification. The coding scheme is related to the one used in the 
      Lempel-Ziv algorithm, storing pointers of substrings appearing at 
      several locations in the document. The proposed approach is formulated 
      as a combinatorial optimization problem, whose solution is 
      approximated by a sequence of convex problems solved by ADMM. The 
      experiments are carried on text classification problems, where 
      compressing the documents leads to some gains in memory and 
      computational efficiency, at a minor loss in terms of precision. 
      I found the approach interesting, even though I am not familiar 
      enough with the NLP literature to exactly judge the novelty of the 
      approach. I have only a few minor remarks to make - the sentence 
      ``an optimal lossless compression of D...'' requires some 
      clarifiation. Is the coding scheme optimal in terms of minimum 
      entropy? - it is not clear that the reweighting scheme can be 
      interpreted here as a majorization-minimization procedure. Is it 
      really the case here? - minimizing (4) with respect to w amounts to 
      computing the Fenchel conjugate of the (weighted) l_infty-norm, which 
      involves a projection on a weighted l1-norm (the dual norm of the 
      l_infty-norm). When adding the non-negativity constraint, this 
      involves a projection on the simplex. Algorithms for projecting on the 
      simplex have been known for a while, and are similar to the approach 
      described in the paper. See Brucker. An O(n) algorithm for quadratic 
      knapsack problems. 1984. see also Bach et al. Optimization with 
      Sparsity-Inducing Penalties. 2012, for the computation of Fenchel 
      conjugates for norms.