디시인사이드 갤러리

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

갤러리 본문 영역

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

...(141.223) 2007.04.24 14:41:40
조회 718 추천 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/10/27 - -
AD [삼성 디지털프라자] 가전을 나답게 BESPOKE&그랑데AI 운영자 20/10/23 - -
공지 프로그래밍 관련 내용이 있어야 합니다. [14] 운영자 20.09.28 898 18
1509253 string 함수하나 만드는데 2시간 걸리네.. [1] 뭐하냐지금갤로그로 이동합니다. 05:36 3 0
1509252 생활코딩 html 보는데 실습은 뭘로 해야함? [2] ㅇㅇ(125.189) 05:30 13 0
1509251 인덱스 거는 방법론적인 원ㄹ도 모르는게 뭔 풀스택이냨ㅋㅋㅋㅋㅋㅋㅋㅋ 솔직맨갤로그로 이동합니다. 05:24 11 1
1509250 풀스택의 상위호환은 아키텍쳐임 솔직맨갤로그로 이동합니다. 05:23 11 1
1509249 이제는 페북에 이어 kt마저 위키추상화갤로그로 이동합니다. 05:16 14 0
1509246 얘들아 난 페북으로 간다 [1] 위키추상화갤로그로 이동합니다. 04:33 42 0
1509245 서른다섯번째 문제 최소힙 파이썬4주완성갤로그로 이동합니다. 04:18 35 0
1509244 풀스택 다음 스텝은 뭐냐? [3] ㅇㅇ(124.44) 04:09 39 0
1509243 오늘 집합론이랑 일반물리복습마무리하고... 영어 소설 읽던거마무리하고.. 인공무현갤로그로 이동합니다. 04:07 23 0
1509242 헤르미온느 따먹은 네빌롱바텀 근황.jpg 동반꿀갤로그로 이동합니다. 04:04 51 2
1509241 리액트 네이티브를 이용한 특강에 참여하게됐는데요 ㅇㅇ(125.189) 04:03 15 0
1509240 혹시 S3 서울리전에 야짤 올리면 불법인거 아냐???? [4] ㅇㅇ(117.111) 03:51 54 0
1509239 서른네번째 문제 아나그램 파이썬4주완성갤로그로 이동합니다. 03:49 22 0
1509237 아 좀 한번에 연락 좀 하지말고 ㅇㅇ(61.40) 03:48 15 0
1509236 학교 과제땜시 리눅스에서 어셈으로 코딩하는데 [2] dd(61.77) 03:45 45 0
1509235 구글 아이콘 바뀐 거 나만 마음에 들어하나? [1] ㅇㅇ(14.63) 03:41 35 0
1509234 아이폰은 어플내 폴더 접근할수없음? ㅅㅂ 각성피에로(110.47) 03:41 28 0
1509233 커뮤니티 사이트의 게시판 보드 디자인 관련 [1] 허헉(123.142) 03:40 38 0
1509232 어플 3개 개발한 회사 vs 이제 막 시작한 [14] ㅇㅇ(61.40) 03:38 58 0
1509231 축구나 해외야구 api 어디가 젤 좋음? ㅁㄴㅇㅁㄴㅇ(106.242) 03:31 13 0
1509230 느긋하게 공부나 좀 하고 싶다. [3] 솨르(58.87) 03:30 37 0
1509229 솨르좌 / 와 이런 버전도 잇구나 나트륨찡갤로그로 이동합니다. 03:30 26 0
1509228 솨르좌 / 와 이런 그림도 잇구나 ㅇㅅㅇ [4] 나트륨찡갤로그로 이동합니다. 03:26 46 0
1509226 솨르좌 / ㅓㅜㅑ [6] 나트륨찡갤로그로 이동합니다. 03:21 64 0
1509225 님들 졸작 안드로이드어플 만드는데 질문좀용 [4] ㅇㅇ(119.194) 03:16 52 0
1509224 정선호-비주얼베이직2015 책 있는친구...? 완전급함(180.69) 03:14 15 0
1509223 내 클론코딩 필기 수준 이정도면 ㅇㅈ? [9] 솨르(58.87) 03:13 85 0
1509222 ffmpeg 잘알있음? ㅇㅇ(175.196) 03:12 29 0
1509221 아니 이새끼들 기술 스택쓰는거 다 사기네?? [5] ㅇㅇ(61.109) 03:07 61 0
1509220 LOC(코드수) 는 말 그대로 코드 라인수를 말하는 것 [3] 루비(118.216) 03:01 40 0
1509219 개 좆박았다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [3] 솔직맨갤로그로 이동합니다. 02:59 45 0
1509218 솔직히 인공지능 [1] ㅇㅇ(118.235) 02:55 31 1
1509217 어제 이번주에 신입왔는데 이새끼 [4] ㅇㅇ(59.14) 02:50 62 0
1509216 크리스마스 하면 이마트만 생각나 ㅇㅇ(218.54) 02:46 18 0
1509215 곧크리스마스니 스노우효과만들가 [2] 피에로는배달원갤로그로 이동합니다. 02:42 31 0
1509214 자야지 슬슬 [1] ㅇㅇ(218.54) 02:41 16 0
1509212 와 스프링 개좆같다. 왜케 어렵냐 ㅇㅇ(121.130) 02:39 20 0
1509211 국비충만 몰래 들어와봐 [1] ㅇㅇ(223.62) 02:39 28 0
1509210 대체 이게 뭔 뜻이다냐 ㅇㅇ(124.51) 02:37 28 0
1509209 구글캘린더 아이콘도 바꿔버렸노 헬마스터갤로그로 이동합니다. 02:35 32 0
1509207 본인 입갤함 [3] 솔직맨갤로그로 이동합니다. 02:22 48 0
1509206 백준 이거 node js readFileSync 머임 [4] 솨르(58.87) 02:21 51 0
1509205 내가 싫어하는 부류 [4] 산기대17세갤로그로 이동합니다. 02:20 74 0
1509204 아무리 생각해도 구글이 짱이다 나트륨찡갤로그로 이동합니다. 02:20 26 0
1509203 c 코딩 질문 받아주시나여 [11] ㅇㅇ(110.13) 02:19 61 0
1509201 과제 우액 [1] 저기,,갤로그로 이동합니다. 02:17 26 0
1509200 구글 음모론 고급정보 검색 잘 안댐 ㅇㅅㅇ 나트륨찡갤로그로 이동합니다. 02:16 26 0
1509199 방금 외주요청 들어옴 Python갤로그로 이동합니다. 02:16 25 0
1509198 나는 컴활을 왜 붙들고있는것인가 ㅇㅇ(220.82) 02:15 24 0
갤러리 내부 검색
전체게시물 정렬 옵션

오른쪽 컨텐츠 영역

이슈줌NEW

1/6

힛(HIT)NEW

그때 그 힛

1/3