Software & Systems

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

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

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

Одним из новых видов логического вывода является логический вывод модифицируемых заключений, который позволяет преобразовать изначально невыводимое заключение с целью сделать его следствием исходных посылок [2]. Этот вид вывода делает возможным расширение класса решаемых системами логического вывода задач, в частности, за счет задач интеллектуального обучения, интеллектуального управления вычислительными процессами, автоматического управления объектами и других.

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

Критерии эффективности

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

а)  критерии пользователей: прозрачность, удобство интеллектуального интерфейса;

б) критерии приглашенных экспертов: оценка решений, предлагаемых системой, сравнение решений системы с собственными решениями, оценка подсистем;

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

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

Первый из критериев имеет однозначный смысл: чем время выполнения вывода меньше, тем эффективнее работа системы. Учитывая, что метод вывода параллельный, данный критерий следует рассматривать с учетом количества вычислителей и выбранной глубины параллелизма.

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

Расчет времени вывода

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

Tвмз=Tпрзак+Тр+Tмин+Tф, (1)

где Tпрзак – время преобразования заключения во множество дизъюнктов; Тр – время расширения формулы заключения; Tмин – время минимизации формулы заключения; Tф – время фильтрации вариантов модификации.

Время преобразования заключения во множество дизъюнктов относительно мало и может быть рассчитано по следующей формуле:

Tпрзак=(t+Tпрф)×]Nф/Nв[, (2)

где t – временные затраты на организацию вычислительного процесса («накладные расходы» на создание процесса, передачу параметров и результата, удаление процесса); Tпрф – среднее время преобразования во множество дизъюнктов одной формулы заключения; Nф – количество формул в заключении; Nв – количество вычислителей; ] [ – операция округления до ближайшего большего целого.

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

Рассчитаем время расширения формулы заключения:

Тр=+Tрз+Tрп+Tрф, (3)

где tрi – время выполнения i-го шага вывода; I – общее количество шагов вывода; Tрз – время согласования решений и формирования вариантов формул дополнительных посылок; Tрп – время подготовки и выполнения проверочного дедуктивного вывода; Tрф – время формирования результата.

Время выполнения i-го шага вывода зависит от количества процедур вывода и для i=1 может быть рассчитано по формуле:

tp1=(t+Tw)×]Nw1/Nв[, (4)

где Tw – среднее время выполнения процедуры вывода; Nw1 – количество выводимых дизъюнктов первого шага (соответствует количеству дизъюнктов заключения).

Для i>1 время рассчитывается по формуле:

tpi=(t+Tw)×]2Nwi/Nв[, (5)

где Nwi – количество выводимых дизъюнктов наi-м шаге.

Логический вывод делением дизъюнктов допускает несколько возможных уровней параллелизма (табл. 1).

Таблица 1

Уровни параллелизма логического вывода

Когда количество вычислителей больше количества одновременно выполняемых процедур вывода, целесообразно повысить уровень параллелизма вывода; время выполнения шага при этом уменьшается:

tpi=(t+TW)×]2Nwi×M/Nв[+(t+Twф)×]2Nwi/Nв[, (6)

где TW – время выполнения процедуры полного деления дизъюнктов; M – количество исходных посылок; Twф – время формирования результата процедурой вывода.

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

Значения Tрз и Tрф по сравнению с остальными значениями малы и не вносят существенного вклада в общее время вывода.

Время дедуктивного вывода Tрп сопоставимо со временем абдуктивного вывода Тр, и с некоторой незначительной погрешностью их можно принять равными: Tрп=Tр.

Время минимизации заключения рассчитать точно достаточно сложно, так как количество операций заранее не определяется и зависит от результатов вывода с расширением формулы заключения. Для расчетов необходимо ввести следующие обозначения: U – общее количество дизъюнктов, полученное после вывода с расширением заключения; Lu – длина (количество литералов u-го дизъюнкта, где u=1, …, U); Eu – количество исключенных из u-го дизъюнкта литералов; Ru – количество полученных минимальных решений для u-го дизъюнкта (последние два параметра заранее неизвестны).

Тогда время минимизации можно рассчитать по формуле:

Tмин»Тд, (7)

где Тд – время дедуктивного вывода (рассчитывается по формуле расчета времени Тр (3)).

Время фильтрации вариантов рассчитывается по формулам: (8) – для первого уровня параллелизма и (9) – для второго и более:

Tф=(max(Vi)×To+Тфф+t)×]W/Nв[, (8)

Tф=(To+t)×]V/Nв[+(Тфф+t)×]W/Nв[, (9)

где То – время выполнения функции оценки для одного дизъюнкта; Тфф – время формирования результатов фильтрации для одного исходного дизъюнкта заключения; W – количество исходных дизъюнктов заключения; V – общее количество модификаций дизъюнктов; Vi – количество модификаций для i-го исходного дизъюнкта заключения (i=1,…,W).

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

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

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

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

Расчет степени модификациизаключения

Представим степень модификации заключения некоторым безразмерным числом МЗ. Поскольку заключение представлено в виде набора дизъюнктов, данную величину можно вычислить, просуммировав степени модификации отдельных дизъюнктов:

МЗ=, (10)

где Мдw – степень модификации дизъюнкта w (w=1,…,W); W – количество дизъюнктов в заключении.

Степень модификации дизъюнкта может определяться несколькими видами модификации:

-   модификация предметных констант и переменных;

-   модификация функторов (замена на другой функтор, константу, переменную);

-   модификация набора литералов.

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

Таблица 2

Коэффициенты видов модификации

Тогда степень модификации дизъюнкта может быть рассчитана следующим образом:

МДw=k1×М1w+k2×М2w+k3×М3w, (11)

где М1w, М2w, М3w – степени модификации соответствующих видов.

Первые два значения связаны с заменой термов. Подсчет количества замененных термов достаточно прост: если некоторый терм исходного дизъюнкта заключения отличается от терма модифицированного дизъюнкта, соответствующая степень модификации увеличивается на единицу. Местность предикатных и функциональных констант при выводе сохраняется, поэтому невозможно в пределах данного предиката или функтора добавление или исключение термов первого уровня. Таким образом, можно сказать, что М1w – это количество замененных предметных переменных и констант; М2w – количество замененных функциональных констант.

-Модификация набора литералов оценивается несколько сложнее. Возможны три варианта модификации: появление (исчезновение) инверсии; добавление литерала; удаление литерала.

По мнению авторов, считать все три варианта равноправными не следует, поэтому предлагается ввести весовые коэффициенты, приведенные в таблице 3.

Таблица 3

Коэффициенты степени модификацииуровня литералов

Тогда степень модификации уровня литералов можно рассчитать по формуле:

М3w=k1×NI+k2×N++k3×N– , (12)

где NI – количество инвертированных литералов; N+ – количество добавленных литералов; N– – количество исключенных литералов.

В общем случае следует считать, что качество модификации тем выше, чем меньше ее степень, рассчитанная по формуле (10). Если нет специальных ограничений или требований, то степень

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

Рассмотренные критерии позволяют оценить как эффективность реализации систем логического вывода, основанных на принципе деления дизъюнктов, так и эффективность их работы на различных аппаратно-программных платформах.

Список литературы

1. Страбыкин Д.А. Логический вывод в системах обра-ботки знаний / Под ред. Д.В. Пузанкова. – СПб: Изд-воСПбГЭТУ,1998.

2. Страбыкин Д.А., Томчук М.Н. Логический вывод с модификацией заключения в исчислении высказываний. // ВестникВятского науч. центра Верхне-Волж. отделения Акад. техноло-гич. наук РФ. // Сб. науч. тр. – Киров: ВНЦ. - 2003. -С. 9-16.