Many real-world problems, e.g. object detection, have outputs that are naturally expressed as sets of entities. This creates a challenge for traditional deep neural networks which naturally deal with structured outputs such as vectors, matrices or tensors. We present a novel approach for learning to predict sets with unknown permutation and cardinality using deep neural networks. Specifically, in our formulation we incorporate the permutation as unobservable variable and estimate its distribution during the learning process using alternating optimization. We demonstrate the validity of this new formulation on two relevant vision problems: object detection, for which our formulation outperforms state-of-the-art detectors such as Faster R-CNN and YOLO, and a complex CAPTCHA test, where we observe that, surprisingly, our set based network acquired the ability of mimicking arithmetics without any rules being coded. Deep structured networks such as deep convolutional (CNN) and recurrent (RNN) neural networks have enjoyed great success in many real-world problems, including scene classification BID7 , semantic segmentation BID15 , speech recognition (6), gaming (12; 13) , and image captioning BID6 . However, the current configuration of these networks is restricted to accept and predict structured inputs and outputs such as vectors, matrices, and tensors 1 . If the problem's inputs or/and outputs cannot be modelled in this way, these learning approaches all fail to learn a proper model BID25 . However, many real-world problems are naturally described as unstructured data such as sets (21; 26) . A set is a collection of elements which is invariant under permutation and the size of a set is not fixed in advance. Set learning using deep networks is an emerging field of study that has generated substantial interest very recently (20; 21; 23; 26) .Consider the task of object detection as an example. Given a structured input, e.g. an image as a tensor, the goal is to predict a set of orderless locations, e.g. bounding boxes, from an unknown and varying number of objects. Therefore , the output of this problem can be properly modelled as a set of entities. However, a deep learning network cannot be simply trained to learn a proper model in order to directly predict unfixed number of orderless locations. Existing approaches formulate this problem using as a pre-defined and fixed-sized grid (18; 17) or anchor boxes BID18 representing all possible locations and scales of the objects. Then, each location and scale is scored independently to contain an object or not. The final output is generated heuristically by a discretization process such as non-maximum suppression (NMS), which is not part of the learning process. Therefore , their performance is hindered by this heuristic procedure. To this end, the current solutions can only deal with moderate object occlusion. We argue that object detection problem can be properly formulated as a set prediction problem, where a deep learning network is trained to output a set of locations without any heuristic.This shortcoming concerns not only object detection but also all problems where a set of instances (as input or/and output) is involved, e.g. a set of topics or concepts in documents (3), segmentation of object instances BID9 and a set of trajectories in multiple object tracking BID1 . In contrast to problems such as classification, where the order of categories or the labels can be fixed during the training process and the output can be well represented by a fixed-sized vector, the instances are often unfixed in number and orderless. More precisely , it does not matter in which order the instances are labelled and these labels do not relate the instances to a specific visual category. To this end, training a deep network to predict instances seems to be non-trivial. We believe that set learning is a principled solution to all of these problems.In this paper, we present a novel approach for learning to deal with sets using deep learning. More clearly, in the presented model, we assume that the input (the observation) is still structured, e.g. an image, but the annotated output is available as a set. Our approach is inspired by a recent work on set learning using deep neural networks BID20 . Although the work in BID20 handles orderless outputs in the testing/inference step, it requires ordered outputs in the learning step. This is a significant limitation, because in many applications, such as object detection, the outputs are naturally not ordered. When that happens, the approach in BID20 cannot learn a sensible model (see Appendix for the experiment). In this paper, we propose a complete set prediction formulation to address this limitation. This provides a potential to tackle many more problems compared to BID20 .The main contribution of the paper is summarised as follows:1. We propose a principled formulation for neural networks to deal with arbitrary sets with unknown permutation and cardinality as available annotated outputs. This makes a neural network, for the first time, able to truly handle orderless outputs at both training and test time. 2. Additionally, our formulation allows us to learn the distribution over the unobservable permutation variables, which can be used to identify the most likely orders of the set. In some applications, there may exist one or several dominant orders, which are unknown from the annotations. 3. For the first time, we reformulate object detection as a set prediction problem, where a deep network is learned end-to-end to generate the detection outputs with no heuristic involved. We outperform the state-of-the art object detectors , such as Faster R-CNN and YOLO v2, on both simulated and real data with high level of occlusions. 4. We also demonstrate the applicability of our framework algorithm for a complex CAPTCHA test which can be formulated as a set prediction problem. In this paper, we proposed a framework for predicting sets with unknown cardinality and permutation using convolutional neural networks. In our formulation, set permutation is considered as an unobservable variable and its distribution is estimated iteratively using alternating optimization. We have shown that object detection can be elegantly formulated as a set prediction problem, where a deep network can be learned end-to-end to generate the detection outputs with no heuristic involved. We have demonstrated that the approach is able to outperform the state-of-the art object detections on real data including highly occluded objects. We have also shown the effectiveness of our set learning approach on solving a complex logical CAPTCHA test, where the aim is to de-sum a digit into its components by selecting a set of digits with an equal sum value.The main limitation of the current framework is that the number of possible permutations exponentially grows with the maximum set size (cardinality). Therefore, applying it to large-scale problem is not straightforward and requires an accurate approximation for estimating a subset of dominant permutations. In future, we plan to overcome this limitation by learning the subset of significant permutations to target real-world large-scale problems such as multiple object tracking.
We present a novel approach for learning to predict sets with unknown permutation and cardinality using feed-forward deep neural networks. A formulation to learn the distribution over unobservable permutation variables based on deep networks for the set prediction problem.