6.5.2. Построение последовательных правил решения по конечным выборкам

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

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

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

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

Хант и его коллеги (Хант, Марин и Стоун, 1966; Хант, 1967) провели эмпирические исследования, чтобы выяснить, насколько быстро сходятся к процедуры просмотра на один шаг вперед. В этих экспериментах выбиралось какое-нибудь известное правило для классификации некоторого множества объектов. Затем формировалась выборка, которая предъявлялась алгоритму распознавания образов. В одной из версий эксперимента выборка увеличивалась каждый раз на один объект, пока не находилось корректное правило классификации образов. В другом случае предъявлялась выборка фиксированного размера и при помощи указанного алгоритма строилось правило, которое сравнивалось с корректным правилом классификации. Общий вывод из этих исследований таков: можно получить разумные приближения нелинейных правил классификации при условии, что корректное правило не является „ужасно сложным». Это утверждение неточно по необходимости. Чтсбы придать ему какое-то содержание, опишем один из экспериментов (Хант и др., 1966)

В этом эксперименте множество состояло из векторов х длины 4, каждая компонента которых была целым числом от 1 до 4. Таких векторов всего Каждый вектор был отнесен к классу 1 или 0 при помощи произвольно выбранной процедуры классификации Применялись четыре различных варианта в соответствии с определением четырех обычно использующихся логических связок: и, включающее или, исключающее или и импликация. (В

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

Рис. 6.6. (см. скан) Правила, примененные Хантом, Марином и Стоуном при исследовании сходимости.

Вектор относится к классу 1, если утверждение истинно; в противном случае он относится к классу .

Вектор относится к классу 1, если утверждение или истинно; в противном случае он относится к классу .

Вектор относится к классу 1, если утверждение влечет истинно. По-другому это можно выразить в виде или . В противном случае вектор относится к классу .

Вектор относится к классу 1, если утверждение или истинно; в противном случае он относится к классу .

Правило определяет необходимые условия для принадлежности классу, — достаточные, условия. Правило содержит

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

Эксперимент проводился следующим образом.

1. Из выбиралось некоторое правило. Назовем его

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

3. Пусть — пробное правило классификации, действующее в момент выбора Первоначально объекты принадлежат классу После выбора вектора он подвергался классификации по обоим правилам

4. Если результаты классификации при помощи правил и совпали, то и происходил возврат к шагу 2. В противном случае перед возвратом к шагу формировалось правило путем исследования алгоритмом просмотра на один шаг вперед, описанным в разд. 6.4.

Цикл, состоящий из шагов 2—4, продолжался до тех пор, пока в выборке не оказывалось 10, 20, 30 или 100 объектов. Эксперимент повторялся 10 раз для каждого возможного правила и каждого количества объектов в 5. После каждого повтора подсчитывался коэффициент „вычислительного выигрыша" (ВВ). Пусть — заключительное правило. Тогда

где К — число неверно классифицированных объектов в правилом — число объектов из класса 0 в — число объектов из класса 1 в Коэффициент ВВ можно интерпретировать как эффективность заключительного правила классификации по сравнению с простым правилом „считать все объекты множества членами наибольшего подкласса в указывает на то, что — совершенное устройство классификации. указывает на то, что построенное алгоритмом правило не лучше простого правила „наиболее вероятного выбора", а отрицательный результат означает, что алгоритм действительно построил более плохую процедуру классификации, чем это правило. На рис. 6.7 изображен коэффициент ВВ как функция вида правила и размера выборки. Наблюдается определенная сходимость к корректному правилу, но скорость ее зависит от сложности (неизвестного) корректного правила.

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

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

Рис. 6.7. Коэффициент иллюстрирующий сходимость в исследованиях Ханта, Марина и Стоуна. Цифры соответствуют правилам

Для описания машинного запоминающего устройства, хранящего записи выборок, Дир и Хант ввели термин „банк памяти". Банк памяти можно организовать двумя способами. Можно рассматривать его как файл записей фиксированной длины, в котором в каждой записи отведено место для размещения компонент вектора, а также для дополнительного символа — имени класса. Другой способ — рассматривать банк памяти как совокупность записей переменной длины, где в каждой записи отведено место для имени класса объекта и для некоторых избранных компонент вектора,

описывающего объект. (Дополнительное место требуется еще для информации о длине записей. Более подробно см. Лефковиц (1968).) Дир и Хант обнаружили, что в работах по распознаванию образов, аналогичных работе Ханта и др., пробная гипотеза по мере увеличения размера выборки постепенно приближается к корректной. В частности, соответствующие компоненты вектора обычно появляются в деревьях для прежде чем они будут правильно классифицированы Чтобы применить этот факт, Дир и Хант модифицировали эксперименты Ханта и др.:

1. Вместо предъявления фиксированного числа объектов осуществлялся несколько раз циклический проход по множеству из 256 объектов. Однако число объектов, которые можно было бы одновременно записать в память, ограничивалось. Считалось, что память состоит из фиксированного множества ячеек, каждая из которых способна хранить точно одну компоненту вектора, и запоминание данных модифицировалось следующим образом.

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

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

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

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

Рис. 6.8. Средние ошибки для задачи (Дир и Хант).

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

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