Tuesday, July 21, 2015

Randomized sketches for kernels: Fast and optimal non-parametric regression

Interesting ! Sketching kernels:


Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n samples, the time and space complexity of computing the KRR estimate scale as O(n3) and O(n2) respectively, and so is prohibitive in many cases. We propose approximations of KRR based on m-dimensional randomized sketches of the kernel matrix, and study how small the projection dimension m can be chosen while still preserving minimax optimality of the approximate KRR estimate. For various classes of randomized sketches, including those based on Gaussian and randomized Hadamard matrices, we prove that it suffices to choose the sketch dimension m proportional to the statistical dimension (modulo logarithmic factors). Thus, we obtain fast and minimax optimal approximations to the KRR estimate for non-parametric regression.
 
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, July 18, 2015

Saturday Morning Videos: Information Theory in Complexity Theory and Combinatorics (Simons Institute @ Berkeley)

Here are the videos and slides of this workshop on Information Theory in Complexity Theory and Combinatorics organized at the Simons Institute at Berkeley. But in the meantime here are the links to pages that generally features both the slides and the videos (and sometimes none of the two).

 
 
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, July 17, 2015

CSJob: Postdoc and/or a Graduate Studentship, Iowa State University

Namrata Vaswani   just sent me the following:
 
  Dear Igor, 
Hope you are doing well. Could you please post this postdoc ad in your blog. Thanks much.
Namrata
http://www.ece.iastate.edu/~namrata
Sure Namrata ! Namrata is looking for a postdoc and/or a graduate student to start in her group for Fall 2015, Spring 2016 or Fall 2016.  
The proposed research lies at the intersection of machine learning for high dimensional problems and signal or information processing. Details can also be found at www.ece.iastate.edu/~namrata. Prof. Namrata Vaswani is looking for a postdoc to start in her group to work on theory and algorithms for online structured data matrix recovery problems such as online robust PCA.

Candidates with a Ph.D. in Electrical Engineering (EE), Mathematics /Applied Mathematics or Mathematical Statistics and with background related to the topics mentioned below are encouraged to apply.

Namrata's research lies at the intersection of signal/information processing and machine learning for high dimensional problems. In recent years, her group has worked on developing and analyzing online algorithms for various high-dimensional structured data recovery problems such as online sparse matrix recovery (recursive recovery of sparse vector sequences) or dynamic compressed sensing, online robust principal components' analysis (PCA) and online matrix completion, sparse PCA etc. Some ongoing work also involves proof of concept applications in video analytics and bioimaging. For more details, see her webpage (the two talks posted on this page will provide a good overview).

If you are interested, please email namrata@iastate.edu with the subject line `Postdoc application`. Please attach a copy of your resume, either a transcript (scanned or unofficial is fine) or a link to your webpage and a copy of your paper(s).
 
 
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, July 16, 2015

Random forests and kernel methods

  Thanks to Reddit, I just found this "Awesome Random Forest" page and added it to the list of highly technical reference pages. From the Reddit thread, I also noticed this reference linking random forests and kernel methods. Interesting. Without further ado:



Random forests and kernel methods by Erwan Scornet 

Abstract : Random forests are ensemble methods which grow trees as base learners and combine their predictions by averaging. Random forests are known for their good practical performance, particularly in high dimensional set-tings. On the theoretical side, several studies highlight the potentially fruitful connection between random forests and kernel methods. In this paper, we work out in full details this connection. In particular, we show that by slightly modifying their definition, random forests can be rewrit-ten as kernel methods (called KeRF for Kernel based on Random Forests) which are more interpretable and easier to analyze. Explicit expressions of KeRF estimates for some specific random forest models are given, together with upper bounds on their rate of consistency. We also show empirically that KeRF estimates compare favourably to random forest estimates.
 
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, July 15, 2015

Intersecting Faces: Non-negative Matrix Factorization With New Guarantees

The search for reasons as to why NMF works continues as witnessed today in the following preprint:



Intersecting Faces: Non-negative Matrix Factorization With New Guarantees  by  Rong Ge, James Zou

Non-negative matrix factorization (NMF) is a natural model of admixture and is widely used in science and engineering. A plethora of algorithms have been developed to tackle NMF, but due to the non-convex nature of the problem, there is little guarantee on how well these methods work. Recently a surge of research have focused on a very restricted class of NMFs, called separable NMF, where provably correct algorithms have been developed. In this paper, we propose the notion of subset-separable NMF, which substantially generalizes the property of separability. We show that subset-separability is a natural necessary condition for the factorization to be unique or to have minimum volume. We developed the Face-Intersect algorithm which provably and efficiently solves subset-separable NMF under natural conditions, and we prove that our algorithm is robust to small noise. We explored the performance of Face-Intersect on simulations and discuss settings where it empirically outperformed the state-of-art methods. Our work is a step towards finding provably correct algorithms that solve large classes of NMF 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.

Tuesday, July 14, 2015

Video: Compressive Hyperspectral Imaging via Approximate Message Passing

As New Horizons flies-by Pluto today, at a speed of 16+ km/s there will be a short window of opportunity for the spacecraft to perform the most accurate images of this planet before it continues its journey to the Kuyper belt (the speed of the spacecraft makes it impossible to orbit Pluto).




Images like the one above are taken by LORRI and are black and white (panchromatic) but the instrument that will provide much of the science data for this Pluto encounter will be Ralph 

...Ralph consists of three panchromatic (black-and-white) and four color imagers inside its Multispectral Visible Imaging Camera (MVIC), as well as an infrared compositional mapping spectrometer called the Linear Etalon Imaging Spectral Array (LEISA). LEISA is an advanced, miniaturized short-wavelength infrared (1.25-2.50 micron) spectrometer provided by scientists from NASA’s Goddard Space Flight Center. MVIC operates over the bandpass from 0.4 to 0.95 microns. Ralph’s suite of eight detectors – seven charge-coupled devices (CCDs) like those found in a digital camera, and a single infrared array detector – are fed by a single, sensitive magnifying telescope with a resolution more than 10 times better than the human eye can see. The entire package operates on less than half the wattage of an appliance light bulb.
 More detailed on this camera can be found here.

All this to say, that any improvement on obtaining hyperspectral data, such as the one provided by Ralph  during the fly-by, coupled with compression from cheap (powerwise) hardware could eventually be very useful to future space missions (please note the 6.3 watts power use of the camera). It so happens that in compressive sensing, we have the beginning of an answer as exemplified by the hardware in the CASSI imager (many of the blog entries relating to Hyperspectral imaging and ompressive sensing can be found under this tag.)

 Today, Dror and colleagues show us how to reconstruct hyperspectral images when they are taken by these compressive imagers using AMP solvers. Here is the tutorial video made by Jin Tan and Yanting Ma  followed by their preprint:




Compressive Hyperspectral Imaging via Approximate Message Passing by  Jin Tan, Yanting Ma, Hoover Rueda, Dror Baron, Gonzalo Arce

We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The CASSI imaging process can be modeled as suppressing three-dimensional coded and shifted voxels and projecting these onto a two-dimensional plane, such that the number of acquired measurements is greatly reduced. On the other hand, because the measurements are highly compressive, the reconstruction process becomes challenging. We previously proposed a compressive imaging reconstruction algorithm that is applied to two-dimensional images based on the approximate message passing (AMP) framework. AMP is an iterative algorithm that can be used in signal and image reconstruction by performing denoising at each iteration. We employed an adaptive Wiener filter as the image denoiser, and called our algorithm "AMP-Wiener." In this paper, we extend AMP-Wiener to three-dimensional hyperspectral image reconstruction. Applying the AMP framework to the CASSI system is challenging, because the matrix that models the CASSI system is highly sparse, and such a matrix is not suitable to AMP and makes it difficult for AMP to converge. Therefore, we modify the adaptive Wiener filter to fit the three-dimensional image denoising problem, and employ a technique called damping to solve for the divergence issue of AMP. Our simulation results show that AMP-Wiener in three-dimensional hyperspectral imaging problems outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given the same amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-Wiener need not tune any parameters, which simplifies the reconstruction process.
 
Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute
 
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, July 12, 2015

Sunday Morning Insight: The Challenges of Reddit's Sparse Admins/Mods Graphs and Sudden Phase Transitions


There is a large part of the internet industry that focuses on doing things faster by using the prior information that everything is on a graph (  this previous entry uses the graph to devise a reconstruction solver, companies like, Google, Facebook or Dato also use this as a central asumption) but there is very little care on finding out how the network behaves over time. Sure enough search engines like Google have developed ways to handle the dynamics of the web over time, social networks like Facebook or LinkedIn do in fact try their best in designing the right recommendation engines to avoid link/friend/job announcement fatigue but the reality is that predicting things on the dynamics of the graph is most of the time left as an empirical exercise. 
Sparse Graphs and Sudden Phase Transitions
It happened before on F##@Company, Digg, Myspace or even earlier ( see Clay Shirky's 2003 A group is its own worst enemy h/t Hugh McLeod), the Reddit on-going implosion (explained here and here) is just one of those seemingly sudden phase transitions. To put these stories in the context of what we read here on Nuit Blanche, the Reddit moderators belong to a sparse graph within the much denser population of users. That sparse graph also interacts, very modestly it seems, with the graph of paid administrators of the site. Given this tidbit of context, I wonder if some of the dynamics on Reddit could not be better foreseen using some of the user-mods-admins data and the statistical physics of networks as explained to us by Lenka Zdeborova at the Paris Machine Learning meetup #8 Season 1 ( slides How hard is it to find a needle in a haystack? ).

 
It is one thing to figure out that a graph is sparse - Duh! the number of moderators is low- it is yet another to figure out the dynamics between the sparse set of unpaid and volunteer moderators, the inner group of paid admins at Reddit and the rest of the much denser community.  The fate of Reddit hinges on its ability to mend fences between the first two communities while at the same time pleasing the third community. The first question one should ask is whether Reddit has the ability to build links and trust so that they get away from a perilious metastable region. The second question is algorithmic, as shown by Lenka and colleagues: if the wrong spectral operator is used to figure out the dynamics of these  graphs, you might be over/underestimating by a large margin the efforts it takes to get away from this metastable region.


It is one thing to build trust between communities in some holistic fashion (aka through PR and some information control), it is yet another one to quantify the fragility of these networks and the different ways to make them robust over time.
Recent work by Lenka and colleagues:

 
 
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, July 11, 2015

Slides : #ICML2015 Tutorials: Structured Prediction, Bayesian Time Series Modeling, Natural Language Understanding, Policy Search, Modern Convex Optimization

Here are the abstacts and slides of the tutorials at ICML2015

Advances in Structured Prediction

Hal Daumé III (University of Maryland) and John Langford (Microsoft Research).
Download slides.
Structured prediction is the problem of making a joint set of decisions to optimize a joint loss. There are two families of algorithms for such problems: Graphical model approaches and learning to search approaches.  Graphical models include Conditional Random Fields and Structured SVMs and are effective when writing down a graphical model and solving it is easy. Learning to search approaches, explicitly predict the joint set of decisions incrementally, conditioning on past and future decisions.  Such models may be particularly useful when the dependencies between the predictions are complex, the loss is complex, or the construction of an explicit graphical model is impossible.
We will describe both approaches, with a deeper focus on the latter learning-to-search paradigm, which has less tutorial support. This paradigm has been gaining increasing traction over the past five years, making advances in natural language processing (dependency parsing, semantic parsing), robotics (grasping and path planning), social network analysis and computer vision (object segmentation).

Bayesian Time Series Modeling: Structured Representations for Scalability

Emily Fox (University of Washington).
Download slides.
Time series of increasing complexity are being collected in a variety of fields ranging from neuroscience, genomics, and environmental monitoring to e-commerce based on technologies and infrastructures previously unavailable. These datasets can be viewed either as providing a single, high-dimensional time series or as a massive collection of time series with intricate and possibly evolving relationships between them.  For scalability, it is crucial to discover and exploit sparse dependencies between the data streams or dimensions.  Such representational structures for independent data sources have been extensively explored in the machine learning community.  However, in the conversation on big data, despite the importance and prevalence of time series, the question of how to analyze such data at scale has received limited attention and represents an area of research opportunities.
For these time series of interest, there are two key modeling components: the dynamic and relational models, and their interplay. In this tutorial, we will review some foundational time series models, including the hidden Markov model (HMM) and vector autoregressive (VAR) process.  Such dynamical models and their extensions have proven useful in capturing complex dynamics of individual data streams such as human motion, speech, EEG recordings, and genome sequences.  However, a focus of this tutorial will be on how to deploy scalable representational structures for capturing sparse dependencies between data streams. In particular, we consider clustering, directed and undirected graphical models, and low-dimensional embeddings in the context of time series.  An emphasis is on learning such structure from the data.  We will also provide some insights into new computational methods for performing efficient inference in large-scale time series.
Throughout the tutorial we will highlight Bayesian and Bayesian nonparametric approaches for learning and inference.  Bayesian methods provide an attractive framework for examining complex data streams by naturally incorporating and propagating notions of uncertainty and enabling integration of heterogenous data sources; the Bayesian nonparametric aspect allows the complexity of the dynamics and relational structure to adapt to the observed data.

Natural Language Understanding: Foundations and State-of-the-Art

Percy Liang (Stanford University).
Download slides.
Building systems that can understand human language—being able to answer questions, follow instructions, carry on dialogues—has been a long-standing challenge since the early days of AI. Due to recent advances in machine learning, there is again renewed interest in taking on this formidable task. A major question is how one represents and learns the semantics (meaning) of natural language, to which there are only partial answers. The goal of this tutorial is (i) to describe the linguistic and statistical challenges that any system must address; and (ii) to describe the types of cutting edge approaches and the remaining open problems. Topics include distributional semantics (e.g., word vectors), frame semantics (e.g., semantic role labeling), model-theoretic semantics (e.g., semantic parsing), the role of context, grounding, neural networks, latent variables, and inference. The hope is that this unified presentation will clarify the landscape, and show that this is an exciting time for the machine learning community to engage in the problems in natural language understanding.

Policy Search: Methods and Applications

Gerhard Neumann (Technische Universität Darmstadt) and Jan Peters (Technische Universität Darmstadt & Max Planck Institute for Intelligent Systems, Tübingen).
Download slides.
Policy search is a subfield in reinforcement learning which focuses on finding good parameters for a given policy parametrization. It is well suited for robotics as it can cope with high-dimensional state and action spaces, one of the main challenges in robot learning. We review recent successes of both model-free and model-based policy search in robot learning.
Model-free policy search is a general approach to learn policies based on sampled trajectories. We classify model-free methods based on their policy evaluation strategy, policy update strategy, and exploration strategy and present a unified view on existing algorithms. Learning a policy is often easier than learning an accurate forward model, and, hence, model-free methods are more frequently used in practice. How- ever, for each sampled trajectory, it is necessary to interact with the robot, which can be time consuming and challenging in practice. Model-based policy search addresses this problem by first learning a simulator of the robot’s dynamics from data. Subsequently, the simulator generates trajectories that are used for policy learning. For both model- free and model-based policy search methods, we review their respective properties and their applicability to robotic systems.

Modern Convex Optimization Methods for Large-scale Empirical Risk Minimization

Peter Richtárik (University of Edimburgh) and Mark Schmidt (University of British Columbia).
Download slides part 1 – part 2.
This tutorial reviews recent advances in convex optimization for training (linear) predictors via (regularized) empirical risk minimization. We exclusively focus on practically efficient methods which are also equipped with complexity bounds confirming the suitability of the algorithms for solving huge-dimensional problems (a very large number of examples or a very large number of features). 
The first part of the tutorial is dedicated to modern primal methods (belonging to the stochastic gradient descent variety), while the second part focuses on modern dual methods (belonging to the randomized coordinate ascent variety). While we make this distinction, there are very close links between the primal and dual methods, some of which will be highlighted. We shall also comment on mini-batch, parallel and distributed variants of the methods as this is an important consideration for applications involving big 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.

Slides #ICML2015 : Léon Bottou – Two high stakes challenges in machine learning

The talk Leon did at the Paris Machine Learning meetup last year was already thought provoking. This year, Leon has not strayed from asking the right questions. Here are the slides of his ICML2015 talk.



Abstract: This presentation describes and discusses two serious challenges:

Machine learning technologies are increasingly used in complex software systems such as those underlying internet services today or self-driving vehicles tomorrow. Despite famous successes, there is more and more evidence that machine learning components tend to disrupt established software engineering practices. I will present examples and offer an explanation of this annoying and often very costly effect. Our first high-stake challenge consists therefore in formulating sound and efficient engineering principles for machine learning applications.

Machine learning research can often be viewed as an empirical science. Unlike nearly all other empirical sciences, progress in machine learning has largely been driven by a single experimental paradigm: fitting a training set and reporting performance on a testing set. Three forces may terminate this convenient state of affairs: the first one is the engineering challenge outlined above, the second one arises from the statistics of large-scale datasets, and the third one is our growing ambition to address more serious AI tasks. Our second high-stakes challenge consists therefore in enriching our experimental repertoire, redefining our scientific processes, and still maintain our progress speed.
 
 
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