Learning Multiple Models via Regularized Weighting
We consider the general problem of Multiple Model Learning (MML) from data, from the statistical and algorithmic perspectives; this problem includes clustering, multiple regression and subspace clustering as special cases. A common approach to solving new MML problems is to generalize Lloyd's algorithm for clustering (or Expectation-Maximization for soft clustering). However this approach is unfortunately sensitive to outliers and large noise: a single exceptional point may take over one of the models. We propose a different general formulation that seeks for each model a distribution over data points; the weights are regularized to be sufficiently spread out. This enhances robustness by making assumptions on class balance. We further provide generalization bounds and explain how the new iterations may be computed efficiently. We demonstrate the robustness benefits of our approach with some experimental results and prove for the important case of clustering that our approach has a non-trivial breakdown point, i.e., is guaranteed to be robust to a fixed percentage of adversarial unbounded outliers.
The authors propose in this paper a regularized 
      weighting technique for multi-model learning. Multi-model learning 
      consists in fitting a "mixture" of simple models to a data set in a quite 
      generic sense where each model is associated to a convex loss and the 
      mixture is optimized with respect to both the model parameters and their 
      weights (each model is associated to a set of weights that describe how 
      much the model claims to explain each data point). This model generalizes 
      several classical approaches such as k-means and classical probabilistic 
      mixture modeling. The authors propose to penalize the weights of each 
      model so as to favor uniform weight distributions as a way to bring 
      robustness of the mixture with respect to outliers. The paper contains 
      several theoretical results and some limited experimental validation. 
      The paper is interesting and well written. In particular, the 
      generality of the approach is very well presented. The authors also 
      managed to pack a nice collection of results in a limited space. They 
      pushed all the proofs in supplementary material, but nevertheless, the 
      paper feels quite self contained. Limitations of the technique are also 
      clearly presented (see Figure 2.2 for instance). My overall 
      impression is therefore very positive. That said, the paper is not without 
      flaws. A very minor one concerns notations: - \Delta^n is introduced a 
      bit too late (in footnote 1 which falls on page 3 while the notation is 
      used on page 2). - P_C (the orthogonal projection operator) is defined 
      only in the supplementary material while it is used in Lemma 2 (in the 
      s.m. the definition is also a bit too delayed). - while the gamma 
      parameter used in the discussion below definition 2 is indirectly defined, 
      I think the discussion would be clearer by being more explicit (for 
      instance by saying that the proportion of zero weights (i.e., ignored data 
      points) should be between this and that). While the overall paper 
      is very clear, Section 3.1 is a bit too cryptic and lacks too much 
      details: how was the noise generated? what is the value of alpha? what is 
      the effect of said value on the performances? does MAD in the legend 
      stands for MD in the text? if the base learning is PCA, is there any 
      dimensionality reduction done? if yes how? All in one, this unique 
      experimental evaluation raises more questions that it brings answers or 
      insights on the proposed method. Coming back to the choice of 
      alpha, it is obvious, as discussed in Section 2 and 3.2, that its actual 
      value will have at least some impact on the performances of the final 
      model. And of course, any practitioner would want to optimize said alpha. 
      Yet the experimental section does not show the effects of alpha (whose 
      value is not specified) and the authors offer almost no clue on how to 
      tune it. This is quite a shortcoming in the paper, in my opinion. As alpha 
      appears explicitly in Theorem 3, it is quite clear that even on a 
      theoretical point of view the parameter has some complex effect on the 
      results. Another point is the upper bound assumption (B 
      everywhere). I'm familiar with clipping techniques used in rather old 
      papers (for instance the Zeger and Lugosi's 1995 paper, see 
      http://www.code.ucsd.edu/~zeger/publications/journals/LuZe95-IT-Nonparametric/LuZe95-IT-Nonparametric.pdf) 
      but I'm not sure how to understand the assumption in the present context. 
      In particular, it seems too me that the very idea of fighting arbitrary 
      outliers might prevent this assumption to be true in practice. In other 
      words, moving from Theorem 3 to a more general one which applies when the 
      bound assumption is not valid (as in done in the paper referenced above) 
      does not seem completely obvious to me. I might be missing something that 
      should then be emphasized more in the paper. A final point is that 
      despite the (short) Section 1.1, the discussion on related works seem 
      quite limited. In particular, mixture models can accommodate many types of 
      reasonable outliers by modeling them explicitly, for instance via some 
      Student component instead of Gaussian ones, or via some explicit noisy 
      components added to the mixture. Bayesian priors can be included into the 
      mix to avoid some strong effects of very badly behaving outliers. I'm not 
      saying that such an approach might lead to non zero breakdown point, but 
      in practice, such variants do work very well.