본문 바로가기

Tech82

[알고리즘]DFS, BFS 이란 너비 우선 탐색(BFS, Breadth-First Search) : 루트 노드(혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 (즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색) 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. 너비 우선 탐색(BFS)의 특징 직관적이지 않은 면이 있다.(BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.) BFS는 재귀적으로 동작하지 않는다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.(즉, 선입선출(FIFO) 원칙으로 탐색) ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다. from collections import dequ.. 2022. 10. 11.
[알고리즘] 정렬(Sort) 정리 선택 정렬 (SelectSort) : 가장 작은 것을 선택해서 계속해서 제일 앞으로 보내는 알고리즘 가장 원시적이고 기초적인 방법 중 하나 데이터의 갯수가 N개일 때 총 몇번의 비교 연산을 해야 되는지 알아야 한다. 선택 정렬은 대략 N * (N+1)/2 번 가량의 연산을 수행해야 한다. 이를 컴퓨터에서는 가장 큰 차수인 N^2만 보고 O(N^2)이라고 표현한다. 즉, 선택 정렬의 시간 복잡도는 O(N^2)이다 정렬 방법 위에 보는 그림과 같이 step 에서는 순서대로 비교하며 index 0의 값을 끝에 값까지 비교한다 각각의 step을 거치면서 수행하면서 최솟값을 찾아서 위치를 바꿔준다 N개의 원소에 대해서는 N-1번을 비교하기 비교한다 def selectionSort(a): n = len(a) for.. 2022. 10. 11.
[영상] Bilinear Interpolation Bilinear Interpolation Bilinear interpolation은 우리 말로 적자면 쌍선형 보간법, 또는 이중선형 보간법 정도가 되며 1차원에서의 선형 보간법을 2차원으로 확장한 것이다. Bilinear interpolation 방법을 설명하기 위해 아래 그림과 같이 직사각형의 네 꼭지점에서의 값이 주어져 있을 때, 이 사각형의 변 및 내부의 임의의 점에서의 값을 추정하는 문제를 생각해 보자. 그림과 같이 점 P에서 x축 방향으로 사각형의 변까지의 거리를 w1, w2, y축 방향으로 거리를 h1, h2라 하고, 알려진 네 점에서의 데이터 값을 A, B, C, D라 할 때, P에서의 데이터 값은 bilinear interpolation에 의해 다음과 같이 계산된다 (단, α=h1/(h1+.. 2022. 10. 6.
[Paper] Faster RCNN Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks Contents 1. Overview 2. Related Work 2.1 Object Proposals (= region proposals) 2.2 Deep Networks for Object Detection 3. Faster R-CNN 3.1 Region Proposal Networks 3.2 Anchors 3.3 Multi-Scale Anchors as Regression References 3.4 Sharing Features for RPN and Fast R-CNN (4-step) 3.4 NMS (Non-Maximum Suppression) 3.6 RPN .. 2022. 10. 6.
[Paper] RCNN R-CNN RCNN은 논문에 설명하는 것처럼 거시적인 측면에서 봤을 때, Input image을 ROI를 통해서 각각의 Region에 해당하는 영역을 Selective Search를 통해서 약 2천장의 Proposal로 분석하고, 나눠진 Proposal을 통합 (Warp)하여 CNN 통해서 학습시켜 각각을 Classification을 할 수 있다. 논문의 사진을 다음과 같이 나누어 설명할 수 있는데, Proposal Method로부터 이미지를 Selective Search를 통해서 선정된 영역을 각각의 ConVN 으로 학습시킨 후 Feature map을 통하여 SVMs과 BBox reg으로 Validation and Evaluation을 할 수 있다. * Selective Search (SS) Regio.. 2022. 10. 6.
[NLP] Seq2Seq Seq2Seq Sequence to Sequence Learning with Neural Networks: https://arxiv.org/pdf/1409.3215.pdf 기존 LSTM 기반의 번역은 한계가 있었다. 왜냐하면 LSTM은 하나가 들어오면 바로 하나의 output을 낼 수 있는데 이것이 문제가 된다. 문자 그대로 인코더는 입력 데이터를 인코딩(부호화)하고, 디코더는 인코딩 된 데이터를 디코딩(복호화) 한다. 즉 인코더는 입력을 처리하고 디코더는 결과를 생성한다. Context벡터는 입력에 대한 정보를 압축하고 있는 벡터. 즉 인코더는 문장을 가지고 context 벡터를 만들어주는데, 이 context 벡터에는 문장에 대한 정보가 응축되어 있다. 반면 디코더는 정보가 응축되어 있는 contex.. 2022. 10. 4.
[NLP] LSTM /GRU LSTM (Long Short-Term Memory) RNN은 가변 길이의 시퀀셜 데이터 형태 입력에는 훌륭하게 동작하지만, 그 길이가 길어지면 앞서 입력된 데이터를 잊어버리는 단점을 가지고 있다. 하지만 LSTM의 등작으로 RNN을 단점을 보완할 수 있게 되었다. LSTM은 기존 RNN의 은닉 상태 이외에도 별도의 셀 스테이트 (cell state)라는 변수를 두어 그 기억력을 증가 시킨다. 그 뿐만 아니라 여러 가지 게이트(gate)를 둠으로써 기억하거나, 잊어버리거나, 출력하고자 하는 데이터의 양을 상황에 따라 마치 수도꼭지를 잠갔다가 열듯이 효과적으로 제어한다. 그 결과 긴 길이의 데이터에 대해서도 효율적으로 대처할 수 있게 되었다 요약하면 장단기 메모리(Long Short-Term Memory).. 2022. 9. 29.
[NLP] RNN (Recurrent Netural Network) RNN (Recurrent Netural Network, 순환신경망) RNN (Recurrent Netural Network, 순환신경망)은 NLP 처리 분야에서 뿌리가 될 만큰 중요한 것이다. NLP 분야에서 단어들이 모여 문장이 되고, 문장이 모여 문서가 되는 듯이 문장 내 단어들은 앞뒤 위치에 따라 서로 영향을 주고 받는다. 문서 내 문장들도 마찬가지다. 따라서 단순히 \(y = f(x)\)와 같은, 순서의 개념 없이 입력을 넣으면 출력이 되는 함수가 형태가 아닌, 순차적(Sequential)으로 입력을 넣고, 입력에 따라 모델의 은닉 상태 (Hidden State)가 순차적으로 변하며, 상태에 따라 출력 결과가 순차적으로 변환되는 함수가 필요했다. 이러한 시간 개념 또는 순서 정보를 사용하여 입력.. 2022. 9. 29.
[ML] SVM(Support Vertor Machine) 서포트 벡터 머신 (Support Vector Machine, SVM) 서포트 벡터 머신은 서포트 벡터를 기준으로 클래스를 판별한다. SVM은 퍼셉트론의 확장이라고 생각할 수 있으며, 퍼셉트론 알고리즘을 사용하여 분류 오차를 최소화 한다. SVM의 최적화 대상은 마진을 최대화 하는 것이다. 마진은 클래스를 구분하는 초평면(결정 경계)과 이 초평면에 가장 가까운 훈련 샘플 사이의 거리로 정의 된다. 이런 샘플을 서포트 벡터(support vector)라고 한다 최대 마진(large margin)의 결정 경계를 원하는 이유는 일반화 오차가 낮아지는 경향이 있기 대문이다. 반면 작은 마진의 모델은 과대적합되기 쉽다. 소프트 마진 (soft margin) 서포트 벡터 머신은 데이터가 잘못 분류되는 경우는 고려하.. 2022. 9. 26.

티스토리툴바