24.정점 임베딩과 추천시스템 Latent Factor Model

강의 복습 내용

• 정점임베딩
  • 그래프의 정점을 벡터로 표현

얻은 지식

---

변환식 정점 표현 학습

• 정점표현 학습(정점임베딩)
  • 그래프의 유사도 기준을 찾기위햔 다양한 접근법
    • 인접성 기반 접근법
    • 거리/경로/중첩 기반 접근법
    • 임의보행 기반 접근법
• 한계

정점 표현 학습

• 입력 그래프의 정점 -> 출력 벡터로 표현하는것
  • 정점 임베딩(node Embedding)이라 부른다.
  • 임베딩 공간
    • 정점이 표현되는 벡터공간
• 
  • 정점 u에 대한 임베딩은 벡터 z_u로 출력

이유

• 그래프에 벡터 형태의 데이터 도구 적용가능
  • 분류기(로지스틱 회귀분석, 다층 퍼셉트론)을 사용가능
    • 군집분석 알고리즘(K-Means) 등
  • 최신 기계 학습도구 사용가능
    • 정점 분류, 군집분석에 사용
• 그래프 분석을 위해 그래프에 특화된 알고리즘을 개발해야 했다.
• 벡터형태로 바꾸면서 벡터를 입력으로 쓰이는 데이터도구가 사용 가능해 졌다.

목표

• 벡터로 만들때 정점간 유사도를 보존 해야한다.
  • 벡터에서의 유사도는 무엇일까?
  • 벡터간의 거리로 유사도를 측정한다.
  • 좌측은 그래프를, 우측은 정점임베딩 공간의 벡터이다.
  • 보라색 정점들은 좌측 그래프와 우측 임베딩공간에서 유사하게 뭉쳐있는것을 보인다.
  • 이러한 유사한 정도를 어떻게 계산하는가?
    • 내적을 사용
• 임베딩 공간에서의 유사도
  • 내적을 사용
    • 두 정점 u와 v의 유사도는 \(z_u^Tz_u = \left\| z_u \right\| \cdot \left\| z_u \right\| \cdot cos(\theta)\)
    • 내적은 두벡터가 클수록, 같은 방향일 수록 큰값을 가진다.
• 정점임베딩의 단계를 정리해보자.
  • 그래프에서의 정점 유사도를 정의한다.
  • 그래프의 정점 유사도를 보존하도록, 정점 임베딩을 학습시킨다.
    • 그래프에서의 유사도의 성질을 벡터로 옮길 수있는 \(z_u^Tz_u\)를 학습시키기이다.
• 그래프의 정점 유사도를 정의하는 여러 접근법(방식)이 있다.
  • 인접성 기반 접근법
  • 거리/경로/중첩 기반 접근법
  • 임의보행 기반 접근법

---

인접성 기반 접근법

• 인접 행렬(adjacency matrix)을 이용해 두 정점이 인접할때 유사하다고 간주
  • u와v가 인접하다는것은 간선 (u,v)가 있을을 의미
  • 원소A_{u,v}를 두 정점 u와 v의 유사도
    • 인접하면1, 인접안하면 0이된다.
• 손실함수
  • 
    • 그래프의 유사도로 정의한 A{u,v}
    • 정점을 u,v의 정점임베딩에서의 유사도 z_u^Tz_v를
    • 임베딩유사도와 그래프유사도의 차이(손실)를 줄이는것
  • 차이가 최소가 되도록 정점 임베딩을 학습
    • 경사하강법을 사용

한계

• 인접성만으로 유사도를 판단하기에는 한계가 있다.
  • ![그림]
  • 단순히 이웃만 판단하기때문에 거리나, 군집들을 보지 못한다.
  • 파랑과 초록은 군집이지만 인접성 기반으로 0이 나온다.

---

거리/경로/중첩 기반 접근법

거리 기반 접근법

• 두 정점 사이의 거리가 충분히 가까운 경우 유사하다
  • ![그림]
  • 빨간점을 기준으로 일정 거리를 유사하다고 정한다.
  • 유사하면 1,유사하지 않으면 0

경로 기반 접근법

• 두 정점 사이에 경로가 많을 수록 유사
  • \(A_{u,v}^k\)두 정점 u와 v상의 경로 중 거리가 k인것
  • 인접행렬 A의 k제곱의 (u,v)원소와 같다
• 손실함수
  • \[\]

중첩 기반 접근법

• 두 정점이 많은 이웃을 공유할 수 록 유사
  • 유사도는 공유하는 이웃의 수
• u의 이웃집합N(u), v의 이웃집합 N(v)일때 이웃의수S_u,v로 정의
• 손실함수
  • \[\]
• 공통 이웃수 대신 자카드유사도 또는 adamic adar 점수를 사용
  • 자카드 유사도
    • \[\]
    • 공통 이웃수 대신 비율을 계산하는 방식
    • 0부터 1사이 값이 나온다.
    • 둘의 이웃이 다 같을때 1이 된다.
  • adamic adar
    • \[\]
    • 공통이웃 각각에 가중치를 부여하여 가중합을 계산
      • 공통이웃이 연결성이 높으면 가중치가 낮게 계산된다. (1/dw)로 반비례
        • 공통이웃에게는 여러 이웃중 하나일뿐이므로 가중치가 낮게 설정되어 계산된다.

임의보행 기반 접근법

• 한 정점에서 시작하여 임의보행을 할때 다른 정점에 도달할 확률
• 임의보행
  • 현재 정점의 이웃중 하나를 균일한 확률로 선택하여 이동하는 과정
• 지역정보와 그래프 전역 정보를 모두고려한다.
  • 지역정보는 시작점 기준으로 여러곳을 갈수 있다
  • 그래프 전역정보는 따로 거리 제한이 없어 모든 곳을 돌 수 있다
• 기법
  • 1) 강 정점에서 시작하여 임의 보행 수행
  • 2) 도달한 정점리스트를 구성
    • u에서 시작한 임의보행리스트 N_R(u)
    • 중복도 허용

• 3) 손실함수를 최소화 하는 임베딩 학습

• 손실함수

• 임의보행방법
  • DeepWalker
    • 일반적인 임의 보행
  • Node2Vec

---

node2vec

• 2차 치우친 임의 보행
• 현재정점과 직전에 머물렀던 정점을 모두 고려
• ![그림]
  • u에서 시작, v에 도달함
  • 정점 거리를 기준으로 차등적인 확률을 부여
• 부여하는 확률에 따라 다른 임베딩을 얻는다.
  • ![그림]
  • 멀어지는 방향에 높은 확률인경우
    • 비슷한 역할(다리,변두리)이 같은경우 임베딩이 유사
  • 가까워지는 방향에 높은 확률인경우
    • 같은 군집에 속한 경우 임베딩이 유사
• 손실함수 근사
  • 일반 손실함수는 정점 수의 제곱에 비례하는 시간 소요
  • 근사식 \(\)

---

변환식 정점표현 학습과 귀납식 정점 표현 학습

• 변환식 정점표현
  • 학습의 결과로 정점의 임베딩 자체를 얻는다.
• 귀납식 정점 표현
  • 정점을 임베딩으로 변화시키는 함수(인코더)
  • 그래프 신경망(graph neural network)

변환식의 한계

• 학습이 진행된 이후 추가된 정점에 대해서는 임베딩을 못얻는다.
• 모든 정점에 대한 임베딩을 미리 계산하여 저장
• 정점이 속성정보를 가진경우 활용 불가

---

그래프의 추천시스템(심화)

• 추천시스템 기본
• 기본잠재인수모형
• 고급잠재인수모형

추천시스템

• 아마존(물건),유튜브(영상),페이스북(친구) 추천
• 사용자가 구매할 만한 상품 추천
  • 미래 간선 예측
  • 누락된 간선의 가중치 추정
• 내용기반 추천
  • 사용자가 구매한 상품과 유사한상품 추천
• 협업필터링
  • 유사취향 사용자들이 선호한 상품 추천
• 추천 시스템 평가
  • 평균제곱 오차

넷플릭스 챌린지

• 사용자별 영화 평점데이터를 사용
  • 2000~2005까지수집
• 추천시스템의 성능을 10%이상 향상시키기
  • 평균제곱근 오차를 0.9514->0.8563까지 낮춰야했ㄷ.

잠재 인수 모형

• 잠재인수 모형(latent factor model)
  • svd, uv decomposition이라고도 불림
• 사용자와 상품을 벡터로 표현
  • 정점 임베딩
• 임베딩 예시
  • ![그림]
  • 2차원공간에 사용자와 영화 카테고리를 표현
• 고정된 인수 대신 효과적인 인수를 학습
  • 추천을 정확하게 하는 차원을 찾는것
  • ![그림]
  • 학습한 인수를 잠재 인수라 부른다.

손실

• overfitting
• 식
  • 람다를 통해 정규화의 세기를 조절한다.
• 정규화 효과
• ![그림]
  • 너무 멀리 간것을 어느정도 완화시킨다.

최적화

• 손실함수를 최소화하는 P와 Q를 찾기
• 경사하강법

고급 잠재 인수 모형

• 사용자,상품의 편향
• 시간적 편향

사용자,상품의 편향을 고려

• 사용자 편형
  • 사용자의 평점평균과 전체 평점 편균의 차
• 상품의 편향
  • 상품에 대한 평점 평균과 평점 평균의 차
• 잠재 인수 모형의 평점
  • 전체평균, 사용자 편향, 상품 편향, 상호작용으로 분리
• 손실함수
  • \(\)식
• 아직 목표에 도달 못함

시간적 편향을 고려

• 시간이 지남에 따라 평점이 변화된다.
  • 넷플릭스 시스템이 바뀌면서 평점이 상승
  • 영화가 시간이 지나면서 평점이 상승
    • 소문에 의해

---

넷플릭스 결과

• bellkor팀
  • 앙상블(ensemble)을 사용
• 연합 ensemble팀
  • bellkor를 무너뜨리려고 연합한 앙상블팀
• bellkor가 20분 빨라서 이겼다

---

실습

node2vec 수행

• Node2Vec(G,dimension,walk_length,num_walks,worker)
  • 입력그래프, 임베딩공간차원, 길이제한,시작지점별 샘플링수, 스레드갯수`

    surprise라이브러리, 잠재인수 모형 활용

• from surprice import SVD

---

좀더 찾아보기

---

피어세션 정리

• 접근법?
  • 학습!
• R^d는?
  • d는 무슨의미?
  • d는 feature의 차원들
  • 차원을 최소화하기
  • 1차원이면 별 의미 없으니까?
• exponential은 왜 나왔나
  • 음수가 나올수있다.
  • 이를 0이상으로 만들기 위해
• 클러스터와 커뮤니티
  • 그래프에서는 커뮤니티, 벡터에서는 클러스터
    • 클러스터는 간선이없는 데이터
  • 커세라의 k-means
    • 클러스터인데 간선이있는 그래프 모양

further

• rmse 예상이 높거나 낮아도 동일한 패널티
  • 예상평점이 높은 상품을 잘맞추는게 중요