Tuesday, May 15, 2007
Ranking on Graph Data
The ranking problem asks for a function which gives us an order of samples. This requirement can be found on search engines, which give the user a sequence of search results of the preferred order of the user. I don't have earlier experience of ranking problems, so I am just curious about this article. After scanning, it turns out highly related to SVM theory.
There is a ranking risk matrix that descibe the risk of ranking error.
So the empirical ranking risk can be formulated as a functional of ranking function, which is what we are looking for. As for a graph, the function degenerates to a vector. As is in SVM, a regularizer is chosen so as to smooth the function by punish the divergence of values on nearby vertices. On thinking about this, the Laplacian regularizer is a commonly used one. (Just think about the Laplacian Eigenmap, the optimized value)
Directed graphs can be treated likewise. The paper later suggests a connection to RKHS and application in bioinformatics. Indeed, multiple alignment requires a ranking result.
Since the loss function relaxed in this paper is still Hinge loss, the idea of Trading Convexity for Scalability should be applicable to it.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment