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: Simetria: Decomposição: União fraca: Contração: Intersecção: 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
é 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,
onde é 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
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,
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,
Transitividade afirma que
Os axiomas grafóides constituem uma caracterização completa de grafos não direcionados.A. Paz, J. Pearl, and S. Ur, "A New Characterization of Graphs Based on Interception Relations" Journal of Graph Theory, Vol. 22, No. 2, 125-136, 1996.
grafóides DAG-induzido Um grafoid é chamado de DAG-induzido, se existe um grafo acíclico direcionado D tal que onde 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: Organize as variáveis em uma ordem arbitrária 1, 2, ..., i, ..., N e, comece com i = 1, escolha para cada nó i um conjunto de nós PAi tal que i seja independente de todos os seus antecessores, 1, 2,...,i − 1, condicionados em PAi. Desenhe setas de PAi 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.
Referências
Categoria:Lógica Categoria:Teoria das probabilidades