Factorizing Shortest Paths with Randomized Optimum Models

Tarlow, D., Gaunt, A., Adams, R. P., & Zemel, R. S. (2016). Factorizing Shortest Paths with Randomized Optimum Models. In Perturbations, Optimization, and Statistics. MIT Press.

Randomized Optimum models (RandOMs) are probabilistic models that de- fine distributions over structured outputs by making use of structured opti- mization procedures within the model definition. This chapter reviews Ran- dOMs and develops a new application of RandOMs to the problem of factorizing shortest paths; that is, given observations of paths that users take to get from one node to another on a graph, learn edge-specific and user- specific trait vectors such that inner products of the two define user-specific edge costs, and the distribution of observed paths can be explained as users taking shortest paths according to noisy samples from their cost function.

  @inbook{tarlow2016factorizing,
  year = {2016},
  author = {Tarlow, Daniel and Gaunt, Alexander and Adams, Ryan P. and Zemel, Richard S.},
  title = {Factorizing Shortest Paths with Randomized Optimum Models},
  booktitle = {Perturbations, Optimization, and Statistics},
  publisher = {MIT Press},
  address = {Cambridge, MA},
  keywords = {structured prediction}
}