Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis

기술 요약: 제한된 데이터 환경에서의 무작위 부분 공간 샘플링에 관한 탐색적 경관 분석(ELA)

문제 정의
탐색적 경관 분석(Exploratory Landscape Analysis, ELA)은 결정 벡터와 목적 함수 값을 구조화된 수치적 특징(feature)으로 변환하여 블랙박스 최적화 문제를 특성화하는 데이터 기반 방법론이다. 이러한 기술자(descriptor)들은 알고리즘 선택, 설정 및 문제 분류와 같은 다운스트림 작업들을 지원한다. 그러나 ELA 특징의 신뢰도는 샘플 크수에 크게 의존한다. 고차원 최적화 문제나 함수 평가 비용이 높은 실제 응용 분야와 같이 자원이 제한된 환경에서는 표준적인 공간 채움 설계(예: 라틴 하이퍼큐브 샘플링)가 실패하는 경우가 많다. 샘플링 예산이 제한될 때, 이러한 설계들은 결정 공간에 대해 희소한 커버리지를 초래하며, 이는 특히 국소적 기하 구조나 이웃 관계에 의존하는 특징들의 추정치에서 높은 분산과 불안정성을 유발한다.

방법론
전역적 대표성과 국소적 샘플링 밀도 사이의 트레이드오프를 해결하기 위해, 저자들은 **무작위 선형 임베딩(random linear embeddings)**에 기반한 샘플링 전략을 제안한다. 고정된 예산을 $D$차원의 전체 주변 공간(ambient space)에 균등하게 배분하는 대신, 예산을 무작위로 방향이 정해진 저차원 아핀 부분 공간(affine subspaces)에 재할당한다.

본 연구는 20차원 설정($D=20$)과 노이즈가 없는 BBOB 테스트 스위트를 사용하여 네 가지 특정 샘플링 구성을 평가한다:

1. Full/ELAA: 전체 주변 공간에서의 균등 샘플링; 특징은 주변 공간에서 계산됨.
2. Sliced/ELAA (다중 임베딩): 예산을 $K$개의 $d$차원 무작위 임베딩에 분할함. 각 부분 공간에서 샘플을 생성하고, 이를 다시 주변 공간으로 매핑한 후, 이 점들의 합집합에 대해 특징을 계산함.
3. All_in/ELAA (단일 임베딩, 주변 공간 평가): 전체 예산을 단일 무작위 임베딩에 할당함. 점들을 주변 공간으로 매핑하여 평가하고, 특징은 주변 공간에서 계산함.
4. All_in/ELAR (단일 임베딩, 축소된 공간 평가): 전체 예산을 단일 무작위 임베딩에 할당함. 점들은 주변 공간에서 평가되지만, 특징은 축소된 $d$차원 부분 공간 내에서 직접 계산됨.

임베딩 행렬은 표준 정규 분포를 사용하여 생성되며, 유클리드 거리를 보존하기 위해 선택적으로 열 정규화(column normalization)를 수행한다. 경계 제약 조건을 처리하기 위해, 임베딩 공간에서 생성된 샘플은 주변 공간으로 매핑된 후 가용 영역 내로 클리핑(clipping)된다. 본 연구는 압축 비율($r = d/D$)로 0.1, 0.25, 0.5를 사용한다.

주요 기여

• 새로운 샘플링 전략 제안: 저자들은 사전 샘플링된 점들의 투영(projection)과 관련된 인위적인 왜곡을 피하기 위해, 고정된 평가 예산을 무작위로 생성된 저차원 부분 공간으로 재할당하여 유효 샘플링 밀도를 높이는 방법을 도입한다.
• 안정성에 대한 경험적 분석: 본 논문은 여섯 가지 고전적인 ELA 특징 세트(ela_distr, ela_level, ela_meta, nbc, disp, ic)와 24개의 BBOB 함수에 대해 전체 공간 샘플링과 임베딩 기반 샘플링 간의 특징 안정성을 비교하는 포괄적인 분석을 수행한다.
• 압축 비율 분석: 압축 비율의 변화가 미치는 영향을 조사하여, 샘플링 밀도 증가와 정보 손실 사이의 트레이드오프를 강조한다.
• 평가 프로토콜: 저자들은 제한된 예산에서 얻은 특징 분포와 고충실도 참조 분포(2000개 샘플) 사이의 Wasserstein-1 거리를 측정함으로써 이러한 전략들의 신뢰성을 평가한다.

결과
40개의 무작위 시드에 대해 집계된 실험 결과는 샘플링 전략의 효과가 특정 특징 클래스와 기저 문제 경관(landscape)에 따라 크게 달라짐을 보여준다:

• 특징 의존성:
  • 메타 모델 특징 (ela_meta): 선형 모델을 적합시키기 위해 전역적 커버리지가 필요한 특징의 경우, 일반적으로 Full-space 샘플링(Full/ELAA)이 부분 공간 방식보다 우수한 성능을 보인다.
  • 분산 (disp) 및 정보량 (ic): 임베딩 기반 샘플링, 특히 중간 정도의 압축 비율($r=0.5$)을 사용할 때 종종 전체 공간 샘플링과 대등하거나 더 나은 성능을 보이는데, 이는 이러한 특징들이 국소적 샘플링에 강건함을 시사한다.
  • 레벨 셋 특징 (ela_level): 축소된 공간에서 특징을 계산하는 단일 임베딩 전략(All_in/ELAR)이 일관되게 상위 순위를 차지한다.
• 압축 비율의 영향: 공격적인 압축(예: $r=0.1$)은 대부분의 특징 세트에서 성능을 체계적으로 저하시키며, 이는 경관 정보의 적절한 수준을 유지하는 것이 필요함을 나타낸다. $r=0.5$ 비율이 전반적으로 가장 좋은 트레이드오프를 제공한다.
• 전반적인 성능: $r=0.5$인 Sliced/ELAA 전략이 가장 우수한 컨센서스 랭킹(consensus ranking)을 달성하였으며, 특징 및 함수 집계 모두에서 일관되게 우수한 성능을 보였다. 그러나 모든 설정에서 통계적으로 우월한 단일 방법은 존재하지 않았다.

의의 및 주장
본 논문은 제한된 평가 예산 하에서 표준적인 균등 전체 공간 샘플링이 문제 경관을 특성화하는 데 있어 종종 최적이 아닐 수 있다고 결론짓는다. 저자들은 **구조화된 부분 공간 샘플링(structured subspace sampling)**이 특정 ELA 특징 서브셋의 안정성을 향상시킬 수 있는 유망한 대안이라고 주장한다.

이 연구의 의의는 샘플링에 대한 관점을 수동적인 데이터 수집 단계에서 능동적인 설계 선택으로 전환했다는 점에 있다. 샘플을 전체 공간에 희소하게 분산시키는 것보다 정보가 풍부한 부분 공간 내에 집중시키는 것이 더 신뢰할 수 있는 기술자를 생성할 수 있음을 입증함으로써, 저자들은 자원이 제한된 최적화 시나리오에서 경관 특성화를 강화할 수 있는 실질적인 메커니즘을 제공한다. 본 연구는 20차원 벤치마크에서 현재 검증되었으며, 전역 구조에 의존하는 특징들은 여전히 국소적 샘플링 하에서 어려움을 겪을 수 있다는 한계를 인정한다. 향후 연구에서는 낮은 고유 차원(low intrinsic dimensionality)을 가진 벤치마크를 탐색하고, 이러한 전략들이 다운스트림 알고리즘 선택 작업에 미치는 영향을 평가할 것을 제안한다.