Year: 2012
12/17 - 18 [elc]   ELC Mini-Workshop (C03)
Place : JR博多シティ9F第2,3会議室
会場:
JR博多シティ9F第3会議室(12/17),第2会議室(12/18)

アクセス:
http://www.jrhakatacity-eventspace.jp/access/index.html

また,17日19時より博多駅付近で懇親会を企画しています
(参加費4000-5000円程度).
参加希望の方は12月13日(木)までに畑埜

http://www.i.kyushu-u.ac.jp/~hatano/

までご連絡下さい.
※なお発表者の方は特に連絡のないかぎり参加を想定していますので,ご連絡は不要です.ご都合の悪い方はお知らせください.



スケジュール:

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:
New Problems


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


17:30 -
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
Diagrams


11:30 - 12:00 (free discussion)


[Tutorial]
Speaker: Kei Uchizawa (Yamagata University)

Title: Learning Algorithm and Circuit Lower Bounds

Abstract:
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).
(1h30min)


Speaker: Kei Uchizawa (Yamagata University)

Title: Output Patterns of Logic Circuits

Abstract:
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.
(45min)


Speaker: Ryo Yoshinaka (Kyoto University)

Title: Distributional Learning of Context-Free Grammars

Abstract:
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
algorithms.
(45min)


Speaker: Takayoshi Shoudai (Kyushu University)

Title: Learning Unordered Tree Contraction Patterns
       in Polynomial Time

Abstract:
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.
(45min)


Speaker: Ayumi Shinohara (Tohoku University)

Title: Revisiting minimum consistency problem for DFA,
       and on the maximum number of runs in a string.

Abstract:
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
complexity
to solve it. It is NP-hard in general, since it contains the minimum
consistency
problem for deterministic finite automata (MinCons(DFA)) as a special
case.
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.
(45min)


Speaker: Kohei Hatano (Kyushu University)

Title: Combinatorial Online Prediction using Offline Approximation
       Algorithms

Abstract:
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
converter", i.e.,
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
offline-online converters.
(45min)


Speaker: Marco Cuturi (Kyoto University)

Title: Transportation Distances and their Application in Machine
       Learning: New Problems

Abstract:
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
(arXiv:1209.2655).
(45min)


Speaker: Koji Tsuda (Aist)

Title: Loss Minimization of Power Distribution Networks with
       Binary Decision Diagrams

Abstract:
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
problem.
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.
(45min)








horiyama@al.ics.saitama-u.ac.jp