바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

Derivatives Trading

파생상품: 주식과 채권 등 전통적인 금융상품을 기초자산으로 하여 기초자산의 가치변동에 따라 가격이 결정되는 금융상품

- 파생상품은 기초자산의 가격 변동에 따른 위험을 헤지(Hedge)하거나, 수익을 극대화하기 위해 사용됨

*Hedge/Hedge Fund란? → https://lets-hci-la-ai-withme.tistory.com/199

기초자산(underlying asset): 파생상품에서 거래대상이 되는 자산 (ex. 주식, 채권, 원자재, 환율, 금리, 지수 등)

ex) 코스피200 선물거래의 기초자산은 코스피200 지수 → 코스피200 지수의 가격이 상승하면, 코스피200 선물의 가격도 상승. 따라서 코스피200 선물을 매수한 투자자는 코스피200 지수의 상승에 베팅하는 것임

주요 파생상품 유형

1) Forward(선도거래)

- 두 당사자가 미래의 특정 시점에 특정 가격으로 기초자산을 거래하기로 약속하는 거래

- 장외에서 비공개로 이루어지며, 거래 당사자들은 서로의 신용도에 따라 거래 조건을 협의함

예시

• 농산물 생산자: 1년 후의 옥수수 가격이 현재보다 하락할 것으로 예상하는 농산물 생산자는 1년 후의 옥수수 선도거래🌽를 통해 현재보다 높은 가격으로 옥수수를 판매할 수 있음 
• 수입업체: 1년 후의 원유 가격이 현재보다 상승할 것으로 예상하는 수입업체는 1년 후의 원유 선도거래🛢️를 통해 현재보다 낮은 가격으로 원유를 구매할 수 있음

2) Swap(스왑)

- 두 당사자가 서로 다른 자산 또는 금융상품을 교환하는 거래

- 장외에서 비공개로 이루어지며, 거래 당사자들은 서로의 신용도에 따라 거래 조건을 협의함

예시

• 기업 A: 고정금리로 금융기관에서 대출을 받은 기업 A는 변동금리📈로 대출을 받고 싶어 함. 기업 A는 변동금리로 대출을 받은 기업 B와 스왑 계약을 체결하여, 두 기업이 서로의 대출 조건을 교환함.
• 금융기관 A: 미국 달러로 대출을 받은 금융기관 A는 유로화💶로 대출을 받고 싶어 함. 금융기관 A는 유로화로 대출을 받은 금융기관 B와 스왑 계약을 체결하여, 두 금융기관이 서로의 대출 통화를 교환함

3) Futures(선물거래)

- 거래소에서 표준화된 조건으로 거래되는 파생상품

- 거래소의 중개를 통해 이루어지며, 거래 당사자들은 거래소의 규정에 따라 거래 조건을 준수해야 함

예시

• 개인투자자: 1년 후의 코스피200 지수가 현재보다 상승📈할 것으로 예상하는 개인투자자는 코스피200 선물거래를 통해 1년 후의 코스피200 지수 상승에 베팅할 수 있음
• 기업 A: 1년 후의 원유 가격이 현재보다 상승📈할 것으로 예상하는 기업 A는 원유 선물거래를 통해 1년 후의 원유 가격 상승에 베팅할 수 있음

4) Options(옵션거래)

- 옵션; 선택할 수 있는 권리

- 특정 시점에 특정 가격으로 기초자산을 매수 또는 매도할 수 있는 권리를 매매하는 거래: 콜옵션 / 풋옵션

- 거래소에서 표준화된 조건으로 거래되거나, 장외에서 비표준화된 조건으로 거래될 수 있음

예시

• 개인투자자: 1년 후의 코스피200 지수가 현재보다 하락할 것으로 예상하는 개인투자자는 코스피200 콜옵션을 매수하여 1년 후의 코스피200 지수 하락에 대비할 수 있음
• 기업 A: 1년 후의 원유 가격이 현재보다 상승할 것으로 예상하는 기업 A는 원유 풋옵션을 매수하여 1년 후의 원유 가격 상승에 대비할 수 있음

콜옵션(Call option)?

옵션거래에서 특정한 기초자산을 만기일이나 만기일 이전에 미리 정한 행사가격으로 살 수 있는 권리

예시 1:

기초자산: A 주식

행사가격: 10,000원

만기일: 2024년 3월 31일

프리미엄: 1,000원

투자자는 A 주식의 가격이 10,000원 이상으로 상승할 것으로 예상하여 콜옵션을 매수. 만기일에 A 주식의 가격이 12,000원이라면, 투자자는 행사가격인 10,000원에 A 주식을 매수할 수 있음. 이 경우, 투자자는 A 주식의 가격이 2,000원 상승한 만큼의 이익을 얻게 됨.

예시 2:

기초자산: 원유

행사가격: 100달러/배럴

만기일: 2024년 6월 30일

프리미엄: 10달러/배럴

투자자는 원유의 가격이 100달러/배럴 이상으로 상승할 것으로 예상하여 콜옵션을 매수. 만기일에 원유의 가격이 110달러/배럴이라면, 투자자는 행사가격인 100달러/배럴에 원유를 매수할 수 있음. 이 경우, 투자자는 원유의 가격이 10달러/배럴 상승한 만큼의 이익을 얻게 됨.

풋옵션(Put option)? 

옵션거래에서 특정한 기초자산을 만기일이나 만기일 이전에 미리 정한 행사가격으로 팔 수 있는 권리

*말장난 주의🚨: 풋옵션을 매수한다 = 미래에 팔 수 있는 권리를 사들인다

예시 1:

기초자산: B 주식

행사가격: 5,000원

만기일: 2024년 9월 30일

프리미엄: 1,000원

투자자는 B 주식의 가격이 5,000원 이하로 하락할 것으로 예상하여 풋옵션을 매수. 만기일에 B 주식의 가격이 4,000원이라면, 투자자는 행사가격인 5,000원에 B 주식을 매도할 수 있음. 이 경우, 투자자는 B 주식의 가격이 1,000원 하락한 만큼의 이익을 얻게 됨.

예시 2:

기초자산: 금

행사가격: 1,800달러/온스

만기일: 2024년 12월 31일

프리미엄: 100달러/온스

투자자는 금의 가격이 1,800달러/온스 이하로 하락할 것으로 예상하여 풋옵션을 매수. 만기일에 금의 가격이 1,700달러/온스가라면, 투자자는 행사가격인 1,800달러/온스에 금을 매도할 수 있음. 이 경우, 투자자는 금의 가격이 100달러/온스 하락한 만큼의 이익을 얻게 됨.

Refer to:

https://terms.naver.com/entry.naver?docId=300403&cid=43665&categoryId=43665

https://www.kcie.or.kr/mobile/guide/3/17/web_view?series_idx=&content_idx=942

https://terms.naver.com/entry.naver?docId=930829&cid=43667&categoryId=43667

https://jfinancediary.tistory.com/entry/%ED%97%A4%EC%A7%80%ED%8E%80%EB%93%9C

헤지(Hedge)

: '쐐기를 박다'

미래의 불확실한 사건으로부터 발생할 수 있는 손실을 미리 방지하기 위한 투자 전략

현물 가격 변동의 위험을 선물가격변동으로 제거하는 것 ('위험회피', '위험분산')

- 쐐기를 박아 가격이 움직이지 않도록 하는 것

- 헤지의 목적: 가격 변동에 따른 손실을 막기 위함 (투자수익을 안정적으로 유지)

- 헤지의 방법: 선도거래, 선물거래, 선물환거래, 옵션거래... etc.

1) 기초자산 매수: 위험이 상승할 것으로 예상되는 자산을 매수하여 위험을 상쇄하는 방법 (ex. 주식 가격이 하락할 것으로 예상되는 투자자는 주식을 매수하여 손실을 줄임)

2) 기초자산 매도: 위험이 하락할 것으로 예상되는 자산을 매도하여 위험을 상쇄하는 방법 (ex. 주식 가격이 상승할 것으로 예상되는 투자자는 주식을 매도하여 손실을 줄임)

3) 파생상품 거래: 기초자산의 가격 변동에 따라 수익과 손실을 얻는 금융상품을 활용하여 위험을 헤지하는 방법 

헤지펀드

: 위험 Hedge를 목적으로 설립된 펀드

- 사실상 주식, 채권, 파생상품, 실물자산 등 다양한 상품에 투자해 목표 수익 달성을 목적으로 함

- 소수의 투자자로부터 자금을 모집하여 운영하는 일종의 사모펀드(일반적으로 일반 투자자들에게 공개되지 않고, 소수의 전문 투자자들을 대상으로 운용됨)

- 단기이익을 목적으로 국제시장에 투자하는 개인모집 투자신탁으로, 투자지역이나 투자대상 등 당국의 규제를 받지 않고 고수익을 노리지만 투자위험도 높은 투기성자본

- 대표적인 헤지펀드 투자 전략: 롱숏 전략 

기초자산의 가격이 상승할 것으로 예상되는 자산(롱 포지션)을 매수하고,

하락할 것으로 예상되는데(숏 포지션) 사실 가지고 있지 않은 자산을 공매도(short selling)하는 전략

- 상대적으로 타이밍에 큰 영향을 받지 않음

"가격 떨어져라... 주가 떨어져라.. 제발 떨어져라... 🙏"

*공매도(空賣渡)? 

가치가 떨어질 것이라 예상되는 재화를 미리 빌려서(원래 내 것이 아님) 동일한 재화로 되갚기로 약속함

주식을 빌려서 주가 떨어지기 전에 팖(매도) → 주가하락 → 동일 주식을 떨어진 가격에 삼(매수)

- 빌린 재화를 현재 가격으로 팔고(공매도), 가치가 떨어졌을 때 해당 재화를 사들여서(매수) 되갚음

- 떨어진 가치만큼 수익이 발생함

- 즉, (예상대로) 주가가 떨어지면 수익 발생, (예상과 달리) 주가가 오르면 손실 발생

이외에도 헤지 펀드 전략에는

Global Macro 전략

: 경제/정치적 사건을 분석하여 투자 결정을 내림

Event-Driven 전략

: 기업합병/분할/재구조화와 같은 특정 이벤트에 초점을 맞춤

고정 수익 전략

: 채권과 같은 고정 수익 증권에 투자. 등이 있음

Refer to:

https://terms.naver.com/entry.naver?docId=300403&cid=43665&categoryId=43665

https://www.kcie.or.kr/mobile/guide/3/17/web_view?series_idx=&content_idx=942

https://terms.naver.com/entry.naver?docId=930829&cid=43667&categoryId=43667

https://jfinancediary.tistory.com/entry/%ED%97%A4%EC%A7%80%ED%8E%80%EB%93%9C

아래 글은 '우아한형제들'의 "요즘 우아한 개발(2023)"의 내용을 기반으로 작성되었습니다.

1. 이상 탐지

- 골자) '정상 패턴 vs 이상 패턴' 탐지

- 활용) 금융거래 사기 탐지, 제조공정 불량 탐지, 허위리뷰 탐지 등

2. 이상탐지의 두 유형

1) Rule-based: 쉽고 빠르게 서비스 적용, 탐지 근거 명확, unseen data나 아웃라이어에 robust하지 않음 

2) ML-based

- 지도 학습: SVM, LightGBM, ANN

- 비지도 학습: K-means, DBSCAN, AutoEncoder, Isolation Forest

- 준지도 학습: 적은 수의 라벨 데이터와 다수의 라벨링되지 않은 데이터를 모두 사용, 모델 성능 개선을 목적으로 라벨 데이터를 추가로 수집하여 업데이트 가능 (라벨 데이터가 너무 적은 경우 그것을 다량으로 확보하는 시간과 비용 vs 비지도에 따른 낮은 정확도)

3. 리뷰 조작 업체 탐지 모델 접근 방향

Step1) ML기반 Anomaly Detection (Anamoly ; 리뷰 조작 회원)

Step2) 소셜 네트워크 분석

Step3) 리뷰 조작 '업체' 탐지

Step1) ML기반 Anomaly Detection (리뷰 조작 '회원' 탐지)

SVDD → Deep SVDD → Deep SAD(준지도)

SVDD(Support Vector Data Description, with soft margin):

- 비지도 이상 탐지

- 흔히 아는 SVM과 유사

- 정상데이터와 이상데이터가 섞여 있을 때, 모든 입력 데이터를 커널 함수로 매핑하여 high dim에 매핑

- 새 mapping 공간에서, 정상 데이터가 최대한 구 안에 포함되도록 함 (이대 구의 중심과 반지름을 찾는 알고리즘)

이상 데이터는 최대한 구의 중심에서 멀리 떨어지도록 함 (soft margin: 구가 지나치게 커지는 것을 막음, 일반화)

- Detect 기준: 구의 경계면 내부에 있는지 외부에 있는지

Deep SVDD

- 비지도 이상 탐지 w/ DL

- SVDD의 커널 함수 대신, 딥러닝 기반으로 정상 데이터를 high dim space에서 최대한 중심으로 매핑시키도록 '학습' (특정 구를 정의하여 구의 중심과 반지름을 계산하는 것이 x, 정상 데이터들이 정상 데이터들의 대표 중심점에 최대한 가깝도록 매핑시킴)'

- DL for representation

- 정상 데이터들의 대표 중심점: Deep SVDD와 동일한 구조를 가진 AutoEncoder를 통해 미리 계산된 weight 사용

- weight regularization 적용

Deep SAD

- 준지도 학습 알고리즘

기본적으로 Deep SAD는 비정형 데이터인 이미지에서 이상을 탐지하는 CNN structure임
리뷰조작 회원의 데이터는 일정 단위로 집계한 정형 데이터
- 정형 데이터 to image 대신, CNN to 정형데이터에 이용 가능한 일반적인 오토인코더 구조로의 변환!

태스크와 데이터의 유형, 성격, 양, 질에 따라
- 기존의 알고리즘(모델 구조)를 변환하거나
- 데이터를 변환하는 과정이 필요

Step2) 소셜 네트워크 분석

가설: "조작 업체 특징을 고려하였을 때, 다량의 허위 리뷰 작성을 위해 다수 계정으로 유사한 가게에 허위 리뷰를 작성할 것이다"

Step1에서, Deformed Deep SAD 기반으로 Anomaly Detection 이후

→ 이상 회원(Anomaly)에 대해서만 네트워크 탐지 (이상리뷰가 작성된 가게 간 자카드 유사도 계산 - 두 집합 사이의 유사도 측정 가능)

→ 이때 스파크의 MinHash LSH 방법을 통해, 모든 이상 회원 pairs이 아닌, 자카드 유사도가 높은 원소를 동일한 버킷에 넣는 해시 알고리즘 사용하여 근삿값을 계산 (비용 및 시간 줄임)

→ 리뷰 작성 가게 간 자카드 유사도가 높은 경우에만 엣지로 연결하여 네트워크 찾음

→ 이렇게 형성된 네트워크에서 community detection 보다 더 강한 조건인 K-core decomposition 적용하여 그래프 내에서 응집도가 높은 그룹만 추출함 (오탐에 따른 문제 완화)

* K-core decomposition 주요 알고리즘: degree pruning, color-coding, and K-shell decomposition

refer to : https://www.baeldung.com/cs/graph-k-core

* 이상 스코어가 높을수록 약한 조건의 네트워크 탐지 / 낮을수록 강한 조건의 네트워크 탐지

Step3) 리뷰 조작 '업체' 탐지 → 검수 및 조치

위의 탐지 경과를 종합

조치를 통해 차단된 라벨 데이터를 저장하여 모델 재학습에 사용

B+ Tree

실제 데이터베이스의 indexing은 B+트리로 이루어져 있음

search에 있어서 매우~ 유리함.

- internal nodes: Index nodes (다음 노드를 가리킬 수 있는 포인터 주소가 존재)

- leaf nodes: Data nodes (실제 데이터)

1. 모든 key, data가 리프노드에 모여있음 (B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가짐)
2. 모든 리프노드가 연결리스트의 형태를 띄고 있음 (B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듦)
3. 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같음

*첫 번째 그림과 같이 leaf nodes가 linked list로 연결된 경우도 있음. 이 경우, 다른 leaf node에 접근하기 위해 다시 root를 방문하지 않아도 됨. 그러나 결국 background operation에 의한 비용을 감당해야하지만, 분명한 이득이 있음

Dis Friendliness of B+Tree

1. 페이지 기반 접근

B+tree는 데이터를 페이지 단위로 저장 (페이지는 일정한 크기의 데이터 블록)

페이지 기반 접근을 통해, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있음.

ex) 
데이터 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
이 데이터를 페이지 단위로 저장하면, 다음과 같이 3개의 페이지로 나눌 수 있음
```
페이지 1: 1, 2, 3
페이지 2: 4, 5, 6
페이지 3: 7, 8, 9, 10
```
이 경우, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있는데, 예를 들어, 데이터 2를 읽으려면 페이지 1만 읽으면 됨

2. 분산 저장

B+tree는 데이터를 루트 노드, 중간 노드, 리프 노드로 분산하여 저장함.

루트 노드는 메모리에 저장되고, 중간 노드와 리프 노드는 디스크에 저장됨.

루트 노드에는 데이터의 위치 정보가 저장되어 있기 때문에, 디스크에서 데이터를 찾을 때는 먼저 루트 노드에서 데이터의 위치 정보를 찾음.

예를 들어, 위의 데이터를 B+tree에 저장하면 다음과 같이 저장됨
```
루트 노드: 1, 4, 7
중간 노드 1: 2, 5, 8
중간 노드 2: 3, 6, 9, 10
리프 노드 1: 1, 2
리프 노드 2: 3, 4
리프 노드 3: 5, 6
리프 노드 4: 7, 8
리프 노드 5: 9, 10
```
이 경우, 디스크에서 데이터를 찾을 때는 먼저 메모리의 루트 노드에서 데이터의 위치 정보를 찾음. 데이터의 위치 정보를 찾으면, 해당 위치의 리프 노드에서 데이터를 찾을 수 있음.

3. 균형 잡힌 트리

B+tree는 균형 잡힌 트리이기 때문에, 데이터를 효율적으로 저장하고 검색할 수 있음. 균형 잡힌 트리는 트리의 높이가 낮기 때문에, 데이터를 찾기 위해 디스크를 읽거나 쓸 때 필요한 I/O 횟수가 적음.

출처

https://ssocoit.tistory.com/217

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

0. B Tree 시리즈의 효용에 대해서는 (아주) 간단히 아래 글에 정리해놓음

*하나의 노드에 여러 자료를 배치하며, 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담음

https://lets-hci-la-ai-withme.tistory.com/190

*일반적으로 이진트리를 다룰 때, 하나의 노드에는 하나의 데이터가, 둘 이하의 자식 노드.

B-Tree(비 트리)

'균형' 이진 탐색 트리의 일종- 그러나 자식 노드를 2개 이상 가질 수 있음

핵심 성질 1: 하나의 노드가, 최대 M개의 자식을 가질 수 있음 (M차 B-Tree)

*internal nodes는 모두 2개 이상의 자식을 가져야 함

핵심 성질 2: 하나의 노드 내에, 2개 이상의 key(데이터)가 저장될 수 있음

M차 B-Tree는,

1. internal nodes의 자식 개수: ceil(M/2) ~ M개 - M값과 자식 개수의 관계

2. 각 노드 내 key의 개수: floor(M/2)-1 ~ (M-1)개 (항상 정렬된 상태, 중복 허용x)  - M값과 k의 관계

3. 한 노드 key의 개수 k에 따라, 그것의 자식 노드의 개수가 k+1로 결정됨 - k와 자식 개수의 관계

4. 특정 노드의 left subtree는 특정 노드 내 '모든 keys'보다 작은 값으로, right subtree는 큰 값으로 정렬

5. 모든 leaf nodes가 같은 레벨에 존재함

1) Search가 아주 쉽다 (하향식)

2) Insertion은 좀 복잡하다 (하향해서 적당한 leaf 자리 찾은 후 '적절한 상태'가 되기까지 상향)

case1: 분리가 일어나지 않는 경우 (상향 불필요)

case2: 분리가 일어나는 경우 (상향 필요)

3) Deletion은 더 복잡하다...

아주 훌륭한 레퍼런스들,,

https://code-lab1.tistory.com/217

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

https://escapefromcoding.tistory.com/731

메모리 계층 구조

- 메모리 계층 구조: 메모리를 필요에 따라 여러가지 종류로 나누어 둠, 상단으로 갈 수록 CPU가 빠르게 처리, 적은 양의 데이터, 비쌈

- 목적: CPU가 메모리에 더 빨리 접근하기 위함

CPU 내부: 레지스터 & 캐시

CPU 외부: RAM(주 메모리), 하드디스크, ...

프로세서(CPU)-메모리(RAM) 격차

CPU는 짧은 시간 내 여러 연산을 빠르게 처리함

CPU가 아무리 빨라도, (CPU 외부로 가서) 데이터를 가져오고 저장하는 속도가 느리면 전체 속도는 느려짐

이같은 격차를 줄이기 위해, 메모리에 효율적으로 접근하는 방법을 고민 → RAM이 연산하는 횟수를 최대한 줄이자

→ CPU 내부 레지스터 용량을 늘리지 못해도

→ CPU와 통합될 수 있는 빠른 보조 메모리를 만들자 = L1, L2 캐시 (레지스터와 RAM 사이에 위치, 속도와 용량이 중간.)

- L1 캐시; cpu 레지스터의 캐시

- L2 캐시; L1 캐시의 캐시

메모리 계층은 왜 피라미드일까?: 시간, 공간 지역성(Locality)

시간 지역성 (temporal locality) : 어떤 메모리주소에 접근한 경우, 곧 똑같은 주소에 다시 접근할 가능성이 높음
공간 지역성 (spatial locality) : 어떤 메모리주소에 접근한 경우, 곧 근처 주소에 접근할 가능성이 높음

- '시간'과 '공간'을 기준으로 이후에 접근할 가능성이 높은 메모리 주소들을 찾아내기 - 각각 for문, array

- 조만간 접근할 가능성이 높은 메모리 주소들을 미리 예측하고, 그 주소들을 CPU 내부에 미리 저장

- 접근 가능성이 더 높은 메모리 주소의 데이터를, CPU의 레지스터와 더욱 가까운 곳에 임시로 저장해 둠

- CPU가 찾는 메모리: 레지스터 > L1 > L2 > RAM... 순으로 찾아봄

Cycle?

여기서 'cycle'이 무슨 뜻일까?

- 사이클이란, CPU가 하나의 명령어를 처리하는 데 걸리는 시간

- CPU가 원하는 데이터에 액세스하기 위해 "한 바퀴"를 몇 번 돌아야 하는지

CPU Cycle

| Fetch | 메모리에서 명령어를 가져오는 단계 |
| Decode | 명령어를 해석하는 단계 |
| Execute | 명령어를 실행하는 단계 |
| Write Back | 명령어의 결과를 저장하는 단계 |

CPU Cycle을 도서관에서 책을 찾는 과정에 비유하자면...

• Fetch 단계: 책을 찾기 위해 도서관에 들어간다.
• Decode 단계: 책의 제목을 확인한다.
• Execute 단계: 책을 꺼내 읽는다.
• Write Back 단계: 책을 제자리에 꽂는다.

CPU Cycle의 길이는 CPU의 종류, 클럭 속도, 메모리 속도 등 다양한 요인에 따라 달라짐

CPU time = Clock cycles x Clock cycle time

CPU time = {명령어 개수(instruction count) x  명령어 당 cycle 횟수(CPI)} x Clock Cycle Time

*명령어의 수와 명령어 당 cycle 수로 표현 → 결국 명령어의 수와 명령어당 cycle 수를 줄이는 게 핵심

*Clock(클럭)에 대해 알기 위해서는 우선 회로에 대한 기본적인 이해가 있어야 함

쉽게 비유해 보자면, 사람이 살아가기 위해 심장에서의 펌핑이 필요하듯이 CPU 동작에 필요한 전압이 펌핑되는 것이라 보면 됨.

High-Low 상태가 반복되며 주기적으로 반복되는 이 신호를 이용해 CPU는 연산을 수행할 수 있음.

*CPU time이 적을 수록, 짧을 수록 더 성능이 좋음. 푸드 파이터도 더 짧은 기록이 나올 수록 좋음. 그럼 시간을 줄이려면 어떻게 해야 할까? 공식에 비춰서 생각해 보면, clock cycle(씹는 횟수)를 줄이고, clock cycle time(한 번 씹을 때 걸리는 시간)을 줄여야 함. 그러나 이게 실제로 가능할까? 결론은 "쉽지 않다." 이유는 두 가지가 trade off 관계에 있기 때문.

출처: https://skyjwoo.tistory.com/entry/컴퓨터-구조-CPU-time [jeongstudy:티스토리]

B-Tree, B+ Tree의 효용

- 내부 기억장치인 레지스터와 캐시는 CPU와 밀접한 위치에 있어 빠른 속도로 데이터를 처리할 수 있고,

- 외부 기억장치는 대용량 데이터를 효율적으로 저장하고 관리할 수 있는 구조로 설계되어 있음

"왜 많은 데이터베이스에서 B tree를 근간으로 사용할까?"

만약 아주 큰 사이즈의 데이터가 들어온다면 (ex. 1TB) 보통의 주요 메모리(RAM)은 8~32GB이므로, 해당 데이터를 레지스터나 캐시나 RAM에서 처리할 수 없음.

결국 CPU로부터 더 먼(? 사이클 횟수가 큰, 오래 걸리는) Flash Disk(SSD)나 하드드라이브에 데이터를 저장하게 됨. 이때 하드디스크나 SSD와 같은 외부 기억장치는 블럭(chunk)단위로 파일을 입출력함

이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일함. (입출력에 있어 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭을 입출력하는 것과 차이 없음)

이때 하나의 블럭(chunk)에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용

=> B-트리, B+트리가 유용한 주요 이유

https://ssocoit.tistory.com/217 [코딩하는 경제학도]
Copyright © SsocoIT

refer to: https://joooing.tistory.com/entry/cs3

목적:  방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것

DP 스타일.

- 모든 SP는 negative cycle 이 없을 때만 수행 가능

- 벨만 포드는, 다익스트라와 달리, 그래프 내에 negative edge가 있더라도 실행 가능 (심지어 negative cycle의 유무를 detect)

- |V|-1까지 단계를 진행했을 때 'single source로부터 그래프 내 모든 node의 최단거리'가 확정됨! (|V| = G 내 노드 개수)

- 정점의 개수만큼 모든 간선을 Relax

Why |V|-1?

source 제외한 각 노드 (총 |V|-1 개)에 대해, 그래프 내 모든 edge에 대한 연산 수행해야 함.

연산량 무려 O(|V||E|)

결국 정해진 source에 대한 특정 노드까지의 최단거리를 구해야 하는데, 해당 최단 거리는 더 작은 최단 거리들의 합으로 구성되어 있음.

source로부터 가장 멀리 떨어진 노드 간 연결하는 edge 개수는, 최대 |V|-1 이고, 각각은 최단거리들의 합임 (마치 optimal substructure). 따라서 

=> 최악의 경우일 때, 순환을 포함해서는 안되므로(negative cycle은 불가능, non-negative cycle은 최단 경로로 포함될 수 없음) 최대 V개의 정점을 가지고, 그 때의 간선의 개수가 V-1기 때문

Relax?

- δ(s,v) : source -> v까지 실제 최단경로 비용

- d[v] : source -> v까지 추정 최단경로 비용 (그래프 노드 안에 적힌 값으로 표현, node.d)

Relaxation:  d[v]가 δ(s,v)의 상한이 되도록 유지하고 조정하는 함수, 궁극적으로는 d[v]가 δ(s,v)까지 줄어들도록 조정함

v까지 최단거리 발견하면 그걸로 다시 업데이트! 또 업데이트!!! 반복쓰 ~.

벨만포드 전체 알고리즘 !

- Bellman-Ford 알고리즘은 정점의 개수만큼 모든 간선을 Relax하기 때문에 엄청난 연산

- 덕분에 음의 가중치가 있는 그래프의 단일 출발지 최단경로를 구할 수 있고, 그래프가 음의 순환구조를 갖는다면 이를 식별할 수 있음

구체적인 예시:

https://victorydntmd.tistory.com/104

Time-Analysis?

line 1 : theta(|V|)

그래프를 초기화

d[s] = 0, d[v] = infinite

line 2 ~ 4 : O((|V|-1)*(|E|)) = O(|V||E|)

정점의 개수만큼 반복문을 돌면서, 모든 간선에 대해 Relax를 수행

line 5 ~ 8: theta(|E|)

음의 가중치를 갖는 순환경로가 존재하는지 확인

존재한다면 false를 반환하고, 존재하지 않으면 벨만 포드 알고리즘이 잘 작동했다는 true를 반환

출처: https://victorydntmd.tistory.com/104

https://jeonyeohun.tistory.com/96

https://velog.io/@cha-suyeon/%ED%98%BC%EA%B3%B5%EB%A8%B8-%EB%B0%B0%EC%B9%98%EC%99%80-%EB%AF%B8%EB%8B%88-%EB%B0%B0%EC%B9%98-%ED%99%95%EB%A5%A0%EC%A0%81-%EA%B2%BD%EC%82%AC%ED%95%98%EA%B0%95%EB%B2%95
 

 
- batch: 일괄적으로 처리되는 집단, 한 번에 여러 개의 데이터를 묶어서 입력하는 방식, 1 epoch당 사용되는 training dataset의 묶음
- epoch: 훈련 세트를 한 번 모두 사용하는 과정
 
일반적으로 우리가 말하는 SGD = mini-BGD를 일컬음
 
- SGD와 BGD의 절충안: Batch 보다 빠르고 SGD 보다 낮은 오차율을 가짐
- batch size: 하나의 mini batch에 들어가는 데이터 수 (prefer: 전체 데이터가 나눠떨어지는 값, 2^n)
- 1 epoch : 여러 개의 mini batch가 for문으로 돌고 돌아 전체 훈련 세트를 한 번 모두 사용하는 과정
 
 
https://welcome-to-dewy-world.tistory.com/86

그리고 필자는 처음에 미니배치를 공부할 때 수만건의 데이터 중에서 n개만큼의 데이터를 임의로 추출하기 때문에 당연히 복원 추출이라고 생각했는데 (왜냐하면 데이터 개수가 매우 많으면서 데이터 전체를 표현해야하기 때문에), Epoch의 개념에서는 전체 데이터셋을 사용해야 1Epoch가 된다는 것을 읽으며 골머리를 앓았다.
배치, 혹은 미니배치학습을 할 때 배치는 복원 추출인가? 비복원 추출인가?
 
이에 대한 해답을 정확히 알 수는 없었으나, 어쨌든 복원 추출이나 비복원 추출이나 사실상 크게 다르지 않다는게 결론이다. 이에 대한 이유는 데이터가 매우 많기 때문이다. 수많은 데이터 중에서 임의의 개수로 임의의 데이터를 추출하는 것을 n번 반복하면 사실상 비복원 추출이나 복원 추출이나 전체 데이터셋을 사용한다고 볼 수 있기 때문이다.
 
https://light-tree.tistory.com/133

'batch' 라는 단어는 엄밀히 'mini-batch'를 의미하지면 편의상 batch 와 혼용해서 사용하는 것.
처음엔 '한 개의 데이터마다 한 개의 기울기를 구할 수 있는데, 어떻게 전체 데이터 셋에 대해서 기울기를 한번만 구한다는 것인가?' 라는 의문을 가지며 BGD를 잘못 이해하고 있었다.
 
Gradient descent 라는 알고리즘 자체는 loss function 을 입력 데이터 x 에 대해 편미분해서 기울기를 계산하는 것이 아닌, 가중치 w 에 대해서 편미분을 하는 것이기 때문에, 기울기를 계산하는 것 자체는 입력 데이터 x 의 갯수와 상관이 없다.
 
에러값을 전체 데이터에 대한 loss function 의 합으로 정의하던 평균으로 정의하던 단순히 w 에 대한 편미분을 수행하면 되는 것.
 

출처: https://light-tree.tistory.com/133 [All about:티스토리]
 
 

https://ratsgo.github.io/deep%20learning/2017/10/02/softmax/

Backprop의 모든 것...🤩
 

0과 1의 세상

- 컴퓨터는 0 또는 1이라는, 2진수 형태(binary)로 이해함

- 기본적으로, Byte(8개 단위의 Bit)를 사용함 

1비트: (0, 1) → 2^1

2비트: ((0, 1), (0, 1)) → 2^2 가지

3비트: 2^3가지

...

8비트: 2^8가지 = 256의 경우의 수

1 byte = 8 bits

1 KB = 2^10 bytes

1 MB = 2^10 KB = 2^20 bytes

1 GB = 2^30 bytes

1 TB = 2^40 bytes

1 KB부터는 2^10 배로 단위가 커짐!

refer: https://mindnet.tistory.com/entry/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-1%ED%8E%B8-Bit-%EC%99%80-Byte-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://semiconductor.samsung.com/kr/support/tools-resources/dictionary/bits-and-bytes-units-of-data/

Data Types

char: 1 byte → express 256 values

short: 2 bytes

int: 4 bytes (32 bits) 

long: 8 bytes (64 bits)

string: an array of chars = an array of bytes(each byte: 0~255)

ASCII 코드

- 결국 컴퓨터는 모든 것을 0과 1의 조합(binary)로 읽음

- 컴퓨터에서 문자(영어 알파벳 / 숫자 / 특수 문자 / 제어 문자 / 공백 문자)를 binary로 표현하기 위한 표준 코드

- 문자와 binary를 일대일로 매핑 → 7비트(128가지) 또는 8비트(256가지)의 binary로 표현

- 아스키코드에서 10진을 보면.. 우리가 이해하기 더 쉬움.

아무튼 127까지 있는 걸 보니 문자를 7 bit로 할당(128가지의 문자를 binary로 매핑)