스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 페이지 랭크 알고리즘의 문제점과 해결방법을 알아 보았습니다. 이번 포스팅에서는 재시작이 포함된 랜덤 워크와 개인화된 페이지 랭크에 대해서 알아보도록 하겠습니다. 앞의 포스팅에서 페이지 랭크의 해결 방법으로 모든 노드를 균일한 확률로 순간이동을 했었습니다. 여기서는 두 노드가 유사성을 전혀 고려하지 않습니다. 일반적으로 생각했을 때, 유사한 노드에 더 많이 이동해야 더 명확한 값을 가질 수 있겠죠? Recommendation 먼저 각 알고리즘에 대해 알아보기 전에 그래프를 이용한 추천에 대해서 알아보고 가겠습니다. 다음과 같이 하나의 유저 노드가 여러개의 아이템 노드를 가질 수 있는 bipartite graph(이분 그래프)로 표현해 줄 수 있습니..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 페이지 랭크 알고리즘에 대해서 배워보았습니다. 이번 포스팅에서는 페이지 랭크 문제점과 어떻게 해결해 나가는지 알아보겠습니다. PageRank Remind 페이지 랭크에 대한 기본 개념들은 지난 포스팅을 참고해 주시길 바랍니다. 우리는 앞에서 페이지 랭크의 수식을 다음과 같이 정의했었죠. 말로 풀어서 설명하자면, t+1번째 노드의 중요도는 t번째 나에게로 들어오는 모든 노드의 중요도의 합과 같습니다. 그래서 이 과정을 언제까지 하냐 살펴보면, 다음과 같이 이전 중요도와 임계값 이하로 차이가 날 때까지 위의 과정을 반복합니다. 위의 과정을 matrix로 표현하면 아래와 같은 수식을 얻을 수 있습니다. 초기 각 노드의 중요도는 1/노드 수이고, r(t..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 전체 그래프 임베딩에 대해서 알아봤습니다. 이번 포스팅에서는 구글의 아주 유명한 알고리즘인 페이지랭크에 대해서 배워보겠습니다. PageRank 페이지 랭크 알고리즘은 구글의 랭킹 알고리즘으로도 유명하죠. 그런데 그래프 이야기를 하다가 왜 갑자기 페이지 랭크 알고리즘이 나왔을까요? 페이지 랭크는 말 그대로 페이지 간의 랭크를 구하는 것인데 말이죠. 그렇다면 그림을 하나 보여드리도록 하겠습니다. 왼쪽은 우리가 지금까지 공부한 그래프이고, 오른쪽은 페이지와 그들간의 링크(하이퍼링크)를 연결한 것입니다. 그래프와 굉장히 유사하죠? 따라서 그래프와 웹은 비슷한 형태를 가진다고 할 수 있습니다. 그래프의 노드는 페이지로, 링크는 하이퍼링크로 연결될 수 있습..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 랜덤 워크에 대해서 알아봤습니다. 이번 포스팅에서는 전체 그래프 임베딩에 대해 알아보겠습니다. Embedding Entire Graphs 전체 그래프를 임베딩 하는 것은 무엇일까요? 단순 노드 임베딩에서는 노드들을 임베딩 공간으로 맵핑시켰습니다. 전체 그래프 임베딩은 하나의 노드를 임베딩 공간으로 맵핑시키는 것이 아니라 전체 그래프를 임베딩 공간으로 맵핑시키는 것을 뜻합니다. 즉, 마치 하나의 파일을 압축하듯 노드들의 정보를 압축시켜 임베딩 공간으로 맵핑해줍니다. 전체 그래프 임베딩은 분자가 독성이 있는지 탐지(분자 구조는 그래프 형태), 또는 이상 탐지 등에 사용될 수 있습니다. Approach1 : 노드 임베딩 값의 평균 또는 총합 이용 첫 ..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 노드 임베딩이 어떤 과정을 거쳐 진행되는지 간단하게 알아봤습니다. 오늘은 노드 임베딩의 접근 방식 중 하나인 랜덤 워크(random walk)에 대해서 알아보겠습니다. 본격적인 설명에 앞서 몇가지 개념을 정의하고 가도록 하겠습니다. zu는 노드 u가 임베딩된 벡터입니다. P(v|zu)는 u노드로 부터 시작한 랜덤 워크가 v를 지나갈 확률을 뜻합니다. softmax 모델이 예측한 K벡터를 합이 1인 확률로 변환해줍니다. sigmoid S모양의 함수로 예측 값을 0~1사이의 값으로 변환시켜줍니다. Random Walk 랜덤워크는 시작점 u에서 무작위로 다음 노드를 선택하여 그래프를 돌아다닐 때, 특정 노드 v를 들릴 확률을 유사도로 두고 학습하는 방..
스탠포드 강의를 듣고 정리한 내용입니다. 지난 포스팅에서는 노드 레벨의 작업과 피쳐에 대해서 알아봤습니다. 이번 포스팅에서는 링크 레벨의 작업과 피쳐에 대해서 알아보겠습니다. Link-level 작업들 Link-level 작업은 두 노드 사이의 관계가 있는지 없는지 예측하는 작업입니다. 보시는 것처럼 노드들의 관계를 랭크로 나타내고 top-K개의 노드 쌍을 예측합니다. 여기에는 크게 2가지 작업이 있는데요. 첫 번째는 기존 그래프에서 랜덤하게 link를 지우고 그 부분을 예측하는 방법이며, 두 번째는 시간에 따라 지나는 관계성을 예측하는 것입니다. 이를 어떻게 적용해야 할까요? 일반적으로는 아래와 같은 프로세스로 작동합니다. 1. 각 노드 쌍(x, y)에 대한 스코어를 계산한다. - c(x, y)는 x와..
스탠포드 강의를 듣고 정리한 내용입니다. 앞의 포스팅에서도 언급했지만, 그래프는 크게 3가지의 작업을 할 수 있습니다. 오늘은 위의 방법들 중 Nodel-level에 대해서 포스팅하도록 하겠습니다. Node-level 작업들 Node-level 작업은 네트워크가 주어지고, 각 노드들이 위와 같이 2개의 라벨을 가진다고 했을 때, 라벨이 달리지 않은 노드에 대해 어느 라벨을 가질지 예측하는 작업을 뜻합니다. 왼쪽에 있는 회색 노드들은 라벨이 붙어있지 않은 노드들인데, 이것을 ML로 학습시켜 라벨을 가지도록합니다. 마치 semi-supervised 학습처럼 보이죠. 위의 작업을 가능하게하는 node feature extraction에 대해서 알아보도록 하겠습니다. Node degree Node central..
스탠포드 강의를 듣고 정리한 내용입니다. 그래프 표현 방법 앞의 포스팅에서는 그래프에는 어떤 종류가 있는지, 어떻게 활용될 수 있는지 알아보았습니다. 이번 포스팅에서는 그래프를 어떻게 표현하는지에 대해서 알아보도록 하겠습니다. 앞에서도 살짝 언급했듯이 그래프는 노드와 엣지로 구성되어있습니다. 이를 수학적 기호로 표현하면 아래와 같습니다. 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..
스탠포드 강의를 듣고 정리한 내용입니다. 왜 그래프인가? 그래프는 일반적으로 엔티티들의 관계 또는 상호작용을 설명하고 분석하는 "언어"입니다. 따라서 위와 같이 데이터를 하나의 독립적인 포인트로 보기 보다는 이렇게 관계, 네트워크 측면에서 생각하자는 것이죠! 왜냐하면!!! 위와 같이 우리의 주변에는 정말 다양한 네트워크/그래프 형태의 데이터가 있기 때문이죠. 따라서 그래프 형태의 데이터를 잘 사용할 수 있다면, 위의 데이터들도 자동적으로 잘 활용될 수 있겠죠? 그럼 그래프의 종류에 대해서 잠깐 정리를 하고 가겠습니다. 그래프의 종류는 natural graph로 잘 알려진 networks와 representation인 graph으로 나뉩니다. Network(also known as Natural Graph..
