Машинное обучение буквально построено на вычислении производных. С помощью backpropagation — алгоритма дифференцирования сложных функций — мы тренируем нейронные сети. Reparameterization trick (он помогает оценить градиенты в нейросетках с семплингом) открыл возможность обучения VAE. Этот пост про статью с ICLR 2019, в которой предложен метод дифференцирования сортировок 😲. Оператор NeuralSort приближенно переставляет компоненты входного вектора так, чтобы они оказались отсортированы. Алгоритм основан на паре красивых лемм и реализовывается на pytorch в десяток строк кода.

У человека, который занимается рекомендациями (меня), от такого учащается пульс и текут слюни. Можно напрямую учить отборщик кандидатов, работающий через kNN. Можно оптимизировать nDCG. Более того, авторы предложили дополнение, которое не просто сортирует компоненты вектора, а семплирует пропорционально этим компонентам. Это именно то, что используется в Boltzmann exploration! В общем, чего-то такого хотелось уже давно.

На практике все оказалось не так легко. С помощью алгоритма из статьи я реализовал лосс, оптимизирующий nDCG, и проверил его на синтетических данных. Оказалось, что алгоритм чувствителен к гиперпараметру, определяющему гладкость перестановки. Если его значение выбрано неправильно, то модель не выучивает даже простую монотонную функцию. Думаю, в реальном рекомендере c сотнями тысяч айтемов этот гиперпараметр будет сложно подобрать. Тем не менее есть работа, в которой утверждается, что подход с оптимизацией nDCG справляется с задачей ранжирования в поиске не хуже стандартных лоссов. Более того, целая серия статей развивает идею дифференцируемых сортировок. Как говорится, we will watch your career with great interest.

P. S. В своих экспериментах я обнаружил, что минимизация nDCG + инверсия предсказаний работает лучше, чем максимизация nDCG. Если у кого-то есть мысли, почему так может быть, напишите, пожалуйста, в комментариях. Исходный код тут.