Efficient Kernel-Based Online Learning via Budgeted SGD
예산 SGD를 통한 효율적인 커널 기반 온라인 학습
- 주제(키워드) stochastic gradient descent , large-scale learning , online learning , kernel methods , SVM , WSVM , KQR
- 발행기관 고려대학교 대학원
- 지도교수 신승준
- 발행년도 2025
- 학위수여년월 2025. 2
- 학위명 석사
- 학과 및 전공 대학원 통계학과
- 원문페이지 27 p
- 실제URI http://www.dcollection.net/handler/korea/000000290847
- UCI I804:11009-000000290847
- DOI 10.23186/korea.000000290847.11009.0001882
- 본문언어 영어
초록/요약
Kernel-based models, while powerful, often suffer from scalability issues due to their quadratic complexity in the number of training samples. This limitation restricts their applicability to large-scale datasets and real-time applications. To address this challenge, we propose the Budgeted Stochastic Gradient Descent (BSD) algorithm. BSGD limits the number of support vectors to a predefined budget, thereby controlling memory usage and computational cost. We apply BSGD to several kernel-based models and demonstrate through extensive experiments on synthetic and real-world datasets that it can significantly reduce training time and memory usage without compromising predictive performance. Our findings highlight the potential of BSGD as a practical solution for large-scale and real-time machine learning tasks.
more초록/요약
커널 기반 모델은 높은 성능을 자랑하지만, 훈련 샘플 수에 비례한 이차적 복잡성 으로 인해 확장성에 한계가 있습니다. 이러한 제약은 대규모 데이터셋과 실시간 애플리케이션에서의 활용을 어렵게 만듭니다. 본 연구에서는 이러한 문제를 해결하기 위해 Budgeted Stochastic Gradient Descent(BSGD) 알고리즘을 제안합니다. BSGD는 지원 벡터의 개수를 사전에 정의된 예산으로 제한함으로써 메모리 사용량과 계산 비용을 제어합니다. BSGD를 여러 커널 기반 모델에 적용한 결과, 합성 및 실제 데이터셋 실험에서 예측 성능을 유지하면서 훈련 시간과 메모리 사용량을 크게 줄일 수 있음을 확인하였습니다. 본 연구는 BSGD가 대규모 및 실시간 머신러닝 작업에 있어 실용적인 해결책으로서의 가능성을 제시합니다.
more목차
Abstract i
국문초록 ii
Table of Contents ii
List of Tables v
List of Figures vi
1 Introduction 1
1.1 Online Learning Algorithm 1
1.2 Stochastic Gradient Descent (SGD) for SVMs 2
1.3 Kernelization for Non-Linear Problems 3
1.4 Curse of Kernelization 4
2 Budget Maintenance on SGD 6
2.1 Budget Maintenance Strategy 6
2.2 Weight Degradation 6
2.3 Budget Maintenance through Removal 7
2.4 Algorithm: Budgeted SGD for SVM 8
3 Extension 9
3.1 Extension to Weighted SVM (WSVM) 9
3.2 Kernel Quantile Regression (KQR) 10
4 Results 12
4.1 Simulation Results 12
4.1.1 SVM, Weighted SVM(WSVM) Results 12
4.1.2 Kernel Quantile Regression (KQR) Results 13
4.1.3 Computation Time Analysis 15
4.2 Real Data Results 15
4.2.1 SVM and WSVM Performance 15
4.2.2 Kernel Quantile Regression (KQR) Results 16
4.2.3 Computation Time Analysis 17
5 Discussion 19
