Monday, October 10, 2016

Input Convex Neural Networks - implementation -


(update: there is now a version 2)
Input Convex Neural Networks by Brandon Amos, Lei Xu, J. Zico Kolter
This paper presents the input convex neural network architecture. These are scalar-valued (potentially deep) neural networks with constraints on the network parameters such that the output of the network is a convex function of (some of) the inputs. The networks allow for efficient inference via optimization over some inputs to the network given others, and can be applied to settings including structured prediction, data imputation, reinforcement learning, and others. In this paper we lay the basic groundwork for these models, proposing methods for inference, optimization and learning, and analyze their representational power. We show that many existing neural network architectures can be made input-convex with only minor modification, and develop specialized optimization algorithms tailored to this setting. Finally, we highlight the performance of the methods on multi-label prediction, image completion, and reinforcement learning problems, where we show improvement over the existing state of the art in many cases.

 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.

Approximate Sparse Linear Regression

Some new results for the sparse regression problem and some extension of it:


Approximate Sparse Linear Regression by Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi
In the Sparse Linear Regression (SLR) problem, given a d×n matrix M and a d-dimensional vector q, we want to compute a k-sparse vector τ such that the error ||Mτ−q|| is minimized. In this paper, we present algorithms and conditional lower bounds for several variants of this problem. In particular, we consider (i) the Affine SLR where we add the constraint that ∑iτi=1 and (ii) the Convex SLR where we further add the constraint that τ≥0. Furthermore, we consider (i) the batched (offline) setting, where the matrix M and the vector q are given as inputs in advance, and (ii) the query(online) setting, where an algorithm preprocesses the matrix M to quickly answer such queries. All of the aforementioned variants have been well-studied and have many applications in statistics, machine learning and sparse recovery.
We consider the approximate variants of these problems in the "low sparsity regime" where the value of the sparsity bound k is low. In particular, we show that the online variant of all three problems can be solved with query time O~(nk−1). This provides non-trivial improvements over the naive algorithm that exhaustively searches all (nk) subsets B. We also show that solving the offline variant of all three problems, would require an exponential dependence of the form Ω~(nk/2/ek), under a natural complexity-theoretic conjecture. Improving this lower bound for the case of k=4 would imply a nontrivial lower bound for the famous Hopcroft's problem. Moreover, solving the offline variant of affine SLR in o(nk−1) would imply an upper bound of o(nd) for the problem of testing whether a given set of n points in a d-dimensional space is degenerate. However, this is conjectured to require Ω(nd) time.







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, October 07, 2016

Course: Stat212b: Topics Course on Deep Learning by Joan Bruna, UC Berkeley, Stats Department. Spring 2016.

Joan Bruna released the detailed syllabus and lectures of his recent Stat212b: Topics Course on Deep Learning that he did at UC Berkeley in the Statistics Department during the Spring 2016. From the page:
 

Topics in Deep Learning

This topics course aims to present the mathematical, statistical and computational challenges of building stable representations for high-dimensional data, such as images, text and audio. We will delve into selected topics of Deep Learning, discussing recent models from both supervised and unsupervised learning. Special emphasis will be on convolutional architectures, invariance learning, unsupervised learning and non-convex optimization.

Detailed Syllabus and Lectures

 
 
 
 
 
 
 
 
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, October 06, 2016

The Famine of Forte: Few Search Problems Greatly Favor Your Algorithm

From the conclusion of the paper:
The search framework we propose is general enough to be applied to many problem areas, such as machine learning, evolutionary search, security and hyperparameter optimization. The results are not just of theoretical importance, but help explain real-world phenomena, such as the need for exploitable dependence in machine learning and the empirical diffi culty of automated learning [12]. Our results help us understand the growing popularity of deep learning methods and unavoidable interest in automated hyperparameter tuning methods. Extending the framework to continuous settings and other problem areas (such as active learning and regression) is the focus of ongoing research.
 
 
 
The Famine of Forte: Few Search Problems Greatly Favor Your Algorithm by George D. Montanez

No Free Lunch theorems show that the average performance across any closed-under-permutation set of problems is fixed for all algorithms, under appropriate conditions. Extending these results, we demonstrate that the proportion of favorable problems is itself strictly bounded, such that no single algorithm can perform well over a large fraction of possible problems. Our results explain why we must either continue to develop new learning methods year after year or move towards highly parameterized models that are both flexible and sensitive to their hyperparameters.
 
 
 
 
 
 
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, October 05, 2016

Universal microbial diagnostics using random DNA probes

Using compressive sensing for pathogen detection.



Universal microbial diagnostics using random DNA probes by Amirali Aghazadeh, Adam Y. Lin, Mona A. Sheikh, Allen L. Chen, Lisa M. Atkins, Coreen L. Johnson, Joseph F. Petrosino, Rebekah A. Drezek and  Richard G. Baraniuk

Early identification of pathogens is essential for limiting development of therapy-resistant pathogens and mitigating infectious disease outbreaks. Most bacterial detection schemes use target-specific probes to differentiate pathogen species, creating time and cost inefficiencies in identifying newly discovered organisms. We present a novel universal microbial diagnostics (UMD) platform to screen for microbial organisms in an infectious sample, using a small number of random DNA probes that are agnostic to the target DNA sequences. Our platform leverages the theory of sparse signal recovery (compressive sensing) to identify the composition of a microbial sample that potentially contains novel or mutant species. We validated the UMD platform in vitro using five random probes to recover 11 pathogenic bacteria. We further demonstrated in silico that UMD can be generalized to screen for common human pathogens in different taxonomy levels. UMD’s unorthodox sensing approach opens the door to more efficient and universal molecular diagnostics.




 
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, October 04, 2016

Thesis: Faster algorithms for convex and combinatorial optimization by Yin Tat Lee.

Congratulations Dr. Lee !

Here is some amazing work: Faster algorithms for convex and combinatorial optimization  by Yin Tat Lee.
In this thesis, we revisit three algorithmic techniques: sparsification, cutting and collapsing. We use them to obtain the following results on convex and combinatorial optimization: 
  • Linear Programming: We obtain the first improvement to the running time for linear programming in 25 years. The convergence rate of this randomized algorithm nearly matches the universal barrier for interior point methods. As a corollary, we obtain the first ... time randomized algorithm for solving the maximum flow problem on directed graphs with m edges and n vertices. This improves upon the previous fastest running time of achieved over 15 years ago by Goldberg and Rao. 
  • Maximum Flow Problem: We obtain one of the first almost-linear time randomized algorithms for approximating the maximum flow in undirected graphs. As a corollary, we improve the running time of a wide range of algorithms that use the computation of maximum flows as a subroutine. 
  • Non-Smooth Convex Optimization: We obtain the first nearly-cubic time randomized algorithm for convex problems under the black box model. As a corollary, this implies a polynomially faster algorithm for three fundamental problems in computer science: submodular function minimization, matroid intersection, and semidefinite programming.
  • Graph Sparsification: We obtain the first almost-linear time randomized algorithm for spectrally approximating any graph by one with just a linear number of edges. This sparse graph approximately preserves all cut values of the original graph and is useful for solving a wide range of combinatorial problems. This algorithm improves all previous linear-sized constructions, which required at least quadratic time. 
  • Numerical Linear Algebra: Multigrid is an efficient method for solving large-scale linear systems which arise from graphs in low dimensions. It has been used extensively for 30 years in scientific computing. Unlike the previous approaches that make assumptions on the graphs, we give the first generalization of the multigrid that provably solves Laplacian systems of any graphs in nearly-linear expected time.
Yin Tat's publications are 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.

Fastfood Dictionary Learning for Periocular-Based Full Face Hallucination

Inpainting with FastFood. I put the faces reconstructed from the slides presentation because our discriminative human vision is far more informative at devising how good this technique is than any figure of merit.
  
Fastfood Dictionary Learning for Periocular-Based Full Face Hallucination by Felix Juefei-Xu and Marios Savvides
The kernel trick becomes a burden for some machine learning tasks such as dictionary learning, where a huge amount of training samples are needed, making the kernel matrix gigantic and infeasible to store or process. In this work, we propose to alleviate this problem and achieve Gaussian RBF kernel expansion explicitly for dictionary learning using Fastfood transform, which is an approximation of full kernel expansion. We have shown, in the context of missing data recovery through joint dictionary learning i.e. periocular-based full face hallucination, that the approximated kernel expansion using Fastfood transform for joint dictionary learning yields much better results than its image space counterparts. Also, explicit kernel expansion through Fastfood allows us to de-kernelize the reconstructed image in the feature space back to the image space, enabling applications that require reconstructive dictionaries such as cross-domain reconstruction, image super-resolution, missing data recovery, etc.
Slides are also available.



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.

Sunday, October 02, 2016

Nuit Blanche in Review (September 2016)

Since the last Nuit Blanche in Review (August 2016), Rosetta landed on a comet but we also had three Paris Machine Learning meetups, three reviews, two sunday morning insights, and many more in-depth entries. Enjoy !







In-depth:


Paris Machine Learning Meetups
Book/reviews/courses

LightOn

Hamming's time


Meetings




CfP:

Videos

Jobs:


credit: ESA, Roman Tkachenko


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, September 30, 2016

CfP: ESANN2017 Special sessions, 26 - 28 April 2017

 
Matthieu just sent me the following:
 
 
Dear Igor, 

I hope you are doing well. I am writing you because I would really appreciate if you could share some information which should interest your blog readers.

Gilles Delmaire, Gilles Roussel, and myself are organizing a special session on Environmental Signal Processing for the 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN https://www.elen.ucl.ac.be/esann/) but it would be fairer to promote all the special sessions (https://www.elen.ucl.ac.be/esann/index.php?pg=specsess), as all of them may interest the Nuit Blanche readers. I think it will really be worth attending ESANN in April 2017, in the magnificent city of Brugge!
All the special session organizers sent submission invitations to potential participants but, at least in our case, if we forget a Nuit Blanche reader who wish to submit a paper in our session, we would appreciate to be firstly contacted.
Thank you in advance for your help.
Best regards,
Matthieu
-- Matthieu PUIGT, Ph.D.
 
Thanks Matthieu ! according to the main page, prospective authors are invited to submit their contributions before 19 November 2016.

 The following special sessions will be organized at ESANN2017:
 
 
 Photo Copyright 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.

Printfriendly