Loss Functions for Multiset Prediction
We study the problem of multiset prediction. The goal of multiset prediction is to train a predictor that maps an input to a multiset consisting of multiple items. Unlike existing problems in supervised learning, such as classification, ranking and sequence generation, there is no known order among items in a target multiset, and each item in the multiset may appear more than once, making this problem extremely challenging. In this paper, we propose a novel multiset loss function by viewing this problem from the perspective of sequential decision making. The proposed multiset loss function is empirically evaluated on two families of datasets, one synthetic and the other real, with varying levels of difficulty, against various baseline loss functions including reinforcement learning, sequence, and aggregated distribution matching loss functions. The experiments reveal the effectiveness of the proposed loss function over the others.
The paper proposes a novel method for multiset prediction, which is to predict, for each class, the number of instances of that class present in the example.  As in previous work, the problem is reduced to training a policy to predict a possibly-repeating sequence of labels.  The main novel proposal in this work is to train the policy to minimize the KL divergence between the expert policy and the model policy, which avoids the need to define an arbitrary order in which to predict the sequence (as in other sequence-based methods), and also sidesteps the optimization difficulties of the RL-based approach.  Experiments show that this method substantially outperforms existing methods on the task of multiple-instance prediction for images.  Pros: 1. The proposed method is simple, well-motivated and carefully designed, and performs well in practice 2. The task seems like a good abstraction for a number of practical applications, and the proposed method solves it very well 3. Focused experiments systematically motivate the method, validate hypotheses, and demonstrate the real-world usefulness and substantial advantages of the method over existing methods 4. Paper is clearly written overall  Cons: 1. The novelty and generality of the technique deployed here may be a bit on the low side 2. One relevant baseline may be missing: using a graphical model over the instance counts of different classes  Overall, I believe the paper makes a compelling case for the proposed method.  It is simple and substantially outperforms what seem to be reasonably strong baselines for the task on real-world problems.  The method is well-motivated, and the paper does a good job of articulating the careful consideration that went into designing the method, and why it might be expected to outperform existing approaches.  The experiments are also well-designed, focusing on answering the most important and interesting questions.  I could also imagine this work having significant impact, because many interesting tasks could be formulated in terms of multiset prediction.  I believe the paper does a commendable job of categorizing the different possible approaches to this problem, explaining the advantages of the proposed method, and empirically demonstrating those advantages.  The proposed method avoids the arbitrary-permutation-dependence of some other sequential prediction approaches, and avoids having to do RL over a long time horizon, as in RL-based methods.  I appreciated how these advantages were clearly articulated and then validated experimentally with targeted experiments.  I did have a doubt with regard to the “one-step distribution matching” baseline—this was tried in the experiments, and the paper cited the “lack of modeling of dependencies among the items” as a potential explanation for its poor performance, but I found this a bit unsatisfying.  I think it should be possible to define a graphical model where each node counts the number of instances of a particular class, and cliques model correlations between counts of different classes.  The node and clique potentials could then be learned so as to maximize the data likelihood.  Since this model may be non-trivial, and I do not have a citation for it, I do not see the lack of this baseline as an egregious oversight, however.  I also noticed that although the lack of a need to perform RL is claimed as a benefit of this method over [25], I think you could argue that the proposed method could be thought of as an approximation of a more natural method that would also require RL.  Specifically, the “most natural” version of the multiset loss function would be marginalized over all possible policy roll-outs.  However, it seems that in practice, the method just samples one roll-out, and optimizes the resulting loss with that roll-out fixed.  The resulting loss gradient is therefore biased, because it does not take into account how the sampled roll-out changes as the policy parameters change.  To un-bias the gradient, one would again have to resort to policy gradient.  If it turns out that neglecting the bias is fine in practice, then that is fine; however, it should probably be acknowledged.  On the other hand, I would like to point out that the choice to sample past states from the policy instead of the expert is a subtle but smart choice, and the paper both includes a citation as to why this is superior, and demonstrates empirically that this choice indeed outperforms the naive approach of sampling past states from the expert when evaluating the loss.  In terms of novelty, I would say that might be one of the weaker aspects of the work, since this is technically a rather straightforward method.  However, I think there is nonetheless significance in carefully and systematically designing a simple method to perform well for a given task, especially taking subtle considerations such as that mentioned above into account.  In summary, I think the clarity and simplicity of the method, combined with the compelling experimental results shown here, will make this work interesting to a significant cross-section of the NIPS audience.  POST-REBUTTAL COMMENTS  I think the paper should acknowledge the connection to previous methods (mentioned by reviewer 1) that employed a KL loss for similar problems.  Mentioning the potential applications to computer vision problems up-front may also help motivate the problem better, because 'multisets' may sound too abstract to many readers.  As for the issue of potential bias in the gradient, I am still a little unclear on this.  It seems like there are two ways to interpret this method: as an RL method, or as an online learning problem (e.g., learning to search).  I am more familiar with the former, but I vaguely understand that there is a regret-based analysis where the bias issue I brought up doesn't directly factor in, or may appear in some other guise.  Ideally, it would also be nice to have some clarity on this issue, though it may be too tangential for this submission.