Fast-and-frugal trees

Recall that the basic elements for making a binary classification are the cues, which are here assumed to be binary. In a fast-and-frugal tree, the cues are ranked, with one cue at each level of the tree and an exit node at each level (except for two exit nodes for the last cue at the last level of the tree). Whenever a cue is used, a question is asked about the value of the cue. The answers to the questions might immediately lead to an exit, or they might lead to a further question (and eventually to an exit). A characteristic property of fast-and-frugal trees is that, for each question, there is at least one possible answer that leads to an exit.

In the literature on fast-and-frugal trees, many different algorithms have been proposed [2]^{[MKW] [LSG]}[4] for (1) ordering cues and (2) deciding which possible answer to a question about a cue leads immediately to an exit. Note that if (1) and (2) are done, a fast-and-frugal tree is fully defined. Often, in order to keep construction simple and intuitive, the algorithms use (1) simple measures of cue "goodness" (e.g., correlation between cue and category, considering each cue independently of the other cues) and (2) make simple choices about exits (e.g., decide on each exit independently of the other exits), but more complex algorithms have been proposed as well.

To use a fast-and-frugal tree, begin at the root and check one cue at a time. At each step, one of the possible outcomes is an exit node which allows for a decision (or action) -- if an exit is reached, stop; otherwise, continue until an exit is reached. you take an exit, stop; otherwise, continue and ask more questions until an exit is reached.

Figure 1. A fast-and-frugal tree that helps emergency room doctors decide whether to send a patient to a regular nursing bed or the coronary care unit (Green & Mehr, 1997) ^[GM].

Figure 1 illustrates a fast-and-frugal tree for classifying a patient as “high risk” of having a heart stroke and thus having to be sent to the “coronary care unit” or as "low risk” and thus having to be sent to a “regular nursing bed" ^[GM] (Green& Mehr, 1997).

Consider three patients, John, Mary, and Jack:

• John has ST segment changes thus is classified as "high risk" and sent to the coronary care unit-- without considering other cues.
• Mary has no ST segment changes, does have chest pain as her chief complaint, but does not have any of the remaining five factors, thus is classified as "low risk" and sent to a regular nursing bed, after all three cues are checked.
• Jack has no ST segment change and does not have chest pain as his chief complaint, thus is classified as "low risk" and sent to a regular nursing bed, by considering these two cues.

The accuracy and robustness of fast-and-frugal trees has been shown to be comparable to that of Bayesian benchmarks in studies by Laskey and Martignon (2014)^[LM]. Extensive studies comparing the performance of fast-and-frugal trees to that of classification algorithms used in statistics and machine learning, such as Naive Bayes, CART, random forests, and logistic regression, have also been carried out by using dozens of real-world datasets ^[WHM][MKW].[4]

Fast-and-frugal trees are used to perform binary classifications or decisions. In psychology, medicine, and other fields, signal detection theory (or detection theory) has been the classic theory under which such tasks are analyzed.

The theory assumes that there are two categories of events or people (e.g., people with and without heart problems), of which the category more relevant to us is referred as “signal” while the other is referred to as “noise.” The two differ in their distribution on an observation scale that we may call “evidence,” with the signal distribution having a higher mean. One can make two possible classifications, namely “signal” or “noise,” upon gathering the evidence. This leads to four possible outcomes: hit (classify as “signal” when it is indeed a signal), correct rejection (classify as “noise” when it is indeed a noise), miss (classify as “noise” when it is actually a signal), and false alarm (classify as “signal” when it is actually a noise). To maximize overall accuracy or the expected value of a classification, the theory posits that we need to carefully select the classification criterion on the evidence scale, above which we make a “signal” decision and below which “noise.” Specially, when the cost of a miss is very high (i.e., classifying a patient with heart problem as normal), a lower, more “liberal” criterion (i.e., toward the left in the evidence scale) needs to be selected, whereas when the cost of a false alarm is very high (e.g., classifying an innocent person as guilty of a murder), a higher, more “conservative” criterion will be better. This implies that a good decision-maker needs to be properly biased in most real-world situations; this is the most critical and relevant insight from signal detection theory on classification and decision making.

Figure 2. The higher section of the figure illustrates the assumptions of signal-detection theory in a binary decision task. The three vertical lines represent three decision criteria the agent and the decision-maker may adopt. The lower section illustrates the four possible FFTs that can be constructed when three features are consulted in a fixed order. Based on the classifications pointed to by the first two exits, the trees are named from left to right FFTss, FFTsn, FFTns, and FFTnn. The arrows connecting the figure parts indicate roughly the locations of the four FFTs’ decision criteria when they are used to make a binary s/n (for signal and noise, respectively) classification or decision. Among the four, FFTss has the most liberal decision criterion and FFTnn the most conservative one. The decision criteria of FFTsn and FFTns are less extreme than the other two, with FFTsn being more liberal than FFTns.

In 2011, Luan, Schooler, and Gigerenzer analyzed characteristics of fast-and-frugal trees from the perspective of signal detection theory. There are several key findings from this analysis. First, the choice of the exit structure of a fast-and-frugal tree corresponds to the setting of the decision criterion in signal detection. In a nutshell, the earlier a "signal exit" appears in a fast-and-frugal tree, the more liberally biased is the tree. The relative biases of two fast-and-frugal trees are determined by the first exit in which the two differ, with the one having the “signal exit” - denoted by "s" - always being more liberal as the one having the "noise exit" - denoted by "n" (Figure 2). For example, an FFTsnnn ( here again s = "Signal exit", n = "noise exit") is more liberally biased than an FFTnsss. This principle is referred to as the “lexicographic decision bias” of fast-and-frugal trees.

Second, a series of simulations show that fast-and-frugal trees with different exit structures will lead to different—sometimes drastically different—expected value of a decision when the consequences of a miss and a false alarm differ. Therefore, when constructing and applying a fast-and-frugal tree, one needs to choose an exit structure that matches well the decision payoff structure of a task.

Third, the overall sensitivity of a fast-and-frugal tree—that is, how well the tree can discriminate a signal from a noise and which can be measured by d’ or A’ from signal detection theory—is affected by properties of the cues that make up the tree, such as the mean and variance of the cues’ sensitivities and the inter-cue correlations among the cues, but not much by the exit structure of the tree. And finally, the performance of fast-and-frugal trees is robust and comparable to much more sophisticated decision algorithms developed in signal detection theory, including the ideal observer analysis model and the optimal sequential sampling model. In the context of out-of-sample predictions, fast-and-frugal trees perform the best relative to other models when the learning sample size is relatively small (e.g., less than 80 trials).

Figure 3. A fast-and-frugal tree that can help soldiers stationed in Afghanistan distinguish whether a car approaching a check-point is driven by civilians or potential suicide bombers (Keller & Katsikopoulos, 2016) ^[KK].

Figure 4. Fast-and-frugal trees that describe how a person decides whether to forgive another person for an offense the latter committed during social interactions (left; Tan, Luan, & Katsikopoulos, 2017) ^[TLK] and how British judges decide whether to make a punitive bail decision (right. Dhami, 2003) ^[D].