Background to make sure I understand decision trees:
In order to create a decision tree, we go through each dimension and we attempt create two partitions of the data by trying every possible "split" of the data along each dimension, constantly checking some metric of each split (e.g. the Gini coefficient of both of the partitioned datasets), and trying to minimize that metric (e.g. the sum of the Gini indexes of the partitioned data). Once we find that best split, we recursively apply this algorithm to each of the partitioned datasets, and we remember the hierarchy of splits. We stop either when every leaf node is pure, or when we reach some depth, or some other criteria.
My Question:
Does this mean that if I were to create a decision tree based on some m x n dataset, and then I find another n dimensional point that I would want to use to "train the tree," I would have to recreate the tree from scratch on the (m+1) x n dataset? Is this what is meant when it's said that decision trees are "unstable?" Does that mean that active learning on decision trees is impossible, since "retraining" the decision tree requires having the entire dataset - any existing tree structure / splits might have to be discarded if a new point is introduced that would "disrupt" the balance of, say, the topmost split?
