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

• Автор: Савченко, Андрей Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 152 с.

Оглавление
Введение

Глава 1. Задача распознавания полутоновых изображений.

1.1. Статистический подход

1.2. Критерий минимума информационного рассогласования

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

1.4. Выводы.

Глава 2. Метод направленного перебора альтернатив.

2.1. Метрические свойства статистики МИР

2.2. Синтез алгоритма.

2.3. Результаты экспериментальных исследований

2.4. Выводы.
Глава 3. Разработка информационной системы
3.1. Архитектура информационной системы.
3.2. Интерфейс информационной системы.
3.3. Программа и результаты экспериментальных исследований
. Выводы.
Глава 4. Перспективы применения метода направленного перебора в других задачах классификации.
4.1. Задача автоматического распознавания речи.
4.2. Распознавание изолированных слов методом направленного перебора.
4.3. Задача прогнозирования рынка ценных бумаг.
4.4. Выводы
Заключение
Библиографический список.
Приложения
Приложение А.Патент на полезную модель.
Приложение Б. Свидетельство о государственной регистрации
программы для ЭВМ
Приложение В. Акт о выполнении работ по проекту НФ ГУВШЭ
Приложение Г. Акт о внедрении Ф ГУВШЭ
Приложение Д. Акт о внедрении ООО Теком
Приложение Е. Диплом III Всероссийской конференции
Искусственный интеллект философия, методология, инновации
МИРЭА,
Обозначения и сокращения
АР авгорсгрессия
АРИ автоматическое распознавание изображений
АРР автоматическое распознавание речи
БД база данных
БЭД база эталонных данных
ВИР величина информационного рассогласования
ГА генетический алгоритм
ИР информационное рассогласование
ИС информационная система
ИТД информационный центр
ИТВР информационная теория восприятия речи
МИР минимум информационного рассогласования
МНИ метод направленного перебора
МП максимальное правдоподобие
ОНИ обьекты нечисловой природы
СПМ спектральная плотность мощности
ЭРЕ элементарная речевая единица
X входной объект изображение, речевой сигнал для распознавания
Я количество эталонов в базе данных г номер альтернативы из К вариантов
Хг база эталонных данных
РкьХХг информационное рассогласование КульбакаЛейблера между входным объектом X и эталоном X г
РХ 1ХГ расстояние Манхэттена между входным объектом X и эталоном Xг
Ох выборочная оценка спектральной плотности мощности сигнала
Сг спектральная плотность мощности сигнала г из словаря эталонов
Р0 пороговый уровень по ВИР для досрочного окончания перебора
Р пороговый уровень но ВИР для выбора информационного го элемента.
Введение
Актуальность


Например, в упомянутой выше задаче идентификации личностей по фотографиям лиц современные базы данных содержат тысячи изображений. Поэтому их полный перебор требует недопустимо больших затрат по времени и, как результат, не может быть реализован в режиме реального времени []. Традиционный подход для преодоления указанной проблемы основан на разбиении классов на подклассы (кластеризация) образов [9, ] и последующем сохранении в базе данных только наиболее информативных эталонов из каждого кластера. К сожалению, в настоящее время подобное решение на практике зачастую признается неудовлетворительным ввиду недостаточно сильного достигаемого с его помощью эффекта редукции данных. А многочисленные методы, основанные на математическом аппарате деревьев решений [], оказываются эффективными лишь в тех редких случаях, когда группы однородных изображений в пределах каждого кластера сходны между собой и одновременно резко отличаются от изображений из других кластеров []. Поэтому чаще всего на практике ускорение вычислений для больших БЭД производится за счет потерь в качестве АРИ. Например, в работе [] все изображения на этапе предварительной обработки приводятся к масштабу 4x4 пикселя. К числу известных способов сокращения вычислительных затрат без существенных потерь в качестве распознавания изображений, помимо отмеченных выше алгоритмов кластеризации, можно указать на устройство мгновенного распознавания изображений []. Однако недостатком этого устройства является жесткое ограничение на полноту множества распознаваемых изображений. На практике же распознаваемое изображение, как правило, не дублирует ни один из эталонов. Проблема вычислительной сложности алгоритмов АРИ в этом случае еще более обостряется. Со всех перечисленных точек зрения несомненный интерес представляет общесистемный принцип минимума информационного рассогласования (МИР) в метрике Кульбака-Лейблера []. ИТВР) [] показала высокие результаты в одном из наиболее актуальных направлений статистической классификации - в задаче автоматического распознавания речи (АРР) []. Высокая чувствительность к информационным различиям в сигналах при относительно высокой степени помехозащищенности их обработки и, главное, радикальное решение проблемы вариативности через строгое определение понятия речевого кластера данных и его информационного центра-эталона далеко не полный перечень достоинств ИТВР. Между тем, ггс все преимущества и возможности принципа МИР на данный момент получили необходимое освещение и развитие в научных исследованиях. В частности, до настоящего времени практически не исследовались возможность его применения в задачах АРИ, для которых проблема больших БЭД особенно актуальна. Исследования в этом направлении и составляют главное содержание представленной диссертационной работы. Объект и предмет исследования. Вычислительные методы классификации изображений и таблиц данных в задачах с большими объёмами баз данных. Цель диссертационного исследования. Основная цель диссертационной работы состоит в разработке методов ускорения вычислительной процедуры классификации в условиях большого количества альтернатив - на основе принципа минимума информационного рассогласования и предлагаемого метода направленного перебора альтернатив (МНП). Выбор и обоснование теоретико-вероятностной модели изображения. Реализация предложенного вычислительного метода в виде комплекса программ для проведения экспериментальных исследований его эффективности в реальных задачах АРИ с БЭД большого объёма. Исследование возможностей и перспектив применения МНП в других актуальных задачах классификации. Методы исследования. Для решения поставленных задач в работе использовались современные методы теории распознавания образов, теории вероятностей и математической статистики, математического моделирования, теории информации, теории сигналов, а также информационной теории восприятия речи []. Научная новизна работы состоит в следующем. Предложена новая тсоретко-вероятиостная модель полутонового изображения с целью применения к задаче распознавания принципа минимума информационного рассогласования в метрике Кульбака-Лейблера.