Grafóide

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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[editar | editar código-fonte]

Judea Pearl e Azaria Paz[1] 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[2] e Wolfgang Spohn.[3] A correspondência entre a dependência e gráficos mais tarde foi estendida para grafos acíclicos direcionados (DAGs)[4][5][6] e outros modelos de dependência.[1][7]

Definição[editar | editar código-fonte]

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:
  2. Decomposição:
  3. União fraca:
  4. Contração:
  5. 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"[8] 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.[8]

Tipos de grafóides[editar | editar código-fonte]

Grafóides probabilísticos[1][7][editar | editar código-fonte]

A independência condicional definida como

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

Grafóides correlacionais[1][7][editar | editar código-fonte]

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[1][7][editar | editar código-fonte]

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[editar | editar código-fonte]

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.[9]

grafóides DAG-induzido[editar | editar código-fonte]

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. [10]

Inclusão e construção[editar | editar código-fonte]

Grafóides gráfico-induzido e DAG-induzido são ambos contidos nos grafóides probabilísticos.[11] 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. [12]

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.[13] 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 PAi tal que i seja independente de todos os seus antecessores, 1, 2,...,i − 1, condicionados em PAi.
  3. 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[editar | editar código-fonte]

  1. a b c d e Pearl, Judea; Paz, Azaria (1985). «Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations» 
  2. Dawid, A. Philip (1979). «Conditional independence in statistical theory». Journal of the Royal Statistical Society, Series B (Methodological): 1–31 
  3. Spohn, Wolfgang (1980). «Stochastic independence, causal independence, and shieldability». Journal of Philosophical Logic. 9: 73–99. doi:10.1007/bf00258078 
  4. Pearl, Judea (1986). «Fusion, propagation and structuring in belief networks». Artificial Intelligence. 29 (3): 241–288. doi:10.1016/0004-3702(86)90072-x 
  5. Verma, Thomas; Pearl, Judea (1988). «Causal networks: Semantics and expressiveness». Proceedings of the 4th Workshop on Uncertainty in Artificial Intelligence: 352–359 
  6. Lauritzen, S.L. (1996). Graphical Models. Oxford: Clarendon Press 
  7. a b c d Geiger, Dan (1990). «Graphoids: A Qualitative Framework for Probabilistic Inference» (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles) 
  8. a b Pearl, Judea (1988). Probabilistic reasoning in intelligent systems: networks of plausible inference. [S.l.]: Morgan Kaufmann 
  9. 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.
  10. Geiger, D. (1987). «The non-axiomatizability of dependencies in directed acyclic graphs» (PDF). UCLA Computer Science Tech Report R-83 
  11. Geiger, D.; Pearl, J. (1993). «Logical and algorithmic properties of conditional independence and graphical models». The Annals of Statistics. 21 (4): 2001–2021. doi:10.1214/aos/1176349407 
  12. Studeny, M. (1992). Kubik, S.; Visek, J.A., eds. «Conditional independence relations have no finite complete characterization». Dordrecht: Kluwer. Information Theory, Statistical Decision Functions and Random Processes. Transactions of the 11th Prague Conference. B: 377–396 
  13. Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, T.S.; Kanal, L.N., eds. «Causal Networks: Semantics and Expressiveness». Elsevier Science Publishers. Uncertainty in AI 4: 69–76