Mathematical Optimisation Techniques in Computer Vision and Machine Learning

摘要

This thesis explores applications of mathematical optimisation to problems arising in machine learning and computer vision, including kernel methods, probabilistic graphical models and several classical topics including smoothing, additive models and state estimation. Mathematical optimisation provides tools for dealing with practical modelling problems and their transformations, as well as supplying powerful algorithm design frameworks, such as operator splitting methods. Convexity in particular is the key property that influences both design and analysis of the proposed techniques. As a contribution to kernel methods, a new kernel suitable for object recognition tasks is introduced which generalises several existing approaches and provides a principled way to incorporate information about geometric structure of scenes. Conditions under which the new kernel can be efficiently computed are presented and performance is evaluated on a number of standard datasets. A uniform treatment of a broad class of estimation problems is also presented, focusing on the underlying optimisation problems and their convexity properties. Convex optimisation formulations for additive models, dynamic generalised linear models and related techniques are given with a number of extensions, including feature selection and outlier detection. A major benefit of the optimisation viewpoint is the ability to deploy powerful algorithm design frameworks. Two new algorithms are provided: an efficient first order algorithm for additive models and a distributed algorithm for state estimation. Beyond convex optimisation, a large number of problems in computer vision and machine learning can be naturally modelled in the framework of discrete Markov random fields. Once the structure of such a model and its parameters are chosen, it is often desirable to find a joint configuration of variables that has the highest probability, known as maximum a posteriori inference. The final contribution of this thesis is the extension of the spectral relaxation family of algorithms to deal with maximum a posteriori inference in discrete Markov random fields with higher order potentials. This is accomplished by relying on the so called tensor power method, which generalises the basic procedure for leading eigenvector computation from matrices to higher order tensors.