Символьные вычисления при помощи нейронных сетей

Нейронные сети хороши в решении статистических задач, в распознавании и генерации речи и изображений. В новой статье, опубликованной на arxiv.org, исследователи из Facebook AI Research показали, что нейросети позволяют получать отличные результаты также в символьном интегрировании и решении дифференциальных уравнений. Причём результаты нейросетей превосходят результаты в решении аналогичных задач коммерческих систем компьютерной алгебры, таких как Matlab или Mathematica.

Сама идея «механизировать» символьные вычисления появилась ещё на рубеже девятнадцатого и двадцатого веков.

В чём тут смысл?

Если у нас есть некоторое арифметическое выражение, например

2 + 10 × 6,

то для получения ответа нам не обязательно привлекать лучшего математика планеты. Вообще говоря, сойдёт и аккуратный исполнитель, который проводить математические исследования, быть может, и не умеет, но зато способен точно исполнять инструкции вида: «если встретились два числа, разделённые знаком +, то надо следовать алгоритму [описание алгоритма сложения в столбик]», или: «если встретились два числа, разделённые знаком ×, то надо следовать алгоритму [описание алгоритма умножения в столбик]».

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

Однако «арифметикой чисел» дело не ограничивается. Превратить в конвейер можно и «арифметику символов». Это несколько сложнее, однако вполне достижимо.

Для этого выражение, содержащее не только числа и знаки операций с ними, но и буквы, следует трактовать, как «текст» на некотором языке, для которого определены правила допустимых «замен».

Например, правило может быть таким:

a_ × c_ + b_ × c_ → (a+b) × c

Это правило трактуется следующим образом: «если нам встретилось какое-то выражение, в дальнейшем называемое a, потом символ ×, потом ещё какое-то выражение, называемое c, потом символ +, потом какое-то выражение, называемое b, потом символ ×, потом точно то же, что и в прошлый раз, выражение c, то такую конструкцию можно заменить на (a + b) × c, где на место a, b и c подставлены соответствующие выражения».

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

2 × x + (3+y) × x

и поймём, что его можно преобразовать в

(2+3+y) × x,

поскольку 2 играет роль a в вышеописанном правиле, (3 + y) — роль b, а x — роль c.

Задав через такие правила все возможные алгебраические преобразования, мы можем поручить «работнику конвейера» перебрать все возможные трансформации интересующего нас выражения: пусть он возьмёт выражение, найдёт все места, соответствующие правилу 1, и применит к ним это правило, получив столько возможных «альтернатив» для исходного выражения, сколько было найдено таких мест. Потом он то же самое проделает с правилом 2. И так далее, пока не переберёт все правила. Потом пусть с каждым элементом получившегося списка «альтернатив» он проделает то же самое.

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

Среди них мы можем найти, например, самую короткую форму — это будет «конвейерное» упрощение выражений. Или, если в выражении был знак «=», то мы можем найти такое преобразование, где слева от «=» стоит «x», и это будет решением уравнения относительно x.

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

И такие системы на данный момент реализованы в относительном изобилии: Mathematica, Maple, Matlab и ряд других программ/библиотек содержат реализацию данного алгоритма вместе с довольно обширным набором правил преобразования, позволяющий им упрощать выражения, решать уравнения, брать производные и т. п.

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

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

В шахматах, как мы знаем, это сработало. И вот недавно группа исследователей, состоящая из Гийома Лампла (Guillaume Lample) и Франсуа Шартона (François Charton), попробовала проделать аналогичное с символьным интегрированием и решением дифференциальных уравнений.

Существуют способы записи математических выражений в «линейной» форме.

Например, выражение

Может быть записано, как

(a+b)/c

Если пойти дальше и ввести понятие «бинарных» (с двумя аргументами) и «унарных» (с одним аргументом) операторов, то форма записи может стать ещё более регулярной.

Divide(Plus(a,b),c)

А отсюда уже один шаг до того, чтобы прийти к записи

Divide,Plus,a,b,c

Здесь уже нет понятия «приоритета операций» («сначала выполняется умножение, а потом сложение», и т. п.) и скобок, однако всё равно любая запись в такой форме имеет единственный смысл и, наоборот, любое математическое выражение можно преобразовать в такую форму.

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

Мэйнстримом машинного перевода сейчас являются нейронные сети, преобразующие одну последовательность слов в другую.

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

На простом примере это можно представить так. Есть у нас набор точек на плоскости.

Мы, предположим, видим, что они расположены вроде бы почти на одной прямой. Мы можем взять уравнение прямой

y(x) = a × x + b

и попытаться подобрать a и b так, чтобы получившаяся прямая прошла как можно ближе ко всем этим точкам.

Сначала мы берём какие-то случайные числа в качестве a и b, потом берём первую известную нам точку и смотрим, как сильно игрек, вычисленный от её икса, отличается от того, который нам известен. После этого слегка подправляем a и b, чтобы отклонение стало поменьше. Потом берём вторую известную нам точку и повторяем для неё то же самое. И так далее, пока отклонения не станут достаточно для нас малыми.

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

Однако роль «иксов» и «игреков» могут играть не просто какие-то числа, а номера слов языка (предположим, что мы все возможные слова пронумеровали), роль же входных данных в этом случае будет играть набор предложений, переводы которых нам известны (например, их сделал человек-переводчик).

Правда, нейронная сеть в данном случае будет использоваться не для «угадывания» номера слова, а для оценки того, насколько хорошо слово с таким-то номером подходит к ситуации.

Тогда для перевода каждого слова в предложении мы можем пройти по всему списку слов второго языка и выбрать те, которым нейронная сеть проставила наилучшие оценки, в качестве гипотез. И повторять это, пока не получится предложение с наилучшей совокупной оценкой.

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

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

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

Нейронная сеть, которая «помнит контекст», как раз и была использована для символьных вычислений в данном исследовании.

Однако что взять в качестве данных для обучения такому «переводу»?

Тут, внезапно, ситуация даже проще, чем с естественными языками. Ведь для генерации набора примеров на последних нам нужен человек-переводчик, предоставивший нам правильные переводы фраз, которые будут использоваться для обучения нейронной сети делу оценки гипотез. В случае же с математическими выражениями мы можем просто генерировать их случайным образом, потом автоматически брать их производную (в отличие от интегрирования, взятие производной — гораздо более простая операция) и считать её входным «подынтегральным» выражением с известным ответом (этим самым случайным выражением).

Кроме того, мы можем сгенерировать случайные выражения и попытаться взять их интеграл при помощи систем компьютерной алгебры, отбирая в данные для обучения те, с которыми используемая нами система справилась.

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

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

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

Более того, согласно авторам исследования, этот метод справлялся с целым рядом тех выражений, с которыми не справлялись наиболее мощные из существующих системы компьютерной алгебры.

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

Тем не менее, результаты всё равно впечатляют и вдохновляют: 99,6% успешных взятий интеграла у этой системы против 84% у Mathematica (с ограничением в 30 секунд) и 65,2% у Matlab.

97% успешных решений дифференциальных уравнений первого порядка против 77,2% у Mathematica.

81% успешных решений дифференциальных уравнений второго порядка против 61,6% у Mathematica.

Наконец, весьма интересна и ещё одна составляющая данного процесса.

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

Лекс Кравецкий :