Skip to main content
Cross Validated

Return to Question

added 24 characters in body
Source Link
bensenberner
bensenberner
  • 13
  • 3

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?

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.

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?

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?

Source Link
bensenberner
bensenberner
  • 13
  • 3

Is active learning with decision trees possible?

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.

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?