IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Deducing Vertex Weights from Empirical Occupation Times

  • April 14, 2017
  • 2:30 p.m.
  • LeConte 312

Abstract

Consider the following machine learning problem originating from the study of human problem solving: Let $G$ be a vertex-weighted digraph with marked start'' andend'' vertices. Suppose that a random walker begins at the start vertex, steps to neighbors of vertices with probability proportional to their weights, and stops upon reaching the end vertex. Could one deduce the weights from the set of paths that many such walkers take? We analyze an iterative Newton-method-like numerical algorithm to solve this reconstruction problem when the empirical mean occupation times of the walkers is given. The existence of a choice of weights that gives rise to a given list of expected occupation times is considered, showing several natural equivalent conditions for such a solution to exist. The family of weight vectors satisfying these conditions can be thought of as the interior of a certain generalization of projective space, which we refer to as ``graphical projective space''; we discuss some of these spaces' (and their hypergraph generalizations') combinatorial and singular properties.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC