Всем привет! Хочу показать общественности свой открытый движок вывода правил (forward chaining) с поддержкой нечеткой логики, под рабочим названием Scala inference engine (sie) (код).
UPD.
Библиотека выложена в центральный репозиторий maven-а:
Существует множество хороших движков вывода и экспертных систем для 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, некоторые владеют нечеткой логикой некоторые нет. Одни имеют простой синтаксис определения правил — у других он сложный и т.д.
В sie я попытался совместить возможности четкого и нечеткого вывода, простоту определения правил и гибкую конфигурацию. Именно Scala (а не java) была изначально выбрана потому, что на ней можно писать в функциональном стиле, что позволит побороть предполагаемую сложность алгоритмов, которые предстояло написать. Тем не менее, движок собирается как maven артефакт, после чего его можно подрубить к любому maven проекту на java (с дополнительной зависимостью на scala-library), и все будет работать.
Введем понятие «пересекающиеся правила». Это такие правила, которые дают заключения об одной и той же переменной. Например
В данном случае если 'a' принимает значение между 300 и 400, то выполняется оба правила и система для дальнейшего вывода должна решить по какому пути идти, т.к 'b' не может быть одновременно 5 и 10. Вообще говоря, существует несколько способов как разрулить конфликтную ситуацию:
Стратегии разрешения конфликта в Drools.
Текущая реализация (и такого я нигде не встречал) идет по другому пути.
4) Считать что оба правила равноценны и 0.5 вероятности что выполняется первое и 0.5 что второе (или в общем случае 1/N вероятности, если пересекающихся правил N).
Далее вывод разделяется на части, и продолжается в отдельности для каждой из ветвей вплоть до нахождение искомой переменной. Впоследствии считается суммарная вероятность для каждого возможного значения искомой переменной по всем ветвям вывода.
Если учесть, что правила могут причудливым образом зависить друг от друга по используемым переменным в предусловиях, что заключения могут содержать присваивания к разным переменным (так, что возможны группы пересекающихся правил, типа X пересекается с Y по переменной a, Y пересекается с Z по переменной b) то простое словесное описание идеи выливается в не очень простую реализацию. Главная цель которая была достигнута — корректное вычисление вероятностей значений принимаемых искомой переменной.
Таким образом движок хорошо справляется с базой возможно противоречивых правил, которые пересекаются:
Таким образом поддерживается элемент нечеткости в выводе.
Структура определения проблемы:
Проблему можно определять полностью программно, однако гораздо удобнее делать это используя специальный (не xml) синтаксис, который был разработан с целью быть лаконичным и сходу понятным для человека с опытом программирования.
Пример 1: Финансовый советник
Вначале идет блок определения переменных:
Это те переменные, которые не выводятся, но используются в правилах. Вначале следует тип, потом имя переменной, потом, опционально валидация на возможные значения ( min: 0 — означает что недопустимо значение меньше 0) и, тоже опционально, после < вопрос пользователю при запросе данной переменной.
Поддерживаются типы: bool, int, double, enum (он же string).
В предусловиях и заключениях могут использоваться выражения любой сложности (самое сложное в примере
Семантика арифметических операций такая же как в java. Поддерживаются неявные преобразования int к double где это нужно. По умолчанию поддерживается вызов функций из java.lang.Math, но можно регистрировать и свои функции.
Правило вида
определяет факт, т.к. его предуслвие всегда выполняется.
Записи
Эквивалентны, т.к. между строками в предусловии неявно стоит операция && (and).
Кстати, проблему можно определять частично, например только правила без пользовательских переменных. А определения переменных добавлять программно. Также можно подсунуть свой datasource для вытаскивания пользовательских переменных.
Возможности парсера:
Парсер был реализован как наследник от
Могу лишь сказать, что писать его было одно удовольствие, при том, что опыт написания парсеров до этого у меня более чем скромный. Мощь этого инструмента заключается в том, что можно задавать шаблоны для парсинга и тут же маппинг результатов на сущности.
Тестированию было уделено особое внимание. Юнит тесты пишутся для парсинга правил (от простых конструкций до определения проблемы целиком), для проверки корректности вывода (от простых задач до сложных, с запутанными пересекающимися правилами).
В пакете
UPD.
Библиотека выложена в центральный репозиторий 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, некоторые владеют нечеткой логикой некоторые нет. Одни имеют простой синтаксис определения правил — у других он сложный и т.д.
В sie я попытался совместить возможности четкого и нечеткого вывода, простоту определения правил и гибкую конфигурацию. Именно Scala (а не java) была изначально выбрана потому, что на ней можно писать в функциональном стиле, что позволит побороть предполагаемую сложность алгоритмов, которые предстояло написать. Тем не менее, движок собирается как maven артефакт, после чего его можно подрубить к любому maven проекту на java (с дополнительной зависимостью на scala-library), и все будет работать.
Killer feature
Введем понятие «пересекающиеся правила». Это такие правила, которые дают заключения об одной и той же переменной. Например
when
a > 300
then
b = 5
when
a < 400
then
b = 10
В данном случае если 'a' принимает значение между 300 и 400, то выполняется оба правила и система для дальнейшего вывода должна решить по какому пути идти, т.к 'b' не может быть одновременно 5 и 10. Вообще говоря, существует несколько способов как разрулить конфликтную ситуацию:
- Выбирать первое/последнее правило
- Задавать где-то приоритет правила
- Выбирать правило с более сложным условием (хотя в данном случае условия имеют одну сложность), исходя из предположения что более простое условие определяет общий случай, а более сложное — частные случаи.
Стратегии разрешения конфликта в Drools.
Текущая реализация (и такого я нигде не встречал) идет по другому пути.
4) Считать что оба правила равноценны и 0.5 вероятности что выполняется первое и 0.5 что второе (или в общем случае 1/N вероятности, если пересекающихся правил N).
Далее вывод разделяется на части, и продолжается в отдельности для каждой из ветвей вплоть до нахождение искомой переменной. Впоследствии считается суммарная вероятность для каждого возможного значения искомой переменной по всем ветвям вывода.
Если учесть, что правила могут причудливым образом зависить друг от друга по используемым переменным в предусловиях, что заключения могут содержать присваивания к разным переменным (так, что возможны группы пересекающихся правил, типа X пересекается с Y по переменной a, Y пересекается с Z по переменной b) то простое словесное описание идеи выливается в не очень простую реализацию. Главная цель которая была достигнута — корректное вычисление вероятностей значений принимаемых искомой переменной.
Таким образом движок хорошо справляется с базой возможно противоречивых правил, которые пересекаются:
- Ненамеренно, если правила были составлены разными экспертами и у каждого свое мнение.
- Намеренно, если одна и та же переменная может быть вычислена разными способами, например:
when graphicCardType == "Top" then graphicCard = "Nvidia super card" when graphicCardType == "Top" then graphicCard = "Radeon super card"
В данном примере советник по выбору видеокарты может посоветовать как карту от Nvidia так и карту от Radeon с равной вероятностью.
Таким образом поддерживается элемент нечеткости в выводе.
Язык определения проблемы
Структура определения проблемы:
- Задаются пользовательские переменные — те, которые будут запрашиваться в процессе вывода.
- Правила вывода, состоящие из предусловий, заключений и, по желанию, вероятности выполнения данного правила (от 0 до 1, по умолчанию 1).
- Цель — имя переменной, которую нужно найти.
Проблему можно определять полностью программно, однако гораздо удобнее делать это используя специальный (не 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?"
when
true
then
minincome = 15000 + (4000 * dependents)
when
true
then
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, но можно регистрировать и свои функции.
Правило вида
when
true
then
minsavings = 5000 * dependents
определяет факт, т.к. его предуслвие всегда выполняется.
Записи
when
(savingsAccount == "adequate") && (income == "adequate")
then
investment = "stocks"
и
when
savingsAccount == "adequate"
income == "adequate"
then
investment = "stocks"
Эквивалентны, т.к. между строками в предусловии неявно стоит операция && (and).
Кстати, проблему можно определять частично, например только правила без пользовательских переменных. А определения переменных добавлять программно. Также можно подсунуть свой datasource для вытаскивания пользовательских переменных.
Возможности парсера:
- Показываются синтаксические ошибки, строка и символ где не удалось распарсить.
- Проверка смысловых ошибок, типа определения нескольких пользовательских переменных с одним именем, или определение присваивание пользовательской переменной в заключении.
- Контроль типов: пользователь видит где произошла ошибка приведения типа.
- Поддержка вызова перегруженных функций.
Парсер был реализован как наследник от
scala.util.parsing.JavaTokenParsers.Могу лишь сказать, что писать его было одно удовольствие, при том, что опыт написания парсеров до этого у меня более чем скромный. Мощь этого инструмента заключается в том, что можно задавать шаблоны для парсинга и тут же маппинг результатов на сущности.
Тестирование
Тестированию было уделено особое внимание. Юнит тесты пишутся для парсинга правил (от простых конструкций до определения проблемы целиком), для проверки корректности вывода (от простых задач до сложных, с запутанными пересекающимися правилами).
Примеры
В пакете
com.greentea.sie.examples есть несколько классов с живыми примерами определения правил для некоторых разных предметных областей: FinancialAdviser, ProgrammingLanguageAdviser, LoanarAdviser. Дальнейшие направления
- Работа движка не должна быть черным ящиком. Необходимо усовершенствовать описание процесса вывода понятное пользователю.
- Поддержка нечетких сравнений.
Типа:
mood is Good
где mood – числовая переменная, а Good — это нечеткое понятие, определяемое функцией пренадлежности. - Тестирование производительности и использования памяти на больших массивах правил.
- Другие возможности разрешения конфликтов для пересекающихся правил.
