ELC Mini-Workshop(C03)

Abstracts

[Tutorial] Title: Learning Algorithm and Circuit Lower Bounds

Speaker: Kei Uchizawa (Yamagata University)

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)

Title: Output Patterns of Logic Circuits

Speaker: Kei Uchizawa (Yamagata University)

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)

Title: Distributional Learning of Context-Free Grammars

Speaker: Ryo Yoshinaka (Kyoto University)

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)

Title: Learning Unordered Tree Contraction Patterns in Polynomial Time

Speaker: Takayoshi Shoudai (Kyushu University)

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)

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

Speaker: Ayumi Shinohara (Tohoku University)

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)

Title: Combinatorial Online Prediction using Offline Approximation Algorithms

Speaker: Kohei Hatano (Kyushu University)

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)

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

Speaker: Marco Cuturi (Kyoto University)

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)

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

Speaker: Koji Tsuda (Aist)

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)