マス・フォア・インダストリ研究所

研究集会・ワークショップ・国際会議



研究集会・ワークショップ・国際会議(一覧)

学習理論における組合せ論


開催時期 2012-09-18 10:00~2012-09-21 17:00

場所 九州大学 伊都キャンパス センター1号館 1304号室

学習理論における組合せ論
Combinatorics in Learning Theory

※ この研究集会はマス・フォア・インダストリ研究所 短期共同研究の公開プログラムです。
 
 開催期間
 
 2012年9月18日(火)~9月20日(木)
 
 開催場所
 
 九州大学 伊都キャンパス センター1号館 1304号室
 伊都キャンパスへのアクセス伊都キャンパスマップ(センターゾーン ㊽ )
 
 講演
 
 9月18日(火)

 10:00-10:45
 題目:Groebner 基底と計算論的学習
          Groebner basis and Computational learning
 発表者:徳永 浩雄(首都大数理情報)
 概要:
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
 題目:Computational Learning and well-quasi ordering
 発表者:赤間 陽二(東北大学数学)
 概要:
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
 題目:Survey on computational learning
 発表者:吉仲 亮(京都大学情報学研究科)
 概要:
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
 題目:統計的学習理論におけるVC次元と組合せ論
          VC dimensions of statistical inferences and combinatorics
 発表者:赤間 陽二(東北大学数学)
 概要:
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
 題目:Recent topics on grammatical inference
 発表者:吉仲 亮(京都大学情報学研究科)
 概要:
We discuss the learnability context-free grammars based on Alexander Clark's syntactic concept lattice.

 16:00-17:00
 題目:Godel Logics, Continuous Embeddability and Fraisse's Conjecture
 発表者:N. Preining(北陸先端大学)
 概要:
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.


 9月19日(水)

 9:30-10:00
 題目:合同な球面四角形による球面タイリングの分類に向けて
          Towards classification of spherical tilings by congruent quadrangles
 発表者:赤間 陽二(東北大学数学)
 概要:
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.
(collaborations with H. Tanaka, H. Hiroki)

 10:15-11:45
 題目:多面体の展開図の列挙と索引化について
          Enumeration and indexing of development maps of polyhedra
 発表者:堀山 貴史(埼玉大情報)
 概要:
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
 題目:多面体の組合せ構造の列挙とその周辺
          Enumeration of combinatorial types of polytopes
 発表者:宮田 洋行(東北大学情報科学研究科)
 概要:
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
 題目:ファノ多面体の分類理論 (I)
          Classification of Fano polytopes (I)
 発表者:佐藤 拓(岐阜聖徳学園大経済)
 概要:
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
 題目:VC dimension and fewnomials
 発表者:櫻井 彰人(慶応義塾大学理工)
 概要:
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.


 9月20日(木)

 9:00-9:45
 題目:ファノ多面体の分類理論 (II)
          Fano polytopes and their classification (II)
 発表者:佐藤 拓(岐阜聖徳学園大経済)
 概要:
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
 題目:Problems related to support vector machines in KDDI labs
 発表者:松本 一則(KDDI研究所)
 概要:
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
 題目:データマイニングにおける離散構造の列挙
          Enumeration of discrete structures by data mining
 発表者:有村 博紀(北海道大学大学院情報科学研究科)
 概要:
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
 題目:ZDDを用いた行列演算の高速化
          Speed-up of Matrix operations by ZDD
 発表者:西野 正彬(NTTコミュニケーション科学基礎研究所)
 概要:
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
     討議
 Chair:山本 章博(京都大学情報学研究科)