2
$\begingroup$

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

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 (finding 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 difficult when the function involves real numbers, which cannot be represented precisely using a finite 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?

$\endgroup$
9
  • $\begingroup$ Casual modeling? $\endgroup$ Aug 17 at 4:20
  • $\begingroup$ @DavidGibson Is it based on analytical formulae only? $\endgroup$
    – hanugm
    Aug 17 at 6:22
  • $\begingroup$ @NeilSlater Since they used the words "typically" and "ususally", which gives a chance to think in other scope. $\endgroup$
    – hanugm
    Aug 17 at 23:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – hanugm
    Aug 18 at 5:33
  • $\begingroup$ @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? $\endgroup$ Aug 18 at 9:18
2
$\begingroup$

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 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, but, from a high-level perspective, this is an analytical (non-iterative) method.

$\endgroup$
1
  • 1
    $\begingroup$ This article 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. $\endgroup$
    – nbro
    Aug 19 at 22:55
1
$\begingroup$

Honourable mention: Memory-based approaches

Although not analytic, memory-based models, such as k-nearest neighbours (k-NN) 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 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), or starting with some form of 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.

$\endgroup$
3
  • $\begingroup$ 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. You may want to do that, otherwise, I may provide an answer with that example. $\endgroup$
    – nbro
    Aug 19 at 13:10
  • $\begingroup$ @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. $\endgroup$ Aug 19 at 13:15
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Aug 19 at 13:18
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.