A Cross-Entropy Method that Optimizes Partially Decomposable Problems: A New Way to Interpret NMR Spectra

Some real-world problems are partially decomposable, in that they can be decomposed into a set of coupled sub-problems, that are each relatively easy to solve. However, when these sub-problem share some common variables, it is not sufficient to simply solve each sub-problem in isola-tion. We develop a technology for such problems, and use it to address the challenge of finding the concentrations of the chemicals that appear in a complex mixture, based on its one-dimensional 1H Nuclear Magnetic Resonance (NMR) spectrum. As each chemical involves clusters of spatially lo-calized peaks, this requires finding the shifts for the clusters and the concentrations of the chemicals, that collectively pro-duce the best match to the observed NMR spectrum. Here, each sub-problem requires finding the chemical concentra-tions and cluster shifts that can appear within a limited spec-trum range; these are coupled as these limited regions can share many chemicals, and so must agree on the concen-trations and cluster shifts of the common chemicals. This task motivates CEED: a novel extension to the Cross-Entropy stochastic optimization method constructed to address such partially decomposable problems. Our experimental results in the NMR task show that our CEED system is superior to other well-known optimization methods, and indeed produces the best-known results in this important, real-world applica-tion. 1