Schedule for Fall 2017 - Kyoto University Informatics Seminar

Schedule for Fall 2017

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

Unless noted otherwise, all talks Thursday 14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus

    • Adam Jatowt(Kyoto University), Across-time Term Similarity Computation and Explanation
    • Adam Jatowt(Kyoto University), Estimating Document Comprehensibility and Comprehensibility-aware Search
    • Mahito Sugiyama(National Institute of Informatics), Information Geometric Analysis on Partial Order Structures hosted by Akihiro Yamamoto
    • Xuefeng Liang(Kyoto University), Viewing Bigger Pictures Promotes Happier Mood: A psychological explanation and an example in the real world
    • Marco Cuturi(Université Paris-Saclay), Generative Modeling and Optimal Transport
    • Francois Le Gall(Kyoto University), Random Walks and Space Complexity
    • Taisuke Izumi(Nagoya Institute of Technology), A Short and Guided Tour on Communication Complexity hosted by F. Le Gall
    • Makoto Yamada(RIKEN AIP), Nonlinear Feature Selection for High-Dimensional Data hosted by Xuefeng Liang
    • Reinhart Euler(University of Brest), Design and Simulation of Wireless Sensor and IoT Networks hosted by D. Avis
    • Komei Fukuda(ETH), Pivoting for Life hosted by D. Avis
    • Michael Faerber(University of Freiburg; Kyoto University), NLP meets Semantic Web and Machine Learning: Finding Novel Information and Appropriate Citations hosted by Adam Jatowt
    • Shinichi Tanigawa(University of Tokyo), Analyzing the Stability of Tensegrities by SDP Duality hosted by D. Avis
    • Xuefeng Liang(Kyoto University), A General Inlier Estimation for Moving Camera Motion Segmentation
    • David Avis(Kyoto University), mts: A Framework for Parallel Tree Search
    • Francois Le Gall(Kyoto University), Quantum Algorithms for Graph Problems

Detailed Information and Abstracts

October 5

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Adam Jatowt, Kyoto University
Title: Across-time Term Similarity Computation and Explanation
Abstract: Recently, large amounts of historical texts have been digitized and made accessible to the public. However, accessing them is difficult due to the terminology gap problem resulting from semantic evolution of terms. Current users of long-term archives may then not know the correct terms for formulating their queries. In this talk, I will first describe the framework for estimating and explaining the across-time similarity of terms. For example, given an input term (e.g., iPod) and the target time (e.g. 1980s), the task is, first, to find its counterpart that existed in the target time (e.g., Walkman) and, then, to output evidences of their similarity (e.g., portable music devices, mp3/tape). Second, I will introduce approach for explaining term similarity over time.

Bio: Adam Jatowt received his Ph.D. in Information Science and Technology from University of Tokyo, Japan in 2005. He is currently Associate Professor at Social Informatics Department, Kyoto University. His research interests include information retrieval and knowledge extraction from document archives and information comprehensibility estimation. Adam has served as a PC co-chair of IPRES2011, SocInfo2013, ICADL2014, JCDL2017 conferences, tutorial co-chair of SIGIR2017, editorial board member of Information Processing and Management Journal and co-organizer of three NTCIR evaluation tasks.

October 12

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Adam Jatowt, Kyoto University
Title: Estimating Document Comprehensibility and Comprehensibility-aware Search
Abstract: Document comprehensibility is one of key factors determining document quality and, in result, reader’s satisfaction. Relevant documents are of little utility for users searching on Web, if they are incomprehensible or impose too much cognitive burden on readers. In this talk we survey our research on estimating comprehensibility of web pages and on ranking search results based on their understandability.

Bio: Adam Jatowt received his Ph.D. in Information Science and Technology from University of Tokyo, Japan in 2005. He is currently Associate Professor at Social Informatics Department, Kyoto University. His research interests include information retrieval and knowledge extraction from document archives and information comprehensibility estimation. Adam has served as a PC co-chair of IPRES2011, SocInfo2013, ICADL2014, JCDL2017 conferences, tutorial co-chair of SIGIR2017, editorial board member of Information Processing and Management Journal and co-organizer of three NTCIR evaluation tasks.

October 19

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Mahito Sugiyama, National Institute of Informatics
Title: Information Geometric Analysis on Partial Order Structures
Abstract: I will introduce information geometry for partial order structures, which are a fundamental structure in computer science and mathematics, for example, relations on set inclusion, sequence prefixes, subgraphs, and reachability in directed acyclic graphs. Our information geometric formulation includes various models in a wide range of fields such as (deep)Boltzmann machines in machine learning, log-linear models in statistics, pattern mining in data mining, and matrix/tensor balancing in matrix theory. The Möbius function plays the key role to connect continuous structure of statistical manifolds in information geometry and discrete structure of partial orders.

October 26

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Xuefeng Liang, Kyoto University
Title: Viewing Bigger Pictures Promotes Happier Mood: A psychological explanation and an example in the real world
Abstract: In psychology, theory-driven researches are usually conducted with extensive laboratory experiments, yet rarely tested or disproved with big data. In this paper, we make use of 418K travel photos with traveler ratings to test the influential “broaden-and-build” theory, that suggests positive emotions broaden one's visual attention. The core hypothesis examined in this study is that positive emotion is associated with a wider attention, hence highly-rated sites would trigger wide-angle photographs. By analyzing travel photos, we find a strong correlation between a preference for wide-angle photos and the high rating of tourist sites on TripAdvisor. We are able to carry out this analysis through the use of deep learning algorithms to classify the photos into wide and narrow angles, and present this study as an exemplar of how big data and deep learning can be used to test laboratory findings in the wild.

bio: XueFeng Liang received his Ph.D. degree in information science from Japan Advanced Institute of Science and Technology, Japan, in 2006. Afterwards, he held JST research fellowship at National Institute of Advanced Industrial Science and Technology in Japan. From 2008 to 2010. He worked as research assistant in both University College of London and Queen Mary University of London. He is currently an associate professor in Kyoto University. He is on the editorial board of two international journals, and has chaired and served as TCP members for several international conferences. His research interests include visual perception, computer vision, machine learning.

November 2

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Marco Cuturi, CREST ENSAE Université Paris Saclay
Title: Generative Modeling and Optimal Transport
Abstract: We present in this talk recent advances on the topic of parameter estimation using optimal transport, and discuss possible implementations for “Minimum Kantorovich Estimators”. We show why these estimators are currently of great interest in the deep learning community, in which researchers have tried to formulate generative models for images. We will present a few algorithmic solutions to this problem.

Bio: MC is professor of statistics at CREST/ENSAE Université Paris Saclay. He received his Ph.D. under the supervision of Jean-Philippe Vert in 11/2005 from the Ecole des Mines de Paris. He worked as a post-doctoral researcher at the Institute of Statistical Mathematics, Tokyo, between 2005 and 2007, in the financial industry until 2008, and in the ORFE department of Princeton University until 2010 as a lecturer. He was an associate professor at the Graduate School of Informatics of Kyoto University between 2010 and 2016.

November 9

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Francois Le Gall, Kyoto University
Title: Random Walks and Space Complexity
Abstract: The concept of random walk is an extremely versatile and powerful paradigm in the field of randomized algorithms. In the first part of this talk I will review the concept of random walks and describe several well-known applications concerning the design of space-efficient algorithms (e.g., how to test if an undirected graph is connected in logarithmic space). In the second part of this talk I will present new results about space-efficient algorithms for solving linear systems of equations based on random walks.

Bio: Francois Le Gall is an Associate Professor in the Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University. He received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation.

November 16

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Taisuke Izumi, Nagoya Institute of Technology
Title: A Short and Guided Tour on Communication Complexity
Abstract: Showing “impossibilities” is one of the most challenging and interesting topics in theoretical computer science, which often yields the invention of very elegant methodologies for proofs. In this talk, I will exhibit a small picture of such a beautiful field, especially in the context of some theory on networked computation - communication complexity. The main question of the communication complexity theory is as follows: Several players have fragments of the whole input data x, and must compute a given function f(x) cooperatively. Then how many bits do they have to exchange for answering f(x)? The simplest case is when the number of players is two. That is, two players have inputs x and y respectively, and they must compute some the value of f(x, y) for a given function f by exchanging messages. The talk shows how the communication complexity is an exciting theory even in this simple setting, with its application to (general) computer science.

November 30

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Makoto Yamada, RIKEN AIP
Title: Nonlinear Feature Selection for High-Dimensional Data
Abstract: Feature selection is an important machine learning problem, and it is widely used for various types of applications such as gene selection from microarray data, document categorization, and prosthesis control, to name a few. The feature selection problem is a fundamental and traditional machine learning problem, and thus there exist many methods including the least absolute shrinkage and selection operator (Lasso). However, there are a few methods that can select features from large and ultra high-dimensional data (more than million features) in nonlinear way. In this talk, we first introduce a Hilbert-Schmidt Independence Criterion Lasso (HSIC Lasso) that can efficiently select non-redundant features from a small and high-dimensional data in nonlinear way. A key advantage of HSIC Lasso is that it is a convex method and can find a globally optimal solution. Then we further extend the proposed method to handle ultra high-dimensional data by incorporating with distributed computing framework. Moreover, we introduce two newly proposed algorithms the localized lasso and hsicInf, where the localized lasso is useful for selecting a set of features from each sub-cluster and hsicInf can obtain p-values of selected features from any type of data.

December 7

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Reinhardt Euler, University of Brest
Title: Design and Simulation of Wireless Sensor and IoT Networks
Abstract:Recent developments of wireless communication and electronics have lead to the technology of Wireless Sensor and IoT Networks. Such a network consists of a large number of sensors, which are small electronic devices deployed over a physical environment to actively cooperate and accomplish one or more tasks. They can for instance collect data from their environment (light, temperature, motion, humidity, pressure etc.) and send them to a base station for further analysis. In more advanced versions, sensors are even capable to act as microcomputers. Due to the limited capacity of a sensor node in terms of energy, computing power, storage, the design of efficient such networks represents a true challenge and performance evaluation tools such as simulation becomes essential. CupCarbon is a platform for the design of Smart-City and IoT Wireless Sensor Networks allowing the representation of a large number of mobile sensor nodes within dynamic and real-world environments, integrating scenarios arising from delays, failures, attacks, disconnections. We give a presentation of CupCarbon and illustrate its application to a real-world situation. We conclude with a problem which is purely graph-theoretical in nature: finding the frontier or polygonal hull of a Euclidean graph.

Bio: Reinhardt Euler received the Ph.D. degree in mathematics from the University of Cologne. He is a professor of computer science at Lab-STICC laboratory (CNRS 6285), University of Brest. He has held visiting professorships at Grenoble University, the University of British Columbia in Vancouver, and Carnegie Mellon University in Pittsburgh. His research interests include combinatorial algorithms and optimization, graph theory, and the efficient solution of large-scale real-life problem instances.

December 14

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Komei Fukuda, ETH
Title: Pivoting for Life
Abstract: The pivot operation is an elementary operation used in many algorithms to solve fundamental problems in linear inequality systems. The simplex method for linear programming is arguably the most well-known such algorithm.

In this talk, I will present my personal research results on pivot algorithms which span my entire academic life from 1976 (the beginning of doctoral study) until my retirement in 2016. These results include a construction of a very clean example of the cycling of the simplex method, a construction of a non-degenerate cycling in the topological setting, finite pivot algorithms (with Jack Edmonds and with Tamas Terlaky) for linear and quadratic programming, the reverse search algorithm (with David Avis) for enumerating all extreme points of a convex polytope, a purely combinatorial pivot algorithm (with Bernd Gaertner and May Szedlak) for removing redundant constraints in linear programming. Wishfully, I try to convince the audience that studying a very elementary thing can be fulfilling and fun.

Bio: Komei Fukuda is professor emeritus and researcher at ETH Zurich. He received his PhD in 1982 from University of Waterloo in Combinatorics and Optimization. His research interests include optimization, polyhedral computation and oriented matroid theory.

December 21

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Michael Faerber, University of Freiburg; Kyoto University
Title: NLP meets Semantic Web and Machine Learning: Finding Novel Information and Appropriate Citations
Abstract: This talk is two-folded: Firstly, new approaches are presented for detecting and extracting simultaneously relevant and novel information from unstructured text documents. A major contribution of these approaches is that the information already provided and the extracted information are modeled semantically. This leads to the following benefits: ( a ) ambiguities in the language can be resolved; ( b ) the exact information needs regarding relevance and novelty can be specified; and ( c ) knowledge graphs can be incorporated. More specifically, this talk presents: (1) an assessment of the suitability of existing large knowledge graphs for the task of detecting novel information in text documents; 2. an approach by which emerging entities that are missing in a knowledge graph are detected in a stream of text documents; 3. an approach to extracting novel, relevant, semantically-structured statements from text documents. The developed approaches are suitable for the recommendation of emerging entities and novel statements respectively, for the purpose of knowledge graph population, and for providing assistance to users requiring novel information, such as journalists and technology scouts. In the second part of the talk, an overview of the task of citation recommendation is given. Citation recommendation refers to the task of recommending appropriate citations for a short text passage within a document. We show results of our comparison between existing approaches and evaluation data sets for citation recommendation and give an outlook to future research directions.

Bio: Michael Färber received a JSPS fellowship for his work on citation recommendation at the Department of Social Informatics at Kyoto University, Kyoto, Japan. Before that, we worked at the University of Freiburg, Germany, and obtained his PhD in February 2017 at the Institute AIFB at Karlsruhe Institute of Technology (KIT), Karlrsuhe, Germany. In this research, Michael Färber focuses mainly on NLP, Semantic Web, and Machine Learning. He served as reviewer and PC member for major NLP and Semantic Web conferences and journals.

December 28

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Shinichi Tanigawa, University of Tokyo
Title: Analyzing the Stability of Tensegrities by SDP Duality
Abstract: In this lecture I will talk about an application of SDP (semidefinite programming) duality to a structural engineering problem. A tensegrity is a structure made from disjoint stiff bars linked by cables, and designing a new stable (and beautiful) tensegrity is a challenging problem. Although this is an subject in structural engineering, the underlying mathematics appears in various different places. For example, if we look at those objects in spherical space, constructing a tensegrity corresponds to a low-rank psd matrix completion problem, a popular topic in machine learning. In 1982 Robert Connelly gave a necessary condition for the stability of tensegrities in his new proof of Cauchy’s theorem on the rigidity of polyhedra. I will explain this condition in terms of modern SDP language.

Bio: Shinichi Tanigawa got his Doctor of Engineering in March 2010 from the Graduate School of Engineering at Kyoto University. He was an Assistant Professor at RIMS, Kyoto University, from 2011-17 and has been an Associate Professor at the University of Tokyo since then.

January 18

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
David Avis, Kyoto University and McGill University
Title: Nonlinear Feature Selection for High-Dimensional Data
Abstract: I will describe mts, a generic framework for parallelizing certain types of tree search programs using a single common wrapper. The first part of the talk is a tutorial on how to parallelize enumeration codes based on reverse search using a very simple mts interface. mts also supports sharing information between processes which is important for applications such as satisfiability testing and branch-and-bound. No parallelization is implemented in the legacy single processor code minimizing the changes needed and simplifying debugging. mts is written in C, uses MPI for parallelization and can be used on a network of computers. I will give computational results for the parallelization of two simple existing reverse search codes, generating topological sorts and generating spanning trees of a graph, and two codes for satisfiability testing. (Joint work with Skip Jordan)

Bio: David Avis is Professor Emeritus in the School of Computer Science at McGill University and a researcher in the Department of Intelligence Science and Technology at Kyoto University. He received his PhD in 1977 from Stanford University in Operations Research. His research interests include discrete optimization, polyhedral computation and parallel computation.

January 25

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Francois Le Gall, Kyoto University
Title: Quantum Algorithms for Graph Problems
Abstract: In this talk I will present recent developments on quantum algorithms for graph-theoretic problems. I will first introduce the concept of quantum algorithms, and in particular the powerful technique known as “quantum walk search”, and describe several fundamental applications. I will then focus on one of the most basic graph-theoretic problems: decide if a given graph contains a triangle. After explaining why this problem is important, I will survey the state of the art of classical and quantum algorithms for triangle finding, and present some new results I obtained recently.

Bio: Francois Le Gall is an Associate Professor in the Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University. He received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation.