[논문 리뷰] Learning Transferable Graph Exploration - 2.Problem Formulation

 

[논문 리뷰] Learning Transferable Graph Exploration - 0.Abstract

[논문 리뷰] Learning Transferable Graph Exploration - 1.Introduction

[논문 리뷰] Learning Transferable Graph Exploration - 2.Problem Formulation

[논문 리뷰] Learning Transferable Graph Exploration - 3.Model

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (1)Synthetic 2D Maze Exploration

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (2) Generating Inputs for Testing Domain Specific Programs

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (3)App Testing

[논문 리뷰] Learning Transferable Graph Exploration - 5.Related work & 6.Conclusion

---

2가지 탐색 설정을 고려해야한다.

첫 번째 설정은 전혀 모르는 환경, 즉, 학습되지 않은 환경에서의 탐색인 것이다.

이 것은 agent가 각 step을 graph로 관찰하는데,

이 graph의 node는 각 unique한 환경 state를 의미하고, edge는 경험해본(학습해본) 것을 의미한다.

이러한 설정에서, 이 graph는 episode가 진행됨에 따라 size가 점차 커지고 agent는 이 graph의 성장 속도를 최대화하려고 한다.

두 번째 설정은 이미 알고있는, 즉, 학습해보았지만 복잡한 환경에서의 탐색이다.

이것은 프로그램 test와 연관이 있기도 하다.

이번 설정에서는, 프로그램 소스 코드와 graph에 접근한다.

여기서의 graph는 node가 프로그램 분기를 의미하고, edge는 분기간에 구문과 의미와 같은 관계를 의미한다.

여기서의 핵심은 graph 구조에 대해 추론하고 이해하고, graph 범위를 늘리기 위한 올바른 action을 마련하는 것이다.

각 action은 거대한 action 공간에 있으며, 큰 구조를 갖는 test input을 의미한다.

의미있는 input과 같은 것을 찾는 것은 구문 자동화 test에서매우 중요하다.

정확한 논리적 추론을 위한 복잡한 프로그램의 의미를 모델링하는 것이 중요하기 때문이다.

살펴보았던 두 가지 설정을 같은 수식으로 도식화할 수 있다.

• 각 step을 $t$
• agent가 graph를 관측한 것을 $G_{t-1} = (V_{t-1}, E_{t-1})$
• coverage mask는 node가 탐색과정을 거쳐진 것을 $c_{t-1}: V_{t-1} -> {0, 1} $

라고 표기할 수 있다.

agent는 액션$x_t$를 수행하고, 환경(environment)은 이 액션을 받아들이고 새로운 graph $G_t = (V_t, E_t)$와 새로운 $c_t$를 리턴한다.

위에서의 첫번째 설정에서, coverage mask인 $c_t$는 graph에서 방문한 node 어떤 노드($v \elements V_t$)라면 항상 1의 값을 갖는다.

즉, coverage mask는 일종의 flag인 셈이다.

agent가 방문한 node인지 아닌지 여부에 따라 {0, 1} 두 값 중 하나의 값을 갖는다.

반면 두 번째 설정에서는 graph$G_t$는 매 step마다 일정하고, coverage mask$c_t(v)$는 만약 $v$가 과거에 이미 방문 했었다면 1의 값을 갖고, 그것이 아니라면 0의 값을 갖는다.

$t=0$일때, 최초의 측정은 $c_0$가 되고 이것은 어떤 node든 0의 값을 갖게한다. 그리고 첫 탐색 때 $G_0$를 빈 graph로 세팅한다.

graph구조의 환경을 탐색하는 과정은 탐색을 위한 예산안에서의 action 혹은 step의 수($T$)를 갖는 finite horizon MDP(Markov Decision Process)으로 볼 수 있다.

 

Action

action space($x_t$)는 문제가 있다.

여기서는 보통 가장 흔한 문자인 $a$ 대신에 $x$ 문자를 사용했는데, 그 이유는 이런 actions들이 때때로 전형적인 강화학습 환경에서의 고정된 유한한 action space보다 잠재적으로 더 넓은 공간을 갖는 NN의 input에 더 가깝게 사용되기 때문에 이를 강조하기 위함이다.

특히, 프로그램 testing에서는, 각 action은 프로그램의 일련의 문자의 나열인 text나 image 혹은 2D배열의 문자와 같은 test input이다

 

우리의 과제는 탐색 object function을 최대화하기 위해 action의 시퀀스인 $x_1, x_2, ... , x_T$를 제공하는 것이다.

명백한 선택은 방문했던 unique한 node 혹은 environment states의 수이다.($\sum_{v \elements V_T} c_T(v)$)

학습하는 동안에 다른 graph size를 처리하기 위해서는, object function을 graph $|V|$의 최대로 가능한 size를 사용한 object function의 normalize를 해야한다.(두번째 탐색 설정에서 얘기했던 $|V_T|$)

그러므로 object function은 아래와 같다.(1)

objective

 

Reward

위와 같은 object function이 주어졌다면, 매 step마다의 reward $r_t$를 식 (2)와 같이 구할 수 있다.

이것은 자명한 이야기인데, MDP의 누적 reward는 식 (1)과 동일하기 때문이다. 초기값은 0이다.

by definition으로 $t$의 step에서의 reward는 action $x_t$로 알려진 coverage가 추가적으로 주어진다.

 

State

agent에게 각 step에서 관측한 결과인 $ (G_t, c_t) $를 제공하는 것 대신에, agent state를 $x_0=\phi$ 인 상황에서 episode $h_t = {(x_{\tau}, G_{\tau}, c_{\tau})}_{\tau=0}^{t-1}$에서의 full interactions history를 포함한 것으로 대표할 수 있다.

 

 

 

 

 

 

도움: data-newbie.tistory.com/707

GNN - 2탄 GNN 기본 개념 알아보기