Технология проблемно-ориентированных алгоритмических композиций

Для решения задач интеллектуального анализа данных в отделе Вычислительных методов прогнозирования ВЦ РАН разработано инструментальное средство ASDIEL, Algorithmic Superpositions Description and Investigation Environment and Language — язык и среда для описания и исследования алгоритмических композиций.

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

Класс решаемых задач

Система ASDIEL предназначена для решения задач распознавания, прогнозирования и поиска скрытых закономерностей в неполных, неточных, противоречивых и разнородных данных. В последние годы эти направления получили общее название data mining или "интеллектуальный анализ данных". Большое количество задач такого рода возникает при попытках использовать для эффективного принятия решений огромные объемы сырой информации, накопленной в банках данных.

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

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

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

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

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

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

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

Зачем нужно строить композиции алгоритмов?

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

Почему для описания композиции нужен специальный язык?

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

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

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

Модель данных

Решение задачи начинается с выделения нескольких упорядоченных множеств, называемых наборами, которые в дальнейшем будут играть роль размерностей в массивах данных. Если предполагается работать только с признаковыми описаниями объектов, то достаточно определить только два набора: объектов и признаков. В общем случае могут понадобиться также:

Затем некоторым декартовым произведениям введенных наборов сопоставляются массивы, предназначенные для хранения и представления данных. Команда языка USE позволяет определить любое количество наборов и массивов. Например, команда

USE F[S], M[S|S];

вводит набор объектов S, набор признаков F, набор функций над парами объектов M, определяет двумерный массив F[S] "признаки – объекты" и трехмерный массив M[S|S] "функции – пары объектов" (символ | используется в ASDIEL для разделения размерностей и может интерпретироваться как знак декартова произведения).

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

Возможны три способа генерации значений признака:

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

Возможны три способа хранения значений признака:

  1. признак хранится в оперативной памяти с прямым доступом (для двумерных массивов);
  2. признак хранится в оперативной памяти с индексированным доступом (для многомерных разреженных массивов);
  3. признак вычисляется алгоритмом или выражением при каждом обращении, память для хранения не отводится.

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

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

Например, чтобы выделить в массиве F[S] подмассив, образованный множеством признаков {x, y, z} из F и множеством первых ста объектов из S, пишут:

F{x,y,z} | S{#1..#100}.

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

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

Определение 1. Алгоритмом в ASDIEL называется вычислимое отображение вида

(X1,…,Xm) -> (Y1,…,Yn),

где (X1,…,Xm) — входные подмассивы, (Y1,…,Yn) — выходные подмассивы.

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

Определение 2. Методом в ASDIEL называется совокупность конечного множества алгоритмов и конечного множества параметров. Любой алгоритм метода может свободно считывать и изменять значение любого параметра метода.

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

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

Введенные определения алгоритма и метода охватывают обширный класс моделей алгоритмов. Многие модели, активно используемые на практике, легко описываются в терминологии ASDIEL. Это позволяет создать мощную библиотеку методов с единым интерфейсом и правилами применения. В настоящее время библиотека ASDIEL постепенно пополняется новыми методами. Разработан открытый документированный интерфейс, позволяющий реализовать новые методы в виде динамических библиотек.

Как решать прикладные задачи с помощью ASDIEL?

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

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

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

Где взять программы и документацию?