Метод минимизации эмпирического риска в задачах восстановления регрессии и обучения распознаванию образов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

РГб од

2 1 '¡¡01№&ё&скт ОРДЕНА. ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. В.И. ЛЕНИНА

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

. ОЛЬШЕВСКАЯ ОЛЬГА ВИКТОРОВНА

УДК 519.23

МЕТОД МИНИМИЗАЦИИ ЭМПИРИЧЕСКОГО РИСКА В ЗАДАЧАХ ВОССТАНОВЛЕНИЯ РЕГРЕССИИ И ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ

01.01.05 - Теория вероятностей и математическая статистика

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

МИНСК, 1993

Работа выполнена в отделе стохастического анализа Института математики Академии наук Беларуси

Научный руководитель - доктор физико-математических наук, Б.А.Залесский

Официальные оппоненты :

- доктор физ.-мат. наук, профессор кафедры высшей математики Гомельского госугагеерситета

им. Ф.Скорыны Малинковский Ю.Б.

- кандидат физ.-мат. наук, доцент кафедры теории вероятностей и математической

статистики Белгосуниверситета им. В.И.Ленина Морозов В. А.

Ведущая организация - Московский государственный университет шени М.В.Ломоносова

Защита состоится чЛЗ" 1993 г. с /С *часов

на заседании специализированного Совета к 056.оз.17 при Белорусском государственном университете имени В.И.Лешна по адресу : 220050, г. Минск, пр. Скорины, 4, Белгосуниверситет, гл. корпус, ауд. 206.

С диссертацией можно ознакомиться в научной библиотеке Белгосунивербитета

Автореферат разослан -/У- 1993 г.

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

Ю.В.Меленец

\

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

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

Классическое направление в области восстановления функциональных зависимостей, основанное на методах параметрической статистики, связано с именами Р.Фишера, К.Пирсона, Г.Крамера, С.Уилкса, М.Квндалла, А.Стыоарта. В последнее время получил развитие подход, в основе которого лежит принцип минимизации эмпирического риска. Исследованиями в этом направлении занимались Л.Ле-Кам, В.Н.Вапник, А.Я.Червонёнкис [11], Деврой [12], Александер [13], Дадли* Уолд, Анселон и др..

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

Э

.минимизации риска.

А.И.Михальский, Ю.С.Завьялов, Б.И.Квасов, В.Л.Мирошниченко и другие исследовали эффективность применения полиномиальных сплайнов для восстановления регрессии. По сравнению с методами полиномиальной регрессии сплайн-аппроксимация регрессионной зависимости имеет преимущество в задачах прогнозирования, т.к. дает возмокность равномерного приближения функции регрессии.

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

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

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

Апробация работы. Результаты диссертации докладывались на республиканских научных конференциях " Математическое и программное обеспечение анализа данных"(г.Минск, 1990г.) и "Проблемы внедрения новых информационных технологий в АПК "(г.Минск,

1991 г.); на международной школе " Предельные теоремы и непараметрическая статистика " (г.Бвлефальд, 1992г.); на республиканской научной школе-семинаре "Компьютерный анализ, данных и моде- . лирование " (г.Минск, 1992г.); на городском научном семинаре " Математическое и программное обеспечение анализа данных организованном кафедрой математического моделирования и анализа данных Белгосуниверситета; на научных семинарах лаборатории статистических методов Института математики АН Беларуси.

Публикации. Основные результаты диссертации опубликованы в ю работах, список которых приведен в конце рефе^ ата [ 1-ю ].

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

СОДЕРЖАНИЕ РАБОТЫ '

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

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

Принцип минимизации эмпирического риска состоит в минимизации вместо теоретического риска

I(a) = J (y-Fte.cO^ícbc.dy),

o

где (y-F(x.a)) - функция потерь, зависящая от переменной у,

векторной переменной х=(х1.....xk)£Rk, параметра сел (функция

Р(х,а) принадлежит параметрическому множеству функциональных '

зависимостей), эмпирического риска

п

v<a> = н ¿(yr?(xd'a,)2'

построенного по выборке х1 .у.,;... ;хп,уп . Функция Р(х,аэ), ми-нимизирущая г (а), близка к функции F(x,a0), минимизирующей ' l(a), при условии существования равномерной сходимости эмпирического риска к теоретическому, т.е.когда для любой заданной величины уклонения ае может быть указано неравенство

Р { sup | i(a)-v(a) ) > зг } < т) . a

В § 1.1. построена оценка скорости равномерной сходимости

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

распознаванию образов в случае конечного числа решающих правил.

Теорема 1.1. Пусть g.,у., í=i,...n - обучающая последовательность длины а, множество решающих правил конечно и состоит

из N правил : F (х,at),...,

тогда

P{sup '|1«х.М»(а.)| > ае } <

i

< 2N шах í(k'l),p(l))(p(I)) '(l-pd))

1<1<т*-ш

n-k(l)Г П I [k(l)j'

о

где то = [аеп] (здесь [аеп] - целая часть аеп) при дробном sen и

(1-р) (к+1)

т =аеп-1 при целом аеп, Х(к,р) -- > Jc(Z) = т + г,

1 —р—пр+Зс

Ш/, 1 Р<г> = й +п--*-

В таблице 1 приведены значения процентных точек ае для :

- построенной в Теореме 1.1 оценки (обозначено ае0),

- для аир р { |Р(а)-у(а)| > ж > (обозначено х ),

р

- для оценки В.Н.Вапника и А.Я.Червоненкиса 111] (ае^) при N=1. Например, при п=40 для т)=0.05 аер=о.1б7, 3^=0.215, эео=0.1б9;

при п=200 для 17=0.025 эгр=0.082, ае, =о.Ю5, ае0=о.083. Таблица 1

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

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

п

Р(£-)=1}=Р{?;)= -1}=о.5,;)=1,...,п, Зп= У

Определим систему событий 3(а)={ х,у: (у-Р(х,а))2 = 1 }.

Теорема 2.1 На случайной независимой выборке п пар х1,у1;...;^1,уп справедлива оценка скорости равномерной сходимости частот к вероятностям по классу событий Б(а) для к=[ ^ ] * ЗД0СЬ Целая часть а ), при к,п одновременно обоих четных либо нечетных

РС аир |1(а)-г(а) |>эе } < 6 р{ ,>к+1 >,

а£Д К-

при к,п одном четном другом нечетном

р{ аир |i(a)-v«x)|>ae } < 6 р{ 5„ >к+1 }. аед к. п

В таблице 2 приведены значения процентных точек х для :

- построенной в Теореме 2.1 оценки (обозначено зг„т),

- для оценки В.Н.Валника и А.Я.Червоненкиса [11] ( ае^ ) . Показано, что в наиболее употребимом диапазоне 0.1 < tj < 0.25 построенная оценка позволяет более точно оценивать доверительный интервал для качества решающего правила, минимизирующего эмпирический риск.

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

Р(х,а)=1 с k v

{¿WW0 }

а=(а1,...,а1с+1)е.Л б Rk+1,x=(x1t...,xk) е Rk , Теорема 3.1 Предположим, что случайные величины X имеют плотность по лебеговой мере i<x)<L, пусть носитель г(х) принадлежит кубу к со стороной длины м. Класс решающих правил ?(х,а), а£Л состоит из индикаторов всех линейных полупространств, как описаго выше. Тогда

(1) Р { аир | I(a)-v(a) | > эе ) < 2С., (к^ехр^гге2)!},

а 1

(2) Р { sup (Ца)-v(а) ) <~з> } < с. (k)nkekp{-2a?n), . а '

к 2

(3) Р { sup ( l(a)-v(a) ) > ае } < c2(k)n ехр{-2ае n},

к-1

где 0, (к)= 2 ^ кк2 | (М+1 кг/2_31с/2Ь1с(4+вхр{4))квхр{к},

к-1

С2(к)= 2 ^ кк2 | (М+1 )к2к кг/г_3к/2Ьк5к9хр{к},

здесь ^ т | 1 биномиальные коэффициенты.

Построенная оценка, как и оценка Деврой [ 12,13 ] имеет оптимальный порядок экспоненты, но лучшую ассимптотику при п чоо .

3 } 1.4. построена оценка скорости равномерной сходимости средних к их математическим ожиданиям в задаче восстановления . регрессии по значениям неслучайных предикторных переменных в I ассе линейных по параметрам функций. Определим регрессию в классе линейных по параметрам функций как

У1=Р(*1,а)+е^ 1=1,...,и, где Р(х,а), сел. - класс линейных по параметрам функций

К+1

р(*,а)= £ = (а,ф(*)), а=(а,.....«к+ч)©*1"'1,

ф(х)=(<р., <х).....<рк+1 (х))©1к+1, «р^^ (х)^,«©^1. Модель строится в

предположении ,. что в<е)=о и все е. независимы и имеют

одинаковую дисперсию. Пусть .....хпб ^-неслучайные

переменные, в этом случае функционал х(а) сводится к

1 П 2 а(а)=п-1 ^е(у^-р(х.. ,а))

п

Эмпириче ский функционал 3 (а) =п~1 ^ (У^-Р (х^, а)).

Пусть и а < < ь, I = 1,...,п. Это вполне естественные ограничения на область определения у2, т.к. область определения значений отклика имеет определенный физический

смысл и значения верхней и нижней границ области изменения

отклика можно установить из физических соображений, анализа

данных. Обозначим г=зир|а|, г < » .здесь |.|- обычная евклидова а

норма в и114"1 .порожденная скалярным произведением. Определим

независимые случайные величины'

^.....3'=1.....п'

где е^у^-ЕСу^) - независимые скалярные случайные величины, определяющие ошибку наблюдения у. Очевидно, что Ег^=0, ■ ;}=1,...,п. Пусть "П^^-Еб^. легко видеть, что Ег]^=0, ¿=1,...,п. Обозначим

п п

Е82=02,^Е|а;{|2 = о2 Х^ф^Я2 = Р2.

Теорема 4.1 Пусть для некоторых 1£, справедливы неравенства

Е|8|И < ~ О2!*"2 И - < Ь*"2 , ш=2,3...,

2 |Ф<^)!2

ь = ье1ф , тогда

¿=1

Р { вир I «г (а)-.г (а) | > зе } < |а|<г

I. I п(Ь-а) J I (-2р2+ (пзе-з0)Ь ->^2 .1]

где

Г Г 2 те2 1 Г (пае-«) Ц

в = Аг@п1п ехр ]--— У + 2 ехр ■{--И .

0<*<п2е|. I п(Ь-а) ) I (пзе-^)Ь ^4г2 )\

Для этой ке задачи в случае, когда ошибки наблюдений явля-

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

'В § 1.5. построена оценка скорости равномерной сходимости средних к их математическим ожиданиям в задаче восстановления регрессии в классе линейных по параметрам функций. Пусть

k+1

F(x,a)= J = (a.x), «Ma,.....Oic+i)®1^1,

j—1

*. • • )ERk » и x - .случайные переменные .Теоретический риск равен 1(a).

Теорема 5.1 Пусть случайные величины |Y| < м, |х| < R, параметр |а| < г. Тогда

(1) р { svp | i(a)-J(a) | > х ) < гСоСк.г.Юп^ехр^гэ^пЛм+гН)4},

|a|<r

(2) Р { sup l(a)-J(a) > зе } < Coik.r.RJn^expi^a^n/di+rR)4},

|a|<r ' 3

где C3(k,r,R)=25kek(rR)klc_k/2(lI+rR)""3k.

Построенная оценка имеет лучший показатель экспоненты, чем полученная при условии равномерной ограниченности потерь оценка В.Н.Вапника и А.Я.Червоненкиса, и ту же ассимптотику при п .

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

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

В { 2.1 разработан алгоритм построения многомерной кусочно-непрерывной ломаной поверхности регрессии.

Обозначим к-мерный параллелепипед о = (а,,4, Ыа^.а^Зе и1*, пусть хЕО, Предположим, что задано разбиение

. Р

параллелепипеда э р- параллелепипедами Б = и о.,, п п. = о,

1 3 31 '32

Параллелешшеды ,в свою очередь, образованы разбиением каадого интервала (а^,^], ¿=1,...,к на т^ частей

Каждой вершине построенных параллелепипедов сопоставим мультииндекс ¿(к). = полагая 1=1.....к,

Пусть у^

ук

, 1=1,...,р-1,

образована векторами-строками у1, (=1,...,к, координат вершин

общей грани, 1к=[1.....1]т, У^1 =[0]- нулевая кхк матрица.

Занумеруем параллелепипеда определенным образом. В кавдом методе указывается свой способ нумерации параллелепипедов.

Пусть п наблюдений *1,... упорядочены по параллелепипе-

дам так, что первые ¿1 наблюдений лежат в параллелепипеде , •

следующие 17- в Ь? и т.д., поспедние I наблюдений лежат в пара-

Р

ллелепипеде ор, причем ^ I. = п .

Теорема 1.1 к-мерная ломаная кусочно-непрерывная поверхность представима в виде

ве = 29 •

где п х (к+р) матрица г имеет следу щи вид: векторы-строки

Ч"1х*и1 .....V(>1к»*а1),

.... )1 к.«^). 1 ■-<▼!!-, 1 ) -о.....о].

1-1 I

I М I «V • 1=2.....» •

У=1 у=1

В 5 2.2 разработан алгоритм построения многомерной непрерывной ломаной поверхности регрессии. Пусть (к))-вершина параллелепипеда с мультииндексом 3(к),1^(0,...,0,1,о,..,о).

Пусть далее (к)=(1,...,1 ,...,1), 1 < а,< т. , 1= 1.....к.

1 1—1 ■ .1 1

Пусть наблюдения независимых переменных в регрессионной

матрице х упорядочены по принадлежности к параллелепипедам 9

возрастающими номерами: перше п., наблюдений принадлежат 1-му

параллелепипеду, наблюдения с номерами ц: п._4+1< ц < п.

принадлежат параллелепипеду о номером » и т. д. до последних

наблюдений от, п до пр=п, принадлежащих р-му параллелепипеду.

Теорема 2.1 к-мерная непрерывная ломаная.поверхность

представима в виде

е9 =: 26 ,

где вд^вОс,),...,в^)]1,*^ 1 < I < п наблюдения к-мерной предикторной переменной.

к

Z « ( V + W ) - nxg- матрица , где g=k+l+^ (т,-1)

1=1

Для 1=1,...,п. 5=1.....к, vij=xij , т. е.

V . . .V

nt пк

Для строк с номерами п^+1 < I < п^, где г>- номер параллелепипеда с мультииндексом опорной вершины ¿(к), элементы к+1- го столбца имеют ввд

4d

d=l

ТГГГТ •

При r=2,...,3d-i,wifl ^=3.....Юн,4=1.....к

d-t

xdtrd(k)) - r,lr,(k)-1J

i,k+ Y(m.-1 )+r

. где r (k)=jJ (k)-ml ,

dv d4

id

d-1

i,k+

|(m -1)+j

xd(jd(k)-i„) • остальные vij=o.

При ¿.>1

d-l

- Wi.k+1= -I '1 +1»

i,k+ 7(m -1 )+j j-« 1

остальные

Vi = 0 ' t '

означает суммирование по d: j >1.

d=l

s

В 5 2.3 дано очень краткое описание комплекса программ regro, ' реализующего два метода построс:шя многомерных лсманых поверхностей регрессии.

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

1. Залесский Б.А., Ольшевская О.В. Построение многомерной кусочно-непрерывной ломаной регрессии // Весц1 АН БССР.Сер.физ.-мат. навук.-1988. . -С. 3-8.

2. Залесский Б.А., Ольшевская О.В. Построение многомерной непрерывной ломаной регрессии // Весщ АН БССР.Сер.физ.- мат. навук. -1990.-№4.-С. 10-15.

3. Программное обеспечение ЭЗМ /АН БССР. Ин-т математики. Мн. ,1990. Вып. 88: Комплекс программ REGRO построешя многомерных кусочно-непрерывной и непрерывной ломаных поверхностей регрессии // Залесский Б.А., Исакова Г.А., Ольшевская 0.B..56C.

4. Залесский Б.А.,Исакова Г.А., Ольшевская О.В. Комплекс программ regro построения многомерных кусочно-непрерывной и непрерывной ломаных поверхностей регрессии // Тез. докл. республ. научн. конф." Математическое и программное обеспечение анализа данных".- Минск. 1990,- с.138.

5. Залесский Б.А.,Исакова Г.А., Ольшевская О.В. Построение многомерной регрессии средствами комплекса программ regro//Проблемы компьютерного анализа данных и моделирования: Сб. науч.ст./ Цод ред. Ю.С.Харина.- МН.:БГУ им.В.И.Ленша. 1991.-с.56-60.

6. Залесский Б.А., Ольшевская О.В. Многомерная непрерывная ломаная регрессия // Тез. докл республ. научн. конф. " Проблемы внедрения новых информационных технологий в АПК ".Минск. 1991.-С.30-32.

7. O.V. Olshevska, B.A.Zalesskii Estimations of Minimum оf Quadratic RiBk for Pattern Recognition And Regression Problems // Bielefeld University. 1993.- p.11.

8. Залесский Б.А., Ольшевская О.В. Оценка скорости равномерной сходности частот появления событий к их вероятностям в задаче обучения распознавании образов // Тез. докл республ. научн. школы-сешшера "Компьютерный анализ данных и моделирование ".-Минск, дек. 1992.-с.40.

9. Олыаевская О.В. Метод минимизации эмпирического

риска в задаче обучения распознаванию образов / Ин-т Математики АН Беларуси,- Мн. 1993.-» 5(496).- 12 с.

ю. Ольшевская О.В. Восстановление регрессии по значениям неслучайных предикторлых переменных в классе линейных по параметрам функций методом минимизации эмпирического риска / Ин-т .Математики АН Беларуси,- Мн. 1993.-№ 7(498).- 21 с.

11. Вапних В.Н. Восстановление зависимостей по ампири* )с-ким данным.- М.: Наука. 1979.

12. Devroye L. Bounds for.the uniform deviation of empirical measures// J.liultivariate Anal.1982.- »12.-p.72-79.

13. Kenneth S. Alexander. Probability inequalities for empirical processes and a law of the iterated logarithm // The Annals of Probability. 1984.- Vol.12, No.4.-1041-1067.