▲

예상치 못한 곳에서 비롯된 새로운 구형 적재 기록

 (quantamagazine.org)
1P by GN⁺ 12시간전 | ★ favorite | 댓글 1개
  • Boaz Klartag는 기존 접근과 달리 초고차원 구 적재 문제에 볼록기하학 도구를 도입함
  • Klartag의 새로운 임의적 방법은 더 큰 부피의 타원체를 생성해 기존의 기록을 대폭 갱신함
  • 이 접근법은 고차원 공간에서 구를 극적으로 더 많이 적재할 수 있게 함
  • 이번 결과는 적재의 질서와 대칭성의 중요성에 대한 논쟁을 부활시킴
  • 연구는 암호학과 통신 분야 등 다양한 응용 가능성에 대해 주목을 받음

기존 구 적재 연구와 제한

  • 과거 Rogers 방법의 장점은 시작 격자가 반드시 효율적일 필요 없이 적절한 타원체만 선택하면 된다는 점이었음
  • 하지만 타원체의 축은 고차원에서 다양하게 변형될 수 있으므로, 어떤 형태로 성장시킬지 선택지가 지나치게 많았음
  • 이후 수학자들은 Minkowski 방식으로 회귀해 격자 자체에 집중했고, 격자 이론에 전문화됐으며 Rogers의 기하 중심 접근에서 멀어졌음
  • 이 전략은 고차원 구 적재에서 점진적 개선을 보였으나, Rogers 방식 대비 근소한 효율 향상에 그쳤음
  • 수십 년간 큰 도약은 나오지 않았고 정체 상태가 이어졌음

외부 시각에서 시작된 혁신

  • Weizmann Institute of Science의 Boaz Klartag는 원래 격자 이론이 아닌 볼록기하학 전공자임
  • 오랜 기간 구 적재문제에 관심은 있었으나 연구 기회를 얻지 못했음
  • 2023년 새로운 시간을 가지게 되어, Tel Aviv University의 Barak Weiss와 세미나를 열어 고전 문헌(Minkowski, Rogers) 를 집중적으로 탐구함
  • Klartag는 Rogers의 타원체 방법이 볼록도형 조작에 대한 노하우 부족으로 비효율적이었다고 판단함
  • 더 효율적인 타원체를 만들면 구 적재의 기록을 새로 쓸 수 있다는 자신감을 가짐

임의적 성장 알고리듬의 도입

  • Klartag는 각 축 방향별로 타원체 경계를 임의로 팽창/수축시키는 자신만의 방법을 적용함
  • 경계가 격자점에 닿으면 해당 방향의 성장을 멈추고, 다른 방향으로는 성장 지속
  • 이 과정에서 타원체는 불규칙한 형태로 공간을 탐색하며 점차 커짐
  • 임의적 특성으로 생성 타원체마다 부피가 다르기 때문에 여러 번 실험하여 더 큰 부피의 타원체 가능성을 평가함
  • 몇 주 만에 기존 Rogers보다 큰 타원체가 나올 수 있음을 증명함

기록 갱신과 영향

  • 새로운 타원체 방식은 Rogers(1947) 이후 최대폭의 구 적재 효율 개선을 달성함
  • 차원이 d일 때, 이전 방식 대비 d배나 많은 구 적재가 가능함
    • 100차원 → 약 100배, 1,000,000차원 → 약 100만 배의 구 적재
  • Klartag는 볼록기하학에서의 통찰로 격자와 구 적재의 오래된 중앙 문제를 몇 개월 내에 돌파함
  • 그의 성과로 질서와 대칭성 기반 적재가 가장 촘촘한 적재를 달성할 수 있다는 견해가 다시 부각됨
  • 반면 최근에는 규칙적인 격자 없이 무질서함을 이용해야 한다는 연구도 경쟁함

평가와 미래 전망

  • 현재 Klartag의 적재 방식이 진정한 최적에 가까운지, 추가 개선 여지가 있는지에 대해 학계 내부에서 논쟁이 있음
  • 이 문제의 해답은 암호학, 통신공학 등 실제 적용에서도 매우 중요함
  • 아직 실무 적용 단계는 아니지만 공학계 등에서 신기술로 주목받고 있음
  • Klartag는 이번 계기로 볼록기하학과 격자 이론의 연계가 강화되길 바람
  • 두 분야의 단절을 극복하고 이 융합이 적재 외의 격자 문제 해법까지 확장되길 희망함
▲
GN⁺ 12시간전  [-]
Hacker News 의견
  • 부모님께 내 직업이 실제로 존재하는 일임을 설명하는 게 늘 어렵다는 고백, ‘나는 도형을 연구하는데, 오목하게 들어간 부분이 없는 모양만 연구한다’고 설명하게 되면 더 난감해지는 상황 상상
    • 내 경험상 어려운 전문 용어를 써서 직업을 설명하는 게 제일 낫다는 결론, 선택지는 세 가지로 압축, 부모님이 이해할 만한 비교적 쉬운 설명을 하면 일이 너무 쉬워 보여 ‘정말 이걸로 돈 버는 거야?’라는 반응을 얻게 됨, 제대로 왜 중요한지 설명하면 설명이 너무 길어져서 부모님이 실증을 느끼고 질문한 걸 후회하게 됨, 아니면 복잡한 전문 용어로 간단히 이야기하면 무슨 소린지 모르지만 괜히 대단해 보이는 효과, 그게 가장 나은 선택지
    • 내가 고에너지 물리 장비용 부품을 만드는 마이크로 비즈니스를 하는데, 남들에게 내 일에 대해 설명할 때 대중이 접해 본 적도 없고 실생활과는 여러 단계로 동떨어진, 극도로 이질적이고 마니악한 주제라서 이해시키는 방법을 아직도 못 찾은 실정
    • 나는 그냥 "컴퓨터랑 일해"라고만 말하며, 그러면 “아, 그래 좋은 일이네” 하는 반응과 함께 대화가 끝나는 편리함
    • 나는 주로 “무슨 일을 하느냐”는 질문 자체보다 이후에 “그게 어떻게 쓸모 있지/어디에 쓰지?”라는 질문에 답하는 게 항상 어렵다는 고충, 근본적인 연구가 실제 활용으로 이어지는 긴 연결고리를 짧고 효과적으로 설명하는 방법의 고민
    • 최소한 구의 밀도 쌓기(sphere packing)는 정보이론의 핵심 문제와 밀접하게 연관되어 있고, 그 결과 벨 전화 시스템의 신뢰성이 높아진 것과 이어지는 점에서 역사적 맥락과 중요한 의미를 찾을 수 있음 (볼록 도형에 대해선 잘 모르겠음)
  • 구 모양을 촘촘히 쌓는 방법(sphere packing)을 이용해 벡터 데이터 압축 알고리즘을 고민했던 경험, 이론적 접근은 데이터가 매우 균일할 때만 효과적이고 현실 데이터엔 적용이 어려웠음
    • 비정형(비균일) 데이터를 균일하게 변환하려면 도메인 지식을 활용해서 비대칭성을 줄이는 방법이 통상적인 트릭, 예를 들어, 데이터에 고차원 구조가 있더라도 국지적으로는 노이즈 때문에 꽤 균일해지기 쉽다는 점을 이용, 대표점(centroid)을 계산하고 저장하면, 대표점은 더 균일해지며, 각 벡터를 대표점 인덱스와 벡터 오프셋으로 분리해서 저장, 인덱스는 효율적인 엔트로피 압축에, 오프셋은 이제 거의 균일해졌으니 기존 구 쌓기 전략을 적용하기에 용이
    • 이미 시도해봤을 듯하지만, 사전 압축(precompression)으로 벡터의 희소성을 줄여 균일도 증강 여부 타진
    • 실제 벡터를 만질 때는(grope는 ‘더듬다’, group의 오타) 조심해야 한다는 농담식 지적
    • 이론의 범위를 실전적 과제들(즉 비균질한 데이터)까지 확장할 필요성, 현실의 활용 사례가 너무 다양하다면 일반적인 접근 방식이 힘들 수도 있지만, 그래도 연구의 확장 필요성에 대한 주목
    • 오래된 상업적으로 중요한 분야에서는 이미 쉽게 얻을 수 있는 성과(저걸음마 열매)가 대부분 다 수확됐다는 점의 지적
  • Klartag의 “볼록 도형은 매우 강력하고 활용 가치가 높다”는 주장에 동의하면서, 수학자가 아니지만 Convex Hull 알고리즘이 예기치 않은 곳에서 특히 이미지의 자동 팔레트 분해 등 다양한 문제에서 등장하는 걸 자주 본다고 경험 공유, 참고 논문 링크 제공 Convex Hull and automatic palette decomposition
  • Klartag의 새로운 구 쌓기 방식이 기존 대비 차원이 d라면 d배만큼 많은 구를 쌓을 수 있다는데, 100차원에선 100배, 백만 차원에선 백만배 증가라니 엄청난 수치, 여러 통신시스템에서 이것이 실제로 대역폭이 수십~수백 배 혹은 전력 소모가 크게 줄어든다는 뜻인지 궁금증
    • 실제로는 차원을 높일수록 밀도(density)가 n^2/2^n으로 지수적으로 나빠지기 때문에 이론상의 선형적 개선은 실제 성능에 그대로 다 반영되지 않는다는 점, 즉 자연적으로 고차원 구조를 가진 데이터에는 쓸모 있지만, 디지털 데이터(길이만 정할 수 있음)에는 작은 차원을 택할 수 있음, sphere packing 상세 참조 wikipedia link
  • 수학자는 첫 박사학위 후 몇 년 뒤 같은 분야가 아닌 인접 전공으로 두 번째 박사학위를 할 수 있어야 한다는 생각
    • 박사학위의 근본 목적은 독립적으로 연구할 수 있는 능력의 증명이므로, 실제론 많은 연구자들이 박사졸업 후 다른 분야로 옮기거나 관심 연구 주제를 바꾸며, 그때부턴 ‘연구’ 자체가 중심이 됨
    • 실제로 이런 게 가능한 예시로 유명 수학자 Bela Bollobas는 이산 기하학과 함수해석학 두 분야에서 박사학위 두 개를 갖고 있음, 다만 현대 학계에서 이걸 다시 시도하는 건 매우 어렵겠지만
    • 이런 제도적 유연성이 과학 전반에 있으면 서로 다른 분야 기술과 아이디어가 빠르게 교류돼 과학 발전 가속화 가능성, 특히 수학처럼 분과 간 연결이 중요한 분야에서 더욱 효용 극대화 기대
  • 초보 질문으로, 최적의 구 쌓기(sphere packing)는 항상 정규 격자와 연관 있는지 궁금, 2D, 3D에선 그렇지만 이게 ND로 확장되는지에 대한 궁금증
    • 2, 3차원 외에도 8차원(E₈ 격자)과 24차원(Leech 격자)에서도 best packing이 정규 격자 형태로 증명된 사례가 있음, 이는 Maryna Viazovska와 동료들이 2017년에 입증했으며, 관련 논문 및 참고자료 링크 논문1, 논문2, 해설pdf 제공, 하지만 다른 차원에선 최적 packing이 정규 격자가 아니라는 반례가 존재할 수 있으며, 일부 차원에선 불규칙한 형태가 더 밀도가 높기도 함
    • 반드시 그런 건 아니고, 3차원에서도 lattice(정규 격자)로 쌓는 방법 외에도 층마다 수평 이동을 달리해 수 없이 다양한 비격자 쌓기가 가능, 이때도 밀도는 FCC lattice와 동일, 고차원에선 대칭성이 부족해 최적 packing이 항상 비격자라는 추측도 있음
  • 이 새 구 쌓기 구조가 기존 최고 밀도가 증명된 차원에서 어디서부터 더 뛰어난가에 대한 최소 차원에 관한 궁금증
  • 본 연구의 결과가 암호학 및 통신분야에서 실질적으로 더욱 안전하고, 더 신뢰성 있으며, 더 에너지 효율적인 통신 시스템 개발에 활용될 수 있을지에 대한 발전 방향 제시, 매우 흥미로운 연구 분야임
  • 실제 물리학에서 ‘Cow Packing’(이론적으로 소를 최적 밀도로 채우는 연구 등)에 실용적 응용 가능성이 언급된 재치 있는 비유
  • 구 쌓기는 응용 분야에서 정말 다양한 문제에 나타나서 흥미로움, 논문 정독 기대
답변달기