On Controllable Sparse Alternatives to Softmax
Converting an n-dimensional vector to a probability distribution over n objects is a commonly used component in many machine learning tasks like multiclass classification, multilabel classification, attention mechanisms etc. For this, several probability mapping functions have been proposed and employed in literature such as softmax, sum-normalization, spherical softmax, and sparsemax, but there is very little understanding in terms how they relate with each other. Further, none of the above formulations offer an explicit control over the degree of sparsity. To address this, we develop a unified framework that encompasses all these formulations as special cases. This framework ensures simple closed-form solutions and existence of sub-gradients suitable for learning via backpropagation. Within this framework, we propose two novel sparse formulations, sparsegen-lin and sparsehourglass, that seek to provide a control over the degree of desired sparsity. We further develop novel convex loss functions that help induce the behavior of aforementioned formulations in the multilabel classification setting, showing improved performance. We also demonstrate empirically that the proposed formulations, when used to compute attention weights, achieve better or comparable performance on standard seq2seq tasks like neural machine translation and abstractive summarization.
Summary -------  This paper introduces several variants of the sparsemax mapping. Experiments are conducted on multi-label classification and attention mechanisms for neural machine translation / summarization.  With some exceptions (see below), the paper is overall clearly written. The authors put great effort in explaining their ideas with figures.  Experiments on two different tasks (multi-label classification and NMT) is also very positive.  That said, the technical contribution seems very limited. The proposed "unifying" framework is just sparsemax with different inputs. As a result, many of the proofs in the Appendix are just existing proofs with different inputs. Sparseflex is just sparsemax with a regularization parameter, which was already proposed in [16]. Sparsecone and sparsehourglass feel quite adhoc and it is not clear why they should be any better than sparsemax.  In the experiments, I am surprised sparsemax performed so much worse than sparseflex (sometimes up to 10 point difference!). As I explain below, sparsemax and sparseflex should perform exactly the same in theory. Therefore, I suspect there are issues in the empirical validation.  Overall, I feel the paper is quite below the acceptance bar for NIPS.  Major comments --------------  * I am sorry to be a bit blunt but the current title is really bad.  I would really avoid bad analogies or bad puns in a title.  My recommendation is to keep titles formal and informative.  How about just "On Sparse Alternatives to Softmax"?   * [16] is a very relevant work and I was surprised not to see it mentioned until the experiment section. I think it deserves a mention in the introduction, since it also provides a unifying framework.  * Theorem 1 is a trivial result. I wouldn't call it a theorem.  * Section 3.2: So is sparseflex just sparsemax with a regularization parameter? The fact that tunning lambda allows to control sparsity was already mentioned in [16].  * Introducing too many new names (sparseflex, sparsecone, etc) is not a good idea, as it confuses the reader. My recommendation is to pick only one or two proposed methods. You don't need to introduce new names for every special case.  * I am surprised that sparsemax performs so much worse than sparseflex in Figure 5 and 6.  Indeed, if the vectors of scores z is produced by a linear model, i.e., z = W x, the regularization parameter can be absorbed into W as is obvious from Eq. (2). Given this fact, how do you explain why sparseflex performs so much better?  * Appendices A.1 to A.4 are essentially the same proof again and again with different inputs. Since sparsegen reduces to the projection on the simplex, there is no need for all this...  * For multi-label classification, experiments on real data would be welcome. Also it'd be great to report the average sparsity per sample on the test set.  Detailed comments -----------------  * Line 62: Z_+ is commonly denoted N.  * Line 63: {a, b, c} usually defines the elements of a set, not a vector  * There are many works tackling the projection onto the simplex before [15]. It would great to give them proper credit. Some examples:  P.Brucker. An O(n) algorithm for quadratic knapsack problems. Operations Research Letters,3(3):163–166, 1984.  C. Michelot.  A finite algorithm for finding the projection of a point onto the canonical simplex of Rn.  Journal of Optimization Theory and Applications, 50(1):195–200, 1986.  * Line 209: multiple labels can be true => multiple labels are allowed  ----------  > However, A.3 follows directly from A.1 and can be removed.  I still think that A.1 is basically a known result since Eq. (6) (supp) can be reduced to the projection on the simplex.  > [On empirical evaluation]  Thank you for the clarification between L_sparsemax and L_sparseflex. This addressed my concern about Fig. 5.