퀠로맨 블로그

Heterogeneous Graph

기존 graph는 edge와 node로만 표현이 된다. G = (V, E)

Heterogeneous graph는 기존의 graph와는 달리 node와 edge(relation)의 type이 있다.

따라서 G = (V, E, R, T)로 표현된다.

특이한 점은 이제 edge가 (v_i, r, v_j), 즉, relation type이 추가되었다는 점이다.

(사실 relation의 방향성 또한 추가되었으니 유의하자.)

아래는 다양한 Heterogenous graph의 예시이다.

Relational GCN

Heterogenous에 GCN을 적용하려면 기존의 GCN을 어떻게 확장해야 할까?

기존의 GCN에서는 다음과 같이 GCN layer당 하나의 weight matrix를 공유해서 사용한다.

Relational GCN의 경우에는 relation type에 따라 다른 weight matrix를 사용한다.

수식으로 표현하면 다음과 같다.

Relational GCN의 Scalability issue

Relational GCN에서 relation마다 서로 다른 weight matrix를 쓴다는 것을 알았다.

이 때 문제가 될 수 있는 것은 relation이 엄청나게 많은 graph도 있기 때문에 weight가 어마어마하게 많아진다는 것이다.

이를 해결하기 위해 2가지 방법이 쓰인다.

(1) Use Block dignoal matrices: 거대한 matrix 중 diagonal 근처 부분만 block으로 묶어서 사용. 멀리 있는 node끼리는 interaction하지 못한다는 단점이 있다.

(2) Basis Learning: Matrix를 다 새로 만드는 것이 아니라 Basis가 되는 vector들을 만들고 vector들의 조합으로 relation마다 weight matrix를 만든다.

Heterogenous graph에서의 Link Prediction

지난 link prediction에서 배웠듯이 message edge와 supervision edge를 나누고, 이를 또 training, validation, test edge로 바꿔서 차례대로 사용하는 edge들을 늘려가면서 training에 활용했다.

Heterogenous graph에서는 relation type별로 학습을 시켜야 하므로 이보다는 복잡하다.

(일단 당장 쓰이는 것이 아니므로 생략하도록 하겠다. 필요하면 슬라이드를 보자.)

Knowledge graph

Knowledge graph란 heterogenous graph의 한 예로 그래프 형태로 설명하는 것이다.

node들은 entity가 되고, node마다 type이 있다. 또한 node들끼리 다른 종류의 relationship으로 연결되어 있다.

다음은 knowledge graph의 예제로 medicine에 관한 예이다.

특정 약물이 어떤 질병에 효과가 있고, 어떤 부작용을 만드는지, 부작용은 어떤 단백질에 의해 일어나는지 등에 대해 그래프의 형태로 표현하고 있다.

위와같이 Knowledge graph는 백만개 이상의 node와 edge 들로 구성되어 있어 크기가 크지만 많은 부분이 Incomplete이기 때문에 우리가 그러한 부분을 채우는 것이 주요 task 중 하나이다.

Knowledge graph Completion Task

(head, relation)이 주어졌을 때 어떻게 tail을 유추할 것인가?

-> (h, r)의 embedding을 구하면 (t)의 embedding과 유사한 값이 나와야 한다.

(1) 어떻게 embedding을 만들 것이고

(2) 어떻게 유사한지를 판단할 것인가?

TransE: 벡터 h와 벡터 r의 합으로 t를 알아낸다.

TransR: Relation마다 벡터 h를 다른 임베딩 스페이스로 매핑해주는 M matrix가 존재하고 거기서 벡터의 합으로 나타낸다.

DisMult: h, r, t의 inner product를 가지고 계사한다.

ComplEx: DisMult인데 complex conjugate를 사용해서 확장.

다음과 같은 relation들을 표현할 수 있어야 expressiveness가 크다고 할 수 있다.

슬라이드에서는 각각을 그림으로 설명하는데 요약하면 다음과 같다.

Decision Transformer를 배우기 위해 일단 Transformer부터 공부해 본다.

빛갓갓 동빈나 님이 체계적으로 잘 정리해주신 자료가 있어 덕분에 이해가 금방 되었다.

https://youtu.be/AA621UofTUA

동빈나님이 설명하신 동영상에 seq2seq 모델이 나오는데 이에 관한 내용은 미리 다음 자료로 공부했었기 때문에 바로 이해할 수 있었다.

https://wikidocs.net/24996

트랜스포머의 핵심 구조 익히기

트랜스포머는 일반적인 언어 모델처럼 Encoder와 Decoder로 구성되어 있다. Encoder는 여러 layer의 반복으로 이루어져 있고, Decoder 또한 여러 layer의 반복으로 이루어져 있다.

Encoder, Decoder를 이루고 있는 단위 layer에는 Self-attention layer라는 것이 들어가는데 이를 잠시 뒤에 자세히 살펴볼 것이다.

이 외에도 Positional Encoding이라는 것이 들어가는데 이것도 나중에 설명이 될 것이다.

언어 모델이기 때문에 Input을 Output으로 translate해준다.

이 때, Input은 문장이고, 문장을 구성하는 각각의 단어들을 Input Embedding layer를 통해 특정 길이의 Embedding으로 변환된다.

그리고 단위 레이어를 지나면서 인풋과 똑같은 크기의 아웃풋 데이터가 나오게 된다.

오른쪽 그림을 보면 알겠지만 Input이 그대로 Output으로 연결되는 Residual connection 또한 가지고 있다.

인코더의 마지막 레이어에서 나온 아웃풋을 모든 디코더 레이어에서 어텐션 메카니즘에 사용하기 위해 인풋으로 넣어준다.

Attention mechanism

트랜스포머를 설명할 때 attention mechanism을 빼놓을 수 없다.

attention mechanism이라는 것은 문장을 구성하고 있는 각 단어(혹은 토큰)들이 문장 내의 다른 단어와 얼마나 연관성이 있는지를 계산하여 가중치로 만들어서 각 단어들의 임베딩을 조합해서 최종 임베딩을 만드는 것이다.

예를 들면 I am a boy라는 문장이 있고, 이를 단어로 쪼개면 ["I", "am", "a", "boy"]이다.

"I"라는 단어의 임베딩 출력을 구하기 위해서는 I와 다른 단어와의 유사성을 찾게 되는데 이 유사성이 [0.7, 0.05, 0.05, 0.2]로 나온다고 하면 임베딩 출력은 각 단어들의 임베딩에 위의 유사성 숫자를 가중치로 곱해준 값들의 합이 되게 된다.

트랜스포머는 이를 Query (Q), Key (K), Value (V)라는 개념으로 설명한다.

하나의 Q에 해당하는 임베딩을 찾기 위해 각 K와의 유사성을 MatMul을 이용해서 체크한다.

그리고 이를 통해 가중치 (energy라고 표현하더라)를 구하고 가중치만큼 Value를 더해줘서 최종적인 Q의 임베딩을 만들어 낸다.

attention mechanism은 seq2seq 모델에도 나오는데 트랜스포머에서는 "self-attention"이라는 것이 중요하다.

즉, attention을 만들 때 자기 정보만 가지고 만든다는 것이다.

seq2seq 모델을 기억해보면 decoder의 attention 정보를 만들기 위해 encoder의 정보를 활용해서 가중치를 만든다.

트랜스포머의 인코더에서는 Q, K, V가 같은 문장에서 다 나오게 된다.

V, K, Q를 직접 쓰는 것이 아니라 MLP layer를 거쳐서 만들어낸 값을 활용하는데, h개 만큼의 MLP layer를 병렬로 사용해서 다양한 attention을 만들고 임베딩을 만들어서 이를 조합해서 사용한다.

좀더 과정을 자세히 살펴보면 다음과 같다.

일단 한 단어의 임베딩을 가지고 Query, Key, Value를 다 만들 것이다.

나중에 여러 head를 concat해서 사용할 것이기 때문에 embedding의 길이를 head의 개수로 나눈 vector 길이로 나오게 된다.

그렇게 만들어진 Q, K, V를 가지고 Attention을 구한다.

Q,K는 Matrix multiplication을 통해 (dot product처럼) 유사도를 구하고 거기에 Value를 곱한다.

dk로 Normalize하는 이유는 backprob을 위해 softmax의 gradient가 큰 지점에 위치시키기 위함이다.

위에서는 하나의 단어에 대해서만 Attention을 만들었지만 사실 여러개의 단어를 동시에 만들게 된다.

embedding matrix와 attention energy matrix를 곱해서 최종 attention을 구해주게 되는데 임의로 attention energy matrix에 마스크 행렬을 곱해서 특정 단어와의 연관성을 없앨 수도 있다.

(이는 Decoder에서 쓰이게 되는데 Decoder에서는 단어를 전부 참조하는 것이 아니라 이미 나온 단어들만 참조하게 만들고 싶기 때문에 미래의 단어들을 참조하는 attention은 마스킹하게 된다.)

위에서 말했듯이 Multi-head attention이기 때문에 각 head에서 나온 attention들을 concat하고 MLP를 통해서 최종 출력을 만든다.

Positional Encoding

트랜스포머는 RNN이나 LSTM을 활용하는 Seq2Seq 모델처럼 단어를 순차적으로 받는 것이 아니라 문장이 한꺼번에 들어간다.

따라서 단어의 위치 정보를 넣어줘야 하는데 이를 하기 위해 Positional Encoding이라는 것을 활용한다.

식은 다음과 같다.

임베딩의 size와 position을 늘리면 다음과 같이 나온다.

이 챕터에서는 GNN이 그래프 안의 노드들을 얼마나 잘 구별하여 노드 임베딩을 만들어줄 수 있는지 이론적으로 알아보는 시간이다.

이 챕터를 다 배우게 되면 어떤 GNN 구조가 가장 expressive power가 좋은지 알게 될 것이다.

GNN은 어떻게 노드를 구별할까?

node들에 따로 id 같은 feature가 없다고 할 때 graph structure만 가지고 노드들을 얼마나 잘 구별할 수 있을까?

위와 같은 구조를 보면 1,2,3,4,5는 노드 피쳐가 없다. 즉, 구별할 수 없는 노드이기 때문에 노드가 그래프 내에 어디에 달려있는지 그 위치 만으로 구별해야 한다.

직관적으로 봤을 때, 1번 노드와 2번 노드는 같게 취급이 될 것이라는 걸 알 수 있다.

노드가 구별하기 위해서는 각 노드별로 만들어지는 computational graph의 구조가 달라야 한다.
1번, 2번 노드의 computational graph를 아래와 같이 그렸을 때 둘의 구조가 정확히 일치하는 것을 알 수 있다.

(노드 번호가 다른 것은 ID가 노드 피쳐로 들어가지 않았으므로 실제로는 구별할 수 없다.)

아래와 같이 모든 노드들에 대해 computational graph(rooted subgraph structure)를 그려봤을 때 서로 다른 computational graph를 가진 노드들만이 서로 다른 임베딩을 갖게 된다.

결국 GNN의 역할은 computational graph를 임베딩으로 매핑하게 되는데,

다른 computational graph는 다른 embedding이 나오기 위해서는 매핑이 "injective" 해야 한다.

그리고 매핑이 injective하기 위해서는 computational graph의 내부 과정인 neighbor aggregation 또한 injective 해야 한다.

GNN이 expressive하지 못할 때

위에서 GNN이 expressive하기 위해서는 neighbor aggregation이 injective해야 한다고 했다.

그렇다면 과연 어떤 neighbor aggregation이 좋을까?

(우리가 하는 neightbor aggregation의 대상은 multi-set이라고 할 수 있다. 여기서 multi-set은 같은 item이 반복될 수 있는 set을 말한다)

Mean pooling failure case (GCN)

Max pooling failure case (GraphSAGE)

The most expressive GNN - Graph Isomorphism Network (GIN)

GIN을 설명하기에 앞서 다음과 같은 두 개념을 알아두자.

Injective multi-set function

Universal Approximation Theorem

1개의 hidden layer를 가진 MLP가 충분히 크면 어떤 continuous function이던 임의의 정확도로 근사할 수 있다.

위 두개의 theorem에 따라 Injective한 aggregation function을 만들면 다음과 같다.

즉, injective한 동시에 MLP 파트들을 잘 학습시켜서 뒤이어 나오는 downstream task 또한 잘 수행될 수 있도록 학습시킬 수 있다.

GIN과 WL Graph Kernel의 유사성

우리는 챕터2에서 그래프를 구별할 수 있는 WL Graph Kernel에 대해 배웠다.

WL Graph Kernel도 주변 노드에서 정보를 합친 뒤 (sum) Hash를 통해 새로운 ID로 매핑한다.

이는 GIN이 하는 일과 굉장히 유사한데 K-step의 GIN operation을 반복하면 K-hop neighborhood 구조를 summarize하는 것과 같은 효과이다.

Pooling의 expressive power 순위

1. Sum (GIN) - multiset 구별 가능

2. Mean (GCN) - distribution 구별 가능

3. Max (GraphSAGE) - set 구별 가능

Level 별 prediction task 방법

Question: GNN을 통해 Node Embedding을 얻고 나서 실제 Task는 어떻게 수행할 것인가?

--> 각 레벨 별로 어떤 식으로 task를 수행할 수 있는지 알아보자.

(아래에서는 prediction head를 가지고 어떻게 활용할 수 있는지 알아보는 것이라 할 수 있다.)

Level	방법
Node-level	- 노드 임베딩에 웨이트를 곱해서 바로 prediction!
Edge-level	- 두 노드 임베딩을 concat한 뒤 MLP 적용! - 두 노드 임베딩을 dot-product  1- way: 바로 product k-way: 가운데 여러개의 Weight를 시도한 뒤 Concat해서 만든다.
Graph-level	노드 임베딩을 aggregation처럼 모아주는 operator를 활용해서 예측에 사용한다. NOTE: 위의 global pooling method들 같은 경우 서로 다른 노드 임베딩이 같은 결과를 나타낼 때도 있기 때문에 다른 방법이 필요하다. 아래 예제에서도 sum pooling을 하게 되면 node feature들의 절대값들이 달라도 결과가 같아지게 되는 문제가 생긴다.

DiffPool (Hierarchical Pooling)

위의 그림처럼 원본 그래프를 점점 더 작은 그래프로 바꾼 다음 graph embedding을 구하게 된다.

각 단계별로

1. 노드 임베딩을 구하고

2. 주어진 노드 임베딩을 가지고 클러스터링을 한뒤

3. 클러스터링 별로 pooling을 적용하여 다음 스테이지를 위한 single node를 만든다.

Supervised Vs Unsupervised Tasks

그래프를 가지고 할 수 있는 task 중에 supervised와 unsupervised가 있다.

아래 표를 보면 알겠지만 unsupervised 같은 경우는 그래프의 구조 자체를 활용한다.

Loss function for supervised learning

- Classification task: Cross entropy loss를 활용한다. (아래 cross entropy는 K개의 data가 있을 때를 의미한다.)

- Regression task: L2 error (Mean Square error)를 활용한다.)

Evaluation Metric

- Classification task

Multi-class classification의 경우

 --> accuracy를 측정 전체 중 정확하게 예측한 것은 몇개인가?

Binary classification의 경우

--> Confusion matrix를 활용

Accuracy: 전체 중 맞춘 것은 무엇인가? (TP + TN) / (TP + TF + FP + FN)

Precision: True라고 예측한 것 중에 진짜 True의 비율(얼마나 오진을 했냐) (TP) / (TP + FP)

Recall: 모든 True들 중 True라고 예측한 것의 비율(얼마나 진짜 True를 빼먹지 않았냐) (TP) / (TP + FN)

어떤걸 예측한다고 했을 때, False의 비율이 굉장히 낫다고 하자.

그러면 무지성으로 True로 예측하면 왠만하면 Accuracy, Precision, Recall이 모두 높게 나올 것이다.

그래서 다음과 같은 개념이 등장한다.

ROC (Receiver operating characteristic) curve and AUC (Area under Curve)

Binary classification에서 threshold를 바꾸면 TPR과 FPR이 바뀌게 된다.

우리의 목표는 FPR이 0이 되고, TPR이 1이 되게 만드는 것이다. (최대한 왼쪽 위)

threshold가 1이면 아무것도 positive가 안될 것이므로 TP=0, FP=0이어서 (FPR,TPR)=(0,0)에 있을 것이고

threshold가 0이면 모든 것이 positive가 될 것이므로 (FPR,TPR)~(1,1)에 있을 것이다.

우리는 최대한 curve 자체도 왼쪽 위로 넓어지기를 원하고 (AUC)

그 중 가장 왼쪽 위에 있는 point를 통해 threshold를 고를 것이다.

- Regression:

Root Mean Square Error(RMSE)

 Mean Absolute Error(MAE)

Split data (train, validation, test set)

일단 random하게 split하고 여러번의 학습 결과를 평균을 내야 한다.

그렇다면 어떻게 random하게 split해야 할까?

Link Prediction example

Link prediction에서는 edge를 감춰서 학습에 쓰일 edge는 message passing edge, 실제 존재하는지 맞춰야하는 edge를 supervision edge로 나눈다.

Inductive setting에서는 단순히 그래프를 나눠서 하면 되지만 아래와 같은 Transductive setting은 약간 tricky하다.

(1) Transductive setting에서는 그래프를 세 개로 세트로 나눈 뒤 그 안에서 message passing edge, supervision edge로 나눈다.

(2) Training 단계에서는 Training message passing edge와 Training supervision edge로 학습한다.

(3) Validation 단계에서는 Training message passing edge + training supervision edge로 validation supervision edge를 예측한다.

(4) Test 단계에서는 Training message passing edge + training supervision edge + Validation supervision edge로 test supervision edge를 예측한다.

참고: 원래 Transductive setting이라면 모든 단계에서 전체 graph structure를 이용해야 하기 때문에 모든 edge를 이용해야 하지만 edge 자체가 각 단계에서 prediction의 대상이 되기 때문에 점진적으로 더 넣어주게 되는 것이다.

* feature augmentation

(사실 이 부분은 정작 중요한 부분이 아닌데 8단원 강의의 첫부분에 나온게 이상하긴 하다)

때로는 feature가 부족하거나 아무것도 없을 때는 임의로 feature를 넣기도 한다.

Feature augmentation 방법	Constant 1을 집어넣기	Node ID를 One-hot으로 집어넣기
특징	- expressive power는 낮다. (graph의 구조에 대해서만 배운다.) - computation cost가 적다. - 그래프가 더 커져도 적용이 가능하다. (단순히 1만 추가하면 되므로)	- expressive power는 높다 (각각의 node에 대해서 배울 수 있다.) - Computation cost가 크다. (one-hot vector 크기가 크므로) - 새로운 노드에는 적용이 불가능하다. (one-hot vector의 크기가 정해져 있으므로 노드가 늘어나면 새로 vector 크기를 정의해야 한다.
설명

때로는 computation graph로는 배울 수 없는 feature들도 있다.

--> 예: 특정 길이의 cycle의 수

이러한 구조적인 정보는 넣어주면 더 좋다. (degree, clustering coefficient, pagerank, centraility)

* Structure augmentation

Too Sparse할 경우	Too Dense할 경우
- biparate graph에서는 edge를 augment해서 한 논문을 같이 쓴 저자들을 묶어줄 수 있다. - 또는 모든 노드를 잇는 임의의 노드를 만들어서 아주 먼 노드를 이어줄 수 있다.	- Neightbor Node를 샘플링 해야 한다. --> computation cost와 missing node로부터의 important message 간의 trade-off

7.1. General GNN Framework

GNN에서 신경써야 할 것들은 다음과 같다.

1. Message: Node embedding에서 Message를 어떻게 만들 것인가

2. Aggregration: neighbor들의 Node embedding을 어떻게 모을 것인가

3. Layer connectivity: 1, 2를 가지고 만든 single layer들을 어떻게 연결할 것인가(예: skip connection을 쓸 것인가?)

4. Graph manipulation: node를 augmentation할 것인가?

5. Training objectives: supervised learning Vs. Unsupervised Learning, Node, Edge, Graph level...

7.2 Single Layer of GNN

GNN에서 하나의 layer는 다음과 같은 기능을 수행한다.

(1) Message transformation: 이전 node embedding을 변환하는 단계

(2) Message aggregation: neighbor들의 node embedding을 모으는 단계

(3) Activation: aggregation 이후에 nonlinearity를 추가하여 expressiveness를 늘린다.

여러가지 GNN을 Message + Aggregation 틀에 맞추어 설명해보자.

Graph Convolution Network (GCN)

node embedding에 linear transformation을 취하고, average를 취한다.

원래의 식은 위와 같으나 Message + Aggregation으로 나누어 표현하여 보자.

GraphSAGE

GCN과 GraphSAGE의 가장 큰 차이점은 GCN은 Node 자체의 embedding은 사용하지 않으나 GraphSAGE는 Node 자체의 embedding을 따로 transformation하고, Concat해서 사용한다는 점이다.

전체 식은 위와 같고, aggregation function은 다양하게 정할 수 있다. (Average, Pooling (Mean, Max), 심지어 LSTM으로 할 수도 있다.)

Message + Aggregation 형식으로 표현하면 다음과 같다.

(옵션) embedding의 크기를 맞춰주기 위해 l2 Normalization을 하면 성능이 좋아지기도 한다.

Graph Attention Network (GAT)

Graph Attention Network는 GraphSAGE보다는 GCN에 가깝다고 볼 수 있다.

GCN은 Average를 사용하므로 Sum을 할 때 각 Neighbor들의 중요도(weight)는 똑같이 1/degree라고 할 수 있다.

GAT에서는 각 node들의 중요도(weight)를 attention mechanism을 이용해 구한다.(Attention Weight)

Attention Mechanism은 자유롭게 정할 수 있는데 보통 두 노드의 임베딩을 Linear + Non-linear layer를 통해서 만들어낸다.

그런 뒤에 weight들의 크기를 맞춰주기 위해 softmax를 취한다.

Attention Mechanism과 Graph Neural Network는 동시에 학습된다.

하나의 attention mechanism이 잘 통하지 않는 경우도 있으니 여러개의 attention mechanism을 동시에 사용하고 aggregation하기도 한다.

다음과 같은 장점들이 있다고 한다.(아직 와닿지 않는다.)

- Computationally efficient

- Storage efficient

- Localized

- Inductive capability

Modern Deep learning Techniques

이 외에도 딥러닝에 쓰이는 테크닉들을 쓸 수 있다.

- Batch Norm: 노드들의 크기를 Normalize한다. (여기서 말하는 Batch는 무엇일까?)

- Dropout: Message Transformation의 Linear layer에 적용 가능

- Activation: 다양한 activation function 사용 가능

7.3 Stacking Layers of a GNN

이전 시간에 GNN layer 하나를 어떻게 구성하는지 배웠으니 이러한 layer들을 연결하는 법을 알아보자.

CNN과는 다르게 GNN에서는 layer의 개수가 반드시 더 많은 expressiveness를 의미하지 않는다.

다만, information을 얼마나 많은 hop에서 얻느냐를 말한다.

# of GNN layers = # of hops != expressiveness

over-smoothing problem

GNN layer를 너무 많이 사용하면 node embedding이 전부 비슷해지는 현상이 생기는데 이를 over-smoothing problem이라고 부른다.

이는 hop이 커지면 reception field가 커져서 결국에는 비슷한 노드를 사용하기 때문에 만들어지는 일이다.

아래 그림을 보면 3-hop만 지나도 그래프의 대부분의 node를 커버하게 된다.

따라서 다른 Deep learning과는 달리 GNN은 Layer를 늘리는 것이 반드시 좋은 것(expressiveness를 늘리는 것)은 아니다.

GNN Layer를 적게 쓰면서 expressiveness를 늘리는 방법은 다음과 같다.

(1) GNN layer 내의 linear layer를 늘리기 (예: message transformation에 쓰이는 MLP layer)

(2) GNN layer 들을 쓰기 전이나 후에 쓰는 MLP layer를 늘이기

혹은 GNN layer들에 skip connection을 사용하면 된다.

Skip connection은 node 자체의 정보를 보존하는데 큰 도움을 주기 때문에 receptive field가 커져도 node embedding이 비슷해지지 않도록 해준다. (Shallow network와 Deep network를 같이 쓰는 효과)

Skip connection은 activation function 전에 node embedding 자체를 더해줘서 만들 수 있다.

RL 코드를 작성하면서 최종적으로 성능을 판단해야될 때가 있다.

당연히 똑같은 실험을 여러번 하면 안되므로 환경과 agent가 랜덤하게 세팅되도록 설정해주어야 한다.

거꾸로 디버깅을 위해서는 최대한 재현이 가능하도록 random하지 않게 (deterministic하게) 만들어주는 것이 좋다.

환경 같은 경우에는 openAI gym을 활용하고 있다면 reset(seed[Int])를 통해 seed를 만들어 줄 수 있다.

똑같은 실험과 성능을 재현하고 싶다면 train할 때나, eval할 때나 고정된 seed값을 줘야 할 것이다.

torch에도 random seed를 주어야 하는데, torch.random을 활용할 때, sample할 때, weight를 initialize할 때 등 다양한 곳에 random seed가 쓰인다.

이 때는 torch.manual_seed(Int)를 활용하면 된다.

참고로 random seed는 각각 PRNG(Pseudo Random Number Generator)의 input으로 들어가게 되어서 우리가 random한 동작을 실행시킬 때 다른 숫자가 나오도록 한다.

seed를 넣지 않으면 특정 entropy(random source)에서 가져온다고 한다.

env 같은 경우 예를 들면 timestamp나 /dev/urandom을 읽어들인다고 한다.

""" Env """
def reset(
    self,
    *,
    seed: Optional[int] = None,
    options: Optional[dict] = None,
) -> Tuple[ObsType, dict]:

""" pytorch """
import torch
torch.manual_seed(0)

""" python """
import randomm
random.seed(0)

""" numpy """
import numpy as np
np.random.seed(0)

논문 정보

Ng, Andrew Y., Daishi Harada, and Stuart Russell. "Policy invariance under reward transformations: Theory and application to reward shaping." Icml. Vol. 99. 1999.

링크: http://luthuli.cs.uiuc.edu/~daf/courses/games/AIpapers/ml99-shaping.pdf

도입

이번에 공부하게 된 논문은 reward shaping에 관한 논문이다.

reward shaping이란 환경에서 얻을 수 있는 실제 reward를 사용하는 것이 아닌 다른 형태의 reward를 주어 agent 학습을 향상시키는 목적으로 쓰인다.

실제로 많은 환경들이 sparse reward (step마다 나오는 reward가 대부분 0)의 문제를 겪기 때문에 이러한 shaping은 빠른 학습을 도울 수 있다.

얼핏 봐서는 당연한 것 같은데 reward shaping을 하기 위해서는 반드시 생각해 봐야할 것이 있다.

"과연 reward shaping 없이 학습시킨 최적의 policy와 reward shaping을 사용하여 학습시킨 최적의 policy가 일치할 것인가?"

reward shaping이라는 것이 결국 환경에 임의의 조작을 가하여 학습을 향상시키는 것이다.

그런데 이 조작 때문에 우리가 배우고자 하는 최적의 policy가 아닌 다른 policy를 배우게 된다면 reward shaping을 하면 안될 것이다.

논문에서 잘못된 reward shaping의 예를 들어주는데 다음과 같다.

우리가 자전거를 타고  시작점에서 도착 지점까지 가면 reward를 얻는다고 하자.

그런데 도착지점 전에는 reward가 나오지 않으므로 우리가 임의로 다음과 같은 reward shaping을 했다고 가정해 보자.

"도착지점과 가까워지는 방향으로 움직이면 추가적인 reward를 얻는다."

그러면 agent가 배우게 되는 잘못된 policy 중 하나는 자전거를 타고 계속 같은 자리를 빙글빙글 도는 것이다.

그러면 한바퀴마다 도착지점에 가까워지는 움직임을 취할것이므로 도착지점에 도착하지 않고도 무한대로 reward를 얻을 수 있다.

따라서 이러한 잘못된 policy(논문에서는 bug라고 칭했다.)를 피하기 위해 논문에서는 다음과 같은 질문에 답을 해야 한다.

"어떤 reward shaping을 하면 original optimal policy와 같은 policy를 학습되도록 보장할 수 있는가?"

논문에서는 간단하게 말한다.

"Potential-based function을 더해주는 방식의 reward shaping을 하면 optimal policy가 동일하다."

위의 식에서 R'가 새로운 reward이고 R은 original reward이다.

추가적인 reward F를 통해서 학습에 도움을 줄 수 있다.

여기서 phi는 potential function으로 우리가 임의로 정할 수 있는 함수이다.

(단, potential은 state에만 영향을 받는 함수이다.)

일단, 이렇게 설정하면 위에서 나온 bug는 피할 수 있다.

왜냐하면 빙글빙글 돌 경우 계속 potential의 차이만큼 reward를 추가적으로 얻게 되는데 제자리에 오게 되면 이러한 추가적인 reward의 합이 0이 될 것이기 때문이다.

논문에서 보여주는 증명을 참고하면 기존의 Bellman Equation에 reward shaping부분을 더한 후,

새롭게 Q-function과 value-function을 정의하면 새로운 Bellman Equation을 만들 수 있다.

그리고 policy는 새로운 Bellman Equation에서 얻은 최대 Q값을 제공하는 action을 취하게 되는데

이 action이 기존 최대 Q값의 action과 일치하므로 (왜냐하면 Q값이 potential function만큼만 shift 됐기 때문이다.)

기존의 최적의 policy와 같게 된다.

Question: 이렇게 argmax로 action을 고르는 방식은 Q-learning에서 쓰이는 것인데 policy gradient에서도 적용할 수 있을까? (참고로 논문에서는 SARSA 알고리즘을 사용했다.)

그렇다면 어떤 potential function을 취하면 좋을까?

논문에서는 domain knowledge가 녹아들어간 임의의 potential function을 이용했다.

논문에서 나온 예제 중 한가지만 설명하자면 다음과 같다.

gridworld에서 시작점에서 도착지점까지 최단 거리로 가야하는 환경이 있다.(매 step마다 -1의 reward를 얻는다.)

이 때, 도착 지점과 가까우면 가까울수록 높은 potential이 있다고 정의했다.

즉, 도착 지점과의 manhattan distance를 이용해 potential을 만들었다.

여기서 추가적으로 매 step마다 20%의 확률로 원하지 않는 방향으로 이동하기 때문에 매 step마다 0.8씩 가게 되는 점까지 고려에 넣었다.

논문에서는 이 potential을 scale해서 비교해 보는 실험을 해보았는데 scale을 하더라도 reward shaping을 안한 경우보다 굉장히 좋은 성능을 보여주었다.

결론 및 느낀점

이 논문에서는 어떤 식으로 reward shaping을 해야 optimal policy를 바꾸지 않으면서도 학습을 향상시킬 수 있을지 보여주었다. reward shaping의 시초격인 논문(무려 1999년 논문이다.)이라 SARSA에 대해서 적용을 했고, 단순한 예제에서만 보여주었기 때문에 후속으로 나오는 reward shaping 논문들이 어떤 식으로 발전했을지 궁금하다. 특히 좀더 학습이 어려운 환경에서 보여주면 좋을 것 같다.

Classification Tree

Decision Tree(결정 트리)란?

Decision Tree는 supervised learning 중의 하나로 연속적인 질문을 통해서 예측하는 모델이다.

이 때, 최종적으로 분류를 예측하면 Classification Tree, 값을 예측하면 Regression Tree가 된다.

Tree라는 이름에 걸맞게 root node부터 시작해서 가지(branch)를 치며 여러가지 node로 나뉘어 지게 된다.

마지막에 예측을 하는 node는 leaf라고 부른다.

이 때, 각 node에는 각 변수에 관한 질문들이 있고, 이에 대한 대답을 통해 branch로 나뉘어지게 된다.

목표는 각 node의 질문을 잘 설정해서 마지막 분류 혹은 값의 예측이 실제 분류나 값과 일치하거나 에러가 적도록 만들어야 한다.

위의 표에서 보이는 바와 같이 세가지 변수를 가지고 Cool As Ice라는 제품을 좋아하는지 분류하는 모델을 만드는 과정을 살펴보자.

1. 어떤 변수를 가지고 root node를 만들어야 할까?

가장 먼저 하는 질문이므로 가장 결과를 잘 분류할 수 있도록 변수를 설정해야 할 것이다.

먼저 "Loves Popcorn"이라는 항목과 "Loves Soda"을 가지고 분류를 한다고 생각해보자.

과연 둘 중에 누가 분류를 더 잘한 것일까?

직관적으로 "Love Soda?"라는 질문을 가지고 했을 때 좀 더 분류를 뚜렷하게 하는 것 같다.

하지만 이걸 어떻게 수치화할까?

이 때 우리는 Gini Impurity라는 방법을 사용하는데 Gini Impurity가 낮은 쪽으로 (즉, pure하게 나뉠 수 있도록) 가지를 나눠야 한다.

Gini Impurity 계산하기

Leaf node에서 Gini Impurity는 1에서 각 분류의 비율을 제곱해서 빼면 된다.

맨 왼쪽의 경우 yes는 1/4, no는 3/4이므로 

$$ 1 - (\frac{1}{4})^2 - (\frac{3}{4})^2 = 0.375 $$

Leaf node가 아닌 node에서는 child node들의 Gini Impurity를 데이터의 비율대로 더해주면 된다.

Love Popcorn?의 경우를 살펴보면

$$ \frac{4}{7}(1 - (\frac{1}{4})^2 - (\frac{3}{4})^2) + \frac{3}{7}(1 - (\frac{2}{3})^2 - (\frac{1}{3})^2) = 0.405 $$

Love Soda?의 경우를 살펴보면

$$ \frac{4}{7}(1 - (\frac{3}{4})^2 - (\frac{1}{4})^2) + \frac{3}{7}(1 - (\frac{3}{3})^2 - (\frac{0}{3})^2) = 0.214 $$

위의 수식과 같이 "Love Popcorn?"을 사용하면 Gini Impurity는 0.405, "Love Soda?"는 0.214라는 값이 나온다.

따라서 우리의 직관과 마찬가지로 "Love Soda?"를 가지고 분류하는 것이 더 좋다.

Q2. 그렇다면 카테고리가 아닌 값으로 되어 있는 변수는 어떻게 활용할까?

Age 같은 경우에는 카테고리가 아닌 값으로 되어 있기 때문에 분류에 활용하기 위해서는 경계값(threshold)를 정해주어야 한다.

즉, Age를 오름차순으로 정렬했을 때, 그 중간값을 가지고 노드를 만들게 된다.

예를 들면 7과 12의 중간값인 (Age > 9.5?)라는 노드를 만들어서 가지를 만들게 된다.

그러면 카테고리 값과 마찬가지로 Gini Impurity를 구할 수 있을 것이다.

데이터가 N개 있으면 N-1개의 중간값을 만들 수 있는데 이를 전부 체크해서 최소 Gini Impurity를 만드는 중간값을 경계값으로 정한다.

최종적으로 세 변수로 만든 Node 중 Gini Impurity가 가장 낮은 것을 골라 root node를 만든다.

위의 예제에서는 Love Popcorn? = 0.405,  Love Soda? = 0.213, Age > 15? = 0.343 이므로 Love Soda?를 root node로 사용하면 된다.

root node 이후에는 어떻게 해야할까?

root node 이후에도 이와 같은 방식으로 계속 가지를 만들어 내려가면 된다.

노드 하나당 가지를 몇개로 할 것인지(보통 2개이다), root로부터 얼마만큼 깊게 가지를 내릴 것인지 등은 하이퍼파라미터로 정할 수 있다.