We propose a unifying dynamic-programming framework to compute exact
literal-weighted model counts of formulas in conjunctive normal form. At the
center of our framework are project-join trees, which specify efficient
project-join orders to apply additive projections (variable eliminations) and
joins (clause multiplications). In this framework, model counting is performed
in two phases. First, the planning phase constructs a project-join tree from a
formula. Second, the execution phase computes the model count of the formula,
employing dynamic programming as guided by the project-join tree. We
empirically evaluate various methods for the planning phase and compare
constraint-satisfaction heuristics with tree-decomposition tools. We also
investigate the performance of different data structures for the execution
phase and compare algebraic decision diagrams with tensors. We show that our
dynamic-programming model-counting framework DPMC is competitive with the
state-of-the-art exact weighted model counters cachet, c2d, d4, and miniC2D.

提出了一种动态编程框架来计算 CNF 中公式的精确带权模型计数，其中包括 project-join 树的计划阶段和执行阶段，以及基于约束满足启发式与树分解工具的规划阶段，以及与张量比较的不同数据结构的执行阶段。与 cachet、c2d、d4 和 miniC2D 等最先进的精确带权模型计数器相比，该框架是有竞争力的。

DPMC：基于项目连接树的动态规划加权模型计数

DPMC: Weighted Model Counting by Dynamic Programming on Project-Join  Trees

The use of machine learning algorithms in finance, medicine, and criminal
justice can deeply impact human lives. As a consequence, research into
interpretable machine learning has rapidly grown in an attempt to better
control and fix possible sources of mistakes and biases. Tree ensembles offer a
good prediction quality in various domains, but the concurrent use of multiple
trees reduces the interpretability of the ensemble. Against this background, we
study born-again tree ensembles, i.e., the process of constructing a single
decision tree of minimum size that reproduces the exact same behavior as a
given tree ensemble in its entire feature space. To find such a tree, we
develop a dynamic-programming based algorithm that exploits sophisticated
pruning and bounding rules to reduce the number of recursive calls. This
algorithm generates optimal born-again trees for many datasets of practical
interest, leading to classifiers which are typically simpler and more
interpretable without any other form of compromise.

本研究旨在解决决策树集成在多领域应用时造成的可解释性下降，提出了 Born-Again 树集成的方法，通过动态规划算法生成出在实际数据集上表现优异的 Born-Again 树模型，以在不牺牲分类器性能的前提下获得更高的可解释性。

重生树集成

Born-Again Tree Ensembles

Shi, Huang, and Lee (2017) obtained state-of-the-art results for English and
Chinese dependency parsing by combining dynamic-programming implementations of
transition-based dependency parsers with a minimal set of bidirectional LSTM
features. However, their results were limited to projective parsing. In this
paper, we extend their approach to support non-projectivity by providing the
first practical implementation of the MH_4 algorithm, an $O(n^4)$ mildly
nonprojective dynamic-programming parser with very high coverage on
non-projective treebanks. To make MH_4 compatible with minimal transition-based
feature sets, we introduce a transition-based interpretation of it in which
parser items are mapped to sequences of transitions. We thus obtain the first
implementation of global decoding for non-projective transition-based parsing,
and demonstrate empirically that it is more effective than its projective
counterpart in parsing a number of highly non-projective languages

通过将转移型句法分析器的动态规划实现与最小集的双向 LSTM 功能相结合，Shi、Huang 和 Lee (2017) 获得了英语和汉语依存句法分析最先进的结果，但受限于投影分析。在本文中，我们通过提供 MH_4 算法的第一个实际实现，扩展了他们的方法以支持非投影性，在非投影性树库上具有非常高的覆盖率，并简化该算法以适应最少的转移型特征集。我们因此获得了非投影性转移型分析的全局解码的第一个实现，并证明它在解析一些高度非投影性的语言方面比其投影对应物更有效。