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

Нгуен Чонг Тинь

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

Специальность 05.13.18-Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

5 ДЕК 2013

Тула 2013

005542675

005542675

_ Работа выполнена на кафедре «Информационная безопасность» в ФГБОУ ВПО «1ульскии государственный университет».

Научный руководитель

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

кандидат физико-математических наук, доцент кафедры «Информационная безопасность» ФГБОУ ВПО «Тульский государственный университет».

Красоткина Ольга Вячеславовна Воронцов Константин Вячеславович, доктор Физико-математических наук, старший научный сотрудник ФГБУН Вычислительный центр им. A.A. Дородницына РАН.;

Герлейн Отго Владимирович, кандидат физико-математических наук, доцент кафедры «Математический анализ» ФГБОУ ВПО «Тульский государственный университет».

Ведущая организация: ФГБУН «Институт проблем управления» им.

В.А. Трапезникова Российской академии наук (ИПУ РАН).

Защита диссертации состойся «30» декабря 2013 г. в 14 часов на заседании диссертационного совета Д 212.271.05 при ФГБОУ ВПО «Тульский государственный университет» (300012, г. Тула, пр. Ленина, 92, ауд 12-105) государственный

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Тульский государственный университет», по адресу: 300012, г. Тула, пр. Ленина, 92.

Автореферат разослан «29» ноября 2013 г.

Ученый секретарь диссертационного совета Д 212.271.05, доктор физико-математических наук, доцент

М.Ю. Соколова

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

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

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

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

измерения признаков.

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

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

В-четвертых, на сегодняшний момент в литературе известен ряд методов отбора признаковой информации, имеющих непереборную природу,: гребневая регрессия, предложенная А. Хоерлом и Р. Кеннардом в 1970 г., LASSO, разработанный Р. Тиб-

ширани в 1996, и являющиеся его последовательными улучшениями Elastic Net SCAD и адаптивный LASSO, предложенные X. Зоу, Т. Хасги и Р. Ли в 2005, 2001 и 2006 гг. соответственно. Как правило, существующие методы принято характеризовать такими свойствами как несмещенность, селективность, состоятельность получаемых оценок, конечность верхней границы риска оценок, способность к отбору в модель коррелированных регрессоров. К сожалению, на сегодняшний момент не существует ни одного метода селекции признаков, удовлетворяющего сразу всем вышеперечисленным требованиям.

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

Задачи исследования. Для достижения поставленной цели в диссертации

сформулированы и решены следующие задачи:

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

_ Задача 2. Создание методов комбинирования модальностей существенно оаз-нои природы в единой системе.

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

Задача 5. Исследование свойств оценок параметров, получаемых с помощью предложенной селективной иерархической вероятностной модели: селективности несмещенности, состоятельности (построение оракульных неравенств), способности к отбору коррелированных регрессоров, непрерывность исследование верхней границы риска оценок. г

Задача 6. Создание алгоритмов оценивания разработанных моделей селективности, применимых для различных задач анализа данных вне зависимости от вида связи модальностей в искомой зависимости: задачи линейной регрессии задачи порядковой регрессии, задачи анализа продолжительности жизни и многомодального восстановления регрессионной зависимости.

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

Объект и предмет исследования. Объектом исследования является задача восстановления зависимостей по эмпирическим данным. Предметом исследования является повышение обобщающей способности алгоритмов восстановления зависимостей при обучении по малонаполненным выборкам.

Положения, составляющие научную новизну и выносимые на защиту _ Априорная иерархическая вероятностная модель параметров восстанавливае-ко°вИой^нформадииП°ЗВОЛЯЮЩаЯ 0существлять селективное комбинирование призна-

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

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

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

Методы исследования. Теоретические исследования основаны на применении

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

Экспериментальные исследования осуществлены на модельных данных и известных реальных данных. Результаты экспериментов сравнивались с передовыми мировыми аналогами для оценки полученных результатов теоретических исследоваНИИ Достоверность полученных результатов подтверждается доказанными математическими утверждениями и модельными экспериментами.

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

Апробация работы. Основные положения и результаты диссертации докладывались на XV Всероссийской конференции «Математические методы распознавания образов» (Республика Карелия, г. Петрозаводск, 2011 г.), XVI Всероссийской конференции «Математические методы распознавания образов» (Республика Татарстан, г. Казань, 2013 г.), Международной конференции «Интеллектуализация обработки информации» (Республика Черногория, г. Будва, 2012 г.).

Публикации. По материалам диссертации опубликованы 7 работ из них з_ в научных изданиях, рекомендованных ВАК при Минобрнауки РФ. В работах [1-3.1, выполненных в соавторстве, соискателем предложена математическая модель в задаче селективного комбинирования признаковой информации, разработан алгоритм оптимизации критерия максимального правдоподобия, описаны результаты экспериментальных исследований.

Структура и объем работы. Диссертация состоит из введения, четырех глав основных выводов, списка литературы и приложений. Материал изложен на 137 страницах, содержит 26 рисунок, 29 таблиц, список литературы из 104 наименовании.

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

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

структура диссертации.

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

Пусть оеП - множество объектов произвольной природы, которые характеризуются некоторой целевой (скрытой или зависимой) переменной уеУ. В данной работе рассматривается задача оценивания регрессионной зависимости, в которой целевая переменная принимает значение либо из множества действительных чисел, либо принадлежит порядковому множеству. Как правило, функция у(со):П~>У -известна нам только для некоторого ограниченного набора объектов, называемого обучающей совокупностью а' =>{©,,7(05,)};./ = где N - число наблюдений.

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

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

емая признаком. Наиболее простым предположением является понимание признаковых представлении объектов как последовательностей действительных чисел Х((В) - G R", где р-число признаков. В цели упрощения можем заме-

нить х(а) = (х,(и),...,хДш)) обозначением х = (Л„...,г) и заменить v(<a.) обозначением у . '

Пусть ф(у| ш, w) - параметрическое семейство условных плотностей распределения, описывающее искомую зависимость. Восстановить зависимость означает подобрать подходящее значение параметра w = (w„...,wp). Если число признаков р в

™1ГЛИК°' а°бъем обучающей выборки N недостаточный, то полученная зависимость может обладать низкой обобщающей способностью н<ш зави

ин000Г=Ьн^0бЩШ01ЦУЮ СПОСОбнОСТЬ можно введением в модель априорной информации об искомых параметрах в виде априорной плотности распределения

ни* o?rrP!13Hf0B ИГраеГ Важную Р°ль и часто используется в процессе обуче-о^чен„яУ избь1Т0ЧН"е признаки или помехи, приводит к ускорению алгоритма nJZZ' повышает его эффективность, увеличивает его обобщающую способность « ™ °ПТИМаЛЬНОГО подмножества признаков является очень трудоемкой"^ У 8 ИДеЗЛе ***** ПеРеб°Ра всех возможных подмножеств исходною ст а получ^Г^^;иП°СТРОеН,1Я На КЗЖДОМ И3 НИХ зависимости и оценивания кач™ "с"мос™ ™ некоторому внешнему критерию. Естественно такая процедура является NP-полной и на практике применяется очень редко

кятетп™^"НЫС ' литеРат>'Ре MeT£№' отбора признаков можно разделить на две

з™Тле^Го™СТр0еННЫ,е МеТОДЫ- В методах"ФильтРах процесс отбора при-отделен от процедуры обучения зависимости. При применении методов из

жетбйГосГе™ЛИУеТСЯ ДВе <ЛраТ6ГИИ OT6°P- Во-первь£, отбор приз™ моД° Примснения алгоритма на основе различный методов выяв-nnZC КаЖД0Г° «дального признака и целевой переменной. Недостатком такого

мГГисГости пеоСП°СОбНОСТЬ аЛГОрИ™а Учитьшать ос°бенности восстан^лива™ мои зависимости. Во-вторых, могут применяться различные вариации жадного алго-

oZ поП°о3пВ0ЛЯЮЩИе добавлять У^ять признаки в активное множе™^ради-^1ТГепш1Ии?г,ГРУППаМИ- ДМ °ЦеНИлВаНИЯ качества полученной зависимой ЗЗГГ» ^ критерии Акаике или Байеса. Недостатками подобной то' ™ количество шагов отбора может быть очень большим, а S™«0"3" позволяет преодолеть такие явления, как мультиколлинеарность.

НССТабиЛЬИЫМИ' ПОТОМУ ™ при незначительных изменениях данных^ набор выбранных переменных может очень сильно различаться

мом °Т фМЬТр°В' во встР°енных методах отбор тесно связан с алгорит-

bctd~Tr В МеТ°ДаХ ДаНН0Й Группы инстРУме|[т отбора признаков

LT^™ °буЧеНИЯ В КаЧ£СТВе ^oPHoro предположения о восста-ХзнакоГи ™ИМ0С™ И' КаК процедура обучения дает и множество

X™ УЮ зависимость" El«e одним достоинством встроенных методов

взвешивать пРизнаки в процессе обучения. Кроме того, так как u^W Ра Прга"аКОВ встРоена в процедуру обучения, вычислительная сложность таких методов, как правило, ниже, чем вычислительная сложность фильтров

сияГА^п'рГ Т°мН7 вЛ-еРат^ известен Рад таких методов: гребневая рецессия LASSO, Elastic Net, SCAD и адаптивный LASSO. Каждый из методов зависит от вида априорнои плотности распределения параметров модели. Априорная плотность при гребневой регрессии имеет вид:

VO, ) ос exp(-\w* );Х>0. ( 1 )

Априорная плотность распределения оцениваемых параметров в методе LASSO имеет вид!

4>(vf,)ocexp(-A.|w,|);A.>0. (2)

Априорная плотность распределения оцениваемых параметров в методе Elastic Net имеет вид:

vj/(>v; ) ос ехр(-(^э |w, | + )); ^з Д4 > 0. (3)

Априорная плотность распределения оцениваемых параметров в методе SCAD имеет вид:

V)j(wt) ce ехр(-р>(| iv, [)), (4)

X\w; w, |<Л, где р(\ wf |) = • -(I w, |2 -2а \ w, | +Х>)/{2(а- 1)},М w, |< аХ,

(а + 1)Я.2/2,| w,. |> аХ, а > 2,Х > 0.

Априорная плотность распределения оцениваемых параметров в методе адаптивного LASSO имеет вид:

) ce ехр(-Ха, |), где а,. = l/|wwf Ху > 0- (5)

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

• селективность - способность исключать из модели незначащие признаки I-I^^jr, где / = - множество всех признаков, I" ={je.I,ws* 0} -множество признаков, входящих в модель, Г = {j е l,w, = 0} - множество исключенных из модели признаков;

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

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

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

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

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

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

верхней грани риска оценки - это области разреженных оценок, т. е. области нашего интереса.

Таблица 1. Свойства встроенных методов отбора признаков

Селективность

Несмещенность

Эффективность группировки

Состоятельность

Верхняя граница риска оценки

Непрерывность

Ridge

LASSO

Elastic Net

SCAD

Адаптивный LASSO

00

Предлагаемый метод

+

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

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

Задача линейной регрессии

В задаче линейной регрессии целевая переменная принимает свое значение из множества действительных чисел, и значение целевой переменной получается как линейная комбинация скрытых параметров: ^(ш,= р 1 (о>) + £, где -случайная величина с нулевым математическим ожиданием и дисперсией о. Тогда

Ф0>, I «О = (1/72^) ехр [~{у1 - ]Г (о>у ))2 /(2а)] и легко получить совместное распределение целевых переменных:

ФСи„...,Я, 1^)°сЩ.ехР[-0;/-Е,С,^Ю)7(2а)]. (6)

Задача анализа продолжительности жизни

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

• целевая переменная неотрицательна;

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

В данной задаче обучающая совокупность представлена тройками следущего вида , где у> - время жизни или наблюдения, х, - вектор признаков объек-

тов и 5,- признак цензурированности. Если 5,. = % то цензурирования нет и ^ - время жизни объекта. Если 8, = 0, то цензурирование есть и у,- время наблюдения за объектом. Зачастую целью восстановления зависимостей в этой задаче является не предсказание продолжительности жизни конкретного объекта, а определение признаков, ко-

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

| ^) = П111[ехр(х^)/Х;^ехр(х^)]5' Л,=У:У/ >у,}. (7)

Задача порядковой регрессии

Задача порядковой регрессии — это задача, в которой целевая переменная принадлежит некоторому множеству с введенным на нем отношением порядка: уе У;У = {гапк1,...,гапк^у где гапк1 -< ...-< гапкч. Таким образом, объекты обучающей выборки оказываются упорядоченными в соответствии со значением целевой переменной. Отношение порядка, которое целевая переменная вводит на объектах обучающей выборки, является бинарным отношением, поэтому в качестве модели генеральной совокупности будем рассматривать параметрическое распределение <р(х1,ху|«',С), определенное на парах объектов (х,.,ж.) и связанное с направлением w в пространстве X определяющим отношение порядка для любой пары объектов:

уу7^ -ху) < -1,

«ыъ.тул ' [ехр[-Слут(х, -ху )],у/(х, -ху) >-1. Тогда совместная априорная плотность распределение будет иметь вид:

П Ф(*,.х,к,С). (9)

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

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

Рассмотрим теперь как устроена модель целевой переменной при представлении объектов потенциальными функциями. Обучающая совокупность при этом будет иметь вид О. =>{К1(а1,а>/)};1 = 1,...,ри',1 = 1,...,Ы. Всякая потенциальная функция K¡(a>J,(i)¡) погружает множество объектов О в некоторое действительное линейное пространство со скалярным произведением Я( , роль которого играет сама потенциальная функция. Использование потенциальных функций дает возможность работать с объектами произвольной природы в единых терминах линейной действительной функции /Хо>) :<Г2 —> К, для оценивания которой достаточно найти направляющий элемент 3,, тогда функция будет выражена в виде скалярного произведения _/~(со| &, ) = АГ,(Э( ,а)). Рассмотрим декартово произведение линейных пространств и определим скалярное произведение в нем как результат комбинирования потенциальных функций. Тогда регрессионной зависимостью, определяемой методом комбинирования потенциальных функций на множестве объектов, является следующая зависимость:

Ясо) = ЛГ(9,ш) + 6 = (10)

где д = (91,...,9р)бЙ1х...хП(!.

Для определения направляющих элементов Э, нужно дополнить модель некоторыми предположениями. Данные предположения похожи на предположения задачи линейной регрессии с той только разницей, что параметр и>: заменяется направляющим элементом 3,.

ф(х,.,х

' Cox D. Regression models and life tables // J. of the Royal Statistical Society. Ser. B. 1972. V. 74. P. 187-220.

значение целевой переменной получается как комбинация >'№'»)где случайная величина с нулевьш математическим ожиданием и дисперсией о.-Тогда условное параметрическое семейство плотностей распределения будет ^ имел, вид <р6л | Э,о>,) = (1Д&)

ехр[Чиу -ХГ,,^(Э1.шу)-6)2/(2ст)]. В этом случае совместное распределение целевых переменных в обучающей совокупности равно:

В свою очередь, будем рассматривать неизвестные параметры регрессии как независимые скрытые случайные величины, каждая из которых распределена в своем линейном пространстве 9, еП„ определенном соответствующей потенциальной функцией, в соответствии с нормальными законами с нулевыми математическими ожиданиями. Пусть дисперсии г,а параметров регрессии различны для каждой модальности и пропорциональны дисперсии шума наблюдения ст и таким образом, априорное распределение параметров регрессии будет имет! вид-М/(3,|^а)«:(1/7/;а)схр[-{!/2^а)/:,(3„3,)]. Что касается константы Ь, то нет ника-

^!Т0РН0Й ИНфТ,аЦИИ ° ее распределении, поэтому совместная априорная плотность распределения будет равна:

><*) = ГГ., о)«ГЕ11(1/>/^)ехр(-а/2/;а)Л:(СЭ„а,)):(12)

В третьей главе предлагается иерархическая вероятностная модель с регулиру-

«^1СЛС,СГИВН0СТЬЮ восстановления зависимостей. Производится обоснование табора априорнои плотности распределения параметров модели, управляемой единственным структурным параметром. Селективность, являясь структурным параметром алгоритма обучения, влияет на сложность обучаемой модели и тем самым пред-огавляет собой инструмент борьбы с переобучением с целью повышения обобщающей способности при восстановлении зависимостей в признаковых пространствах большой размерности. Выбрать подходящий уровень селективности можно одним из стандартных методов, например, по контрольной выборке или с помощью процедуры ГГШ6ГО К01ГГР°ЛЯ- Доказывается, что предложенный в диссертационной работе встроенный метод отбора признаков позволяет получать состоятельные, несмещенные оценки вектора коэффициентов, обладает способностью отбирать коррелированные регрессоры в определенной области пространства признаков и имеет конечную

°ЦеНКУ РИСКа- Т"е- в отличие от всех существующих методов обладает всеми свойствами идеальных в современном понимании оценок.

н„™„1ПрИОрНаЯ веРоятностная модель распределения параметров искомой за-

ВИДИМОСТИ

®ыберем В качестве априорной плотности распределения параметра ^ - нормальное распределение с нулевым математическим ожиданием и некоторой дисперсией г>- ^О, ехр/(2г))

раметров ^ регрессии имеет вид: ' С°Вместное Распределение па-

(13)

Будем предполагать также, что сами величины, обратные дисперсиям, имеют априорное гамма-распределение у(1/^а,р)«(1/г,Г1ехр(-Р/';)- Тогда совместная априорная плотности распределения дисперсий 1/г, примет вид:

G(l/rp...,l/^|a,ß) = YlljVir, |a,ß) - П,С,«1/';Г' exp(-P/0)- d4)

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

P(w,r | у,,...,у„) I w)4/(w1,...,wJ,[r1,...,r(,)G(l//"1,...,l/rp|a,P), (15)

На основе принципа максимизации апостериорной плотности, общий критерий оптимизации имеет вид:

I мОЧ^уц,...,w |)G(l//;,...,l/r | a,ß) -> max (16)

Выберем параметры a,ß следующим образом а = 1 + l/(2pi);ß = 1/(2ц), тогда получим математическое ожидание и дисперсию величины обратных дисперсий оцениваемых параметров в следующим виде: £(1/т-) = 2ц + 1, Vor (1/>-) = 2ц(2ц +1). Видим, что если ц стремится к нулю, то математическое ожидание стремится к единице, а дисперсия стремится к нулю, что соответствует включению всех признаков в модель, отбор переменных при этом не осуществляется. Если ц стремится к бесконечности, то величины, обратные дисперсиям, могут значительно различаться. Чем больше ц, тем большее число признаков, дисперсии которых стремятся к нулю, и число признаков, фактически исключаемых из модели, повышается. Изменение значения соответствует разным уровням селективности. Чем больше значение ц, тем меньше число отобранных признаков и наоборот. Таким образом, имеем способ, который регулирует оперативно уровень селективности. Параметр ц мы будем называть структурным параметром селективности.

Подставим распределения (6), (13), (14) и а = l + l/(2n);ß = 1/(2ц) в формулу (16). Получим выражение для критерия обучения задачи линейной регрессии

j(w„...,w,,г,...,/-»=м-х;>лк))2А2ст>+

, (17)

+0/2)Х1 + (1/2)0 + In /• + №)Zm c^'lv

Подставим распределения (7). (13), (14) и а = 1+1/(2ц);Р = 1/(2ц) в формулу (16). Получим выражение для критерия обучения задачи продолжительности жизни

j{y>x.....

/ ОЮ

+0/2)i;>7/o+(i/2)(i +1ЛОЕмЬ'г+ilvriHjn (в,, Д1,/

Подставим распределения (9), (13), (14) и а = l + l/(2[a);ß = 1/(2ц) в формулу (16). Получим выражение для критерия обучения задачи порядковой регрессии

■ (wH " (19)

st >0,S = {(i,j):Vj >-у,} jJ = \,..,N;V(i,e5: wr(x, - x,)>1 -S,r

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

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

функций имеет вид j| П',ц) = X" iАК>^J'^ + Ь' где паРаметРы

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

- и< min •

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

Свойства предлагаемой априорной модели

Асимптотическая несмещенность с точки зрения байесовской модели выражается в том, для что отобранных в модель признаков априорное распределение коэффициентов регрессии является равномерным. Достаточным условием для несмещенности является стремление к нулю производной регуляризирущего члена при увеличении параметра: -<1гщ/(] щ |))' ->0, когда | м>11->-0. Легко видеть, что данное требование удовлетворяется для штрафного члена с регулируемой селективностью для любого значения ц > 0.

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

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

Теорема 2. Если е [-1Д/Й ,1Д/н]. то | щ,-ц>}|->0, когдасогг(х„ху) -> 1.

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

Пусть = (теи,1У20) - вектор истинных коэффициентов модели, \ум = 0 и \у|0 состоит из коэффициентов отличных от нуля, л - число компонент вектора

= Еу(:п), «л), -+2>,\ ¿у= тах{(-1п1|/(| у, |))': м» * 0},

а„ = тах{(-1т)/(| и', |))': * 0}, Х = а!а8{(-1ПЧ/([ м>ш |))\...,(-1тК| и>,01))"}.

Теорема 3. При Ьы 0 существует локальная оптимальная точка \у, которая удовлетворяет условию |й- - || = Ор (А'~42 + а„).

Теорема 4. Если функция -1пу(| щ |) удовлетворяет условию Птт*"ПпипГ(—ц 1пц/(| |)') > 0,

Ц->«>, л/лг/ц-хю при N —>°о, то с вероятностью, стремящейся к 1, для локальной оптимальной точки й = (й„й2), удовлетворяющей условиям теоремы 3, выполняются условия:

(а) Множество отобранных в модель переменных совпадает с истинным множеством регрессоров, присутствующих в модели, т.е. \у2 =0.

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

VW/.iw,,) + Z){w, - w10 + (/,(w10) + S)-'b} -> N{0,/[(w10)}.

Необходимым и достаточным условием для непрерывности является argminfl | —(Invp(| w] |)'} = 0. Видим, что это условие выполняется для предлагаемого метода. Можно показать, что для предлагаемого метода: min{| wt |-(1п(ц/(и>,)) } = 0,

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

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

Общий алгоритм

Для оптимизации критерия будем использовать итерационный алгоритм метода Гаусса - Зейделя по двум группам переменных - коэффициентам регрессии (w1,...,wf>) и их обобщенным дисперсиям (г„...,/-р). Пусть (wlk),гт) - очередное приближение к точке минимума. Следующее приближение r(i+l) найдем из условия = arg min Q(rt), где

r(

Имеем

>T"=(H(*f>)2 + l)/(H + l). (22)

Если подставим выражения (22) в формулу (21), априорная плотность распределения оцениваемых параметров в предлагаемом методе будет иметь вид:

v(/(w) ос ехр(-((й+1)/(2ц)) 1п(ци^ +1)). (23)

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

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

Найдем очередное приближение w<ir4l) из условия

w(t+,Uargmin[X^1(^-Z"1^(«/))7(2o)+(l/2)WrR(t+1,W]. (24)

Очевидно, что

где s(.xi({a/)>—'xp(.<°j))T ■

Вычислительная сложность метода есть lx0(N*) + 0(N2p + pN).

Алгоритм восстановления параметров в задаче анализа продолжительности жизни

Найдем очередное приближение w(h" из условия

w'"" = argmin((l/2) ^К)2/^' -ifj.tf w«ptf w))). (25) ff _ __

Введем обозначения wf = wjjr™ и xtj = •Jrf'x^. Тогда

^ = argmin((l/2)X',(^)2 "Zl»^"-'"^«^*)))- (26)

w

Пусть = = = Xw,

¿(w),i'(w) и ¿(f|), ¿ (f|) обозначают градиент и Гессиан функции Z,(w) в точках w и fi. Разложение функции Цw) в ряд Тейлора с отбрасываем членов выше второго порядка в точке w имеет вид

¿(те) Я £(те) + (те - те)г ¿(те) + (те - те)1" ¿(те) (те - те)/2

= Д*)+(х*--фгг;сл)+(хл-пУГСл)(х»-л)/2, (27)

где г[ = Хте.

Краткая запись (27): ¿(те)« (1/2)(г(т|) - Хте)7 £(Л)(г(тО - Хте) + С(т{, те), где г(т|") = Л-£(т|Т ¿(л), и С(г),те) не зависит от те. Матрица вторых производных IОт)- это полная матрица, для вычисления которой потребуется 0(М2) операций. Для того чтобы ускорить алгоритм, заменим ее диагональной матрицей с диагональными элементами матрицы ¿"(тО и обозначаем ¡-й диагональный элемент матрицы Ь Сп) как у(т1), . Показательным является то, что такая замена работает, так как оптимальная точка остается неподвижной и недиагональные элементы £"(¥{) малы по сравнению с диагональными элементами. Введем специальные обозначения для первой и второй частной производной ¿(те) по одной компоненте вектора

ц, = 81/дц, = 5, -ехр(л,)£(ег (1/Х^.ехр(пу));С; ={кие = 1,...,^; а,, = дгЬ/5л,2 = ехр(п,)^<е(. (1/£^ехр(лу)) -ехр(2п, О/^^ехр^))2).

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

Шаг 1. Задаемся начальными приближениями те = те и вычисляем т)" = Хте. Шаг2. Вычисляем у(т]), = а„;г(Т1), = г(

Шаг 3. Минимизируем следующий критерий ^ = ащгшпА/(те), где

Л/(те) = ^("у(т1),(г(л),-¿Гте)2+Х,:,Л,2 -

Можно показать, что очередное приближение к точке минимума для параметров может быть найдено по формуле аМ/дй^ = О, откуда следует, что

** =<Е>(Л),г(т|),

Шаг 4. Принимаем те = те и т)" = Хте.

Шаг 5. Повторяем шаги 2-4, пока изменяется й .

Пусть /, - число итераций алгоритма восстановления параметров те и /2- число итераций задачи на шаге 3. Тогда вычислительная сложность задачи анализа продолжительности жизни есть Iх(О(Л0+/,х (О(рЫ) +/2хО(Л'х(р-1)))).

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

Найдем очередное приближение те'**" из условия

(28) критерий

(29)

Для решения этой задачи будем использовать методы квадратичного программирования. Если число объектов мало, используем алгоритм последовательной ми-нимальнои оптимизации (ЭМО). Если число объектов велико, то решать двойствен-

18, > 0-У0,Л е 5 г те7 (х, - х,) > 1-5,;/,/ = 1,.., М

С учетом переобозначений " = И, ^ = и =

обучения принимает вид

(5, > 0;У(/,у)е5.• тег(х, -х,) > 1 -8,;/,у =

ную задачу не эффективно, и тогда будем решать прямую задачу. Для решения прямой задачи воспользуемся методом Ньютона. Тогда в каждом итерации выполняются следующие вычисления w(t+l) =ww-#~lg, где Я- матрица Гесса целевой функции и g градиент целевой функции. При этом нет необходимости вычислять обратную матрицу Гесса, можно вычислить только вектор % = Н'1 g, являющийся решением системы линейных уравнений Н% = g. Систему решаем приближенно методом сопряженных градиентов.

Вычислительная сложность задачи порядковой регрессии -

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

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

[i;,5!" = o, (30)

rm = ((/^^^^Zr-.W^K'^^+V^j/d + 1/ц).

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

/ х (0((АГ +1)3) + CKN1 р)). Легко видеть, что оценка целевой переменной имеет вид:

= + (31)

В пятой главе описывается экспериментальное исследование предложенного встроенного метода отбора признаков.

Для сравнительного тестирования предложенного алгоритма мы выбрали для каждой задачи самые эффективные из существующих на данный момент встроенных методов. Эксперименты проводились на модельных и реальных данных. Реальные данные взяты из общедоступных источников. Модельные данные имеют следующие свойства: число признаков гораздо больше числа объектов обучения и между признаками имеет место корреляция. Значения структурных параметров р подбирались с помощью процедуры скользящего контроля (CV-10).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Исследованы свойства оценок, получаемых с помощью предложенной вероятностной модели.

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

1. Нгуен Т.Ч., Красоткина О.В., Мотгль В.В. Модель линейной регрессии с регулируемой селективностью для отбора признаков в задаче оценивания зависимостей по экперкментальным данным // Известия ТулГУ. Технические науки. 2012. Вып. 1. С. 138—146.

2. Нгуен Т.Ч., Красоткина О.В., Поленова Е.А., Моттль В.В. Байесовский поход к оцениванию факторов, влияющих на положение сайта в результатах поискового запроса // Известия ТулГУ. Технические науки. 2013. Вып. 2. С. 168177.

3. Нгуен Т.Ч., Красоткина О.В., Попов В.А., Мотгль В.В. Байесовский поход к оцениванию факторов риска в анализе продолжительности жизни // Известия ТулГУ. Технические науки. 2013. Вып. 2. С. 187-196.

4. Нгуен Т.Ч., Красоткина О.В., Ежова Е.О., Мотгль В.В.. Селективное комбинирование потенциальных функций при многомодальном восстановлении регрессионной зависимости //Доклады 15-й Всероссийской конференции «Математические методы распознавания образов». М.: МАКС Пресс, 2011. С. 138-141.

5. Нгуен Т.Ч., Красоткина О.В., Поленова Е.А., Моттль В.В. Исследование модели порядковой регрессии с регулируемой селективностью в задаче оценивания позиции сайта в результатах поискового запроса // Доклады 9-й конференции «Интеллектуализация обработки информации». М.: Торус Пресс, 2012. С. 122-125.

6: Нгуен Т.Ч., Красоткина О.В., Попов В.А., Мотгль В.В. Исследование регрессионной модели Кокса с регулируемой селективностью в задаче анализа продолжительности жизни // Доклады 9-й конференции «Интеллектуализация обработки информации». М.: Торус Пресс, 2012. С. 633-636.

7. Нгуен Т.Ч., Поленова Е.А., Красоткина О.В., Мотгль В.В. Байесовский подход к оцениванию факторов, влияющих на положение сайта в результатах поискового запроса // Доклады 16-й Всероссийской конференции «Математические методы распознавания образов». М.: МАКС Пресс, 2013. С.92-92

Изд. лиц.ЛР № 020300 от 12.02.97. Подписано в печать 11.11.2013.

Формат бумаги 60 х 84 . Бумага офсетная.

Усл. печ. л. 1,1. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 092 Тульский государственный университет 300012, г. Тула, просп. Ленина, 92 Отпечатано в Издательстве ТулГУ 300012, г. Тула, пр. Ленина, 95

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

5

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

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

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

6

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

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

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

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

Задача 2. Создание методов комбинирования модальностей существенно разной природы в единой системе.

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

Задача 5. Исследование свойств оценок параметров, получаемых с помощью предложенной селективной иерархической вероятностной модели: селективности, несмещенности, состоятельности (построение оракульных неравенств), способности к отбору коррелированных регрессоров, непрерывность исследование верхней границы риска оценок.

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

7

продолжительности жизни и многомодального восстановления регрессионной зависимости.

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

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

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

Решение представленных задачи осуществляется в диссертации в следующих главах.

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

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

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

8

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

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

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

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

самые эффективные из существующих на данный момент встроенных методов. Эксперименты проводились на модельных и реальных данных.

1 ПРОБЛЕМА ПЕРЕОБУЧЕНИЯ ПРИ ВОССТАНОВЛЕНИИ ЗАВИСИМОСТЕЙ ПО ЭМПИРИЧЕСКИМ ДАННЫМ И ОСНОВНЫЕ ЗАДАЧИ ИССЛЕДОВАНИЯ

1.1 Задача восстановления зависимостей по эмпирическим данным

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

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

объектов, называемого обучающей совокупностью С1* ^ где ТУ -

число наблюдений. Естественно, что компьютер не может непосредственно воспринимать физические объекты. Поэтому всегда необходима некоторая формальная переменная х(со):0—>Х, выступающая как посредник между компьютером и природой, называемая признаком. Наиболее простым предположением является понимание признаковых представлений объектов как последовательностей действительных чисел х(со)=(.х, (оэ),..., (со)) е Мр,

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

х(со)=(лс,(т),...,*р(а>)) обозначением х=(х1,...,л:/,).

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

cd -> Q \ Q*. Предметом рассмотрения данной работы является случай, когда выходная переменная является действительнозначной j>(co):Q—и

исходная задача представляет собой задачу оценивания регрессионной зависимости. Если _у(со) принимает значения из конечного множества, то

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

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

1.2 Проблема переобучения

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

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

Эмпирическим риском называется средняя ошибка алгоритма на обучающей выборке. Метод минимизации эмпирического риска (empirical risk minimization, ERM) наиболее часто применяется для построения алгоритмов обучения. Он состоит в том, чтобы в рамках заданной модели выбрать алгоритм, имеющий минимальное значение средней ошибки на заданной обучающей выборке. С переобучением метода ERM связано три утверждения, которые на первый взгляд могут показаться парадоксальными.

Утверждение 1. Минимизация эмпирического риска не гарантирует, что вероятность ошибки на тестовых данных будет мала. Легко строится контрпример — абсурдный алгоритм обучения, который минимизирует эмпирический риск до нуля, но при этом абсолютно не способен обучаться. Алгоритм состоит в следующем. Получив обучающую выборку, он запоминает её и строит функцию, которая сравнивает предъявляемый объект с запомненными обучающими объектами. Если предъявляемый объект в точности совпадает с одним из обучающих, то эта функция выдаёт для него запомненный правильный ответ. Иначе выдаётся произвольный ответ (например, случайный или всегда один и тот же). Эмпирический риск алгоритма равен нулю, однако он не восстанавливает зависимость и не обладает никакой способностью к обобщению. Вывод: для успешного обучения необходимо не только запоминать, но и обобщать.

Утверждение 2. Переобучение появляется именно вследствие минимизации эмпирического риска. Пусть задано конечное множество из Б алгоритмов, которые допускают ошибки независимо и с одинаковой вероятностью. Число ошибок любого из этих алгоритмов на заданной обучающей выборке подчиняется одному и тому же биномиальному распределению. Минимум эмпирического риска — это случайная величина, равная минимуму из Б независимых одинаково распределённых биномиальных случайных величин. Её ожидаемое значение уменьшается с ростом Б. Соответственно, с ростом Б увеличивается переобученность — разность вероятности ошибки и частоты ошибок на обучении.

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

Явление переобучения можно проиллюстрировать примером задачи восстановления полинома на рис. 1.1. На левом рисунке порядок полинома равен 1, модель слишком проста и имеет мало переменных, поэтому

13

происходит недообучение. На правом рисунке, уровень полинома равен 9, модель слишком сложна и имеет много параметров, поэтому происходит переобучение. На среднем рисунке, порядок полинома равен 3, модель близка к истинной зависимости. Истинная зависимость показана сплошной линией, пунктирная линия соответствует восстановительной зависимости.

Рисунок 1.1 Явление недообучения (слева), и переобучение (справа) и идеальная зависимость (в середине)

1.3 Байесовский подход к оцениванию зависимостей

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

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

• Теоретические результаты работают на практике при больших выборках, т.е. при п» 1.

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

• Основным методом статистического оценивания является метод максимального правдоподобия (Фишер, 1930-е гг.)

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

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

�