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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Факультет Вычислительной Математики и Кибернетики

Р Г Б ОД

На правах рукописи УДК 519.8

Белянюга Георгий Андреевич

ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКОЙ ИГРЫ РАСПОЗНАВАНИЯ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1996

Работа выполнена на кафедре исследования операций факультета Вычислительной математики и

кибернетики Московского Государственного Университета им. М.В.Ломоносова

Научный руководитель: кандидат физико-математических наук

доцент Морозов В.В.

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

Горелик В.А.

кандидат физико-математических наук Бенинг В.Е.

Ведущая организация: ГП Московский Институт Теплотехники

Защита состоится " 13 " декабря 1996 г. в У/ часов на заседании Специализированного Совета Д 053.05.38 по математике в Московском государственном университете им.М.В.Ломоносова по адресу: 119899 Москва, Ленинские горы, МГУ им.М.В Ломоносова, 2-й уч. корпус, факультет ВМиК, ауд. 685.

С диссертацией можно ознакомиться в научной библиотеке факультета ВМиК. Автореферат разослан " 13 " ноября 1996 г.

Ученый секретарь Специализированного Совета

профессор , Н.П.Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Цель работы

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

з

закона распределения пространства признаков для объектов распознаваемых классов. Функция выигрыша определяется как вероятность ошибки распознавания.

'" Научная новизна

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

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

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

Апробация работы . Результаты настоящей работы докладывались на Международной конференции студентов и аспирантов "Воробьевы горы - 95" (Москва, апрель 1995); на Восьмой международной конференции по непараметрическим методам в кибернетике (Красноярск, октябрь 1995); на Первой международной конференции по исследованию операций (Москва, апрель 1996); на Втором Сибирском Конгрессе по прикладной и индустриальной математике (Новосибирск, июнь 1996). Доклады по теме диссертации включены в программу Двадцатой международной конференции по компьютерной и индустриальной математике (Кёнчжу, Южная Корея, октябрь 1996). Работа проводимая по тематике диссертации поддержана Российским Фондом Фундаментальных Исследований (грант N 95-01-00732а).

Публикации

Основное содержание работы изложено в работах [1-4].

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

объем работы составляет 108 страниц. Изложение иллюстрируется 12 рисунками. В приложении приведены тексты программ на языке Паскаль.

СОДЕРЖАНИЕ РАБОТЫ Во введении делается обзор имеющихся результатов по теме диссертации, обосновывается ее актуальность, формулируется цель работы и излагается ее краткое содержание. Здесь же описывается формальная постановка задачи, даются необходимые определения и вводятся соответствующие обозначения.

Данная задача формулируется в виде многомерной статистической игры двух лиц, которых мы в дальнейшем будем называть игроком 1 и игроком 2. Игрок 1 создает некоторую совокупность объектов или явлений, которая может быть заранее разбита на два непересекающихся множества - классы 1 и 2. При этом он стремится с помощью средств противодействия, принадлежащих распознаваемым объектам, наилучшим образом снизить эффективность распознавания указанных объектов. Под стратегией игрока I мы будем понимать набор конкретных параметров средств противодействия х=(а,Ь,БД) е Х=АхВх5хЛ, определяющих многомерные плотности распределения вероятностей числовых значений признаков распознавания:

/, (г) = «2лГ№Тп ехр{-<2(г)/2) /г (~) = ((2яГ|Я|Г,/2 ехр{-Т{т) / 2)

где = Т(г) = (:-Ь)Ц-\2-Ь)т

Игрок 2 разрабатывает систему распознавания объектов или явлений, созданных игроком 1 и при этом стремится наиболее

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

F(x,y) = pi J fx(z)dz + рг f/2(z)dz V Em\V

Задача состоит в решении игры Г-<X, Y,F(x.y)>, т.е. в определении оптимальных стратегий обоих игроков.

В главе 1 рассматривается одномерный вариант статистической игры распознавания. В этом случае стратегия первого игрока х-(а.Ьлт), где а и b - математические ожидания, a î и г - дисперсии гауссовых законов распределения вероятностей числовых значений признаков для двух классов объектов. Стратегией второго игрока является подмножество числовой прямой V, с помощью которого производится классификация объектов.

В §1 исследуются элементарные свойства одномерной игры, не зависящие от вида множества V. Показывается, что если существует стратегия х такая, что

D(x) = - Ь)2 -(s-г) In (fist pi г)) < 0 , (*)

то первый игрок может снизить эффективность распознавания до min[pi,p2]. Наилучшим ответом второго игрока на эту стратегию будет являться или V=E! или V-0. Находится точка, в которой достигается минимум выражения D(x), что позволяет быстро проверять выполнение условия (*).

В §2 рассматривается одномерная статистическая игра распознавания с решающим правилом классификации, определяющим стратегию второго игрока, в виде полупрямой (у,+0°) или (~со,_у). На множество стратегий первого игрока накладываются следующие ограничения: отрезки изменения математических ожиданий

[я,а],и>М>а <Ь считаются непересекающимися; дисперсии считаются принадлежащими отрезкам [«,«], [г, г]. Таким образом, ^ = У={(у,р) 1 уеЕ1, р е{1,2}}. Причем пара

(у,1) задает классификационное множество (у,+оо), а пара (у.2) -множество (-ао,у). В предположении р!<рг показывается, что стратегия р-\ всегда лучше, чем р =2.0сновным результатом данного параграфа является доказательство существования седловой точки

5*=5, г* = г, у -уг (5,г), при у2,г)йа;

5* такое, что у2(я',г)=а, г*=г, у*=а, при у2(£,г)>а£у2(5,г);

5*=5, г'=г, у'=у2(я'У), при Ь2у2и,г)>а;

/=5, г* такое, что у2(з, г')=Ь, у"=Ь, при у2(я,г)>Ь^.у2{в,г)-,

г'=г, у'=у2^',г'), при у2(з,г)>Ь, где у2~ наибольший из корней уравнения р1 /¡(г) =р2/2(г). В § 3 исследуется одномерная статистическая игра распознавания с решающим правилом классификации в виде отрезка [уиу2] или дополняющего его до полупрямой множества. Отрезки изменения математических ожиданий считаются совпадающими : [-с,с].

а = а ,Ь =Ь,

Дисперсии считаются фиксированными и равными э, г. 5<г. Таким образом, множество стратегий первого игрока >ф-}х{/-},

множество стратегий второго игрока У= {(у; ,у:) | у/,Е1}. Если у; <у2, то классификационным множеством будет интервал (у/ а если )>1>у: , то множество (-оо,у:)и( у^, Основным результатом этого параграфа является определение оптимальных стратегий первого и второго игроков, нахождение максимина и минимакса. Показывается, что в общем случае седловая точка в чистых стратегиях отсутствует.

В § 4 в предположениях предыдущего параграфа исследуется смешанное расширение игры. Седловая точка ищется для стратегий вида :

= о,

где ф(1) - функция плотности для вероятностного распределения математического ожидания первого объекта, 1с - индикатор точки с.

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

В § 5 рассматривается вариант одномерной статистической игры, когда множество стратегий второго игрока удовлетворяет условиям: существуют такие с',с", что [с',с"]сА , [с', с" ]сВ и |с"-с'\> З^я-г\.

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

./с'+с" ^ и-С' + С"

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

В главе 2 рассматриваются многомерные статистические игры распознавания с линейными или кусочно-линейными решающими правилами. Особое внимание уделяется введенному классу билинейных классификаторов:

Н= <ЬТ < /2}. В § 1 рассматриваются игры, которые оператором проектирования - < п, х >, где х" е Е1,п е Ё\ х е Е" могут быть сведены к одному из рассмотренных одномерных случаев. Показывается, что на них могут быть распространены результаты, полученные в Главе 1.

В § 2 исследуется вопрос об определении оптимальных стратегий первого и второго игроков в случае применения билинейного решающего правила. Множество стратегий первого игрока имеет вид:. Х=АхВх{5}х{11}, где А.ВеЕ?, 5,Ямножество стратегий второго игрока - У={(к,1] I, .¡¿еЕ1} задает классификационное

множество V - [г\/, < кгГ < 12) ■

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

быть найдены по следующим формулам:

к^ф-аХБ+аЯУ1

. _ Нка'-СУкЬ'+^/о "...... П-'-С, '

где

Аз

а-

Р\

\2=112~каТ

(кат-кЬт)2-(Н-С)1п

°Рг

Щ

в=тт н^кяк7.

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

(а,Ь) = ащ щт к(Ь-а)2

АхВ

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

РА фс

где

1 * I2

\12к

о

п

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

В § 5 факты, полученные в § 5 главы 1, распространяются на многомерный случай. Основным результатом данного параграфа является доказательство существования е- седловой точки при условии, что радиус максимального шара, принадлежащего и множеству А и множеству В, более чем в три раза превосходит корень из максимального по модулю собственного значения матрицы Б-Л, умноженного на т. Как и в главе 1, вероятность ошибки распознавания, в случае применения первым игроком • соответствующей стратегии, увеличивается до максимально возможного уровня, равного шт[р],р2].

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

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

3 приводится программа на языке Pascal, разработанная специально для вычисления таких интегралов.

В § 2 сравниваются вероятности ошибок распознавания билинейных и байесовских решающих правил для двумерного пространства признаков. Показывается, что максимальное отличие двух вероятностей не превышает 0.0998. Это значение достигается при совпадающих значениях математических ожиданий и корреляционных матрицах, совпадающих и равных произведению единичной матрицы на константу. Однако, при увеличении размерности пространства признаков эта оценка возрастает (например, при ш=10 максимальное отличие составляет 0.2837).

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

В § 4 показывается, что билинейное решающее правило всегда лучше линейного решающего правила.

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

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

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

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

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

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

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

Основные результаты работы опубликованы в следующих работах автора:

1. Морозов В.В., Белянкин Г.А., Бежуашвили Б.Т. Теоретико-игровой подход к задаче распознавания. // Вычислительная техника и вопросы кибернетики, вып.28, Математические модели дискретных систем. С-Пб., 1994. с.88-103.

2. Белянкин Г. А. Вычисление вероятности ошибки "распознавания для билинейного решающего правила. Вестник МГУ. Сер. 15 Вычислительная математика и кибернетика. № , С. 30-37.

3. Белянкин Г.А., Медведков И.А. Использование билинейного классификатора в статистических играх распознавания объектов.// Тезисы докладов Второго Сибирского Конгресса по Прикладной и Индустриальной Математике., 1996, С. 158.

4. Белянкин Г.А., Медведков И.А., Морозов В.В. Игровая постановка задачи статистического распознавания и ее решение для ряда классификационных правил.// Сборник трудов Первой Московской Конференции по Исследованию Операций, С.7-12.