## Maximum Margin Algorithms with Boolean Kernels

** Roni Khardon, Rocco A. Servedio**; 6(Sep):1405--1429, 2005.

### Abstract

Recent work has introduced Boolean kernels with which one can learn
linear threshold functions over a feature space containing all
conjunctions of length up to *k* (for any 1 ≤
*k* ≤ *n*) over the original *n* Boolean
features in the input space. This motivates the question of whether
maximum margin algorithms such as Support Vector Machines can learn
Disjunctive Normal Form expressions in the Probably Approximately
Correct (PAC) learning model by using this kernel. We study this
question, as well as a variant in which structural risk minimization
(SRM) is performed where the class hierarchy is taken over the length
of conjunctions.

We show that maximum margin algorithms using the Boolean kernels do
not PAC learn *t*(*n*)-term DNF for any *t*(*n*)
= ω(1), even when used with such a SRM scheme. We also
consider PAC learning under the uniform distribution and show that if
the kernel uses conjunctions of length
˜ω(√*n*) then the maximum margin hypothesis
will fail on the uniform distribution as well. Our results concretely
illustrate that margin based algorithms may overfit when learning
simple target functions with natural kernels.

[abs][pdf]