Search

Your search keyword '"Liao, Shizhong"' showing total 173 results
Start Over Author "Liao, Shizhong"
173 results on '"Liao, Shizhong"'

1. Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis

Author

Li, Junfan and Liao, Shizhong

Subjects
Computer Science - Machine Learning
Abstract

Online kernel selection is a fundamental problem of online kernel methods.In this paper,we study online kernel selection with memory constraint in which the memory of kernel selection and online prediction procedures is limited to a fixed budget. An essential question is what is the intrinsic relationship among online learnability, memory constraint, and data complexity? To answer the question,it is necessary to show the trade-offs between regret and memory constraint.Previous work gives a worst-case lower bound depending on the data size,and shows learning is impossible within a small memory constraint.In contrast, we present distinct results by offering data-dependent upper bounds that rely on two data complexities:kernel alignment and the cumulative losses of competitive hypothesis.We propose an algorithmic framework giving data-dependent upper bounds for two types of loss functions.For the hinge loss function,our algorithm achieves an expected upper bound depending on kernel alignment.For smooth loss functions,our algorithm achieves a high-probability upper bound depending on the cumulative losses of competitive hypothesis.We also prove a matching lower bound for smooth loss functions.Our results show that if the two data complexities are sub-linear,then learning is possible within a small memory constraint.Our algorithmic framework depends on a new buffer maintaining framework and a reduction from online kernel selection to prediction with expert advice. Finally,we empirically verify the prediction performance of our algorithms on benchmark datasets.

Published
2024

2. Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound

Author

Liao, Yun, Li, Junfan, Liao, Shizhong, Hu, Qinghua, and Dang, Jianwu

Subjects
Computer Science - Machine Learning, Statistics - Machine Learning
Abstract

In this paper, we study the mistake bound of online kernel learning on a budget. We propose a new budgeted online kernel learning model, called Ahpatron, which significantly improves the mistake bound of previous work and resolves the open problem posed by Dekel, Shalev-Shwartz, and Singer (2005). We first present an aggressive variant of Perceptron, named AVP, a model without budget, which uses an active updating rule. Then we design a new budget maintenance mechanism, which removes a half of examples,and projects the removed examples onto a hypothesis space spanned by the remaining examples. Ahpatron adopts the above mechanism to approximate AVP. Theoretical analyses prove that Ahpatron has tighter mistake bounds, and experimental results show that Ahpatron outperforms the state-of-the-art algorithms on the same or a smaller budget.

Published
2023

3. Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression

Author

Li, Junfan and Liao, Shizhong

Subjects
Computer Science - Machine Learning, Statistics - Machine Learning
Abstract

The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of nearly orthogonal basis used to approximate the kernel mapping, and keep nearly optimal regret bounds by controlling the approximate error. The number of basis depends on the approximate error and the decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of $O(\sqrt{L(f)})$ and $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ at a computational complexity in $O(\ln^2{T})$. If the eigenvalues decay polynomially with degree $p\geq 1$, then our algorithms keep the same regret bounds at a computational complexity in $o(T)$ in the case of $p>4$ and $p\geq 10$, respectively. $L(f)$ is the cumulative losses of $f$ and $\mathrm{d}_{\mathrm{eff}}(\mu)$ is the effective dimension of the problem. The two regret bounds are nearly optimal and are not comparable.

Published
2023

4. Improved Regret Bounds for Online Kernel Selection under Bandit Feedback

Author

Li, Junfan and Liao, Shizhong

Subjects
Computer Science - Machine Learning
Abstract

In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a $O((\Vert f\Vert^2_{\mathcal{H}_i}+1)K^{\frac{1}{3}}T^{\frac{2}{3}})$ expected bound for Lipschitz loss functions. We prove two types of regret bounds improving the previous bound. For smooth loss functions, we propose an algorithm with a $O(U^{\frac{2}{3}}K^{-\frac{1}{3}}(\sum^K_{i=1}L_T(f^\ast_i))^{\frac{2}{3}})$ expected bound where $L_T(f^\ast_i)$ is the cumulative losses of optimal hypothesis in $\mathbb{H}_{i}=\{f\in\mathcal{H}_i:\Vert f\Vert_{\mathcal{H}_i}\leq U\}$. The data-dependent bound keeps the previous worst-case bound and is smaller if most of candidate kernels match well with the data. For Lipschitz loss functions, we propose an algorithm with a $O(U\sqrt{KT}\ln^{\frac{2}{3}}{T})$ expected bound asymptotically improving the previous bound. We apply the two algorithms to online kernel selection with time constraint and prove new regret bounds matching or improving the previous $O(\sqrt{T\ln{K}} +\Vert f\Vert^2_{\mathcal{H}_i}\max\{\sqrt{T},\frac{T}{\sqrt{\mathcal{R}}}\})$ expected bound where $\mathcal{R}$ is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.

Published
2023

5. Improved Kernel Alignment Regret Bound for Online Kernel Learning

Author

Li, Junfan and Liao, Shizhong

Subjects
Computer Science - Machine Learning
Abstract

In this paper, we improve the kernel alignment regret bound for online kernel learning in the regime of the Hinge loss function. Previous algorithm achieves a regret of $O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$ at a computational complexity (space and per-round time) of $O(\sqrt{\mathcal{A}_TT\ln{T}})$, where $\mathcal{A}_T$ is called \textit{kernel alignment}. We propose an algorithm whose regret bound and computational complexity are better than previous results. Our results depend on the decay rate of eigenvalues of the kernel matrix. If the eigenvalues of the kernel matrix decay exponentially, then our algorithm enjoys a regret of $O(\sqrt{\mathcal{A}_T})$ at a computational complexity of $O(\ln^2{T})$. Otherwise, our algorithm enjoys a regret of $O((\mathcal{A}_TT)^{\frac{1}{4}})$ at a computational complexity of $O(\sqrt{\mathcal{A}_TT})$. We extend our algorithm to batch learning and obtain a $O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$ excess risk bound which improves the previous $O(1/\sqrt{T})$ bound.

Published
2022

9. High-Probability Kernel Alignment Regret Bounds for Online Kernel Selection

Author

Liao, Shizhong, Li, Junfan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Oliver, Nuria, editor, Pérez-Cruz, Fernando, editor, Kramer, Stefan, editor, Read, Jesse, editor, and Lozano, Jose A., editor

Published
2021
Full Text
View/download PDF

10. Competitive Analysis of Online Kernel Selection in Unified Framework

Author

LIAO Yun, ZHANG Xiao, LIAO Shizhong

Subjects
competitive analysis, online kernel selection, expert advice framework, metrical task systems, unified framework, Electronic computers. Computer science, QA75.5-76.95
Abstract

Online kernel selection aims to find the optimal kernel for online kernel learning at each round. It is one of the fundamental and critical problems of online kernel learning. A problem of online kernel selection can be reduced to a problem of expert advice framework, where the set of experts corresponds to the set of candidate kernels. Predictions are given according to the weights and advices of the set of experts, and the weights are updated at each round. Based on the reduction, while improving the regret bound, this paper proposes the concept of expected online kernel selection. Within the unified framework of expert advice framework and metric task system, this paper presents the regret bounds and competitive ratios of expected online kernel selection, and proves that the competitive ratio is stable in expanded loss ranges. Finally, this paper derives a competitive ratio combined with online kernel learning. The work of investigating online kernel selection within the unified framework guarantees not only a sublinear regret bound, but also a strong competitive ratio, comprehensively generalizing the concept of online kernel selection and paving the way for new online kernel selection research.

Published
2020
Full Text
View/download PDF

13. Improved Sublinear Primal-Dual Algorithm for Support Vector Machines

Author

Gu, Ming, Liao, Shizhong, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Liu, Weiru, editor, Giunchiglia, Fausto, editor, and Yang, Bo, editor

Published
2018
Full Text
View/download PDF

14. Online Kernel Selection with Multiple Bandit Feedbacks in Random Feature Space

Author

Li, Junfan, Liao, Shizhong, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Liu, Weiru, editor, Giunchiglia, Fausto, editor, and Yang, Bo, editor

Published
2018
Full Text
View/download PDF

15. Stochastic Online Kernel Selection with Instantaneous Loss in Random Feature Space

Author

Han, Zhizhuo, Liao, Shizhong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Liu, Derong, editor, Xie, Shengli, editor, Li, Yuanqing, editor, Zhao, Dongbin, editor, and El-Alfy, El-Sayed M., editor

Published
2017
Full Text
View/download PDF

21. Parallel Column Subset Selection of Kernel Matrix for Scaling up Support Vector Machines

Author

Wu, Jiangang, Feng, Chang, Gao, Peihuan, Liao, Shizhong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Wang, Guojun, editor, Zomaya, Albert, editor, Martinez, Gregorio, editor, and Li, Kenli, editor

Published
2015
Full Text
View/download PDF

22. Accuracy-Preserving and Scalable Column-Based Low-Rank Matrix Approximation

Author

Wu, Jiangang, Liao, Shizhong, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Zhang, Songmao, editor, Wirsing, Martin, editor, and Zhang, Zili, editor

Published
2015
Full Text
View/download PDF

23. Boosting via Approaching Optimal Margin Distribution

Author

Liu, Chuan, Liao, Shizhong, Goebel, Randy, Series editor, Tanaka, Yuzuru, Series editor, Wahlster, Wolfgang, Series editor, Cao, Tru, editor, Lim, Ee-Peng, editor, Zhou, Zhi-Hua, editor, Ho, Tu-Bao, editor, Cheung, David, editor, and Motoda, Hiroshi, editor

Published
2015
Full Text
View/download PDF

24. Preventing Over-Fitting of Cross-Validation with Kernel Stability

Author

Liu, Yong, Liao, Shizhong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, Series editor, Tanaka, Yuzuru, Series editor, Wahlster, Wolfgang, Series editor, Siekmann, Jörg, Series editor, Calders, Toon, editor, Esposito, Floriana, editor, Hüllermeier, Eyke, editor, and Meo, Rosa, editor

Published
2014
Full Text
View/download PDF

25. Approximate Consistency: Towards Foundations of Approximate Kernel Selection

Author

Ding, Lizhong, Liao, Shizhong, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, Series editor, Tanaka, Yuzuru, Series editor, Wahlster, Wolfgang, Series editor, Siekmann, Jörg, Series editor, Calders, Toon, editor, Esposito, Floriana, editor, Hüllermeier, Eyke, editor, and Meo, Rosa, editor

Published
2014
Full Text
View/download PDF

27. An Explicit Description of the Extended Gaussian Kernel

Author

Liu, Yong, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Washio, Takashi, editor, and Luo, Jun, editor

Published
2013
Full Text
View/download PDF

30. Model Combination for Support Vector Regression via Regularization Path

Author

Wang, Mei, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Anthony, Patricia, editor, Ishizuka, Mitsuru, editor, and Lukose, Dickson, editor

Published
2012
Full Text
View/download PDF

31. Nyström Approximate Model Selection for LSSVM

Author

Ding, Lizhong, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Tan, Pang-Ning, editor, Chawla, Sanjay, editor, Ho, Chin Kuan, editor, and Bailey, James, editor

Published
2012
Full Text
View/download PDF

34. Accurate Probabilistic Error Bound for Eigenvalues of Kernel Matrix

Author

Jia, Lei, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Zhou, Zhi-Hua, editor, and Washio, Takashi, editor

Published
2009
Full Text
View/download PDF

37. A Generic Diffusion Kernel for Semi-supervised Learning

Author

Jia, Lei, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Sun, Fuchun, editor, Zhang, Jianwei, editor, Tan, Ying, editor, Cao, Jinde, editor, and Yu, Wen, editor

Published
2008
Full Text
View/download PDF

38. Cluster Selection Based on Coupling for Gaussian Mean Fields

Author

Chen, Yarui, Liao, Shizhong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Sun, Fuchun, editor, Zhang, Jianwei, editor, Tan, Ying, editor, Cao, Jinde, editor, and Yu, Wen, editor

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results