Grafóide

Um grafóide é um conjunto de sentenças da forma "X é irrelevante para Y dado que conhecemos Z", onde X, Y e Z são conjuntos de variáveis. A noção de "irrelevância" e "dado que conhecemos" pode ser vista de diferentes interpretações, incluindo probabilística, relacional e correlacional, dependendo da aplicação. Essas interpretações compartilham propriedades comuns que podem ser capturadas por caminhos em grafos (daí o nome "grafóide"). A teoria dos grafóides caracteriza essas propriedades em um conjunto finito de axiomas que são comuns a irrelevância informativa e suas representações gráficas.

História

Judea Pearl e Azaria Paz cunharam o termo "grafóides" depois de descobrirem que um conjunto de axiomas que regem uma Independência condicional na teoria da probabilidade é compartilhada por grafos não-direcionados. As variáveis são representadas como nós em um gráfico de tal forma que os conjuntos de variáveis X e Y são condicionados independentemente de Z na distribuição, sempre que o conjunto de nós Z separa X de Y no gráfico. Axiomas para independência condicional na probabilidade foram obtidos anteriormente por A. Philip Dawid e Wolfgang Spohn. A correspondência entre a dependência e gráficos mais tarde foi estendida para grafos acíclicos direcionados (DAGs) e outros modelos de dependência.

Definição

Um modelo de dependência M é um subconjunto de trigêmeos (X,Z,Y) para os quais o predicado I(X,Z,Y): X é independente de Y dado Z, é verdade. Um grafóide é definido como um modelo de dependência fechado sob os seguintes cinco axiomas:

1. Simetria: $I(X,Z,Y)\Leftrightarrow I(Y,Z,X)$
2. Decomposição: $I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)$
3. União fraca: $I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)$
4. Contração: $I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)$
5. Intersecção: $I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)$

Um semi-grafóide é um modelo de dependência fechado sob (i)–(iv). Estes cinco axiomas juntos são conhecidos como o "axiomas grafóides" Intuitivamente, as propriedades de união fraca, e contração, significam que informações irrelevantes não devem alterar o estado de relevância de outras proposições no sistema; o que era relevante continua a ser relevante e o que era irrelevante continua irrelevante.

Tipos de grafóides

Grafóides probabilísticos

A independência condicional definida como

$I(X,Z,Y){\text{ iff }}P(X\mid Y,Z)=P(X\mid Z)$

é um semi-grafóide que se torna grafóide quando P é estritamente positivo.

Grafóides correlacionais

Um modelo de dependência é um grafóide correlacional se em alguns função de probabilidade, temos,

$I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ for every }}x\in X{\text{ and }}y\in Y$

onde $\rho _{xy.z}$ é a correlação parcial entre x e y dado o conjunto Z.

Em outras palavras, o erro de estimativa linear das variáveis em X usando medições de Z não seria reduzido pela adição de medições das variáveis de Y, tornando Y irrelevante para a estimativa de X. Modelos de dependência correlacional e probabilísticos coincidem para distribuições normais.

Grafóides relacionais

Um modelo de dependência é um grafóide relacional se ele satisfaz

$P(X,Z)>0~\&~P(Y,Z)>0\implies P(X,Y,Z)>0.$

Em palavras, o intervalo de valores permitidos para X não é restringido pela escolha de Y, uma vez que Z é fixo.  As declarações de independência pertencentes a este modelo são semelhantes  a dependências multivaloradas incorporadas (EMVD s) em bancos de dados.

Graphoides grafo-induzido

Se existe um grafo não direcional G , tal que,

$I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{G},$

Assim, o grafóide chamado de grafo-induzido. Em outras palavras, existe um grafo não direcionado G tal que cada declaração de independência, em M é reflectida como uma separação de vértices em G e vice-versa. Uma condição necessária e suficiente para um modelo de dependência ser um grafóide grafo-induzido é que ele satisfaz os seguintes axiomas: simetria, decomposição, intersecção, união forte e transitividade.

União forte afirma que,

$I(X,Z,Y)\implies I(X,Z\cup W,Y)$

Transitividade afirma que

$I(X,Z,Y)\implies I(X,Z,\gamma ){\text{ or }}I(\gamma ,Z,Y)~~\forall ~~\gamma \notin X\cup Y\cup Z.$

Os axiomas grafóides constituem uma caracterização completa de grafos não direcionados.

grafóides DAG-induzido

Um grafoid é chamado de DAG-induzido, se existe um grafo acíclico direcionado D tal que $I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}$ onde $\langle X,Z,Y\rangle _{D}$ está para d-separação em D. d-separação (d-conota "direcional") estende a noção de separação de vértices de grafos não direcionados para grafos acíclicos direcionados. Isso permite a leitura de independências condicionais a partir da estrutura da Rede bayesiana. Entretanto, as independências condicionais em um DAG não podem ser completamente caracterizado por um conjunto finito de axiomas.

Inclusão e construção

Grafóides gráfico-induzido e DAG-induzido são ambos contidos nos grafóides probabilísticos. Isto significa que, para cada grafo G , existe uma distribuição de probabilidade P de tal forma que cada independência condicional em P é representada em G, e vice-versa. O mesmo é verdadeiro para os DAGs. No entanto, existem distribuições probabilísticas que não são semi-grafóides e, além disso, não há axiomatização finita para dependências probabilísticas.

Thomas Verma, mostrou que a cada semi-grafóide existe uma forma recursiva de construir um DAG na qual cada d-separação é válida. A construção é semelhante ao utilizado em redes de Bayes e segue da seguinte forma:

1. Organize as variáveis em uma ordem arbitrária 1, 2, ..., i, ..., N e, comece com i = 1,
2. escolha para cada nó i um conjunto de nós PA_i tal que i seja independente de todos os seus antecessores, 1, 2,...,i − 1, condicionados em PA_i.
3. Desenhe setas de PA_i para i e continue.

O DAG criado por esta construção representará todas as independências condicionais que se seguem daquelas usadas na construção. Além disso, cada d-separação mostrada no DAG será uma independência condicional válida no grafóide utilizado na construção.