Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets
To cope with the high level of ambiguity faced in domains such as Computer Vision or Natural Language processing, robust prediction methods often search for a diverse set of high-quality candidate solutions or proposals. In structured prediction problems, this becomes a daunting task, as the solution space (image labelings, sentence parses, etc.) is exponentially large. We study greedy algorithms for finding a diverse subset of solutions in structured-output spaces by drawing new connections between submodular functions over combinatorial item sets and High-Order Potentials (HOPs) studied for graphical models. Specifically, we show via examples that when marginal gains of submodular diversity functions allow structured representations, this enables efficient (sub-linear time) approximate maximization by reducing the greedy augmentation step to inference in a factor graph with appropriately constructed HOPs. We discuss benefits, tradeoffs, and show that our constructions lead to significantly better proposals.
The paper proposes to greedily find a series of M diverse solutions to a structured output problem. First, the structured output prediction problem is expressed in terms of MAP inference in a factor graph. Next, this graph is augmented by a higher-order factor that encourages diversity from previously found solutions.  Repeated MAP inference in this augmented factor graph (with iteratively updated higher-order potentials) then gives a series of M diverse solutions. Different task-specific user-defined diversity measures lead to inference problems that are a special case of either label costs, co-operative cuts or cardinality potentials inference. The experiments show similar performance to Diverse M-Best [1, cited] on two datasets for one proposed diversity measure whereas the other proposed diversity measures perform significantly worse than [1] in general, but have some advantages on single instances of the dataset.Quality: The paper is well written (apart from some minor notational issues raised below) and the structure is mostly clear. It offers some theoretical insights in the DivMBest method and extends that model to higher-order diversity potentials. The paper contains most relevant proofs.The proposed diversity measures, however, seem to lack some desirable properties:* The diversity measures in Eqs. (5) and (6) are invariant to label flips. For instance, if in one segmentation, two objects are labeled as cat and dog, then there is no diversity-related reward for flipping those two labels, i.e. labeling the objects as dog and cat, respectively. * Only new labels are rewarded, structure (location and size of the superpixels,...) is not taken into account, e.g. labeling a different object as dog, or increasing the size of the dog object.* The greedy fashion of the algorithm has drawbacks when the diversity measure from Eq. (5) is utilized: For instance, if in Fig. 2a the MAP solution y_1 yields a segmentation containing three (super)pixels with a dog, person and horse, then there is no further marginal gain for diversity. Also, the general diversity in Eq. (6) will favor segmentations with many distinct labels. Diverse solutions may, however, also contain fewer distinct labels.* The parsimony factor raises some concerns:  i) The parsimony factor should naturally be included into the diversity term, not the relevance term (l. 227) since the learned weights in the relevance term should be independent of the diversity term. If a diversity term without bias towards more labels is designed, the parsimony factor would be unnecessary. In other words, if the MAP solution of the factor graph without diversity term is to be found (i.e. minimization of the relevance term), the parsimony factor should not be included.  ii) It is currently chosen in a rather heuristic manner (e.g. how to choose/learn c(l) in line 248?).   iii) It is unclear whether/how this term is weighted against the relevance AND/OR diversity term: In l. 252 it is assigned the same weight as the diversity term, whereas this lambda is missing in l. 396.   iv) Both background-only segmentations and a segmentation containing only new labels are rewarded by zero (using l. 252). Hence, many segmentations will only consist of background, such as in Fig. 3.   v) Another major concern is that the sum in l. 252 may become negative, and consequently the requirements for the objective in Eq. (2) are violated.Furthermore, the paper does not elaborate on how the maximization in Eq. (2) is done over V\S^(t-1). If the maximization is done over V instead, it is not clear how it can be ensured that an optimal solution a^t is chosen which is not already contained in S^(t-1).The concerns above are mirrored by the experiments which perform significantly worse than the competitive method [1]. The Hamming balls potentials address some of these issues and achieve competitive results, but approximation errors from maximizing the loose lower bound (eq. 10) are included. Why is it not possible to include the exact marginal gain into the higher-order potential? Moreover, the Hamming ball section would profit from some reformulations and derivations, since this -- according to the experimental results -- seems to be the only useful diversity measure proposed in this paper.The experimental section would benefit from a more thorough analysis: * It would be interesting to see how robust the results are with different diversity parameters.* A combination of DivMBest and the proposed method, i.e. including the unary potentials from DivMBest AND the higher-order potentials, may perform much better.* It is not stated how the parameters are chosen for the experiment in 5.2, how the parsimony factor weight is chosen, and how the Hamming ball radius k chosen.* It is not clear why the MAP solutions in Tab. 2 are different.* Why is only recall reported?While the authors claim "significantly higher oracle accuracy" (l. 94), according to the Results Section the method performs significantly worse than DivMBest in all cases except for the Hamming ball measure (which they state is rather similar to DivMBest), where results are comparable.  Clarity:* Fig. 2a (not referenced in the text) shows 6 examples which seem to be diverse segmentations. With the proposed count diversity, however, the greedy algorithm will only reward diversity for the first 1-3 segmentations (dependent on the order). Hence, this example should only include 1-3 different segmentations.* The notation in Eq. (9b), | B | and | union(B) |, where B are balls, is unclear.* The derivation of the equation in l. 287 is unclear and so is Fig. 2b: In Fig. 2b, some balls seem to have b=9, some b=7,...; |S|=4. It is not intuitively clear, why b/|S| is used. This makes it difficult to understand the exact connection to DivMBest [1]. The supplementary material should be extended appropriately.* I_y in ll. 289 and 307 does not seem to be the same.* Suppl. Fig 4 bottom is confusing: How can y_2 (Hamming) be black completely and y_3 contain a label? y_2 shouldn't have changed the objective, right?* l. 98: [14] do not learn a MIXTURE of M models* It is not mentioned in Sec. 3 that r(y) is required to be submodular.* The relevance function must be non-negative, as stated in l. 160 and enforced by the constraint in Suppl. l. 58. I assume the constraint is added in a cutting-plane fashion, since it involves all y \in Y. In practice, this constraint may be violated for some y \in Y? What is the procedure then?Originality and Significance:The derivation of diverse M-best solutions using set functions and maximizing their marginal gains is novel and sheds new light on DivMBest [1] for this specific model class. Extending [1] to higher-order potentials seems promising, but experimental results show only incremental and partial improvement compared to [1]. Minor comments:Equations 4, 5, 8, 9a: Instead of { G_i | ... } these sets should be over indices of groups { i | ... } rather than over one group G_i157: r(y) non-negative only ensures that r(.) is monotone.Fig. 2 is not referenced in the text19: is a challenging in structured prediction problems -> is a challenging task in structured prediction problems41: solve [...] problems that often fairly ambiguous -> solve [...] problems that often are fairly ambiguous81: where [k] is... -> leave out, since it is defined by [L] = {1,...,L} already143: there is broad class -> there is a broad class146: use structured a relevance function -> use a structured relevance function156: and a feature vectors -> and feature vectors157: It must be stressed that r(.) is only monotone if r(.) is linear and all summands are non-negative. 239: diverity -> diversity245: missing brackets around the differenceSupp. 66 and below: w* -> \hat w*266: leave out "large"289: I(y') -> I(y)292: presentend -> presented-----------I have increased the quality score by 2, assuming the authors will make all promised additions to the camera-ready version.