Schedule for Spring 2016 - Kyoto University Informatics Seminar

Schedule for Spring 2016

Official course name: Perspectives in Informatics 4, Graduate School of Informatics

Unless noted otherwise, all talks Monday 16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus

    • Colin de la Higuera(Université de Nantes), Grammatical inference: learning grammars and automata, hosted by A. Yamamoto
    • Arnaud Dessein(Université de Bordeaux), Regularized Optimal Transport and the Rot Mover's Distance, hosted by M.Cuturi
    • Rudy Raymond(IBM Japan), Introduction to Mathematical Optimization Methods and Applications at IBM Research, hosted by D. Avis and M. Cuturi
    • Chee Seng Chan(University of Malaya), A Deep Convolutional Network for Fine-art Paintings Classification, hosted by X. Liang
    • Luc Devroye(McGill), On the shape of random trees, hosted by D. Avis and M. Cuturi
    • Adam Jatowt(Kyoto University), Bridging Past with Present: Information Retrieval and Processing in Document Archives
    • Marco Cuturi(Kyoto University), Regularized Optimal Transport and Applications,
    • François Le Gall(Kyoto University), The complexity of matrix multiplication, hosted by Adam Jatowt
    • Bill Cook(Waterloo), In Pursuit of the Traveling Salesman, hosted by D. Avis and A. Yamomoto
    • Peter Eades(Sydney), Big Social Networks, Linear Algebra, and a Little Electricity, hosted by D. Avis and A. Yamamoto
    • Sebastian Pokutta(Georgia Institute of Technology), Extension Complexity: an overview, hosted by D. Avis and A. Yamamoto
    • Mathieu Blondel(NTT Communication Science Laboratories), Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms, hosted by M. Cuturi

Detailed Information and Abstracts

April 11

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Colin de la Higuera, Université de Nantes
Title: Grammatical inference: learning grammars and automata
Abstract: Grammatical inference corresponds to learning a finite state machine or a grammar given structured data (strings, trees, now even graphs). Applications are numerous, from computational linguistics to bioinformatics, model checking or pattern recognition. The algorithms and techniques are quite different from those in statistical machine learning, often less robust and better suited for cases where the situation is that of identification: we know that there is a pattern of the intended family to be found.

PDF

April 18

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Arnaud Dessein, Université de Bordeaux
Title: Regularized Optimal Transport and the Rot Mover's Distance
Abstract: I will present an ongoing work on smooth convex regularization of discrete optimal transport problems. In this context, the regularized optimal transport turns out to be equivalent to a matrix nearness problem with respect to Bregman divergences. Our framework thus naturally generalizes a previously proposed regularization based on the Boltzmann-Shannon entropy related to the Kullback-Leibler divergence, and solved with the Sinkhorn-Knopp algorithm. We call the regularized optimal transport distance the rot mover's distance in reference to the classical earth mover's distance. We develop two generic schemes that we call the alternate scaling and non-negative alternate scaling algorithms, to compute efficiently the regularized optimal plans depending on whether the domain of the regularizer lies within the non-negative orthant or not. These schemes are based on Dykstra's algorithm with alternate Bregman projections, and further exploit the Newton-Raphson method for separable divergences. We enhance the separable case with a sparse extension to deal with high data dimensions. We also instantiate our proposed framework and discuss the inherent specificities for well-known regularizers and statistical divergences in the machine learning and information geometry communities.

April 25

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Rudy Raymond, IBM Japan
Title: Introduction to Mathematical Optimization Methods and Applications at IBM Research
Abstract: Techniques of mathematical optimization are becoming more crucial than ever as we are witnessing the rise of data complexity and volume in the era of Internet of Things (IoT), Big Data, and Artificial Intelligence (AI). Collaborating with academia and government agencies, IBM Research – Tokyo has been working on developing new optimization methods to cope with important problems in these areas. I will introduce our activities centered at the use of mathematical programming based on the papers [1, 4, 5, 6, 7, 8] as listed below, as well the recent ones on Dynamic Boltzmann Machine (DyBM) [3] and Deep Choice Models[2]. Students are encouraged to work on some practical problems shown in the lecture. A part of this talk is based on the work supported by JST, CREST.

[1] “Truncating Shortest Path Search for Efficient Map-Matching”, Takashi Imamichi, Takayuki Osogami, and Rudy Raymond, IJCAI 2016 (accepted) [2] “A Deep Choice Model”, Makoto Otsuka and Takayuki Osogami, AAAI 2016 [3] “Seven neurons memorizing alphabetical images via spike-timing dependent plasticity”, Takayuki Osogami and Makoto Otsuka, Scientific Reports, 5, 14149, 2015 doi: 10.1038/srep14149

Other references: — [4] “An Offline Map Matching via Integer Programming”, Hiroki Yanagisawa, ICPR 2010 [5] “Map Matching with Hidden Markov Model on Sampled Road Network”, Rudy Raymond, Tetsuro Morimura, Takayuki Osogami, Noriaki Hirosue, ICPR 2012 [6] “Map Matching with Inverse Reinforcement Learning”, Takayuki Osogami and Rudy Raymond, IJCAI 2013 [7] “Dependable Virtual Machine Allocation”, Hiroki Yanagisawa, Takayuki Osogami and Rudy Raymond, IEEE INFOCOM, 2013 [8] “Analysis of transient queues with semidefinite optimization”, Takayuki Osogami and Rudy Raymond, Queueing Syst. 73(2): 195-234 (2013)

May 9

16:30 - 18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Chee Seng Chan, University of Malaya
Title: A Deep Convolutional Network for Fine-art Paintings Classification
Abstract: This work will​ ​ present a study on large-scale classification of fine-art paintings using the Deep Convolutional Network. The​ ​ objectives are two-folds. On one hand,​ ​ this work​ ​ would like to train an end-to-end deep convolution model to investigate​ ​the capability of deep model in fine-art painting classification problem. On the other hand,​ ​the work​ ​argues​ ​that classification of fine-art collections is a more challenging problem in comparison to objects or face recognition. This is because of some of​ ​the artworks are non-representational nor figurative, and might requires imagination to recognize them. Hence, a question​ ​arose is that does a machine have or able to capture “imagination” in paintings? One way to find out is train a deep model​ ​and then visualize the low-level to high-level features learnt. In the experiment,​ ​a​ ​recently publicly available large-scale “Wikiart paintings” dataset that consists of more than 80,000 paintings​ ​is employed​ ​and​ ​the proposed​ ​solution achieved state-of- the-art results (68%) in overall performance.

May 16

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Luc Devroye, McGill
Title: On the shape of random trees
Abstract: In this talk, I will give a brief survey of the properties of a large class of random trees, commonly known as “simply generated trees” and “conditional Galton-Watson trees”. They include the well-known Cayley trees and Catalan trees. I hope to be able to explain what these trees look like both at the macroscopic and microscopic level. I will conclude with some recent results related to a geometric web graph model called the Apollonian network.

May 23

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Adam Jatowt, Kyoto University
Title: Bridging Past with Present: Information Retrieval and Processing in Document Archives
Abstract: Recently, large amounts of historical documents (e.g., past news articles) have been digitized and made accessible to the public. However, we still lack effective methods for accessing and making use of such temporal data. This talk will overview our efforts towards facilitating access and understanding of historical texts. We will first describe the framework for estimating and explaining across-time similarity of terms. For example, given an input term (e.g., iPod) and the target time (e.g. 1980s), the task is to find its counterpart that existed in the target time (e.g., Walkman). The related problem is then to output evidences for helping to understand the term similarity. Our approach relies on transforming word contexts across time based on their neural network representations. In the second part of the talk I will demonstrate online systems for exploring semantic changes of words over time and for analyzing historical texts from the viewpoint of their semantic change based on Google ngram data.

May 30

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Marco Cuturi, Kyoto University
Title: Regularized Optimal Transport and Applications
Abstract: Optimal transport (OT) theory provides geometric tools to compare probability measures. After reviewing the basics of OT distances (a.k.a Wasserstein or Earth Mover's), I will show how an adequate regularization of the OT problem can result in substantially faster (GPU parallel) and much better behaved (strongly convex) numerical computations. I will then show how this regularization can enable several applications of OT to learn from probability measures. I will focus on in particular on the computation of Wasserstein barycenters and inverse problem (regression) in the simplex with the OT geometry (the latter being joint work with G. Peyré and N. Bonneel).

June 6

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
François Le Gall, Kyoto University
Title: The complexity of matrix multiplication
Abstract: Until a few years ago, the fastest algorithm for matrix multiplication was the “Coppersmith-Winograd algorithm” designed in 1987. Recently, a surge of activity by Andrew Stothers, Virginia Vassilevska-Williams and myself has finally led to improved algorithms. In this talk I will describe the long history of work on the complexity of matrix multiplication, and discuss these very recent improvements.

June 13

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Bill Cook, University of Waterloo
Title: In pursuit of the traveling salesman
Abstract: We discuss recent work and open research questions surrounding the traveling salesman problem. The focus will be on topics having potential impact on the computational solution of large-scale NP-hard problems.

June 27

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Peter Eades, University of Sydney
Title: Big Social Networks, Linear Algebra, and a Little Electricity
Abstract: The analysis of large social networks, such as Facebook and LinkedIn, is a key component of today’s business and social strategies. In this talk we show how well-known methods of linear algebra can be used to visualize these networks and show their structure. Further, we describe recent methods that use elementary electrical circuit theory to scale up the methods to handle very large networks.

July 4

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Sebastian Pokutta, Georgia Institute of Technology
Title: Extension Complexity: an overview
Abstract: Linear and semidefinite programming are two core optimization paradigms with many important applications in engineering and business. However, the expressive power of these modeling paradigms is only partially understood so far and extended formulations are a powerful and natural tool to analyze the possibilities and limitations of linear and semidefinite programming formulations. In this talk, I will provide an introduction to extended formulations and an overview of recent breakthrough results, both in the linear and the semidefinite setting, and provide some insights for the underlying hardness results.

July 11

16:30 -18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Mathieu Blondel, NTT Communication Science Laboratories
Title: Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms
Abstract: Polynomial networks and factorization machines are two recently-proposed models that can efficiently use feature interactions in classification and regression tasks. In this paper, we revisit both models from a unified perspective. Based on this new view, we study the properties of both models and propose new efficient training algorithms. Key to our approach is to cast parameter learning as a low-rank symmetric tensor estimation problem, which we solve by multi-convex optimization. We demonstrate our approach on regression and recommender system tasks.