How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets
Zhiyun Lu1†, Avner May2† Kuan Liu1‡, Alireza Bagheri Garakani1‡, Dong Guo1‡, Aurélien Bellet4‡111Most of the work in this paper was carried out while the author was affiliated with Department of Computer Science, University of Southern California. Linxi Fan2, Michael Collins2, Brian Kingsbury3, Michael Picheny3, Fei Sha1¶ 1 Dept. of Computer Science, U. of Southern California, Los Angeles, CA 90089 {zhiyunlu, kuanl, bagherig, dongguo, 2 Dept. of Computer Science, Columbia University, New York, New York 10027 {avnermay, 3 IBM T. J. Watson Research Center, Yorktown Heights, NY 10598 {bedk, 4 LTCI UMR 5141, Télécom ParisTech、CNRS, France † and ‡: shared first and second co-authorships, respectively ¶: to whom questions and comments should be sent
Abstract
The computational complexity of kernel methods has often been a major barrier for applying them to large-scale learning problems. We argue that this barrier can be effectively overcome. In particular, we develop methods to scale up kernel models to successfully tackle large-scale learning problems that are so far only approachable by deep learning architectures. Based on the seminal work by [38] on approximating kernel functions with features derived from random projections, we advance the state-of-the-art by proposing methods that can efficiently train models with hundreds of millions of parameters, and learn optimal representations from multiple kernels. We conduct extensive empirical studies on problems from image recognition and automatic speech recognition, and show that the performance of our kernel models matches that of well-engineered deep neural nets (DNNs). To the best of our knowledge, this is the first time that a direct comparison between these two methods on large-scale problems is reported. Our kernel methods have several appealing properties: training with convex optimization, cost for training a single model comparable to DNNs, and significantly reduced total cost
中文速览
核函数方法（kernel methods）虽然理论优美，却因计算复杂度随训练样本数平方增长而难以处理大规模数据，长期被认为无法与深度神经网络（DNN）正面竞争。本文基于随机投影近似核函数的经典思路，提出了一套可扩展的训练方案：利用随机特征将核模型转化为超亿参数的线性分类器，并结合随机梯度平均法（SAG）和分块并行训练实现高效优化；同时提出多核乘法组合策略，让模型能从数据中自适应学习更优的特征表示。在大规模图像识别和语音识别基准上的系统对比实验表明，这些核模型的性能可以媲美甚至超越精心调优的深度神经网络，而且超参数更少、总调参成本更低。这是首次在真正大规模任务上对两类方法进行直接对比，不仅证明了核方法在工业级问题上的可行性，也为理解两种范式各自学到了哪些互补表示提供了新的研究视角。
原文 arXiv:1411.4000;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1411.4000v2