ok-lab

전통적인 자연어처리 방식에서는 동시발생 행렬(Co-occurrence Matrix), 즉, 각 단어가 동시에 출현한 빈도를 측정한 행렬을 사용하였다. 그러나, 발생 횟수를 기반으로 하기 때문에 많이 출현하는 The, A, An 등과 같은 단어로 인해 해당 단어와의 유사도가 높게 측정될 수 있다. 이와 같은 문제를 해결하고자 점별 상호정보량(Pointwise Mutual Information, PMI)이라는 척도가 도입된다. \[ \text{PMI} (x, y) = \log_2 \frac{P(x, y)}{P(x) \cdot P(y)} \] $P(x)$는 x가 발생할 확률, $P(y)$는 y가 발생할 확률, $P(x,y)=P(x \cap y)$는 x와 y가 동시에 발생할 확률을 의미한다. 이때 PMI 값이 ..

Contents CNN은 이미지처리, 자연어처리 등 다양한 분야에서 각광받는 기술이다. 파라미터를 공유하는 개념을 통해서 기존의 연구에서 제안된 단순한 Linear 수준을 넘어서서 매우 우수한 성능을 발휘한다. 이번 글에서는 CNN을 밑바닥부터 구현하는 것을 다룬다. Import Packages from sklearn.datasets import fetch_openml from sklearn.utils import check_random_state from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler import matplotlib.pyplot as plt import pand..

Contents 네트워크에는 밀집(Density), 차수(Degree), 길이(Length) 등 다양한 지표가 존재하며, 이를 측정하기 위한 방법도 다양하게 존재한다. 본 글에서는 이를 측정하는 방법에 대해서 알아본다. Density Density는 그래프의 밀집 정도를 의미한다. 예를 들어, 완전 연결 그래프의 경우 Density는 1이 될 것이다. 완전 연결 그래프는 Complete Graph 혹은 Clique로 부르기도 한다. 이때 평균 차수는 다음과 같이 계산할 수 있다. \[ m = \begin{pmatrix} n \\ 2 \end{pmatrix} = \frac{n (n-1)}{2} \] \[ \left \langle k \right \rangle = \frac{2m}{n} = \frac{n(n..

Contents Walk, Trail 등 다양한 구조를 가진 그래프가 존재한다. 본 글에서는 각 그래프에 해당하는 이름에 대해서 살펴보고 해당 그래프의 특징을 알아보고자 한다. 먼저 Walk를 다루기 이전에 그래프에서의 Length가 어떤 것인지 알아보자. Length Length는 그래프의 길이를 의미한다. 노드의 개수가 아닌 엣지들이 지나가는 길의 수를 의미하는 것이며, 이를 Hop이라고 한다. $V_5$에서 $V_1$까지는 총 2-hop을 나타내고, $V_5$에서 $V_3$까지는 3-hop을 나타낸다. 그렇다면 Hop의 수는 어떻게 구할 수 있을까? Walk 보행(Walk)은 복잡하게 보이지만, 그래프의 노드를 통과하는 하나의 스텝(step)일 뿐이다. Walk는 움직일 때 거치는 엣지의 수를 의미..

Contents 노드를 임베딩(Embedding)하는 이유는 노드의 정보를 vector로 표현할 수 있다면 Classification, Cluster 등 다양한 기법을 사용할 수 있는 것 뿐만 아니라 Node Classification, Community Detection 등에도 활용이 가능하다. 그렇다면 어떻게 노드를 벡터로 변환할 수 있을까? 이에 대한 내용은 Leskobec 교수님의 Node2Vec을 살펴보거나 DeepWalk를 보면 자세히 알 수 있으며 본 강의에서는 Random Walk, Node2Vec 이전에 제안된 노드 임베딩 기법의 개략적인 내용에 대해서만 다룬다. Random Walk, Node2Vec 등의 모델은 여기를 참고하면 된다. 그래프에서의 노드 간의 유사도를 최대한 보존하면서 ..

Contents Community 군집이란 Cluster 혹은 Community를 의미하며, 집합에 속하는 노드 사이에는 만은 엣지가 존재하고, 집합에 속하는 노드와 그렇지 않은 노드 사이에는 적은 수의 엣지가 존재해야 한다. 아래의 그림을 예로 들면, 11개의 군집이 있는 것을 확인할 수 있다. 온라인 소셜 네트워크에서도 군집을 찾아볼 수 있다. 이때는 사회적 무리(Social Circle)를 의미하는 경우가 많다. 예를 들어, 같은 회사 동료라는 사회적 무리와 가족 관계 혹은 고등학교 친구 등과 같은 사회적 무리를 의미한다. 이때의 사회적 무리는 회사 동료, 가족 관계, 고등학교 친구 뿐만 아니라 같은 지도 교수님한테 지도받은 학생들, 대학 동기 등 다양한 사회적 무리를 나타낼 수 있다. 온라인 소셜..

Contents 그래프를 통한 influence는 정보 혹은 행동, 고장, 질병 등 다양한 influence가 존재할 수 있다. 예를 들어, 온라인 소셜 네트워크를 통해 다양한 정보를 전파할 수 있다. 컴퓨터 네트워크에서는 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수도 있다. 최근에 이슈가 된 코로나-19라는 질병이 사회라는 거대한 소셜 네트워크를 통해 전파되는 것도 언급할 수 있다. 이처럼 다양한 influence를 그래프로 표현할 수 있을 것이다. 이와 같은 전파 과정을 체계적으로 이해하고 대처하기 위해서는 그래프의 구조를 제대로 이해하고 있어야 한다. 본 글에서는 Cascade model 중 두 가지 모형을 다룬다. 첫 번째 모형은, 의사결정 기반의 Cascade model이다. 먼저 ..

본 글에서는 DGL 을 통한 Link Prediction을 GraphSAGE를 통해 진행한다. Link Prediction은 두 노드가 연결되어 있는지, 아닌지를 확인하는 문제로 이해할 수 있다. 패키지 불러오기 본 글에서는 DGL 과 PyTorch 그리고 인접행렬을 만들거나 연산을 진행하기 위한 numpy와 scipy를 사용한다. import dgl import dgl.function as fn import torch import torch.nn as nn import torch.optim as optim import torch.nn.functional as F import itertools import numpy as np import scipy.sparse as sp from sklearn.metr..

Contents 본 글에서는 DGL 패키지를 이용해서 그래프를 생성하는 방법에 대해서 다룬다. DGL 패키지는 그래프를 다루기 위한 패키지로 그래프를 생성하거나 기존 연구에서 제안된 함수(GCN, GraphSAGE 등)를 호출을 통해 편리하게 사용하도록 도와주는 패키지다. 패키지 불러오기 import dgl import torch 기본적으로 dgl은 PyTorch와 함께 사용한다. tensorflow도 사용하는 것이 가능하지만 본 글에서는 PyTorch를 이용한 dgl을 다루어 볼 것이다. 필요한 함수는 dgl이며 pip install을 통해 설치하면 된다. 그래프 생성하기 dgl에서 그래프를 생성하는 것은 매우 간단하다. dgl 내에 내장된 graph 함수를 사용하면 바로 만들 수 있다. g = dgl..

Contents Graph Convolution Neural Network(GCN)는 2017년에 처음으로 제안된 모델이다[논문]. 우수한 성능을 보이고 있으며, GNN에 CNN을 접목하기 시작한 계기가 된다. 본 글에서는 이론적인 내용은 자세히 다루지 않고, DGL을 사용해서 GCN을 만들어볼 것이다. GCN에 대한 상세한 내용은 여기를 참고하면 된다. 1. Load Package GCN을 사용하기 위해서는 Pytorch, torch_geometric, Tensorflow, PyG 등 다양한 프레임워크들이 존재하지만 본 글에서는 가장 간단한 DGL을 이용해서 GCN을 구현한다. 구현하기에 앞서 먼저 필요한 패키지들을 호출하자. import numpy as np import dgl from dgl.nn ..