GIST 알고리즘 소개: 스마트 샘플링의 다음 단계

머신러닝에서 “데이터를 더 모으면 성능이 오른다”는 말은 여전히 유효하지만, 요즘은 그 다음 문장이 꼭 붙습니다. “그런데 비용과 시간이 감당이 안 된다.” 그래서 등장한 게 데이터 하위 집합 선택(data subset selection), 즉 똑똑하게 일부만 뽑아 학습 효율을 끌어올리는 방법입니다.

이번 글의 주인공은 GIST(Greedy Independent Set Thresholding) 입니다. GIST는 한마디로 “서로 너무 비슷한 데이터는 줄이고(다양성), 모델에 도움 되는 데이터는 챙기는(유용성)” 샘플링을 빠르게 해내는 알고리즘입니다. 무엇보다 두 목표를 동시에 만족시키면서도 해의 품질에 대한 수학적 보장까지 노리는 ‘다음 단계’ 접근으로 소개됩니다.

왜 지금 ‘스마트 샘플링’이 절실해졌을까: 데이터는 커지고, 중복도 커진다

대규모 데이터셋은 풍부해 보이지만, 막상 들여다보면 “새 정보”보다 “비슷한 장면의 반복”이 훨씬 많습니다. 예를 들어 이미지 분류에서 고양이 사진이 100만 장이라도, 비슷한 각도·비슷한 배경·비슷한 품종이 쌓이면 학습 관점에선 중복 비용이 커집니다.

이 문제는 피처 선택(feature selection)에서 오래전부터 보던 고민과 닮아 있습니다. 피처 선택도 결국 “중복되거나 도움이 덜 되는 요소를 덜어내서 학습을 빠르고 견고하게” 만들려는 목적이니까요. 실제로 피처 선택은 학습 시간 단축, 차원의 저주 완화, 모델 단순화 같은 실용적 이유로 널리 쓰입니다¹. 데이터 샘플링은 그 철학을 “행(row)” 단위로 확장한 셈이고, GIST는 그 확장을 꽤 공격적으로 잘 해냅니다.

GIST 핵심 아이디어 1: ‘다양성’은 거리 임계값으로 간단하게 강제한다

GIST의 첫 번째 엔진은 거리 기반 규칙입니다. 어렵게 들리지만 감각은 단순합니다.

“너랑 너, 너무 비슷하면 둘 다 데려가지 말자.”

이를 위해 GIST는 데이터 포인트들 사이 거리를 보고, 서로 일정 임계값(threshold)보다 가까우면 중복으로 판단합니다. 이 한 줄 규칙이 좋은 이유는 명확합니다. 다양성을 “점수”로 뭉뚱그려 최적화하면 계산이 비싸지는데, GIST는 “가까우면 탈락” 같은 룰로 다양성을 빠르게 확보합니다.

여기서 포인트는, 다양성이 단순히 ‘골고루’가 아니라 학습 데이터의 커버리지(coverage)와 연결된다는 겁니다. 비슷한 것만 잔뜩 뽑으면 모델이 보는 세상이 좁아지고, 예상 밖 데이터에서 성능이 흔들리기 쉬워집니다.

GIST 핵심 아이디어 2: ‘유용성’은 겹치지 않는 집합에서 greedy로 최대화한다

다양성만 챙기면 어떻게 될까요? 극단적으로는 “희귀하지만 별 도움 안 되는 샘플”만 남을 수도 있습니다. 그래서 GIST는 두 번째 엔진으로 유용성(utility) 을 최대화합니다.

이때 중요한 제약이 하나 붙습니다. 아까 거리 임계값으로 걸러낸 규칙 때문에, 동시에 선택될 수 있는 데이터들이 정해집니다. 즉 “서로 너무 비슷한 애들은 함께 못 뽑는다”는 조건 아래에서, 유용성 점수가 큰 애들을 최대한 많이 담는 문제가 됩니다.

이 구조는 그래프 관점으로 보면 “서로 충돌하는 데이터끼리 간선이 있는 그래프에서, 충돌 없는(독립) 노드 집합을 뽑되 점수 합이 크도록”과 비슷한 형태가 됩니다. 이런 문제는 대개 정확한 최적해가 어렵기 때문에, GIST는 이름 그대로 greedy(탐욕적) 방식으로 빠르고 괜찮은 해를 찾습니다. 탐욕 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방식으로, 실무에선 “속도가 무기”인 경우가 많아 자주 채택됩니다.

‘다양성 vs 유용성’ 싸움을 끝내는 방식: 둘 중 하나가 아니라, 둘 다의 규칙을 만든다

샘플링 기법들이 흔히 겪는 비극은 이것입니다.

유용성 위주로 뽑으면 데이터가 한쪽으로 쏠리고, 다양성 위주로 뽑으면 모델 성능이 덜 오른다.

GIST는 이 싸움을 “가중치 튜닝”으로 풀기보다, 아예 역할을 나눕니다. 다양성은 거리 임계값으로 강제하고, 유용성은 그 안에서 최대화합니다. 그래서 실무자가 “다양성 가중치 λ를 0.3으로 할까 0.7로 할까” 같은 끝없는 튜닝 지옥에서 한 발 벗어날 여지가 생깁니다.

게다가 GIST는 이미지 분류 같은 작업에서 기존 벤치마크를 뛰어넘는 성능을 보였고, 선택된 해의 품질에 대한 수학적 보장을 제공하는 방향으로 소개됩니다. 이런 보장은 특히 “왜 이 샘플링을 믿어도 되지?”라는 질문에 답을 주는 안전장치가 됩니다.

GIST는 ‘단독 스킬’이 아니라 ‘합체 파츠’다: GIST-margin, GIST-submod 같은 결합 전략

현장에서 진짜 환영받는 알고리즘은, 혼자 잘하는 알고리즘이 아니라 기존 파이프라인에 잘 붙는 알고리즘입니다. GIST가 흥미로운 이유가 여기 있습니다.

GIST는 다양한 하위 집합 선택 전략과 결합해 성능을 올리는 형태로도 확장됩니다. 예를 들어 특정 샘플 선택 기준(마진 기반, 서브모듈러 기반 등)에 GIST의 “다양성 룰”을 결합한 변형들이 소개되는데, 이런 조합은 한마디로 “원래 잘하던 유용성 전략에, 중복 방지 안전벨트를 채워준다”에 가깝습니다.

또 대규모 데이터셋(예: ImageNet)처럼 규모가 큰 환경에서도 GIST는 빠르게 동작해 실제 트레이닝 파이프라인에 통합하기 좋고, 실제 사례로는 YouTube 비디오 추천 시스템 개선에 기여한 것으로도 언급됩니다. “논문 속에서만 빠른 척하는” 게 아니라, 제품 환경을 의식한 설계라는 신호로 읽힙니다.

시사점: GIST를 도입할 팀이 얻는 실용적 이득 3가지

첫째, 학습 시간을 줄이면서도 성능을 지킬(혹은 올릴) 가능성이 큽니다. 단순히 데이터를 덜 쓰는 게 아니라, “중복을 덜 쓰는 것”이기 때문입니다.

둘째, 데이터 품질 논쟁을 “룰 기반”으로 정리할 수 있습니다. 다양성을 점수로 설계하면 합의가 어렵지만, 거리 임계값은 상대적으로 설명과 운영이 쉽습니다.

셋째, 기존 샘플링/액티브러닝/서브모듈러 최적화 등과 결합해 점진적으로 개선하기 좋습니다. 처음부터 파이프라인을 갈아엎지 않고도 “중복 제거 레이어”를 얹는 방식으로 접근할 수 있죠.

개인적으로는, 앞으로의 확장 가능한 AI 시스템에서 경쟁력이 “더 큰 모델”만이 아니라 “더 똑똑한 데이터 선택”으로도 갈릴 거라고 봅니다. GIST는 그 흐름에서 꽤 실무 친화적인 답안지에 가깝습니다. 데이터가 커질수록, 결국 우리는 같은 질문으로 돌아오니까요. “이 중에서, 진짜 학습에 도움이 되는 건 뭐지?”

참고

¹Feature selection - Wikipedia