Answers.Body: <p>In some cases, you can solve a <strong>linear regression</strong> problem with an analytical (or closed-form) solution/expression (although this may not always be the best approach). See <a href="https://ai.stackexchange.com/a/28488/2444">this answer</a> for more details.</p>
  <p>Note that this solution involves matrix multiplications and the computation of an inverse with floating-point numbers, so this is still a numerical algorithm/problem. We could also consider this solution an iterative algorithm if, under the hood, you compute the inverse of the matrix or <a href="https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm" rel="nofollow noreferrer">perform the matrix multiplications with iterative algorithms</a>, but, from a high-level perspective, this is an analytical (non-iterative) method.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T22:55:01.090Z
Answers.Text: [This article](https://machinelearningmastery.com/analytical-vs-numerical-solutions-in-machine-learning/) could also be useful, where the author notices that, for example, performing one-hot encoding is an analytical operation, although this operation is just part of the solution to an ML problem.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T13:26:41.053Z
Answers.LastActivityDate: 2021-08-19T13:26:41.053Z
Answers.UserDisplayName: nbro
Answers.Body: <h2>Honourable mention: Memory-based approaches</h2>
  <p>Although not analytic, memory-based models, such as <a href="https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm" rel="nofollow noreferrer">k-nearest neighbours (k-NN)</a> are very lightweight when learning, but have a higher cost to use the stored knowledge.</p>
  <p>Even though a k-NN model is slow to make inferences, the computation involved is not complex or iterative. It makes a single pass through all the data, keeping only the k closest examples to the example that it is predicting the output for, and then performs a simple aggregate function (e.g. a weighted mean) on that list of k closest matches.</p>
  <h2>Knowledgebases and Inference Engines</h2>
  <p>A logic-based system can be considered a learning system if it is able to accept new statements. This might be at runtime, or you could consider the training process to be the addition of new logical rules into a long-term storage. Either way, the system learns by adding new rules, not by observing anything directly, or by consuming input/output pairs. Adaptors could in theory be written using other AI approaches to feed the knowledgebase though.</p>
  <p>This is a classic use for the LISP programming language. For example, you could build an <a href="https://en.wikipedia.org/wiki/Inference_engine" rel="nofollow noreferrer">inference engine</a> and teach it facts as LISP statements. Every time you added a fact, the engine would be able to infer more about the domain it was working with. In some ways this resembles the k-NN approach, in that all facts are stored, and the inference stage is more computationally expensive.</p>
  <p>The main issue with learning systems based on predicate logic is that they brittle and cannot deal with uncertainty easily. The approaches used to patch that include coding how uncertainty works as a set of facts (<a href="https://en.wikipedia.org/wiki/Cyc" rel="nofollow noreferrer">see CYC</a>), or starting with some form of <a href="https://en.wikipedia.org/wiki/Fuzzy_logic" rel="nofollow noreferrer">fuzzy logic</a> as a core part of the system.</p>
  <p>You would not use it to process audio or image inputs, at least not directly. However, there are some advantages for things like explainable AI - an inference engine can always explain how it came up with an answer, step by step.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T13:10:35.520Z
Answers.Text: I only very quickly read some parts of this answer, but it seems to me that you don't mention linear regression and its [closed-form solution](https://ai.stackexchange.com/a/28488/2444). You may want to do that, otherwise, I may provide an answer with that example.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T13:15:12.527Z
Answers.Text: @nbro: I could, as yet another "honourable mention" IMO, as that is often still fairly heavy numerical computing, with iteration too, just not using gradients. Beyond some scale (e.g. 50,000 examples or more), you are better off using gradient descent. It does however match "analytical" in one sense.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T13:18:01.287Z
Answers.Text: Yes, it's true that closed-form solution is numerical because you need to perform matrix multiplications and compute inverses that involve floating-point numbers. However, iterative means that you need to perform multiple iterations of some update rule to get to the answer, which is not (usually) the case with this closed-form solution, and the OP seemed to be interested in analytical expressions.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-09T13:24:05.417Z
Answers.Text: @NeilSlater Sorry for the comment on an old answer, but could you expand on your statement that "adaptors could in theory be written using other AI approaches to feed the knowledgebase"? Are you referring to, say, a neural net somehow being used as a component of a logic-based system? This is an intriguing idea but I'm having trouble visualizing how it would look in practice.
Answers.UserDisplayName: xojfqa
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-09T20:12:07.903Z
Answers.Text: @xojfqa: I'm not entirely sure myself, but it may be feasible to have data set input, and output of a rule to add to a ruleset. Decision tree learners do similar to this when expanding a tree.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-18T11:33:20.303Z
Answers.LastActivityDate: 2021-08-18T11:33:20.303Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>In addition to the other answers, I would like to mention that there is a branch in Deep Learning community, that tries to get an intuition on the general problem via solving some simpler problems.</p>
  <p>The main complication with working with real-world data is that it doesn't possess a simple analytical description. Data from ImageNet or MNIST belongs to a complicated distribution on nontrivial manifolds, that is rather different from the Gaussian or any other common distribution.</p>
  <p>Deep Neural networks are complicated nonlinear functions of data and the model weights, hence in general one is not expected to get a closed-form solution.</p>
  <p>However, there are limits, when the dynamics simplifies a lot.</p>
  <p><strong>Mean field regime</strong></p>
  <p>For the case of a single hidden layer and an infinite number of hidden units, one switches from the dynamics of particular weight to the dynamics of the weight distribution. In addition let the learning rate <span class="math-container">$\eta \rightarrow 0$</span>.</p>
  <p>Discrete optimization is replaced by the continuous evolution of PDE. An example of such treatment is given here:</p>
  <p><a href="https://www.pnas.org/content/pnas/115/33/E7665.full.pdf" rel="nofollow noreferrer">https://www.pnas.org/content/pnas/115/33/E7665.full.pdf</a></p>
  <p><strong>NTK regime</strong></p>
  <p>For infinitely wide networks with specific parametrization <a href="https://arxiv.org/abs/1806.07572" rel="nofollow noreferrer">https://arxiv.org/abs/1806.07572</a> - evolution of the model output is given by a particular differential equation with fixed kernel.</p>
  <p>An example of estimating convergence with NTK approach of the loss function, depending on the smoothness of target function, is given in the paper:</p>
  <p><a href="https://arxiv.org/abs/2105.00507" rel="nofollow noreferrer">https://arxiv.org/abs/2105.00507</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T15:24:53.653Z
Answers.LastActivityDate: 2021-08-19T15:24:53.653Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>Most of the algorithms in machine learning I am aware of use datasets and learning happens in an iterative manner given some examples. The examples can also be understood as experience in the case of reinforcement learning.</p>
  <p>Consider the following from <a href="https://www.deeplearningbook.org/contents/numerical.html" rel="nofollow noreferrer">Numerical Computation chapter of Deep Learning book</a></p>
  <blockquote>
  <p>Machine learning algorithms usually require a high amount of numerical computation. <strong>This typically refers to algorithms that solve mathematical problems by methods that update estimates of the solution via an iterative process, rather than analytically deriving a formula to provide a symbolic expression for the correct solution.</strong> Common operations include optimization (ﬁnding the value of an argument that minimizes or maximizes a function) and solving systems of linear equations. Even just evaluating a mathematical function on a digital computer can be diﬃcult when the function involves real numbers, which cannot be represented precisely using a ﬁnite amount of memory.</p>
  </blockquote>
  <p>I am wondering whether there is any domain in machine learning that deals with solving the problem analytically rather than computationally heavy iterative algorithms?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-17T04:20:24.073Z
Comments.Text: Casual modeling?
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-17T06:22:17.653Z
Comments.Text: @DavidGibson Is it based on analytical formulae only?
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-17T23:17:34.417Z
Comments.Text: @NeilSlater Since they used the words "typically" and "ususally", which gives a chance to think in other scope.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-18T05:33:19.953Z
Comments.Text: Hello, for those who down-voted: please try to comment, if possible, about the reason for down-vote. Whether it is about the quality of the question or presentation or language or scope of the question etc., It will be beneficial for me as well as for the site.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-18T09:18:53.937Z
Comments.Text: @hanugm: So your question **is** specifically about existence of analytical machine learning approaches? And therefore not about analytical AI used for any purposes other than learning?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-18T09:21:11.660Z
Comments.Text: @NeilSlater Yeah. True....
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-18T09:27:54.170Z
Comments.Text: OK, that was not clear to me initially. I think the text "solving the problem" was misdirecting me. It is sometimes possible to solve problems where ML is applied other than using a learning approach. But by "solving the problem" I think you mean "the problem of learning", and not whatever motivated using ML in the first place? That is subtly different
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-18T10:51:49.853Z
Comments.Text: @NeilSlater Oh. No issue... I am a beginner in framing phrases... So, excuse... :P :)
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-20T22:19:08.487Z
Comments.Text: You should remember that (nearly) all learning systems are based on a loss function, calculated analytically.
Comments.UserDisplayName: Hermes Morales
Tags: <machine-learning><math><linear-regression><numerical-algorithms>
Title: Is there any domain in machine learning that solves a problem by using only analytical algorithms?
UserDisplayName: hanugm
ThreadText: # Is there any domain in machine learning that solves a problem by using only analytical algorithms?
  
  (Asked by: username_0 on 2021-08-16)
  
  Most of the algorithms in machine learning I am aware of use datasets and learning happens in an iterative manner given some examples. The examples can also be understood as experience in the case of reinforcement learning.
  
  Consider the following from [Numerical Computation chapter of Deep Learning book](https://www.deeplearningbook.org/contents/numerical.html)
  
  > Machine learning algorithms usually require a high amount of numerical computation. **This typically refers to algorithms that solve mathematical problems by methods that update estimates of the solution via an iterative process, rather than analytically deriving a formula to provide a symbolic expression for the correct solution.** Common operations include optimization (ﬁnding the value of an argument that minimizes or maximizes a function) and solving systems of linear equations. Even just evaluating a mathematical function on a digital computer can be diﬃcult when the function involves real numbers, which cannot be represented precisely using a ﬁnite amount of memory.
  
  I am wondering whether there is any domain in machine learning that deals with solving the problem analytically rather than computationally heavy iterative algorithms?
  
  **Tags:** machine-learning, math, linear-regression, numerical-algorithms
  
  > **Comments:**
  > **username_1**: Casual modeling?  
  > **username_0**: @DavidGibson Is it based on analytical formulae only?  
  > **username_0**: @username_2 Since they used the words "typically" and "ususally", which gives a chance to think in other scope.  
  > **username_0**: Hello, for those who down-voted: please try to comment, if possible, about the reason for down-vote. Whether it is about the quality of the question or presentation or language or scope of the question etc., It will be beneficial for me as well as for the site.  
  > **username_2**: @username_0: So your question **is** specifically about existence of analytical machine learning approaches? And therefore not about analytical AI used for any purposes other than learning?  
  > **username_0**: @username_2 Yeah. True....  
  > **username_2**: OK, that was not clear to me initially. I think the text "solving the problem" was misdirecting me. It is sometimes possible to solve problems where ML is applied other than using a learning approach. But by "solving the problem" I think you mean "the problem of learning", and not whatever motivated using ML in the first place? That is subtly different  
  > **username_0**: @username_2 Oh. No issue... I am a beginner in framing phrases... So, excuse... :P :)  
  > **username_3**: You should remember that (nearly) all learning systems are based on a loss function, calculated analytically.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2021-08-19. Score: 2
  
  In some cases, you can solve a **linear regression** problem with an analytical (or closed-form) solution/expression (although this may not always be the best approach). See [this answer](https://ai.stackexchange.com/a/28488/2444) for more details.
  
  Note that this solution involves matrix multiplications and the computation of an inverse with floating-point numbers, so this is still a numerical algorithm/problem. We could also consider this solution an iterative algorithm if, under the hood, you compute the inverse of the matrix or [perform the matrix multiplications with iterative algorithms](https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm), but, from a high-level perspective, this is an analytical (non-iterative) method.
  
  > **Comments:**
  > **username_4**: [This article](https://machinelearningmastery.com/analytical-vs-numerical-solutions-in-machine-learning/) could also be useful, where the author notices that, for example, performing one-hot encoding is an analytical operation, although this operation is just part of the solution to an ML problem.  
  
  ---
  
  ### Answer by username_2 on 2021-08-18. Score: 1
  
  ## Honourable mention: Memory-based approaches
  
  Although not analytic, memory-based models, such as [k-nearest neighbours (k-NN)](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) are very lightweight when learning, but have a higher cost to use the stored knowledge.
  
  Even though a k-NN model is slow to make inferences, the computation involved is not complex or iterative. It makes a single pass through all the data, keeping only the k closest examples to the example that it is predicting the output for, and then performs a simple aggregate function (e.g. a weighted mean) on that list of k closest matches.
  
  ## Knowledgebases and Inference Engines
  
  A logic-based system can be considered a learning system if it is able to accept new statements. This might be at runtime, or you could consider the training process to be the addition of new logical rules into a long-term storage. Either way, the system learns by adding new rules, not by observing anything directly, or by consuming input/output pairs. Adaptors could in theory be written using other AI approaches to feed the knowledgebase though.
  
  This is a classic use for the LISP programming language. For example, you could build an [inference engine](https://en.wikipedia.org/wiki/Inference_engine) and teach it facts as LISP statements. Every time you added a fact, the engine would be able to infer more about the domain it was working with. In some ways this resembles the k-NN approach, in that all facts are stored, and the inference stage is more computationally expensive.
  
  The main issue with learning systems based on predicate logic is that they brittle and cannot deal with uncertainty easily. The approaches used to patch that include coding how uncertainty works as a set of facts ([see CYC](https://en.wikipedia.org/wiki/Cyc)), or starting with some form of [fuzzy logic](https://en.wikipedia.org/wiki/Fuzzy_logic) as a core part of the system.
  
  You would not use it to process audio or image inputs, at least not directly. However, there are some advantages for things like explainable AI - an inference engine can always explain how it came up with an answer, step by step.
  
  > **Comments:**
  > **username_4**: I only very quickly read some parts of this answer, but it seems to me that you don't mention linear regression and its [closed-form solution](https://ai.stackexchange.com/a/28488/2444). You may want to do that, otherwise, I may provide an answer with that example.  
  > **username_2**: @username_4: I could, as yet another "honourable mention" IMO, as that is often still fairly heavy numerical computing, with iteration too, just not using gradients. Beyond some scale (e.g. 50,000 examples or more), you are better off using gradient descent. It does however match "analytical" in one sense.  
  > **username_4**: Yes, it's true that closed-form solution is numerical because you need to perform matrix multiplications and compute inverses that involve floating-point numbers. However, iterative means that you need to perform multiple iterations of some update rule to get to the answer, which is not (usually) the case with this closed-form solution, and the OP seemed to be interested in analytical expressions.  
  > **username_5**: @username_2 Sorry for the comment on an old answer, but could you expand on your statement that "adaptors could in theory be written using other AI approaches to feed the knowledgebase"? Are you referring to, say, a neural net somehow being used as a component of a logic-based system? This is an intriguing idea but I'm having trouble visualizing how it would look in practice.  
  > **username_2**: @username_5: I'm not entirely sure myself, but it may be feasible to have data set input, and output of a rule to add to a ruleset. Decision tree learners do similar to this when expanding a tree.  
  
  ---
  
  ### Answer by username_6 on 2021-08-19. Score: 0
  
  In addition to the other answers, I would like to mention that there is a branch in Deep Learning community, that tries to get an intuition on the general problem via solving some simpler problems.
  
  The main complication with working with real-world data is that it doesn't possess a simple analytical description. Data from ImageNet or MNIST belongs to a complicated distribution on nontrivial manifolds, that is rather different from the Gaussian or any other common distribution.
  
  Deep Neural networks are complicated nonlinear functions of data and the model weights, hence in general one is not expected to get a closed-form solution.
  
  However, there are limits, when the dynamics simplifies a lot.
  
  **Mean field regime**
  
  For the case of a single hidden layer and an infinite number of hidden units, one switches from the dynamics of particular weight to the dynamics of the weight distribution. In addition let the learning rate $\eta \rightarrow 0$.
  
  Discrete optimization is replaced by the continuous evolution of PDE. An example of such treatment is given here:
  
  <https://www.pnas.org/content/pnas/115/33/E7665.full.pdf>
  
  **NTK regime**
  
  For infinitely wide networks with specific parametrization <https://arxiv.org/abs/1806.07572> - evolution of the model output is given by a particular differential equation with fixed kernel.
  
  An example of estimating convergence with NTK approach of the loss function, depending on the smoothness of target function, is given in the paper:
  
  <https://arxiv.org/abs/2105.00507>
  
  
  ---
  
  