You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by tgaloppo <gi...@git.apache.org> on 2015/01/01 16:38:58 UTC
[GitHub] spark pull request: SPARK-5017 - Use SVD to compute determinant an...
GitHub user tgaloppo opened a pull request:
https://github.com/apache/spark/pull/3871
SPARK-5017 - Use SVD to compute determinant and inverse of covariance matrix
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/tgaloppo/spark spark-5017
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/3871.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 #3871
----
commit fd9784cad41ee76b4711cb702dbbb7216965db89
Author: Travis Galoppo <tj...@columbia.edu>
Date: 2015-01-01T15:33:28Z
SPARK-5017 - Use SVD to compute determinant and inverse of covariance matrix
----
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68610312
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/25016/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22442436
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,74 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case)
--- End diff --
For link, use double-brackets:
```
(See [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
```
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68652967
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/25038/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/3871
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423959
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
--- End diff --
Perhaps you could add a note here about how this behaves when sigma is singular, plus a reference like [http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]
The doc could be a short version of what you have below for ```calculateCovarianceConstants```
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22552390
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
Ugh, no, I have. I was confused about which were inverses, and what you wrote looks perfectly fine. Sorry for the trouble! I'll remove the comments.d
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68652965
[Test build #25038 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25038/consoleFull) for PR 3871 at commit [`a5b8bc5`](https://github.com/apache/spark/commit/a5b8bc55e5f4abdc7c1e53bd3c32dac508e03f9f).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68491851
[Test build #24987 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/24987/consoleFull) for PR 3871 at commit [`fd9784c`](https://github.com/apache/spark/commit/fd9784cad41ee76b4711cb702dbbb7216965db89).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22434157
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x = Vectors.dense(0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(1, 1, Array(1.0)).toBreeze.toDenseMatrix
+ var dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.39894 absTol 1E-5)
+
+ sigma = Matrices.dense(1, 1, Array(4.0)).toBreeze.toDenseMatrix
+ dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.19947 absTol 1E-5)
+ }
+
+ test("multivariate") {
+ val x = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(2, 2, Array(1.0, 0.0, 0.0, 1.0)).toBreeze.toDenseMatrix
--- End diff --
Good catch with the other var; could you please fix this and the test above too? var -> val
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423970
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /*
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition (breeze provides one specifically for symmetric matrices,
+ * so I am making an assumption here that there is some efficiency gain).
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, ie, Octave).
+ */
+ private def calculateCovarianceConstants: (DBM[Double], Double) = {
+ val eigSym.EigSym(d, u) = eigSym(sigma) // sigma = u * diag(d) * u.t
+
+ // For numerical stability, values are considered to be non-zero only if they exceed tol.
+ // This prevents any inverted value from exceeding (eps * n * max(d))^-1
+ val tol = MLUtils.EPSILON * max(d) * d.length
+
+ // pseudo-determinant is product of all non-zero eigenvalues
+ val pdetSigma = (0 until d.length).map(i => if (d(i) > tol) d(i) else 1.0).reduce(_ * _)
--- End diff --
More concise:
```
val pdetSigma = d.activeValuesIterator.filter(_ > tol).foldLeft(1.0)(_ * _)
```
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68649965
[Test build #25038 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25038/consoleFull) for PR 3871 at commit [`a5b8bc5`](https://github.com/apache/spark/commit/a5b8bc55e5f4abdc7c1e53bd3c32dac508e03f9f).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68813341
[Test build #25069 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25069/consoleFull) for PR 3871 at commit [`383b5b3`](https://github.com/apache/spark/commit/383b5b3c69189adf3a5d3dfd7e4857056bcd488c).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423964
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /*
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition (breeze provides one specifically for symmetric matrices,
--- End diff --
No need to comment on Breeze here; you can in the PR description if it's in question.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22486202
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,74 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * sigmaInv2 = (-1/2) * inv(sigma)
+ * u = (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ */
+ private val (sigmaInv2: DBM[Double], u: Double) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /**
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition.
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, e.g., Octave).
+ */
+ private def calculateCovarianceConstants: (DBM[Double], Double) = {
+ val eigSym.EigSym(d, u) = eigSym(sigma) // sigma = u * diag(d) * u.t
+
+ // For numerical stability, values are considered to be non-zero only if they exceed tol.
+ // This prevents any inverted value from exceeding (eps * n * max(d))^-1
+ val tol = MLUtils.EPSILON * max(d) * d.length
+
+ try {
+ // pseudo-determinant is product of all non-zero singular values
+ val pdetSigma = d.activeValuesIterator.filter(_ > tol).reduce(_ * _)
+
+ // calculate pseudo-inverse by inverting all non-zero singular values
+ val pinvS = new DBV(d.map(v => if (v > tol) (1.0 / v) else 0.0).toArray)
+ val pinvSigma = u * diag(pinvS) * u.t
--- End diff --
minor: We don't need to compute `pinvSigma` explicitly.
~~~
Sigma = U * D * U^T
Sigma^+ = U * D^+ U^T = (D^{-1/2} U)^T (D^{-1/2} U)
-0.5 * delta^T * Sigma^+ * delta = -0.5 \| D^{-1/2} U delta \|_2^2
~~~
So we can scale the rows of `U` by `1/math.sqrt(d_i)`, and then update line 47.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68578626
[Test build #25001 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25001/consoleFull) for PR 3871 at commit [`d448137`](https://github.com/apache/spark/commit/d448137b739691c152dd981f136cef62b65d4e50).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22507242
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
Hm, I don't think U is symmetric. E.g., in R:
```
> b
[,1] [,2] [,3] [,4]
[1,] 9 3 3 3
[2,] 3 3 0 0
[3,] 3 0 3 0
[4,] 3 0 0 3
> svd(b)
$d
[1] 1.200000e+01 3.000000e+00 3.000000e+00 2.775558e-16
$u
[,1] [,2] [,3] [,4]
[1,] -0.8660254 2.102975e-17 2.071704e-16 0.5
[2,] -0.2886751 -8.065591e-01 1.270001e-01 -0.5
[3,] -0.2886751 2.932942e-01 -7.620008e-01 -0.5
[4,] -0.2886751 5.132649e-01 6.350006e-01 -0.5
$v
[,1] [,2] [,3] [,4]
[1,] -0.8660254 -7.284921e-17 0.0000000 0.5
[2,] -0.2886751 -8.065591e-01 0.1270001 -0.5
[3,] -0.2886751 2.932942e-01 -0.7620008 -0.5
[4,] -0.2886751 5.132649e-01 0.6350006 -0.5
```
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22504722
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
U D^-1 * U.t => U D^(-1/2) D^(-1/2) U.t => (U D^(-1/2)) (D^(-1/2) U.t)
...both are U and D are symmetric, so...
(U D^(-1/2)) = (U.t (D^(-1/2)).t) => (D^(-1/2) U).t
and
(D^(-1/2) U.t) = (D^(-1/2) U)
thus
U D^-1 U.t => (D^(-1/2) U).t (D^(-1/2) U)
... bringing in the delta we get
delta.t (D^(-1/2) U).t (D^(-1/2) U) delta
=> ((D^(-1/2) U) delta).t (D^(-1/2) U) delta = norm(D^(-1/2) U delta)^2
as indicated by @mengxr
(phew, hope I did that OK! :) )
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68649845
@jkbradley Good call on the test suite; I have added some non-center points to the tests. I also added the brackets to the in-comment link.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22512662
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
In that case, U must not be symmetric. But I must have been wrong about the orientation of U returned by the svd call.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68572495
[Test build #24998 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/24998/consoleFull) for PR 3871 at commit [`b4415ea`](https://github.com/apache/spark/commit/b4415ea70055e8ca2c0444cf964b696f0e1e410d).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68565800
One more request: Could you please add a unit test with a singular matrix? Thank you! Perhaps in a new suite for MultivariateGaussian
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22545409
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
(u, d) is the eigendecomposition of sigma, so sigma = u * diag(d) * u^-1 ... but we have a special case since covariance matrices are always symmetric and positive semi-definite, in which case u * u.t = I, making it equivalent to the singular value decomposition... so sigma = u * diag(d) * u.t ... so in svd terms, v.t = u.t, then the inverse is v * inv(diag(d)) * u.t = u * inv(diag(d)) * u.t ...
Have I lost my bearings?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423967
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /*
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition (breeze provides one specifically for symmetric matrices,
+ * so I am making an assumption here that there is some efficiency gain).
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, ie, Octave).
--- End diff --
"ie" --> "e.g."
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68934738
@tgaloppo Now that my confusion is over...LGTM Thanks very much!
CC: @mengxr
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68580981
[Test build #25001 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25001/consoleFull) for PR 3871 at commit [`d448137`](https://github.com/apache/spark/commit/d448137b739691c152dd981f136cef62b65d4e50).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68813348
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/25069/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22429029
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x = Vectors.dense(0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(1, 1, Array(1.0)).toBreeze.toDenseMatrix
+ var dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.39894 absTol 1E-5)
+
+ sigma = Matrices.dense(1, 1, Array(4.0)).toBreeze.toDenseMatrix
+ dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.19947 absTol 1E-5)
+ }
+
+ test("multivariate") {
+ val x = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0, 0.0).toBreeze. toDenseVector
--- End diff --
typo: space between . and toDenseVector
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22429027
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,69 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case)
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * sigmaInv2 = (-1/2) * inv(sigma)
+ * u = (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ */
+ private val (sigmaInv2: DBM[Double], u: Double) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /**
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition.
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, e.g., Octave).
+ */
+ private def calculateCovarianceConstants: (DBM[Double], Double) = {
+ val eigSym.EigSym(d, u) = eigSym(sigma) // sigma = u * diag(d) * u.t
+
+ // For numerical stability, values are considered to be non-zero only if they exceed tol.
+ // This prevents any inverted value from exceeding (eps * n * max(d))^-1
+ val tol = MLUtils.EPSILON * max(d) * d.length
+
+ // pseudo-determinant is product of all non-zero eigenvalues
+ val pdetSigma = d.activeValuesIterator.filter(_ > tol).reduce(_ * _)
--- End diff --
If all singular values are <= tol, then this will throw an UnsupportedOperationException. Could you perhaps catch it and throw a more meaningful error if that happens?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68580983
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/25001/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68581031
@tgaloppo Thanks for the updates. Sure, the log-space computation could be in another PR.
Just to make sure: Did you compute the PDF values in the tests using other software?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68584510
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/25006/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68575728
@jkbradley I think performing the pdf calculation in log-space (and providing a logpdf() method) is a good idea. Perhaps we can make this part of transitioning MultivariateGaussian to public scope?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68565659
@tgaloppo The logic looks good; my comments are basically about clarity (except for the log space question). Thanks for the PR!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22521704
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
I agree; I see no reason why U should always be symmetric (as you have demonstrated). Before I roll back the change, I just want to make sure that I did not misinterpret @mengxr , and/or that we are not missing something that he sees.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22429025
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,69 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case)
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * sigmaInv2 = (-1/2) * inv(sigma)
+ * u = (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ */
+ private val (sigmaInv2: DBM[Double], u: Double) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /**
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition.
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, e.g., Octave).
+ */
+ private def calculateCovarianceConstants: (DBM[Double], Double) = {
+ val eigSym.EigSym(d, u) = eigSym(sigma) // sigma = u * diag(d) * u.t
+
+ // For numerical stability, values are considered to be non-zero only if they exceed tol.
+ // This prevents any inverted value from exceeding (eps * n * max(d))^-1
+ val tol = MLUtils.EPSILON * max(d) * d.length
+
+ // pseudo-determinant is product of all non-zero eigenvalues
--- End diff --
"eigenvalues" --> "singular values" (here and in the next comment on line 79)
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68565593
@tgaloppo @mengxr What are your thoughts about doing the computation in log space as much as possible, and then exponentiating at the end? I'm mainly thinking about numerical stability, but I could imagine wanting to provide pdf() and logpdf() methods eventually.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68606410
@tgaloppo thanks for verifying about the test pdf values
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22442437
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x = Vectors.dense(0.0).toBreeze.toDenseVector
--- End diff --
It might be good to test at 2 points, rather than just 1. (This tests the distribution constant but not inv(Sigma).)
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423962
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /*
--- End diff --
Use ```/**``` for class/method documentation.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22502677
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
```D^(-1/2) * U``` should be ```U * D^(-1/2)```, right? If so, it is an issue in both the comments & code below
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22485212
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,69 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x1 = Vectors.dense(0.0).toBreeze.toDenseVector
--- End diff --
We can construct `BDV` and `BDM` directly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22508610
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
@jkbradley Hmm. I am going to punt on this one. Perhaps @mengxr can point out my error. FWIW - Changing the code to U * D^(-1/2) causes the unit tests to fail.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68806762
@mengxr Changes made.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22542741
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,84 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, diag, max, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/**
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution. In
+ * the event that the covariance matrix is singular, the density will be computed in a
+ * reduced dimensional subspace under which the distribution is supported.
+ * (see [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Degenerate_case]])
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ /**
+ * Compute distribution dependent constants:
+ * rootSigmaInv = D^(-1/2) * U, where sigma = U * D * U.t
--- End diff --
I think it's just a documentation error. ```sigma = u * diag(d) * u.t``` should instead be ```sigma = u.t * diag(d) * u``` (for the value u being stored)
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 - Use SVD to compute determinant an...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68489677
[Test build #24987 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/24987/consoleFull) for PR 3871 at commit [`fd9784c`](https://github.com/apache/spark/commit/fd9784cad41ee76b4711cb702dbbb7216965db89).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22434487
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x = Vectors.dense(0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(1, 1, Array(1.0)).toBreeze.toDenseMatrix
+ var dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.39894 absTol 1E-5)
+
+ sigma = Matrices.dense(1, 1, Array(4.0)).toBreeze.toDenseMatrix
+ dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.19947 absTol 1E-5)
+ }
+
+ test("multivariate") {
+ val x = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(2, 2, Array(1.0, 0.0, 0.0, 1.0)).toBreeze.toDenseMatrix
--- End diff --
@jkbradley No problem; fixed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68566334
[Test build #24998 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/24998/consoleFull) for PR 3871 at commit [`b4415ea`](https://github.com/apache/spark/commit/b4415ea70055e8ca2c0444cf964b696f0e1e410d).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68582759
[Test build #25006 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25006/consoleFull) for PR 3871 at commit [`dc3d0f7`](https://github.com/apache/spark/commit/dc3d0f7d70cfe54350a1ef70b20e9120b8937919).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68562386
@tgaloppo Could you please add a description? It can be based off of the JIRA, just enough to cover the main points of the PR. Thanks!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68610310
[Test build #25016 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25016/consoleFull) for PR 3871 at commit [`629d9d0`](https://github.com/apache/spark/commit/629d9d03e4bfd79410c8e1471e05986970022175).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423961
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
--- End diff --
Could you please add explicit types + documentation here for clarity?
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by tgaloppo <gi...@git.apache.org>.
Github user tgaloppo commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68581355
@jkbradley I used Octave's mvnpdf from the statistics package for the non-singular cases; it can not handle singular covariance matrices, so I was only able to recreate the function using octaves' pinv() function.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68806850
[Test build #25069 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25069/consoleFull) for PR 3871 at commit [`383b5b3`](https://github.com/apache/spark/commit/383b5b3c69189adf3a5d3dfd7e4857056bcd488c).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68648254
@tgaloppo 2 more small comments, but after those, I believe this will be ready. Thanks!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68572497
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/24998/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68491855
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/24987/
Test PASSed.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68941542
Merged into master. Thanks!
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68650576
@tgaloppo Thanks for the updates! LGTM after tests pass
CC: @mengxr
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22429041
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,69 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
--- End diff --
Use ```/**```
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22423972
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussian.scala ---
@@ -17,23 +17,62 @@
package org.apache.spark.mllib.stat.impl
-import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, Transpose, det, pinv}
+import breeze.linalg.{DenseVector => DBV, DenseMatrix => DBM, max, diag, eigSym}
-/**
- * Utility class to implement the density function for multivariate Gaussian distribution.
- * Breeze provides this functionality, but it requires the Apache Commons Math library,
- * so this class is here so-as to not introduce a new dependency in Spark.
- */
+import org.apache.spark.mllib.util.MLUtils
+
+/*
+ * This class provides basic functionality for a Multivariate Gaussian (Normal) Distribution
+ *
+ * @param mu The mean vector of the distribution
+ * @param sigma The covariance matrix of the distribution
+ */
private[mllib] class MultivariateGaussian(
val mu: DBV[Double],
val sigma: DBM[Double]) extends Serializable {
- private val sigmaInv2 = pinv(sigma) * -0.5
- private val U = math.pow(2.0 * math.Pi, -mu.length / 2.0) * math.pow(det(sigma), -0.5)
-
+
+ private val (sigmaInv2, u) = calculateCovarianceConstants
+
/** Returns density of this multivariate Gaussian at given point, x */
def pdf(x: DBV[Double]): Double = {
val delta = x - mu
- val deltaTranspose = new Transpose(delta)
- U * math.exp(deltaTranspose * sigmaInv2 * delta)
+ u * math.exp(delta.t * sigmaInv2 * delta)
+ }
+
+ /*
+ * Calculate distribution dependent components used for the density function:
+ * pdf(x) = (2*pi)^(-k/2) * det(sigma)^(-1/2) * exp( (-1/2) * (x-mu).t * inv(sigma) * (x-mu) )
+ * where k is length of the mean vector.
+ *
+ * We here compute distribution-fixed parts
+ * (2*pi)^(-k/2) * det(sigma)^(-1/2)
+ * and
+ * (-1/2) * inv(sigma)
+ *
+ * Both the determinant and the inverse can be computed from the singular value decomposition
+ * of sigma. Noting that covariance matrices are always symmetric and positive semi-definite,
+ * we can use the eigendecomposition (breeze provides one specifically for symmetric matrices,
+ * so I am making an assumption here that there is some efficiency gain).
+ *
+ * To guard against singular covariance matrices, this method computes both the
+ * pseudo-determinant and the pseudo-inverse (Moore-Penrose). Singular values are considered
+ * to be non-zero only if they exceed a tolerance based on machine precision, matrix size, and
+ * relation to the maximum singular value (same tolerance used by, ie, Octave).
+ */
+ private def calculateCovarianceConstants: (DBM[Double], Double) = {
+ val eigSym.EigSym(d, u) = eigSym(sigma) // sigma = u * diag(d) * u.t
+
+ // For numerical stability, values are considered to be non-zero only if they exceed tol.
+ // This prevents any inverted value from exceeding (eps * n * max(d))^-1
+ val tol = MLUtils.EPSILON * max(d) * d.length
+
+ // pseudo-determinant is product of all non-zero eigenvalues
+ val pdetSigma = (0 until d.length).map(i => if (d(i) > tol) d(i) else 1.0).reduce(_ * _)
+
+ // calculate pseudo-inverse by inverting all non-zero eigenvalues
+ val pinvS = new DBV((0 until d.length).map(i => if (d(i) > tol) (1.0 / d(i)) else 0.0).toArray)
--- End diff --
This too can be more concise.
You generally do not need to use the ```(0 until length).map``` pattern unless you need the indices; it is easier to map the values of an array like d directly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68584507
[Test build #25006 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25006/consoleFull) for PR 3871 at commit [`dc3d0f7`](https://github.com/apache/spark/commit/dc3d0f7d70cfe54350a1ef70b20e9120b8937919).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/3871#issuecomment-68607516
[Test build #25016 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/25016/consoleFull) for PR 3871 at commit [`629d9d0`](https://github.com/apache/spark/commit/629d9d03e4bfd79410c8e1471e05986970022175).
* This patch merges cleanly.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: SPARK-5017 [MLlib] - Use SVD to compute determ...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/3871#discussion_r22429030
--- Diff: mllib/src/test/scala/org/apache/spark/mllib/stat/impl/MultivariateGaussianSuite.scala ---
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.stat.impl
+
+import org.scalatest.FunSuite
+
+import org.apache.spark.mllib.linalg.{Vectors, Matrices}
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+import org.apache.spark.mllib.util.TestingUtils._
+
+class MultivariateGaussianSuite extends FunSuite with MLlibTestSparkContext {
+ test("univariate") {
+ val x = Vectors.dense(0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0).toBreeze.toDenseVector
+ var sigma = Matrices.dense(1, 1, Array(1.0)).toBreeze.toDenseMatrix
+ var dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.39894 absTol 1E-5)
+
+ sigma = Matrices.dense(1, 1, Array(4.0)).toBreeze.toDenseMatrix
+ dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.19947 absTol 1E-5)
+ }
+
+ test("multivariate") {
+ val x = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0, 0.0).toBreeze. toDenseVector
+ var sigma = Matrices.dense(2, 2, Array(1.0, 0.0, 0.0, 1.0)).toBreeze.toDenseMatrix
+ var dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.15915 absTol 1E-5)
+
+ sigma = Matrices.dense(2, 2, Array(4.0, -1.0, -1.0, 2.0)).toBreeze.toDenseMatrix
+ dist = new MultivariateGaussian(mu, sigma)
+ assert(dist.pdf(x) ~== 0.060155 absTol 1E-5)
+ }
+
+ test("multivariate degenerate") {
+ val x = Vectors.dense(0.0, 0.0).toBreeze.toDenseVector
+
+ val mu = Vectors.dense(0.0, 0.0).toBreeze. toDenseVector
--- End diff --
typo: space between . and toDenseVector
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org