전체 글 검색 결과
213 개의 검색 결과가 있습니다.
Machine Learning - Thoery/Graph Representation Learning

SMILES 표기법이란? (SMILES representation 설명 및 장단점)

SMILES 표기법은 Simplified Molecular Input Line Entry System의 준말로, 분자 구조를 string 형태로 표현하여 NLP에 활용된 다양한 머신러닝 / 딥러닝 알고리즘들을 분자 구조에도 적용할 수 있게 해주는 표기법이다. 이번 글에서는 SMILES 표기법을 어떻게 쓸 수 있는지와 함께 이의 장단점에 대해서 알아보겠다. SMILES 구성 요소 SMILES 표기법을 구성하는 요소는 크게 다섯가지로 나눌 수 있고, 이는 원자 (atom), 결합 (bond), 고리 (ring), 방향족 (aromaticity), 그리고 가지 (branch)이다. 각 요소들에 대해서 차례대로 알아보겠다. 원자 (atom) SMILES 표기법에서 각 원자는 해당하는 원소 기호로 표시하고, 수소..

2022. 3. 13. 16:44
Machine Learning - Thoery/Graph Representation Learning

Graph Laplacian 설명 (Unnormalized Laplacian, Normalized Laplacian)

Graph Laplacian은 Adjacency matrix 를 다양한 방법으로 변형하여 그래프를 표현할 수 있게 한 행렬들을 말한다. 이번 글에서는 이 Graph Laplacian의 종류 중 하나인 unnormalized Laplacian, normalized Laplacian의 정의와 특성들에 대해 알아보겠다. Unnormalized Laplacian Laplacian matrix 중 가장 기본이 되는 matrix가 unnormalized Laplacian이다. 이는 다음과 같이 정의한다. 위 식에서 D는 degree matrix, A는 adjacency matrix이다. 그러므로 unnormalized Laplacian matrix의 각 성분(L[i,j])은, (self-loop가 없는 그래프 가정..

2022. 2. 15. 21:00
Machine Learning - Thoery/Graph Representation Learning

Katz index란? (Katz index 증명, Adjacency matrix 설명)

local neighborhood를 활용한 measure들은, 두 노드가 공통된 이웃을 가지고 있지 않는 상황에서는 두 노드 간의 관계에 대해 추론하기 힘들다. 그러므로 이번 글에서는, 이러한 한계점을 해결하기 위해 도출된 개념인 그래프 전체를 고려하여 두 노드 간의 관계를 표현하는 Katz index에 대해 알아보고, 이와 함께 Adjacency matrix가 무엇이고 특성이 무엇인지에 대해 알아보겠다. 정의 Katz index는, 두 노드 사이의 모든 길이의 path의 빈도를 의미한다. 즉, 수학적으로 정의하면 아래와 같이 정의할 수 있다. 위 식에서 i는 두 노드 사이의 path의 길이를 의미하고, beta값은 긴 path에 대해 얼마나 weight를 줄 것인지를 결정한다. 예를 들어, beta가 ..

2022. 2. 9. 23:23
Machine Learning - Thoery/Graph Representation Learning

두 노드 사이의 관계를 표현하는 Local overlap measure (Sorensen index, Salton index, Jaccard overlap, RA index, AA index)

우리는 그래프를 활용해서 어떤 예측을 할 때, 하나의 노드가 어떤 특성을 가지고 있는지를 예측하기도 하지만 (node classification), 두 노드 사이의 관계를 예측하기(link prediction)도 한다. 이번 글에서는 두 노드 사이의 관계를 표현하는 가장 기본이 되는 척도인 neighborhood overlap, 그 중에서도 local overlap measure에 대해서 알아보겠다. 우선, 두 노드 사이의 neighborhood overlap은 말 그대로 몇 개의 이웃(직접 연결된 노드)을 공유하고 있는지를 의미한다. 이를 식으로 나타내면 다음과 같다. 위 식은 다른 말로 common neighbors라고도 부른다. 예를 들어, 다음과 같은 그래프가 있다고 하자. 그림에도 나타나 있듯이..

2022. 2. 8. 22:53
Machine Learning - Thoery/Graph Representation Learning

Graphlet과 Graphlet Degree Vector(GDV)이란? (induced subgraph, graph isomorphism 설명)

이번 글에서는 node degree, clustering coefficient와 같이 node 특징을 나타낼 수 있는 척도 중 하나인 특정한 subgraph를 나타내는 말인 graphlet과, 이를 활용하여 node의 특징을 graph의 구조적인 측면을 활용하여 나타낼 수 있는 또다른 척도인 graphlet degree vector(GDV)에 대해 알아보겠다. Graphlet 우선, graphlet의 정의에 대해 알아보겠다. graphlet은 서로 연결되어 있는(connected) induced non-isomorphic subgraph를 말한다. connected는 떨어져 있는 노드가 없는 것을 의미할 것이고, 다른 두 단어는 조금 생소하다. 각 단어의 뜻을 하나씩 알아보겠다. induced subgr..

2022. 2. 8. 22:12
Machine Learning - Thoery/Graph Representation Learning

Clustering Coefficient 설명 (그래프의 clustering coefficient 계산)

이번 글에서는 node degree, node centrality에 이어 또다른 node feature인, 해당 노드에 이웃하는 노드들이 얼마나 잘 연결되어 있는지를 표현하는 지표인 clustering coefficient가 무엇인지에 대해 설명하겠다. 정의 Clustering coefficient는 해당 노드에 이웃하는 노드들이 얼마나 잘 연결되어 있는지를 측정하는 measure이다. 이의 정의는 아래와 같다. 위 식에서 d_u는 노드 u의 degree를 뜻하고, N(u)는 노드 u의 이웃 노드를 뜻한다. 그러므로 분모는 노드 u의 이웃 노드들끼리의 노드쌍의 경우의 수를 의미하고, 분자는 그 중 연결된 엣지의 수를 의미한다. 즉, clustering coefficient가 1이면 모든 이웃 노드들이 서..

2022. 1. 27. 20:48
Machine Learning - Thoery/Graph Representation Learning

Node degree와 Node centrality 설명 (betweenness centrality, closeness centrality, eigenvector centrality)

이번 포스팅에서는 노드에 연결된 엣지 수의 합을 의미하는 node degree, 노드의 중요도를 의미하는 node centrality가 무엇인지에 대해 알아보겠다. Node degree Node degree란, 노드에 연결된 엣지 수의 합을 말한다. 즉, 노드가 몇 개의 이웃(neighbor)을 가지는지를 표현한 것이라고 할 수 있다. 이를 식으로 표현하면 아래와 같다. 예를 들어, 아래와 같이 생긴 그래프가 있다고 하자. 이 예시 그래프에서 노드 A의 node degree는 C 하나의 노드만 연결되어 있기 때문에 1, 노드 D의 node degree는 B, C, E, H 네 개의 노드가 연결되어 있기 때문에 4가 될 것이다. Node degree는 가장 기본이 되는 graph statistics이기 때..

2022. 1. 27. 20:31
Machine Learning - Thoery/Graph Representation Learning

Erdos-Renyi Model 설명 (Erdős–Rényi model이란? ER model이란?)

이번 글에서는 graph를 만드는 generative model의 가장 기본이 되는 모델인 Erdos-Renyi model이 무엇이고, 그 특징이 어떤 것인지에 대해 알아보겠다. 정의 Erdos-Renyi Model은, 한 마디로 정리하면 모든 엣지가 생길 확률이 일정한 generative model이다. 노드 u와 v 사이에 엣지가 생길 확률(r)은 아래와 같이 정의할 수 있다. 즉, 간단하게 어떤 노드 쌍을 가져오더라도 이들 사이에 엣지가 존재할 확률은 r인 모델인 것이다. 이 방식으로 그래프를 만드는 데에는 O(|V^2|)의 time complexity가 필요하다. (모든 노드 쌍에 대해 엣지가 존재할 지 여부를 결정해야 하기 때문이다.) 장단점 Erdos-Renyi model의 장점은 간단하다는 ..

2022. 1. 26. 22:42
Machine Learning - Thoery/Graph Representation Learning

Graph와 Machine learning 설명 (Node classification, relation prediction, clustering, graph regression)

Graph 형태로 표현된 데이터는 복잡한 데이터를 한 눈에 쉽게 파악할 수 있게 해주고, 데이터 간의 관계를 한 눈에 알 수 있게 해준다는 장점을 가진다. 그래프에 머신러닝을 적용하는 것이 기존의 머신러닝과 비교했을 때 가지는 가장 큰 차이점은 그래프 내부의 노드나 엣지들이 서로 독립적인 것이 아닌, 관계를 가지고 있기 때문에 이들이 가지는 관계성을 머신러닝 시에 고려해야 한다는 점이다. 이를 고려한 그래프에의 머신러닝 활용 방법에는 크게 네 가지가 있다. 이번 포스팅에서는 그래프의 머신러닝 활용 방법에는 어떤 것이 있는지에 대해 알아보겠다. Node classification Node classification은 그래프 내의 노드의 label을 classification하는 것을 말한다. 이 노드의 l..

2021. 11. 8. 22:01
Machine Learning - Thoery/Graph Representation Learning

Multi-relational graph 설명 (Heterogeneous graph란?, Multiplex graph란?)

그래프는 노드의 집합 V와 이들의 관계를 나타내는 엣지의 집합 E로 정의한다. 그래프의 엣지에 방향성이 없다면 이를 undirected graph, 방향성이 있다면 directed graph, 엣지에 weight가 있다면 weighted graph라고 부르는 등 graph에는 다양한 종류들이 있다. 이번 포스팅에서는 multi-relational graph, 그리고 그 대표적인 종류 중 하나인 heterogeneous graph와 multiplex graph에 대해 알아보겠다. Multi-relational graph Multi-relational graph는 edge가 특정한 type을 가지고 있는 그래프를 의미한다. 예를 들어, 인스타그램 속 사람들의 관계를 나타내는 그래프가 있다고 하자. 이 관계에..

2021. 11. 1. 21:51
Machine Learning - Thoery

Forward KL Divergence과 Reverse KL Divergence 설명 (Inclusive KL과 exclusive KL)

이번 포스팅에서는 저번 KL divergence 글에 이어, forward KL과 reverse KL이 무엇인지에 대해 설명하겠다. Forward KL Forward KL(inclusive KL)은 아래와 같이 정의한다. 이는 기존에 우리가 알던 KL divergence의 형태와 같다. 이 Forward KL을 최소화하는 q를 찾는 과정을 우리는 M-projection 혹은 moment projection이라고 부른다. 그렇다면 우리는 이 forward KL을 어떻게 해석할 수 있을까? 이를 해석하기 위해 전체 x 값을 p(x)=0인 구간과 p(x)>0인 구간으로 분류한다. p(x)=0 p(x)가 0인 구간에 대해서 우리는 KL divergence를 고려할 필요가 없다. 왜냐하면, KL divergenc..

2021. 10. 27. 19:48
Machine Learning - Thoery

KL divergence 설명 (Relative entropy 설명, KL divergence와 MLE)

KL divergence는 어떤 분포 p, q가 있을 때, 우리는 이들이 얼마나 비슷한 분포인지를 표현하는 measure로, 분포의 entropy와 비교하는 분포 간의 cross entropy 값을 반영한다. 이번 포스팅에서는 확률 분포 사이의 divergence measure 중 하나인 KL divergence(Relative entropy)에 대해 알아보겠다. 정의 분포가 discrete할 때, KL divergence는 아래와 같이 정의할 수 있다. 분포가 연속일 때는 KL divergence를 아래와 같이 정의한다. 해석 위의 식이 가지는 의미는 무엇일까? 위 식의 log를 풀어서 써 보면 아래와 같은 식으로 표현할 수 있다. 이 식에서 우리는 앞에 있는 plog(p) 값이 p의 entropy를,..

2021. 10. 27. 19:26
Machine Learning - Thoery

Proper scoring rule 설명 (proper scoring rule이란?, Brier score 설명)

머신 러닝 혹은 딥러닝의 궁극적인 목적은 loss function을 최소화하는 parameter를 찾는 것이다. 이 loss function에는 다양한 종류가 있다. 이 예시로는 discrete한 예측 label을 가지는 classification problem에서 사용되는 예측이 맞았을 때는 loss를 0으로 그리고 틀렸을 때는 1로 계산하는 zero-one loss부터 continuous한 예측 값을 가지는 regression problem에서 사용되는 l2 loss, l1 loss, huber loss 등 다양한 것이 있다. 이외에도 true probability distribution에 대해서 이에 맞는 probability distribution을 예측하는 probabilistic predict..

2021. 10. 5. 21:13
Machine Learning - Thoery/Probability & Statistics

Method of Moments 설명 (MOM이란?)

우리는 어떤 데이터에 대한 parameter를 추정하고 싶을 때, Maximum Liklihood Estimation 혹은 MAP Estimation 등의 방법을 주로 사용한다. 이외에도 Empirical Risk Minimization(ERM), Method of Moments(MOM) 등 parameter를 추정하는 다양한 방법들이 존재한다. 이번 포스팅에서는 그 중에서도 log likelihood의 미분이 힘들어 MLE를 계산하기가 어려운 상황일 때에 사용하는 방법인 Method of Moments에 대해서 알아보겠다. 정의 MOM은 이론적으로 계산한 moment 값인 theoretical moment와 실제 moment 값인 empirical moment의 차이가 최소화되는 방향으로 paramet..

2021. 9. 13. 19:54
Machine Learning - Thoery/Probability & Statistics

Empirical risk minimization 설명 (ERM이란?)

우리는 어떤 데이터에 대한 parameter를 추정하고 싶을 때, 주로 Maximum Likelihood Estimation 혹은 MAP Estimation을 사용한다. 하지만 이외에도 MOM(Method of Moments), ERM(Empirical Risk Minimization) 등 parameter를 추정하는데에 쓰이는 다양한 방법들이 존재한다. 이번 포스팅에서는 그 중에서도 MLE를 일반화하여 표현한 방법인 Emprical Risk Minimization이 무엇인지에 대해 알아보겠다. 정의 Empirical Risk Minimization은 loss function이 어떤 형태이든 적용할 수 있는 방법으로, 이 방법에서는 loss function을 아래 식과 같이 정의한다. 위 식에서 l(y_..

2021. 9. 9. 22:48
Machine Learning - Thoery/Probability & Statistics

Exponential Family 설명 (지수족이란?)

통계학이나 머신 러닝 공부를 하다 보면 exponential family라는 단어를 종종 접할 수 있다. 이번 포스팅에서는 exponential family가 무엇인지에 대해 알아보고, 이 예시에는 어떤 것이 있는지 알아보겠다. 정의 y를 random variable, eta를 parameter라고 할 때 Exponential family는 아래와 같은 형태로 표현될 수 있는 분포를 의미한다. 여기서 우리는 h(y)를 scaling constant 혹은 base measure, T(y)를 sufficient statistics, eta를 natural parameter, Z(eta)를 p(y|eta)의 합을 1로 만들어주는 normalization constant인 partition function, A..

2021. 9. 4. 18:49
Machine Learning - Thoery

Mutual Information이란? (상호의존정보란?, Normalized Mutual Information, Maximal Information Coefficient)

어떤 random variable들 X, Y가 있을 때, 우리는 이들이 어떤 관계인지를 궁금해 할 수 있다. 이를 위해 우리는 각 random variable들의 확률 분포가 주어져 있다면 KL divergence를 활용해 이들이 얼마나 비슷한지를 관찰하기도 하고, X, Y의 correlation coefficient를 구하기도 한다. 이번 글에서는 하나의 random variable이 다른 random variable에 얼마나 dependent한지를 나타내는 지표인 mutual information(MI)에 대해서 설명해볼 것이다. 배경 (Correlation의 한계) 서로 다른 두 random variable의 관계를 알고 싶다면, 가장 먼저 우리는 correlation을 계산해볼 수 있을 것이다. ..

2021. 9. 1. 20:41
Process Mining - Tools/pm4py

PM4Py 시작하기 (PM4Py tutorial)

* 이 글은 PM4Py version 2.2.7.1을 기준으로 작성되었습니다. 이 글은 파이썬에 대한 기본 지식 및 프로세스 마이닝의 기본 용어에 대한 지식이 있다는 가정 하에 진행됩니다. 대부분의 PM4Py 포스팅이 2019년에 작성되었고, 2년이라는 시간 동안 PM4Py의 버전이 1이나 올라버렸다. 그래서 PM4Py 버전 2에 맞는 포스팅들을 다시 하나하나 작성하려고 한다. (PM4Py 설치는 다음 포스팅을 참고한다.) 이번 포스팅에서는 PM4Py를 사용해서 프로세스마이닝 분석을 하려면 어떤 흐름으로 분석을 진행해야 하는지에 대해 간략하게 알아보고자 한다. 각 기능들에 대한 세부 포스팅은 차후에 진행하겠다. Library 및 모듈 import import statistics import pm4py i..

2021. 5. 16. 17:16
Process Mining - Tools/pm4py

PM4Py로 BPMN 모델 프로세스 분석하는 법 (python으로 BPMN import 및 export)

BPMN(Business Process Modeling Notation)은 아주 간단하게 프로세스 모델을 표현할 수 있는 모델링 방법으로, 오늘날 비즈니스 프로세스를 모델링할 때에 가장 널리 쓰이는 언어 중 하나이다. 이번 포스팅에서는 BPMN을 프로세스 마이닝 패키지인 pm4py를 활용하여 import하고 export하는 방법에 대해 알아보겠다. * 이 포스팅은 pm4py version 2.1.4를 기준으로 작성되었다. (얼마나 오래 공부를 안 한거여... 버전 1이 올랐네... :( ) Import 우선, BPMN 파일을 pm4py를 활용하여 python에서 import하는 방법을 알아보겠다. 1. 다음 코드를 입력한다. import pm4py from pm4py.visualization.bpmn i..

2021. 3. 3. 00:13
Machine Learning - Thoery

RFE와 RFECV (Recursive Feature Elimination이란?)

데이터 분석에 드는 노력의 80%, 어쩌면 그 이상은 모델링이 아닌 데이터의 특성을 파악하는 EDA, missing value를 처리하는 등의 정제 작업을 진행하는 데이터 전처리, 좋은 모델링을 위해 적절한 feature를 선택하는 feature selection의 데이터 그 자체의 특성을 파악하고 이를 정제하는 데에 소요된다. 이번 포스팅에서는 feature selection의 한 방법인 RFE (Recursive Feature Elimination)와 RFECV(Recursive Feature Elimination with Cross Validation)에 대해 알아볼 것이다. Feature Selection 먼저, feature selection이 무엇인지에 대해 간략하게 설명하겠다. 우리는 데이터..

2021. 3. 1. 18:13