태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

markov's Blog
Intelligent IF

랭킹은 검색 엔진의 핵심 기술이라고 할 수 있다. 이번 글에서 다룰 랭킹 기술은 구글의 PageRank와는 또 다른, 보다 직관적인 접근 방법이다.

랭킹이란 줄 세우기이다. DB에 아이템이 총 N개 (x1, x2, ..., xN) 있다고 할 때, 이들을 1등부터 N등까지 줄을 세울 방법을 말한다. 예를 들면 x5, x2, x10, x9, x1, ... 이런 식으로 줄을 세워볼 수 있다.
이때 줄 세우는 기준으로 다음과 같이 여러 가지를 생각해 볼 수 있다.
  1. 내용 기반: 각 아이템과 검색어(쿼리)를 벡터화 한 다음, 해당 벡터 공간에서 검색어와의 거리 순으로 줄을 세운다. 여기에는 사용자의 어떤 주관도 개입되지 않으며, 아이템의 내용이 서로 얼마나 유사하냐 하는 것으로만 평가를 하게 된다. 널리 사용되는 유사도 측정 방법은 cosine similarity이다.
  2. 링크 구조 기반: 널리 알려진 PageRank가 바로 이런 방식이다. 링크 구조만 이용한다면 내용의 유사성을 완전히 무시하고 랭킹하게 되지만, PageRank 알고리즘을 검색어 의존적인 방식으로 수정하는 경우(주1), 통상적인 직선 거리 대신 Markov random walk을 이용하여 유사도를 측정하는 내용 기반 랭킹 알고리즘이 된다(보다 자세한 내용은 이 문서를 참고).
  3. 선호도 기반(주2): 사용자들에게 각 아이템에 점수를 매기게 한 다음 줄을 세울 수도 있다. 예를 들어, 영화는 보통 '별 5개', '별 2개 반' 하는 식으로 점수를 매기곤 한다. 물론 선호도 기반에서도 내용이 유사한 아이템은 대체로 비슷한 점수가 매겨질 것이다. 하지만 '내용이 어디까지 얼마나 비슷해야 점수도 비슷하게 매겨지는지', 즉, 거리와 점수의 비는 벡터 공간 내에서 균일하지 않고, 각 영역마다 천차만별이 된다. 어떤 영역대에서는 내용상 아주 약간의 차이만으로 점수가 몇 점씩 왔다갔다 할 수 있고, 다른 영역대에서는 다양한 내용의 아이템들이 비슷한 점수를 갖고 넓게 분포해 있을 수도 있다.
  4. 그밖에 다양한 기준들...

주석 보기


여기서 한 가지 의문이 생긴다.

"아니 그렇다면 우리는 각각의 기준마다 별개의 랭킹 알고리즘을 연구해야 하는 건가요? 나는 알고리즘 하나 만들어놓으면 온갖 기준에 대해서 다 돌아가도록 하고 싶은데..."

즉, 일반화의 욕구다.
물론 일반화의 장점은 비단 이것 뿐만이 아니다. 서로 제각각의 기준으로 세운 수백 수천 가지의 줄들을 하나의 알고리즘 안에서 1개의 줄로 통합할 수 있다는 장점도 있다.

일반화를 위해, 우리는 다음과 같은 데이터가 들어올 것으로 가정한다.

줄1: x1, x99, x20, x5, x35, ...
줄2: x4, x18, x7, ...
줄3: x35, x20
줄4: x56, x23, x22
...

즉, 데이터 하나하나의 단위는 '줄'이다(줄의 앞에 나온 아이템이 뒤에 나온 아이템보다 높은 순위를 가진다). 그밖에 좀 더 구체적으로,
  • 각각의 줄은 임의의 기준을 가진다. (각 줄마다 기준이 서로 제각각, 물론 같을 수도 있고)
  • 각 줄이 정확히 어떤 기준을 써서 만든 줄인지는 몰라도 된다.
  • DB 안의 모든 아이템에 대해 줄을 세울 필요는 없다. (위의 예에서 줄3은 아이템 2개, 줄4는 아이템 3개만 골라서 세운 줄이다)
  • 일관성이 맞지 않을 수도 있다. (위의 예에서 줄1은 x20을 x35보다 높은 순위로 평가했는데, 줄3은 그 반대다)
한 마디로, 최대한 제약 없고 유연하게 데이터를 받겠다는 것이다. 우리의 목적은 일반화니까.
하지만 길이도 제각각이고 일관성도 맞지 않을 수 있는 수많은 줄들을 어떻게 해야 하나로 통합할 수 있을까?

우선, 일관성이 맞지 않는 문제는 다수결의 원칙, 즉 '서로 상충되는 경우 더 많은 수의 줄들의 의견을 따른다'는 방법으로 해결할 수 있다.

다음으로, 길이가 제각각인 문제는 transitivity(이행성), 즉 'A>B이고 B>C이면 A>C이다' 라는 규칙을 가정함으로써 해결한다. 즉, 하나의 긴 줄을 여러 개의 pair(아이템 2개짜리 줄)로 쪼개는 것이다.
위의 예에서 줄1: x1, x99, x20, x5, x35, ... 은 다음과 같이 쪼갤 수 있다:

줄1.1: x1, x99
줄1.2: x99, x20
줄1.3: x20, x5
줄1.4: x5, x35
...

여기서 기호를 하나 정의하자. si = (a, b, >) 라고 한다면, "i번째 pair si는 a > b" (즉 아이템 a가 아이템 b보다 순위가 높다) 라는 의미이다. 마찬가지로 sj = (c, d, <) 와 같이 c < d를 의미하는 pair도 있을 수 있다.
이 기호를 사용하여 일반화된 문제를 중간 정리해 보면 다음과 같다:

N개 아이템에 대해 si = (xi, xi', yi) 와 같이 정의되는(yi<, > 중 하나) pair M개(s1, s2, ..., sM)가 주어졌을 때, 가장 많은 개수의 pair와 일치하는 total ordering을 구한다.

  1. total ordering이란 N개 아이템 모두에 대해 세운 길이 N짜리 줄을 의미한다.
  2. 어떤 pair si와 주어진 total ordering이 일치한다는 의미는, si가 xi > xi' 라면 total ordering에서도 xi가 xi'보다 앞에 있어야 한다는 것이다. 물론, 꼭 바로 앞은 아니어도 된다.
이렇게 문제를 설정해 놓고 보니 combinatorial로 보인다. 즉, 최적의 total ordering을 구하기 위해 N! = N(N-1)(N-2).. 개의 모든 가능한 total ordering들을 나열한 다음, 이들 각각에 대해 일일히 M개의 pair 중 몇 개와 일치하는지 검사하는 방법이 우선 떠오른다. 하지만 이 방법은 complexity가 factorial time으로 polynomial algorithm이 아니다.

보다 효율적인 방법은 랭킹 함수를 학습하는 것이다(주3). 랭킹 함수란, 어떤 아이템에 대한 명세(specification)를 입력받으면 그 아이템에 대해 점수를 매겨주는 함수이다. 즉, 아이템 x에 대해 점수값을 return하는 함수 f(x)를 학습하겠다는 것이다.
물론 이 함수 또한, return 값이 주어진 pair들과 최대한 많이 일치해야 한다. 일치한다는 의미는, si가 xi > xi' 라면 f(xi) > f(xi') 여야 한다는 것이다.

주석 보기


따라서 우리가 풀고자 하는 최종 문제는 다음과 같이 정리된다:

다음 조건을 최대한 많은 si = (xi, xi', yi) 들에 대해 만족하는 함수 f를 구한다:
1. yi>인 경우: f(xi) > f(xi')
2. yi<인 경우:
f(xi) < f(xi')

이러한 함수를 구하는 방법은 물론 여러 가지가 있다. underlying function을 바탕으로 classficiation을 수행하는 방법이라면 무엇이든 이 문제를 푸는 데에 쓰일 수 있다. 다음 글에서는 대표적인 방법을 몇 가지 소개하겠다.

------
2007년 10월 19일 작성
2007년 11월 28일 최종 수정 - (주1) 추가
신고
1 ··· 4 5 6 7 8 9 10 11 12 ··· 15 
분류 전체보기 (15)
기계학습 프로그래밍 (14)
연구 (1)
리뷰 (0)

티스토리 툴바