Is there any domain in machine learning that solves a problem by using only analytical algorithms?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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