Почему все используют градиентные методы для обучения больших моделей?

🤩 Продемонстрирую наглядно на примере решения задачи Multidimensional Scaling (MDS). В этой задаче нам надо нарисовать на плоскости объекты, про которые мы знаем только насколько каждый из них далеко друг от друга. Т.е. на входе у нас матрица попарных расстояний, а на выходе координаты объектов на плоскости. Причем эти координаты должны быть такими, чтобы соотношения расстояний между объектами оставалось как можно более близким к исходным. В качестве функции потерь выступает сумма квадратов отклонений расстояний между городами при текущих координатах и заданным значением.

f(X) = ∑ₘ ∑ₙ (Dₘₙ − dₘₙ(X))²

🗣 Несмотря на увеличение размерности, вся траектория метода может быть наглядно продемонстрирована на плоскости. Количество переменных в задаче здесь - 2*(количество городов), т.к. для каждого из городов мы ищем 2 координаты на плоскости.

↗️ По очереди запускается обычный градиентный спуск, требующий знания градиента, и метод Нелдера-Мида из scipy (широко используемый безградиентный метод). Сначала задача решается для 6 самых населенных европейских городов, потом для 15 и для 34 (это все города-миллионики Европы из википедии).

🤔 Видно, что чем больше городов на карте (чем больше размерность задачи), тем больше разрыв между градиентным и безградиентным методами. Это одна из главных причин, по которой для решения задач большой размерности нам нужны не только значение минимизируемой функции, но и её производная.

🤔 Оказывается, у градиентных методов (при наборе разумных предположений) количество итераций, необходимое до сходимости метода, не зависит напрямую от размерности задачи. То есть если вы рассмотрите корректно настроенный градиентный спуск на десятимерной задаче, то ему нужно будет, скажем, не более 20 итераций для сходимости. А если вы возьмёте условно ту же задачу, но 100500-мерную, то ему нужны будут те же 20 итераций. Конечно, стоимость одной итераций растет с ростом размерности задачи, но хотя бы их количество явно не растет.

🤩 Ставь реакцию, если видишь свой город.
💩 Код для построения анимации