Philip M. Long* Computer Science Department Duke University P.O. Box 90129 Durham, North Carolina 27708 September 7, 1994
Abstract
We study the application of a linear programming algorithm due to Vaidya to the problem of learning halfspaces in Baum's nonmalicious distribution model. We prove that, in n dimensions, this algorithm learns up to ε accuracy with probability 1 — ε in For many combinations of the parameters, this compares favorably with the best known time. bound for the perceptron algorithm, which is O(n 2 /e 5). Keywords :  Computational learning theory, analysis of algorithms.
11
Introduction
In part due to their interpretation as artificial neurons [13, 15], a great deal has been written about the analysis of halfspaces in different computational models of learning. In this paper, we analyze the use of one of Vaidya's linear programming algorithms [18] to learn halfspaces in a variant of the PAC model [19] due to Baum [2], called the non-malicious distribution (NMD) model. In the NMD model, a halfspace H ⊆ R n is chosen randomly. There is a straightforward reduction from the problem of learning arbitrary halfspaces to learning homogeneous halfspaces, i.e., those that go through the origin (see, ee.g. [5]). We will therefore restrict our attention to homogeneous halfspaces. The halfspace H to be learned is then chosen by picking its normal vector uniformly from the unit sphere.  (If one works through the reduction from general halfspaces, this gives rise to the distribution on general halfspaces obtained by choosing (w 1 , ..., w n,b) uniformly from the unit ball in IRn+1, and setting the halfspace to be learned to be { x : w  x > b}.) It is further assumed that there is a probability distribution D over IRn that is unknown to the learner, but that the learner may (in unit time) sample points I , ..., Im independently at random according to D. Furthermore, the learner can find out whether each of these points is in the hidden halfspace H . The goal of the learner is to output an approximation fi of H . The accuracy of fi is measured by the probability that another point x drawn from D will be in the symmetric difference of H and H, i.e., that Â is “wrong” about x. The learner is given an input ε > 0, and is required to ensure that with probability at least 1 — c, with respect to the random choice of H and X 1 , ..., X m, the accuracy of H is better than ε. This model takes a Bayesian viewpoint, as has been done in [9, 14] and elsewhere. In Baum's original formulation, there were two separate parameters measuring the accuracy and the probability that the given accuracy was achieved. However, combining the two simplifies our bounds greatly, and it seems that in practice the two should at least be close.  Both being extremely sure of having a mediocre hypothesis, and being fairly sure of having an outstanding hypothesis seem unusual goals. 1 Baum [2] showed that the perceptron algorithm [15] accomplishes the above in O(n2/e5) time. In this paper, we show that an algorithm based on linear programming [18], 2 requires time. For many values of n and ε, this represents a substantial improvement.  For example, when n and 1/e are within a constant factor, the linear programming bound of this paper grows like O( n 3.38 log n ), which compares favorably with the O(n7) bound in this case for the perceptron algorithm. We make use of O ( n 2.38 ) time matrix multiplication [4] as a subroutine. Since the constants in the analysis of this matrix multiplication algorithm, as well as those for other o(n3) algorithms, are quite large, some claim that in practice the time required for multiplying n × n matrices grows like O(n³). However, replacing the n2.38 in our learning bounds with n³ only changes the n³.38 in our bound to an n 4 . An O(n 4 logn) bound would still be a significant improvement over O(n 7 ). The most natural application of linear programming techniques to the problem of learning halfs- paces is to draw a sample X 1 , …. I m, and then find a halfspace H for which each of I 1 , …. I m is in H  if and only if it is in the halfspace H to be learned, since this requirement amounts to m linear constraints on the normal vector of H [3]. However, in order to simply plug in to the time bounds for solving linear inequalities (with m inequalities and n unknowns), one must make assumptions on the precision of the Xj's.  (It is open whether there is a polynomial time algorithm for the unit-cost model for linear programming.  Such an algorithm would imply unit-cost polynomial time algorithms for learning in the NMD model, as well as Valiant's PAC model [19] (see [3]).) In the NMD model, we have found that a different approach doesn't require any assumptions on the precision of the Xj 's, and yields significantly improved time bounds.³ The iterations in Vaidya's linear programming algorithm can be viewed as what are called queries in another model of learning (due to Angluin [1]) often called the equivalence query model [12]. Implicit in Vaidya's analysis of his algorithm are bounds the number of iterations made by this algorithm in terms of the volume of the solution set of the system of linear inequalities [18]. These bounds can therefore also be viewed as equivalence query bounds.  Using conversions from this model to the PAC model [1, 10, 11], one can see that, for arbitrary ε > 0, if the volume of the set of normal vectors defining halfspaces that "agree" with the target halfspace H on I , ..., I m is not unreasonably small, then, with high probability, a randomized variant of Vaidya's algorithm quickly finds a setting of weights whose associated halfspace H satisfies that the fraction of elements of X 1 , … , X m  which  ie  in  the  symmetric  difference  of  Ĥ  and  H  is  at  most  ε/2.  Applying  results of Blumer, Ehrenfeucht, Haussler and Warmuth, for m = O((n/c) log(1/c)), this is good enough. Finally, we show that, with high probability, the volume of the set of normal vectors defining halfspaces which “agree” with the halfspace to be learned on x 1 , … , x m is not too small.
2
Preliminaries
Let IN denote the positive integers and R the reals. For sets S 1 and S 2 , let S 1 AS 2 denote the symmetric difference of S 1 and S 2 . We use the unit cost RAM model of computation (see, ee.g. [17]), where it is assumed that the standard operations on real numbers can be done in unit time. Choose X = Un Xn, and for all n, let C, be a class of subsets of X,,, and C = UnC,. Such a C is called a concept class.  An example of C ∈ C n is a pair ( x, xc ( x )) ∈ X n × {0,1}, where χc is C's characteristic function.  A subset C' of Xn is consistent with ( x, xc ( x )) if xc ( x ) = xc' ( x ). A sample is a finite sequence of examples.  We say C ′ ⊆ X n is consistent with a sample if it is consistent with each example in the sample. A  batch learning algorithm A takes as inputs an n ∈ IN, a desired accuracy ε > 0, and a sequence of elements of  X n × {0,1}.  A then outputs an algorithm for computing a function h :  X n → {0,1}. Usually, the algorithm can be understood from the description of h, and we will refer to the two interchangeably in the rest of this paper. We begin with the PAC model [19]. For a function φ : IR × IN → IN U {∞}, we say  A PAC-learns C in time φ if and only if there is a function ψ : R × IN → IN ∪{∞} such that for all input parameters n and ε, if m = ψ(1/ε, n):
Now we turn to the NMD model [2]. Suppose, for each n E IN, Pn is a probability distribution on C n, and P = {P n : n ≥ 1}. In this case, we say A PAC-learns C with respect to P in the NMD model in time φ if and only if there is a function ψ : R × IN → IN such that for all input parameters n and ε if m = ψ(1/ε, n): •  m ≤ φ(1/ε, n),
We will also discuss concept classes not indexed by n. It should be obvious how to adjust the above definitions for this case. Finally, we define the equivalence-query model [1].  In the equivalence-query model, when the algorithm is learning a class C, it sequentially produces queries which are (representations of) elements of C .  When the algorithm correctly guesses the function C to be learned, the learning process is over.  Otherwise, if the algorithm has queried Â, it receives x E ÂAC.  A learning algorithm for this model is called a query algorithm. For each n, let HALF, be the set of all homogeneous halfspaces in IRn, i.e. {{ x ∈ IRn : w  x ≥ 0} : w ∈ IRn}. Let HALF = UnHALFn
3
The analysis
We will make use of the following lemma, which is implicit in the analysis of Littlestone. Lemma 1 ([11]) Choose X,C ⊆ 2×. Suppose for any x ∈ X,C ∈ C, the question of whether x E C can be computed in β time. If there is a query algorithm B for C for which the time taken by B between queries is at most α, and the algorithm makes at most γ queries, then there is a PAC learning algorithm for C which outputs hypotheses from C whose time requirement is random examples The following notation will be useful. Fix some n. For each w ∈ R n , let H = { x ∈ R n : w  x ≥ 0}. For some finite set S ⊆ R n and some w ∈ R n , let H α , S = H α ∩ S . Also, define Es,w = {'i' E R'' : Hii,s = H ii,s, ||'i||2 < 1}. Informally, ES,w represents the set of all halfspaces that are indistinguishable from H w on the basis of S . Finally, for a finite set S ⊂ IRn, and v ≥ 0, let HALF S,v = {H w,S : W E IRn, volume(E S,w) ≥ v}. Now we are ready for another lemma, which is implicit in the analysis of Vaidya [18], if his linear programming algorithm is viewed as a query algorithm in the manner of Maass and Turán [12]. Lemma 2 ([18, 12]) For any finite S ⊂ Rn, there is a query algorithm MTV, such that, for all v > 0, MTV learns HALFS,v while using at most O(n2 · 38 ) time between queries, and makes at most
queries. We also make use of a special case of a result of Blumer, Ehrenfeucht, Haussler, and Warmuth. Lemma 3 ([3]) There is a constant c such that, for all c < 1/4, then if a (randomized) batch learning algorithm for learning HALFn draws
random examples, and with probability at least 1 — c/2 outputs a halfspace Ĥ such that the fraction of examples in the symmetric difference of H and the halfspace H to be learned is at most c/2, then H has accuracy better than ε with probability at least 1 — ε The following bound will also be useful. Lemma 4 (see [16, 6, 3]) Choose m, n ∈ IN, and S = { ī 1, ..., ī m} ∈ IRn. Then
Finally, we record a trivial lemma. let m be the least power of 2 not less thanֲךlog ļ , where c is as in Lemma 3 ; draw x 1, …, x m ∈ IR n independently at random from D ; S := {x, ..., xm} v := ξ ( ~ ) convert algorithm MTV (from Lemma 2) for learning HALFs,w into a PAC algorithm A' using the transformation of Lemma 1; simulate A ′ using the uniform distribution on ( x 1 , ..., x m ) to, with probability at least 1 — c/4, find a halfspace Â such that ¬|{j : ¯ zj E Â H}| ≤ c/2; output  Î Figure 1: Algorithm A from Theorem 6 Lemma 5  Choose a set X, and a probability distribution D over X.  Suppose E 1 ,…, E r form a partition for X, and for each x ∈ X, ix is the index of the element of the partition containing x Then for all c ≥ 0, We put these together to prove the main result of this paper. Theorem 6 If, for each integer n ≥ 2, P n is the distribution over HALF n obtained by choosing the normal vector w uniformly from the unit ball, then there is an algorithm A that PAC learns HALF with respect to P = {Pn} in the NMD model in time Proof : Choose n. Consider the algorithm A described in Figure 1. Fix S for the moment. Then since the volume of the unit ball is more than 2 n /n!,
Combining Lemma 4 and Lemma 5 with the above, we get
By the choice of v, Pr , w (volume( ES, , w ) ≤ v) ≤ c/4. By Fubini's Theorem (see [7, volume 2, page 120]), since this holds for arbitrary S , it holds for randomly chosen S as well. Thus, the probability with respect to the random choice of X 1 , ..., X m and of the target H that H N {X 1 , ..., X m} is not in HALF { f 1 ,.., f m},v is at most c/4. By construction, this implies that the probability that Â does not satisfy ∑ |{j : ī j ∈ Ĥ∆ H} | ≤ ϵ/2 is at most ϵ/2. Applying Lemma 3 completes the proof of the correctness of the algorithm. To analyze the time used by the algorithm, it is tempting to simply plug into the time bounds of Lemma 1. However, in that lemma, it is assumed that the algorithm may obtain random examples in unit time. However, when we simulate A ′ , we must generate random examples for it. Neverless, one may trivially sample from the uniform distribution on {1, ..., m} in O(log m) time, and therefore the total time spent sampling is at most by the sample size bound of Lemma 1, together with Lemma 2. Substituting and simplifying yields that this time is
To bound the time spent otherwise, we plug into Lemma 1 together with Lemma 2, getting
Expanding the definitions of v and m, simplifying, and observing that the resulting quantity dom- inates (1) completes the proof. □
4
Acknowledgements
We especially thank Nicolò Cesa-Bianchi, Yoav Freund, Hans Hagauer, David Haussler and Manfred Opper.