9.1. Алгоритм CORAL [108]

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

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

 и .

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

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

Можно потребовать, чтобы алгоритм делал для каждого образа не по одному, а по несколько покрывающих наборов. Это требование перекликается с высказыванием Р. Фейнмана [155] о том, что мы можем говорить, что понимаем явление, если в состоянии объяснить его несколькими разными способами. С этой целью после получения первого покрытия исключаем из рассмотрения первый признак, включенный в это покрытие, и процесс поиска закономерностей начинается с другого случайно выбираемого признака.

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

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