딥마인드 블로그 : https://deepmind.com/blog/article/Competitive-programming-with-AlphaCode
논문 : https://arxiv.org/abs/2203.07814
이세돌 9단과의 경기에서 4-1로 승리한 알파고, 36만 개 이상의 단백질 3차원 구조를 예측한 알파폴드를 개발한 딥마인드(DeepMind) 팀이 이번에는 코딩 경진대회 문제를 푸는 코딩하는 AI, 알파코드 (AlphaCode)를 발표했다. 알파코드는 5,000명 이상의 참가자가 참가한 실제 경진대회에서 평균 54%의 상위 순위를 달성했다.
알파코드가 코딩을 학습한 방법은 최근 AI 분야에서 좋은 성능을 보이고 있는 사전학습과 fine-tuning 전략이다. 알파코드는 먼저 깃허브 등에 올라와 있는 대량의 프로그램 코드에 대해 자기 지도 학습 (Self-supervised Learning)을 수행한다. 자기지도학습을 통해 자연어, 코딩 등을 학습한 모델은 실제 프로그래밍 대회 문제들에 대해 fine-tuning 하는 과정을 거쳐 알파코드가 완성되었다.
알파코드는 기존에 연구되었던 단순히 코드를 작성하는 AI가 아닌 문제에 대해 알고리즘을 구현하고, 새 알고리즘을 만들어야 하는 알고리즘 문제를 풀 수 있는 모델이다. 복잡한 문제 설명을 이해하고 코드를 작성하는 경쟁 프로그래밍 문제를 해결하는 어려운 영역에서 인간의 성적에 달하는 인공지능을 개발한 데에 의의가 있다.
💻 알파코드가 풀고자 하는 문제 : Competitive programming
모델에게 있어 프로그래밍 코드를 작성하는 것은 sparse한 보상 시그널을 가지는 대규모 공간에서 탐색을 하는 작업이라고 볼 수 있다. 글자 하나라도 틀리면 작성한 코드는 틀릴 수 있고, 같은 문제에 대한 다양한 솔루션이 존재할 수도 있기 때문이다. 이러한 어려움으로 인해 알파코드 이전의 논문들은 도메인이 제한된 프로그램 언어나 짧은 코드 스니펫을 생성하는 것에 한정되곤 했다.
하지만 알파코드가 다루는 것은 주어진 문제에 대한 전체 코드 프로그램을 작성하는 경쟁 프로그래밍이다.
경쟁 프로그래밍은 주어진 문제를 해결할 수 있는 컴퓨터 프로그램의 소스코드를 작성하는 것을 말한다. 대회에서 출제되는 문제는 논리적이거나 수리적인 문제이기 때문에, 조합론, 숫자 이론, 그래프 이론, 알고리즘 게임 이론, 계산 기하학, 문자열 분석 등과 관련이 있다. 즉, 주어진 문제를 읽고 이해하는 독해 능력과 더불어 문제에 대한 설루션을 작성하는 알고리즘 작성 및 구현 능력, 추론 능력을 요구한다. 작성한 코드는 숨겨진 테스트 케이스들에 대해서도 잘 작동해야 하고, 실행 속도가 중요하기도 하다.
Codeforces 플랫폼에서 개최된 최근 프로그래밍 대회에서 시뮬레이션 평가를 실행한 결과, 알파코드는 5,000명 이상의 참가자가 참가한 대회에서 평균 54.3%의 상위 순위를 달성했다. 또한 알파코드가 작성한 답안을 볼 때, 알파코드는 학습 데이터의 코드를 복사해 코드를 작성했다기보다는 문제 설명에 의존에 코드를 작성한 것으로 분석된다.
이렇게 좋은 성능을 낼 수 있었던 데에는 다음의 세 가지 핵심 요소가 작용한 것으로 분석한다 :
(1) 모델 학습 및 평가를 위한 광범위하고 잘 정제된 경쟁 프로그래밍 데이터 세트
(2) 라지 스케일의 효율적인 트랜스포머 기반 아키텍처
(3) 라지 스케일 샘플링(코드 생성)을 통해 공간을 탐색하고, 필터링을 통해 제출에 적합한 최종 코드를 찾아냄
데이터 세트
알파코드 모델은 다음의 두 가지 데이터셋으로 학습하였다 :
(1) Pre-training : Github에서 수집한 오픈소스 코드
(2) Fine-tuning : CodeContests(https://github.com/deepmind/code_contests) - 경쟁 프로그래밍 데이터셋
(1) Pre-training dataset
> 2021년 7월 14일 자에 스냅샷으로 수집한 선별된 공개 깃허브 레퍼지토리
> 자주 사용되는 프로그래밍 언어들에 대한 모든 코드를 수집함 (C++, C#, Go, Java, JavaScript, Lua, PHP, Python, Ruby, Rust, Scala, and TypeScript)
> 필터링 수행 :
- 자동 생성된 코드 제거 - 1MB보다 큰 파일 제거 , 1,000 문자 이상이 한 줄에 포함된 경우 제거
- 공백을 제거한 후 같은 내용을 가지는 파일 제거
> 필터링 후 최종적으로는 715.1GB의 데이터셋을 사전학습용 데이터로 사용
(2) Fine-tuning dataset - CodeContests
대량의 코드를 사전학습한 모델만으로 간단한 프로그래밍 문제를 풀 수 있을지는 몰라도, 경쟁 프로그래밍 문제를 풀 수는 없었다. 따라서 경쟁 프로그래밍 문제를 풀 수 있도록, 이러한 문제를 모아놓은 데이터인 CodeContests데이터를 새로 제작하고, 배포하였다.
CodeContests는 다음의 데이터로 구성되어 있다 :
a) Codeforces 플랫폼에서 수집한 문제, 솔루션, 그리고 테스트 케이스
- 문제에 대한 전체 지시문
- 메타데이터 (난이도, 문제를 풀 수 있는 접근법에 대한 태그 eg. greedy, dip, .. 포함)
- 솔루션은 C++, Python, Java 언어로 작성된 사람이 작성한 프로그램이며, 옳은 제출일 수도, 틀린 제출일 수도 있음
- 올바른 솔루션인지 여부는 인풋에 대한 프로그램 아웃풋과 기대 아웃풋을 비교함으로써 체크함
- 테스트 케이스는 플랫폼에서 제공하는 모든 테스트 케이스를 포함 (대회 종료 후 숨겨진 테스트를 공개한 경우가 있음)
- 예시 :
b) 현존하는 공개된 경쟁 프로그래밍 데이터셋
- Description2Code
- CodeNet
** 잘못된 솔루션 필터링을 위한 추가 테스트 케이스 생성 작업
제출된 솔루션의 적절성 여부를 채점하기 위해서는 양질의 테스트 케이스들이 필요하다. 하지만, 이러한 테스트 케이스들을 수집하기 어려운 경우가 많다. 예를 들어 Codeforces플랫폼에서는 400글자 이상의 테스트 케이스는 전체 공개를 하지 않는 식이다. 이렇게 테스트 케이스가 부족한 상황에서 솔루션을 채점하면, 다음의 두 가지 오류가 발생할 수 있다
a) False Positive - 실제로 틀린 코드가 맞다고 채점되는 경우
b) Slow Positive - 작동은 하지만, 비효율적이어서 문제의 제한 시간 내에 작동할 수 없는 경우 (계산 복잡도 기준을 불만족)
이러한 오분류율을 줄이기 위해, 딥마인드 팀은 현존하는 테스트 인풋을 변형(mutate)하여 추가 테스트 케이스를 생성했다.
새로운 테스트 케이스를 생성하는 방법은 다음과 같다 :
step 1. mutation 적용 : binary 인풋에 대한 bit flip, 정수 인풋을 랜덤으로 키우거나 줄이기, 문자열의 순서 바꾸기 등
step 2. 올바른 제출 30개를 새로운 테스트 케이스에 대해 실험한 후, 모든 솔루션이 같은 답안을 생성하는지 체크
=> 이 과정을 각각의 문제에 대해 200개의 테스트를 생성하거나 10 CPU 시간이 될 때까지 반복
인풋 포맷이 복잡한 경우가 있기 때문에 문제 중 6.3%에 대해서는 목표한 200개의 테스트 세트를 생성하지 못했다.
마지막으로, 검증 데이터와 테스트 데이터에 있어서는 테스트 케이스가 부족한 문제들을 제외하였따. 즉, 최소 5개의 생성된 혹은 제공된 테스트에 대해 2개 이상의 다른 아웃풋을 가지는 문제들만을 남겨두었다. 이러한 과정을 통해 모델이 단순히 YES 혹은 NO 등 고정된 답변만을 내놓는 식으로 솔루션을 찾는 것을 방지한다.
위의 표에서 볼 수 있듯이 새로 생성한 테스트 케이스를 활용한 결과, false positive rate를 62%에서 4%로 줄일 수 있었다. 이는 기존 데이터셋에 비해 크게 개선된 수치이다. 그럼에도 불구하고 테스트 셋에 대해서 작동하기는 하나 비효율적인 솔루션은 46%로, 여전히 다수 포함되어 있다.
AlphaCode Approach
모델 아키텍처
> 경쟁 프로그래밍은 문제를 입력받아 코드를 작성하는 Seq2Seq 문제이므로, Encoder-Decoder 트랜스포머 선택
> 수식적으로 표현하면, p(Y|X)를 모델링하는데,
- 인코더는 문제 지시문 X를 메타데이터를 포함해 토큰화 된 시퀀스로 입력받아
- 디코더가 autoregressive하게 코드를 생성해냄 (end of token이 나올 때까지)
> 이러한 인코더-디코더 구조를 가져가는 것은 디코더만으로 이루어진 모델에 비해 다음과 같은 장점이 있음 :
- 양방향 representation을 생성할 수 있음
- 인코더와 디코더 구조를 다르게 가져갈 수 있음
- 일반적으로 문제 지시문이 더 길기 때문에 인코더는 1536토큰, 디코더는 768 토큰 길이 사용
- 인코더는 shallow하게, 디코더를 deep하게 가져가는 것이 성능이 더 좋았음
> 모델은 3억 개 파라미터 ~ 410억 파라미터 모델까지 다양한 사이즈를 학습
- 9B모델과 41B 모델은 모델 병렬화를 통해 학습했으며, 각 샤드 당 하나의 key, value가 학습된
- 모델은 JAX와 Haiku로 만들어 TPUv4에서 16 bfloat precision으로 학습됨
> 트랜스포머 아키텍처의 효율성 고려
- 효율적인 샘플링을 위해 multi-query attention 활용
: 각 attention 블록에서 query head는 모두 사용하되, key와 value는 공유함으로써 샘플링의 큰 병목이 되는 메모리 사용과 업데이트 비용을 줄임
> 토크나이저는 SentencePiece tokenizer 사용
- 깃허브 & CodeContests 데이터에 대해 vocab size = 8000으로 학습함
- 인코더와 디코더는 같은 토크나이저 활용
AlphaCode Step-by-Step
알파코드 개발에는 크게 다음의 네 가지 과정이 있다 :
1. 사전학습
: 깃허브 데이터에 대해 일반적인 언어모델 목적함수를 활용하여 Transformer기반의 언어 모델 사전학습
> 이 과정은 모델이 사람의 코딩 방식 공간을 학습함으로써 탐색 공간을 크게 줄이는 역할을 함
> 사전학습 태스크
- 인코더 : Masked Language Modeling (인풋의 일부를 마스킹한 후, 해당 토큰이 무엇인지 맞추는 태스크)
- 디코더 : Next Token Prediction (다음 토큰을 예측해나가는 태스크)
> 깃허브 데이터로부터 유니폼하게 기준점을 샘플링하고, 기준점 이전을 인코더, 기준점 이후 내용을 디코더 아웃풋으로 사용
> 1B 파라미터 모델은 256배치로 10^6 스텝 동안 사전학습. 더 큰 모델은 더 많이, 작은 모델은 이보다 더 적게 학습했으나, 41B 모델은 너무 큰 관계로 상대적으로 덜 학습하였고, 이에 따라 스케일 대비 덜 학습됨 (under-trained)
2. Fine tuning
: 경쟁프로그래밍 데이터셋에 대해 GOLD with tempering을 학습 목적함수로 fine-tuning
> CodeContest데이터의 자연어 지시문은 인코더, 프로그램 솔루션을 디코더에 활용하며, 사전학습과 마찬가지로 MLM loss와 next-token prediction loss를 학습 시그널로 활용
> 여기에 더하여 tempering, value conditioning and prediction, GOLD을 도입하여 솔루션 도출 확률을 높임
Tempering
- 아웃풋 로짓을 temperature T로 나눔으로써 softmax를 취했을 때 결과를 더 날카롭게 하거나 스무딩하는 기법
- T = 0.2 <1 로 설정하면 학습 분포가 날카로워지고, 결과적으로 추론 시에는 분포를 스무드하게 하여 오버피팅을 방지하는 것을 발견함. 이는 tempering에 있어 기존에 제시되었던, T > 1를 사용하여 추론 분포를 날카롭게 하는 것을 권고한 논문과는 반대의 인사이트임.
- 샘플링 시의 T'는 검증 데이터에 대해 찾아냈으며, tempering만 사용할 시에는 T' = 0.12, tempering과 GOLD를 모두 사용해 학습한 모델에 대해서는 T'=0.25를 사용하는 것이 좋았음
Value Conditioning & Prediction
- CodeContests데이터에는 옳은 제출 솔루션과 틀린 솔루션이 모두 포함되어 있음
- 이 둘을 구분하기 위해 value conditioning & prediction을 도입하여 모델에 잘못된 시그널을 주지 않도록 가이드함
- Value Conditioning : 학습 시에는 디코더의 아웃풋이 되는 제출코드가 맞는 코드인지(correct) 아닌지(incorrect)를 조건부로 알려주고, 추론 시에는 항상 조건=correct로 설정하여 코드를 샘플링
- Value Prediction : 학습 중 마지막 레이어의 토큰 representation으로부터 코드가 맞는지 아닌지 분류하는 auxiliary 태스크를 도입하여 학습함. 이 과정은 추론 시에는 사용되지 않음
- Value Conditioning은 아래와 같이 메타 데이터와 함께 모델의 인풋으로 주어지게 된다 :
GOLD
- 코딩 테스트는 하나의 문제에 대해 여러 개의 답변이 존재할 수 있는 one-of-many 태스크에 해당한다
- 일반적인 maximum likelihood 목적함수는 학습 데이터에 있는 여러 개의 솔루션에 웨이트를 줘서 학습하는데, 실제 정답인 것을 최대한 맞추어야 하는 recall과 비슷하다. 하지만 경쟁 프로그래밍 안에서는 한정된 제출 가능한 개수 내에서 하나라도 맞는 솔루션을 찾아내는 것이 중요하고, 이는 precision이 높아야 하는 작업이다.
- 따라서 알파코드는 모델이 이미 높은 likelihood를 할당한 토큰으로부터 학습함과 동시에, 분포에 존재하지 않는 토큰은 무시할 수 있는 offline 강화학습 알고리즘인 GOLD의 변형을 사용한다.
3. Large Scale Sampling
: 각각의 문제에 대해 모델로부터 다량의 코드 샘플을 생성
- 트랜스포머 기반 모델은 샘플링 시 병렬화가 가능하기 때문에 문제 하나당 수백만의 샘플 코드를 생성하는 것이 가능하다
- 충분히 많은 샘플을 일단 생성하기 위해 다음의 과정을 거친다 :
① 코드의 절반은 파이썬, 나머지 절반은 C++을 사용해 코드를 샘플링하도록 설정
② 자연어 프롬프트의 문제 태그와 평점을 랜덤화하여 설정
③ 상대적으로 높은 sampling temperature을 사용하여 샘플링
> 실험 결과 다양한 temperature을 사용하는 것은 점수 상승에 영향이 적었으므로, 검증 데이터로 최적화한 T' 사용
- Top-k나 nucleus 샘플링도 실험해 보았으나 성능 향상이 없었으므로, 일반적인 temperature을 사용한 샘플링 적용
4. 필터링 & 클러스터링
: 필터링 등을 적용하여 최종적으로 hidden 테스트 케이스에 평가할 최대 10개의 후보 제출 코드를 선별
필터링
- 문제에서 제시한 테스트 케이스를 사용해 실행한 후 통과하는 코드만을 남기는 방식으로 약 99%의 코드를 필터링
- 하지만, 이러한 과정 후에도 여전히 수천 개의 코드가 남아 있는 경우가 있음
- 문제의 10% 정도는 난이도가 높은 문제로, 필터링을 통해 남는 코드가 하나도 없었음 (답안 찾기 실패)
클러스터링
- 필터링 후에도 수백~수천 개의 코드가 남아있는 경우, 제출 제한 개수인 10개를 선택하는 과제가 남아있다
- 이때 랜덤하게 코드를 선택하는 것은 10번밖에 안 되는 소중한 기회를 낭비하는 경우가 생길 수 있음
- 따라서 클러스터링을 통해 의미적으로 같은 프로그램을 그루핑하고, 그룹 내에서 대표 코드를 샘플링하는 방식 채택
- 의미적으로 같은 프로그램을 찾기 위해 알파코드는 테스트 인풋 생성 모델을 따로 학습해 둠
⇒ 추가적인 테스트 인풋에 대해 같은 아웃풋을 내는 프로그램은 같은 그룹 내에 있다로 분류하는 방식
⇒ 테스트 인풋 생성 모델은 학습 데이터 필터링에 필요한 테스트 케이스를 만들어냈던 mutation 기반의 모델과는 다른 모델이다. 기존 모델의 경우, 올바른 인풋과 아웃풋 케이스를 만드는 것이 중요했다. 반면, 클러스터링 단계에서 만들어낸 테스트 케이스는 꼭 유효할 필요는 없다. 유효하지 않은 데이터라도 코드를 클러스터링하는 데에 활용하기는 충분하기 때문이다.
- 클러스터링을 진행한 이후 가장 큰 클러스터로부터 차례로 코드를 샘플링하는 방식이 성공 확률이 높았다.
실험 결과
(5.1) Codeforces 대회 평가 결과
> 2021년 12월 1일부터 2021년 12월 28일까지 Codeforces 플랫폼에서 실제 개최된 모든 대회에 참가해 모델을 평가
- 각 대회에는 5,000명 이상의 참여자가 참가했으며, 총 10개의 대회가 열림
- 참가한 알파코드 시스템은 41B모델과 9B모델을 앙상블하고 클러스터링을 진행한 모델이 validation 데이터에서 가장 좋았으나, 실제로는 41B 모델만으로 클러스터링을 한 모델보다 성능이 떨어진 것으로 나타남
> 각 콘테스트에서는 알파코드를 실시간으로 작동시켜 각 문제에 대한 코드를 샘플링하고 필터링한 후 클러스터링 하여 제출하는 과정을 거쳤고, 각각의 대회에서 알파코드의 성적을 얻음. 첫 번째 시도 후에는 이 과정을 두 번 더 수행하여 분산과 10개 이상의 제출을 했을 때의 성능을 측정함.
> 컴퓨터 프로그램이 대회에 참가하여 사람 참가자들과 경쟁한 것은 알파코드가 최초의 사례
- 각 문제에 대해 제출 기회를 10번으로 제한했을 때, 평균적으로 알파코드는 54.3%의 랭킹을 달성했고, 실제로는 평균적으로 2.4번의 제출로 정답을 달성하였다. 10회의 제출은 Codeforces상에 1238등 정도에 해당하고, 6개월간의 참여자 중 상위 28%에 해당한다.
- 10회 이상의 제출을 시도했을 때는 평균 48.8%의 랭크를 달성했고, 평균 28.8회의 제출 끝에 문제를 풀 수 있었다.
(5.2) CodeContests 평가 결과
> CodeContests 데이터의 검증 & 테스트 데이터에 대해서 모델을 평가하였다. 이때 사용된 테스트 데이터는 (5.1)에서 사용된 콘테스트를 포함하는 초집합(superset)이다. 이 데이터에 대한 평가 지표는 실제 대회에 참가하는 등의 과정을 포함하지 않기 때문에 variance가 적고 평가가 용이하다
> 평가 지표
- pass@k : k개의 제출을 했을 때 모델이 hidden 테스트 케이스를 통과한 비율. 이 매트릭은 샘플링 과정에서 search 측면의 성능을 측정하는 데에 주로 사용됨
- 10@k : 각 문제에 대해 k개의 샘플을 뽑았지만, 그중에 10개 만을 사용해 평가했을 때 문제를 푼 비율. 이 매트릭은 필터링 과정에서 모델이 많은 샘플을 생성했을 때 얼마나 효율적으로 샘플을 추리는 지를 평가하는 데에 주로 사용됨
각각의 문제에 대해 최대 백만 개의 샘플을 생성했을 때, 검증 데이터에 대해 34.2%의 문제를 풀 수 있었고, 10만 개 생성 시 검증 데이터는 31.8%, 테스트 셋트에서는 29.6%의 문제를 풀 수 있었다. 데이터는 시간 순서에 따라 학습/검증/테스트 데이터셋을 분할하였기 때문에, 검증 및 테스트 데이터에는 학습 중에 볼 수 있었던 문제가 없다.
검증 데이터와 테스트 데이터에서의 성능 차이는 문제의 분포에 변화가 있었기 때문일 수 있고, 모델의 오버피팅도 기여했을 수 있다. 다만, 검증 및 테스트 데이터에서 성능에 기여한 요소는 일관적이다 :
- 큰 모델의 성능이 우세, 즉 41B 모델은 항상 9B 모델보다 좋았다.
- 클러스터링을 사용했을 때, 항상 성능 향상이 있었다.
(5.3) CodeContests ablations & Results
(5.3.1) 파라미터 개수, 계산량, 샘플 개수, 데이터 사이즈에 따른 성능
<그림 6>은 X축에 샘플링한 코드의 개수, Y축에 CodeContests 검증 데이터셋에서의 성능을 표시한 도표이고, 각각의 선은 모델 사이즈를 보여준다. 보라색 선이 가장 큰 41B 모델로, 모델 사이즈가 클수록 성능이 좋다는 것을 볼 수 있다. 또한, 샘플링한 코드 수가 많을수록 성능은 향상되었다. 또한 (a) 도표를 볼 때, 똑같이 10개의 샘플만을 제출하더라도 샘플링한 코드가 많을수록 성능은 크게 증가하였다.
<그림 7>은 학습 및 샘플링 시에 사용한 자원에 따른 성능을 보여준다.
이러한 실험 결과는 다음의 세 가지로 요약할 수 있다
1) Solve rate(해결률)는 더 많은 샘플을 사용할 때 log-linear 하게 증가한다
: 10@k와 pass@k 지표는 둘 다 많은 샘플을 사용할 때 k가 커짐에 따라 대략적으로 log-linear하게 증가했다. <그림 7>의 (a) 그림을 보면 10@k 지표는 샘플링 예산이 많을 때 log-linear 증가 추세가 약간 감소하였다. 10개의 코드만을 최종 제출하더라도 충분한 양의 코드를 샘플링할 때 성능이 증가하는 것은 탐색 공간을 충분히 탐색하는 것이 중요하다는 것을 보여준다. 하지만 solve rate를 향상시키기 위해서 샘플링 사이즈를 지수적으로 증가해야 한다는 것은 샘플링 비용이 빠르게 소진될 수 있다.
2) 더 나은 모델은 scaling curve에서 더 가파른 기울기를 가진다
: <그림 6>에서 큰 스케일의 모델은 더 나은 성능을 보일 뿐만 아니라 더 많은 샘플링에 따른 성능 향상의 기울기가 더 컸다. scaling curve의 기울기가 크다는 것은 더 적은 표본으로 동일한 해결률에 도달할 수 있다는 것이다. 따라서 1)의 결과와 같이 더 높은 해결률을 달성하기 위한 샘플의 수가 지수적으로 폭증하는 상황에서, 더 나은 모델을 확보하는 것이 해결책이 될 수 있다.
3) 해결률은 더 많은 계산 양에 따라 log-linear 하게 증가한다
: <그림 7>의 (a) 그림에서 볼 수 있듯이 학습 시 사용한 자원에 log-linear 하게 해결률이 증가한다. 도표의 곡선에서 각 점은 하나의 모델에서의 성능을 보여준다. <그림 7>의 (b)는 추론 시 소요되는 계산량과 solve rate의 관계를 보여주는데, 큰 모델의 경우 하나의 코드 샘플을 생성하는 데에 더 많은 계산 자원이 필요하지만, 많이 샘플링할수록 같은 샘플링 비용을 사용할 때 작은 모델보다 성능이 좋은 것을 볼 수 있다.
(5.3.2) 샘플링 속도 개선을 위한 아키텍처 수정
(5.3.1)에서 더 많은 코드를 샘플링하는 것이 성능 향상에 중요한 요소라는 것이 밝혀졌다. 따라서 샘플링 속도를 높이는 아키텍처는 한정된 예산 내에서 속도를 높임과 동시에 solve rate를 높일 수 있다. 알파코드는 두 가지 아키텍처 변형을 선택했다 :
(1) 인코더와 디코더의 구조가 비대칭적인 구조
(2) multi-query attention - 각 attention head내에 key를 공유하고 attention block 내에서 value를 공유하는 구조
이 두 가지 구조의 효과를 분석하기 위해 1B모델을 사용해 ablation study를 진행하였다.
위의 표에서 볼 수 있듯이, multi-query attention을 사용한 인코더-디코더 구조의 모델이 샘플링 속도가 크게 향상되었다.
(5.3.4) Model enhancement
모델 학습에 사용한 방법들에 따른 성능 향상 ablation study 결과는 아래와 같다.
(5.3.5) Filtering & Clustering
Filtering using example tests: <표 9>는 샘플 테스트를 통과한 모델 샘플의 비율과, 적어도 하나의 샘플 테스트를 통과한 문제의 비율을 보여준다. 이 표는 모델이 생성한 전체 샘플 셋으로부터 계산한 결과로, 구문적인 에러가 있는 프로그램을 필터링하지 않은 채 얻은 결과이다. 전체적으로 모델이 작성한 코드 중 1%보다 적은 비율이 테스트 케이스를 통과하였고, 즉 example test를 사용해 필터링을 하면 모델 샘플의 99% 이상을 거를 수 있다 뜻이다. 올바른 솔루션을 찾아낸 문제에서는 example test를 통과한 비율이 그렇지 않은 문제의 2배 정도 되었지만, 여전히 낮은 수치였다.
Clustering: 올바른 솔루션은 example test 이외에 숨겨진 테스트 케이스에 대해서도 작동해야 하기 때문에 모든 공개된 example test를 통과한 코드 중에서도 올바른 코드를 선별하는 작업이 남아있다. 필터링은 수백만 개의 샘플의 99%를 제거하지만, 여전히 수천 개의 후보 코드가 남아있다. 클러스터링은 테스트 인풋에 대한 샘플 코드의 결과에 따라 샘플을 그루핑하고, 효과적으로 코드를 골라내는 역할을 한다.
<그림 8>은 필터링 / 클러스터링 방법을 활용할 때 Solve rate를 보여준다.
(5.4) APPS 데이터셋에서 성능
기존에 프로그래밍 벤치마크 데이터셋으로 사용되었던 APPS 데이터셋에 대한 성능 비교 :
알파코드의 가능성과 한계
(6.1) 학습 데이터로부터 코드를 단순히 복사하는 문제
대규모 언어 모델에 있어 대량의 데이터에 대해 학습함에 따라 다운스트림 태스크를 학습 데이터를 단순히 암기함으로써 해결할 수도 있다는 것은 일반적인 우려사항이다. 경쟁 프로그래밍은 언어모델이 진정으로 문제 해결 능력을 가지고 새로운 문제를 해결할 수 있는지 확인해볼 수 있는 좋은 태스크이다.
학습 데이터의 솔루션을 베끼기만 해서는 문제를 풀 수 없겠지만, 비슷한 문제가 있다면 기존 솔루션에 입각하여 중요한 부분을 대부분 복사하여 사용할 수는 있다. 이를 조사하기 위해 validation 문제에 대해 모델이 생성한 솔루션에 대해 전체 학습 데이터셋(사전학습 깃허브와 fine-tuning용 CodeContests 데이터)과 공백을 제외하고 가장 길게 겹치는 문자열을 검색하였다. 그리고 그 길이를 사람이 작성한 솔루션이 겹치게 되는 길이와 비교하였다.
<그림 9>는 이 실험에 대한 결과를 보여준다. 모델 샘플이 겹치는 길이가 조금 더 길긴 했지만, 그 분포가 사람의 것과 거의 비슷하다는 것을 알 수 있다. 학습에서 사용한 코드와 가장 긴 부분이 겹쳤던 코드는 인풋 데이터를 읽고 파싱 하는 boilerplate code를 포함하는 부분으로, 문제를 해결하는 핵심적인 로직과는 관련이 적은 부분이었다. 즉, 알파코드는 학습 데이터로부터 긴 코드블럭을 복사하지 않는다라는 결론을 낼 수 있다.
겹치는 문자열에 더해 50개의 모델이 생성한 솔루션에 대한 질적인 분석을 추가로 진행했다. 왼쪽 코드는 모델이 작성한 코드에 대해 fine-tuning 데이터에서 찾을 수 있는 가장 긴 문자열들을 색칠해본 결과이다. 예를 들어, 가장 길게는 오렌지 색으로 색칠된 구문이 있고, 그다음은 붉은색으로 색칠된 부분... 인 색이다.
하이라이팅 된 부분을 보면 알 수 있듯이, 코어 로직은 여러 개의 색깔이 섞여있고, 모델이 학습 데이터로부터 핵심 로직을 복사했다고 보기 어렵다.
(6.2) 모델 솔루션의 특징
알파코드 모델의 크기별로 사용한 언어에 따라 생성된 코드 샘플 중 구문적으로 옳은 샘플의 비율을 측정해보았다. 그 결과, Python 언어가 구문 오류가 없는 샘플의 비율이 가장 높았으며, C++은 Python에 비해 배우기 어려운 언어였음을 알 수 있다.
더 나아가 dead code, 즉 프로그램에 불필요한 라인을 생성한 비율을 측정해보았다. 이런 코드는 학습 데이터에도 존재하는데, 참여자들이 사용하지 않는 패키지를 import하거나, 함수를 복사 붙여넣기한 경우가 있기 때문이다. dead code가 많다는 것은 모델이 작성하고 있는 코드에 대해 잘 이해하지 못하고 있다는 증거이기도 하다.
Dead code 비율을 조사하기 위해 파이썬의 Abstract Syntax Tree의 코드 포맷 모듈을 적용하여 불필요한 코드 제거 후, 원본과의 길이를 비교해 보았다. <그림 11>에서 볼 수 있듯이 알파코드는 사람과 거의 비슷한 양의 dead code를 사용한 것으로 나타났다.
다음으로 모델 크기와 문제의 유형에 따른 모델의 해결률을 조사하였다. 당연한 결과이지만, 모델 규모가 클수록 전반적으로 해결률이 상승했다. <표 11>을 보면 알파코드는 bitmask, sorting, maths, 그리고 greedy search에서 잘 작동하나, dynamic programming이나 constructive algorithm에서 성능이 떨어지는 것을 볼 수 있다.
(6.3) 문제 지시문에 대한 민감도
** 이 부분은 appendix E.3에 상세히 나와있음
문제에 대한 설명이 모델 성능에 미치는 영향을 조사하기 위해 문제 지시문(problem description)에 대한 모델의 민감도를 조사하였다. 전반적으로 알파코드는 문제 지시에 생기는 중요한 변화에 민감하게 반응하고, 추가적으로 주어지는 정보를 활용하는 것으로 나타났다. 즉, 모델은 주어지는 설명의 대부분을 무시하지 않고 문제 유형에 맞는 모든 가능한 해결책을 강제적으로 찾고자 한다. (예. 문제 지시문에 "소수"라는 단어가 들어있다면, 소수와 관련된 무든 알고리즘을 사용)
(a) : 문제에 간소화된 설명만 나와있을 경우 (실제 콘테스트에는 존재하지 않는 경우) 더 높은 해결률을 보임
(b) : 관련은 있지만 다른 문제가 주어져 있을 때 해결률이 급격히 떨어졌으나, 같은 문제를 다른 방식으로 묘사하는 경우에는 영향력이 별로 없음
(c)-(h) : 유의어 단어 교체, 타입 정보의 생략 등에는 모델이 영향을 받지 않으나, 더 큰 변화(단어 삭제 등)에는 반응
(f) 모델은 지시문의 각기 다른 부분에 의존하며, 특히 구체적으로 설명하는 부분에 의존한다는 것을 알 수 있음
(6.4) 메타데이터에 대한 민감성
샘플링 시에 다양성을 높이기 위해 메타데이터를 랜덤하게 제공하였다. 메타정보는 문제의 종류 (binary search / brute force ..), 평점(문제의 난이도), 프로그래밍 언어, 그리고 솔루션이 옳은지 아닌지 등을 포함한다.
(a) 모델은 메타데이터의 조건에 적절하게 코드를 생성하는가
=> 모델은 메타데이터의 조건에 따라 다른 태그가 제공되면 다른 코드를 생성
예를 들어 아래의 <Gregor andn Cryptography> 문제에서는 주어진 소수 P에 대해 다음의 조건을 만족하는 두 정수 a, b를 찾아야 한다; P를 a로 나눈 나머지가 P를 b로 나눈 나머지와 같음 (P mod a = P mod b) , 2<=a<b<=P .
이 문제를 풀기 위해 단순히 모든 경우의 수를 대입해보는 brute-force 방법을 사용하고 싶을 수 있지만, 정수론을 사용하면 더 쉽게 솔루션을 찾을 수 있다 : P는 홀수여야 하고, 따라서 P를 2로 나눈 나머지와 P를 (P-1)로 나눈 나머지가 모두 1이어야 한다는 것이다.
이 문제에 대한 코드를 샘플링할 때, "brute force"라는 태그와 "number theory(정수론)"라는 태그를 각각 사용해 결과를 뽑아보았다. 그 결과 brute force 태그를 사용한 솔루션은 두 개의 루프 구조를 가지지만, number theory를 사용한 솔루션은 그러한 루프 구조 없이 코딩을 완성하였다.
(b) 메타데이터가 주어지지 않는 테스트 시에 어떤 셋팅으로 메타 데이터를 생성하는 것이 가장 좋은가
=> 태그와 평점은 랜덤하게 샘플링하되, 솔루션은 CORRECT 조건으로 샘플링해야 한다
랜덤 태그는 샘플의 다양성을 높이거나 실제로 유용한 힌트를 제공하는 역할을 할 수 있다. <표 13>을 보면, (b) 테스트 시점에 실제 태그를 제공하는 것은 불가능하지만, (c)와 같이 고정된 랜덤 태그를 제공하는 것보다 성능이 좋았다. 하지만 최고의 성능은 (a)와 같이 샘플링 시 랜덤한 태그를 제공하여 다양성을 주는 것이 solve rate를 높인다는 것을 알 수 있다.
(6.5) Validation loss는 solve rate 개선의 징표가 되지 않았다
알파코드를 fine-tuning할 때 validation language modelling loss는 1B 모델에서 50k 스텝부터 증가하기 시작했지만 학습 loss는 계속 감소하는 현상을 관측했다. 일반적으로 이것은 오버피팅의 증거가 된다. 하지만 validation loss의 증가에도 불구하고 solve rate는 50k 이상 학습해도 계속해서 개선되었다.
알파코드가 풀고자 하는 태스크는 one-of-many 태스크로, 샘플 중 하나라도 문제를 풀 수 있는 코드라면 문제가 풀렸다고 볼 수 있다. Fine-tuning에 사용된 CodeContests 데이터셋은 하나의 문제에 대해 여러 개의 솔루션을 포함한다. Solve rate를 측정하는 매트릭인 10@k 역시 k개의 샘플을 사용해 해결률을 측정한다.
즉, 해결률과 loss가 반비례하지 않는 원인은 모델은 학습 중에 일부 비정형적인 솔루션에서 보다 전형적인 솔루션으로 확률(probability mass)을 재할당하기 때문인 것으로 볼 수 있다. 이 과정에서 여러 개의 솔루션에 대해 측정되는 전반적으로 loss는 증가하게 될 수 있지만, 전형적인 솔루션이 solve rate를 높이기 때문에 오히려 해결률은 올라갈 수 있는 것이다.
Solve rate가 최종적인 매트릭이긴 하지만, 높은 분산과 계산 비용으로 인해 학습 스텝 수를 결정하는 데 사용하기 어렵다. Validation loss가 최종 성능과 상관관계를 가지도록 개선함으로써 의사결정 프로세스를 더 효율적으로 할 수 있는데, 이는 future work로 남겨둔다.
'AI' 카테고리의 다른 글
| AI alignment - 인공지능과 사람의 <동상동몽> (2) | 2022.04.17 |
|---|---|
| [논문리뷰] GPT3의 새로워진 버전 - InstructGPT : 인간의 지시에 따른 결과물을 완성해내는 AI (3) | 2022.04.03 |
| [ML Ops] - 지속가능한 AI서비스를 위한 Model Drift의 인지 및 관리 (0) | 2022.02.20 |
| [논문리뷰] Relative Position Representations in Transformer (0) | 2022.02.04 |
| [논문리뷰] Multimodal Neurons in Artificial Neural Networks (2) | 2021.11.21 |
