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

• Лысёнок, Евгений Игоревич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Лысёнок, Евгений Игоревич

Введение

Глава

Глава

Глава

Введение диссертации (часть автореферата) на тему «Построение базиса на множестве алгоритмов, основанных на гиперплоскостях, для произвольной задачи распознавания»

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

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

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

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

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

Таким образом, на первом этапе собирается экспериментальный материал проверки той или иной гипотезы о методе решения конкретной задачи. Изучается класс задач, приводящих к задаче распознавания, например, задача прогнозирования в геологии. Изучение описаний месторождений и участков местности, где месторождения не обнаружены, приводит к гипотезе: множества описаний первого и второго класса разделяются достаточно простой поверхностью. Простейшей поверхностью является гиперплоскость. Уточнённая гипотеза: описания, выполненные набором числовых признаков и принадлежащие разным классам, разделяются гиперплоскостью. Проводится эксперимент на ЭВМ и показывается, что в 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).

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

Список литературы диссертационного исследования кандидат физико-математических наук Лысёнок, Евгений Игоревич, 2010 год

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.