On Stopping Rules and Spatial Adaptation for CART

컴퓨터가 데이터로부터 예측을 수행하는 방법을 배우는 머신러닝의 광활한 풍경 속에서, 가장 오래 지속되고 신뢰받는 도구 중 하나는 결정 트리(decision tree)입니다. 데이터에 대해 "온도가 70도 이상인가?" 또는 "소득이 50,000달러보다 많은가?"와 같은 일련의 간단한 질문을 던지는 순서도(flowchart)를 상상해 보십시오. 이 질문들은 답을 최종 결론에 도달할 때까지 특정 경로로 안내합니다. 이러한 모델들이 인기 있는 이유는 인간이 읽고 이해하기 쉬우면서도, 훨씬 더 복잡한 시스템과 경쟁할 수 있을 만큼 강력하기 때문입니다. 이러한 트리를 구축하는 표준 방법인 CART는 탐욕스러운 탐험가처럼 작동합니다. 매 단계마다, 현재의 데이터 그룹을 서로 최대한 다르게 만드는 두 부분으로 나눌 수 있는 단 하나의 질문을 찾습니다. 이 과정은 데이터를 점점 더 작은 직사각형 상자로 깎아 나가며 질문을 계속 던지다가, 멈추기로 결정할 때까지 계속됩니다.

통계학자들이 오랫동안 의문을 품어온 미스터리는 트리가 어떻게 성장하느냐가 아니라, 언제 멈추느냐 하는 것입니다. 멈춤을 위한 규칙은 매우 중요한데, 왜냐하면 그 규칙이 예측을 수행하는 국소적 이웃 역할을 하는 최종 상자의 크기를 결정하기 때문입니다. 만약 트리가 너무 일찍 멈추면 상자가 너무 커져서, 예측이 세부적인 특징을 놓치는 거친 평균값이 됩니다. 반대로 너무 늦게 멈추면 상자가 아주 작아져서, 실제 패턴이 아닌 데이터의 무작위적인 노이즈를 포착하게 됩니다. 분할 지점을 선택하는 방법은 광범위하게 연구되어 왔지만, 멈춤 규칙의 통계적 역할은 다소 불투명한 상태로 남아 있었습니다. 연구자들은 이 탐욕적인 트리들이 데이터의 복잡성을 미리 알려주지 않아도, 거칠고 울퉁불퉁한 영역에서는 정교하고 세밀한 예측을 하고 평탄하고 차분한 영역에서는 부드럽고 단순한 예측을 하는 식으로 데이터의 국소적 복잡성에 자동으로 적응할 수 있는지 오랫동안 궁금해해 왔습니다.

싱가포르 국립대학교의 연구진은 이제 이 질문에 대한 확정적인 답을 제시하며, 표준 CART 알고리즘이 특정 유형의 멈춤 규칙을 사용할 경우 실제로 이러한 공간적 적응을 달성할 수 있음을 증명했습니다. 그들의 연구는 가장 흔한 멈춤 결정 방식인 '모든 최종 상자에 최소한의 데이터 포인트가 포함되어야 한다'는 규칙이 적응에 실패한다는 것을 보여줍니다. 이 경직된 규칙은 트리가 매끄럽고 예측 가능한 영역과 혼란스럽고 노이즈가 많은 영역을 동일한 수준의 세밀함으로 처리하도록 강요하여, 한쪽 혹은 양쪽 모두에서 저조한 성능을 초래합니다. 반면, 분할을 통해 얻은 이득이 특정 임계값 아래로 떨어질 때 트리를 멈추는 다른 규칙은 알고 алгорит이 완벽한 균형을 찾을 수 있게 해준다는 것을 연구진은 증명했습니다. 이 임계값 기반 규칙은 민감한 게이지처럼 작동하여, 추가적인 분할이 더 이상 새로운 정보를 밝혀내지 못하고 단순히 무작위적인 변동을 쫓고 있을 뿐임을 자동으로 감지합니다.

연구진은 이 임계값 기반 규칙을 사용할 때, 트리가 데이터의 변화가 급격한 곳에서는 작고 세밀한 상자를 만들고, 데이터가 매끄러운 곳에서는 크고 단순한 상자를 자연스럽게 생성한다는 것을 보여주었습니다. 그들은 이 과정이 전체 데이터셋에 걸쳐 동시에 발생한다는 것을 수학적으로 증명했는데, 이는 트리가 어디가 거칠거나 매끄러운 패치인지 미리 알 필요 없이 모든 곳에서 국소적인 세부 사항을 정확히 잡아낸다는 것을 의미합니다. 이 발견은 결정 트리가 왜 실무에서 효과적인지를 설명해 줍니다. 즉, 결정 트리는 단순히 경직된 구조가 아니라, 데이터의 지형에 맞춰 스스로의 해상도를 조м 조정할 수 있는 적응형 도구라는 점입니다. 또한 이 연구는 이러한 적응이 데이터에 충분한 신호(signal)가 포함되어 트리가 유의미한 분할을 찾을 수 있다는 특정 구조적 조건에 의존함을 명확히 했으며, 데이터가 순수하게 무작위적이거나 분할 과정을 혼란스럽게 만드는 방식으로 구조화된 시나리오는 제외되었습니다.

왜 흔히 쓰이는 "최소 리프 크기(minimum leaf size)" 규칙이 실패하는지 이해하기 위해, 세계의 한 부분에서는 값이 천천히 변하고 다른 부분에서는 빠르게 변하는 값을 예측하려는 시나리오를 생각해 보십시오. 만약 규칙이 모든 최종 상자에 반드시 50개의 데이터 포인트가 포함되어야 한다고 요구한다면, 트리는 두 영역 모두에서 동일한 크기의 상자를 만들어야 합니다. 매끄러운 영역에서 이 상자는 불필요하게 작아져 노이즈를 포착하고 예측을 요동치게 만듭니다. 거친 영역에서는 상자가 너무 커져서 중요한 세부 사항을 뭉뚱그려 예측을 흐릿하게 만듭니다. 연구진은 어떤 단일한 최소 상자 크기도 두 영역의 요구를 동시에 만족시킬 수 없음을 입증했습니다. 하나의 크기가 모든 국소적 과업에 들어맞을 수는 없습니다.

대조적으로, 임계값 기반 규칙은 분할로부터 얻은 실제 가치를 측정함으로써 작동합니다. 트리가 데이터를 더 작은 조각으로 깎아 나감에 따라, 각 새로운 절단으로부터 얻는 이득은 결국 줄어들게 됩니다. 매끄러운 영역에서는 이득이 빠르게 감소하여 트리에 조기에 멈추도록 신호를 보내 큰 상자를 남기게 합니다. 거친 영역에서는 이득이 더 오랫동안 높게 유지되어, 트리가 미세한 세부 사항에 도달할 때까지 계속해서 자르도록 독려합니다. 연구진은 이 멈춤 지점이 해당 위치에서 예측을 수행하기 위한 최적의 크기와 정확히 일치한다는 것을 증명했습니다. 그들은 데이터의 신호가 배경 노이즈와 구별할 수 없을 정도가 될 때 트리가 정확히 분할을 멈추어, 최종 상자가 너무 크지도 너무 작지도 않도록 보장한다는 것을 보여주었습니다.

연구는 또한 데이터가 많은 다양한 특징(feature)을 가진 고차원 환경에서의 트리의 동작도 다루었습니다. 그들은 데이터가 관련 특징에 집중할 수 있게 하는 특정 구조적 패턴을 따를 경우, 동일한 적응 메커니즘이 유효하다는 것을 발견했습니다. 이는 트리가 무관한 정보는 무시하고 데이터가 실제로 변화하는 방향을 따라 핵심적인 변수에 집중할 수 있음을 의미합니다. 연구진은 이러한 조건들을 충족하는 복잡한 함수들의 예시를 제공하여, 이 이론이 광범위한 현실적인 시나리오에 적용될 수 있음을 보여주었습니다.

논문은 알고리즘의 이론적 보증에 초점을 맞추고 있지만, 실무적인 데이터 분석에 주는 시사점은 명확합니다. 이는 결정 트리의 성공이 우연이 아니라, 올바른 멈춤 규칙이 트리의 구조를 데이터의 국소적 기하학적 구조와 일치시키는 깊은 통계적 속성에 뿌리를 두고 있음을 시사합니다. 최소 불순도 감소(minimum impurity decrease) 규칙이 국소적 예측을 위한 최적의 정확도율을 달성한다는 것을 증명함으로써, 연구진은 이러한 모델들의 경험적 성공에 대한 견고한 이론적 토대를 마련했습니다. 또한 그들의 연구는 구현하기 더 쉬워 보일 수 있지만 궁극적으로 모델이 문제의 실제 복잡성에 적응하는 것을 방해하는 더 단순하고 경직된 멈춤 규칙을 사용하는 것에 대해 경고의 메시지를 전달합니다.

연구진은 올바른 규칙이 작동한다는 것을 증명하는 데 그치지 않고, 잘못된 규칙이 왜 실패하는지도 정확히 보여주었습니다. 상세한 수학적 논증을 통해, 그들은 단일한 전역적(global) 멈춤 파라미터가 서로 다른 매끄러움 수준을 가진 두 지점에서 편향(bias)과 분산(variance) 사이의 절충안을 동시에 최적화할 수 없음을 입증했습니다. 이것이 최소 리프 크기 접근 방식의 근본적인 한계입니다. 이 증명은 최적의 상자 크기가 거친 지점과 매끄러운 지점에서 현저히 다른 특정 사례들을 구성함으로써, 단일한 전역적 제약이 두 지점 모두를 제대로 수행하는 것이 불가능함을 보여줍니다.

실험에서 연구진은 거칠고 울퉁불퉁한 구간과 매끄럽고 선형적인 구간이 결합된 하이브리드 신호를 사용하여 이러한 차이를 시각화했습니다. 그들은 임계값 규칙을 사용하는 트리가 거친 구간에서는 작고 복잡한 상자를 만들고, 매끄러운 구간에서는 크고 단순한 상자를 만들어 데이터의 국소적 요구에 완벽하게 부합하는 것을 관찰했습니다. 그러나 최소 리프 크기 규칙을 사용하는 트리는 두 구간 모두에서 거의 동일한 크기의 상자를 생성하여, 모델의 구조와 데이터의 실체 사이에 명확한 불일치를 나타냈습니다. 이러한 시각적 증거는 그들의 이론적 발견을 뒷받집하며, 적응적 행동이 단순한 수학적 호기심이 아니라 알고리즘의 실질적인 특징임을 보여주었습니다.

논문은 멈춤 규칙이 알고리즘의 사소한 구현 세부 사항이 아니라, 알고리즘의 통계적 힘의 핵심 구성 요소임을 강조하며 끝을 맺습니다. 그것은 트리가 경직된 '일률적인(one-size-fits-all)' 구조에서 유연하고 국소적으로 적응 가능한 추정기로 전환할 수 있게 하는 메커니즘입니다. 이 적응이 발생하는 정확한 조건을 확립함으로써, 연구진은 최소 불순도 감소 규칙의 통계적 역할을 명확히 했습니다. 그들의 연구는 결정 트리의 실무적 성공과 왜 그것들이 작동하는지에 대한 이론적 이해 사이의 간극을 메우며, 복잡하고 이질적인 현실 세계의 데이터 지형을 항해하는 결정 트리의 능력에 대한 정밀한 설명을 제공합니다.