**Combinatorics in Learning Theory** : IMI Short-term Joint Research Project | Date | September 18-20, 2012 | Place | Center Zone 1 (#1304), Faculty of Mathematics building, Ito Campus Access，Ito Campus map (Center Zone ㊽) | Program | September 18 (Tuesday) 10:00-10:45 Title：**Groebner basis and Computational learning** Author：Hiroo Tokunaga (Tokyo Metropolitan U., Division of Mathematical Sciences) Abstract： By relating languages over an alphabet to ideals of a ring, we discuss sufficient conditions of learnabiblity of languages, from viewpoint of the ascending chain conditions for ideals, and then discuss Groebner basis. 11:00-11:45 Title：**Computational Learning and well-quasi ordering** Author：Yohji Akama (Tohoku U., Math. Inst.) Abstract： By introducing the order-type of a set system from viewpoint of computational learning, we obtain a generalization of Higman's well-quasi ordering. We study basic properties of the order-type of a set system and its continuous deformation. Then we sketch possible relation to Noetherian spaces. 13:00-13:45 Title：**Survey on computational learning** Author：Ryo Yoshinaka (Kyoto U., Graduate School of Informatics) Abstract： We survey Gold's model of learning languages in the limit, and Dana Angluin's characterization of the learnability of languages in Gold's model. 14:00-14:45 Title：**VC dimensions of statistical inferences and combinatorics** Author：Yohji Akama (Tohoku U., Math. Inst.) Abstract： In Gaussian/linear regression analysis, a geometric classe arises as the target of learning. The Vapnik-Chervonenkis dimension (VC dimension) of the class represents the difficulty to learn/estimate such class. It is essentially the number of points to specify uniquely a member of the geometric class, so to say. To compute the VC dimension of such geometric class, convex geometric approaches and so-called Milnor-Thom bound for connected components of algebraic varieties are important. We discuss recent results on this matter. 15:00-15:45 Title：**Recent topics on grammatical inference** Author：Ryo Yoshinaka (Kyoto U., Graduate School of Informatics) Abstract： We discuss the learnability context-free grammars based on Alexander Clark's syntactic concept lattice. 16:00-17:00 Title：**Godel Logics, Continuous Embeddability and Fraisse's Conjecture** Author：N. Preining (Japan Advanced Institute and Technology) Abstract： In this talk we present a family of many-valued logics introduced by Kurt Goedel to approximate Intuitionistic Logic. Later on these were extended to first order and have exhibited connections to temporal logics, Kripke frames based logics, fuzzy logics in the sense of Hajek (t-norm based logics). These logics are based on selecting a closed subset of the real interval [0,1], and collecting all formulas evaluating to true for all valuations into this truth value set. Due to the specific truth functions different truth values sets might generate the same logics (as sets of formulas). During the search for the total number of logics we took up old conjecture of Fraisse (theorem of Laver) on the behaviour of scattered linear orderings. We consider continuous embeddability in the reals and prove a generalized Fraisse conjecture stating the the closed subsets of the real [0,1] interval with continuous embeddability are better-quasi-ordered. Using this result we can show that surprisingly the total number of different Goedel logics is countable. This discrepancy - on the one hand uncountable many equivalence classes of the above mentioned ordering, and countable many Goedel logics on the other hand - leaves us still without an "intensional definition" of Goedel logics in the sense that if two semantical objects (to be found or defined) are different, then the respective logics are different, too. This does not hold for equality of the truth value sets, since there are different truth value sets creating the same logic, as well as for the above mentioned continuous embeddability induced equivalence. September 19 (Wednesday) 9:30-10:00 Title：**Towards classification of spherical tilings by congruent quadrangles** Author：Yohji Akama (Tohoku U., Math. Inst.) Abstract： Spherical tilings are tilings of the sphere, and are found in Japanese traditional artwork TEMARI. They can be related to molecular spheres studied by synthetic chemists recently. Since low symmetric spherical tilings by congruent quadrangles are discovered recently, we are concerned on the classification of spherical tilings by congruent quadrangles, and discuss graph-theoretic background to enumerate them all. 10:15-11:45 Title：**Enumeration and indexing of development maps of polyhedra** Author：Takashi Horiyama (Satama U., Graduate School of Science and Engineering) Abstract： To solve many open, important problems of the development maps of polytopes, we are concerned with the enumeration (data mining) of the development maps of polytopes. We discuss efficient indexing techniques of the development maps. 14:00-14:45 Title：**Enumeration of combinatorial types of polytopes** Author：Hiroyuki Miyata (Tohoku U, Graduate School of Information Sciences) Abstract： The face lattice of a polytope is a discrete data having various information of the polytope. When the dimension is low or the number of vertices is small, there are nice characterizations and efficient enumeration techniques of face lattices of polytopes. However, in general case, recognition of face lattices itself is known to be hard and thus enumeration is difficult. In this talk, we survey known results on the enumeration of face lattices of polytopes and relevant work, and then presents our work on the enumeration of 5-dimensional polytopes with 9 vertices (joint work with Fukuda (ETH Zurich) and Moriyama (Tohoku U.). 15:00-15:45 Title：**Enumeration of combinatorial structures of polyhedra** Author：Hiroyuki Miyata (Tohoku U, Graduate School of Information Sciences) Abstract： Fano varieties are important algebraic varieties, especially in bi-rational geometry. There is a bijective correspondence between the class of toric Fano varieties and the class of Fano polyhedra. We will survey basic properties of Fano polyhedra and the classification results. 16:00-17:00 Title：**VC dimension and fewnomials** Author：Akito Sakurai (Keio U., Graduate School of Science and Technology) Abstract： To estimate the generalization error of neural networks, the VC dimensions of the neural network were studied. The lower bounds of the VC dimensions were computed constructively, while the upper bounds were computed by counting argument. For the counting argument, we discuss Khovanskii's work on fewnomials. September 20 (Thursday) 9:00-9:45 Title：**Fano polytopes and their classification (II)** Author：Hiroshi Sato (Gifu Shotoku Gakuen U., Faculty of Economics and Information) Abstract： We study so-called SFP algorithm introduced by Obro. The SFP algorithm is an amazing algorithm that outputs all the Fano polytope of a given dimension. This algorithm completes the classification of Toric-Fano variety, in a sense. 10:00-10:45 Title：**Problems related to support vector machines in KDDI labs** Author：Kazunori Matsumoto (KDDI Lab.) Abstract： From the point of an engineering side, especially the state of the art in a commercial company, we introduce current serious problems of data mining from big data, such as learning time of support vector machines and so on. 11:00-11:45 Title：**Enumeration of discrete structures by data mining** Author：Hiroki Arimura (Hokkaido U., Graduate School of Information Science and Technology) Abstract： Data mining is a research topic to study efficient techniques to find interesting rules and patterns from big data. Data mining from data bases (sets) have been studied so far. However, in this decade, data mining from discrete structures such as graphs are well studied. The latter data mining are regarded as an enumeration algorithm of all the substructures of a given discrete structures. In this talk, we survey basic data mining techniques and data mining algorithms for discrete structures such as trees recently. 14:00-14:45 Title：**Speed-up of Matrix operations by ZDD** Author：Masaaki Nishino (NTT Communication Science Laboratories) Abstract： Multiplication between a binary matrix and a real value vector can be seen in various situations. In the previous work, we showed the number of computation needed for multiplications can be reduced by using ZDD (Zero-suppressed Binary Decision Diagrams). The proposed calculation method, however, needs to translate a binary matrix to corresponding ZDD before operation, and the translation needs non-negligible computation time. In this talk, we will show a translation method that can directly translate a binary matrix into a reduced ZDD. Our method can work with less memory. 15:00-15:30 **discussion** Chair:Akihiro Yamamoto (Kyoto U., Graduate School of Informatics) | | | | |