Dong, Minghzi;
(2019)
Metric Learning with Lipschitz Continuous Functions.
Doctoral thesis (Ph.D), UCL (University College London).

Text
Dong_M_Thesis_revised.pdf Download (2MB)  Preview 
Abstract
Classification is a fundamental problem in the field of statistical machine learning. In classification, issues of nonlinear separability and multimodality are frequently encountered even in relatively small data sets. Distancebased classifiers, such as the nearest neighbour (NN) classifier which classifies a new instance by computing distances between this instance and the training instances, have been found useful to deal with nonlinear separability and multimodality. However, the performance of distancebased classifiers heavily depends on the underlying distance metric, so it is valuable to study metric learning, which enables the algorithms to automatically learn a suitable metric from available data. In this thesis, I discuss the topic of metric learning with Lipschitz continuous functions. The classifiers are restricted to have certain Lipschitz continuous properties, so that the performance guarantee of classifiers, which could be described by probably approximately correct (PAC) learning bounds, would be obtained. In Chapter 2, I propose a framework in which the metric would be learned with the criterion of large margin ratio. Both interclass margin and intraclass dispersion are considered in the criterion, so as to enhance the generalisation ability of classifiers. Some wellknown metric learning algorithms can be shown as special cases of the proposed framework. In Chapter 3, I suggest that multiple local metrics would be learned to deal with multimodality problems. I define an intuitive distance with local metrics and influential regions, and subsequently propose a novel local metric learning method for distancebased classification. The key intuition is to partition the metric space into influential regions and a background region, and then regulate the effectiveness of each local metric to be within the related influential regions. In Chapter 4, metric learning with instance extraction (MLIE) is discussed. A big drawback of the NN classifier is that it needs to store all training instances, hence it suffers from problems of storage and computation. Therefore, I propose an algorithm to extract a small number of useful instances, which would reduce the costs of storage as well as the computation costs during the test stage. Furthermore, the proposed instance extraction method could be understood as an elegant way to do local linear classification, i.e. simultaneously learn the positions of local areas and the linear classifiers inside the local areas. In Chapter 5, based on an algorithmdependent PAC bound, another algorithm of MLIE is proposed. Besides the Lipschitz continuous requirement with respect to the parameter, the Lipschitz continuous requirement with respect to the gradient of parameter will also be considered. Therefore, smooth classifiers and smooth loss functions are proposed in this chapter. The classifiers proposed in Chapter 2 and Chapter 3 have bounded values of lip(h x) with a PAC bound, where lip(h x) denotes the Lipschitz constant of the function with respect to the input space X. The classifiers proposed in Chapter 4 enjoys the bounded value of lip(h ) with a tighter PAC bound, where lip(h ) denotes the Lipschitz constant of the function with respect to the input space . In Chapter 5, to consider the property of the optimisation algorithm simultaneously, an algorithmdependent PAC bound based on Lipschitz smoothness is derived.
Type:  Thesis (Doctoral) 

Qualification:  Ph.D 
Title:  Metric Learning with Lipschitz Continuous Functions 
Event:  UCL (University College London) 
Open access status:  An open access version is available from UCL Discovery 
Language:  English 
Additional information:  Copyright © The Author 2018. Original content in this thesis is licensed under the terms of the Creative Commons Attribution 4.0 International (CC BY 4.0) Licence (https://creativecommons.org/licenses/by/4.0/). Any thirdparty copyright material present remains the property of its respective owner(s) and is licensed under its existing terms. Access may initially be restricted at the author’s request. 
UCL classification:  UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Statistical Science 
URI:  https://discovery.ucl.ac.uk/id/eprint/10064046 
Archive Staff Only
View Item 