distribution of user ueries seen in the past. e assume that the distribution of ueries received b the s stem does not change significantl with time hence, the past distribution directs the s stem to learn relevant knowledge for the future ueries.

hile proving  ueries, the learning component accumulates information about the con trol values (average cost and number of solutions) of various literals. toring a separate value for each literal is not practical, for two reasons. The first is the large space re  uired b this approach. The second is the lack of generali ation the ordering algorithm is   uite likel to encounter literals which have not been seen before, and whose control values are unknown.   ecall that when we transformed    uation   into    uation  , we moved from control values of single literals to average control values over sets of literals. To obtain the precise averages for these sets, we still needed the control values of individual literals. ere, we take a di erent approach, that of learning and using control values for more general classes of literals. The estimated cost (nsols) value of a class can be defined as the average real cost (nsols) value of all e amples of this class that were proved in the past.

The more refined the classes, the smaller the variance of real control values inside each class, the more precise the cost and nsols estimations that the classes assign to their mem bers, and the better orderings we obtain. T
ne eas  wa  to define classes is b  modes or binding patterns ( ebra arren, 19 ll man Vardi, 19 )  for each argu ment we denote whether it is free or bound.  ore ample, for the predicate father the possible classes are father(free,free) , father(bound,free) , father(free,bound) and father(bound,bound). Now, if we receive a literal (fore ample, father(abraham,X)),
we can easil determine its binding pattern (in this case, father(bound,free)) and re trieve the control information stored for this class. f course, to find the binding pattern of a subgoal with a given binding set, we need a method to determine which variables are bound b the subgoals of the binding set. The same problem arose in computation
( ection . ). e shall discuss some practical wa s to solve this problem in  ection 7.1.

or the purpose of class definition we can also use regression trees at pe of decision tree that classifies to continuous numeric values and not to discrete classes ( reimanet al., 19 Quinlan, 19 ). Two separate regression trees can be stored for ever program predicate, one for its cost values, and one for the nsols. The tests in the tree nodes can be defined in various wa s. If we onl use the test "is argument bound?", then the classes of literals defined b  regression trees coincide with the classes defined b  binding patterns.   ut we can also appl more sophisticated tests, both s ntactic (e.g., "is the third argument a term with functor f ?") and semantic (e.g., "is the third argument female?"), which leads to more refined classes and better estimations.    possible regression tree for estimating the of number of solutions for predicate father is shown in   igure 1  .

emantic tests about the arguments re  uire logic inference (in the e  ample of   igure 1 invoking the predicate female on the first argument of the literal). Therefore, the   must be as e cient as possible. therwise the retrieval of control values will take too much time. The problem of e  cient learning of control values is further considered elsewhere ( edeniov arkovitch, 199 a).

everal researchers applied machine learning techni ues for accelerating logic inference e ong one , 19 angle , 19 arkovitch cott, 199 into n,
( ohen, 199 19 itc hell, Kelle r, Kedar abelli, 19 one elle, 199 rieditis ostow, 19 7). ome of these works used e planation based learning or generali ed caching tech