[BoostCamp] DAY22 Graph#2
[BoostCamp] DAY22 Graph#2
1. 그래프를 이용한 기계학습
1. 검색엔진에서는 그래프를 어떻게 활용할까?
1.1 페이지 랭크의 배경
웹과 그래프
- 웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성있는 그래프이다.
- 웹페이지는 정점에 해당한다.
- 웹페이지가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당한다.
- 단 웹페이지는 추가적으로 키워드 정보를 가지고 있다.
구글 이전의 검색 엔진
- 웹을 거대한 디렉토리구조로 정리하자.
- 웹페이지 수가 증가함에 따라 카테고리의 수와 깊이도 무한정 커지는 문제가 발생
- 카테고리 구분이 모호하여 저장과 검색에 어려움이 有
- 웹페이지에 포함된 키워드에 의존한 검색 엔진
- 사용자가 입력한 키워드에 대해 해당 키워드를 (여러 번)포함한 웹페이지를 반환
- 악의적 페이지에 취약하다는 단점이 존재.
- 성인 사이트에 축구라는 키워드를 여러번 포함하면 해당 웹페이지도 결과로 나올 가능성 존재
그렇다면 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 어떻게 찾을 수 있을까
페이지 랭크에 대해 알아보자.
1.2 페이지 랭크의 정의
페이지 랭크의 정의 : 투표 관점
- 페이지 랭크의 핵심아이디어는 투표이다.
- 즉, 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 탐색한다.
- 투표의 주체는 웹페이지 이다.
- 웹페이지는 하이퍼링크를 통해 투표를 한다.
-
- 여기서 사용자 키워드를 포함한 웹페이지를 고려해보자.
- 웹페이지 home이 about me로의 하이퍼링크를 포함한다면,
- home의 작성자가 판단하기에 about me가 관련성이 높고 신뢰할 수 있는 것을 의미한다.
- 즉, home이 about me에게 투표했다고 생각할 수 있다.
- 즉 들어오는 간선이 많을 수록 신뢰할 수 있다는 의미이다.
- 그런데 들어오는 간선의 수를 세는 것은 괜찮을까?
- Nope!!!!!! 악용될 소지가 존재한다.
- 웹페이지를 여러개 만들어서 간선의 수를 부풀릴 수 있다.
- Solution??
- 페이지랭크에서는 이를 방지하기 위해 가중 투표를 한다.
- 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주한다.
- 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법이다.
[DO IT!!!]
- 측정하려는 웹페이지의 관련성 및 신뢰도를 페이지 랭크 점수라고 하자.
- 페이지 랭크 점수는 어떻게 계산하나??
페이지 랭크의 정의 : 임의 보행 관점
- 페이지 랭크는 임의 보행(random walk)의 관점에서도 정의할 수 있다.
- 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정하자.
- 즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼 링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서힝한다.
- 자 그럼, 웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 학률을 Pi(t)라고 하자
- P(t)는 길이가 웹페이지 수와 같은 확률 분포 벡터가 된다.
- t가 무한히 커지면, P(t) = P(t + 1) = P가 성립한다.
- 수렴한 확률 분포 P는 정상분포라고 한다. 그러면 위의 공식을 아래와 같이 변환 할 수 있다.
- 해당 수식을 보면 위의 투표관점에서의 페이지 랭크 계산식과 유사하다는 것을 알 수 있다.
1.3 페이지 랭크의 계산
페이지 랭크의 계산 : 반복곱
- 페이지랭크 점수의 계산에는 반복 곱을 사용한다.
- 각 웹 페이지 i의 페이지 랭크점수 를 통일하게 1/(웹페이지의 수)로 초기화한다.
- 아래 식을 이용하여 각 웹페이지의 페이지 랭크 점수를 갱신한다.
- 페이지 랭크 점수가 수렴하였으면 종료하고 아니면 2번으로 돌아가 연산한다.
문제점과 해결법
- Problem
- 반복곱이 항상 수렴하는 것을 보장할 수 있나?
- 반복곱이 합리적인 점수로 수렴하는 것을 보장할 수 있나?
- 반복곱이 항상 수렴하는 것을 보장할 수 있나?
- NOPE!!!
- 들어오는 간선은 있지만 나가는 간선은 없는 정점 집합인 스파이더 트랩에 의한 문제이다.
- 반복곱이 “합리적인” 점수로 수렴하는 것을 보장할 수 있나?
- NOPE!!!
- 들어오는 간선은 있지만 나가는 간선이 없는 막다른 정점에 의한 문제이다.
- SOLUTION
- 순간이동 도입
- 임의 보행 관점에서, 웹을 서피하는 웹서퍼의 행동을 아래와 같이 수정한다.
- 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동한다.
- 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 a인 동전을 던진다.
- 앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택해서 클릭한다.
- 뒷면이라면 임의의 웹페이지로 순간이동한다.
- 1과 4의 임의의 웹페이지는 전체 웹페이지들 중에 하나를 균일 확률로 선택한다.
- 순간이동에 의해 스파이더 트랩이나 막다른 정점에 갇히는 일도 없어졌다.
- a를 감폭비율이라고 부르며 값으로 보통 0.8을 사용한다.
- 임의 보행 관점에서, 웹을 서피하는 웹서퍼의 행동을 아래와 같이 수정한다.
- 순간이동 도입에 의해 변화된 페이지 랭크 점수계산.
- 막다른 정점에서 (자신을 포함) 모든 다른 정점으로 가는 간선을 추가한다.
- 아래 수식을 이용하여 반복곱을 수행한다.
- 순간이동 도입
2. 그래프를 바이럴 마케팅에 어떻게 활용할까?
2.1 그래프를 통한 전파의 예시
전파과정은 다양할 뿐 아니라 매우 복잡하다.
이를 체계적으로 이해하고 대처하기 위해서는 수학적 모형화가 필요하다.
그래프를 통한 정보의 전파
- 온라인 소셜 네트워크를 통해 정보가 전파된다.
- 2011년 스페인의 15M에 대한 정보 : 트위터로 퍼짐
- 유용한 과학적 정보가 전파되기도 함
그래프를 통한 행동의 전파
- 온라인 소셜 네트워크를 통해 다양한 행동이 전파된다.
- 아이 버킷 챌린지
- 펭귄 문제
그래프를 통한 고장의 전파
- 컴퓨터 네크워크에서의 일부 장비의 고장이 전파되어 전체네트워크를 마비시킬수 있다.
- 일부 장비의 고장이 다른 장비의 과부화를 초래
- 파워 그리드에서의 정전이 전파되는 과정
그래프를 통한 질병의 전파
- 사회라는 거대한 소셜 네트워크를 통한 질병의 전파도 존재한다.
- 코로나, 메르스, 사스
2.2 의사결정 기반의 전파 모형
언제 의사결정 기반의 전파 모형을 사용할까?
- Presenting the Situtation
- 카카오톡과 라인 중에 어떤 것을 사용하고 있고, 왜 그런 선택을 했는가?
- 이러한 경우들은 모두 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다.
- 이렇듯 주변 사람들의 의사 결정을 고려하여 각자 의사결정를 내리는 경우에 의사 결정 기반의 전파모형을 사용한다
선형 임계치 모형
-
가장 간단한 형태의 의사 결정 기반의 전파 모형이다.
- 친구 관계의 두사람 u와 v를 가정하자.
- 둘은 두개의 호환되지 않는 기술 A와 B중에서 하나를 선택한다.
- 둘 모두 A기술을 사용할 경우, 행복이 a만큼 증가한다.
- 둘 모두 B기술을 사용할 경우, 행복이 b만큼 증가한다.
-
but 둘이 서로 다른 기술을 사용할 경우, 행복이 증가하지 않는다.
- 이를 소셜 네트워크에서 생각을 해보자.
- 우리는 동시에 여러 사람과 친구 관계를 맺는 다.
- 각각의 친구, 즉 소셜 네트위크 상의 이웃과의 사이에서 발생하는 행복을 고려해야한다.
- p 비율의 이웃이 A를 선택하였다.
- 1 - p 비율의 이웃이 B를 선택하였다.
- 언제 A를 선택할까? ap > b(1 - p)일때이다.
- 즉, p > b /(a + b)일때 A를 선택한다.
- 이제 우리는 b/(a+b)를 임계치 q라고 하자.
- 이러한 모형을 선형 임계치 모형이라고 한다.
- 각 정점은 이웃 중 A를 선택한 비율이 임계치 q를 넘을 때만 A를 선택한다.
- 전부 B를 사용하는 상황을 가정하자.
- 처음 A를 사용하는 얼리어 답터를 가정하자.
- Seed Set이라고 불리는 얼리 어답터들은 항상 A를 고수하자.
2.3 확률적 전파 모형
언제 확률적 전파 모형을 사용할 까?
- Presenting the Situtation
- 코로나의 전파 과정을 수학적으로 추상화해보자.
- 의사결정 기반 모형은 적합하지 않다.
- WHY?
- 누구도 코로나에 걸리기로 의사 결정을 내리는 사람은 없기 때문이다.
- 따라서 코로나의 전파는 확률적 과정이기 때문에 확률적 전파 모형을 고려해야한다.
독립적 전파 모형
-
독립적 전파 모형은 가장 간단한 형태의 확률적 전파 모형이다.
- 방향성이 있고 가중치가 있는 그래프를 가정하자.
- 각 간선(u, v)의 가중치는 Puv는 u가 감염됐을때, 그리고 v가 감염되지 않았을 때
- u가 v를 감염시킬 확률에 해당한다.
- 즉, 각 정점 u가 감염될 때마다, 각 이웃 v는 Puv확률로 전염된다.
-
서로 다른 이웃이 전염되는 확률은 독립적이다.
- Simulation
- 모형은 최초 감염자들(Seed Set)로부터 시작된다.
- 각 최초의 감염자 u는 각 이웃 v에게 Puv의 확률로 병을 전파한다.
- 위과정을 새로운 감염자 각각에게 반복한다.
- 더이상 새로운 감염자가 없을 때까지 반복한다.
- 해당 모형에서는 감염자는 계속 감염자 상태로 남아 있는 것을 가정한다.
- 감염자의 회복을 가정하는 SIS, SIR등의 다른 전파 모형도 존재한다.
2.4 바이럴 마케팅과 전파 최대화 문제
바이럴 마케팅이란?
- 바이럴 마케팅은 소비자들로 하여금 상품에 대한 긍정적인 입소문을 내게 하는 기법이다.
- 바이럴 마케팅이 효과적이기 위해서는 소문의 시작점이 중요하다.
- 시작점이 어디인지 따라서 입소문이 전파되는 범위가 영향을 받기 때문이다.
시드 집합의 중요성
- ex) 미들턴 효과
- 앞서 소개한 전파 모형들에서도 시드 집합이 전파 크기에 많은 영향을 미친다.
전파 최대화 문제
- 시드 집합을 선택할 수 있다면, 어떻게 선택할 것인가?
- 그래프, 전파 모형 드리고 시드 집합의 크기가 주어졌을 때
- 전파를 최대화하는 시드 집합을 찾는 문제를
- 전파 최대화 문제라고 한다.
-
전파 모형으로는 앞서 배운 선형 임계치 모형, 독립 전파 모형을 포함하여 다양한 모형을 고려할 수 있다.
- 전파 최대화 문제는 매우 어려운 문제이다.
- 그래프에 |V|개의 정점이 있는 경우, 시드 집합의 크기를 k개로 제한 하더라도 |V|Ck개이다.
- 이론적으로 많은 전파 모형에 대하여 전파 최대화 문제는 NP-hard임이 증명되었다.
- 최고의 시드 집합을 찾는 것은 포기하자.
정점 중심성 휴리스틱
- 대표적 휴리스틱으로 정점의 중심성을 사용한다.
- 즉, 시드 집합의 크기가 k개로 고정되었을때, 정점의 중심성이 높은 순으로 k개 정점을 선택하는 방법이다.
- 정점의 중심성으로는 페이지 랭크 점수, 연결 중심성, 근접 중심성, 매개 중심성 등이 있다.
- 합리적이지만, 최고의 시드 집합을 찾는 다는 보장은 없다.
탐욕 알고리즘
- 탐욕 알고리즘은 시드 집합의 원소, 즉 최초 전파자를 한번에 한 명씩 선택한다.
- 집합을 비교하여 전파를 최대화하는 시드 집합을 찾는다.
- 이때 전파의 크기를 비교하기 위해 시뮬레이션을 반복하여 평균값을 사용한다.
- 이때 뽑힌 집합을 X라고 하자.
- X를 포함한 집합을 비교하여 전파를 최대화 하는 시드 집합을 찾는다.
- 이때 뽑힌 집합을 {X, Y}라고 하자.
- 이러한 과정을 목표하는 크기의 시드 집합에 도달할 때까지 반복한다.
- 집합을 비교하여 전파를 최대화하는 시드 집합을 찾는다.
- 최초 전파자간의 조합의 효과를 고려하지 않고 근시안적으로 최고 전파자를 선택하는 과정을 반복한다.
탐욕알고리즘은 얼마나 정확한가요?
- 독립 전파 모형의 경우, 이론적으로 정확도가 일부 보장된다.
- 즉, 항상 입력 그래프와 무관하게 아래의 부등식이 성립한다.
- 따라서 탐욕 알고리즘의 최저 성능은 수학적으로 보장되어 있다.
3. 추가 질문을 해보아요.
- 코로나와같은 질병의 확산을 위에서는 확률적 전파 모형을 사용하하여 표현을 하였다.
- 그리고 질병을 회복하는 것을 가정하는 전파 모형에는 SIS, SIR등이 있다고 하였다.
- 그렇다면 SIS, SIR이 무엇인지 알아보고, 질병을 회복한 사람은 다시 질병에 걸리지 않는 다는 전제를 만족하는 모델이 있는지 탐색해 보자.
댓글남기기