[AI ⊂ TM] Машина Тьюринга и искусственный интеллект

Пререквизиты

Обязательно - основы теории вычислений, искусственные нейронные сети.

Желательно - генетические алгоритмы, RL-агенты.

Почему машина Тьюринга?

Действительно, почему машина Тьюринга (TM) сегодня в теме про искусственный интеллект (AI) ? Ведь AI сегодня это все больше про машинное обучение (ML), искусственные нейронные сети (ANN), LLM, вычисления на CUDA и т. п.

Причина в том, что никакой AI, с точки зрения математики, не превосходит по возможностям TM.

Сужать же тему AI дополнительно до задачи минимизации дифференцируемой функции с помощью одной из модификаций алгоритма градиентного спуска в попытке построить регрессию (это математическое определение "обучения" ANN без лишней лирики), значит еще более ограничивать возможности AI. Из протеста против такого сужения темы, из размышлений над принципиальными возможностями и ограничениями AI родилась небольшое исследование.

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

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

Что не так с ANN?

Родовое проклятие Перцептрона

Первым модель перцептрона (родоначальник ANN) предложил Фрэнк Розенблатт. Его модель была двухслойной, но настраивались только веса связей второго слоя (связи между A и R элементами). Поэтому его модель эквивалентна однослойной нейронной сети с прямой связью. Его перцептрон демонстрировал возможность обучения. В частности, он мог научиться распознавать буквы английского алфавита. Однако, математический анализ возможностей перцептрона показал, что легко находятся задачи, которые перцептрон решает крайне неэкономично. Увеличение количества обучаемых слоев (MLP) и применение процедуры backpropagation расширяют класс эффективно решаемых задач, но не устраняет принципиальных ограничений перцептрона. Кстати CNN сети также являются вариантом MLP, но с дополнительными ограничениями на веса связей, что повышает эффективность ML в случае работы с пространственно-распределенными данными аудио, изображений и видео.

Приведу примеры задач (не единственные и не исчерпывающие), потенциально решаемые с использованием AI, с постепенным ростом сложности по моему субъективному представлению.

Уровень 1. Распознать кошку на 2D-изображении в заданном ракурсе, положении и масштабе. С данной задачей легко справится MLP, сеть Хопфилда (один из ранних вариантов рекуррентных сетей) и CNN.

Уровень 2. Распознать кошку при вариациях ракурса, положения и масштаба. Здесь должна сработать CNN в связке с процедурой augmentation.

Уровень 3. Распознать "кошачий" пазл по случайно размещенным фрагментам пазла. CNN может последовательно преобразовать исходную 2D матрицу изображения пазла в одномерный вектор признаков. Если фрагменты пазла содержат характерные признаки (на рисунке ниже, это могут быть фрагменты глаза и носа), то это облегчит задачу распознавания для CNN. По крайнем мере CNN сможет различать "кошачий" и "цветочный" пазлы. Однако может быть неприемлемая доля ложно-положительных ошибок, когда пазлы будут представлять только животных - собак, кроликов и т. п. у которых имеются похожие признаки. В этом случае произвести надежное распознавание можно только предварительно собрав пазл хотя бы частично, чего CNN самостоятельно сделать практически не может. CNN неплохо справляется со сдвигом изображения (это заложено в структуре операции свертки), теоретически может также хорошо справляться с другими аффинными преобразованиями. В случае же неаффинных преобразований CNN обрабатывает изображения не лучше классического MLP.

RRN, LSTM, NTM, ...

Возможности рекуррентных сетей (RNN) теоретически не уступают возможностям TM, но обучение RNN в общем случае методом backpropagation затрудненно из-за эффектов "затухания" или "взрыва" градиента.

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

Если рассматривать последнее развитие RNN, а именно LSTM и NTM (Neural Turing Machine), то они на мой взгляд хороши в решении задач трансформации последовательностей, при некоторых ограничениях. Во первых, задача должна позволять обрабатывать последовательность строго однонаправленно, читая данные строго последовательно, поэлементно, блоками элементов или некоторым скользящим окном. Во вторых, должна наблюдаться локальность зависимостей. Сочетания значений в соседних позициях последовательности должны быть намного важней для трансформации, чем сочетания значений в отдаленных позициях. Примеры таких задач - прогнозирование временных рядов, перевод и генерация текстов. Это важный, но неполный класс задач, которые мог бы решать AI.

Попробуем заставить NTM работать в режиме приближенном к TM, применяя следующий мета-алгоритм обучения:

1. Шаг инициализации. NTM сохраняет входные данные во внутренний буфер.

2. В цикле с фиксированным количеством итераций:

   1. Контроллер читает буфер исходных данных и текущее содержимое блока памяти

   2. Контроллер обновляет содержимое блока памяти

3. Некий дополнительный модуль читает содержимое блока памяти и формирует окончательный ответ NTM.

4. Вычисляется градиент функции ошибки.

5. Обновляются параметры контроллера и ключи ячеек блока памяти на основе вычисленного градиента функции ошибки.

Схема на первый взгляд выглядит рабочей, однако проблема затухающего градиента ограничивает сверху количество итераций шага 2. Проблемы вычисления градиента для RNN не позволяют NTM достигнуть вычислительных возможностей TM.

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

Прокрустово ложе градиента

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

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

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

Немного из собственной скромной практики

Приведу пример из своей практики, для демонстрации того, что в практических задачах ANN далеко не всегда работают как в рекламе достаточно эффективно. Задача состояла в распознавании антенн приема спутникового сигнала на спутниковых снимках. На входе спутниковый снимок из Google maps, Bing maps или Yandex maps. На выходе координаты обнаруженных спутниковых антенн.

Для решения задачи было решено использовать CNN c архитектурой UNet. Была выполнена ручная разметка для подготовки обучающих данных (примерно 5 000 изображений). Для обучения моделей был выдан доступ к серверу с установленными NVidia GPU c поддержкой CUDA. Вроде все необходимое имелось и проблем не предвиделось.

Изображение самой антенны содержит мало характерных признаков. Это по преимуществу однотонно закрашенный эллипс. Проблема в том, что похожие изображения могут создавать надувной бассейн во дворе, багажный футляр на крыше автомобиля, элементы вентиляции помещений, трубы на крышах домов, цилиндрические баки и др. Таким образом значительная доля информации содержалась в весьма разнообразном контексте (в окружении предполагаемого целевого объекта). Относительно простая UNet в итоге научилась только выделять любые однотонно закрашенные эллипсы, что приводило к неприемлемому уровню ложно-положительных ответов.

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

Попытка использовать архитектуру ResNet или аналогичную потребовала дополнение CNN модулем типа MLP. MLP могла получать от CNN "сжатое" изображение 10x10 с числом каналов в несколько десятков. Но и такое сокращение размера исходного изображения потребовало нескромного количества обучающих данных и интенсивного использования процедуры augmentation.

Таким образом в данной практической задаче метод ANN проявил неэкономичность по отношению к количеству настроечных параметров и, как следствие, жадность к количеству обучающих данных, о чем предупреждали еще Марвин Минский и Сеймур Паперт в далеком 1969 году.

По моему опыту CNN хорошо работают, когда:

• информация содержится в основном в изображении/очертаниях самого целевого объекта

• сам целевой объект имеет ключевые признаки с типичными пространственными соотношениями

• достаточно последовательных преобразований от слоя к слою ядрами небольшого размера (от 2x2 до 5x5)

В иных случаях CNN перестают быть эффективными, хотя за неимением иного эффективного инструмента приходится все равно пользоваться CNN.

Разве TM лучше ? Модификация TM для ML

Кратко напомним, что такое классическая TM.

TM это абстрактное вычислительное устройство, состоящее из следующих компонент:

1. Одномерная и бесконечная в обе стороны лента, поделенная на ячейки.

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

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

4. Конечное множество состояний головки. Выделяют стартовое состояние головки.

5. Таблица переходов, состоящая из набора правил формата — если головка в состоянии S1 считала с текущей ячейки ленты символ A, то перевести головку в состояние S2, записать в текущую ячейку ленты символ B, переместить головку по ленте в положение P.

TM останавливается в случае отсутствия подходящего правила перехода.

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

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

Алгоритмическая универсальность, простота конструкции и локальность обработки данных является привлекательным свойством. Однако в контексте ML классическая TM имеет критические недостатки:

1. Бесконечную ленту трудно реализовать на физическом компьютере.

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

3. TM останавливает работу, если не нашлось подходящего правила перехода. При "ручном" программировании TM это свойство целенаправленно используется, чтобы определить условия остановки TM. Однако в задачах ML такое свойство видится нежелательным. Если ML-модель попытаться реализовать на базе классической TM, то ее обучения будет практически невозможным из-за того, что поверхность функция ошибки ML-модели по преимуществу будет иметь форму "плато". Большинство TM будет преждевременно останавливаться, не давая заметного разброса результатов работы и информации для правильного выбора направления поиска улучшения ML-модели.

4. ML больше работает с действительными числами, векторами и матрицами, а классическая TM работает с дискретным и конечным множеством символов и состояний.

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

6. Представление данных на одномерной ленте плохо подходит для обработки 2D и 3D изображений .

Все выше перечисленные недостатки критичны для ML, однако их можно легко устранить в модифицированной версии TM.

Сначала рассмотрим модификации, связанные с лентами и головками.

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

Далее, для обработки 2D изображений одномерную ленту можно заменить 2-мерным "полотном". Соответственно, для обработки N-мерных изображений потребуется N-мерная "лента".

Можно использовать многоленточную TM с несколькими независимо работающими головками. Каждая головка ленты работает по индивидуальной или одной общей таблице переходов. Здесь можно провести аналогию с ANN. Лента может пониматься как аналог слоя в многослойной ANN (MLP, CNN).

Скрытый текст

Одну ленту можно изменять более чем одной головкой. Количество головок на ленту ничем не ограничено. Головок может быть даже больше, чем доступная длина ленты. Головки работают независимо. Видится разумным ввести ограничение, что все головки одной ленты используют одну общую для ленты таблицу переходов. Также потребуется ввести для правил перехода параметр приоритета, чтобы разрешить конфликт одновременной записи в ячейку ленты. Здесь можно провести аналогию с ANN. Головка ленты может пониматься как аналог нейрона слоя в многослойной ANN (MLP, CNN). Только головки TM, в отличие от нейронов ANN, могут перемещаться.

Наконец можно перейти от дискретных к непрерывным значениям данных. Сами правила переходов могут быть представлены действительными функциями, вместо таблиц. Такие функции на входе получают числовой вектор из данных лент и состояния головки. На выходе функция возвращает числовой вектор, определяющий новое значение для ячейки ленты (скаляр или вектор), новое значение состояния головки (скаляр или вектор) и значение перемещения головки (в общем случае вектор). Перемещение головки можно рандомизировать, если определять перемещение параметрическим распределением случайной величины. Напомним, что TM может быть недетерминированной, без потери вычислительной полноты.

Если не градиентный спуск, то что ?

Спойлер

Альтернативные методы оптимизации

Мы ослабляем требование к функции ошибки, отменяя необходимость ее дифференцируемости. В этом случаем мы не можем, по крайнем мере напрямую, использовать метод обратного распространения ошибки. Что же тогда мы можем применить для настройки нашей модификации TM ?

Рассмотрим, насколько остро стоит проблема поиска TM, решающую заданную задачу.

Количество всех вариантов правил для одно-ленточной TM способной перемещать головку более чем двумя способами.

Вариантов выбора конкретного набора k правил из n возможных правил равно числу сочетаний из n объектов по k.

Мне неизвестны вычислительные устройства, на которых была бы возможна реализация поиска подходящей TM полным перебором для нетривиальных задач. Допустим у нас всего 3 состояния, 3 символа ленты и 3 возможных перемещения головки. Это дает всего 243 возможных правил перехода TM. Если поведение TM должно определяться всего 3-мя правилами, то количество возможных вариантов 2362041. И это для столь простого случая ! Количество вариантов растет экспоненциально от размера задачи.

Посмотрим, что нам предлагает наука оптимизации. Перечислю известные мне "не градиентные" методы, в порядке возрастания практически доступного размера решаемых задач. Перечисленные методы (кроме Хука-Дживса) иногда называют методами глобальной оптимизации, в том смысле, что они не склонны застревать в локальных оптимумах.

1. полный перебор

2. сканирование по решетке с фиксированным шагом

3. случайный поиск

4. имитация отжига, симплекс-метод, метод Хука-Дживса

5. эволюционное программирование

6. генетический алгоритм

7. генетическое программирование

Рассмотрим последние три метода. Эволюционное программирование основывается на операторе мутации. Имеется ограниченное количество вариантов решения (популяция). На каждой итерации алгоритма к каждому варианту применятся мутация для получения новых решений. Затем выполняется отбор лучших полученных решений в новую популяцию. На каждой итерации новые решения выбираются только из окрестности текущих решений (скрещивание не применяется). Пробы могут быть полностью случайны или использовать более направленный метод, например метод Хука-Дживса. Мой опыт говорит, что данный метод хорош только для поиска очень приближенных решений. По мере роста номера итерации вероятность нахождения улучшенного решения быстро снижается.

Генетический алгоритм (GA) повышает эффективность поиска за счет использования оператора скрещивания. Данный оператор позволяет искать улучшенные решения в областях между точками текущих решений, если говорить языком геометрии. При некоторых ограничениях это позволяет приближаться к оптимальному решению без ограничения локальности поиска. Мутация в GA также используется, но здесь ее роль в большей степени сводится к поддержанию разнообразия решений в популяции.

Недостаток GA в том, что он требует представления решения в виде цепочки символов фиксированного алфавита (классический вариант) или в виде числового вектора. Генетическое программирование (GP) снимает это требование. GP требует только чтобы над представлением решения был определен оператор скрещивания, который из двух или большего количества решений "родителей" формировал бы новое решение, сочетающее в себе свойства всех "родителей". Решение может быть представлено в виде древовидной структуры, матрицы, таблицы и др. Лишь бы было можно легко выделять "фрагменты" и создавать из них новое работающее сочетание. Именно GP использовался в далее описанных экспериментах.

Секрет эффективности GA

Скрещивание vs мутация

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

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

Пусть необходимо найти оптимальное решение, которое можно закодировать строкой генов (генотип). Пусть существует единственное оптимальное решение. Назовем "корректным" ген в позиции i некоторого генотипа, если он совпадает с геном в этой же позиции генотипа оптимального решения. Таким образом все гены оптимального генотипа являются "корректными".

Примем гипотезу, что приспособленность генотипа монотонно возрастает по мере увеличения в нем количества "корректных" генов. Другими словами, чем больше у генотипа "корректных" генов, тем больше его приспособленность.

где

fit(g) - fitness-функция приспособленности генотипа g

с(g) - функция подсчета количества корректных генов в генотипе g.

В менее строгой вероятностной форме

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

Теперь посмотрим на картинку ниже. Скрещиваются два генотипа из 5 генов, отличающихся от оптимального генотипа только в одном гене. Вероятность получения оптимального генотипа в результате скрещивания равна 25%. При этом операция мутации любого из этих генотипов приводит к оптимальному генотипу в лучшем случае с вероятностью 20%. Если бы генотипы имели длину 100 генов, то при мутации оптимальный генотип получался бы только с вероятностью не более 1%. При этом для скрещивания шанс успеха не меняется, все те же 25%.

Среднее количество "корректных" генов в генотипе, полученном в результате скрещивания двух неоптимальных родительских генотипов, вычисляется как (m + n) / 2. Здесь m и n количество "корректных" генов в родительских генотипах соответственно. При m = n вероятность получить количество "корректных" генов у потомка больше, чем у обоих родительских генотипов, лежит в границах [25%, 50%).

На любых стадиях поиска GA скрещивание сохраняет вероятность успеха примерно в 25% случаев. Мутация же эффективна только на первых итерациях (эпохах) поиска, так как изначально случайно выбранный генотип легко немного улучшить, но по мере приближения к оптимальному решению вероятность улучшения генотипа при мутации линейно снижается.

Напоминаю, что под "успехом" и "эффективностью" здесь понимается увеличение количества "корректных" генов в популяции генотипов. Но отбор в GA выполняется на основании значения функции приспособленности. Поэтому GA эффективен только в задачах, где фитнесс функция и количество "корректных" генов коррелируют.

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

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

GA vs GD

Попробуем сравнить GA с главным конкурентом в ML — алгоритмом градиентного спуска (GD). Прямое сравнение по единому показателю не получится, так как в случае GA больше интересует зависимость размера задачи и необходимого количества итераций для поиска оптимального решения. Для градиентных алгоритмов же строятся оценки количества итераций в зависимости от целевого уровня ошибки. Но можно попробовать сравнить алгоритмы по самой форме оценок. В какой класс они попадают — линейный, полиномиальный или экспоненциальный?

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

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

Минимизировать расстояние Хемминга можно конечно без всякого GA. Достаточно просто последовательно подбирать тип гена в генотипе последовательно, позиция за позицией. И более эффективного алгоритма для последовательно работающей машины видимо не существует. Но нам нужна легко анализируемая тестовая задача для GA.

Что же показывает на такой модельной задаче GA ? Моя эмпирическая оценка на генотипах длиной от 500 до 3000 позиций и двоичным алфавитом показывает следующую зависимость матожидания количества итераций поиска точного решения от длины генотипа .

Статистическая значимость оценки по критерию Фишера составила 828.33, при критическом значении 6.61. То есть наблюдается практически идеальная линейная зависимость. Такой результат можно объяснить только наличием в GA оператора скрещивания. И этот оператор действительно в ходе всех экспериментов показывал высокие шансы произвести улучшенную версию генотипа, по сравнению с оператором мутации. Мутация была больше необходима для поддержания разнообразия популяции и предотвращения ранней остановки поиска.

Совпадение эмпирических результатов с характеристиками оптимального алгоритма (с точностью до константы), это полагаю отличный результат.

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

Блочная оптимизация

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

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

Вспомним, о чем по сути говорит теорема схем для GA. Она говорит, что в процессе эволюции в генотипах накапливаются по преимуществу полезные (повышающие в среднем значение fitness-функции) и короткие схемы. Если схема слишком длинна, то мутация будет ее разрушать со слишком большой вероятностью, что не позволит ей закрепиться в популяции. Для GP полагаю, данная закономерность остается в силе. Единственный способ обойти ограничение длины схемы, это своевременно переходить на более высокий уровень описания решения GP, то есть искать и затем использовать шаблонные вычислительные блоки как элементы высокоуровневого программирования.

Как этого достичь ? Готовых проверенных ответов у меня сейчас нет. Могу предложить направления исследований.

На низком уровне можно искать в популяции GP повторяющиеся "закрепившиеся" схемы/шаблоны кода (в случае TM, это повторяющиеся правила переходов и группы таких правил). Затем защищать такие блоки от интенсивных мутаций и разрыва при скрещивании. Рекомбинация при скрещивании цельных шаблонов кода, а не отдельных и произвольных их участков, как раз и является переходом на более высокий уровень описания решения GP.

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

RL, Q-learning (DQN, DDPG, TD3 и др.)

Идея возможности использования reforcement learning (RL) метода обучения агентов пришла в процессе написания статьи. Ранее доводилось работать с этими методами, но конкретно опыта применения для оптимизации TM не было. Тем не менее решил, что описать идею будет полезно.

Кратко напомню, что RL есть задача обучения агента эффективному поведению в среде на базе анализа примеров состояния среды, действий и вознаграждения. Q-learning это один из методов решения LR задачи, для случая неизвестной модели среды. Классический Q-learning работает в среде из класса Марковских процессов, с конечным набором дискретных состояний и действий. Алгоритм DQN и его развитие (DDPG, TD3 и др.) есть развитие Q-learning и способ управления агентом в среде с непрерывным пространством состояний и действий.

В классическом Q-learning функция оценки вознаграждения реализуется как таблица, а выбор действия вычисляется как простая функция аргмаксимума (argmax) над списком значений. В DQN все функции (модели critic и actor) реализуются как ANN с непрерывным входом и выходом. Эти функции настраиваются посредством обучения методом backpropagation в связке со стохастическим градиентом. Требование, чтобы процесс смены состояний среды оставался Марковским, остается для всех вариантов Q-learning.

Переформулируем задачу минимизации функции ошибки для TM как задачу оптимизации поведения RL-агента в среде с неизвестной моделью. В таблице ниже показано простое однозначное отображение элементов обеих задач.

Таблица 1. Связь задач минимизации функции и поведения RL-агента.

Среда RL-агента, представленная функцией, в связке с действием в виде корректировки решения, обладает свойством Марковского процесса, что важно для RL-задач. Действительно, текущее значение функции ошибки определяется только текущей точкой вычисления и не зависит от предыдущих точек (на то она и функция).

Предлагаю следующий мета-алгоритма минимизации функции ошибки TM

1. Определяем стартовую рабочую конфигурацию TM. Инициируем RL-агента. Вычисляем функцию ошибки TM для рабочей конфигурации.

2. RL-агент выбирает корректировку рабочей конфигурации TM.

   1. Вычисляем функцию ошибки TM для новой пробной конфигурации.

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

   3. Обучаем RL-агента

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

4. Останавливаемся, если достигнут целевой уровень ошибки, либо достигнуты ограничения на длительность вычислений. Иначе переходим на шаг 2.

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

Может возникнуть вопрос, почему автор предлагает TM как альтернативу ANN, и одновременно предлагает использовать DQN со встроенной ANN, реализующей модели critic и actor ? Дело в том, что здесь модели critic и actor не требуется "знать" всю область оптимизации функции ошибки TM. То есть задача этих моделей намного проще, чем задача TM. Для critic и actor достаточно хорошо моделировать окрестность текущего решения и предложить улучшенное решение в этой области с большей эффективностью, чем эффективность случайного выбора.

После перехода к улучшенному решению конечно сдвинется и локальная область поиска, следовательно изменится "поведение среды". К счастью DQN способен адаптироваться к плавным изменениям поведения среды.

Подобное решение успешно применялось автором в одной следящей системе управления. Но это было давно, модель среды приближалась квадратичной формой (полиномом 2-й степени), а DQN тогда еще не придумали.

Эксперименты

Технический ресурс: офисный ноутбук c 4-я ядрами 2.4 Ghz Intel i5-1135G7 и 8 Gb RAM, python 3.11 c JIT (среда выполнения pypy).

Принцип выбора тестовых задач подчинялся следующим условиям:

1. Задачи не совсем тривиальные для TM.

2. Решение задачи в ходе тестирования можно найти за приемлемое время.

3. Для задач известны точные решения.

4. Для задачи желательно заранее знать эталонную TM, точно решающую задачу при любом размере входных данных.

Из-за 2-го требования пришлось отказаться от задач распознавания образов и перевода текстов. Наличных технических ресурсов не хватило бы для действительно эффектного эксперимента.

Выбор остановился на задачах преобразования двоичных одномерных последовательностей:

1. Инверсия порядка следования символов двоичной последовательности.

2. Инкремент положительного целого числа, представленного двоичной последовательностью (кодирование по схеме двоичной позиционной системы счисления). Результат также должен быть представлен двоичной последовательностью.

3. Проверка простоты положительного целого числа, представленного двоичной последовательностью.

Метод оптимизации — GP. Помимо проверки возможности решения задачи связкой TM+GP, проводилось сравнение с MLP, как классического представителя инструментов Deep ML. Использовалась реализация MLP из библиотеки tensorflow. Структура MLP выбиралась с целью минимизации ошибки обобщения. Структура варьировалась в следующих пределах: скрытых слоев от 1 до 3, количество нейронов в скрытом слое от 5 до 32. В качестве функции активации всех нейронов использовалась ReLU.

Обучение во всех случаях выполнялось методом стохастического градиента Adam, с фиксированным шагом и размером пакета от 32 до 100 примеров.

Таблица 2. Параметры и результаты решения тестовых задач

Безусловно количество и состав экспериментов не является достаточно презентабельным для однозначных выводов. В представленных экспериментах качество работы TM либо немного уступает MLP, либо заметно превосходит (задача инкремента). Другая важная характеристика, TM может обрабатывать данные различного размера без необходимости ее перестройки. MLP в силу ограничений архитектуры, не могут выполнять обработку векторов различной длины. Под каждый размер входного вектора требуется обучать отдельную MLP либо дополнять MLP нетривиальной предобработкой данных (например, применять анализ главных компонент). Конечно, проблему частично решает применение RNN, но только частично.

При решении задачи инверсии порядка символов последовательности с помощью TM возникла сложность. Известно точное решение на базе одно-ленточной TM. Для точного решения известны затраты памяти и количество итераций, в зависимости от размера инвертируемой последовательности. Поэтому изначально для тестирования работы GP генотип кодировал одно-ленточную TM. Функция fitness вычисляла расстояние Левенштейна между полученной и эталонной последовательностью, взятое со знаком минус. Однако выяснилось, что при таком выборе функции fitness и конфигурации TM, функция fitness ведет себя критично неудачно для GP. Небольшое отклонение решения от эталонного приводило к резкому уменьшению значения fitness и приводило к ее локальному минимуму. Дело в том, что "почти правильное" решение обладает свойством генерировать неверные последовательности на всю доступную память ленты, что приводило к скачку значения расстояние Левенштейна. На рисунке 12 точкой A обозначена точка точного решения, а точкой B область локально-оптимального решения. Эволюция GP практически гарантировано приводила к области B, где точность решения составляла 70% вместо 100% при точном решении. Тогда было решено перейти ко второму варианту с много-ленточной TM, правда за счет утери возможности в дальнейшем обрабатывать последовательности произвольной длины.

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

Выводы

ANN мощный инструмент ML, позволяющий решать существенный набор задач. Однако не все задачи в одинаковой степени решаются этим инструментом. В тоже время имеются альтернативные и потенциально более мощные инструменты, хотя и не представленные готовыми программными библиотеками. Если в вашем ML-проекте заложены достаточные траты на R&D, то можно включить в арсенал инструментов представленную в статье идею объединения TM и ML. Если вы человек науки и информационных технологий, то возможно вы захотите развить идею или воплотить ее в полноценной программной библиотеке.

Ссылки

1. Turing machine - Wikipedia

2. Genetic programming - Wikipedia

3. Perceptrons (book) - Wikipedia

4. Siegelmann, H. T. and Sontag, E. D. (1995). On the computational power of neural nets. Journal of computer and system sciences, 50(1):132–150.