Wasserstein Training of Restricted Boltzmann Machines

 

 

Commenting on the previous blog entry, Marco mentions that similar ideas have been presented in Wasserstein Training of Restricted Boltzmann Machines by Grégoire Montavon, Klaus-Robert Müller, Marco Cuturi

Boltzmann machines are able to learn highly complex, multimodal, structured and multiscale real-world data distributions. Parameters of the model are usually learned by minimizing the Kullback-Leibler (KL) divergence from training samples to the learned model. We propose in this work a novel approach for Boltzmann machine training which assumes that a meaningful metric between observations is given. This metric can be represented by the Wasserstein distance between distributions, for which we derive a gradient with respect to the model parameters. Minimization of this new objective leads to generative models with different statistical properties. We demonstrate their practical potential on data completion and denoising, for which the metric between observations plays a crucial role.

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 Embedding are Equivalent for Norms

It was on my list of "to feature" preprint but it looks like Ilya Razenshteyn has written a detailed blog post about it. Here is the paper: Sketching and Embedding are Equivalent for Norms by Alexandr Andoni, Robert Krauthgamer, Ilya Razenshteyn

An outstanding open question [sublinear.info, Question #5] asks to characterize metric spaces in which distances can be estimated using efficient sketches. Specifically, we say that a sketching algorithm is efficient if it achieves constant approximation using constant sketch size. A well-known result of Indyk (J. ACM, 2006) implies that a metric that admits a constant-distortion embedding into $\ell_p$ for $p\in(0,2]$ also admits an efficient sketching scheme. But is the converse true, i.e., is embedding into $\ell_p$ the only way to achieve efficient sketching?
We address these questions for the important special case of normed spaces, by providing an almost complete characterization of sketching in terms of embeddings. In particular, we prove that a finite-dimensional normed space allows efficient sketches if and only if it embeds (linearly) into $\ell_{1-\varepsilon}$ with constant distortion. We further prove that for norms that are closed under sum-product, efficient sketching is equivalent to constant-distortion embedding into $\ell_1$. Examples of such norms include the Earth Mover's Distance (specifically its norm variant, called Kantorovich-Rubinstein norm), and the trace norm (a.k.a. Schatten 1-norm or the nuclear norm). Using known non-embeddability theorems for these norms by Naor and Schechtman (SICOMP, 2007) and by Pisier (Compositio. Math., 1978), we then conclude that these spaces do not admit efficient sketches either, making progress towards answering another open question [sublinear.info, Question #7].
Finally, we observe that resolving whether "sketching is equivalent to embedding into $\ell_1$ for general norms" (i.e., without the above restriction) is equivalent to resolving a well-known open problem in Functional Analysis posed by Kwapien in 1969.

 

also of note:

• A. Andoni and I. Razenshteyn, Optimal Data-Dependent Hashing for Approximate Near Neighbors, STOC, 2015 (local copy, arXiv, five-minute talk, video). 

This image was taken by Navcam: Right B (NAV_RIGHT_B) onboard NASA's Mars rover Curiosity on Sol 889 (2015-02-05 16:30:26 UTC).

Image Credit: NASA/JPL-Caltech

  Join the CompressiveSensing subreddit or the Google+ Community 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.

emd_flow : The Constrained Earth Mover Distance Model,with Applications to Compressive Sensing

Here is an extension of the Earth Mover's distance work that allows one to use a different kind of structured sparsity. Here it might even be very an extension of the generic MMV approach. 

The Constrained Earth Mover Distance Model,with Applications to Compressive Sensing by Ludwig Schmidt, Chinmay Hegde, Piotr Indyk. 

Abstract—Sparse signal representations have emerged as powerful tools in signal processing theory and applications, and serveas the basis of the now-popular field of compressive sensing (CS).However, several practical signal ensembles exhibit additional,richer structure beyond mere sparsity. Our particular focus inthis paper is on signals and images where, owing to physicalconstraints, the positions of the nonzero coefficients do not changesignificantly as a function of spatial (or temporal) location.Such signal and image classes are often encountered in seismicexploration, astronomical sensing, and biological imaging. Ourcontributions are threefold: (i) We propose a simple, deterministicmodel based on the Earth Mover Distance that effectively capturesthe structure of the sparse nonzeros of signals belonging to suchclasses. (ii) We formulate an approach for approximating anyarbitrary signal by a signal belonging to our model. The ke yidea in our approach is a min-cost max-flow graph optimization problem that can be solved efficiently in polynomial time. (iii)We develop a CS algorithm for efficiently reconstructing signalsbelonging to our model, and numerically demonstrate its benefitsover state-of-the-art CS approaches.

The attendant code for emd_flow is on Ludwig Schmidt's code page.

Other relevant papers:

• Automatic Fault Localization Using the Generalized Earth Mover's Distance
• Approximation-Tolerant Model-Based Compressive Sensing
• Automatic Fault Localization Using the Generalized Earth Mover's Distance
• Ludwig Schmidt's thesis: Model-Based Compressive Sensing with Earth Mover’s Distance Constraints

and eventually:

• Learning Manifolds in the Wild
• Around the blogs in 80 summer hours (NIPS and more)
• SAHD: Multiscale bi-Harmonic Analysis of Digital Data Bases and Earth moving distances - Raphy Coifman

Join the CompressiveSensing subreddit or the Google+ Community 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.

SAHD: Multiscale bi-Harmonic Analysis of Digital Data Bases and Earth moving distances - Raphy Coifman

From the SAHD workshop;

Multiscale bi-Harmonic Analysis of Digital Data Bases and Earth moving distances by Raphy Coifman

Thank you to the organizers of SAHD,  David Brady, Robert Calderbank, Lawrence Carin, Ingrid Daubechies,David Dunson, Mauro Maggioni, Sayan Mukherjee, Guillermo Sapiro and Rebecca Willett for making these videos available.

Related:

• Learning Manifolds in the Wild
• Fast Earth Mover's Distance (EMD) implementation
• CS: Sparse Recovery for Earth Mover Distance
• Monday Morning Algorithm 7: Diffusion Maps for Dimensionality Reduction and Manifold Parametrization

Join the CompressiveSensing subreddit or the Google+ Community 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.

Around the blogs in 80 summer hours (NIPS and more)

Zhilin successfully defended his Ph.D. dissertation on 12/12/12. Congratulations Dr. Zhang !

Masaaki points to Compressed Sensing as a New Trend in Control

Suresh makes a summary of his thoughts about NIPS in:

• NIPS II: Deep Learning and the evolution of data models
• NIPS ruminations I

In his NIPS ruminations I Suresh mentioned this about the Earth Mover's distance:

Kernel distances: Ever since I discovered the kernel distance (as in, found it, not invented it) I've been fascinated by how it behaves more or less like the earth mover distance, but is so much easier to compute. Scott Aaronson (at his NIPS invited talk) made this joke about how nature loves ℓ 2. The kernel distance is "essentially" the ℓ variant of EMD (which makes so many things easier). There's been a series of papers by Sriperumbudur et al. on this topic, and in a series of works they have shown that (a) the kernel distance captures the notion of "distance covariance" that has become popular in statistics as a way of testing independence of distributions. (b) as an estimator of distance between distributions, the kernel distance has more efficient estimators than (say) the EMD because its estimator can be computed in closed form instead of needing an algorithm that solves a transportation problem and (c ) the kernel that optimizes the efficient of the two-sample estimator can also be determined (the NIPS paper).

We've seen EMD recently. In Learning Manifolds in the Wild by Chinmay Hegde, Aswin C. Sankaranarayanan, Richard Baraniuk made the case that one could learn manifolds through the use of the Earth Mover’s Distance on top of keypoint descriptors. Does that mean that a combination of the faster FREAKs and kernel distance might provide for a speedier way of learning manifold from images and videos ? [Update: the answer seems to be Yes]

As an aside, one of the commenters pointed out to a manuscript on the Earth Mover's distance by Cedric Villani where you get to learn (page 33) the historical nature of the concept from Monge. It is quite fascinating that indeed it has to do with moving soil from one place to another.

On the PSD matrices remark, I am reminded of the work by Frédéric Barbaresco  on Applications Radar de la Géométrie de l'information associée aux matrices de covariances : traitements spatio-temporels. It's in French but understandable, there is also a video of him on Applications of Information Geometry to Radar Signal Processing  (Interactions between symmetric cone and Information Geomtries: Bruhat-Tits and Siegel Spaces, Models for High Resolution Autoregressive Doppler Imagery). As another aside, I wonder if one could multiplex the various modailities of radar.

Sergey talks about Algebraic topology – now in compressed sensingRich talks about NuMax – A Convex Approach for Learning Near-Isometric Linear Embeddings, we featured here earlier.
Larry has New Names For Statistical Methods
Bob points out that Even humans can make extreme octave errors
Danny talks about Collaborative filtering:

• Collaborative Filtering - 3rd Generation [or] winning the kdd cup in 5 minutes!
• Collaborative filtering - 3rd generation - part 2
• Some interesting feedback for the 3rd generation cf discussed in this blog

Mathblogging features a new blog in Mathematical Instruments: Haggis the Sheep
John mentions the The Lindy effect
Laurent features the ERBlet transform (on WITS: Where is the starlet)
Emmanuel talks about a Paper: Inverting and Visualizing Features for Object Detection
Andrew ia announcing Sublinear.Info!, that page is now part of the highly technical reference page
OpenPicus has a 20% discount megasaale until december 31st.

Join the CompressiveSensing subreddit or the Google+ Community 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 Earth Mover's Distance (EMD) implementation

As the subject of Earth Mover's distance is heating up see for instance Learning Manifolds in the Wild and Sparse Recovery for Earth Mover Distance, I came across this FastEMD algorithm implementation. From the page:

Fast Earth Mover's Distance (EMD) Code
(C++ and Matlab and Java wrappers)
The code efficiently computes the Earth Mover's Distance (EMD) between two histograms or sparse histograms (signatures). The EMD is also known as Mallows, 1st Wasserstein, Monge-Kantorovich, Match and Transporatation distances. The approach was described in the paper:
"Fast and Robust Earth Mover's Distances" [, ].
EMD-HAT (a better definition of EMD for non-normalized histograms) was presented in the paper:
"A Linear Time Histogram Metric for Improved SIFT Matching" [, ].
One of the demos (demo_FastEMD4) includes a C++ implementation of the CIEDE2000 color distance. The CIEDE2000 C++ code is an adaption of Prof. Gaurav Sharma's Matlab code (used with permission). Other demos include comparison of David Lowe's SIFT descriptors, simple 1d histogram comparison and grayscale image comparison.
Quadratic Chi (QC) - code that computes the new Quadratic Chi histogram distances (proposed at ECCV 2010) very fast.

Credit: NASA/ESA

Join our Reddit Experiment, Join the CompressiveSensing subreddit 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 Manifolds in the Wild

One of Achille's heel of image processing and manifold signal processing in particular, revolves around the difficulty of building manifolds from images thanks to the apparent suboptimal capabilities of the euclidean norm. In short, the Euclidian norm doesn't provide a good means of evaluating similarity information when images are taken in different conditions (pose, illumination etc). Today's approach provides a refreshing look at this central, but often overlooked issue, through the use of the Earth Mover’s Distance on top of keypoint descriptors. Improvement could include the use of FREAK instead of SIFT and a faster Distance computations thanks to  the structure of FREAK or otherwise (see below)

Learning Manifolds in the Wild by Chinmay Hegde, Aswin C. Sankaranarayanan, Richard Baraniuk. The abtstract reads:

Despite the promise of low-dimensional manifold models for image processing, computer vision, and machine learning tasks, their utility has been hamstrung in practice by two fundamental challenges. First, practical image manifolds are non-isometric to their underlying parameter space, while the state-of-the-art manifold modeling and learning frameworks assume isometry. Second, practical image manifolds are strongly perturbed by nuisance parameters such as illumination variations, occlusions, and clutter. In this paper, we develop new theory and practical algorithms for manifold modeling, learning, and processing that directly address these challenges. To address the isometry challenge, we show that the Earth Mover’s Distance (EMD) is a more natural metric for inter-image distances than the standard Euclidean distance and use it to establish the isometry of manifolds generated by translations and rotations of a reference image. To the best of our knowledge, this is the first rigorous result on manifold isometry for generic grayscale image familes. To address the nuisance parameter challenge, we advocate an image representation based on local keypoint features and use it to define a new keypoint articulation manifold (KAM). We employ the KAM framework on a number of real-world image datasets acquired “in the wild” to demonstrate its improved performance over state-of-the-art manifold modeling approaches. A particularly compelling application of our approach is the automatic organization of large, unstructured collections of photographs gathered from the internet.

It turns out it seems possible to compute Earth Mover's Distance faster: Sublinear Time Algorithms for Earth Mover’s Distance by Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld. The abstarct reads:

We study the problem of estimating the Earth Mover’s Distance (EMD) between probability distributions when given access only to samples of the distribution. We give closeness testers and additive-error estimators over domains in [0; 1]d , with sample complexities independent of domain size – permitting the testability even of continuous distributions over infinite domains. Instead, our algorithms depend on the dimension of the domain space and the quality of the result required. We also prove lower bounds showing the dependencies on these parameters to be essentially optimal. Additionally, we consider whether natural classes of distributions exist for which there are algorithms with better dependence on the dimension, and show that for highly clusterable data, this is indeed the case. Lastly, we consider a variant of the EMD, defined over tree metrics instead of the usual `1 metric, and give tight upper and lower bounds.

Join our Reddit Experiment, Join the CompressiveSensing subreddit 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.

CVPR'11 papers. A Partial list of interest

The list of CVPR papers are out and are listed with a link to the pdf version on cvpaprs.com whenever it was found. The following is a small sample I decided to feature from their title (all the papers are here). The figure on the left is from the first beautiful paper:

• Reconstructing an image from its local descriptors (PDF) Philippe Weinzaepfel (ENS Cachan Bretagne), Herve Jegou, Patrick Perez (Technicolor)
• Earth Mover's Prototypes: a Convex Learning Approach for Discovering Activity Patterns in Dynamic Scenes (PDF, project, videos) Elisa Ricci (Fondazione Bruno Kessler), Gloria Zen (Fondazione Bruno Kessler)
• Learning invariance through imitation (PDF, supplementary material)Graham Taylor (New York University), Ian Spiro (New York University), Rob Fergus (New York University)
• Sparse Image Representation with Epitomes (PDF), Louise Benoit (ENS), Julien Mairal, Francis Bach (INRIA), Jean Ponce.
• Are Sparse Representations Really Relevant for Image Classification? (PDF), Roberto Rigamonti (EPFL), Matthew Brown (EPFL), Vincent Lepetit
• Capturing Time-of-Flight Data with Confidence PDF(draft PDF, project) Malcolm Reynolds (University College London), Jozef Doboš (University College London), Leto Peel (BAE Systems), Tim Weyrich (University College London), Gabriel Brostow
• A Non-convex Relaxation Approach to Sparse Dictionary Learning (PDF) Jianping Shi (Zhejiang University), Xiang Ren (Zhejiang University), Jingdong Wang, Guang Dai (ZJU), Zhihua Zhang
• Camera Calibration with Lens Distortion from Low-rank Textures (PDF) Zhengdong Zhang (Microsoft Research Asi), Yasuyuki Matsushita, Yi Ma
• Blind Deconvolution Using A Normalized Sparsity Measure (PDF) Dilip Krishnan (New York University), Rob Fergus
•  An Analysis of Using High-Frequency Sinusoidal Illumination to Measure the 3D Shape of Translucent Objects (PDF, project, results) Michael Holroyd (University of Virginia), Jason Lawrence (University of Virginia)
• Fusion of GPS and Structure-from-Motion using Constrained Bundle Adjustments (PDF) Maxime Lhuillier
• The Light-Path Less Traveled (PDF) Srikumar Ramalingam (MERL), Sofien Bouaziz (EPFL), Peter Sturm, Philip Torr (Oxford Brookes University)
• Fast and High-Performance Template Matching Method (PDF) Alexander Sibiryakov (Mitsubishi Electric) 
• Tag Localization with Spatial Correlations and Joint Group Sparsity (PDF) Yang Yang (The University of Queensland), Yi Yang (The University of Queensland), Zi Huang (The University of Queensland), Heng Tao Shen (The University of Queensland), Feiping Nie (University of Texas, Arlington)
• Robust Classification via Structured Sparse Representation (PDF) Ehsan Elhamifar (Johns Hopkins University), RenéVidal
• Analytical Projection Model for Non-Central Catadioptric Cameras with Quadric Mirrors (PDF, supplementary material, project,videos) Amit Agrawal, Yuichi Taguchi (Mitsubishi Electric Research Labs), Srikumar Ramalingam (MERL)
•  Sparsity-based Image Denoising via Dictionary Learning and Structural Clustering (PDF, project, code, results) Weisheng Dong (Xidian University), Xin Li (WVU), Lei Zhang (Hong Kong Polytechnic University), Guangming Shi (Xidian University)
•  Sparse Approximated Nearest Points for Image Set Classification (PDF) Yiqun Hu (University of Western Australia), Ajmal Mian (University of Western Australia), Robyn Owens (University of Western Australia)
• Intrinsic Images Decomposition Using a Local and Global Sparse Representation of Reflectance (PDF) Li Shen (I2R), Chuohao Yeo (i2r.a-star.edu.sg)
•  Accelerated Low-Rank Visual Recovery by Random Projection (PDF) Yadong Mu (NUS, Singapore), Jian Dong (NUS, Singapore), Xiaotong Yuan (NUS, Singapore), Shuicheng Yan (NUS, Singapore)
•  Is face recognition really a Compressive Sensing problem? (PDF) Qinfeng Shi (The University of Adelaide), Anders Eriksson (University of Adelaide), Anton vandenHengel, Chunhua Shen (NICTA)
• Probabilistic Gaze Estimation Without Active Personal Calibration (PDF) Jixu Chen (Rensselaer Polytechnic Inst.), Qiang Ji
• Real Time Head Pose Estimation with Random Regression Forests (PDF, project, videos) Gabriele Fanelli (ETHZ), Juergen Gall, Luc VanGool
• Multiview Specular Stereo Reconstruction of Large Mirror Surfaces (PDF)Jonathan Balzer (KAUST), Sebastian Hoefer, Juergen Beyerer
• Sparse Reconstruction Cost for Abnormal Event Detection (PDF) Yang Cong (Nanyang Technological of Unive), Junsong Yuan (Nanyang Technological University), Ji Liu (University of Wisconsin-Madison)
• Learning photographic global tonal adjustments with a database of input/output image pairs (PDF, project, videos, dataset, bibtex) Vladimir Bychkovsky (MIT / CSAIL), Sylvain Paris, Eric Chan (Adobe Systems Inc.), Fredo Durand (MIT)
• On analyzing video with very small motions (PDF) Robert Pless, Nathan Jacobs (University of Kentucky), Michael Dixon (Washington University in St. Louis), Austin Abrams (Washington University in St. Louis)
• What makes an image memorable? (PDF) Phillip Isola (MIT), Jianxiong Xiao (MIT CSAIL), Aude Oliva, Antonio Torralba
• Geometric $\ell_p$-norm Feature Pooling for Image Classification, Jiashi Feng (NUS), Bingbing Ni, Qi Tian (University of Texas at San Antonio), Shuicheng Yan
• Multi-layer Group Sparse Coding -- for Concurrent Image Classification and Annotation, Shenghua Gao (Nanyang Technological Univ.), Liang-Tien Chia (Nanyang Technological University), Ivor W. Tsang
•  L1-rotation averaging using the Weiszfeld algorithm, Richard Hartley (ANU)

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from