-
Dulmage-Mendelsohn Decomposition (Part 1)
개요 이 글에서는 Dulmage-Mendelsohn Decomposition의 개념과 성질을 소개하고 이를 구하는 방법에 대해서 다룹니다. Dulmage-Mendelsohn Decomposition의 코드와 PS에서의 활용은 다음으로 이어지는 글에서 다루겠습니다. 사전 지식으로 이분 매칭과 SCC를 알고 있다고 가정하고 진행하겠습니다. Dulmage-Mendelsohn Decomposition(DM 분해)는 이분 그래프의 모든 최대 매칭의 구조를 알아내기 위해서 정점 집합을 여러 개의 부분집합들로 unique하게 분할하는 방법입니다. 구체적으로 예를 들면, DM 분해를 사용해서 아래와 같은 질문들에 대해 빠르게 답변할 수 있습니다. 주어진 이분 그래프의 각 정점 $u$에 대해, 모든 최대 매칭에서 $u$가...
-
SmoothMix: a Simple Yet Effective Data Augmentation to Train Robust Classifiers (CVPRW 2020)
SmoothMix: a Simple Yet Effective Data Augmentation to Train Robust Classifiers SmoothMix는 제가 앞서 소개했던 RandomMix, SAGE 등에 비하면 꽤나 오래전에 나온 논문입니다. 그렇기 때문에 해당 논문에서 baseline들로 비교하고 있는 기법들도 꽤나 기본적인 것들만을 사용하여 비교하고 있으며 엄청 특출난 성능을 보인다고 보기는 어렵습니다. 그러나 해당 mixup 방법 및 발견한 model의 이미지에서의 visualization attention, 그리고 data augmentation이 어떻게 Robustness에 영향을 줄 수 있는지 에 대한 기초적인 접근 방향의 아이디어를 찾을 수 있습니다. 최근에 computer vision과 data...
-
variational quantum algorithm
서론 Keywords: VQC(Variational Quantum Circuit), VQA(Variational Quantum Algorithm), VQE(Variational Quantum Eigensolver), Observable, Hamiltonian 기본적인 양자상태의 표현과 gate가 어떻게 작동하는지는 이해하고 있다는 가정하에 글을 작성하였다. VQC, VQA, VQE 모두 양자 컴퓨팅에서 중요한 개념들이지만 한국어로 제대로 소개된 글이 없기에 이 글을 통해 소개하고자 한다 Quantum Circuit 그림 1. 양자회로의 모습 위 그림 1은 일반적인 양자회로의 모습을 나타내고 있다. 고전 회로에서 1-input gate인 Inverter과 2-input gate인 AND, OR, XOR게이트, 3-input gate인 3-input OR 등등이 있듯이 양자 회로에도 다양한...
-
Faster Matroid Intersection - Part 1
0. Introduction 필자는 Matroid를 소개하는 글 및 Matroid Intersection을 소개하는 글을 2019년에 작성한 바 있다. Matroid Intersection은 해당 글에도 나와 있듯 다양한 문제들을 해결할 수 있는 툴이 되며, 이에 따라 많은 연구가 진행되었다. 특히, 2019년을 기점으로 하여 Matroid Intersection을 어떻게 하면 빠르게 할 수 있을지에 대해 여러 논문의 결과가 발표되기 시작했다. 대표적인 예시로 다음과 같은 4가지 논문이 존재하고, 앞으로는 다음 논문들의 결과에 대해 다룰 것이다. A note on Cunningham’s algorithm for matroid intersection(2019) Faster Matroid...
-
Choice Coordination Problem
개요 문제 상황 $n$개의 프로세서가 존재한다. 각 프로세서는 $m$개의 선택지 중 하나를 선택해야 한다. 그런데, 프로세서들이 완전히 비동기적으로 작동한다. 프로세서가 공유하는 일관적인 시계 (global clock)이 존재하지도 않을 뿐더러, 프로세서의 응답 속도에 대한 가정을 할 수도 없다. 이러한 상황에서 모든 프로세서가 동일한 선택으로 합의하도록 하는 알고리즘이 필요하다. 인격을 부여해 이러한 비유 상황을 만들어낼 수 있다: $n$명의 관광객이 존재한다. 그들이 머무는 여행지는 $m$개의 방으로 이루어져 있다. 이 때 관광객 모두가 방 하나에 모일 수 있도록 행동 규약을...