퀠로맨 블로그

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을 늘리면 다음과 같이 나온다.

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 논문들이 어떤 식으로 발전했을지 궁금하다. 특히 좀더 학습이 어려운 환경에서 보여주면 좋을 것 같다.