Maximum Margin Algorithms with Boolean Kernels
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.
Cite
Text
Khardon and Servedio. "Maximum Margin Algorithms with Boolean Kernels." Journal of Machine Learning Research, 2005.Markdown
[Khardon and Servedio. "Maximum Margin Algorithms with Boolean Kernels." Journal of Machine Learning Research, 2005.](https://mlanthology.org/jmlr/2005/khardon2005jmlr-maximum/)BibTeX
@article{khardon2005jmlr-maximum,
title = {{Maximum Margin Algorithms with Boolean Kernels}},
author = {Khardon, Roni and Servedio, Rocco A.},
journal = {Journal of Machine Learning Research},
year = {2005},
pages = {1405-1429},
volume = {6},
url = {https://mlanthology.org/jmlr/2005/khardon2005jmlr-maximum/}
}