Самообучение

Применение методов искусственного интеллекта в переборных алгоритмах

Раньше в литературе (например, в "А.Я.Лернер. Начала кибернетики. - М.: Наука, 1967") можно было встретить следующее определение: процесс изменения свойств системы, позволяющий ей достигнуть наилучшего или по крайней мере приемлемого функционирования в изменяющихся условиях, называется адаптацией. В то же время обучение определялось (там же) как передача знаний или приемов решения задач от обучающего к обучаемому. Как видим, самообучением в таком случае можно назвать получение системой информации, помогающей решать задачи, из собственного опыта работы. Теперь, если в определении адаптации изменить соответствующее условие на "в постоянных или изменяющихся условиях", а как субъект процесса изменения свойств указать саму систему, то полученное определение будет также подходить к понятию самообучения. Именно в таком смысле применяется понятие самообучения в современных работах по сложным позиционным играм (например, в "J.B.Pollack, A.D.Blair. Coevaluation of a backgammon player. (Доступна в сети Интернет на странице Comp.Sci.Dept., Volen Center for Complex Systems, Brandies Univ., Waldham)").

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

Одним из самых распространенных подходов к проблеме обучения в подобных ситуациях стал так называемый метод вскарабкивания на холм (hillclimbing, описание программы, играющей в короткие нарды и использующей этот метод, - в "J.B.Pollack, A.D.Blair. Coevaluation of a backgammon player"). Он заключается в следующем. За основу берется некоторый стартовый набор параметров. Затем один из параметров изменяют. Программы с неизмененным и с измененным параметром играют друг с другом. Дальнейшие действия производятся с победившей программой и сводятся к повторению предыдущих шагов. Очевидно, что с каждым шагом программа играет не хуже. Даже более того, в силу сказанного выше о существенности параметров оценочной функции, на каком-то шаге программа непременно должна начать играть лучше. Кроме того, если получено повышение качества игры при изменении некоторого параметра, можно исследовать этот параметр в направлении благоприятного изменения с достаточно маленьким шагом и получить своего рода экстремум по этому параметру с соответствующей выбранному шагу точностью. Вообще, если предположить, что качество игры можно численно оценить, то нашу задачу можно считать задачей поиска максимума этой оценки как функции, зависящей от набора параметров оценочной функции, как от переменных. Теория экстремальных задач предлагает здесь метод покоординатного спуска, возможность использования которого рассматривается далее.

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

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

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

Итак, окончательный вывод выглядит так: при выборе очередного параметра для изменения невозможно учитывать предыдущий порядок выбора параметров. То есть каждый раз, выбирая очередной параметр, мы стоим на распутье, где неоткуда получить никакой априорной информации, куда идти. Два выхода из такой ситуации. Первый: выбрать параметр случайно или попробовать все и остановиться на том, который дает лучший результат. Второй выход сопряжен с огромным расходом времени. Кроме того, что параметров много, не известно, на сколько надо их менять. Таким образом, количество проб в таком случае приблизительно равно произведению числа параметров на число предполагаемых вариантов длины шага. Учитывая то, что каждая проба подразумевает состязание двух программ, которое в свою очередь обычно заключается в проведении нескольких партий, делаем вывод, что перебор всех вариантов - задача трудновыполнимая. Кроме того, даже при таком подходе отнюдь не исключается возможность пропустить верную дорогу, так как она может оказаться "за поворотом", то есть необходимо исследовать все возможности на два шага вперед, на три и так далее. Первый выход по крайней мере выполним. В таком методе обучение программы отдается на волю случая. Этот подход называют также эволюцией в популяции из двух особей (смотрите "J.B.Pollack, A.D.Blair. Coevaluation of a backgammon player"). "Особями" здесь выступают конкурирующие программы, из которых "выживает" сильнейшая, дает "потомство", которое "мутирует", то есть изменяет один из параметров своей оценочной функции.

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

А.В.Мосеев, underwood.narod.ru, 1999 год