2_딥러닝과 최적화 개요
190905 이민예
XOR Problem
위 XOR 문제는 구분할 수 없다. 2차원의 Feature Space 에 있는 2개의 클래스를 구분하기 위해서는
선형이 아닌, 비선형을 사용한다
선형을 쓰기 위해 (목적), Feature Space를 변환(수단)한다.
Feature Space를 변환한다는 것은, 응용통계방법론에서 Space Transformation 과 유사하다. 데이터는 동일한데 (즉, 목적은 같은데) 이 목적을 이루기 위해서 직교좌표계 (x,y) 가 아닌, 극좌표계 (theta, r) 을 사용한다.
정규분포 (=Gaussian Distribution)
정규분포, 즉 가우시안 분포라고도 한다. 정규분포를 어떠한 형태로 나타내었을 때, 표준이냐에 대한 주장이 있어왔다 (Gauss, Stigler). 하지만, 일반적으로 이야기하는 표준정규분포 N(0,1)란, 평균이 0이고, 분산이 1인 정규분포를 표준정규분포라 한다. 정규분포에 PDF 는 아래와 같다.
표준정규분포 N(0,1) 는 아래와 같다.
계수의 역할
: 적분이 1이 되도록 함. 즉 함수 아래 면적이 1임.
: 샘플 값을 스케일링함으로서, 단위 분산 (분산 = 1) 이 되도록 함.
표준정규분포의 적분 값이 1임을 증명하기 위해서는, 가우시안 적분 값이 임을 알아야 하며, 가우시안 적분 값으로부터 가우시안 함수를 통해 표준정규분포의 적분 값이 1임을 알 수 있다.
표준정규분포 적분 1의 증명
가우시안 적분 값 증명
제곱을 한다.
x,y 로 쪼갠다.
극좌표로 표현한다. (질문)
즉, 위 단계는 공간변환의 단계이며, 공간변환을 통해서, 적분 값을 증명하였다.
가우시안 함수를 이용한 표준정규분포 적분 값 증명
정규분포를 일반화하는 수식을 가우시안 함수라 하고, 다음과 같이 정의한다.
가우시안 함수에서, 정규분포가 되기 위한 각 a,b,c는 다음과 같다.
가우시안 적분에서 얻은 값을 가우시안 함수에 대입하면, 다음을 얻을 수 있다.
가우시안 적분 값은 위와 같고, 정규분포가 되기 위한 a,b,c 값을 대입하면 표준정규분포의 적분 값은 1이다. 따라서, 이슈는 두 클래스가 잘 나누어 질 수 있도록, 좋은 변환 방법을 찾아야 한다.
차원의 저주
24*24 에서 각 셀들은 확률을 가지고 있음.
최적화
Concave
오목함수(Concave)일 경우, 1차 미분과 2차 미분을 이용한 최대, 최소를 구할 수 있다.
Convex
Gradient Search
Greedy Search
탐욕적이라서 근시안적으로 밖에 보지 못함. 근시안적 탐색이라고 이해하는 게 직관적임.
동적 계획법보다 효율적이긴 하지만 항상 최적의 결과를 보장하지는 못한다.
Huristic
현실에서는, 제약적인 조건(해답을 찾는데 너무 오랜 시간이 들거나 Time Complexity, 찾더라도 저장할 공간이 없음 Space Complexity)이 있기 때문에, 이상적인 최적 해를 찾는 것이 어려움. 따라서, 휴리스틱 알고리즘이란 자원에한적인 상황에서 알고리즘 목적 중 둘 혹은 하나를 포기하면서, 최선의 해답을 찾는 알고리즘이다.
휴리스틱 알고리즘은 우리가 아는 탐욕 탐색 알고리즘이다.
하지만, 휴리스틱 알고리즘은 해결하고자 하는 문제마다 각기 그 특성에 맞추어 개발해야 하는 어려움이 있다. 특정문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용가능한 상위수준의 발견적 기법, 즉 메타 휴리스틱(Meta-Heuristic) 이다.
Heal-Clime
Meta-Huristic
Tabu Search(TS)
SA 와 GA 는 현재 값에 이웃값을 참조하여, 현재 값을 개선하려는 경향이 있음.
이러한 알고리즘은 국소 최저점에 빠질 경우가 있음.
Tabu Search는 Tabu Queue 라는 별도의 메모리를 가지어 이전에 방문한 지역 최저점에 가지 않는다.
이웃해가 모두 Tabu Queue 에 있거나 사용자 정의에 종료조건을 만족하면, 종료함.
Simulated Annealing(SA)
Annealing 이란 말은 금속 공학에서 결함을 작게 하기 위해서 열을 가하고, 서서히 냉각시키는 과정을 의미함.
금속 재료에 열을 가하면 원자는 자신이 위치한 내부 에너지의 국소 최저점 ( Local Minimum ) 에서, 더 높은 에너지가 있는 곳으로 정처없이 방황하게 될것이다. 천천히 냉각함으로서, 초기 상태보다 내부 에너지가 한층 더 극소인 상태로 얻을 가능성이 많아짐.
따라서, 지역 최소점에 빠지지 않도록, SA 알고리즘을 사용한다. 쉽게 생각하면, Hill Climbing Method 에 Huristic을 적용한 것이다.
Hill Climbing 은 Local Minima에 빠질 가능성이 있으나, SA는 이웃해가 클지라도, 새로운 경로를 탐색하여, Global Minima 에 도달함.
T를 어떻게 낮추어 가는 지가 중요함.
T 값을 빨리 감소시킬 경우 : 새로운 값을 받아들일 확률이 적어지기 때문에, 지역 최저점에 빠진다.
T값을 천천히 감소시킬 경우 : 전역 최저점에 도달할 확률이 커지지만, 시간이 많이 걸린다.
따라서, T값을 어떻게 할지에 관한 많은 연구가 있음
Genetic Algorithm(GA)
이처럼, 메타휴리스틱은 여러 실행 가능한 영역을 탐색하고 지역 최적해에서 탈출할 수 있다는 것이 가장 큰 특징임.
[Reference]
Last updated
