Solved – Oblivious Decision Tree and Why

boostingcartmachine learning

I read the catboost paper and they mentioned the trees are oblivious decision tree. What is the definition of oblivious decision tree? I found two possible candidates but not sure if they are the correct ones:

  1. The feature used for splitting is the same across all intermediate nodes within the same level of tree.
  2. The definition of oblivious tree from Wikipedia: All the leaves are in the same level, all the internal nodes have degree at most 3, and only the nodes along the rightmost path in the tree may have degree of one.

In addition, why do we want to use an oblivious decision tree instead of a more general binary tree?

Best Answer

1. - correct

2. - false.

The definition of the oblivious tree can be found here: Bottom-Up Induction of Oblivious Read-Once Decision Graphs: Strengths and Limitations (1994)

Short extract: