Support vector machine classifiers with uncertain knowledge sets via robust optimization

Abstract

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.

Keywords:

• robust optimization
• robust Farkas' lemma
• support vector machines
• uncertain knowledge sets
• quadratic optimization
• duality

AMS Subject Classifications:

• 65K10
• 90C25
• 90M45

Acknowledgements

This research was partially supported by a grant from the Australian Research Council.