퀠로맨 블로그

들어가면서

다양한 자료 구조 (특히 회로)들은 그래프로 표현하는 것이 직관적으로 더 좋고 성능도 더 잘 나온 것으로 알려져서 스탠포드에서 graph representation leraning 강의가 올라와 있어서 이를 공부하며서 정리하고자 한다.

https://web.stanford.edu/class/cs224w/index.html

왜 그래프를 사용해야 하는가?

기존의 Machine learning 및 Deep learning의 경우 grid(image), sequence(text나 audio) 형태의 input만 주로 활용했지만 세상에는 grid, sequence로 표현되지 않는 것도 많다.

그래프는 relation, interaction을 표현하기 좋은 수단으로 더 나은 prediction 결과를 낼 수 있다.

그래프 표현의 예

그래프를 활용한 Neural Network의 모습

그래프를 가지고 할 수 있는 task들

• Node classification: 특정 노드가 어떤 특징(feature)를 가지고 있는지 예측 (online user/item categorization)
• Link prediction: 두 노드간 link가 있을 것인지 없을 건인지 관계를 에측 (Knowledge graph completion, recommendation system, drug side effect prediction)
• graph classification: 그래프가 어떤 property를 가질 것인지 구분 (molecule/drug property prediction)
• clustering: 특정 sub-graph를 찾아낸다. (social circle prediction, traffic prediction)
• graph generation: 특정 조건을 만족하도록 새로운 그래프를 생성 (Drug discovery)
• graph evolution: 그래프가 어떻게 변화해 갈 것인지 예측 (physical simulation)

그래프의 구성 요소

Node, Edge, Graph

그래프를 표현하는 방법들

(1) Adjacency matrix

각 노드에 index를 부여하고 index의 개수만큼 row와 column을 가지는 매트릭스를 만든다.

- undirected graph일 경우 adjacency matrix는 symmetric하다.

- 만약 edge에 가중치를 준다면 1이 아닌 다른 숫자를 넣으면 된다.

성질

1. row (혹은  column) 값을 다 더하면 해당 노드의 degree가 된다.

$$ k_i = \sum_{j}^{N}A_{ij} $$

보통 node의 개수에 비해 edge의 개수가 훨씬 적으므로 "sparse matrix"가 된다 => memory, computation에서 손해

(2) Edge list

(따로 떨어져 있는 노드 없이 노드들이 모두 연결되어 있다는 가정 하에) edge들의 list만으로 그래프를 표현할 수 있다.

ex: [(1,2), (2,3), (1,3), (3,4)]

(3) Adjacency list

각 노드들의 neighbor들을 표기해준다.

1: 2,3

2: 1,3

3:, 1,2,4

4: 3

다양한 그래프들

• Directed Vs. Undirected: edge에 방향성이 있나 없나
• Heterogenous graph G = (V, E, R, T)
• Bipartite graph: 노드가 두 그룹 (U, V)로 나뉘어져 edge가 같은 그룹내에서는 없고, 서로 다른 두 그룹 사이에만 존재 (user와 iterm, actors & movies
• weighted vs unweighted
• self-edge를 허용할 것인가? multiple edge를 허용할 것인가?

https://interconnected.blog/romance-of-three-kingdoms-semiconductor-x86-arm-riscv-intel/

위 글을 보면서 알게 됐는데 삼국지는 (정확히는 삼국연의) 영어로 Romance of the three kingdoms다.

서양 사람들은 위, 촉, 오의 어떤 점을 romance라고 생각한걸까?

참고로 실제 소설이 아닌 역사를 기록한 삼국지는 Records of three kingdoms라고 불린다.

여러가지 운동을 하는데 어깨의 가동성이 너무 안좋고 자고 일어나서 승모가 너무 뻣뻣한 느낌이어서 재활 운동을 실시하려고 써본다.

레퍼런스

원인

책상 생활: 머리가 앞으로 쏠려서 중심을 잡기 위해 등이 뒤로 굽고, 자연스럽게 어깨는 앞으로 말린다.

해결책

결국에는 가슴 스트레칭 + 등 근육 강화 (특히 견갑을 잡아주는 하부 승모)

교정 운동

• 마사지 볼과 벽을 이용해서 소흉근과 대흉근 스트레칭
• 한팔씩 혹은 양팔 전부 L자로 만들어서 가슴 스트레칭
• 흉추 스트레칭
  • 팔꿈치로
  • 폼롤러 가로 and 세로
• 흉추 회전
• 바닥에서 Y운동 (버티기)
• 바닥에서 and 벽에서 W운동

이번에는 스트레칭을 너무 분산하지 말고 재활운동 하듯이 라운드 숄더에만 집중해보자.

책상에서 업무를 할 때도 항상 등을 기대지 말고 머리와 가슴, 등을 일자로 만드는 것에 신경 쓰도록.

넷플릭스를 보다가 알게 됐는데

흔히 조난시 구조 요청 신호로 보내는 SOS는 아무 의미가 없다.

그저 가장 주고 받기 쉬운 모스 부호이다. (・・・ −−− ・・・)

왜 RNN이 필요한가?

순서가 의미를 부여하는 데이터를 Sequence 라고 부른다. 다시 말하면 하나의 input이 하나의 output을 만들어 내기보다는 input 하나하나가 쌓여 output을 만들게 된다.

특히, 이렇게 순서가 중요한 데이터들 중 시간에 따른 의미가 존재하는 데이터를 시계열 (time series)이라 부른다. (예: 주식 가격 데이터)

예: 다음 스펠링 예측

예를 들어 사용자가 triangle이라는 단어를 입력하고 싶다고 해보자. 그러면 사용자는 차례대로 키보드를 통해 t, r i, a, n, g, l, e라는 글자를 타이핑할 것이다. 그리고 결국에 우리가 하고 싶은 것은 사용자가 전부 스펠링을 치기 전에 triangle이라는 단어를 예측하고 차례대로 출력해야 한다.

그러기 위해서는 사용자가 n을 치고 있을 때, 그전에 차례대로 입력한 t,r,i,a를 알고 있어야 한다.

이렇듯 언어 처리는 전반적으로 이전의 데이터들이 context가 되기 때문에 비슷한 방식으로 처리 해야한다. (단어 자동 완성, 다음 단어 예측)

즉, 순서가 중요한 데이터들을 처리하기 위해서는 기존의 Neural Network와는 다르게 메모리를 가지고 있어 이전 입력값이 현재의 출력에 영향을 주어야 한다.

RNN의 구조

정말 간단한 구조의 MLP(Multi layer Perception)과 RNN을 비교해 보자.

가장 큰 차이점은 새로 그려진 hidden layer 자기 자신으로 다시 들어가는 화살표이다. 이 화살표들은 이전에 hidden layer에서 계산된 결과값들이 다음 버너 hidden layer의 결과값 계산에 쓰인다는 이야기이다. 즉, MLP와는 다르게 hidden layer의 결과값(t=n)을 계산하기 위해서는 새로운 input(t=n)과 더불어 hidden layer의 이전 결과값(t=n-1)이 필요하다.

예: 'name'이라는 단어의 스펠링 예측하기

우리는 RNN을 통해 name이라는 단어의 스펠링을 예측하도록 만들것이다.name이라는 스펠링을 예측한 다는 것은 n을 타이핑 했을 때, a를 예측해야 하고, a를 타이핑 했을 때는 m, m을 타이핑 했을 때는 e를 예측해야 한다.

위의 그림은 hidden layer가 2개인 RNN의 구조이다. 보이다시피 파란색 화살표를 통해 이전 시점의 값을 현재 시점의 값을 계산하는데 사용하게 된다.

위의 RNN을 식으로 풀어 써보면 다음과 같다. (w는 weight, b는 bias이고 activation functino으로 tanh를 사용하였다.)

위의 RNN 구조를 시점 별로 풀어서 나타내면 다음과 같다. (여기서 또한 이전의 값을 사용하게 되는 걸 파란색 화살표로 표시하였다.)

output을 처음 계산할 때에는(t=0) hidden layer들의 이전 값들이 없기 때문에 적당한 값을 initial value로 지정해준다. (h1(-1), h2(-1))

RNN의 트레이닝 과정

기본적으로 트레이닝 과정은 MLP의 트레이닝 과정과 비슷하다.

특정 input에 대해 기대하는 정답 output(Label)이 정해져 있다. (n→a, a→m, m→e) 즉, 3개의 input에 대해 3개의 label이 있고, label과 output의 차이를 가지고 loss function을 만들어 gradient descent를 이용하여 weight와 bias들을 업데이트하게 된다.

다만 큰 차이점이라고 한다면 특정 시점의 output을 계산할 때, 그 이전 시점예 계산됐던 값이 필요하다는 점이다. 예를 들어 w22를 업데이트 하고 싶다고 하면 우리는 다음을 구해야 한다.

예를 들어 w22를 구하기 위해서는 h2의 이전 값(h2(t-1))을 알아야 하고, 또 h2(t-1)을 구하기 위해서는 h2(t-2)를 구해야 할 것이다. 이처럼 back propagation이 layer의 앞쪽 방향으로만 가는게 아니라 시점도 앞으로 가게 된다. 이를 Back Propagation Through Time (BPTT)라고 한다. 화살표가 좌에서 우로 가는 것뿐만 아니라 위에서 아래로도 내려온다는 것을 생각하면 된다.

RNN의 한계

time sequence가 늘어나면 back prop시에 미분값이 0과 1 사이의 값이 여러번 곱해져서 기울기가 소멸한다. 따라서 트레이닝이 되질 않는다. (gradient vanishing)

⇒ LSTM이나 GRU를 사용한다.