Abstract:
- In-Context Learning (문맥 기반 학습)에서 적합한 예시들을 선택하여 성능을 향상시키는 방법에 대한 논문임.
- 이 논문의 제목에 있는 Support Examples 라는 건 모델이 학습을 잘 할 수 있도록 도와주는 예시들을 말함. 이는 모델이 학습할 때 주어진 문제를 잘 설명할 수 있는 예시를 찾아 성능을 극대화 하는 것.
- In-Context Learning 은 주어진 예시들 간의 강한 상호 의존성 때문에 최적의 조합을 찾는 문제는 NP-hard 조합 문제로 분류됨. 또한 모든 가능한 예시들의 순열을 확인하는 것은 비현실적이기도 하다.
- 여기서는 최적의 예시를 찾는 방법으로 LENS (fiLter-thEN-Search) 방법 을 소개함:
- 1단계: 예시 필터링 - InfoScore 를 도입해서 데이터셋에서 각 예시가 문맥에서 얼마나 유용한지 평가함. 이를 바탕으로 정보가 적은 예시들을 걸러내고 필터링 과정을 통해 중요한 예시들을 선별함.
- 2단계: 다양성 기반 탐색 - 다양한 예시 순열을 반복적으로 평가하고 개선하여, 주어진 과제를 충분히 설명할 수 있는 예시 조합을 찾는 것.
- 이런 LENS 방법을 적용한 결과 크게 성능이 향상되었다고 함.
Introduction:
- 논문에서는 전체 데이터셋을 잘 대표하고 정보량이 많은 소수의 예시들을 Support Examples로 선택하는 방법을 제안함.
- 이는 전통적인 머신 러닝 방법인 서포트 벡터 머신(SVM) 에서 영감을 받았다고 함:
- SVM 에서 선택된 서포트 벡터는 두 클래스를 최대한 안정적이고 넓게 분리할 수 있도록 결정 경계를 형성하는데 중요한 포인트들임. (마진 최대화)
- 두 클래스가 서로 가까이 있다면 분리하기에는 적절하지 않을거임. 반면 마진을 최대화해서 분리하면 두 클래스 경계가 명확해져서 안정한 분리가 가능함.
- ICL에서 선택된 예시들은 LM에게 중요한 작업 정보를 제공하며, 그 수량도 제한적이기 때문에 Support Examples라고 함.
- 예시들 간의 강한 의존성:
- 예시 순서의 민감성: 이전 연구(Lu et al., 2022)에 따르면, 동일한 예시 집합이라도 순서에 따라 성능이 크게 달라질 수 있다는 걸 발견함. 어떤 경우에는 무작위 추측 수준의 성능을 보이다가도, 순서를 바꾸면 최첨단 성능을 나타낼 수 있다고 함. 예시 조합의 영향:
- 예시 조합의 영향: 논문에서는 Table 1을 통해 두 개의 예시를 개별적으로 사용할 때보다 조합해서 사용할 때 성능이 오히려 저하되는 현상을 보여주기도 한다고 함. 이는 이는 예시들 간에 조합적인 의존성이 있음을 나타냄
- 모든 예시 조합 탐색의 비현실성: 예시들의 의존성을 고려하기 위해 모든 가능한 예시 조합을 나열하고 성능을 확인하는 것은 이론적으로 가능하지만 조합 폭발 (combinatorial explosion) 로 인해 실제로는 불가능하긴 함.
- 여기서는 LENS 라는 방법을 제안함. LENS는 fiLter-thEN-Search의 약자로, 두 단계로 구성된 지원 예시(support examples) 를 찾는 방법임.
- 1단계: 예시 필터링:
- 정보량이 많은 예시 선별: 데이터셋에서 개별적으로 정보량이 많은 인포메이티브(informative) 예시들을 선별함.
- InfoScore 제안: 언어 모델의 피드백을 기반으로 예시의 문맥 내 정보량(in-context informativeness) 을 평가하는 InfoScore라는 새로운 척도를 도입해서 사용한다.
- 진행형 필터링 과정: 정보량이 적은 예시들을 점진적으로 걸러내는 과정을 통해 중요한 예시들을 남김.
- 2단계: 다양성 기반 예시 탐색:
- 반복적 개선 및 평가: 선택된 예시들을 반복적으로 개선하고 평가하여, 작업을 완전히 나타낼 수 있는 지원 예시들을 지원 예시를 찾는다.
- 다양성 고려: 예시들 간의 다양성(diversity) 을 고려하여, 예시들의 조합이 예측 성능에 미치는 영향을 최적화한다.
- 1단계: 예시 필터링:
- 지원 예시들은 무작위 예시들과는 다른 경향성을 보였다고도 함:
- 순서에 대한 민감도가 적음: 지원 예시들은 무작위 예시들에 비해 예시 순서 변화에 덜 민감
- 정답 레이블의 중요성: 지원 예시에서는 실제 정답 레이블(ground truth labels) 이 중요하다고 함. 이전 연구(Min et al., 2022b)는 무작위 예시에서는 레이블이 중요하지 않다고 했지만, 지원 예시에서는 그렇지 않았음.
- 모델 간 전이 가능성: 한 언어 모델에서의 지원 예시들은 다른 크기나 사전 학습 데이터가 다른 언어 모델에서도 잘 작동하며, 무작위 예시들보다 여전히 우수한 성능을 보였다고 함.
예시 간의 조합 의존성:
정보량이 많은 예시 필터링 (Informative Examples Filtering):
- 데이터셋에서 개별적으로 정보량이 많은(informative) 예시들을 선별하여, ICL에서 중요한 예시들을 찾는 방법임.
- InfoScore 를 이용한 정보량 판단 방법:
- 전체 데이터셋에 대해 모든 예시의 InfoScore를 계산하면 계산량이 O(|\mathcal{D}|^2) 가 되어 비현실적이게 됨. 그래서 이를 해결하기 위해 진행형 필터링 과정(progressive filtering process) 을 제안한다.
진행형 필터링 과정 (Algorithm 1):
- 이 알고리즘은 대량의 데이터셋에서 정보량이 많은 예시들을 효율적으로 선별하기 위한 알고리즘임. 이 과정은 계산 효율성을 유지하면서도 중요한 예시들을 찾아내기 위해 설계되었다고 한다.
- 알고리즘의 전체 과정은 다음과 같다:
Algorithm 1: Progressive Example Filtering
Input: Training set 𝓓 = {e_i}^n_{i=1}, language model G, desired candidate size m, progressive factor ρ, initial score data size l.
Output: Individually informative examples 𝓓'
1: 𝓓' ← 𝓓
2: S ← Randomly sample l examples from 𝓓.
3: while |𝓓'| > m do
4: for e_i ∼ 𝓓' do
5: s(e_i) ← I(e_i, S)
6: end for
7: if |𝓓'| / ρ < m then
8: 𝓓' ← the top-m of 𝓓' using {s(e_i)}_{i=1}^{|𝓓'|}
9: Break;
10: else
11: 𝓓' ← the top (1/ρ) of 𝓓' using {s(e_i)}_{i=1}^{|𝓓'|}
12: end if
13: S' ← Randomly sample l * (ρ - 1) examples from 𝓓
14: S ← S ∪ S'
15: end while
16: return 𝓓'- 입력 파라미터에 대한 설명:
- mathcal{D} = { e_i }_{i=1}^n: 전체 훈련 데이터셋입니다. 각 예시 e_i 는 입력과 레이블로 구성됩니.
- 언어 모델 G : In-Context Learning에 사용되는 언어 모델입니다.
- 원하는 후보 크기 m : 최종적으로 남길 예시의 개수입니다.
- 진행 비율 \rho (rho): 필터링 단계마다 데이터셋 크기를 줄이는 비율입니다.
- 초기 점수 데이터 크기 l : 초기 단계에서 InfoScore를 계산하기 위해 사용할 작은 데이터셋의 크기입니다.
Algorithm 1 주요 과정 단계별 분석:
- 초기화
1: 𝓓' ← 𝓓
2: S ← Randomly sample l examples from 𝓓.- \mathcal{D}{\prime} 를 전체 데이터셋 \mathcal{D}로 초기화합니다.
- 점수 집합 S 를 생성합니다
- \mathcal{D}에서 무작위로 `l` 개의 예시를 샘플링합니다.
- 이 점수 집합 S 는 각 예시의 InfoScore를 계산하는 데 사용됩니다.
- 초기에는 작은 크기의 S 를 사용하여 대략적인 평가를 수행합니다
- 반복 과정 시작
3: while |𝓓'| > m do- 원하는 후보 크기 m 에 도달할 때까지 반복합니다.
- 현재 후보 예시들에 대해 InfoScore 계산
4: for e_i ∼ 𝓓' do
5: s(e_i) ← I(e_i, S)
6: end for- 현재 후보 예시 집합 \mathcal{D}{\prime}에 있는 각 예시 e_i 에 대해 InfoScore s(e_i) 를 계산합니다.
- 여기서 I(e_i, S) 는 예시 e_i 와 점수 집합 S 를 사용하여 계산됩니다.
- InfoScore는 예시 e_i 가 다른 예시들의 예측에 얼마나 기여하는지를 나타냅니다.
- 필터링 결정
7: if |𝓓'| / ρ < m then
8: 𝓓' ← the top-m of 𝓓' using {s(e_i)}_{i=1}^{|𝓓'|}
9: Break;
10: else
11: 𝓓' ← the top (1/ρ) of 𝓓' using {s(e_i)}_{i=1}^{|𝓓'|}
12: end if- 현재 후보 예시 집합의 크기를 확인합니다.
- 만약 다음 단계에서 필터링했을 때 크기가 m 보다 작아지면:
- 현재 단계에서 바로 상위 m 개의 예시를 선택하고 반복을 종료합니다.
- 그렇지 않으면:
- 현재 후보 예시들의 상위 1/\rho 비율의 예시들을 선택하여 \mathcal{D}{\prime}를 업데이트합니다.
- 즉, 각 반복마다 후보 예시들의 수를 1/\rho 로 줄여나갑니다.
- 만약 다음 단계에서 필터링했을 때 크기가 m 보다 작아지면:
- 점수 집합 S 확장
13: S' ← Randomly sample l * (ρ - 1) examples from 𝓓
14: S ← S ∪ S'
15: end while- 다음 반복을 위해 점수 집합 S 를 확장합니다.
- \mathcal{D}에서 추가로 l \times (\rho - 1) 개의 예시를 무작위로 샘플링하여 S{\prime} 를 만듭니다.
- 점수 집합 S 에 S{\prime} 를 추가합니다.
- 이렇게 하면 다음 반복에서 더 많은 예시를 사용하여 InfoScore를 더 정밀하게 계산할 수 있습니다.
- 반복 종료 및 결과 반환
16: return 𝓓'- 원하는 후보 크기 m 에 도달하면, 선별된 예시 집합 \mathcal{D}{\prime}를 반환합니다
알고리즘의 핵심 아이디어 정리:
- 진행형 평가: 처음에는 작은 점수 집합을 사용하여 대략적인 InfoScore를 계산하고, 각 반복마다 점수 집합을 확장하여 더 정확한 평가를 수행함.
- 계산 효율성 유지: 모든 예시 간의 관계를 계산하면 계산량이 O(n^2) 이지만, 이 알고리즘은 작은 점수 집합과 진행형 필터링을 통해 계산량을 크게 줄인다.
- 유망한 예시에 집중: 유망한(정보량이 많은) 예시들은 반복될수록 더 많은 계산 자원을 할당받아 정확하게 평가됨.
- 질이 낮은 예시 배제: 정보량이 적은 예시들은 초기 단계에서 필터링되어 이후의 계산에서 제외됨.
- 점진적 정밀도 향상: 반복될수록 InfoScore 계산의 정확도가 높아질거임. 초기에는 대략적으로 평가하고, 중요한 예시들에 대해서는 더 정확한 평가를 할 것.
InfoScore 계산의 이해:
- InfoScore I(e_i, S) 는 예시 e_i 가 점수 집합 S 에 있는 예시들의 예측에 얼마나 기여하는지를 나타냄.
- 구체적으로, e_i 를 포함했을 때와 포함하지 않았을 때의 언어 모델의 예측 확률 차이를 계산함.
- 이 값이 클수록 e_i 는 다른 예시들의 예측을 개선하는 데 큰 기여를 하므로, 정보량이 많은 예시로 간주됨.
다양성 기반 예시 탐색(Diversity-Guided Example Search):
- 첫 번째 알고리즘에서 우리는 개별적으로 정보량이 많은 예시들의 집합을 얻었음. 하지만 예시들 간의 강한 의존성 때문에, 이 예시들을 단순히 조합하여 사용할 경우 성능이 저하될 수 있다.
- 그리고 우리는 조합 폭발(combinatorial explosion) 문제로 인해 모든 가능한 예시 조합을 평가하는 것은 불가능함.
- 예를 들어, 50개의 예시 중에서 8개의 예시를 선택하는 경우의 수는 약 5억 3천 6백만 가지이며, 예시의 순서까지 고려하면 더 많아짐.
- Diversity-Guided Example Search 는 필터링된 예시들 중에서 작업(task)을 완전히 나타낼 수 있는 지원 예시들의 조합을 찾는 걸 말함. 예시들의 다양성(diversity) 을 고려해서, 반복적으로 예시 조합을 개선하고 평가함으로써 최적의 예시 조합을 찾아보자.
- 주요 개념 및 방법:
- 예시들의 다양성(Diversity) 활용:
- 다양성은 예시들이 서로 다른 정보를 제공하여 모델이 다양한 상황에서 잘 작동하도록 돕는 걸 말함.
- 예시들이 너무 유사하면, 모델이 특정 패턴에만 과적합될 수 있다.
- 다양성 있는 예시들을 선택함으로써, 모델은 더 일반화된 성능을 보일 수 있다.
- 반복적 개선 과정:
- 초기 예시 조합(permutations)을 생성하고, 반복(iterations) 을 통해 예시 조합을 개선함.
- 각 반복에서, 예시들의 정보량과 다양성을 고려하여 조합을 업데이트함.
- 예시 교체 및 순서 변경:
- 예시 교체: 현재 조합에서 하나의 예시를 선택하여, 더 나은 예시로 교체
- 순서 변경: 예시들의 순서를 무작위로 섞어서 새로운 조합을 생성
- 빔 서치(Beam Search) 활용:
- 빔 서치(Beam Search) 를 사용하여 여러 후보 조합을 동시에 유지하고 업데이트함.
- 이는 지역 최적해(local optimum)에 빠지는 것을 방지하고, 더 넓은 탐색 공간을 커버할 수 있게 한다.
- 예시들의 다양성(Diversity) 활용:
Algorithm 2: Diversity-Guided Search:
Algorithm 2: Diversity-Guided Search
Input: Candidate examples 𝓓' = {e_i}^m_{i=1}, candidates’ feature {f(e_i)}^m_{i=1}, a small validation set V, iteration num I, beam size 𝐵, example substitution size 𝐵'
Output: A performant examples’ permutation.
1: 𝓔 = {E_j}^𝐵_{j=1} ← initialize 𝐵 examples’ permutations
2: for i in 1, 2, ⋯, 𝐼 do
3: 𝓔' ← {}
4: for E in {E_j}^𝐵_{j=1} do
5: for b in 1, 2, ⋯, 𝐵' do
6: e* ← Randomly sample an example from E
7: e*_new ← argmax_{e ∈ 𝓓'} s(e, E − e*)
8: E* ← Replace e* in E with e*_new
9: 𝓔' ← 𝓔' ∪ {E*}
10: end for
11: for b in 1, ⋯, 𝐵 − 𝐵' do
12: E* ← Randomly shuffle E
13: 𝓔' ← 𝓔' ∪ {E*}
14: end for
15: end for
16: 𝓔 ← Evaluate 𝓔' on V and get the top-𝐵
17: end for
18: return The top-1 of 𝓔
알고리즘 2 (Diversity-Guided Search): 주요 단계:
- 입력 파라미터 및 초기화
후보 예시 집합 \mathcal{D}{\prime} = \{ e_i \}_{i=1}^m : 필터링 단계에서 선별된 m 개의 정보량이 많은 예시들입니다.
예시들의 특징 벡터 \{ f(e_i) \}_{i=1}^m : 각 예시의 특징을 나타내는 벡터입니다. 이는 예시 간 유사도 계산에 사용됩니다.
작은 검증 집합 V : 예시 조합의 성능을 평가하기 위한 데이터셋입니다.
반복 횟수 I : 알고리즘의 반복(iteration) 횟수입니다.
빔 사이즈 B : 각 반복에서 유지할 후보 예시 조합의 개수입니다.
예시 교체 횟수 B{\prime} : 각 후보 조합에 대해 예시 교체를 수행할 횟수입니다.
- 초기화
1: 𝓔 = {E_j}^𝐵_{j=1} ← initialize 𝐵 examples’ permutations- 초기에는 B 개의 예시 조합을 생성합니다.
- 각 조합은 정보량과 다양성을 최대화하도록 구성됩니다
- 이는 이산 최적화(discrete optimization) 문제로 설정되며, CPLEX와 같은 최적화 솔버를 사용하면 구할 수 있다고 함.
- 반복(iteration)을 통한 예시 조합의 업데이트
2: for i in 1, 2, ⋯, 𝐼 do
- 예시 교체 및 순서 변경을 통한 조합의 개선
3: 𝓔' ← {}
- 예시 교체
4: for E in {E_j}^𝐵_{j=1} do
5: for b in 1, 2, ⋯, 𝐵' do
6: e* ← Randomly sample an example from E
7: e*_new ← argmax_{e ∈ 𝓓'} s(e, E − e*)
8: E* ← Replace e* in E with e*_new
9: 𝓔' ← 𝓔' ∪ {E*}
10: end for
- 예시 순서 변경
11: for b in 1, ⋯, 𝐵 − 𝐵' do
12: E* ← Randomly shuffle E
13: 𝓔' ← 𝓔' ∪ {E*}
14: end for
- 3: 새로운 후보 조합들을 저장할 빈 집합을 초기화 합니다.
- 4~10: 예시 교체 작업:
- 무작위로 예시 선택:
- 현재 조합 E 에서 무작위로 하나의 예시 e^ 를 선택합니다
- 최적의 교체 예시 선택:
- e^* 를 제외한 조합 E{\prime} = E - e^* 에 대해, 다음 점수 함수를 최대화하는 예시 e^_{\text{new}} 를 찾습니다:
- 예시 교체:
- e^* 를 e^_{\text{new}} 로 교체하여 새로운 조합 E^ 를 만듭니다.
- 새로운 조합 저장:
- 새로운 조합 E^* 를 후보 조합 집합 \mathcal{E}{\prime} 에 추가합니다.
- 무작위로 예시 선택:
- 4~11: 예시 순서 변경:
- 현재 조합 E 의 예시들을 무작위로 섞어서 새로운 조합 E^* 를 만듭니다
- 이는 예시 순서에 대한 민감성을 완화하고, 다양한 순서를 탐색하기 위함입니다
- 새로운 조합 E^* 를 후보 조합 집합 \mathcal{E}{\prime} 에 추가합니다
- 성능 평가 및 후보 조합의 선택
16: 𝓔 ← Evaluate 𝓔' on V and get the top-𝐵- 검증 집합 V 를 사용하여 후보 조합 집합 \mathcal{E}{\prime} 의 각 조합을 평가합니다.
- 성능 지표: 일반적으로 정확도(Accuracy), F1 스코어 등 작업에 적합한 평가 지표를 사용합니다
- 상위 B 개의 조합 선택: 평가 결과를 기반으로 성능이 우수한 상위 B 개의 조합을 선택합니다
- 최종 결과 반환
- 모든 반복(iteration)이 완료되면, 최종 후보 조합 집합 \mathcal{E} 에서 성능이 가장 우수한 조합(top-1) 을 반환합니다
점수 함수에 대한 설명:
예시의 특징 벡터 f(e) 설명:
f(e) = [c(e, e_1^S), c(e, e_2^S), \dots, c(e, e_{|S|}^S)]- 특징 벡터 f(e) 는 예시 e 의 특성을 수치적으로 표현한 벡터임.
- 이 벡터는 예시 e 가 점수 집합 S 의 다른 예시들과 얼마나 관련성이 있는지를 나타낸다. 즉, 이 벡터를 통해 예시 e 가 점수 집합의 예시들과 어떤 관계를 맺고 있는지를 수치화 한 것.
- 특정 예시 e 와 점수 집합에 있는 각 예시 e^S_i 와의 관계를 기여도 c(e, e^S_i) 라는 값으로 계산하여 이 값들을 모은게 특징 벡터임.
- 기여도 c(e, e^S_i) 는 예시 e 가 점수 집합에 있는 다른 예시 e^S_i 의 예측에 얼마나 도움을 주는지를 나타내는 값임.
알고리즘 2 (Diversity-Guided Search): 요약:
- 다양성 및 정보량 균형: 점수 함수 s(e, E{\prime}) 를 통해 예시의 정보량과 기존 조합과의 유사도를 모두 고려하여 최적의 예시를 선택합니다.
- 반복적 개선: 각 반복에서 예시 교체와 순서 변경을 통해 조합을 개선하고, 성능 평가를 통해 우수한 조합을 유지합니다.
- 빔 서치(Beam Search): 여러 후보 조합을 동시에 유지하고 업데이트하여 탐색 공간을 넓히고, 지역 최적해에 빠지는 것을 방지합니다.
- 예시 순서의 영향 완화: 순서를 무작위로 변경하여 순서에 따른 성능 변동을 줄이고, 다양한 조합을 탐색합니다.