Are decision tree learning algorithms deterministic?

Are decision tree learning algorithms deterministic? Given a fixed dataset, do they always produce a tree with the same structure?

Is decision tree learning a deterministic algorithm?

Given a fixed dataset, does it always produce a tree of a same topology?

Generally, yes. Most decision tree learners, like the common ID3 and C4.5/C5.0 algorithms, are deterministic. At each step, the learners consider all possible feature that have not yet been used to split the data, and find the splits that maximize some function (e.g. information gain). There is no randomness (or pseudo-randomness) in this process.

The exceptions to this would be if you used randomness to break ties (rather than, say, using the index of each feature, as is common), but this would be an unusual modification.

Like the name suggests, random forests do make use of randomness, or at least, pseudo-randomness. Douglass expands on the distinction in his answer, but if we're only concerned about whether or not the algorithm is deterministic in the usual sense of the word (at least, within computer science), the answer is no.

If you start the same random forest learning algorithm, with the same datasets, at two different times (or, using two different seeds for your pseudorandom number generator), you will get two different forests. This is because the algorithm selects random subsets of the features and/or datapoints to learn on, and, if different seeds are used, the subsets will be different each time.

What makes a system deterministic is not the objective of the algorithm or the variability of the data set or lack thereof. It is not the system's academic origin or the label we assign to it or even whether it is predictable that drives whether it is deterministic. A system is deterministic if, given perfectly accurate and comprehensive knowledge of the initial state and an arbitrarily large set of computing resources that any future state can be determined from known rules of causality governing the system.

In the case of decision tree learning or random forests, the academic origins do not inject truly random noise. Digital systems, including pseudo random number generators with hard coded seeds, are always deterministic. Pseudo random number generators using a timestamp in nanoseconds as a seed can be used to fake a stochastic process. However, if the timestamp was known, shows itself to be deterministic at its core because it is repeatable down to the last binary bit of results. So the general answer to the question is yes. They are most often deterministic.

This does not exclude the possibility of a truly random input as a seed or a random number generator driven by an imaging chip in a mobile device or a Brownian motion or quantum motion detector in the hardware.

If those truly stochastic sources of what information theory calls entropy and systems engineers call noise are used in the algorithm for whatever reason, usually to improve search success probabilities, then those algorithms would then be non-deterministic. Regardless of the comprehensiveness of knowledge of initial state and the time and resources for computing the results, the system would theoretically never be expected to repeat the same behavior. If it did, it would do so at upon an instance of operation about which we would have zero bits of information.

• ID3, which infers a decision tree from data, is an example of a deterministic algorithm. It will always end up with the same decision tree given the same training data. – Oliver Mason Apr 1 '19 at 16:09
• I wasn't criticising, just giving an example for a deterministic decision tree algorithm. – Oliver Mason Apr 3 '19 at 8:13