Heuristic search is often used for motion planning and pathfinding problems,
for finding the shortest path in a graph while also promising completeness and
optimal efficiency. The drawback is it's space complexity, specifically storing
all expanded child nodes in memory and sorting large lists of active nodes,
which can be a problem in real-time scenarios with limited on-board
computation. To combat this, we present the Search with Learned Optimal
Pruning-based Expansion (SLOPE), which, learns the distance of a node from a
possible optimal path, unlike other approaches that learn a cost-to-go value.
The unfavored nodes are then pruned according to the said distance, which in
turn reduces the size of the open list. This ensures that the search explores
only the region close to optimal paths while lowering memory and computational
costs. Unlike traditional learning methods, our approach is orthogonal to
estimating cost-to-go heuristics, offering a complementary strategy for
improving search efficiency. We demonstrate the effectiveness of our approach
evaluating it as a standalone search method and in conjunction with learned
heuristic functions, achieving comparable-or-better node expansion metrics,
while lowering the number of child nodes in the open list. Our code is
available at this https URL

通过学习最佳剪枝扩展的搜索方法（SLOPE），在限制的计算环境下，我们实现了对最优路径附近区域的探索，降低了内存和计算成本。

SLOPE: 带学习的最优剪枝扩展搜索

SLOPE: Search with Learned Optimal Pruning-based Expansion

We consider the fundamental problem of inferring the causal direction between
two univariate numeric random variables $X$ and $Y$ from observational data.
The two-variable case is especially difficult to solve since it is not possible
to use standard conditional independence tests between the variables.
To tackle this problem, we follow an information theoretic approach based on
Kolmogorov complexity and use the Minimum Description Length (MDL) principle to
provide a practical solution. In particular, we propose a compression scheme to
encode local and global functional relations using MDL-based regression. We
infer $X$ causes $Y$ in case it is shorter to describe $Y$ as a function of $X$
than the inverse direction. In addition, we introduce Slope, an efficient
linear-time algorithm that through thorough empirical evaluation on both
synthetic and real world data we show outperforms the state of the art by a
wide margin.

本文提出了一种基于信息理论的方法，使用 MDL 原理基于压缩编码对局部和全局函数关系进行编码，提出了 Slope 算法，并在合成和真实数据上展示了比现有技术更佳的性能，用于解决从观测数据中推断两个单变量数值随机变量之间因果关系的问题。

基于 MDL 的局部和全局回归区分因果关系

Telling Cause from Effect using MDL-based Local and Global Regression

We introduce a new estimator for the vector of coefficients $\beta$ in the
linear model $y=X\beta+z$, where $X$ has dimensions $n\times p$ with $p$
possibly larger than $n$. SLOPE, short for Sorted L-One Penalized Estimation,
is the solution to \[\min_{b\in\mathbb{R}^p}\frac{1}{2}\Vert y-Xb\Vert
_{\ell_2}^2+\lambda_1\vert b\vert _{(1)}+\lambda_2\vert
b\vert_{(2)}+\cdots+\lambda_p\vert b\vert_{(p)},\] where
$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_p\ge0$ and $\vert
b\vert_{(1)}\ge\vert b\vert_{(2)}\ge\cdots\ge\vert b\vert_{(p)}$ are the
decreasing absolute values of the entries of $b$. This is a convex program and
we demonstrate a solution algorithm whose computational complexity is roughly
comparable to that of classical $\ell_1$ procedures such as the Lasso. Here,
the regularizer is a sorted $\ell_1$ norm, which penalizes the regression
coefficients according to their rank: the higher the rank - that is, stronger
the signal - the larger the penalty. This is similar to the Benjamini and
Hochberg [J. Roy. Statist. Soc. Ser. B 57 (1995) 289-300] procedure (BH) which
compares more significant $p$-values with more stringent thresholds. One
notable choice of the sequence $\{\lambda_i\}$ is given by the BH critical
values $\lambda_{\mathrm {BH}}(i)=z(1-i\cdot q/2p)$, where $q\in(0,1)$ and
$z(\alpha)$ is the quantile of a standard normal distribution. SLOPE aims to
provide finite sample guarantees on the selected model; of special interest is
the false discovery rate (FDR), defined as the expected proportion of
irrelevant regressors among all selected predictors. Under orthogonal designs,
SLOPE with $\lambda_{\mathrm{BH}}$ provably controls FDR at level $q$.
Moreover, it also appears to have appreciable inferential properties under more
general designs $X$ while having substantial power, as demonstrated in a series
of experiments running on both simulated and real data.

介绍一种名为 SLOPE 的算法，其使用排好序的 L1 范数作为正则化项，在控制误发现率的同时保证具有很强的推断能力，适用于包括正交设计和通用设计在内的各种数据集，能够在大型数据集下高效地完成回归分析。