Direct 0-1 Loss Minimization and Margin Maximization with Boosting
We propose a boosting method, DirectBoost, a greedy coordinate descent algorithm that builds an ensemble classifier of weak classifiers through directly minimizing empirical classification error over labeled training examples; once the training classification error is reduced to a local coordinatewise minimum, DirectBoost runs a greedy coordinate ascent algorithm that continuously adds weak classifiers to maximize any targeted arbitrarily defined margins until reaching a local coordinatewise maximum of the margins in a certain sense. Experimental results on a collection of machine-learning benchmark datasets show that DirectBoost gives better results than AdaBoost, LogitBoost, LPBoost with column generation and BrownBoost, and is noise tolerant when it maximizes an n ′ th order bottom sample margin.
This paper presents a boosting method that directly 
      minimizes the empirical classification error that is defined based on the 
      indicator whether predicted y = observed y, the so-called 0-1 loss. The 
      proposed method first runs greedy coordinate descent to search the 
      coordinatewise minimum loss, and then runs coordinate ascent to expand the 
      margin. The method is interesting and novel, and offers some advantages. 
      The following concerns are raised. 1. It seems the authors assume 
      a hypothesis space which has a finite number of hypotheses because in the 
      algorithms 1 and 2, it loops on all hypotheses h at each iteration. For 
      instance, algorithm 1 finds all weak learners that lead to largest 
      classification error reduction at each iteration. What if users choose a 
      hypothesis space, such as linear functions? 2. At the end of 
      Algorithm 1, what is the rationale to update the weight of one weak 
      learner that gives the smallest exponential loss? Isn’t it still using a 
      convex loss function although in the early part of the algorithm, it uses 
      0-1 loss. 3. It also assumes that data is always separable as long 
      as the combined strong classifier is strong. What if it is not the case? 
      What if the chosen hypothesis space is not complex enough to separate a 
      given dataset. The paper states that algorithm 1 reaches a solution of 
      coordinatewise minimum. It also says the 0-1 loss reaches 0. What is the 
      definition of coordinatewise minimum? Is it actually a global minimum 
      because the lowest error would be 0. 4. When the second step 
      (margin maximization) starts, it starts from a region that would not get 
      the solution out of the 0 loss region, characterized by the value of d. It 
      is not clear how exactly this value of d is calculated instead of simply 
      saying “determine the lowest sample whose margin is decreasing”. 
      5. Given separable cases are assumed, the margin is always 
      positive in their formulation. What happens if there are negative margins 
      for inseparable cases? The second part of the algorithm would not run. 
      6. In the early paragraph of page 2, it says “it might escape the 
      region of minimum training error in order to achieve a larger margin”. In 
      the later section, the design of algorithm 2 will not allow the margin 
      maximization step go beyond zero 0-1 loss region. 7. Assuming a 
      weak learner can be obtained in a similar computational cost, DirectBoost 
      is certainly more computationally heavy for each iteration than AdaBoost. 
      In their experiments, what is the stopping criterion that they used for 
      AdaBoost? Why does AdaBoost need so many iterations? 8. It is not 
      that clear about the truly convincing advantage of the proposed method 
      over regular boosting methods.