CoChat
Sign Up
PreprintCited by 1Game Theory and ApplicationsExplainable Artificial Intelligence (XAI)Adversarial Robustness in Machine Learning

Learning to Give Checkable Answers with Prover-Verifier Games

Open access
Anil, Cem, Zhang, Guodong, Wu, Yuhuai, Grosse, Roger·2021·arXiv
DOI 10.48550/arxiv.2108.12099arXiv 2108.12099
Open this paper in CoChat — free accountOpen PDF

Abstract

Our ability to know when to trust the decisions made by machine learning systems has not kept up with the staggering improvements in their performance, limiting their applicability in high-stakes domains. We introduce Prover-Verifier Games (PVGs), a game-theoretic framework to encourage learning agents to solve decision problems in a verifiable manner. The PVG consists of two learners with competing objectives: a trusted verifier network tries to choose the correct answer, and a more powerful but untrusted prover network attempts to persuade the verifier of a particular answer, regardless of its correctness. The goal is for a reliable justification protocol to emerge from this game. We analyze variants of the framework, including simultaneous and sequential games, and narrow the space down to a subset of games which provably have the desired equilibria. We develop instantiations of the PVG for two algorithmic tasks, and show that in practice, the verifier learns a robust decision rule that is able to receive useful and reliable information from an untrusted prover. Importantly, the protocol still works even when the verifier is frozen and the prover's messages are directly optimized to convince the verifier.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2108.12099

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Anil et al. (2021) propose Prover-Verifier Games, where a weak verifier can verify proofs from a more powerful but untrustworthy prover; their system doesn't include an adversarial component between untrustworthy provers, so it is more similar to consultancy than debate.

    “Anil et al. (2021) propose Prover-Verifier Games (PVGs), where a weak verifier can verify proofs from a more powerful (but untrustworthy) prover. This is similar to scalable oversight, but their system doesn't include an adversarial component between the untrustworthy provers, so in that respect their approach is more similar to consultancy than debate.”

    From Debate Helps Supervise Unreliable Experts (2023) · cites this paper as Anil et al. (2021)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 30

  1. [1][1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009. -
  2. [2][2] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450 , 2016. - · arXiv
  3. [4][4] Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. A game theoretic approach to class-wise selective rationalization. Advances in Neural Information Processing Systems , 32:10055-10065, 2019. -
  4. [5][5] Tong Che, Xiaofeng Liu, Site Li, Yubin Ge, Ruixiang Zhang, Caiming Xiong, and Yoshua Bengio. Deep verifier networks: Verification of deep discriminative models with deep generative models. In AAAI , 2021. -
  5. [6][6] Thomas M Cover. Elements of information theory . John Wiley & Sons, 1999. -
  6. [7][7] Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint arXiv:1805.10265 , 2018. - · arXiv
  7. [8][8] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In Proceedings of the 37th International Conference on Machine Learning , 2020. -
  8. [10][10] Shafi Goldwasser, Guy N Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) . Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. -
  9. [11][11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems , pages 2672-2680, 2014. -
  10. [12][12] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations , 2015. -
  11. [13][13] Marcel Hildebrandt, Jorge Andres Quintero Serna, Yunpu Ma, Martin Ringsquandl, Mitchell Joblin, and Volker Tresp. Reasoning on knowledge graphs with debate dynamics. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, pages 4123-4131, 2020. -
  12. [16][16] Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al. Spatial transformer networks. Advances in neural information processing systems , 28:2017-2025, 2015. -
  13. [17][17] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer Aided Verification , pages 97-117. Springer, 2017. -
  14. [20][20] Tao Lei, Regina Barzilay, and Tommi S. Jaakkola. Rationalizing neural predictions. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016 , pages 107-117. The Association for Computational Linguistics, 2016. -
  15. [21][21] Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In International Conference on Machine Learning , 2013. -
  16. [22][22] C Maddison, A Mnih, and Y Teh. The concrete distribution: A continuous relaxation of discrete random variables. In Proceedings of the international conference on learning Representations , 2017. -
  17. [23][23] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning , pages 3578-3586. PMLR, 2018. -
  18. [24][24] Rafael Müller, Simon Kornblith, and Geoffrey E Hinton. When does label smoothing help? Advances in Neural Information Processing Systems , 32:4694-4703, 2019. -
  19. [25][25] Jorge Nocedal and Stephen Wright. Numerical optimization . Springer Science & Business Media, 2006. -
  20. [26][26] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences , 117(40):24652-24663, 2020. -
  21. [27][27] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An imperative style, highperformance deep learning library. Advances in neural information processing systems , 32:8026-8037, 2019. -
  22. [28][28] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations , 2018. -
  23. [30][30] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in Neural Information Processing Systems , 31:10802-10813, 2018. -
  24. [32][32] Jonathan Uesato, Ananya Kumar, Csaba Szepesvari, Tom Erez, Avraham Ruderman, Keith Anderson, Krishnamurthy Dj Dvijotham, Nicolas Heess, and Pushmeet Kohli. Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures. In International Conference on Learning Representations , 2018. -
  25. [33][33] John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior . Princeton university press, 2007. -
  26. [34][34] Yuanhao Wang*, Guodong Zhang*, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference on Learning Representations , 2020. URL https://openreview.net/forum?id=Hkx7\_1rKwS . -
  27. [35][35] Nicholas Watters, Loic Matthey, Christopher P Burgess, and Alexander Lerchner. Spatial broadcast decoder: A simple architecture for learning disentangled representations in vaes. arXiv preprint arXiv:1901.07017 , 2019. - · arXiv
  28. [36][36] Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. In Proceedings of the 32nd International Conference on Neural Information Processing Systems , pages 8410-8419, 2018. -
  29. [37][37] Mo Yu, Shiyu Chang, Yang Zhang, and Tommi Jaakkola. Rethinking cooperative rationalization: Introspective extraction and complement control. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) , pages 4094-4103, 2019. -
  30. [38][38] Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger Grosse. Don't fix what ain't broke: Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. arXiv preprint arXiv:2102.09468 , 2021. · arXiv

Cited by

Sorted by citations

Authors
Anil, C., Zhang, G., Wu, Y., & Grosse, R.
Affiliations
University of Toronto (CA)
ORCID
Zhang, Guodong
Venue
arXiv
Publisher
arXiv
Published
2021
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2108.12099
arXiv
2108.12099
OpenAlex
W3197492536
Cited by
0
References
2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Canadian Institute for Advanced Research
  • Government of Canada
Topics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
Keywords
verifiable reasoning, game-theoretic learning, Nash equilibrium, sequential games, concurrent games, explainable AI

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review