jagomart
digital resources
picture1_Greta Thesis Oe Np Hard


 115x       Filetype PDF       File size 0.35 MB       Source: www.tml.cs.uni-tuebingen.de


File: Greta Thesis Oe Np Hard
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 ...

icon picture PDF Filetype PDF | Posted on 08 Feb 2023 | 2 years ago
Partial capture of text on file.
               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
The words contained in this file might help you see if this file matches what you are looking for:

...Eberhard karls university of tubingen faculty science department computer bachelor thesis in is ordinal embedding np hard margareta schluter supervisor prof dr ulrike von luxburg theory machine learning bachelorthesis processing period abstract the task to nd points y rd that comply n a given set constraints each constraint form closer than i j this investigates computational complexity problem k most important it proven for all dimen sions d more precise shown deciding whether such an exists r complete proof reduction from euclidean preference proles according peters besides tries deepen understanding solv ing with rst order optimization methods one approach statement by bower et al two dimensional search space used objective has no non global minimizers claim reconstructed and generalized elimination unnecessary premise if holds higher dimensions valuable result solving since algorithms are prone convergence local minima instead solutions ii...

no reviews yet
Please Login to review.