Answers.Body: <p><strong>Maybe.</strong></p>
  
  <p>AI has a long history of encountering mathematical impossibilities and then working around them already. While the individuals who solved these problems don't get as much press as Newton, Einstein, or Hawking, a case could be made that their contributions to human knowledge are on a similar scale. Unfortunately, their results don't relate to physical systems, so they can be harder to explain to the layperson. </p>
  
  <p>Something to keep in mind is that your question assumes the correctness of the "<a href="https://en.wikipedia.org/wiki/Great_man_theory" rel="nofollow noreferrer">Great Man Theory</a>" of science history, which holds that science advances by the efforts of exceptional people, and that we need to wait around for more such people to appear for science to advance. This view of scientific history is overly simplistic, and probably wrong. For example, most (all?) of Newton's discoveries were likely to have been made by someone else, around the same time, if he didn't make them (see, e.g. Leibnitz, who actually <em>did</em> discover calculus at the same time), so a better view might be of a large community of researchers who gradually develop more advanced models based on each others' work.</p>
  
  <p>To answer your question, I've listed out some past examples of problems that were overcome, and some outstanding problems that might require the development of new mathematical tools to solve properly. Keep in mind though, that we can't know for sure whether new tools are needed: maybe existing tools are sufficient, but no one has applied them in the right way yet!</p>
  
  <p><strong>Some past problems that plagued AI and required the development of better mathematical approaches</strong>:</p>
  
  <ol>
  <li><p>The <a href="https://en.wikipedia.org/wiki/Combinatorial_explosion" rel="nofollow noreferrer">combinatorial explosion</a> problem appeared to preclude having an AI system reason about probabilities and causation in a logically correct way. This problem was solved by the development of <a href="https://en.wikipedia.org/wiki/Bayesian_network" rel="nofollow noreferrer">Bayesian networks</a> and causal networks, with the work being led by <a href="https://en.wikipedia.org/wiki/Judea_Pearl" rel="nofollow noreferrer">Judea Pearl</a> and his students. Pearl won a Turing award for this, but has received very little coverage in the popular press.</p></li>
  <li><p>Many optimization problems that AI systems need to solve are <a href="https://en.wikipedia.org/wiki/NP-hardness" rel="nofollow noreferrer">NP-hard</a>. This means that no general purpose algorithms exist that can give exact solutions to these problems in a polynomial number of steps. Because of this, the problems were initially viewed as intractable. The development of <a href="https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow noreferrer">PTAS algorithms</a>, and a deep understanding of <a href="https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf" rel="nofollow noreferrer">phase-changes</a> in NP-Hard problems (pioneered by Cheeseman et al.) led to an ability to identify exactly what makes these problems hard, to identify which subparts cause the hardness, and to practical algorithms that solve all sorts of problems in these domains. </p></li>
  <li><p>Much effort in AI was spent designing new classification methods, and arguing about why one might or might not be better than another. The <a href="http://www.no-free-lunch.org/" rel="nofollow noreferrer">No Free Lunch Theorems</a>, along with other work in computational learning theory provided a clear mathematical framework for understanding how systems can learn, and where their limits are. </p></li>
  <li><p>As a more recent example, games involving chance, like Poker, have state spaces so vast that they cannot be searched through effectively, even with heuristics. Phrasing these games in the language of Game Theory, and proving the convergence of the counter-factual minimax regret algorithm provided solutions. Bowling et al. were at the center of this work. It got some press coverage, but most of the coverage focused on "computers can play poker", and not the exiting, more generalizable, lessons AI researchers had learned in the process.</p></li>
  </ol>
  
  <p><strong>Some problems that are still outstanding, and might require new mathematical techniques:</strong></p>
  
  <ol>
  <li><p>Are there efficient algorithms for solving problems in the complexity classes PPAD, NP, or #P? Many AI problems fall into these categories. <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem" rel="nofollow noreferrer">We do not know the answer definitively</a>, and although most researchers suspect that no such algorithms exist, understanding <em>why not</em> seems like it could also provide major research advantages. Existing proof techniques do not seem likely to crack this problem.</p></li>
  <li><p>We have no good mathematical models of subjective experience. While some researchers (like <a href="https://en.wikipedia.org/wiki/Paul_Churchland" rel="nofollow noreferrer">Churchland</a>) think this is not likely to play a major role in the development of intelligent systems, a concrete model could either support or refute that view, and might provide solid frameworks for current problems in AI like the study of <a href="http://www.cs.cornell.edu/~helou/IMRL.pdf" rel="nofollow noreferrer">motivation</a>. </p></li>
  <li><p>The original project of the social sciences was to provide mathematical models of individual humans, and then of human societies. This has mostly been abandoned (Psych is still at it, but Economics prefers to study rational agents instead of humans, and most of the others gave up mathematical modeling entirely to pursue the methodologies of the humanities instead of the sciences). Nonetheless, the lack of sound mathematical descriptions of human behaviours is becoming a major topic within AI, with work on norms, trust, emotion, and other topics. If a mathematical framework were developed to describe the actions of human societies or of individual humans, then AI would be advanced significantly (along with many other fields!).</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-06T19:18:33.420Z
Answers.LastActivityDate: 2018-12-30T20:51:45.460Z
Answers.LastEditDate: 2018-12-30T20:51:45.460Z
Answers.UserDisplayName: John Doucette
Body: <p>As an Electronics &amp; Communication Engineering student I've heard some stories and theories about "The math we have is not enough to complete a thinker-learner AI."</p>
  
  <p>What is the truth? Is humankind waiting for another Newton to make new calculus or another Einstein-Hawking to complete the quantum mechanics?</p>
  
  <p>If so, what exactly do we need? What will we call it? </p>
  
Tags: <machine-learning><agi><math>
Title: Is known math really enough for AI
UserDisplayName: CanSevgi
ThreadText: # Is known math really enough for AI
  
  (Asked by: username_0 on 2018-10-04)
  
  As an Electronics & Communication Engineering student I've heard some stories and theories about "The math we have is not enough to complete a thinker-learner AI."
  
  What is the truth? Is humankind waiting for another Newton to make new calculus or another Einstein-Hawking to complete the quantum mechanics?
  
  If so, what exactly do we need? What will we call it?
  
  **Tags:** machine-learning, agi, math
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-10-06. Score: 4 | Accepted answer
  
  **Maybe.**
  
  AI has a long history of encountering mathematical impossibilities and then working around them already. While the individuals who solved these problems don't get as much press as Newton, Einstein, or Hawking, a case could be made that their contributions to human knowledge are on a similar scale. Unfortunately, their results don't relate to physical systems, so they can be harder to explain to the layperson.
  
  Something to keep in mind is that your question assumes the correctness of the "[Great Man Theory](https://en.wikipedia.org/wiki/Great_man_theory)" of science history, which holds that science advances by the efforts of exceptional people, and that we need to wait around for more such people to appear for science to advance. This view of scientific history is overly simplistic, and probably wrong. For example, most (all?) of Newton's discoveries were likely to have been made by someone else, around the same time, if he didn't make them (see, e.g. Leibnitz, who actually *did* discover calculus at the same time), so a better view might be of a large community of researchers who gradually develop more advanced models based on each others' work.
  
  To answer your question, I've listed out some past examples of problems that were overcome, and some outstanding problems that might require the development of new mathematical tools to solve properly. Keep in mind though, that we can't know for sure whether new tools are needed: maybe existing tools are sufficient, but no one has applied them in the right way yet!
  
  **Some past problems that plagued AI and required the development of better mathematical approaches**:
  
  1. The [combinatorial explosion](https://en.wikipedia.org/wiki/Combinatorial_explosion) problem appeared to preclude having an AI system reason about probabilities and causation in a logically correct way. This problem was solved by the development of [Bayesian networks](https://en.wikipedia.org/wiki/Bayesian_network) and causal networks, with the work being led by [Judea Pearl](https://en.wikipedia.org/wiki/Judea_Pearl) and his students. Pearl won a Turing award for this, but has received very little coverage in the popular press.
  2. Many optimization problems that AI systems need to solve are [NP-hard](https://en.wikipedia.org/wiki/NP-hardness). This means that no general purpose algorithms exist that can give exact solutions to these problems in a polynomial number of steps. Because of this, the problems were initially viewed as intractable. The development of [PTAS algorithms](https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme), and a deep understanding of [phase-changes](https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) in NP-Hard problems (pioneered by Cheeseman et al.) led to an ability to identify exactly what makes these problems hard, to identify which subparts cause the hardness, and to practical algorithms that solve all sorts of problems in these domains.
  3. Much effort in AI was spent designing new classification methods, and arguing about why one might or might not be better than another. The [No Free Lunch Theorems](http://www.no-free-lunch.org/), along with other work in computational learning theory provided a clear mathematical framework for understanding how systems can learn, and where their limits are.
  4. As a more recent example, games involving chance, like Poker, have state spaces so vast that they cannot be searched through effectively, even with heuristics. Phrasing these games in the language of Game Theory, and proving the convergence of the counter-factual minimax regret algorithm provided solutions. Bowling et al. were at the center of this work. It got some press coverage, but most of the coverage focused on "computers can play poker", and not the exiting, more generalizable, lessons AI researchers had learned in the process.
  
  **Some problems that are still outstanding, and might require new mathematical techniques:**
  
  1. Are there efficient algorithms for solving problems in the complexity classes PPAD, NP, or #P? Many AI problems fall into these categories. [We do not know the answer definitively](https://en.wikipedia.org/wiki/P_versus_NP_problem), and although most researchers suspect that no such algorithms exist, understanding *why not* seems like it could also provide major research advantages. Existing proof techniques do not seem likely to crack this problem.
  2. We have no good mathematical models of subjective experience. While some researchers (like [Churchland](https://en.wikipedia.org/wiki/Paul_Churchland)) think this is not likely to play a major role in the development of intelligent systems, a concrete model could either support or refute that view, and might provide solid frameworks for current problems in AI like the study of [motivation](http://www.cs.cornell.edu/~helou/IMRL.pdf).
  3. The original project of the social sciences was to provide mathematical models of individual humans, and then of human societies. This has mostly been abandoned (Psych is still at it, but Economics prefers to study rational agents instead of humans, and most of the others gave up mathematical modeling entirely to pursue the methodologies of the humanities instead of the sciences). Nonetheless, the lack of sound mathematical descriptions of human behaviours is becoming a major topic within AI, with work on norms, trust, emotion, and other topics. If a mathematical framework were developed to describe the actions of human societies or of individual humans, then AI would be advanced significantly (along with many other fields!).
  
  
  ---
  
  