Seit dem Aufkommen der ersten Computer haben sich die Menschen die Frage gestellt, ob diese Maschinen mit ihrer enormen numerischen Rechnerleistung nicht in der Lage sein sollten zu denken. Im Laufe der Zeit entwickelte sich das Forschungsgebiet Maschinelles Lernen bzw. Künstliche Intelligenz, das sich mit dieser Frage beschäftigt. Seit Beginn der achtziger Jahre setzte eine verstärkte Interaktion mit den Bereichen Algorithmik und Komplexitätstheorie ein. Dabei wurden sowohl tiefe Einblicke in die Struktur von Problemen des Maschinellen Lernens gewonnen als auch reizvolle algorithmische Fragestellungen aufgeworfen. Gleichzeitig wurden aber auch einige Grenzen des Maschinellen Lernens sichtbar. Das vorliegende Buch Algorithmisches Lernen gibt eine Einführung in dieses Gebiet und stellt die wesentlichen strukturellen Resultate in sehr kompakter Weise vor.

Behandelt werden das PAC-Modell, Occam-Algorithmen, Schwache Lerner und Boosting, Nichtlernbarkeit, Lernen aus verrauschten Beispielen sowie On-Line-Lernen. Zusätzlich gibt es zu jedem Kapitel einige Aufgaben.

André Große