MPhil Thesis Defence "Scaling up Support Vector Data Description by Using Core-sets" By Mr. Shun-Kwong Chu Abstract Support vector data description (SVDD) is a powerful kernel method that has been commonly used for novelty detection. While its quadratic programming formulation has the important computational advantage of avoiding the problem of local minimum, this has a runtime complexity of O(N3), where N is the number of training patterns. It thus becomes prohibitive when the data set is large. Core-sets approximation are common in shape fitting problems in computational geometry, where approximating the minimum enclosing ball problem have several nice properties. The runtime is relatively small comparing with other shape fitting problems; moreover, it also grows linear with N and the dimension of the data. Inspired from the use of Core-sets in approximating the minimum enclosing ball problem in computational geometry, we propose an approximate and heuristic method, called Core-sets SVDD (CSVDD), that allows SVDD to scale better to larger data sets. Most importantly, the proposed method has a running time that is only linear in N. Experimental results on two large real-world data sets demonstrate that the proposed method can handle data sets that are much larger than those that can be handled by standard SVDD packages, while its approximate solution still attains comparable, or sometimes even better, novelty detection performance. An ensemble approach of CSVDD, called ESVDD, is also proposed. This method can help to improve novelty detection performance of CSVDD as well as reduce variations. The running time of ECSVDD is still linear in N. Date: Saturday, 21 August 2004 Time: 11:00a.m.-1:00p.m. Venue: Room 3006 Lift 3 Committee Members: Prof. James Kwok (Supervisor) Prof. Dit-Yan Yeung (Chairperson) Prof. Brian Mak **** ALL are Welcome ****