Abdulrhman Alanazi, Reem (2023). Optimal 0−1 loss classification in linear, overlapping and interpolation settings. University of Birmingham. Ph.D.
AbdulrhmanAlanazi2023PhD.pdf
Text  Accepted Version Restricted to Repository staff only until 12 December 2025. Available under License All rights reserved. Download (5MB)  Request a copy 
Abstract
Classification problems represent a major subject in machine learning, and addressing them requires solving underlying optimisation problems. Optimis ing the 0–1 loss function is the natural pathway to address the classification problem. Because of the properties of 0–1 loss, which are that it is nonconvex and nondifferentiable, 0–1 loss is mathematically intractable and classified as nondeterministic polynomialtime hard (NPhard). Consequently, the 0– 1 loss function has been replaced by surrogate loss functions that can be optimised more efficiently, where their optimal solution is guaranteed with respect to these surrogate losses. At the same time, these functions may not provide the same optimal solution as the 0–1 loss function. Indeed, the loss function used during the empirical risk minimisation (ERM) is not the same loss function used in evaluation; the mismatch of the loss functions leads to an approximate solution that may not be an ideal solution for 0–1 loss. Thus, an additional source of error is produced because of this replacement.
In this thesis, optimising 0–1 loss directly is discussed from three per spectives. First, the consequences of replacing the 0–1 loss function with surrogate functions from the theoretical perspective for linearly separable data are outlined, showing that hinge loss is an exact minimiser for 0–1 loss under this setting. Second, in the case of overlapping, it is determined that the surrogate functions do not provide an exact solution. Therefore, we compared the actual time complexity of existing 0–1 loss optimisation algo rithms based on the following secondorder factors: dimensionality of data and amount of overlap between classes. In addition, a new heuristic 0–1 loss optimisation algorithm was introduced that can optimise 0–1 risk exactly in practical way in \(O(\sqrt{D}\log(\frac{1}{\epsilon})N^3)\) polynomial complexity class. A new al gorithm, called testing all pairs of points (TPP), as well as its prioritised version, was introduced; the prioritised version has actual time complexity that is less than TPP, and it is referred to as prioritising the search by support vectors (PSSVs). TPP and PSSVs can terminate before the time limit, whereas the time taken by other direct 0–1 loss optimisation algorithms depends on secondorder factors when the data size is fixed. Third, a new di rection of ERM is discussed in a simple classification algorithm, which is the canonical K nearest neighbour (KNN) algorithm that still dominates by the conventional ERM. The interpolated local KNN is our new algorithm, which works on modern interpolation ERM view. The interpolated local KNN aims to fit the training points locally using a set of local K parameters that are determined by a predefined confidence score. The mechanism used in the interpolated local KNN helps to define the noise and overlap points and then isolate them from being used in predicting unseen points, whereas the iso lated points have their own decision boundary that can be used to predict them correctly. Thus, we can have zero empirical risk and low generalisation risk compared with the canonical KNN.
These contributions show the possibility of optimising the 0–1 loss directly in polynomial time for linearly separable data using a surrogate loss function; for overlapping data, our new algorithms TPP and PSSVs can be used. Ultimately, we introduce a first interpolation version for the canonical KNN algorithm. This thesis focuses on the binary classification problem; our main focus in the future will be to extend this work to multiclass classification.
Type of Work:  Thesis (Doctorates > Ph.D.)  

Award Type:  Doctorates > Ph.D.  
Supervisor(s): 


Licence:  All rights reserved  
College/Faculty:  Colleges (2008 onwards) > College of Engineering & Physical Sciences  
School or Department:  School of Computer Science  
Funders:  Other  
Other Funders:  King Faisal University  
Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software 

URI:  http://etheses.bham.ac.uk/id/eprint/14290 
Actions
Request a Correction  
View Item 
Downloads
Downloads per month over past year