УДК 681.3.06
Информационные технологии, №6, 1997
В.Э.
Карпов, канд. техн. наукМосковский Государственный институт электроники и математики
(Технический университет)
ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧЕ ИНДУКТИВНОГО ВЫВОДА
Рассматривается применимость метода эволюционного моделирования к решению задачи индуктивного вывода. В качестве машины вывода используются конечные стохастические автоматы. Приведены некоторые результаты вычислительных экспериментов по индуктивной классификации путем моделирования эволюции множества невзаимодействующих автоматов - автоматного газа, оценены основные параметры моделирования, намечены пути решения общей задачи индуктивного вывода.
1. ВВЕДЕНИЕ
Задача индуктивного вывода заключается в выделении структурных закономерностей на основе анализа множества наблюдаемых данных, движении от частного к общему. В данной работе предлагается реализация системы индуктивного вывода на основе метода эволюционного моделирования. Также приведены некоторые результаты проведенных экспериментов по индуктивной классификации.
Эволюционное моделирование (ЭМ) - это один из методов бионического направления искусственного интеллекта. Основным тезисом ЭМ является замена процесса моделирования сложного объекта моделированием его эволюции [Фогель и др., 1969]. ЭМ реализует процедуру поиска в пространстве решений в виде эволюции множества приближающих решений. Объект, представляющий собой некоторое решение, называется особью, а множество этих объектов образует популяцию. При этом особи имеют возможность размножаться, мутировать при размножении и конкурировать между собой. Именно эти необходимые и достаточные условия, определяющие неизбежность эволюции [Шмальгаузен, 1968] - наследственная изменчивость (мутации), борьба за существование и естественный отбор - лежат в основе методологии ЭМ. Обычно в качестве объектов выступают алгоритмы решения, представленные в той или иной форме.
Базовой операцией эволюционного моделирования является предсказание символов входной последовательности, трактуемых как сигналы внешней среды. Сама же эволюция заключается в самоусовершенствовании предсказывающего объекта, представленного в виде прогностического алгоритма.
Применительно к задаче индуктивного вывода метод эволюционного моделирования заключается в создании машины вывода (МВ) в виде самоорганизующейся системы, распознающей (предсказывающей) символы некоторой входной последовательности - наблюдаемых данных. Тогда объектом ЭМ будет являться некое инициальное экстраполирующее устройство, эволюция которого приводит к созданию оптимальной в рамках данной задачи МВ.
В рамках задачи индуктивного вывода рассмотрим один из методов решения задачи классификации - соотнесения некоторого предъявляемого объекта тому или иному классу [Фор, 1989]. Данная задача решается путем индуктивного построения решающего (распознающего) алгоритма в виде конечного автомата. Индуктивный вывод осуществляется в процессе эволюции множества невзаимодействующих автоматов - т.н. автоматного газа. Будем называть это множество автоматов популяцией, а сами автоматы - особями
.2. АВТОМАТНЫЙ ГАЗ
Автоматный газ представляет собой синхронно функционирующее в дискретные моменты времени множество конечных автоматов, генерирующих выходные сигналы в соответствии с некоторой стохастической матрицей. Классификация входного вектора осуществляется циклически. На каждом такте функционирования на вход автоматов подаются входные сигналы. При этом выходные сигналы также могут сниматься в любой момент дискретного времени.
После
N тактов функционирования цикл заканчивается, и далее особи популяции либо возвращаются в исходное состояние (режим периодического функционирования), либо остаются в текущем состоянии (режим непрерывного функционирования). В результате цикла из N тактов работы автоматы выдают реакцию на N входных сигналов. При этом вводится функция ошибки, устанавливающая соответствие входной и выходной последовательностей - некий функционал видаS(x1,x2,..,xn,y1,y2,...,yn),
где
x1,x2,..,xn - входная последовательность, y1,y2,...,yn - выходная последовательность символов. Функция ошибки определяет величину штрафа, получаемого автоматом за неверное предсказание. Когда величина накопленных особью штрафов превышает некоторое заданное значение, данная особь "умирает" (аналог естественного отбора). Особи периодически размножаются. Полученная в результате партеногенетического размножения особь наследует свойства (т.е. структуру) своего родителя. Однако, при копировании структуры происходят локальные мутации, что обуславливает такой необходимый фактор эволюции, как наследственная изменчивость [Шмальгаузен, 1968; Горбань и др, 1988]. Под локальными мутациями понимается множество элементарных структурных изменений: изменение количества состояний автомата, изменение связей между состояниями и т.п. В свою очередь, роль борьбы за существование играет конкуренция коэффициентов размножения автоматов в условиях ограниченного размера популяции.В результате эволюции популяции (фактически, мы имеем дело с нерегрессивным поиском в пространстве структур [Букатова и др., 1991]) происходит процесс формирования особей, которые с минимальными ошибками классифицируют входные последовательности.
3. ПРИНЦИП СОСТАВНЫХ СРЕД
Рассмотрим среду, в которую погружены эволюционирующие особи. Пусть некий набор элементарных признаков (ЭП)
ji(Xi,Vi) (ji - это двойка: вектор признаков Xi=(x1i,x2i,..,xni) и значение функции принадлежности (номер класса) Vi , Vi=1,..,n) представляет собой некую составную среду C = {j1,j2,..,jm}. Понятие составной среды C отличается от составной среды, введенной Цетлиным [Цетлин, 1969]. Различие это заключается прежде всего в детерминированном характере компонентов составной среды. Функционирование распознающей системы состоит в периодическом случайном выборе очередного элементарного признака ji из среды C и предъявления его множеству автоматов. Данный ЭП можно, в свою очередь, рассматривать как стационарную среду, в которую погружается автомат. Мы же, поскольку речь здесь идет о задаче индуктивного вывода, будем трактовать ЭП ji как очередной пример. Индуктивный вывод будет делаться именно на основе множества примеров C. Итак, автомату A периодически предъявляются примеры среды C, правильность классификации которых служит мерой эффективности распознающего (классифицирующего) алгоритма (или автомата, что суть одно и то же). Будем говорить, что множество ЭП фиксированной и одинаковой размерности представляет собой составную среду (С-среду).Далее рассмотрим задачу бинарной классификации, т.е. задачу соотнесения заданного вектора одному из двух классов, что, во-первых, упрощает сам процесс вывода и, во-вторых, не снижает общности задачи индуктивной классификации. Предварительно введем понятие
t-момента времени - значения локального времени, под которым будем понимать порядковый номер текущего символа анализируемой среды. В отличие от абсолютного значения времени моделирования, t-момент времени характеризует именно текущий вектор признаков, т.е. текущую стационарную среду. Особенностью решающих автоматов является отсутствие выделенных конечных (терминальных) состояний. Любое состояние, вообще говоря, может считаться конечным и становится им по достижении конца входной последовательности. В силу отсутствия выделенных терминальных состояний, каждый переход генерирует выходной символ - значение решающей (или классифицирующей) функции в данный t-момент времени. Поэтому мы будем приписывать в конце каждого правила порождаемой автоматом грамматики значение выходного сигнала.Тестовые последовательности представляли собой множества ЭП - примеры, - которые генерировались либо на основе таблицы истинности некоторых булевых функций нескольких переменных (порождались булевой функцией), либо задавались экспериментатором произвольно. При этом в первом случае элементами векторов ЭП служили значения переменных, а функция принадлежности определялась значением булевой функции. Во втором случае брались последовательности, структура которых определялась исходя из некоторых субъективных соображений экспериментатора. Характерно, что зачастую принципы классификации, порожденные автоматами, совсем не соответствовали заложенным человеком.
4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ
Ниже приведены примеры автоматов, полученных в ходе эволюционного процесса. При этом рассматривался период моделирования эволюции в 400.000 тактов. Из популяций, насчитывающих к концу моделирования по 20 особей, были выбраны автоматы с максимальным временем жизни и минимальным накопленным штрафом. Все они имеют нулевую ошибку классификации. Помимо графов автоматов приводятся также порождаемые ими регулярные грамматики. Вообще говоря, на выходе нас интересуют, с прагматической точки зрения, именно сгенерированные грамматики или набор предикатов. При этом правила порождаемых грамматик дополнены справа значениями выходных символов. В силу того, что мы имеем дело с вероятностными автоматами, то запись типа "
0.4'0, 0.6'1" означает выдачу символа ‘0’ с вероятностью 0.4 и символа ‘1’ с вероятностью 0.6. Если вероятность равна единице, то просто записывается этот символ.Пример 1
. Автоматы были погружены в С-среду, порожденную булевой функцией Y=(x1+x2)(x3+x4).Автомат
A1:
Рис.1. Автомат, реализующий булеву функцию
Y=(x1+x2)(x3+x4)Ниже представлена порождаемая автоматом грамматика:
G1 = (V1,T, P1, S)
V1 = { S,A,B,C }
T = { 0,1 }
P1 = { S®0A/0, S®1B/1, A®0C/0, A®1B/1,
B®0S/1, B®1B/1, C®0C/0, C®1C/0 }
С тем же успехом можно говорить и о генерации Пролог-программ - множества предикатов. Это могло бы выглядеть примерно так:
S([0|X],0) :- A(X,0). S([1|X],1) :- B(X,1).
A([0|X],0) :- C(X,0).
. . . . . . . . . . .
C([_|X],0) :- C(X,0).
При этом второй (выходной аргумент) предикатов обозначает “реакцию” автомата, т.е. значение классифицирующей функции.
Пример 2
. Распознаваемые последовательности состоят из набора единиц и нулей длиной по 10 символов. Составлялись они по следующему принципу: если в последовательности есть серия из идущих подряд трех единиц, то считается, что данная последовательность принадлежит классу K2, иначе мы имеем дело с классом K1.Автомат
A2:
Рис.2. Автомат, распознающий серии из трех единиц
G2 = (V2,T, P2, S)
V2 = { S,A,B }
T = { 0,1 }
P2 = { S
®0S/1, S®1A/0.5’0,0.5’1, A®0B/0, A®1B/0.5’0,0.5’1,B
®0B/0, B®1S/0.5’0,0.5’1 }Пример 3.
Последовательность из 10-ти символов принадлежит классу K2, если после каждой последовательности единиц стоит такое же количество нулей. Иначе мы имеем дело с классом K1.Автомат
A3:
Рис.3. Автомат, проверяющий равенство нулей и единиц
G3 = (V3,T, P3, S)
V3 = { S,A,B,C }
T = { 0,1 }
P3 = { S
®0A/0.5’0,0.5’1, S®1B/0, A®0B/0.5’0,0.5’1,A
®1S/1, B®0C/0.5’0,0.5’1, B®1C/0, C®0S/0.5’0,0.5’1,C
®1S/1 }Типичное изображение процесса эволюции во времени представлено на Рис.4. По оси абсцисс отложено время, по оси ординат - показатель эффективности автомата - значение функционала вида
r
= R0/(R0+Re), (1)умноженного на 100%, где
R0 - количество правильных предположений (классификаций), Re - количество ошибочных предположений. В самом начале процесса эволюции наблюдается хаотическое распределение показателя качества особей. Смертность и рождаемость весьма интенсивны. Однако с течением времени проявляется преобладание более эффективных автоматов, заполняющих экологическую нишу: акты размножения становятся все реже, что обусловливается уменьшением смертности. При этом, если критерием качества отдельной особи Ai в момент времени t является величина вида (1), то критерием качества поведения популяции в целом на временном интервале Dt = t2-t1 может служить величина вида
(2)
где
Чисто визуально о качестве эволюции популяции можно судить по степени разброса показателей
ri во времени.
Рис.4. Процесс эволюции автоматов из Примера 2
На Рис.5. представлены характерные результаты моделирования процесса эволюции. При этом, если на Рис.5.1. и 5.2. показаны абсолютно сходящиеся, устойчивые процессы (показатели эффективности не изменяются, достигнув максимума, т.е. ниша заполнена), то на Рис.5.3 и 5.4 представлены процессы т.н. неустойчивой (несходящейся) эволюции. Будем называть процесс вида 5.3 неустойчивым первого рода, а процесс 5.4 - неустойчивым второго
рода. Различие между ними очевидно.
Рис.5. Основные виды эволюционных процессов
При проведении экспериментов существовала опасность того, что структура генерируемых автоматов будет отражать не внутреннюю логику входных последовательностей, а логику работы переключательной функции (в данном случае - генератора случайных чисел). Однако специально проведенные эксперименты, при которых значения функций принадлежности при каждом очередном предъявлении примера выбирались случайным образом, показали, что этого не происходит - средняя оценка при случайном выборе значений не превышала 50-60-ти процентов правильности предсказаний (вопрос о поведении автоматного газа в условиях полностью недетерминированной среды выходит за рамки данной работы).
5. ПАРАМЕТРЫ МОДЕЛИРОВАНИЯ
Рассмотрим некоторые параметры моделируемой среды и структуры эволюционирующих особей.
1.
Кратность среды Kenv. Данный параметр можно трактовать как количество “осмотров“ анализируемой последовательности. При Kenv>1 не следует при начале очередного “осмотра” устанавливать автомат в начальное состояние (это вполне естественно, ибо при этом теряется сам смысл введения данного параметра). Однако установка автомата в начальное состояние при подаче на его вход последовательности сигналов следующего примера практически не сказывается на его поведении. По крайней мере, выигрыш оказывается весьма незначительным. (Сравните Рис.5.1, на котором показан процесс эволюции автоматов, устанавливаемых в начальное состояние, и Рис.5.2, на котором автоматы в начальное состояние не устанавливаются.)2.
Штраф за неверное предсказание. При увеличении числа сред штраф необходимо уменьшать. В противном случае автомат просто не будет успевать полностью настраиваться на все среды даже при наличии у него оптимальной структуры. Штраф за неверное предсказание можно оценить так:sp = k
ЧMaxS/ Nenv, (3)где
MaxS - максимально допустимый штраф, Nenv - количество сред, k - коэффициент, характеризующий скорость изменения матрицы вероятностей действий, 0<k<1 [Цетлин, 1969].3.
Стартовый сигнал. Судя по проведенным экспериментам наличие или отсутствие выделенного (стартового) сигнала не влияет на скорость сходимости (т.е. эффективность) эволюционного процесса. Иными словами, режим непрерывного функционирования имеет не худшие показатели по сравнению с режимом периодического функционирования (сравните Рис.4. и Рис.5.1).4.
Равномерность длин последовательностей. Скорость эволюции сильно зависит от того, насколько различаются друг от друга длины входных последовательностей данной серии. Чем больше отличаются друг от друга эти длины, тем хуже результаты.ЗАКЛЮЧЕНИЕ
Итак, в данной работе был исследован вопрос применимости метода эволюционного моделирования к решению частной задачи индуктивного вывода - бинарной классификации. На основе проведенных вычислительных экспериментов были оценены основные параметры моделирования эволюции машин вывода в виде конечных стохастических автоматов, намечены пути решения общей задачи индуктивного вывода.
Кроме того, в проведенных экспериментах параллельно решалась задача генерации минимального представления модели входного сигнала, что представляется весьма актуальным для систем, работающих в условиях ограниченной памяти и критичности быстродействия. Осуществлялось это путем введения безусловного штрафа, пропорционального количеству состояний автомата.
СПИСОК ЛИТЕРАТУРЫ