A scalable version of MADD for big-data classification

새로운 사람이 북적이는 방 안으로 걸어 들어올 때, 그 사람의 "가장 가까운 친구"를 찾는다고 상상해 보십시오. 컴퓨터 과학의 세계에서 이것은 **분류(classification)**라고 불립니다. 즉, 새로운 데이터 포인트가 어떤 그룹에 가장 가까운지를 보고 어느 그룹에 속하는지 알아내는 것입니다.

오랫동안 컴퓨터는 이 가까움을 측정하기 위해 **유클리드 거리(Euclidean distance)**라는 단순한 자를 사용했습니다. 하지만 여기 반전이 있습니다. 고차원의 세계(유전자 서열이나 고해 resolution 이미지처럼 수백 또는 수천 개의 특징을 가진 데이터의 세계)에서는 이 자가 제대로 작동하지 않습니다. 이는 마치 모든 사람이 너무 멀리 떨어져 있어서 모두가 똑같이 멀게 느껴지는 방에서 누가 더 가까운지 판단하려는 것과 같습니다. 컴퓨터는 혼란에 빠지고, "이웃"의 구조는 무너지며, 분류는 실패합니다.

이를 해결하기 위해 과학자들은 MADD(Mean Absolute Difference of Distances)라는 더 똑똑한 자를 발명했습니다. MADD는 단순히 A에서 B까지의 거리를 측정하는 대신, "A에서 다른 모든 사람까지의 거리가 B에서 다른 모든 사람까지의 거리와 비교했을 때 어떠한가?"라고 묻습니다. 만약 A와 B가 같은 그룹이라면 이 차이는 아주 작습니다. 만약 두 사람이 서로 다른 그룹이라면 이 차이는 매우 큽니다. 이는 고차원에서도 완벽하게 작동하는 아주 영리한 트릭입니다.

하지만 문제가 하나 있습니다.

MADD는 조금 느린 편입니다. 두 점 사이의 거리를 측정하기 위해, MADD는 방 안의 모든 다른 사람을 살펴봐야 합니다. 방이 작다면(데이터셋이 작다면) 괜찮습니다. 하지만 거대한 인파(빅 데이터)가 있다면, M당은 사람들의 모든 쌍에 대해 수학 문제를 풀어야 합니다. 논문에 따르면, 16,384개의 훈련 샘플이 있을 때 5,000명의 새로운 사람을 분류하는 데만 6.5시간 이상이 걸립니다. 이는 돋보기를 들고 모든 짚단을 하나하나 확인하며 건더기 속에서 바늘을 찾는 것과 같습니다. 작동은 하지만, 너무나 고통스러울 정도로 느립니다.

핵심 아이디어: "대표 선수단"

이 논문의 저자들은 이렇게 물었습니다. "우리가 정말로 군중 속의 모든 사람에게 물어봐야 할까요? 아니면 몇 명의 똑똑한 대표자에게만 물어보면 되지 않을까요?"

그들은 확장 가능한 버전의 MADD(MADDsc라고 불림)를 제안했습니다. 새로운 사람을 모든 16,384명과 비교하는 대신, 컴퓨터는 작지만 매우 똑똑한 "대표 선수단"을 뽑습니다. 이 선수단은 **결정론적 점 프로세스(Determinantal Point Process, DPP)**라는 정교한 수학 도구를 사용하여 선발됩니다.

DPP를 아주 까다로운 파티 플래너라고 생각해 보십시오. 만약 당신이 무작위로 사람을 골라 친구 그룹을 정하라고 한다면, 그들은 아마도 똑같은 구석에 앉아 있는 똑 닮은 사람들 다섯 명을 고를지도 모릅니다. 하지만 DPP는 다릅니다. DPP는 비슷한 사람들을 고르는 것을 적극적으로 피합니다. 이는 선수단이 방 안의 모든 사람과 대화할 필요 없이도, 다양한 구석의 사람들을 섞어 놓음으로써 군중의 전체적인 '분위기'를 포착하도록 보장합니다.

이 선수단(수천 명 대신 50명이나 100명 정도로 구성될 수 있음)을 사용함으로써, 컴퓨터는 MADD 계산을 훨씬 짧은 시간 안에 수행할 수 있습니다.

• 결과: 테스트 결과, 이 새로운 방식은 느리고 원래의 MADD만큼 거의 정확하면서도, 압도적으로 빨랐습니다. 4,096개의 샘 샘플이 있는 데이터셋에서, 새로운 방식은 약 472초가 걸린 반면, 기존 방식은 1,249초가 걸렸습니다. 이는 엄청난 속도 향상입니다!

거대 데이터셋을 위한 "초고속" 트릭

만약 군중이 너무 커서 선수단을 뽑는 것조차 시간이 너무 오래 걸린다면 어떻게 될까요? 저자들은 **무작위 푸리에 특징(Random Fourier Features, RFF)**이라는 두 번째 트릭을 추가했습니다.

당신이 거대한 도서관을 가지고 있고 유사한 책을 찾아야 한다고 상상해 보십시오. 모든 페이지를 읽는 대신, 텍스트를 간단한 코드로 변환하는 마법의 스캐너를 사용합니다. 이 코드는 주머니에 들어갈 만큼 짧지만, 여전히 책의 "본질"을 유지합니다. RFF는 선수단을 선정하는 수학적 과정에 대해 이와 같은 역할을 수행합니다.

이 방법을 25,000개의 훈련 샘플이 있는 데이터셋에 테스트했을 때:

• 원래의 MADD 방식은 메모리 부족으로 인해 중단되었습니다(데이터를 담을 공간이 없었습니다).
• 마법의 스캐너(RFF) 없이 MADDsc를 사용했을 때는 15시간 이상이 걸렸습니다.
• RFF 마법 스캐너를 사용한 MADDsc 방식은 25분 미만(구체적으로 1,468.68초) 만에 완료되었습니다.

실제로 효과가 있었을까요?

저자들은 단순히 추측한 것이 아니라, 확실히 하기 위해 각 시나리오에 대해 25번의 시뮬레이션을 실행했습니다. 그들은 다음의 데이터로 방법을 테스트했습니다:

1. 합성 데이터(Synthetic Data): 정답을 알고 있는 가공의 데이터.
2. 실제 데이터(Real Data): 심박수, 전력 사용량, 센서 판독값과 같은 실제 시계열 데이터(UCR Time Series Classification Archive 활용).

시뮬레이션에서 새로운 방식(MADDsc)은 일관되게 경쟁력이 있었으며, 특히 데이터가 까다로운 형태나 혼합 구조를 가질 때 Random Forest나 Support Vector Machine과 같은 인기 있는 방법들을 종종 능가했습니다. 실제 세계 테스트에서도 매우 좋은 성능을 보였으며, 종종 1위나 2위를 차지했습니다. 예를 들어, "Synthetic Control Chart" 데이터셋에서 MADDsc는 단 **1.29%**의 오류만을 범했는데, 이는 **9.13%**의 오류를 낸 표준 최근접 이웃(nearest-neighbor) 방식보다 뛰어난 수치입니다.

하지 않은 것 (그리고 피한 것)

이 논문이 주장하지 않은 내용을 아는 것도 중요합니다.

• 그들은 단순한 무작위 샘플링(눈을 감고 손가락으로 가리켜서 뽑는 방식)을 배제했습니다. 무작위 선택은 데이터의 중요한 구조를 놓치는 경우가 많아 성능이 떨어진다는 것을 보여주었습니다.
• 그들은 이 방법이 모든 유형의 데이터에 영원히 통용된다고 주장하지 않았습니다. 그들은 더 복잡한 버전인 gMADD의 경우, 수학적 구조가 너무 까다로워 아직 "마법의 스캐너"(RFF) 트릭을 사용할 수 없다고 언급했습니다. 이는 미래의 연구자들이 해결해야 할 과제로 남겨두었습니다.
• 그들은 이 방법이 "완벽하다"거나 "해결되었다"고 말하지 않았습니다. 그들은 자신들의 특정 시뮬레이션에서 오류율이 원래의 느린 방식과 매우 근접했다는 점(보통 1% 이내)을 보여주었으며, 진짜 주인공은 바로 '속도의 이득'임을 강조했습니다.

결론

이 논문은 여러분이 두 마리 토끼를 다 잡을 수 있다는 것을 증명합니다. 느리지만 정확한 방법과 빠르지만 부정확한 방법 사이에서 하나를 선택할 필요가 없습니다. 전체 군중에게 묻는 대신 똑똑하고 다양한 "대표 선수단"을 뽑고, 가장 큰 데이터셋을 위해 영리한 수학적 지름길을 사용함으로써, 정확도를 잃지 않으면서도 방대한 양의 데이터를 빠르게 분류할 수 있습니다.

저자들이 테스트를 통해 보여주었듯이, 이 접근 방식은 우리가 이전에는 너무 느리거나 메모리 용량 문제로 다루기 힘들었던 "빅 데이터" 문제에 강력한 도구인 MADD를 사용할 수 있게 해줍니다. 이는 속도의 승리이자 정확성의 승리이며, 동시에 수학적 정직함을 유지하는 방법입니다.