산 넘어 산 개발일지

Activation Functions Activation function은 한 뉴런(혹은 레이어)에서 값을 출력할 때 사용되는 함수이다. 즉 가장 최종적인 연산이라고 생각하면 된다. 이 Activation function에도 여러 종류가 있다. 가장 최초로 나온 것은 Sigmoid이며, 이에 대한 보완책으로 여러 함수들이 개발되었다. 이 함수들에 대해서 각각 어떤 문제점을 보완했는지, 단점은 무엇이 남아있는지를 공부하고자 한다. Sigmoid 함수는 일정한 범위 내에서(약 [-4, 4])는 선형적인 모습을 보이지만, 이를 벗어나면 비선형적인 모습을 보인다. 이는 뉴런의 "firing rate"를 적절히 해석했다는 점에서 장점이 있지만, 3가지 단점이 있다. 첫 번째는 saturate 되는 부분, 즉 뉴런..

Fully Connected Layer (FC layer) Fully Connect Layer(이하 FC layer)는 보통 CNN 모델들의 마지막 분류기에서 사용된다. 보통 W라는 가중치에서 한 줄의 원소들이 모두 input 원소들과 곱해져 하나의 activation 노드를 형성하기 때문에 Fully-Connected(모두 연결된)이라는 용어를 쓰는 것 같다. W라는 가중치는 input -> output으로 만들어주므로 당연히 그 사이즈는 (inputSize x outputSize) 이다. 이를 통해, activation 노드 하나는 W의 특정한 가중치를 통해 input 전체를 본다고 할 수 있겠다. Convolution Layer Convolution Layer는 한 이미지를 필터들을 통해 연산을 하..

Backpropagation 기본 원리 위 그래프에서 초록색 숫자는 forward feed 시에 계산되는 숫자들이다. 그리고 Backpropagation을 위해 맨 마지막 노드인 f에서부터 시작을 한다. 맨 처음 받는 값은 df/df이므로 1이다. f노드에 해당하는 식은 q*z 이므로 q에대한 f의 미분은 z이고, z에 대한 f의 미분은 q이다. 따라서 아래와 같은 결과값들을 얻을 수 있다. 이 때, "A에 대한 B의 미분" 이라 함은 "B에 대한 A의 영향력" 이라고 해석할 수 있다. 즉 A가 바뀌는 정도에 따라서 B가 얼만큼 바뀌는지를 정의한 식이다. q에 대한 f의 미분을 알았으니, 다음으로는 x, y 에 대한 f의 미분(f에 대한 x, y의 영향력)을 구해야 한다. 이를 구하기 위해서 "Chain..

풀이 키워드 DP 이분 탐색 LIS LIS(최장 증가 부분 수열) 이분탐색에서 주로 나오는 LIS문제였다. DP랑 같이 합해져서 나오는 문제 중 자주 나오는 유형인 것 같다. 이런 LIS의 경우 방식은 다음과 같다. 1. List를 만들고 첫 번째 원소를 넣는다. 2. 다음 원소(Next)부터는 list의 맨 마지막 원소(Last)와 비교하며 조건마다 특정한 작업을 수행한다. (조건 1) Last = Next list 원소 중 Next와 같거나 Next보다 작으면서 가장 비슷한 원소의 바로 다음 원소를 삭제하고 그 자리에 Next를 넣는다. (가령, Last = 3 이고 List = [1, 2, 4]였다면 4자..

Loss Functions 1. Multiclass SVM loss 설명 Multiclass SVM loss는 정답 score와 비정답 score 간의 차이로 손실함수를 계산하는 방식이다. 이 때 중요한 점은 score의 정확한 값보다는 정답 scroe와 비정답 score간의 상대적인 차이에 집중한다는 점이다. 시그마에서 j = yi를 빼는 이유는 Loss의 이론적 최소 값을 0으로 맞추기 위함이다. 만약 j = yi가 식에 포함된다면, Sj - Syi + 1 = 1이 되므로 Loss의 최소 값이 0이 될 수 없다. 디버깅 초기 W의 설정은 주로 0과 비슷한 작은 값으로 설정한다. 즉 Sj 와 Syi가 매우 흡사해지므로, 초기 W가 잘 설정되어 있다면 Total loss = (Class 개수) - 1 이..

풀이 키워드 Stack 스택은 처음 사용해보았다. 스택이라는 개념은 알고 있었지만, 알고리즘에 사용해본 경우는 처음이였다. 스택을 사용하지 않고 재귀를 이용해 풀었을 때는 틀리는 케이스들도 있었고 무엇보다 효율성을 통과하지 못했다. 스택을 사용한 경우, 일단 무엇보다 코드가 간결해졌다. 뭔가 재귀로 풀어야 할 문제들을 만났을 때, 재귀로 풀기 전 스택을 한번 고려해보면 좋을 것 같다고 느꼈다. 우선 원리는 간단하다. 입력받은 문자열 s를 한 문자씩 탐색해나간다. 그리고 조건에 따라 문자를 스택에 넣거나(push()) 스택에서 문자 하나를 빼낸다(pop()). push() 조건 Stack이 비어있거나 || 스택의 윗부분이 현재 문자와 다를 경우 pop() 조건 Stack이 비어있지 않을 경우 && 스택의 ..

풀이 키워드 다익스트라 다익스트라로 푸는 것을 안다면 그렇게 어려운 문제는 아니였다. 그러나 다익스트라로 풀어야 한다는 것을 눈치채는 것이 문제라면 문제인 그런 유형이였다. 우선 그래프 탐색에는 유명한 3가지 DFS, BFS, Dijkstra가 있다. 우선 대부분의 문제에서 2차원 형식의 지도(?)처럼 주어지면 대개 DFS/BFS로 푸는 경우가 많다. 반대로, Dijkstra의 경우 대부분 이렇게 2차원 지도로 주어지지 않고 각 노드간의 연결 정보와 그 가중치가 주어진다. 이렇게 주어지는 이유는, DFS/BFS와 Dijkstra의 가장 큰 차이점은 노드간 가중치가 같은지 여부이기 때문이다. DFS/BFS의 경우 모든 노드간의 가중치가 같고, 우리가 찾아내야 하는 정답의 기준은 "얼마나 적은 수의 노드를 ..

풀이 키워드 에라토스테네스의 체 이번 문제는 척 보면 알 수 있듯이 소수를 사용하는 문제이다. 소수하면 바로 에라토스테네스의 체가 떠오른다. 에라토스테네스의 체는 범위 내의 숫자들이 소수인지 아닌지를 미리 판별해내는 계산이다. 간단히 설명하자면, 미리 1~N까지의 배열(boolean)을 만들어 놓는다. 그리고 처음에는 2부터 시작을 한다. 2를 제외한 2의 배수들은 소수가 아니므로 소수가 아니라고 마킹(false)한다. 그리고 다음 숫자 3으로 넘어간다. 3은 소수가 아니라 마킹이 안되었으므로 앞 과정과 동일하게 3을 제외한 나머지 배수들을 소수가 아니라고 마킹한다. 다음 4는 2에 의해 마킹되었으므로 넘어간다. 다음 5는 마킹이 안되었으므로 앞 3과 동일한 작업을 수행한다. 이런 과정을 N까지 반복하면..

풀이 키워드 브루트포스 정해진 규칙이 딱히 없으니, 브루트포스로 일일이 다 해봐야 한다는 것을 알 수 있다. 그런데 이 때 어떤 것을 일일이 다 해볼지가 문제이다. 브루토프스의 경우, 가장 큰 틀에서 경우의 수를 일일이 해보는 것부터 생각을 해봐야 한다. 이번 문제의 경우, N의 채널은 0 ~ 500,000까지 존재하므로 만약 모든 채널을 일일이 다 해본다면 50만 번의 시도가 필요하다. 즉 나쁘지 않은 시도횟수이므로 이것을 기준으로 브투르포스를 진행하면 되는 것이다. 다만, 채널을 돌릴 때, 아래에서 N까지 시도해볼 수도 있고, 위에서 N까지 시도해볼 수도 있다. 예를 들어, N = 500000 일 경우 480000부터 시도해볼 수도 있지만, 520000부터 시도해볼 수도 있는 것이다. 어느 쪽에서 시..

풀이 키워드 다익스트라(Dijkstra) 일반적인 다익스트라 알고리즘으로 풀리는 문제이다. 한 노드에서 각 노드까지 갈 수 있는 최단거리를 구해야 하며, 각 노드마다 가중치가 각각 다르므로 DFS, BFS로는 풀 수 없고 다익스트라로 풀어야 한다는 것을 알 수 있다. 우선순위 큐(PriorityQueue)를 사용해서 풀면 훨씬 빠르고 편리하다. 우선순위 큐를 사용하면 현재 큐를 최적의 방법으로 정렬하여 가장 거리가 짧은 노드부터 검사할 수 있게 해주며, 이 때문에 각 노드의 방문여부를 체크할 필요가 사라진다. 푸는 방식을 간단하게 소개하면 다음과 같다. 도시들의 그래프인 arr[]이 있고, 시작점에서 각 도시까지의 거리를 나타낸 dist[]가 있다. dist[]는 시작점은 0으로, 나머지는 Inf 값으로..