튜토리얼 개요

이 자습서는 다음과 같이 네 부분으로 나뉩니다.

1. 기능 최적화
2. 후보 솔루션
3. 목적 함수
4. 평가 비용

기능 최적화

함수 최적화는 수학의 하위 분야이며 현대에는 수치 계산 방법을 사용하여 다루어집니다.

연속 함수 최적화 (여기서 “함수 최적화”)는 수학적 최적화라고 하는 더 넓은 연구 분야에 속합니다.

시퀀스 또는 조합으로 구성된 후보 솔루션(예: 조합 최적화)과 달리 숫자 입력 변수로 구성된 최적의 후보 솔루션을 찾는 것을 포함하므로 다른 유형의 최적화와 구별됩니다.

기능 최적화는 거의 모든 과학 및 엔지니어링 분야에서 사용되는 기술의 널리 사용되는 도구 모음입니다.

사람들은 최적화합니다. 투자자는 과도한 위험을 피하면서 높은 수익률을 달성하는 포트폴리오를 만들려고 합니다. […] 최적화는 의사 결정 과학 및 물리적 시스템 분석에서 중요한 도구입니다.

— 페이지 2, 수치 최적화, 2006.

거의 모든 머신러닝 알고리즘이 함수 최적화를 사용하여 모델을 학습 데이터 세트에 맞추기 때문에 머신러닝에서 중심적인 역할을 합니다.

예를 들어, 점 집합에 선을 맞추려면 최적화 문제를 풀어야 합니다. 선형 회귀 또는 신경망 모델을 훈련 데이터 세트에 맞추는 것과 같습니다.

이러한 방식으로 최적화는 일반 모델을 특정 상황에 맞게 조정하는 도구를 제공합니다. 학습은 최적화 또는 검색 문제로 처리됩니다.

실제로 함수 최적화는 함수에서 최소 또는 최대 출력을 생성하는 주어진 함수에 대한 입력을 찾는 문제 클래스를 설명합니다.

목표는 변수 또는 미지수라고하는 시스템의 특성에 따라 다릅니다. 우리의 목표는 목표를 최적화하는 변수의 값을 찾는 것입니다.

— 페이지 2, 수치 최적화, 2006.

함수 최적화에는 함수에 대한 입력(예: x), 목적 함수 자체(예: f()) 및 함수의 출력(예: 비용)의 세 가지 요소가 포함됩니다.

• 입력(x): 평가할 함수에 대한 입력값(예: 후보 솔루션).
• 함수 (f()): 입력을 평가하는 목적 함수 또는 목표 함수입니다.
• 비용: 목적 함수를 사용하여 후보 솔루션을 최소화 또는 최대화한 결과입니다.

각 요소를 차례로 자세히 살펴 보겠습니다.

후보 솔루션

후보 솔루션은 목적 함수에 대한 단일 입력값입니다.

후보 솔루션의 형태는 목적 함수의 특성에 따라 다릅니다. 단일 부동 소수점 숫자, 숫자로 구성된 벡터, 숫자로 구성된 행렬 또는 특정 문제 도메인에 필요한 만큼 복잡할 수 있습니다.

가장 일반적으로 숫자의 벡터입니다. 테스트 문제의 경우 벡터는 함수에 대한 각 입력 변수의 특정 값을 나타냅니다(x = x1, x2, x3, …, xn). 머신러닝 모델의 경우 벡터는 모델 계수 또는 가중치를 나타낼 수 있습니다.

수학적으로 말하자면, 최적화는 변수에 대한 제약이 적용되는 함수의 최소화 또는 최대화입니다.

— 페이지 2, 수치 최적화, 2006.

후보 솔루션에 대한 문제 영역 또는 목적 함수에 의해 부과된 제약 조건이 있을 수 있습니다. 여기에는 다음과 같은 측면이 포함될 수 있습니다.

• 변수 수(1, 20, 1,000,000 등)
• 변수의 데이터 형식(정수, 이진, 실수 값 등)
• 허용되는 값의 범위(0과 1 사이 등)

중요한 것은 후보 솔루션이 개별적이며 많은 솔루션이 있다는 것입니다.

후보 솔루션의 세계는 열거하기에는 너무 방대할 수 있습니다. 대신 우리가 할 수 있는 최선은 검색 공간에서 후보 솔루션을 샘플링하는 것입니다. 실무자로서 우리는 검색 공간을 효과적으로 샘플링하고 좋은 또는 최상의 후보 솔루션을 찾기 위해 문제에 대해 사용 가능한 정보를 최대한 활용하는 최적화 알고리즘을 추구합니다.

• 검색 공간: 목적 함수에 허용되는 입력의 수, 유형 및 범위로 정의되는 후보 솔루션의 우주.

마지막으로, 후보 솔루션은 목적 함수에 의한 평가를 기반으로 순위를 매길 수 있으며, 이는 일부 솔루션이 다른 솔루션보다 우수하다는 것을 의미합니다.

목적 함수

목적 함수는 문제 영역에 따라 다릅니다.

테스트 함수, 예를 들어 특정 수의 입력 변수를 가진 잘 알려진 방정식일 수 있으며, 그 계산은 입력 비용을 반환합니다. 테스트 기능의 최적이 알려져 있으므로 검색 공간을 효율적으로 탐색하는 능력을 기반으로 알고리즘을 비교할 수 있습니다.

머신러닝에서 목적 함수는 후보 솔루션을 모델에 연결하고 학습 데이터 세트의 일부에 대해 평가하는 것을 포함할 수 있으며, 비용은 종종 모델 손실이라고 하는 오류 점수일 수 있습니다.

목적 함수는 정의하기 쉽지만 평가하는 데 비용이 많이 듭니다. 기능 최적화의 효율성은 총 기능 평가 횟수를 최소화하는 것을 의미합니다.

목적 함수는 정의하기 쉽지만 최적화하기가 어려울 수 있습니다. 목적 함수의 난이도는 미적분학 또는 선형 대수학을 사용하여 직접 함수를 분석적으로 풀 수 있는 것(쉬움), 로컬 검색 알고리즘(보통)을 사용하는 것, 전역 검색 알고리즘을 사용하는 것(어려움)에 이르기까지 다양할 수 있습니다.

목적 함수의 난이도는 함수에 대해 얼마나 많이 알려져 있는지에 따라 결정됩니다. 이것은 종종 후보 솔루션을 평가하기 위해 방정식이나 코드를 단순히 검토하여 결정할 수 없습니다. 대신 응답 표면의 구조를 나타냅니다.

반응 표면(또는 검색 환경)은 후보 솔루션의 검색 공간과 관련된 비용의 기하학적 구조입니다. 예를 들어, 매끄러운 반응 표면은 입력값(후보 솔루션)에 대한 작은 변화가 목적 함수의 출력(비용)에 작은 변화를 초래한다는 것을 나타냅니다.

• 반응 표면: 후보 솔루션의 변경에 대한 응답으로 목적 함수에서 비용의 기하학적 속성입니다.

반응 표면은 낮은 차원으로 시각화할 수 있습니다(예: 하나 또는 두 개의 입력 변수가 있는 후보 솔루션의 경우). 1차원 입력값은 x축에 입력 값이 있고 비용이 y축에 있는 2D 산점도로 플로팅할 수 있습니다. 2차원 입력값은 x축과 y축에 입력 변수가 있고 비용을 나타내는 표면의 높이가 있는 3D 표면도로 플로팅할 수 있습니다.

이 응답 표면의 구조와 모양은 알고리즘이 검색 공간을 솔루션으로 탐색하는 데 어려움을 겪게 될 것을 결정합니다.

실제 목적 함수의 복잡성은 표면을 분석적으로 분석할 수 없다는 것을 의미하며, 입력의 높은 차원성과 함수 평가의 계산 비용으로 인해 실제 목적 함수를 매핑하고 플로팅하는 것이 어렵습니다.

평가 비용

후보 솔루션의 비용은 거의 항상 단일 실수 값 숫자입니다.

비용 값의 척도는 목적 함수의 특성에 따라 달라집니다. 일반적으로 비용 값의 유일한 의미 있는 비교는 동일한 목적 함수로 계산된 다른 비용 값과 비교하는 것입니다.

함수의 최소 또는 최대 출력을 함수의 최적이라고 하며 일반적으로 최소값으로 단순화됩니다. 최대화하려는 모든 함수는 함수에서 반환된 비용의 앞에 음수 기호를 추가하여 최소화로 변환할 수 있습니다.

전역 최적화에서는 최적화 문제의 진정한 전역 솔루션이 발견됩니다. 타협은 효율성입니다. 글로벌 최적화 방법의 최악의 복잡성은 문제 크기에 따라 기하 급수적으로 증가합니다 …

— 페이지 10, 볼록 최적화, 2004.

목적 함수는 목적 함수의 전역 최적이라고 하는 단일 최상의 해를 가질 수 있습니다. 또는 목적 함수가 많은 전역 최적값을 가질 수 있으며,이 경우 하나 또는 모두를 찾는 데 관심이있을 수 있습니다.

많은 수치 최적화 방법은 국소 최소값을 찾습니다. 로컬 최소값은 로컬에서 최적이지만 일반적으로 로컬 최소값이 전역 최소값인지 여부는 알 수 없습니다.

— 8페이지, 최적화 알고리즘, 2019.

전역 최적값 외에도, 함수에는 로컬 최적값이 있을 수 있으며, 이는 비교적 쉽게 찾을 수 있지만 전역 최적값만큼 좋지는 않은 좋은 후보 솔루션입니다. 로컬 최적은 검색 알고리즘에 대한 전역 최적으로 보일 수 있습니다(예: 응답 표면의 계곡에 있을 수 있음).이 경우 알고리즘이 쉽게 찾을 수 있고 갇혀 전역 최적값을 찾지 못하기 때문에 기만적이라고 할 수 있습니다.

• 글로벌 최적: 목적 함수에서 가장 좋은 비용을 가진 후보 솔루션입니다.
• 로컬 옵티마. 후보 솔루션은 좋지만 글로벌 최적만큼 좋지는 않습니다.

비용 값의 상대적 특성은 순진한 검색 알고리즘(예: 무작위)을 사용하여 까다로운 문제에 대한 성능의 기준선을 설정할 수 있으며 보다 정교한 검색 알고리즘에 의해 발견된 최적 솔루션의 “장점”을 기준선과 비교할 수 있음을 의미합니다.

후보 솔루션은 종종 설명하기가 매우 간단하고 구성하기가 매우 쉽습니다. 기능 최적화의 어려운 부분은 후보 솔루션을 평가하는 것입니다.

함수 최적화 문제 또는 목적 함수를 푸는 것은 최적값을 찾는 것을 의미합니다. 프로젝트의 전체 목표는 비용이 좋거나 가장 좋은 특정 후보 솔루션을 찾고 사용 가능한 시간과 리소스를 제공하는 것입니다. 단순 및 중간 문제에서 최적의 후보 솔루션을 정확하게 찾을 수 있고 그렇게 했다는 확신을 가질 수 있습니다.

비선형 최적화 문제에 대한 많은 알고리즘은 목적 함수가 실현 가능한 다른 모든 근거리 점보다 작은 지점인 로컬 솔루션만 찾습니다. 그들은 항상 가능한 모든 점 중에서 함수 값이 가장 낮은 점 인 전역 솔루션을 찾는 것은 아닙니다. 일부 응용 프로그램에서는 글로벌 솔루션이 필요하지만 많은 문제에 대해 인식하기 어렵고 찾기가 훨씬 더 어렵습니다.

— 페이지 6, 수치 최적화, 2006.

더 어려운 문제에 대해서는 프로젝트에 사용할 수 있는 시간이 주어지면 비교적 좋은 후보 솔루션(예: 충분히 좋음)에 만족할 수 있습니다.

추가 정보

이 섹션에서는 더 자세히 알아보려는 경우 주제에 대한 더 많은 리소스를 제공합니다.

책

• 최적화를 위한 알고리즘, 2019.
• 볼록 최적화, 2004.
• 수치 최적화, 2006.

기사

• 수학적 최적화, 위키피디아.

요약

이 자습서에서는 함수 최적화에 대한 다음 내용을 배웠습니다.

• 후보 솔루션으로서의 기능 최적화의 세 가지 요소, 목적 기능 및 비용.
• 검색 공간과 응답 표면을 탐색하는 기능 최적화의 개념화.
• 함수 최적화 문제를 풀 때 전역 최적값과 국소 최적값의 차이입니다.