[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15965244#comment-15965244
]
Yan Facai (颜发才) commented on SPARK-10788:
-
[~josephkb] As categories A, B and C are independent, why not collect
statistics only for cateogry? Splits are calculated in the last step in
`binsToBestSplit`. So communication cost is N bins.
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>Assignee: Seth Hendrickson
>Priority: Minor
> Fix For: 2.0.0
>
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14990576#comment-14990576
]
Apache Spark commented on SPARK-10788:
--
User 'sethah' has created a pull request for this issue:
https://github.com/apache/spark/pull/9474
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>Priority: Minor
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14940196#comment-14940196
]
Joseph K. Bradley commented on SPARK-10788:
---
Updated. Does it make more sense now?
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[ https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14940186#comment-14940186 ] Joseph K. Bradley commented on SPARK-10788: --- Reading what I wrote now, I realize I didn't actually phrase it correctly. I'll update the description. > Decision Tree duplicates bins for unordered categorical features > > > Key: SPARK-10788 > URL: https://issues.apache.org/jira/browse/SPARK-10788 > Project: Spark > Issue Type: Improvement > Components: ML >Reporter: Joseph K. Bradley > > Decision trees in spark.ml (RandomForest.scala) effectively creates a second > copy of each split. E.g., if there are 3 categories A, B, C, then we should > consider 3 splits: > * A vs. B, C > * A, B vs. C > * A, C vs. B > Currently, we also consider the 3 flipped splits: > * B,C vs. A > * C vs. A, B > * B vs. A, C > This means we communicate twice as much data as needed for these features. > We should eliminate these duplicate splits within the spark.ml implementation > since the spark.mllib implementation will be removed before long (and will > instead call into spark.ml). -- This message was sent by Atlassian JIRA (v6.3.4#6332) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14940316#comment-14940316
]
Seth Hendrickson commented on SPARK-10788:
--
Yes, much clearer. I can work on this task.
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14940343#comment-14940343
]
Joseph K. Bradley commented on SPARK-10788:
---
OK, thanks!
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14940345#comment-14940345
]
Joseph K. Bradley commented on SPARK-10788:
---
Though I should say: I should probably put this as Minor priority. It's not a
huge savings, and it's likely a somewhat complex change. If you have other
things you're working on, I'd prioritize those instead.
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>
> Decision trees in spark.ml (RandomForest.scala) communicate twice as much
> data as needed for unordered categorical features. Here's an example.
> Say there are 3 categories A, B, C. We consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we collect statistics for each of the 6 subsets of categories (3 *
> 2 = 6). However, we could instead collect statistics for the 3 subsets on
> the left-hand side of the 3 possible splits: A and A,B and A,C. If we also
> have stats for the entire node, then we can compute the stats for the 3
> subsets on the right-hand side of the splits. In pseudomath: {{stats(B,C) =
> stats(A,B,C) - stats(A)}}.
> We should eliminate these extra bins within the spark.ml implementation since
> the spark.mllib implementation will be removed before long (and will instead
> call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-10788) Decision Tree duplicates bins for unordered categorical features
[
https://issues.apache.org/jira/browse/SPARK-10788?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=14936219#comment-14936219
]
Seth Hendrickson commented on SPARK-10788:
--
[~josephkb] I'm interested in working on this issue, but I'm not sure I see the
problem. Looking through ML RandomForest implementation I found that
{{numBins}} for unordered features is {{def numUnorderedBins(arity: Int): Int =
2 * ((1 << arity - 1) - 1)}} and that {{numSplits}} is just {{numBins / 2}}.
In the 3 category example: {{numBins = 2 * (( 1 << (3 - 1)) - 1) = 6}} and so
the number of splits considered is {{numSplits = 6 / 2 = 3}}. This seems to be
the same as in the MLlib implementation. Perhaps I am overlooking something.
I'd appreciate any feedback...
> Decision Tree duplicates bins for unordered categorical features
>
>
> Key: SPARK-10788
> URL: https://issues.apache.org/jira/browse/SPARK-10788
> Project: Spark
> Issue Type: Improvement
> Components: ML
>Reporter: Joseph K. Bradley
>
> Decision trees in spark.ml (RandomForest.scala) effectively creates a second
> copy of each split. E.g., if there are 3 categories A, B, C, then we should
> consider 3 splits:
> * A vs. B, C
> * A, B vs. C
> * A, C vs. B
> Currently, we also consider the 3 flipped splits:
> * B,C vs. A
> * C vs. A, B
> * B vs. A, C
> This means we communicate twice as much data as needed for these features.
> We should eliminate these duplicate splits within the spark.ml implementation
> since the spark.mllib implementation will be removed before long (and will
> instead call into spark.ml).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
