| [ KAIST ] in KIDS 글 쓴 이(By): chopin (** 쇼팽 **) 날 짜 (Date): 2003년 12월 6일 토요일 오후 11시 15분 32초 제 목(Title): Re: [질문] information theory 잠시 고민을 해보니 최적 measure를 찾는 문제는 NP class의 문제에 대응하면 그 난이도가 쉽게 이해가 가는군요. 임의의 문제가 정확히 주어졌을 때 그에 대한 최적 measure를 찾는 문제는 최소한 NP-complete에 속합니다. 제 추측에는 더 난이도가 높은 NP-hard에 속하지 않을까 생각이 듭니다. 마찬가지로 여기서 주어진 measure가 최적인지 검증하는 것도 비슷한 클래슥에 속합니다. 이보다 더 영역을 좁혀서, 특정한 하나의 문제에 대해서만 주어진 measure가 최적인지 판별하는 문제는 그 문제의 성격에 따라 크게 달라질 겁니다. 그 문제가 만약 measure들의 parameter의 변화에 따라 정확도가 연속적으로 변하는 미분가능한 영역에 있다면 분석적인 방법으로 해를 찾거나 증명하는 것이 가능한 영역으로 들어올 겁니다. 그렇지 않다면 난이도는 이 경우 역시 별로 달라지지 않습니다. 따라서 만일 한 문제에 대해서만 최적해를 찾고 계신다면 그 문제의 성질을 파악하는게 우선이 되야할 겁니다. 운이 좋으면 convex형태를 보여서 미분가능한 경우가 가끔 있습니다. 보통의 경우에는 그런경우는 드믈지만 찾아볼만한 가치는 있습니다. 그리고 또 한가지 추가할 것은 measure라는 것은 문제와 모델이 정확히 주어졌을 때만 우열을 따질 수 있다는 것입니다. 많은 경우에 모델이 부적합하거나 더 좋은 모델이 가능한 경우가 많기 때문에, 일반적으로 상상하는 최적 measure를 찾았다는 것이 그문제의 최적해를 찾은 것은 아니라는 것입니다. 그 문제를 모델링 한 것이 과연 최적인지를 한번더 따져봐야 measure의 최적 찾기 노력이 의미가 있습니다. measure도 모델의 일부입니다. 시원찮은 모델위에서 measure가 최적이 되어봤자 별볼 일 없다는 것과 같은 의미입니다. 문제 이해에 도움이 되었기를 바라면서... __ 쇼팽 http://brainew.com |