-
계산 복잡도 위계와 불리언 식
계산 복잡도 위계와 불리언 식 계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의...
-
Prime Number
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학교 고급 알고리즘 시간에 Miller–Rabin Algorithm 에 대해서 공부하게 되었다. 매우 흥미로운 내용이 많았으며, 다른 사람들과 공유하면 좋겠다고 생각하여 소인수 분해 알고리즘 등의 다양한 알고리즘을 알게 된것을 포함하여 공유하고 싶어졌다. 이번 포스트에서는 그 알고리즘들의 구현과 실제 문제에 대해 어떻게 사용되는지 소개하고자 한다. 기본 지식 일단 최소한 Modulo Operation, 즉, 나머지 연산에 대해서 조금 설명할 필요가 있다. Mod 연산은...
-
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
ACER: Sample Efficient Actor-Critic With Experience Replay
ACER: Sample Efficient Actor-Critic With Experience Replay 제목에서도 볼 수 있듯이, 딥마인드에서 나온 Sample Efficient Actor-Critic With Experience Replay 는 Actor-Critic method에 Experience Replay를 접목시켜 데이터 효율성을 높인 새로운 강화학습 알고리즘을 제안하는 논문입니다. A3C의 off-policy 버전이라고 생각하셔도 됩니다. 논문 내용을 요약하면 다음과 같습니다. Experience Replay를 도입해서 Sample efficiency를 향상시켰다. Experience Replay를 사용하기 위해 그래디언트 계산에 off-policy correction을 추가했다. Importance sampling을 사용할 것인데 그냥 사용하면 bounded 되지 않은 importance weight 값이 여러번 곱해져 variance가 너무 커질...
-
data science 기초
Data Science 의 기초 contents what is data science? ready to start analysis feature check outliers PCA linear regression conclusion what is data science? 데이터 과학이란? 이번 주제에서는 데이터 과학이라는 분야를 다뤄보고자 한다. 딥러닝이 현재 큰 인기와 관심이 주목된 가운데, 데이터과학의 중요도 또한 크게 중요해지고 있다. 데이터들이 중요한 이유는 무엇일까? AI(인공지능)는 learning 을 통해서 자신의 내부 computation을 견고하게 만들고, 그 learning은 다름이 아닌 data들의 집합을 통해서 이루어진다. 여러가지 예를 들 수 있겠지만 image classification 이라는...