jPub09_최적화와탐색

최적화 = 오차 함수 정의 + 이 값을 최소화

• 방법 : 미분을 통해 기울기 구하기, ,기울기 하강법
• 문제점 : 비연속의 문제는 기울기 하강법 사용 못함

1. 기울기 하강법

목적 : 을 찾는것

임의의 값 X_1에서 결정할 것

1. 어떤 방향으로 움직여야 하는가?
   • 최급강하법(Steepest Descent): 탐욕적(greedy)방법으로 선택 하는것
2. 얼마나 움직여야 하는가?
   • 선형탐색
   • 신뢰영역(Trust Region)

최급강하법(Steepest Descent)

• 테일러 전개식 함수 기반 : 함수의 미분값을 바탕으로 근사치를 접근하는 방법

• J(x) : 벡터의 1차 미분함수 자코비안
• H(x) : 벡터의 2차 미분함수인 해시안 행렬

2. 최소 제곱법

MLP, 선형회귀등에서 많이 사용

레벤버그 말퀘트(ML): 신뢰영역 최적화 알고리즘

3. 켤레 기울기(Conjugate gradient)

켤레 = 어떤 행렬A에 대해서 두 벡터들이 을 만족할 경우

이동거리 = =

4. 그외 기울기를 사용하지 않는 최적화 방법(=탐색) 들

비연속 최적화 문제(eg. 외판원)해결 가능

4.1 완전 탐색

• 모든 해결책을 다 시도해 보고 가장 최선의 것을 선택
• 비용이 많이 들어 비 현실적

4.2 탐욕(Greedy) 탐색

• 각 단계에서 지역적으로 가장 좋은 선택
• 비용은 적게 들지만, 좋은 해답을 얻는다는 보장이 없음

4.3. 언덕 오르기

• 현재 해법을 바탕으로 지역 탐색을 수행하고, 결과를 향상 시키는 옵션을 선택
• 단점
  • 많은 언덕 존재시 : 지역 최댓값에 오르고 그것을 해답으로 간주
  • 평지의 경우 : 최댓값을 못 찾을수 있음
  • 경사가 급한 경우 : 최댓값에 이르기 전에 이미 도달했다고 판단

5. 활용과 탐험

진화 알고리즘

6. 담금질 기법