AllKendall: All Kendall's distances between two sets of total rankings or...

In YunlongJiao/kernrank: Kernel Methods for Rank Data

Description

Calculates all of the Kendall's distances between two sets of total rankings or real-valued vectors.

Usage

AllKendall(r, seqs = NULL, data.info = NULL, use.kernel.trick = FALSE,
  kmat = NULL, type = c("type-b", "type-a"), mc = 0.25)

Arguments

r	A vector or a matrix of m1 sequences in rows and orders of n items in cols.
seqs	Another vector or a matrix of m2 sequences in rows and orders of n items in cols. By default "seqs" is set equal to "r".
data.info	Optional argument giving the Kendall embedding of "r", that is the result of calling KendallInfo, to facilitate computing Kendall's difference for "r" to "seqs" without exploring the kernel trick.
use.kernel.trick	Logical. Indicator of whether the kernel trick is explored. This is particularly interesting when the number of items to be ranked is large (m1, m2 >> n) and will use cor.fk for fast computation. By default (set FALSE), Kendall embedding is explicitly computed; otherwise kernel trick is explored.
kmat	Kendall kernel matrix of dimension m1 x m2, correlation type correponding to "type". If given, kernel trick is explored directly.
type	A character string indicating the type of Kendall correlation for "kmat".
mc	A normalization constant default to 0.25 such that output normalized squared Euclidean distance in the feature space induced by Kendall embedding amounts exactly to Kendall distances.

Value

A matrix of dimension m1 x m2 where entry [i,j] is the distance from sequence i in "r" to sequence j in "seqs".

Note

Kernel trick is explored in the sense that "r" and "seq" are only used for checking dimensions and getting attributes but not used explicitly to compute the distance. Option "use.kernel.trick" set TRUE or FALSE may give slightly different results due to computation precision of two implementations.

Author(s)

Yunlong Jiao

References

Kendall's tau rank correlation coefficient: https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient

Yunlong Jiao, Jean-Philippe Vert. "The Kendall and Mallows Kernels for Permutations." IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 40, no. 7, pp. 1755-1769, 2018. DOI:10.1109/TPAMI.2017.2719680

See Also

KendallInfo, cor.fk

Examples

#### Ex 1: Compute Kendall distance matrix and Mallows kernel matrix
data1 <- do.call("rbind", list(1:5, 5:1, c(3, 2, 1, 4, 5)))
data2 <- do.call("rbind", list(1:5, 5:1))

# Kendall distance matrix
s.K.d.mat <- AllKendall(data1, data2)

# Mallows kernel matrix with dispersion parameter lambda
lambda <- 0.1
M.k.kmat <- exp(-lambda * s.K.d.mat)

#### Ex 2: Why kernel trick?
r <- lapply(1:20, function(i) sample.int(1000, replace = TRUE))
r <- do.call('rbind', r)
dim(r)

# I) Without kernel trick
pt <- proc.time()
dmat1 <- AllKendall(r, use.kernel.trick = FALSE)
proc.time() - pt

# II) With kernel trick (should be much faster in this setting)
require(pcaPP)
pt <- proc.time()
dmat2 <- AllKendall(r, use.kernel.trick = TRUE)
proc.time() - pt

# NOTE: dmat1 and dmat2 may return slightly different values due to computation precision
isTRUE(all.equal(dmat1, dmat2, check.attributes = FALSE)) # May sometimes output FALSE
isTRUE(max(abs(dmat1 - dmat2)) < 1e-6) # Should always output TRUE

YunlongJiao/kernrank documentation built on May 10, 2019, 1:13 a.m.