Fast Kernels for String and Tree Matching

By S. V. N. Vishwanathan, Alex Smola. 2002

358 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Hardware and Architecture, Information Systems, Natural Language Processing, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Information Systems

In Natural Language Processing

In Statistical Learning Theory

Citations in the corpus

Kernel methods in machine learning (2007, neutral): “|) time by means of a tree to string conversion (Vishwanathan and Smola [146]).”
Text Mining Infrastructure in R (2008, methodology): “Further improvements for string kernel algorithms are specialized formulations using su x trees (Vishwanathan and Smola 2004) and su x arrays (Teo and Vishwanathan 2006).”
Neural methods for non-standard data (2004, methodology): “As an alternative, string kernels can directly be applied to the prefix representation of trees as proposed in [ 98 ].”
Feature Selection via Dependence Maximization (2012, background): “For many such situations we have k(x, x ′ ) = ∑ a⊑x w a # a (x)# a (x ′ ), where a ⊑ x is a substring of x (Vishwanathan and Smola, 2003; Leslie et al., 2002).”
Linear-Time Computation of Similarity Measures for Sequential Data (2008, methodology): “The comparison framework proposed in this article shares the concept of embedding sequences with all of the above kernels, in fact most of the linear-time string kernels (e.g., Joachims, 1998; Leslie et al., 2002; Vishwanathan and Smola, 2004) are enclosed in the framework.”
Support vector machines (2008, positive): “For example, there exists several variations of (22) which account for different types of subtrees, such as complete trees (Vishwanathan and Smola, 2004) and ordered trees (Kashima and Koyanagi, 2002).”
Bhattacharyya and Expected Likelihood Kernels (2003, background): “For instance, string kernels and sequential data kernels [18, 17, 6, 7, 26, 25] do not specifically address the generative hidden Markov model (HMM) literature.”
A Tree-Based Kernel for Graphs (2012, background): “Inspite of the fact that it has been demonstrated that the computation of any tree kernel for unordered trees with subtrees as their substructures is ]P -complete [11], some kernels for unordered trees have been defined in literature [14, 21].”
Generative Kernels for Tree-Structured Data (2018, background): “Their predictive performance is compared with that of syntactic tree kernels in the literature (reviewed in Section II), such as ST [26], SST [11], PT [29], subpath [31], and the ET kernels [27], [28].”
A Kernel Between Sets of Vectors (2003, background): “This idea has given rise to a whole host of novel kernels, such as string kernels (Watkins, 2000)(Lodhi et al., 2002)(Leslie et al., 2003)( Vishwanathan & Smola, 2003 ), kernels on graphs (Kondor & Lafierty, 2002), kernels on automata (Cortes et al., 2003), kernels on the statistical manifold (Jaakk”
Online learning with kernels (2001, background): “Thus, the complexity of the estimator used in prediction increases linearly over time (in some restricted situations, this can be reduced to logarithmical cost [5] or constantcost [ 6 ], yet with linear storagerequirements).”