We introduce a formalism called graphical learning algorithms and use it to produce bounds on error deviance for unstable learning algorithms. This formalism suggests a flexible class of extensions of existing algorithms for which risk can be decomposed into algorithmic model risk plus estimation error in a way that enables bounds on estimation error and analysis of the algorithmic model risk. For example we obtain error deviance bounds for support vector machines (SVMs) with variable offset parameter and estimation error bounds for variations of SVM where the offset parameter is selected to minimize empirical risk. In addition we prove convergence to the Bayes error for variations of SVM that use a universal kernel and choose the regularization parameter to minimize empirical error. We provide experimental results that suggest that these variations may offer advantages over standard SVMs in both computation and generalization performance.
展开▼
