A new Highly Technical Reference Page: Probabilistic-Programming.org

To be added to the list of Highly Technical Reference Pages - Aggregators. Here is: Probabilistic-Programming.org  a wiki by Daniel Roy.  From the wiki's description:

This website serves as a repository of links and information about probabilistic programming languages, including both academic research spanning theory, algorithms, modeling, and systems, as well as implementations, evaluations, and applications. If you would like to contribute to this site, please contact Daniel Roy. The site is still under construction: please help us link to relevant projects and research! 

The probabilistic programming approach

Probabilistic graphical models provide a formal lingua franca for modeling and a common target for efficient inference algorithms. Their introduction gave rise to an extensive body of work in machine learning, statistics, robotics, vision, biology, neuroscience, artificial intelligence (AI) and cognitive science. However, many of the most innovative and useful probabilistic models published by the AI, machine learning, and statistics community far outstrip the representational capacity of graphical models and associated inference techniques. Models are communicated using a mix of natural language, pseudo code, and mathematical formulae and solved using special purpose, one-off inference methods. Rather than precise specifications suitable for automatic inference, graphical models typically serve as coarse, high-level descriptions, eliding critical aspects such as fine-grained independence, abstraction and recursion.

PROBABILISTIC PROGRAMMING LANGUAGES aim to close this representational gap, unifying general purpose programming with probabilistic modeling; literally, users specify a probabilistic model in its entirety (e.g., by writing code that generates a sample from the joint distribution) and inference follows automatically given the specification. These languages provide the full power of modern programming languages for describing complex distributions, and can enable reuse of libraries of models, support interactive modeling and formal verification, and provide a much-needed abstraction barrier to foster generic, efficient inference in universal model classes.

We believe that the probabilistic programming language approach within AI has the potential to fundamentally change the way we understand, design, build, test and deploy probabilistic systems. This approach has seen growing interest within AI over the last 10 years, yet the endeavor builds on over 40 years of work in range of diverse fields including mathematical logic, theoretical computer science, formal methods, programming languages, as well as machine learning, computational statistics, systems biology, probabilistic AI.

  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.

Talking Machine Season 2 on Kickstarter: Human Conversation about Machine Learning

The second season of Talking Machine is on Kickstarter. If you liked this unique podcast during the first season like I did and which provides the ML community a voice, you might be interested in supporting them for the second season. 
    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.

CSPDEs: Compressed-sensing based approximation of solutions to high-dimensional operator equations - implementation -

 

Here is a follow-up to Compressed Sensing Petrov-Galerkin Approximations for Parametric PDEs about a paper submitted to SamPTA ( e paper: Compressed Sensing Petrov-Galerkin Approximations for Parametric PDEs by Jean-Luc Bouchot, Benjamin Bykowski, and Holger Rauhut, Christoph Schwab ). Well, Jean-Luc just mentioned in a tweet that there is now an implementationon Github: Compressed-sensing based approximation of solutions to high-dimensional operator equations. 

Thanks Jean-Luc for the heads-up.

  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.

Saturday Morning Videos: Videos and Slides, Deep Learning Summer School, Montreal 2015

 

Here are the videos and attendant slides of the Deep Learning Summer School that took place in Montreal this past August. Enjoy !

• Introduction to Machine Learning (slides) Pascal Vincent 
• Deep Learning:Theoretical Motivations (slides) Yoshua Bengio  
• Deep Generative Models ( slides) Yoshua Bengio
• Training Deep Neural Networks ( slides ) Hugo Larochelle
• Convolutional Networks ( slides ) Honglak Lee  
• Stacks of Restricted Boltzmann Machines ( slides ) Honglak Lee
• NLP and Deep Learning 1: Human Language & Word Vectors ( slides ) Christopher Manning
• Variational Autoencoder and Extensions ( slides) Aaron Courville
• Deep NLP Recurrent Neural Networks ( slides ) Richard Socher
• Tutorial on Neural Network Optimization Problems ( slides ) Ian Goodfellow
• Multilayer Neural Networks ( slides ) Léon Bottou
• Learning to Compare ( slides ) Graham Taylor
• Deep Learning ( slides ) Ruslan Salakhutdinov
• Deep Learning for Distribution Estimation ( slides ) Hugo Larochelle
• Deep NLP Applications and Dynamic Memory Networks (slides ) Richard Socher
• Memory, Reading, and Comprehension (slides ) Phil Blunsom
• Smooth, Finite, and Convex Optimization Deep Learning Summer School  ( slides ) Mark Schmidt
• On manifolds and autoencoders ( slides ) Pascal Vincent
• Speech Recognition and Deep Learning  ( slides ) Adam Coates
• Non Smooth, Non Finite, and Non Convex Optimization ( slides ) Mark Schmidt  Visual features: From Fourier to Gabor ( slides ) Roland Memisevic
• Adversarial Examples (slides) Ian Goodfellow
• Seeing People with Deep Learning (slides ) Graham Taylor
• NLP and Deep Learning 2: Compositional Deep Learning  (slides ) Christopher Manning
• Undirected Graphical Models ( slides ) Aaron Courville
• Multilayer Neural Networks (slides) Léon Bottou
• Deep Learning 2  (slides) Ruslan Salakhutdinov
• From Language Modelling to Machine Translation ( slides ) Phil Blunsom
• Deep Learning (hopefully faster)  (slides) Adam Coates
• Visual features II ( slides) Roland Memisevic

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute

In this small section of the larger crescent image of Pluto, taken by NASA's New Horizons just 15 minutes after the spacecraft's closest approach on July 14, 2015, the setting sun illuminates a fog or near-surface haze, which is cut by the parallel shadows of many local hills and small mountains. The image was taken from a distance of 11,000 miles (18,000 kilometers), and the width of the image is 115 miles (185 kilometers). 

 

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.

A comment on "Phase Transitions in Group Testing "

 

 

Following this entry on Phase Transitions in Group Testing, I emailed the following to Volkan:
 

Volkan,
Congrats on the SODA acceptance!
I wrote a small blurb on it on Nuit Blanche today as regards to previous work. Since group testing is exceptionnally important and as a consequence is seen from many different angles and communities, I have made a similar comment to the one I made of Kannan's recent preprint, i.e. if I am coming from the outside, which I really am, I am wondering how the 2007 paper of Mezart or the more recent paper of Krzakala et al fit with your analysis. I used to underestimate the physicists within the context of CS and related fields but since 2011 I think it is important to pay particular attention to their findings.
Cheers,
Igor.

Volkan and Jon kindly responded to my query:

Dear Igor,


We are quite excited about the SODA acceptance. Thanks also a lot for the mention.


You discuss the 2007 paper by Mezard, and the more recent one by Zhang, Krzakala and others in the blog. We think that the more relevant paper in the context of our work is the former, since the latter, among other things, focuses on linear group testing instead of Boolean group testing (as mentioned in the response by Kannan Ramchandran to your earlier blog post).


We actually already found out about Mezard's paper some time after we wrote the initial version, and we will cite it in the final version.


The goals of our paper and Mezard's are similar, seeking sharp thresholds on the number of measurements above which the error probability vanishes, but below which the error probability tends to one. However, the analysis techniques are different, and as we outline below, there is actually very little overlap in terms of results.


Perhaps the main difference is in the relevant regimes of theta (the value such that #defectives ~ (#items)^theta) - we get phase transitions only for sufficiently small theta, whereas Mezard gets phase transitions only for sufficiently large theta. Note that Mezard's beta corresponds to our 1-theta, but the description below use our own convention.


Mezard's analysis uses a few heuristic arguments that are not verified for all theta - in particular, see the comments on short loops just after (9), before (19), and after (29). They give arguments (some rigorous and some heuristic) revealing for which choices of beta this "short loops" assumption should be valid, and it appears that the best they get is $beta < 1/6$ ($ theta > 5/6 $) rigorously, and $ beta < 1/3 $ ($ theta > 2/3 $) non-rigorously. In fact, on Page 10 they give numerical simulations showing that the assumption is *invalid* for beta = 2/3 (theta = 1/3). There is also mention of "replica symmetry" just before (35) - this technique has been used a fair bit in information-theoretic studies, and while we are not quite familiar with it ourselves, our understanding is that it is known to be rigorous in some cases but not others.


In contrast, the main outcome of our analysis is a rigorous phase transition for $ theta < 1/3 $, which does not overlap with the regime where Mezard's analysis is rigorous. To the best of our judgement, Mezard's analysis does not recover our thresholds in this regime, even heuristically. Our results reveal that Bernoulli matrix designs are asymptotically optimal in this regime, even matching the optimal thresholds for adaptive measurements. In contrast, the discussion around (43) in Mezard's paper suggests that different designs (the ones they call R-R and R-P) are better for large theta (small beta). It might be interesting to see if such designs can also be handled in our framework.


We also briefly mention two additional contributions in our paper: Sharp thresholds for a noisy setting, and nearly-sharp bounds for the case of partial recovery.


We hope that this response is useful.

Jon & Volkan
-------
Prof. Volkan Cevher
Laboratory for Information and Inference Systemshttp://lions.epfl.ch 

 It was useful, thank you very much Volkan and Jon for your kind answer !

 

Credits: NASA/JHUAPL/SwRI)

Closer Look: Majestic Mountains and Frozen Plains: Just 15 minutes after its closest approach to Pluto on July 14, 2015, NASA’s New Horizons spacecraft looked back toward the sun and captured this near-sunset view of the rugged, icy mountains and flat ice plains extending to Pluto’s horizon. The smooth expanse of the informally named Sputnik Planum (right) is flanked to the west (left) by rugged mountains up to 11,000 feet (3,500 meters) high, including the informally named Norgay Montes in the foreground and Hillary Montes on the skyline. The backlighting highlights more than a dozen layers of haze in Pluto’s tenuous but distended atmosphere. The image was taken from a distance of 11,000 miles (18,000 kilometers) to Pluto; the scene is 230 miles (380 kilometers) across.

 

 

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.

Entropy-Scaling Search of Massive Biological Data - implementation -

A continuation of the Compressive Genomics approach:

  

Entropy-Scaling Search of Massive Biological Data by Y. William Yu, Noah M. Daniels, David Christian Danko, Bonnie Berger

Highlights

• •We describe entropy-scaling search for finding approximate matches in a database
• •Search complexity is bounded in time and space by the entropy of the database
• •We make tools that enable search of three largely intractable real-world databases
• •The tools dramatically accelerate metagenomic, chemical, and protein structure search

Summary

Many datasets exhibit a well-defined structure that can be exploited to design faster search tools, but it is not always clear when such acceleration is possible. Here, we introduce a framework for similarity search based on characterizing a dataset’s entropy and fractal dimension. We prove that searching scales in time with metric entropy (number of covering hyperspheres), if the fractal dimension of the dataset is low, and scales in space with the sum of metric entropy and information-theoretic entropy (randomness of the data). Using these ideas, we present accelerated versions of standard tools, with no loss in specificity and little loss in sensitivity, for use in three domains—high-throughput drug screening (Ammolite, 150× speedup), metagenomics (MICA, 3.5× speedup of DIAMOND [3,700× BLASTX]), and protein structure search (esFragBag, 10× speedup of FragBag). Our framework can be used to achieve “‘compressive omics,” and the general theory can be readily applied to data science problems outside of biology (source code: http://gems.csail.mit.edu).

Obviously the implementation is here.

  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.

Locality-sensitive Hashing without False Negatives

 

Locality-sensitive Hashing without False Negatives by Rasmus Pagh

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (FOCS '98). The efficiency of the new construction essentially matches their bound if cr=log(n)/k, where n is the number of points in the data set and k∈N, and differs from it by at most a factor ln(4)<1.4 in the exponent for general values of cr. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

  Credits: ESA/Rosetta/MPS for OSIRIS Team MPS/UPD/LAM/IAA/SSO/INTA/UPM/DASP/IDA

This image shows a portion of the Seth region on comet 67P/Churyumov-Gerasimenko, exhibiting a fractured scarp and a debris field at the foot of the cliff suggesting a progressive process of 'mass-wasting'.
The image was taken by Rosetta's OSIRIS narrow-angle camera.
An annotated version of the image with an indication of the physical scale is available here, as part of a composite image.


 

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.

Phase Transitions in Group Testing

Great, phase transitions in group testing problems!

 

 Much like previously, when I don't see a citation in the reference section I always wonder if the paper provides a new or a very new insight from previously [0,1,2,3]. What is most fascinating here is that some of these recent results on group testing, are coming from different communities and it is definitely a challenge to delineate which work provides the most advances. 

 

For one, I am also convinced that, much like what happened in compressive sensing, the use of empirical phase transitions (read the Map Makers)  goes a long way toward avoid endless discussions about asymptotics for real life reconstruction solvers. Without further due:

Phase Transitions in Group Testing  by Scarlett, Jonathan; Cevher, Volkan

We consider the fundamental limits on the number of tests required for the group testing problem, which has applications in medical testing, fault detection, communication protocols, pattern matching, and database systems. Specifically, we have p items labeled 1,…,p, among which a uniformly random subset S of cardinality k are defective. The goal is to recover the set S based on n possibly noisy measurements, each taking the form Y = \boldsymbol{1}\bigg{ \bigcup_{i \in S} {X_i = 1} \bigg} \oplus Z, \nonumber where X=(X1,…,Xp)∈0,1p is a measurement vector indicating the items involved in each test, and Z∈0,1 represents possible noise under modulo-2 addition. We consider Bernoulli designs, in which each entry of each measurement vector is independently drawn at random from a Bernoulli distribution. In the noiseless case with k=Θ(pθ) (θ≤13), we show the following for an optimal recovery algorithm: n \ge \Big( k\log_2\frac{p}{k} \Big) (1+\eta) \implies \PP[\mathrm{error}] \to 0 \nonumber
n \le \Big( k\log_2\frac{p}{k} \Big) (1-\eta) \implies \PP[\mathrm{error}] \to 1 \nonumber for any η>0, where an error means that S^≠S, with S^ denoting the estimate of S. That is, we provide an exact threshold at which the error probability under goes a phase transition from 0 to 1, for a measurement-optimal recovery rule minimizing the required number of measurements regardless of the computational complexity. The same threshold was previously shown to be the best possible when the measurement vectors are designed adaptively, with each vector chosen based on the outcomes of previous tests. Thus, despite being non-adaptive, Bernoulli designs are asymptotically optimal when θ≤13. In the case of partial recovery, we show that n \le \Big( (1-\alpha^{*}) k\log_2\frac{p}{k} \Big) (1-\eta) \implies \PP[\mathrm{error}] \to 1, \nonumber for any η>0, where an error means that |S∖S^|≥α∗|S| or |S^∖S|≥α∗|S|, so that α∗ indicates the allowed ``distance'' from S^ to S. Thus, there is little gain to be obtained in the required number of measurements even under this relaxed criterion. Finally, analogous necessary and sufficient conditions are derived for the noisy setting with Z∼Bernoulli(ρ), and we again provide exact thresholds for sufficiently small θ. Our analysis takes a novel approach revealing that the error probability is characterized by tail probabilities containing quantities of the form ı(x;y):=logPY|X(y|x)PY(y), permitting precise characterizations due to the fact that independent summations concentrate around their mean. This approach is a significant departure from widely-used tools such as maximum-likelihood decoding and Fano's inequality, and leads to sharper bounds for the case that k scales with p, as well as the stronger statement Pr[error]→1 (as opposed to merely Pr[error]↛0) in the converse bounds.

As a reminder, all the preprints/papers mentioned on this blog related to Group Testing are listed under the GroupTesting tag. There are 50 blog entries using that tag. A while ago, I explained how compressive sensing works on Quora using the concepts behind group testing: What is compressed sensing (compressive sampling) in layman's terms?

[0] Group testing with Random Pools: Phase Transitions and Optimal Strategy by  M. Mézard, M.Tarzia, C. Toninelli

The problem of Group Testing is to identify defective items out of a set of objects by means of pool queries of the form "Does the pool contain at least a defective?". The aim is of course to perform detection with the fewest possible queries, a problem which has relevant practical applications in different fields including molecular biology and computer science. Here we study GT in the probabilistic setting focusing on the regime of small defective probability and large number of objects, p→0 and N→∞. We construct and analyze one-stage algorithms for which we establish the occurrence of a non-detection/detection phase transition resulting in a sharp threshold, M¯, for the number of tests. By optimizing the pool design we construct algorithms whose detection threshold follows the optimal scaling M¯∝Np|logp|. Then we consider two-stages algorithms and analyze their performance for different choices of the first stage pools. In particular, via a proper random choice of the pools, we construct algorithms which attain the optimal value (previously determined in Ref. [16]) for the mean number of tests required for complete detection. We finally discuss the optimal pool design in the case of finite p.

see recently also:

1. Group Testing and SAFFRON
2. SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing based on Sparse-Graph Codes"
3. Non-adaptive pooling strategies for detection of rare faulty items / Improved Constructions for Non-adaptive Threshold Group Testing

 

 Potentially relevant

• The Compressive Sensing Handle
• Group Testing and Its Connection to Compressed Sensing.
• CS: Group Testing and Sparse Signal Recovery, A linear solution to the 12-balls problem
• CS: Ain't the Power of Interwebs Great or What ?
• Boolean Compressed Sensing and Noisy Group Testing by George Atia, and Venkatesh Saligrama
• Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction by Dino Sejdinovic, Oliver Johnson.
• Superselectors: Efficient Constructions and Applications by Ferdinando Cicalese, Ugo Vaccaro.
• Derandomization and Group Testing by Mahdi Cheraghchi.
• Improved Constructions for Non-adaptive Threshold Group Testing by Mahdi Cheraghchi.
• Venkatesh Saligrama - Noisy Group Testing and Boolean Compressed Sensing
• Group Testing and Sparse Recovery by Mark Iwen
• Compressed Sensing with Probabilistic Measurements: A Group Testing Solution by Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin Vetterli

 

 

 

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.