Hash Kernels for Structured Data

By Javen Qinfeng Shi, James Petterson, Gideon Dror, J. Langford, Alex Smola, S. V. N. Vishwanathan. 2009

240 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

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 Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Recent advances in convolutional neural networks (2015, methodology): “le parameter value. Their network shrinks the storage costs of neural networks signicantly while mostly preserves the generalization performance in image classication. As pointed out in Shi et al . [188] and Weinberger et al . [189], sparsity will minimize hash collision making feature hashing even ”
Compressing Convolutional Neural Networks in the Frequency Domain (2015, methodology): “a the hashing trick) [11, 49, 60] has been previously studied as a technique for reducing model storage size.”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “Kernels between sets and more specifically between structured sets, also called hash kernels (Shi et al. 2009), have been successfully applied to strings, data streams, and unlabeled graphs.”
Self-taught hashing for fast similarity search (2010, background): “A somewhat related, but different, line of research is to use hashing representations for machine learning [41, 47].”
Simple and Scalable Response Prediction for Display Advertising (2014, background): “A theoretical analysis of learning with multiple hash functions is provided in Shi et al. [2009, theorem 2].”
Discrete Graph Hashing (2014, unknown): “During the past few years, hashing has become a popular tool for tackling a variety of large-scale computer vision and machine learning problems including object detection [6], object recognition [35], image retrieval [22], linear classifier training [19], active learning [24], kernel matrix approxi”
Provable Filter Pruning for Efficient Neural Networks (2019, background): “…Denton et al., 2014), and random projections and hashing (Arora et al., 2018; Ullrich et al., 2017; Chen et al., 2015; Weinberger et al., 2009; Shi et al., 2009) that compress a pre-trained network, to those approaches that enable sparsity by embedding sparsity as an objective directly in the…”
Modelling input texts: from Tree Kernels to Deep Learning (2015, methodology): “[146], provide an efficient way to reduce the dimensionality of the resulting feature vector, while enumerating an exponential number of all tree fragments is infeasible.”
Training and Testing Low-degree Polynomial Data Mappings via Linear SVM (2010, methodology): “For online training, some (e.g., Langford et al., 2009) have designed feature hashing techniques to control the memory use of w. Recently, feature hashing has been popular for projecting a high dimensional feature vector to a lower dimensional one (e.g., Weinberger et al., 2009; Shi et al., 2009).”
Efficient Distributed Linear Classification Algorithms via the Alternating Direction Method of Multipliers (2012, methodology): “One solution for this is to use the hash trick [18] to randomly group different features to reduce the dimension and therefore alleviate communication overheads.”
Power Iterated Color Refinement (2014, background): “Hashing is known to help to solve continuous optimization problems more efficiently, see e.g. (Shi et al. 2009).”
The Geometry of Distributed Representations for Better Alignment, Attenuated Bias, and Improved Interpretability (2020, background): “1 Structure of Word Embeddings Embedding complex data objects into a high-dimensional, but easy to work with, feature space has been a popular paradigm in data mining and machine learning for more than a decade [74, 75, 86, 97].”
Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch (2013, background): “Unfortunately, there exist a number of applications where both m and |E| are very large: for instance, Carlson et al. [4] describe an SSL system with hundreds of overlapping classes, and Shi et al [14] describe a text classification task with over 7000 classes.”
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds (2018, background): “[43] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan.”
Efficient Higher-Order CRFs for Morphological Tagging (2013, methodology): “Because the weight vector dimensionality is high for large tagsets and productive languages, we use a hash kernel (Shi et al., 2009) to keep the dimensionality constant.”
One Permutation Hashing (2012, methodology): “The variable-length hashing scheme is to some extent related to the Count-Min (CM) sketch [6] and the Vowpal Wabbit (VW) [21, 25] hashing algorithms.”
A High-Performance Syntactic and Semantic Dependency Parser (2010, methodology): “The parser is trained with the margin infused relaxed algorithm (MIRA) (McDonald et al., 2005) and combined with a hash kernel (Shi et al., 2009).”
Top Accuracy and Fast Dependency Parsing is not a Contradiction (2010, methodology): “A Hash Kernel for structured data uses a hash function h : J → { 1 ...n } to index φ , cf. maps the Shi et al. (2009). φ observations X to a feature space.”
Mathematics for Machine Learning (2020, unknown): “, sets, sequences, strings, graphs, and distributions (Ben-Hur et al., 2008; Gärtner, 2008; Shi et al., 2009; Sriperumbudur et al., 2010; Vishwanathan et al., 2010).”