모북의 코딩블로그

그래프 정의 G = (V, E) V : 공집합이 아닌 유한한 정점의 집합 E : 유한한 edge들의 집합. 그래프 종류 방향성에 따른 분류 Undirected Graph 방향성이 없는 그래프 (u, v) = (v, u) Directed Graph 방향성이 있는 그래프 != 위 사진의 a, b가 undirected이고 c가 directed이다. 순환성에 따른 분류 Cyclic Graph 시작과 끝이 동일한 path가 있는 그래프 Acyclic Graph 순환할 수 없는 그래프 (tree가 대표적인 acyclic graph이다.) 가중치에 따른 분류 Unweighted Graph edge에 가중치가 없는 경우 Weighted Graph edge에 가중치가 있는 경우 / 인접 행..

다양한 DCNN 구조에 대해 간단하게 살펴보겠다. 아래에서 살펴볼 4개의 모델들은 ILSVRC(ImageNet Large Scale Visual Recognition Challenge)라는 대회에서 만들어진 모델이다. 2010년부터 2017년까지 진행되었으며 이 대회는 DCNN에 큰 혁신을 일으켰다. AlexNet (2012) 최초로 DCNN 구조를 사용한 방식이다. 이 방식이 기존의 ML 방식을 크게 뛰어넘게 되고, 이후의 방법에도 큰 영향을 주었다. 구조 5개의 convolution 층과 3개의 FC 층이 있다. 커널을 11*11,5*5,3*3 형태를 사용하였다. 특징 활성화 함수롤 ReLU 처음 사용 FC layer 사이에 dropout 사용 데이터 증강 기법 사용 Batch size 는 128 V..

생성 모델 주어진 학습 데이터를 기반으로 해당 분포에서 새로운 샘플을 생성한다. 우리는 P_model(x)를 얻어서 새로운 x를 샘플링하는 것이 목적이다. 명시적(explicit) 밀도 추정 : P_model(x) 를 명시적으로 정의하고 찾아내는 방법 암시적(implicit) 밀도 추정 : P_model(x)를 명시적으로 정의하지 않고도 샘플링 할 수 있는 모델을 학습하는 방법 화소를 독립적으로 생각하여 이미지를 생성하는 모델 확률적 생성모델 화소 별로 확률을 파악해 랜덤으로 생성한다. 화소별로 학습해 생성한 결과는 그리 좋지 않게 보인다. 그래서 뒤쪽에 나오는 오토인코더나 GAN 등이 만들어졌다. 화소가 서로 독립적이지 않다고 생각하는 모델 PixelRNN 순환 신경망을 이용하여 생성하는 방법 새롭게 ..

강화 학습 보상 또는 페널티와 같은 피드백으로 에이전트의 학습 과정을 돕는 방법 강화학습과 지도학습의 비교 지도 학습 (신경망) 강화 학습 문제(데이터) 훈련 집합 X와 Y 환경 또는 환경에서 수집한 데이터 최적화 목표 o 과 y의 오차인 |o-y| 최소화 누적 보상 최대화 학습 알고리즘이 알아내야 하는 것 오차 최소화하는 신경망의 가중치 누적 보상을 최대화하는 최적 정책 품질을 평가하는 함수 손실함수 가치함수 학습 알고리즘 SGD 동적 프로그래밍, Salsa, Q러닝, DQN 등 탐사형 정책과 탐험형 정책 에이전트가 주어진 state에서 어떤 action을 선택할지 결정하는 규칙이나 전략 탐사형 정책 (exploitation policy) 이미 알려진 영역이나 분야를 더 자세히 조사하고 연구하는 과정 ..

시계열 데이터 시계열 데이터란? 시간 축을 따라 신호가 변하는 동적 데이터 심전도, 주식, 음성인식 등이 있다. 시계열 데이터 특성 요소의 순서가 중요하다. (time dependency) 샘플의 길이가 다르다. 문맥 의존성 (context dependency) 를 가진다. 계절성(seasonality)을 가지는 데이터가 있다. 시계열 데이터 표현 (가변길이, 벡터의 벡터로 구성) 시계열 데이터 구조 윈도우 크기 (w) : 문제의 이전 요소를 얼마나 볼 것인가? 수평선 계수 (h) : 얼마나 먼 미래를 예측 할 것인가? 데이터가 다중 품목을 표현하고 있을 수도 있다. 다중 채널의 데이터는 벡터의 벡터 구조로 표현하면 된다. X1 = ((34,12), (35,10), (36,8)) Y1 = (35, 15)..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다...

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작..

최단 경로 문제 (Shortest path problem) 가중치가 있는 그래프에서 한 정점에서 다른 정점까지 갈 수 있는 최단 경로를 구하는 문제이다. s 에서 t로 갈 때 지나가는 경로 상에 있는 cost의 합이 최소화 되는 경로를 찾는 경우이다. 최단경로 문제는 Internet packet routing, flight reservation, driving directions 등 다양한 경우에 사용된다. 최단경로 문제를 해결하는 방법은 여러가지가 있는데 그 중에 대표적인 것은 아래 세 가지이다. 다익스트라 알고리즘 (Dijkstar's algorithm) 플로이드-와샬 알고리즘 (Floyd Warshall algorithm) 벨만 포드 알고리즘 (Bellman Ford algorithm) 오늘은 이 ..

허프만 코드는 그리디 알고리즘으로 해결할 수 있는 대표적인 문제이다. 오늘은 허프만 코드가 무엇인지, 그리고 어떻게 구현하는지에 대해 알아볼 것이다. 2023.06.08 - [Computer Science/Data structure & Algorithm] - [Algorithm] Greedy Algorithm (탐욕 알고리즘) [Algorithm] Greedy Algorithm (탐욕 알고리즘) Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 ..

Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 하여 문제 해결을 수행하는 경험론적 알고리즘. 그리디 알고리즘은 이름에서 유추할 수 있듯이 각 단계마다 당장 가장 '좋은' 방법을 선택한다. 문제를 전체적으로 고려해 가장 좋은 것을 찾는 DP나 이진탐색과는 차이가 있다. 기본 접근법 선택 절차 (selection procedure) 특정 후보 중에 하나를 선택해 해당 방식이 주어진 문제의 해인지 결정하는 절차이다. 이때 해는 현재의 상황에서 가장..