Home

Inleiding Informatiekunde II

Colleges 2003-2004

Tweede Semester, eerste helft.

Hoorcolleges: Harmonie H12.025 wo. 15:15-17

Docent: Hennie Klein

Bureau : Harmonie H11.426 Spreekuur ma. 13:15-15

Email: hkleinApestaartjelet.rug.nl

Inhoud

De Inleiding Infomatiekunde, Deel II voor 2003-2004 wordt door Hennie Klein verzorgd. Het doel is om in groepen een project in de geeesteswetenschappelijke informatica te onderzoeken, te ontwerpen, en verslag hiervan uit te brengen. Het wordt op prijs gesteld waar onderdelen van het ontwerp daadwerkekelijk uitgevoerd kunnen worden.

Thema: De Genealogie van Documenten

Charles H. Bennett, Ming Li, en Bin Ma hebben geschetst hoe ze een de geschiedenis van verschillende versies van een kettingbrief konden achterhalen. Zie Chain Letters and Evolutionary Histories in Scientific American, juni 2003, Vol. 288(6), pp.76-81. (Let op dat de link alleen naar Scientific American in het algemeen verwijst. U moet dan in de aangeboden menus de goede artikel vinden.)

De auteuren nemen in aanspraak dat hun methode "de stamboom van wat dan ook" laat achterhalen.

Materiaal

Om te beginnen is het nodig om material te krijgen. Een deel van het werk ligt er in verschillende versies van een tekst te vinden (die man ook voor analyse kan gebruiken). We stellen voor om SPAM hiervoor te gebruiken, i.h.b. de bekende mail van Lagos, Nigeria, waarin men uitgenodigd wordt om deel van 20 Millioen dollar of meer. Het voorstel is dat iedere groep 200 honderd emails van deze soort proberen te krijgen. We hebben geen preciesere bron van deze mails, dus u moet dit uitzoeken. Ik heb enkele voorbeelden (alleen vanaf 10 feb 2004) in een archief opgeslaan.

Taak

De taak is dan tot een idee te komen welke versie van deze mail van welke andere afstammen. Het is prima om een experiment uit te voeren waarin men met een simpele idee probeert deze onstaansgeschiedenis ("genealogie") te achterhalen, b.v. door van iedere brief een histogram van woordfrequenties af te leiden, en dan deze als indicatie van vergelijkbaarheid te gebruiken.

Het is goed om op te merken dat het bepalen van vergelijkbaarheid niet hetzelfde is als het bepalen van de genealogie. Het idee is dat elementen die uit hetzelfde tak van een genealogie vergelijkbaarder moeten zijn dan elementen uit andere takken. Maar vergelijkbaarheid legt de volgorde van onstaan echter niet vast. Desondanks focuseren we hierop als een eerste stap---een indicaties van de stamboom.

Om vergelijkbaarheid te bepalen, zou men de (simpele) algoritme DICE kunnen gebruiken (zie Inl. IK I, wk. 6). Onderaan zijn ook andere voorbeelden. Het resultaat is in het simpelste geval een tabel of matrix van "vergelijkbaarheidswaarden". In zo'n tabel kijkt men bij brief i in rij i en bij brief j in colom j. De maat van vergelijkbaarheid staat dan in cel (i,j).

Visualisering

www.let.rug.nl/~kleiweg/ >> "Software" >> "Clustering" heeft programma's om stambomen af te leiden op basis van vergelijkbaarheidsmatrixen, en verder om ze in postscript te tekenen. Zoiets is nuttig om resultaten te visualiseren.

Vergelijkbaar Werk

Om zo'n thema te onderzoeken is het o.a. zinvol om vergelijkbaar werk van andere te bekijken. Een deel van het project is informatie hierover te verzamelen. Dit kan op de world-wide web. Het verdient de aanbeveling om te kijken naar wat bekend is over de volgende gebieden:
  • stemmatology - de wetenschap over de onstaansgeschiedenis van tekst, b.v. hoe men bepaalt of een bepaalde document waarschijnlijk een afschrift is van een oudere. De bijbel is een geliefd object van studie in de stemmatology. Zie i.h.b. het werk van Piet van Reenen (VU) over stemmatologie.
    • Andere mensen geven weer de voorkeur aan de naam:
  • cladistics - de wetenschap die vooral in de biologie gedreven wordt om stambomen van soorten te verkrijgen. Zie Peter Robinson's werk over Chaucer's "Wife of Bath", en bericht over zijn program Collate. A Program for Interactive Collation of Large Textual Traditions
    • Een verwante lijn van onderzoek heeft niet teksten in visier, maar talen.
  • Language Trees and Zipping is de titel van een artikel van Dario Benedetto, Emanuele Caglioti en Vittorio Loreto in een natuurkundige tijdschrift.

    De basisidee van Benedetto et al is simpel: Men gaat ervan uit dat men steekproeven van teksten van vergelijkbare lengte heeft. Wil men toetsen of (a,b) vergelijjkbaarder zijn dan (a,c), zo is het voldoende om te kijken of het resultaat van compressie van a samen met b kleiner is dan het resultaat van compressie van a samen met c. De compressie zal alle punten van overeenkomst proberen te baat te nemen, en dus iedere spoor van vergelijkbaarheid achterhalen.

    Dit lijkt me ook een idee die toetsbaar zou moeten zijn. Een compressieprogramma zoals gzip is voldoende om experimenten uit te voeren. Let ook op dat Benedetto et al. ook critici hebben. Zie b.v. het commentaar van de computationele taalkundige, Joshua Goodman.

  • AuteurschapNog een gebied waarin teksten worden vergeleken is in de bepalen van auteurschap. Dit heeft een lange geschiedenis, maar de inzet van exacte methoden om auteurschap te bepalen is controversieel.

    Een bijzonder kritische stem is die van Joseph Rudman

  • Plagiaat Zeker het makkelijkst te herkennen is plagiaat, het wel of niet bewust afschrijven van een andere. Plagiaat is alleen lastig i.v.m. het boven waten halen van een origineel.

    • Enkele verwijzingen in dit gebied.

    Language Identification and Authorship Attribution

    1. Jussi Karlgren and Douglass Cutting 1994. Recognizing Text Genres with Simple Metrics Using Discriminant Analysis Proceedings of COLING 94, Kyoto.
    2. Thomas Bayer, Ingrid Renz, Michael Stein, Ulrich Kressel 1996. Domain and Language Independent Feature Extraction for Statistical Text Categorization. Proceedings of the Workshop on Language Engineering for Document Analysis and Recognition. Brighton, UK, 1-2 Apr 1996
    3. Brett Kessler, Geoffrey Nunberg, Hinrich Schuetze 1997 Automatic Text Genre Detection Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and the 8th Meeting of the European Chapter of the Association for Computational Linguistics, pages 32-38, Morgan Kaufmann Publishers, San Francisco CA, 1997
    4. Benedetto, D., Caglioti, E. & Loreto, V. 2002 Language trees and zipping. Physical Review Letters, 88, 048702.
    5. Li, M. et al. 2001 An information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics, 17, 149 - 3154.
    6. E. Stamatatos, N. Fakotakis and G. Kokkinakis 1999 Automatic Authorship Attribution EACL. 1999
    7. E. Stamatatos, N. Fakotakis, G. Kokkinakis 2001 Computer-based Authorship Attribution without Lexical Measures Computers and the Humanities, Volume 35, Issue 2, May 2001, pp. 193-214.
    8. E. Stamatatos, N. Fakotakis, G. Kokkinakis 2000 Automatic Text Categorization in Terms of Genre and Author Computational Linguistics, Vol. 26, Issue 4 - December 2000 471-495.
    9. Tsukasa MATSUURA 2000 Authorship Attribution in Japanese Modern Sentences via N-gram Distribution Mathematical Linguistics, vol.22, no.6, 225-238.
    10. Paul Clough 2000 Plagiarism in natural and programming languages: an overview of current tools and technologies, CS-00-05, Internal Report, Department of Computer Science, The University of Sheffield, July 2000.

    Verslaggen

    Formatering van Verslaggen

    Bij de verslaggeving moet gebruik worden gemaakt van het formateringsprogramma LaTeX. Als u niet hiermee bekend bent, verdient het de aanbeveling om ook het volgende te lezen. Deze zijn er om de eerste stappen en ook het nakijken te versimpelen. Men hoeft zeker niet alles in deze lijst door te werken!

    Bij alle opdrachten gaan de docenten van informatiekunde ervan uit dat studenten alleen hun eigen werk indienen. Zie de verantwoordelijkheden van studenten voor motivatie en details. Soms is de reactie van studenten dat ze het niet zo bedoelden, maar de wetenschappelijke cultuur vereist streng dat men alle belangrijke bronnen identificeert.
    Hennie Klein
    Last modified: Tues Oct 21 16:00:26 METDST 2003