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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:719122 |
| Date | January 2008 |
| Creators | Wainer, L. J. |
| Publisher | University College London (University of London) |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://discovery.ucl.ac.uk/1446151/ |
Page generated in 0.0153 seconds