Institutsseminar/2021-07-23 Zusatztermin

Aus IPD-Institutsseminar
Zur Navigation springen Zur Suche springen
Termin (Alle Termine)
Datum Fr 23. Juli 2021, 11:00 Uhr
Dauer 75 min
Raum https://conf.dfn.de/webapp/conference/979160755
Vorheriger Termin Fr 16. Juli 2021
Nächster Termin Fr 23. Juli 2021

Vorträge

Vortragende(r) Tom George
Titel Augmenting Bandit Algorithms with Domain Knowledge
Vortragstyp Masterarbeit
Betreuer(in) Pawel Bielski
Kurzfassung Bandit algorithms are a family of algorithms that efficiently solve sequential decision problems, like monitoring in a cloud computing system, news recommendations or clinical trials. In such problems there is a trade of between exploring new options and exploiting presumably good ones and bandit algorithms provide theoretical guarantees while being practical.

While some approaches use additional information about the current state of the environment, bandit algorithms tend to ignore domain knowledge that can’t be extracted from data. It is not clear how to incorporate domain knowledge into bandit algorithms and how much improvement this yields.

In this masters thesis we propose two ways to augment bandit algorithms with domain knowledge: a push approach, which influences the distribution of arms to deal with non-stationarity as well as a group approach, which propagates feedback between similar arms. We conduct synthetic and real world experiments to examine the usefulness of our approaches. Additionally we evaluate the effect of incomplete and incorrect domain knowledge. We show that the group approach helps to reduce exploration time, especially for small number of iterations and plays, and that the push approach outperforms contextual and non-contextual baselines for large context spaces.

Vortragende(r) Youheng Lü
Titel Auswahl von SAT-Instanzen zur Evaluation von Solvern
Vortragstyp Bachelorarbeit
Betreuer(in) Jakob Bach
Kurzfassung Das schnelle und effiziente Lösen von SAT-Instanzen ist für viele Bereiche relevant, zum Beispiel Kryptografie, Scheduling oder formale Verifikationen. Um die Geschwindigkeit von SAT-Solvern zu evaluieren, gibt es SAT-Instanzenmengen, die die Solver lösen müssen. Diese Instanzenmengen (Benchmarks) bestehen aus Hunderten von unterschiedlichen Instanzen. Um ein repräsentatives Ergebnis zu erhalten, muss eine Benchmark viele unterschiedliche Instanzen haben, da unterschiedliche Solver auf unterschiedlichen Instanzen gut sind. Wir gehen aber davon aus, dass wir Benchmarks erstellen können, die kleiner als die aktuellen Benchmarks sind, die immer noch repräsentative Ergebnisse liefern.

In unserer Arbeit stellen wir einen Ansatz vor, der aus einer gegebenen repräsentativen Benchmark eine kleinere Teilmenge wählt, die als repräsentative Benchmark dienen soll. Wir definieren dabei, dass eine Benchmark repräsentativ ist, wenn der Graph der Laufzeiten ein festgelegtes Ähnlichkeitsmaß gegenüber der ursprünglichen Benchmark überschreitet. Wir haben hierbei einen BeamSearch-Algorithmus erforscht. Am Ende stellen wir allerdings fest, dass eine zufällige Auswahl besser ist und eine zufällige Auswahl von 10 % der Instanzen ausreicht, um eine repräsentative Benchmark zu liefern.

Neuen Vortrag erstellen

 

Hinweise