LS8 News - Teaching - Research - Projects - Software - Staff - General - Internal

PG 520 - Intelligence Service (WiSe 07 / SoSe 08)


Lehrverantwortliche

Prof. Dr. Katharina Morik
Dipl.-Inform. Felix Jungermann

Inhalt

Ziel der PG ist das automatische Erstellen eines Pressespiegels für eine bestimmte Person (z.B. einen Politiker) oder eine bestimmte Firma aus dem Internet bzw. aus Datenbanken.
Daraus sollen dann gezielt Antworten auf bestimmte Fragen extrahiert werden. Methoden zu einem solchen Intelligence Service werden untersucht und implementiert.

Natürlich soll die PG über das reine Datensammeln hinausgehen. Prinzipiell ist aber schon dieser Punkt erwähnenswert, da, um einen objektiven Pressespiegel für eine Person zu erstellen, möglichst viele Quellen benutzt werden müssen. Die ausschliessliche Nutzung einer bestimmten Biographie-Seite kann somit auf keinen Fall ausreichen. Ein breiteres Spektrum stellt die Nutzung von Suchmaschinen zur Informationsgewinnung dar.

Allerdings ist das Spektrum der Informationen für eine einzige Anfrage hierbei zu gross - das Problem ist, die interessanten Daten zwischen den uninteressanten Daten herauszufinden. Dies ist das Problem des Information Retrieval. Der zu entwickelnde Intelligence Service soll natürlich über das Information Retrieval von Suchmaschinen hinausgehen.

Das grundsätzliches Problem ist, dass Suchmaschinen nicht konkrete Antworten liefern. Vielmehr wird eine Auswahl an Dokumenten geliefert, die die Antwort zu gestellten Anfrage höchstwahrscheinlich enthält. Was man aber oft möchte, ist auf eine Frage wie:
``Wann und wo findet die ICDM-07 statt?''
die Antwort:
``28.-31.10.2007, Omaha, Nebraska, USA''

zusammen mit der URL, auf der die Information gefunden wurde, zu erhalten.
Für solche Fragebeantwortung muss man nicht nur die relevanten Dokumente finden, sondern auch die relevanten Passagen - ein weiterer Punkt, der von Suchmaschinen nicht erbracht wird.
Wenn die Dokumente durch eine Auszeichnungssprache (XML) annotiert sind, ist die Suche in den relevanten Dokumenten erleichtert, so dass gezielt etwa nach Investitionen, Erfolgen, neuen Produkten, Börsenzahlen gesucht werden kann.
Die meisten Dokumente sind aber nicht annotiert. Man muss also algorithmisch nach Entitäten eines bestimmten Typs (z.B. Person, Ort, Firma) suchen.
Das Gebiet, das sich mit der Erkennung der Entitäten eines inhaltlichen Typs in Texten befasst, ist die Named Entity Recognition (NER) und verwendet statistische Verfahren und solche des maschinellen Lernens bzw. Data Mining. Somit ist die NER ein weiterer Bereich, mit dem sich die PG befassen muss.

Selbst wenn wir das Problem, die interessanten Informationen zu erfassen, einmal als gelöst betrachten, weist das Recherchieren noch mindestens ein anderes Problem auf, nämlich die strukturierte Zusammenstellung von Informationen zu einem Gesamtbild.
Beispielsweise wollen Firmen oft einen überblick über ihre Konkurrenz oder ihr eigenes Image in der öffentlichkeit erhalten. Solche Recherchen werden oft noch von Hand durch Abfolgen von Anfragen an Suchmaschinen und das Verfolgen von links durchgeführt.
Die Abfolge von Anfragen sollte jedoch automatisiert erfolgen, um ein allgemein nutzbares System zu schaffen. Für Politiker bietet sich hierfür beispielsweise die Internetseite Bundestag.de an. Hier sind zu jedem Abgeordneten die jeweiligen Biographien hinterlegt. Zusätzlich zu diesen offensichtlichen Daten kann man jedoch auch noch die digital vorliegenden Drucksachen (z.B. Anträge) und Protokolle verarbeiten. Nach durchgeführter NER über diesen Dokumenten sollen dann konkrete Fragen beantwortet werden.

Teilnehmer

Baumann, Björn
Böhmer, Martin
Cai, Wei
Firstein, Roman
Fritsch, Regina
Günal, Emel
Güner, Mustafa
Kaz, Erkan
Koloch, Rafael
Kubatz, Marius
Spierling, Daniel
Viefhues, Alexander
Zhu, Qingchui

PG-Realisierung

Die PG beginnt in jedem Semester mit einer Seminarphase und endet mit einer Evaluation. Die Studierenden planen ihre Arbeiten selbst, entscheiden über die Werkzeuge, die sie verwenden wollen (z.B. CVS, LaTex, XML-Editor), teilen sich in kleinere Teams ein - allerdings wird dies in den PG-Sitzungen von den Veranstaltern kritisch begleitet, damit es nicht zu falschen Zeitabschätzungen kommt und die PG erfolgreich innerhalb der 2 Semester abgeschlossen wird.

Werkzeuge

IE-Plugin für RapidMiner

1. Seminarphase: 09.,11. und 12.10.2007

  • Dienstag, 09.10.2007:
    • 10 Uhr - Vorstellung und Organisation (parallel Frühstück)
    • 11 Uhr - Björn Baumann: Named Entity Recognition
      • Information Extraction, Theory and Practice; Feldman, Ronen. http://www.cs.biu.ac.il/%7Efeldman/icml_tutorial.html. ICML Tutorial, 2006.
      • Introduction to Information Extraction Technology; Appelt, Douglas and Israel, David. IJCAI-Tutorial, 1999.
      • Named Entity Recognition; Cunningham, Hamish and Bontcheva, Kalina. http://gate.ac.uk/talks/ne-tutorial.ppt. Talk at the RANLP, 2003.
    • 12 Uhr - Martin Böhmer: Support Vector Machines
      • A Tutorial on Support Vector Machines for Pattern Recognition; Burges, Christoper J.C. In Data Mining and Knowledge Discovery, 2, 1999. pages 121 - 167.
      • Fast Training of Support Vector Machines using Sequential Minimal Optimization; Platt, John. In Advances in Kernel Methods - Support Vector Learning, 1999.
    • 13 Uhr - Mittagspause
    • 14 Uhr - Regina Fritsch: SVM struct
      • Support Vector Machine Learning for Interdependent and Structured Output Spaces; Tsochantaridis, Ioannis etal. In Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004.
    • 15 Uhr - Wei Cai: Hidden Markov Models
      • A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition; Rabiner, Lawrence R. In Proceedings of the IEEE, 1989. pages 257-286.
      • An Introduction to Hidden Markov Models; Rabiner, Lawrence R. and Juang, Biing-Hwang. In IEEE ASSP Magazine, 3, 1986. pages 4-16.
    • 16 Uhr - Roman Firstein: Maximum Entropy Markov Models
      • Maximum Entropy Markov Models for Information Extraction and Segmentation; McCallum, Andrew etal. In Proc. 17th International Conf. on Machine Learning, 2000. pages 591-598.
    • 17 Uhr - Felix Jungermann: Conditional Random Fields
      • Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data; Lafferty, John etal. In Proc. 18th International Conf. on Machine Learning, 2001. pages 282-289.

  • Donnerstag, 11.10.2007:
    • Clustering
      • 10 Uhr - Daniel Spierling: Cluster Ensembles
        • Cluster Ensembles - A Knowledge Reuse Framework for Combining Partitionings; Alexander Strehl and Joydeep Ghosh. Proceedings of AAAI 2002, Edmonton, Canada, 2002.
        • A mixture model for clustering ensembles; Topchy, A. and Jain, A. and Punch, W. In Proc. of SIAM Conference on Data Mining, 2004.
      • 11 Uhr - Erkan Kaz: Semi-Supervised Clustering
        • Semi-Supervised Clustering with User Feedback; David Cohn and Rich Caruana and Andrew McCallum. Technical report, 2000.
      • 12 Uhr - Alexander Viefhues: SVM Clustering
        • Supervised Clustering with Support Vector Machines; T. Finley and T. Joachims. In Proceedings of the International Conference on Machine Learning (ICML), 2005.
    • 13 Uhr - Mittagspause
    • 14 Uhr - Emel Günal: Indexierung für Suchmaschinen
      • Inverted Files for Text Search Engines; Zobel, Justin and Moffat, Alistair. In Computing Surveys, 77, 2006. pages 1-56.
    • 15 Uhr - Marius Kubatz: Webpageranking
      • The PageRank citation ranking: Brining order to the Web; Page, Lawrence etal. Technical report, 1998.
      • A Unified Probabilistic Framework for Web Page Scoring Systems; Diligenti, Michelangelo etal. In IEEE Transactions on Knowledge and Data Engineering, 1, 2004. pages 4-16.

  • Freitag, 12.10.2007:
Martin Böhmer: L-Trees

PG-Seite auf Sourceforge.net

PG-Treffen:

  • Dienstags 14 - 16 Uhr (c.t.)
  • Donnerstags 14 - 16 Uhr (c.t.)

Aufgaben des 1.Semesters:

  • Wahl eines Anwendungsszenarios, Festlegen der Fragen und der NE
  • Erstellen der Trainingsdatensätze
  • Experimente mit vorhandenen NER-Lernverfahren
  • Ansätze zur Verbesserung der NER

2. Seminarphase: 04.-08.02.2008 werden die Ergebnisse zusammengetragen, diskutiert und dokumentiert.

3. Seminarphase: Anfang April 2008

  • Automatische Thesaurus-Erstellung:
    • Chen et al.: Building a Web Thesaurus from Web Link Structure, 2003.
    • Chen et al.: Automatic Thesaurus Generation for an Electronic Community System, 1995.
  • Automatische Fragebeantwortung:
    • Pasca and Harabagiu: Answer Mining from On-Line Documents, 2001.
    • TREC Question-Answering Track Publications
  • Text-Clustering:
    • Zeng et al.: Learning to Cluster Web Search Results, 2004.
    • Zamir and Etzioni: Grouper: A dynamic clustering interface to web search results, 1999.
    • Wurst et al.: Localized Alternative Cluster Ensembles for Collaborative Structuring, 2006.
  • Webseiten-Ranking:
    • Page et al.: The PageRank citation ranking: Bringing order to the Web, 1998.
    • Kleinberg: Authoritative Sources in a Hyperlinked Environment, 1999.
    • Diligenti et al.: A Unified Probabilistic Framework for Web Page Scoring Systems, 2004.
  • First Story Detection:
    • Zhang et al.: Novelty and Redundancy Detection in Adaptive Filtering, 2002.
    • Allan et al.: First Story Detection In TDT Is Hard, 2000.
  • Topic Tracking:
    • Matsumura et al.: Discovery of Emerging Topics between Communities on WWW, 2001.
    • Matsumura et al.: Future Directions of Communities on the Web, 2001.
    • Jatowt et al.: Change Summarization in Web Collections, 2004.

Aufgaben des 2.Semesters:

  • Sammeln der Daten (mittels crawling-Techniken oder z.B. clickstream-Analyse)
  • Erstellung des Anfrageplans zur Erfassung von Informationen über einen Politiker oder eine Firma
  • Konkrete Ausnutzung der NER (Bezug auf erstes Semester) zur Fragebeantwortung

Ergebnis des 2. Semesters:

  • PG Abschlussbericht und -präsentation

PG-Antrag:

PG-Antrag

PG-Kurzvorstellung:

Kurzvorstellung

PG-Vorstellung:

Vorstellung








































   LS8 News - Teaching - Research - Projects - Software - Staff - General - Internal Imprint