What is the probability of a correct answer with different class selection strategies in a tree leaf, and how to calculate it for arbitrary probabilities?

In a decision tree, leaf nodes typically contain class probability distributions, for example, (P(C_i)) for class (C_i). The strategy for choosing the class at the leaf affects the probability of a correct answer:

1. Choosing the class with the maximum probability (argmax)

   • The probability of a correct answer is equal to the maximum value (\max_i P(C_i)).
   • This is the most common strategy, minimizing classification error at the leaf.

2. Randomly choosing a class according to the probability distribution

   • The probability of a correct answer is equal to the sum of the squares of the class probabilities: [ \sum_i P(C_i)^2 ]
   • This is related to the fact that the probability of guessing class (C_i) correctly is (P(C_i)), and the probability that the true class (C_i) is also (P(C_i)).

3. Choosing a class based on a fixed strategy (e.g., always the same class)

   • The probability of a correct answer is the probability of that class in the leaf.

For arbitrary probabilities (P(C_1), P(C_2), ..., P(C_k)), where (\sum_i P(C_i) = 1), the calculations are as follows:

• When choosing the class with the maximum probability: [ P_{correct} = \max_i P(C_i) ]

• When randomly choosing a class according to the distribution: [ P_{correct} = \sum_i P(C_i)^2 ]

Thus, the choice strategy directly influences the probability of a correct answer, and selecting the maximum probabilities is usually optimal for classification accuracy.