You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by neggert <gi...@git.apache.org> on 2016/09/08 22:01:13 UTC
[GitHub] spark pull request #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
GitHub user neggert opened a pull request:
https://github.com/apache/spark/pull/15018
[SPARK-17455][MLlib] Improve PAVA implementation in IsotonicRegression
## What changes were proposed in this pull request?
New implementation of the Pool Adjacent Violators Algorithm (PAVA) in mllib.IsotonicRegression. The previous implementation could have factorial complexity in the worst case. This implementation, which closely follows those in scikit-learn and the R `iso` package, runs in quadratic time in the worst case.
## How was this patch tested?
Existing unit tests in both `mllib` and `ml` passed before and after this patch. Scaling properties were tested by running the `poolAdjacentViolators` method in [scala-benchmarking-template](https://github.com/sirthias/scala-benchmarking-template) with the input generated by
```{scala}
val x = (1 to length).toArray.map(_.toDouble)
val y = x.reverse.zipWithIndex.map{ case (yi, i) => if (i % 2 == 1) yi - 1.5 else yi}
val w = Array.fill(length)(1d)
val input: Array[(Double, Double, Double)] = (y zip x zip w) map{ case ((y, x), w) => (y, x, w)}
```
Before this patch:
| Input Length | Time (us) |
| ------------:| ---------:|
| 100 | 1.35 |
| 200 | 3.14 |
| 400 | 116.10 |
| 800 | 2134225.90|
After this patch:
| Input Length | Time (us) |
| ------------:| ---------:|
| 100 | 1.25 |
| 200 | 2.53 |
| 400 | 5.86 |
| 800 | 10.55 |
Benchmarking was also performed with randomly-generated y values, with similar results.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/neggert/spark SPARK-17455-isoreg-algo
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/15018.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 #15018
----
commit 5608ae1f4c9089dd3a299eef14af59bed6c96192
Author: z001qdp <ni...@target.com>
Date: 2016-09-08T21:43:24Z
New PAVA implementation
----
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15018
@neggert I think this is looking good except for the question about zero weights. If throwing an error is OK to you go for it. The test should be restored, but be updated to expect an exception. Other than that, more tests always help, but there is some OK coverage already
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92232757
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
+ j = j + 1
+ }
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
+ // Pool the violating sequence with the data point preceding it
+ if (input(i)._1 != input(j)._1) {
--- End diff --
This condition is "if there was any decrease, not just == from i to j" right? and `pool` makes everything in [i,j] non-violating.
Comments from the previous code note that this could introduce a violation -- is this still possible? it wasn't obvious why it can't happen 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 pull request #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92298204
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
--- End diff --
That should be correct. Lemma 1 from "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints"
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70886/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Done. It was surprisingly tricky to test, since the exception is thrown in the executor.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71271 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71271/testReport)** for PR 15018 at commit [`132d6a6`](https://github.com/apache/spark/commit/132d6a691a0a5f65b6d2cd84d031883a6e917282).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/65117/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Found another input that triggers non-polynomial time with the code in this PR. I'm again borrowing from scikit-learn. I think this is the case they found that led them to re-write their implementation.
```
val y = ((0 until length) ++ (-(length - 1) until length) ++ (-(length - 1) to 0)).toArray.map(_.toDouble)
val x = (1 to y.length).toArray.map(_.toDouble)
```
| Input Length | Time (ns) |
| --: | --: |
| 40 | 2059 |
| 80 | 4604 |
| 160 | 1974269 |
| 320 | 3246603433 |
I'm now working on implementing what's described in the Best papers. This should give O(n), even in the worst case.
Should I close this and open a new PR with the new algorithm, or just add it here and you can squash when you merge?
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92298473
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
+ j = j + 1
+ }
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
+ // Pool the violating sequence with the data point preceding it
+ if (input(i)._1 != input(j)._1) {
--- End diff --
I believe the logic is:
* If equality holds here, then either (a) i = j or (b) the block [i,j] has equal elements.
* A violation could be introduced but will be caught on the next iteration of the outer loop.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
Thanks for pinging about this---it looks important!
One request: Do you know if there is a resource with a clearer statement of this precise algorithm for the L2 norm? That'd be nice to have. The best I found so far was "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints"
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70363 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70363/testReport)** for PR 15018 at commit [`8762531`](https://github.com/apache/spark/commit/8762531b9c70e21ce047393b252fefe2ed134036).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Looks like the build completed successfully. Somehow Jenkins didn't post the message.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/71092/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92230452
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
+ j = j + 1
--- End diff --
Nit: `j += 1` and likewise elsewhere.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70364 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70364/testReport)** for PR 15018 at commit [`d19647b`](https://github.com/apache/spark/commit/d19647b230f3350432b67a5035822cb04d529c9d).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
Thanks for the updates! This LGTM, except for deciding about negative weights.
Responding to your comment above, negative weights are just as problematic as 0 weights. See my comment above "Btw, with negative weights, ..."
I spoke with @mengxr offline, and he does not recall why the original work supported negative weights. I'll wait a few days before merging this to see if @zapletal-martin can check out the issue.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92231712
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
--- End diff --
The condition changed to >= here on purpose right? you're now looking for a region that's non-increasing, not just strictly decreasing. Just checking.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70833/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Your changes sound fine. I don't have strong feelings one way or another, although I think we should at least throw a warning if we're discarding points. I do want to point out that disallowing negative weights also breaks the API, since they were previously supported (there's even a test for them).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71271 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71271/testReport)** for PR 15018 at commit [`132d6a6`](https://github.com/apache/spark/commit/132d6a691a0a5f65b6d2cd84d031883a6e917282).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70831/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92920572
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,68 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
-
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
-
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ /*
+ Keeps track of the start and end indices of the blocks. blockBounds(start) gives the
+ index of the end of the block and blockBounds(end) gives the index of the start of the
+ block. Entries that are not the start or end of the block are meaningless.
+ */
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
+
+ /*
+ Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ gives the values for the block. Entries that are not at the start of a block
+ are meaningless.
+ */
+ val weights: Array[(Double, Double)] = input.map(x => (x._3, x._3 * x._1)) // (weight, weight * y)
--- End diff --
Up to you; might be clearer as `input.map { case (y, _, weight) => (weight, weight * y) }`
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
Sounds good. I'll run fresh tests before merging to be safe 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Alright, the PAV algorithm has been completely re-written to follow what's outlined in "Minimizing Separable Convex Functions Subject to Simple Chain Constraints". I've tested it with a bunch of different inputs that caused previous version of this algorithm to go non-polynomial. It stays linear for all of them. I will note that it's slightly slower on very small datasets (< 5000 points or so), but those still finish in less than a millisecond on my laptop, so I'm not too concerned.
The only caveat is that there was one test that I couldn't get passing, so I removed it. It involved passing input data with 0 weights. I'd argue that the isotonic regression problem doesn't even have a unique solution in that case, so we shouldn't support it. Still, it is a slight change in behavior.
Looks like Jenkins is pointing out some style issues, so I'll get to work on those.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92432636
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
--- End diff --
I hadn't actually seen that paper. I just worked from the scikit-learn implementation (which, incidentally, has changed since I submitted this PR).
I believe that either way will get you correct results. Doing `>=` should be faster in some cases, because it's greedier about pooling, which should lead to fewer iterations of the outer loop.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70134 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70134/consoleFull)** for PR 15018 at commit [`8d16043`](https://github.com/apache/spark/commit/8d16043b50629f2dc2f96c124189d284c833ddc0).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the issue:
https://github.com/apache/spark/pull/15018
LGTM
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70836/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70831 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70831/testReport)** for PR 15018 at commit [`c65e263`](https://github.com/apache/spark/commit/c65e2639741fb3e4717c2f16922d3b10c9f6e2e7).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r94640811
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,80 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // input(i) to input(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = input.map { case (y, _, weight) =>
+ require(weight != 0.0)
--- End diff --
Are negative weights OK? (you don't need a type on `weight`, but hardly matters)
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15018
@jkbradley I'll merge if there are no other thoughts here. Seems OK to me too
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
Merging with master
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70886 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70886/testReport)** for PR 15018 at commit [`a119423`](https://github.com/apache/spark/commit/a119423fa769bb6be9cc27e455a82d04360e03b3).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70216/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #65117 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/65117/consoleFull)** for PR 15018 at commit [`5608ae1`](https://github.com/apache/spark/commit/5608ae1f4c9089dd3a299eef14af59bed6c96192).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95914244
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -312,90 +313,120 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
/**
- * Performs a pool adjacent violators algorithm (PAV).
- * Uses approach with single processing of data where violators
- * in previously processed data created by pooling are fixed immediately.
- * Uses optimization of discovering monotonicity violating sequences (blocks).
+ * Performs a pool adjacent violators algorithm (PAV). Implements the algorithm originally
+ * described in [1], using the formulation from [2, 3]. Uses an array to keep track of start
+ * and end indices of blocks.
*
- * @param input Input data of tuples (label, feature, weight).
+ * [1] Grotzinger, S. J., and C. Witzgall. "Projections onto order simplexes." Applied
+ * mathematics and Optimization 12.1 (1984): 247-270.
+ *
+ * [2] Best, Michael J., and Nilotpal Chakravarti. "Active set algorithms for isotonic
+ * regression; a unifying framework." Mathematical Programming 47.1-3 (1990): 425-439.
+ *
+ * [3] Best, Michael J., Nilotpal Chakravarti, and Vasant A. Ubhaya. "Minimizing separable convex
+ * functions subject to simple chain constraints." SIAM Journal on Optimization 10.3 (2000):
+ * 658-672.
+ *
+ * @param input Input data of tuples (label, feature, weight). Weights must
+ be non-negative.
* @return Result tuples (label, feature, weight) where labels were updated
* to form a monotone sequence as per isotonic regression definition.
*/
private def poolAdjacentViolators(
input: Array[(Double, Double, Double)]): Array[(Double, Double, Double)] = {
- if (input.isEmpty) {
- return Array.empty
+ val cleanInput = input.flatMap{ case (y, x, weight) =>
--- End diff --
filter would be simpler than flatMap
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
@zapletal-martin Pinging since you wrote the original PR: There's discussion here about whether IsotonicRegression should support negative weights. Is there a good reason to? I haven't seen papers which allow negative weights, though I've only looked at a few. 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/71087/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15018
If it's correct and faster, I tend to favor merging this. The code looks OK to my understanding and passes existing tests.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #3547 has finished](https://amplab.cs.berkeley.edu/jenkins/job/NewSparkPullRequestBuilder/3547/testReport)** for PR 15018 at commit [`0aeca09`](https://github.com/apache/spark/commit/0aeca09c0ea234d8a61664f2827abd80d7850c5b).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70831 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70831/testReport)** for PR 15018 at commit [`c65e263`](https://github.com/apache/spark/commit/c65e2639741fb3e4717c2f16922d3b10c9f6e2e7).
* This patch **fails Scala style 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71092 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71092/testReport)** for PR 15018 at commit [`83480e7`](https://github.com/apache/spark/commit/83480e7ac33d9cf066245f2e8206ed6d765bafb4).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the issue:
https://github.com/apache/spark/pull/15018
@neggert I am fine for throwing an error.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70833 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70833/testReport)** for PR 15018 at commit [`da1ac1b`](https://github.com/apache/spark/commit/da1ac1b650c52428633a7efa97f3be7d2dbfae57).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70214 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70214/testReport)** for PR 15018 at commit [`61d383f`](https://github.com/apache/spark/commit/61d383fd65d3a4e99938931483e6636025893039).
* This patch **fails Scala style 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70833 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70833/testReport)** for PR 15018 at commit [`da1ac1b`](https://github.com/apache/spark/commit/da1ac1b650c52428633a7efa97f3be7d2dbfae57).
* This patch **fails Scala style 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 pull request #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r93229282
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,69 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. blockBounds(start) gives the
+ // index of the end of the block and blockBounds(end) gives the index of the start of the
+ // block. Entries that are not the start or end of the block are meaningless. The idea is that
--- End diff --
I'm still not sure about this comment -- how can `blockBounds(x)` be both the start and end of a block? the implementation below is identical.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r93266668
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,69 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. blockBounds(start) gives the
+ // index of the end of the block and blockBounds(end) gives the index of the start of the
+ // block. Entries that are not the start or end of the block are meaningless. The idea is that
--- End diff --
It relies on knowing ahead of time wether `x` is the start or end index<sup>1</sup>. If it's a start index, `blockBounds(x)` gives the ending index of that block. If it's an end index, `blockBounds(x)` gives the starting index of the block. So yes, the implementations of `blockStart` and `blockEnd` are identical. I just have two different functions because it makes the code more readable.
Maybe the comment from scikit-learn (where I borrowed this idea from) explains it better? (their `target` = my `blockBounds`)
> target describes a list of blocks. At any time, if [i..j] (inclusive) is
> an active block, then blockBounds[i] := j and target[j] := i.
The trick is just in maintaining the array so that the above property is always true. At initialization, it's trivially true because all blocks have only one element, and `blockBounds(x)` = `x`. After initialization, `blockBounds` is only modified by the merge function, which is set up to modify `blockBounds` so that this property is preserved, then return the starting index of the newly-merged block.
This is admittedly a bit tricky, but it's a lot faster than the implementation I did where created a doubly-linked list of `Block` case classes. I'm open to suggestions on how to explain it better.
<sup>1</sup> You could actually figure out whether you have a start or an end index by comparing `blockBounds(x)` to `x`. The lesser value will be the start index.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70214 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70214/testReport)** for PR 15018 at commit [`61d383f`](https://github.com/apache/spark/commit/61d383fd65d3a4e99938931483e6636025893039).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95094550
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,80 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // input(i) to input(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = input.map { case (y, _, weight) =>
+ require(weight != 0.0)
+ (weight, weight * y)
}
- var i = 0
- val len = input.length
- while (i < len) {
- var j = i
+ // a few convenience functions to make the code more readable
+
+ // blockStart and blockEnd have identical implementations. We create two different
+ // functions to make the code more expressive
+ def blockEnd(start: Int): Int = blockBounds(start)
+ def blockStart(end: Int): Int = blockBounds(end)
+
+ // the next block starts at the index after the end of this block
+ def nextBlock(start: Int): Int = blockEnd(start) + 1
+
+ // the previous block ends at the index before the start of this block
+ // we then use blockStart to find the start
+ def prevBlock(start: Int): Int = blockStart(start - 1)
+
+ // Merge two adjacent blocks, updating blockBounds and weights to reflect the merge
+ // Return the start index of the merged block
+ def merge(block1: Int, block2: Int): Int = {
+ assert(blockEnd(block1) + 1 == block2, "attempting to merge non-consecutive blocks")
--- End diff --
Please make the error message more informative:
* Make it clear that this indicates an internal bug within IsotonicRegression
* State the invalid values
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95775162
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -312,10 +313,19 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
/**
- * Performs a pool adjacent violators algorithm (PAV).
- * Uses approach with single processing of data where violators
- * in previously processed data created by pooling are fixed immediately.
- * Uses optimization of discovering monotonicity violating sequences (blocks).
+ * Performs a pool adjacent violators algorithm (PAV). Implements the algorithm originally
+ * described in [1], using the formulation from [2, 3]. Uses an array to keep track of start
+ * and end indices of blocks.
+ *
+ * [1] Grotzinger, S. J., and C. Witzgall. "Projections onto order simplexes." Applied
+ * mathematics and Optimization 12.1 (1984): 247-270.
+ *
+ * [2] Best, Michael J., and Nilotpal Chakravarti. "Active set algorithms for isotonic
+ * regression; a unifying framework." Mathematical Programming 47.1-3 (1990): 425-439.
+ *
+ * [3] Best, Michael J., Nilotpal Chakravarti, and Vasant A. Ubhaya. "Minimizing separable convex
+ * functions subject to simple chain constraints." SIAM Journal on Optimization 10.3 (2000):
+ * 658-672.
*
* @param input Input data of tuples (label, feature, weight).
--- End diff --
Can you update the param doc to indicate that now negative weights are prohibited?
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70134/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70136 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70136/consoleFull)** for PR 15018 at commit [`9cfa5ed`](https://github.com/apache/spark/commit/9cfa5ed57cbedcb5189d612c74f5c81c4cc0cc0b).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the issue:
https://github.com/apache/spark/pull/15018
SGTM. See if @jkbradley has more comment?
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
@srowen Addressed your comments and fixed some style issues.
Some updated timings:
Alternating decreasing input
val x = (1 to length).toArray.map(_.toDouble)
val y = x.reverse.zipWithIndex.map{ case (yi, i) => if (i % 2 == 1) yi - 1.5 else yi}
Before:
| Input Length | Time (us) |
|-------------:|----------:|
| 100 | 1.4 |
| 200 | 3.0 |
| 400 | 101.8 |
| 800 | 2,010,511.7 |
After:
| Input Length | Time (us) |
|-------------:|----------:|
| 100 | 2.5 |
| 200 | 5.8 |
| 400 | 10.1 |
| 800 | 20.7 |
Pathological input from scikit-learn benchmarks:
val y= ((0 until length) ++ (-(length - 1) until length) ++ (-(length - 1) to 0)).toArray.map(_.toDouble)
val x = (1 to y.length).toArray.map(_.toDouble)
Before:
| Input Length | Time (us) |
|-------------:|----------:|
| 40 | 2.2 |
| 80 | 4.7 |
| 160 | 2140.0 |
| 320 | 3,076,508.1 |
After:
| Input Length | Time (us) |
|-------------:|----------:|
| 40 | 5.3 |
| 80 | 10.4 |
| 160 | 21.3 |
| 320 | 41.9 |
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70363/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70214/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70216 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70216/testReport)** for PR 15018 at commit [`e420fb3`](https://github.com/apache/spark/commit/e420fb353c079d8053695ad2b6cf13a52fdf2e05).
* This patch **fails Scala style 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Anyone? @srowen?
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95914074
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -312,90 +313,120 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
/**
- * Performs a pool adjacent violators algorithm (PAV).
- * Uses approach with single processing of data where violators
- * in previously processed data created by pooling are fixed immediately.
- * Uses optimization of discovering monotonicity violating sequences (blocks).
+ * Performs a pool adjacent violators algorithm (PAV). Implements the algorithm originally
+ * described in [1], using the formulation from [2, 3]. Uses an array to keep track of start
+ * and end indices of blocks.
*
- * @param input Input data of tuples (label, feature, weight).
+ * [1] Grotzinger, S. J., and C. Witzgall. "Projections onto order simplexes." Applied
+ * mathematics and Optimization 12.1 (1984): 247-270.
+ *
+ * [2] Best, Michael J., and Nilotpal Chakravarti. "Active set algorithms for isotonic
+ * regression; a unifying framework." Mathematical Programming 47.1-3 (1990): 425-439.
+ *
+ * [3] Best, Michael J., Nilotpal Chakravarti, and Vasant A. Ubhaya. "Minimizing separable convex
+ * functions subject to simple chain constraints." SIAM Journal on Optimization 10.3 (2000):
+ * 658-672.
+ *
+ * @param input Input data of tuples (label, feature, weight). Weights must
+ be non-negative.
* @return Result tuples (label, feature, weight) where labels were updated
* to form a monotone sequence as per isotonic regression definition.
*/
private def poolAdjacentViolators(
input: Array[(Double, Double, Double)]): Array[(Double, Double, Double)] = {
- if (input.isEmpty) {
- return Array.empty
+ val cleanInput = input.flatMap{ case (y, x, weight) =>
+ require(weight >= 0.0, "weights must be non-negative")
+ if (weight == 0.0) {
+ logWarning(s"Dropping zero-weight point ($y, $x, $weight)")
--- End diff --
I disagree about logging for zero-weight points. If an instance has zero weight, then it should be ignored, and that's not a problem.
If we really want to log this, then let's do it once per dataset, not once per row, which could make logs explode. I'd also say we should lower the logging level to logInfo.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71087 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71087/testReport)** for PR 15018 at commit [`e33a308`](https://github.com/apache/spark/commit/e33a3083fc6437bcf5149103e71646f355e84578).
* This patch **fails Spark unit 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the issue:
https://github.com/apache/spark/pull/15018
For the zero-weight values, can we do similar to scikit-learn to remove zero-weight values, like https://github.com/amueller/scikit-learn/commit/2415100f79293bbbf52c12c36d63a6cf602cf3c4
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Looks like the new scikit-learn implementation suffers from a similar problem to the one that the original Spark implementation had. I left them a note pointing it out.
Right now I'm working on implementing what's in "Minimizing Separable Convex Functions Subject to Simple Chain Constraints", by Best, Chakravarti, and Ubhaya. Running down the referecence trail, it looks like the original algorithm is in "Projections onto Order Simplexes" by Grotzinger and Witzgall, and this particular formulation of it is originally in "Active set algorithms for isotonic regression; A unifying framework" by Best and Chakravarti.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
@viirya Better to remove them, or throw an error? Personally, I'd rather be alerted that I'm passing invalid input, rather than have it "fixed" for me.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70886 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70886/testReport)** for PR 15018 at commit [`a119423`](https://github.com/apache/spark/commit/a119423fa769bb6be9cc27e455a82d04360e03b3).
* This patch passes all 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 pull request #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92322282
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
+ j = j + 1
+ }
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
+ // Pool the violating sequence with the data point preceding it
--- End diff --
Is this comment correct? Looks like you pool the violating sequence [i, j] only. The preceding data points are checked for pooling in next outer loop.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70836 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70836/testReport)** for PR 15018 at commit [`47d5b4f`](https://github.com/apache/spark/commit/47d5b4fc58bc40fcec2565185d4a4068219ebb47).
* This patch passes all 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70136/
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70134 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70134/consoleFull)** for PR 15018 at commit [`8d16043`](https://github.com/apache/spark/commit/8d16043b50629f2dc2f96c124189d284c833ddc0).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #3547 has started](https://amplab.cs.berkeley.edu/jenkins/job/NewSparkPullRequestBuilder/3547/testReport)** for PR 15018 at commit [`0aeca09`](https://github.com/apache/spark/commit/0aeca09c0ea234d8a61664f2827abd80d7850c5b).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71087 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71087/testReport)** for PR 15018 at commit [`e33a308`](https://github.com/apache/spark/commit/e33a3083fc6437bcf5149103e71646f355e84578).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92920619
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,68 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
-
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
-
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ /*
+ Keeps track of the start and end indices of the blocks. blockBounds(start) gives the
+ index of the end of the block and blockBounds(end) gives the index of the start of the
--- End diff --
blockBounds(start) is the _end_ of a block? this is reflected in your helper functions below but it seems reversed. Can you double check and elaborate a bit?
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Could someone please take a look at this? @mengxr maybe? Looks like you merged the initial implementation.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Given that the scikit-learn implementation I based this on has changed (https://github.com/scikit-learn/scikit-learn/pull/7444) since I submitted the PR, and @jkbradley has pointed out a reference I hadn't seen, I'd like to take a little bit of time to see if there's yet a better algorithm.
This one is an improvement over what we had, but as long as we're changing it, we may as well get it right.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92428442
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
+ j = j + 1
+ }
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
+ // Pool the violating sequence with the data point preceding it
+ if (input(i)._1 != input(j)._1) {
--- End diff --
Correct. Any violations that are introduced will be fixed in the next iteration.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71092 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71092/testReport)** for PR 15018 at commit [`83480e7`](https://github.com/apache/spark/commit/83480e7ac33d9cf066245f2e8206ed6d765bafb4).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95914179
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -312,90 +313,120 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
/**
- * Performs a pool adjacent violators algorithm (PAV).
- * Uses approach with single processing of data where violators
- * in previously processed data created by pooling are fixed immediately.
- * Uses optimization of discovering monotonicity violating sequences (blocks).
+ * Performs a pool adjacent violators algorithm (PAV). Implements the algorithm originally
+ * described in [1], using the formulation from [2, 3]. Uses an array to keep track of start
+ * and end indices of blocks.
*
- * @param input Input data of tuples (label, feature, weight).
+ * [1] Grotzinger, S. J., and C. Witzgall. "Projections onto order simplexes." Applied
+ * mathematics and Optimization 12.1 (1984): 247-270.
+ *
+ * [2] Best, Michael J., and Nilotpal Chakravarti. "Active set algorithms for isotonic
+ * regression; a unifying framework." Mathematical Programming 47.1-3 (1990): 425-439.
+ *
+ * [3] Best, Michael J., Nilotpal Chakravarti, and Vasant A. Ubhaya. "Minimizing separable convex
+ * functions subject to simple chain constraints." SIAM Journal on Optimization 10.3 (2000):
+ * 658-672.
+ *
+ * @param input Input data of tuples (label, feature, weight). Weights must
+ be non-negative.
* @return Result tuples (label, feature, weight) where labels were updated
* to form a monotone sequence as per isotonic regression definition.
*/
private def poolAdjacentViolators(
input: Array[(Double, Double, Double)]): Array[(Double, Double, Double)] = {
- if (input.isEmpty) {
- return Array.empty
+ val cleanInput = input.flatMap{ case (y, x, weight) =>
+ require(weight >= 0.0, "weights must be non-negative")
--- End diff --
State invalid y,x,weight.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70136 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70136/consoleFull)** for PR 15018 at commit [`9cfa5ed`](https://github.com/apache/spark/commit/9cfa5ed57cbedcb5189d612c74f5c81c4cc0cc0b).
* This patch **fails from timeout after a configured wait of \`250m\`**.
* 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #71329 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/71329/testReport)** for PR 15018 at commit [`0aeca09`](https://github.com/apache/spark/commit/0aeca09c0ea234d8a61664f2827abd80d7850c5b).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r94571308
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,81 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // input(i) to input(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = input.map {
+ case (_, _, weight) if weight == 0d =>
--- End diff --
I'd always write 0.0 instead of 0d for clarity. I also think we want an `IllegalArgumentException`, so maybe:
```
val weights = input.map { case (y, _, weight) =>
require(weight > 0.0)
(weight, weight * y)
}
```
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Merged build finished. Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/15018
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
My thought was that there's nothing in the computation that prevents it (unlike 0 weights, which cause NaNs). Why not err on the side of maximum flexibility to the end user? Just because there's no use case for it now doesn't mean someone won't find one in the future.
Just my 2 cents. I don't feel strongly about it and will defer to commiters.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92331409
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -344,27 +344,30 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ val n = input.length - 1
+ var notFinished = true
+
+ while (notFinished) {
+ i = 0
+ notFinished = false
+
+ // Iterate through the data, fix any monotonicity violations we find
+ // We may need to do this multiple times, as pooling can introduce violations
+ // at locations that were previously fine.
+ while (i < n) {
+ var j = i
+
+ // Find next monotonicity violating sequence, if any.
+ while (j < n && input(j)._1 >= input(j + 1)._1) {
--- End diff --
I think the original one i.e., `input(j)._1 > input(j + 1)._1` is correct. Here it is going to select out-of-order blocks.
Quoted from the paper:
> We refer to two blocks [p, q] and [q + 1, r] as consecutive. We refer to two consecutive blocks [p, q] and [q +1, r] as in-order if theta_pq <= theta_q+1, r and out-of-order otherwise.
LEMMA 1 is pointing the how a merged block is also a single-valued block.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/70364/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r92920879
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,68 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
-
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
-
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ /*
+ Keeps track of the start and end indices of the blocks. blockBounds(start) gives the
+ index of the end of the block and blockBounds(end) gives the index of the start of the
+ block. Entries that are not the start or end of the block are meaningless.
+ */
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
+
+ /*
+ Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ gives the values for the block. Entries that are not at the start of a block
+ are meaningless.
+ */
+ val weights: Array[(Double, Double)] = input.map(x => (x._3, x._3 * x._1)) // (weight, weight * y)
+
+ // a few convenience functions to make the code more readable
+ def blockEnd(start: Int) = blockBounds(start)
+ def blockStart(end: Int) = blockBounds(end)
+ def nextBlock(start: Int) = blockEnd(start) + 1
+ def prevBlock(start: Int) = blockStart(start - 1)
+ def merge(block1: Int, block2: Int): Int = {
+ assert(blockEnd(block1) + 1 == block2, "attempting to merge non-consecutive blocks")
+ blockBounds(block1) = blockEnd(block2)
+ blockBounds(blockEnd(block2)) = block1
+ val w1 = weights(block1)
+ val w2 = weights(block2)
+ weights(block1) = (w1._1 + w2._1, w1._2 + w2._2)
+ block1
}
+ def average(start: Int) = weights(start)._2 / weights(start)._1
+ /*
+ Implement Algorithm PAV from [3].
+ Merge on >= instead of > because it elimnate adjacent blocks with the same average, and we want
+ to compress our output as much as possible. Both give correct results.
+ */
var i = 0
- val len = input.length
- while (i < len) {
- var j = i
-
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
-
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
- pool(input, i, j)
- i = i - 1
+ while (nextBlock(i) < input.length) {
+ if (average(i) >= average(nextBlock(i))) {
+ merge(i, nextBlock(i))
+ while((i > 0) && (average(prevBlock(i)) >= average(i))) {
--- End diff --
Super nit: space before `while` here and below. You can probably nix the extra parens around each of the two terms, but no big deal
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70836 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70836/testReport)** for PR 15018 at commit [`47d5b4f`](https://github.com/apache/spark/commit/47d5b4fc58bc40fcec2565185d4a4068219ebb47).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70363 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70363/testReport)** for PR 15018 at commit [`8762531`](https://github.com/apache/spark/commit/8762531b9c70e21ce047393b252fefe2ed134036).
* This patch **fails Scala style 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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on the issue:
https://github.com/apache/spark/pull/15018
Sorry, I've been on vacation. I'll make the requested changes in the next day or two.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95914526
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -312,90 +313,120 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
}
/**
- * Performs a pool adjacent violators algorithm (PAV).
- * Uses approach with single processing of data where violators
- * in previously processed data created by pooling are fixed immediately.
- * Uses optimization of discovering monotonicity violating sequences (blocks).
+ * Performs a pool adjacent violators algorithm (PAV). Implements the algorithm originally
+ * described in [1], using the formulation from [2, 3]. Uses an array to keep track of start
+ * and end indices of blocks.
*
- * @param input Input data of tuples (label, feature, weight).
+ * [1] Grotzinger, S. J., and C. Witzgall. "Projections onto order simplexes." Applied
+ * mathematics and Optimization 12.1 (1984): 247-270.
+ *
+ * [2] Best, Michael J., and Nilotpal Chakravarti. "Active set algorithms for isotonic
+ * regression; a unifying framework." Mathematical Programming 47.1-3 (1990): 425-439.
+ *
+ * [3] Best, Michael J., Nilotpal Chakravarti, and Vasant A. Ubhaya. "Minimizing separable convex
+ * functions subject to simple chain constraints." SIAM Journal on Optimization 10.3 (2000):
+ * 658-672.
+ *
+ * @param input Input data of tuples (label, feature, weight). Weights must
+ be non-negative.
* @return Result tuples (label, feature, weight) where labels were updated
* to form a monotone sequence as per isotonic regression definition.
*/
private def poolAdjacentViolators(
input: Array[(Double, Double, Double)]): Array[(Double, Double, Double)] = {
- if (input.isEmpty) {
- return Array.empty
+ val cleanInput = input.flatMap{ case (y, x, weight) =>
+ require(weight >= 0.0, "weights must be non-negative")
+ if (weight == 0.0) {
+ logWarning(s"Dropping zero-weight point ($y, $x, $weight)")
+ Array[(Double, Double, Double)]()
+ } else {
+ Array((y, x, weight))
+ }
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
+ if (cleanInput.isEmpty) {
+ return Array.empty
+ }
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // cleanInput(i) to cleanInput(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ // Initially, each data point is its own block.
+ val blockBounds = Array.range(0, cleanInput.length)
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = cleanInput.map { case (y, _, weight) =>
+ (weight, weight * y)
}
- var i = 0
- val len = input.length
- while (i < len) {
- var j = i
+ // a few convenience functions to make the code more readable
- // Find monotonicity violating sequence, if any.
- while (j < len - 1 && input(j)._1 > input(j + 1)._1) {
- j = j + 1
- }
+ // blockStart and blockEnd have identical implementations. We create two different
+ // functions to make the code more expressive
+ def blockEnd(start: Int): Int = blockBounds(start)
+ def blockStart(end: Int): Int = blockBounds(end)
- // If monotonicity was not violated, move to next data point.
- if (i == j) {
- i = i + 1
- } else {
- // Otherwise pool the violating sequence
- // and check if pooling caused monotonicity violation in previously processed points.
- while (i >= 0 && input(i)._1 > input(i + 1)._1) {
- pool(input, i, j)
- i = i - 1
- }
+ // the next block starts at the index after the end of this block
+ def nextBlock(start: Int): Int = blockEnd(start) + 1
- i = j
- }
+ // the previous block ends at the index before the start of this block
+ // we then use blockStart to find the start
+ def prevBlock(start: Int): Int = blockStart(start - 1)
+
+ // Merge two adjacent blocks, updating blockBounds and weights to reflect the merge
+ // Return the start index of the merged block
+ def merge(block1: Int, block2: Int): Int = {
+ assert(
+ blockEnd(block1) + 1 == block2,
+ s"Attempting to merge non-consecutive blocks [${block1}, ${blockEnd(block1)}]" +
+ s" and [${block2}, ${blockEnd(block2)}. This is likely a bug in the isotonic regression" +
--- End diff --
missing "]"
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15018
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/71271/
Test PASSed.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by neggert <gi...@git.apache.org>.
Github user neggert commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r94641912
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,80 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // input(i) to input(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = input.map { case (y, _, weight) =>
+ require(weight != 0.0)
--- End diff --
It's a weird thing to do, but I don't think there's any reason we can't support it. The problem still has a unique solution.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15018
Ping @neggert
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15018
@neggert I'll ask @mengxr about the negative weights since he oversaw the original work here.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70364 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70364/testReport)** for PR 15018 at commit [`d19647b`](https://github.com/apache/spark/commit/d19647b230f3350432b67a5035822cb04d529c9d).
* This patch passes all 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 pull request #15018: [SPARK-17455][MLlib] Improve PAVA implementation ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15018#discussion_r95094551
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/regression/IsotonicRegression.scala ---
@@ -328,74 +336,80 @@ class IsotonicRegression private (private var isotonic: Boolean) extends Seriali
return Array.empty
}
- // Pools sub array within given bounds assigning weighted average value to all elements.
- def pool(input: Array[(Double, Double, Double)], start: Int, end: Int): Unit = {
- val poolSubArray = input.slice(start, end + 1)
- val weightedSum = poolSubArray.map(lp => lp._1 * lp._3).sum
- val weight = poolSubArray.map(_._3).sum
+ // Keeps track of the start and end indices of the blocks. if [i, j] is a valid block from
+ // input(i) to input(j) (inclusive), then blockBounds(i) = j and blockBounds(j) = i
+ val blockBounds = Array.range(0, input.length) // Initially, each data point is its own block
- var i = start
- while (i <= end) {
- input(i) = (weightedSum / weight, input(i)._2, input(i)._3)
- i = i + 1
- }
+ // Keep track of the sum of weights and sum of weight * y for each block. weights(start)
+ // gives the values for the block. Entries that are not at the start of a block
+ // are meaningless.
+ val weights: Array[(Double, Double)] = input.map { case (y, _, weight) =>
+ require(weight != 0.0)
--- End diff --
Please add an informative error message.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15018
Just add commits here.
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #65117 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/65117/consoleFull)** for PR 15018 at commit [`5608ae1`](https://github.com/apache/spark/commit/5608ae1f4c9089dd3a299eef14af59bed6c96192).
---
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 #15018: [SPARK-17455][MLlib] Improve PAVA implementation in Isot...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15018
**[Test build #70216 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/70216/testReport)** for PR 15018 at commit [`e420fb3`](https://github.com/apache/spark/commit/e420fb353c079d8053695ad2b6cf13a52fdf2e05).
---
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