[jira] [Commented] (SPARK-31007) KMeans optimization based on triangle-inequality
[ https://issues.apache.org/jira/browse/SPARK-31007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17489270#comment-17489270 ] zhengruifeng commented on SPARK-31007: -- this case is not OOM, but the overflow: {code:java} scala> val k = 5 val k: Int = 5scala> k * (k + 1) / 2 val res0: Int = -897458648scala> k * (k + 1) val res1: Int = -1794917296scala> k / 2 * (k + 1) val res2: Int = 1250025000scala> Array.ofDim[Double](k * (k + 1) / 2) java.lang.NegativeArraySizeException at scala.reflect.ManifestFactory$DoubleManifest.newArray(Manifest.scala:273) at scala.reflect.ManifestFactory$DoubleManifest.newArray(Manifest.scala:271) at scala.Array$.ofDim(Array.scala:323) ... 32 elidedscala> Array.ofDim[Double](k / 2 * (k + 1)) java.lang.OutOfMemoryError: Java heap space at scala.reflect.ManifestFactory$DoubleManifest.newArray(Manifest.scala:273) at scala.reflect.ManifestFactory$DoubleManifest.newArray(Manifest.scala:271) at scala.Array$.ofDim(Array.scala:323) ... 29 elidedscala> val k = 45000 val k: Int = 45000scala> Array.ofDim[Double](k / 2 * (k + 1)) java.lang.OutOfMemoryError: Java heap spacescala> k / 2 * (k + 1) val res6: Int = 1012522500 {code} I think we should add a limit of k for this optimization. the change should not be large, I will send a PR. > KMeans optimization based on triangle-inequality > > > Key: SPARK-31007 > URL: https://issues.apache.org/jira/browse/SPARK-31007 > Project: Spark > Issue Type: Improvement > Components: ML >Affects Versions: 3.1.0 >Reporter: zhengruifeng >Assignee: zhengruifeng >Priority: Major > Fix For: 3.1.0 > > Attachments: ICML03-022.pdf > > > In current impl, following Lemma is used in KMeans: > 0, Let x be a point, let b be a center and o be the origin, then d(x,c) >= > |(d(x,o) - d(c,o))| = |norm(x)-norm(c)| > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > According to [Using the Triangle Inequality to Accelerate > K-Means|[https://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf]], we can go > futher, and there are another two Lemmas can be used: > 1, Let x be a point, and let b and c be centers. If d(b,c)>=2d(x,b) then > d(x,c) >= d(x,b); > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}}. > However, luckily for CosineDistance we can get a variant in the space of > radian/angle. > 2, Let x be a point, and let b and c be centers. Then d(x,c) >= max\{0, > d(x,b)-d(b,c)}; > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > The application of Lemma 2 is a little complex: It need to cache/update the > distance/lower bounds to previous centers, and thus can be only applied in > training, not usable in prediction. > So this ticket is mainly for Lemma 1. Its idea is quite simple, if point x is > close to center b enough (less than a pre-computed radius), then we can say > point x belong to center c without computing the distances between x and > other centers. It can be used in both training and predction. -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-31007) KMeans optimization based on triangle-inequality
[ https://issues.apache.org/jira/browse/SPARK-31007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17489235#comment-17489235 ] Sean R. Owen commented on SPARK-31007: -- Hm, can you use a simpler "unpacked" representation for those statistics? it's not the memory per se, but the size of a single array. Instead an array of arrays? > KMeans optimization based on triangle-inequality > > > Key: SPARK-31007 > URL: https://issues.apache.org/jira/browse/SPARK-31007 > Project: Spark > Issue Type: Improvement > Components: ML >Affects Versions: 3.1.0 >Reporter: zhengruifeng >Assignee: zhengruifeng >Priority: Major > Fix For: 3.1.0 > > Attachments: ICML03-022.pdf > > > In current impl, following Lemma is used in KMeans: > 0, Let x be a point, let b be a center and o be the origin, then d(x,c) >= > |(d(x,o) - d(c,o))| = |norm(x)-norm(c)| > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > According to [Using the Triangle Inequality to Accelerate > K-Means|[https://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf]], we can go > futher, and there are another two Lemmas can be used: > 1, Let x be a point, and let b and c be centers. If d(b,c)>=2d(x,b) then > d(x,c) >= d(x,b); > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}}. > However, luckily for CosineDistance we can get a variant in the space of > radian/angle. > 2, Let x be a point, and let b and c be centers. Then d(x,c) >= max\{0, > d(x,b)-d(b,c)}; > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > The application of Lemma 2 is a little complex: It need to cache/update the > distance/lower bounds to previous centers, and thus can be only applied in > training, not usable in prediction. > So this ticket is mainly for Lemma 1. Its idea is quite simple, if point x is > close to center b enough (less than a pre-computed radius), then we can say > point x belong to center c without computing the distances between x and > other centers. It can be used in both training and predction. -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-31007) KMeans optimization based on triangle-inequality
[ https://issues.apache.org/jira/browse/SPARK-31007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17489230#comment-17489230 ] zhengruifeng commented on SPARK-31007: -- [~srowen] This optimization needs an array of size val packedValues = Array.ofDim[Double](k * (k + 1) / 2) can may cause failure when k is large. https://issues.apache.org/jira/browse/SPARK-36553 k=5 should we: 1, revert this optimization 2, or enable it only for small k? (but the impl will be more complex) > KMeans optimization based on triangle-inequality > > > Key: SPARK-31007 > URL: https://issues.apache.org/jira/browse/SPARK-31007 > Project: Spark > Issue Type: Improvement > Components: ML >Affects Versions: 3.1.0 >Reporter: zhengruifeng >Assignee: zhengruifeng >Priority: Major > Fix For: 3.1.0 > > Attachments: ICML03-022.pdf > > > In current impl, following Lemma is used in KMeans: > 0, Let x be a point, let b be a center and o be the origin, then d(x,c) >= > |(d(x,o) - d(c,o))| = |norm(x)-norm(c)| > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > According to [Using the Triangle Inequality to Accelerate > K-Means|[https://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf]], we can go > futher, and there are another two Lemmas can be used: > 1, Let x be a point, and let b and c be centers. If d(b,c)>=2d(x,b) then > d(x,c) >= d(x,b); > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}}. > However, luckily for CosineDistance we can get a variant in the space of > radian/angle. > 2, Let x be a point, and let b and c be centers. Then d(x,c) >= max\{0, > d(x,b)-d(b,c)}; > this can be applied in {{EuclideanDistance}}, but not in {{CosineDistance}} > The application of Lemma 2 is a little complex: It need to cache/update the > distance/lower bounds to previous centers, and thus can be only applied in > training, not usable in prediction. > So this ticket is mainly for Lemma 1. Its idea is quite simple, if point x is > close to center b enough (less than a pre-computed radius), then we can say > point x belong to center c without computing the distances between x and > other centers. It can be used in both training and predction. -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org