Содержание к диссертации
Введение
Глава 1. Задача распознавания полутоновых изображений 17
1.1. Статистический подход 17
1.2. Критерий минимума информационного рассогласования 24
1.3. Результаты экспериментальных исследований 33
1.4. Выводы 40
Глава 2. Метод направленного перебора альтернатив 42
2.1. Метрические свойства статистики МИР 42
2.2. Синтез алгоритма 47
2.3. Результаты экспериментальных исследований 61
2.4. Выводы 73
Глава 3. Разработка информационной системы 74
3.1. Архитектура информационной системы 74
3.2. Интерфейс информационной системы 81
3.3. Программа и результаты экспериментальных исследований 90
3.4. Выводы 102
Глава 4. Перспективы применения метода направленного перебора в других задачах классификации 103
4.1. Задача автоматического распознавания речи 103
4.2. Распознавание изолированных слов методом направленного перебора 110
4.3. Задача прогнозирования рынка ценных бумаг 117
4.4. Выводы 129
Заключение 130
Библиографический список 135
Приложения 147
- Критерий минимума информационного рассогласования
- Интерфейс информационной системы
- Программа и результаты экспериментальных исследований
- Распознавание изолированных слов методом направленного перебора
Введение к работе
Актуальность темы. Классификация объектов как направление исследований и одновременно теоретическая база для решения прикладных задач распознавания образов активно развивается с середины XX века. Большой вклад в его развитие внесли отечественные ученые В.Н. Вапник, В.М. Глушков, А.Л. Горелик, Ю.И. Журавлёв, Н.Г. Загоруйко, А.А. Харкевич, ЯЗ. Цыпкин, А.Я. Червоненкис и др. За рубежом одними из основоположников классификации применительно к распознаванию образов считаются Ф. Розенблатт и Б. Уидроу. В дальнейшем их идеи были развиты Л. Рабинером, К. Фукунагой, П. Хартом, Дж. Хопфилдом и др.
Среди систем классификации особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений. Действительно, цифровые изображения являются одним из основных способов представления информации в промышленности, медицине, и, конечно, в экономическом анализе (диаграммы, таблицы, графики и т.п.). Одной из наиболее актуальных прикладных задач в этой области считается ([Eickeler et al, 2000]1) распознавание людей по фотографиям их лиц. Идентификация по фотографиям признана наиболее приемлемой для применения, т.к. может использоваться незаметно для окружающих в местах массового скопления людей.
Несмотря на широкую коммерциализацию рынка программных продуктов распознавания изображений, интенсивность исследований отнюдь не снижается, т.к. хотя цена существующих систем весьма высока, их надежность не достаточна. И связано это, прежде всего, с острейшей проблемой вариативности. Отдельные изображения одного объекта могут существенно варьироваться в зависимости от условий наблюдения: ракурса, расстояния, освещения. Проблема точности особенно усиливается, если объем базы эталонных данных составляет тысячи единиц, что приводит, к усложнению методов распознавания и, как следствие, не-возможности реализации существующих алгоритмов ([Cover, Hart, 1968] ) в ре-
1 Eickeler S., Jabs М, Rigoll G. Comparison of Confidence Measures for Face Recognition II Fourth IEEE International
Conference on Automatic Face and Gesture Recognition (FG'00). 2000. P.257-263.
2Cover T.M., Hart P.E. Nearest Neighbor Pattern Classification. IEEE Trans. Information Theory. 1968. Vol. 13. P.21-27.
жиме реального времени. Без применения современных моделей изображений и новых вычислительных методов их классификации данная проблема больших баз эталонов ([Tse, Lam, 2008] ) не может быть преодолена.
Общепринятой моделью здесь служит понятие образа ([Цыпкин, 1968] ) -изображения группируются по принципу их близости (в некотором смысле) в набор кластеров. Система распознавания тогда решает задачу классификации изображений на наборе наиболее информативных эталонов из каждого кластера ([Орлов, 2009] ). К сожалению, такая редукция базы эталонов к центрам кластеров зачастую не позволяет преодолеть отмеченную проблему, т.к. число выделенных кластеров может быть велико. А многочисленные методы, основанные на математическом аппарате деревьев решений ([Zhang, Srihari, 2004]6), оказываются эффективными лишь в тех редких случаях, когда группы однородных изображений в пределах каждого кластера сходны между собой, но резко отличаются от объектов из других кластеров. Поэтому на практике классификация в реальном времени осуществляется за счет потерь в точности классификации ([Hastie et al, 2009] ).
Со всех перечисленных точек зрения несомненный интерес представляет моделирование распознавания изображений на основе теоретико-
информационного подхода ([Zhao, Chellappa, 2005] ) и общесистемного принципа минимума информационного рассогласования (МИР) в метрике Кульбака-Лейблера ([Кульбак, 1967] ). Основанная на этом принципе информационная теория восприятия речи показала высокие результаты ([Савченко, 2007] ) в задаче
3 Tse S.-H., Lam К.-М. Efficient face recognition with a large database II 10th IEEE International Conference on Control,
Automation, Robotics and Vision. 2008. P.944-949
4 Цыпкин ЯЗ. Адаптация и обучение в автоматических системах. - М: Наука, 1968. - 400 с.
5Орлов А.И.О развитии математических методов теории классификации//Заводская лаборатория. - 2009. - №75(7).-С.51-63
6 Zhang В., Srihari S.N. Fast k-Nearest Neighbor Classification Using Cluster-Based Trees. IEEE Trans, on Pattern Analy
sis and Machine Intelligence. 2004. Vol.26. №4. P. 525-528.
7 Hastie, Т., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd
ed. Springer-Verlag, 2009. 746 p.
8 Zhao W., Chellappa R. ed. Face Processing: Advanced Modeling and Methods. Elsevier/Academic Press, 2005. 768 p.
9 Кульбак С. Теория информации и статистика / Пер. С англ. М.: Наука, 1967. - 408 с.
10 Савченко В.В. Информационная теория восприятия речи//Известия вузов. Радиоэлектроника.-2007. - №6. - с.3-9.
автоматического распознавания речи. Между тем, не все преимущества принципа МИР получили необходимое освещение и развитие. В частности, до настоящего времени почти не исследовалась возможность разработки на его основе новых методов распознавания изображений. Исследования в этом актуальном направлении и составляют главное содержание представленной диссертационной работы. Объект и предмет исследования. Вычислительные методы классификации изображений и таблиц данных в задачах с большими объёмами баз данных. Цель и задачи работы. Основная цель диссертационной работы состоит в разработке методов ускорения вычислительной процедуры классификации в условиях большого количества альтернатив - на основе принципа минимума информационного рассогласования и предлагаемого метода направленного перебора альтернатив (МНИ). Для достижения этой цели в диссертации решались следующие задачи:
1. Выбор и обоснование теоретико-вероятностной модели изображения.
2. Разработка нового, теоретико-информационного критерия оптимальности
решения задачи автоматического распознавания изображений на основе теорети
ко-вероятностной модели изображений.
Разработка и исследование нового метода классификации с направленным перебором и редукцией множества эталонов как альтернативы традиционным методам, основанным на принципе полного перебора конкурирующих гипотез.
Реализация предложенного вычислительного метода в виде комплекса программ для проведения экспериментальных исследований его эффективности в реальных задачах распознавания изображений с базой эталонов большого объёма.
Исследование возможностей и перспектив применения метода направленного перебора в других актуальных задачах классификации.
Методы исследования. В работе использовались современные методы теории распознавания образов, теории вероятностей и математической статистики, имитационного моделирования, теории информации, теории сигналов. Научная новизна работы состоит в следующем
1. Предложена новая теоретико-вероятностная модель полутонового изображения с целью применения к задаче распознавания на основе принципа минимума
информационного рассогласования в метрике Кульбака-Лейблера.
Разработан новый вычислительный метод направленного перебора альтернатив, позволяющий значительно ускорить вычислительную поисковую процедуру классификации по сравнению с традиционными методами «ближайших соседей»; его новизна подтверждена патентом на полезную модель.
Разработана модификация метода направленного перебора с обучением в режиме «без учителя», основанная на принципах группирования данных в кластеры по критерию минимума информационного рассогласования, благодаря чему достигается максимальный выигрыш по быстродействию при классификации среди большого количества альтернатив.
На основе метода направленного перебора предложен новый алгоритм распознавания речи, позволяющий в несколько раз сократить объем выполняемых вычислений по сравнению с современными методами полного перебора. Практическая ценность работы состоит в том, что метод направленного перебора и его модификации предназначены для решения задач классификации в условиях больших баз данных эталонов, когда известные методы характеризуются недостаточным быстродействием. При этом предложенный метод может быть использован как на основе существующих информационных систем, так и путем включения в них вспомогательных блоков подготовки данных в режиме обучения и их обработки в режиме распознавания. Достигаемый эффект - сокращение объема и времени вычислений - главное с точки зрения практики качество метода.
Полученные в диссертации результаты использованы в отчете по проекту НФ ГУ-ВШЭ №09-03 от 04.06.2009 «Разработка информационной системы для автоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационного рассогласования». Разработанная в рамках этого проекта «Автоматизированная система распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под №2009616508. Эта система использована в качестве прототипа при разработке системы биометрической идентификации в отделе исследовательских и перспективных проектов ООО «Теком». Результаты
диссертационной работы внедрены в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (080700.62). Апробация диссертации. Основные результаты работы докладывались на IX Международной научно-технической конференции «Интеллектуальные системы» в рамках Международного конгресса по информационным технологиям (Дивно-морск, ТТИ ЮФУ, 2009), на XVI Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, НГТУ, 2010), на III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, МИРЭА, 2009), на 14-й Нижегородской сессии молодых ученых по математическим наукам (министерство образования Нижегородской области, 2009).
Публикации. По теме диссертации опубликованы 11 работ, которые приведены в конце автореферата, в том числе 5 - в журналах из Перечня ВАК; автором получен патент на полезную модель «Устройство для распознавания изображений», а также зарегистрирована в Роспатенте программа для ЭВМ «Автоматизированная система распознавания людей по фотографиям лиц». Основные положения, выносимые на защиту.
Метод направленного перебора альтернатив как эффективный (в смысле вычислительной сложности) метод решения задачи автоматического распознавания полутоновых изображений.
Комплекс проблемно-ориентированных программ, реализующий метод направленного перебора и предназначенный для проведения вычислительного эксперимента.
Оценки вычислительной трудоемкости метода направленного перебора в сравнении с генетическим алгоритмом по результатам комплексного исследования проблемы больших баз эталонных данных в задаче автоматического распознавания изображений.
Структура и объем работы. Диссертация изложена на 152 страницах, состоит из введения, четырех глав основного текста, заключения, списка используемой литературы, включающего 117 наименований, и шести приложений.
Критерий минимума информационного рассогласования
Предложена новая теорегико-вероятностная модель полутонового изображения с целью применения к задаче распознавания принципа минимума информационного рассогласования в метрике Кульбака-Лейблера.
Разработан новый вычислительный метод направленного перебора альтернатив, позволяющий значительно ускорить вычислительную поисковую процедуру классификации по сравнению с традиционными методами «ближайших соседей»; его новизна подтверждена патентом на полезную модель;
3. Разработана модификация метода направленного перебора с обучением в режиме «без учителя», основанная на принципах группирования данных в кластеры по критерию минимума информационного рассогласования, благодаря чему достигается максимальный выигрыш по быстродействию при классификации среди большого количества альтернатив;
4. На основе метода направленного перебора предложен новый алгоритм распознавания речи, позволяющий в несколько раз сократить объем выполняемых вычислений по сравнению с современными методами полного перебора.
Практическая ценность работы состоит в том, что предложенный МНП и его модификации предназначены для решения задач классификации в условиях больших БЭД, когда известные методы характеризуются недостаточным быстродействием. При этом МНП может быть использован как на основе структуры и состава существующих информационных систем, так и путем включения в эти системы вспомогательных (дополнительных) блоков подготовки данных в режиме обучения и их обработки в режиме распознавания. Достигаемый при этом эффект: сокращение объема и времени вычислений оказывается прямо пропорциональным объему БЭД - это главное с точки зрения практики применения качество предложенного МНП.
Результаты диссертационного исследования были использованы в проекте НФ ГУ-ВШЭ №09-03 от 04.06.2009 «Разработка информационной системы для автоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационного рассогласования» под руководством автора. Разработанная в рамках данного проекта «Автоматизированная система распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под № 2009616508 - по заявке 2009615314 от 28.09.2009 [37]. Созданная автоматизированная система использована в качестве прототипа при разработке системы биометрической идентификации в отделе исследовательских и перспективных проектов ООО «Теком» (г.Н.Новгород). Результаты диссертационной работы внедрены также в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (080700.62).
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на IX Международной научно-технической конференции «Интеллектуальные системы» в рамках Международного конгресса по интеллектуальным системам и информационным технологиям (Дивноморск, ТТИ ЮФУ, 2009), на XVI Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, НГТУ, 2010), на III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, МИРЭА, 2009), на 14-й Нижегородской сессии молодых ученых по математическим наукам (министерство образования Нижегородской области, 2009), а также на ряде научных семинаров кафедры «Информационные системы и технологии» НФ ГУ-ВШЭ.
Публикации. Основные результаты диссертации опубликованы в одиннадцати работах автора [38-46] в том числе пять - в журналах их Перечня ВАК, а именно: «Автометрия» СО РАН, «Системы управления и информационные технологии», «Вестник Нижегородского университета им. Н.И. Лобачевского» и «Известия вузов России. Радиоэлектроника». Кроме того, автором получен патент на полезную модель «Устройство для распознавания изображений» [47], а также зарегистрирована в Роспатенте программа для ЭВМ «Автоматизированная система распознавания людей по фотографиям лиц» [37].
Основные положения, выносимые на защиту: 1. Метод направленного перебора альтернатив как эффективный вычислительный метод в задаче автоматического распознавания полутоновых изображений; 2. Комплекс проблемно-ориентированных программ для ЭВМ, реализующий метод направленного перебора и предназначенный для проведения вычислительного эксперимента; 3. Оценки вычислительной трудоемкости метода направленного перебора альтернатив в сравнении с генетическим алгоритмом по результатам комплексного исследования проблемы больших баз эталонных данных в задаче автоматического распознавания изображений.
Интерфейс информационной системы
Счі - счётчик верно распознанных изображений. На его вход поступает распознаваемое изображение с блока И и наиболее близкое к нему изображение-эталон. Результатом является суждение о верности распознавания ("1"-распознал,"0"-не распознал). Сч2 — счётчик распознаваемых изображений. Д - делитель, определяющий вероятность распознавания сегментов. Принцип работы экспериментальной установки заключается в следующем. Источник изображений И выдаёт изображения по команде генератора тактовых импульсов ГТИ. БПО осуществляет приведение изображения к единому масштабу (высота изображения U=const, ширина V=consf) и нормировку. БИС, в данном случае, - блок вычисления рассогласований между тестовым изображением и эталонами. На выходе БИС получается минимальное рассогласование между входным изображением и одним из эталонов. Получившееся расстояние сравнивается с порогом и СС вырабатывает наиболее близкий к входному изображению эталон. Накопитель Сч1, получив на вход распознаваемое изображение и изображение с блока СС, считает количество верно распознанных изображений за всё время работы системы. Накопитель Сч2 считает общее число изображений, поданных с И. Делитель Д вычисляет отношение правильно распознанных изображений к общему числу распознаваемых изображений, иначе говоря, вычисляет вероятность правильного распознавания. Вначале рассмотрим случай, когда все изображения освещены одинаково. Для проведения эксперимента использовался персональный компьютер марки PENTIUM-4. В качестве предварительной обработки изображений детекция лиц осуществлялась с использованием библиотеки OpenCV [70]. Выделенные лица приводились к одному масштабу (U=V=64). Итак, решалась задача распознавания изображения X из множества всех его допустимых альтернатив [х ]. Сначала для этого применялась метрика L из выражения (1.1.1). Здесь в 99% случаев было получено точное решение X = Xг. При этом среднее время распознавания одного изображения составило примерно 1350 мс, поэтому распознавание в режиме реального времени затруднительно даже для столь несложной задачи с размером изображений 64x64 пикселя. Аналогичная задача решалась позже в метрике Кульбака-Лейблера (1.2.8). В результате, в 98,9% случаев было получено точное решение X =Х . Среднее время распознавания одного изображения составило 1400 мс. Кажется, что для этого эксперимента результаты, полученные на основе метрики / , превосходят по качеству результаты использования рассогласования Кульбака-Лейблера. Однако это превосходство основано на том, что метрика / в формулировке (1.1.1) использует условное предположение о том, что все входные изображения освещены так же, как и эталоны из БЭД. Для подтверждения немного изменим наш предыдущий эксперимент. Выполним искусственное изменение освещения тестовых изображений (рис. 1.3.1,в) и проведем процедуру АРИ еще раз. В этом случае для метрики Кульбака-Лейблера вероятность ошибки составила 1,3%. Таким образом, результаты использования рассогласования Кульбака-Лейблера (1.2.8) ухудшились не существенно по сравнению с предыдущим экспериментом без искажений тестовых изображений. Однако при использовании метрики /j из выражения (1.1.1) результаты получаются значительно хуже. Так, вероятность ошибки повысилась до 16%. При традиционном сравнении гистограмм яркости без сортировки точность классификации составила 99,2% при фиксированном освещении и 74% для затемненных тестовых изображений. Если же использовать динамическое выравнивание гистограмм, то точность классификации при варьирующемся освещении составит 99%, однако среднее время распознавания превышает 2,3 с. Таким образом, предложенный критерий в формулировке (1.2.8) превосходит традиционные подходы в задачах с варьирующейся освещенностью. Теперь попытаемся распознать изображение, которого нет в БЭД (рис. 1.3.6). В этом случае, для рассогласования Кульбака-Лейблера (1.2.8) min pKL{X/Xr) = 0,20\»p]=0,l3S и система (рис.1.3.5) re {l ..я} принимает решение о том, что входное изображение в БЭД отсутствует. 1.4. Выводы В результате проведенных исследований можно сделать следующие выводы. Во-первых, качество решения для разных задач АРИ во многом определяется используемым критерием. Например, критерий МИР в формулировке (1.2.1) превосходит традиционные критерии в задачах с варьирующейся освещенностью тестовых изображений, т.е при их искажениях. Во-вторых, для больших объемов БЭД (несколько тысяч единиц) использование оптимальных решающих правил вида (1.1.1) или (1.2.8) существенно затрудняется тем, что в их основе лежит полный перебор всех альтернатив. Последнее обстоятельство является главным препятствием на пути реализации подобных систем в режиме реального времени.
Программа и результаты экспериментальных исследований
Для подбора оптимальных значений указанных выше параметров может использоваться меню «Тест». В начале, существующая база данных изображений разбивается на две части с помощью команды "Тест"- "Разбиение БД". В появившемся диалоговом окне пользователь может выбрать исходный каталог, в котором хранятся изображения БД, с описанной выше организацией структуры подкаталогов; целевой каталог, в котором по результату выполнения операции будут созданы два подкаталога (db для хранения части БД и test, содержащий изображения для тестирования). Также пользователь может указать, какая часть w (в процентах) исходной БД будет помещена в каталог db. Блок-схема операции разбиения БД показана на рис. 3.3.2.
Блок-схема алгоритма разбиения БД После завершения операции разбиения требуется оценить пороги PQ И /?. Для этого используется меню "Тест"- "Оценить оптимальный порог". В появившемся диалоговом окне вводится созданный ранее каталог db с изображениями БД. По окончании операции ИС отображает следующие результаты в новом окне (рис. 3.3.3): гистограммы распределения рассогласований \рг ] (ИР внутри одного класса изображений) и у?,. ] (ИР между различными классами), описанных в разделе 1.3. Именно с помощью этих последовательностей ИР и определяются оптимальные значения порогов; вероятность ошибки - относительное число изображений, для которых ИР внутри класса превышает ИР с изображением из другого класса. Для всех таких изображений полный перебор приводит к ошибке; нижний порог- порог PQ досрочного останова перебора БЭД; верхний порог - порог рл. Если ИР между входным изображением и всеми эталонами из БЭД превышает р , то делается вывод о том, что распознаваемое изображение не принадлежит ни одному из классов БЭД ((R+1 )-й элемент в ИТВР); ошибка второго рода - относительное число изображений, для которых ИР внутри их класса превышает нижний порог. Структурная схема операции оценки порогов /?Q И р показана на рис. 3.3.4. 3.1.7). Предварительно можно выполнить операцию группирования (меню "Группирование") с использованием того же значения для порога ИР внутри одного кластера, описанную в разделе 3.2. Наконец, задаются параметры МНП (рис. 3.3.1) и выполняется операция автоматического распознавания в тестовом режиме. Для ее выполнения служит команда "Тест"- "Распознать". В открывшемся диалоговом окне необходимо выбрать каталог с изображениями для тестирования (каталог test, созданный ранее) и сохраненный на предыдущем этапе файл БД. Кроме того, можно указать, необходимо ли детектировать в тестовых изображениях лица, и задать используемые алгоритмы распознавания (доступны флажки МНП и ГЛ). Структурная схема алгоритма тестирования совпадает с блок-схемами (рис. 1.3.5 и рис. 2.3.1). Различие состоит лишь в том, что критерием верного распознавания здесь служит совпадение имен родительских каталогов для двух изображений, тестового и наиболее близкого к нему эталона (что следует из структуры каталогов БД, описанной в разделе 3.1). По завершении операции распознавания появляется дочернее окно (рис. 3.3.5) с результатами тестирования распознавания. Результаты тестирования включают в себя гистограммы количества вычислений рассогласований, вычисленных тем или иным методом, а также ряд параметров, таких как вероятность успешного распознавания ГА и МНП, среднее число проверок (вычислений I (1\4) 1 расстояний). Вероятность р = РуС є Xу М из (2.2.10) отображается под заголовком «МНП: вероятность успеха». Эта вероятность зависит от параметров М и Т, поэтому далее показаны экспериментальные графики зависимости р только от этих параметров.
Для оценки оптимальных значений параметров N, М и Т воспользуемся базой данных фотографий [69], использовавшейся ранее в экспериментах из разделов 1.3 и 2.3. После ее разбиения на две части и последующей группировке и выделении информационных центров-эталонов в каталоге db была создана БД объемом R=980 фотографий лиц. Результаты процедуры поиска оптимальных порогов для этого эксперимента показаны на рис. 3.3.3. Согласно этим результатам, для создания БД использовался нижний порог ВИР /?Q =0,097. Для тестирования качества распознавания при различных значениях параметров программа разбиения скопировала в каталог test другие 1221 изображения.
Далее на рисунках приведены зависимости среднего количества вычислений ВИР для МНП и вероятности р от значений трех основных параметров (N,M,T). При тестировании два параметра принимали фиксированные значения (см. подписи к рисункам), а третий менялся с помощью диалогового окна «Параметры», описанного ранее в этом разделе. Так как значение порога для ВИР во всех случаях оставалось фиксированным, то и вероятность верного распознавания для всех -экспериментов варьировалась незначительно и составила в среднем 95%.
Напомним, что МНП представляет собой рандомизированный алгоритм планирования эксперимента в задаче АРИ. Это означает, что даже для одинаковых значений всех параметров результат - среднее количество вычислений ИР (n/R) - может оказаться различным (±0,5%), поэтому графики зависимости величины n/R от параметров не являются идеально гладкими.
Распознавание изолированных слов методом направленного перебора
Использовалась первоначальная (не модифицированная) версия МНП с экстраполяцией ВИР на основе АР-модели. Действительно, процедура АР-анализа является частью первого этапа по выделению ЭРЕ, поэтому ее использование на втором этапе можно признать уместным. Здесь среднее количество проверок составило примерно 26% от объема ЭС. С вероятностью 80% это количество не превышает 5000 или 50% от общего числа слов-эталонов для проверки. При этом в 100% случаев было получено абсолютно точное решение X = Xг . Таким образом, описанный эксперимент убедительно доказал, что МНП совместно с принципом МИР может успешно применяться и в такой сложной задаче, как автоматическое распознавание речи. 4.3. Задача прогнозирования рынка ценных бумаг. К числу центральных задач статистического анализа, особенно в экономике, относится задача прогнозирования случайных временных рядов по конечным выборкам наблюдений. В настоящее время одной из наиболее актуальных задач такого рода стало планирование и организация биржевой игры на фондовом рынке, или рынке ценных бумаг. Эта задача, в отличие от АРР, обычно не рассматривается в контексте распознавания образов. Однако в этом разделе показано, что, сводя задачу прогнозирования к задаче классификации,, могут быть получены результаты, весьма интересные не только для специалистов-исследователей, но и для практиков биржевой игры. Задача планирования игры на очередную торговую сессию (рабочий день биржи) состоит в предвидении или прогнозировании поведения рыночных цен на ближайшие будущие торговые сессии [107]. В рамках популярного технического анализа [108] решение этой задачи связано с прогнозированием изменений цен в будущем только на основе анализа изменений цен в прошлом. Проблема заключается в том, что используемые прогнозы принципиально ограничены по своей точности и надёжности, т.е. сопровождаются значительными ошибками ввиду воздействия на рыночную конъюнктуру множества случайных, не учитываемых факторов. Действительно, на формирование рыночной конъюнктуры действуют два механизма [109]. Первый из них доминирует на стабильном рынке и реализует в своей основе принцип саморегулирования курса ценных бумаг в процессе осуществляемых торгов. В теории биржевой игры он отображается в виде вполне определённой математической модели поведения рынка в динамике. Второй механизм отталкивается от возможности внешних корректировок рыночных цен в интересах какой-либо группы влиятельных участников рынка (любая их реакция на важные текущие общественные события в форме массовых покупок или продаж, по сути, и есть такая корректировка рынка). Планирование биржевой игры в указанных условиях находится в прямой зависимости от той или иной альтернативы поведения рынка в динамике, т.е. должно носить многоолътернативный характер. \ Таким образом, постановка задачи создания автоматизированной системы прогнозирования динамики рынка о, жестким безальтернативным решением на основе идей технического анализа представляется недостаточно разумной. Корректнее ставить задачу о создании системы поддерлски принятия решения (СППР) [НО], которая может предоставить трейдеру информацию о тех периодах изменения цены в прошлом, которые наиболее подходят для текущей рыночной ситуации. Найденные периоды и будут представлять собой различные альтернативы планирования биржевой игры. В результате задача оптимального планирования сводится к задаче распознавания образов, поэтому для ее решения может быть применен принцип МИР. Однако нельзя не отметить существенное ограничение на пути практической реализации указанного подхода -объем исторической информации обычно настолько велик, что полный перебор всевозможных альтернатив может оказаться неприемлем. В данном разделе для ослабления указанной проблемы вычислительной сложности предлагается использовать модификацию синтезированного в главе 2 МНП. Рассмотрим некоторый конкретный вид ценных бумаг. Обозначим для них цену закрытия по результатам рабочего дня биржи как c(1)(t), где / =1,2,...- дискретное время или порядковый номер торговой сессии в ряду других, предшествующих ей сессий. Тогда конечная разность первого порядка x(!)(t)=c(J)(t)-c(! (t-l) будет характеризовать приращение цены в процессе осуществляемых торгов. При x(1)(t) 0 говорят о росте курса соответствующей ценной бумаги,при x(l (t) 0 - о его падении. Наилучшим планом игры в первом случае является, очевидно, покупка ценных бумаг в начале и продажа в конце сессии. Напротив, при снижении цен сначала должна производиться продажа данных акций. При этом большое значение имеет и последующая динамика рынка в моменты t+1, f+2,..., t+k, где к -длина интервала прогнозирования.
Задача состоит в нахождении ситуаций в прошлом, наиболее близких к текущей динамике курса ценной бумаги [I ll]. Для ее решения требуется, в первую очередь, задать размер И (в днях) периода, на котором курс цен является однородным [112]. Кроме того, заметим, что цена закрытия c(l)(t) - хоть и наиболее важный, но далеко не единственный показатель, описывающий рыночную ситуацию. Так, в большинстве исторических бюллетеней помимо цены закрытия указываются цена открытия, наибольшая и наименьшая цена за сессию и пр. Обозначим весь набор параметров, которые, по мнению исследователя, наиболее адекватно характеризуют конъюнктуру рынка
