My data lab

PDE 를 풀기위한 여러 방법중 위의 방법들에 대해서 공부를 하였다.

FDM : 1차 2치미분을 태일러 전개를 통해 discrete 한 Q 값의 차이로 근사를 이용한다.

1차미분= discrete 한 두 관찰된 포인트를 이용하여 미분방정식을 대체 함

특징

1. 직관적이고 쉽다.

2. 양함수적 성질로 인하여, Stepping방법을 자유롭게 변형 가능

3. 고차로 변형이 쉽다.

4. 복잡한 공간에서의 적용이 어려움

5. 불연속점에 대한 불완전성

FVM : volume 을 미리 만들어 놓고 conversation law 를 이용하여

i 번째 grid volume 의 Q_i(t+1) 값을 주변 Flux 의 변화량 으로 나타낼 수 있다.

이 때, Flux 는 다시 Q_i-1, , Q_i , Q_i+1 등으로 나타낼 수 있으므로

이때 Flux의 정의에 따라서 차수와 안정성(stability) 등이 결정 된다.

특징:

1. FDM 과는 다르게 복잡한공간 (complex Geometry) 에서도 flux 를 정의 하여 사용가능하다.

2. 이때 만들어진 원래의 방정식은 높은 차수(high order accuracy)를 갖을수 없는 단점을 가지고있다.(~2차 정도?)

FEM : weak Sense 로접근한다.

Test function 을 가지고 접근하여 그것을 적분했을 때 원래 식에 일치하는 것인지 확인하는 매커니즘을 갖는다.

u 자체를 미리정해놓은 basis(pi1, pi2 .) 들의 Weighted 합이라고 간주하고

pi1, pi2 는 한편 근처의 pi 들 외에는 내적할경우 0 이되도록 설정 해 버린다.

그러면 원래 풀려던 식에 pi 를 내적하면 Tridiagonal 한 Matrix A, Ax=b를 푸는 문제 가 된다.

1. FVM 과는 달리, FEM 는 basis function 자체를 고차로 잡아 버릴 수 있기 떄문에 높은 차수를 갖을 수 있다.

2. Matrix 자체를 연산하기 때문에 Implict 한 Method 이기 때문에 stability 등에 불완전성을 갖는다.

Kmean clustering lib (1).pptx

Machine learning 을 주요 데이터 흐름과 각 노드로 분류하면, Data retrieval, Data preprocessing, Feature Engineering, Modeling,  Predict, Evaluation 단계로 나눌 수 있다.
각 단계 별 Data 의 Input과 Output 특성에 따라 작업을 분해하고 모듈화 하여 구성하는 것이 Data Analysis Framework을 제작하는 첫 단계라고 할 수 있다.

Machine Learning 을 위한 Data는 대개 아래의 과정을 거친다.

Data cleaning

Fill in missing values (attribute or class value):
Identify outliers and smooth out noisy data:
Correct inconsistent data: use domain knowledge or expert decision.

Data transformation

Normalization:
Aggregation: moving up in the concept hierarchy on numeric attributes.
Generalization: moving up in the concept hierarchy on nominal attributes.
Attribute construction: replacing or adding new attributes inferred by existing attributes.

Data reduction

Reducing the number of attributes
Reducing the number of attribute values
Reducing the number of tuples

출처 :  http://www.cs.ccsu.edu/~markov/ccsu_courses/datamining-3.htm

위의 과정은 아래 설명하는 Machine Learning 각 단계에서 적절히 분배되어야 한다.

1.1 Data Retrieval

Data를 조회하고 그 특성을 파악하는 단계로, Data에 통계 기법 등 적용을 위해서는 간단한 변환이 필요하다. 대개 Implementation 단계에서는 필요 없는 작업이므로 엑셀이나 R 등의 접근이 용이한 tool을 사용하는 것이 바람직하다.

따라서,  Framework 모듈 대상에서는 제외할 예정이나 관련 library 정도는 제공하는 것이 바람직하다고 판단된다.

1.2 Data Preprocessing

Data 의 전처리 단계이다. 비 정형 데이터 Input을 뒤에서 ML Algorithm을 사용할 수 있을 정도의 형태로 변환하여 Output으로 제공한다. 뿐만 아니라 데이터의 무결성, 적합성도 보장을 해야 하는 단계이다. 

이를 위하여 비정형 데이터를 정형 데이터로 변환하는 것 뿐 아니라 결측 Data를 제거하거나, 다른 값으로 채워 넣어 보완하거나, 틀린 형식을 보정하는 등의 기능도 제공해야 한다.

1.3 Feature Engineering

Feature Engineering 은 뒤에서 사용할 algorithm에 따라 Feature를 선택/제거하는 기능 및 왜곡을 방지하기 위한 값 변경(normalize, scaling, one-hot encoding..etc.) 기능을 제공해야 한다.

Machine Learning에서 feature engineering 은 사용 Model과 mapping하면 절차적으로 제공 가능하다.

종적 데이터를 횡적 데이터로 변환하고 Vector화 하는 기능이 대부분 Model에서 필요할 것으로 판단된다.

1.4 Modeling

Modeling 단계는 가장 capsulation이 용이한 부분이다. 대부분 solution에서 제공하는 library는 정형적으로 사용하도록 되어 있으며, hyperparameter 만 조절하면 될 정도로 단순하다. 

1.5 Predict, Evaluation

예측 및 평가 단계는 학습과 테스트 Data 를 나누어 검증하는 기능과, 검증 report를 제공하여 사용자가 1.4 단계를 다시 반복할 수 있도록 하는 기능이 필요하다.

Model 과 Predict/Evaluation은 밀접한 상관관계가 있으므로 묶어서 모듈화 하는 고려가 필요하다.

출처 : http://opt-lab.tistory.com/14

개미는 페로몬으로 길을 찾는다. 처음 가보는 길이더라도 동료들이 남긴 페로몬을 따라 먹이가 있는 곳까지 찾아간다. 뿐만 아니라 시간의 흐름에 따라 효율적으로 짧은 길을 찾아낸다. 개미가 지름길을 찾아낼 수 있는 것은 먼 거리의 경로 보다 짧은 거리의 경로에 상대적으로 같은 시간 안에 통과하는 개미가 더 많게되고, 더 많은 페로몬이 누적되기 때문이다. 아래는 시간의 흐름에 따라 개미가 짧은 길을 찾아내는 과정을 나타낸 그림이다.

장애물이 처음 나타났을 때 장애물을 돌아가는 양쪽 길 중 하나를 같은 확률로 선택한다면 더 짧은 경로에 더 많은 개미가 통과하게 되고 따라서 더 많은 페로몬이 누적되게된다. 시간의 흐름에 따라 긴 경로의 페로몬이 증발량이 누적량보다 많아지게 되면 점점 긴 경로를 선택하는 개미는 줄어들게 될 것이고 결국 짧은 경로만 선택되게 된다. 개미의 입장에서 보면 TSP문제가 아무것도 아닌 문제일 수도 있다.

Ant Colony Optimization은 이러한 개미의 습성을 모방한 Meta-Heuristic이다. Meta-Heuristic이란 Optimal에 근사한 답을 찾아낼 수 있는 Heuristic을 말한다. 보통 Optimal의 1~2%내외의 답을 찾아낼 수 있을 때 Meta-Heuristic이라고 할 수있다. 대표적인 Meta-Heuristic은 Genetic Algorithm, Simulated Anealing이 있다. 재미있는 것은 훌륭한 Meta-Heuristic은 대부분 자연을 모방해서 만들어졌다는 것이다.

Ant Colony Optimization을 얘기하려면 Ant Colony Optimization의 역사를 먼저 이야기 해야 하는데 Ant Colony System의 기원은 Ant System이다. Ant System은 1992년 Marco Dorigo가 창안해냈다. 그 후 Ant System을 몇 가지 개선시킨 Ant Colony System이 1997년(Gambardella Dorigo) 발표되었다. 그럼 먼저 Ant System을 알아보자.

Ant System은 간단하게 3단계로 나눌 수 있다.

Ant System
1. 개미들을 탐색시킨다.
2. 모든 개미가 탐색이 끝나면 각 arc의 페로몬을 업데이트 한다.
3. 개미가 찾은 해를 비교해서 현재의 best solution보다 더 나은 해일경우 best solution 업데이트.
종료 조건이 충족될 때 까지 1~3반복

Heristic의 특성상 Optimal을 찾았더라도 그 답이 Optimal인지 확인 할 수 없기 때문에 보통 종료 조건은 일정한 시간 혹은 iteration 동안 더 나은 해를 찾지 못하면 종료하도록 하거나 평균적인 solution의 값이 어떤 값으로 수렴하게되면 종료한다. 

Ant System에서 가장 중요한 것은 개미가 탐색할 때 다음 노드를 선택하는 기준이다. 개미의 습성을 구현하는 방법은 많겠지만 Ant System은 다음과 같은 확를 분포를 이용했다.

p_i,j : 개미가 node i에서 node j로 이동할 확률
τ_i,j : arc i,j의 페로몬 양
η_i,j : arc i,j의 중요도. 보통 1/c_i,j
S : 개미가 방문한 node
α, β : 파라미터

그러니까 arc의 페로몬의 양이 클 수록, arc의 cost가 작을 수록 그 arc를 선택할 확률이 높아지고 α, β의 값으로 각각 페로몬의 양에 비례할 강도와 arc cost에 반비례할 강도를 조절할 수 있다. 논문에서는 α=1, β=2를 사용했지만 꼭 정수일 필요는 없다. 개미가 방문한 노드들은 선택에서 제외시킴으로써 개미가 집으로 돌아오지 못하고 무한루프에 빠지는 경우를 막는다. 

그리고 Ant System의 페로몬 Update 방법은 다음과 같은 공식을 사용해 이루어 진다.

 
ρ : 파라미터. 페로몬의 증발비율. 0~1 사이의 값을 가진다.
c_k : 개미k가 찾은 solution의 cost

Iteration마다 모든 arc의 페로몬을 일정비율 증가시키고, 개미가 이동한 arc에는 페로몬을 누적시키는 것이다. 주의깊게 보아야 할 부분은 페로몬의 양이 Iteration마다 ρ만큼씩 증발한다는 것이다. 즉, 개미가 그 arc를 지나가지 않으면 그 arc의 페로몬 값은 Iteration 횟수가 증가할 수록 0으로 수렴한다. 그리고 개미가 지나간 arc에 추가되는 페로몬의 양은 그 개미가 찾은 답의 비용에 반비례한다. 즉, 좋은 답을 찾은 개미일수록 더 많은 양의 페로몬을 남긴다.

Ant System의 특징은 각각의 개미가 arc를 선택하는 것이 다른 개미의 arc 선택에 영향을 주지 않는다는 것이다. 한번의 Iteration이 끝나야 페로몬이 업데이트 되기 때문이다. 또한 개미의 arc선택이 페로몬의 양과 arc의 cost에 영향을 받기는 하지만 기본적으로 Random한 선택이기 때문에 Iteration이 진행되어도 개미가 이전보다 더 나은 선택을 한다는 보장이 없다.

이런점을 보완한 것이 Ant Colony System이다. 아마도 Colony를 붙인 것은 개미간의 상호 작용을 반영했기 때문인 것 같다. 먼저 Ant System과 구분되는 Ant Colony System의 특징을 알아보자.

Ant Colony System
1. 개미가 다음 노드를 선택할 때, 확률적으로 Deterministic한 선택을 한다.
2. 개미가 arc를 선택해서 이동할 때 마다 페로몬의 값을 업데이트한다.
3. 개미들 중 제일 좋은 solution을 찾은 개미가 선택한 arc에 추가적인 페로몬을 누적시킨다.

자연의 개미가 길을 선택할 때 페로몬이 많은 길을 선택할 것은 자명한 일이다. 1번은 이점을 표현한 것이다. 그러니까 개미가 arc를 선택할 때 단순히 페로몬의 가장 많은 arc를 선택할 확률이 있다는 것이다. 이러한 선택은 다음과 같이 나타낼 수 있다.

equation 1
q₀ : 파라미터. 개미가 Deterministic한 선택을 할 확률. 0~1 사이의 값을 가진다.
q : 0~1사이의 확률변수
※ q ≥ q₀라면 Ant System의 확률분포를 이용한 arc선택을 한다.

즉 q₀확률로 개미는 주사위를 던지지 않고 본능에 충실하게 페로몬이 많은 길을 선택하는 것이다.

2번이 추가됨으로써 개미가 한 노드에서 다른 노드로 움직일 때 마다 페로몬을 업데이트(Local Step Update) 시키고 그 영향을 탐색중인 모든 개미들이 받게된다. 다음의 식을 이용해서 업데이트 한다.

equation 2
τ₀ : 파라미터. 페로몬의 초기값. 보통 1/(N x Nearest Neighbor의 값)
φ : 파라미터. 페로몬의 Local Step 증발비율.

3번은 한 번의 Iteration이 끝난 후에 이루어진다.(Global Update) 다음과 같은 식을 이용해서 업데이트 한다.

equation 3

3번을 보면 Neural Net의 신경망 학습과정과 매우 유사하다. 아무튼 전체 개미 중에서 가장 좋은 solution을 찾은 개미에게 자신의 tour에 페로몬을 남길 기회를 준다. 이렇게 함으로써 다음 Iteration에서 더 좋은 arc를 선택할 확률이 늘어나게되고 결과적으로 개미들에게 더 좋은 solution을 찾도록 유도한다.

지금까지 설명한 Ant Colony System을 정리하면 다음과 같다.
1. 개미들을 탐색시킨다.
1-1. 0~1사이의 난수를 발생시켜 q₀보다 작으면 Deterministic한 선택을 한다.(1번 식)
1-2. 난수가 q₀보다 크거나 같으면 Ant System과 같은 확를분포를 사용한 아크선택을 한다.
1-3. 개미들이 아크를 이동할 때마다 그 아크의 페로몬을 Local Step Update 시킨다. (2번 식)
2. 한 번의 Iteration이 끝나면 제일 좋은 solution을 찾은 개미의 tour에 페로몬을 Global Update한다. (3번 식)
3. 개미가 찾은 해를 비교해서 현재의 best solution보다 더 나은 해일경우 best solution 업데이트.
종료 조건이 충족될 때 까지 1~3반복

Ant Colony Optimization 알고리듬의 단점은 우선 파라미터 값들이 너무 많고 알고리듬이 파라미터에 너무 민감하게 반응한다는 것이다. 또 문제의 크기에 따라 파라미터 값들을 적절히 바꿔줘야 Optimal에 근사한 답을 찾아낸다. 파라미터를 고정시켜놓고 다양한 크기의 문제에 적용하면 solution의 질이 천차만별이다. 하지만 파라미터를 적절히 설정했을 때 optimal +1% 안밖의 답을 찾아냈다.

유의해야할 파라미터는 φ와 ρ이다. φ와 ρ는 페로몬 값이 0으로 수렴하는 속도를 결정한다. 너무 크게하면 좋은 경로를 놓치게 될 확률이 크고 너무 작게하면 더 좋은 답을 찾지 못하고 엉뚱한 방향으로 페로몬이 수렴하는 경향이 있다. 50 node의 문제에서 φ=0.02, ρ= 0.05로 했을 때 가장 좋은 결과를 얻었다.

다음은 50개의 랜덤하게 생성한 node의 문제에서 페로몬의 값과 best solution의 변화를 보여준다.

페로몬의 색깔은 상대적인 페로몬의 크기를 나타낸다.