End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking (DeepThinking Systems)

Abstract

반복 아키텍처, 반복 알고리즘을 통해 작은 문제를 해결할 수 있는 알고리즘을 반복하여 더 크고 복잡한 문제를 해결할 수 있도록 알고리즘 외삽을 수행한다.

 

[Github]

[arXiv](2022/10/14 version v3)

 

 

 

Methods

 

2, 3번째 그림처럼 같은 블록이 여러 번 반복되는 아키텍처를 생각해 보자.

 

임베딩 함수는 p, 출력 헤드는 h, 블록의 반복을 다음과 같이 표기하고

 

블록의 출력은 이렇게 표기한다.

 

전체 네트워크를 간단하게 표기할 수 있다.

---

Recall architectures

문제 해결을 위해 오랫동안 생각할 때, 우리는 종종 질문이나 작업을 다시 검토한다.

이에 착안하여 이전 블록의 출력에 입력을 연결하여 제공. (차원을 맞추기 위한 컨볼루션 레이어 사용)

---

Promoting forward progress through optimization

훈련 알고리즘.

Gradient를 계산하지 않고 n번 반복 (출력을 다시 입력으로 사용), 그다음 k번 반복.

별개로 다시 m번 반복하고 (n + k ≤ m) 두 손실을 모두 최종 손실에 반영한다.

 

이런 짓을 하는 이유:

• 네트워크는 많은 반복 동안 오류가 포함된 부분적인 해결책의 품질 지속적으로 향상시키도록 훈련된다.
• 임의의 반복부터 시작함으로써 특정 반복에 특정 행동을 학습하는 것을 방지한다.

 

 

 

Extreme extrapolation

9×9 미로를 해결할 수 있는 네트워크를 DeepThinking System을 통해 더 오랫동안 실행함으로써 더 큰 미로를 해결할 수 있도록 외삽하였다.