// tmp excerpt from 마스터 알고리즘
의사결정트리(decision_tree?)역시
차원의 저주에서 벗어나지 못한다. 예를 들어 학습하고자 하는 개념이
구,sphere라고 하자. 구 내부의 점들은 양이고 밖의 점들은 음이다. 의사결정트리는 구가 들어가는 가장 작은
정육면체,cube에 구를
근사,approximation시킬 수 있다. 완벽하지는 않지만 너무 나쁜 근사도 아니다. 정육면체의 구석들만 잘못
분류,classification한 셈이다. 하지만 고차원에서는 초정육면체(
초입방체,hypercube)의 거의 모든 체적(
부피,volume)이
초구,hypersphere 밖에 있다. 올바르게 양으로 분류한 사례에 비하여 틀리게 양으로 분류한 사례가 훨씬 더 많기 때문에
정확도,accuracy는 급락하고 만다.
사실 어떤 ML도 차원의 저주에서 벗어나지 못한다. 차원의 저주는 ML에서
과적합,overfitting 문제에 이어 두 번째로 가장 나쁜 골칫거리다. '차원의 저주'는 Richard Bellman이 1950년대에 만든 용어다. 그는 3차원에서 잘 작동한 제어 알고리즘
control algorithm이 로봇 팔의 모든 관절이나 화학 공장의 모든 조절 손잡이를 제어하기 원할 때처럼 더 높은 차원의 공간에서는 절망스러울 정도로 비효율적이 되는 것을 발견했다. ... (그래서 대책은 관련 없는 차원들을 없애는 것.) .... 방의 천장이 높지만 데이터의 위치는 카펫에 앉은 얇은 먼지 층처럼 모두 바닥에 가까운 경우도 있다. 이것은 운이 좋은 경우다. 3차원 문제처럼 보이지만 사실상 2차원 문제에 더 가깝기 때문이다. 자연이 이미 우리를 위해 높이를 줄였기 때문에 우리가 높이를 줄일 필요가 없다.
데이터,data가 균일하게 (초)공간에 퍼지지 않은 이런 '비균일성의 축복'
blessing of nonuniformity이 종종 곤경을 면하게 해 준다. ....