Теория сложности вычислений
Это неожиданный сосед теоремы No Free Lunch. Возможно, вы слышали о проблеме равенства классов P и NP — одной из семи проблем тысячелетия. Она посвящена времени и памяти, которые требуются для решения вычислительных задач. Кстати, за её решение назначена премия в миллион долларов.
В теории сложности есть понятие алгоритмического разрыва: он возникает, когда доказанная нижняя граница трудности задачи оказывается ниже, чем сложность лучшего известного алгоритма для неё. Проще говоря, мы понимаем, что задача в теории не должна быть слишком сложной, но пока не знаем алгоритма, который решает её настолько же эффективно.
Это явление приближает учёных к ответу на вопрос, сколько ресурсов требует задача. Но нас интересует другая сторона: почему один и тот же алгоритм на похожих данных может вести себя по-разному.
Важна природа самой задачи. В ML это называют индуктивным смещением или априорными предположениями. Например:
линейная регрессия предполагает, что зависимости близки к линейнымдеревья решений — что пространство признаков можно эффективно разделить последовательностью простых правилнейронные сети — что сложные зависимости представимы как композиция множества сравнительно простых преобразований⠀⠀⠀Пример со свёрточными
⠀⠀⠀⠀ нейронными сетями
⠀⠀⠀⠀⠀⠀⠀⠀⠀ (CNN)
Механизм их работы довольно прост — мы изобразили его на карточке. Объясним, что происходит.
Представьте фотографию чашки. Если чашка находится в левом верхнем углу изображения, мы всё равно её узнаём. Если она окажется в центре кадра или справа, ничего не изменится: это та же чашка. Для человека это очевидно, для алгоритма — нет.
Обычная полносвязная сеть рассматривает каждый пиксель независимо: перемещение объекта по изображению меняет набор входных данных.
Свёрточная сеть устроена иначе: в неё заранее встроено предположение, что один и тот же объект должен распознаваться независимо от положения. Это свойство называют трансляционной инвариантностью.
Важная деталь: это предположение не следует из данных. Оно заранее заложено разработчиками в архитектуру сети. Именно благодаря этому ограничению CNN работают значительно лучше универсальных полносвязных сетей на изображениях.То есть мы снова сталкиваемся с парадоксом: сила алгоритма рождается не из универсальности, а из его «предубеждений». Чем больше алгоритм знает о структуре решаемой задачи, тем лучше он работает именно на этом классе задач — и тем хуже справляется с задачами, нарушающими эти предположения.
Эта идея выходит далеко за пределы компьютерного зрения:
рекуррентные сети используют то, что данные образуют последовательноститрансформеры предполагают, что элементы последовательности взаимодействуют друг с другом независимо от расстояния между нимиграфовые нейронные сети учитывают связи между объектамиPhysics-Informed Neural Networks (PINNs) напрямую встраивают в обучение известные физические законыВо всех случаях происходит одно и то же: разработчики сознательно жертвуют универсальностью ради эффективности на интересующем их классе задач.
Важно не путать это с теоремой об универсальной аппроксимации.Часто можно услышать: «Нейронная сеть может выучить любую функцию». Это не совсем так. Теорема об универсальной аппроксимации утверждает лишь, что сеть достаточного размера способна представить практически любую непрерывную функцию с нужной точностью.
Но способность выразить решение и способность эффективно его обнаружить — совершенно разные вещи.
Но если под каждую задачу нужны свои предположения, почему современные большие модели выглядят всё более универсальными?
Накидайте 🔥, если интересно, и мы раскроем ответ в следующем посте. А от читателей, работающих с нейросетями, ждём догадки в комментах!
#как_устроено
