devmoon

딥러닝의 레이어를 훨씬 깊게 쌓을 수 있게 영향을 준 이번 논문은 Computer Vision 분야의 대회였던 ILSVRC에서 2위를 차지한 VGGNet에 대한 논문이다. 레이어를 깊게 쌓을수록 파라미터의 수가 많아져 계산량이 늘어나고 시간이 오래 걸린다는 단점이 있었을 텐데, 이를 어떻게 극복했는지 신경 쓰면서 보면 좋은 논문이다. Introduction 2015년 당시 고해상도의 이미지를 입력받아, 사물이나 물체를 인식하여 분류하는 대회인 ILSVRC에서 Convolution연산을 사용하는 딥러닝 모델(ConvNet)을 사용하는 팀들이 우수한 성적들을 많이 보여주고 있었다. 특히 Computer Vision 분야에서는 ConvNet은 마치 흙속의 진주와도 같았고 그렇기에 많은 사람들이 이를 개선하기 ..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 1이상 4,000,000 이하의 수 $N$ 개를 입력받고 $K$개의 임의의 수 $k$를 입력 받았을 때, $N$ 개의 수에서 $k$ 보다 큰 수들 중 가장 작은 수를 출력하면 되는 문제이다. 따라서 입력받는 대로 모든 수를 정렬하고, upper_bound 로 만족하는 결과를 얻을 수 있는 set 의 자료 구조의 사용을 바로 떠올렸다. set s..

AlexNet이라고 흔히 불리는 이번 논문은 2012년 이미지 분류 대회에서 우승을 차지한 모델이다. CNN을 사용한 딥러닝 구조에서 어떻게 많은 120만 장의 사진들을 그 당시 기술로 처리를 하였고, 파라미터 수가 많은데 과적합 문제를 어떻게 해결했는지 알아볼 수 있는 좋은 논문이다. INTRODUCTION 2012년, 객체 인식(Object Recognition)을 하기 위해서는 머신러닝을 사용한 방법들이 거의 필수적으로 다가왔고 그 성능을 끌어올리기 위해서는 많은 양의 데이터셋이나 더 강력한 모델 그리고 오버 피팅을 방지하기 위한 기술들이 필요했다. 따라서 약 100만 개의 데이터를 학습시키기 위한 모델이 필요했었고, 수천 가지의 카테고리로 분류하기 위해서는 가지고 있지 않은 데이터에 대해서도 좋은..

딥러닝을 공부하고 모델링을 진행하다 보면 자주 등장하는 개념이 Batch Normalization이다. 번역해서 배치 정규화라고도 불리는데, 대략적인 개념을 알지만 그 세세한 작동원리와 그 구조를 자세하게 알고 싶어서 리뷰할 논문으로 선택하였다. 배치 정규화를 사용했을 때, 14배 빠른 속도로 동일한 성능을 보일 수 있다니 대단한 개념이라고 생각되었다. 배치 정규화를 가장 처음에 요약하고 시작하자면, 딥러닝 구조의 각 레이어에서 입력들의 분포가 항상 유사하거나 일정하도록 만들어주는 것이다. 입력 분포가 일정하지 않으면 무엇이 문제이고 어떤 단점들이 있는지 논문에서 잘 설명해주어서 그 중요성을 많이 깨닫게 되었다. Introduction 처음에 논문은 SGD의 장점들에 대해서 설명한다. SGD는 딥러닝 모..

경사하강법과 관련된 여러 기법들을 정리해서 소개하는 이번 논문은 각 경사하강법의 최적화 방법 또는 이론들이 어떻게 등장하였고, 그 원리가 무엇인지 간단하게 이해하기 좋다고 생각되었다. 실제로 읽으면서 각 최적화 알고리즘들이 어떻게 이전의 단점들을 개선시켜 나갔는지 그 흐름을 파악하기가 좋았었다. 이 논문에서 소개하는 것들은 정말 기본적인 Gradient Descent(GD)를 시작으로 SGD, Mini-batch GD 과 최적화 기법인 momentum, NAG, Adagrad, Adadelta, RMSprop, Adam 등이 있다. 이외에도 2가지 최적화 방법 AdaMax와 Nadam이 있지만 자주 등장하는 개념은 아닌 것 같아 세세하게 읽어보지는 않았다. 저자는 처음에 경사하강법이 무엇인지 짧지만 매우..

1. 문제 출처 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2. 문제 접근 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exac..

1. 문제 출처 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 문제 접근 기존에 알고 있었던 세그먼트 트리이지만, 업데이트해야 하는 것이 하나의 값이 아니라 구간에 대해서 업데이트를 진행해야 했다. 해당 구간에 대해서 일일이 업데이를 진행하는 것보다 lazy propataion방법을 사용하면 더 효율적으로 풀이가 가능했다. lazy propagation에 대한 정보가 없었..

※ 이 게시물은 에 나오는 KMP부분을 읽고 개인이 정리하는 글입니다. 더 자세한 설명은 위의 책에 나와있습니다. KMP알고리즘은 아주 긴 문자열 $S_{1}$과 $S_{2}$가 주어졌을 때, $S_{1}$속에 $S_{2}$가 몇 번이나 등장하는지 빠르게 알아낼 수 있는 알고리즘이다. 두 문자열을 비교할 때, 가장 쉬운 방법은 $S_{1}$의 모든 index를 순회하면서, $S_{2}$의 길이만큼 서로 문자 같은지 비교를 진행하는 것이다. 하지만 이럴 경우 총 ($S_{1}.length-S_{2}.length + 1) \times S_{2}.length$만큼 비교를 진행해야 한다. 하지만, 구현이 단순하다는 장점이 존재한다. 이 장점 때문에 C에서는 strstr(), C++에서 string:find(),..