3.1.1. Предъявление обучающего множества

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

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

Выработку процедуры классификации на основе фиксированной выборки обычно относят к статистике, а не к искусственному интеллекту. Опубликовано много работ, в которых излагаются соответствующие методы (например, Андерсон, 1958; Тацуока, 1971), особенно для задач, в которых можно использовать евклидовы пространства описаний. Статистиков также интересовал и другой, тесно связанный с этим вопрос. Обнаруживают ли члены, относящиеся к разным группам, систематические различия при измерении одной зависимой переменной? Этот вопрос очень важен для экспериментальных исследований, где „классификация" проводится с данными, получаемыми при меняющихся экспериментальных условиях.

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

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

Можно построить устройство распознавания образов, в котором

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

Способ, которым устройство распознавания образов изменяет пробное правило классификации, в большей мере определяется величиной информации, которую оно способно запомнить. В каждом случае, когда новый объект предъявляется для классификации, устройство распознавания получает какую-то информацию об окружающей среде — хотя бы только для улучшения оценки частоты появления объектов определенного типа. Как должна записываться такая информация? Вообще говоря, существует два способа. Один из них — детальный метод, при котором информация о каждом объекте записывается в момент его предъявления. Например, врач обычно записывает результат каждого обследования и диагноз. Другой метод—статистический; он предполагает хранение обобщенной статистики, связанной с каждым классом и представляющей собой результат некоторого усреднения данных всех наблюдавшихся до настоящего момента случаев в соответствующем классе. Здесь примером может служить бюро погоды, строящее свои прогнозы на типичных показателях. Вместо хранения подробной информации об одном дне для обновления представлений о „типичном“ дождливом или ясном дне используется информация о каждом новом дне.

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

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

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

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