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

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

Ткачев Юрий Игоревич

МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТИ КОЛЛЕКТИВАМИ РАСПОЗНАЮЩИХ

АЛГОРИТМОВ

Специальность 05.13.17 — Теоретические основы информатики

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

1 б СЕН 2013

Москва - 2013

005533657

Работа выполнена в Федеральном государственном бюджетном учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук.

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

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

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

Шибзухов Заур Мухадинович, ведущий научный сотрудник Научно-аналитического управления, Всероссийский центр мониторинга и прогнозирования чрезвычайных ситуаций природного и природно-техногенного характера, Министерство по делам гражданской обороны и чрезвычайных ситуаций РФ. кандидат физико-математических наук Челноков Федор Борисович,

старший технический менеджер, Московский филиал Корпорации Алаин Текноложди Ресерч энд Девелопмент, Инк. (США).

Ведущая организация: Федеральное государственное образовательное

учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)». Защита состоится «. гн .» р. (Гэп 1Я г. на заседании диссертационного

совета Д 002.017.02 при Федеральном государственном бюджетном учреждение науки Вычислительный центр им. А.А.Дородницына Российской академии наук по адресу: 119333, г. Москва, ул. Вавилова, д. 40. С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан «_Ll_» CiA^p 2013 г.

Ученый секретарь диссертационного совета //V/v J?

Д 002.017.02, д.ф.-м.н., профессор В.В.Рязанов

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

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

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

В то же время, случай дискретной величины (стандартная задача распознавания) в настоящее время достаточно хорошо изучен. Более 20 лет тому назад Ю.И.Журавлевым было отмечено, что задача распознавания может рассматриваться как задача интерполяции специальных функций, когда независимые переменные (значения признаков) могут быть фактически произвольны, а зависимая величина принимает конечное число значений. В настоящее время существуют различные модели и конкретные алгоритмы для решения задач распознавания, для которых исследованы свойства корректности и устойчивости (алгебраический подход, логические корректоры и др.).

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

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

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

Основные положения, выносимые на защиту.

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

2. Модели восстановления зависимостей «байесовский корректор» и «линейный корректор».

3. Доказательства свойств корректности и устойчивости моделей восстановления зависимостей «байесовский корректор» и «линейный корректор».

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

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

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

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

Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений.

Апробация работы. Основные результаты работы докладывались на следующих научных конференциях:

• 14-я всероссийская конференция «Математические методы распознавания образов» (Суздаль, 2009 год);

• 2-я международная конференция «Классификация, прогнозирование, анализ данных» СРБМ-2010 (Варна, Болгария, 2010 год);

• 10-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ-10-2010» (Санкт-Петербург, 2010 год).

Публикации. Материалы диссертации опубликованы в 4 научных статьях [1-4], из них 2 работы [2,3] — в журналах, включенных в Перечень ведущих рецензируемых научных журналов и изданий.

Структура и объем диссертации. Работа состоит из оглавления, введения, трех глав, заключения и списка литературы. Содержание работы изложено на 47 страницах. Список литературы включает 49 наименований. Текст работы иллюстрируется 1 таблицей.

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

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

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

3

специальных задач распознавания, построенных на исходной обучающей выборке. Рассматриваются модели восстановления зависимостей по выборкам прецедентов «байесовский корректор» и «линейный корректор». Исследуются свойства корректности (модель не делает ошибок на обучающей выборке) и квазикорректности относительно разбиения области значений целевого признака (суммарная ошибка модели на обучающей выборке не превосходит заданной величины) рассматриваемых моделей.

Имеется выборка {(Si, Ui)}^, х = (х\~ описание объекта, Xj 6 Mj, j = 1,... Mj — множество произвольной природы; у £ R — значение целевого признака, Йс1. Обозначим т! — число различных значений целевого признака в обучающей выборке, т! = j {J/i}J=11 •

Рассмотрим разбиение области значений целевого признака Д = {Ai,...,A„} на интервалы Дг = (d0, di],..., Дп = (dn-i,d„]. Без ограничения общности считаем, что объекты обучающей выборки упорядочены по возрастанию значения целевого признака, тогда 2/1, ■■■,Ут1 е Дъг/mi+l, ■■■,Ут2 € Л2, . . .,утп_1+1, ■ ■ ■ , Утп 6 Дп-

Возьмем число L, 2 ^ L ^ п, и определим N разбиений отрезка R на L интервалов, поставив каждому разбиению в соответствие вектор с целочисленными компонентами к, = (0, ..., k\L l\n),i = 1, ...,7V, < < п. Каждое разбиение отрезка R определяет разбиение

множества М = Mi х • • ■ х М^ на L непересекающихся подмножеств

L

К{,..., К\ (классов): М = (J К\, и ф /л => Klv П Кг = 0 согласно правилу:

t=1

объект х принадлежит классу Щ разбиения Кг = {К\,..., KlL} тогда и только тогда, когда у = f(x) £ Д^ и 6 (kij, fcij+i]- Каждое разбиение Кг определяет стандартную задачу распознавания Z, с L классами. Пусть Ai — некоторый алгоритм решения задачи распознавания Zi, относящий произвольный объект х к одному из классов Кга., щ = 1,..., L.

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

1. формирование разбиений вещественной оси на интервалы А^г?

2. формирование обучающих выборок задач распознавания выбор классификаторов А;, их обучение;

3. вычисление значения зависимой величины на основе коллективного решения классификаторов.

В разделе 1.1 рассматривается задача формирования разбиения вещественной оси на фиксированное число интервалов п, приводится алгоритм решения данной задачи методом динамического программирования.

Для формирования разбиения вещественной оси на интервалы А к требуется определить номера граничных объектов гпк" утк_х < уг ^ утк. Обозначим Ск = —--выборочное среднее для интервала Дь к = 1,.... п.

В задаче динамического программирования используется функционал

п ТПк

<5(А) = ^ ^ (Уг~ск)2, оптимизация проводится по номерам граничных

к=1 г=7Пк_1+1

объектов ТПк, к = 1,..., п.

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

В разделе 1.2 рассматривается модель восстановления зависимости «байесовский корректор», исследуются свойства модели: корректность и квазикорректность относительно разбиения области значений целевого признака.

Считаем декартово произведение К1 X • • • х х Д множеством элементарных событий, событие {К\ ,..., К^ , означает: «объект х отнесен алгоритмом А{ в класс 01,..., алгоритмом Лдг в класс а .у, у = /(¿с) 6 Д&». Вероятность такого события обозначается как Р(К^ ,..., , или Р(х, Д&).

По формуле Байеса имеем РСЛ, I К1 KN 1 - '- - -' K°n'Afc) _.

, л..........р(К,...,к«,) ~

= р(*'......<|д*> (1>

Пусть классификаторы статистически независимы, тогда Р..., |Д0 = П P(^,|Afc), P«,..., Kl) = П Р(^), и формулу

i=1 г=1

Байеса можно записать в виде:

Р(Ак\х) = Р(Д*К\,..., О = NP{Ak) П (2)

П Р(Ч)i=1

г=1

Определение 1 Байесовским корректором называется функция F:

(РСД^-.-ЛАп!*)) -»•

Определение 2 «Ответом по среднему» байесовского корректора для объ-

п

екта х называется величина у = ^

k=1

Определение 3 «• Ответом по максимуму» байесовского корректора для

объекта х называется величина у = ск, где к = argmaxР(Д^|ж).

i=i

Алгоритм восстановления зависимости

1. формирование разбиений вещественной оси на интервалы Ак, к = 1,..., п;

2. задание разбиений К1, г = 1,..., N, формирование обучающих выборок задач распознавания Zi, i = 1 выбор классификаторов Ai, г = 1,... ,N, их обучение;

3. вычисление оценок вероятностей Р(Щ\Ак), Р(Д^), Р(Щ), г = 1 ,...,N, j = 1,...,L, к= l,...,n.

Алгоритм вычисления значения зависимой величины

1. классификация алгоритмами Ai,..., Ду объекта х-

2. вычисление значений условных вероятностей Р(Д&|:г), к = 1,...,п по формулам (2);

3. вычисление «ответа по среднему» у или «ответа по максимуму» у.

Для вычисления параметров модели восстановления зависимостей ставится следующая оптимизационная задача:

т

F = Y,(Vi- Vi)2 -> . min

при ограничениях:

L j=i

n

Y p(Afc) = 1. Р(Д*) > о, fc = 1,..., n;

fc=l

n

Y P(Afc) P(Äj|Afc) = P(Äj), P(ÄilAfc) o, i = 1,..., N,j = 1,..., L.

k=\

Аналитическим решением данной задачи при L — 2, N = п — 1 и фиксированных значениях вероятностях интервалов P(Afc) = ctk являются величины:

0, г < к,

Р(К\\Ак) = 1, % = к,

, , г > к; Р(Щ\Ак) = 1 - P(^|Afc); (3)

p(*i) =, Л-1 ; 1 - at

Р(Щ) = 1 - Р(Ki);

i = 1,..., п; к = 1,..., п.

Определение 4 Модель обладает свойством (*), если для объекта Х{, г =

1,..., т, обучающей выборки Р(Д&|:Гг) ^ 0 г/j Е Дь

7

"Утверждение 1.1 Байесовский корректор с оценками вероятностей (3) обладает свойством (*).

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

(1, г ^ к,

О, г < к

{1, г < к,

,г = 1,...,п-1,к=1,...,п.

О, г > к

Частотные оценки вероятностей классов =

Е Р(Я?|Д*) Р(Д*) = ¿а*; Р(Щ) = ±Р(К*\Ак)Р(Ак) = £ ак,

к=1 к=1 к=1 к=г+1

г = 1,... ,п — 1.

Утверждение 1.2 Байесовский корректор с частотными оценками вероятностей и «ответом по среднему» или «гответом по максимуму» обладает свойством (*).

При практическом построении Р(Щ\Ак) возникают ситуации, когда классификаторы относят объект х к классам так, что Р(Щ\Ак) = О, к = 1 ,...,п. Рассматривается подход, позволяющий бороться с такими ситуациями.

Рассмотрим линейную комбинацию оценок вероятностей

тт{й,п—к]

Р{К)\Ак) =- тЬ{;п_,}-,г = = 1,... ,Ь, к = 1,...,п

Е щ

г=тах{—(1,1—к}

Р(К}) = Е к=1

Величины Р{Щ\Ак) формально являются вероятностями. Назовем величину <1 шириной окна сглаживания, величины и>_,г,... л — весами сглаживания. Процесс замены Р(Щ\Ак) —> Р(Щ\Ак) назовем сглаживанием.

На веса сглаживания накладываются ограничения:

• неотрицательность: г^ ^ 0, £ = —(I,... ,(Ц

• симметричность: ги{ = £ = 1,... ,с1;

• характер убывания: и>г = и > 1, £ = —с/,...

Определение 5 Модель обладает, свойством (**), если для объекта Х{,г — 1,... ,т обучающей выборки: Уг € Ак =Ф- > РСА^¡а?,), к ф к\.

"Утверждение 1.3 Байесовский корректор со сглаженными частотными оценками вероятностей и «ответом по максимуму» обладает, свойством (**).

Определение 6 Модель восстановления зависимости называется квазикорректной относительно разбиения А, если для обучающей выборки {(Уг, ХгвЫПОЛНвНО Уг £ Дд. =4> & € Д^, I = 1, . . . , ТО.

Определение 7 Модель восстановления зависимости называется корректной, если для обучающей выборки {(у^^г)}*! 1 выполнено Уг = Уиг = 1,...,ш.

Определение 8 Моделью называется байесовский корректор над корректными классификаторами с аналитическими оценками вероятностей при использовании <?ответа по среднему».

Определение 9 Моделью Аг называется байесовский корректор над корректными классификаторами с частотными оценками вероятностей при использовании «ответа по максимуму».

Определение 10 Моделью А!; называется байесовский корректор над корректными классификаторами со сглаженными частотными оценками вероятностей и шириной окна сглаживания с1 при использовании «ответа по максимуму».

Теорема 1.1 Модели Ах, А2 и А2 при непротиворечивой обучающей информации являются квазикорректными относительно разбиения Д.

9

Теорема 1.2 Модели Ai,A2 и Af при непротиворечивой обучающей информации и разбиении А : п = т! области значений целевого признака являются корректными.

Для обучения корректной модели восстановления зависимости с разбиением области значений целевого признака на то' интервалов необходимо обучить то' — 1 классификаторов, т.е. число классификаторов сравнимо с количеством объектов обучающей выборки. Рассмотрим свойства байесовского корректора для разбиения А : [ А| = п,п < то'.

771

Погрешность модели восстановления зависимости есть ^ \ fji — с/-. |2,

i=1

г/i € Дki, г = 1,... ,то. Данное выражение совпадает с погрешностью разбиения Q(А), т.е. для построения модели с заданной погрешностью 6 необходимо построить разбиение с погрешностью S.

Утверждение 1.4 Алгоритмическая сложность построения разбиения для байесовского корректора, дающего суммарную ошибку Q(А) < S, равна 0(т3 log то).

В разделе 1.3 рассматривается модель восстановления зависимости «линейный корректор», исследуются свойства модели: корректность и квазикорректность относительно разбиения области значений целевого признака.

Обозначим и^ = *, i = 1,..., N, j = 1,..., L.

Составим вектор ответов й(х) = (1, щ(х),..., и^(х)), щ(х) = uf\ если классификатор А{ отнес объект х в класс Щ.

Определение 11 Линейным корректором называется функция / : X —> М, f(x) = (u(x),w), w - вектор весов, w G М^"1"1.

Вектор весов есть решение оптимизационной задачи

771

Е(2Л - /Ш)2 -»• min. ¿=i у

Алгоритм восстановления зависимости

1. формирование разбиений вещественной оси на интервалы Дд., к = 1,...,п;

2. задание разбиений К\ г = 1,..., Ы, формирование обучающих выборок задач распознавания г = 1,..., /V, выбор классификаторов Л,, г = 1,..., И, их обучение;

3. вычисление вектора весов Ни.

Алгоритм вычисления значения зависимой величины

1. классификация алгоритмами ..., Д\г объекта х;

2. вычисление вектора ответов й(х);

3. вычисление значения /(х).

Теорема 1.3 Линейный корректор при п = т! является корректной моделью.

Утверждение 1.5 Для случая Ь — 2, N — п — 1 и п = т' вектор весов

имеет вид: гик = %7Ук~п), к = 2,..., п, Юх = ух - ¿ иРь)к.

ик~Ч к=2

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

т

Погрешность модели восстановления зависимости есть \Уг ~

¿=1

У{ £ Д/с,, г = 1,..., т. Данное выражение совпадает с погрешностью разбиения А), т.е. для построения модели с заданной погрешностью 6 необходимо построить разбиение с погрешностью 6.

Теорема 1.4 Линейный корректор при п < т' является квазикорректной относительно разбиения А моделью.

Во второй главе рассматривается свойство устойчивости моделей

«байесовский корректор» и «линейный корректор». Устойчивость является

аналогом регулярности по Журавлеву для распознающих алгоритмов.

11

Под моделью А будем понимать байесовский или линейный корректор с корректными классификаторами.

Введем обозначение А(Ит) = у = (уи ■ ■ ■, ут)Т■

Рассмотрим пространство задач с метрикой Обозначим

= {%'т\Рх{%пи < 5} — ¿-окрестность задачи Введем метрику на пространстве алгоритмов рл(А^т), А{Е'т)) = ||у — у'\\.

Определение 12 Модель восстановления зависимости А устойчива, если Уе >0,35 = 5{е) : Чг'т € 26(гт) рА(А{гт), А(г'т)) < е.

В разделе 2.1 рассматривается свойство устойчивости моделей относительно изменения описаний объектов.

Рассмотрим задачу с изменением описаний объектов Я'т = {(¿*г', Уг)У{=1- Разбиение области значений целевого признака А' задачи Z'm для модели А совпадает с разбиением А, т.к. значения целевого признака у одинаковы для задач Zm и Z'm. При этом оценки значений целевого признака для задач Zm и совпадают, у = у'.

Рассмотрим пространство задач с метрикой рх^т,/^) =

I171 / \ — 112 -у ¿=1

Обозначим my(Z) - число различных значений целевого признака задачи Z. Обозначим А*(И) - модель для задачи Z с разбиением А : ||Д|| = туНапомним, что модель А*^т) корректна, у = у. Также корректна модель А*{г'т), {/ =

Теорема 2.5 Модель А* устойчива относительно изменения описаний объектов.

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

Рассмотрим задачу с изменением значений целевого признака объектов Z'm = у[)}?=1. Рассмотрим пространство задач с

метрикой ру^т^'п,) = \\у — ¡?1\. ¿-окрестность задачи Zm есть

2ц{гт) = {г'т\рг{гт,г'т)<5}.

Теорема 2.6 Модель А* устойчива относительно изменения значений целевого признака объектов.

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

Рассмотрим задачу с изменением описаний и значений целевого признака объектов Z'm = {{х/, У;')К=1- Рассмотрим пространство задач с метри-I т

кой Рхг^т, г'т) = ЛХ) (шх||£г - ¿¿'||2 + гиу(у{ - у-)2). гДе > о.

Теорема 2.7 Модель А* устойчива относительно изменения описаний и значений целевого признака объектов.

Модель А с разбиением Д : ||Д|| < не обладает свойством

устойчивости.

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

В качестве классификаторов в моделях «байесовский корректор» и «линейный корректор» использовался алгоритм голосования по системам логических закономерностей классов.

Описание задач:

1. «медицинская задача» — описание объекта состоит из 30 бинарных и количественных признаков: медицинские показатели состояния пациента, зависимая величина — частота кризов артериальной гипертензии; множество объектов разбито на непересекающиеся обучающую (263 объекта) и контрольную (66 объектов) выборки;

2. «стоимость домов» — описание объекта состоит из 13 бинарных и количественных признаков: характеристики дома и района, в котором он расположен, зависимая величина — стоимость дома; множество объектов разбито на непересекающиеся обучающую (253 объекта) и контрольную (253 объекта) выборки;

3. «прочность бетона» — описание объекта состоит из 8 количественных признаков: массовые доли компонент и возраст бетона, зависимая величина — прочность бетона; множество объектов разбито на непересекающиеся обучающую (772 объекта) и контрольную (257 объектов) выборки.

Для сравнения моделей использовалась среднеквадратичная ошибка

тп

МБЕ ~ ~ У г)2 Для нормированных значений целевого признака.

¿=1

Задача Байес.корр. Лин. корр. Линейная регрессия Ядерное сглаживание

Мед. задача 0.00417 0.0021 0.02011 0.00701

Стоимость домов 0.00229 0.00111 0.01034 0.00679

Прочность бетона 0.01551 0.01127 0.02117 0.01745

Модели «байесовский корректор» и «линейный корректор» дали меньшую среднеквадратичную ошибку на всех рассмотренных задачах.

В заключении сформулированы основные результаты диссертационной работы.

Основные результаты:

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

2. Разработаны модели восстановления зависимостей «байесовский корректор» и «линейный корректор».

3. Доказаны свойства корректности и устойчивости моделей восстановления зависимостей «байесовский корректор» и «линейный корректор».

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

Список публикаций

[1] Рязанов В. В., Ткачев Ю.И. Решение задачи восстановления зависимости коллективами распознающих алгоритмов // Доклады 14-й Всероссийской

14

конференции «Математические методы распознавания образов» ММРО-

2009. - М.: МАКС Пресс, 2009. - С. 172-175.

[2] Рязанов В. В., Ткачев Ю.И. Решение задачи восстановления зависимости коллективами распознающих алгоритмов // Доклады Академии наук.

2010. Т. 432. № 6. С. 750-754.

[3] Рязанов В.В., Ткачев Ю.И. Восстановление зависимости на основе байесовской коррекции коллектива распознающих алгоритмов // ЖВМиМФ. 2010. Т. 50, № 9. С. 1687-1696.

[4] V.V. Ryazanov, Ju.I. Tkachev. Restoring of Dependences of Samples of Precedents with Usage of Models of Recognition // New Trends in Classification and Data Mining, ISBN 978-954-16-0042-9, ITHEA, Sofia, Bulgaria, 2010, pp.17-24.

Заказ № 42-Р/09/2013 Подписано в печать 11.09.13 Тираж 100 экз. Усл. п.л. 0,8

ООО "Цифровичок", тел. (495) 797-75-76 www.cfr.ru; е-таП: info@cfr.ru

Федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук

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

Ткачев Юрий Игоревич

Методы решения задачи восстановления зависимости коллективами распознающих алгоритмов

Специальность 05.13.17 — «Теоретические основы информатики»

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

Научный руководитель: д.ф.-м.н., проф. Рязанов В.В.

Москва - 2013

Оглавление

Введение......................................................................3

Глава 1. Модели восстановления зависимостей............................13

1.1 Разбиение области значений целевого признака................14

1.2 Байесовский корректор............................................15

1.2.1 Общая схема построения модели..........................15

1.2.2 Вычисление оценок вероятностей........................18

1.2.3 Сглаживание оценок вероятностей........................22

1.2.4 Корректность модели......................................28

1.2.5 Свойства модели при снижении числа интервалов разбиения ........................................................29

1.3 Линейный корректор..............................................31

1.3.1 Общая схема построения модели..........................31

1.3.2 Корректность модели......................................32

1.3.3 Вычисление вектора весов................................32

1.3.4 Свойства модели при снижении числа интервалов разбиения ........................................................33

Глава 2. Устойчивость моделей..............................................36

2.1 Изменение описаний объектов....................................36

2.2 Изменение значений целевого признака..........................37

2.3 Изменение описаний и значений целевого признака объектов 37 Глава 3. Практическое сравнение моделей ................................40

3.1 Модельные задачи..................................................40

3.2 Реальные задачи....................................................41

3.3 Результаты..........................................................43

Заключение....................................................................44

Литература....................................................................45

Введение

Рассматривается стандартная задача восстановления зависимостей между вектором независимых переменных х — ..., х^), х^ G Mj,

где Mj — множество произвольной природы, и скалярной величиной у G R по выборке прецедентов {(yi, предполагая существование между ни-

ми функциональной связи у = f{x). Вектор х является признаковым описанием некоторого объекта, ситуации, явления или процесса, а величина у — значение некоторой скалярной характеристики х. Данная задача в статистической постановке известна как задача восстановления регрессии — функции условного математического ожидания, при этом предполагается существование условной плотности р(у\х).

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

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

Линейная регрессия.

d

Зависимая переменная восстанавливается [б] в виде у = Wq+ wjxj• Пара-

з=1

m

метры модели есть решение оптимизационной задачи ^2(yi—yi)2 min. Ре-

¿=1

шение может быть представлено в виде w = (ХтХ)~1Хту, где X G Wnxd — матрица, в которой i -я строка является описанием объекта щ. В случае слабой обусловленности матрицы ХТХ используются методы регуляризации: гребневая регрессия [6,19], для которой вектор параметров модели ищется в виде w = (ХТХ + т1)~1Хту, где т — параметр регуляризации, I G M.dxd — единичная матрица; метод LASSO [39,44,49], в котором вектор параметров

модели есть решение оптимизационной задачи

(

||у — Хт\\ Ш1П,

сI

Е 1НН < «>

3=1

где к; — параметр регуляризации.

Полиномиальная регрессия

Зависимая переменная восстанавливается [6] в виде

7

у = шр1,...,рс1х11 • • ■ хР<11 гДе 7 — степень регрессии. Решение

и—О рН-----

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

Х1 • • • хс2 •

Криволинейная регрессия

Зависимая переменная восстанавливается [6, 34] в виде

к

у = Е 'шз1РАхь • ■ • > Хсд, где Ч>э-> 3 — 1,..., & — преобразования Жп —>• Ж. ¿=1

Решение ищут методом наименьших квадратов аналогично линейной регрессии для матрицы X, в которой в г -й строке у -я компонента есть щ{х1,.. .,ха).

Логистическая регрессия Зависимая переменная восстанавливается [22, 27] в виде у = , г —

п

Е и)зхз + и)0-

3=1

Метод опорных векторов

Зависимая переменная восстанавливается [3,25] в виде у — (ги, х), вектор

ъй — линейная комбинация описаний объектов х^ г — 1,..., т. Для поиска

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

171 2

программирования: ((«;, щ — у()) + г(ги, го)2. Заметим, что в задаче ми-

г=1

нимизации и в зависимой переменной используется скалярное произведение описаний объектов. Также зависимая переменная может восстанавливаться в виде у = (ги,<р(х)): где (р — некоторая функция преобразования описаний объектов. Тогда в задаче оптимизации вместо скалярного произведения

(хг, х^) будет использоваться ((р(х{), (/?(£})), для представления которого могут быть использованы ядра:

• однородное полиномиальное

• неоднородное полиномиальное ((аГ^я}) + 1)а;

• радиальная базисная функция ехр(—— ж}||2);

• сигмоид tanh (а(ж*г, ж}) + Ь).

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

т

X; иц{х)у1

Зависимая переменная определяется [21] как у — -, где т^х) =

¿=1

К (^¡р^, г — 1,..., т, К — ядерная функция, к — ширина окна. В качестве ядерных функций используются:

• ядро Епанчикова К (г) — |(1 — г2)/[|г| ^ 1];

• квадратическое ядро К(г) = ||(1 — г2)2/[|г| ^ 1];

• ядро Гаусса К (г) = ехр(-у);

• прямоугольное ядро К (г) — \1[\г\ ^ 1];

• треугольное ядро К (г) = (1 — |г|)/[|г| ^ 1].

Здесь 1[х] — функция-индикатор. Для выбора ширины окна Н используется метод скользящего контроля: искомое значение И есть решение задачи

771

минимизации функционала СУ {К) — ~ Уиг)2, гДе Уш вычисляется по

г=1

выборке объектов с номерами {1,..., г — 1, г + 1,..., т}.

Метод к ближайших соседей Зависимая переменная представляет собой среднее, взвешенное в изменяющейся окрестности [26]. Эта окрестность определяется только теми значениями переменной х, которые являются к ближайшими к х, величина к является параметром.

Искусственные нейронные сети Для решения задачи восстановления зависимости используется нейронная

сеть [42,43] прямой передачи сигнала типа многослойный персептрон с одним или несколькими скрытыми слоями. Скрытый слой состоит из нейронов с нелинейной функцией активации: логистической /(ж) = 1+ехр(аа;) или гиперболическим тангенсом /(ж) = ехр(ж)+ехр(-ж) • ® качестве функции активации нейронов выходного слоя используется линейная функция. Обучение сети производится методом обратного распространения ошибки.

Регрессионные деревья Метод восстановления зависимости описан в [23,30,31]. Листовым вершинам дерева приписываются значения зависимой величины, внутренним вершинам — признак описания объекта и его пороговое значение. Для восстановления зависимой величины нужно спуститься из корня дерева в листовую вершину, причем для определения поддерева, через которое проходит путь, производится сравнение значения признака, приписанного текущей вершине, и значения признака объекта, для которого производится восстановление зависимой величины. Процесс построения дерева является «жадным» алгоритмом, на каждом шаге выбирается признак и помещается в текущую вершину, для которой далее строятся поддеревья. Для выбора признака используется один из критериев:

• ГОЗ, основанный на учете прироста информации;

• С4.5, основанный на учете нормализованного прироста информации;

• БВ-САКГ, использующий оценки распределения описаний объектов и зависимой величины.

Случайный лес

Метод восстановления зависимости заключается в использовании комитета решающих деревьев [24,37]. Структура каждого дерева аналогична структуре регрессионных деревьев. Деревья строятся по следующей процедуре:

• генерируется случайная подвыборка обучающей выборки с повторениями;

• для каждой внутренней вершины выбирается признак из подмножества признаков мощности (I < выбор осуществляется на основе критерия Гини;

• дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга.

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

Метод группового учета аргумента Метод заключается в порождении и выборе моделей восстановления зависимости оптимальной сложности [11,18,38]. Под сложностью модели в МГУА понимается число параметров. Для порождения используется базовая модель, подмножество элементов которой должно входить в искомую модель. Для выбора моделей используются внешние критерии, специальные функционалы качества моделей, вычисленные на тестовой выборке. Индуктивный алгоритм построения модели оптимальной структуры состоит из следующих основных шагов:

• выбор или задание класса базисных функций и преобразования данных, например, используется полипом Колмогорова-Габора у = гио +

(I <1 б.

Е + Е Е ЩзЩЪ + ...;

г=1 ¿=1,7=1

• выбирается целевая функция — внешний критерий, описывающий качество модели;

• индуктивно порождаются модели-претенденты;

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

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

Для порождения и выбора моделей может быть использован генетический алгоритм [17].

Регрессия на основе классификации (regression via classification)

Данный подход заключается в сведении задачи восстановления зависимости к задаче классификации [35, 45 47]. Процесс обучения заключается в дискретизации области значений зависимой величины, постановке специальной задачи классификации: объекты, значения зависимой величины yi которых принадлежат интервалу Aj разбиения, относятся классу Kj, и обучении классификатора. Процесс восстановления зависимой величины заключается в классификации объекта и преобразовании метки класса в значение зависимой величины, например, в качестве оценки берется центр интервала. Известны коллективные методы восстановления регрессии на основе классификации [32], в которых генерируется N независимых разбиений на п интервалов, ставится N задач классификации с п классами. В качестве восстановленного значения зависимой величины берется среднее по результирующим значениям элементов коллектива. Для разбиения области значений зависимой величины используются методы: интервалы равной ширины, интервалы равной частоты [29], критерий контраста монотетичности [40], векторная

квантизация [36].

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

В то же время, случай дискретной величины у — {1,..., Ь] (стандартная задача распознавания) в настоящее время достаточно хорошо изучен. Более 20 лет тому назад Ю.И.Журавлевым было отмечено, что задача распознавания может рассматриваться как задача экстраполяции специальных функций, когда независимые переменные (значения признаков) могут быть фактически произвольны, а зависимая величина принимает конечное число значений. В настоящее время существуют различные модели и конкретные алгоритмы для решения задач распознавания [1,5,7,9,10,13,20,25]. С середины 70-х годов 20-го века были разработаны подходы для решения

задач распознавания коллективами эвристических распознающих алгоритмов (алгебраический подход [8,9], логические корректоры [9,10]). В [28] описан Байесовский подход к синтезу коллективных решений, получивший определенное развитие за рубежом.

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

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

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

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

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

Основные положения, выносимые на защиту.

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

2. Модели восстановления зависимостей «байесовский корректор» и «линейный корректор».

3. Доказательства свойств корректности и устойчивости моделей восстановления зависимостей «байесовский корректор» и «линейный корректор».

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

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

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

Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений.

Апробация работы. Основные результаты работы докладывались на следующих научных конференциях:

• 14-я всероссийская конференция «Математические методы распознавания образов» (Суздаль, 2009 год);

• 2-я международная конференция «Классификация, прогнозирование, анализ данных» СРБМ-2010 (Варна, Болгария, 2010 год);

• 10-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ-10-2010» (Санкт-Петербург, 2010 год).

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

Публикации. Основные результаты по теме диссертации изложены в 4 научных статьях [14-16,41], из них 2 работы [15,16] — в журналах, включенных в Перечень ведущих рецензируемых научных журналов и изданий.

Краткое содержание. В первой главе описывается общий подход к р�