구글은 AI를 이용해 10년 순위 알고리즘의 봉인을 깨고 매일 수조 번씩 실행되는데 네티즌들은 이것이 가장 비현실적인 연구라고 말한다.

조직 | 누카콜라 추싱주안

기초 컴퓨터 공학 과정을 이수한 친구는 정렬 알고리즘을 직접 설계해야 합니다. 즉, 코드를 사용하여 정렬되지 않은 목록의 항목을 오름차순 또는 내림차순으로 재정렬하는 것입니다. 이는 흥미로운 도전이며 이를 수행할 수 있는 방법은 많습니다. 정렬 작업을 보다 효율적으로 수행하는 방법을 찾는 데 많은 시간이 투자되었습니다.

기본 작업으로 정렬 알고리즘은 대부분의 프로그래밍 언어의 표준 라이브러리에 내장되어 있습니다. 대량의 데이터를 온라인으로 정리하기 위해 전 세계의 코드베이스에는 다양한 정렬 기술과 알고리즘이 사용되지만 적어도 LLVM 컴파일러와 함께 사용되는 C++ 라이브러리에 관한 한 정렬 코드는 10년 넘게 변경되지 않았습니다. .

최근 Google의 DeepMind AI 팀은 강화 학습 도구인 AlphaDev를 개발했습니다. 이 도구는 인간 코드 예제를 사용하여 사전 훈련할 필요 없이 극도로 최적화된 알고리즘을 개발할 수 있습니다. 오늘날 이러한 알고리즘은 LLVM 표준 C++ 정렬 라이브러리에 통합되어 10여년 만에 처음으로 정렬 라이브러리의 일부가 변경되었으며 강화 학습으로 설계된 알고리즘이 라이브러리에 추가된 것은 처음입니다.

프로그래밍 과정을 "게임"으로 생각하세요

DeepMind 시스템은 인간의 게임 전략에 대한 사전 노출이 필요하지 않기 때문에 인간이 생각하지 못한 문제에 대한 해결책을 발견할 수 있는 경우가 많습니다. DeepMind는 경험을 통해 학습할 때 전적으로 자기 대결에 의존하기 때문에 때때로 인간이 악용할 수 있는 사각지대가 있습니다.

이 방법은 실제로 프로그래밍과 매우 유사합니다. 대규모 언어 모델은 인간 코드의 수많은 예를 보았기 때문에 효율적인 코드를 작성할 수 있습니다. 하지만 이로 인해 인간이 이전에 해보지 못한 일을 언어 모델이 만들어내는 것은 어렵습니다. 유비쿼터스 기존 알고리즘(예: 정렬 기능)을 더욱 최적화하려면 기존 휴먼 코드에 계속 의존하여 고유한 아이디어의 제약을 극복하기 어려울 것입니다. 그렇다면 AI는 어떻게 진정으로 새로운 방향을 찾을 수 있을까요?

DeepMind 연구원들은 체스 및 바둑과 유사한 방법을 사용하여 코드 작업을 최적화하여 이를 싱글 플레이어 "직소 퍼즐"로 전환했습니다. AlphaDev Systems는 코드 실행 지연을 점수로 처리하는 x86 어셈블리 알고리즘을 개발했으며, 코드가 원활하게 실행될 수 있도록 하면서 점수를 최소화하기 위해 노력하고 있습니다. AlphaDev는 강화 학습을 적용한 덕분에 효율적이고 간결한 코드를 작성하는 기술을 점차 습득했습니다.

AlphaDev는 AlphaZero를 기반으로 합니다. DeepMind는 스스로 게임 규칙을 학습할 수 있는 AI 소프트웨어를 개발하는 것으로 잘 알려져 있습니다. 이러한 사고 방식은 매우 효과적인 것으로 입증되었으며 체스, 바둑, "스타크래프트"와 같은 많은 게임 문제를 성공적으로 해결했습니다. 세부 사항은 플레이하는 게임에 따라 다르지만 DeepMind의 소프트웨어는 반복 플레이를 학습하여 점수를 최대화하는 방법을 지속적으로 탐색합니다.

AlphaDev의 두 가지 핵심 구성 요소는 학습 알고리즘과 표현 기능입니다.

게임을 조립하기 위해 무작위 검색 최적화 알고리즘과 결합된 DRL을 사용하는 것은 AlphaDev 학습 알고리즘의 방법입니다. AlphaDev의 주요 학습 알고리즘은 신경망이 게임을 통해 검색을 안내하도록 학습되는 잘 알려진 DRL 알고리즘인 AlphaZero 33의 확장입니다.

이 기능은 알고리즘의 일반적인 구조는 물론 x86 레지스터 및 메모리 사용을 포함하여 코드 개발의 전반적인 성능을 모니터링하는 데 사용됩니다. 시스템은 게임 시스템에서 차용한 몬테카를로 트리 검색 방법을 사용하여 선택할 때 독립적으로 추가되는 조립 지침을 점진적으로 도입할 것입니다. 트리 구조를 통해 시스템은 많은 수의 잠재적 명령어가 포함된 제한된 영역으로 검색 범위를 빠르게 좁힐 수 있는 반면, 몬테카를로 방법은 이 분기 영역에서 어느 정도 무작위로 특정 명령어를 선택합니다. 여기에 언급된 "명령"은 유효하고 완전한 어셈블리를 생성하기 위해 특정 레지스터를 선택하는 것과 같은 작업입니다. )

그런 다음 시스템은 어셈블리 코드의 대기 시간과 유효성 상태를 평가하고 이전 점수와 비교되는 점수를 제공합니다. 강화학습을 통해 시스템은 주어진 프로그램 상태에 대한 트리 구조의 다양한 분기의 작업 정보를 기록할 수 있습니다. 시간이 지남에 따라 시스템은 가장 높은 점수(최저 지연 시간을 나타냄)로 게임에서 승리하는 방법(정렬 완료)에 익숙해집니다. AlphaDev의 주요 표현 기능은 Transformers를 기반으로 합니다.

AlphaDev가 새로운 알고리즘을 발견하도록 훈련시키기 위해 AlphaDev는 각 라운드에서 자신이 생성하는 알고리즘과 중앙 처리 장치(CPU)에 포함된 정보를 관찰한 다음 알고리즘에 추가할 명령을 선택하여 게임을 완료합니다. AlphaDev는 순서화할 수 있고 현재 최고의 알고리즘보다 빠른 알고리즘을 찾기 위해 가능한 많은 명령 조합을 효율적으로 검색해야 하며, 에이전트 모델은 알고리즘의 정확성과 대기 시간을 기반으로 보상을 받을 수 있습니다.

사진 A: 조립 게임, 사진 B: 보상 계산

마지막으로 AlphaDev는 LLVM libc++ 정렬 라이브러리를 개선할 수 있는 새로운 정렬 알고리즘을 발견했습니다. 짧은 시퀀스의 경우 정렬 라이브러리가 70% 더 빠르고, 요소가 250,000개가 넘는 시퀀스의 경우 속도가 약 1.7% 증가합니다.

특히 이 알고리즘의 혁신은 주로 AlphaDev Swap Move(스왑 이동) 및 AlphaDev Copy Move(복사 이동)라는 두 가지 명령 시퀀스에 있습니다. AlphaDev는 이 두 명령을 통해 한 단계를 건너뛰고 겉으로는 잘못된 것처럼 보이지만 실제로는 지름길을 수행합니다. 항목을 연결합니다.

왼쪽: min(A,B,C)를 사용한 원래 sort3 구현. ‍

오른쪽 사진: AlphaDev 스왑 이동 - AlphaDev는 min(A,B)만 필요하다는 것을 발견했습니다.

왼쪽: 8개 요소를 정렬하는 더 큰 정렬 알고리즘을 위한 max(B, min (A, C))의 원래 구현입니다.

‍오른쪽: AlphaDev는 복사 이동을 사용할 때 최대(B, min (A, C))만 필요하다는 것을 발견했습니다.

이 시스템의 가장 큰 장점은 교육 과정에 코드 예제가 필요하지 않다는 것입니다. 대신 시스템은 코드 예제를 자율적으로 생성한 다음 이를 평가합니다. 그 과정에서 명령 조합의 효과적인 순서에 대한 정보를 점차적으로 습득합니다.

정렬부터 해싱까지

더 빠른 정렬 알고리즘을 발견한 후 DeepMind는 AlphaDev가 다른 컴퓨터 과학 알고리즘인 해싱을 일반화하고 개선할 수 있는지 테스트했습니다.

해싱은 컴퓨팅에서 데이터를 검색, 저장 및 압축하는 데 사용되는 기본 알고리즘입니다. 특정 책을 찾기 위해 분류 시스템을 사용하는 사서와 마찬가지로 해싱 알고리즘은 사용자가 무엇을 찾고 있는지, 어디서 찾을 수 있는지 알 수 있도록 도와줍니다. 이러한 알고리즘은 특정 키(예: 사용자 이름 "Jane Doe")에 대한 데이터를 가져와 해시합니다. 이는 원시 데이터를 고유한 문자열(예: 1234ghfty)로 변환하는 프로세스입니다. 이 해싱 알고리즘은 전체 데이터를 검색할 필요 없이 키와 관련된 데이터를 빠르게 검색하는 데 사용됩니다.

DeepMind는 더 빠른 알고리즘을 발견하기 위해 데이터 구조에서 가장 일반적으로 사용되는 해싱 알고리즘 중 하나에 AlphaDev를 적용합니다. AlphaDev는 해시 함수가 9-16바이트 범위의 데이터를 사용할 때 알고리즘이 30% 더 빠르다는 것을 발견했습니다.

올해 AlphaDev의 새로운 해싱 알고리즘은 전 세계 수백만 명의 개발자가 사용할 수 있는 오픈 소스 Abseil 라이브러리에 출시되었으며 이제 라이브러리는 매일 수조 번 사용됩니다.

실제 작업 코드

복잡한 프로그램의 정렬 메커니즘은 대규모의 임의 항목 모음을 처리할 수 있습니다. 그러나 표준 라이브러리 수준에서 이 기능은 일련의 매우 제한된 특정 기능에서 비롯됩니다. 이러한 각 기능은 하나 또는 몇 가지 상황만 처리할 수 있습니다. 예를 들어 일부 개별 알고리즘은 3, 4 또는 5개의 항목만 정렬할 수 있습니다. 일련의 함수를 사용하여 항목 수에 관계없이 정렬할 수 있지만 함수 호출당 항목을 최대 4개까지만 정렬할 수 있습니다.

AlphaDev는 DeepMind에서 각 기능을 구현했지만 실제 작동 방식은 크게 다릅니다.. 특정 수의 항목을 처리하는 함수, 즉 변수 상태에 따라 다른 코드를 실행하는 함수를 처리하기 위해 분기 문 없이 코드를 작성할 수 있습니다. 따라서 코드 성능은 관련된 명령어 수에 반비례하는 경향이 있습니다.

AlphaDev는 sort-3, sort-5 및 sort-8의 명령 수를 각각 하나씩 성공적으로 줄였으며 sort-6 및 sort-7에서는 훨씬 더 많이 줄였습니다. 기존 코드를 개선할 수 있는 방법은 sort-4에서만 찾을 수 없습니다. 실제 시스템에 대한 반복 테스트를 통해 명령어 수가 적어지면 성능이 향상되는 것으로 나타났습니다.

다양한 수의 항목을 정렬하려면 코드에 분기 문을 포함해야 하며, 프로세서마다 이러한 분기를 처리하는 데 사용되는 구성 요소 수가 다릅니다.

연구원들은 이 상황을 평가할 때 100가지의 서로 다른 컴퓨팅 장치를 사용했습니다. AlphaDev는 이러한 유형의 시나리오에서 성능을 더욱 압축하는 방법도 찾았습니다. 한 번에 최대 4개 항목을 정렬하는 기능을 예로 들어 작동 방식을 살펴보겠습니다.

현재 C++ 라이브러리 구현에서 코드는 정렬해야 하는 항목 수를 확인하기 위해 일련의 테스트를 수행한 다음 항목 수에 따라 해당 정렬 함수를 호출해야 합니다.

AlphaDev의 수정된 코드는 보다 "마법적인" 아이디어를 채택합니다. 먼저 항목이 2개 있는지 테스트하고, 그렇다면 해당 함수를 호출하여 즉시 정렬합니다. 숫자가 2보다 크면 코드는 처음 3개 항목을 먼저 정렬합니다. 이렇게 하면 실제로 항목이 3개만 있는 경우 정렬된 결과가 반환됩니다. 실제로 정렬할 항목이 4개 있으므로 AlphaDev는 매우 효율적인 방식으로 정렬된 처음 3개 항목 중 적절한 위치에 4번째 항목을 삽입하기 위해 특수 코드를 실행합니다.

이 접근 방식은 조금 이상하게 들리지만 기존 코드보다 항상 성능이 더 좋다는 것이 밝혀졌습니다.

AlphaDev는 더 효율적인 코드를 생성하므로 연구팀은 이러한 결과를 LLVM 표준 C++ 라이브러리에 다시 병합할 계획입니다. 하지만 문제는 코드가 C++가 아닌 어셈블리 형식이라는 것입니다. 따라서 동일한 어셈블리를 생성하는 C++ 코드를 찾으려면 거꾸로 작업해야 합니다.

이 문장의 재작성 버전: 코드의 이 부분은 이제 LLVM 툴체인에 통합되었으며 거의 ​​10년 만에 처음으로 업데이트되었습니다. 연구원들은 AlphaDev에서 생성된 새로운 코드가 매일 수조 번 실행되는 것으로 추정합니다.

결론

너무 좋아요! 우리 프로그래머들은 이 기본적인 정렬 작업을 오래 전에 배웠지만 이제는 70% 더 빨라졌습니다. 우리 모두가 의존하는 알고리즘과 라이브러리의 AI가 상당한 속도 향상을 제공하므로 기대되는 부분이 많습니다. "일부 개발자는 Google DeepMind의 결과에 매우 기뻐하고 있습니다.

그러나 일부 개발자는 이를 구매하지 않았습니다. "매우 실망스럽습니다...1.7% 개선? 5개 요소 시퀀스의 70%? 아마도 가장 인기가 없고 가장 비현실적인 응용 연구일 것입니다..." 일부 개발자는 다음과 같이 말했습니다. 새로운 알고리즘이 발견되었다고 말하는 것은 약간 오해의 소지가 있는 것 같나요? 어쨌든 여전히 멋지네요."

참조 링크:

https://arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

Depth: 왜 중국의 데이터베이스 분야에서는 Snowflake와 같은 거대 기업이 등장하지 않았나요?

17년 만에 가장 기괴한 붕괴! OpenAI와 Google이 데이터를 공짜로 얻는 것을 막기 위해 Reddit은 막대한 API 비용을 청구하고 개발자를 비방하여 커뮤니티에서 대규모 항의를 일으켰습니다

회사 창업 코드 '훔치기', 학력 ​​위조, 6일 만에 1억 달러 벌었지만 임금 체불 안한 AI 유니콘 CEO, 거듭된 질문에 직접 답변

위 내용은 구글은 AI를 이용해 10년 순위 알고리즘의 봉인을 깨고 매일 수조 번씩 실행되는데 네티즌들은 이것이 가장 비현실적인 연구라고 말한다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!