On empirical eigenfunction-based ranking with ℓ1 norm regularization
-
Min Xu [1] ; Qin Fang [2] ; Shaofan Wang [3] ; Junbin Li [1]
-
[1] Dalian University of Technology
Dalian University of Technology
China
-
[2] Dalian University
Dalian University
China
-
[3] Beijing University of Technology
Beijing University of Technology
China
-
- Localización: Journal of approximation theory, ISSN 0021-9045, Vol. 192, Nº 1 (April 2015), 2015, págs. 273-290
- Idioma: inglés
- DOI: 10.1016/j.jat.2014.12.011
- Enlaces
-
Resumen
The problem of ranking, in which the goal is to learn a real-valued ranking function that induces a ranking over an instance space, has recently gained increasing attention in machine learning. We study a learning algorithm for ranking generated by a regularized scheme with an ℓ1 regularizer. The algorithm is formulated in a data dependent hypothesis space. Such a space is spanned by empirical eigenfunctions which are constructed by a Mercer kernel and the learning data. We establish the computations of empirical eigenfunctions and the representer theorem for the algorithm. Particularly, we provide an analysis of the sparsity and convergence rates for the algorithm. The results show that our algorithm produces both satisfactory convergence rates and sparse representations under a mild condition, especially without assuming sparsity in terms of any basis
