summaries: The authors introduce a method to learn to permute sets end-to-end. They define the cost of a permutation as the sum of pairwise costs induced by the permutation, where the pairwise costs are learned. Permutations are made differentiable by relaxing them to doubly stochastic matrices which are approximated with the Sinkhorn operator. In the forward pass of the algorithm, a good permutation (ie one with low cost) is obtained with a few steps of gradient descent (the forward pass itself contains an optimization procedure). This permutation is then either used directly as the output of the algorithm or is used to permute the original inputs and feed the permuted sequence to another module (such as an RNN or a CNN). The method can easily be adapted to other structures such as lattices by considering row-wise and column-wise pairwise relations.

summaries: This paper proposed an interesting idea of learning representations of sets by permutation optimizations. Through learning a permutation of the elements of a set, the proposed algorithm can learn a permutation-invariant representation of that set. To deal with the underlying difficult combinatorial optimization problem, the authors proposed to relax the optimization constraints and instead optimize over the set of doubly-stochastic matrices with reparameterization using the Sinkhorn operator. The cost function of this optimization is related to a pairwise ordering cost, which compares the order for each pair of the elements.

abstractText: Representations of sets are challenging to learn because operations on sets should be permutation-invariant. To this end, we propose a Permutation-Optimisation module that learns how to permute a set end-to-end. The permuted set can be further processed to learn a permutation-invariant representation of that set, avoiding a bottleneck in traditional set models. We demonstrate our model’s ability to learn permutations and set representations with either explicit or implicit supervision on four datasets, on which we achieve state-of-the-art results: number sorting, image mosaics, classification from image mosaics, and visual question answering.

authors:
Ryan Prescott Adams
Richard S. Zemel

title: Ranking via sinkhorn propagation

authors:
Brandon Amos
J. Zico Kolter

title: Optnet: Differentiable optimization as a layer in neural networks

venue: In ICML,

authors:
Peter Anderson
Xiaodong He
Chris Buehler
Damien Teney
Mark Johnson
Stephen Gould
Lei Zhang

title: Bottom-up and top-down attention for image captioning and visual question answering

authors:
Stanislaw Antol
Aishwarya Agrawal
Jiasen Lu
Margaret Mitchell
Dhruv Batra
C. Lawrence Zitnick
Devi Parikh

title: VQA: Visual Question Answering

venue: In ICCV,

authors:
David Belanger
Bishan Yang
Andrew. McCallum

title: End-to-end learning for structured prediction energy networks

authors:
Chris Burges
Tal Shaked
Erin Renshaw
Ari Lazier
Matt Deeds
Nicole Hamilton
Greg Hullender

title: Learning to rank using gradient-descent

authors:
Irène Charon
Olivier Hudry

title: A survey on the linear ordering problem for weighted or unweighted tournaments

authors:
Rodrigo Santa Cruz
Basura Fernando
Anoop Cherian
Stephen Gould

title: DeepPermNet: Visual Permutation Learning

title: Generic Methods for Optimization-Based Modeling

venue: In AISTATS,

authors:
Fajwel Fogel
Rodolphe Jenatton
Francis Bach
Alexandre D

title: Aspremont. Convex relaxations for permutation problems

venue: In NIPS,

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

authors:
Yash Goyal
Tejas Khot
Douglas Summers-Stay
Dhruv Batra
Devi Parikh

title: Making the V in VQA matter: Elevating the role of image understanding in Visual Question Answering

authors:
Jin-Hwa Kim
Jaehyun Jun
Byoung-Tak Zhang

title: Bilinear attention networks

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In ICLR,

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Truc Le
Ye Duan

title: PointGrid: A Deep Network for 3D Shape Understanding

authors:
Gonzalo Mena
David Belanger
Scott Linderman
Jasper Snoek

title: Learning Latent Permutations with Gumbel-Sinkhorn Networks

authors:
Ryan L. Murphy
Balasubramaniam Srinivasan
Vinayak Rao
Bruno Ribeiro

title: Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs

authors:
Mehdi Noroozi
Paolo Favaro

title: Unsupervised learning of visual representations by solving jigsaw puzzles

venue: In ECCV,

authors:
Panos M. Pardalos
Stephen A. Vavasis

title: Quadratic programming with one negative eigenvalue is NP-hard

venue: J. Global Optimization,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

venue: NIPS-W,

authors:
Charles R. Qi
Hao Su
Kaichun Mo
Leonidas J. Guibas

title: PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation

authors:
Adam Santoro
David Raposo
David G Barrett
Mateusz Malinowski
Razvan Pascanu
Peter Battaglia
Tim Lillicrap

title: A simple neural network module for relational reasoning

authors:
Aliaksei Severyn
Alessandro Moschitti

title: Learning to rank short text pairs with convolutional deep neural networks

venue: In SIGIR,

title: A relationship between arbitrary positive matrices and doubly stochastic matrices

authors:
Veselin Stoyanov
Alexander Ropson
Jason Eisner

title: Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structureeneric methods for optimization-based modelin

authors:
Oriol Vinyals
Samy Bengio
Manjunath Kudlur

title: Order Matters: Sequence to sequence for sets

authors:
Yan Zhang
Jonathon Hare
Adam Prügel-Bennett

title: Learning to count objects in natural images for visual question answering

venue: Unlike Mena et al

heading: 1 INTRODUCTION

text:
Consider a task where each input sample is a set of feature vectors with each feature vector describing an object in an image (for example: person, table, cat). Because there is no a priori ordering of these objects, it is important that the model is invariant to the order that the elements appear in the set. However, this puts restrictions on what can be learned efficiently. The typical approach is to compose elementwise operations with permutation-invariant reduction operations, such as summing (Zaheer et al., 2017) or taking the maximum (Qi et al., 2017) over the whole set. Since the reduction operator compresses a set of any size down to a single descriptor, this can be a significant bottleneck in what information about the set can be represented efficiently (Qi et al., 2017; Le & Duan, 2018; Murphy et al., 2019).
We take an alternative approach based on an idea explored in Vinyals et al. (2015a), where they find that some permutations of sets allow for easier learning on a task than others. They do this by ordering the set elements in some predetermined way and feeding the resulting sequence into a recurrent neural network. For instance, it makes sense that if the task is to output the top-n numbers from a set of numbers, it is useful if the input is already sorted in descending order before being fed into an RNN. This approach leverages the representational capabilities of traditional sequential models such as LSTMs, but requires some prior knowledge of what order might be useful.
Our idea is to learn such a permutation purely from data without requiring a priori knowledge (section 2). The key aspect is to turn a set into a sequence in a way that is both permutation-invariant, as well as differentiable so that it is learnable. Our main contribution is a Permutation-Optimisation (PO) module that satisfies these requirements: it optimises a permutation in the forward pass of a neural network using pairwise comparisons. By feeding the resulting sequence into a traditional model such as an LSTM, we can learn a flexible, permutation-invariant representation of the set while avoiding the bottleneck that a simple reduction operator would introduce. Techniques used in our model may also be applicable to other set problems where permutation-invariance is desired, building on the literature of approaches to dealing with permutation-invariance (section 3).
In four different experiments, we show improvements over existing methods (section 4). The former two tasks measure the ability to learn a particular permutation as target: number sorting and image mosaics. We achieve state-of-the-art performance with our model, which shows that our method is suitable for representing permutations in general. The latter two tasks test whether a model can learn to solve a task that requires it to come up with a suitable permutation implicitly: classification from image mosaics and visual question answering. We provide no supervision of what the permutation should be; the model has to learn by itself what permutation is most useful for the task at hand.
Here, our model also beats the existing models and we improve the performance of a state-of-the-art model in VQA with it. This shows that our PO module is able to learn good permutation-invariant representations of sets using our approach.

heading: 2 PERMUTATION-OPTIMISATION MODULE

text:
We will now describe a differentiable, and thus learnable model to turn an unordered set {xi}N with feature vectors as elements into an ordered sequence of these feature vectors. An overview of the algorithm is shown in Figure 1 and pseudo-code is available in Appendix A. The input set is represented as a matrix X = [x1, . . . ,xN ]T with the feature vectors xi as rows in some arbitrary order. In the algorithm, it is important to not rely on the arbitrary order so that X is correctly treated as a set. The goal is then to learn a permutation matrix P such that when permuting the rows of the input through Y = PX , the output is ordered correctly according to the task at hand. When an entry Pik takes the value 1, it can be understood as assigning the ith element to the kth position in the output.
Our main idea is to first relate pairs of elements through an ordering cost, parametrised with a neural network. This pairwise cost tells us whether an element i should preferably be placed before or after element j in the output sequence. Using this, we can define a total cost that measures how good a given permutation is (subsection 2.1). The second idea is to optimise this total cost in each forward pass of the module (subsection 2.2). By minimising the total cost of a permutation, we improve the quality of a permutation with respect to the current ordering costs. Crucially, the ordering cost function – and thus also the total cost function – is learned. In doing so, the module is able to learn how to generate a permutation as is desired.
In order for this to work, it is important that the optimisation process itself is differentiable so that the ordering cost is learnable. Because permutations are inherently discrete objects, a continuous relaxation of permutations is necessary. For optimisation, we perform gradient descent on the total cost for a fixed number of steps and unroll the iteration, similar to how recurrent neural networks are unrolled to perform backpropagation-through-time. Because the inner gradient (total cost differentiated with respect to permutation) is itself differentiable with respect to the ordering cost, the whole model is kept differentiable and we can train it with a standard supervised learning loss.
Note that as long as the ordering cost is computed appropriately (subsection 2.3), all operations used turn out to be permutation-invariant. Thus, we have a model that respects the symmetries of sets while producing an output without those symmetries: a sequence. This can be naturally extended to outputs where the target is not a sequence, but grids and lattices (subsection 2.4).

heading: 2.1 TOTAL COST FUNCTION

text:
The total cost function measures the quality of a given permutation and should be lower for better permutations. Because this is the function that will be optimised, it is important to understand what it expresses precisely.
The main ingredient for the total cost of a permutation is the pairwise ordering cost (details in subsection 2.3). By computing it for all pairs, we obtain a cost matrix C where the entry Cij represents the ordering cost between i and j: the cost of placing element i anywhere before j in the output sequence. An important constraint that we put on C is that Cij = −Cji. In other words, if one ordering of i and j is “good” (negative cost), then the opposite ordering obtained by swapping them is “bad” (positive cost). Additionally, this constraint means that Cii = 0. This makes sure that two very similar feature vectors in the input will be similarly ordered in the output because their pairwise cost goes to 0.
In this paper we use a straightforward definition of the total cost function: a sum of the ordering costs over all pairs of elements i and j. When considering the pair i and j, if the permutation maps i to be before j in the output sequence, this cost is simply Cij . Vice versa, if the permutation maps i to be after j in the output sequence, the cost has to be flipped to Cji. To express this idea, we define the total cost c : RN×N 7→ R of a permutation P as:
c(P ) = ∑ ij Cij ∑ k Pik( ∑ k′>k Pjk′ − ∑ k′<k Pjk′) (1)
This can be understood as follows: If the permutation assigns element i to position u (so Piu = 1) and element j to position v (so Pjv = 1), the sums over k and k′ simplify to 1 when v > u and −1 when v < u; permutation matrices are binary and only have one 1 in any row and column, so all other terms in the sums are 0. That means that the term for each i and j becomes Cij when v > u and −Cij = Cji when v < u, which matches what we described previously.

heading: 2.2 OPTIMISATION PROBLEM

text:
Now that we can compute the total cost of a permutation, we want to optimise this cost with respect to a permutation. After including the constraints to enforce that P is a valid permutation matrix, we obtain the following optimisation problem:
minimize P c(P )
subject to ∀i, k : Pik ∈ {0, 1}, ∀i : ∑ k Pik = 1, ∑ k Pki = 1
(2)
Optimisation over P directly is difficult due to the discrete and combinatorial nature of permutations. To make optimisation feasible, a common relaxation is to replace the constraint that Pik ∈ {0, 1} with Pik ∈ [0, 1] (Fogel et al., 2013). With this change, the feasible set for P expands to the set of doublystochastic matrices, known as the Birkhoff or assignment polytope. Rather than hard permutations, we now have soft assignments of elements to positions, analogous to the latent assignments when fitting a mixture of Gaussians model using Expectation-Maximisation.
Note that we do not need to change our total cost function after this relaxation. Instead of discretely flipping the sign of Cij depending on whether element i comes before j or not, the sums over k and k′ give us a weight for each Cij that is based on how strongly i and j are assigned to positions. This weight is positive when i is on average assigned to earlier positions than j and negative vice versa.
In order to perform optimisation of the cost under our constraints, we reparametrise P with the Sinkhorn operator S from Adams & Zemel (2011) (defined in Appendix B) so that the constraints are always satisfied. We found this to lead to better solutions than projected gradient descent in initial
experiments. After first exponentiating all entries of a matrix, S repeatedly normalises all rows, then all columns of the matrix to sum to 1, which converges to a doubly-stochastic matrix in the limit.
P = S(P̃ ) (3)
This ensures that P is always approximately a doubly-stochastic matrix. P̃ can be thought of as the unnormalised permutation while P is the normalised permutation. By changing our optimisation to minimise P̃ instead of P directly, all constraints are always satisfied and we can simplify the optimisation problem to minP̃ c(P ) without any constraints.
It is now straightforward to optimise P̃ with standard gradient descent. First, we compute the gradient:
∂c(P )
∂Ppq = 2 ∑ j Cpj( ∑ k′>q Pjk′ − ∑ k′<q Pjk′) (4)
∂c(P )
∂P̃pq =
∂P ∂P̃pq · ∂c(P ) ∂P
(5)
From equation 4, it becomes clear that this gradient is itself differentiable with respect to the ordering cost Cij , which allows it to be learned. In practice, both ∂c(P )/∂P̃ as well as ∂[∂c(P )/∂P̃ ]/∂C can be computed with automatic differentiation. However, some implementations of automatic differentiation require the computation of c(P ) which we do not use. In this case, implementing ∂c(P )/∂P̃ explicitly can be more efficient. Also notice that if we define Bjq = ∑ k′>q Pjk′ −∑
k′<q Pjk′ , equation 4 is just the matrix multiplication CB and is thus efficiently computable.
For optimisation, P has to be initialised in a permutation-invariant way to preserve permutationinvariance of the algorithm. In this paper, we consider a uniform initialisation so that all Pik = 1/N (PO-U model, left) and an initialisation that linearly assigns (Mena et al., 2018) each element to each position (PO-LA model, right).
P̃ (0) ik = 0 or P̃ (0) ik = wkxi (6)
where wk is a different weight vector for each position k. Then, we perform gradient descent for a fixed number of steps T . The iterative update using the gradient and a (learnable) step size η converges to the optimised permutation P (T ):
P̃ (t+1) = P̃ (t) − η ∂c(P (t))
∂P (t) (7)
One peculiarity of this is that we update P̃ with the gradient of the normalised permutation P , not of the unnormalised permutation P̃ as normal. In other words, we do gradient descent on P̃ but in equation 5 we set ∂Puv/∂P̃pq = 1 when u = p, v = q, and 0 everywhere else. We found that this results in significantly better permutations experimentally; we believe that this is because ∂P /∂P̃ vanishes too quickly from the Sinkhorn normalisation, which biases P away from good permutation matrices wherein all entries are close to 0 and 1 (Appendix D).
The runtime of this algorithm is dominated by the computation of gradients of c(P ), which involves a matrix multiplication of two N ×N matrices. In total, the time complexity of this algorithm is T times the complexity of this matrix multiplication, which is Θ(N3) in practice. We found that typically, small values for T such as 4 are enough to get good permutations.

heading: 2.3 ORDERING COST FUNCTION

text:
The ordering cost Cij is used in the total cost and tells us what the pairwise cost for placing i before j should be. The key property to enforce is that the function F that produces the entries of C is anti-symmetric (F (xi,xj) = −F (xj ,xi)). A simple way to achieve this is to define F as:
F (xi,xj) = f(xi,xj)− f(xj ,xi) (8)
We can then use a small neural network for f to obtain a learnable F that is always anti-symmetric.
Lastly, C is normalised to have unit Frobenius norm. This results in simply scaling the total cost obtained, but it also decouples the scale of the outputs of F from the step size parameter η to make optimisation more stable at inference time. C is then defined as:
C̃ij = F (xi,xj) (9)
Cij = C̃ij/‖C̃‖F (10)

heading: 2.4 EXTENDING PERMUTATIONS TO LATTICES

text: In some tasks, it may be natural to permute the set into a lattice structure instead of a sequence. For example, if it is known that the set contains parts of an image, it makes sense to arrange these parts back to an image by using a regular grid. We can straightforwardly adapt our model to this by considering each row and column of the target grid as an individual permutation problem. The total cost of an assignment to a grid is the sum of the total costs over all individual rows and columns of the grid. The gradient of this new cost is then the sum of the gradients of these individual problems. This results in a model that considers both row-wise and column-wise pairwise relations when permuting a set of inputs into a grid structure, and more generally, into a lattice structure.

heading: 3 RELATED WORK

text:
The most relevant work to ours is the inspiring study by Mena et al. (2018), where they discuss the reparametrisation that we use and propose a model that can also learn permutations implicitly in principle. Their model uses a simple elementwise linear map from each of the N elements of the set to the N positions, normalised by the Sinkhorn operator. This can be understood as classifying each element individually into one of the N classes corresponding to positions, then normalising the predictions so that each class only occurs once within this set. However, processing the elements individually means that their model does not take relations between elements into account properly; elements are placed in absolute positions, not relative to other elements. Our model differs from theirs by considering pairwise relations when creating the permutation. By basing the cost function on pairwise comparisons, it is able to order elements such that local relations in the output are taken into account. We believe that this is important for learning from permutations implicitly, because networks such as CNNs and RNNs rely on local ordering more than absolute positioning of elements. It also allows our model to process variable-sized sets, which their model is not able to do.
Our work is closely related to the set function literature, where the main constraint is invariance to ordering of the set. While it is always possible to simply train using as many permutations of a set as possible, using a model that is naturally permutation-invariant increases learning and generalisation capabilities through the correct inductive bias in the model. There are some similarities with relation networks (Santoro et al., 2017) in considering all pairwise relations between elements as in our pairwise ordering function. However, they sum over all non-linearly transformed pairs, which can lead to the bottleneck we mention in section 1. Meanwhile, by using an RNN on the output of our model, our approach can encode a richer class of functions: it can still learn to simply sum the inputs, but it can also learn more complex functions where the learned order between elements is taken into account. The concurrent work in (Murphy et al., 2019) discusses various approximations of averaging the output of a neural network over all possible permutations, with our method falling under their categorisation of a learned canonical input ordering. Our model is also relevant to neural networks operating on graphs such as graph-convolutional networks (Kipf & Welling, 2017). Typically, a set
function is applied to the set of neighbours for each node, with which the state of the node is updated. Our module combined with an RNN is thus an alternative set function to perform this state update with.
Noroozi & Favaro (2016) and Cruz et al. (2017) show that it is possible to use permutation learning for representation learning in a self-supervised setting. The model in Cruz et al. (2017) is very similar to Mena et al. (2018), including use of a Sinkhorn operator, but they perform significantly more processing on images with a large CNN (AlexNet) beforehand with the main goal of learning good representations for that CNN. We instead focus on using the permuted set itself for representation learning in a supervised setting.
We are not the first to explore the usefulness of using optimisation in the forward pass of a neural network (for example, Stoyanov et al. (2011); Domke (2012); Belanger et al. (2017)). However, we believe that we are the first to show the potential of optimisation for processing sets because – with an appropriate cost function – it is able to preserve permutation-invariance. In OptNet (Amos & Kolter, 2017), exact solutions to convex quadratic programs are found in a differentiable way through various techniques. Unfortunately, our quadratic program is non-convex (Appendix E), which makes finding an optimal solution possibly NP-hard (Pardalos & Vavasis, 1991). We thus fall back to the simpler approach of gradient descent on the reparametrised problem to obtain a non-optimal, but reasonable solution.
Note that our work differs from learning to rank approaches such as Burges et al. (2005) and Severyn & Moschitti (2015), as there the end goal is the permutation itself. This usually requires supervision on what the target permutation should be, producing a permutation with hard assignments at the end. We require our model to produce soft assignments so that it is easily differentiable, since the main goal is not the permutation itself, but processing it further to form a representation of the set being permuted. This means that other approaches that produce hard assignments such as Ptr-Net (Vinyals et al., 2015b) are also unsuitable for implicitly learning permutations, although using a variational approximation through Mena et al. (2018) to obtain a differentiable permutation with hard assignments is a promising direction to explore for the future. Due to the lack of differentiability, existing literature on solving minimum feedback arc set problems (Charon & Hudry, 2007) can not be easily used for set representation learning either.

heading: 4 EXPERIMENTS

text: Throughout the text, we will refer to our model with uniform assignment as PO-U, with linear assignment initialisation as PO-LA, and the model from Mena et al. (2018) as LinAssign. We perform a qualitative analysis of what comparisons are learned in Appendix C. Precise experimental details can be found in Appendix F and our implementation for all experiments is available at https: //github.com/Cyanogenoid/perm-optim for full reproducibility. Some additional results including example image mosaic outputs can be found in Appendix G.

heading: 4.1 SORTING NUMBERS

text:
We start with the toy task of turning a set of random unsorted numbers into a sorted list. For this problem, we train with fixed-size sets of numbers drawn uniformly from the interval [0, 1] and evaluate on different intervals to determine generalisation ability (for example: [0, 1], [0, 1000], [1000, 1001]). We use the correctly ordered sequence as training target and minimise the mean squared error. Following Mena et al. (2018), during evaluation we use the Hungarian algorithm for solving a linear assignment problem with −P as the assignment costs. This is done to obtain a permutation with hard assignments from our soft permutation.
Our PO-U model is able to sort all sizes of sets that we tried – 5 to 1024 numbers – perfectly, including generalising to all the different evaluation intervals without any mistakes. This is in contrast to all existing end-to-end learning-based approaches such as Mena et al. (2018), which starts to make mistakes on [0, 1] at 120 numbers and no longer generalises to sets drawn from [1000, 1001] at 80 numbers. Vinyals et al. (2015a) already starts making mistakes on 5 numbers. Our stark improvement over existing results is evidence that the inductive biases due to the learned pairwise comparisons in our model are suitable for learning permutations, at least for this particular toy problem. In subsection C.1, we investigate what it learns that allows it to generalise this well.

heading: 4.2 RE-ASSEMBLING IMAGE MOSAICS

text:
As a second task, we consider a problem where the model is given images that are split into n× n equal-size tiles and the goal is to re-arrange this set of tiles back into the original image. We take these images from either MNIST, CIFAR10, or a version of ImageNet with images resized down to 64× 64 pixels. For this task, we use the alternative cost function described in subsection 2.4 to arrange the tiles into a grid rather than a sequence: this lets our model take relations within rows and columns into account. Again, we minimise the mean squared error to the correctly permuted image and use the Hungarian algorithm during evaluation, matching the experimental setup in Mena et al. (2018). Due to the lack of reference implementation of their model for this experiment, we use our own implementation of their model, which we verified to reproduce their MNIST results closely. Unlike them, we decide to not arbitrarily upscale MNIST images to get improved results for all models.
The mean squared errors for the different image datasets and different number of tiles an image is split into are shown in Table 1. First, notice that in essentially all cases, our model with linear assignment initialisation (PO-LA) performs best, often significantly so. On the two more complex datasets CIFAR10 and ImageNet, this is followed by our PO-U model, then the LinAssign model. We analyse what types of comparisons PO-U learns in subsection C.2.
On MNIST, LinAssign performs better than PO-U on higher tile counts because images are always centred on the object of interest. That means that many tiles only contain the background and end up completely blank; these tiles can be more easily assigned to the borders of the image by the LinAssign model than our PO-U model because the absolute position is much more important than the relative positioning to other tiles. This also points towards an issue for these cases in our cost function: because two tiles that have the same contents are treated the same by our model, it is unable to place one blank tile on one side of the image and another blank tile on the opposite side, as this would require treating the two tiles differently. This issue with backgrounds is also present on CIFAR10 to a lesser extent: notice how for the 3× 3 case, the error of PO-U is much closer to LinAssign on CIFAR10 than on ImageNet, where PO-U is much better comparatively. This shows that the PO-U model is more suitable for more complex images when relative positioning matters more, and that PO-LA is able to combine the best of both methods.

heading: 4.3 IMPLICIT PERMUTATIONS THROUGH IMAGE CLASSIFICATION

text:
We now turn to tasks where the goal is not producing the permutation itself, but learning a suitable permutation for a different task. For these tasks, we do not provide explicit supervision on what the permutation should be; an appropriate permutation is learned implicitly while learning to solve another task.
As the dataset, we use a straightforward modification of the image mosaic task. The image tiles are assigned to positions on a grid as before, which are then concatenated into a full image. This image is fed into a standard image classifier (ResNet-18 (He et al., 2015)) which is trained with the usual cross-entropy loss to classify the image. The idea is that the network has to learn some permutation of the image tiles so that the classifier can classify it accurately. This is not necessarily the permutation that restores the original image faithfully.
One issue with this set-up we observed is that with big tiles, it is easy for a CNN to ignore the artefacts on the tile boundaries, which means that simply permuting the tiles randomly gets to almost the same test accuracy as using the original image. To prevent the network from avoiding to solve the task, we first pre-train the CNN on the original dataset without permuting the image tiles. Once it is fully trained, we freeze the weights of this CNN and train only the permutation mechanism.
We show our results in Table 2. Generally, a similar trend to the image mosaic task with explicit supervision can be seen. Our PO-LA model usually performs best, although for ImageNet PO-U is consistently better. This is evidence that for more complex images, the benefits of linear assignment decrease (and can actually detract from the task in the case of ImageNet) and the importance of the optimisation process in our model increases. With higher number of tiles on MNIST, even though PO-U does not perform well, PO-LA is clearly superior to only using LinAssign. This is again due to the fully black tiles not being able to be sorted well by the cost function with uniform initialisation.

heading: 4.4 VISUAL QUESTION ANSWERING

text:
As the last task, we consider the much more complex problem of visual question answering (VQA): answering questions about images. We use the VQA v2 dataset (Antol et al., 2015; Goyal et al., 2017), which in total contains around 1 million questions about 200,000 images from MS-COCO with 6.5 million human-provided answers available for training. We use bottom-up attention features (Anderson et al., 2018) as representation for objects in the image, which for each image gives us a set (size varying from 10 to 100 per image) of bounding boxes and the associated feature vector that encodes the contents of the bounding box. These object proposals have no natural ordering a priori.
We use the state-of-the-art BAN model (Kim et al., 2018) as a baseline and perform a straightforward modification to it to incorporate our module. For each element in the set of object proposals, we concatenate the bounding box coordinates, features, and the attention value that the baseline model generates. Our model learns to permute this set into a sequence, which is fed into an LSTM. We take the last cell state of the LSTM to be the representation of the set, which is fed back into the baseline model. This is done for each of the eight attention glimpses in the BAN model. We include another baseline model (BAN + LSTM) that skips the permutation learning, directly processing the set with the LSTM.
Our results on the validation set of VQA v2 are shown in Table 3. We improve on the overall performance of the state-of-the-art model by 0.37% – a significant improvement for this dataset – with 0.27% of this improvement coming from the learned permutation. This shows that there is a substantial benefit to learning an appropriate permutation through our model in order to learn better
set representations. Our model significantly improves on the number category, despite the inclusion of a counting module (Zhang et al., 2018) specifically targeted at number questions in the baseline. This is evidence that the representation learned through the permutation is non-trivial. Note that the improvement through our model is not simply due to increased model size and computation: Kim et al. (2018) found that significantly increasing BAN model size, increasing computation time similar in scale to including our model, does not yield any further gains.

heading: 5 DISCUSSION

text:
In this paper, we discussed our Permutation-Optimisation module to learn permutations of sets using an optimisation-based approach. In various experiments, we verified the merit of our approach for learning permutations and, from them, set representations. We think that the optimisation-based approach to processing sets is currently underappreciated and hope that the techniques and results in this paper will inspire new algorithms for processing sets in a permutation-invariant manner. Of course, there is plenty of work to be done. For example, we have only explored one possible function for the total cost; different functions capturing different properties may be used. The main drawback of our approach is the cubic time complexity in the set size compared to the quadratic complexity of Mena et al. (2018), which limits our model to tasks where the number of elements is relatively small. While this is acceptable on the real-world dataset that we used – VQA with up to 100 object proposals per image – with only a 30% increase in computation time, our method does not scale to the much larger set sizes encountered in domains such as point cloud classification. Improvements in the optimisation algorithm may improve this situation, perhaps through a divide-and-conquer approach.
We believe that going beyond tensors as basic data structures is important for enabling higher-level reasoning. As a fundamental mathematical object, sets are a natural step forward from tensors for modelling unordered collections. The property of permutation invariance lends itself to greater abstraction by allowing data that has no obvious ordering to be processed, and we took a step towards this by learning an ordering that existing neural networks are able to take advantage of.

heading: A PSEUDOCODE OF ALGORITHM

text: Algorithm 1 Forward pass of permutation-optimisation algorithm 1: Input: X ∈ RN×M with xi as rows in arbitrary order 2: Learnable parameters: weights that parametrise F , step size η 3: 4: Cij ← normed(F (xi,xj)) . compute ordering costs (equation 10) 5: initialise P̃ . either uniform or linear assignment init (equation 6) 6: for t← 1, T do 7: P ← S(P̃ ) . normalise assignment with Sinkhorn operator (Appendix B) 8: G← ∂c(P )/∂P . compute gradient of normalised assignment (equation 4) 9: P̃ ← P̃ − ηG . gradient descent step on unnormalised assignment (equation 7) 10: end for 11: P ← S(P̃ ) 12: Y ← PX . permute rows of X to obtain output Y

heading: B SINKHORN OPERATOR

text:
The Sinkhorn operator S as defined in Adams & Zemel (2011) is:
Tr(X)ij = Xij/ ∑ k Xik (11)
Tc(X)ij = Xij/ ∑ k Xkj (12)
S(0)(X) = exp(X) (13)
S(l+1)(X) = Tc(Tr(S(l)(X))) (14) S(X) = S(L)(X) (15)
Tr normalises each row, Tc normalises each column of a square matrix X to sum to one. This formulation is different from the normal Sinkhorn operator by Sinkhorn (1964) by exponentiating all entries first and running for a fixed number of steps L instead of for steps approaching infinity. Mena et al. (2018) include a temperature parameter on the exponentiation, which acts analogously to temperature in the softmax function. In this paper, we fix L to 4.

heading: C QUALITATIVE ANALYSIS OF LEARNED COMPARISON FUNCTIONS

text:
C.1 NUMBER SORTING
First, we investigate what comparison function F is learned for the number sorting task. We start with plotting the outputs of F for different pairs of inputs in Figure 2. From this, we can see that it learns a sensible comparison function where it outputs a negative number when the first argument is lower than the second, and a positive number vice versa.
The easiest way to achieve this is to learn f(xi, xj) = xi, which results in F (xi, xj) = xi − xj . By plotting the outputs of the learned f in Figure 3 we can see that something close to this has indeed been learned. The learned f mostly depends on the second argument and is a scaled and shifted version of it. It has not learned to completely ignore the first argument, but the deviations from it are small enough that the cost function of the permutation is able to compensate for it. We can see that there is a faint grey diagonal area going from (0, 0) to (1, 1) and to (1000, 1000), which could be an artifact from F having small gradients due to its skew-symmetry when two numbers are close to each other.
C.2 IMAGE MOSAICS
Next, we investigate the behaviour of F on the image mosaic task. Since our model uses the outputs of F in the optimisation process, we find it easier to interpret F over f in the subsequent analysis.
C.2.1 OUTPUTS
We start by looking at the output of F1 (costs for left-to-right ordering) and F2 (costs for top-to-bottom ordering) for MNIST 2× 2, shown in Figure 4. First, there is a clear entry in each row and column of both F1 and F2 that has the highest absolute cost (high colour saturation) whenever the corresponding tiles fit together correctly. This shows that it successfully learned to be confident what order two tiles should be in when they fit together. From the two 2-by-2 blocks of red and blue on the anti-diagonal, we can also see that it has learned that for the per-row comparisons (F1), the tiles that should go into the left column should generally compare to less than (i.e. should be permuted to be to the left of) the tiles that go to the right. Similarly, for the per-column comparisons (F2) tiles that should be at the top compare to less than tiles that should be at the bottom. Lastly, F1 has a low absolute cost when comparing two tiles that belong in the same column. These are the entries in the matrix at the coordinates (1, 2), (2, 1), (4, 3), and (3, 4). This makes sense, as F1 is concerned with whether one tile should be to the left or right of another, so tiles that belong in the same column should not have a preference either way. A similar thing applies to F2 for tiles that belong in the same column.
C.2.2 SENSITIVITY TO POSITIONS
Next, we investigate what positions within the tiles F1 and F2 are most sensitive to. This illustrates what areas of the tiles are usually important for making comparisons. We do this by computing the gradients of the absolute values of F with respect to the input tiles and averaging over many inputs. For MNIST 2× 2 (Figure 5, left), it learns no particular spatial pattern for F1 and puts slightly more focus away from the centre of the tile for F2. As we will see later, it learns something that is very content-dependent rather than spatially-dependent. With increasing numbers of tiles on MNIST, it tends to focus more on edges, and especially on corners. For the CIFAR10 dataset (Figure 6), there is a much clearer distinction between left-right comparisons for F1 and top-bottom comparisons for F2. For the 2× 2 and 4× 4 settings, it relies heavily on the pixels on the left and right borders for left-to-right comparisons, and top and bottom edges for top-to-bottom comparisons. Interestingly, F1 in the 3× 3 setting (middle pair) on CIFAR10 focuses on the left and right halves of the tiles, but specifically avoids the borders. A similar thing applies to F2, where a greater significance is given to pixels closer to the middle of the image rather than only focusing on the edges. This suggests that it learns to not only match up edges as with the other tile numbers, but also uses the content within the tile to do more sophisticated content-based comparisons.
C.2.3 PER-TILE GRADIENTS
Lastly, we can look at the gradients of F with respect to the input tiles for specific pairs of tiles, shown in Figure 7 and Figure 8. This gives us a better insight into what changes to the input tiles would affect the cost of the comparison the most. These figures can be understood as follows: for each pair of tiles, we have the corresponding two gradient maps next to them. Brightening the pixels for the blue entries in these gradient maps would order the corresponding tile more strongly towards the left for F1 and towards the top for F2. The opposite applies to brightening the pixels with red entries. Vice versa, darkening pixels with blue entries orders the tile more strongly towards the right for F1 and the bottom for F2. More saturated colours in the gradient maps correspond to greater effects on the cost when changing those pixels.
We start with gradients on the tiles for an input showing the digit 2 on MNIST 2 × 2 in Figure 7. We focus on the first row, left side, which shows a particular pair of tiles from this image and their gradients of F1 (left-to-right ordering), and we share some of our observations here:
• The gradients of the second tile show that to encourage the permutation to place it to the right of the first tile, it is best to increase the brightness of the curve in tile 2 that is already white (red entries in tile 2 gradient map) and decrease the black pixels around it (blue entries). This means that it recognised that this type of curve is important in determining that it should be placed to the right, perhaps because it matches up with the start of the curve from tile 1. We can imagine the curve in the gradient map of tile 2 roughly forming part of a 7 rather than a 2 as well, so it is not necessarily looking for the curve of a 2 specifically.
• In the gradient map of the first tile, we can see that to encourage it to be placed to the left of tile 2, increasing the blue entries would form a curve that would make the first tile look like part of an 8 rather than a 2, completing the other half of the curve from tile 2. This means that it has learned that to match something with the shape in tile 2, a loop that completes it is best, but the partial loop that we have in tile 1 satisfies part of this too.
• Notice how the gradient of tile 1 changes quite a bit when going from row 1 to row 3, where it is paired up with different tiles. This suggests that the comparison has learned something about the specific comparison between tiles being made, rather than learning a general trend of where the tile should go. The latter is what a linear assignment model is limited to doing because it does not model pairwise interactions.
• In the third row, we can see that even though the two tiles do not match up, there is a red blob on the left side of the tile 2 gradient map. This blob would connect to the top part of the line in tile 1, so it makes sense that making the two tiles match up more on the border would encourage tile 2 to be ordered to the right of tile 1.
Similar observations apply to the right half of Figure 7, such as row 5, where tile 1 (which should go above tile 2) should have its pixels in the bottom left increased and tile 2 should have its pixels in the top left increased in order for tile 1 to be ordered before (i.e. above) tile 2 more strongly.
On CIFAR10 2× 2 in Figure 8, it is enough to focus on the borders of the tiles. Here, it is striking how specifically it tries to match edge colours between tiles. For example, consider the blue sky in the left half (F1), row 6. To order tile 1 to the left of tile 2, we should change tile 1 to have brighter sky and darker red on the right border, and also darken the black on the left border so that it matches up less well with the right border of tile 2, where more of the bright sky is visible. For tile 2, the gradient shows that it should also match up more on the left border, and have increase the amount of bright pixels, i.e. sky, on the right border, again so that it matches up less well with the left border of tile 1 if they were to be ordered the opposing way.

heading: D JUSTIFICATION FOR ALTERNATIVE UPDATE

text:
First, the gradient of S(X) is:
∂S(X) ∂X = ∂ exp(X) ∂X ∂Tr(exp(X)) ∂ exp(X) ∂Tc(Tr(exp(X))) ∂Tr(exp(X)) · · · (16)
∂Tr(X)uv ∂Xij = 1u=i 1v=j
∑ kXuk −Xuv
( ∑
kXuk) 2
(17)
∂Tc(X)uv ∂Xij = 1v=j 1u=i
∑ kXkv −Xuv
( ∑
kXkv) 2
(18)
where 1 is the indicator function that returns 1 if the condition is true and 0 otherwise.
We compared the entropy of the permutation matrices obtained with and without using the “proper” gradient with ∂S(P̃ )/∂P̃ as term in it and found that our version has a significantly lower entropy. To understand this, it is enough to focus on the first two terms in equation 16, which is essentially the gradient of a softmax function applied row-wise to P .
Let x be a row in P and si be the ith entry in the softmax function applied to x. Then, the gradient is:
∂si ∂xj = si(1i=j − sj) (19)
Since this is a product of entries in a probability distribution, the gradient vanishes quickly as we move towards a proper permutation matrix (all entries very close to 0 or 1). By using our alternative update and thus removing this term from our gradient, we can avoid the vanishing gradient problem.
Gradient descent is not efficient when the gradient vanishes towards the optimum and the optimum – in our case a permutation matrix with exact ones and zeros as entries – is infinitely far away. Since we prefer to use a small number of steps in our algorithm for efficiency, we want to reach a good solution as quickly as possible. This justifies effectively ignoring the step size that the gradient suggests and simply taking a step in a similar direction as the gradient in order to be able to saturate the Sinkhorn normalisation sufficiently, thus obtaining a doubly stochastic matrix that is closer to a proper permutation matrix in the end.

heading: E QUADRATIC PROGRAMMING PROBLEM

text:
We can write our total cost function as a quadratic program in the standard xTQx form with linear constraints. We leave out the constraints here as they are not particularly interesting. First, we can define O ∈ RN×N as:
Okk′ =  −1 if k > k′ 0 if k = k′
1 if k < k′ (20)
and with it, Q ∈ RN2×N2 as:
Q(ik)(jk′) = CijOkk′ (21)
Then we can write the cost function as:
c(P ) = ∑ ij Cij ∑ kk′ PikPjk′Okk′ (22)
= ∑ ik ∑ jk′ Pik(CijOkk′)Pjk′ (23)
= ∑ (ik) ∑ (jk′) P(ik)Q(ik)(jk′)P(jk′) (24)
= pTQp (25)
where there is some bijection between a pair of indices (i, k) and the index l and p is a flattened version of P with pl = Pik. Q is indefinite because the total cost can be negative: a uniform initialisation for P has a cost of 0, better permutations have negative cost, worse permutations have positive cost. Thus, the problem is non-convex and the problem is possibly NP-hard. Also, since we have flattened P into p, the number of optimisation variables is quadratic in the set size N . Even if this were a convex quadratic program, methods such as OptNet (Amos & Kolter, 2017) have cubic time complexity in the number of optimisation variables, which makes it O(N6) for our case.

heading: F EXPERIMENTAL DETAILS

text:
All of our experiments can be reproduced using our implementation at https:// github.com/Cyanogenoid/perm-optim in PyTorch (Paszke et al., 2017) through the experiments/all.sh script. For the former three experiments, we use the following hyperparameters throughout:
• Optimiser: Adam (Kingma & Ba, 2015) (default settings in PyTorch: β1 = 0.9, β2 = 0.999, = 10−8)
• Initial step size η in inner gradient descent: 1.0
All weights are initialised with Xavier initialisation (Glorot & Bengio, 2010). We choose the f within the ordering cost function F to be a small MLP. The input to f has 2 times the number of dimensions of each element, obtained by concatenating the pair of elements. This is done for all pairs that can be formed from the input set. This is linearly projected to some number of hidden units to which a ReLU activation is applied. Lastly, this is projected down to 1 dimension for sorting numbers and VQA, and 2 dimensions for assembling image mosaics (1 output for row-wise costs, 1 output for column-wise costs). These outputs are used for creating the ordering cost matrix C.
F.1 SORTING NUMBERS
• Inner gradient descent steps T : 6 • Adam learning rate: 0.1 • Batch size: 512 • Number of sets to sort in training set: 218
• Set sizes: 5, 10, 15, 80, 100, 120, 512, 1024 • Evaluation intervals: [0, 1], [0, 10], [0, 1000], [1, 2], [10, 11], [100, 101], [1000, 1001] (same
as in Mena et al. (2018)) • F size of hidden dimension: 16
The ordering cost function F concatenates the two floats of each pair and applies a 2-layer MLP that takes the 2 inputs to 16 hidden units, ReLU activation, then to one output.
For evaluation, we switch to double precision floating point numbers. This is because for the interval [1000, 1001], as the set size increases, there are not enough unique single precision floats in that interval for the sets to contain only unique floats with high probability (the birthday problem). Using double precision floats avoids this issue. Note that using single precision floats is enough for the other intervals and smaller set sizes, and training is always done on the interval [0, 1] at single precision.
F.2 RE-ASSEMBLING IMAGE MOSAICS
• Adam learning rate: 10−3
• Inner gradient descent steps T : 4 • Batch size: 32 • Training epochs: 20 (MNIST, CIFAR10) or 1 (ImageNet) • F size of hidden dimension: 64 (MNIST, CIFAR10) or 128 (ImageNet)
For all three image datasets from which we take images (MNIST, CIFAR10, ImageNet), we first normalise the inputs to have zero mean and standard deviation one over the dataset as is common practice. For ImageNet, we crop rectangular images to be square by reducing the size of the longer side to the length of the shorter side (centre cropping). Images that are not exactly divisible by the number of tiles are first rescaled to the nearest bigger image size that is exactly divisible. Following Mena et al. (2018), we process each tile with a 5×5 convolution with padding and stride 1, 2×2 max pooling, and ReLU activation. This is flattened into a vector to obtain the feature vector for each tile, which is then fed into our F . Unlike Mena et al. (2018), we decide not to arbitrarily upscale MNIST images by a factor of two, even when upscaling results in slightly better performance in general.
While we were able to mostly reproduce their MNIST results, we were not able to reproduce their ImageNet results for the 3× 3 case. In general, we observed that good settings for their model also improved the results of our PO-U and PO-LA models. Better hyperparameters than what we used should improve all models similarly while keeping the ordering of how well they perform the same.
This task is also known as jigsaw puzzle (Noroozi & Favaro, 2016), but we decided on naming it image mosaics because the tiles are square which can lead to multiple solutions, rather than the typical unique solution in traditional jigsaw puzzles enforced by the different tile shapes.
F.3 IMPLICIT PERMUTATIONS THROUGH IMAGE CLASSIFICATION
We use the same setting as for the image mosaics, but further process the output image with a ResNet-18. For MNIST and CIFAR10, we replace the first convolutional layer with one that has a 3× 3 kernel size and no striding. This ResNet-18 is first trained on the original dataset for 20 epochs (1 for ImageNet), though images may be rescaled if the image size is not divisible by the number of tiles per side. All weights are then frozen and the permutation method is trained for 20 epochs (1 for ImageNet). As stated previously, this is necessary in order for the ResNet-18 to not use each tile individually and ignore the resulting artefacts from the permuted tiles. This is also one of the reasons why we downscale ImageNet images to 64× 64 pixels. Because the resulting image tiles are so big while the receptive field of ResNet-18 is relatively small if we were to use 256 × 256 images, the permutation artefacts barely affect results because they are only a small fraction of the globally-pooled features. The permutation permutes each set of tiles, which are reconstructed (without use of the Hungarian algorithm) into an image, which is then processed by the ResNet-18.
We observed that the LinAssign model by Mena et al. (2018) consistently results in NaN values after Sinkhorn normalisation in this set-up, despite our Sinkhorn implementation using the numericallystable version of softmax with the exp-normalise trick. We avoided this issue by clipping the outputs of their model into the [-10, 10] interval before Sinkhorn normalisation. We did not observe these NaN issues with our PO-U model.
F.4 VISUAL QUESTION ANSWERING
We use the official implementation of BAN as baseline without changing any of the hyperparameters. We thus refer to Kim et al. (2018) for details of their model architecture and hyperparameters. The only change to hyperparameters that we make is reducing the batch size from 256 to 112 due to the GPU memory requirements of the baseline model, even without our permutation mechanism.
The BAN model generates attention weights between all object proposals in a set and words of the question. We take the attention weight for a single object proposal to be the maximum attention weight for that proposal over all words of the question, the same as in their integration of the counting module. Each element of the set, corresponding to object proposals, is the concatenation of this attention logit, bounding box coordinates, and the feature vector projected from 2048 down to 8 dimensions. We found this projection necessary to not inhibit learning of the rest of the model, which might be due to gradient clipping or other hyperparameters that are no longer optimal in the BAN model. This set of object proposals is then permuted with T = 3 and a 2-layer MLP with hidden dimension 128 for f to produce the ordering costs. The elements in the permuted sequence are weighted by how relevant each proposal is (sigmoid of the corresponding attention logit) and the sequence is then fed into an LSTM with 128 units. The last cell state of the LSTM is the set representation which is projected, ReLUd, and added back into the hidden state of the BAN model. The remainder of the BAN model is now able to use information from this set representation. There are 8 attention glimpses, so we process each of these with a PO-U module and an LSTM with shared parameters across these 8 glimpses.

heading: G ADDITIONAL RESULTS

text:
An interesting aspect we observed throughout all experiments is how the learned step size η changes during training. At the start of training, it decreases from its initial value of 1, thus reducing the influence of the permutation mechanism. Then, η starts rising again, usually ending up at a value above 1 at the end of training. This can be explained by the ordering cost being very inaccurate at the start of training, since it has not been trained yet. Through training, the ordering cost improves and it becomes more beneficial for the influence of the PO module on the permutation to increase.
G.1 RE-ASSEMBLING IMAGE MOSAICS
In Table 4, we show the accuracy corresponding to the results in Table 1 where the permutation has been trained with explicit supervision. In Figure 12, Figure 13, and Figure 14, we show some example reconstructions that have been learnt by our PO-U model. Starting from a uniform assignment at the top, the figures show reconstructions as a permutation is being optimised. Generally, it is able to reconstruct most images fairly well. Due to the poor quality of many of these reconstructions (particularly on ImageNet), the last two figures show reconstructions on the 2 × 2 versions of the datasets rather than 3× 3.
G.2 IMPLICIT PERMUTATIONS THROUGH IMAGE CLASSIFICATION
In Table 5, we show the mean squared error reconstruction loss corresponding to the results in Table 2. These show similar trends as before. In Figure 15, Figure 16, and Figure 17, we show some example reconstructions that have been learnt by our PO-U model on 3 × 3 versions of the image datasets.
Because the quality of implicit CIFAR10 and ImageNet reconstructions are relatively poor, we also include Figure 18, and Figure 19 on 2×2 versions. Starting from a uniform assignment at the top, the figures show reconstructions as a permutation is being optimised. The reconstructions here are clearly noisier than before due the supervision only being implicit. This is evidence that while our method is superior to existing methods in terms of reconstruction error and accuracy of the classification, there is still plenty of room for improvement to allow for better implicitly learned permutations. Keep in mind that it is not necessary for the permutation to produce the original image exactly, as long as the CNN can consistently recognise what the permutation method has learned. Our models tend to naturally learn reconstructions that are more similar to the original image than the LinAssign model.


summaries: This paper proposes a Projective Subspace Network (PSN) for few-shot learning. The PSN represents each support set of classes as a subspace obtained by SVD. Then the method calculates distances between a query and classes by the projection error to the subspace. Instead of using the prototype of the class center, the subspace representation is more robust to outliers. Though the contribution seems to be incremental, it is a reasonable improvement upon Matching Networks and Prototypical Networks.

summaries: This paper considers the problem of few-shot learning and proposes a new embedding-based approach. In contrast to previous work (such as Matching Networks and Prototypical Networks) where distance is computed in pure embedding space, this work proposes computing a low-dimensional subspace to represent a class and using the distance from an embedded query point to this subspace. The low-dimensional subspace for a class is computed by running truncated Singular Value Decomposition on the normalized embeddings of all points in the support set for that class and using the top n left singular vectors as the basis for the class's subspace. The authors also propose an extension to their model to the semi-supervised few-shot learning setting by incorporating masked-mean computation and zero-mean cluster for distractor items (both ideas borrowed from Renn 2017 for prototypical networks). Experiments are conducted on Mini-Imagenet in the few-shot learning setting and on Mini-Imagenet and Tiered-ImageNet in the semi-supervised few-shot learning setting.

abstractText: Generalization from limited examples, usually studied under the umbrella of metalearning, equips learning techniques with the ability to adapt quickly in dynamical environments and proves to be an essential aspect of lifelong learning. In this paper, we introduce the Projective Subspace Networks (PSN), a deep learning paradigm that learns non-linear embeddings from limited supervision. In contrast to previous studies, the embedding in PSN deems samples of a given class to form an affine subspace. We will show that such modeling leads to robust solutions, yielding competitive results on supervised and semi-supervised few-shot classification. Moreover, our PSN approach has the ability of end-to-end learning. In contrast to previous works, our projective subspace can be thought of as a richer representation capturing higher-order information datapoints for modeling new concepts.

authors:
Bogdan Alexe
Thomas Deselaers
Vittorio Ferrari

title: Measuring the objectness of image windows

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI),

authors:
Ronen Basri
David W. Jacobs

title: Lambertian reflectance and linear subspaces

authors:
Rinu Boney
Alexander Ilin

title: Semi-supervised few-shot learning with prototypical networks

venue: arXiv preprint arXiv:1711.10856,

authors:
Li Fei-Fei
Rob Fergus
Pietro Perona

title: One-shot learning of object categories

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In International Conference on Machine Learning(ICML),

authors:
Victor Garcia
Joan Bruna

title: Few-shot learning with graph neural networks

venue: In International Conference on Learning Representations(ICLR),

authors:
Spyros Gidaris
Nikos Komodakis

title: Dynamic few-shot visual learning without forgetting

authors:
Mengran Gou
Fei Xiong
Octavia Camps
Mario Sznaier

title: Monet: Moments embedding network

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Geoffrey E. Hinton
Li Deng
Dong Yu
George E. Dahl
Abdel rahman Mohamed
Navdeep Jaitly
Andrew Senior
Vincent Vanhoucke
Patrick Nguyen
Tara N. Sainath
Brian Kingsbury

title: Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups

venue: IEEE Signal Processing Magazine,

authors:
Catalin Ionescu
Orestis Vantzos
Cristian Sminchisescu

title: Matrix backpropagation for deep networks with structured layers

venue: In IEEE International Conference on Computer Vision (ICCV),

authors:
Diederik P. Kingma
Jimmy L. Ba

authors:
Gregory Koch
Richard Zemel
Ruslan Salakhutdinov

title: Siamese neural networks for one-shot image recognition

venue: In International Conference on Machine Learning Deep Learning 2015 Workshop,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In Advances in neural information processing systems(NIPS),

authors:
Brenden M. Lake
Ruslan Salakhutdinov
Joshua B. Tenenbaum

title: Human-level concept learning through probabilistic program induction

authors:
Angeliki Lazaridou
Marco Marelli
Marco Baroni

title: Multimodal word meaning induction from minimal exposure to natural text

venue: Cognitive Science,

authors:
Peihua Li
Jiangtao Xie
Qilong Wang
Wangmeng Zuo

title: Is second-order information helpful for large-scale visual recognition

authors:
Zhenguo Li
Fengwei Zhou
Fei Chen
Hang Li

title: Meta-sgd: Learning to learn quickly for few shot learning

venue: arXiv preprint arXiv:1707.09835,

authors:
Aditya K. Menon
Charles Elkan

title: Fast algorithms for approximating the singular value decomposition

venue: ACM Trans. Knowl. Discov. Data(TKDD),

authors:
Nikhil Mishra
Mostafa Rohaninejad
Xi Chen
Pieter Abbeel

title: A simple neural attentive metalearner

authors:
James O’ Neill
Paul Buitelaar

title: Few shot transfer learning betweenword relatedness and similarity tasks using a gated recurrent siamese network

venue: In AAAI Conference on Artificial Intelligence,

title: Automatic differentiation in pytorch

venue: In NIPS Autodiff Workshop,

authors:
Siyuan Qiao
Chenxi Liu
Wei Shen
Alan L. Yuille

title: Few-shot image recognition by predicting parameters from activations

authors:
Sachin Ravi
Hugo Larochelle

title: Optimization as a model for few-shot learning

authors:
Mengye Ren
Eleni Triantafillou
Sachin Ravi
Jake Snell
Kevin Swersky
Joshua B. Tenenbaum
Hugo Larochelle
Richard S. Zemel

title: Meta-learning for semi-supervised few-shot classification

venue: In International Conference on Learning Representations (ICLR),

authors:
Olga Russakovsky
Jia Deng
Hao Su
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
et al. Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International Journal of Computer Vision(IJCV),

authors:
Jake Snell
Kevin Swersky
Zemel Richard

title: Prototypical networks for few-shot learning

venue: In Advances in Neural Information Processing Systems(NIPS),

authors:
Antonio Torralba
Kevin P. Murphy
William T. Freeman

title: Sharing visual features for multiclass and multiview object detection

authors:
Eleni Triantafillou
Richard Zemel
Raquel Urtasun

title: Few-shot learning through an information retrieval lens

authors:
Oriol Vinyals
Charles Blundell
Tim Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Yu-Xiong Wang
Ross Girshick
Martial Herbert
Bharath Hariharan

title: Low-shot learning from imaginary data

authors:
Zhongwen. Xu
Linchao Zhu
Yi Yang

title: Few-shot object recognition from machine-labeled web images

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: In British Machine Vision Conference(BMVC),

heading: 1 INTRODUCTION

text:
Supervised learning with deep architectures, though achieving remarkable results in many areas, requires large amount of annotated data. Various studies show that many deep learning techniques in computer vision, speech recognition and natural language understanding, to name a few methods stated in Hinton et al. (2012); Krizhevsky et al. (2012), will fail to produce reliable models that generalize well if limited data annotations are available. Aside from the labor associated with annotating data, precise annotation can become ill-posed in some cases. One prime example of such a difficulty is object detection labeling which requires annotating bounding boxes of objects as explained in Alexe et al. (2012).
In contrast to the current trend in deep learning, humans can learn new concepts from only a few examples. This in turn provides humans with lifelong learning abilities. Inspired by such learning abilities, several approaches are developed to study learning from limited examples Lake et al. (2015); Lazaridou et al. (2017); Vinyals et al. (2016); Triantafillou et al. (2017); Xu et al. (2017); Finn et al. (2017); Ravi & Larochelle (2017); Wang et al. (2018); Mishra et al. (2018); Qiao et al. (2018); Neill & Buitelaar (2018). In machine learning, the diverse ideas in this context include embedding features through metric learning (Koch et al. (2015), Vinyals et al. (2016)), optimization technique(Finn et al. (2017), Ravi & Larochelle (2017)), and generative models(Fei-Fei et al. (2006), Lake et al. (2015)).
In this work, we propose a deep model that learns new concepts from limited data to address two challenging learning problems; namely: (i) few-shot classification and (ii) semi-supervised few-shot learning. The goal of few-shot classification is to learn a model that can discriminate a given query by comparing it to a few of samples (a.k.a. the support set). An example is to classify a motorcycle by viewing some different types of motorcycles (or other vehicles). The goal of semi-supervised few-shot learning is to additionally benefit from unlabeled data to boost the performance of the model.
Our method, coined Projective Subspace Networks or PSN for short, learns non-linear embeddings using subspaces, in a sense that samples of a class are modeled as a low-dimensional affine subspace. The use of subspaces to model images and sets has a long history in computer vision and machine learning. For example, it has been proved that the set of all reflectance functions (the mapping from surface normals to intensities) produced by Lambertian objects lie close to a low-dimensional linear subspace (Basri & Jacobs (2003)).
In spite of its intriguing properties, to the best of our knowledge, the subspace modeling has never been used previously to address few-shot learning problems. This makes our paper distinct and novel as compared to former studies (e.g., Vinyals et al. (2016); Snell et al. (2017)). Fig. 1 provides a conceptual illustration of our approach.
We empirically observed that embeddings tailored towards capturing the structure of each class through low-dimensional affine subspaces could lead to discriminative models. Interestingly, such models can be built with minimum overheads and without opting for advanced methods in subspace creation (e.g., such as the notion of sparsity). Our conjecture here is that subspaces are less sensitive to perturbations such as outliers and noise compared to other embedding techniques for few-shot learning as illustratively shown in Fig. 2.
Our contributions in this work are: i. Few-shot learning is formulated as an embedding problem through subspaces. We rely on a
well-established concept stating that samples of a class (and hence variations such as pose and illumination) can be effectively captured by a low-dimensional affine space.
ii. Adaptation from few-shot learning to semi-supervised learning is performed with a refinement through soft-assignment. The robustness of such a model is shown in our experiments.
iii. We also introduce an evaluation mechanism to assess the generalization ability over unseen classes during test time.

heading: 2 RELATED WORK

text:
In this section, we briefly review the literature on few-shot learning and subspace clustering. Fewshot learning was originally introduced to imitate human learning capabilities in classification. Some of the early works made use of generative models and similarity learning to capture the variation within parts and geometric configurations of objects (Fei-Fei et al. (2006); Lake et al. (2015); Torralba et al. (2007)). As of late, few-shot problems are mainly addressed through meta-learning techniques. For example, in Koch et al. (2015); Vinyals et al. (2016); Snell et al. (2017); Garcia & Bruna (2018), the problem of few-shot learning is formulated as non-linear embedding or representation learning.
The closest approach to our proposed work is the Prototypical Networks (PN hereafter) model ( Snell et al. (2017)). It uses the random choice of episode images which form the prototype center per class. In addition, recent metric learning approaches use complex architectures and pipelines in convolutional networks of Gidaris & Komodakis (2018) and Wang et al. (2018). In contrast, our projective subspace concept is extremely simple by design as it constitutes just a single layer of the network.
Another common meta-learning approach to few-shot classification uses meta-learning and manipulates gradient updates to train the model parameters. Ravi & Larochelle (2017) utilized Long-Short Term Memory (LSTM)-based learner to optimize the model parameters and their gradients. Moreover, the Model Agnostic Meta-Learner(MAML) proposed by Finn et al. (2017) used gradients per
task as well as a meta-gradient from combined tasks, and, as a result, it outperformed LSTM-based learner. Mishra et al. (2018) employed ResNets to model few-shot classification as a temporal solution with aggregation, thus, in meta-learning context, their model can refer to the past experience.
Our idea is based on the assumption that samples from any class in the support set form a lowdimensional subspace. As we will show, to train PSN, backpropagation through Singular Value Decomposition (SVD) is required. Backpropagation through matrix decomposition such as SVD is a well-studied problem Ionescu et al. (2015) with applications ranging from semantic segmentation to classification and visual recognition Ionescu et al. (2015); Li et al. (2017a); Gou et al. (2018).

heading: 3 PROBLEM SET-UP

text:
We start by defining the terminology used in few-shot learning. The problem of N -way K-shot classification (e.g., 5-way 1-shot) is defined as classifying queries belonging to N classes by seeing only K samples from each class. For example, in 5-way 1-shot setting, the model needs to identify a query among five classes by seeing only one sample from each class. To obtain a reliable model, so-called episodes are used in training. An episode Ti consists of two sets, the support set S and the query setQ. The system is then trained by minimizing a classification loss over episodes, simulating the scenarios it will encounter at test time. This episode setting is the same as proposed by Vinyals et al. (2016).
A related problem is semi-supervised few-shot setting learning where unlabeled data is provided to the model. In the literature, various configurations are considered for semi-supervised few-shot learning (e.g., Garcia & Bruna (2018); Boney & Ilin (2017); Ren et al. (2018)). In this work, we follow the challenging protocol in Ren et al. (2018) where so-called distractors are introduced. Here, an episode includes the support set S, query setQ, and unlabeled setR. The support (labeled) S and query Q sets are configured as in few-shot learning. Additionally, an unlabeled set R is provided to assist the classification task within an episode. In the unlabeled set, there are examples from two different sources: the support classes and the distractor classes. As the name implies, examples from distractor classes are irrelevant to the classification task and represent classes outside the support set.
4 PROJECTIVE SUBSPACE NETWORKS
In what follows, we introduce our PSN approach. The whole framework is trained end-to-end (see Fig. 3) which enables PSN to be used with various deep architectures. As an example, in § 5, we use PSN on top of the WideResNets (Zagoruyko & Komodakis (2016)) for few-shot classification.
We start by introducing our notations for the (N -way, K-shot) few-shot learning. Each episode or task Ti is composed of the support set S = {(x1,1, c1,1), (x1,2, c1,2), · · · , (xN,K , cN,K)} and the query set Q = {q1, · · · , qN×M}. Here, xi,j denotes the j-th sample from class i and ci,j ∈ {1, · · · , N}. In the semi-supervised setting, there is an unlabeled set R = {r1, .., rU} within an episode. We propose to model points by subspaces {Zi}Ni=1. Each subspace Zi has a basis represented by RD×n 3 Pi = [p1, · · · ,pn];n ≤ D, with P>i Pi = In.

heading: 4.1 PSN FOR FEW-SHOT CLASSIFICATION

text:
Let fΘ : X → RD be a mapping from the input space X to some D-dimensional representation realized by a neural network. Our goal is to learn Θ, i.e., the embedding function in a way that the resulting space is suitable for subspace representation. For simplicity, we assume that every class in an episode can be described by just one subspace. Extension to multiple subspaces per class is straightforward though. Define µk as the mean of class k in the embedded space. That is,
µk = 1
K ∑ i, ci=k fΘ(xi). (1)
A basis for the subspace representing class k can be obtained by Singular Value Decomposition (SVD). To be specific, we define Xk = [xk,1 − µk, · · · ,xk,K − µk]. Applying truncated SVD on Xk provides us with Pk. We emphasize that more involved techniques to obtain robust subspaces from Xk can potentially improve the PSN. Nevertheless, our goal is to assess whether the concept of subspace modeling for few-shot learning is justified or not and thus we opt for truncated SVD in our implementation. Now a query qj can be projected onto Pk which yields:
yj,k = P > k (fΘ(qj)− µk). (2)
The distance from the query to Pk is:
dj,k = ‖fΘ(qj)− µk − Pkyj,k‖. (3)
We define the probability of the query assigned to class k using a softmax function as:
pΘ(c = k|qj) = exp
( − d2j,k )∑ k′ exp ( − d2j,k′
) . (4) Now, we can minimize the negative log of Eqn. 4 to obtain Θ. To train the whole framework, backpropagation through SVD is required which is available in modern deep learning packages such as PyTorch (Paszke et al. (2017)). Algorithm 1 explains the steps of training our PSN. The code will be released online on Github1.
Algorithm 1 Train Projective Subspace Networks Input: Each episode Ti with S = {(x1,1, c1,1), · · · , (xN,K , cN,K)} and Q = {q1, ..., qN×M}
1: Θ0 ← random initialization 2: for t in {T1, ..., TNT } do 3: Lt ← 0 4: for k in {1, ..., N} do 5: X ← Sk . Get examples in the support set from class k 6: µk ← 1K ∑ x∈X fΘ(x) . Mean from the support set 7: µk ← Kµk + ∑ imifΘ(ri)
K + ∑ imi . Refined mean(only semi-supervised learning)
8: X̃ ← [xi − µk, ...,xK − µk] 9: [U ,Σ,V>]← SVD(X̃) . Matrix factorization using SVD 10: Pk ← U1,...,n . Truncate the matrix 11: for qj in Qk do 12: yj,k ← P>k (fΘ(qj)− µk) . Query projection 13: dj,k ← ‖fΘ(qj)− µk − Pkyj,k‖ . Distance calculation 14: pj,k ← exp(−d2j,k)∑ k′ exp(−d2j,k′) . Softmax on distance scores
15: end for 16: end for 17: Lt ← 1N2M ∑ k ∑ j − log (pj,k) 18: Update Θ using ∇ΘLt 19: end for

heading: 4.2 PSN FOR SEMI-SUPERVISED FEW-SHOT LEARNING

text:
In what follows, we extend the model developed in § 4.1 to address semi-supervised few-shot learning. In doing so, we need to take advantage of the unlabeled data to fit better subspaces to our data. We achieve this by refining the center of each class according to
µ̃k = Kµk +
∑ imifΘ(ri)
K + ∑ imi , where mi = exp(−‖fΘ(ri)− µk)‖2)∑ k′ exp(−‖fΘ(ri)− µk′)‖2) . (5)
Here, mi is the soft-assignment score for unlabeled samples. To work at the presence of distractors, we use a fake class with zero mean. We empirically observed that such a simple modification to the means can improve the results without the need of refining the SVD step.

heading: 5 EXPERIMENTS

text:
Below we contrast and assess our method against state-of-the-art techniques on two challenging datasets, namely Mini-ImageNet (Ravi & Larochelle (2017)) and Tiered-ImageNet (Ren et al.
1https://github.com/anonymousauthor/PSN
(2018)). As the rule of thumb, the parameters of subspace dimension (n) that we used in the experiments are K-1 for training and two for testing stage.
Mini-ImageNet. The Mini-ImageNet(Ravi & Larochelle (2017)) contains 60,000 images of the ImageNet(Russakovsky et al. (2015)) datasets. Images in the Mini-ImageNet are of size 84 × 84 and represent 100 classes with 64, 16, and 20 classes used for training, validation, and testing, respectively.
Tiered-ImageNet. This dataset is also derived from ImageNet but contains a broader set of classes compared to the Mini-ImageNet. There are 351 classes from 20 different categories for training, 97 classes from 6 different categories for validation, and 160 classes from 8 different categories for testing. In contrast to the Mini-ImageNet, the training and test sets in Tiered-ImageNet represent distinct classes. Moreover, in designing the Tiered-ImageNet, the problem of few-shot learning with unlabeled data was taken into account and the labeled data is only within a small percentage when performing semi-supervised learning. In this large dataset, learning from the labeled data is still sufficient to produce reasonable representations even though the unlabeled data is set in huge portion e.g., 90%.

heading: 5.1 FEW-SHOT LEARNING

text:
We follow the general practice and evaluate our method on the Mini-ImageNet dataset when it comes to few-shot learning and classification. Various procedures such as pre-training using 64 classes (e.g., Qiao et al. (2018)) and training with more classes/way have shown to increase the overall accuracy. Nevertheless, we avoid such procedures deliberately as we are mainly interested in contrasting the core idea, i.e., the role of subspaces in few-shot learning. So, we trained on 5- way 5-shot and 20-way 5-shot, then applied the same classification task setup during testing. The CNN architecture is the same as the one used in Snell et al. (2017) with 4-convolutional stages. We also use WideResNets (Zagoruyko & Komodakis (2016)) with 16 depth, 6 widening factor, and 0.3 dropout rate to compare with ResNets (He et al. (2016)) solution reported by Mishra et al. (2018). The feature dimensions from both architectures are 1600 and 384 respectively. We used ADAM ( Kingma & Ba (2015)) for optimizing our model and set the learning rate to 0.001 and cut it to half every 2.5K episodes for both architectures.
Results. By design, the method cannot accommodate learning with exactly one example, hence, the comparison here is provided only for 5-shot in 5-way and 20-way. In every episode, the query set contains 15 samples from each class. Our method outperforms the previous methods with 4- convolutional stages shown in Table 1. We also implemented WideResNets (Zagoruyko & Komodakis (2016)) using our method and obtained the performance for 5-way 5-shot: 69.92± 0.64% and 20-way 5-shot: 41.84± 0.24% that can outperform ResNets-based approach proposed by Mishra et al. (2018) with 68.88± 0.92% in 5-way and 5-shot classification task.

heading: 5.2 SEMI-SUPERVISED FEW-SHOT LEARNING

text:
In this experiment, the embedding architecture has 4-convolutional layers as PN (Snell et al. (2017)). We follow the experimental setup proposed by Ren et al. (2018). The episode composition for labeled or support set and query set is similar to the few-shot learning classification task, but there is an additional unlabeled set provided in each episode. Our model is trained on 100K episodes for
Mini-ImageNet and Tiered-ImageNet with 40% and 10% of labeled data, respectively. We used the ADAM solver (Kingma & Ba (2015)), the set the learning rate to 0.001 with the weight decay and cut the rate to half every 10K episodes. We trained in two settings: (i) supervised setting, where only labeled data is taken into account, and (ii) semi-supervised setting for which the unlabeled set is also used. The unlabeled set is composed of the examples from the classes in the support set and distractor classes. The number of supporting classes and distractor classes is set to five for training and testing. In the training stage, the number of examples in the unlabeled set is 50 consisting of five examples from each class. In the testing stage, the unlabeled set consists of 20 examples from each class. We also define the query set to have 20 examples per class for testing purpose.
Results. In these experimental results, the performance is counted over 600 episodes. The results are averaged over 10 random splits of labeled and unlabeled sets. The supervised experiment shows that our method learns robust feature embedding from a small portion of labeled data. With the help of soft-assignment over unlabeled datapoints, the semi-supervised experiment detailed in Table 2 is demonstrated to outperform Prototypical Networks for Semi-Supervised Learning (PN-SSL) proposed by Ren et al. (2018).
5.3 GENERALIZATION BEYOND N -WAY K-SHOT
As a measure of generalization ability, we propose to evaluate algorithms beyond the somehow inflexible testing protocol of few-shot learning. In particular, we assess whether a model trained on low number of classes can generalize well to classification tasks involving large number of classes. To gain more insights, we further study how models trained with theK-shot assumption will perform if extra examples are available at the test time.
In the evaluation below, all models are trained with the 5-way 5-shot setting. At the test time, the models face the test protocol of N -way K-shot learning with N ∈ {5, 10, 15, 20} and K ∈ {3, 5, 10, 15, 20}. Table 3 contrasts the performance of PSN against PN. The table is selfexplanatory. In all experiments, PSN outperforms PN with the gap widened with more challenging settings (e.g., 20-way 20-shot).
Robustness to Perturbations. Our motivation to develop PSN is to devise a model that shows better resilience to perturbations. Intuitively, to have a noticeable change in the orientation of a subspace, one needs to induce drastic changes to the set. To empirically verify our claim, we assess how robust is PSN in comparison to PN (Snell et al. (2017)) in the presence of perturbations. In particular, we considered the problems of 5-way 5-shot and 5-way 10-shot learning and introduced two types of perturbations at the test time to the trained models. Firstly, we randomly sampled examples from classes not presented in the support sets and included them in the support examples. Secondly, noisy examples are generated randomly using a multivariate Gaussian distribution with random mean and variance of σ = {0.15, 0.3, 0.4}. The results of this study are presented in Appendix A due to page limitations. To summarize, our experiments show that both PSN and PN are affected by outliers negatively. That said, the PSN exhibits a much better degree of resilience to outliers. When additive noise is considered, PSN behaves robustly for a wide-range of contamination. In contrast, the performance of PN drops rapidly and significantly in the presence of noise, reinforcing our idea that the use of subspaces indeed leads to a more robust model for the task in hand.

heading: 6 DISCUSSION

text:
Conceptually, the PN Snell et al. (2017) is the closest work to ours as both solutions obtain a refined representation for each class in the support sets, with the former using the class mean as the representation while in PSN affine subspaces model classes. That said, PSN also uses the mean of each class towards identifying their representative subspaces. Aside from the theoretical properties of affine subspaces2, we empirically observed that for more challenging setups (e.g., 20-way 20-shot), utilizing the mean leads to a better performance. This is because prototypes lie on subspaces in the feature space. Additionally, prototypes in the PN can be easily utilized to design a hybrid with our approach. Remark 1. Interestingly, in special cases, PSN simplifies to PN. For example, if samples of a class span a infinitesimal region, at the limit, collapsing to a point, then an affine subspace reduces to a point, recovering PN from PSN. Remark 2. Since it is not possible to build an affine subspace from only one example, PSN cannot address 1-shot learning problems per se. However, simply applying augmentations to support images facilitates 1-shot learning. However, this issue is beyond the point we make in this work.
Subspace Dimension. In comparison to other models such as matching networks or PN, PSN comes with an extra hyper-parameter, the dimensionality of the subspaces (i.e., n). As a rule of thumb, we recommend to use n = K − 1 to train the model, while n = 2 at the test time gives reasonable and robust results. That said, we thoroughly studied the effect of this parameter and summarized our findings in Appendix B. In short, PSN exhibits a great degree of robustness to n, which in turns, makes training of them painless.
Computational Complexity. The computational complexity of our PSN approach is O(min(ND2K,NDK2)), whereK,N , andD are the number of shot, way, and feature dimensionality respectively. Compared to the complexity of the PN algorithm, i.e., O(NDK) , our algorithm is somehow slower due to the involvement of the SVD step. If the complexity is of a concern, fast approximate algorithms for SVD (e.g., Menon & Elkan (2011)) can be considered.

heading: 7 CONCLUSIONS

text:
This paper presents the PSN, a novel approach for few-shot learning that employs nonlinear embeddings and modeling via affine subspaces. Empirically, we showed that the representations learned via PSN were expressive across a wide-range of supervised and semi-supervised few-shot problems.
In PSN, each class is represented by the subspace formed by all its examples, meaning that each class is modeled by the span of its samples. One possibility to extend the PSN modeling is to benefit -cleverly- from the null space associated with each class, in the hope of designing a more discriminative model.
2One can argue why not modeling classes with linear subspaces, i.e., to drop the class mean for modeling. We note that linear subspaces are indeed special cases of more general affine subspaces where all subspaces intersect at the origin.

heading: A PERTURBATIONS EFFECT ON PERFORMANCE

text:
In this section, we study the effect of perturbation on the performance of PN and PSN. More specifically, we considered the problems of 5-way 5-shot and 5-way 10-shot learning and introduced two types of perturbations at the test time with the trained models. Note that, the model is obtained from 5-way 5-shot training without perturbations. Firstly, we randomly sampled examples from classes not presented in the support sets. Secondly, additive noise is generated randomly using a multivariate Gaussian distribution with random mean and variance of σ = {0.15, 0.3, 0.4}. Both examples in these two types are included in the support examples for prototypes and subspaces creation.
The results of this study are depicted in Fig. 4. To summarize, our experiments show that both PSN and PN are affected by outliers negatively. That said, the PSN exhibits a much better degree of resilience to outliers. For example, modelling with PN leads to a drop of 19% and 12% percentage points when each support set has 20 outliers for the problem of 5-way 5-shot and 5-way 10-shot respectively. For the same experiment, the PSN modelling only suffers 11% and 9% percentage points of performance drop. When additive noise is considered, PSN behaves robustly for a widerange of contamination. In contrast, the performance of PN drops rapidly and significantly in the presence of noise, reinforcing our idea that subspaces form indeed a more robust model for the task in hand.

heading: B SUBSPACE DIMENSION EXPERIMENT

text:
In this section, we report the results of experiments conducted to assess the effect of the subspace dimensionality (i.e., n) on the overall accuracy of the algorithm. In particular, we considered two few-shot problems, namely 5-way 5-shot and 5-way 20-shot. For the former, we varied the subspace dimensionality n ∈ {2, 3, 4, 5} and considered all combinations during training and testing (for example, n = 4 during training and n = 3 at the test time). For the experiment on 5-way 20- shot problem, we varied the subspace dimensionality n ∈ {5, 10, 15, 20} and again considered all combinations.
Our experiments demonstrate that PSN behaves robustly over a wide-range of subspace dimensionality. For example, the lowest and highest performances for the 5-way 5-shot learning are 66.08± 0.67% and 66.62± 0.69%, respectively. For the problem of 5-way 20-shot learning, the lowest and highest performances are 75.03± 0.57% and 75.58± 0.57%, respectively.

title: PROJECTIVE SUBSPACE NETWORKS FOR FEW-SHOT LEARNING