Author name cluster

M.K. Warmuth

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AIJ Journal 1997 Journal Article

The perceptron algorithm versus winnow: linear versus logarithmic mistake bounds when few input variables are relevant

J. Kivinen
M.K. Warmuth
P. Auer

We give an adversary strategy that forces the Perceptron algorithm to make Ω(kN) mistakes in learning monotone disjunctions over N variables with at most k literals. In contrast, Littlestone's algorithm Winnow makes at most O(k log N) mistakes for the same problem. Both algorithms use thresholded linear functions as their hypotheses. However, Winnow does multiplicative updates to its weight vector instead of the additive updates of the Perceptron algorithm. In general, we call an algorithm additive if its weight vector is always a sum of a fixed initial weight vector and some linear combination of already seen instances. Thus, the Perceptron algorithm is an example of an additive algorithm. We show that an adversary can force any additive algorithm to make (N + k −1) 2 mistakes in learning a monotone disjunction of at most k literals. Simple experiments show that for k ⪡ N, Winnow clearly outperforms the Perceptron algorithm also on nonadversarial random data.

Details DOI

I&C Journal 1994 Journal Article

Composite Geometric Concepts and Polynomial Predictability

P.M. Long
M.K. Warmuth

We study the predictability of geometric concepts, in particular those defined by boolean combinations of simple geometric objects. First, we give a negative results, showing that the problem of predicting the class of convex polytopes encoded by listing their vertices is prediction complete for P. Thus, an efficient solution to this prediction problem implies the existence of efficient solutions to all prediction problems whose associated evaluation problems are in P. Assuming the existence of a one-way function that is hard on iterates, there are such prediction problems which do not admit efficient solutions. Thus we show under minimal cryptographic assumptions that the class of convex polytopes encoded by listing their vertices is not predictable. As a side effect, we show that determining membership in the convex hull of a given set of points is complete for P with respect to log space reductions. Next, we establish the predictability of the class consisting of unions of a fixed number of flats by reducing its prediction problem to that of the class of flats, which has previously been shown to be predictable. Finally, we give an Occam algorithm for predicting fixed finite unions of boxes. Both constructive results for flats and boxes hold if the dimension is variable.

Details DOI

I&C Journal 1994 Journal Article

Predicting {0, 1}-Functions on Randomly Drawn Points

D. Haussler
N. Littlestone
M.K. Warmuth

We consider the problem of predicting {0, 1}-valued functions on R n and smaller domains, based on their values on randomly drawn points. Our model is related to Valiant′s PAC learning model, but does not require the hypotheses used for prediction to be represented in any specified form. In our main result we show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. This result is based on new combinatorial results about classes of functions of finite VC dimension. We also discuss more computationally efficient algorithms for predicting indicator functions of axis-parallel rectangles, more general intersection closed concept classes, and halfspaces in R n. These are also optimal to within a constant factor. Finally, we compare the general performance of prediction strategies derived by our method to that of those derived from methods in PAC learning theory.

Details DOI

I&C Journal 1994 Journal Article

The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case

H.L. Bodlaender
S. Moran
M.K. Warmuth

In Moran and Warmuth (1993, SIAM. J. Comput. 22, No. 2, 379-399), it was shown that computing any non-constant function on a ring of n of processors requires Ω(n log) bits and this bound is tight. This model assumed that all the processors in the ring are identical (anonymous), i. e. , all processors run the same program and the only parameter of the program is the input to the processor. In a relaxed model the anonymity is broken by providing each processor with a distinct identity which becomes a second parameter of the program that is executed by all processors. If the set of possible identities grows doubly exponentially in n, then by a reduction to the anonymous case one can show that the lower bound holds as well. In this paper we show that the lower bound of Ω(n log n) bits for computing any non-constant function holds even if the set of possible identities is "very small, " that is, of sizer n 1 + ϵ, for any positive ϵ.

Details DOI

I&C Journal 1994 Journal Article

The Weighted Majority Algorithm

N. Littlestone
M.K. Warmuth

We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes. We are interested in the case where the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. We call this method the Weighted Majority Algorithm. We show that this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will make at most c(log | A | + m) mistakes on that sequence, where c is fixed constant.

Details DOI