Hybride Methoden- und Systemarchitekturen für heterogene Informationsräume

• Applicant: Professor Dr. Stefan Wrobel
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2002 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5399759

• Final Report Year: 2007

Final Report Abstract

Für einfach strukturierte, homogene Datenbestände existiert mittlerweile eine Vielzahl von erfolgreichen Analysemethoden aus den Bereichen Statistik, Neuronale Netze, Fuzzy- Systeme und Maschinelles Lernen. Mit diesen Methoden lassen sich in Daten, die in einer einzelnen Tabelle mit numerischen oder symbolischen Werten abgelegt sind, auf unterschiedliche Weise interessante Muster oder funktionale Zusammenhänge entdecken ("Data Mining"). In vielen aktuellen Anwendungsbereichen der computergestützten Datenanalyse kann heute aber nicht mehr davon ausgegangen werden, dass nur eine einzige Art homogen (in der Regel durch einen Satz fester Merkmale) beschriebener Objekte zu betrachten sind. Anwendungen bei biologischen Daten, im World Wide Web und andere mehr befassen sich mit heterogenen Objekten unterschiedlicher Arten, die über vielfältige Relationen miteinander verbunden sein können. Eine natürliche Beschreibungssprache für solche Daten sind (beschriftete) Graphen, deren Nutzung für die Datenanalyse, insbesondere für das Lernen klassifizierender Funktionen aus Beispielen, im Mittelpunkt dieses Projektes stand. Wir konzentrierten uns dabei insbesondere auf die Klasse der so genannten Kernmethoden (Supportvektormaschinen und andere), die sich in den vergangenen Jahren auf Grund ihrer guten theoretischen Fundierung, ihrer überlegenen Lerngenauigkeit und ihrer Fähigkeit zur hybriden Kombination unterschiedlicher Kernfunktionen zur dominierenden Verfahrensklasse im Maschinellen Lernen entwickelt haben. Vor Beginn des beantragten Projektes gab es keine effektiven und effizient berechenbaren Kernfunktionen für Graphen, so dass graphstrukturierte Probleme nicht direkt mit Kernmethoden bearbeitet werden konnten. In den vergangenen 36 Projektmonaten wurden unter Nutzung von Algorithmen aus der Graphentheorie in diesem Projekt Kernfunktionen für Graphen (kurz: Graphkerne) entwickelt, die sich im Vergleich zu den parallel international entstandenen Alternativen zum einen durch eine überlegene Genauigkeit, insbesondere auf den im Projekt schwerpunktmäßig betrachteten Anwendungen aus der Bioinformatik, als auch durch eine mindestens vergleichbare und oft deutlich bessere Effizienz auszeichnen. Auch im Vergleich zu indirekten Alternativen, wie der Transformation von Graph-Daten in eine logische Darstellungsform für die sog. induktive Logikprogrammierung, haben sich die in dem Projekt entwickelten Graphkerne als überlegen erwiesen. Wirkstoffsuche ist ein potentielles Anwendungsfeld für Graphkerne, da die molekularen Atom-Bindungsstrukturen als beschriftete Graphen betrachtet werden können. Aus diesem Grund haben wir unsere Graphkerne auf verschiedenen Moleküldatenbanken evaluiert. Die betrachteten Datenbanken wurden aus drei verschiedenen Quellen bezogen: dem chemischen Datensatz von NCI (online frei verfügbar), einem kleinen Datensatz, der in vitro von dem Pharmakologischen Institut der Universität Bonn annotiert wurde, und zwei Datensätzen, die von der Altana Pharma AG vorbereitet wurden. Die Kombination unserer Graphkerne mit Supportvektormaschinen (Support Vector Machines) hat vielversprechende empirische Ergebnisse auf jedem dieser Datensätze gezeigt. Um die prädiktive Performanz unserer Graphkerne weiter zu verbessern, haben wir zwei weitere Ansätze untersucht. Zuerst haben wir uns auf Graphkerne konzentriert, die auf der Betrachtung von häufigen Teilgraphen als Merkmalen basieren. Die bisher üblichen Algorithmen, die wir getestet haben, waren allerdings nicht in der Lage, größere Datensätze, wie beispielsweise den NCI Datensatz, der zur Zeit mehr als 250.000 Molekülen enthält, zu behandeln. Daher haben wir uns auf Graphklassen beschränkt, deren spezifische Eigenschaften effizient ausgenutzt werden können. Insbesondere haben wir die Klasse der außenplanaren Graphen betrachtet, da diese Klasse die Verallgemeinerung der Bäume in einer natürlichen Hierarchie darstellen. Desweiteren spielen sie in vielen Anwendungen eine wichtige Rolle, wie zum Beispiel in der Pharmakologie. Als zweiten Ansatz haben wir allgemeine domänenunabhängige Verfahren für verschiedene Lernszenarien entwickelt. Wir haben eine transduktive Inferenzmethode konzipiert, die die während der Trainingsphase zur Verfügung stehenden Testinstanzen zum Training mitverwendet, und halbüberwachte Techniken, die es erlauben, größere Mengen von unbeschriftete Beispielen in der Trainingsphase zu betrachten.

Publications

• J. Ramon and T. Gärtner. Expressivity versus efficiency of grapgh kernels. In L. De Raedt and T. Washio, editors, Proc. of the First International Workshop on Mining Graphs, Trees and Sequences (MGTS 2003), pages 65-74. ECML/PKDD'03 workshop proceedings, 2003.
  
  
• K. Kersting and T. Gärtner. Fisher kernels for logical sequences. In Proc. of the 15th European Conference on Machine Learning, pages 205-216. Springer Verlag, Berlin, 2004.
  
  
• Kurt Driessens, Jan Ramon, and Thomas Gärtner. Graph kernels and gaussian processes for relational reinforcement learning. Machine Learning, 64(1-3):91-119,2006.
  
  
• Quoc V. Le, Alex J. Smola, and Thomas Gärtner. Simpler knowledge-based support vector machines. In Proc. of the 23rd International Conference on Machine Learning (ICML 2006), pages 521-528. ACM, 2006.
  
  
• Quoc V. Le, Alexander J. Smola, Thomas Gärtner, and Yasemin Altun. Transductive gaussian process regression with automatic model selection. In Proc. of the 17th European Conference on Machine Learning (ECML 2006), pages 306-317. Springer Verlag, Berlin, 2006.
  
  
• S. Wrobel, T. Gärtner, and T. Horväth. Kernels for predictive graph mining. In M. Spiliopoulou, R. Kruse, A. Nürnberger, C. Borgelt, and W. Gaul, editors, From Data and Information Analysis to Knowledge Engineering, Studies in Classification, Data Analysis, and Knowledge Organization, pages 75-86. Springer Verlag, Berlin, 2006.
  
  
• T. Gärtner, J.W. Lloyd, and P.A. Flach. Kernels and distances for structured data. Machine Learning, 57(3):2005-232, 2004.
  
  
• T. Gärtner, K. Driessens, and J. Ramon. Graph kernels and Gaussian processes for relational reinforcement learning. In Proc. of the 13th International Conference on Inductive Logic Programing (ILP 2003), pages 146-163. Springer Verlag, Berlin, 2003.
  
  
• T. Gärtner, P.A. Flach, and S, Wrobel. On graph kernels: Hardness results and efficient alternatives. In Proc of the 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop (COLT2003), pages 129-143. Springer Verlag, Berlin, 2003.
  
  
• T. Gärtner, T. Horväth, Q. Le, A. Smola, and S. Wrobel. Kernel methods for graphs. In D.J. Cook and L.B. Holder, editors, Mining Graph Data, pages 253-282. John Wiley & Sons, Inc., New York, 2007.
  
  
• T. Gärtner. A survey of kernels for structured data. SIGKDD Explorations, 5(l):49-58, 2003.
  
  
• T. Gärtner. Predictive graph mining with kernel methods. In S. Bandyopadhyay, D. Cook, U. Maulik, and L. Holder, editors, Advanced Methods for Knowledge Discovery from Complex Data, pages 55-8. Springer Verlag, Berlin, 2005.
  
  
• T. Horväth, R.H. Sloan, and G. Turan. Learning logic programs with unary partial function graph background knowledge. In L. De Raedt and T. Washio, editors, Proc. of the First International Workshop on Mining Graphs, Trees and Sequences (MGTS 2003), pages 33^4. ECML/PKDD'03 workshop proceedings, 2003.
  
  
• T. Horväth, S. Hoche, and S. Wrobel. Effective rule induction from molecular structures represented by labeled graph. In Proc. of the 21st Annual ACM Symposium on Applied Computing (SAC 2006), pages 611-616. ACM Press, New York, NY, 2006.
  
  
• T. Horväth, T. Gärtner, and S. Wrobel. Cyclic pattern kernels for predictive graph mining. In Proc. of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2004), pages 158-167. ACM Press, New York, NY, 2004.
  
  
• Tamäs Horväth, Jan Ranion, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. In Proc. of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2006), pages 197-206. ACM Press, New York, NY, 2006.
  
  
• Tamäs Horväth. Cyclic pattern kernels revisited. In Proc. of Advances in Knowledge Discovery and Data Mining, 9th Pacific-Asia Conference (PAKDD 2005), pages 791- 801. Springer Verlag, Berlin, 2005.
  
  
• U. Brefeld, T. Gärtner, T. Scheffer, and S. Wrobel. Efficient co-regularised least squares regression. In Proc, of the 23rd International Conference on Machine Learning (ICML 2006), pages 137-144. ACM, 2006.
  
  
• X Horväth, B. Bringmann, and L. De Raedt. Frequent hypergraph mining. In Proc. of the 16th International Conference on Inductive Logic Programing (ILP 2006), page. Springer Verlag, Berlin, 2007.