Impossibility Results in AI: A Survey
arXiv:2109.00484 · doi:10.1145/3603371
Abstract
An impossibility theorem demonstrates that a particular problem or set of problems cannot be solved as described in the claim. Such theorems put limits on what is possible to do concerning artificial intelligence, especially the super-intelligent one. As such, these results serve as guidelines, reminders, and warnings to AI safety, AI policy, and governance researchers. These might enable solutions to some long-standing questions in the form of formalizing theories in the framework of constraint satisfaction without committing to one option. We strongly believe this to be the most prudent approach to long-term AI safety initiatives. In this paper, we have categorized impossibility theorems applicable to AI into five mechanism-based categories: deduction, indistinguishability, induction, tradeoffs, and intractability. We found that certain theorems are too specific or have implicit assumptions that limit application. Also, we added new results (theorems) such as the unfairness of explainability, the first explainability-related result in the induction category. The remaining results deal with misalignment between the clones and put a limit to the self-awareness of agents. We concluded that deductive impossibilities deny 100%-guarantees for security. In the end, we give some ideas that hold potential in explainability, controllability, value alignment, ethics, and group decision-making. They can be deepened by further investigation.
arXiv comment23 pages, 2 figures, 103 references
References in corpus (23)
- Ultimate physical limits to computation
- Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations
- Inherent Trade-Offs in the Fair Determination of Risk Scores
- Towards Robust Interpretability with Self-Explaining Neural Networks
- Why does deep and cheap learning work so well?
- The Hypervolume Indicator: Problems and Algorithms
- Information-theoretic approach to the study of control systems
- Constructor Theory of Information
- A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points
- Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
- Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
- Physical limits of inference
- Superintelligence cannot be contained: Lessons from Computability Theory
- Occam's razor is insufficient to infer the preferences of irrational agents
- Formal Mathematics Statement Curriculum Learning
- Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning
- Impossibility and Uncertainty Theorems in AI Value Alignment (or why your AGI should not have a utility function)
- Personal Universes: A Solution to the Multi-Agent Value Alignment Problem
- Truthful AI: Developing and governing AI that does not lie
- The Impossibility Theorem of Machine Fairness -- A Causal Perspective
- Constraints on physical reality arising from a formalization of knowledge
- A general theory of identification
- What is important about the No Free Lunch theorems?