Unsupervised Neural Networks Fight in a Minimax Game

Jürgen Schmidhuber (2018)
(Pronounce: You_again Shmidhoobuh)

Edit of June 12, 2019: There is now a more detailed write-up [AC19] of the summary below.

One of the most important goals of research on Artificial Neural Networks (NNs) is to create algorithms that learn the statistics of given data. To achieve this, I introduced a new type of unsupervised learning in the 1990s. It is based on the principles of gradient descent/ascent in a minimax game where one NN minimizes the objective function maximized by another. This duel between two unsupervised adversarial NNs was called Predictability Minimization (PM) [PM3, PM1, PM2, PM4, ZIF].

PM requires an encoder network with initially random connection strengths or weights. It receives data samples (such as images) through its input units (white circles in the figure to the right) and generates codes thereof across its output units called code units (grey). Each code unit can be active in the interval [0,1]. A separate predictor network (black output units in the figure) is trained to predict each code unit from the remaining code units. Both encoder and predictor may have hidden units (not shown here). The predictor learns the conditional expectation of each code unit, given the other code units. But the encoder is trained to maximize exactly the same objective function minimized by the predictor (e.g., mean squared error). That is, each code unit wants to become as unpredictable as possible. Predictor and encoder fight each other, to motivate the encoder to achieve a "holy grail" of unsupervised learning, namely, an ideal, disentangled, binary, factorial code of the data, where the code units are statistically independent of each other - see relevant proof by Dayan & Zemel & Pouget (1992) [PM5, PM2]. Ideally, after learning, the probability of a given data pattern is simply the product of the probabilities of its code units; these probabilities equal the predictor's outputs. (Pattern codes can be decoded again [PM1].)

Generative Adversarial Networks (GANs, 2014) [GAN1] also use an unsupervised minimax principle to model the statistics of given data. The well-known NIPS 2014 GAN paper [GAN1] claims that PM is not based on a minimax game with a value function that one agent seeks to maximise and the other seeks to minimise, and that for GANs "the competition between the networks is the sole training criterion, and is sufficient on its own to train the network," while PM "is only a regularizer that encourages the hidden units of a neural network to be statistically independent while they accomplish some other task; it is not a primary training criterion" [GAN1]. However, good old PM is indeed a pure minimax game, too, e.g., [PM3], Equation 2 (there is no "other task"). In particular, PM was also trained [PM3, PM1] (also on images [PM3, PM4]) such that "the competition between the networks is the sole training criterion, and is sufficient on its own to train the network."

Unsupervised Minimax for Artificial Curiosity in Adversarial Reinforcement Learning

Many recent papers on curiosity for RL are based on this simple principle. Certain drawbacks of the approach were overcome in numerous follow-up papers starting in 1991, e.g., [AC91, AC91b], and many more.

In particular, in an adversarial approach of 1997 [UARL3-5], two dueling, reward-maximizing modules (both general computers) called the left brain and the right brain can collectively design an experiment: a (probabilistic) program that defines how to execute an action sequence in the environment, and how to compute the final experimental outcome through an instruction sequence implementing a computable function (e.g., a binary yes/no classification) of the observation sequence triggered by the experiment. Both brains can predict experimental outcomes before they are known. If their predictions or hypotheses differ, after having generated and executed the experiment, the surprised loser pays an intrinsic reward to the winner in a zero sum game.

This motivates the unsupervised two brain system to focus on the "interesting" things, losing interest in boring aspects of the world that are consistently predictable by both brains, as well as seemingly random aspects of the world that are currently still hard to predict by any brain. Again, in the absence of external reward, each unsupervised module is trying to maximise the value function minimised by the other. This type of artificial curiosity & creativity may drive artificial scientists and artists, e.g., [AC09], and may also accelerate the intake of external reward, e.g., [UARL5], intuitively because a better understanding of the world can help to solve certain problems faster.

Today, many are using the unsupervised minimax principle, both for modeling data distributions and for artificial curiosity (and also for generating algorithmic art). Compare recent slides [ICML18ws].

References

[PM1] J. Schmidhuber. Learning factorial codes by predictability minimization. Neural Computation, 4(6):863-879, 1992. Based on TR CU-CS-565-91, Univ. Colorado at Boulder, 1991. PDF. More.

[PM2] J. Schmidhuber. Netzwerkarchitekturen, Zielfunktionen und Kettenregel (Network architectures, objective functions, and chain rule). Habilitation (postdoctoral thesis), Institut for informatics, Tech Univ. Munich, 1993. PDF. HTML.

[PM3] J. Schmidhuber, M. Eldracher, B. Foltin. Semilinear predictability minimzation produces well-known feature detectors. Neural Computation, 8(4):773-786, 1996. PDF. More.

[PM4] N. N. Schraudolph, M. Eldracher, J. Schmidhuber. Processing Images by Semi-Linear Predictability Minimization. Network, 10(2): 133-169, 1999. PDF.

[PM5] P. Dayan, R. Zemel, and A. Pouget, 1992. Personal Communication. See [PM2], Sec. 6.9.3.

[ZIF] J. Schmidhuber. Neural predictors for detecting and removing redundant information. In H. Cruse, J. Dean, and H. Ritter, editors, Adaptive Behavior and Learning. Kluwer, 1998. PDF. HTML.

[GAN1] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio. Generative adversarial nets. NIPS 2014, 2672-2680, Dec 2014.

[PhD] J. Schmidhuber. Dynamische neuronale Netze und das fundamentale raumzeitliche Lernproblem (Dynamic neural nets and the fundamental spatio-temporal credit assignment problem). Dissertation, TUM, 1990. PDF. HTML.

[UARL1] J.  Schmidhuber. Making the world differentiable: On using fully recurrent self-supervised neural networks for dynamic reinforcement learning and planning in non-stationary environments. Technical Report FKI-126-90, TUM, Feb 1990, revised Nov 1990. PDF

[UARL2] J.  Schmidhuber. A possibility for implementing curiosity and boredom in model-building neural controllers. In J. A. Meyer and S. W. Wilson, editors, Proc. of the International Conference on Simulation of Adaptive Behavior: From Animals to Animats, pages 222-227. MIT Press/Bradford Books, 1991. PDF. HTML.

[UARL3] J. Schmidhuber. What's interesting? Technical Report IDSIA-35-97, IDSIA, July 1997. More on artificial curiosity.

[UARL4] J. Schmidhuber. Artificial Curiosity Based on Discovering Novel Algorithmic Predictability Through Coevolution. In Proc. CEC 1999, p. 1612-1618, IEEE Press, Piscataway, NJ, 1999.

[UARL5] J. Schmidhuber. Exploring the Predictable. In Ghosh, S. Tsutsui, eds., Advances in Evolutionary Computing, p. 579-612, Springer, 2002. PDF. HTML.

[AC91b] J.  Schmidhuber. Adaptive curiosity and adaptive confidence. Technical Report FKI-149-91, Institut fuer Informatik, Technische Universitaet Muenchen, April 1991. PDF.

[AC91] J.  Schmidhuber. Curious model-building control systems. In Proc. International Joint Conference on Neural Networks, Singapore, volume 2, pages 1458-1463. IEEE, 1991. PDF. HTML. Numerous papers on artificial curiosity followed later.

[AC09] J. Schmidhuber. Art & science as by-products of the search for novel patterns, or data compressible in unknown yet learnable ways. In M. Botta (ed.), Et al. Edizioni, 2009, pp. 98-112. PDF. (More on artificial scientists and artists.)

[ICML18ws] J. Schmidhuber. Unsupervised Minimax: Nets That Fight Each Other. Slides for the ICML 2018 Workshop on Theoretical Foundations and Applications of Deep Generative Models. PDF.

[AC19] J. Schmidhuber. Unsupervised Minimax: Adversarial Curiosity, Generative Adversarial Networks, and Predictability Minimization. 11 Jun 2019. Preprint arXiv/1906.04493.

PS: Earlier adversarial settings include reinforcement learners playing against themselves, e.g., [SAM59], or predator prey games in artificial evolution [HIL90]. Chess programs date back to 1945 [ZUSE45], and for many decades have used a recursive minimax procedure with continually shrinking look-ahead. Such earlier adversarial settings, however, neither were unsupervised, nor gradient-based, nor about modeling the statistics of given data, nor about intrinsic rewards for artificial curiosity:

[SAM59] A. L. Samuel. Some studies in machine learning using the game of checkers. IBM Journal on Research and Development, 3:210-229, 1959.

[HIL90] W. D. Hillis. Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D: Nonlinear Phenomena, 42(1-3):228-234, 1990.

[ZUSE45] K. Zuse. Chess programs, in The Plankalkül. Rept. No. 106, Gesellschaft für Mathematik und Datenverarbeitung, pages 201-244, 1976. Translation of German original, 1945.

.