2006 RankingOnGraphData
Jump to navigation
Jump to search
- (Agarwal, 2006) ⇒ Shivani Agarwal. (2006). “Ranking on Graph Data.” In: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006) doi:10.1145/1143844.1143848
Subject Headings: Ranking Function, Graph Structure.
Notes
Cited By
Quotes
Abstract
In ranking, one is given examples of order relationships among objects, and the goal is to learn from these examples a real-valued ranking function that induces a ranking or ordering over the object space. We consider the problem of learning such a ranking function when the data is represented as a graph, in which vertices correspond to objects and edges encode similarities between objects. Building on recent developments in regularization theory for graphs and corresponding Laplacian-based methods for classification, we develop an algorithmic framework for learning ranking functions on graph data. We provide generalization guarantees for our algorithms via recent results based on the notion of algorithmic stability, and give experimental evidence of the potential benefits of our framework.
References
- 1. Shivani Agarwal, Thore Graepel, Ralf Herbrich, Sariel Har-Peled, Dan Roth, Generalization Bounds for the Area Under the ROC Curve, The Journal of Machine Learning Research, 6, p.393-425, 9/1/2005
- 2. Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. Proceedings of the 18th Annual Conference on Learning Theory.
- 3. Altschul, S. F., Madden, T. L., Schaffer, A. A., Zhang, J., Zhang, Z., Miller, W., & Lipman, D. J. (1997). Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25, 3389--3402.
- 4. Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. Proceedings of the 17th Annual Conference on Learning Theory.
- 5. Mikhail Belkin, Partha Niyogi, Semi-Supervised Learning on Riemannian Manifolds, Machine Learning, v.56 n.1-3, p.209-239 doi:10.1023/B:MACH.0000033120.25363.1e
- 6. Olivier Bousquet, André Elisseeff, Stability and generalization, The Journal of Machine Learning Research, 2, p.499-526, 3/1/2002 doi:10.1162/153244302760200704
- 7. Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
- 8. Christopher J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 doi:10.1023/A:1009715923555
- 9. Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society.
- 10. Chung, F. R. K. (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9, 1--19.
- 11. Cohen, W. W., Schapire, R. E., & Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 243--270.
- 12. Cortes, C., & Mohri, M. (2004). AUC optimization vs. error rate minimization. Advances in Neural Information Processing Systems 16.
- 13. Crammer, K., & Singer, Y. (2002). Pranking with ranking. Advances in Neural Information Processing Systems 14.
- 14. Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
- 15. Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers, 115--132.
- 16. Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
- 17. Joachims, T. (2003). Transductive learning via spectral graph partitioning. Proceedings of the 20th International Conference on Machine Learning.
- 18. Murzin, A., Brenner, S. E., Hubbard, T., & Chothia, C. (1995). SCOP: A structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology, 247, 536--540.
- 19. John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
- 20. Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326..
- 21. Vikas Sindhwani, Partha Niyogi, Mikhail Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proceedings of the 22nd International Conference on Machine learning, p.824-831, August 07-11, 2005, Bonn, Germany doi:10.1145/1102351.1102455
- 22. Strang, G. (1988). Linear algebra and its applications. Brooks Cole. 3rd edition.
- 23. Tenenbaum, J., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.
- 24. Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
- 25. Weston, J., Eliseeff, A., Zhou, D., Leslie, C., & Noble, W. S. (2004). Protein ranking: from local to global structure in the protein similarity network. Proceedings of the National Academy of Science, 101, 6559--6563..
- 26. Dengyong Zhou, Jiayuan Huang, Bernhard Schölkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd International Conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany doi:10.1145/1102351.1102482
- 27. Zhou, D., & Schöölkopf, B. (2004). A regularization framework for learning from graph data. ICML Workshop on Statistical Relational Learning.
- 28. Zhou, D., Weston, J., Gretton, A., Bousquet, O., & Schöölkopf, B. (2004). Ranking on data manifolds. Advances in Neural Information Processing Systems 16.
,