Answers.Body: <p>@nbro has already provided a great answer, so i'll just supplement his answer with two specific results:</p>
  
  <p>Minsky, in his 1969 book <a href="https://en.wikipedia.org/wiki/Perceptrons_(book)" rel="nofollow noreferrer"><em>Perceptrons</em></a> provided a mathematical proof that showed that certain types of neural networks (then called perceptrons) weren't able to compute a function called the XOR function, thus showing that the mind couldn't be implemented on strictly this structure. Minsky further argued that this result would generalize to all neural networks, but he failed to account for an architectural adaptation known as "hidden layers", which would allow for neural networks to compute the XOR function. This result isn't very relavant in modern times, but the immediate impact of his proof lead to several decades of people ignoring neural networks due to their perceived failings.</p>
  
  <p>Another commonly cited result is the <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="nofollow noreferrer">Universal approximation theorem</a>, which shows that a sufficiently wide single layer neural network would be able to approximate (read as: arbitrarily close) any continuous function given appropriate activation function (iirc the activation needed to be non-linear). </p>
  
  <p>You can also consider the research of MIRI, which in a sense is more of a "pure" study of AI than the examples listed above. Their <a href="https://arxiv.org/abs/1401.5577" rel="nofollow noreferrer">Program Equilibrium via Provability Logic</a> result was pretty interesting, the gist of that paper is that programs can learn to cooperate in a very simple game if they read each other's source code.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-07T05:31:18.193Z
Answers.LastActivityDate: 2020-02-07T18:45:16.917Z
Answers.LastEditDate: 2020-02-07T18:45:16.917Z
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.Body: <p><strong>Computational learning theory</strong> (or just <strong>learning theory</strong>, abbreviated as CLT, COLT, or LT) is devoted to the mathematical and computational analysis of machine learning algorithms, so it is concerned with the learnability (i.e. generalization, bounds, efficiency, etc.) of certain tasks, given a learner (or a learning algorithm), a hypothesis space, data, etc.</p>
  <p>CLT can be divided into two subfields:</p>
  <ul>
  <li><a href="http://www.mit.edu/%7E6.454/www_spring_2001/emin/slt.pdf" rel="nofollow noreferrer">statistical learning theory</a> (SLT) and</li>
  <li><a href="https://seop.illc.uva.nl/entries/learning-formal" rel="nofollow noreferrer">algorithmic/formal learning theory</a> (ALT), which is the nonstatistical approach to CLT</li>
  </ul>
  <p>The most famous and studied SLT frameworks might be <a href="https://people.mpi-inf.mpg.de/%7Emehlhorn/SeminarEvolvability/ValiantLearnable.pdf" rel="nofollow noreferrer">PAC learning</a> and the <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory" rel="nofollow noreferrer">VC theory</a> (which extends PAC learning to infinite-dimensional hypothesis spaces).</p>
  <p>There are many good resources on CLT, some of which can be found in <a href="https://ai.stackexchange.com/a/20358/2444">this answer</a>.</p>
  <p>Here's a related question on this site: <a href="https://ai.stackexchange.com/q/12971/2444">What sort of mathematical problems are there in AI that people are working on?</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-04T19:41:43.880Z
Answers.LastActivityDate: 2022-01-16T22:30:57.327Z
Answers.LastEditDate: 2022-01-16T22:30:57.327Z
Answers.UserDisplayName: nbro
Body: <p>I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am interested in the question: Can we mathematically establish that a certain AI system has the ability to learn a task given some examples of how it should be done? 
  I would like to know what research has been done on this topic and also what mathematical tools could be helpful in answering such questions.</p>
  
Tags: <machine-learning><computational-learning-theory><math>
Title: Mathematical foundations of the ability to learn
UserDisplayName: Matheo
ThreadText: # Mathematical foundations of the ability to learn
  
  (Asked by: username_0 on 2020-02-04)
  
  I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am interested in the question: Can we mathematically establish that a certain AI system has the ability to learn a task given some examples of how it should be done?
  I would like to know what research has been done on this topic and also what mathematical tools could be helpful in answering such questions.
  
  **Tags:** machine-learning, computational-learning-theory, math
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-02-04. Score: 5 | Accepted answer
  
  **Computational learning theory** (or just **learning theory**, abbreviated as CLT, COLT, or LT) is devoted to the mathematical and computational analysis of machine learning algorithms, so it is concerned with the learnability (i.e. generalization, bounds, efficiency, etc.) of certain tasks, given a learner (or a learning algorithm), a hypothesis space, data, etc.
  
  CLT can be divided into two subfields:
  
  * [statistical learning theory](http://www.mit.edu/%7E6.454/www_spring_2001/emin/slt.pdf) (SLT) and
  * [algorithmic/formal learning theory](https://seop.illc.uva.nl/entries/learning-formal) (ALT), which is the nonstatistical approach to CLT
  
  The most famous and studied SLT frameworks might be [PAC learning](https://people.mpi-inf.mpg.de/%7Emehlhorn/SeminarEvolvability/ValiantLearnable.pdf) and the [VC theory](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory) (which extends PAC learning to infinite-dimensional hypothesis spaces).
  
  There are many good resources on CLT, some of which can be found in [this answer](https://ai.stackexchange.com/a/20358/2444).
  
  Here's a related question on this site: [What sort of mathematical problems are there in AI that people are working on?](https://ai.stackexchange.com/q/12971/2444).
  
  
  ---
  
  ### Answer by username_1 on 2020-02-07. Score: 1
  
  @nbro has already provided a great answer, so i'll just supplement his answer with two specific results:
  
  Minsky, in his 1969 book [*Perceptrons*](https://en.wikipedia.org/wiki/Perceptrons_(book)) provided a mathematical proof that showed that certain types of neural networks (then called perceptrons) weren't able to compute a function called the XOR function, thus showing that the mind couldn't be implemented on strictly this structure. Minsky further argued that this result would generalize to all neural networks, but he failed to account for an architectural adaptation known as "hidden layers", which would allow for neural networks to compute the XOR function. This result isn't very relavant in modern times, but the immediate impact of his proof lead to several decades of people ignoring neural networks due to their perceived failings.
  
  Another commonly cited result is the [Universal approximation theorem](https://en.wikipedia.org/wiki/Universal_approximation_theorem), which shows that a sufficiently wide single layer neural network would be able to approximate (read as: arbitrarily close) any continuous function given appropriate activation function (iirc the activation needed to be non-linear).
  
  You can also consider the research of MIRI, which in a sense is more of a "pure" study of AI than the examples listed above. Their [Program Equilibrium via Provability Logic](https://arxiv.org/abs/1401.5577) result was pretty interesting, the gist of that paper is that programs can learn to cooperate in a very simple game if they read each other's source code.
  
  
  ---
  
  