1강. 그래프 이론
그래프란 무엇이고, 왜 중요할까?
(1) 그래프의 정의
•
정점 집합과 간선 집합으로 이루어진 수학적 구조이다.
•
하나의 간선은 두 개의 정점을 연결한다.
•
모든 정점의 쌍이 반드시 간선으로 연결되는 것은 아니다.
그래프 = 네트워크 / 정점 = 노드 / 간선 = 엣지 or 링크
(2) 그래프의 중요성
•
우리 주변에는 많은 복잡계가 존재하는데, 그래프를 통해 이를 효과적으로 표현할 수 있다.
•
복잡계를 이해하고 복잡계에 대해서 정확하게 예측을 하기 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요하다.
2강. 그래프 패턴
•
실제 그래프 : 다양한 복잡계로부터 얻어진 그래프를 의미한다.
•
랜덤 그래프 : 확률적 과정을 통해 생성한 그래프이다.
•
에르되시-레니 랜덤 그래프 : 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정된다. ex) G(3,0.3)은 정점이 3개이며 간선 연결 확률이 0.3인 그래프이며, 총 8가지 형태가 나올 수 있다. 각 형태의 확률은 아래와 같다.
3강. 페이지 랭크
페이지 랭크의 정의
(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) 반복곱의 해결책
반복곱에는 스파이더 트랩과 막다른 정점이라는 두 가지 문제점이 나타난다. 이 두 가지 문제를 해결하기 위해 순간이동Teleport을 도입한다. 임의 보행의 관점에서 웹서퍼의 행동을 다음과 같이 수정할 수 있다. 먼저 현재 웹페이지에 하이퍼링크가 없을 경우에는 임의의 웹페이지로 순간이동한다. 현재 웹페이지에 하이퍼링크가 있을 경우에는 앞면이 나올 확률이 a인 동전을 던진다. 이 동전이 앞면이라면 하이퍼링크 중 하나를 균일한 확률로 선택하여 클릭하고, 이 동전이 뒷면이라면 임의의 웹페이지로 순간이동한다.
여기서 잠깐! 스파이더 트랩과 막다른 정점이란?
스파이더 트랩Spider Trap이란 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합을 의미한다. 이에 따라 반복곱이 항상 수렴하지 않는 형태를 띤다.
막다른 정점Dead End이란 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합을 의미한다. 이에 따라 반복곱이 항상 합리적인 점수로 수렴하지는 않게 된다.
이 순간이동 방식을 통해서 위에서 문제점으로 지적되었던 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어져 이 두 문제를 해결할 수 있게 되었다. 이때 a를 감폭 비율Damping Factor이라고 부르며, 보통 0.8의 값을 활용한다.
그리고 순간이동의 도입을 통해 바뀐 페이지 랭크 점수 계산 방식은 다음과 같다. 먼저, 각각의 막다른 정점에서 자신을 포함하여 다른 정점으로 가는 간선들을 추가한다. 그 이후에, 이전에 나온 수식에 확률 a를 곱하고 그 나머지 확률을 [1/|v|] 에 곱한 값을 더한 수식을 활용하여 페이지 랭크 점수를 계산한다. 이때 |v|는 전체 웹페이지의 수를 의미한다.
4강. 전파 모델
의사결정 기반의 전파 모형의 가장 간단한 형태, 선형 임계치 모형(Linear Threshold Model)
u와 v라는 사람이 있다고 가정하자. 이 둘은 두 개의 호환되지 않는 기술 A와 B 중에서 하나를 선택하여 활용한다. 둘 모두 A 기술을 사용할 경우, 각각의 행복이 a만큼 증가한다. 둘 모두 B 기술을 사용할 경우, 각각의 행복이 b만큼 증가한다. 하지만 둘이 서로 다른 기술을 사용할 경우에는 행복이 증가하지 않는다. 이를 모형으로 나타내면 다음과 같다.
이번에는 u가 소셜 네트워크 상에 있다고 가정해보자. u는 동시에 여러 사람과 친구 관계를 맺기 때문에, 소셜 네트워크 상의 이웃과의 사이에서 발생하는 행복을 모두 고려해야 한다. 위의 예시와 마찬가지로 생각해보면, u가 A를 선택할 경우 행복이 2a만큼 증가하고, u가 B를 선택할 경우 행복이 3b만큼 증가한다. 이때, 2a>3b라면 u는 A를 선택할 것이고, 2a<3b라면 u는 B를 선택할 것이다.
이를 일반화하면 임계치 q를 구할 수 있다. 비율 p의 이웃이 A를 선택했다고 가정하고, 비율 (1-p)의 이웃이 B를 선택했다고 가정하면 ap>b(1-p)일 때 A를 선택할 것이다. 이를 p에 대해서 정리하면 p>b/(a+b)이며, 이 b/(a+b)를 임계치 q라고 한다.
이 모형을 선형 임계치 모형이라고 한다. 즉, 각 정점은 이웃 중에서 A를 선택한 비율이 임계치 q를 넘을 때만 A를 선택한다.
그 다음 모형에서는 전부 B를 사용하는 상황을 가정해보자. 처음 A를 사용하는 얼리 어답터들이 존재하며, 시드 집합인 얼리 어답터들은 항상 A를 고수한다. 임계치 q가 55%이고 u와 v가 시드 집합이라면, 처음에는 이웃들 모두가 B를 사용하다가, 이웃 중 A를 선택한 비율이 임계치 55%를 넘는 이웃 4명이 추가적으로 A를 선택한다. 그리고 같은 방법으로 1명의 이웃이, 그리고 또 1명의 이웃이, 마지막으로 또 1명의 이웃이 추가로 A를 선택한다. 이 과정을 거치면 A를 택하지 않은 정점 중에서 이웃 중 A를 선택한 비율이 임계치 55%를 넘지 않는 사람을 제외하고는 모두 A를 선택하는 선형 임계치 모형이 나타난다. 이를 그림으로 나타내면 다음과 같다.
[ u와 v를 제외하고 전부 B를 사용하는 상황 ]
[ 이웃 중 A를 선택한 비율이 임계치를 넘지 않는 사람을 제외하고 모두 A를 선택한 상황]
확률적 전파 모형의 가장 간단한 형태, 독립 전파 모형(Independent Cascade Model)
방향성과 가중치가 모두 있는 그래프를 가정해보자. 해당 그림에서 각 간선 (u, v)의 가중치 Puv는 u가 감염되었을 때, 감염되지 않은 v에게 u가 감염시킬 확률을 의미한다. 즉, 각 정점 u가 감염될 때마다 각 이웃 v는 Puv의 확률로 전염된다. 물론 여기에서 서로 다른 이웃이 전염되는 확률은 독립적으로 시행된다.
모형은 모델의 최초 감염자들로부터 시작한다. 첫 감염자들을 시드 집합이라고 하면, 최초 감염자 u는 각 이웃 v에게 Puv의 확률로 질병을 전파한다. 위의 그림에서는 a가 첫 감염자인 시드 집합이다. 감염자들이 이웃에게 Puv의 확률로 질병을 전파하는 과정을 계속 반복하다가 새로운 감염자가 더 이상 없으면 해당 모형의 반복을 종료한다.
확률적 전파 모형을 통한 질병의 전파 외에도 감염자의 회복을 가정하는 SIS, SIR 등의 전파 모형도 있다.
5강. 군집 탐색
(1) 군집 탐색 문제
•
군집(Community)의 정의 : 집합에 속하는 정점 사이에는 많은 간선이 존재하는 정점들의 집합 and 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재하는 정점들의 집합
•
군집 탐색(Community Detection) : 그래프를 여러 군집으로 ‘잘’ 나누는 문제
•
비지도 기계학습인 클러스터링(Clustering)과 유사
(2) 비교 대상 : 배치 모형
•
배치 모형(Configuration Model) : 각 장점의 연결성(Degree)를 보존한 상태에서 간선들을 무작위로 재배치하여 얻은 그래프
•
두 정점 i와 j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례
(3) 군집성의 정의
•
군집성(Modulartiy) : 군집 탐색의 성공 여부를 판단하는 요소
•
배치 모형과 비교했을 때 그래프에서 군집 내부 간선의 수가 월등히 많을수록(차이가 클수록) 성공적인 군집 탐색
•
즉, 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단
•
항상 -1에서 +1 사이의 값을 가짐
•
0.3~0.7의 값을 가질 시, 통계적으로 유의미한 군집이라고 할 수 있음
군집 탐색 알고리즘
(1) Girvan-Newman 알고리즘
•
대표적인 하향식(Top-Down) 군집 탐색 알고리즘
•
전체 그래프를 먼저 탐색 후 군집들이 분리되도록 간선을 순차적으로 제거
•
서로 다른 군집을 연결하는 다리 역할의 간선들을 제거
•
간선의 매개 중심성(Betweenness Centrality) : 정점 간의 최단 경로에 놓이는 횟수
•
제거 과정
•
군집성이 최대가 되는 시점까지 간선을 제거
•
순서
1) 전체 그래프에서 시작
2) 매개 중심성이 높은 순서로 간선을 제거하면서 군집성의 변화를 기록
3) 군집성이 가장 커지는 상황을 복원
4) 서로 연결된 정점들, 연결 요소를 하나의 군집으로 간주
(2) Louvain 알고리즘
•
대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘
•
개별 정점에서 시작해서 점점 큰 군집을 형성
•
순서
1) 개별 정점으로 구성된 크기 1의 군집으로부터 시작
2) 각 정점 u를 기존 혹은 새로운 군집으로 이동 → 군집성이 최대화되도록 군집을 결정
3) 군집이 더 이상 증가하지 않을 때까지 2)번 반복
4) 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3)번 수행
5) 한 개의 정점이 남을 때까지 4)를 반복
6강. 추천시스템 기초
내용 기반 추천시스템
(1) 내용 기반 추천시스템의 원리
•
각 사용자가 구매/만족했던 상품과 유사한 것
•
과정
•
첫 번째 단계 : 사용자가 선호했던 상품들의 상품 프로필(Item Profile)을 수집하는 단계
◦
상품 프로필이란? 해당 상품의 특성을 나열한 벡터
•
두 번째 단계 : 사용자 프로필(User Profile)을 구성하는 단계
◦
사용자 프로필이란? 선호한 상품의 상품 프로필을 선호도를 사용하여 가중 평균하여 계산
•
세 번째 단계 : 사용자 프로필과 다른 상품들의 상품 프로필 매칭하는 단계
◦
코사인 유사도가 높을수록, 해당 사용자가 과거 선호했던 상품들과 해당 상품이 유사함을 의미
•
마지막 단계 : 사용자에게 상품을 추천하는 단계
(2) 내용 기반 추천시스템의 장단점
장점
•
다른 사용자의 구매 기록이 필요하지 않는다
•
독특한 취향의 사용자에게도 추천이 가능하다
•
새 상품에 대해서도 추천이 가능하다
•
추천의 이유를 제공할 수 있다
단점
•
상품에 대한 부가 정보가 없는 경우에도 사용할 수 없다
•
구매 기록이 없는 사용자에게는 사용할 수 없다
•
과적합(Overfitting)으로 지나치게 협소한 추천을 할 위험이 있다
협업 필터링 추천시스템
(1) 협업 필터링 원리
핵심 아이디어
•
유사한 취향의 사용자를 찾는 것
상관 계수(Correlation Coefficient)
•
상관 계수를 사용해 취향의 유사도를 계산
•
취향의 유사도를 가중치를 사용한 평점의 가중 평균을 통해 평점을 추정
•
추천한 평점이 가장 높은 상품을 추천
(2) 협업 필터링의 장담점
장점
•
상품에 대한 부가 정보가 없는 경우에도 사용할 수 있다
단점
•
충분한 수의 평점 데이터가 누적되어야 효과적이다
•
새 상품, 새로운 사용자에 대한 추천이 불가능하다
•
독특한 취향의 사용자에게 추천이 어렵다
7강. 정점 표현
정점 표현 학습이란?
정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것이다. 이는 간단히 정점 임베딩이라고도 한다. 따라서 정점 표현 학습은 정점들을 벡터로 나타내기 위한 학습을 의미한다. 정점 표현 학습에서 입력은 그래프이고 출력으로 임베딩된 벡터가 나온다.
정점 표현의 목적
그래프에서의 정점간 유사도를 보전하는 방식으로 임베딩을 진행한다.
임베딩 공간내에서의 유사도는 내적을 사용하여 측정한다. 내적은 특성상 같은 방향을 가질수록 큰 값을 가지기 때문에 유사도를 측정할 때 많이 사용한다.
는 정점 v에 대한 임베딩 벡터를 의미하고 는 u에 대한 임베딩 벡터를 의미한다.
정점 표현 학습 접근법
(1) 인접성 기반 접근법
임베딩 공간에서는 내적을 통해 유사도를 측정한다고 했는데 그래프에서는 어떤 것을 기준으로 유사도를 평가할지 정할 필요가 있다. 첫 번째 소개하는 방식은 인접성을 기반으로 하는 방식이다.
위의 사진은 인접 행렬인데 두 정점이 인접하다면 1을 표시하고 인접하지 않다면 0을 표시해서 만든 그래프이다. 이를 토대로 손실 함수를 정의하면 인접 여부에 따라 정점들을 임베딩해줄 수 있다.
이 방식에서 오차는 임베딩된 벡터와 인접 행렬에서 해당하는 값 사이의 차 제곱이라고 설정할 수 있고 모든 정점들 사이의 오차를 합해주면 손실함수가 완성된다. 이 방식은 직관적이고 간편하지만 인접성만으로 유사도를 판단하기 때문에 거리에 대한 고려를 할 수 없다는 단점이 존재한다. 이러한 문제점을 해결하기 위해 다른 방법들이 등장하였다.
(2) 거리 기반 접근법
거리기반 접근법은 두개의 정점사이의 거리가 충분히 가까운 경우 유사하다고 판단한다. 예를 들어 충분한 것의 기준이 2라면 빨간색 정점은 초록색, 파랑색과는 유사하지만 보라색과는 유사하지 않다고 판단한다.
(3) 경로 기반 접근법
경로 기반 접근법에서는 두 정점사이의 경로가 많을수록 유사하다고 판단한다. 따라서 경로의 갯수를 기준으로 학습을 진행한다.
여기서 는 정점 u와 v사이에 있는 경로의 수를 의미한다. 따라서 임베딩은 두 정점사이 경로의 개수와 유사해지는 방향으로 학습이 진행된다.
(4) 중첩 기반 접근법
중첩 기반 접근법은 두 정점이 공유하고 있는 이웃의 수를 기준으로 학습을 진행한다.
위에서 빨간 정점과 파란 정점은 두 개의 이웃을 공유하고 있기 때문에 학습을 진행할때 2라는 숫자를 가지고 손실함수를 계산한다.
(5) 임의 보행기반 접근법
임의 보행기반 접근법은 한 정점에서 출발해서 균일 확률로 이동했을 때 특정 점에 도달할 확률을 구하는 방법이다. 랜덤으로 이동했을 때 그 정점까지 도착할 확률이 높다면 유사도가 높다고 할 수 있고 확률이 낮다면 유사도가 낮다고 할 수 있다.
u, v는 정점, V는 정점들의 집합, 는 임의보행을 했을때 도달한 정점을 원소로 갖는 집합, Zu,Zv는 임베딩된 벡터이다.
손실 함수는 위와 같이 정의를 하는데 첫번째 시그마가 의미하는 것은 모든 정점이 출발점이 된다는 것이고 두번째 시그마가 의미하는 것은 임의 보행을 했을 때 도달한 정점들 만을 학습시킨다는 의미이다.
학습은 소프트맥스 함수와 크로스엔트로피를 사용하고 도달한 정점은 1로 라벨링하고 도달하지 못한 정점은 0으로 라벨링하기 때문에 크로스엔트로피를 사용할때 도달한 정점만을 가지고 학습을 시켜준다.
8강. 추천시스템 심화
넷플릭스 챌린지 소개
넷플릭스 챌린지의 목표는 추천시스템 성능을 10% 이상 향상시키는 것이었다. 구체적으로 당시 넷플릭스 추천시스템의 평균 제곱근 오차는 0.9514였는데, 이를 0.8563까지 낮출 경우 100만 달러의 상금을 받는 조건이었다. 이는 2006년부터 2009년까지 진행되었으며, 2700개의 팀이 참여했고 이 넷플릭스 챌린지는 추천시스템의 성능이 비약적으로 발전하는 계기가 되었다.
잠재 인수 모형
(1) 잠재 인수 모형의 개요
잠재 인수 모형은 가장 큰 성능 개선을 나타냈으며, 지금까지도 널리 사용되고 있는 모형이다. 잠재 인수 모형은 Latent Factor Model, UV decomposition, SVD 등으로 불리며 이 모형의 핵심은 정점 임베딩을 활용하여 사용자와 상품을 벡터로 표현하는 것이다. 하지만 어떤 영화가 얼마나 액션을 포함하고 있는지/로맨스를 담고 있는지, 얼마나 진지한지/가벼운지를 수치상으로 임베딩하기 어려우며 이러한 기준만을 가지고 영화를 표현할 필요도 없다.
잠재 인수 모형에서는 고정된 인수 대신 효과적인 인수를 학습하는 것을 목표로 한다. 즉, 추천을 가장 정확하게 할 수 있는 차원을 찾아서 그 차원으로 구성된 임베딩 공간에 영화와 사람들을 배치하는 것이다. 그때 이 학습한 인수, 임베딩 공간의 축들을 잠재 인수라고 부른다.
(2) 손실 함수
그렇다면 사용자와 상품을 임베딩하는 기준은 무엇일까? 정점 임베딩에서는 그래프에서의 유사도를 임베딩 공간에서도 보존하도록 임베딩했었다. 여기에서는 그래프에서의 영화와 사람의 유사도를 평점을 이용하여 계산한다. 사용자와 상품의 임베딩의 내적이 평점과 최대한 유사하도록 하는 것이다. 사용자 x의 임베딩을 px, 상품 i의 임베딩을 qi라고 할 때, 사용자 x의 상품 i에 대한 평점을 rxi라고 하자. 이때, 임베딩의 목표는 pxqi가 rxi와 유사하도록 하는 것이다.
이를 행렬 차원에서 살펴보자. 사용자 수의 열과 상품 수의 행을 가진 평점 행렬을 R이라고 한다. 그리고 사용자들의 임베딩인 벡터를 쌓아서 만든 사용자 행렬을 P라고 하고, 영화들의 임베딩인 벡터를 쌓아서 만든 상품 행렬을 Q라고 한다. 그렇다면 행렬은 다음과 같이 나타난다.
잠재 인수 모형은 다음 손실 함수를 최소화하는 사용자 임베딩 벡터의 형태 P와 영화 임베딩 벡터의 형태 Q를 찾는 것을 목표로 한다. 그렇기에 손실 함수는 다음과 같이 나타낼 수 있다.
하지만, 위의 손실 함수를 사용할 경우 과적합(Overfitting) 문제가 발생할 수 있다. 과적합이란 기계학습 모형이 훈련 데이터의 잡음인 노이즈까지 학습하여 평가 성능이 오히려 감소하는 현상을 말한다. 이에 과적합을 방지하기 위해서 정규화 항(R2 regularization)을 손실 함수에 더해준다. 즉, 오차 부분 뿐만 아니라 모형 복잡도 부분도 함께 최소화하는 과정이 필요하다. 그리고 모형 복잡도 부분이 최소화된다는 것은 p와 q가 크지 않은 값을 가진다는 것을 의미한다. 이를 통해 손실 함수를 다시 다음과 같이 표현할 수 있다.
(3) 최적화
손실함수를 최소화하는 P와 Q를 찾기 위해서는 경사하강법 및 확률적 경사하강법을 사용한다. 경사하강법은 손실함수를 안정적이지만 느리게 감소시키고, 확률적 경사하강법은 바로 결정을 진행하기 때문에 손실함수를 불안정하지만 빠르게 감소시킨다. 이에 실제로는 확률적 경사하강법이 더 많이 사용된다. 그리고 잠재 인수 모형을 통해 평균 제곱근 오차가 크게 감소한 것을 볼 수 있다. 이를 통해 확률적 경사하강법이 협업 필터링보다 더 성능이 좋음을 알 수 있다.
고급 잠재 인수 모형
(1) 사용자와 상품의 편향을 고려한 잠재 인수 모형
성능 차이를 줄이기 위해서 기본 잠재 인수 모형으로부터 고급 잠재 인수 모형이 도출되었다. 사용자와 상품의 편향을 고려한 잠재 인수 모형에서 각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차이를 통해 나타낸다. 그리고 각 상품의 편향은 해당 상품에 대한 평점 평균과 전체 평점 평균의 차이를 통해 나타낸다.
개선된 잠재 인수 모형에서는 평점을 전체 평균, 사용자 편향, 상품 편향, 상호작용으로 분리한다. 예전에는 상호작용을 통해 평점을 분석하고자 했다면, 현재에는 전체 평균, 사용자 편향, 상품 편향을 활용하여 평점을 분석한 뒤, 상호작용을 통해 차이를 메워 근삿값을 찾는 방식으로 분석한다. 평점 식은 위와 같이 분리하여 표현할 수 있다.
그리고, 개선된 잠재 인수 모형의 손실 함수는 위와 같다. 이 손실 함수는 확률적 경사하강법을 통해 손실 함수를 최소화하는 잠재 인수와 편향을 찾아낸다. 이를 통해 잠재 인수 모형보다 평균 제곱근 오차가 더 작은, 사용자와 상품의 편향을 고려한 잠재 인수 모형을 표현할 수 있게 되었다. 하지만 아직도 목표 오차와의 갭이 존재한다.
(2) 시간적 편향을 고려한 잠재 인수 모형
이 차이를 메우기 위하여 시간적 편향을 고려한 잠재 인수 모형이 개발되었다. 넷플릭스 시스템의 변화로 평균 평점이 크게 증가하는 사건이 있었다. 이는 넷플릭스 인터페이스의 변화나 점수를 매기는 시스템의 변화에 따라 나타날 수 있다. 또한 영화의 평점은 출시일 이후 시간이 지남에 따라 상승하는 경향을 보인다. 평균 평점의 변화는 다음과 같이 나타났다.
개선된 잠재 인수 모형에서는 시간적 편향을 고려하여 사용자 편향과 상품 편향을 시간에 따른 함수로 가정한다. 이와 같은 시간적 편향을 고려한 잠재 인수 모형의 평균 제곱근 오차가 목표 오차에 거의 도달하게 되었다. 여러 모형들을 통해 변화한 평균 제곱근 오차는 다음과 같다.
넷플릭스 챌린지의 결과
앙상블 학습을 사용하여 BellKor 팀이 처음으로 목표 성능 가까이에 도달하였다. 이에 BellKor을 제외한 2~6등의 팀들이 연합하여 Ensemble 팀을 만들었고, 이들 역시 목표 성능에 도달할 수 있었다. 두 팀 모두 오차가 동일했으나, Bellkor 팀의 제출이 20분 빨라 이들이 우승하게 되었다고 한다.
9강. GNN 기초
귀납식 정점 표현 학습
정점 임베딩 자체를 얻는 변환식 방법과는 다르게 정점을 임베딩으로 변환시키는 함수인 인코더를 얻는 방식이다.
변환식 임베딩
장점
•
추가된 정점에 대해서도 임베딩을 얻을 수 있다.
•
모든 정점에 대한 임베딩을 저장하지 않아도 된다.
•
정점이 속성 정보를 가질때도 활용할 수 있다.
단점
•
추가되는 정점에 대해서 임베딩을 얻을 수 없다.
•
모든 정점에 대한 임베딩을 미리 저장해두어야 한다.
•
정점이 속성정보를 가질때 활용할 수 없다.
그래프 신경망의 구조
그래프 신경망은 입력으로 그래프와 정점의 속성 정보를 사용한다. 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 계산 한다. 대상 정점을 임베딩하기 위해 이웃과 그들의 정보를 집계한다. 입력층에는 정점의 속성벡터가 들어가고 이를 통해 이웃들의 임베딩을 계산한다. 최종적으로 이웃들의 임베딩을 통해 대상 정점을 학습한다.
계산 그래프
대상 정점별 집계되는 구조를 계산 그래프라고 한다.
집계함수
층별로 집계함수를 공유하며 위의 그림에서는 네모를 의미한다.
입력값의 갯수가 정점마다 다르기 때문에 평균을 먼저 계산하고 신경망에 적용한다.
는 k번째 층에서 정점v의 임베딩을 의미한다. 위 식을 보면 0번째 층에서 정점 v의 속성 벡터를 사용해서 초기화하는 것을 알 수 있다. 이전 층의 이웃들의 임베딩의 평균에 가중치를 곱하고 자기자신의 임베딩에 가중치를 곱한 값을 더해서 시그모이드 함수를 통과시키는 방식으로 k층의 벡터 v임베딩을 구한다.
출력 임베딩
마지막 층에서의 임베딩이 출력 임베딩이 된다.
학습 변수
학습을 통해 신경망의 가중치를 갱신한다.
손실함수(임베딩)
임베딩 공간에서의 유사도와 실제 그래프에서의 유사도의 차이를 loss로 설정하여 이를 역전파해서 학습을 진행한다.
손실함수(분류)
크로스 엔트로피를 사용하여 End to End 학습을 할 수 있다.
그래프 합성곱 신경망
기존 집계 함수와의 차이점은 자신의 임베딩을 반영할때 다른 이웃들과 같이 합쳐서 가중치를 적용한다는 점과 정규화 할때도 이웃의 임베딩과 자기자신의 임베딩 모두를 활용한다는 점이 있다.
10강. GNN 심화
그래프 신경망에서의 어텐션
(1) 기본 그래프 신경망의 한계
•
기본 그래프 신경망 : 이웃들의 정보를 동일한 가중치로 평균을 내는 신경망이다.
•
그래프 합성곱 신경망 : 단순히 연결성을 고려한 가중치로 평균을 내는 신경망이다.
(2) 그래프 어텐션 신경망
•
그래프 어텐션 신경망(Graph Attention Network, GAT) : 가중치를 자체 학습하는 신경망이다.
•
가중치 학습을 위한 셀프-어텐션(Self-Attention)
•
각 층에서 정점 i로부터 이웃 j로의 가중치 학습 과정
1) 해당 층의 정점 i로부터 임베딩 에 신경망 W를 곱해 새로운 임베딩을 얻는다.
2) 정점 I와 정점 J의 새로운 임베딩을 연결한 후, 어텐션 계수 a를 내적한다. 어텐션 계수 a는 모든 정점이 공유하는 학습 변수를 의미한다.
3) 2번의 결과에 Softmax를 적용한다.
→ 여러개의 어텐션을 동시에 학습한 뒤, 결과를 연결해 사용하는데, 이를 멀티헤드 어텐션(Multi-head Attention)이라고 부른다.
•
어텐션의 결과 정점 분류의 정확도가 향상됨을 확인할 수 있다.
그래프 표현 학습과 그래프 풀링
(1) 그래프 표현 학습 : 그래프 전체를 벡터의 형태로 표현한 것이다.
(2) 그래프 풀링 : 정점 임베딩들로부터 그래프 임베딩을 얻는 과정
지나친 획일화 문제와 대응
(1) 지나친 획일화 문제
•
그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상이다.
•
작은 세상 효과(적은 수의 층으로도 다수의 정점에 의해 영향을 받게 됨)가 나타난다.
•
그래프 신경망의 층의 수를 늘렸을 떄, 후속 과제에서의 정확도가 감소하는 현상이 발견된다.
→ 그래프 신경망의 층이 2개 혹은 3개일 때 정확도가 가장 높음을 알 수 있다.
(2) 지나친 획일화 문제에 대한 대응
•
JK 네트워크(Jumping Knowledge Network) : 마지막 층의 임베딩 뿐만 아니라, 모든 층의 임베딩을 함께 사용한다.
•
APPNP : 0번째 층을 제외하고 신경망 없이 집계 함수를 단순화한다.
→ 층의 수 증가에 따른 정확도 감소 효과가 없는 것을 확인할 수 있다.
그래프 데이터의 증강
•
그래프에서 누락되거나 부정확한 간선의 경우 데이터 증강을 통해 보완할 수 있다.
•
유사도 높은 정점 간의 간선을 추가하는 방법이 제안된다.
•
그래프 데이터 증강의 결과 정점 분류의 정확도가 개선되는 것을 확인할 수 있다.
