- Последнее изменение этой страницы: 15:37, 30 октября 2009.
- Текст доступен на условиях лицензии Creative Commons Attribution/Noncommercial/Share-Alike
-
-
Цель статьи состоит в демонстрации простейшей экспертной системы, реализованной на языке Erlang, использующей продукционную модель представления знаний и позволяющей определить транспортное средство по введенным характеристикам. Хотя, это приложение с одинаковым успехом может иметь и другие применения, например, определение заболевания по указанным симптомам и т. д.
Довольно часто системы искусственной разумности (ИР для краткости. Буду называть их так: «Под ИИ понимают не робота, наделенного способностями человеческого разума и прошедшего тест Тьюринга: в английской литературе словосочетание artificial intelligence звучит не столь вызывающе, как по-русски, и может переводиться как искусственная разумность.» — Адаменко, Кучуков, 2003, стр. 140) и, в частности, экспертные системы разрабатываются на языках и с помощью средств, специфичных для рассматриваемой проблемной области, таких, например, как Prolog, LISP, CLIPS и т. д.
Поскольку Erlang/OTP — язык функционального программирования, и в первую очередь был предназначен решать проблемы в области телекоммуникаций (теперь его можно считать языком общего назначения), то, что называется, «из коробки», тот набор средств, предоставляемых Erlang/OTP, не дает полноценной возможности программирования экспертных систем. В связи с этим командой энтузиастов был разработан инструмент ERESYE, который будет использован в данном приложении.
ERESYE – это библиотека предназначенная для создания, исполнения машин обработки правил, управления ими, и, таким образом, подходящая для реализации экспертных систем.
Каждая машина имеет имя и базу знаний (knowledge base, KB); KB состоит из базы фактов (fact base, FB), которая хранит набор фактов, представляющих текущее состояние, и базы правил (rule base, RB), хранящей набор правил вывода, представляющих возможности осмысления машины. Все это вместе, как правило, отражает ту или иную предметную область. Каждый факт записывается в форме кортежа Erlang, например {temperature, 50, 'F'}, {alarm, on}, {speed, 30, 'km/h'}. Правила вывода, которые представляют действия, необходимые к выполнению машиной, когда один или более фактов утверждаются (asserted) в FB, вместо этого записываются, используя стандартные функции Erlang. В частности, каждое правило ERESYE реализуется через клозы функции, где первый параметр представляет имя машины, в котором исполняется правило, а другие параметры являются кортежами, представляющими шаблоны фактов, которые должны быть утверждены в FB, для того чтобы правило активировалось (более подробно см. документацию в директории doc, помещающейся в архив с дистрибутивом ERESYE на сайте проекта).
Таким образом, в свете изложенных сведений, для реализации экспертной системы нужно:
Мы спроектируем систему, способную выводить новые знания, используя некоторый набор правила вывода; в качестве приложения выберем область типа транспорта: мы начнем с некоторого простого понятия вроде transport, а потом средствами специфических правил выведем понятие kindof.
В соответствии с описанными выше понятиями, мы, прежде всего, выведем факты, которые будут использованы для представления наших понятий. Имея отношения, описанные выше, они будут представлены средствами следующих фактов:
| # | Понятие | Факт / кортеж Erlang |
|---|---|---|
| 1 | X является транспортом со списком характеристик Y |
{transport, X, Y} |
| 2 | X является списком доступных характеристик |
{props, X} |
| 3 | X является воздушным транспортом |
{kindof, aerial, X} |
| 4 | X является военным транспортом |
{kindof, military, X} |
%% ERESYE rule. Any transport than has airscrew or wings is interpreted as aerial
%% and the fact {kindof, aerial, TransporName} is asserted.
%%
%% if (Properties contain airscrew) or (Properties contain wings)
%% then (Transport is aerial)
%%
aerial(Engine, {transport, Transport, Properties}) when is_list(Properties) ->
case lists:any(fun(X) -> lists:member(X, [airscrew, wings]) end, Properties) of
true ->
eresye:assert(Engine, {kindof, aerial, Transport});
_->
void
end.
%% if (Properties contain armour) or (Properties contain gun_tube)
%% then (Transport is military)
military(Engine, {transport, Transport, Properties}) when is_list(Properties) ->
case lists:any(fun(X) -> lists:member(X, [armour, gun_tube]) end, Properties) of
true ->
eresye:assert(Engine, {kindof, military, Transport});
_->
void
end.
Это правила, реализованные с помощью клозов функций Erlang. Голова первого правила определяет, что при утверждении любого факта в FB, соответствующего кортежу {transport, Transport, Properties}, оно будет выполнено. Тело этого правила проверяет, принадлежит ли очередному виду транспорта какое-либо из свойств, как [airscrew, wings], т. е. воздушный винт, либо крылья, и если это так, то в FB вносится факт в виде {kindof, aerial, Transport}, где Transport — имя транспорта. Т. о. этот вид транспорта будет считаться воздушным (aerial). Например, факт {kindof, aerial, helicopter_ka50} будет одним из тех, который попадет в FB, поскольку в нее добавлялось утверждение {transport, helicopter_ka50, [airscrew, armour, engine, wheels]}, активирующее рассмотренное правило.
Аналогично — со вторым правилом. В этом случае будет добавлен тип военный (military), если какое-либо из свойств, которыми обладает транспорт, присутствует в списке [armour, gun_tube].
Для людей, знакомых с Erlang и/или Prolog, код программы покажется довольно самоописательным и понятным. Для новичков же он подробно объясняется далее по тексту.
-export([start/0, stop/0, show_kb/0, guess/0, add_transport/0, add_property/0]). -export([aerial/2, military/2]).
Первая строка кода экспортирует пользовательские функции, вторая — функции, выступающие в роли правил для ERESYE. Эти объявления можно было бы заменить на -compile(export_all). Но это, как правило, не считается хорошим тоном, т. к. экспортирует все функции, делая их доступными вне модуля и обычно используется в процессе разработки или отладки приложения.
-define(ENGINE, transport).Макрос, задающий имя машины вывода.
start() ->
% load ERESYE binary module if it hasn't been yet
code:ensure_loaded(eresye),
% start ERESYE engine with specified name
eresye:start_link(?ENGINE),
% add rules
lists:foreach(fun(X) -> eresye:add_rule(?ENGINE, {?MODULE, X}) end, [aerial, military]),
% populate knowledge base with some facts
eresye:assert(?ENGINE,
[{props, [airscrew, armour, wings, bucket, chain, conditioner,
engine, gun_tube, spokes, track, wheels]},
{transport, moskvitch412, [engine, wheels, conditioner]},
{transport, excavator, [engine, track, bucket]},
{transport, bicycle, [wheels, spokes, chain]},
{transport, motorcycle, [engine, wheels, spokes, chain]},
{transport, tank_t34, [armour, engine, track, gun_tube]},
{transport, helicopter_mi8, [airscrew, engine, wheels]},
{transport, helicopter_ka50, [airscrew, armour, engine, wheels]},
{transport, plane_su27, [wings, armour, engine, wheels]}
]).
Здесь вызов code:ensure_loaded(eresye) проверяет, загружен ли модуль eresye и если это не так, загружает его, затем запускается сервер ERESYE вызовом eresye:start_link(?ENGINE), после этого в RB с помощью вызова add_rule/2 добавляются правила, а с помощью assert/2 в FB добавляются факты.
show_kb() -> eresye:get_kb(?ENGINE).Выводит содержимое KB.
%% Adds a new transport to the available transport list in the FB
add_transport() ->
Transp = get_name("Please enter a transport name: "),
eresye:assert(?ENGINE, {transport, Transp, ask_props()}).
%% Adds a new property to the available properties list in the FB
add_property() ->
NewProp = get_name("Please enter a property name: "),
CurProps = get_props(),
eresye:retract(?ENGINE, {props, CurProps}),
eresye:assert(?ENGINE, {props, [NewProp|CurProps]}).
Функции add_transport/0 и add_property/0 добавляют соответственно новый транспорт и новую характеристику (свойство) транспорта в FB.
%% @spec get_props() -> list(atom())
%% Returns the list of properties that a kind of transport can possess
get_props() ->
{props, Props} = hd(eresye:query_kb(?ENGINE, {props, '_'})),
Props.
Как видно из спецификации, функция get_props/0 возвращает текущий список свойств, находящихся в FB. Примечательно, что в запросе query_kb/2 фигурирует кортеж {props, '_'}, где вторым элементом является атом '_', это не анонимная переменная _, а специальный символ (групповой символ, джокер, wildcard), говорящий ERESYE, что вторая позиция может быть сопоставлена с любым термом. В данном случае в FB находится только одно подходящее утверждение {props, [airscrew, armour, wings, bucket, chain, conditioner, engine, gun_tube, spokes, track, wheels]}, и оно будет возвращено в результирующий список. Поэтому мы используем функцию hd/1 для извлечения головы списка, в котором — лишь один вышеупомянутый факт.
% Gets input from user until an entered line meets these requirements:
% starts with lowercase letter followed by lowercase letters, digits
% or underscore ('_'), e. g. example_1
get_name(Prompt) when is_list(Prompt) ->
Line = io:get_line(Prompt),
case re:run(Line, "^[a-z]*[a-z,0-9,_]*\n$") of
{match, _} ->
list_to_atom(hd(string:tokens(Line, "\n")));
nomatch ->
io:format("Wrong input, please use only lowercase Latin characters, digits and undersore.~n", []),
get_name(Prompt)
end.
Эта функция служит для получения информации, введенной пользователем с клавиатуры и ее преобразования в атом, который может быть использован для именования транспортного средства или очередного свойства транспортного средства. Здесь использовались регулярные выражения для проверки корректности ввода данных, функция string:tokens/2 для разбиения строки на список, элементы которого отделяются символом перевода строки. В данном случае, нас интересует только первый элемент списка.
%% @spec ask_props() -> list(atom())
%% Returns the list of properties selected by the user from available properties
ask_props() ->
Filter = fun(Prop) ->
case io:get_line("Does this kind of transport have "
++ atom_to_list(Prop) ++ "? ") of
"y"++_ ->
true;
_ ->
false
end
end,
lists:filter(Filter, get_props()).
Функция ask_props/0 используется для взаимодействия с пользователем и получения списка свойств, которыми обладает предполагаемый транспорт, подлежащий определению по полученным характеристикам. Здесь защита (guard) "y"++_ срабатывает, когда пользователь вводит строку, начинающуюся с символа y (игрек, лат.), и возвращается атом true, в противном случае — атом false. Функция lists:filter/2 формирует на основе переданного ей списка новый список, включающий только те элементы, результатом применения функции к которым было значение true.
%% Asks the user for properties which transport possesses %% and triggers guessing process guess() -> guess(ask_props()).Функция запрашивает список характеристик, необходимых для определения транспорта и передает его функции
guess/1.
%% Tries to find kinds of transport which match best the given properties
guess(Properties) when is_list(Properties) ->
% Filter out objects which have appropriate Properties
% Any item which makes fun(X) return true is included in result
%Fun1 = fun(X) -> lists:all(fun(Y) -> lists:member(Y, Properties) end, X) end,
Fun2 = fun(X) -> if
is_list(X) ->
lists:all(fun(Y) -> lists:member(Y, Properties) end, X);
true ->
false
end
end,
TupleList = eresye:query_kb(?ENGINE, {transport, '_', Fun2}),
% Explain result
lists:foreach(fun({transport, Name, Props}) ->
io:format("I assume this might be ~w because it has the following properties: ~w~n",
[Name, Props]) end, TupleList).
Эта функция является основной частью программы, реализующей ее логику и объяснительную компоненту. Здесь следует отметить один важный момент. Обратите внимание на функции Fun1 и Fun2. Первая — не сработала бы, вызвав смерть процесса, поскольку, когда при переборе фактов в FB встретится, например, факт {kindof, aerial, plane_su27}, то возникнет ошибка отсутствия подходящего для сопоставления клоза:
** exception error: no function clause matching
lists:all(#Fun<transport_expert.8.43570349>,plane_su27)
in function eresye:'-query_kb/2-lc$^1/1-1-'/1
in call from eresye:'-query_kb/2-lc$^1/1-1-'/1
in call from eresye:'-query_kb/2-fun-3-'/2
in call from lists:'-filter/2-lc$^0/1-0-'/2
in call from transport_expert:guess/1
это потому что в процессе вывода, при сопоставлении факта, в силу реализации ERESYE, машина вывода сопоставляет все элементы факта от первого до последнего, формируя список истинности для каждого проверяемого факта, а затем производит конъюнкцию всех значений истинности. Например, машина вывода сформирует список [false, true, false] для факта {kindof, aerial, plane_su27} при запросе eresye:query_kb(?ENGINE, {transport, '_', Fun2}), поскольку только один из элементов совпал с запросом и в результате конъюнкции будет получен результат false. Т. е. факт, очевидно, не соответствует запросу. В данном случае функция lists:all/2 принимает функцию в качестве первого аргумента и список в качестве второго, но если попадается факт {kindof, aerial, plane_su27}, то, как уже отмечено, подходящего клоза не находится и возникает ошибка, так как, plane_su27 является атомом, а не списком. Поэтому в Fun1 здесь была введена дополнительная проверка, после которой функция превратилась в Fun2. Это явилось небольшим неудобством для меня. На момент написания статьи использовалась ERESYE версии 1.2.4. Возможно, поведение системы изменится в будущем, поэтому следите за развитием событий на сайте проекта.
Запуск Erlang shell нужно осуществлять с добавлением в список директорий пути к приложению ERESYE, например:
% erl -pa /home/kingping/ERESYE-1.2.4/ebin/Ключ
-pa сообщает системе, что нужно включить указанный путь в список директорий.
Erlang R13B02 (erts-5.7.3) [rq:1] [async-threads:0]
Eshell V5.7.3 (abort with ^G)
1> c(transport_expert).
{ok,transport_expert}
2> transport_expert:start().
ok
3>
После вызова функции transport_expert:start/0 машина вывода создается и заполняется. Если ошибок не возникло, то правила должны были обработаться, а новые факты выведены. Для того чтобы проверить это, запустим функцию transport_expert:show_kb/0, которая выводит список утверждений, внесенных в KB данной машины:
3> transport_expert:show_kb().
[{kindof,aerial,plane_su27},
{kindof,military,plane_su27},
{kindof,military,helicopter_ka50},
{transport,plane_su27,[wings,armour,engine,wheels]},
{kindof,aerial,helicopter_ka50},
{transport,helicopter_ka50,[airscrew,armour,engine,wheels]},
{kindof,aerial,helicopter_mi8},
{transport,helicopter_mi8,[airscrew,engine,wheels]},
{kindof,military,tank_t34},
{transport,tank_t34,[armour,engine,track,gun_tube]},
{transport,motorcycle,[engine,wheels,spokes,chain]},
{transport,bicycle,[wheels,spokes,chain]},
{transport,excavator,[engine,track,bucket]},
{transport,moskvitch412,[engine,wheels,conditioner]},
{props,[airscrew,armour,wings,bucket,chain,conditioner,
engine,gun_tube,spokes,track,wheels]}]
4>
Наличие фактов, отражающих такие понятия, как kindof, aerial и kindof, military, подтверждает, что правила, похоже, работают так, как ожидалось.
Мы, однако, можем запросить информацию из KB, используя специфичные шаблоны фактов. Например, если мы хотим знать список всех военных видов транспорта, мы можем использовать функцию eresye:query_kb/2 таким образом:
4> eresye:query_kb(transport, {kindof, military, '_'}).
[{kindof,military,plane_su27},
{kindof,military,helicopter_ka50},
{kindof,military,tank_t34}]
5>
Возвращенные факты подкрепляются отношениями, отображенными на диаграмме выше, таким образом, подтверждая, что записанные правила действительно работают.
Теперь попробуем добавить новые характеристики и транспорт:
5> transport_expert:add_property(). Please enter a property name: atomic_reactor ok 6> transport_expert:add_property(). Please enter a property name: periscope ok 7> transport_expert:add_transport(). Please enter a transport name: submarine Does this kind of transport has periscope? yes Does this kind of transport has atomic_reactor? yup Does this kind of transport has airscrew? no Does this kind of transport has armour? yeppers Does this kind of transport has wings? nope Does this kind of transport has bucket? noes Does this kind of transport has chain? newp Does this kind of transport has conditioner? nah Does this kind of transport has engine? yeah Does this kind of transport has gun_tube? nahh Does this kind of transport has spokes? nooo Does this kind of transport has track? nuh Does this kind of transport has wheels? nono ok 8>Приложение запросило информацию, необходимую для ввода характеристик и транспорта и поместила их в KB:
8> eresye:get_kb(transport).
[{kindof,military,submarine},
{transport,submarine,
[periscope,atomic_reactor,armour,engine]},
{props,[periscope,atomic_reactor,airscrew,armour,wings,
bucket,chain,conditioner,engine,gun_tube,spokes,track,
wheels]},
{kindof,aerial,plane_su27},
{kindof,military,plane_su27},
{kindof,military,helicopter_ka50},
{transport,plane_su27,[wings,armour,engine,wheels]},
{kindof,aerial,helicopter_ka50},
{transport,helicopter_ka50,[airscrew,armour,engine,wheels]},
{kindof,aerial,helicopter_mi8},
{transport,helicopter_mi8,[airscrew,engine,wheels]},
{kindof,military,tank_t34},
{transport,tank_t34,[armour,engine,track,gun_tube]},
{transport,motorcycle,[engine,wheels,spokes,chain]},
{transport,bicycle,[wheels,spokes,chain]},
{transport,excavator,[engine,track,bucket]},
{transport,moskvitch412,[engine,wheels,conditioner]}]
9>
Из результатов запроса видно, что появились новые утверждения в FB, связанные с подводной лодкой, и что правила сработали.
Выше было описано, как устроена функция guess/1, выполняющая основное предназначение приложения. Вместо джокера '_', как вы уже, возможно, догадались, можно использовать fun в качестве элемента кортежа при запросе. Давайте проверим способность экспертной системы определить тип транспорта:
9> transport_expert:guess(). Does this kind of transport has periscope? n Does this kind of transport has atomic_reactor? n Does this kind of transport has airscrew? n Does this kind of transport has armour? n Does this kind of transport has wings? n Does this kind of transport has bucket? n Does this kind of transport has chain? y Does this kind of transport has conditioner? n Does this kind of transport has engine? y Does this kind of transport has gun_tube? n Does this kind of transport has spokes? y Does this kind of transport has track? n Does this kind of transport has wheels? y I assume this might be motorcycle because it has the following properties: [engine,wheels,spokes,chain] I assume this might be bicycle because it has the following properties: [wheels,spokes,chain] ok 10>Система выдала два варианта, наиболее близко соответствующих введенным пользователем характеристикам.
Приведу цитату из Artificial Intelligence with Erlang: the Domain of Relatives (Trapexit.org), с которой я полностью согласен:
Эта статья не только показывает применение машины вывода ERESYE для написания приложения ИР, но также подчеркивает многосторонность языка Erlang: характеристики функционального и символьного программирования наряду с возможностью выполнения интроспекции (самоанализа (логики поведения)) объявления функции могут быть успешно использованы для прикладных областей, являющихся абсолютно новыми для Erlang, но, можно с уверенностью сказать, очень интересными.
Исходный код рассмотренной экспертной системы (архив).
На сайте вы можете найти аналогичное приложение (257 KiB), реализованное на Visual Prolog 5.2.