데이터 전처리 정제 및 선택 주요 유사논문 색인마킹**
기존 LLM의 정보를 활용하여 효율적으로 pre-training dataset를 선택함으로써, 비용 효율적이고 성능이 좋은 새로운 LLM을 개발하는 방법을 제시함.
1. 문제 정의
2. 제안하는 해결책
3. 핵심 아이디어
4. 방법
상관관계 계수 \(\gamma_j\) 계산 (핵심 섹션)
\(\gamma_j = \sum_{1 \leq k, l \leq n \atop k \neq l} \text{sign}(y_k - y_l)(rank_j(x_{k,j}) - rank_j(x_{l,j}))\)
5. 이론적 근거
단일 지수 모델 가정
\(y_i = f(\langle \boldsymbol{\theta}^*, \mathbf{x}_i \rangle + \epsilon_i)\)
상관관계 계수의 이론적 정당화 (핵심 섹션)
\(\mathbb{E}[sign(y_i - y_j)(\Phi(\mathbf{x}_i) - \Phi(\mathbf{x}_j))] = \frac{2}{\pi} \sin^{-1}\left(\frac{\boldsymbol{\theta}^*}{\sqrt{2(1+\sigma^2)}}\right)\)
데이터 최적 선택
6. 장점
데이터 필터링 모델 https://huggingface.co/mlfoundations/fasttext-oh-eli5
본문
1. 서론
대규모 언어모델(LLM)의 학습에 있어 데이터 큐레이션의 중요성이 점점 더 커지고 있습니다. pre-training dataset셋의 규모가 2020년 200B 토큰 미만에서 현재 240T 토큰으로 증가함에 따라, 최고 품질의 LLM을 만들기 위한 최적의 데이터 부분집합을 식별하는 것이 중요해졌습니다. 이에 따라 다양한 데이터 선택 방법들이 등장했지만, 데이터 기반 접근 방식은 일반적으로 비용이 많이 드는 모델 재학습 단계를 포함하여 그 효과성에 제한이 있었습니다.
본 논문에서는 공개된 고성능 LLM들을 활용하여 데이터 평가와 선택을 수행하는 새로운 방법을 제안합니다. 이 방법의 핵심은 다음 두 가지 관찰 가능한 특성을 활용하는 것입니다.
접근 방식은 퍼플렉시티 상관관계를 통해 데이터를 선택하는 것욿, LLM의 로그 확률과 downstream 벤치마크 성능 간의 상관관계가 높은 데이터 도메인(e.g., wikipedia.org, stackoverflow.com 등)을 선택합니다.
2. 관련 연구
기존의 데이터 선택 방법들은 중복 제거, 퍼플렉시티 필터링, 수작업 큐레이션 등을 넘어서기 위해 다양한 접근 방식을 제시했습니다. 이들은 크게 두 가지 범주로 나눌 수 있습니다.
그러나 이런 방법들은 여전히 한계가 있어, Li et al. (2024)의 조사에 따르면 현재 많은 작업에서 SOTA 성능을 보이는 것은 여전히 단순한 fastText Classfier(Joulin et al., 2016)와 영어 필터의 조합입니다.
3. 문제 설정
목표는 pre-training dataset 분포가 downstream 벤치마크 성능에 미치는 영향을 예측하는 모델을 구축하고, 이를 통해 더 나은 언어 모델을 만드는 것입니다. 그러나 이 작업은 계산적으로 비용이 많이 듭니다.
전통적인 접근 방식은 다음과 같습니다.
이 방법은 \(N\)번의 LLM 학습을 필요로 하며, 특히 MMLU와 같은 어려운 벤치마크의 경우 수천만에서 수억 달러의 비용이 들 수 있습니다.
각 LLM의 Pre-training 데이터 추적(대리 함수)
접근 방식은 이와 달리 관찰적 설정을 고려합니다.
상기 식에서 핵심 아이디어는 관찰 불가능한 \(p_{i,j}\) (모델 \(i\)의 데이터 선택 정책이 문서 \(j\)를 샘플링할 확률)를 관찰 가능한 대리변수 \(x_{i,j}\)로 대체하는 것입니다. \(x_{i,j}\)는 모델 \(i\)에서의 문서 \(j\)의 음의 로그 가능도입니다.
이를 통해 음의 로그 가능도 \(\mathbf{x}_i\)와 벤치마크 오류 \(y_i\) 사이의 관계를 모델링하는 회귀 모델을 구축할 수 있습니다. 이 모델을 사용하여 손실 \(x_{i,j}\)를 감소시키면 오류 \(y_i\)가 빠르게 감소할 것으로 예측되는 도메인 \(j\)의 pre-training dataset를 선택할 수 있습니다.
LLM training dataset 추정 대리 함수 색인마킹*
퍼플렉시티-성능 가설을 단일 지수 모델(SIM)로 공식화합니다.
\[y_i = f(\langle \boldsymbol{\theta}^*, \mathbf{x}_i \rangle + \epsilon_i)\]이 단일 지수 모델의 장점은 다음과 같습니다.
이는 \(f\)의 단조성으로부터 직접 볼 수 있습니다.
\[\langle \boldsymbol{\theta}^*, \mathbf{x}_i \rangle + \epsilon_i < \langle \boldsymbol{\theta}^*, \mathbf{x}_j \rangle + \epsilon_j \Leftrightarrow f(\langle \boldsymbol{\theta}^*, \mathbf{x}_i \rangle + \epsilon_i) < f(\langle \boldsymbol{\theta}^*, \mathbf{x}_j \rangle + \epsilon_j).\]퍼플렉시티 상관관계를 통한 데이터 선택 (핵심 섹션)
가중치 \(\boldsymbol{\theta}^*\)는 어떤 도메인의 퍼플렉시티가 downstream 성능과 상관관계가 있는지 알려줍니다. 그러나 이것만으로는 데이터 선택에 충분하지 않습니다. 모델 가능도가 모델 성능과 어떻게 관련되는지 알더라도, 데이터 선택이 가능도에 어떤 영향을 미치는지는 알 수 없습니다. 더욱이 이 데이터 혼합물에서 가능도로의 관계는 관찰적으로 학습될 수 없습니다. 왜냐하면 어떤 모델의 데이터 혼합물도 알지 못하기 때문입니다.
그럼에도 불구하고, 데이터 혼합물을 최적화하는 깔끔한 접근 방식이 있습니다. 핵심 관찰은 다음과 같습니다. 만약 비음수 \(\boldsymbol{\theta}^*\)를 찾는다면, \(\boldsymbol{\theta}^*\)에 비례하여 샘플링하는 것이 항상 좋은 선택입니다.
이를 형식적으로 표현하면 다음과 같습니다.
명제 1: \(\boldsymbol{\theta}^*\) 가중치가 비음수라고 가정합시다. 그러면 관련 가능도가 \(\mathbf{x} \in \mathcal{X} \subset \mathbb{R}^D\)인 모델에 대해, \(\boldsymbol{\theta}^*\) 샘플링 분포에 대한 사전 학습 손실 \(\mathbb{E}_{j\sim\boldsymbol{\theta}^*}[x_j]\)의 최소화기는 단일 지수 모델에 따른 예상 downstream 오류도 가장 낮습니다.
\[\arg\min_{\mathbf{x}\in\mathcal{X}} \mathbb{E}_{j\sim\boldsymbol{\theta}^*}[x_j] = \arg\min_{\mathbf{x}\in\mathcal{X}} \mathbb{E}[f(\langle\boldsymbol{\theta}^*, \mathbf{x}\rangle + \epsilon)].\]이 관찰은 비음수 \(\boldsymbol{\theta}^*\)를 분포로 정규화할 수 있다는 사실에서 직접 따릅니다(정규화 상수를 \(f\)로 이동시킬 수 있음). 이를 통해 단일 지수 모델의 내적을 예상 사전 학습 손실의 단조 함수로 쓸 수 있습니다.
\[y = f(\langle\boldsymbol{\theta}^*, \mathbf{x}\rangle + \epsilon) = f(\mathbb{E}_{j\sim\boldsymbol{\theta}^*}[x_j] + \epsilon).\]명제 1은 목표 가능도에 대한 최적의 데이터 혼합물을 찾는 작업을 완전히 피할 수 있게 해줍니다. 대신, 사전 학습 손실을 예측된 downstream 오류의 단조 함수로 만드는 샘플링 분포를 선택합니다. 그 후에는 손실을 최적화하는 능력에 의존하여 downstream 성능을 최적화할 수 있습니다.
이 관점은 데이터 선택을 위한 명확한 로드맵을 제공합니다. 1) 손실과 downstream 벤치마크 성능이 높은 상관관계를 가지는 도메인 집합을 추정하고, 2) \(\boldsymbol{\theta}^*\) 추정치를 pre-training dataset 샘플링 분포로 제한합니다.
이런 접근 방식은 기존의 데이터 선택 방법들과 비교하여 다음과 같은 장점을 가집니다. 1) 새로운 LLM을 학습시킬 필요가 없어 비용 효율적이며, 2) 이미 존재하는 다양한 고성능 모델들의 정보를 활용할 수 있습니다. 3) 단일 지수 모델을 통해 수학적으로 정당화된 방법을 제공합니다.
4. 방법
4.1 알고리즘
\(\boldsymbol{\theta}^*\) 추정
\(\theta_j^*\) 파라미터는 도메인 \(j\)의 로그 가능도와 downstream 성능 간의 관계를 측정합니다. 이로 인해 \(\theta_j^*\)가 \(x\)와 \(y\) 사이의 비선형 상관 계수와 관련이 있을 것으로 자연스럽게 예상할 수 있습니다. 연구는 다음과 같은 간단한 상관 측정을 사용합니다.
\[\gamma_j = \sum_{1 \leq k, l \leq n \atop k \neq l} \text{sign}(y_k - y_l)(rank_j(x_{k,j}) - rank_j(x_{l,j}))\]상기 식에서 \(rank_j(x)\)는 \(\{x_{1,j} \ldots x_{N,j}\}\) 중 \(x\)의 순위로 이 공식은 직관적입니다. 모델 \(k\)가 모델 \(l\)보다 성능이 좋을 때, 모델 \(k\)의 로그 가능도는 모델 \(l\)의 로그 가능도에 비해 어떤 백분위에 있을까요? 이는 유일한 좋은 성능을 보이는 상관 계수는 아니지만(Appendix E 참조), 이 함수 형태는 \(\boldsymbol{\theta}^*\)의 원칙적인 추정치라는 추가적인 이점이 있습니다. 특히, 아래 섹션에서 기대값 상으로 \(\boldsymbol{\gamma}\)의 도메인 순위가 \(\boldsymbol{\theta}^*\)의 순위와 정확히 일치함을 보입니다(표준 고차원 회귀 가정 하에; 섹션 4.2에서 완전한 논의 참조).
Pre-training Dataset 선택
도메인 선택 및 비율 설정
정확한 비음수 추정치 \(\gamma_j\)가 있다고 가정할 경우, \(\gamma_j\)를 직접 데이터 선택 절차로 사용할 수 있으며, 명제 1은 모집단 사전 학습 손실을 최소화하면 downstream 오류가 최소화됨을 보장합니다. 불행히도, \(\gamma_j\)는 음수일 수 있으며 도메인당 토큰 수가 제한되어 있어 모집단 사전 학습 손실을 최소화하기 어려울 수 있습니다. 따라서 \(\gamma_j\)를 비음수이며 도메인별 토큰 수를 고려하는 합리적인 pre-training dataset 분포 집합으로 투영해야 합니다.
\(\boldsymbol{\gamma}\)를 통해 추정된 도메인 순위를 샘플링 분포로 투영하는 좋은 방법은 무엇일까요? 직관적으로, wikipedia.org가 \(\gamma_j = 0.5\)이고 arxiv.org가 \(\gamma_k = 0.9\)라면, pre-training dataset를 선택할 때 \(\boldsymbol{\gamma}\) 순서대로 토큰을 선택하여 wikipedia.org보다 arxiv.org의 토큰을 선호하는 것이 자연스러울 것입니다.
이렇게 도메인의 순서를 정한 뒤 남은 문제는 각 도메인에서 얼마나 많은 토큰을 가져올지 결정하는 것입니다. 데이터를 반복하면 성능이 저하된다는 최근의 관찰(Abbas et al., 2023)을 따라 간단한 선택 알고리즘에 도달했습니다. \(\boldsymbol{\gamma}\)가 가장 큰 것부터 가장 작은 순으로 도메인을 선택하고, 총 사전 학습 토큰 예산을 모두 사용할 때까지 각 도메인의 모든 토큰을 한 번씩 가져옵니다.
전체 알고리즘 (핵심 방법)
이런 단계들을 종합하면 간단하고 파라미터가 없는 알고리즘이 만들어집니다. 이 알고리즘은 순위 상관 계수를 계산하고 계수가 큰 순서대로 도메인을 선택합니다. 이 과정을 알고리즘 1에서 명시적으로 보여주며, 추가로 선택된 문서와 도메인을 나머지 풀과 구별하는 fastText(Joulin et al., 2016) Classfier를 훈련하는 단계를 포함합니다(Li et al. (2024)의 표준 설정과 바이그램 특성 사용). fastText Classfier를 사용하면 단일 페이지 수준에서 데이터 선택을 수행하고 더 큰 데이터셋으로 선택 과정을 확장할 수 있습니다. 또한 Classfier가 문서를 직접 선택하는 것보다 downstream 성능을 약간 향상시키는 것을 발견했습니다. 테스트한 데이터 선택 접근 방식의 세부 사항은 Appendix D에 주어져 있습니다.
(알고리즘 1) 퍼플렉시티 상관관계 기반 데이터 선택
이 알고리즘은 도메인 간의 상관관계를 계산하고, 이를 기반으로 사전 training dataset를 선택하며, 최종적으로 선택된 데이터를 분류하기 위한 fastText 분류기를 학습합니다.
| 단계 | 수정되는 변수 | 설명 |
|---|---|---|
| 2 | \(\mathbf{r}_0, \mathbf{r}_1, \ldots, \mathbf{r}_N\) | 각 도메인의 순위 계산 |
| 3 | \(\boldsymbol{\gamma}\) | 상관 계수 계산 및 업데이트 |
| 5 | \(t_i\), \(counter\) | 선택된 토큰 수 및 카운터 업데이트 |
| 6 | \(classifier\) | fastText 분류기 학습 |
4.2 이론
이제 본 논문의 접근 방식을 자세히 살펴보고 상관 계수와 투영 단계에 대한 선택이 Plan et al. (2016)의 고전적인 고차원 단일 지수 모델 Estimator의 확장임을 보입니다. 먼저 기본적인 단일 지수 모델 Estimator를 설명하고, 확장을 설명한 다음, Estimator와 결과가 이론에서 어떻게 벗어나는지에 대한 논의로 결론을 맺겠습니다.
4.2.1 단일 지수 모델의 고차원 추정
이론을 위해 Plan et al. (2016)과 Chen & Banerjee (2017)의 표준 고차원 회귀 설정을 고려합니다. 상기 식에서 목표는 단일 지수 모델 \(y_i = f(\langle \boldsymbol{\theta}^*, \mathbf{x}_i \rangle + \epsilon_i)\)에서 알려지지 않은 가중치 \(\boldsymbol{\theta}^*\)를 추정하는 것입니다. 상기 식에서 \(x_i \sim \mathcal{N}(\mathbf{0}, \mathbf{I})\)이고 \(\|\boldsymbol{\theta}^*\|_2 = 1\)입니다. (일반성을 잃지 않는다고 가정하면 \(\|\boldsymbol{\theta}^*\|_2\)는 \(f\)에 흡수될 수 있음)
이 아이디어의 시발점은 Plan et al. (2016)의 고전적인 결과입니다. 그들은 다음을 보였습니다.
\[\mathbb{E}[y_k \mathbf{x}_k] = c \boldsymbol{\theta}^*,\]상기 식에서 \(c\)는 양의 상수이고 \(1 \leq k \leq N\)입니다. 이와 밀접하게 관련된 것은 Chen & Banerjee (2017)의 결과로, 것과 유사한 강건한 Estimator를 보여주었습니다.
\[\mathbb{E}[sign(y_k - y_l)(\mathbf{x}_k - \mathbf{x}_l)] = \beta \boldsymbol{\theta}^*\]상기 식에서 \(1 \leq k,l \leq N\) (\(k \neq l\))이고 \(\beta\)는 양의 상수입니다. 이 두 결과 모두 가우시안 설정에서 고차원 단일 지수 모델의 경우, 일반화된 상관 계수가 참 회귀 계수 \(\boldsymbol{\theta}^*\)의 일관된 추정치를 제공한다는 것을 명확히 보여줍니다.
4.2.2 Estimator 도출
Plan et al.과 Chen & Banerjee는 모두 고차원, 희소 설정에서 \(\boldsymbol{\theta}^*\)를 일관되게 복구하는 모멘트 매칭 스타일의 Estimator를 제공합니다. 그러나 두 Estimator 모두 \(x\)의 값을 직접 사용하며, 이로 인해 언어 모델 로그 가능도의 이상치로 인해 불안정한 추정치가 발생한다는 것을 발견했습니다. 이상치 제거가 한 가지 가능성이지만, Chen & Banerjee (2017)의 Estimator를 \(x\)의 이상치에 대해 강건하게 만드는 더 간단한 접근 방식을 발견했습니다.
추정치 \(\boldsymbol{\gamma}\)는 다음의 쌍별 합으로 정의된 U-통계량입니다.
\[sign(y_i - y_j)(\Phi(\mathbf{x}_i) - \Phi(\mathbf{x}_j)),\]상기 식에서 \(1 \leq i,j \leq N\) (\(i \neq j\))이고 \(\Phi\)는 \(\mathbf{x}\) 값의 경험적 CDF입니다. 이 추정치는 Chen & Banerjee (2017)의 것보다 이상치에 훨씬 덜 민감합니다. 경험적 CDF가 0과 1 사이에 제한되어 있고 단일 모델이 Estimator를 퇴화시킬 수 없기 때문입니다.
이 추정치를 가우시안 설정에서 이론적으로 연구합니다. 상기 식에서 \(\Phi\)를 표준 가우시안의 CDF로 하는 점근적으로 동등한 Estimator를 고려합니다. 이 경우, 이 수정된 Estimator가 \(\boldsymbol{\theta}^*\)를 복구하는 데 일관성이 있음을 보일 수 있습니다.
Theorem 1
\(\epsilon \sim \mathcal{N}(0, \sigma^2)\)일 때, 다음이 성립합니다.
\[\mathbb{E}[sign(y_i - y_j)(\Phi(\mathbf{x}_i) - \Phi(\mathbf{x}_j))] = \frac{2}{\pi} \sin^{-1}\left(\frac{\boldsymbol{\theta}^*}{\sqrt{2(1+\sigma^2)}}\right).\]증명은 Appendix A에 제공되어 있습니다. \(\|\boldsymbol{\theta}^*\|_2 = 1\)을 가정하고 방정식 7의 기대값이 \(-1\)과 \(1\) 사이에 있어야 하므로, 항상 \(\sin^{-1}\)의 정의역 내에 있으며 이를 역변환할 수 있습니다. 역변환 후, 다음을 얻습니다.
\[\hat{\boldsymbol{\theta}} \propto \sin\left(\frac{\pi}{2}\mathbb{E}[sign(y_i - y_j)(\Phi(\mathbf{x}_i) - \Phi(\mathbf{x}_j))]\right)\]이는 \(\boldsymbol{\theta}^*\)의 추정치로, 노이즈로 인한 상수 \(\sqrt{2(1+\sigma^2)}\) 항은 제외되었습니다.
Estimator가 일관성이 있다는 것 외에도, Chen & Banerjee Estimator와의 더 긴밀한 연결을 보일 수 있습니다. 추정치가 순위 변환된 데이터에 대해 원래 Estimator를 실행할 때 일치한다는 것을 보일 수 있습니다. 더 구체적으로, 추정된 모델 순위가 \(\langle \hat{\boldsymbol{\theta}}, \mathbf{x}_i \rangle > \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_j \rangle\)인 두 모델 \(\mathbf{x}_i\)와 \(\mathbf{x}_j\)에 대해, 순위 변환 (즉, \(\Phi(\mathbf{x})\)) 하에서의 예상 순위가 이 순위와 일치합니다.
Corollary 1
\(\hat{\boldsymbol{\theta}}\)가 고정된 가중치의 벡터고, \(\mathbf{x} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})\)라고 가정하면, \(\langle \hat{\boldsymbol{\theta}}, \mathbf{x}_i \rangle < \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_j \rangle\) 사건을 조건으로 할 때, 다음이 성립한다.
\[\langle \hat{\boldsymbol{\theta}}, \mathbb{E}[\Phi(\mathbf{x}_i) | \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_i \rangle < \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_j \rangle] \rangle < \langle \hat{\boldsymbol{\theta}}, \mathbb{E}[\Phi(\mathbf{x}_j) | \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_i \rangle < \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_j \rangle] \rangle.\]이는 확률 1로 성립함을 알 수 있습니다.
이 증명은 Theorem 1과 동일한 계산에서 따르며 Appendix A에 제공되어 있습니다.
4.2.3 사전 학습을 위한 데이터 선택
(알고리즘 2) 데이터 선택
데이터 선택 알고리즘은 \(\boldsymbol{\gamma}\)를 유효한 샘플링 분포(최소한 비음수)로 제한하고 이 추정치에서 직접 샘플링하는 것임을 상기하세요. 지금은 \(\hat{\boldsymbol{\theta}}\)를 제한하는 데 집중하겠습니다. 이 섹션의 끝에서 \(\boldsymbol{\gamma}\)에 직접 같은 제약을 적용하여 동일한 결과를 얻을 수 있음을 볼 것입니다. \(\hat{\boldsymbol{\theta}}\)에 대한 제약된 추정의 이론은 간단하고 잘 이해되어 있으며, Plan et al. (2016)과 Chen & Banerjee (2017) 모두 알려진 볼록 제약 집합 \(C\) 하에서 \(\hat{\boldsymbol{\theta}}\)를 추정하는 문제를 광범위하게 연구했습니다. 특히, Plan et al. (2016)은 \(\hat{\boldsymbol{\theta}}_{proj} = \arg\min_{\boldsymbol{\theta} \in C} \|\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}\|_2\)를 통한 \(L_2\) 투영이 주변 차원이 아닌 \(C\)의 가우시안 평균 너비에 의존하는 개선된 수렴률을 제공한다는 것을 보였고, Chen & Banerjee (2017)는 선형 상관관계 \(\hat{\boldsymbol{\theta}}_{proj} = \arg\min_{\boldsymbol{\theta} \in C \subseteq B^D} -\langle \boldsymbol{\theta}, \hat{\boldsymbol{\theta}} \rangle\)를 최대화할 때 유사한 결과를 보였습니다.
상기 식에서 유사한 접근 방식을 취합니다. \(\hat{\boldsymbol{\theta}}\)를 합리적인 샘플링 분포로 강제하는 볼록 제약 집합 \(C\)를 정의하고 선형 상관관계 접근 방식을 통해 최선의 샘플링 분포를 찾습니다.
\(C\)를 두 가지 제약 조건의 조합으로 정의합니다. 첫째, 유효한 샘플링 분포를 가져야 하므로 \(\hat{\boldsymbol{\theta}}\)를 단체에 제한합니다. 위에서 언급했듯이, 데이터를 중복하면 성능이 저하된다는 것이 잘 알려져 있으므로(Abbas et al., 2023), 도메인에 대한 최대 가중치를 제한하여 데이터 중복을 피하도록 \(\hat{\boldsymbol{\theta}}\)를 제약합니다. 구체적으로, 전체적으로 \(m\) 토큰으로 사전 학습하려면 \(\theta_i^* \leq \tau_i, \forall i \in [1,D]\)를 강제합니다. 상기 식에서 \(\tau_i\)는 \(\tau_i m\)이 훈련에 접근할 수 있는 \(i\)번째 도메인의 토큰 수가 되도록 설정됩니다.
결과로 나오는 선형 프로그램은 간단한 해결책을 가지며 \(\hat{\boldsymbol{\theta}}_{proj}\)를 \(\mathbf{0}\)으로 초기화한 다음 \(\hat{\boldsymbol{\theta}}\)의 값을 가장 큰 것부터 가장 작은 것까지 반복하면서 \(\hat{\boldsymbol{\theta}}_{proj}\)의 해당 인덱스의 값을 허용 가능한 최대값으로 설정하고, \(\hat{\boldsymbol{\theta}}_{proj}\)의 합이 1이 될 때까지 진행하는 형태를 취합니다. (증명은 Appendix B 참조).
Theorem 2
다음을 해결하고자 한다고 가정합니다.
\[\hat{\boldsymbol{\theta}}_{proj} = \arg\min_{\boldsymbol{\theta} \in \mathbb{R}^D} -\langle \boldsymbol{\theta}, \hat{\boldsymbol{\theta}} \rangle,\]제약 조건
\(\sum_{i=1}^D \theta_i = 1\) \(0 \leq \theta_i \leq \tau_i, \forall i \in [1,D],\)
상기 식에서 \(\tau_i > 0\)는 고정된 값입니다. 그러면 해결책은 다음과 같습니다.
\[\hat{\theta}_k^{proj} = \begin{cases} \tau_k & \text{if } \sum_{j : r_j(\hat{\theta}_j) \geq r_k(\hat{\theta}_k)} \tau_j \leq 1 \\ 1 - \sum_{j : r_j(\hat{\theta}_j) > r_k(\hat{\theta}_k)} \tau_j & \text{if } \sum_{j : r_j(\hat{\theta}_j) \geq r_k(\hat{\theta}_k)} \tau_j \geq 1 \wedge \sum_{j : r_j(\hat{\theta}_j) > r_k(\hat{\theta}_k)} \tau_j \leq 1 \\ 0 & \text{otherwise} \end{cases},\]상기 식에서 \(r\)은 \(k \neq j\)에 대해 \(\hat{\theta}_j\)와 \(\hat{\theta}_k\) 사이의 모든 동점을 깨는 함수이며, 그 외에는 서수 관계를 그대로 유지합니다.
이 선형 프로그램의 사용이 Chen & Banerjee (2017)에서 제안된 제약된 Estimator와 일치하지만, \(L_2\) 투영이 더 자연스럽고 점근적 복구 조건을 위해 \(\|\hat{\boldsymbol{\theta}}\|_2 = 1\)을 가정할 필요가 없다는 점에 주목합니다. Appendix B에서 이 이차 경우에 대한 유사한 닫힌 형태의 표현을 유도하지만, 두 가지 별개의 이유로 이 접근 방식을 사용하지 않습니다.
첫째, \(L_2\) 투영은 \(\hat{\boldsymbol{\theta}}\)의 값의 순위에만 의존하는 선형 프로그램과 달리 \(\hat{\boldsymbol{\theta}}\)의 \(L_2\) 노름에 의존합니다. 노름을 결정하는 데 있어 과제는 방정식 7의 정확한 복구 결과가 노이즈 수준에 대한 지식을 요구하며, 삼각함수가 \(x\)의 가우시안 구조에 강하게 의존한다는 것입니다. 이로 인해 \(\hat{\boldsymbol{\theta}}\)의 노름을 정확하게 추정할 수 있을 가능성이 낮으며, 이를 피하는 유일한 방법은 노름을 하이퍼파라미터로 취급하는 것인데, 이는 불필요한 복잡성을 추가합니다. 둘째 이유는 경험적인 것입니다(첫 번째 이유의 결과일 수 있음) - 선형 투영이 광범위한 벤치마크와 조건에서 더 나은 성능을 보인다는 것을 발견했습니다(Appendix E 참조).
4.1절의 전체 알고리즘과 이론을 관련시키며 결론을 맺습니다. \(\boldsymbol{\gamma}\)에 대한 추정 단계는 방정식 8의 기대값에 대한 유한 표본, U-추정치로, 비선형 변환 \(\sin\)과 \(\pi/2\)를 제외합니다. 이 두 항은 도메인의 순위를 변경하지 않기 때문입니다. 데이터 선택 단계는 방정식 10의 투영을 직접 적용하며, 이 투영이 도메인 간의 순위에만 의존한다는 사실을 이용하여 \(\boldsymbol{\theta}^*\)에 대한 정확한 추정치 대신 \(\boldsymbol{\gamma}\)를 사용합니다.
4.3 대안적 방법(선행 연구)
본 연구에서 제안한 추정기는 고차원 단일 지수 모델에 대한 유일한 합리적 추정 방법이 아닙니다. 실험 결과로 넘어가기 전에 몇 가지 대안적 방법들과 장단점에 대해 간략히 논의하고자 합니다.
적용 가능성: $D \gg N$ 상황에서 특히 효과적입니다.
$D$는 특징의 수, $N$은 샘플의 수를 의미하며, 이 조건에서는 특징별 강건한 상관관계가 좋은 성능을 보일 가능성이 높습니다. 그러나 합리적인 모델을 얻기 위해서는 극단적인 수준의 정규화가 필요합니다.
이런 선행 대안적 방법들과의 비교를 통해, 본 연구에서 제안한 상관관계 기반 추정기의 장점을 다음과 같이 정리할 수 있습니다.
결론적으로, 본 연구에서 제안한 방법은 다양한 대안적 방법들과 비교했을 때, 단순성과 성능 면에서 우수한 균형을 보여줍니다. 특히 고차원 데이터에서의 안정성과 확장성은 실제 응용에서 큰 장점이 될 수 있습니다. 다만, 특정 문제에 따라 다른 방법이 더 적합할 수 있으므로, 문제의 특성과 데이터의 구조를 고려하여 적절한 방법을 선택하는 것이 중요합니다.
4.3 대안적 방법
5. 결과
본 연구에서는 제안된 퍼플렉시티 상관관계 기반 데이터 선택 방법의 유효성을 실험적으로 검증하였습니다. 실험은 크게 세 부분으로 구성되어 있습니다.
모든 실험에서 알고리즘 1에 기반한 단일 지수 모델을 사용하였으며, 선택된 도메인과 선택되지 않은 도메인을 구분하는 fastText Classfier를 학습하여 페이지 수준에서 사전training dataset를 필터링하였습니다.
입력 데이터 행렬 \(\mathbf{X}\) 구성
목표 벤치마크 성능 \(\mathbf{y}\) 구성
5.1 사전학습 실험
실험 설정
비교 대상 베이스 라인
결과 분석
추가 분석
5.2 성능 순위 예측
실험 방법
결과 분석
5.3 손실 행렬 \(\mathbf{X}\) 분석
분석 방법
PCA와 t-SNE 관련 내용 색인마킹
주요 발견
이런 분석 결과는 손실 행렬 \(\mathbf{X}\)가 언어 모델의 특성과 training dataset의 성질을 잘 반영하고 있음을 보여줍니다. 이는 제안된 퍼플렉시티 상관관계 기반 데이터 선택 방법의 효과성을 뒷받침하는 증거가 됩니다.
6. 사전 등록을 통한 강건성 검사
본 연구의 소규모 실험에서 제안된 접근 방식은 Li et al.의 조사에서 최고 성능을 보인 수동으로 보강된 고정 fastText 모델과 경쟁력 있는 결과를 보여주었습니다. 그러나 과거의 많은 데이터 선택 방법들이 초기에는 긍정적인 결과를 보였지만 나중에 더 큰 모델로 확장되거나 특정 실험 설정에 의존하면서 실패한 경우가 있었습니다. 이에 본 연구에서는 이런 우려를 해소하기 위해 사전 등록된 확장 실험을 설계하였습니다.
사전 등록 실험 설계
이런 사전 등록 실험은 제안된 방법의 확장성과 외적 타당성을 검증하는 데 중요한 역할을 할 것으로 예상됩니다. 특히, arXiv 프리프린트의 영구성을 활용하여 실험 결과의 신뢰성을 높이고, 부정적인 결과도 보고하겠다는 약속을 통해 연구의 객관성을 확보하고자 합니다.
7. 결론
본 연구는 고성능 데이터 선택이 반드시 정교한 수작업 휴리스틱이나 비용이 많이 드는 모델 학습을 필요로 하지 않음을 보여주었습니다. 대신, 기존의 공개 모델들을 데이터 선택을 위한 정보원으로 활용하는 대안적 접근 방식을 제시하였습니다.
주요 기여
Appendix
이 Appendix은 논문에서 제안된 추정기의 수학적 기반을 제공하는 중요한 증명들을 담고 있습니다. 세 가지 주요 Lemma(lemma)를 통해 추정기의 성질을 단계적으로 증명해 나갑니다. 각 Lemma의 목적과 증명 과정을 상세히 설명하겠습니다.
A.1 Lemma 1 (조건부 확률 분포의 특성 증명)
목적
이 Lemma의 주요 목적은 특정 조건 하에서의 확률 변수의 분포를 도출하는 것입니다. 이는 추정기의 핵심 부분인 조건부 확률 분포를 이해하는 데 필수적입니다.
기본 개념
반정규 분포 (Half-Normal Distribution) 정규 분포의 양의 부분만을 취한 분포로, 그 확률 밀도 함수(PDF)는 다음과 같습니다
\[f(x;\sigma = \frac{2}{\sigma\sqrt{\pi}}e^{-\frac{x^2}{2\sigma^2}} \text{ for } x > 0\]이 분포는 0을 중심으로 대칭인 정규 분포에서 양의 값만을 고려할 때 사용됩니다.
조건부 확률 분포 특정 조건이 주어졌을 때의 확률 변수의 분포를 나타냅니다. 이는 베이즈 정리의 기초가 되는 개념입니다.
증명 과정
Step 1: 조건부 확률의 벡터 표현
먼저, 조건부 확률을 벡터의 내적으로 표현합니다.
\[Z_{1j} | \langle \mathbf{Z}_1 - \mathbf{Z}_2, \boldsymbol{\beta} \rangle + \epsilon > 0 \stackrel{d}{=} Z_{1j} | \langle [\mathbf{Z}_1 \; \mathbf{Z}_2 \; \epsilon/\sigma], [\boldsymbol{\beta} \; -\boldsymbol{\beta} \; \sigma] \rangle > 0\]이 단계는 조건을 벡터 연산으로 변환하여 문제를 단순화합니다.
Step 2: 벡터 정규화
다음으로, 계산을 단순화하기 위해 벡터를 정규화하여 단위 벡터로 만듭니다.
\[\stackrel{d}{=} Z_{1j} | \langle [\mathbf{Z}_1 \; \mathbf{Z}_2 \; \epsilon/\sigma], [\boldsymbol{\beta} \; -\boldsymbol{\beta} \; \sigma] / \sqrt{2+\sigma^2} \rangle > 0\]Step 3: 조건부 랜덤 벡터 분해
조건부 랜덤 벡터를 조건에 의존하는 부분과 독립적인 부분으로 분해합니다.
\[\mathbf{Z}_c | \langle \mathbf{Z}_c, \boldsymbol{\beta}_c \rangle > 0 \stackrel{d}{=} (\mathbf{I} - \boldsymbol{\beta}_c\boldsymbol{\beta}_c^\top)\mathbf{Z}'' + \boldsymbol{\beta}_c Z^+\]상기 식에서 \(\mathbf{Z}'' \sim \mathcal{N}(\mathbf{0}, \mathbf{I})\)이고, \(Z^+ \sim \text{HalfNormal}(1)\)입니다.
Step 4: 개별 인덱스에 대한 조건부 분포 계산
마지막으로, 개별 인덱스 \(j\)에 대한 조건부 분포를 계산합니다.
\[Z_{1j} | \langle \mathbf{Z}_1 - \mathbf{Z}_2, \boldsymbol{\beta} \rangle + \epsilon > 0 \stackrel{d}{=} Z' \sqrt{1-\frac{\beta_j^2}{2+\sigma^2}} + \frac{\beta_j}{\sqrt{2+\sigma^2}} Z^+\]상기 식에서 \(Z' \sim \mathcal{N}(0,1)\)입니다.
이 Lemma의 결과는 추정기의 조건부 확률 분포를 이해하기 위해 사용되고, 이를 통해 특정 조건 하에서 확률 변수의 분포를 보다 더 정확히 알 수 있게 됩니다.
A.2 Lemma 2 (정규 분포의 CDF와 관련된 기댓값 계산)
목적
이 Lemma의 목적은 정규 분포의 누적 분포 함수(CDF)에 관한 기댓값을 계산하여 추정기의 성능을 평가하기 위함입니다.
기본 개념
누적 분포 함수 (CDF) 확률 변수가 특정 값 이하일 확률을 나타내는 함수로, 정규 분포의 CDF는 보통 \(\Phi(x)\)로 표기
기댓값 확률 분포의 평균을 의미하며, 연속 확률 변수의 경우 다음과 같이 정의됩니다.
\(E[X] = \int_{-\infty}^{\infty} x f(x) dx\) (\(f(x)\)는 확률 밀도 함수)
증명 과정
Step 1: 기댓값 정의 먼저, 계산하고자 하는 기댓값을 정의합니다.
\[E[\Phi(aZ+c)]\]\(\Phi\)는 표준 정규 분포의 CDF, \(a\)와 \(c\)는 상수, \(Z \sim \mathcal{N}(0,1)\)입니다.
Step 2: CDF의 정의 적용
CDF의 정의를 이용하여 기댓값을 확률로 표현합니다.
\[E[\Phi(aZ+c)] = E[P(X \leq aZ+c)]\] \[X \sim \mathcal{N}(0,1)\]Step 3: 확률 계산
확률을 계산하기 위해 다음과 같이 변형합니다.
\[= E[P(X - aZ - c \leq 0)]\]Step 4: 가우스 분포의 특성 이용
\(X - aZ - c\)는 독립적인 가우스 확률 변수들의 선형 조합이므로, 이 또한 가우스 분포를 따릅니다. 그 평균과 분산을 계산합니다.
따라서 \(X - aZ - c \sim \mathcal{N}(-c, 1+a^2)\)입니다.
Step 5: 최종 결과
이제 본 논문에서 구하고자 하는 확률은 이 가우스 분포의 CDF를 0에서 평가한 것과 같습니다.
\[E[\Phi(aZ+c)] = \Phi(\frac{c}{\sqrt{1+a^2}})\]이 Lemma의 결과는 정규 분포의 CDF와 관련된 복잡한 기댓값 계산을 단순화합니다. 이는 추정기의 성능을 분석하는 데 필수적인 도구가 됩니다.
A.3 Lemma 3 (Lemma 3, 반정규 분포와 관련된 더 복잡한 기댓값을 해결)
목적
이 Lemma의 목적은 반정규 분포와 관련된 더 복잡한 기댓값을 계산하는 것으로 추정기의 최종 형태를 도출하는 데 필요한 핵심 단계입니다.
기본 개념
오차 함수 (erf): 정규 분포와 밀접하게 관련된 특수 함수로, 다음과 같이 정의됩니다. \(\text{erf}(x) = \frac{2}{\sqrt{\pi}} \int_0^x e^{-t^2} dt\)
적분 테이블 복잡한 적분을 해결하기 위한 참조 자료로, 여러 유형의 적분에 대한 해답을 제공합니다.
증명 과정
Step 1: 기댓값 정의 계산하고자 하는 기댓값을 정의합니다.
\[E[\Phi(Z^+ \frac{b}{\sqrt{a^2+1}})]\]\(\Phi\)는 표준 정규 분포의 CDF, \(Z^+ \sim \text{HalfNormal}(1)\), \(a\)와 \(b\)는 상수입니다.
Step 2: 적분으로 표현
기댓값을 적분 형태로 표현합니다.
\[E[\Phi(Z^+ \frac{b}{\sqrt{a^2+1}})] = \int_0^\infty \Phi(z\frac{b}{\sqrt{a^2+1}}) f_{Z^+}(z) dz\]\(f_{Z^+}(z)\)는 반정규 분포의 PDF입니다.
Step 3: 적분 분해
적분을 두 부분으로 나눕니다.
\[= \frac{1}{2\pi} \left(\int_0^\infty e^{-z^2/2} dz + \int_0^\infty \text{erf}\left(z\frac{b}{\sqrt{2(a^2+1)}}\right) e^{-z^2/2} dz\right)\]Step 4: 적분 테이블 사용
복잡한 부분은 Ng & Geller (1968)의 적분 테이블을 이용하여 해결합니다.
\[\int_0^\infty \text{erf}(cx) e^{-d^2x^2} dx = \frac{\sqrt{\pi}}{2d} - \frac{1}{d\sqrt{\pi}} \tan^{-1}\left(\frac{d}{c}\right)\]Step 5: 경우 분석
세 가지 경우 (\(b>0\), \(b=0\), \(b<0\))로 나누어 각각 계산합니다.
\(b > 0\) 경우: 적분 테이블을 직접 적용
\(b = 0\) 경우: \(\text{erf}(0) = 0\)이므로 간단히 계산
\(b < 0\) 경우: \(\text{erf}\)의 odd-function의 성질을 이용하여 계산
Step 6: 최종 결과
최종적으로 모든 경우에 대해 동일한 결과를 얻습니다.
\[E[\Phi(Z^+ \frac{b}{\sqrt{a^2+1}})] = \frac{1}{2} + \frac{1}{\pi} \tan^{-1}\left(\frac{b}{\sqrt{a^2+1}}\right)\]이 Lemma의 결과는 반정규 분포와 관련된 복잡한 기댓값을 간단한 형태로 표현합니다.
A.4 전체 증명
A.1부터 A.3까지의 세 가지 Lemma를 통해, 논문에서 제안한 추정기의 수학적 기반을 단계적으로 구축했습니다. 각 Lemma는 서로 연결되어 있으며, 최종적으로 추정기의 성질을 증명하는 데 사용됩니다.
위와 같은 A.1부터 A.3까지의 정리를 통해 전체를 증명해봅시다.
\[\mathbb{E}[\text{sign}(y_1-y_2)(\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2))] = \frac{2}{\pi}\sin^{-1}\left(\frac{\boldsymbol{\theta}^*}{\sqrt{4+2\sigma_1^2+2\sigma_2^2}}\right)\]상기 식에서 \(y_1\), \(y_2\), \(\Phi(\mathbf{x}_1)\), \(\Phi(\mathbf{x}_2)\), 그리고 \(\boldsymbol{\theta}^*\)는 본문에 정의된 대로이며, \(\epsilon_1 \sim \mathcal{N}(0,\sigma_1^2)\)와 \(\epsilon_2 \sim \mathcal{N}(0,\sigma_2^2)\)입니다.
전체 증명
대칭성 이용 대칭성을 이용하여 기댓값을 두 부분으로 나눕니다.
\[\begin{aligned} &\mathbb{E}[\text{sign}(y_1-y_2)(\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2))] \\ &= \frac{1}{2}\mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2) | \text{sign}(y_1-y_2) > 0] + \frac{1}{2}\mathbb{E}[-(\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2)) | \text{sign}(y_1-y_2) < 0] \end{aligned}\]단조 증가성 이용 \(f\)의 단조 증가성을 이용하여 조건을 변환합니다.
\[= \frac{1}{2}\mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta > 0] + \frac{1}{2}\mathbb{E}[-(\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2)) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta < 0]\]상기 식에서 \(\epsilon_\Delta = \epsilon_1 - \epsilon_2 \sim \mathcal{N}(0, \sigma_1^2 + \sigma_2^2)\)입니다.
대칭성 다시 이용 \(\mathbf{x}_1 \stackrel{d}{=} \mathbf{x}_2\)와 \(\epsilon_\Delta \stackrel{d}{=} -\epsilon_\Delta\)를 이용하여 두 기댓값이 같음을 보입니다.
\[= \mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta > 0]\]기댓값의 선형성 이용 기댓값을 두 부분으로 나눕니다.
\[= \mathbb{E}[\Phi(\mathbf{x}_1) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta > 0] - \mathbb{E}[\Phi(\mathbf{x}_2) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta > 0]\]Lemma 1 적용 단일 인덱스 \(j\)에 대해 Lemma 1을 적용합니다.
\[\Phi(x_{1j}) | \langle \mathbf{x}_1-\mathbf{x}_2, \boldsymbol{\theta}^* \rangle + \epsilon_\Delta > 0 \stackrel{d}{=} \Phi(Za + Z^+b_1)\]상기 식에서 \(a = \sqrt{1-\frac{(\theta_j^*)^2}{2+\sigma_1^2+\sigma_2^2}}\)와 \(b_1 = \frac{\theta_j^*}{\sqrt{2+\sigma_1^2+\sigma_2^2}}\)입니다.
Lemma 2와 3 적용 Lemma 2와 3을 순차적으로 적용하여 기댓값을 계산합니다.
\[\begin{aligned} &= \mathbb{E}[\Phi(Za + Z^+b_1)] - \mathbb{E}[\Phi(Za + Z^+b_2)] \\ &= \mathbb{E}[\Phi(Z^+\frac{b_1}{\sqrt{a^2+1}})] - \mathbb{E}[\Phi(Z^+\frac{b_2}{\sqrt{a^2+1}})] \\ &= \frac{1}{2} + \frac{1}{\pi}\tan^{-1}(\frac{b_1}{\sqrt{a^2+1}}) - \frac{1}{2} - \frac{1}{\pi}\tan^{-1}(\frac{b_2}{\sqrt{a^2+1}}) \end{aligned}\]삼각함수 성질 이용 \(\tan^{-1}\)의 odd-function의 성질과 \(b_2 = -b_1\)을 이용합니다.
\[= \frac{2}{\pi}\tan^{-1}(\frac{b_1}{\sqrt{a^2+1}})\]최종 결과 \(a\)와 \(b_1\)을 \(\theta_j^*\)로 표현하고, \(\sin^{-1}\) 항등식을 이용하여 최종 결과를 도출합니다.
\[= \frac{2}{\pi}\sin^{-1}\left(\frac{\theta_j^*}{\sqrt{4+2\sigma_1^2+2\sigma_2^2}}\right)\]A.5 Corollary 5 (따름 정리 5)
목적
이 Corollary는 추정된 가중치 벡터 \(\hat{\boldsymbol{\theta}}\)를 사용할 때의 순위 보존 성질을 보여줍니다.
증명 과정
조건부 기댓값 계산
\[\mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2) | \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_1 \rangle + \epsilon_1 > \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_2 \rangle + \epsilon_2] = \mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2) | \langle \hat{\boldsymbol{\theta}}, \mathbf{x}_1-\mathbf{x}_2 \rangle + \epsilon_\Delta > 0]\]이전 증명 결과 적용 각 인덱스 \(j\)에 대해, 이 기댓값은 다음과 같습니다.
\[\frac{2}{\pi}\sin^{-1}\left(\frac{\hat{\theta}_j}{\sqrt{4+2\sigma_1^2+2\sigma_2^2}}\right)\]부호 분석 \(\sin^{-1}\)의 odd-function의 성질로 인해, 위 표현식은 \(\hat{\theta}_j\)와 같은 부호를 갖습니다.
결론 조건부 기댓값 \(\mathbb{E}[\Phi(\mathbf{x}_1)-\Phi(\mathbf{x}_2)]\)의 각 요소와 \(\hat{\boldsymbol{\theta}}\)의 대응하는 요소가 같은 부호를 가지므로, 다음이 성립합니다.
\[\langle \hat{\boldsymbol{\theta}}, \mathbb{E}[\Phi(\mathbf{x}_1)] \rangle > \langle \hat{\boldsymbol{\theta}}, \mathbb{E}[\Phi(\mathbf{x}_2)] \rangle\]이 증명들은 제안된 추정 방법의 수학적 기반을 제공하며 특히, 추정된 가중치 벡터를 사용할 때도 순위 보존 성질이 유지됨을 보여줌으로써, 방법의 안정성과 신뢰성을 뒷받침합니다.
Appendix B
Appendix B는 최적 투영 가중치 해법에 대한 증명을 제공합니다. (1) 선형 투영과 (2) 이차 투영으로 나뉩니다.
B.1 선형 투영
목적
이 섹션의 목적은 선형 제약 조건 하에서 최적의 투영 가중치를 찾는 문제의 해법을 증명하는 것입니다.
문제 정의
다음과 같은 최적화 문제를 고려합니다.
\[\begin{aligned} \hat{\boldsymbol{\theta}}_{proj} &= \arg\min_{\boldsymbol{\theta} \in \mathbb{R}^D} -\langle \boldsymbol{\theta}, \hat{\boldsymbol{\theta}} \rangle \\ \text{subject to: } & \sum_{i=1}^D \theta_i = 1 \\ & 0 \leq \theta_i \leq \tau_i, \forall i \in [1,D] \end{aligned}\]상기 식에서 \(\tau_i > 0\)는 고정된 값입니다.
해법
최적해는 다음과 같이 주어집니다.
\[\hat{\theta}_k^{proj} = \begin{cases} \tau_k & \text{if } \sum_{j : r_j(\hat{\theta}_j) \geq r_k(\hat{\theta}_k)} \tau_j \leq 1 \\ 1 - \sum_{j : r_j(\hat{\theta}_j) > r_k(\hat{\theta}_k)} \tau_j & \text{if } \sum_{j : r_j(\hat{\theta}_j) \geq r_k(\hat{\theta}_k)} \tau_j \geq 1 \wedge \sum_{j : r_j(\hat{\theta}_j) > r_k(\hat{\theta}_k)} \tau_j \leq 1 \\ 0 & \text{otherwise} \end{cases}\]증명
이 해법의 증명은 세 가지 경우로 나누어 진행됩니다.
1. 경우 1: \(\hat{\theta}_k^{proj} = \tau_k\)인 경우
가정: 최적해 \(\hat{\boldsymbol{\theta}}_{proj}\)에서 어떤 \(k\)에 대해 \(\hat{\theta}_k^{proj} < \tau_k\)라고 가정합니다.
접근 방법
상기 식에서 \(\Delta = \sum_{i=1}^n \delta_i > 0\)입니다.
내적 비교
\[\begin{aligned} \langle \hat{\boldsymbol{\theta}}, \hat{\boldsymbol{\theta}}_{proj} \rangle - \langle \hat{\boldsymbol{\theta}}, \boldsymbol{\theta}' \rangle &= \hat{\theta}_k \hat{\theta}_k^{proj} + \hat{\theta}_p \hat{\theta}_p^{proj} + \cdots + \hat{\theta}_q \hat{\theta}_q^{proj} \\ &\quad - (\hat{\theta}_k \hat{\theta}_k^{proj} + \hat{\theta}_k \Delta + \hat{\theta}_p \hat{\theta}_p^{proj} + \cdots + \hat{\theta}_q \hat{\theta}_q^{proj} - \hat{\theta}_p \delta_1 - \cdots - \hat{\theta}_q \delta_n) \\ &= -\hat{\theta}_k \Delta + \hat{\theta}_p \delta_1 + \cdots + \hat{\theta}_q \delta_n \\ &\leq \hat{\theta}_p (\delta_1 + \cdots + \delta_n) - \hat{\theta}_k \Delta \\ &= \hat{\theta}_p \Delta - \hat{\theta}_k \Delta \\ &\leq 0 \end{aligned}\]결론적으로
2. 경우 3: \(\hat{\theta}_k^{proj} = 0\)인 경우
이 경우는 경우 1과 유사한 방식으로 증명됩니다. 가정을 반대로 하고 비슷한 논리를 적용합니다.
3. 경우 2: \(0 < \hat{\theta}_k^{proj} < \tau_k\)인 경우
경우 1과 3이 성립함을 보였으므로, 남은 가중치는 이 조건을 만족하는 단일 값에 할당되어야 합니다.
B.2 이차 투영
이 섹션에서는 이차 제약 조건 하에서의 투영 문제를 다룹니다. 두 개의 Lemma를 통해 최적해의 성질을 밝힙니다.
B.2.1 Lemma 4
목적
이 Lemma는 최적해에서 특정 요소가 0일 때, 다른 요소들의 성질을 밝힙니다.
문제 정의
\[\begin{aligned} \hat{\boldsymbol{\theta}}_{proj} &= \arg\min_{\boldsymbol{\theta} \in \mathbb{R}^D} \|\hat{\boldsymbol{\theta}} - \boldsymbol{\theta}\|_2^2 \\ \text{subject to: } & \sum_{i=1}^D \theta_i = 1 \\ & 0 \leq \theta_i \leq \tau_i, \forall i \in [1,D] \end{aligned}\]정리
\(\hat{\theta}_s^{proj} = 0\)이면, \(\hat{\theta}_s > \hat{\theta}_j\)인 모든 \(j\)에 대해 \(\hat{\theta}_j^{proj} = 0\)입니다.
증명
1. 가정
\(\hat{\theta}_s^{proj} = 0\)이고 \(\hat{\theta}_s > \hat{\theta}_j\)이지만 \(\hat{\theta}_j^{proj} > 0\)이라고 가정합니다.
2. 새로운 벡터 \(\boldsymbol{\theta}'\) 구성
\[\begin{aligned} \theta'_s &= \hat{\theta}_s^{proj} + \Delta \\ \theta'_j &= \hat{\theta}_j^{proj} - \Delta \end{aligned}\]상기 식에서 \(0 < \Delta < \min(\hat{\theta}_j^{proj}, \tau_s - \hat{\theta}_s^{proj})\)입니다.
3. L2 노름 차이 계산
\[\begin{aligned} \|\hat{\boldsymbol{\theta}} - \hat{\boldsymbol{\theta}}_{proj}\|_2^2 - \|\hat{\boldsymbol{\theta}} - \boldsymbol{\theta}'\|_2^2 &= (\hat{\theta}_s - \hat{\theta}_s^{proj})^2 + (\hat{\theta}_j - \hat{\theta}_j^{proj})^2 \\ &\quad - (\hat{\theta}_s - (\hat{\theta}_s^{proj} + \Delta))^2 - (\hat{\theta}_j - (\hat{\theta}_j^{proj} - \Delta))^2 \\ &= 2\Delta((\hat{\theta}_s - \hat{\theta}_s^{proj}) - (\hat{\theta}_j - \hat{\theta}_j^{proj}) - \Delta) \\ &> 2\Delta((\hat{\theta}_s - \hat{\theta}_s^{proj}) - (\hat{\theta}_j - \hat{\theta}_j^{proj}) - \min(\hat{\theta}_j^{proj}, \tau_s - \hat{\theta}_s^{proj})) \\ &\geq 2\Delta((\hat{\theta}_s - \hat{\theta}_s^{proj}) - (\hat{\theta}_j - \hat{\theta}_j^{proj}) - \hat{\theta}_j^{proj}) \\ &= 2\Delta(\hat{\theta}_s - \hat{\theta}_j) \\ &> 0 \end{aligned}\]결과론적으로 \(\hat{\boldsymbol{\theta}}_{proj}\)가 최적해라는 가정에 모순이 발생합니다.
B.2.2 Lemma 5
목적
이 Lemma는 최적해에서 특정 요소가 상한값에 도달했을 때, 다른 요소들의 성질을 밝힙니다.
정리
\(\hat{\theta}_s^{proj} = \tau_s\)이면, \(\hat{\theta}_j - \tau_j > \hat{\theta}_s - \tau_s\)인 모든 \(j\)에 대해 \(\hat{\theta}_j^{proj} = \tau_j\)입니다.
증명
Lemma 4와 유사한 방식으로 진행되며, 새로운 벡터 \(\boldsymbol{\theta}'\)를 구성하여 L2 노름 차이를 계산합니다.
이런 Lemma들은 최적해의 구조를 이해하는 데 도움을 주며, 실제 최적화 알고리즘을 설계할 때 유용한 지침을 제공합니다. 예를 들어, 이 결과를 바탕으로 효율적인 투영 알고리즘을 개발할 수 있으며, 특히 고차원 문제에서 계산 복잡도를 줄이는 데 활용할 수 있습니다.
B.2.3 Full Proof
Theorem 3
B.2.1과 B.2.1을 연결해 이차 투영 문제의 최적해를 찾는 방법을 살펴보겠습니다. 이 증명의 핵심은 라그랑지 승수법을 사용하여 최적성 조건을 도출하고, Lemma 4와 5를 활용하여 경계 조건을 처리하는 것입니다. 최종적으로, \(\lambda\) 값을 조정하여 제약 조건을 만족시키는 과정을 통해 최적해를 찾습니다.
라그랑지 승수법을 통한 이차 투영 문제 해결
Theorem 3의 목적
이 정리는 제약 조건이 있는 이차 최소화 문제의 해를 명시적으로 제공합니다.
문제 정의
\[\begin{aligned} \hat{\boldsymbol{\theta}}_{proj} &= \arg\min_{\boldsymbol{\theta} \in \mathbb{R}^D} \|\hat{\boldsymbol{\theta}} - \boldsymbol{\theta}\|_2^2 \\ \text{subject to: } & \sum_{i=1}^D \theta_i = 1 \\ & 0 \leq \theta_i \leq \tau_i, \forall i \in [1,D] \end{aligned}\]해법
최적해는 다음과 같이 주어집니다.
\[\hat{\theta}_k^{proj} = \min(\max(\hat{\theta}_k - \lambda, 0), \tau_k)\]상기 식에서 \(\lambda\)는 다음 조건을 만족하도록 선택됩니다.
\[\sum_{i=1}^D \min(\max(\hat{\theta}_i - \lambda, 0), \tau_i) = 1\]증명 과정
1. 라그랑지안 설정 문제의 라그랑지안을 다음과 같이 설정합니다.
\[\mathcal{L}(\boldsymbol{\theta}, \mu, \zeta, \lambda) = \frac{1}{2}|\hat{\boldsymbol{\theta}} - \boldsymbol{\theta}|2^2 + \lambda(-1 + \sum{i=1}^N \theta_i) - \langle \mu, \boldsymbol{\theta} \rangle + \langle \zeta, \boldsymbol{\theta} - \tau \rangle\]2. 최적성 조건 \(\boldsymbol{\theta}\)의 각 요소에 대해 도함수를 0으로 설정합니다.
\[\frac{d\mathcal{L}}{d\theta_i} = \theta_i - \hat{\theta}_i + \lambda - \mu_i + \zeta_i = 0\]3. KKT 조건 적용 상보적 여유 조건(complementary slackness)에 의해, \(0 < \theta_i < \tau_i\)일 때 \(\zeta_i = \mu_i = 0\)이므로, \(\theta_i\)를 다음과 같이 정의합니다.
\[\theta_i = \hat{\theta}_i - \lambda\]4. 경계 조건 처리
5. 최종 해 도출 두 조건을 결합하여 최종 해를 얻습니다.
\[\hat{\theta}_k^{proj} = \min(\max(\hat{\theta}_k - \lambda, 0), \tau_k)\]6. \(\lambda\) 값 결정 다음 제약 조건을 만족하는 \(\lambda\)를 찾아야 합니다.
\[\sum_{i=1}^D \min(\max(\hat{\theta}_i - \lambda, 0), \tau_i) = 1\]이런 논증은 여러 논문에서 실제 응용에서 유용하게 사용되는데, 예를 들어, 머신러닝에서 특징 선택이나 희소 모델링 문제에 적용할 수 있습니다. 또한, 이 해법은 효율적인 수치 알고리즘으로 구현될 수 있어, 대규모 최적화 문제를 해결하는 데 주로 쓰입니다.
구현 참고사항
Appendix C: 손실 행렬 계산 세부사항
이 Appendix은 실험에서 사용된 손실 행렬(loss matrix)의 계산 방법을 설명합니다.
Appendix D: 사전학습 실험 추가 세부사항
이 Appendix은 언어 모델 사전학습 및 평가, 그리고 데이터 선택 방법에 대한 상세한 정보를 제공합니다.
D.1 LLM 사전학습
하이퍼파라미터 표 2에 제시된 주요 하이퍼파라미터들은 다음과 같습니다.
| 파라미터 | 값 |
|---|---|
| 디바이스당 배치 크기 | 128 |
| 학습률 | 5 × 10^(-3) |
| Warmup 비율 | 0.1 |
| Adam β1 | 0.9 |
| Adam β2 | 0.95 |
| Adam ε | 1 × 10^(-8) |
| 가중치 감소 | 0.1 |
| 학습률 스케줄러 | cosine |
| 최대 그래디언트 노름 | 1.0 |
| BF 16 | True |
| 분산 백엔드 | nccl |
| 그래디언트 누적 단계 | 1 |
D.2 LLM 평가
D.3 DSIR
DSIR(Xie et al., 2023b)은 간단하지만 일부 튜닝이 필요한 데이터 선택 방법입니다.
실제 선택된 토큰 수 표 3에 제시된 각 벤치마크별 실제 선택된 고유 토큰 수는 다음과 같습니다.
| 벤치마크 | 토큰 수 |
|---|---|
| ARC Easy | 2,905,206,499 |
| PIQA | 2,910,486,295 |
| SCIQ | 2,920,734,042 |
| LAMBADA | 3,022,219,424 |
| LAMBADA_DE | 3,210,986,137 |
| LAMBADA_ES | 3,396,528,704 |
| LAMBADA_FR | 3,413,930,081 |
| LAMBADA_IT | 3,384,854,845 |
이 방법은 n-gram 중복을 기반으로 데이터를 선택하며, 벤치마크별로 약간의 차이가 있습니다.
D.4 fastText
Li et al. (2024)의 “SOTA” fastText 모델을 사용한 데이터 필터링 방법입니다.
이 방법은 고품질 데이터를 효과적으로 선별하는 데 사용됩니다.
Appendix E, F, G는 추가적인 실험 결과와 분석을 제공합니다. 이들은 주요 방법의 견고성을 검증하고, 다양한 조건에서의 성능을 보여줍니다. 특히, Appendix E의 Figure 7은 다양한 상관관계 기반 데이터 선택 방법의 성능을 비교하며, Appendix F의 Figure 8은 더 큰 사전training dataset 풀에서의 방법 성능을 보여줍니다. Appendix G의 Figure 9는 사용된 모델들의 파라미터 수 분포를 보여주어, 제안된 방법이 다양한 규모의 모델에 적용 가능함을 시사합니다.