Learning the unknown causal parameters of a linear structural causal model is
a fundamental task in causal analysis. The task, known as the problem of
identification, asks to estimate the parameters of the model from a combination
of assumptions on the graphical structure of the model and observational data,
represented as a non-causal covariance matrix. In this paper, we give a new
sound and complete algorithm for generic identification which runs in
polynomial space. By standard simulation results, this algorithm has
exponential running time which vastly improves the state-of-the-art double
exponential time method using a Gr\"obner basis approach. The paper also
presents evidence that parameter identification is computationally hard in
general. In particular, we prove, that the task asking whether, for a given
feasible correlation matrix, there are exactly one or two or more parameter
sets explaining the observed matrix, is hard for $\forall R$, the co-class of
the existential theory of the reals. In particular, this problem is
$coNP$-hard. To our best knowledge, this is the first hardness result for some
notion of identifiability.

使用新的算法，根据模型的图形结构和观察数据来估计线性结构因果模型中未知的因果参数，证明参数标识在一般情况下是计算上困难的。

线性结构因果模型中识别复杂性研究

On the Complexity of Identification in Linear Structural Causal Models

Recent progress towards theoretical interpretability guarantees for AI has
been made with classifiers that are based on interactive proof systems. A
prover selects a certificate from the datapoint and sends it to a verifier who
decides the class. In the context of machine learning, such a certificate can
be a feature that is informative of the class. For a setup with high soundness
and completeness, the exchanged certificates must have a high mutual
information with the true class of the datapoint. However, this guarantee
relies on a bound on the Asymmetric Feature Correlation of the dataset, a
property that so far is difficult to estimate for high-dimensional data. It was
conjectured in W\"aldchen et al. that it is computationally hard to exploit the
AFC, which is what we prove here.
We consider a malicious prover-verifier duo that aims to exploit the AFC to
achieve high completeness and soundness while using uninformative certificates.
We show that this task is $\mathsf{NP}$-hard and cannot be approximated better
than $\mathcal{O}(m^{1/8 - \epsilon})$, where $m$ is the number of possible
certificates, for $\epsilon>0$ under the Dense-vs-Random conjecture. This is
some evidence that AFC should not prevent the use of interactive classification
for real-world tasks, as it is computationally hard to be exploited.

通过交互式证明系统和证明者选择一个具有信息量的证书的方式，以达到高完整性和声音，从而对具有高互信息的证书进行边际分析，区分高维数据集。进而证明 Asymmetric Feature Correlation 是难以计算利用的，从而推断它不会阻止交互分类用于现实任务。

欺骗性证书选择的难度

Hardness of Deceptive Certificate Selection

Sparse decision tree optimization has been one of the most fundamental
problems in AI since its inception and is a challenge at the core of
interpretable machine learning. Sparse decision tree optimization is
computationally hard, and despite steady effort since the 1960's, breakthroughs
have only been made on the problem within the past few years, primarily on the
problem of finding optimal sparse decision trees. However, current
state-of-the-art algorithms often require impractical amounts of computation
time and memory to find optimal or near-optimal trees for some real-world
datasets, particularly those having several continuous-valued features. Given
that the search spaces of these decision tree optimization problems are
massive, can we practically hope to find a sparse decision tree that competes
in accuracy with a black box machine learning model? We address this problem
via smart guessing strategies that can be applied to any optimal
branch-and-bound-based decision tree algorithm. We show that by using these
guesses, we can reduce the run time by multiple orders of magnitude, while
providing bounds on how far the resulting trees can deviate from the black
box's accuracy and expressive power. Our approach enables guesses about how to
bin continuous features, the size of the tree, and lower bounds on the error
for the optimal decision tree. Our experiments show that in many cases we can
rapidly construct sparse decision trees that match the accuracy of black box
models. To summarize: when you are having trouble optimizing, just guess.

通过使用智能猜测策略，我们可以在几个数量级的时间里降低运行时间，提供对最佳决策树误差和表达能力偏差的界限，并在许多情况下快速构建与黑盒模型的匹配精度的稀疏决策树。