-
WaveBound: Dynamic Error Bounds for Stable Time Series Forecasting (NeurIPS'22) 눈문 소개
올해 11월 말에 열릴 머신러닝 학회인 NeurIPS 2022에 제가 제출했던 논문 “WaveBound: Dynamic Error Bounds for Stable Time Series Forecasting”이 어셉되어서 리뷰하고자 합니다. 소개 시간의 흐름에 따라 순차적으로 기록된 데이터를 시계열 데이터라고 부릅니다. 시계열 예측은 과거 시계열 데이터로부터 미래를 예측하는 테스크로 교통 속도 예측, 에너지 사용량 예측 등 다양한 분야에서 주목을 받아왔습니다. 최근에는 Informer, Autoformer와 같은 딥러닝 기반 시계열 예측 모델이 주목받았지만 본 연구에서 이러한 모델은 여전히 과적합에 취약함을 보여주었습니다. 기존 딥러닝 모델의 과적합...
-
Unique Games Conjecture
본인은 최근 들어 Theoretical Computer Science 분야 중에서도 Computational Hardness에 관련한 결과들을 다루는 스터디에 참여하고 있고, Unique Games Conjecture와 관련하여 발표할 일이 있었다. 나름 의미가 있는 주제임에도 불구하고, 이와 관련한 국문 자료는 (본인이 검색해본 한에서는) 전혀 찾아볼 수 없었어서 이 글을 작성하게 되었다. 이 글은 Unique Games Conjecture가 무엇이고, 이를 통해 어떤 결과들을 얻을 수 있는지에 대해 전달하는 것을 목표로 한다. Unique Games Conjecture에서 어떤 형태로 reduction을 구성할 수 있는지 그 느낌 또한 전달하는 것...
-
The number of topological sorts in DAG, AND polytope centroid
Introduction 문제를 풀다 보면 “조건을 만족하는 해 $x$를 찾아라” 라는 문제는 쉽게 풀 수 있지만, “조건을 만족하는 해 $x$의 개수를 찾아라” 라는 문제가 유독 어려운 경우가 많습니다. 대표적으로 2-SAT은 다항 시간 안에 해를 찾을 수 있지만, 2-SAT의 조건을 모두 만족하는 해의 개수를 찾는 것은 매우 어렵다는 것이 알려져 있습니다. 비슷하게 이분그래프의 완전 매칭은 다항 시간 안에 찾을 수 있지만, 완전 매칭의 개수를 구하는 것은 permanent라는 계산하기 어려운 식과 동치가 됩니다. 오늘 다룰 주제는 Directed Acyclic...
-
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$ 인 이상 최적해를 다항 시간에 구할 수 없는데, 이러한 문제를 회피하는 여러 방법 중 가장 많이 연구되는 방법 중 하나가 근사 알고리즘이다. 근사 알고리즘의 목표는, 최적해에 근접함이 보장된 해를 다항 시간에 찾는 것이며, 가능하다면 그 보장의 정도를 최대한으로 끌어오는 것이다. 모든 문제가 근사 알고리즘으로 쉽게 해결되었으면 정말 좋았겠지만 당연히 세상 일이...