Fuzzy scala inference engine - fusie

Как-то вспомнилось, что делал в универе лабу по предмету "Системы исскуственного интеллекта" на тему - экспертная система. Настолько это было интересно тогда, что, помню, много души вложил в эту работу. И захотелось.. вспомнить былое, переписать ту лабу с java на scala, воспользовавшись преимуществами последнего.

Результатом примерно двухмесячной работы стал движек вывода правил (forward chaining) с поддержкой нечеткой логики, под названием fusie (Fuzzy Scala inference engine)  (код).

Библиотека выложена в центральный репозиторий maven-а:

<dependency>
   <groupId>net.sf.brunneng.fusie</groupId>
   <artifactId>fusie</artifactId>
</dependency>

Возможные применения

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

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

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

Место данного движка среди себе подобных

Существует множество хороших движков вывода и экспертных систем для jvm. Приведу свой маленький обзор некоторых из них (не претендующий, впрочем, на полноту и достоверность, только мои первые впечатления при беглом знакомстве).
Drools - Взрослый, хорошо конфигурируемый опен сорс движок, использующий forward chaining. Синтаксис определения правил можно посмотреть здесь.
d3web - Достаточно взрослая платформа для построения экспертных систем. Имеет собственное вики, для редактирования правил, вопросов, построения форм для принятия входных даннных, юнит тестирования. Несложный язык определения правил.
jColibry - как я понял, эта библиотека предназначенная для интерактивного поиска данных из большого числа вариантов.
InfoSapient - движок вывода, использующий backward chaining, с поддержкой нечеткой логики. Позвляет использовать человекоподобный язык описания правил. Но имеет, на мой взгляд, несколько существенных недостатков, описанных тут (page 19-20):
 "By current design, the rule base currently cannot access external data. This means during the consultation session, the ‘client’ must supply the goal to be solved, and all supporting information as well.*" "The rule syntax does not permit calculations, i.e. if ((a + b) is greater than m) then x; or executing external programs, scripts, or methods on external objects.* In other words, the client must execute any other external object, or script, based on the results from the consultation session."
Jena - позволяет представлять данные в стандартном RDF формате (семантическая сеть), и потом пытается извлекать интересующие данные используя специальный язык запросов SPARQL.
mandarax - компилятор правил. Недостаток в том, что он статичен - каждый набор правил должен был скомпилирован как джава код, и это нельзя сделать динамически.
И другие.

Как видим все движки очень разные: некоторые используют forward некоторые backward chaining, некоторые владеют нечеткой логикой некоторые нет. Одни имеют простой синтаксис определения правил — у других он сложный и т.д. В fusie я попытался совместить возможности четкого и нечеткого вывода, простоту определения правил и гибкую конфигурацию. Именно Scala (а не java) была изначально выбрана потому, что на ней можно писать в функциональном стиле, что позволит побороть предполагаемую сложность алгоритмов, которые предстояло написать. Тем не менее, движок собирается как maven артефакт, после чего его можно подрубить к любому maven проекту на java (с дополнительной зависимостью на scala-library), и все будет работать.

Общая схема понятий движка и их взаимоотношений между собой

Как видим правила работают с переменными (не обьектами) поэтому данный движкек не соответствует JSR-94.

Killer feature

Введем понятие "пересекающиеся правила". Это такие правила, которые дают заключения об одной и той же переменной. Например
 

when
   a > 300
then
   b = 5

when
   a < 400
then
   b = 10

  В данном случае если 'a' принимает значение между 300 и 400, то выполняется оба правила и система для дальнейшего вывода должна решить по какому пути идти, т.к 'b' не может быть одновременно 5 и 10. Вообще говоря, существует несколько способов как разрулить конфликтную ситуацию:

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

Стратегии разрешения конфликта в Drools.
Текущая реализация (и такого я нигде не встречал) идет по другому пути.
4) Считать что оба правила равноценны и 0.5 вероятности что выполняется первое и 0.5 что второе (или в общем случае 1/N вероятности, если пересекающихся правил N). Далее вывод разделяется на части, и продолжается в отдельности для каждой из ветвей вплоть до нахождение искомой переменной. Впоследствии считается суммарная вероятность для каждого возможного значения искомой переменной по всем ветвям вывода. Если учесть, что правила могут причудливым образом зависить друг от друга по используемым переменным в предусловиях, что заключения могут содержать присваивания к разным переменным (так, что возможны группы пересекающихся правил, типа X пересекается с Y по переменной a, Y пересекается с Z по переменной b) то простое словесное описание идеи выливается в не очень простую реализацию. Главная цель которая была достигнута — корректное вычисление вероятностей значений принимаемых искомой переменной. Таким образом движок хорошо справляется с базой возможно противоречивых правил, которые пересекаются:

1. Ненамеренно, если правила были составлены разными экспертами и у каждого свое мнение.
2. Намеренно, если одна и та же переменная может быть вычислена разными способами, например:

   when
     graphicCardType == "Top"
   then
     graphicCard = "Nvidia super card"
   
   when
     graphicCardType == "Top"
   then
     graphicCard = "Radeon super card"
   

   В данном примере советник по выбору видеокарты может посоветовать как карту от Nvidia так и карту от Radeon с равной вероятностью.

Таким образом поддерживается элемент нечеткости в выводе.

Язык определения проблемы

Структура определения проблемы:

1. Задаются пользовательские переменные — те, которые будут запрашиваться в процессе вывода.
2. Правила вывода, состоящие из предусловий, заключений и, по желанию, вероятности выполнения данного правила (от 0 до 1, по умолчанию 1).
3. Цель — имя переменной, которую нужно найти.

Проблему можно определять полностью программно, однако гораздо удобнее делать это используя специальный (не xml) синтаксис, который был разработан с целью быть лаконичным и сходу понятным для человека с опытом программирования.
 Пример 1: Финансовый советник
 

int amountSaved <- "How many savings you have?"
int earnings <- "What is you year income?"
bool steady <- "Your year income is stable?"
int dependents = min: 0 <- "How many dependents you have?"

fact
   minincome = 15000 + (4000 * dependents)

fact
   minsavings = 5000 * dependents

when
   savingsAccount == "inadequate"
then
   investment = "savings"

when
   (savingsAccount == "adequate") && (income == "adequate")
then
   investment = "stocks"

when
   savingsAccount == "adequate"
   income == "inadequate"
then
   investment = "combination"

when
   amountSaved > minsavings
then
   savingsAccount = "adequate"

when
   amountSaved <= minsavings
then
   savingsAccount = "inadequate"

when
   steady
   earnings > minincome
then
   income = "adequate"

when
   steady
   earnings <= minincome
then
   income = "inadequate"

when
   !steady
then
   income = "inadequate"

find investment

Вначале идет блок определения переменных:

int amountSaved <- "How many savings you have?"
int earnings <- "What is you year income?"
bool steady <- "Your year income is stable?"
int dependents = min: 0 <- "How many dependents you have?"

Это те переменные, которые не выводятся, но используются в правилах. Вначале следует тип, потом имя переменной, потом, опционально валидация на возможные значения ( min: 0 — означает что недопустимо значение меньше 0) и, тоже опционально, после <-  вопрос пользователю при запросе данной переменной. Поддерживаются типы: bool, int, double, enum (он же string). В предусловиях и заключениях могут использоваться выражения любой сложности (самое сложное в примере minincome = 15000 + (4000 * dependents)), но это далеко не предел) Семантика арифметических операций такая же как в java. Поддерживаются неявные преобразования int к double где это нужно. По умолчанию поддерживается вызов функций из java.lang.Math, но можно регистрировать и свои функции.
 Правило вида

fact
   minincome = 15000 + (4000 * dependents)

 определяет факт.

Записи

when
   (savingsAccount == "adequate") && (income == "adequate")
then
   investment = "stocks"

 и

when
   savingsAccount == "adequate"
   income == "adequate"
then
   investment = "stocks"

эквивалентны, т.к. между строками в предусловии неявно стоит операция && (and). Кстати, проблему можно определять частично, например только правила без пользовательских переменных. А определения переменных добавлять программно. Также можно подсунуть свой datasource для вытаскивания пользовательских переменных. Возможности парсера:

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

Парсер был реализован как наследник от scala.util.parsing.JavaTokenParsers. Могу лишь сказать, что писать его было одно удовольствие, при том, что опыт написания парсеров до этого у меня более чем скромный. Мощь этого инструмента заключается в том, что можно задавать шаблоны для парсинга и тут же маппинг результатов на сущности.

Нечеткие сравнения

Был реализован синтанксис задания нечеткого сравнения через функцию принадлежности. Например:

fact
  b = 2.5

when
  b~=linear(/\, 1.0, 2.5, 3.0)
then
  a=1

find a

Данная программа вернет что a = 1 с вероятностью 1.0. Давайте разберемся что произошло.
linear - имя функции - это линейная функция. /\ - форма функции, а 1.0, 2.5, 3.0 - точки аппроксимации. Таким образом считаем что на отрезке от 1.0 до 2.5 вероятность возрастает линейно от 0 до 1, от 2.5 до 3.0 убывает линейно от 1 до 0. В нашем случае b = 2.5, сделовательно в этой точке функция принадлежности выдаст 1. Если бы b = 1.75, то вероятность была бы соответственно 0.5. Это лишь самый простой пример, с помощью этой нотации можно строить и более сложные функции, с большим числом точек, а также вместо линейной функции использовать функцию poly - которая для аппроксимации строит полином в форме Лагранжа.

Быстродействие

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

Было написано 2 теста:

1. Задача из 8000 правил, для вывода искомой переменной требует срабатывания всех правил последовательно с последнего по первое. Время вывода (без разогрева jvm) около 600 мс.
2. Задача из 26 пересекающихся правил, для вывода искомой переменной строится огромное дерево c 2^14 = 16384 листьями. Время вывода (без разогрева jvm) около 770 мс.

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

Тестирование

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

Примеры

В пакете com.greentea.sie.examples есть несколько классов с живыми примерами определения правил для некоторых разных предметных областей: FinancialAdviser, ProgrammingLanguageAdviser, LoanarAdviser.

Дальнейшие направления

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