ML Note

합/곱 알고리즘 (sum - product Algorithm) (tistory.com) 합/곱 알고리즘 (sum - product Algorithm) 인자 그래프 (tistory.com) 인자 그래프 그래프 모델의 추론 알고리즘을 알아보기 전에 이를 이해하는 데 필요한 새로운 형태의 그래프인 인자 그래프(factor graph)에 대해 알아보자. 인자 그래프는 각 mldiary.tistory.com 합/곱 알고리즘은 인자 그래프로 표현된 p(x)를 바탕으로 변수들에 대한 분포를 구할 수 있다. 그러나 우리는 종종 ¹가장 높은 확률을 가지는 변수들의 설정과, 그 ²해당 확률값을 알고싶을 때가 있다. 이를 구하기 위한 알고리즘이 최대 합 알고리즘이다. 이를 구하기 위해 가장 먼저 해볼 수 있는 생각이 합/곱..

인자 그래프 (tistory.com) 인자 그래프 그래프 모델의 추론 알고리즘을 알아보기 전에 이를 이해하는 데 필요한 새로운 형태의 그래프인 인자 그래프(factor graph)에 대해 알아보자. 인자 그래프는 각각의 인자를 기준으로 그래프를 나 mldiary.tistory.com 위의 글에서 소개한 인자 그래프를 바탕으로 트리 구조 그래프에 적용할 수 있는 강력한 추론 알고리즘인 합/곱 알고리즘(sum-product algorithm)에 대해 알아보자. 합/곱 알고리즘 먼저 특정 변수 노드 x의 주변값 p(x)를 구하는 문제를 고려해 보자. 지금은 모든 변수들이 은닉 변수 즉, 관측되지 않았다고 가정하자. x를 제외한 모든 변수에 대한 결합 분포를 합산하여 주변 분포를 구할 수 있다. 여기서 x\x는..

그래프 모델의 추론 알고리즘을 알아보기 전에 이를 이해하는 데 필요한 새로운 형태의 그래프인 인자 그래프(factor graph)에 대해 알아보자. 인자 그래프는 각각의 인자를 기준으로 그래프를 나타낸 것이다. 예시는 다음과 같다. 위의 그래프는 인자 그래프로 얼핏 보면 비방향성 그래프와 비슷하지만 이와는 달리 작은 사각형이 포함되어 있다. 이 사각형이 '인자'이며, 인자는 변수들의 관계로 인해 생성된다. 위의 그래프를 결합 분포로 적으면 다음과 같다. 위의 식에서 fa는 x1, x2사이의 관계에 대해 나타내는 인자이며, fb도 마찬가지이다. fc는 x2와 x3의 관계, fd는 x3에 대한 함수이다. 만약 위의식을 비방향성 그래프로 나타냈다면, fa와 fb는 합쳐져 x1, x2의 포텐셜 함수로, fc,와..

앞에서 알아본 그래프 모델을 통해 추론 문제를 해결해 볼 것이다. 여기서는 사슬 형태를 가지는 그래프에서의 추론 문제를 볼 것이다. 사슬 모양 그래프는 다음과 같다. 위 그래프의 결합 분포는 다음 형태를 띈다. N개의 노드들이 각각 K개의 상태를 가지는 이산 변수를 표현한다고 가정하자. 이 경우 포텐셜 함수는 K * K 행렬을 구성하게 되므로 총 (N-1)K^2 개의 매개 변수를 가지게 된다. 이제 관측된 값이 하나도 없을 때 p(xn)을 구하는 법을 알아보자. 이는 다음과 같이 xn을 제외한 모든 변수의 합산을 통해 구할 수 있다. 이 경우 결합 분포는 가능한 x값 하나에 대해 하나씩의 숫자들의 집합으로 표현할 수 있다. 각각 K개의 상태를 가지는 변수가 N개이기 때문에 총 가능한 x의 값은 K^N개이..

비방향성 그래프, 방향성 그래프 변환 지금까지 확률 분포를 표현하기 위해 방향성 그래프와 비방향성 그래프에 대해 알아 보았다. 이제 두 그래프의 연관성에 대해 알아보자. 일단 첫 번째로 방향성 그래프를 이용해 명시된 모델을 비방향성 그래프로 변환하자. 첫 번째 예시로 다음을 고려해보자. 이를 그래프로 표현하면 다음과 같다. 이 비방향성 그래프에서 최대 클리크는 단순히 인접한 노드들의 쌍에 해당하기 때문에 위와 같이 비방향성 그래프가 표현되었다. 이를 결합분포로 다음과 같이 확인할 수 있다. 여기서 각각의 포텐셜함수는 다음과 같이 정의된다. 이렇게, 방향성 그래프의 조건부 확률을 비방향성 그래프의 클리크 활성화 함수로 매칭할 수 있으면 변환이 가능하다. 역도 마찬가지이다. 이를 만족시키기 위해서는 각 조건..

이진 이미지에서 노이즈를 제거하는 예시를 바탕으로 비방향성 그래프의 적용에 대해 살펴보자. 노이즈가 포함된 관측된 이미지를 이진 픽셀값 yi ∈ {−1, +1}들의 배열로 표현해 보자. 이때 i = 1, ... ,D는 모든 픽셀들에 대한 인덱스다. 깨끗한 원본 이미지가 있고(왼쪽 상단), 여기서 모든 픽셀을 10%의 확률로 뒤집는다고 하자(오른쪽 상단). 우리는 yi를 바탕으로 원본 이미지 xi를 추측해야 한다. 노이즈의 정도가 크지 않으므로 xi, yi 사이에 강한 상관관계가 있음을 알 수 있다. 또한 서로 근처에 있는 xi와 xj도 큰 상관관계를 가지는 것을 알 수 있다. 이러한 사전 지식을 바탕으로 위의 이미지를 마르코프 무작위장으로 나타낼 수 있다. 이 그래프는 두 종류의 클리크를 가지고 있다. ..

마르코프 무작위장(Markov random field)은 노드와 링크로 구성되어 있다는 점에서 베이지안 네트워크와 비슷하나, 이와는 달리 방향성이 없는 링크를 가지고 있어 비방향성 그래프 모델(undirected graphical model)이라고도 불린다. 마르코프 무작위장을 이해하기 위해 먼저 조건부 독립 성질부터 알아보자. 조건부 독립 성질 조건부 독립(conditional independence) (tistory.com) 조건부 독립(conditional independence) 여기서는 확률 분포에서 중요한 개념인 조건부 독립(conditional independence)에 대해 알아본다. 세 개의 변수 a, b, c를 고려해 보자. 다음과 같은 식이 있다. 변수 a가 b, c가 주어진 상황과 ..

조건부 독립(conditional independence) (tistory.com) 조건부 독립(conditional independence) 여기서는 확률 분포에서 중요한 개념인 조건부 독립(conditional independence)에 대해 알아본다. 세 개의 변수 a, b, c를 고려해 보자. 다음과 같은 식이 있다. 변수 a가 b, c가 주어진 상황과 c만 주어진 mldiary.tistory.com 위 글에서 살펴본 방향성 그래프에서 조건부 독립 성질을 확장시켜 d 분리에 대해 알아보자. 일반적인 방향성 그래프를 가정해 보자. 이때 A, B, C는 서로 겹치지 않는 임의의 노드 집합이다. 주어진 방향성 비순환 그래프로부터 다음이 유추될 수 있는 지 알고싶다고 하자. 이를 위해 A의 아무 노드로부..

여기서는 확률 분포에서 중요한 개념인 조건부 독립(conditional independence)에 대해 알아본다. 세 개의 변수 a, b, c를 고려해 보자. 다음과 같은 식이 있다. 변수 a가 b, c가 주어진 상황과 c만 주어진 상황에서 같은 값을 가진다. 이는 다시 말해, c가 주어진 상황에서 b가 주어져도, 안주어져도 같은 값을 가진다는 것 즉, 독립적이라는 것이다. 이런 경우 a는 c가 주어진 상황하에 b로부터 조건부 독립적이라고 한다. 이를 다른식으로도 표현할 수 있다. 위의 식에서 조건부 c를 제외하고 생각하면 p(a,b) = p(a)p(b)이다. 이는 독립의 대표적 성질이다. 조건부 독립은 여기에 조건부 c를 붙여 위와 같이 표현하게 된다. 때로 조건부 독립을 다음과 같이 간단히 기호로 표..

베이지안 네트워크 - 이산 변수 (tistory.com) 베이지안 네트워크 - 이산 변수 노드들이 이산 변수인 경우에 대해 살펴보자. K개의 상태를 가질 수 있는 단일 이산 변수 x(원-핫 인코딩)의 확률 분포 p(x|µ)를 다음과 같이 표현할 수 있다. 그리고 이 확률 분포는 매개변수 µ = ( mldiary.tistory.com 위의 장에서 이산 변수의 베이지안 네트워크에 대해 살펴보았다. 이번 장에서는 다변량 가우시안을 방향성 그래프로 표현하는 것에 대해 살표볼 것이다. 이는 성분 변수들에 대한 선형 가우시안 모델에 해당한다. D개의 변수들에 대한 임의의 방향성 비순환 그래프(DAG)를 고려해 보자. 이때 그래프의 노드 i는 가우시안 분포를 가지는 하나의 연속 확률 변수 xi를 지칭한다. 이 분포의..