-
도형의 합집합과 넓이
도형의 불리언 연산이란, 여러 도형의 영역에 대한 집합 연산을 말합니다. 두 원의 교집합의 넓이를 구하는 방법은 잘 알려져 있습니다. 부채꼴 2개의 넓이를 합친 다음, 이등변삼각형 2개의 넓이를 빼는 방식으로 구할 수 있습니다. 같은 방법으로 두 원의 합집합의 넓이도 구할 수 있습니다. 하지만 원이 3개만 되어도 이런 “포함 배제” 접근을 하기 어렵습니다. 이 글에서는 도형의 합집합 및 그 넓이를 구하는 일반적인 방법을 소개합니다. 테두리 따기 아래 그림에서 테두리가 갖고 있는 중요한 성질을 찾아봅시다. 테두리는 도형의 둘레로...
-
Kirchhoff's Theorem (Matrix-Tree Theorem)
이번 글에서는 그래프의 스패닝 트리의 개수를 세는 두 가지 정리, Cayley’s formula와 Kirchhoff’s theorem에 대해 소개합니다. Cayley’s Formula 일반 그래프의 스패닝 트리의 개수를 세어보기에 앞서, 특수한 경우부터 먼저 살펴봅시다. Theorem 1 (Cayley’s Formula). $n$개의 정점으로 이루어진 완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다. 이 정리를 증명하는 방법으로는 여러 가지가 알려져 있으며, 대표적으로 Prüfer sequence와의 일대일 대응 관계를 찾는 증명이 있습니다. 개인적으로 가장 마음에 드는 증명은 다음과 같은 더블 카운팅을 이용한 증명입니다. 책 “하늘책의 증명” (Proofs from...
-
Low degree optimal polynomial의 계산기하적 접근
Optimal Polynomial 일반적으로 함수 $f(x)$와 차수 $d$가 주어졌을 때, $\lvert P(x) - f(x) \rvert$의 최댓값 를 최소화하는 $d$차 다항함수를 $f$에 대한 degree $d$의 optimal polynomial 이라 합니다. 그러나 이러한 $P$를 구해야 하는 상황에서는 보통 함수 $f$를 모르는 상태에서, $f$가 $d$차 이하의 다항식일 것이라고 가정한 후 $P$를 추측해야 하는 경우가 잦습니다. 몇 개의 $x_i$에 대해 $f$의 실험값 $y_i = f(x_i) + \epsilon_i$ 가 주어져있을 때 오차 $\max (\lvert P(x_i) - y_i \rvert)$를 최소화하는 $P$를 어떻게 구할...
-
간단한 딥러닝 기반 장기 시계열 예측 모델 리뷰 (FiLM, NLinear)
소개 시계열 예측은 과거 시퀀스로부터 미래 시퀀스를 예측 하는 테스크로서 교통, 에너지 사용량 분석, 금융 등 다양한 분야 및 비즈니스 모델에서 활용도가 높기 때문에 큰 주목을 받아왔습니다. 시계열 예측을 정확하게 하기 위해서는 시계열 데이터에 있는 복잡한 주기성이나 경향을 포착할 수 있어야 합니다. ARIMA나 Kalman filter 같이 고전 타임시리즈 예측에 쓰이는 방법론은 주로 시계열 모델링에 대해 선형성 같은 강한 가정을 하고 있고 적절한 파라미터를 선택하는데 어려움이 있습니다. 이에 따라 데이터 내의 복잡한 모델링 능력을 배우기 위해...
-
Foundation Model and Transfer Learning
최근 딥러닝 관련 challenge나 딥러닝을 이용한 task를 수행할 때 pretrained model을 사용하지 않으면 높은 성능을 내기 어려운 상황입니다. 그 중에서도 scale이 커서 일반화된 성능을 내는 모델들을 foundation model이라고 합니다. 이번 글에서는 이러한 foundation model에 대해 자세히 알아보겠습니다. 최신 AI 연구 트렌드 최근 AI 연구에서의 트렌드는 모델을 포함하여 dataset, computing resource 등 뭐든 크게 만드는 것입니다. 모델이 크면 서비스가 요구하는 latency를 만족하기 어렵고 상시 많은 resource를 사용할 수 없습니다. 따라서 큰 모델이 학습한 지식을 작은 모델에...