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 (総合７), Main Campus

 Adam Jatowt(Kyoto University), Acrosstime Term Similarity Computation and Explanation

 Adam Jatowt(Kyoto University), Estimating Document Comprehensibility and Comprehensibilityaware 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é ParisSaclay), 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 HighDimensional 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), Universal Rigidity and the Unique PSD Matrix Completions 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 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Acrosstime 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 longterm 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 acrosstime 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 cochair of IPRES2011, SocInfo2013, ICADL2014, JCDL2017 conferences, tutorial cochair of SIGIR2017, editorial board member of Information Processing and Management Journal and coorganizer of three NTCIR evaluation tasks.
October 12
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Estimating Document Comprehensibility and Comprehensibilityaware 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 cochair of IPRES2011, SocInfo2013, ICADL2014, JCDL2017 conferences, tutorial cochair of SIGIR2017, editorial board member of Information Processing and Management Journal and coorganizer of three NTCIR evaluation tasks.
October 19
14:45 16:15, Joho 2, Research Bldg. No.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, loglinear 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 (総合７), 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, theorydriven 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 “broadenandbuild” 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 highlyrated sites would trigger wideangle photographs. By analyzing travel photos, we find a strong correlation between a preference for wideangle 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 (総合７), 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 JeanPhilippe Vert in 11/2005 from the Ecole des Mines de Paris. He worked as a postdoctoral 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 (総合７), 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 wellknown applications concerning the design of spaceefficient 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 spaceefficient 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 (総合７), 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 (総合７), Main Campus
Makoto Yamada, RIKEN AIP
Title: Nonlinear Feature Selection for HighDimensional 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 highdimensional data (more than million features) in nonlinear way. In this talk, we first introduce a HilbertSchmidt Independence Criterion Lasso (HSIC Lasso) that can efficiently select nonredundant features from a small and highdimensional 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 highdimensional 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 subcluster and hsicInf can obtain pvalues of selected features from any type of data.
December 7
14:45 16:15, Joho 2, Research Bldg. No.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 SmartCity and IoT Wireless Sensor Networks allowing the representation of a large number of
mobile sensor nodes within dynamic and realworld environments, integrating scenarios arising from
delays, failures, attacks, disconnections. We give a presentation of CupCarbon and illustrate its application
to a realworld situation. We conclude with a problem which is purely graphtheoretical 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 LabSTICC 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 largescale reallife problem instances.
December 14
14:45 16:15, Joho 2, Research Bldg. No.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 wellknown 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 nondegenerate 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 (総合７), 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 twofolded: 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, semanticallystructured 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.
January 18
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
David Avis, Kyoto University and McGill University
Title: Nonlinear Feature Selection for HighDimensional 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 branchandbound. 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 (総合７), 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 graphtheoretic 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 graphtheoretic 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.