-
Sequence model: from RNN to Attention
Introduction Sequence model은 연속적인 데이터를 입력으로 받아서 연속적인 데이터를 출력하는 모델을 의미합니다. 다시 말해, 시계열 데이터를 다루는 모델이라고 할 수 있습니다. Sequence model이 사용되는 대표적인 task로는 번역, 챗봇, 동영상 생성 등등이 있습니다. 이번 글에서는 가장 기초적인 Sequence model인 RNN부터 요즘 모든 딥러닝 분야에서 필수적으로 사용되는 개념인 Attention까지 발전 흐름을 따라 알아보고자 합니다. RNN overview RNN (Recurrent Neural Network)은 서로 독립적인 데이터가 아닌 연속적인 데이터를 다루기 위한 신경망입니다. 연속적인 데이터를 시계열 데이터라고도 하는데, 주가, 음성, 대화,...
-
Denoising Diffusion Probabilistic Models 수학적 분석
이번 글에서는 요즘 CV에서 가장 핫한 토픽인 diffusion model 중에서 가장 기본이 되는 DDPM (https://arxiv.org/pdf/2006.11239.pdf)에 대해서 자세히 알아보려고 합니다. ※ inline으로 표현이 안되는 수식이 많아서 쓸데없이 글이 늘어지는 점 양해 부탁드립니다. Overview DDPM은 간단하게 말해서 data인 $x_0$에 gaussian noise를 순차적으로 추가하는 forward process를 거쳐 gaussian noise인 $x_T$를 만들어내고, 다시 random gaussian noise $x_T$로부터 gaussian noise를 순차적으로 제거하는 reverse process를 거쳐 생성하고자 하는 이미지 $x_0$를 생성해내는 모델입니다. 더 자세한 내용은 DDPM을 소개한 다른 글들이 많으니 그를...
-
Inapproximability in computational hardness
Inapproximability in computational hardness 근사 알고리즘(Approximation algorithm)은, 문제에 대한 최적해를 제공하지는 못하나, 최적해에 근접한 해(근사해)를 빠른 시간에 찾는 알고리즘이다. NP-Complete인 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없는데, 이러한 문제를 회피하는 여러 방법 중 가장 많이 연구되는 방법 중 하나가 근사 알고리즘이다. 근사 알고리즘의 목표는, 최적해에 근접함이 보장된 해를 다항 시간에 찾는 것이며, 가능하다면 그 보장의 정도를 최대한으로 끌어오는 것이다. 모든 문제가 근사 알고리즘으로 쉽게 해결되었으면 정말 좋았겠지만 당연히 세상 일이...
-
Nearly optimal communication complexity of Bipartite Maximum Matching
Introduction Bipartite Maximum Matching (BMM)은 Bipartite graph $(V = X \sqcup Y, E \subseteq X \times Y)$에 대해 크기 $F$ 이상인 Matching이 존재하는지를 묻는 decision problem, 혹은 Maximum Matching의 크기를 계산하는 문제를 이야기합니다. 굉장히 오래 전부터 연구되어 온 문제이고, 정점이 $n$개, 간선이 $m$개인 BMM은 $m^{1 + o(1)}$ 시간 안에 해결할 수 있다는 것이 알려졌습니다. 원본 문제의 시간 복잡도가 subpolynomial 수준에서 사실상 optimum을 달성했기 때문에, 비전형적인 세팅에서 BMM을 해결하는 기법들이 등장하기 시작했습니다. 그 예시가 multi-party communication으로,...
-
SAT problem의 변형과 Schaefer’s Dichotomy Theorem
Boolean Formula, SAT $(x \lor \neg y) \land (\neg x \lor z)$와 같은 식을 Boolean formula라 한다. Boolean formula의 변수(variable)는 True/False (또는 1/0이라고도 한다)의 두가지 값만을 가질 수 있다. 위 boolean formula의 variable은 $x, y, z$이다. 각 연산자에 대해 알아보면 $\lor$ 와 $\land$는 각각 logical OR(disjunction)/ logical AND (conjunction)를 나타내고, $\neg$(negation)는 NOT을 나타내는 연산자로 피연산자가 True였다면 False로, False였다면 True로 바꿔주는 역할을 한다. 식에서 각각의 항 $x, \neg y, \neg x, z$는 literal이라 한다. $x, y$와...