본 글은 성균관대학 교수인 이상구 교수님이 선형대수학 배워서 뭐해? 라는거에 대해 설명하기 위해 쓴 글인데 이해하기 쉽고 간단해서 소개해.

 

좋은 검색엔진은 어떻게 동작해야할까?

 

간단히 생각해보면 내가 검색한 키워드가 본문에 많이 들어가 있으면 좋을거야

근데 만약 문서에

 

 

"""

스타크래프트 립버전 1.16.1다운 스타크래프트 립버전 1.16.1다운 있을 것 같았다. 그건 실로 벅찬 감격이었다.고마워요 본드. 덕분에 마음이 아주 편해졌어요.고마워할 필요는 없어.킴은 미소지으며 손을 내밀었다. 니콜라는 기쁜 얼굴로 악수를

리를 질렀다. 이건....정말 상황 파악이 느린 녀석이로군. 네가 지금 어디에 스타크래프트 립버전 1.16.1다운 알기나 하는 거야 어리광을 받아주는 것도 여기까지다. 어서 이름이나 말해 어디서 감히 스타크래프트 립버전 1.16.1다운 지르나 천한

"""

 

이런식으로 의도적으로 키워드를 때려박은 문서가 있다면?

이건 우리가 원하는 검색결과물이 아니지.

 

그래서 이런 쓰레기랑 진짜 가치있는 페이지랑 어떻게하면 구분할 수 있을까를 스탠포드 다니던 레리페이지라는 학생과 세르게이 브린이라는 학생 둘이 아이디어를 내게 돼 (이후 구글 설립자가 됨)

 

가치있는 페이지라면 그걸 인용한 사람들이 많을거니까 같은 키워드가 들어있다면 인용이 많이 된 페이지가 좋은 페이지 아닐까? 라는 아이디에서 착안해서 Page-rank algorithm이라는 방법을 개발하게 돼.

 

페이지 랭크 알고리즘은 다음의 순서로 계산돼

먼저 웹 페이지간 서로 연결관계를 파악해

 

아래 사진에서

페이지 a를 인용하는 문서는 b,c,d이고

페이지 b를 인용하는 문서는 a,d이고

주루룩 쓸수 있겠지

 

이를 인용관계가 있으면 1을 채우고 없으면 0을 채우는 방법으로 행렬을 만들면 다음과 같이 돼

 

a->a로 가는 길은 없으니 A(1,1)=0, a->b로 가는 경로는 있으니 A(1,2)는 1 이런식으로 행렬이 만들어진거야.

근데 행렬은 신기한게, 이 행렬을 곱연산을 한 A*A의 1행 2열 성분은 A에서 어딘가를 거쳐 B로 간 경로를 의미하게 돼.

마찬가지로 A*A*A의 1행 2열 성분은 A에서 어딘가를 거치고 어딘가를 거쳐서 B로 갈 애들을 의미하게 돼.

 

그러면 이걸 n번 연산하면 대충 n번 이후에 각 페이지에 애가 위치할 애들의 숫자가 되겠지? 

근데 저 행렬을 바로 쓰기에는 문제가 하나 있어. 5열이 0이라서 한번 페이지E에 도달한 애들은 다음번엔 사라져버리는 문제가 생기게 돼.

 

그래서 이를 해결하고자 몇가지 조작을 하고 수학적인 수렴조건을 맞춰서 행렬을 새로 만들게 돼.

그게 바로 구글행렬이야.

 

저 연결관계를 바탕으로 구글행렬을 만들면 요렇게 돼 사실 아이디어는 같은데 수학적인 조작만 좀 가한거야 더 디테일한 내용이 궁금하면 교수님의 자료를 한번 확인해봐 (http://matrix.skku.ac.kr/2012-e-Books/KMS-News-LA-Google-SGLee.pdf)

 

 

이제 정상적으로 수렴하고 정보가 사라지지 않게 행렬도 바꿨겠다 한번 n번 연산해서 어떤 결과가 나오는지 확인해보자.

 

아래 그림은 20번 연산을 한 그 결과물이야 (matlab m 파일도 첨부하니 궁금하면 돌려봐도 좋아)

g=[0.03, 22/25, 91/200, 47/150, 1/5;
    91/200, 3/100, 3/100, 47/150, 1/5;
    3/100, 3/100, 3/100, 47/150, 1/5;
    91/200, 3/100, 3/100, 3/100, 1/5;
    3/100, 3/100, 91/200, 3/100, 1/5];

init_cond = [0.2;0.2;0.2;0.2;0.2];
History = [];

for i=1:1:20;
    g_mul = g^(i);
    prob = g_mul*init_cond;
    History = [History, prob];
end
plot(History')
legend('a','b','c','d','e')

 

 

이말대로면 a>b>d>c>e순으로 중요하다는 결과를 얻게 돼.

왜 이런 결과가 나왔는지 한번 알아보면

 

a는 누가봐도 중요해 그치? 왜냐면 엄청나게 많은애들이 얘를 참조하고 있으니까.

그리고 b보다는 d가 더 중요한게 d는 a라는 강력한애가 얘를 참조해주고 있고

e가 약한 이유는 e를 서포트해주는건 d 뿐이라 약하게 나온거야.

 

그래서 이런 방식을 사용하면 더 많은 사람들이 가치있다고 생각한 페이지를 정량화하여 알수 있게되기에 이를 바탕으로 구글의 검색엔진을 설계했어.

 

그렇다면 이런 방식이 가지는 문제점은 뭘까?

문제점은 만약 여기서 강력한 a가 누군가를 참조하면, 그게 사실 가치없는 정보더라도 가치있는것 처럼 계산이 된다는거야.

그래서 예전에 스탠포드 페이지가 강력한 a였는데 돈받고 몰래 하꼬 사이트 링크해주는 방법으로 뒷돈을 받았다는 썰도 있어ㅋㅋ.

 

이걸 그럼 어디다 쓸수 있느냐, 그래프 형태로 구성된 관계에서 어떤게 더 중요한건지 정량화 하는데 사용할 수 있어.

 

예를들어서 싸이월드 1촌관계도, 페북 친구관계가 있으면 이중 누가 진짜 인싸고 누가 아싸인지 정량적으로 구분이 된다는거지