Month: 8월 2020

구글의 랜덤회로샘플링은 좋은 평가기준일까?

Hhan댓글 남기기

작년 화제가 된 구글의 양자우월성 증명은 양자랜덤회로를 만들고, 그 결과를 측정(measure)하여 얼마나 올바른 분포를 만들었는지를 관측하는 XEB Fidelity benchmark를 사용했다. 지난번 관련된 글을 두개 써서 현황을 설명하기도 했다.

그런데 실제로 우리가 쓸 것으로 예상되는 회로들은 Grover의 알고리즘이나 HHL의 선형방정식 알고리즘, 양자 머신러닝, Shor의 알고리즘등 같은 연산을 반복하거나 (Grover, HHL) 비슷한 연산을 반복하는 양자 Fourier 변환등을 이용하게 된다. 즉, 우리가 실제로 쓸 연산은 랜덤회로와 달리 굉장히 구조적이라는 것.

그렇다면 과연 구글의 양자랜덤회로 샘플링을 통한 평가가 우리가 실제로 쓸 것으로 예상되는 “구조적”인 알고리즘을 평가하는데에 얼마나 도움이 될까? 가장 이상적으로는 랜덤회로나 구조적인 회로나 비슷한 수준의 에러를 갖거나, 구조적인 회로가 더 적은(!)에러를 갖는 경우일 것이다.

하지만 안타깝게도, 어제 아카이브에 올라온 논문에 따르면 실제로는 그 반대인듯 하다고 한다. 즉,

현재 기술로는 양자랜덤회로 샘플링이 구조적 알고리즘보다 쉽다

라는 것. 그러니까, 양자랜덤회로의 에러가 구조적 알고리즘의 에러보다 더 작다는 말.

다만 이 실험은 구글의 Sycamore가 아닌, 실험하기 더 쉬운 IBM Q와 Rigetti의 양자컴퓨터를 이용해서 진행했다고 하니 Sycamore의 경우는 어떤지 아직 알수는 없다. 그 실험적 결과는 아래와 같다.

Image
논문에서 가져온 그림. 오른쪽 그래프는 보지 않아도 된다. (a), (b)에서 각 칸은 실험에서 사용한 큐비트 수(width)와 회로의 깊이(depth)에 따라 배치되었으며, 내부의 색은 랜덤회로의 정확성, 외부의 색은 구조적 회로의 정확성을 나타낸다. 붉을수록 부정확하고, 푸른색/녹색일수록 정확함을 표시한다. (a)는 실험 결과에서 나타난 정확성이고, (b)는 서버에서 제시한 회로의 오차를 통해 예측한 정확성.

위 그림을 살펴보면 꽤나 부정적인 결과를 여럿 얻을 수 있다.

  • 전체적으로 회로의 정확성이 예측보다 훨씬 못한 편이다.
  • 대체적으로 구조적 회로가 랜덤회로보다 훨씬 부정확하다. (가끔 그렇지 않은 경우도 있긴 하다)
  • 7큐비트정도부터는 depth를 조금만 늘려도 전부 다 제 멋대로 나오는듯 하다.
  • IBM Q Melbourne은…. 뭔가 문제가 있어 보인다.

근데, 지난 글에서 구글의 실험 자체가 옳은지를 검증하는게 어렵다는 말을 한적이 있다. 이 논문에서 어떻게 구조적 회로와 랜덤회로의 정확성/에러를 확인한걸까? 마지막으로 논문에서 이 부분을 어떻게 해결했는지 살펴보자.

저자들이 사용한 방식은 거울회로, 혹은 실험에 사용한 회로 C의 역인 C-1, 혹은 그의 변형을 생각하는 것이다. 논문에서는 다음과 같이 그림으로도 설명해준다.

Image

대충 원래 적용한 회로의 역, 혹은 그거를 약간 변형한 방식을 한번 더 적용함으로써 답이 고전상태로 정해지는 독특한 회로를 만든것.

이 회로의 결과는 고전컴퓨터로 계산/검증이 쉽지만 에러가 있는 양자컴퓨터로는 계산하기 어렵다. 어찌보면 양자우월성에서 필요했던 회로의 듀얼 버젼인데, 이걸 이렇게 간단히 만들 수 있다는 사실이 신기하군ㅋ

악의적 비서 문제

Hhan댓글 남기기

n명의 후보자가 순서대로 면접을 보러 오는 상황에서, 각 면전에서는 각 후보자의 점수를 정확히 알 수 있고, 그 점수를 바탕으로 후보자의 합/불 여부를 면접하는 즉시 결정하여 최고의 점수를 가진 후보자를 뽑는 비서 문제에 대해서는 다들 들어보았으리라고 믿는다.

보통의 문제에서 (거의) 최적의 전략은 n명중 약 n/e을 먼저 확인하여 최고점을 측정한 후 나머지 사람중 그 점수를 넘는 사람을 고르는 것. 이러는 경우 약 1/e의 확률로 최고점수의 사람을 고를 수 있다는 것은 잘 알려져 있다.

사실 이 문제는 최근 많은 주목을 받고 있는, 데이터를 연속적으로 받는 온라인 알고리즘 혹은 스트리밍 알고리즘의 한 문제로 볼 수 있다. 그리고 이런 문제들은 데이터를 악의적으로 조작한 상황에 얼마나 우리가 잘 해낼 수 있는지를 많이들 궁금해 한다. 즉, 다음과 같은 상황을 생각해 볼 수 있다.

경쟁사에서 첫 후보자로 (다른 모든 후보를 뛰어넘는) 엄청난 능력자를 보내는 경우, 이 전략은 100%로 실패하게 된다!! 혹은 몇몇 후보자들이 회사가 이 전략을 쓴다는 것을 아는 순간 그 후보자들은 후반 순서를 받기를 원할 것이고, 이 경우에도 뭔가 이상해 질 것이고. 또, 만약 한 명이 아니라 여러명의 비서를 뽑고싶다면 어떻게 될까?

이러한 상황이 악의적 비서 문제, 혹은 음모적(Byzantine) 비서 문제라고 한다. 과연 이런 악의적으로 정해진 상황에서 훌륭한 비서를 뽑을 수 있을까? 이 글은 이 문제에 대한 ITCS 2020에 발표된 논문의 결과를 소개하는 것이 목표이다. 아쉽게도 알고리즘 자체는 꽤나 복잡하고, 대략적인 아이디어만 소개하는 것이 목표.

계속 읽기 →

에러정정부호를 이용해 효율적인 COVID-19 검사가 가능하다

Hhan댓글 남기기

지난번 Zariski님의 포스트와 뉴욕타임즈 기사에 따르면 n명에 대한 COVID-19 검사를 실행하는데 뭔가 Group testing같은 기법을 이용해서 n/5번의 PCR검사로 가능하다고 한다. 즉 5배의 효율로 검사를 할 수 있다는 것.

과연 5배보다 더 잘 할수 있을까? PCR 검사에는 에러가 많을텐데, 이론적으로 에러에 robust한 것을 보장할 수 있을까?

놀랍게도 Science Advances에 실린 한 논문에 의하면 1.3%정도 이하의 사람이 양성인 경우 n명에 대해 n/8번의 PCR으로 검사 가능하다고 한다. 심지어 어느정도 에러에 robust 하다고 증명이 가능하다고 주장한다.

그 방법은 384명을 48개의 검사지로 나누고, 각 사람을 정확히 6개의 검사지에 넣어 각 검사지에 사람을 48명이 포함되게 만들고, 이를 이용해 분석한다고 한다. 각 사람이 어떤 검사지에 포함되는지는 Reed-Solomon Error correction code를 이용해 결정한다고.

방법이 굉장히 신기해서 좀 읽어보려고 했는데, -_- 도저히 무슨말인지 이해가 안된다. 대충 알아들은 것을 적으면

  1. 48개의 검사지 중 40개 미만의 검사지가 양성이라고 가정하고,
  2. Gradient Projection for Sparse Reconstruction 라는 방식을 이용해 가장 의심스러운 20명을 골라낸다.
  3. 뭔가 optimization을 거쳐서 양성자를 찾아내는 듯 하다…?

당최 무슨말인지 이해할 수 없다 -_- Reed-Solomon code는 어떻게 썼다는 걸까? 결과는 놀랍지만… 이해하려면 시간을 더 들여야 하는듯 한데 그만큼 흥미는 없어서 패스..ㅋㅋ

정다면체는 48개 있다

Hhan댓글 한 개

우리는 초~중학교때 쯤 정다면체가 정사면체, 정팔면체, 정십면체, 정십이면체, 정이십면체의 5개가 있다고 배운다. 그리고 그 사실을 “증명”까지 했던 것 같다! 굉장히 빈약한 논리이긴 했지만 ㅋ. 하지만 아래 유튜브 영상에 따르면 사실 정다면체가 48개나 있다고 한다!!!

그림도 그려가며 아주 재미있게 설명하니 앞부분 일부를 슥슥 뛰어가며 감상하는 것을 추천. 누군가 한글 자막도 달아주었다!!

어릴 때 한 “증명”은 사실 문제가 없고, 그 정의가 엄밀하지 않았던 것에 있다. 우리가 했던 증명을 따르려면 다면체는 항상 볼록이여야할거고, 겹치는 부분이 없고, 어쩌구 저쩌구… 이런저런 조건들이 많이 필요하다. 이 영상에서 (그리고 아마 역사적으로) 고려한 “정다면체”는 각 면이 정다각형인 것보다 약간 일반적인 정의를 생각한다.

우선 정다각형은 각 변의 길이/변 사이의 (방향)각이 같은 것으로 생각한다. 근데 사실 이게 한 점을 “다음” 점으로 옮기면서 다각형의 형태를 유지할 수 있다는 것을 말하는 것이고, 이것을 “정다각형”으로 정의한다.

마찬가지로 정다면체는 임의의 꼭짓점/변/면을 다른 꼭짓점/변/면으로 옮기며 형태를 유지한 변환하는 점/변-추이성이 유지되는 3차원 공간의 다면체로 정의한다. 다면체는 각 변이 정확히 두개의 면의 교집합이여야 하고.

그러면 여기서 새로운 정다면체는 어떤 것들이 있을까? 원래 우리가 아는 정다면체 5개를 먼저 세자.

  1. “별 모양” 같은 것도 사실 정다각형으로 생각할 수 있고, 이걸로 정다면체를 만들 수 있다. (이게 4개라고 한다.)
  2. 정삼/사/육각형으로 평면을 가득 채우는 타일링도 사실 저 정의에서는 정다면체가 된다. (3개) 이처럼 공간에 무한히 뻗어가는 다른 정다면체들도 여러개 있다. (이런게 3개 더 있다고 한다)
  3. 사실 정다면체가 정다각형인 면으로 이루어 질 필요가 없다는 것을 관찰하면 (이름과는 조금 다르지만…….), 각 “면” 비슷한 것이 정다각형의 각 변을 꼬아서 만든 것으로 만들어서, 새로운 15개의 정다각형을 만들 수 있다고 한다.
  4. 이 다음부터는 더욱 더 복잡해지는듯 한데, 여러가지 테크닉, 예를 들어 정사각형을 위상수학에서 원의 covering space R을 생각하듯이…. 쭉 늘려서 새로운 3차원상의 정다각형을 만들고 이를 이용하는 방식으로 새로운 18개의 정다각형을 만들수 있다고 한다.

말로 설명하는 것보다 동영상이 훨씬 재밌을듯 하다. 그림을 그려주는 것에서 확실히 좋다 ㅎㅎ.

양자컴퓨터도 XEB Fidelity를 더 잘 속일수는 없다

Hhan댓글 한 개

작년 구글의 양자컴퓨터 실험과 그 이후의 고전 시뮬레이션 발전에 대해 지난번 글에서 소개한 바 있다. 다음과 같이 정의되는 XEB Fidelity를 다시 불러오자.

\displaystyle {F}_C(p):=2^n \sum_{x\in\{0,1\}^n} p(x)q_C(x) -1

여기서 C는 타겟이 되는 random circuit이고, p는 테스트하고자하는 확률 분포, q_C는 C의 결과로 나오는 확률 분포. 이 XEB값은 p가 유니폼 랜덤이면 Fidelity가 0이 되고, p=q_C가 되면 (C의 structure때문에) 1이 된다고 한다.

이러한 설명 하에 지난번까지의 양자우월성 실험에 대한 결론은 다음과 같다.

  • XEB Fidelity는 구글 실험에서 0.00224를 달성한다.
  • 강력한 가정하에, C의 depth d를 키우면 고전컴퓨터는 XEB Fidelity를 (구글 실험보다도) 크게 만들 수 없다.
  • (구글 실험과 겹치지 않는) 특정한 파라미터에서는 고전컴퓨터가 XEB Fidelity를 1에 가깝게 만들 수는 있다.

그치만 고전컴퓨터는 depth가 클 때 XEB Fidelity가 거의 항상 0에 가깝고, 양자컴퓨터로 구글의 실험을 하면 노이즈가 줄어들수록 XEB Fidelity가 1에 가까워지니 이걸로 “양자우월성”을 증명하겠다는 것이 구글의 전략이였다.

근데 여기서 잠깐 XEB Fidelity의 정의를 살펴보면, 이 값은 굳이 0~1 사이의 값이 될 필요는 없다. 괴상하게 p를 잘 잡으면 1보다 더 커질 수 있는 값이다!

그렇다면 여기서 질문: 양자컴퓨터를 이용하면 XEB Fidelity를 어떻게 잘 “속여서(Fool)” 1보다 더 크게 만들 수 있지 않을까? 예를들어 100이나 d2같은 값으로? 이렇게 하면 XEB Fidelity를 크게 키우는 것에 집중했을 때 (마지막 결과의) 고전컴퓨터를 이용한 시뮬레이션보다 훨씬 큰, 더 강력한 결과가 되지 않을까?

(안타깝게도) 오늘 나온 논문의 결과에 따르면, 그게 안될 가능성이 높다고 한다.

조금 자세하게는 C는 임의의 회로, 즉 uniform random unitary map으로 잡으면 임의의 ε>0에 대해 XEB Fidelity를 1+ε보다 크게 만드는 실험을 하려면

\displaystyle\frac{2^{n/4}}{poly (n)}

보다 큰 개수의 샘플이 필요하다고 한다. 그리고 샘플이 2^{n/3}개 정도 있으면 실제로 XEB Fidelity를 2에 가까운 정도로 크게 만들수 있다고.

그러니까, 신기하게도 구글의 실험에서 한 단순한 실험이 XEB Fidelity를 키우는데에는 어느정도 최적의 알고리즘 중 하나라는것!

다만 해석에는 여지가 약간 있는데, 논문에서 C를 depth가 작은 임의의 회로가 아닌 uniform random unitary map으로 잡았다. 이건 사실 효율적으로는 구현이 불가능한 회로이고, 이론적으로 뭔가를 증명하기가 훨씬 좋은 이상적인 대상이다. 뭐 여튼 구글의 단순한 실험이 XEB Fidelity 값을 최대로 만드는 방식일 것이라는 강력한 근거는 된다 ㅋ.

난독화 이야기 (1) 가상 블랙박스 난독화는 불가능하다

Hhan댓글 남기기

한동안 연구 주제로 잡았던 것 중 프로그램을 “읽기 어렵게 만드는” 난독화라는 기술이 있다. 프로그램 난독화 기술은 여러가지 이유로 2013년 정도부터 (이론적) 암호학에서 현재 가장 중요한 주제로 떠올랐다.

특히 구별불가능성 난독화(Indistinguishability Obfuscation)의 존재성이 그 핵심 문제인데, 이를 가장 활발히 풀던 연구자들이 해당 기술이 가능하다고 주장하는 논문을 최근 포스팅했다.

따라서 이를 기념(?)하기 위해 이 방향의 연구의 큰 이야기들을 몇 개의 글로 정리해보고자 한다. 다만 의욕이 항상 없어 다음 이야기가 언제 나올지는 의문 ㅋ

이번 글에서는 프로그램 난독화의 초창기 결과인 2001년의 보아즈 바락(Boaz Barak)등이 증명한 가상 블랙박스 난독화(Virtual Black-box Obfuscation)이 불가능하다는 논문에 대한 이야기를 하고자 한다. 증명이 아주 간단하다!

계속 읽기 →

얼굴 인식 기술을 속일 수 있을까?

Hhan댓글 2개

일전에 얼굴인식 기술이 미국에서, 특히 경찰이 그 완성되지 않은 기술을 사용하는데에 대해 우려가 있다는 글을 포스팅 한 적이 있다. 그 뿐만 아니라 얼굴 인식 기술이 예측하지 못한 방식으로 개인을 추적하고, 그 추적한 정보를 이용해 스토킹을 하거나 개인과 협상하는데에 다양하게 악의적으로 이용할 수 있는 등의 위험성이 크다. 심지어 올해 초의 뉴욕타임즈 글에 따르면 Clearview라는 스타트업은 이미 30조개 이상의 사진을 수집하고 이를 이용해 기술을 개발하고 있다고 한다.

이에 따라 자연스럽게 떠오르는 질문은 얼굴 인식 기술을 어떻게든 무효화 시킬 수 있겠냐는 것. 시카고 대학의 연구자들의 대답은 다음과 같다.

현재의 얼굴 인식 기술은 꽤 강하게 무효화할 수 있다!

USENIX security 2020 학회에 발표된 논문의 저자이 개발한 Fawkes라는 기술을 이용하면 우리가 보는 이미지를 (저자들의 표현에 따르면) “클로킹”시킬 수 있다고 한다. 사람에게는 비슷하지만 현재 얼굴 인식 기술들에게는 꽤나 다르게 보이는 새로운 이미지를 만들 수 있다는 것. 이 클로킹 기술은 심지어 저자들의 소개 페이지에서 다운로드해서 이용 가능하다!

Image
원본 이미지(왼쪽)와 클로킹된 이미지(오른쪽)

논문에 따르면 Fawkes의 클로킹은 다음과 같은 정도로 얼굴 인식 기술의 무효화를 달성한다.

  • 최신 얼굴 인식 기술을 제공하는 Microsoft Azure, Amazon Rekognition, Face++등의 기술에게 클로킹된 이미지를 학습 데이터로 제공한 경우, 그 학습 모델은 새로운 클로킹 되지 않은 이미지를 잘못 분류할 가능성이 거의 100%에 달한다. 여기서는 Fawkes가 해당 모델의 Feature extractor (FE)를 알고, 정확히 같은 FE를 쓴다고 가정한듯.
  • 얼굴 인식 기술 Fawkes가 알지 못하는 FE를 쓰는 경우나, 모델이 그냥 이미지 자체에서 얼굴인식을 해내는 경우에도 95%이상의 확률로 클로킹되지 않은 이미지를 잘못 분류했다고 한다.
  • 얼굴 인식 기술이 클로킹 되지 않은 이미지도 학습 데이터로 쓰는 경우, 학습데이터중 클로킹된 이미지가 많아지면 많아질수록 얼굴인식이 실패할 확률이 높아졌다고 한다. 특히 클로킹된 이미지와 되지 않은 이미지의 비율이 1:1인 경우정도부터 95%정도의 확률로 잘못 분류하기 시작했다고.

굉장히 흥미롭다! 다만 얼굴 인식 기술이 항상 불가능함을 증명할수는 없는듯. 어찌보면 당연한게, 사람은 구별 가능해야할테니… 자세한 소개는 저자들의 유튜브 영상에잘 설명되어 있다.

Authors’ presentation

그렇다면 여기서 몇 가지 질문이 떠오른다.

  • 특정한 Class의 얼굴인식 기술에 대해 증명 가능한 무효화 기술은 없을까? 예를 들어, 푸리에 변환을 이용한다거나, 특정한 Feature만 쓴다거나.. 이런 것은 암호학적 기술과 결합하면 꽤나 그럴듯한 시나리오처럼 보이는데, 글쎄 -_-…머신러닝을 잘 모르니..
  • 실제 Fawkes된 이미지를 보면 원래 이미지와 약간 달라 보이는데, 조금 궁금한것은 원래 얼굴 인식 기술이 촬영/보정 어플을 적용한 경우에도 잘 작동할까? 그렇다면 촬영/보정 어플을 적용하고 Fawkes를 쓰면 안전성/보정 측면 모두에서 만족할만한 결과가 나올까?

암호학 단신

Hhan댓글 남기기

1. 유한체 \mathbb F_{2^{30750}} 위에서의 이산로그가 풀렸다는 소식. 기존의 유한체위의 이산로그 최고기록은 2014년의 \mathbb F_{2^{9234}} 에서의 문제였고, NMBTHRY mailing list 항목에서 확인할 수 있다. 기존 기록은 45 core-year가 필요했고, 이번 기록은 2900 core-year가 들었다고 한다. 지난번 정수위에서의 소인수분해/이산로그 글에서 소개했던 것도 있고, 이런 실험들을 하는 여러 그룹들이 있는가보다.

2. 7월 7일 새로나온 논문에 따르면 소인수분해 등을 푸는데 사용되는 NFS (Number field sieve)의 점근적 시간복잡도가 약간 현실과 맞지 않는다고 한다. 좀 자세히 말하면, NFS의 복잡도는 다음과 같다.

\exp\left(\sqrt[3]{\frac{64}{9}} (\log N)^{1/3}(\log \log N)^{2/3} (1+o(1))\right)

여기서 주로 $o(1)$ 항을 0으로 두고 최적화를 진행하는데, 이 $o(1)$ 항이 0에 가까워지려면 $N>\exp(\exp(25))$정도는 되어야 하고, 따라서 지금까지 이를 이용한 최적화가 현실적으로 다양하게 약간 잘못되었을 수 있다고. 이런걸 고려하면 소인수분해를 약간은 더 빨리할 수 있을듯.

3. 암호학적 증명을 컴퓨터로 확인할 수 있다는 소식. 특히 IND-CPA 공개키 암호를 IND-CCA후지사키-오카모토 변환의 대양자 안전성 증명을 컴퓨터로 확인했다는 논문.

논문에 따르면 암호학계의 증명이 틀리는 것은 꽤나 흔한 일이라고 한다. 예를 들어 일전에 소개한 OCB2의 증명이 틀렸다는 소식이나, 더 이전에는 RSA-OAEP라는 산업에서도 굉장히 잘 쓰이는 RSA의 변형의 안전성이 틀렸고, 여러번 수정되었다는 사실 (링크된 위키페이지에도 잘 소개되어있다.), 그리고 난수함수와 난수행렬이 구별이 어렵다는 유명한 PRF/PRP switching lemma의 교과서에도 소개되던 증명이 틀렸다는 사실 등. 그래서 Code-based game-playing proof라는걸 로가웨이와 벨라르가 소개하며 안전성 증명의 컴퓨터 검증의 방향을 제시했고, 그 이후 여러가지 논문이 정말 있었나보다. (이 논문 등) 이번에는 그런 방향을 양자안전성 증명까지 확장한듯. 증명 검증 툴은 Coq정도만 알고있었는데, 생각보다 다양한 것이 있군.

하드웨어와 알고리즘의 발전 중 무엇이 빠를까?

Hhan댓글 남기기

컴퓨터 과학과 공학은 최근 수십년간 엄청난 주목을 받고, 특히 문제를 푸는 알고리즘과 그를 실행하는 하드웨어에서 큰 발전을 이루어내고 있다.

알고리즘쪽은 컴퓨터가 풀 수 있는 “효율적인” 문제가 무엇인지에 대답하기 위해 발전하고, 이 블로그의 글중 많은 부분에서 여러 발전을 소개하고있다.

하드웨어 부분에서는 최근까지도 상수년에 2배의 속도가 빨라진다는 무어의 법칙에 거의 따라가며 발전하고 있고, 이 발전은 많은 뉴스기사를 보거나, 당장 우리가 쓰는 컴퓨터를 실행해 봐도 실감할 수 있다.

그렇다면 여기서 질문: 최근의 하드웨어와 알고리즘은 무엇이 더 많이 발전했을까?

물론 일반적으로 두 발전을 비교하는 것은 불가능하다. 특히, 하드웨어는 일반적인 발전정도를 단위연산별로 계측하여 어느정도는 측정할 수 있지만, 알고리즘의 경우에는 어떤 문제를 푸냐에 따라 그 발전정도가 천차만별이다. 심지어 몇몇 문제의 경우는 특수한 경우에 훨씬 잘 풀기도 하고. 지난 글에서 슬쩍 언급했듯이 몇몇 문제는 수십년간 발전이 거의 없는 정도이다.

대신 얼마전 유럽의 연구자들이 Arxiv에 구체적인 문제를 대상으로 비교방식을 제시하는 논문을 포스팅했다. 논문에서는 구체적으로 주어진 식을 만족하는 해가 존재하냐고 묻는 SAT문제를 대상으로 비교를 진행했다. 찾아보니 SAT Competition이 계속 진행되고 있을정도로 활발하게 연구되는 분야이니, 꽤나 괜찮은 대상인듯.

논문의 결과를 간단히 요약하자면 다음과 같다.

Image
Taken from the paper.

여기서 각 항목은 200개의 SAT 인스턴스 중 해결한 인스턴스의 개수를 말하고, 가로축은 서로 다른 SAT-solver 알고리즘들을 뜻하고, 세로축은 1999년과 2019년의 하드웨어, 정확하게는 다음 세팅을 썼다고 한다.

  • 1999년: Pentium III processor (467MHz) + 1.5GB RAM
  • 2019년: Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM

저자들은 Team SW, Team HW를 나누어 각자 구현했다고 한다. 결과에 따르면 다음과 같이 말할수 있다.

SAT문제에 관해서는 알고리즘의 발전이 하드웨어의 발전보다 약간 더 빠르다!

몇가지 관찰이나 세팅은 아래에 정리해둔다.

  • 각 결과들은 200개의 인스턴스중 900초안에 풀리는 인스턴스의 개수를 센 것이다.
  • 인스턴스들은 알려진 벤치마크들로 여러가지 만들어진 것으로, 테스트를 위한 적절한 크기/방법을 골랐다고 한다. 아마 Random SAT등으로 고르면 일부 세팅은 거의 전부 푸는데 다른 세팅은 전혀 못푸는 그런 상황이 벌어졌을듯. 특히 set-asp-gauss라는 벤치마크가 가장 적절하여 이용했다고 한다.
  • 2019년에 가장 좋은 알고리즘으로 알려진 Maple SAT solver가 1999년 하드웨어를 쓴 경우 다른 알고리즘보다 약간 더 못푸는 경우가 발생했다. 저자들도 정확한 이유를 알지는 못하고, 아마 좋은 알고리즘에서 사용한 특정한 자료구조가 현대 하드웨어에 훨씬 적합한게 아닐까.. 같은 추측을 한다.
  • 사실 SAT 알고리즘은 1990년대 후반 등장한 CDCL (Conflict-Driven Clause Learning)이라는 방식을 아직 기반으로 사용하고 있다고 한다. 물론 다양한 발전이 있긴하다! 심지어 CDCL도 DPLL (Davis–Putnam–Logemann–Loveland)이라고 하는 1960년대 알고리즘을 기반으로 발전했다고 한다. 역시 알고리즘의 큰 줄기는 1960년대에 다 나온듯 ㅋㅋㅋ

과거의 알고리즘에 비해 얼마나 좋아졌는지 뭔가 직관적으로 볼 수 있는 결과가 있으면 좋을텐데 좀 아쉽다 ㅋㅋ 여튼 결론은 알고리즘의 연구가 하드웨어연구만큼 중요하다는 것으로 논문은 끝.

깔끔한 문제는 깔끔한 복잡도를 가질까?

Hhan댓글 남기기

이론적 컴퓨터과학의 많은 문제들을 보면, 최근 수십년간 이 학문이 엄청나게 발전했음에도 불구하고 대부분의 문제에서 최적인 알고리즘은 아주 오래전 (수십년 전, 길게는 거의 60년 정도까지!) 발견된 쉬운 알고리즘인 경우가 많다. 좀 발전했다 쳐봤자, 거기에서 조금 나아지는 정도? 구체적인 예들로는 다음과 같은 것들이 있다. O*(X)는 polylogX이나 다른 파라미터들에 대한 비슷한 팩터를 무시한 복잡도. 덧셈, 곱셈등의 복잡도는 대부분의 경우 O(1)로 생각한다.

  • n개의 점으로 이루어진 그래프에서 모든 쌍들 사이의 최단거리(All pair shortest path)를 모두 구하는 알고리즘은 (가장 일반적인 경우, 즉 대부분의 edge가 있는 경우) 1960년대 Floyd-Warshall 알고리즘의 복잡도인 점의 개수 n에 대해 O(n3)에서 수년 전 Ryan Williams가 발견한 알고리즘이 살짝 나아진 O(n3/exp(\sqrt {\log n}))정도를 달성하는데에 그친다.
  • 길이가 n인 두 수열에서 같은 부분수열을 찾는 문제(Longest common subsequence, LCS)나 한 주어진 수열에서 특정한 규칙을 따라 다른 주어진 수열로 변화시키는데 최소 몇번의 변환을 해야하는지에 대한 문제(Edit distance)역시 간단한 동적계획법 알고리즘으로 O(n2)의 알고리즘에서 거의 개선되지 않았다. 비슷하게 1980년의 O(n2/log2n)정도가 지금까지 찾은 최고의 알고리즘.
  • n개의 수의 집합에서 a+b+c=0를 만족하는 쌍 (a,b,c)를 찾는 문제인 3-SUM문제는 아주 간단한 알고리즘인 정렬 후 체크방식인 O(n2)알고리즘보다 나은 방식은 Baran등이 제안한 알고리즘으로 기껏해야 O((nloglogn/logn)2)수준의 굉장히 미묘한 발전이 끝이다.
  • 지난 글에서 말했듯이 외판원 문제(Traveling salesman problem)역시 1960년대 발견된 헬드-카프 알고리즘의 복잡도인 O*(2n)에서 거의 발전하지 않았다.
  • 또, NP-hard문제의 대명사인 SAT문제를 일반적인 경우에 푸는 최고의 알고리즘도 역시 O*(2n)수준에 그친다. 물론 SAT문제의 형태를 제한한 3-SAT같은 경우에는 O*((4/3)n)정도의 알고리즘도 있다.

특히 마지막 두 문제는 NP-hard로 잘 알려진 문제들. 이 문제들을 가장 잘 푸는 방식은 이게 최선일까?

많은 컴퓨터과학자들은 사람들이 좋은 알고리즘을 개발하는 것을 문제의 어려움을 증명하는 것보다 훨씬 잘한다고 생각한다. 즉, 우리가 아는 최선의 알고리즘이 진짜 최선에서 그렇게 벗어나지 않았을 것이라고 믿는다!

이런 생각은 다음과 같은 가설로 구체화된다.

  • Exponential time hypothesis (ETH)는 n개의 변수에 대한 3-SAT 문제가 어떤 상수 c>1에 대해 O*(cn)의 복잡도를 갖는 알고리즘이 최적이라는 가설이다. 좀 더 강하게, k-SAT의 최적의 복잡도 O*(ckn)를 만족하는 ck를 생각하면 \lim_{k\rightarrow \infty} c_k = 2가 성립할것이라고 말하는 Strong exponential time hypothesis (SETH)도 있다. 최근에는 이것의 양자버젼인 QSETH도 제안되었다. (사실 다들 생각은 하고 있었고, 이걸로 의미있는 결과를 처음으로 얻어냈다.)
  • 비슷하게 3-SUM hypothesis는 임의의 ε>0에 대해 3-SUM을 푸는 O*(n2-ε) 알고리즘이 없을것이라는 가설이다.

많은 컴퓨터과학자와 나는 SETH가 참이라고 믿는다. 하지만 이를 증명하는것은… 글쎄다. 아마 이러한 관점에서 많은 컴퓨터과학자들이 두 n×n 행렬의 곱이 O*(n2)에 될것이라고 믿는듯 하다. 나는 이것은 아직 그렇게까지 믿지 않는다 -_-ㅋ 이 스택익스체인지에 관련 논의가 있다. 딱히 강력한 근거는 없는듯. 여튼, 이러한 관점에서 컴퓨터과학자들은

깔끔하게 정의된 문제는 깔끔한 복잡도를 갖는다

라고 믿는다. 물론 나도 믿는다 ㅋ

하지만: 지난 TSP에 관한 글에서 언급했듯 네더로프가 증명한 바에 따르면 행렬곱이 O*(n2)복잡도를 달성한다면 이분그래프에 대한 외판원 문제가 O*(1.9999n)에 풀린다고 한다!

그렇다면 가능성은 다음과 같다.

  • 이분그래프에 대한 TSP는 “깔끔한 문제”가 아니다.
  • 행렬곱은 “깔끔한 문제”가 아니다.
  • 이분그래프에 대한 TSP는 사실 다른 깔끔한 복잡도(e.g. O*((4/3)n))를 갖는다.
  • 행렬곱이 다른 깔끔한 복잡도를 갖는다.

나는 개인적으로 첫번째 가능성을 지지한다 ㅋㅋㅋ

조금 다른 관점에서, 답을 approximate하게 구하는 것은 어떨까? 예를 들어 TSP의 최적값에 가까운 해를 구하는 알고리즘이나, 선형시간에 LCS에 가까운 해를 찾는것은? 그 가까운의 범위도 깔끔한 값을 가질까?

오랫동안 사람들은 그렇게 믿어온듯 하다. 예를들어 metric TSP, 즉 외판원 문제에서 변들의 길이가 삼각부등식을 만족하는 경우에는 1.5-approximation 다항식 시간 알고리즘이 Christofides–Serdyukov에 의해 알려져 있었고, 이게 최적으로 믿고 있었다. 다음 블로그 글에 한글로도 잘 정리되어 있다.

그리고 LCS는 \sqrt{n}-approximation 선형 알고리즘이 최적이고, 심지어 n^t-approximation 근사는 O*(n2-2t)에 되었다고 한다.

하지만: 최근 arixv에 올라온 논문에 따르면 metric TSP문제가 다항식시간에 1.49…9-approximation이 가능하다고 한다. 여기서 9는 36개 이하로 있다고 한다 -_- 저자들은 이 결과가 어쩌면 4/3-approximation일수도 있다고 생각하는듯 하다.

그리고, SODA2019에 발표된 결과에 따르면 LCS에 대한 O(n0.497956)-approximation을 선형시간에 할 수 있다고 한다.

이런, 그렇다면 근사할 수 있는 정도는 깔끔하지 않은것일까? 이건 전혀 모르겠다 -_- 나는 참이라고 믿는데, 최근의 결과들은 그렇지 않다고 주장한다. metric TSP정도는 꽤나 깔끔한 문제처럼 느껴지는데……