🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

이 논문은 전역적 대수 구조를 가진 데이터셋에 대해 이론적 보장과 기존 클러스터링 기반 방식 대비 실증적 개선을 제공하며, 저계수 근사와 잔차 기반 샘플링을 활용하여 가중치가 부여된 데이터 포인트의 부분 집합을 효율적으로 선택하는 새로운 데이터 선택 프레임워크를 소개한다.

원저자: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

게시일 2026-06-16

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 세계 최고의 수프를 만들기 위해 노력하는 셰프라고 상상해 보세요. 당신에게는 수천 가지의 서로 다른 채소, 향신료, 육수가 가득 찬 거대한 창고(데이터셋)가 있습니다. 완벽한 수프를 만들기 위해서는 이 모든 재료를 맛보고 섞어야 합니다. 하지만 문제는 당신의 주방은 아주 작고, 화력은 약하며, 주어진 시간도 몇 시간뿐이라는 것입니다. 창고에 있는 모든 재료로 요리를 하는 것은 불가능합니다.

당신은 전체 창고의 맛과 정확히 일치하는 맛을 낼 수 있는, 완벽하고 작은 한 줌의 재료를 골라내야 합니다. 이것이 바로 데이터 선택(Data Selection) 문제입니다.

옛날 방식: "거리"에 의한 선택

한동안 최고의 셰프들은 **클러스터링(Clustering, 군집화)**이라는 방법을 사용했습니다. 창고에 들어가서 각기 다른 구석에 있는 채소를 하나씩 고른다고 상상해 보세요. 북쪽에서 당근을, 남쪽에서 감자를, 동쪽에서 피망을, 서쪽에서 토마토를 집어 드는 식입니다.

그 논리는 이랬습니다: "아이템들이 서로 멀리 떨어져 있다면, 모든 경우의 수를 다 커버할 수 있을 거야." 단순한 레시피에서는 이 방법이 잘 작동했습니다. 하지만 데이터가 거대하고 복잡한 현대의 세상(수백만 개의 아이템이 있는 창고와 같은 상황)에서 이 방법에는 결함이 있습니다. 이 방식은 아이템이 '어디에' 있는지에 집중할 뿐, 그 아이템이 실제로 '무엇을 하는지'에는 집중하지 않습니다. 결과적으로 당신은 겉모습은 다양하지만 맛은 모두 똑같은 채소 꾸러미를 갖게 될 수도 있으며, 정작 수프의 맛을 결정짓는 단 하나의 비밀 향신료는 놓칠 수도 있습니다.

새로운 방식: "구조"에 의한 선택

이 논문의 저자들은 이렇게 말합니다: "채소가 어디에 서 있는지 보지 마세요. 맛의 **형태(Shape)**를 보세요."

그들은 **저계수 구조(Low-Rank Structure)**에 기반한 새로운 방법을 제안합니다.
당신의 수프 재료를 개별 아이템이 아니라, 복잡한 3D 조각품이라고 생각해 보세요. 비록 조각품이 복잡해 보일지라도, 실제로는 단 몇 개의 주요 들보(beam)와 지지대로 만들어졌을 수 있습니다. 나머지는 그저 장식일 뿐입니다.

주요 들보 (Low-Rank): 이것들은 맛의 가장 중요한 방향입니다. 이것들만 제대로 잡으면 수프의 맛을 제대로 낼 수 있습니다.
장식 (Residuals): 이것들은 맛을 크게 변화시키지 않는 아주 작고 중요하지 않은 세부 사항들입니다.

저자들의 방법은 수학적인 "X-레이"(**저계수 근사(Low-Rank Approximation)**라고 불림)를 사용하여 그 주요 들보들을 찾아냅니다. 아이템들을 서로 멀리 떨어뜨려 놓는 대신, 그들은 맛의 구조를 지탱하는 핵심적인 들보 역할을 하는 특정 재료들을 골라냅니다.

방법론: "민감도" 척도

어떤 재료가 "주요 들보"인지 알아내기 위해, 그들은 **민감도 샘플링(Sensitivity Sampling)**이라는 기술을 사용합니다.

거대한 저울이 있다고 상상해 보세요. 채소를 저울 위에 올려놓으면, 저울은 이렇게 알려줍니다: "만약 이 채소를 빼놓는다면, 수프의 맛이 얼마나 변할까요?"

만약 맛이 크게 변한다면, 저울의 수치는 치솟습니다. 이 채소는 민감도가 매우 높습니다 (매우 중요함).
만약 맛이 거의 변하지 않는다면, 저울의 수치는 낮게 유지됩니다. 이 채소는 민감도가 낮습니다 (중복됨).

그들의 알고리즘은 창고의 모든 아이템에 대해 이 점수를 계산한 다음, 중요도에 따라 가중치를 두어 작은 그룹을 무작위로 선택합니다. 즉, "고민감도" 아이템을 선택할 확률이 훨씬 높아지는 것입니다.

결과: 이것이 왜 중요한가

이 논문은 두 가지 방식으로 이 아이디어를 테스트했습니다.

신용카드 테스트: 그들은 표준 금융 데이터셋을 사용하여 누가 신용카드 대금을 미납할지 예측하려고 했습니다. 그들의 "저계수(Low-Rank)" 방식은 기존의 "클러스터링" 방식이나 단순히 무작위로 선택하는 것보다 훨씬 더 잘 예측하는 소수의 고객 그룹을 찾아냈습니다.
거대 뇌 테스트 (LLM): 그들은 거대한 AI(Llama3-8B)에게 수학과 질문 답변을 가르치려 했습니다. 전체 데이터셋으로 AI를 학습시키는 것은 시간이 엄청나게 오래 걸리고 비용도 막대하게 듭니다. 그들은 이 방법을 사용하여 단 6%에서 25%의 데이터만으로도, 무작위 데이터나 기존의 클러스터링 방식을 사용했을 때보다 더 똑똑한 AI를 학습시켰습니다.

핵심 요약

이 논문은 현대의 거대한 데이터셋에 있어서는 데이터 포인트 사이의 "거리"보다 데이터의 "형태"(대수적 구조)가 더 중요하다고 주장합니다.

단순히 모든 구석을 다 채우려고 노력하는 대신, 데이터의 주요 구조적 들보에 집중함으로써, 당신은 데이터의 90%를 버리고도 모든 데이터를 사용했을 때와 같거나 심지어 더 나은 성능을 내는 머신러닝 모델을 학습시킬 수 있습니다. 이는 마치 바다의 짠맛을 알기 위해 바닷물 속의 모든 소금 알갱이를 맛볼 필요는 없으며, 단지 바다의 진정한 특성을 대표하는 한 숟가락의 물만 맛보면 된다는 사실을 깨닫는 것과 같습니다.

기술 요약: 저차원 구조를 활용한 데이터 선택에서의 능동 학습 (Active Learning with Low-Rank Structure for Data Selection)

문제 정의

본 논문은 머신러닝의 데이터 선택 문제, 특히 모델 성능을 크게 저하시키지 않으면서 효율적인 모델 학습을 가능하게 하는 작고 대표성 있는 데이터 부분 집합(코어셋, coreset)을 식별하는 과제를 다룹니다. 현대적인 데이터셋과 파운데이션 모델은 성공을 견인해 왔으나, 학습 및 미세 조정(fine-tuning)에 막대한 계산 비용을 발생시킵니다.

Sener와 Savarese [SS18], 그리고 Axiotis 등 [ACH+24]의 연구와 같은 기존 방식들은 데이터 임베딩에 적용된 클러스터링 기반 휴리스틱(예: $k$ -center 또는 $k$ -means)에 의존합니다. 이러한 방법들은 데이터가 다양성과 점 사이의 거리가 정보성을 결정하는 내재적 기하학적 구조를 가지고 있다고 가정합니다. 그러나 저자들은 많은 현대적 데이터셋, 특히 고차원 공간에서의 데이터셋은 지역적 기하학적 클러스터링보다는 저차원 근사(예: 주성분 분석, PCA)에 의해 더 잘 포착되는 **전역적 대수 구조(global algebraic structure)**를 보인다고 주장합니다. 클러스터링 방식은 지배적인 분산 방향을 포착하지 못하여 모델 학습에 필수적인 구성 요소를 놓칠 가능성이 있습니다.

방법론

본 논문은 **저차원 근사(low-rank approximation)**와 **잔차 기반 민감도 샘플링(residual-based sensitivity sampling)**에 기반한 새로운 데이터 선택 프레임워크를 제안합니다. 핵심 아이디어는 단순히 기하학적 다양성을 극대화하는 것이 아니라, 데이터의 지배적인 스펙트럼 방향(spectral directions)을 보존하는 것을 우선시하는 것입니다.

이론적 프레임워크

이 접근 방식은 행 부분 집합 선택(Row Subset Selection) 문제와 **손실 보존 코어셋 구축(loss-preserving coreset construction)**에 근거합니다. 저자들은 임베딩 행렬을 가진 데이터셋 $D$ 에 대해, 손실 함수 $\ell$ 이 $k$ 차원 부분 공간 $V$ (상위 특이 벡터 또는 주성분에 의해 생성됨)에 대해 다음과 같이 분해될 수 있다는 **가정 2.1(Assumption 2.1)**을 도입합니다:

직교 페널티(Orthogonal Penalty): 부분 공간 $V$ 외부에 있는 점 $y$ 에 대한 손실 편차는 $V$ 에 직교하는 잔차 성분 $r(y)$ 의 노름(norm)에 의해 $\lambda$ 라는 상수로 스케일링되어 이차적으로 제한됩니다.
부분 공간 근사(Subspace Approximation): 부분 공간 $V$ 내부에서 손실은 기저 방향들을 따른 손실의 가중 합으로 잘 근사되며, 이는 상수 $\gamma$ 에 의해 스케일링됩니다.

이 가정은 $V$ 라는 지배적인 저차원 부분 공간에 직교하는 방향들이 손실에 적게 기여하거나 정보성이 낮다는 직관을 공식화하며, 이는 PCA, 행렬 완성(matrix completion), 저차원 적응(LoRA)과 같은 작업에서 관찰되는 특성입니다.

알고리즘: 민감도 샘플링 (Sensitivity Sampling)

제안된 알고리в즘(알고리즘 2)은 다음 단계들을 통해 가중 코어셋 $S$ 를 구축합니다:

저차원 스케치(Low-Rank Sketch): 데이터셋의 rank- $k$ 근사치를 계산하여(예: SVD를 통해) 부분 공간 $V$ 와 그 기저 $\{v_1, \dots, v_k\}$ 를 정의합니다.
분해(Decomposition): 각 데이터 포인트 $x$ 에 대해, 이를 $V$ 로의 투영 $v(x)$ 와 $V$ 에 직교하는 잔차 $r(x)$ 로 분해합니다.
민감도 점수 계산: 다음을 결합하여 각 점에 대한 민감도 점수 $\sigma(x)$ $σ (x)$ 를 계산합니다:
- 기저 방향을 따른 가중 손실: $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ .
- 잔차에 대한 페널티: $\lambda \|r(x)\|_2^2$ .
- 기저 내 최대 손실과 관련된 상수 항.
샘플링: 정규화된 민감도 점수 $p(x) = \sigma(x) / \sum \sigma(y)$ 에 비례하여 복원 추출 방식으로 데이터셋에서 점을 샘플링합니다.
가중치 부여: 추정기가 편향되지 않도록 샘플링된 점들에 $w(x) = 1/(s \cdot p(x))$ 의 가중치를 할당합니다.

주요 기여

이론적 보장 (Theorem 2.2 & 2.3): 본 논문은 최적의 rank- $k$ 근사 비용 $\Phi_k(D)$ 에 비례하는 가산 항(additive term)을 제외하고, $\tilde{O}(k + 1/\varepsilon^2)$ 크기의 가중 부분 집합이 전체 데이터셋의 평균 손실을 $(1 \pm \varepsilon)$ 상대 오차 내에서 근사할 수 있음을 증명합니다.
- Theorem 2.2는 일반적인 가중 부분 집합에 대해 이를 보장합니다.
- Theorem 2.3은 이를 **행 부분 집합 선택(Row Subset Selection)**으로 확장하여, 선택된 부분 집합이 입력 데이터셋의 실제 데이터 포인트들로 구성됨을 보장합니다.
- 오차 경계는 $\Phi_k(D)$ 에 명시적으로 의존하며, 이는 강한 저차원 구조를 가진 데이터셋일수록 더 타이트한 경계와 더 정확한 코어셋을 생성함을 나타냅니다.
알고리즘적 혁신: 저자들은 저차원 구조를 활용하여 중요도 점수를 계산하는 민감도 샘플링 알고리즘을 도입하였으며, 이는 클러스터링 기반 방식에서 사용하는 기하학적 거리 측정법과는 차별화됩니다.
실증적 검증: 제안된 프레임워크는 정형 데이터(Credit Card Default 데이터셋)와 대규모 언어 모델 미세 조정(GSM8k, ViGGO, SQL 태스크에 대한 Llama3-8B 및 Qwen2.5-3B) 모두에서 검증되었습니다.

실험 결과

본 논문은 제안된 **저차원 민감도 샘플링(Low-rank SS)**을 Uniform Sampling, $k$ -Center, Clustering-based Sensitivity Sampling, Graph Cut 등의 여러 베이스라인과 비교 평가했습니다.

정형 데이터 (Credit Card 데이터셋):
- Low-rank SS는 제곱합(sum-of-squares) 측면에서 가장 낮은 근사 오차를 달축하였으며, 작은 샘플 크기( $s=1000$ )에서 무작위 샘플링보다 10배, 클러스터링보다 약 50% 낮은 오차를 기록했습니다.
- 다운스트림 로지스틱 회귀에서 Low-rank SS는 $s=5000$ 일 때 최대 74%의 테스트 정확도를 달성하여, 클러스터링(70%)과 무작위 샘플링(67%)을 능가했습니다.
LLM 미세 조정 (Llama3-8B & Qwen2.5-3B):
- GSM8k, ViGGO, SQL 태스크에서 Low-rank SS는 Uniform Sampling 및 클러스터링 기반 방식보다 일관되게 우수한 성능을 보였습니다.
- 예를 들어, Llama3-8B를 사용한 ViGGO 태스크에서 25% 데이터 압축 시, Low-rank SS는 **77.6%**의 정확도를 기록하여 클러스터링 기반 SS의 **74.9%**를 앞질렀습니다.
- 전이 가능성(Transferability): 더 큰 모델(Llama3-8B)을 사용하여 선택된 부분 집합이 더 작은 모델(Qwen2.5-3B)로 성공적으로 전이되었으며, 심지어 타겟 모델에 의해 직접 선택된 부분 집합보다 높은 성능을 보였습니다. 이는 저차원 기준이 데이터의 내재적 특성을 포착함을 시사합니다.
- 절제 실험(Ablation): 이 방법은 기저 선택(basis selection)의 선택에 견고함을 입증했습니다. Leverage score sampling이 가장 좋은 성능을 보였으나, Uniform basis selection조차 경쟁력 있는 결과를 보여주었습니다.
구조 분석: GSM8k에 대한 실험은 해당 데이터셋이 클러스터링에 비해 저차원 가정 하에서 더 낮은 근사 오차를 보임을 입증하였으며, 이는 가정 2.1의 적용 가능성을 검증합니다.

의의 및 주장

본 논문은 단순한 무작위 서브샘플링이나 클러스터링 기반 데이터 선택에 대한 강력하고 효율적인 대안을 제공한다고 주장하며, 특히 고차원 및 대규모 설정에서 유용합니다.

이론적 기여: 저차원 손실 가정 하에서의 데이터 선택에 대한 엄격한 보장을 확립하였으며, 코어셋의 품질을 데이터셋의 저차원 구조( $\Phi_k(D)$ )와 직접 연결하였습니다.
실질적 영향: 사전 학습된 모델(예: BERT)의 단순한 임베딩만으로도 훨씬 더 큰 타겟 모델(LLM)을 위한 정보성 있는 포인트를 선택하는 데 필요한 저차원 구조를 근사하기에 충분하다는 것을 보여주었습니다.
효율성: 이 접근 방식은 전체 데이터셋에 대해 불확실성 점수(uncertainty scores)를 계산해야 하는 계산적 제약(일반적인 능동 학습의 문제)이나, 클러스터링 기반 배치 선택의 중복 문제를 피합니다.
겸허함: 저자들은 클러스터링이 일부 사례에서 여전히 가치가 있음을 인정하지만, 지배적인 스펙트럼 방향이 중요한 대규모 모델 환경에서는 저차원 접근 방식이 더 신뢰할 수 있는 토대를 제공한다고 밝힙니다. 이들은 보편적 최적성을 주장하는 것이 아니라, 데이터가 전역적 대수 구조를 보이는 설정에서 상당한 개선을 이루었음을 강조합니다.