Mathematical foundations of the ability to learn

Question

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.

Answer 1

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 (SLT) and
• algorithmic/formal learning theory (ALT), which is the nonstatistical approach to CLT

The most famous and studied SLT frameworks might be PAC learning and the VC 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.

Here's a related question on this site: What sort of mathematical problems are there in AI that people are working on?.

Answer 2

@nbro has already provided a great answer, so i'll just supplement his answer with two specific results:

Minsky, in his 1969 book Perceptrons 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, 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 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.