Algorithmic approaches to avoiding bad local minima in nonconvex inconsistent feasibility

현대 물리학의 세계에서 과학자들은 빛을 산란시키는 방식을 분석하여 분자의 보이지 않는 구조를 재구성하려고 노력하곤 합니다. 전자의 빔을 물질에 투사하고 튕겨 나오는 빛의 패턴을 포착한다고 상상해 보십시오. 각도 분해 광전자 분광법(angle-resolved photoemission spectroscopy)으로 알려진 이 기술은 분자의 전자 구름의 형태라는 비밀을 간직한 복잡한 데이터 지도를 만들어냅니다. 그러나 산란된 빛을 다시 명확한 분자 이미지로 바꾸는 것은 매우 어려운 난제입니다. 해결책을 향한 수학적 경로는 함정들로 가득 차 있습니다. 방정식에는 그럴듯해 보이지만 물리적으로는 틀린 수많은 국소 해(local solutions)가 존재하는데, 이는 마치 등산객이 작은 골짜기를 발견하여 산의 바닥이라고 생각했지만, 바로 너머에 훨씬 더 깊은 골짜기가 있다는 것을 깨닫게 되는 것과 같습니다. 진정한 가장 깊은 골짜기, 즉 올바른 분자 구조를 찾는 것은 표준적인 수학적 도구들이 이러한 얕고 잘못된 웅덩이에 빠지기 쉬운 지형을 탐색하는 과정입니다.

괴팅겐 대학교의 연구팀은 이러한 험난한 수학적 지형을 더 효과적으로 탐색하는 방법을 조사했습니다. 그들은 재구성 문제를 해결하기 위해 설계된 세 가지 특정 알고리즘에 초점을 맞추어, 컴퓨터 생성 시뮬레이션과 실제 실험실의 전자 산란 실험 데이터를 모두 사용하여 테스트했습니다. 그들의 연구는 알고리즘이 나쁜 해에 빠졌을 때, 어떻게 하면 더 나은 해를 찾도록 유도할 수 있는가라는 근본적인 질문에 집중합니다. 연구진은 현재 업계의 선호 방식인 순환 투영(cyclic projections) 방식과 더글라스-라크포드(Douglas-Rachford) 알고리즘으로 알려진 기법의 두 가지 변형을 비교했습니다. 표준 방식은 빠르고 신뢰할 수 있게 '하나의' 해를 찾아내지만, 그것이 실제와 아주 동떨어진 근사치일지라도 첫 번째로 발견한 괜찮은 답에 안주하는 경우가 빈번합니다. 연구진은 특정 방식으로 적용된 더글라스-라크포드 알고리즘의 특정 버전이 강력한 필터 역할을 한다는 것을 발견했습니다. 이 방식은 느리고 신중하지만, 얕고 잘못된 골짜기에서 벗어나 빠른 방법들이 놓치는 더 깊고 정확한 해를 향해 올라갈 수 있는 독특한 능력을 갖추고 있습니다.

연구는 실제 실험 조건을 모방한 시뮬레이션 데이터를 사용하여 엄격한 테스트를 설정하는 것으로 시작되었습니다. 연구팀은 각 알고리즘이 결국 어디에 정착하는지 확인하기 위해 100개의 서로 다른 시작점에서 알고리즘을 실행했습니다. 그 결과, 표준 순환 투영 방식이 평균 단 169단계 만에 안정적인 답에 도달하며 속도 면에서 우위를 점한다는 것을 발견했습니다. 그러나 이 속도에는 대가가 따랐습니다. 이 방식은 종종 최선의 적합치가 아닌 해들의 집단에 착륙하곤 했습니다. 순환 버전의 더글라스-라크포드 알고리즘은 약 두 배 더 많은 단계가 소요되어 더 느렸지만, 최선의 해를 찾는 데는 더 뛰어났습니다. 가장 놀라운 발견은 세 번째 접근법인 곱 공간(product space)에 적용된 완화된 더글라스-라크포드 알고리즘에서 나왔습니다. 이 방식은 매우 느릿하여 수천 단계가 필요했고, 많은 경우 전통적인 의미에서 수렴하는 것처럼 보이지도 않았습니다. 하지만 연구진이 최종 결과를 검토했을 때, 이 느리고 방황하는 방식이 나쁜 국소 최솟값(local minima)을 탈출하는 데 탁월하다는 것을 발견했습니다.

연구진은 문제 해결의 핵심이 어떤 알고리즘 하나를 선택하는 것이 아니라, 이들을 특정 순서로 사용하는 것임을 깨달았습니다. 그들의 실험은 최선의 전략이 빠른 표준 순환 투영을 사용하여 빠르게 안정적인 지점을 찾는 것에서 시작하는 것이라고 보여주었습니다. 일단 그 지점이 발견되면, 느린 완화된 더글라스-라크포드 알고리즘으로 전환해야 합니다. 빠른 방법이 찾아낸 위치에서 시작하여, 알고리즘이 더 넓고 탐색적인 단계를 밟을 수 있도록 허용하는 설정인 큰 완화 매개변수(relaxation parameter)를 사용하여 느린 방법을 실행함으로써, 연구진은 솔루션을 얕고 잘못된 골짜기에서 밀어내어 더 깊고 정확한 골짜기로 이동시킬 수 있었습니다. 시뮬레이션 데이터 테스트에서 이 조합은 표준 방식만을 사용할 때보다 훨씬 더 자주 최선의 해를 찾아냈습니다.

연구 결과가 단순히 컴퓨터 시뮬레이션의 결과가 아님을 확인하기 위해, 팀은 동일한 전략을 실제 광전자 실험에서 수집된 실제 실험 데이터에 적용했습니다. 이러한 실제 환경 테스트에서는 '그라운드 트루스(ground truth)', 즉 분자의 정확한 형태를 알 수 없었습니다. 따라서 연구진은 오차를 직접 측정할 수 없었습니다. 대신, 그들은 재구성된 이미지가 문제의 모든 물리적 제약 조건을 얼마나 잘 만족하는지를 나타내는 값인 '갭(gap)'을 측정했습니다. 갭이 작을수록 더 일관성 있고 좋은 재구성을 의미합니다. 실제 데이터에 대해 표준 순환 투영을 실행했을 때, 알고리즘은 특정 갭 크기를 생성했습니다. 그 후 그 결과값을 완화된 더 더글라스-라크포드 알고리즘에 입력했을 때, 갭은 일관되게 줄어들었습니다. 100개의 서로 다른 시작점 모두에서, 두 번째 단계는 결과를 개선하여 물리적 제약 조건이 더 엄격하게 충족되는 상태로 솔루션을 이동시켰습니다.

또한 연구는 실험 데이터가 시뮬레이션 데이터와 다르게 행동한다는 것을 밝혀냈습니다. 실제 측정값은 물리적 실험에 내재된 노이즈가 수학적 지형의 가장 극단적이고 어려운 함정들을 부드럽게 만들기 때문에 더 규칙적인 것처럼 보였습니다. 이러한 규칙성에도 불구하고, 느린 알고리즘을 사용하여 빠른 알고리즘을 정교화하는 전략은 여전히 유효했습니다. 연구진은 표준 방식이 특히 좋지 않은 솔루션을 찾아낸 몇몇 사례에서, 완화된 더글라스-라크포드 알고리즘이 재구성을 상당히 다르고 더 나은 구조로 변화시킬 수 있음을 관찰했습니다. 이는 느린 알고리즘이 빠른 방식이 최선의 답을 찾는 데 실패하는 드물지만 결정적인 경우들을 잡아내는 안전망 역할을 한다는 것을 확인시켜 주었습니다.

이 연구는 위상 회복(phase retrieval)이라 불리는, 파동 데이터로부터 이미지를 재구성하는 물리학의 관련 분야에서 오랫동안 지속되어 온 관행에 도전합니다. 수년 동안 표준 절차는 더글라스-라크포드 유형의 알고리즘을 몇 단계 실행하여 이미지의 대략적인 윤곽을 잡은 다음, 세부 사항을 '정리'하기 위해 더 빠른 순환 투영으로 전환하는 것이었습니다. 괴팅겐 팀의 연구 결과는 이 순서가 거꾸로 되어 있음을 시사합니다. 그들의 결과는 먼저 빠른 순환 투영을 사용하여 발판을 마련한 다음, 느린 완화된 더 더글라스-라크포드 알고리즘을 사용하여 국소적 함정에서 벗어나 진정한 전역 해(global solution)를 찾아야 함을 나타냅니다. 느린 알고리즘이 그 자체로는 효율적이지는 않지만, 빠른 방법들이 피할 수 없는 나쁜 솔루션들을 걸러내는 강력한 도구로 기능합니다.

이 발견의 함의는 복잡한 이미징 데이터를 다루는 연구자들에게 실질적이고 즉각적입니다. 단순히 연산 순서를 바꾸고 마지막 단계에 사용하는 매개변수를 조정하는 것만으로도, 과학자들은 새로운 하드웨어나 더 복잡한 이론 없이도 올바른 분자 구조를 재구성할 확률을 크게 높일 수 있습니다. 이 연구는 모든 비볼록 최적화(nonconvex optimization) 문제를 해결했다고 주장하거나, 느린 알고리즘이 모든 경우에 적용되는 마법의 탄환이라고 제안하는 것이 아닙니다. 다만, 이 연구는 재구성 문제의 가장 어려운 부분을 헤쳐 나가기 위한 명확하고 증거에 기반한 로드맵을 제공합니다. 한 방법의 속도와 다른 방법의 탐색 능력을 결합함으로써, 연구진은 분자의 보이지 않는 전자 세계를 더 명확하게 볼 수 있는 새로운 방법을 제시했습니다.