Sanjeev Arora

Wednesday, September 30, 2015 at 11:00 am

Sanjeev Arora

Charles C. Fitzmorris Professor of Computer Science

Princeton University


Title: Random walks on discourse spaces: a generative model approach to semantic word embeddings

Abstract: Semantic word embeddings represent words as vectors in a geometric space. They are useful  for many NLP tasks and often constructed using nonlinear/nonconvex techniques such as deep nets and energy-based models. Recently Mikolov et al (2013) showed that such embeddings exhibit linear structure that can be used to solve “word analogy tasks” such as man: woman :: king: ??.  Subsequently, Levy and Goldberg (2014) and Pennington et al (2014) tried to explain why such linear  structure should arise in embeddings derived from nonlinear methods. We point out gaps in these explanations and provide a more complete explanation in the form of a loglinear generative model for text corpora that directly models latent semantic structure in words and involves random walk in the context space.  A rigorous mathematical analysis is performed  to obtain explicit expressions for word cooccurence probabilities, which leads to a surprising explanation for  why low-dimensional word embeddings exist and why they exhibit linear structure that allows solving analogies. It also casts new light on older “Vector Space methods.” Our model and its analysis leads to several counterintuitive predictions, which are also empirically verified.

We think our methodology and generative model may be useful for other NLP tasks.

Joint work with Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski (listed in alphabetical order).

Bio: Sanjeev Arora is the Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area spans several areas of theoretical Computer Science including computational complexity and algorithm design, and  theoretical problems in machine learning.  He has received the ACM-EATCS Gödel Prize (/imgn 2001 and 2010),  Packard Fellowship (1997), the ACM Infosys Foundation Award in the Computing Sciences (2012), the Fulkerson Prize (2012), and the Simons Investigator Award (2012).

Host: Julia Chuzhoy

William Freeman

Thursday, October 15, 2015 at 11:00 am

William T. Freeman

Professor of Electrical Engineering and Computer Science

Member of Computer Science and Artificial Intelligence Laboratory

Massachusetts Institute of Technology

Title: A big world of tiny motions

Abstract: We have developed a “motion microscope” to visualize small motions by synthesizing a video with the desired motions amplified.  The project began as an algorithm to amplify small color changes in videos, allowing color changes from blood flow to be visualized. Modifications to this algorithm allow small motions to be amplified in a video.  I’ll describe the algorithms, and show color-magnified videos of adults and babies, and motion-magnified videos of throats, pipes, cars, smoke, and pregnant bellies.  These algorithms are being used in biological, civil, and mechanical engineering applications.

Having this tool led us to explore other vision problems involving tiny motions.  I’ll describe recent work in analyzing fluid flow and depth by exploiting small motions in video or stereo video sequences caused by refraction of turbulent air flow (joint work with the authors below and Tianfan Xue, Anat Levin, and Hossein Mobahi).  We have also developed a “visual microphone” to record sounds by watching objects, like a bag of chips, vibrate (joint with the authors below and Abe Davis and Gautam Mysore).

Collaborators:  Michael Rubinstein, Neal Wadhwa, and co-PI Fredo Durand.

Project web pages:

Short videos:

Radio show segment (starting at 3:28):

TED or TEDx talks by students:

Bio: William T. Freeman is a professor of Electrical Engineering and Computer Science at MIT, and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) there.  He is currently on a partial leave from MIT, starting a computer vision group at Google in Cambridge, MA.

His current research interests include machine learning applied to computer vision, Bayesian models of visual perception, and computational photography. He received outstanding paper awards at computer vision or machine learning conferences in 1997, 2006, 2009 and 2012, and test-of-time awards for papers from 1990 and 1995. Previous research topics include steerable filters and pyramids, orientation histograms, the generic viewpoint assumption, color constancy, computer vision for computer games, and belief propagation in networks with loops.

He is active in the program or organizing committees of computer vision, graphics, and machine learning conferences.  He was the program co-chair for ICCV 2005, and for CVPR 2013.

Host: Greg Shakhnarovich

Yoshua Bengio

Friday, November 20, 2015 at 11:00 am

Yoshua Bengio

Professor of Computer Science and Operations Research

Canada Research Chair in Statistical Learning Algorithms

Universite de Montreal


Slides: PDF

Title: Deep Learning Theory

Abstract: Although neural networks have long been considered lacking in theory and much remains to be done, theoretical evidence is mounting and will be discussed, to support distributed representations, depth of representation, the non-convexity of the training objective, and the probabilistic interpretation of learning algorithms (especially of the auto-encoder type, which were lacking one). The talk will focus on the intuitions behind these theoretical results.

Bio: Yoshua Bengio received a PhD in Computer Science from McGill University, Canada in 1991. After two post-doctoral years, one at M.I.T. with Michael Jordan and one at AT&T Bell Laboratories with Yann LeCun and Vladimir Vapnik, he became professor in the Department of Computer Science and Operations Research at Université de Montréal. He is the author of two books and around 200 publications, the most cited being in the areas of deep learning, recurrent neural networks, probabilistic learning algorithms, natural language processing and manifold learning. He is among the most cited Canadian computer scientists and is or has been associate editor of the top journals in machine learning and neural networks. Since ‘2000 he holds a Canada Research Chair in Statistical Learning Algorithms, since ‘2006 an NSERC Industrial Chair, since ‘2005 his is a Fellow of the Canadian Institute for Advanced Research. He is on the board of the NIPS foundation and has been program chair and general chair for NIPS. He has co-organized the Learning Workshop for 14 years and co-created the new International Conference on Learning Representations. His current interests are centered around a quest for AI through machine learning, and include fundamental questions on deep learning and representation learning, the geometry of generalization in high-dimensional spaces, manifold learning, biologically inspired learning algorithms, and challenging applications of statistical machine learning.

Host: Karen Livescu

Tandy Warnow

Friday, Feburary 12, 2016 at 11:00 am

Tandy Warnow

Professor of Computer Science and Bioengineering

The University of Illinois at Urbana-Champaign


Title: New HMM-based Methods in Sequence Alignment, Phylogenetics, and Metagenomics

Abstract: Multiple sequence alignment of datasets containing many thousands of sequences is a challenging problem with applications in phylogeny estimation, protein structure and function prediction, taxon identification of metagenomic data, etc. However, few methods can analyze large datasets, and none have been shown to have good accuracy on datasets with more than about 10,000 sequences, especially if the sequence datasets have evolved with high rates of evolution.

In this talk, I will present a new method to obtain highly accurate estimations of large-scale multiple sequence alignments and phylogenies. The basic idea is to use an ensemble of Hidden Markov Models (HMMs) to represent a “seed alignment”, and then align all the remaining sequences to the seed alignment. Our method, UPP, returns very accurate alignments, and trees on these alignments are also very accurate - even on datasets with as many as 1,000,000 sequences, or datasets that contain many fragmentary sequences. Furthermore, UPP is both fast and very scalable, so that the analysis of the 1-million taxon dataset took only 24 hours using 12 cores and small amounts of memory. Finally, this Ensemble of HMMs technique improves the accuracy of methods for other bioinformatics problems, including phylogenetic placement and taxon identification of metagenomic data.

This is joint work with Nam-phuon Nguyen and Siavash Mirarab.

Bio: Tandy Warnow is the Founder Professor of Bioengineering and Computer Science at the University of Illinois at Urbana-Champaign, a member of the Carl Woese Institute for Genomic Biology, and an affiliate in the departments of Electrical and Computer Engineering, Statistics, Mathematics, Animal Biology, Plant Biology, and Entomology. Warnow received her PhD in Mathematics in 1991 at the University of California at Berkeley under the direction of Eugene Lawler, and she did postdoctoral training with Simon Tavaré and Michael Waterman at the University of Southern California from 1991-1992. Tandy was on the faculty at the University of Pennsylvania from 1994-1999, and then joined the University of Texas, before joining the faculty at the University of Illinois in 2014. Warnow received the National Science Foundation Young Investigator Award in 1994, the David and Lucile Packard Foundation Award in Science and Engineering in 1996, a Radcliffe Institute Fellowship in 2006, and a John Simon Guggenheim Foundation Fellowship for 2011. Warnow’s international service includes being the NSF program director in charge of the Big Data program, and serving as the chair of the NIH BDMA (Biodata Management and Analysis) study section. Warnow has published more than 130 papers, and her research combines mathematics, computer science, and statistics to develop improved models and algorithms for reconstructing complex and large-scale evolutionary histories in both biology and historical linguistics. Her current research focuses on phylogeny and alignment estimation for very large datasets (10,000 to 1,000,000 sequences), estimating species trees and phylogenetic networks from collections of gene trees, and taxon identification in metagenomics.

Host: Jinbo Xu


All talks will be held at TTIC in room #526 located at 6045 South Kenwood Avenue (intersection of 61st street and Kenwood Avenue)

Parking: Street parking, or in the free lot on the corner of 60th St. and Stony Island Avenue.

For questions and comments contact Julia Chuzhoy.