The Case for Learned Index Structures

Here is a different kind of The Great Convergence: when neural networks go after data structures, (hashes, etc....) and eventually database systems....

The Case for Learned Index Structures by Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term learned indexes. The key idea is that a model can learn the sort order or structure of lookup keys and use this signal to effectively predict the position or existence of records. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show, that by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just provides a glimpse of what might be possible.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

ProjectionNet: Learning Efficient On-Device Deep Networks Using Neural Projections

At our weekly meeting, Iacopo talked about this recent interesting preprint: 

ProjectionNet: Learning Efficient On-Device Deep Networks Using Neural Projections by Sujith Ravi

Deep neural networks have become ubiquitous for applications related to visual recognition and language understanding tasks. However, it is often prohibitive to use typical neural networks on devices like mobile phones or smart watches since the model sizes are huge and cannot fit in the limited memory available on such devices. While these devices could make use of machine learning models running on high-performance data centers with CPUs or GPUs, this is not feasible for many applications because data can be privacy sensitive and inference needs to be performed directly "on" device.
We introduce a new architecture for training compact neural networks using a joint optimization framework. At its core lies a novel objective that jointly trains using two different types of networks--a full trainer neural network (using existing architectures like Feed-forward NNs or LSTM RNNs) combined with a simpler "projection" network that leverages random projections to transform inputs or intermediate representations into bits. The simpler network encodes lightweight and efficient-to-compute operations in bit space with a low memory footprint. The two networks are trained jointly using backpropagation, where the projection network learns from the full network similar to apprenticeship learning. Once trained, the smaller network can be used directly for inference at low memory and computation cost. We demonstrate the effectiveness of the new approach at significantly shrinking the memory requirements of different types of neural networks while preserving good accuracy on visual recognition and text classification tasks. We also study the question "how many neural bits are required to solve a given task?" using the new framework and show empirical results contrasting model predictive capacity (in bits) versus accuracy on several datasets.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Deep Learning to Hash: HashNet and DHN

Using Deep Learning to learn to hash, the Great Convergence continues. Here are two recent examples:

HashNet: Deep Learning to Hash by Continuation by Zhangjie Cao, Mingsheng Long, Jianmin Wang, Philip S. Yu

Learning to hash has been widely applied to approximate nearest neighbor search for large-scale multimedia retrieval, due to its computation efficiency and retrieval quality. Deep learning to hash, which improves retrieval quality by end-to-end representation learning and hash encoding, has received increasing attention recently. Subject to the vanishing gradient difficulty in the optimization with binary activations, existing deep learning to hash methods need to first learn continuous representations and then generate binary hash codes in a separated binarization step, which suffer from substantial loss of retrieval quality. This paper presents HashNet, a novel deep architecture for deep learning to hash by continuation method, which learns exactly binary hash codes from imbalanced similarity data where the number of similar pairs is much smaller than the number of dissimilar pairs. The key idea is to attack the vanishing gradient problem in optimizing deep networks with non-smooth binary activations by continuation method, in which we begin from learning an easier network with smoothed activation function and let it evolve during the training, until it eventually goes back to being the original, difficult to optimize, deep network with the sign activation function. Comprehensive empirical evidence shows that HashNet can generate exactly binary hash codes and yield state-of-the-art multimedia retrieval performance on standard benchmarks.

Deep Hashing Network for Efficient Similarity Retrieval by Han Zhu, Mingsheng Long, Jianmin Wang, Yue Cao

Due to the storage and retrieval efficiency, hashing has been widely deployed to approximate nearest neighbor search for large-scale multimedia retrieval. Supervised hashing, which improves the quality of hash coding by exploiting the semantic similarity on data pairs, has received increasing attention recently. For most existing supervised hashing methods for image retrieval, an image is first represented as a vector of hand-crafted or machine-learned features, followed by another separate quantization step that generates binary codes. However, suboptimal hash coding may be produced, because the quantization error is not statistically minimized and the feature representation is not optimally compatible with the binary coding. In this paper, we propose a novel Deep Hashing Network (DHN) architecture for supervised hashing, in which we jointly learn good image representation tailored to hash coding and formally control the quantization error. The DHN model constitutes four key components: (1) a sub-network with multiple convolution-pooling layers to capture image representations; (2) a fully-connected hashing layer to generate compact binary hash codes; (3) a pairwise cross-entropy loss layer for similarity-preserving learning; and (4) a pairwise quantization loss for controlling hashing quality. Extensive experiments on standard image retrieval datasets show the proposed DHN model yields substantial boosts over latest state-of-the-art hashing methods.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Factorized Binary Codes for Large-ScaleNearest Neighbor Search

Factorized Binary Codes for Large-ScaleNearest Neighbor Search by Frederick Tung , James J. Little 

 Hashing algorithms for fast large-scale nearest neighbor search transform data points into compact binary codes by applying a set of learned or randomly generated hash functions. Retrieval accuracy generally increases with the number of hash functions, but increasing the number of hash functions also increases the storage requirements of the resulting binary codes. We present a novel factorized binary codes approach that uses an approximate matrix factorization of the binary codes to increase the number of hash functions while maintaining the original storage requirements. The proposed approach does not assume a particular algorithm for generating the hash functions, and requires only that we can discover and take advantage of correlations among the hash functions. Experiments on publicly available datasets suggest that factorized binary codes work particularly well for locality-sensitive hashing algorithms.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Streaming algorithms for identification of pathogens and antibiotic resistance potential from real-time MinION (TM) sequencing

About four years ago, I tried to predict the future for August 25, 2030. In order to do this, I first mentioned The Steamrollers i.e. technologies that were exponential in nature. Nanopore sequencing was one of them. In the second installment, I mentioned different algorithms that could help in making sense of the data generated by these steamrollers (Predicting the Future: Randomness and Parsimony). Streaming was one of them. It is really no surprise, if like in hyperspectral imaging or nanopore sequencing you are producing a lot of data, your interest switch from the modeling aspect of things to how can it be helpful now and how fast.  How does it change science ? well you just need to read the following article:

The main contribution of this article is to demonstrate that despite the higher error rate, it is possible to return clinical actionable information, including species and strain identification from as few as 500 reads. We achieved this by developing novel approaches that are less sensitive to base-calling errors and which use whatever subset of genome-wide information is observed up to a point in time, rather than a panel of pre-defined markers or genes. For example, the strain typing presence/absence approach relies only on being able to identify homology to genes and also allows for a level of incorrect gene annotation.

Streaming algorithms for identification of pathogens and antibiotic resistance potential from real-time MinIONTMsequencing by Minh Duc Cao, Devika Ganesamoorthy, Alysha G. Elliott, Huihui Zhang, Matthew A. Cooper and Lachlan J.M. Coin

The recently introduced Oxford Nanopore MinION platform generates DNA sequence data in real-time. This has great potential to shorten the sample-to-results time and is likely to have benefits such as rapid diagnosis of bacterial infection and identification of drug resistance. However, there are few tools available for streaming analysis of real-time sequencing data. Here, we present a framework for streaming analysis of MinION real-time sequence data, together with probabilistic streaming algorithms for species typing, strain typing and antibiotic resistance profile identification. Using four culture isolate samples, as well as a mixed-species sample, we demonstrate that bacterial species and strain information can be obtained within 30 min of sequencing and using about 500 reads, initial drug-resistance profiles within two hours, and complete resistance profiles within 10 h. While strain identification with multi-locus sequence typing required more than 15x coverage to generate confident assignments, our novel gene-presence typing could detect the presence of a known strain with 0.5x coverage. We also show that our pipeline can process over 100 times more data than the current throughput of the MinION on a desktop computer.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Dual Purpose Hashing

Dual Purpose Hashing by Haomiao Liu, Ruiping Wang, Shiguang Shan, Xilin Chen

Recent years have seen more and more demand for a unified framework to address multiple realistic image retrieval tasks concerning both category and attributes. Considering the scale of modern datasets, hashing is favorable for its low complexity. However, most existing hashing methods are designed to preserve one single kind of similarity, thus improper for dealing with the different tasks simultaneously. To overcome this limitation, we propose a new hashing method, named Dual Purpose Hashing (DPH), which jointly preserves the category and attribute similarities by exploiting the Convolutional Neural Network (CNN) models to hierarchically capture the correlations between category and attributes. Since images with both category and attribute labels are scarce, our method is designed to take the abundant partially labelled images on the Internet as training inputs. With such a framework, the binary codes of new-coming images can be readily obtained by quantizing the network outputs of a binary-like layer, and the attributes can be recovered from the codes easily. Experiments on two large-scale datasets show that our dual purpose hash codes can achieve comparable or even better performance than those state-of-the-art methods specifically designed for each individual retrieval task, while being more compact than the compared methods.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Thesis: Rich and Efficient Visual Data Representation, Mohammad Rastegari,

Here is a new thesis, congratulations Dr. Rastegari !

Rich and Efficient Visual Data Representation by Mohammad Rastegari

Increasing the size of training data in many computer vision tasks has shown to be very effective. Using large scale image datasets (e.g. ImageNet) with simple learning techniques (e.g. linear classifiers) one can achieve state-of-the-art performance in object recognition compared to sophisticated learning techniques on smaller image sets. Semantic search on visual data has become very popular. There are billions of images on the internet and the number is increasing every day. Dealing with large scale image sets is intense per se. They take a significant amount of memory that makes it impossible to process the images with complex algorithms on single CPU machines. Finding an efficient image representation can be a key to attack this problem. A representation being efficient is not enough for image understanding. It should be comprehensive and rich in carrying semantic information. In this proposal we develop an approach to computing binary codes that provide a rich and efficient image representation. We demonstrate several tasks in which binary features can be very effective. We show how binary features can speed up large scale image classification. We present learning techniques to learn the binary features from supervised image set (With different types of semantic supervision; class labels, textual descriptions). We propose several problems that are very important in finding and using efficient image representation.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Sketching and Neural Networks

  Two subjects we used to not see in the same field. Interesting!

Sketching and Neural Networks by Amit Daniely, Nevena Lazic, Yoram Singer, Kunal Talwar

High-dimensional sparse data present computational and statistical challenges for supervised learning. We propose compact linear sketches for reducing the dimensionality of the input, followed by a single layer neural network. We show that any sparse polynomial function can be computed, on nearly all sparse binary vectors, by a single layer neural network that takes a compact sketch of the vector as input. Consequently, when a set of sparse binary vectors is approximately separable using a sparse polynomial, there exists a single-layer neural network that takes a short sketch as input and correctly classifies nearly all the points. Previous work has proposed using sketches to reduce dimensionality while preserving the hypothesis class. However, the sketch size has an exponential dependence on the degree in the case of polynomial classifiers. In stark contrast, our approach of using improper learning, using a larger hypothesis class allows the sketch size to have a logarithmic dependence on the degree. Even in the linear case, our approach allows us to improve on the pesky $O({1}/{{\gamma}^2})$ dependence of random projections, on the margin $\gamma$. We empirically show that our approach leads to more compact neural networks than related methods such as feature hashing at equal or better performance.

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Learning A Deep ℓ∞ Encoder for Hashing

In a recent blog entry, Jack described what we have been calling The Great Convergence: several fields merging because they use ML and Deep Learning as a way to reinvent their practices and algorithms. This morning, Atlas pointed out one of his preprint :

[1604.01475] Learning A Deep $\ell_\infty$ Encoder for Hashing one more push on "great convergence"! @IgorCarron https://t.co/1H7rSWDGcE

— Atlas Wang (@atlaswang) 7 avril 2016

Thanks Atlas !

Learning A Deep ℓ∞ Encoder for Hashing by Zhangyang Wang, Yingzhen Yang, Shiyu Chang, Qing Ling, Thomas S. Huang

We investigate the ℓ∞-constrained representation which demonstrates robustness to quantization errors, utilizing the tool of deep learning. Based on the Alternating Direction Method of Multipliers (ADMM), we formulate the original convex minimization problem as a feed-forward neural network, named \textit{Deep ℓ∞ Encoder}, by introducing the novel Bounded Linear Unit (BLU) neuron and modeling the Lagrange multipliers as network biases. Such a structural prior acts as an effective network regularization, and facilitates the model initialization. We then investigate the effective use of the proposed model in the application of hashing, by coupling the proposed encoders under a supervised pairwise loss, to develop a \textit{Deep Siamese ℓ∞ Network}, which can be optimized from end to end. Extensive experiments demonstrate the impressive performances of the proposed model. We also provide an in-depth analysis of its behaviors against the competitors.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding

Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding by Samet Oymak

Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g.~circulant matrices. While binary embedding has been studied extensively, theoretical results on fast binary embedding are rather limited. In this work, we build upon the recent literature to obtain significantly better dependencies on the problem parameters. A set of N points in Rn can be properly embedded into the Hamming cube {±1}k with δ distortion, by using k∼δ−3logN samples which is optimal in the number of points N and compares well with the optimal distortion dependency δ−2. Our optimal embedding result applies in the regime logN≲n1/3. Furthermore, if the looser condition logN≲n√ holds, we show that all but an arbitrarily small fraction of the points can be optimally embedded. We believe our techniques can be useful to obtain improved guarantees for other nonlinear embedding problems.

 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems / BPTree: an $\ell_2$ heavy hitters algorithm using constant memory / Approximate Hamming distance in a stream

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems by Arnab Bhattacharyya, Palash Dey, David P. Woodruff

We give the first optimal bounds for returning the $\ell_1$-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of $m$ items in $\{1, 2, \dots, n\}$ and parameters $0 < \epsilon < \phi \leq 1$, let $f_i$ denote the frequency of item $i$, i.e., the number of times item $i$ occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items $i$ for which $f_i \geq \phi m$, returns no items $j$ for which $f_j \leq (\phi -\epsilon)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq \epsilon m$ for each item $i$ that it returns. Our algorithm uses $O(\epsilon^{-1} \log\phi^{-1} + \phi^{-1} \log n + \log \log m)$ bits of space, processes each stream update in $O(1)$ worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive $\epsilon m$ error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of $\ell_1$-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.

BPTree: an $\ell_2$ heavy hitters algorithm using constant memory by Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, David P. Woodruff, Zhengyu Wang

The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. In sub-polynomial space, the strongest guarantee available is the $\ell_2$ guarantee, which requires finding all items that occur at least $\varepsilon\|f\|_2$ times in the stream, where the $i$th coordinate of the vector $f$ is the number of occurrences of $i$ in the stream. The first algorithm to achieve the $\ell_2$ guarantee was the CountSketch of [CCF04], which for constant $\varepsilon$ requires $O(\log n)$ words of memory and $O(\log n)$ update time, and is known to be space-optimal if the stream allows for deletions. The recent work of [BCIW16] gave an improved algorithm for insertion-only streams, using only $O(\log\log n)$ words of memory.
In this work, we give an algorithm "BPTree" for $\ell_2$ heavy hitters in insertion-only streams that achieves $O(1)$ words of memory and $O(1)$ update time for constant $\varepsilon$, which is optimal. In addition, we describe an algorithm for tracking $\|f\|_2$ at all times with $O(1)$ memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.

Approximate Hamming distance in a stream by Raphael Clifford, Tatiana Starikovskaya

We consider the problem of computing a $(1+\epsilon)$-approximation of the Hamming distance between a pattern of length $n$ and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem, giving Alice the first half of the stream and Bob the second half. We show the following: (1) If Alice and Bob both share the pattern then there is an $O(\epsilon^{-4} \log^2 n)$ bit randomised one-way communication protocol. (2) If only Alice has the pattern then there is an $O(\epsilon^{-2}\sqrt{n}\log n)$ bit randomised one-way communication protocol.
We then go on to develop small space streaming algorithms for $(1+\epsilon)$-approximate Hamming distance which give worst case running time guarantees per arriving symbol. (1) For binary input alphabets there is an $O(\epsilon^{-3} \sqrt{n} \log^{2} n)$ space and $O(\epsilon^{-2} \log{n})$ time streaming $(1+\epsilon)$-approximate Hamming distance algorithm. (2) For general input alphabets there is an $O(\epsilon^{-5} \sqrt{n} \log^{4} n)$ space and $O(\epsilon^{-4} \log^3 {n})$ time streaming $(1+\epsilon)$-approximate Hamming distance algorithm.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Exact Weighted Minwise Hashing in Constant Time

As I was featuring one of his work, Anshu sent me the following:

Dear Igor,

I am a regular follower of your blog.

I think the audience may be interested in two of our recent results. Take a look

1) Exact and Constant Time Weighted Minwise Hashing (Can be 60,000 times faster than Consistent Weighted Sampling) http://arxiv.org/abs/1602.08393


2) Training Deep Networks using LSH. Generally saves around 95% of computation and ideal for asynchronous training. http://arxiv.org/pdf/1602.08194v1.pdf

Thanks
Anshu

Thanks Anshu, we just featured the second work yesterday, here is the first:

Exact Weighted Minwise Hashing in Constant Time by Anshumali Shrivastava

Weighted minwise hashing (WMH) is one of the fundamental subroutine, required by many celebrated approximation algorithms, commonly adopted in industrial practice for large scale-search and learning. The resource bottleneck of the algorithms is the computation of multiple (typically a few hundreds to thousands) independent hashes of the data. The fastest hashing algorithm is by Ioffe \cite{Proc:Ioffe_ICDM10}, which requires one pass over the entire data vector, O(d) (d is the number of non-zeros), for computing one hash. However, the requirement of multiple hashes demands hundreds or thousands passes over the data. This is very costly for modern massive dataset.
In this work, we break this expensive barrier and show an expected constant amortized time algorithm which computes k independent and unbiased WMH in time O(k) instead of O(dk) required by Ioffe's method. Moreover, our proposal only needs a few bits (5 - 9 bits) of storage per hash value compared to around 64 bits required by the state-of-art-methodologies. Experimental evaluations, on real datasets, show that for computing 500 WMH, our proposal can be 60000x faster than the Ioffe's method without losing any accuracy. Our method is also around 100x faster than approximate heuristics capitalizing on the efficient "densified" one permutation hashing schemes \cite{Proc:OneHashLSH_ICML14}. Given the simplicity of our approach and its significant advantages, we hope that it will replace existing implementations in practice.

 Related ealier:
Improved Consistent Sampling, Weighted Minhash and L1 Sketching, Sergey Ioffe 

 Some of Anshu's earlier publications include:

• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS). [pdf]
  Anshumali Shrivastava and Ping Li.
  Conference on Uncertainty in Artificial Intelligence (UAI) 2015.
  
• Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment. [pdf][slides]
  Anshumali Shrivastava and Ping Li.
  International World Wide Web Conference (WWW) 2015.
  
• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). [pdf][slides][video]
  Anshumali Shrivastava and Ping Li.
  Neural Information Processing Systems (NIPS) 2014.
  Best Paper Award.
  
• A New Space for Comparing Graphs. [pdf] [slides]
  Anshumali Shrivastava and Ping Li.
  IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) 2014.
  Best Paper Award.
  
• Improved Densification of One Permutation Hashing. [pdf]
  Anshumali Shrivastava and Ping Li.
  Conference on Uncertainty in Artificial Intelligence (UAI) 2014.
  
• In Defense of Minhash over Simhash. [pdf] [slides]
  Anshumali Shrivastava and Ping Li.
  International Conference on Artificial Intelligence and Statistics (AISTATS) 2014.
  
• Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search. [pdf][slides][video]
  Anshumali Shrivastava and Ping Li.
  International Conference on Machine Learning (ICML) 2014.
  
• Codings for Random Projections. [pdf]
  Ping Li, Michael Mitzenmacher and Anshumali Shrivastava .
  International Conference on Machine Learning (ICML) 2014.
  
• Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search. [pdf] [slides]
  Anshumali Shrivastava and Ping Li.
  Neural Information Processing Systems (NIPS) 2013.
  
• Fast Near Neighbor Search in High-Dimensional Binary Data. [pdf] [slides]
  Anshumali Shrivastava and Ping Li.
  European Conference on Machine Learning (ECML) 2012.
  Top few papers invited for journal submission
  
• Fast multi-task learning for query spelling correction. [pdf]
  Xu Sun, Anshumali Shrivastava and Ping Li.
  ACM International Conference on Information and Knowledge Management (CIKM) 2012.
  
• GPU-based minwise hashing. [pdf]
  Ping Li, Anshumali Shrivastava and Christian Konig.
  International World Wide Web Conference (WWW)(Companion Volume) 2012.
  
• Query spelling correction using multi-task learning. [pdf]
  Xu Sun, Anshumali Shrivastava and Ping Li.
  International World Wide Web Conference (WWW)(Companion Volume) 2012.
  
• Hashing Algorithms for Large Scale Learning [pdf]
  Ping Li, Anshumali Shrivastava, Joshua Moore and Christian Konig.
  Neural Information Processing Systems (NIPS) 2011.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Scalable and Sustainable Deep Learning via Randomized Hashing

I very much like the following paper, especially the introduction which poses in no uncertain term the scalability issue of current architectures:

"...Deep Learning is revolutionizing big-data applications, after being responsible for groundbreaking improvements in object classification ( Krizhevsky et al., 2012) and speech recognition ( Hinton et al.,2012). With the recent upsurge in data, at a much faster rate than our computing capabilities, neural networks are growing deeper in order to process the information more effectively. Microsoft’s deep residual network (He et al., 2015) that won the ILSVRC 2015 competition had 152 layers and 3.6 billion FLOPs. To handle such large neural networks, researchers usually train them on high performance graphics cards or large clusters.

Graphic processing units (GPUs) are well suited at processing the expensive matrix multiplication operations found in the forward and back propagation steps of neural network computation. However, there are some challenges that come with using GPUs to train deep networks. For one, the amount of memory available on GPUs is limited, and so transferring data back and forth between main memory and the graphics card is a bottleneck. In addition, the disparity between network bandwidth and GPU processing speed limits scaling a GPU cluster beyond a single machine. These challenges limit the scalability of deep networks with giant parameter spaces on GPUs with current algorithms.
In distributed computing environments, the parameter space of giant deep networks is split across multiple nodes (Dean et al., 2012). This setup requires costly communication and synchronization between the parameter server to transfer the gradient and parameter updates. There is no clear way to avoid the costly synchronization without resorting to some ad-hoc breaking of the network. This ad-hoc breaking of deep networks is not well understood and is likely to hurt performance and to increase the risk of diverging. While deep networks are growing larger and more complex, there is a push for greater energy efficiency in order to satisfy the growing popularity of machine learning applications on mobile phones and low-power devices. These devices are designed for long battery life, and costly matrix multiplications although parallelizable are not energy-efficient. Recent work by (Chen et al. ,2015) demonstrates a technique to compress a neural networks parameter space through hashing in order to minimize its memory footprint. However, reducing the computational costs of neural networks, which directly translates into longer battery life, re-mains a critical issue...."

you can read the rest here: Scalable and Sustainable Deep Learning via Randomized Hashing by Ryan Spring, Anshumali Shrivastava

Current deep learning architectures are growing larger in order to learn from enormous datasets.These architectures require giant matrix multiplication operations to train millions or billions of parameters during forward and back propagation steps. These operations are very expensive from a computational and energy standpoint. We present a novel technique to reduce the amount of computation needed to train and test deep net-works drastically. Our approach combines recent ideas from adaptive dropouts and randomized hashing for maximum inner product search to select only the nodes with the highest activation efficiently. Our new algorithm for training deep networks reduces the overall computational cost,of both feed-forward pass and backpropagation,by operating on significantly fewer nodes. As a consequence, our algorithm only requires 5% of computations (multiplications) compared to traditional algorithms, without any loss in the accuracy. Furthermore, due to very sparse gradient updates, our algorithm is ideally suited for asynchronous training leading to near linear speedup with increasing parallelism. We demonstrate the scalability and sustainability (energy efficiency) of our proposed algorithm via rigorous experimental evaluations.

 

 
 
 

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Fast Cross-Polytope Locality-Sensitive Hashing

Chris of Rachel's lab let me know of the following interesting result:

Hello Igor,

Your readers may be interested in our recent paper that develops a variant of cross-polytope lsh which is both provably optimal in query time and has fast hash computations.  Here is a link to the paper:

http://arxiv.org/abs/1602.06922

Thanks,
Chris Kennedy

 Thanks Chris !





 


Fast Cross-Polytope Locality-Sensitive Hashing by Christopher Kennedy, Rachel Ward

We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is both optimal in asymptotic sensitivity and provably fast. Precisely, we substitute the random rotation in the standard cross-polytope scheme for a fast Johnson-Lindenstrauss transform followed by lifted rotation to reduce the number of hash computations from O(d2) to O(dlnd). This builds on a recent result in (Andoni, Indyk, Laarhoven, Razenshteyn, Schmidt, 2015) by providing an LSH scheme for angular distance which is not only optimal in asymptotic sensitivity, but also fast. Finally, we present a discretized version of the scheme which reduces the number of random bits to O(d) while still retaining asymptotic optimality and efficient hash computations.

 
 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.