Memory and Computation-Efficient Kernel SVM via Binary Embedding and Ternary Model Coefficients

Zijian Lei, Liang Lan

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

Abstract

Kernel approximation is widely used to scale up kernel SVM training and prediction. However, the memory and computation costs of kernel approximation models are still too large if we want to deploy them on memory-limited devices such as mobile phones, smart watches and IoT devices. To address this challenge, we propose a novel memory and computation-efficient kernel SVM model by using both binary embedding and binary model coefficients. First, we propose an efficient way to generate compact binary embedding of the data which can preserve the kernel similarity. Second, we propose a simple but effective algorithm to learn a linear classification model with binary coefficients which can support different types of loss function and regularizer. Our algorithm can achieve better generalization accuracy than existing works on learning binary coefficients since we allow coefficient to be -1, 0 or 1 during the training stage and coefficient 0 can be removed during model inference. Moreover, we provide detailed analysis on the convergence of our algorithm and the inference complexity of our model. The analysis shows that the convergence to a local optimum is guaranteed and the inference complexity of our model is much lower than other competing methods. Our experimental results on five large real-world datasets have demonstrated that our proposed method can build accurate nonlinear SVM model with memory cost less than 30KB.
Original languageEnglish
Title of host publication35th AAAI Conference on Artificial Intelligence, AAAI 2021
PublisherAAAI press
Pages8316-8323
Number of pages8
ISBN (Print)9781577358664
DOIs
Publication statusPublished - 18 May 2021
Event35th AAAI Conference on Artificial Intelligence, AAAI 2021 - Virtual
Duration: 2 Feb 20219 Feb 2021
https://aaai.org/Conferences/AAAI-21/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
Number9
Volume35
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468
NameAAAI-21/ IAAI-21/ EAAI-21 Proceedings

Conference

Conference35th AAAI Conference on Artificial Intelligence, AAAI 2021
Period2/02/219/02/21
Internet address

User-Defined Keywords

  • Classification and Regression

Fingerprint

Dive into the research topics of 'Memory and Computation-Efficient Kernel SVM via Binary Embedding and Ternary Model Coefficients'. Together they form a unique fingerprint.

Cite this