|
|
pl:prolog:pllib:minihyper_ilp_program [2019/06/27 15:50] |
pl:prolog:pllib:minihyper_ilp_program [2019/06/27 15:50] (aktualna) |
| ====== Minihyper ilp program ====== |
| {{tag>ILP}} |
| ===== Description ===== |
| MINIHYPER - a simple ILP program. |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{minihyper_ilp_program.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % Figure 19.4 MINIHYPER - a simple ILP program. |
| |
| :- op( 900, fy, not). |
| |
| % not Goal): negation as failure; |
| % Note: This is often available as a built-in predicate, |
| % often written as prefix operator "\+", e.g. \+ likes(mary,snakes) |
| |
| not Goal :- |
| Goal, !, fail |
| ; |
| true. |
| |
| % Program MINIHYPER |
| |
| % induce( Hyp): |
| % induce a consistent and complete hypothesis Hyp by gradually |
| % refining start hypotheses |
| |
| induce( Hyp) :- |
| iter_deep( Hyp, 0). % Iterative deepening starting with max. depth 0 |
| |
| iter_deep( Hyp, MaxD) :- |
| write( 'MaxD = '), write( MaxD), nl, |
| start_hyp( Hyp0), |
| complete( Hyp0), % Hyp0 covers all positive examples |
| depth_first( Hyp0, Hyp, MaxD) % Depth-limited depth-first search |
| ; |
| NewMaxD is MaxD + 1, |
| iter_deep( Hyp, NewMaxD). |
| |
| % depth_first( Hyp0, Hyp, MaxD): |
| % refine Hyp0 into consistent and complete Hyp in at most MaxD steps |
| |
| depth_first( Hyp, Hyp, _) :- |
| consistent( Hyp). |
| |
| depth_first( Hyp0, Hyp, MaxD0) :- |
| MaxD0 > 0, |
| MaxD1 is MaxD0 - 1, |
| refine_hyp( Hyp0, Hyp1), |
| complete( Hyp1), % Hyp1 covers all positive examples |
| depth_first( Hyp1, Hyp, MaxD1). |
| |
| complete( Hyp) :- % Hyp covers all positive examples |
| not (ex( E), % A positive example |
| once( prove( E, Hyp, Answer)), % Prove it with Hyp |
| Answer \== yes). % Possibly not proved |
| |
| consistent( Hyp) :- % Hypothesis does not possibly cover any negative example |
| not (nex( E), % A negative example |
| once( prove( E, Hyp, Answer)), % Prove it with Hyp |
| Answer \== no). % Possibly provable |
| |
| % refine_hyp( Hyp0, Hyp): |
| % refine hypothesis Hyp0 into Hyp |
| |
| refine_hyp( Hyp0, Hyp) :- |
| conc( Clauses1, [Clause0/Vars0 | Clauses2], Hyp0), % Choose Clause0 from Hyp0 |
| conc( Clauses1, [Clause/Vars | Clauses2], Hyp), % New hypothesis |
| refine( Clause0, Vars0, Clause, Vars). % Refine the Clause |
| |
| % refine( Clause, Args, NewClause, NewArgs): |
| % refine Clause with arguments Args giving NewClause with NewArgs |
| |
| % Refine by unifying arguments |
| |
| refine( Clause, Args, Clause, NewArgs) :- |
| conc( Args1, [A | Args2], Args), % Select a variable A |
| member( A, Args2), % Match it with another one |
| conc( Args1, Args2, NewArgs). |
| |
| % Refine by adding a literal |
| |
| refine( Clause, Args, NewClause, NewArgs) :- |
| length( Clause, L), |
| max_clause_length( MaxL), |
| L < MaxL, |
| backliteral( Lit, Vars), % Background knowledge literal |
| conc( Clause, [Lit], NewClause), % Add literal to body of clause |
| conc( Args, Vars, NewArgs). % Add literal's variables |
| |
| % Default parameter settings |
| |
| max_proof_length( 6). % Max. proof length, counting calls to 'non-prolog' pred. |
| |
| max_clause_length( 3). % Max. number of literals in a clause |
| </code> |
| ===== Comments ===== |
| |