Построение базиса на множестве алгоритмов, основанных на гиперплоскостях, для произвольной задачи распознавания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

004616254

На правах рукописи

Лысёнок Евгений Игоревич

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

Специальность 01.01.09 — дискретная математика и математическая

кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2010

-злек 2ою

004616254

Работа выполнена в организации Московский Государственный Университет имени М.В. Ломоносова, факультет Вычислительной Математики и Кибернетики,

Научный руководитель: доктор физико-математических наук, академик РАН Журавлёв Юрий Иванович.

Официальные оппоненты: доктор физико-математических наук, Сметанин Юрий Геннадиевич,

кандидат физико-математических наук Кольцов Петр Петрович.

Ведущая организация: Московский Физико-Технический Институт,

факультет управления и прикладной математики.

Защита диссертации состоится Я У -¿3 12 ,2 О !Р На заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Автореферат разослан . 4Ь.П.20-1 о

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор

В. В. Рязанов

Общая характеристика работы

Актуальность темы. Проблема автоматического распознавания образов является одной из актуальных проблем математической кибернетики. Эта проблема является ведущей в таких областях науки и техники, как практическая геология, биология, химия, медицина и т.п. Одной из причин распространения данной проблемы в этих областях является то, что для применения методов распознавания требуется значительно меньшая точность описываемых объектов и явлений, чем при применении других методов прикладной математики. Второй важной причиной является то, что идея прецедентное™, то есть идея принятия обоснованного решения па основе сравнения с другими объектами или явлениями, является ключевой для естественных наук.

Для решения задач распознавания было предложено множество методов. В том числе алгоритмы нахождения минимального эмпирического риска (Вапник В.Н. Червоиенкис А.Я), метод потенциальных функций (йзерман М.А., Броверман Э.М., Розепэр Л.И.), алгоритмы вычисления оценок ( Журавлёв Ю.И., Никифоров В.В.). Ю.И. Журавлёвым введено понятие алгебраического подхода к задачам распознавания, позволяющего синтезировать результаты распознавания алгоритмов различного рода. Было доказано, что с помощью алгебраических операций над некоторыми семействами алгоритмов можно построить алгоритм, точно распознающий любую наперёд заданную выборку при заданной начальной информации. Из каждого семейства, обладающего этим свойством, можно выделить конечный базис алгоритмов, который достаточен для данного построения.

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

В настоящей работе доказано существование данного базиса для

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

Методика исследований. Для доказательства использован математический аппарат комбинаторики, линейной алгебры, математической логики. Для разработки оптимизационного метода использован экспериментально-теоретический подход. Проведены эксперименты на данных реальных прикладных задач.

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

Апробация работы. Результаты, изложенные в диссертации, представлены на научных семинарах ВЦ РАН и кафедры Математических Методов Прогнозирования МГУ.

Основные результаты диссертации.

1) Доказана теорема о корректности линейного замыкания семейства алгоритмов, основанных на гиперплоскостях.

2) Создана программа для построения базиса исследуемого семейства.

3) Предложен подход для оптимизации построения базиса.

4) Реализован программный модуль, позволяющий применять указанный подход на данных различных форматов.

5)

Исследуемые методы применены на данных прикладных задач.

Практическая и теоретическая ценность. Приведены теоретические результаты, касающиеся семейств распознающих алгоритмов, основанных на разделении гиперплоскостями. Показано, что с помощью линейных комбинаций можно построить корректное семейство. Таким образом, показано, что для достижения корректности данного семейства, нет необходимости расширять базовые алгоритмы или вводить новые операции. Результат и доказательство даёт возможность получать аналогичные утверждения для других семейств алгоритмов, что может влиять на их дальнейшее развитие и разработку.

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

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

Публикации. По теме диссертации опубликованы две работы в ЖВМиМФ ( без соавторов).

Структура и объём работы. Работа состоит из введения, трёх глав и списка литературы из 26 наименований. Общий объём работы — 93 страницы, включая 22 рисунка.

Содержание диссертационной работы

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

В первой главе вводятся основные определения и обозначения, рассматривается постановка задачи, даётся понятие алгоритма, основанного

па разделяющей гиперплоскости.

Оператор Яд называется распознающим оператором, если он переводит

(10{Кг,.... Щ, ЦБь..., 5,)), 1о(Кь..., К{) б /

в числовую матрицу {ау}?х! = М,хг.

Оператор г^ называется решающим правилом, если он переводит произвольную числовую матрицу {а¿;} = в информационную

матрицу

{°$}?хг = ^хг,

то есть матрицу, составленную из элементов {0,1, Д}.

Решающее правило га называется корректным, если для всякой конечной совокупности допустимых объектов £[,..., существует числовая матрица {ау}9Х; такая, что г\ переводит {%•} в матрицу, истинную для ..., Б'г

Оператор А являющимся произведением распознающего оператора Яд и решающего правила г а называется стандартным распознающим алгоритмом.

Пусть заданы элемент 1о(1) из {/о},описания д) допустимых объектов ..., Б'д, а также предикаты Р\,...,Р1 на множестве допустимых объектов {5}, определяющих вхождение векторов Й!,...,^ в классы Кх,..., К[. Задача 2 = .2(/о> • ■ •, ... ,Р/) состоит в построении алгоритма для вычисления по /о свойств Р\}... ,Р\ для объектов ¿>1, ■. •,

Распознающий алгоритму! называется корректным для задачи ¿у, если для задачи 2 выполнено условие А(1$(1},1(3\,..., 5,)) = где

{ау}гх/ — истинная информационная матрица для объектов .....5?.

Семейство алгоритмов {А} называется корректным над множеством задач {£}, если для любой задачи Z £ {Я} найдётся алгоритм А € {А}, являющийся корректным для Ъ.

Пусть В', В" € {Яа} ~ Два произвольных распознающих оператора.

В'{1о, ..., Бд) - {а'у}дх;, В"(1а, Бг,..., 5д) = {ау},х/, б'-произвольное скалярное вещественное число. Операторы Ь' ■ В,В' + В", В' ■ В" определяются следующим образом:

= (1) + = + (2)

(В'-В")(/,5ь...,59) = {4.а'/.}9хг. (3)

Замыкание множества {В} относительно операций (1)-(3)

называется алгебраическим замыканием распознающих операторов Соответствующее семейство распознающих алгоритмов с фиксированным корректным решающим правилом называется алгебраическим замыканием распознающих алгоритмов.

Замыкание £>{В} множества {В} относительно операций (1)-(2) называется линейным замыканием распознающих операторов. Соответствующее семейство распознающих алгоритмов с фиксированным корректным решающим правилом называется линейным замыканием распознающих алгоритмов.

Рассматриваются описания объектов

{5} € М = М1 х ■ • • х Мп, Мг С К в виде вещественных векторов (ах,02,...,ап),щ £ М{ размерности п, то есть стандартная обучающая информация.

Пусть (Л} — совокупность кусочно-линейных поверхностей в п-мерном евклидовом пространстве.

Алгоритм А, основанный на кусочно-линейной поверхности, является алгоритмом распознавания для стандартной обучающей информации и определяется заданием кусочно-линейной поверхности Я, набора неотрицательных числовых параметров 7(й[),г = 1,...,т, параметров х^,

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

Пусть R — гиперповерхность в n-мерное числовом пространстве, разбивающая его на два подмножества. Для объектов S, входящих в одно из подмножеств и таких, что R(S) -ф 0, будем писать R(S) > 0. Для объектов S, входящих в другое подмножество, если R(S) ^ 0, то будем писать R(S) < 0.

Алгоритм А представляет собой произведение распознающего оператора В и корректного решающего правила С*. В зависит от параметров (й,7т, х). Оператор В по выборке S\,...,Sq строит числовую матрицу:

l|o«(5j)ll?xi = ИМ?*'-

Для произвольного допустимого объекта строка B(S) = (ai (S),..., a ¡{S)) определяется следующим образом.

1, R(S) — 0. Тогда a,(5) = const, аг(5) не зависит от параметров алгоритма: разделяющей поверхности R и параметров 71,.. .,^m,xlaß.

2. R(S) Ф 0. Разобьём объекты S[,..., S'm такие, что ^ 0 на подмножества Ш3а д, а = 0,1, ß — 0,1, j = 1,..., Здесь:

a — значение предиката Pj(Si) ■< S[ 6 Kj >, 1 < j ^ Z;

ß — значение предиката Q(Sl) :< R(Si) > 0 > .

. Множество Ш3а0 состоит из таких 5-, что

Положим Г^ = Е^еот^ 7(5<)- Ъслк {ОТ}^ пусто, то Г^ = 0.

Г. R(S)>0,B(S} = (aï(S),...,a,(S)),

^oi ' П1 + *10 ' ^10 + *

= .« V" , J№

2°. R(S) < 0,

„ /с\ хо\ ' rm + ж10 ' Но

j{ '= .г* +Х1 • rj +Г [ }

хи 111 ' %) -1 00 ^ 1

в

(4) и (5) область изменения параметров 7; есть (0,+оо),г = 1 ,...,т, параметры из х принимают значение 0,1.

Рассмотрим класс Z задач

Z=<I,Sh..., Sq >=< 5(S[);... ; S'm: 5 (S'J-S\,...,Sq >, удовлетворяющих следующим условиям:

î) {Si,.=

2) матрица ||a,j||mxi, строками которой являются информационные векторы объектов S[,...,S'm, не содержит одинаковых столбцов.

Совокупность задач Z, удовлетворяющих условиям 1) и 2) обозначим через {Z}.

Условия 1) и 2) являются естественными. Условие 1) означает, что Si 6 {SJ,... и задача распознавания решена, так как известна принадлежность классам К\,... ,Ки Нарушение условия 2) означает, что два класса на обучающей выборке неразличимы.

Положим M = {£{,..., S'm}.

Класс Kj называется изолированным в Z, если существуют классы Kr, Kty Kv, 1 ^ j, г, t, v < I такие, что:

1) KjftîZc Кг()М\

2) KtÇ\M СК^М- ^ __

3) {KjflKv)[}М = 0 я M f]{Kj\JKV) = M.

Рассмотрим подкласс задач {Z} С {5}, состоящих из задач, не содержащих изолированных классов.

Следующие две теоремы были доказаны в более ранних работах. Теорема 1.1. Линейное замыкание L{A] класса алгоритмов, основанных на кусочно-линейных поверхностях, является корректным па {Z}.

В алгебре 21(5} распознающих операторов, соответствующих алгоритмам А, основанным на кусочно-линейных поверхностях, выделим операторы, представимые полиномами степени не выше 2. Множество таких операторов обозначим 21г{В}, а множество алгоритмов

А = В' ■ С,В' 6 2Ь{В}, ( С* — фиксированное корректное решающее правило ) — через 21г{Л}.

Теорема 1.2. Совокупность алгоритмов 21г{Л}. корректна на множестве задач {£}.

Во второй главе диссертации доказывается утверждение, являющееся усилением приведённых теорем:

Теорема 2.3. (О корректности алгоритмов на основе гиперплоскостей). Линейное замыкание Ь{А} класса алгоритмов {Л} = {В ■ С*} с произвольным корректным решающим правилом С* и операторами В € {В{х,7, Я)}, где Я 6 {Д} является гиперплоскостью, является корректным на

Доказательство теоремы опирается на три леммы с номерами 1,3 и 4. При этом лемма 3 опирается на промежуточное утверждение, обозначенное леммой 2.

Лемма 1 (О разделяющем семействе гиперплоскостей). Пусть дано произвольное множество из к различных точек в вещественном пространстве {5} = {йх,..., ¿¡У £ Кп. Тогда существует система из к гиперплоскостей:

Яь-.-.Яь (6)

таких, что

1.|Я1-П{5}| = 1)...1|ЯЛ-П{5}|=А1

2.Щ С Я2- с ■ • ■ С Щ

3.Я+ЭЯ+Э.-ОЯ^,

4.Н, П {5} = 0,1 = 1,2,...,к.

Лемма 2 (О замкнутости линейных подпространств в конечномерном вещественном линейном пространстве). Любая предельная точка

подпространства Н конечномерного вещественного пространства Ь принадлежит подпространству Н.

Лемма 3 (О полноте линейного замыкания частного линейных комбинаций).

Пусть {а^}Пхт — булева

матрица размеров п х т.,яу 6 {0,1},г = 1,2,...,т,] = 1,2,п Ь — булев вектор размера т,Ь{ € {0,1}, г = 1,2,..., т. Обозначим через а1,..., ап столбцы матрицы {ау} :

' оу ^ а> = ... •

у О'тз у

Пусть дано отображение М из декартова произведения множеств вещественных векторов размера т с положительными координатами, булевых векторов размера т и булевых матриц размеров п х т во множество вещественных матриц с двумя строками и п столбцами, определяемое соотношениями

М:Ж™хВтх Втхп —+ Е2хп,

М(ъЬ,А)=(т ■ ■ (7)

■■■ /

<7 > № ~:-=7—'

1+ < 7, а> > <7 ®Ь,а? > ^ = 1+ <7,0* > для произвольных £ € К+, 6 € Вт, А £ £тхп.

Для фиксированных матрицы А и столбца Ь пусть даны отображения М\,М-1,М^ из множества вещественных векторов длины т с положительными координатами во множество вещественных матриц с двумя

строками и п столбцами

: Н™ —>

К2хп, г = 1,2,3,

(8)

определяемые следующими соотношениями:

= М(7,А), М2(7) = М(7,6, А), М3(7) = М(7>5, Л), (9)

где М определяется соотношениями (7).

Пусть фиксированы матрица А из Втхп, у которой все столбцы различны, и произвольный булев вектор Ъ из Вт.

Тогда линейное замыкание объединения образов отображений (9) совпадает с подпространством матриц из двух строк длины п вида

где соотношение х^ = 0 должно быть выполнено, если существует со — номер нулевого столбца в матрице Л, соотношение Х2С1 = О должно быть выполнено, если существует с\ — номер столбца матрицы А, содержащего только единицы.

Лемма 4 (О конструировании базиса матриц размерности тхп на основе базиса двустрочных матриц). Пусть задан базис

пространства матриц К2хп. Пусть элементы матрицы Еу, г = 1,2, з = 1,2,... п равны Е%.

Пусть задана система из т булевых векторов Ь1,... ,Ьт такая что V ЬТ — 1, № ф Ьг, 1 р < г ^ пг, т.е. координаты с единицами вектора ЬР содержатся во множестве координат единиц следующего за

Хц, Хц € М, 1 < 3 < 71, ХХсо = О, ¡Г2с1 = 0},

(10)

'2 п

(П)

ним вектора Ьр+\, не равного У, 1 ^ р < п. Очевидно, что при таком условии имеем Ьп = а", где а", где вектор из п единиц.

Для каждого фиксированного вектора =1,2,,..,шс помощью системы (11) построим систему матриц изЖтхп :

Еи,Р =

( рП

Рп

\

Е2пф =

. Еп \

г?п

■■ Е]1п /

{ Р2п

Е

а п \ 'ип

Е2 п

тр1п п

■■■

^РтП }

(12)

где

/ 1.

т.е. строка с номером í у матрицы Ег^'р равна первой строке матрицы базиса двустрочных матриц -Е4 в случае, если г-й элемент вектора У равен 1, и второй строке той же матрицы в обратном случае, т.е. в случае 0 в г-й координате №. Тогда система матриц (12) полна в Мтх".

В третьей главе приводятся результаты экспериментальных исследований и предлагается подход для улучшения качества рассматриваемых алгоритмов.

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

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

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

В заключении приводится краткий итог диссертации.

Таким образом, на зашиту выносится:

1) Теорема о корректности линейного замыкания алгоритмов на основе гиперплоскостей.

2) Метод построения базиса алгоритмов на основе гиперплоскостей.

3) Метод улучшения качества полученных алгоритмов за счёт оптимизации выбора начального вектора.

Список публикаций по теме диссертации

1. Лысёнок Е.И. Корректность линейного замыкания распознающих алгоритмов, основанных на гиперплоскостях. ЖВМиМФ. т. 49, № 10, С. 1885-1904, 2009.

2. Лысёнок Е.И. О некотором подходе выбора гиперплоскости для алгоритмов распознавания. ЖВМиМФ. т. 50, № 10, С. 1862-1864, 2010.

Подписано в печать: 16.11.2010

Заказ № 4549 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение

Глава

Глава

Глава

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

Второй важной причиной является то, что идея прецедентности, то есть идея принятия научного решения на основе сравнения с другими объектами или явлениями, является ключевой для естественных наук. Действительно, обучение или исследование может проходить в естественных науках либо на основе уже известных принципов и законов, либо на основе примеров. При этом тот или иной пример относится к определённому классу на основе накопленной информации о других примерах. Тем самым проявляется идеология распознавания. Все допустимые объекты или явления разбиты на конечное число классов (классы могут пересекаться). Для каждого класса известно конечное число ранее изученных объектов или явлений. Изучаемый (данный) объект следует отнести к тому или иному классу. Различные математические методы распознавания являются формализацией вышеописанной схемы.

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

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

Представители второй школы пришли к выводу, что задачи распознавания требуют новых подходов в прикладной математике. В разработке таких подходов помогло появление первых ЭВМ, что позволило математикам проводить широкий спектр математических экспериментов. Этот метод исследования во многом похож на экспериментальные методы исследования физика-естественника, которые позволяют ему строить различные гипотезы об изучаемых им явлениях, а затем проверять их-экспериментальным путём. Точно также математик может выдвинуть гипотезу и, не проводя строгих математических доказательств, проверить гипотезу, проведя -математический эксперимент.

Таким образом, на первом этапе собирается экспериментальный материал проверки той или иной гипотезы о методе решения конкретной задачи. Изучается класс задач, приводящих к задаче распознавания, например, задача прогнозирования в геологии. Изучение описаний месторождений и участков местности, где месторождения не обнаружены, приводит к гипотезе: множества описаний первого и второго класса разделяются достаточно простой поверхностью. Простейшей поверхностью является гиперплоскость. Уточнённая гипотеза: описания, выполненные набором числовых признаков и принадлежащие разным классам, разделяются гиперплоскостью. Проводится эксперимент на ЭВМ и показывается, что в 99 случаях из 100 гипотетическое разделение действительно имеет место.

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

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

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

Среди описанных моделей можно выделить модели основанные на принципах разделения [3], модели типа потенциалов [1], модели вычисления оценок [9][10][11][12].

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

В рамках исследования моделей алгоритмов выделилось две ветви, возникших в связи со стремлением математиков к обобщению способов описания алгоритмов моделей.

Суть исследования, первой ветви сводится к упрощению описания алгоритмов, а также сопутствующих множеств, таких как множеств объектов распознавания или выделяемых признаков, посредством использования индуктивного подхода при описании множеств. Выбирается некоторый набор базисных элементов, а затем посредством определённых операций, строится всё множество. Так, при помощью заданных порождающих отображений, строятся описания классов. Аналогично - из элементарных признаков и системы логических операций - строится множество признаков. Таким образом, система правил для построения начальной обучающей информации для распознающего алгоритма, порождает новую модель. Такие алгоритмы и модели получили название структурных или синтаксических методов распознавания [24].

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

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

Алгоритмы вычисления оценок. Идея алгоритмов вычисления оценок основана на формализации принципа частичной прецедентности. Модель разработана для стандартной информации [9]. Введём основные определения.

Пусть М — множество, элементы которого S называются допустимыми объектами. Для каждого S определено I(S) — описание объекта S. Кроме того, М — Uí=1-K¿- Множества /ц называются классами. Задано также множество {1о(К\,. ,Ki)} информации о классах. Вектор а = (ai,., сщ) называется информационным, если a¿ € {0,1, Д}. Введены предикаты Pj(S) — объект S принадлежит классу K¡,j — 1,2,. ,1.

Для краткости набор описаний I(S[),., I(S'q) допустимых объектов S{,. ,S'q обозначим через I(S{,., S'q).

Определение 1. Алгоритм А называется распознающим алгоритмом, если

A(I¿KUKt), I(S[, .,S'q)) = {a¿.}9Xb

IQ{KU .,Ki)e {10(Кг,., К,)}, S{,.,S'q допустимые объекты, q >1 — произвольное натуральное число, € {0,1, Д}. Строка (аг'{,., называется информационным вектором [9] объекта S¡ в алгоритме А.

Значения интерпретируются следующим образом.

1. afj € {0,1}; тогда алгоритм А установил, что Pj(S¡) = a¿j.

2. огу = Д : алгоритм А отказался вычислять значение Pj(S¡).

Определение 2. Вектор а(5) = {ал (5),., г V; (£")), называется истинным для 5, если а^Э) € {0,1} и

Пусть в пространстве информационных векторов задана функция р(а,/3), обладающая всеми свойствами расстояния, за исключением, может быть, аксиомы треугольника. Задана также последовательность числовых функций /1(0:1),., /д(жь ., хд),., причём: 1) /д(хи .,хч) определена и неотрицательна при хг > 0; 2) монотонно не возрастает по каждой из переменных 3) /9 достигает абсолютного максимума на наборе (0,. ,0).

Пусть опять £1,., З'ч — произвольная конечная выборка из множества допустимых объектов, а истинный для Б'г, ал(5г') — информационный вектор в алгоритме А.

Определение 3. Функционалом качества алгоритма А на ., З'ц называется величина

Функционал качества алгоритма А будем обозначать в дальнейшем через ф{А) или <р(А, ., В практических задачах обычно рассматриваются следующие виды функционалов ¡р(А).

1. Пусть для каждой пары

5-, К у), в М, 1 < о < определены числа 7у(а, (3),а,0 е {0,1, Д}, причём 7„-(а,а) > при а ф ¡3) = П/,3(Р,а), 7у(а,Д) >

7^(5, Д), если а б {0,1},/? 6 {0,1}, аф]).

Функционал <р(А) называется линейным [13], если и все остальные 7Ч =0, то функционал у?(Л) называется долей правильных прогнозов.

В дальнейшем основной задаче является эффективное построение распознающих алгоритмов с максимальным значением <р{А). Такие алгоритмы в дальнейшем называются оптимальными.

2. Если

7у(1,1) =^(0,0) = 1,

Пусть заданы характеристики 1,2,.,п (признаки) с множествами значений соответственно Мх,., Мп.

Определение 4. Стандартным описанием /(51) объекта 5* называется набор (й1, а2,., а„), аг € М», г = 1,2,., п. Набор

5г), 5(50,., 7(£го), а(5т)) = Ш, называется стандартной обучающей информацией, если 1{Бх),., 1(5'т) — стандартные описания допустимых объектов 5х,., и а(3{) — их истинные информационные векторы, г = 1,2,., т. Если {/(б^),., /(5^)} 1(>5/1,., 5^) = /5(9) ~ также набор стандартных описания объектов, то набор (/о(0> называется стандартной информацией. Применение распознающего алгоритма к стандартной информации символически обозначается А(10(1), /3(9) = Алгоритм А по описаниям объектов бх,., 5т и их информационным истинным векторам вычисляет принадлежность ., классам ., К

Если классы К1,., К1 попарно не пересекаются, то описания объектов йх,., 8т сводятся в таблицу, строками которой являются описания, столбцами — значения признаков в этих описаниях. Строки упорядочены но классам — сначала идут описания объектов из Кь, затем из Кь,, если V < т. Указанная таблица называется таблицей обучения и обозначается грО -1 иго'

Рассмотрим действия, необходимые для построения алгоритмов вычисления оценок по шагам. Каждому шагу построения соответствуют определённые параметры алгоритма.

1. В наборе признаков {1,2,. ,п} выделяется совокупность подмножеств {(гъгг,. ,«*)} не обязательно одинаковой мощности. В дальнейшем выделенные подмножества называются опорными множествами алгоритма, а вся их совокупность — системой опорных множеств для А.

Иногда опорное подмножество О = (¿х, г2,., г а-) удобно задавать характеристическим булевым вектором и> = («х, «2,. ,ап), в котором а^ = • ■ • = а,к и остальные координаты равны 0. Система 0,А задаётся в этом случае булевой функцией /л(жх, •• •, хп) : /л(о5) = 1 тогда и только тогда, когда и> есть характеристический вектор для из Од. Очевидно, соответствия й <—> <—> /л взаимно однозначны.

Естественно вводится понятие и5— части ш1{Б)(и}3) описания в. Если /(5) = (ах,., а„), «¡г = • • • = а1к = 1, то 5/(5) = {ан,., щк) = £55.

При решении прикладных задач обычно рассматривались такие системы опорных множеств:

1) Од — есть совокупность тупиковых текстов [5],[23],[4] таблицы обучения Т°т;

2) — совокупность всех подмножеств {1,2,., п} одинаковой мощности к, 1 < к < п — 1;

3) и а — совокупность всех непустых подмножеств множества {1,2,., п}. 2. Для ш—частей описаний соБ, и Б' допустимых объектов 8, Б' задаётся функция близости В (ив, ив') > 0. В модели на способ задания В не накладывается существенных ограничений. При решении реальных задач рассматривались следующие типы функций В.

Пусть во множествах Мг,., Мп признаков 1,2,., п заданы полуметрики ( метрики без аксиомы треугольника ) р\,. ,рп.

1. Пусть шБ = (а;1,. ,а^),ц/5' = . .,Ь1к),е> 0; В(и>,й) = 1, если Рц (аг.; > 1-1.,) < В остальных случаях В = 0. Алгоритмы с функцией

В( 1) подробно изучены в [22].

2. Рассмотрим систему неравенств

Р\{а\,Ъ1) < £1, - • • ,Рп(ап,Ьп) < £п, — неотрицательные числа.

Сопоставим 3, в' булев вектор 5(Б, Б') = ,., 5п), = 1, если Рг(^, Ьг) < £{, 5г = 0 1фИ Рг(щ, к) > £г, I = 1, 2, . . . , П. Определение 5. Функция

В {со Б, шБ') = В ((а¿1 ,.,а,к), (Ьг1,., Ь^)) называется пороговой [2], [6], [8] , если однозначно определяется набором координат ., Sik вектора

5,5').

Приведём пример пороговой функции. Пусть, кроме числовых параметров еъ.,еп заданы целочисленные параметры . ,е\.£12 и {1,2,., п} = и1=1Мг, К П К» = 0 при V ф у. В(и1(Б),ш1{Б')) = 1, если и только если среди координат вектора 6(Б, Б') с номерами из ]Уг число единичных координат не меньше е\, число ненулевых — не больше ¿2) 2 = 1,2, .

3. Задаётся оценка близости Г (В (и) Б, и) Б')) — мера поощрения за величину близости В (соБ, и) Б'). Если 5 — объект, описание которого входит в обучающую информацию, Б' — распознаваемый объект, 7(5) — параметр, характеризующий представительность 5, р(со) — представительность (£;•<-» то обычно

Г(5(25, С5')) = Га(5,5') = 7(5) -р(2) • (1)

4. Определяется оценка Г,-(й") объекта 5" по классу К^.

Положим И7/ = А^- П . ,5т),/х(Ж/) — число элементов в

Тогда, например,

Г^5") = £ ' ¿фт) ' IV} • Г«з(5,$')» N - нормирующий множитель. 3

Этапы 1—4 описывают распознающий оператор Я а, переводящий начальную информацию Кг), ВД,., 5;)) = (/0(О, Ш) в числовую матрицу

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

Естественно, что описание Лд производится в соответствующих терминах. Отметим, что во всех описаниях распознающих алгоритмов в явной или неявной форме выполняется переход от начальной информации к числовой матрице {а^}^ — число распознаваемых в задаче объектов, I — число классов. Величины ац интерпретируются в терминологии размытых множеств [25] как значения функции принадлежности классу К у Мы будем пользоваться более коротким термином: "оценка по К?.

5. По набору (Ггх,., Ггг), — распознаваемый объект, — формируется информационный вектор адО^О = (а^,., € {0,1, Д}.

В алгоритмах вычисления оценок типичными являются линейные решающие правила: пусть заданы I последовательностей линейных форм Ц(хь-.,^) = + ■•■ + Ц + Ц+ъЗ = 1, —* = 2,3,.,/,., и параметры с^-, с2у, с^ < = 1,2,.,/.

Линейное решающее правило г а : = € К^) если Ь\ (аг1,., аи) > с2]\ — 0(5- ф. К)), если Ц(а*и ■ ■ ■, аи) < с^, = А ( алгоритм А не установил принадлежность классу Kj ) при с^ < Ь\{ац,., ац) < Су■

В дальнейшем под решающим правилом г а будем понимать оператор ГА{а^}дх1 = переводящий матрицу оценок в матрицу информационных векторов алгоритма А [9]. При построении общей теории распознающих алгоритмов на г а накладывается единственное условие корректности.

Определение 6- Решающее правило г,\ называется корректным, если для любой конечной совокупности допустимых объектов существует числовая матрица {ау}дХ1 такая, что

4{ОгЛ5Х( = (аи}дхг и сен,. ,ац — истинный информационный вектор для 5г',г = 1,., д.

Основной проблемой для алгоритмов вычисления оценок является проблема синтеза экстремального по функционалу качества алгоритма. Для этого прежде всего необходимо уметь строить эффективные процедуры для вычисления величин 1\7- = Г, (5').

Для различных простых вариантов моделей типа вычисления оценок эта задача решена в [7],[12],[9],[10],[13], [22],[20].

Заключение

В работе доказывается факт о свойстве корректности ( введённом в 115]) сужения ранее изучаемого семейства алгоритмов (рассмотренного в [17]). Демонстрируется применение данного утверждения на практике и изучается точность распознавания алгоритма, который по определению корректности абсолютно точно распознаёт заданную выборку, на новой выборке.

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

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

Доказано утверждение о существовании базиса на множестве алгоритмов с гиперповерхностями для произвольной задачи распознавания с тривиальными естественными ограничениями, что является усилением предыдущих аналогичных теоретических результатов: во первых, расширен класс задач; во вторых, сужен класс алгоритмов. Доказательство является с учётом замечаний главы конструктивным. Применение утверждения продемонстрировано на данных ряда прикладных задач (см. главу 2).

Чтобы уменьшить сложность доказательства путём наложения структуры, оно разделено на части, оформленные в виде лемм. Большинство лемм (с номерами 1,2 и 4) независимы друг от друга. Доказательства опираются на метод индукции, аппарат математического анализа, линейной алгебры, дискретной математики и комбинаторики. Доказательство теоремы объединяет утверждения лемм и опирается на предыдущие результаты теории распознавания. Доказательство сопровождается наглядными простыми примерами, что позволяет лучше понять как сами рассуждения, так и их возможную "алгоритмизацию", т.е. написание программы, повторяющую шаги доказательства.

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

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

1. Айзерман М.А., Броверман Э.М., Розенэр Л.И. Метод потенциальных функций в теории обучения машин, изд-во «Наука»СО, Новосибирск, 1969.

2. Баграновская З.В. О некоторых свойствах алгоритмов V-голосования, журн. «Кибернетика», № 6, К., 1975.

3. Вапник В.Н. Червоненкис А.Я. Теория распознавания образов, изд-во «Наука», М., 1974.

4. Дюкова Е.В. Об одном алгоритме построения тупиковых тестов, «Сборник по математической кибернетике», вып. 1, изд. II Московского медицинского института, 1975.

5. Дмитриев А.Н., Журавлёв Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений, сб. «Дискретный анализ», вып. 7, изд-во «Наука», СО, Новосибирск, 1966.

6. Гулямов Д.Х., Журавлёв Ю.И. Оценка качества экспертов, формирующих таблицу обучения в задаче распознавания образов, ЖВМиМФ, т.12,№ 4, М., 1982.

7. Гуревич И.Б., Журавлёв Ю.И. Минимизация булевых функций и эффективные формулы распознавания, журн. «Кибернетика», № 3, К., 1974.

8. Докторович А.Б. О применении алгоритмов вычисления оценок в задачах медицинской диагностики, сб. «Проблемы медицинской и биологической кибернетики», вып. 1, изд. II Московского медицинского института, 1975.

9. Журавлёв Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок, журн. «Кибернетика», № 3, К., 1971.

10. Журавлёв Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение, изд-во «Фан», Ташкент, 1974.

11. Журавлёв Ю.И. Алгоритмы распознавания, основанные на вычислении оценок. Содержательный смысл параметров, задающих алгоритм, Труды Международного сипозиума по практическому применению методов распозавания образов, изд. ВЦ АН СССР, М., 1973.

12. Журавлёв Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур, сб. «Проблемы прикладной математики н механики», изд-во «Наука», М., 1971.

13. Журавлёв Ю.И. Алгоритмы распознавания, основанные на вычислении оценок для задач с пересекающимися классами, Труды ВЦ Польской АН, вып. 145, Варшава, 1974.

14. Журавлёв Ю.И. Корректные алгебры над множествами некорректных ( эвристических ) алгоритмов. I. — «Кибернетика». К.,1977,№ 4.

15. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации, сб. «Проблемы кибернетики», вып. 33, изд-во «Наука», М., 1976.

16. Журавлёв Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации. ДАН СССР 231, 3, 1976, С. 532-535.

17. Журавлёв Ю.И. Корректные алгебры над множествами некорректных ( эвристических ) алгоритмов, журн. «Кибернетика», № 3, К., 1977.

18. Ильин В.А., Ким Г.Д., Лииейная алгебра и аналитическая геометрия. Издательство Московского университета. 2002.

19. Лысёнок Е.И. Корректность линейного замыкания распознающих алгоритмов, основанных на гиперплоскостях. ЖВМиМФ. т.49, № 10, С. 1885-1904, 2009.

20. Лысёнок Б.И. Простые формулы для подсчёта оценок в алгоритмах распознавания, основанных на голосовании по опорным множествам. ЖВМиМФ. т.44, № 9, С. 1708-1712, 2004.

21. Лысёнок Е.И. О некотором подходе выбора гиперплоскости для алгоритмов распознавания. ЖВМиМФ. т.50, N5 10, С. 1862-1864, 2010.

22. Мирошник. С.Н. Алгоритм голосования с непрерывной метрикой, журн. «Кибернетика», № 2, К., 1972.

23. Чегис И.А. Яблонский C.B. Логические способы контроля электрических схем, Труды Математического института им. В.А. Стеклова АН СССР, т.51, М., 1968.

24. Fu K.S. Syntactic Approaches to Pattern Recognition, Academy Press, New York, 1974.

25. Zadech L.A. Fuzzy Sets. «Information and Control», v.8, 1965.

26. Данные итальянского банка задач распознавания. http://www.isc.uci.edu/ mlearn/MLRepository.html.