% General to specific induction algorithm

% run_general() :- Calls general_to_specific with H initialized
% 	to the most general feature vector and N initialized to []
%	Also, provides the types for specializing simple vectors of 
%	type [size, color, shape].

run_general :-
	general_to_specific([[_,_,_]], [], 
	[[small, medium, large], [red, blue, green], [ball, brick, cube]]).

% general_to_specific(List_of_hypotheses, List_of_positives, List_of_types) :-
%	This is the top level control loop. It reads in a new positive or
% 	negative instance and calls process to update List_of_hypotheses
%	and List_of_positives. List_of_types is passed in for specializing
%  	descriptions.
general_to_specific(H, P, Types) :-
	write("H = "), write(H),nl,
	write("P = "), write(P),nl,
	write("Enter Instance "),
	process(Instance, H, P, Updated_H, Updated_P, Types),
	general_to_specific(Updated_H, Updated_P, Types).
% process(Instance, List_of_hypotheses, List_of_positives, 
%		Updated_hypotheses, Updated_positives, List_of_types) :-
%	updates List_of_hypotheses and List_of_types in response to
%	Instance.  LIst_of_types is passed through to enable specialization.
process(negative(Instance), H, P, Updated_H, P, Types) :- 
	specialize_set(H,Spec_H, Instance, Types),
	delete(X, Spec_H, (member(Y, Spec_H), more_general(Y, X)), Pruned_H),
	delete(X, Pruned_H, (member(Y, P), not(covers(X, Y))), Updated_H).

process(positive(Instance), H, P, Updated_H, [Instance|P], _) :-
	delete(X, H, not(covers(X, Instance)), Updated_H).
process(Input, H, P, H, P,_):- 
	Input \= positive(_),
	Input \= negative(_),
	write("Enter either positive(Instance) or negative(Instance) "), nl.

specialize_set([], [], _, _).
specialize_set([Hypothesis|Rest],Updated_H,Instance, Types):-
	covers(Hypothesis, Instance),			
	(bagof(Hypothesis, specialize(Hypothesis, Instance, Types), 
	Updated_head); Updated_head = []),
	specialize_set(Rest, Updated_rest, Instance, Types),
	append(Updated_head, Updated_rest, Updated_H).
specialize_set([Hypothesis|Rest],[Hypothesis|Updated_rest],Instance, Types):-
	not (covers(Hypothesis, Instance)),			
	specialize_set(Rest,Updated_rest, Instance, Types).

specialize([Prop|_], [Inst_prop|_], [Instance_values|_]):-
	member(Prop, Instance_values),
	Prop \= Inst_prop.
specialize([_|Tail], [_|Inst_tail], [_|Types]):-
	specialize(Tail, Inst_tail, Types).

% more_general(Feature_vector_1, Feature_vector_2) :- succeeds if
%	Feature_vector_1 is strictly more general than Feature_vector_2

more_general(X, Y) :-  not(covers(Y, X)), covers(X, Y).

% covers(Feature_list_1, Feature_list_2) :- Succeeds if Feature_list_1
%	covers Feature_list_2.  Note that covers, unlike unification is
%	not symmetric: variables in Feature_list_2 will not match constants
%	in Feature_list_1.

covers([H1|T1], [H2|T2]) :-
	var(H1), var(H2), 
	covers(T1, T2).
covers([H1|T1], [H2|T2]) :-
	var(H1), atom(H2), 
	covers(T1, T2).	
covers([H1|T1], [H2|T2]) :-
	atom(H1), atom(H2), H1 = H2,
	covers(T1, T2).

% delete(Element, List1, Goal, List2) :- List2 contains all bindings
%	of Element to a member of List1 except thos that cause 
%	Goal to succeed
delete(X, L, Goal, New_L) :-
	(bagof(X, (member(X, L), not(Goal)), New_L);New_L = []).

Close Window