결정 목록(decision list)은 분류 또는 예측 작업을 정렬된 if-then 규칙의 순서로 표현하는 기계 학습 모델이다. 각 규칙은 조건(하나 이상의 입력 특성에 대한 검사)과 결과(클래스 레이블 또는 예측 값)로 구성된다. 새 인스턴스가 제시되면 모델은 목록에 나타난 순서대로 규칙을 평가하며, 조건이 충족되는 첫 번째 규칙의 결과가 예측으로 반환된다. 일치하는 규칙이 없으면 기본 결과, 일반적으로 훈련 데이터에서 가장 흔한 클래스가 사용된다. 이러한 구조는 결정 목록을 본질적으로 해석 가능하게 만드는데, 전체 결정 과정이 단순한 선형 지침 집합으로 읽힐 수 있기 때문이다.
결정 목록은 규칙 기반 학습의 한 형태로, 계층적 분기 구조를 사용하는 결정 트리와는 구별된다. 결정 목록의 순차적 특성은 앞선 규칙이 이후 규칙보다 우선함을 의미하며, 복잡한 결정 경계를 간결하게 표현할 수 있게 한다. 이는 의료 진단, 신용 평가, 법적 추론과 같이 설명 가능성이 중요한 영역에서 특히 유용하며, Machine learning 및 Artificial intelligence 맥락에서 광범위하게 연구되어 왔다.
역사적 기원
결정 목록의 개념은 1990년대 초 컴퓨터 과학자 로널드 리베스트(Ronald Rivest)에 의해 공식화되었으며, 그는 1987년 논문 "결정 목록 학습(Learning Decision Lists)"에서 이를 소개했다. RSA 암호 시스템 연구로 알려진 리베스트는 예제로부터 부울 함수를 학습하는 방법으로 결정 목록을 제안했다. 그는 고정 크기의 결정 목록이 PAC 학습 가능(PAC-learnable, probably approximately correct)임을 보였으며, 이는 합리적인 수의 훈련 예제로부터 효율적으로 학습될 수 있음을 의미한다. 이러한 이론적 기반은 결정 목록을 당시 덜 이해되고 훈련하기 어려웠던 신경망과 같은 더 복잡한 모델에 대한 실용적 대안으로 자리매김하게 했다.
리베스트의 연구는 Carnegie Mellon University 연구원 ross quinlan이 개발한 결정 트리용 ID3 알고리즘과 같은 초기 규칙 유도 연구에 기반을 두었다(제공된 슬러그 목록에는 없지만 그의 영향력은 주목할 만하다). 결정 목록은 이후 연속 특성과 다중 클래스 문제를 처리하도록 확장되었으며, 귀납적 논리 프로그래밍 분야의 핵심 요소가 되었다.
알고리즘 학습
데이터로부터 결정 목록을 학습하는 것은 일반적으로 탐욕적 접근 방식을 포함한다. 알고리즘은 빈 목록으로 시작하여 훈련 인스턴스의 하위 집합을 포함하는 최상의 규칙을 반복적으로 선택하고, 해당 인스턴스를 제거한 후 남은 데이터에 대해 과정을 반복한다. "최상의" 규칙은 종종 정확도, 정보 이득, 또는 커버리지와 정밀도의 조합과 같은 지표를 기반으로 선택된다. 이 과정은 모든 인스턴스가 포함되거나 최소 남은 인스턴스 수 또는 최대 목록 길이와 같은 중지 기준이 충족될 때까지 계속된다.
이 알고리즘의 변형에는 여러 후보 규칙을 동시에 탐색하는 빔 검색(beam search) 사용과 과적합을 피하기 위한 가지치기 기법 통합이 포함된다. 예를 들어, 1980년대 후반에 개발된 CN2 알고리즘은 순서가 있는 규칙을 유도하기 위해 빔 검색을 사용하며, 이는 결정 목록 학습과 밀접하게 관련된다. 더 최근의 접근 방식은 훈련된 Neural network 모델에서 규칙을 추출하는 규칙 추출(rule extraction) 과정을 통해 결정 목록을 Deep learning과 통합하여 해석 가능성을 개선한다.
응용 및 장점
결정 목록의 주요 장점은 투명성이다. Large language model이나 Transformer (architecture) 기반 시스템과 달리 블랙 박스로 작동하지 않으며, 결정 목록은 인간이 검사하고 이해할 수 있어 고위험 결정에 적합하다. 예를 들어, 의료 분야에서 결정 목록은 "나이가 60세 초과이고 혈압이 140 초과이면 고위험"과 같은 규칙을 인코딩할 수 있으며, 임상의가 쉽게 검증할 수 있다. 금융 분야에서는 각 규칙이 특정 의심스러운 행동 패턴에 해당하는 사기 탐지에 사용된다.
결정 목록은 저장하고 실행하기 간단하므로 최소한의 계산 자원을 요구한다. 이는 Qualcomm 기반 모바일 장치나 Arm Holdings 기반 마이크로컨트롤러와 같이 지연 시간이 중요한 임베디드 시스템이나 실시간 응용 프로그램에 매력적이다. 또한 Chess computer 프로그램에서 오프닝 또는 엔드게임 휴리스틱을 인코딩하고, TomTom 내비게이션 시스템에서 교통 분류에 사용되어 왔다.
다른 모델과의 관계
결정 목록은 결정 트리와 밀접하게 관련되지만 구조에서 차이가 있다. 결정 트리는 각 루트-리프 경로를 규칙으로 순회하여 동등한 결정 목록으로 변환될 수 있지만, 이는 더 긴 목록을 초래할 수 있다. 반대로, 결정 목록은 각 노드가 최대 하나의 자식을 갖는 퇴화된 트리로 표현될 수 있지만, 이는 항상 효율적이지는 않다. Machine learning의 더 넓은 관점에서 결정 목록은 Deep learning 네트워크와 같은 "블랙 박스" 모델과 대조되는 "화이트 박스" 모델의 한 형태로 간주된다. 이는 종종 더 복잡한 알고리즘과 비교하기 위한 기준선으로 사용되며, 여러 약한 결정 목록이 결합되는 부스팅과 같은 앙상블 방법의 구성 요소로도 사용된다.
현대 AI 연구에서 결정 목록은 설명 가능한 AI(XAI) 맥락에서 새로운 관심을 얻고 있다. MIT CSAIL 및 Stanford AI Lab과 같은 기관의 연구자들은 Neural network 예측에서 결정 목록을 생성하는 방법을 탐구하여 Generative AI 시스템이 내린 결정에 대한 인간이 이해할 수 있는 설명을 제공하는 것을 목표로 한다. 이러한 하이브리드 접근 방식은 딥 모델의 정확성을 활용하면서 규칙 기반 시스템의 해석 가능성을 유지한다.
한계 및 확장
결정 목록의 주요 한계는 표현력이다. 이는 축 정렬된 결정 경계(즉, 각 규칙이 단일 특성 또는 단순 조건의 결합을 검사)만 표현할 수 있어 특성 간의 복잡한 상호작용을 포착하지 못할 수 있다. 이는 복잡한 패턴이 있는 작업에서 Residual Network (ResNet)이나 U-Net과 같은 비선형 모델에 비해 낮은 정확도를 초래할 수 있다. 또한 탐욕적 학습 과정은 최적이 아닌 목록을 생성할 수 있으며, 규칙의 순서가 중요하다 - 초기의 지나치게 광범위한 규칙이 더 구체적인 규칙을 가릴 수 있기 때문이다.
이러한 문제를 해결하기 위한 확장에는 조건이 진실의 정도를 가질 수 있게 하는 퍼지 결정 목록과 신뢰 점수를 출력하는 확률적 결정 목록이 포함된다. 또 다른 확장은 일부 Sanctuary AI 로봇 공학 프로젝트에서 볼 수 있듯이 상태를 행동에 매핑하는 정책으로서 강화 학습에서 결정 목록을 사용하는 것이다. 단순함에도 불구하고 결정 목록은 정확성과 해석 가능성의 균형을 맞추는 방식에서 다른 모델이 따라잡기 어려운 AI 도구 키트의 귀중한 도구로 남아 있다.