[ML] Mondrian Forest

Mondrain Forest

• Random forest에서 incremental learning을 위해 몬드리안 포레스트를 사용한다.
• 최근 제안된 Online random forest 방법보다 빠르고 정확하다
• Mondrian forests = Mondrian process + Random forests
• MF =  Online bagging + Extremely randomized tree + Temporal knowledge weighting
  • Online bagging 설명

 

RF에서 각 트리를 만드는 방법

• Breiman-RF:
  • Bagging + feautre들을 무작위로 서브 샘플링하고 서브 샘플링 feature들 중에서 가장 적합한 위치 선택
• Extremely Randomized Trees:
  • 랜덤으로 K (feature-id,location) 쌍을 샘플링하고, 이 하위 집합 중에서 최고의 분할을 선택
  • no bagging

 

Mondrain process 

• MP(λ, X )는 X의 계층적 축 정렬 이진 파티션(binary partition)에 대한 분포를 지정함
• λ는 Mondrian process의 복잡성 파라미터이다. (weigted max-depth)
• 각 노드 내에서 하한과 상한을 정의하려면 X를 사용하고, 샘플들을 분할하려면 MP를 사용하십시오.

 

 

원래의 online random forest와 mondrain forest의 차이

 

• 보이지 않는 지역으로 확장되지 않는 분할
• 한 트리의 어느 곳에서나 새로운 분할을 도입할 수 있다.
• The size and lifetime of a node control probability of new splits being introduced
• Self-consistent hierarchical Bayesian prior on the leaf parameters.

 

Mondrian trees: online learning

• 데이터셋이 커짐에 따라 조건부 몬드리안 프로세스(conditional Mondrian process) MTx에서 시뮬레이션 하여 몬드리안 트리 T를 확장한다.
• 배치와 온라인 트리의 분포는 동일하다
• 데이터 포인트의 순서는 중요하지 않다(상관x)
• MTx는 다음 4개의 연산 중 하나 이상을 수행한다
  • 이미 존재하는 분할에 새로운 분할을 삽입
  • 존재하는 분할을 새로운 범위로 확장
  • 잎을 분할
• MTx의 연산량은 트리 깊이에 선형이다(linear in depth of tree)

 

 

Mondrian Forest: Training

split tuple (f, δ)은 target 또는 impurity와 독립적으로 결정된다. 모든 feature들이 같은 규모를 가지고 중요도가 똑같다면 이는 extremely randomized tree와 같다.(max_features=1로 설정된)

1. 분할 feature 인덱스 f는 u_b[f]-l_b[f]에 비례하는 확률로 그려진다. (u_b: 모든 feature들의 upper bound, l_b: lower bound)
2. feature 인덱스를 고정한 후, 분할 임계 값(split threshold) δδ는 한계 l_b, u_b를 갖는 균일 분포(uniform distribution)에서 도출된다.

경계간에 큰 차이가 있는 feature은 중요한 feature일 가능성이 높다. 몬드리안 트리의 모든 부분 공간 j에도 정보가 저장된다.

1. 특정 노드의 모든 feature들의 upper and lower bounds 또는 bounding box는 트레이닝 데이터로 인해 결정된다.
2. 평균 $\sum^{D}_{f=1}$(ub[f]−lb[f])을 가진 지수(exponential)에서 추출되는 분할 시간 τ. tau 값이 작을 수록 바운딩 박스가 커진다.

 

분할 시간은 가중 깊이로 볼 수 있다. 부모 노드와 자식 노드 사이의 모서리가 음이 아닌 가중치와 연관되어 있다고 가정하자. 노드에서 분할 시간은 루트에서 노드까지의 경로를 따라온 가중치의 합이다. 가중치가 모두 1인 경우 분할 시간은 노드의 깊이이다.

 

 

Mondrain Forest: Prediction

 

 예측을 위해 루트에서 리프까지 경로에 있는 모든 노드를 고려한다. 

이 공식을 통해 특정 노드의 예측에 대한 확신/불확실성을 기반으로 노드에 유연하게 가중치를 줄 수 있다.

 

 

Conclusion

regression 관점에서 볼 때, decision tree는 leaf에서 각 point들의 평균을 y값으로 예측하지만, mondrain tree는 모든 노드에서 bounding box와 각 point의 거리에 관해 가중치를 두고 root부터 leaf까지 내려올 때 거치는 모든 노드의 가중치를 계산한다.

 

 

 

출처: https://medium.com/mlrecipies/mondrian-forests-making-random-forests-better-and-efficient-b27814c681e5

출처: https://scikit-garden.github.io/examples/MondrianTreeRegressor/

출처: https://project.inria.fr/bnpsi/files/2015/07/balaji.pdf