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. A relatively less studied problem in machine learning, particularly supervised learning, is the problem of multiset prediction. The goal of this problem is to learn a mapping from an arbitrary input to a multiset 1 of items. This problem appears in a variety of contexts. For instance, in the context of high-energy physics, one of the important problems in a particle physics data analysis is to count how many physics objects, such as electrons, muons, photons, taus, and jets, are in a collision event BID4 . In computer vision, automatic alt-text, such as the one available on Facebook, 2 is a representative example of multiset prediction BID16 BID9 . 3 In multiset prediction, a learner is presented with an arbitrary input and the associated multiset of items. It is assumed that there is no predefined order among the items, and that there are no further annotations containing information about the relationship between the input and each of the items in the multiset. These properties make the problem of multiset prediction unique from other wellstudied problems. It is different from sequence prediction, because there is no known order among the items. It is not a ranking problem, since each item may appear more than once. It cannot be transformed into classification, because the number of possible multisets grows exponentially with respect to the maximum multiset size.In this paper, we view multiset prediction as a sequential decision making process. Under this view, the problem reduces to finding a policy that sequentially predicts one item at a time, while the outcome is still evaluated based on the aggregate multiset of the predicted items. We first propose an oracle policy that assigns non-zero probabilities only to prediction sequences that result exactly in the target, ground-truth multiset given an input. This oracle is optimal in the sense that its prediction never decreases the precision and recall regardless of previous predictions. That is, its decision is optimal in any state (i.e., prediction prefix). We then propose a novel multiset loss which minimizes the KL divergence between the oracle policy and a parametrized policy at every point in a decision trajectory of the parametrized policy. 1 A set that allows multiple instances, e.g. {x, y, x}. See Appendix A for a detailed definition. https://newsroom.fb.com/news/2016/04/using-artificial-intelligenceto-help-blind-people-see-facebook/ 3 We however note that such a multiset prediction problem in computer vision can also be solved as segmentation, if fine-grained annotation is available. See, e.g., BID6 .We compare the proposed multiset loss against an extensive set of baselines. They include a sequential loss with an arbitrary rank function, sequential loss with an input-dependent rank function, and an aggregated distribution matching loss and its one-step variant. We also test policy gradient, as was done by BID16 recently for multiset prediction. Our evaluation is conducted on two sets of datasets with varying difficulties and properties. According to the experiments, we find that the proposed multiset loss outperforms all the other loss functions.The paper is structured as follows. We first define multiset prediction at the beginning of Section 2, and compare it to existing problems in supervised learning in 2.1. Then we propose the multiset loss in Section 2.2, followed by alternative baseline losses in Section 3. The multiset loss and baselines are then empirically evaluated in Section 4. We have extensively investigated the problem of multiset prediction in this paper. We rigorously defined the problem, and proposed to approach it from the perspective of sequential decision making. In doing so, an oracle policy was defined and shown to be optimal, and a new loss function, called multiset loss, was introduced as a means to train a parametrized policy for multiset prediction. The experiments on two families of datasets, MNIST Multi variants and MS COCO variants, have revealed the effectiveness of the proposed loss function over other loss functions including reinforcement learning, sequence, and aggregated distribution matching loss functions. The success of the proposed multiset loss brings in new opportunities of applying machine learning to various new domains, including high-energy physics.Precision Precision gives the ratio of correctly predicted elements to the number of predicted elements. Specifically, letŶ = (C, µŶ ), Y = (C, µ Y ) be multisets. Then DISPLAYFORM0 The summation and membership are done by enumerating the multiset. For example, the multisetŝ Y = {a, a, b} and Y = {a, b} are enumerated asŶ = {a DISPLAYFORM1 Formally, precision can be defined as DISPLAYFORM2 where the summation is now over the ground set C. Intuitively, precision decreases by 1 |Ŷ| each time an extra class label is predicted.Recall Recall gives the ratio of correctly predicted elements to the number of ground-truth elements. Recall is defined analogously to precision, as: Similarly, we start with the definition of the recall: DISPLAYFORM3 Rec(ŷ <t , Y) = y∈ŷ<t I y∈Y |Y| .turned into a conditional distribution over the next item after affine transformation followed by a softmax function. When the one-step variant of aggregated distribution matching is used, we skip the convolutional LSTM layers, i.e., c = DISPLAYFORM4 See Fig. 2 for the graphical illustration of the entire network. See TAB4 for the details of the network for each dataset. conv 5 × 5 max-pool 2 × 2 feat 10 81 conv 3 × 3 feat 32 conv 5 × 5 max-pool 2 × 2 feat 10 conv 3 × 3 feat 32 conv 5 × 5 max-pool 2 × 2 feat 32
We study the problem of multiset prediction and propose a novel multiset loss function, providing analysis and empirical evidence that demonstrates its effectiveness.
{"src": "scitldr-AIC_train", "paper_id": "Syjha0gAZ"}