그래포이드

이 글은 고아로, 다른 어떤 기사도 그것에 연결되지 않는다.관련 문서에서 이 페이지에 대한 링크를 소개하고, 제안사항을 보려면 링크 찾기 도구를 사용하십시오.(2014년 9월)

graphhoid는 "X는 우리가 Z를 안다는 점에서 Y와는 무관하다"라는 형식의 문장으로, 여기서 X, Y, Z는 변수 집합이다."비선진성"과 "우리가 아는 바와 같이"의 개념은 적용에 따라 확률론적, 관계적, 상관관계를 포함하여 서로 다른 해석을 얻을 수 있다.이러한 해석은 그래프에서 경로로 캡처할 수 있는 공통 속성을 공유한다("그래프호이드"라는 이름을 사용).그래포이드 이론은 정보의 비합리성과 그 그래픽적 표현에 공통적인 공리의 유한 집합에서 이러한 성질을 특징짓는다.

역사

유대 펄과 아자리아 파즈는^[1] 확률론에서 조건부 독립성을 지배하는 일련의 공리들이 비방향 그래프에 의해 공유된다는 것을 발견하고 "그래프호이드"라는 용어를 만들었다.변수는 변수 집합 X와 Y가 그래프에서 X와 Y를 구분할 때마다 분포에서 Z에서 독립적으로 조건화되도록 그래프에 노드로 표시된다.확률의 조건부 독립성에 대한 공리는 A에 의해 앞서 도출되었다. 필립 도이드와^[2] 볼프강 스펀.^[3]의존성과 그래프 사이의 대응은 나중에 지시된 반복 그래프(DAG)^[4][5][6]와 다른 의존성 모델로 확장되었다.^[1][7]

정의

종속성 모델 M은 세 쌍둥이(X,Z,Y)의 하위 집합이며, 여기서 조건 I(X,Z,Y):X는 주어진 Z에 독립적이다.graphhoid는 다음의 다섯 가지 공리에서 닫히는 종속성 모델로 정의된다.

1. 대칭: I${\displaystyle }$( ${\displaystyle X}$, ${\displaystyle Z}$, ${\displaystyle Y}$) ${\displaystyle \iff }$ ${\displaystyle I}$(${\displaystyle Y}$, ${\displaystyle Z}$, ${\displaystyle X}$) ${\displaystyle I (X,Z,Y)\$왼쪽 오른쪽 $화살표$I ($Y,Z,X)}$
2. 분해: Y W) )& I W) $\\displaystyle I (X,Z,Y\컵 W)\Rightarrow I (X,Z,Y)\&I (X,Z,W)$
3. 약한 유니언: ${\displaystyle I}$ ${\displaystyle (X}$ ${\displaystyle ,}$ ${\displaystyle Z}$, ${\displaystyle Y}$ ${\displaystyle \cup }$ W${\displaystyle }$) ${\displaystyle \Rightarrow }$ I${\displaystyle }$(${\displaystyle X}$, ${\displaystyle Z}$ ${\displaystyle \cup }$ W${\displaystyle }$, Y${\displaystyle }$) ${\displaystyle$ I $(X,Z,Y\컵 W)\Rightarrow$ I $(X,Z\컵 W,Y)}$
4. Contraction: ${\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}$
5. Intersection: ${\displaystyle I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}$

반그래프호이드는 1-4로 닫힌 의존성 모델이다.이 다섯 가지 공리는 모두 그래프로이드 공리로 알려져 있다.^[8]직관적으로, 약한 결합과 수축 속성은 관련 없는 정보가 시스템의 다른 명제의 관련성 상태를 변경해서는 안 된다는 것을 의미한다. 관련성이 있는 것은 관련성이 있고 관련성이 없는 것은 관련성이 없다.^[8]

그래핀의 종류

확률형 그래핀^[1][7]

조건부 독립성, 다음과 같이 정의된다.

${\displaystyle I(X,Z,Y)\왼쪽 오른쪽 화살표 P(X\mid Y,Z)=P(X\mid Z)}$

p가 엄격히 양성일 때 완전한 그래핀이 되는 반그래프호이드다.

상관 그래포이드^[1][7]

의존성 모델은 상관관계 그래프 입니다. 만약 우리가 어떤 확률함수를 가지고 있다면,

${\displaystyle I_{c}(X,Y,Z)\좌우타로우 \rho _{xy.z}=0{\text{{}} 매 }x\in X{\text{ 및 }y\in Y}$

여기서 $\rho {\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle y_{}}$. z ${\$$z}}$은 x와 y의 주어진 집합 Z 사이의 편상관이다.

즉, Z에 대한 측정을 사용한 X에 있는 변수의 선형 추정 오차는 Y에 있는 변수의 측정을 더해도 줄어들지 않으므로 Y는 X의 추정과 무관하게 된다. 상관관계 및 확률적 종속성 모델은 정규 분포에 대해 일치한다.

관계그래프자리^[1][7]

종속성 모델은 만족하는 경우 관계형 그래프로 표시된다.

$#\디스플레이스타일 P(X,Z)0~\&~P(Y,Z)0\implies P(X,Y,Z)0.}$

즉, 일단 Z가 고정되면 X에 허용되는 값의 범위는 Y의 선택에 의해 제한되지 않는다.이 모델에 속하는 독립성 문장은 데이터베이스의 내장형 다중값 종속성(EMVD s)과 유사하다.

그래프유발그래프

만일 다음과 같은 방향성이 없는 그래프 G가 존재한다면,

${\displaystyle I(X,Z,Y)\왼쪽 오른쪽 화살표 \langle X,Z,Y\rangele _{G}}$

그래핀을 그래프로 유도한다고 한다.즉, M의 모든 독립성문이 G의 정점 분리로서 반영되고 그 반대의 경우도 마찬가지인 비방향 그래프 G가 존재한다.종속성 모델이 그래프에 의한 그래포이드가 되기 위해 필요하고 충분한 조건은 대칭성, 분해성, 교차성, 강한 결합성, 전이성 등의 공리를 만족한다는 것이다.

강한 연합은 다음과 같이 말한다.

${\displaystyle I(X,Z,Y)\implies I(X,Z\컵 W,Y)}$

Transitivity는 다음과 같이 말한다.

${\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\컵 Y\cup Z,~~I(X,Z,\gamma ){\text{ 또는 }}}}$

공리는 대칭, 분해, 교차점, 강한 결합, 그리고 전이성이 비방향 그래프의 완전한 특성화를 구성한다.^[9]

DAG 유도 그래핀

A graphoid is termed DAG-induced if there exists a directed acyclic graph D such that ${\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}}$ where ${\displaystyle \langle X,Z,Y\rangle _{D}}$ stands for d-separation in D. d-separation (d-connotes "directional") extends 방향 지정되지 않은 그래프에서 지시된 반복 그래프까지의 정점 분리 개념.베이지안 네트워크 구조에서 조건부 독립성을 읽을 수 있도록 허용한다.그러나 DAG의 조건부 독립성은 유한한 공리 집합으로 완전히 특성화할 수 없다.^[10]

포함 및 시공

그래프와 DAG에 의한 그래핀은 둘 다 확률론적 그래핀에 포함되어 있다.^[11]즉, 모든 그래프 G에 대해 P의 모든 조건부 독립성이 G로 표시되도록 확률 분포 P가 존재하며, 그 반대의 경우도 마찬가지다.DAG도 마찬가지다.단, 그래핀이 아닌 확률론적 분포가 있으며, 더욱이 확률론적 조건부 의존성에 대해서는 유한한 공리화가 없다.^[12]

토마스 베르마는 모든 반그래프호이드는 모든 d-분리가 유효한 DAG를 재귀적으로 구성하는 방법을 가지고 있다는 것을 보여주었다.^[13]이 구조는 베이즈 네트워크에서 사용되는 구조와 유사하며 다음과 같이 진행된다.

1. 변수를 임의의 1, 2, ..., i, ..., ..., N 순서로 배열하고, i = 1로 시작하여
2. 각 노드 i에 대해 노드 PA_i 집합을 선택하여 PA에_i 조건이 지정된 모든 이전 노드 1, 2, ...,i - 1에 대해 독립적이다.
3. PA에서_i i로 화살표를 그리고 계속하십시오.

이 건설에 의해 만들어진 DAG는 건설에 사용된 것들로부터 따르는 모든 조건부 독립성을 나타낼 것이다.또한 DAG에 표시된 모든 d-분리는 구성에 사용되는 그래프로이드에서 유효한 조건부 독립성이 될 것이다.

참조