Technical Reports
Display by Author: A
| B
| C
| D
| E
| F
| G
| H
| I
| J
| K
| L
| M
| N
| O
| P
| Q
| R
| S
| T
| U
| V
| W
| X
| Y
| Z
TR-2004-10
Maximum Margin Algorithms with Boolean Kernels |
|
Authors: | Khardon, Roni; Servedio, Rocco |
Date: | November 2004 |
Pages: | 25 |
Download Formats: | [PDF] |
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 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 such maximum margin algorithms do not PAC learn t(n)-term DNF for any |
Faculty: for help posting a technical report please visit the User Guide.