1.5.2.Варианты реализации систем обобщения
Существуют различные подходы к решению задачи об отнесении объекта к некоторому классу. Самым простым вариантом системы, решающей задачу распознавания, являются системы без обучения. В таких системах заранее известны классы, к которым могут относиться предъявляемые объекты, а также критерии отнесения объекта к классу.
Более сложными являются системы с обучением. В системах с обучением не задан алгоритм разделения предъявляемых объектов на классы. Процесс создания и оптимизации такого алгоритма и называется обучением. Для обучения используется определенный набор объектов, называемый обучающим множеством или обучающей выборкой. В свою очередь системы с обучением делятся на: системы обучения без учителя и обучения с учителем.
1.5.2.1 Обучение "без учителя": основные понятия
Главное отличие обучения «без учителя» от обучения «с учителем» в том, что исходная информация представлена в виде обучающего множества, не разделенного на классы. Это значит, что для объектов обучающего множества не задано, к каким классам они принадлежат. Задача обучения в этом случае сводится к разделению объектов выборки на группы объектов, «сходных» друг с другом по каким-либо общим признакам. Более точно задача алгоритмов данного типа формулируется следующим образом.
Пусть обучающая выборка содержит M объектов:
Каждый из этих объектов представляет собой n-мерный вектор Хi значений признаков:
Где
–
значение j-го
признака для i-го
объекта, n
– количество признаков, характеризующих
объект.
Требуется в соответствии с заданным критерием разделить набор на классы, количество которых заранее не известно. Под критерием подразумевается мера близости всех объектов одного класса между собой. Будем считать, что работа алгоритма завершена успешно, если классы, сформированные в результате работы алгоритма, достаточно компактны и, возможно, выполнены некоторые дополнительные критерии.
При решении задачи обучения «без учителя» самыми несложными являются алгоритмы, основанные на мерах близости. Для достижения цели – компактного формирования классов – вводится понятие точки-прототипа, или точки в n-мерном пространстве признаком, являющейся наиболее «типичной» представительницей построенного класса. В дальнейшем расстояние от объекта до класса будет заменяться расстоянием от объекта до точки-прототипа. Точка-прототип может быть сопоставлена каждому сформированному классу, и при этом вовсе не обязательно существование реального объекта, соответствующего точке-прототипу.
1.5.2.2. Обучение "с учителем": постановка задачи
Пусть имеется множество объектов, состоящее из положительных и отрицательных примеров формируемых понятий. Назовем такое множество обучающей выборкой. На основании обучающей выборки необходимо построить понятие [11], разделяющее положительные и отрицательные объекты.
В основе процесса обобщения лежит сравнение описаний исходных объектов, заданных совокупностью значений признаков, и выделение наиболее характерных фрагментов этих описаний. В зависимости от того, входит или не входит объект в объем некоторого понятия, назовем его положительным или отрицательным объектом для этого понятия.
Пусть О – множество всех объектов, представленных в некоторой системе знаний, V – множество положительных объектов и W – множество отрицательных объектов. Будем рассматривать случай, когда О = V W, V W = 0, W = Wi и Wi Wj = 0 (i ≠ j). Пусть K – непустое множество объектов, такое, что K = K+K–, где K+ V и K– W. Будем называть K обучающей выборкой. На основании обучающей выборки надо построить правило, разделяющее положительные и отрицательные объекты обучающей выборки.
Понятие, таким образом, сформировано, если удалось построить решающее правило, которое для любого примера из обучающей выборки указывает, принадлежит ли этот пример понятию или нет. Алгоритмы, которые мы исследуем, формируют решение в виде правил типа «ЕСЛИ условие, ТО искомое понятие». Условие представляется в виде логической функции, в которой булевы переменные, отражающие значения признаков, соединены логическими операциями конъюнкции, дизъюнкции и отрицания. Решающее правило является корректным, если оно в дальнейшем успешно распознает объекты, не вошедшие первоначально в обучающую выборку.
После того, как распознающее правило на обучающей выборке построено, проводится экзамен – с помощью распознающего правила надо разделить объекты новой, экзаменационной выборки на примеры и контрпримеры. Если решающее правило правильно проводит такое разделение, обучение заканчивается. Если результат экзамена неудовлетворителен, то можно проводить дополнительное обучение на новой обучающей выборке (например, к исходной обучающей выборке можно добавить примеры, на которых при распознавании возникали ошибки).