728x90
반응형
- 강의 목록
- 그래프의 정점을 어떻게 벡터로 표현할까?
- 그래프를 추천시스템에 어떻게 활용할까?
- 요약
강의
그래프의 정점을 벡터로 표현하는 법과, 추천 시스템에 대해 학습했다.
피어세션
어제의 학습을 복습했고, GRU를 활용한 문장 제작 인공지능을 연습했다.
- 학습정리
정점 표현 학습
- 그래프의 정점들을 벡터의 형태로 표현하는 것
- 정점 표현 학습은 간단히 정점 임베딩 (Node Embedding) 이라고 부른다.
- 정점 임베딩은 벡터 형태의 표현 그 자체를 의미하며, 정점이 표현되는 벡터 공간을 임베딩이라고 부른다.
- 정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것
- 정점 표현 학습의 입력은 그래프이다.
- 주어진 그래프의 각 정정 u에 대한 임베딩, 즉 벡터 표현 z(u)가 정점 임베딩의 출력이다.
- 정점 표현 학습을 하는 이유는, 정점 임베딩의 결과를 벡터 형태의 데이터를 위한 도구들을 그래프에 적용할 수 있기 때문.
- 예를 들어 기계학습 도구들이 그 예시이다. 대부분의 분류기들과 군집 분석 알고리즘들은 벡터 형태로 표현된 사례들을 입력으로 받는다.
- 그래프의 정점들을 벡터 형태로 표현하면 위의 도구들 뿐 아니라 최신의 기계 학습도구들을 정점 분류, 군집 분석 등에 활용할 수 있다.
- 정점을 벡터로 변환하는 것은 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표로 한다.
- 그래서 정점을 벡터로 변환하는 기준은 정점간 유사도를 활용한다.
- 임베딩 공간에서의 유사도로는 내적을 사용한다.
- 내적은 두 벡터가 클 수록 그리고 같은 방향을 향할수록 큰 값을 가진다.
- 정점 임베딩은 그래프에서의 정점의 유사도 정의 => 정의한 유사도를 보존하도록 임베딩을 학습 하는 단계로 나뉘어 진행된다.
인접성 (Adjacency) 기반 접근법
- 두 정점이 인접할 때 유사하다고 간주한다.
- 두 정점이 인접하다는 것은 둘을 직접 연결하는 간선이 있음을 의미한다.
- 인접성 기반 접근법에서는 손실 함수를 사용해 손실 함수가 최소화 되는 정점 임베딩을 찾는다.
- 손실 함수 최소화를 위해 (확률적) 경사하강법 등을 사용한다.
- 하지만 인접성만으로 유사도를 판단하는 것에는 한계가 존재한다.
- 위의 예시에서 빨간 정점과 파랑 정점은 거리가 3인데, 초록 정점과 파란 정점의 거리는 2이다.
- 군집 관점에서는 빨간색 정점과 파란색 정점은 다른 군집에 속하고, 초록색 정점과 파란색 정점은 같은 군집에 속한다.
- 인접성만을 고려할 경우 이러한 사실에 대한 고려 없이 두 경우의 유사도는 0이 된다.
거리/경로/중첩 기반 접근법
거리 기반 접근법
- 두 정점의 거리가 충분히 가까운 경우 유사하다고 간주한다.
- 위의 예시에서 빨간 정점은 초록, 파랑 정점들과 유사하니 유사도가 1이다.
- 하지만 빨간 정점은 보라 정점과 유사하지 않다. 유사도가 0이다.
경로 기반 접근법
- 두 정점 사이의 경로가 많을수록 유사하다고 간주한다.
- 두 정점 사이의 경로는 아래 조건들을 만족하는 정점들의 순열이다.
- u에서 시작해 v에서 끝난다.
- 순열에서 연속된 정점은 간선으로 연결되어 있다.
- 경로 기반 접근법은 두 정점 사이의 경로가 많을수록 유사하다고 간주한다.
중첩 기반 접근법
- 두 정점이 많은 이웃을 공유할수록 유사하다고 간주한다.
- 위의 예시에서 빨간 정점과 파란 정점은 두 명의 이웃을 공유하므로 유사도는 2이다.
- 정점 u의 이웃 집합을 N(u), 정점 v의 이웃 집합을 N(v)라고 정의하면 두 정점의 공통 이웃은 다음과 같다.
- 중첩 기반 접근법은 공통 이웃 수를 자카도 유사도 혹은 Adamic Adar 점수를 사용할 수도 있다.
임의보행 기반 접근법
- 한 정점에서 시작해 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주한다.
- 임의 보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하여 이동하는 과정을 반복하는 것을 의미한다.
- 임의 보행 사용시 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려할 수 있다.
- 임의 보행 기반 접근법은 다음 단계를 거친다.
- 각 정점에서 시작해 임의 보행 반복
- 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성
- 손실함수를 최소화하는 임베딩 학습
- 정점 u에서 시작한 임의보행이 정점 v에 도달할 확률은 다음과 같다.
- 식에서 알 수 있듯, 유사도가 높을수록 도달 확률이 높다.
- 이렇게 추정한 도달 확률을 사용해 손실함수를 완성하고 이를 최소화하는 임베딩을 학습한다.
- 임의 보행의 방법에 따라 Deepwalk와 Node2Vec으로 구분된다.
- DeepWalk는 앞서 설명한 기본적인 임의보행을 사용한다.
- 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하여 이동하는 과정을 반복한다.
Node2Vec
- 2차 치우친 임의보행을 사용한다.
- 현재 정점은 물론, 직전에 머물렀던 정점을 모두 고려하여 다음 정점을 선택한다.
- 직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여한다.
- Node2Vec에서는 이렇게 부여한 확률에 따라 다른 종류의 임베딩을 얻는다.
- 멀어지는 방향에 높은 확률 부여 시 정점의 역할이 같은 경우 임베딩이 유사하다.
- 정점의 역할은 다리 역할, 변두리 정점 등
- 가까워지는 방향에 높은 확률 부여 시 같은 군집에 속한 경우 임베딩이 유사하다.
- 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다.
- 중첩된 합 때문이다.
- 그렇기에 많은 경우 근사식을 사용하는데, 모든 정점에 대해 정규화를 하는 대신 몇 개의 정점을 뽑아 비교하는 형태이다.
- 이 때 뽑힌 정점들을 네거티그 샘플이라 부른다.
- 연결성에 비례하는 확률로 네거티브 샘플을 뽑기 때문에, 샘플은 많을수록 좋다.
from node2vec import Node2Vec
node2vec = Node2Vec(G, dimensions=16, walk_length=4, num_walks = 200, workers = 4)
#(입력 그래프, 임베딩 공간 차원, 랜덤 워크 길이 제한, 시작 지점 별 샘플링하는 랜덤 워크 수, 사용하는 쓰레드 수)
model = node2vec.fit(window = 2, min_count = 1, batch_words = 4)변환식 정점 표현 학습
- 정점 임베딩 방법은 변환식 방법이다. (Transductive)
- 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻을 수 있다.
- 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식 방법과 대조된다.
- 변환식 임베딩 방법은 다음의 한계를 갖는다.
- 학습이 진행된 이후에 추가된 정점의 임베딩을 얻을 수 없다.
- 모든 정점에 대한 임베딩을 미리 계산해 저장해야 한다.
- 정점이 속성 정보를 가진 경우 활용할 수 없다.
- 이러한 한계를 극복한 것이 귀납식 임베딩 방법이다. (Inductive)
- 그래프 신경망이 바로 귀납식 임베딩 방법이다.
추천 시스템 (기본) 복습
- 추천 시스템은 사용자들이 구매 혹은 선호할만한 상품, 영화, 영상을 추천하는 것이다.
- 추천 시스템은 사용자별 구매나 선호를 예측한다.
- 그래프 관점에서 추천 시스템은 미래의 간선을 예측하는 문제 혹은 누락된 간선의 가중치를 추정하는 문제로 해석이 가능하다.
- 내용 기반 추천 시스템은 각 사용자가 구매했거나 만족했던 상품과 유사한 상품을 추천한다.
- 본인의 기록만을 사용하기에 독특한 취향의 사용자도 추천이 가능하고, 새롭게 업로드된 상품에 대한 추천도 가능하다.
- 하지만 구매 기록이 없는 사용자에게는 적용할 수 없고, 상품의 부가 정보가 반드시 필요하다.
- 협업 필터링 기반 추천 시스템은 유사한 취향의 사용자들이 구매했더나 만족했던 상품을 추천한다.
- 상품에 대한 부가 정보가 없어도 사용이 가능하다.
- 하지만 충분한 수의 평점 데이터가 누적되어야 하고, 새로운 상품이나 새로운 사용자에게 추천이 불가능하다.
- 추천시스템은 훈련 데이터 중 일부를 없애고 추청해, 원본과 MSE, RMSE를 활용해 비교하여 평가한다.
넷플릭스 챌린지
- 넷플릭스 챌린지 데이터셋은 사용자별 영화 평점 데이터가 사용되었다.
- 훈련 데이터는 48만명의 사용자의 1만 8천 개의 영화에 대한 1억 개의 평점으로 구성된다.
- 평가 데이터는 각 사용자의 최신 평점 280만개로 구성된다.
- 넷플릭스 챌린지의 목표는 추천 시스템의 성능을 10% 이상 향상시키는 것이었다.
- 평균 제곱근 오차 0.9514를 0.8563으로 낮추는 것이 조건
- 해당 챌린지를 통해 추천 시스템의 성능이 비약적으로 발전했다.
- 해당 챌린지에서 행렬 분해 기법을 이용한 잠재요인 협업 필터링 방식이 등장했다.
잠재 인수 모형
- 사용자와 상품을 벡터로 표현하는 것을 핵심으로 한다.
- 잠재 인수 모형에서는 고정된 인수 대신 효과적인 인수를 학습하는 것을 목표로 한다.
- 이렇게 학습한 인수를 잠재 인수 (Latent Factor)라고 부른다.
- 사용자와 상품을 임베딩하는 기준은 사용자와 상품의 임베딩의 내적이 평점과 최대한 유사하도록 하는 것이다.
- 기존의 평점 행렬 R을 상품 행렬 Q와 사용자 행렬 P로 나눈다.
- 임베딩의 목적은 pxtqi이 rxi와 유사하도록 하는 것이다.
- 그래서 우측 상단의 식을 사용하는데, 일반 오차만 계산하면 과적합이 발생할 수 있기에 우측의 정규화 항을 손실 함수에 더해줌으로써 과적합을 방지한다.
- 정규화는 절댓값이 너무 큰 임베딩을 방지하는 효과가 있다.
- 손실함수를 최소화하는 P와 Q를 찾기 위해서는 (확률적) 경사하강법을 사용한다.
고급 잠재 인수 모형
사용자와 상품의 편향을 고려한 잠재 인수 모형
- 각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차이다.
- 상품의 편향은 해당 상품에 대한 평점 평균과 전체 평점 평균의 차이다.
- 개선된 잠재 인수 모형에서는 평점을 전체 평균, 사용자 편향, 상품 편향, 상호작용으로 분리한다.
- 개선된 잠재 인수 모형의 손실 함수는 아래의 식과 같다.
시간적 편향을 고려한 잠재 인수 모형
- 넷플릭스 시스템의 변화로 평균 평점이 크게 상승하는 사건이 있었다.
- 또한 영화의 평점은 출시일 이후 꾸준히 상승하는 경향이 있다.
- 개선된 잠재 인수 모형에서는 이러한 시간적 편향을 고려한다.
- 구체적으로 사용자 편향과 상품 편향을 시간에 따른 함수로 가정한다.
- 피어세션 회의 내용
차원을 잘 보면서 하자!
- 해야할 일
728x90
반응형
'BOOSTCAMP AI TECH > 5주차_Machine Learning with Graphs' 카테고리의 다른 글
| [BOOSTCAMP AI TECH] 25일차_ GNN (0) | 2021.02.26 |
|---|---|
| [BOOSTCAMP AI TECH] 23일차_군집 탑색 & 추천 시스템 (0) | 2021.02.24 |
| [BOOSTCAMP AI TECH] 22일차_페이지랭크 & 전파 모델 (0) | 2021.02.23 |
| [BOOSTCAMP AI TECH] 21일차_그래프 이론 기초 & 그래프 패턴 (0) | 2021.02.22 |
