Date of Degree


Document Type


Degree Name



Computer Science


Changhe Yuan

Committee Members

Chao Chen

Jia Xu

Neng-Fa Zhou

Subject Categories

Artificial Intelligence and Robotics | Theory and Algorithms


Graphical Model, Multiple Inference, M-Best, M-Modes, Heuristic Search


For inference problems in graphical models, much effort has been directed at algorithms for obtaining one single optimal prediction. In practice, the data is often noisy or incomplete, which makes one single optimal solution unreliable. To address this problem, multiple Inference is proposed to find several best solutions, M-Best, where multiple hypotheses are preferred for advanced reasoning. People use oracle accuracy as an evaluation criterion expecting one of the solutions has high accuracy with the ground truth. It has been shown that it is beneficial for the top solutions to be diverse. Approaches for solving diverse multiple inference are proposed such as Diverse M-Best and M-Modes. They rely on hyper-parameters in enforcing diversity. Works keep optimizing the efficiency of solving difficult M-Modes problems by using an intelligent heuristic search on tree decompositions. The newest Min-Loss M-Best introduces a parameter-free method that directly minimizes the expected loss to simultaneously find the multiple top solution set.