Алгоритмы алгебраической и логической коррекции, и их применения




Скачать 468.68 Kb.
НазваниеАлгоритмы алгебраической и логической коррекции, и их применения
страница1/4
Дата31.08.2012
Размер468.68 Kb.
ТипДокументы
  1   2   3   4
Алгоритмы алгебраической и логической коррекции, и их применения.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/, приведены иллюстративные сравнительные результаты распознавания для ряда прикладных задач.


  1. Полиномиальная коррекция на основе слагаемых максимальной высоты

Как уже упоминалось выше, одним из главных результатов алгебраической теории распознавания является доказательство существования корректного полинома над семейством алгоритмов вычисления оценок (АВО) /2/. Однако, практическое применение данной теоремы для построения полиномиальных корректоров порождает несколько сложных задач. Во-первых, необходимо построить набор базовых алгоритмов, причём, как можно более устойчивых. Далее, необходимо минимизировать сложность полинома, т.е. его степень и количество слагаемых. На пути их решения была введена новая характеристика алгоритма, так называемая высота /9/:

,

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

Был разработан набор методов оптимизации высоты алгоритмов в семействе АВО с переменными порогами функции близости /10, 11/. В частности, описан точный метод и набор быстрых приближенных алгоритмов, сравнительное тестирование которых проводилось на наборе специально сгенерированных выборок /11/.

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

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



где – класс, которому принадлежит j-й контрольный объект, - оценка объекта S за класс оператором B. Оптимизационный метод построим по принципу градиентного.

  1. В качестве начального решения возьмем полином первой степени.

  2. Если неравенства корректности выполнены, останавливаемся, иначе переходим к шагу 3.

  3. В случае функционала, увеличим на единицу степень слагаемого, увеличение которого приведет к исправлению максимального числа неправильных неравенств, и перейдем к шагу 2.

В случае функционала , увеличим на единицу степень слагаемого, увеличение которого приведет к исправлению максимального числа неправильных неравенств среди всех слагаемых степень которых меньше , и перейдем к шагу 2.

Нетрудно видеть, что метод сходится.

Изначально схема разрабатывалась для специальным образом построенного набора АВО, однако её легко обобщить для использования с любым набором алгоритмов, образующим базу для заданной контрольной выборки.

Тем не менее, прикладное использование данной схемы осложнено высокой сложностью построения базового набора алгоритмов известными методами (подразумевается, что в качестве базы используется набор АВО максимальной высоты). На практике было решено отказаться от корректности и использовать набор «хороших» слагаемых, высота которых легко, т.е. с помощью быстрых приближенных методов, получается положительной. В ходе решения большого числа прикладных задач была замечена тенденция алгоритмов большой высоты на заданной подвыборке обладать хорошим качеством распознавания в окрестности её объектов. В результате был получен метод «АВО-полином», который строит полином второй степени над АВО вида:

,

где – АВО со специальной функцией близости, обратно пропорциональной евклидову расстоянию до центрального объекта базового АВО.


  1   2   3   4

Похожие:

Алгоритмы алгебраической и логической коррекции, и их применения iconМетоды и алгоритмы координатно-временных определений на основе применения спутниковых навигационных технологий Системный анализ, управление и обработка информации
Методы и алгоритмы координатно-временных определений на основе применения спутниковых навигационных технологий
Алгоритмы алгебраической и логической коррекции, и их применения iconПараллельный алгоритм апостериорного вывода во фрагменте знаний алгебраической байесовской сети
В работе предлагается подход к распараллеливанию алгоритма вывода апостериорных вероятностей во фрагменте знаний алгебраической байесовской...
Алгоритмы алгебраической и логической коррекции, и их применения iconТеоретические вопросы к курсовой работе по дисциплине «Структуры и алгоритмы обработки данных»
Основные понятия и определения (данные, тип, структура данных, понятие логической и физической структуры, уровни представления и...
Алгоритмы алгебраической и логической коррекции, и их применения iconЗадача отыскания импульсной характеристики канала осложняется тем, что идентификация системы по известному переданному сигналу и сигналу на выходе (т е.
В работе рассматриваются алгоритмы адаптивной коррекции сигналов во временной и частотной областях с применением методов обратного...
Алгоритмы алгебраической и логической коррекции, и их применения iconНаучные и практические аспекты патогенетически обоснованного применения витаминов в профилактических и лечебных целях Сообщение Недостаток витаминов в рационе современного человека: причины, последствия и пути коррекции
Сообщение Недостаток витаминов в рационе современного человека: причины, последствия и пути коррекции
Алгоритмы алгебраической и логической коррекции, и их применения iconИвин Логика «Логика»
Главное внимание уделяется логической проблематике, представляющей особый интерес с точки зрения наук о культуре. Изложение логической...
Алгоритмы алгебраической и логической коррекции, и их применения iconИспользование информационно-коммуникационных технологий в коррекционно-развивающей работе с детьми как способ оптимизации процесса коррекции устной речи и ознакомления ребенка с окружающим миром
Исследования, посвящённые проблеме изучения и коррекции речевых нарушений у дошкольников, показывают, что данные нарушения характеризуются...
Алгоритмы алгебраической и логической коррекции, и их применения iconОпыт применения ибандроновой кислоты для коррекции остеопороза у диализных пациентов с вторичным гиперпаратиреозом
...
Алгоритмы алгебраической и логической коррекции, и их применения iconМетод проектирования логической структуры реляционной бд для веб-приложений без нормализации таблиц
Анализ классического метода и case-средств проектирования логической структуры реляционной бд 14
Алгоритмы алгебраической и логической коррекции, и их применения iconПравительство Российской Федерации фгбоу впо «Санкт-Петербургский государственный университет» Философский факультет
Он обязан иметь общее представление об истории развития логики и ориентироваться в важнейших направлениях применения логической техники...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница