🚀 go-pugleaf

--------------------------------------------------------------------------

                                                      K        K  I
F O R S C H U N G S K O L L O Q U I U M               KK     KK   II
                                                      KKK  KKK    III
im Sommersemester 96                                  KKK KKK     III
                                                      KKKKKK      III
                                                      KKK  KKK    III
                                                      KKK   KKK   III
                                                      KK      KK   II
                                                      K         K   I
Dienstag, den 28.5.1996
16.00 - 18.00 Uhr
Raum  FR 0041
--------------------------------------------------------------------------


Graphalgorithmen und Induktive Logische Programmierung


Tobias Scheffer und Ralf Herbrich


Zusammenfassung:

Im Vortrag sollen einige Standpunkte, die den Ausgangspunkt f�r das
DFG-Projekt "Neue Methoden des Maschinellen Lernens" bilden, zur
Diskussion gestellt und erste Ergebnisse vorgestellt werden.

Wir sprechen zwei Probleme der Induktiven Logischen Programmierung an, zu
denen graphentheoretische Algorithmen neue Beitr�ge leisten k�nnen:

(1) Die Deduktion, also der Test, ob eine Beobachtung von einer Hypothese
    erkl�rt wird, besitzt im allgemeinen exponentiellen Aufwand. Wir zeigen,
    da� ein an einen Graphisomorphiealgorithmus von Weisfeiler angelehnter
    Subsumtionstest in den meisten F�llen nur polynomiellen Aufwand besitzt,
    durch eine zus�tzliche graphentheoretische �berlegung l��t sich der
    gr��te Teil des verbleibenden Suchraumes ausschlie�en.

(2) Wir diskutieren die Beziehung zwischen logischen und graphischen
    Generalisierungsoperationen und schlagen eine graphbasierten
    Generalisierung von Klauseln vor, die eine konstante L�nge (gegen�ber
    dem exponentiellen Wachstum der lgg) und einen dabei maximalen
    Informationsgehalt besitzt.


--------------------------------------------------------------------------

TU Berlin
FG Methoden der K�nstlichen Intelligenz (KI)
Franklinstr. 28/29, FR 5-8
D-10587 Berlin

--------------------------------------------------------------------------



-- 
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TU Berlin, FG KI, Sekr. FR 5-8
Peter Geibel <<<<<<<<<<<<<<<<<<<<<<<<<<< Franklinstr. 28/29, D-10587 Berlin
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Tel. +49-30-314-25491 
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< URL http://www.cs.tu-berlin.de/~geibel