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

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

Гультяева Татьяна Александровна

ИССЛЕДОВАНИЕ ПОДХОДА К РЕШЕНИЮ ЗАДАЧИ КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПРЕДСТАВЛЕННЫХ СКРЫТЫМИ МАРКОВСКИМИ МОДЕЛЯМИ, С ИСПОЛЬЗОВАНИЕМ ИНИЦИИРОВАННЫХ ЭТИМИ МОДЕЛЯМИ

ПРИЗНАКОВ

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

АВТОРЕФЕРАТ

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

2 8 НОЯ 2013

Новосибирск - 2013

005540878

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

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

Попов Александр Александрович

Официальные оппоненты: Загоруйко Николай Григорьевич

доктор технических наук, профессор Федеральное государственное бюджетное учреждение науки «Институт математики им. С.Л. Соболева» Сибирского отделения Российской академии наук, заведующий лабораторией анализа данных;

Фаддеенков Андрей Владимирович кандидат технических наук, доцент Федеральное государственное бюджетное образовательное учреждении высшего профессионального образования «Новосибирский государственный технический университет», доцент кафедры теории рынка

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

зовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Защита состоится « 26 » декабря 2013 г. в 1400 часов на заседании диссертационного совета Д 212.173.06 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет» по адресу: 630073, Новосибирск, пр. К. Маркса, 20.

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

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

Ученый секретарь

диссертационного совета Мі^-' Чубич Владимир Михайлович

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

Актуальность темы исследований. Распознавание образов является одной из задач анализа данных, лежащего в основе любых научных методов. Один из подходов к классификации образов состоит в построении математической модели, описывающей эти образы. В диссертационной работе рассматриваются скрытые марковские модели (СММ), относящиеся к классу статистических моделей. Особенностью СММ является то, что они учитывают внутреннюю структуру последовательностей, которые регистрируются при наблюдении за процессами или объектами. СММ, собственно как метод, был разработан в середине бОх-конце 70х годов 20 века независимо отечественными (Вин-цюк Т. К., Ковалевский В.А.) и зарубежными (Баум JI.E, Петри Т.) исследователями. Значительный вклад в развитие как теории, так и практического использования СММ внесли такие отечественные ученые, как Моттль В.В. и Мучник И.Б., Воробьев С.А., Борисов A.B. Зарубежные исследования таких ученых, как Рабинер Л.Р., Нефиан A.B., Самариа Ф., Каппе О., более ориентированные на прикладные задачи, также внесли свой вклад в развитие СММ. По своей природе СММ позволяют учитывать как пространственные, так и временные характеристики последовательностей. Поэтому эти модели получили широкое применение в различных прикладных задачах, таких как распознавание речи (см., например, работы авторов Рабинер J1.P., Леггетгер С.Ж., Жанг Б.Х., Галес М„ Хуанг К.Д., Гефке Д.А., Иконин С.Ю.), изображений (Нефиан A.B., Самариа Ф., Плотц Т., Бунке X., Сандерсон К., Ли Дж.), видеопоследовательностей (Кошал А., Лиу К., Сайд У.), задачи биоинформатики (Коски Т., Барбю B.C., Бирней Е., Дурбин Р.), задачи геофизики (Грант Р.), эконометриче-ские задачи (Мамон P.C., Грегоир С., Бхар Р.), задачи сферы телекоммуникаций (Миллер Б.М., Антон-Харо С., Фоноллоза Ж.А.), исследование динамических систем (Фрейзер A.M.), стегоанализ (Сидоров М.А.) и т. д.

Классификация последовательностей с использованием СММ при условии того, что конкурирующие модели достаточно хорошо различимы друг от друга (по вероятности), как правило, не вызывает затруднений. При этом традиционно используется подход (ТП - традиционный подход), основывающийся на критерии правдоподобия. Однако в случае, когда эти модели оказываются по какой-либо причине близкими, результаты классификации становятся малоинформативными, т. е. принадлежность некоторой последовательности к любому классу является равновероятной. Существует два подхода к решению этой задачи. В первом подходе используются методы, которые ориентированы на то, чтобы точнее описать исследуемый объект или процесс: либо изменяют структуру используемых моделей (см., например, работы таких авторов, как Александров В., Нил P.M.), либо используют иные методы оценки параметров моделей (Вальдер С.Ж., Икбал С., Жоу Г.Д.), либо же комбинируют эти два подхода (Лиу С., Чатзис П.С.). При использовании второго подхода появляется возможность видоизменять решающее правило классификации, получая некую информацию от моделей и применяя ее для проведения классификации (см., например, работы таких авторов, как Солера-Урена Р., Линг Ч., Аран О.). Этот под-

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

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

Для достижения поставленной цели предусмотрено решение следующих

задач:

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

- исследование поведения классификаторов, использующих пространство признаков в виде производных от логарифма функции правдоподобия по параметрам СММ в условиях, когда последовательности искажены помехами или при структурной неопределенности;

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

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

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

Научная новизна диссертационной работы заключается в том, что были впервые:

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

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

- проведен сравнительный анализ ИП и ТП к решению задачи классификации порожденных скрытыми марковскими моделями последовательностей, искаженных помехами;

- проведен сравнительный анализ ИП и ТП к решению задачи классификации порожденных скрытыми марковскими моделями последовательностей в условиях неточных знаний о структуре этих моделей;

- выявлены особенности, присущие классифицируемым последовательностям, при которых использование ИП предпочтительнее ТП.

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

- результаты исследования ИП в условиях действия помех различной интенсивности и природы;

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

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

- выявленные особенности последовательностей, при которых использование ИП предпочтительнее ТП.

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

- корректным применением аналитического аппарата математического анализа, теории вероятностей и математической статистики для исследования свойств построенных моделей;

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

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

Практическая ценность результатов заключается в том, что:

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

- проведены исследования, которые выявили особенности, присущие анализируемым последовательностям, при которых использование ИП дает выигрыш в сравнении с ТП;

- разработана программная система, позволяющая классифицировать последовательности, применяя ИП и ТП.

Апробация работы. Основные результаты исследований, проведенных автором, докладывались и обсуждались на: Российской НТК «Информатика и проблемы телекоммуникаций» (Новосибирск, 2010, 2011, 2012); Пятнадцатой всероссийской конференции «Математические методы распознавания образов-15» (Петрозаводск, 2011); Международной заочной научной конференции «Технические науки: проблемы и перспективы» (Санкт-Петербург, 2011); Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2011); Четвертой международной конференции по распознавания образов и искусственному интеллекту «РКеМ1-2011» (Москва 2011); XI международной НТК «Актуальные проблемы электронного приборостроения АПЭП-2012» (Новосибирск, 2012); Всероссийской конференции с международным участием «Информационные и математические технологии в науке, технике, медицине» (Томск, 2012).

Реализация полученных результатов. Результаты диссертационных исследований использованы при разработке автономной системы электроснабжения летательных аппаратов в рамках НИОКР с предприятием ОАО «АКБ Якорь», г. Москва, что подтверждено соответствующей справкой об использовании результатов диссертационной работы. Работа выполнялась при финансовой поддержке: по гранту № 2.1.1/2932 «Оптимизационные методы построения логико-вероятностных моделей в задачах многомерного статистического анализа» федеральной целевой программы «Развитие научного потенциала высшей школы» (2009-2010 гг.); по гранту № 2.1.1/11599 «Методы устойчивой идентификации в задачах построения зависимостей и классификаций по неоднородным экспериментальным данным в условиях параметрической и структурной неопределенности» федеральной целевой программы (2011г.); стипендии Правительства Российской Федерации на 2011-2012 учебный год согласно приказу № 154 от 28.02.2012.

Публикации. Основные научные результаты диссертации опубликованы в 18 печатных работах, из них 5 - в изданиях, входящих в Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёной степени доктора и кандидата наук, 4 - в сборниках научных работ, 9 - в материалах конференций.

Структура работы. Диссертация состоит из введения, 5 глав, заключения, 6 приложений и списка использованных источников (212 наименований). Основной текст работы изложен на 242 страницах, включает 7 таблиц и 93 рисунка.

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

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

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

В п. 1.1 осуществляется введение в теорию СММ. Такие модели являются частным случаем скрытого марковского процесса, представляющего собой двухкомпонентный случайный процесс со скрытой компонентой (марковская цепь с конечным множеством состояний) и наблюдаемой компонентой. СММ задают следующие параметры: _

1) вектор вероятностей начальных состояний П = {-т;}, г = 1, /V, где щ = = , множество скрытых состояний 5 = >5дгЬ N - количество скрытых состояний в модели, С[\ - состояние в момент ? = 1 из последовательности О, являющейся реализацией скрытого процесса;

2) матрица вероятностей переходов А={а,у}, г, у = , где ау = р|<7г = Sj \cfo-i =, ¿7, - состояние в момент Г = 2,7", Т - длина последовательности;

3) функции условной плотности распределений наблюдений В = \bt (/)}, где bt(t) - это условные плотности вероятностей P{ot\qt =i,}, оi б Е - наблюдение, фиксируемое в момент t = l,T, из последовательности О, являющейся реализацией наблюдаемого процесса. В работе рассматривается случай, когда условные плотности распределений наблюдений являются смесями нормальных распределений:

т=1

где Г(ш - это вес т -ой компоненты смеси в описании i -ого скрытого состояния,

М - количество компонент смеси, параметры fiim и afm являются, соответственно, математическим ожиданием и дисперсией.

В п. 1.2 рассматривается вопрос обучения СММ по имеющимся последовательностям исследуемого процесса или объекта. В работе был использован алгоритм обучения, в общем случае называемый ЕМ (ЕМ - Expectation Maximization; максимизация ожидания) или, применительно к СММ, алгоритмом Баума-Велша. Чтобы решить проблему того, что результаты умножений различных вероятностей, используемых для оценивания параметров СММ, стремятся к нулю, вводится масштабный коэффициент.

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

В п. 1.4 рассматривается ТП к классификации последовательностей.

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

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

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

В п. 2.2 описывается ИП к решению задачи классификации последовательностей. Для каждой обучающей последовательности О формируется характеристический вектор вида: V =[z (О, А{) Z{0,Aq)f. где Z(0,Ak) - вектор первых производных от логарифма функции правдоподобия последовательности О по параметрам моделей Як, it = 1,2. Аналогичным образом вычисляется характеристический вектор для тестовой последовательности. Далее в полученном пространстве признаков решается задача классификации.

В п. 2.3 и п. 2.4 описываются применяемый в работе классификатор к ближайших соседей (kNN - k Nearest Neighbor) и классификатор, основанный на методе опорных векторов (SVM - Support Vector Machines).

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

В п. 2.6 приводятся формулы для вычисления первых производных от логарифма функции правдоподобия по различным параметрам СММ.

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

В п. 2.8 приводятся результаты исследования возможности проведения классификации в пространстве первых производных по параметрам моделей для ИП в случае, если две конкурирующие модели имеют следующие параметры: = ^ +с1А при ¡=Ш и Д7+1= Ат+1 ПРИ ' =1,^-1. Ат =Ат~ЛЛ' = т = Ш. Таким образом, параметры , й?1", йа определяют степень близости между моделями. На рисунке 1 приведены зависимости среднего процента верно классифицированных последовательностей (СПВКП) для ситуации, когда модели отличались друг от друга только в матрицах переходных вероятностей и использовался ИП с БУМ классификатором*. Данное исследование показало, что приемлемый результат по точности классификации достигается только в том случае, если используется пространство производных по тем параметрам, по которым при моделировании было заложено отличие между двумя конкурирующими моделями. При этом при увеличении длины последовательностей результаты классификаторов приближаются к результатам ТП на основе отношения функций правдоподобия. Таким образом, проведенные вычислительные эксперименты подтверждают выдвинутое предположение о том, что возможно использовать ИП с М^Ш и БУМ классификаторами для классификации последовательностей в пространстве инициированных признаков - первых производных от логарифма функции правдоподобия по параметрам модели. Кроме того было установлено, что результаты классификации, полученные с использованием БУМ классификатора в рассматриваемом подходе, несколько лучше результатов, полученных с использованием классификатора

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

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

Рисунок 1 - Зависимость СПВКП от длины Т, аА= 0.1

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

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

В п. 3.2 приводятся результаты исследований в случае, когда вероятности появления наблюдений описываются одним распределением. При распределении аддитивной помехи, подчиняющейся нормальному закону с постоянными параметрами распределения, классификатор kNN в пространстве ПА не дает улучшений в сравнении с ТП. Это связано с тем, что у шума и исходной последовательности вероятности появления наблюдений имеют нормальное распределение. Поэтому при проверке сложной гипотезы о согласии эмпирического распределения частот появления наблюдений в скрытых состояниях с нормальным распределением с параметрами, оцененными по алгоритму Баум-Велша, наблюдался высокий достигнутый уровень значимости. Кроме того отметим, что с увеличением уровня шума модели становятся плохо различимы, т. к. расстояние между ними стремится к нулю из-за того, что распределения наблюдений в скрытых состояниях стремятся к одному и тому же распределению (распределению ошибки) для двух моделей. В случае распределения ошибки по закону Коши и при проверке сложной гипотезы о согласии эмпирических распределений частот появления наблюдений в скрытых состояниях с нормальным распределением, было установлено, что небольшое увеличение уровня шума приводит к тому, что нормальное распределение плохо описывает эти эмпирические распределения частот. При этом до уровня шума ¿у <0.3 модели остаются еще достаточно далеки друг от друга по расстоянию, и ИП показывает на этом интервале лучшую классификацию, чем традиционный. Таким образом, ИП позволяет повысить процент верно классифицированных последовательностей в сравнении с ТП в случае, когда расстояние между моделями еще достаточно велико, но согласие эмпирического распределения частот появления наблюдений в скрытых состояниях с нормальным распределением не достигается. На рисунке 2 приведены зависимости СПВКП от уровня шума для случая, когда помеха носит аддитивный характер с изменяемыми параметрами распределения, которые зависят от номера скрытого состояния модели: ех >- С(0,0.1), е2 >■ С(5,0.1), ¿3 >- С(10,0.1). Заметно существенное преимущество ИП перед ТП. При вероятностной помехе наблюдаются аналогичные результаты. В целом можно сделать вывод, что для близких по параметрам моделей с количеством компонент смеси

ОД 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

Рисунок 2 - Зависимость СПВКП от уровня шума О). dA =0.1

М = 1 при использовании классификатора кШ удается повысить процент верно классифицированных последовательностей в случае, если эти последовательности искажены помехой, имеющей распределение Коши. При этом прирост процентов верной классификации в сравнении с ТП может достигать 40%.

В п. 3.3 приводятся результаты исследований в случае, когда у СММ вероятности появления наблюдений описываются смесями распределений с количеством компонент смеси М = 3. На ___ _______

рисунке 3 приведены зависимости СПВКП от уровня шума для случая, когда помеха носит аддитивный характер с постоянными параметрами распределения: е >- С(0,0.1). Заметно существенное преимущество ИП перед ТП. Аналогичная картина наблюдается и при различии между моделями, заложенными в ¿^ и (Iа. Также в результате исследований было установлено, что ТП обладает наибольшим значением разброса СПВКП среди рассматриваемых методов классификации. Наименьшим разбросом усредненного процента обладает ИП, использующий БУМ. Кроме того, почти всегда наблюдается ситуация, когда разброс усредненного процента для БУМ меньше, чем разброс усредненного процента для кШ. При вероятностной помехе наблюдаются результаты аналогичные тем, что были получены при аддитивной помехе. Результаты сравнения поведения классификаторов на задаче двухклассовой классификации в целом остаются справедливыми и для многоклассового случая.

В п. 3.4 исследуются поведения классификаторов в условиях, когда помеха, смоделированная по вероятностной схеме, имеет различные законы распределения: Лапласа; минимального значения; двойного экспоненциального; логистического; Эрланга или же функцию вероятности распределения Пуассона. По результатам исследований, можно выдвинуть гипотезу о том, что ТП проигрывает в сравнении с ИП в случае, если последовательности искажены помехами с различным типом распределений: с тяжелыми хвостами, симметричными и асимметричными. Процент верно классифицированных последовательностей удается повысить всегда в сравнении с ТП, правильно выбрав пространство для классификации (в среднем на 10%).

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

В п. 4.1 приводятся результаты исследований, когда используются различные законы распределений появления наблюдений. Рассматриваются различные случая отклонения от классического предположения о виде функции условной плотности распределений наблюдений (см. формулу (1)). На рисун-

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 Рисунок 3 - Зависимость СПВКП от уровня шума со. ¿А =0.1

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

Ъ^(?) = /с(о,;0Д01), Ь*2 (г) = /с (о,;0,0.01 + «/), Ь2(?) = /с(о,;0.05,0.01),

ЫО = /с(0г-О.О5,О.О1), где /с - функция плотности вероятности распределения Коши. Оценивание параметров моделей проводилось для СММ с количеством скрытых состояний и компонент смеси еат м1еагп = 3 • Видно, что чем дальше модели раздвинуты друг от друга за счет увеличения значения параметра (1, тем выше процент верной классификации в используемых пространствах. Кроме того, при с1> 0.1 преимущество использования ИП теряется, т. к. модель смесей, которая используется при оценивании параметров, достаточно хорошо описала выбранный при моделировании закон распределения. После оценивания параметров можно было увидеть, что основное различие между двумя моделями оказалось сосредоточено в матрице переходных вероятностей, поэтому при классификации в пространстве ПА и в пространстве ПАМД наблюдается заметный выигрыш в сравнении ТП.

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

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

классов \ и Л} моделировались по следующим формулам: о^ =8т(0.1?) + е,

о/2=(1 + </Атр)5т((0.1 + Лет)* + ^) + е, е>-ЛГ(0,0.1), г = <1Атр, <1т, ^

- параметры, отвечающие за близость последовательностей. На рисунке 5 приведены зависимости СПВКП с использованием ТП и ИП с классификатором

50 І...................4-.............-.....I.................4-----------І------------------1 6

0.00 0,02 0,04 0,06 0,08 0,10 Рисунок 4 - Зависимость СПВКП от

значения параметра сі, Т = 100

SVM от количества скрытых состояний Niearn и компонент смеси М

используемых на этапе преимущество во всех пространствах ИП в сравнении с ТП. Также проводились исследования при варьировании параметров близости последовательностей с1Лтр и ¿У, с получением аналогичных результатов.

В п. 4.3 исследуется поведение классификаторов в условиях структурной неопределенности. Исследования проводились для двухклассового случая при

обучения

100 %т—

learn'

СММ. Наблюдается существенное

2 3 4-ЦГ 5 6

^ learn learn Рисунок 5 - Зависимость СПВКП от значения параметров

^learn и Miearn. Г = 100 для SVM, сГ =0.01

условии, что исследователь не обладает информацией об истинном значении параметров N и М, а конкурирующие модели близки друг к другу по элементам матрицы А. На рисунке 6 приведены

зависимости СПВКП от параметра близостей моделей й = йА при количестве скрытых состояний и компонент смеси, с которыми моделировались последовательности N = 4, М = 6 и при различных значениях АЦеагп = М¡еагп на этапах обучения и тестирования.

100 95 90 85 80 75 70 65 60 55 50

0,0 ОД 0,2 0,3 0,4 0,5 б)

Рисунок 6 - Зависимость СПВКП от параметра близостей моделей d при ^learn = Miearn = 2 (а); Nlearn = мlearn = 6 (б)

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

SVM/IL jf; Щ Т

к Г\

І \ fill: / \ ltNN/Ш

I...........\> •! у

!■ II F '/>

4 SVM/ПАЫД

Е I

X г

/ ......^

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

В п. 5.1 рассматриваются различные методы выбора информативных признаков. Как было установлено в работе, выбор пространства признаков, которое используется при классификации с применением ИП, существенным образом влияет на эффективность работы классификаторов. Оценка информативности признаков делается прямым способом с использованием средней ошибки распознавания, получаемой в режиме скользящего экзамена и одним из косвенных способов, основанным на вычислении значения функции конкурентного сходства (FRiS - Function of Rival Similarity).

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

В п. 5.3 проводятся исследования на широко распространенных выборках данных: «Hill-Valley Dataset» и «Waveform Database». В качестве прикладной задачи рассматривается определение по сигналу электрического тока структуры схемы электрической цепи, с которой был снят этот сигнал. Во всех случаях показано преимущество использования ИП в оптимально выбранном пространстве признаков перед ТП.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Проведен сравнительный анализ ИП и основывающегося на критерии правдоподобия ТП к решению задачи классификации порожденных СММ последовательностей, искаженных помехами. При этом рассмотрены несколько вариантов распределений вероятностей появления помехи по непрерывным и дискретным законам. Установлено, что использование ИП позволят в ряде случаев повысить точность классификации на 30% в сравнении с ТП.

4. Проведен сравнительный анализ ИП и ТП к решению задачи классификации порожденных СММ последовательностей в условиях неточных знаний о

структуре этих моделей. А именно, рассмотрены различные законы распределений появления наблюдений, отличные от нормального. Установлено, что в этом случае использование ИП позволят повысить точность классификации на 45% в сравнении с ТП. Рассмотрена ситуация, когда процесс или объект, порождающий наблюдаемые последовательности, предположительно не имеет скрытых состояний. Установлено, что использование СММ для описания таких последовательностей и их классификации с помощью ИП позволят повысить точность классификации на 35% в сравнении с ТП. Рассмотрена ситуация, когда отсутствует априорная информация о количестве скрытых состояний и компонент смесей СММ. Установлено, что при заниженной оценке этих значений при использовании ИП можно повысить точность классификации на 40% в сравнении с ТП.

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

6. Выявлены особенности, присущие анализируемым последовательностям, при которых использование ИП предпочтительнее ТП. Эти особенности во многом определяют затрудненные условия применения ТП и связаны с близостью конкурирующих СММ, порождающих последовательности, и наличием различного рода искажений самих последовательностей.

7. Установлено, что разброс показателя точности классификации с использованием ТП выше, чем с использованием ИП в оптимально выбранном пространстве признаков.

8. ИП был применен для решения задачи классификации на ряде приводимых в литературе выборках, которые используются для оценки качества работы классификаторов. Установлено, что применяя ИП, удается повысить точность классификации в сравнении с результатами, приводимых другими исследователями для этих выборок. ИП был использован при разработке автономной системы электроснабжения летательных аппаратов в рамках НИОКР с предприятием ОАО «АКБ Якорь» г. Москва.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Научные публикации в изданиях, входящих в Перечень ведущих рецензируемых научных журналов и изданий:

1. Гультяева Т.А. Классификация последовательностей с использованием скрытых марковских моделей в условиях неточного задания их структуры / Т.А. Гультяева, A.A. Попов // Вестник ТГУ. Управление, вычислительная техника и информатика - Томск : Изд-во ТГУ, 2013. - № 3 (24). - С. 57-63.

2. Гультяева Т.А. Классификация смоделированных скрытыми марковскими моделями последовательностей в многоклассовом случае / Т.А. Гультяева, A.A. Попов // Научный вестник НГТУ. - Новосибирск : Изд-во НГТУ, 2013. -№3(52).-С. 40-45.

3. Гультяева Т.А. Классификация последовательностей, смоделированных скрытыми марковскими моделями при наличии аддитивного шума / Т.А. Гультяева, A.A. Попов // Научный вестник НГТУ. - Новосибирск : Изд-во НГТУ, 2012. - № 3 (48). - С. 17-24.

4. Гультяева Т.А. Классификация зашумленных последовательностей, порожденных близкими скрытыми марковскими моделями / Т.А. Гультяева, A.A. Попов // Научный вестник НГТУ. - Новосибирск : Изд-во НГТУ, 2011. -№3(44).-С. 3-16.

5. Gultyaeva Т.А. The Classification of Noisy Sequences Generated by Similar HMMs / T.A. Gultyaeva, A.A. Popov // PReMI 2011, LNCS. - Springer-Verlag Berlin Heidelberg, 2011. - Vol. 6744/2011. - P. 30-35. [Классификация зашумленных последовательностей, смоделированных близкими СММ].

Научные публикации в других изданиях:

6. Гультяева Т.А. Исследование поведения классификаторов при классификации смоделированных СММ последовательностей в условиях отклонения от классических предположений / Т.А. Гультяева, A.A. Попов // Информационные и математические технологии в науке, технике, медицине : материалы Все-рос. конф. с междунар. участием, Томск, 2012 г. - Томск : Изд-во ТПУ, 2012. -Ч. 1.-С. 49-51.

7. Гультяева Т.А. Классификация сигналов, представляющих собой суммарный ток, потребляемый в электрической цепи, при наличии шума и близких параметров нагрузок / Т.А. Гультяева, Д.Ю. Коротенко II Информатика и проблема телекоммуникаций: материалы российской науч.-технич. конф. - Новосибирск: Изд-во СибГУТИ, 2012. - Т. I. - С. 23-26

8. Гультяева Т.А. Применение скрытых марковских моделей, kNN и SVM для задачи классификации режимов системы электроснабжения / Т.А. Гультяева, A.A. Попов, Д.Ю. Коротенко // Актуальные проблемы электронного приборостроения. АПЭП 2012: материалы XI междунар. науч.-технич. конф. - Новосибирск : Изд-во НГТУ, 2012. - том 6 - С. 36-41.

9. Гультяева Т.А. Исследование возможностей применения алгоритма к-ближайших соседей и метода опорных векторов при классификации последовательностей, порожденных скрытыми марковскими моделям / Т.А. Гультяева, Д.Ю. Коротенко // Сборник Научных трудов НГТУ. - Новосибирск : Изд-во НГТУ, 2011. - № 3 (65). - С. 45-55.

10. Гультяева Т.А. Исследование возможностей применения алгоритма к-ближайших соседей и метода опорных векторов для классификации сигналов, порожденных скрытыми марковскими моделями / Т.А. Гультяева, Д.Ю. Коротенко // Наука. Технологии. Инновации - 2011 : материалы Всерос. науч. конф. молодых ученых. - Новосибирск : Изд-во НГТУ, 2011. - Ч. 1. - С. 242-246.

11. Гультяева Т.А. Классификация последовательностей, подверженных действию помех с характеристиками, зависящими от скрытых состояний / Т.А. Гультяева, A.A. Попов // Сборник Научных трудов НГТУ. - Новосибирск : Изд-во НГТУ, 2011. - № 1 (63). - С. 59-68.

12. Гультяева Т.А. Классификация последовательностей, порожденных близкими скрытыми марковскими моделями, при наличии шума / Т.А. Гультяева, A.A. Попов // Технические науки: проблемы и перспективы : материалы ме-ждунар. заоч. науч. конф. - Санкт-Петербург : Изд-во Реноме, 2011. - № 1. -С. 37-41.

13. Гультяева Т.А. Классификация последовательностей, порожденных близкими скрытыми марковскими моделями, при наличии шума, распределенного по закону Коши / Т.А. Гультяева, A.A. Попов // Информатика и проблема телекоммуникаций: материалы российской науч.-технич. конф. - Новосибирск: Изд-во СибГУТИ, 2011. - Т. I. - С. 60-63.

14. Гультяева Т.А. Классификация последовательностей, порождённых скрытыми марковскими моделями, при наличии шума / Т.А. Гультяева, A.A. Попов // Математические методы распознавания образов-15 : материалы всеросс. конф. - Москва: Изд-во МАКС Пресс, 2011. - С. 211-214.

15. Гультяева Т.А. Построение гибридной модели для распознавания цифровых сигналов, основанной на комбинации скрытых марковских моделей и машин опорных векторов / Т.А. Гультяева, Д.Ю. Коротенко// Информатика и проблема телекоммуникаций: материалы российской науч.-технич. конф. - Новосибирск: Изд-во СибГУТИ, 2011. - Т. I. - С. 76-79.

16. Гультяева Т.А. Вычисление первых производных от логарифма функции правдоподобия для скрытых марковских моделей / Т.А. Гультяева // Сборник Научных трудов НГТУ. - Новосибирск : Изд-во НГТУ, 2010. - № 2 (60). -С. 39-46.

17. Гультяева Т.А. Особенности вычисления первых производных от логарифма функции правдоподобия для скрытых марковских моделей при длинных сигналах / Т.А. Гультяева // Сборник Научных трудов НГТУ. - Новосибирск : Изд-во НГТУ 2010. - № 2 (60). - С. 47-52.

18. Гультяева, Т.А. Повышение классификационных свойств скрытых марсковских моделей / Т.А. Гультяева // Информатика и проблема телекоммуникаций: материалы российской науч.-технич. конф. - Новосибирск: Изд-во СибГУТИ, 2010. - Т. I. - С.52-54.

Отпечатано в типографии Новосибирского государственного технического университета 630073, г. Новосибирск, пр. К. Маркса, 20 Тел./факс (383) 346-08-57 Формат 60 х 84/16. Объем 1 п.л. Тираж 110 экз. Заказ 1486. Подписано в печать 18.11.2013 г.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский государственный технический университет»

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

04201454401

Гультяева Татьяна Александровна

ИССЛЕДОВАНИЕ ПОДХОДА К РЕШЕНИЮ ЗАДАЧИ КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ПРЕДСТАВЛЕННЫХ СКРЫТЫМИ МАРКОВСКИМИ МОДЕЛЯМИ, С ИСПОЛЬЗОВАНИЕМ ИНИЦИИРОВАННЫХ ЭТИМИ МОДЕЛЯМИ ПРИЗНАКОВ

05.13.17 - Теоретические основы информатики

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: Попов А.А.

Новосибирск - 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................................................................6

ГЛАВА 1 ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ.......................................14

1.1 Введение в теорию СММ....................................................................................14

1.2 Обучение СММ....................................................................................................18

1.2.1 Алгоритм прямого-обратного прохода................................................21

1.2.2 Алгоритм Баум-Велша...........................................................................24

1.2.3 Масштабирование..................................................................................29

1.3 Моделирование последовательностей..............................................................33

1.4 Классификация последовательностей...............................................................36

1.5 Исторический обзор............................................................................................39

1.6 Выводы.................................................................................................................45

ГЛАВА 2 ЗАДАЧА КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.........47

2.1 Постановка задачи классификации последовательностей..............................47

2.2 Исследуемый подход к решению задачи классификации последовательностей..............................................................................................................................48

2.3 Метод ближайших соседей.................................................................................50

2.4 Классификатор, основанный на методе опорных векторов............................52

2.4.1 Машины опорных векторов..................................................................52

2.4.2 Размерность Вапника-Червоненкиса и минимизация структурного риска.................................................................................................................54

2.4.3 Построение ЭУМ классификатора.......................................................55

2.4.3.1 Случай линейно разделимой выборки..................................55

2.4.3.2 Случай линейно неразделимой выборка..............................59

2.4.4 Выбор гиперпараметров алгоритма 8УМ............................................62

2.5 Многоклассовая классификация........................................................................63

2.6 Вычисление первых производных от логарифма функции правдоподобия для СММ.....................................................................................................................65

2.7 Особенности вычисления первых производных от логарифма функции правдоподобия для СММ при длинных последовательностях............................68

2.8 Исследование возможности проведения классификации в пространстве первых производных.......................................................................................................70

2.9 Выводы.................................................................................................................81

ГЛАВА 3 КЛАССИФИКАЦИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В УСЛОВИЯХ ДЕЙСТВИЯ ПОМЕХ РАЗЛИЧНОЙ ИНТЕНСИВНОСТИ И ПРИРОДЫ..........82

3.1 Используемые модели помех, действующих на последовательности...........82

3.2 Исследования для моделей, в которых вероятности появления наблюдений описываются одним распределением......................................................................85

3.2.1 Аддитивная помеха с постоянными параметрами распределения ... 85

3.2.2 Аддитивная помеха с изменяемыми параметрами распределения... 92

3.2.3 Вероятностная помеха с постоянными параметрами распределения .....................................................................................................................95

3.2.4 Вероятностная помеха с изменяемыми параметрами распределения.....................................................................................................................98

3.3 Исследования для моделей, в которых вероятности появления наблюдений описываются смесями распределений..................................................................102

3.3.1 Аддитивная помеха с постоянными параметрами распределения.................................................................................................................. 103

3.3.2 Аддитивная помеха с изменяемыми параметрами...........................112

3.3.3 Вероятностная помеха с постоянными параметрами распределения ...................................................................................................................117

3.3.4 Вероятностная помеха с изменяемыми параметрами распределения...................................................................................................................122

3.4 Помехи, распределенные по различным законам..........................................127

3.5 Выводы...............................................................................................................134

ГЛАВА 4 ПОВЕДЕНИЕ КЛАССИФИКАТОРОВ В УСЛОВИЯХ ОТКЛОНЕНИЯ ОТ ПРЕДПОЛОЖЕНИЙ...............................................................................135

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

4.1.1 Вероятности появления наблюдений описываются распределением, параметры которого зависят от номера скрытого состояния СММ........135

4.1.2 Вероятности появления наблюдений описываются распределениями, параметры и вид которых зависят от номера скрытого состояния СММ.................................................................................................141

4.1.3 Вероятность появления наблюдений описывается смесью распределений, вид которых зависит от номера скрытого состояния СММ.........143

4.1.4 Вероятность появления наблюдений описывается смесью различных распределений с параметрами, зависящими от номера скрытого состояния СММ...............................................................................................................146

4.2 Процесс или объект, порождающий наблюдаемые последовательности, не имеет скрытых состояний.......................................................................................150

4.3 Поведение классификаторов в условиях структурной неопределенности..............................................................................................................................156

4.3.1 Исследование на двухклассовой задаче классификации.................157

4.3.2 Исследование на многоклассовой задаче классификации...............165

4.4 Выводы...............................................................................................................170

ГЛАВА 5 ВЫБОР ИНФОРМАТИВНЫХ ПРИЗНАКОВ....................................172

5.1 Методы выбора информативных признаков..................................................172

5.2 Исследования на смоделированных данных..................................................175

5.2.1 Исследования на двухклассовой задаче классификации.................175

5.2.2 Исследования на много классовой задаче классификации...............181

5.3 Экспериментальные и прикладная задачи......................................................185

5.3.1 Анализ выборки «Hill-Valley Dataset»...............................................185

5.3.2 Анализ выборки «Waveform Database»..............................................189

5.3.3 Прикладная задача...............................................................................194

5.4 Выводы...............................................................................................................216

ЗАКЛЮЧЕНИЕ........................................................................................................217

Список использованных источников....................................................................220

Приложение А Описание алгоритма Витерби.....................................................243

Приложение Б Рисунки и таблицы к исследованиям, приведенным в

пункте 3.2.1..............................................................................................................247

Приложение В Рисунки и таблицы к исследованиям, приведенным в параграфе 3.3 ...................................................................................................................254

Приложение Г Рисунки и таблицы к исследованиям, приведенным в

пункте 5.3.3 .............................................................................................................271

Приложение Д Описание программной системы................................................280

Д.1 Общая характеристика программной системы..............................................281

Д. 2 Основные элементы системы..........................................................................282

Д.З Задание выборок, параметров моделей и параметров программной системы...........................................................................................................................285

Д.4 Данные, формируемые в результате работы системы .................................287

Приложение Е Справка о внедрении результатов...............................................292

ВВЕДЕНИЕ

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

В данной диссертационной работе рассматриваются скрытые марковские модели (СММ), относящиеся к классу статистических моделей. Особенностью СММ является то, что они учитывают внутреннюю структуру последовательностей, которые регистрируются при наблюдении за процессами или объектами, описываемыми с помощью СММ [58].

СММ, собственно как метод, был разработан в середине бОх-конце 70х годов 20 века независимо отечественными (Винцюк Т.К. [12], Ковалевский В.А. [47, 48]) и зарубежными (Баум Л.Е (Baum L.E.) [85, 87-90], Петри Т. (Petrie Т.) [86]) исследователями. Значительный вклад в развитие как теории, так и практического использования СММ внесли такие отечественные ученые, как Моттль В.В. и Мучник И.Б. [58, 59], Воробьев С.А [13-19], Борисов A.B. [4-7]. Зарубежные исследования таких ученых, как Рабинер Л.Р. (Rabiner L.R.) [187189], Нефиан A.B. (Nefian A.V.) [179], Самариа Ф. (Samaria F.) [191], Каппе О. (Сарре О.) [98], более ориентированные на прикладные задачи, также внесли свой вклад в развитие СММ.

По своей природе СММ позволяют учитывать как пространственные, так и временные характеристики последовательностей. Поэтому эти модели получили широкое применение в различных прикладных задачах, таких как распознавание речи (см., например, работы авторов Рабинер J1.P. (Rabiner L.R.) [187189], Леггеттер С.Ж. (Leggetter C.J.) [158], Жанг Б.Х. (Juang, В.Н.) [146], Га-лес М. (Gales M.) [128], Хуанг К.Д. (Huang X.D.) [137], Гефке Д.А. [22], Ико-нинС.Ю. [44]), изображений (Нефиан A.B. (Nefian A.V.) [179], Самариа Ф. (Samaria F.) [191], Плотц Т. (Plötz Т.) [186], Бунке X. (Bunke H.) [96], Сандер-сон К. с коллегами (Sanderson С.) [99], Ли Дж. (Li J.) [164]), видеопоследовательностей (Кошал A. (Ghoshal А.) [129], Лиу К. (Liu X.) [168], Сайд У. (SaeedU.) [190]), задачи биоинформатики (Коски T. (Koski Т.) [151], Бар-бю B.C. (Barbu V.S.) [83], Бирней Е. (Birney Е.) [93], Р. Дурбин (Durbin R.) [115]), задачи геофизики (Грант Р. (Granat R.) [130]), эконометрические задачи (Мамон P.C. (Mamón R.S.) [171], Грегоир С. (Gregoir S.) [131], Бхар P. (Bhar R.) [91]); задачи сферы телекоммуникаций (Миллер Б.М. [56, 57], Антон-Харо С. (Anton-Haro С.) [76], Фоноллоза Ж.A. (Fonollosa J.А.) [123]), исследование динамических систем (Фрейзер A.M. (Fraser A.M.) [125]), стегоанализе (Сидоров М.А. [62]) и т. д.

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

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

Существует два подхода к решению этой задачи. В первом подходе используются методы, которые работают с самой моделью: либо изменяют структуру используемых моделей (см., например, работы таких авторов, как Александров В. [72], Нил P.M. (Neal R.M.)) [178], либо используют иные методы оценки параметров моделей (Вальдер С.Ж. (Walder C.J.) [205], Икбал С. (Ikbal S.) [138], Жоу Г.Д. (Zhou G.D.) [212]), либо же комбинируют эти два подхода (Лиу С. (Liu С.) [167], Чатзис П.С. (Chatzis S.P.) [102]). Другими словами, методы первой группы ориентированы на то, чтобы точнее описать исследуемый объект или процесс. При использовании второго подхода появляется возможность видоизменять решающее правило классификации, получая некую информацию от моделей и применяя ее для проведения классификации. Например, переходя в пространство вторичных признаков (см. работы таких авторов, как Солера-Урена Р. (Solera-Urena, R.) [198], Линг Ч. (Ling Ch.) [166], Аран О. (Aran О.) [77]), проводят классификацию с использованием метода опорных векторов. Второй подход представляется нам наиболее перспективным, т. к. здесь существует определенная свобода как в выборе пространства признаков, в котором проводится классификация, так и в выборе самого классификатора. Однако систематических исследований этого подхода в условиях, когда исследуемые процессы оказываются близкими по своей природе и присутствуют некоторые искажения последовательностей, порождаемые этими процессами, в литературе не встречается. Кроме того, нет исследований, связанных с выбором используемых в этом случае классификаторов; не освещен вопрос выбора информативных признаков при построении пространства, в котором происходит классификация последовательностей с использованием этого подхода.

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

первых производных от логарифма функции правдоподобия по параметрам СММ.

Для достижения поставленной цели предусмотрено решение следующих

задач:

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

- исследование поведения классификаторов, использующих пространство признаков в виде производных от логарифма функции правдоподобия по параметрам СММ в условиях, когда последовательности искажены помехами или при структурной неопределенности;

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

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

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

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

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

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

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

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

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

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

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

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

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

Обоснованность и достоверность научных положений, выводов и

рекомендаций обеспечивается:

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