| |
| <!DOCTYPE html> |
| <!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]--> |
| <!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]--> |
| <!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]--> |
| <!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]--> |
| <head> |
| <meta charset="utf-8"> |
| <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> |
| <title>Advanced topics - Spark 2.2.2 Documentation</title> |
| |
| |
| |
| |
| <link rel="stylesheet" href="css/bootstrap.min.css"> |
| <style> |
| body { |
| padding-top: 60px; |
| padding-bottom: 40px; |
| } |
| </style> |
| <meta name="viewport" content="width=device-width"> |
| <link rel="stylesheet" href="css/bootstrap-responsive.min.css"> |
| <link rel="stylesheet" href="css/main.css"> |
| |
| <script src="js/vendor/modernizr-2.6.1-respond-1.1.0.min.js"></script> |
| |
| <link rel="stylesheet" href="css/pygments-default.css"> |
| |
| |
| <!-- Google analytics script --> |
| <script type="text/javascript"> |
| var _gaq = _gaq || []; |
| _gaq.push(['_setAccount', 'UA-32518208-2']); |
| _gaq.push(['_trackPageview']); |
| |
| (function() { |
| var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; |
| ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; |
| var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); |
| })(); |
| </script> |
| |
| |
| </head> |
| <body> |
| <!--[if lt IE 7]> |
| <p class="chromeframe">You are using an outdated browser. <a href="http://browsehappy.com/">Upgrade your browser today</a> or <a href="http://www.google.com/chromeframe/?redirect=true">install Google Chrome Frame</a> to better experience this site.</p> |
| <![endif]--> |
| |
| <!-- This code is taken from http://twitter.github.com/bootstrap/examples/hero.html --> |
| |
| <div class="navbar navbar-fixed-top" id="topbar"> |
| <div class="navbar-inner"> |
| <div class="container"> |
| <div class="brand"><a href="index.html"> |
| <img src="img/spark-logo-hd.png" style="height:50px;"/></a><span class="version">2.2.2</span> |
| </div> |
| <ul class="nav"> |
| <!--TODO(andyk): Add class="active" attribute to li some how.--> |
| <li><a href="index.html">Overview</a></li> |
| |
| <li class="dropdown"> |
| <a href="#" class="dropdown-toggle" data-toggle="dropdown">Programming Guides<b class="caret"></b></a> |
| <ul class="dropdown-menu"> |
| <li><a href="quick-start.html">Quick Start</a></li> |
| <li><a href="rdd-programming-guide.html">RDDs, Accumulators, Broadcasts Vars</a></li> |
| <li><a href="sql-programming-guide.html">SQL, DataFrames, and Datasets</a></li> |
| <li><a href="structured-streaming-programming-guide.html">Structured Streaming</a></li> |
| <li><a href="streaming-programming-guide.html">Spark Streaming (DStreams)</a></li> |
| <li><a href="ml-guide.html">MLlib (Machine Learning)</a></li> |
| <li><a href="graphx-programming-guide.html">GraphX (Graph Processing)</a></li> |
| <li><a href="sparkr.html">SparkR (R on Spark)</a></li> |
| </ul> |
| </li> |
| |
| <li class="dropdown"> |
| <a href="#" class="dropdown-toggle" data-toggle="dropdown">API Docs<b class="caret"></b></a> |
| <ul class="dropdown-menu"> |
| <li><a href="api/scala/index.html#org.apache.spark.package">Scala</a></li> |
| <li><a href="api/java/index.html">Java</a></li> |
| <li><a href="api/python/index.html">Python</a></li> |
| <li><a href="api/R/index.html">R</a></li> |
| </ul> |
| </li> |
| |
| <li class="dropdown"> |
| <a href="#" class="dropdown-toggle" data-toggle="dropdown">Deploying<b class="caret"></b></a> |
| <ul class="dropdown-menu"> |
| <li><a href="cluster-overview.html">Overview</a></li> |
| <li><a href="submitting-applications.html">Submitting Applications</a></li> |
| <li class="divider"></li> |
| <li><a href="spark-standalone.html">Spark Standalone</a></li> |
| <li><a href="running-on-mesos.html">Mesos</a></li> |
| <li><a href="running-on-yarn.html">YARN</a></li> |
| </ul> |
| </li> |
| |
| <li class="dropdown"> |
| <a href="api.html" class="dropdown-toggle" data-toggle="dropdown">More<b class="caret"></b></a> |
| <ul class="dropdown-menu"> |
| <li><a href="configuration.html">Configuration</a></li> |
| <li><a href="monitoring.html">Monitoring</a></li> |
| <li><a href="tuning.html">Tuning Guide</a></li> |
| <li><a href="job-scheduling.html">Job Scheduling</a></li> |
| <li><a href="security.html">Security</a></li> |
| <li><a href="hardware-provisioning.html">Hardware Provisioning</a></li> |
| <li class="divider"></li> |
| <li><a href="building-spark.html">Building Spark</a></li> |
| <li><a href="http://spark.apache.org/contributing.html">Contributing to Spark</a></li> |
| <li><a href="http://spark.apache.org/third-party-projects.html">Third Party Projects</a></li> |
| </ul> |
| </li> |
| </ul> |
| <!--<p class="navbar-text pull-right"><span class="version-text">v2.2.2</span></p>--> |
| </div> |
| </div> |
| </div> |
| |
| <div class="container-wrapper"> |
| |
| |
| <div class="left-menu-wrapper"> |
| <div class="left-menu"> |
| <h3><a href="ml-guide.html">MLlib: Main Guide</a></h3> |
| |
| <ul> |
| |
| <li> |
| <a href="ml-statistics.html"> |
| |
| Basic statistics |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-pipeline.html"> |
| |
| Pipelines |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-features.html"> |
| |
| Extracting, transforming and selecting features |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-classification-regression.html"> |
| |
| Classification and Regression |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-clustering.html"> |
| |
| Clustering |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-collaborative-filtering.html"> |
| |
| Collaborative filtering |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-frequent-pattern-mining.html"> |
| |
| Frequent Pattern Mining |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-tuning.html"> |
| |
| Model selection and tuning |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="ml-advanced.html"> |
| |
| <b>Advanced topics</b> |
| |
| </a> |
| </li> |
| |
| |
| </ul> |
| |
| <h3><a href="mllib-guide.html">MLlib: RDD-based API Guide</a></h3> |
| |
| <ul> |
| |
| <li> |
| <a href="mllib-data-types.html"> |
| |
| Data types |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-statistics.html"> |
| |
| Basic statistics |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-classification-regression.html"> |
| |
| Classification and regression |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-collaborative-filtering.html"> |
| |
| Collaborative filtering |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-clustering.html"> |
| |
| Clustering |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-dimensionality-reduction.html"> |
| |
| Dimensionality reduction |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-feature-extraction.html"> |
| |
| Feature extraction and transformation |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-frequent-pattern-mining.html"> |
| |
| Frequent pattern mining |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-evaluation-metrics.html"> |
| |
| Evaluation metrics |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-pmml-model-export.html"> |
| |
| PMML model export |
| |
| </a> |
| </li> |
| |
| |
| <li> |
| <a href="mllib-optimization.html"> |
| |
| Optimization (developer) |
| |
| </a> |
| </li> |
| |
| |
| </ul> |
| |
| </div> |
| </div> |
| <input id="nav-trigger" class="nav-trigger" checked type="checkbox"> |
| <label for="nav-trigger"></label> |
| <div class="content-with-sidebar" id="content"> |
| |
| <h1 class="title">Advanced topics</h1> |
| |
| |
| <ul id="markdown-toc"> |
| <li><a href="#optimization-of-linear-methods-developer" id="markdown-toc-optimization-of-linear-methods-developer">Optimization of linear methods (developer)</a> <ul> |
| <li><a href="#limited-memory-bfgs-l-bfgs" id="markdown-toc-limited-memory-bfgs-l-bfgs">Limited-memory BFGS (L-BFGS)</a></li> |
| <li><a href="#normal-equation-solver-for-weighted-least-squares" id="markdown-toc-normal-equation-solver-for-weighted-least-squares">Normal equation solver for weighted least squares</a></li> |
| <li><a href="#iteratively-reweighted-least-squares-irls" id="markdown-toc-iteratively-reweighted-least-squares-irls">Iteratively reweighted least squares (IRLS)</a></li> |
| </ul> |
| </li> |
| </ul> |
| |
| <p><code>\[ |
| \newcommand{\R}{\mathbb{R}} |
| \newcommand{\E}{\mathbb{E}} |
| \newcommand{\x}{\mathbf{x}} |
| \newcommand{\y}{\mathbf{y}} |
| \newcommand{\wv}{\mathbf{w}} |
| \newcommand{\av}{\mathbf{\alpha}} |
| \newcommand{\bv}{\mathbf{b}} |
| \newcommand{\N}{\mathbb{N}} |
| \newcommand{\id}{\mathbf{I}} |
| \newcommand{\ind}{\mathbf{1}} |
| \newcommand{\0}{\mathbf{0}} |
| \newcommand{\unit}{\mathbf{e}} |
| \newcommand{\one}{\mathbf{1}} |
| \newcommand{\zero}{\mathbf{0}} |
| \]</code></p> |
| |
| <h1 id="optimization-of-linear-methods-developer">Optimization of linear methods (developer)</h1> |
| |
| <h2 id="limited-memory-bfgs-l-bfgs">Limited-memory BFGS (L-BFGS)</h2> |
| <p><a href="http://en.wikipedia.org/wiki/Limited-memory_BFGS">L-BFGS</a> is an optimization |
| algorithm in the family of quasi-Newton methods to solve the optimization problems of the form |
| <code>$\min_{\wv \in\R^d} \; f(\wv)$</code>. The L-BFGS method approximates the objective function locally as a |
| quadratic without evaluating the second partial derivatives of the objective function to construct the |
| Hessian matrix. The Hessian matrix is approximated by previous gradient evaluations, so there is no |
| vertical scalability issue (the number of training features) unlike computing the Hessian matrix |
| explicitly in Newton’s method. As a result, L-BFGS often achieves faster convergence compared with |
| other first-order optimizations.</p> |
| |
| <p><a href="http://research-srv.microsoft.com/en-us/um/people/jfgao/paper/icml07scalable.pdf">Orthant-Wise Limited-memory |
| Quasi-Newton</a> |
| (OWL-QN) is an extension of L-BFGS that can effectively handle L1 and elastic net regularization.</p> |
| |
| <p>L-BFGS is used as a solver for <a href="api/scala/index.html#org.apache.spark.ml.regression.LinearRegression">LinearRegression</a>, |
| <a href="api/scala/index.html#org.apache.spark.ml.classification.LogisticRegression">LogisticRegression</a>, |
| <a href="api/scala/index.html#org.apache.spark.ml.regression.AFTSurvivalRegression">AFTSurvivalRegression</a> |
| and <a href="api/scala/index.html#org.apache.spark.ml.classification.MultilayerPerceptronClassifier">MultilayerPerceptronClassifier</a>.</p> |
| |
| <p>MLlib L-BFGS solver calls the corresponding implementation in <a href="https://github.com/scalanlp/breeze/blob/master/math/src/main/scala/breeze/optimize/LBFGS.scala">breeze</a>.</p> |
| |
| <h2 id="normal-equation-solver-for-weighted-least-squares">Normal equation solver for weighted least squares</h2> |
| |
| <p>MLlib implements normal equation solver for <a href="https://en.wikipedia.org/wiki/Least_squares#Weighted_least_squares">weighted least squares</a> by <a href="https://github.com/apache/spark/blob/v2.2.2/mllib/src/main/scala/org/apache/spark/ml/optim/WeightedLeastSquares.scala">WeightedLeastSquares</a>.</p> |
| |
| <p>Given $n$ weighted observations $(w_i, a_i, b_i)$:</p> |
| |
| <ul> |
| <li>$w_i$ the weight of i-th observation</li> |
| <li>$a_i$ the features vector of i-th observation</li> |
| <li>$b_i$ the label of i-th observation</li> |
| </ul> |
| |
| <p>The number of features for each observation is $m$. We use the following weighted least squares formulation: |
| <code>\[ |
| \min_{\mathbf{x}}\frac{1}{2} \sum_{i=1}^n \frac{w_i(\mathbf{a}_i^T \mathbf{x} -b_i)^2}{\sum_{k=1}^n w_k} + \frac{\lambda}{\delta}\left[\frac{1}{2}(1 - \alpha)\sum_{j=1}^m(\sigma_j x_j)^2 + \alpha\sum_{j=1}^m |\sigma_j x_j|\right] |
| \]</code> |
| where $\lambda$ is the regularization parameter, $\alpha$ is the elastic-net mixing parameter, $\delta$ is the population standard deviation of the label |
| and $\sigma_j$ is the population standard deviation of the j-th feature column.</p> |
| |
| <p>This objective function requires only one pass over the data to collect the statistics necessary to solve it. For an |
| $n \times m$ data matrix, these statistics require only $O(m^2)$ storage and so can be stored on a single machine when $m$ (the number of features) is |
| relatively small. We can then solve the normal equations on a single machine using local methods like direct Cholesky factorization or iterative optimization programs.</p> |
| |
| <p>Spark MLlib currently supports two types of solvers for the normal equations: Cholesky factorization and Quasi-Newton methods (L-BFGS/OWL-QN). Cholesky factorization |
| depends on a positive definite covariance matrix (i.e. columns of the data matrix must be linearly independent) and will fail if this condition is violated. Quasi-Newton methods |
| are still capable of providing a reasonable solution even when the covariance matrix is not positive definite, so the normal equation solver can also fall back to |
| Quasi-Newton methods in this case. This fallback is currently always enabled for the <code>LinearRegression</code> and <code>GeneralizedLinearRegression</code> estimators.</p> |
| |
| <p><code>WeightedLeastSquares</code> supports L1, L2, and elastic-net regularization and provides options to enable or disable regularization and standardization. In the case where no |
| L1 regularization is applied (i.e. $\alpha = 0$), there exists an analytical solution and either Cholesky or Quasi-Newton solver may be used. When $\alpha > 0$ no analytical |
| solution exists and we instead use the Quasi-Newton solver to find the coefficients iteratively.</p> |
| |
| <p>In order to make the normal equation approach efficient, <code>WeightedLeastSquares</code> requires that the number of features be no more than 4096. For larger problems, use L-BFGS instead.</p> |
| |
| <h2 id="iteratively-reweighted-least-squares-irls">Iteratively reweighted least squares (IRLS)</h2> |
| |
| <p>MLlib implements <a href="https://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares">iteratively reweighted least squares (IRLS)</a> by <a href="https://github.com/apache/spark/blob/v2.2.2/mllib/src/main/scala/org/apache/spark/ml/optim/IterativelyReweightedLeastSquares.scala">IterativelyReweightedLeastSquares</a>. |
| It can be used to find the maximum likelihood estimates of a generalized linear model (GLM), find M-estimator in robust regression and other optimization problems. |
| Refer to <a href="http://www.jstor.org/stable/2345503">Iteratively Reweighted Least Squares for Maximum Likelihood Estimation, and some Robust and Resistant Alternatives</a> for more information.</p> |
| |
| <p>It solves certain optimization problems iteratively through the following procedure:</p> |
| |
| <ul> |
| <li>linearize the objective at current solution and update corresponding weight.</li> |
| <li>solve a weighted least squares (WLS) problem by WeightedLeastSquares.</li> |
| <li>repeat above steps until convergence.</li> |
| </ul> |
| |
| <p>Since it involves solving a weighted least squares (WLS) problem by <code>WeightedLeastSquares</code> in each iteration, |
| it also requires the number of features to be no more than 4096. |
| Currently IRLS is used as the default solver of <a href="api/scala/index.html#org.apache.spark.ml.regression.GeneralizedLinearRegression">GeneralizedLinearRegression</a>.</p> |
| |
| |
| </div> |
| |
| <!-- /container --> |
| </div> |
| |
| <script src="js/vendor/jquery-1.8.0.min.js"></script> |
| <script src="js/vendor/bootstrap.min.js"></script> |
| <script src="js/vendor/anchor.min.js"></script> |
| <script src="js/main.js"></script> |
| |
| <!-- MathJax Section --> |
| <script type="text/x-mathjax-config"> |
| MathJax.Hub.Config({ |
| TeX: { equationNumbers: { autoNumber: "AMS" } } |
| }); |
| </script> |
| <script> |
| // Note that we load MathJax this way to work with local file (file://), HTTP and HTTPS. |
| // We could use "//cdn.mathjax...", but that won't support "file://". |
| (function(d, script) { |
| script = d.createElement('script'); |
| script.type = 'text/javascript'; |
| script.async = true; |
| script.onload = function(){ |
| MathJax.Hub.Config({ |
| tex2jax: { |
| inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], |
| displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], |
| processEscapes: true, |
| skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'] |
| } |
| }); |
| }; |
| script.src = ('https:' == document.location.protocol ? 'https://' : 'http://') + |
| 'cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'; |
| d.getElementsByTagName('head')[0].appendChild(script); |
| }(document)); |
| </script> |
| </body> |
| </html> |