Generalization Bounds for Certain Class of Ranking Algorithm

Wei Gao; Yun Gang Zhang

doi:10.4028/www.scientific.net/AMR.267.456

Paper Titles

A Novel Method to Calculate Frequency Control Word of Direct Digital Synthesizer
p.433

Stability Analysis for Local Transductive Regression Algorithms
p.438

Data Stream Clustering Algorithm Based on Affinity Propagation and Density
p.444

New Criteria on Impulsive Stabilization and Synchronization of Delayed Unified Chaotic Systems with Uncertainty
p.450

Generalization Bounds for Certain Class of Ranking Algorithm
p.456

A New Method to Detect P-Wave Based on Quadratic Function
p.462

Stock Price Index Prediction Based on Improved SVM
p.468

Application of Teleoperation for Rehabilitation Training Robot
p.472

Collision Detection Based on Surface Simplification and Particle Swam Optimization
p.476

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 267Generalization Bounds for Certain Class of Ranking...

Generalization Bounds for Certain Class of Ranking Algorithm

Abstract:

The quality of ranking determines the success or failure of information retrieval and the goal of ranking is to learn a real-valued ranking function that induces a ranking or ordering over an instance space. We focus on a ranking setting which uses truth function to label each pair of instances and the ranking preferences are given randomly from some distributions on the set of possible undirected edge sets of a graph. The contribution of this paper is the given generalization bounds for such ranking algorithm via strong and weak stability. Such stabilities have lower demand than uniform stability and fit for more real applications.

You might also be interested in these eBooks

Manufacturing Systems and Industry Application

View Preview

Info:

Periodical:

Advanced Materials Research (Volume 267)

Pages:

456-461

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.267.456

Citation:

Cite this paper

Online since:

June 2011

Authors:

Wei Gao, Yun Gang Zhang

Keywords:

Algorithmic Stability, Generalization Bounds, Ranking, Strong Stability, Truth Function, Weak Stability

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] R. Cynthia, E. Robert, and D. Ingrid, Boosting based on a smooth margin, Proceedings of the 16th Annual Conference on Computational Learning Theory, pp.502-517, (2004).

Google Scholar

[2] C. Burges, Learning to rank using gradient descent, Proceedings of the 22nd Intl Conference on Machine Learning, pp.89-96, (2005).

Google Scholar

[3] Y. Rong, Alexander, and D. Hauptmann, Efficient margin-based rank learning algorithms for information retrieval, CIVR, pp.113-122, (2006).

Google Scholar

[4] R. Cynthia, Ranking with a P-Norm Push, COLT 2006, LNAI 4005, pp.589-604, (2006).

Google Scholar

[5] C. Rudin, C. Cortes, M. Mohri, and R.E. Schapire, Margin-based ranking meets boosting in the middle, In Proceedings of the 18th Annual Conference on Learning Theory, (2005).

DOI: 10.1007/11503415_5

Google Scholar

[6] S. Agarwal, and P. Niyogi, Generalization bounds for ranking algorithms via algorithmic stability, Journal of Machine Learning Research, vol 10 , December. 2009, pp.441-474.

Google Scholar

[7] S. Kutin, and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, (2002).

Google Scholar

[8] S. Kutin. Extensions to McDiarmid's inequality when differences are bounded with high probability, Technical report, Department of Computer Science, The university of Chicago, (2002).

Google Scholar

[9] Dominique de Caen. An upper bound on the sum of squares of degrees in a graph, Discrete Mathematics, 185: 245-248, (1998).

DOI: 10.1016/s0012-365x(97)00213-6

Google Scholar