Методы решения задачи восстановления зависимости коллективами распознающих алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Ткачев, Юрий Игоревич

• Ткачев, Юрий Игоревич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Ткачев, Юрий Игоревич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 Результаты

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Методы решения задачи восстановления зависимости коллективами распознающих алгоритмов»

Введение

Рассматривается стандартная задача восстановления зависимостей между вектором независимых переменных х — ..., х^), х^ 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] — в журналах, включенных в Перечень ведущих рецензируемых научных журналов и изданий.

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

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

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

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

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

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

Рассмотрим разбиение области значений целевого признака А = {Дь ..., Д„} на интервалы Дх = (¿1],..., Дп = (<¿„-1,4]-

Возьмем число 2 ^ Ь ^ п, и определим N разбиений отрезка Я на Ь интервалов, поставив каждому разбиению в соответствие вектор с целочисленными компонентами к^ = (0, ..., /с^-1^, п), г = 1,..., ТУ, < < п. Каждое разбиение отрезка Я определяет разбиение мно-

жества М = М1 х • • ■ х М^ на Ь непересекающихся подмножеств К{,..., Кгь ь

(классов): М = и К\, и ^ ¡1 Кги П Кг — 0 согласно правилу: объект х

¿=1

принадлежит классу Щ разбиения Кг = {К[,..., Кгь} тогда и только тогда, когда у = f(x) € Да; и к £ /с^+т.]. Каждое разбиение Кг определяет стандартную задачу распознавания с Ь классами. Пусть А( — некоторый алгоритм решения задачи распознавания Zг, относящий произвольный объект х к одному из классов Кг , щ = 1,..., Ь.

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

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

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

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

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

Без ограничения общности считаем, что объекты обучающей выборки упорядочены по возрастанию значения целевого признака, тогда yi,---,ymi G Ai, ymi+1, . - - , Ут2 G Д2, . . . , 2/m„_i+1, • • • , Утп G An.

Введем обозначение Q(А) — погрешность разбиения A, Q(А) =

п Ц

Е Q({U-i, • ■ •, ч}), Q{{it-i, • • •, г*}) = Е (Ук - vt)2, yit_1+1, ...,yit,vt е

Ai, t = 1,... ,n. Поиск оптимального разбиения производится по номерам граничных объектов i = 1,..., п.

Для фиксированного разбиения А погрешности разбиения Q( А) до-

it

£ Ук

стигается на значениях Vt = Г'^"1 ^ , i = l,...,n. Действительно, функционал Q{А) — гладкая функция переменных = 1 =

it

2 Е (г/А — Vi) = 0, i = 1,..., гг.

A;=it_i+1

Оптимальное разбиение будем строить с помощью метода динамического программирования [2].

Алгоритм построения оптимального разбие-

ния:

1: G(i, 1) = Q({i,..., п}), i = п,..., m;

2: for t = 2, . . . , П do

3: for i — П — t, . . . ,171 — П + ldo

4: for к — i,... ,m — i+ldo

5: к) = Q({i,..., /с}) + С(г + 1, t - 1);

6: end for

7: G{i,t)= min gt(i,k); 8: I{i,t)= argmin gt{i,k)-,

i^k^m—t+l

9: end for 10: end for

Погрешность оптимального разбиения есть G(l,n). Вычислительная сложность рассматриваемого алгоритма есть 0(пт2).

Для описания оптимального разбиения воспользуемся индексами объектов it,t = 1,... ,п: 1: г0 = 0; 2: ¿1 = /(1,п); 3: for t — 2,..., п do 4: it = /(г4-1 + 1,П - t)\ 5: end for

Границы интервалов оптимального разбиения dt,t — 1,... ,п — 1, определяются из условия dt € {Уц,Уг1+1), например, dt — Уч+^ч+х. Крайние значения разбиения должны удовлетворять условиям do < yi, ут < dn, например, do = 2yi - di, dn = 2ут - dn-\.

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

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

Пусть задано разбиение области значений целевого признака А = {AfcjjJ-! на п интервалов.

Считаем декартово произведение К1 х • • • х К^ х А множеством элементарных событий, событие (К^,..., К^ , А&) означает: «объект х отнесен алгоритмом А\ в класс ai,..., алгоритмом An в класс ан, у = f(x) G А/с». Вероятность такого события обозначается как • ■., KaN, А и) или

P(£,Afc).

По формуле Байеса имеем

р(д*1 О =

а\ 1 • • • » Лалг>

" а\> " • • » ^ *'адг;

(1.1)

Пусть классификаторы статистически независимы, тогда

Р(^,...,<|Д,) = ПР(^а.|А*), Р«, = ПР«), И

г=1 г=1

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

Р(Д*|*) = Р(А,К, - - -, О = /(А*} П Р«1Д^) (!-2)

П Р(^)

1=1

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

(Р( Ах ,..., Р(Ди|ж)) —> М, где Р(Д&| х), к — 1,..., п получены из формулы (1.1).

Определение 2 Наивным байесовским корректором называется функция Р:

(Р(Ах,..., Р(Д„|ж)) —> М; где Р(Д&|:е), к = 1,..., п получены из формулы (1.2).

Далее будем рассматривать именно наивный байесовский корректор. Примечание: в случае задачи распознавания у — метка класса при классификации объекта х, а все разбиения Кг совпадают). Модель наивного байесовского корректора в задаче распознавания описана, например, в [28].

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

п

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

к=1

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

ТЬ

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

з=1

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

1. формирование разбиений вещественной оси на интервалы Д^, к — 1,..., щ

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

3. вычисление оценок вероятностей Р(Д^), Р(-?ф, г = 1,...,ТУ, ^ = /с = 1,...,п.

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

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

2. вычисление значений условных вероятностей р\,...,рп по формулам (1.2);

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

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

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

Далее рассматривается задача с числом классов Ь = 2. Зададим ТУ = п — 1 задач классификации: для задачи Zi вектор меток имеет вид: (0,г,тг),г = 1,..., ТУ.

Рассмотрим объект х обучающей выборки, значение целевого признака которого у(х) G Afc- В задаче Z^i = 1,...,N данный объект содержится в обучающей выборке, причем х G и = к,..., ./V; х G К^, и — 1,..., k—1.

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

. , ■ -К2, i — 1, ■ ■ •, к — 1, Мх) = { (1.3)

К[, i = к,..., п. 1.2.2. Вычисление оценок вероятностей

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

т

F = JZ(yi- Уг? min (1.4)

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

ь

5]P(Äj) = l,i = l ,...,iV; i=i

Tl

P(Afc) = 1, Р(А*) > 0, к = 1,..., n; (1.5)

k=i

п

Y, Р(Ал) P(Ä]|Afc) = P(Äj), P(äJ|A*) ^ 0, г = 1,..., N, j = 1,..., L.

k=l

В данной задаче функционал — гладкая, выпуклая функция переменных P(Kj\Ak), P(Afc), P(Kj). Множество, по которому осуществляется оптимизация, являются выпуклым, что позволяет использовать для решения задачи метод проекции градиента.

Частным случаем задачи (1.4) является задача с фиксированными P(Afc),

Аналитическое решение Рассмотрим аналитическое решение данной задачи для корректных алгоритмов распознавания А при Ь — 2.

Обозначим Рг = Р(К{), Р(К{\Ак) = е\к\ % = 1,..., Ы, к = 1,...,п. Оценки вероятности интервалов Р(Д/с) будем считать фиксированными, ?{&к) = ак,к = 1,...,п.

Пусть У1 е /\к — 1- Тогда для Хг в силу (1.3):

а-д)...^-,)^...^1-^ ■'' ^^ • • • ^ =1 - ^

(1.6)

Разделив уравнение (1.6) для г = 2, 2 = 1 на уравнение (1.6) для I — 1,2 = 1) получаем: = 0. Т.к. > 0, то е^ = 1.

Разделив уравнение (1.6) для % — 3, ^ = 2 на уравнение (1.6) для г = 2,2 — 2, получаем: у^г = 0. Т.к. > 0, то е^ — 1.

Далее разделим уравнение (1.6) для г = 2,2 — 2 на уравнение (1.6) для г = 1, У = 2, получаем: ^^. Т.к. -^р1 > 0, то е^ = 0.

Разделив уравнение (1.6) для г = к + 1,2 — к на уравнение (1.6) для г = к, 2 = к, аналогично получаем е^ = 1. Далее последовательно для £ = к — 1,..., 1 делим уравнение (1.6) для г — 1,2 — к на уравнение (1.6) для г = к^ = к, получаем е^ = 0.

(к) 1 <

Итак, е\ — <

II, г = к.

Заметим, что в каждое уравнение с нулевой правой частью входит хотя бы один нулевой сомножитель. Уравнения с ненулевой правой частью принимают вид:

аке{^ ... = (1 - Л)... (1 - Рк-г)Рк ...Рп,к — 1,... ,п (1.7)

Условия 1.5 принимают вид:

¿—1

Р< = ^с^е?*+ а4>1 = 1,..., п (1.8)

¿=1

Пусть е^ = •■• — е^ ^ = ек, к = 2,..., п. Тогда уравнение (1.7) пред ставимо в виде:

акек+1... е„ = (1 - Л)... (1 - Рк-\)Рк ...Рп,к = 2,...

а уравнение (1.8) - в виде:

п

(1.9)

г—1

Р» = ^ ^ + г = 1, • • •,

п

(1.10)

¿=1

Последовательно для Ь — 2,... ,п делим уравнение (1.9) для к = Ь на уравнение (1.9) для А; = £ + 1, получаем:

ег

Рг-1

Ь = 2, ...,п

(1.11)

1 -

Покажем с помощью метода математической индукции, что Р{ —

Базис индукции: из уравнения (1.10) для г = 1 получаем Р\ — а\] подставляем Р\ в уравнение (1.11) для £ = 2, получаем е2 = =

Шаг индукции: подставляем значение е^+х, полученное на предыдущем шаге, в уравнение (1.10):

% — 1,..., п.

Р¡+1 = ег+1 щ + = 04+1

¿=1

Е1=1 1 - Е!=1

+ 1

«г+1

Подставляем в уравнение (1.11) для £ = г + 1:

бг+2

1 - е;=1 ^

«г+2

«г+1 [1 - Р{+1] «¿+1

1 - Е!=1

1

аг+г

1 - ЕЙ! ^

Итоговые значения параметров байесовского корректора:

/

О, г < к,

р(я;|д*) = Ь, I — к

г — к

Р(Кг2\Ак) = 1-Р(К{\Аку,

(1.12)

р{Ю2) = 1 - Р(^);

г = 1,..., п; к — 1,..., п.

Список литературы диссертационного исследования кандидат наук Ткачев, Юрий Игоревич, 2013 год

Литература

1. Баскакова Л.В., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // ЖВ-МиМФ. 1981. Т.21, № 5. С.1264-1275.

2. Беллман Р., Дрейфус С.. Прикладные задачи динамического программирования — М., Наука, 1965.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. - М.: Наука, 1979.

4. Гантмахер Ф.Р.. Теория матриц. — М.: Наука, 1967.

5. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Дискретный анализ. Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. С. 3-11.

6. Дрейпер Н., Смит Г. Прикладной регрессионный анализ. — М.: Издательский дом «Вильяме», 2007.

7. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976, С.511.

8. Журавлев Ю.И. Корректные алгебры над множествами не корректных (эвристических) алгоритмов. //I. Кибернетика. 1977. N4. С. 5-17., II. Кибернетика, N6, 1977, III. Кибернетика. 1978. N2. С. 35-43.

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

10. Журавлев Ю. И., Рязанов В. В., Сепько О. В. РАСПОЗНАВАНИЕ. Математические методы. Программная система. Практические применения. — М.: Фазис, 2005.

11. Ивахненко А.Г. Индуктивный метод самоорганизации моделей сложных систем. — Киев: Наукова думка, 1982.

12. Подкопаев Д.В. Оценка эффективности лечения больных артериальной гипертонией на амбулаторном этапе: дис.канд.мед.наук. М., 2008. 148 с.

13. Рязанов В.В. Логические закономерности в задачах распознавания (параметрический подход) // ЖВМиМФ. 2007. Т.47, №10, с.1793-1808.

14. Рязанов В. В., Ткачев Ю.И. Решение задачи восстановления зависимости коллективами распознающих алгоритмов // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. - М.: МАКС Пресс, 2009. - С. 172-175.

15. Рязанов В.В., Ткачев Ю.И. Решение задачи восстановления зависимости коллективами распознающих алгоритмов // Доклады Академии наук. 2010. Т. 432. № 6. С. 750-754.

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

17. Стрижов В.В., Шакип В.В. Выбор оптимальной регрессионной модели. // Математика. Компьютер. Образование. XII международная конференция. Тезисы докладов, 2005.

18. Стрижов В.В. Методы индуктивного порождения регрессионных моделей. М.: ВЦ РАН, 2008.

19. Тихонов А.Н. О решении некорректно поставленных задач и методе регуляризации. // Доклады Академии наук. 1963. Т. 151. №3. С. 501— 504.

20. Уоссермен Ф. Нейрокомпыотерная техника, — М.: Мир, 1992.

21. Хардле В. Прикладная непараметрическая регрессия. — М.: Мир, 1993.

22. Bishop С. Pattern Recognition and Machine Learning. Springer, 2006.

23. Breiman L., Friedman J.H., Olshen R.A., Stone C.J. Classification and regression trees. Monterey, CA: Wadsworth. 1984.

24. Breiman L. Random forests. // Machine learning 45.1. 2001. pp.5-32.

25. Christopher J.C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. // Data Mining and Knowledge Discovery 2, p.121-167, 1998.

26. Cover T.M., Hart P.E. Nearest neighbor pattern classification. IEEE Trans. Inform. Theory. IT-13(1), 1967. pp.21-27.

27. David W. Hosmer, Stanley Lemeshow. Applied Logistic Regression, 2nd ed. New York, Chichester, Wiley. 2002.

28. Domingos P., Pazzani M.. On the optimality of the simple Bayesian classifier under zero-one loss. // Machine Learning, 29, 1997. pp.103-130.

29. Dougherty J., Kahavi R., Sahami M. Supervised and unsupervised discretization of continuous features. // Proceedings of the 12th International Conference on Machine Learning. (ICML-95), Morgan Kaufmann, 1995. pp. 194-202.

30. Fan W., McCloskey J., Yu P.S. A general framework for accurate and fast regression by data summarization in random decision trees. // Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (ICKDM-06), ACM New York, NY, USA., 2006. pp.136-146.

31. Geurts P., Ernst D., Wehenkel L. Extremely randomized trees. // Machine Learning, 63, 2006. pp.3-42.

32. Halawani S.M., Albidewi I.A., Ahmad A. A Novel Ensemble Method for Regression via Classification Problems. // Journal of Computer Science 7 (3), 2011. pp.387-393.

33. Harrison D., Rubinfeld D.L. Hedonic housing prices and the demand for clean air. // Journal of Environmental Economics and Management, vol.5. 1978. pp.81-102.

34. Hastie T., Tibshirani R. Generalized additive models // Statistical Science, vol. 1. 1986. pp. 297-318.

35. Indurkhya N., Weiss S.M.. Solving regression problems with rule-based ensemble classifiers. // Proceedings of the 7th ACM International Conference Knowledge Discovery and Data Mining, (KDD-01), ACM New York, NY, USA. 2001. pp.287-292.

36. Kohonen T. Self Organization and Associative Memory. 3rd Edn., SpringerVerlag, Berlin, Germany. 1989.

37. Liaw A., Wiener M. Classification and Regression by randomForest. // R news. 2002. Vol. 2. pp.18-22.

38. Malada H.R., Ivakhnenko A. G. Inductive Learning Algorithms for Complex Systems Modeling. CRC Press, 1994.

39. Meinshausen N. Relaxed lasso. // Computational Statistics and Data Analysis, 52. 2007. pp. 374-393.

40. Merckt T.V.D. Decision trees in numerical attribute spaces. // Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1993. pp.1016-1021.

41. Ryazanov V.V., Tkachev Ju.I. 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. Setiono R., Leow W.K. Pruned Neural Networks for Regression. // Proceedings of the 6th Pacific Rim Conference on Artificial Intelligence, PRICAI, 2000. pp.500-509

43. Specht D.F. A general regression neural network. // IEEE Transactions on Neural Networks, Vol. 2., N. 6, 1991. pp.568-576.

44. Tibshirani R. Regression Shrinkage and Selection Via the Lasso // Journal of the Royal Statistical Society, Series B. 1994. N. 58, pp.267-288.

45. Torgo L., Gama J. Regression by classification. // Advanced Artificial Intelligence, 1159. 1996. pp.51-60.

46. Torgo L., Gama J. Regression using classification algorithms. // Intelligent Data Analysis, 1. 1997. pp.275-292.

47. Torgo L., Gama J. Search-based class discretization. // Machine Learning, 1224. 1997. pp.266-273.

48. Yeh I-Cheng. Modeling of strength of high performance concrete using artificial neural networks. // Cement and Concrete Research, Vol. 28, N. 12. 1998. pp.1797-1808.

49. Zhao P., Yu B. Stagewise lasso. // The Journal of Machine Learning Research, 8. 2007. pp. 2701-2726.