Программа HYPER
В листинге 19.6 показана реализация описанного выше проекта в виде программы HYPER. Основные предикаты этой программы описаны ниже.
Листинг 19.6. Программа HYPER. Процедура prove/Зприведена в листинге 19.2
I Программа HYPER (HYPothesis refinER! для решения задач обучения путем i логического вывода
:- ор( 500, xfx, :} .
4 induce ( Hyp) :
Глава 19. Индуктивное логическое программирование
% осуществляет логический вывод совместимой и полной гипотезы Hyp путем % постепенного- усовершенствования начальных гипотез
induce!. Hyp) :-initcounts, !,
start_hyps( Hyps) , best_search[ Hyps, _;Hyp)
% Инициализировать счетчики гипотез I Получить начальные гипотезы % Специализированный предикат поиска % по заданному критерию
% best_search[ CandidateHyps, FinalHypothesis)
best_search[ [Hyp I Hypsl, Hyp) :-
% Показать содержимое счетчиков гипотез
Hyp = 0:Н, % Стоимость Cost = 0; это означает, что гипотеза Н
% не охватывает ни одного отрицательного примера
complete[Н> . % Гипотеза охватывает все положительные примеры
be3t_search( !C0;HO I HypsO], Н) :-
write!'Refining hypo with cost '}, write ( CO) ,
write(:J, nl, show_hyp (HO) , nl,.
all_refinements( HO, NewHs), % Все усовершенствования гипотезы НО
add_hyps( NewHs, HypsO, Hyps), !,
addl ( refined) , % Подсчитать количество усовершенствованны!! гипотез
best_search( Hyps, H) .
all_refinements( HO, Hyps) :-findalK C:H,
1 refine_hyp(HO,H) , % H - новая гипотеза
once ( ( addl( generated), % Подсчитать количество выработанных
% гипотез
| complete(H), addl( complete), eval[H,C) |
% Гипотеза Н охватывает все положительные : примеры
4 Подсчитать количество полных гипотез С - стоимость гипотезы Н
) ) ) -Hyps).
% add_hyps! Hypsl, Kyps2, Hyps):
% выполнить слияние гипотез Hypsl и Kyps2 в порядке стоимостей
* и получить гипотезу Hyps
add_hyps( Hypsl, Hyps2, Hyps) :-merge sort! Hypsl, OrderedHypsl), merge ( Hyps2, OrderedHypsl, Hyps).
Complete! Hyp) :- % Hyp охватывает все положительные примеры
not ( ex ?), % Положительный пример
once- prove) P, Hyp, Answ)) , % Доказать его с помощью гипотезы Hyp
Answ \™ уеэ] . % Возможно, доказательство не найдено
% eval! Hypothesis, Cost):
% стоимость гипотезы Cost - Size + 10
i
* количество_охваченных_отрицательиых_примеров,
| размер |
где Size
eval! Hyp, Cost) :-size! Hyp, S) , covers_neg Hyp, ( N - 0, " ! , Cost is 0; Cost is S + 10*N) .
% Размер гипотезы б Количество охваченных отрицательным примеров I Охваченных отрицательных примеров нет
% size { Hyp, Size) :
% размер Size = kl • количество_литералов + k2
% * количество_переменных_в_1,мпотеае;
% значения коэффициентов: kl=10, k2=l
Часть II. Применение языка Prolog в области искусственного интеллекта
!< [ ] , 0 ) .
_М [CsO/VsO 1 RestHyp], Size] :-
sngth(CsO, LO),
sngtht VsO, MO) ,
iaet RestKyp, SizeRest),
ize is 10*LQ + NO + SizeRest.
overs_neg[ H, K):
N - количество отрицательных стримеров, которые, ВОЗМОЖНО, охвачены гипотезой К. Возможность тсго, что примеры охвачены гипотезой, существует, если предикат prcve/З зоэврашает значение 'ус.-- ' или
■ers_nea( Hyp, N) :- % Гипотеза Кур охватывает N отрицательных примеров indall'( 1, (nex(E), once(prove(E,Hyp,Answ)), Answ \== no) , L) , .ength( L, N) .
msatisfiablef Clause, Hyp) : предложение Clause нельзя ни при каких условиях использовать в каком-либо доказательстве; это означает, что тело предложения Clause не может быть доказано на основании гипотезы Hyp
satisfiabie; [Head Body], Hyp) :-
once С prove( Body, Hyp, Answ)),Answ = no.
art_hyps ( Hyps) :- ~t Множество начальных гипс-тез max_clauses ( M) , setof[ C:K,
(start_hyp(H,M) , addl(generated) , complete(H) , addl(complete) , eval(H,C)) , Hyps).
start_hyp( Hyp, MaxClauses):
Hyp - начальная гипотеза, количества предложений в которой не превышает MaxClauses
:art_hyp! [) , _) .
| : - % Определяемое пользователем начальное предложение |
cart_hyp< [С I Cs] , К) К > 0, Ml is M-l, start_clause[ С) , start_hypt Cs, Ml).
refine_hyp( HypO, Hyp) :
лредккат, преобразующий гипотезу НурО в гипотезу Hyp
путем усовершенствования
•efine_hyp{ HypO, Hyp) :-choose_clauset HypO, ClauseO/VarsO, Clauses!, Clauses2), I Выбрать предложение conc( Clauses 1, [Clause/Vars [ Clauses2], Hyp), t Новая гипотеза
refine С ClauseO, VarsO, Clause, Vars), - Усовершенствовать выбранное
% предложение
non_redundant( Clause), I Предложение Clause не является избыточным
not unsatisfiable[ Clause, Hyp). % Предложение Clause не является
i удовлетворяемым
choose_clauset Hyp, Clause, Clausesl, Clauses2) :- % Предикат, который выбирает
% предложение Clause из состава гипотезы Кур
СОЯС { Clausesl, [Clause | Clauses2] , Hyp), % Выбрать предложение
пех(Е), % Отрицательный пример Е
prove! E, [Clause], yes), % Пример Ё охватывает само предложение Clause
% Предложение должно бысгь усовершенствовано
Clausesl, [Clause | Clauses2], Hyp). i ! противном случае выбрать
% любое предложение
Глава 19. Индуктивное логическое программирование
* refinet Clause, Args, NewClause, MewArgs):
% предикат, который позволяет усовершенствовать предложение Clause
% с параметрами Args и случить пре дяожение NewClause С параметрами NewArgs
% Усовершенствовать по методу согласования параметров
refine( Clause, Args, Clause, HewArgs) :-
conct Argsl, [A | Args2], Args), ' i Выбрать переменную А
me.Tlber ( A, Args2), Согласовать ее с другой переменной
СОПСС Argsl, Args2, NewArgs).
% Усовершенствовать переменную по методу преобразования в терм
refine( Clause, ArgsO, Clause, Argsl :-
del( Var:Type, ArgsO, Argsl), Удалить переменную Var:Type
i из множества параметре в ArgsO
term'' Type, Var, Vars) , % Переменная var становится термом типа Type
СОПС( Argsl, Vars, Args) . 4 Ввести переменные в новый терм
% Усовершенствовать предложение путем добавления литерала
refine( Clause, Args, NewClause, KewArgs) :-
length( Clause, L),
max_clause_length ( MaxL) ,
L < MaxL,
backliteral( Lit, InArgs, RestArgs), % Литерал с определением фоновых знаний
cone! Clause, [Lit], NewClause], - Добавить литерал к телу предложения
connect_inputs i. Args, InArgs}, % Соединить входные параметры литерала
! с другими параметрами
cone! Args, RestArgs, KewArgs). i Добавить остальные параметры литерала
■ поп redundant; Clause) : очевидно, что предложение Clause
% не имеет избыточных литералов
xiQn_redundant ( [_]) . % Предложение с одним литералом
non_redundant( {Litl I Lits]) :-not literaljnember ■: Litl, Lits), nor. redundant! Lits).
literal_member( X, [XI I Xs]) :- % Переменная :■' в полном смысле слова
% равна элементу списка X == XI, !
literaljnember [ X, Xs) .
% show_hyp( Hypothesis}:
% предикат, который выводит гипотезу Hypothesis в удобной для чтения форме,
% с именами переменных А, В,
show_hyp( []) :- nl.
show_hyp( [C/Vars | Cs]) :- nl, copy term( C/Vars, Cl/Varsl),
s~vars( Varsl, ['A', ' Б' , ' С ',' D' , ' E ' , ?' ,'G' ,'R' , ' I ', ' J', ' К ', " L ', 'К', "N']j, show_clause[ CD , show_hyp( Cs), ! .
show_clause( (Head | Body]) :-
write [ Head} ,
( Body = [] ; write ( ':-' ), nl ), write_body( Body).
write_body( []} :-
write { ' . '), ! .
466 Часть II. Применение языка Prolog в области искусственного интеллекта
write_body! |G [ Gs]) :- !, tab( 2), write( G!, ( Gs = [], ! , write ( '.'}» nl
write!', ' ) , nl, write_bodyt Gs)
) .
name_vars { [], _) .
name_varst [Kame:Type I Xs] , [Name i Names]i :-name_vars[ Xs, Names).
* connect_inputs( Vars, Inputs):
предикат, который согласует каждую переменную в списке Inputs с переменной I в списке Vars
eor.nect_inputs ( _, [] ) .
connect_inputsf S, [X I Xs] ) :-membert x, S) , conr.ect_in.puts ( s, Xs) .
% merge! LI, L2 , L3) : предикат слияния, в котором все параметры,
% заданные в виде списков, отсортированы
merge ( [] , L, L) :- ! .
merge ( L, [ ] , L) : - ! .
merge! [Xl|Ll], [X2IL2], [X1IL3]) :-
XI g = < X2, !, % XI "лексикографически предшествует" Х2 (встроенный предикат)
merge( LI, 1X2|L2), L3]. merge) LI, [X2|L2], [X21L3]) :-
merge( Ll, L2, L3).
4 mergesort[ Ll, L2) : предикат, который сортирует список Ll, формируя список L2
mergesort ( [] , [] ) :- ! .
mergesort! [x:, [X]) :- !.
mergesort! L, s) :-split! L, Ll, L2) , mergesort! Ll, El) , mergesort! L2, S2) , merge! SI, S2, 5) .
% split! L, Ll, L2) : предикат, который разбивает список L на два списка % примерно разной длины
split. ( [] , [] , []) .
split [ [X] , [X], []>•
split! (XI,Х2 I L], [XIЦЛЬ [X2iL2]) :-split! L, Ll, L2) .
I Счетчики сформированных, полных и усовершенствованных гипотез
init_counts :-
retract! counteri_,_)!, fail % Удалить прежние значения счетчиков
assert! counter! generated, 0) J , % Инициализировать счетчик сформированных
% гипотез
Глава 19. Индуктивное логическое программирование
assert ( counter ( complete, 01), % Инициализировать счетчик полных гипотез assert ( counter! refined, 0)). % Инициализировать счетчик
% усовершенствованных гипотез
addl! Counter) :-
retract! countei( Counter, Щ ) , !, N1 is N + l, assert ( counter! Counter, N1)).
show counts :-
counter generated, KG), counter! refined, NR), counter! complete, NO,
nl, write! 'Hypotheses generated: ■), write(KG),
nl, write! 'Hypotheses refined: '), write (NR),
ToBeRefined is NC - NR,
nl, write! 'To be refined: '), write ( ToBeRefined), nl.
Значения параметров
max_proof_length | 6). % Максимальная длина доказательства с учетом
% вызовов предикатов в гипотезах
max_clauses( 4). % Максимальное количество предложений в гипотезах
ma>;^clause_lerigth ( 5). % Максимальное количество литералов в теле предложении
• refine hyp ( HypO, Hyp). Предикат, который в процессе усовершенствования
преобразует гипотезу НурО в Hyp, усовершенствовав одно из предложений в
НурО.
• refine ( Clause, Vars, NewClause, NewVars). Предикат, преобразующий в
процессе усовершенствования данное предложение Clause с переменными
Vars и вырабатывающий усовершенствованное предложение NewClause с пе
ременными NewVars. Это усовершенствованное предложение формируется пу
тем согласования двух переменных одного и того же типа в списке Vars, или
путем усовершенствования переменной в списке Vars с преобразованием в
терм, или путем добавления нового фонового литерала к предложению Clause.
• induce_hyp { Hyp). Предикат, который логически выводит совместимую и полную гипотезу Hyp для данной задачи обучения. В этом предикате осуществляется поиск по заданному критерию путем вызова предиката best_search/2.
• best_search< Hyps, Hyp). Процедура, которая начинает работу с множества
начальных гипотез Hyps, выработанных предикатом stazt_hyps/l, и выполняет поиск по заданному критерию в лесу усовершенствования до тех пор, пока не будет найдена совместимая и полная гипотеза Hyp. В этой процедуре для управления поиском в качестве функции оценки используется стоимость гипотез. Каждая рассматриваемая гипотеза применяется в сочетании с ее стоимостью в виде терма Cost: Hypothesis. Во время сортировки списка таких термов (по методу сортировки и слияния) гипотезы сортируются по возрастанию стоимости.
• prove t Goal, Hyp, Answer). Интерпретатор с ограничением длины доказательства, который определен в листинге 19.2.
• eval i Hyp, Cost). Функция оценки гипотез. В параметре Cost учитываются размер гипотезы Hyp и количество отрицательных примеров, охваченных гипотезой Кур. Если Кур не охватывает ни одного отрицательного примера, то
Cos- = 0.
• start_hyps( Hyps). Предикат, который вырабатывает множество Hyps на
чальных гипотез для поиска. Каждая начальная гипотеза представляет собой
список, состоящий из начальных предложений в количестве вплоть до
MaxClauses. Значение MaxClauses определяется пользователем с помощью
468 Часть II.Применение языка Prolog в области искусственного интеллекта
предиката гаах clauses. Начальные предложения определяются пользователем с использованием предиката start_clause.
• show hyp { Hyp) . Предикат, отображающий гипотезу Hyp в обычном формате Prolog.
• init counts, show_counts, add! (Counter). Предикаты, которые инициализируют, отображают и обновляют счетчики гипотез. Отдельно подсчитываются гипотезы трех типов: выработанные (количество всех выработанных гипотез), полные (количество выработанных гипотез, которые охватывают все положительные примеры) и усовершенствованные (количество всех усовершенствованных гипотез).
• start_clause ( Clause] . Определяемые пользователем начальные предложе
ния (наподобие следующего), которые обычно представляют собой нечто очень
общее:
start_clause( [ member (X,L! ] / [ K:item, L:list]) .
• max proof length0), так clauses (MaxClauses), max clause lengthCMaxLength).
Предикат, определяющие следующие параметры: максимальная длина дока
зательства, максимальное количество предложений в гипотезе и максимальное
количество литералов в предложении. Например, при изучении предиката
member/2 или сопс/3 достаточно задать MaxClauses=2. По умолчанию в про
грамме, приведенной в листинге 19.6, заданы следующие значения:
max_proof_Iength(б). max_clause3(4). max_clause_length(5}.
Для программы в листинге 19.6 требуются также такие часто используемые предикаты, как not/1, once/1, member/2, cone/3, del/3, length/2, copy_term/2.
В качестве иллюстрации вызовем на выполнение программу HYPER для решения задачи изучения предиката member (X, L). Кроме самой программы HYPER, в систему Prolog необходимо загрузить определение задачи, приведенное в листинге 19.4. После этого программе можно задать следующий вопрос: ?- induce (Н) , 5how_hyp!H).
Во время выполнения программа HYPER последовательно отображает текущее количество гипотез (выработанных, усовершенствованных и ожидающих усовершенствования), а также показывает гипотезу, которая в настоящее время проходит процесс усовершенствования. Эта программа вырабатывает следующие окончательные результаты:
Hypotheses generated: 105 t Количество выработанных гипотез
Hypotheses refined: 26 * Количество уса ввршвютвовашшх гипотез
Тс be refined: 15 % Количество гипотез, подлежащих усовершенствованию
гаеиЬег(&, (AjB]).
member(С, [А|В]) : -member (С, В) .
Логически выведена именно такая гипотеза, как и следовало ожидать. До того как была найдена эта гипотеза, всего было выработано 105 гипотез, 26 из них были усовершенствованы, а 15 все еще оставались в списке кандидатов на усовершенствование. Разность 105 - 26 - 15-51 показывает, сколько найденных неполных гипотез было немедленно отброшено. Необходимая глубина усовершенствования для этой задачи обучения равна 5 (см. листинг 19,5). Общее количество возможных гипотез в пространстве усовершенствования, которое определено с. помощью данного (ограниченного) оператора усовершенствования программы HYPER, составляет несколько тысяч. Программа HYPER выполнила поиск только в очень ограниченной части этого пространства (составляющей меньше 10%). Эксперименты показали, что при решении более сложных задач обучения (конкатенация списков, поиск маршрутов) это соотношение становится еще меньше.
Глава 19, Индуктивное логическое программирование
Упражнение
19.5. Определите задачу обучения для изучения предиката конкатенации списков cone (LI, L2, L3) в соответствии с соглашениями, показанными в листинге 19.4, и вызовите на выполнение программу HYPER с этим определением, Определите глубину усовершенствования целевой гипотезы и оцените размер дерева усовершенствования для этой глубины при начальной гипотезе, состоящей из двух предложений. Сравните этот размер с количеством гипотез, выработанных и усовершенствованных программой HYPER.