다차원 Parametric Min-cut을 응용한 섭동확률모델에서의 예측손실 최적화

학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2015. 8. 정교민.We consider the problem of learning perturbation-based probabilistic models by computing and differentiating expected losses. This is a challenging computational problem that has traditionally been tackled using Monte Carlo-based methods. In this work, we show how a generalization of parametric min-cuts can be used to address the same problem, achieving high accuracy of faster than a sampling-based baseline. Utilizing our proposed Skeleton Method, we show that we can learn the perturbation model so as to directly minimize expected losses. Experimental results show that this approach offers promise as a new way of training structured prediction models under complex loss functions.Abstract i Chapter 1 Introduction 1 Chapter 2 Background: Perturbations, Expected Losses 4 Chapter 3 Algorithm: Skeleton Method 6 3.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Finding a New Facet . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Updating the Skeleton GY . . . . . . . . . . . . . . . . . . . . . . 10 3.4 Calculating Expected Loss R . . . . . . . . . . . . . . . . . . . . 11 3.5 Example: Two Parameters . . . . . . . . . . . . . . . . . . . . . . 11 Chapter 4 Learning 14 4.1 Computing Gradients: Slicing . . . . . . . . . . . . . . . . . . . . 14 4.2 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Exploiting the Skeletond Method . . . . . . . . . . . . . . . . . . 17 Chapter 5 Experiments and Discussion 18 5.1 Data and Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 ii 5.2 Calculating Expected Losses . . . . . . . . . . . . . . . . . . . . 19 5.3 Calculating Gradients . . . . . . . . . . . . . . . . . . . . . . . . 20 5.4 Model Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.4.1 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.4.2 Other Loss Functions . . . . . . . . . . . . . . . . . . . . 23 5.5 Expected Segmentations . . . . . . . . . . . . . . . . . . . . . . . 25 Chapter 6 Conclusion 27 Bibliography 29 초록 32Maste