해당 포스팅은 네이버 부스트캠프 AI Tech 학습 정리 자료임을 알려드립니다.
1. 강의 정리
신기정 교수님 - 검색 엔진에서는 그래프를 어떻게 활용할까?
페이지 랭크의 배경
1) 웹과 그래프
웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성이 있는 그래프입니다. 여기서 정점은 웹페이지가 되고, 웹페이지가 포함하고 있는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당합니다. 단, 웹페이지는 추가적으로 키워드 정보를 포함하고 있습니다.
2) 구글 이전의 검색 엔진
구글 이전의 검색 엔진들은 어떻게 검색이 되도록 노력했을까요? 첫 번째 시도는 웹을 거대한 디렉토리로 정리하는 것이었습니다. 하지만, 이 방법은 웹페이지의 수가 증가함에 따라 카테고리의 수와 깊이가 무한정 커지는 문제가 있습니다. 또한 카테고리 구분이 모호한 경우가 많이 있어, 저장과 검색에 어려움이 있습니다. 두 번째 시도는 웹페이지에 포함된 키워드에 의존한 검색 엔진입니다. 이 방법은 사용자가 입력한 키워드에 대해 여러 번 포함된 웹페이지를 반환합니다. 이러한 방법은 악의적인 웹페이지에 취약하다는 단점이 있습니다. 예를 들어, 성인 사이트에 '축구'라는 키워드를 보이지 않도록 여러 번 포함하게 되면, '축구' 키워드로 검색했을 때, 해당 사이트가 나올 수 있습니다.
페이지 랭크의 정의
1) 투표 관점
페이지 랭크의 핵심 아이디어는 투표입니다. 투표를 통해서 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾습니다. 투표는 웹페이지(정점)이 하게 되고, 하이퍼링크(간선)을 통해 투표합니다. 웹페이지 A에서 B로의 하이퍼링크를 포함하고 있다면 A의 작성자가 판단하기에 B가 관련성이 높고 신뢰할 수 있다는 것을 의미합니다. 즉, 들어오는 간선이 많을 수록 신뢰할 수 있다는 뜻입니다. 하지만, 들어오는 간선의 수를 세는 것으로 앞에서의 문제를 해결할 수는 없습니다. 왜냐하면 웹페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있습니다. 즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있습니다. '청춘기록' 드라마에서 배우 변우석의 엄마가 연기자인 아들의 SNS 계정 팔로워수를 늘리기 위해 조작하는 행위를 하는 것과 같은 맥락이라고 이해하시면 될 것 같습니다. 이러한 문제를 해결하기 위해서는 페이지 랭크에 가중 투표를 하도록 합니다. 즉, 모든 웹사이트의 간선이 동일한 의미를 갖는 것이 아닌, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 생각하는 방법입니다.
측정하려고 하는 웹페이지의 관련성 및 신뢰도를 페이지 랭크 점수라고 하면, 각 웹페이지는 나가는 이웃에게 자신의 페이지 랭크 점수를 나가는 이웃의 수 만큼 나눠서 가중치로 투표를 합니다. 그렇게 받은 가중치들의 합이 그 해당 웹페이지의 페이지 랭크 점수가 됩니다. 위의 그림처럼 계산할 수 있습니다. 이렇게 구해진 정점 별 페이지랭크를 식으로 표현해서 연립방정식으로 계산할 수 있습니다.
2) 임의 보행 관점
페이지랭크는 임의 보행의 관점에서도 정의할 수 있습니다. 이 방법은 쉽게 말하면, 임의로 전체 웹페이지 중에서 하나를 클릭하는 방식으로 이동합니다. 웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 확률을 $p_{i}(t)$라고 합시다. 그러면 $p(t)$는 길이가 웹페이지 수와 같은 확률분포 벡터가 됩니다. 이를 아래의 식으로 표현할 수 있으며, 우측의 식도 성립합니다.
$$ p(t) = [p_{1}(t), p_{2}(t) ... , p_{|v|}(t)], \, p_{j} = \sum_{i \in N_{in}(j)} \frac{p_{i}(t)}{d_{out}(i)} $$
웹서퍼가 이 과정을 무한히 반복하고 나면, 즉 t가 무한히 커지면 확률 분포 $p(t)$는 수렴하게 됩니다. 다시 말해서 $p(t)$ = $p(t+1)$ = $p$가 성립하게 됩니다. 수렴한 확률 분포 $p$는 정상 분포(Stationary Distribution)이라고 부릅니다. 그래서 위에서 소개한 식이 $t$가 무한하게 커지게 되면 아래의 식으로 바꿀 수 있습니다.
$$ p_{j} = \sum_{i \in N_{in}(j)} \frac{p_{i}}{d_{out}(i)} $$
이 식은 투표 관점에서 정의한 페이지랭크 점수와 동일한 정상 분포인 것을 확인할 수 있습니다.
페이지랭크의 계산
페이지랭크 점수의 계산에는 반복곱(Power Iteration)을 사용합니다. 반복곱은 세 단계로 구성 됩니다. 가장 먼저 각 웹페이지 i의 페이지 랭크 점수 $r_{i}^{(0)}$를 동일하게 웹페이지의 수로 나눠서 초기화합니다. 그리고 아래의 식을 이용해서 각 웹페이지의 페이지랭크 점수를 갱신합니다.
$$r_{j}^{(t+1)} = \sum_{i \in N_{in}(j)} \frac{r_{i}^{(t)}}{d_{out}(i)} $$
마지막으로 페이지랭크 점수가 수렴하였으면 종료합니다. 아닌 경우에는 위에 식으로 갱신을 반복합니다. 여기서 수렴한다는 것의 의미는 $r^{(t)} \approx r^{(t+1)}$를 만족하는 것입니다. 아래의 그림은 $t$값이 증가함에 따라 어떤식으로 계산이 되는 지에 대한 간략한 그림입니다.
하지만, 반복곱이 항상 수렴하는 것을 보장하지는 않습니다. 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합인 스파이더 트랩(Spider Trap)에 의한 문제가 발생합니다. 또한 반복곱은 합리적인 점수로 수렴하는 것을 보장하지 않는다는 문제가 있습니다. 들어오는 간선은 있지만 나가는 간선은 없는 막다른 정점(Dead End)에 의해서 발생하는 문제입니다. 한쪽에서는 주기만 하고 한쪽은 받기만 한다면, 둘의 페이지랭크는 0으로 수렴하게 됩니다. 이는 좋은 방법이 아닐 것 입니다. 둘다 의미없는 페이지가 되어버렸으니까요. 그래서 이 문제를 해결하기 위해 순간이동(Teleport)를 도입합니다.
임의 보행 관점에서, 웹을 서핑하는 웹서퍼의 행동을 새롭게 규정하게 됩니다. 첫 번째, 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동 합니다. 이는 막다른 정점에서 빠져나오기 위한 대책이 됩니다. 두 번째, 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 $\alpha$인 동전을 던집니다. 만약, 앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭합니다. 만약 뒷면이라면, 임의의 웹페이지로 순간이동 합니다. 순간이동에 의해서 스파이더 트랩이나 막다른 정점에 갇히는 일을 막을 수 있습니다. 또한 위에서 언급한 $\alpha$는 감폭 비율(Dampling Factor)라고 부르며, 보통 0.8의 값을 사용하는 것이 일반적입니다.
이렇게 순간이동의 도입으로 페이지랭크 점수 계산이 변경됩니다. 첫 번째, 막다른 정점에서 자신을 포함해서 모든 정점으로 가는 간선을 추가합니다. 그리고 아래 수식을 이용해서 반복곱을 수행합니다.
$$ r_{j} = \sum_{i \in N_{in}(j)} \alpha \frac{r_{i}^{(t)}}{d_{out}(i)} + (1-\alpha)\frac{1}{|V|}$$
여기서 $|V|$는 전체 웹페이지의 수를 의미하고, 앞의 항은 하이퍼링크를 따라 정점 $j$에 도착할 확률을 의미하고, 뒤의 항은 순간이동을 통해 정점 $j$에 도착할 확률을 의미합니다.
신기정 교수님 - 그래프를 바이럴 마케팅에 어떻게 활용할까?
1) 그래프를 통한 전파의 예시
온라인 소셜 네트워크를 통해 다양한 정보가 전파됩니다. 2011년 스페인의 15M 운동에 대한 정보는 트위터를 통해 전국적으로 알려졌습니다. 덕분에 주류 언론이 침묵하는 상황에서도 시민들이 정부의 부정부패에 맞서 연대할 수 있었습니다. 또한 이외에도 캐글코리아나 텐서플로우 코리아로부터 유용한 정보들이 전파되기도 합니다. 정보 외에도 온라인 소셜 네트워크를 통해 아이스 버킷 챌린지나 펭귄 문제 등 다양한 행동도 전파됩니다. 컴퓨터 네트워크에서는 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수 있습니다. 정전도 이러한 네트워크에 의한 고장이 전파되는 현상에 해당됩니다. 지금 가장 심각한 문제인 코로나-19와 같이 질병의 전파도 빠뜨릴 수 없습니다. 이렇게 다양한 전파가 있으며 매우 복잡한 형태로 구성되어 있습니다. 이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요합니다.
2) 의사결정 기반의 전파 모형
앞에서 말했던 수학적 모형화의 하나로 의사결정 기반의 전파 모형이 있습니다. 지금 글을 읽으시는 분은 카카오톡과 라인 중에서 어떤 것을 사용하시고 계신가요? 대부분의 한국사람들은 카카오톡을 주로 사용하고 있을 것입니다. 왜 그럴까요? 당연하게도 주변의 사람들이 카카오톡을 많이 사용하기 때문이죠. 라인을 사용하시는 분도 마찬가지로 주변사람들이 많이 사용하기 때문에 선택하게 된 것처럼 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미칩니다. 이렇듯 주변 사람들의 의사결정을 고려하여 각자 의사결정을 내리는 경우에 의사결정 기반의 전파 모형을 사용하게 됩니다. 의사결정 기반의 전파 모형 중 가장 간단한 형태의 선형 임계치 모형을 알아봅시다.
만약, 카카오톡과 라인이 있는 데, 친구와 연락하고 싶다면 둘다 동일한 어플을 사용해야 겠지요. 이처럼 이웃과 동일한 것을 사용할 때 연락이 가능하기 때문에 행복이 증가할 수 있습니다. 그래서 선형 임계치 모형은 각 정점은 이웃 중에서 A를 선택한 비율이 임계치 $q$를 넘을 때만 A를 선택하도록 해서 각자 행복이 최대화되는 선택을 하게 됩니다. 이 모형은 전부 B를 사용하는 상황을 가정합니다. 그리고 처음 A를 사용하는 얼리 어답터들을 가정하고 얼리 어답터들(시드 집합)은 항상 A를 고수한다고 가정합니다.
$p$ 비율의 이웃이 카카오톡을 선택했다고 해봅시다. 그렇다면 1-$p$ 비율의 이웃이 라인을 선택하게 되겠죠. 그렇다면 언제 카카오톡을 선택하게 될까요? $ap > b(1-p)$일 때, 카카오톡을 선택하게 되겠죠. 정리해보면, $p > \frac{b}{a+b}$일 때, 카카오톡을 선택하게 되며, 편의상 $\frac{b}{a+b}$를 임계치 $q$라고 하게 됩니다.
임계치가 55%라고 가정하고 한 가지 아래의 예시를 보고자 합니다.
최초 얼리어답터인 u, v에게 카카오톡을 쓰게 설정하고 나머지는 라인을 쓰게 했습니다. 그 후 1회 전파하게 되면, 총 4명이 u, v에 의해 임계점 55%를 넘어서 카카오톡을 쓰게 됩니다. 2회 전파에서는 v와 새롭게 전파 받았던 1명이 다른 한명을 꼬시게 됩니다. 이후로도 계속 한 명씩 증가하게 되어 마지막 그림은 2명 빼고 모두 동일한 제품으로 전파되는 모습을 볼 수 있습니다.
3) 확률적 전파 모형
코로나의 전파 과정을 수학적으로 생각해보면, 의사결정 기반 모형은 적합하지 않습니다. 그 이유는 당연하게도 코로나를 걸리겠다는 의사결정을 내리는 사람은 없기 때문입니다. 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야 합니다. 여기서 설명하는 확률적 전파 모형은 가장 간단한 형태의 독립 전파 모형(Independent Cascade Model)입니다.
독립적 전파 모형은 기본적으로 방향성이 있고 가중치가 있는 그래프를 가정합니다. 각 간선 $(u, v)$의 가중치 $p_{uv}$는 $u$가 감염되었을 때 $v$가 감염되지 않은 상태에서 $u$가 $v$를 감염시킬 확률에 해당합니다. 즉, 각 정점 $u$가 감염될 때마다, 각 이웃 $v$는 $p_{uv}$ 확률로 전염됩니다. 여기서 서로 다른 이웃이 전염되는 확률은 독립적으로 작용합니다. 독립적 전파 모형도 최초 감염자들(시드 집합)으로부터 시작합니다. 감염자들은 계속 전파해서 더 이상 새로운 감염자가 없으면 종료합니다. 여기서 감염자는 회복한다는 가정은 빠져있는 상태입니다. 이를 반영하는 SIS, SIR 등의 다른 전파 모형도 존재합니다.
4) 바이럴 마케팅과 전파 최대화 문제
바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법입니다. 최근 유튜브에서 많은 뒷광고가 화제가 되었었죠. 왜 많은 기업들은 인플루언서들에게 광고를 요청하는 것일까요? 인플루언서들의 영향력이 굉장히 크기 때문입니다. 그래서 바이럴 마케팅에서는 소문의 시작점이 굉장히 중요합니다. 어디서 시작했는 지에 따라 입소문이 전파되는 범위가 영향을 받기 때문입니다. 이처럼 시드 집합이 굉장히 중요합니다. 그러면 우리는 어떠한 방식으로 시드 집합을 선택할 수 있을까요? 이처럼 그래프, 전파 모형, 그리고 시드 집합의 크기가 주어졌을 때 전파를 최대화하는 시드 집합을 찾는 문제를 전파 최대화(Influence Maximization) 문제라고 부릅니다. 앞에서 배운 선형 임계치 모형, 독립 전파 모형을 포함한 다양한 모형을 고려할 수 있습니다.
하지만, 전파 최대화 문제는 굉장히 어렵습니다. 그래프에 $|V|$개의 정점이 있을 경우, 시드 집합의 크기를 $k$개로 제한하더라도 경우의 수는 $\binom{|V|}{k}$개 입니다. 정점이 만약 10000개이고, 시드 집합의 크기를 10이라고 해도 경우의 수는 엄청 많은 숫자가 됩니다. 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명 되었습니다.
그래서 이 어려운 문제를 어떤식으로 해결할 수 있을까요? 대표적으로 휴리스틱으로 정점의 중심성을 사용하는 방법을 사용할 수 있습니다. 여기서 휴리스틱은 실험적으로는 잘 동작할 수 있지만 이론적으로는 정확도에 대해 보장할 수 없는 알고리즘입니다. 정점의 중심성으로는 페이지랭크 점수, 연결중심성, 근접 중심성, 매개 중심성 등이 있습니다. 연결중심성은 연결성이 높은 정점들이 높은 중심성을 가지는 특성을 활용하는 것이고, 근접 중심성은 다른 정점들로의 평균거리를 측정한 뒤 평균거리가 작은 정점들이 높은 중심성을 가지는 특성을 활용합니다. 매개 중심성은 정점 간 최단 경로를 고려해서 최단 경로에 많이 놓인 정점일수록 높은 중심성을 가집니다.
탐욕 알고리즘 역시 많이 활용됩니다. 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택합니다. 시드 집합을 고정하고 시뮬레이션으로 반복해서 평균 값으로 비교합니다. 그래서 전파 크기가 좋은 집합을 선택하는 방식으로 진행합니다. 1개의 원소가 정해지면 1개를 더 추가해서 똑같은 방식으로 목표하는 크기의 시드 집합에 도달할 때까지 반복해서 최적의 시드 집합을 구합니다. 탐욕 알고리즘은 최초 전파자 간의 조합의 효과를 고려하지 않고 근시안적으로 최초 전파자를 선택하는 과정을 반복합니다. 탐욕 알고리즘은 독립 전파 모형에서는 이론적으로 정확도가 일부 보장됩니다. 항상 입력그래프와 무관하게 탐욕 알고리즘으로 찾은 시드 집합에 의한 전파의 크기는 최고의 시드 집합에 의한 전파의 크기의 63.2%보다 높은 값을 갖고 있어 최저 성능은 보장됩니다.
