Code to extract sparse transport support from Markov Graph

Question

Hi,

If the target map satisfies a marjov random field structure, then the inverse transport map will be sparse. I know how to extract the nonzero components from the MRF. But I was wondering if you had code to do this automatically? I see in this example: https://transportmaps.mit.edu/docs/example-inverse-stochastic-volatility-6d.html?highlight=conditional%20independence You do it by hand.

I just wanted to check if you already wrote this code before doing it myself.

 

Thanks,

 

Patrick

Answer 1

Hi Patrick, 

Thank you very much for your question! Given a marginal random field (MRF), the sparsity of the inverse transport map (i.e., the active variables set in the code you referenced) can be extracted from a variable elimination algorithm applied to the graph. We have implemented this code as part of our SING algorithm for learning the structure of graphical models from data, which alternates using a sparse map to learn the adjacency of the graph with extracting the map sparsity from the adjacency matrix. 

The code block to extract the active variables as a list given a matrix A encoding the edges of the MRF is:

# Variable elimination moving from highest node (dim-1) to node 2 (at most)
dim = A.shape[0]
ALower = np.tril(A)
for i in range(dim-1,1,-1):
    non_zero_ind  = np.where(ALower[i,:i] != 0)[0]
    if len(non_zero_ind) > 1:
        co_parents = list(itertools.combinations(non_zero_ind,2))
        for j in range(len(co_parents)):
            row_index = max(co_parents[j])
            col_index = min(co_parents[j])
            ALower[row_index, col_index] = 1.0

# Find list of active_vars
active_vars = []
for i in range(dim):
    actives = np.where(ALower[i,:] != 0)
    active_list = list(set(actives[0]) | set([i]))
    active_list.sort(key=int)
    active_vars.append(active_list)

Please let us know if you have any other questions!

 

Best,

Ricardo