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의 경우 해볼 만함

머신러닝 모델의 비교

- Power, expressibility: 얼마나 복잡한 작업을 할 수 있느냐

- Interpretability

- Ease of Use

- Training speed

- Prediction speed

cf) 딥러닝은 Foward Fast를 이용한다. Nearest Neighbor는 거리 계산 때문에 연산 시간이 길다.

XOR & Linear Classifier

- Linear Classifier는 XOR 같은 간단한 비선형함수를 적합시킬 수 없다.

- 대안: Decision tree, Random forest, Support Vector Machines, Deep Learning

Decision Tree Classifier

- root->leaf path를 통과하면서 분류가 되는 모델

- 트리는 학습 예시들을 비교적 균일한 구성으로 분해

- Top-down manner로 구성

- m개의 클래스들에 대한 정보를 정제하기 위해 1개의 피쳐/차원을 따라 분리

* pure split: 1개의 단일 클래스 노드 생성 

* balanced split: group 크기가 대략적으로 비슷하도록 항목을 분리

Information-Theoretic Entropy

- entropy: class confusion의 양을 측정

Split Criteria

- information gain

gain(D, A_i) = entropy(D)-entropy_{A_i}(D)

- 이용: 데이터 칼럼별로 계산해서, 가장 값이 큰 것을 선택해야 잘 나눌 수 있음.

Stopping Criteria

- information gain이 0이 될 때가 아니라, 입실론보다 작다면 멈춰도 된다. -> 이정도면 충분하다는 뜻

- alternate strategy: full tree를 만들어서 low value node를 가지치기 하기

-> subtree중 의미가 거의 없는 부분을 leaf로 통일한 후, 원래 트리와 성능을 비교하여 채택

Decision Tree의 장점

- 비선형성

- categorical variable을 잘 적용

- 설명 가능성 높음

- robustness: 다른 트리들과의 앙상블을 진행해서 더 나은 것을 vote할 수 있음

Ensemble Methods

1. Bagging

training

- k개의 bootstrap sample 생성

- 각각의 S[i] 샘플에 대해 classifier를 생성해서 k개의 classifier를 만듦 (같은 알고리즘 이용)

testing

- k개의 classifier를 동일한 가중치로 투표해서 새로운 사례들을 분류해보기

2. Boosting

training

- classifier의 sequence를 생성 (같은 base learner 이용)

- 각각의 classifier는 이전 classifier에 의존적이며 그것의 에러를 찾는 데 집중

- 이전 classifier에서 잘못 예측된 사례들은 더 높은 가중치를 부여

testing

- classifier들의 연속으로 판단된 결과를 결합하여 test case의 최종 클래스를 부여

Random Forest

- Bagging with decision tree + split attribute selection on random subspace

-> learning process에서 나뉜 후보자들 각각을 선택하여 학습한 변형 트리 알고리즘 사용 -> random subset of features

* 1단계: bootstrapped dataset 생성

* 2단계: decision tree 생성 -> 각 단계의 피쳐의 random subset만을 이용한 bootstrapped dataset을 이용해야 함

- 새로운 노드에서도 root처럼 랜덤으로 두개의 변수를 candidate로 선택 (전체 3개의 column중 1개는 무시)

* 3단계: 반복 - 반복을 통해 새로운 트리를 계속 생성

* 4단계: Inference

- 가장 투표를 많이 받은 옵션이 무엇인지 확인

* 정확도 측정

- 통상적으로 원본 데이터의 1/3은 bootstrapped dataset에 나타나지 않음

-> 이 데이터(Out-Of-Bag sample)로 validation을 진행

Support Vector Machines

- 비선형성 분류기를 만드는 중요한 방법

- 2개의 클래스 사이에서 maximum margin linear separator를 추구

SVM vs Logistic Regression

- 공통점: seperating plane

- 차이점: LR는 모든 값에 대해서 평가하지만, SVM은 경계에 있는 점만 확인함

- SVM: 기본적으로 선형적이지만 더 고차원에도 적용할 수 있다.

고차원으로의 projection

- 차원 수를 늘리면 모든 것을 linearly separable하게 만들 수 있다.

Kernels and non-linear functions

Feature Engineering

- domain-dependent data cleaning은 중요하다

* Z-scores, normalization

* bell-shaped distribution 생성

* missing value를 imputing

* 차원축소 (SVD) -> 노이즈 말고 중요한, y값을 예측할 수 있는 아주 작은 신호 정보들을 뭉개버릴 수 있어 performance에 문제가 생길 수 있다.

* non-linear combination의 explicit incorporation (ex. products, ratios...)

Nerual Networks

Nearest Neighbor Classification

- 어떤 training example이 target에 가장 가까운지 확인해서 class label을 붙이는 것

- distance function을 올바르게 정의하는 것이 중요

- 장점: simplicity, interpretability, non-linearity

- k-nearest neighbor

Distance Metrics

다음과 같은 조건을 만족하는 경우

- d(x, y) >= 0 for all x, y (positivity)

- d(x, y) = 0 iff x = y (identity)

- d(x, y) = d(y, x) (symmetry)

- d(x, y) <= d(x, z) + d(z, y) (triangle inequality)

Not a Metric

다음과 같은 자연 유사성 측정 값들은 distance metric이 아니다.

- correlation coefficient (-1~1)

- cosine similarity, dot product

- mutual information measures

- cheapest airfare 

Euclidean Distance Metric

- 최소한 정규화를 통해 차원을 비교가능하게 해야 함

L_k Distance Norms

- 유클리드 거리를 일반화하기 위해서는 다음과 같은 식 사용

- k=1 일 때, Manhattan distance metric

- k=∞ 일 때, maximum component 

- k는 largest and total dimensional difference 사이의 tradeoff를 조절

p1(2, 0), p2(1.5, 1.5) 중 (0, 0)에서 더 먼 점은?

- k=1일 때, k=2일 때, k=∞일 때 먼 점이 다르다.

- distance metric은 어떤 점이 더 가까운지 설정

Circles for different k

- L_k circle의 모양은 원점에 대해 어떠한 점이 동등한 것들인지 나타낸 것

Projections from higher dimensions

- Projection method (ex.SVD): 표현 복잡도를 줄이기 위해 차원을 축소

- nearest neighbor는 원래 공간에 비해 확고해질 것

Regression / Interpolation by NN

- NN이라는 컨셉을 function interpolation에 이용할 수 있다.

- k개의 근접 점의 값의 평균을 내는 방식

- weighted average scheme는 (1) distance rank, (2) actual distances에 의해 따라 점들을 다르게 값을 매길 수 있다.

- 분류에도 비슷한 방식을 이용할 수 있다.

Gender Classification by Height/Weight

- k가 커지면 더 매끄러운 구분선을 만들 수 있음

Seeking good analogies

- 많은 지식의 분야는 analogy(비유)에 기초해 있다.

* Law: 어떤 법적 판례가 이 사례와 비슷한가?

* Medicine: 비슷한 증상을 가졌던 환자를 과거에 어떻게 치료했고, 그 환자가 살아남았는가?

* Real Estate: 이웃 지역에 비교 가능한 자산이 어느정도 가격에 팔렸는가?

Finding Nearest Neighbors

- n개의 점이 주어진 d차원에서 NN을 구하는 것은 O(nd)의 시간복잡도를 가진다.

- training set이 커지거나 차원이 커지면 시간이 굉장히 많이 든다.

-> grid indices, kd-trees, Voronoi diagrams, locality sensitive hashing 등을 이용

Voronoi Diagrams / Kd-trees

- Voronoi Diagrams: 가장 근접한 이웃을 공유하는 지역으로 공간을 분할

- kd-tree 등은 저차원에서 가장 근접한 이웃을 찾는 효율적인 알고리즘이다.

- 정확한 NN search는 충분히 고차원의 데이터에 대해서는 linear research로 축소되어야 한다.

Grid files

- 일정한 간격으로 나뉘어진 격자에 찍힌 점을 버켓팅 (Bucketting) 하는 것은 유사성으로 점들을 그룹화하는 방법 중 하나임

- 차원이 증가하면 index는 expensive해진다. -> 주변 격자들도 모두 탐색해야 하므로, exponential하게 증가할 수밖에 없음

Locality Sensitive Hashing

- Hashing은 이웃하는 점이 같은 bucket으로 hash 되었을 때 NN search를 더 빠르게 진행될 수 있도록 함

* hashing: 검색을 빠르게 하기 위해 hash key 값을 가져와서 빠르게 찾도록 함

- normal hashing은 distance bucket으로 유사한 점들을 퍼뜨림

- Locality Sensitive Hashing (LSH): 점이나 벡터 a, b를 가져와서 a가 b와 인접하면 h(a)=h(b)일 것이라고 생각함.

LSH for points on a sphere

1) 원점을 가로지르는 랜덤 면을 선택

2) 서로 이웃해 있다면 두 점은 그 면의 같은 면에 존재할 것임. (왼쪽 또는 오른쪽)

3) d개의 랜덤 면에 대한 L/R 패턴은 d-bit LSH hash code를 생성

예시를 살펴보자! 파란 색 점에 대해서 코드를 살펴볼 것.

1번 선을 그었을 때, 해당 점은 오른쪽에 있어서 0

2번 선을 그었을 때 해당 점은 왼쪽에 있어서 1

3번 선은 오른쪽이므로 0

4번 선은 왼쪽이므로 1 --> 최종 LSH 코드는 0101

Network data

Point Sets and Graphs

- Point set: graph를 정의함 -> x, y 점이 서로 이웃하면 (x, y) edge를 추가 / threshold 기준으로 거리가 가까우면 긋기

- graph: point set을 정의함 -> 인접 행렬의 SVD를 수행

ex) 2차원 SVD를 진행하여, 주성분 1/2까지 뽑아내기

Classical Graph Algorithms

- 두 vertices 사이의 최소 거리는 곧 그래프에서의 거리가 된다.

- 최소 거리를 찾는 클래식한 알고리즘, connected components, spanning trees, cuts, flows, matchings, topological sorting 등이 적용될 수 있음

PageRank

- PageRank(v, G): G에서의 random walk가 vertex v에 멈춘다는 뜻

- 반복적으로 정의됨

- 실제 상황에서는 빠르게 수렴함.

- 예) 중요한 친구가 표를 희소하게 나눠줄 때 -> 계속 업데이트가 되어 변하지 않게 됨 (수렴)

- centrality, importance 등을 측정하는 데 중요한 지표로 사용됨

- 예) 위키피디아 페이지

- PageRank에서 사용할 수 있는 의사 결정

* 관련성이 떨어져보이는 vertices/edges 편집

* outdegree가 0인 vertices 다루기

* random jump을 허가하는 문제: damping factor

Clustering

- 정의: 유사도를 기준으로 점을 그룹화하는 문제

- 요소들이 적은 수의 source로부터 유래한 상황에 이러한 origin을 나타내기 위해 클러스터링을 이용할 수 있다.

- ill-defined problem: 보는 사람에 따라 클러스터를 나누는 기준이 달라질 수 있음. 주관적인 부분

- 예시: 유전자 데이터 그룹화

- 클러스터링을 사용하는 이유

* hypothesis development: 내 데이터에 구별되는 데이터가 얼마나 있는가?

* Modeling over smaller groups: 각각의 클러스터에 대해 구분되는 예측 모델을 생성할 수 있음

* Data reduction: 각 클러스터의 centroid를 이용하여 클러스터를 대체/대표

* Outlier detection: 어떤 항목이 클러스터의 중심으로부터 멀리 떨어져있거나 아주 작은 클러스터에 갇혀있는가?

K-means Clustering

- 정의: k개의 점을 중심으로 정의 -> 모든 항목들을 가장 가까운 중심에 할당 -> 중심을 다시 계산 -> 이 과정을 계속 반복하여 충분히 안정되도록 함

- 문제점: local optima에 갇힐 위험이 있음

Centroids or Center Points?

- Centroid: color, gender 등 숫자로 정의되지 않은 특성에 대해 그룹화를 진행할 때는 명확하지 않다.

* 보통 이러한 데이터에서는 one-hot encoding으로 인코딩 진행

- center로 input example 중 가장 가운데에 가까운 점을 이용하는 것은 우리가 의미있는 거리 함수를 이용하기만 한다면 k-means를 이용할 수 있다는 뜻이다.

How Many Clusters?

- 올바른 클러스터의 개수는 클러스터링을 진행하기 전에는 알 수 없다.

- 클러스터를 더해갈 때, 점과 중심 사이의 MSE 값은 점진적으로 감소해야 한다.

- 올바른 클러스터의 개수를 초과하게 되면 MSE 값이 감소하는 속도가 느려진다.

K-means의 한계

- nested cluster, long thin cluster에 대해서 좋지 않은 성능을 보임

- 반복적으로 클러스터링을 진행하는 것은 local optima를 피할 수 있게 함 (random seed 값을 달리 함)

Expectation Maximization (EM)

- EM 알고리즘의 대표적인 예시가 K-means

- E-step: 추정되는 클러스터에 점을 할당

- M-step: 할당을 이용하여 parameter 추정을 향상시킴

Agglomerative Clustering

- 이런 bottom up 방식은 반복적으로 2개의 근접한 클러스터를 병합시킴

가장 가까운 클러스터가 의미하는 것

- 보통 Average, Centroid 방식을 채택

Linkage Criteria

Advantages of Cluster Hierachies

- 클러스터 및 서브클러스터의 조직화

- 클러스터링 과정 시각화

- 새로운 항목의 클러스터링을 효율적으로 할 수 있음

어떤 클러스터링 알고리즘을 사용할까?

- 올바른 거리 함수 사용

- 올바르게 변수를 정규화

- 최종 클러스터를 시각화해서 제대로 되었는지 확인하기

Linear Regression

- n개의 점이 주어졌을 때, 가장 근사를 잘 하거나 잘 맞는 직선을 찾는 것

Error in Linear Regression

- residual error: 예측값과 실제값 사이의 차이 

- Least squares regression은 모든 점의 잔차의 합을 최소화함.

-> nice closed form, 부호 무시하므로 선택됨

Contour plots - gradient descent

Linear function을 사용하는 이유

- 이해하기 쉬움

- default model에 적합

* 일한 시간에 따라 급여가 증가 / 지역이 커짐으로써 선형적으로 집값이 상승 / 먹은 음식에 따라 몸무게가 선형적으로 증가

변수가 여러 개일 때

- 각각의 x_n 변수들과 y값을 행렬로 나타내어 세타 값에 대한 행렬을 구할 수 있다.

더 나은 회귀 모델

1. 이상치 제거

- 잔차의 quadratic weight 때문에 이상치는 회귀 모델의 fit에 영향을 줄 수 있다.

- 이러한 잔차를 제거하는 것은 더 적합한 모델을 만들 수 있다. 

2. nonlinear function fitting

- 기본적으로 Linear regression은 직선이지만, x^2, sqrt(x) 등을 이용하면 곡선을 만들 수 있다.

- 임의로 polynomial, exponential, logarithm 등을 적용할 수 있다.

cf) 딥러닝은 raw feature에서 스스로 원하는 것을 뽑아낼 수 있어 feature engineering에 대한 수요가 적다. 최근에는 prompt engineering을 중요하게 여긴다.

3. feature/target scaling

- 넓은 범위의 데이터를 다루게 되면 coefficient가 지나치게 커질 수 있다.

- Z-score 등으로 스케일을 조정할 필요가 있다.

- power law이 적용되는 수입 등의 데이터에서는 특히 중요하다.

- x값을 log(x), sqrt(x) 등으로 대체할 수 있다.

- feature가 정규분포 형태라면, power law distribution을 갖는 데이터는 linear한 조합으로 나타내기 어렵다.

- Z normalization으로 변형된 데이터를 학습한 후, 결과는 원래 상태로 돌려둔 후 나타내면 된다.

4. highly correlated variable 제거

- 두 데이터가 서로 상관관계가 높다면 더 이상 우리에게 줄 수 있는 정보가 없다. 오히려 혼란을 가중시킴.

--> 따라서 제거해도 된다.

- covariance matrix를 생성하여 제거해야 하는 feature를 찾을 수 있다.

Closed form solution의 문제

- 세타 값을 구하는 방법은 큰 데이터에서는 연산 속도가 엄청 느려진다. - O(n^3)

- linear algebra는 다른 공식에 적용하기 어렵다.

- gradient descent 방식을 선택하게 만든다.

Lines in Parameter Space

- error function J는 convex하다.

Gradient Descent Search

- convex: 1개의 local/global minima 를 갖는 공간

- convex한 공간에서는 minima를 찾기 쉽다. -> 그냥 경사를 따라서 내려가기만 하면 찾을 수 있다.

- 어떤 점에서 내려가는 방향을 찾는 방법은, 미분을 해서 tangent line을 따라 가면 됨

--> (x+dx, f(x+dx))점을 찾은 후, (x, f(x)) 점에 fit

Batch Gradient Descent

- Batch: 각각의 경사하강에서 모든 training sample을 사용하는 것

- 통상적으로는 batch size를 줄여가며 경사하강

Local Optima

- J가 convex가 아니라면, 경사하강법을 따라 갔을 때, Local optima에 빠져버릴 수 있다.

Effect of Learning Rate / Step Size

- 너무 작은 스텝으로 움직이면 optima에 convergence하는 속도가 늦다.

- 너무 큰 스텝으로 움직이면 목표에 도달하지 못할 수 있다.

- 적절한 step size를 구하려면?

-> step size가 적절한지 판단하고, 너무 늦다면 multiplicative factor (3의 지수배 등등) 를 이용하여 늘려보기

-> 너무 크다면 (1/3의 지수배 등) 줄여보기

Stochastic Gradient Descent

- batch size도 hyperparameter이다.

- 모든 example이 아닌 일부만 이용하여 derivative를 계산하는 것도 방법

Regulation

- J 함수에 coefficient가 작게 유지되도록 람다 값을 추가

- 람다 값이 0에 가까워지면 error는 감소하고, 무한대에 가까워지면 thetha_0만 식에 남게 된다.

- 데이터에 최대한 가깝게 식을 만들면 error는 감소하지만, 위 공식에서 파란 부분은 커진다.

Interpreting/Penalizing Coefficients

- Squared coefficient의 합을 Penalizing 하는 것은 ridge regression or Tikhonov regularization

- coefficient의 절댓값을 penalizing하는 것은 LASSO regression이다.

* L1 metric

* L2: 각 차원에 대한 제곱의 합 -> 유클리드 거리 

LASSO (Least Absolute Shrinkage and Selection Operator)

- sparse solution을 선택하는 경향

- 변수 선택 및 regularization 기능

- interpretability를 향상

What is right Lambda?

- 람다가 커지면 small parameter를 강조 -> ex) set to all zeros

- 람다가 작아지면 training error 를 줄이기 위해 모든 파라미터를 자유롭게 이용할 수 있음

- 오버피팅/언더피팅 사이 균형을 유지해야 함

Normal form with regulation

- Normal form equation은 regularization을 다루기 위해 일반화될 수 있다.

- 또는 경사하강을 이용할 수도 있다.

Classification

- 분류는 남자/여자, 스팸/일반메일, 악성/양성 종양 등의 구분에 이용

- input record에 라벨을 부여

Regression for Classification

- linear regression을 이용하여 분류 문제를 해결할 수 있다.

- 이때 각각의 분류에 대해 0/1의 이진 분류를 사용한다.

- positive = 1, negative = 0

- regression 선은 이러한 분류를 나눌 것이다.

- 극단적인 +, - 사례를 추가할 경우 선이 바뀐다.

Decision Boundaries

- Feature space에서 선을 통해 클래스를 분류할 수 있다.

- Logistic Regression: 가장 적합한 분류 선을 찾기 위한 방법

Cost for Positive/Negative Cases

- 세타 값을 줄이는 것이 목표임

- 새로운 x에 대한 예측

Logistic Regression via Gradient Descent

- loss function이 convex하므로, 경사 하강을 통해 가장 적합한 파라미터를 찾을 수 있다.

-> 따라서 두 클래스에 대한 linear seperator를 찾을 수 있다.

Logisitc Gender Classification

Classification의 문제

1. Balanced Training Classes

- 긍정 라벨을 가진 데이터가 1개고 부정 라벨을 가진 데이터가 10만개 있다면 올바른 결과가 나올 수 없다.

- 각각의 라벨 데이터 수를 맞추자.

* minority class에 해당하는 데이터를 찾기 위해 더 노력하기

* 더 큰 class의 요소를 버리기

* minority class에 가중치 부여 -> overfitting 조심하기

* small class에 대해 데이터를 복제하기 -> random perturbation (복원추출로 여러개 뽑아서 앙상블 진행)

2. Multi-Class Classifications

- 모든 분류가 이진적이지는 않음.

- ordering 관계가 없는 분류에 대해서는 단순히 숫자로 표현하여 분류를 진행하면 안 된다.

- ordinal data에 대해서만 숫자로 라벨링 가능. 아닌 경우 원 핫 인코딩 이용.

cf) One Versus All Classifiers

- 다중 독립 이진분류기를 이용하여 multiclass classifier를 만들 수 있다.

- 각 분류기가 예측한 가능성 중 가장 큰 것을 채택.

3. Hierarchical Classification

- 유사성을 이용해 그룹으로 나누고 taxonomy를 만드는 것은 효율적인 class 개수를 줄일 수 있게 한다.

- top-down tree를 이용해 분류