본문 바로가기

Enginius/Machine Learning

공간 속에 있는 점들 사이이 거리에 대한 성질

공간 속에 있는 점들 사이이 거리에 대한 성질

엄청 애매한 말이지만, 이런 것이 수학의 진수가 아닐까 싶다. 

내가 찾고자 하는 것은 다음과 같다. 

'$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) 

 '$f$'를 어떤 set '$B \subseteq S$'에서 정의된 density function이라 하고, '$n \in N$', 즉 어떤 자연수라 하자. 이 때 어떤 point process '$X$'가 '$f$'의 density를 따르며 모두 i.i.d. 관계를 갖고 있으면 이러한 '$X$'를 '$B$'에서 '$f$'의 분포로 '$n$'개의 점으로 이뤄진 binomial point process라 한다. 
$$X \sim binomial(B, n, f)$$


Definition (Poisson 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