PGM_Undirected#2

Undirected Graph 중에 Conditional Independence Graph는 그래프 노드는 정규분포를 따른다고 가정한다. 그 분포를 최대값으로 추정하는 공분산의 역행렬을 (Precision Matrix) 를 추정하기 위하여 미분한 것이 0이 되는 수식을 지난 시간에 배웠다. 그리고 Sparsity를 위해 라쏘 패널티를 추가하였다. ρi,j\rho_{i,j} 는 precision matirx 의 entry 이다.

λ∑I=1∣ρi,j∣\lambda \sum_{I=1}|\rho_{i,j}|

그럼 이제 문제는 위 식을 푸는 것이다. maximization 최적화 문제인 것이다. 하지만, 단변량일때는 풀면 되는데, 그래프의 노드는 많고 다변량을 풀때에는 컴퓨터 시간 복잡도라는 개념이 생긴다.

  • Interioir-point Optimization Methods (내부 점 최적화): Yuan and Lin(2007), Banerjee and others (2007), Dahl and others (2007)

  • Coordinate Descent Algorithm, Graphical Lasso : Friedman, J., etal(2008) - 스탠포드 교수

  • Regression Approach : M

고차원 방법에 대한 문제이기 때문에 Undirected Graph에서 Precision Matirx를 추정하는 방법중에 "Graphical Lasso"가 가장 유명하다.

Generate Data based on Netwrok Structure!

네트워크 구조를 생각한 후, 데이터를 생성해야 한다.

  • Random Network : 대각선 아래를 0 또는 값을 랜덤하게 배정한다면 계층적 구조를 유지한 랜덤 네트워크를 선택할 수있다.

Xi=∑j∈pajaijXj+ZiX_i = \sum_{j\in pa_j}a_{ij}X_j+Z_i

Hierachical Ordering 네트워크에서 가장 상위에 있는 노드를 Ancestor 라고 한다. X1, X2, X3, X4 가 높은 계층 순으로 순차적으로 나열되어 있다할때, 대각선(Upper Diagonal) 위 계수를 0으로 채우고, 대각선 아래(Lower Diagonal)의 계수를 상수 또는 0으로 랜덤하게 채우면 Hierachical Ordering 을 유지한채 랜덤 네트워크를 생성할 수 있다.

  • Hub Network : 30% 이상의 노드들이 허브이며, 허브의 Degree가 평균 Degree 를 초과하는 네트워크이다.

꼭 30% 가 아니어도 된다. 예) 상위 25%에 해당하는 엔트리만 0 또는 랜덤하게 주면 상대적으로 높은 계층의 있는 노드의 Out-Degree에 밀집되게 되므로 허브가 되게 된다. (row=>parent, column=>child)

  • Scale-free Network

차수(간서의 수)의 분포가 지수분포 멱법칙(Power of Law)을 따르는 네트워크를 Scale-Free 네트워크라고 한다. Degree가 많은 노드는 적고, Degree가 적은 노드는 많다. (위키피디아)

  • Band-type Network

----> Lecture PPT2

Graphical Lasso 를 Precision Matrix 를 추정하여야 하기 때문에 고차원 데이터에 적용하기에 어렵다. Regression-based Approach 는 시간 복잡도 문제를 해결할 수 있다.

질문. Graphical Lsso 에도 Lasso 가 들어가는데 뭐가 문제이지?

Lasso-based Approach (Tibshirani, 1996)

y 에 영향을 주는 변수 선택을 하는데, 계수 β\beta 가 0 이 아니면 변수 선택을 한다.

argminβ∣∣Y−Xjβ∣∣22+λ∣∣β∣∣1argmin_{\beta}||Y-X_j\beta||_2^2 +\lambda||\beta||_1

타겟 노드는 종속변수라 하고, 타겟노드를 제외한 노드는 독립변수라고 한다. 0이 아닌 계수에 대해서는 probabilistic neighbors 관계가 형성된다. 람다값이 커지면, 많은 계수들이 0으로 되고, 람다값이 작아지면, 상수값의 계수가 많아진다.

Disadvantage of Lasso-based Approach

  • 오라클 속성이 없다.

    • 오라클 속성 중 하나는 Consistency in variable Selection이다. 일반적인 상황에서는 이것을 만족하지 않는다.

  • 다중공정성 문제

minE(E(Y)−∑iβ′Xi)2min E(E(Y)-\sum_i\beta'X_i)^2

Prediction oracle solution

선형 모델에서는 라쏘와 크로스 벨리데이션이 만족시킨다.

Consistency in variable Selection

P(M′=M∗) −>1 for n−>∞P(M'=M*)\ ->1\ for \ n -> \infty

샘플 데이터가 무한대로 갈수록 모델 이 실제 추정한 변수가 실제 시스템 변수와 같아질 확률이 1이다.

SCAD, MCP, Adaptive Lasso 가 만족시킨다.

PreviousPGM_Undirected#1NextPGM_Undirected #2,3 R 실습

Last updated