새로운 알고리즘으로 계산 시간을 수십 배 단축

• 새로운 알고리즘은 문제를 해결하는 데 필요한 반복 횟수를 대폭 줄여 계산 속도를 기하급수적으로 높입니다.
• 소셜 미디어 분석 및 유전자 데이터 클러스터링과 같은 대규모 데이터 세트에서 기존(순차) 알고리즘보다 훨씬 더 나은 성능을 발휘합니다. 

수익에 대한 위험을 최소화하기 위해 주식에 자금을 할당하거나 작업 흐름 및 직원 통계를 최대화하기 위해 직원을 사용 가능한 사무실에 할당하는 것과 같은 수천 가지 최적화 문제(가능한 모든 솔루션에서 최상의 솔루션을 찾는 문제)는 순차 알고리즘에 크게 의존합니다.

이러한 알고리즘의 기본 작동 패턴은 1970년대 초에 처음 확립된 이후 변경(향상)되지 않았습니다. 특정 문제는 "n" 단계를 거쳐 순차적으로 해결됩니다.

단계 수는 문제의 크기(알고리즘에 특정 값을 입력으로 제공)에 따라 달라집니다. 이러한 종류의 방법은 일반적으로 계산 병목 현상을 발생시킵니다. 각 반복의 상대적 이득은 알고리즘이 진행됨에 따라 점점 작아집니다.

문제를 해결하기 위해 수천 번의 작은 단계를 거치는 대신 알고리즘이 몇 번의 점프를 수행할 수 있다면 어떨까요? 오늘날 널리 사용되는 대규모 알고리즘 세트가 기하급수적으로 더 빠르게 작동하도록 만들 수 있다면 어떨까요? 우리는 신약을 발견하고 트래픽을 방지하는 데 도움이 되는 알고리즘에 대해 이야기하고 있습니다.

이를 가능하게 하기 위해 하버드 대학의 연구자들은 문제를 해결하는 데 필요한 반복 횟수를 대폭 줄여 계산 속도를 기하급수적으로 높이는 "돌파"라는 새로운 유형의 알고리즘을 고안했습니다.

정보 추출, 경매 설계, 머신 비전, 전산 생물학, 네트워크 분석 등 다양한 영역에 걸쳐 광범위한 문제에 대한 계산 속도를 높입니다.

개발자에 따르면 이전에는 며칠 또는 몇 주가 걸렸던 대규모 계산을 몇 초 만에 수행할 수 있습니다. 이는 새로운 대규모 병렬화 접근 방식의 문을 열어 실용적인 요약 프로세스를 탁월한 규모로 구축할 수 있게 해줍니다.

어떻게 작동하나요?

순차 알고리즘은 한 번에 한 단계씩 실행 가능한 솔루션의 수를 줄이는 방식으로 작동합니다. 반면, 새로운 알고리즘은 서로 다른 방향을 병렬로 샘플링한 다음 관련성이 낮은 방향을 제거하고 가장 유리한(가치가 높은) 방향을 선택하여 솔루션에 도달합니다. 향후 반복에서 무시될 값을 선택적으로 삭제합니다.

획기적인 알고리즘은 적응형 샘플링을 사용합니다 | 연구원 제공

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

참고자료:Harvard SEAS | 하버드 출판물

예를 들어, 작업이 스타워즈와 유사한 영화를 추천하는 것이라면 기존 알고리즘은 스타워즈와 유사한 속성(액션, 모험, 판타지)을 가진 각 단계에 하나의 영화를 추가합니다.

반면 새로 개발된 알고리즘은 영화 세트를 무작위로 샘플링하여 스타워즈와 전혀 일치하지 않는 영화를 잘라냅니다. 이는 스타워즈와 유사한 다양한 영화 컬렉션을 제공합니다(분명히 추천 대상에 슈퍼맨 영화 10편은 포함되지 않음).

알고리즘은 추천할 항목이 충분할 때까지 각 단계에서 다양한 영화를 계속 추가합니다. 모든 단계에서 중요한 결정을 내리는 열쇠는 적응형 샘플링 프로세스에 있습니다.

문제를 해결하기 위해 순차(검은색) 및 돌파(빨간색) 알고리즘이 수행한 단계 수

테스트 및 적용

연구원들은 6,000명의 사용자가 보낸 4,000편의 영화에 대한 100만 개의 평가가 포함된 대규모 데이터 세트에서 적응형 샘플링 알고리즘을 테스트했습니다. 기존 알고리즘보다 20배 빠른 속도로 개인 맞춤형 다양한 영화 추천에 성공했습니다.

그들은 또한 택시 배차 문제에도 이 알고리즘을 적용했습니다. 즉, 제한된 택시로 최대 수의 고객에게 서비스를 제공할 수 있는 최적의 위치를 선택했습니다. 200만 번의 택시 운행에 대해 알고리즘은 최신 기술보다 6배 빠르게 작동했습니다.

소셜 미디어 분석이나 유전자 데이터 클러스터링과 같은 대규모 데이터 세트에서 훨씬 더 나은 결과를 얻을 수 있습니다.  이 외에도 이 알고리즘은 다양한 질병에 대한 임상시험 개발, 의료 영상용 센서 배열, 약물 간 상호 작용 감지 등에 적용될 수 있습니다.

읽기:새로운 자율 주행 차량 알고리즘으로 차선을 공격적으로 변경할 수 있습니다

요즘에는 수백만 개의 이미지/비디오에서 딥 러닝 네트워크를 훈련하기 위한 효과적인 데이터 하위 집합을 찾는 것이 어려운 작업이 되었습니다. 이 연구는 귀중한 하위 집합을 신속하게 추출하는 데 도움이 될 수 있으며 대규모 데이터 요약 문제에 상당한 영향을 미칠 수 있습니다.