- Monday, 08 February 2010, 11:00AM -- D.L. Pratt, 290 C
- Machine Learning Seminar
- Speaker: Charlie Tang, School of Computer Science, University of Waterloo
Title: "Sparsely Connected Deep Networks for More Robust Visual Recognition"
Abstract: Deep architectures such as the Deep Belief Networks (DBNs) are excellent at modeling high dimensional visual data. However, classification using DBNs are not very robust to variations such as occlusion and random noise if examples are not included in the training set. Due to the impractical nature of adding all possible noises that may exist in the real-world environment to the training set, it is desirable for the DBNs to be more robust to out-of-sample test images.
We will first show that by restricting the first hidden layer to be sparsely connected to the visible layer (specifically in the form of localized receptive fields), recognition is automatically improved over a standard DBN on the MNIST dataset. We will also present a denoising algorithm which tries to identify a subset of the first hidden layer nodes as been affected by noise and "ignores" them. The algorithm combines top-down and bottom-up inputs and further improves recognition results when the test images contain occlusions and noises. The denoising algorithm takes advantage of a generative model and is applicable to any deep feed-forward network with localized first layer connections.
- Tuesday, 9 February 2010, 11:00AM -- Bahen Centre, Rm. 1180
- Distinguished Lecture Series Lecture
- Speaker: Dr. Joe Marks, Vice President, Disney Research
Title: "Interactive Media Research at The Walt Disney Company"
Remarks: Speaker bio: Joe Marks grew up in Dublin, Ireland. Being more perseverant than imaginative, he earned three degrees from Harvard University. His areas of interest include computer graphics, human-computer interaction, and artificial intelligence. He has worked previously at Bolt Beranek and Newman and at Digital's Cambridge Research Laboratory. Prior to joining The Walt Disney Company he was the Research Director at Mitsubishi Electric Research Labs in Cambridge, MA, from 2000-2006.
Abstract: The research challenges in interactive media faced by the different business units of The Walt Disney Company fall in four broad categories: motion pictures, park attractions, games & sports, and media networks. Enumerating these challenges provides a key industry perspective on promising directions for future research in digital arts, experiential media systems, creative environments, and emerging media technologies.
- Tuesday, 9 February 2010, 3:15PM -- Pratt 266
- Theoretical Computer Science Seminar
- Speaker: Joshua Brody, Dartmouth College
Title: "Communication Complexity and You: A Winning Combination"
Abstract: Communication Complexity has been used to prove lower bounds and hardness
results in a wide variety of domains, from the theoretical (circuit complexity,
proof complexity) to the practical (streaming algorithms, data structures, etc.)
In this talk I'll present some recent results on two communication problems:
Gap Hamming Distance and Multiparty Pointer Jumping. The Gap Hamming Distance
problem captures the hardness of computing certain functions on data streams,
even when randomness and approximation are used. Proving sufficiently strong
lower bounds for Multiparty Pointer Jumping would resolve a major open question
in circuit complexity.
Despite the different nature of the applications, the lower-bounds proofs in
each problem use similar techniques, which should be useful in other problems as
well.
The results on Gap Hamming Distance are joint work with Amit Chakrabarti, Oded
Regev, Thomas Vidick, and Ronald de Wolf. This talk assumes no prior
knowledge of communication complexity.
- Friday, 12 February 2010, 11:00AM -- D.L.Pratt Building, Rm. 266
- Computational Vision Seminar
- Speaker: Simon Prince, University College London
Title: "Superpixel Lattices"
Abstract: Unsupervised over-segmentation of an image into superpixels is a common
preprocessing step for image parsing algorithms.
Ideally, every pixel within each superpixel region will belong to the same
real-world object. Existing algorithms generate superpixels that forfeit
many useful properties of the regular topology of the original pixels: for
example, the nth superpixel has no consistent position or relationship with
its neighbors. We propose two novel algorithms that produce superpixels that
are forced to conform to a grid (a regular superpixel lattice). Despite this
added topological constraint, these algorithms are comparable in terms of
speed and accuracy to alternative segmentation approaches. Finally, we
propose a way to learn about the regularities of images to form a prior on
the shape and size of the superpixels in the lattice.
- Friday, 12 February 2010, 11:10AM -- GB 244 - Galbraith Bldg
- Theoretical Computer Science Seminar
- Speaker: Eden Chlamtac, Weizmann Institute of Science
Title: "New Approximation Algorithms for Densest k-Subgraph"
Abstract: We consider the Densest k-Subgraph (DkS) problem: Given a graph G and
a parameter k, find a subgraph of G on k vertices with the maximum
number of edges. This is a well known optimization problem, which is a
natural optimization version of the decision problem k-CLIQUE.
The previous best known approximation ratio by Feige, Kortsarz and
Peleg in 2001 was O(n^{1/3-epsilon}) for epsilon estimated at around
1/60. We improve on this result, giving an O(n^{1/4+delta})
approximation for any delta>0.
In essence, our algorithm relies on the following principle: In a
random graph with average degree n^alpha, a planted k-subgraph can be
detected if it has average degree (strictly) greater than k^alpha. We
show that this principle largely carries over to provide results in
the same spirit for worst-case (non-random) instances.
Joint work with Aditya Bhaskara, Moses Charikar, Uriel Feige and
Aravindan Vijayaraghavan.
- Thursday, 25 February 2010, 2:00PM -- Pratt 266
- Theoretical Computer Science Seminar
- Speaker: Yi Wu, Carnegie Mellon University
Title: "Approximability of NP hard problems in Learning and CSPs"
Abstract: An alpha-approximation algorithm is an algorithm guaranteed to output a
solution that is within an alpha ratio of the optimal solution. We are
interested in the following question:
Given an NP-hard optimization problem, what is the best approximation
guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of
NP-hard problems:
Constraint Satisfaction Problems (CSPs) and Computational Learning Problems.
Our research in the field of CSPs is to show that certain Semidefinite
Programming (SDP) algorithms are the optimal polynomial time approximation
algorithm; our work in the learning area is to prove that tasks are inherently
hard; i.e., there is no better-than-trivial algorithm for the problems.
We will describe results on the approximability of several problems
from these two classes such as Max-Cut, Satisfiable 3-CSPs and
agnostic learning of monomials and low degree PTFs.
- Tuesday, 30 March 2010, 11:00AM -- Bahen Centre, Rm. 1180
- Distinguished Lecture Series Lecture
- Speaker: Professor Maja Mataric, Computer Science and Neuroscience, University of Southern California
Title: "To be announced"