Certifiably Globally Optimal Unsupervised Machine Learning

Forschungsthema/Bereich

Classification & Semidefinite Relaxations

Typ der Abschlussarbeit

Master

Startzeitpunkt

11.05.2024

Bewerbungsschluss

02.05.2025

Dauer der Arbeit

6 months

Beschreibung

It is known [Jean B. Lasserre, 2001] that for polynomial problems (POPs), i.e., nonconvex optimization problems where objective and constraints are multivariate polynomials, the global optimum can be determined via rank relaxation, adding redundant constraints, ascending Lasserre‘s hierarchy, and solving a semidefinite program (SDP), in polynomial time. While this methology is not yet real-time applicable as of 2024, it is merely a matter of time until increased computational power, more advanced solvers, and optimized problem design strategies render this possible. The potential applications of machine learning with optimality guarantees and certificates are immense. Many supervised machine learning and perception problems have already been formulated as POP and successfully solved with this framework, e.g., point cloud registration, pose and shape estimation, and robust estimation.

Unsupervised ML problems, like clustering and Gaussian mixture estimation, can also be stated as POP. The goal of this work is demonstrating and evaluating globally and certifiably solving these kind of problems with that same framework as well. The state of art closest to this in terms of problem structure is robust perception, which should be reproduced first to get familiar with the required methology and tools.

What to do

• Get familiar with solving POPs via SDP
• Reproduce robust perception
• Attempt Clustering
• Attempt Gaussian Mixture Estimation
• Optimize problem structure, e.g. exploiting sparsity
• Evaluate against state of art

Thesis language: German or English.

Voraussetzung

Voraussetzungen an Studierende

• Excellent grades
• Pre-knowledge in Julia, Matlab, or Python are welcome
• Strong self-motivation, perseverance, reliability, mathematical skills, and critical mind

Studiengangsbereiche

• Ingenieurwissenschaften
  Elektrotechnik & Informationstechnik
  Informatik
  Mechanical Engineering
• Naturwissenschaften und Technik
  Mathematik
  Physik
  Technomathematik

Betreuung

Titel, Vorname, Name

Dr.-Ing. Daniel Frisch

Organisationseinheit

Intelligent Sensor-Actuator-Systems (ISAS)

E-Mail Adresse

daniel.frisch@kit.edu

Link zur eigenen Homepage/Personenseite

Website

Bewerbung per E-Mail

Bewerbungsunterlagen

• Notenauszug

E-Mail Adresse für die Bewerbung
Senden Sie die oben genannten Bewerbungsunterlagen bitte per Mail an daniel.frisch@kit.edu


Zurück