Michael's Study Blog

Index

1. Introduction
2. Correlation Coefficient
3. Correlation for Multiple random variables
4. Transformation of Multiple random variables
5. linear combinaiton of random variables

Introduction

이 장에서는 Multivariate Random Variable에서의 다양한 연산을 정의해볼 것이다. 상관 계수, 여러 변수에서의 변환, 랜덤 변수의 선형 결합 등등 여러 연산들을 정의할 것이다.

Correlation Coefficient

이 장에서는 확률 변수들이 서로 의존일때 얼마나, 그리고 어떻게 그 변수들이 연관되어 있는지를 알아볼 것이다.
이러한 의존성에는 어려가지 척도가 있다. 그 중에서 여기서는 $X$와 $Y$라는 확률 변수의 선형성을 측정하는 결합 분포의 모수 $\rho$를 소개할 것이다.
이 절에서 다루는 모든 확률 변수는 기댓값이 있다고 가정한다.

이러한 모수를 다루기 전에 우리는 공분산이라는 것을 정의해볼 필요가 있다.

위 식의 $Cov(X,Y)$를 우리는 $X$와 $Y$의 공분산이라고 한다. 위의 정의에서 $\mu_X$, $\mu_Y$는 각각 $X$와 $Y$의 기댓값이다.

위 식을 정리해서 다음과 같은 결과를 얻을 수도 있다.

위 식을 사용하는 것이 정의를 직접 활용해서 계산하는 것보다 종종 더 쉽기도 하다.
그리고 위 공분산을 정규화하여 단위가 없는 척도를 만들 수도 있다. 이를 상관계수라고 한다.

위 정의에서 $\sigma_X, \sigma_Y$는 각각 $X$와 $Y$의 표준 편차이다.
그리고 이러한 상관 계수에는 다음과 같은 성질이 있다.

1. 상관 계수 $\rho$가 존재하는 결합 분포를 가진 모든 확률 변수 $(X,Y)$에 대해서 $-1 \leq \rho \leq 1$ 이다.
2. $X,Y$가 독립인 확률변수이면 $Cov(X,Y) = 0$이고 따라서 상관 계수 $\rho = 0$이다. 이의 역은 성립하지 않지만 대우는 성립한다.
3. $(X, Y)$가 $X, Y$의 분산이 양수이고 유한할때 결합 분포를 가진다고 하자. 만약 $E[Y|X]$가 $X$에 대해서 선형이면 다음이 성립한다. $$\begin{align} E[Y|X] &= \mu_Y + \rho\frac{\sigma_Y}{\sigma_X}(X - \mu_X) \\ E[Var(Y|X)] &= \sigma_Y^2(1 - \rho^2) \end{align}$$

Correlation for Multiple random variables

이 파트에서는 여러 확률 변수로 앞서 배운 내용을 확장해볼 것이다. 우선, 확률 변수 $n$개에 대한 공간을 정의해 보도록 하겠다.

표본 공간 $\mathcal{C}$에서의 확률 실험을 생각해보자. 확률 변수 $X_i$는 각 요소 $c \in \mathcal{C}$에 단 하나의 실수 $X_i(c) = x_i$를 부여한다고 하자. $(1 \leq i \leq n)$ 이에 대한 $n$ 차원 벡터를 $(X_1, \dotsb, X_n)$으로 표시하고 tuple로써 공간을 정의한다.

이러한 확률 벡터의 결합 분포에 대한 본질은 앞서 다룬 내용과 별반 다를게 없다. CDF, PDF, PMF의 성질도 그러하다. 이 파트에서는 이에 따른 특수한 정리를 다뤄볼 것이다.

• 결합 분포의 적률 생성 함수(MGF)

  $-h_i \leq t_i \leq h_i$ $(i = 1,\dotsb, n)$에 대해서 다음이 존재한다고 하자.

  $$M(t_1, t_2, \dotsb, t_n) = E[e^{t_1X_1 + t_2X_2 + \dotsb+t_nX_n}]$$

  변수가 1~2개일때와 같이 위와 같은 MGF가 유일하게 결정된다.
  그리고 이러한 MGF의 벡터 표현으로 다음과 같이 표현할 수 있다.

  $$\mathbf{t} \in B \subset \mathbb{R}^n \rightarrow M(\mathbf{t}) = E[e^{\mathbf{t}^T\mathbf{X}}]$$

  그리고 이 정리가 앞으로 유용할 것이다.

  정리) $X_1, X_2, \dotsb, X_n$을 상호 독립적인 확률 변수라고 하자. 그리고 모든 $i = 1,2,3,\dotsb,n$에 대하여 $-h_i \leq t_i \leq h_i$ 이고 $h_i > 0$일때 $X_i$는 MGF $M_i(t)$를 가진다고 하자. $k_1, k_2, \dotsb, k_n$이 상수일때, $T$를 다음과 같이 $X_i$들의 선형 결합이라고 정의해 보자.

  $$T = \sum_{i = 1}^n k_iX_i$$

  이러면 $T$는 다음과 같은 MGF를 가진다.

  $$M_T(t) = \prod_{i = 1}^n M_i(k_it), \quad -\min_i{h_i} < t_i < min_i{h_i}$$

  이의 따름 정리로 다음을 정의 가능하다.

  위의 따름정리) 만약 k_i = 1 이고, $X_i$가 $i$에 상관 없이 전부 공통의 MGF를 가지고 같은 범위의 $t$($h$에서)를 가지며 서로 I.I.D 일때, 다음이 성립한다.

  $$M_T(t) = [M(t)]^n, \quad -h < t < h$$

• 다변량 분산/공분산 행렬

  이 절에서는 선형 대수학을 모르는 사람들에게는 조금 힘든 절이 될 것이다. 필히 기초 선형 대수학을 공부하고 오도록 하자.

  일단, 앞으로 설명할 변수들의 Notation들 부터 설명하도록 하겠다.

  $$\mathbf{X} = \begin{pmatrix} X_1 \\ X_2 \\ \vdots \\ X_n \end{pmatrix}$$

  $\mathbf{X}$: $n$차 확률 벡터
  $X_i$: $\mathbf{X}$의 원소

  $$\begin{align} \mathbf{W} = [W_{ij}] \\ \mathbf{W} \in \mathbb{R}^{m \times n} \end{align}$$

  $\mathbf{W}$: $m \times n$ 크기의 행렬
  $W_{ij}$: $\mathbf{W}$의 $i$행, $j$열의 원소

  위와 같은 표현에서 우리는 다음과 같이 기댓값 연산을 정의할 수 있다.

  $$E[\mathbf{X}] = \begin{pmatrix} E[X_1] \\ E[X_2] \\ \vdots \\ E[X_n] \end{pmatrix}$$

  이렇게 평균 벡터를 정의할 수 있다고 지난 챕터에서 정의했다. 그리고 평균 행렬 또한 같은 맥락으로 정의할 수 있다.

  $$\begin{align} E[\mathbf{W}] = [E(W_{ij})] \\ E[\mathbf{W}] \in \mathbb{R}^{m \times n} \end{align}$$

  그리고 이에 따라서 기댓값 행렬/벡터의 연산은 행렬과 벡터의 연산의 성질과 기댓값 본연의 성질이 합쳐져서 다음과 같은 따름 정리가 성립한다.

  따름 정리) $\mathbf{W}_1, \mathbf{W}_2$라는 행렬이 있다고 가정하자. 두 행렬 모두 차원이 $\mathbb{R}^{m \times n}$이다.
  또한, $\mathbf{A}_1, \mathbf{A}_2$를 $\mathbb{R}^{k \times m}$ 크기의 상수 행렬이라고 하고 행렬 $\mathbf{B}$를 크기가 $\mathbb{R}^{n \times l}$의 상수 행렬이라고 하자.

  그러면 다음이 성립한다.

  $$\begin{align} E[\mathbf{A}_1\mathbf{W}_1 + \mathbf{A}_1\mathbf{W}_2] &= \mathbf{A}_1E[\mathbf{W}_1] + \mathbf{A}_2E[\mathbf{W}_2] \\ E[\mathbf{A}_1\mathbf{W}_1B] &= \mathbf{A}_1E[\mathbf{W}_1]B \end{align}$$

  자, 그렇다면 대망의 분산-공분산 행렬을 다음과 같이 정의할 수 있다.

  분산-공분산 행렬) $\mathbf{X} = (X_1, \dotsb, X_n)^T$을 $\sigma_i^2 = Var(X_i) < \infty$인 $n$차원 확률 벡터라고 하자. $\mathbf{X}$의 평균 벡터를 다음과 같이 $\mathbf{\mu}$라고 표현하자. 이에 대하여 분산-공분산 행렬은 다음과 같이 정의된다.

  $$Cov(\mathbf{X}) = E[(\mathbf{X} - \mathbf{\mu})(\mathbf{X} - \mathbf{\mu})^T] = [\sigma_{ij}] \tag{definition 4}$$

  위 행렬 $Cov(\mathbf{X})$에서 대각 성분은 $Var(X_i)$이고 비 대각 성분은 $Cov(X_i, X_j), (i \neq j)$이다.

  이러한 분산-공분산 행렬의 특징은 다음과 같다.

  $\mathbf{X} = (X_1, \dotsb, X_n)^T$을 $\sigma_i^2 = Var(X_i) < \infty$인 $n$차원 확률 벡터라고 하자. $\mathbf{A}$가 상수의 $\mathbb{R}^{m \times n}$인 행렬이라고 하면 다음이 성립한다.

  $$\begin{align} Cov(\mathbf{X}) &= E[\mathbf{X}\mathbf{X}^T] - \mathbf{\mu}\mathbf{\mu}^T \\ Cov(\mathbf{A}\mathbf{X}) &= \mathbf{A}Cov(\mathbf{X})\mathbf{A}^T \end{align}$$

  또한, 모든 분산-공분산 행렬은 양반정치(PSD, positive semi-definite) 행렬이다. 즉, 모든 벡터 $\mathbf{a} \in \mathbb{R}^n$에 대하여 $\mathbf{a}^TCov(\mathbf{X})\mathbf{a} \geq 0$이다.

Transformation of Multiple random variables

자, 이제 진짜로 머리 터지는 부분에 돌입해보자. 우리는 이전 챕터에서 두 확률 변수가 주어졌을때, 한 변수로부터 다른 변수로의 분포 변환을 다루어 보았다. 이번에는 그것을 $n$차원으로 확장해서 다루어 보도록 하겠다.

우선 $n$차원 공간 $\mathcal{S}$의 부분 집합 $A$에 대하여 다음과 같은 다중 적분을 고려해보자.

다음의 확률 변수와 역함수를 $\mathcal{S}$를 $y_1, \dotsb, y_n$이 있는 공간 $\mathcal{T}$로 시상하여 $A$를 집합 $B$로 시상하는 1:1 변환을 정의한다고 하자.

역함수의 1계 편도함수는 모두 연속이고 다음 $n \times n$ 행렬식(야코비안이라고 한다, 정의 5번)이 $\mathcal{T}$에서 0이 아니라고 하면 다음을 얻을 수 있다.

이렇게 변수 변환이 깔끔하게 되는 경우는 실제로 그렇게 자주 발생하지 않는다. 예를 들어서 변환이 1:1로 안되는 경우가 대표적일 것이다. 이러한 경우의 자세한 문제적 예시는 Part. C에서 다뤄보도록 할 것이다.

linear combinaiton of random variables

자, 여기서 여러분은 선형 결합이 뭔지부터 알아야 할 것이다. 예를 들어서 확률 벡터 $(X_1, \dotsb, X_n)^T$이 있다고 하자. 여기서 여러 확률 변수들의 선형 결합은 특수한 상수 $a_1, a_2, \dotsb, a_n$에 대해서 다음과 같이 정의된다.

여기서는 $X_i$들의 선형결합으로 표현되는 확률 변수 $T$의 평균, 분산의 표현에 대해서 공부한다.

• 평균

• 공분산에 대한 정리

$T$가 위와 같이 $X_i$로 정의되는 선형 결합이고, $W$는 확률 변수 $Y_1, Y_2, \dots, Y_n$과 특정 상수 $b_1, b_2, \dotsb, b_n$로 표현되는 선형 결합이라고 가정하자. 모든 확률 변수에 대해서 분산이 유한할때, 다음이 성립한다.

• 위 정리에 대한 따름 정리 1

위의 가정과 같이 $X_i$의 분산이 유한이면 다음이 성립한다.

• 위 정리에 대한 따름 정리 2

$X_i$들 끼리 전부 독립이고 모든 $i = 1,2,\dots,n$에 대해서 $Var(X_i) = \sigma_i^2$이면 다음이 성립한다.

이 결과를 얻기 위해서 단지 모든 $X_i$와 $X_j$에 $(i \neq j)$ 대해서 독립이면 된다. 다음으로는 독립성 이외에도 확률 변수들이 동일한 분포를 가진다고 가정한다. 이러한 확률 변수의 모음을 확률 표본 이라고 한다. 이를 축약하여 I.I.D 라고도 한다!

Index

1. Introduction
2. Distirbution of Two Random Variables
3. Conditional Distribution and Expectation
4. Independence Random Variables

Introduction

이번 포스트에서는 Mathematical Statistics Chapter 2의 전반부의 이론을 설명할 것이다. 앞으로 나올 내용들의 초석이 되니 주의 깊게 공부할 필요가 있다. 또한, 이번 파트부터는 예제 문제를 풀어서 그 풀이까지 올리도록 할 것이다. 이번 Chapter 2의 경우에는 Part A, B, C로 나뉘어질 것이며 각각 전반부 이론, 후반부 이론, 실습 문제 및 Appendix로 구성될 것이다. 이번 파트를 초석으로 앞으로 괴랄할 내용들이 많이 나올 것이다. 쉽게 쉽게 넘길 수 있는 내용이지만, 기초는 쉬운게 아니라 중요한 것이다. 절대 가볍게 생각하지 말도록 주의하자.

Distirbution of Two Random Variables

우선, 두개 이상의 랜덤 변수를 쌍으로 묶어서 분포를 보고 싶은 경우가 있다고 하자. 예를 들어서, 동전 3개를 동시에 던져서 나오는 앞면/뒷면의 조합을 보는 사건이 있다고 가정해 보는 것이다. 이러한 경우에는 각 동전별로 랜덤 변수 (가령) $X$, $Y$, $Z$를 할당할 수 있다. 그렇다면 우리는 이 사건은 랜덤 변수의 쌍 $(X, Y, Z)$로 표현할 수 있을 것이다. 이렇게 확률 변수의 쌍을 우리는 확률 벡터(Random Vector)라고 부리기로 하였다.

Random Vercot의 정의: 표본 공간이 $\mathcal{C}$인 확률 실험이 주어졌을때 $\mathcal{C}$의 각 원소 $c$에 단 하나의 수의 순서쌍 $X_1(c) = x_1, X_2(c) = x_2$를 대응시키는 두 확률 변수 $X_1, X_2$를 생각해보자. $(X_1, X_2)$를 확률 벡터(Random Vector)라고 한다. $(X_1, X_2)$의 공간은 순서쌍 $\mathcal{D} = { (x_1, x_2): x_1 = X_1(c), x_2 = X_2(c) }$이다.

그렇다면 이러한 랜덤 벡터에서 사건의 확률을 어떻게 구할 수 있을까?
기본적으로 여러 방법들이 있다. 이 챕터에서는 그것을 다룰 것이다.

1. 기본적으로 각 랜덤 변수의 사건의 교집합의 확률을 구할 수 있다.
2. 여러 사건들이 얽힌 조건부 확률을 구할 수 있다.

기본적으로 이 2개의 방법을 중점으로 다룰 것이다.
이중에서 해당 절에서는 첫번째를 집중해서 다룰 것이다.

우선 각각의 확률 변수가 할당된 사건의 교집합에 대한 확률을 구해보도록 하자.
$\mathcal{D}$를 랜덤 벡터 $(X1, X_2)$에 대한 공간이라고 하자. $A$가 $\mathcal{D}$의 부분 집합이라고 했을때, 우리는 하나의 확률 변수때와 마찬가지로 이를 사건 $A$라고 한다.
그리고 이 사건 $A$에 대한 확률을 $P{X_1, X_2}[A]$라고 표현한다. 그렇다면 이러한 사건 $A$를 다음과 같이 정의해서 구한 확률을 우리는 하나의 확률 변수때와 마찬가지로 CDF(누적 분포 함수)로 정의할 수 있으며 다음과 같이 표현할 수 있다.

이렇게 정의한 CDF를 우리는 결합 누적 분포 함수라고 부른다. 여기서 공간 $\mathcal{D}$가 가산형이면 우리는 이산형 확률 벡터라고 하고 다음과 같이 결합 확률 질량 함수를 정의할 수 있다.

단일 확률 변수에서와 마찬가지로 PMF는 CDF를 유일하게 결정짓는다는 특성을 가진다. 또한, 다음 두 성질 또한 결합 PMF의 특징이다.

1. $0 \leq p_{X_1, X_2} \leq 1${
2. $\mathop{\sum\sum}{\mathcal{D}} p{X_1, X_2} = 1$

여기서 사건 $B$의 경우에는 다음과 같이 확률을 표현할 수 있다.

그리고 공간 $\mathcal{D}$가 연속형이라면 다음과 같이 적분으로 결합 CDF를 표현할 수 있다.

위 정의 3에서 $f_{X_1, X_2}$을 결합 확률 밀도 함수라고 한다. 그러면 확률이 0인 사건을 제외하고는 다음과 같이 정의된다.

결합 PDF 또한 다음과 같은 본질적인 성질이 있다.

1. $f_{X_1, X_2}(x_1, x_2) \geq 0$
2. $\int\int{\mathcal{D}} f{X_1, X_2}(x_1, x_2) dx_1dx_2 = 1$

이것 또한 마찬가지로 사건 $A \in \mathcal{D}$에 대하여 다음과 같이 확률을 구할 수 있다.

모두들 중적분쯤은 안다고 가정하고 이 글을 쓰지만 솔직히 양심에 겁나게 찔리기 때문에 중적분에 대한 논의는 Appendix에서 하도록 하겠다. (저자도 따로 사이트에 중적분 관련한 포스트를 올려놨는데 내가 뭐라고…)

Marginal Distribution

간단하게 말해서 결합 분포는 다음과 같은 분포를 뜻한다.

어떤 확률 벡터의 결합 분포로부터 하나의 확률 변수의 분포를 얻어내는 것.

예를 들어보겠다. 우리는 2개의 확률 변수 $(X_1, X_2)$의 확률 벡터와 그것의 결합 누적 분포를 가지고 있다고 가정하자. 이때 우리는 각각의 확률 변수의 분포를 보고 싶다. 어찌 해야겠는가?

답은 간단하다. 하나의 변수를 전 구간에서 적분해서 없애버리면 된다. 두 확룔 변수가 연속형일때 다음과 같이 $X_1$의 CDF를 구할 수 있다.

반대로 이산형이라면, Summation으로 구할 수 있다.

Expectation

이 개념을 기댓값을 확장해서 생각해보자. 우선 우리는 확률 벡터의 기댓값을 구하기 전에 확률 벡터에서의 기댓값을 먼저 정의할 필요가 있다.
벡터는 스칼라가 아니다. 평균을 구한다는 것이 output을 벡터로 내뱉을 것인가? 아니면 스칼라로 뱉을 것인가? 그것부터 알쏭달쏭하지 않은가?
우리는 다음과 같이 기댓값을 구하는 방법 2가지를 보도록 할 것이다.

1. 새로운 확률 변수 $Y$를 정의하여 평균을 구하는 방법 $\rightarrow$ output: scalar
2. 주변 분포를 구한 뒤에 각 변수의 평균을 구하는 방법 $\rightarrow$ output: vector

이러면 명확해 진다. 우리는 첫번째 방법부터 차례차례 알아볼 것이다.

새로운 확률 변수 $Y = g(X_1, X_2)$ ($g: \mathbb{R}^2 \rightarrow \mathbb{R}$)을 정의하여 다음과 같은 조건을 만족시킨다면 우리는 랜덤 변수 $Y$에 대해서 기댓값이 존재한다고 할 수 있다.

그렇다면 기댓값은 다음과 같이 정의할 수 있다.

이산형이라면 여기서 적분을 Summation으로 바꿔주면 된다.
그리고 특수한 평균이라고 하면 또 적률 생성 함수를 꼽을 수 있다. 그것은 다음과 같이 정의된다.

$\mathbf{X} = (X1, X_2)^T$이고, $h_1,h_2$가 양수일때 $|t_1| < h_1$, $|t_2| < h_2$이라고 하자. 이때, $E(e^{t_1X_1 + t_2X_2})$가 존재하면 이것을 $M{X_1, X_2}(t_1, t_2)$라고 하고 이를 $\mathbf{X}$의 적률 생성 함수라고 한다.

이때, $\mathbf{t} = (t_1, t_2)^T$라면 다음과 같이 정의할 수 있다.

우리는 이렇게 첫번째 기댓값을 정의할 수 있었다. 그렇다면 결과가 벡터로 나오는 확률 벡터의 기댓값은 어떻게 구할까?

뭘 어떻게 구하나, 주변 분포 구해서 벌크로 각 랜덤 변수의 평균을 구하면 된다.
이는 다음과 같이 표기한다.

Conditional Distribution and Expectation

그렇다면 이러한 확률 벡터들을 다루는데 있어서 조건부 확률(즉, 어떤 확률 변수의 값이 특정되어 있을때)의 확률은 어떻게 구할 수 있을까? 이번 파트에서는 그것을 알아볼 것이다.
우선 확률 변수가 이산형일때부터 알아보자.

우선 다음과 같은 확률을 관찰해보자.

위와 같은 확률을 다음과 같이 정의한다.

위 정의를 두고 조건부 PMF라고 한다.
같은 방법으로 조건부 PDF 또한 도출이 가능하다.

그리고 다음과 같이 $X_2$에 대한 함수 $u(X_2)$와 $X_1 = x_1$이라는 것이 주어졌을때, 조건부 기댓값은 다음과 같이 구할 수 있다.

그리고 조건부 분산은 다음과 같이 구할 수 있다.

그리고 이에 따른 정리는 다음과 같다.

• $(X_1, X_2)$가 확률 벡터이고 $X_2$의 분산이 유한이라고 하면

1. $E[E(X_2|X_1)] = E(X_2)$
2. $Var[E(X_2|X_1)] \leq Var(X_2)$

이에 대한 증명은 Appendix에서 하도록 하겠다.
이 성질 2개는 아주 중요한 것을 시사한다. $\mu_2$를 모르는 상황에서 우리는 확률 변수 $X_2$, $E[X_2|x_1]$의 데이터를 뽑아서 $\mu_2$를 추측할 수 있는데, 2번째 성질에 의하여 $X_2$보다는 $E[X_2|x_1]$가 더 신뢰할 수 있는 데이터를 제공한다는 것이다. 이 성질은 7장에서 요긴하게 사용하게 될 것이다.

Independence Random Variables

이번 파트에서는 우리는 결합 분포에서 사건의 독립이라는 조건이 어떠한 영향을 미치는지 알아볼 것이다. 우선, 두 확률 변수 $X_1, X_2$가 있을때, 두 확률 변수가 담당하는 사건이 독립이라는 것은 다음을 의미한다.

그리고 독립이 아닌 확률 변수는 의존 이라고 부른다. 이러한 독립과 관련하여 다음과 같은 정리들이 있다.

1. 확률 변수 $X_1, X_2$는 각각 받침 $\mathcal{S}_1, \mathcal{S}_2$를 가지고 결합 pdf $f(x_1,x_2)$를 가진다고 하자. 이 경우에 $f(x_1,x_2)$을 각각 $x_1, x_2$만으로 표현되는 함수 $g(x_1)$과 $h(x_2)$의 곱으로 표현할 수 있다.
2. $(X_1,X_2)$가 결합 CDF $F(x_1, x_2)$를 가지고 각각 marginal CDF 또한 가진다고 하자. 그렇다면 다음 조건이 만족되면 $X_1,X_2$는 서로 독립이다. $$\forall(x_1, x_2) \in \mathbb{R}^2, F(x_1,x_2) = F_1(x_1)F_2(x_2)$$
3. $X_1,X_2$가 독립이라는 것은 다음과 필요 충분 조건이다. $$P(a < X_1 \leq b, c < X_2 \leq d) = P(a < X_1 \leq b)P(c < X_2 \leq d)$$
4. $X_1,X_2$가 독립이며 각각 $E[u(X_1)], E[v(X_2)]$가 존재한다면 다음이 성립한다. $$E[u(X_1)v(X_2)] = E[u(X_1)]E[v(X_2)]$$
5. $X_1,X_2$에 대해 결합 MGF $M(t_1, t_2)$가 존재한다면 $X_1,X_2$는 다음일때 독립이다 $$M(t_1,t_2) = M(t_1,0)M(0,t_2)$$

일단 각각의 정리들에 대한 증명은 Appendix에서 자세히 논하도록 하겠다.

Index

1. Introduction
2. What is Set?
3. Probability Set function
4. Conditional Probability and Independency
5. Random Variables
6. Discrete Random Variables
7. Continuous Random Variables
8. Expectation of Random Variable
9. Special Expectation
10. Important Inequality

Introduction

이 카테고리의 글들은 Robert V. Hogg, Joseph W. McKean의 Mathematical Statistics를 정리하는 것이다.
여기서 논의할 수리 통계학에서는 엄밀한 확률론이나 심도 깊은 실 해석학의 내용은 직관적인 설명만으로 퉁치고 넘어갈 예정이다. 더 이상 깊이 파는 내용은 Appendix, 또는 다른 추가적인 포스트로 보충 설명을 하도록 하겠다.
1장의 경우에는 고등학생도 이해할 수 있는 내용만 나오므로 1개의 포스트에 내용을 욱여 넣을 예정이지만, 다른 포스트에서는 그런 일이 없을 것이다.
그리고 주요 예제 및 문제들은 챕터의 마지막 파트의 포스트로 빼서 다룰 것이다.
수리 통계학은 아주 현재 CS의 응용 분야에 빠질 수 없는 내용이다. 따라서 필자도 이 포스트부터는 진지하게 내용을 전개할 것이고 실수, 오타, 기타 틀린 내용은 언제나 About 페이지의 개인 정보로 연락을 주면 고쳐 나가도록 하겠다.

또한, 이 책에서 나오는 예제 R 코드는 전부 Python (with numpy)로 바꿔서 진행할 예정이다. 이유는 필자가 R을 별로 안 좋아하기 때문이다 ㅎㅎ.

마지막으로, 이 글의 예상 독자들은 당연히 고등학교 수학은 다 뗀 사람들이다. 아직 이 조건에 충족하지 못한 사람들은 아쉽지만 고등학교 수학부터 차근 차근 공부하는 것을 추천한다. 너무 낙담하지 말자. 원래 수학은 차근차근 해 나가는 학문이다. 참고로 필자는 00년생이다. 그리고 19년도에 입시를 마쳤다. 그 이후에는 교육 과정이 축소되었다고 알고 있는데, 필자때의 고등 수학을 기준으로 삼을 것이다. (참고로 자랑은 아니지만 필자는 고등학생때 미적분학/선형 대수학을 독학했다. “이거 기준으로 고등 수학을 정의할 것이다”)

What is Set?

우선 확률, 통계를 논하기 전에 가장 기초적인 Mathematical Notation인 Set부터 짚고 넘어갈 필요가 있다.

“집합”이란, 어떤 element의 모임을 설명하는 것이다.

너무 집합에 대해서 복잡하게 생각하지 말자. 집합(Set/Collection)은 어떤 “것”들의 모임이다. 예를 들어, 자연수들의 집합($\mathbb{N}$)같은 것이 있을 수 있고 실수의 집합($\mathbb{R}$)이 있을 수 있다.

이때, 이러한 집합중에서 “셀 수 있는” 원소를 가지고 있는 것을 가산형(countable) 집합 이라고 한다. 유의한 점은 가산형 집합이라는 워딩때문에 해당 집합이 유한한 원소를 가져야만 한다는 것이 아니라는 것이다. 이에 대해서는 나중에 독자들이 꼭 한번 생각해 보는 것을 추천한다.

예를 들어서, 양의 유리수의 집합은 가산형 집합이다. 왜일까?

위 그림을 보면 그 답이 나온다. 양의 유리수는 2개의 자연수의 쌍으로 표현할 수 있기 때문에 가산형 집합으로 분류할 수 있다.

이러한 집합 중에서 우리가 봐야할 어떠한 “사건”의 전체에 해당하는 집합을 우리는 표본 집합이라고 부르고 앞으로는 $\mathcal{C}$라고 표현할 것이다. 또한, 어떠한 원소들도 포함하지 않는 집합을 공집합이라고 부르고 $\empty$로 표기할 것이다.
이를 다시 말하면, “사건”은 $\mathcal{C}$의 부분 집합이다. 아주 중요한 개념이지만 해당 내용은 차차 엄밀하게 다루도록 하고 지금은 그렇구나 하고 넘어가면 된다.

이러한 집합을 표현하는데 있어서 Venn Diagram이 유용하게 사용된다. 이는 다음과 같은 집합의 표현 방식중 하나이다.

대충 위와 같은 그림이라고 보면 된다. 이에 대한 내용은 이 글을 읽는 독자들은 다 알고 있으리라 추측하고 넘어 가겠다.

집합에도 여러가지 연산이 존재한다. 이 파트에서는 간단하게 어떤 연산들이 있는지를 알아보도록 할 것이다.

우선, 어떤 집합 $A$, $B$가 있다고 가정해보자. 그렇다면 다음의 정의가 성립한다.

1. Complement Set ($A^{\complement}$) : $\mathcal{C}$에서 $A$가 아닌 원소들의 집합을 뜻한다. 즉, $A^{\complement} = {x \in \mathcal{C} | x \notin A}$
2. 집합 $A$의 각 원소가 또한 집합 $B$의 원소이면 집합 $A$는 집합 $B$의 부분 집합이라고 하고 다음과 같이 표현한다. $A \subset B$
3. $A$와 $B$의 합집합이라고 하면 $A$에 있거나 $B$에 있거나 아니면 둘 다에 있는 원소들의 집합이고 다음과 같이 표기한다. $A \cup B$
4. $A$와 $B$의 교집합이라고 하면 $A$와 $B$ 둘 다에 있는 원소들의 집합이고 다음과 같이 표기한다. $A \cap B$
5. 만약, $A \cap B = \empty$이면, $A$와 $B$를 배반 사건이라고 부른다.

이러한 집합의 연산에도 여러가지 연산 규칙이 적용될 수 있다. 대표적으로,

1. 배분 법칙
2. 교환 법칙
3. 드모르간의 법칙

이 있는데, 상세한 내용은 알 것이라고 생각하고 굳이 구구절절 설명은 안 하도록 하겠다. 그 대신 이 부분을 짚고 넘어가자.

앞으로 이러한 식으로 연속된 집합의 합/교 집합을 표현할 것이다.

이러한 집합열중에는 단조(monotone) 인 집합열도 있는데, 여기에는 2가지 유형이 있다.

1. $n \in \mathbb{N}$에 대하여 $An \subset A{n+1}$ 인 집합열 ${A_n}$을 비감소(nondecreasing) 또는 위로 중첩(nested upper) 라고 한다.
2. $n \in \mathbb{N}$에 대하여 $A_{n+1} \subset A_n$ 인 집합열 ${A_n}$을 비증가(nonincreasing) 또는 아래로 중첩(nested downward) 라고 한다.

이러한 경우에는 다음과 같음이 성립한다.

• 비감소의 경우

• 비증가의 경우

다음으로 다룰 개념은 Set을 정의역으로 삼고 실수를 공역으로 삼는 함수이다. 고등학생쯤 된다면 아직 익숙하지 않을 것이다. 자주 다루는 함수는 실수 또는 자연수가 정의역이고 공역이 실수 쯤 될 것이다.
하지만 일단 확률을 이해하는데 있어서 필수불가결인 부분이다. 지금은 받아들이도록 하자.

종종 집합 함수는 합이나 적분으로 정의된다. 다음 (1), (2)는 각각 1,2 차원에서 집합 $A$에 대한 리만 적분을 의미한다.

이때 유의해야할 점이 함수 $f$, $g$에 대해서 A를 잘못 설정하게 되면 아예 위 적분이 존재하지 않는 상황이 발생한다는 것이다.

또한, 다음 (3), (4)는 $x \in A$에 대한 $f(x)$의 총합 / $(x,y) \in B$에 대한 $g(x,y)$에 대한 총합을 의미한다.

Probability Set function

이제부터 슬슬 내용이 고등화된다. 우선 어떤 실험이 주어졌을때, 가능한 모든 결과의 표본 공간을 $\mathcal{C}$라고 하자. 일단 그리고 다음과 같은 가정을 추가하겠다.

모든 경우에 사건의 모임이 관심 있는 모든 사건을 포함할 정도로 크고, 여집합의 연산과 가산형 합집합의 연상에 대해 닫혀 있다고 가정한다. 그리고 이러한 사건의 집합을 $\mathcal{B}$라고 표현하자.

전문적으로 이러한 사건의 집합을 $\mathcal{C}$의 부분 집합의 $\sigma$-field라고 한다. 이에 대해서는 추후에 다른 포스트 하나를 소요해서 설명할 예정이다. 진짜 완전 중요한 개념이다.

이제 드디어 확률이 뭔지를 정의할 수 있는 밑밥을 다 깔았다.

$\mathcal{C}$가 표본 공간이고 $\mathcal{B}$가 사건의 집합이라고 하자. 또한, $\mathcal{B}$상에서 정의된 실함수를 $P$라고 하자. $P$가 다음 3가지 조건을 만족하면 $P$를 확률 집합 함수라고 한다.

1. $\forall A \in \mathcal{B}$, $P(A) \geq 0$
2. $P(\mathcal{C}) = 1$
3. 만약, ${A_n}$이 $\mathcal{B}$안에서 사건열이고 모든 $m \neq n$에 대해서 $A_m \cap A_n = \empty$ 일때 다음이 성립한다.

조건 3번의 경우에는 원소들이 쌍으로 배반인 사건의 모임을 서로 배타적인 모임이라고 하며 이 모임의 합집합을 배반인 합집합이라고도 한다.
그리고 이러한 합집합이 표본공간이 되면 이 모임을 exhaustive라고 한다.

드디어 확률이 무엇인지 제대로 정의했다. 위 조건을 만족시키는 집합 함수를 우리는 확률이라고 부른다. 아무거나 확률을 가져다 붙이는 것이 아니다.

그리고 이러한 확률은 다음 정리를 만족한다.

1. 각 $A \in \mathcal{B}$에 대하여 $P(A) = 1 - P(A^{\complement})$이다.
2. 공집합의 확률은 0이다.
3. A와 B가 $A \subset B$를 만족하는 사건이면 $P(A) \leq P(B)$이다.
4. 각 $A \in \mathcal{B}$에 대하여 $0 \leq P(A) \leq 1$이다.
5. $A$와 $B$가 $\mathcal{C}$에 있는 사건이면 $P(A \cup B) = P(A) + P(B) - P(A \cap B)$이다.

각 정리에 대한 증명은 책을 참고하자. 굳이 여기서 구구 절절 설명하지는 않겠다.

그리고 여기서 확률 집합 함수의 중요한 정의중 하나인 등가능성 사례를 알아보도록 하겠다.

$\mathcal{C}$가 유한한 표본 공간이라고 하자. 모든 $i = 1,2,…,m$에 대하여 $p_i = 1/m$이고 $\mathcal{C}$이 모든 부분 집합 $A$에 대하여 다음과 같이 정의하자

위 definition 3이 바로 등가능성 사례이다. 이는 매우 흥미로운 확률 모형이다. 주사위, 포커 뽑기 등등 여러 실 사용 예시가 있고 수학적으로 접근하기도 쉽다. 아무래도 그냥 세기만 잘 하면 되기 때문이다.
하지만 이런 것들을 “잘 세는” 것도 매우 중요한 일이다. 이에 대한 좋은 수학적 도구중 대표적으로 순열과 조합이 있다.

1. 순열 (Permutation)

1. 조합 (Combination)

위 2가지를 모르는 사람은 없을 것이라고 가정하고 넘어 가도록 하겠다.

그리고 이 확률론을 사건열에도 적용하여 또 다른 정리를 끌어낼 수 있다.

1. ${C_n}$을 비감소 사건열이라고 하면 다음이 성립한다.

1. ${C_n}$을 비증가 사건열이라고 하면 다음이 성립한다.

1. ${C_n}$을 임의의 사건열이라고 하면 다음을 불의 부등식이라 부른다.

Conditional Probability and Independency

어떤 확률 실험에서는 사건 $A$에만 집중해야하는 경우도 있다. 이렇게 새로운 표본공간 A를 가진 확률 집합함수를 정의하는 문제를 생각해보는 것이 바로 조건부 확률(Conditional Probability)이다. 조건부 확률은 사건 $A$의 가설에 대한 사건 $B$의 확률이 어떻게 정의되는가를 본다. 보통 이러한 확률은 ‘$A$가 주어졌을때(given) $B$의 조건부 확률’이라고 읽고 $P(B|A)$라고 표현한다. 이러한 조건부 확률은 다음과 같이 정의한다.

그리고 위와 같은 정의로부터 우리는 다음과 같은 결과를 얻을 수 있다.

1. $P(B | A) \geq 0$
2. $P(A|A) = 1$
3. $B1,B_2,\dotsb$가 서로 배타적인 사건일 경우, $P\left(\bigcup{n = 1}^{\infty} Bn | A \right) = \sum{n = 1}^{\infty}P(B_n|A)$

1,2번은 명백하다 그리고 3번에 대한 설명을 추가적으로 하자면 일련의 사건 $B_1,B_2,\dotsb$가 서로 배타적이라고 가정하면 다음이 성립하게 된다.

이를 가산형 합집합에 대한 분배법칙을 활용하면 다음과 같은 결과를 얻을 수 있다.

물론, 당연히 여기서 $P(A) > 0$이 성립해야한다.
그리고 조건부 확률의 정의로써 다음을 알 수 있다.

이 관계식을 확률의 곱셈 법칙이라고 한다. 이는 아주 단순하지만 유용하게 사용되고는 한다.
곱셈 법칙은 3개 이상의 사건으로도 확장될 수 있다. 이를 $k$개의 사건으로 확장하는 수학적 귀납법을 활용한 증명을 밑에 적어두도록 하겠다. 나중에 베이즈 정리 등을 이해할때 필수적이닌 꼭 숙지해 두도록 하자.

• $k$개의 사건에 대한 확률의 곱셈 법칙의 증명

$P(A_i) > 0, (i = 1,2,\dots,k)$인 $k$개의 배타적이고 전체를 이루는 사건들에 대해서 생각해 보자. 이러한 사건이 $\mathcal{C}$를 분할한다고 여겨도 된다. 이때, 위 확률의 분포가 균일할 필요는 없다. 그리고 $P(B) > 0$인 또 다른 사건 $B$가 있다고 하자. 따라서 사건 $B$는 사건 $A_i, (i = 1,2,\dots,k)$중 단지 하나와 같이 발생한다. 즉,

이 성립한다.

이때, $B \cap A_i, (i = 1,2,\dots,k)$는 서로 배반 사건이므로 다음 또한 성립한다.

이때, $P(B \cap A_i) = P(A_i)P(B | A_i), (i = 1,2,\dots,k)$이므로, 다음이 성립한다.

이 결과를 총 확률의 법칙이라고 하고 다음의 매우아주엄청슈퍼중요한 정리로 이어진다.

Bayes Theorem

이 파트는 따로 포스트 하나를 떼서 설명해도 모자랄 정도로 매우 중요한 정리이다. 하지만 지금은 가볍게 짚고 넘어가기 위해서 간단한 설명만을 하겠다.

• Bayes Theorem

$i = 1,2,\dots,k$에서 $P(A_i) > 0$인 사건들이 있다고 하자. 그리고 이 사건들이 표본공간 $\mathcal{C}$를 분할한다고 가정했을때 $B$가 어떤 사건이라면 다음을 얻을 수 있다.

이에 대한 증명은 독자들에게 맡긴다. 워낙 쉽기도 하고 위의 총확률의 법칙을 활용하면 되기 때문이다.

여기서 중요한 용어를 조금 정리하고 넘어가고자 한다. 으례 다음과 같이 확률에 이름을 붙이는데, 여러 분야에서 활용되니 알고 넘어가자.

• 위에서 $P(A_i)$를 사전 확률(prior probability)라고 부른다.
• 위에서 $P(A_i|B)$를 사후 확률(posterior probability)라고 부른다.

이에 대한 유용성, 응용 분야는 차례차례 알아가도록 하자. 지금은 일단 알아만 두기를 권장한다.

Independency

어떤 경우에는 사건 $A$에 사건 $B$가 영향을 받지 않는 경우가 있다. 이러한 경우에는 사건 $A$와 $B$는 서로 독립적이다. 라고 부른다.

이에 곱셈 법칙을 적용하면 다음과 같은 결과를 얻는다.

따라서 위의 위의 결과를 만족시키면 사건 $A$, $B$를 서로 독립이라고 불러도 된다.
이를 $k$개의 사건에도 적용할 수 있다. 이 부분에 대한 증명은 독자들에게 맡기도록 하겠다.

Random Variables

이제 독자들은 표본공간 $\mathcal{C}$의 원소가 수가 아닐때는 $\mathcal{C}$를 기술하기가 그렇게 쉽지 않다는 것을 알 수 있을 것이다. 이를 실수로 대응시킬 수 있는 방법이 바로 확률 변수를 사용하는 것이다.

표본공간 $\mathcal{C}$에서 확률 실험이 주어졌다면 각 원소 $c \in \mathcal{C}$에 오직 하나의 실수 $X(c) = x$를 대응시키는 함수 $X$를 확률 변수, random variable이라고 한다. $X$의 공간/범위는 실수의 집합 $\mathcal{D} = { x: x = X(c), c \in \mathcal{C} }$이다.

여기서 표현한 $\mathcal{D}$가 가산형 집합이냐 실수의 구간이냐에 따라서 확률 변수가 이산형(discrete)이냐 연속형(continuous)이냐가 결정이 된다.

자, 이제부터 중요한 내용인 Probability Mass Function(PMF), Probability Density Function(PDF), Cumulative distribuiton function(CDF)가 등장하게 된다.

우선, $X$가 유한공간 $\mathcal{D} = {d_1, \dots, d_m}$에서 정의된 경우를 생각해 보자. 이때, 표본공간 $\mathcal{D}$에서 다음과 같은 함수 $p_X(d_i)$를 정의해보자.

이제 여기서 표본공간 $\mathcal{D}$의 사건 $D$의 확률을 다음과 같이 정의할 수 있다.

이러한 함수 $p_X(d_i)$를 우리는 확률 질량 함수(PMF)라고 한다.

그렇다면, $X$가 연속형일 경우는 어떨까? 표본 공간이 연속형인 경우에는 단 한 지점에서의 확률을 논하는 것이 의미가 없다. 왜냐? 확률적으로 0.00001도 오차 없이 딱 그 지점에서 사건이 발생할 확률은 0에 수렴하기 때문이다. (직관적으로 받아들이자.)
따라서 우리는 연속형 확률 변수에서는 구간을 지정해서 확률을 구해야 한다.

따라서 우리는 구간 $(a,b) \in \mathcal{D}$에 대해 $X$의 유도된 확률 분포 $P_X$가 정의될 수 잇는 함수를 지정할 수 있다.

이러한 함수 $f_X(x)$는 다음과 같은 조건을 만족해야 한다.

1. $f_X(x) \geq 0$
2. $\int_{\mathcal{D}} f_X(x)dx = 1$

이러한 함수 $f_X(x)$를 확률 밀도 함수(PDF)라고 한다.

그리고 이산이건, 연속이건 상관 없이 정의되는 함수가 있다. 바로 누적 분포 함수(CDF)이다.
이는 다음과 같이 정의된다.

여기서 위 정의 8의 우항은 $P(X \leq x)$라고 간략하게 표현되기도 한다.

이러한 CDF의 성질은 다음과 같이 정리할 수 있다.

• 누적 분포 함수 $F(x)$를 가진 확률 변수가 $X$일때, 다음이 성립한다.
  1. $\forall (a,b) \in \mathbb{R}^2$, $F(a) \leq F(b), a < b$ (비 감소 함수)
  2. $\lim_{x \rightarrow -\infty} F(x) = 0$
  3. $\lim_{x \rightarrow \infty} F(x) = 1$
  4. $\lim_{x \downarrow x_0} F(x) = F(x_0)$, $F(x)$는 우 연속 함수
• CDF $F_X$를 가진 확률 변수를 $X$라고 하면 $a < b$에서 $P[a < X \leq b] = F_X(b) - F_X(a)$이다.
• 모든 확률 변수에서 $\forall x \in \mathbb{R}$에 대해 $P[X = x] = FX(x) - F_X(x-)$이다. ($F_X(x-) = \lim{z \uparrow x } F_X(z)$)

위 식들에 대한 증명은 나중에 Chapter 1 Appendix의 다른 포스트에서 다루도록 하겠다.

Discrete Random Variables

이산형 확률 변수는 다음과 같이 정의된다.

확률 변수의 공간이 유한이거나 가산형일 경우인 경우에 이러한 확률 변수를 이산형 확률 변수라고 한다.

공간 $\mathcal{D}$를 가진 이산형 확률 변수를 $X$라고 하자. $X$의 확률 질량 함수는 다음과 같이 정의된다.

이때, PMF는 다음 2가지 성질을 만족해야한다.

1. $0 \leq p_X(x) \leq 1, x \in \mathcal{D}$
2. $\sum_{x \in \mathcal{D}}p_X(x) = 1$

만약, 이산형 집합 $\mathcal{D}$에서 위 2가지 조건을 만족한자면 이 함수는 한 확률 변수의 분포함수를 유일하게 결정한다는 것을 증명할 수 있다. 하지만 여기서는 다루지 않을 것이다.

그리고 여기서 또 한번 중요한 정의가 나온다. 바로 받침(support)이라는 것이다. 공간 $\mathcal{D}$를 가진 이산형 확률 변수 $X$가 있다고 하자. 위의 CDF의 3번째 성질이 의미하는 바를 다시 톺아보자.

모든 확률 변수에서 $\forall x \in \mathbb{R}$에 대해 $P[X = x] = FX(x) - F_X(x-)$이다. ($F_X(x-) = \lim{z \uparrow x } F_X(z)$)

위 정리와 같이 $F_X(x)$의 불연속성은 질량을 정의한다. 즉, $x$가 $F_X$의 불연속점일때 $P(X=x) > 0$이 된다. 우리는 여기서 이산형 확률 변수의 공간과 양의 확률인 이러한 불연속 점들 사이의 특성을 정의하고자 한다.

이산형 확률 변수 $X$의 받침을 양의 확률인 $K$ 공간의 점이라고 하자. $K$의 받침을 나타내기 위해서 흔히 $\mathcal{S}$를 사용한다. (이때, $\mathcal{S} \subseteq \mathcal{D}$ 이다.)

우리가 여기서 알 수 있는 점은 $x \in \mathcal{S} \rightarrow p_X(x) > 0$과 $x \notin \mathcal{S} \rightarrow p_X(x) = 0$이라는 점이다. 따라서 $x \notin \mathcal{S}$인 $x$에서 $F_X(x)$는 연속이다.

너무 어렵게 말했는가? 누구나 알기 쉽게 말하자면 불연속점의 집합을 $\mathcal{S}$라고 하고 거기에 속하지 않은 부분에서의 확률은 $0$이고 아니면 PMF가 확률을 가진다는 뜻이다.

Transformation

통계를 다루면서 자주 부딧히는 문제중에 하나이다. 확률 변수 $X$가 있으며 그것의 분포를 알고 있을때, 우리는 $X$로 표현되는 확률 변수 $Y = g(X)$의 분포를 알고 싶은 것이다. 이때, $X$가 이산형이라면 어떻게 표현할 수 있는지 그것을 알아보고자 한다.

$X$가 공간 $\mathcal{D}_X$를 가진 이산형 확률 변수라고 하자. 그렇다면 $Y$는 공간 $\mathcal{D}_Y = { g(x): x \in \mathcal{D}_X }$일 것이다.
여기서 우리는 2가지 경우를 생각해볼 수 있다.

1. $g$가 1 대 1 함수이다.

   이런 경우에는 문제가 심플해진다. $Y$의 PMF는 다음과 같이 얻을 수 있다.

1. 1이 어림도 없는 경우) 이러한 경우에는 함수의 구간별로 나눠서 각각 1대 1인 상황을 만든 후에 변환을 진행하면 된다. (귀찮은 경우이다.)

Continuous Random Variables

앞선 절에서는 이산형 확률 변수에 대해서 알아 보았으니, 이번에는 연속형 확률 변수에 대해서 알아보도록 하겠다.

확률 변수 $X$의 누적 분포 함수 $F_X(x)$가 $\forall x \in \mathbb{R}$에 대해서 연속이라면 확률 변수 $X$를 연속현 확률 변수라고 부른다.

주의해야할 점이 위 CDF의 정리중에서 3번째이다. 연속형에서는 질량점이 없으므로 어느 점을 꼽든지 간에 $P[X = x] = 0$이다. 대부분 연속형 확률 변수는 절대 연속이다. 즉, 어떤 함수 $f_X(t)$에 대하여

이다. 이러한 $f_X(t)$를 우리는 PDF, 확률 밀도 함수라고 한다. 이러한 확률 밀도 함수는 다음 2가지 조건을 만족해야한다.

1. $f_X(x) \geq 0$
2. $\int^{\infty}_{-\infty}f_X(x)dx = 1$

여기서 중요한 점은 한 함수가 위의 2개의 성질을 만족한다면 그것은 한 연속형 확률 변수의 PDF라는 것이다.

Quantile

여기서 등장하는 개념이 분위수이다.

$0 < p < 1$이라고 하자. 확률 변수 $X$의 분포에서 $p$차 분위수는 $P(X < \xi_p) \leq p$, $P(X \leq \xi_p) \geq p$가 되는 $\xi_p$ 값이다. 이를 $X$의 $100p$번째 백분위수라고 한다.

Transformation

그렇다면 연속형 확률 변수에서의 변환은 어떻게 이루어질까? 다음에 그 방법을 설명해두었다.
우리는 CDF를 활용하면 쉽게 그것을 행할 수 있다.

$X$는 pdf $f_X(x)$를 가진 연속형 확률 변수이고 $Y = g(X)$라고 하자. 여기서 $g(x)$는 1대 1 대응 함수이며 미분 가능한 함수이다. $g$의 역함수를 $x = g^{-1}(y)$라고 표현하며 $\frac{dx}{dy} = \frac{d[g^{-1}(y)]}{dy}$라면 $Y$의 pdf는 다음과 같다.

여기서 $\frac{dx}{dy} = \frac{d[g^{-1}(y)]}{dy}$를 변환의 야코비안(Jacobian, $J$로 표기한다.)이라고 한다.

Expectation of Random Variable

이 파트에서는 기댓값 연산을 소개한다. 다음 정의를 보자.

만약 $X$가 pdf $f(x)$와 다음이 성립하면 연속형 확률 변수이면

$X$의 기댓값은 다음과 같다.

만약 x가 이산형 확률 변수이면 다음이 성립할때

$X$의 기댓값은 다음과 같다.

여기서 $E(X)$는 수학적 기댓값(mathematical expectation), $X$의 기댓값(expected value), $X$의 평균 (mean)이라고들 부른다. 일반적으로 $\mu$라고 표기한다.
이러한 평균은 다음 성질들을 가진다.

1. $X$가 확률 변수이고 어떤 함수 $g$에 대하여 $Y = g(X)$라고 하자.

   a. $X$가 pdf $fX$를 가진 연속형 변수일때, $\int{-\infty}^{\infty}|g(x)|f_X(x)dx < \infty$이면 $Y$의 기대값은 존재하며 다음과 같다.

   $$E(Y) = \int_{-\infty}^{\infty}g(x)f_X(x)dx$$

   b. $X$가 pmf $pX$를 가진 이산형 변수이고 $X$의 받침이 $S_X$라고 하자. 만약 $\sum{x \in S_X}|g(x)|p_X(x) < \infty$이면 $Y$의 기댓값이 존재하며 이 값은 다음과 같다.

   $$E(Y) = \sum_{x \in S_X}g(x)p_X(x)$$

2. $g_1(X)$, $g_2(X)$가 $X$의 함수이고 $g_1(X)$, $g_2(X)$의 기댓값이 존재한다고 가정하자. 그렇다면 상수 $k_1, k_2$에 대해서 $k_1g_1(X) + k_2g_2(X)$의 기댓값이 존재하며 이 값은 다음과 같다.

Special Expectation

몇몇 특수한 함수의 기댓값은 확률 변수의 특수한 성질들을 끌어내어 그 특성을 파악하는데 도움을 준다. 이러한 특수한 기댓값들의 종류를 이번 장에서는 다뤄볼 것이다.

1. Variance

   이걸 굳이 설명해야하나 싶지만, 일단 정의만 적어 보겠다.

   $$\sigma^2 = Var(X) = E[(X - \mu)^2]$$

2. Moment Generating Function (MGF)

   어떤 $h > 0$에 대하여 $-h < t < h$일때, $e^{tX}$의 기댓값이 존재하는 확률 변수를 $X$라고 하자. $X$의 적률 생성 함수는 $M(t) = E[e^{tX}]$로 정의된다.

   이러한 적률 생성 함수는 특수한 성질을 가지는데, 그것은 다음과 같다.

   0을 초함하는 개구간에 존재하는 적률 생성 함수 $M_X$와 $M_Y$를 가진 확률 변수를 각각 $X,Y$라고 하자. 임의의 $h > 0$에 대해 $-h < t < h$일때, $M_X(t) = M_Y(t)$인 경우에 한하여 모든 $z \in \mathbb{R}$에 대하여 $F_X(z) = F_Y(z)$이다.

   조금 많이 중요한 성질로는 이러한 MGF를 n차 미분한 결과에 0을 대입한 것을 n차 적률(n-th moment) 이라고 부르고 이는 $E(X^n)$과 같다.

3. Characteristic Function

   이는 적률 함수와 모양새가 비슷한데, 허수 단위를 추가한 것이다.
   $\varphi(t) = E[e^{itX}]$ 로 정의되며 $\varphi(t) = M(it)$가 성립한다.

적률 생성 함수와 특성함수는 각각 PDF의 라플라스 변환/푸리에 변환이다. 따라서 각 함수들은 PDF 별로 유일하다.

Important Inequality

여기서는 알아두면 아주 유용한 부등식을 소개할 것이다. 증명은 나중에 Appendix 포스트에서 몰아서 할 것이니 유의하자. 여기서는 소개만 할 것이다.

1. $X$가 확률 변수이고 $m$은 양의 정수이며 $E[X^m]$이 존재한다고 가정하자. 만약 $k$가 양의 정수이고 $k \leq m$이면 $E[X^k]$가 존재한다.
2. [마르코프 부등식]확률 변수 $X$의 음이 아닌 함수를 $u(X)$라고 하자. $E[u(X)]$가 존재하면 모든 양수 $c$에 대하여 다음이 성립한다.

1. [체비셰프 부등식]확률 변수 $X$가 유한한 분산을 가진다고 하자. 즉, 1번 부등식에 의해 평균이 존재한다고 하면, $k > 0$에 대해서 다음이 성립한다.

1. [옌센의 부등식] 만약, $\phi$가 개구간 $I$에서 볼록이면 $X$가 받침이 $I$안에 있고 유한 기댓값을 가진 확률 변수라면 다음이 성립한다.

만약, $\phi$가 순 볼록이면 부등식 $X$가 상수 확률변수가 아닌 한 엄격하다.

SLAM Study - Introduction

이번 포스트에서는 SLAM에 관해서 논의해 볼 것이다. 이 포스트는 다음 글을 바탕으로 제작되었다.

Index

1. SLAM: Problem Definition
   1. Mathematical Basis
   2. Example: SLAM in Landmark Worlds
   3. Taxonomy of the SLAM Problem
2. Three Main SLAM Paragigms
   1. Extended Kalman Filters
   2. Particle Methods
   3. Graph-Based Optimization
   4. Relation of Paradigms
3. Visual RGB-D SLAM

SLAM: Problem Definition

SLAM이란, 이동하는 로봇이 미지의 환경과 noise가 낀 Sensor를 가지고 주변 환경의 Map을 만들면서 자기 자신의 상대적인 위치를 특정하는 알고리즘을 일컫는다. 이러한 알고리즘을 배우기 위해서 이 파트에서는 어떠한 수학적 지식이 필요한지와, 어떤 문제들을 해결해 나가야 하는지를 배우게 된다.

Mathematical Basis

SLAM에서 mobile robot의 궤적은 다음과 같이 정의된다.

2차원 평면에서의 좌표 $(x, y)$와 로봇이 향하고 있는 방향 $\theta$의 3차원 벡터의 Sequence

예를 들어서 $x_t = (x,y,\theta)$ 라고 하자. 그렇다면 이러한 궤적(path)는 다음과 같이 정의된다.

이러한 궤적에서 $T$는 $\infin$가 될 수도 있다.
여기서 Odometry라는 개념이 나온다. 이는 무엇이냐면, “시간에 따른 위치 변화를 측정하기 위하여 Sensor의 데이터를 사용하는 것”이다. 굉장히 포괄적인 개념인데, SLAM을 할때는 반드시 나오는 개념이니 꼭 이해해 두도록 하자.

여기서 우리는 간단하게 Odometry로 $t-1$에서 $t$로의 위치 벡터 $x_t$를 추정할 수 있는 데이터 $u_t$가 있다고 가정하자.

그렇다면 다음의 Sequence $U_T$를 로봇의 상대적인 위치의 motion의 정보라고 할 수 있다.

noise가 없는 motion의 경우, $U_T$와 $x_0$만으로도 충분히 경로를 복원할 수 있을 것이다. 하지만 어림도 없다. $U_T$에는 반드시 noise가 끼워져 있을 수 밖에 없다.

최종적으로 로봇은 주변 환경을 감지할 것이다. LiDAR든지 Camera를 사용해서 말이다. 우리는 $m$을 주변 환경에 대한 진짜 지도라고 앞으로 표시하겠다.
이러한 지도 $m$은 Landmark, object, surface 등등으로 구성되어 있을 것이다. 그리고 $m$은 그들의 location이 될 것이다. 그리고 $m$은 종종 time-invariant하다고 간주된다.

주변의 환경 정보 $m$과 자신의 위치 정보 $x_t$ 사이에서 로봇의 measurements는 정보를 수립하게 된다. 만약에 로봇이 정확하게 1번의 기준 시점에서 1개의 measurement를 얻는다면 우리는 이러한 measurement의 sequence를 다음과 같이 표시할 수 있다.

그렇다면 우리는 SLAM을 위의 definition 1,2,3을 사용해서 재차 간략하게 표현할 수 있다.

SLAM은 $U_T$와 $Z_T$를 가지고 주변 환경 $m$과 자신의 위치의 sequence $X_T$를 복원하는 문제이다.

이러한 SLAM 문제를 조금 더 세부적으로 나눠서 여러 문제들이 또 존재한다.
첫번째로, 밑의 확률 분포를 구하는 문제를 full SLAM problem이라고 한다.

보이다시피, 이 알고리즘을 데이터를 batch 단위로 처리하게된다. 즉, offline이라는 것이다.

두번째로, 밑의 확률 분포를 구하는 문제를 online SLAM problem이라고 한다.

Online SLAM은 로봇의 전체 경로를 복원하는 것보다는 현재의 위치에 초점을 맞추고 있다. 이러한 online알고리즘들은 통상 filters라고 부른다.

이러한 SLAM Problem들을 해결하기 위해서는 2가지의 모델이 추가로 필요하다.

1. Odometry Model $U_T$에 대한 수학적인 model
2. 환경 $m$에서 로봇의 위치가 $x_t$일때, measurment $z_t$에 대한 model

그렇다면 우리는 SLAM에서 다음과 같은 확률 분포를 추측하는 것이 타당하다고 쉽게 알 수 있을 것이다.

위 2가지 확률 분포를 여태까지의 내용을 종합해 보았을때 우리가 필요한 2가지의 모델이라고 할 수 있다.

Example: SLAM in Landmark Worlds

우리는 종종 표현하기 어려운 수학적인 모델을 표현하기 쉽도록 가정을 통해서 constraints를 두는 것을 많이 진행한다.

SLAM에서 가장 흔하게 쓰이는 가정이 바로 환경 $m$을 point-landmarks로 표현하는 것이다.
이를 간략하게 설명하자면, 2D 평면에 점들을 찍어서 Map을 표현하는 것이다. 이렇게 표현하면 점의 갯수를 $N$이라고 했을때 Map을 $2N$ Dimension의 벡터로 표현할 수 있다.

이러한 계파에서는 다음과 같이 가정을 하는 것이 일반적이다.

로봇은 다음 3가지를 감지할 수 있다.

1. landmarks 주변의 상대적인 거리
2. landmarks들의 상대적인 bearing (방위각)
3. landmark들의 identity

위에서 1,2번은 noise가 발생할 수 밖에 없다. 하지만 가장 simple한 케이스로 한정을 한다면 3번은 완벽하게 측정할 수 있다.

만약, 3번을 결정하는 문제로 넘어가면 그건 SLAM의 가장 어려운 문제중 하나로 분류된다.

위 설정을 가지고 noise가 없는 measurement function을 먼저 정의해 보도록 하겠다.

위의 $z^g_t$, $x^g_t$는 각각 $\mathbb{R}^2$, $\mathbb{R}^3$에 속하는 벡터들로써, noise가 없는 진짜 사물의 landmark point/위치이다.

하지만 우리가 실제로 받는 값은 여기에 Noise가 끼기 마련이다. 따라서 이를 수학적으로 정의하기 위해서 우리는 하나의 예시로써 다음과 같이 $z_t$, $x_t$를 정의해 보자.

$\mathcal{N}$을 Gaussian Distribution이라고 하고 $\mathbf{Q}_t \in \mathbb{R}^{2 \times 2}$, $\mathbf{R}_t \in \mathbb{R}^{3 \times 3}$인 Noise Covariance Matrix 2개가 있다고 가정하자.

그렇다면 $z_t$, $x_t$는 다음과 같이 표현할 수 있다.

물론, 여태까지의 논의는 솔직히 너무 현실과 동떨어져있다. 하지만 명심해야할 점은 어떠한 SLAM 알고리즘이던, 결국에는 $p(zt | x_t, m)$와 $p(x_t|x{t-1}, u_t)$에 대한 논의가 필요하다는 것이다.

Taxonomy of the SLAM Problem

SLAM이 워낙 포괄적인 문제이다보니, 알고리즘별로 여러 접근 방법이 존재한다. 우리는 그것의 분류법을 여기서 다뤄볼 것이다.

1. Full Batch vs Online

   위에서 다룬 논의이니 넘어가도록 하겠다.

2. Volumetric vs Feature-Based

   Volumetric SLAM에서는 Map 정보가 고화질로 sampling되어 주변 환경을 photo-realistic하게 재구축할 수 있는 상황이다. 상당히 많은 데이터를 다루고 그만큼 연산량도 엄청나다.

   그에 비해서 Feature-Based SLAM은 상대적으로 sparse한 정보를 가지고 SLAM을 진행한다. 이 방법이 조금 더 연산량이 가볍고 효율적이지만, 정확도는 상대적으로 떨어질 수 밖에 없다.

3. Topological vs Metric

   Topological한 Mapping 기법은 location들의 관계를 기초로 하여 정의된다. 그에 반해서 Metric Mapping은 location들의 거리(Metric)에 기반하여 Mapping을 진행한다. 요즘 학계에서는 Topological 기법을 거의 쓰지 않는다.

4. Known vs Unknown Correspondence

   Correspondence 문제는 관측된 것들의 Identity끼리의 관계도를 조사하는 것이다. 몇몇 SLAM 알고리즘들에서 이러한 처리를 추가적으로 진행한다. 이러한 Correspondence를 추정하는 문제는 data association 문제라고도 불리우며 SLAM의 가장 난제중 하나이다.

5. Static vs Dynamic

   Static SLAM은 주변 환경이 시간에 따라 변화하지 않는다는 전제를 가지고 SLAM을 진행한다. Dynamic SLAM은 시간에 따라 환경이 변화할 수 있다는 것을 전제로 SLAM을 진행한다.

6. Small vs Large Uncertainty

   SLAM의 문제는 위치의 uncertainty를 어느 정도로 다룰 수 있는지에 따라서 구분된다. closing loop에 대해서는 이러한 uncertainty가 매우 커지는데, 이 문제를 loop closing problem이라고 한다. 이렇게 loop를 닫는 문제를 푸는 것이 현대 SLAM의 특징이다. 이러한 uncertainty는 GPS같이 자신의 절대 위치를 특정할 수 있으면 조금 감소되어진다.

7. Active vs Passive

   Passive SLAM에서는 다른 개체가 로봇을 조종하게 된다. 그리고 SLAM 알고리즘은 순전히 관측만 한다. 대부분의 SLAM 알고리즘이 이것에 속한다.

   그에 반해서 Active SLAM에서는 로봇이 자체적으로 환경을 조사하면서 정확한 지도를 얻어내게 된다.

8. Single-Robot vs Multi-Robot

   notation 대로, 단일 로봇이냐 다중 로봇이냐이다.

9. Any-Time and Any-Space

   이 문제는 제한된 시간과 computation power를 가진 로봇에서 SLAM을 푸는데 있어서 과거의 방법애 대한 대안이다.

Three Main SLAM Paragigms

이 장에서는 다음 3가지의 알고리즘에 대해서 다루게 된다.

• EKF SLAM
• Particle filters
• Graph-Based Optimization

각각의 특성을 알고리즘별로 알아볼 것이다.

Extended Kalman Filters

역사적으로 Extended Kalman Filters(EKF)는 가장 일찍 나왔다. 아마도 가장 영향력 있는 SLAM 알고리즘이 아닐까 싶다.

간략하게 설명하자면, 로봇이 주어진 환경에서 움직이면서 measurement를 수집하는데, system의 state vector와 covariance vector가 Kalman filter로 계속 update가 되는 방식이다.
즉, 새로운 feature가 발견될때마다 quaderatic하게 covariance의 dimension이 증가하게 된다.

이러한 Kalman filter의 구현은 매우 중요하고도 어려운 주제이다. 또한 마찬가지로 sensing과 world modeling 또한 이에 필요한 주제이다. 이는 해당 링크에서 자세한 내용을 확인할 수 있다.

EKF 알고리즘은 robot의 estimation을 다음과 같은 multivariate Gaussian으로 표현한다.

여기서 고차원의 벡터 $\bf{\mu}_t$는 현재 위치 $x_t$에 대해서 최적의 estimation을 나타낸다. 그리고 $\bf{\Sigma}_t$는 $\bf{\mu}_t$에 대한 평균적인 error이다.

지난번에 다루었던 point-landmark 예시에서는 $\bf{\mu}_t$는 $3 + 2N$차원아고 $\bf{\Sigma}_t$는 $(3+2N) \times (3+2N)$차원인 양의 준 정방 행렬이다.

EKF SLAM의 point-landmark example에서의 유도를 간략히 설명해 보자면 한 시점에서 $g$와 $h$가 Talyor Expansion으로 선형화되고, 그 선형화 된 식에 Kalman Filter를 적용하는 방식이다.
EKF SLAM은 기본적으로 online SLAM으로 분류된다. 밑의 그림이 이를 대략적으로 나타내고 있다.

위 그림에서 점선이 로봇의 실제 궤적이고 회색 타원이 EKF가 추정한 로봇의 위치이다. 또한 회색 점이 Landmark point의 실제 위치이고 흰색 타원이 EKF가 추정한 point의 위치이다.

(a-c)까지는 landmark를 마주할 때마다 로봇의 위치의 uncertainty가 커지게 된다. 그리고 (d)에서 로봇이 처음의 landmark를 다시 감지했을때 모든 landmark와 position의 uncertainty가 감소한다. (d를 잘 보면 현재 위치에 대한 uncertainty가 특히 감소되어 있다.)

이러한 현상은 Gaussian Posterior의 Covariance Matrix의 Correlation 덕분이다. 로봇의 위치에 대한 오차가 누적되어 가면서 시간에 따라 추정치는 모호해질 수 밖에 없다. 하지만 상대적으로 잘 알려져 있는 첫번째 landmark의 위치를 확실하게 다시 특정하여 로봇의 위치에 대한 정보를 확정한 순간 연관되어 있는 모든 landmark point에 영향을 주어 정보를 전파할 수 있는 것이다.

EKF SLAM의 가장 기본 전제는 map의 feature들을 로봇이 한 지점에서 완벽하게 관측이 가능하다는 것이다. 물론 아닌 경우에 대한 연구들도 존재한다.
EKF SLAM의 가장 난점은 연산이 quadratic하다는 것이다. 시간 복잡도가 폭팔한다. 이를 해결하기 위해서 EKF의 Extention에 해당하는 연구들이 많이 등장하였는데, 여기서는 다루지 않겠다.

Particle Methods

두번째 방법은 Particle filter를 사용하는 방법이다. 이는 Monte Carlo Method(1947)에 기인하고 있지만, 최근 20년 근처에 꽤 유행하게 되었다.
꽤 추상적으로 먼저 말해보자면, 수 많은 particle들을 모아서 posterior distribution을 추정하는 것이 particle filter 방법이다.

대표적인 알고리즘으로는 Fast SLAM이 있는데, 이를 간략하게 point-landmark example에 대입해서 생각해 보도록 할 것이다.

여기서부터는 Fast SLAM의 설명입니다.

모든 시간대에서 FastSLAM은 $K$개의 다음과 같은 type의 Particle을 가진다.

위 정의 13에서 $[k]$는 Sample의 index이다. 위 식에 대한 설명을 하자면 다음과 같다.

• Sample Path $X_t^{[k]}$
• $N$ (Landmark의 point의 개수)개의 2-D Gaussian Distribution의 mean $\bf{\mu}{t, n}^{[k]}$과 Covariance Matrix $\bf{\Sigma}{t, n}^{[k]}$

위에서 $n$은 landmark point의 index($1 \leq n \leq N$)이다.

즉, FastSLAM은 $K$개의 Path와 $KN$개의 Gaussian Distribution을 가지고 있는 것이다.
이 파라미터들을 초기화 하는 것은 간단하다. 모든 particle의 로봇의 위치를 원점으로 두고 계산하는 것이다.
그 다음에 parameter의 update는 다음과 같이 수행한다.

1. Odometry의 측정값이 도착하면, 새로운 위치 변수가 각 particle들에 대해서 stochastic하게 생성된다. 이때 location particle들을 생성하는 분포는 definition 14와 같다. 여기서 $x^{[k]}_{t-1}$는 이전 location이며 이러한 확률적 sampling 과정은 kinematics가 계산될 수 있는 어떠한 로봇이든 쉽게 수행될 수 있다.

   $$x^{[k]}_t \approx p(x_t | x^{[k]}_{t-1}, u_t) \tag{Definition 14}$$

2. measurement $z_t$를 받으면 2가지 일이 일어난다.
   첫번째로 각 particle들에 대해서 $z_t$의 확률을 계산한다. definition 15 처럼 말이다.
   이러한 $w_t^{[k]}$를 importance weight라고 한다. (현재 measurement에 대해서 이 particle이 얼마나 중요한지를 나타내는 factor)

   $$w_t^{[k]} = \mathcal{N}(z_t | x^{[k]}_t, \bf{\mu}_{t, 1}^{[k]}, \bf{\Sigma}_{t, N}^{[k]}) \tag{Definition 15}$$

3. 그 다음으로 Fast SLAM은 위에서 만든 importance weight를 가지고 새로운 particle을 뽑는다. 이 과정을 resampling이라고 한다.

4. 그 다음에 새로 뽑은 particle set을 가지고 EKF Filter의 rule에 따라서 parameter를 update 한다.

꽤 복잡하게 들리지만, 막상 적용하기는 쉽다.

1. motion sampling은 이미 역학적인 계산으로 쉽게 얻을 수 있고
2. Gaussian measurement를 사용한다면 importance를 계산하는 것도 쉽고,
3. parameter를 update 하는 것도 결국 low-dimension에서 이루어지니 쉽다.

이러한 FastSLAM의 유도 과정에서는 3가지 테크닉을 활용하는데, 간략하게 이름만 적어 보도록 하겠다.

1. Rao–Blackwellization
2. conditional independence
3. resampling

이 3가지 과정을 중점적으로 공부하면서 차후에 FastSLAM은 더 자세히 포스트로 정리해서 올려둘 것이다.

이러한 FastSLAM은 2가지 문제점이 있다.

1. map을 구성하기 위한 sample의 수가 적당히(educated guess) 지정되어야 한다
2. 이전에 mapping된 지역에 재방문 하는 일이 많은 nested loop의 경우에는 particle depletion이 발생할 수 있다.

이를 해결하기 위해서 또 많은 연구들이 등장했는데, 여기서는 다루지 않도록 하겠다.

Graph-Based Optimization

이번에 다룰 내용은 SLAM 문제를 풀 수 있는 3번째 방법인 Graph Based Optimization이다. 이 방법은 non-linear sparse optimization으로 SLAM을 해결한다. 이 방법을 직관적으로 설명하자면 다음과 같다.

1. Landmark와 robot의 location은 graph의 node라고 생각할 수 있다.
2. 각각의 연속된 location pair $x_{t-1}, x_t$는 edge로써 연결되어 있다.
3. 해당 edge는 odometry $u_t$로 부터 나오는 정보를 표현한다.
4. 이때, 해당 edge는 시간 $t$에서의 location $x_t$에서 landmark $m_i$를 감지했을때 발생한다.

이러한 Graph의 Edge는 Soft constraints이다. 이러한 Constraints를 만족시키는 것으로 map과 robot의 full path를 추정할 수 있다. 이 과정은 밑의 그림으로 자세히 설명할 수 있다.

그림을 보면 robot이 이동하면서 위치 $x_t$애서 landmark $m_i$를 감지할때마다 edge가 생기게 되고, 그것을 adjacent matrix로 표현해 나갈 수 있다. 이러한 과정에서 위 matrix는 sparse한 상태로 남게 된다. 최악의 경우에는 node에 비해 constraints의 갯수가 시간과 node의 개수에 대해서 linear해질 수도 있다.

정보 이론적으로 생각해서, 우리가 이러한 SLAM문제를 푸는 것은 이 그래프의 엔트로피를 최소화 하는 것으로 생각해 볼 수 있다. 그 관점에서 우리는 graph를 다루기 이전에 지난번에 정의한 posterior probability에 log를 씌워보자.

우리는 각 location과 mapping의 sensing 사건이 독립적이라고 가정했을때 다음과 같이 수식을 전개할 수 있다.

엔트로피를 최소화 한다는 것은 definition 16을 최대화 하는 것과 같다.

equation 1을 point-landmark example에서 Gaussian 추정을 적용하여 다음과 같은 quadratic form으로 표현할 수 있다.

위 equation 3를 최적화 하는 것이 SLAM문제를 푸는 것으로 연결된다. 흔한 선택지로는 sparse Cholesky & QR decomposition이고, Gradient Descent나 conjugate gradient 방법도 좋은 선택지이다.

Graphical SLAM은 EKF보다 훨씬 더 넓은 map으로 scale을 넓힐 수 있다는 것이 장점이다. 몇몇 추정을 더해야하기는 하지만, EKF에 비하면 Graph method의 update에 필요한 time-complexity와 space-complexity는 각각 constant/linear하다.

Relation of Paradigms

• EKF SLAM: quadratic한 Time/Space Complexity로 인한 map의 scaling에 한계가 있다 + linearization 과정에서 mapping이 잘못될 수 있다.
• Particle filter: EKF SLAM에 있던 계산 복잡도의 한계를 해결했으나, map이 복잡해질 수록 필요한 particle의 수가 기하 급수적으로 늘어난다.
• Graph-based Optimization: 시간복잡도와 공간 복잡도를 혁명적으로 해결함으로써 가장 큰 mapping을 그릴 수 있는 알고리즘이 되었다.

Visual RGB-D SLAM

최근에 SLAM의 중요한 연구 화제는 단영 Visual SLAM이다. Visual SLAM은 RGB-D Sensor(Kinect)나 Camera를 활용하여 주변 map을 생성하거나 로봇의 6-DOF Pose를 추정하는 알고리즘이다. Visual SLAM은 appearance information을 활용해서 loop-closing같은 어려운 문제를 해결할 수 있는 단초를 제공하기도 한다. 이러한 Visual SLAM은 최근까지도 Video Stream을 처리할 HW 성능이 부족해서 난항을 겪고 있었다.
Davison이 이러한 연구에 있어서 선구자적인 역할을 하면서 해당 분야가 각광을 받게 되었다.

Davison과 다른 연구자들에 의하면 Visual SLAM은 camera로 얻어지는 measurement가 odometry 정보를 제공할 수 있게 만드는 것이라고 한다. 이러한 연구들의 종파들 중에는 Feature detection, Feature matching, outlier rejection, constraint estimation, trajectory optimization 등이 있다.

그리고 Visual Information은 loop-closing을 위한 정보 또한 엄청나게 많이 제공을 하는데, 대표적인 예시가 바로 visual object detection을 이용한 location recognition이다.

또한, robust한 visual SLAM의 이정표를 만든 연구는 PTAM이다. 이 연구는 keyframe mapping과 localization을 별도릐 thread로 나눠서 계산을 진행함으로써 online processing에서의 robustness와 성능을 동시에 높일 수 있었다. 여기서의 keyframe은 현재 Visual SLAM에서 복잡도를 줄일 수 있는 방법으로써 주류를 이루고 있다.
다른 방법으로는 view-based mapping system이라고 large-scale에서 pose graph optimization을 기반으로 visual mapping을 진행하는 방법도 있다.

다른 계파로는, RGB-D sensor(Kinect)를 이용해서 mapping과 localization을 동시에 진행하는 연구들도 있다. 그리고 object의 surface를 스캔하는 연구도 있다. 이러한 연구는 sensor의 pose와 surface point의 위치를 최적화 하는 연구이다.

앞으로는 Dense processing method라고 해서 GPU를 활용하여 조금 더 성능을 fine tuning하는 것도 있다.

해당 포스트는 필자가 직무 Interview를 위해 스터디한 내용을 적어두는 곳입니다. 틀린 내용이 있을 수 있습니다.

Index

• DS & Algorithm
  • Linked List / Array
    • Linked List for Array
    • Linked List for Tree
  • Stack
  • Queue
  • Sort
    • Stable / Unstable Sort
    • Bubble Sort
    • Insert Sort
    • Selection Sort
    • Quick Sort
    • Merge Sort
    • Count Sort
    • Radix Sort
  • Tree
    • Binary Tree (Vanila, Full, Complete)
    • Binary Search Tree
    • Red Black Tree
    • B Tree
    • B+ Tree
  • Heap
  • Hash Table
  • Graph
    • Graph Travarsal
    • Minimum Spanning Tree
      • Kruskal algorithm
      • Prim algorithm
• Operating System
  • Process
  • Thread
  • Multi-processing / Multi-Threading
  • Scheduling
  • System Call
  • Synchronization
  • Memory
    • Memory Management Strategy
    • Locality of Cache
• Database
  • SQL vs NoSQL
  • Index
  • Transaction
  • Lock
  • deadlock
  • Redis
  • High Avaliablity Strategy
  • ORM
• Web
  • TCP / UDP
  • TCP 3way/4way hand shake
  • TLS/SSL
  • HTTP 1.1/2.0
  • HTTP Cache
  • RESTful API
  • Sync / Async / Blocking / Non-Blocking
  • Blocking IO / Non-Blocking IO
• Javascript/Nodejs
  • Javascript
  • NodeJS
• Object Oriented Programming Basic
  • Properties of OOP
  • 5 Principle

DS & Algorithm

Linked List / Array

먼저 Array에 대해서 설명을 해보자면 Array는 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 index를 통해서 해당 element에 접근이 가능하다. 그렇기에 찾고자 하는 원소의 index를 알고 있으면 $O(1)$의 시간 복잡도로 해당 element에 접근할 수 있다. 즉 random access가 가능하다는 장점이 있다.

하지만 insert와 delete 연산의 경우에는 이야기가 다르다. 어떠한 index의 element를 삽입/삭제 하는 경우에는 그 뒤의 원소들을 한칸씩 뒤/앞으로 shift해줘야 한다. 이 경우에 시간 복잡도가 O(n)이 된다.

Linked List는 이와는 다르다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것이다.

하지만 Linked List 역시 한 가지 문제가 있다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

Stack

선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.

Queue

선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 놈이 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다. 이를 구현하고 있는 Priority queue등을 사용할 수 있다.

Sort

Stable / Unstable Sort

Stable Sort와 Unstable Sort의 차이는 같은 값의 숫자더라도 그 상대적인 위치가 유지 되느냐 아니냐이다.
예를 들어서 다음과 같이 “3 3 4 2 1 5 3“가 있다고 해보자.
만약 sorting된 결과가 다음과 같으면 stable sort이다.
“1 2 3 3 3 4 5”
이 이외의 결과는 전부 unstable sort이다.

Bubble Sort

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
==> 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

기본적으로 $O(n^2)$의 시간 복잡도를 가진다.

Insert Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

기본적으로 $O(n^2)$의 시간 복잡도를 가진다.

Selection Sort

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
==> 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
==> 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.

기본적으로 $O(n^2)$의 시간 복잡도를 가진다.

Quick Sort

분할 정복 알고리즘의 하나로 평균적으로 $O(n\log_2 n)$의 시간 복잡도를 가진다. 이는 불안정 정렬에 속한다.
과정은 다음과 같다.

1. 리스트 안의 한 요소를 선택한다. 이를 pivot이라고 하겠다.
2. pivot을 기준으로 그보다 작은 요소를 전부 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 동일한 방법으로 재 정렬한다.
4. 이를 부분 리스트들이 더 이상 분할 불가능 할때까지 반복한다.

최악의 경우에는 시간 복잡도가 $O(n^2)$이 되며 이 경우는 대표적으로 리스트가 전부 정렬 되어 있는 경우이다.

실질적으로는 pivot을 중간값으로 잡아서 알고리즘을 최적화 하는 방법도 있다. 정말 아무 값이나 pivot으로 잡아버리면 리스트가 불균등하게 분할되어 시간이 오래 걸리는 경우가 생긴다.

이를 방지하기 위해서 C++에서는 quick sort와 heap sort를 합친 intro sort를 사용하고 있다. 이는 기본적으로 quick sort와 동일하게 동작하지만 재귀 호출의 깊이가 일정 수준 이상으로 깊어지면 그 다음부터는 쪼개진 list를 heap sort로 정렬하여 시간 복잡도를 개선하였다. (구체적으로는 재귀함수의 깊이가 $1.5\log_2 N$보다 깊어지면 heap sort를 사용하여 정렬을 진행한다.)

Merge Sort

분할 정복 알고리즘의 하나로 $O(n\log_2 n)$의 시간 복잡도를 가진다. quick sort와 달리 안정 정렬에 속한다.
과정은 다음과 같다.

1. 리스트의 절반의 길이로 리스트를 2개로 분할한다.
2. 계속 이렇게 잘라 나가면서 각 부분 리스트들을 재귀적으로 합병 정렬을 이용해서 정렬한다.
3. 두 부분 리스트들을 하나의 정렬된 리스트들로 병합한다.

단점으로는 별도의 메모리 공간이 필요하다. 리스트를 병합하는 과정에서 추가적인 메모리 공간에 이를 덧씌우는 작업을 진행하는데, 이 과정에서 컴퓨팅 resource를 잡아 먹으므로 실제로는 quick sort가 최선의 경우에서는 더 좋은 성능을 내고 있다.

Count Sort

등장하는 숫자의 개수를 counting 하면서 정렬을 하는 알고리즘이다.
정렬 자체는 시간복잡도가 $O(N)$이지만, 공간 복잡도가 리스트의 원소에 따라 달라진다. 게다가, 리스트의 원소가 크면 클수록 무의미한 순회를 반복하기 때문에 비효율성이 발생되는 정렬 방법이다.

Radix Sort

기수 정렬은 낮은 자리수부터 정렬해 가는 정렬이다. 비교 연산을 하지 않으며 시간 복잡도가 $O(dN)$으로 빠른 정렬중에 하나이다. 하지만 데이터의 자리수에 따라서 정렬 시간 복잡도에 영향을 미치며, 추가적인 Queue를 사용하며 메모리 공간을 차지 한다는 점이 단점이다.

Tree

Tree는 기본적으로 Stack이나 Queue와는 달리 계층적 구조를 표현하는 비선형 자료구조이다. Tree의 명확한 정의는 “Cycle이 없는 Graph”이다.

다음은 기본적인 Tree에서의 용어는 Graph에서의 그것과 큰 차이는 없지만 몇가지 추가되는 것이 있다.

1. Root Node: 트리 구조에서 최상위 노드에 있는 것을 의미한다.
2. Leaf Node: 하위에 다른 노드들이 연결되어 있지 않은 Node를 의미한다.
3. Internal Node: 단말 노드를 제외한 모든 노드로 Root Node를 포함한다.

Binary Tree (Vanila, Full, Complete)

우선 기본적인 Binary Tree의 정의부터 살펴보도록 하겠다.
Root Node를 중심으로 2개의 Sub Tree로 나뉘는 Tree를 뜻한다. 이때 해당 Sub tree 들도 Binary Tree의 조건을 만족해야 한다.
이 재귀적인 정의가 성립하려면 공집합도 Binary tree이고 Node가 하나인 것도 Binary Tree이다.

이러한 Binary Tree는 그 형태에 따라서 3가지 종류로 나뉜다.

1. Perfect Binary Tree: 모든 level이 꽉 찬 Tree
2. Complete Binary Tree: 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태가 Complete Binary Tree 이다.
3. Full Binary Tree: 모든 노드가 0개 혹은 2개의 children 을 가지고 있는 Tree

Binary Search Tree

Binary Search Tree는 다음과 같이 정의된 Tree를 말한다.

1. BST의 Node에 저장된 Key는 유일하다
2. 부모의 Key는 왼쪽 자식 Node의 Key보다 크다.
3. 부모의 Key는 오른쪽 자식 Node의 Key보다 작다.
4. 왼쪽과 오른쪽 Sub Tree도 BST이다.

BST의 특장점은 트리 위에서 특정 Key를 검색하는 속도가 $O(N\log_2 N)$이라는 것이다.
하지만 만약 한쪽으로만 계속 데이터가 저장되어 Skewed Tree가 된다면 성능에 영향을 미칠 수 있다. 대표적으로 한쪽으로만 데이터가 계속 저장되면 탐색에 필요한 시간 복잡도는 $O(N)$이 된다.

Red Black Tree

Red Black Tree는 BST에서 Insert/Delete 연산을 수행할때의 시간 복잡도를 줄이기 위해서 나타난 자료구조이다. 동일한 Node의 개수일때, Depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 Idea이다.

RBT의 명확한 정의는 다음과 같다.

1. BST의 정의를 만족해야 한다.
2. 각 Node는 red 또는 Black의 색을 가진다.
3. Root Node는 무조건 Black이다.
4. 각 Leaf Node(NULL)는 무조건 Black이다.
5. 어떤 Node의 색이 Red라면 두 Children의 색은 모두 Black이다.
6. 각 Node에 대해서 Node로 부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다.

이러한 RBT는 다음과 같은 특징을 가진다.

1. Binary Search Tree 이므로 BST 의 특징을 모두 갖는다.
2. Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
3. 노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.

그리고 RBT의 삽입과 삭제 연산은 다음과 같이 수행된다.

• 삽입

  BST의 특성을 유지하면서 Node를 삽입한다. 그리고 삽인된 Node의 색은 Red로 지정한다.
  삽입 결과가 RBT의 특성에 위반될 경우에는 Node의 색을 조정하고 Black-Height가 같아야 한다는 정의에 위반되면 rotation을 통해서 Height를 조정한다.
  이러한 과정을 통해서 RBT는 동일한 Height에 존재하는 internal node들의 Black-hieght가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.

• 삭제

  삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제한다.
  삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 된다.
  그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정한다.
  지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지된다.

B Tree

B Tree는 이진트리에서 발전되어 모든 Leaf Node들이 같은 level을 가질 수 있도록 자동으로 balancing이 되는 Tree이다. 정렬 순서를 보장하고 Multi Level Indexing을 통한 빠른 검색이 가능하다.

최대 $M$개의 자식을 가질 수 있는 B Tree의 정의는 다음과 같다.

1. Node에 최대 $M$개부터 $\frac{M}{2}$개 까지의 자식을 가질 수 있다.
2. Node에 최대 $M-1$개부터 $[\frac{M}{2}] - 1$개의 Key가 포함될 수 있다.
3. Node의 Key가 $x$개라면 자식의 수는 $x+1$개이다.
4. 최소 차수는 자식수의 하한값을 의미하며 최소 차수가 $t$라면 $M = 2t-1$을 만족한다.
5. BST 처럼 각 Key들의 왼쪽 자식들은 항상 부모보다 작은 값을, 오른쪽 자식들은 부모보다 큰 값을 가진다.

B+ Tree

B+ Tree는 B Tree를 변형한 자료구조이다. 이는 실제 여러 DB에서 Index를 저장할때 사용되고 있다.

B+ Tree는 B Tree와 다음이 다르다.

1. 모든 Key, Data가 Leaf Node에 모여 있다. B Tree는 Leaf Node가 아닌 각자 Key 마다 data를 가진다면 B+ Tree는 Leaf Node에 모든 data를 가진다.
2. 모든 Leaf node가 Linked List의 형태를 띄고 있다. 따라서 B+ Tree에서는 Root Node에서부터 검색을 하는 것이 아닌, Leaf Node에서 선형 검사를 할 수 있어서 시간 복잡도가 굉장히 줄어든다.

Heap

Heap은 특정한 규칙을 만족시키는 Complete Binary Tree의 일종이다. Heap에는 Max Heap과 Min Heap 2가지 종류가 있다.

Max Heap이란 각 Node의 값이 해당 Children의 값보다 크거나 같은 Complete Binary Tree를 말한다.
그리고 Min Heap은 그것의 반대이다.

Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complexity 이 $O(1)$이다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (즉, random access 가 가능하다.) 또한 Min Heap도 최소값이라는 점만 다르고 나머지는 동일하다.

Hash Table

Hash의 정의는 다음과 같다.

내부적으로 Array를 사용하며 특수한 알고리즘(Hash function)을 사용하여 데이터와 연관된 고유한 숫자를 만들어낸 후에 이를 Index로 사용하는 자료구조.

이러한 특수한 알고리즘 덕분에 collision이 발생하지 않는다면 $O(1)$의 시간 복잡도로 데이터를 찾을 수 있다.

하지만 어설픈 Hash function을 사용하면 당연히 collision이 자주 발생하게 된다.
따라서 좋은 Hash Function을 사용해서 Hash Table을 구성해야 한다.

Hash function을 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해서 어떻게 대응할 것인가가 훨씬 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 hash function를 만들어봤자 그건 array 와 다를바 없고 메모리를 너무 차지하게 된다.

이제는 Conflict를 해결하는 방법을 알아보도록 하겠다.

1. Open Address 방식

   Hash에서 Collision이 발생하면 다른 Hash Bucket에 해당 자료를 삽입하는 방식이다.
   여기서 Hash Bucket은 Hash Table에 데이터를 저장하는 하나의 공간이다.

   이렇게 되면 원하는 데이터를 $O(1)$에 못 찾을 수도 있다. 그럴 경우에 원하는 데이터를 찾아내는 여러가지 방법이 있다. 대표적인 예시로 다음과 같은 것들이 있다.

   • Linear Probing: 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
   • Quadratic probing: 2 차 함수를 이용해 탐색할 위치를 찾는다.
   • Double hashing probing: 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.

2. Separate Chaining 방식

   일반적으로 Open Addressing은 Separate Chaining 방식보다 느리다. Separate Chaining 방식은 Hash Collision이 발생하지 않도록 보조 함수를 통해 조정할 수 있다면 Worst Case에 가까워지는 빈도를 줄일 수 있다.

   이러한 Separate Chaining 방식은 2가지 구현 방식이 있다.

   1. Linked List를 활용: 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다.
   2. Red Black Tree를 이용: 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다.

Graph

Graph는 크게 Undirected Graph와 Directed Graph로 나뉜다. 말 그대로 간선 연결 관계에서 방향성이 없는 것을 전자, 방향성을 가진 것을 후자라고 한다.
이때, Degree라는 개념이 등장한다. 이는 Undirected Graph 에서 각 정점(Vertex)에 연결된 Edge 의 개수를 Degree 라 한다.
그리고 Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

이러한 Graph를 구현하는 방법은 2가지가 있다.

• 인접 행렬을 사용하는 방법: 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 $O(1)$ 으로 파악할 수 있다. Edge 개수와는 무관하게 $V^2$ 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.
• 인접 리스트를 사용하는 방법: vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 $O(E + V)$이다. Sparse graph 를 표현하는데 적당한 방법이다.

Graph Travarsal

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.

1. DFS (Depth First Search)

   그래프 상에서 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아가는 방법을 우선하여 탐색한다. Stack을 사용하여 구현할 수 있고 시간 복잡도는 $O(V + E)$ 이다.

2. BFS (Breath First Search)

   그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 시간 복잡도는 $O(V + E)$이다. 이때 간선이 가중치를 가지고 있지 않으면 (전부 동일한 가중치를 가지고 있다면) BFS로 찾은 경로가 최단 경로이다.

Minimum Spanning Tree

그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다.

특정 Graph에서 MST를 찾아내려면 다음 2가지 알고리즘을 사용하면 된다.

1. Kruskal Algorithm

   초기화 작업으로 edge 없이 vertex 들만으로 그래프를 구성한다. 그리고 weight 가 제일 작은 edge 부터 검토한다. 그러기 위해선 Edge Set 을 non-decreasing 으로 sorting 해야 한다. 그리고 가장 작은 weight 에 해당하는 edge 를 추가하는데 추가할 때 그래프에 cycle 이 생기지 않는 경우에만 추가한다. spanning tree 가 완성되면 모든 vertex 들이 연결된 상태로 종료가 되고 완성될 수 없는 그래프에 대해서는 모든 edge 에 대해 판단이 이루어지면 종료된다.

   이때 Cycle의 여부는 Union find 알고리즘으로 판단한다.

   시간 복잡도: $O(E \log E)$

2. Prim Algorithm

   초기화 과정에서 한 개의 vertex 로 이루어진 초기 그래프 A 를 구성한다. 그리고나서 그래프 A 내부에 있는 vertex 로부터 외부에 있는 vertex 사이의 edge 를 연결하는데 그 중 가장 작은 weight 의 edge 를 통해 연결되는 vertex 를 추가한다. 어떤 vertex 건 간에 상관없이 edge 의 weight 를 기준으로 연결하는 것이다. 이렇게 연결된 vertex 는 그래프 A 에 포함된다. 위 과정을 반복하고 모든 vertex 들이 연결되면 종료한다.

   시간 복잡도: $O(E \log V)$

Operating System

Process

Process는 실행중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU를 할당받을 수 있는 것을 의미한다.

Process는 OS로 부터 Memory, File, Address Space등을 할당 받으며 이들을 총칭하여 process라고 부른다.
OS는 Process를 관리하기 위해 특정 자료구조로 Process의 정보를 저장하고 있는데, 이것이 Process Control Block (PCB)이다. OS는 Process의 생성과 동시에 고유의 PCB를 생성하고 관리한다.

(중요도 낮음)
PCB에는 다음과 같은 정보들이 저장된다.

• Process ID
• Process 상태
• Program Counter
• CPU Register
• CPU Scheduling 정보
• Memory 관리 정보
• I/O 상태 정보
• Accounting 정보

Thread

Thread는 Process의 내부에서 각자의 주소 공간이나 자원을 공유하는 하나의 실행 단위이다.

Thread는 Thread ID, Program Counter, Register 집합, 그리고 Stack으로 구성된다. 같은 Process에 속한 Thread들 끼리는 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 OS의 자원을 공유한다.

Multi-processing / Multi-Threading

• Multi-Threading의 장점

Multi-Process를 통해 동시에 처리하던 Task를 Multi-Threading으로 처리할 경우, 메모리 공간과 OS Resource를 절약할 수 있다.
만약 병렬로 처리해야하는 Task가 각자의 통신을 요구하는 경우에도 Multi-Processing과는 다르게 별도의 자원을 요구하는 것이 아닌, 전역 변수 공간에 할당된 Heap 영역을 통해 데이터의 공유가 가능하다.
심지어 Thread의 Context Switch는 Process의 그것과는 달리 Cache Memory를 비울 필요가 없기 때문에 더 빠르다.
이러한 이유로 Multi-Threading이 Multi-Processing보다 자원 소모가 적고 더 빠른 응답 시간을 가진다.

• Multi-Threading의 단점

Multi-Processing과는 달리, Multi-Threading은 공유 자원인 Heap 영역이 있기 때문에 동일한 자원을 동시에 접근할 수 있어서 이 부분을 신경써서 Programming을 해야한다.
이 때문에 Multi-Threading은 동기화 작업이 필요하다.
하지만 이를 위해서 과도한 lock을 걸어버리면 오히려 그것 때문에 병목현상이 발생하고 성능이 저하될 수 있다.

• Multi-Threading vs Multi-Processing

Multi-Threading은 Multi-Processing보다 적은 메모리를 차지하고 빠른 Context Switching이 가능하다는 장점이 있지만, 오류로 인해 하나의 Thread가 죽으면 전체 Thread가 죽을 수도 있다는 단점이 있다.
반면 Multi-Processing은 하나의 Process가 죽더라도 다른 Process는 전혀 영향을 받지 않는다.

Scheduling

Scheduler란 한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할을 일컫는다.

이러한 Scheduling을 위해서 Scheduling Queue라는 것이 존재한다.

• Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.

1. Long Term Scheduler

   long-term스케줄러는 보조기억장치에 존재하는 프로세스 중 어떤 프로세스를 주 메모리로 load할 지 결정하는 역할을 해준다.
   메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다.

1. Short Term Scheduler

   CPU 와 메모리 사이의 스케줄링을 담당한다. Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정하는 Scheduler이다.

2. Medium Term Scheduler

   여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아내는 역할을 한다.
   현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.

그리고 CPU를 잘 사용하기 위해서 Process를 잘 배정할 필요가 있다. 이 과정을 CPU Scheduling이라고 부른다.

이러한 CPU Scheduling은 선점과 비선점 Scheduling으로 나뉜다.

1. 비선점 Scheduling

   프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이함)

   이러한 비선점 Scheduling에도 종류가 여러가지가 있다.

   • FCFS (First Come First Served)
   • SJF (Shortest Job First)
   • HRN (Hightest Response-ratio Next)

2. 선점 Scheduling

   OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리시간 예측 어려움)

   이러한 선점 Scheduling에도 종류가 여러가지가 있다.

   • Priority Scheduling
   • Round Robin
   • Multilevel-Queue
   • Multilevel-Feedback-Queue

이렇게 여러가지 CPU Scheduling 알고리즘이 있는데 이를 평가할 수 있는 척도가 있어야 한다. 그래야 어떤 알고리즘이 더 좋은지 알 수 있기 때문이다.
이러한 척도는 총 5가지가 있다.

1. CPU utilization : 계속 CPU를 사용할수 있도록 하기 위함. CPU가 컴퓨터가 켜져있는 동안 계속 동작한다면 100% 그리고 CPU가 한번도 동작하지 않는다면 0%이다.

2. Throughput : 특정 시간동안 실행될 수 있는 프로세스 몇개인가?

3. Turnaround time : 메모리에 들어가기 위해 기다리는 시간 + ready queue에서 기다리는 시간 + CPU 실행하는 시간 + I/O하는 시간

4. Waiting time : 프로세스가 ready queue에서 기다리는 시간의 총 합

5. Response time : 프로세스가 응답을 시작할 때까지 걸리는 시간

System Call

fork( ), exec( ), wait( )와 같은 것들을 Process 생성과 제어를 위한 System call이라고 부름.

• fork, exec는 새로운 Process 생성과 관련이 되어 있다.
• wait는 Process (Parent)가 만든 다른 Process(child) 가 끝날 때까지 기다리는 명령어임.

1. Fork

   새로운 Process를 생성할 때 사용하는 System Call임.

1. Exec

   child에서는 parent와 다른 동작을 하고 싶을 때는 exec를 사용할 수 있음.

2. Wait

   child 프로세스가 종료될 때까지 기다리는 Task이다.

Synchronization

동기화의 정의를 다루기전에 먼저 Race Condition과 Critical Section의 개념을 다룰 필요가 있다.

Race Condition이란 여러 Process들이 동시에 데이터에 접근하는 상황에서 어떤 순서로 데이터에 접근하느냐에 따라서 결과값이 달라질 수 있는 상황을 말한다.

Critical Section이란 동일한 자원을 접근하는 작업을 실행하는 코드 영역을 일컫는다. 또는 코드 상에서 Race Condition이 발생할 수 있는 특정 부분이라고도 말한다.

Process의 동기화란이런 Critical Section에서 발생할 수 있는 Race Condition을 막고 데이터의 일관성을 유지하기 위해서 협력 Process간의 실행 순서를 정해주는 메커니즘이다.

이러한 Critical Section상에서 발생할 수 있는 문제를 해결하기 위해서는 다음 조건들을 만족해야 한다.

1. Mutual Exculsion (상호 배제)

   이미 한 Process가 Critical Section에서 작업중이면 다른 모든 Process는 Critical Section에 진입하면 안된다.

2. Progress (진행)

   Critical Secion에서 작업중인 Process가 없다면 Critical Section에 진입하고자 하는 Process가 존재하는 경우에만 진입할 수 있어야 한다.

3. Bounded Waiting (한정 대기)

   Process가 Critical Section에 들어가기 위해 무한정 기다려서는 안된다.

이러한 Critical Section 문제를 해결하기 위해서 다음과 같은 해결책들이 존재한다.

• Mutex Lock (Mutual Exclusion Lock)

Mutex Lock은 이미 하나의 Process가 Critical Section에서 작업중이면 다른 Process들은 Critical Section에 진입할 수 없도록 한다.
하지만 이러한 방식은 Busy Waiting의 단점이 있다. Critical Section에 Process가 존재할때 다른 Process들이 계속 Critical Section에 진입하려고 시도하면서 CPU를 낭비하는 것이다.

이렇게 lock이 반환될때까지 계속 확인하면서 Process가 대기하고 있는 것을 Spin Lock이라고도 한다. Spin lock은 Critical Section에 진입을 위한 대기 시간이 짧을때 즉, Context Switching을 하는 비용보다 기다리는게 더 효율적인 특수한 상황에서 사용된다.

• Semaphores

Semaphore는 Busy Waiting이 필요 없는 동기화 도구이며, 여러 Process/Thread가 Critical Section에 진입할 수 있게 하는 Locking 메커니즘이다.

Semaphore는 Counter를 활용하여 동시에 자원에 접근할 수 있는 Process를 제한한다. 단순히 생각해서 공유 자원의 개수라고 생각하면 편하다. 이러한 Semaphore에는 2 종류가 있다.

1. Counting Semaphore: 자원의 개수만큼 존재하는 Semaphore
2. Binary Semaphore: 0과 1뿐인 Semaphore

Memory

Memory Management Strategy

각각의 프로세스 는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제 만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다.

Locality of Cache

Database

SQL vs NoSQL

SQL과 NoSQL은 각자 다음과 같은 뜻이 있다.

SQL: Structured Query Language
NoSQL: Not Only SQL

각자 쓰이는 장소가 다르다. SQL은 관계형 데이터베이스(RDBMS)에서 사용되고 NoSQL은 비 관계형 데이터베이스에서 사용된다.

이들은 각각 특성이 있을뿐, 장단으로 명확하게 나뉘지 않는다.

SQL의 특성:

• 명확하게 정의된 스키마가 있으며 데이터의 무결성을 보장한다.
• 관계는 각 데이터를 중복없이 한번만 저장하면 된다.
• 데이터의 스키마를 사전에 계획하고 알려야 한다. (나중에 수정하기 매우 힘들다)
• 관계를 맺고 있어서 Join문이 많은 복잡한 쿼리를 사용해야할 수도 있음
• 대체적으로 수직적 확장만 가능함. (DB 서버의 성능을 올리는 방향)

NoSQL의 특성:

• 명확하게 정의된 스키마가 없으며 유연한 데이터 구조를 지님
• 데이터를 Application이 필요로 하는 형태로 저장할 수 있음. 데이터의 I/O가 빨라짐.
• 수직 및 수평적 확장이 용이함.
• 데이터의 중복을 계속 업데이트할 필요가 있음.

Index

Index는 DB의 검색 속도를 높이기 위한 테크닉중 하나이다.

Index를 통해서 DB는 Table을 Full Scan하지 않고도 원하는 데이터를 찾을 수 있다. 이러한 Index는 대개 B+ Tree 구조로 저장되어 있어서 Index를 통한 검색을 더욱 빠르게 진행할 수 있다.

하지만 Index를 사용하게 되면 한 페이지를 동시에 수정할 수 있는 병행성이 줄어들고 Insert, Update, Delete 등의 Write 작업의 성능에 영향을 미칠 수 있다. 또한 Index를 관리하기 위해 저장 공간의 약 10%가 사용되므로 Write 연산이 빈번한 Table에 Index를 잘못 걸게 되면 오히려 성능이 저하될 수 있다.

Transaction

Transaction이란 DB의 상태를 변화시키기 위한 수행 단위를 일컫는다.
예를 들어서, 은행에서 송금을 처리하는 퀴리문들이 있다고 가정하자. 그렇다면 다음의 쿼리문들이 하나의 Transaction이다.

사용자 A의 계좌에서 만원을 차감한다 : UPDATE 문을 사용해 사용자 A의 잔고를 변경
사용자 B의 계좌에 만원을 추가한다 : UPDATE 문을 사용해 사용자 B의 잔고를 변경

위의 2개의 쿼리문이 하나의 Transaction이다. 2개의 쿼리문이 성공적으로 완료되어야만 하나의 Transaction이 성공하고 DB에 반영된다. (이를 Commit한다고 한다.)
반대로 둘중 하나라도 실패하게 된다면 모든 쿼리문을 취소하고 DB는 원상태로 돌아간다. (이를 Rollback이라고 한다.)

RDB에서 Transaction은 다음을 엄격하게 만족시켜야 한다.
ACID (Atomicity, Consistency, Isolation, Durability)

• Atomicity: 트랜잭션이 DB에 모두 반영되거나, 혹은 전혀 반영되지 않아야 된다.
• Consistency: 트랜잭션의 작업 처리 결과는 항상 일관성 있어야 한다.
• Isolation: 둘 이상의 트랜잭션이 동시에 병행 실행되고 있을 때, 어떤 트랜잭션도 다른 트랜잭션 연산에 끼어들 수 없다.
• Durability: 트랜잭션이 성공적으로 완료되었으면, 결과는 영구적으로 반영되어야 한다.

반대로 NoSQL DB에서는 완화된 ACID를 지원하는데, 이를 종종 BASE(Basically Avaliable, Soft state, Eventually consistent)라고 부르기도 한다.

• Basically Avaliable: 기본적으로 언제든지 사용할 수 있다는 의미를 가지고 있다.
• Soft state: 외부의 개입이 없어도 정보가 변경될 수 있다는 의미를 가지고 있다.
• Eventually consistent: 일시적으로 일관적이지 않은 상태가 되어도 일정 시간 후 일관적인 상태가 되어야한다는 의미를 가지고 있다.

BASE는 ACID와는 다르게, 데이터의 일관성보다는 가용성을 우선시하는 것이 특징이다. 어느 것이 좋다고 말을 할 수 없이 그냥 특성으로 받아들이는 것이 좋다.

Lock

DB에서 Lock은 Transaction 처리의 순차성을 보장하기 위해서 나온 개념이다. Lock은 여러 connection에서 동시에 동일한 자원을 요청할 경우 순서대로 한 시점에는 하나의 connection만 변경할 수 있게 해주는 역할을 한다.

Lock의 종류로는 Shared Lock과 Exclusive Lock이 있다. Shared Lock은 Read Lock이라고도 불리우며 Exclusive Lock은 Write Lock이라고도 불리운다.

1. Shared Lock: 공유 Lock은 데이터를 읽을 때 사용되어지는 Lock이다. 이런 공유 Lock은 공유 Lock 끼리는 동시에 접근이 가능하다.
2. Exclusive Lock: 베타 Lock은 데이터를 변경하고자 할 때 사용되며, 트랜잭션이 완료될 때까지 유지된다. 베타락은 Lock이 해제될 때까지 다른 트랜잭션(읽기 포함)은 해당 리소스에 접근할 수 없다.

deadlock

교착상태는 두 트랜잭션이 각각 Lock을 설정하고 다음 서로의 Lock에 접근하여 값을 얻어오려고 할 때 이미 각각의 트랜잭션에 의해 Lock이 설정되어 있기 때문에 양쪽 트랜잭션 모두 영원히 처리가 되지않게 되는 상태를 말한다. 교착상태가 발생하면 DBMS가 둘 중 한 트랜잭션에 에러를 발생시킴으로써 문제를 해결합니다. 교착상태가 발생할 가능성을 줄이기 위해서는 접근 순서를 동일하게 하는것이 중요하다.

교착 상태의 빈도를 낮추는 방법:

1. 트랜잭션을 자주 커밋한다.
2. 정해진 순서로 테이블에 접근한다. 트랜잭션들이 동일한 테이블 순으로 접근하게 한다.
3. 읽기 잠금 획득 (SELECT ~ FOR UPDATE)의 사용을 피한다.
4. 한 테이블의 복수 행을 복수의 연결에서 순서 없이 갱신하면 교착상태가 발생하기 쉽다, 이 경우에는 테이블 단위의 잠금을 획득해 갱신을 직렬화 하면 동시성을 떨어지지만 교착상태를 회피할 수 있다.

Redis

Redis는 In-Memory기반의 Key-Value 데이터 구조의 DB이다.

Redis는 메모리(RAM)에 저장해서 디스크 스캐닝이 필요없어 매우 빠른 장점이 존재한다. 캐싱도 가능해 실시간 채팅에 적합하며 세션 공유를 위해 세션 클러스터링에도 활용된다.

High Avaliablity Strategy

High Avaliablity on SQL DB

MySQL 같은 SQL DB에서 HA를 구축하는 전략중에 가장 보편적인 방법은 Master-Slave Node를 구성하는 방법이다.
Master Node는 Read/Write 연산을 둘 다 담당할 수 있고 Slave Node는 Read Only이다.
Slave Node가 Master Node의 Binary log를 읽어서 Slave DB의 Relay log로 복사 후 반영하여 변경된 데이터를 동기화하는 방식이 잘 알려진 Replication이다.

Slave 대수에 따라 수 초의 Delay가 발생할 수 있어 실시간이 매우 중요한 데이터 읽기 트랜잭션은 Master DB에서 읽게 하고 Slave DB는 이외 읽기 트랜잭션을 적용하는 것이 일반적이다.

필자는 Proxy SQL을 사용하여 Application에서 들어오는 Transaction을 Master/Slave Node에 분류하여 처리하게 하였고 Read 연산의 경우 Slave node들에 Round Robin으로 Load Balancing을 진행하였다.

그리고 여기서 또 중요한 점이 한가지 존재한다. Master가 죽었을 때 어떻게 Slave들이 데이터의 일관성을 유지할 것인지가 굉장히 중요한 논점이다.

High Avaliablity on Redis

Redis에서 HA를 적용하는 방법은 크게 2가지가 있다.

• Master/Slave Node with Redis Sentinel

  이는 SQL에서와 마찬가지로 Read/Write 연산을 담당하는 Master Node와 Read Only 연산을 담당하는 Slave Node로 나눈 뒤에, 각 Node의 상태를 Redis Sentinel이 감시하게 하는 방법을 사용한다.
  Redis Sentinel은 최소 3대로 Cluster를 이루어 Master의 생존 여부를 투표로 결정하고 Master가 죽은 경우에는 투표를 통해서 살아있는 Slave Node를 Master로 승격시킨다.

• Redis Cluster

  Redis Cluster의 경우, Redis Sentinel 없이 최소 3대의 Master/Slave Node가 서로를 모니터링 하면서 고 가용성을 만든다.
  데이터세트을 여러 노드로 자동분할 하는 기능(샤딩) (최대 1000개)을 가지고 있으며 Gossip Protocol을 통해서 서로 통신을 진행한다.

  Master Node에 장애가 발생할 경우, Master의 Slave는 Gossip Protocol을 통해 장애를 파악한다.
  이후 스스로 Master로 승격하여 Master를 대신한다. 장애가 발생한 Master가 복구될경우, 스스로 Slave로 강등

ORM

ORM은 Object Relational Mapping의 약자로써, 풀어서 설명하자면 우리가 OOP(Object Oriented Programming)에서 쓰이는 객체라는 개념을 구현한 클래스와 RDB(Relational DataBase)에서 쓰이는 데이터인 테이블 자동으로 매핑(연결)하는 것을 의미한다.

쌩 SQL Query를 작성하는 것보다 ORM이 가지는 장단점은 다음과 같다.

장점)

• 완벽한 객체지향적 코드: ORM을 사용하면 SQL문이 아닌 Class의 Method를 통해서 DB를 조작할 수 있다. 이는 개발자가 Object Model만을 이용해서 Programming을 하는데 집중할 수 있게 해준다.
• 재사용/유지보수/리펙토링의 용이: ORM은 기존 객체와 독립적으로 작성되어있으며, Object로 작성되어 있기 때문에 재활용이 가능하다. 또한 Mapping하는 정보가 명확하기 때문에 ERD를 보는 의존도를 낮출 수 있다.
• DBMS의 종속성 하락: 객체 간의 관계를 바탕으로 SQL문을 자동으로 생성하고, 객체의 자료형 타입까지 사용할 수 있기 때문에 RDBMS의 데이터 구조와 객체지향 모델 사이의 간격을 좁힐 수 있다.

단점)

• ORM은 명확한 한계가 존재한다: Project가 커지면 그만큼 구현의 난이도가 올라가고, 이때 설계를 부실하게 하면 오히려 속도가 떨어지는 문제점이 생긴다. 또한 그 뿐만 아니라 일부 SQL의 경우에는 속도를 위해서 별도의 튜닝이 필요한데, 이때는 결국 SQL문을 직접 작성해야 한다.
• Object-Relation 간의 불일치
  • 세분성: 경우에 따라서 데이터베이스에 있는 테이블 수보다 더 많은 클래스를 가진 모델이 생길 수 있다.
  • 상속성: RDB에서는 객체지향의 특징인 상속 기능이 존재하지 않는다.
  • 연관성: 객체지향 언어는 방향성이 있는 객체의 참조를 사용하여 연관성을 나타내지만, RDBMS는 방향성이 없는 foreign key를 통해서 이를 나타낸다.

Web

TCP / UDP

우선 TCP 통신과 UDP 통신부터 알아보자.

• TCP 통신

  TCP는 TCP/IP 모델의 3계층, Transport 계층의 프로토콜이다.
  기본적으로 신뢰성 있는 데이터 전송을 위한 연결 지향형 프로토콜이다.
  TCP는 우선 HandShake 방식을 통해서 데이터를 송/수신한다. 예를 들어서 TCP에서는 송신자가 데이터를 전송할 경우, 다음과 같은 검증 과정을 거친다.

  1. 데이터를 제대로 수신했는지
  2. 에러는 발생하지 않았는지
  3. 수신 속도에 비해 전송 속도가 너무 빠르지는 않았는지 (흐름 제어)

  4. 네트워크가 혼잡하지는 않은지 (혼잡 제어)

     이러한 기본적인 사항들을 지키는 Protocol이기 때문에 TCP를 높은 신뢰성을 보장한다고 말한다.

     여기서 흐름 제어와 혼잡 제어를 보다 더 정확하게 설명하면 다음과 같다.

  • 흐름 제어

    수신측이 송신측보다 데이터 처리 속도가 빠르면 문제없지만, 송신측의 속도가 빠를 경우 문제가 생긴다. 수신측에서 제한된 저장 용량을 초과한 이후에 도착하는 데이터는 손실 될 수 있으며, 만약 손실 된다면 불필요하게 응답과 데이터 전송이 송/수신 측 간에 빈번히 발생한다.
    아래서 설명하겠지만, Receiver Buffer의 크기만큼 수신자는 데이터를 읽을 수 있다. 따라서 수신측의 데이터 처리 속도가 송신측보다 느리면 문제가 발생한다.

    해결 방법:

    • Stop and Wait : 매번 전송한 패킷에 대해 확인 응답을 받아야만 그 다음 패킷을 전송하는 방법
    • Sliding Window (Go Back N ARQ): 수신측에서 설정한 윈도우 크기만큼 송신측에서 확인응답없이 세그먼트를 전송할 수 있게 하여 데이터 흐름을 동적으로 조절하는 제어기법

  • 혼잡 제어

    송신측의 데이터는 지역망이나 인터넷으로 연결된 대형 네트워크를 통해 전달된다. 만약 한 라우터에 데이터가 몰릴 경우, 자신에게 온 데이터를 모두 처리할 수 없게 된다.
    이런 경우 호스트들은 또 다시 재전송을 하게되고 결국 혼잡만 가중시켜 오버플로우나 데이터 손실을 발생시키게 된다. 따라서 이러한 네트워크의 혼잡을 피하기 위해 송신측에서 보내는 데이터의 전송속도를 강제로 줄이게 되는데, 이러한 작업을 혼잡제어라고 한다.

이러한 TCP는 전체적으로 다음과 같은 전송 과정을 거쳐서 데이터를 전송한다.

* Application Layer: Sender Application layer가 socket에 data를 전송함.
* Transport layer: data를 segment에 감싼다. 그리고 network layer에 넘겨준다.
* Network layer - physical layer에서 도착지에 데이터를 전송한다. 이때 Sender의 send buffer에 data를 저장하고 receiver는 receive buffer에 data를 저장한다.
* Application에서 준비가 되면 buffer에 있는 데이터를 읽음 (흐름 제어의 핵심은 이 receiver buffer가 넘치지 않게 하는 것에 있다.)
* Receiver는 Receive Window : receiver buffer의 남은 공간을 홍보함.

• UDP

  UDP의 경우에는 TCP 처럼 신뢰성을 보장하지 않는다. 하지만 그만큼 신뢰성을 보장하기 위한 흐름 제어/혼잡 제어같은 처리가 필요 없어서 overhead가 발생하지 않고 빠른 처리 및 경량화된 헤더를 가지게 된다. 이러한 이유 때문에 UDP는 다음과 같은 연속성과 성능이 더 중요한 분야에 사용되게 된다.

  • 인터넷 전화
  • 온라인 게임
  • 멀티미디어 스트리밍

TCP 3/4way handshake

TCP 통신은 연결을 수립/종료할때 각각 3/4 way handshake를 통해서 진행하게 된다.
먼저 연결을 수립하는 과정인 3 way handshake를 생각해 보자.

3 way handshake는 총 3번의 통신 과정을 거쳐서 내가 누구와 통신중인지, 내가 받아야할 데이터의 sequence number는 몇번인지 등등의 정보를 주고 받으면서 연결의 상태를 생성하게 된다.

1. 먼저 수신자는 LISTEN 상태로 대기를 하게 된다. 이때, 수신자는 요청자가 요청을 하기 전까지는 대기를 하게 되는데 이 상태를 수동 개방이라고 하고 수신자를 Passive Opener라고 한다.
2. 요청자가 수신자에게 연결 요청을 하면서 랜덤한 숫자인 Sequence Number를 생성하여 SYN 패킷에 담아 보낸다. 이 Sequence Number를 활용하여 계속 새로운 값을 만들고 서로 확인하며 연결 상태와 패킷의 순서를 확인하게 된다.
3. 수신자는 요청자가 보낸 SYN 패킷을 잘 받았으면 SYN + ACK 패킷을 보낸다. 여기에는 제대로된 Sequence Number를 받았다는 의미인 승인 번호값이 들어있으며 이는 Sequence Number + 상대방이 보낸 데이터의 크기(byte)의 값을 가지고 있다. 하지만 맨 처음에는 1을 더해서 보낸다.
4. 요청자가 이러한 ACK의 값이 Sequence Number와 1차이가 나는 것을 확인하였으면 다시 확인차 ACK 패킷을 보내 연결이 수립된다.

1번이 초기 상태이고 2~4번부터 3 Way Handshake의 과정이다. 이렇게 3단계의 과정을 거쳐서 TCP의 연결을 수립한다.

이제 4 Way Handshake에 대해서 알아보도록 하겠다.
이는 연결을 종료할때 사용하는 과정이다. 굳이 이러한 과정을 거쳐서 연결을 종료하는 이유는 연결을 그냥 끊었다가는 다른 한쪽이 연결이 끊겼는지 아닌지 알 방법이 없기 때문이다. 이러한 과정을 총 4번의 통신을 거치기에 4 way handshake라고 한다.

1. 먼저, 연결을 종료하고자 하는 요청자가 상대에게 FIN 패킷을 보내면서 FIN_WAIT 상태로 들어가게 된다.
2. 수신자는 요청자가 보낸 Sequence Number + 1로 승인 번호를 만들어서 다시 요청자에게 ACK로 응답해주면서 CLOSE_WAIT 상태로 들어가게 된다. 이때 요청자는 자신이 받은 값이 Sequence Number + 1이 맞는지 다시 확인해 본다.
3. 수신자는 자신이 처리할 데이터가 더 없다면 FIN을 다시 한번 요청자에게 보내고 LAST_ACK 상태에 들어간다.
4. 요청자는 FIN을 수신자로부터 받고 다시 ACK 패킷을 수신자에게 보내준다. 그럼 수신자는 완벽하게 요청을 끊는 것이다.

TLS/SSL

TLS는 Transport Layer Security의 약자이고 SSL은 Secure Socket Layer의 약자이다.
SSL은 암호화 기반의 인터넷 보안 프로토콜이다. TLS의 전신인 이 프로토콜은 전달되는 모든 데이터를 암호화하고 특정 유형의 사이버 공격 또한 차단한다.
하지만 SSL은 3.0 이후로 업데이트 되지 않고 있으며 여러 취약점들이 알려져 사용이 중된되었다. 따가서 이렇게 개발된 최신 암호화 프로토콜이 TLS이다.

TLS 는 SSL의 업데이트 버전으로 SSL의 최종버전인 3.0과 TLS의 최초버전의 차이는 크지않으며, 이름이 바뀐것은 SSL을 개발한 Netscape가 업데이트에 참여하지 않게 되어 소유권 변경을 위해서였다고 한다.
결과적으로 TLS는 SSL의 업데이트 버전이며 명칭만 다르다고 볼 수 있다.

SSL/TLS는 handshake를 통해서 실제 데이터를 주고 받기 전에 서로 연결 가능한 상태인지 파악을 하게 된다.

1. Client Hello

   Client는 Server에게 다음과 같은 정보를 넘겨주면서 Hello라는 패킷을 보낸다.

   • Client에서 생성한 Random 값
   • Client가 지원하는 암호화 방식
   • (이전에 HandShake가 일어났을 경우) Session ID

2. Server Hello

   Server는 Client에게 다음과 같은 정보를 전달한다.

   • Server에서 생성한 Random 값
   • Client가 제공한 암호화 방식중 Serve가 선택한 암호화 방식
   • 인증서

3. Certificate

   Server가 자신의 TLS/SSL 인증서를 Client에게 전달한다. Client는 Server가 보낸 CA(Certifiacte Authority)의 개인키로 암호화된 SSL 인증서를 이미 모두에게 공개된 CA의 공개키를 사용해 복호화 한다. 즉, 인증서를 검증하는 과정을 거친다.

4. Server Key Exchange / Hello Done

   Server Key Exchange는 Server의 공개키가 TLS/SSL 인증서 내부에 없을 경우 Server가 직접 이를 전달하는 것을 의미한다. 공개키가 인증서 내부에 있으면 이 과정은 생략된다.

5. Client Key Exchange

   실제로 데이터를 암호화 하는 키(대칭키)를 Client가 생성해서 SSL 인증서 내부에서 추출한 Server의 공개키를 이용해 암호화한 뒤에, Server에 전달한다. 여기서 전달된 대칭키가 SSL Handshake의 목적이자, 실제 데이터를 암호화 하게될 비밀키이다.

6. Change Cipher Spec / Finished

   Client, Server가 모두 서로에게 보내는 Packet으로 교환할 정보를 모두 교환환 뒤에, 통신을 할 준비가 되었음을 알리는 Packet이다. 이것으로 Handshake는 종료된다.

이를 요약하면 다음과 같다.

ClientHello(암호화 알고리즘 나열 및 전달) - > Serverhello(암호화 알고리즘 선택) - > Server Certificate(인증서 전달) - > Client Key Exchange(데이터를 암호화할 대칭키 전달) - > Client / ServerHello done (정보 전달 완료) - > Fisnied (SSL Handshake 종료)

HTTP 1.0/1.1/2.0

HTTP의 명확한 정의는 다음과 같다.

WWW 상에서 정보를 주고 받을 수 있는 프로토콜. 주로 HTML 문서를 주고 받는 데에 쓰인다.

HTTP는 TCP위에서 돌아가는 Application Level의 Protocol이며 기본적으로 Stateless Protocol이다.

HTTP는 1.0과 1.1, 2.0 그리고 최근데 3.0이 나왔는데, 1.0과 1.1의 차이를 비교하면서 1.0과 1.1을 논하도록 하고 1.1과 2.0의 차이를 논하도록 하겠다.

HTTP 1.0과 1.1의 차이점은 다음과 같다.

• Connection 유지

  1.0과 1.1의 차이는 TCP Session을 유지할 수 있느냐 없느냐이다. TCP는 Handshake를 통해서 연결을 수립하는데 HTTP/1.0를 통해서 통신을 할때마다 이를 끊고 다시 수립하는 과정이 있어야 했다. 이를 보완하려면 Persistence Connection을 지원하는 Client는 Server에게 요청을 보낼때 connection:keep-alive header를 통해서 Persistence Connection을 수립해야 했다. 그리고 Server는 응답에서 똑같은 Header를 넣어서 보낸다.

  하지만 HTTP/1.1은 이를 기본으로 지원한다. 즉, 굳이 Connection Header 를 사용하지 않아도 모든 요청과 응답은 기본적으로 Persistent Connection을 지원하도록 되어 있으며 필요 없을 경우(HTTP 응답 완료 후 TCP 연결을 끊어야 하는 경우) Connection Header를 사용한다.

  Keep-Alive 를 통해 얻을 수 있는 장점으로는 단일 시간 내의 TCP 연결을 최소화 함으로써 CPU와 메모리 자원을 절약할 수 있고 네트워크 혼잡이나 Latency 에 대한 경우의 수를 줄일 수 있다는 점이다.

  • Pipelining

    HTTP 1.0 에서는 HTTP 요청들의 연결을 반복적으로 끊고 맺음으로서 서버 리소스적으로 비용을 요구한다.

    HTTP 1.1 에서는 다수의 HTTP Request 들이 각각의 서버 소켓에 Write 된 후, Browser는 각 Request들에 대한 Response를 순차적으로 기다리는 문제를 해결하기 위해 여러 요청들에 대한 응답 처리를 뒤로 미루는 방법을 사용한다.

    Pipelining이 적용되면 하나의 Connection으로 다수의 Request와 Response를 처리할 수 있고 Network Latency를 줄일 수 있게 된다.

• Host Header

  HTTP 1.0 환경에서는 하나의 IP에 여러 개의 도메인을 운영할 수 없었지만 HTTP 1.1 부터 가능하게 된다.

  HTTP 1.1 에서 Host 헤더의 추가를 통해 비로소 Virtual Hosting이 가능해졌다.

• 향상된 Authentication Prcedure

  HTTP 1.1 에서 다음 2개의 헤더가 추가된다.

  • proxy-authentication

  • proxy-authorization

    실제 Server에서 Client 인증을 요구하는 www-authentication 헤더는 HTTP 1.0 에서부터 지원되어 왔으나, Client와 Server 사이에 프록시가 위치하는 경우 프록시가 사용자의 인증을 요구할 수 있는 방법이 없었다.

그리고 다음과 같은 특성을 가진 HTTP/2.0이 나왔다.

• Multiplexed Streams (한 커넥션에 여러개의 메세지를 동시에 주고 받을 수 있음)
• 요청이 커넥션 상에서 다중화 되므로 HOL(Head Of Line) Blocking 이 발생하지 않음
• Stream Prioritization (요청 리소스간 의존관계를 설정)
• Header Compression (Header 정보를 HPACK 압축 방식을 이용하여 압축 전송)
• Server Push (HTML문서 상에 필요한 리소스를 클라이언트 요청없이 보내줄 수 있음)
• 프로토콜 협상 메커니즘 - 프로토콜 선택, 예. HTTP / 1.1, HTTP / 2 또는 기타.
• HTTP / 1.1과의 높은 수준의 호환성 - 메소드, 상태 코드, URI 및 헤더 필드
• 페이지 로딩 속도 향상

기존 HTTP는 Body가 문자열로 이루어져 있지만, HTTP 2.0 부터는 Binary framing layer 라고 하는 공간에 이진 데이터로 전송된다.

HTTP Cache

HTTP Cache는 이미 가져온 데이터나 계산된 결과값의 복사본을 저장함으로써 처리 속도를 향상시키며, 이를 통해 향후 요청을 더 빠르게 처리할 수 있다.

브라우저가 시도하는 모든 HTTP 요청은 먼저 브라우저 캐시로 라우팅되어, 요청을 수행하는데 사용할 수 있는 유효한 캐시가 있는지를 먼저 확인한다. 만약 유효한 캐시가 있으면, 이 캐시를 읽어서 불필요한 전송으로 인해 발생하는 네트워크 대기시간, 데이터 비용을 모두 상쇄한다.

요약하자면 Cache의 효과는 다음과 같다.

• 불필요한 데이터 전송을 줄여 네트워킹 비용을 줄여준다.
• 거리로 인한 지연시간을 줄여 웹페이지를 빨리 불러올 수 있게 된다.
• 서버에 대한 요청을 줄여 서버의 부하를 줄인다.

RESTful API

Representational State Transfer의 약자로 REST이다. 이는 여러 특성을 가지고 있는데 이 특성에 부합하는 API를 RESTful API라고 한다.
결국 REST는 다음과 같이 정의된다.

자원을 이름(자원의 표현)으로 구분하여 해당 자원의 상태(정보)를 주고 받는 모든 것을 의미한다.

자세한 정의를 말해보자면 자원의 표현은 HTTP URI로 하며 HTTP Method를 통해 해당 자원의 CRUD를 적용하는 것을 RESTful 하다고 표현한다.

Restful API는 흔히 Stateless라고 표현하고 이의 특징이 존재한다.
Restful API를 구현하는 절대 조건은 서버가 Client의 정보를 어느 것도 저장하지 않는다는 것이다. 이렇게 구현하는 절대적인 이유는 서버의 Scalablity이다.

Sync / Async / Blocking / Non-Blocking

제목의 4가지 개념은 각기 다른 것이다. Server에서 어떻게 요청을 처리할 것인지를 나타내고 있다. 각각 다음과 같은 의미를 지닌다.

• Synchronous: A함수가 B 함수를 호출할때, B 함수의 결과를 A함수에서 처리함.
• ASynchronous: A함수가 B 함수를 호출할때, B 함수의 결과를 B함수에서 처리함. (Callback)
• Blocking: A함수가 B함수를 호출할때, B함수가 자신의 작업이 종료되기 전까지 A함수에게 제어권을 넘겨주지 않음
• Non-Blocking: A 함수가 B 함수를 호출할때, B함수가 바로 제어권을 A 함수에게 넘겨주면서 A 함수가 다른 일을 할 수 있도록 함.

Blocking IO / Non-Blocking IO

I/O 작업은 Kernel Level에서만 수행이 가능하다. 따라서 Process나 Thread는 Kernel에게 I/O를 요청해야만 한다.

이때, I/O를 Blocking 방식으로 처리하느냐 Non-Blocking 방식으로 처리하느냐에 따라서 효율성이 다르다.

1. Blocking I/O

   Blocking 방식으로 I/O를 구현하면 다음과 같이 I/O를 처리해야 한다.

   • Process나 Thread가 Kernel에게 I/O를 요청하는 함수를 호출함.

   • Kernel이 작업을 완료하면 작업 결과를 반환받음.

     이렇게 되면 I/O 작업이 진행되는 동안 Process/Thread는 자신의 작업을 중단한 채로 대기한다. 이는 Resource의 낭비가 심하다. (I/O 작업이 CPU를 거의 사용하지 않으므로)

     만약 여러 Client가 접속하는 서버를 Blocking 방식으로 구현하려는 경우 client별로 별도의 Thread를 생성해서 처리해야한다. 이로인해 많아진 Thread들의 Context Switching 비용이 늘어나서 효율성이 감소하게 된다.

2. Non-Blocking I/O

   Non-Blocking 방식으로 I/O를 구현하면 I/O 작업이 진행되는 동안 User Process의 작업을 중단하지 않는다.

   • User Process가 recvfrom 함수 호출 (커널에게 해당 Socket으로부터 data를 받고 싶다고 요청함)
   • Kernel은 이 요청에 대해서, 곧바로 recvBuffer를 채워서 보내지 못하므로, “EWOULDBLOCK”을 return함.
   • Blocking 방식과 달리, User Process는 다른 작업을 진행할 수 있음.
   • recvBuffer에 user가 받을 수 있는 데이터가 있는 경우, Buffer로부터 데이터를 복사하여 받아옴. 이때, recvBuffer는 Kernel이 가지고 있는 메모리에 적재되어 있으므로, Memory간 복사로 인해, I/O보다 훨씬 빠른 속도로 data를 받아올 수 있음.
   • recvfrom 함수는 빠른 속도로 data를 복사한 후, 복사한 data의 길이와 함께 반환함.

Javascript/Nodejs

Javascript

• var, let, const 차이점

var: 함수 스코프를 갖는다. 변수를 한번 더 선언해도 에러가 발생하지 않는다. 그래서 es6 업데이트로 let과 const 도입되었다.

let : 블록 스코프를 갖는다. 예를들어 if문 for문 while문 중괄호{}안에 선언 되었을 경우, 변수가 그 안에서 생성되고 사라진다.

const : 블록 스코프, 상수를 선언 할 때 사용한다. 선언과 동시에 할당 되어야합니다. (재할당하면 오류발생)

• hoisting

hoisting은 코드가 실행하기 전 변수선언/함수선언이 해당 스코프의 최상단으로 끌어 올려진 것 같은 현상을 말한다.

• Temporal Dead Zone

const와 let은 범위가 지정된 변수를 갖는다.
이 둘의 호이스팅이 실행 되기전 까지 액세스 할수 없는 것을 TDZ라 한다.

즉, let/const선언 변수는 호이스팅되지 않는 것이 아니다.
스코프에 진입할 때 변수가 만들어지고 TDZ(Temporal Dead Zone)가 생성되지만, 코드 실행이 변수가 실제 있는 위치에 도달할 때까지 액세스할 수 없는 것이다.
let/const변수가 선언된 시점에서 제어흐름은 TDZ를 떠난 상태가 되며, 변수를 사용할 수 있게 된다.

NodeJS

• NodeJS

NodeJS는 Single Threaded Event Driven Asynchronous Non-Blocking Javascript Engine이다. 하나의 스레드로 동작하지만, Asynchronous I/O 작업을 통해 요청들을 서로 Blocking하지 않는다.
즉, 동시에 많은 요청을 비동기로 처리함으로써 Single Threaded이더라도 많은 요청들을 Asynchronous하게 처리할 수 있다.

어떻게 그것이 가능하느냐? Single Threaded로 동작하면서 Blocking 작업을 어떻게 Non Blocking으로 Asynchronous하게 처리할 수 있을까?
그것은 NodeJS에서 일부 Blocking이 필요한 작업을 libuv의 Thread Pool에서 수행되기 때문이다.

• Event Loop (JS Engine)

Event Loop라는 것을 설명하기 전에 Event Driven의 개념부터 짚고 넘어가야 한다.

Event Driven이라는 것은 Event가 발생할때 미리 지정해둔 작업을 수행하는 방식을 의미한다.

NodeJS는 EventListener에 등록해둔 Callback함수를 수행하는 방식으로 이를 처리한다.

Event Loop는 Main Thread 겸 Single Thread로써 Busniess Logic을 수행한다. 이를 수행하는 도중에 Blocking I/O 작업을 만나면 Kernel Asynchronous 또는 자신의 Worker Thread Pool에게 넘겨주는 역할을 한다. GC 또한 Event Loop에서 돌아가고 있다.

위에서 Blocking Task(api call, DB Read/Write 등)들이 들어오면 Event Loop가 uv_io에게 내려준다고 하였다. libuv는 Kernel단(윈도우의 경우 IOCP, 리눅스는 AIO)에서 어떤 비동기 작업들을 지원해주는지 알고 있기때문에, 그런 종류의 작업들을 받으면, 커널의 Asynchronous 함수들을 호출한다. 작업이 완료되면 시스템콜을 libuv에게 던져준다. libuv 내에 있는 Event Loop에게 Callback으로서 등록된다.

그러한 Event Loop는 다음과 같은 phase로 동작하고 있다.
각 phase들은 Queue를 가지고 있으며 이 Queue에는 특정 이벤트의 Callback들을 넣고 Event Loop가 해당 Phase를 호출할때 실행된다.

Timers: setTimeout()과 setInterval과 같은 Timer 계열의 Callback들이 처리된다.
I/O Callbacks: Close Callback, Timer로 스케쥴링된 Callback. setImmediate()를 제외한 거의 모든 Callback들을 집핸한다.
idle, prepare: 내부용으로만 사용 모든 Queue가 비어있으면 idle이 되서 tick frequency가 떨어짐
poll: Event Loop가 uv__io_poll()을 호출했을때 poll Queue에 있는 Event, Callback들을 처리함.
check: setImmediate() Callback은 여기서 호출되고 집행된다.
Close Callback: .on(‘close’, …) 같은 것을이 처리됨.

Event Loop는 round-robin 방식으로 Nodejs Process가 종료될때까지 일정 규칙에 따라 여러개의 Phase들을 계속 순회한다. Phase들은 각각의 Queue들을 관리하고, 해당 Queue들은 FIFO 순서로 Callback Function들을 처리한다.

• NodeJS module

module.exports: nodejs에서 .js파일을 만들어서 객체를 따로 모아놓은 것들을 module이라고 부른다. 그것을 외부로 export하기 위해서 module.exports 객체로 만들어 놓은 것이다.
exports: 이는 module.exports를 call by reference로 가리키고 있는 변수이다. 따라서 이를 바로 쓸 수는 없고 다른 property로 지정해서 써야한다.

• Async/Await, Promise

Promise는 JS Asynchoronous 처리에 사용되는 객체이다.
그리고 이 Promise 객체를 반환하게 하는 decorator가 async이고 Async 함수 안에서 다른 Async 작업의 Blocking을 담당하는 것이 await이다.

Object Oriented Programming Basic

Properties of OOP

OOP에는 4가지 특성이 있다.

1. 추상화: 필요로 하는 속성이나 행동을 추출하는 작업
2. 캡슐화: 낮은 결합도를 유지할 수 있도록 설계하는 것
3. 상속: 일반화 관계(Generalization)라고도 하며, 여러 개체들이 지닌 공통된 특성을 부각시켜 하나의 개념이나 법칙으로 성립하는 과정
4. 다형성: 서로 다른 클래스의 객체가 같은 메시지를 받았을 때 각자의 방식으로 동작하는 능력

객체 지향 설계 과정

• 제공해야 할 기능을 찾고 세분화한다. 그리고 그 기능을 알맞은 객체에 할당한다.
• 기능을 구현하는데 필요한 데이터를 객체에 추가한다.
• 그 데이터를 이용하는 기능을 넣는다.
• 기능은 최대한 캡슐화하여 구현한다.
• 객체 간에 어떻게 메소드 요청을 주고받을 지 결정한다.

5 Principle

SOLID라고 부르는 5가지 설계 원칙이 존재한다.

• SRP(Single Responsibility) - 단일 책임 원칙

  클래스는 단 한 개의 책임을 가져야 한다.

  클래스를 변경하는 이유는 단 한개여야 한다.

  이를 지키지 않으면, 한 책임의 변경에 의해 다른 책임과 관련된 코드에 영향이 갈 수 있다.

• OCP(Open-Closed) - 개방-폐쇄 원칙

  확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.

  기능을 변경하거나 확장할 수 있으면서, 그 기능을 사용하는 코드는 수정하지 않는다.

  이를 지키지 않으면, instanceof와 같은 연산자를 사용하거나 다운 캐스팅이 일어난다.

• LSP(Liskov Substitution) - 리스코프 치환 원칙

  상위 타입의 객체를 하위 타입의 객체로 치환해도, 상위 타입을 사용하는 프로그램은 정상적으로 동작해야 한다.

  상속 관계가 아닌 클래스들을 상속 관계로 설정하면, 이 원칙이 위배된다.

• ISP(Interface Segregation) - 인터페이스 분리 원칙

  인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.

  각 클라이언트가 필요로 하는 인터페이스들을 분리함으로써, 각 클라이언트가 사용하지 않는 인터페이스에 변경이 발생하더라도 영향을 받지 않도록 만들어야 한다.

• DIP(Dependency Inversion) - 의존 역전 원칙

  고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

  저수준 모듈이 고수준 모듈에서 정의한 추상 타입에 의존해야 한다.

  즉, 저수준 모듈이 변경돼도 고수준 모듈은 변경할 필요가 없는 것이다.

Index

1. Post의 주제 소개
2. 강의 내용

Post의 주제 소개

이 카테고리의 포스트는 Docker에 대해서 더 딥 다크한 부분까지 알고 싶어하는 사람들을 위해서 만들어 나갈 것이다. 먼저 그 전에 Docker에 대해서 잠깐 짚고 넘어가는 것이 좋을 것 같다.

Docker

Docker는 수 많은 Containerization Software 중 하나이다. open source이며 가장 유명하기도 하다. 그렇다면 Containerization은 무엇일까?

Containerization

여기서는 RedHat 공식 홈페이지에서 나온 문구를 인용해 보도록 하겠다.

컨테이너화란 소프트웨어 코드를 라이브러리, 프레임워크 및 기타 종속성과 같은 필수 요소와 함께 패키지에 포함하여 각자의 “컨테이너”로 분리하는 것을 뜻합니다.

간단하게 말하면 우리가 작성한 Application을 운영 체제 내에서 하나의 고립된 공간을 만들어 패키징 하는 것을 말한다.

주로 사람들이 Virtual Machine하고 비교를 하곤 한다. 하지만 필자의 생각으로는 비교 자체가 조금 잘못되었다. Virtual Machine은 OS Kernel 바로 위에 Hypervisor라는 가상화 layer를 추가하여 별도의 OS를 올릴 수 있게 가상화를 하는 것이다. (밑의 그림이 아주 좋은 예시이다.)
그에 반해서 Docker는 기존에 OS에서 돌아가는 Process의 일종이다. 하지만 그 Process가 사용할 수 있는 PID, Network Interface, CPU, Memory 등의 여러 자원들을 다른 Process들과 고립시켜서 마치 독립된 머신 위에서 돌아가는 것 “처럼” 만드는 것이다.
둘은 엄밀히 다른 목적을 가지고 사용되어야 한다. 누가 더 좋냐의 문제가 아니라 때에 맞춰서 적절한 기술을 사용해야하는 것이다.

그래서 이 카테고리에 해당하는 포스트들은 뭔 내용을 다루는가?
답은 간단하다

Docker는 어떻게 Process를 Isolation 하는가?

Docker가 어떤 기술을 사용해서 process를 고립시키는지 OS, Computer Network의 관점에서 서술할 것이다.
여기서는 어떻게 Docker를 사용하는 방법 같은 것은 일체 다루지 않을 것이다. 이미 Docker를 능숙하게 다룰 수 있는 사람이 어떻게 하면 좀 더 효율적으로 Docker를 사용할 수 있는지에 대한 Insight를 제공하는 목적으로 서술될 것이다. 그래서 제목이 Deep Dark Docker이다.

진짜 이딴걸 누가 볼까 싶다

강의 내용

강의는 크게 다음과 같은 주제를 필두로 전개될 것이다.

1. PID/Network/IPC Isolation - Linux Namespace
2. Network Isolation Advanced - Docker Network
3. Computing Resource Isolation - Cgorup
4. Docker File System Isolation - Docker Volume, linux Namespace

우선 Docker가 process id, network interface, IPC 같은 자원들을 어떻게 isolation하는지를 다룰 것이다. 이때 주요하게 쓰이는 기술이 바로 Linux Namespace이다. 따라서 이를 Deep Dark하게 다뤄볼 것이다.

그리고 Web Service를 구축하는데 있어서 가장 중요한 부분인 “어떻게 Network를 구성할 것이가”에 대한 내용을 다룰 것이다. 이는 Docker Network를 통해서 조금 실용적으로 다뤄볼까 한다.

다음으로는 Docker가 어떻게 CPU, RAM Memory 같은 자원을 Container에게 할당하고 제한하는지를 알아볼 것이다. 이때 사용되는 기술이 Control Group인데, 이 또한 Deep Dark하게 알아보고자 한다.

그리고 마지막으로 Docker의 File System에 대해서 알아볼 것이다. 이는 비단 Docker가 어떻게 File System을 고립시키는지 알아보고 실습을 통해서 어떻게 하면 안전하게 docker file system을 관리할 수 있는지에 대해서 알아본다.

진짜 이쯤 설명하고 나니 누가 볼까 싶지만 일단 끄적여 보겠다. 필자도 많이 부족하므로 틀린 부분이 있다면 망설이지 말고 지적해 줬으면 한다.

Index

1. 통신 Protocol 공부 배경
2. 참고할 서적들

Network Protocol 공부 배경

필자가 DDH라는 스타트업에서 일하며서 가장 크게 느낀 것이 바로 현대적인 Computer Networking에 대한 절대적인 지식 부족이었다.
탄탄한 기초를 가지고 있는 좋은 Engineer가 되기 위해서 TCP/IP에 대한 이해와 HTTP, gRPC에 대한 이해는 필수 불가결하다고 생각한다.

필자의 통신 프로토콜 공부는 Go언어를 기반으로 진행될 예정이며, 다른 포스트들과는 다르게 실습과 이론을 나누지 않을 예정이다. 이것 만큼은 나누는 것이 오히려 큰 혼란을 불러 일으킬 것 같다.

다음과 같은 큰 주제를 바탕으로 공부가 진행될 것이다.

1. Network System의 개요
2. TCP Socket 통신의 기초
3. HTTP 기초 (HTTP/1.1 정의 및 응용)
4. HTTP 심화 (HTTP/2.0 및 gRPC 관련 내용)

위의 주제들은 1개당 1개의 포스트로 절대 안 끝나고 소 Chapter로 나뉘어 상세하게 다룰 것이다. 겸사겸사 하면서 Go 언어의 문법도 상세히 다룰 예정이다. (랄까 필자도 공부하면서 다룰 것이라 틀린 내용이 있으면 제발 지적좀 부탁한다.)

참고할 서적들

1. Go 언어를 활용한 네트워크 프로그래밍
2. HTTP 완벽 가이드

Index

1. Operating System 공부 배경
2. 참고할 서적들

Operating System 공부 배경

필자가 블로그를 시작한 현 시점에서 아직 머학생 2학년이다. (휴학중) 절대적으로 CS관련 전공 지식이 부족한 가운데 스스로 공부를 하지 않으면 뒤처질 것 같다는 느낌을 씨게 받아서 이렇게 공부를 시작하기 위해 블로그 포스팅을 시작한다.
주로 공룡책을 가지고 공부를 할 예정이며 언제나 그랬듯이 필자의 포스팅은 1개의 주제를 이론/실습 2가지 파트로 나누어 진행된다.
그리고 언어는 Rust로 진행될 것이다. 공룡책에서는 C로 구현했는데(적어도 필자가 가지고 있는 서적판에서는) 조금 다르게 진행해볼까 한다.

Rust는 Stack Overflow에서 “개발자들에게 가장 사랑받는 언어 Top 1”을 6년째 유지중이며, MS는 C/C++로 짜여진 코드를 Rust로 Migration하고 있다고 한다. 그런 의미에서 Rust를 한번이라도 접해보는 것이 나의 개발 능력을 한단계 Upgrade 시켜줄 것이라고 믿고 한번 고난의 길을 걸어볼까 한다.

또한 필자의 Toy Project에서도 Rust를 사용할 예정이라 일석 이조라고 생각한다. 이 기회에 Rust를 한번 찐하게 공부해 봐야할 것 같다.

참고할 서적들

1. 공룡책
2. 운영체제와 정보기술의 원리

Index

1. Tensorflow Serving Server
2. Tensorflow Serving Client
3. Tensorflow Serving Application

Tensorflow Serving Application

이번 파트에서는 flask를 이용해서 간단한 웹 페이지를 만들어서 배포해보고 tensorflow serving과 통신하는 것까지 구현해 보도록 하겠다.

일단 간단하게 HTML 페이지를 작성해 보도록 하겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

<body>
    <p>Upload Your Image</p>
    
    <form id="upload" action="/predict" method="POST" enctype="multipart/form-data">
        <button class="btn">Upload</button>
        <input type="file" value="Upload" name="image">

        <br>

        <p>Result</p>
        {% if label %}
            <span class="result">
                {{ label }}
            </span>
        {% endif %}
    </form>

</body>

귀찮아서 body만 가져왔다.
대충 이렇게 페이지를 짜주자. 왜냐면 메인은 이게 아니니깐.

그리고 다음과 같이 flask server를 구성해 보겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

classes = ["airplane", "car", "bird", "cat", "deer", "dog", "frog", "horse", "boat", "truck"]
headers = {"content-type": "application/json"}

@app.route('/')
def index():
    return render_template('index.html')

@app.route('/predict', methods=["POST"])
def predict():
    data = request.files["image"].read()
    image = Image.open(io.BytesIO(data))
    
    image = image.convert("RGB")
    image = image.resize((32, 32))
    image = img_to_array(image)
    image = np.expand_dims(image, axis=0)
    image = np.asarray(image, dtype=np.uint8)
    
    data = json.dumps({"signature_name": "serving_default", "instances": image.tolist()})
    json_response = requests.post('http://localhost:8501/v1/models/ViT:predict', data=data, headers=headers)
    print(json_response.text)
    predictions = np.array(json.loads(json_response.text)["predictions"])
    index = np.argmax(predictions[0])
    
    return render_template("index.html", label=classes[index])

굉장히 심플하게 구성했다. 이제 서버를 구동해 주면 이미지를 띄울 수 있는 창이 뜨고 사진을 업로드 하면 inference 결과를 보여준다.

Index

1. Tensorflow Serving Server
2. Tensorflow Serving Client
3. Tensorflow Serving Application

여기서는 1~2은 Part. A이고 3는 Part. B에서 다루도록 하겠다.

Tensorflow Serving Server

Tensorflow Serving은 tensorflow로 학습시킨 model을 보다 효율적으로 배포하기 위해 나온 것이다. 이번 포스트에서는 docker를 이용하여 학습시킨 ViT model을 배포하고 HTTP를 통해서 입력과 출력을 주고 받는 예제를 만들어 보겠다.

우선 그러려면 Tensorflow Serving이 뭔지부터 알아야 한다. Tensorflow serving은 tensorflow로 만들어진 모델을 서비스에 배포하기 위해서 만들어진 하나의 application이라고 생각하면 된다.

위의 그림과 같이 Docker와 함께 사용하여 우리가 만든 모델을 Tensorflow Serving에 넣어주면 HTTP/HTTPS/gRPC를 통해서 model의 inference 결과를 받아볼 수 있다.

종래의 Tensorflow model serving의 경우, 대체적으로 flask를 사용해서 REST API 형식으로 Serving을 했었다. 하지만 그것보다는 tensorflow serving의 성능이 좋다. 이유는 대체적으로 여러 요인이 있지만 대표적으로는 2가지가 있다.

1. python의 overhead 해소
2. HTTP/2.0을 사용하는 gRPC를 지원하기 때문

즉, tensorflow serving을 제일 완벽하게 활용하려면 gRPC를 사용해야 하지만 현재로써는 필자의 지식이 부족하기 때문에 일단 HTTP 통신을 사용해 보도록 하겠다. 하지만 그렇더라도 tensorflow serving이 일반 flask를 활용한 serving 보다는 빠르다.

그렇다면 어떻게 Docker를 사용하여 우리가 만든 모델을 Tensorflow Serving으로 배포할 수 있을까?
우선 예제를 보기 전에 자신만의 모델을 만들자. 필자는 ViT를 예시로 들겠다.
모델을 만들었다면, 다음과 같은 폴더 구조에 .pb와 함께 다양한 파일들이 모델로써 저장될 것이다.

1
2
3
4
5
6
7

ViT/1/
├── assets
├── variables
│   ├── variables.data-00000-of-00001
│   └── variables.index
├── keras_metadata.pb
└── saved_model.pb

그렇다면 우리는 이 폴더를 Docker Container에 mount해주고 8501번 포트를 열어주면 된다. 다음과 같은 명령어로 말이다.

1

sudo docker run -p 8501:8501 --name tf_serving -v /path/to/your/model/ViT/:/models/ViT -e MODEL_NAME=ViT -t tensorflow/serving &

그렇다면 준비 완료이다. 이제 Tensorflow Serving으로 ViT 모델을 Serving한 것이다.
물론, 실제 production 할때는 이따구로 하면 큰일난다. 어디까지 예제로 만들기 위해서 간단하게 만든 것이다.

Tensorflow Serving Client

이제 띄워놓은 ViT model에게 HTTP를 통해서 Shiba견의 이미지를 보내고 결과를 받아와보자.

(머스크형 제발 닥쳐줘)

한번 예제 소스코드를 다음과 같이 짜 보았다.

1
2
3
4
5
6
7
8
9
10

image = cv2.imread("./image/Shiba.jpg")
image = cv2.resize(image, dsize=(32, 32))
image = np.expand_dims(image, axis=0)

data = json.dumps({"signature_name": "serving_default", "instances": image.tolist()})

headers = {"content-type": "application/json"}
json_response = requests.post('http://localhost:8501/v1/models/ViT:predict', data=data, headers=headers)
predictions = np.array(json.loads(json_response.text)["predictions"])
print(np.argmax(predictions[0]))

우선 데이터는 위와 같은 형식을 유지해주면 된다. 그리고 POST method로 HTTP request를 보내면 결과 tensor가 text 형식으로 온다.

우리는 그걸 json으로 바꾸고 안에 있는 list를 꺼내서 inference 결과를 받으면 되는 것이다.

다음 포스트에서는 이걸 이용해서 간단한 application을 flask로 만들어보는 시간을 가져보자.