Mid-level Visual Element Discovery as Discriminative Mode Seeking
Recent work on mid-level visual representations aims to capture information at the level of complexity higher than typical "visual words", but lower than full-blown semantic objects. Several approaches [5,6,12,23] have been proposed to discover mid-level visual elements, that are both 1) representative, i.e., frequently occurring within a visual dataset, and 2) visually discriminative. However, the current approaches are rather ad hoc and difficult to analyze and evaluate. In this work, we pose visual element discovery as discriminative mode seeking, drawing connections to the the well-known and well-studied mean-shift algorithm [2,1,4,8]. Given a weakly-labeled image collection, our method discovers visually-coherent patch clusters that are maximally discriminative with respect to the labels. One advantage of our formulation is that it requires only a single pass through the data. We also propose the Purity-Coverage plot as a principled way of experimentally analyzing and evaluating different visual discovery approaches, and compare our method against prior work on the Paris Street View dataset of [5]. We also evaluate our method on the task of scene classification, demonstrating state-of-the-art performance on the MIT Scene-67 dataset.
The paper proposes a new method for learning 
      discriminative image patches predictive of the image class. The procedure 
      starts by considering all (?) patches in an image collection. The 
      discriminative patches are then found as the centres of patch clusters, 
      obtained by a discriminative version of the mean-shift algorithm. 
      Discriminativeness is incorporated in mean shift by dividing the kernel 
      density estimate of the positive patches by the one of negative ones. 
      Pros: - The problem of learning discriminative 
      patches/parts is an important one. - The classification performance of 
      the proposed discriminative patches is very good, at least on MIT Scene 
      67. - There are a few interesting insights in the formulation. 
      Cons: - The authors start from mean-shift and gradually 
      transform it into a very different algorithm. In the end, I am not sure 
      that the mean-shift interpretation is useful at all. - Several aspects 
      of the formulation and derivation are heuristics. Some of the heuristics 
      are changed on a dataset-by-dataset basis. - The learning algorithm is 
      also heuristic, with no formal guarantee of correctness/convergence. - 
      There are several small errors in the formal derivation. Detailed 
      comments: The empirical results are sufficiently strong that this 
      paper should be considered for publication. However, the formulation and 
      technical derivation should be improved significantly, as detailed below: 
      ### l.125: The notation should be clarified. The expression 
      max(d(x_i,w) - b, 0) is the triangular kernel assuming that d() is the 
      negative of the Euclidean distance (as stated on l. 130) *and* that the 
      bandwidth b is negative, which is counter-intuitive. max(b - d(x_i,w), 0) 
      is more natural. ### Eq. (1). arglocalmax is never defined. 
      ### Eq. (2). This equation indicates that, contrary to what 
      stated in the manuscript, the algorithm is not maximizing a ratio of 
      density values, but an energy function computed with a sort of adaptive 
      bandwidth. This density is given by E(w) = sum_i max(d(x_i^+) - 
      b(w), 0) where the bandwidth b(w) is selected as a function of the 
      current point w as b(w) = b : sum_i max(d(x_i^+) - b, 0) = 
      epsilon. Several aspects of this formulation should be clarified: 
      (a) The triangular kernel should be normalized by its mass to get 
      a proper density estimator. Interestingly, this normalization factor, 
      which depends on w, cancels out in the ratio (2), which perhaps "saves the 
      day". (b) This formulation should be contrasted to the standard 
      adaptive mean shift (e.g. B. Georgescu, I. Shimshoni, and P. Meer. Mean 
      shift based clustering in high dimensions: A texture classification 
      example. In Proc. ICCV, 2003). There the bandwidth is chosen as a function 
      of x_i rather than w and the normalization of the kernels become crucial. 
      (c) What happens if there are more than one value of b(w) 
      satisfying the constraint in (2) ? ### Eq. (3) l. 157: 
      It is the _squared_ Euclidean distance d^2() that reduces to the inner 
      product, not the euclidean distance d(). Note that restricting the 
      domain to the unit sphere requires in principle to modify all the 
      densities to have this manifold as domain. Fortunately, the required 
      modification (normalising factors) does not seem to have a consequence in 
      this case. l. 177: it seems to me that changing lambda _does_ 
      change the solution w, not just its norm. To keep the direction of w 
      invariant while changing lambda, epsilon must change as well. Therefore, 
      choosing different values of lambda should have an effect on the solution, 
      unless all values of epsilon are equally good (but then why having epsilon 
      in the first place?). ### Eq. (5) This is where the 
      proposed method diverges substantially from mean shift. Mean shift applies 
      hill climbing to each w independently starting from w = x_i for all data 
      points, in order to determine a clustering of the data x_i themselves. 
      Here, instead, the authors formulate (5) and (6) as a method to "explain" 
      all the data. Practical differences include: - mean-shift is 
      non-parametric, in the sense that the number of clusters is not specified 
      a priori. Here the authors start with a fixed number of cluster centers 
      w1...wK and optimise those to fit the data, which is more similar to 
      K-means. - the authors worry about the fact that "patches should 
      not be double counted" and introduce a set of soft associations 
      data-cluster alpha_ij. This is difficult to map in the standard semantic 
      of mean-shift clustering, where the association of a data point x_i to a 
      mode wk is obtained implicitly by the locality of the kernel estimator 
      only. As the authors argue, alpha_ij establish a "competition" between 
      modes to explain data points, which again is more similar to k-means. 
      - the way the alpha_ij are updated has little to do with the 
      optimization of (6) and is completely ad hoc (l.199 - 211) ### 
      Optimization method Unfortunately this method is just an heuristic 
      (l. 212-259). ### Experiments Baselines: [5,8] 
      have mechanism to avoid or remove redundant patches, which do not seem to 
      be incorporated in this baseline. Removing such redundant patches might 
      affect Fig. 3, 4. Scene-67 experiments: There are several tuning 
      of the representation (e.g. number of HOG cells in a descriptor) that 
      probably helps the method achieve state of the art results. While this is 
      ok, the authors should consider re-running this experiment with the 
      baseline discriminative patches obtained as in Fig. 4. ### 
      Other minor comments l.315: I have seen [5] and [8] in CVPR 2013 
      and it seems to me that they both have LDA 
      retraining.