3 ms·

I find this paper super cool, and highly unintuitive that an operation as discrete as sorting can be done entirely with smooth functions, and efficiently to boo

I find this paper super cool, and highly unintuitive that an operation as discrete as sorting can be done entirely with smooth functions, and efficiently to boot. 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?

mpoteat 7y ago
I view the usefulness as expanding the class of programmatic functions we can differentiate. One usefulness of differentiating programmatic functions is the ability to perform gradient descent optimization on that function... which has applications in operations research for example.
billconan 7y ago
A few months ago, I played with a Julia differentiable programming framework, and I thought what if I make a differentiable virtual machine and use unsorted and sorted numbers as training data. will it learn a sorting algorithm, something similar to deep Turing machine. My conclusion was I can't ....
- etaioinshrdlu 7y ago
  I see no reason why you couldn't make a differentiable virtual machine! Getting it to learn may be quite tricky tho.
  - stev0lution 7y ago
    "We extend the capabilities of neural networks by coupling them to external memory resources, which they can interact with by attentional processes. The combined system is analogous to a Turing Machine or Von Neumann architecture but is differentiable end-to-end, allowing it to be efficiently trained with gradient descent. Preliminary results demonstrate that Neural Turing Machines can infer simple algorithms such as copying, sorting, and associative recall from input and output examples." https://arxiv.org/pdf/1410.5401.pdf https://arxiv.org/pdf/1410.5401.pdf
- mpoteat 7y ago
  The million dollar question is if it's possible to construct a theory of computation where the input language itself is automatically differentiable, and where the execution semantics are also so. Perhaps a continuous spatial automata that has been proven to be Turing complete.
  - deleted 7y ago
    [deleted]
- sjg007 7y ago
  Seems like it should work. A fully connected network would encode all permutations. Interesting.
  - sdenton4 7y ago
    Yeah, the trick is choosing the right one...
huac 7y ago
I think that this means that certain rank-based metrics, e.g. NDCG or AUC, which are very commonly used in ranking or classification, can be represented in a differentiable form. That, practically, means that neural networks can easily optimize directly for those results, instead of (most commonly) minimizing log-likelihood and monitoring for results on NDCG (as in the original formulation of RankNet). My (limited) understanding of LambdaRank is that their model empirically minimizes NDCG, but does not have a strong theoretical backing for why it should work. 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).
- pheug 7y ago
  > My (limited) understanding of LambdaRank is that their model empirically minimizes NDCG, but does not have a strong theoretical backing for why it should work. 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.
currymj 7y ago
they add a regularization term to smooth things out and make the derivative exist. in a sense it’s similar to how argmax is a very discrete operation, but softmax is a good approximation that is differentiable.
bo1024 7y ago
You're right, the paper's messaging is very confusing. 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.

mpoteat 7y ago

I view the usefulness as expanding the class of programmatic functions we can differentiate. One usefulness of differentiating programmatic functions is the ability to perform gradient descent optimization on that function... which has applications in operations research for example.

billconan 7y ago

A few months ago, I played with a Julia differentiable programming framework, and I thought what if I make a differentiable virtual machine and use unsorted and sorted numbers as training data. will it learn a sorting algorithm, something similar to deep Turing machine. My conclusion was I can't ....

etaioinshrdlu 7y ago
I see no reason why you couldn't make a differentiable virtual machine! Getting it to learn may be quite tricky tho.
- stev0lution 7y ago
  "We extend the capabilities of neural networks by coupling them to external memory resources, which they can interact with by attentional processes. The combined system is analogous to a Turing Machine or Von Neumann architecture but is differentiable end-to-end, allowing it to be efficiently trained with gradient descent. Preliminary results demonstrate that Neural Turing Machines can infer simple algorithms such as copying, sorting, and associative recall from input and output examples." https://arxiv.org/pdf/1410.5401.pdf https://arxiv.org/pdf/1410.5401.pdf
mpoteat 7y ago
The million dollar question is if it's possible to construct a theory of computation where the input language itself is automatically differentiable, and where the execution semantics are also so. Perhaps a continuous spatial automata that has been proven to be Turing complete.
- deleted 7y ago
  [deleted]
sjg007 7y ago
Seems like it should work. A fully connected network would encode all permutations. Interesting.
- sdenton4 7y ago
  Yeah, the trick is choosing the right one...

huac 7y ago

I think that this means that certain rank-based metrics, e.g. NDCG or AUC, which are very commonly used in ranking or classification, can be represented in a differentiable form. That, practically, means that neural networks can easily optimize directly for those results, instead of (most commonly) minimizing log-likelihood and monitoring for results on NDCG (as in the original formulation of RankNet). My (limited) understanding of LambdaRank is that their model empirically minimizes NDCG, but does not have a strong theoretical backing for why it should work. 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).

pheug 7y ago
> My (limited) understanding of LambdaRank is that their model empirically minimizes NDCG, but does not have a strong theoretical backing for why it should work. 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.

currymj 7y ago

they add a regularization term to smooth things out and make the derivative exist. in a sense it’s similar to how argmax is a very discrete operation, but softmax is a good approximation that is differentiable.

bo1024 7y ago

You're right, the paper's messaging is very confusing. 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.