본문 바로가기
728x90

전체 글424

Lecture 16 - 강연결 요소 + 그리디 알고리즘(1) 강연결 요소 유향 그래프의 모든 정점 쌍에 대해서 양방향으로 경로가 존재하면 강하게 연결되었다고 한다. 그래프 전체 대신 강하게 연결된 부분 그래프에 대해서는 강연결 요소 (Strongly connected component)라고 한다. 아래는 강연결요소를 찾는 psuedo code이다. 수행 시간: Θ(|V|+|E|) 예시 그래프를 통해 자세히 살펴보자. 그리디 알고리즘 그리디 알고리즘(Greedy algorithm)은 이름처럼 눈앞의 이익만 취하고 보는 알고리즘을 뜻한다. 현재 시점에서 가장 이득인 것으로 보이는 해를 선택하는 행위를 반복한다. 많은 경우에 그리디 방식은 최적해를 보장하지 못하지만, 드물게 최적해가 보장되는 경우가 존재하므로 해당 특별한 case를 잘 알아두는 것이 중요하다. 그리디 .. 2023. 5. 15.
Word Embedding(2) Skip-Gram with Negative Sampling (SGNS) 네거티브 샘플링(Negative Sampling)을 사용하는 Word2Vec을 직접 케라스(Keras)를 통해 구현해보고자 한다. 네거티브 샘플링 (Negative Sampling) Word2Vec의 출력층에서는 소프트맥스 함수를 통과한 단어 집합 크기의 벡터와 실제값인 one-hot 벡터와의 오차를 구하고 이로부터 임베딩 테이블에 있는 모든 단어에 대한 임베딩 벡터 값을 업데이트합니다. Word2Vec은 역전파 과정에서 모든 단어의 임베딩 벡터값의 업데이트를 수행하지만, 만약 현재 집중하고 있는 중심 단어와 주변 단어가 '강아지'와 '고양이', '귀여운'과 같은 단어라면, 이 단어들과 별 연관 관계가 없는 '돈가스'나 '컴퓨터'와 .. 2023. 5. 14.
Lecture 4 - One Random Variable Cumulative Distribution Function (CDF) CDF의 정의는 다음과 같다. X 2023. 5. 13.
Word Embedding(1) 희소 표현(Sparse Representation) one-hot 인코딩과 같은 방식으로 인코딩을 한 결과인 one-hot 벡터들은 하나의 인덱스의 값만 1이고 나머지 인덱스는 전부 0으로 표현하는 벡터표현 방법을 희소표현이라고 하고 이때 one-hot 벡터는 희소 벡터이다. 희소 벡터의 문제점은 단어의 개수가 늘어나면 벡터의 차원이 계속 커진다는 점이다. 단어가 10,000개였다면 벡터의 차원은 10,000이어야한다. 심지어 그 중에서 단어의 인덱스에 해당되는 부분만 1이고 나머지는 0의 값을 가져야만 한다. 단어 집합이 클수록 고차원의 벡터가 된다. 예를 들어 단어가 10,000개 있고 인덱스가 0부터 시작하면서 강아지란 단어의 인덱스는 4였다면 one-hot 벡터는 다음과 같이 표현된다. Ex) 강.. 2023. 5. 11.
Lecture 18 - Graph(2) 위상 정렬 (Topological Sorting) 우선 싸이클이 없는 유향 그래프에서 정의되는 문제이다. 간단하게 살펴보면 모든 정점을 정렬하되 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야 하는 정렬이다. 이때 복수의 위상 순서가 존재할 수 있다. 라면 끓이기에서 위상순서를 나타낸 그래프를 보면 위와 같다. Kahn 기반 알고리즘 다음은 Kahn 알고리즘 기반 위상 정렬의 psuedo code이다. topologicalSort1(G, v) { for ← 1 to n { 진입간선이 없는 정점 u를 선택한다; A[i] ← u; 정점 u와, u의 진출간선을 모두 제거한다; } ▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다 } 수행 시간은 Θ(|V|+|E|)이고.. 2023. 5. 8.
Long Short-Term Memory (LSTM) Vanilla RNN의 한계 기본을 뜻하는 Vanilla RNN은 time-step이 길어질수록 정보량이 손실되어 시점이 길어지면 x1과 같은 초반부의 정보의 영향력은 거의 없어지게 된다. 이러한 문제를 장기 의존성 문제(the problem of Long-Term Dependencies)라고 한다. 위와 같은 Vanilla RNN을 보완하여 아래와 같은 LSTM을 만들었다. LSTM 구조 LSTM은 은닉층의 메모리 셀에 입력 게이트, 망각 게이트, 출력 게이트를 추가하여 불필요한 기억을 지우고, 기억해야할 것들을 정한다. 요약하면 LSTM은 은닉 상태(hidden state)를 계산하는 식이 전통적인 RNN보다 조금 더 복잡해졌으며 셀 상태(cell state)라는 값을 추가하였다. 셀 상태는 Ct로 .. 2023. 5. 5.
Lecture9, 10 - Gauss's Law, Divergence Gauss's Law 가우스 법칙은 특정 폐곡면을 잡았을때 해당 폐곡면을 통과하는 electric flux density의 총합이 해당 폐곡면의 내부에 존재하는 모든 전하량의 합이 같다는 법칙이다. Point charge field 점전하에 의해서 발생된 charge field를 살펴보자. 위의 상황에 대해 가우스 법칙을 적용해보면 다음과 같다. Line charge field 선전하에 의해서 발생된 charge field에 대해서 알아보자. 위의 상황에 대해서 가우스 법칙을 적용해보자. Divergence 전자기학에서의 Divergence는 벡터장의 확산 정도를 나타내는 개념이다. 특정 미소 지점에서 벡터장의 상태를 표현하는 스칼라 값이다. 위와 같이 divergence를 이용하여 전하밀도를 구할 수 .. 2023. 5. 4.
Lecture8 - Electric Flux Density Faraday Experiment 패러데이의 실험에서는 전하량 +Q로 대전된 내부의 금속구를 폐곡면 금속구로 감싸서 아래와 같이 Flux와 Q가 완전히 일치하는 상태를 만들었다. 그리고 그에 따라 전기 플럭스 밀도에 대한 식을 다음과 같이 쓸 수 있게 되었다. 외부원과 내부원을 따로 보면 다음과 같다. 이를 일반화하면 다음과 같이 D벡터로 표현할 수 있다. 이때 이를 electric field intensity와 비교하면 아래와 같은 관계식을 구할 수 있다. 따라서 electric flux density와 electric field intensity를 비교해보면 다음과 같다. 2023. 5. 4.
Baekjoon Training #5430 #5430 AC import sys from collections import deque input = sys.stdin.readline T = int(input()) # 테스트 케이스의 개수 T입력 for i in range(T): p = input().strip() # 함수 입력 n = int(input()) # 정수 배열의 정수의 수 입력 err = 0 # 에러 상태인지 확인 arr = input().strip() # 정수 배열 입력 dq = deque(arr[1:-1].split(',')) # []와 , 를 제거하여 deque 자료구조로 dq에 입력 if n == 0: # n이 0이면 빈 deque으로 설정 dq = deque() R_cnt = 0 # R연산 횟수 카운터 for i in range.. 2023. 5. 4.
Yale - Financial Markets (Lesson #7) Behavior Finance 행동경제학은 인간 심리학을 바탕으로 경제학을 분석한 굉장히 중요한 분야이다. 행동경제학이라는 용어는 1990즈음에 처음 나왔지만 행동경제학의 역사는 경제학의 아버지라고 불리는 Adam Smith의 이론에서 부터 시작된다. 그는 1776년 "국부론"에서 이렇게 말했다. 석탄을 파는 양은 누가 결정하는가? 1776년부터 지금까지도 석탄을 파는 양을 결정하는 국가 부처는 한번도 없었다. 이를 결정하는 것은 이윤 동기이다. 이는 자유시장을 상징하는 "보이지 않는 손"과도 연관이 있다고 할 수 있다. 그는 1759년 심리학 전공자는 아니지만 "도덕감정론"이라는 책을 출판했다. 애덤 스미스는 사람들은 칭찬받는것을 매우 좋아한다고 했다. 이점은 정말 당연한 것이다. 하지만 여기서 그치지.. 2023. 5. 3.
Recurrent Neural Network 순환 신경망(RNN) RNN(Recurrent Neural Network)은 시퀀스(Sequence) 모델로 입력과 출력을 시퀀스 단위로 처리한다. 단어 시퀀스로 이루어진 언어모델들이 대표적인 시퀀스 모델이다. RNN은 딥러닝에서 가장 기본적인 시퀀스 모델이라고 할 수 있다. 우선 순환 신경망의 가장 큰 특징은 그림과 같이 활성화 함수를 통해 나온 결과를 출력층 방향으로도 보내주는 것이다. RNN에서 은닉층에서 활성화 함수를 통해 결과를 내보내는 역할을 하는 노드를 셀(cell)이라고 한다. 이 셀은 이전의 값을 기억하려고 하는 일종의 메모리 역할을 수행하므로 이를 메모리 셀 또는 RNN 셀이라고 표현한다. 위와 같이 그림을 그리면 조금더 직관적으로 이해하기 쉽다. 은닉층의 메모리 셀은 각각의 시점(ti.. 2023. 5. 2.
Lecture 17 - Graph(1/4) 그래프 정점(vertex) 및 간선(edge)로 이루어진 자료구조이다. G = (V, E) 형태로 나타냄 (V: 정점 집합, E: 간선 집합) 두 정점이 간선으로 연결되어 있을 경우 인접하다고 한다. 종류 그래프의 종류를 나누는 기준은 다음과 같다. - 두 vertex 간 가능한 edge의 개수 - Edge의 방향 유무 - Loop의 유무 - 추가적으로 edge의 weight 유무에 따라 weighted, unweighted로 나눌 수 있음 인접 행렬을 이용한 그래프의 표현은 이해하기 쉽고 간선의 존재 여부를 Θ(1)만에 파악 가능하다. 그러나 그래프 정보를 저장하기 위해서만 Θ(𝑛^2) 시간이 소요되고 메모리 사용량도 크다는 점은 단점으로 작용한다. 간선의 밀도가 높은 그래프에서는 인접 행렬을 사용한 .. 2023. 5. 1.
728x90

티스토리툴바