심층 강화 학습을 사용하여 발견된 더 빠른 정렬 알고리즘

Nature 618권, 257~263페이지(2023)이 기사 인용

88k 액세스

952 알트메트릭

측정항목 세부정보

정렬이나 해싱과 같은 기본 알고리즘은 특정 날짜에 수조 번 사용됩니다1. 계산에 대한 수요가 증가함에 따라 이러한 알고리즘의 성능을 최대한 높이는 것이 중요해졌습니다. 과거에는 놀라운 진전이 이루어졌지만2 이러한 루틴의 효율성을 더욱 향상시키는 것은 인간 과학자와 컴퓨터 접근 방식 모두에게 어려운 일이었습니다. 여기서 우리는 인공지능이 지금까지 알려지지 않은 루틴을 발견함으로써 어떻게 현재의 기술 수준을 뛰어넘을 수 있는지 보여줍니다. 이를 실현하기 위해 우리는 싱글 플레이어 게임에서 더 나은 정렬 루틴을 찾는 작업을 공식화했습니다. 그런 다음 이 게임을 플레이하기 위해 새로운 심층 강화 학습 에이전트인 AlphaDev를 훈련했습니다. AlphaDev는 이전에 알려진 인간 벤치마크보다 성능이 뛰어난 작은 정렬 알고리즘을 처음부터 발견했습니다. 이러한 알고리즘은 LLVM 표준 C++ 정렬 라이브러리3에 통합되었습니다. 정렬 라이브러리의 이 부분에 대한 이러한 변경은 강화 학습을 사용하여 자동으로 발견된 알고리즘으로 구성 요소를 대체함을 나타냅니다. 또한 접근 방식의 일반성을 보여주는 추가 영역의 결과도 제시합니다.

인간의 직관과 노하우는 알고리즘을 개선하는 데 결정적인 역할을 했습니다. 그러나 많은 알고리즘은 인간 전문가가 더 이상 최적화할 수 없는 단계에 도달하여 계속해서 증가하는 계산 병목 현상을 초래합니다. 수십 년에 걸쳐 진행된 고전 프로그램 합성 문헌의 작업은 대기 시간에 대한 프록시를 사용하여 올바른 프로그램을 생성하거나 프로그램을 최적화하는 것을 목표로 합니다. 여기에는 열거형 검색 기술4,5,6,7 및 확률적 검색5,6,8,9,10뿐만 아니라 올바른 프로그램 생성을 위해 프로그램 합성에 딥 러닝을 사용하는 최근 추세가 포함됩니다11,12,13,14,15,16 . 심층 강화 학습(DRL)을 사용하면 이전 작업에 비해 정확하고 빠른 프로그램의 공간을 보다 효율적으로 검색하고 고려하여 CPU 명령 수준에서 실제 측정된 대기 시간을 최적화하여 정확하고 성능이 뛰어난 알고리즘을 생성함으로써 한 단계 더 나아갈 수 있습니다. .

컴퓨터 과학의 근본적인 질문 중 하나는 시퀀스를 정렬하는 방법입니다17,18,19,20. 이것은 전 세계 초등 컴퓨터 과학 수업에서 가르치며21,22 광범위한 응용 프로그램에서 어디서나 사용됩니다23,24,25. 수십 년간의 컴퓨터 과학 연구는 정렬 알고리즘을 발견하고 최적화하는 데 중점을 두었습니다26,27,28. 실용적인 솔루션의 핵심 구성 요소는 짧은 요소 시퀀스에 대한 작은 정렬입니다. 이 알고리즘은 분할 정복 접근법을 사용하는 대규모 배열을 정렬할 때 반복적으로 호출됩니다. 본 연구에서는 두 가지 유형의 소규모 정렬 알고리즘, 즉 (1) 고정 정렬과 (2) 가변 정렬에 중점을 둡니다. 고정 정렬 알고리즘은 고정 길이의 시퀀스를 정렬하는 반면(예를 들어 정렬 3은 길이가 3인 시퀀스만 정렬할 수 있음), 가변 정렬 알고리즘은 다양한 크기의 시퀀스를 정렬할 수 있습니다(예를 들어 변수 정렬 5는 1에서 5까지의 시퀀스를 정렬할 수 있음) 강요).

우리는 AssemblyGame이라고 하는 싱글 플레이어 게임으로 새롭고 효율적인 정렬 알고리즘을 발견하는 문제를 공식화합니다. 이 게임에서 플레이어는 새롭고 효율적인 정렬 알고리즘을 생성하기 위해 결합할 일련의 하위 수준 CPU 명령어(조립 명령어30)를 선택합니다. 이는 플레이어가 정확하고 빠른 알고리즘을 생성하기 위해 조립 지침의 조합 공간을 고려해야 하기 때문에 어려운 일입니다. AssemblyGame의 견고함은 체스(10120 게임)31 및 바둑(10700 게임)32과 같은 매우 어려운 게임과 유사한 검색 공간의 크기뿐만 아니라 보상 기능의 특성에서도 발생합니다. AssemblyGame의 단 하나의 잘못된 명령으로 인해 전체 알고리즘이 무효화될 수 있으므로 이 게임 공간에서의 탐색이 엄청나게 어려워집니다.

) to the current algorithm generated thus far. A reward rtis received that comprises both a measure of algorithm correctness and latency. Algorithm correctness (Fig. 2b) involves inputting a set of N test sequences into the current algorithm Pt to generate N outputs. These outputs are then compared to the expected outputs and a correctness reward rt is computed. Latency rewards can be generated by either (1) penalizing the agent for increasing the length of the algorithm (when length and latency are highly correlated) that we refer to as the algorithm length reward, or (2) measuring the actual latency of the algorithm. The game is executed for a limited number of steps, after which the game is terminated. Winning the game corresponds to generating a correct, low-latency algorithm using assembly instructions. Losing the game corresponds to generating an incorrect algorithm or a correct but inefficient algorithm./p> assembly instruction, which is appended to the current algorithm. The agent receives a reward that is a function of the algorithm's correctness, discussed in b, as well as the algorithm's latency. The game is won by the player discovering a low latency, correct algorithm. b, The program correctness and latency computations are used to compute the reward rt. In this example, test sequences are input to the algorithm; for example, in the case of sorting three elements, test inputs comprise all sequences of unsorted elements of length 3. For each sequence, the algorithm output is compared to the expected output (in the case of sorting, the expected output is the sorted elements). In this example, the output \({\bf{D}}{\boldsymbol{{\prime} }}\) does not match the expected output \({\bf{B}}{\boldsymbol{{\prime} }}\) and the algorithm is therefore incorrect./p>