Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Exact and Efficient Leave-Pair...

Exact and Efficient Leave-Pair-Out Cross-Validation for Ranking RLS

Tapio Pahikkala, Antti Airola, Jorma Boberg, Tapio Salakoski, Exact and Efficient Leave-Pair-Out Cross-Validation for Ranking RLS. In: Timo Honkela, Matti Pöllä, Mari-Sanna Paukkeri, Olli Simula (Eds.), Proceedings of the 2nd International and Interdisciplinary Conference on Adaptive Knowledge Representation and Reasoning (AKRR08), 1-8, Helsinki University of Technology, 2008.

Abstract:

In this paper, we introduce an efficient cross-validation algorithm for RankRLS, a kernel-based ranking algorithm. Cross-validation (CV) is one of the most useful methods for model selection and performance assessment of machine learning algorithms, especially when the number of labeled data is small. A natural way to measure the performance of ranking algorithms by CV is to hold each data point pair out from the training set at a time and measure the performance with the held out pair. This approach is known as leave-pair-out cross-validation (LPOCV).

We present a computationally efficient algorithm for performing LPOCV for RankRLS. If RankRLS is already trained with the whole training set, the computational complexity of the algorithm is O(m^2). Further, if there are d outputs to be learned simultaneously, the computational complexity of performing LPOCV is O(m^2d). An approximative O(m^2) time LPOCV algorithm for RankRLS has been previously proposed, but our method is the first exact solution to this problem.

We introduce a general framework for developing and analysing hold-out and cross-validation techniques for quadratically regularized kernel-based learning algorithms. The framework is constructed using a value regularization based variant of the representer theorem. We provide a simple proof for this variant using matrix calculus. Our cross-validation algorithm can be seen as an instance of this framework.

Files:

Abstract in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpPaAiBoSa08a,
  title = {Exact and Efficient Leave-Pair-Out Cross-Validation for Ranking RLS},
  booktitle = {Proceedings of the 2nd International and Interdisciplinary Conference on Adaptive Knowledge Representation and Reasoning (AKRR08)},
  author = {Pahikkala, Tapio and Airola, Antti and Boberg, Jorma and Salakoski, Tapio},
  editor = {Honkela, Timo and Pöllä, Matti and Paukkeri, Mari-Sanna and Simula, Olli},
  publisher = {Helsinki University of Technology},
  pages = {1-8},
  year = {2008},
}

Belongs to TUCS Research Unit(s): Turku BioNLP Group

Edit publication