To this end, we rely on the Perturb-and-MAP framework (Papandreou and Yuille, 2011).
we perturb the potentials (arc weights) with samples from the Gumbel distribution and compute the most probable structure with the perturbed potentials: Each element of the matrix G ∈ R n×n contains random samples from the Gumbel distribution 4 which is independent from the network parameters θ, hence there is no need to backpropagate through this path in the computation graph.