Ensemble Learning이란?

여러 개의 base-learner(base-model)를 조합하는 모델

Bagging

- 다른 이름: Bootstrap Aggregating

- Bootstrap: Random Sampling 방법론 중 하나. 복원 추출을 시행한다.

- 복원 추출을 통해 동일한 크기의 데이터셋을 여러 개 생성한 후, 앙상블을 구성하는 학습 방식

- 단점: 랜덤 샘플링은 운에 의존한다.

만약, decision tree를 학습시킨다고 가정해보자.

boostrap으로 데이터를 추출할 경우, 복원 추출이기 때문에 같은 데이터가 여러 번 뽑힐 수 있고, 그렇기 때문에 데이터셋끼리 유사하다. 그러므로 이런 경우 decision tree의 root node는 모델 간에 항상 비슷해질 수밖에 없다. 

Boosting

- Bagging과 같은 방법이 randomness에 의존한다는 단점을 보완하기 위해 고안된 방식

- 전체 데이터셋을 3개로 분할한다. (D1, D2, D3)

- 학습 방식

base-learner를 3개 학습시킨다.

1. h1을 D1으로 학습시킨다.

2. h2를 D2 중 h1이 틀렸던 문제 + 맞았던 문제 같은 비율로 구성된 데이터셋으로 학습시킨다.

3. h3을 h2가 틀렸던 문제 데이터셋으로 학습시킨다.

- 예측 방식

h1(x)=h2(x)라면, h1(x)를 반환.

아니라면 h3(x)을 반환. => 틀렸던 문제만으로 학습된 모델이므로 가장 맞을 확률이 높다.

Statement = Proposition : 명제

- 정의: 참이나 거짓으로 판단할 수 있는 문장

- 종류

1) Universal Statement: 한 집합의 모든 요소에 대해서 참

2) Conditional Statement: 특정 조건만 포함

3) Existential Statement: 조건을 만족하는 요소가 1개 이상 있다.

4) Universal Conditional Statement: universal & conditional

5) Universal Existential Statement: 첫 부분은 universal, 두 번째 부분은 existential

6) Existential Universal Statement: 첫 부분은 existential, 두 번째 부분은 universal

Set : 집합

- 정의: 특정 조건을 만족하는 요소들의 모임

- ex) { x | 0 < x < 5 }

Russell's Paradox

R = {x | x is a set and x is not an element of itself}

정의에 따르면 R이 R의 요소라면, R은 R의 요소일 수 없다.

또한, R이 R의 요소가 아니라면, R은 R의 요소이다.

-> 모순적

Cartesian product

A X B : Cartesian product of A and B

B X A : Cartesian product of B and A

정의: A X B = {(x, y) | x is a member of A, y is a member of B}

ex) A = {1, 2} / B = {3, 4} -> A X B = {(1,3), (1,4), (2,3), (2,4)}

Relation

- 공집합이 아닌 집합 A에 대해 A에 대한 relation = A X A의 subset

- 종류

1) Reflexive

ex) A = {1, 2, 3, 4}일 때

R1 = { (1, 1), (2, 2) } 라면, 이 집합은 Reflexive하지 않다.

이유: (3, 3), (4, 4)가 없다.

R2 = { (1, 1), (2, 2), (3, 3), (4, 4), (2, 3) } 라면, 이 집합은 Reflexive하다.

이유: (1, 1)~(4, 4)가 모두 있다. (2, 3)은 상관이 없다.

2) Symmetric

ex) R3 = 공집합이라면, 이 집합은 Symmetric하다.

이유: 집합에서 요소들의 쌍이 없기 때문에

R4 = { (1, 2), (2, 1), (2, 2) } 라면, 이 집합은 Symmetric하다.

R5 =  { (1, 2), (2, 1), (2, 3) } 라면, (3, 2)가 없어 Symmetric하지 않다.

3) Transitive

R6 = { (1, 5), (5, 1), (1, 1) } 이라면 만족할 수 없다.

(1, 5), (5, 1) -> (1, 1) 이지만

(5, 1), (1, 5) -> (5, 5)도 있어야 하는데 없다.

Greedy Best-First Search

Evaluation Func & Heuristic Func

1. Evaluation func f(n)
   1. node n의 estimated cost
2. Heuristic func h(n)
   1. node n에서 goal state로 가는 가장 저렴한 비용의 추정치
   2. root-finding problem에서 각 도시별 직선거리 함수

Greedy Best-First Search

1. 정의: best-first search의 일종 → h(n) value가 가장 적은 노드를 확장
   1. table을 유지하는 경우 그래프 (중복을 고려)
   2. 없애는 경우 tree search (중복을 고려하지 않음)
2. 성능 평가
   1. Completeness → 사이클 발생
      1. Not complete: tree-like search
      2. complete: graph search
   2. Not cost-optimal
   3. Time Complexity: O(b^m)
   4. Space Complexity: O(b^m)

A* Search

1. 정의: f(n) = g(n) + h(n)을 evaluation function으로 이용
   1. g(n): n까지 오는 데 비용
   2. h(n): n부터 goal까지 가는 데 추정되는 비용
2. Admissible Heuristic Function
   1. goal에 도달하기 위한 비용을 절대 overestimate하지 않음
   2. h(n) <= h*(n) : h(n)은 실제 값
   3. admissible heuristic function을 이용한다면 A* search는 cost-optimal하다.
3. Consistent Heuristic Function
   1. consistent: 모든 노드 n과 a라는 행동으로 생성된 자식 n’이 있을 때
   2. h(n) <= c(n,a,n') + h(n') 성립
   3. consistent heuristic function을 이용한다면 A* search는 cost-optimal하다 → 모든 consistent heuristic은 admissible하다.
4. Search contours
   1. A*는 가장 적은 f-cost를 가진 frontier 노드를 확장하므로 등고선이 커지면서 cost가 점점 커지는 형태이다.
   2. 좋은 휴리스틱을 가졌다면, 등고선은 점점 goal state에 가까워질 것이며 최적 경로에 가까워질수록 더 좁아질 것이다.
5. Optimally Efficient → C* : optimal cost
   1. surely expanded: f(n)<C*
   2. depends: f(n)=C*
   3. never expended: f(n) > C*
6. Weighted A* Search
   1. 정의: C와 WC*사이의 cost를 가지는 해답을 찾는 것
   2. f(n)=g(n)+W*h(n)
   3. Suboptimal search techniques
      1. bounded suboptimal search: 실제 optimal cost의 1/2배 ..
      2. bounded-cost search: 실제 cost는 모르고 얼마 안에 도달하는 경로 찾기
      3. unbounded-cost search
      4. beam search: 메모리는 적게 유지 → 가장 좋은 score인 것만 유지하고 나머지는 가지치기
7. 성능 평가
   1. Complete
   2. Cost-optimal
   3. Time-complexity <= O(b^d)
   4. Space complexity <= O(b^d)

Iterative-Deepening A* Search

1. 정의 (IDA*)
   1. iterative deepening search + A* Search
   2. 이전 반복에서 cutoff를 초과하였던, f-cost가 가장 작은 임의의 노드를 cutoff → 기준보다 크지 않았다면 계속 내려감
2. 특징
   1. f-cost가 모두 정수일 때 잘 작동
   2. f-cost가 모두 다른 노드일 때, 반복 숫자가 결국 state수와 같아질 수 있다.

Recursive Best-First Search

1. 정의 (RBFS)
   1. recursive depth-first search + best-first search
   2. f-limit을 현재 노드가 초과한다면 다시 감아 내려가서 alternative path로 이동
2. 진행 과정
   1. 일단 처음 limit = 무한대
   2. 다음 경로 중 가장 작은 cost인 쪽을 선택, limit은 두 번째로 가장 작은 값으로 변경
   3. 내려가서 limit과 cost의 값을 비교 → cost가 limit보다 크면 해당 cost를 limit으로 변경하고, limit과 같은 cost를 가졌던 node를 확인
3. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(bd)
      • 지나치게 적은 메모리 사용 → 계속 같은 state를 반복하여 탐색

Simplified Memory-Bounded A* Search

1. 정의
   1. A* search를 메모리가 꽉 찰 때까지 진행
   2. 메모리가 꽉 찼다면 f-cost가 가장 큰 worst leaf node를 버림
   3. 잊어버린 노드의 값을 다시 부모에게 전달
2. 성능 평가
   1. Complete
   2. Cost-optimal
   3. time complexity <= O(b^d)
   4. space complexity <= O(b^d)

Example Problems

1. Robotic Vacuum Cleaner
2. 8-Puzzle
3. 8-queens
4. Route-finding problem

Solving Problems by Searching

용어 정의

1. Problem formulation: 어떤 고려할 state, action을 결정할지 정하는 프로세스 → 목표는 주어져 있음
2. 문제는 state space, initial state, goal state, action, transition model, action cost function으로 구성
3. action의 연속은 path를 구성
4. solution: initial state→goal state로 가는 path
5. optimal solution: path cost가 가장 적은 해답
6. search: 목표에 도달할 수 있는 행동의 연속을 찾는 것
7. execution phase에서 행동을 한 번에 한 개씩 찾아낼 수 있다.

Abstraction

1. 정의: 표현에 필요 없는 디테일은 감추는 것
   1. Useful abstraction
   2. Valid abstraction
   3. level of abstraction

State space

1. 정의: 환경이 처할 수 있는 가능한 state의 집합
2. 그래프로 표현: vertices → state, edges → actions
3. solution

Search Tree

1. Node expansion: Node generation, parent / child / successor node
2. reached state: 해당 state에 맞는 노드가 생성된 상태
3. frontier: unexpanded node의 집합
4. redundent path and cycle 신경쓰면 → graph search, 아니면 → tree-like search

탐색 전략 및 성능 평가

1. 탐색 전략
   1. FIFO
   2. LIFO
   3. Highest priority first
2. 성능 평가
   1. completeness
   2. cost optimality
   3. time complexity
   4. space complexity

Task Environment의 특징

• Task environment: 성능평가, 환경, actuator, sensor
• fully observable, partially observable, unobservable ⇒ sensor
• deterministic, nondeterministic, stochastic ⇒ transition model
• discrete, continuous ⇒ state, action, sensor, time
• known, unknown ⇒ laws of physics
• single, multiagent ⇒ agent
• episodic, sequential ⇒ dependency
• static, dynamic, semi-dynamic ⇒ state and action
• fully observable, deterministic, known environment → solution = fixed sequence of actions

Uninformed Searches

Breadth-First Search

1. 정의: 루트 노드가 가장 먼저 확장되고, 루트 노드의 자식이 확장되고, 그 다음 그들의 자식이 확장되고… 하는 식
2. 수도코드 특징
   • IsGoal 함수: frontier에 FIFO queue를 사용
   • reached: 노드가 생성되면 reached list에 저장
3. 성능 평가
   1. Complete: 유한한 branching factor, 유한/무한 state space
   2. Cost optimal하지 않음
   3. time complexity: O(b^d) → b: branching factor, d: 가장 얕은 해
   4. space complexity: O(b^d)
   5. 답이 있으면 무조건 찾을 수 있다.

Uniform-Cost Search

1. 정의: 가장 적은 path cost g(n)을 가진 노드 n으로 확장
2. 수도코드 특징
   • reached: lookup table → key problem.Initial & value node
   • child.PathCost < reached[s].PathCost : 방문은 이미 한 상태에서 비교만
   • late goal test
3. 성능 평가
   1. Complete: 모든 cost가 양수라는 조건이 있어야 함
   2. Cost-Optimal
   3. Time complexity: O(b^{1+\lfloor{C/\epsilon}\rfloor})
   4. Space complexity: O(b^{1+\lfloor{C/\epsilon}\rfloor}) → C*: optimal solution의 cost
4. 하나만 선택하려면 time보다는 space를 줄이는 것이 필요

Depth-First Search

1. 정의: Frontier에 있는 가장 깊은 노드를 확장
   • backing search: 단 1개의 successor만이 생성됨 → 부분적으로 확장된 노드는 다음 번에 확장될 노드에 대해서 기억
   • 새로운 메모리를 할당하는 것보다 현재 상태 설명을 직접 변경함으로써 successor 생성 → backtrack이 가능하게 하기 위해서는 되돌리는 것이 가능해야 함
2. 성능 평가
   1. Completeness
      • not complete: infinite state space, tree-like search
      • complete: finite, graph
   2. Not cost-optimal
   3. Time complexity: $O(b^m)$ → m: 트리의 최대 깊이
   4. Space complexity
      1. O(b^m): graph search → backtracking 정보를 유지해야 하므로
      2. O(bm): tree-like search → 트리 서치를 하면 complete해지지 않으므로
      3. O(m): backtracking search

Depth-Limited Search

1. 정의: depth limit l이 정해져 있음 → 깊이 l인 노드의 경우는 successor가 없는 것처럼 취급
2. 수도코드 특징
   1. result ← cutoff
3. 성능 평가
   1. Not complete
   2. Not cost-optimal
   3. time complexity: $O(b^l)$ → l: depth limit
   4. space complexity: $O(bl)$ → 방문한 노드 리스트를 유지하지 않으므로

Iterative Deepening Search

1. 정의: depth-limited search + increasing limits
2. 성능 평가
   1. Complete
   2. Not cost-optimal
   3. Time complexity: O(b^d)
   4. Space complexity: O(bd) → 메모리 절약
3. 특징
   1. depth first search와 breadth first search의 장점을 모두 포함
   2. hybrid approach로 이용 가능
   3. state space가 메모리 크기보다 크고 depth가 알려지지 않았을 때 이용
   4. Iterative lengthening search: cost가 모두 동일한 것이 아니라면 cost가 커지는 방식으로 deepening

Bidirectional Search

1. 정의: 2개의 frontier로 확장 → 1개는 initial state, 1개는 goal state → 중간에서 만나기를 기원
2. 수도코드 특징
   1. solution 선택 시 어떤 방향이 가장 비용이 적을지 판단하여 그것을 선택함
   2. proceed 함수: 상대방의 reached state 정보를 받아서 실행
3. 성능 평가
   1. Complete
   2. Not cost-optimal
   3. time complexity: O(b^{d/2})
   4. space complexity: O(b^{d/2})

Big Data Intro

- 2003년 전까지 5 엑사바이트의 정보를 생산했음

- 이제 이틀마다 5 엑사바이트의 정보를 생산 -> 빅데이터

Big Data의 4V

- Volume

- Variety

- Velocity

- Veracity

Science Paradigms

- 몇천 년 전: 과학은 empirical 했다. -> 자연 현상을 서술

- 몇백 년 전: theoretical branch -> 이론, 모델링

- 몇십 년 전: computational -> 시뮬레이션

- 오늘날: data exploration

- 미래: Data-driven Science -> Data-driven Hypothesis Generation

Big Data Challenges

- 빅데이터

* 크고 복잡한 데이터

* 예: social, web, financial transaction data, academic articles, genomic data...

- 2가지의 고난

* 효율적 저장 및 접근

* Data Analytics -> 가치 있는 정보 캐내기

Data Science and Big data

- 빅데이터라는 용어는 거대한 데이터셋의 분석을 뜻함

- 예: 트위터/페이스북 전체, 주요 사이트의 웹 로그, 몇천 명의 genome sequence, Flickr의 전체 이미지...

- 크기가 커지면 데이터를 다루기 더 어려워진다

Big data as Bad data

- Unrepresentative participation (bias): 인스타그램-젊은 층만 이용, 뉴욕타임즈-자유주의적, Fox News-보수적, 월스트리트저널-부자만 봄

- Spam and machine-generated content: 봇, 가짜뉴스 등 

- Power-laws: redundancy를 의미 -> 건물 탐지 태스크를 수행할 때, 랜드마크 데이터는 많으므로 랜드마크만 잘 인식하고 일반 건물은 잘 인식하지 못할 수 있음

- Susceptibility to temporal bias (ex. Google Flu Trends): 구글의 자동완성 기능이 검색 쿼리의 분포를 변화시킴

Large-Scale Machine Learning

- 우리가 지금까지 공부한 알고리즘들은 아주 큰 데이터셋에 잘 맞지 않는다.

- 아주 큰 데이터셋에 대해서는 파라미터가 적은 모델이 잘 작동하지 않는다.

- 알고리즘의 시간복잡도가 linear -> O(n)이어야 한다.

- Big matrices는 빅데이터에 대해 희소할 수 있다.

* 예) 넷플릭스 고객 1억명을 대상으로 전체 영화에 대한 유저 평점 matrix를 분석한다고 했을 때 차원이 아주 크고 희소하다.

-> 모든 사람이 모든 영화를 보지는 못하기 때문에

Filtering Data -> domain specific criteria

- 빅데이터의 장점은 분석을 더 깔끔하게 하기 위해서 빅데이터의 상당 부분을 버려도 된다는 것이다.

- 예: 트위터의 전체 트윗 중 34%만이 영어권 계정 -> 나머지는 버려도 됨

- irrelevant or hard-to-interpret data를 필터링 하는 것은 application-specific knowledge를 필요로 한다.

Subsampling Data

- subsampling...?

* training/validation/testing data를 깔끔하게 분리할 수 있다.

* 단순하고 튼튼한 모델은 파라미터가 적음 -> big data의 overkill 유도

cf) hyperparameter fitting, 모델 선정->여러번 학습

* 스프레드시트 사이즈의 데이터셋은 분석이 쉽고 빠르게 된다.

절단(truncation)을 이용하기

- 첫 n개의 기록만을 취하는 것은 쉽지만 여러 오류를 범할 수 있다.

* temporal biases (오래된 데이터만을 분석하게 될 수도)

* lexicographic biases (A에 대한 데이터만 분석하게 될 수도 -> Arabic은 분석범위에 있지만 Korean은 포함되지 않을 수 있다)

* numerical biases (ID 번호 같은 건 무작위 부여가 아니라 의미가 있는 숫자일 수 있음)

Stream Sampling

- n을 모를 때 size k 짜리 균일 샘플을 추구할 때가 있다.

- 해결책: k개의 active element에 대한 배열을 유지하고, n번쨰 요소를 k/n의 확률로 대체 -> 들어왔던 것도 쫓겨날 수도 있음

- cut을 만들 때 새로운 요소의 위치를 랜덤으로 선정할 수 있음.

Distributed vs. Parallel Processing

- Parallel processing: 1개의 기계에서 진행 (스레드, 운영체제 프로세스 등을 통해)

- Distributed processing: 여러 개의 기계에서 진행 - 네트워크 통신 등을 이용

Data Paralllelism

- parallelism을 이용하는 방법은 빅데이터를 다수의 기계로 나눠 독립적으로 모델을 학습시키는 것이다.

- k-means처럼 각각의 결과를 합치기가 어렵다.

* Parallelized K-means

예를 들어 100개의 seed가 있는 상황이라고 하면

1. 1개의 master machine (job assign...)이 k개의 random seed를 선정해서 다른 machine에게 broadcast

2. local에서, 각 machine은 자신이 가진 데이터가 어느 클러스터에 속하는지 계산한다.

3. 그 데이터로부터 새로운 centroid, data #를 계산하여 전달한다. (sum vector 등의 형태로 전달하면 일일이 전달할 필요가 없다)

4. master machine이 그 정보를 전달받아 centroid 값을 최종적으로 업데이트하고, 이를 다시 broadcast한다.

5. 계속 반복한다.

Grid Search

- 정의: right hyper-parameter를 찾는 것

- 예: k-means clustering에서 올바른 k값을 찾는 것

- parallel하게 실행될 경우 최적의 값을 찾아낼 수 있다.

Distributed processing의 복잡도

- machine 수에 따라 급격하게 증가한다

* 1개: 나의 box의 중심부를 바쁘게 함

* 2개: 몇 개의 box에 대해 프로그램을 실행시킨다.

* 여러개: MapReduce 등의 시스템을 이용하여 효율적으로 관리할 수 있다.

MapReduce / Hadoop

- distributed computing을 위한 구글의 MapReduce 패러다임은 Hadoop, Spark 등의 오픈소스로 구현됨

- 간단한 parallel programming model

- 수백/수천 개의 기계에 대해 Straightforward scaling

- redundancy(여분)을 통한 fault tolerance

Divide and Conquer

1. 분할(partition): 하나의 일을 여러 개로 쪼갬

2. 각각 수행

3. 병합(combine): 각각의 결과를 하나로 합침

Typical Big Data Problem

- 아주 큰 숫자의 기록을 반복

- 각각에서 관심있는 것을 뽑아내기

- 중간 결과를 shuffle, sort

- 중간 결과를 집합

- 최종 결과를 도출

- word counting, k-means clustering을 생각해보기

MapReduce의 아이디어

- Scale Out: 여러 개의 기계를 붙이기 (up-> 기계 성능 장체를 올리는 것->X)

* 스케일 업은 메모리 bottleneck 현상 등이 발생할 위험이 있다.

- Move processing to the data: 클러스터들이 제한된 bandwidth를 가진다

- 순차적으로 데이터를 처리하고, 랜덤 접근을 피하라: seek은 비용이 많이 들지만, disk throughput은 합리적

* HDD 등에서 데이터를 읽을 때 head를 이동해가며 읽는다. 이것을 어떻게 최적화하느냐?

Components of Hadoop

1. Hadoop/MapReduce

- 분산된 빅데이터 처리 인프라구조

- abstract/paradigm

- fault-tolerant: 데이터를 100개로 나누어주는데, 그중 1개의 처리기가 고장나면 일단 재시작부터 함 -> 그래도 동작하지 않을 경우 다른 처리기에게 할당

- schedule: job assignment 등을 조율

- execution

2. HDFS (Hadoop Distributed File System)

- fault-tolerant: 하드디스크가 망가져도 괜찮음

- high-bandwidth

- high availability distributed storage

- 최소 3개의 복사본은 유지

MapReduce Word Count

- Map and Reduce 함수

map(k,v) -> [(k', v')]
reduce(k', [v']) -> [(k',v')]

- Word Count

Map(String docid, String text):
    for each word w in text:
    	Emit(w, 1);
Reduce(String term, Iterator<int> values):
    int sum = 0;
    for each v in values:
    	sum += v;
    Emit(term, sum);

MapReduce 실행 시간

- scheduling 조절: map, reduce task를 수행하도록 worker에 부여

- 데이터 분산 조절: 프로세스에서 데이터로 이동

- synchronization 조절: intermediate data의 수집, 정렬, 혼합

- error, fault 조절: worker failure 감지 및 재시작

Hadoop Distributed File System (HDFS)

- 클러스터 내부의 노드의 local disk에 데이터 저장 -> 메모리의 모든 데이터를 갖고 있을 RAM이 충분하지 않음

- Disk access는 느리지만 disk throughput은 합리적 -> file을 통한 linear scan은 괜찮음

- 모든 데이터를 3번 복제 -> reliability on commodity hardware

Cloud Computing Services

- Amazon 등의 플랫폼은 단기 작업에 대한 여러 machine 제공 가능

Feel Free to Experiment: micro instance의 경우 해볼 만함