IN – Track A

Project

IN-A4

Project Heads

Project Members

Tamás Mészáros (FU)

Project Duration

01.01.2020 – 31.12.2020

Located at

FU Berlin

Cooperation partners

• Sebastian Pokutta (Zuse Institut Berlin)
• Christoph Spiegel (Universitat Politècnica de Catalunya)

Generous computational resources are provided by the Zuse Institut Berlin.

Description

Background

Recently the AlphaGo Zero program, after tabula rasa reinforcement learning from games of self-play, managed to achieve a level of play that even the strongest rated Go player of the world stands no chance against it. Due to the enormous size of the game tree, earlier this was believed to be impossible. Later this approach was generalized into a single AlphaZero algorithm that can achieve similar performance in several other challenging domains. In particular, starting from random play, and given no domain knowledge except the game rules, it was able to achieve \superhuman” level of play in various games of perfect information, including chess, shogi (Japanese chess) and Go. Positional games are an extensive family of games of perfect information. Their theory is a thoroughly studied area of contemporary mathematics with a rich history and deep connections to combinatorics, random structures, algorithms, and theoretical computer science. A positional game involves two players alternately occupying the vertices of a hypergraph H. The winner of the game is determined by the family H and a rule; for example it is the player who first fully occupies a member of H. Well known examples of such games are Tic-Tac-Toe, Hex, and Shannon’s Switching Game.

Goals

The mathematical theory of positional games is well developed. In particular, for many interesting games optimal strategies are known, which is very much not the case for chess, shogi, or Go. This could make positional games a fertile ground for a more quantitative analysis of the performance of learning algorithms than it was possible in scenarios with suboptimal opponents. All this still in a complex environment, which might require the development of various novel heuristic ideas to improve the algorithms. One aim of the project would be to develop a theoretical framework for positional games to evaluate learning algorithms like AlphaZero. A main ingredient of the Alpha Zero program is a deep neural network, whose parameters are trained by self-played reinforcement learning, using a Monte-Carlo tree search. Despite its great experimental success of Monte Carlo strategies, very little is known about the mathematical reasons, if any, underpinning that success. As a potential first step towards such understanding, it would be interesting to know more about the quality of the basic Monte Carlo strategies on positional games with the property that the outcome of the game with optimal players is the same as the outcome with random players, with high probability (as the board size tends to infinity). Such games include for example the connectivity game and the Hamiltonicity game.

Selected Publications

• D. Hefetz, M. Krivelevich, M. Stojakovic, and T. Szabó. Positional Games. Vol. 44 of Oberwolfach Seminars. Birkhäuser, Basel (2014).

Background

We say that a concept class (hypergraph) H on the ground set X shatters a given set S ⊆ X if the restriction of H to S contains all possible subsets of S, and the family of subsets of X shattered by H is denoted by Sh(H). The Vapnik-Chervonenkid dimension (VC dimension for short) of H, denoted by VC-dim(H), is the size of the largest set shattered by H. It is an important parameter in the theory of machine learning, in particular, it measures the learnability of the concept class. The Sauer-Shelah lemma states that we always have |Sh(H)| ≥ |H|. Concept classes which satisfy the inequality with equality are called (shattering) extremal, but they also appear in the literature under the names ample and lopsided classes. An easy corollary of the Sauer-Shelah lemma is thatConcept classes satisfying the above inequality with equality are called maximum classes, and serve as important examples. Note that maximum classes are, in particular, extremal. A (labeled) sample is a pair s = (H,S) with H ⊆ S ⊆ X. The size of s is |S|. An unlabeled sample is simply a set S. A sample s is said to be realizable by the concept class H if there is a concept C ∈ H such that C ∩ S = H. A (labeled) sample compression scheme of size k for a concept class H consist of a compression function K, which maps realizable samples to subsamples of size at most k, and a reconstruction function R, which takes possible outputs of K and maps them to concepts that need to realize the original sample. An unlabeled sample compression scheme of size k is a sample compression scheme where the compressed subsamples are unlabeled. The smallest sample size to which a given concept class can be compressed is believed to provide an alternative way to measure the learnability of concept classes. Along this line, Littlestone, Floyd and Warmuth conjectured that for every concept class of VC-dimension d there exists a sample compression scheme of size O(d), and already they proved it for maximum classes with sample size d. Then almost 20 years passed without significant progress, until recently the conjecture came to the forefront again. Moran and Yehudayoff proved that for every concept class there is a compression scheme of size O(exp(d)); while Moran and Warmuth proved the conjecture for extremal concept classes with sample size d.

Goals

The far-reaching goal of the project is to get closer to the full resolution of the compression scheme conjecture. In full generality this might be out of reach of the possibilities of this project, but still we are hopeful to make several steps in this direction. More concretely we plan to study the extension of the conjecture, where we look for unlabeled compression schemes instead of labeled ones in certain special cases, such as extremal classes. According to the current state of the art it is not clear how different the two variants of compression schemes are. Another far-reaching goal of the project is to move towards the better understanding of the differences, if any.

Given an extremal class H , a representation map is a bijection r : H → Sh(H) for which C ∩ (r(C) ∪ r(C’)) ≠ C’ ∩ (r(C) ∪ r(C’)) for all C ≠ C’ ∈ H. Recently Chalopin et al., by extending an earlier result of Kuzmin and Warmuth, showed that the existence of a representation map for an extremal class of VC dimension d implies an unlabeled compression scheme of size d. Unfortunately, they were able to construct such representation maps only for maximum classes. Our goal is to extend their results. We believe that the algeraic methods, that were developed by Mészáros and Rónyai to study set shattering and related problems, could be of significant help to advance further on these intriguing problems.

Selected Publications

• C. Kusch and T. Mészáros. A note on a conjecture about shattering-extremal set systems. Discrete Applied Mathematics, Vol. 276, Pages 92-101 (2020). https://doi.org/10.1016/j.dam.2019.07.016
• T. Mészáros, Standard monomials and extremal point sets, Discrete Mathematics, Vol. 343(4), article ID: 111785 (2020). https://doi.org/10.1016/j.disc.2019.111785
• T. Mészáros and L. Rónyai. Standard monomials and extremal vector systems (extended abstract). Electronic Notes in Discrete Mathematics, Vol. 61(C), Pages 855-861 (2017). https://doi.org/10.1016/j.endm.2017.07.046
• T. Mészáros. Algebraic Phenomena in Combinatorics: Shattering-Extremal Families and the Combinatorial Nullstellensatz. PhD thesis, Central European University, Budapest (2015).
• L. Rónyai, T. Mészáros. Some Combinatorial Applications of Gröbner bases. Proc. CAI 2011, LNCS, Vol. 6742, Pages 65-83 (2011).
• T. Mészáros. S-extremal set systems and Gröbner bases. Diploma thesis, Budapest University of Technology and Economics (2010).