Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Space-efficient Feature Maps for String Alignment Kernels   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 SVM 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 address
this need by presenting the first approximation for string alignment kernels,
which we call space-efficient feature maps for edit distance with moves
(SFMEDM), by leveraging a metric embedding named edit sensitive parsing (ESP)
and feature maps (FMs) of random Fourier features (RFFs) for large-scale string
analyses. The original FMs for RFFs consume a huge amount of memory
proportional to the dimension d of input vectors and the dimension D of output
vectors, which prohibits its large-scale applications. We present novel
space-efficient feature maps (SFMs) of RFFs for a space reduction from O(dD) of
the original FMs to O(d) of SFMs with a theoretical guarantee with respect to
concentration bounds. We experimentally test SFMEDM on its ability to learn SVM
for large-scale string classifications with various massive string data, and we
demonstrate the superior performance of SFMEDM with respect to prediction
accuracy, scalability and computation efficiency.

26
The categories of this paper are: bayes-an
37
The categories of this paper are: supr-con
31
The categories of this paper are: ao-sci
33
The categories of this paper are: plasm-ph
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
36
The categories of this paper are: cmp-lg
19
The categories of this paper are: eess
13
The categories of this paper are: quant-ph
8
The categories of this paper are: hep-ex
27
The categories of this paper are: comp-gas
23
The categories of this paper are: solv-int
6
The categories of this paper are: astro-ph
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
2
The categories of this paper are: math