Friday, August 26, 2016

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.

Thursday, August 25, 2016

Videos: Deep Learning Summer School 2016



The videos and slides of the Deep Learning Summer School 2016 are out on VideoLectures.net:

Invited Talks


Contributed Talks



h/t Edward Grefenstette 





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.

Wednesday, August 24, 2016

How to Fake Multiply by a Gaussian Matrix

You know what happens when Random Matrices Are Too Damn Large and so yuuuggge, they cannot be held in memory nor processed ? well, the answer is to fake them till you make it. I like how the authors used the phase transition diagrams to show the similarity of two algorithms.




How to Fake Multiply by a Gaussian Matrix by Michael Kapralov, Vamsi K. Potluru, David P. Woodruff

Have you ever wanted to multiply an n×d matrix X, with nd, on the left by an m×n matrix G~ of i.i.d. Gaussian random variables, but could not afford to do it because it was too slow? In this work we propose a new randomized m×n matrix T, for which one can compute TX in only O(nnz(X))+O~(m1.5d3) time, for which the total variation distance between the distributions TX and G~X is as small as desired, i.e., less than any positive constant. Here nnz(X) denotes the number of non-zero entries of X. Assuming nnz(X)m1.5d3, this is a significant savings over the na\"ive O(nnz(X)m) time to compute G~X. Moreover, since the total variation distance is small, we can provably use TX in place of G~X in any application and have the same guarantees as if we were using G~X, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).




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.

Direct inference on compressive measurements using convolutional neural networks

 Here is another instance of the great convergence. Here the first layer of a deep network is a compressive sensing system. The results are Ok, it is just the beginning.


Direct inference on compressive measurements using convolutional neural networks by Suhas Lohit    Kuldeep Kulkarni , Pavan Turaga
Compressive imagers, e.g. the single-pixel camera (SPC), acquire measurements in the form of random projections of the scene instead of pixel intensities. Compressive Sensing (CS) theory allows accurate reconstruction of the image even from a small number of such projections. However, in practice, most reconstruction algorithms perform poorly at low measurement rates and are computationally very expensive. But perfect reconstruction is not the goal of high-level computer vision applications. Instead, we are interested in only determining certain properties of the image. Recent work has shown that effective inference is possible directly from the compressive measurements, without reconstruction, using correlational features. In this paper, we show that convolutional neural networks (CNNs) can be employed to extract discriminative non-linear features directly from CS measurements. Using these features, we demonstrate that effective high-level inference can be performed. Experimentally, using hand written digit recognition (MNIST dataset) and image recognition (ImageNet) as examples, we show that recognition is possible even at low measurement rates of about 0.1. 




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.

Tuesday, August 23, 2016

Stable Reinforcement Learning with Autoencoders for Tactile and Visual Data

Here is an interesting bit where random features are used to approximate control policy modeling in reinforcement learning and deep auto-encoders are used to figure out the latent dimension of the model. 


Stable Reinforcement Learning with Autoencodersfor Tactile and Visual Data by Herke van Hoof, Nutan Chen, Maximilian Karl , Patrick van der Smagt, Jan Peters

For many tasks, tactile or visual feedback is helpful or even crucial. However, designing controllers that take such high-dimensional feedback into account is non-trivial. Therefore, robots should be able to learn tactile skills through trial and error by using reinforcement learning algorithms. The input domain for such tasks, however, might include strongly correlated or non-relevant dimensions, making it hard to specify a suitable metric on such domains. Auto-encoders specialize in finding compact representations, where defining such a metric is likely to be easier. Therefore, we propose a reinforcement learning algorithm that can learn non-linear policies in continuous state spaces, which leverages representations learned using auto-encoders. We first evaluate this method on a simulated toytask with visual input. Then, we validate our approach on a real-robot tactile stabilization task. 






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.

Monday, August 22, 2016

Decoupled Neural Interfaces using Synthetic Gradients

Last week in Stacked Approximated Regression Machine: A Simple Deep Learning Approach we mentioned a way for neural networks to be built without a backpropagation step. Another NIPS paper proposes to do the same using a different technique. Delip talks about it on his blogThe Great Convergence continues...





Training directed neural networks typically requires forward-propagating data through a computation graph, followed by backpropagating error signal, to produce weight updates. All layers, or more generally, modules, of the network are therefore locked, in the sense that they must wait for the remainder of the network to execute forwards and propagate error backwards before they can be updated. In this work we break this constraint by decoupling modules by introducing a model of the future computation of the network graph. These models predict what the result of the modelled subgraph will produce using only local information. In particular we focus on modelling error gradients: by using the modelled synthetic gradient in place of true backpropagated error gradients we decouple subgraphs, and can update them independently and asynchronously i.e. we realise decoupled neural interfaces. We show results for feed-forward models, where every layer is trained asynchronously, recurrent neural networks (RNNs) where predicting one's future gradient extends the time over which the RNN can effectively model, and also a hierarchical RNN system with ticking at different timescales. Finally, we demonstrate that in addition to predicting gradients, the same framework can be used to predict inputs, resulting in models which are decoupled in both the forward and backwards pass -- amounting to independent networks which co-learn such that they can be composed into a single functioning corporation.




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.

Full Resolution Image Compression with Recurrent Neural Networks

The real question is not whether we are seeing another instance of the Great Convergence, but when is Deepmind going to beat the Weissmann score of Pied Piper Inc ?





This paper presents a set of full-resolution lossy image compression methods based on neural networks. Each of the architectures we describe can provide variable compression rates during deployment without requiring retraining of the network: each network need only be trained once. All of our architectures consist of a recurrent neural network (RNN)-based encoder and decoder, a binarizer, and a neural network for entropy coding. We compare RNN types (LSTM, associative LSTM) and introduce a new hybrid of GRU and ResNet. We also study "one-shot" versus additive reconstruction architectures and introduce a new scaled-additive framework. We compare to previous work, showing improvements of 4.3%-8.8% AUC (area under the rate-distortion curve), depending on the perceptual metric used. As far as we know, this is the first neural network architecture that is able to outperform JPEG at image compression across most bitrates on the rate-distortion curve on the Kodak dataset images, with and without the aid of entropy coding.




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.

Friday, August 19, 2016

Reviews: Low-Rank Semidefinite Programming:Theory and Applications / A Primer on Reproducing Kernel Hilbert Spaces

 
 
In the same spirit as the Highly Technical Reference pages, I have created an "Overviews" tag that links back to all the entries that provide a review or an overview of a specific field. Today we have two:
 
Finding low-rank solutions of semidefinite programs is important in many applications. For example, semidefinite programs that arise as relaxations of polynomial optimization problems are exact relaxations when the semidefinite program has a rank-1 solution. Unfortunately, computing a minimum-rank solution of a semidefinite program is an NP-hard problem. In this paper we review the theory of low-rank semidefinite programming, presenting theorems that guarantee the existence of a low-rank solution, heuristics for computing low-rank solutions, and algorithms for finding low-rank approximate solutions. Then we present applications of the theory to trust-region problems and signal processing.


A Primer on Reproducing Kernel Hilbert Spaces by Jonathan H. Manton, Pierre-Olivier Amblard
Reproducing kernel Hilbert spaces are elucidated without assuming prior familiarity with Hilbert spaces. Compared with extant pedagogic material, greater care is placed on motivating the definition of reproducing kernel Hilbert spaces and explaining when and why these spaces are efficacious. The novel viewpoint is that reproducing kernel Hilbert space theory studies extrinsic geometry, associating with each geometric configuration a canonical overdetermined coordinate system. This coordinate system varies continuously with changing geometric configurations, making it well-suited for studying problems whose solutions also vary continuously with changing geometry. This primer can also serve as an introduction to infinite-dimensional linear algebra because reproducing kernel Hilbert spaces have more properties in common with Euclidean spaces than do more general Hilbert spaces.
 
 

Image Credit: NASA/JPL-Caltech/Space Science Institute
W00100570.jpghttp://saturnraw.jpl.nasa.gov/multimedia/raw/?start=1#raw-364127 was taken on 2016-08-16 22:59 (UTC) and received on Earth 2016-08-17 07:42 (UTC). The camera was pointing toward SATURN, and the image was taken using the MT3 and CL2 filters.

 
 
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.

Thursday, August 18, 2016

Three Highly Technical Reference Pages: Reinforcement Learning, Deep Vision, Recurrent Neural Networks and state of the art page in object classification

 
 
Obviously, they have been added to The List.
 

 Credit: ESA/Rosetta/MPS for OSIRIS Team MPS/UPD/LAM/IAA/SSO/INTA/UPM/DASP/IDA
 
 
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 Component Pursuit for Large-Scale Inverse Covariance Estimation



The maximum likelihood estimation (MLE) for the Gaussian graphical model, which is also known as the inverse covariance estimation problem, has gained increasing interest recently. Most existing works assume that inverse covariance estimators contain sparse structure and then construct models with the l1 regularization. In this paper, different from existing works, we study the inverse co-variance estimation problem from another perspective by efficiently modeling the low-rank structure in the inverse covariance, which is assumed to be a combination of a low-rank part and a diagonal matrix. One motivation for this assumption is that the low-rank structure is common in many applications including the cli-mate and financial analysis, and another one is that such assumption can reduce the computational complexity when computing its inverse. Specifically, we propose an efficient COmponent Pursuit (COP) method to obtain the low-rank part, where each component can be sparse. For optimization, the COP method greedily learns a rank-one component in each iteration by maximizing the log-likelihood. Moreover, the COP algorithm enjoys several appealing properties including the existence of an efficient solution in each iteration and the theoretical guarantee on the convergence of this greedy approach. Experiments on large-scale synthetic and real-world datasets including thousands of millions variables show that the COP method is faster than the state-of-the-art techniques for the inverse covariance estimation problem when achieving comparable log-likelihood on test data.




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.

Printfriendly