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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В настоящий момент ядро языка реализовано полностью. Дальнейшее его развитие пойдёт, по-видимому, по пути наращивания библиотеки методов.

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