sarah0518

기존 indexing의 문제점 high dimensional data에서는 기존의 indexing 기법이 잘 적용되지 않음 비슷한 데이터의 grouping이 힘들게 됨 → 겹치는 데이터가 많아짐 → 차원의 저주 M-tree(Metric indexing) 직접 grouping하는 것이 아니라, 거리를 계산하여 거리기준으로 grouping 하는 것 (distance based indexing) 따라서 차원에 대해 independent한 indexing을 설계 할 수 있음 metric space metric space에 존재한다고 하려면 아래 조건을 만족해야함 도로망 같은 경우는 metric space의 조건을 만족하지 않음 A보다 B도로가 더 길 수 있음 M-tree 특징 차원의 저주에 dependent 하..

DQN이 등장하게된 배경 Q table로 해결하기 어려운 것 when the number of states is too large. → 계산하기가 매우 복잡해짐 위의 벽돌상태를 (깨진것, 안깨진것) 0,1로 표시하고 공의 위치를 0/1로 표시하면 너무 많은 조합이 있음 → 해결책 ) 이미지 자체를 input으로 사용하자. 단, 순간의 이미지를 캡쳐하므로 공의 방향을 알기 어려움 → 해결책 ) time-series 4개의 이미지를 연속해서 가져옴 하지만 또 너무 많은 조합 → DQN을 사용하자. DQN 정의: Q table을 함수화하여 input을 state로 정하고 output을 각 action에 대한 Q-value로 하는 것 Understanding DQN - supervised learning을 사용..

** policy가 정해진상태에서 V, Q 구하는 것 = prediction ** policy를 정하는 것 = control 1. Temporal Difference Learning - TD Prediction Monte Carlo method의 단점 episode가 너무 길거나, 끝나지 않는 episode이면(continuous tasks) return값을 계산할 수 없으므로 temporal difference learning을 사용함 Monte Carlo method의 장점 현실은 dynamic programming을 쓸 수 없는 경우가 많다(model-free method 필요) Dynamic programming의 장점 bootstrapping을 사용하여 episode가 끝날때까지 기다리지 않아도..

Range query index없이 모든 point들을 다 살펴보는것은 효율적이지 않음 반면, R-tree의 범위 질의를 통해 빠르게 query에 답할 수 있음 aggregation query: 특정 범위내에 있는 값에대해 집계처리(count, sum, avg, min, max)의 결과를 return하는 것 Straightforward approach: reduce to a range query. Better approach: along with each index entry, store aggregate of the sub-tree. 노란색 처럼 각 노드에 count 값을 미리 가지고 있음 Nearest Neighbor (NN) Query eg) Given a query location q, find ..

R-tree (Rectangle tree) 각 노드가 최소 50%이상 사용되도록 하는 트리 insert와 split이 수월하다 query수행 시 MBR을 사용한다. DISK 기반의 TREE임 (A multi-way external memory tree) 현재 가장 많이 사용하는 TREE HEIGHT(level)이 균일하므로 DISK I/0가 균일하게 발생함 하나의 노드는 최소 m개의 entry가, 최대 M개의 entry를 가지도록 제한됨 단, root 노드는 최소 2개의 entry(children)를 가질 수 있음(한개도 괜찮음) m과 M에 대한 예시 ** mbr의 grouping의 결과를 tree 구조로 나타낸 것임 ** 일부분이 걸쳐있는경우에는 포함이 안됨 (P3에 H는 포함 안됨) ** F = 4 ..

퍼셉트론 학습이란? 훈련집합이 주어졌을 때, 옳게 분류하는 퍼셉트론 (weight, bias)를 찾는 것 input layer, output layer 2개만 있음 입력층: d+1 (bias포함) 노드 출력층: 1개 노드 (2 class 분류기 일때) 이 외에도, 가중치 & 활성 함수 필요 아래 내용 풀어보기 패턴 인식에서 일반적인 학습 알고리즘 설계 과정  단계 1: 분류기 구조 정의와 분류 과정의 수학식 정의  단계 2: 분류기 품질 측정용 비용함수 J(Θ) 정의  단계 3: J(Θ)를 최적화하는 Θ를 찾는 알고리즘 설계 목적함수 분류기 품질을 측정하는 것 오분류라면 true answer와 prediction의 부호가 다르게 되고 위의 목적함수에서 보다시피 두 값을 곱하게 되면 오분류의 경우 항..

z-ordering tree z-ordering tree는 linear quadtree처럼 MBR을 사용하지 않음 z-odering tree는 최대 degree인 d를 설정하고 시작함 d=3이므로 4^3 = 64의 격자로 쪼개짐 위와 같이 degree=3 이므로 최대 3개의 digit을 갖는 index로 표현할 수 있음 단, 03처럼 030,031,032, 033이 모두 포함되면 그냥 03으로 표기함 그 다음 object가 겹치는 index의 집합을 구성함 ** linear quadtree 와 z-ordering 차이를 알기! 단점. 여전히 duplication이 많이 발생함 z-order tree에서의 rectangle 찾기 파란점 = 012, 빨간점 121 indexing을 하면 012(파랑)부터 시..

Importance의 필요성에 대해 이 전 글에서 언급했던 내용을 다시 복습해보면 아래와 같다. off-policy의 단점: 한번 try했던 policy가 가장 best임에도 불구하고, random하게 생성된 policy로 진행이 되어 이전 best policy에 대한 가치를 제대로 반영 하지 못함 → randomly하게 선택했을 때의 distribution과(behavior policy) 목표하는 것의 distribution(target policy)이 일치 하지 못할 때 → 해결책: importance sampling을 사용하여 해결함 the importance sampling ratio The relative probability of the trajectory under the target and..