공간 속에 있는 점들 사이이 거리에 대한 성질
엄청 애매한 말이지만, 이런 것이 수학의 진수가 아닐까 싶다.
내가 찾고자 하는 것은 다음과 같다.
'$S \subseteq R^d$'의 공간에서 반지름 '$r$'인 ball들이 '$N$'개가 뿌려져있다고 가정하자.
이 때, 전체 영역에서 ball로 채워지지 않은 영역은 얼마나 될 것인가?
모 대충 이런 상황이다.
1. Distance Distribution in Finite Uniformly Random Networks: Theory and Applications
Spatial point process는 임의의 random countable subset of space '$S$'라고 볼 수 있다. 일반적으로 '$S$'는 '$d$' 차원의 box인 경우가 많다. 예를 들어서 1km^2 공간을 생각해보자. 이 때 '$S = [0, 1]^2 \subset R^2$' 일 것이다. 이 공간 속에 있는 잡초의 분포 등이 spatial point process가 될 것이다.
Definition (Locally Finite)
'$n(x)$'를 subset '$x \subseteq S$'의 cardinality라 하자. 만약 '$s$'가 finite하지 않다면, '$n(x) = \infty $'이다. '$x_B = x \cap B$' for '$B \subseteq S$'라 하자. 즉 '$x_B$'는 '$x$'라는 set과 '$B$'라는 set의 교집합이다. 이 때 '$x$'가 locally finite이라는 정의는 '$n(x_B) < \infty $' whenever '$B$' is bounded.
Definition (Point process)
'$S$'에서 정의된 point process '$X$'의 정의는 probability space '$(\Omega, F, P)$'에서의 measurable mapping이다. (값의 범위는 skip!) 직관적으로 설명하자면 이러한 point process '$X$'는 어떤 set '$F$'에 대한 확률을 정의할 수 있고, 이는 다음과 같다. '$P_X(F) = P(\{ w \in \Omega : X(w) \in F \})$'
아래 두 개념(BPP, PPP)은 spatial point process의 기본 중에 기본이다.
Definition (Binomial Point Process)
이는 기본적으로 점들 사이에 그 어떤 interaction도 없음을 의미한다. 다시 말해서 점들 사이에 어떤 연관 관계가 있는 경우에 PPP는 의미없는 결과를 도출하게 된다. 물론 간단해서 좋다.
어떤 point process '$X$' on '$S \subseteq R^d$'는 다음의 조건을 만족할 때 Poisson point process라 한다.
1. 어떤 '$B \subseteq S$'에 대해 '$\mu(B) < \infty$', '$N(B) ~ Pois(\mu(B))$' (평균이 '$\mu(B)$'인 Poisson distribution)를 만족한다. 쉽게 생각해서 어떤 영역을 잡았을 때 해당 영역에 뿌려져 있는 원소의 수는 해당 넓이를 평균으로 하는 Poisson distribution을 따르는 것을 의미한다.
- 사실 구현은 쉽다. 영역이 주어지면, 영역의 넓이 (혹은 넓이의 함수)를 평균으로 하는 Poisson 분포에서 값을 뽑은 후에 해당 영역에 뽑은 값 만큼의 원소를 뿌리면 된다. (http://stats.stackexchange.com/questions/16282/how-to-generate-nd-point-process)
2. 어떤 '$n \in N$'과 '$B \subseteq S$'이고, '$0 < \mu(B) < \infty$'에 대해서
$$[X_B | N(B) = n] \sim binomial(B, n, \frac{\sigma(\zeta)}{\mu(B)}) $$
를 만족한다!
만약 '$S$'가 bounded라면 PPP를 그리는 가장 간단한 방법은 1) '$N(B) ~ Pois(\mu(B))$' 2) '$N(B)$' 개의 independent한 점을 '$B$'에서 뽑는 것이다. 논문엔 '$S$' 라고 나오는데 내 생각엔 '$B$' 인 것 같다.
먼저 위와 같은 상황이 있다고 하자. 이 공간 속에 N개의 점이 있다고 할 때, 각 점까지의 거리를 크기 순으로 나열했다고 하자. 그리고 이 거리에 대한 분포에 대해서 생각해보자.
결론만 쓰자면, 공간 속 (임의의 '$d$' 차원의 공 속에 '$N$'개의 점이 임의로 뿌려져 있다면 원점에서 '$m$' 번째로 가까운 점 까지의 거리는 다음의 분포를 갖는다.
이를 유도하는 과정을 직관적으로 설명하자면 먼저 해당 random variable의 1-CDF를 구한다. 임의의 점에서 n번째로 가까운 점까지의 거리에 대한 1-CDF는 '$r_n$' (해당 확률 변수)가 주어졌을 때, '$r_n$' ball 안에 점이 n개보다 적게 들어있을 확률을 의미한다. 전체 영역이 주어졌고, '$r_n$' ball에 해당하는 넓이가 가 주어졌으므로 임의의 점이 해당 ball 속에 있을 확률 '$p$'가 있다. 이 때 1부터 n까지 '$p$'의 확률을 갖는 multinomial 확률 변수의 확률을 다 더하면 된다. 이 값을 미분하면 pdf가 나온다.
위의 식을 매트랩을 이용해서 여러 다른 조건에서 그려보면 다음과 같다.
이 때 원점에서 가장 가까운 점 까지의 거리와 두 번째로 가까운 점 까지의 거리는 다음과 같이 나타난다.
사용된 매트랩 코드
2. On the Lengths of the Pieces of a Stick Broken at Random
3. The Probability Distribution of the Distance between Two Random Points in a Box
4. Random Points Associated with Rectangles
.
'Enginius > Machine Learning' 카테고리의 다른 글
ICML에 나온 Gaussian process (0) | 2014.07.23 |
---|---|
Stochastic process and Gaussian process (2) | 2014.07.16 |
Manifold가 무엇일까? (0) | 2014.06.17 |
PAC-Bayes bound for Gaussian process (0) | 2014.05.09 |
Machine Learning (Regularization) (2) | 2014.05.06 |