А. К. АБРАМЯН, А. Л. ТУЛУПЬЕВ
Санкт-Петербургский институт информатики и автоматизации РАН
ЛОГИКО-ВЕРОЯТНОСТНЫЙ ВЫВОД В ИДЕАЛАХ КОНЪЮНКТОВ: JAVA- И ILOG-ТЕХНОЛОГИИ
Логико-вероятностный вывод (априорный, апостериорный, поддержание непротиворечивости) в алгебраических байесовских сетях сводится к решению серий задач линейного программирования над вероятностями элементов, входящих в идеалы цепочек конъюнкций. В работе рассмотрен подход к программной реализации соответствующих алгоритмов вывода с помощью Java - и ILOG-технологий.
Идеал конъюнктов является носителем математической модели фрагментов знаний (ФЗ) в теории алгебраических байесовских сетей (АБС) [1]. Элементам идеала в ФЗ приписаны оценки вероятностей, которые могут быть точечными или интервальными. Логико-вероятностный вывод для ФЗ должен предусматривать его проверку на непротиворечивость, а также возможность обработки интервальных оценок вероятностей в априорном выводе и в апостериорном выводе (выводе по свидетельствам). Для этого требуется разработать представление данных и алгоритмы так, чтоб можно было воспользоваться уже существующими технологиями.
Для упрощения работы с ФЗ вводится специальная система индексации его элементов. Каждый элемент ФЗ — это положительно означенная цепочка конъюнкций (конъюнкт) над некоторым конечным алфавитом. Если представить цепочку конъюнкций в виде последовательности 0 и 1, где 1, находящаяся в i-ой позиции этой последовательности, будет означать наличие атома с порядковым номером i в данной цепочке, 0 его отсутствие, а длина последовательности будет равна числу атомов в алфавите, то мы получим двоичное представление некоторого целого числа. Таким образом каждому элементу ФЗ однозначно сопоставляется некоторое целое число, которое будем называть индексом данного элемента. Такая система индексации позволяет задать оценки вероятностей элементов ФЗ в виде массива, причем каждый индекс этого массива осмыслен. Он является индексом элемента ФЗ.
При поддержании непротиворечивости и априорном выводе в ФЗ с интервальными оценками необходимо решать задачи линейного программирования (ЗЛП); при апостериорном — задачи гиперболического программирования, но они сводятся к ЗЛП. Удобным программным пакетом для решения ЗЛП является ILOG CPLEX; для обращения к нему в Java-коде используется библиотека интерфейсов ILOG Concert.
Ключевой для логико-вероятностного вывода фрагмент кода, реализующий на языке Java проверку непротиворечивости ФЗ с интервальными оценками с использованием библиотеки ILOG CPLEX, представлен ниже.
boolean solve=true;
//Создание модели для формирования ЗЛП в CPLEX
IloCplex cplex = new IloCplex();
//Создание переменных с указанием их верхних
//и нижних границ
IloNumVar [] pc=mVarArray(numOfElements, newLB, newUB);
//Матрица I_n из [1], позволяющая задать ограничения
//вытекающие из аксимоатики вероятностной логики
IJMatrix im=new IJMatrix(numOfAtoms, true);
//Создание выражений для задания ограничений
IloNumExpr [] exprs=im. multiplyOnIloVector(pc);
//Задание ограничений
for(int i=0;i<numOfElements;i++){
cplex. addLe(0.0,exprs[i]);}
//Решение ЗЛП — поиск верхней границы оценки истинности
for(int i=0;i<numOfElements;i++){
IloObjective maxObj=cplex. addMaximize(pc[i]);
if(cplex. solve()){ //Запуск решателя ЗЛП
double val=cplex. getValue(pc[i]);
reconciledUB[i]=val;
cplex. remove(maxObj);}
else{ //Если ЗЛП не имеет решения
solve=false;
break;} }
cplex. end();
Во фрагменте кода массив pc представляет вероятности элементов ФЗ с заданными верхней и нижней оценкой. С помощью матрицы im формируется серия ограничений вида cplex. addLe(0.0,exprs[i]) на вероятности, вытекающих из аксиоматики вероятностной логики.
В системе логико-вероятностного вывода в настоящее время с помощью указанных технологий для идеала конъюнктов полностью реализованы поддержание непротиворечивости ФЗ и априорный вывод, а апостериорный вывод осуществляется для детерминированных свидетельств.
Список литературы
1. , , Сироткин сети: логико-вероятностный подход. СПб.: Наука, 20с.
