How broad is the meaning of "algorithm"?

This is a purely terminological question.

The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative statements giving roughly the same idea.

But for some computer systems, such as neural networks, it is somewhat stretching it (for me) to say that they are "algorithms". e.g. neural networks are very "approximate" compared to traditional software algorithms.

• Would people in general say that a particular neural network with a particular parameterization (i.e. not the learning algorithm, but the resulting neural net itself) is an "algorithm")?

• If not, what other word is there to refer to the more general class that contains such networks as well?

• Neural networks aren't "approximate" in themselves. We use it for approximation. Also, One of my teacher gave an (additional, not exclusive) definition of "algorithm" as "something that can be computed by a Turing machine". Jan 14, 2019 at 17:53
• @GBat: "something that can be computed by a Turing machine" is a computable function, not an algorithm. Jan 14, 2019 at 18:17

No. A specific neural network is just the (weights) parameters of an algorithm for function approximation.

A neural network in general yes, is the algorithm for classifying a given x into a class, given a probabilistic distribution (weights).

This is like asking weather a specific VAT rate is an algorithm. The calculation of VAT is an algorithm but the VAT rate is not.

• @GBat, do you agree with this? Jan 17, 2019 at 6:11
• I don't know how you mean that a "neural network in general" is an algorithm any more than a "specific neural network is". The particular parameters of a network don't change it's algorithmic-ness. You seem to be saying that there does exist an algorithm for doing classification with neural networks, but this point about general vs specific networks is confusing. Feb 15, 2019 at 21:46

A neural network itself is more of a data structure than an algorithm; it has a set of numbers and functions and specific connections between them, similar to a graph. You could define algorithms which use a neural network such as: do a convolution on my image using the first layer of weights, then apply the first non-linearity, then ..., then return the class with the largest softmax probability as the class of this image. That's an algorithm for classifying an input with a given neural network. There are other algorithms that use neural networks too like those for learning their weights, using them to play games, etc. These are sometimes randomized algorithms (due to randomness in the initialization of the weights and in permuting the training data, as well as often random augmentations of the training data). Graphs, similarly, have many associated algorithms (finding paths, minimum cuts, etc.).

As you said, I'd think of an algorithm as a set of steps or instructions for completing some task. Generally when we think of algorithms, that task is well-specified: given a list of numbers, I want to output them in order from smallest to largest. Then we can construct algorithms for which we provide guarantees (proofs) that they will always complete this task. We can also give proofs showing, e.g., how long our algorithms will take (asymptotically) for an input of a given size.

When you think about the algorithm which takes as inputs a neural network and an input to the network and outputs a label for the input, the steps themselves are well-defined, but the task might be trickier to define. You might like to say, I want an algorithm which will provably always give me the correct label, just like my sorting algorithm always orders my lists properly. There has been a lot of research recently about how well the algorithms used to train neural networks converge to weights which minimize the training loss, but you have to start making some assumptions if you want to say something about how well using a prediction algorithm with the network generalizes to datapoints never seen in training. Generally, we can't say that using a given neural network gives any specific approximation-factor to an optimal algorithm.

So, I would say that there is an algorithm for making predictions using a neural network, but the only thing I can be sure of about the task that algorithm is accomplishing is that, e.g., if I'm doing a $$k$$-way classification, the result I get will be one of the $$k$$ classes (or, for regression, the output will be some real number).