디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

구글 검색 알고리즘의 원리 3

...(141.223) 2007.04.24 14:41:40
조회 719 추천 0 댓글 7


앞에서는 쇼프로와 K-1이라는, 그나마 그 성격이 확연히 다른 주제를 예로 들었는데,
만약 두 주제의 성격이 다소 비슷한 면이 있다 라고 한다면,
(예를 들면 \'리눅스\' 관련 문서들과 \'윈도우즈\' 관련 문서들)
아래 그림처럼 훨씬 더 골때리는 상황이 생길 수 있어.

(단어 2)
^
|                 o o o
|              o          o o
|           o *     x          o       x
|          o           x x            x 
|                            x   x  x 
|                               
|
-------------------------------> (단어 1)

o = 주제 1에 속하는 문서들
x = 주제 2에 속하는 문서들
* = 쿼리

사용자가 위의 별표와 같은 쿼리를 줬을 때, 올바른 결과라고 하려면
주제 1에 속하는 문서들(그 중에서도 쿼리와 가까이 있는 문서들)이 상위에 올라와야겠지.
그런데 위 그림을 보면, 주제 2에 속하는 문서들 중 몇몇 개가 주제 1의 문서들보다
쿼리에 더 가까이 있기 때문에, 걔들이 상위에 올라가게 된다는 문제가 생기지.

사실 이전 글에 나온 예의 경우, 올바른 분류에 방해가 되는 단어(\"최홍만\")와 도움이 되는 단어(\"K-1\")가 확실히 구분이 되었었고,
따라서 방해가 되는 단어들만 어떻게 잘 찾아낸 다음,
그 단어들의 빈도수는 무시하고 거리를 계산하면 올바른 결과를 얻을 수가 있었어.
하지만 지금 이 예제의 경우는 이런 식의 해결이 불가능하지.

그런데, 위 그림을 보다보면 한 가지 단서가 나와.
그림에서 쿼리 근처 영역만 잘라놓고 보자.

|                 o ←A
|       D→  o
|     C→ o *     x ←B  
|          o 
|                          

일단 그림에서 보듯이 A와 쿼리 사이의 직선 거리는 B와 쿼리 사이의 직선 거리보다 멀지.
그렇지만.. 직선 거리만 보면 그렇지만...
쿼리와 C, 쿼리와 D, C와 D, D와 A의 거리들은
쿼리와 B의 거리보다 가깝지.

이런 점에 착안을 해서 나온 아이디어가 Markov random walk 이라는 건데,
쿼리의 위치에서 시작을 해서 A 또는 B에 도착하게 될 때까지
매 턴마다 랜덤하게 임의의 포인트로 이동을 하는 거야.
단, 각 포인트로 이동하게 될 확률은, 현재 포인트와의 거리가 가까울 수록 큰 것이 핵심.

즉, 현재 위치가 쿼리라면, 다음 턴에 방문하게 될 포인트로는
C가 가장 확률이 높고 그 다음이 D, B, A 순이 되는 거지.
현재 위치가 D라면, 다음에 방문할 포인트로는 A/C/쿼리가 각각 비슷한 확률을 갖고 B는 그보다 좀 작겠지.

그림을 보면, 쿼리에서 시작해서 A까지 갈 수 있는 유망한(= 비교적 높은 확률을 가지는) path들이 몇 개 있지?
쿼리->C->D->A, (확률값은 P(쿼리->C)*P(C->D)*P(D->A))
쿼리->D->A, (확률값은 P(쿼리->D)*P(D->A))
그밖에 되돌아왔다 다시 방문하는 경우들.. (쿼리->C->쿼리->D->A 등등)

결국 쿼리에서 시작해서 이리 저리 포인트를 거쳐 최종적으로 A에 도착할 확률은,
위의 path들 각각의 확률을 모두 더한 것이 될 거야.

반면, 쿼리에서 시작해서 B로 갈 수 있는 유망한 path는 쿼리->B 하나 뿐이지.
쿼리를 제외한 나머지 포인트들과는 거리가 너무 멀어서,
다음 턴에 방문하게 될 확률이 낮으니까.
-> 잘 납득이 안 간다면 곱하기의 성질을 생각해봐.
n개의 값들을 곱한다고 했을 때, 이 중 단 한 개의 값이라도 작으면(예를 들면 0.01)
그 곱셈의 결과는 작아지지.
(반면 덧셈은, n개의 값을 더할 때 이 중 몇 개의 값이 작더라도 결과에 무진장 큰 영향은 안미치고.)
가령 쿼리->C->B 라는 path를 생각해 보면,
이 path를 타고 B까지 갈 확률은 P(쿼리->C)*P(C->B) 가 되겠지.
그런데 이때 P(C->B)가 너무 작기 때문에 이 path 전체의 확률까지 같이 작아져 버리는 거야.
쿼리->A->B, 쿼리->D->B 등등 모두 마찬가지지. 쿼리->B로 직접 가는 경우를 빼고...

즉... 이제 우리는 두 문서간의 유사성을 판단할 때 그들 사이의 직선 거리를 생각하는 대신,
\"이 문서에서 Markov random walk을 했을 때 저 문서에 도착할 확률\"을 생각하면 되는 거야.

여기서 이런 의문을 가지는 횽아들이 있을 거야.
\"A에서 B로 가는 path만 센다고 하더라도 A->B, A->C->B, A->D->B, A->D->C->D->A->B 등등등
무수히 많은 path들이 존재하는데 얘네들 각각의 확률을 어떻게 일일히 다 구해서 더해주나?\"

이에 대한 답을 겸해서, 알고리즘을 써 볼께.

1. 우선 각 문서들 사이의 거리를 가지고 기본 확률을 구해야겠지.
즉, d(A,B)가 있을 때 P(A->B)를 정하는데,
이건 보통, 초월함수 e를 이용해서 변환을 해.
P(A->B) = exp(-d(A,B)) / {모든 point들에 대해 exp(-d(A,x))의 합}
(모든 point들에 대한 합으로 나눠주는 이유는,
 A에서 임의의 포인트로 움직일 확률의 전체 합이 1이 되어야 하니까.)

2. n개의 문서가 있다고 하면, 얘들에게 임의의 순서로 차례(index)를 부여 해. 1, 2, ..., n 까지.
그런 다음, K라는 행렬을 정의하는데
K의 i번째 행, j번째 열에 들어갈 원소의 값을 앞에서 구한 P(i번째 포인트 -> j번째 포인트) 로 설정해.

3(핵심). I를 단위행렬(대각선 원소만 1이고 나머지는 다 0인 행렬)이라고 했을 때, 마지막으로
Q = inverse(I - 0.9*K)    (0.9는 예를 들면 그렇다는 거고, 0 초과 1 미만의 값이면 됨)
이렇게 계산을 하면, Q의 i번째 행, j번째 열의 원소값은
i번째 포인트에서 Markov random walk을 해서 j번째 포인트로 도착할 확률,
즉 우리가 구하고자 하는 유사성, 그 값이 나오게 돼.

Q가 왜 이런 값이 나오는지는 위의 역행렬 공식을 테일러 전개해 보면 알 수 있어.
inverse(I - 0.9*K) = I + 0.9*K + 0.9^2*K^2 + 0.9^3*K^3 + ....
이렇게 되거든.

이때 K^n의 i번째 행, j번째 열의 원소값은
i번째 포인트에서 Markov random walk을 했을 때 \"정확히 n턴 이후에\" j번째 point에 도착할 확률을 나타내.
(I는 K의 0제곱, 즉, 시작 지점에서 아직 전혀 이동을 안한 상태를 의미)
따라서 위 식을 말로 풀어 쓰면
Q = \"0턴 이후에 도착할 확률 + 1턴 이후에 도착할 확률 + 2턴 이후에 도착할 확률 + ....\"
이렇게 되는 거지.
따라서 모든 가능한 path들의 확률을 빠짐없이 다 더해주는 효과가 있지.
각각의 path를 일일히 세지 않아도 말이지...

요기까지가 본론이야.
이 알고리즘의 장점은, 검색할 데이터의 종류가 특정 응용 분야에 한정되어 있지 않다는 점이지.
문서, 그림, 비디오 등등, 벡터화 할 수 있는 모든 종류의 데이터들의 검색에 모두 쓰일 수 있고,
심지어 벡터화 할 수 없는 데이터라 하더라도(그런게 있나 모르겠지만;;)
임의의 두 아이템의 직선 거리(또는 유사성)만 정의할 수 있으면 이 알고리즘을 쓸 수 있어.

구글의 PageRank 알고리즘은 이 아이디어를 \"웹 검색\" 이라는 분야에 적용을 한 케이스인거지.
이에 대한 얘기는 다음 글에 쓸께. 이제 정말 마지막이야;

추천 비추천

0

고정닉 0

0

원본 첨부파일 1

댓글 영역

전체 리플 0
등록순정렬 기준선택

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 거지분장이 찰떡인 스타는? 운영자 20/12/02 - -
AD [댓글 이벤트] 삼성디프 12월 고객감사전! 운영자 20/12/02 - -
공지 프로그래밍 관련 내용이 있어야 합니다. [17] 운영자 20.09.28 1792 34
1547431 인지과학대학원어디가 손발이시립니다갤로그로 이동합니다. 05:42 4 0
1547430 웹 이미지 업로드해서 랜덤으로 뿌려주는 사이트 같은거 없음? 동반꿀갤로그로 이동합니다. 05:41 11 0
1547429 인공무현 ai 배운다고 그만 까불고 이거보고 생각 잘해라 어계세키위갤로그로 이동합니다. 05:36 12 0
1547427 텐서플로우는 오픈ai가아니다 [2] 인공무현갤로그로 이동합니다. 05:31 25 0
1547426 여기 프로그램중 알맞는게 어떤걸까 ??? [3] ㅇㅇ(1.238) 05:20 34 0
1547424 인공무현 패키지 싱글 게임 하냐? 레식이런거 말고 [1] 어계세키위갤로그로 이동합니다. 05:05 18 0
1547423 php문법 대강 아는데 바로 라라벨 ㅇㅇ(115.86) 05:04 14 0
1547422 4년제 대학 졸업하고 바로 취업못하는 사람들 비율 몇%나 되냐? [2] 동반꿀갤로그로 이동합니다. 05:04 30 2
1547421 주식해보니까 창업을 보는관점이 확달라지노 [1] 인공무현갤로그로 이동합니다. 04:59 46 0
1547420 스타트업이라는게 결국 주식쇼구나 인공무현갤로그로 이동합니다. 04:57 30 0
1547419 리액트 네이티브 강좌듣고 앱 만들면서 실습 중인데 [3] ㅇㅇ(115.126) 04:51 32 0
1547418 2.프라미스 abort 많이들 함? [67] 딱국갤로그로 이동합니다. 04:48 115 0
1547417 그냥 빨리 잘걸 [1] 아무거나1234갤로그로 이동합니다. 04:36 23 0
1547416 열심히 공부하는 프갤러들을 위한 선물 [3] ㅇㅇ(115.86) 04:35 43 0
1547415 1. class vs return [1] 딱국갤로그로 이동합니다. 04:34 41 0
1547414 백단에서 데이터 관리 질문. [13] capcha_test갤로그로 이동합니다. 04:33 47 0
1547413 s3에 파일 업로드하고 나서 로그에 키 두번뜨는거 거슬리네 [3] 리삐삐갤로그로 이동합니다. 04:26 32 0
1547412 비트캠프나 삼성멀티캠이나 쌍용 이세개중한곳가면 ㅇㅇ(106.101) 04:25 20 0
1547411 업무효율을 위한 전담 뻑뻑피는 중.. 리삐삐갤로그로 이동합니다. 04:25 18 0
1547410 졸려서 미칠거같음 리삐삐갤로그로 이동합니다. 04:24 15 0
1547409 아 스트링파이해서 올리는게 맞네 리삐삐갤로그로 이동합니다. 04:22 15 0
1547407 etl 글루에서 할 예정이었는데 리삐삐갤로그로 이동합니다. 04:15 11 0
1547406 그래도 너무 이론만 하면 지칠거같음 sfdsa갤로그로 이동합니다. 04:15 19 0
1547405 헤으응 고3 대학 어쩌농 [2] ㅇㅇ(219.254) 04:14 53 0
1547404 구찮으니까 일단은 파싱해둔 s3만 쓰자 ㅇ.ㅇ.. 리삐삐갤로그로 이동합니다. 04:12 13 0
1547403 요건 추가 되도 다 받아들일 수 있게 좀 카탈로그 넓게 잡을까 리삐삐갤로그로 이동합니다. 04:09 13 0
1547402 앞으로 할 예정 [2] 리삐삐갤로그로 이동합니다. 04:06 39 0
1547401 철학과도 나쁘진 않을거같아 sfdsa갤로그로 이동합니다. 04:05 23 0
1547400 아 내가 string으로 저장하고 있었네 [3] 리삐삐갤로그로 이동합니다. 04:05 32 0
1547399 본인 지잡대 소프트웨어학과 학생인데 [4] ㅇㅇ(211.171) 04:03 48 0
1547398 AVL 트리 O(logN)에 동작하도록 개선했다 [7] ㄱㄹ갤로그로 이동합니다. 03:58 60 0
1547396 수학과도 재밌어보이는거 많음 sfdsa갤로그로 이동합니다. 03:56 25 0
1547395 웹은 아직 개발진행형인 거 같음 redux도 다음 세대에 교체될 듯 [12] 나트륨찡갤로그로 이동합니다. 03:38 72 0
1547393 밑글 사진 안올라가는데 비밀번호 까먹어서 사진첨부 ㅁㄹㅇㅁ(119.203) 03:35 45 0
1547392 야 리액트판에 퍼블리셔 생존하냐?? ㅇㅇ(118.235) 03:34 27 0
1547390 이거 오류 왜뜨는거냐? [1] ㅁㄹㅇㅁ(119.203) 03:32 21 0
1547389 국비중인데 강사 ㅈ같다 (국비 50일째) [6] ㅇㅇ(218.157) 03:31 60 1
1547387 오늘 한 일, 할일 ㅇㅇ(39.119) 03:30 16 0
1547386 redshift 처음으로 만들예정.. 리삐삐갤로그로 이동합니다. 03:28 20 0
1547385 저 포인터 관련 질문이요 ㅇㅇ(39.7) 03:27 22 0
1547384 아니 aws glue 이넘 도통 모르것메 [3] 리삐삐갤로그로 이동합니다. 03:26 31 0
1547383 디자이너랑 연애하고싶다 [2] 야근맨(220.117) 03:24 29 0
1547382 아이디어만으로 개발자 구하는애들 있더라 [5] 헬마스터갤로그로 이동합니다. 03:16 100 0
1547381 딸깜 던지고 간다 [1] ㅇㅇ(223.62) 03:16 88 0
1547380 useSelector [6] 야근맨(220.117) 03:13 52 0
1547379 인프런 파이썬 세일하는데 [1] ㅇㅇ(211.238) 03:12 175 0
1547378 react에서 redux쓰면 [6] aZe(106.250) 03:11 65 0
1547377 빌드는 esbuild 야근맨(220.117) 03:10 22 0
1547376 나도 리덕스싫어 빨리 새로운거 쓰고싶다 [12] 야근맨(220.117) 03:09 53 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

이슈줌NEW

1/6

힛(HIT)NEW

그때 그 힛

1/3