Title: No title found

Abstract: We present a new methodology that constructs a family of positive definite kernels from any given dissimilarity measure on structured inputs whose elements are either real-valued time series or discrete structures such as strings, histograms, and graphs. Our approach, which we call D2KE (from Distance to Kernel and Embedding), draws from the literature of Random Features. However, instead of deriving random feature maps from a user-defined kernel to approximate kernel machines, we build a kernel from a random feature map, that we specify given the distance measure. We further propose use of a finite number of random objects to produce a random feature embedding of each instance. We provide a theoretical analysis showing that D2KE enjoys better generalizability than universal Nearest-Neighbor estimates. On one hand, D2KE subsumes the widely-used representative-set method as a special case, and relates to the well-known distance substitution kernel in a limiting case. On the other hand, D2KE generalizes existing Random Features methods applicable only to vector input representations to complex structured inputs of variable sizes. We conduct classification experiments over such disparate domains as time series, strings, and histograms (for texts and images), for which our proposed framework compares favorably to existing distance-based learning methods in terms of both testing accuracy and computational time.
Distance-Based Kernel Learning. Existing approaches either require strict conditions on the distance function (e.g. that the distance be isometric to the square of the Euclidean distance) (Haasdonk & Bahlmann, 2004; Schölkopf, 2001) , or construct empirical PD Gram matrices that do not necessarily generalize to the test samples (Pekalska et al., 2001; Pkkalska & Duin, 2005; Pekalska & Duin, 2006; 2008; Duin & P ękalska, 2012) . Haasdonk & Bahlmann (2004) and Schölkopf (2001) provide conditions under which one can obtain a PD kernel through simple transformations of the distance measure, but which are not satisfied for many commonly used dissimilarity measures such as Dynamic Time Warping, Hausdorff distance, and Earth Mover's distance (Haasdonk & Bahlmann,
1A generalization error bound was provided for the similarity-as-kernel approach in (Chen et al., 2009a), but only for a positive-definite similarity function.

1. I:

In many problem domains, it is easier to specify a reasonable dissimilarity (or similarity) function between instances than to construct a feature representation. This is particularly the case with structured inputs whose elements are either real-valued time series or discrete structures such as strings, histograms, and graphs, where it is typically less than clear how to construct the representation of entire structured inputs with potentially widely varying sizes, even when given a good feature representation of each individual component. Moreover, even for complex structured inputs, there are many well-developed dissimilarity measures, such as the Dynamic Time Warping measure between time series, Edit Distance between strings, Hausdorff distance between sets, and Wasserstein distance between distributions. However, standard machine learning methods are designed for vector representations, and classically there has been far less work on distance-based methods for either classification or regression on structured inputs. The most common distance-based method is Nearest-Neighbor Estimation (NNE), which predicts the outcome for an instance using an average of its nearest neighbors in the input space, with nearness measured by the given dissimilarity measure. Estimation from nearest neighbors, however, is unreliable, specifically having high variance when the neighbors are far apart, which is typically the case when the intrinsic dimension implied by the distance is large.

To address this issue, a line of research has focused on developing global distance-based (or similaritybased) machine learning methods (Pkkalska & Duin, 2005; Duin & P ękalska, 2012; Balcan et al., 2008a; Cortes et al., 2012) , in large part by drawing upon connections to kernel methods (Scholkopf et al., 1999) or directly learning with similarity functions (Balcan et al., 2008a; Cortes et al., 2012; Balcan et al., 2008b; Loosli et al., 2016) ; we refer the reader in particular to the survey in (Chen et al., 2009a) . Among these, the most direct approach treats the data similarity matrix (or transformed dissimilarity matrix) as a kernel Gram matrix, and then uses standard kernel-based methods such as Support Vector Machines (SVM) or kernel ridge regression with this Gram matrix. A key caveat with this approach however is that most similarity (or dissimilarity) measures do not provide a positive-definite (PD) kernel, so that the empirical risk minimization problem is not well-defined, and moreover becomes non-convex (Ong et al., 2004; Lin & Lin, 2003) .

A line of work has therefore focused on estimating a positive-definite (PD) Gram matrix that merely approximates the similarity matrix. This could be achieved for instance by clipping, or flipping, or shifting eigenvalues of the similarity matrix (Pekalska et al., 2001) , or explicitly learning a PD approximation of the similarity matrix (Chen & Ye, 2008; Chen et al., 2009b) . Such modifications of the similarity matrix however often leads to a loss of information; moreover, the enforced PD property is typically guaranteed to hold only on the training data, resulting in an inconsistency between the set of testing and training samples (Chen et al., 2009a) 1.

Another common approach is to select a subset of training samples as a held-out representative set, and use distances or similarities to structured inputs in the set as the feature function (Graepel et al., 1999; Pekalska et al., 2001) . As we will show, with proper scaling, this approach can be interpreted as a special instance of our framework. Furthermore, our framework provides a more general and richer family of kernels, many of which significantly outperform the representative-set method in a variety of application domains.

To address the aforementioned issues, in this paper, we propose a novel general framework that constructs a family of PD kernels from a dissimilarity measure on structured inputs. Our approach, which we call D2KE (from Distance to Kernel and Embedding), draws from the literature of Random Features (Rahimi & Recht, 2008) , but instead of deriving feature maps from an existing kernel for approximating kernel machines, we build novel kernels from a random feature map specifically designed for a given distance measure. The kernel satisfies the property that functions in the corresponding Reproducing Kernel Hilbert Space (RKHS) are Lipschitz-continuous w.r.t. the given distance measure. We also provide a tractable estimator for a function from this RKHS which enjoys much better generalization properties than nearest-neighbor estimation. Our framework produces a feature embedding and consequently a vector representation of each instance that can be employed by any classification and regression models. In classification experiments in such disparate domains as strings, time series, and histograms (for texts and images), our proposed framework compares favorably to existing distance-based learning methods in terms of both testing accuracy and computational time, especially when the number of data samples is large and/or the size of structured inputs is large.

We highlight our main contributions as follows:

• From the perspective of distance kernel learning, we propose for the first time a methodology that constructs a family of PD kernels via Random Features from a given distance measure for structured inputs, and provide theoretical and empirical justifications for this framework.

• From the perspective of Random Features (RF) methods, we generalize existing Random Features methods applied only to vector input representations to complex structured inputs of variable sizes. To the best of our knowledge, this is the first time that a generic RF method has been used to accelerate kernel machines on structured inputs across a broad range of domains such as time-series, strings, and the histograms. 

2004:

). Equivalently, one could also find a Euclidean embedding (also known as dissimilarity representation) approximating the dissimilarity matrix as in Multidimensional Scaling (Pekalska et al., 2001; Pkkalska & Duin, 2005; Pekalska & Duin, 2006; 2008; Duin & P ękalska, 2012) 2. Differently, Loosli et al. (2016) presented a theoretical foundation for an SVM solver in Krein spaces and directly evaluated a solution that uses the original (indefinite) similarity measure.

There are also some specific approaches dedicated to building a PD kernel on some structured inputs such as text and time-series (Collins & Duffy, 2002; Cuturi, 2011) , that modify a distance function over sequences to a kernel by replacing the minimization over possible alignments into a summation over all possible alignments. This type of kernel, however, results in a diagonal-dominance problem, where the diagonal entries of the kernel Gram matrix are orders of magnitude larger than the off-diagonal entries, due to the summation over a huge number of alignments with a sample itself.

Random Features Methods.:

Interest in approximating non-linear kernel machines using randomized feature maps has surged in recent years due to a significant reduction in training and testing times for kernel based learning algorithms (Dai et al., 2014) . There are numerous explicit nonlinear random feature maps that have been constructed for various types of kernels, including Gaussian and Laplacian Kernels (Rahimi & Recht, 2008; Wu et al., 2016) , intersection kernels (Maji & Berg, 2009) , additive kernels Vedaldi & Zisserman (2012) , dot product kernels (Kar & Karnick, 2012; Pennington et al., 2015) , and semigroup kernels (Mukuta et al., 2018) . Among them, the Random Fourier Features (RFF) method, which approximates a Gaussian Kernel function by means of multiplying the input with a Gaussian random matrix, and its fruitful variants have been extensively studied both theoretically and empirically (Sriperumbudur & Szabó, 2015; Felix et al., 2016; Rudi & Rosasco, 2017; Bach, 2017; Choromanski et al., 2018) . To accelerate the RFF on input data matrix with high dimensions, a number of methods have been proposed to leverage structured matrices to allow faster matrix computation and less memory consumption (Le et al., 2013; Hamid et al., 2014; Choromanski & Sindhwani, 2016) .

However, all the aforementioned RF methods merely consider inputs with vector representations, and compute the RF by a linear transformation that is either a matrix multiplication or an inner product under Euclidean distance metric. In contrast, D2KE takes structured inputs of potentially different sizes and computes the RF with a structured distance metric (typically with dynamic programming or optimal transportation). Another important difference between D2KE and existing RF methods lies in the fact that existing RF work assumes a user-defined kernel and then derives a randomfeature map, while D2KE constructs a new PD kernel through a random feature map and makes it computationally feasible via RF. The table 1 lists the differences between D2KE and existing RF methods.

A very recent piece of work (Wu et al., 2018) has developed a kernel and a specific algorithm for computing embeddings of single-variable real-valued time-series. However, despite promising results, this method cannot be applied on discrete structured inputs such as strings, histograms, and graphs. In contrast, we have an unified framework for various structured inputs beyond the limits of (Wu et al., 2018) and provide a general theoretical analysis w.r.t KNN and other generic distance-based kernel methods.

3. P S:

We consider the estimation of a target function f : X → R from a collection of samples {(x i , y i )} n i=1 , where x i ∈ X is the structured input object, and y i ∈ Y is the output observation associated with the target function f (x i ). For instance, in a regression problem, y i ∼ f (x i ) + ω i ∈ R for some random noise ω i , and in binary classification, we have y i ∈ {0, 1} with P(y i = 1|x i ) = f (x i ). We are given a dissimilarity measure d : X × X → R between input objects instead of a feature representation of x.

2A proof of the equivalence between PD of similarity matrix and Euclidean of dissimilarity matrix can be found in (Borg & Groenen, 1997) .

Note that the size structured inputs x i may vary widely, e.g. strings with variable lengths or graphs with different sizes. For some of the analyses, we require the dissimilarity measure to be a metric as follows.

Assumption 1 (Distance Metric). d : X × X → R is a distance metric, that is, it satisfies (i) d(x 1 , x 2 ) ≥ 0, (ii) d(x 1 , x 2 ) = 0 ⇐⇒ x 1 = x 2 , (iii) d(x 1 , x 2 ) = d(x 2 , x 1 ), and (iv) d(x 1 , x 2 ) ≤ d(x 1 , x 3 ) + d(x 3 , x 2 ). 3.1 F C S C

An ideal feature representation for the learning task is (i) compact and (ii) such that the target function f (x) is a simple (e.g. linear) function of the resulting representation. Similarly, an ideal dissimilarity measure d(x 1 , x 2 ) for learning a target function f (x) should satisfy certain properties. On one hand, a small dissimilarity d(x 1 , x 2 ) between two objects should imply small difference in the function values | f (x 1 )f (x 2 )|. On the other hand, we want a small expected distance among samples, so that the data lies in a compact space of small intrinsic dimension. We next build up some definitions to formalize these properties. Assumption 2 (Lipschitz Continuity). For any x 1 , x 2 ∈ X, there exists some constant

EQUATION

We would prefer the target function to have a small Lipschitz-continuity constant L with respect to the dissimilarity measure d(., .). Such Lipschitz-continuity alone however might not suffice. For example, one can simply set d(x 1 , x 2 ) = ∞ for any x 1 x 2 to satisfy Eq. equation 1. We thus need the following quantity that measures the size of the space implied by a given dissimilarity measure.

Definition 1 (Covering Number). Assuming d is a metric. A δ-cover of X w.r.t. d(., .) is a set E s.t. ∀x ∈ X, ∃x i ∈ E, d(x, x i ) ≤ δ.

Then the covering number N(δ; X, d) is the size of the smallest δ-cover for Xwith respect to d.

Assuming the input domain X is compact, the covering number N(δ; X, d) measures its size w.r.t. the distance measure d. We show how the two quantities defined above affect the estimation error of a Nearest-Neighbor Estimator.

3.2. E D N N E:

We extend the standard analysis of the estimation error of k-nearest-neighbor from finite-dimensional vector spaces to any structured input space X, with an associated distance measure d, and a finite covering number N(δ; X, d), by defining the effective dimension as follows.

Assumption 3 (Effective Dimension). Let the effective dimension p X,d > 0 be the minimum p satisfying

∃c > 0, ∀δ : 0 < δ < 1, N(δ; X, d) ≤ c 1 δ p .

Here we provide an example of effective dimension in case of measuring the space of Multiset.

Multiset with Hausdorff Distance. A multiset is a set that allows duplicate elements. Consider two multisets

x 1 = {u i } M i=1 , x 2 = {v j } N j=1 . Let ∆(u i , v j

) be a ground distance that measures the distance between two elements u i , v j ∈ V in a set. The (modified) Hausdorff Distance (Dubuisson & Jain, 1994 ) can be defined as

EQUATION

Let N(δ; V, ∆) be the covering number of V under the ground distance ∆. Let X denote the set of all sets of size bounded by L. By constructing a covering of X containing any set of size less or equal than L with its elements taken from the covering of V, we have

N(δ; X, d) ≤ N(δ; V; ∆) L . Therefore, p X,d ≤ L log N(δ; V, ∆). For example, if V := {v ∈ R p | v 2 ≤ 1} and ∆ is Euclidean distance, we have N(δ; V, ∆) = (1 + 2 δ ) p and p X,d ≤ Lp.

Equipped with the concept of effective dimension, we can obtain the following bound on the estimation error of the k-Nearest-Neighbor estimate of f (x).

Theorem 1. Let V ar(y| f (x)) ≤ σ 2 , and fn be the k-Nearest Neighbor estimate of the target function f constructed from a training set of size n. Denote p := p X,d . We have

E x fn (x) -f (x) 2 ≤ σ 2 k + cL 2 k n 2/p

for some constant c > 0. For σ > 0, minimizing RHS w.r.t. the parameter k, we have

E x fn (x) -f (x) 2 ≤ c 2 σ 4 p+2 L 2p 2+p 1 n 2 2+p

(3)

for some constant c 2 > 0.

Proof. The proof is almost the same to a standard analysis of k-NN's estimation error in, for example, (Györfi et al., 2006) , with the space partition number replaced by the covering number, and dimension replaced by the effective dimension in Assumption 3.

When p X,d is reasonably large, the estimation error of k-NN decreases quite slowly with n. Thus, for the estimation error to be bounded by , requires the number of samples to scale exponentially in p X,d . In the following sections, we develop an estimator f based on a RKHS derived from the distance measure, with a considerably better sample complexity for problems with higher effective dimension.

4. F D K S I:

We aim to address the long-standing problem of how to convert a distance measure into a positivedefinite kernel. Here we introduce a simple but effective approach D2KE that constructs a family of positive-definite kernels from a given distance measure. Given an structured input domain X and a distance measure d(., .), we construct a family of kernels as

EQUATION

where ω ∈ Ω is a random structured object whose elements could be real-valued time-series, strings, and histograms, p(ω) is a distribution over Ω, and φ ω (x) is a feature map derived from the distance of x to all random objects ω ∈ Ω. The kernel is parameterized by both p(ω) and γ.

Relationship to Distance Substitution Kernel. An insightful interpretation of the kernel in Equation ( 4) can be obtained by expressing the kernel in Equation (4) as

exp -γsoftmin p(ω) {d(x, ω) + d(ω, y)} (5)

where the soft minimum function, parameterized by p(ω) and γ, is defined as

EQUATION

Therefore, the kernel k(x, y) can be interpreted as a soft version of the distance substitution kernel (Haasdonk & Bahlmann, 2004) , where instead of substituting d(x, y) into the exponent, it substitutes a soft version of the form softmin p(ω) {d(x, ω) + d(ω, y)}.

Note when γ → ∞, the value of Equation ( 7) is determined by min ω ∈Ω d(x, ω) + d(ω, y), which equals d(x, y) if X ⊆ Ω, since it cannot be smaller than d(x, y) by the triangle inequality. In other words, when X ⊆ Ω, k(x, y) → exp(-γd(x, y)) as γ → ∞.

On the other hand, unlike the distance-substituion kernel, our kernel in Equation ( 5) is always PD by construction.

Algorithm 1 Random Feature Approximation of function in RKHS with the kernel in Equation 41: Draw R samples from p(ω) to get {ω j } R j=1 . 2: Set the R-dimensional feature embedding as

φj (x) = 1 √ R exp(-γd(x, ω j )), ∀ j ∈ [R]

3: Solve the following problem for some µ > 0:

ŵ := argmin w ∈R R 1 n n i=1 (w T φ(x i ), y i ) + µ 2 w 2

4: Output the estimated function fR (x) := ŵT φ(x).

Random Feature Approximation. The reader might have noticed that the kernel in Equation ( 4) cannot be evaluated analytically in general. However, this does not prohibit its use in practice, so long as we can approximate it via Random Features (RF) (Rahimi & Recht, 2008) , which in our case is particularly natural as the kernel itself is defined via a random feature map. Thus, our kernel with the RF approximation can not only be used in small problems but also in large-scale settings with a large number of samples, where standard kernel methods with O(n 2 ) complexity are no longer efficient enough and approximation methods, such as Random Features, must be employed (Rahimi & Recht, 2008) . Given the RF approximation, one can then directly learn a target function as a linear function of the RF feature map, by minimizing a domain-specific empirical risk. It is worth noting that a recent work (Sinha & Duchi, 2016 ) that learns to select a set of random features by solving an optimization problem in an supervised setting is orthogonal to our D2KE approach and could be extended to develop a supervised D2KE method. We outline this overall RF based empirical risk minimization for our class of D2KE kernels in Algorithm 1. It is worth pointing out that in line 2 of Algorithm 1 the random feature embeddings are computed by a structured distance measure between the original structured inputs and the generated random structured inputs, followed by the application of the exponent function parameterized by γ. This is in contrast with traditional RF methods that translate the input data matrix into the embedding matrix via a matrix multiplication with random Gaussian matrix followed by a non-linearity. We will provide a detailed analysis of our estimator in Algorithm 1 in Section 5, and contrast its statistical performance to that of K-nearest-neighbor.

Relationship to Representative-Set Method. A naive choice of p(ω) relates our approach to the representative-set method (RSM): setting Ω = X, with p(ω) = p(x). This gives us a kernel Equation (4) that depends on the data distribution. One can then obtain a Random-Feature approximation to the kernel in Equation ( 4) by holding out a part of the training data { xj } R j=1 as samples from p(ω), and creating an R-dimensional feature embedding of the form:

EQUATION

as in Algorithm 1. This is equivalent to a 1/ √ R-scaled version of the embedding function in the representative-set method (or similarity-as-features method) (Graepel et al., 1999; Pekalska et al., 2001; Pkkalska & Duin, 2005; Pekalska & Duin, 2006; 2008; Chen et al., 2009a; Duin & P ękalska, 2012) , where one computes each sample's similarity to a set of representatives as its feature representation. However, here by interpreting Equation (8) as a random-feature approximation to the kernel in Equation (4), we obtain a much nicer generalization error bound even in the case R → ∞. This is in contrast to the analysis of RSM in (Chen et al., 2009a) , where one has to keep the size of the representative set small (of the order O(n)) in order to have reasonable generalization performance.

Effect of p(ω).:

The choice of p(ω) plays an important role in our kernel. Surprisingly, we found that many "close to uniform" choices of p(ω) in a variety of domains give better performance than for instance the choice of the data distribution p(ω) = p(x) (as in the representative-set method). Here are some examples from our experiments: i) In the time-series domain with dissimilarity computed via Dynamic Time Warping (DTW), a distribution p(ω) corresponding to random time series of length uniform in ∈ [2, 10], and with Gaussian-distributed elements, yields much better performance than the Representative-Set Method (RSM); ii) In string classification, with edit distance, a distribution p(ω) corresponding to random strings with elements uniformly drawn from the alphabet Σ yields much better performance than RSM; iii) When classifying sets of vectors with the Hausdorff distance in Equation (2), a distribution p(ω) corresponding to random sets of size uniform in ∈ [3, 15] with elements drawn uniformly from a unit sphere yields significantly better performance than RSM.

We conjecture two potential reasons for the better performance of the chosen distributions p(ω) in these cases, though a formal theoretical treatment is an interesting subject we defer to future work. Firstly, as p(ω) is synthetic, one can generate unlimited number of random features, which results in a much better approximation to the exact kernel in Equation (4). In contrast, RSM requires held-out samples from the data, which could be quite limited for a small data set. Second, in some cases, even with a small or similar number of random features to RSM, the performance of the selected distribution still leads to significantly better results. For those cases we conjecture that the selected p(ω) generates objects that capture semantic information more relevant to the estimation of f (x), when coupled with our feature map under the dissimilarity measure d(x, ω).

5. A:

In this section, we analyze the proposed framework from the perspectives of error decomposition. Let H be the RKHS corresponding to the kernel in Equation ( 4). Let

f C := argmin f ∈H E[ ( f (x), y)] s.t. f H ≤ C (9)

be the population risk minimizer subject to the RKHS norm constraint f H ≤ C. And let

EQUATION

be the corresponding empirical risk minimizer. In addition, let fR be the estimated function from our random feature approximation (Algorithm 1). Then denote the population and empirical risks as L( f ) and L( f ) respectively. We have the following risk decomposition L( fR

) -L( f ) = (L( fR ) -L( fn ))

r andom f eature

+ (L( fn ) -L( f C )) estimation + (L( f C ) -L( f )) approximation

In the following, we will discuss the three terms from the rightmost to the leftmost.

Function Approximation:

Error. The RKHS implied by the kernel in Equation ( 4) is

H :=      f f (x) = m j=1 α j k(x j , x), x j ∈ X, ∀ j ∈ [m], m ∈ N     

, which is a smaller function space than the space of Lipschitz-continuous function w.r.t. the distance d(x 1 , x 2 ). As we show, any function f ∈ H is Lipschitz-continous w.r.t. the distance d(., .). Proposition 1. Let H be the RKHS corresponding to the kernel in Equation ( 4) derived from some metric d(., .).

For any f ∈ H , | f (x 1 ) -f (x 2 )| ≤ L f d(x 1 , x 2 )

where L f = γC.

We refer readers to the detailed proof in Appendix A.1. While any f in the RKHS is Lipschitzcontinuous w.r.t. the given distance d(., .), we are interested in imposing additional smoothness via the RKHS norm constraint f H ≤ C, and by the kernel parameter γ. The hope is that the best function f C within this class approximates the true function f well in terms of the approximation error L( f C ) -L( f ). The stronger assumption made by the RKHS gives us a qualitatively better estimation error, as discussed below.

Estimation Error. Define D λ as

D λ := ∞ j=1 1 1 + λ/µ j where {µ j } ∞

j=1 is the eigenvalues of the kernel in Equation ( 5) and λ is a tuning parameter. It holds that for any λ ≥ D λ /n, with probability at least 1 -δ, L( fn ) -L( f C ) ≤ c(log 1 δ ) 2 C 2 λ for some universal constant c (Zhang, 2005) . Here we would like to set λ as small as possible (as a function of n). By using the following kernel-independent bound: D λ ≤ 1/λ, we have λ = 1/ √ n and thus a bound on the estimation error

EQUATION

)

The estimation error is quite standard for a RKHS estimator. It has a much better dependency w.r.t. n (i.e. n -1/2 ) compared to that of k-nearest-neighbor method (i.e. n -2/(2+p X, d ) ) especially for higher effective dimension. A more careful analysis might lead to tighter bound on D λ and also a better rate w.r.t. n. However, the analysis of D λ for our kernel in Equation ( 4) is much more difficult than that of typical cases as we do not have an analytic form of the kernel.

Random Feature Approximation. Denote L(.) as the empirical risk function. The error from RF approximation L( fR ) -L( fn ) can be further decomposed as

(L( fR ) -L( fR )) + ( L( fR ) -L( fn )) + ( L( fn ) -L( fn ))

where the first and third terms can be bounded via the same estimation error bound in Equation ( 11), as both fR and fn have RKHS norm bounded by C. Therefore, in the following, we focus only on the second term of empirical risk. We start by analyzing the approximation error of the kernel

EQUATION

) Proposition 2. Let ∆ R (x 1 , x 2 ) = k(x 1 , x 2 ) -k(x 1 ,

x 2 ), we have uniform convergence of the form

P max x 1 ,x 2 ∈X |∆ R (x 1 , x 2 )| > 2t ≤ 2 12γ t 2p X, d e -Rt 2 /2 ,

where p X,d is the effective dimension of X under metric d(., .). In other words, to guarantee |∆ R (x 1 , x 2 )| ≤ with probability at least 1 -δ, it suffices to have

R = Ω p X,d 2 log( γ ) + 1 2 log( 1 δ ) .

We refer readers to the detailed proof in Appendix A.2. Proposition 2 gives an approximation error in terms of kernel evaluation. To get a bound on the empirical risk L( fR ) -L( fn ), consider the optimal solution of the empirical risk minimization. By the Representer theorem we have fn

(x) = 1 n i α i k(x i , x) and fR (x) = 1 n i αi k(x i , x)

. Therefore, we have the following corollary. Corollary 1. To guarantee L( fR ) -L( fn ) ≤ , with probability 1 -δ, it suffices to have

R = Ω p X,d M 2 A 2 2 log( γ ) + M 2 A 2 2 log( 1 δ ) .

where M is the Lipschitz-continuous constant of the loss function (., y), and A is a bound on α 1 /n.

We refer readers to the detailed proof in Appendix A.3. For most of loss functions, A and M are typically small constants. Therefore, Corollary 1 states that it suffices to have number of Random Features proportional to the effective dimension O(p X,d / 2 ) to achieve an approximation error.

Combining the three error terms, we can show that the proposed framework can achieve -suboptimal performance.

Claim 1. Let fR be the estimated function from our random feature approximation based ERM estimator in Algorithm 1, and let f * denote the desired target function. Suppose further that for some absolute constants c 1 , c 2 > 0 (up to some logarithmic factor of 1/ and 1/δ):

1. The target function f * lies close to the population risk minimizer f C lying in the RKHS spanned by the D2KE kernel:

L( f C ) -L( f ) ≤ /2.

2.. The number of training samples:

n ≥ c 1 C 4 / 2 .

3. The number of random features R ≥ c 2 p X,d / 2 .

We then have that: L( fR ) -L( f * ) ≤ with probability 1 -δ.

6. E:

We evaluate the proposed method in four different domains involving time-series, strings, texts, and images. First, we discuss the dissimilarity measures and data characteristics for each set of experiments. Then we introduce comparison among different distance-based methods and report corresponding results.

Distance Measures. We have chosen three well-known dissimilarity measures: 1) Dynamic Time Warping (DTW), for time-series (Berndt & Clifford, 1994) ; 2) Edit Distance (Levenshtein distance), for strings (Navarro, 2001) ; 3) Earth Mover's distance (Rubner et al., 2000) for measuring the semantic distance between two Bags of Words (using pretrained word vectors), for representing documents. 4) (Modified) Hausdorff distance (Huttenlocher et al., 1993; Dubuisson & Jain, 1994) for measuring the semantic closeness of two Bags of Visual Words (using SIFT vectors), for representing images. Note that Bag of (Visual) Words in 3) and 4) can also be regarded as a histogram. Since most distance measures are computationally demanding, having quadratic complexity, we adapted or implemented C-MEX programs for them; other codes were written in Matlab.

Datasets.:

For each domain, we selected 4 datasets for our experiments. For time-series data, all are multivariate time-series and the length of each time-series varies from 2 to 205 observations; three are from the UCI Machine Learning repository (Frank & Asuncion, 2010) , the other is generated from the IQ (In-phase and Quadrature components) samples from a wireless line-of-sight communication system from GMU. For string data, the size of alphabet is between 4 and 8 and the length of each string ranges from 34 to 198; two of them are from the UCI Machine Learning repository and the other two from the LibSVM Data Collection (Chang & Lin, 2011) . For text data, all are chosen partially overlapped with these in (Kusner et al., 2015) . The length of each document varies from 9.9 to 117. For image data, all of datasets were derived from Kaggle; we computed a set of SIFTdescriptors to represent each image and the size of SIFT feature vectors of each image varies from 1 to 914. We divided each dataset into 70/30 train and test subsets (if there was no predefined train/test split). Properties of these datasets are summarized in Table 6 in Appendix B. Baselines. We compare D2KE against 5 state-of-the-art baselines, including 1) KNN: a simple yet universal method to apply any distance measure to classification tasks; 2) DSK_RBF (Haasdonk & Bahlmann, 2004 ): distance substitution kernels, a general framework for kernel construction by substituting a problem specific distance measure in ordinary kernel functions. We use a Gaussian RBF kernel; 3) DSK_ND (Haasdonk & Bahlmann, 2004) : another class of distance substitution kernels with negative distance; 4) KSVM (Loosli et al., 2016) : learning directly from the similarity (indefinite) matrix followed in the original Krein Space; 5) RSM (Pekalska et al., 2001) : building an embedding by computing distances from randomly selected representative samples.

Among these baselines, KNN, DSK_RBF, DSK_ND, and KSVM have quadratic complexity O(N 2 L 2 ) in both the number of data samples and the length of the sequences, while RSM has computational complexity O(N RL 2 ), linear in the number of data samples but still quadratic in the length of the sequence. These compare to our method, D2KE, which has complexity O(N RL), linear in both the number of data samples and the length of the sequence. For each method, we search for the best parameters on the training set by performing 10-fold cross validation. For our new method D2KE, since we generate random samples from the distribution, we can use as many as needed to achieve performance close to an exact kernel. We report the best number in the range R = [4, 4096] (typically the larger R is, the better the accuracy). We employ a linear SVM implemented using LIBLINEAR (Fan et al., 2008) for all embedding-based methods (RSM and D2KE) and use LIBSVM (Chang & Lin, 2011) for precomputed dissimilairty kernels (DSK_RBF, DSK_ND, and KSVM). More details of experimental setup are provided in Appendix B.

Results.:

As shown in Tables 2, 3 , 4, and 5, D2KE can consistently outperform or match the baseline methods in terms of classification accuracy while requiring far less computation time.

There are several observations worth making here. First, D2KE performs much better than KNN, supporting our claim that D2KE can be a strong alternative to KNN across applications. Second, compared to the two distance substitution kernels DSK_RBF and DSK_ND and the KSVM method operating directly on indefinite similarity matrix, our method can achieve much better performance, suggesting that a representation induced from a truly PD kernel makes significantly better use of the data than indefinite kernels. Among all methods, RSM is closest to our method in terms of practical construction of the feature matrix. However, the random objects (time-series, strings, or sets) sampled by D2KE perform significantly better, as we discussed in section 4. More detailed discussions of the experimental results for each domain are given in Appendix C.

7. C F W:

In this work, we have proposed a general framework for deriving a positive-definite kernel and a feature embedding function from a given dissimilarity measure between input objects. The framework is especially useful for structured input domains such as sequences, time-series, and sets, where many well-established dissimilarity measures have been developed. Our framework subsumes at least two existing approaches as special or limiting cases, and opens up what we believe will be a useful new direction for creating embeddings of structured objects based on distance to random objects. A promising direction for extension is to develop such distance-based embeddings within a deep architecture to support use of structured inputs in an end-to-end learning system.

A P T 1 T 2

A.1 P T 1

Proof. Note the function g(t) = exp(-γt) is Lipschitz-continuous with Lipschitz constant γ. Therefore,

| f (x 1 ) -f (x 2 )| = | f , φ(x 1 ) -φ(x 2 ) | ≤ f H φ(x 1 ) -φ(x 2 ) H = f H ∫ ω p(ω)(φ ω (x 1 ) -φ ω (x 2 )) 2 dω ≤ f H ∫ ω p(ω)γ 2 |d(x 1 , ω) -d(x 2 , ω)| 2 dω ≤ γ f H ∫ ω p(ω)d(x 1 , x 2 ) 2 dω ≤ γ f H d(x 1 , x 2 ) ≤ γCd(x 1 , x 2 ) A.2 P T 2 Proof. Our goal is to bound the magnitude of ∆ R (x 1 , x 2 ) = kR (x 1 , x 2 ) -k(x 1 , x 2 ). Since E[∆ R (x 1 , x 2 )] = 0 and |∆ R (x 1 , x 2 )| ≤ 1, from

Hoefding's inequality, we have

P {|∆ R (x 1 , x 2 )| ≥ t} ≤ 2 exp(-Rt 2 /2)

a given input pair (x 1 , x 2 ). To get a unim bound that holds ∀(x 1 , x 2 ) ∈ X × X, we find an -covering E of X w.r.t. d(., .) of size N( , X, d). Applying union bound over the -covering E for x 1 and x 2 , we have P max

EQUATION

Then by the definition of E we have |d(x 1 , ω)d(x 1 , ω)| ≤ d(x 1 , x 1 ) ≤ . Together with the fact that exp(-γt) is Lipschitz-continuous with parameter γ for t ≥ 0, we have

|φ ω (x 1 ) -φ ω (x 1 )| ≤ γ and thus | kR (x 1 , x 2 ) -kR (x 1 , x 2 )| ≤ 3γ , |k(x 1 , x 2 ) -k(x 1 , x 2 )| ≤ 3γ

for γ chosen to be ≤ 1. This gives us

EQUATION

Combining equation 13 and equation 14, we have

EQUATION

Choosing = t/6γ yields the result.

A.3 P C 1:

Proof. First of all, we have

1 n n i=1 ( 1 n n j=1 αj k(x j , x i ), y i ) ≤ 1 n n i=1 ( 1 n n j=1 α j k(x j , x i ), y i )

by the optimality of { αj } n j=1 w.r.t. the objective using the approximate kernel. Then we have L( fR ) -L( fn

) ≤ 1 n n i=1 ( 1 n n j=1 α j k(x j , x i ), y i ) -( 1 n n j=1 α j k(x j , x i ), y i ) ≤ M α 1 n max x 1 ,x 2 ∈X | k(x 1 , x 2 ) -k(x 1 , x 2 )| ≤ M A max x 1 ,x 2 ∈X | k(x 1 , x 2 ) -k(x 1 , x 2 )|

where A is a bound on α 1 /n. Therefore to guarantee

L( fR ) -L( fn ) ≤ we would need max i, j ∈[n] |∆ R (x 1 , x 2 )| ≤ ˆ := /M A.

Then applying Theorem 2 leads to the result.

B G E S General Setup. For each method, we search for the best parameters on the training set by performing 10-fold cross validation. Following (Haasdonk & Bahlmann, 2004) , we use an exact RBF kernel for DSK_RBF while choosing squared distance for DSK_ND. We use the Matlab implementation provided by Loosli et al. (2016) to run experiments for KSVM. Similarly, we adopted a simple method -random selection -to obtain R = [4, 512] data samples as the representative set for RSM (Pekalska et al., 2001) . For our new method D2KE, since we generate random samples from the distribution, we can use as many as needed to achieve performance close to an exact kernel. We report the best number in the range R = [4, 4096] (typically the larger R is, the better the accuracy). We employ a linear SVM implemented using LIBLINEAR (Fan et al., 2008) for all embedding-based methods (RSM, and D2KE) and use LIBSVM (Chang & Lin, 2011) for precomputed dissimilairty kernels (DSK_RBF, DSK_ND, and KSVM).

All datasets are collected from popular public websites for Machine Learning and Data Science research, including the UCI Machine Learning repository (Frank & Asuncion, 2010) , the LibSVM Data Collection (Chang & Lin, 2011) , and the Kaggle Datasets, except one time-series dataset IQ that is shared from researchers from George Mason University. The first interesting observation is that our method performs substantially better than KNN, often by a large margin, i.e., D2KE achieves 26.62% higher performance than KNN on IQ_radio. This is because KNN is sensitive to the data noise common in real-world applications like IQ_radio, and has notoriously poor performance for high-dimensional data sets like Auslan. Moreover, compared to the two distance substitution kernels DSK_RBF and DSK_ND, and KSVM operating directly on indefinite similarity matrix, our method can achieve much better performance, suggesting that a representation induced from a truly p.d. kernel makes significantly better use of the data than indefinite kernels. Among all methods, RSM is closest to our method in terms of practical construction of the feature matrix. However, the random time series sampled by D2KE performs significantly better, as we discussed in section 4. First, RSM simply chooses a subset of the original data points and computes the distances between the whole dataset and this representative set; this may suffer significantly from noise or redundant information in the time-series. In contrast, our method samples a short random sequence that could both denoise and find the patterns in the data. Second, the number of data points that can be sampled is limited by the total size of the data while the number of possible random sequences drawn from the distribution is unlimited, making the feature space much more abundant. Third, RSM may incur significant computational cost for long time-series, due to its quadratic complexity in length.

C.2 R:

Setup. For string data, there are various well-known edit distances. Here, we choose Levenshtein distance as our distance measure since it can capture global alignments of the underlying strings. We first compute the alphabet from the original data and then uniformly sample characters from this alphabet to generate random strings. We search for the best parameters for γ in the range [1e-5 1], and for the length of random strings in the range [2 50], respectively.

Results. As shown in Table 3 , D2KE consistently performs better than or similarly to other distancebased baselines. Unlike the previous experiments where DTW is not a distance metric, Levenshtein distance is indeed a distance metric; this helps improve the performance of our baselines. However, D2KE still offers a clear advantage over baseline. It is interesting to note that the performance of DSK_RBF is quite close to our method's, which may be due to DKS_RBF with Levenshtein distance producing a c.p.d. kernel which can essentially be converted into a p.d. kernel. Notice that on relatively large datasets, our method, D2KE, can achieve better performance, and often with far less computation than other baselines with quadratic complexity in both number and length of data samples. For instance, on mnist-str8 D2KE obtains higher accuracy with an order of magnitude less runtime compared to DSK_RBF and DSK_ND, and two orders of magnitude less than KSVM, due to higher computational costs both for kernel matrix construction and for eigendecomposition.

C.3 R W V:

Setup. For text data, following (Kusner et al., 2015) we use the earth mover's distance as our distance measure between two documents, since this distance has recently demonstrated a strong performance when combining with KNN for document classifications. We first compute the Bag of Words for each document and represent each document as a histogram of word vectors, where google pretrained word vectors with dimension size 300 is used. We generate random documents consisting of each random word vectors uniformly sampled from the unit sphere of the embedding vector space R 300 . We search for the best parameters for γ in the range [1e-2 1e1], and for length of random document in the range [3 21].

Results. As shown in Table 4 , D2KE outperforms other baselines on all four datasets. First of all, all distance based kernel methods perform better than KNN, illustrating the effectiveness of SVM over KNN on text data. Interestingly, D2KE also performs significantly better than other baselines by a notiably margin, in large part because document classification mainly associates with "topic" learning where our random documents of short length may fit this task particularly well. For the datasets with large number of documents and longer length of document, D2KE achieves about one order of magnitude speedup compared with other exact kernel/similarity methods, thanks to the use of random features in D2KE.

C.4 R SIFT-:

Setup. For image data, following (Pekalska et al., 2001; Haasdonk & Bahlmann, 2004) we use the modified Hausdorff distance (MHD) (Dubuisson & Jain, 1994) as our distance measure between images, since this distance has shown excellent performance in the literature (Sezgin & Sankur, 2004; Gao et al., 2012) . We first applied the open-source OpenCV library to generate a sequence of SIFT-descriptors with dimension 128, then MHD to compute the distance between sets of SIFTdescriptors. We generate random images of each SIFT-descriptor uniformly sampled from the unit sphere of the embedding vector space R 128 . We search for the best parameters for γ in the range [1e-3 1e1], and for length of random SIFT-descriptor sequence in the range [3 15].

Results. As shown in Table 5 , D2KE performance outperforms or matches other baselines in all cases. First, D2KE performs best in three cases while DSK_RBF is the best on dataset decor. This may be because the underlying SIFT features are not good enough and thus random features is not effective to find the good patterns quickly in images. Nevertheless, the quadratic complexity of DSK_RBF, DSK_ND, and KSVM in terms of both the number of images and the length of SIFT descriptor sequences makes it hard to scale to large data. Interestingly, D2KE still performs much better than KNN and RSM, which again supports our claim that D2KE can be a strong alternative to KNN and RSM across applications.

:



Figures and Tables:

Comparison between D2KE and different random features methods.

Table content: <table><tr><td>Methods</td><td>Inputs format</td><td>Distance Metric</td><td>Random Feature</td><td>Build new kernel</td></tr><tr><td>D2KE</td><td>Time-series, strings, sets</td><td>DTW, EditDist, HD</td><td>From any distribution</td><td>Yes</td></tr><tr><td>Rahimi's RF and its variants</td><td>Vector-form</td><td>Euclidean</td><td>User defined</td><td>No</td></tr></table>

Classification performance comparison on multi-variate Time-series with variable lengths

Table content: <table><tr><td>Methods</td><td colspan="2">D2KE</td><td colspan="2">KNN</td><td colspan="2">DSK_RBF</td><td colspan="2">DSK_ND</td><td colspan="2">KSVM</td><td/><td>RSM</td></tr><tr><td>Datasets</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td></tr><tr><td>Auslan</td><td>92.60</td><td>42.4s</td><td>70.26</td><td>52.1s</td><td>92.47</td><td>43.4s</td><td>89.74</td><td>44.6s</td><td>85.58</td><td>95.6s</td><td>88.96</td><td>68.6s</td></tr><tr><td>pentip</td><td>99.88</td><td>4.5s</td><td>98.37</td><td>27.3s</td><td>98.02</td><td>125.4s</td><td>70.40</td><td>126.6s</td><td>98.37</td><td>125.3s</td><td>98.48</td><td>13.6s</td></tr><tr><td>ActRecog</td><td>64.72</td><td>43.4s</td><td>53.43</td><td>85.5s</td><td>55.58</td><td>64.9s</td><td>45.31</td><td>68.0s</td><td>51.65</td><td>75.2s</td><td>62.44</td><td>64.5s</td></tr><tr><td>IQ_radio</td><td>86.87</td><td>469.3s</td><td>60.25</td><td>3734s</td><td>77.41</td><td>13381s</td><td>47.31</td><td>12251s</td><td>80.52</td><td>10084s</td><td>70.84</td><td>1275.9s</td></tr></table>

Classification performance comparison on Strings with variable lengths.

Table content: <table><tr><td>Methods</td><td colspan="2">D2KE</td><td/><td>KNN</td><td colspan="2">DSK_RBF</td><td colspan="2">DSK_ND</td><td colspan="2">KSVM</td><td/><td>RSM</td></tr><tr><td>Datasets</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td></tr><tr><td>bit-str4</td><td>90.00</td><td>2.3s</td><td>80.00</td><td>3.2s</td><td>88.33</td><td>3.9s</td><td>86.67</td><td>3.5s</td><td>83.33</td><td>2.8s</td><td>86.67</td><td>2.6s</td></tr><tr><td>splice</td><td>90.03</td><td>46.9s</td><td>79.41</td><td>164.2s</td><td>87.88</td><td>204.9s</td><td>85.89</td><td>208.2s</td><td>67.29</td><td>169.9s</td><td>86.10</td><td>87.3s</td></tr><tr><td>dna3</td><td>89.65</td><td>125.1s</td><td>85.79</td><td>859.6s</td><td>86.75</td><td>1005.2s</td><td>87.15</td><td>1025.2s</td><td>46.10</td><td>991.8s</td><td>87.04</td><td>213.5s</td></tr><tr><td>mnist-str8</td><td>98.49</td><td>2196s</td><td>96.58</td><td>13207s</td><td>97.5</td><td>18666s</td><td>92.66</td><td>18604s</td><td>96.80</td><td>84684s</td><td>97.31</td><td>4608.6s</td></tr></table>

Classification performance comparison on Bag of Words Vectors for Documents.

Table content: <table><tr><td>Methods</td><td colspan="2">D2KE</td><td/><td>KNN</td><td colspan="2">DSK_RBF</td><td colspan="2">DSK_ND</td><td colspan="2">KSVM</td><td colspan="2">RSM</td></tr><tr><td>Datasets</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td></tr><tr><td>Bbcsport</td><td>98.11</td><td>90.0s</td><td>95.4</td><td>157.2s</td><td>97.15</td><td>514.5s</td><td>96.52</td><td>512.5s</td><td>96.27</td><td>511.0s</td><td>97.0</td><td>263.2s</td></tr><tr><td>Twitter</td><td>74.2</td><td>15.1s</td><td>71.3</td><td>65.4s</td><td>72.05</td><td>73.5s</td><td>71.93</td><td>73.0s</td><td>70.60</td><td>73.0s</td><td>71.84</td><td>17.9s</td></tr><tr><td>Recipe</td><td>61.5</td><td>257s</td><td>57.4</td><td>478.1s</td><td>58.51</td><td>1508.5s</td><td>57.53</td><td>1502.2s</td><td>52.63</td><td>2364.1s</td><td>58.55</td><td>480.2s</td></tr><tr><td>Ohsumed</td><td>64.4</td><td>532.3s</td><td>55.5</td><td>3650.5s</td><td>59.89</td><td>6236.1s</td><td>58.51</td><td>6229.2s</td><td>46.50</td><td>6108.1s</td><td>59.91</td><td>841.5s</td></tr></table>

Classification performance comparison on Bag of Visual Words for images.

Table content: <table><tr><td>Methods</td><td colspan="2">D2KE</td><td/><td>KNN</td><td colspan="2">DSK_RBF</td><td colspan="2">DSK_ND</td><td colspan="2">KSVM</td><td colspan="2">RSM</td></tr><tr><td>Datasets</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td><td>Accu</td><td>Time</td></tr><tr><td>flower</td><td>46.03</td><td>22.0s</td><td>33.33</td><td>96.4s</td><td>36.51</td><td>103.5s</td><td>36.51</td><td>102.4s</td><td>38.10</td><td>85.1s</td><td>33.33</td><td>38.6s</td></tr><tr><td>letters2</td><td>55.45</td><td>64.5s</td><td>42.52</td><td>90.9s</td><td>54.55</td><td>101.9s</td><td>53.27</td><td>99.7s</td><td>42.45</td><td>205.2s</td><td>53.34</td><td>89.8s</td></tr><tr><td>decor</td><td>70.06</td><td>150.3s</td><td>61.81</td><td>1017.3s</td><td>70.83</td><td>1225.1s</td><td>70.14</td><td>1221.9s</td><td>52.78</td><td>987.1s</td><td>67.25</td><td>425.2s</td></tr><tr><td>style</td><td>40.29</td><td>20.5s</td><td>36.57</td><td>348.0s</td><td>38.06</td><td>450.3s</td><td>30.59</td><td>449.2s</td><td>25.74</td><td>443.1s</td><td>37.68</td><td>352.6s</td></tr></table>

Properties of the datasets. TS, Str, Text, and Img stand for Time-Series, String, text, and Image respectively. Var stands for the number of variables for time-series, word embeddings, and image SIFT-descriptors while Alpb stands for the size of the alphabet for strings. Note that all data samples have quite different range of lengths in different datasets.

Table content: <table><tr><td>Domain</td><td>Name</td><td colspan="2">Var/Alpb Classes</td><td>Train</td><td>Test</td><td>length</td></tr><tr><td>TS</td><td>Auslan</td><td>22</td><td>95</td><td>1795</td><td>770</td><td>45-136</td></tr><tr><td>TS</td><td>pentip</td><td>3</td><td>20</td><td>2000</td><td>858</td><td>109-205</td></tr><tr><td>TS</td><td>ActRecog</td><td>3</td><td>7</td><td>1837</td><td>788</td><td>2-151</td></tr><tr><td>TS</td><td>IQ_radio</td><td>4</td><td>5</td><td>6715</td><td>6715</td><td>512</td></tr><tr><td>Str</td><td>bit-str4</td><td>4</td><td>10</td><td>140</td><td>60</td><td>44/158</td></tr><tr><td>Str</td><td>splice</td><td>4</td><td>3</td><td>2233</td><td>957</td><td>60</td></tr><tr><td>Str</td><td>dna3</td><td>4</td><td>2</td><td>3620</td><td>1555</td><td>147</td></tr><tr><td>Str</td><td>mnist-str8</td><td>8</td><td>10</td><td colspan="2">60000 10000</td><td>17/99</td></tr><tr><td>Text</td><td>Bbcsport</td><td>300</td><td>5</td><td>517</td><td>220</td><td>43-469</td></tr><tr><td>Text</td><td>Twitter</td><td>300</td><td>3</td><td>2176</td><td>932</td><td>1-26</td></tr><tr><td>Text</td><td>Recipe</td><td>300</td><td>15</td><td>3059</td><td>1311</td><td>1-340</td></tr><tr><td>Text</td><td>Ohsumed</td><td>300</td><td>10</td><td>3999</td><td>5153</td><td>11-166</td></tr><tr><td>Img</td><td>flower</td><td>128</td><td>10</td><td>147</td><td>63</td><td>66/429</td></tr><tr><td>Img</td><td>decor</td><td>128</td><td>7</td><td>340</td><td>144</td><td>35/914</td></tr><tr><td>Img</td><td>style</td><td>128</td><td>7</td><td>625</td><td>268</td><td>6/530</td></tr><tr><td>Img</td><td>letters2</td><td>128</td><td>33</td><td>3277</td><td>1404</td><td>1/22</td></tr></table>

Table6lists the detailed properties of the datasets from four different domains. All computations were carried out on a DELL dual-socket system with Intel Xeon processors at 2.93GHz for a total of 16 cores and 250 GB of memory, running the SUSE Linux operating system. To accelerate the computation of all methods, we used multithreading with 12 threads total for various distance computations in all experiments. For time-series data, we employed the most successful distance measure -DTW -for all methods. For all datasets, a Gaussian distribution was found to be applicable, parameterized by its bandwidth σ. The best values for σ and for the length of random time series were searched in the ranges [1e-3 1e3] and [2 50], respectively.

Table content: <table><tr><td>C D</td><td>E</td><td>R</td><td>T -S</td><td>, S</td><td>,</td><td>I</td></tr><tr><td>C.1 R</td><td/><td>-</td><td/><td/><td/><td/></tr><tr><td>Setup.</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 D2KE: From Distance to Kernel and Embedding Quality: average Originality: original Significance: relevant for ICLR Pros: - interesting idea -- see detailed comments Cons: some technical issues, validity of the results not clear -- see detailed comments I have seen this paper already at ICML as a review and I am happy to see that the authors have improved the paper. Although the core idea is interesting and novel the paper raises still a number of questions (see below). Beside of some technical bits, I am (again) unhappy with the experimental evaluation - in particular there are strange mismatches between the results reported in the ICML submission and this one. The method looks now better in the shown results - basically be removing results from ICML on another method and some additional datasets. Further some information is not provided (parametrization, standard deviation of the results, significance of the differences). Some results are changed unexpectedly and there is still no comparison to some more challenging datasets as provided by other authors from the field. comments - the paper has a number of typos in the references - please carefully check and also complete missing information - I understand that you have to promote your approach but looking on the title your objective is to go from distances to kernels --> although you go a different way (which is fine) you can also do this directly by using concepts as proposed by Gisbrecht et al. *Metric and non-metric proximity transformations at linear costs*, Neurocomputing which you should at least take into account - to sum up a bit your related work part you should refer to a recent review by Tino et. al about indefinite learning, neural computation - *A line of work has therefore focused on estimating a positive-definite (PD) ...* - yes and by combining the approach from the Gisbrecht paper with the one of Loosli you can have e.g. an SVM in the Krein space without restriction to a single Hilbert space and with a simple and clear out of sample extension to test data. So basically there are ways to stay with an indefinite kernel (or non-metric dissimilarity), not loosing any performance and having no need to put it into a vector space. --> You could point to this option in your introduction - And as mentioned by a number of other authors (Pekalska, Tino, ...) there maybe good reasons for not going to a PD kernel - because one may still loose information - *distance kernel learning,* - this is a bit a mismatch - you either have a kernel or a distance and you may define a distance based on a kernel ... - *This type of kernel, however, results in a diagonal-dominance problem, where the diagonal entries of the kernel Gram matrix are orders of magnitude larger than the off-diagonal entries,* -- well yes, but could this not be solved by a renormalization of the kernel matrix (assuming that the diagonal elements are at least positive) such that finally all diagonals are 1? - Eq 4 is not a so new idea. Many authors have already plugged distances into an exp to make it a similarity - but this is changing the data representation (this is widely discussed by pekalska). And if d is non-metric the Eq for may not even provide the *correct* mathematical formulation. That may not be a problem - e.g. by asking - can I get any kind of similar kernel to my given dissimilarities (I think there is old work around this by G. Wahba et al.), e.g. by learning a proxy kernel such that the similarities of the kernel are close to the dissimilarities. One may also more directly deal with the dissimilarities see e.g. work of Yiming Ying about learning with dissimilarities (or so). But if I would like to keep the classical formulation that from an inner product based on K I can define a dissimilarity - and this should be the same like the original one which I used to get K the Eq 4 may not be so nice (--> see double centering in the book of Pekalska) - *, our kernel in Equation (5) is always PD by* - Eq 5 or Eq 4 - later on Eq 5 is never used again - cmp Algo 1 - caption/title - if I understand correct in Alg 1 l(x,y) - refers to a loss function (?) and y to a label - not introduced anywhere - but then your approach is supervised - the classical RFF are unsupervised (and hence more generic) - beside of this I may not have any label information if I go from a dissimilarity to similarities --> if this is a restriction of your method you should reflect this in adding e.g. * ... in supervised learning* in the title - *Since most distance measures are computationally demanding, having quadratic complexity, we adapted or implemented C-MEX programs for them; other codes were written in Matlab.* - software implementation details are not relevant here - please remove - please provide the full crossvalidation information including mean/std-dev, aligned with a significance test - *For our new method D2KE, since we generate random samples from the distribution, we can use as many as needed to achieve performance close to an exact kernel. We report the best number in the range R = [4, 4096] (typically the larger R is, the better the accuracy).* - if so I will hope you tuned your R on the training data and the reported values are from the test data! - please clarify - the other methods may also have meta-parameters e.g. C in the case of classical SVM - which values are used and how are they obtained - classical DTW is not defined for multiple timeseries - what did you use - your result tables have changed compared to the ICML paper (also one method GDK_LDE by Pekalska has vanished) please explain ! In particular also the runtime of RSM has nonlinearly changed between the two papers and the overall results are now a bit more in favour of your method. (Table 1) The dataset *mnist-str4* has vanished as well. For the image data you also have a strange change - in the ICML paper GDK_LED was best and now - because this method does not show up anymore your approach looks to be the best. As the runtime change so much between the two submissions I am wondering why you still report them. Basically the O-notation is telling that your method is linear (for reasonable large N and not to large R) and that most other have O(N^2). To ensure reproducability of your results I ask you to provide the respective codes e.g. on github (can be done anonymous) - Repeating myself from the last review: there is a lot of work addressing that making a kernel psd may not be good idea - you provide experiments for a small number of data where your kernel is now psd but what is with the other data (where e.g. in Pekalska and followers it was shown that making them psd is bad ... ) - is your approach solving this - or do we end with an approach which is not very performant (in accuracy) for the hard/crucial datasets? - why do you not use some of the datasets provided by Pekalska (simbad EU project - still in the web) (some maybe also be found by Loosli) to have a more realistic comparison - once more the number of datasets used in the evaluation is not particular large - still a few typos *dissimilairty* --> spell checker