Sie sind hier

Skalierbare ME-Inferenz durch Parallelverarbeitung und Cluster Computing

Thema

Inferenz nach dem Prinzip der maximalen Entropie (ME-Inferenz) ist ein aus Sicht der Informationstheorie optimales Verfahren zum Schließen aus unvollständiger Information. Nach diesem Prinzip kann zu einer Wissensbasis bestehend aus probabilistischen Konditionalen (Regeln der Form "wenn A dann B mit Wahrscheinlichkeit p") eine eindeutige Wahrscheinlichkeitsverteilung (ME-Verteilung) bestimmt werden, die sowohl die Konditionale der Wissensbasis erfällt als auch so wenig Information wie nötig ergänzt. Diese Wahrscheinlichkeitsverteilung ist dadurch gekennzeichnet, dass sie das informationstheoretische Maß der Entropie unter allen Verteilungen, die die Wissensbasis erfüllen, maximiert. Eine effektive Methode die ME-Verteilung zu berechnen ist in [3] beschrieben und beruht auf einer iterativen Berechnung und der Dekomposition der ME-Verteilung mit HiIfe von LEG-Netzwerken (local event group). Der in [3] beschriebene Algorithmus ist in dem System SPIRIT [5] implementiert, ein Expertensystem das speziell im Operations Research eingesetzt wird. Ein großer Nachteil des Ansatzes von [3] ist allerdings die Skalierbarkeit. Bei großen Wissenbasen, wie sie unter anderem bei der Grundierung relationaler Wissensbasen [6] und im Semantic Web [4] auftauchen, versagt der Ansatz aufgrund hoher Speicher- und Laufzeitanforderungen.

 

Aufgabenstellung

In dieser Abschlussarbeit soll untersucht werden, inwieweit sich der in [3] beschriebene Ansatz zur Parallelisierung [7] und zur Verwendung in Clustern [1] eignet, siehe auch [2]. Da der Algorithmus aus [3] auf Dekomposition der ME-Verteilung beruht, scheint dort ein vielversprechender Ansatzpunkt zu sein um Berechnungen parallel und auf verschiedenen Maschinen durchzuführen. Da insbesondere der Speicherplatzbedarf bei großen Wissensbasen für einzelne Rechner leicht zu groß werden kann, ist vor allem zu untersuchen wie dieser Speicherplatzbedarf bei der Verwendung von Cluster Computing aufgeteilt werden kann. Der in dieser Arbeit zu entwickelnde Algorithmus soll prototypisch in Java implementiert und sowohl analytisch als auch empirisch evaluiert werden. Bei der Implementierung soll nach Möglichkeit auf vorhandene Java Bibliotheken für Cluster Computing, wie z. B. GridGain1, zurückgegriffen werden.

1http://www.gridgain.com

 

Literatur

[1] Mark Baker et al., editor. Cluster Computing White Paper. Unpublished, 2001. http://arxiv.org/abs/cs/0004014.

[2] Alan Kaminsky. Building Parallel Programs: SMPs, Clusters & Java. Course Technology, 2009.

[3] Carl-Heinz Meyer. Korrektes Schließen bei unvollständiger Information. PhD thesis, FernUniversität in Hagen, Germany, 1997.

[4] Mathias Niepert. Reasoning under uncertainty with log-linear description logics. In Proceedings of the 7th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2011), 2011.

[5] Wilhelm Rädder and Carl-Heinz Meyer. Coherent Knowledge Processing at Maximum Entropy by SPI- RIT. In Proc. Twelfth Conf. on Uncertainty in Artifcial Intelligence, pages 470-476, 1996.

[6] Matthias Thimm, Gabriele Kern-Isberner, and Jens Fisseler. Relational probabilistic conditional reasoning at maximum entropy. In Proceedings of the Eleventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'11), June 2011.

[7] Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103-111, 1990.

 

 

Studienart: 
master
Ausschreibungsdatum: 
2015