What sort of mathematical problems are there in AI that people are working on?

Question

I recently got a 18-month postdoc position in a math department. It's a position with relative light teaching duty and a lot of freedom about what type of research that I want to do.

Previously I was mostly doing some research in probability and combinatorics. But I am thinking of doing a bit more application oriented work, e.g., AI. (There is also the consideration that there is good chance that I will not get a tenure-track position at the end my current position. Learn a bit of AI might be helpful for other career possibilities.)

What sort of mathematical problems are there in AI that people are working on? From what I heard of, there are people studying

• Deterministic Finite Automaton
• Multi-armed bandit problems
• Monte Carlo tree search
• Community detection

Any other examples?

Answer 1

In artificial intelligence (sometimes called machine intelligence or computational intelligence), there are several problems that are based on mathematical topics, especially optimization, statistics, probability theory, calculus and linear algebra.

Marcus Hutter has worked on a mathematical theory for artificial general intelligence, called AIXI, which is based on several mathematical and computation science concepts, such as reinforcement learning, probability theory (e.g. Bayes theorem and related topics) measure theory, algorithmic information theory (e.g. Kolmogorov complexity), optimisation, Solomonoff induction, universal Levin search and theory of compution (e.g. universal Turing machines). His book Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, which is a highly technical and mathematical book, describes his theory of optimal Bayesian non-Markov reinforcement learning agents. Here I list other similar works.

There is also the research field called computational learning theory, which is devoted to studying the design and analysis of machine learning algorithms (from a statistical perspective, known as statistical learning theory, or algorithmic perspective, algorithmic learning theory). More precisely, the field focuses on the rigorous study and mathematical analysis of machine learning algorithms using techniques from fields such as probability theory, statistics, optimization, information theory and geometry. Several people have worked on the computational learning theory, including Michael Kearns and Vladimir Vapnik.

There is also a lot of research effort dedicated to approximations (heuristics) of combinatorial optimization and NP-complete problems, such as ant colony optimization.

There is also some work on AI-completeness, but this has not received much attention (compared to the other research areas mentioned above).

Answer 2

Most of the math work being done in AI that I'm familiar with is already covered in nbro's answer. One thing that I do not believe is covered yet in that answer is proving algorithmic equivalence and/or deriving equivalent algorithms. One of my favourite papers on this is Learning to Predict Independent of Span by Hado van Hasselt and Richard Sutton.

The basic idea is that we may first formulate an algorithm (in math form, for instance some update rules/equations for parameters that we're training) in one way, and then find different update rules/equations (i.e. a different algorithm) for which we can prove that it is equivalent to the first one (i.e. always results in the same output).

A typical case where this is useful is if the first algorithm is easy to understand / appeals to our intuition / is more convenient for convergence proofs or other theoretical analysis, and the second algorithm is more efficient (in terms of computation, memory requirements, etc.).

Answer 3

Specifically for mathematical apparatus of Neural Networks - random matrix theory. Non-asymptotic random matrix theory was used in some proofs of convergence of gradient descent for Neural Networks, high dimensional random landscapes in connection to Hessian spectrum have relation to loss surfaces of Neural Networks.

Topological data analysis is another area of intense research related to ML, AI and applied to Neural Networks.

There were some works on Tropical Geometry of Neural Networks

Homotopy Type Theory also have connection to AI