Библиотека ДИССЕРТАЦИЙ

Главная страница Обмен ссылками Каталог

Книги
Статьи
О сайте
Авторские права
О защите
Для авторов
Бюллетень ВАК
Новости
Поиск
СУПЕРОБУЧЕНИЕ Полезные ссылки

Введите слово для поиска

Научные статьи, тезисы, монографии, учебники.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

Факультет Вычислительной математики и кибернетики

Кафедра «Математических методов прогнозирования»

 

Учебный план дисциплины

«Математические методы распознавания образов»

 

 

Характеристика учебной дисциплины.

Годовой кафедральный курс для студентов 3 курса кафедры ММП (5-6 семестры).

5 семестр:       лекции ‑         2 ч./нед,                      36 ч.

6 семестр:       лекции ‑         2 ч./нед,                      32 ч.

______________________________________________

Итого аудиторных часов                                          68

Форма контроля ‑ экзамен в 6-м семестре.

 

 

 

 

 

Разработали

Академик РАН, д.ф.м.-н., профессор Ю.И. Журавлев,

к.ф.-м.н., доцент С.И. Гуров

Лектор

к.ф.-м.н., доцент С.И. Гуров

 

Москва, 1999


ВВЕДЕНИЕ

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

·        отнесение объекта или ситуации к некоторым заранее заданным классам;

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

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

и т.д.

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

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

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

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

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

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

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

Программа дисциплины

5-й семестр

1. Основные понятия распознавания образов. Постановка задачи распознавания

Феномен узнавания как свойство живых высокоорганизованных систем. Примеры (узнавание знакомого объекта, понимание речи, чтение текстов, дешифрирование аэро- и космоснимков, распознавание изображения, состояния устройств, систем, экономических объектов и т.д.). Принцип эмпирической индукции Ф. Бэкона. Определение основных понятий: распознавание образов (РО), объекты и образы, признак, классы. Прецедент ‑ образ с известной классификацией. Описание классов зависимостями и прецедентами. Принятие решений на основе моделирования (Model Base Reasoning) и по прецедентной информации (Case Base Reasoning). Классификация и прогнозирование. Этапы развития РО.

2. Задачи, возникающие при разработке распознающих систем

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

Два направления исследований в РО ‑ построение алгоритмов распознавания и поиск оптимального признакового пространства.

Представление исходных данных (описание объектов). Обоснование теории РО (гипотеза компактности). Пример М.М. Бонгарда. Типы признаков: числовые (детерминированные и вероятностные), функциональные, графические, структурные и т.д. Зависимость качества распознавания от размерности признакового пространства.

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

Выбор метода распознавания. Определение типа алгоритма и выбор эвристического метода. Типы задач распознавания: распознавание без обучения, распознавание с обучением (с учителем), распознавание с самообучением (без учителя). Дискриминантные и синтаксические (структурные) методы распознавания. Понятие о статистических, R-, П-, Г- и Lмоделях распознавания.

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

3. Примеры алгоритмов РО различных типов

Распознавание без обучения ‑ дискриминантная функция Фишера. Расстояние Махаланобиса. Распознавание с обучением ‑ персептрон. Формальный нейрон в простейшей модели Мак-Калока‑Питтса. Распознавание с самообучением ‑ понятие кластера и простейший алгоритм кластеризации.

4. Системы РО с обучением (детерминистский подход). Простейшие метрические алгоритмы

Детерминированные и стохастические системы и алгоритмы РО. Системы РО с памятью и без памяти и соответствующие им алгоритмы ‑ с принудительным обучением и рекуррентные.

Классификация с помощью функции расстояния. Случаи единственности и множественности эталонов классов. Методы q-NN.

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

Алгоритмы классификации, основанные на функции разделения (R- модели распознавания). Некорректность задачи разделения классов гиперповерхностями. Случаи разделимости: индивидуальная и попарная отделимость. Простейший алгоритм разделения двух подмножеств в Rn, его достоинства, недостатки и адаптация для Bn.

Методы построения разделяющих гиперплоскостей. Конечно-сходящиеся алгоритмы. Критерий разделимости. Рекуррентные алгоритмы с поощрением. Теорема А. Новикова. Критерий остановки.

Градиентные алгоритмы построения разделяющих гиперплоскостей. Примеры градиентных алгоритмов (персептронный, дробной коррекции и т.д.). Алгоритм, основанный на минимизации среднеквадратичной ошибки (НСКО-алгоритм). Понятие о методе обобщенного портрета. Построение разделяющей гиперплоскости в Rn как задача квадратичного программирования. Достоинства и недостатки рассмотренных алгоритмов.

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

Дискретный метод нахождения максимальной совместной подсистемы неравенств. Верхние нули и нижние единицы монотонных булевых функций. Задача расшифровки булевой функции. Понятие о функции Шеннона. Алгоритм Н.Н. Катериночкиной и его свойства. Приближенный алгоритм расшифровки монотонной булевой функции.

6. Метод комитетов в распознавании образов

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

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

7. Разделение классов нелинейными гиперповерхностями

Нелинейная разделимость классов. Спрямляющее пространство. Равномерная и интегральная функциональные метрики. Полная система элементов линейного нормированного пространства. Вероятность ошибки распознавания. Теорема об аппроксимации в L2 произвольной функции полной системой элементов. Трудности определения коэффициентов аппроксимации.

Полные ортонормированные системы функций одной переменной и их свойства. Классические ортогональные полиномы. Построение семейств аппроксимирующих функций многих переменных.

Квадратичные и полиномиальные дискриминантные функции.

8. Системы РО с обучением (вероятностный подход). Методы теории статистических решений

Вероятностная постановка задачи распознавания. Методы минимизации среднего риска (применение теории статистических решений, переход к минимизации эмпирического риска, методы стохастической аппроксимации).

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

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

9. Минимизация эмпирического риска

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

Понятие функции роста класса решающих правил. Число возможных дихотомий конечного числа точек из Rn в классе линейных и аффинных разделяющих правил. Максимальное число областей разбиения евклидова пространства конечным числом гиперплоскостей проходящих через начало координат и общего положения (функция Ф(n,l)).

Индекс класса решающих правил относительно набора прецедентов из тренировочной последовательности. Функция роста класса решающих правил. Примеры функций роста для различных систем «пространство признаков ‑ набор решающих правил». Емкость класса решающих правил. Свойства функции F(n,l). Лемма о свойстве индекса системы решающих правил. Теорема об основном свойстве функции роста. Теорема о достаточных условиях равномерной сходимости эмпирического риска к среднему.

6-й семестр

10. Метод потенциальных функций в РО.

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

МПФ как подкласс процедур Роббинса-Монро решения уравнений регрессии. Виды функции потерь в зависимости от постановки задачи распознавания. Теорема о сходимости процедуры Роббинса-Монро почти наверное (без доказательства).

Идея МПФ. «Наивный» МПФ и его недостатки. Примеры потенциальных функций. Алгоритм МПФ для РО. Предположения (гипотезы Н1, Н2, Н3 и Н4) МПФ. Геометрическая интерпретация метода, его «персептронная» реализация. Теорема о представлении потенциальной функции в виде Н3 (без доказательства). Выбор функциональной системы для разложения потенциальной функции. Примеры применения алгоритма МПФ для «персептронной» и «машинной» реализации.

Экстремизируемый функционал МПФ. Ложное решение. Сходимость процедуры МПФ. Гипотеза Н5 МПФ. Терема о сходимости разделяющей функции к характеристической (без доказательства). Теорема Розенблатта-Новикова о скорости сходимости. Терема о свойствах сходимости МПФ.

11. Логические модели распознавания.

Характеристика логических моделей распознавания, их достоинства и недостатки. Разделяющие алгоритмы, основанные на построении ДНФ. Понятие частичной булевой функции (ч.б.ф). Сокращенная ДНФ ч.б.ф. и ее построение. Алгоритм минимизации ДНФ ч.б.ф. Пример.

Разделяющие алгоритмы, основанные на использовании логических деревьев. Понятия решающего дерева (РД), полного и неполного РД, проектора как признакового предиката и бинарного решающего дерева (BDT). Перечисление BDT. Производящая функция для числа неизоморфных BDT с m внутренними вершинами, построенных с использованием не более чем n предикатов (признаков). Алгоритм построения BDT. Пример. Оценка надежности BDT. Трудности синтеза оптимальных BDT. Эвристические приемы построения оптимальных BDT.

12. Алгоритмы, построенные на принципе голосования.

Принцип частичной прецедентности, алгоритмы голосования и Г-модели РО. Понятие элементарного классификатора. Типы алгоритмов голосования: алгоритмы, основанные на использовании представительных наборов; тестовые алгоритмы; алгоритмы вычисления оценок (АВО).

Г-модели с представительными наборами. Обучающая таблица Т и опорные множества. Подтаблицы Т, связанные с данным классом Kt по данному опорному множеству J. Понятие представительного набора для класса Kt  по опорному множеству J. Тупиковый представительный набор и eпредставительный набор, их связь с неприводимым покрытием бинарной таблицы и трудности их построения.

Тестовые алгоритмы. Тестовые наборы и матрица Lt таблицы Т. Тупиковые тесты и их связь с неприводимыми покрытиями матрицы Lt. Пример: отличие тестового алгоритма от алгоритма, основанные на построении ДНФ.

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

Основные элементы АВО: система опорных множеств (о.м.); функция близости двух объектов; правила вычисления оценок близости между объектами по данному о.м., между объектом и классом по данному о.м., между объектом и классом по системе о.м.; решающее правило. Причины ограничения совокупности признаков при РО и варианты задания о.м. Примеры задания функции близости между объектами по данному о.м. и оценок близости между объектом и классом по данному о.м. и по системе о.м. Стандартные решающие правила.

Понятия о параметрической оптимизации АВО и об алгоритмическом подходе к задачам РО. Распознающий оператор и решающее правило. Двухуровневая система РО и корректор распознающих операторов. Корректные множества алгоритмов РО.

Проблема построения эффективных формул вычисления оценок Гt(S) близости между объектом и классом по системе о.м. Условия получения эффективных формул вычисления оценок (пороговость и симметричность функции близости, аддитивность веса о.м.). Два метода построения простых формул для Гt(S). Правильные системы о.м. Примеры получения эффективных формул Гt(S) для некоторых случаев о.м. и функций близости.

13. Структурные (синтаксические) методы РО.

«Лингвистический» подход к РО как альтернатива дискриминантному подходу. Случаи эффективности синтаксических методов. Примитивы и разложение образа на примитивы. Порождающая грамматика. Этапы построения и работы структурной системы РО. Обработка изображений как специфический класс задач РО. Предварительная обработка объекта (примеры: дискретизация, квантование уровня, кодирование, задачи реставрации изображений). Представление объекта в виде слова некоторого формального языка (сегментация и выделение примитивов). Определение принадлежности слова формальному языку. Синтез формальных грамматик.

Основные понятия теории формальных грамматик. Три основных вопроса теории формальных языков: порождение слов, разрешимость языка, восстановление грамматики. Разрешимые (рекурсивные) и перечислимые (рекурсивно перечислимые) и регулярные множества. Примеры грамматик порождающих простые графические образы. Иерархия грамматик и языков по Н. Хомскому (языки типа 0, 1, 2 и 3). Примеры. Перечислимость языков типа 0. Разрешимость языков типа 1. Регулярность языков типа 3. Обобщения КС-грамматик (языки типа 1,5). Программные грамматики.

Алгоритм восстановления регулярных грамматик в РО.

 

ЛИТЕРАТУРА

Обязательная

1.      Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. ‑ М.: Наука, 1970.

2.      Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Стохастические проблемы обучения. ‑ М.: Наука, 1974.

3.      Журавлев Ю.И. Избранные научные труды. – Изд. Магистр, 1999.

4.      .Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. ‑ М.: Наука, 1990.

5.      Ту Дж., Гонсалес Р. Принципы распознавания образов. ‑ М.: Мир, 1978.

6.      Фомин В.Н. Математическая теория обучаемых опознающих систем. ‑ Л.: ЛГУ, 1976.

Дополнительная

1.      Автоматический анализ сложных изображений / Сб. пер. под ред. Э.М. Бравермана. ‑ М.: 1969.

2.      Алгоритмы обучению распознаванию образов / Под. ред. В.Н. Вапника. – Сов. радио, 1973.

3.      Андерсон Т. Введение в многомерный статистический анализ. – М.: 1963.

4.      Бонгард М.М. Проблема узнавания. ‑ М.: Наука, 1967.

5.      Ванцвайг М.Н. Алгоритм обучению распознаванию образов «Кора» // Алгоритмы обучению распознаванию образов. – М.: Сов. радио, 1973. – С. 82-91.

6.      Вапник В.Н. Восстановление зависимостей по эмпирическим данным. ‑ М.: Наука, 1979.

7.      Гинзбург С. Лекции о контекстно-свободных языках / Алгебраическая теория автоматов, языков и полугрупп. Под. ред. М. Арбиба. ‑ М.: Статистика, 1975. ‑ С. 298 ‑ 310.

8.      Гоппа В.Д. Введение в алгебраическую теорию информации. ‑ М.: Наука, 1995.

9.      Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания: Некоторые аспекты. ‑ М.: Радио и связь (Кибернетика), 1985.

10.  Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1977.

11.  Гуревич И.Б., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика, 1974, № 3. – С. 16-20.

12.  Диде Э. Методы анализа данных. ‑ М.: Финансы и статистика, 1985.

13.  Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // Журнал вычислит. матем-ки и математич. физики, 1982, т. 22, № 4. – С. 963-974.

14.  Дюкова Е.В. Алгоритмы распознавания типа «Кора»: сложность реализации и метрические свойства // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. – М.: Наука, 1989. – С. 99-125.

15.  Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание. Классификация. Прогноз. Математические методы и их применение. Вып. 1. – М.: Наука. 1989. – С. 9-16.

16.  Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. – М.: Наука, 1989. – С. 5-72.

17.  Минский М., Пейперт С. Персептроны. ‑ М.: Мир, 1971.

18.  Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 1971, № 2. С. 140-146.

19.  Классификация и кластер / Под ред. Дж. Вэн Райвин; Пер. с англ. под ред. Ю.И. Журавлева. М.: Мир, 1978.

20.  Катериночкина Н.Н. Поиск максимального верхнего нуля монотонной функции алгебры логики // ДАН СССР, т. 224, № 3, 1975. – С. 557-560.

21.  Нильсон Н. Обучающиеся машины. ‑ М.: Мир, 1967.

22.  Рудаков К.В. О числе гиперплоскостей, разделяющих конечные множества точек // ДАН СССР, 1976, т. 231, № 6. – С. 1296-1299.

23.  Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание. Классификация. Прогноз. Математические методы и их применение. Вып. 1. – М.: Наука. 1989. – С. 229-279.

24.  Себестиан Г.С. Процессы принятия решений при распознавании образов. ‑ Киев: Техника, 1965.

25.  Фу К. Структурные методы в распознавании образов. ‑ М.: Мир, 1977.

Биология
Ветеринария
Геология
Искусствоведение
История
Культурология
Медицина
Педагогика
Политика
Психология
Сельхоз
Социология
Техника
Физ-мат
Филология
Философия
Химия
Экономика
Юриспруденция

Подписаться на новости библиотеки


Пишите нам
X