Github user atalwalkar commented on a diff in the pull request:
https://github.com/apache/spark/pull/2063#discussion_r16511804
--- Diff: docs/mllib-decision-tree.md ---
@@ -77,109 +85,316 @@ bins if the condition is not satisfied.
**Categorical features**
-For `$M$` categorical feature values, one could come up with `$2^(M-1)-1$`
split candidates. For
-binary classification, we can reduce the number of split candidates to
`$M-1$` by ordering the
+For a categorical feature with `$M$` possible values (categories), one
could come up with
+`$2^{M-1}-1$` split candidates. For binary classification and regression,
+we can reduce the number of split candidates to `$M-1$` by ordering the
categorical feature values by the proportion of labels falling in one of
the two classes (see
Section 9.2.4 in
[Elements of Statistical Machine
Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/) for
details). For example, for a binary classification problem with one
categorical feature with three
-categories A, B and C with corresponding proportion of label 1 as 0.2, 0.6
and 0.4, the categorical
-features are ordered as A followed by C followed B or A, C, B. The two
split candidates are A \| C, B
-and A , C \| B where \| denotes the split. A similar heuristic is used for
multiclass classification
-when `$2^(M-1)-1$` is greater than the number of bins -- the impurity for
each categorical feature value
-is used for ordering.
+categories A, B and C whose corresponding proportions of label 1 are 0.2,
0.6 and 0.4, the categorical
+features are ordered as A, C, B. The two split candidates are A \| C, B
+and A , C \| B where \| denotes the split.
+
+In multiclass classification, all `$2^{M-1}-1$` possible splits are used
whenever possible.
+When `$2^{M-1}-1$` is greater than the `maxBins` parameter, we use a
(heuristic) method
+similar to the method used for binary classification and regression.
+The `$M$` categorical feature values are ordered by impurity,
+and the resulting `$M-1$` split candidates are considered.
### Stopping rule
The recursive tree construction is stopped at a node when one of the two
conditions is met:
-1. The node depth is equal to the `maxDepth` training parameter
+1. The node depth is equal to the `maxDepth` training parameter.
2. No split candidate leads to an information gain at the node.
+## Implementation details
+
### Max memory requirements
-For faster processing, the decision tree algorithm performs simultaneous
histogram computations for all nodes at each level of the tree. This could lead
to high memory requirements at deeper levels of the tree leading to memory
overflow errors. To alleviate this problem, a 'maxMemoryInMB' training
parameter is provided which specifies the maximum amount of memory at the
workers (twice as much at the master) to be allocated to the histogram
computation. The default value is conservatively chosen to be 128 MB to allow
the decision algorithm to work in most scenarios. Once the memory requirements
for a level-wise computation crosses the `maxMemoryInMB` threshold, the node
training tasks at each subsequent level is split into smaller tasks.
+For faster processing, the decision tree algorithm performs simultaneous
histogram computations for
+all nodes at each level of the tree. This could lead to high memory
requirements at deeper levels
+of the tree, leading to memory overflow errors. To alleviate this problem,
a `maxMemoryInMB`
--- End diff --
"...tree, leading to..." -> "...tree, potentially leading to..."
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
