크로스 엔트로피 방법

교차 엔트로피 방법(CEM)은 중요도 샘플링과 엘리트 샘플 기반의 매개변수 업데이트를 사용하여 희귀 사건 추정 및 조합 또는 연속 최적화를 위한 반복적 확률적 최적화 기법입니다.

크로스 엔트로피 방법(CEM)은 어려운 최적화 및 희소 사건 추정 문제를 해결하기 위한 범용 몬테카를로 기법이다. 이 방법은 1997년 Reuven Rubinstein에 의해 희소 사건의 확률을 추정하는 방법으로 소개되었으며, 곧 조합 최적화 및 연속 최적화로 확장되었다. 이 방법은 반복적으로 매개변수화된 확률 분포에서 무작위 표본을 생성하고, 이를 평가한 다음, 가장 우수한 성과를 보인 표본 집합인 엘리트 집합에 집중하도록 분포 매개변수를 갱신한다. 이 접근법은 목적 함수가 노이즈가 있거나, 미분 가능하지 않거나, 또는 많은 지역 최적점을 갖는 문제에서 특히 효과적이다.

CEM의 핵심 아이디어는 최적 해에 모든 확률 질량을 부여하는 이상적인 분포와 표본 추출 분포 간의 크로스 엔트로피를 최소화하는 것이다. 실제로는 현재 분포에서 표본을 추출하는 단계와 엘리트 표본의 최대 우도 추정을 사용하여 분포를 갱신하는 단계를 반복적으로 수행함으로써 이를 달성한다. 이 방법은 구현이 간단하고, 하이퍼매개변수가 적으며, 종종 빠르게 수렴하기 때문에 강화 학습, 로보틱스, 수당 연구 등의 분야에서 널리 채택되고 있다.

알고리즘 프레임워크

크로스 엔트로피 방법은 반복 루프로 작동한다. 처음에는 솔루션 공간에 매개변수화된 분포(종종 다변량 가우시안 또는 범주형 분포)가 정의된다. 각 반복에서 후보 위치 묶음이 이 분포로부터 추출된다. 각 후보를 점수 함수를 이용해 평가하고, 상위 성능을 보이는 비율(일반적으로 10%에서 20%)이 엘리트 집단으로 선택된다. 그런 다음 분포 매개변수는 보통 가우시안 분포의 경우 표본 평균과 분포의 편차를 계산하거나 범주형 분포의 경우 표본의 경험적 빈도를 계산하여 이러한 엘리트 표본에 적합하도록 갱신된다.

조기 수렴을 방지하기 위해 스무딩 매개변수자체가 분포의 새 매개변수와 이전 매개변수를 블렌딩하는데 도입되는 경우가 많다. 이 스무딩은 탐색을 유지하고 지역 최적값에 빠지는 것을 피하는 데 도움이 된다. 프로세스는 최대 반복 수 또는 최고 점수의 무시 가능한 변화와 같은 중지 조건을 충족할 때까지 반복된다.

기계 학습 응용

Machine learning에서 CEM은 하이퍼파라미터 최적화, 신경 구조 탐색, Reinforcement learning 맥락에서의 정책 훈련 등에 사용되었다. 예를 들어, Deep learning에서 CEM은 역전파 없이 소규모 Neural network의 가중치를 최적화할 수 있으며, 그 지점이 경사가 없거나 비싸 때 특히 유용하다. 또한 Large language model의 패턴 전송 가능하지 않은 이산 프롬프트 최적화에도 적용되었으며, 검색 공간은 조합형이다.

Artificial intelligence 연구에서 CEM은 진화 전략 및 Stochastic Gradient Descent Variants과 종종 비교된다. 경사 기반 방법과 달리 CEM은 목적의 미분 가능성을 요구하지 않으므로 블랙박스 최적화에 적합하다. 로보틱스에서는 Robotics의 궤적 최적화에 사용되며 자율 주행 시스템의 매개변수 조정에도 활용되어 왔다.

희소 사건 추정과의 관계

CEM의 원래 동기는 시스템 고장이나 극단적인 금융계 손실과 같은 희소 사건의 확률을 추정하는 것이였다. 이 맥락에서 방법은 중대한 샘플링을 이용해 분산을 줄인다. 알고리즘은 관심 지역을 강조하는 표집 분포를 적응적으로 구성하여 몬테 카를로의 케이스보다 훨씬 적은 표본으로 정확한 추정을 가능하게 한다. 이러한 이중 용도-최적화 및 추정-는 표본 분포와 최적의 중요도 표본 추출 분포 사이의 Kullback-Leibler 발산을 최소화하는 동일한 수학적 기초에서 비롯된다.

확장 및 변형

CEM의 여러 확장이 개발되었다. 연속 버전은 가우시안 또는 가우시안 혼합(II)을 사용하는 반면, 이산 버전은 순회 판매자 문제와 같은 조합 문제를 처리한다. 주목할 만한 변형으로 개선된 크로스 엔트로피 방법이 있으며, 과거 엘리트 표본의 기억을 포함해 갱신을 안정화한다. 또 다른 확장은 모델 기반 강화 학습에서 CEM을 사용하는 것으로, 학습된 세계 스무딩 위한 것 그 자체의 계획과 행동을 실행하는 것이다. 이 접근법은 잠재한 Deep Reinforcement Learning 알고리즘에서 추구한 방식으로 Model-Based Policy Optimization(MBPO) 프레임워크 등에서 제시되었다.

CEM은 또한 Curriculum Learning과 결합되어 샘플의 난이도를 점진적으로 증가시키거나, Data Augmentation과 함께 사용되어 견고한 최적화를 수행한다. Bayesian Optimization에서 CEM은 새로운 샘플 획득 함수의 최적화기 역할을 할 수 있다.

실용 고려 사항

CEM을 적용할 때, 분포 클래스의 선택과 엘리트 비율이 중요하다. 너무 작은 엘리트 비율은 갑작스러운 수렴을 초래할 수 있으며, 너무 큰 비율은 진행을 늦출 수 있다. 스무딩 매개변자는 종종 0.5와 0.9 사이로 설정되어 탐색과 활용 간의 균형을 잡는다. 고차원 문제의 경우, 반복당 샘플 수가 이에 맞게 증가해야 하므로 불필요한 계산 비용이 발생할 수 있다. 이러한 어려움에도 불구하고 CEM의 요율성과 견고성은 최적화 도구 상자에서 핵심적인 도구가 되게 하였다.

실제로 CEM은 연구 논문에서 주로 기준선으로 사용되며 여러 글로벌 하이퍼 문제에서 Bayesian Optimization과 같은 더 복잡한 방법과 성능이 견줄 정도로 우수하다. 다양한 오픈 소스 라이브러리에서 CEM으로 구현되어 있으며, Python의 cma 패키지가 이에 해당하지만 기존 CEM은 CMA-ES(공분산 행렬 적응 진화 전략)와는 별개의 알고리즘이다.