Reservoir Boosting : Between Online and Offline Ensemble Learning
We propose to train an ensemble with the help of a reservoir in which the learning algorithm can store a limited number of samples. This novel approach lies in the area between offline and online ensemble approaches and can be seen either as a restriction of the former or an enhancement of the latter. We identify some basic strategies that can be used to populate this reservoir and present our main contribution, dubbed Greedy Edge Expectation Maximization (GEEM), that maintains the reservoir content in the case of Boosting by viewing the samples through their projections into the weak classifier response space. We propose an efficient algorithmic implementation which makes it tractable in practice, and demonstrate its efficiency experimentally on several compute-vision data-sets, on which it outperforms both online and offline methods in a memory constrained setting.
This paper proposes a new boosting method that 
      represents a tradeoff between online and offline learning. The main idea 
      of the method is to maintain a reservoir of training examples (of fixed 
      size) from which to train the weak learners. At each boosting iteration, 
      new examples are added to the reservoir and then a selection strategy is 
      used to reduce the reservoir to its original fixed size before the weak 
      learner is trained. Several naive selection strategies are proposed but 
      the main contribution of the paper is a more sophisticated selection 
      strategy whose goal is to remove examples from the reservoir so that a 
      weak learner trained on the reduced set will minimize the error computed 
      on the whole set before reduction. The resulting algorithm is applied on 
      four computer vision datasets, where it is shown to outperform several 
      other online boosting methods. The idea of using a reservoir is 
      original and very interesting. The derivation of the GEEM algorithm from 
      this initial idea is technically sound and the authors have been very 
      careful in designing an efficient solution. Experiments are done on only 
      four datasets but these datasets represent real computer vision problems 
      of practical interest. GEEM is compared with many different methods, 
      including some well-chosen baselines for the reservoir framework. The 
      authors seem to have taken great care to put other methods in the best 
      conditions for the comparison and despite this, the performance of GEEM is 
      clearly superior to all other methods. While I think that the 
      reservoir idea is very interesting per se, it's not clear which particular 
      learning setting or constraints the authors want to address with this idea 
      in the paper. Do they want to reduce computing times, to reduce memory 
      usage, to obtain the best possible predictive accuracy, or a combination 
      of those? This lack of a clear definition of the problem makes the 
      assessment of the significance of the method difficult. It clearly works 
      better than other online methods in terms of accuracy, but computing times 
      and memory usage seem worse. In terms of predictive performance, GEEM is 
      also probably worse than offline boosting (but this baseline is actually 
      not provided). I think that the paper should more clearly define the 
      specific constraints the method is targeting and then make the experiments 
      better reflect such constraints. At the moment, only test accuracies are 
      compared in the experiments and the authors have only put a constraint on 
      the number T of weak classifiers. In such conditions, offline boosting is 
      probably the best method. Some design choices also are not totally 
      convincing. In Section 3.1, the idea of selecting the subset B so that it 
      is as representative as possible of the entire set A does not seem so 
      natural to me. Ideally, the subset B should be selected so that the weak 
      learner that will be obtained from it will improve as much as possible the 
      current model. Making it as close as possible to the weak learner trained 
      from A does not make sense when A is not a good subset to train a weak 
      learner. So, a more natural selection criterion from B should not 
      necessarily depend on A. The choice of a perfect model h* in 3.3 is 
      justified but why not instead simply look for the optimal weak learner 
      from A and then project it on all Bs when doing the greedy search. The 
      computational cost of this operation would probably be negligible with 
      respect to the cost of the computation of the covariance matrix. 
      The paper is well written and mostly clear but it would be very 
      difficult however to re-implement the algorithm given its complexity and 
      also to reproduce the experiments as the settings of all tested algorithms 
      are mostly unknown (see some questions below). The authors will however 
      share their implementation upon publication. Other comments - 
      I find it difficult to see how logitboost could be combined with the 
      algorithm in Table 2, since logitboost as defined in (Friedman, Hastie, 
      and Tibshirani, 1998) uses weak learners in the form of regressors and 
      updates both the weights and the responses of these examples. Giving a 
      description of the whole algorithm could help. - It's not clear how 
      comparable are the different algorithms in the experiments. In particular, 
      are all algorithms actually seeing the exact same number of examples, ie. 
      is the number of calls to the filter function the same in each case? - 
      In the algorithm of Table 2, why is h^t built from R_t and not from 
      R_{t-1} U Q_{t-1}? Since R_t is selected so that the weak classifier built 
      from it will look as much as possible like the weak classifier built from 
      R_{t-1} U Q_{t-1} and since the computational cost for deriving R_t is 
      higher than the computational cost for selecting h^t from R_{t-1} U 
      Q_{t-1}, I don't see any reason not to train h^t from R_{t-1} U Q_{t-1}. 
      - The authors show that the FIX method needs 10 times more examples at 
      each iteration than GEEM to reach similar accuracy. However, FIX is forced 
      to always use the same examples at each iteration while GEEM samples 100 
      or 250 new examples at each iteration, meaning that at the end, GEEM has 
      seen 25,000 or 62,500 fresh examples in total. So, I'm not sure the 
      comparison is really fair. I would be interested to see the results of the 
      application of offline boosting on the same number of examples as seen by 
      GEEM, to see what we loose by working with a fixed reservoir. - Also, 
      why is FIX using adaboost while GEEM uses logitboost? - The size r 
      seems to be a sensible parameter that should not be chosen too small (as 
      the weak learner is trained on r examples). The algorithm can thus not be 
      turned into a real online method. I would like to see a study of the 
      impact of the value of this parameter, in particular to see how large r 
      has to be to reach a reasonable accuracy.