История исследований и развития методов распознования образов

Введение
Возникновение методов
Статистический метод
Нейронные сети
Логические правила и деревья решений
Алгоритмы нечеткой логики
Список литературы

История исследований и развития методов распознования образов

В связи с данной оценкой роли нейронных сетей для собственно
распознавания хотелось бы отметить следующее: нейронные сети, будучи чрезвычайно сложным объектом для математического анализа, при грамотном их использовании, позволяют находить весьма нетривиальные законы в данных. Их трудность для анализа, в общем случае, объясняется их сложной структурой и как следствие, практически неисчерпаемыми возможностями для обобщения самых различных закономерностей. Но эти достоинства, как это часто и бывает, являются источником потенциальных ошибок, возможности переобучения. Как будет рассказано далее, подобный двоякий взгляд на перспективы всякой
модели обучения является одним из принципов машинного обучения.
Еще одним популярным направлением в распознавании являются логические правила и деревья решений. В сравнении с вышеупомянутыми методами распознавания эти методы наиболее активно используют идею выражения наших знаний о предметной области в виде, вероятно самых естественных структур - логических правил. Под элементарным логическим правилом подразумевается высказывание типа «если неклассифицируемые признаки находятся в соотношении X то
классифицируемые находятся в соотношении Y».
Для поиска логических правил в данных необходимы 2 вещи:
определить меру «информативности» правила и пространство правил.
И задача поиска правил после этого превращается в задачу полного
либо частичного перебора в пространстве правил с целью нахождения наиболее информативных из них. Пространство поиска определяется стандартно. Предположим, что объект в нашей задаче характеризуется
некласифицируемыми X и нужно установить значение классифицирумого признака y вне прецедентных данных. Тогда пространство состоит из правил вида «если все a<x<b то y=c», причем число термов k слева ограничивается для того, чтобы избежать переобучения.
После нахождения достаточно информативных правил наступает
фаза «сборки» правил в конечный классификатор. Не обсуждая глубоко проблемы которые здесь возникают(а их возникает немалое количество) перечислим 2 основных способа «сборки». Первый тип - линейный список. Пусть даны правила вида β → с , тогда результирующий классификатор определяется по принципу:
Второй тип – взвешенное голосование, когда каждому правилу
ставится в соответствие некоторый вес, и объект относится классификатором к тому классу за который проголосовало наибольшее количество правил.
В действительности, этап построения правил и этап «сборки»
выполняются сообщя и, при построении взвешенного голосования
либо списка, поиск правил на частях прецедентных данных вызывается снова и снова, чтобы обеспечить лучшее согласование данных и модели.
Примыкают к логическим правилам и деревья классификации. В
этом случае алгоритм классификации задается бинарным деревом. При
классификации объекта X, он проходит по дереву путь от корня до
некоторого листа, в соответствии со следующим алгоритмом:

Фактически, бинарные деревья классификации выражают идею построения промежуточных "концептов", которым соответствуют вершины дерева.
Большой вклад в развитие теории распознавания и классификации внесли советские и, в последующем, российские ученые: Айзерман, Браверман, Розоноэр (метод потенциальных функций /1/), Вапник, Червоненкис (статистическая теория распознавания, метод «обобщенный портрет» /2/), Мазуров (метод комитетов /11/), Ивахненко (метод группового учета аргументов /9/), Загоруйко (алгоритмы таксономии и анализа знаний /7,8/), Лбов (логические методы распознавания и поиска зависимостей /10/). Рассмотрим некоторые из них более подробно.
Теория Вапника-Червоненкиса
Заметим, что обоснование методов распознавания является
характерной особенностью именно статистического подхода. Это и
неудивительно - никакая другая формализация распознавания не имеет столь глубоко разработанную математическую основу как статистический подход, базой которого служит теория вероятности. И хотя попытки создать математическую основу, отличную от вероятностной, для оценок качества алгоритмов предпринимаются, ни одну из них успешной назвать пока нельзя.
Что вообще в данном случае подразумевается под обоснованием? Чтобы понять это рассмотрим модельную(и классическую) задачу распознавания образов. Пусть в пространстве R заданы конечное число объектов 2 классов: A и B. Объекты классов A и B появляются с некоторыми неизвестными вероятностями Ap и Bp соответственно, причем распределения объектов A и B подчиняются нормальному закону. И требуется построить решающее правило, которое разделяло бы пространство R на 2 подмножества - объекты класса A и B, и причем с малой вероятностью ошибалась бы на внешних данных. Эта задача была рассмотрена в 1936 г. Рональдом Фишером, который и разработал теорию ее решения. Фишер предложил следующее решение: вначале оценить по обучающей выборке вероятности Ap и Bp , а затем оценить параметры нормальных законов элементов из A и B. Далее решающее правило имело интуитивно очевидный вид: объект классифицировался как A, если выполнялось одно условие и классифицировался как B, если выполнялось другое условие.
Итого, для того, чтобы данный алгоритм хорошо обобщал
требуется чтобы на обучении было достаточно много объектов как класса A так и B, и эти классы были достаточно отлично друг от друга распределены. Этим качественным соображениям соответствует достаточно хорошо проработанная количественная статистическая теория оценок.
В конце 60х начале 70х годов В.Н.Вапником и А.Я.Червоненкисом была создана статистическая теория распознавания, которая несмотря на некоторые свои недостатки, и стала основным инструментом в обосновании методов распознавания.
Выглядит она следующим образом:
Дальнейшее развитие теории Вапника-Червоненкиса заключалось доказательстве для многих методов обучения конечности VC-размерности. Выяснилось, что для параметрических моделей обучения, как правило, VC-размерность имеет порядок числа параметров необходимых для настройки модели.
Композиции методов распознавания.
Как следует из теории VC, если в низкоразмерном пространстве разделена куча объектов, мы понимаем, что это «неслучайно» и должны радоваться. Но вероятность такой «неслучайности» мала и объекты могут не разделиться. Но мы не унываем и полагаем, что раз в данных нет закономерности типа линейной разделимости, то могут быть и другие! Мы применяем другой алгоритм распознавания и т.д. до тех пор, пока не получим результат.
Таким образом, если у нас нет априорных знаний о виде, в котором нужно искать закономерности, ничего не остается как пробовать различные модели – метрические, основанные на логических правилах и т.д.
Если посмотреть на данную схему с точки зрения теории VC, то можно заметить, что функция роста такой «метамодели» будет суммой функций роста каждой из моделей участвующих в ней. Такое относительно незначительное усложнение может тем не менее серьезно улучшить способность удовлетворить ограничения обучающей выборки, при отсутствии априорных знаний о данных.
Однако вполне возможен и такой вариант, когда какие-то законы в данных ловятся посредством одной модели, а какие-то посредством другой.
Интенсивные исследования проводились с конца 60-х годов в ВЦ АН СССР (в настоящее время ВЦ им А.А.Дородницына РАН). Еще в начале 60-х академиком РАН Журавлевым был предложен тестовый алгоритм распознавания – логический метод эффективного решения задач распознавания при малом числе обучающих прецедентов /3/. В дальнейшем на базе этого алгоритма Журавлевым был построен новый класс распознающих процедур – алгоритмы вычисления оценок, а затем введена и исследована алгебраическая теория распознавания /8/. В этом направлении фундаментальные результаты получили также чл.корр. РАН Рудаков (общая теория проблемно-ориентированного алгебраического синтеза корректных алгоритмов, чл.корр. РАН Матросов (статистическое обоснование алгебраического подхода ), Рязанов (оптимизация моделей классификации, коллективные решения задач кластерного анализа /12,13/), Дюкова (асимптотически-оптимальные логические алгоритмы), Сенько (алгоритмы взвешенного статистического распознавания), Асланян (логические алгоритмы распознавания), Донской (решающие деревья) и многие другие исследователи России, СНГ и дальнего зарубежья
Математический формализм который возникает при анализе подобных алгоритмов весьма сложен. Это и неудивительно, сложно получить объяснения работы ансамбля сложно взаимодействующих алгоритмов, если до сих пор непонятно, почему может работать один.
Однако уже сейчас понятно, что одним из основных вопросов интересующих теорию композиций алгоритмов являются условия при которых соответствующие модели смогут обеспечить полное удовлетворение ограничений обучающей выборки – так называемые условия разрешимости. На этой идее основывается весьма глубокая теория локальных и универсальных ограничений выдвинутая К.В. Рудаковым.
Статистическое рассмотрение конструкций алгебраического подхода показало, что ассимптотическое обоснование(а других пока от статистики и не дождешься) для некоторых композитных алгоритмов, типа бустинга, алгебраических расширений АВО, так же может быть найдено.
В последние годы появились узкоспециализированные пакеты интеллектуального анализа данных. Для данных пакетов часто характерна ориентация на узкий круг практических задач, а их алгоритмической основой является какая-либо одна из альтернативных моделей, использующая нейронную сеть, решающие деревья, ограниченный перебор, и т.п. Ясно, что подобные разработки существенно ограничены при практическом использовании. Во-первых, заложенные в них подходы не является универсальными относительно размерностей задач, типа, сложности и структурированности данных, величины шума, противоречивости данных, и т.п. Во-вторых, созданные и «настроенные» на решение определенных задач, они могут оказаться совершенно бесполезными для других. Наконец, множество задач, представляющих интерес практическому пользователю, обычно шире возможностей отдельного подхода. Например, пользователю может быть важно иметь численную характеристику надежности некоторого прогноза, но «решающее дерево» ее не вычисляет. «Нейронная сеть» выступает в роли «черного ящика», предлагающего некоторый прогноз без его обоснования. Логические методы распознавания позволяют выявлять логические закономерности в данных и использовать их при прогнозировании, но при наличии линейных зависимостей между признаками и прогнозируемой величиной точность прогноза, сделанного «линейной машиной», может быть заметно выше.
Таким образом, на настоящем уровне развития методов решения задач распознавания, представляется предпочтительным путь создания программных средств, включающих основные существующие разнообразные подходы. В данном случае повышаются шансы подбора из имеющихся алгоритмов такого алгоритма, который обеспечит наиболее точное решение интересующих пользователя задач на новых данных. Другим важным атрибутом систем анализа и классификации должно быть наличие средств автоматического решения задач распознавания и классификации коллективами алгоритмов. Действительно, стандартной ситуацией является наличие нескольких альтернативных алгоритмов или решений, равнозначных для пользователя. Для выбора из них одного наиболее предпочтительного не хватает информации. Тогда естественной альтернативой выбору является создание на базе имеющихся алгоритмов или решений новых, более предпочтительных.
Теоретические основы практической реализации идеи решения задач анализа данных коллективами алгоритмов были разработаны в ВЦ РАН в рамках алгебраического подхода для решения задач распознавания (логическая и алгебраическая коррекция алгоритмов) в 1976-1980 /5, 6/ и комитетного синтеза классификаций для задач кластерного анализа (автоматической классификации) в 1981-1982 годах /12,13/. Позднее появились исследования в данной области и в других странах.
В алгебраическом подходе новые алгоритмы распознавания строятся в виде полиномов над исходными алгоритмами (применение алгебраических корректоров) или в виде специальных булевских функций (логических корректоров). Теоретическим базисом является теорема о существовании для произвольного алгоритма распознавания ему эквивалентного стандартного алгоритма, представимого в виде произведения распознающего оператора и решающего правила /8/. Это позволяет описать основные результаты вычислений произвольных алгоритмов распознавания в стандартном виде с помощью числовых матриц оценок («мер принадлежности» объектов к классам) и информационных матриц окончательных ответов (классификаций). Матрицы оценок различных распознающих алгоритмов являются «исходным материалом» для синтеза в виде полиномов новых матриц оценок, которые задают основу нового скорректированного решения задачи распознавания. Алгебраический подход позволяет строить алгоритмы, безошибочные на «обучающем» материале или совершающие меньшее число ошибок, чем каждый из исходных алгоритмов.
Нейронечеткие системы
Теория нечетких множеств (fuzzy sets theory) ведет свое начало с 1965 г., когда профессор Лотфи Заде (Lotfi Zadeh) из университета Беркли опубликовал основополагающую работу «Fuzzy Sets» в журнале «Information and Control» [Zadeh L. Fuzzy sets // Information and Control. - 1965. - №8. - P. 338-353. ]. Прилагательное «fuzzy», которое можно перевести на русский как нечеткий, размытый, ворсистый, пушистый, введено в название новой теории с целью дистанцирования от традиционной четкой математики и аристотелевой логики, оперирующих с четкими понятиями: «принадлежит - не принадлежит», «истина - ложь». Концепция нечеткого множества зародилась у Заде «как неудовлетворенность математическими методами классической теории систем, которая вынуждала добиваться искусственной точности, неуместной во многих системах реального мира, особенно в так называемых гуманистических системах, включающих людей» [Л. Заде. Понятие лингвистической переменной и ее применение к принятию приближенных решений. М.: Мир, 1976. 167 с. ]. Революционным явилось то, что с этого момента зарождения данной теории высказывания могут принимать значения истинности не только 0 и 1, а любое значение между этими числами. За почти 40-летнюю историю своего развития данная теория дала рождение ряду серьезных научных направлений в области управления как техническими, так и гуманистическими системами. Были созданы крупные научные школы (Беркли (США), Торонто (Канада), Тулуза (Франция), Милан (Италия), Зиген (Германия), Москва, Таганрог (Россия), Рига (Латвия), Баку (Азербайджан) и общества, культивирующие данное направление (ISAFS, IFSA), ежегодно проводятся десятки научных конференций и симпозиумов, в том числе и традиционная всемирная конференция WCIS (Worldwide Conference on Intelligent System in Industrial Automation), которая была проведена в этом году в Ташкенте уже в третий раз (первая и вторая - в 2000 и 2002).
Следует отметить, что США, как правило, идущие в авангарде использования новейших теоретических разработок в области интеллектуальных систем, в течение 20 лет считали данную теорию лженаукой, до тех пор, пока в Японии не был создан первый процессор на нечеткой логике, базирующейся на теории нечетких множеств, после чего разработки в данном направлении были серьезно профинансированы и экспорт fuzzy-технологий из США был запрещен как стратегически важных научных исследований.
Началом практического применения теории нечетких множеств можно считать 1975г., когда Мамдани и Ассилиан (Mamdani and Assilian) построили первый нечеткий контроллер для управления простым паровым двигателем. В 1982 г. Холмблад и Остергад (Holmblad and Osregaad) разработали первый промышленный нечеткий контроллер, который был внедрен в управление процессом обжига цемента на заводе в Дании. Успех первого промышленного контроллера, основанного на нечетких лингвистических правилах «Если то», привел к всплеску интереса к теории нечетких множеств среди математиков и инженеров. Несколько позже Бартоломеем Коско (Bart Kosko) была доказана теорема о нечеткой аппроксимации (Fuzzy Approximation Theorem), согласно которой любая математическая система может быть аппроксимирована системой, основанной на нечеткой логике. Другими словами, с помощью естественно-языковых высказываний-правил «Если то», с последующей их формализацией средствами теории нечетких множеств можно сколько угодно точно отразить произвольную взаимосвязь «входы-выход» без использования сложного аппарата дифференциального и интегрального исчислений, традиционно применяемого в управлении и идентификации.
Системы, основанные на нечетких множествах, разработаны и успешно внедрены в таких областях, как: управление технологическими процессами, управление транспортом, медицинская диагностика, техническая диагностика, финансовый менеджмент, биржевое прогнозирование, распознавание образов. Спектр приложений очень широкий - от видеокамер и бытовых стиральных машин до средств наведения ракет ПВО и управления боевыми вертолетами. Практический опыт разработки систем нечеткого логического вывода свидетельствует, что сроки и стоимость их проектирования значительно меньше, чем при использовании традиционного математического аппарата, при этом обеспечивается требуемый уровень робастности и прозрачности моделей.
В реальном мире слишком много задач, для которых классические методы либо слишком громоздки, либо просто не применимы», то становится очевидным, что не следует заниматься разработкой основ сетевых технологий на основе нечеткой логики, а вот в вопросах их проектирования данная теория может быть достаточно полезна, тем более уже есть вполне реальные положительные результаты.
Реализованная программа РАСПОЗНОВАНИЕ
Хочется отметить первую версия универсальную программную систему интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ(разработана Ю.И.Журавлевым, В.В.Рязановым, О.В.Сенько). В основу требований к системе положены идеи универсальности и интеллектуальности. Под универсальностью системы понимается возможность ее применения к максимально широкому кругу задач (по размерностям, по типу, качеству и структуре данных, по вычисляемым величинам). Под интеллектуальностью понимается наличие элементов самонастройки и способности успешного автоматического решения задач неквалифицированным пользователем. Для достижения данных показателей были проведены работы по объединению различных подходов в рамкой единой системы, в частности, по унификации обозначений, форматов, пользовательских интерфейсов, единых форм представления результатов обработки данных и обеспечения в результате единого комфортного языка общения пользователя с различными методами распознавания и кластерного анализа.
В рамках Системы РАСПОЗНАВАНИЕ разработана библиотека программ, реализующих линейные, комбинаторно-логические, статистические, нейросетевые, гибридные методы прогноза, классификации и извлечения знаний из прецедентов, а также коллективные методы прогноза и классификации.
1. Алгоритмы распознавания, основанные на вычислении оценок. Распознавание осуществляется на основе сравнения распознаваемого объекта с эталонными по различным наборам признаков, и использования процедур голосования. Оптимальные параметры решающего правила и процедуры голосования находятся из решения задачи оптимизации модели распознавания - определяются такие значения параметров, при которых точность распознавания (число правильных ответов на обучающей выборке) является максимальной /5,6/.