{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/64452968","id":64452968,"diff_hunk":"@@ -4,10 +4,85 @@ title: Advanced topics - spark.ml\n displayTitle: Advanced topics - spark.ml\n ---\n \n-# Optimization of linear methods\n+* Table of contents\n+{:toc}\n+\n+`\\[\n+\\newcommand{\\R}{\\mathbb{R}}\n+\\newcommand{\\E}{\\mathbb{E}} \n+\\newcommand{\\x}{\\mathbf{x}}\n+\\newcommand{\\y}{\\mathbf{y}}\n+\\newcommand{\\wv}{\\mathbf{w}}\n+\\newcommand{\\av}{\\mathbf{\\alpha}}\n+\\newcommand{\\bv}{\\mathbf{b}}\n+\\newcommand{\\N}{\\mathbb{N}}\n+\\newcommand{\\id}{\\mathbf{I}} \n+\\newcommand{\\ind}{\\mathbf{1}} \n+\\newcommand{\\0}{\\mathbf{0}} \n+\\newcommand{\\unit}{\\mathbf{e}} \n+\\newcommand{\\one}{\\mathbf{1}} \n+\\newcommand{\\zero}{\\mathbf{0}}\n+\\]`\n+\n+# Optimization of linear methods (developer)\n+\n+## Limited-memory BFGS (L-BFGS)\n+[L-BFGS](http://en.wikipedia.org/wiki/Limited-memory_BFGS) is an optimization \n+algorithm in the family of quasi-Newton methods to solve the optimization problems of the form \n+`$\\min_{\\wv \\in\\R^d} \\; f(\\wv)$`. The L-BFGS method approximates the objective function locally as a \n+quadratic without evaluating the second partial derivatives of the objective function to construct the \n+Hessian matrix. The Hessian matrix is approximated by previous gradient evaluations, so there is no \n+vertical scalability issue (the number of training features) unlike computing the Hessian matrix \n+explicitly in Newton's method. As a result, L-BFGS often achieves faster convergence compared with \n+other first-order optimizations.\n \n-The optimization algorithm underlying the implementation is called\n [Orthant-Wise Limited-memory\n QuasiNewton](http://research-srv.microsoft.com/en-us/um/people/jfgao/paper/icml07scalable.pdf)\n-(OWL-QN). It is an extension of L-BFGS that can effectively handle L1\n-regularization and elastic net.\n+(OWL-QN) is an extension of L-BFGS that can effectively handle L1 regularization and elastic net.\n+\n+L-BFGS is used as a solver for [LinearRegression](api/scala/index.html#org.apache.spark.ml.regression.LinearRegression),\n+[LogisticRegression](api/scala/index.html#org.apache.spark.ml.classification.LogisticRegression),\n+[AFTSurvivalRegression](api/scala/index.html#org.apache.spark.ml.regression.AFTSurvivalRegression)\n+and [MultilayerPerceptronClassifier](api/scala/index.html#org.apache.spark.ml.classification.MultilayerPerceptronClassifier).\n+\n+MLlib L-BFGS solver calls the corresponding implementation in [breeze](https://github.com/scalanlp/breeze/blob/master/math/src/main/scala/breeze/optimize/LBFGS.scala).\n+\n+## Normal equation solver for weighted least squares (normal)\n+\n+MLlib implements normal equation solver for [weighted least squares](https://en.wikipedia.org/wiki/Least_squares#Weighted_least_squares) by [WeightedLeastSquares](https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/ml/optim/WeightedLeastSquares.scala).\n+\n+Given $n$ weighted observations $(w_i, a_i, b_i)$:\n+\n+* $w_i$ the weight of i-th observation\n+* $a_i$ the features vector of i-th observation\n+* $b_i$ the label of i-th observation\n+\n+The number of features for each observation is $m$. We use the following weighted least squares formulation:\n+`\\[   \n+minimize_{x}\\frac{1}{2} \\sum_{i=1}^n \\frac{w_i(a_i^T x -b_i)^2}{\\sum_{i=1}^n w_i} + \\frac{1}{2}\\frac{\\lambda}{\\delta}\\sum_{j=1}^m(\\sigma_{j} x_{j})^2\n+\\]`\n+where $\\lambda$ is the regularization parameter, $\\delta$ is the population standard deviation of label\n+and $\\sigma_j$ is the population standard deviation of the j-th feature column.\n+\n+This objective function has an analytic solution and it requires only one pass over the data to collect necessary statistics to solve.\n+Unlike the original dataset which can only be stored in distributed system,\n+these statistics can be easily loaded into memory on a single machine, and then we can solve the objective function through Cholesky factorization on the driver.\n+\n+WeightedLeastSquares only supports L2 regularization and provides options to enable or disable regularization, standardizing features and labels.\n+In order to take the normal equation approach efficiently, WeightedLeastSquares requires that the number of features be no more than 4096. For larger problems, use L-BFGS instead.","path":"docs/ml-advanced.md","position":73,"original_position":73,"commit_id":"7f80d781ab2a4094f46f6eb322879ef4506f8ac0","original_commit_id":"7f80d781ab2a4094f46f6eb322879ef4506f8ac0","user":{"login":"sethah","id":7275795,"avatar_url":"https://avatars.githubusercontent.com/u/7275795?v=3","gravatar_id":"","url":"https://api.github.com/users/sethah","html_url":"https://github.com/sethah","followers_url":"https://api.github.com/users/sethah/followers","following_url":"https://api.github.com/users/sethah/following{/other_user}","gists_url":"https://api.github.com/users/sethah/gists{/gist_id}","starred_url":"https://api.github.com/users/sethah/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sethah/subscriptions","organizations_url":"https://api.github.com/users/sethah/orgs","repos_url":"https://api.github.com/users/sethah/repos","events_url":"https://api.github.com/users/sethah/events{/privacy}","received_events_url":"https://api.github.com/users/sethah/received_events","type":"User","site_admin":false},"body":"Does it make sense to direct readers to \"use L-BFGS\" instead? Spark doesn't expose an L-BFGS api nor does it even expose the normal equation solver to users. ","created_at":"2016-05-24T18:54:02Z","updated_at":"2016-05-24T18:54:02Z","html_url":"https://github.com/apache/spark/pull/13262#discussion_r64452968","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/13262","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/64452968"},"html":{"href":"https://github.com/apache/spark/pull/13262#discussion_r64452968"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/13262"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/13262","id":71062852,"html_url":"https://github.com/apache/spark/pull/13262","diff_url":"https://github.com/apache/spark/pull/13262.diff","patch_url":"https://github.com/apache/spark/pull/13262.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/13262","number":13262,"state":"open","locked":false,"title":"[SPARK-11959] [SPARK-15484] [Doc] [ML] Document WLS and IRLS","user":{"login":"yanboliang","id":1962026,"avatar_url":"https://avatars.githubusercontent.com/u/1962026?v=3","gravatar_id":"","url":"https://api.github.com/users/yanboliang","html_url":"https://github.com/yanboliang","followers_url":"https://api.github.com/users/yanboliang/followers","following_url":"https://api.github.com/users/yanboliang/following{/other_user}","gists_url":"https://api.github.com/users/yanboliang/gists{/gist_id}","starred_url":"https://api.github.com/users/yanboliang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yanboliang/subscriptions","organizations_url":"https://api.github.com/users/yanboliang/orgs","repos_url":"https://api.github.com/users/yanboliang/repos","events_url":"https://api.github.com/users/yanboliang/events{/privacy}","received_events_url":"https://api.github.com/users/yanboliang/received_events","type":"User","site_admin":false},"body":"## What changes were proposed in this pull request?\r\n* Document ```WeightedLeastSquares```(normal equation) and ```IterativelyReweightedLeastSquares```.\r\n* Copy ```L-BFGS``` documents from ```spark.mllib``` to ```spark.ml```.\r\n\r\nDue to the session ```Optimization of linear methods``` is used for developers, I think we should provide the brief introduction of the optimization method, necessary references and how it implements in Spark. It's not necessary to paste all mathematical formula and derivation here. If developers/users want to learn more, they can track reference. \r\n\r\n## How was this patch tested?\r\nDocument update, no tests.","created_at":"2016-05-23T13:40:57Z","updated_at":"2016-05-24T18:54:02Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6a9b4940bdebfa622b6953c62ff78caec2cc3d87","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/13262/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/13262/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/13262/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/7f80d781ab2a4094f46f6eb322879ef4506f8ac0","head":{"label":"yanboliang:spark-15484","ref":"spark-15484","sha":"7f80d781ab2a4094f46f6eb322879ef4506f8ac0","user":{"login":"yanboliang","id":1962026,"avatar_url":"https://avatars.githubusercontent.com/u/1962026?v=3","gravatar_id":"","url":"https://api.github.com/users/yanboliang","html_url":"https://github.com/yanboliang","followers_url":"https://api.github.com/users/yanboliang/followers","following_url":"https://api.github.com/users/yanboliang/following{/other_user}","gists_url":"https://api.github.com/users/yanboliang/gists{/gist_id}","starred_url":"https://api.github.com/users/yanboliang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yanboliang/subscriptions","organizations_url":"https://api.github.com/users/yanboliang/orgs","repos_url":"https://api.github.com/users/yanboliang/repos","events_url":"https://api.github.com/users/yanboliang/events{/privacy}","received_events_url":"https://api.github.com/users/yanboliang/received_events","type":"User","site_admin":false},"repo":{"id":21890948,"name":"spark","full_name":"yanboliang/spark","owner":{"login":"yanboliang","id":1962026,"avatar_url":"https://avatars.githubusercontent.com/u/1962026?v=3","gravatar_id":"","url":"https://api.github.com/users/yanboliang","html_url":"https://github.com/yanboliang","followers_url":"https://api.github.com/users/yanboliang/followers","following_url":"https://api.github.com/users/yanboliang/following{/other_user}","gists_url":"https://api.github.com/users/yanboliang/gists{/gist_id}","starred_url":"https://api.github.com/users/yanboliang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yanboliang/subscriptions","organizations_url":"https://api.github.com/users/yanboliang/orgs","repos_url":"https://api.github.com/users/yanboliang/repos","events_url":"https://api.github.com/users/yanboliang/events{/privacy}","received_events_url":"https://api.github.com/users/yanboliang/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/yanboliang/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/yanboliang/spark","forks_url":"https://api.github.com/repos/yanboliang/spark/forks","keys_url":"https://api.github.com/repos/yanboliang/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/yanboliang/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/yanboliang/spark/teams","hooks_url":"https://api.github.com/repos/yanboliang/spark/hooks","issue_events_url":"https://api.github.com/repos/yanboliang/spark/issues/events{/number}","events_url":"https://api.github.com/repos/yanboliang/spark/events","assignees_url":"https://api.github.com/repos/yanboliang/spark/assignees{/user}","branches_url":"https://api.github.com/repos/yanboliang/spark/branches{/branch}","tags_url":"https://api.github.com/repos/yanboliang/spark/tags","blobs_url":"https://api.github.com/repos/yanboliang/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/yanboliang/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/yanboliang/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/yanboliang/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/yanboliang/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/yanboliang/spark/languages","stargazers_url":"https://api.github.com/repos/yanboliang/spark/stargazers","contributors_url":"https://api.github.com/repos/yanboliang/spark/contributors","subscribers_url":"https://api.github.com/repos/yanboliang/spark/subscribers","subscription_url":"https://api.github.com/repos/yanboliang/spark/subscription","commits_url":"https://api.github.com/repos/yanboliang/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/yanboliang/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/yanboliang/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/yanboliang/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/yanboliang/spark/contents/{+path}","compare_url":"https://api.github.com/repos/yanboliang/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/yanboliang/spark/merges","archive_url":"https://api.github.com/repos/yanboliang/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/yanboliang/spark/downloads","issues_url":"https://api.github.com/repos/yanboliang/spark/issues{/number}","pulls_url":"https://api.github.com/repos/yanboliang/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/yanboliang/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/yanboliang/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/yanboliang/spark/labels{/name}","releases_url":"https://api.github.com/repos/yanboliang/spark/releases{/id}","deployments_url":"https://api.github.com/repos/yanboliang/spark/deployments","created_at":"2014-07-16T07:24:13Z","updated_at":"2016-04-08T13:35:05Z","pushed_at":"2016-05-24T15:25:45Z","git_url":"git://github.com/yanboliang/spark.git","ssh_url":"git@github.com:yanboliang/spark.git","clone_url":"https://github.com/yanboliang/spark.git","svn_url":"https://github.com/yanboliang/spark","homepage":null,"size":168847,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"dafcb05c2ef8e09f45edfb7eabf58116c23975a0","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","deployments_url":"https://api.github.com/repos/apache/spark/deployments","created_at":"2014-02-25T08:00:08Z","updated_at":"2016-05-24T17:39:15Z","pushed_at":"2016-05-24T18:53:29Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":496527,"stargazers_count":8640,"watchers_count":8640,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":8033,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":408,"forks":8033,"open_issues":408,"watchers":8640,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/13262"},"html":{"href":"https://github.com/apache/spark/pull/13262"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/13262"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/13262/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/13262/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/13262/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/7f80d781ab2a4094f46f6eb322879ef4506f8ac0"}}}}
{"actor":{"display_login":"sethah"}}