정규분포, 타원형, 구글 검색 알고리즘1

 

 

구글 검색 엔진 알고리즘에 대해 간단히 이야기 하기 전에 앞에 이야기한 PCA와 관련해서 정규분포와 타원형의 중요성에 대해 한번 이야기를 해 보겠습니다. 이쪽 공부를 하려면 정규분포에 대해서 잘 이해를 해야 합니다.

 

 

 

구글 알고리즘 이후에 히든 마코프 모델(HMM)을 먼저 이야기할지 아니면 연관분석을 먼저 이야기 할 지 지금 조금 고민입니다. 히든 마코프 모델은 개념 자체는 별로 어렵지는 않지만 계산문제가 골치가 아파 이야기하려면 상당한 시간이 걸리고요. 최근 통역이라든지 사람 말을 인식한다든지 이런 곳에 사용되고 앞으로도 굉장히 많이 응용이 될 것 같은 분야라고 생각이 듭니다. 인공지능이 뜨면서 언론에 범죄자의 움직임도 인공지능으로 추적할 수 있다는 기사가 나오는데 이쪽 응용으로 책에 나오는 예입니다. 실제로 적용은 할 수 없죠. 비현실적인 가정들이 너무 많으니까요.

 

 

 

연관분석은 최근 인터넷 몰에서 많이 사용하는 개인 구매 정보를 이용하여 연관상품을 추천하는 것에 사용되는 것인데 이건 그냥 조건부 확률 등 기초 초보 문제입니다. 진짜 문제는 현장에서 실제 상황에 맞쳐, 목적이 뭔지에 따라 어떻게 구현할 건가 하는 문제가 진짜 문제가 됩니다. 즉 이론은 별 공부할 필요도 없고 학부 1학년 통계 수준이면 어느 정도 이해가 되는 분야입니다.

 

 

 

 

1. 정규분포, 타원형

 

앞에서 PCA 이야기할 때 타원형 모양에 대한 이해가 중요하다는 것을 이야기 했습니다. 이 타원형이 왜 중요하냐면 정규분포의 모양이 타원형을 하기 때문입니다. 즉 정규분포의 모양을 산의 모양이라 생각하고 중간을 수평으로 짜르면 타원형의 모양이 됩니다. 이 짤라진 타원형 모양이 정규분포의 성격을 결정적으로 좌우합니다.

 

아래 그림에서 앞 그림은 두 변수가 독립인 경우이고 뒤 그림은 두 변수가 상관관계가 있는 정규분포의 모양입니다.

 

 

이걸 산 중간에서 평평하게 짜르면 아래 그림처럼 타원형 모양이 나옵니다. 원은 타원형의 특수한 경우라고 보면 됩니다.

 

 

 

 

 

 

정규분포의 식은 다음과 같습니다.

 

 

 

 

 

이걸 로그을 취한 후 쓸데없는 것을 없애면 다음과 같은 식이 됩니다. 이 식이 타원형 식이 됩니다. 물론 안에 있는 행렬의 모양에 따라서 쌍곡선이나 상대성 이론에 나오는 시공간 모양이 되기도 합니다. 기하학에서요.

 

 

 

 

 

1)

 

그럼 통계학에서 정규분포가 왜 중요한지 이야기를 하겠습니다.

 

첫째, 통상적으로 현실에서 여러 현상이 정규분포를 한다고 알려져 있습니다. 그러나 이 주장은 별로 검증된 이야기가 아니고요. 정규분포가 어떻게 도출되었는지에 대한 이야기는 앞에서 언급한 엔트로피의 대가인 Jaynes의 probability logic이라는 책에서 자세히 설명되어 있습니다.

 

양궁의 명사수가 있다고 하죠. 이 명사수가 과녁을 겨냥해 활을 계속 쏩니다. 이 때 중력의 영향이나 바람의 영향 등 외부적인 요인이 없다고 가정하죠. 그럼 표적의 중앙에는 딱 맞지는 않겠지만 중앙을 중심으로 왼쪽, 오른쪽, 위쪽, 아래쪽 다양한 방향으로 맞을 겁니다. 여기서 우리가 논리적으로 생각할 수 있는 것이 화살의 맞는 점이 중앙을 중심으로 어떤 방향으로 선호할 수가 없다는 것입니다. 즉, 왼쪽에 맞을 확률, 오른쪽에 맞을 확률, 위에 맞을 확률, 아래쪽에 맞을 확률 모두 같다는 것이죠. 더구나 15도로 맞을 확률, 225도로 맞을 확률 이것 마저도 같습니다. 즉 좌우로, 또는 상하로, 또는 방향 전환에 대해 맞을 확률이 무차별, 무선호입니다. 즉 대칭의 논리가 작용합니다. 이런 대칭의 논리를 만족시키는 분포가 정규분포입니다.

 

Jaynes의 책을 보면 원래 천문학에서 별을 관찰하는 것에서 나옵니다. 별의 원래 위치가 있지만 우리의 여러 가지 요인이나 한계 때문에 이 별의 위치를 정확하게 알 수 없습니다. 그래서 우리가 실제 관찰한 별의 위치는 진짜 별의 위치에서 왼쪽, 오른쪽, 위쪽, 아래쪽 등 다양한 방향으로 떨어진 위치로 측정하게 됩니다. 사실 천체에서 좌우, 상하, 또는 방향이 있다는 것 자체가 말이 안되죠. 그래서 우리가 관찰하는 별의 위치는 별의 진짜 위치를 중심으로 다양한 방향으로 무차별, 무선호하는 대칭의 원칙이 작용해야 된다는 것이죠. 이런 전제 하에서 도출해보니까 정규분포가 나왔다는 것이죠.

 

위대한 발견은 꼭 근거가 되는 데이터에서 나오는 것이 아니라 이런 논리 전개 속에서 나오는 경우가 많이 있습니다. 새논의 엔트로피도 이와 비슷한 논리 전개에서 나왔다고 언급한 적이 있죠.

 

 

 

2)

 

키나 몸무게 등은 정규분포를 할 것 같습니다. 확인해보지는 않았습니다. 통상 일정 기간안에, 일정 구역 내에 생긴 사고 건수는 포아송 분포를 한다고 알려져 있고, 일정 사고가 일어날 때 까지 걸리는 시간은 지수분포를 한다고 알려져 있습니다. 물론 여기서 좀 더 일반화된 형태의 분포도 있습니다.

 

사회적 구조가 영향을 미치는 소득이나 집값 등 부동산 가격은 정규분포를 하지 않고 한쪽으로 치우치는 분포를 하는 것으로 알려져 있습니다. 이런 경우 log 함수를 취하면 정규분포를 하는 것으로 알려져 있고요.

 

원래 소득이나 부동산 가격의 평균과 로그를 취한 후 로그의 평균을 구한 다음 다시 역으로 지수함수를 취한 값은 일치가 되지 않습니다. 화씨로 측정한 평균 온도는 이 평균온도를 섭씨로 다시 변환하면 원래 섭씨로 계산한 평균과 일치합니다.

 

즉 두 개의 변수가 선형관계일때는 이쪽 용어로 좀 더 어렵게 이야기하면 affine transformation 관계이면 어느 쪽을 평균해서 이 평균값을 다시 변환해도 문제가 없습니다. 그러나 log나 exponential 등 선행관계가 아니면 어느 한쪽이 척도로 평균을 구할 때는 주의가 필요합니다. Jensen 부등식을 검색해 보시길 바랍니다. 유명한 부등식입니다.

 

또 로그를 많이 취하는 경우는 주식 가격을 분석할 때입니다. 주식 가격이 일정 수익률을 계속 변화한다면 이 주식 가격에 로그를 취한 후 시간에 따라 그래프를 그리면 직선 형태로 나옵니다.

 

그래서 주식 가격을 로그로 취한 후 시간에 따라 그래프를 그린 모양을 보고 이 수익률이 어떻게 변화해 왔는지를 어느 정도 감을 잡을 수가 있습니다. 이건 이 공식에서 나옵니다. 초기 주식 가격을 S(0)라 하고 일정시간 후 주식가격을 S(t)라고 하면, 또 주식의 가격 상승률이 시간에 관계없이 일정하다고 하면 이를 a라고 할 때

 

 

S(t)=S(0)exp(at)

 

이런 형태를 취합니다. 여기서 주식 가격을 log 취하면

 

log(S(t))=log(S(0))+at

 

가 되는 것이죠. 즉 at 시간에 관해 일차 직선이 되어 버립니다. 인구 증가율도 마찬가지입니다. 우리나라 인구 수를 log 취한 후 시간에 따라 log(인구 수)를 그리면 대강 우리나라 인구 증가율의 변화를 직감할 수 있습니다.

 

그래서 귀찮게 일일이 시기별로 수익률을 구해서 그래프를 그릴 필요 없이 간단하게 데이터에 로그를 취한 후 로그 데이터를 그래프로 그리면 수익률이나 인구증가율 변화에 대해 감을 잡을 수가 있다는 것이죠.

 

 

 

2)

 

이론적으로 정규분포가 많이 쓰이는 이유는 표본수가 점점 늘어나면 대부분 이론상의 분포는 정규분포로 갑니다. 그 대표적인 것이 중심극한 정리(CLT)입니다.

 

중심극한 정리는 원래 분포가 무엇이든 이 분포에서 나온 데이터의 평균은 데이터 수가 많아지면 정규분포를 한다는 것이죠. 무슨 말이지 감이 잘 안오지요.

 

동전을 던지는 실험을 한번 해보죠. 만번을 던졌습니다. 즉 표본수, 데이터수는 만번입니다. 우리의 관심은 동전이 앞면이 나올 확률입니다. 이 확률은 우리가 알 수가 없습니다. 실험을 통해서 추측, 즉 추정을 해야 하는 것이죠. 그럼 만번 던져서 3100번 앞면이 나왔다면 우리 모두 다 동전이 앞면이 나올 확률은 0.31 정도라 이야기할 겁니다. 그러나 이게 정확하게 맞을 확률은 0이죠. 0.31, 31%가 진짜 동전이 나올 확률과 비슷한 값이라 생각할 겁니다.

 

이때 구한 동전이 앞이 나오는 백분율은 사실 우리가 잘 아는 표본 평균입니다. 처음 동전을 던질때 앞면이 나오면 1, 뒷면이 나오면 0으로 코딩하면 이건 (X1+X2+...,X10000)/10000이 됩니다. 즉 표본 평균이죠.

 

이런 만번 동전을 던지는 실험을 상상 속에서 시행을 해 봅니다. 똑 같은 동전을 100만명이 각각 독립적으로 시행합니다. 어떤 사람은 27.84%가 나올 수 있고, 어떤 사람은 33.012%가 나올 수 있고, 이 백만명이 던져서 나온 앞면이 나올 백분율 값을 분포로 그려내면 우리가 모르지만 진짜 동전이 앞면이 나올 확률을 중심으로 정규분포를 한다는 것이죠.

 

각 사람이 만번 던지는 것을 2만번, 5만번, 10만번 이런 식으로 실험 횟수, 즉 표본 수, 데이터 수를 늘려가면 위에서 이야기한 분포는 진짜 앞면이 나올 확률값을 중심으로 점점 집중하는 정규분포을 한다는 것이죠. 이런 가상 실험을 한다는 생각에서 이론적인 분포를 생각하는 것을 통계학에서 샘플링 이론이라 합니다. 우리가 아는 여론조사 같은 경우 어떻게 표본을 뽑을 것인가 하는 의미가 아닙니다. 즉 샘플링 이론은 두 가지 개념으로 사용됩니다. 여론조사시 표본을 어떻게 뽑을 것인가 하는 이론과 가상 실험을 해서 우리의 추정치가 어떤 모양의 분포를 할 것인가 하는 이론 이 두가지이고 주류 통계학에서는 두 번째 개념의 샘플링을 중요시 합니다. 사실 통계학 배우다가 제일 먼저 벽에 부딪치는 개념이 이 샘플링 이론입니다.

 

 

3)

 

여기 블로그을 자주 읽는 분은 아시겠지만 제가 주류 통계학에 매우 비판적인 사람입니다. 특히 주류 중에 주류라는 MVUE 개념의 추정 방법은 거의 쓸모가 없다고 이야기했죠. 사실상 실제 현실 문제에서는 주류 중 비주류인 MLE가 사용된다고 이야기했습니다. 이건 인공지능에서도 마찬가지입니다. 주류 중의 주류라는 학파는 왜 현실 문제에서 사용되지 않는가? 모형이 조금만 복잡해지면 애들이 주장하는 것을 구해 낼 수가 없습니다. 반면에 주류 중의 비주류인 MLE는 수식으로도 구해지는 경우도 많고, 수식으로 못 구해지면 수치해석, 즉 컴퓨터 알고리즘을 통해 근사치를 구해 낼 수 있는 경우가 많습니다.

 

또한 표본평균과 같이 표본 수, 즉 데이터 수가 많아지면 이 MLE도 역시 정규분포로 갑니다. 그것도 매우 좋은 정규분포로 갑니다. 즉, MLE로 추정하는 수식은 잘 모르지만 진짜 값에 매우 근사하게 다가간다는 것이죠. BAN 성질이라 합니다.

 

이 말이 무슨 뜻이냐 하면 MLE가 수식으로 정확하게 표현이 되면, closed form이라고 하죠, 이 수식을 통해 여러 가지 이론적인 성질을 규명해 낼 수 있습니다. 그러나 이걸 컴퓨터를 통해 수치해석으로 근사치를 찾는 경우는 정확한 수식모양을 모르기 때문이 이론적으로 어떤 성질을 가지고 있는지 모릅니다. 그러나 표본 수가 많으면 정규분포로 가기 때문에 표본 수가 적절하게 많다고 가정하고 이 정규분포를 가지고 성질을 논하게 됩니다.

 

우리가 많이 사용하는 회귀분석의 경우 회귀계수 값도 MLE이고 또 정확한 수식을 알 수 있습니다. 이를 통해 t 검증을 통해 어떤 변수가 영향력이 있는 변수인지, 아닌지를 알 수 있습니다. 최근 인공지능 때문에 많이 사용하는 로지스틱 회귀분석의 경우 MLE를 사용하지만 정확한 수식을 모릅니다. 그래서 이 경우 MLE이지만 회귀계수를 수치해석으로 근사치를 구합니다. 이렇게 근사치를 구한 것이 표본 수가 많으면 정규분포를 간다는 것을 이용해 가설 검증을 합니다. 구조방정식에서 경로계수 구하는 것도 다 수치해석으로 MLE를 구한 다음 정규분포로 간다는 성질을 이용해 가설 검증을 합니다.

 

 

4)

또 정규분포가 왜 좋은가 하면 매우 좋은 해석학 성질을 가지고 있습니다. 즉, 계산하기 매우 편합니다. 앞에서 이야기한 적이 있지만 이 정규분포식은 우리가 적분도 못합니다. 그래서 확률을 구할 때 시물레이션을 해서 구해야 합니다. 그러나 매우 좋은 성질도 가지고 있습니다. 즉 어떤 변수 X1, X2, ..., Xk가 다변량 정규분포를 한다고 하면

 

조건부 확률분포, 또는 주변 확률분포 모두 정규분포를 하고 이 분포는 정확하게 이론적으로 풀어집니다. 그래서 다변량 정규분포에서 여러분이 조건부 확률분포나 주변확률분포를 구하고 싶을 때 일일이 계산하거나 컴퓨터로 시뮬레이션 할 필요가 없다는 것이죠. 그냥 책에 보면 공식이 있습니다.

 

 

5)

 

앞에서 정규분포를 식을 보면 exponential 위에 있는 모양이 데이터 x에 대해 타원형을 합니다. 그러나 우리가 분포에서 모르는 값 모수 u를 중심으로 봐도 이것 역시 타원형 모양입니다. 즉 정규분포는 핵심만 보면 데이터 x와 모수 u에 대해 대칭적인 모양입니다. 따라서 이 정규분포는 데이터에 관련해서만 중요한 것이 아니라 베이지안, 즉 사전확률이나 사후확률분포에서도 중요한 역할을 합니다.

 

 

6)

 

이런 여러 가지 이유로 정규분포가 매우 좋고, 많이 사용됩니다. 그런데 이 정규분포의 모양을 결정하는 것이 타원형이라고 했습니다. 그래서 타원형에 대한 수학적 이론을 잘 아는 것, 즉 가운데 행렬 부분의 고유벡터나 고유값 이론을 잘 아는 것이 중요합니다.

 

 

 

 

2. 구글 검색 엔진 알고리즘

 

다음은 구글 검색 알고리즘에 대해 간단히 이야기 하겠습니다. 책에 간단히 소개되어 있어 여기에 한번 써 봅니다. PageRank 알고리즘이라고 하네요.

 

page rank이니까 웹문서를 중요성에 따라 순위를 매긴다고 생각할 수 있습니다. 그리니까 page가 보통명사로 생각할 수 있습니다. 그런데 이 알고리즘을 발표한 사람의 이름이 Page라고 하네요. Page라는 사람과 기타 몇몇이 발표한 논문에 실린 알고리즘이라 합니다. 물론 실제 구글에서 작동하는 알고리즘에 그 논문에 실린 알고리즘에서 여러 가지 변형을 했겠지요.

 

네이버나 다음 등 우리나라 검색 엔진 회사는 돈 벌 궁리부터 먼저 했지요. 그러나 구글은 검색 이용자가 진짜 원하는 문서를 찾는 방법부터 궁리를 한 것이죠. 이렇게 하면 장기적으로 검색 시장에서 선두를 찾지 할 수 있고, 이게 나중에는 전부 다 돈이 된다고 생각한 것이죠. 초기에 이런 생각의 차이가 구글과 우리나라 포탈간의 차이를 가져 온 것이라 보입니다.

 

구글 검색 알고리즘은 간단합니다. 예를 들어 ‘최순실’이라고 검색을 했다고 하죠. 그럼 최순실이라는 단어가 들어가 있는 웹문서, 홈피나 블로그, 또는 다른 SNS에서 최순실이 들어가 있는 모든 웹문서를 디비로 가지고 있습니다.

 

그런 다음 랜덤으로 하나의 문서, A라는 문서에서 출발합니다. 이 A라는 문서에 최순실에 대한 링크가 5개 있다고 하죠. 그럼 이 링크를 따라 다른 문서로 점프할 확률은 1/5이 됩니다. 이런 식으로 링크를 따라 계속 점프를 합니다.

 

최순실이라는 단어를 포함하고 있는 웹문서가 만개가 있다고 하면 그럼 만*만 크기의 전이행렬을 구할 수 있습니다. 즉 링크를 따라 마코프체인 프로세스가 됩니다.

 

이와 같이 랜덤으로 시작해서 링크를 따라 마코브체인 프로세스로 시뮬레이션을 계속하면 어떤 웹문서에 가장 많이 체류하는지 알 수 있습니다. 가장 많이 방문하는 웹문서가 가장 중요한 문서가 되고 검색 결과에 가장 먼저 노출을 시켜 줍니다.

 

사람들이 웹문서의 링크가 있어도 그 링크가 마음에 안들면 링크에 따라 추적하는 것이 아니라 바로 빠져 나와 다른 웹문서로 점프할 수 있습니다. 아니면 웹문서에 링크 자체가 없다면 다른 웹문서로 점프를 한다는 것이죠. 이 가능성에어느 정도 확률값을 주면 좀 더 현실적인 알고리즘이 될 수 있습니다.

 

좀 더 구체적인 알고리즘은 Hastie 등이 지은 “The Elements of Statistical Learning”이라는 책에 소개 되어 있습니다. 물론 시간이 있는 분은 Page 원 논문을 찾아 읽으면 되지요. 하여간 이것도 인터넷에 돌아다닙니다.

 

이 책에 있는 구글 알고리즘을 구체적으로 쓰면 아래 이미지와 같습니다.

 

 

 

(1-d)가 링크를 따라가지 않고 빠져 나와 다른 웹문서로 점프할 중요성이 됩니다. 나중에 정규화, 합해서 1이 되도록 조절 하면 확률 개념이 되죠. 입니다. 그래서 어떤 웹문서를 링크한 웹문서가 하나도 없더라도 이렇게 링크를 따르지 않고 랜덤으로 다시 점프해서 이 웹문서를 방문 할 수 있습니다.

 

Cj는 앞의 최순실 예에서 j 웹문서에 최순실이 링크 된 개수입니다. Lij은 링크가 있으면 1, 없으면 0, 그래서 j 웹문서에서 링크 개수가 5개 있으니까 Lij/Cj는 링크가 있으면 1/5, 없으면 0/5=0이 됩니다. 공식 뒤 부분 복잡한게 0이상이기 때문에 웹문서 중요도는 최소 (1-d)라는 값을 가집니다. 논문에서는 d 값을 0.85로 설정했다고 하네요. 그래서 어떤 웹문서도 최소 0.15의 중요성은 갖는다고 전제했고요.

 

식이 복잡한 것 같지만 이 책을 보면 이게 p가 웹문서 중요도 벡터, A를 전이행렬이라고 하면

 

p=Ap

 

형태로 고칠 수가 있다고 합니다. 전개 과정은 별 어렵지는 않지만 이것 연구할 사람이 아니면 구태여 해 볼 필요는 없겠지요.

 

위의 형태를 만족하는 p를 수학에서는 fixed point라고 합니다. 일반적으로 표현해서 어떤 함수 f(x)가 있을 때

 

f(x)=x

 

를 만족하는 x가 있으면 이때 x를 fixed point라고 합니다. 수치해석에서 중요한 개념입니다. 일반적으로 알고리즘을 G라는 함수로 생각하고, x를 우리가 찾는 답이라 하면

 

x(다음 단계)=G(x(이전 단계))

 

이런 식으로 계속 반복해서 답 x를 찾아갑니다. 그럼 이런 반복 작업을 어디서 멈추는가?

 

x(다음단계)=x(이전 단계)

 

일 때입니다. 즉 알고리즘 함수 G에 대해 답이 fixed point가 될 때까지 하는 것이죠. 

 

x=G(x)

 

를 만족할 때까지 반복 작업해서 찾아갑니다.

 

실제로는 x(다음단계)=x(이전 단계)가 아니고 두 값이 굉장히 비슷해지는 단계까지 찾아 갑니다.

 

실제 검색 장사를 하려고 하면 다음과 비슷한 순서로 해야 할 겁니다. 일단 장사 시작하기 전에 이 세상에 존재하는 웹문서에 있는 단어를 디비에 저장합니다. 쓸데없는 조사나 전치사 이런 것은 필요가 없겠지요.

 

그런 다음 이 디비에서 중요한 단어를 포함하는 웹문서 디비를 각각 만듭니다. 박근혜의 경우 박근혜를 포함하는 웹문서만의 디비를 만들고요, 최순실의 경우 최순실를 포함하는 웹문서만의 디비를 따로 만듭니다. 그래서 실제로는 백과사전에 나오는 단어라든지, 중요한 잡지나 최근 신문기사에 나오는 단어들을 중심으로 해당하는 단어만을 포함하는 웹문서 디비를 만드는 것이죠.

 

그런 다음 위 PageRank 알고리즘을 이용해서 이미 각 웹문서의 중요성을 랭크를 매깁니다. 그런 다음 시장에서 웹문서 검색 장사를 하는 것이죠.

 

이 알고리즘을 이해하면 검색 사기 장사를 할 수도 있겠지요.

 

일단 천개나 만개 정도 가공 웹문서를 만듭니다. 여기에 시간과 돈이 좀 들어가겠네요.

 

그런 다음 어떤 가게가 자기네 가게가 웹 검색에 뜨게 해 달라고 돈을 주면 이 만개 되는 가공 웹문서에 이 가게 웹문서 주소를 링크합니다. 이건 간단한 작업입니다. 프로그램 좀 잘 하는 친구에게 부탁하면 쉽게 짤 수 있습니다. text process 하는 프로그램은 이 쪽에서는 기초적인 작업입니다. C white book에 보면 자세한 알고리즘이 있습니다.

 

위에 설명한 것의 Page Rank 알고리즘의 예를 Hastie 책에 있는 예를 아래에 소개합니다.