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 <nicholas.egg...@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 infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org
