Оглавление
Введение 3
Глава 1 12
Глава 2 22
Глава 3 51
Заключение 89
2
Введение
История развития алгоритмов распознавания. Проблема автоматического распознавания образов является одной из актуальных и трудных проблем математической кибернетики и прикладной математики. Это проблема является ведущей в таких областях науки и техники, как практическая геология, биология, химия, медицина и т.п. Одной из причин широкого распространения этой проблемы в этих областях является то, что для применения методов распознавания требуется значительно меньшая точность описываемых объектов и явлений, чем при применении других методов прикладной математики, а упомянутые научные сферы являются слабоформализуемыми.
Второй важной причиной является то, что идея прецеденти ости, то есть идея принятия научного решения на основе сравнения с другими объектами или явлениями, является ключевой для естественных наук. Действительно, обучение или исследование может проходить в естественных науках либо на основе уже известных принципов и законов, либо на основе примеров. При этом тот или иной пример относится к определенному классу на основе накопленной информации о других примерах. Тем самым проявляется идеология распознавания. Все допустимые объекты или явления разбиты па конечное число классов (классы могут пересекаться). Для каждого класса известно конечное число ранее изученных объектов или явлений. Изучаемый (данный) объект следует отнести к тому или иному классу. Различные математические методы распознавания являются формализацией вышеописанной схемы.
После появления в середине двадцатого века множества задач распознавания в естественных пауках, выделилось две школы с принципиально различными подходами к решению проблемы распознавания.
Представители первой школы каждую из решаемой задач пытались формализовать, иными словами, перевести на язык математики, а затем
3
применяли и развивали стандартные математические, .методы. Например, широкое распространение в решении задач распознавания, получили методы математической статистики. Это удавалось не для каждой из практических задач, либо класс задач сужался до тех; которые могли быть подвержены формализации. В случае расширения класса задач при практическом применении иногда приходилось отступать, от принципов строгого математического доказательства, который применялся в теоретических исследованиях.
Представители второй школы пришли к выводу, что задачи распознавания требуют новых подходов в прикладной математике. В разработке таких подходов помогло появление первых ЭВМ, что позволило математикам проводить широкий спектр математических экспериментов. Этот метод исследования во многом похож на экспериментальные методы исследования физика-естественника, которые позволяют ему строить различные гипотезы об изучаемых им явлениях, а затем проверять их'Экспериментальным путем. Точно также математик может выдвинуть гипотезу и, не проводя строгих математических доказательств, проверить гипотезу, проведя математический эксперимент.
Таким образом, на первом этапе собирается экспериментальный материал проверки той или иной гипотезы о методе решения конкретной задачи. Изучается класс задач, приводящих к задаче распознавания, например, задача прогнозирования в геологии. Изучение описаний месторождений и участков местности, где месторождения не обнаружены, приводит к гипотезе: множества описаний первого и второго класса раздел якугся достаточно простой поверхностью. Простейшей поверхностью является гиперплоскость. Уточнённая гипотеза: описания, выполненные набором числовых признаков и принадлежащие разным классам, разделяются гиперплоскостью. Проводится эксперимент на ЭВМ и показывается, что в 99 случаях из 100 гипотетическое разделение действительно имеет месте.
Появляется так называемый эвристический алгоритм: по описаниями объектов двух разных классов строится разделяющая гиперповерхность, а процесс распознавания сводится к определению полупространства относительно построенной гиперплоскости, к которой относится описание предъявленного для распознавания объекта.
В развитие теории распознавания можно выделить этап, сиязанный с появлением большого числа принципиально разных эвристических алгоритмов. Так как эти алгоритмы оспованы лишь на экспериментально
4
проверенных гипотезах, они называются некорректными.
Следующий этап развития связан с обобщением и классификацией полученных эвристических методов, изучением принципов их формиро-вания. На основе подобных изучений, были построены, некоторые классы формально описаипых процедур распознавания, или так называемые модели распознающих алгоритмов. Исследование алгоритмических моделей производилось уже с использованием строгих математических методов и служило предпосылкой для развития общей теории распознавания.
Среди описанных моделей можно выделить модели основанные на принципах разделения (3), модели типа потенциалов [1], модели вычисления оценок |9][10]|11][12].
Каждая из этих моделей имеет свою специфическую проблематику, связанную как с теоретическими исследованиями и с технической реализацией алгоритмов* модели, так и касающуюся конкретных внешних задач. Важными являются задачи, связанные с отысканием оптимальных в данной модели алгоритмов в смысле некоторых заданных критериев, которые зависят от внешней задачи. Чаще всего построение оптимальных алгоритмов сводится к некоторым экстремальным задачам, которые иногда невозможно свести к уже изученным.
В рамках исследования моделей алгоритмов выделилось две ветви, возникших в связи со стремлением математиков к обобщению способов описания алгоритмов моделей.
Суть исследования.первой ветви сводится к упрощению описания алгоритмов, а так лее сопутствующих множеств, таких как множеств объектов распознавания или выделяемых признаков, посредством использования индуктивного подхода при описании множеств. Выбирается некоторый набор базисных элементов, а затем посредством определенных операций, строится всё множество. Так, при помощью заданных порождающих отображений, строятся описания классов. Аналогично - из элементарных признаков и системы логических операций - строится множество признаков. Таким образом, система правил для построения начальной обучающей информации для распознающего алгоритма, порождает новую модель. Такие алгоритмы и модели получили название структурных или синтаксических методов распознавания |24).
Вторая ветвь связана с анализом всего множества возможных эвристических алгоритмов. На основе изучения различных моделей экспериментальных алгоритмов, удалось сформулировать обобщённые понятие
алгоритма распознавания и изучить свойства множества таких алгоритмов. Оказалось, что. введя соответствующие операции на этом множестве, множество алгоритмов можно рассматривать как алгебру, что позволило детально изучить его свойства с помощью соответствующих алгебраических методов. Используя этот подход, получены фундаментальные результаты [17J, касающиеся нахождения абсолютно точно классифицирующего алгоритма для конкретной задачи в рамках множества распознающих алгоритмов.
В дальнейшем обзоре алгоритмов распознавания будут рассмотрены конкретные модели, а также основные результаты, касающиеся описываемых семейств алгоритмов. Начнём обзор моделей со сравнительно давно используемой в практических применениях — с модели алгоритмов вычисления оценок (АВО).
Алгоритмы вычисления оценок. Идея алгоритмов вычисления оценок основана на формализации принципа частичной ирецедентности. Модель разработана для стандартной информации [9|. Введём основные определения.
Пусть М — множество, элементы которого 5 называются допустимыми объектами. Для каждого S определено I(S) — описание объекта S. Кроме того, М = и[_! К\. Множества Кі называются классами. Задано также множество {/ofA’i,... ,K|)} информации о классах. Вектор cv = (a-j,..., rvj) называется информационным, если оц Є {0,1, А}. Введены предикаты Pj(S) — объект S принадлежит классу Кj, j = 1,2,...
Для краткости набор описаний /(50,..., J(Sq) допустимых объектов S[,...,Sq обозначим через I(S{,...,S'q).
Определение 1. Алгоритм Л называется распознающим алгоритмом, если
Л(/0(Аі,..., A,), I(S[,..., S'q)) =
W<i *і) Є {/о№S'q
— допустимые объекты, q > 1 — произвольное натуральное число, а-] <= {0,1, А}. Строка (ад,,..., а-}) называется информационным вектором |9| объекта S' в алгоритме А.
Значения a'j интерпретируются следующим образом.
1. afj <= {0,1}; тогда алгоритм А установил, что Pj(S't) = aft.
2. ггц « А : алгоритм А отказался вычислять значение Pj(Sl).
6
Определение 2. Вектор й(5) - (а,(5),...,«/(5)), называется истинным для .9, если аД5) € {О, Л} и
Р,(5)== 0,(5),./-1,2,...,/.
Пусть в пространстве информационных векторов задана функция р(а,р), обладающая всеми свойствами расстояния, за исключением, может быть, аксиомы треугольника. Задана также последовательность числовых функций /1(^1),..., /„(.Т!,..., х„),..., причём: I) /ч(хи ...,хч) определена и неотрицательна при > 0; 2) /ч монотонно не возрастает по каждой из переменных х,; 3) /7 достигает абсолютного максимума па наборе (0,... ,0).
Пусть опять 5[,..., 5' — произвольная конечная выборка из множества допустимых объектов, 5 истинный для а*(5{) — информационный вектор 5' в алгоритме А.
Определение 3. Функционалом качества алгоритма А на 5(,...,5' называется величина
ШВД). ^И)). • ■ ■ ,р(^), 5Д^))).
Функционал качества алгоритма А будем обозначать в дальнейшем через <^(>4) или <р(А, 5{,.. •, 5'). В практических задачах обычно рассматриваются следующие виды функционалов <р{Л).
1. Пусть для каждой пары
А^),5- е М, 1 < у < /, определены числа 7,^(0:,/?), о,/? € {0,1,Л}, Причём 7^(а,а) > 7у (<*>£) ПРИ а ^ & 7у(<*>/?) = 7у(0.а),Ту(а, Д) > 70(а,Д), если а £ {0,1},/? 6 {0,1},5 7^ Д.
Функционал 9?(Л) называется линейным |13], если
ЛА) -
/ «=1 ^=1
2. Если
7у(1,1) = 7«(0,0) = 1,
и все остальные 7,, = 0, то функционал у(Л) называется долей правильных прогнозов.
В дальнейшем основной задаче является эффективное построение распознающих алгоритмов с максимальным значением ф(А). Такие алгоритмы в дальнейшем называются оптимальными.
7
- Київ+380960830922