2021.03.26 TIL

• 기초통계

최적화

함수의 최저 또는 최고점을 찾는 과정.

분류문제의 경우 차원 상에 가장 잘 분류할 수 있는 모형을 찾기 위해 최적화를 이용한다.

그리드 서치

일정한 간격의 모든 값을 계산하여 그래프를 그려 최저 또는 최고점을 찾는다.

간단하고 직관적이지만 차원이 높으면 사실상 불가능.

수치적 최적화

가능한 적은 만큼 시도하여 최적점을 찾는 과정.

• 현재 위치 X(k)가 최적점인지 판단하는 알고리즘이 필요.
• 어떤 위치 X(k)시도 후 다음번 X(k+1)을 찾는 알고리즘이 필요.

기울기가 0인 지점이 최적점인것을 이용. 기울기가 0이면 미분한 값이 0이다. 그레디언트벡터가 0벡터.

이는 필요조건인데 최저점을 구할 경우 기울기가 0이라 한다면 최고점일 경우도 있기에 사실상 2차 도함수 까지 파악해야 정확히 알 수 있다.

2차 도함수는 헤시안 행렬. 최저점을 찾을 경우 기울기(도함수)가 0임은 물론, 2차도함수-헤시안행렬이 양수여야 한다. (양의 정부호)

최대경사법

수치적 최적화를 위해 최대경사법이라는 방법을 이용한다.

현재 위치 X(k)에서 기울기값만을 이용하여 g(X(k)) 다음번 위치 X(k+1)을 결정하는 방법.

최적점에 도달했을 경우 위의 설명과 마찬가지로 기울기가 0이되어 최대경사법을 진행해도 위치를 옮기지 않게 된다. 또한 최적점 근처에 다가갈수록 기울기가 0에 가까워지므로 적게 움직이게 된다.

하지만 이 역시 100% 확실한 것은 아니다. 스텝사이즈가 크게 되면 최적점에서 오히려 멀어지는 현상이 발생하게 된다.

결국 적절한 스텝사이즈(μ)를 구하는 것이 관건.

다차원에서는 ‘진동현상’이 발생할 수 있다.

이를 해결하기 위해 1. 뉴턴방법, 2.모멘텀방법을 사용하게 된다.

모멘텀방법의 경우 가던 방향으로 계속 진행하여 지그재그 현상을 없애는 것으로 인공신경망-딥러닝에서 주로 사용하게 된다. 일반적으로나 머신러닝의 경우(목적함수를 수식으로 표현되는 경우) 뉴턴방법을 사용하는데 이는 도함수 말고도 2차도함수를 이용하여 최적점을 찾는 방법이다.

스텝사이즈에 그레디언트 벡터를 곱한 기존방법과 다르게 헤시안 행렬의 역행렬을 곱하게 되는데 이렇게 함으로써 벡터의 방향과 크기가 바뀌게 되어 진동현상이 덜 생기게 최적점에 다가갈 수 있다.

Scipy 이용

Scipy의 optimize 서브 패키지는 최적화 명령 minimize()를 제공한다.

이런식으로 이용하고 성공유무가 표시된다.

제한조건이 있는 최적화 문제

제한조건에는 1.등식제한조건과 2. 부등식제한조건이 존재한다.

등식 제한조건은 평이하지만 부등식 제한조건이 있는 경우 상대적으로 해결하기 어렵다.

제한조건이 걸려 있는 최적화 문제를 해결하기 위해 ‘라그랑주 승수법’이라는 방법을 사용한다.

라그랑주 승수법

목적함수에 조건을 추가하여 새로운 목적함수를 만들어낸다.

제한조건 등식에 λ라는 새로운 변수를 곱해 더한 함수를 목적함수로 간주한다. (λ의 개수는 제한조건 등식의 개수와 동일 )

x1, x2, λ 변수가 총 3개가 되어 방정식을 풀어야 한다. 제한조건이 이차식 이상일 경우 값을 직접 대입하여 최저점을 도출(전역최저점)하는 값을 찾아야 한다.

Scipy의 optimize 서브패키지에 제한조건이 있는 최적화 문제를 푸는 fmin_slsqp()명령이 존재,

fmin_slsqp(목적함수, x0(초기값), eqcons=[제한조건1, 제한조건2..])

위의 식으로 예를 들자면

def f1array(x):

​ return x[0] ** 2 + x[1]** 2

def eq_constraint(x):

​ return x[0] + x[1] -1

sp.optimize.fmin_slsqp(f1array, np.array([1, 1]), eqcons=[eq_constraint] )

당연한 얘기지만 λ이 0이라면 제한조건이 의미가 없어지기때문에 원래 목적함수의 최적화와 다를바 없어 진다.

부등식 제한 조건 최적화 문제

역시 라그랑주 승수법을 사용하여 해결할 수 있다. 제한조건이 0보다 크거나 같다면 양변에 -를 곱하여 부호를 바꾸어준다. (최저점을 찾기 위해)

1) 등식 제한조건과 달리 (x, λ로 미분한 값이 모두 0) x로 미분한 값만 0이 되면 된다.

2) 등식 제한조건과 달리 (그레디언트 - λ로 미분한 값이 0) λ * 그레디언트 값이 0이 되면 된다.

​ 그레디언트가 0 이되거나 혹은 λ값이 0이 되면 된다.

3) 라그랑주 승수는 0또는 양수

그림으로 확인해 보면,

왼쪽의 경우 최적점이 제한조건이 없는 경우와 똑같아지므로 제한조건이 의미가 없는 경우 즉. λ값이 0인 경우다.

오른쪽의 경우 최적점이 등식제한조건의 경우와 똑같아지므로 결국 부등식 제한조건은 1.제한조건이 없거나 2. 등식 제한조건의 문제를 풀거나로 귀결된다.

이 역시 fmin_slsqp()로 풀 수 있는데 제한조건과 다르게 인수가 eqcons 에서 ieqcons로 바뀌고 ieqcons에 들어가는 부등식 조건이 위와 다르게 g(x) >= 0, 즉 0보다 큰 경우로 부등식을 맞추어 넣어주어야 한다.