본문 바로가기

전체 글

Mergesort & Counting Inversions * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Mergesort array를 반으로 나누어 2개의 array를 만든다. 각 array에 대해 recursive하게 sort를 진행한다. Sort된 두개의 array를 이용하여 하나의 큰 sorted array로 merge한다. 두개의 array가 sort되었다고 가정하므로, 각 array에 대해 왼쪽에서 오른쪽으로 진행하면서 comparison을 진행하면된다. 그 결과, merge에 $O(n)$의 시간이 걸린다. Mergesort recurrence n을 2의 지수승이라 하면 다음과 같다. Time complexity : $O(nlogn)$ Proof by recursion tree Recursion을 tree로 표현할 수 있.. Basic Learning/Algorithm Design 2020. 10. 20.
Huffman Coding * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Prefix Code Symbol을 인코딩하는데 있어, 고정된 길이로 인코딩할 수 있지만, symbol 빈도수가 클수록 길이를 작게한다면 더 효율적일 것이다. Huffman coding은 symbol frequency가 주어졌을 때, symbol에 code를 할당하는 알고리즘이다. Prefix code : 1, 0으로 이루어진 code에서, 하나의 code가 다른 하나의 prefix가 되지 않는 code이다. ABL (Average Bits per Letter) Prefix code는 아래 그림과 같이 tree의 leaves에 할당함으로써 표현할 수 있다. 중간 노드에 할당이 될 수 없는데, 할당되면 아래 노드의 prefix가 .. Basic Learning/Algorithm Design 2020. 10. 17.
QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding Alistarh, Dan, et al. "QSGD: Communication-efficient SGD via gradient quantization and encoding." Advances in Neural Information Processing Systems. 2017. Link Abstract SGD의 병렬 구현은 뛰어난 확장성 덕분에 상당한 관심을 받고 있다. SGD 병렬화의 bottleneck은 gradient update를 하는데 필요한 통신비용이다. 이를 해결하기 위해, 각 노드가 quantized gradient를 전달하는 손실 압축 휴리스틱이 제안되었다. 이는 통신비용을 줄이는데있어 효과적이지만 수렴성이 보장되지는 않는다. 이 논문에서 수렴을 보장하면서 성능이 우수한 압축 스키마인 QS.. Deep Learning/Distributed Deep Learning 2020. 10. 12.
Scaled Representations : Image Pyramid * 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다. Fourier Transform & Sampling Continous time FT Discrete time FT Sampling Nyquist theorem Band-limited signal을 완전 복원하기 위해 다음 조건이 필요하다. $f_B$를 signal의 maximum frequency, $f_S$를 sampling frequency라 할 때, $f_S \geq 2f_B$를 만족하면 완전 복원이 가능하다. 위의 조건이 만족되지 않으면 aliasing이 발생한다. Gaussian Pyramid Aliasing 방지 : Sampling전에 low-pass filter를 통해 high frequency를 줄인다. 미리 gaus.. Basic Learning/Computer Vision 2020. 10. 8.
More Features * 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다. Hough Transform 직선을 탐지하기위해, x-y space를 기울기-절편 space, 즉 m-b space로 변환하는 것. 그러면 xy 평면상의 한점은 mb평면상에서 vote하는 것이 된다. Image space에서의 선은 점으로 mapping, 점은 선으로 mapping된다. 하지만 수직선의 경우 m이 무한대가 되기 때문에 Hough space가 무한으로 커지게 된다. 이를 보완하기 위해 Hough space가 아닌 Parameter space로 transform한다. Parameter space 역시, 하나의 점은 Image space에서 직선을 의미한다. Generalized Hough Transform Hough t.. Basic Learning/Computer Vision 2020. 10. 8.
Edges * 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다. First-order Derivative Filters Edge를 detect하기위해 intensity의 gradient를 구한다. 이 때 gradient 방향은 edge와 수직이다. 하지만 미분 filter를 취함으로써, noise가 증가한다. 그렇기 때문에 Smoothing을 진행한 이후에 미분을 취하여 edge를 얻어낸다. Derivative of Gaussian (DOG) 미분 filtering을 하기전에 Gaussian smoothing을 진행한다. Convolution 순서는 바껴도 상관없기 때문에, Gaussian filter를 미분한 filter를 만들 수 있다. Canny Edge Detecctor 1. Noise .. Basic Learning/Computer Vision 2020. 10. 8.
Linear Filters * 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다. Linear Filtering 새로운 pixel값은 주변 pixel의 weighted sum으로 표현할 수 있다. 이를 Convolution operation이라 한다. Boundary Issue : boundary 주변에서는 주변 pixel이 정의되지 않음 -> Crop, zero padding, copy edge 등의 다양한 방법들이 있음 Reduce Noise Image noise models Additive noise : $I(i, j) = \hat{I}(i, j) + n(i, j)$ Multiplicative noise : $I(i, j) = \hat{i}(i, j) \cdot n(i, j)$ Impulsive noise .. Basic Learning/Computer Vision 2020. 10. 8.
Minimum Spanning Tree & Clustering * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Minimum Spanning Tree Spanning tree : 최소 개수의 edge를 사용하여 모든 node를 커버하는 tree (graph) Minimum spanning tree : 사용된 edge cost의 합이 최소가 되는 spanning tree * Cayley's Theorem : Complete graph에는 가능한 spanning tree가 $n^{n-2}$개 존재한다. Edge의 cost가 모두 다르다는 가정하에, Cut property : Subset S와 G - S를 잇는 edge가 여러개 있을 때 (cutset), cost가 제일 작은 edge를 e라 하자. 그러면 MST는 e를 포함한다. Cycle .. Basic Learning/Algorithm Design 2020. 10. 8.

티스토리툴바