Gabriel José Gil Perez
https://orcid.org/0000-0002-7728-9522
Augusto de Jesús Gónzalez García
https://orcid.org/0000-0002-2367-6113  Bachelor of Computer Science Faculty of
Mathematics and Computing Graphics/uhlogo

# Nonparametric causal discovery with applications to cancer bioinformatics

Jean Pierre Gómez Matos

(November 2022
github.com/jean-pierre-gm/CChains)

###### Abstract

Many natural phenomena are intrinsically causal. The discovery of the cause-
effect relationships implicit in these processes can help us to understand and
describe them more effectively, which boils down to causal discovery about the
data and variables that describe them. However, causal discovery is not an
easy task. Current methods for this are extremely complex and costly, and
their usefulness is strongly compromised in contexts with large amounts of
data or where the nature of the variables involved is unknown. As an
alternative, this paper presents an original methodology for causal discovery,
built on essential aspects of the main theories of causality, in particular
probabilistic causality, with many meeting points with the inferential
approach of regularity theories and others. Based on this methodology, a non-
parametric algorithm is developed for the discovery of causal relationships
between binary variables associated to data sets, and the modeling in graphs
of the causal networks they describe. This algorithm is applied to gene
expression data sets in normal and cancerous prostate tissues, with the aim of
discovering cause-effect relationships between gene dysregulations leading to
carcinogenesis. The gene characterizations constructed from the causal
relationships discovered are compared with another study based on principal
component analysis (PCA) on the same data, with satisfactory results.

Keywords: causality, causal sufficiency, graphs, causal graphs, gene, genetic
dysregulation, cancer.

To each and every one of the people who got me this far.

###### Acknowledgements.

I want to thank my parents, who have been by my side unconditionally in each
and every phase of my life, have silently resisted the problems and
difficulties without making me a direct participant, and have supported me in
every small project, giving their all and more to get me ahead. To my
grandmother, who sees through my eyes, always attentive to everything that
happens to me, one of the few who knows how to make me smile when I need it
most with her witticisms, and who goes out of her way for me. On them I place
all my affection and love, and all my gratitude. To my tutor Gabriel, who has
put in a superhuman effort to carry out this project and has become the most
important person I have met in the last year, and who, more than my mentor, I
would gladly like to call him my friend. To all my friends, old and new, who
in one way or another have built the path I have taken to this point: to
Daniel Martínez, who went from being my friend to becoming the brother I never
had, and without whom my life would surely not have the same color, to Deby,
who has become part of me, a confidant of secrets, evils and smiles, in whom I
have placed all my trust, as she has in me, to Juan Pablo, unconditional
friend who has become my arms and legs many times, has earned my trust and
respect in record time, and to whom I will never be able to repay everything
he has done for me, to Javier, one of my goals to overcome during this race,
the person with whom I have unconsciously competed in silence, one of those I
admire most for his ability, Daniel Rivero, the person who, along with Javier,
comes to mind when I hear the word genius, with whom it has been a pleasure to
work throughout this entire period. To each and every one of them, thank you
very much

###### Contents

  1. Introduction
  2. 1 State of the art
    1. 1.1 Regularity theory
    2. 1.2 Probabilistic causality theory
    3. 1.3 Theories of manipulability
    4. 1.4 Graphs
    5. 1.5 Bayesian networks
    6. 1.6 Causal graphs
    7. 1.7 PC algorithm for causal discovery
  3. 2 Proposal
    1. 2.1 Causal relationships
      1. 2.1.1 Sufficient, necessary, and contributory causes
      2. 2.1.2 Causation by omission and prevention
    2. 2.2 Data presentation
    3. 2.3 Model approach
      1. 2.3.1 Triangles
    4. 2.4 Modeling
      1. 2.4.1 Causal sufficiency
      2. 2.4.2 Loevinger coefficient
      3. 2.4.3 Construction of the causal graph
    5. 2.5 Spurious arcs
      1. 2.5.1 Order of elimination of spurious arcs
    6. 2.6 Non-transitive paths
    7. 2.7 Redundant arcs
      1. 2.7.1 Order of elimination of redundant arcs
    8. 2.8 Remaining undirected edges
  4. 3 Implementation details and experiments
    1. 3.1 General configuration
    2. 3.2 Construction of the causal graph
      1. 3.2.1 Input matrix compression
    3. 3.3 Causal graph simplification
    4. 3.4 Modules and dependencies
    5. 3.5 Implementation details
      1. 3.5.1 Construction
      2. 3.5.2 Spurious arcs
      3. 3.5.3 Redundant arcs
      4. 3.5.4 Pseudocode and time complexity
      5. 3.5.5 Remaining undirected edges
  5. 4 Results
    1. 4.0.1 Problem
    2. 4.0.2 Data origin
    3. 4.0.3 Processing
    4. 4.0.4 Artificial cancer state gene
    5. 4.0.5 Construction of the genetic alterations graph
    6. 4.0.6 Results

###### List of Figures

  1. 2.1 First case of adjacent triangles, with conflict for the elimination of spurious arcs
  2. 2.2 Second case of adjacent triangles, with conflict for the elimination of spurious arcs
  3. 2.3 Third case of adjacent triangles, without conflicts for the elimination of spurious arcs
  4. 2.4 Example of possible latent contributory causes
  5. 2.5 Examples of undirected edge orientation in the presence of transitivity
  6. 2.6 Incorrect removal order for transitive arcs
  7. 2.7 Correct removal order for transitive arcs
  8. 3.1 Diagram of dependencies between program modules
  9. 4.1 Distribution of degrees in the graph of genetic alterations
  10. 4.2 Subgraph of the simplified graph, induced by the vertices with contrast greater than 5%
  11. 4.3 Subgraph of the base network, induced by vertices with contrast greater than 5% in the simplified network

###### List of Tables

  1. 2.1 Truth table of the material implication.
  2. 2.2 Possible distribution of three variables $i$, $j$, and $k$ in 22 individuals
  3. 2.3 Possible distribution of three variables $i$, $j$, and $k$, in 22 individuals
  4. 2.4 Possible distribution of three variables $i$, $j$, and $k$ in 22 individuals
  5. 4.1 Vertices with contrast greater than 5%
  6. 4.2 Vertices with contrast greater than 5%
  7. 4.3 First 15 vertices of the ranking by PageRank
  8. 4.4 First 15 vertices of the ranking by PageRank, in the graph induced by vertices with paths to the artificial vertex of cancer
  9. 4.5 PageRank of the vertices corresponding to the genes of the PCA analysis
  10. 4.6 PageRank of the vertices corresponding to the genes in the analysis by PCA
  11. 4.7 PageRank of the vertices corresponding to genes from PCA analysis
  12. 4.8 PageRank of the vertices (without transposition of the graph) corresponding to genes from PCA analysis

## Introduction

Causality is a fundamental concept in our way of understanding the world. It
appears as a subject of study by Aristotle in his book Analytical Seconds, but
it was in the 18th century that it acquired its first detailed formulation
from the hand of David Hume. According to this author, causality is associated
with the achievement of two events, contiguous in time and space.Hume Since
then, the existence of a necessary connection between the two has been
presumed, which must be explained. It is the current impossibility of
specifying the nature of this necessary connection in empirical terms that
makes the study of causality a true conceptual challenge.

Human intuition seems to be able to determine what is cause and what is effect
in a large number of cases. For example, if a billiard ball hits another, it
can be inferred that the motion of the first is the cause of the subsequent
motion of the second. Modern science has been able to expand this intuition to
regions and scales of the universe inaccessible to our perception, revealing
the causal mechanisms behind certain phenomena. To mention one case, today it
is known that certain proteins are responsible for the translation of the
genetic code into others, even when this is not a process observable to the
naked eye. However, there are cases where not even the support of modern
science is enough to establish causal relationships. For example, the causal
relationships established between socioeconomic indicators are not always easy
to explain in a mechanistic framework, and therefore it is not easy to predict
the influence of specific policies on them.

This scenario has guaranteed that in recent years discovery and causal
inference have gained scientific recognition. In fact, the 2021 Nobel Prize in
Economics was awarded to J. Angrist and G. Imbens for their contributions to
the methodology for the analysis of causal relationships.Nobel Also, the field
of causal modeling has been developed, which brings together a set of
techniques to re-present systems of causal relationships and infer them from
probabilities. One of the most important figures within this field is Judea
Pearl, who created the computational basis for information processing under
uncertainty. He is also credited with the invention of Bayesian networks, as
well as the main algorithms used for inference in these models. Their work
revolutionized the field of artificial intelligence, and overturned the long-
held belief that causation can only be determined from randomized controlled
trials, which isimpossible in areas such as biological and social
sciences.Turing His contributions to causal modeling earned him the 2011
Turing Award, "for his fundamental contributions to artificial intelligence
through the development of a calculus for probabilistic and causal
reasoning".Turing2

Nowadays, there is no doubt about the potential and importance of causal
discovery. However, most algorithms designed for this use complex and
extremely expensive methods. They generally consist of parametric methods, ie,
they make assumptions about the probability distribution in the data, and are
not practical solutions for large volumes of data. This problem lies in a
large part of the motivations and objectives of this study, which proposes to
design a non-parametric algorithm for causal discovery, which allows detecting
cause-effect relationships between the variables associated with a set of data
from a different approach than the usual ones, focusing mainly on sufficient
causal relationships. As a secondary motivation, we want to apply this
algorithm to discover causal relationships between genetic alterations
associated with carcinogenesis. The final objective is to discover genes whose
alteration serves as an indication of the presence of cancer (ie, indicator
genes), and genes whose alteration plays a fundamental role in the regulatory
mechanisms that at the genetic level promote the origin and proliferation of
said disease. (ie, target genes). The detection of genes with these
characteristics is of high importance for the diagnosis and treatment of
cancer. In particular, the target genes could be used in alternative therapies
to conventional chemotherapy, since the suppression or replacement of their
genetic expressions in cancerous tissue could contribute to the regulation of
the disease, and its possible cure.

Therefore, the general objective of this work can be summarized:

  * •

Proposal of a causal discovery methodology to detect causal relationships
between variables referring to a set of data, and its application for the
discovery of cause-effect relationships between genetic alterations that cause
and regulate carcinogenesis.

Therefore, its field of action mainly covers causality, probabilities, graph
theory and genomics. Its specific objectives are:

  * •

Analyze the main characteristics of causal relationships, and some of the
theories that define and study them.

  * •

Study current methods of causal discovery, paying special attention to the
modeling of causal relationships using graphs.

  * •

Analysis of the behavior of causal relationships in cases of causal
sufficiency.

  * •

Design a causal discovery algorithm that:

$\bullet$ is non-parametric,

$\bullet$ describes sufficient causal relationships,

$\bullet$ does not employ statistical tests of conditional independence,

$\bullet$ minimize the number of spurious, redundant, and unknown-direction
causal relationships represented in the resulting model.

  * •

Apply this algorithm in the construction of genetic regulation networks
associated with carcinogenesis, in order to identify cancer indicator genes
and possible target genes for therapy.

  * •

Develop software that implements the algorithm and functionalities related to
causal graph analysis, efficiently and accessible to users, with particular
attention to those within the field of bioinformatics.

The chapters of this document are organized as follows:

  * •

Chapter 1: The different theories that define and study causal relationships
are analyzed. An approach is made to current methods of causal discovery,
paying particular attention to the modeling of causal relationships in sets of
variables through graphs.

  * •

Chapter 2: A brief analysis of the main characteristics of causal relations,
particularly sufficient causal relations, is carried out.

Chapter 5: The conclusions of the research are presented. A methodology and
algorithm is proposed for the discovery of sufficient causal relationships in
a set of variables associated with a population of individuals.

  * •

Chapter 3: An implementation of the proposed algorithm is described, and the
main characteristics of the program that includes it.

  * •

Chapter 4: The results obtained after applying the proposed algorithm on a
data set of genetic alterations associated with cancer, particularly prostate
cancer, are analyzed.

  * •

Chapter 5: The conclusions of the research are presented.

##  Chapter 1 State of the art

Below is an analysis of the main theories that study causality and its
properties. These theories are various and complex, with extensive precedent
in various fields such as Physics and Philosophy. The study is reduced to a
subset of them, which will serve as the basis for the methodology to be
developed in the following chapters.

###  1.1 Regularity theory

The theory of causal regularity is based on the observation that causes are
regularly followed by their effects. This theory has a reductionist approach,
and does not propose causal powers by virtue of which causes produce their
effects. The Scottish empiricist philosopher David Hume (1711-1776) is the
father of this conception of causality. According to this author, cause and
effectHume

“(…) are [objects] contiguous in time and place and that the named object
causes precedes the other, which we call effect.”

From his perspective, cause and effect appear in a kind of constant
conjunction but there is no necessary connection between them. In fact, his
theory attributes to the mind the idea that, by necessity, a cause is followed
by its effect:Hume

“(…) after frequent repetition I see that when one of the objects appears the
mind is determined by habit to attend to its usual companion, and to consider
it (…), by virtue of its relationship with the first object. It is then this
impression or determination that gives me the idea of necessity.”

For Hume, the impression of a necessary connection emerges as a result of the
inferential habits developed on the basis of experience of regularities.
However, later approaches to regularity theory conceive of causality as an
objective process, independent of an observer’s experience.

In summary, Hume’s regularity theory states that, let $c$ and $e$ be two
instances of events of types $C$ y $E$, respectively, $c$ is a cause of $e$ if
and only ifReg:

  * •

$c$ is spatially and temporally contiguous to $e$,

  * •

$c$ precedes $e$ in time, and

  * •

all type $C$ events are followed by an event of type $E$.

The first condition excludes causal relations at a distance (except, perhaps,
through a causal chain of events), the second establishes that the cause-
effect succession is oriented in the same direction of time, and the third
indicates the manifestation of cause and effect in constant conjunctionReg.

This theory has some advantages. On the one hand, it does not require an
objective but inaccessible explanation that can support the idea of a
necessary connection between cause and effect; on the other, it reduces
causality to three verifiable conditions (spatiotemporal contiguity, temporal
precedence, and regular association). In this way, Hume’s theory allows causal
relationships to be inferred in a relatively simple way. Since temporal
precedence and spatiotemporal contiguity are generally observable, identifying
causal relationships is reduced to the mere detection of regularitiesReg.

However, this approach to causality presents two fundamental problems:

  * •

It does not contemplate singular causal relationships.

  * •

Introduces spurious causal relationships.

By singular causal relationships, we understand any causal relationship that
takes place only once. For example, the death of Archduke Franz Ferdinand
(1863 - 1914), heir to the Austro-Hungarian crown, is recognized as the cause
of the First World War (although not the only one)War. These events happened
only once in History and are, in fact, unrepeatable (like any other historical
event). However, many agree that there is a cause-effect relationship between
the two, contradicting the notion of causality as an inferential habit when
identifying a regularity.

On the other hand, an example of a spurious causal relationship is the
association of the light on while sleeping as a cause of myopia in young
children. In 1999, a team from the University of Pennsylvania (USA) published
a study in Naturewhich concluded that babies who sleep with the light on were
at greater risk of developing myopia, indicating a possible cause-effect
relationship between these events. However, a subsequent study from Ohio State
University refuted these claims, finding no such causal relationship between
the two and, instead, revealing a tendency in myopic parents to leave the
lights on in their children’s rooms, as well as a hereditary factor in this
diseaseMyopia. In this case, a regularity occurs, and yet there is no causal
relationship between infants’ myopia and the light on when sleeping. In fact,
the correlation between both events is due to a common cause: paternal myopia.

The existence of non-causal regularities shows that the definition of
causality proposed by Hume is, to say the least, incomplete. Addressing this
problem, Mill (1806 – 1873) refined Hume’s theory of causality. Mill extends
the concept of cause to a conjunction of positive and negative factors, where
the presence of the positive and the absence of the negative produces the
appearance of the effect. On the other hand, he states that mere regularity is
not sufficient to determine causality. The regularities of causality require
support from some law of natureReg. By law of nature, Mill understands a set
of more general regularitiesMill:

“[The term] Laws of Nature means nothing more than the uniformities that exist
among natural phenomena (or, in other words, the result of induction) when
they are reduced to their simplest expression.”

Note that in his definition of laws of nature there is an implicit human
factor. Appreciates regularities as natural processes, but their status as law
depends on subjective criteria of generality and simplicity.

Mackie (1917 – 1981) is one of the heirs of the regularist tradition in the
20th century. According to its formulation, each of the groups of factors of a
cause is a conjunction of positive terms (eg, the presence of events) and
negative terms (eg, the absence of events). Then, the disjunction of all these
conjunctions re-presents the totality of causes of an event. For example, a
lit match, the presence of dry leaves and the absence of rain can be the
causes of a forest fire, as can the breakdown of a power line and a delay in
the deployment of preventive actions, or an accident. automobile and the
presence of a fuel shipment in one of the vehicles involved, etc. Mackie
proposes that each of the factors of a conjunction is a cause, butMackie

“[t]he so-called cause is, and is known to be, an insufficient but necessary
part of a condition which is itself unnecessary but sufficient for the result.
In view of the importance of conditions of this kind in our knowledge and ways
of talking about causality, it will be convenient to have a short name for
them: INUS conditions.”

Mackie proposes that a cause $C$ is always an INUS (Insufficient-Necessary-
Unnecessary-Sufficient) condition of the associated effect $E$, admitting the
exceptions where $C$ is by itself a sufficient cause, a necessary cause, or
both. Therefore, from their perspective, a cause can have essentially four
forms. Let $C_{i,j}$ be a causal event on an effect $E$, and ’/$\rightarrow$’
be the symbol of the causal relationship:

  * •

si $C_{1,1}\rightarrow E$, then $C_{1,1}$ is a unique, necessary and
sufficient cause;

  * •

si $(C_{1,1}\wedge C_{1,2}\wedge...C_{1,n})\rightarrow E$, then $C_{1,1}$ is a
necessary cause, but not sufficient;

  * •

si $C_{1,1}\vee(C_{2,1}\wedge C_{2,2}\wedge...C_{2,m})\vee...(C_{k,1}\wedge
C_{k,2}\wedge...C_{k,l})\rightarrow E$, then $C_{1,1}$ is cause sufficient,
but not necessary;

  * •

si $(C_{1,1}\wedge C_{1,2}\wedge...C_{1,n})\vee(C_{2,1}\wedge
C_{2,2}\wedge...C_{2,m})\vee...(C_{k,1}\wedge
C_{k,2}\wedge...C_{k,l})\rightarrow E$, then $C_{1,1}$ is an INUS condition.

Mackie’s theory, although it presents great facilities for causal inference,
and denotes causes more explicitly and concisely than its predecessor Mill, is
incapable of distinguishing spurious causal relationships. On the other hand,
he raised doubts about an apparent symmetry of complex regularities from his
approach, which contradicts the asymmetry inherent to causal relationships in
generalReg.

Baumgartner subsequently denies claims about such symmetry. From his point of
view, Mackie’s complex regularities remain asymmetric, in the sense that the
instantiation of any conjunction $(C_{i,1}\wedge...C_{i,n})$ of causes
determines the effect $E$, as instantiating $E$ it does not allow us to
determine more than the total disjunction of all these conjunctions.
Baumgartner defends what is known as the asymmetry of overdetermination, in
which any of the sufficient causes of an effect determine it, but the effect
cannot determine any of its sufficient causes separately. This author states
that the main deficiency in Mackie’s theory lies in not strictly minimizing
material regularities, and states thatBaumgartner

“[t]he most important condition that regularities must satisfy to be causally
interpretable is what can be called a principle of non-redundancy. The causal
structures do not present redundancies. Each cause contained in a causal
structure […] makes a difference in at least one effect of the structure, in
at least one situation.”

According to Baumgartner, to characterize the causal structure of a complex
regularity, a minimally necessary disjunction of minimally sufficient
conjunctions is required.

Sometimes, theories of causal regularity have become inferential theories of
causality. Inferential theories propose that a causal relationship can be
taken as refinements and generalizations of regularity theory. For example, an
INUS condition can be explained in terms of logical inferences, interpreting
the causal relation ’$\rightarrow$’ as a biconditional ’$\iff$’Reg:

$(C_{1,1}\wedge C_{1,2}\wedge...C_{1,n})\vee(C_{2,1}\wedge
C_{2,2}\wedge...C_{2,m})\vee...(C_{k,1}\wedge C_{k,2}\wedge...C_{k,l})\iff E$
.

###  1.2 Probabilistic causality theory

The theory of causal regularity generally presents a deterministic
perspective, assuming that causes occur together with their effects in
invariable succession. However, a cause-effect relationship may exist between
two events without necessarily always appearing together. For example,
Covid-19 causes loss of smell, difficulty breathing, lung damage, among
others, but there are many cases of asymptomatic patients. This imperfection
in the infection-symptoms regularity can be explained within the framework of
the theory of causal regularity, ie, the infection could be an INUS condition
of the symptoms, and the apparent imperfection would then arise from not
considering the rest of the causes (positive and negative) that must be
presented in conjunction with this (genetic factors, immune response and
comorbidities of the infected person, etc.). Although this deterministic
approach can be useful in some contexts, usually the number of causal factors
of an event it’s huge. Hence the need to limit the analysis to a few relevant
factors, inevitably losing part of the causal information. All phenomenology
described only by these relevant factors behaves stochastically. This
motivates the proposal of a theory that evaluates causality through
probabilities.

The probabilistic theory of causality is based on the premise that causes
increase the probability of their effects. Let $C$ be the cause and $E$ be the
effect, then it is required that:

$P(E\mid C)>P(E)\leavevmode\nobreak\ ,$ (1.1)

that is, the probability of the effect is greater given the cause. In another
formulation is

$P(E\mid C)>P(E\mid\neg C)\leavevmode\nobreak\ ,$ (1.2)

so the increase in the probability of the effect given the cause is measured
with regarding the condition in which the cause is absent. It can be shown
that the two inequalities (1.1)-(1.2) are equivalentCartwright.

This basic definition has certain advantages. First, one event can increase
the probability of another, and therefore be its cause, without the need for a
constant conjunction (see previous section). Therefore, it admits
imperfections in regularities (or irregularities) naturally. On the other
hand, if $C$ is the cause of $E$ then $C$ is in some way relevant to $E$ (its
probability increases), condition not necessarily present in the regularities
in general. However, the probabilistic theory based only on (1.1)-(1.2) does
not solve the problem of spurious causal relationships: it can be true that
$P(E\mid C)>P(E\mid\neg C)$, even when $C$ does not cause $E$; for example, if
both are effects of a common cause. Nor does it reflect the asymmetry of
causality, since $P(E\mid C)>P(E\mid\neg C)$ if and only if $P(C\mid
E)>P(C\mid\neg E)$. Therefore, conditions (1.1)-(1.2) are not sufficient to
determine whether $C$ is a cause $E$ o vice versa.Prob

Reichenbach (1891 – 1953), father of the theory of probabilistic causality,
addresses the problem of spurious relationships based on a condition that he
called screening off. $A$ is said to screen $C$ from $E$ when

$P(E\mid A\wedge C)=P(E\mid A)\leavevmode\nobreak\ ,$ (1.3)

which is equivalent to $P(C\wedge E\mid A)=P(C\mid A)P(E\mid A)$ if $P(C\wedge
E)>0$. That is, conditioning in $A$ breaks the correlation between events $C$
and $E$.Reichenbach. A screening off can happen in two ways:

  * •

$C$ causes $A$, $A$ causes $E$, and there is no other path other than $A$ by
which the event $C$ can affect event $E$. In this case, the causal
relationship from $C$ to $E$ is considered indirect o remote, through the
mediator $A$, as opposed to the direct or near causality that is established
between cause and effect when there are no other intervening events.

For example, exposure to SARS-CoV-2 carriers can cause contagion through
contact with infected secretions. However, among the people who have contact
with infected secretions, exposure or not to SARS-CoV-2 carriers does not
influence the probability of infection. In addition, if the healthy person
were protected by an effective mask, thus preventing own mucous membranes come
into contact with foreign secretions, the probability contagion does not
depend on direct exposure to SARS-CoV-2 carriers.

  * •

$A$ is the common cause of events $C$ y $E$, and between $C$ and $E$ there is
no other causal connection.

For example, there is a correlation between the light on when sleeping and the
onset of myopia in young children. However, since the cause of both events is
usually paternal myopia, among children whose parents suffer from myopia,
those who sleep with the light on are no more likely to develop this disease
than those who sleep in the dark.

Reichenbach considers that $C$ ss relevant cause of a subsequent event $E$ if:

  * •

$P(E\mid C)>P(E)$, and

  * •

there is no set of events prior to or simultaneous with $C$ that screen $C$
from $E$.

The second condition excludes the possibility that there is a common cause
that explains the correlation between $C$ and $E$, dictated by the first
condition. Note that the second condition refers to events prior to or
simultaneous with $C$. Therefore, the shielding mentioned cannot be caused by
an intermediary cause. In the latter case, $C$ would be an indirect (but not
irrelevant) cause of $E$.

Additionally, Reichenbach arrives at a series of conditions, known
collectively as the “principle of common cause”, which are verified in the
event that the correlations between events are not due to a causal
relationship between them. According to this principle, if $E_{1}$ and $E_{2}$
are positively correlated (ie, $P(E_{1}\wedge E_{2})>P(E_{1})P(E_{2})$) but do
not form a cause and effect pair, then they are effects of a common cause $C$
and are meet the following conditions:Reichenbach

  1. 1.

$0<P(C)<1$

  2. 2.

$P(E_{1}\wedge E_{2}\mid C)=P(E_{1}\mid C)P(E_{2}\mid C)$

  3. 3.

$P(E_{1}\wedge E_{2}\mid\neg C)=P(E_{1}\mid\neg C)P(E_{2}\mid\neg C)$

  4. 4.

$P(E_{1}\mid C)>P(E_{1}\mid\neg C)$

  5. 5.

$P(E_{2}\mid C)>P(E_{2}\mid\neg C)$

Inequalities (4)-(5) are satisfied by virtue of the fact that $C$ is the
common cause of $E_{1}$ and $E_{2}$. Now, in (2)-(3) it is stated that $C$ and
$\neg C$ screen the relationship between $E_{1}$ and $E_{2}$, so that $C$ is
responsible for the correlation between $E_{1}$ and $E_{2}$.

The definition of cause proposed by Reichenbach, in conjunction with this
principle, solves the problems of spurious causal relationships, while making
use of the order temporal to explain the asymmetry of cause and effect.
However, it is not a sufficient condition of causality. Consider, for example,
the causal relationship between contraceptive pills and thrombosis. Birth
control pills can cause thrombosis episodes. However, these drugs prevent
pregnancy, which constitutes an even greater risk of thrombosis.Hausman This
is a controversial example and must not be taken as an empirically
demonstrated reality. However, and since is illustrative, in this context it
is assumed to be true. Let $C$ be the ingestion of birth control pills, $E$ be
the increase in blood pressure and $A$ be pregnancy, then it can be given that
$P(E\mid C)<P(E\mid\neg C)$ (and therefore, that $P(E\mid C)<P(E)$). This
means that that the ingestion of birth control pills can indirectly prevent
the increase in blood pressure, by directly preventing pregnancy.

With inequality (1.1) reversed, $C$ could not be considered a relevant cause
of $E$ according to the definition of Reichenbach, but $C$ is the cause of $E$
(and is not irrelevant). Note that if it is conditioned on $A$ or $\neg A$,
then it is possible to obtain the correct inequalities, ie, $P(E\mid C\wedge
A)>P(E\mid\neg C\wedge A)$ y $P(E\mid C\wedge\neg A)>P(E\mid\neg C\wedge\neg
A)$, in each case. Indeed, contraceptive pills raise the blood pressure of
both pregnant and non-pregnant women. This problem is known as the Simpson’s
paradox.Cartwright

In this scenario, Cartwright proposes a new definition of cause, based on
conditioning on background contexts. A background context is nothing more than
a conjunction of factors (events). This author proposes that $C$ causes $E$ if
and only if:

$P(E\mid C\wedge B)>P(E\mid\neg C\wedge B)$ (1.4)

for every background context $B$, such that $B$ is formed by different causes
of $E$ of $C$ and the effects of $C$.Cartwright Skyrms, on the other hand,
proposes a weaker condition, $C$ causes $E$ if and only if a background
context $D$ exists, such that:

$P(E\mid C\wedge D)>P(E\mid\neg C\wedge D)$ (1.5)

and for any background context $B$ it holds $P(E\mid C\wedge B)\geq
P(E\mid\neg C\wedge B)$.Skyrms. On the other hand, Dupré suggests an
intermediate condition. It proposes that $C$ should be considered a cause of
$E$ if the probability of E increases in a representative sample of the target
population, ie,

$\sum_{B}P(E\mid C\wedge B)P(B)>\sum_{B}P(E\mid\neg C\wedge
B)P(B)\leavevmode\nobreak\ .$ (1.6)

###  1.3 Theories of manipulability

Manipulability theories are based on the idea that manipulating causes must be
a way of manipulating effects. The first approaches to this theory gave a
relatively central role to man, and were reductionist in nature.

One of the prominent theories in this framework was the theory of Menzies and
Price, which attempts to reduce causality using free action as a primitive
notion. The definition of free action is not entirely clear, but it seems to
refer to an action without a cause or a deterministic cause, or to an action
that comes from the voluntary choices of an agent.Mani On this basis, these
authors take an event $C$ to be the cause of another event $E$ if a free agent
can cause the occurrence of $E$ by guaranteeing the occurrence of $C$.Menzies
The objective of this link between causality and free agency is to support
probabilistic analysis by replacing traditional conditional probabilities with
probabilities conditioned on a free action that guarantees the occurrence of
an event: $C$ is considered the cause of $E$ if the probability of $E$ is
greater given that $C$ is obtained through a free act.Mani This notion of
agent has a fundamentally human focus, and is based on the basic premise that
everyone has an experience of acting as agents, from an early period of
lifeMenzies. So the analysis of causality in terms of agency preserves the
reductionist ideal, and does not suffer from circularities. However, this
makes the interpretation of causality difficult or impossible in those
scenarios where human action is not conceivable. Menzies and Price try to
solve this problem by alluding to the similarity between these non-manipulable
processes and others that can be manipulated, such as event simulations, as
long as the latter capture the essential characteristics of the former. The
problem with this definition is that it is implicitly causal, and therefore
not reductive at all.Mani In general, analyzes of causality through free
action fail in contexts where agents are not operative. Furthermore, they are
incapable of solving the problem of spurious relationships: the free action
that triggers an event $C$ could be correlated with, or properly be, a common
cause of $C$ and $E$, causing a false notion of a cause-effect relationship
between $C$ and $E$.

Before entering into Judea Pearl’s interventionist theoryPearl, it is worth
adding a short digression. There is still unresolved controversy about what
causality relates; In other words, what type of entities belong to what we
call cause and effect. Different authors refer to events (eg, LewisLewis),
facts (eg, MellorMellor), conditions (eg, MackieMackie), etc. Until now, it
has been useful and intuitive to discuss regularist, probabilistic and
manipulation theories in terms of events without, necessarily, their
respective authors having shared this choice. Within the framework of Pearl’s
theory, however, causality relates variables. Either way, when variables are
binary, their values can identify the occurrence or not of a certain event.

Pearl brings a new approach to the theory of manipulability, starting from the
concept of intervention. According to this author, an intervention is an
atomic alteration to a variable $X_{i}$, which does not directly affect any
other variable in the system. The objective of these interventions is,
therefore, to measure the effect that a variable $X_{i}$ has on the rest: any
change in another variable cannot be an effect of the intervention and will,
therefore, be a product of the change in the value of $X_{i}$, revealing a
relationship causal. This approach, unlike its predecessors in manipulability
theory, is not reductive, as it accepts intervention as a causal notion.Mani

Pearl models the causal relationships between a set of variables as a directed
graph and an associated system of equations. Each equation of the system
represents an autonomous causal mechanism, and has the form
$X_{i}=F_{i}(Pa_{i},U_{i})$, where $Pa_{i}$ are the direct causes of $X_{i}$
(parents of $X_{i}$ in the graph) that are explicitly represented as variables
of the set, and $U_{i}$ is an error (or noise) variable that measures the
influence that all the variables not considered have on $X_{i}$.Pearl The
autonomy of each individual mechanism is weighed against the possibility of
disturbing it (and therefore the associated equation) without affecting the
rest.Mani Then:Pearl

“The simplest type of external intervention is one in which a single variable,
say $X_{i}$, is forced to assume some fixed value $x_{i}$. Such an
intervention, which we call “atomic”, amounts to removing $X_{i}$ from the
influence of the old functional mechanism $X_{i}=F_{i}(Pa_{i},U_{i})$ and
placing it under the influence of a new mechanism that sets the value $x_{i}$
while keeping all other mechanisms unchanged. Formally, this atomic
intervention, which we denote by $do(X_{i}=x_{i})$, or $do(x_{i})$ for short,
amounts to removing the equation $X_{i}=F_{i}(Pa_{i},U_{i})$ from the model
and substituting $X_{i}=x_{i}$ into the remaining equations. The new model
thus created represents the behavior of the system under the intervention
$do(X_{i}=x_{i})$ and, when solved for the distribution of $X_{j}$, yields the
causal effect of $X_{i}$ on $X_{j}$.”

Therefore, it assumes that any variable other than $X_{i}$, whose value is
affected by this intervention, is an effect of $X_{i}$.Mani

Pearl defines the causal effect of $X_{i}$ on another variable $X_{j}$ by the
function $P(X_{j}|hatX_{i})=P(X_{j}|do(X_{i}=x_{i}))$, for possible values
$x_{i}$ of $X_{i}$.Pearl Note that $P(X_{j}|do(X_{i}=x_{i}))\neq
P(X_{j}|X_{i}=x_{i})$, i.e., conditioning on the information that $X_{i}$ was
observed to take the value $x_{i}$ is not the same as conditioning on the
information that $X_{i}$ was manipulated to take the value $x_{i}$ (something
Menzies and Price had already noticed). For example, if between $X_{i}$ and
$X_{j}$ there is no causal relationship, but they are correlated by a common
cause $X_{k}$, then $X_{i}$ and $X_{j}$ are probabilistically dependent and
$P(X_{j}|X_{i}=x_{i})\neq P(X_{j})$. Instead,
$P(X_{j}|do(X_{i}=x_{i}))=P(X_{j})$, since by establishing the value of
$X_{i}$ through an intervention all relation of $X_{i}$ with its causes is
broken, in particular its relation with $X_{k}$ and, therefore, with $X_{j}$
is broken ($X_{i}$ and $X_{j}$ are independent after the intervention).Mani

A difficulty with this definition of causal effect is precisely that
intervening to change the value of a variable $X_{i}$ keeps the rest of the
equations unchanged. In particular, all causes of $X_{j}$ other than $X_{i}$
and effects of $X_{i}$ remain unchanged. Therefore, when considering the
causal effect of $X_{i}$ on $X_{j}$ one does not only evaluate the effect that
$do(X_{i}=x_{i})$ has on $X_{j}$, but the contribution between it and the rest
of these causes.Ê Prompted by this problem, among others, Woodward and
Hitchcock decide to take a different approach to the intervention proposed by
Pearl. From their perspective, an intervention of one variable $X_{i}$ must be
defined with respect to another variable, with the further idea of
characterizing the causal effect of one variable $X_{i}$ on another $X_{j}$ by
intervening $X_{i}$ with respect to $X_{j}$.Mani

###  1.4 Graphs

In the previous section it was mentioned the use of graphs for the
representation of causal relationships. Although the concept of graph is
common and recurrent in several fields, an approach to the main definitions
surrounding this structure is convenient.

A graph $G$ is a pair of sets $<V,E>$, where the elements of $V$ are called
vertices (or nodes), and the elements of $E$ are pairs $<v,w>$ of different
elements of $V$, which are called edges (or links). Two vertices are said to
be adjacent if they are connected by an edge. An edge $<v,w>$ can be directed
(in this case it is called an arrow and is denoted by $v\rightarrow w$), or
bidirectional (also called an undirected edge, or just an edge, and denoted by
$v\leftrightarrow w$). An arc has an implicit notion of direction, so that the
arc $v\rightarrow w$ is not equal to the arc $w\rightarrow v$. On the other
hand, the edge $v\leftrightarrow w$ is identical to the edge $w\leftrightarrow
v$.

A graph containing arcs and edges is called a mixed graph. A path in a mixed
graph is a set $P=\\{v_{1},v_{2},...v_{n}\\}$ of distinct vertices such that
$\forall i,0<i<n$ exists the arc $v_{i}\rightarrow v_{i+1}$, the
$v_{i}\leftarrow v_{i+1}$, or the edge $v_{i}\leftrightarrow v_{i+1}$. If the
path $P$ satisfies that $foralli,0<i<n$ exists on the arc $v_{i}\rightarrow
v_{i+1}$, then $P$ is said to be a directed path. A directed path is called a
cycle if the arc $v_{n}\rightarrow v_{1}$ also exists.

If a mixed graph contains only arcs then it is a directed graph, while a mixed
graph containing only bidirectional edges is an undirected graph. Of
particular interest among directed graphs are directed and acyclic graphs
($DAG$).

Finally, a genealogical relationship is usually established between the
vertices of a directed graph. A vertex $v$ is said to be the parent of another
$w$ if and only if the arc $v\rightarrow w$ exists. In these cases $w$ is also
said to be a child of $v$. A vertex without a parent is said to be an orphan.
From this definition, we establish the ancestor-descendant relation for any
pair of vertices $(i,j)\in V\times V$, so that:

  * •

$i$ is an ancestor of $j$ if $i$ is the father of $j$.

  * •

$i$ is an ancestor of $j$ if $i$ is an ancestor of $j$’s father.

  * •

$j$ is a descendant of $i$ if $i$ is an ancestor of $j$.

###  1.5 Bayesian networks

Given a set $V=\\{v_{1},v_{2},...v_{n}\\}$ of variables, and a probability
function $P$, a Bayesian network $G$ over $V$ consists of a $DAG$ that
satisfies:

$P(v_{1},v_{2},...v_{n})=\prod_{v_{i}\in V}P(v_{i}|Pa_{i})$ (1.7)

where $Pa_{i}$ is the set of variables corresponding to the parents of $v_{i}$
in $G$.

This condition is called factorization of Bayesian networks, and in $DAGs$ it
is equivalent to the local Markov condition. A graph meets the local Markov
condition if every vertex $v_{i}$ of the graph, conditioned on all its
parents, is independent of the rest of the non-descendant vertices of $v_{i}$.

The condition of minimality is also usually required for A Bayesian network
$G$ satisfies the condition of minimality if:Prob

  * •

$G$ satisfies the local Markov condition.

  * •

No subgraph of $G$, resulting from eliminating arcs of $G$, satisfies the
Markov condition.

Under the Markov condition on a graph G, certain structures within the graph
acquire importance. Especially:

  * •

A chain is a trio of vertices $\\{v_{1},v_{2},v_{3}\\}$ such that the arcs
$v_{1}\rightarrow v_{2}$ and $v_{2}\rightarrow v_{3}$ exist.

  * •

A bifurcation or fork is a trio of vertices $\\{v_{1},v_{2},v_{3}\\}$ such
that the arcs $v_{1}\leftarrow v_{2}$ and $v_{2}\rightarrow v_{3}$ exist.

  * •

A immorality is a trio $\\{v_{1},v_{2},v_{3}\\}$ such that the arcs
$v_{1}\rightarrow v_{2}$, $v_{2}\leftarrow v_{3}$ exist, and furthermore the
arcs $v_{1}\rightarrow v_{3}$, $v_{1}\leftarrow v_{3}$ do not exist. Within
the immorality, the vertex $v_{2}$ is referred to as the collider.

Part of the importance of these structures lies in the relationships of
conditional independence that they fulfill:Neal

  * •

Both a chain and a fork $\\{v_{1},v_{2},v_{3}\\}$ satisfy that
$P(v_{1},v_{3}|v_{2})=P(v_{1}|v_{2})P(v_{3}|v_{2})$, that is, $v_{1}$ and
$v_{3}$ are independent given $v_{2}$.

  * •

An immorality fulfills that:

$\bullet$ $P(v_{1},v_{3})=P(v_{1})P(v_{3})$, that is, $v_{1}$ y $v_{3}$ are
statistically independent.

$\bullet$ $P(v_{1},v_{3}|v_{2})\neq P(v_{1}|v_{2})P(v_{3}|v_{2})$, that is,
$v_{1}$ y $v_{3}$ are dependents given $v_{2}$.

$\bullet$ Let $v_{4}$ be any descendant of $v_{2}$, then
$P(v_{1},v_{3}|v_{4})\neq P(v_{1}|v_{4})P(v_{3}|v_{4})$.

###  1.6 Causal graphs

Given a set $V=\\{v_{1},v_{2},...v_{n}\\}$ of variables, a causal graph over
$V$ is a graph where each vertex represents a variable $v_{i}$ of the set. An
edge in a causal graph can be either an arc or a bidirectional edge. An arc
$v\rightarrow w$ represents the causal relationship where $v$ is the cause and
$w$ the effect, while an edge $v\leftrightarrow w$ denotes the existence of
causes common to $v$ and $w$ not observed in $V$ (sometimes called confounding
factors).Pearl Therefore, if $v$ is the parent of $w$ then $v$ is the cause of
$w$.

Usually, the cause-effect relationships represented by arcs in a causal graph
are direct causal relationships, that is, (as defined above in terms of
events), those causal relationships between two variables where there are no
other intermediate variables. In these cases, a directed path represents a
chain of direct causal relationships between the variables that compose it.
Therefore, between any two non-consecutive vertices $v$, $w$ of a directed
path, the subpath from $v$ to $w$ represents an indirect causal relationship
from $v$ to $w$

###  1.7 PC algorithm for causal discovery

A causal discovery algorithm is one that, given a set $V$ of variables,
detects the causal relationships between its elements and represents them
consistently, usually, through a causal graph. As sections 1.1, 1.2 and 1.3
suggest, the identification of these relationships involves several
difficulties. One of the most popular approaches within causal discovery is
based on statistical independence as a primitive notion, given that the latter
guarantees causal independence if no other relevant factors exist. In the most
general case, conditional independence is used as a sufficient condition for
the absence of a direct causal relationship, which are the relationships that
are usually represented in causal graphs.

Given a graph $G$, associated with a set V of variables and a probability
function $P$, Pearl uses the concept of d-separation to identify relationships
of conditional independence:Pearl

“A path $p$ is said to be d-separated (or blocked) by a set of nodes $Z$ if
and only if:

  1. 1.

$p$ contains a chain or a fork such that the middle node $m$ is in $Z$, or

  2. 2.

$p$ contains an inverted branch (or collider) such that the middle node $m$ is
not in $Z$ and such that no descendant of $m$ is in $Z$.

A set $Z$ is said to separate [a set] $X$ from [another set] $Y$ if and only
if $Z$ blocks all paths from a node in $X$ to a node in $Y$.”

This concept makes sense on the fulfillment of the local Markov condition in
the graph $G$, and has the objective of exploiting the properties of the
chains, bifurcations, and immoralities described above. Pearl states that, for
a $DAG$ that meets this condition (Bayesian network)Pearl

“If the sets $X$ and $Y$ are d-separated by $Z$ in a $DAG$ $G$, then $X$ is
independent of $Y$ conditional on $Z$ in every $G$-compatible distribution.
Conversely, if $X$ and $Y$ are not d-separable by $Z$ in a $DAG$ $G$, then $X$
and $Y$ are conditionally dependent on $Z$ in at least one $G$-compatible
distribution.”

This condition is known as the global Markov condition, and implies that,
given the structure of $G$, it is possible to discover the conditional
independence relations between the variables of $V$. However, what is desired
is an opposite condition, which allows the structure of the graph $G$ to be
discovered from these relations of conditional independence. This condition is
called the fidelity condition and dictates that these independence relations
are also necessary for the global Markov condition. On this basis, Spirtes,
Glymour, and Scheines build the $SGS$ algorithm for causal discovery. Starting
from a set $V$ of variables, the $SGS$ algorithm constructs the causal graph
$G$ of $V$ assuming:

  * •

The set of variables $V$ presents causal sufficiency (there are no confounding
factors).

  * •

The graph $G$ that describes the causal relationships of $V$ is acyclic.

  * •

$G$ satisfies the Markov conditions.

  * •

The probability distribution of $P$ in the set $V$ is such that the fidelity
condition is satisfied.

The algorithm can be summarized in the following steps:Spirtes

  * •

A graph $H$ is constructed on the set $V$ of variables, such that $H$ is an
undirected graph and contains all possible edges between vertices of $V$.

  * •

For each pair of vertices $v$ and $w$, if there exists a subset $S$ of
$V\setminus\\{v,w\\}$ such that $v$ and $w$ are d-separated given $S$, then
the edge between $v$ and $w$ is removed from $H$.

  * •

Let $K$ be the undirected graph resulting from the previous step. For every
trio of vertices $v$, $w$, $x$ such that the pair $v$, $w$ and the pair $w$,
$x$ are each adjacent in $K$ (i.e., $v\leftrightarrow w\leftrightarrow x$),
but the pair $v$ and $x$ are not adjacent in $K$, one orients
$v\leftrightarrow w\leftrightarrow x$ as $v\rightarrow w\leftarrow x$ if and
only if $w$ does not belong to any $S$-subset of $V$ that d-separates $v$ and
$x$.

  * •

Finally, it is repeated:

$\bullet$ for each trio of vertices $v$, $w$, $x$, if $v\rightarrow w$, $w$
and $x$ are adjacent via an undirected edge, and $v$ and $x$ are not adjacent,
then $w\leftrightarrow x$ is oriented as $w\rightarrow x$;

$\bullet$ for each trio of vertices $v$, $w$, if there is a direct path from
$v$ to $w$, and an undirected edge between $v$ and $w$, then $v\leftrightarrow
w$ is oriented as $v\rightarrow w$;

until no more edges can be oriented.

Note that the second step of the algorithm is justified in that, if by
conditioning on a set $S$ the dependency between two variables $v$ and $w$ is
broken , then between $v$ and $w$ there is no direct causal relationship and
the edge that unites them can be eliminated.

On the other hand, the third step is based on two essential ideas:Neal

  * •

There exists at least one set $S$ such that $v$ and $x$ are d-separable given
$S$.

This statement is true, since at the beginning $G$ contains all possible
edges, and the edge $v\leftrightarrow w$ is no longer in $G$, then the edge
was eliminated by conditioning on some set of variables.

  * •

$w$ does not belong to any set that d-separates $v$ and $x$.

From which it follows that, although $v$ and $x$ are d-separable when
conditioning on some set, as long as $w$ belongs to the set being conditioned,
said d-separation will not be achieved. Then $w$ is necessarily a collider,
and the subgraph underlying $v\leftrightarrow w\leftrightarrow x$ is
$v\rightarrow w\leftarrow x$.

This algorithm, although it has a high reliability in terms of causal
discovery, presents a high time complexity. The second step requires
conditioning, for each pair of vertices connected by an edge, on all possible
subsets of remaining variables, thus becoming an exponential time complexity
algorithm. In addition:Spirtes

“In the worst case such complexity is unavoidable if reliability is to be
maintained. Two variables may be dependent conditioning on a set $U$ but
independent conditioning on a superset or subset of $U$. Any worst-case
procedure that does not examine the conditional independence relationships of
variables $X$, $Y$ on all subsets of vertices that do not contain that pair
will fail.”

Spirtes, Glymour and Scheines then redesigned the $SGS$ algorithm and the $PC$
algorithm emerged, which essentially replaces the second and third steps of
the $SGS$ algorithm with two equivalent, but computationally less expensive,
procedures.

##  Chapter 2 Proposal

In this chapter, a non-parametric method is proposed for the discovery of
causal relationships between binary variables. The approach used is related to
that of the probabilistic theory of causality, although it is based on
different assumptions.

Next, some basic notions of causal relationships are introduced, which will be
used in the rest of the chapter

###  2.1 Causal relationships

Causality is conceived as a binary relationship between variables (cause and
effect) and whose main characteristics are:Hausman

  * •

Irreflexivity: For every variable $i$ it is true that $i$ is not the cause of
itself.

  * •

Asymmetry: For every pair of variables $i$ and $j$ it is true that if $i$ is
the cause of $j$ then $j$ is not the cause of $i$.

  * •

Transitivity: For every trio of variables $i$, $j$ and $k$ such that $k$ is
the cause of $j$ and $j$ is the cause of $k$, it is true that $i$ is the cause
of $k$.

A causal chain is defined as a finite sequence of variables
$\\{i_{1},i_{2},...i_{n}\\},n\geq 2$ such that $\forall a,0\leq a<n$ is true
that $i_{a}$ is the cause of $i_{a+1}$.

####  2.1.1 Sufficient, necessary, and contributory causes

A sufficient cause of a variable $j$ is defined as its cause $i$, such that if
$i$ is present then $j$ is also present. Analogously, a necessary cause of a
variable $j$ is defined as its cause $i$, such that if $i$ does not occur then
$j$ does not occur either. In the first case, the causal relation between $i$
and $j$ is called a sufficient causal relation, and in the second, a necessary
causal relation. Contributory causes of $j$ are causes that individually are
not sufficient causes of $j$, but whose conjunction with others does
constitute a sufficient cause (see state of the art).

####  2.1.2 Causation by omission and prevention

Furthermore, the following cases are distinguished: when the cause is
identified with the presence or absence of an attribute or event, and when the
effect is identified with the presence or absence of an attribute or event.
The case in which the absence of an attribute or event produces the effect is
known as omission causation. Now, regardless of causality by omission, if the
effect corresponds to the absence of an attribute or event, it is said to be a
case of prevention. Our model ignores both omission causation and prevention.
Thus, the causality implicit in our model connects only the presence of one
attribute or event to the presence of another attribute or event.

###  2.2 Data presentation

The starting point is a matrix $M$ of binary variables by individuals,
corresponding to the individuals of a population $I$ and variables of a set
$V$. Each variable represents the presence or absence of a certain attribute
in an individual. In $M$, if $m_{i\gamma}=1$ if the attribute corresponding to
the variable $i$ is present in the individual $\gamma$. Likewise, if
$m_{i\gamma}=0$ if the attribute that corresponds to variable $i$ is present
in individual $\gamma$. Attributes and individuals in the following analysis
can be understood in the most general way possible. In particular, individuals
can be situations and attributes, events that take place or not in such
situations.

We define the negation of a variable $i$, and denote it $\neg i$, as a
variable that takes value $0$ whenever $i$ is $1$ and takes value $1$ whenever
$i$ is $0$.

We denote the frequency of variable $i$ as the frequency with which $i$ takes
value $1$ in the population of individuals $I$, i.e., $\pi_{i}=\frac{1}{\mid
I\mid}\sum_{\gamma\in I}m_{i\gamma}$. Similarly, we call the frequency of
coincidences of variables $i$ and $j$ the frequency with which $i$ and $j$
take value $1$ in the same individual in the population, i.e.,
$\pi_{ij}=\frac{1}{\mid I\mid}\sum_{\gamma\in I}m_{i\gamma}m_{j\gamma}$.

In subsequent analyses, we will implicitly use a frequentist interpretation of
probability, so that, e.g., $\pi_{i}$ can be interpreted as the probability
that the variable $i$ takes $1$, and $\pi_{ij}$ the probability that $i$ and
$j$ take $1$ at the same time. These notions are extended to conditional
probability, so that $\pi_{ij\mid\neg k}$ can be interpreted as the
probability that $i$ and $j$ take value $1$, given that $k$ takes value $0$.

###  2.3 Model approach

We seek to construct a directed graph $G=<V,E>$, where each vertex corresponds
to a variable $i\in V$ and each edge $<i,j>\in E$ represents a causal
relationship between pairs of variables $i$ and $j$ of $V$, i.e., a causal
graph. Since $G$ is directed, a genealogical relationship is established
between its vertices.

According to the characteristics of causality, $G$ possesses certain
properties:

  * •

$\forall i\in V$ is true that $i\rightarrow i\notin E$ (in $G$ there are no
ties), due to irreflexivity.

  * •

In $G$ there is no more than one arc between two pairs of vertices. If there
is direct causality from $i$ to $j$ in different ways, the arc $i\rightarrow
j$ represents each and every one.

  * •

$\forall(i,j)\in V\times V$, if $i\rightarrow j\in E$ then it must hold that
$j\rightarrow i\notin E$, due to asymmetry of causality.

  * •

$G$ must be acyclic: any vertex of a cycle, being an ancestor of itself, would
be its own cause by transitivity, contradicting causal irreflexivity

Therefore, $G$ is a simple graph, and must be a $DAG$.

####  2.3.1 Triangles

For convenience, we also define triangle as a triples of vertices $(i,j,k)$,
such that there exist the arcs $i\rightarrow j$, $j\rightarrow k$,
$i\rightarrow k$. Within a triangle, these arcs are called lados. In
particular, $i\rightarrow k$ is called the hypotenuse, $i\rightarrow j$ is
called the first leg, and $j\rightarrow k$ is called the second leg. Note that
the order of the vertices is important, so that the triangle $(i,j,k)$ is not
equal to $(i,k,j)$ nor to $(j,i,k)$, for example.

The measure of length of the edges of a triangle is given by the difference in
frequency of its vertices. That is, the length of the arc $i\rightarrow j$ is
determined by $|\pi_{i}-\pi_{j}|$. Then, the Euclidean classification of
triangles according to the length of their edges (scalene, isosceles and
equilateral) also applies in this case. Bizarre, but not inconsistent, results
arise from this measure of length. For example, it follows that the vertices
of an equilateral triangle have equal frequency and that, therefore, their
edges have zero length.

A measure for the magnitude of an angle is not available and in the present
context is meaningless. In particular, there are no right triangles and the
nomenclature of legs and hypotenuse only alludes to the length of the edges
and the way a triangle is oriented (whether $(i,j,k)$ or another permutation
of the vertex triplet). The length of the hypotenuse must be greater than or
equal to the length of the legs. In addition, the hypotenuse shares the parent
vertex with the first leg and the child vertex with the second leg.

###  2.4 Modeling

Inferring causal relationships is a difficult task. If $i$ causes $j$, then
$i$ and $j$ are dependent variables. However, statistical dependence between
variables does not ensure that a causal relationship exists between them. In
fact, two variables may be statistically dependent on each other due to a
common cause. Therefore, it is often said that “correlation does not imply
causation”. However, statistical independence between variables is a necessary
and sufficient condition for the absence of causal relationships. This is the
main motivation of current causal discovery algorithms to employ statistical
independence as a primitive notion, and to indirectly infer causal
relationships by exclusion rules (see epigraph 1.7). However, in the context
of causal sufficiency relations, it is possible to follow another strategy;
namely, it is possible to infer causal relations between two variables
directly, without resorting to statistical dependence or independence between
other variables.

####  2.4.1 Causal sufficiency

Let $i$ be the cause of $j$. In the deterministic case, the causal relation
$i\rightarrow j$ is said to be sufficient if and only if it suffices for the
cause $i$ to be present for the effect $j$ to be present. That is, given
$i\rightarrow j$, $j$ can be inferred from $i$. So the causal relation
$i\rightarrow j$ in causal inference serves the same function as the material
implication $i\implies j$ in the modus ponens of logic. In the stochastic
case, causal inference is not perfect due to the presence of errors, resulting
from noise in the data.

To explain what is meant by errors, examine the truth table corresponding to
the material implication:

$i$ |  | $j$ |  | $i\implies j$
---|---|---|---|---
0 |  | 0 |  | 1
0 |  | 1 |  | 1
1 |  | 1 |  | 1
1 |  | 0 |  | 0

Table 2.1: Truth table of the material implication.

As usual, 0 means false and 1 means true.

The only condition in which the material implication is not fulfilled is in
the last row. Therefore, the ordered pair of truth values $(1,0)$
corresponding to the pair of variables $(i,j)$ is called the error (of the
material implication). In the error-free case, it is strictly satisfied
$i\implies j$.

If the value space of the variables contains no errors, the variables are
logically (and therefore statistically) dependent on each other. When the
number of errors is comparable to the number of hits (ordered pairs other than
$(1,0)$), the variables are statistically independent. So one can contrast the
errors in the data against the errors under conditions of independence to
assess how much the material implication is fulfilled and, therefore, how
justified the inference represented by $i\rightarrow j$ is.

####  2.4.2 Loevinger coefficient

The frequency of errors in $i\rightarrow j$ is $\pi_{i}-\pi_{ij}$. Now, under
conditions of statistical independence $\pi_{ij}=\pi_{i}\pi_{j}$. In case of
causality, the number of errors made in the inference from $i$ to $j$ is
expected to be smaller than in case of statistical independence between the
two. From this last condition, we construct the figure of merit that we will
use to measure the degree of validity of the causal inference:

$\displaystyle\pi_{i}-\pi_{ij}<\pi_{i}-\pi_{i}\pi_{j}$ (2.1)
$\displaystyle\pi_{i}-\pi_{ij}<\pi_{i}(1-\pi_{j})$
$\displaystyle\frac{\pi_{i}-\pi_{ij}}{\pi_{i}(1-\pi_{j})}<1$ $\displaystyle
1-\frac{\pi_{i}-\pi_{ij}}{\pi_{i}(1-\pi_{j})}>0$
$\displaystyle\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}>0$

The expression $H_{ij}=\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}$ is
known as Loevinger’s coefficient. The higher $H_{ij}$, the lower the number of
errors. Its maximum value $H_{ij}=1$ is obtained when $H_{ij}=\pi_{ij}$, and
thus corresponds to the error-free case. Its minimum admissible value,
$H_{ij}=0$, is obtained when $\pi_{ij}=\pi_{i}\pi_{j}$, and thus identifies
the case of statistical independence. It is possible to have $H_{ij}<0$, but
in these cases $\pi_{ij}-\pi_{i}\pi_{j}<0$, so the variables are negatively
correlated. It can be shown that cases of negative correlation can only
correspond to cases of causation by omission or preemptions:

$\displaystyle\pi_{ij}-\pi_{i}\pi_{j}<0$ (2.2)
$\displaystyle-\pi_{ij}+\pi_{i}\pi_{j}>0$
$\displaystyle\pi_{i}-\pi_{ij}-\pi_{i}+\pi_{i}\pi_{j}>0$
$\displaystyle(\pi_{i}-\pi_{ij})-\pi_{i}(1-\pi_{j})>0$
$\displaystyle\pi_{i\neg j}-\pi_{i}\pi_{\neg j}>0$

Note that the expression $H_{ij}$ is undefined when $\pi_{i}=0$ or $\pi_{j}=1$
(cases in which the inequality $\pi_{i}-\pi_{ij}<\pi_{i}-\pi_{i}\pi_{j}$ is
not satisfied). In these cases we take $H_{ij}=0$, by convention. Note that
causality cannot be inferred if the cause never occurs, or if the effect
always occurs.

In principle, it would suffice that $H_{ij}>0$ be satisfied to assert the
existence of causal sufficiency from $i$ to $j$. In practice, a stronger
condition, i.e. $H_{ij}>H_{0}>0$, is imposed to increase the level of
confidence in this assertion. $H_{0}$ then constitutes a threshold for causal
sufficiency between variables. This is the only parameter of the model.

On the other hand, the Loevinger coefficient is inherently asymmetric. Namely,
$H_{ij}\neq H_{ji}$ if and only if $\pi_{i}\neq\pi_{j}$. In particular,
$H_{ij}>H_{ji}$ if and only if $\pi_{i}<\pi_{j}$. The following is the proof:

$\displaystyle\pi_{i}<\pi_{j}$ (2.3)
$\displaystyle\pi_{i}-\pi_{i}\pi_{j}<\pi_{j}-\pi_{i}\pi_{j}$
$\displaystyle\pi_{i}(1-\pi_{j})<\pi_{j}(1-\pi_{i})$
$\displaystyle\frac{1}{\pi_{i}(1-\pi_{j})}>\frac{1}{\pi_{j}(1-\pi_{i})}$
$\displaystyle\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}>\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{j}(1-\pi_{i})}$
$\displaystyle H_{ij}>H_{ji}$

If $\pi_{i}<\pi_{j}$ then $H_{ij}>H_{ji}$. By inverse procedure, it can also
be proven that if $H_{ij}>H_{ji}$ then $\pi_{i}<\pi_{j}$.

If $H_{ij}>H_{ji}$ is satisfied, the inference from $i$ to $j$ from $j$ to $i$
makes more sense. Therefore, it is inferred that $i$ is a sufficient cause of
$j$ if and only if $H_{ij}>H_{0}$ and $H_{ij}>H_{ji}$ (in other words, if
$H_{ij}>H_{0}$ and $\pi_{i}<\pi_{j}$). While $H_{ij}>H_{0}$ indicates the
presence of sufficient causality, the condition $\pi_{i}<\pi_{j}$ indicates
its direction. On the other hand, the condition $\pi_{i}<\pi_{j}$ is more
supported in sufficiency contexts, where an effect is expected to occur more
frequently than its cause: the effect may have different causes, and must
appear when either of them occurs.

On the other hand, when $\pi_{i}=\pi_{j}$ asymmetry is not satisfied. In fact,
if $\pi_{i}=\pi_{j}$ then $H_{ij}=H_{ji}$, and both inferences share the same
degree of validity.

The following is the proof:

$\displaystyle\pi_{i}=\pi_{j}$ (2.4) $\displaystyle(1-\pi_{i})=(1-\pi_{j})$
$\displaystyle\pi_{j}(1-\pi_{i})=\pi_{i}(1-\pi_{j})$
$\displaystyle\frac{1}{\pi_{i}(1-\pi_{j})}=\frac{1}{\pi_{j}(1-\pi_{i})}$
$\displaystyle\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}=\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{j}(1-\pi_{i})}$
$\displaystyle H_{ij}=H_{ji}$

In these cases it is impossible to discern a priori the cause of the effect In
summary, for a pair $(i,j)$ of variables such that $\pi_{i}\leq\pi_{j}$, there
are three cases:

  * •

$\pi_{i}<\pi_{j}$ y $H_{ij}>H_{0}$, then $i$ is a sufficient cause of $j$.

  * •

$\pi_{i}<\pi_{j}$ y $H_{ij}\leq H_{0}$, then $i$ is not a sufficient cause of
$j$.

Since $\pi_{i}<\pi_{j}\implies H_{ij}>H_{ji}$, it is also true that
$H_{ji}<H_{0}$, so that $j$ is not a sufficient cause of $i$ either.

  * •

$\pi_{i}=\pi_{j}$, so $H_{ij}=H_{ji}$.

If $H_{ij}=H_{ji}\leq H_{0}$ then $i$ and $j$ are not causes of each other.

Otherwise, as the inferences have the same degree of validity, and it is not
possible to identify the direction of causality.

Finally, the Loevinger coefficient is equivalent to the measure of causality
probabilistic. According to the previous one, it is said that $i$ is the cause
of $j$ if it holds:

$\displaystyle\pi_{j|i}>\pi_{j}$ (2.5)

Developing inequality:

$\displaystyle-\pi_{j|i}<-\pi_{j}$ (2.6) $\displaystyle 1-\pi_{j|i}<1-\pi_{j}$
$\displaystyle\pi_{i}(1-\pi_{j|i})<\pi_{i}(1-\pi_{j})$
$\displaystyle\pi_{i}-\pi_{j|i}\pi_{i}<\pi_{i}(1-\pi_{j})$
$\displaystyle\pi_{i}-\pi_{ij}<\pi_{i}-\pi_{i}\pi_{j}$

which was the starting point for the definition of $H_{ij}$, in 2.1.

$Hij$ is also related to the Pearson correlation coefficient. In fact, the
Pearson coefficient for binary variables is the geometric mean of $H_{ij}$ and
$H_{ji}$:

$\displaystyle\root \of{H_{ij}H_{ji}}=\root
\of{\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{j}(1-\pi_{i})}}$
(2.7) $\displaystyle\root \of{H_{ij}H_{ji}}=\root
\of{\frac{(\pi_{ij}-\pi_{i}\pi_{j})^{2}}{\pi_{i}(1-\pi_{j})\pi_{j}(1-\pi_{i})}}$
$\displaystyle\root \of{H_{ij}H_{ji}}=\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\root
\of{\pi_{i}(1-\pi_{i})\pi_{j}(1-\pi_{j})}}$ $\displaystyle\root
\of{H_{ij}H_{ji}}=\frac{\text{Cov}(i,j)}{\root
\of{\text{Var}(i)\text{Var}(j)}}$

The Pearson coefficient is a symmetric version of the Loevinger coefficient,
where the validity of the inferences from $i$ to $j$ and from $j$ to $i$
matter simultaneously.

####  2.4.3 Construction of the causal graph

The graph is built on the sufficient causal relations inferred from $H$, on
the matrix $M$. Therefore, in $G$ there is an arc $i\rightarrow j$ if and only
if $\pi_{i}<\pi_{j}$ y $H_{ij}>H_{0}$. In cases where $\pi_{i}=\pi_{j}$, the
arcs $i\rightarrow j$ and $j\rightarrow i$ are placed , as an undirected edge
$i\leftrightarrow j$. The purpose of these edges is to reflect that the real
direction of causality is unknown. Due to causal asymmetry, it is known that
at least one of the two arcs that compose it is spurious, and consequently it
must be eliminated (see Section 3.5).

This graph largely satisfies the proposed objectives. However, it presents a
priori some essential problems. These can be summarized in:

  * •

Spurious arches

  * •

Non-transitive paths

  * •

Redundant arcs

  * •

Remaining undirected edges

These problems deserve a more detailed treatment, and are the main motivation
for the simplification of the graph $G$, by eliminating specific arcs. It is
hoped that this will resolve the problems raised, and obtain a new graph that
represents only sufficient and direct causal relationships.

###  2.5 Spurious arcs

The coefficient $H_{ij}$ is a criterion for inferring causality between a pair
of variables $i$ and $j$. As long as $H_{ij}>H_{0}$ or $H_{ji}>H_{0}$ a causal
relationship is claimed to exist, and is considered to take place from $i$ to
$j$ or vice versa, respectively. However, the arc $i÷toj$ may represent a
spurious causal relationship, in which the vertices involved do not form a
cause-and-effect pair.

It turns out that, when $i$ and $j$ are correlated, any of the following three
cases may occur:Hausman

  * •

$i$ is cause of $j$

  * •

$j$ is cause of $i$

  * •

$i$ and $j$ are effects of a common cause.

Therefore, the spurious causal relationship between $i$ and $j$ is then due to
a cause $k$, common to both. In these cases, for fixed values of $k$, a
variation in the values of $i$ should not cause changes in $j$, or vice versa.
That is, conditioning on the values of the common parent $k$ must break the
apparent relationship of causal sufficiency between $i$ and $j$. In other
words:

$H_{ij|k}\leq H_{0}$ (2.8)

$H_{ij|\neg k}\leq H_{0}$ (2.9)

This criterion is inspired by one of the pillars of the probabilistic theory
of causality, i.e. Reichenbach’s principle of common cause (see Section 2.2).

Conditions 2.8 and 2.9 are sufficient to justify the absence of causal
sufficiency from $i$ to 2.8 y 2.9 bastan para justificar la ausencia de
suficiencia causal de $i$ a $j$ or vice versa. Given a common parent $k$ that
meets the aforementioned criterion, it is possible to affirm that $k$ is
responsible for the spurious causal sufficiency relationship between $i$ and
$j$. Therefore, for every edge $i\rightarrow j\in E$ (including undirected
ones), we look to see if there is a cause $k$ common to $i$ and $j$ that
satisfies the proposed conditions, and if this is met, the arc $i\rightarrow
j$ of $G$ is completely eliminated.

####  2.5.1 Order of elimination of spurious arcs

In principle, the order of elimination of spurious arcs is arbitrary. If
conditioning on a common parent and its absence breaks a causal relationship,
it is assumed that the causal relationship is spurious and that the common
parent is responsible for the underlying correlation. Now, accidentally, due
to the incompleteness of the data in terms of variables and individuals, the
ordering of the elimination of arcs can be important. First, it is possible
that the set of individuals is not sufficient to distinguish a real common
father from a fictitious one. In particular, it is possible that the real
parent corresponds to a variable external to the graph but is
indistinguishable from a variable internal to the graph, given the sample of
individuals. The latter leads to situations in which arcs are eliminated that
should not have been eliminated based on vertices of the graph. The
consequence of this elimination does not have a local character. That is,
there is a cascade effect that results in the permanence of spurious arcs that
could have been eliminated based on the vertices of the graph.

To exemplify the above, all possible cases in which the late elimination of a
spurious arc generates conflicts will be illustrated. Since every spurious arc
$j\rightarrow k$ is the second leg of the triangle that it shares with $i$,
the common parent of $j$ and $k$ responsible for the spurious relationship,
then it is only necessary to consider three cases. These occur when the second
leg of the triangle in question is the first leg, second leg, or hypotenuse of
another triangle. Each of these will be exemplified below, taking a
hypothetical triangle $(i,j,k)$ as the triangle to examine.

In the first case, the second leg of triangle $(i,j,k)$ is hypotenuse of
another triangle $(j,l,k)$ (Fig.2.1). In this one, both in the diagram
Fig.2.1(a), as well as in Fig.2.1(b) and Fig.2.1(c), the frequency of the
vertices is decreasing with the ordinate axis (e.g., as $i$ is above $j$ on
the $Y$-axis, then $i$ < $j$). Henceforth, this feature will be present in all
figures, to gain in explainability and regularity of the diagrams. By
construction, in this example the arc $j\rightarrow k$ is spurious and the arc
$l\rightarrow k$ must not be eliminated on the basis of graph vertices. That
is, the graph underlying Fig.2.1(a) is Fig.2.1(b). Moreover, $i$ is the cause
common to $j$ and $k$ that causes the arc $j\rightarrow k$ to appear. If the
triangle $(j,l,k)$ is visited first, the arc $l\rightarrow k$ can be
eliminated under the erroneous assumption that $j$ is common parent of $l$ and
$k$, and then the arc $j\rightarrow k$ by its spuriousness, obtaining the
incorrect graph of the 2.1(c).

Figure 2.1: First case of adjacent triangles, with conflict for the
elimination of spurious arcs

In the second case, the second leg of the triangle $(i,j,k)$ is the first leg
of another triangle $(j,k,l)$ (Fig.2.2). Analogous to the previous one, in
this example the arc $j\rightarrow k$ is spurious and the arc $k\rightarrow l$
should not be eliminated based on the vertices of the graph. That is, the
graph underlying Fig.2.2(a) is Fig.2.2(b). Furthermore, $i$ is the common
cause to $j$ and $k$ that causes the appearance of the arc $j\rightarrow k$.
Again, if the triangle $(j,k,l)$ is visited first, the arc $k\rightarrow l$
can be erroneously eliminated for the same reasons, and then the arc
$j\rightarrow k$ due to its spuriousness, obtaining the incorrect graph of
Fig.2.2(c).

Figure 2.2: Second case of adjacent triangles, with conflict for the
elimination of spurious arcs

In the third and last case, the arc $j\rightarrow k$ is the second leg of the
triangles $(i,j,k)$ and $(l,j,k)$ (Fig.2.3). By construction, the arc
$j\rightarrow k$ is spurious in this example: the graph underlying Fig.2.3(a)
is Fig.2.3(b), and i is the common cause to $j$ and $k$ that causes its
appearance. In this case no conflicts are generated, since the only arc to
eliminate in both triangles is the spurious arc itself.

Figure 2.3: Third case of adjacent triangles, without conflicts for the
elimination of spurious arcs

The elimination of arcs that should not be removed based on the vertices of
the graph can be reduced by following an order criterion for the elimination
based on the average frequency of the ends of the arcs, from lowest to
highest. In cases of equal average frequency, there is no order criterion
based on arc properties. In this scheme, a heuristic but reasonable criterion
is used: eliminating the arcs from highest to lowest correlation. It is
presumed that the external variables produce spurious relationships of lower
correlation than the internal variables, given that the latter have been
previously selected as the most relevant.

###  2.6 Non-transitive paths

Transitivity is a property of causal relations. In the deterministic case, it
holds that if $i\rightarrow j$ and $j\rightarrow k$, then $i\rightarrow k$.
Note that if we always have $i\implies j$ and $j\implies k$, then $i\implies
k$. In terms of $H$, if $H_{ij}=1$ and $H_{jk}=1$, then $H_{ik}=1$:

$\displaystyle H_{ij}=1\implies\pi_{ij}=\pi_{i}$ (2.10)
$\displaystyle\pi_{ij}=\pi_{i}\implies\pi_{i\neg j}=0$
$\displaystyle\pi_{i\neg j}=0\implies\pi_{i\neg jk}=0$ $\displaystyle
H_{jk}=1\implies\pi_{jk}=\pi_{j}$
$\displaystyle\pi_{jk}=\pi_{j}\implies\pi_{ijk}=\pi_{ij}$
$\displaystyle\pi_{ik}=\pi_{ijk}+\pi_{i\neg jk}$
$\displaystyle\pi_{ik}=\pi_{ij}+0$ $\displaystyle\pi_{ik}=\pi_{ij}$
$\displaystyle\pi_{ik}=\pi_{i}$ $\displaystyle\pi_{ik}=\pi_{i}\implies
H_{ik}=1$

But in the stochastic case these conditions are not met exactly, and
transitivity may be lost. To illustrate, see the following example that
represents a possible distribution of three variables $i$, $j$, and $k$ in a
set of 22 individuals:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | … | 22
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$i$ | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$j$ | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$k$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | … | 0

Table 2.2: Possible distribution of three variables $i$, $j$, and $k$ in 22
individuals

In principle, none of the implications $i\implies j$ or $j\implies k$ hold
strictly, but the number of errors present in each one is small.

For $H_{0}=0.5$ we have:

$\displaystyle
H_{ij}=\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}=\frac{\frac{4}{22}-\frac{6}{22}\frac{7}{22}}{\frac{6}{22}(1-\frac{7}{22})}\approx
0.51>H_{0}$ (2.11) $\displaystyle
H_{jk}=\frac{\pi_{jk}-\pi_{j}\pi_{k}}{\pi_{j}(1-\pi_{k})}=\frac{\frac{5}{22}-\frac{7}{22}\frac{8}{22}}{\frac{7}{22}(1-\frac{8}{22})}\approx
0.55>H_{0}$

So, as $\pi_{i}<\pi_{j}<\pi_{k}$, $i$ is a sufficient cause of $j$, y $j$ is a
sufficient cause of $k$ (assuming that there is no spuriousness). By
transitivity, it must also be true that $i$ is a sufficient cause of $k$.
Nevertheless:

$\displaystyle
H_{ik}=\frac{\pi_{ik}-\pi_{i}\pi_{k}}{\pi_{i}(1-\pi_{k})}=\frac{\frac{2}{22}-\frac{6}{22}\frac{8}{22}}{\frac{6}{22}(1-\frac{8}{22})}\approx-0.047<H_{0}$
(2.12)

That is, $i$ is not a sufficient cause of $k$. This does not constitute a
violation of causal transitivity in the underlying deterministic case, since
the following situation could occur:

Figure 2.4: Example of possible latent contributory causes

In this example, $l$ contributes (together with $i$) in the production of
effect $j$, and $m$ contributes (together with $j$) in the production of
effect $k$. Then in the causal relationship $i\rightarrow k$ Two external
causes contribute, losing causal sufficiency. It can be said that in reality
the arcs $i\rightarrow j$ and $j\rightarrow k$ represent quasi-sufficient
causal relations that emerge, for example, when contributory causes $l$ and
$m$ have little variability in the data.

En este ejemplo, $l$ contribuye (junto a $i$) en la producción del efecto $j$,
y $m$ contribuye (junto a $j$) en la producción del efecto $k$. Luego en la
relación causal $i\rightarrow k$ contribuyen dos causas externas, perdiéndose
la suficiencia causal. Puede decirse que en realidad los arcos $i\rightarrow
j$ y $j\rightarrow k$ representan relaciones causales cuasi-suficientes que
emergen, por ejemplo, cuando las causas contributivas $l$ y $m$ tienen poca
variabilidad en los datos. In any case, one should not dispense with the non-
transitive path $i\to j\rightarrow k$, since it provides useful information
about the underlying causal relationships.

###  2.7 Redundant arcs

See the following matrix, corresponding to a possible distribution of three
variables $i$, $j$, and $k$, in a set of 22 individuals:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | … | 22
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$i$ | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$j$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$k$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0

Table 2.3: Possible distribution of three variables $i$, $j$, and $k$, in 22
individuals

As can be corroborated, the material implications $i\implies j$ and $j\implies
k$ are strictly fulfilled. Then $H_{ij}=1$, $H_{jk}=1$ and therefore
$H_{ik}=1$. Since $\pi_{i}<\pi_{j}<\pi_{k}$, the arcs $i\rightarrow j$,
$j\rightarrow k$ and $i\rightarrow k$ are considered to represent sufficient
causal relations. However, in this triangle $(i,j,k)$ the hypotenuse does not
provide new information regarding the legs: the causal relationship it
represents is completely describable by the latter. Therefore, it is a
redundant arc. This is because $i\rightarrow k$ actually represents an
indirect causal relationship from $i$ to $k$ through $j$, a product of
transitivity.

This particular example illustrates a deterministic case, and in these cases
transitivity always holds, as seen above. Therefore, to identify $i\rightarrow
k$ as a transitive arc, it is enough that $i\rightarrow j$ and $j\rightarrow
k$ exist. But in the stochastic case this generally does not hold. To
illustrate, see the following example:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | … | 22
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$i$ | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$j$ | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | … | 0
$k$ | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | … | 0

Table 2.4: Possible distribution of three variables $i$, $j$, and $k$ in 22
individuals

For $H_{0}=0.5$ we have:

$\displaystyle
H_{ij}=\frac{\pi_{ij}-\pi_{i}\pi_{j}}{\pi_{i}(1-\pi_{j})}=\frac{\frac{5}{22}-\frac{6}{22}\frac{7}{22}}{\frac{6}{22}(1-\frac{7}{22})}\approx
0.75>H_{0}$ (2.13) $\displaystyle
H_{jk}=\frac{\pi_{jk}-\pi_{j}\pi_{k}}{\pi_{j}(1-\pi_{k})}=\frac{\frac{5}{22}-\frac{7}{22}\frac{8}{22}}{\frac{7}{22}(1-\frac{8}{22})}\approx
0.55>H_{0}$ $\displaystyle
H_{ik}=\frac{\pi_{ik}-\pi_{i}\pi_{k}}{\pi_{i}(1-\pi_{k})}=\frac{\frac{6}{22}-\frac{6}{22}\frac{8}{22}}{\frac{6}{22}(1-\frac{8}{22})}=1>H_{0}$

Therefore, as $\pi_{i}<\pi_{j}<\pi_{k}$, it is considered that the arcs
$i\rightarrow j$, $j\rightarrow k$ and $i\rightarrow k$ represent sufficient
causal relations. In the causal sufficiency relation $i\rightarrow k$ there
are no errors. On the other hand, in the causal chain $i\rightarrow
j\rightarrow k$ there are a total of $3$ errors, corresponding to columns
$6$-$8$ of the matrix. Given this situation, in the triangle $(i,j,k)$ it is
not possible to explain, using the legs , the causal relationship represented
by the hypotenuse. Therefore, either $i\rightarrow k$ is a direct causal
relationship in itself, or it is the union of a direct and an indirect
relationship, or it represents another indirect relationship in which $j$ does
not intervene.

A criterion is necessary, then, to identify transitivity relations of which
not, with the aim of eliminating all the redundancies of $G$.

Starting from the first example (deterministic case of causality), it is
observed that the transitive relation $i\rightarrow k$ meets the following
conditions:

$\pi_{ij}=\pi_{ik}\leq\pi_{jk}\\\ $ (2.14) $\pi_{\neg i\neg j}\geq\pi_{\neg
i\neg k}=\pi_{\neg j\neg k}$ (2.15)

On the other hand, in case of statistical independence between $i$, $j$ and
$k$ two by two (case of nonexistence of causal relationships), the conditions
are met:

$\pi_{i}\pi_{j}<\pi_{i}\pi_{k}<\pi_{j}\pi_{k}\implies\pi_{ij}<\pi_{ik}<\pi_{jk}$
(2.16) $\pi_{\neg i}\pi_{\neg j}>\pi_{\neg i}\pi_{\neg k}>\pi_{\neg
j}\pi_{\neg k}\implies\pi_{\neg i\neg j}>\pi_{\neg i\neg k}>\pi_{\neg j\neg
k}$ (2.17)

In the intermediate case, transitive relations are expected to fulfill a mixed
condition of both. That is:

$\pi_{ij}\leq\pi_{ik}\leq\pi_{jk}$ (2.18) $\pi_{\neg i\neg j}\geq\pi_{\neg
i\neg k}\geq\pi_{\neg j\neg k}$ (2.19)

These inequalities were rigorously deduced by Mokken within the framework of a
latent variable theory.Mokken Even so, it was preferred to avoid the
formalization of Mokken for two fundamental reasons: 1) Mokken does not
address the issue of causality (and therefore, neither that of indirect
causality) and it is only a reinterpretation of its result that we allows it
to be used in our context, and 2) Mokken’s conceptual apparatus requires a
series of assumptions that, although compatible with the case of interest,
require a much more detailed treatment, which is beyond the scope of this
thesis. We refer the reader to Mokken’s book, under the assumption that prima
facie the Loevinger coefficient is capable of measuring the validity of causal
inference.

Therefore, for every triangle $(i,j,k)$, the hypotenuse is considered to
represent an indirect causal relationship described by the legs if the
proposed conditions are met. In this case, the hypotenuse $i\rightarrow k$ of
$G$ is eliminated.

Note that in the example related to table 2.4 condition 2.18 is not met, since
$\pi_{ik}>\pi_{jk}$. Therefore, it is correctly identified that the arc
$i\rightarrow k$ is not transitive.

Finally, if any of the legs of $(i,j,k)$ is an undirected edge, it is directed
in the sense of the identified transitive causal relationship. For example, by
identifying an arc $i\rightarrow k$ as the indirect causal relation
$i\rightarrow j\rightarrow k$, the edge between $i$ and $j$ is directed as if
undirected. Analogously for the edge between $j$ and $k$.

Figure 2.5: Examples of undirected edge orientation in the presence of
transitivity

####  2.7.1 Order of elimination of redundant arcs

Removing arcs by this method must follow a specific order, to avoid conflicts.
Three cases may arise: when the transitive hypotenuse of the triangle
considered is the transitive hypotenuse of another triangle, and when it is
the first or second leg of another transitive triangle. In the first case, the
hypotenuse could be eliminated by either of the two triangles involved.
However, in the second and third cases, eliminating the hypotenuse destroys
another transitive triangle. The cases in which the transitive hypotenuse is
the first or second leg of another transitive triangle are, essentially,
identical, so only one of them will be addressed below.

Take as an example the case in which the transitive hypotenuse of a triangle
is the second leg of another transitive triangle (Fig.2.6). In this case, the
hypotenuse of the triangle $(j,l,k)$ is the second leg of the triangle
$(i,j,k)$. By construction, the arcs $i\rightarrow k$ and $j\rightarrow k$
represent the indirect causal relations $i\rightarrow j\rightarrow k$ and
$j\rightarrow l\rightarrow k$ respectively. By choosing the second triangle
first (Fig.2.6(b)) and eliminating $j\rightarrow k$, the first triangle
disappears. Therefore, it is impossible to eliminate the arc $i\rightarrow k$
with the proposed method.

Figure 2.6: Incorrect removal order for transitive arcs

On the other hand, if the first triangle is chosen first (Fig.2.7(a)) and the
arc $i\rightarrow k$ is eliminated , the second triangle can later be visited
(Fig.2.7(b)) and $j\rightarrow k$ eliminated without problems, obtaining the
correct underlying graph (Fig.2.7(c)).

Figure 2.7: Correct removal order for transitive arcs

Note that in general, when the transitive hypotenuse is the first or second
leg of another transitive triangle, it is true that said hypotenuse has less
than or equal length than that of the other triangle. Since the hypotenuse of
the other triangle must be removed first, if they are removed in order from
longest to shortest by length, no conflicts as long as the lengths are
different. That is, an arc $i\rightarrow j$ will be examined before another
$l\rightarrow k$ if $|\pi_{i}-\pi_{j}|>|\pi_{l}-\pi_{k}|$.

However, under this criterion, the order of elimination is arbitrary in cases
of equal length. Only when two triangles are adjacent, and their hypotenuses
have equal length, an order must be established for the discarding of
redundant arcs. In these conditions, three cases are distinguished, according
to the role played the hypotenuse of the triangle considered in the adjacent
triangle (first leg, second leg, and hypotenuse). In the case of the
hypotenuse, the order of elimination is arbitrary. Eliminating the hypotenuse
of a transitive triangle, with the help of another transitive triangle that
also has it as hypotenuse means, in any way, eliminating it. In the case where
the arc in question is the second leg of the adjacent triangle, the order of
elimination can be found in terms of Mokken’s inequalities, that is, by
ordering the arcs by frequency of coincidences from smallest to largest.
However, this order fails in the case where the arc is the first leg of the
adjacent triangle where the order of elimination would be dictated by the
frequency of coincidences, but in reverse, from highest to lowest.

In the algorithm under discussion, one of these orders is taken by frequencies
of coincidences, knowing that there may be redundant arcs that will not be
eliminated. In any case, these cases must be rare as they must satisfy three
conditions: 1) that for a transitive triangle there exists at least one other
adjacent triangle, 1) transitive triangle, 2) transitive triangle transitive,
2) that the hypotenuses of the adjacent triangles be of equal length, and 3)
that the hypotenuses of the adjacent triangles be of equal length. equal
length, and 3) that one of the triangles takes the redundant arc of the other
as its first leg. of the other as the first leg.

A simple algorithm for solving this problem would be to postpone the
elimination of arcs of equal length until we move to a different length in the
order of arcs. to a different length in the order of arcs. Unfortunately, this
leads to a large computational computational cost since there is no way to
distinguish a priori whether the arc of equal arc of equal length will be
hypotenuse, first or second leg of a transitive triangle. transitive triangle.

We then resort to the same heuristic criterion used as in the heading 2.5.1:
order the arcs of equal length from greatest to least correlation.
correlation. The idea is to give priority to the hypotenuses with the highest
correlation between their extremes, since they are the ones that presumably
represent direct and non-redundant causal relationships.

###  2.8 Remaining undirected edges

The methods used to eliminate spurious and redundant arcs can partially solve
the problem of undirected edges in $G$. In specific cases, they allow them to
be completely removed or their real direction determined. However, they are
not sufficient solutions: the first requires the spuriousness of the edge to
eliminate it, while the second requires the presence of transitivity in the
triangle under analysis to eliminate the edge or orient it according to the
case. Consequently, other approaches are necessary to orient or eliminate
possible remaining undirected edges.

In an initial approach, for each undirected edge $i\leftrightarrow j$ it is
possible to discern cause from effect using the asymmetric properties of
causality. For example, from a property of $i$ inherent to causes and improper
to effects, one could conclude that the causal relation underlying
$i\leftrightarrow j$ is $i\rightarrow j$, and eliminate the opposite arc
$j\rightarrow i$. Among the possible causality asymmetries to analyze for this
purpose, one of the best candidates is robustness.

Hausman defines robustness as an asymmetric property of causality, which
expresses the invariance of the cause-effect relationship with respect to the
frequency of the cause or how it arises, but not with respect to the frequency
of the effect or how it arises.Hausman Modifying the frequency of a cause
should not break the link between it and the effect. However, due to the
necessary condition $\pi_{i}<\pi_{j}$ , increasing the frequency of a cause
$i$ is not always feasible (an increase in the frequency of $i$ could violate
the inequality). On the other hand, decreasing the frequency of a cause $i$
does not cause conflicts in terms of robustness: the necessary condition
remains true, and the number of errors in $i\rightarrow j$ can only be
maintained or decreased.

This criterion can be used to orient undirected edges. For a given arc
$i\leftrightarrow j$, the robustness of the relations $i\rightarrow j$ and
$j\rightarrow i$ is checked. If the first is robust (a decrease in the
frequency of $i$ keeps the cause-effect relationship from $i$ to $j$ intact),
while the second does not, then it is assumed that $i\rightarrow j$ is the
causal relationship underlying $i\leftrightarrow j$, and the arc $j\rightarrow
i$ is eliminated. Analogously otherwise.

At this point, the question is how to correctly alter the frequency of a
variable. Decreasing the frequency of a variable $i$ does not only alter the
value $\pi_{i}$, it also varies the individuals in which the variable $i$
takes a value of $1$. This redistribution of values of $i$ cannot be
arbitrary, as it could change the nature of the variable, invalidating the
analysis.

In a stochastic case, the following solution can be taken to obtain a valid
redistribution of a variable $i$:

  * •

Carry out a new survey of variable $i$ on the same population of individuals.

  * •

Calculate the intersection between the results of the original survey and this
new survey.

  * •

Let $ii$ be this intersection, take $ii$ as the new variable $i$.

This solution is justified in that $ii$ takes a value of $1$ only in
individuals in which $i$ is $1$ for both surveys, and therefore collects the
most consistent information about $i$. On the other hand, $p_{ii}\leq p_{i}$,
so the desired decrease in frequency is expected to be achieved.

With the new distribution $ii$, we calculate
$H_{iij}=\frac{\pi_{iij}-\pi_{ii}\pi_{j}}{\pi_{ii}(1-\pi_{j})}$ to check if it
remains above the validity threshold $H_{0}$ (note that the expression
$H_{iij}$ is obtained from $H_{ij}$ by replacing all the values referring to
$i$ with those of $ii$). If $H_{iij}>H_{0}$ is true, then the relationship
$i\rightarrow j$ is robust. If by proceeding analogously with $j$, it is
confirmed that $j\rightarrow i$ is not robust $H_{jji}<H_{0}$, then it is
assumed that $i\rightarrow j$ is the causal relationship underlying
$i\leftrightarrow j$, and the arc $j\rightarrow i$ is eliminated. In cases
where both relationships are robust, the edge can be oriented based on the
values $H_{iij}$ and $H_{jji}$. If $H_{iij}>H_{jji}$ is true , it makes more
sense to infer causality from $i$ to $j$ than vice versa, given its greater
validity. Analogously for the case $H_{iij}<H_{jji}$. The cases in which
$H_{iij}=H_{jji}$ hold should be considerably few or non-existent.

Even if the problem seems solved, conducting a new survey for a variable $i$
is usually impractical or impossible. An alternative then is approximating
$ii$, which in practice is reduced to approximating the values$\pi_{ii}$ and
$\pi_{iij}$ that are used to calculate $H_{iij}$.

Let $i-1$ be the parent of $i$ with the highest frequency of matches with $i$,
$i-1$ can be taken as the approximation of a new survey of $i$. However,
considering the values $\pi_{i,i-1}$ and $\pi_{ii}$ approximate may not be
rigorous enough.

However, it can be expected that the similarities between both terms are
maintained even in cases of independence, due to the way in which $i-1$ was
chosen, ie,
$\frac{\pi_{ii}}{\pi_{i,i-1}}\approx\frac{\pi_{i}^{2}}{\pi_{i}\pi_{i-1}}$.
Solving, we obtain $\pi_{ii}\approx\frac{\pi_{i}\pi_{i,i-1}}{\pi_{i-1}}$ as an
approximate expression for $\pi_{ii}$. On the other hand, let $i+1$ be the
child of $i$ with the highest frequency of coincidences with $i$, the
expression $\pi_{ii}\approx\frac{\pi_{i}\pi_{i,i+1}}{\pi_{i+1}}$ is obtained
in an analogous way as an approximation of $\pi_{ii}$. These two expressions
were proposed by Mokken within the framework of his theoryMokken, also as an
approximation of the coincidences between surveys of the same variable, with
similar definitions of $i-1$ and $i+1$.

Using reasoning similar to the previous one, it is expected that the
similarities between $\pi_{ij}$ and $\pi_{iij}$ will remain proportional in
case of independence between $i$ and $j$, this is,
$\frac{\pi_{ij}}{\pi_{iij}}\approx\frac{\pi_{i}\pi_{j}}{\pi_{ii}\pi_{j}}$.
Solving, we obtain $\pi_{iij}\approx\frac{\pi_{ii}\pi_{ij}}{\pi_{i}}$ as an
approximate expression for $\pi_{iij}$.

By approximating the values $\pi_{ii}$, $\pi_{iij}$, $\pi_{jj}$ and
$\pi_{jji}$ in this way, it is possible to calculate $H_{iij}$ and $H_{jji}$
to carry out the rest of the proposed analyses. In practice, for each
undirected edge $i\leftrightarrow j$ the values are approximated using $i-1$
and $j-1$ first and, if this is not sufficient $H_{iij}=H_{jji}$), using $i+1$
and $j+1$ later.

In the small cases in which $H_{iij}=H_{jji}$ is met, one last criterion is
applied: calculate and compare the values $H_{iijj}$ and $H_{jjii}$.
$H_{iijj}$ is a measure of the validity of the inference $i\rightarrow j$
considering only the most consistent information of $i$ and $j$. Therefore, if
$H_{iijj}>H_{jjii}$ then it makes more sense to infer causality from $i$ to
$j$ than vice versa, given its greater validity. Analogously for
H$H_{iijj}<H_{jjii}$. On the other hand, if $H_{iijj}\leq H_{0}$ and
$H_{jjii}\leq H_{0}$ are true, it is considered that between $i$ and $j$ there
is actually no causal sufficiency relationship: since causal sufficiency is
lost in both directions when considering only the most consistent data for
each variable, then it can be concluded that such sufficiency is spurious, a
product of noise in the data.

Since the values $\pi_{ii}$ and $\pi_{jj}$, to calculate
$H_{iijj}=\frac{\pi_{iijj}-\pi_{ii}\pi_{jj}}{\pi_{ii}(1-\pi_{jj)}}$ it’s just
necessary to calculate $\pi_{iijj}$. Applying the same idea as with
$\pi_{iij}$, it’s assumed
$\frac{\pi_{ij}}{\pi_{iijj}}\approx\frac{\pi_{i}\pi_{j}}{\pi_{ii}\pi_{jj}}$,
and $\pi_{iijj}\approx\frac{\pi_{ii}\pi_{jj}\pi_{ij}}{\pi_{i}\pi_{j}}$ is
obtained as an approximate expression for $\pi_{iijj}$.

##  Chapter 3 Implementation details and experiments

The methodology for causal discovery proposed in the previous chapter is
original, and is presented for the first time in this document. For its
implementation, a code for scientific use called CChains (for causal chains,
in English) is developed in the C++ programming language. The latter is chosen
because it is a high-speed compiled language, ideal for the intense
calculation required by the algorithm.

The program consists of several phases, which correspond to each of the steps
of the methodology. First, the causal graph is constructed [phase 1], using
the metric $H_{ij}$ for each pair of vertices and the threshold $H_{0}$.
Second, we proceed to simplify the causal graph [phase 2], by eliminating
arcs. This phase is further subdivided into three stages dedicated to solving
the problems of spurious arcs (due to a common cause) [stage 1], redundant
(due to transitivity) [stage 2] and remaining undirected edges [stage 3], in
that order. In each stage, all and only the arcs of the simplified graph in
the previous stage or phase are consulted. All phases and stages are
independent, in the sense that they consist of their own inputs and outputs,
and are associated with different modules.

In the following, the input, output and operating specifications of each phase
and stage are discussed, after an explanation of the basic general
configuration.

###  3.1 General configuration

The program code base is available in the public GitHub repository
https://github .com/jean-pierre-gm/CChains. It can be downloaded through the
console by using the command git clone https://github.com/jean-pierre-
gm/CChains and, if you have Cmake installed, compiled using the command cmake
from the downloaded directory, to obtain the corresponding executable. Since
the program is intended for scientific use, it does not have a graphical user
interface. However, the configuration of the program is extremely simple, as
will be described below.

The configuration is done by means of a plain text file. The address of this
file is the only argument that the program receives, e.g:

⬇

1 C:\Users\Jean\Desktop> CChains.exe parameters.txt

This file specifies the address of the remaining input (data) and output
files, among other specifications. The configuration file has the next format,
e.g,

⬇

1 run_mode=build

2

3 metric=H

4 threshold=0.5

5

6 graph_builder_in=sample.txt

7 graph_builder_out=graph_file.txt

8 graph_builder_frequencies_out=frequencies.txt

9

10 run_summary=out.txt

Each line of the configuration file must correspond to a single input
variable, following the format texttt$<$variable name$>$=$<$value$>$. Any line
that does not respect this format is taken as a comment and is therefore not
processed as input.

In particular, the input variables run_mode, metric, threshold and run
summary are global.

The variable metric refers to the measure associated to each pair of vertices
to check whether or not an arc exists between them (in phase 1), and on the
basis of which spurious arcs and undirected edges are simplified (in phase 2,
stages 1 and 3, respectively). Although the CChains methodology starts from
$H$, it may be of interest to analyze the behavior of some phase or stage of
the algorithm (in particular, the construction of the graph) using other
metrics. The metrics available are the Loevinger coefficient (metric=H), the
Pearson correlation coefficient (metric=r) and the two measures of
probabilistic causality explored under the heading 1.2 (metric=pc1 and
metric=pc2). This input variable is mandatory.

The variable threshold refers to the threshold that must be exceeded by the
considered metric to determine the presence of an arc between two vertices (in
phase 1), as well as to simplify spurious arcs and undirected edges (in phase
2, stages 1 and 3, respectively). It corresponds to the parameter $H_{0}$ in
the case metric=H. This input variable is mandatory.

La variable run_mode especifica qué fases o etapas del programa se desean
ejecutar. En particular, la instrucción

  * •

run_mode=build is used to build the causal graph (phase 1),

  * •

run_mode=Reichenbach to eliminate spurious arcs (phase 2, stage 1),

  * •

run_mode=Mokken to remove redundant arcs (phase 2, stage 2),

  * •

run_mode=Robustness to remove remaining undirected edges (phase 2, stage 3).

The variables corresponding to stages 1 and 2 of phase 2 are named Reichenbach
and Mokken because Reichenbach’s principle of common cause (heading 1.2), and
the inequalities 2.18 and 2.19 proposed by Mokken, are the main inspiration
for these phases of the proposed algorithm.

The phases and stages can be chained with the operator &, to be executed one
after the previous one. executed one after the previous one, e.g,
run_mode=build& Reichenbach_test&Robustness_test. This input variable is
mandatory.

The variable run summary determines the address of the file to which the run
report for each phase is written. the execution report of each phase or stage
is written to. The report contains summary information about the number of
arcs before and after each stage or phase. of each stage or phase. This input
variable is optional. In its absence, the program writes the output report to
the console.

###  3.2 Construction of the causal graph

The program constructs a causal graph $G=<V,E>$, from a matrix $M$ of binary
variables $V$ by individuals $I$, using the method proposed in the section
2.4.3. The matrix data is received as a plain text file, the address of which
is determined by the value of the input variable in the configuration file
graph_builder_in (e.g., graph_builder_in=sample.txt). This file contains the
matrix $M$ in tabular form, where each row represents a variable from $V$ and
each column represents an individual from $I$. The number of rows and columns
matches the number of individuals in the matrix. The number of rows and
columns coincides with $|V|$ and $|I|$, respectively. The supported values of
each component are $0$ or $1$, and each column must be separated by _normal_
or tab (or _tab_) spaces. Below is an example of a file with the correct
formatting:

⬇

1 0 1 1 0 0 0 0 0

2 0 1 1 1 1 1 1 1

3 0 0 0 1 1 1 1 1

4 0 1 0 1 1 1 1 1

5 0 0 0 1 0 1 1 0

6 1 1 1 1 1 1 1 0

So far, the only input data required for phase 1. As output, the program
returns a file with the causal network, in the form of adjacency lists.
adjacency lists. The variable graph_builder_out determines the output file of
the network (e.g., graph_builder_out=graph_file.txt) in plain text. The row
$i$ of this file corresponds to the adjacency list of the vertex $i\in G$. In
each column, the adjacencies of $i$ are represented as pairs ($j$, $j$, $j$).
are represented as pairs ($j$, $\pi_{ij}$), where the child index and the
frequency of parent-child matches are separated by a space. In contrast, the
columns are separated by a _tab_. Finally, empty rows empty rows correspond to
vertices without children. See the following example of output file for the
network:

⬇

1 1 0.25 5 0.25

2

3 1 0.625 3 0.625

4 1 0.75

5 1 0.375 2 0.375 3 0.375 5 0.375

These formats for graphs and data matrices will be used hereafter to describe
the inputs and outputs of the algorithm.

Additionally, the input variable graph_builder_frequencies_out determines the
address of the output file for the frequency of the vertices of $G$ (e.g.,
graph_builder _frequencies_out=frequencies.txt). This entry is optional, and
in its absence the frequencies of each vertex are not exported to file. When
generated, this file contains one row and one column for each vertex. The
order of rows is not in correspondence with the order of frequencies, but with
the row index of the matrix $M$ and of vertices in the graph $G$.

####  3.2.1 Input matrix compression

The matrix may contain identical rows due to the finiteness of the sample of
individuals and/or the origin of the binary matrix. In case identical rows are
present, the associated variables are described by a single vertex. For this
reason, from the initial set $V$ of variables (rows of $M$), another final set
$V$ of vertices of $G$) must be constructed, such that to each variable of $V$
corresponds one and only one vertex of $V$, and to two variables of $V$
corresponds the same vertex of $V$, and to two variables of $V$ corresponds
the same vertex of $V$, such that to each variable of $V$ corresponds the same
vertex of $V$, such that to each variable of $V$ corresponds the same vertex
of $V$, if and only if the corresponding rows of the matrix of the matrix $M$
are identical.

This process is called matrix compression and takes place in stage 1 of phase
1 (stage 1), and is specified in the input variable run_mode by means of the
value sample_compressor. This C++ method (hereafter, _method_ in italics)
receives the original matrix $M$, performs the compression process, and
returns the resulting matrix $M^{\prime}$, where all rows are different from
each other. The addresses of the input and output files of the matrix must be
specified in the configuration file, by means of the variables
sample_compressor_in and sample_compressor_out.

The _method_ also returns another file, where each row corresponds to a vertex
of $V^{\prime}$, and each column corresponds to the variables in $V$ variables
associated to it. The purpose of this file is to serve as a map between the
variables and the vertices (or nodes) of the network. The address of this
output file is specified by the input variable sample_compressor_nodes_out.

The simplest run using matrix compression is set up as follows, e.g.:

⬇

1 run_mode=sample_compressor\&build

2

3 metric=H

4 threshold=0.5

5

6 sample_compressor_in=sample.txt

7 sample_compressor_out=compressed_sample.txt

8 sample_compressor_nodes_out=nodes.txt

9

10 graph_builder_in=sample.txt

11 graph_builder_out=graph_file.txt

12 graph_builder_frequencies_out=frequencies.txt

The matrix $M^{\prime}$ obtained from the compression process is the one to be
used from now on in the rest of the phases of the algorithm, in particular
used in the remaining phases of the algorithm, in particular in the
construction of the network (phase 1). in the construction of the network
(phase 1). It will always be possible to obtain, from a vertex of from a
vertex of $V$, the associated variables of $V$ using the map between sets.
using the map between sets.

###  3.3 Causal graph simplification

La fase 2 (simplificación del grafo) recibe un archivo de texto plano con la
descripción de un grafo $G$ (listas de adyacencia, ver más arriba), y un
archivo con la matriz $M$ asociada. Devuelve un archivo de texto plano con el
grafo $G$ tras eliminar todos sus arcos espurios, redundantes, y eliminar u
orientar las aristas no dirigidas remanentes, dependiendo de la etapa, y según
los métodos propuestos en los epígrafes 2.5, 2.7, y 2.8, respectivamente.

Los archivos de entrada del grafo (a simplificar) y la matriz de muestra deben
especificarse como valores de la variables graph_simplifier_in y
graph_simplifier_
sample_in, respectivamente. El archivo de salida del grafo (simplificado) de
salida en graph_simplifier_out.

Un ejemplo de configuración puede ser el siguiente:

⬇

1 run_mode=Reichenbach&Mokken&Robustness

2

3 metric=H

4 threshold=0.5

5

6 graph_simplifier_in=graph_file.txt

7 graph_simplifier_sample_in=sample.txt

8 graph_simplifier_out=simplified_graph_file.txt

9 graph_simplifier_frequencies_in=frequencies.txt

The input variable graph_builder_frequencies_in is optional, and specifies the
input file for the vertex frequency listing. If not specified, the listing is
recalculated from the input matrix.

If the chaining of more than one stage of phase 2 is specified in run_mode
(e.g., using run_mode=Reichenbach&Mokken), then the output network of one
stage corresponds to the input network of the next stage. In that case, the
output file corresponds to the sequence of stages. By default, the network
resulting from any of the intermediate stages is not available at the end of
the calculation. If necessary, the network resulting from a specific stage can
be obtained by assigning the address of an output file to the variable named
<[value of run_mode corresponding to stage 2]_out>(e.g.,
Reichenbach_out=reichenbach_graph
_file.txt para la etapa 1 de la fase 2) for stage 1 of phase 2).

###  3.4 Modules and dependencies

The modules of the _CChains_ program are listed below, along with a brief
description of its content:

  * •

_Definitions_ : type definitions and class declarations that are used in the
rest of the modules. It has an iomanager submodule in which the _methods_ to
manage the program’s input and output files are defined.

  * •

_Metrics_ : _methods_ for calculating correlation or causality measures
(Loevinger’s coefficient, Pearson’s coefficient, and probabilistic causality
measures), as well as their dependencies (_methods_ for calculating
frequencies, frequencies of coincidences, among others)

  * •

_Sample compressor_ : $M$ matrix compression _method_.

  * •

_Graph auxiliary methods_ : auxiliary _methods_ for managing graphs, eg, the
_method_ to obtain the arcs of the graph, to obtain the undirected edges, to
eliminate arcs, to transpose the graph, among others.

  * •

_Graph builder_ : causal graph $G$ construction _method_.

  * •

_Graph simplifier_ : causal graph simplification modules.

    * –

_Reichenbach test_ : _method_ for eliminating spurious arcs.

    * –

_Mokken test_ : _method_ for eliminating redundant arcs.

    * –

_Robustness test_ : _method_ for eliminating remaining undirected edges.

  * •

_Sample generator_ : matrix generation module, to be used in the test module.
It generates matrices of three types: Guttman scale, randomly perturbed
Guttman scale, and double monotony Mokken scale. In all these cases, the
underlying graph is a linear causal chain.

  * •

_Test_ : module to evaluate the correctness of the algorithm in simple, self-
generated test cases, in which the resulting graph is known _a priori_. It
generates two types of matrices, from perturbations on a base matrix in which,
for every component $m_{ij}$, it is true that if $m_{ij}=1$ then $m_{i,j-1}=1$
and $m_{i+1,j}=1$. The perturbations are They are carried out completely
randomly for matrices of the first type, and with heuristic criteria for those
of the second type. On each of these matrices, a graph is built and simplified
with the proposed algorithm and the results obtained are evaluated, depending
on the type of matrix. The _Test_ module receives a set of its own parameters:

    * –

test_rows: number of rows of the test matrix to generate.

    * –

test_columns: number of columns of the test matrix to generate.

    * –

test_perturbation: probability of making a change (from 0 to 1, or from 1 to
0) in a component of the generated matrix. It is only applicable in the
construction of matrices of the first type.

    * –

test_cases: number of test cases.

    * –

magnitudes_to_check_out: file with monitoring magnitudes for each test case.
In particular, the fraction of arcs of the underlying graph that were
reproduced, the fraction of redundant arcs that were eliminated, and the
Mokken scalability coefficientMokken for the test matrix and its transpose are
evaluated.

The structure of modules and dependencies of the program responds to the
following diagram:

Figure 3.1: Diagram of dependencies between program modules

###  3.5 Implementation details

In this section, the algorithm used is introduced in general terms and its
performance is analyzed.

####  3.5.1 Construction

The graph is constructed as a list of adjacencies, since the graph is expected
to be sparse ($|E|<|V|\log|V|$) or, at least, to be sparse after the
simplification process. Although throughout the algorithm it will continually
be necessary to determine the existence of specific arcs within the graph, for
which an adjacency matrix is ideal, it is expected to work with a large number
of variables ($|V|\sim 10^{4}$), so represent $G$ as an adjacency matrix of
size $|V|\times|V|$ could compromise the performance of the algorithm in terms
of memory.

To construct the graph, it is necessary to calculate the value $H_{ij}$ for
all pairs of vertices of $G$. Therefore, the frequencies $\pi_{i}$ are
calculated for all vertices of the graph and stored in a list $\pi$, available
in several phases of the algorithm. Furthermore, the coincidence frequencies
$\pi_{ij}$ are calculated for each pair of vertices but only those
corresponding to arcs of $G$ are stored (ie, when $H_{ij}>H_{0}$). Therefore,
in the adjacency list of $i$, each arc (or undirected edge) $i\rightarrow j$
is represented as a pair $<j,\pi_{ij}>$. The structure of the adjacency lists
is similar to that which is usual in a weighted graph, although $G$ is not. In
any case, the analogue of a weight in the graph $G$ is not $\pi_{ij}$ but
$H_{ij}\leavevmode\nobreak\ \Theta(H_{ij}-H_{0})$.

A function $H(\pi_{ij},\pi_{i},\pi_{j})$ is defined that calculates the value
$H_{ij}$ for a pair of vertices $i$ and $j$ of $G$, and an arc $i\rightarrow
j$ is added to $G$ if the pair $(i,j)$ satisfies $\pi_{i}\leq\pi_{j}$ and
$H_{ij}>H_{0}$. Note that for pairs $(i,j)$, such that $\pi_{i}=\pi_{j}$ and
$H_{ij}>H_{0}$, an arc is added in both directions (undirected edges).

##### Pseudocode and time complexity

The following pseudocode reflects the algorithm for constructing the graph.
The input parameter $M$ is the base matrix, $\pi$ is the list of frequencies,
and $H_{0}$ is the threshold that the metric must exceed to determine the
presence of an arc between two vertices.

Data: $M,\pi,H_{0}$

Result: $G$

1 Function  _Build(_$M,\pi,H_{0}$_)_:

2

3 $G\leftarrow\text{empty graph}$

4 for  _$i,j$ in $V\times V$_ do

5

6 $\pi_{ij}\leftarrow$ calculate_pij(M, i, j)

7 if  _$i\neq j$ and $\pi_{i}\leq\pi_{j}$ and
$H(\pi_{ij},\pi[i],\pi[j])>H_{0})$_ then

8

9 add $i\rightarrow j,\pi_{ij}$ to $G$

10 end if

11

12 end for

13 return $G$

14

Algorithm 3.1 Graph construction algorithm

The function calcula_pij calculates the frequencies of coincidences $\pi_{ij}$
on the matrix $M$, in a number of operations that linearly depends on the
number of individuals. Therefore, it is $O(|I|)$. This operation is performed
once for each pair of vertices. Since they are a total of $|V|(|V|-1)$ ordered
pairs, and the rest of the operations are atomic, then the construction method
has a time complexity of $O(|I||V|^{2})$.

####  3.5.2 Spurious arcs

The Reichenbach_Test _method_ implements the spurious arc removal algorithm
proposed in 2.5. For each arc $i\rightarrow j$ of $G$, the parents common to
$i$ and $j$ are searched. Of these, we look for some parent $k$ that meets the
conditions $H_{ij|k}\leq H_{0}$ and $H_{ij|\neg k}\leq H_{0}$. If this is the
case, $i\rightarrow j$ is eliminated from $G$.

For convenience, the graph is transposed, so that each adjacency list of a
vertex contains all its parents instead of all its children. This decision
makes it easier to find the parents common to the ends of an arc $i\rightarrow
j$, finding the intersection of the adjacency lists of $i$ and $j$.

In accordance with the idea proposed in 2.5.1, the arcs are ordered by the
average frequency of their ends, and are visited in this order. As seen
therein, this resolves all conflicts between two triangles with shared sides,
except when the second leg of one of the triangles is the hypotenuse of the
other, and the second legs involved are of equal length. In this case, the
arcs to visit in each triangle have the same average frequency and the order
criterion is not valid. In this case, the arc with the highest correlation
between its extremes is taken first. Since conflicting arcs always share a
vertex, and non-sharing vertices have equal frequencies, for example
$j\rightarrow k$ and $l\rightarrow k$ in Fig.2.2(a), then the ordering of arcs
from highest to lowest correlation between vertices is reduced to an ordering
from highest to lowest frequency of coincidences

##### Pseudocode and time complexity

The following pseudocode reflects the algorithm for removing spurious arcs.
The parameters $M$, $\pi$, and $H_{0}$ are the same as in the previous
algorithm, while G is the graph to be simplified.

Data: $G,M,\pi,H_{0}$

Result: $G$

1 Function  _Reichenbach’s_Test(_$G,M,\pi,H_{0}$_)_:

2

3 $E\leftarrow E(G)$

4 Sort$(E,$ Compare $)$

5 for  _$i\rightarrow j$ in $E$_ do

6

7 for  _$k$ in common_parents$(i,j)$_ do

8

9 if  _Common_cause_principle $(M,\pi,H_{0},i\rightarrow j,k)$_ then

10

11 remove $i\rightarrow j,\pi_{ij}$ of $G$

12 end if

13

14 end for

15

16 end for

17

18

19

20 Function  _Compare(_$i\rightarrow j,l\rightarrow k$_)_:

21

22 if  _$\pi[i]+\pi[j]\neq\pi[l]+\pi[k]$_ then

23

24 return $\pi[i]+\pi[j]<\pi[l]+\pi[k]$

25 end if

26 return $\pi_{ij}>\pi_{lk}$

27

Algorithm 3.2 Algorithm for the elimination of spurious arcs

Where Common_cause_principle checks compliance with the conditions
$H_{ij|k}\leq H_{0}$ and $H_{ij|\neg k}\leq H_{0}$, calculating $H_{ij|k}$ y
$H_{ij|\neg k}$ in $O(|I|)$.

Ordering the arcs according to the proposed criterion is done in
$O(|E|log|E|)=O(|E|log|V|)$.

Subsequently, for each arc $i\rightarrow j$ of $E$, the common parents of $i$
and $j$ in $O(|V|)$ (intersection of the adjacency lists of $i$ and $j$) are
computed. Then, for each one, the conditions proposed in $O(|I|)$ are checked.
If the conditions are met, the arc is eliminated in $O(|V|)$ (although it may
be reduced to $O(|log|V|)$ if each adjacency list is implemented over an
ordered tree structure or a dictionary). Like one elimination operation is
performed for each arc of at most $O(\log|V|)$, these operations are in total
at most at most, these operations are in total $O(|E||V|)$.

Finally, the time complexity of the spurious arc removal algorithm is
$O(|E|log|V|+|E||V||I|)=O(|E||V||I|)$.

####  3.5.3 Redundant arcs

The Mokken_Test _method_ implements the proposed transitive arc elimination
algorithm. For each arc $i\rightarrow j$ of $G$, it finds all triangles
$(i,k,j)$ in which it is hypotenuse and check the conditions
$\pi_{ij}\leq\pi_{ik}\leq\pi_{jk}$ and $\pi_{\neg i\neg j}\geq\pi_{\neg i\neg
k}\geq\pi_{\neg j\neg k}$. If this is fulfilled, then $i\rightarrow j$ is
eliminated from $G$. Previously, the arcs are ordered as proposed in the
section 2.7.1, by length from longest to shortest and, in length from longest
to shortest, and, in case of equal length, from longest to shortest by
frequency of coincidences between their ends.

####  3.5.4 Pseudocode and time complexity

The following pseudocode reflects the algorithm for eliminating redundancy
arcs. The parameters $G$ and $\pi$ are the same as in the previous algorithm.

Data: $G,\pi$

Result: $G$

1 Function  _Mokken_Test(_$G,\pi$_)_:

2

3 $E\leftarrow E(G)$

4 Sort$(E,$ Compare $)$

5 for  _$i\rightarrow j$ en $E$_ do

6 Simplify_triangle$(G,i\rightarrow j)$

7 end for

8

9

10

11 Function  _Simplify_triangle(_$G,i\rightarrow j$_)_:

12

13 for  _$k$ in children$(i)$_ do

14

15 if  _exists $j\rightarrow k$ in $G$_ then

16 if  _Mokken_conditions $(G,i\rightarrow j)$_ then

17 remove $i\rightarrow j,\pi_{ij}$ of $G$ return

18 end if

19

20 end if

21

22 end for

23

24

25

26 Function  _Compare(_$i\rightarrow j,l\rightarrow k$_)_:

27

28 if  _$\mid\pi[i]-\pi[j]\mid$ $\neq$ $\mid\pi[l]-\pi[k]\mid$_ then

29

30 return $\mid\pi[i]-\pi[j]\mid$ $>$ $\mid\pi[l]-\pi[k]\mid$

31 end if

32 return $\pi_{ij}>\pi_{lk}$

33

Algorithm 3.3 Algorithm for the elimination of redundant arcs

Where Mokken_Conditions checks the fulfillment of the conditions
$\pi_{ij}\leq\pi_{ik}\leq\pi_{jk}$ and $\pi_{\neg i\neg j}\geq\pi_{\neg i\neg
k}\geq\pi_{\neg j\neg k}$, in $O(1)$. This is possible since $\pi_{ij}$,
$\pi_{ik}$, and $\pi_{jk}$ are stored in the corresponding arcs, and
$\pi_{\neg i\neg j}$, $\pi_{\neg i\neg k}$, y $\pi_{\neg j\neg k}$ can be
computed from these and the list $\pi$ (e.g., $\pi_{\neg i\neg
j}=1-\pi_{i}-\pi_{j}+\pi_{ij}$).

Ordering the arcs according to the proposed criterion is done in
$O(|E|log|E|)=O(|E|log|V|)$.

Subsequently, for each arc $i\rightarrow j$ de $E$, all the triangles where it
is hypotenuse are visited searching for all vertices $k$ children of $i$ that
are parents of $j$, in $O(|V|^{2})$ (although it can be reduced to
$O(|V|\log|V|)$ by implementing the adjacency lists over ordered tree
structures or dictionaries). Then, for each one, the conditions proposed in
$O(1)$ are checked .

Finally, the time complexity of the spurious arc elimination algorithm is
$O(|E|log|V|+|E||V|^{2})=O(|E||V|^{2})$.

####  3.5.5 Remaining undirected edges

The Robustness_Test _method_ implements the proposed undirected edge removal
algorithm. For each undirected edge $i\leftrightarrow j$, find the vertices
$i-1$ and $j-1$, to calculate the corresponding $\pi_{ii}$ and $\pi_{jj}$
values .

##### Pseudocode and time complexity

The following pseudocode reflects the algorithm for orienting or removing
remaining undirected edges. The parameters $G$ and $\pi$ are the same as in
the previous algorithm.

Data: $G,\pi,H_{0}$

Result: $G$

1 Function  _Robustness_Test(_$G,\pi,H_{0}$_)_:

2

3 for  _$i\rightarrow j$ in $E$_ do

4

5 switch  _Verify_robustness $(G,i\leftrightarrow j,M,\pi,H_{0})$_ do

6

7 case  _$1$_ do

8 remove $i\rightarrow j,\pi_{ij}$ of $G$

9 end case

10

11 case  _$2$_ do

12 remove $i\leftarrow j,\pi_{ij}$ of $G$

13 end case

14

15 case  _$3$_ do

16 remove $i\leftrightarrow j,\pi_{ij}$ of $G$

17 end case

18

19 end switch

20

21 end for

22

23

24

25 Function  _Verify_robustness(_$G,i\leftrightarrow j,\pi,H_{0}$_)_:

26

27 $\pi_{ii}\leftarrow$ Calculate_pii$(G,i\rightarrow j,\pi,H_{0})$

28 $\pi_{jj}\leftarrow$ Calculate_pii$G,i\leftarrow j,\pi,H_{0}$

29 if  _$\pi_{i,i-1}==-\infty$ or $\pi_{j,j-1}==-\infty$_ then

30 return $0$

31 end if

32

33 return Robustness_conditions$(\pi[i],\pi[j],\pi_{ii},\pi_{jj},\pi_{ij})$

34

35

36 Function  _Calculate_pii(_$G,i\rightarrow j,\pi,H_{0}$_)_:

37

38 $\pi_{ii}\leftarrow-\infty$; $\pi_{i,i-1}\leftarrow-\infty$;
$\pi_{i-1}\leftarrow-\infty$

39 for  _$k$ in parents$(i)$_ do

40

41 if  _$k\neq j$_ then

42

43 if  _$\pi_{i,i-1} <\pi_{i,k}$_ then

44

45 $\pi_{i-1}=\pi[k]$

46 $\pi_{i,i-1}=\pi_{ik}$

47 $\pi_{ii}=\pi[i]*\pi{i,i-1}/\pi_{i-1}$

48 else

49 if  _$\pi_{i,i-1}==\pi_{ik}$ and $\pi_{i-1}<\pi[k]$_ then

50

51 $\pi_{i-1}=\pi[k]$

52 $\pi_{ii}=\pi[i]*\pi_{i,i-1}/\pi[k]$

53 end if

54

55 end if

56

57 end if

58

59 end for

60

61 return $\pi_{ii}$

62

Algorithm 3.4 Algorithm for orienting or eliminating undirected edges

Where Robustness_Conditions checks compliance with the robustness conditions
proposed in section 2.8 by performing the necessary algebraic calculations, in
$O(1)$. Returns an integer value indicating the arc that should be removed
(eg, $i\rightarrow j$, $i\leftarrow j$ or the entire edge $i\leftrightarrow
j$).

The time complexity depends on the operations to find $i-1$ and $j-1$, which
is performed once for each undirected edge, and is bounded by $|V|$. Since the
number of undirected edges is at most $|E|$, then the method is $O(|V||E|)$.

Consequently, the time complexity of the CChains algorithm is the sum of the
time complexities of each of its phases, i.e.,
$O(|I||V|^{2})+O(|E||V||I|)+O(|E||V|^{2})+O(|V||E|)$, which, in the expected
case $|V|\leq|E|$ is reduced to
$O(\max(|E||V||I|,|E||V|^{2}))$.

##  Chapter 4 Results

####  4.0.1 Problem

Nowadays, scientific-technical developments make it possible to collect large
amounts of data in different contexts. In particular, in the field of biology,
the human genome project (active from 1990 to 2003) recorded the complete
genetic code of man.PGH Numerous databases are publicly available for
researchers in the field to consult in order to find the mechanisms at work in
certain phenomena, as well as to test models and theories that might explain
them. Many of these repositories are associated with intrinsically causal
processes. For example, in the case of the database The Cancer Genome Atlas,
an enormous amount of information is stored on mutation and gene expression
profiles that could reveal the genetic origin of cancer, and indicate
strategies to detect and treat it.TCGA In the latter case, although
significant progress has been made in describing groups of cancer-correlated