Frédéric Koriche

Online Rule Learning via Weighted Model Counting

Online multiplicative weight-update learning algorithms, such as Winnow, have proven to behave remarkably for learning simple disjunctions with few relevant attributes. The purpose of this paper is to extend the Winnow algorithm to more expressive target concepts characterized by DNF formulas with few relevant rules. For such problems, the convergence of Winnow is still fast, since the number of mistakes increases only linearly with the number of attributes. Yet, the learner is confronted with an important computational barrier: during any prediction, it must evaluate a weighted sum of an exponential number of rules. To circumvent this issue, we convert the prediction problem into a Weighted Model Counting problem. The resulting algorithm, SharpNow, is an exact simulation of Winnow equipped with backtracking, caching, and decomposition techniques. Experiments on static and drifting problems demonstrate the performance of the algorithm in terms of accuracy and speed.

INTRODUCTION

A recurrent theme in Machine Learning is the development of online mistake-driven learning algorithms [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF]. Such algorithms are "anytime learners" that can be interrupted at each instant to provide a prediction whose correctness is related to the number of mistakes that have been made so far. Basically, the underlying model takes place in a sequence of trials. At any time step, the learner is presented an observation and it is asked to predict its associated class. If the prediction is incorrect, we charge it one mistake.

In a landmark paper, Littlestone [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF] introduced the Winnow algorithm, which has rapidly become the blueprint of many efficient online learners. Winnow resembles the Perceptron algorithm in its simplicity, but uses multiplicative, rather than additive, weight updates on input features. Consequently, when the target concept is a k out of n variable disjunction, the number of mistakes grows as k log n instead of kn. The fact that the dependence on n is reduced to logarithmic, rather than linear, makes this algorithm applicable even if the number of features is enormous.

This remarkable property opens the door to learning problems characterized by high-dimensional feature spaces. One of them concerns the well-known problem of rule learning which consists in identifying, from a collection of examples, a small set of rules that explains all the positive examples and none of the negative ones [START_REF] Fürnkranz | Separate-and-conquer rule learning[END_REF]. In the paradigm of concept learning, any rule theory can be viewed as a DNF formula, that is, a disjunction of conjunctive features. Based on this notion, Winnow can naturally be extended to rule theories by projecting the data into an higher-dimensional feature space in which any conjunctive feature is viewed as a basic attribute. The enhanced algorithm inherits of an increased expressiveness while preserving a strong learning power. Indeed, if the observed examples are vectors of n attributes taking values over a domain of size d then, providing 1 LIRMM, Université Monptellier 2, France, Frederic.Koriche@lirmm.fr that the number of all conjunctive features is bounded by (d + 1) n , the performance of Winnow degrades only linearly with the input dimension. In fact, for any target concept, the number of mistakes grows essentially as kn log(d + 1), where k is the minimum number of rules needed to represent the concept into a rule theory.

In its primal form, Winnow maintains a vector that assigns a weight to each distinct feature. For rule learning, such an implementation is computationally prohibitive, since the number of possible rules grows exponentially with the input dimension. Specifically, during any prediction, the learner is confronted with the problem of computing the weighted sum of an exponential number of features.

Kernel methods have emerged as a standard approach for solving counting problems that arise from high-dimensional feature spaces. The underlying idea is to start from the dual form of the learning algorithm and to use a kernel function that simulates the target feature space while working with original input data. Specifically, in the setting of Boolean DNF formulas, efficient kernel functions have been obtained for the Perceptron algorithm and its maximum margin variants [START_REF] Sadohara | Learning of boolean functions using support vector machines[END_REF]. Unfortunately, it seems impossible to find an analogous result for the Winnow algorithm. Indeed, as observed by Khardon et al. [START_REF] Khardon | Efficiency versus convergence of boolean kernels for on-line learning algorithms[END_REF], the Kernel Winnow Prediction problem is #P-hard, even for the restricted class of monotone DNF formulas.

Such a computational barrier does not imply that, in practice, the sole option for the learner is a brute force enumeration of its feature space. To this very point, in the AI literature, a great deal of attention has been devoted to a related problem, referred to as Weighted Model Counting [START_REF] Chavira | On probabilistic inference by weighted model counting[END_REF][START_REF] Domshlak | Probabilistic planning via heuristic forward search and weighted model counting[END_REF][START_REF] Sang | Performing Bayesian inference by weighted model counting[END_REF]. The problem is to evaluate the sum of weights of all the assignments satisfying a CNF formula. The basic building block for most model counting algorithms is the Davis-Putnam (DP) procedure that performs a backtracking search in the space of candidate models [START_REF] Birnbaum | The good old Davis-Putnam procedure helps counting models[END_REF]. Based on this procedure, recent programs such as Cachet [START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF] and SharpSat [START_REF] Thurley | sharpSat -counting models with advanced component caching and implicit BCP[END_REF] can handle large instances by combining formula caching and decomposition into connected components.

The power of these techniques raises the natural question of whether the Kernel Winnow Prediction problem can be solved in practice by translation to Weighted Model Counting. This paper provides initial evidence that the answer is affirmative: such a translation can be indeed effective for learning, with fast convergence and speed, "sparse" target concepts involving a small number of relevant rules. The resulting algorithm, called SharpNow, is an exact simulation of kernel Winnow, equipped with backtracking, caching, and decomposition techniques. For sparse target concepts, it can efficiently handle large spaces of conjunctive features with an accuracy superior to that of kernel Perceptron-like algorithms.

The background about online rule learning can be found in section 2. The translation method and the SharpNow algorithm are presented in section 3. Experiments on both static and drifting problems are reported in section 4. Finally, section 5 concludes the paper with a discussion about related work and perspectives of further research.

In the online learning model, the algorithm is presented with a series of examples {xt, yt} labeled by a target concept. At each time step t, the algorithm first outputs a class prediction ŷt for the observation xt, and then updates its hypothesis based on the true class yt. We adopt the convention that yt ∈ {-1, +1}.

The learners of particular interest in this study are the Perceptron [START_REF] Rosenblatt | The Perceptron: a probabilistic model for information storage and organization in the brain[END_REF] and Winnow [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF] algorithms applied to rule theories.

Rule Theories

Let {x1, • • • , xn} be a set of attributes taking values in a discrete domain of size d. For convenience, we assume a standard way of naming values, as a list of natural numbers. A concept is a function f from d n to {-1, +1}, and an example is a vector x in d n . We say that a series of examples {xt, yt} is labeled by a target concept f if f (xt) = yt for each index t.

An atom is an expression xi = j, also denoted x j i , where xi is an attribute and j a value. A conjunctive feature, or rule, is a conjunction of atoms, and a rule theory is a set of rules. A rule r covers an example x if for all atoms x j i in r, the value of xi in x is j. A rule theory R covers an example x if at least one rule in R covers x. For instance, the following expression is a theory with three rules

   sky = sunny ∧ humidity = normal sky = cloudy ∧ temp = mild sky = rain ∧ wind = weak
The example (sunny, normal , mild , weak ) is classified as positive by this theory, because it is covered by the first rule.

It is well-known that any concept can be represented by an equivalent rule theory. The rule size of a concept f , denoted |f |, is the minimal number of rules needed to represent f as a rule theory.

The feature space R n,d of all rules generated from n attributes taking values over a domain of size d is represented by an indexed set {r1, • • • , rN }, where N = (d + 1) n . Given an example x, the feature expansion of x onto R n,d is a vector φ(x) in {0, 1} N where φi(x) = 1 if and only if ri covers x.

Perceptron

For sake of clarity, we examine the zero-threshold version of the Perceptron algorithm. Throughout its execution, it maintains a vector wt in R N which is initialized to w0 = 0. Upon receiving an example xt, the algorithm predicts using the rule

ŷt = sign(wt • φ(xt)) (1)
No change is made to wt if the prediction is correct. In case of mistake, the algorithm uses the additive rule

wt+1 = wt + ytφ(xt) (2)
For rule theories, implementing the Perceptron in its the primal form is computationally infeasible since we would need to maintain a weight vector of (d+1) n size. Yet, it is well-known that the dual form of the algorithm is a linear combination of inner products formed by the current observation xt and the previous examples {(xs, ys)} on which mistakes where made. In the setting of R n,d , each inner product φ(xs) • φ(xt) can be simulated by the kernel function

K(xs, xt) = 2 |{i:x s,i =x t,i }|
In particular, the kernel obtained by Sadohara [START_REF] Sadohara | Learning of boolean functions using support vector machines[END_REF] can be derived from d = 2. Based on the so-called kernel trick, the prediction rule 1 can be replaced with

ŷt = sign m s=1 ysK(xs, xt) (3)
Each trial of the kernel Perceptron algorithm can thus be executed in polynomial time. Unfortunately, the algorithm can provably require many updates even for very simple rule theories [START_REF] Khardon | Efficiency versus convergence of boolean kernels for on-line learning algorithms[END_REF].

Theorem 1. There exists a target concept of polynomial rule size and a sequence of examples labeled by it which causes the kernel Perceptron algorithm to make 2 Ω(n) mistakes.

Importantly, this result still holds for most Perceptron-like algorithms, including the version parameterized with a learning rate and a nonzero threshold, and the recent maximum margin variants [START_REF] Khardon | Maximum margin algorithms with boolean kernels[END_REF].

Winnow

The algorithm has a very similar structure. It takes as input two parameters: a learning rate η and a threshold θ, and maintains a vector wt which is initialized to w0 = 1. Upon receiving an example xt, the algorithm predicts according to the rule

ŷt = sign(wt • φ(xt) -θ) (4)
Again no change is made to wt if the prediction is correct. In case of mistake, the hypothesis is updated with a multiplicative rule

wt+1 = wt exp(ηytφ(xt)) (5)
According to these specifications, the following result can be deduced by a simple adaptation of Winnow's amortized analysis [START_REF] Auer | Tracking the best disjunction[END_REF]. Thus, the Winnow algorithm has a polynomial mistake bound for learning polynomial-size rule theories. However, the key difficulty is to provide a computationally efficient simulation of the algorithm. Specifically, the Kernel Winnow Prediction problem is to infer the sign of wt • φ(xt) -θ for the last example of a given sequence {(xt, yt)} of examples labeled by a target polynomial-size rule theory, after applying the prediction rule 4 and the update rule 5 on the weight vector wt for the previous examples. As shown in [START_REF] Khardon | Efficiency versus convergence of boolean kernels for on-line learning algorithms[END_REF] this problem is #P-hard, which implies that, unless #P = P, there is no general construction that will run Winnow using kernel functions.

In a nutshell, the most important message to be gleaned from online rule learning is that both additive and multiplicative update algorithms are, in theory, limited by either computational efficiency or convergence reasons. On the one hand, even if kernel Perceptron-like algorithms may be executed efficiently, they can provably require an exponential number of mistakes and, on the other hand, even if the kernel Winnow algorithm has a polynomial mistake bound, it seems impossible to simulate its execution in polynomial time.

Despite the undoubtable importance of the aforementioned results, it remains to be seen whether, in practice, the execution of kernel Winnow can be simulated using efficient techniques that have been developed for solving real-world #P problems. The key motivation of this paper is to convert the Kernel Winnow Prediction problem into a Weighted Model Counting problem, for which general and efficient model counting techniques can be applied.

The Translation Method

Informally, any instance of the Weighted Model Counting problem consists in a set of weighted clauses; the task is to evaluate the sum of weights of assignments satisfying these clauses [START_REF] Sang | Performing Bayesian inference by weighted model counting[END_REF]. The intuitive idea behind the translation method is just to ascribe a weighted clause to each labeled example that has led to a mistake.

To this end, we need to introduce additional definitions. Consider again a set {x1, • • • , xn} of attributes taking values over a discrete domain of size d. In the following, any rule defined over this vocabulary is viewed as an assignment, that is a set of atoms or, equivalently, a map that assigns to each atom a value in {0, 1}. A literal is an atom x j i or its negation ¬x j i and a clause is a disjunction of literals. Given a rule r and a literal x j i (resp. ¬x j i ), we say that r satisfies x j i (resp.

¬x j i ), if x j i ∈ r (resp. x j i ∈ r).
Given a rule r and a clause c, we say that r satisfies c if r satisfies at least one literal occurring in c. Based on these notions, the feature expansion of a clause c under R n,d is a map φ(c) in [0, 1] N where φi(c) = 1 if and only if ri satisfies c.

A weighted clause is an expression of the form (c, w) where c is a clause and w is a value in R. Intuitively, w reflects how strong a constraint it is: the higher the weight, the greater the difference in likelihood between a rule that satisfies the constraint and one that does not. In this setting, any "unweighted" clause c is treated as an abbreviation of (c, 0): it denotes a hard constraint that restricts the space of possible rules. A weighted knowledge base KB is a finite set of weighted clauses. The weight of KB , denoted KB , is

KB = N i=1 (c,w)∈KB w 1-φ i (c) (6)
As usual, we take the convention that 0 0 = 1 and 0 z = 0 for any real number z > 0. Thus, the weight of the knowledge base KB is just the sum of weights of the assignments that are models of KB .

We are now in position to present the translation method. The learning algorithm starts with the knowledge base KB 0 = ∅. On seeing an example xt, the algorithm predicts according to

ŷt = sign KB t ∪ {¬x j i : xt,i = j} -θ (7)
Recall that in the above expression, each unary clause ¬x j i is treated as an abbreviation of (¬x j i , 0). In case of mistake, KB t is simply expanded with a weighted clause that conveys, in a concise form, the information gathered from xt and yt. In formal terms

KB t+1 = KB t ∪ {x j i : xt,i = j}, e ηy t (8)
For instance, suppose that our learner makes a mistake on the positive example (sunny, normal , mild , weak ). Then its knowledge base is expanded with the weighted clause (c, e η ), where c is the disjunction of all atoms sky = cloudy, sky = rain, . . . that are false in the example. In the next prediction, the weight of any rule that violates c will be multiplied by e η .

The SharpNow Algorithm

In the spirit of model counting algorithms such as Cachet [START_REF] Sang | Combining component caching and clause learning for effective model counting[END_REF] and SharpSat [START_REF] Thurley | sharpSat -counting models with advanced component caching and implicit BCP[END_REF], we begin to develop a procedure for evaluating the weight of knowledge base that combines backtracking search with formula caching and decomposition into connected components.

The procedure, called WMC, takes as input a weighted knowledge base KB and a set of atoms A. Basically, the procedure performs a depth-first search in the tree of partial assignments generated from A. Notably, a leaf of the tree is reached whenever every clause occurring in KB is empty. In this case, the resulting weight can be evaluated by simply taking the product of weights of these clauses. Following [START_REF] Bayardo | Counting models using connected components[END_REF], the depth-first search procedure is enhanced by using decomposition into connected components. Namely, by identifying in linear time the connected components in the constraint graph of KB , the resulting weight can be determined by multiplying together the weight of each connected component. Finally, the WMC procedure is equipped with a caching technique that prevents it from recomputing the same component. Because the length of weighted clauses is in O(nd), we employ the hybrid coding scheme suggested in [START_REF] Thurley | sharpSat -counting models with advanced component caching and implicit BCP[END_REF] that concisely encodes a set of clauses KB as a vector of indices. Notice that the technique of component caching is particularly relevant in the setting of online learning when the algorithm is susceptible to recompute many identical subtrees from one prediction to the next. With these notions in hand, we can now present the algorithm SharpNow. As specified by the translation method, the algorithm starts with an empty knowledge base. During any trial, SharpNow predicts according to rule 7 and updates its knowledge base in light of rule 8. The prediction rule is implemented using the WMC procedure as specified in proposition 3. The following result claims that Sharp-Now and Winnow make exactly the same predictions on the same series of labeled examples. As an immediate corollary, the mistake bound of SharpNow is the same as the one derived for the original algorithm. This implies, among others, that the size of the knowledge base maintained by the learner is polynomial in the input dimension.

wt • φ(xt) = KB t ∪ {¬x j i : xt,i = j} (9)
First of all, consider an assignment r which is not an element of R n,d . Then, for any possible example xt, r violates at least one clause in the set {¬x j i : xt,i = j}. It follows that r is not a model of KB t ∪ {¬x j i : xt,i = j}. Thus, to prove 9, we only need to consider assignments that are elements of R n,d . So, let ri be a rule in R n,d , wt,i the weight of ri maintained by wt, and w KB t,i the weight of ri according to KB t, i.e. w KB t,i = {w : (c, w) ∈ KB t, ri ∩ c = ∅}. We shall prove by induction on the number of trials that wt,i = w KB t,i . Consider the first trial. We have = 1 and since KB 0 = ∅, we have w KB 0,i = 1. Now consider an arbitrary trial and assume by induction hypothesis that wt-1,i = w KB t-1,i at the beginning of the trial. If no mistake has occurred during the trial, then wt,i = w KB t,i trivially holds. Thus, suppose that a mistake has occurred. If φi(xt) = 1, then we know that ri violates the clause {x j i : xt,i = j}. So w KB t,i = e y t η w KB t-1,i = e y t η wt-1,i = wt,i. As a similar strategy applies when φi(xt) = 0. By applying the fact that wt,i = w KB t,i to each rule in R n,d , we therefore obtain the desired result.

EXPERIMENTS

To provide empirical support for SharpNow, we evaluated it on several learning problems where the target concept is characterized by a small set of rules. A comparison with other standard online mistakedriven algorithms relies on their ability to achieve fast convergence to the optimal hyperplane in the conjunctive feature space R n,d .

The experiments were conducted on a 3.00 GHz Intel Xeon 5160 with 4 GB RAM running Windows XP. All algorithms were written in C++. Notably, the SharpNow algorithm was run using a cache of size 1 GB, and a learning rate η = 1.278 for which the term η 2 sinh η in theorem 2 is minimized.

Static Problems

We begin with experiments on several UCI datasets, with no (known) concept drift, aiming at evaluating the performance of SharpNow relative to the kernel Perceptron and kernel Passive-Aggressive (PA) algorithms. Basically, the PA algorithm [START_REF] Crammer | Online passive-aggressive algorithms[END_REF] is a maximum margin variant of Perceptron that forces the learner to achieve a unit margin on the most recent example while remaining as close as possible to the previous hypothesis. Both algorithms were implemented using the kernel prediction rule 3, and the PA algorithm was run with the update rule (PA-I) and a slack variable C fixed to 100. Experiments were conducted with the "tic-tac-toe" dataset (958 instances, 9 attributes, 27 atoms), the "kr-vs-kp" dataset (3196 instances, 36 attributes, 73 atoms), and the "poker-hand" dataset (1,025,010 instances, 10 attributes, 85 atoms). The last dataset was divided into 10 binary problems. Each problem consists in finding a particular class of poker hand, where all examples of this class are considered as positive, and all other examples are negative. Each card is described using two attributes (suit and rank); to compare pairs of cards, we introduced four additional binary attributes, same-suit, same-rank, before-rank and next-rank. The total number of atoms is thus 165. For all experiments, the accuracy results have been obtained using only one epoch of the training set. For the tic-tac-toe and kr-vs-kp datasets, we employed a standard 10-fold cross-validation. For the poker-hand dataset, we used the training set of 25,010 instances and a subset of 5,000 test instances in the pool of 1, 000, 000 test instances. The test set was filled with up to 2,500 positives and the rest as negatives, all examples been chosen at random in the pool.

Results are reported in Table 1. In term of accuracy, the performance of SharpNow is remarkable. Notably, for many problems in the poker hand dataset, we observed that the algorithm converges using less than 5,000 trials while kernel Perceptron and the kernel Passive-Aggressive show some difficulty in approaching the target concept. The running time is measured in milliseconds per trial. As expected, SharpNow is the slowest because it must solve a Weighted Model Counting problem during each prediction. Yet, with a speed of several milliseconds per trial, SharpNow can be used in real-time for medium-size datasets involving a sparse target function.

Drifting Problems

A natural application for online learning algorithms is to track concepts that are allowed to change over time. In this setting, we analyze the performance of SharpNow relative to the kernel Perceptron and kernel Forgetron algorithms. The Forgetron [START_REF] Dekel | The Forgetron: A kernelbased Perceptron on a fixed budget[END_REF] is a shifting variant of Perceptron that gradually forgets the oldest supports in the set of examples on which mistakes were made; to this end, it uses a decaying rule that diminishes the contribution of old supports and a fixed memory budget B that removes the oldest support.

We conducted experiments with a variant of the Stagger Concepts, a standard benchmark for drifting problems. Each example is a scene involving objects o1, • • • , o k with attributes color (oi) ∈ {green, blue, red }, shape(oi) ∈ {triangle, circle, square}, and size(oi) ∈ {small , medium, large}. In the original problem [START_REF] Schlimmer | Beyond incremental processing: Tracking concept drift[END_REF], each scene involves only one object. To analyze the performance of The accuracy results obtained with k = 5 and k = 20 are reported in Figures 1 and2. We observe that SharpNow needs some time to readjust its weights but always converges toward the target concepts; by contrast the kernel Perceptron and kernel Forgetron algorithms show some difficulty in approaching the first and the last concepts. This phenomenon increases with k, revealing that SharpNow is quite robust to irrelevant features. The running time of SharpNow ranges from less than 1 1000 seconds per trial with k ≤ 5 to 1 4 seconds per trial for k = 20 (180 atoms and 10 28 conjunctive features).

CONCLUSIONS

We presented SharpNow, an online rule learning algorithm that aims at combining a multiplicative weight update strategy and a weighted model counting method. As an exact simulation of kernel Winnow, the mistake bound of SharpNow is linear in the input dimension. Preliminary experiments on static and drifting problems tend to confirm that SharpNow is particularly efficient for learning small rule theories in presence of many irrelevant conjunctive features.

The problem of extending multiplicative weight-update algorithms to expressive concept classes has been a subject of ongoing research in Machine Learning. Yet, to the best of our knowledge, very few investigations have attempted to handle rule theories. A notable exception is the work by Chawla et. al [START_REF] Chawla | On approximating weighted sums with exponentially many terms[END_REF] who suggested to explore Markov Chain Monte Carlo (MCMC) methods for approximating the Kernel Winnow Prediction problem. The main difference with our study is that MCMC methods cannot guarantee an exact simulation of kernel Winnow. Moreover, the running time of their resulting algorithm remains quite slow, taking days to learn a DNF formula over 20 variables. By contrast, the weighted model counting technique takes several milliseconds per trial for similar problems.

Several avenues of research naturally emerge from this study. One of them concerns the analysis of SharpNow under noisy environments using, for example, a discount factor suggested in kernel functions. An orthogonal direction is to extend our method to multi-class environments by simulating multiplicative voting algorithms [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF].

Theorem 2 .

 2 Let θ = η 2 sinh η (d + 1) n . Then, for any target concept f , the number m of mistakes made by the Winnow algorithm over any sequence of examples labeled by f satisfies m ≤ e η + 1 η [1 + |f |n log(d + 1)]

Proposition 3 .

 3 Let KB be a weighted knowledge base, xt an example, and At the set of all atoms that are true in xt. Let A be the set of atoms in At that occur in KB , and A = At -A. Then KB ∪ {¬x j i : xt,i = j} = 2 |A| * WMC(KB , A) Proof. Based on the completeness of the DP backtracking search procedure for model counting [3], we know that WMC(KB , A) = r⊆A {w : (c, w) ∈ KB , r ∩ c = ∅} Let KB = KB ∪ {¬x j i : xt,i = j}. From definition 6, we can infer KB = r⊆A t {w : (c, w) ∈ KB , r ∩ c = ∅} = 2 |A| WMC(KB , A)

Theorem 4 .

 4 SharpNow is an exact simulation of kernel WinnowProof. We consider that Winnow and SharpNow are run with the same parameters η and θ, and the same series of labeled examples {(xt, yt)}. A sufficient condition for establishing the result is to prove that the following equation holds:

Figure 1 .

 1 Figure 1. Stagger Concepts with 5 objets

Figure 2 .

 2 Figure 2. Stagger Concepts with 20 objets

  Algorithm 1: WMC(KB , A) Input: a weighted knowledge base KB and a set of atoms A Output: the sum of weights of all subsets of A according to KB if INCACHE(KB ) then return GETFROMCACHE(KB ) if ISLEAF(KB ) then return 2 |A| * (c,w)∈KB w weight ← 1 for each connected component KB i in KB do let Ai be the set of atoms occurring in KB i choose an atom a in Ai KB i,1 ← {(c -{a}, w) : (c, w) ∈ KB i, a ∈ c} weight 1 ← WMC(KB i,1, Ai -{a}) KB i,2 ← {(c -{¬a}, w) : (c, w) ∈ KB i, ¬a ∈ c} weight 2 ← WMC(KB i,2, Ai -{a}) SETTOCACHE(KB i, weight 1 + weight 2 ) weight ← weight * (weight 1 + weight 2 ) return weight

Table 1 .

 1 Results for the tic-tac-toe, kr-vs-kp, and poker hand datasets

	data	Perceptron	PA	SharpNow
	set	error	ms	error	ms error	ms
	tic-tac-toe	0.058 0.02	0.073 0.02 0.009	0.21
	kr-vs-kp	0.042 0.09	0.073 0.16 0.028	713
	nothing	0.032 0.89	0.020 0.70 0.021	16.5
	one pair	0.116 2.01	0.113 2.09 0	2.44
	two pairs	0.026 0.78	0.042 0.53 0	5.17
	three of a kind	0.004 0.12	0.007 0.22 0	4.41
	straight	0.167 0.87	0.158 0.70 0.107	119
	flush	0.012 0.06	0.011 0.03 0.010	0.03
	full house	0.070 0.14	0.069 0.13 0	5.84
	four of a kind	0.019 0.03	0.029 0.03 0	2.34
	straight flush	0.010 0.03	0.009 0.01 0.007	0.01
	royal flush	0.003 0.01	0.003 0.01 0.003	0.01