-
A Tree Representation for Failure Function of a String
A Tree Representation for Failure Function of a String Introduction KMP(Knuth-Morris-Pratt) 알고리즘은 주어진 문자열에서 패턴 문자열을 검색하는 전통적인 선형 시간 알고리즘이다. 알고리즘 대회 분야에서도 KMP 알고리즘을 응용하여 해결할 수 있는 문제는 꾸준히 출제되고 있으며, 한국 리저널만 보더라도 2017 Preliminary J번, 2021 Regional K번 등에서 등장한 바가 있다. KMP 알고리즘을 응용하여 해결하는 문제들은 많은 경우 KMP 알고리즘의 중간 단계에서 등장하는 실패 함수(Failure function)에 대한 깊은 이해를 바탕으로 한다. 따라서, 실패 함수가 해당 문자열의 구조에 대해 어떤...
-
SAGE: Saliency-Guided Mixup with Optimal Rearrangements
SAGE: Saliency-Guided Mixup with Optimal Rearrangements Mixed Sample Data Augmentation, MSDA는 vision task에서 사용하는 데이터를 증강하기 위해서 사용되는 기법입니다. 이를 위한 수많은 접근 방법이 나왔으며, Mixup을 필두로 해당 기법이 성능 개선에 큰 효과가 있다는 것이 알려지고, 최근에 왜 이러한 MSDA 방법론들이 실제 성능 향상에 영향을 주는지를 loss function perspective로 설명하는 A Unified Analysis of Mixed Sample Data Augmentation: A Loss Function Perspective이란 논문이 나오면서 더욱 다양한 관점과 방법론으로 연구되고 있습니다. 물론 아직 MSDA 방식이 정말로...
-
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에 대해 더 궁금하다면 논문 원문을 살펴보는 것을 강력하게...