Effiziente Wahrscheinlichkeitsberechnung für Ereignisausdrücke
Status
Finished diploma thesis
Student
- Twain Hoffmann
Finished
2004
-
Task description
HyREX ist eine XML-Retrievalengine. Die Berechnung von Wahrscheinlichkeiten in HyREX erfolgt über Ereignisausdrücke, die die Abhängigkeit eines Antwortelements von den (probabilistischen) Basisereignissen (Erfüllung der einzelnen Fragebedingungen durch das aktuelle Element) in Form eines booleschen Ereignisausdrucks beschreiben.
Bisher erfolgt die Berechnung der zugehörigen
Wahrscheinlichkeit mit Hilfe der Siebformel (oder
Einschluß-Ausschluß-Formel). Dabei muss der Ereignisausdruck
zunächst in die disjunktive Normalform überführt werden:
e = K1 or ...or Kn ,
wobei die Kis Basiserereignisse oder Konjunktionen solcher
Ereignisse darstellen. Dann ergibt sich die zugehörige Wahrscheinlichkeit
als alternierende Summe der Wahrscheinlichkeiten von Kombinationen der
Kis.
Die Siebformel hat exponentielle Komplexität. Im Rahmen dieser Arbeit soll nun eine alternative Strategie realisiert werden:
Modifiziert man die disjunktive Normalform so, dass die einzelnen Minterme zueinander disjunkt sind (z.B.\ durch Bildung der vollständigen disjunktiven Normalform), so kan man anstelle der Siebformel einfach die Summe der Wahrscheinlichkeiten der einzelnen Konjunktionen berechnen. Dabei ist auch eine partielle Auswertung möglich, d.h.\ man berechnet Teilsummen, die jeweils bessere untere Schranken für die gesuchte Wahrscheinlichkeit bilden. Durch die Anwendung des Verfahrens auf die Gegenwahrscheinlichkeit erhält man jeweils bessere obere Schranken, was für das Ranking in IR-Anwendungen relevant ist.
Im Rahmen dieser Arbeit soll die neue Strategie implementiert und in HyREX integriert werden. Ferner soll ein Verfahren zur Auswahl der jeweils effizienteren Strategie entwickelt und integriert werden. Die Realisierung soll anhand von Testdaten auf ihre Laufzeiteffizienz hin untersucht werden.