새 알고리즘, 계산 시간을 주문 단위로 단축

새로운 알고리즘이 문제 해결에 필요한 반복 횟수를 획기적으로 줄여 계산을 기하급수적으로 가속화합니다. 소셜 미디어 분석, 유전자 데이터 클러스터링 등 대규모 데이터셋에서 기존 순차 알고리즘보다 훨씬 뛰어난 성능을 보입니다.

최적화 문제와 순차 알고리즘의 한계

수천 가지 최적화 문제(모든 실행 가능한 해 중 최적해를 찾는 문제) — 수익률 위험을 최소화하기 위해 주식에 자금을 배분하거나, 직원 가용 사무실에 배치해 업무 흐름과 직원 통계를 최대화하는 문제 등 — 은 순차 알고리즘에 크게 의존합니다.

이 알고리즘들의 기본 작동 패턴은 1970년대 초 처음 정립된 이후 개선(향상)되지 않았습니다. 이들은 특정 문제를 'n' 단계로 순차적으로 해결합니다.

단계 수는 문제의 크기(알고리즘에 특정 값을 입력으로 제공)에 따라 달라집니다. 이런 방식은 보통 계산 병목 현상을 초래합니다. 알고리즘이 진행될수록 각 반복에서 얻는 상대적 이득은 점점 작아집니다.

알고리즘이 수천 개의 작은 단계 대신 몇 번의 도약으로 문제를 해결할 수 있다면? 오늘날 널리 쓰이는 알고리즘들을 기하급수적으로 더 빠르게 만들 수 있다면? 신약 개발과 교통 체증 회피를 돕는 알고리즘들을 말하는 것입니다.

이를 가능하게 하기 위해 하버드 대학교 연구진이 '돌파구(Breakthrough)'라 부르는 새로운 유형의 알고리즘을 개발했습니다. 문제 해결에 필요한 반복 횟수를 획기적으로 줄여 계산을 기하급수적으로 가속화합니다.

이 알고리즘은 정보 추출, 경매 설계, 머신 비전, 계산 생물학, 네트워크 분석 등 여러 분야의 광범위한 문제에 대한 계산을 가속화합니다.

개발자들에 따르면, 이전에는 며칠 또는 몇 주 걸리던 대규모 계산을 단 몇 초 만에 수행할 수 있습니다. 이는 새로운 대규모 병렬화 접근법의 문을 열어, 예외적 규모의 실용적 요약 프로세스 구축을 가능하게 할 것입니다.

작동 원리

순차 알고리즘은 실행 가능한 해의 수를 한 단계씩 좁혀나갑니다. 반면 새 알고리즘은 서로 다른 방향들을 병렬로 샘플링한 뒤, 덜 관련 있는 방향들을 제거하고 가장 유리한(고가치) 방향들을 선택해 해에 도달합니다. 향후 반복에서 무시될 값들을 선택적으로 버립니다.

이미지 출처: 연구진 제공

구체적으로, 이 알고리즘은 O(log n) 순차 단계를 요구하며 1/3에 임의로 가까운 근사치에 도달합니다. 병렬화를 활성화하면, 알고리즘은 서브모듈러 최대화(sub-modular maximization) 문제에 대해 기존 어떤 방법보다 기하급수적으로 빠르게 상수 인자 근사치에 도달합니다.

참조: Harvard SEAS | Harvard Publications

예를 들어, <스타워즈>와 비슷한 영화를 추천하는 작업이라면, 기존 알고리즘은 각 단계마다 <스타워즈>와 속성(액션, 어드벤처, 판타지)이 비슷한 영화를 하나씩 추가합니다.

새로 개발된 알고리즘은 반면 영화 세트를 무작위로 샘플링한 뒤, <스타워즈>와 전혀 맞지 않는 것들을 가지치기합니다. 이는 <스타워즈>와 비슷한 다양한 영화 컬렉션을 제공합니다(당연히 슈퍼맨 영화 10편을 추천받고 싶진 않을 테니까요).

알고리즘은 추천할 충분한 항목이 모일 때까지 각 단계마다 다양한 영화를 추가합니다. 매 단계에서 가치 있는 결정을 내리는 열쇠는 적응적 샘플링 과정에 있습니다.

순차(검정) 알고리즘과 돌파구(빨강) 알고리즘이 문제를 해결하는 데 걸린 단계 수

테스트 및 응용

연구진은 6,000명의 사용자가 4,000편의 영화에 매긴 100만 개의 평점 데이터셋으로 적응적 샘플링 알고리즘을 테스트했습니다. 한 사람에게 맞춤형이고 다양한 영화를 기존 알고리즘보다 20배 빠르게 추천하는 데 성공했습니다.

택시 배차 문제에도 적용했습니다 — 제한된 택시로 최대 고객을 서비스할 최적 위치 선정. 200만 건의 택시 운행 데이터에서 최첨단 알고리즘보다 6배 빠르게 작동했습니다.

소셜 미디어 분석이나 유전자 데이터 클러스터링 같은 대규모 데이터셋에서 훨씬 더 나은 결과를 낼 수 있습니다. 그 외에도 다중 질병 임상 시험 개발, 의료 영상용 센서 어레이, 약물 상호작용 탐지 등에 적용 가능합니다.

관련 기사: 새 자율주행차 알고리즘, 공격적 차선 변경 가능

요즘 수백만 장의 이미지/비디오에서 딥러닝 네트워크 훈련용 효과적 데이터 부분집합을 찾는 것이 어려운 과제가 되었습니다. 이 연구는 가치 있는 부분집합을 신속히 추출하는 데 도움을 주며, 대규모 데이터 요약 문제에 상당한 영향을 미칠 것입니다.