Fast Differentiable Sorting and Ranking
arxiv.org
arxiv.org
https://en.wikipedia.org/wiki/Doubly_stochastic_matrix
which is better explained here:
https://cs.stackexchange.com/questions/4805/sorting-as-a-lin...
where the sorting operation is defined as a linear program. Evidently, this has been known for at least half a century. That said, if a solution to a linear program can be found in a way that's differentiable, this means that the operation of sorting can be found to be differentiable as well. This appears to be trick in the paper and they appear to have a relatively fast way to compute this solution as well, which I think is interesting.
In general if memory serves right, linear programming can solve every problem that's in P with some suitable linear time preprocessing. See https://en.wikipedia.org/wiki/P-complete for some background.
Inner point methods to solve linear programs should then give you the bridge to continuous domains.
Paper is interesting but not yet sure of practical uses.
The trick I use in practice when I need a differentiable sort, is usually a pre-sort step which involves thresholding (i.e. selecting with sparsity only values greater than a certain score (usually either a constant, or a fraction of the best score, or the Kth score ) ). Then pay the quadratic price with n=10 or 20.
I don't see when the relevance of rank between garbage results would really matter. When n get bigger and you don't want to ignore bad results, usually quantile approximations suffice.
In the applications they cite :
The smart use (cross-validation) of threshold by the Huber loss in section 6.4 works better 2 out of 3 times in their own graphs).
The other use cases when order matters (for example like in section 6.3 is where the rankings are given as input). If n is low you pay the quadratic cost, if n is high you usually need to process samples a subset at a time for memory reasons and use some comparison losses (triplet loss...). So this is relevant only in the sweet spot in between if you need exact calculations.
However I must admit that I do not fully grasp the implications of this paper. Why do we really need differentiable sorting for deep learning in the first place? What new possibilities open up as a result? My best uneducated guess is that the gradients produced by differentiable sorting are more informative than regular piecewise sorting, and this allows the gradient descent to progress faster, therefore training faster. (Think about how you can know an entire analytic function can be completely known from any small neighborhood. Are these sorting functions analytic too?) My intuition tells me that the derivatives produced with this technique allow the optimizer to see true gradients across classes.
Are higher order derivatives also meaningful here?
The experiments section is pretty clear in what potential applications can be, e.g. "optimizing directly for top-k classification loss" or "label ranking via soft Spearman’s rank correlation coefficient". In Google's case, there are pretty clear applications towards web search (top-k results, classification = do you click or not), and things like entity labeling (e.g. what label should we assign to a news story).
That's akin to saying that minimizing cross entropy empirically maximizes accuracy but there's no strong theoretical backing for that either
LambdaRank is one way of getting a smooth differentiable approximation to NDCG by slapping a sigmoid somewhere. The paper we're discussing now offers another way. Hard to say which way would turn out to be empirically better on problems of practical significance without actually experimenting.
What they want to do (eventually) is propose loss functions for machine learning. NOT algorithms for sorting per se.
The consider ML models of the form f: x --> r that take features x to some permutation or list of ranks. For example in their CIFAR experiments, I think (correct me if I'm wrong) that x is an image and there are n possible labels, e.g. "dog, cat, giraffe, ...", and given x, f(x) should rank the labels from most likely to least likely.
Now, how do we train such a model f? We use empirical risk minimization over some labeled dataset, e.g. a collection of pairs (x,y) where x is the image and y is a label.
So we train our neural net to become the f that minimizes average Loss(f(x), y) over pairs x,y.
But what Loss function do we use? That's what this paper is ultimately about. And they claim theirs is efficient to compute and produces good hypotheses f.
I do have one question though: what is the resulting algorithm actually "doing" when analyzed as a conventional sorting algorithm and not a geometric operation?
This textbook covers CS theory using real numbers instead of integers.
https://www.amazon.com/Complexity-Real-Computation-Lenore-Bl...
I would go one step further and argue that we shouldn't teach kids discrete math first, but rather continuous math instead.
Sure, you have discrete digits and toys, but Piaget (and his student Papert) observe that kids begin pouring water between different containers in the bath before they can do integer counting and from that develop understanding that objects of different shape can have the same volume and concepts of partial filling, ratios etc.
The human scale world is continuous more than it is discrete.
(Euclidean) geometry is an interesting case. It has discrete arrangements that you can vary continuously.
Of course, there's also areas of math without anything resembling numbers or the discrete vs continuous distinction in it.
Anecdotal consequence: 16bits floating point numbers have so much non-linearity in their round-off error that you can use them to build neural network with no activation functions (which are traditionally needed to introduces non-linearity).
I imagine that how well this works also strongly depends on the kinds of rounding. I imagine that stochastic rounding, or the rounding used in Google's bfloat16 are different in this regard in comparison with standard IEEE floating point rounding.
I believe it is not used because it requires 16bits precision which, nowadays, you only get on GPU. People usually train on GPU but then evaluate on CPU (in production) where the discontinuity would be much smaller (as you would use 32 bits precision).
Furthermore I don't know if, in practice, that type of discontinuity trains as well as a classical activation function (the gradient propagation might be hindered by the limited precision).
AFAIK analog computers are still the standard in radars for example and it sound like neural networks would benefit from similar hardware.
"A textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms" --Wikipedia
I wonder if the techniques developed by the authors could make it feasible to take other piecewise linear/constant algorithms (which until now have been considered "non-differentiable" for practical purposes) and turn them into differentiable algorithms.
Think beyond sorting and ranking.
Naively one might think, why not just do a standard loss - a point to point metric like mean squared error. But this is deeply flawed. Because it requires assigning each sample to a specific natural number, effectively reducing the solution space by an order of magnitude, n!. In practice, believe me, I have tried - the network never converges because the mapping is entirely arbitrary and has nothing to do with the samples.
To remedy this, we need an innovation in loss functions / mathematics. The loss function for the output of the net needs to be a set function [1]. This set function should measure the distance between the Set of outputs of the net and the Set {1,2,...,n-1,n}. This is different from KL and all the other standard loss metrics, because we do not care about the point to point mappings, and have no ability to histogram or compute the probability distribution since those are non differentiable operations.
On sorting: tensorflow has a differentiable sort but it is a hack and simply propagates the loss backwards to the position the original data was in before it ended up in its sorted position. This loss of dist(sort(Y_pred),[1,n]) provides better results but still fails for large data sets due to the fakeness of the sort derivative.
I have a hunch that there is a mathematical way to uniquely measure some arithmetic quality to optimize for, that is maximum when the output set is the discrete uniform distribution.
The mean, standard deviation and other statistical measures are terrible identifiers and actually, via statistical theory, we would need n moments for a dataset of size n, to uniquely identify the distribution..so scratch those off the list [2].
So there are two ways to achieve this milestone in ML:
1) a truly differentiable distance metric between two sets d(S,T)
2) a differentiable measure of ideal dispersion / density that forces the output set S to converge to the discrete uniform distribution (this is more problem specific to perfect hashes.)
Perhaps this sort is the key to doing #1 generically so we can have a new type of NN based on the output Set instead of the specific points. It is late here but I am excited to hear feedback.
we hit permutation invariance issues like what you're talking about in some atomistic simulations because the atoms need to be permutable if you want to use the same model for chemistry as protein folding/docking, and the FGW algo from e.g. https://arxiv.org/pdf/1811.02834.pdf https://tvayer.github.io/materials/Titouan_Marseille_2019.pd...
relaxes the invariance issue by adding a feature distance to the euclidean distance.
higher order distance matrices are a neat trick, but blow up VRAM past 10-50k atoms, but if you did it in mixed precision with newer gpus it could scale damn far. problem is, the distance between distance matrices assumes the target and source items are matched, so you get into iterative closest point alignment, and pretty soon you're just reinventing RMSD
it would be cool for molec stuffs to have fast permutation-invariant set based loss functions using transport theory, but this might be better handled with a model-free approach (just let the AI figure out the loss function itself)
This means that most building blocks for neural networks are basic linear algebra and not much else (I am simplifying, nowadays we have access to a surprisingly large array of operations).
This paper gives you two new building block, a sorting function and a ranking function. The ranking function might have direct applications for recommender systems.