A graphoid is a set of statements of the form, "''X'' is irrelevant to ''Y'' given that we know ''Z''" where ''X'', ''Y'' and ''Z'' are sets of variables. The notion of "irrelevance" and "given that we know" may obtain different interpretations, including
probabilistic
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, ...
,
relational and correlational, depending on the application. These interpretations share common properties that can be captured by paths in graphs (hence the name "graphoid"). The theory of graphoids characterizes these properties in a finite set of
axioms
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
that are common to informational irrelevance and its graphical representations.
History
Judea Pearl and
Azaria Paz coined the term "graphoids" after discovering that a set of axioms that govern
conditional independence
In probability theory, conditional independence describes situations wherein an observation is irrelevant or redundant when evaluating the certainty of a hypothesis. Conditional independence is usually formulated in terms of conditional probabil ...
in
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
is shared by
undirected graphs. Variables are represented as nodes in a graph in such a way that variable sets ''X'' and ''Y'' are independent conditioned on ''Z'' in the distribution whenever node set ''Z'' separates ''X'' from ''Y'' in the graph. Axioms for conditional independence in probability were derived earlier by
A. Philip Dawid and
Wolfgang Spohn.
The correspondence between dependence and graphs was later extended to
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...
s (DAGs)