3강. 그래프를 이용한 기계 학습 - 검색 엔진에서는 그래프를 어떻게 활용할까?

1. 페이지 랭크 알고리즘의 탄생 배경

(1) 웹과 그래프

웹 = 웹페이지 + 하이퍼링크

웹은 거대한 방향성이 있는 그래프이다. 웹페이지는 정점, 웹페이지가 포함하고 있는 하이퍼링크는 해당 웹페이지에서 나가는, 방향성이 있는 간선에 해당한다. 이때, 웹페이지는 추가적으로 키워드 정보를 포함하고 있다.

(2) 구글 이전의 검색 엔진

구글 이전의 검색 엔진 시도는 크게 두 가지로 나눌 수 있다. 첫 번째 시도는 웹을 거대한 디렉토리로 정리하는 것이다. 특히 이는 옛날에 YAHOO!에서 카테고리 정리 방식으로 활용했는데, 웹페이지의 수가 증가함에 따라 카테고리의 수와 깊이가 무한정 커진다는 문제가 있었다. 또한 카테고리의 구분이 모호하기 때문에 저장 및 탐색에도 문제가 있었다. 현재는 수십억~수백억 개의 웹페이지가 있다고 한다.

두 번째 시도는 웹페이지에 포함된 키워드에 의존한 검색 엔진을 활용하는 것이다. 즉, 수많은 웹페이지 중에서 우리가 찾고자 하는 웹페이지를 검색 엔진을 통해 찾는 것이다. 이는 사용자가 키워드를 입력했을 때, 이 키워드를 여러 번 포함한 웹페이지를 반환하는 형태로 이루어진다. 다만 검색 엔진 활용 방식은 악의적인 웹페이지에 취약하다는 문제점이 있다.

이러한 문제점을 해결하고, 사용자가 입력한 키워드와 관련성이 높으면서도 신뢰할 수 있는 웹페이지를 찾는 방법이 바로 페이지 랭크이다.

2. 페이지 랭크의 정의

(1) 투표 관점에서의 페이지 랭크

투표 관점의 페이지 랭크에서의 핵심 아이디어는 투표이다. 즉, 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾는 것이다. 투표의 주체는 웹페이지이며, 웹페이지는 하이퍼링크를 통해 투표를 진행한다.

예를 들어 웹페이지 u가 v로의 하이퍼링크를 포함하고 있다고 가정하자. 이때 웹페이지 u의 작성자는 v를 관련성이 높고, 신뢰할 수 있다고 간주할 것이다. 이를 통해 u가 v에 투표했다고 생각할 수 있다.

따라서 들어오는 간선이 많을수록 신뢰도가 높아질 수 있다고 해석할 수 있다. 다만, 들어오는 간선의 수를 세는 것만으로 신뢰도를 측정할 수 있는 것은 아니다. 웹페이지를 여러 개 만들어서 간선의 수를 부풀린 뒤, 관련성과 신뢰도가 높아 보이도록 조작을 할 수 있기 때문이다. 따라서 인위적으로 만들어진 웹페이지에 대해 의심을 가질 필요가 있다.

이러한 악용은 온라인 소셜 네트워크에서도 찾을 수 있다. 우리는 흔히 돈을 주고 팔로워를 구매할 수 있는데, 이렇게 돈을 주고 팔로워를 구매하면 들어오는 간선의 수가 증가하여 온라인 소셜 네트워크 속에서 본인의 영향력을 과장할 수 있게 된다.

그렇기 때문에 이러한 악용을 막기 위해 가중 투표를 진행한다. 이는 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주한다는 의미이다. 이는 악용이 있을 때와 없을 때 모두 사용할 수 있는 합리적인 투표 방법으로 제시된다. 다만 관련성과 신뢰성은 투표를 통해 측정하고자 했던 것으로, 순환 이론에 빠질 수 있으나 연립방정식 풀이, 즉 재귀Recursion를 통해 해결할 수 있다.

페이지 랭크 점수에 대해 조금 더 알아보도록 하겠다. 우리가 측정하려는 웹페이지의 관련성과 신뢰도를 페이지 랭크 점수라고 부를 때, 웹페이지들은 각각의 나가는 이웃에게 [자신의 페이지 랭크 점수/나가는 이웃의 수] 만큼의 가중치로 투표를 진행하게 된다. 페이지 랭크 점수는 해당 웹페이지에 들어오는 가중치를 모두 더해주면 된다. 페이지 랭크 점수는 j에 들어오는 이웃들이 보내는 투표의 가중치를 통해, [i의 페이지 랭크/i의 나가는 연결성] 으로 정의할 수 있다. 식은 다음과 같다.

(2) 임의 보행Random Walk 관점에서의 페이지 랭크

임의 보행의 관점에서는 웹을 서핑하는 웹서퍼를 가정한다. 이 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹서핑을 진행한다. 웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 확률을 pi(t)라고 할 때, p(t)는 길이가 웹페이지 수와 같은 확률분포 벡터가 된다. p(t)의 길이는 정점의 수 |v|와 같으며, i번째 원소를 다시 pi(t)라고 할 수 있다. t+1번째로 방문한 웹페이지가 웹페이지 j일 확률은, t번째로 방문한 웹페이지 j에 들어오는 i의 확률을 i에서 j로 나가는확률로 나눈 것과 같으며 이는 t번째에 웹페이지 i에 있다가 t+1번째에 웹페이지 j에 오는 확률과 같다.

웹서퍼가 이러한 과정을 무한히 반복하여 t가 무한히 커지면 확률 분포는 p(t)에 수렴하게 된다. 즉,p(t)=p(t+1)=p이며 이때 확률 분포 p를 정상 분포Stationary Distribution라고 부른다. 식은 다음과 같이 나타낼 수 있으며, r 대신 p 로테이션을 사용했을 뿐 식 자체는 투표 관점에서 정의한 것과 동일하다.

3. 페이지 랭크의 계산

(1) 반복곱Power Iteration

페이지 랭크 점수 계산에서 반복곱을 활용할 수 있다. 반복곱은 다음 세 가지 단계로 구성된다. 먼저, 각 웹페이지 i의 페이지 랭크 점수 ri(0)을 동일하게 [1/웹페이지의 수] 로 초기화한다. 그리고 페이지 랭크의 정의를 통해 각 웹페이지의 페이지 랭크 점수를 갱신한다. 마지막으로 페이지 랭크 점수가 수렴한 경우, 즉 r(t)=r(t+1)이 될 경우에는 r(t+1) 값을 페이지 랭크의 아웃풋으로 낸다. 페이지 랭크 점수가 수렴하지 않는 경우는 두 번째 단계를 페이지 랭크 점수가 수렴할 때까지 반복한다.

(2) 반복곱의 문제점

반복곱은 어떤 예시에서는 잘 작동하지만, 다른 예시에서는 잘 작동하지 않는다. 따라서 반복곱이 항상 수렴하지는 않는다는 것, 그리고 반복곱이 항상 ‘합리적인’ 점수로 수렴하는 것은 아니라는 것에 대한 문제점이 나타난다.

반복곱이 항상 수렴하지는 않는 경우는 한 가지, 스파이더 트랩Spider Trap 때문이다. 스파이더 트랩은 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합을 의미한다. 이 때는 짝수 번째 이터레이션 벡터와 홀수 번째 이터레이션 벡터만 구분 가능하고 짝수 번째 이터레이션 벡터들, 홀수 번째 이터레이션 벡터들은 각각 동일한데, 번갈아 가면서 나오기 때문에 한 값에 수렴하는 형태는 띄지 않는다.

반복곱이 항상 ‘합리적인’ 점수로 수렴하는 것은 아니라는 것에 대한 문제점은 바로 막다른 정점Dead End 때문이다. 막다른 정점은, 들어오는 간선은 있지만 나가는 간선이 없기에 나타나는 현상이다.

(3) 반복곱의 해결책

위에 나타난 두 가지 문제를 해결하기 위해 순간이동Teleport을 도입한다. 임의 보행의 관점에서 웹서퍼의 행동을 다음과 같이 수정할 수 있다. 먼저 현재 웹페이지에 하이퍼링크가 없을 경우에는 임의의 웹페이지로 순간이동한다. 현재 웹페이지에 하이퍼링크가 있을 경우에는 앞면이 나올 확률이 a인 동전을 던진다. 이 동전이 앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택하여 클릭하고, 이 동전이 뒷면이라면 임의의 웹페이지로 순간이동한다.

이 순간이동 방식을 통해서 위에서 문제점으로 지적되었던 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어져 이 두 문제를 해결할 수 있게 되었다. 이때 a를 감폭 비율Damping Factor이라고 부르며, 보통 0.8의 값을 활용한다.

순간이동의 도입을 통해 바뀐 페이지 랭크 점수 계산 방식은 다음과 같다. 먼저, 각각의 막다른 정점에서 자신을 포함하여 다른 정점으로 가는 간선들을 추가한다. 그 이후에, 이전에 나온 수식에 확률 a를 곱하고 그 나머지 확률을 [1/|v|] 에 곱한 값을 더한 수식을 활용하여 페이지 랭크 점수를 계산한다. 이때 |v|는 전체 웹페이지의 수를 의미한다.

수정된 페이지 랭크 점수의 예시를 보면 다음과 같다. 각 정점의 크기는 그 정점의 페이지 랭크 점수에 비례하는 크기를 지니며 정점 내부에 써있는 숫자는 페이지 랭크 점수에 100을 곱한 수이다. 이 숫자가 큰 이유는 많은 정점에서 투표를 하거나, 간선이 적은 경우에도 숫자가 큰 이유는(c) 높은 페이지 랭크(b)가 오직 한 곳(c)으로만 간선을 가지고 있고 이 높은 페이지 랭크(b)를 모두 한 곳(c)으로만 보내므로 한 표밖에 받지 못했을지라도 신뢰도가 높은 곳(b)으로부터 받았기 때문에 페이지 랭크 값이 높을 수 있다. 그 밖에 페이지 랭크 점수가 낮은 이유는 정점에서 투표를 거의 하지 않았기 때문이며, 점수가 0이 아닌 다른 수로 나온 이유는 순간이동을 통해 다른 곳에서 이동해 온 것이 있기 때문이다.

3강 - 페이지 랭크

3강. 그래프를 이용한 기계 학습 - 검색 엔진에서는 그래프를 어떻게 활용할까?

1. 페이지 랭크 알고리즘의 탄생 배경

2. 페이지 랭크의 정의

3. 페이지 랭크의 계산