Почему нейросеть, которая распознаёт картинки, может провалиться на другой задаче? Вчера мы уже приблизились к догадке — всему виной опять математика. А точнее...

Теория сложности вычислений 👀

Это неожиданный сосед теоремы No Free Lunch. Возможно, вы слышали о проблеме равенства классов P и NP — одной из семи проблем тысячелетия. Она посвящена времени и памяти, которые требуются для решения вычислительных задач. Кстати, за её решение назначена премия в миллион долларов.

📃 В теории сложности есть понятие алгоритмического разрыва: он возникает, когда доказанная нижняя граница трудности задачи оказывается ниже, чем сложность лучшего известного алгоритма для неё.

Проще говоря, мы понимаем, что задача в теории не должна быть слишком сложной, но пока не знаем алгоритма, который решает её настолько же эффективно.

Это явление приближает учёных к ответу на вопрос, сколько ресурсов требует задача. Но нас интересует другая сторона: почему один и тот же алгоритм на похожих данных может вести себя по-разному.

Важна природа самой задачи. В ML это называют индуктивным смещением или априорными предположениями. Например:

▶️линейная регрессия предполагает, что зависимости близки к линейным
▶️деревья решений — что пространство признаков можно эффективно разделить последовательностью простых правил
▶️нейронные сети — что сложные зависимости представимы как композиция множества сравнительно простых преобразований

⠀⠀⠀Пример со свёрточными
⠀⠀⠀⠀ нейронными сетями
⠀⠀⠀⠀⠀⠀⠀⠀⠀ (CNN)

Механизм их работы довольно прост — мы изобразили его на карточке. Объясним, что происходит.

Представьте фотографию чашки. Если чашка находится в левом верхнем углу изображения, мы всё равно её узнаём. Если она окажется в центре кадра или справа, ничего не изменится: это та же чашка. Для человека это очевидно, для алгоритма — нет.

Обычная полносвязная сеть рассматривает каждый пиксель независимо: перемещение объекта по изображению меняет набор входных данных.

Свёрточная сеть устроена иначе: в неё заранее встроено предположение, что один и тот же объект должен распознаваться независимо от положения. Это свойство называют трансляционной инвариантностью.

*️⃣Важная деталь: это предположение не следует из данных. Оно заранее заложено разработчиками в архитектуру сети. Именно благодаря этому ограничению CNN работают значительно лучше универсальных полносвязных сетей на изображениях.

То есть мы снова сталкиваемся с парадоксом: сила алгоритма рождается не из универсальности, а из его «предубеждений». Чем больше алгоритм знает о структуре решаемой задачи, тем лучше он работает именно на этом классе задач — и тем хуже справляется с задачами, нарушающими эти предположения.

Эта идея выходит далеко за пределы компьютерного зрения:

▶️рекуррентные сети используют то, что данные образуют последовательности
▶️трансформеры предполагают, что элементы последовательности взаимодействуют друг с другом независимо от расстояния между ними
▶️графовые нейронные сети учитывают связи между объектами
▶️Physics-Informed Neural Networks (PINNs) напрямую встраивают в обучение известные физические законы

Во всех случаях происходит одно и то же: разработчики сознательно жертвуют универсальностью ради эффективности на интересующем их классе задач.

*️⃣Важно не путать это с теоремой об универсальной аппроксимации.

Часто можно услышать: «Нейронная сеть может выучить любую функцию». Это не совсем так. Теорема об универсальной аппроксимации утверждает лишь, что сеть достаточного размера способна представить практически любую непрерывную функцию с нужной точностью.

Но способность выразить решение и способность эффективно его обнаружить — совершенно разные вещи.

Но если под каждую задачу нужны свои предположения, почему современные большие модели выглядят всё более универсальными?

Накидайте 🔥, если интересно, и мы раскроем ответ в следующем посте. А от читателей, работающих с нейросетями, ждём догадки в комментах!

#как_устроено