UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Online graph-based learning for classification

Wainer, LJ; (2008) Online graph-based learning for classification. Doctoral thesis , UCL (University College London). Green open access

[thumbnail of Wainer_thesis.Redacted.pdf]
Preview
Text
Wainer_thesis.Redacted.pdf

Download (16MB) | Preview

Abstract

The aim of this thesis is to develop online kernel based algorithms for learning clas sification functions over a graph. An important question in machine learning is: how to learn functions in a high dimension One of the benefits of using a graphical representation of data is that it can provide a dimensionality reduction of the data to the number of nodes plus edges in the graph. Graphs are useful discrete repre sentations of data that have already been used successfully to incorporate structural information in data to aid in semi-supervised learning techniques. In this thesis, an online learning framework is used to provide guarantees on performance of the algo rithms developed. The first step in developing these algorithms required motivating the idea of a "natural" kernel defined on a graph. This natural kernel turns out to be the Laplacian operator associated with the graph. The next step was to look at a well known online algorithm - the perceptron algorithm - with the associated bound, and formulate it for online learning with this kernel. This was a matter of using the Laplacian kernel with the kernel perceptron algorithm. For a binary classification problem, the bound on the performance of this algorithm can be interpreted in terms of natural properties of the graph, such as the graph diameter. Further algorithms were developed, motivated by the idea of a series of alternate projections, which also share this bound interpretation. The minimum norm interpolation algorithm was developed in batch mode and then transformed into an online algorithm. These al gorithms were tested and compared with other proposed algorithms on toy and real data sets. The main comparison algorithm used was k-nearest neighbour along the graph. Once the kernel has been calculated, the new algorithms perform well and offer some advantages over other approaches in terms of computational complexity.

Type: Thesis (Doctoral)
Title: Online graph-based learning for classification
Identifier: PQ ETD:593480
Open access status: An open access version is available from UCL Discovery
Language: English
Additional information: Thesis digitised by ProQuest. Third party copyright material has been removed from the ethesis. Images identifying individuals have been redacted or partially redacted to protect their identity.
URI: https://discovery.ucl.ac.uk/id/eprint/1446151
Downloads since deposit
47Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item