Tamás Mészáros (FU)
01.01.2020 – 31.12.2020
Freie Universität Berlin
Generous computational resources are provided by the Zuse Institut Berlin.
We investigate two different setups of learning in connection with a hypergraph H.
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.
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.
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.
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.
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.