Локальные базисы в алгебраическом подходе к проблеме распознавания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Российская Академия Наук Вычислительный центр

На правах рукописи

Воронцов Константин Вячеславович

Локальные базисы в алгебраическом подходе

К ПРОБЛЕМЕ РАСПОЗНАВАНИЯ 01.01.09— Математическая кибернетика

диссертация на соискание учёной степени кандидата физико-математических наук

Москва 1999

Оглавление

Введение 3

1 Локальные базисы и методы их построения 9

1.1 Задачи обучения по прецедентам ........................................9

1.2 Оптимизационный и алгебраический подходы..........................10

1.3 Оптимизационные задачи построения локальных базисов..............14

1.4 Проблемно-независимые и проблемно-зависимые подзадачи..........20

2 Решение задач оптимизации при построении локальных базисов 22

2.1 Линейные корректирующие операции....................................23

2.1.1 Задача восстановления регрессии................................23

2.1.2 Задача классификации..............................................25

2.2 Полиномиальные корректирующие операции............................27

; чу-:

2.2.1 Задача восстановления регрессии . . . . . Ч',.> t".? ..........28

2.2.2 Задача классификации..............................................29

2.3 Монотонные корректирующие операции ................................30

2.3.1 Оптимизация базиса при построении корректного алгоритма 31

2.3.2 Оптимизация базиса при фиксированном числе операторов . 35

2.3.3 Задача классификации..............................................44

2.3.4 Задача восстановления регрессии................................47

2.3.5 0 методах построения монотонных корректирующих операций 50

2.3.6 Монотонные корректирующие операции в задаче классификации ................................................................52

2.3.7 Монотонные корректирующие операции в задаче восстановления регрессии....................................................55

2.3.8 Некоторые алгоритмы монотонизации выборок................65

3 Проблемно-зависимые подзадачи и язык SDL 71

3.1 Введение в язык алгоритмических суперпозиций......................72

3.2 Модель данных SDL........................................................78

3.2.1 Терминология ......................................................79

3.2.2 Массивы..............................................................81

3.2.3 Методы и алгоритмы..............................................82

3.3 Некоторые элементы языка 8DL..........................................83

3.4 Обоснование достаточности модели данных для решения прикладных задач....................................................................86

3.4.1 Метод наименьших квадратов....................................88

3.4.2 Метод построения линейной разделяющей поверхности .... 89

3.4.3 Вычисление дефекта набора алгоритмических операторов . . 90

3.4.4 Метод монотонной интерполяции ................................91

3.4.5 Метод монотонизации выборки....................................91

3.4.6 Метод нормировки признаков ....................................92

3.4.7 Метод генерации признаков по функции расстояния ..........93

3.4.8 Метод упорядочивания объектов по убыванию расстояний . . 94

3.4.9 Метод генерации метрик по признакам..........................95

3.4.10 Метод ближайших соседей........................................95

3.4.11 Метод таксономии..............................95

3.4.12 Метод вычисления расстояния между признаками ............96

3.5 Примеры описания алгоритмических суперпозиций....................97

3.5.1 Абстрактные методы с алгоритмами стандартной структуры 97

3.5.2 Линейная коррекция в задаче восстановления регрессии ... 99

3.5.3 Монотонная коррекция в задаче восстановления регрессии . . 103

3.5.4 Полиномиальная коррекция в задаче классификации.....107

4 Заключение 112

Список рисунков 114

Литература 115

Диссертация выполнена в рамках алгебраического подхода к проблеме распознавания, развиваемого школой академика РАН Ю.И. Журавлёва. Целью работы является создание специальных методов, необходимых для эффективного использования конструкций алгебраического подхода при решении прикладных задач распознавания, классификации и прогнозирования. Данные методы ориентированы на непосредственное практическое применение и обеспечивают требуемое качество распознавания при относительно невысокой сложности алгоритмов. Рассматривается новая для алгебраического подхода задача построения локальных базисов, приводящая к построению алгоритмических операторов путём решения последовательности оптимизационных задач. Предлагается общая методология решения прикладных задач, основанная на использовании специального языка для описания настраиваемых алгоритмических суперпозиций.

Введение

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

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

симость восстанавливают по прецедентам: накапливают достаточное количество пар вида «начальная информация» —«финальная информация» и строят алгоритм, корректно воспроизводящий заданные ответы на заданном конечном множестве объектов. Процесс построения алгоритма, приближающего искомую зависимость, принято называть обучением по прецедентам, совокупность прецедентов — обучающей выборкой, а начальные информации, описывающие отдельные прецеденты, — объектами обучения.

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

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

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

ниям [37, 38], заданным на основе содержательных представлений об искомом отображении.

Традиционно в алгебраическом подходе основное внимание уделялось изучению вопросов регулярности и полноты алгебраических замыканий моделей алгоритмов [14,15]. При этом корректные алгоритмы строились конструктивно, но основной целью их построения было доказательство теорем существования, а не решение прикладных задач. Для упрощения доказательств при изучении класса регулярных задач корректность обеспечивалась путём максимального, в некотором смысле, расширения исходной эвристической модели. Получаемое в результате семейство алгоритмов оказывалось настолько обширным, что не нужно было применять методы оптимизации, чтобы найти в нём корректный алгоритм — он легко конструировался по явным формулам. С другой стороны, получаемые таким образом алгоритмы оказывались довольно громоздкими и на практике обычно не применялись.

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

исходной информации.

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

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

Работа состоит из трёх глав.

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

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

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

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

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

— доказана сходимость суперпозиции к корректному алгоритму за конечное число шагов;

— рассмотрена задача построения суперпозиции ограниченной сложности; для неё исследовано специальное отношение предпорядка на множестве объектов обучения, что позволило сформулировать критерий оптимизации очередного базисного оператора;

— решена задача построения многомерной монотонной функции, проходящей

через заданные точки и обладающей достаточной степенью гладкости.

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

Благодарности

Автор выражает глубокую признательность члену-корреспонденту РАН Константину Владимировичу Рудакову за постановку задач, многочисленные идеи и постоянное внимание к работе; академику РАН Юрию Ивановичу Журавлёву за поддержку на всех этапах выполнения данной работы; всем своим коллегам, дискуссии с которыми способствовали решению задачи монотонной коррекции и развитию языка SDL.

1 Локальные базисы и методы их построения

1.1 Задачи обучения по прецедентам

В самой общей постановке задача синтеза алгоритмов преобразования информации состоит в следующем [15]. Имеется множество начальных информаций 3; и множество финальных информаций 3/. Требуется построить алгоритм, реализующий отображение из 3,- в 3/, удовлетворяющее заданной системе ограничений.

Одним из частных случаев является задача обучения по прецедентам, в которой система ограничений задаётся следующим образом. Фиксируется последовательность 1Ч = {хк}1=1 элементов множества 3,- и последовательность 1Ч = = {ук}1=1 элементов множества 3/. Искомый алгоритм А должен точно или приближённо удовлетворять системе из д равенств

А(хк) = ук, к = 1,...

которую мы будем сокращённо записывать как А(1д) = Ограничения такого типа называются локальными или прецедентными. Кроме того, обычно требуется, чтобы искомый алгоритм удовлетворял некоторым дополнительным ограничениям, которые в общем случае выражаются условием

Аешг,

где 9Ли — заданное множество отображений из 3,- в 3/ . Алгоритм, удовлетворяющий локальным и дополнительным ограничениям, называют корректным. Итак, рассматриваемые задачи обучения по прецедентам определяется пятёркой 2 =

Различие между локальными и дополнительными ограничениями заключается в том, что первые относятся к конечному набору точек и допускают эффективную проверку, в то время как вторые накладываются на всё отображение «в целом» и не допускают эффективной проверки. В частности, это могут быть ограничения непрерывности, гладкости, монотонности, унимодальности, и т. д. На практике

дополнительные ограничения учитываются на этапе построения параметрического семейства алгоритмов, а локальные — при последующей настройке параметров алгоритма на заданные прецеденты.

1.2 Оптимизационный и алгебраический подходы

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

1. Выбирается эвристическая информационная модель алгоритмов 9Л таким образом, чтобы 9Л С Ши. Тем самым гарантируется, что все алгоритмы из ШТ удовлетворяют универсальным ограничениям «по построению».

2. При произвольном фиксированном д определяется функцио�