We consider a simple and overarching representation for permutation-invariant functions of sequences (or set functions). Our approach, which we call Janossy pooling, expresses a permutation-invariant function as the average of a permutation-sensitive function applied to all reorderings of the input sequence. This allows us to leverage the rich and mature literature on permutation-sensitive functions to construct novel and flexible permutation-invariant functions. If carried out naively, Janossy pooling can be computationally prohibitive. To allow computational tractability, we consider three kinds of approximations: canonical orderings of sequences, functions with k-order interactions, and stochastic optimization algorithms with random permutations. Our framework unifies a variety of existing work in the literature, and suggests possible modeling and algorithmic extensions. We explore a few in our experiments, which demonstrate improved performance over current state-of-the-art methods. Pooling is a fundamental operation in deep learning architectures BID23 . The role of pooling is to merge a collection of related features into a single, possibly vector-valued, summary feature. A prototypical example is in convolutional neural networks (CNNs) BID22 , where linear activations of features in neighborhoods of image locations are pooled together to construct more abstract features. A more modern example is in neural networks for graphs, where each layer pools together embeddings of neighbors of a vertex to form a new embedding for that vertex, see for instance, BID20 BID0 BID15 Velickovic et al., 2017; BID28 Xu et al., 2018; BID26 BID25 van den Berg et al., 2017; BID12 BID13 Ying et al., 2018; Xu et al., 2019) .A common requirement of a pooling operator is invariance to the ordering of the input features. In CNNs for images, pooling allows invariance to translations and rotations, while for graphs, it allows invariance to graph isomorphisms. Existing pooling operators are mostly limited to predefined heuristics such as max-pool, min-pool, sum, or average. Another desirable characteristic of pooling layers is the ability to take variable-size inputs. This is less important in images, where neighborhoods are usually fixed a priori. However in applications involving graphs, the number of neighbors of different vertices can vary widely. Our goal is to design flexible and learnable pooling operators satisfying these two desiderata.Abstractly, we will view pooling as a permutation-invariant (or symmetric) function acting on finite but arbitrary length sequences h. All elements h i of the sequences are features lying in some space H (which itself could be a high-dimensional Euclidean space R d or some subset thereof). The sequences h are themselves elements of the union of products of the H-space: h ∈ ∞ j=0 H j ≡ H ∪ . Throughout the paper, we will use Π n to represent the set of all permutations of the integers 1 to n, where n will often be clear from the context. In addition, h π , π ∈ Π |h| , will represent a reordering of the elements of a sequence h according to π, where |h| is the length of the sequence h. We will use the double bar superscript f to indicate that a function is permutation-invariant, returning the same value no matter the order of its arguments: f (h) = f (h π ), ∀π ∈ Π |h| . We will use the arrow superscript f to indicate general functions on sequences h which may or may not be permutationinvariant 1 . Functions f without any markers are 'simple' functions, acting on elements in H, scalars or any other argument that is not a sequence of elements in H.Our goal in this paper is to model and learn permutation-sensitive functions f that can be used to construct flexible and learnable permutation-invariant neural networks. A recent step in this direction is work on DeepSets by Zaheer et al. (2017) , who argued for learning permutation-invariant functions through the following composition: DISPLAYFORM0 f (|h|, h; θ (f ) ) = |h| j=1 f (h j ; θ (f ) ) and h ≡ h(x; θ (h) ).Here, (a) x ∈ X is one observation in the training data (X itself may contain variable-length sequences), h ∈ H is the embedding (output) of the data given by the lower layers h : X × R a → H ∪ , a > 0 with parameters θ (h) ∈ R a ; (b) f : H × R b → F is a middle-layer embedding function with parameters θ (f ) ∈ R b , b > 0, and F is the embedding space of f ; and (c) ρ : F × R c → Y is a neural network with parameters θ (ρ) ∈ R c , c > 0, that maps to the final output space Y. Typically H and F are high-dimensional real-valued spaces; Y is often R d in d-dimensional regression problems or the simplex in classification problems. Effectively, the neural network f learns an embedding for each element in H, and given a sequence h, its component embeddings are added together before a second neural network transformation ρ is applied. Note that the function h may be the identity mapping h(x; ·) = x that makes f act directly on the input data. Zaheer et al. (2017) argue that if ρ is a universal function approximator, the above architecture is capable of approximating any symmetric function on h-sequences, which justifies the widespread use of average (sum) pooling to make neural networks permutation-invariant in BID12 , BID15 , BID20 , BID0 , among other works. We note that Zaheer et al. (2017) focus on functions of sets but the work was extended to functions of multisets by Xu et al. (2019) and that Janossy pooling can be used to represent multiset functions. The embedding h is permuted in all |h|! possible ways , and for each permutation h π , f (|h|, h π ; θ (f ) ) is computed. These are summed and passed to a second function ρ(· ; θ (ρ) ) which gives the final permutation-invariant output y(x; θ (ρ) , θ (f ) , θ (h) ); the gray rectangle represents Janossy pooling. We discuss how this can be made computationally tractable .In practice, there is a gap between flexibility and learnability. While the architecture of equations 1 and 2 is a universal approximator to permutationinvariant functions, it does not easily encode structural knowledge about y.Consider trying to learn the permutation-invariant function y(x) = max i,j≤|x| |x i − x j |. With higherorder interactions between the elements of h, the functions f of equation 2 cannot capture any useful intermediate representations towards the final output, with the burden shifted entirely to the function ρ. Learning ρ means learning to undo mixing performed by the summation layer f (|h|, h; θ (f ) ) = |h| j=1 f (h j ; θ (f ) ). As we show in our experiments, in many applications this is too much to ask of ρ.Contributions. We investigate a learnable permutation-invariant pooling layer for variable-size inputs inspired by the Janossy density framework, widely used in the theory of point processes (Daley & Vere-Jones, 2003, Chapter 7) . This approach, which we call Janossy pooling, directly allows the user to model what higher-order dependencies in h are relevant in the pooling. FIG0 summarizes a neural network with a single Janossy pooling layer f (detailed in Definition 2.1 below): given an input embedding h, we apply a learnable (permutation-sensitive) function f to every permutation h π of the input sequence h. These outputs are added together, and fed to the second function ρ. Examples of function f include feedforward and recurrent neural networks (RNNs) . We call the operation used to construct f from f the Janossy pooling. Definition 2.1 gives a more detailed description. We will detail three broad strategies for making this computation tractable and discuss how existing methods can be seen as tractability strategies under the Janossy pooling framework.Thus, we propose a framework and tractability strategies that unify and extend existing methods in the literature. We contribute the following analysis: (a) We show DeepSets (Zaheer et al., 2017) is a special case of Janossy pooling where the function f depends only on the first element of the sequence h π . In the most general form of Janossy pooling (as described above), f depends on its entire input sequence h π . This naturally raises the possibility of intermediate choices of f that allow practitioners to trade between flexibility and tractability. We will show that functions f that depend on their first k arguments of h π allow the Janossy pooling layer to capture up to k-ary dependencies in h. (b) We show Janossy pooling can be used to learn permutation-invariant neural networks y(x) by sampling a random permutation of h during training, and then modeling this permuted sequence using a sequence model such as a recurrent neural network (LSTMs BID17 , GRUs BID6 ) or a vector model such as a feedforward network. We call this permutation-sampling learning algorithm π-SGD (π-Stochastic Gradient Descent). Our analysis explains why this seemingly unsound procedure is theoretically justified, which sheds light on the recent puzzling success of permutation sampling and LSTMs in relational models BID29 BID15 . We show that this property relates to randomized model ensemble techniques. (c) In Zaheer et al. (2017) , the authors describe a connection between DeepSets and infinite de Finetti exchangeabilty . We provide a probabilistic connection between Janossy pooling and finite de Finetti exchangeabilty BID11 . Our approach of permutation-invariance through Janossy pooling unifies a number of existing approaches, and opens up avenues to develop both new methodological extensions, as well as better theory. Our paper focused on two main approaches: k-ary interactions and random permutations. The former involves exact Janossy pooling for a restricted class of functions f . Adding an additional neural network ρ can recover lost model capacity and capture additional higher-order interactions, but hurts tractability and identifiability. Placing restrictions on ρ (convexity, Lipschitz continuity etc.) can allow a more refined control of this trade-off, allowing theoretical and empirical work to shed light on the compromises involved. The second was a random permutation approach which conversely involves no clear trade-offs between model capacity and computation when ρ is made more complex, instead it modifies the relationship between the tractable approximate loss J and the original Janossy loss L. While there is a difference between J and L, we saw the strongest empirical performance coming from this approach in our experiments (shown in the last row of TAB0 ; future work is required to identify which problems π-SGD is best suited for and when its conver-gence criteria are satisfied. Further, a better understanding how the loss-functions L and J relate to each other can shed light on the slightly black-box nature of this procedure. It is also important to understand the relationship between the random permutation optimization to canonical ordering and how one might be used to improve the other. Finally, it is important to apply our methodology to a wider range of applications. Two immediate domains are more challenging tasks involving graphs and tasks involving non-Poisson point processes. is now a summation over only |h|!/(|h| − k)! terms. We can conclude that
We propose Janossy pooling, a method for learning deep permutation invariant functions designed to exploit relationships within the input sequence and tractable inference strategies such as a stochastic optimization procedure we call piSGD
{"src": "scitldr-AIC_train", "paper_id": "BJluy2RcFm"}