졸업최적화

Graduated optimization

어드밴스트 최적화는 매우 단순화된 문제를 초기에 해결하고, 어려운 최적화 문제와 동등해질 때까지 그 문제를 점진적으로 변형(최적화하면서)하여 어려운 최적화 문제를 해결하려고 시도하는 글로벌 최적화 기법이다.[1][2][3]

기술 설명

세분화된 최적화의 예.

졸업 최적화는 산악인이 지역 최적지에 정착하지 않도록 하는 힐 클라이밍의 개선이다.그것은 어려운 최적화 문제를 일련의 최적화 문제로 세분화하는데, 이는 시퀀스의 첫 번째 문제가 볼록(또는 거의 볼록)하고, 각 문제에 대한 해결책은 시퀀스의 다음 문제에 좋은 출발점을 제공하며, 시퀀스의 마지막 문제는 결국 그것이 일으키는 어려운 최적화 문제다.해결해야 할 과제종종, 졸업된 최적화는 단순한 언덕 등반보다 더 좋은 결과를 준다.또한 특정 조건이 존재할 경우, 최종 문제에 대한 최적의 해결책을 순서에서 찾을 수 있음을 보여줄 수 있다.이러한 조건은 다음과 같다.

  • 시퀀스의 첫 번째 최적화 문제는 초기 시작 지점을 고려하여 해결할 수 있다.
  • 시퀀스에 포함된 각 문제의 글로벌 최적 주위에 있는 국소 볼록 영역은 시퀀스에 포함된 이전 문제의 글로벌 최적점에 해당하는 지점을 포함한다.

만약 이러한 조건들이 충족된다면, 언덕 등반가는 어려운 문제에 대한 전지구적 최적점에 도달할 것이라는 것을 귀납적으로 보여줄 수 있다.안타깝게도 이러한 조건을 충족하는 최적화 문제의 순서를 찾기가 어려울 수 있다.종종, 졸업된 최적화는 문제의 순서가 이 모든 조건을 엄격히 충족한다고 증명될 수 없는 경우에도 좋은 결과를 산출한다.

몇 가지 예

세분화된 최적화는 일반적으로 더 큰 이미지 내에서 개체를 찾기 위해 이미지 처리에 사용된다.이 문제는 이미지를 흐리게 함으로써 더 볼록하게 만들 수 있다.따라서 먼저 가장 많이 블러셔된 영상을 검색한 다음, 그 지점에서 시작해 덜 블러셔된 영상 내에서 검색하고, 원래 날카로운 영상에서 정확하게 물체가 위치할 때까지 이러한 방식으로 물체를 찾을 수 있다.흐릿한 연산자의 적절한 선택은 한 영상의 물체와 다른 영상의 물체와 관련된 기하학적 변환에 달려 있다.[4]

세분화된 최적화는 다지관 학습에 사용될 수 있다.예를 들어, 다지관 조각 알고리즘은 비선형 치수 감소를 위한 다지관 내장을 찾기 위해 절삭된 최적화를 사용한다.[5]데이터 집합 내의 추가 치수에서 점차적으로 분산을 스케일링하는 동시에 나머지 치수로 최적화한다.그것은 또한 종양과의 분열을 위한 조건,[6] 컴퓨터 시야에서의 물체 추적,[7] 그리고 다른 목적에도 사용되었다.

그 방법과 그 적용에 대한 철저한 검토는 에서 찾을 수 있다.[3]

관련 최적화 기법

시뮬레이션 어닐링은 졸업된 최적화와 밀접한 관련이 있다.최적화하는 함수를 평활화하는 대신, 시뮬레이션된 어닐링은 붕괴되는 양만큼 현재 용액을 임의로 교란시키므로 유사한 효과가 있을 수 있다.[citation needed]그러나 시뮬레이션된 어닐링은 개선을 찾기 위해 무작위 샘플링에 의존하기 때문에, 그것의 계산 복잡성은 최적화되는 차원의 수에서 기하급수적이다.[citation needed]이와는 대조적으로, 등급 최적화는 최적화되는 기능을 부드럽게 하므로, 고차원 공간(구배 기반 기법, 힐 등반가 등)에서 효율적인 국소 최적화 기법을 여전히 사용할 수 있다.

참고 항목

참조

  1. ^ Thacker, Neil; Cootes, Tim (1996). "Graduated Non-Convexity and Multi-Resolution Optimization Methods". Vision Through Optimization.
  2. ^ Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. ISBN 0-262-02271-0.[페이지 필요]
  3. ^ a b 호세인 모바히, 존 W.피셔 3세가우스 호모토피 계속과 볼록 봉투의 연결, 컴퓨터 과학 강의 노트(EMMCVPR 2015), 스프링거 2015.
  4. ^ 호세인 모바히, C. 로렌스 지트닉, 이마. 블러, 컴퓨터 비전 및 패턴 인식에 관한 IEEE 회의(CVPR)를 통해 본 2012년 6월.
  5. ^ Gashler, M.; Ventura, D.; Martinez, T. (2008). "Iterative Non-linear Dimensionality Reduction with Manifold Sculpting" (PDF). In Platt, J. C.; Koller, D.; Singer, Y.; et al. (eds.). Advances in Neural Information Processing Systems 20. Cambridge, MA: MIT Press. pp. 513–20.
  6. ^ Afanasjev, BP; Akimov, AA; Kozlov, AP; Berkovic, AN (1989). "Graduated optimization of fractionation using a 2-component model". Radiobiologia, Radiotherapia. 30 (2): 131–5. PMID 2748803.
  7. ^ Ming Ye; Haralick, R.M.; Shapiro, L.G. (2003). "Estimating piecewise-smooth optical flow with global matching and graduated optimization". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (12): 1625–30. doi:10.1109/TPAMI.2003.1251156.