데이터 스케치 이론 정리: 레비-힌친 표현으로 스트리밍 알고리즘을 기계적으로 설계하는 법

핵심 메시지

• 스케치 연구의 핵심 질문은 어떤 함수의 모멘트를 폴리로그 공간만으로 근사할 수 있는지, 그리고 하나의 스케치로 모든 함수를 감당할 수 있는지다.
• 기존 기법은 무작위 사영과 부분추출 두 가지뿐이었고, 계산 가능성 판정도 함수가 만족해야 할 성질을 나열하는 방식이었다.
• 제안된 '레비 타워'는 목표 함수를 특성지수로 갖는 레비 과정을 찾아 그 과정과 벡터의 내적을 유지하는 방식으로 스케치를 기계적으로 만든다.
• 이 틀은 AMS 스케치, 인딕의 안정 분포 스케치, 플라졸레-마르탱과 하이퍼로그로그까지 지난 40년의 결과를 그대로 재현한다.
• 기존 기법이 손대지 못하던 '거의 주기적인' 함수도 자연스럽게 처리되며, 남은 일반화는 선형계획법으로 근사를 찾는 방식으로 시도됐다.

쉽게 이해하기

스트리밍 알고리즘이 푸는 문제는 단순하게 적힌다. 아주 긴 벡터가 있고 값이 계속 더해지거나 빠지는데, 벡터 전체를 저장하지 않고도 마지막에 특정 통계량을 근사하고 싶다. 각 항목에 함수를 적용해 모두 더한 값을 f-모멘트라 부르며, f가 제곱이면 2차 모멘트, f가 0이 아닌지 여부면 서로 다른 원소의 개수가 된다. 페티 교수는 이 문제를 40년 동안 쌓인 개별 기법들의 집합이 아니라 하나의 이론으로 보려 한다.

강연은 먼저 고전들을 훑는다. AMS 스케치는 벡터와 무작위 부호 벡터의 내적 하나만 유지해도 2차 모멘트의 불편 추정량이 된다는 두 줄짜리 증명으로 요약된다. 인딕은 부호 대신 안정 분포 난수를 써서 0과 2 사이의 모든 p-모멘트로 일반화했다. 플라졸레-마르탱은 원소를 격자 위 한 점으로 해싱해 어느 칸이 채워졌는지만 보고 서로 다른 원소 수를 추정한다. 결국 쓰이는 도구는 무작위 사영과 부분추출 둘뿐이었다.

새 접근의 출발점은 레비 과정이다. 레비 과정은 증분이 시간에 무관하고 서로 독립인, 말하자면 기억을 갖지 않는 확률 과정이다. 브라운 운동이 대표적이고, 지수 시간마다 하나씩 늘어나는 계수 과정이나 모든 척도에서 점프가 나타나는 코시 과정도 여기 속한다. 각 레비 과정은 특성지수라는 함수와 짝을 이루는데, 그 함수들이 공교롭게도 우리가 스케치할 수 있다고 알고 있던 함수들과 겹친다.

여기서 레시피가 나온다. 스케치하고 싶은 함수를 특성지수로 갖는 레비 과정을 찾고, 벡터의 각 좌표마다 독립적인 복사본을 하나씩 두고, AMS가 무작위 부호와 내적을 잡듯 이 과정들과의 내적을 유지한다. 관측 시각은 목표 값의 크기에 반비례하게 잡아야 정보가 나오므로, 시각을 지수적으로 여러 개 두어 층층이 쌓은 것이 레비 타워다. 이 구성은 AMS를 극한으로 재현하고, 무한대로 '죽는' 레비 과정을 쓰면 뺄셈이 불가능한 증가 전용 모델의 플라졸레-마르탱과 하이퍼로그로그까지 설명한다.

가장 흥미로운 대목은 기존 기법의 사각지대다. 이진 표현의 최하위 1의 위치로 정의되는 함수처럼 값이 심하게 요동치며 이따금 0에 아주 가까워지는 '거의 주기적인' 함수는 어떤 표본추출 전략으로도 잡히지 않는다. 레비 타워는 이런 함수를 푸리에 전개해 1에서 코사인을 뺀 기저의 계수로 바꾸면 곧바로 다룬다. 계수에 음수가 섞여 레비 표현이 불가능한 함수는 양수부와 음수부로 갈라 각각 스케치한 뒤 빼는데, 이때 오차가 원래 값보다 훨씬 커지는 문제가 생겨 선형계획법으로 좋은 근사를 찾는 방법이 제시됐다.

주요 인사이트

• 이론의 가치는 새 결과보다 설명력에 있다. 서로 무관해 보이던 스케치들이 어떤 레비 과정을 어떤 시각에 관측하느냐의 차이로 정리되면서 '세상이 왜 이렇게 생겼는지'가 설명된다.
• 증가 전용 모델과 가감 모델의 근본적 차이는 무한대로 죽는 레비 과정이라는 장치로 흡수된다. 무한대는 빼서 되돌릴 수 없기 때문에 되돌릴 수 없는 연산을 자연스럽게 표현한다.
• 같은 하이퍼로그로그도 각 칸을 독립적인 과정으로 볼지, 한 열을 하나의 과정을 서로 다른 시각에 관측한 것으로 볼지에 따라 갈린다. 결합 방식이 알고리즘의 정체를 결정한다.
• 계산 가능성의 정의 자체가 입력이 정수인지 실수인지에 따라 달라진다는 지적이 나왔다. 같은 함수라도 값을 0 근처로 압축할 수 있으면 더 높은 모멘트를 복원할 수 있기 때문이다.
• 발표자가 남긴 추측은 명확하다. 함수가 계산 가능하다면 선형계획법 방식이 언제나 좋은 분해를 찾아낼 것이며, 이것이 참이면 계산 가능성 문제의 최종 답이 된다는 것이다.

자주 묻는 질문

관련 AI 소식