Logic, Trees and Kernels
Kernel based methods achieved much of their initial success on problems with real valued attributes. There are many problems with discrete attributes (including Boolean) and in this paper we present a number of results concerning the kernelisation of Boolean and discrete problems. We give results about the learnability and required complexity of logical formulae to solve classification problems. These results are obtained by linking propositional logic with kernel machines. In particular we show that decision trees and disjunctive normal forms (DNF) can be represented via of a special kernel, which connects the regularised risk to the margin of separation. Subsequently we derive a number of lower bounds on the required complexity of logical formulae using properties of algorithms for generation of linear machines machines. An interesting side eect of the development is a number of connections between machine learning algorithms that utilize discrete structures (such as a trees) and kernel machines. We also present some more general kernel constructions on discrete sets using the machinery of frames. These can be used to progressively penalize higher order interactions by explicitly constructing reproducing kernel Hilbert spaces, their associated kernels and the concomitant use of norm-based used regularization.