기술 요약: 관련성 인지 규칙: 의사결정 나무에서의 무관한 조건의 구조적 삭제

1. 문제 정의

의사결정 나무는 $C_1 \land C_2 \land \dots \land C_r \Rightarrow y = c$ 형태의 해석 가능한 if-then 규칙을 생성한다. 그러나 트리 유도(induction)의 재귀적 특성으로 인해, 이러한 루트-리프 경로는 종종 무관한 조건(Irrelevant Conditions, IRCs)—특정 리프의 최종 결정에 기여하지 않는 전제 조건들—을 축적하게 된다.

IRCs를 제거하는 기존 방법들은 다음과 같은 트레이드오프에 직면한다:

• 전역적 트리 단순화 (가지치기/최적화): 전체 트리 크기를 줄이지만, 자식 노드들이 상위 조건을 모두 상속받기 때문에 개별적으로 살아남은 리프 규칙을 반드시 단축시키지는 못한다.
• 경험적 규칙 사후 가지치기 (예: Quinlan, 1987): 통계적 테스트를 기반으로 전제 조건을 삭제하여 예측 성능을 개선한다. 그러나 이는 분할 트리(partitioning trees)를 충돌 해결이 필요한 중첩된 규칙 집합으로 변환할 수 있으며, 원래 트리의 신뢰 구조를 보존하지 못한 채 규칙의 모집단(ancestor-rule assimilation)을 변경할 수 있다.
• 논리적 경로 중복성 테스트 (예: Izza et al., 2022): 클래스 결과가 엄격히 보존되는 경우에만 삭제를 인증한다. 이는 정확하지만, 왜 특정 조건이 무관해지는지에 대한 구조적 설명을 결여하고 있으며 지나치게 보수적일 수 있다.

본 연구가 다루는 핵심 문제는, 단순히 최종 클래스 레이블만을 보존하는 것이 아니라, 원래 규칙의 **신뢰성(reliability)**과 **의미(meaning)**를 엄격히 보존하면서 의사결정 나무의 **분할 메커니즘(splitting mechanics)**에 기반하여 IRC를 식별하는 방법이 부족하다는 점이다.

2. 방법론: 구조적 삭제 프레임워크

저자들은 관련성 인지 구조적 IRC 삭제(Relevance-Aware Structural IRC Deletion) 프레임워크를 제안한다. 핵심 통찰은 이진 분할(binary split)에서 부모 클래스의 비율은 두 자식 노드의 가중 평균이라는 점이다. 결과적으로, 한 자식이 클래스 1의 비율을 높인다면, 형제 노드는 클래스 0의 비율을 높여야 한다.

2.1. 구조적 진단 (C1/C0 링크)

프레임워크는 C1-링크(클래스 1 비율을 증가시킴)와 C0-링크(클래스 0 비율을 증가시킴)를 도입한다.

• 매치된 링크 (Matched Link): 클래스 $c$인 리프로 향하는 경로에서 클래스 $c$의 비율을 높이는 링크.
• 미스매치된 링크 (Mismatched Link): 클래스 $c$인 리프로 향하는 경로에서 반대 클래스($1-c$)의 비율을 높이는 링크.

결정적으로, 미스매치된 링크는 구조적으로 의심스럽지만(structurally suspicious) 반드시 무관한 것은 아니다. 프레임워크는 세 가지 분석 계층을 통해 구조적 후보와 실제 삭제를 구분한다:

1. 로컬 어노테이션 (Local Annotation): 링크를 C1, C0 또는 중립(neutral)으로 태깅.
2. 리프 상대적 진단 (Leaf-Relative Diagnosis): 리프 클래스에 대해 링크를 매치(matched) 또는 미스매치(mismatched)로 분류.
3. 경로 수준 효과 (Path-Level Effect): 삭제가 규칙 신뢰성에 미치는 영향 평가.

2.2. 두 가지 상호 보완적 절차

프레임워크는 각각 구체적인 보증을 가진 두 가지 별개의 삭제 방법을 구현한다.

방법 1: 미스매치 가이드 삭제 (광범적 압축)

이 방법은 C1/C0 미스매치를 후보로 사용하되, 관련성을 보장하기 위해 설정별 수용 기준을 적용한다.

• 결정론적 설정 (M1-D): 엄격한 미스매치 세트는 **결합 하드-함의 인증(joint hard-implication certificate)**이 충족되는 경우에만 삭제된다 (즉, 약화된 규칙이 도메인의 모든 사례에 대해 올바른 클래스를 여전히 함의해야 함). 이는 정리 1(Joint Monotone Weakening)에 의존한다.
• 클래스-확률 설정 (M1-P):
  • 보호 (Protection): $H_c(L)$(클래스 $c$인 리프들만을 포함하는 가장 큰 조상 서브트리) 내부의 미스매치는 "부정적 관련성 가정(negative-relevance-presumed)"으로 취급되어 보호된다. 이 링크들은 동일한 클래스에 대한 신뢰성 정교화를 인코딩할 수 있기 때문이다.
  • 삭제 (Deletion): $H_c(L)$ 외부의 미스매치는 "IRC 가정(IRC-presumed)" 후보로 취급된다. 이들은 양방향 신뢰성 기준이 충족될 때만 삭제된다 (즉, 규칙 신뢰성의 변화 $D_c(Q; R)$가 허용 오차 $\epsilon$ 이내여야 함, $|D_c(Q; R)| \le \epsilon$). 이는 삭제가 신뢰성을 유의미하게 낮추거나(양의 관련성 효과), 의미 있는 정교화를 제거(음의 관련성 효과)하지 않음을 보장한다.

방법 2: 형제 인증 삭제 (정확한 보존)

이 방법은 링크의 방향성이 아닌 **토폴로지(topology)**에 의존한다.

• 메커니즘: 만약 하나의 분할에서 한 자식은 클래스 $c$인 리프이고, 다른 자식은 클래스 $c$인 자식 리프를 포함하는 내부 노드라면, 해당 내부 노드로 향하는 링크는 IRC이다.
• 보증: 이러한 링크를 삭제하는 것(정리 2)은 도메인이나 샘플 크기에 관계없이 피팅된 트리의 예측, 전체 커버리지, 그리고 **반대 클래스 규칙 충돌 제로(zero opposite-class rule conflict)**를 보장한다. 이 방법은 C1/C0 방향성과 독립적이다.

3. 주요 기여

1. IRC의 구조적 메커니즘: 본 논문은 이진 분할이 본질적으로 상보적인 C1/C0 링크를 생성함을 입증하여, 의심스러운 조건을 식별하기 위한 구조적 근거를 제공한다.
2. 정형화된 관련성 의미론: 경로 수준의 관련성을 세 가지 계층(어노테이션, 진단, 효과)을 통해 정의하며, "레이블 보존"과 "신뢰성 보존"을 구분한다.
3. 확장 가능한 프레임워크: 제안된 방법들은 리프 규칙의 수에 대해 선형적 확장성($O(n_L D)$ 또는 $O(n_L D^2)$)을 달성하며, 이는 기존의 논리적 테스트($O(n_L^2 D^2)$) 및 경험적 가지치기($O(n_L D^3)$)보다 실행 시간 면에서 크게 우수하다.

4. 실험 결과

연구는 결정론적 의사결정 테이블(Weather, Human ID)과 8개의 클래스-확률 데이터셋(UCI/OpenML)을 사용하여 Quinlan (1987) 및 Izza et al. (2022) 절차와 프레임워크를 평가한다.

4.1. 결정론적 설정

• M1-D와 Izza는 동일한 조건 제거율(Weather 데이터셋에서 30.43%)을 달성했으며, 둘 다 M2-D(21.74%)보다 우수한 성능을 보였다.
• 모든 방법은 100% 커버리지와 제로 반대 클래스 충돌을 유지했다.

4.2. 클래스-확률 설정

• 단순화:
  • M1-P는 M2-P 및 Izza보다 훨씬 더 많은 조건을 제거했다 (영향을 받은 규칙의 전제 조건 중 약 35% 제거 vs 타 방법의 ~23%). 이는 보수적인 Izza 방법과 공격적인 Quinlan 방법 사이의 간극을 메운다.
  • Quinlan은 가장 많은 조건을 제거했으나(~64%), 그 대가가 컸다.
• 충실도 (Fidelity):
  • M2-P와 Izza는 정확도 변화 제로 및 규칙 충돌 제로(정확한 보존)를 유지했다.
  • M1-P는 낮은 충돌률(~2.3–2.8%)과 낮은 클래스별 편차(MacroDev < 1 percentage point)와 함께 작은 정확도 이득(+0.51 ~ +0.63 퍼센트 포인트)을 얻었다.
  • Quinlan은 높은 충돌률(>50%)과 상당한 클래스별 편차(MacroDev > 5 percentage points)를 보였으며, 이는 원래 트리의 행동 구조가 손실되었음을 나타낸다.
• 확장성:
  • M2-P가 가장 빨랐으며, 트리 크기에 선형적으로 비례하고 샘플 크기($M$)와는 독립적이었다.
  • M1-P는 $M$에 선형적으로 비례했으나, Quinlan 절차보다 수적으로 훨씬 빨랐다 (예: 128개 리프에서 약 944배 빠름).

5. 의의 및 주장

본 논문은 **관련성 인지 규칙(relevance-aware rules)**이 단순히 가장 짧은 전제 조건 집합이 아니라, 삭제 근거와 보존 대상이 명시적인 규칙임을 주장한다.

• 구조적 충실성: 경험적 가지치기가 규칙 영역을 관련 없는 모집단으로 확장할 수 있는 것과 달리, 제안된 프레임워크는 구조적 신호(C1/C0, 형제 토폴로지)를 사용하여 삭제가 트리의 구성 로직에 근거하도록 보장한다.
• 길이보다 신뢰성: 연구는 "더 짧은 것"이 반드시 "더 나은 것"은 아니라고 주장한다. 관련성 인지 규칙은 (클래스 레이블을 바꾸지 않더라도) 신뢰성 정교화에 필수적인 조건은 보존하는 동시에, 구조적 및 경험적으로 중복되는 조건은 제거한다.
• 균형 잡힌 트레이드오프: 프레임워크는 조절 가능한 스펙트럼을 제공한다: 방법 2는 보수적이고 정확한 보존을 제공하며, 방법 1은 엄격한 신뢰성 제어를 통한 광범한 압축을 제공한다. 두 방법 모두 순수 경험적 사후 가지치기와 관련된 높은 충돌률을 피한다.

저자들은 의사결정 트리 규칙 단순화가 단순히 제거된 조건의 수가 아니라, 어떤 조건이 제거되었는지, 왜 그 삭제가 정당화되는지, 그리고 어떤 규칙의 의미가 보존되었는지에 의해 평가되어야 한다고 결론짓는다.