arXiv:1802.06382v4 [cs.LG] 25 Mar 2018

Scalable Alignment Kernels via
Space-Efficient Feature Maps
Yasuo Tabei1 , Yoshihiro Yamanishi2 , and Rasmus Pagh3
1

RIKEN Center for Advanced Intelligence Project, Japan
2
Kyushu University, Japan
3
IT University of Copenhagen, Denmark

Abstract

1

Introduction

Massive string data are now ubiquitous throughout
research and industry, in areas such as biology, chemistry, natural language processing and data science.
For example, e-commerce companies face a serious
problem in analyzing huge datasets of user reviews,
question answers and purchasing histories [10, 21].
In biology, homology detection from huge collections
of protein and DNA sequences is an important part
for their functional analyses [24]. There is therefore
a strong need to develop powerful methods to make
best use of massive string data on a large-scale.

String kernels are attractive data analysis tools for
analyzing string data. Among them, alignment kernels are known for their high prediction accuracies
in string classifications when tested in combination
with SVMs in various applications. However, alignment kernels have a crucial drawback in that they
scale poorly due to their quadratic computation complexity in the number of input strings, which limits large-scale applications in practice. We present
the first approximation named ESP+SFM for alignment kernels leveraging a metric embedding named
edit-sensitive parsing (ESP) and space-efficient feature maps (SFM) for random Fourier features (RFF)
for large-scale string analyses. Input strings are projected into vectors of RFF leveraging ESP and SFM.
Then, SVMs are trained on the projected vectors,
which enables to significantly improve the scalability of alignment kernels while preserving their prediction accuracies. We experimentally test ESP+SFM
on its ability to learn SVMs for large-scale string classifications with various massive string data, and we
demonstrate the superior performance of ESP+ SFM
with respect to prediction accuracy, scalability and
computation efficiency.

Kernel methods [11] are attractive data analysis
tools because they can approximate any (possibly
non-linear) function or decision boundary well with
enough training data. In kernel methods, a kernel
matrix a.k.a. Gram matrix is computed from training
data and non-linear support vector machines (SVMs)
are trained on the matrix. Although it is known
that kernel methods achieve high prediction accuracy
for various tasks such as classification and regression,
they scale poorly due to its quadratic complexity in
the number of training data [12, 8]. In addition, calculation of a classification requires, in the worst case,
linear time in the number of training data, which
limits large-scale applications of kernel methods in
practice.
String kernels [9] are kernel methods for strings,
and a variety of strings kernels have been proposed
1

using different string similarity measures [16, 24, 5,
19]. Alignment kernels are the state-of-the-art string
kernel, and they are known for high prediction accuracies in string classifications such as remote homology detection for protein sequences [24] and time
series classifications [31, 5], when tested in combination with SVMs. However, alignment kernels have
a crucial drawback in that they scale poorly due to
their quadratic computation complexity in the number of training data as in other kernel methods.
To solve the scalability issues in kernel methods,
kernel approximations using feature maps (FM) have
been proposed. FM projects training data into lowdimensional vectors such that the kernel value (similarity) between each pair of training data is approximately equal to the inner product of the corresponding pair of low dimensional vectors. Then,
linear SVMs are trained on the projected vectors,
which significantly improves the scalability of nonlinear SVMs while preserving their prediction accuracies. Although a variety of kernel approximations
using FM have been proposed for enhancing the scalability of kernel methods (e.g., Jaccard kernels [18],
polynomial kernels [22] and Min-Max kernels [17]),
and Random Fourier Features (RFF) [23] is an approximation of shift-invariant kernels (e.g., Laplacian
and radial basis fuction (RBF) kernels), there are no
previous works on the approximation for alignment
kernels. Thus, an important open challenge, which is
required for large-scale analyses of string data, is to
develop a kernel approximation for alignment kernels.
Several metric embeddings for string distance measures have been proposed for large-scale string processing [4, 2]. Edit-sensitive parsing (ESP) [4] is a
metric embedding of a string distance measure called
edit distance with moves (EDM) that consists of ordinal edit operations of insertion, deletion and replacement in addition to substring move operation. ESP
maps all the strings from the EDM space into integer
vectors named characteristic vectors in the L1 distance space. Thus, EDM between each pair of input
strings is approximately preserved by the corresponding pair of characteristic vectors. To date, ESP has
been applied only to string processing such as string
compression [20], indexing [28], edit-distance computation [4]; however, as we will see, there remains

high potential for application to an approximation of
alignment kernels. ESP is expected to be effective for
approximating alignment kernels, because it approximates EDM between strings as L1 distance between
integer vectors.
Contribution. In this paper, we present the first approximation for alignment kernels to solve large-scale
learning problems on string data. Key ideas behind
our method are (i) to project input strings into characteristic vectors leveraging ESP, (ii) to map characteristic vectors into low dimensional vectors by FM
of RFF, and (iii) to train linear SVMs on the mapped
vectors. However, applying FM for RFF to high dimensional vectors in a direct way requires memory
linearly proportional to dD, where d is the dimensionality of input vectors and D is the target dimension.
Both d and D need to be large for our applications
(e.g., tens of millions of d and thousands of D), which
limits the applicability of FM on a large-scale. Although Le et al. [15] presented the fastfood approach
for fast computations of RFFs in O(D log d) time and
memory, this method is only applicable to RFFs for
RBF kernels. We present space-efficient FM (SFM)
that requires only O(d) memory to solve this problem. Unlike the fastfood approach, SFM can be used
to generate RFFs for any kernels. Our method called
ESP+SFM has the following desirable properties:

1. Scalability: ESP+SFM is applicable to massive string data.
2. Fast training: ESP+SFM trains SVMs fast.
3. Space efficiency:
ESP+SFM trains SVMs
space-efficiently.
4. Prediction accuracy: ESP+SFM can achieve
high prediction accuracy.
5. Online learning: ESP+SFM can train SVMs
with alignment kernels in an online manner.

We experimentally test the ability of ESP+SFM to
train SVMs with various massive string data, and
demonstrate that ESP+SFM has superior performance in terms of prediction accuracy, scalability and
computational efficiency.
2

Table 1: Summary of alignment kernels.

LAK [24]
GAK [6, 5]
ESP+SFM (this study)
CGK+SFM (this study)

2

Training
Training
Prediction
Online
Approach
time
space
time
learning
Local alignment
O(N 2 L2 )
O(N 2 )
O(N L2 ) Unsupported
2 2
2
Global alignment
O(N L )
O(N )
O(N L2 ) Unsupported
ESP
O(N L + dDN ) O(N L log N L + N D + d) O(L + dD) Supported
CGK
O(N L + dDN )
O(L|Σ| + N D + d)
O(L + dD) Supported

Literature Review

and is made possible by leveraging an idea behind
ESP and FM.
CGK [2] is another metric embedding for edit distance and maps input strings Si of alphabet Σ and
of the maximum length L into strings Si′ of fixedlength L such that the edit distance between each pair
of input strings is approximately preserved by the
Hamming distance between the corresponding pair
of mapped strings. Recently, CGK has been applied
to the problem of edit similarity joins [29]. We also
present a kernel approximation of alignment kernels
called CGK+SFM by leveraging an idea behind CGK
and SFM.
Details of the proposed method are presented in
the next section.

Several alignment kernels have been proposed for analyzing string data. We briefly review the state of
the art, which is also summarized in Table 1. Early
methods are proposed in [1, 26, 31] and are known
not to satify the positive definiteness for their kernel
matrices. Thus, they are proposed with numberical
corrections for any deficiency of the kernel matrices.
Global alignment kernel (GAK) [6, 5] is an alignment kernel based on global alignments using Dynamic Time Warping Distance (DTW) as a distance
measure. GAK defines a kernel as summation score
of all possible global alignments between two time series. The computation time of GAK is O(N 2 L) for
the number of strings N and the length of strings L.
The space usage is O(N 2 ).
Saigo et al. [24] proposed local alignment kernel (LAK) on the notion of the Smith-Waterman algorithm [27] for protein remote homology detections.
LAK measures the similarity between each pair of
strings by summing up scores obtained from local
alignments with gaps of strings. The computation
time of LAK is O(N 2 L2 ) for the number of strings
N and the length of strings L. The space usage is
O(N 2 ). Although LAK achieves high classification
accuracies for protein sequences in combination with
SVM, LAK is applicable to only protein strings because its scoring function is optimized for proteins.
Despite the importance of a scalable learning with
alignment kernels, no previous work has been able to
achieve high scalabilities and enables online learning
with alignment kernels while preserving high prediction accuracies. We present the first scalable learning with alignment kernels that meets these demands

3

Edit-sensitive parsing

Edit-sensitive parsing (ESP) [4] is an approximation
method for efficiently computing edit distance with
moves (EDM). EDM is a string-to-string distance
measure to turn one string to the other in a series
of string operations where substring move is included
as a string operation in addition to typical string operations such as insertion, deletion and replacement.
Let S be a string of length L and S[i] be i-th character in S. Formally, EDM EDM (S, S ′ ) between two
string S and S ′ is defined as the minimum number of
edit operations defined below to transform S into S ′ :
• Insertion: character a at position i in S is
inserted, resulted in S[1]...S[i − 1]aS[i]S[i +
1]...S[L],
• Deletion: character S[i] at position i in S is
deleted, resulted in S[1]...S[i − 1]S[i + 1]...S[L],
3

• Replacement: character S[i] at position i in S
is replaced by a, resulted in S[1]...S[i − 1]aS[i +
1]...S[L],
• Substring move:
a substring S[i]S[i +
1]...S[j] in S is moved and inserted at position k, resulted in S[1]...S[i − 1]S[j + 1]...S[k −
1]S[i]...S[j]S[k]...S[L].

A

Finding EDM between two strings is known as an
NP-complete problem [25]. ESP can approximately
compute EDM by embedding strings into L1 vector
space by a parsing technique.
Given string S, ESP builds a parse tree named
ESP tree, which is illustrated in Figure 1 as an example. ESP tree is a balanced tree and each node in
an ESP tree belongs to one of three types: (i) node
with three children, (ii) node with two children and
(iii) node without children (i.e., leaf). In addition,
internal nodes in ESP tree have the same node label
if and only if they have children satisfying both two
conditions: (i) the numbers of those children are the
same; (ii) node labels of those children are the same
in the left-to-right order. Since ESP tree is balanced,
nodes in each level can be considered as a sequence of
node labels that are listed in the left-to-right order.
We denote S ℓ as a sequence of node labels at level ℓ
in an ESP tree built from input string S. A sequence
of node labels for leaves is denoted as S 1 and is the
same as input string S, i.e., S 1 = S. We denote node
labels for internal nodes as Xi . The height of ESP
tree is O(log L) for the length of input string L.
Let V (S) ∈ Nd be a d-dimension integer vector
built from ESP tree T such that each dimension of
V (S) is the number of a node label appearing in T .
Such vectors are called characteristic vectors. ESP
builds ESP trees such that as many subtrees with
the same node labels as possible are built for common substrings for strings S and S ′ , resulted in an
approximation of EDM between S and S ′ by L1 distance between their characteristic vectors V (S) and
V (S ′ ), i.e., EDM (S, S ′ ) ≈ ||V (S) − V (S ′ )||1 , where
|| · ||1 is an L1 norm. More precisely, the upper and
lower bounds of the approximation are as follows,

B

A

B

A

B

B

A

B

Figure 1: Illustration of an ESP tree for string S =
ABABABBAB.
where log∗ L is the iterated logarithm of L, which
is recursively defined as log1 L = log2 L, logk+1 L =
log logk L and log∗ L = min{k; logk L ≤ 1, k ≥ 1} for
a positive integer L.
In the next section, we introduce left preferential
parsing (LPP) as a basic algorithm of ESP. In the
later of this section, we present the ESP algorithm.

3.1

Left preferential parsing (LPP)

A basic idea of LPP is to make pairs of nodes from the
left to the right positions preferentially in a sequence
of nodes at ESP tree and make triples of remaining
three nodes. Then, ESP builds type2 nodes for these
pairs of nodes and a type1 node for the triple of nodes.
LPP builds an ESP tree in a bottom-up manner.
More precisely, if the length of sequence S ℓ at ℓ-th
level of ESP tree is even, LPP makes pairs of S ℓ [2i−1]
and S ℓ [2i] for all i ∈ [1, |S ℓ |/2] and builds type2 nodes
for all the pairs. Thus, S ℓ+1 at (ℓ + 1)-th level of
ESP tree is a sequence of type2 nodes. If the length
of sequence S ℓ+1 of (ℓ + 1)-th level of ESP tree is
odd, LPP makes pairs of S ℓ [2i − 1] and S ℓ [2i] for
each i ∈ [1, |S ℓ /2 − 3|]. and makes triple of S ℓ [2i − 2],
S ℓ [2i − 1] and S ℓ [2i]. LPP builds type2 nodes for
pairs of nodes and type1 node for the triple of nodes.
Thus, S ℓ+1 at (ℓ+1)-th level of ESP tree is a sequence
of type2 nodes except the last node and the type1
node as the last node. LPP builds an ESP tree in
a bottom-up manner, i.e., it build an ESP tree from
leaves (i.e, ℓ = 1) to the root. See Example 2 for an
example.
A crucial drawback of LPP is that it can build completely different ESP trees for similar strings. For

EDM (S, S ′ ) ≤ ||V (S) − V (S ′ )||1
≤ O(log L log∗ L)EDM (S, S ′ ),
4

A

B

A

B

A

B

B

A

B

A

B

G

H

C

E

A

F

Figure 2: Example of LPP for a sequence S ′ = Figure 4: Illustration of the parsing on alphabet reABABABBAB of odd length.
duction.
landmarks
labels
1
0
1
0
2
4
1
binary
000 001 110 111 010 100 000 101
sequence
A
B
G
H
C
E
A
F

egories. ESP applies LPP to each subsequence of
sequence S ℓ in category (ii) and (iii), and it builds
nodes at (ℓ + 1)-level. For subsequences in category (i), ESP applies a special parsing technique
named alphabet reduction.

Figure 3: Example of alphabet reduction.
example, S ′ = AABABABBAB is a string where
character A is inserted at the first position of S in
Figure 1. Although S ′ and S are similar strings,
LPP builds completely different ESP trees T ′ and
T for S ′ and S, respectively, resulted in a large difference between EDM EDM (S ′ , S) and L1 distance
||V (S ′ ) − V (S)||1 for characteristic vectors V ′ and V .
Thus, LPP lacks an ability of approximating EDM.

3.2

Alphabet reduction. alphabet reduction is a procedure for converting a sequence to a new sequence
of alphabet size at most 3. For each symbol S ℓ [i], a
conversion is performed as follows. S ℓ [i − 1] is a left
adjacent symbol of S ℓ [i]. Suppose S ℓ [i − 1] and S ℓ [i]
are represented as binary integers. Let p be the index
of the least significant bit in which S ℓ [i − 1] differs
from S ℓ [i], and let bit(p, S ℓ [i]) be the binary integer of
S ℓ [i] at the p-th bit index. label label(S ℓ[i]) is defined
as 2p + bit(p, S ℓ [i]) and label(S ℓ[i]) is computed for
each position i in S ℓ . When this conversion is applied
to a sequence of alphabet Σ, the alphabet size of the
resulted label sequence is 2 log |Σ|, In addition, an important property of labels is that all adjacent labels
in a label sequence are different, i.e., label(S ℓ[i]) 6=
label(S ℓ[i − 1]) for all i ∈ [2, |S ℓ |]. Thus, this conversion can be iteratively applied to new label sequence,
label(S ℓ[1])label(S ℓ[2])...label(S ℓ[L]), until its alphabet size is at most 6.
Reduction of the alphabet size from {0, 1, ..., 5} to
{0, 1, 2} is performed as follows. First, each 3 in
a sequence is replaced with the least element from
{0, 1, 2} that does not neighbor the 3, then do the
same for each 4 and 5, which generates a new sequence A of node labels drawn from {0, 1, 2}, Where
no adjacent characters are identical.
We then select any position i which is a local maximum, i.e., A[i − 1] < A[i] > A[i + 1]. We shall call
those positions landmarks. In addition, we pick out as
a landmark any position i which is a local minimum,
i.e., A[i − 1] > A[i] < A[i + 1], and not adjacent to an
already chosen landmark. An important property for

The ESP algorithm

ESP uses an engineered strategy while using LPP
in its algorithm. ESP classifies a string into substrings of three categories and applies different parsing strategies according to their categories. An ESP
tree for an input string is built by gradually applying this parsing strategy in ESP to strings from the
lowest to the highest level of the tree.
Given sequence S ℓ , ESP divides S ℓ into subsequences in the following three categories: (i) Substring such that all pairs of adjacent node labels are
different and substring length is at least 5. Formally,
substring starting from position s and ending at position e in S satisfies S ℓ [i] 6= S ℓ [i+1] for any i ∈ [s, e−1]
and (e − s + 1) ≥ 5; (ii) Substring of same node label
and of length at least 5. Formally, substring starting from position s and ending at position e satisfies
S ℓ [i] = S ℓ [i+1] for any i ∈ [s, e−1] and (e−s+1) ≥ 5;
(iii) None of the above categories (i) and (ii).
After classifying a sequence into subsequences of
above three categories, ESP applies different parsing methods to each substring according to their cat5

such that for every choice of vectors x, y ∈ Rd we
have
E[zr (x)′ zr (y)] = K(x, y),

those landmarks is that for any two successive landmark positions i and j, either |i − j| = 2 or |i − j| = 3
hold. because A is a sequence of no adjacent characters in alphabet {0, 1, 2}. Figure 3 illustrates alphabet reduction for sequence ABGHCEAF .
Finally, we build type2 nodes (respectively, type3
nodes) for subsequences between landmarks i and j
of length |i − j| = 2 (respectively, |i − j| = 3). Figure 4 shows the parsing using alphabet reduction illustrated in Figure 3.

3.3

where K is the kernel function. The randomness of
zr comes from a vector r ∈ Rd sampled from an appropriate distribution Dk that depends on k (see section 5 for more details), and the expectation is over
the choice of r. For the purposes of this section all
we need to know about Dk is that the d vector coordinates are independently sampled according to the
marginal distribution ∆k .
Since
(zr (x)′ zr (y))2
≤
1
we
have
′
V ar(zr (x) zr (y)) ≤ 1, bounded variance, but
this in itself does not imply the desired approximation as K(x, y) ≈ zr (x)′ zr (y). Indeed, zr (x)′ zr (y)
is a poor estimator of K(x, y). The accuracy can
be improved by increasing the output dimension
to D ≥ 2. Specifically RFF uses D/2 independent
vectors r1 , . . . , rD/2 ∈ Rd sampled from Dk , and
considers FM
q

2
z : x 7→ D
zr1 (x), zr2 (x), . . . , zrD/2 (x)

Computation complexity

Given a collection of N strings S1 ,S2 ,...,SN where the
maximum length of strings among those strings is L,
ESP builds ESP-trees T1 ,T2 ,...,TN where Tj is built
from Sj for each j = 1, 2,...,N . To build ESP-trees
satisfying the condition that nodes having the same
label sequences in their children have the same node
labels, ESP uses a hash table that allows the unique
symbol to be found from a pair or a triple of symbols.
The hash table, denoted by H, holds pairs/triples of
symbols keyed on the corresponding symbol, resulted
in O(N L log N L) memory used in ESP. In practice,
the total number of pairs/triples of symbols is much
less than N L. Thus, the memory used for hash table
remains small in practice, which is shown in Sec.6.
The computation time of ESP is O(N L).
ESP builds characteristic vectors of high dimension
(e.g., tens of millions of vectors). Applying FM for
RFF to such high dimensional vectors consumes a
large amount of memory. In the next section, we
preset SFM for building RFF space-efficiently.

that concatenates the D/2 functions values to one
D-dimensional vector. Then one can show that
|z(x)′ z(y) − k(x, y)| ≤ ε with high probability for
D = Ω(1/ε2 ) sufficiently large.
In order to represent the function z one needs
to store the matrix containing vectors r1 , . . . , rD/2 ,
which uses space O(dD). Our insight is that the vectors ri do not need to be independent to ensure a
good approximation. Instead, for a small integer parameter t ∈ N we compute each vector ri using a
hash function h : {1, . . . , D/2} → Rd chosen from a
t-wise independent family such that for every i, h(i)
comes from distribution Dk . Then, instead of storing
4 Space-efficient Feature Maps r1 , . . . , r we only need to store the description of
D/2
the hash function h in O(tN ) memory. Apriori there
In this section we present FM for RFF using space
seems to be two issues with this approach:
also proportional to d and independent of the dimen• It is not clear how to construct t-wise indepension D for vectors of RFF. Our space-efficient FM is
dent hash functions whose output has distribucalled SFM and improves the space usage for genertion Dk .
ating RFF, which is proportional to dD. From an
abstract point of view, RFF is based on a way of
• Is t-wise independence sufficient to ensure results
constructing a random mapping
similar to the fully independent setting?
zr : Rd → [−1, +1]2

We address these issues in the next two subsections.
6

4.1

Hash functions with distribution second central moment:
i
h
Dk
2
′

E (z(x) z(y) − k(x, y))

2 
D/2
X

 2
zh(i) (x)′ zh(i) (y) − k(x, y) 
= E  D

For concreteness we base our construction on the
following class of t-wise independent hash functions, where t ∈ N is a parameter: For a =
(a0 , a1 , . . . , at−1 ) ∈ [0, 1]t chosen uniformly at random, let
fa (x) =

t−1
X

i=1



D/2

= E

aj xj mod 1

j=0

X

zh(i) (x)′ zh(i) (y) −

D
2

i=1

D/2

=

where y mod 1 computes the fractional part of y ∈
R. It can be shown that for any t distinct integer
inputs i1 , . . . , it ∈ N, the vector (fa (i1 ), . . . , fa (it ))
is uniformly distributed in [0, 1]t [23].
Let CDF −1 denote the inverse of the cumulative distribution function of the marginal distribution ∆k . Then if y is uniformly distributed in [0, 1],
CDF −1 (y) ∼ ∆k . We can now construct the hash
function h where the jth coordinate on input i is:

4
D2

X
i=1

E

h

zh(i) (x)′ zh(i) (y) −


2
k(x, y) 
D
2

2 i
≤ 2/D .
k(x, y)

The
second
equality
above
uses
2wise
and
the i fact
that
hP independence,
D/2
D
E
= 0 to
i=1 zh(i) (x) · zh(i) (y) − 2 k(x, y)
conclude that only D/2 terms in the expansion have
nonzero expectation. Finally, we have:
Pr[|z(x)′ z(y) − k(x, y)| ≥ ε]
≤ Pr[(z(x)′ z(y) − k(x, y))2 ≥ ε2 ]

h(i)j = CDF −1 (faj (i))

≤ E[(z(x)′ z(y) − k(x, y))2 ]/ε2 ≤ 2/(ε2 D),
where a1 , . . . , an are chosen independently from
[0, 1]k . We see that for every i ∈ N, h(i) = where the second inequality follows from Markov’s
(h(i)1 , . . . , h(i)n ) has distribution Dk . Furthermore, inequality. This concludes the proof.
for every set of t distinct integer inputs i1 , . . . , it ∈ N,
the hash values h(i1 ), . . . , h(it ) are independent.
In the original analysis of RFF a stronger kind of
approximation guarantee was considered, namely approximation of the kernel function for all pairs of
4.2 Concentration bounds
points x, y in a bounded region of Rd . This kind of
result can be achieved by chosing t ≥ 2 sufficiently
We next show that like for RFF, D = O(1/ε2 ) ranlarge to obtain stronger tail bounds. However, our
dom features suffice to approximate the kernel func- experiments suggest that the type of point-wise guartion within ε error with probability arbitrarily close antee (i.e., t = 2) provided by Theorem 1 is sufficient
to 1.
for an application in kernel approximations.
Theorem 1. For every pair of vectors x, y ∈ Rd , if
the mapping z is constructed as described above using
t ≥ 2 we have for every ε > 0:

5

Scalable Alignment Kernels

In this section we present the ESP+SFM algorithm
for scalable learning with alignment kernels.
Let us assume a collection of N strings and their laProof. Our proof follows the same outline as the stan- bels (S1 , y1 ), (S2 , y2 ), ..., (SN , yN ) where yi ∈ {0, 1}.
dard proof of Chebychev’s inequality. Consider the We define alignment kernels using EDM (Si , Sj ) for
Pr[|z(x)′ z(y) − k(x, y)| ≥ ε] ≤ 2/(ε2 D) .

7

Algorithm 1 Generation of the Cauchy random
number using 2-wise independent hash functions.
array1 , array2 : arrays of d 64-bit unsigned integers;
U M AX32: maximum value of unsigned 32-bit integer; β: a parameter.
1: Initialize array1 and array2 with 64-bit random
numbers.
2: function Func f(i, j)
3:
t = array1 [j] · i
4:
v = (t + array2 [j]) >> 32
⊲ Get the most
significant 32-bit of value
5:
return v/U M AX32 ⊲ Return value in [0, 1]
6: function Func h(i, j)
7:
u = F unc F (i, j)
8:
return tan(π · (u − 0.5))/β
⊲ Convert
random number u to Cauchy random number

For Laplacian kernels, zrm (x) for each m
1, 2, ..., D/2 is defined as

each pair of strings Si and Sj as follows,

5.1

K(Si , Sj ) using FM z(x) for RFF as follows,
K(Si , Sj ) ≈ z(V (Si ))′ z(V (Sj )),

(3)

where
z(x)

=

r

2
(zr (x), zr2 (x), ..., zrD/2 (x)).
D 1

⊤
zrm (x) = (cos (r⊤
m x), sin (rm x))

=
(4)

where random vectors rm ∈ Rd for m = 1, 2, ..., D/2
are sampled from the Cauchy distribution.
Applying FM to high dimensional characteristic
vectors consumes huge amount of memory. Thus, we
present SFM for RFF using O(D) memory by applying t-wise independent hash functions introduced in
Algorithm 2 Construction of RFF by SFM. z: vec- Sec.4. We fix t = 2 in this study.
Algorithm 1 is a random number generation from
tor of RFF; D: dimension of z; V : characteristic
Cauchy
distribution using O(d) memory. We use two
vector; d: dimension of V .
arrays
array
1 and array2 initialized with 64-bit ran1: function SFM(V )
dom
numbers.
Function fa (x) is implemented using
2:
for i = 1, ..., D/2 do
array
and
array
1
2 in F unc F and returns a random
3:
s=0
number
in
[0,
1]
for
given i and j as input. Then, ran4:
for j = 1, ..., d do
dom
number
u
returned
from F unc F is converted
5:
s = s + Vq
[j] · F unc H(i, j)
to
a
random
number
from
Cauchy distribution in
2
6:
z[2 · i − 1] = D
· sin(s)
F
unc
H
as
tan(π
·
(u
−
0.5))/β
at line 8. Algorithm 2
q
2
implements
SFM
generating
RFF
in Eq.4. The com7:
z[2 · i] = D · cos(s)
putation time and memory for SFM are O(dDN ) and
8:
return z
O(d), respectively.

Online learning

(1) Vector of RFF z(V (Si )) for characteristic vector
V (Si ) from ESP for each string Si can be computed
where β is a parameter. We apply ESP to each Si in an online manner, because ESP and SFM are exfor i = 1, 2, ..., N and build ESP trees T1 , T2 , ..., TN . ecutable in an online manner. By applying online
Since ESP approximates EDM (Si , Sj ) as an L1 dis- learning of linear SVMs such as passive aggressive altance between characteristic vectors V (Si ) and V (Sj ) gorithm [30] to z(V (Si )), linear SVMs can be trained
built from ESP trees Ti and Tj for Si and Sj , i.e., in an online manner.
EDM (Si , Sj ) ≈ ||V (Si ) − V (Sj )||1 , we can approximate K(Si , Sj ) as follows,
K(Si , Sj ) = exp(−EDM (Si , Sj )/β),

5.2

K(Si , Sj ) ≈ exp(−||V (Si ) − V (Sj )||1 /β).

(2)

CGK+SFM

CGK [2, 29] is another string embedding using a ranSince Eq.2 is a Laplacian kernel that is also known domized algorithm. Let Si for i = 1,2,...,N be inas a shift invariant kernel [23], we can aprroximate put strings of alphabet Σ and let L be the maximum
8

Dataset
Protein
DNA
Music
Sports
Compound

Table 2: Summary of datasets.
Number #positives Alphabet size
3,238
96
20
3,238
96
4
10,261
9,022
61
296,337
253,017
63
1,367,074
57,536
44

length of input strings. CGK maps input strings Si
in the edit distance space into strings Si′ of length
L in the Hamming space, i.e, the edit distance between each pair Si and Sj of input strings is approximately preserved by the Hamming distance of the
corresponding pair Si′ and Sj′ of the mapped strings.
See [29] for the detail of CGK.
To apply SFM, we convert mapped strings Si′ in
the Hamming space by CGK to characteristic vectors V C (Si′ ) in the L1 distance space as follows. We
view elements Si′ [j] for j = 1,2,...,L as locations (of
the nonzero elements) instead of characters. For example, when Σ = {1, 2, 3}, we view each Si′ [j] as
a vector of length |Σ| = 3. If Si′ [j] = 1, then we
code it as (0.5, 0, 0); if Si′ [j] = 3, then we code it
as (0, 0, 0.5). We then concatenate those L vectors
into one vector V C (Si′ [j]) of dimension L|Σ| and with
L nonzero elements, resulted in Hamming distance
Ham(Si′ , Sj′ ) = ||V C (Si′ ) − V C (Sj′ )||1 .
Vectors of RFF z(V C (Si′ )) can be built using SFM.
We shall call approximation of alignment kernels using CGK and SFM CGK+SFM. CGK+SFM cannot
achieve high prediction accuracies in practice, which
is shown in Sec.6.

6

Average length
607
1,827
329
307
53

by a string consisting of 20 types of amino acids. Enzymes belonging to class 5 in the enzyme commission (EC) numbers in ”DNA” and ”Protein” have
positive labels and the other enzymes have negative
labels. There are 96 enzymes with positive labels
and 3,142 enzymes with negative labels in ”DNA”
and ”Protein”. The ”Music” and ”Sports” datasets
consist of 10,261 and 296,337 reviews of musical instruments products and sports products in English
from Amazon [10, 21], respectively. Each review has
a rating of five levels. We assigned positive labels to
reviews with four or five levels for rating and negative labels to the other reviews. The numbers of
positive and negative reviews were 9,022 and 1,239,
respectively in ”Music”. The numbers of positive
and negative reviews were 253,017 and 296,337, respectively in ”Sports”. The ”Compound” dataset
consists of 1,367,074 bioactive compounds obtained
from the PubChem database in the national center for biotechnology information (NCBI) [14]. Each
compound was coded by a string representation of
chemical structures called simplified molecular input
line entry system (SMILES). The biological activities of the compounds for human proteins were obtained from the ChEMBL database. In this study
we focused on the biological activity for the human
protein microtubule associated protein tau (MAPT).
The label of each compound corresponds to the presence or absence of biological activity for MAPT. The
numbers of positive and negative compounds were
57,537 and 1,309,537, respectively. We implemented
all the methods by C++ and performed all the experiments on one core of a quad-core Intel Xeon CPU
E5-2680 (2.8GHz). We stopped the execution of each
method if it was not finished within 48 hours in the

Experiments

In this section, we evaluated the performance of
ESP+SFM with five massive sting datasets, as shown
in Table 2. The ”Protein” and ”DNA” datasets
consist of 3,238 human enzymes obtained from the
KEGG GENES database [13], respectively. Each enzyme in ”DNA” was coded by a string consisting of
four types of nucleotides or bases (i.e., A, T, G, and
C). Similarity, each enzyme in ”Protein” was coded
9

Table 3: Execution time in seconds, memory in mega bytes and dimension d of characteristic vectors by
ESP and CGK for each dataset.
Data
Method

ESP

Time (sec)
Memory (MB)
Dimension d

Protein
CGK

1.25
1, 042.90
707, 922

0.87
0.09
4, 950, 686

DNA

Music

Sports

ESP

CGK

ESP

CGK

ESP

CGK

2.01
1, 049.89
969, 653

2.63
3.38
19, 192, 656

1.86
1, 048.30
910, 110

0.86
0.37
2, 129, 505

47.83
1, 514.23
18, 379, 173

34.08
0.54
3, 095, 844

Compound
ESP
CGK
32.73
1, 165.60
5, 302, 660

28.70
0.08
485, 840

experiments. Softwares and datasets used in this exFigure 5 shows the memory consumed in SFM
periments are downloadable from 1 .
and FM for characteristic vectors built by ESP and
CGK for each dataset. Huge amount of memory was
consumed in FM for high dimension characteristic
6.1 Scalability of ESP
vectors and projected vectors. Around 1.1TB and
First, we evaluated the scalability of ESP in the com- 323GB memories were consumed by ESP+FM for
parison with CGK. Table 3 shows the execution time, D = 16, 384 in the results of ”Sports” and ”Commemory and dimension d for characteristic vectors pound”, respectively, which prevented us from buildgenerated by ESP and CGK. ESP and CGK were ing high dimension vectors of RFF. The memory repractically fast enough to build characteristic vectors quired by SFM was linear to dimension d of characfor large datasets. The executions of ESP and CGK teristic vectors for each dataset. Only 280MB and
finished within 60 seconds for ”Compound” that was 80MB were consumed by ESP+SFM for D = 16, 384
the largest dataset consisting of more than 1 mil- in the results of ”Sports” and ”Compound”, respeclion compounds. The memory used in CGK was tively. These results suggest that ESP+SFM enables
smaller than that of ESP for each dataset and at dramatical reduction of required memory, compared
most 1.5GB memory was consumed in the execution with ESP+FM.
Figure 6 shows the execution time for building proof ESP. These results demonstrates high scalability
jected
vectors for each dataset. The execution time
of ESP for massive datasets.
increased
linearly to dimension D for each method
Characteristic vectors of very high dimensions were
and
SFM
built 16,384 dimension vectors of RFF for
built by ESP and CGK for each dataset. For ex”Compound”
in around 9 hours.
ample, 18 million dimension vectors were built by
We
evaluated
the accuracies of our approximations
ESP for the ”Sports” dataset. Applying FM to such
of
alignment
kernels
by the average error of RFF dehigh dimension characteristic vectors consumed huge
fined
as
amount of memory, deteriorating the scalability of
FM. Our proposed SFM can solve the scalability
PN PN
′
i=1
j=i |K(Si , Sj ) − z(V (Si )) z(V (Sj ))|
problem, which will be shown in the next subsection.
,
N (N + 1)/2

6.2

Efficiency of SFM

We evaluated the efficiency of SFM applied to characteristic vectors built from ESP and CGK, and
compared it with FM. We examined combinations
of characteristic vectors and projected vectors of
ESP+FM, ESP+SFM, CGK+FM and CGK+SFM.
The dimension D of projected vectors of RFF was
examined for D = {128, 512, 2048, 8192, 16384}.
1 https://sites.google.com/view/alignmentkernels/home

where K(Si , Sj ) was defined as Eq. 2 and β = 1 was
fixed. The average error of SFM was compared with
that of FM for each dataset. Table 4 shows the average errors of SFM and FM using characteristic vectors built from ESP for each dataset. The average
errors were almost the same between ESP+SFM and
ESP+FM for all datasets and dimension D. The accuracies of FM were preserved in SFM while achieving the dramatical reduction of memory required for
FM. The same tendencies were observed for the av-

10

DNA

Music

Sports

Compound

100

10

1
0

5000

10000

100000
ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

10000
1000
100
10
1
0

15000

Dimension of RFF (D)

10000
5000
Dimension (D)

10000
ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

1000
100
10
1
0

15000

340000
100000

1000000

10000
5000
Dimension (D)

Memory for building RFFs (MB)

ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

1000

Memory for building RFFs (MB)

10000

Memory for building RFFs (MB)

Memory for feature maps (mega bytes)

100000

1000000

100000
ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

10000
1000
100
10
1

15000

0

10000
5000
Dimension (D)

Memory for building RFFs (MB)

Protein
320000
100000

10000
ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

1000
100
10
1
0

15000

5000
10000
Dimension (D)

15000

Figure 5: Memory in mega bytes for building vectors of RFF for various dimensions D.

0

0
0

10000
5000
Dimension (D)

15000

0

10000
5000
Dimension (D)

15000

ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

0

10000
5000
Dimension (D)

15000

Compound
Time for building RFFs (sec)
10000
30000
50000

Sports
ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

0

ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

Time for building RFFs (sec)
2000
4000
6000

ESP+SFM
ESP+FM
CGK+SFM
CGK+FM

Music
Time for building RFFs (sec)
0 10000
30000
50000

DNA
Time for building RFFs (sec)
0 500
1500
2500
3500

Time for building RFFs (sec)
500
1000 1500 2000

Protein

0

10000
5000
Dimension (D)

15000

0

10000
5000
Dimension (D)

15000

Figure 6: Time in seconds for building vectors of RFF for various dimensions D.
erage errors of SFM in combination with CGK, as C ={0.001, 0.01, 0.1, 1, 10, 100}
shown in Table 5
Table 6 shows the execution time for building RFF
and computing kernel matrices in addition to training
linear/non-linear SVMs for each method. LAK was
6.3 Classification
performance
of applied to only ”Protein” because its scoring funcESP+SFM
tion was optimized for protein sequences. It took 9
We evaluated the classification abilities of hours for LAK to finish the execution, which was the
ESP+SFM, CGK+SFM, LAK and GAK. We most time-consuming among all methods on ”Proused an implementation of LAK downloadable from tein”. The execution of GAK finished within 48
2
. In addition, Laplacian kernels with characteristic hours for only ”Protein” and ”Music” and it took
vectors of ESP and CGK in Eq.2 were evaluated and around 7 hours and 28 hours for ”Protein” and ”Mudenoted as ESP+Kernel and CGK+Kernel, respec- sic”, respectively. The execution of ESP+Kernel
tively. We used LIBLINEAR [7] for training linear and CGK+Kernel did not finish with 48 hours for
SVMs with ESP+SFM and CGK+SFM. We trained ”Sports” and ”Compound”. These results suggest
non-linear SVMs with GAK, LAK, ESP+Kernel that existing alignment kernels are not suitable for
and CGK+Kernel using LIBSVM [3]. We performed applications to massive string datasets. The execu3-fold cross-validation for each dataset and measured tions of ESP+SFM and CGK+SFM finished with 48
the prediction accuracy by the area under the ROC hours for all datasets. ESP+SFM and CGK+SFM
curve (AUC). The dimension D of vectors of RFF took around 9 hours and 13 hours, respectively, for
was examined for D = {128, 512, 2048, 8192, 16384}. ”Compound” consisting of 1.3 million strings in the
We selected the best parameter achieving the highest setting of large D = 16382.
Figure 7 shows the memory consumed for trainAUC among all combinations of kernel’s parameter
β={1, 10, 100, 1000, 10000} and SVM’s parameter ing linear/non-linear SVMs for each method, where
GAK, LAK, ESP+Kernel, CGK+ Kernel are repre2 http://sunflower.kuicr.kyoto-u.ac.jp/ hiroto/project/homology.html
sented as ”Kernel”. ”Kernel” required small mem~
11

Table 4: Average error
Method
ESP+SFM(D=128)
ESP+FM(D=128)
ESP+SFM(D=512)
ESP+FM(D=512)
ESP+SFM(D=2048)
ESP+FM(D=2048)
ESP+SFM(D=8192)
ESP+FM(D=8192)
ESP+SFM(D=16384)
ESP+FM(D=16384)

by ESP+SFM and ESP+FM for
Protein
DNA
7.054(±5.320) 7.051(±5.318)
7.055(±5.321) 7.054(±2.664)
3.523(±2.662) 3.526(±2.663)
3.526(±2.665) 3.526(±2.666)
1.762(±1.332) 1.762(±1.332)
1.763(±1.332) 1.762(±1.332)
0.881(±0.666) 0.881(±0.665)
0.880(±0.666) 0.881(±0.666)
0.623(±0.471) 0.623(±0.470)
0.628(±0.470) 0.623(±0.471)

each dataset. All
Music
7.058(±5.318)
7.059(±5.318)
3.526(±2.662)
3.526(±2.663)
1.762(±1.332)
1.762(±1.331)
0.879(±0.665)
0.881(±0.666)
0.621(±0.470)
0.623(±0.471)

Table 5: Average error by CGK+SFM and CGK+FM for
Method
Protein
DNA
CGK+SFM(D=128)
7.056(±5.319) 7.051(±5.318)
CGK+FM(D=128)
7.054(±5.316) 7.055(±5.322)
CGK+SFM(D=512)
3.524(±2.662) 3.526(±2.663)
CGK+FM(D=512)
3.523(±2.664) 3.526(±2.664)
CGK+SFM(D=2048)
1.761(±1.331) 1.762(±1.332)
CGK+FM(D=2048)
1.762(±1.332) 1.761(±1.331)
CGK+SFM(D=8192)
0.881(±0.662) 0.881(±0.665)
CGK+FM(D=8192)
0.881(±0.666) 0.881(±0.666)
CGK+SFM(D=16384) 0.623(±0.471) 0.623(±0.470)
CGK+FM(D=16384)
0.623(±0.471) 0.623(±0.470)

ory for relatively small datasets such as ”Protein”,
”DNA” and ”Music”, but it required huge memory
for relatively large datasets such as ”Sports” and
”Compound”. For example, it consumed 654GB and
1.3TB memories for ”Sports” and ”Compound”, respectively. The memories for ESP+SFM and CGK
+SFM were at least one order magnitude smaller
than those of ”Kernel”. ESP+SFM and CGK+SFM
required 36GB and 166GB memories for ”Sports”
and ”Compound” in the setting of large D =
16382, respectively. These results demonstrated high
memory-efficiency of ESP+SFM and CGK+SFM.

values are multiplied by 102 .
Sports
Compound
7.058(±5.319) 7.057(±5.31)
7.059(±5.320) 7.057(±5.318)
3.525(±2.662) 3.527(±2.662)
3.526(±2.663) 3.526(±2.662)
1.762(±1.332) 1.761(±1.331)
1.763(±1.331) 1.762(±1.331)
0.881(±0.665) 0.876(±0.664)
0.881(±0.666) 0.881(±0.665)
0.623(±0.470) 0.606(±0.461)
0.623(±0.471) 0.623(±0.471)

each dataset. All
Music
7.059(±5.320)
7.059(±5.319)
3.526(±2.662)
3.527(±2.661)
1.763(±1.332)
1.332(±1.763)
0.881(±0.665)
0.881(±0.666)
0.632(±0.470)
0.632(±0.471)

values are multiplied by 102 .
Sports
Compound
7.057(±5.319) 7.056(±5.317)
7.057(±5.319) 7.060(±5.319)
3.525(±2.662) 3.525(±2.661)
3.525(±2.662) 3.527(±2.663)
1.763(±1.332) 1.762(±1.331)
1.762(±1.331) 1.763(±1.331)
0.881(±0.665) 0.869(±0.663)
0.881(±0.665) 0.881(±0.666)
0.623(±0.470) 0.589(±0.453)
0.623(±0.470) 0.623(±0.470)

and CGK+SFM improved for larger D. The prediction accuracy of ESP+SFM was higher than that
of CGK+SFM for any D on all datasets and competitive to those of LAK, GAK, ESP+Kernel and
CGK+Kernel. These results suggest that ESP+SFM
can achieve high classification accuracy and it is much
more efficient than the other methods in terms of
memory and time for building RFF and training linear SVMs.

Figure 8 shows the classification accuracy of each
method. The prediction accuracies of ESP+SFM
12

Table 6: Training time in seconds for linear/non-linear SVMs with each method.
Method
Protein DNA Music Sports Compound
ESP+SFM(D=128)
5
8
11
204
261
ESP+SFM(D=512)
22
34
47
799
1,022
ESP+SFM(D=2048)
93
138
193
3,149
4,101
ESP+SFM(D=8192)
367
544
729
12,179
16,425
ESP+SFM(D=16384)
725
1,081
1,430
24,282
32,651
CGK+SFM(D=128)
14
52
26
452
397
CGK+SFM(D=512)
60
222
104
1,747
1,570
CGK+SFM(D=2048)
237
981
415
7,156
6,252
CGK+SFM(D=8192)
969
3,693
1,688
27,790
25,054
CGK+SFM(D=16384)
1,937
7,596
3,366
53,482
49,060
LAK
31,718
GAK
25,252 >48h 101,079
>48h
>48h
ESP+Kernel
20
28
162
>48h
>48h
CGK+Kernel
31
95
196
>48h
>48h

7

Conclusions
Work

and

Future

important to scale up kernel methods to be applied
in various machine learning applications.

We presented the first approximation of alignment
Acknowledgments
kernels for solving large-scale classifications of string 8
datasets. Our method called ESP+SFM has the folWe thank Takaaki Nishimoto and Ninh Pham for
lowing appealing properties:
useful discussions of kernel approximation methods.
1. Scalability: ESP+SFM is applicable to mas- The research of Rasmus Pagh has received funding
from the European Research Council under the Eurosive string data (see Section 6).
2. Fast training: ESP+SFM trains SVMs fast pean Union’s 7th Framework Programme (FP7/20072013) / ERC grant agreement no. 614331.
(see Section 6.3).
3. Space efficiency:
ESP+SFM trains SVMs
space-efficiently (see Section 6.3).
4. Prediction accuracy: ESP+SFM can achieve References
high prediction accuracy (see Section 6.3).
[1] C. Bahlmann, B. Haasdonk, and H. Burkhardt.
5. Online learning: ESP+SFM can train SVMs
Online handwriting recognition with support
with alignment kernels in an online manner (see
vector machines-a kernel approach. In ProceedSection 5.1).
ings of the 8th International Workshop on FronWe developed novel space-efficient feature maps
tiers in Handwriting Recognition, pages 49–54,
named SFM for RFF and applied to approximations
2002.
of alignment kernels, but in principle it is useful for
[2] D. Chakraborty, E. Goldenberg, and M. Koucký.
scaling up other kernel approximations using FM.
Streaming algorithms for embedding and comThus, an important feature work is to apply SFM to
puting edit distance in the low distance regime.
other kernel approximations, Such extensions will be
13

0.8
AUC
0.4

0.6

ESP+SFM(D=128)
ESP+SFM(D=512)
ESP+SFM(D=2048)
ESP+SFM(D=8192)
ESP+SFM(D=16384)
ESP+Kernel
CGK+SFM(D=128)
CGK+SFM(D=512)
CGK+SFM(D=2048)
CGK+SFM(D=8192)
CGK+SFM(D=16384)
GCK+kernel
LAK
GAK

1e+07

Music

Sports

Compound

Figure 7: Memory in mega
bytes for training SVMs for each
method.
”Kernel” represents
GAK, LAK, ESP+Kernel and
CGK+Kernel.

0.0

Protein/DNA

0.2

1e+01

Memory (mega bytes)
1e+03
1e+05

ESP/CGK+SFM(D=128)
ESP/CGK+SFM(D=512)
ESP/CGK+SFM(D=2048)
ESP/CGK+SFM(D=8192)
ESP/CGK+SFM(D=16384)
Kernel

Protein

DNA

Music

Sports

Compound

Figure 8: AUC for each method.

In Proceedings of the 48th annual ACM symposium on Theory of Computing, pages 715–725,
2016.

chines. SIAM Journal of Optimization, 13:783–
804, 2003.

[9]
[3] C. C. Chang and C. J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology,
[10]
pages 27:1–27:27, 2011.
[4] G. Cormode and S. Muthukrishnan. The string
edit distance matching problem with moves.
ACM Transactions on Algorithms, 3:2:1–2:19,
2007.
[5] M. Cuturi. Fast global alignment kernels. In
Proceedings of the 28th International Conference
on Machine Learning, pages 929–936, 2011.

T. Gärtner. A survey of kernels for structured
data. ACM SIGKDD Explorations Newsletter,
5:49–58, 2003.
R. He and J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with
one-class collaborative filtering. In Proceedings
of the 25th International World Wide Web Conference, pages 507–517, 2016.

[11] T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. The Annals of
Statistics, 36:1171–1220, 2008.

[12]
[6] M. Cuturi, J. P. Vert, Ø. Birkenes, and T. Matsui. A kernel for time series based on global
alignments. In Proceedings of the 2007 IEEE International Conference on Acoustics, Speech and
[13]
Signal Processing, pages 413–416, 2007.

T. Joachims. Training linear SVMs in linear
time. In Proceedings of the 12th ACM Conference on Knowledge Discovery and Data Mining,
pages 217–226, 2006.
M. Kanehisa, M. Furumichi, M. Tanabe,
Y. Sato, and K. Morishima. Kegg: new perspectives on genomes, pathways, diseases and drugs.
Nucleic Acids Research, 45:D353–D361, 2017.

[7] R. E. Fan, K. W. Chang, C. J. Hsieh, X. R.
Wang, and C. J. Lin. LIBLINEAR: A library
for large linear classification. Journal of Machine
[14] S. Kim, P. A. Thiessen, E. E. Bolton, J. Chen,
Learning Research, 9:1871–1874, 2008.
G. Fu, A. Gindulyte, L. Han, J. He, S. He,
[8] M. C. Ferris and T. S. Munson. InteriorB. A. Shoemaker, J. Wang, B. Yu, J. Zhang,
point methods for massive support vector maand S. H. Bryant. Pubchem substance and
14

[15]

[16]

[17]

[18]

compound databases. Nucleic Acids Research, [23] A. Rahimi and B. Recht. Random features for
large-scale kernel machines. In Proceedings of
44:D1202–D1213, 2016.
the 21st Conference on Neural Information ProQ. Le, T. Sarlos, and A. Smola. Fastfood – apcessing Systems, pages 1177–1184, 2007.
proximating kernel expansions in loglinear time.
In Proceedings of the 30th International Confer- [24] H. Saigo, J. P. Vert, N. Ueda, and T. Akutsu.
Protein homology detection using string alignence on Machine Learning, pages 244–252, 2013.
ment kernels. Bioinformatics, 20:1682–1689,
C. Leslie, E. Eskin, and W. S. Noble. The spec2004.
trum kernel: a string kernel for svm protein classification. In Proceedings of the 7th Pacific Sym- [25] D. Shapira and J. A. Storer. Edit distance with
move operations. In Proceedings of the 13th
posium on Biocomputing, pages 566–575, 2002.
Symposium on Combinatorial Pattern Matching,
P. Li. Linearized GMM kernels and normalvolume 2373, pages 85–98, 2002.
ized random fourier features. In Proceedings of
the 23rd ACM SIGKDD International Confer- [26] H. Shimodaira, K. Noma, M. Nakai, and
S. Sagayama. Dynamic time-alignment kernel
ence on Knowledge Discovery and Data Mining,
in support vector machine. In Proceedings of the
pages 315–324, 2017.
14th Advances in Neural Information Processing
P. Li, A. Shrivastava, J. Moore, and A. C.
Systems, pages 921–928, 2001.
Köning. Hashing algorithms for large-scale
learning. In Proceedings of the 24th Interna- [27] T. F. Smith and M. S. Waterman. Identification
of common molecular subsequences. Journal of
tional Conference on Neural Information ProMolecular Biology, 147:195–197, 1981.
cessing Systems, pages 2672–2680, 2011.

[19] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cris- [28] Y. Takabatake, Y. Tabei, and H. Sakamoto. Improved ESP-index: A practical self-index for
tianini, and C. Watkins. Text classification using
highly repetitve texts. In Proceedings of the 13th
string kernels. Journal of Machine Learning ReInternational Symposium on Experimental Algosearch, 2:419–444, 2002.
rithms, pages 338–350, 2014.
[20] S. Maruyama, Y. Tabei, H. Sakamoto, and
[29] EmbedJoin: Efficient Edit Similarity Joins via
K. Sadakane. Fully-online grammar compresEmbeddings. Zhang, h. and zhang, q. In
sion. In Proceedings of International Symposium
Proceedings of the 23rd SIGKDD International
on String Processing and Information Retrieval,
Conference on Knowledge Discovery and Data
pages 218–229, 2013.
Mining, pages 585–594, 2017.
[21] J. McAuley, C. Targett, J. Shi, and A. van den
[30] J. Wang, P. Zhao, and C. S. Holi. Exact soft
Hagel. Image-based recommendations on styles
confidence-weighted learning. In Proceedings of
and substitutes. In Proceedings of the 38th
the 29th International Conference on Machine
International ACM SIGIR Conference on ReLearning, pages 121–128, 2012.
search and Development in Information Retrieval, pages 43–52, 2015.
[31] F. Zhou, F. De la Torre, and J. F. Cohn. Unsupervised discovery of facial events. In Proceed[22] N. Pham and R. Pagh. Fast and scalable polyings of the 2010 IEEE Computer Society Connomial kernels via explicit feature maps. In
ference on Computer Vision and Pattern RecogProceedings of the 19th ACM SIGKDD Internanition, pages 2574–2581, 2010.
tional Conference on Knowledge Discovery and
Data Mining, pages 239–247, 2013.
15

