115x Filetype PDF File size 0.35 MB Source: www.tml.cs.uni-tuebingen.de
Eberhard Karls University of Tubingen¨ Faculty of Science Department of Computer Science Bachelor Thesis in Computer Science Is Ordinal Embedding NP-hard? Margareta Schluter¨ Supervisor Prof. Dr. Ulrike von Luxburg Theory of Machine Learning Department of Computer Science Faculty of Science University of Tubingen¨ Schluter,¨ Margareta: Is Ordinal Embedding NP-hard? Bachelorthesis in Computer Science Eberhard Karls University of Tubingen¨ Processing period: 01/04/2020 - 31/07/2020 Abstract The task of ordinal embedding is to find points y ,...,y ∈ Rd that comply to 1 n a given set of constraints. Each constraint is of the form “y is closer to y than i j to y ”. This thesis investigates the computational complexity of that problem. k Most important, it is proven that ordinal embedding is NP-hard for all dimen- sions d ≥ 2. More precise, it is shown that deciding whether such an embedding exists for a given constraint set is ∃R-complete. The proof is a reduction from d-Euclidean for preference profiles, a problem that is ∃R-complete according to Peters (2017). Besides, the thesis tries to deepen the understanding of solv- ing ordinal embedding with first order optimization methods. One approach is a statement by Bower et al. (2018), that in a two-dimensional search space, the used objective has no non-global minimizers. This claim is reconstructed and generalized by elimination of an unnecessary premise. If the statement holds for higher dimensions, it is a valuable result for the solving of ordinal embedding, since optimization algorithms are prone to convergence to local minima instead of global solutions. i ii
no reviews yet
Please Login to review.