Latent Maximum Margin Clustering
We present a maximum margin framework that clusters data using latent variables. Using latent representations enables our framework to model unobserved information embedded in the data. We implement our idea by large margin learning, and develop an alternating descent algorithm to effectively solve the resultant non-convex optimization problem. We instantiate our latent maximum margin clustering framework with tag-based video clustering tasks, where each video is represented by a latent tag model describing the presence or absence of video tags. Experimental results obtained on three standard datasets show that the proposed method outperforms non-latent maximum margin clustering as well as conventional clustering approaches.
Summary: This work proposes an extension to 
      the maximum margin clustering (MMC) method that introduces latent 
      variables. The motivation for adding latent variables is that they can 
      model additional data semantics, resulting in better final clusters. The 
      authors introduce a latent MMC (LMMC) objective, state how to optimize it, 
      and then apply it to the task of video clustering. For this task, the 
      latent variables are tag words, and the affinity of a video for a tag is 
      given by a pre-trained binary tag detector. Experiments show that LMMC 
      consistently, and sometimes substantially, beats several reasonable 
      baselines. Comments: Clarity: The paper is clear and 
      well-written. The related work section is extensive and the experimental 
      details are abundant. Noticed just a few typos: 1) Line 83: The 
      "and combines them" should be "and combine them". 2) Line 187: The 
      "Balanced clusters are constrained by the last constraint" should be 
      something like "Cluster balance is enforced by the last constraint". 
      Originality: Adding latent variables to MMC is relatively novel. 
      The changes to the MMC objective and optimization are not too substantial, 
      but nonetheless represent something new. Very recent work that somewhat 
      overlaps with this work is that of Yang Wang and Liangliang Cao, 
      "Discovering Latent Clusters from Geotagged Beach Images" (MMM 2013). As 
      this work also deals with adding latent variables, though in a different 
      manner, it would be good if the authors could indicate the ways in which 
      their LMMC method differs. Significance: The empirical validation 
      presented in this work is strong enough to indicate that, at a minimum, 
      LMMC is significant for video clustering. Most likely it is also 
      applicable to many other clustering tasks, which frequently arise in the 
      machine learning community. However, it is hard to be sure from the 
      current experiments that the latent variables actually correspond to 
      coherent sub-aspects of a category. Quality: This paper is of good 
      quality. Its math and experiments seem relatively sound. While the delta 
      from MMC is not very large in the statement of the objective and the 
      exposition of the optimization, the experiments clearly show that the new 
      method represents a step up accuracy-wise. One suggestion --- it would be 
      interesting to see some runtime comparisons in Table 
      1.