You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@madlib.apache.org by iyerr3 <gi...@git.apache.org> on 2017/06/21 07:28:14 UTC
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
GitHub user iyerr3 opened a pull request:
https://github.com/apache/incubator-madlib/pull/142
DT: Include NULL rows in count for termination check
When the primary split feature for a node is computed, the statistics of
rows going to the true and false side don't include the rows that have
NULL value for this split feature. These "NULL" rows can only be
included in the statistics during the next pass when surrogates have
been trained. This commit ensures that in the presence of NULL rows, we
don't terminate prematurely by comparing with a lower count.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/iyerr3/incubator-madlib bugfix/dt_accurate_termination
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-madlib/pull/142.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 #142
----
commit 7213d3008d657df323a577111355aae6354ef663
Author: Rahul Iyer <ri...@apache.org>
Date: 2017-06-21T06:31:06Z
DT: Include NULL rows in count for termination check
When the primary split feature for a node is computed, the statistics of
rows going to the true and false side don't include the rows that have
NULL value for this split feature. These "NULL" rows can only be
included in the statistics during the next pass when surrogates have
been trained. This commit ensures that in the presence of NULL rows, we
don't terminate prematurely by comparing with a lower count.
----
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/84/
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123573305
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -446,21 +446,20 @@ DecisionTree<Container>::updatePrimarySplit(
predictions.row(falseChild(node_index)) = false_stats;
// true_stats and false_stats only include the tuples for which the primary
- // split is NULL. The number of tuples in these stats need to be stored to
+ // split is not NULL. The number of tuples in these stats need to be stored to
// compute a majority branch during surrogate training.
uint64_t true_count = statCount(true_stats);
uint64_t false_count = statCount(false_stats);
- nonnull_split_count(node_index*2) = static_cast<double>(true_count);
- nonnull_split_count(node_index*2 + 1) = static_cast<double>(false_count);
-
- // current node's children won't split if,
- // 1. children are pure (responses are too similar to split further)
- // 2. children are too small to split further (count < min_split)
- bool children_wont_split = (isChildPure(true_stats) &&
- isChildPure(false_stats) &&
- true_count < min_split &&
- false_count < min_split
- );
+ nonnull_split_count(trueChild(node_index)) = static_cast<double>(true_count);
+ nonnull_split_count(falseChild(node_index)) = static_cast<double>(false_count);
+
+ // current node's child won't split if,
+ // 1. child is pure (responses are too similar to split further) OR
--- End diff --
Why did we change the logic on children_wont_split?
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/86/
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123855465
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -446,21 +446,20 @@ DecisionTree<Container>::updatePrimarySplit(
predictions.row(falseChild(node_index)) = false_stats;
// true_stats and false_stats only include the tuples for which the primary
- // split is NULL. The number of tuples in these stats need to be stored to
+ // split is not NULL. The number of tuples in these stats need to be stored to
// compute a majority branch during surrogate training.
uint64_t true_count = statCount(true_stats);
uint64_t false_count = statCount(false_stats);
- nonnull_split_count(node_index*2) = static_cast<double>(true_count);
- nonnull_split_count(node_index*2 + 1) = static_cast<double>(false_count);
-
- // current node's children won't split if,
- // 1. children are pure (responses are too similar to split further)
- // 2. children are too small to split further (count < min_split)
- bool children_wont_split = (isChildPure(true_stats) &&
- isChildPure(false_stats) &&
- true_count < min_split &&
- false_count < min_split
- );
+ nonnull_split_count(trueChild(node_index)) = static_cast<double>(true_count);
+ nonnull_split_count(falseChild(node_index)) = static_cast<double>(false_count);
+
+ // current node's child won't split if,
+ // 1. child is pure (responses are too similar to split further) OR
--- End diff --
Thanks, I agree that this makes more sense.
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123618828
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -486,8 +485,18 @@ DecisionTree<Container>::expand(const Accumulator &state,
Index stats_i = static_cast<Index>(state.stats_lookup(i));
assert(stats_i >= 0);
- // 1. Set the prediction for current node from stats of all rows
- predictions.row(current) = state.node_stats.row(stats_i);
+ if (statCount(predictions.row(current)) !=
+ statCount(state.node_stats.row(stats_i))){
+ // Predictions for each node is set by its parent using stats
+ // recorded while training parent node. These stats do not include
+ // rows that had a NULL value for the primary split feature.
+ // The NULL count is included in the 'node_stats' while training
+ // current node. Further, presence of NULL rows indicate that
+ // stats used for deciding 'children_wont_split' are inaccurate.
+ // Hence avoid using the flag to decide termination.
+ predictions.row(current) = state.node_stats.row(stats_i);
+ children_wont_split = false;
+ }
--- End diff --
Let me try to rephrase my question:
Assume the if check at lines 490-491 is `true`. `children_wont_split` will be set to `false`. This variable is used with an & operator at line 568. That means the second boolean value is irrelevant, the result will always be `false`. In this case, do we need the 2 double for loops from lines 516-547?
The compiler might calculate the backwards slice of this instruction to find its optimal location but I don't think we should rely on that.
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
When I ran the RF example thrice - twice I got 100% and once I got 13/14 (~93%). I guess there's some randomness there (which is expected).
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123622385
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -486,8 +485,18 @@ DecisionTree<Container>::expand(const Accumulator &state,
Index stats_i = static_cast<Index>(state.stats_lookup(i));
assert(stats_i >= 0);
- // 1. Set the prediction for current node from stats of all rows
- predictions.row(current) = state.node_stats.row(stats_i);
+ if (statCount(predictions.row(current)) !=
+ statCount(state.node_stats.row(stats_i))){
+ // Predictions for each node is set by its parent using stats
+ // recorded while training parent node. These stats do not include
+ // rows that had a NULL value for the primary split feature.
+ // The NULL count is included in the 'node_stats' while training
+ // current node. Further, presence of NULL rows indicate that
+ // stats used for deciding 'children_wont_split' are inaccurate.
+ // Hence avoid using the flag to decide termination.
+ predictions.row(current) = state.node_stats.row(stats_i);
+ children_wont_split = false;
+ }
--- End diff --
- `children_wont_split` is **one** of the factors that determines if training should stop after current iteration. `children_wont_split=true` implies training stops; `children_wont_split=false` implies other flags determine termination.
- The lines 516-547 are finding the best feature to split on and are necessary - independent of `children_wont_split` and independent of the result of line 490.
I could exchange sections 1 and 2 since they're independent, if that helps in reading the code.
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123856874
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -486,8 +485,18 @@ DecisionTree<Container>::expand(const Accumulator &state,
Index stats_i = static_cast<Index>(state.stats_lookup(i));
assert(stats_i >= 0);
- // 1. Set the prediction for current node from stats of all rows
- predictions.row(current) = state.node_stats.row(stats_i);
+ if (statCount(predictions.row(current)) !=
+ statCount(state.node_stats.row(stats_i))){
+ // Predictions for each node is set by its parent using stats
+ // recorded while training parent node. These stats do not include
+ // rows that had a NULL value for the primary split feature.
+ // The NULL count is included in the 'node_stats' while training
+ // current node. Further, presence of NULL rows indicate that
+ // stats used for deciding 'children_wont_split' are inaccurate.
+ // Hence avoid using the flag to decide termination.
+ predictions.row(current) = state.node_stats.row(stats_i);
+ children_wont_split = false;
+ }
--- End diff --
No need to exchange anything. After reading through the `updatePrimarySplit` function, I understand why it is needed even if its boolean output doesn't affect the variable.
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/incubator-madlib/pull/142
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123577006
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -486,8 +485,18 @@ DecisionTree<Container>::expand(const Accumulator &state,
Index stats_i = static_cast<Index>(state.stats_lookup(i));
assert(stats_i >= 0);
- // 1. Set the prediction for current node from stats of all rows
- predictions.row(current) = state.node_stats.row(stats_i);
+ if (statCount(predictions.row(current)) !=
+ statCount(state.node_stats.row(stats_i))){
+ // Predictions for each node is set by its parent using stats
+ // recorded while training parent node. These stats do not include
+ // rows that had a NULL value for the primary split feature.
+ // The NULL count is included in the 'node_stats' while training
+ // current node. Further, presence of NULL rows indicate that
+ // stats used for deciding 'children_wont_split' are inaccurate.
+ // Hence avoid using the flag to decide termination.
+ predictions.row(current) = state.node_stats.row(stats_i);
+ children_wont_split = false;
+ }
--- End diff --
Should we move the sections 2 and 3 under the else clause of this if check (except the `children_not_allocated` check at line 559)? Since `children_wont_split` is set to false, the calculation at line 564 should be redundant.
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
DT output seems correct, it seems RT randomness was the cause. LGTM +1
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123597014
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -486,8 +485,18 @@ DecisionTree<Container>::expand(const Accumulator &state,
Index stats_i = static_cast<Index>(state.stats_lookup(i));
assert(stats_i >= 0);
- // 1. Set the prediction for current node from stats of all rows
- predictions.row(current) = state.node_stats.row(stats_i);
+ if (statCount(predictions.row(current)) !=
+ statCount(state.node_stats.row(stats_i))){
+ // Predictions for each node is set by its parent using stats
+ // recorded while training parent node. These stats do not include
+ // rows that had a NULL value for the primary split feature.
+ // The NULL count is included in the 'node_stats' while training
+ // current node. Further, presence of NULL rows indicate that
+ // stats used for deciding 'children_wont_split' are inaccurate.
+ // Hence avoid using the flag to decide termination.
+ predictions.row(current) = state.node_stats.row(stats_i);
+ children_wont_split = false;
+ }
--- End diff --
The if statement is basically checking if a NULL row is present in the `current` node and if yes, then the predictions for that node is updated. I've added an explanation in the comments for both statements on why they're needed. If the explanation is not clear then please add more details on what would help you understand.
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/88/
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/89/
---
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.
---
[GitHub] incubator-madlib pull request #142: DT: Include NULL rows in count for termi...
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/142#discussion_r123596546
--- Diff: src/modules/recursive_partitioning/DT_impl.hpp ---
@@ -446,21 +446,20 @@ DecisionTree<Container>::updatePrimarySplit(
predictions.row(falseChild(node_index)) = false_stats;
// true_stats and false_stats only include the tuples for which the primary
- // split is NULL. The number of tuples in these stats need to be stored to
+ // split is not NULL. The number of tuples in these stats need to be stored to
// compute a majority branch during surrogate training.
uint64_t true_count = statCount(true_stats);
uint64_t false_count = statCount(false_stats);
- nonnull_split_count(node_index*2) = static_cast<double>(true_count);
- nonnull_split_count(node_index*2 + 1) = static_cast<double>(false_count);
-
- // current node's children won't split if,
- // 1. children are pure (responses are too similar to split further)
- // 2. children are too small to split further (count < min_split)
- bool children_wont_split = (isChildPure(true_stats) &&
- isChildPure(false_stats) &&
- true_count < min_split &&
- false_count < min_split
- );
+ nonnull_split_count(trueChild(node_index)) = static_cast<double>(true_count);
+ nonnull_split_count(falseChild(node_index)) = static_cast<double>(false_count);
+
+ // current node's child won't split if,
+ // 1. child is pure (responses are too similar to split further) OR
--- End diff --
I've added a new commit with more explanation. The short answer is that the previous logic was incorrect and resulting in longer trees.
---
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.
---
[GitHub] incubator-madlib issue #142: DT: Include NULL rows in count for termination ...
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on the issue:
https://github.com/apache/incubator-madlib/pull/142
I need more info on the RF docs discrepancy.
- Which example is giving the lower than 100% training accuracy?
- How do the trees look?
- Can we replicate in decision tree since that is easier to debug?
On its own, less than 100% accuracy is not wrong, but if the tree is not as long as it should be (i.e. prematurely terminating) then a problem has been introduced here.
---
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.
---