RESIT: regression with subsequent independence testing

Fix a finite nonempty ordered vertex set $V$ and a population law of a real vector $X=(X_j{)}_{j\in V}$ generated by an additive-noise model. A population regression rule $\mathcal{R}$ assigns to each target $j\in V$ and predictor set $C\subseteq V\setminus \{j\}$ a Borel function $m_{j,C}:{\mathbb{R}}^C\to \mathbb{R}$. A perfect independence oracle returns “independent” exactly when the tested random variable and random vector are independent under this population law. For a given ANM, $\mathcal{R}$ is population-consistent on that model if for every $j$ and every $C$ with $\mathrm{pa}(j)\subseteq C\subseteq \mathrm{nd}(j)$, there is a constant $c_{j,C}\in \mathbb{R}$ such that $m_{j,C}(X_C)=f_j(X_{\mathrm{pa}(j)})+c_{j,C}\text{almost surely}\mathrm{.}$ This consistency condition concerns only the population regression target and does not assert a finite-sample guarantee. The procedure itself is defined for any supplied regression rule and oracle.

RESIT takes $X$, $\mathcal{R}$, and the perfect independence oracle and performs the following steps, using a fixed total order on $V$ for every tie and loop order.

1. Set the remaining set $S:=V$ and an empty sink list. While $S\mathrm{\ne }\mathrm{\varnothing }$, for each $j\in S$ form $R_j:=X_j-m_{j,S\setminus \{j\}}(X_{S\setminus \{j\}})\mathrm{.}$ Retain the vertices for which the oracle declares $R_j$ independent of $X_{S\setminus \{j\}}$. If there is no such vertex, return failure. Otherwise choose the least retained vertex $k$, record the provisional parent set $\stackrel{}{\mathrm{pa}}(k):=S\setminus \{k\}$, append $k$ to the sink list, and remove $k$ from $S$.
2. Reverse the sink list to obtain an order $\pi$. In that order, for each vertex $j$ and each candidate $\mathrm{\ell }$ in its provisional parent set, in the fixed order, let $C:=\stackrel{}{\mathrm{pa}}(j)\setminus \{\mathrm{\ell }\}$ and form $R_{j,\mathrm{\ell }}:=X_j-m_{j,C}(X_C)\mathrm{.}$ If the oracle declares $R_{j,\mathrm{\ell }}$ independent of the vector of all vertices preceding $j$ in $\pi$, delete $\mathrm{\ell }$ from $\stackrel{}{\mathrm{pa}}(j)$; otherwise retain it.
3. Return the DAG with arrow $i\to j$ exactly when $i\in \stackrel{}{\mathrm{pa}}(j)$ after pruning.

Finite additive-noise model and its parent sets

Finite recursive DAG convention

Peters et al., JMLR (2014), Algorithm 1 and §4.1

Assaad, Devijver, and Gaussier, course notes (2023), Algorithm 2

Peters, Janzing, and Schölkopf, Elements of Causal Inference, §7.2.3