기존의 randomforest 같은 경우 데이터의 주요 변동 요인을 포착하는 데 도움이 되는 내부 표현을 효율적으로 학습하는 메커니즘이 부족하다.
본 연구에서는 의사결정 트리의 divide and conquer 원칙을 통해 심층 아키텍처에서 representation learning에서 매력적인 속성을 통합하는 새로운 접근 방식인 Deep Neural Decision Forests을 제시함.
이 논문에서 우리는 (심층) 컨볼루션 네트워크에서 end to end 학습을 위한 대체 분류기로 사용할 수 있는 확률적이고 차별화 가능한 의사 결정 트리를 모델링하고 훈련하는 방법을 보여주었다.
기존의 의사 결정 트리 훈련에 대한 일반적인 접근방식은 일반적으로 탐욕스럽고 국지적인 방식(local manner)으로 작동하여 표현 학습(representation learning)을 불가능하게 만든다.
이 문제를 극복하기 위해 의사결정 트리에 대한 확률적 라우팅을 도입하여 역전파를 통한 분할 노드 매개 변수 학습을 가능하게 했다.
또한 트리/기본 네트워크의 현재 상태를 고려하여 리프 노드(leaf node)를 최적의 예측 변수로 채우는 방법을 보여주었다. 우리는 새로운 의사 결정 포레스트 모델을 표준 머신 러닝 데이터 세트의 독립 실행형 분류기로 성공적으로 검증했으며 데이터 세트 확대 없이 GoogLeNet 아키텍처에 통합할 때 ImageNet의 최신 성능을 능가한다.
의사 결정 트리(decision tree)는 결정 노드(또는 분할 노드)와 예측 노드(또는 리프 노드)로 구성된 분류기이다.
N으로 인덱싱 된 의사 결정 노드는 트리의 내부 노드(interal node)
L로 인덱싱된 예측 노드는 트리의 터미널 노드(terminal node)(leaf node
결정 트리는 트리를 통해 leaf node로 분류하며 이것은 y에 대한 $\pi$ 확률 분포에 의해 발생하는 예측을 통해서 이루어진다.
트리를 통한 라우팅은 의사결정 함수를 통해 결정된다 $d_n(., \theta) : X → [0,1]$
각각의 decision node에서 결정이 수반된다.
왼쪽 또는 오른쪽으로 subtree로 보내진다.
일반적인 decision forests는 $d_n$ 이 binary이고, routing 은 deterministic 하게 결정된다.
이 논문에서는 확률적인 라우팅을 고려할 것이다. 라우팅 방향은 mean $d_n$ 에 베르누이 무작위 변수의 출력이다.
leaf node 안에서 샘플링이 끝날 때, 관련된 트리 예측은 class-label 확률 분포로 결정된다.
확률적으로 라우팅 하는 경우, leaf 예측은 잎에 도달할 확률에 의해 가중치가 부여된다.
따라서 tree T로부터 나오는 마지막 샘플 x에 대한 예측은 다음과 같이 주어진다.
라우팅 함수에 대한 명시적인 형태를 제공하기 위해 트리의 구조에 의존하는 다음의 이진 관계를 도입한다.
Decision nodes
논문의 나머지 부분에서는 다음과 같이 정의된 의사결정 함수를 사용하여 확률적 경로(stochastic routing)를 제공하는 의사결정 함수를 고려한다.
decision tree 학습하기 위해서는 decision node parameterizations과 노드 예측하는 $\pi$가 요구된다.
추정을 위해 우리는 주어진 데이터 세트 T에 관한 최소 경험적 위험 원칙(minimum empirical risk principle)을 고수한다.
학습은 2개의 step 최적화 전략을 고려한다. 여기서 우리는 최소화를 위한 방법으로 $\theta$의 업데이트와 $\pi$ 업데이트를 번갈아 한다.
Learning Decision Nodes
All decision functions는 공통 파라미터를 의존한다.
우리는$f_n$의 함수 유형에 대해 어떠한 가정도 하지 않았다. 따라서 주어진 것과 관련된 위험의 최적화를 막는 것은 없다.
의사결정 트리에 의존하는 gradient term은 다음과 같이 주어진다.
마지막 언급으로, 우리는 또한 SGD에 대한 대체 최적화 절차, 즉 마지막 반복에 대한 risk partial derivative의 sign change를 기반으로 각 매개 변수에 대한 특정 학습 속도를 자동으로 조정하는 RPROP [27]를 고려했다.
Learning Prediction Nodes
이는 볼록 최적화 문제입니다. 유사한 문제가 기존 의사결정 트리의 맥락에서 발생했지만, 오직
단일 노드 수준에서. 이 논문의 경우, 전체 나무가 고려되고, 우리는 공동으로 모든 잎 예측을 추정하고 있다.
모든 leaves는 uniform에서 시작하여, 점점 업데이트된다.
또한, 우리는 이전 하위 섹션에서 설명한 대로 $\pi$의 업데이트를 $\theta$의 전체 확률적 업데이트 시기와 인터리빙 한다.
Learning a Forest
위에서는 단일 의사 결정 트리 설정을 다루었습니다. 논문에서 모든 트리가 $\Theta$에서 동일한 매개 변수를 공유할 수 있지만, 각 트리는 다른 decision functions 세트(여전히 (3)에서 정의됨)와 independent lead prediction $\pi$로 다른 구조를 가질 수 있는 트리 F의 앙상블을 고려한다.
때문에 forest의 각 트리는 leaf parameters $\pi$의 set을 가진다. 독립적으로 각각의 트리의 예측 node를 업데이트한다.
논문에서 각 미니 배치에 대해 F에서 트리를 무작위로 선택한 후 SGD 업데이트에 대해 (Learning Decision Nodes)에서 자세히 설명한 대로 진행합니다.
이 전략은 다소 Dropout의 basic idea와 닮았다. 각각 SGD 업데이트는 잠재적으로 다른 네트워크 토폴로지에 적용된다.
또한 전체 포레스트 대신 개별 트리를 업데이트하면 훈련 중 계산 부하가 감소한다.
(4)와 같이 훈련 시간 동안 각 트리에 의해 전달된 예측은 최종 결과를 산출하기 위해 평균화된다.
Summary of the Learning Procedure
학습 절차는 알고리즘 1에 요약된다.
Decision Nodes
Routing Function
라우팅 함수 $\mu_l$ 의 계산은 트리를 한 번 통과하여 수행할 수 있습니다.
실험
결론
이 논문에서 우리는 (심층) 컨볼루션 네트워크에서 종단 간 학습을 위한 대체 분류기로 사용할 수 있는 확률적이고 차별화 가능한 의사 결정 트리를 모델링하고 훈련하는 방법을 보여주었다. 의사 결정 트리 훈련에 대한 일반적인 접근방식은 일반적으로 표현 학습을 불가능하게 하는 탐욕스럽고 국지적인 방식으로 작동한다. 이 문제를 극복하기 위해 의사결정 트리에 대한 확률적 라우팅을 도입하여 역전파를 통한 분할 노드 매개 변수 학습을 가능하게 했다. 또한 트리/기본 네트워크의 현재 상태를 고려하여 리프 노드를 최적의 예측 변수로 채우는 방법을 보여주었다. 우리는 새로운 의사 결정 포레스트 모델을 표준 머신 러닝 데이터 세트의 독립 실행형 분류기로 성공적으로 검증했으며, 데이터 세트 확대 없이 GoogLeNet 아키텍처에 통합할 때 ImageNet의 최신 성능을 능가한다.
