Support Vector Learning for Ordinal Regression

In the short paper, the author proposed an order learning method based on SVM and gave some analysis of its behaviour. The problem of ordinal regression is of great importance because in many cases we are unable (or unnatural) to provide metric observations while purely classification is not enough for our needs. This condition arises most often in opinion polls where the answers are seldom in numbers but in preference classes. In my memory, this is the first time we study this problem in the class.

 

Given input space X and an ordered outcome space Y, the author first shows that the problem of learning the mapping function h {X->Y} can be formulated as finding an optimal h that minimizes pairwise ordering reversals among all the training samples over some probability distribution. The author then further shows that by maximizing the margins of different ranks one could bound the learning error even better. Finally, an algorithm with similar ideas to SVM is proposed to compute the projection axis for the rank classification. The algorithm may be adapted to non-linear cases using the standard kernel method.

 

The experiments did support the idea. Since this method built implicit ordering relation into the seperating hyperplanes, it could be anticipated to outperform the standard multi-class SVM. The concept of minimizing discrimination functions over the pairwise sample space can also be applied to other learning algorithms as well. For instance, I am wondering how it would work when AdaBoost replaces SVM. This should be quite interesting.

The PageRank Citation Ranking: Bringing Order to the Web

This paper introduces the PageRank algorithm, which is one of the central ranking estimators employed in the Google search engine. The idea of PageRank is quite simple: if one page is cited (linked) by a important page, it should likely be important as well. By putting more important pages in front of less important ones in the result list, we can effectively improve the search quality. Although I don't actually know how they combine different estimators in Google, PageRank seems to be the essential ones.

 

Although the definition of PageRank is recursive, given a network it can be computed via naive iterations when we view the pages and links as nodes and edges respectively. First, we randomly initialize the value of each page, and second, we update them by propagating those values through the links on the page. The iteration is ran to the convergence. If we interpret the normalized values of pages as probabilities, the thing that PageRank do is equivalent to computing the long term probabilities of a random walk markov chain. As argued in the paper, simple iterations converge quickly on common networks as their geometries permit.

 

The author further introduced a method to personalize the search engine. Using the thought of transition probability matrices in random walk, we could blend each row with some constant vectors that characterize personal preferences. The experiments on real data did support this idea. The other applications shown in the paper are also interesting.