ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2014, том 54, № 12, с. 1979-1993
УДК 519.7
ПРАКТИЧЕСКИЕ АЛГОРИТМЫ АЛГЕБРАИЧЕСКОЙ И ЛОГИЧЕСКОЙ КОРРЕКЦИИ В ЗАДАЧАХ РАСПОЗНАВАНИЯ ПО ПРЕЦЕДЕНТАМ1
© 2014 г. С. В. Абламейко*, А. С. Бирюков**, А. А. Докукин**, А. Г. Дьяконов***, Ю. И. Журавлев**, В. В. Краснопрошин*, В. А. Образцов*, М. Ю. Романов**, В. В. Рязанов**
(*220030 Минск, пр-т Независимости 4, БГЦ; **119333 Москва, Вавилова, 40, ВЦ РАН; ***119991 Москва, ГСП-1, Ленинские горы, ВМКМГУ) e-mail: ablameyko@bsu.by, asbiryukov@yandex.ru, dalex@ccas.ru, djakonov@mail.ru, zhuravlev@ccas.ru, krasnoproshin@bsu.by, obraztsov@bsu.by, mromanov@gmail.com, rvv@ccas.ru Поступила в редакцию 17.06.2014 г.
Рассматриваются практические алгоритмы распознавания по прецедентам, основанные на логической или алгебраической коррекции различных эвристических алгоритмов распознавания. Задача распознавания решается в два этапа. Сначала для распознавания произвольного объекта применяются независимо алгоритмы некоторого коллектива, далее применяется соответствующий корректор для вычисления окончательного коллективного решения. Приводятся общие понятия алгебраического подхода, описания практических алгоритмов логической и алгебраической коррекции, результаты их практического сравнения. Библ. 33. Табл. 1.
Ключевые слова: распознавание по прецедентам, алгебраическая коррекция, логическая коррекция.
Б01: 10.7868/80044466914120035
ВВЕДЕНИЕ
К настоящему времени создано большое число алгоритмов распознавания по прецедентам (классификации с учителем), основанных на различных идеях и принципах. Первыми появились алгоритмы, в основе которых лежали различные идеи об оценке близости объектов к различным классам (например метод "ближайший сосед", см. [1], "тестовый алгоритм" см. [2], "алгоритм Кора" см. [3], дискриминант Фишера, см. [1]). Их обоснованием фактически были "априорные соображения о близости объектов" и положительные практические результаты. Далее появились параметрические модели распознавания, где основной задачей стал поиск оптимального алгоритма в заданном множестве. Данные задачи сводились к выбору какого-то оптимального набора параметров. В моделях частичной прецедентности (см. [4]) значения параметров находились в результате минимизации критерия качества распознавания (эмпирического риска). Основная задача здесь состояла в поиске произвольной максимальной совместной подсистемы некоторой системы неравенств, были созданы приближенные методы поиска (см. [5]). При обучении нейронных сетей большое распространение получил метод обратного распространения ошибки (см. [6]). В результате пользователям были предоставлены различные параметрические модели распознавания, основанные на принципе частичной прецедентности (см. [4]), статистические модели (см. [1]), основанные на построении разделяющих поверхностей (см. [7]), нейросетевые алгоритмы (см. [6]). При решении практических задач пользователь обычно сталкивается с ситуацией, когда есть набор различных алгоритмов распознавания, имеющих приблизительно равную точность распознавания на обучающей выборке, но совершающих ошибки на различных объектах. Данные ситуации стали практической основой третьего — мультиалгоритмического — этапа в развитии теории распознавания. Было предложено решать задачу распознавания в два этапа. Сначала для распознавания некоторого объекта применяются
1) Работа выполнена при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (грант № 14-01-90019 Бел_а), РФФИ (код проекта 14-01-00824), гранта Президента РФ НШ-4652.2012.1, Программы поддержки фундаментальных исследований Президиума РАН (П-15) и Отделения математических наук РАН № 2.
1979
10*
независимо различные алгоритмы. Далее по исходным данным и выходам алгоритмов вырабатывается некоторое окончательное коллективное решение. Здесь были созданы различные эвристические и статистические подходы.
В конце 70-х годов Ю.И. Журавлевым был разработан алгебраический подход для решения задач распознавания (см. [8], [9]). Было введено универсальное определение алгоритма распознавания как алгоритма, переводящего начальную информацию о классах (данные обучающей выборки) и описания распознаваемых объектов в матрицу бинарных ответов на вопросы о принадлежности распознаваемого объекта к каждому из классов (здесь мы для простоты считаем, что алгоритмы не совершают отказы). Была поставлена задача распознавания коллективом заданных алгоритмов с помощью логической коррекции, когда сначала решаются задачи распознавания объектов заданной контрольной выборки (выборки объектов с известными ответами) независимо каждым из алгоритмов, а далее к полученным булевым матрицам применяется найденная булева функция (логический корректор), вычисляющая конечное решение (классификацию). Были предложены разнообразные подходы к выбору вида логических корректоров, а также методы их поиска (см. [10]—[12]). Было доказано, что любой алгоритм распознавания представим в виде произведения (последовательного выполнения) двух операторов: распознающего оператора и решающего правила. Распознающий оператор переводит пару "начальная информация + описания распознаваемых объектов" в числовую матрицу. Решающее правило преобразует числовую матрицу в двоичную матрицу окончательных результатов распознавания. Была доказана главная роль распознающего оператора. Были определены над множествами распознающих операторов алгебраические операции, которые позволяют строить алгебраические расширения известных множеств операторов в виде операторных многочленов. Произведения операторных многочленов и фиксированного стандартного порогового решающего правила позволяют строить новые алгоритмы распознавания, в том числе находить корректные алгоритмы (безошибочные для заданной контрольной выборки). К настоящему времени в алгебраической теории распознавания найдены необходимые и достаточные условия существования корректных алгоритмов, построены степени операторных многочленов (см. [8], [9], [13], [14]). Отметим, что здесь используются только данные обучающих и контрольных выборок. Алгебраический подход является развитием идей интерполяции на случай, когда функция принимает конечное число значений. Для сколь угодно большой контрольной выборки можно построить безошибочный для ее объектов алгоритм, обладающий положительным радиусом устойчивости. Хорошей иллюстрацией данной интерполяции можно считать результаты эксперимента по распознаванию рукописных цифр, когда в качестве материала обучения-контроля использовалась выборка из 30000 рукописных цифр (см. [15]). На данной информации были построены нейросетевые алгоритмы с последующей простой коррекцией. Поскольку материал обучения-контроля был весьма обширным, точность созданного алгоритма распознавания уступала незначительно точности распознавания цифр человеком.
В данной статье приводятся новые результаты в алгебраическом подходе к решению задач распознавания, а также практические алгоритмы построения алгебраических и логических корректоров. Данные алгоритмы позволяют находить корректные, "квазикорректные" алгоритмы, их приближения. В работе приводятся различные практические примеры, в том числе результаты сравнения с другими алгоритмами.
1. КОРРЕКЦИЯ МНОЖЕСТВ РАСПОЗНАЮЩИХ АЛГОРИТМОВ (АЛГЕБРАИЧЕСКАЯ И ЛОГИЧЕСКАЯ)
Согласно [1] будем использовать следующую систему обозначений и исходных понятий. Рассматривается задача распознавания по прецедентам с / классами К1,К2,...,К/. Обозначим через Р(Б) заданный на множестве объектов {§} предикат "§ е К". Пусть задан конечный набор объектов У = {§',..., Б^}. Будем использовать обозначения К, = У п К¡,1 = 1,2,...,/, и полагать, что К Ф 0, I = 1,2,...,/.
Матрица ||ау ||?х/, где а у = Ру(Б'1), называется информационной матрицей набора §' по системе предикатов Р1,...,Р/. Строка (ай,...,ап) называется информационным вектором объекта Б\.
Задача распознавания состоит в том, чтобы по начальной информации о классах I и предъявленному для распознавания набору объектов У найти информационную матрицу 11 ау || 9Х/. Любой практический алгоритм А(1,Б1,...,Б'д) = ||ру||?х/ решает обычно данную задачу с ошибками:
!!ауWqxi ^ !!ßjWqxi (здесь ßj е {0,1}, ß¡j — значение предиката Pj на объекте S-, вычисленное алгоритмом A). Здесь (для простоты) мы ограничимся случаем отсутствия отказов при распознавании.
Пусть у нас имеется множество алгоритмов {A}, переводящих (I,S',...,S'q), I е {I}, S с {S}, в матрицы A(I ,S1,...,Sq) = !!ßj !!qxl. Алгоритм A называется корректным для задачи распознавания, если выполнено равенство A(I, S{,...,Sq) = ||а у !!qxl.
В [8], [9] было доказано, что каждый алгоритм A е {A} представим как последовательное выполнение (произведение) алгоритмов (операторов) B и C (A = BC), где B(I,S1,...,S'q) = Цйу !!qxl, üj — действительные числа, C(\\aij!!qxl) = !!ß;j!!qxl, ßij e {0, 1}, B = B(A), C = C(A).
Множество {A} порождает множества {B} и {С}. Элементы из {B} называются распознающими операторами, элементы из {С} — решающими правилами. Числовые матрицы B(I,S1,...,Sq) = !!üj!!qxl называют матрицами оценок объектов за классы, или просто матрицами оценок.
Решающее правило C называется корректным на {ST'}, если для всякого конечного набора S с {S} существует хотя бы одна числовая матрица \\ay\\qxl такая, что C(!üj!!qxl) = Цау!!qxl.
В [9] на множестве распознающих операторов {B} были введены операции сложения, умножения и умножения на скаляр, что позволило строить операторы вида B' = ^b¡Ba «... • Bik, при этом
B'(I,S1,...,Sq) =y^i aUv = ^biaUV •...• aU^
если Bit (I ,S',...,S') = Ца'Л !!qxl. Тогда можно рассматривать алгоритмы
A = B' C*, (1)
где C* — корректное решающее правило, а операторы B' построены на базе операторов параметрических моделей распознавания. Построение алгоритмов вида (1) называется алгебраической коррекцией алгоритмов {A}.
Пусть задан коллектив из n распознающих алгоритмов A1,A2,...,A", Ak(I,S[,...,Sq) = !!ßk!!qxl, k = 1,2,...,п. Множества матриц {!!ßk!!qxl, k = 1,2,...,n, Цау!!qxl} определяют lне всюду определенных булевых фун
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.