# Sound Reconstruction via Optical Multi-Mode Fiber

Ege Küçükkömürcü<EMAIL_ADDRESS>Berk Nezir Gün
Programmable Photonics Group, Department of Physics, Middle East Technical
University, 06800, Ankara, Turkey<EMAIL_ADDRESS>Emre Yüce  Programmable
Photonics Group, Department of Physics, Middle East Technical University,
06800, Ankara, Turkey

###### Abstract

Sound reconstruction via arbitrary objects has been a popular method in recent
years, based on the recording of scattered light from the target object with a
high-speed detector. In this work, we demonstrate the use of multi-mode fiber
as a medium that enables reconstruction at a much further distance. By placing
a speaker near the fiber and using a high-speed camera with a maximum region
of interest, we show that it is possible to reconstruct the sound without
relying on specific grain information in the speckle. Basic filtration
techniques and spectral subtraction methods are employed to improve the signal
quality. After applying band-stop and high-pass filters, the magnitude-squared
coherence between the original sound and captured data is 0.8 at fundamental
frequencies. The proof-of-concept method that we introduce here can be
extended to monitor the vibrations of earth’s crust and civilian buildings for
structural safety.

## Introduction

Sound is a pressure wave that excites all translational, rotational, and
vibrational modes of atoms in a medium. What we hear is the motion of the
atoms, governed by the vibrational modes. Similar to an eardrum, a microphone
also has a diaphragm that is sensitive to vibrations across a wide range of
frequencies. The diaphragm of the microphone is excited by the vibrations and
converted into an electrical signal via an inductive coil. In fact, the motion
of the diaphragm can also be visualized and converted into sound, enabling
sound reconstruction from consecutive images [1]. Capturing vibrations from
arbitrary shaped objects might be challenging; however, there are many
advantages and applications.

Sound reconstruction through optical means is appealing due to its wider range
of detection than that of classical microphones and its durability in harsh
environmental conditions. An additional plus for optical techniques is that
the optical system carries information about the sound source’s location,
contrary to a classical microphone. With optical methods, real-time sound
reconstruction might also be possible, depending on the complexity of data
processing and computational power. The advantages of optical techniques to
get vibrations have catalyzed various applications in non-destructive
testing[2], medical diagnosis[3], optical coherence tomography[4], and
security[5].

In our approach to reconstructing sound optically, we utilize Laser Doppler
Vibrometry (LDV) principles [6], specifically with a focus on the inherent
sensitivity of multi-mode fiber. Unlike traditional LDV methods that involve
complex setups [7, 8], our method provides a simpler alternative for sound
reconstruction without the need for a second light path. By leveraging the
millimeter range between the source and the multi-mode fiber, our approach
captures and reconstructs sound using only a high-speed camera, multi-mode
fiber, and light source, making it more straightforward and efficient in
capturing the vibration characteristics of the object. This emphasis on
simplicity and effectiveness of our method as a viable and practical solution
for optical sound reconstruction.

Various signal processing methods are proposed to properly reconstruct sound
from surface vibrations. Some options are phase-based algorithms[9][10],
singular value decomposition[11], digital image correlation[12], and machine
learning algorithms[13]. Within our scenario, our inclination lies in
computing the average of pixel values encompassing the captured speckle
pattern as a preliminary step for data processing prior to embarking on the
sound reconstruction endeavor. We use an 8-bit camera that provides grayscale
images with a dynamic range between 0-255.

## Experimental Setup

We use a telecom laser at L=1550 nm as the light source. The speaker, whose
maximum power is 90 dBa, is placed such that it makes a 2mm distance from the
multi-mode fiber (Thorlabs FG105LCA). The fiber vibrates as the speaker plays
the sound, and so does the speckle pattern within. To detect the frequencies
that the sound wave produces through fiber, we collect the frames taken by a
high-speed infrared camera (Goldeye-008) at the output. We use a computer with
an Intel Core i7-7700 processor and 16 GB RAM for postprocessing.

## Method

Our primary objective is to capture high-frequency components with maximum
fidelity to accurately reconstruct the emitted sound. To achieve this, we
operate the camera at its highest frame rate, directing our attention to a
localized region that harbors sufficient speckle information for the
subsequent reconstruction process. Having maximum fps requires the camera
resolution to be set to a subregion of 128x8 pixels with 500$\mu$s exposure
time. To pick a proper subregion, we utilize full-resolution snapshots taken
at different times when the sound is on. We obtain the subregion that we will
use moving forward by consecutively taking the differences of these 8-bit
snapshots for every 128x8 pixels within the larger 320x256 pixel frame and
selecting the subregion with the highest maximum intensity value.

Figure 1: The experimental setup used for the reconstruction of sound through
capturing silent video of the vibrating laser beam. The infrared light beam is
emitted from the laser source and guided towards the coupler (indicated by the
arrow). The surface vibrations originating from speaker sound are transmitted
to the high-speed camera with the same optical principles. The intensity
values of speckle patterns captured by the camera are multiplied by 5 for
enhanced visibility.

We play the 5-second piano version of Inspector Gadget’s Theme near the multi-
mode fiber. To address the absence of a trigger option for synchronizing the
timing of the original sound and the recording within our system, a post-
recording cross-correlation method is employed. When initiating the recording
process, we did not have precise knowledge of which segment of the signal was
being captured. Therefore, after the recording, cross-correlation is utilized
to align the captured vibrations with the original sound data. To facilitate
this alignment, the original audio signal undergoes temporal downsampling from
41.8 kHz to 1.9 kHz, ensuring compatibility with the sampling rate of our
recording system.

$\widehat{R}_{xy}(m)=\begin{cases}\displaystyle\sum_{n=0}^{N-m-1}x_{n+m}y_{n}^{*}&\text{if
}m\geq 0,\\\
\vphantom{\displaystyle\sum_{n=0}^{N-m-1}}\widehat{R}_{xy}^{*}(-m)&\text{if
}m<0,\end{cases}$ (1)

where ${R}_{xy}(m)$ is the cross-correlation sequence at lag m, $x_{n}$ and
$y_{n}$ are the original and recorded data being correlated. We apply m amount
of shift that gives us the maximum value of cross-correlation for the
alignment.

In our setup, we use a high-speed camera to capture the speckle pattern, which
is the interference pattern produced by the laser beam reflecting off the
vibrating surface. To ensure that we capture enough information and do not
average out the data, we confirm that the size of the grains in the speckle is
larger than the single-pixel size of the camera. We capture a total of 10.000
frames of speckle patterns during the play of the 5-second record. After the
frames are captured from the designated area of 128x8 pixels, a comprehensive
set of filtering techniques is applied to acquire optimal results. These
techniques, commonly used in signal processing, are specifically chosen to
address the presence of noise related to pulses, as evidenced in Figure 3(a).
The frequencies of these pulses are 360 Hz, 720 Hz (2nd harmonic of 360 Hz),
and 840 Hz. We also reconstructed the signal itself before playing any sound
near the multi-mode fiber. Observing the signal in Fourier domain we saw that
we have setup related noises in these certain frequencies.

Figure 2: (a) 320x256 pixel speckle image with 5x intensity scaling. (b) 128x8
pixel speckle image used to gather data from the region shown.

  * •

Band-stop and high-pass filtering

A band-stop filtering technique was implemented to suppress the noise in the
system. This method removes specific frequency ranges, in this case, 360 Hz,
720 Hz, and 840 Hz, to effectively eliminate the noise. A high-pass filter was
also applied to remove excessive noise at low frequencies, specifically those
below 30 Hz, as seen in Figure 3(a). Using band-stop and high-pass filtering
allowed noise reduction, thus enhancing signal quality.

  * •

Audio enhancement

Figure 3: Time(s) vs. frequency(Hz) graphs of (a) captured data without
filter, (b) data after broadband and band-stop filters are applied, (c) data
after spectral subtraction method is used in addition to the filters applied
in (b). (d) Time(s) vs. frequency(Hz) graph of original sound data played by
the speaker.

Following the implementation of the high-pass and band-stop filters, the
signal was normalized between -1 and 1 to optimize its volume level. This step
is essential as normalization ensures the signal is within a consistent range,
preventing a possible distortion. To enhance sound quality further, we
employed the spectral subtraction method [14, 15], a technique used to remove
background noise from sound signals by estimating the background noise’s power
spectral density (PSD) and subtracting it from the total PSD of the signal.

## Results

Figure 3(a) shows the short-time Fourier transform (STFT) of captured
vibrations on the fiber. Those vibrations are caused by the external sound we
introduced and the electronic devices on the optical table as a noise factor.
As seen, below 30 Hz, huge noise was detected in addition to relatively less
but consistent noise over time around 360 Hz, 720 Hz, and 840 Hz. Figure 3(b)
shows the STFT of captured data after filtering constant noise frequencies.
Here, the magnitudes of frequencies are not apparent compared to Figure 3(d),
which represents the original data. To quantify the similarity between the
original and captured data, listening to the reconstructed sound one can
perceive the song that is being played. To justify our results, as a metric we
used magnitude-squared coherence. The magnitude-squared coherence is a
function of the power spectral densities, $P_{xx}(f)$ and $P_{yy}(f)$, and the
cross power spectral density, $P_{xy}(f)$, of x (original sound) and y
(reconstructed sound):

$C_{xy}(f)=\frac{\lvert P_{xy}(f)\rvert^{2}}{P_{xx}(f)P_{yy}(f)}$ (2)

Within our study, we examine several critical aspects of our system’s
performance. The analysis of the region of interest reveals that among the
potential 255 grey levels, the maximum grey level stands at 35, while the mean
value settles at 17. However, the accuracy of our system is challenged by the
presence of environmental noise, necessitating the application of appropriate
noise reduction strategies. To address this, we employ a combination of
bandstop and high-pass filters, effectively mitigating specific noise
components.

Figure 4: Analysis of Reconstructed and Original Signals (a) magnitude-squared
coherence between signals over frequencies (b) Signals in Fourier domain,
blue: original signal, red: reconstructed signal.

Investigating the magnitude-squared coherence between the two signals reveals
noteworthy insights. The coherence is close to 1 at main frequencies of the
sound, which are essential for perceiving the played song. For instance,
examining the fundamental frequencies of the original sound in Figure 4(a), at
80 Hz, we observe a coherence of 0.5, at 100 Hz a coherence of 0.7, and at 300
Hz a coherence of 0.8. This also coincides with the Figure 3(c) and Figure
3(d).

As monitored in Figure 3, we observe that the frequencies between 350 Hz and
550 Hz are reconstructed with higher magnitudes than other frequencies. Based
on our results, it appears that the frequency response of the fiber might
contribute to the variations observed in the reconstructed sound.
Additionally, the reconstruction method involving the mean of each grey pixel
value could lead to the rounding of magnitudes for higher frequencies [16].
This may result in attenuated amplitudes for outer frequencies in the
reconstructed sound. To address this issue, an alternative approach for
selecting pixels could be explored, avoiding such attenuation and potentially
improving the reconstruction quality of the outer frequency components [17].

The experiment demonstrates the feasibility of reconstructing external sound
signals through a multi-mode fiber. The results of the experiment are analyzed
using spectrographic techniques to assess the quality of the reconstructed
sound. The use of filtering methods is found to significantly improve the
reconstructed sound quality, as evidenced by a comparison of the original and
reconstructed signals. The magnitude-squared coherence between the original
and reconstructed signals has a remarkable value for frequencies of interest.
The visual similarity of the original and the reconstructed sound is apparent
in Figure 3, with the similarity more pronounced and easily perceived through
both audio files provided as supplementary materials.

## Conclusion

In conclusion, our achievement in sound reconstruction from the 128x8 pixel
speckle pattern stands as a testament to our success in circumventing the need
for additional spatial downsampling. The sensitivity of surface vibrations is
notably accentuated in proximity to the fiber source, primarily channeling
through a dominant vibrational mode. However, scenarios lacking a singular
dominant mode in the multi-mode fiber pose challenges to achieving more
precise sound reconstruction. In such intricate scenarios, the employment of
signal processing algorithms [17] emerges as a potential strategy to increase
the fidelity and audibility of the reconstructed audio.

The demonstrated capabilities of our methodology, with a primary focus on
acoustic signal capture, set the stage for further exploration and refinement.
This proof-of-concept setup, while showcasing the inherent acoustic
sensitivity of fibers, prompts intriguing possibilities for advancement. The
method can be expanded in order to exploit the sensitivity of multi-mode
fibers to the acoustic signals, for eavesdropping purposes. In addition to
that, the deployed methodology offers the potential to be extended for
monitoring Earth’s crust vibrations and evaluating the structural integrity of
civilian buildings, consequently contributing to enhanced safety measures.
Hence, the technology ushers in promising prospects for advancing our
comprehension of seismic activities and safeguarding vital infrastructure,
thereby significantly bolstering urban safety measures and disaster readiness.

## Acknowledgments

The authors thank Süleyman Kahraman for valuable discussions.

## References

  * [1] Davis, A. _et al._ The visual microphone: Passive recovery of sound from video.  _ACM Transactions on Graphics (Proc. SIGGRAPH)_ 33, 79:1–79:10 (2014).
  * [2] Chen, J. G. _et al._ Video camera-based vibration measurement for civil infrastructure applications.  _Journal of Infrastructure Systems_ 23, B4016013, DOI: 10.1061/(ASCE)IS.1943-555X.0000348 (2017).  https://ascelibrary.org/doi/pdf/10.1061/%28ASCE%29IS.1943-555X.0000348.
  * [3] Beard, P.  Biomedical photoacoustic imaging.  _Interface Focus_ 1, 602–631, DOI: 10.1098/rsfs.2011.0028 (2011).  https://royalsocietypublishing.org/doi/pdf/10.1098/rsfs.2011.0028.
  * [4] Fujimoto, J. G., Pitris, C., Boppart, S. A. & Brezinski, M. E.  Optical coherence tomography: An emerging technology for biomedical imaging and optical biopsy.  _Neoplasia_ 2, 9–25, DOI: 10.1038/sj.neo.7900071 (2000).
  * [5] Nassi, B., Pirutin, Y., Shamir, A., Elovici, Y. & Zadov, B.  Lamphone: Real-time passive sound recovery from light bulb vibrations.  Cryptology ePrint Archive, Paper 2020/708 (2020).  https://eprint.iacr.org/2020/708.
  * [6] Oikawa, Y., Goto, M., Ikeda, Y., Takizawa, T. & Yamasaki, Y.  Sound field measurements based on reconstruction from laser projections.  In _Proceedings. (ICASSP ’05). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005._ , vol. 4, iv/661–iv/664 Vol. 4, DOI: 10.1109/ICASSP.2005.1416095 (2005).
  * [7] Lü, T., Guo, J., Zhang, H.-y., Yan, C.-h. & Wang, C.-j.  Acquirement and enhancement of remote speech signals.  _Optoelectronics Letters_ 13, 275–278, DOI: 10.1007/s11801-017-7059-9 (2017).
  * [8] song Wu, S., Lv, T., yu Han, X., hui Yan, C. & yong Zhang, H.  Remote audio signals detection using a partial-fiber laser doppler vibrometer.  _Applied Acoustics_ 130, 216–221, DOI: https://doi.org/10.1016/j.apacoust.2017.09.028 (2018).
  * [9] Marafioti, A., Holighaus, N. & Majdak, P.  Time-frequency phase retrieval for audio—the effect of transform parameters.  _IEEE Transactions on Signal Processing_ 69, 3585–3596, DOI: 10.1109/TSP.2021.3088581 (2021).
  * [10] Zhou, J., Li, H., Zhang, L., Wang, X. & Li, Y.  Vibration measurement with video processing based on alternating optimization of frequency and phase shifts.  _IEEE Transactions on Instrumentation and Measurement_ 70, 1–13, DOI: 10.1109/TIM.2021.3116322 (2021).
  * [11] Epps, B. P. & Krivitzky, E. M.  Singular value decomposition of noisy data: noise filtering.  _Experiments in Fluids_ 60, 126, DOI: 10.1007/s00348-019-2768-4 (2019).
  * [12] Helfrick, M. N., Niezrecki, C., Avitabile, P. & Schmidt, T.  3d digital image correlation methods for full-field vibration measurement.  _Mechanical Systems and Signal Processing_ 25, 917–927, DOI: https://doi.org/10.1016/j.ymssp.2010.08.013 (2011).
  * [13] Olivieri, M. _et al._ Audio information retrieval and musical acoustics.  _IEEE Instrumentation & Measurement Magazine_ 24, 10–20, DOI: 10.1109/MIM.2021.9549233 (2021).
  * [14] Boll, S.  A spectral subtraction algorithm for suppression of acoustic noise in speech.  In _ICASSP ’79. IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 4, 200–203, DOI: 10.1109/ICASSP.1979.1170696 (1979).
  * [15] Zavarehei, E.  Boll spectral subtraction.  https://www.mathworks.com/matlabcentral/fileexchange/7675-boll-spectral-subtraction, MATLAB Central File Exchange (2023).  [Retrieved April 5, 2023.].
  * [16] D’Emilia, G., Razzè, L. & Zappa, E.  Uncertainty analysis of high frequency image-based vibration measurements.  _Measurement_ 46, 2630–2637, DOI: https://doi.org/10.1016/j.measurement.2013.04.075 (2013).
  * [17] Zhu, G. _et al._ Sound recovery via intensity variations of speckle pattern pixels selected with variance-based method.  _Optical Engineering_ 57, 026117, DOI: 10.1117/1.OE.57.2.026117 (2018).


# Enhancing Identification of Causal Effects by Pruning

Santtu Tikka<EMAIL_ADDRESS>
Juha Karvanen<EMAIL_ADDRESS>
Department of Mathematics and Statistics
P.O.Box 35 (MaD) FI-40014 University of Jyvaskyla, Finland

###### Abstract

Causal models communicate our assumptions about causes and effects in real-
world phenomena. Often the interest lies in the identification of the effect
of an action which means deriving an expression from the observed probability
distribution for the interventional distribution resulting from the action. In
many cases an identifiability algorithm may return a complicated expression
that contains variables that are in fact unnecessary. In practice this can
lead to additional computational burden and increased bias or inefficiency of
estimates when dealing with measurement error or missing data. We present
graphical criteria to detect variables which are redundant in identifying
causal effects. We also provide an improved version of a well-known
identifiability algorithm that implements these criteria.

Keywords: causal inference, identifiability, causal model, pruning, algorithm

##  1 Introduction

A formal framework for causal inference is provided by the probabilistic
causal model (Pearl, 2009) that encodes our knowledge of the variables of
interest and their mutual relationships. In observational studies
experimentation is not available, but through the causal model framework we
can still symbolically intervene on variables, forcing them to take certain
values as if an experiment had taken place. The question is whether we can
make inferences about the effect of the intervention in the post-intervention
model using only the observed probability distribution of the variables in the
model before the intervention took place. This question is formally defined as
identifiability of causal effects, and it has received considerable attention
in literature, including a number of algorithmic solutions (Huang and
Valtorta, 2006; Shpitser and Pearl, 2006; Tian and Pearl, 2002).

A causal model can be associated with a directed acyclic graph (DAG) that
represents the functional relationships of the variables included in the
model. The graphical representation provides us with the concept of
d-separation (Geiger et al., 1990), that can be used to infer conditional
independences between variables from the graph. If the distribution of the
variables implies no conditional independence statements other than those
already encoded in the graph, we say that the distribution is faithful
(Spirtes et al., 2000).

The use of d-separation in the post-intervention model is the basis of do-
calculus (Pearl, 1995), which consists of a set of inference rules for
manipulating interventional distributions. The purpose of do-calculus is to
derive formulas for causal effects and other causal queries, and it has been
shown to be complete with respect to the identifiability of causal effects
(Huang and Valtorta, 2006; Shpitser and Pearl, 2006). The derived formulas
provide recipes for estimating the causal effects from observational data.

When computing causal effect formulas, we often apply an identifiability
algorithm, such as the ID algorithm by Shpitser and Pearl (2006). Criteria for
identifiability such as the back-door criterion and front-door criterion are
available for manual derivations (Pearl, 2009) but the ID algorithm is more
general and thus more suitable for automated processing. The ID algorithm
splits the original problem into smaller subproblems which are then solved and
aggregated as the final expression for the causal effect.

Complicated expressions are likely to arise in situations where we have
included variables in our model that do not provide further benefit for the
identification of the causal effect of interest. It is often the case that
these variables nonetheless appear in the resulting formula, and deriving a
simpler expression with the variable eliminated can be non-trivial. It is hard
to specify what makes one expression simpler than another, but we can consider
a number of criteria to evaluate simplicity. For example, we can compare the
number of sums and fractions and the number of variables present in the
expression.

In this paper we propose a number of graphical criteria to infer which
variables in our causal model are in fact not necessary for identification.
These criteria allow us to prune the graph, which in practice means removing
specific vertices and considering identification in a latent projection. A
significantly simpler expression can be obtained by pruning alone, but we may
also combine pruning with simplification procedures that operate symbolically
on the interventional distribution as presented in (Tikka and Karvanen,
2017b). Applying these methods in conjunction often provides additional
benefits.

We present an identifiability algorithm that is able to recognize and
eliminate unnecessary variables from the graph based on our criteria resulting
in a simpler expression. When a large number of graphs and identifiability
queries are processed, evaluating simpler expressions has apparent
computational benefits. First, it is more efficient to evaluate a simpler
expression repeatedly especially when some variables have been completely
removed which further reduces the complexity of the task. Second, in practical
applications that involve real-world data, variables often contain missing
data or are affected by bias. Obtaining expression that do not involve such
variables can be of great benefit in estimation. Third, a simpler expression
is easier to communicate.

An introductory example motivates the use of the improved algorithm. We are
interested in the causal effect of $X$ on $Y$ in graph $G$ of Figure 1(1(a)).
Here, open circles denote unobserved variables. A more in-depth overview of
graph theoretic concepts used in this paper is provided in Section 2.

$W_{1}$$W_{2}$$Z_{2}$$X$$Z_{3}$$Z_{4}$$Z_{1}$$Y$$U_{1}$$U_{2}$$U_{3}$$U_{4}$$U_{5}$$U_{6}$$U_{7}$$U_{8}$
(a) Graph $G$.

$Z_{2}$$X$$Z_{1}$$Y$$U_{4}$$U_{5}$$U_{6}$ (b) Graph $G$ after pruning.

Figure 1: Graph $G$ before and after pruning for the introductory example.

The causal effect is identifiable and the output of the ID algorithm is

$\displaystyle\sum_{z_{2},z_{4},z_{3},z_{1}}$
$\displaystyle\left(\sum_{w_{1},w_{2},x^{\prime}}P(y|w_{1},z_{2},z_{4},w_{2},z_{3},x^{\prime},z_{1})P(x^{\prime}|w_{1},z_{2},z_{4},w_{2},z_{3})\right.\times$
$\displaystyle\quad\left.\vphantom{\sum_{x^{\prime}}}P(z_{3}|w_{1},z_{2},z_{4},w_{2})P(w_{2}|w_{1},z_{2},z_{4})P(z_{2}|w_{1})P(w_{1})\right)\left.\vphantom{\sum_{x^{\prime}}}\middle/\right.$
$\displaystyle\left(\sum_{w_{1},w_{2},x^{\prime},y^{\prime}}P(y^{\prime}|w_{1},z_{2},z_{4},w_{2},z_{3},x^{\prime},z_{1})P(x^{\prime}|w_{1},z_{2},z_{4},w_{2},z_{3})\right.\times$
$\displaystyle\quad\left.\vphantom{\sum_{x^{\prime}}}P(z_{3}|w_{1},z_{2},z_{4},w_{2})P(w_{2}|w_{1},z_{2},z_{4})P(z_{2}|w_{1})P(w_{1})\right)\times$
$\displaystyle\left(\sum_{w_{1},w_{2},z_{3}^{\prime},x^{\prime},y^{\prime}}P(y^{\prime}|w_{1},z_{2},z_{4},w_{2},z_{3}^{\prime},x^{\prime},z_{1})P(x^{\prime}|w_{1},z_{2},z_{4},w_{2},z_{3}^{\prime})\right.\,\times$
$\displaystyle\quad\left.P(z_{3}^{\prime}|w_{1},z_{2},z_{4},w_{2})P(w_{2}|w_{1},z_{2},z_{4})P(z_{2}|w_{1})P(w_{1})\vphantom{\sum_{x^{\prime}}}\right)\times$
$\displaystyle\qquad
P(z_{1}|w_{1},z_{2},z_{4},w_{2},x)P(z_{3}|z_{2})P(z_{4}).$

This expression is very cumbersome and complicated. However, it turns out that
a simpler expression exists for the causal effect. By exploiting the structure
of the graph and using standard probability calculus the following expression
can be obtained

$\sum_{z_{2},z_{1}}\left(\sum_{x^{\prime}}P(y|z_{2},z_{1},x^{\prime})P(x^{\prime}|z_{2})P(z_{2})\right)P(z_{1}|z_{2},x).$

This expression is simpler in every regard compared to the original output. It
contains fewer terms and no fractions. Also, we have completely removed the
variables $w_{1},w_{2}$ and $z_{4}$ from the expression. It can be shown that
identifying the causal effect in the original graph is equivalent to
identifying it in the graph depicted in Figure 1(1(b)). By running our
improved algorithm we are able to prune the original graph and obtain this
simpler expression directly. The algorithm works recursively and the pruning
is carried out at each stage of the recursion. The recursive pruning provides
significant benefits over pruning as a pre-processing step as demonstrated
later.

The paper is structured as follows. In Section 2 we review crucial definitions
and concepts related to graph theory and causal models. In Section 3 we focus
on semi-Markovian causal models and present the original formulation of the ID
algorithm. Our main results are presented in Section 4 and they are
implemented into an improved identifiability algorithm in Section 5. Examples
on the benefits of recursive pruning are provided in Section 6. Section 7
concludes with a discussion.

##  2 Definitions

We assume the reader to be familiar with a number of graph theoretic concepts
and refer them to works such as (Koller and Friedman, 2009). We use capital
letters to denote vertices and the respective variables, and small letters to
denote their values. Bold letters are used to denote sets. A directed graph
with a vertex set $\mathbf{V}$ and an edge set $\mathbf{E}$ is denoted by
$\langle\mathbf{V},\mathbf{E}\rangle$. For a graph
$G=\langle\mathbf{V},\mathbf{E}\rangle$ and a set of vertices
$\mathbf{W}\subseteq\mathbf{V}$ the sets
$\textrm{Pa}(\mathbf{W})_{G},\textrm{Ch}(\mathbf{W})_{G},\textrm{An}(\mathbf{W})_{G}$
and $\textrm{De}(\mathbf{W})_{G}$ denote a set that contains $\mathbf{W}$ in
addition to its parents, children, ancestors and descendants in $G$,
respectively. We also define the set $\textrm{Co}(\mathbf{W})_{G}$ to denote
the set of vertices that are connected to $\mathbf{W}$ in $G$ via paths where
the directionality of the edges is ignored, including $\mathbf{W}$. The root
set of a graph $G$ is the set of vertices without any descendants $\\{X\in
V\mid\textrm{De}(X)_{G}\setminus\\{X\\}=\emptyset\\}$, where $\setminus$
denotes the set difference. A subgraph of a graph
$G=\langle\mathbf{V},\mathbf{E}\rangle$ induced by a set of vertices
$\mathbf{W}\subset\mathbf{V}$ is denoted by $G[\mathbf{W}]$. This subgraph
retains all edges $V\rightarrow W$ of $G$ such that $V,W\in\mathbf{W}$. The
graph obtained from $G$ by removing all incoming edges of $\mathbf{X}$ and all
outgoing edges of $\mathbf{Z}$ is written as
$G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}},\underaccent{\,\rule{2.45004pt}{0.8pt}}{\mathbf{Z}}}$.
To facilitate analysis of causal effects we must first define the
probabilistic causal model (Pearl, 2009).

######  Definition 1 (Probabilistic Causal Model)

A _probabilistic causal model_ is a quadruple

$M=\langle\mathbf{U},\mathbf{V},\mathbf{F},P(\mathbf{u})\rangle,$

where

  1. 1.

$\mathbf{U}$ is a set of unobserved (exogenous) variables that are determined
by factors outside the model.

  2. 2.

$\mathbf{V}$ is a set $\\{V_{1},V_{2},\ldots,V_{n}\\}$ of observed
(endogenous) variables that are determined by variables in
$\mathbf{U}\cup\mathbf{V}$.

  3. 3.

$\mathbf{F}$ is a set of functions
$\\{f_{V_{1}},f_{V_{2}},\ldots,f_{V_{n}}\\}$ such that each $f_{V_{i}}$ is a
mapping from (the respective domains of)
$\mathbf{U}\cup(\mathbf{V}\setminus\\{V_{i}\\})$ to $V_{i}$, and such that the
entire set $\mathbf{F}$ forms a mapping from $\mathbf{U}$ to $\mathbf{V}$.

  4. 4.

$P(\mathbf{u})$ is a joint probability distribution of the variables in the
set $\mathbf{U}$.

Each causal model induces a causal diagram which is a directed graph that
provides a graphical means to convey our assumptions of the causal mechanisms
involved. The induced graph is constructed by adding a vertex for each
variable in $\mathbf{U}\cup\mathbf{V}$ and a directed edge from
$V_{i}\in\mathbf{U}\cup\mathbf{V}$ into $V_{j}\in\mathbf{V}$ whenever
$f_{V_{j}}$ is defined in terms of $V_{i}$.

Causal inference often focuses on a sub-class of models that satisfy
additional assumptions: each $U\in\mathbf{U}$ appears in at most two functions
of $\mathbf{F}$, the variables in $\mathbf{U}$ are mutually independent and
the induced graph of the model is acyclic. Models that satisfy these
additional assumptions are called _semi-Markovian causal models_. A graph
associated with a semi-Markovian model is called a _semi-Markovian graph_
(SMG). In SMGs every $U\in\mathbf{U}$ has at most two children. When semi-
Markovian models are considered it is common not to depict background
variables in the induced graph explicitly. Unobserved variables with exactly
two children are not denoted as $V_{i}\leftarrow U\rightarrow V_{j}$ but as a
bidirected edge $V_{i}\leftrightarrow V_{j}$ instead. Furthermore, unobserved
variables with only one or no children are omitted entirely. We also adopt
these abbreviations. For SMGs the sets
$\textrm{Pa}(\cdot)_{G},\textrm{Ch}(\cdot)_{G},\textrm{An}(\cdot)_{G},\textrm{De}(\cdot)_{G}$
and $\textrm{Co}(\cdot)_{G}$ contain only observed vertices. Additionally, a
subgraph $G[\mathbf{W}]$ of an SMG $G$ will also retain any bidirected edges
between vertices in $\mathbf{W}$.

Any DAG can be associated with an SMG by constructing its _latent projection_
(Verma, 1993).

######  Definition 2 (latent projection)

Let $G=\langle\mathbf{V}\cup\mathbf{L},\mathbf{E}\rangle$ be a DAG such that
the vertices in $\mathbf{V}$ are observed and the vertices in $\mathbf{L}$ are
latent. The _latent projection_ $L(G,\mathbf{V})$ is a DAG
$\langle\mathbf{V},\mathbf{E}_{L}\rangle$, where for every pair of distinct
vertices $Z,W\in\mathbf{V}$ it holds that:

  1. 1.

$L(G,\mathbf{V})$ contains an edge $Z\rightarrow W$ if there exists a directed
path $Z\rightarrow\cdots\rightarrow W$ in $G$ on which every vertex except $Z$
and $W$ is in $\mathbf{L}$.

  2. 2.

$L(G,\mathbf{V})$ contains an edge $Z\leftrightarrow W$ if there exists a path
from $Z$ to $W$ in $G$ that does not contain the pattern $Z\rightarrow
M\leftarrow W$ (a collider) and on which every vertex except $Z$ and $W$ is in
$\mathbf{L}$ and the first edge has an arrowhead pointing into $W$ and the
last edge has an arrowhead pointing into $Z$.

From the construction it is easy to see that a latent projection is in fact an
SMG. The induced graph of a probabilistic causal model can also be used to
derive conditional independences among the variables in the model using a
concept known as d-separation. We provide a definition for d-separation
(Shpitser and Pearl, 2008) which takes into account the presence of bidirected
edges and is thus suitable for SMGs.

######  Definition 3 (d-separation)

A path $P$ in an SMG $G$ is said to be d-separated by a set $\mathbf{Z}$ if
and only if either

  1. 1.

$P$ contains one of the following three patterns of edges: $I\rightarrow
M\rightarrow J$, $I\leftrightarrow M\rightarrow J$ or $I\leftarrow
M\rightarrow J$, such that $M\in\mathbf{Z}$, or

  2. 2.

$P$ contains one of the following three patterns of edges: $I\rightarrow
M\leftarrow J$, $I\leftrightarrow M\leftarrow J$, $I\leftrightarrow
M\leftrightarrow J$, such that $\textrm{De}(M)_{G}\cap\mathbf{Z}=\emptyset$.

Disjoint sets $\mathbf{X}$ and $\mathbf{Y}$ are said to be d-separated by
$\mathbf{Z}$ in $G$ if every path from $\mathbf{X}$ to $\mathbf{Y}$ is
d-separated by $\mathbf{Z}$ in $G$.

Whenever we can decompose the joint distribution of the observed variables
$\mathbf{V}$ and the unobserved variables $\mathbf{U}$ as
$P(\mathbf{v},\mathbf{u})=\prod_{W\in\mathbf{V}\cup\mathbf{U}}P(w|\textrm{Pa}^{*}(w)_{G})$,
where $\textrm{Pa}^{*}(\cdot)$ also contains the unobserved parents but not
the argument itself, we say that $G$ is an I-map of $P(\mathbf{v},\mathbf{u})$
(Pearl, 2009). If sets $\mathbf{X}$ and $\mathbf{Y}$ are d-separated by
$\mathbf{Z}$ in G, then $\mathbf{X}$ is independent of $\mathbf{Y}$ given
$\mathbf{Z}$ in every $P$ for which $G$ is an I-map (Pearl, 1988). We use the
notation of (Dawid, 1979) to denote this d-separation and conditional
independence statement as $(\mathbf{X}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Y}|\mathbf{Z})_{G}$. It is clear that
the graph induced by any semi-Markovian causal model is an I-map for the joint
distribution $P(\mathbf{v},\mathbf{u})$ induced by the model.

Our interest lies in the effects of actions imposing changes to the model. An
action that forces $\mathbf{X}$ to take a specific value $\mathbf{x}$ is
called an _intervention_ and it is denoted by $\textrm{do}(\mathbf{x})$
(Pearl, 2009). An intervention $\textrm{do}(\mathbf{x})$ on a model $M$
creates a new sub-model, denoted by $M_{\mathbf{x}}$, where the functions in
$\mathbf{F}$ that determine the value of $\mathbf{X}$ have been replaced with
constant functions. The _interventional distribution_ of a set of variables
$\mathbf{Y}$ in the model $M_{\mathbf{x}}$ is denoted by
$P_{\mathbf{x}}(\mathbf{y})$. This distribution is also known as the _causal
effect_ of $\mathbf{X}$ on $\mathbf{Y}$.

Multiple causal models can share the same graph, and thus the same sub-model
resulting from an intervention. The question is, are our assumptions encoded
in the causal model sufficient to uniquely specify an interventional
distribution of interest. This notion is captured by the following definition
(Shpitser and Pearl, 2006).

######  Definition 4 (identifiability)

Let $G=\langle\mathbf{V},\mathbf{E}\rangle$ be an SMG and let $\mathbf{X}$ and
$\mathbf{Y}$ be disjoint sets of variables such that
$\mathbf{X},\mathbf{Y}\subset\mathbf{V}$. The causal effect of $\mathbf{X}$ on
$\mathbf{Y}$ is said to be _identifiable_ from $P$ in $G$ if
$P_{\mathbf{x}}(\mathbf{y})$ is uniquely computable from $P(\mathbf{V})$ in
any causal model that induces $G$.

In order to show the identifiability of a given effect we have to express the
interventional distribution in terms of observed probabilities only. The link
between observed probabilities and interventional distributions is provided by
three inference rules known as _do-calculus_ (Pearl, 1995):

  1. 1.

Insertion and deletion of observations:

$P_{\mathbf{x}}(\mathbf{y}|\mathbf{z},\mathbf{w})=P_{\mathbf{x}}(\mathbf{y}|\mathbf{w}),\text{
if }(\mathbf{Y}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Z}|\mathbf{X},\mathbf{W})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}.$

  2. 2.

Exchanging actions and observations:

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y}|\mathbf{w})=P_{\mathbf{x}}(\mathbf{y}|\mathbf{z},\mathbf{w}),\text{
if }(\mathbf{Y}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Z}|\mathbf{X},\mathbf{W})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}},\underaccent{\,\rule{2.45004pt}{0.8pt}}{\mathbf{Z}}}}.$

  3. 3.

Insertion and deletion of actions:

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y}|\mathbf{w})=P_{\mathbf{x}}(\mathbf{y}|\mathbf{w}),\text{
if }(\mathbf{Y}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Z}|\mathbf{X},\mathbf{W})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}},\accentset{\rule{5.60002pt}{0.8pt}}{Z(\mathbf{W})}}},$

where
$Z(\mathbf{W})=\mathbf{Z}\setminus\textrm{An}(\mathbf{W})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}.$

Completeness of do-calculus was established independently by Huang and
Valtorta (2006) and Shpitser and Pearl (2006). In this paper we focus on the
solution provided by Shpitser and Pearl (2006). They constructed an
identifiability algorithm called ID, which in essence applies the rules of do-
calculus and breaks the problem into smaller sub-problems repeatedly.

##  3 ID Algorithm

In order to present the ID algorithm, we first need some additional
definitions that are used to construct the graphical criterion for non-
identifiability (Shpitser and Pearl, 2006).

######  Definition 5 (C-component)

Let $G$ be an SMG and let $C\subseteq G$. If every pair of vertices in $C$ is
connected by a bidirected path, that is a path consisting entirely of
bidirected edges, then $C$ is a _C-component_ (confounded component).
Furthermore, $C$ is a _maximal C-component_ if $C$ contains every vertex
connected to $C$ via bidirected paths in $G$ and $C$ is an induced subgraph of
$G$.

No restrictions are imposed on the directed edges of a C-component. The same
is not true for the maximal C-components (also known as districts) of an SMG
$G$, which are assumed to be induced subgraphs of $G$. This requirement
guarantees the uniqueness of the maximal C-components.

Maximal C-components are an important tool for identifying causal effects. The
set of maximal C-components of a semi-Markovian graph $G$ is denoted by
$C(G)$. A result in (Tian, 2002) states that if
$C=\langle\mathbf{C},\mathbf{E}\rangle$ is a maximal C-component and $C\subset
G$ then the causal effect $P_{\mathbf{v}\setminus\mathbf{c}}(\mathbf{c})$ is
identifiable from $P$ in $G$. A distribution $P$ of a semi-Markovian model
also factorizes with respect to the maximal C-components of the induced graph
$G$ such that $P(\mathbf{v})=\prod_{\langle\mathbf{C},\mathbf{E}\rangle\in
C(G)}P_{\mathbf{v}\setminus\mathbf{c}}(\mathbf{c})$ (Shpitser and Pearl,
2006). It is precisely this factorization that the ID algorithm takes
advantage of. A specific type of C-component is used to characterize
problematic structures for identifiability.

######  Definition 6 (C-forest)

Let $G$ be an SMG and let $\mathbf{Y}$ be the root set of $G$. If $G$ is a
C-component and all observed vertices have at most one child, then $G$ is a
$\mathbf{Y}-$_rooted C-forest_.

The complete criterion for non-identifiability uses a structure formed by two
C-forests:

######  Definition 7 (hedge)

Let $\mathbf{X},\mathbf{Y}\subset\mathbf{V}$ be disjoint sets of variables and
let $G$ be an SMG. Let $F=\langle\mathbf{V}_{F},\mathbf{E}_{F}\rangle$ and
$F^{\prime}=\langle\mathbf{V}_{F^{\prime}},\mathbf{E}_{F^{\prime}}\rangle$ be
$\mathbf{R}$-rooted C-forests in $G$ such that
$\mathbf{V}_{F}\cap\mathbf{X}\neq\emptyset$,
$\mathbf{V}_{F^{\prime}}\cap\mathbf{X}=\emptyset$, $F^{\prime}\subseteq F$,
and
$\mathbf{R}\subseteq\textrm{An}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$.
Then $F$ and $F^{\prime}$ form a hedge for $P_{\mathbf{x}}(\mathbf{y})$ in
$G$.

Intuitively hedges are a difficult concept. Whenever a hedge is present, there
exists two causal models with the same probability distribution over
$\mathbf{V}$ but their interventional distributions do not agree.
Observational data can not be used to estimate causal effects in this
scenario. We are now ready to present the ID algorithm.

1:Value assignments $\mathbf{x}$ and $\mathbf{y}$, joint distribution
$P(\mathbf{v})$ and an SMG $G=\langle\mathbf{V},\mathbf{E}\rangle$. $G$ is an
$I$-map of $P$.

2:Expression for $P_{\mathbf{x}}(\mathbf{y})$ in terms of $P(\mathbf{v})$ or
FAIL$(F,F^{\prime})$.

3:

4:function ID$(\mathbf{y},\mathbf{x},P,G)$

5:if $\mathbf{x}=\emptyset$,

6: return $\sum_{v\in\mathbf{v}\setminus\mathbf{y}}P(\mathbf{v})$.

7:if $\mathbf{V}\neq\textrm{An}(\mathbf{Y})_{G}$,

8: return
ID$(\mathbf{y},\mathbf{x}\cap\textrm{An}(\mathbf{y})_{G},P(\textrm{An}(\mathbf{Y})_{G}),G[\textrm{An}(\mathbf{Y})_{G}])$.

9:let
$\mathbf{W}=(\mathbf{V}\setminus\mathbf{X})\setminus\textrm{An}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$.

10:if $\mathbf{W}\neq\emptyset$,

11: return ID$(\mathbf{y},\mathbf{x}\cup\mathbf{w},P,G)$.

12:if
$C(G[\mathbf{V}\setminus\mathbf{X}])=\\{G[\mathbf{S}_{1}],\ldots,G[\mathbf{S}_{k}]\\}$,

13: return
$\sum_{v\in\mathbf{v}\setminus(\mathbf{y}\cup\mathbf{x})}\prod_{i=1}^{k}$
ID($\mathbf{s}_{i},\mathbf{v}\setminus\mathbf{s}_{i},P,G)$.

14:if $C(G[\mathbf{V}\setminus\mathbf{X}])=\\{G[\mathbf{S}]\\}$,

15: if $C(G)=\\{G\\}$,

16: throw FAIL$(G,G[\mathbf{S}])$.

17: if $G[\mathbf{S}]\in C(G)$,

18: return
$\sum_{v\in\mathbf{s}\setminus\mathbf{y}}\prod_{V_{i}\in\mathbf{S}}{P(v_{i}|v_{\pi}^{(i-1)})}$.

19: if
$(\exists\mathbf{S}^{\prime})\mathbf{S}\subset\mathbf{S}^{\prime}\textbf{ such
that }G[\mathbf{S}^{\prime}]\in C(G)$,

20: return
ID$(\mathbf{y},\mathbf{x}\cap\mathbf{s}^{\prime},\prod_{V_{i}\in\mathbf{S}^{\prime}}{P(V_{i}|V_{\pi}^{(i-1)}\cap\mathbf{S}^{\prime},v_{\pi}^{(i-1)}\setminus\mathbf{s}^{\prime}),G[\mathbf{S}^{\prime}}])$.

Algorithm 1 The causal effect of intervention $do(\mathbf{X}=\mathbf{x})$ on
$\mathbf{Y}$ (ID).

Shpitser and Pearl (2006) showed that whenever Algorithm 1 returns an
expression for a causal effect, it is correct. Additionally whenever line 5 is
triggered there exists a hedge for the causal effect currently being
identified. This result establishes the completeness of the algorithm and also
the completeness of do-calculus, since the soundness of each line of the
algorithm can be shown with do-calculus and standard probability calculus
alone.

##  4 Pruning of Variables

In this section we present a number of results that deal with variables that
are not necessary for identification either by removing them from the graph or
by considering them latent. When the causal effect
$P_{\mathbf{x}}(\mathbf{y})$ is considered in an SMG we can present an outline
of the pruning process:

  1. 1.

Removal of non-ancestors of $\mathbf{Y}$.

  2. 2.

Removal of ancestors of $\mathbf{X}$ that are connected to $\mathbf{Y}$ only
via $\mathbf{X}$ under certain conditions.

  3. 3.

Removal of vertices connected to other vertices only through a single vertex.

  4. 4.

Identification in a latent projection under certain conditions.

Steps 2–4 are new and they are based on the results of this section. Step 1 is
derived from a useful result by Shpitser and Pearl (2006) which states that
for a causal effect $P_{\mathbf{x}}(\mathbf{y})$ we can always ignore non-
ancestors of $\mathbf{Y}$.

###### Lemma 8

Let $\mathbf{X}^{\prime}=\mathbf{X}\cap\textrm{An}(\mathbf{Y})_{G}$. Then
$P_{\mathbf{x}}(\mathbf{y})$ obtained from $P$ in $G$ is equal to
$P_{\mathbf{x}^{\prime}}^{\prime}(\mathbf{y})$ obtained from
$P^{\prime}=P(\textrm{An}(\mathbf{Y})_{G})$ in
$G[\textrm{An}(\mathbf{Y})_{G}]$.

Lemma 8 is implemented on line 2 of Algorithm 1. Not all ancestors of
$\mathbf{Y}$ are always necessary for identification. The next result states
that we may sometimes remove ancestors of $\mathbf{X}$ that are connected to
$\mathbf{Y}$ only through $\mathbf{X}$.

###### Theorem 9

Let $G$ be an SMG and let $\mathbf{Z}\subset\mathbf{V}$ be the set of all
vertices such that $\mathbf{X}$ intercepts all paths from $\mathbf{Z}$ to
$\mathbf{Y}$. Then the causal effect $P_{\mathbf{x}}(\mathbf{y})$ obtained
from $P$ in $G$ is equal to $P^{\prime}_{\mathbf{x}}(\mathbf{y})$ obtained
from $P^{\prime}=P(\mathbf{V}\setminus\mathbf{Z})$ in
$G[\mathbf{V}\setminus\mathbf{Z}]$ if $\mathbf{Z}$ contains no members of
$\mathbf{X}$ and if
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$.

Proof  Let $G^{\prime}=G[\mathbf{V}\setminus\mathbf{Z}]$ and assume that
$G^{\prime}=L(G,\mathbf{V}\setminus\mathbf{Z})$. Let
$\mathbf{U}_{\mathbf{Z}}$, $\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$ and
$\mathbf{U}_{\mathbf{X}}$ be sets of unobserved variables such that for all
$U\in\mathbf{U}_{\mathbf{Z}}$ it holds that
$\textrm{Ch}(U)_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}\subseteq\mathbf{Z}$,
for all $U\in\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$ it holds that
$\textrm{Ch}(U)_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}\subseteq\mathbf{V}\setminus\mathbf{Z}$
and for all $U\in\mathbf{U}_{\mathbf{X}}$ it holds that
$\textrm{Ch}(U)_{G}\in\mathbf{X}$. The sets $\mathbf{U}_{\mathbf{Z}}$,
$\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$ and $\mathbf{U}_{\mathbf{X}}$
partition $\mathbf{U}$ because $\mathbf{X}$ intercepts all paths from
$\mathbf{Z}$ to $\mathbf{Y}$. According to the third rule of do-calculus
$P_{\mathbf{x}}(\mathbf{y})=P_{\mathbf{x},\mathbf{z}}(\mathbf{y})$ because the
condition $(\mathbf{Y}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Z}|\mathbf{X})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$
holds as removing the edges incoming to $\mathbf{X}$ separates $\mathbf{X}$
from its ancestors. Applying the truncated factorization formula (Pearl, 2009)
we have that

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y})=\sum_{\mathbf{U}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z})}P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})\prod_{\mathbf{U}}P(u_{i}).$

Since variables in $\mathbf{U}_{\mathbf{Z}}$ can only be parents of variables
in $\mathbf{Z}$ or $\mathbf{X}$ in $G$, we can sum them out from the previous
expression and obtain

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y})=\sum_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}\cup\mathbf{U}_{\mathbf{X}}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z})}P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})\prod_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}\cup\mathbf{U}_{\mathbf{X}}}P(u_{i}).$

Similarly, variables in $\mathbf{U}_{\mathbf{X}}$ can only be parents of
variables in $\mathbf{X}$ in $G$, so we can also sum them out of the
expression to obtain

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y})=\sum_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z})}P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})\prod_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}P(u_{i}).$

We let $\mathbf{V}^{\prime}=\mathbf{V}\setminus\mathbf{Z}$. Verma (1993)
showed that a graph and its latent projection have the same set of conditional
independence relations among the observed variables. Because we have assumed
that $G^{\prime}=L(G,\mathbf{V}\setminus\mathbf{Z})$ every conditional
independence between variables in $\mathbf{V}^{\prime}$ and
$\mathbf{U}_{\mathbf{V}^{\prime}}$ applies in both $G$ and $G^{\prime}$. We
have that for all $V_{i}\in\mathbf{V}^{\prime}\setminus\mathbf{X}$ it holds
that
$P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})=P^{\prime}(v_{i}|\textrm{Pa}(v_{i})_{G^{\prime}}\setminus\\{v_{i}\\})$
and for all $U_{i}\in\mathbf{U}_{\mathbf{V}^{\prime}}$ it holds that
$P(u_{i})=P^{\prime}(u_{i})$. Finally we obtain

$P_{\mathbf{x},\mathbf{z}}(\mathbf{y})=\sum_{\mathbf{U}_{\mathbf{V}^{\prime}}}\sum_{\mathbf{V}^{\prime}\setminus(\mathbf{Y}\cup\mathbf{X})}\prod_{\mathbf{V}^{\prime}\setminus\mathbf{X}}P^{\prime}(v_{i}|\textrm{Pa}(v_{i})_{G^{\prime}}\setminus\\{v_{i}\\})\prod_{\mathbf{U}_{\mathbf{V}^{\prime}}}P^{\prime}(u_{i})=P^{\prime}_{\mathbf{x}}(\mathbf{y}).$

Theorem 9 can also be applied in a more general setting where a subset of
$\mathbf{X}$ intercepts all paths from a set $\mathbf{Z}$ to $\mathbf{Y}$

###### Corollary 10

Let $G$ be an SMG and let $\mathbf{Z}\subset\mathbf{V}$ be the set of all
vertices such that a set $\mathbf{W}\subseteq\mathbf{X}$ intercepts all paths
from $\mathbf{Z}$ to $\mathbf{Y}$ and no member of
$\mathbf{X}\setminus\mathbf{W}$ is a descendant of $\mathbf{W}$. Then the
causal effect $P_{\mathbf{x}}(\mathbf{y})$ obtained from $P$ in $G$ is equal
to $P^{\prime}_{\mathbf{x}\setminus\mathbf{z}}(\mathbf{y})$ obtained from
$P^{\prime}=P(\mathbf{V}\setminus\mathbf{Z})$ in
$G[\mathbf{V}\setminus\mathbf{Z}]$ if $\mathbf{Z}$ contains no members of
$\mathbf{W}$ and if
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$.

Proof  Since $\mathbf{W}$ intercepts all paths from $\mathbf{Z}$ to
$\mathbf{Y}$ and no member of $\mathbf{X}\setminus\mathbf{W}$ is a descendant
of $\mathbf{W}$, it follows that no member of $\mathbf{W}$ is in $\mathbf{Z}$.
According to the third rule of do-calculus we have that
$(\mathbf{Y}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\mathbf{Z}|\mathbf{X}\setminus\mathbf{Z})_{G_{\overline{\mathbf{X}\setminus\mathbf{Z}}}}$
and
$P_{\mathbf{x}}(\mathbf{y})=P_{\mathbf{x}\setminus\mathbf{z}}(\mathbf{y})$.
The claim now follows by applying Theorem 9 to
$P_{\mathbf{x}\setminus\mathbf{z}}(\mathbf{y})$.

###### Corollary 11

When the causal effect $P_{\mathbf{x}}(\mathbf{y})$ is considered in graph
$G$, a set of vertices
$\mathbf{Z}=\textrm{An}(\mathbf{Y})_{G}\setminus\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$
can be removed from $G$ if
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$.

Proof  The set $\textrm{An}(\mathbf{Y})_{G}$ contains $\mathbf{Y}$ in addition
to the ancestors of $\mathbf{Y}$, and the set
$\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$
contains $\mathbf{Y}$ and all vertices that are connected to $\mathbf{Y}$ via
a path that does not contain edges incoming to $\mathbf{X}$. Therefore,
$\mathbf{Z}$ contains such ancestors of $\mathbf{Y}$ that all paths from
$\mathbf{Z}$ to $\mathbf{Y}$ contain $\mathbf{X}$. The removal of $\mathbf{Z}$
from $G$ is now licensed by Corollary 10.

Corollary 11 provides a constructive criterion for the set $\mathbf{Z}$
described in Corollary 10 when $G$ consists only of $\mathbf{Y}$ and its
ancestors. If a vertex $Z_{i}$ is a member of
$\textrm{An}(\mathbf{Y})_{G}\setminus\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$
then it must be connected to $\mathbf{Y}$ only through paths containing some
$\mathbf{W}_{Z_{i}}\subseteq\mathbf{X}$. We can always choose the sets
$\mathbf{W}_{Z_{i}}$ in such a way that the union
$\mathbf{W}=\cup\mathbf{W}_{Z_{i}}$ over the members $Z_{i}$ of
$\textrm{An}(\mathbf{Y})_{G}\setminus\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$
has no descendants in $\mathbf{X}\setminus\mathbf{W}$. The set $\mathbf{W}$
intercepts all paths from $\mathbf{Z}=\cup\\{Z_{i}\\}$ to $\mathbf{Y}$.
Conversely, if $Z_{i}$ is a vertex such that a set
$\mathbf{W}\subseteq\mathbf{X}$ intercepts all paths from $Z_{i}$ to
$\mathbf{Y}$, then $Z_{i}$ cannot be connected to $\mathbf{Y}$ in
$G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}$. If we assume that
$G=G[\textrm{An}(\mathbf{Y})_{G}]$ it follows that $Z_{i}$ is a member of
$\textrm{An}(\mathbf{Y})_{G}\setminus\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$.

We present a simple example to motivate the usefulness of Corollary 11. We
apply the ID algorithm to identify the causal effect of $X$ on $Y$ in graph
$G$ of Figure 2(2(a)).

$W_{1}$$W_{2}$$X$$Z$$Y$ (a) Graph $G$.

$X$$Z$$Y$ (b) Subgraph $G[\\{X,Y,Z\\}]$.

Figure 2: A graph for an example where Corollary 11 allows us to remove
vertices $W_{1}$ and $W_{2}$ when the causal effect of $X$ on $Y$ is
considered.

Applying the ID algorithm results in the following expression for the causal
effect

$\sum_{z}P(z|w_{1},w_{2},x)\left(\sum_{w_{1},w_{2},x^{\prime}}P(y|w_{1},w_{2},x^{\prime},z)P(x^{\prime}|w_{1},w_{2})P(w_{2}|w_{1})P(w_{1})\right).$

Applying Corollary 11 in this case would result in the removal of the vertices
$W_{1}$ and $W_{2}$ from the graph, since they are ancestors of $Y$ in $G$ but
not connected to $Y$ in $G_{\accentset{\rule{2.79996pt}{0.8pt}}{X}}$ and the
corresponding latent projection is the subgraph $G[\\{X,Y,Z\\}]$ of Figure
2(2(b)). Running the ID algorithm in this subgraph provides us the following
expression

$\sum_{z}P(z|x)\left(\sum_{x^{\prime}}P(y|x^{\prime},z)P(x^{\prime})\right).$

We may consider this expression simpler compared to the previous output by
noting that $W_{1}$ and $W_{2}$ do not appear in the expression and it has
fewer unique terms. The same expression can also be obtained manually by
applying the front-door criterion (Pearl, 2009).

Often the question of identifiability can not be answered directly by neither
the back-door nor the front-door criterion which leads us to more general
methods, such as the ID algorithm. We are interested in the causal effect of
$W_{1}$, $X_{1}$ and $X_{2}$ on $Y_{1}$ and $Y_{2}$ in the graph of Figure
3(3(a)).

$W_{1}$$W_{2}$$X_{1}$$X_{2}$$Z$$Y_{1}$$Y_{2}$ (a) Graph $G$.

$X_{1}$$X_{2}$$Z$$Y_{1}$$Y_{2}$ (b) Subgraph
$G[\\{X_{1},X_{2},Z,Y_{1},Y_{2}\\}]$.

Figure 3: A graph for an example where the back-door and front-door criteria
are unavailable, but Corollary 11 allows us to remove vertices $W_{1}$ and
$W_{2}$ even when $W_{1}$ is part of the intervention.

Direct application of the ID algorithm provides us with the following
expression

$\sum_{z}P(y_{1}|w_{2},w_{1},x_{2},x_{1},z)P(z|w_{2},x_{2})\left(\sum_{w_{2},x_{2}^{\prime}}P(y_{2}|w_{2},x_{2}^{\prime},z)P(x_{2}^{\prime}|w_{2})P(w_{2})\right).$

Corollary 11 licenses the removal of $W_{1}$ and $W_{2}$ from the graph. By
running ID again in the resulting subgraph
$G[\\{X_{1},X_{2},Z,Y_{1},Y_{2}\\}]$ as shown in Figure 3(3(b)) we obtain a
simpler expression for the causal effect

$\sum_{z}P(y_{1}|x_{1},x_{2},z)P(z|x_{2})\left(\sum_{x_{2}^{\prime}}P(y_{2}|x_{2}^{\prime},z)P(x_{2}^{\prime})\right).$

The next example illustrates the necessity of the assumption
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$ of
Theorem 9 and Corollary 10. We are interested in the causal effect of $X_{1}$
and $X_{2}$ on $Y$ in graph $G$ of Figure 4(4(a)).

$X_{1}$$X_{2}$$Z$$W$$Y$ (a) Graph $G$.

$X_{1}$$X_{2}$$Z$$Y$ (b) Subgraph $G[\\{X_{1},X_{2},Z,Y\\}]$.

$X_{1}$$X_{2}$$Z$$Y$ (c) Latent projection $L(G,\\{X_{1},X_{2},Z,Y\\})$.

Figure 4: An example where the assumptions of Corollary 10 are not met because
the subgraph in panel (b) and the latent projection in panel (c) differ from
each other.

In this graph $W$ is connected to $Y$ only through $X_{1}$ and $X_{2}$, but
the corresponding latent projection does not match the subgraph with $W$
removed as seen in Figures 4(4(b)) and 4(4(c)). In $G$ the causal effect is
identifiable, but it is not identifiable in the latent projection
$G^{\prime}=L(G,\\{X_{1},X_{2},Z,Y\\})$. In this latent projection a
bidirected edge exists between $X_{1}$ and $X_{2}$ and a hedge is formed by
the C-forests $G^{\prime}$ and $G[\\{Y\\}]$.

We may also remove sets of vertices that are connected to the rest of the
graph only through a single vertex even when no intervention on the
corresponding variable has taken place.

###### Theorem 12

Let $G$ be an SMG such that $G=G[An(\mathbf{Y})_{G}]$ for a set of vertices
$\mathbf{Y}$ and let $W$ be a vertex of $G$. If there exists a set
$\mathbf{Z}$ such that $\mathbf{Z}\cap(\mathbf{Y}\cup\mathbf{X})=\emptyset$
and $\mathbf{Z}$ is connected to $\mathbf{V}\setminus\mathbf{Z}$ only through
$W$. Then the causal effect $P_{\mathbf{x}}(\mathbf{y})$ obtained from $P$ in
$G$ is equal to $P^{\prime}_{\mathbf{x}}(\mathbf{y})$ obtained from
$P^{\prime}=P(\mathbf{V}\setminus\mathbf{Z})$ in
$G[\mathbf{V}\setminus\mathbf{Z}]$.

Proof  Let $G^{\prime}=G[\mathbf{V}\setminus\mathbf{Z}]$ and let
$\mathbf{U}_{\mathbf{Z}}$ and $\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$ be
sets of unobserved variables such that for all $U\in\mathbf{U}_{\mathbf{Z}}$
it holds that $\textrm{Ch}(U)_{G}\in\mathbf{Z}\cup\\{W\\}$ and for all
$U\in\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$ it holds that
$\textrm{Ch}(U)_{G}\in(\mathbf{V}\setminus\mathbf{Z})\cup\\{W\\}$. Sets
$\mathbf{U}_{\mathbf{Z}}$ and $\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$
partition $\mathbf{U}$ because $\mathbf{Z}$ is connected to
$\mathbf{V}\setminus\mathbf{Z}$ only through $W$. Applying the truncated
factorization formula yields

$P_{\mathbf{x}}(\mathbf{y})=\sum_{\mathbf{U}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X})}P(w|\textrm{Pa}(w)_{G}\setminus\\{w\\})\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\\{W\\})}P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})\prod_{\mathbf{U}}P(u_{i}).$

Since variables in $\mathbf{U}_{\mathbf{Z}}$ and $\mathbf{Z}$ can be connected
to the other vertices of $G$ only through $W$ we can complete the
marginalization over $\mathbf{Z}$ and $\mathbf{U}_{\mathbf{Z}}$

$P_{\mathbf{x}}(\mathbf{y})=\\!\\!\sum_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}\\!P(w|\textrm{Pa}(w)_{G}\setminus(\mathbf{z}\cup\\{w\\}))\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z}\cup\\{W\\})}\\!P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})\\!\prod_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}P(u_{i}).$

Because we have assumed that $\mathbf{Z}$ is disconnected from
$\mathbf{V}\setminus\mathbf{Z}$ in
$G_{\accentset{\rule{2.79996pt}{0.8pt}}{W}}$ we have that
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$.
Therefore, just as in the proof of Theorem 9, we have that
$P(v_{i}|\textrm{Pa}(v_{i})_{G}\setminus\\{v_{i}\\})=P^{\prime}(v_{i}|\textrm{Pa}(v_{i})_{G^{\prime}}\setminus\\{v_{i}\\})$
for all $V_{i}\in\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z}\cup\\{W\\})$ and
$P(u_{i})=P^{\prime}(u_{i})$ for all
$U_{i}\in\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}$. Additionally, we have
$P(w|\textrm{Pa}(w)_{G}\setminus(\mathbf{z}\cup\\{w\\}))=P(w|Pa(w)_{G^{\prime}}\setminus\\{w\\})$.
Finally we obtain

$\displaystyle P_{\mathbf{x}}(\mathbf{y})$
$\displaystyle=\sum_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}P(w|\textrm{Pa}(w)_{G^{\prime}}\setminus\\{w\\})\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z}\cup\\{W\\})}P(v_{i}|\textrm{Pa}(v_{i})_{G^{\prime}}\setminus\\{v_{i}\\})\prod_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}P(u_{i})$
$\displaystyle=\sum_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}\sum_{\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X}\cup\mathbf{Z})}\prod_{\mathbf{V}\setminus(\mathbf{X}\cup\mathbf{Z})}P(v_{i}|\textrm{Pa}(v_{i})_{G^{\prime}}\setminus\\{v_{i}\\})\prod_{\mathbf{U}_{\mathbf{V}\setminus\mathbf{Z}}}P(u_{i})$
$\displaystyle=P_{\mathbf{x}}^{\prime}(\mathbf{y}).$

###### Corollary 13

Let $W$ be a vertex of an SMG $G$ and let
$\mathbf{R}=\textrm{An}(W)_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}\setminus\textrm{De}(\mathbf{X})_{G}$.
When the causal effect $P_{\mathbf{x}}(\mathbf{y})$ is considered in graph
$G$, the set of vertices
$\mathbf{T}=\mathbf{R}\setminus\textrm{Co}(\mathbf{V}\setminus\mathbf{R})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{W}}}$
can be removed from the graph if $G=G[\textrm{An}(\mathbf{Y})_{G}]$.

Proof  No descendant of $\mathbf{X}$ can be removed via theorem 12 since they
are connected to $\mathbf{X}$ and the set to be removed cannot itself contain
$\mathbf{X}$. By removing descendants of $\mathbf{X}$ and $\mathbf{X}$ itself,
and assuming that $G=G[\textrm{An}(\mathbf{Y})_{G}]$, we have that
$\mathbf{T}\cap(\mathbf{X}\cup\mathbf{Y})=\emptyset$. Thus it remains to
remove those vertices from $\mathbf{R}$ that are connected to
$\mathbf{V}\setminus\mathbf{R}$ through a path that does not contain $W$.
Removal of the resulting set $\mathbf{T}$ from the graph is now licensed by
theorem 12.

In the following example we consider the causal effect of $X$ on $Y$ in graph
$G$ of Figure 5(5(a)) and show how Corollary 13 can be applied.

$W_{1}$$W_{2}$$X$$Z$$Y$ (a) Graph $G$.

$X$$Z$$Y$ (b) Subgraph $G[\\{X,Y,Z\\}]$.

Figure 5: First example of Corollary 13.

The ID algorithm succeeds in identifying the causal effect and returns
following expression for it

$\sum_{w_{1},w_{2},z}P(z|x,w_{1},w_{2})P(w_{2}|x,w_{1})P(w_{1}|x)\left(\sum_{x^{\prime}}P(y|x^{\prime},w_{1},w_{2},z)P(x^{\prime})\right).$

We apply Corollary 13 which allows us to remove $W_{1}$ and $W_{2}$ from the
graph, since they are connected to other vertices of the graph through a
single vertex $Z$. Applying the ID algorithm in the resulting subgraph
$G[\\{X,Y,Z\\}]$ of Figure 5(5(b)) provides us the following expression

$\sum_{z}P(z|x)\left(\sum_{x^{\prime}}P(y|x^{\prime},z)P(x^{\prime})\right).$

The same expression can be obtained manually by applying the front-door
criterion.

We provide another example on Corollary 13 with a slightly more complicated
graph. We are interested in the causal effect of $X$ on $Y$ in graph $G$ of
Figure 6(6(a))

$W_{1}$$W_{2}$$X$$Z_{1}$$Z_{2}$$Y$ (a) Graph $G$.

$X$$Z_{1}$$Z_{2}$$Y$ (b) Subgraph $G[\\{X,Y,Z_{1},Z_{2}\\}$.

Figure 6: Second example of Corollary 13.

We obtain a formula for the causal effect using the ID algorithm

$\frac{\sum_{w_{2},z_{2}}P(y|w_{1},w_{2},z_{2},z_{1},x)P(x|w_{1},w_{2},z_{2},z_{1})P(z_{2}|w_{1},w_{2})P(w_{2}|w_{1})}{\left(\sum_{w_{2},z_{2},y}P(y|w_{1},w_{2},z_{2},z_{1},x)P(x|w_{1},w_{2},z_{2},z_{1})P(z_{2}|w_{1},w_{2})P(w_{2}|w_{1})\right)}.$

Vertices $W_{1}$ and $W_{2}$ are connected to other vertices only through
$Z_{2}$ which allows us to remove them from the graph. We obtain a simpler
formula for the causal effect from the subgraph $G[\\{X,Y,Z_{1},Z_{2}\\}]$ of
Figure 6(6(b))

$\frac{\sum_{z_{2}}P(y|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}{\sum_{z_{2},y}P(y|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}.$

The previous results have allowed us to completely remove specific vertices
from the graph. Next we will consider cases where a vertex is present in the
graph, but it is not necessary to observe it. This means that instead of the
original graph we may consider identifiability in the corresponding latent
projection, as characterized by the following lemma.

###### Lemma 14

Let $G=\langle\mathbf{V},\mathbf{E}\rangle$ be an SMG and let
$\mathbf{X},\mathbf{Y}$ and $\mathbf{Z}$ be disjoint sets of variables. Let
$P(\mathbf{V})$ be the joint distribution of $\mathbf{V}$. Then the causal
effect of $\mathbf{X}$ on $\mathbf{Y}$ is identifiable from $P^{\prime}$ in
the latent projection $L(G,\mathbf{V}\setminus\mathbf{Z})$ where
$P^{\prime}=P(\mathbf{V}\setminus\mathbf{Z})$, if and only if it is
identifiable from $P^{\prime}$ in $G$.

Proof  Tian (2002) showed that the latent projection has the same topological
relations over the observables and that it has the same set of maximal
C-components. Thus if $P_{\mathbf{x}}(\mathbf{y})$ is identifiable from
$P^{\prime}$ in $G$ it is also identifiable from $P^{\prime}$ in
$L(G,\mathbf{V}\setminus\mathbf{Z})$ with the same expression and vice versa.

In situations where $\mathbf{X}$ is a singleton we can exploit the following
sufficient condition for identifiability by Tian and Pearl (2002).

###### Theorem 15

The causal effect $P_{x}(\mathbf{y})$ is identifiable if there is no
bidirected path between $X$ and any of its children in
$G[\textrm{An}(\mathbf{Y})_{G}]$.

We can regard any variable as latent when $\mathbf{X}$ is a singleton if the
respective latent projection does not induce such a bidirected path.

###### Corollary 16

Let $G$ be an SMG and let $\mathbf{Y}$ be a set of vertices. Let
$X,W\in\mathbf{V}$ such that $X\neq W$, $W\not\in\mathbf{Y}$ and
$X,W\in\textrm{An}(\mathbf{Y})_{G}$. The causal effect $P_{x}(\mathbf{y})$
obtained from $P$ in $G$ is equal to $P^{\prime}_{x}(\mathbf{y})$ obtained
from $P^{\prime}=P(\textrm{An}(\mathbf{Y})_{G}\setminus\\{w\\})$ and
$G^{\prime}=L(G[\textrm{An}(\mathbf{Y})_{G}],\textrm{An}(\mathbf{Y})_{G}\setminus\\{W\\})$
if there is no bidirected path from $X$ to any of its children in
$G^{\prime}$.

Proof  By Theorem 15 the causal effect $P^{\prime}_{x}(\mathbf{y})$ is
identifiable from $P^{\prime}$ in $G^{\prime}$. By Lemma 14
$P^{\prime}_{x}(\mathbf{y})$ is now identifiable from $P^{\prime}$ in $G$.
$P_{x}(y)$ obtained from $P^{\prime}$ in $G$ is equal to $P^{*}_{x}(y)$
obtained from $P^{*}=P(\textrm{An}(\mathbf{Y})_{G})$ in
$G[\textrm{An}(\mathbf{Y})]$ since identifiability from $P^{\prime}$ implies
identifiability from $P$. Finally, $P^{*}_{x}(\mathbf{y})$ obtained from
$P^{*}=P(\textrm{An}(\mathbf{Y})_{G})$ in $G[\textrm{An}(\mathbf{Y})_{G}]$ is
equal to $P_{x}(y)$ obtained from $P$ in $G$.

We continue with an example on how Corollary 16 can be applied in practice. We
consider the causal effect of $X$ on $Y$ in the graph $G$ of Figure 7(7(a)).

$X$$Y$$Z_{1}$$Z_{2}$$Z_{3}$ (a) Graph $G$.

$X$$Y$$Z_{1}$$Z_{2}$ (b) Latent projection $L(G,\\{X,Y,Z_{1},Z_{2}\\})$.

Figure 7: A graph for an example where Corollary 16 allows us to make variable
$Z_{3}$ latent.

The causal effect is identifiable and the output of the ID algorithm is

$\displaystyle\sum_{z_{2},z_{3},z_{1}}P(z_{1}|z_{2},x)\frac{\left(\sum_{x^{\prime}}P(y|z_{2},x^{\prime},z_{3},z_{1})P(z_{3}|z_{2},x^{\prime})P(x^{\prime}|z_{2})P(z_{2})\right)}{\left(\sum_{x^{\prime},y^{\prime}}P(y^{\prime}|z_{2},x^{\prime},z_{3},z_{1})P(z_{3}|z_{2},x^{\prime})P(x^{\prime}|z_{2})P(z_{2})\right)}\times$
$\displaystyle\qquad\left(\sum_{x^{\prime},z_{3},y^{\prime}}P(y^{\prime}|z_{2},x^{\prime},z_{3},z_{1})P(z_{3}|z_{2},x^{\prime})P(x^{\prime}|z_{2})P(z_{2})\right)P(z_{3}|z_{2}).$

We may apply Corollary 16 by noting that $G=G[\textrm{An}(Y)_{G}]$ and that
there is no bidirected path between $X$ and its only child $Z_{1}$ in the
latent projection $L(G,\mathbf{V}\setminus\\{Z_{3}\\})$ as depicted in Figure
7(7(b)).

Running the ID algorithm in $L(G,\mathbf{V}\setminus\\{Z_{3}\\})$ results in
the following expression

$\sum_{z_{2},z_{1}}\left(\sum_{x^{\prime}}P(y|z_{2},x^{\prime},z_{1})P(x^{\prime}|z_{2})P(z_{2})\right)P(z_{1}|z_{2},x).$

##  5 Pruning Identifiability Algorithm

Corollaries 11, 13 and 16 can be implemented as additional steps for the ID
algorithm. For Algorithm 2, line 3 implements Corollary 11, line 4 implements
Corollary 13 and line 5 implements Corollary 16. Other lines are identical to
the ID algorithm. This algorithm is provided by the R package _causaleffect_
which implements various causal inference algorithms such as the original ID
algorithm (Tikka and Karvanen, 2017a).

The ordering of the variables in the loop on line 4 has no effect on the
resulting expression, but the ordering does matter on line 5. Choosing a
different ordering may lead to a different expression. For example, when
identifying the causal effect of $X$ on $Y$ in graph $G$ of Figure 8 one may
obtain either the back-door formula or the front-door formula by proceeding in
either the topological ordering or the reverse-topological ordering of the
vertices, respectively.

$X$$Z$$Y$$W$ Figure 8: Graph $G$ where different latent projections lead to
different expressions for $P_{x}(y)$.

1:Value assignments $\mathbf{x}$ and $\mathbf{y}$, joint distribution
$P(\mathbf{v})$ and an SMG $G=\langle\mathbf{V},\mathbf{E}\rangle$. $G$ is an
$I$-map of $P$.

2:Expression for $P_{\mathbf{x}}(\mathbf{y})$ in terms of $P(\mathbf{v})$ or
FAIL$(F,F^{\prime})$.

3:

4:function PID$(\mathbf{y},\mathbf{x},P,G)$

5:if $\mathbf{x}=\emptyset$,

6: return $\sum_{v\in\mathbf{v}\setminus\mathbf{y}}P(\mathbf{v})$.

7:if $\mathbf{V}\neq\textrm{An}(\mathbf{Y})_{G}$,

8: return
PID$(\mathbf{y},\mathbf{x}\cap\textrm{An}(\mathbf{y})_{G},P(\textrm{An}(\mathbf{Y})_{G}),G[\textrm{An}(\mathbf{Y})_{G}])$

9:let
$\mathbf{Z}=\textrm{An}(\mathbf{Y})_{G}\setminus\textrm{Co}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$.

10:if $\mathbf{Z}\neq\emptyset$ and
$G[\mathbf{V}\setminus\mathbf{Z}]=L(G,\mathbf{V}\setminus\mathbf{Z})$,

11: return
PID$(\mathbf{y},\mathbf{x}\setminus\mathbf{z},P(\mathbf{V}\setminus\mathbf{Z}),G[\mathbf{V}\setminus\mathbf{Z}])$

12:for $W\in\mathbf{V}\setminus\mathbf{X}$ do

13: let
$\mathbf{R}=\textrm{An}(W)_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}\setminus\textrm{De}(\mathbf{X})_{G}$.

14: let
$\mathbf{T}=\mathbf{T}\cup(\mathbf{R}\setminus\textrm{Co}(\mathbf{V}\setminus\mathbf{R})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{W}}})$.

15:if $\mathbf{T}\neq\emptyset$,

16: return
PID$(\mathbf{y},\mathbf{x},P(\mathbf{V}\setminus\mathbf{T}),G[\mathbf{V}\setminus\mathbf{T}])$

17:if $\mathbf{X}=\\{X\\}$,

18: let $G[\mathbf{S}_{X}]\in C(G),X\in\mathbf{S}_{X}$.

19: if
$\textrm{Ch}(\mathbf{X})_{G[\mathbf{S}_{X}]}\setminus\mathbf{X}=\emptyset$,

20: for $W\in\mathbf{V}\setminus(\mathbf{Y}\cup\mathbf{X})$ do

21: let $G^{\prime}=L(G,\mathbf{V}\setminus\\{W\\}).$

22: let $G^{\prime}[\mathbf{S}^{\prime}_{X}]\in
C(G^{\prime}),X\in\mathbf{S}^{\prime}_{X}$.

23: if
$\textrm{Ch}(\mathbf{X})_{G^{\prime}[\mathbf{S}^{\prime}_{X}]}\setminus\mathbf{X}=\emptyset$,

24: $P\leftarrow P(\mathbf{V}\setminus\\{W\\})$.

25: $G\leftarrow G^{\prime}$.

26: $\mathbf{V}\leftarrow\mathbf{V}\setminus\\{W\\}$.

27:let
$\mathbf{W}=(\mathbf{V}\setminus\mathbf{X})\setminus\textrm{An}(\mathbf{Y})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{\mathbf{X}}}}$.

28:if $\mathbf{W}\neq\emptyset$,

29: return PID$(\mathbf{y},\mathbf{x}\cup\mathbf{w},P,G)$.

30:if
$C(G[\mathbf{V}\setminus\mathbf{X}])=\\{G[\mathbf{S}_{1}],\ldots,G[\mathbf{S}_{k}]\\}$,

31: return
$\sum_{v\in\mathbf{v}\setminus(\mathbf{y}\cup\mathbf{x})}\prod_{i=1}^{k}$
PID($\mathbf{s}_{i},\mathbf{v}\setminus\mathbf{s}_{i},P,G)$.

32:if $C(G[\mathbf{V}\setminus\mathbf{X}])=\\{G[\mathbf{S}]\\}$,

33: if $C(G)=\\{G\\}$,

34: throw FAIL$(G,G[\mathbf{S}])$.

35: if $G[\mathbf{S}]\in C(G)$,

36: return
$\sum_{v\in\mathbf{s}\setminus\mathbf{y}}\prod_{V_{i}\in\mathbf{S}}{P(v_{i}|v_{\pi}^{(i-1)})}$.

37: if
$(\exists\mathbf{S}^{\prime})\mathbf{S}\subset\mathbf{S}^{\prime}\textbf{ such
that }G[\mathbf{S}^{\prime}]\in C(G)$,

38: return
PID$(\mathbf{y},\mathbf{x}\cap\mathbf{s}^{\prime},\prod_{V_{i}\in\mathbf{S}^{\prime}}{P(V_{i}|V_{\pi}^{(i-1)}\cap\mathbf{S}^{\prime},v_{\pi}^{(i-1)}\setminus\mathbf{s}^{\prime}),G[\mathbf{S}^{\prime}}])$.

Algorithm 2 A pruning identifiability algorithm (PID) for causal effects.

On line 5 we first check whether the set $\mathbf{X}$ is a singleton. If so,
we determine whether any children of $X$ belong the same C-component as $X$.
If no such children exist, we iterate over the possible latent projections in
an attempt to find one that does not induce a bidirected path between $X$ and
any of its children in the projection. After the new pruning steps have been
carried out, we attempt identification using the original formulation of the
ID algorithm.

We return to the example presented in the introduction and show how Algorithm
2 operates to derive the expression for $P_{x}(y)$ in the graph of Figure
1(1(a)). We choose the topological ordering to be
$Y>Z_{1}>X>Z_{3}>W_{2}>Z_{4}>Z_{2}>W_{1}$. We begin on line 3, since
$\mathbf{Z}=\textrm{An}(Y)_{G}\setminus\textrm{Co}(Y)_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{X}}}=\mathbf{V}\setminus\\{W_{1},W_{2}\\}$
and continue by calling
$\textsc{PID}(y,x,P(\mathbf{V}\setminus\\{W_{1},W_{2}\\}),G[\mathbf{V}\setminus\\{W_{1},W_{2}\\}])$.
In the presentation below, $\mathbf{V}$ and $G$ refer to the set of vertices
and graph in the current call of PID, respectively.

Next we enter the loop on line 4. When $W=Z_{1}$ we obtain
$\mathbf{R}=\textrm{An}(Z_{1})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{X}}}\setminus\textrm{De}(X)_{G}=\\{Z_{2},Z_{4}\\}$
and
$\mathbf{R}\setminus\textrm{Co}(\mathbf{V}\setminus\mathbf{R})_{G_{\accentset{\rule{2.79996pt}{0.8pt}}{Z_{1}}}}=\\{Z_{2},Z_{4}\\}\setminus\\{Z_{2}\\}=\\{Z_{4}\\}$
since $Z_{4}$ is an ancestor of $Z_{1}$ and it is disconnected from other
vertices in $G_{\accentset{\rule{2.79996pt}{0.8pt}}{Z_{1}}}$. Other choices of
$W$ result in an empty set. When the loop is completed we have
$\mathbf{T}=\\{Z_{4}\\}$ and we continue by calling
$\textsc{PID}(y,x,P(\mathbf{V}\setminus\\{Z_{4}\\}),G[\mathbf{V}\setminus\\{Z_{4}\\}])$.

Since $\mathbf{X}$ is a singleton we end up on line 5 and find no children of
$X$ in the same C-component as $X$. We assume a reverse-topological ordering
for the loop and begin with the latent projection
$L(G,\mathbf{V}\setminus\\{Z_{2}\\})$. This projection creates a bidirected
edge between $X$ and $Z_{1}$ bringing them into the same C-component in the
projection. Thus we continue with $L(G,\mathbf{V}\setminus\\{Z_{1}\\})$. This
projection is also unsuitable, since $Y$ is a child of $X$ in the projection
and there is a bidirected arc connecting them. We continue with
$L(G,\mathbf{V}\setminus\\{Z_{3}\\})$ and find that $X$ is not connected to
its children via bidirected paths in the projection. Thus we set $P\leftarrow
P(\mathbf{V}\setminus\\{Z_{3}\\})$, $G\leftarrow
L(G,\mathbf{V}\setminus\\{Z_{3}\\})$ and
$\mathbf{V}\leftarrow\mathbf{V}\setminus\\{Z_{3}\\}$. This projection is
identical to the graph depicted in Figure 7(7(b)). After these steps, only
lines of the original ID algorithm are called, which results in the expression

$\sum_{z_{2},z_{1}}\left(\sum_{x^{\prime}}P(y|z_{2},z_{1},x^{\prime})P(x^{\prime}|z_{2})P(z_{2})\right)P(z_{1}|z_{2},x).$

##  6 Examples on Recursive Pruning

Corollaries 10, 13 and 16 often provide direct benefits when applied before
the ID algorithm. The following examples show why they are also useful as
recursive steps as implemented in the PID algorithm.

We are tasked with identifying the causal effect of $X$ on $Y$ in graph $G$
depicted in Figure 9(9(a))

$Z_{1}$$Z_{2}$$Z_{3}$$Z_{4}$$X$$Y$ (a) Graph $G$.

$Z_{3}$$Z_{4}$$X$$Y$ (b) Subgraph $G[\\{Z_{3},X,Y\\}]$.

Figure 9: A graph for the example of recursive application of Corollary 11
within the ID algorithm.

Initially there are no vertices that are connected to other vertices only
through $X$. As a recursive step of the ID algorithm, we are tasked with
identifying $P^{\prime}_{z_{3},x}(y)$ from $P^{\prime}$, where

$P^{\prime}=\sum_{z_{2}}P(y|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3}),$

in the subgraph $G[\\{Z_{3},X,Y\\}]$ shown in Figure 9(9(b)). In this graph
$Z_{3}$ is connected to other vertices only through $X$ and it can be removed
according to Corollary 11, since the corresponding latent projection is the
subgraph $G[\\{X,Y\\}]$. Thus we sum out $Z_{3}$ from $P^{\prime}$ and the
resulting expression for the causal effect is

$\sum_{z_{4}}\frac{\sum_{z_{2},z_{3}}P(y|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}{\sum_{z_{2},z_{3},y^{\prime}}P(y^{\prime}|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}.$

If Corollary 11 is not applied at this stage, the final expression is instead

$\displaystyle\sum_{z_{4}}\left(\frac{\sum_{z_{2}}P(y|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}{\sum_{z_{2},y^{\prime}}P(y^{\prime}|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}\right.\times$
$\displaystyle\quad\left.\frac{\sum_{z_{2},y^{\prime}}P(y^{\prime}|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}{\sum_{z_{2},y^{\prime},z_{4}}P(y^{\prime}|z_{3},z_{2},z_{1},x,z_{4})P(z_{4}|z_{3},z_{2},z_{1},x)P(x|z_{3},z_{2},z_{1})P(z_{2}|z_{3})P(z_{3})}\right).$

Using Corollary 11 provides us with a simpler expression in this situation by
completely removing the second term from the product inside the summation.

Next we show how Corollary 13 can also be applied at a recursive step. Our
interest lies in the causal effect of $X$ on $Y$ in graph $G$ of Figure
10(10(a))

$Z_{1}$$Z_{2}$$Z_{3}$$X$$Y$ (a) Graph $G$.

$Z_{2}$$Z_{3}$$X$$Y$ (b) Subgraph $G[\\{Z_{2},Z_{3},X,Y\\}]$.

Figure 10: A graph for the example of recursive application of Corollary 13
within the ID algorithm.

There are no vertices that are connected to other vertices in the graph via a
single vertex. When the ID algorithm is applied we eventually reach a step
where the causal effect of $P^{\prime}_{z_{2},x}(y)$ is to be identified from
$P^{\prime}$, where

$P^{\prime}=P(y|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2}),$

in the subgraph $G[\\{Z_{2},Z_{3},X,Y\\}]$ which is depicted in Figure
10(10(b)).

In this graph $Z_{3}$ can be removed according to Corollary 13, since $Z_{3}$
is connected to other vertices of the subgraph only through $Y$. The resulting
distribution is obtained by summing out $Z_{3}$ from $P^{\prime}$. The final
expression for the causal effect is now

$\frac{\sum_{z_{2},z_{3}}P(y|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}{\sum_{z_{2},z_{3},y^{\prime}}P(y^{\prime}|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}.$
(1)

If Corollary 13 is not applied, the resulting expression is instead

$\displaystyle\sum_{z_{3}}\left(\frac{\sum_{z_{2}}P(y|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}{\sum_{z_{2},y^{\prime}}P(y^{\prime}|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}\times\right.$
$\displaystyle\quad\left.\vphantom{\sum_{z}}\sum_{z_{2},x,y^{\prime}}P(y^{\prime}|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})\right).$

As in the previous example, the benefit of applying Corollary 13 is apparent.

We can also take advantage of latent projections recursively via Corollary 16
as shown in the next example. Our interest lies in the causal effect of $X$ on
$Y$ in graph $G$ of Figure 11.

$Z_{1}$$Z_{2}$$W$$X$$Y$ (a) Graph $G$.

$W$$X$$Y$ (b) Subgraph $G[\\{X,W,Y\\}]$.

Figure 11: A graph for the example of recursive application of Corollary 16
within the ID algorithm.

Here $X$ is connected to its child $W$ via a bidirected path and thus they
belong to the same C-component rendering Corollary 16 unusable at this time.
However, as a recursive step of the ID algorithm we have to identify
$P^{\prime}_{x}(y)$ from $P^{\prime}$, where

$P^{\prime}=\sum_{z_{2}}P(y|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})$

in the subgraph $G[\\{X,W,Y\\}]$. In this subgraph $X$ is not connected to its
child $W$ via a bidirected path. We also find that the latent projection
$L(G[\\{X,W,Y\\}],\\{X,Y\\})$ does not induce such a path between $X$ and $Y$.
We can now continue identification in this latent projection and sum out $W$
from $P^{\prime}$. The resulting expression for the causal effect is

$\frac{\sum_{z_{2},w}P(y|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}{\sum_{z_{2},w,y^{\prime}}P(y^{\prime}|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})},$

whereas the expression without applying the corollary is instead

$\displaystyle\sum_{w}\left(\frac{\sum_{z_{2}}P(y|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}{\sum_{z_{2},y^{\prime}}P(y^{\prime}|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}\right.\times$
$\displaystyle\quad\frac{\sum_{z_{2},y^{\prime}}P(y^{\prime}|z_{2},z_{1},x,w)P(w|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}{\sum_{z_{2},w^{\prime},y^{\prime}}P(y^{\prime}|z_{2},z_{1},x,w)P(w^{\prime}|z_{2},z_{1},x)P(x|z_{2},z_{1})P(z_{2})}.$

Additional examples are provided as an R script (R Core Team, 2017) at the
JMLR online paper repository. The script also includes all of the examples
presented in this paper.

An interesting question is how pruning works together with simplification
presented in (Tikka and Karvanen, 2017b). We return to the example on
identifying the causal effect of $X$ on $Y$ in the graph of Figure 10. If we
apply the ID algorithm without pruning and perform simplification as a post-
processing step, then the resulting expression is

$\sum_{z_{3}}\frac{\sum_{z_{2}}P(y|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}{\sum_{z_{2}}P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}P(z_{3}|z_{2}).$
(2)

This expression is in some aspects simpler than expression (1) obtained using
pruning alone, but does contain a sum over $Z_{3}$ that was not originally
present.

When pruning is introduced to the ID algorithm and simplification is again
applied, the resulting expression is instead

$\frac{\sum_{z_{3},z_{2}}P(y|z_{2},z_{3},z_{1},x)P(x|z_{2},z_{3},z_{1})P(z_{3}|z_{2})P(z_{2})}{\sum_{z_{2}}P(x|z_{2},z_{1})P(z_{2})},$

which is noticeably simpler than expressions (1) and (2). This example shows,
that when pruning methods are employed together with simplification, a simpler
expression can be reached than what is possible with either pruning or
simplification alone.

##  7 Discussion

We have presented criteria for removing variables from causal models that are
not necessary to achieve identifiability for a given causal effect, and showed
how these criteria can be applied in practice. We integrated our results into
a new version of the ID algorithm called PID as presented in Algorithm 2 to
facilitate automatic processing of identifiability queries. It should be noted
that the ID algorithm already performs some pruning such as removing non-
ancestors of $\mathbf{Y}$.

The pruning operations carried out by Algorithm 2 can significantly simplify
the resulting expression compared to the traditional ID algorithm. Benefits of
simplification can be realized in various settings. A simpler expression is
easier to understand and to evaluate, since the dimensionality of the problem
has been reduced. This is especially true for settings where the expression
has to be evaluated repeatedly. Simplification can also help dealing with data
where some variables are affected by bias or contain missing data. Obtaining
an expression that does not contain these variables has clear advantages. It
may also be of interest to obtain a different expression for the same causal
effect.

The choice of variable ordering on line 5 of Algorithm 2 is not arbitrary.
However, available external knowledge may guide our selection to prefer
certain orderings. For example, in a situation where two latent projections
are mutually exclusive, we may prefer an ordering where the variable that is
associated with the smallest cost, or of which we have the most accurate
measurements is not considered latent.

When PID is applied in conjunction with simplification methods described in
(Tikka and Karvanen, 2017b), various situations that lead to complex
expressions can be taken into account. These methods complement each other,
since the results in this paper deal with completely removing variables from
the resulting expression, whereas the simplification methods focus on symbolic
summation of so-called atomic expressions, which are expression consisting of
a single sum and a number of product terms. An expression for a causal effect
may consist of multiple atomic expressions, some of which can be simplified
and some of which can not.

We showed via examples that our improvements are not simply pre-processing
steps to be carried out before calling the ID algorithm, but actually provide
significant benefits when applied recursively. As the ID algorithm manipulates
the original graph it often enables the application of our results as well. As
hedges characterize identifiability, it is possible to consider latent
projections in a more general manner, but this is not necessarily beneficial
for simplification. One could construct an algorithm that performs a search
over the possible subsets of $\mathbf{V}$, and checks whether identifiability
is retained in the corresponding latent projection. However, as we have shown
via examples, this may not be enough to obtain a simpler expression, and the
recursive structure of the ID algorithm needs to be taken advantage of.
Instead, we could consider a variant of the PID algorithm, where line 5 is
replaced by this procedure. However, one must be careful when applying this
method, so that the computation does not become intractable when the number of
vertices increases due to the complexity of the search.

Acknowledgments

We wish to thank Professor Jukka Nyblom for his comments that greatly helped
to improve this paper. We also thank the anonymous reviewers for their
insightful feedback. The work belongs to the profiling area ”Decision
analytics utilizing causal models and multiobjective optimization” (DEMO)
supported by Academy of Finland (grant number 311877).

## References

  * Dawid (1979) A. P. Dawid.  Conditional independence in statistical theory.  _Journal of the Royal Statistical Society B_ , 41:1–31, 1979.
  * Geiger et al. (1990) D. Geiger, T. Verma, and J. Pearl.  Identifying independence in Bayesian networks.  _Networks_ , 20(5):507–534, 1990.
  * Huang and Valtorta (2006) Y. Huang and M. Valtorta.  Pearl’s calculus of intervention is complete.  In _Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence_ , pages 217–224. AUAI Press, 2006.
  * Koller and Friedman (2009) D. Koller and N. Friedman.  _Probabilistic Graphical Models: Principles and Techniques_.  MIT Press, 2009.
  * Pearl (1988) J. Pearl.  _Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference_.  Morgan Kaufmann, 1988.
  * Pearl (1995) J. Pearl.  Causal diagrams for empirical research.  _Biometrika_ , 82:669–688, 1995.
  * Pearl (2009) J. Pearl.  _Causality: Models, Reasoning and Inference_.  Cambridge University Press, 2nd edition, 2009.
  * R Core Team (2017) R Core Team.  _R: A Language and Environment for Statistical Computing_.  R Foundation for Statistical Computing, 2017.  URL https://www.R-project.org/.
  * Shpitser and Pearl (2006) I. Shpitser and J. Pearl.  Identification of joint interventional distributions in recursive semi-Markovian causal models.  In _Proceedings of the 21st National Conference on Artificial Intelligence - Volume 2_ , pages 1219–1226. AAAI Press, 2006.
  * Shpitser and Pearl (2008) I. Shpitser and J. Pearl.  Complete identification methods for the causal hierarchy.  _Journal of Machine Learning Research_ , 9:1941–1979, 2008\.  ISSN 1532-4435.
  * Spirtes et al. (2000) P. Spirtes, C. Glymour, and R. Scheines.  _Causation, Prediction, and Search_.  MIT press, 2nd edition, 2000.
  * Tian (2002) J. Tian.  _Studies in Causal Reasoning and Learning_.  PhD thesis, Department of Computer Science, University of California, Los Angeles, 2002.
  * Tian and Pearl (2002) J. Tian and J. Pearl.  A general identification condition for causal effects.  In _Proceedings of the 18th National Conference on Artificial Intelligence_ , pages 567–573. AAAI Press, 2002.
  * Tikka and Karvanen (2017a) S. Tikka and J. Karvanen.  Identifying causal effects with the R package causaleffect.  _Journal of Statistical Software_ , 76(12):1–30, 2017a.
  * Tikka and Karvanen (2017b) S. Tikka and J. Karvanen.  Simplifying probabilistic expressions in causal inference.  _Journal of Machine Learning Research_ , 18(36):1–30, 2017b.  URL http://jmlr.org/papers/v18/16-166.html.
  * Verma (1993) T. S. Verma.  Graphical aspects of causal models.  Technical report, Department of Computer Science, University of California, Los Angeles, 1993.  R-191.