Subset Selection and Summarization in Sequential Data
Subset selection, which is the task of finding a small subset of representative items from a large ground set, finds numerous applications in different areas. Sequential data, including time-series and ordered data, contain important structural relationships among items, imposed by underlying dynamic models of data, that should play a vital role in the selection of representatives. However, nearly all existing subset selection techniques ignore underlying dynamics of data and treat items independently, leading to incompatible sets of representatives. In this paper, we develop a new framework for sequential subset selection that finds a set of representatives compatible with the dynamic models of data. To do so, we equip items with transition dynamic models and pose the problem as an integer binary optimization over assignments of sequential items to representatives, that leads to high encoding, diversity and transition potentials. Our formulation generalizes the well-known facility location objective to deal with sequential data, incorporating transition dynamics among facilities. As the proposed formulation is non-convex, we derive a max-sum message passing algorithm to solve the problem efficiently. Experiments on synthetic and real data, including instructional video summarization, show that our sequential subset selection framework not only achieves better encoding and diversity than the state of the art, but also successfully incorporates dynamics of data, leading to compatible representatives.
The paper consider a new problem of subset selection from set X that represents objects from sequence Y with additional constraint that the selected subset should comply with underlaying dynamic model of set X. The problem seems interesting to me and worth investigation.
The novel problem boils down to maximization problem (11). The authors suggest a new message-passing scheme for the problem. 
The problem can be seen as a multilabel energy minimization problem (T nodes, M labels, chain structure with additional global potential -log(\Phi_{card}(x_{r_1}, \ldots, x_{r_T}))) written in overcomplete representation form [23]. The problem is well known in energy minimization community as energy minimization with label costs [2]. It is shown that global potential -log(\Phi_{card}(x_{r_1}, \ldots, x_{r_T})) can be represented as a set of pairwise submodular potentials with auxiliary variables [2, 3]. Therefore, the problem (11) can be seen as multilabel energy minimization with pairwise potentials only. There are tons of methods including message passing based to solve the problem approximately (TRW-S, LBP, alpha-beta swap, etc). While they may work worse than the proposed message passing, the thoughtful comparison should be performed.
I believe that the paper in its current form cannot be accepted. Although the considered problem is interesting, the related work section should include [1,2,3]. Also, different baselines for experimental evaluation should be used (other optimization schemes for (11)), as it is clear from the experiments that DPP based methods do not suit for the problem. I think that the improved version may have a great impact.
typos:
- (8) \beta was missed
- L229 more more -> more
- L236 jumping, jumping -> jumping
[1] Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 2008
[2] Delong, Andrew, et al. "Fast approximate energy minimization with label costs." International journal of computer vision 96.1 (2012): 1-27.
[3]  M. A. Fischler and R. C. Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–395, 1981.