You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by WeichenXu123 <gi...@git.apache.org> on 2017/11/06 10:13:08 UTC
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
GitHub user WeichenXu123 opened a pull request:
https://github.com/apache/spark/pull/19666
[SPARK-22451][ML] Reduce decision tree aggregate size for unordered features from O(2^numCategories) to O(numCategories)
## What changes were proposed in this pull request?
We do not need generate all possible splits for unordered features before aggregate,
- Change `mixedBinSeqOp` (which running on executor), for each unordered feature, we do the same stat with ordered features. so for unordered features, we only need O(numCategories) space for this feature stat.
- After driver side get the aggregate result, generate all possible split combinations, and compute the best split.
This will reduce decision tree aggregate size for each unordered feature from `O(2^numCategories)` to `O(numCategories)`, `numCategories` is the arity of this unordered feature.
This also reduce the cpu cost in executor side. Reduce time complexity for this unordered feature from `O(numPoints * 2^numCategories)` to `O(numPoints)`.
This won't increase time complexity for unordered features best split computing in driver side.
## How was this patch tested?
UT added.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/WeichenXu123/spark improve_decision_tree
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/19666.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #19666
----
commit 93c7e0fdf8a16a4e14adfe1891b0a4dc018f6de8
Author: WeichenXu <we...@databricks.com>
Date: 2017-11-05T13:35:45Z
init pr
commit e79abfd2a231ff29abc4be1723002542c85189df
Author: WeichenXu <we...@databricks.com>
Date: 2017-11-06T09:41:04Z
add unit test
----
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149561550
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -741,17 +678,43 @@ private[spark] object RandomForest extends Logging {
(splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
} else if (binAggregates.metadata.isUnordered(featureIndex)) {
// Unordered categorical feature
- val leftChildOffset = binAggregates.getFeatureOffset(featureIndexIdx)
- val (bestFeatureSplitIndex, bestFeatureGainStats) =
- Range(0, numSplits).map { splitIndex =>
- val leftChildStats = binAggregates.getImpurityCalculator(leftChildOffset, splitIndex)
- val rightChildStats = binAggregates.getParentImpurityCalculator()
- .subtract(leftChildStats)
+ val numBins = binAggregates.metadata.numBins(featureIndex)
+ val featureOffset = binAggregates.getFeatureOffset(featureIndexIdx)
+
+ val binStatsArray = Array.tabulate(numBins) { binIndex =>
+ binAggregates.getImpurityCalculator(featureOffset, binIndex)
+ }
+ val parentStats = binAggregates.getParentImpurityCalculator()
+
+ var bestGain = Double.NegativeInfinity
+ var bestSet: BitSet = null
+ var bestLeftChildStats: ImpurityCalculator = null
+ var bestRightChildStats: ImpurityCalculator = null
+
+ traverseUnorderedSplits[ImpurityCalculator](numBins, null,
+ (stats, binIndex) => {
+ val binStats = binStatsArray(binIndex)
+ if (stats == null) {
+ binStats
+ } else {
+ stats.copy.add(binStats)
+ }
+ },
+ (set, leftChildStats) => {
+ val rightChildStats = parentStats.copy.subtract(leftChildStats)
gainAndImpurityStats = calculateImpurityStats(gainAndImpurityStats,
leftChildStats, rightChildStats, binAggregates.metadata)
- (splitIndex, gainAndImpurityStats)
- }.maxBy(_._2.gain)
- (splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
+ if (gainAndImpurityStats.gain > bestGain) {
+ bestGain = gainAndImpurityStats.gain
+ bestSet = set | new BitSet(numBins) // copy set
--- End diff --
The class do not support `copy`
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by tengpeng <gi...@git.apache.org>.
Github user tengpeng commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r175646373
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/DecisionTreeMetadata.scala ---
@@ -152,15 +152,13 @@ private[spark] object DecisionTreeMetadata extends Logging {
// TODO(SPARK-9957): Handle this properly by filtering out those features.
if (numCategories > 1) {
// Decide if some categorical features should be treated as unordered features,
--- End diff --
Change , to .
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 closed the pull request at:
https://github.com/apache/spark/pull/19666
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149237212
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -741,17 +678,43 @@ private[spark] object RandomForest extends Logging {
(splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
} else if (binAggregates.metadata.isUnordered(featureIndex)) {
// Unordered categorical feature
- val leftChildOffset = binAggregates.getFeatureOffset(featureIndexIdx)
- val (bestFeatureSplitIndex, bestFeatureGainStats) =
- Range(0, numSplits).map { splitIndex =>
- val leftChildStats = binAggregates.getImpurityCalculator(leftChildOffset, splitIndex)
- val rightChildStats = binAggregates.getParentImpurityCalculator()
- .subtract(leftChildStats)
+ val numBins = binAggregates.metadata.numBins(featureIndex)
+ val featureOffset = binAggregates.getFeatureOffset(featureIndexIdx)
+
+ val binStatsArray = Array.tabulate(numBins) { binIndex =>
--- End diff --
Could you please add a comment explaining what this is? E.g.:
`// Each element of binStatsArray stores pre-computed label statistics for a single bin of the current future`
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by tengpeng <gi...@git.apache.org>.
Github user tengpeng commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r175646335
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/DecisionTreeMetadata.scala ---
@@ -152,15 +152,13 @@ private[spark] object DecisionTreeMetadata extends Logging {
// TODO(SPARK-9957): Handle this properly by filtering out those features.
if (numCategories > 1) {
// Decide if some categorical features should be treated as unordered features,
--- End diff --
Change , to .
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149242575
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -976,6 +930,44 @@ private[spark] object RandomForest extends Logging {
categories
}
+ private[tree] def traverseUnorderedSplits[T](
--- End diff --
Also, does `traverseUnorderedSplits` need to take a type parameter / two different closures as method arguments? AFAICT the use of a type parameter/closures here allow us to unit test this functionality on a simple example, but I wonder if we could simplify this somehow.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on the issue:
https://github.com/apache/spark/pull/19666
Discussed with @jkbradley, I'll split up #19433 so that the parts of it that'd potentially conflict with this PR (refactoring RandomForest.scala into utility classes) can be merged first.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19666
**[Test build #83481 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83481/testReport)** for PR 19666 at commit [`e79abfd`](https://github.com/apache/spark/commit/e79abfd2a231ff29abc4be1723002542c85189df).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149238185
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -741,17 +678,43 @@ private[spark] object RandomForest extends Logging {
(splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
} else if (binAggregates.metadata.isUnordered(featureIndex)) {
// Unordered categorical feature
- val leftChildOffset = binAggregates.getFeatureOffset(featureIndexIdx)
- val (bestFeatureSplitIndex, bestFeatureGainStats) =
- Range(0, numSplits).map { splitIndex =>
- val leftChildStats = binAggregates.getImpurityCalculator(leftChildOffset, splitIndex)
- val rightChildStats = binAggregates.getParentImpurityCalculator()
- .subtract(leftChildStats)
+ val numBins = binAggregates.metadata.numBins(featureIndex)
+ val featureOffset = binAggregates.getFeatureOffset(featureIndexIdx)
+
+ val binStatsArray = Array.tabulate(numBins) { binIndex =>
+ binAggregates.getImpurityCalculator(featureOffset, binIndex)
+ }
+ val parentStats = binAggregates.getParentImpurityCalculator()
+
+ var bestGain = Double.NegativeInfinity
+ var bestSet: BitSet = null
+ var bestLeftChildStats: ImpurityCalculator = null
+ var bestRightChildStats: ImpurityCalculator = null
+
+ traverseUnorderedSplits[ImpurityCalculator](numBins, null,
--- End diff --
Could you please add a comment explaining what this does? E.g.:
`// Computes the best split for the current feature, storing the result across the vars above`
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on the issue:
https://github.com/apache/spark/pull/19666
Also cc @smurching Thanks!
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149241680
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -976,6 +930,44 @@ private[spark] object RandomForest extends Logging {
categories
}
+ private[tree] def traverseUnorderedSplits[T](
+ arity: Int,
+ zeroStats: T,
+ seqOp: (T, Int) => T,
+ finalizer: (BitSet, T) => Unit): Unit = {
+ assert(arity > 1)
+
+ // numSplits = (1 << arity - 1) - 1
+ val numSplits = DecisionTreeMetadata.numUnorderedSplits(arity)
+ val subSet: BitSet = new BitSet(arity)
+
+ // dfs traverse
+ // binIndex: [0, arity)
+ def dfs(binIndex: Int, combNumber: Int, stats: T): Unit = {
+ if (binIndex == arity) {
+ // recursion exit when binIndex == arity
+ if (combNumber > 0) {
+ // we get an available unordered split, saved in subSet.
+ finalizer(subSet, stats)
+ }
+ } else {
+ subSet.set(binIndex)
+ val leftChildCombNumber = combNumber + (1 << binIndex)
+ // pruning: only need combNumber satisfy: 1 <= combNumber <= numSplits
--- End diff --
If I understand correctly, the check `if (leftChildCombNumber <= numSplits)` helps us ensure that we consider each split only once, right?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19666
**[Test build #83481 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83481/testReport)** for PR 19666 at commit [`e79abfd`](https://github.com/apache/spark/commit/e79abfd2a231ff29abc4be1723002542c85189df).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* ` test(\"Multiclass classification with unordered categorical features: split calculations\") `
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by facaiy <gi...@git.apache.org>.
Github user facaiy commented on the issue:
https://github.com/apache/spark/pull/19666
Hi, I write a demo with python. I'll be happy if it could be useful.
For N bins, say `[x_1, x_2, ..., x_N]`, since all its splits contain either `x_1` or not, so we can choose the half splits which doesn't contain x_1 as left splits.
If I understand it correctly, the left splits are indeed all combinations of the left bins, `[x_2, x_3, ... x_N]`. The problem can be solved by the [backtracking algorithm](https://en.wikipedia.org/wiki/Backtracking).
Please correct me if I'm wrong. Thanks very much.
```python
#!/usr/bin/env python
def gen_splits(bins):
if len(bins) == 1:
return bins
results = []
partial_res = []
gen_splits_iter(1, bins, partial_res, results)
return results
def gen_splits_iter(dep, bins, partial_res, results):
if partial_res:
left_splits = partial_res[:]
right_splits = [x for x in bins if x not in left_splits]
results.append("left: {:20}, right: {}".format(str(left_splits), right_splits))
for m in range(dep, len(bins)):
partial_res.append(bins[m])
gen_splits_iter(m+1, bins, partial_res, results)
partial_res.pop()
if __name__ == "__main__":
print("first example:")
bins = ["a", "b", "c"]
print("bins: {}\n-----".format(bins))
splits = gen_splits(bins)
for s in splits:
print(s)
print("\n\n=============")
print("second example:")
bins = ["a", "b", "c", "d", "e"]
print("bins: {}\n-----".format(bins))
splits = gen_splits(bins)
for s in splits:
print(s)
```
logs:
```bash
~/Downloads ❯❯❯ python test.py
first example:
bins: ['a', 'b', 'c']
-----
left: ['b'] , right: ['a', 'c']
left: ['b', 'c'] , right: ['a']
left: ['c'] , right: ['a', 'b']
=============
second example:
bins: ['a', 'b', 'c', 'd', 'e']
-----
left: ['b'] , right: ['a', 'c', 'd', 'e']
left: ['b', 'c'] , right: ['a', 'd', 'e']
left: ['b', 'c', 'd'] , right: ['a', 'e']
left: ['b', 'c', 'd', 'e'], right: ['a']
left: ['b', 'c', 'e'] , right: ['a', 'd']
left: ['b', 'd'] , right: ['a', 'c', 'e']
left: ['b', 'd', 'e'] , right: ['a', 'c']
left: ['b', 'e'] , right: ['a', 'c', 'd']
left: ['c'] , right: ['a', 'b', 'd', 'e']
left: ['c', 'd'] , right: ['a', 'b', 'e']
left: ['c', 'd', 'e'] , right: ['a', 'b']
left: ['c', 'e'] , right: ['a', 'b', 'd']
left: ['d'] , right: ['a', 'b', 'c', 'e']
left: ['d', 'e'] , right: ['a', 'b', 'c']
left: ['e'] , right: ['a', 'b', 'c', 'd']
```
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19666
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/83481/
Test FAILed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by facaiy <gi...@git.apache.org>.
Github user facaiy commented on the issue:
https://github.com/apache/spark/pull/19666
Thank you, @WeichenXu123 . You can also use the condition "include the first bin" to filter left splits. Perhaps it is better.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on the issue:
https://github.com/apache/spark/pull/19666
@facaiy Thanks for your review! I put more explanation on the design purpose of `traverseUnorderedSplits`. But, if you have better solution, no hesitate to tell me!
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on the issue:
https://github.com/apache/spark/pull/19666
@facaiy Your idea looks also reasonable. So we can use the condition "exclude the first bin" to do the pruning (filter out the other half symmetric splits). This condition looks simpler than `1 <= combNumber <= numSplists`, `Good idea !
And your code use another traverse order, my current PR is also backtracking, with different traverse order, but I think both of them works, and both of their complexity will be `O(2^n)`
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/19666
Btw, this is going to conflict with https://github.com/apache/spark/pull/19433 a lot. @WeichenXu123 and @smurching have you planned for merging one before the other?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149274660
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -976,6 +930,44 @@ private[spark] object RandomForest extends Logging {
categories
}
+ private[tree] def traverseUnorderedSplits[T](
+ arity: Int,
+ zeroStats: T,
+ seqOp: (T, Int) => T,
+ finalizer: (BitSet, T) => Unit): Unit = {
+ assert(arity > 1)
+
+ // numSplits = (1 << arity - 1) - 1
+ val numSplits = DecisionTreeMetadata.numUnorderedSplits(arity)
+ val subSet: BitSet = new BitSet(arity)
+
+ // dfs traverse
+ // binIndex: [0, arity)
+ def dfs(binIndex: Int, combNumber: Int, stats: T): Unit = {
+ if (binIndex == arity) {
+ // recursion exit when binIndex == arity
+ if (combNumber > 0) {
+ // we get an available unordered split, saved in subSet.
+ finalizer(subSet, stats)
+ }
+ } else {
+ subSet.set(binIndex)
+ val leftChildCombNumber = combNumber + (1 << binIndex)
+ // pruning: only need combNumber satisfy: 1 <= combNumber <= numSplits
--- End diff --
Yes. for example: "00101" and "11010" they're equivalent splits, we should traverse only one of them.
So here I use the condition `1 <= combNumber <= numSplits` to do the pruning. It can simply filter out another half splits.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by facaiy <gi...@git.apache.org>.
Github user facaiy commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149313427
--- Diff: mllib/src/test/scala/org/apache/spark/ml/tree/impl/RandomForestSuite.scala ---
@@ -631,6 +614,42 @@ class RandomForestSuite extends SparkFunSuite with MLlibTestSparkContext {
val expected = Map(0 -> 1.0 / 3.0, 2 -> 2.0 / 3.0)
assert(mapToVec(map.toMap) ~== mapToVec(expected) relTol 0.01)
}
+
+ test("traverseUnorderedSplits") {
+
--- End diff --
Since `traverseUnorderedSplits` is a private method, I wonder whether we can check the unorder splits on DecisonTree directly? For example, create a tiny dataset and generate a shallow tree (depth = 1?). I know the test case is difficult (maybe impossible) to design, however it focuses on behavior instead of implementation.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149238531
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -976,6 +930,44 @@ private[spark] object RandomForest extends Logging {
categories
}
+ private[tree] def traverseUnorderedSplits[T](
--- End diff --
Could you please add a docstring for this method, since it's a bit complicated?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by facaiy <gi...@git.apache.org>.
Github user facaiy commented on the issue:
https://github.com/apache/spark/pull/19666
I believe that unordered features will benefit a lot from the idea, however I have two questions:
1. I'm a little confused by 964L in `traverseUnorderedSplits`. Is it a backtracking algorithm?
```scala
dfs(binIndex + 1, combNumber, stats)
```
2. `traverseUnorderedSplits` succeed in decoupling an abstraction from its implementation. Cool! However, I just wonder whether we can write a simpler function, say, remove `seqOp`, `finalizer`, `T` and collect all logic together in one place?
Anyway, thanks for your good work, @WeichenXu123.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149567340
--- Diff: mllib/src/test/scala/org/apache/spark/ml/tree/impl/RandomForestSuite.scala ---
@@ -631,6 +614,42 @@ class RandomForestSuite extends SparkFunSuite with MLlibTestSparkContext {
val expected = Map(0 -> 1.0 / 3.0, 2 -> 2.0 / 3.0)
assert(mapToVec(map.toMap) ~== mapToVec(expected) relTol 0.01)
}
+
+ test("traverseUnorderedSplits") {
+
--- End diff --
So how to test all possible splits to make sure the generated splits are all correct ? If tree generated, only best split is remained.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on the issue:
https://github.com/apache/spark/pull/19666
@smurching I guess if iterating over gray code will have higher time complexity O(n * 2^n), (Not very sure, maybe there's some high efficient algos?) , the recursive traverse in my PR only need O(2^n).
and , recursive traversing has advantage in "pruning", the pruning condition I mentioned above "1 <= combNumber <= numSplits", recursive traversing can pruning the total subtree, and save about half the time. Can iterating over gray code also do this ?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by facaiy <gi...@git.apache.org>.
Github user facaiy commented on the issue:
https://github.com/apache/spark/pull/19666
In fact, I'm not sure whether the idea is right, so no hesitate to correct me. I assume the algorithm requires O(N^2) complexity.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19666
Merged build finished. Test FAILed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19666: [SPARK-22451][ML] Reduce decision tree aggregate ...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19666#discussion_r149238123
--- Diff: mllib/src/main/scala/org/apache/spark/ml/tree/impl/RandomForest.scala ---
@@ -741,17 +678,43 @@ private[spark] object RandomForest extends Logging {
(splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
} else if (binAggregates.metadata.isUnordered(featureIndex)) {
// Unordered categorical feature
- val leftChildOffset = binAggregates.getFeatureOffset(featureIndexIdx)
- val (bestFeatureSplitIndex, bestFeatureGainStats) =
- Range(0, numSplits).map { splitIndex =>
- val leftChildStats = binAggregates.getImpurityCalculator(leftChildOffset, splitIndex)
- val rightChildStats = binAggregates.getParentImpurityCalculator()
- .subtract(leftChildStats)
+ val numBins = binAggregates.metadata.numBins(featureIndex)
+ val featureOffset = binAggregates.getFeatureOffset(featureIndexIdx)
+
+ val binStatsArray = Array.tabulate(numBins) { binIndex =>
+ binAggregates.getImpurityCalculator(featureOffset, binIndex)
+ }
+ val parentStats = binAggregates.getParentImpurityCalculator()
+
+ var bestGain = Double.NegativeInfinity
+ var bestSet: BitSet = null
+ var bestLeftChildStats: ImpurityCalculator = null
+ var bestRightChildStats: ImpurityCalculator = null
+
+ traverseUnorderedSplits[ImpurityCalculator](numBins, null,
+ (stats, binIndex) => {
+ val binStats = binStatsArray(binIndex)
+ if (stats == null) {
+ binStats
+ } else {
+ stats.copy.add(binStats)
+ }
+ },
+ (set, leftChildStats) => {
+ val rightChildStats = parentStats.copy.subtract(leftChildStats)
gainAndImpurityStats = calculateImpurityStats(gainAndImpurityStats,
leftChildStats, rightChildStats, binAggregates.metadata)
- (splitIndex, gainAndImpurityStats)
- }.maxBy(_._2.gain)
- (splits(featureIndex)(bestFeatureSplitIndex), bestFeatureGainStats)
+ if (gainAndImpurityStats.gain > bestGain) {
+ bestGain = gainAndImpurityStats.gain
+ bestSet = set | new BitSet(numBins) // copy set
--- End diff --
Why not use `set.copy()`?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19666: [SPARK-22451][ML] Reduce decision tree aggregate size fo...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on the issue:
https://github.com/apache/spark/pull/19666
OK. I will waiting @smurching to merge split parts of #19433 get merged first, and then I will update this PR.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org