site/docs/4.1.0-preview1/ml-advanced.html - spark-website - Git at Google



 <!DOCTYPE html>
 <html class="no-js">
     <head>
         <meta charset="utf-8">
         <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
         <meta name="viewport" content="width=device-width, initial-scale=1.0">

         <title>Advanced topics - Spark 4.1.0-preview1 Documentation</title>


         <link rel="stylesheet" href="css/bootstrap.min.css">
         <link rel="preconnect" href="https://fonts.googleapis.com">
         <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
         <link href="https://fonts.googleapis.com/css2?family=DM+Sans:ital,wght@0,400;0,500;0,700;1,400;1,500;1,700&Courier+Prime:wght@400;700&display=swap" rel="stylesheet">
         <link href="css/custom.css" rel="stylesheet">
         <script src="js/vendor/modernizr-2.6.1-respond-1.1.0.min.js"></script>

         <link rel="stylesheet" href="css/pygments-default.css">
         <link rel="stylesheet" href="css/docsearch.min.css" />
         <link rel="stylesheet" href="css/docsearch.css">


         <!-- Matomo -->
         <script>
             var _paq = window._paq = window._paq || [];
             /* tracker methods like "setCustomDimension" should be called before "trackPageView" */
             _paq.push(["disableCookies"]);
             _paq.push(['trackPageView']);
             _paq.push(['enableLinkTracking']);
             (function() {
               var u="https://analytics.apache.org/";
               _paq.push(['setTrackerUrl', u+'matomo.php']);
               _paq.push(['setSiteId', '40']);
               var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
               g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s);
             })();
         </script>
         <!-- End Matomo Code -->


     </head>
     <body class="global">
         <!-- This code is taken from http://twitter.github.com/bootstrap/examples/hero.html -->
         <nav class="navbar navbar-expand-lg navbar-dark p-0 px-4 fixed-top" style="background: #1d6890;" id="topbar">
             <div class="navbar-brand"><a href="index.html">
                 <img src="https://spark.apache.org/images/spark-logo-rev.svg" width="141" height="72"/></a><span class="version">4.1.0-preview1</span>
             </div>
             <button class="navbar-toggler" type="button" data-toggle="collapse"
                     data-target="#navbarCollapse" aria-controls="navbarCollapse"
                     aria-expanded="false" aria-label="Toggle navigation">
                 <span class="navbar-toggler-icon"></span>
             </button>
             <div class="collapse navbar-collapse" id="navbarCollapse">
                 <ul class="navbar-nav me-auto">
                     <li class="nav-item"><a href="index.html" class="nav-link">Overview</a></li>

                     <li class="nav-item dropdown">
                         <a href="#" class="nav-link dropdown-toggle" id="navbarQuickStart" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">Programming Guides</a>
                         <div class="dropdown-menu" aria-labelledby="navbarQuickStart">
                             <a class="dropdown-item" href="quick-start.html">Quick Start</a>
                             <a class="dropdown-item" href="rdd-programming-guide.html">RDDs, Accumulators, Broadcasts Vars</a>
                             <a class="dropdown-item" href="sql-programming-guide.html">SQL, DataFrames, and Datasets</a>
                             <a class="dropdown-item" href="streaming/index.html">Structured Streaming</a>
                             <a class="dropdown-item" href="streaming-programming-guide.html">Spark Streaming (DStreams)</a>
                             <a class="dropdown-item" href="ml-guide.html">MLlib (Machine Learning)</a>
                             <a class="dropdown-item" href="graphx-programming-guide.html">GraphX (Graph Processing)</a>
                             <a class="dropdown-item" href="sparkr.html">SparkR (R on Spark)</a>
                             <a class="dropdown-item" href="api/python/getting_started/index.html">PySpark (Python on Spark)</a>
                             <a class="dropdown-item" href="declarative-pipelines-programming-guide.html">Declarative Pipelines</a>
                         </div>
                     </li>

                     <li class="nav-item dropdown">
                         <a href="#" class="nav-link dropdown-toggle" id="navbarAPIDocs" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">API Docs</a>
                         <div class="dropdown-menu" aria-labelledby="navbarAPIDocs">
                             <a class="dropdown-item" href="api/python/index.html">Python</a>
                             <a class="dropdown-item" href="api/scala/org/apache/spark/index.html">Scala</a>
                             <a class="dropdown-item" href="api/java/index.html">Java</a>
                             <a class="dropdown-item" href="api/R/index.html">R</a>
                             <a class="dropdown-item" href="api/sql/index.html">SQL, Built-in Functions</a>
                         </div>
                     </li>

                     <li class="nav-item dropdown">
                         <a href="#" class="nav-link dropdown-toggle" id="navbarDeploying" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">Deploying</a>
                         <div class="dropdown-menu" aria-labelledby="navbarDeploying">
                             <a class="dropdown-item" href="cluster-overview.html">Overview</a>
                             <a class="dropdown-item" href="submitting-applications.html">Submitting Applications</a>
                             <div class="dropdown-divider"></div>
                             <a class="dropdown-item" href="spark-standalone.html">Spark Standalone</a>
                             <a class="dropdown-item" href="running-on-yarn.html">YARN</a>
                             <a class="dropdown-item" href="running-on-kubernetes.html">Kubernetes</a>
                         </div>
                     </li>

                     <li class="nav-item dropdown">
                         <a href="#" class="nav-link dropdown-toggle" id="navbarMore" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">More</a>
                         <div class="dropdown-menu" aria-labelledby="navbarMore">
                             <a class="dropdown-item" href="configuration.html">Configuration</a>
                             <a class="dropdown-item" href="monitoring.html">Monitoring</a>
                             <a class="dropdown-item" href="tuning.html">Tuning Guide</a>
                             <a class="dropdown-item" href="job-scheduling.html">Job Scheduling</a>
                             <a class="dropdown-item" href="security.html">Security</a>
                             <a class="dropdown-item" href="hardware-provisioning.html">Hardware Provisioning</a>
                             <a class="dropdown-item" href="migration-guide.html">Migration Guide</a>
                             <div class="dropdown-divider"></div>
                             <a class="dropdown-item" href="building-spark.html">Building Spark</a>
                             <a class="dropdown-item" href="https://spark.apache.org/contributing.html">Contributing to Spark</a>
                             <a class="dropdown-item" href="https://spark.apache.org/third-party-projects.html">Third Party Projects</a>
                         </div>
                     </li>

                     <li class="nav-item">
                         <input type="text" id="docsearch-input" placeholder="Search the docs…">
                     </li>
                 </ul>
                 <!--<span class="navbar-text navbar-right"><span class="version-text">v4.1.0-preview1</span></span>-->
             </div>
         </nav>


         <div class="container">


                     <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-datasource.html">

                 Data sources

         </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">

                 Advanced topics

         </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 mr-3" 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 class="language-plaintext highlighter-rouge">\[
 \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 class="language-plaintext highlighter-rouge">$\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&#8217;s method. As a result, L-BFGS often achieves faster convergence compared with
 other first-order optimizations.</p>

 <p><a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2007/01/andrew07scalable.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/org/apache/spark/ml/regression/LinearRegression.html">LinearRegression</a>,
 <a href="api/scala/org/apache/spark/ml/classification/LogisticRegression.html">LogisticRegression</a>,
 <a href="api/scala/org/apache/spark/ml/regression/AFTSurvivalRegression.html">AFTSurvivalRegression</a>
 and <a href="api/scala/org/apache/spark/ml/classification/MultilayerPerceptronClassifier.html">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/v4.1.0-preview1/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 class="language-plaintext highlighter-rouge">\[
 \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 class="language-plaintext highlighter-rouge">LinearRegression</code> and <code class="language-plaintext highlighter-rouge">GeneralizedLinearRegression</code> estimators.</p>

 <p><code class="language-plaintext highlighter-rouge">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 &gt; 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 class="language-plaintext highlighter-rouge">WeightedLeastSquares</code> requires that the number of features is 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/v4.1.0-preview1/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 class="language-plaintext highlighter-rouge">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/org/apache/spark/ml/regression/GeneralizedLinearRegression.html">GeneralizedLinearRegression</a>.</p>


                 </div>

              <!-- /container -->
         </div>

         <script src="js/vendor/jquery-3.5.1.min.js"></script>
         <script src="js/vendor/bootstrap.bundle.min.js"></script>

         <script src="js/vendor/anchor.min.js"></script>
         <script src="js/main.js"></script>

         <script type="text/javascript" src="js/vendor/docsearch.min.js"></script>
         <script type="text/javascript">
             // DocSearch is entirely free and automated. DocSearch is built in two parts:
             // 1. a crawler which we run on our own infrastructure every 24 hours. It follows every link
             //    in your website and extract content from every page it traverses. It then pushes this
             //    content to an Algolia index.
             // 2. a JavaScript snippet to be inserted in your website that will bind this Algolia index
             //    to your search input and display its results in a dropdown UI. If you want to find more
             //    details on how works DocSearch, check the docs of DocSearch.
             docsearch({
     apiKey: 'd62f962a82bc9abb53471cb7b89da35e',
     appId: 'RAI69RXRSK',
     indexName: 'apache_spark',
     inputSelector: '#docsearch-input',
     enhancedSearchInput: true,
     algoliaOptions: {
       'facetFilters': ["version:4.1.0-preview1"]
     },
     debug: false // Set debug to true if you want to inspect the dropdown
 });

         </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://') +
                     'cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js' +
                     '?config=TeX-AMS-MML_HTMLorMML';
                 d.getElementsByTagName('head')[0].appendChild(script);
             }(document));
         </script>
     </body>
 </html>




	<!DOCTYPE html>
	<html class="no-js">
	<head>
	<meta charset="utf-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">

	<title>Advanced topics - Spark 4.1.0-preview1 Documentation</title>





	<link rel="stylesheet" href="css/bootstrap.min.css">
	<link rel="preconnect" href="https://fonts.googleapis.com">
	<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
	<link href="https://fonts.googleapis.com/css2?family=DM+Sans:ital,wght@0,400;0,500;0,700;1,400;1,500;1,700&Courier+Prime:wght@400;700&display=swap" rel="stylesheet">
	<link href="css/custom.css" rel="stylesheet">
	<script src="js/vendor/modernizr-2.6.1-respond-1.1.0.min.js"></script>

	<link rel="stylesheet" href="css/pygments-default.css">
	<link rel="stylesheet" href="css/docsearch.min.css" />
	<link rel="stylesheet" href="css/docsearch.css">


	<!-- Matomo -->
	<script>
	var _paq = window._paq = window._paq \|\| [];
	/* tracker methods like "setCustomDimension" should be called before "trackPageView" */
	_paq.push(["disableCookies"]);
	_paq.push(['trackPageView']);
	_paq.push(['enableLinkTracking']);
	(function() {
	var u="https://analytics.apache.org/";
	_paq.push(['setTrackerUrl', u+'matomo.php']);
	_paq.push(['setSiteId', '40']);
	var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
	g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s);
	})();
	</script>
	<!-- End Matomo Code -->


	</head>
	<body class="global">
	<!-- This code is taken from http://twitter.github.com/bootstrap/examples/hero.html -->
	<nav class="navbar navbar-expand-lg navbar-dark p-0 px-4 fixed-top" style="background: #1d6890;" id="topbar">
	<div class="navbar-brand"><a href="index.html">
	<img src="https://spark.apache.org/images/spark-logo-rev.svg" width="141" height="72"/></a><span class="version">4.1.0-preview1</span>
	</div>
	<button class="navbar-toggler" type="button" data-toggle="collapse"
	data-target="#navbarCollapse" aria-controls="navbarCollapse"
	aria-expanded="false" aria-label="Toggle navigation">
	<span class="navbar-toggler-icon"></span>
	</button>
	<div class="collapse navbar-collapse" id="navbarCollapse">
	<ul class="navbar-nav me-auto">
	<li class="nav-item"><a href="index.html" class="nav-link">Overview</a></li>

	<li class="nav-item dropdown">
	<a href="#" class="nav-link dropdown-toggle" id="navbarQuickStart" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">Programming Guides</a>
	<div class="dropdown-menu" aria-labelledby="navbarQuickStart">
	<a class="dropdown-item" href="quick-start.html">Quick Start</a>
	<a class="dropdown-item" href="rdd-programming-guide.html">RDDs, Accumulators, Broadcasts Vars</a>
	<a class="dropdown-item" href="sql-programming-guide.html">SQL, DataFrames, and Datasets</a>
	<a class="dropdown-item" href="streaming/index.html">Structured Streaming</a>
	<a class="dropdown-item" href="streaming-programming-guide.html">Spark Streaming (DStreams)</a>
	<a class="dropdown-item" href="ml-guide.html">MLlib (Machine Learning)</a>
	<a class="dropdown-item" href="graphx-programming-guide.html">GraphX (Graph Processing)</a>
	<a class="dropdown-item" href="sparkr.html">SparkR (R on Spark)</a>
	<a class="dropdown-item" href="api/python/getting_started/index.html">PySpark (Python on Spark)</a>
	<a class="dropdown-item" href="declarative-pipelines-programming-guide.html">Declarative Pipelines</a>
	</div>
	</li>

	<li class="nav-item dropdown">
	<a href="#" class="nav-link dropdown-toggle" id="navbarAPIDocs" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">API Docs</a>
	<div class="dropdown-menu" aria-labelledby="navbarAPIDocs">
	<a class="dropdown-item" href="api/python/index.html">Python</a>
	<a class="dropdown-item" href="api/scala/org/apache/spark/index.html">Scala</a>
	<a class="dropdown-item" href="api/java/index.html">Java</a>
	<a class="dropdown-item" href="api/R/index.html">R</a>
	<a class="dropdown-item" href="api/sql/index.html">SQL, Built-in Functions</a>
	</div>
	</li>

	<li class="nav-item dropdown">
	<a href="#" class="nav-link dropdown-toggle" id="navbarDeploying" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">Deploying</a>
	<div class="dropdown-menu" aria-labelledby="navbarDeploying">
	<a class="dropdown-item" href="cluster-overview.html">Overview</a>
	<a class="dropdown-item" href="submitting-applications.html">Submitting Applications</a>
	<div class="dropdown-divider"></div>
	<a class="dropdown-item" href="spark-standalone.html">Spark Standalone</a>
	<a class="dropdown-item" href="running-on-yarn.html">YARN</a>
	<a class="dropdown-item" href="running-on-kubernetes.html">Kubernetes</a>
	</div>
	</li>

	<li class="nav-item dropdown">
	<a href="#" class="nav-link dropdown-toggle" id="navbarMore" role="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">More</a>
	<div class="dropdown-menu" aria-labelledby="navbarMore">
	<a class="dropdown-item" href="configuration.html">Configuration</a>
	<a class="dropdown-item" href="monitoring.html">Monitoring</a>
	<a class="dropdown-item" href="tuning.html">Tuning Guide</a>
	<a class="dropdown-item" href="job-scheduling.html">Job Scheduling</a>
	<a class="dropdown-item" href="security.html">Security</a>
	<a class="dropdown-item" href="hardware-provisioning.html">Hardware Provisioning</a>
	<a class="dropdown-item" href="migration-guide.html">Migration Guide</a>
	<div class="dropdown-divider"></div>
	<a class="dropdown-item" href="building-spark.html">Building Spark</a>
	<a class="dropdown-item" href="https://spark.apache.org/contributing.html">Contributing to Spark</a>
	<a class="dropdown-item" href="https://spark.apache.org/third-party-projects.html">Third Party Projects</a>
	</div>
	</li>

	<li class="nav-item">
	<input type="text" id="docsearch-input" placeholder="Search the docs…">
	</li>
	</ul>
	<!--<span class="navbar-text navbar-right"><span class="version-text">v4.1.0-preview1</span></span>-->
	</div>
	</nav>



	<div class="container">


	<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-datasource.html">

	Data sources

	</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">

	Advanced topics

	</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 mr-3" 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 class="language-plaintext highlighter-rouge">\[
	\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 class="language-plaintext highlighter-rouge">$\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="https://www.microsoft.com/en-us/research/wp-content/uploads/2007/01/andrew07scalable.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/org/apache/spark/ml/regression/LinearRegression.html">LinearRegression</a>,
	<a href="api/scala/org/apache/spark/ml/classification/LogisticRegression.html">LogisticRegression</a>,
	<a href="api/scala/org/apache/spark/ml/regression/AFTSurvivalRegression.html">AFTSurvivalRegression</a>
	and <a href="api/scala/org/apache/spark/ml/classification/MultilayerPerceptronClassifier.html">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/v4.1.0-preview1/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 class="language-plaintext highlighter-rouge">\[
	\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 class="language-plaintext highlighter-rouge">LinearRegression</code> and <code class="language-plaintext highlighter-rouge">GeneralizedLinearRegression</code> estimators.</p>

	<p><code class="language-plaintext highlighter-rouge">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 class="language-plaintext highlighter-rouge">WeightedLeastSquares</code> requires that the number of features is 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/v4.1.0-preview1/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 class="language-plaintext highlighter-rouge">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/org/apache/spark/ml/regression/GeneralizedLinearRegression.html">GeneralizedLinearRegression</a>.</p>


	</div>

	<!-- /container -->
	</div>

	<script src="js/vendor/jquery-3.5.1.min.js"></script>
	<script src="js/vendor/bootstrap.bundle.min.js"></script>

	<script src="js/vendor/anchor.min.js"></script>
	<script src="js/main.js"></script>

	<script type="text/javascript" src="js/vendor/docsearch.min.js"></script>
	<script type="text/javascript">
	// DocSearch is entirely free and automated. DocSearch is built in two parts:
	// 1. a crawler which we run on our own infrastructure every 24 hours. It follows every link
	// in your website and extract content from every page it traverses. It then pushes this
	// content to an Algolia index.
	// 2. a JavaScript snippet to be inserted in your website that will bind this Algolia index
	// to your search input and display its results in a dropdown UI. If you want to find more
	// details on how works DocSearch, check the docs of DocSearch.
	docsearch({
	apiKey: 'd62f962a82bc9abb53471cb7b89da35e',
	appId: 'RAI69RXRSK',
	indexName: 'apache_spark',
	inputSelector: '#docsearch-input',
	enhancedSearchInput: true,
	algoliaOptions: {
	'facetFilters': ["version:4.1.0-preview1"]
	},
	debug: false // Set debug to true if you want to inspect the dropdown
	});

	</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://') +
	'cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js' +
	'?config=TeX-AMS-MML_HTMLorMML';
	d.getElementsByTagName('head')[0].appendChild(script);
	}(document));
	</script>
	</body>
	</html>