이니의 공부일지

DFS 일반적으로 재귀를 사용하여 구현한다. BFS 큐를 사용하여 구현한다. BFS는 정의상 시작점으로부터 가까운 지점부터 방문하게 되기 때문에 그림에서처럼 가중치가 전부 동일한 그래프에서는 최단거리를 확실하게 구해줄 수 있는 것이다. BFS를 이용한 최단거리는, 가중치만 전부 동일하다면 방향 그래프에서도 동일하게 적용된다.

트리의 정의는 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프이다. 트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징이다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부른다. 그 외에도 추가적인 용어들은 다음과 같다. 노드: 각 지점을 의미합니다. 정점이라 부르기도 한다. 간선: 두 노드를 연결하는 선을 의미합니다. 에지라고 부르기도 한다. 루트 노드: 트리에서 맨 꼭대기를 의미한다. 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부른다. 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미한다. 깊이: 루트 노드와..

오늘은 모델이 자연어를 이해할 수 있도록 만들어주는 과정인 Tokenization에 대해 학습할 것이다. Tokenization 이전의 전처리 과정은 자연어 형태에서의 noise를 줄여준다고 하면, Tokenization에서는 문자로 나타내는 단어를 컴퓨터가 이해할 수 있는 형태로 어떻게 바꿀 것인가?를 주로 배우게 된다. Tokenization은 우리가 여태까지 학습했던 내용과는 달리 생소할 수 있지만, NLP에서 가장 중요한 분야 중 하나이다. 다양한 언어의 문자를 간결한 형태로 컴퓨터가 이해할 수 있게 하지 않으면 이후의 모든 과정에서 비효율성이 발생할 수 있기 때문이다. Intro Input을 ' I am a student ' 라는 문장으로 놓는다. 이러한 문장을 전처리과정을 통해 깨끗하게 만들어..

오늘은 자연어 처리 데이터를 전처리 하는 과정을 배워보겠습니다. 전처리하는 파이프라인과 전처리하는 과정에서 활용할 수 있는 모듈을 배우고, 다룬 모듈을 활용해 간단하게 데이터를 크롤링하여 전처리하는 실습을 진행해보겠습니다. text data를 모델이 encode 할 때에는 아래와 같은 파이프라인을 거치게 된다. Normalization -> pre-tokenization -> tokenization -> post-processing 먼저, raw string이 덜 랜덤하고 깨끗해지는 과정을 통틀어 Normalization이라고 말한다. 예를 들면, white space(여백)을 제거하고, 특수기호를 제거하거나, 대소문자가 섞여있을때 하나로 통일해주는 과정이 있다. 이렇게 normalization 과정을 ..

스택 ( stack ) 스택은 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 말한다. 즉, 맨 아래에 있는 데이터를 꺼내기 위해서는 그 위의 데이터를 모두 꺼내야 할 것이다. 이런 구조를 후입선출 구조(LIFO; Last In First Out)라고 부른다. stack은 크게 5가지 함수 사용이 가능하다. 1. push(x) # x를 stack의 맨 위에 올려 놓는다. 2. size() # stack 위에 쌓인 블럭의 개수를 반환한다. 3. empty() # stack 위가 비어있다면 true, 비어있지 않다면 false를 반환한다. 4. top() # stack의 맨 위에 있는 숫자 값을 반환한다. 단, stack에서 그 블럭을 제거하지는 않는다. 5. pop() # stack의 맨 위에 있는..

이진탐색 이진탐색은, 찾아야하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것이다. 이진탐색을 사용하는 이유는 순차탐색보다 더 빠르기 때문이다. 실제 이진탐색의 시간복잡도는 O(logN)이다. 루프를 한 번 돌때 마다, 우리가 다루는 구간의 길이는 반으로 감소하고, 구간의 길이가 1이 될 때 까지 계속 반복해서 탐색하는 것을 볼 수 있다. 즉, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN)이 되는 것을 볼 수 있다. O(N)과 O(logN)은 정말 큰 차이를 보인다. 만약, N이 4,294,967,296이라면, O(logN)의 시간복잡도를..

오늘은 Attention의 개념을 다뤄보겠습니다. Sequence-to-sequence 구조의 RNN계열 모델에서 attention이 왜 필요한지, 어떻게 적용될 수 있는지 살펴보도록 하겠습니다. Sequence to sequence sequence to sequence model을 보면, 한쪽은 encoder, 다른 한쪽은 decoder라는 부분으로 나뉘어져 있다. 간단하게, encoding은 문장이 들어가는 부분, decoding은 문장이 나오는 부분이라고 생각하자. 이들은 각각 RNN 혹은 LSTM 혹은 GRU를 기반한 구조가 된다. 위 그림은 챗봇의 예제로써, 질문이 들어왔을 때, 그것에 답을 하는 task를 수행하는 것이다. 이 질문은 LSTM에 기반해서 하나씩 입력을 받아 다음 step으로 넘..

오늘은 RNN의 long-term dependency에 대해 다뤄보도록 하겠습니다. RNN에는 어떤 문제가 존재하는지 살펴보고, 이 문제를 완화하는 방법인 LSTM과 GRU에 대해 다뤄볼 것입니다. 그리고, RNN에서 gradient exploding, vanishing이 왜 발생하는지 computational graph를 통해 살펴보도록 하겠습니다. 더불어 RNN의 base model들을 리뷰하고, 기존 RNN-based model의 overfitting 문제를 해결하기위한 방법들을 알아보겠습니다. Vanishing Gradient RNN은 long term dependency라는 문제가 있다. 이는, 오래전에 있었던 문제를 쉽게 까먹는다는 것이다. 예를 들면, 'Jane walked into the ..

RNN에 대해 짧게 복습한 후, RNN의 다양한 task에 대한 설명을 다룰 것입니다. RNN RNN이라고 하는 것은, sequence data 혹은 time series data를 입력으로 받는 함수이다. sequence data라는 것은, 매 time step마다 들어오고 있는 입력이 있다는 것이다. 예를들면, ' I go home ' 이라는 문장이 있을 때, time step 이 1일때, I 가 들어오고, time step이 2일 때, go가 들어오게 된다. RNN의 기본 구조는 매 time step마다 동일한 function을 쓰고, 이 function의 출력은 현재 time step의 hidden state이고, 입력은 이전 time step의 hidden state vector와 현재 time..