private static double pruneErrorBased(TreeNodeVisitor parent, int pathFollowed, TreeNodeVisitor current, ClassificationDataSet testSet, double alpha)
    {
        //TODO this does a lot of redundant computation. Re-write this code to keep track of where datapoints came from to avoid redudancy. 
        if(current == null || testSet.isEmpty())
            return 0;
        else if(current.isLeaf())//return number of errors
        {
            int errors = 0;
            double N = 0;
            for(int i = 0; i < testSet.size(); i++)
            {
		if (current.localClassify(testSet.getDataPoint(i)).mostLikely() != testSet.getDataPointCategory(i))
		    errors += testSet.getWeight(i);
		N += testSet.getWeight(i);
	    }
            return computeBinomialUpperBound(N, alpha, errors);
        }
        List<ClassificationDataSet> splitSet = new ArrayList<>(current.childrenCount());
	IntList hadMissing = new IntList();
        for(int i = 0; i < current.childrenCount(); i++)
            splitSet.add(testSet.emptyClone());
        
        int localErrors = 0;
        double subTreeScore = 0;
        
        double N = 0.0;
	double N_missing = 0.0;
	double[] fracs =new double[splitSet.size()];
	
        for(int i = 0; i < testSet.size(); i++)
        {
            DataPoint dp = testSet.getDataPoint(i);
	    int y_i = testSet.getDataPointCategory(i);
	    double w_i = testSet.getWeight(i);
	    
            if(current.localClassify(dp).mostLikely() != y_i)
                localErrors+=w_i;
            
            
            int path = current.getPath(dp);
            if(path >= 0)
	    {
		N += w_i;
                splitSet.get(path).addDataPoint(dp, y_i, w_i);
		fracs[path] += w_i;
	    }
            else
	    {
                hadMissing.add(i);
		N_missing += w_i;
	    }
        }
	for(int i = 0; i < fracs.length; i++)
	    fracs[i] /= N;
        
        if(!hadMissing.isEmpty())
            DecisionStump.distributMissing(splitSet, fracs, testSet, hadMissing);
        
        //Find child wich gets the most of the test set as the candidate for sub-tree replacement
        int maxChildCount = 0;
        int maxChild = -1;
        for(int path = 0; path < splitSet.size(); path++)
            if(!current.isPathDisabled(path))
            {
                subTreeScore += pruneErrorBased(current, path, current.getChild(path), splitSet.get(path), alpha);
                
                if(maxChildCount < splitSet.get(path).size())
                {
                    maxChildCount = splitSet.get(path).size();
                    maxChild = path;
                }
            }

        /* Original uses normal approximation of p + Z_alpha * sqrt(p (1-p) / n).
         * Instead, just compute exact using inverse beta
         * Upper Bound = 1.0 - BetaInv(alpha, n-k, k+1)
         */
        final double prunedTreeScore = computeBinomialUpperBound(N+N_missing, alpha, localErrors);

        double maxChildTreeScore;
        if(maxChild == -1)
            maxChildTreeScore = Double.POSITIVE_INFINITY;
        else
        {
            TreeNodeVisitor maxChildNode = current.getChild(maxChild);
            int otherE = 0;
            for (int path = 0; path < splitSet.size(); path++)
	    {
		ClassificationDataSet split = splitSet.get(path);
		for(int i = 0; i < split.size(); i++)
                        if (maxChildNode.classify(split.getDataPoint(i)).mostLikely() != split.getDataPointCategory(i))
                            otherE+=split.getWeight(i);
	    }
	    
            maxChildTreeScore = computeBinomialUpperBound(N+N_missing, alpha, otherE);
        }
        
        
        if(maxChildTreeScore < prunedTreeScore && maxChildTreeScore < subTreeScore && parent != null)
        {
            try//NodeVisitor may not support setPath method, which is optional
            {
                parent.setPath(pathFollowed, current.getChild(maxChild));

                return maxChildTreeScore;
            }
            catch(UnsupportedOperationException ex)
            {
                //fall out to others, this is ok
            }
        }
        //MaxChildTreeScore is not the min, or it was not supported - so we do not compare against it any more
        if(prunedTreeScore < subTreeScore  )
        {
            for(int i = 0; i < current.childrenCount(); i++)
                current.disablePath(i);
            return prunedTreeScore;
        }
        else//no change
            return subTreeScore;
        
    }
private static double pruneErrorBased ( TreeNodeVisitor parent , int pathFollowed , TreeNodeVisitor current , ClassificationDataSet testSet , double alpha ) { if ( current == null || testSet . isEmpty ( ) ) return 0 ; else if ( current . isLeaf ( ) ) { int errors = 0 ; double N = 0 ; for ( int i = 0 ; i < testSet . size ( ) ; i ++ ) { if ( current . localClassify ( testSet . getDataPoint ( i ) ) . mostLikely ( ) != testSet . getDataPointCategory ( i ) ) errors += testSet . getWeight ( i ) ; N += testSet . getWeight ( i ) ; } return computeBinomialUpperBound ( N , alpha , errors ) ; } List < ClassificationDataSet > splitSet = new ArrayList < > ( current . childrenCount ( ) ) ; IntList hadMissing = new IntList ( ) ; for ( int i = 0 ; i < current . childrenCount ( ) ; i ++ ) splitSet . add ( testSet . emptyClone ( ) ) ; int localErrors = 0 ; double subTreeScore = 0 ; double N = 0.0 ; double N_missing = 0.0 ; double [ ] fracs = new double [ splitSet . size ( ) ] ; for ( int i = 0 ; i < testSet . size ( ) ; i ++ ) { DataPoint dp = testSet . getDataPoint ( i ) ; int y_i = testSet . getDataPointCategory ( i ) ; double w_i = testSet . getWeight ( i ) ; if ( current . localClassify ( dp ) . mostLikely ( ) != y_i ) localErrors += w_i ; int path = current . getPath ( dp ) ; if ( path >= 0 ) { N += w_i ; splitSet . get ( path ) . addDataPoint ( dp , y_i , w_i ) ; fracs [ path ] += w_i ; } else { hadMissing . add ( i ) ; N_missing += w_i ; } } for ( int i = 0 ; i < fracs . length ; i ++ ) fracs [ i ] /= N ; if ( ! hadMissing . isEmpty ( ) ) DecisionStump . distributMissing ( splitSet , fracs , testSet , hadMissing ) ; int maxChildCount = 0 ; int maxChild = - 1 ; for ( int path = 0 ; path < splitSet . size ( ) ; path ++ ) if ( ! current . isPathDisabled ( path ) ) { subTreeScore += pruneErrorBased ( current , path , current . getChild ( path ) , splitSet . get ( path ) , alpha ) ; if ( maxChildCount < splitSet . get ( path ) . size ( ) ) { maxChildCount = splitSet . get ( path ) . size ( ) ; maxChild = path ; } } final double prunedTreeScore = computeBinomialUpperBound ( N + N_missing , alpha , localErrors ) ; double maxChildTreeScore ; if ( maxChild == - 1 ) maxChildTreeScore = Double . POSITIVE_INFINITY ; else { TreeNodeVisitor maxChildNode = current . getChild ( maxChild ) ; int otherE = 0 ; for ( int path = 0 ; path < splitSet . size ( ) ; path ++ ) { ClassificationDataSet split = splitSet . get ( path ) ; for ( int i = 0 ; i < split . size ( ) ; i ++ ) if ( maxChildNode . classify ( split . getDataPoint ( i ) ) . mostLikely ( ) != split . getDataPointCategory ( i ) ) otherE += split . getWeight ( i ) ; } maxChildTreeScore = computeBinomialUpperBound ( N + N_missing , alpha , otherE ) ; } if ( maxChildTreeScore < prunedTreeScore && maxChildTreeScore < subTreeScore && parent != null ) { try { parent . setPath ( pathFollowed , current . getChild ( maxChild ) ) ; return maxChildTreeScore ; } catch ( UnsupportedOperationException ex ) { } } if ( prunedTreeScore < subTreeScore ) { for ( int i = 0 ; i < current . childrenCount ( ) ; i ++ ) current . disablePath ( i ) ; return prunedTreeScore ; } else return subTreeScore ; }
@param parent the parent node, or null if there is no parent
@param pathFollowed the path from the parent node to the current node
@param current the current node to evaluate
@param testSet the set of points to estimate error from
@param alpha the Confidence
@return expected upperbound on errors