Глава 6. ПОСЛЕДОВАТЕЛЬНОЕ РАСПОЗНАВАНИЕ ОБРАЗОВ

6.0. Последовательная классификация

Можно считать, что алгоритмы параллельной классификации образов предназначаются для машин типа изображенной на рис. 6.1. Классифицируемый объект предъявляется на входы множества из детекторов признаков, которые независимо и параллельно вычисляют измерений, определяющих вектор описания Измерениям приписываются веса и определяется взвешенная сумма. Если сумма превышает некоторый порог , то объект считается членом класса 1; в противном случае объект считается членом класса 0. Рассмотрим машину иного типа, изображенную на рис. 6.2, - машину последовательной классификации образов. Это устройство также содержит детекторы признаков, однако они связаны друг с другом более сложным образом. Сначала ко всем объектам применяется детектор признаков 1 для определения измерения которое в свою очередь поступает на вход правила переключения, определяющего, в какой из нескольких возможных интервалов попадает значение (Или можно считать, что интервал изменений ограничивается некоторым множеством целых чисел, так что правило переключения просто отмечает значение соответствующего измерения.) В зависимости от результата переключения для произведения следующего измерения будет выбран один из нескольких детекторов признаков. Правило переключения будет применено ко второму измерению для того, чтобы выбрать третье, и т. д. до тех пор, пока не будет получено достаточно информации для проведения классификации. Последовательную машину можно описать, задав правило - переключения и расположения каждого детектора признаков в дереве тестов. Ясно, что последовательная машина сложнее параллельной, которую можно описать, просто задав весовой вектор Кроме того, она мощнее параллельных машин, поскольку для любой параллельной процедуры

(кликните для просмотра скана)

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

В этой главе мы будем заниматься последовательными классификациями образов и процедурами распознавания. Если не оговаривается особо, то каждое измерение вектора признаков будет целым числом где обычно весьма мало. Значениями признаков будут произвольные символы, а не числа. В общем случае будем считать, что существует корректное правило которое применялось для отнесения к классам всех элементов из множества возможных описаний объектов. (Допускается вероятностное отнесение к классам). Мы будем рассматривать алгоритмы, на вход которых поступает множество описаний и имен классов объектов и которые на основании этого множества выводят правило являющееся приближением правила Степень приближения к будет определена сравнением классификаций, проведенных правилами и на пространстве всех возможных описаний объектов.

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

Первой буквой должна быть или

Второй буквой должна быть или

Третьей буквой должна быть или Т.

Четвертой буквой должна быть или

Рис. 6.3. Пример последовательной классификации четверок букв.

Мы выбрали некоторое правило которое относит каждую из возможных четырехбуквенных последовательностей к классу 1 или 0. Вот некоторые из классификаций этого правила:

Объекты класса 0

Объекты класса 1

Каково это правило R? Читателю предлагается самостоятельно попытаться ответить на этот вопрос, прежде чем обратиться к рис. 6.3, где отражено примененное правило. При решении задачи постарайтесь отметить ход ваших рассуждений, приведших к ответу.

На самом деле к той же классификации приводят и другие правила. Обычно именно так и бывает. Если — собственное подмножество множества всех описаний то несколько правил дадут одинаковые классификации для объектов из и различные — для объектов из Нет причины выделять из них какое-то одно, если у нас

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

6.1. Определения и обозначения

Прежде всего пересмотрим наши обозначения и введем определения, которые понадобятся нам для обсуждаемой проблемы.

Объекты и описания

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

Пространство описаний

D — множество всех возможных описаний, N — число элементов в D:

Классы

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

Последовательности наблюдений

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

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

Для формального представления этих понятий определим последовательность описаний длины как упорядоченное множество пар целых чисел удовлетворяющих следующим условиям:

(1) так как а указывает возможное измерение;

(2) так как — возможное значение измерения а;

(3) множество не содержит пар с одинаковыми а-компонентами, т. е. каждое измерение входит в каждую последовательность не более одного раза.

Последовательность содержит последовательность если и первые членов последовательности совпадают с

Правила классификации

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

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

имя класса, связанного с этой последовательностью. Это эквивалентно „прохождению объекта по дереву" до некоторой концевой точки.

Выборка

Выборкой называется множество векторов, определенное случайным образом выбранными из объектами, описания которых и являются векторами из

Расширение последовательности

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

Алгоритм последовательного распознавания образов

Это процедура формирования правила по выборке. Если алгоритм сначала работает с выборкой и формирует правило а затем иереходит к новой выборке (которая может содержать или не содержать чтобы получить по второе правило то полученным правилам будут присваиваться номера в порядке их формирования.

Стоимости

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

Вероятности классификации или наблюдения

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

— вероятность того, что объект, выбранный случайным образом, будет принадлежать классу

вероятность того, что определенной последовательности длины и удовлетворит вектор описания объекта, выбранного случайным образом;

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