NeuroWhAI의 잡블로그

이 알고리즘은 우연히 알게되었다. 구현은 참으로 간단한데 이게 왜 되는지 이해가 안돼서 한참을 삽질했다. 정리할 겸 글을 적어본다. 일단 알고리즘의 목적은 유향 그래프든 연결 리스트든 그 속에 순환이 존재하는지, 존재한다면 그 시작 지점은 어딘지 찾는 것이다. 1. 먼저 시작 노드를 가리키는 포인터 2개를 준비한다. 2. 노드의 간선을 따라 포인터를 이동시킬 것인데 하나는 1칸씩, 다른 하나는 2칸씩 옮긴다. 3. 순환이 없다면 두 포인터가 만나는 일은 없겠지만 순환이 존재하면 결국 만나게 된다. 4. 이때 느린 포인터를 다시 시작 노드로 옮기고 이번엔 둘 다 1칸씩 이동시킨다. 5. 그럼 또 결국 어떤 지점에서 만나게 되는데 놀랍게도 여기가 순환이 시작되는 곳이다. 이 방법으로 순환을 찾을 수 있다는 ..

https://www.acmicpc.net/problem/6591 정답 비율이 낮아서 겁먹고 미뤘던 문제입니다. 그런데 다른 쉬웠던 이항 계수 문제랑 거의 똑같이 했는데도 패스가 나네요. 무엇?? 그냥 캐시를 사용한 동적계획법으로 풀었더니 시간, 공간 복잡도가 안습이긴 하지만 패스는 되더라고요. 이후에 검색해서 공부한 방법으로 다시 풀었더니 정석대로 패스된 것 같습니다. 동적계획법으로 풀때의 아이디어는 위키백과에서 봤던 C(n, r) = C(n, n-r)이라는 점을 이용해서 중복 계산을 피하는 것이고 r = 0, r = 1, n = r일때는 답이 명확하므로 조건문을 써줬다는 것? 캐시는 최대한 크게 할당하고 n, r이 범위에 있을때만 캐시를 검사하도록 했습니다. 2번의 메모리 초과는 적절한 캐시 크기를 ..

#include #include #include #include using namespace std; // Knuth-Morris-Pratt Algorithm // bush의 앞에서부터 needle의 최초 위치를 찾아 반환합니다. size_t kmp(string_view bush, string_view needle) { const size_t needleLen = needle.length(); const size_t bushLen = bush.length(); // string::find는 패턴 문자열이 비어있을 경우 0을 반환함. if (needleLen == 0) { return 0; } // pi[match] == needle[:match+1]의 최대 동일 접두접미사 길이 vector pi(need..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. (가중치 초기화 방법들(Xavier, He)은 코드로 구현은 하였지만 글은 넘어갑니다.) 드롭아웃은 오버피팅(과적합)을 방지하기 위해서 순전파시 일정 확률로 특정 출력값을 0으로 만들고 역전파시에도 기울기의 해당 부분들을 0으로 만들어서 보냅니다. 보통 일정 확률로 신경망의 뉴런을 비활성화한다 혹은 끈다고 설명합니다. 학습이 좀 느려진다는 단점은 있지만 쉽게 과적합을 어느정도 이겨낼 수 있습니다. 비슷하게 배치정규화라는 놈도 과적합을 방지해주지만 이건 학습 속도가 훨씬 빠릅니다. 아래 코드는 드롭아웃 계층을 어떻게 구현했는지만 넣어놨습니다. 코드: impl Layer for Dropout { fn forward(&mut self, x..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 매개변수라 함은 학습시 손실을 줄이기 위해 조절하는 변수들을 말합니다. 가중치나 편향 등을 매개변수라고 할 수 있습니다. 이때까지는 매개변수를 단순히 학습률과 기울기의 곱으로 빼서 갱신했지만 그것보다 더 잘할 수 있는 방법이 많습니다. 참고로 이때까지 사용한 방법은 SGD(확률적 경사 하강법)로 볼 수 있습니다. 아래 코드는 5장에서 구현했던 신경망을 살짝 수정해서 여러 매개변수 갱신법을 사용해 MNIST 학습을 진행하는 예제입니다. 코드: use std::collections::HashMap; use rulinalg::matrix::{Matrix, BaseMatrix, BaseMatrixMut}; use common::utils; ..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 5장의 마지막입니다. ReLU, Affine 등의 레이어를 잘 구현해서 쌓아올리기만 하면 학습이 가능한 신경망을 만들 수 있습니다.이게 가능한 이유는 체인룰 덕분이고 이전 글에서 계산 그래프를 통해 설명되었습니다. forward, backward 메소드에 주목하셔야 하는데 forward는 흔히 아시는 순전파에 역전파에 사용할 값을 기억해두는 역할도 합니다. backward가 역전파이고 뒷 계층의 기울기(dout)를 받아 현재 계층의 기울기를 구하여 저장한 뒤 앞 계층으로 넘겨줍니다. 아래 코드는 Affine - ReLU - Affine - Softmax 순서로 계층을 쌓아 만든 신경망으로 MNIST를 학습하는 예제입니다. 이전에 수치..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 5장에서는 계산 그래프라는 방법을 통해 순전파, 역전파를 가르쳐줍니다. 연쇄 법칙(Chain rule) 덕분에 각 층의 자체(?) 기울기를 곱하면서 역전파하면 각 층의 최종 기울기를 얻을 수 있습니다. 아래 코드는 간단하게 덧셈, 곱셈 레이어를 만들고 이를 사용하여 사과, 오렌지의 가격을 순전파로 계산한 다음 역전파로 각 요소가 최종 가격에 끼치는 기울기를 계산하는 예제입니다. 코드: pub struct MulLayer { x: f32, y: f32, } impl MulLayer { pub fn new() -> Self { MulLayer { x: 0.0, y: 0.0 } } pub fn forward(&mut self, x: f32..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 이번에는 이때까지 구현한 기능을 조합하여 2층 신경망을 만들어봅니다. 다만 수치 미분을 사용했기에 매우 느려 학습이 잘 되는지는 확인하지 못했으니 대충 흐름만 보시면 되겠습니다. 코드에서 MNIST 데이터셋과 관련된 부분은 포함하지 않았으니 관심있으신 분은 GitHub에서 보시면 되겠습니다.또한 속도를 높히기 위하여 데이터셋의 일부만 학습에 사용하였고테스트를 위해 사용했던 해석적 미분을 이용한 부분은 주석 처리 해두었습니다. 코드: use std::f32; use rulinalg::matrix::{Matrix, BaseMatrix, BaseMatrixMut}; use rand; use ch03::activation; use commo..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 이전에 신경망의 학습은 손실 함수의 값을 최소화하는 방향으로 파라미터를 조정한다고 했습니다. 그럼 파라미터를 어떻게 조절해야 손실이 줄어드는지 알 수 있을까요? 저는 미적분을 제대로 배우지 않았지만 미분은 값의 변화와 관련이 있다는건 압니다. 그러니까 L = f(x)이고 x가 d만큼 변했을때 L은 d의 몇 배만큼 변하는지가 미분이라고 대충 알고 있습니다. 여기서 L을 손실, f를 손실 함수 + 신경망, x를 파라미터라고 하면 대충 윤곽이 보이죠. 우리는 f 함수를 미분하여 기울기를 구해 x를 올바른 방향으로 조절할 수 있습니다. 그런데 저 같은 수포자에게 함수를 미분하라는건 힘든 일입니다. 그러나 수치 미분이란 방법을 쓰면 해석적 미..

※ 실제로 동작하는 전체 소스코드는 GitHub에서 보실 수 있습니다. 손실 함수는 신경망의 학습 정도를 수치화하는데 사용되는 함수입니다. 손실 함수의 값을 최소화하는 방향으로 신경망의 파라미터들을 조정하는게 학습입니다. 여러 종류가 있는데 보통은 어떤 문제를 푸느냐에 따라 다른 함수를 사용하는 것 같습니다. 아래 코드는 대표적인 손실 함수인 MSE와 Cross entropy를 구현하고 손실값을 계산해보는 예제입니다. 코드: use rulinalg::matrix::{Matrix, BaseMatrix, BaseMatrixMut}; pub fn mean_squared_error(y: &Matrix, t: &Matrix) -> f32 { let mut err = y - t; err = err.apply(&|v..