Fully-Dynamic Decision Trees

Marco Bressan, Gabriel Damay, Mauro Sozio

We develop the first fully dynamic algorithm that maintains a decision tree over an arbitrary sequence of insertions and deletions of labeled examples. Given $\epsilon >0$ our algorithm g…