Note ≡ 탐욕적 탐색 알고리즘
탐욕적 알고리즘(greedy algorithm)은 조합 탐색(combinatorial search) 문제의 각 단계에서 국부적으로 최적의 선택을 합니다. 일반적으로 해당 문제에 대한 차선의 솔루션을 만듭니다. 완전 탐색 알고리즘(exhaustive search algorithm)은 모든 가능한 조합을 평가하므로 최적의 솔루션을 찾을 것이라고 보장됩니다. 실전에서는 완전 탐색이 계산하기 불가능한 경우가 많고 탐욕적 알고리즘이 덜 복잡하고 효율적으로 계산할 수 있는 솔루션을 만들 수 있습니다.
SBS 알고리즘 이면의 아이디어는 매우 간단합니다. SBS는 새로운 특성의 부분 공간이 목표하는 특성 개수가 될 때까지 전체 특성에서 순차적으로 특성을 제거합니다. 각 단계에서 어떤 특성을 제거할지 판단하기 위해 최대화할 기준 함수를 정의합니다.
기준 함수에서 계산한 값은 어떤 특성을 제거하기 전후의 모델 성능 차이입니다. 각 단계에서 제거할 특성은 기준 값이 가장 큰 특성으로 정의할 수 있습니다. 이해하기 쉽게 말하면 각 단계에서 제거했을 때 성능 손실이 최소가 되는 특성을 제거합니다. SBS 정의에 따라 이 알고리즘을 간단히 네 단계로 정리할 수 있습니다.