Estimating Moments - AMS method

빅데이터를 다루기 위해서, 즉 Stream Data를 다루기 위해서 Moment라는 개념을 정리해 둘 필요가 있다. 

여러 물리량을 다루는 데 있어서 모멘트라는 개념이 많이 쓰이기도 하기 때문에 낯설지는 않은 개념이겠지만, 확실하게 짚고 넘어가는 것이 좋다. m(i)를 특정한 값 i가 Stream 에 등장한 횟수라고 정의할 때, kth Moment는 아래 그림과 같이 스트림에 있는 N개의 m(i)를 각각 k승 한 값들의 합으로 나타낼 수 있다. 

 

 

 

 

이 모멘트는 k값에 따라 각기 다른 특정한 의미를 갖는데, 모멘트를 정의하는데 사용했던, m(i)의 의미를 생각해보면 쉽게 이해할 수 있다. 

 

0th moment = m(i)의 값이 의미가 없어지므로, 스트림 내에서 서로 다른 원소의 개수를 의미한다.

1st moment = m(i)의 값을 모두 더하면 스트림 내의 데이터의 개수가 나오므로 모든 원소들의 개수를 의미한다.

2rd moment = 서로 다른 원소들의 분포를 나타내는 지표로 사용할 수 있다. (분산의 개념) (surprise number S 라고 부른다!)

 

이렇게 kth moment가 데이터 스트림을 분석하는데에 중요한 역할을 수행하기 때문에 이를 구하는 일은 데이터 분석에서 굉장히 중요하다.

따라서 이를 구하는 방법인 AWS method를 살펴보도록 하겠다.

 

AMS method

AMS method 는 모든 모멘트에 대해서 적용가능한 방법이다. 먼저 이번 포스팅에서는 2번째 모멘트를 구하는 방법에 대해서 살펴보고, 이를 k값을 확장시켜 나가면서 적용하면 된다. 

 

방법은 다음과 같다. 우선 Random Variable X를 잡는다. X는 여러개 잡을 것이고, 각각의 X값들은 스트림에서 들어오는 데이터의 종류인 X.el과, 스트림 내의 동일한 원소의 개수인 X.val을 저장한다.(이 때 서로다른 X는 스트림에서 서로다른 데이터를 가리키고 있어야 한다. ) AMS method는 이 여러개의 X값들을 통해 (메모리에 제한이 있으므로, Random Variable X의 개수에도 제한이 걸린다.) kth(여기서는 2번째) 모멘트를 예측한다.

 

 

이를 가지고 Surprisenumber (2rd moment)를 예측하는데, 예측하는데 사용하는 식은

 

S = f(x) = n(2*c - 1) 이다. (n은 스트림의 길이(나중에 확장시킬 것), c는 특정 시간 t부터(t<n) n까지 등장한 X.el의 개수(시간이 지날수록 이 값은 같거나 작아진다.))

 

실제 상황에서는 여러 X를 저장해놓고 각각의 X값에 대해 S값을 추정할 수 있기 때문에

모든 추정값을 평균 낸 값을 2nd moment로 사용한다. 

 

Proof

증명은 단순하다. E[f(x)]의 값이 2nd moment의 정의와 부합하기 때문에 그냥 통계적으로 여러 f(x)의 값들을 평균내서 사용하는 것이다.