스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 페이지 랭크 알고리즘의 문제점과 해결방법을 알아 보았습니다. 이번 포스팅에서는 재시작이 포함된 랜덤 워크와 개인화된 페이지 랭크에 대해서 알아보도록 하겠습니다. 앞의 포스팅에서 페이지 랭크의 해결 방법으로 모든 노드를 균일한 확률로 순간이동을 했었습니다. 여기서는 두 노드가 유사성을 전혀 고려하지 않습니다. 일반적으로 생각했을 때, 유사한 노드에 더 많이 이동해야 더 명확한 값을 가질 수 있겠죠? Recommendation 먼저 각 알고리즘에 대해 알아보기 전에 그래프를 이용한 추천에 대해서 알아보고 가겠습니다. 다음과 같이 하나의 유저 노드가 여러개의 아이템 노드를 가질 수 있는 bipartite graph(이분 그래프)로 표현해 줄 수 있습니..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 페이지 랭크 알고리즘에 대해서 배워보았습니다. 이번 포스팅에서는 페이지 랭크 문제점과 어떻게 해결해 나가는지 알아보겠습니다. PageRank Remind 페이지 랭크에 대한 기본 개념들은 지난 포스팅을 참고해 주시길 바랍니다. 우리는 앞에서 페이지 랭크의 수식을 다음과 같이 정의했었죠. 말로 풀어서 설명하자면, t+1번째 노드의 중요도는 t번째 나에게로 들어오는 모든 노드의 중요도의 합과 같습니다. 그래서 이 과정을 언제까지 하냐 살펴보면, 다음과 같이 이전 중요도와 임계값 이하로 차이가 날 때까지 위의 과정을 반복합니다. 위의 과정을 matrix로 표현하면 아래와 같은 수식을 얻을 수 있습니다. 초기 각 노드의 중요도는 1/노드 수이고, r(t..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 전체 그래프 임베딩에 대해서 알아봤습니다. 이번 포스팅에서는 구글의 아주 유명한 알고리즘인 페이지랭크에 대해서 배워보겠습니다. PageRank 페이지 랭크 알고리즘은 구글의 랭킹 알고리즘으로도 유명하죠. 그런데 그래프 이야기를 하다가 왜 갑자기 페이지 랭크 알고리즘이 나왔을까요? 페이지 랭크는 말 그대로 페이지 간의 랭크를 구하는 것인데 말이죠. 그렇다면 그림을 하나 보여드리도록 하겠습니다. 왼쪽은 우리가 지금까지 공부한 그래프이고, 오른쪽은 페이지와 그들간의 링크(하이퍼링크)를 연결한 것입니다. 그래프와 굉장히 유사하죠? 따라서 그래프와 웹은 비슷한 형태를 가진다고 할 수 있습니다. 그래프의 노드는 페이지로, 링크는 하이퍼링크로 연결될 수 있습..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 노드 레벨의 작업과 피쳐에 대해서 알아봤습니다. 이번 포스팅에서는 링크 레벨의 작업과 피쳐에 대해서 알아보겠습니다. Link-level 작업들 Link-level 작업은 두 노드 사이의 관계가 있는지 없는지 예측하는 작업입니다. 보시는 것처럼 노드들의 관계를 랭크로 나타내고 top-K개의 노드 쌍을 예측합니다. 여기에는 크게 2가지 작업이 있는데요. 첫 번째는 기존 그래프에서 랜덤하게 link를 지우고 그 부분을 예측하는 방법이며, 두 번째는 시간에 따라 지나는 관계성을 예측하는 것입니다. 이를 어떻게 적용해야 할까요? 일반적으로는 아래와 같은 프로세스로 작동합니다. 1. 각 노드 쌍(x, y)에 대한 스코어를 계산한다. - c(x, y)는 x와..
