Sequential Facility Location: Approximate Submodularity and Greedy Algorithm
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:17841793, 2019.
Abstract
We develop and analyze a novel utility function and a fast optimization algorithm for subset selection in sequential data that incorporates the dynamic model of data. We propose a cardinalityconstrained sequential facility location function that finds a fixed number of representatives, where the sequence of representatives is compatible with the dynamic model and well encodes the data. As maximizing this new objective function is NPhard, we develop a fast greedy algorithm based on submodular maximization. Unlike the conventional facility location, the computation of the marginal gain in our case cannot be done by operations on each item independently. We exploit the sequential structure of the problem and develop an efficient dynamic programmingbased algorithm that computes the marginal gain exactly. We investigate conditions on the dynamic model, under which our utility function is ($\epsilon$approximately) submodualr, hence, the greedy algorithm comes with performance guarantees. By experiments on synthetic data and the problem of procedure learning from instructional videos, we show that our framework significantly improves the computational time, achieves better objective function values and obtains more coherent summaries.
Related Material


