ICML 2020

文章贡献：

  1. 用AND-OR树来对分子和反应进行表示。
  2. 基于AND-OR树的表示，通过训练出的神经网络指导一个类似A*搜索的过程，来完成retrosynthetic planning这一过程。主要学的是cost。

Problem Statement

image.png
B代表单步的反合成模型，所有分子表示为M，t属于M，代表目标分子，至多有k个产生该分子的单步反应R，对应的反应物集为S，以及反应成本c。成本可以表示为在B下的似然的相反数（似然越小，成本越高，似乎还挺有道理的）。训练集为image.png，也就是说训练集提供目标分子以及相应的反应物。
之前用树推理反合成用到了MCT，蒙特卡洛树，之后如果有需要再细究。这里详细说说AND-OR树。
PNS模型，proof-number search是为two-player game设计的，旨在快速证明或否定根节点，这反合成任务中等价于对于根节点的分子，找到一条可行的合成路线，否则就是不可合成的。
image.png
pn(u)代表为了证明u需要的最少的叶子节点，dn(u)代表为了否定u需要的最少的叶子节点。分子节点为OR，反应节点为AND，很好理解，因为我们只需要一个可行的反应，但确定反应之后的反应物缺一不可。
构建这个树的目的就是快速建立或推翻一个反应过程。所以就想找到根节点的子节点中最小的pn(u)或最小的dn(u)（如果是OR节点就找到最小的可证明，如果是AND节点就找到最小的推翻，这样才节省时间）。

Retro* Search Algorithm

Retro算法如下：
image.png
T就是上文介绍的AND-OR Tree，分子为OR，反应为AND。接下来拆开解释：
selection：对于树T，有节点集image.png，image.png指代T中还没有扩展到的分子节点，image.png为value function，算法第三行就是根据价值函数找下一个要扩展的节点。
expansion：找到要扩展的m之后，通过B(m)可以找到k个单步反合成。在m之下生成R节点代表反应，在R之下生成m’代表反应物，R接连m成为stump。
update：把加入m之后的T叫T’，并更新V。
接下来介绍价值函数的设计。采用了A算法的思想。将value function拆分：
image.png
g就是目前为止的cost，h是未来的cost。转化成更简单的形式解决这个问题。image.png表明合成m需要的cost，rn是reaction number函数。定义如下：
image.png
定义value如下，pr为parent节点，A为ancestor节点。
image.png
第一项为从m回溯到根节点一路上反应的cost。注意反应为AND节点，其下的反应物的cost也要算进去。第二项就是解决这个需求的。看式子很难受，配图解释挺清楚的：
image.png
更新价值函数。