yababoost.java

Boosting算法软件包

		if(count_t_over_s > NUM_ITERATIONS_FINISH_GAME){
		    t = m_s + 0.001;  // m_s is updated after loop
		    break;
		}
		continue;
	    }
	    
	    if (t < STEP_EPS) {
		t = STEP_EPS;
		t_step = -t_step;
		continue;
	    }
	      
	    alpha = 0;
	    //System.out.print("\nt: " + t);
	    double alpha_step = 0.1;
	    while(Math.abs(alpha_step) > STEP_EPS) {

		// Increment alpha
		alpha += alpha_step;
		//System.out.print("   alpha: " + alpha);
		
		// Deal with boundary cases, keep margin normalized
		if(alpha < 0 || alpha > 1) {
		    alpha = Math.round(alpha);
		    alpha_step = -alpha_step;
		    continue;
		}
		
		// calculate constraints for values of alpha and t
		vars = calc_constraints (alpha, t, examples);

		// reverse alpha search direction
		if(sign(vars.B) != sign(alpha_step)) alpha_step /= -2;	
	    }
	    
	    System.out.format("\tYabaBoost: (alpha=%.4f, t=%.4f) -> "
			      + "(corr=%.6f, pot_diff=%.6f, pot_diff=%.6f), "
			      + "potential=%.6f\n", alpha, t, vars.B, vars.E,
			      m_initialPotential - vars.Potential, vars.Potential);

	    // reverse t search direction
	    vars.E = m_initialPotential - vars.Potential;
	    if(sign(vars.E) != sign(t_step)) t_step /= -2; 
	}

	// The bisection (binary search) alpha and t
	double bs_alpha = alpha;
	double bs_t = t;

	// We use the binary search alpha and t
	alpha = bs_alpha;
	t = bs_t;

	m_oldS = m_s;
	m_s -= t;
	  
        System.out.format("YabaBoost: alpha=%.4f, t=%.4f, time left=%.4f, " 
                          + "potential=%.4f, theta=%.4f\n", alpha, t, m_s, vars.Potential, m_theta);	  

	System.out.println("Binary Search gives alpha=" + bs_alpha + ", t=" + bs_t);
	System.out.println("We use binary searchalpha=" + alpha + ", t=" + t);
	System.out.println("Objective function is: gamma + avg_pot_diff = " 
			   + vars.B + " + " + vars.E + " = " + (vars.B + vars.E));
	System.out.println("Time remaining in game: " + m_s);


	/*
	 * When we can't obtain the potential we wanted, we need to
	 * adjust the paramters.  We adjust theta and c1 to maintain a
	 * constant potential.
	 */
	double CONSTRAINT_EPS = 0.01;
	double EPS = 0.001;
	if (m_s > FINISH_GAME_NOW && Math.abs(vars.Potential-m_initialPotential)>CONSTRAINT_EPS) {
	    System.err.println("Average potential difference is too big!");
/*
	    m_s = m_oldS;
	    System.err.println("Outputting all data to outfile!");
	    dump_everything(vars);
	    
	    s = m_c - m_s;
	    double old_mu = m_theta - m_c1* ( Math.exp(-s) - Math.exp(-m_c) );

	    double theta_step = 0;
	    if(vars.Potential-m_initialPotential > 0) {
		theta_step = - THETA_UPDATE_STEP;
	    } else if(vars.Potential-m_initialPotential < 0) {
		theta_step = THETA_UPDATE_STEP/(Math.PI/3); // irrational number
	    }
	    m_theta += theta_step;
	    m_c1 = m_c1 + theta_step / (Math.exp(-(0)) - Math.exp(-m_c));

	    double new_mu = m_theta - m_c1* ( Math.exp(-s) - Math.exp(-m_c) );
	    
	    System.out.println("old_mu="+old_mu+", new_mu="+new_mu);
	    double margin = 0;
	    s = 0;
	    double mu = m_theta - m_c1 * (Math.exp(-s) - Math.exp(-m_c));
	    double sd = Math.sqrt(m_c2 * (Math.exp(-2*s) - Math.exp(-2*m_c))) + FINISH_GAME_NOW;
	    double pot = (1 - erf((margin-mu)/sd)) / 2;
	    System.out.println("New potential is: " + pot);
	    System.out.println("New intial potential is: " + calculatePotential(0, m_c));
	    System.out.println("New theta is:" + m_theta);
	    return solve_constraints(hyp_err);

*/
	}

	if (Math.abs(vars.B) > CONSTRAINT_EPS) {
	    System.err.println("CORRELATION IS TOO BIG!!!");
	}

	if (t < 0) {
	    dump_everything(vars);
	    System.err.println("The change in time is negtive!");
	    System.err.println("Outputting all data to outfile!");
	    System.exit(2);
	}

	/*
	 * Weird things happen towards the end of the game
	 * (underflow/overflow).  So we cheat a little and terminate
	 * before the actual end of the game.
	 */
	if (m_s < FINISH_GAME_NOW) {
	    m_s = -1;
	}

	m_lastAlpha = alpha;
	return alpha;
    }

    /**
     *  Update the examples, m_margins, and m_weights using a 
     *  normalized update rule.  When m_s reaches
     *  the stopping criterion of m_s &lt; 0, this update returns 
     *  immediately and does not actually do any further updating.  
     *  @param predictions values for examples
     *  @param exampleIndex the list of examples to update
     */  
    public void update(Prediction[] predictions, int[][] exampleIndex) {
	if (m_s < 0){
	    return;
	}
    
	for (int i= 0; i < exampleIndex.length; i++) {
	    double p = predictions[i].getClassScores()[1];
	    if(Math.abs(p) > 1){
		System.err.println("System cannot be normalized!  alpha="+Math.abs(p));
	    }
	    double[] value = new double[] { -p, p };
	    int[] indexes = exampleIndex[i];
	    for (int j= 0; j < indexes.length; j++) {
		int example   = indexes[j];
		double alpha = Math.abs(p);

		// Set margins to new margin
		// value[m_labels[example]] is equal to alpha*step
		double EPS = 0.0001;
		if (Math.abs(p) - m_lastAlpha  > EPS) {
		    System.err.println("Prediction was messed up!");
		    System.err.println("alpha was: " + m_lastAlpha);
		    System.err.println("prediction is: " + Math.abs(p));
		}
		m_oldMargins[example] = m_margins[example];
		m_margins[example] = (1-alpha)*m_margins[example] 
		    + value[m_labels[example]];

		if(Math.abs(m_margins[example]) > 1){
		    System.out.println("m_margins[" +example+ "]: " 
				       + m_margins[example] + " greater than 1!!!!");
		}
	    }
	}


	if (m_hypPredictions.length != m_margins.length || m_hypPredictions.length != m_numExamples) {
	    System.err.println("WARNING: m_hypPredictions is not the same length as the margins");
	}
	for (int i=0; i < m_hypPredictions.length; i++) {
	    m_oldWeights[i]= m_weights[i];
	    m_totalWeight -= m_weights[i];
	    m_weights[i] = calculateWeight(m_margins[i]);
	    m_totalWeight += m_weights[i];

	    m_totalPotential -= m_potentials[i];
	    m_potentials[i] = calculatePotential(m_margins[i]);
	    m_totalPotential += m_potentials[i];
	}
    }


    /**
     * @param margin
     * @return weight of any example with the given margin
     */
    public double calculateWeight(double margin) {
	return calculateWeight(margin, m_s);
    }

    /**
     * @param margin
     * @return potential of example with given margin
     */
    public double calculatePotential(double margin) {
	return calculatePotential(margin, m_s);
    }

    /**
     * @param margin
     * @param time remaining in game
     * @return weight of any example with the given margin
     */
    public double calculateWeight(double margin, double time_remaining) {
	double s  = m_c - time_remaining;
	double mu = m_theta - m_c1* ( Math.exp(-s) - Math.exp(-m_c) );
	double sd = Math.sqrt(m_c2*(Math.exp(-2*s) - Math.exp(-2*m_c))) + FINISH_GAME_NOW;
	double norm = 1 / Math.sqrt(Math.PI * sd * sd); 
	double ret = norm * Math.exp(- Math.pow((margin-mu)/sd,2));

	if (USE_CONFIDENCE) {
	    if (margin < mu) 
		ret = 0;
	    else 
		ret = 2*ret;
	}

  	return ret;
    }


    /**
     * @param margin
     * @return potential of example with given margin
     */
    public double calculatePotential(double margin, double time_remaining) {
	double s  = m_c - time_remaining;
	double mu = m_theta - m_c1 * (Math.exp(-s) - Math.exp(-m_c));
	double sd = Math.sqrt(m_c2 * (Math.exp(-2*s) - Math.exp(-2*m_c))) + FINISH_GAME_NOW;
	double pot = (1 - erf((margin-mu)/sd)) / 2;
	if (USE_CONFIDENCE) {
	    pot = Math.min(2*pot, 1.0);
	}
	/*
	System.out.println("S:"+s);
	System.out.println("mu:"+mu);
	System.out.println("sd:"+sd);
	System.out.println("margin:"+margin);
	System.out.println("pot:"+pot);
	System.out.println("pot:"+ -(pot*2 -1));
        System.out.println("YabaBoost:\n" 
			   + "\t m_c: " + m_c + "\n"
			   + "\t m_c1: " + m_c1 + "\n"
			   + "\t m_c2: " + m_c2 + "\n"
			   + "\t m_theta: " + m_theta + "\n");
	*/
  	return pot;
    }


    public String getParamString() {
        String ret = String.format("YabaBoost s=%.4f c=%.4f c1=%.4f c2=%.4f theta=%.4f confidence=%b ", m_s, m_c, m_c1, m_c2, m_theta, USE_CONFIDENCE);
        return ret;
    }



    /**
     * See comments for BrownBoost.BrownBag.
     * @author Aaron Arvey
     */
    class YabaBag extends BrownBoost.BrownBag {

	protected YabaBag(int[] list) {
	    super(list);
	}
 
	protected YabaBag() {
	    super();
	}

	/** compute the binary prediction associated with this bag */
	public MixedBinaryPrediction calcPrediction(double alpha) {
	    MixedBinaryPrediction ret = new MixedBinaryPrediction(0);
	    try {
		ret = new MixedBinaryPrediction(m_w[1] > m_w[0] ? 1.0 : -1.0 );
	    } catch (NotNormalizedPredException e){
		System.err.println(e.getStackTrace());
		System.err.println(e.getMessage());
		System.exit(2);
	    }
	    ret.scale(alpha);
	    return ret;
	}
      
      
	/** Place holder to ensure that this function is not used in BrownBoost. */
	public MixedBinaryPrediction calcPrediction(){
	    System.err.println("Need to have alpha for prediction in BrownBag.calcPrediction()!");
	    System.exit(2);
	    return new MixedBinaryPrediction(0);
	}
      
      
	/** constructor that copies an existing bag */
	protected YabaBag(YabaBag bag) {
	    super(bag);
	}
      
      
	/** Output the weights in the bag */
	public String toString() {
	    String s= "YabaBag.\t w0=" + m_w[0] + "\t w1=" + m_w[1] + "\n";
	    return s;
	}
      
	
    } /* End YabaBag */
    
    
    

    public Bag newBag(int[] list) {
	return new YabaBag(list);
    }

    public Bag newBag() {
	return new YabaBag();
    }

    public Bag newBag(Bag bag) {
	return new YabaBag((YabaBag) bag);
    }

    /**
     * Returns the prediction associated with a bag representing a subset of the
     * data.
     */
    protected Prediction getPrediction(Bag b) {
	return ((YabaBag) b).calcPrediction();
    }


    protected MixedBinaryPrediction getZeroPred() {
	return new MixedBinaryPrediction(0);
    }

} /* End YabaBoost Class */