[Day 24] 정점 표현 & 추천 시스템 (심화)
[Day 24] 정점 표현 & 추천 시스템 (심화)
1. 강의 복습 내용
1.1) 정점 표현
정점 표현
1. 정점 표현 학습
1.1) 정점 표현 학습이란?
- 그래프의 정점들을 벡터의 형태로 표현하는 것
- 정점 표현 학습은 정점 임베딩(Node Embedding)이라고도 부름
- 정점 임베딩은 벡터 형태의 표현 그 자체를 의미
- 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.
- 정점 표현 학습의 입력은 그래프
- 주어진 그래프의 각 정점 u에 대한 임베딩, 즉 벡터 표현z_{u}가 정점 임베딩의 출력
1.2) 정점 표현 학습의 이유
- 정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있다.
- 많은 기계학습 도구들은 벡터 형태로 표현된 사례(Instance)들을 입력으로 받는다.
- 따라서 그래프의 정점들을 벡터 형태로 표현할 수 있다면, 최신의 기계학습 도구들을 통하여 정점 분류(Node Classification), 군집 분석(Community Detection)등에 활용할 수 있다.
1.3) 정점 표현 학습의 목표
- 그래프에서의 정점간 유사도를 임베딩 공간에서도 '보존' 하는 것을 목표로 한다.
- 임베딩 공간에서의 유사도로는 내적(Inner Product)를 사용한다.
- 임베딩 공간에서의 u와 v의 유사도는 둘의 임베딩의 내적이고, 내적은 두 벡터가 클 수록, 그리고 같은 방향을 향할 수록 큰 값을 갖는다.
- 즉 정점 임베딩은 다음 두 단계로 이루어진다.
1. 그래프에서의 정점 유사도를 정의하는 단계
2. 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계
2. 인접성 기반 접근법
- 인접성(Adjacency) 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주한다.
- 두 정점 u와 v가 인접하다는 것은, 둘을 직접 연결하는 간선(u,v)가 있음을 의미한다. -> 인접행렬
2.1) 인접성 기반 접근법의 손실 함수 (Loss Function)
- Loss Function을 최소화하는 것이 목표이므로, 임베딩 공간에서의 유사도와 그래프에서의 유사도의 차이를 최소화하는 것(=손실 함수 값을 최소화)이 목표이다. -> 확률적 경사하강법
2.2) 인접성 기반 접근법의 한계
- 인접성만으로 유사도를 판단하는 것은 한계가 있다.
- 정점의 거리 관점에서, 인접성만으로 유사도를 판단시 거리가 2이상인 경우는 모두 유사도가 0이다.
- 군집 관점에서도, 인접성만으로 유사도를 판단하면 군집을 판단할 수 없다.
3. 경로 기반 접근법
- 경로 기반 접근법에서는 두 정점 사이의 경로(Path)가 많을 수록 유사하다고 간주한다.
3.1) 경로 기반 접근법의 손실 함수 (Loss Function)
4. 중첩 기반 접근법
- 중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주한다.
4.1) 중첩 기반 접근법의 손실 함수 (Loss Function)
- 공통 이웃 수를 대신 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수도 있다.
1. 자카드 유사도
- 공통 이웃의 수 대신 비율을 계산하는 방식
2. Adamic Adar 점수
- 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식
- u,v와 공통 이웃 w에 대하여 w의 연결성이 크면 클수록 가중치는 낮다.
- 왜냐하면, w의 연결성이 낮을 수록 u,v가 유사도가 가까울 확률이 높기 때문이다.
5. 임의보행 기반 접근법
- 임의보행 기간 접근법에서는 한 정점에서 시작하여 임의보행을 할 때, 다른 정점에 도달할 확률을 유사도로 간주한다.
- 임의보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복하는 것을 의미
- 임의보행을 사용할 경우, 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있다.
5.1) 임의보행 기반 접근법의 세 단계 과정
1. 각 정점에서 시작하여 임의보행을 반복 수행
2. 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성
이 때, 정점 u에서 시작한 임의보행 중 도달한 정점들의 리스트를 N_{R}(u)라고 한다.
한 정점을 여러 번 도달한 경우, 해당 정점은 N_{R}(u)에 여러 번 포함될 수 있다.
3. 손실함수를 최소화하는 임베딩을 학습한다.
5.2) u에서 부터 시작하여 v에 도달할 확률을 구하는 방법
5.3) 임의보행 기반 접근법의 손실 함수 (Loss Function)
5.4) DeepWalk와 Node2Vec
- 임의보행의 방법에 따라 DeepWalk와 Node2Vec으로 구분된다.
1) DeepWalk
DeepWalk는 앞에서 설명한 기본적인 임의보행을 사용한다.
즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복한다.
2) Node2Vec
Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)을 사용한다.
현재 정점(v)과 직전에 머물렀던 정점(u)을 모두 고려하여 다음 정점을 선택
직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여
*) 따라서 Node2Vec에서는 부여하는 확률에 따라 다른 종류의 임베딩을 얻을 수 있다.
 |
 |
| 멀어지는 방향에 높은 확률을 부여한 경우 | 가까워지는 방향에 높은 확률을 부여한 경우 |
5.5) 임의보행 기반 접근법의 손실 함수의 근사
- 앞서 알아본 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다.
즉, O(n^2) 시간복잡도를 가지므로 정점의 수가 많아지면 시간이 너무 오래 걸린다.
따라서 근사식을 사용하여 시간복잡도를 줄인다.
- 모든 정점에 대해서 정규화하는 대신, 몇 개의 정점을 뽑아서 비교하는 형태로 근사하여 시간복잡도를 줄인다.
- 이 때, 뽑힌 정점들을 네거티브 샘플이라고 부른다.
- 연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을 수록 학습이 더욱 안정적이다.
6. 변환식 정점 표현 학습의 한계
- 앞서 알아본 접근법 모두 변환식 방법으로 분류 된다.
6.1) 변환식 방법과 귀납식 방법
- 변환식(Transdctive) 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다.
- 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive) 방법과 대조된다.
6.2) 변환식 정점 표현 학습의 한계
1. 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다. -> 유연하지 못함
2. 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야한다. -> 메모리 리스크
3. 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없다. -> 표현력의 한계
-> 이러한 단점을 극복한 귀납식 임베딩 방법은 그래프 신경망(Graph Neural Network)이다.
1.2) 추천 시스템 (심화)
추천 시스템 (심화)
1. 잠재 인수 모형
1.1) 잠재 인수 모형 개요
- 잠재 인수 모형(Latent Factor Model)의 핵심은 사용자와 상품을 벡터로 표현하는 것
- 하지만, 사용자와 영화를 예시와 같이 로맨스<->액션, 가벼운 영화<->진지한 영화 구분할 필요도 없고 직접 수치적으로 표현하기 쉽지 않다.
- 따라서 이를 잠재 인수로 바꾸어, 고정된 인수 대신 효과적인 인수를 학습하는 것을 목표로 한다.
1.2) 잠재 인수 모형 손실 함수
1) 사용자와 상품을 임베딩하는 기준
2) 행렬 차원에서의 임베딩
3) 손실 함수
- 잠재 인수 모형은 다음 손실 함수를 최소화하는 P와 Q를 찾는 것을 목표로 한다.
- 손실 함수를 최소화하는 P와 Q를 찾기 위해서 확률적 경사하강법을 사용한다.
- 하지만, 위 손실 함수를 사용할 경우 과적합(Overfitting)이 발생할 수 있다.
- 기계학습 모형이 훈련 데이터의 잡음(Noise)까지 학습하여, 평가 성능은 오히려 감소하는 현상이 나올 수 있다.
- 따라서 위 손실 함수에서 아래 손실 함수 식과 같이 보완이 필요 하다.
- 즉, 정규화는 극단적인, 절댓값이 너무 큰 임베딩을 방지하는 효과가 있다.
2. 고급 잠재 인수 모형
- 기본 잠재 인수 모형에서 성능을 더욱 더 끌어올리기 위해 발전 시킨 모형
2.1) 사용자와 상품의 편향을 고려한 잠재 인수 모형
- 각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차
- 각 상품의 편향은 해당 상품에 대한 평점 평균과 전체 평점 평균의 차
- 사용자와 상품의 편향을 고려한 잠재 인수 모형의 손실 함수
2.2) 시간적 편향을 고려한 잠재 인수 모형
 |
 |
- 그림의 예시와 같이 시간에 따라서도 평균 평점도 영향을 받는 것을 알 수 있다.
- 시간적 편향을 고려한 잠재 인수 모형의 손실 함수
2. 피어 세션
1. 강의에 대한 토의
- Node2Vec 과 Word2Vec 차이
- 임의보행 기반 접근법에서 하이퍼파라미터
- 임의보행 기반 접근법 근사 손실함수에서 시그모이드가 나온 이유
- 잠재인수모형 구현방법 (Input은 무엇이 들어가고 무엇을 학습시키는가?)
- Further Question
1. 추천시스템의 성능을 높이기 위해, 예상 평점이 높은 상품을 잘 맞추는 것이 중요한데 어떻게 모델링할까?
- 손실함수의 변경 (높은 평점을 맞출때 가중치를 많이 준다)
2. 추천시스템의 성능을 향상 시키기위한 노력
- 딥러닝 다층레이어 구조가 아니고 머신러닝 학습이므로, 모델의 구조를 바꾸는 것보다는 주어진 데이터의 특징을 잘보고 (마치 시간적 편향을 추가했듯이) 손실함수에 항을 추가해서 고려해주자.
3. Conclusion
1. 임베딩 개념, 구현 과정에서 사용되는 역할 파악하기. (NLP, Graph에서 비슷한듯하면서도 상이한것 같다)
2. 추천시스템에서 입력은 과연 인접행렬로만 넣을 수 있을까? 다른 모델이나 추천시스템 관련 TASK 살펴보기