8 ms·
Game Theory Reveals the Future of Deep Learning
- arcanus 10y agoGame theory is a fun way to tell stories... but it is seldom predictive. Conversely, machine learning seldom provides a story (at least in a human readable form) but it is predictive by nature.
- taeric 10y agoThis "post-hoc" nature of game theory bothers me a lot. People love the stories they can tell about things using game theory, but I have seen far fewer example of people understanding a new scenario using it.
- oli5679 10y agoAuctions are good example of a domain where game theory (and reverse game theory or mechanism design) often makes useful predictions and has practical influence. Google and Facebook use mechanisms that approximate the VCG allocation rule for some of their ad content and know that they should not be able to find massive improvements on this due to theory. I agree that it is often less predictive and more like stories.
- nabla9 10y agoGame theory is part of the toolbox used to design, study and understand machine learning algorithms. It's currently the bleeding edge of machine learning.
- Xcelerate 10y agoPersonally, I think information theory is going to end up being a lot more important to AI than game theory.
- sgt101 10y agoWell here as are a few predictions made by game theory. 1. There wasn't a nuclear war today 2. Every telco in the world gives large chunks of money to governements due to auctions 3. Ebay sellers get higher prices than they should Also, I can read association rules, decision trees and lisp programs ok... and yet my machine learning programs (ok ok nowadays the ones I get out of various apis and packages) have written them...
- spectrum1234 10y agoWhy the eBay one?
- taeric 10y ago1 and 3 aren't predictions, but post-hoc explanations. There is an argument that game theory helped lead to 1, I suppose. But, in general, I think that is giving them more credit than they would even ask for. Mutually assured destruction is far from their central theorem. 2 could just as easily be explained by standard supply/demand scenarios. There is a very limited supply of that is auctioned off to telcos and they have a very vested interest in buying as much as they can. Even if they are not going to utilize it.
- sgt101 10y agoWhat!!! 1) You can allocate credit how you like, but there's a dominant strategy for that too. 2)Ok for the UK case see http://www.nuff.ox.ac.uk/users/klemperer/biggestpaper.pdf http://www.nuff.ox.ac.uk/users/klemperer/biggestpaper.pdf And look them up. Interestingly your position makes me wonder if you are actually an exec working in a senior finance position in a major telco?
- tpm 10y agoWell, game theory can be used to create outcomes: https://en.m.wikipedia.org/wiki/Mechanism_design https://en.m.wikipedia.org/wiki/Mechanism_design
- lngnmn 10y agoThe Game Theory has nothing to say about partially observable, stochastic, continuous environments and has no concept of future.
- deleted 10y ago[deleted]
- vowelless 10y agoThis post is in particular about utilizing certain concepts from game theory to build new architectures. For example, it talks about adversarial networks where the problem is reduced to finding Nash equilibria between competing models -- a concept that merges game theory with neural networks. The post is not talking about making a new paradigm primarily based on game theory concepts.
- JustFinishedBSG 10y agoGame theory does have things to say about observable, stochastic, continuous environments and has a concept of future actually.
- nabla9 10y ago> The Game Theory has nothing to say about partially observable, stochastic, continuous environments and has no concept of future. This is not true. What makes you think this way? Game theory studies games with stochastic outcomes, adversaries, and partial observability. Bayesian Nash equilibrium, trembling hand equilibrium and correlated equilibrium are generalizations of Nash equilibrium into these domains. Game theory also extends to continuous environments and sequential games that have concept of past and future.
- aub3bhat 10y agoWhats is the Nash equilibrium of Pong? or Go? or Chess? All the generalizations you cite are fancy economics methods which loose applicability at the first contact with complex real world scenarios. Game Theory is like asking question such as "Is chess a win for white? [1]" Sure answering this question might be important theoretically but its of no use when designing an agent that plays and learns. [1] https://en.wikipedia.org/wiki/Solving_chess https://en.wikipedia.org/wiki/Solving_chess
- EternalData 10y agoA lot of advances in deep learning have come from providing more data and semi-structured information, but there are a finite amount of fields for which this can apply. Using game theory dynamics can move AI to transfer of domain knowledge and can create more adaptable deep learning architectures. It could also be a pathway to "stronger" forms of AI.
- Houshalter 10y agoAdversarial networks can be viewed as different agents competing against each other. But beyond that, I don't see how game theory is relevant or what insights it provides. This article is super vague and confusing to me. >Where do these regularizations come from and how can we select a good regularization? How do we handle impartial information? This is where a game theoretic viewpoint becomes important. Generalization is sometimes referred to as ‘structural risk minimization’. Ok... and what useful insight do the game theorists have here? He doesn't elaborate at all. Regularization is a very well studied concept already. I don't see how this is connected to game theory at all. Regularization is all about priors and Occam's razor.
- westoncb 10y agoIf nothing else, I think the idea was initially important because it provided the insight to pit two networks against each other in a competition as an optimization strategy. Now, since the competing networks can be formally characterized as a minimax two-player game, other theorems relating to these games may provide further insight in how to proceed.
- kem 10y agoThe article is weird but also interesting to me at the same time. My background is in more traditional statistical modeling. The adversarial networks paradigm is really fascinating to me because it's a new way to think about model fit problems. It may turn out to be the same as some traditional model fit statistics approaches, but they're usually not thought of as competitive, which seems to open up a new way of thinking of it. At some point in the author's discussion of game theory, I began thinking that if DL does go that route, it will eventually rediscover Bayesian statistics, which can be derived from decision-theoretic principles. It seems like many things in DL have parallels in traditional statistical theory, but are expressed in a mechanistic way. I guess my broader point is that I had the opposite reaction as a lot of people: rather than wondering how game theory might be relevant, to me it seemed inevitable, given the important role it plays in basic derivations of major inferential paradigms. Those derivations usually leave the mechanisms of decision theory a black box, and in DL the making the contents of the box is the focus.
- 10y ago
- rdlecler1 10y agoOne way to avoid overfitting is to trim spurious interactions Wij -> O. This constraint forces the network to economize on the neural circuitry, thereby driving the system to find an optimal network topology. Hypothetically this should favor certain circuit-design principles. I don't know how much work has been done in artificial neural networks but there has been quite a bit of work gone with artificial gene regulatory networks which utilize the same mathematical model of integrating weighted inputs and passing this through some kind of sigmoidal/logistic function.
- aub3bhat 10y agoThe author is wildly extrapolating limited results ("Nash Equilibrium outcomes achieved by agents trained using deep reinforcement learning") to the entire field. Just because in DRL agents approach nash equilibrium in limited set of games does not means that somehow using nash equilibrium is going to help design future algorithms. E.g. for several games such as Pong, Go on which we know that DRL outperforms traditional methods, there is no tractable Nash equilibrium. Also let alone so many other problem which come under umbrella of deep learning such as recognition / detection/ Seq to Sequence prediction where there is no "Game theory" component.
- pizza 10y agoThe author's description of "approximation of Nash equilibrium" is a description of the use of contradiction in the time-evolution of the two internal components of GANs
- westoncb 10y agoMy understanding is that the use of game theory in this context has nothing to do with the domain in which the network is being trained. It's not about creating game playing AI's—it's about a 'game' between two neural networks, one who competes by getting better at classifying, and the other by getting better at generating. That basic architecture is quite general—which I think is why you also see e.g. LeCun being excited about this direction. To be fair, the article does a kind of weird thing in discussing three different ways game theory has shown up in the context of machine learning recently—but they're all separate ideas really. Edit: a more precise description in the abstract here: https://arxiv.org/abs/1406.2661 https://arxiv.org/abs/1406.2661
- webmaven 10y ago> Also let alone so many other problem which come under umbrella of deep learning such as recognition / detection/ Seq to Sequence prediction where there is no "Game theory" component. Ah, but there is! GANS can be applied to all those problems.
- pizza 10y agoI'm guessing a lot of you have read Neuromancer; I liken generative-adversarial networks to be a lot like neuromancer-wintermute networks :) Imagine Robert Axelrod's iterated artificial intelligence agents tournaments [0], reloaded; let's pit GANs with LSTM cells, deep-q-networks, style-transferring networks, random forest algos, MCMC algorithms, word2vec architectures, etc. against one another, if only to see possible new failure modes of tit-for-tat. [0] https://en.wikipedia.org/wiki/Tit_for_tat#Background https://en.wikipedia.org/wiki/Tit_for_tat#Background
- hiddencost 10y agoThe second half of your post reads like word salad made from headlines about ML. They're all words, but the fact that you thought they form a thought with semantic content makes me worried. We need fewer MBAs coked out of their mind meddling with this stuff. The advancements that are interesting in ML mostly come from deep statistics and information theory and very sophisticated analysis, not combining the most popular black boxes that you read a medium post about.
- pizza 10y agoI think you might be over-fitting a bit with your model there
- visarga 10y agoSupervised learning - is learning from pairs of input -> desired output. Unsupervised learning - is learning based on predicting future, present or past data from current data. Both use immediate feedback. Reinforcement learning is based on learning from dynamic datasets as opposed from static datasets. Games are like dynamic datasets. Of course game theory has a lot to do with deep learning. If the signal you are learning is dynamic, it's related to game theory.
- mcintyre1994 10y ago> If the signal you are learning is dynamic, it's related to game theory. I'm not really familiar with the literature in this area, so sorry if this sounds dumb. But what you're saying here seems to make sense and sounds almost profound - like there's a vast amount of research (game theory) that's immediately related in some way. Is there somewhere I can read more about the relationship?
- dandermotj 10y agoThe references made in the article are probably the best place to start.
- joeyo 10y agoIn what way does unsupervised learning "use immediate feedback"? It's unique in that it does not use reward or error feedback signals derived from labeled data!
- argonaut 10y agoReinforcement learning is not "learning from dynamic datasets as opposed from static datasets." Reinforcement learning is learning from sequences of states/actions and a reward signal. The sequences could be totally deterministic and similar across different runs of the environment, and hence what I'm guessing you're calling "static" ("static" really has no meaning in the ML field). Or not. Go is totally deterministic, for example, but RL is still applied there. Unsupervised learning is kind of vague, but it's supervised learning except the "desired output" (label) is generated from the input, or some desired statistic is inferred from the input. Inferring past/present or predicting future data is only a subset of the first case.
- graycat 10y agoMy background in game theory is from: (1) careful study, teaching, and applying the detailed mathematics of linear programming and, in particular, its approach to proving the basic von Neumann saddle point theorem of game theory, (2) applications of game theory to US strategic systems analysis, e.g., the Blue side positioning submarines and targeting multi-warhead nuclear missiles and the Red side allocating submarine search resources so that if Red shoots first Blue gets maximum expected target value destroyed, (4) study of game theory from Guillermo Owen, Game Theory, W. B. Saunders. (5) study of game theory, including Nash's result with a nice proof by Lemke and Sion's result, in T. Parthasarathy and T. E. S. Raghavan, Some Topics in Two-Person Games, ISBN 0-444-00059-3, American Elsevier. With this background, I read the OP and found no clear connections with anything in game theory.
- westoncb 10y agoSo is [1], for example, misleading? [1] https://arxiv.org/abs/1406.2661 https://arxiv.org/abs/1406.2661
- nl 10y agoThat paper doesn't mention game theory or the Nash equilibrium at all. Perhaps you mean [2], which does. However, the article seems to misinterpret this: the fact that that system approximates the Nash equilibrium should be expected. Any system (including humans) that performs well in those types of games will, almost by definition. [2] https://arxiv.org/pdf/1603.01121.pdf https://arxiv.org/pdf/1603.01121.pdf
- westoncb 10y agoIt doesn't mention Nash equilibrium, but the whole approach they are discussing comes from the idea of pitting two networks against each other in a "minimax two-player game". "We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models ... This framework corresponds to a minimax two-player game." Edit: Regarding the paper you linked to. The fact that a Nash equilibrium is expected is an important part of why it's interesting to structure things this way: it's an optimization process guaranteed to stabilize (whereas it's problematic that other approaches will diverge). "When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged"
- jonmc12 10y agoI think the argument for using physics models for constraints in a DL system was a more clear argument https://www.youtube.com/watch?v=5MdSE-N0bxs https://www.youtube.com/watch?v=5MdSE-N0bxs
- nl 10y agoand (3) A way to predict behavior of human participants. The last application can make your skin crawl! A lot of machine learning is about predicting human participants. Thing like "winning" at ImageNet have devolved into predicting the exact labels humans will put on a subset of the ImageNet dataset (as the "easy" labels are solved and it now comes down to working out what the most humans labelled confusing images as). If that makes the authors skin crawl, one would have to wonder what they think ML actually is?
- westoncb 10y agoIf you're curious what this is all about, I'd recommend jumping to this point in a video linked to in the article: https://youtu.be/IbjF5VjniVE?t=42m11s https://youtu.be/IbjF5VjniVE?t=42m11s —Yann LeCun will begin saying, "the best idea ever ... is adversarial training." The article is kind of confusing because it's discussing three different ways game theory has shown up in the context of machine learning recently—but they're all totally separate ideas.
- jondubois 10y agoThis adversarial approach sounds a lot like evolutionary computation. The idea of making Artificial Neural Networks compete with each other based on a selection function has been around for many years. I remember learning about it during my undergrad studies 6 years ago. This just sounds like a more refined version of that. Using RNNs instead of ANNs.
- caycep 10y agothe best explanation of this are Ian Goodfellow's talks (i think there are video transcripts online somewhere) or at NIPS this past year. He and a few others also have a new deep learning book just coming out this past month from MIT press
- jonbaer 10y agoComputing Equilibria in Multi-Player Games - http://theory.stanford.edu/~tim/papers/sym.pdf http://theory.stanford.edu/~tim/papers/sym.pdf