Department of Computer Science and Operations Research
Canada Research Chair in Statistical Learning Algorithms
<my first name> (dot) <my last name> (at sign) umontreal (dot) ca
long-term goal is to understand
understanding the underlying principles would deliver artificial
intelligence, and I believe that learning algorithms are essential in
algorithms attempt to endow machines with the ability to capture
operational knowledge through examples, e.g., allowing a machine to
classify or predict correctly in new cases. Machine learning research
has been extremely successful in the past two decades and is now
applied in many areas of science and technology, some well known
examples including web search engines, natural language translation,
speech recognition, machine vision, and data-mining. Yet, machines
still seem to fall short of
even mammal-level intelligence in many respects. One of the remaining
frontiers of machine learning is the difficulty of learning the kind of
complicated and highly-varying functions that are necessary to perform
machine vision or natural language processing tasks at a level
comparable to humans (even a 2-year old).
See my lab's long-term
vision web page for a broader introduction.
Much of my fundamental research is funded by the National Sciences and Engineering Research Council of Canada(NSERC), the Network of Centers of Excellence on Mathematics of Information Theory and Complex Systems (MITACS), and the Canada Research Chairs.
Below you will find a brief description of selected topics, including pointers to selected recent publications. More details can be found in my publications site:
- The need for deep architectures: deep architectures are a hot topic, why should we care? to be able to represent complicated functions compactly
- Learning algorithms for deep architectures: ok, we need deep architectures, but what how do we train them?
- The need for non-local generalization and distributed representations: depth is not enough, but is often combined with distributed representations.
- Strategies for non-convex optimization of deep architectures: training deep architectures presents a fundamental non-convex optimization challenge. Any hope for general principles to succeed training them?
- Learning sequential dependencies and language modeling: we'll need to address that to deal with data involving time (language, video, music, etc.)
- The Baby AI project: putting it all together...
As described in an 2007 NSF report on Future
Challenges for the Science and Engineering of Learning, one of the
missing ingredients is depth. Deep learning methods aim at
learning of feature hierarchies with features from higher-levels of the
hierarchy formed by the composition of lower level features.
Automatically learning features at multiple levels of abstraction allows a
system to learn complex functions mapping the input to the output
directly from data, without depending completely on human crafted
features. This is especially important for higher-level abstractions,
which humans often do not know how to specify explicitly. Complexity theory theorems suggest
that one of the missing ingredients in current learning algorithms is depth of architecture (the number of
levels of composition in the learned function, e.g. number of layers of
a neural network), illustrated below
|Learning Algorithms for Deep
Until 2006, attempts at training deep architectures (e.g. multi-layer neural networks with more than 2 hidden layers) were unsuccessful. Since then, several strategies have been proposed and successfully demonstrated to train deeper architectures. A prominent example of such algorithms are the Deep Belief Networks, which are graphical models structured as stochastic neural networks with many layers, and that can be trained in an unsupervised way, one layer at a time.
Each layer represents a factor model for the layer below, and altogether we obtain a highly non-linear factor model. Since 2006, the number of papers on deep architectures has grown very quickly, several other algorithms for deep architectures have been proposed, exciting experimental results have been obtained on a wide variety of tasks, and funding agencies are starting to perceive the importance of this research question. Hinton et al introduced Deep Belief Networks in a 2006 Neural Computation paper. I wrote the following review paper on the motivations and algorithms for deep architectures:
Need for Non-Local Generalization and Distributed Representations
In addition to depth of architecture, we have found that another ingredient is crucial: distributed representations. We and others have found that most non-parametric learning algorithms suffer from the so-called curse of dimensionality. We would prefer to call it the curse of highly-varying functions or the curse of locality. That curse occurs when the only way a learning algorithm generalizes to a new case x is by exploiting only a raw notion of similarity (such as Euclidean distance) between the cases. This is typically done by the learner looking in its training examples for cases that are close to x according to some similarity measure. One can often interpret what these algorithms do as some kind of interpolation between the neighboring examples. Imagine trying to approximate a function by many small linear or constant pieces. We need at least one example for each piece. We can figure out what each piece should look like by looking mostly at the examples in the neighborhood of each piece. If the target function has a lot of variations, we'll need correspondingly many training examples. In dimension d (or on a manifold of dimension d), the number of variations may grow exponentially with d, hence the number of required examples. However, if we are lucky, we may still obtain good results when we are trying to discriminate between two highly complicated regions (manifolds), e.g. associated with two classes of objects. Even though each manifold may have many variations, they might be separable by a smooth (maybe even linear) decision surface. That is the situation where local non-parametric algorithms work well. They also work comparatively well when the distribution of examples is very noisy, because it is difficult to capture much signal then (and a smooth predictor is pretty much the best one can do).
Distributed representations are transformations of the data that compactly capture many different factors of variations present in the data. Because many examples can inform us about each of these factors, and because each factor may tell us something about examples that are very far from the training examples, it is possible to generalize non-locally, and escape the curse of dimensionality. The simplest distributed representation is a linear transformation of the input example (e.g., learned by Principal Components Analysis, Partial Least Squares, Independent Component Analysis or other more recent techniques, often called Factor Models). To represent more complicated functions, we need non-linear factor models, such as the Restricted Boltzmann Machine and Auto-Encoder introduced as building blocks of deep architectures.
This is an early paper on fighting the curse of dimensionality in high-dimensional discrete distributions using neural networks:
Non-Convex Optimization of Deep Architectures
One basic hypothesis of our work is that the main stumbling block explaining past failures at training deep architectures is due to an optimization difficulty: learning with deep architectures involves a difficult optimization problem, whose exact solution is intractable. The optimization problem is made difficult because of the presence of local minima and plateaus. However, it is encouraging to note that animals and humans seem to apply sub-optimal but wholly adequate strategies (that we have yet to fully elucidate!). The optimization problem is made difficult because of the presence of local minima and plateaus. The working strategies we know of involve at least one of these ingredients:
Our research objective is to further improve our understanding of these algorithms and to exploit it to develop new strategies for training deep architectures, taking inspiration from the natural world (how humans manage to learn such complicated tasks). An example of inspiration from the natural world comes from the way in which children develop and learn new skills. Whereas machine learning algorithms are typically provided with a single homogeneous training set of examples, children learn in stages, moving to a next stage only after having mastered the previous stage, and they care mostly about examples illustrating the concepts that are on the frontier of their understanding of the world. That is why schooling is normally organized in the form of a curriculum. This principle is also called shaping in the world of animal training, where a sequence of gradually more difficult tasks is set up for an animal.
This is a new research thread in my lab, and the only published work discussing these ideas are the following. First, we did experiments that confirm that the main issue with the traditional optimization method for deep neural networks is with the difficulty in optimizing the lower layers. We also show the importance of the unsupervised layer-wise inititialization (by opposition to supervised):
|Learning sequential dependencies and
One of the highest impact results I obtained was about the difficulty of learning sequential dependencies, either in recurrent neural networks or in dynamical graphical models (such as Hidden Markov Models). The paper below suggests that with parametrized dynamical systems (such as a recurrent neural network), the error gradient propagated through many time steps is a poor source of information for learning to capture statistical dependencies that are temporally remote. The mathematical result is that either information is not easily transmitted (it is lost exponentially fast when trying to propagate it from the past to the future through a context variable, or it is vulnerable to perturbations and noise), or the gradients relating temporally remote events becomes exponentially small for larger temporal differences.
Our recent work with unsupervised learning for deep architectures, Mnih and Hinton's (ICML'2007) work on temporal RBMs, unpublished work by James Bergstra (thesis proposal), and unpublished work by Ilya Sutskever (U. Toronto), all suggest that there may be ways around the issues introduced in the above papers in the mid-90's. Exploring these potential solutions is one of the current undertakings in my lab.