Tony Jebara - US grants

Statistical machine learning tools permit scientists and engineers to automatically estimate computational models directly from real-world data for making predictions, classifications and inferences. However, before learning can take place, the practitioner needs to know how to properly represent data in a consistent, invariant and well-behaved
numerical form for processing by the various techniques. This proposal reduces this burden and facilitates applications of machine learning via novel algorithms that not only model data but also automatically handle invariances and discover appropriate
representations of the data.

This proposal formalizes a variety of potential transformations and embeds them within a principled learning framework. This makes it possible to handle real scenarios where data transforms, translates, changes nonlinearly and effectively creates many difficulties for
traditional tools. The set of interesting transformations the proposal considers also includes permutations. Handling permutation allows algorithms to learn when each data-point in the dataset is a collection of tuples whose ordering is arbitrary. For example, a
digital color image can be represented as a bag of pixels whose ordering is arbitrary. This project then develops the necessary algorithms for invariance to permutations, re-orderings, translations, and many other transformations affecting data in practice.

The proposal makes use of and extends state-of-the-art techniques in the machine learning field including Bayesian networks, kernel methods and convex programming. Primary applications include face recognition and surveillance. To recognize human face identity from video, the proposed algorithms compensate for possible transformations as faces translate, deform and rotate in real images. Standardized and challenging face recognition datasets are used for evaluation. The representation learning methods also facilitate machine learning in general, promising potential impact in other applied fields where data undergoes transformations including computational vision, speech, time
series analysis and bio-informatics.

This proposal investigates new computational and combinatorial tools for learning from data and performing inference about data. As such, it serves as a bridge between the machine learning community and the combinatorics community. The latter field develops efficient algorithms or shows when an efficient solution to a particular problem exists. The project will support graduate students in the intersection of these two fields to combine recent theoretical results with practical data problems. The team will produce a website of tutorials, data sets, downloadable code, interactive visual examples and course materials to allow better integration across the two fields. The combinatorics community has identified a family of inputs called perfect graphs where otherwise hard problems are efficiently solvable. This proposal will investigate how to bridge this powerful theoretical result to the area of machine learning and formally characterize which learning and inference problems are efficiently solvable.

More specifically, the team will investigate data learning problems (such as clustering a data set into subgroups that are self-similar or finding anomalies in a database) and statistical inference problems (computing the most likely or most typical outcome from observed measurements). These problems will be compiled or represented as graphs and networks. Then, these graphs and networks can be more formally diagnosed using perfect graph theory to determine if the instance of the problem is easy (or hard) and to provide efficient solutions via exact algorithms on perfect graphs. These solvers will be implemented using message passing or convex programming.

This proposal explores the optimization of complicated nonlinear equations that underlie machine learning problems by reducing them to simpler easy-to-solve update rules. The learning problems include classification, regression, unsupervised learning and more. Through a method known as majorization, complicated optimization problems are handled by iteratively solving simpler problems like least-squares and traditional linear algebra operations. The proposal focuses on how to parallelize this method so that it can efficiently leverage many CPUs/GPUs simultaneously and in a distributed manner. Furthermore, by making the method stochastic, faster convergence on large or streaming data-sets becomes possible. Other variations are explored such as sparse learning where the recovered solution is forced to be compact which also leads to further efficiency.

Increasingly, the vast majority of machine learning problems in the literature are optimized by using generic first- and second-order methods. The approach in this proposal is designed specifically for machine learning optimization problems and uses majorization and bounding to guarantee monotonic convergence. In preliminary work, majorization has produced faster convergence in practice as well as novel theoretical guarantees. To make the method truly viable in practice, this proposal puts forward distributed, parallel, stochastic and sparse extensions. Since such extensions may violate monotonic convergence guarantees, the proposal explores additional algorithmic and theoretical efforts to preserve guarantees while also obtaining fast algorithms. In particular, parallelization and distributed computation is performed by wrapping current state-of-the-art least squares solvers with bound majorization steps. Stochastic computation is explored using singleton, small-batch and variable-sized batch methods. Sparsity is achieved by iterating current large-scale sparse solvers like FISTA and QUIC within the bound majorization technique. In terms of broader impact, one graduate student will be supported and will help produce downloadable tools for machine learning experts as well as practitioners. Modules will be developed to add to the PI's existing courses in machine learning. The PI will organize a one-day workshop on majorization methods. The proposal also provides a public project website with access to research publications, software/data downloads and schedules of upcoming events.