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

[논문 리뷰] 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

---

핵심적인 부분만 요약해서 포스팅하려고 했는데 공부하다보니까 그냥 직독직해식으로 공부하는 것이 나을 거 같아서 일단은 전부 의역하면서 짚어나가겠다.

 

---

 

Exploration은 인공지능 분야에 있어서 근본적인 문제였다. exploration과 exploitation의 문제에서처럼 말이다.

이 논문에서는 모르는 미지의 환경(학습이 이루어지지 않았던 환경)이 주어졌을 때, exploration의 여러가지 문제를 커버하고자 하려고 한다.

그래서 본 논문의 목적은 가능한 최대한 많은 unique한 state를 주어진 상호가능한 예산안에서 도달하는 것이다. 

 

위에서도 언급했듯이, state-space를 돌아다니는 탐험 문제는 실제 현실세계에서도 매우 중요한 것으로 나타나고 있다.

예를 들면, software test를 진행할때와 맵을 새로이 만드는 작업 같은 것이다.

software test 같은 경우, 목적이 조심스럽게 설계할 때나 test input을 넣었어서 돌릴 때, 숨어있는 잠재 버그들을 찾아내는 것이다.

프로그램의 탐험의 효율성을 정량화하기 ㅜ이해서는 input에 의해 작동되는 코드의 branch들의 수와 같은 프로그램 커버리지가 전형적으로 surrogate objective(바뀐 목적으로) 사용된다.

가장 유명한 자동화 test 기술 중의 하나는 바로 fuzzing이 있다. 이것은 random하게 실행되는 input들로 하여금 코드 활성도를 높이려고 한다.

지도를 만드는 작업에서는, 로봇이 현재 갖고 있는 위치 정보를 기억하면서 모르는 지역의 환경에 대한 구조를 필요로 할 것이다.

더 많은 위치에 방문할수록, 지도의 재구성은 더 나아질 것이다.

이런 대부분의 문제들은 제한된 예산(budget: limited time or simulation trials)을 갖고 있으며, 그러므로 좋은 탐험(탐색) 전략을 갖는 것은 매우 중요하다.

 

이 문제에서 가장 중요한 부분은 경험하지 못한 환경에 대한 일반화이다.

software test문제를 다시 가져와서 얘기를 하자면, 가장 전형적인 방법은 fuzzing 방법론이고, 이 fuzzing  방법론은 이전에 테스트한 프로그램에 대한 지식이 활용되지 않는 처음부터 시작하는 것이다.

 

다른 프로그램들은 보통 비슷한 디자인 패턴과 semantic을 갖는데 이들은 exploration을 진행하는 동안에 exploited을 진행한다.

본 논문은 전환가능한 탐험 효율성을 이루는 것을 목적으로 하면서 각기 다른 환경들의 분포로부터의 정책을 학습하는 "learning to explore" 프레임워크가 목적인 셈이다.

test를 진행할 때, 동일한 환경 분포로부터 경험하지 못한 환경이 주어진다면, policy는 제한된 state step안에서 최대한 많은 unique한 state를 방문할 수 있는 탐색 전략을 일반화시키는 것을 목표로 한다.

 

강화학습을 이용한 state-space 커버리지 문제를 수식화해야한다.

Markov Decision Process(MDP)에 일치하는 보상 메커니즘은 각 에피소드 절차처럼 극적으로 변하는 것처럼 정지되어 있는 상태는 아니다.

특별히, 관찰하지 않은 state를 방문하는 것은 보상이 이루어지지만, 한 번보다 많이 방문한 것은 탐색 예산의 낭비이다.

다른 말로 풀어 쓰자면, 환경은 항상 agent로부터 새로워야 한다는 것이다.

 

이런 많은 탐색 문제를 갖는 state는 전형적으로 구조화되어 있다.

예를 들어, 프로그램은 구문적 혹은 의미론적 구조를 가지고 있고, program statement를 효율적으로 다루는 것은 graph 구조에 대한 추론이 필요하다.

일반적인 강화학습 환경에서의 state도 도달가능성을 의미하는 edge를 갖는 graph 구조로 표현이 가능하다.

이런 환경 구조를 이용하기 위해서, 그래프 신경망(GNN, Graph Neural Network)의 RL agent를 늘려서 graph 구조를 갖는 state로 나타내고 인코딩한다.

이러한 모델은 문제 상황(환경)을 관통하는 일반화할 수 있는 능력을 agent에게 부여한다.

또한 graph 구조의 외부 메모리를 사용하여 agent와 환경 간의 상호작용 기록을 포착한다.

이 정보를 agent의 state에 추가하면, 탐색 문제의 coverage의 비정상성 문제를 처리할 수 있다.

본 논문의 핵심을 정리하자면 다음과 같다.

 

• 몇 가지 중요한 적용을 위해서 탐색 문제에 대해서 graph 구조를 갖는 공간 새로운 framework를 제안함.
• GNN을 사용하여 graph 구조의 state를 모델링하고, 일련의 발전하는 graph로 탐색 기록을 모델링하는 것을 제안함. 특히 일련의 발전하는 graph의 모델링은 학습 및 프로그램 test 연구를 시도하는 것은 본 논문이 처음이다.
• 합성 2-Dimension 미로부터 software test를 위한 input 생성과 마지막으로 실제 Android 앱을 테스트하는 것까지, 이와 같은 도전적인 문제의 범위에서의 graph 탐색 agent를 적용하는 것을 성공적으로 이끌었다. 이에 대한 실험 평가는 실제 전문가가 설계한 heuristic과 Z3 SMT(Satisfiability Modulo Theories) solver를 사용한 상징적 실행과 같은 강력한 기준선과 비교하거나 더 좋다는 것을 보여준다.