-
비지도 방식으로 GANs의 이미지 생성을 조작하는 방법
소개 GANs는 이미지 생성이나 스타일 변화 테스크에서 굉장한 성능을 보여주고 있습니다. 특히, StyleGAN, BigGAN과 같은 최신 모델은 이미 실제와 구분이 힘들정도로 자연스러운 이미지를 생성합니다. 유저가 아웃풋 이미지를 원하는 형태로 조절하는 연구 또한 많이 진행되었으나 대부분 추가적인 라벨을 사용해서 모델을 학습하는 것에 초점을 맞췄었습니다. GANs의 해석 가능성에 대한 연구가 활발해지면서 각 특징을 조작하는 변수가 잘 구분되도록 학습하는 테스크인 disentanglement learning이 주목받게 됩니다. InfoGAN, beta-VAE 등이 대표적인 모델로 비지도 방식으로 생성 모델을 학습하면서 출력 결과의 중요한 특징들을...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3) Chapter 4: Continued 4.2. Contraction 4.2.1 Properties of Contraction Lemma 4.2를 사용하여 우리는 Non-tree edge의 개수가 작은 Decremental MSF 알고리즘으로 문제를 환원하였다. 이제 이를 Edge의 개수가 작은 Decremental MSF 알고리즘으로 다시 환원한다. 다행이도, 이 부분은 Competitive Programming에서 익숙한 내용이라서 배경 지식이 있다면 빠르게 이해할 수 있다. Definition 4.11. (Connecting Paths). 트리 $T = (V, E)$ 와 터미널의 집합 $S \subseteq V$ 가 있을 때, $P_{S}(T)$ 는...
-
KMP 알고리즘과 Aho-Corasick 알고리즘
본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 이유는 둘 모두 평균 시간 복잡도뿐 아니라 최악의 경우 시간 복잡도가 극적으로 개선되었기 때문이다. 두 알고리즘 모두 실제로는 다이나믹 프로그래밍의 한 예시일 뿐임에도 실제로는 어려운 알고리즘으로 생각되고 있었다. (내가 그랬다..) 풀고 싶은 문제 우리가 두 알고리즘을 이용해 풀고 싶은 문제는 아래와 같다. 1) 아주 긴 문자열 $S$ 와 짧은 문자열 $T$ 가 주어진다. $S$ 의 길이는 $N$,...
-
Consistent Hashing
안녕하세요? 오늘은 웹서버 등에서 요청을 여러 곳으로 공평하게 분산시키는, load balancing 작업을 수행할 때 널리 사용되는 consistent hashing 알고리즘에 대해 알아보겠습니다. Consistent hashing은 1997년 Karger의 논문 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web에서 제안된 알고리즘입니다. 서론 Karger의 논문에서는, 다른 클라이언트에서 접근 가능한 많은 object를 가지고 있는 단일 서버의 상황을 가정하였습니다. 서버에 캐시를 두면 더 빠른 접근이 가능하다는 것은 자명합니다. Object들은 여러 개의 캐시에 분산되어야 하는데,...
-
Indistinguishability in Cryptography
1. Introduction 주어진 암호를 키에 대한 정보 없이 전수 조사보다 더 효율적으로 완전히 해독할 수 있다면 더할 나위 없이 강력한 공격입니다. 특히 현재 널리 쓰이고 있는 암호 시스템에 대해 이러한 공격을 찾았다면 정말 큰 업적을 세웠다고 할 수 있습니다. 그러나 수명, 많게는 수십명이 협력해 만들고 긴 시간을 걸쳐 검증을 받아온 암호 시스템에서 이러한 공격이 발견되기란 굉장히 어려운 일입니다. 이렇게 암호문을 완전히 해독하는건 매우 힘들지만 학계에서는 꼭 암호문을 완전 해독해내는 것이 아닌 더 느슨한 환경에서의 조그만...