Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

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

Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода

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

численные методы и комплексы программ»

кандидата технических наук

Савченко Андрей Владимирович

Москва - 2010

Работа выполнена на кафедре информационных систем и технологий Нижегородского филиала Государственного университета - Высшей школы экономики

Научный руководитель: кандидат технических наук, доцент Бабкин Эдуард Александрович

Официальные оппоненты: доктор технических наук, доктор экономических наук профессор Орлов Александр Иванович,

кандидат технических наук, доцент Акатьев Дмитрий Юрьевич

Ведущая организация: Институт прикладной физики Российской Академии Наук

Защита состоится “ 25 ” ноября 2010 г. в 12.00 часов на заседании диссертационного совета Д 212.048.09 при Государственном университете - Высшей школе экономики по адресу: 105679, Москва, ул. Кирпичная, д. 33, ауд. 503.

С диссертацией можно ознакомиться в библиотеке Государственного университета - Высшей школы экономики по адресу: 101990, Москва, ул. Мясницкая, д. 20.

Автореферат разослан “____” октября 2010 г.

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

доктор технических наук В.А. Фомичев

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

информационный распознавание изображение программа

Актуальность темы. Классификация объектов как направление исследований и одновременно теоретическая база для решения прикладных задач распознавания образов активно развивается с середины XX века. Большой вклад в его развитие внесли отечественные ученые В.Н. Вапник, В.М. Глушков, А.Л. Горелик, Ю.И. Журавлёв, Н.Г. Загоруйко, А.А. Харкевич, Я.З. Цыпкин, А.Я. Червоненкис и др. За рубежом одними из основоположников классификации применительно к распознаванию образов считаются Ф. Розенблатт и Б. Уидроу. В дальнейшем их идеи были развиты Л. Рабинером, К. Фукунагой, П. Хартом, Дж. Хопфилдом и др.

Среди систем классификации особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений. Действительно, цифровые изображения являются одним из основных способов представления информации в промышленности, медицине, и, конечно, в экономическом анализе (диаграммы, таблицы, графики и т.п.). Одной из наиболее актуальных прикладных задач в этой области считается ([Eickeler et al, 2000] Eickeler S., Jabs M., Rigoll G. Comparison of Confidence Measures for Face Recognition // Fourth IEEE International Conference on Automatic Face and Gesture Recognition (FG'00). 2000. P.257-263.) распознавание людей по фотографиям их лиц. Идентификация по фотографиям признана наиболее приемлемой для применения, т.к. может использоваться незаметно для окружающих в местах массового скопления людей.

Несмотря на широкую коммерциализацию рынка программных продуктов распознавания изображений, интенсивность исследований отнюдь не снижается, т.к. хотя цена существующих систем весьма высока, их надежность не достаточна. И связано это, прежде всего, с острейшей проблемой вариативности. Отдельные изображения одного объекта могут существенно варьироваться в зависимости от условий наблюдения: ракурса, расстояния, освещения. Проблема точности особенно усиливается, если объем базы эталонных данных составляет тысячи единиц, что приводит, к усложнению методов распознавания и, как следствие, невозможности реализации существующих алгоритмов ([Cover, Hart, 1968]Cover T.M., Hart P.E. Nearest Neighbor Pattern Classification. IEEE Trans. Information Theory. 1968. Vol. 13. P.21-27.) в режиме реального времени. Без применения современных моделей изображений и новых вычислительных методов их классификации данная проблема больших баз эталонов ([Tse, Lam, 2008] Tse S.-H., Lam K.-M. Efficient face recognition with a large database // 10th IEEE International Conference on Control, Automation, Robotics and Vision. 2008. P.944-949) не может быть преодолена.

Общепринятой моделью здесь служит понятие образа ([Цыпкин, 1968] Цыпкин Я.З. Адаптация и обучение в автоматических системах. - М: Наука, 1968. - 400 с.) - изображения группируются по принципу их близости (в некотором смысле) в набор кластеров. Система распознавания тогда решает задачу классификации изображений на наборе наиболее информативных эталонов из каждого кластера ([Орлов, 2009]Орлов А.И.О развитии математических методов теории классификации//Заводская лаборатория. - 2009. - №75(7).-С.51-63). К сожалению, такая редукция базы эталонов к центрам кластеров зачастую не позволяет преодолеть отмеченную проблему, т.к. число выделенных кластеров может быть велико. А многочисленные методы, основанные на математическом аппарате деревьев решений ([Zhang, Srihari, 2004] Zhang B., Srihari S.N. Fast k-Nearest Neighbor Classification Using Cluster-Based Trees. IEEE Trans. on Pattern Analysis and Machine Intelligence. 2004. Vol.26. №4. P. 525-528.), оказываются эффективными лишь в тех редких случаях, когда группы однородных изображений в пределах каждого кластера сходны между собой, но резко отличаются от объектов из других кластеров. Поэтому на практике классификация в реальном времени осуществляется за счет потерь в точности классификации ([Hastie et al, 2009] Hastie, T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer-Verlag, 2009. 746 p.).

Со всех перечисленных точек зрения несомненный интерес представляет моделирование распознавания изображений на основе теоретико-информационного подхода ([Zhao, Chellappa, 2005] Zhao W., Chellappa R. ed. Face Processing: Advanced Modeling and Methods. Elsevier/Academic Press, 2005. 768 p.) и общесистемного принципа минимума информационного рассогласования (МИР) в метрике Кульбака-Лейблера ([Кульбак, 1967] Кульбак С. Теория информации и статистика / Пер. С англ. М.: Наука, 1967. - 408 с.). Основанная на этом принципе информационная теория восприятия речи показала высокие результаты ([Савченко, 2007] Савченко В.В. Информационная теория восприятия речи//Известия вузов. Радиоэлектроника.-2007. - №6. - с.3-9.) в задаче автоматического распознавания речи. Между тем, не все преимущества принципа МИР получили необходимое освещение и развитие. В частности, до настоящего времени почти не исследовалась возможность разработки на его основе новых методов распознавания изображений. Исследования в этом актуальном направлении и составляют главное содержание представленной диссертационной работы.

Объект и предмет исследования. Вычислительные методы классификации изображений и таблиц данных в задачах с большими объёмами баз данных.

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

1. Выбор и обоснование теоретико-вероятностной модели изображения.

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

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

4. Реализация предложенного вычислительного метода в виде комплекса программ для проведения экспериментальных исследований его эффективности в реальных задачах распознавания изображений с базой эталонов большого объёма.

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

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

Научная новизна работы состоит в следующем

1. Предложена новая теоретико-вероятностная модель полутонового изображения с целью применения к задаче распознавания на основе принципа минимума информационного рассогласования в метрике Кульбака-Лейблера.

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

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

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

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

Полученные в диссертации результаты использованы в отчете по проекту НФ ГУ-ВШЭ №09-03 от 04.06.2009 «Разработка информационной системы для автоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационного рассогласования». Разработанная в рамках этого проекта «Автоматизированная система распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под №2009616508. Эта система использована в качестве прототипа при разработке системы биометрической идентификации в отделе исследовательских и перспективных проектов ООО «Теком». Результаты диссертационной работы внедрены в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (080700.62).

Апробация диссертации. Основные результаты работы докладывались на IX Международной научно-технической конференции «Интеллектуальные системы» в рамках Международного конгресса по информационным технологиям (Дивноморск, ТТИ ЮФУ, 2009), на XVI Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, НГТУ, 2010), на III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, МИРЭА, 2009), на 14-й Нижегородской сессии молодых ученых по математическим наукам (министерство образования Нижегородской области, 2009).

Публикации. По теме диссертации опубликованы 11 работ, которые приведены в конце автореферата, в том числе 5 - в журналах из Перечня ВАК; автором получен патент на полезную модель «Устройство для распознавания изображений», а также зарегистрирована в Роспатенте программа для ЭВМ «Автоматизированная система распознавания людей по фотографиям лиц».

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

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

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

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

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

Основное содержание работы

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

В первой главе для решения «Задачи распознавания полутоновых изображений» применяется статистический подход и принцип МИР. Задача состоит в том, чтобы отнести вновь поступающее (на вход) изображение к одному из R классов, заданных эталонами . Здесь U - высота изображения, V - его ширина; - интенсивность точки с координатами (u,v); x_max - максимальное значение интенсивности.

Для случайной величины - интенсивности r-го изображения - оценим по матрице X_r ее распределение

:

,

где д(x) - дискретная дельта-функция. Такая же процедура выборочной оценки распределения H применяется и для входного изображения X. Как известно, непосредственно сравнение гистограмм наталкивается на проблему вариативности освещения - если затемнить/осветлить изображение, то его гистограмма изменится. Именно поэтому после вычисления гистограмм H_r и H зачастую применяется их динамическое выравнивание, что существенно увеличивает объем вычислений.

В работе предлагается кардинальный способ преодоления указанного недостатка. Так как основная информация об изображении заключается не в цвете его точек, а в количестве точек с одинаковой освещенностью, перейдем к независимой от освещения гистограмме путем сортировки элементов H_r по убыванию: и существует такая перестановка чисел (1,2,…,x_max), что . В результате, можно рассматривать как распределение некой случайной величины. Применение этой теоретико-вероятностной модели изображения позволяет свести задачу распознавания к проверке R гипотез о распределении изображения на входе .

Теорема 1. Оптимальный в байесовском смысле минимума вероятности ошибки критерий распознавания изображений задается выражением

. (1)

Статистика с_KL(X/X_r) здесь определяет информационное рассогласование (направленное расхождение) по Кульбаку-Лейблеру между наблюдаемым изображением X и r-м эталоном. Справедливость теоремы 1 вытекает из более общей теоремы.

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

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

(2)

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

Проведено экспериментальное исследование эффективности критерия (1) в задаче распознавания людей по фотографиям лиц из большой базы данных Face Recognition Data: [сайт]. URL: http://cswww.essex.ac.uk/mv/allfaces/index.html (дата обращения: 05.09.2010). Из 6500 фотографий отобраны в качестве эталонов R=5500 изображений. Оставшиеся 1000 фотографий использовались для тестирования классификации. В результате применения критерия (1) в 98,9% случаев получено правильное решение. Среднее время распознавания одного изображения составило 1,4 с. на компьютере Pentium-IV (2,9ГГц, 1Гб ОЗУ), что не удовлетворяет требованию к реальному времени. При обычном сравнении гистограмм яркости без сортировки классификация осуществлялась с точностью 99,2%. Однако, если немного изменять освещение входного изображения, точность (1) составит 98,7%. Для иллюстрации на рис.1 показаны две фотографии одного человека: первая - эталон (рис.1а), вторая - изображение на входе (рис 1.в). Решение по (1) принято безошибочно притом, что входное фото затемнено и отличается ракурсом.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Для обычного сравнения гистограмм вероятность ошибки повысилась до 26%. Если же выравнивать гистограммы динамически, то точность повысится до 98,9%, однако среднее время распознавания превышает 2,5 с. Таким образом, предложенный критерий в формулировке (1) превосходит традиционные подходы в задачах распознавания изображений с варьирующейся освещенностью.

Во второй главе синтезируется «Метод направленного перебора альтернатив». Воспользовавшись метрическими свойствами критерия (1), сведем задачу

(3)

к упрощенному (в ее практической реализации) виду

(4)

Здесь с₀ - порог для допустимого рассогласования на множестве объектов одного класса за счет известной их вариативности. Значение такого порога определяется опытным путем при фиксировании ошибки второго рода. Заметим, что в общем случае справедливо неравенство с₀?с₁. Применение выражений (2) и (4) является обобщением последовательного анализа Вальда на критерий МИР.

Принятие решения на основе (4) требует вычисление рассогласований до тех пор, пока оно не будет меньше порогового уровня с₀, что позволит сократить объем перебора в среднем на 50%. Естественным развитием идеи останова (4) служит предложенный ниже метод направленного перебора, в котором метрические свойства статистики (1) используются в наиболее полной степени.

Наугад выбирается первая выборка из N<R эталонов . Среди них определим ближайший к X эталон X_i,i?N. Если с_KL(X/X_i)<с₀, то перебор на этом эталоне и завершается. В противном случае, для выделенного изображения-эталона X_i по предварительно вычисленной (один раз для конкретного множества эталонов) матрице значений рассогласований с_ij=с_KL(X_j/X_i) найдем множество из M<R эталонов , , находящихся от X_i на расстоянии, не превышающем порогового значения с_KL(X/X_i):

(5)

Здесь - отклонение рассогласования между входным изображением X и локальным оптимумом X_i относительно расхождения между X_j и X_i. Добавим к X^(M) еще один, (M+1)-й элемент из числа не попавших в состав контрольной выборки по результатам предыдущего этапа вычислений. Этим в поисковую процедуру вносится элемент случайности. В результате получаем вторую контрольную выборку изображений-эталонов , для анализа. Далее все вычисления первого этапа повторяются до тех пор, пока на некотором K-м этапе для элемента X_н не будет выполнено условие останова (4). В худшем случае, после перебора всех элементов {X_r}, но в отсутствие решения из (4), делается вывод о том, что входное изображение X нельзя отнести ни к одной из альтернатив. В результате, суммарное число N+(M+1)K выполняемых согласно (4) проверок может существенно выигрывать по сравнению с объемом базы эталонов. Этот выигрыш обусловлен, в частности, тем, что для рассогласования Кульбака-Лейблера (как, впрочем, и для других непрерывных расстояний) вероятность p того, что искомый эталон X^* принадлежит множеству X^(M), значительно выше вероятности того, что X^* будет одним из M наудачу выбранных эталонов:

. (6)

В этом и состоит эффект направленного перебора. А отличия в количестве K этапов алгоритма объясняются тем, что вероятность (6) зависит не только от используемой метрики, но и от входного изображения и множества эталонов.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Проиллюстрируем метод с помощью диаграммы (рис.2). Здесь звездочками обозначены все имеющиеся изображения-эталоны, буквой X - входное изображение, а ромбиком - наиболее близкий к X эталон X^*, определяющий искомое решение задачи. Жирными точками обозначена последовательность наиболее близких к оптимуму изображений после нескольких подряд этапов вычислений. Радиусы окружностей определяются согласно (5). Траектория поиска отображается на рис. 2 ломаной направленной линией и имеет вид скручивающейся спирали.

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

(7)

После этого на основе критерия минимума суммы рассогласований в пределах r-го кластера определяется его информационный центр-эталон вида

(8)

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

Вследствие сходства выражений (7) и (4), МНП (1), (4) - (6) может быть применен и для самообучения (7), (8). Действительно, при адаптивном подходе классы формируются постепенно следующим образом. Вначале число классов R=0, далее для каждого изображения-эталона ищется класс r, для которого выполняется условие (4), то есть решается задача классификации изображения X_l. Если такой класс х найден, то объект X_l добавляется в класс X_х, а далее согласно (9) вычисляется его новый информационный центр. И только если , то создается новый, (R+1)-й класс .

Для МНП (4)-(8) в работе сформулированы и доказаны следующие теоремы.

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

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

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

В третьей главе «Разработка информационной системы» представлена комплекс программ, реализующий критерий (1) и метод (4)…(8). Программная часть системы реализована на современном языке Java SE 6, что расширяет возможности ее дальнейшего практического использования. Приведена общая схема автоматической системы распознавания людей по фотографиям лиц, описан ее интерфейс, сформулированы назначение и принципы работы. Подробно рассмотрены функциональные возможности системы, приведены блок-схемы новых алгоритмов: МНП, редукции базы эталонов (7),(8) и определения порогов рассогласований с₀ и с₁. На рис. 3 показана структурная схема распознавания изображений на основе МНП. Принципиальное отличие этой схемы от всех известных аналогов заключается в том, что блок выбора эталонов для проверки управляется новым блоком экстраполяции расстояний (5).

Рис. 3. Структурная схема устройства для распознавания изображений на основе МНП.

Для решения задачи распознавания людей по фотографиям из главы 1 средствами созданной системы определены оптимальные (в смысле среднего количества вычислений рассогласований) значения параметров МНП: размер начальной выборки N=5, число попыток M=64. Вначале, задав ошибку второго рода равной 5%, был подобран порог досрочного прекращения перебора с₀=0,097. Далее, используя алгоритм редукции на основе МНП, все множество из 5500 изображений сгруппировано в R=960 кластеров. Количество вычислений рассогласований составило 29,5% по сравнению с традиционным группированием полным перебором. Однако гораздо важнее сокращение вычислений на втором этапе алгоритма - этапе распознавания. Результаты применения здесь МНП и генетического алгоритма (ГА), реализующего случайный поиск, показаны на рис. 4.

Рис.4. Гистограммы количества вычислений рассогласований относительно объема базы

Здесь среднее количество вычислений рассогласований по МНП составило примерно 11,9% от числа эталонов. С вероятностью 65% количество вычисления рассогласований (1) не превысило 5% от R. При этом в 96,8% случаев было получено точное решение. Среднее время распознавания одного изображения на том же компьютере составило 25 мс, что уже позволяет реализовать подобную систему в режиме реального времени. Для сравнения, при использовании с МНП традиционной l₁-метрики, вероятность ошибки составила 2,5%, при этом проверялось 18,5% эталонов. Таким образом, МНП существенно сокращает вычислительную трудоемкость классификации изображений и для традиционных критериев.

В четвертой главе рассматривается «Перспективы применения метода направленного перебора в других задачах классификации», для которых актуальна проблема большого числа эталонов. В двух первых разделах главы исследуется задача распознавания изолированных слов, для которой проблема вариативности не может быть преодолена без введения модели «образа». Решение задачи сводится к двухэтапной проверке статистических гипотез. На первом этапе классифицируются элементарные речевые единицы типа отдельных фонем, а на втором - слова как структурированные последовательности разных фонем. Фонема здесь определяется в строгом, теоретико-информационном смысле, как множество типа кластера (7),(8) речевых единиц, объединенных по критерию МИР.

На первом этапе используется линейная авторегрессионная модель формирования речевого сигнала, обоснованная предположением о гауссовом законе распределения, и теорией «акустической трубы» Гельмгольца. Тогда критерий МИР

(9)

будет оптимальным в байесовском смысле. Здесь G_x(f) и G_r(f)- оценки (на основе рекурсивной процедуры Берга-Левинсона) спектральной плотности мощности сигнала x и r-ого эталона x_r из фонетической базы данных; F - верхняя граница частоты сигнала. В результате речевой сигнал разбивается на последовательность фонем. Рассогласование между словами на втором этапе вычисляется как сумма рассогласований (9) между составляющими их фонемами. Для выравнивания слов по темпу речи применяется динамическое программирование и алгоритм Левенштейна.

В ходе эксперимента вначале, используя запись диктором отрывка из «Капитанской дочки», алгоритмом (7)…(9) выявлено множество из 20 элементарных речевых единиц. На его основе путем перебора разных сочетаний фонем сформировано множество{X_r} объема R=10000. В ней каждое слово представлялось последовательностью сочетающихся случайным образом фонем, чем достигались наиболее жесткие условия для последующей классификации. На основе некоторого (каждый раз разного) слова-эталона X_r путем дублирования или удаления части его фонем формировалось распознаваемое слово. Среднее количество вычислений рассогласований при точности 99% составило примерно 20,6% от количества альтернатив. Этот эксперимент убедительно показал, что МНП может успешно применяться и в такой сложной задаче классификации, как распознавание речи.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

В заключительном, третьем разделе главы рассмотрена задача многоальтернативного планирования биржевой игры на фондовом рынке по принципу аналогии текущего состояния рынка с его состояниями в прошлом. Задача сводится к многоальтернативной классификации в режиме «без учителя», в пределах нескольких тысяч альтернатив в ретроспективе рынка глубиной в несколько лет. Вначале задаются размер U периода, на котором курс цен считается однородным, и набор параметров {c^(н)(t)}, наиболее адекватно, по мнению исследователя, характеризующих конъюнктуру рынка. План игры зависит от знака приращений параметров x^(н)(t)=c^(н)(t)-c^(н)(t-1) - положительное приращение соответствует росту цен, отрицательное - спаду. Предположим, что каждая торговая сессия в момент времени определяет изображение с двумя компонентами цветности и , где r=t-U и . Тем самым задана математическая модель фондового рынка в виде изображения приращений цен для данного финансового инструмента на данный момент времени. Текущая рыночная ситуация описывается аналогичным изображением X. Для иллюстрации на рис. 5 показаны модели-изображения акций General Electric на период длиной в одну неделю на 20.02.2001 и 22.09.2009. Несмотря на значительный временной сдвиг между ними, рассматриваемые состояния весьма близки по геометрии рисунка. Эффект от сказанного еще более усиливается рис. 6, где сопоставлены временные диаграммы рынка для тех же (рис.5) состояний, причем как в ретро, так и перспективе.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 6. Временные диаграммы рыночных цен

Реальная ретроспектива рынка содержит в себе большое число изображений-эталонов {X_r}, которые можно сгруппировать в несколько состояний-кластеров. Предположив, что X_r представляет собой спектральную плотность некоего (гипотетического) двумерного случайного сигнала, сведем задачу к проверке R гипотез о спектральной плотности мощности сигнала - текущего состояния рынка X, тогда основанное на принципе МИР (9) решение примет вид

. (10)

Для многоальтернативного планирования игры достаточно привести критерий (10) к виду (4). Действительно, при надлежащем выборе порога с₀ условию (4) могут удовлетворить сразу несколько эталонов.

В процессе экспериментальных исследований рассмотрено несколько примеров из истории акций компании General Electric и индекса высокотехнологичного сектора американского рынка Nasdaq-100. Использовались стандартные параметры: цены открытия, закрытия, а также минимальная и максимальная цена. Исторические данные (ретроспектива) взяты за период с января 1995г по сентябрь 2009г. Количество ближайших альтернатив задано равным A=4. Для их нахождения использовалась описанная в главе 3 система распознавания изображений. Среднее число вычислений по МНП составило здесь 24,8% от объема ретроспективы для акций General Electric и 33,4% - для индекса Nasdaq-100. Для сравнения, случайный поиск потребовал соответственно 66,7% и 80,2% вычислений рассогласований. Полученные результаты подтверждают ожидания в отношении перспектив применения метода направленного перебора в задачах классификации произвольных объектов, заданных в виде таблиц данных.

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

Основные результаты диссертационной работы

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

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

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

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

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

Список публикаций автора по теме диссертации

Работы в изданиях, входящих в Перечень ВАК:

1. Савченко А.В. Метод направленного перебора альтернатив в задаче автоматического распознавания полутоновых изображений // Автометрия. - 2009. - Т.45, №3. - с.90-98. 0,5 п.л.

2. Савченко А.В. Распознавание изображений методом направленного перебора с применением редукции множества альтернатив // Системы управления и информационные технологии. - 2009. - Т.37, №3. - С.40-47. 0,5 п.л.

3. Савченко А.В. Метод направленного перебора словаря в задаче автоматического распознавания речи на основе принципа минимума информационного рассогласования // Системы управления и информационные технологии. - 2009. - Т.35, №1. - С.83-91. 0,75 п.л.

4. Савченко А.В. Распознавание изображений методом направленного перебора на основе принципа минимума информационного рассогласования // Вестник Нижегородского Университета им. Н.И. Лобачевского. - 2010. - №2. - С.211-216. 1,0 п.л.

5. Савченко В.В., Савченко А.В. Принцип минимального информационного рассогласования в задаче распознавания дискретных объектов // Известия вузов России. Радиоэлектроника. - 2005. - №3. - С.10-18. 1,0 п.л. (вклад автора 0,3 п.л.)

Работы в других изданиях:

6. Савченко А.В. Распознавание фотографий лиц методом направленного перебора на основе принципа минимума информационного рассогласования //Тр. Конгресса по интеллектуальным и информационным технологиям «AIS-IT'09». - М. Физматлит. - 2009. - Т.3.-С.314-315. 0,1 п.л.

7. Савченко А.В. Метод направленного перебора альтернатив в задаче планирования биржевой игры. // Материалы XVI международной научно-технической конференции «Информационные системы и технологии-2010». НГТУ, Нижний Новгород. - 2010. - С.245-247. 0,1 п.л.

8. Савченко А.В. Распознавание образов методом направленного перебора. // Искусственный интеллект: философия, методология, инновации. Материалы III всероссийской конференции студентов, аспирантов и молодых ученых. - М.: Связь-принт. - 2009. - С.312-315. 0,3 п.л.

9. Савченко А.В. Группирование фотографий лиц методом направленного перебора на основе принципа минимума информационного рассогласования // Тр. XIV Нижегородской сессии молодых ученых. Математические науки. - Н.Новгород. - 2009. - С.24-25. 0,1 п.л.

10. Savchenko A.V. Image retrieval using minimum information discrimination criterion // The IASTED International Conference on Control, Diagnostics, and Automation (ACIT-CDA). Novosibirsk. 2010. pp. 345-349. 0,6 п.л.

11. Савченко А.В. Распознавание образов на основе принципа минимума информационного рассогласования // Тр. XII Всероссийской научно-технической конференции «Нейроинформатика-2010». - Москва. - 2010. - Т.2. - С.201-202. 0,1 п.л.

12. Патент РФ №2009127049/22, 27.10.2009. Савченко А.В. Устройство для распознавания изображений/Патент России №88171. 2009. Бюл. №30. 0,2 п.л.

13. Савченко А.В. Автоматизированная система распознавания людей по фотографиям лиц - Программа для ЭВМ. / Свид-во о гос. регистрации № 2009616508 по заявке 2009615314 от 28.09.2009. 0,1 п.л.

Лицензия ЛР № 020832 от 15 ноября 1993 г.

Подписано в печать ___ октября 2010 г.

Формат 60 х 84/16

Бумага офсетная.

Печать офсетная.

Усл. печ. л. 1

Тираж 100 экз. Заказ № ______

Типография издательства

Государственного университета - Высшей школы экономики,

125319, г. Москва, Кочновский проезд, д.3

Размещено на Allbest.ru

...