private void treeShap ( R feat , float [ ] phi , N node , S nodeStat , int unique_depth , PathPointer parent_unique_path , float parent_zero_fraction , float parent_one_fraction , int parent_feature_index , int condition , int condition_feature , float condition_fraction ) { // stop if we have no getWeight coming down to us if ( condition_fraction == 0 ) return ; // extend the unique path PathPointer unique_path = parent_unique_path . move ( unique_depth ) ; if ( condition == 0 || condition_feature != parent_feature_index ) { extendPath ( unique_path , unique_depth , parent_zero_fraction , parent_one_fraction , parent_feature_index ) ; } final int split_index = node . getSplitIndex ( ) ; // leaf node if ( node . isLeaf ( ) ) { for ( int i = 1 ; i <= unique_depth ; ++ i ) { final float w = unwoundPathSum ( unique_path , unique_depth , i ) ; final PathElement el = unique_path . get ( i ) ; phi [ el . feature_index ] += w * ( el . one_fraction - el . zero_fraction ) * node . getLeafValue ( ) * condition_fraction ; } // internal node } else { // find which branch is "hot" (meaning x would follow it) final int hot_index = node . next ( feat ) ; final int cold_index = hot_index == node . getLeftChildIndex ( ) ? node . getRightChildIndex ( ) : node . getLeftChildIndex ( ) ; final float w = nodeStat . getWeight ( ) ; final float hot_zero_fraction = stats [ hot_index ] . getWeight ( ) / w ; final float cold_zero_fraction = stats [ cold_index ] . getWeight ( ) / w ; float incoming_zero_fraction = 1 ; float incoming_one_fraction = 1 ; // see if we have already split on this feature, // if so we undo that split so we can redo it for this node int path_index = 0 ; for ( ; path_index <= unique_depth ; ++ path_index ) { if ( unique_path . get ( path_index ) . feature_index == split_index ) break ; } if ( path_index != unique_depth + 1 ) { incoming_zero_fraction = unique_path . get ( path_index ) . zero_fraction ; incoming_one_fraction = unique_path . get ( path_index ) . one_fraction ; unwindPath ( unique_path , unique_depth , path_index ) ; unique_depth -= 1 ; } // divide up the condition_fraction among the recursive calls float hot_condition_fraction = condition_fraction ; float cold_condition_fraction = condition_fraction ; if ( condition > 0 && split_index == condition_feature ) { cold_condition_fraction = 0 ; unique_depth -= 1 ; } else if ( condition < 0 && split_index == condition_feature ) { hot_condition_fraction *= hot_zero_fraction ; cold_condition_fraction *= cold_zero_fraction ; unique_depth -= 1 ; } treeShap ( feat , phi , nodes [ hot_index ] , stats [ hot_index ] , unique_depth + 1 , unique_path , hot_zero_fraction * incoming_zero_fraction , incoming_one_fraction , split_index , condition , condition_feature , hot_condition_fraction ) ; treeShap ( feat , phi , nodes [ cold_index ] , stats [ cold_index ] , unique_depth + 1 , unique_path , cold_zero_fraction * incoming_zero_fraction , 0 , split_index , condition , condition_feature , cold_condition_fraction ) ; } }
recursive computation of SHAP values for a decision tree