Программа 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.