스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 페이지 랭크 알고리즘에 대해서 배워보았습니다. 이번 포스팅에서는 페이지 랭크 문제점과 어떻게 해결해 나가는지 알아보겠습니다. PageRank Remind 페이지 랭크에 대한 기본 개념들은 지난 포스팅을 참고해 주시길 바랍니다. 우리는 앞에서 페이지 랭크의 수식을 다음과 같이 정의했었죠. 말로 풀어서 설명하자면, t+1번째 노드의 중요도는 t번째 나에게로 들어오는 모든 노드의 중요도의 합과 같습니다. 그래서 이 과정을 언제까지 하냐 살펴보면, 다음과 같이 이전 중요도와 임계값 이하로 차이가 날 때까지 위의 과정을 반복합니다. 위의 과정을 matrix로 표현하면 아래와 같은 수식을 얻을 수 있습니다. 초기 각 노드의 중요도는 1/노드 수이고, r(t..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 전체 그래프 임베딩에 대해서 알아봤습니다. 이번 포스팅에서는 구글의 아주 유명한 알고리즘인 페이지랭크에 대해서 배워보겠습니다. PageRank 페이지 랭크 알고리즘은 구글의 랭킹 알고리즘으로도 유명하죠. 그런데 그래프 이야기를 하다가 왜 갑자기 페이지 랭크 알고리즘이 나왔을까요? 페이지 랭크는 말 그대로 페이지 간의 랭크를 구하는 것인데 말이죠. 그렇다면 그림을 하나 보여드리도록 하겠습니다. 왼쪽은 우리가 지금까지 공부한 그래프이고, 오른쪽은 페이지와 그들간의 링크(하이퍼링크)를 연결한 것입니다. 그래프와 굉장히 유사하죠? 따라서 그래프와 웹은 비슷한 형태를 가진다고 할 수 있습니다. 그래프의 노드는 페이지로, 링크는 하이퍼링크로 연결될 수 있습..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 노드 임베딩이 어떤 과정을 거쳐 진행되는지 간단하게 알아봤습니다. 오늘은 노드 임베딩의 접근 방식 중 하나인 랜덤 워크(random walk)에 대해서 알아보겠습니다. 본격적인 설명에 앞서 몇가지 개념을 정의하고 가도록 하겠습니다. zu는 노드 u가 임베딩된 벡터입니다. P(v|zu)는 u노드로 부터 시작한 랜덤 워크가 v를 지나갈 확률을 뜻합니다. softmax 모델이 예측한 K벡터를 합이 1인 확률로 변환해줍니다. sigmoid S모양의 함수로 예측 값을 0~1사이의 값으로 변환시켜줍니다. Random Walk 랜덤워크는 시작점 u에서 무작위로 다음 노드를 선택하여 그래프를 돌아다닐 때, 특정 노드 v를 들릴 확률을 유사도로 두고 학습하는 방..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 링크 레벨의 작업과 피쳐에 대해서 알아봤습니다. 이번 포스팅에서는 그래프 레벨의 피쳐와 그래프 커널에 대해 알아보겠습니다. Graph-level feature graph-level feature의 목적은 전체 그래프의 구조를 특징짓는 하나의 feature를 만드는 것입니다. 예를 들어 graph-level feature는 위의 A~H노드와 그 간선들을 표현할 수 있는 하나의 feature로 만드는 것이죠. 위의 작업을 하기 위해서는 kernel이라는 것을 이용합니다. kernel은 쌍으로 이루어진 그래프들의 유사도를 비교하기 위해 전통적인 ML에서 널리 쓰이는 방법입니다. 요약을 하자면 다음과 같습니다. 두 그래프의 커널이란 서로 다른 데이터 ..
스탠포드 강의를 듣고 정리한 내용입니다. 그래프 표현 방법 앞의 포스팅에서는 그래프에는 어떤 종류가 있는지, 어떻게 활용될 수 있는지 알아보았습니다. 이번 포스팅에서는 그래프를 어떻게 표현하는지에 대해서 알아보도록 하겠습니다. 앞에서도 살짝 언급했듯이 그래프는 노드와 엣지로 구성되어있습니다. 이를 수학적 기호로 표현하면 아래와 같습니다. Objects : nodes, vertices → N Interactions : link, edges → E System : network, graph → G(N,E) Directed Graph와 Undirected Graph 그래프의 종류에는 크게 Directed Graph와 Undirected Graph가 있습니다. Directed Graph Directed Gr..
