Homogeneous Poisson Process 생성

안녕하세요. 톡발이입니다.

 

제가 CNN을 이용해 wafer map defect 분류하는 논문을 리뷰한 적이 있었는데요. Wafer에 대한 정보는 회사에서 공개를 하지 않기 때문에 직접 시뮬레이션으로 dataset을 만들어서 쓰는 경우가 대부분입니다. 오늘은 논문에서 어떤 식으로 wafer map을 만들었는지, 그에 관련된 알고리즘을 알아보겠습니다.

2023.10.17 - [분류 전체 보기] - CNN으로 Wafer Map Defect Pattern 분류하기 (논문 리뷰)

CNN으로 Wafer Map Defect Pattern 분류하기 (논문 리뷰)

알고리즘은 " Generating Homogeneous Poisson Process "라는 논문에 자세히 설명이 되어 있습니다. 그러므로 오늘은 이 논문에 대해서 설명해 드리겠습니다.

 

이 논문의 핵심 주제는 homogeneous poisson process로부터 pseudorandom numbers(의사난수)을 생성하기 위한 방법들에 대해서 다루고 있습니다. 여기서는 one-dimensional / two-dimensional homogeneous poisson process 이렇게 두 가지를 다룹니다.

각각이 무엇인지 이제 설명드리겠습니다.

 

• One-dimensional homogeneous poisson process : 사건이 하나의 축(예: 시간 또는 공간)을 따라 발생하는 경우를 말합니다. 이는 주로 시계열 데이터 또는 일련의 사건이 발생하는 공간적인 문제에 적용됩니다.
• Two-dimensional homogeneous poisson process : 사건이 두 개의 축(예: 시간과 공간)을 따라 발생하는 경우입니다. 이는 주로 공간적인 분포를 가진 사건들이 시간에 따라 발생하는 문제에 적용됩니다. 예를 들어, 지진 발생 패턴이나 센서 네트워크의 사건 분포 등을 모델링하는 데 사용될 수 있죠.

그럼 pseudorandom numbers (의사난수)란 무엇일까요?

실제로는 무작위로 보이지만 사실은 알고리즘에 의해 생성된 수열을 말합니다. 이러한 수열은 컴퓨터 프로그램 등에서 사용되며, 통계적으로 무작위성을 가지고 있어서 실제 random number (난수)와 비슷한 특성을 가지고 있습니다.

 

실제 난수는 완전히 예측할 수 없는 무작위성을 가지며, 물리적인 과정에 의해 발생하는 경우가 대부분인데요, 그러나 컴퓨터는 결정론적인 방식으로 작동하기 때문에 완전한 실제 난수를 생성하는 것은 어렵습니다. 따라서 pseudorandom number generator라는 알고리즘이 사용되며, 이 알고리즘은 초기값인 시드(seed)로부터 계산된 수열을 생성합니다. 따라서 의사난수는 초기값인 시드가 동일하면 항상 같은 수열을 생성하기 때문에 예측 가능하죠.

Homogeneous Poisson Process

이제 본격적으로 Homogeneous Poissin Process의 정의들에 대해 알아보겠습니다.

Stochastic Process

Stochastic Process란 확률 변수의 집합으로 이루어진 수열이나 함수입니다. 간단히 말해, 시간 또는 공간에 따라 값이 변하는 확률 변수의 모음이죠. Stochastic process에 관한 몇 가지 성질은 다음과 같습니다.

• 시간이나 공간과 같은 독립 변수에 따라 확률 변수가 정의됨
• 각 시간 또는 공간 지점에서의 확률 변수는 무작위성을 가짐
• 각각의 확률 변수는 서로 독립적이지 않을 수 있으며, 이전 확률 변수들과의 관계를 나타낼 수 있음

Counting Process

Counting process $\{N_t, t ≥ 0\}$은 sample space $\Omega$에서 정의된 stochastic process로, 각 $\omega \in \Omega$에 대해 함수 $N_t(\omega)$ 는 구간 $(0, t]$에서 발생하는 사건(event)의 실현값(realization)을 나타내며, $N_0(\omega)$이다.

 

쉽게 말하자면, Counting process는 시간에 따라 사건이 발생하는 과정을 나타내는 stochastic process입니다. Counting process는 주어진 시간 간격에서 사건의 수를 추적하고 기록하는 역할을 합니다. 다음과 같은 성질을 가집니다.

• Counting process는 시간에 따라 정의되며, 보통 시간 축은 양의 실수값을 가짐
• Counting process는 각 시간 지점에서 발생한 사건의 수를 나타내는 확률 변수를 가짐
• 초기 시간에서의 값은 일반적으로 0으로 설정
• 각 시간 지점에서의 사건 수는 이전 시간 지점에서의 사건 수에 추가되는 방식으로 업데이트

이 정의에 따르면, 각 $ \omega $에 대해 $ N_t(\omega) $는 자연수 값이며, 감소하지 않고 right-continuous인 특성을 갖는다.

 

왜 right-continuous 할까?

이산형으로 예를 들면, x = a, b, c,... 이렇게 이산적인 점에서 확률이 존재할 텐데, 누적해서 더하다 보면 x = a, b, c,.. 가 되는 그 순간에만 값이 증가하겠죠? 따라서 x = a전후로 보면, x < a에선 값이 그대로이다가 x = a인 순간에 값이 증가해서 x > a 일 때 다시 증가한 값 그대로 갈 겁니다. 그러면 x = a와 x > a 구간이 연속, 즉 우측이 연속이 됩니다.

 

Homogeneous Poisson Process는 다음과 같은 특징을 가지는 Counting Process의 한 종류입니다.

Homogeneous Poisson Process

Definition 1

A counting process $\{N_t, t \geq 0\}$ is called a homogeneous Poisson process if:

1. $\forall{t}, s \geq$ 0 , and $0 \leq u \leq t, N_{t+s} - N_t$ is independent of $N_u$ ;
2. $\forall{t}, s \geq 0, \text{Pr}\{N_{t+s} - N_t \geq 2\} = o(s)$; and
3. $\forall{t}, s \geq 0, \text{Pr}\{N_{t+s} - N_t = 1\} = \lambda s + o(s)$, where $\lambda > 0$.

여기서 $o(h)$는 작은 오차를 의미하는 표기법입니다. Poisson process에서는 단위 시간 또는 단위 공간에서 발생하는 사건의 평균 수를 $\lambda$로 표현하죠.

 

1. 은 결과 과정이 독립적인 증가(independent increaments)를 가지도록 보장해 줍니다. 즉, 서로 다른 시간 간격에서 발생하는 사건의 수가 독립적이라는 것을 의미합니다.

 

비슷하게, 조항 2. 와 3. 은 과정이 정상 증가(stationary increments)를 가지도록 보장해 줍니다. 즉, 구간 내에서 발생하는 사건의 수의 분포가 해당 구간의 길이에만 의존한다는 것을 의미합니다. 쉽게 말해서, 구간의 시작점이나 종료점에는 의존하지 않는다는 것을 의미하는데요, 이는 동일한 길이의 구간에서는 발생하는 사건의 분포가 동일하게 유지됨을 의미합니다.

 

Definition 1은 사건 간의 시간이 독립적이며, 동일한 분포를 따르는 (i.i.d. = independent and identically distributed) 지수 분포의 확률 변수로 간주됨을 의미합니다. 이 지수 분포의 평균은 $1 / \lambda $ 입니다. 게다가, 시간 길이가 $t$인 고정된 구간 내에서의 사건의 수는 평균이 $\lambda t$인 poisson 분포를 따릅니다.

후자의 사실을 통해 poisson process의 Definition 2를 도출하는 동기가 됩니다.

Definition 2

A counting process $\{N_t, t \geq 0\}$ is called a homogeneous Poisson process if:

1. $\forall{t}, s \geq 0, and 0 \leq u \leq t, N_{t+s} - N_t$ is independent of $N_u$; and
2. $\forall{t}, s \geq 0, \text{Pr}\{N_{t+s} - N_t = j\} = \exp\{-\lambda s\}\frac{(\lambda{s}^j)}{j!}, j = 0, 1, ….$

Definition 1과 Definition 2는 equivalent 합니다.

Definition 3

1. $\forall t \geq 0$ and almost all $\omega$, the mapping $t \rightarrow N_t(\omega)$ has jumps of unit magnitude only; i.e.,$ N_t(\omega)-\lim_{s \uparrow t} N_s(\omega) = 0\ \text{or}\ 1\ \forall t \geq 0$ and for almost all $\omega$;
2. $\forall t, s \geq 0$, and $0 \leq u \leq t, N_{t+s}-N_t$ is independent of $N_u$; and
3. $\forall t, s \geq 0$, the distribution of $N_{t+s} - N_t$ does not depend on $t$.

논문에서는 이렇게 총 3가지 homogeneous poisson process에 대한 정의를 설명합니다.

이제 본격적으로 homogeneous poisson process로부터 pseudorandom numbers를 생성하는 방법에 대해 논의해 봅시다. 이것이 의미하는 것은 디지털 컴퓨터에서, $\lambda$로 지정된 homogeneous poisson process로부터 사건 시간 $ \{ t_i, i=  1,2,...\}$ 의 실현값(realization)을 생성하는 것입니다.

1. Generating on the Nonnegative Real Line

Algorithm 1

1. Initialize $t = 0$
2. Gernerate $u \sim U(0, 1)$
3. Set $t\ \leftarrow t - \frac{1}{\lambda}\log(u)$
4. Deliver $t$
5. Go to Step (2)

Algorithm 2

1. Generate $n \sim \text{Poisson}(\lambda t)$
2. If $n = 0$ then exit. Otherwise independently generate $u_1 \sim U(0, 1), u_2 \sim U(0, 1), …, u_n \sim U(0, 1)$, and sort (in increasing number) to obtain $u_1 , u_2,…, u_n$
3. Set $t_i \leftarrow t_0u_{(i)}$, $i = 1, 2, …, n$
4. Deliver $t_i$, $i = 1, 2,…, n$

2. Generating on the Plane

먼저 앞에서 언급한 two-dimensional homogeneous poisson process에 대해서 정의하겠습니다.

 

A counting process $\{N(t), t \geq 0\}$ is said to constitute a two-dimensional homogeneous Poisson process on $C \subseteq \mathbb{R}^2$ with rate $\lambda \geq 0$ if:

1. the number of events in a region $R \subseteq C$ is Possion distributed with parameter $\Lambda(R) = \int_R\lambda dV = \lambda A(R)$, where $A(R)$ is the volume of the reigion $R$;
2. the number of events occuring in any finite set of nonoverlapping regions are mutually independent.

반지름 $r > 0$의 원 위에 있는 비율 $\lambda$를 가진 two-dimensional homogenoue Poisson process로부터의 생성은 Lewis와 Shedler에 의한 다음 결과를 기반으로 쉽게 생성할 수 있습니다.

Theorem) [Lewis and Shedler, 1979]

Suppose $ (R_1, \theta_1), (R_2, \theta_2), …, (R_N, \theta_N) $ are the polar coordinates of $N > 0$ events from a homogeneous Poisson process on the circle $ C ≡ \{ (x, y) : x^2+y^2 \leq r^2 \} $. Then conditional on $ N = n $, the ordered event radii $ R_{(1)}, R_{(2)}, ..., R_{(n)} $are order statistics from the density $ f(z) = \frac{2z}{r^2}, z \in [0, r] $. Furthermore, $ \theta_1, \theta_2, ..., \theta_n $ are i. i. d. uniform in $ [0, 2\pi] $ and independent of $ R_1, R_2, ..., R_n$.

Algorithm 3

1. Generating $n \sim \text{Poisson}(\pi r^2 \lambda)$. If $n = 0$ then exit. Otherwise generate $u_1 \sim U(0, 1), u_2 \sim U(0, 1),…, u_n \sim U(0, 1)$ independently.
2. Set $R_1 \leftarrow r\sqrt{u_1}$, $R_2 \leftarrow r\sqrt{u_2}$,…, $R_n \leftarrow r\sqrt{u_n}$
3. Sort $R_1, R_2,..., R_n$ in ascending order to obtain $R_{(1)}, R_{(2)},..., R_{(n)}$
4. Generating $u_{n+1} \sim U(0, 1), u_{n+2} \sim U(0, 1),…, u_{2n} \sim U(0, 1)$ independently
5. Set $\theta_1 \leftarrow 2\pi u_{n+1}$, $\theta_2 \leftarrow 2\pi u_{n+2}$,…, $\theta_n \leftarrow 2\pi u_{2n}$
6. Deliver $(R_{(1)}, \theta_1)$, $(R_{(2)}, \theta_2)$,…,

Algorithm 3은 논문에서 Wafer map의 결함 점들을 생성할 때 사용한 방법입니다. 그래서 조금 자세히 설명해 보겠습니다.

1. Poisson 분포 생성: Poisson 분포를 따르는 변수 $n$을 생성합니다. $n$은 평균값이 $πr^2λ$인 Poisson 분포를 따릅니다. 만약 n이 0이라면 알고리즘을 종료합니다.
   ※ Poisson 분포의 평균 = $\lambda$
2. 반지름 생성: $u_1$부터 $u_n$까지 독립적으로 0부터 1까지의 균일 분포를 따르는 변수들을 생성합니다. 이 변수들을 이용하여 $R_1$부터 $R_n$까지 반지름 값을 생성합니다. 각 반지름 값 $R_i$는 $r\sqrt{u_i}$로 계산
3. 반지름 정렬: $R_1$부터 $R_n$까지의 반지름 값을 오름차순으로 정렬합니다. 이 과정을 통해 $R_{(1)}$부터 $R_{(n)}$까지의 반지름 값이 얻어집니다.
4. 추가 균일 분포 생성: $u_{n+1}$부터 $u_{2n}$까지 독립적으로 0부터 1까지의 균일 분포를 따르는 변수들을 생성
5. 각도 생성: $u_{n+1}$부터 $u_{2n}$까지의 변수들을 이용하여 $θ_1$부터 $θ_n$까지의 각도 값을 생성합니다. 각도 값 $θ_i$는 $2πu_i$로 계산
6. 결과 반환: 반지름과 각도 값의 쌍인 $(R_{(1)}, θ_1), (R_{(2)}, θ_2), ..., (R_{(n)}, θ_n)$을 반환

Algorithm 4

1. Initialize $j = 1, n = 0, w = 0, x_0 = 0$
2. Generate $u_j \sim U(0, 1)$ independently
3. Set $w_j \leftarrow −\frac{1}{\lambda} \ln(1 − u_j )$
4. Set $w \leftarrow w + w_j$
5. If $w \leq \int_{0}^{T}f(x)dx$ then set $n \leftarrow n + 1$ and go to Step (2)
6. If $n = 0$ then exit. Otherwise solve for $x_{(i)}$, $i = 1, 2, . . . , n$ satisfying $\int_{x_{(i-1)}}^{x_{(i)}}f(x)dx = w_i$
7. Generate $u_{n+1} \sim U(0, 1), u_{n+2} \sim U(0, 1), . . . , u_{2n} \sim U(0, 1)$ independently
8. Set $y_i \leftarrow u_{n+i}f(x_i)$
9. Deliver $(x_{(i)}, y_i)$, $i = 1, 2, . . . , n$

Algorithm 5

1. Generate $n \sim \text{Poisson}(\lambda A(C))$
2. If $n = 0$ then exist. Ohterwise independently generate n points $(x_i, y_i)$, $i = 1, 2,…, n$ that are uniformly distributed in $C$

 

이렇게 homogeneous poisson process로부터 pseudorandom numbers를 생성하기 위한 알고리즘 5가지를 알아보았습니다. 사실 이 논문은 그저 wafer map의 결함 점들을 생성할 때 참고한 논문이라서 아주 자세한 설명까지는 하지 않고 간단히 알아보았습니다. 역시 수학 논문은 어렵네요.

 

여담으로 한 통계 연구에 따르면, 호주 시드니 시의 휴대전화 기지국 위치는 homogeneous Poisson point process의 형태를 따르고 있다고 하네요.

글에 사진이 없어서 호주 사진이라도 넣어봤습니다.

그럼 긴 글 읽어주셔서 감사합니다!!