автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему: Оптимальные коллективные решения в задачах распознавания и классификации

Автореферат диссертации по теме "Оптимальные коллективные решения в задачах распознавания и классификации"

РОССИЙСКАЯ ШДЕХШ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦШР

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

Рязанов Владимир Васильевич

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

05.13.16 - Приминание вычислительной та шика, иатеыатичэско-го моделирования а математических методов в научных исследованиях

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

Работа выполнена в Вычислительном центре Российское Акадэжи Наук.

доктор технических нале, профессор

доктор (Щзико-математических наук, профессор

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

Зашита состоятся '3&' 1994 г. в часов

на заседании специализированного Совета Д 002.32.06 при Вычислительном Центре РАН по адресу:

117967, Москва, ГСП-1, ул, Вавилова 40

С диссертацией морю ознакомиться в библиотеке МИ РАН

Автореферат разослан" 1994 г.

специализированного .Совета Д 002.32.06 кандидат физико-матеыэтачесюп наук

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

3 то же время дои математического моделирования явлений, ситуация, объектов или1 процессов необходам определенный ■уровень знаний и информации, связанных с объектами исследований. Прежде всего необходимо иметь качественную модель объекта исследования, то есть знать, какие факторы являются определяющими и каковы связи между ниш. Необходимо знать систему закономерностей, уравнений, функционалов и т.п., описывающих адекватно исследуемый объект. Наконец, необходим определенный объем информации' и уровень еб точности для точного вычисления в математических моделях различных величин, решения уравнений и т.п. Отсутствие каких-либо из данных условий зачастую приводит к непреодолимым в рамках математического моделирования проблемам.

Здесь можно отметить следующие две типичные практические ситуации: "

- имеется необходимость в исследовании и анализе новых процессов или явлений,'для которых отсутствуют математические модели, а их разработка требует определенного времени _:иш невозможна на данном этапе знаний о предметной области:

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

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

ческсго моделирования отмечено академиком А.А.Дородницыным1 „

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

За 30-40 лет интенсивного развития теории распознавания оыли созданы сотни алгоритмов распознавания и классификации, основанные на различных идеях, гипотезах и принципах. В настоящее время выделяются следующие три последовательных этапа процесса конструирования точных распознающих алгоритмов по выборкам прецедентов:

- создание параметрических моделей распознавания, основанных на эмпирических закономерностях;

- оптимизация параметрических моделей распознавания;

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

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

1 Дородницын А.А. Проблемы математического моделирования в описательных науках// Кибернетика. 1983, Ы, С.6-Ю.

адураЕлэв О. И. 00 алгебраическом подходе к решению задач распознавания или классификации// Проблемы кибернетики. М.: Наука, 1978. Внп. С.5-68.

вые , результаты получена Ю.й.Журавлевым (алгебраическая теория распознавания) и его учениками, правде всего академиком РАО В.Л.Магросовым и чл^н.-корр. РАЕН К.В.Рудаковым; данные вопросы в настоящее раОотэ не рассматриваются.

Известные модели распознавания, основанные на поиске по обучающим данным а;лгарических закономерностей, ориентированы обычно на определенный тип признаков, требуют выполнения некоторых условий или гипотез на начальной информации или ограничены использованием эвристических и локальных средств. Таким образом, актуальным направлением является создание новых, обобщающее, известные моделей распознавания с эмпирическими закономерностями, существующие метода оптимизации сложных многопараме-рических моделей как правило связаны либо с построением локальных решений в отдельных параметрических подоросграю. убвх, либо с оптимизацией линейных решающих правил. Поэтом;, исследование оптимизационных проблем в '¿_. многопараметричесю» с, существенно нелинейных моделях с разнотипными параметрами, разработка методов оптимизации моделей в полных параметрических пространствах является ' ■ также актуальной «мой исследований. Третьим актуальным направлешоч, разгшаемом в настоящей работе, является разработка аьзлогов алгебраического подхода в теории классификации (таксономии), с целью автоматизации построения оптимальных решений задач классификации на базе имещихся коллективов эвристических процедур.

Соответствие исследовательским планам. Диссертация выполнена в соответствии с плановыми НИР : Ц РАН "Развитие алгоритмического и программного обеспечения для применения вычислительных машин при решении задач прогнозирования и диагностики на базе алгебраических и . огических методов"(НГР 0Г.86.0 130490), Дискретные и неклассичесние модели обработки информации и принятия решений (Тема 1.13.12.6), Алгебраические метода в теории распознавания и прогнозирования (Программа "Перспективные информационные технологии", решение ГККГ * 836), Грантом РФШ * 93-012-457: Математические метода синтеза решений неклассических задач экстраполяции (в том числе гад1ч распознавания, классификации и прогнозирования ), тремя хозяйственными договорами.

Цель работы. Реальностью настоящего этапа развития теории распознавания к классификации (кластерного анализа,

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

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

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

Научная новизна. I. Предложен новый общий подход к формализации понятия "эмпирическая закономерность" для задач распознавания со стандартными начальны.-.. информациями, как коллективов специальных подмножеств пространства допустишь признаковых описаний - оптимальных систем признаковых окрестностей. Разработаны параметрические и непараметричзс-кие способы их описания. Задачи нахождения оптимальных систем признаковых окрестностей пол юмиально сведены к решению специальных линейных (БМС-ЦЛП) и билинейных задач целочисленного программирования. Исследована взаимосвязь мевду размэрностью задачи БМС-ВДП и величиной оптимума функционала качества системы -.окрестностей. Разработан новый класс распознающих алгоритмов - основанных на локальных критериях оптимальности.

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

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

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

4. Впервые разработан аналог алгебраического подхода а теории распознавания для решения задач классификации (таксономии) - теория комитетного синтеза коллективных решений задачи классификации. Введены и исследованы критерии оптимальности коллективных решений, разработан эффективный алгоритм поиска оптимальных комитетннх решений при использовании хэмминговой метрики в пространства матриц оценок.

5. Впервые предложена и реализована в программных системах ДИСАРО и ОБРАЗ идеология последовательно-параллельного исследования стандартных информация и решения задач распознавания и классификации.

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

- разработка качественных моделей процессов, ситуаций и явлений по прецедентной информации в малоформализованных областях;

- создание новых моделей распознавания, основанных на поиске эмпирических закономерностей;

- разработка специализированных методов оптимизации различных многопараметричвсккх моделей распознавания;

- решение задач диагностики, классификации, прогноза, .

распознавания и контроля ® медицине, геологии, технике, социологии и других областях. •

Апробация. Основные результаты диссертации докладывались и обсувдались на I Всесоюзном совещании по статистическому и дискретному анализу нечисловое информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, IS8I г.). Советско-Гермаяских семинарах "Дискретная математика и ев приложения в кибернетика" (Росток, 1977 г., Москва, 1903 г., Алма-Ата, 1985 г., Тбилиси, 1986 г., Самарканд, 1987 г.), Первой - пятой Всесоюзны! конференциях "Математические методы распознавания образов" (Москва, 1983 г.. Дшппкан , 1985 г., Львов, 1987 г», Рига, 1989 г., Москва,. 1991 г.), Всероссийской конференции "Математические методы распознавания образов"(Москва, 1993 г.), Международных конференциях "Проблемы искусственного интеллекта и распознавания образов" (Киев, 1984 г.), Советско-йшском семинаре по практическому распознаванию (Тбилиси, 1987 г.), "Информационные технологии в обработке изображений и распознавании образов" (Львов, 1990 г.),"Информатика-88" (Гавана, 1988 г. ),"Информатиха-90" (Гавана, 1990 г.), Международных школах-семинарах по биокибернетике (Варшава, 1986 г., 1987 г.), Российско-Германском семинаре "Понимание изображений и распознавание образов" (Зрланген, 1993 г.), семинарах Вычислительного центра РАН (1977 г., 1981 г., 1987 г., 1994г.), факультета БЫК ШУ (1977 г.). Института Социально-экономических проблем РАН (Санкт-Петербург, 1989 г.), Московского физико-технического института (1977 г., 1994 г.), Белорусского Государственного университета (Минск, 1986 г.). Сибирского научно-исследовательского института нефтяной промышленности (Тюмень,1992 г.), Института математики АН ГДР (Берлин, 1985 г.), Гумбольд--университета (Берлин, 1983 г.), Вильгельм Пик- университета (Росток, 1983 г.), Высшей технической школы (Магдебург, 1985 г.), Института математики, кибернетики и физики АН Кубы (Гавана, IS88 г., 1990 г.).

Реализация. Разработанные в диссертации метода, алгоритмы и программные системы были использованы при решении различных прикладных задач (более 20 наименований) и внедрены в П/0 "ЮГАНСКНЕФТЕГАЗ" (Нефтеюганск, Г986 г.), СибНШНП (Тюмень, 1992 г.), "ПШРПРОГРтсКСТМ" (Тверь, 1989 г. ), рядэ научных и производственных учреждения МО, Министерства

здравохранения, Министерства сельского хозяйства.

Публикации. Результаты опубликованы в 41 печатной работа.. Личный вклад автора в совместных работах, имепцих прикладной характер, состоит в формальных постановках, разработке алгоритмов и программ, связанных с реализацией методов построения оптимальных коллективных решений в задачах распознавания и классификации. В статье /35/ автором написаны первые две глав».

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы из 174 наименований. Объем диссертации 263 стр. машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы исследований и приводится краткая характеристика реботы в целом.

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

Рассматривается задача распознавания в стандартной постановке, когда исследуемое множество объектов К представимо в виде объединения I подмножеств К;, Кг. К1Р называемых классами, заданы начальная информация 10 о классах и описание 1(5) произвольного объекта 3 из *.

Требуется по информации 10 и 1(8) для I = 1,2. г

определить значения свойств 5 е Предполагается, что описания ГСЯ; определяются наборами п числовых (что для нас в принципе не■существенно ) признаков, начальная информация Г0 (обучающая информация) задается выборкой описаний 1(31),1(32). г1(3т), 1(Зу)=(аи1,аиг. ат), в виде числовой таблицы Т в которой представлены объекты всех X классов с известным распределением их по классы. Для задачи классификации метки классов для объектов обучающей информации не требуются.

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

в диссертации методов построения оптимальных коллективных решения задач распознавания и классификации.

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

Алгоритмы распознавания, основанные на локальных критериях оптимальности, базируются на понятиях признаковых окрестностей - [0> и систем признаковых окрестностей - (0), критериев качества окрестностей - критериев качества систем окрестностей - Р, распознающих операторов - Я и решающих правил - г. Модель распознавания, основанная на локальных критериях оптимальности, определяется конкретизацией элементов набора <С0),(О)

Признаковой окрестностью О (или просто окрестностью) называется произвольное подмножество пространства допустимых описаний объектов распознавания, для которого О Л 10 Ф 0. Критерием качества окрестности 0 (локг 'ьным функционалом) называется функционал /: (О) —*■ Критерием качества

системы окрестностей 0 = (О,,02. 0^) (глобальным функционалом) называется функционал Р: (О) —>- Я .

Вводятся определения эквивалентных окрестностей, допустимых и монотонных систем окрестностей.

. гг(3)) = (а1(8),аг(8). а1(8)). Значения

Задача целочисленного линейного программирования называется задачей с блочно-монотонными столбцами коэффициентов системы ограничений и целевого функционала (БМС-ЦШ задача), ее д ока формулируется в следующем виде:

где к эффициенгы целевого функционала я матрицы ограничений удовлетворяют условиям:

а^ > а* > О, а*^ €fO,tJ, v-r,2. k, ц=Г,2. hv-J.

В $2 описан експергно-таксономический подход к определению окрестностей и систем окрестностей. Исходные монотонные системы окрестностей Ov, v=1,2. к, являются

семействами окрестностей О = О CS, ,d ) » fS: pfS.S. J <

d . ftv» где S, - эталоны (задастся экспертом

или как решение задачи таксономии), р-мэтрика в пространстве признаковых описаний, вычисляются по информации 10, < dv(i+>, \i=1,2. hv-1. Локальный функционал /ГО^.) =

= где р - произвольная метрика на Я1,

Глобальный функционал определяется как F(0) - 2

где Q=(0 . ,0. . 0 > - произвольная система окрестностей. Задача поиска оптимальной системы признаковых окрестностей сведена к решению некоторой задачи БМС-1Щ1 (теорема 2.1), единичным компонентам решения которой соответствуют окрестности оптимальной системы окрестностей.

В §3 рассматриваются параметрические методы синтеза систем окрестностей. Предполагается, что Я= . т. Окрестности

А. € и/, называются х* - эквивалентными, если

Задача Найти минимум ?(0(((<^,е)>). гт) по множеству "опустимых значений параметров ]=1,2. т)

<Ж(ы,'-))) - разделяющая классы система окрестностей; 3. окрестности А. £ для кэвдого фиксированного

J=1. m п и3 являются г1 - эквивалентным.

Системы окрестностей оявлящнвся рвяенхяш задача называются равномерно овлиадышма раздампЦвк классы системам*. Рассматриваются следупциэ задача:

¿оказано (теорема 2.5), что репешэ задачи поиска равномерно оптимальной разделяпцей системы окрестностей 0(((ы*,е*)>) =

-эквивалентными окрестностями o'x(e*J). X^'u*-', однозначно определяется решениями (z*J,y*Ji т сформулированных выше независимых билинейных задач целочисленного программирования, причем:

1) коэффйциёнты t*1,2r. ¡t(K,j), получены в результате применения первого и второго алгоритмов сокращения к последовательностям CJX;

2) значениям у"х\=1 соответствуют ^ =1>.

Набор (J;uv)=(aft ,aJt ,---aJi ),где (ú*J=(t;,í2. tfc),

называется равномерно оптимальным представительным e*J-набором. Используя в задаче Z3 различные другие варианты ограничений на множества допустимых систем окрестностей вводятся понятия равномерно оптимальных систем окрестностей, оптимальных систем окрестностей и соответствующие им понятия равномерно оптимальных e-наборов фиксированной длины и оптимальных е-наборов фиксированной длины. Методы их поиска . аналогичны методам решения задачи . _ ,

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

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

Глава 3 посвящена проблеме оптимизации сложных

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

моделями понимаются модели, использующие в своих описаниях

наборы многомерных разнотипных параметров. Исследуется

задача оптимизации моделей, основанных на принципе частичной

прецэдентности (алгоритмы вычисления оценок, модель с

тупиковыми тестами, модель с представительными наборами) в

стандартной ■ постановке. Данные модели оперируют с

параметрами, характеризующими точности измерения признаков -

Е=(е;,е2. ел),информативность признаков- р=(р,,р2. ря),

представительность эталонных объектов - 7=(7),72. 7т),

параметрами решающего правила в^, 1=1,2. )=1,2. 1+2

(или б(, б2 при использовании голосования "по большинству").

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

функционала качества £ (доля правильных отве-

тон), где = I при правильном прогнозе и %lJ =0 при неправильном прогнозе или отказе от распознавания алгоритмом А объекта Б1 контрольной выборки = (в^Б^. ,5^> по отношению к классу К>. Задача 2, состоит в поиске максимальной совместной подсистемы системы неравенств, левые части которых являются полилинейными формами от р,7,С, а коэффициенты - функциями параметров е. Известно, что данная задача может быть сведена к задаче поиска максимального верхнего нуля специальной трудновычислимой монотонной булевой функции и относится к классу сложных комбинаторных задач. Привод.--ся ссылки на существующие локальные и эвристические метода оптимизации.

В настоящей работе предложен новый общий подход к решению задачи 2Т, основанный на разложении процесса распознавания на три последовательных этапа: вычисления матриц близости, матриц оценок, информационных матриц результатов распознавания. Соответственно, алгоритм распознавания представляется как произведение (последовательное выполнение справа налево) А=гВВ оператора близости

распознающего оператора В(р,1)• ВСЕ) —► |Г^(£,р,7) ¡^г и гГ|в^:'|Г^<е.р.т>| > " решающего

правила. Для построения оптимального алгоритма распознавания (решения задачи 21) предложено использовать оптимальные в соответствующих подпространствах операторы В,. Я, г. С данной целью введены " специальные критерии оптимальности данных операторов, проведено их качественное исследование, показана взаимосвязь оптимальных решений различных экстремальных задач, разработаны соответствуквд'.э методы оптимизации.

В §2 вводятся критерии оптимальности операторов близости, как расстояния матриц близости В(е) до "потенциально- наилучшей" матрицы близости (при специальных ограничениях на множества допустимых <В(е)>) в различных метрических пространствах. Если ^-п" то метР!по1

порождают, соответственно, критерии <р7(е1, Фг(е). Критерии оптимальности распознающих операторов определяются как расстояния матриц оценок 1 (б - сояз£) до

множеств "потенциально - наилучших" матриц оценок для контрольной информации I при заданном уровне осторожности д в пространстве числовых матриц д-1 с метрикой р; (задача Ъ2, минимизация функционала О), или как расстояния в той же метрике до "абсолютно-наилучшей матрицы оценок" (задача %3, минимизация функционала ?). Ъг является задачей минимизации билинейной Форш при билинейных ограничениях с положительными коэффициентами, Ъ3 - задачей минимизации билинейной формы при ограничениях: 12120. Критерием

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

§3 посвящен качественному исследованию рассматриваемых экстремальных задач и взаимосвязи их оптимальных решений. Рассматриваются монотонно возрастающие последовательности Сх=0,с*,с*. всевозможных значений величин

1,2. .,т, 3=1,2. Доказано, что для модели вычисления оценок ЯИЛ,р,£,-у,С;,й.,) справедливы соотношения:

■« /(p.i.ej - au /(p.7.«V ml» «(p.T.eJ • sta ®rp.7.e.>. (p,y.*)(D (p.j.mHS (p.f,*)iJ) (p.f.e)tt

В - (p,7,e:f)f»0,t»T)0.e(E). E-E(«E2« . «En, E^ - подаосж-довательвости (7х, построенные в результате применения первого в второго алгоритмов сокращения, р.7 - фиксированы. Дм частного случая fXiO.U'V, показано,

что параметры р могут быть исключены из описания модели.

Задачам Z,,Z_, Z_ можно поставить, в соответствие их

дискретные аналэгх Z>;Z2,Z3, в которых 7£3", ptfi, «<Е . Данные задача имеют самостоятельный интерес, поскольку единичные компоненты векторов р я 7 оптимальных решений позволяют выделять информативную часть таблицы обучения одновременно го признакам и по »талонам. Показано, что для модели вычисления оценок решение задачи Z3

на £ достигается в одной из точек множества

Теореад з.Б-3,7 показывают взаимосвязь между задачей оптимизации оператора близости и задачами оптимизация распознающего оператора я распознающего алгоритма. Доказано, что для модели вычисления оценок Я(Ь,р,е,7,в) справедливы

если ein o-mn(«in((av-«v_f

o-conat. Таким образом, оптимальные значения параметров е* для оператора близости являются оптимальными для распознатих операторов при "естественном" выборе параметров р, 7 и дают вившо оценку для максимума f(A(k,p,e,f,0)), причем чем меньше значение «in тем более высокая

точность.распознающего алгоритма нам гарантируется.

Далее рассматривается взаимосвязь оптимальных распознающих операторов ж распознай х алгоритмов. Для систем линейных неравенств вида (Ък,х) < о„, Ш, (dl,х) >.of, UIt и связанной с ними задачи линейного/ программирования Ч(Ь,г? —* vliii при ограничениях » о., icl, й= J ьс1,

вводится понятие согласованности. 'Георема 3.8 утверждает,

- что «сп приведенные система а задаче ЛИ является согдасовавяша. тр ревввхе эадачя т удовлетворяет некоторой максимальной. совместной подсистеме системв (Ь1.х) < а2. Ш* (¿1,х) > о,. 1<Х. Из данного вахта непосредственно следуют утверждения о взаимосвязи оптимальных решений задачи %г по параметрам р, щж фиксированных значениях остальных параметров (или по параметрам 7 при вихсированных значениях остальных параметров) с решением задач» г>: если возникающие систеад линейных неравенств в задаче 2Г ж задача Ш в задаче Ъг являются согласованными, то оптимальные решения задач 1г будут локвльно-оптииалышмиреаениями задач в соответствующих параметрмческих подпространствах.

В $4 описаны методы оптимизации оператора близости, распознающего оператора и распознающего алгоритма.

Оптимизация оператора близости основана на использовании теоремы 3.11 (для функционала ф((£Л я теоремы 3.12 (для функционала ц>2(е)). обеспечивающих полиномиальное сведение задач оптимизации оператора близости к задачам ЕМС-ЦЛП; "длй решения последней использовалась локальные методы наискорейшего спуска.

Ддя оптимизация распознающего оператора предложены численные метода решения задач 1'г, 2'3.

Задача 1г сводится к решений последовательности систем нелинейных неравенств, методы решения которых разработаны в главе 4. Для решения ев дискретного аналога 1'г использовздась локальные градиентные методы, учитывающие ев специфику. Для решения задачи 2'3 (решение 13 является одним из решений ?.'3) были разработаны специальные локальные метода, основанные на использовании полученной линейной по вариациям параметров верхней оценки вариаций функционала Р(р,7) в допустимой точке (р.т) на окрестностях произвольного радиуса. Из текуией точки (р,7) осуществляется переход в точку (р' ,7'), которая находится за 0Шг1о& п *■ тт?1<щ я) операций и обеспечивает минимальную верхами оценку для

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

В §5 приведенврезультаты оптимизации модели вычисления

оценок на примере одной задачи медицинской диагностики, а также сравнение полученных оптимальных алгоритмов (76% правильных ответов и S% отказов) с классическими статистическими методами (метод "к ближайших соседей"- 54S и 12%, соответственно; линейный дискриминант Фишера- 705» и 8%).

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

В §1 приводятся основные принципы релаксационных алгоритмов решения систем выпуклых неравенств, разработанных в работах Еремина И.И.

Рассматривается задача нахождения некоторого решения

совместной системы норавенств f> (х) $ О, J=1,2. m, где

fj (х) - выпуклые гладкие функции, определенные на Я", Ы -

множество её решений. Определяется отображение ф(х):Яп—*■ Rn

(х - Ш(хМхУ1Ш)1г , I(x)*fl,

1. d(x) = шах /Лх)=/ fxj. ы(х) = v/ (U,

3. d(x) = \ U(X) = 5 y/jd),

Xj>u - фиксированные числа. Функции a¡(xi, dfx) достаточно считат«- определенными на Rn\M. В зависимости от выбора пары и(т), будем различать отображения <р( i.x), ф?(х) и ф3(х), соответственно.

Строится последовательность х',лг2. xv. xv*г=ф(х"),

х1 £ И, которая сходится к одному из решений системы при условии Inf eN>0. Для случаев ф,(х) и фд(г) доказана линейная скорость еб сходимости ' (слабой) при ограниченности градиентов vfj (х) и существовании x°iU, /^(х°)<0, J=1,2. п.1 Соответственно выбору ф(г) будем различать алгср-тш Д(, Аг и А3. f 1втрудно привести примеры распространенных ситуаций, когда вычислительные затраты при работе приведенных алгоритмов могут быть сколь угодно велики (при высоких затратах на вычисления значений функций или их градиентов, при больших размерностях' задачи, или наличии "овражных" ситуаций).

В §2 предложен один подход к ускорении сходимости релаксационного метода. Вводится параметрическое множество отображений (ф(9Д)>, являющееся расширением отображений ф,, <р2 и <р3, и бесконечномерное параметрическое множество релаксационных алгоритмов (А). Каждый алгоритм из CA) на каждой итерации использует определенное отображение из (р).

Набор Ks = CXj| > О, JtJ(x)=il j ft(x) ^ О )) называется допустимым, если > 0> Л I(x) t ¡3. Допустимым направлением в точке х / ä называется направление ы(х) = = £ г), где допустимый набор для точки х, Л(х)-JtJ(x)

- множество допустимых в х наборов \х.

Шаг ге(\ v)= ]> Ä. / (rv)/\m(xv)\, вычисленный в точке

xv0 для допустимого в х" направления u(xv), называется оптимальным гарантированным шагом (ОВД. Определяется множество отображений Ф = (ф), ф=ф<,0-Л,):

Через A(9ylAv; v=I,2. ) обозначается релаксационный алгоритм , определяющий последовательность х' ,-Г2. xv.

1 Еремин И.И. О скорости сходимости- в методе фейероЕоких приближений// Мат. заметки. 1968. Т. 4, Ж. С. 53-61.

озгласно 4>fev'x"J. v»I,2. (x' - произвольно). где XK«XJr» - допустимые наборы. 9V<(0,2), 111* ву > О, - OIJD *

ufxvj > допустимые направления. Релаксационный алгоритм A*kA(Qv,\v; называется оптимальным, веял вv «1а

значения находятся из условия ж(А.г») —» авх .

Для оптимального алгоритма Л справедлива минимальная верхняя оценка |xv* '-*|2 < |xv-*|2 ais(X v)* относительно других вариантов релаксационного сдвига из х". Показано, что xv*' является проекцией xv на многогранник K(xv):Wj(xv),x-xu)+fJlxv) i О, JtJ(xv). и, следовательно,

монет быть найден также путем ревения задачи |xv-x| —•> вйп.

Через А обозначим приближение алгоритма Л, под которым понимается произвольный релаксационный алгоритм с условием: ОПП a(\fv)> пах( xf(kxv), здесь ае, и являются

0Ш,- соответствующие алгоритмам А, и А3 в точхе xv. Сходимость и оценка скорости сходимости А и А* следуют из сходимости л,:и при этом справедлива оценка: jxv+,-tf| < < e^lx"-*!. e^U-sf/Nfcf)"*, tt > 1, где 0Ш \ > 1, fft, Ct - const, t=i, 3-

B J3 предлагаются алгоритмы типа л, не требующие решения вспомогательных задач квадратичного программирования. Алгоритм Л4 на каждом ваге последовательности итераций осуществляет релаксационный сдвиг согласно тому алгоритму из iAJtA2,A3), который обеспечивает максимальное относительно других значение x(Kxv). Показано, что для случаев "очень тупых", "прямоугольных" и "очень острых" конусов, на вершины которых проецируется xv оптимальным алгоритмом 4*. алгоритм Л4 работает как А* или (в последнем случае) предпочтительнее чем А;, а£. Алгоритм а5 является обобщением А, и проецирует

xv if. (х")=0) на наиболее удаленное от ху множество

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

В §5 рассмотрен случай плоских систем, под которыми

понимаются сястеш ft(x)* J la*!»».

со еле лущима свойствами:

V*(1,Z. HtJ, I2=(n1*t,m^e. mi, e > О, |£|</. ( для

I.либо Лх)ПГ'=0, либо ЛхЮГЧэ; 2. «Г(х)П1г^0,

Доказано, что применение в первой ситуации релаксационного сдвига согласно обеспечивает сдвиг, близкий к

оптимальному (теорема 4.2). При наличии второй ситуации использование алгоритма типа ' А3 обеспечивает большую величину ОШ. Получены оценки сверху для |х'-а|, где а -- проекция х на *'■=fx" | fj(z') < О, JeJ(x)), х'=ф(х).

В главе Ь рассматривается проблема построения оптимальных решений задачи классификации (таксономии) на основе конечных наборов еб решений, полученных различными эвристическими классифишрухстми алгоритмами.

В §1 приводятся формализации классифицирующего алгоритма и комитетного синтеза коллективных решений. Алгоритмом таксономии называется алгоритм, переводящий описания JAS) объектов 5, ,Sn, . S в класс эквивалентности

являются эквивалентными, если они равны с точностью до перестановки столбцов, каздая информационная матрица Ia,j 1ж, ¡ опредэляет класс эквиваленгности Отметим, что

результатом применения произвольного эвристического алгоритма таксономии к Jm(S) является покрытие (но обязательно разбиение) выборки таксонами.

Пусть заданы результаты применения п эвристических алгоритмов таксономии <4®, к выборке S;,S2. Se:

Предполагается, что Iv не содержат равные или нулевые столбцы. Е" едятся обозначения: L= jaaxíl rlz. ln); Dv- множество числовых матриц |-г удовлетворяющих ограничени-

- 22 -\ X. ям: ТхГ, J'1.2. L, J х"..*1,1*1,2. 1

- информационная матрица, полученная из добавлением справа L-lv нулевых столбцов; I'v - произвольный элемент множества JC(I*J. Можно считать» что каждый алгоритм v=f,2. n, вычислил K<X*J. Между множествами К я D «■ Ш обозначаются прямые произведения множеств JC(Г*; и Dv,v*1,2. п, соответственно:

В. Г&, где В = Ib^l^, btJ?0.

называется сумматором, если Ъ = J а'*. Матрицы В называются

матрицами оценок. Комитетным синтезом информационной матрицы на элементе Г<3 называется ев вычисление

r(B(T)) при условиях: В - сумматор, г- пороговое решающее •1, 1*1,2. m;

правило, ctJ « A, e^>btJ>e[, J=1,2. L;

где oJ.Oj, t=1,2. m - параметры решающего правила.

Показано, что оператор гЗ ("произведение операторов В и

г) осуществляет отображение 3 на некоторое множество Kc*<*:(lc