The Kendall and Mallows Kernels for Permutations.

Area of Science:

• Machine Learning
• Statistics
• Computational Biology

Background:

• Kernel methods are powerful tools in machine learning for analyzing complex data.
• Permutation data, representing ordered lists or rankings, presents unique analytical challenges.
• Existing kernels for permutation data can be computationally intensive.

Purpose of the Study:

• To introduce Kendall tau correlation and Mallows kernels as positive definite kernels for permutation data.
• To demonstrate their utility as computationally attractive alternatives to existing methods.
• To extend these kernels for handling partial, multivariate, and uncertain rankings.

Main Methods:

• Theoretical analysis to establish the positive definiteness of Kendall tau and Mallows kernels.
• Development of kernel extensions for partial, multivariate, and uncertain rankings.
• Application of these kernels to clustering and classification problems using kernel algorithms.

Main Results:

• Kendall tau and Mallows kernels are proven to be positive definite kernels for permutations.
• The proposed extensions effectively handle diverse ranking data complexities.
• Promising results were achieved in clustering heterogeneous rank data and high-dimensional biomedical classification.

Conclusions:

• Kendall tau and Mallows kernels provide efficient and effective tools for learning from ranking data.
• These kernels offer versatile solutions for various ranking scenarios, including partial and uncertain data.
• The demonstrated success in biomedical applications highlights their practical significance.