Combinatorial optimization isn’t a topic that is discussed much in experimental particle physics, but it is hiding in one of the most common data analysis tasks that we face at the Large Hadron Collider. Particles like quarks and gluons undergo an unobserved, tree-like process of radiation leading to a collimated spray of observed particles called a “jet”. Estimating the most likely tree of radiation history that gives rise to that jet is a combinatorial optimization problem over (2N-3)!! possible binary trees. We developed a trellis data structure and corresponding dynamic programming algorithm that allows us to find the maximum likelihood and marginal likelihood for this problem exactly. The trellis data structure provides a scaffolding for A* search and various approximate algorithms. Finally, the data structure also allows us to efficiently parameterize a distribution over this combinatorially large discrete space of trees for use in variational inference and probabilistic machine learning.
Copyright. All Rights Reserved.