Loading...
Please wait, while we are loading the content...
Efficient Learning Algorithms for Rankings and Other Combinatorial Concept Classes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Suehiro, Daiki |
| Copyright Year | 2014 |
| Abstract | Recently, learning to rank techniques has been attracting increasing attention in various areas such as web search, product recommendation, financial risk analysis, scheduling, and so on. Informally, the task is to obtain an appropriate ranking among items from training data. The amount of data is typically very large in these areas and even rapidly increasing. Therefore, it is particularly important to develop learning algorithms that run efficiently, as well as producing rankings with high quality. In this thesis, we explore efficient algorithms in the following two theoretical learning models, the statistical learning model and the online prediction model. In the statistical learning model, we consider the bipartite ranking problem, which is one of the most fundamental problems of learning ranking functions. In the bipartite ranking problem, we are given a randomly generated sample consisting of positive and negative instances and required to learn a real-valued function called a ranking function, so that it maps a positive instance to a higher value than a negative instance. It is well known that the problem is reduced to a binary classification problem and so we can apply any of standard learning algorithms such as the Support Vector Machines (SVMs). However, the sample is blown up quadratically in size through the reduction. This means that if we use the 1-norm or 2-norm regularized SVM to obtain a good ranking function, we need to solve a linear or quadratic programming problem of size O(m), respectively, where m is the size of the original sample. In this thesis, we reformulate the SVMs for ranking functions as significantly simplified optimization problems of size O(m) and give theoretical guarantees on the generalization ability of the ranking functions obtained by solving the optimization problems. In particular, the reformulation of the 1-norm regularized SVM yields the first practical algorithm that is competitive with the original 1-norm regularized SVM in performance. As an application of our algorithm, we consider the problem of constructing an evalu- |
| File Format | PDF HTM / HTML |
| DOI | 10.15017/1441266 |
| Alternate Webpage(s) | https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1441266/isee534.pdf |
| Alternate Webpage(s) | https://doi.org/10.15017/1441266 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
