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

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

---

5. Related work

강화학습에서 exploration과 eploitation의 벨런스에 대한 이야기는 전형적인 주제이다.

이 문제에 대해 테클을 걸자면, 많은 메커니즘이 개발되어왔고(epsilon-greedy부터 pseudo-count, inrtinsic motivation, diversity, meta learning approach까지), 이런 알고리즘들은 스스로 학습을 진행하거나 mulit-modality policy distribution을 다루는 구조적인 noise를 결합했다.

SLAM paper에서는, 탐색 문제가 entropy나 정보 기반 접근방식과 같은 다른 불확실성 영역을 갖는 active SLAM으로 알려져있다.

본 논문에서 소개된 연구는 graph 안에서 distinct한 state를 탐색하는 것에만 초점을 맞추고 있다.

 

Exploration for Fuzzing

Fuzzing은 학습된 제안된 distribution 혹은 알려진 search coverage와 함께 software에서는 corner case를 탐색한다.

input 예시로 program semantics를 탐색하기 위해서는 greedy 방법론이나 직접 조정된 distribution으로부터 샘플링 하면서 사람(전문가)이 개입되어 heuristic하게 디자인했어야만했다.

몇몇의 최근 fuzzing 방법론을 기반으로한 학습방법(Learn&Fuzz, DeepFuzz)은 새로운 입력을 생성하기 위해 입력과 샘플의 언어 모델을 구축하지만, 그러한 패러다임은 프로그램 조건부 테스트에 직접 적용할 수 없다.

Neuzz는 gradient guided input generation을 허용하는 AFL의 정상 부분에 smooth한 추정함수를 만든다.

arxiv.org/pdf/1711.04596.pdf 이 논문에서는 이전의 fuzzing 탐색에 대한 지도 학습을 사용하여 어떤 byte가 새로운 coverage로 이어질 수 있는지를 예측하는 함수를 학습한다.

특정 task를 탐색하는 이러한 방법론과는 달리, 본 논문에서는 새로운 보지 못한 호나경에서 직접 roll out될 수 있는 graph memory 기반 agent에 encoding된 전송 가능한 탐색 전략을 학습한다.

 

Representation Learning over structures

외부의 graph memory의 대표적인 것은 graph representation learning에서 최근의 advance를 구축하는 것이다.

GNN과 다양한 것들은 프로그램 모델링, 준지도학습, 생명정보학과 화학을 포함한 도메인 영역에서 무지 좋은 결과를 보여줬다.

본 논문에서는 1511.05493.pdf (arxiv.org)논문의 parameterization과 graph sequence modeling, 그리고 attention 기반 read-out for graph를 적용했다.

 

Optimization over Graph

현존하는 논문들은 경로 찾기 문제를 연구해왔다.

DOM-Q-NET 알고리즘은 HTML 문서를 다루고 확실하게 task를 끝낸다.

반면에 1611.03673.pdf (arxiv.org)논문은 복잡한 시각적 input들을 학습하는 것을 다룬다.

우리의 task는 본직적으로 NP-hard 문제와 같은 optimal traversal tour을 찾는 문제이다.

그리고 이 연구는 graph 구조의 데이터의 combinatiorial optimization 분야에서 최근 좋은 결과를 보인 것과 관련이 있다.

GNN은 one-bit 혹은 완전 지도학습으로 학습할 수 있으며 combinatiorial optimization문제를 일반화한다.

supervision이 부족한 경우 강화학습은 조정된다.

arxiv.org/pdf/1704.01665.pdf논문에서는 action policy를 학습하기 위해 finite horizon DQN을 사용한다.

본 논문의 연구는 크게 2가지면에서 다르다.

1. graph의 전체적인 구조는 항상 관측되는 것이 아니고 agent에 탐색되는 것이다.
2. 탐색 history를 sequence of evolving graph로 모델링 한다. 하나의 graph에서의 Q-learning 대신에

 

 

 

 

 

 

6. Conclusion

본 논문에서, transferable graph exploration을 연구했다.

일련의 graph 구조를 갖는 외부 메모리를 탐색 history의 encoding에 사용하는 것을 제안했다.

GNN을 사용한 graph 구조의 encoding을 함으로써, 본 연구는 trasferable history memory representaion을 포함할 수 있었다.

본 논문에서의 방법론을 synthetic 2D 미로 탐색과 실제의 프로그램과 어플 test에 활용하였고, 사람이 직접 설계한 방법보다 더 좋은 성능을 보였다.

Future work로는 graph external memory를 더 큰 software 혹은 code르 다루기 위해 scale-up 하는 것이다.