Задача оптимизации, память и спиновые стекла06.09.2015 02:18

Физик Михаил Фейгельман о процессе охлаждения спинового стекла, интенсивности динамического шума и нейронных сетях с точки зрения статистической физики

Спиновые стекла — это модель системы, очень сильно неупорядоченная. Если буквально, то это набор магнитных стрелочек, которые взаимодействуют друг с другом случайным образом — положительным и отрицательным — и в результате, если посмотреть на них при достаточно низких температурах, образуют какое-то замерзшее, но неупорядоченное состояние. Замерзшее в том смысле, что каждая стрелочка смотрит в среднем времени в какую-то определенную сторону, а неупорядоченное значит, что каждая эта стрелочка смотрит в случайную сторону. Если попытаться установить их среднюю намагниченность, то она будет равна нулю.

Теоретические исследования самых простых моделей таких систем привели к любопытному результату: возникающие в них замерзшие состояния устроены иерархическим или древовидным образом. Вскоре после осознания этого обстоятельства люди поняли, что полученные результаты или идеи этих результатов можно приложить к совсем другим областям деятельности. Например, есть задача поиска оптимума чего-нибудь, есть множество параметров, которые нужно как-то так выбрать, чтобы какая-нибудь целевая функция стала максимальной. Простейший пример — задача коммивояжера: как ему, бедняге, объездить за самое короткое время заданное количество городов? И вообще таких задач бессчетное количество, и многие из них могут быть сформулированы в более или менее физических терминах.

Скажем, возьмем эту целевую функцию, которую надо максимизировать, напишем минус перед ней и будем считать, что это энергия, которую надо минимизировать. Как устроена стандартная, самая тупая конструкция с поиском вот такого минимума? Каждый раз нужно попробовать чуть-чуть изменить состояние, найти направление, в котором наша энергия уменьшается, и пойти туда. Потом еще раз. Это называется наискорейший спуск. Сложные задачи характерны тем, что там это наилучшее состояние плохо определено, а точнее говоря, есть очень много состояний, которые в какой-то окрестности будут похожи на наилучшее. А на самом деле самое наилучшее — оно, может быть, даже и единственное, но по дороге к нему есть так много каких-то промежуточных локальных минимумов, что до этого глобального можно никогда не добраться. Значит, решение такой задачи при помощи такого простейшего наискорейшего спуска практически гарантированно приводит в один из каких-то локальных минимумов, где алгоритм останавливается. Типичным образом полученные значения целевой функции будут далеко не лучшими. Энергия останется еще довольно высокой. Как получить лучший результат?

Идея возникла из сравнения с этими фазовыми переходами в стеклах и спиновых стеклах. Идея стала называться simulated annealing. Она состоит вот в чем. Если мы посмотрим на физическую систему, скажем, как стекло получается при быстром охлаждении жидкости, есть много случаев, когда медленное охлаждение той же самой жидкости приводит к кристаллическому состоянию, а быстрое — к стекольному. То есть стекольное состояние оказывается более вероятным достижимым минимумом, если попробовать достичь минимума быстро, а минимальная же энергия будет в состоянии кристаллического. Возникла мысль, что в задачах оптимизации более-менее общего вида можно поступить аналогичным образом. То есть не говорить, что мы сразу будем искать всякий раз направление, которое достоверно приводит к уменьшению нашей энергии, а мы будем рассматривать эту систему как статистическую при некоторой температуре. Иначе говоря, введем в систему динамический шум и будем интенсивность этого шума понемногу уменьшать, то есть мы промоделируем на этой нашей системе медленное охлаждение жидкости или спинового стекла.

Хотя на каждом отдельном шаге такого мероприятия вы, казалось бы, делаете хуже: добавили шум, возникли какие-то неконтролируемые флуктуации, но результат всего процесса за достаточно большое время оказывается куда лучше. Вы можете найти состояние с существенно более низкой энергией или более высокой вашей исходной целевой функции.

Динамические флуктуации, которые вы сначала позволили, а потом стали постепенно выключать, позволяют системе самой находить выход из локальных тупиков.

Какой-то такой локальный минимум, с которым она при простейшем подходе застревает. Если добавить некоторое количество шума, то система сможет с достаточной вероятностью из этого локального минимума выскочить, пойти дальше, найти минимум, который получше. Насколько я помню, идея такого подхода к задачам оптимизации возникла тоже где-то в районе 1983–1984 года и получила вполне серьезное распространение.

Другое применение спиновых стекол, возникшее примерно в те же годы, — оно возникло из работы американского физика Джона Хопфилда, который предложил посмотреть на то, что давно называлось нейронными сетями с точки зрения статистической физики. Иначе говоря, есть какая-то очень простая модель мозга: каждый элемент бинарный, плюс один и минус один или ноль и единица. До того эта задача, как я понимаю, изучалась, конечно, миллиардами людей, но именно как задача динамики. То есть мы пишем алгоритм, по которому данный k-тый нейрон переключается, если на него действуют такие-то входные импульсы от всех остальных. И там можно проводить много всяких численных моделирований. Особенно чем сильнее компьютеры, тем, естественно, веселее этим заниматься.

Хопфилд предложил посмотреть на эту задачу с точки зрения статистической физики и сформулировал вопрос таким образом: пусть мы хотим создать систему распределенной памяти или ассоциативной памяти, что примерно то же самое, которая содержит в себе n штук бинарных элементов, и мы хотим, чтобы взаимодействие между этими элементами, условными нейронами, было устроено таким образом, чтобы у нашей системы было некоторое количество (k штук) запомненных ею состояний, то есть каких-то распределений нулей и единиц по системе. Понятно, если всего их n элементов, то общее количество состояний в такой системе — это 2n, а мы хотим выяснить, сколько мы можем записать различных таких картинок, то есть распределений нулей и единиц по системе, таким образом, чтобы, если мы начинаем с какого-то произвольного начального состояния, начального распределения этих нулей и единиц, заставляем эту систему эволюционировать в соответствии с тем, как устроены в ней взаимодействия, то она придет к одному из этих k состояний — по-видимому, к тому, к которому она была ближе в начальный момент.

Возник, конечно, вопрос. Во-первых, как конкретно должны быть устроены взаимодействия между этими нашими нулями и единицами, для того чтобы формировались такие картинки? Это нетрудно написать. В особенности это написать просто, если таких состояний там совсем немного — одно, два, три. Дальше возникает вопрос:, а сколько мы их можем записать так, чтобы они не слишком друг другу мешали? Всего состояний 2n, так сказать, микросостояний. Но сколько из них можно сделать более-менее стабильными и воспроизводящимися, такое воспоминание? Воспоминание состоит в чем? Скажем, мы резко просыпаемся и пытаемся вспомнить, о чем мы в прошлый раз думали. Вот это «о чем думали» сохранилось в виде нескольких каких-то отпечатков. Оказалось, что если делать совсем простым, то количество таких возможных картинок, которые действительно можно запомнить, всего лишь пропорционально числу элементов и, более того, представляет от него некоторую долю, примерно одну седьмую числа элементов.

Если попытаться запихнуть в эту систему памяти больше разных образов, то она перестает работать, точнее говоря, вместо каких-то хорошо определенных записанных картинок происходит каша наподобие того самого спинового стекла. Можно немного это ограничение перехитрить, если записывать картинки не совсем как попало, а устраивать некоторые между ними корреляции. Конечно же, было с самого начала понятно, что само по себе предложение рассматривать систему памяти буквально по аналогии со статистической механикой в равновесии — это довольно сильная гипотеза. Неизвестно, с какой бы стати реальные системы памяти должны вообще описываться таким образом. Но как модель, которая очень много качественных свойств такой ассоциативной памяти правильно воспроизводит, это вполне сработало. И конечно, ключевое, с точки зрения физика по крайней мере, отличие реальной системы от тех, которые я описывал, — это то, что реальная система не в равновесии, она принципиально не описывается равновесной статистической физикой. Это не означает, что ее вообще нельзя описать. Просто это описание оказывается существенно более сложным.

Эти два примера про системы ассоциативной памяти и задачи оптимизации вовсе не единственные. Есть еще примеры того, как теория, созданная для описания на первый взгляд никому не нужных, кроме десятка физиков, систем, приводит к идеям и применениям, имеющим довольно-таки широкое значение. Это в том числе пример того, почему вредно и не нужно всякого научного работника спрашивать, какую конкретную пользу он принес в текущий квартал. Результаты, особенно наиболее интересные, бывают неожиданны.

Михаил Фейгельман