[KOOC] 인공지능 및 기계학습 개론 9주차 - Hidden Markov Model

Chapter 9. Hidden Markov Model

• 목차

1. Hidden Markov model
   • static clustering to the dynamic clustering
   • difference of the graphical model
2. three major questions of HMM
   • evaluation question
   • decoding question
   • learning question
3. link some method
   • forward-backward algorithm to the message passing
   • baum-welch algorithm to the EM algorithm.

 

 

9-1. Hidden Markov Model

이때까지는 시간에 관계없는 상황에서의 데이터들이었다. 그러나 만약 시간에 따라 변화하는 데이터에 대해서는 어떻게 다룰 수 있는지 살펴보고자 한다.

시간에 따라 변화한다는 것은 latent variable이 연관되어 있다는 뜻이고, 이를 그래프화하면 다음과 같다.

왼쪽 그래프는 이때까지 다뤄왔던 각 데이터들이 독립적인 관계에 대한 것이고, 오른쪽 그래프가 시간이라는 latent variable이 추가되어 각 포인트마다 관련이 되어 있는 상황이다.

 

관측값 x는 이산적일수도, 연속적일수도 있다. 이산적이라면, x는 특정 값을 가지고, 연속적이라면 확률 분포를 가진다. 이번 강의에서는 이산적인 경우에 대해서만 다뤄보고자 한다.

시간이 1~T까지 흘러감에 따라 x는 x1~xT로 존재한다.

 

latent variable, z의 경우도 이산적일수도 있고, 연속적일수도 있다. latent variable이 연속적인 경우에 사용하는 기법을 Kalman filter 이라 한다. 따라서 이번 강의에서는 z도 이산적인 경우만 다룬다. z는 vector로서 k개의 elements를 가진다.

 

initial probability, P(z1) 은 π1~πk 에 대한 multinomial distribution에 의해 생성된다.

그리고 HMM(Hidden Markov Model)에는 2가지 확률이 더 존재한다.

1. Transition Probabilities

z1에서 z2, z2에서 z3등과 같이 $ z_{i} $에서 $z_{j}$로 가는 관계를 나타내는 확률이다. 수식적으로 보면, t-1에서의 z에 대한 z_t의 condition probability를 나타내고, 이는 a라는 변수에 대한 multinomial distribution로 나타내어진다.

이 때, z_t=1이라는 특정 상황에 대한 확률을 $ a_{i,j} $ 로 나타낼 수 있다. i와 j는 z의 k개의 elements에서 i번째 elements와 j번째 elements에 대한 index를 나타낸다.

 

1. Emission Probabilities

이는 z에서의 x에 대한 관계를 나타낸다. 이 또한, x_t=1이라는 특정 상황에 대한 확률을 $ b_{i,j} $ 로 나타낼 수 있다.

 

 

9-2. Forward-Backward Probability

HMM의 과정을 자세하게 살펴보기에 앞서, 알고 가야할 개념들이 있다.

 

Many Questions

일단, ML(machine Learning)에서 몇가지 과제가 있는데, 이는 주어진 변수들에 따라 달라진다.

1. Evaluation question
   • π, a, b, X 가 주어진 경우
   • 즉, 관측값과 latent factor에 대한 정보도 모두 가지고 있는 상태
   • P(X|Model,π,a,b)를 찾는 것이 목적
   • π,a,b,X가 주어졌을 때 학습된 모들에 의해 특정 X가 관측될 확률을 구함.

 

1. Decoding question
   • π, a, b, X 가 주어진 경우
   • $ argmax_Z P(Z|X,M,π,a,b) $
   • π,a,b,X가 주어졌을 때, latent factor, Z의 확률 중 가장 확률이 높은 Z를 구하는 것, 즉 Z를 학습시키면서 가장 최적의 Z를 찾음.

 

1. Learning question
   • X만 주어진 경우
   • $ argmax_{π, a, b} P(X|M,π,a,b) $
   • 관측값만 가진 상태에서 특정 X가 관측될 확률을 구함.

decoding의 경우 관측값과 GT가 주어지므로 Supervised learning과 유사하고, learning 의 경우 관측값만 주어진 상황에서 확률을 구해야 하는 unsupervised learning과 유사하다.

 

 

• loaded dice

간단한 예시를 들어보자. 기울어진 주사위가 있어서 6이 나올 확률이 1/2이고 나머지는 모두 1/10 확률을 가진다고 하자. 일반적인 주사위는 모두 동일하게 1/6의 확률을 가진다.

latent factor로서, 기울어진 주사위(L)을 사용할지 평범한 주사위(F)를 사용할지에 대한 확률이 있고, 처음 L을 사용할 확률을 0.5, L을 사용한 후에 다시 L을 사용할 확률을 0.7, F를 사용한 후 F을 사용할 확률을 0.5라 가정한다.

X와 Z가 주어진 상황에서 dataset을 훈련시킬 때, 간편한 계산을 위해 Joint probability를 사용해볼 것이다. baysian network를 생각했을 때, P(X,Z)는 다음과 같이 풀어줄 수 있다.

\[P(X,Z) = P(x_1,...,x_t,z_1,...,z_t) = P(z_1)P(x_1|z_1)P(z_2|z_1)P(x_2|z_2)P(z_3|z_2)P(x_3|z_3)\]

아무것도 가정하지 않고도 joint와 conditinoal probability의 정의에 따라 풀어줄 수 있다.

앞서 배운 transition과 emission probability를 적용하면 다음과 같다.

$ P(X,Z) = \pi_{z_1} b_{x1=1,z_1=1} a_{z_1=1,z_2=1} \dots $

 

 

그렇다면, P(166,LLL) 과 P(166,FFF) 에 대한 값을 직접 구할 수 있다. 처음 L을 사용할 확률은 0.5, L을 사용했을 때 1이 나올 확률은 0.1, L을 사용했을 때 6이 나올 확률은 0.5이고, L을 사용한 후에 다시 L을 사용할 확률은 0.7이었으므로 다음과 같이 계산한다.

P(166,LLL) = 1/2 x 1/10 x 7/10 x 1/2 x 7/10 x 1/2 = 0.0061

 

P(166,FFF) = 1/2 x 1/6 x 1/2 x 1/6 x 1/2 x 1/6 = 5.7870e - 04

F를 사용했을 때 1이 나올 확률과 6이 나올 확률은 동일하게 1/6이고 처음 F를 사용할 확률은 1/2, F에서 F를 다시 사용할 확률은 0.5였다.

 

이처럼 직접 구해줄 수는 있지만, 횟수가 늘어남에 따라 경우의 수는 기하급수적으로 증가하므로 큰 횟수에 대해서는 직접 구해주기 힘들다.

 

 

이전에 다뤘던 marginalization 기법을 사용하고자 한다.

$ P(X|\theta) = \sum_Z P(X,Z|\theta) $

 

HMM에서는 θ가 아닌, π,a,b이므로 이에 대해 다시 정의한다.

$ P(X|\pi,a,b) = \sum_Z P(X,Z|\pi,a,b) $

 

$ P(X) = \sum_Z P(X,Z) = \sum_{z_1} \dots \sum_{z_t} P(x_1,…,x_t,z_1,…,z_t) = \sum_{z_1} \dots \sum_{z_t} \pi_{z_1} \prod_{t=2}^T a_{z_{t-1},z_t} \prod_{t=1}^T b_{z_t,x_t}$

이는 너무 많은 연산이 들어가므로, 반복적인 연산을 피하기 위해 하나의 시간에 대해서만 계산해보자. 특정 시간 t에 대해 구하기 위해서 t-1에서의 z를 marginalization 처리해준다.

$ P(x_1,…,x_t,z_t^k=1) = \sum_{z_{t-1}} P(x_1,…,x_{t-1},x_t,z_{t=1}, z_t^k=1) = \sum_{z_{t-1}} P(x_1,…,x_{t-1},z_{t-1})P(z_t^k=1|z_{t-1})P(x_t|z_t^k=1) $

이 때, z_t에 대한 확률을 구할 때는 x와는 모두 독립적이고, x_t에 대한 확률을 구할 때는 x_1~t-1에 대한 값들과 z_t-1에 대해서는 독립적이므로 지워줄 수 있다.

지워주고 나서 시그마에 관련 없는 값들은 밖으로 빼내고 나면, 이전에 구했던 transition과 emission probabilities를 적용할 수 있다.

적용하고 나면

$ P(x_1,…,x_t,z_t^k=1) = \alpha_t^k = b_{k,x_t} \sum_i \alpha_{t-1}^i a_{i,k} $

 

즉, 시간 t에 대한 확률은 시간 t-1에서의 확률에 값을 곱한 것과 동일한 재귀적인 관계가 형성된다.

 

 

Dynamic Programming

이 때, dynamic programming이라는 기법이 등장한다. 이는 특정 값을 연산하는 데 있어서 겹치는 값들에 대해서는 재사용(recurrence)하는 방식이다. 예를 들어, 피보나치 수열에서 n=4를 구하기 위해서는 F(3)과 F(2)를 구해야 하고, F(3)을 구하기 위해서는 F(2)와 F(1)을 구해야 한다.

이런 Top-down 방식으로 연산하는 것을 Recursion이라 하고, 이 recursion의 단점은 같은 값을 반복적으로 연산하는 것이다.

반대로, 아래에서부터 연산을 시작하여 F(4)가 될 때까지 연산하는 방식이 dynamic programming이다. 이런 방식으로 진행하게 되면, 먼저 F(0)을 계산하고 값을 저장한다. 그리고 F(1)을 계산하고 저장하고, F(2)를 연산할 때 저장해둔 F(0)과 F(1)을 가져와 F(2)를 계산한다. 이렇게 연산을 이어나가다가 원래 찾고자 했던 값인 F(4)를 연산하고 나면 과정을 종료한다.

dynamic programming의 장점은 반복적인 연산을 하지 않는다는 것이다. 이와 같이 반복적인 연산을 할 때 값을 저장하고 불러오는 과정을 Memoization이라 한다.

 

 

Forward Probability Calculation

만약 $ \alpha_t^k $ 를 안다면 Z를 알아낼 필요없이 P(X)를 계산할 수 있다. 따라서 이 $ \alpha_t^k $ 를 계산하기 위해 Forward Probability를 사용한다.

1. Initialize

2. Iterate until time T
   • $ \alpha_t^k = b_{k,x_t} \sum_i \alpha_{t-1}^i a_{i,k} $
3. Return $ \sum_i \alpha_T^i $
   • $ \sum_i \alpha_t^i = \sum_i P(x_1,…,x_t,z_t^i = 1) = P(x_1,…,x_t) $

 

Forward probablity의 한계로는 t가 전체 데이터셋에 대한 T일 필요가 없다는 점이다. 예를 들어 t가 2라고 한다면, z3에 도달하지 않은 채로 x1,x2,z2에 대해 모델링된다. 그렇다 하더라도 문제가 발생하지 않는다. 따라서 전체 데이터셋인 X에 대한 확률도 계산해줘야 한다. 그를 위한 방법이 Backward probability calculation 이다.

 

 

Backward Probability Calculation

이 때는 P(X,z_t^k=1) 이 아닌 P(z_t^k=1|X) 를 계산한다. 전체 X에 대해 연산하기 위해 앞서 구했던 x_t에서 x_t+1~x_T를 추가한다.

$ P(z_t^k=1,X) = P(x_1,…,x_t,z_t^k=1,x_{t+1},…,x_T) = P(x_1,…,x_t,z_t^k=1)P(x_{t+1},…,x_T|x_1,…,x_t,z_t^k=1) $

이 때도 x_t+1~x_T과 x_1~x_t는 독립적이므로 제거할 수 있다.

$ P(x_1,…,x_t,z_t^k=1)P(x_{t+1},…,x_T|z_t^k=1) $

P(x_1,…,x_t,z_t^k=1)는 forward 계산할 때 α_t^k로 지정했다. 그리고 P(x_{t+1},…,x_T|z_t^k=1) 를 β_t^k 로 정의한다.

 

$ P(x_{t+1},…,x_T|z_t^k=1) = \sum_{z_{t+1}} P(z_{t+1},x_{t+1},…,x_T | z_t^k=1) = \sum_i P(z_{t+1}^i =1 | z_t^k = 1) P(x_{t+1} | z_{t+1}^i = 1, z_t^k=1) P(x_{t+2},…,x_T|x_{t+1},z_{t+1}^i=1,z_{t}^k=1) $

이 떄, x_t+1에 대해 구할 때 z_t+1을 알고 있다면, z_t과는 독립적이 되어 제거되고, 그 뒤에 x_t+1도 x_t+2~x_T와는 독립적이므로 제거할 수 있다.

이렇게 다 제거하고 나면 이전에 구했던 a,b,β로 치환할 수 있다.

$ P(x_{t+1},…,x_T|z_t^k=1) = \beta_t^k = \sum_i a_{k,i}b_{i,x_t} \beta_{t+1}^i $

이 때, β_t+1 의 size는 t+1에서 T로 점점 다가가므로 감소된다.

 

 

9-3. Viterbi Decoding

decoding question에서 가장 많이 사용되는 기법이 Viterbi decoding이다.

• $ \alpha_t^k $ : forward probability
• $ \beta_t^k $ : backward probability

$ P(z_t^k=1,X) = \alpha_t^k \beta_t^k = (b_{j,x_t}\sum_i \alpha_{t-1}^i a_{i,k}) \times (\sum_i a_{k,i}b_{i,x_t} \beta_{t+1}^i) $

이렇게 특정 time t에 대한 joint probability를 계산할 수 있고, joint를 통해 conditional probability도 계산할 수 있다. 그러나 이는 특정 시간 t인데, 우리가 구하고자 하는 것은 전체 sequence를 보고 전체 sequence에 대한 latent variable이다.

그래서 z_t가 아닌 전체 latent variable인 Z에 대해 구해보고자 하고, 이 과정을 decoding question이라 할 수 있다.

 

$ P(x_1,…,x_{t-1},z_1,…,z_{t-1},x_t,z_t^k=1) $ 를 $V_t^k $라 정의하고, 이는 t-1까지의 가장 확률이 높은 Latent vector을 나타낸다.

즉, estimation하고자 하는 latent factor(z_t)가 1이라는 클러스터에 속하고 있는 상황에서 $ x_1,…,x_{t-1} $과 $ z_1,…,z_{t-1}, x_t, z_t^k=1 $ 이 관측될 확률이 최대가 되는 z1~z_t-1을 최적화하겠다는 의미이다.

t-1까지의 과정을 dynamic programming을 통해 구한다.

 

V_t^k 의 joint probability를 condition probability로 나타내어 간편화한다.

$ V_t^k = max_{z_1,…,z_{t-1}} P(x_t,z_t^k=1|x_1,…,x_{t-1},z_1,…,z_{t-1})P(x_1,…,x_{t-1},z_1,…,z_{t-1}) $

이 때, x_t와 z_t^k=1에 대해 구할 때, x1,…,x_t-1,z1,…,z_t-2와는 독립적이므로 제거된다. 이에 따라 maximize하는 값도 앞에는 z1~z_t-1이 아닌 z_t-1로 변환되고, 뒤에는 V_t^k 식과 동일한 형식이므로 z1~z_t-2로 바뀌게 된다.

이 때, time t-1의 latent factor가 i라는 라는 클러스터에 속해진다고 가정을 하게되면, 다음과 같이 나타내진다.

$ max_{i \in t-1} P(x_t,z_t^k=1|z_{t-1}^i = 1)V_{t-1}^i = max_{i \in t-1} P(x_t|z_t^k=1)P(z_{t-1}^i = 1)V_{t-1}^i $

forward, backward probability 인 a와 b로 나타내면

$ b_{k,x_t} max_{i \in z_{t-1}} a_{i,k} V_{t-1}^i $

 

이 식을 통해 t=T일 때까지 반복하여 V_(t-1)^i 를 업데이트한다.

 

 

viterbi decoding에 대한 예제가 하나 있다. 제품을 생산하는 시간을 최적화하는 알고리즘으로, 각 원(station)안에 들어 있는 숫자는 프로세스 시간이고, assembly line이 2개 존재한다. 각 station에서는 같은 line으로 갈수도 있고, 다른 line으로 갈수도 있는데, 다른 line으로 갈 경우 추가 시간이 발생된다.

이러한 경우 최소한의 시간이 드는 루트는 어떻게 되는지 확인하는 과정이다.

아래의 두 개의 테이블에서 첫번째 table은 각 시간마다 line별 걸린 시간을 나타낸 것이고, 오른쪽 table은 해당 시간에서 이전의 line이 어디였는지를 나타내는 값이다. 해당 시간에서 소요된 시간이 더 적은 line에서 이동된 것으로서, 이 숫자들을 역추적해서 이으면 최적의 루트가 된다.

즉, 마지막이 line1에서 끝났으므로 1을 선택하고, t=6에서 2가 되어 있으므로 t=5에서는 line2가 소요된 시간이 적게 걸렸다고 볼 수 있다. t=5에서는 L2에 2로 되어 있으므로 t=4에서도 line2에 위치하는 것이 최적의 루트이다. 이렇게 따라가다보면, 빨간색 화살표의 경로처럼 된다.

 

 

이러한 경우를 확률적으로 계산해보자. 일단 먼저 확률을 계산하는 table과 trace에 대한 memoization table이 존재해야 한다. trace란 이전 시간에서 최적의 루트를 나타내는 값이다.

 

• Viterbi Decoding Algorithm
  1. Initialize
  • $ V_1^k = b_{k,x_1} \pi_k $
  • π라는 초기값을 통해 V_1^k를 계산한다.
    1. Iterate until time T
  • $ V_t^k = b_{k,x_t} max_{i \in z_{t-1}} a_{i,k} V_{t-1}^i $
  • $ trace_t^k = argmax_{i \in z_{t-1}} a_{i,k} V_{t-1}^i $
  • V_t^k 는 앞서 말한 확률 table에 대한 값이고, trace는 trace table에 대한 값이다.
    1. Return $ P(X,Z) = max_k V_T^k, z_T^ = argmax_k V_T^k,z_{t-1}^* = trace_t^{z_t^*}$

 

viterbi decoding에도 한계가 존재한다. a,b가 확률이므로 데이터가 100개 200개와 같이 많은 경우 값이 매우 작아져서 0에 가까워진다.

따라서 이러한 곱셈 연산에 log를 씌워 곱셈을 덧셈으로 바꿔 연산을 하게 해야 한다.

 

최종적으로 이러한 decoding algorithm을 통해 학습된 파라미터(π,a,b)와 X를 통해 새로운 sequence(데이터)에 대해 최적의 클러스터링을 할 수 있게 된다.

자연어 처리를 예로 들면, 모델을 학습하여 π,a,b를 얻은 후 새로운 데이터(문장)이 들어왔을 때, viterbi decoding 과정을 통해 pos-tagging(품사 태깅)을 할 수 있다.

 

 

9-4. Baum-Welch algorithm

decoding알고리즘은 supervised learning에 해당되었다. π,a,b,X 를 모두 알고 있다는 가정하에 새로운 데이터에 대해 fitting하는 작업을 했다. 이제는 unsupervised learning, 즉 X만 주어진 상황에서 모델을 학습하는 동시에 새로운 데이터에 대해 fitting하는 작업을 해보고자 한다. 이를 수행하기 위한 방법이 Baum-Welch 알고리즘이다. 이 Baum-Welch 알고리즘은 이전에 배웠던 EM 알고리즘과 동작이 거의 동일하다.

 

 

clustering을 하는 데 있어서 HMM의 파라미터인 π,a,b는 Forward algorithm과 Viterbi algorithm(decoding)에서 사용된다.

그러나 π,a,b는 X와 Z를 알고 있다는 가정 하에 추론이 가능해진다. 그러나 현실에서는 Z를 관찰하는 것은 매우 어렵다. 이 Z를 추론하기 위해 학습을 시킨다면, annotation이 필요하게 된다.

만약 Z를 모르고, X만 관찰할 수 있다면 clsutering을 위해서는 Z와 π,a,b를 모두 찾아야 한다.

 

파라미터들을 최적의 값으로 찾아내기 위해 EM algorith을 사용하고자 한다. EM 알고리즘의 전략은 다음과 같다.

1. X에 대해 π,a,b를 최적화한다.
2. X,π,a,b에 대해 가장 확률이 높은 Z를 찾는다.
3. 이를 반복적으로 작업하여 Z,π,a,b를 찾는다.

 

EM algorithm에 대해 조금 더 자세하게 살펴보자. EM 알고리즘의 순서는 다음과 같다.

1. 무작위 값으로 $ \theta^0 $ 를 초기화한다.
2. likelihood가 수렴이 될때까지 아래 과정을 반복한다.
3. Expectation step
   • $ q^{t+1}(z) = argmax_q Q(\theta^t, q) = argmax_q L(\theta^t, q) = argmin_q KL(q||P(Z|X,\theta^t)) $
     • q는 latent variable 할당에 대한 값으로, X와 θ^t가 주어졌을 때, Z를 할당하는 확률 그대로 q를 할당한다.
4. Maximization step
   • $ θ^{t+1} = argmax_θ Q(θ, q^{t+1}) = argmax_θ L(θ, q^{t+1}) $
   • 할당된 Z와 관측값 X에 대해 MLE를 수행하여 파라미터들을 최적화한다.

 

이 과정을 HMM(Hidden Markov Model)에 적용하면 아래와 같게 된다.

1. 무작위 값으로 $ π^0, a^0, b^0 $ 를 초기화한다.
2. likelihood가 수렴될 때까지 아래 과정을 반복한다.
3. Expectation step
   • $ q^{t+1}(z) = P(Z|X,π^t, a^t, b^t) $
4. Maximization step
   • $ π^{t+1}, a^{t+1}, b^{t+1} = argmax_{π,a,b} Q(π,a,b,q^{t+1}) $
     • 지난 주 KL divergence를 배울 때, Q에 대해 정의했다. ln함수는 concave에 해당하므로 최소값과의 차이이 H(q)와 함께 ln안에 있던 ∑를 밖으로 빼냈다.
     • E는 expectation값 즉, 기대값을 의미하고, 이 기대값 q^t+1(Z)는 Expectation step에서 P(Z|X,π^t, a^t,b^t) 로 정의하기로 했으므로 파라미터의 업데이트 식은 다음과 같이 정의된다.
     • $ π^{t+1}, a^{t+1}, b^{t+1} = argmax_{π,a,b}E_{q^{t+1}(z)} lnP(X,Z|π,a,b) + H(q) $

이 때, P(X,Z|π,a,b)는 joint를 condition probability으로 바꿈과 동시에 marginalization을 통해

$ P(X,Z|π,a,b) = \pi_{z_1} \prod_{t=2}^T a_{z_{t-1},z_t} \prod_{t=1}^T b_{z_t,x_t} = ln\pi_{z_1} + \sum_{t=2}^T lna_{z_{t-1},z_t} + \sum_{t=1}^T lnb_{z_t, x_t} = Q(π,a,b,q^{t+1}) $

로 정의된다.

 

Q 함수를 최적화해야 하므로, 이에 대해 미분을 수행하는데, 제약조건이 하나 있다. π를 multinomial distribution을 따른다고 정의했으므로 $ \sum_i π_i = 1 $ 이다. 따라서 lagrange method를 사용하여 미분해야 한다.

$ L(π,a,b,q^{t+1}) = Q(π,a,b,q^{t+1}) - \lambda(\sum_{i=1}^k \pi_i - 1) - \sum_{i=1}^K \lambda_{a_i} (\sum_{j=1}^K a_{i,j} -1) - \sum_{i=1}^K \lambda_{b_i} (\sum_{j=1}^M b_{i,j} -1) $

 

이 식에서 π에 대해 편미분을 수행해보자.

$ \frac{dL(π,a,b,q^{t+1})}{dπ_i} = \frac{d}{dπ_i} \sum_Z P(Z|X,π^t, a^t, b^t) lnπ_{z_1} - \lambda_π (\sum_{i=1}^K π_i - 1) = 0 $

이 식은 z_1이 i 일 때만 성립되므로, z_1 = i로 두어 π의 최대값을 찾는다.

$ \frac{P(z_1^i = 1| X,π^t, a^t, b^t)}{π_i} = \lambda_\pi $

 

이 식을 바로 풀기는 어려우므로 L함수를 $ \lambda_\pi $ 에 대해 편미분을 수행한다.

$ \frac{d}{d\lambda_\pi} L(\pi,a,b,q^{t+1}) =\gt : \sum_{i=1}^K \pi_i = 1 $

즉, π_i를 i=1부터 K까지 모두 더하면 1이 된다는 것이다.

그렇다면 $ \lambda_\pi $ 는 분자에 있는 값을 1~K만큼 합한 것과 같고, 이것이 곧 $ π^{t+1} $ 이 된다.

이 프로세스를 동일하게 a와 b에 적용하면 우상단의 값들로 추출이 된다.

 

Baum Welch algorithm은 결국 HMM에 대한 learning question이자 HMM을 위한 EM 알고리즘이다.