Алгоритмы алгебраической и логической коррекции, и их применения.1
Журавлев Ю.И.2 (zhuravlev@ccas.ru), Абламейко С.В.3 (ablameyko@bsu.by), Бирюков А.С.Error: Reference source not found (asbiryukov@yandex.ru), Докукин А.А.Error: Reference source not found (dalex@ccas.ru), Краснопрошин В.В.Error: Reference source not found (krasnoproshin@bsu.by), Образцов В.В.Error: Reference source not found (Obraztsov@cosmostv.by), Романов М.Ю.Error: Reference source not found (mromanov@gmail.com), Рязанов В.В.Error: Reference source not found (rvv@ccas.ru)
Рассматриваются практические алгоритмы распознавания по прецедентам, основанные на логической или алгебраической коррекции различных эвристических алгоритмов или моделей распознавания. Задача распознавания решается в два этапа. Сначала для распознавания произвольного объекта применяются независимо алгоритмы некоторого коллектива, далее применяется соответствующий корректор для вычисления окончательного коллективного решения. Приводятся общие понятия алгебраического подхода, описания практических алгоритмов логической и алгебраической коррекции, результаты их практического сравнения
Введение
В истории развития теории распознавания по прецедентам выделяют три основных этапа:
- появление эвристических методов и алгоритмов как универсальных, предназначенных для решения широкого спектра задач, так и специальных, ориентированных на обработку информации заданного типа (например, алгоритмы «ближайший сосед», «тестовый алгоритм», «алгоритм Кора», дискриминант Фишера);
- создание параметрических моделей и поиск наилучших алгоритмов в пределах фиксированных моделей (например, модели вычисления оценок, нейросетевые модели);
- создание подходов для решения задач распознавания множествами алгоритмов и расширениями существующих моделей.
Создание третьего этапа связано прежде всего с алгебраической теорией распознавания, основы которой разработаны Ю.И.Журавлевым в конце 70-х годов /1,2/. Было введено определение алгоритма распознавания как алгоритма, переводящего начальную информацию о классах и описания распознаваемых объектов в матрицу бинарных ответов на вопросы о принадлежности распознаваемого объекта к каждому из классов (для простоты считаем, что алгоритмы не совершают отказы). Тогда может быть поставлена задача распознавания коллективом заданных алгоритмов в два этапа с помощью логической коррекции: сначала каждый алгоритм независимо от других решает задачи распознавания для объектов заданной выборки (то есть вычисляет некоторую булеву матрицу), далее к заданным булевым матрицам применяется некоторая булева функция (логический корректор), вычисляющая окончательную классификацию. Существуют разнообразные подходы к выборы типа логических корректоров и методы их поиска. Различные методы логической коррекции алгоритмов распознавания описаны в работах /3-5/.
Было также показано, что произвольный алгоритм может быть представлен в виде произведения (последовательного выполнения) двух алгоритмов: распознающего оператора и решающего правила. Распознающий оператор переводит начальную информацию и описания распознаваемых объектов в числовую матрицу. Решающее правило переводит числовую матрицу в бинарную матрицу окончательных ответов. Показана определяющая роль распознающего оператора. Над множествами распознающих операторов определены алгебраические операции, позволяющие строить алгебраические расширения заданных множеств операторов в виде операторных многочленов. Произведения данных операторных многочленов и стандартного фиксированного порогового решающего правила позволяют строить новые алгоритмы распознавания, в том числе корректные (безошибочно распознающие элементы заданной контрольной выборки). К настоящему времени в алгебраической теории распознавания получены необходимые и достаточные условия существования корректных алгоритмов, получены оценки степени операторных многочленов /1,2,6,7/. В настоящей статье описаны некоторые практические алгоритмы построения алгебраических и логических корректоров, позволяющие строить корректные, «квазикорректные» алгоритмы и их приближения. Приводятся примеры решения практических задач, в том числе результаты сравнения с известными алгоритмами распознавания.
1. Алгебраическая и логическая коррекция множеств распознающих алгоритмов
Следуя /1/, будем использовать следующую систему обозначений и исходных понятий. Рассматривается стандартная задача распознавания с классами . Через обозначим заданный на множестве допустимых объектов предикат . Пусть задан конечный набор допустимых объектов . Будем использовать обозначения и считать, что , .
Матрица , где называется информационной матрицей набора по системе предикатов . Строка называется информационным вектором объекта .
Задача распознавания состоит в том, чтобы по начальной информации о классах и предъявленной для распознавания выборке найти информационную матрицу . Реальный практический алгоритм решает данную задачу с ошибками: (здесь , - значение предиката на объекте , вычисленное алгоритмом ). Для простоты мы ограничимся случаем отсутствием отказов при распознавании.
Пусть у нас имеется множество алгоритмов , переводящих , , в матрицы . Алгоритм называется корректным для задачи распознавания, если выполнено равенство .
В /1/ было доказано, что каждый алгоритм представим как последовательное выполнение (произведение) алгоритмов и ( ), где , -действительные числа, , , , .
Множество порождает множества и . Элементы из называются распознающими операторами, элементы из - решающими правилами. Числовые матрицы называют матрицами оценок объектов за классы, или просто матрицами оценок.
Решающее правило называется корректным на , если для всякого конечного набора существует хотя бы одна числовая матрица такая, что .
В /1/ на множестве распознающих операторов были введены операции сложения, умножения и умножения на скаляр, что позволяет строить операторы вида , при этом , если . Тогда можно рассматривать алгоритмы
, (1)
где - корректное решающее правило, а операторы построены на базе операторов параметрических моделей распознавания. Построение алгоритмов вида (1) называется алгебраической коррекцией алгоритмов .
Пусть задан коллектив из n распознающих алгоритмов , , Множества матриц определяют l не всюду определенных булевых функций . При этом , и функция не определена на остальных наборах. Основная задача состоит в таком доопределении функции на весь дискретный единичный куб , при котором будут максимально выполнены дополнительные «содержательно обоснованные» условия, обеспечивающие некоторый однозначный и оптимальный выбор такой функции. Данные функции называются логическими корректорами.
В настоящей статье приводятся результаты исследований, связанных с практическим построением алгебраических и логических корректоров распознающих алгоритмов. Некоторые из корректоров интегрированы в программную систему интеллектуального анализа данных и распознавания «РАСПОЗНАВАНИЕ» /8/, приведены иллюстративные сравнительные результаты распознавания для ряда прикладных задач.
Полиномиальная коррекция на основе слагаемых максимальной высоты
Как уже упоминалось выше, одним из главных результатов алгебраической теории распознавания является доказательство существования корректного полинома над семейством алгоритмов вычисления оценок (АВО) /2/. Однако, практическое применение данной теоремы для построения полиномиальных корректоров порождает несколько сложных задач. Во-первых, необходимо построить набор базовых алгоритмов, причём, как можно более устойчивых. Далее, необходимо минимизировать сложность полинома, т.е. его степень и количество слагаемых. На пути их решения была введена новая характеристика алгоритма, так называемая высота /9/:
,
где – множество правильных пар (объект, класс), т.е. пар в которых объект принадлежит классу, а – множество неправильных пар.
Был разработан набор методов оптимизации высоты алгоритмов в семействе АВО с переменными порогами функции близости /10, 11/. В частности, описан точный метод и набор быстрых приближенных алгоритмов, сравнительное тестирование которых проводилось на наборе специально сгенерированных выборок /11/.
Имея набор базовых алгоритмов (без ограничения общности считаем, что базовый набор содержит по одному алгоритму для каждого контрольного объекта ), несложно построить корректный полином .
Для минимизации его степени предлагается использовать градиентную схему. Запишем задачу оптимизации формально, для простоты записи рассмотрим случай, когда классы не пересекаются – принципиального значения это не имеет. Оптимизация проводится по переменным , . Необходимо минимизировать величину (либо ), при этом должны быть выполнены неравенства, обеспечивающие корректность полинома, а именно:
где – класс, которому принадлежит j-й контрольный объект, - оценка объекта S за класс оператором B. Оптимизационный метод построим по принципу градиентного.
В качестве начального решения возьмем полином первой степени.
Если неравенства корректности выполнены, останавливаемся, иначе переходим к шагу 3.
В случае функционала , увеличим на единицу степень слагаемого, увеличение которого приведет к исправлению максимального числа неправильных неравенств, и перейдем к шагу 2.
В случае функционала , увеличим на единицу степень слагаемого, увеличение которого приведет к исправлению максимального числа неправильных неравенств среди всех слагаемых степень которых меньше , и перейдем к шагу 2.
Нетрудно видеть, что метод сходится.
Изначально схема разрабатывалась для специальным образом построенного набора АВО, однако её легко обобщить для использования с любым набором алгоритмов, образующим базу для заданной контрольной выборки.
Тем не менее, прикладное использование данной схемы осложнено высокой сложностью построения базового набора алгоритмов известными методами (подразумевается, что в качестве базы используется набор АВО максимальной высоты). На практике было решено отказаться от корректности и использовать набор «хороших» слагаемых, высота которых легко, т.е. с помощью быстрых приближенных методов, получается положительной. В ходе решения большого числа прикладных задач была замечена тенденция алгоритмов большой высоты на заданной подвыборке обладать хорошим качеством распознавания в окрестности её объектов. В результате был получен метод «АВО-полином», который строит полином второй степени над АВО вида:
,
где – АВО со специальной функцией близости, обратно пропорциональной евклидову расстоянию до центрального объекта базового АВО.
Построение степенного алгебраического корректора
Данный вид корректоров введен в /1,2/. Пусть имеется некоторая модель алгоритмов . Соответствующую ей модель распознающих операторов обозначим через , а решающее правило зафиксируем в классе пороговых решающих правил , которые, как известно, являются корректными при (если исключить отказы от распознавания). Тогда степенные алгебраические корректоры в общем виде можно представить следующим образом
,(2)где - действительное число ( ), - некоторое натуральное число ( ), индекс пробегает некоторое множество значений, которое существенным образом зависит от решаемой задачи. Пара выбирается из множества . Степень соответствующего распознающего оператора определяется “покомпонентно”, т.е. в коммутативной относительно умножения линейной алгебре. Обозначим также матрицы , где индексы и пробегают все множество допустимых значений для каждого фиксированного .
Модель (2) является корректной при не очень “жестких” условиях на результаты распознавания в . Число распознающих операторов в (2) также в общем случае является “избыточным”. Но точно известно, что больше чем операторов, использовать при построении (2) нет смысла, т.к. базис пространства состоит из матриц. Такой вид модели будем считать “каноническим” и приведем для нее упомянутые выше условия корректности.
Для этого нам понадобится еще одно обозначение. Множество индексов при заданной информационной матрице очевидным образом разбивается на два подмножества
и .
Тогда модель (2) является корректной, при выполнении следующих условий
,(3)и при этом
,(4)где [ ] – целая часть числа , а выбирается из условия (3).
Безусловно, условия (3), (4) являются достаточными. Особенностью такой канонической модели является необходимость построения операторов, удовлетворяющих условию (3). Построенная модель обладает недостатками. При достаточно больших она может оказаться не устойчивой. Условие (3), конечно, более конструктивно, чем условие построения базиса пространства . Некий аналог подобного условия рассматривался в /2, 12/. Там было введено условие квази-полноты, и показано, что модели , в которых выполняется данной условие, существуют. Для этих же моделей , очевидно, выполняется и условие (3). Тем не менее, условия квази-полноты и (3), несмотря на их выполнимость, являются все-таки избыточными.
Ниже будет показано, что при небольшой модификации степенного корректора, условие (3) может быть сделано еще менее “жестким”, а степень вообще может быть положена равной 1.
Для этого введем в пространстве операцию обращения матриц
или ,
где - единичная относительно коммутативного обращения матрица пространства .
Модель (2) модифицируем следующим образом
,(5)а оператор определим с помощью операции обращения (индекс и взят из (3))
.(6)Нетрудно видеть, что при условии (3) для оператора матрица обладает следующим свойством
(7)Следовательно, для нее условие (4) имеет вид
Из последнего неравенства несложно получить, что для
,
модель (5) является корректной при .
Несложно также увидеть, что для распознающего оператора (6) условие (7) выполняется не только, когда для оператора имеет место (3). В действительности, данное условие легко обобщается до следующего
,(8)которое также влечет (7) для оператора (6).
Таким образом, в предложенной модели (5) удается избавится от основных недостатков модели (2). Условие (8) накладывает гораздо менее “жесткие” условия на модель алгоритмов . Кроме того, если в первой модели уместно было говорить о неустойчивости результатов, то в модели (5) корректности удается добиться выбором подходящего параметра .
|
