Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata
This work addresses efficiency bottlenecks in inference tasks for researchers and practitioners in probabilistic graphical models and constraint satisfaction, offering a significant but incremental improvement over existing methods.
The paper tackles the problem of exact most probable explanation and constrained optimization in graphical models by proposing a concise function representation based on deterministic finite state automata, integrated into Bucket Elimination (FABE), resulting in runtime improvements of up to 5 orders of magnitude compared to state-of-the-art methods.
We propose a concise function representation based on deterministic finite state automata for exact most probable explanation and constrained optimization tasks in graphical models. We then exploit our concise representation within Bucket Elimination (BE). We denote our version of BE as FABE. FABE significantly improves the performance of BE in terms of runtime and memory requirements by minimizing redundancy. Results on most probable explanation and weighted constraint satisfaction benchmarks show that FABE often outperforms the state of the art, leading to significant runtime improvements (up to 5 orders of magnitude in our tests).