Answers.Body: <p>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 <strong>proving algorithmic equivalence</strong> and/or <strong>deriving equivalent algorithms</strong>. One of my favourite papers on this is <a href="https://arxiv.org/abs/1508.04582" rel="noreferrer">Learning to Predict Independent of Span</a> by Hado van Hasselt and Richard Sutton.</p>
  
  <p>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). </p>
  
  <p>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.).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-21T15:27:52.157Z
Answers.LastActivityDate: 2019-06-21T15:27:52.157Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>Specifically for mathematical apparatus of Neural Networks - <a href="https://en.wikipedia.org/wiki/Random_matrix" rel="nofollow noreferrer">random matrix theory</a>.  <a href="https://arxiv.org/abs/1011.3027" rel="nofollow noreferrer">Non-asymptotic random matrix theory</a> was used in some <a href="https://arxiv.org/abs/1811.08888" rel="nofollow noreferrer">proofs of convergence of gradient descent for Neural Networks</a>, <a href="https://arxiv.org/abs/1806.05294" rel="nofollow noreferrer">high dimensional random landscapes</a> in connection to Hessian spectrum have relation to <a href="https://arxiv.org/abs/1412.0233" rel="nofollow noreferrer">loss surfaces of Neural Networks</a>.</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Topological_data_analysis" rel="nofollow noreferrer">Topological data analysis</a> is another area of intense research related to ML, AI and <a href="https://arxiv.org/abs/1905.12200" rel="nofollow noreferrer">applied to Neural Networks</a>.</p>
  
  <p>There were some works on <a href="https://arxiv.org/abs/1805.07091" rel="nofollow noreferrer">Tropical Geometry of Neural Networks</a></p>
  
  <p><a href="https://en.wikipedia.org/wiki/Homotopy_type_theory" rel="nofollow noreferrer">Homotopy Type Theory</a> also have <a href="https://andrewnetwork.github.io/minor/math/2017/07/29/hotti.html" rel="nofollow noreferrer">connection to AI</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-22T07:44:55.943Z
Answers.LastActivityDate: 2019-06-22T07:44:55.943Z
Answers.UserDisplayName: mirror2image
Answers.Body: <p>In <em>artificial intelligence</em> (sometimes called <em>machine intelligence</em> or <em>computational intelligence</em>), there are several problems that are based on mathematical topics, especially optimization, statistics, probability theory, calculus and linear algebra.</p>
  <p><a href="http://www.hutter1.net/" rel="nofollow noreferrer">Marcus Hutter</a> has worked on a mathematical theory for <em>artificial general intelligence</em>, called <a href="https://jan.leike.name/AIXI.html" rel="nofollow noreferrer"><strong>AIXI</strong></a>, which is based on several mathematical and computation science concepts, such as reinforcement learning, probability theory (e.g. Bayes theorem and related topics) <a href="http://mathworld.wolfram.com/MeasureTheory.html" rel="nofollow noreferrer">measure theory</a>, <a href="http://www.scholarpedia.org/article/Algorithmic_information_theory" rel="nofollow noreferrer">algorithmic information theory</a> (e.g. Kolmogorov complexity), optimisation, <a href="https://wiki.lesswrong.com/wiki/Solomonoff_induction" rel="nofollow noreferrer">Solomonoff induction</a>, <a href="http://www.scholarpedia.org/article/Universal_search" rel="nofollow noreferrer">universal Levin search</a> and <a href="https://en.wikipedia.org/wiki/Theory_of_computation" rel="nofollow noreferrer">theory of compution</a> (e.g. universal Turing machines). His book <a href="http://lib.slon.pp.ru/ComputerScience/Sequential%20Decisions%20Based%20On%20Algorithmic%20Probability.pdf" rel="nofollow noreferrer">Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability</a>, which is a highly technical and mathematical book, describes his theory of optimal Bayesian non-Markov reinforcement learning agents. <a href="https://ai.stackexchange.com/q/21427/2444">Here</a> I list other similar works.</p>
  <p>There is also the research field called <a href="http://www.learningtheory.org/" rel="nofollow noreferrer"><strong>computational learning theory</strong></a>, which is devoted to studying the design and analysis of machine learning algorithms (from a statistical perspective, known as <a href="https://www.math.arizona.edu/%7Ehzhang/math574m/Read/vapnik.pdf" rel="nofollow noreferrer"><em>statistical learning theory</em></a>, or algorithmic perspective, <em>algorithmic learning theory</em>). 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 <a href="https://ai.stackexchange.com/q/20355/2444">computational learning theory</a>, including Michael Kearns and <a href="https://en.wikipedia.org/wiki/Vladimir_Vapnik" rel="nofollow noreferrer">Vladimir Vapnik</a>.</p>
  <p>There is also a lot of research effort dedicated to approximations (heuristics) of <a href="https://en.wikipedia.org/wiki/Combinatorial_optimization" rel="nofollow noreferrer">combinatorial optimization</a> and <a href="https://en.wikipedia.org/wiki/NP-completeness" rel="nofollow noreferrer">NP-complete</a> problems, such as <a href="http://www.scholarpedia.org/article/Ant_colony_optimization" rel="nofollow noreferrer">ant colony optimization</a>.</p>
  <p>There is also some work on <a href="https://en.wikipedia.org/wiki/AI-complete" rel="nofollow noreferrer">AI-completeness</a>, but this has not received much attention (compared to the other research areas mentioned above).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-21T14:48:44.113Z
Answers.LastActivityDate: 2021-01-31T13:40:45.927Z
Answers.LastEditDate: 2021-01-31T13:40:45.927Z
Answers.UserDisplayName: nbro
Body: <p>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.</p>
  
  <p>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.)</p>
  
  <p>What sort of <strong>mathematical problems</strong> are there in AI that people are working on? From what I heard of, there are people studying</p>
  
  <ul>
  <li><a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton" rel="noreferrer">Deterministic Finite Automaton</a></li>
  <li><a href="https://en.wikipedia.org/wiki/Multi-armed_bandit" rel="noreferrer">Multi-armed bandit problems</a></li>
  <li><a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="noreferrer">Monte Carlo tree search</a></li>
  <li><a href="https://en.wikipedia.org/wiki/Community_structure" rel="noreferrer">Community detection</a></li>
  </ul>
  
  <p>Any other examples?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-21T11:47:19.607Z
Comments.Text: Optimization. Probably is the most impactful field to AI ML.  Proof of convergence, like in reinforcement learning, is lacking.
Comments.UserDisplayName: drerD
Tags: <research><math>
Title: What sort of mathematical problems are there in AI that people are working on?
UserDisplayName: LeafGlowPath
ThreadText: # What sort of mathematical problems are there in AI that people are working on?
  
  (Asked by: username_0 on 2019-06-21)
  
  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](https://en.wikipedia.org/wiki/Deterministic_finite_automaton)
  * [Multi-armed bandit problems](https://en.wikipedia.org/wiki/Multi-armed_bandit)
  * [Monte Carlo tree search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)
  * [Community detection](https://en.wikipedia.org/wiki/Community_structure)
  
  Any other examples?
  
  **Tags:** research, math
  > **Comments:**
  > **username_1**: Optimization. Probably is the most impactful field to AI ML.  Proof of convergence, like in reinforcement learning, is lacking.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2019-06-21. Score: 14 | Accepted answer
  
  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](http://www.hutter1.net/) has worked on a mathematical theory for *artificial general intelligence*, called [**AIXI**](https://jan.leike.name/AIXI.html), 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](http://mathworld.wolfram.com/MeasureTheory.html), [algorithmic information theory](http://www.scholarpedia.org/article/Algorithmic_information_theory) (e.g. Kolmogorov complexity), optimisation, [Solomonoff induction](https://wiki.lesswrong.com/wiki/Solomonoff_induction), [universal Levin search](http://www.scholarpedia.org/article/Universal_search) and [theory of compution](https://en.wikipedia.org/wiki/Theory_of_computation) (e.g. universal Turing machines). His book [Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability](http://lib.slon.pp.ru/ComputerScience/Sequential%20Decisions%20Based%20On%20Algorithmic%20Probability.pdf), which is a highly technical and mathematical book, describes his theory of optimal Bayesian non-Markov reinforcement learning agents. [Here](https://ai.stackexchange.com/q/21427/2444) I list other similar works.
  
  There is also the research field called [**computational learning theory**](http://www.learningtheory.org/), which is devoted to studying the design and analysis of machine learning algorithms (from a statistical perspective, known as [*statistical learning theory*](https://www.math.arizona.edu/%7Ehzhang/math574m/Read/vapnik.pdf), 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](https://ai.stackexchange.com/q/20355/2444), including Michael Kearns and [Vladimir Vapnik](https://en.wikipedia.org/wiki/Vladimir_Vapnik).
  
  There is also a lot of research effort dedicated to approximations (heuristics) of [combinatorial optimization](https://en.wikipedia.org/wiki/Combinatorial_optimization) and [NP-complete](https://en.wikipedia.org/wiki/NP-completeness) problems, such as [ant colony optimization](http://www.scholarpedia.org/article/Ant_colony_optimization).
  
  There is also some work on [AI-completeness](https://en.wikipedia.org/wiki/AI-complete), but this has not received much attention (compared to the other research areas mentioned above).
  
  
  ---
  
  ### Answer by username_2 on 2019-06-21. Score: 5
  
  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](https://arxiv.org/abs/1508.04582) 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 by username_3 on 2019-06-22. Score: 3
  
  Specifically for mathematical apparatus of Neural Networks - [random matrix theory](https://en.wikipedia.org/wiki/Random_matrix). [Non-asymptotic random matrix theory](https://arxiv.org/abs/1011.3027) was used in some [proofs of convergence of gradient descent for Neural Networks](https://arxiv.org/abs/1811.08888), [high dimensional random landscapes](https://arxiv.org/abs/1806.05294) in connection to Hessian spectrum have relation to [loss surfaces of Neural Networks](https://arxiv.org/abs/1412.0233).
  
  [Topological data analysis](https://en.wikipedia.org/wiki/Topological_data_analysis) is another area of intense research related to ML, AI and [applied to Neural Networks](https://arxiv.org/abs/1905.12200).
  
  There were some works on [Tropical Geometry of Neural Networks](https://arxiv.org/abs/1805.07091)
  
  [Homotopy Type Theory](https://en.wikipedia.org/wiki/Homotopy_type_theory) also have [connection to AI](https://andrewnetwork.github.io/minor/math/2017/07/29/hotti.html)
  
  
  ---
  
  