Experiments with Optimal Model Trees

이 논문은 선형 서포트 벡터 머신을 리프 노드로 사용하는 최적 모델 트리를 혼합 정수 선형 프로그래밍을 통해 학습하고, 기존 탐욕적 알고리즘 및 다른 머신러닝 모델과 비교하여 해석 가능성과 정확도 측면에서 경쟁력 있는 성능을 입증했습니다.

핵심

1. 문제: "현실적인 요리사" vs "완벽한 건축가"

기존의 방법 (그리디 알고리즘):
기존의 결정 트리를 만드는 알고리즘은 마치 **"매 순간 가장 맛있는 재료를 고르는 요리사"**와 같습니다.

• 방식: 데이터를 쪼개면서 "지금 당장 가장 좋은 선택은 뭐지?"라고 생각하며 하나씩 나무를 키워갑니다.
• 단점: 지금 당장은 맛있어도, 나중에 전체 요리의 맛을 망칠 수 있습니다. 그래서 나무가 너무 커지고 복잡해져서, **"왜 이렇게 만들었지?"**라고 묻기 힘들어집니다. (국소 최적해)

이 논문이 제안하는 방법 (MILP 기반 최적 모델 트리):
이 논문은 **"전체 건물을 설계하는 건축가"**처럼 접근합니다.

• 방식: 나무를 하나씩 키우는 게 아니라, **"최종적으로 가장 작고 정확한 나무가 어떤 모습이어야 할지"**를 수학적으로 한 번에 계산합니다. (전역 최적해)
• 특징: 나무의 잎 (Leaf) 에 단순히 'A'나 'B'라는 답만 적는 게 아니라, **수학 공식 (선형 모델)**을 적어넣습니다.
  • 예시: "나이가 30 세 이상이고, 월급이 500 만 원 이상이면 -> 공식 (A) 을 적용해서 예측"
  • 이렇게 하면 나무의 크기는 작아지는데, 예측 정확도는 오히려 더 높아집니다.

2. 핵심 기술: "수학적 마법 (MILP)"

이 연구는 **혼합 정수 선형 계획법 (MILP)**이라는 수학적 도구를 사용했습니다.

• 비유: 마치 퍼즐을 풀 때, 조각을 하나씩 끼워 맞추는 게 아니라, **"완성된 그림을 보고 모든 조각이 어디에 맞춰져야 하는지 한 번에 계산하는 것"**입니다.
• 결과: 이 방법으로 만든 나무는 기존 방법보다 훨씬 작지만 (간결함), 정확도 (성능) 는 떨어지지 않거나 오히려 더 좋습니다.

3. 실험 결과: "작은 나무가 더 강력하다"

저자들은 25 개의 다양한 데이터 세트 (질병 진단, 주가 예측 등) 로 실험을 했습니다.

• 정확도: 기존에 널리 쓰이던 방법 (랜덤 포레스트 등) 과 비교했을 때, 이 새로운 방법은 비슷하거나 더 좋은 정확도를 보여주었습니다.
• 크기: 가장 큰 장점은 나무의 크기입니다. 기존 방법들은 설명하기 힘들 정도로 거대한 나무를 만들지만, 이 방법은 작은 나무로 같은 성능을 냈습니다.
  • 비유: 거대한 백과사전 10 권을 읽지 않아도, 핵심 요약본 1 권만 읽으면 모든 답을 알 수 있는 셈입니다.
• 해석 가능성: 나무가 작고, 잎에 수학적 공식이 들어있기 때문에, **"왜 이런 결론이 나왔는지"**를 사람이 쉽게 이해할 수 있습니다. (예: "이 환자는 나이가 많고 혈압이 높아서 위험합니다"라고 명확히 설명 가능)

4. 한계점: "시간이 많이 걸리는 대가"

이 완벽한 방법에는 단점이 하나 있습니다. 계산 시간이 매우 오래 걸립니다.

• 비유: 완벽한 건축 도면을 그리는 데는 시간이 걸리지만, 일단 그려지면 그 건물은 튼튼하고 효율적입니다. 반면, 기존 방법은 "일단 빨리 지어보자"라고 해서 금방 지지만, 나중에 고치기 힘들고 비효율적일 수 있습니다.
• 현실: 데이터가 너무 크면 계산이 끝날 때까지 시간이 너무 오래 걸려서 (1 시간 이상), 실제 적용이 어렵습니다. 하지만 데이터 크기가 적당하거나, **정확도와 설명 가능성이 생명인 분야 (의료, 금융 등)**에서는 매우 유용합니다.

5. 요약: 왜 이 연구가 중요한가요?

이 논문은 **"작고 간결한 나무로 큰 성과를 내는 방법"**을 증명했습니다.

1. 이해하기 쉬움: 복잡한 AI 의 결정 과정을 사람이 쉽게 이해할 수 있게 해줍니다. (블랙박스 문제 해결)
2. 효율성: 불필요하게 큰 모델을 만들지 않아도 됩니다.
3. 정확성: 작아졌다고 해서 성능이 떨어지지 않습니다.

결론적으로, 이 연구는 "AI 는 복잡할수록 좋은 게 아니다. 적당히 작고, 논리적이고, 정확한 AI가 진짜로 필요한 곳 (의료, 법률 등) 에서 큰 역할을 할 수 있다"는 것을 보여줍니다.

기술 요약

논문 요약: 최적 모델 트리 (Optimal Model Trees) 에 대한 실험적 연구

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 의사결정나무 (Decision Trees) 는 해석 가능성 (Interpretability) 이 뛰어나지만, 전통적인 트리는 잎 노드 (Leaf Node) 에 상수 값만 가지기 때문에 예측 정확도를 높이기 위해 트리가 불필요하게 커지는 경향이 있습니다. 이를 해결하기 위해 잎 노드에 선형 회귀나 로지스틱 회귀 모델을 도입한 **모델 트리 (Model Trees)**가 제안되었습니다.
• 문제점: 기존 모델 트리 학습 알고리즘 (M5P, CART 등) 은 탐욕적 (Greedy) 방식으로 작동합니다. 즉, 각 노드에서 국소적으로 최적의 분할 (Split) 을 선택하여 트리를 성장시키므로, 전체적으로 최적의 구조를 보장하지 못합니다. 이로 인해 트리가 복잡해지거나 예측 정확도가 낮아질 수 있습니다.
• 목표: 전역 최적 (Globally Optimal) 인 모델 트리를 학습하여, 작은 크기의 트리로 높은 예측 정확도를 달성하고 해석 가능성을 유지하는지 실증적으로 검증하는 것입니다.

2. 방법론 (Methodology)

이 연구는 **혼합 정수 선형 계획법 (MILP, Mixed-Integer Linear Programming)**을 사용하여 전역 최적의 모델 트리를 구축하는 새로운 프레임워크를 제안합니다.

• 핵심 접근법:
  • 이산적 구조와 연속적 매개변수의 동시 최적화: 트리의 구조 (분할 여부, 분할 순서) 는 이산적 변수로, 잎 노드의 선형 모델 계수는 연속적 변수로 정의하여 MILP 로 통합 최적화합니다.
  • 잎 노드 모델: 분류 문제에는 **선형 SVM (Support Vector Machine)**을, 회귀 문제에는 선형 회귀 SVM을 잎 노드에 배치합니다.
  • 트리 구조: 완전 트리 (Perfect Tree) 형태의 가상의 구조를 정의하고, MILP 변수를 통해 실제 분할이 일어나는 노드와 분할이 일어나지 않는 노드를 선택하여 실제 트리를 유도합니다.
• 수식화 (Formulation):
  • 분할 변수: $d_n$ (노드 분할 여부), $a_{f,n}$ (특성 선택), $b_n$ (분할 임계값).
  • 모델 변수: $\beta_{f,n}$ (SVM 가중치), $\delta_n$ (절편), $\epsilon_{i,n}$ (오차/마진).
  • 목적 함수: SVM 의 정규화 항 (가중치의 L1 노름) 과 오차 항을 최소화하도록 설계되었습니다.
  • 제약 조건: 데이터 포인트가 정확히 하나의 잎 노드로 이동하도록 보장, 분할의 일관성 유지, SVM 마진 조건 등을 MILP 제약식으로 표현합니다.
• 변형:
  • 단변량 (Univariate): 하나의 특성만 기준으로 분할 (해석 가능성 높음).
  • 다변량 (Multivariate): 특성의 선형 조합으로 분할 (정확도 향상 가능, 해석 가능성 저하).
• 하이퍼파라미터 튜닝: 정규화 계수 $C$와 최대 분할 수 $S$에 대해 검증 집합 (Validation Set) 을 사용하여 최적의 조합을 탐색합니다.

3. 주요 기여 (Key Contributions)

1. 최적 모델 트리를 위한 새로운 MILP 공식화: 분류 (OCMT) 와 회귀 (ORMT) 모두에 적용 가능한 MILP 기반 최적 모델 트리 학습 알고리즘을 제안했습니다. 특히 분류를 위한 SVM 기반 공식화는 기존 연구에서 다루지 않았던 새로운 접근입니다.
2. 광범위한 실증적 평가: OpenML 의 20 개 이진 분류, 5 개 다중 클래스 분류, 20 개 회귀 데이터셋을 대상으로 실험을 수행했습니다.
3. 비교 대상의 다양성:
   • 기존 최적 트리 알고리즘 (OCT, ORT, DL8.5).
   • 탐욕적 모델 트리 (LMT, M5P, LS-OMT).
   • 랜덤 포레스트 (RF), SVM, CART 등.
4. 다변량 분할의 영향 분석: 해석 가능성을 희생하고 다변량 분할을 도입했을 때의 정확도 향상 효과를 분석했습니다.

4. 실험 결과 (Results)

• 예측 정확도:
  • 모델 트리 vs. 일반 트리: 동일한 최대 깊이에서 **최적 모델 트리 (OCMT/ORMT)**는 잎 노드가 상수인 **최적 트리 (OCT/ORT)**보다 훨씬 높은 예측 정확도를 달성했습니다 (분류의 경우 최대 30% 이상 향상).
  • 탐욕적 알고리즘 대비: 랜덤 포레스트나 SVM 에 비해 정확도는 약간 낮을 수 있으나, CART, M5P, LMT 등 기존 탐욕적 알고리즘과 비슷하거나 더 나은 정확도를 보이면서도 트리의 크기가 훨씬 작았습니다.
• 모델 크기 (해석 가능성):
  • 제안된 최적 모델 트리는 다른 알고리즘에 비해 **일관되게 작은 크기 (적은 잎 노드 수)**를 가졌습니다.
  • 예를 들어, CART 나 LMT 는 수십 개에서 수백 개의 잎 노드를 가지는 경우가 많았으나, MILP 기반 모델 트리는 대부분 10 개 미만의 잎 노드로 제한되었습니다.
• 단변량 vs. 다변량:
  • 다변량 트리 (OCMT-H, ORMT-H) 가 단변량 트리보다 정확도가 높을 것으로 예상되었으나, 실제 실험에서는 단변량 트리가 다변량 트리보다 더 일관된 성능을 보였습니다. 일부 데이터셋 (Parity, Long) 에서만 다변량 트리가 큰 개선을 보였습니다.
• 계산 비용 (Scalability):
  • 시간 제한: 3600 초의 시간 제한 내에서 2 개 이상의 분할 (잎 노드 3 개 이상) 을 가진 트리를 최적화하는 것은 대부분의 경우 시간 초과 (Time-out) 되었습니다.
  • 실용성: 시간 초과가 발생하더라도, MILP 솔버가 반환한 해 (해) 는 탐욕적 알고리즘의 결과와 경쟁력 있는 성능을 보였습니다. 특히 데이터 크기가 작거나 중간 규모이며, 해석 가능성과 정확도가 최우선인 시나리오에 적합합니다.

5. 의의 및 결론 (Significance & Conclusion)

• 해석 가능성과 정확도의 균형: 이 연구는 MILP 를 활용하여 작고 정확한 모델 트리를 학습할 수 있음을 입증했습니다. 이는 "Black-box" 모델 (랜덤 포레스트, 딥러닝 등) 의 정확도와 "White-box" 모델 (작은 트리) 의 해석 가능성 사이의 간극을 줄이는 중요한 통찰을 제공합니다.
• 실무 적용: 계산 시간이 길다는 단점이 있으나, 의료, 금융 등 해석 가능성이 필수적인 분야나 데이터 크기가 제한된 환경에서 매우 유용한 대안이 될 수 있습니다.
• 향후 과제: 계산 효율성을 높이기 위해 분해 기법 (Decomposition methods) 을 적용하거나, 최적 정책 트리 (Optimal Policy Trees) 로의 확장을 모색할 필요가 있습니다.

요약하자면, 이 논문은 탐욕적 알고리즘의 국소 최적 문제를 해결하기 위해 MILP 기반의 전역 최적 모델 트리를 제안하고, 이를 통해 매우 작은 크기의 트리 구조로도 높은 예측 성능을 달성할 수 있음을 실증적으로 증명했습니다.