-
Treewidth Parametrized Dynamic Programming for Local Graph Problems
Introduction Vertex Cover, Independent Set, Dominating Set 등은 복잡도 이론에 관심이 있다면 익히 들어보았을 법한 문제들입니다. 각 문제의 정의는 다음과 같습니다. 무방향 단순그래프 $G = (V, E)$에 대해, Vertex Cover: 모든 $e = (u, v) \in E$에 대해 $u \in S 또는 $v \in S$를 만족하는 $S \subseteq V$를 찾아라. Independent Set: 모든 $u, v \in S$에 대해 $(u, v) \notin E$인 $S \subseteq V$를 찾아라. Dominating Set: 모든 $v \in V$에 대해 $v \in...
-
SOAP: Schedule Ordered by Age-based Priority
Introduction Scheduling Policies 우리는 흔히 일상 생활에서 효율적인 일처리를 위해 todo list를 만들거나 시간 단위로 스케줄을 나누어 계획을 세우곤 합니다. 또한, 컴퓨터의 CPU는 여러 개의 처리해야 할 task이 있을 때 어떤 일부터 처리해야 할지 정하고 task를 수행합니다. 이 때 어떤 일부터 처리할지를 잘못 결정한다면 특정 일은 처리하는 시간이 너무 늦어지는 현상이 발생합니다. 이에 대한 결과로 과제를 늦게 제출하거나, 컴퓨터 화면이 멈춰버리는 등의 불상사가 발생하곤 합니다. 처리하는 주체를 server, 처리되어야 하는 일을 job, job들의 대기열을 queue이라고...
-
Forward Forward algorithm
서론 인공지능의 대부 Hinton교수가 새로운 신경망 학습 방법을 고안했다. 2022년 12월 27일에 아카이브에 올라온 논문이라 글 작성 시점에서 아직 따끈따끈한 논문이다. 인공지능의 대부가 쓴 논문인 만큼 벌써 조금씩 인용이 되고 있다. 과연 Hinton교수가 이번에 발명한 학습방법은 어떤 것인지 살펴보도록 하자. 본 글은 Hinton교수님의 Forward Forward algorithm 논문[1] 중에서도 Forward Forward의 작동 원리만을 이해하는 것에 초점을 두고 정리하였다. 논문 전체 내용을 정리하는 목적이 아니므로 빠진 내용들이 있다. FF에 대해 더 궁금하다면 논문 원문을 살펴보는 것을 강력하게...
-
Diversified Late Acceptance Search
서론 지역 검색(Local Search) 알고리즘은, 여러 종류의 최적화 문제를 광범위하게 해결하는 데에 사용하고, 다양한 알고리즘의 기준선(baseline)이 될 수 있습니다. 우리는 이 알고리즘 중 기초적인 언덕 오르기(Hill Climbing) 알고리즘과, 그 변형인 늦게 수용하는 언덕오르기(Late Acceptance Hill Climbing, LAHC) 알고리즘 중 하나인 다양성을 갖춘 늦게 수용하는 탐색(Diversified Late Acceptance Search, DLAS)에 대해 알아봅니다. 언덕 오르기 알고리즘과 변형 언덕 오르기 알고리즘은 최적화 문제를 해결하기 위한 간단하고 직관적인 알고리즘 중 하나입니다. 이 알고리즘은 현재 상태에서 지역 최적해를 찾는 데...
-
A Bayesian Perspective on Federated Learning (1)
Introduction Federated Learning은 최근에 머신러닝과 인공지능 연구에서 매우 중요한 분야로 떠오르고 있습니다. 이 기술은 분산된 디바이스들의 데이터를 이용하여 중앙 집중식으로 데이터를 수집하지 않고 모델을 학습시키는 것으로, 개인정보 보호와 같은 문제를 해결하는 데 도움이 됩니다. 따라서, Federated Learning은 데이터 프라이버시와 보안 문제가 중요한 분야에서 매우 유용합니다. 이 기술은 인공지능 모델을 개발하는 데 있어서 중요한 문제 중 하나인 데이터 분산 문제를 해결할 수 있습니다. 이러한 이유로, Federated Learning은 최근 많은 관심을 받고 있으며, 새로운 연구와 개발이 계속해서...