IDeAS

Fall 2017

IDeAS Seminar: Towards de-mystification of deep learning: function space analysis of the representation layers

Speaker: 
Shai Dekel, Tel Aviv University
Date: 
Sep 19 2017 - 2:30pm
Event type: 
IDeAS
Room: 
McDonnell Hall, Room 102A
Abstract: 

We propose a function space approach to Representation Learning [1] and the analysis of the representation layers in deep learning architectures. We show how to compute a `weak-type'  Besov smoothness index that quantifies the geometry of the clustering in the feature space. This approach was already applied successfully to improve the performance of machine learning algorithms such as the Random Forest [2] and tree-based Gradient Boosting [3]. Our experiments demonstrate that in well-known and well-performing trained  networks, the Besov smoothness of the training set, measured in the corresponding hidden layer feature map representation, increases from layer to layer which relates to the `unfolding' of the clustering in the feature space. We also contribute to the understanding of generalization [4] by showing how the Besov smoothness of the representations, decreases as we add more mis-labeling to the training data. We hope this approach will contribute to the de-mystification of some aspects of deep learning.  

References:

[1] Y. Bengio , A. Courville and P. Vincenty, Representation Learning: A Review and New Perspectives, IEEE Transactions on Pattern Analysis and Machine Intelligence 8 (2013), 1798-1828. 

[2] O. Elisha and S. Dekel , Wavelet decompositions of Random Forests - smoothness analysis,sparse approximation and applications, Journal of machine learning research 17 (2016), 1-38.

[3] S. Dekel, O. Elisha and O. Morgan, Wavelet decomposition of Gradient Boosting, preprint. 

[4] C. Zhang, S. Bengio, M. Hardt, B. Recht and O. Vinyals, Understanding deep learning requires rethinking generalization, In ICLR 2017 conference proceedings. 

Shai serves as Head of AI at WIX and is a visiting associate professor at the school of mathematical sciences at Tel-Aviv University.  For further information see: https://www.shaidekel.com/

IDeAS Seminar: Stability of some super-resolution problems

Speaker: 
Dmitry Batenkov, MIT
Date: 
Sep 27 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

The problem of computational super-resolution asks to recover an object from its noisy and limited spectrum. In this talk, we consider two inverse problems of this flavor, mainly from the point of view of stability estimates. In the first problem, we assume that the object's spectrum is a finite sum of exponentials modulated by polynomials (extending the well-researched case where the polynomials are constants). We derive upper bounds on the problem condition number and show that the attainable resolution exhibits Hölder-type continuity with respect to the noise level [1,3]. As an application we consider the approximation of a piecewise-smooth function from its Fourier coefficients. We can show that the asymptotic accuracy of our approach is only dictated by the smoothness of the function between the jumps, even if the jump locations are not known [2].

The second problem is concerned with on-going work on the weighted extrapolation problem on the real line for functions of finite exponential type where we abandon the sparsity assumption. It turns out that the extrapolation range scales logarithmically with the noise level, while the pointwise extrapolation error exhibits again a Hölder-type continuity.

References:

[1] A. Akinshin, D. Batenkov, and Y. Yomdin, “Accuracy of spike-train Fourier reconstruction for colliding nodes,” in 2015 International Conference on Sampling Theory and Applications (SampTA), 2015, pp. 617–621.

[2] D. Batenkov, “Complete algebraic reconstruction of piecewise-smooth functions from Fourier data,” Math. Comp., vol. 84, no. 295, pp. 2329–2350, 2015

[3] D. Batenkov, “Stability and super-resolution of generalized spike recovery,” Applied and Computational Harmonic Analysis, http://dx.doi.org/10.1016/j.acha.2016.09.004.

Dmitry Batenkov is a postdoctoral researcher at the Massachusetts Institute of Technology. His research interests include applied harmonic analysis, approximation theory, numerical analysis, sparse representations, sampling theory and inverse problems.  http://dimabatenkov.info

 

IDeAS Seminar: When does an algorithm become a legitimate subject of study?

Speaker: 
Veit Elser, Cornell University
Date: 
Oct 11 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Suppose you want to solve a combinatorially hard problem. Option one is to think really hard about the problem and design an algorithm that guarantees a solution. A second option is to try a “mystery” algorithm that comes without any guarantee of success but in practice usually outperforms any of the algorithms you have designed. Is there a point when you should shift your focus of study to the mystery algorithm? Does the mystery algorithm know something that you do not?

This talk explores the questions above for the case of hard feasibility problems that are efficiently solved by iterated maps generated by projections to non-convex sets. There is a strong analogy with mechanics. When applied to unfeasible instances these iterated maps sample a probability density in a high dimensional space, analogous to the attractor of a strongly mixing dynamical system. It is in this sense that the iterated map performs an exhaustive search. Feasible instances differ only in the existence of an attractive fixed point at some unknown location on the attractor. To improve the iterated-map algorithm, one can dramatically increase the rate of discovery of the solution fixed point by reducing the Kolmogorov-Sinai entropy of the attractor. These ideas will be illustrated with three applications: bit retrieval (phase retrieval on 2-valued sequences), latin-square completion and graph coloring.

IDeAS Seminar: On multi-dimensional compact solitary patterns

Speaker: 
Philip Rosenau, Tel Aviv University
Date: 
Oct 17 2017 - 2:30pm
Event type: 
IDeAS
Room: 
McDonnell Hall, Room 102A
Abstract: 

As though to compensate for the rarity of multidimensional integrable systems in higher dimensions, spatial extensions of many of the well-known nonlinear dispersive equations on the line, exhibit a remarkably rich variety of solitary patterns unavailable in 1-D. Our work systematizes this observation with a special attention paid to compactons - solitary waves with compact support - where this effect is found to be far more pronounced and begets a zoo of multi-dimensional compact solitary patterns. 

One manifestation of this phenomenon is found in the sublinear NLS and Complex Klein-Gordon where the compactons inducing mechanism coupled with azimuthal spinning may expel the compact vortices from the origin to form a finite or countable number of genuine ring-vortices. Such rings are an exclusive feature of compacton supporting systems. 

Click here for graphic

IDeAS Seminar: Iron Age Hebrew Epigraphy in the Silicon Age - An Algorithmic Approach To Study Paleo-Hebrew Inscriptions

Speaker: 
Barak Sober, Tel Aviv University
Date: 
Oct 18 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Handwriting comparison and identification, e.g. in the setting of forensics, has been widely addressed over the years. However, even in the case of modern documents, the proposed computerized solutions are quite unsatisfactory. For historical documents, such problems are worsened, due to the inscriptions’ preservation conditions. In the following lecture, we will present an attempt at addressing such a problem in the setting of First Temple Period inscriptions, stemming from the isolated military outpost of Arad (ca. 600 BCE). The solution we propose comprises: (A) Acquiring better imagery of the inscriptions using multispectral techniques; (B) Restoring characters via approximation of their composing strokes, represented as a spline-based structure, and estimated by an optimization procedure; (C) Feature extraction and distance calculation - creation of feature vectors describing various aspects of a specific character based upon its deviation from all other characters; (D) Conducting an experiment to test a null hypothesis that two given inscriptions were written by the same author. Applying this approach to the Arad corpus of inscriptions resulted in: (i) The discovery of a brand new inscription on the back side of a well known inscription (half a century after being unearthed); (ii) Empirical evidence regarding the literacy rates in the Kingdom of Judah on the eve of its destruction by Nebuchadnezzar the Babylonian king.

Barak Sober received his B.Sc. degree in Mathematics and Philosophy from Tel Aviv University, Israel, in 2006. He received his M.Sc. in Applied Mathematics (summa cum laude) on the topic of “Handwritten Character Stroke Reconstruction” in 2013. He is currently pursuing his PhD in Applied Mathematics on the topic of “Approximation of Manifolds from Scattered Data”. His interests include approximation theory, machine learning, image processing and archaeology.

IDeAS Seminar: Graph-based Bayesian learning: continuum limits and scalability of sampling algorithms.

Speaker: 
Nicolas Garcia Trillos, Brown University
Date: 
Oct 25 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

The principled learning of functions from data is at the core of statistics, machine learning and artificial intelligence. In this talk I will focus on Bayesian approaches to learning in the context of inverse problems on unknown domains and in particular to semi-supervised learning. More specifically, we consider the problem of recovering a function input of a partial differential equation formulated on an unknown domain M where we can define a ground-truth Bayesian inverse problem.  We assume to have access to a discrete domain Mn = {x1, . . . , xn} ⊂ M, and to noisy measurements of the output solution at p ≤ n of those points. The discrete domain is then endowed with a graph structure which is used to create a graph surrogate for the ground-truth Bayesian inverse problem. The first theoretical result that I will present establishes the convergence of the graph posterior distribution associated to the graph-Bayesian inverse problem towards its ground-truth counterpart as the number of unlabeled data points converges to infinity. Our analysis relies on the variational description of posterior distributions,  the choice of an appropriate topology to compare distributions on different domains, and precise quantitative estimates of the spectrum of graph Laplacians. I will then show that our consistency results have profound algorithmic implications: when they hold, carefully designed graph-based Markov chain Monte Carlo (MCMC) algorithms have a uniform spectral gap, independent of the number of unlabeled data.

This talk is based on works with Zachary Kaplan, Thabo Samakhoana, and Daniel Sanz-Alonso.

IDeAS Seminar: Provably good convex methods for mapping problems

Speaker: 
Nadav Dym, Weizmann Institute
Date: 
Nov 8 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Computing mappings or correspondences between surfaces is an important tool for many applications in computer graphics, computer vision, medical imaging, morphology and related fields. Mappings of least angle distortion (conformal) and distance distortion (isometric) are of particular interest. The problem of finding conformal/isometric mappings between surfaces is typically formulated as a difficult non-convex optimization problem. Convex methods relax the non-convex optimization problem to a convex problem which can then be solved globally. The main issue then is whether the global solution of the convex problem is a good approximation for the original global solution. In this talk we will discuss two families of convex relaxations.

Conformal: We relax the problem of computing planar conformal mappings (Riemann mappings) to a simple convex problem which can be solved by solving a system of linear equations. We show that in this case the relaxation is exact- the solution of the convex problem is guaranteed to be the Riemann mapping!

Discrete isometric: for perfectly isometric asymmetric surfaces, the well known doubly-stochastic (DS) relaxation is exact. We generalize this result to the more challenging and important case of symmetric surfaces, once exactness is correctly defined for such problems. For non-isometric surfaces it is difficult to achieve exactness. Several relaxations have been proposed for such problems, where the more accurate relaxations are generally also more time consuming. We will describe two algorithm which strike a good balance between accuracy and efficiency: The DS++ algorithm, which is provably better than several popular algorithms but does not compromise efficiency,  and the Sinkhorn-JA algorithm, which gives a first-order algorithm for efficiently solving the strong but high-dimensional JA relaxation. We utilize this algorithmic improvement to achieve state of the art results for shape matching and image arrangement.

Nadav Dym received his Bsc and Msc degrees in mathematics from the Hebrew University.  His Msc thesis was on the topic “spatial recurrence for ergodic fractal measures “. He is currently pursuing his PhD degree in the department of computer science and applied mathematics in the Weizmann Institute, on the topic “convex methods for shape matching and related problems“ . His research interests include convex optimization, analysis and geometry and their applications.

 

IDeAS Seminar: Computational Algebraic Geometry and Applications to Computer Vision

Speaker: 
Joe Kileel, Princeton University
Date: 
Nov 15 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Many models in science and engineering are described by polynomials.  Computational algebraic geometry gives tools to analyze and exploit algebraic structure.  In this talk, we offer a user-friendly introduction to some of these notions, including dimension (formalizing degrees of freedom), degree (formalizing the number of solutions to a polynomial system) and 0-1 laws in algebraic geometry (solution sets to polynomial systems exhibit similar behavior for all but a measure 0 subset of problem instances).  We will also mention algorithms, based on Gröbner bases (symbolic techniques) and homotopy continuation (numerical techniques).

Applied examples are drawn from the structure-from-motion problem in computer vision, where the task of building a 3D model from multiple 2D images leads to nontrivial polynomial systems.

References include:

J. Kileel, Minimal Problems for the Calibrated Trifocal Variety, SIAM Journal on Applied Algebra and Geometry 1 (2017) 575-598.

J. Kileel, Z. Kukelova, T. Pajdla and B. Sturmfels, Distortion Varieties, Foundations of Computational Mathematics, first online.

 

BIO:

Joe Kileel is a postdoctoral research associate at Princeton’s Program in Applied and Computational Mathematics, and a member of the Simons Collaboration on Algorithms and Geometry.  He received his PhD in May 2017 from UC Berkeley, advised by Bernd Sturmfels, where his thesis was awarded the Bernard Friedman Memorial Prize for best in applied mathematics.  Joe's current publication list is available at http://web.math.princeton.edu/~jkileel/.  

IDeAS Seminar: Data-driven analysis of neuronal activity

Speaker: 
Gal Mishne, Yale University
Date: 
Nov 29 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

Recent advances in experimental methods in neuroscience enable the acquisition of large-scale, high-dimensional and high-resolution datasets. These complex and rich datasets call for the development of advanced data analysis tools, as commonly used techniques do not suffice to capture the spatiotemporal network complexity. In this talk I will present new data-driven methods based on global and local spectral embeddings for the processing and organization of high-dimensional datasets, and demonstrate their application to the analysis of neuronal measurements.  

We develop a new greedy adaptive spectral clustering method capable of handling overlapping clusters and disregarding clutter. Applied to in-vivo calcium imaging of neurons and apical dendrites, we extract hundreds of neuronal structures with detailed morphology, and demixed and denoised time-traces. Next we introduce a nonlinear, data-driven and model-free approach for the analysis of a spatiotemporal dynamical system, represented as a rank-3 tensor. Applying our methodology to neuronal measurements, we identify, solely from observations and in a purely unsupervised data-driven manner, functional subsets of neurons, activity patterns associated with particular behaviors and pathological dysfunction caused by external intervention.

Gal Mishne is a Gibbs Assistant Professor in the Applied Math program at Yale University, working with Ronald Coifman's research group. She completed her Ph.D. at the Viterbi Faculty of Electrical Engineering at the Technion in 2017, and holds a B.Sc. (summa cum laude) in Electrical Engineering and Physics from the Technion. Her research interests are high-dimensional data analysis methods based on manifold learning and diffusion geometry for computational neuroscience, image processing and biomedical signal processing.

IDeAS Seminar: Reconstructing 3D protein crystal intensity from unoriented sparse diffraction patterns

Speaker: 
Ti-Yen Lan, Cornell University
Date: 
Dec 6 2017 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

The femtoseconds long pulses of an X-ray free electron laser (XFEL) enable the measurement to outrun the irreversible radiation damage. This concept of `diffract before destroy’ inspires new methods such as serial crystallography, which determines 3D protein structures by merging 2D snapshots of microcrystals collected at random orientations. In recent years, there has been a growing interest to apply this technique to the synchrotron storage ring sources because of their wider availability. For very small crystals, however, radiation damage occurs before sufficient numbers of photons are diffracted to determine the orientation of the crystal. The challenge is to merge data from a large number of such “sparse” frames in order to measure the full reciprocal space intensity.

In this talk I will discuss our effort to develop an analysis method to analyze the unoriented sparse crystal diffraction patterns. Using the EMC algorithm (Loh & Elser, 2009), we reconstruct the 3D crystal intensity by iteratively maximizing the likelihood function of the crystal orientations. I will demonstrate the ability of our method to analyze sparse patterns through a couple of proof-of-concept experiments with increasing complexity. Finally I will present our recent progress in applying the EMC algorithm to a serial crystallography dataset taken at a storage ring source. 

Ti-Yen Lan received his B.S. degree in Physics from National Taiwan University, Taiwan, in 2012. He is now a Ph.D. candidate in Theoretical Physics working with Professor Veit Elser at Cornell University. He is interested in developing methods to extract information from noisy image data through the modeling of the image formation process.

IDeAS Seminar

Speaker: 
Mahdi Soltanolkotabi, University of Southern California (USC)
Date: 
Mar 14 2018 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA

IDeAS Seminar

Speaker: 
Jeffrey Donatelli, UC Berkeley
Date: 
Apr 25 2018 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA

IDeAs Seminar

Speaker: 
Peter Doerschuk, Cornell University
Date: 
May 2 2018 - 2:30pm
Event type: 
IDeAS
Room: 
224 Fine Hall
Abstract: 

TBA