Бекмуратов К.А.
Рассматривается один из возможных принципов усложнения решающего правила непрерывного пространства признаков, порождаемого опорными объектами конкретного образа. Предложена процедура нахождения предельного значения размерности признакового пространства, в котором возможно кусочно-линейное разделение образов и гарантированы требуемые качество и надежность распознавания, необходимые в системах управления.
В работе [1] описан метод формирования пространства непрерывных признаков, приводящий к безошибочному разделению образов. Введено понятие непрерывного признака и показано, что если набирать пространство только из определенных в [1] признаков, то можно достичь безошибочного разделения образов.
В данной работе так же, как и в [2], рассмотрим случай, когда в пространстве непрерывных признаков размерности n безошибочное разделение обучающей последовательности невозможно.
Пусть на некотором множестве  мощности  объектов  определены подмножества  при  , представляющие собой образы на обучающей выборке 
Допустим, что  - подмножество на , соответствующее конкретному образу  , а  - подмножество на , соответствующее остальным  образом 
Требуется с использованием обучающую выборки найти решающее правило  , указывающее принадлежность любого объекта из одному
из заданных образов или с вероятностью ошибки, не превышающей  , достигаемой с надежностью (1- ), и определить целесообразности усложнения решающих правил при синтезе непрерывных признаковых пространств.
Если обучающая последовательность не может быть безошибочно разделима выбранным решающим правилом, то в общем случае справедлива теорема Вапника - Червоненкиса [3], смысл которой состоит в том, что если в n-мерном пространстве признаков решающее правило совершает  ошибок при классификации обучающей последовательности длины  , то с вероятностью  можно утверждать, что вероятность ошибочной классификации составит величину, меньшую  ,
 ,
где N- число всевозможных правил заданного класса, которое можно построить в пространстве заданной размерности.
Предположим, что в процессе обучения из последовательно поступивших непрерывных свойств относительно  опорных объектов  синтезирована подсистема непрерывных признаков. В зависимости от состава случайной и независимой выборки процесс обучения может остановиться при любом значении n, но если разделение конкретной обучающей выборки наступило в n-мерном пространстве, то число N всевозможных решающих правил в классе не должно превышать числа всех подмножеств множества, состоящего из элементов, т.е.
 ,
где
 .
Логарифмируя получим
 (1)
Если учесть  , то (1) принимает вид
  , (2)
где  можно оценить в виде
 (3)
Подставляя (3) в (2), получаем
 (4)
Используя теорему Вапника-Червоненкиса [3], можно вычислить предельную размерность пространства
 , (5)
которая при заданных  гарантирует требуемые e и h.
Пусть вычислено максимально допустимое значение размерности пространства  в виде (5) и в этом пространстве фиксирована линейная решающая функция
 (6)
Далее, для того чтобы в процессе обучения синтезировать пространство, в котором линейное решающее правило (6) безошибочно разделило бы обучающую выборку  длины , и при этом размерность пространства не превышала бы , необходимо на признаки  наложить дополнительные требования. Зная предельную размерность простанства (8), можно оценить минимально допустимую разделяющую силу каждого выбираемого признака  в виде
Минимально допустимая разделяющая сила признака позволяет при синтезе непрерывного пространства использовать не все признаки, а выбирать только те, разделяющая сила которых удовлетворяет неравенству
Допустим, что в синтезированном пространстве непрерывных признаков размерности n линейная решающая функция (9) совершает ошибки с частотой . Тогда рассмотрим соотношение
 , (7)
где N* - соответствует решающему правилу, работающему с частотой ошибки , N**- безошибочно разделяющая обучающая последовательность длины .
С использованием этого соотношения, можно установить целесообразность усложнения решающего правила в случае, если в пространстве размерности n ещё не достигнуто безошибочное разделение обучающей выборки.
Известно [3], что если вместо линейного правила используется кусочно-линейное и оно безошибочно разделяет обучающую выборку длины l, то в соответствии (7) вместо n следует выбирать величину
n=nk+k , (8)
где k - число линейных решающих правил, составляющих искомое кусочно - линейное правило. Используя соотношения (7) и (8), ответим на вопрос: стоит ли усложнять решение, если линейное правило в пространстве размерности n не обеспечивает безошибочного разделения обучающей выборки. Для этого нужно сделать подстановку:
 , (9)
В этом случае усложнение решающего правила, определяемое числом k, не приведёт к снижению вероятности ошибки, если будет выполнено соотношение (7) после подстановки (8). Из этого условия можно найти такое значение k, выше которого теряет всякий смысл усложнение решающего правила, действующего в пространстве непрерывных признаков размерности n:
 . (10)
Таким образом, если выбирать n и k согласно (5) и (10), то процедура позволяет, при синтезе пространства, использовать не все признаки, а выбирать только те, разделяющая сила которых позволяет при заданных  обеспечить требуемые значения ε и η.
Список литературы
1. Бекмуратов. К.А. Процедура формирования непрерывных признаковых пространств при последовательном обучении. Узб. Журнал // «Проблемы информатики и энергетики».- 1994.-№4.-С.17-20.
2. К.А. Бекмуратов. Пошаговая проверка целесообразности усложнения решающего правила при последовательном обучении задаче распознавания. Узб. Журнал // «Проблемы информатики и энергетики». -2000. -№1. – С. 16-19.
3. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов.(Статистические проблемы обучения). – М.: Наука, 1974. –С. 415.
|