The usage of Rational Speech Acts (RSA) framework has been successful in
building \emph{pragmatic} program synthesizers that return programs which, in
addition to being logically consistent with user-generated examples, account
for the fact that a user chooses their examples informatively. We present a
general method of amortizing the slow, exact RSA synthesizer. Our method first
query the exact RSA synthesizer to compile a communication dataset. The dataset
contains a number of example-dependent rankings of subsets of programs. It then
distills a \textit{single} global ranking of all programs as an approximation
to every ranking in the dataset. This global ranking is then used at inference
time to rank multiple logically consistent candidate programs generated from a
fast, non-pragmatic synthesizer. Experiments on two program synthesis domains
using our ranking method resulted in orders of magnitudes of speed ups compared
to the exact RSA synthesizer, while being more accurate than a non-pragmatic
synthesizer when communicating with humans. Finally, we prove that in the
special case of synthesis from a single example, this approximation is exact.

利用理性言语行为（RSA）框架在构建与用户生成的例子逻辑一致且注重用户选择例子信息性的计算机程序综合器方面取得了成功。本研究提出了一种摊销慢速、精确的 RSA 综合器的通用方法，通过先查询精确的 RSA 综合器来编制一个通信数据集，这一数据集包含了与程序子集相关的示例依赖排序。然后将这些排序抽取为对所有程序的单个全局排序，以近似数据集中的每个排序。在推理时，使用该全局排序来对由一个快速、非实用的综合器生成的多个逻辑一致的候选程序进行排序。在两个程序综合领域的实验中，我们的排序方法相比于精确的 RSA 综合器获得了数量级的加速度，并在与人类交流时比一个非实用的综合器更准确。最后，我们证明了在从单个例子进行综合的特殊情况下，此近似方法是精确的。

利用排序规则分摊实用程序综合

Amortizing Pragmatic Program Synthesis with Rankings

We propose a number of techniques for obtaining a global ranking from data
that may be incomplete and imbalanced -- characteristics almost universal to
modern datasets coming from e-commerce and internet applications. We are
primarily interested in score or rating-based cardinal data. From raw ranking
data, we construct pairwise rankings, represented as edge flows on an
appropriate graph. Our statistical ranking method uses the graph Helmholtzian,
the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in
much the same way the graph Laplacian is an analogue of the Laplace operator or
scalar Laplacian. We study the graph Helmholtzian using combinatorial Hodge
theory: we show that every edge flow representing pairwise ranking can be
resolved into two orthogonal components, a gradient flow that represents the
L2-optimal global ranking and a divergence-free flow (cyclic) that measures the
validity of the global ranking obtained -- if this is large, then the data does
not have a meaningful global ranking. This divergence-free flow can be further
decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow
(locally acyclic but globally cyclic); these provides information on whether
inconsistency arises locally or globally. An obvious advantage over the NP-hard
Kemeny optimization is that discrete Hodge decomposition may be computed via a
linear least squares regression. We also investigated the L1-projection of edge
flows, showing that this is dual to correlation maximization over bounded
divergence-free flows, and the L1-approximate sparse cyclic ranking, showing
that this is dual to correlation maximization over bounded curl-free flows. We
discuss relations with Kemeny optimization, Borda count, and Kendall-Smith
consistency index from social choice theory and statistics.

使用图 Helmholtzian 和组合 Hodge 理论，基于边缘流的成对排名可以解析为两个正交成分，其中一个表示 L2 最优全局排名，而另一个表示无旋转流，同时还可以通过线性最小二乘回归计算离散的 Hodge 分解。