ALGORITHMIC CHALLENGES IN LEARNING PATH METRICS FROM OBSERVED CHOICES

摘要

In many systems it is an essential part of the operation to find optimal paths in large graphs. In order to understand the system, we need to know the path metric under which the optimal paths are chosen. In many cases, however, no explicite knowledge of the metric is available, we can only observe the path choices that are made. Our goal is to learn the unknown metric, as accurately as possible, from the observed path choices. We present a mathematical model and method to handle this problem. Our main result is that the unknonw path metric can be optimally learned by a polynomial time algorithm, if we assume an additive (but unknown) metric over the graph edges. We also consider the case when the path metric is general, that is, not necessarily additive.