Dec 17 (mon) JR Hakata City 9F, Meeting Room 3
10:00 - 10:20
Eiji Takimoto (Kyushu University)
Opening address and some remarks on the mission of Group C03.
10:30 - 12:00 [Tutorial Talk]
Kei Uchizawa (Yamagata University)
Learning Algorithm and Circuit Lower Bounds
14:00 - 15:30
Kohei Hatano (Kyushu University)
Combinatorial Online Prediction using Offline Approximation Algorithms
Marco Cuturi (Kyoto University)
Transportation Distances and their Application in Machine Learning:
15:45 - 17:15
Ayumi Shinohara (Tohoku University)
Revisiting minimum consistency problem for DFA, and on the maximum number
of runs in a string.
Ryo Yoshinaka (Kyoto University)
Distributional Learning of Context-Free Grammars
Kei Uchizawa (Yamagata University)
Output Patterns of Logic Circuits
19:00 - drinking session
Dec 18 (tue) JR Hakata City 9F, Meeting Room 2
10:00 - 11:30
Takayoshi Shoudai (Kyushu University)
Learning Unordered Tree Contraction Patterns in Polynomial Time
Koji Tsuda (Aist)
Loss Minimization of Power Distribution Networks with Binary Decision
11:30 - 12:00 (free discussion)
Speaker: Kei Uchizawa (Yamagata University)
Title: Learning Algorithm and Circuit Lower Bounds
In this talk, we mainly survey the following two papers concerning a
relationship between learning algorithms and circuit lower bounds:
(1) Efficient Learning Algorithms Yield Circuit Lower Bounds,
Journal of Computer and System Sciences, 75, 27-36, 2009.
(2) Learning DNFs and Circuits using Teaching Assistants,
In Proceedings of COCOON 2004, 188-197, 2004.
We then discuss future work and open problems along a line of research
given by the paper (2).
Speaker: Kei Uchizawa (Yamagata University)
Title: Output Patterns of Logic Circuits
Consider any combinatorial circuit C of logic gates. We define
an output pattern of C for a circuit input x as a vector of the outputs
of the gates in C for x, and say that C has a number p of output patterns
if different p output patterns arise in C for the circuit inputs.
In this talk, we observe that the number of output patterns are strongly
related to another major complexity measure, size
(i.e., the number of gates), and then present some lower bounds on
the number of output patterns. We also give some dichotomy result on
a problem of counting output patterns of a simple logic circuit.
Speaker: Ryo Yoshinaka (Kyoto University)
Title: Distributional Learning of Context-Free Grammars
In Grammatical Inference, intensive research on the learning of
regular languages has achieved a plenty of positive results so far.
It had been thought to be quite a hard task to learn a considerably
rich class of languages that handle context-free structures.
In these years, a new line of research on the learning of context-free
languages, called "distributional learning", has been proposed and has
produced several fruitful results.
Distributional learning algorithms model and exploit the distribution of
substrings in grammatical sentences.
This talk summarizes different approaches of distributional learning
and presents some open problems on the efficiency of the learning
Speaker: Takayoshi Shoudai (Kyushu University)
Title: Learning Unordered Tree Contraction Patterns
in Polynomial Time
We present a concept of edge contraction-based tree-structured
patterns as a graph pattern suited to represent tree-structured data.
A tree contraction pattern (TC-pattern) is an unordered tree-structured
pattern common to a given tree-structured data, which is obtained by
merging every uncommon connected substructure into one vertex by
edge contraction. In this talk, in order to establish an algorithmic
foundation for the discovery of knowledge from tree-structured data,
we show that TC patterns are learnable in polynomial time.
Speaker: Ayumi Shinohara (Tohoku University)
Title: Revisiting minimum consistency problem for DFA,
and on the maximum number of runs in a string.
We discuss two topics. The first one is motivated by a simple puzzle game
which we own created, and we are interested in the computational
to solve it. It is NP-hard in general, since it contains the minimum
problem for deterministic finite automata (MinCons(DFA)) as a special
MinCons(DFA) is well-known to be NP-hard and hard to approximate.
We are trying to analyze the complexity for a special case, which
is also related to the problem of inferring graphs from walks.
The second topic is concerning with the combinatorial properties of
maximal repetitions (runs) in strings. We show a new lower bound of
maximal sum of exponents of runs in a string.
Speaker: Kohei Hatano (Kyushu University)
Title: Combinatorial Online Prediction using Offline Approximation
We consider online prediction problems of combinatorial concepts.
Examples of such concepts include shortest pathes, permutations,
assignments, covers, and so on.
The goal of the online prediction algorithm is to compete with the best
fixed combinatorial concept in hindsight.
A generic approach to this problem is to design an "offline-online
an online prediction algorithm using the corresponding offline
(approximation) algorithm as an oracle.
The current state-of-the art converter, however, is not efficient enough.
In this talk, we will discuss approaches to construct more efficient
Speaker: Marco Cuturi (Kyoto University)
Title: Transportation Distances and their Application in Machine
Learning: New Problems
I will present in this talk two new research topics related to the
optimal transportation distance (also known as Earth Mover's or
Wasserstein) and its application in machine learning to compare
histograms of features.
I discuss first the ground metric learning problem, which is the
problem of tuning automatically the parameters of transportation
distances using labeled histogram data.
After providing some reminders on optimal transportation,
I will argue that learning transportation distances is akin
to learning an L1 distance on the simplex, namely a distance with
polyhedral level sets, and I will draw some parallels with Mahalanobis
distances, the L2 distance and elliptic level sets. I will then introduce
our algorithm (arXiv:1110.2306) and more recent extensions.
In the second part of my talk, I address the fact that transportation
distances are not Hilbertian by showing that they can be cast as
positive definite kernels through the "generating function trick".
We prove that the trick, which uses the generating function of the
transportation polytope to define a similarity - rather than focusing
exclusively on the optimal transport to define a distance - leads to
a positive definite kernel between histograms
Speaker: Koji Tsuda (Aist)
Title: Loss Minimization of Power Distribution Networks with
Binary Decision Diagrams
Determining loss minimum configuration in a distribution network is a
hard discrete optimization problem involving many variables.
Since more and more dispersed generators are installed on the demand side
of power systems and they are reconfigured frequently, developing
automatic approaches is indispensable for effectively managing a
large-scale distribution network. Existing fast methods employ local
updates that gradually improve the loss to solve such an optimization
problem. However, they finally get stuck at local minima, resulting in
arbitrarily poor results. In contrast, this paper presents a novel
optimization method that provides an error bound on the solution quality.
Thus, the obtained solution quality can be evaluated in comparison to
the global optimal solution. Instead of using local updates,
we construct a highly compressed search space using a binary decision
diagram and reduce the optimization problem to a shortest path-finding
Our method was shown to be not only accurate but also remarkably efficient;
Optimization of a large-scale model network with 468 switches was solved
in three hours with 1.56% relative error bound.