Learning to predict combinatorial structures [Elektronische Ressource] / vorgelegt von Shankar Vembu

Learning to Predict CombinatorialStructuresDissertationzurErlangung des Doktorgrades (Dr. rer. nat.)derMathematisch-Naturwissenschaftlichen Fakult¨atderRheinischen Friedrich-Wilhelms-Universit¨at Bonnvorgelegt vonShankar VembuausVizag, IndienUrbana, IL, USA, 2010iiAngefertigt mit Genehmigung der Mathematisch-NaturwissenschaftlichenFakult¨at der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn1. Referent: Prof. Dr. Stefan Wrobel2. Referent: Prof. Dr. Michael ClausenTag der Promotion: 18.05.2010ZusammenfassungDie gr¨oßte Herausforderung bei der Entwicklung von diskriminativen Ler-nalgorithmen fu¨r die Vorhersage von strukturierte Ausgaben stellt die An-zahl der m¨oglichen Ausgaben dar. Diese kann n¨amlich exponentiell mit derEingabegr¨oße wachsen, so dass ersch¨opfendes Testen nicht in hinreichendkurzer Zeit m¨oglich ist. Um dennoch effiziente Lernalgorithmen zu erhal-ten, hatmanbishergewisse Annahmengetroffen. Fu¨rviele kombinatorischeStrukturen, wie z.B. Kreise in Graphen, sind diese Annahmen jedoch nichtzutreffend. In dieser Arbeit entwicklen wir Lernalgorithmen fu¨r strukturi-erte Ausgaben unter zwei neuen Annahmen, die von viele kombinatorischenStrukturen erfu¨llt werden:(i) DieersteAnnahmeist,dasseinbestimmtesZ¨ahlproblemeffizientgelo¨stwerden kann. Unter dieser Annahme entwickeln wir eine Verallge-meinerung der klassischen Kleinste-Quadrate Methode fu¨r strukturteAusgaben.