{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/3519","labels_url":"https://api.github.com/repos/apache/spark/issues/3519/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/3519/comments","events_url":"https://api.github.com/repos/apache/spark/issues/3519/events","html_url":"https://github.com/apache/spark/pull/3519","id":50475211,"number":3519,"title":"[MLLIB][SPARK-3278] Monotone (Isotonic) regression using parallel pool adjacent violators algorithm","user":{"login":"zapletal-martin","id":6018812,"avatar_url":"https://avatars.githubusercontent.com/u/6018812?v=3","gravatar_id":"","url":"https://api.github.com/users/zapletal-martin","html_url":"https://github.com/zapletal-martin","followers_url":"https://api.github.com/users/zapletal-martin/followers","following_url":"https://api.github.com/users/zapletal-martin/following{/other_user}","gists_url":"https://api.github.com/users/zapletal-martin/gists{/gist_id}","starred_url":"https://api.github.com/users/zapletal-martin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zapletal-martin/subscriptions","organizations_url":"https://api.github.com/users/zapletal-martin/orgs","repos_url":"https://api.github.com/users/zapletal-martin/repos","events_url":"https://api.github.com/users/zapletal-martin/events{/privacy}","received_events_url":"https://api.github.com/users/zapletal-martin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":43,"created_at":"2014-11-30T23:24:52Z","updated_at":"2015-01-30T13:12:06Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/3519","html_url":"https://github.com/apache/spark/pull/3519","diff_url":"https://github.com/apache/spark/pull/3519.diff","patch_url":"https://github.com/apache/spark/pull/3519.patch"},"body":"This PR introduces an API for Isotonic regression and one algorithm implementing it, Pool adjacent violators. \r\n\r\nThe Isotonic regression problem is sufficiently described in [Floudas, Pardalos, Encyclopedia of Optimization](http://books.google.co.uk/books?id=gtoTkL7heS0C&pg=RA2-PA87&lpg=RA2-PA87&dq=pooled+adjacent+violators+code&source=bl&ots=ZzQbZXVJnn&sig=reH_hBV6yIb9BeZNTF9092vD8PY&hl=en&sa=X&ei=WmF2VLiOIZLO7Qa-t4Bo&ved=0CD8Q6AEwBA#v=onepage&q&f=false), [Wikipedia](http://en.wikipedia.org/wiki/Isotonic_regression) or [Stat Wiki](http://stat.wikia.com/wiki/Isotonic_regression).\r\n\r\nPool adjacent violators was introduced by  M. Ayer et al. in 1955.  A history and development of isotonic regression algorithms is in [Leeuw, Hornik, Mair, Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods](http://www.jstatsoft.org/v32/i05/paper) and list of available algorithms including their complexity is listed in [Stout, Fastest Isotonic Regression Algorithms](http://web.eecs.umich.edu/~qstout/IsoRegAlg_140812.pdf). \r\n\r\nAn approach to parallelize the computation of PAV was presented in [Kearsley, Tapia, Trosset, An Approach to Parallelizing Isotonic Regression](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR96640.pdf). \r\n\r\nThe implemented Pool adjacent violators algorithm is based on  [Floudas, Pardalos, Encyclopedia of Optimization](http://books.google.co.uk/books?id=gtoTkL7heS0C&pg=RA2-PA87&lpg=RA2-PA87&dq=pooled+adjacent+violators+code&source=bl&ots=ZzQbZXVJnn&sig=reH_hBV6yIb9BeZNTF9092vD8PY&hl=en&sa=X&ei=WmF2VLiOIZLO7Qa-t4Bo&ved=0CD8Q6AEwBA#v=onepage&q&f=false) (Chapter Isotonic regression problems, p. 86) and  [Leeuw, Hornik, Mair, Isotone Optimization in R: Pool-Adjacent-Violators Algorithm (PAVA) and Active Set Methods](http://www.jstatsoft.org/v32/i05/paper), also nicely formulated in [Tibshirani,  Hoefling, Tibshirani, Nearly-Isotonic Regression](http://www.stat.cmu.edu/~ryantibs/papers/neariso.pdf). Implementation itself inspired by R implementations [Klaus, Strimmer, 2008, fdrtool: Estimation of (Local) False Discovery Rates and Higher Criticism](http://cran.r-project.org/web/packages/fdrtool/index.html) and [R Development Core Team, stats, 2009](https://github.com/lgautier/R-3-0-branch-alt/blob/master/src/library/stats/R/isoreg.R). I ran tests with both these libraries and confirmed they yield the same results. More R implementations referenced in aforementioned [Leeuw, Hornik, Mair, Isotone Optimization in R: Pool-Adjacent-Violators\r\nAlgorithm (PAVA) and Active Set Methods](http://www.jstatsoft.org/v32/i05/paper). The implementation is also inspired and cross checked with other implementations: [Ted Harding, 2007](https://stat.ethz.ch/pipermail/r-help/2007-March/127981.html), [scikit-learn](https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/_isotonic.pyx), [Andrew Tulloch, 2014, Julia](https://github.com/ajtulloch/Isotonic.jl/blob/master/src/pooled_pava.jl), [Andrew Tulloch, 2014, c++](https://gist.github.com/ajtulloch/9499872), described in [Andrew Tulloch, Speeding up isotonic regression in scikit-learn by 5,000x](http://tullo.ch/articles/speeding-up-isotonic-regression/), [Fabian Pedregosa, 2012](https://gist.github.com/fabianp/3081831), [Sreangsu Acharyya. libpav](https://bitbucket.org/sreangsu/libpav/src/f744bc1b0fea257f0cacaead1c922eab201ba91b/src/pav.h?at=default) and [Gustav Larsson](https://gist.github.com/gustavla/9499068)."},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/72198487","html_url":"https://github.com/apache/spark/pull/3519#issuecomment-72198487","issue_url":"https://api.github.com/repos/apache/spark/issues/3519","id":72198487,"user":{"login":"AmplabJenkins","id":4031291,"avatar_url":"https://avatars.githubusercontent.com/u/4031291?v=3","gravatar_id":"","url":"https://api.github.com/users/AmplabJenkins","html_url":"https://github.com/AmplabJenkins","followers_url":"https://api.github.com/users/AmplabJenkins/followers","following_url":"https://api.github.com/users/AmplabJenkins/following{/other_user}","gists_url":"https://api.github.com/users/AmplabJenkins/gists{/gist_id}","starred_url":"https://api.github.com/users/AmplabJenkins/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AmplabJenkins/subscriptions","organizations_url":"https://api.github.com/users/AmplabJenkins/orgs","repos_url":"https://api.github.com/users/AmplabJenkins/repos","events_url":"https://api.github.com/users/AmplabJenkins/events{/privacy}","received_events_url":"https://api.github.com/users/AmplabJenkins/received_events","type":"User","site_admin":false},"created_at":"2015-01-30T13:12:06Z","updated_at":"2015-01-30T13:12:06Z","body":"Test FAILed.\nRefer to this link for build results (access rights to CI server needed): \nhttps://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/26400/\nTest FAILed."}}