ERA

Download the full-sized PDF of Multiple Kernel Learning with Many KernelsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3K01H

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Multiple Kernel Learning with Many Kernels Open Access

Descriptions

Other title
Subject/Keyword
Greedy Coordinate Descent
Multiple Kernel Learning
Stochastic Gradient Descent
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Afkanpour, Arash
Supervisor and department
Szepesvari, Csaba (Computing Science)
Bowling, Michael (Computing Science)
Examining committee member and department
Szepesvari, Csaba (Computing Science)
Schuurmans, Dale (Computing Science)
Mizera, Ivan (Mathematical and Statistical Sciences)
Pontil, Massimiliano (Computer Science, University College London)
Bowling, Michael (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2013-03-20T13:40:17Z
Graduation date
2013-06
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
Multiple kernel learning (MKL) addresses the problem of learning the kernel function from data. Since a kernel function is associated with an underlying feature space, MKL can be considered as a systematic approach to feature selection. Many of the existing MKL algorithms perform kernel learning by combining a given set of base kernels. While efficient MKL algorithms are capable of handling large training sets, their computational complexity depends linearly on the number of base kernels. Hence, these algorithms are not scalable to problems with many kernels. In this thesis, we investigate MKL when the number of kernels is very large. We aim to exploit the structure of kernel space to design efficient MKL algorithms. Such a structure exists for some of the important families of kernels, such as polynomial kernels and Gaussian kernels. We propose efficient gradient-based algorithms, with convergence guarantees, for the two prominent problem formulations of MKL, i.e. one-stage and two-stage MKL. We show that stochastic gradient descent and greedy coordinate descent are suitable algorithms to deal with very large kernel sets. We propose an efficient stochastic gradient descent method for one-stage MKL. We show that sampling a coordinate with a probability proportional to the magnitude of gradient results in a low-variance estimate of gradient. For the case of learning polynomial kernels we show that the computational complexity of our algorithm has only a logarithmic dependence on the number of kernels. We show how greedy coordinate descent can be applied to one-stage and two-stage MKL. Greedy coordinate descent is in particular useful when the goal is to combine continuously-parameterized kernels, such as Gaussian kernels. We perform thorough empirical study on synthetic and real data to compare the new gradient-based algorithms against several MKL algorithms. Our experiments demonstrate that our new methods are competitive in terms of generalization performance, while their computational cost is significantly less than other methods that enjoy similarly good generalization performance.
Language
English
DOI
doi:10.7939/R3K01H
Rights
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Afkanpour, A. Gyorgy, A., Szepesvari, C., and Bowling, M., A Randomized Mirror Descent Algorithm for Large Scale Multiple Kernel Learning. JMLR W&CP 28(1):374-382, 2013.

File Details

Date Uploaded
Date Modified
2014-04-30T22:15:44.000+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1240696
Last modified: 2015:10:18 02:07:43-06:00
Filename: thesis.pdf
Original checksum: fdcf78672779c925156bb7e4e8f1c720
Well formed: true
Valid: false
Status message: Invalid destination object offset=1185517
Status message: Invalid destination object offset=1185517
Status message: Invalid destination object offset=1185517
Status message: Invalid destination object offset=1185517
Status message: Invalid destination object offset=1185517
File title: Frontmatter
File title: Multiple Kernel Learning with Many Kernels
File author: Arash Afkanpour
Page count: 109
Activity of users you follow
User Activity Date