You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by MechCoder <gi...@git.apache.org> on 2016/06/29 00:30:23 UTC
[GitHub] spark pull request #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplit...
GitHub user MechCoder opened a pull request:
https://github.com/apache/spark/pull/13959
[SPARK-14351] [MLlib] [ML] Optimize findBestSplits method for decision trees (and random forest)
## What changes were proposed in this pull request?
The current `findBestSplits` method creates an instance of `ImpurityCalculator` and `ImpurityStats` for every possible split and feature in the search for the bestSplit. Every instance of `ImpurityCalculator` creates an array of size `statsSize` which is unnecessary and take a non-negligible amount of time. This pull request tackles this problem by the following technique.
1. Remove the `impurityCalculator` instantiation for every possible split and feature. Replace this by a `calculateGain` method for each impurity that computes the gain directly from the `allStats` attribute of the `DTStatsAggregator` which holds all the necessary information.
2. Replace returning an instance of `ImpurityStats` for every possible split and feature with just the information gain since the gain is sufficient to calculate the `bestSplit`. Just return an instance of `ImpurityStats` once for the `bestSplit`
3. Remove the not-so-useful `calculateImpurityStats` method.
## How was this patch tested?
Since this is a performance improvement, tests are necessary. Here are the improvements for a `RandomForestRegressor` with `maxDepth` set to 30, `subSamplingRate` set to 1 and `maxBins` set to 20 on synthetic data. The timings were calculated locally and the mean of 3 attempts were taken.
| n_trees | n_samples | n_features | time in master | total time in this branch |
| ------------- |:-------------:| -----------:|---------------:|--------------------------:|
| 1 | 10000 | 500 | 8.954 | 7.786 |
| 10 | 10000 | 500 | 9.44 | 6.825 |
| 100 | 10000 | 500 | 18.457 | 16.498 |
| 1 | 500 | 10000 | 8.718 | 6.783 |
| 10 | 500 | 10000 | 8.579 | 6.853 |
| 100 | 500 | 10000 | 17.593 | 15.905 |
| 1 | 1000 | 1000 | 8.323 | 6.456 |
| 10 | 1000 | 1000 | 8.841 | 6.633 |
| 100 | 1000 | 1000 | 17.834 | 16.077 |
| 500 | 1000 | 1000 | 64.3 | 58.94 |
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/MechCoder/spark again
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/13959.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 #13959
----
commit 64d066b90b152ceb71b185b7e17313486974ae77
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-27T20:42:44Z
Add calculateGain method to all Impurity objects
commit f1d8c8950f8adace6ee175cd569b20ed6468bb61
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-27T21:32:56Z
Refactor gain calculation for categorical splits
commit 6e31e3a7b36981c8ccbf867e013363aa6f784e39
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-27T22:58:10Z
Remove impurity calculation to outside the for loop
commit ea4a0735c14ff91ad1071fb517da3fd890080354
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-28T00:45:36Z
Remove per feature impurityCalculator initialization
commit ca8b36088b74cacb7f162fb793070c4d3c6a1a8c
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-28T17:27:40Z
Get rid of calculateImpurityStats
commit 67b401a6a0e59b48a167e4f3036ca9f3f6a5df1f
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-28T18:17:32Z
where did that come from?
commit e8b89141f6cabfef5f582fe9521f4443afa9ec65
Author: MechCoder <mk...@nyu.edu>
Date: 2016-06-29T00:01:55Z
Add documentation
----
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by MechCoder <gi...@git.apache.org>.
Github user MechCoder commented on the issue:
https://github.com/apache/spark/pull/13959
@jkbradley @sethah Please have a look when free!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/13959
The lack of bandwidth in MLlib means that sometimes good code that would make an impact just gets ignored. This is kind of the reality of things. However, if we are going to close the PR simply because committers could not or did not get to it - this is the case here IMO - then we should also close the JIRA. Closing a PR for this reason essentially means "we don't see this as an issue worth spending time on." That's a reason to close a JIRA as well. Closing the JIRA will at least prevent others from wasting their time on this issue like @MechCoder did.
If we don't close the JIRA, then it seems like we are closing it merely because we don't want the "clutter" of long waiting prs. But if a PR is still valid, well-written, and solves a real problem, why would we not keep it open? This sends a bad message to contributors IMO.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/13959
Merged build finished. Test FAILed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/13959
I think the problem is that this PR was incomplete, and left open. We generally only leave open PRs that are active. There was evidently no interest in proceeding with it; I don't know if it was lack of attention.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by MechCoder <gi...@git.apache.org>.
Github user MechCoder commented on the issue:
https://github.com/apache/spark/pull/13959
I don't understand. If you don't have time to review that is fine (I've been there too), but there is no need to close a PR due to unavailability of comitters.
One of the reasons, that I am happy to have stopped contributing to Spark and focus my energy elsewhere...
Thanks!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by HyukjinKwon <gi...@git.apache.org>.
Github user HyukjinKwon commented on the issue:
https://github.com/apache/spark/pull/13959
> The reason for closing PRs but _not_ their corresponding JIRA would be that the PR is either poorly implemented or the author is non-responsive.
Yes, I tried to identify this case.
For this PR (or such PRs), the author looks still responsive and active so I do not disagree with re-opening personally because this was the point in https://github.com/apache/spark/pull/18017. Probably, I should have left a comment about this in each PR for clarification though.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by HyukjinKwon <gi...@git.apache.org>.
Github user HyukjinKwon commented on the issue:
https://github.com/apache/spark/pull/13959
I think we should fix the compatibility issue first rather then leaving this PR incomplete. If it is inactive, I would rather like to propose to close this for now.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/13959
Yes, this is a tough issue. Let's wait and see if @jkbradley has thoughts on this issue. If we don't hear anything, then I'd leave it up to @MechCoder on whether to reopen. Thanks, btw, for taking the time to do the cleanups. It is important and justified in many cases.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/13959
Merged build finished. Test FAILed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplit...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/13959
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/13959
**[Test build #61425 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/61425/consoleFull)** for PR 13959 at commit [`e8b8914`](https://github.com/apache/spark/commit/e8b89141f6cabfef5f582fe9521f4443afa9ec65).
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by HyukjinKwon <gi...@git.apache.org>.
Github user HyukjinKwon commented on the issue:
https://github.com/apache/spark/pull/13959
@MechCoder, I apologize that, probably, it sounds the reason for my suggestion was not clear initially and if it looks without a respect.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by MechCoder <gi...@git.apache.org>.
Github user MechCoder commented on the issue:
https://github.com/apache/spark/pull/13959
The test failure is just due to binary incompatibility. I can fix those once we decide that the current PR is the way to proceed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/13959
True, and I'd probably close the JIRA too. Maybe we can draw @jkbradley 's attention for a comment?
A closed PR still exists and can be examined or reopened, so it doesn't go away. I'd prefer to close it if it's almost surely not going to be merged, as a minor courtesy to the contributor, rather than leave it open. It's not so much the clutter, but, that's a factor. If there are always 500 open PRs, what's one more? and being open carries virtually no information.
I both want more closing of things to reflect that fact that, at this stage, not a lot is going to change -- and want more committers.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/13959
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/61425/
Test FAILed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/13959
**[Test build #61427 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/61427/consoleFull)** for PR 13959 at commit [`af1ff66`](https://github.com/apache/spark/commit/af1ff66153103874e97b24282bd8a207958578da).
* This patch **fails MiMa tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/13959
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/61427/
Test FAILed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by HyukjinKwon <gi...@git.apache.org>.
Github user HyukjinKwon commented on the issue:
https://github.com/apache/spark/pull/13959
FWIW, I think we already had few discussion about the last resort - automatic-closing. I was strongly against this. This is my effort to prevent this for now ...
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/13959
**[Test build #61427 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/61427/consoleFull)** for PR 13959 at commit [`af1ff66`](https://github.com/apache/spark/commit/af1ff66153103874e97b24282bd8a207958578da).
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/13959
This is fine, but are we not also policing JIRAs? I've argued above that the reason this PR has been inactive is simply lack of interest in this issue. If that's the case, then the JIRA must also be closed, since we've implicitly decided that this is no longer or never was a problem worth solving.
If it is not the case, then we must absolutely leave this open - since this is a.) still unsolved b.) good code c.) still of interest. The reason for closing PRs but _not_ their corresponding JIRA would be that the PR is either poorly implemented or the author is non-responsive. While it is no doubt frustrating for contributors to submit code that is well-written and solves a problem that a project committer asked for, I also don't know that leaving it open indefinitely is a solution either. I guess I don't understand why we'd be willing to leave JIRAs open indefinitely but not PRs. At any rate, in this case I would have proposed we ask for Joseph's (issue creator) input for a few days, and if we hear nothing close both JIRA and PR. We surely do not want others to submit patches for this issue if it will not be reviewed and merged.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #13959: [SPARK-14351] [MLlib] [ML] Optimize findBestSplits metho...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/13959
**[Test build #61425 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/61425/consoleFull)** for PR 13959 at commit [`e8b8914`](https://github.com/apache/spark/commit/e8b89141f6cabfef5f582fe9521f4443afa9ec65).
* This patch **fails MiMa tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org