Burrows` „Delta“

Burrows’ „Delta“ verstehen
Stefan Evert, Thomas Proisl
Friedrich-Alexander-Universität Erlangen-Nürnberg
Fotis Jannidis, Steffen Pielström, Isabella Reger, Christof
Schöch, Thorsten Vitt
Julius-Maximilians-Universität Würzburg
<philtag n="13"/>, Würzburg, 26. Februar 2016
Authorship attribution
(Juola 2006; Koppel et al. 2008; Stamatatos 2009)
I
Vordergründiges Ziel: Identifikation unbekannter oder strittiger
Autoren anhand stilistischer Merkmale
I
I
I
Federalist Papers: Hamilton vs. Madison
(Mosteller and Wallace 1963)
Gab es Shakespeare wirklich?
Robert Galbraith (The Cuckoo’s Calling) = J. K. Rowling
http://www.scientificamerican.com/article/how-a-computerprogram-helped-show-jk-rowling-write-a-cuckoos-calling/
I
Interessanter: Was sind die charakteristischen stilometrischen
Merkmale eines bestimmten Schriftstellers?
+ Merkmale, die besonders zur erfolgreichen Attribution beitragen
I
Können auf diese Weise auch gattungsspezifische Merkmale
gefunden und von autorenspezifischen unterschieden werden?
Authorship attribution
(Juola 2006; Koppel et al. 2008; Stamatatos 2009)
I
Autorschaftsattribution als Klassifikation
I
I
I
I
I
vorgegebene Liste von in Frage kommenden Autoren
Trainingsdaten: bekannte Texte dieser Autoren
überwachte Lernverfahren Ü relevante Merkmale + Gewichtung
Evaluation: Genauigkeit (accuracy)
Autorschaftsattribution als Clustering
unüberwachtes Lernverfahren auf Basis einer Textsammlung
Texte des gleichen Autors sollen in ein Cluster gruppiert werden
I Basis: stilometrisches Abstandsmaß für Texte
I Evaluation: adjusted Rand index (ARI, Hubert and Arabie 1985)
+ kann auch zur Klassifikation genutzt werden (nearest neighbour)
I
I
I
Einfaches und erfolgreiches Abstandsmaß: Burrows Delta
Burrows Delta (∆B )
(Burrows 2002)
I
Relative Häufigkeiten der 100–5000 häufigsten Wörter (MFW)
als stilistischer „Fingerabdruck“ eines Autors
standardisierte z-Werte: zi (D) =
fi (D) − µi
σi
2
the and to of
a
I
in was that he her
z(Madding Crowd) = ( .53, -.23, -.32, .20, 1.66, -.37, 1.04, .52, -.44, -.92, .03, . . .)
z(Tess of the d’U.) = ( .75, -.48, -.08, .51, -.24, -.87, .60, .41, -.14, -.47, 1.39, . . .)
z(Oliver Twist) = (1.05, .15, -.71, -.56, .37, -1.01, -.06, -.74, -.28, .48, -.94, . . .)
−2
−1
0
1
Hardy: Far from the Madding Crowd
Hardy: Tess of the d'Urbervilles
Abstandsmaße für Texte
I
I
Ähnlichkeit zwischen zwei „Fingerabdrücken“, d.h. Vektoren
z(D1 ) und z(D2 ), muss quantifiziert werden
Vektor = Punkt in einem nw -dimensionalen Raum
I
nw = Anzahl MFW = Dimensionalität des Vektors
y
A
6
5
Metrik =
geometrisches
Abstandsmaß
Manha%an:
d1(A,,B),=,5
4
3
Euclidean:
d2(A,,B),=,3.6
2
1
B
Cosine:
α(A,,B),=,41.6°
α
1
2
3
4
5
6
x
Die Delta-Familie
(Burrows 2002; Hoover 2004; Argamon 2008; Smith and Aldridge 2011)
I
Burrows Delta = Manhattan-Abstand (Burrows 2002)
∆B (D1 , D2 ) = kz(D1 ) − z(D2 )k1 =
nw
X
|zi (D1 ) − zi (D2 )|
i=1
I
Quadratic Delta = Euklidischer Abstand (Argamon 2008)
∆Q (D1 , D2 ) = kz(D1 ) −
z(D2 )k22
=
nw
X
(zi (D1 ) − zi (D2 ))2
i=1
I
Cosine Delta = Winkelabstand (Smith and Aldridge 2011)
Pnw
cos ∆∠ (D1 , D2 ) =
i=1 zi (D1 ) · zi (D2 )
kz(D1 )k2 · kz(D2 )k2
Delta verstehen
„In theory, theory and practice are the same. In practice, they are not.“
I
Empirische Studie zu Delta-Maßen (Jannidis et al. 2015)
drei Romankorpora (Deutsch, Englisch, Französisch)
jeweils 75 Romane von 25 verschiedenen Autoren
I Zeitraum: frühes 19. Jhd. bis Mitte des 20. Jhd.
I unüberwachtes Clustering in 25 Gruppen mit allen bekannten
Delta-Varianten und nw = 100, 1000, 5000 MFW
+ Beste Maße: Burrows Delta ∆B und Cosine Delta ∆∠
I
I
I
Gemeinsame Folgestudie (Evert et al. 2015)
systematische Untersuchung von nw und anderen Parametern
besseres Clusteringverfahren, Evaluation mit ARI
+ Längennormalisierung spielt entscheidende Rolle
I
I
I
Neue Ergebnisse (philtag / DHd 2016)
I
I
Gründe für positive Auswirkung der Längennormalisierung
Hypothesen: (i) Outlier vs. (ii) „Schlüsselprofil“
Parameter: Anzahl nw von MFW
80
60
40
(im folgenden nur noch Ergebnisse für deutsches Romankorpus)
10000
# features
5000
2000
1000
500
200
100
50
20
0
20
Burrows Delta
Quadratic Delta
Cosine Delta
10
adjusted Rand index (%)
100
German (z−scores)
Parameter: Anzahl nw von MFW
80
60
40
(im folgenden nur noch Ergebnisse für deutsches Romankorpus)
10000
# features
5000
2000
1000
500
200
100
50
20
0
20
Burrows Delta
Quadratic Delta
Cosine Delta
10
adjusted Rand index (%)
100
English (z−scores)
Parameter: Anzahl nw von MFW
80
60
40
(im folgenden nur noch Ergebnisse für deutsches Romankorpus)
10000
# features
5000
2000
1000
500
200
100
50
20
0
20
Burrows Delta
Quadratic Delta
Cosine Delta
10
adjusted Rand index (%)
100
French (z−scores)
Parameter: Längennormalisierung der Vektoren
80
60
Längennormalisierung ist entscheidend für gutes Clustering!
10000
# features
5000
2000
1000
500
200
100
50
20
0
20
40
Burrows Delta
Quadratic Delta
Cosine Delta
Burrows Delta / L1
Burrows Delta / L2
Quadratic Delta / L1
10
adjusted Rand index (%)
100
German (z−scores)
Warum ist Längennormalisierung so wichtig?
I
Hypothese 1: wenige „extreme“ z-Werte (outlier) üben großen
Einfluss auf Abstandsmaße aus und verzerren die Ergebnisse
I
I
derartige Ausreißer sind oft charakteristisch für einzelnen Text
Hypothese 2: charakteristisches Autorenprofil findet sich im
grundsätzlichen Muster positiver und negativer Abweichungen,
unabhängig vom Grad ihrer Ausprägung („Schlüsselprofil“)
Evidenz für Hypothese 1: Minkowski-Abstand
I
Minkowski-Delta als Verallgemeinerung: ∆B = ∆1 , ∆Q = ∆2
I
∆p ist umso anfälliger für Ausreißer, je größer p wird
v
u nw
uX
p
∆p (D1 , D2 ) = kz(D1 ) − z(D2 )kp = t
|zi (D1 ) − zi (D2 )|p
i=1
80
60
40
5000
2000
10000
# features
1000
500
200
100
50
20
0
20
Cosine Delta
Burrows (L1) Delta
L1 2−Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (z−scores, not normalized)
Evidenz für Hypothese 1: Minkowski-Abstand
I
Minkowski-Delta als Verallgemeinerung: ∆B = ∆1 , ∆Q = ∆2
I
∆p ist umso anfälliger für Ausreißer, je größer p wird
v
u nw
uX
p
∆p (D1 , D2 ) = kz(D1 ) − z(D2 )kp = t
|zi (D1 ) − zi (D2 )|p
i=1
80
60
40
5000
2000
10000
# features
1000
500
200
100
50
20
0
20
Cosine Delta
Burrows (L1) Delta
L1 2−Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (z−scores, L2−normalized)
Evidenz für Hypothese 2: Vektorlänge (Norm)
1.0
German (L2, 500 mfw)
●
●
●
●
0.6
Jean Paul
Kafka
Keller
Lewald
Marlitt
May
Raabe
Schopenhauer
Spielhagen
Tieck
Wassermann
Wieland
●
●
●
●●
●
●
●
●
●
●
●
●
●
0.4
●
0.2
mean negative score
0.8
●
Arnim
Dohm
Ebner Eschenbach
Fischer
Fontane
Fouqué
François
Freytag
Goethe
Gutzkow
Hahn Hahn
Hauff
Huber
0.0
0.2
0.4
0.6
mean positive score
0.8
1.0
1.2
Neuer Ansatz: Transformation der z-Werte
−0.2
−0.1
0.0
0.1
0.2
I
Längennormalisierung der Vektoren
Hardy: Far from the Madding Crowd
Hardy: Tess of the d'Urbervilles
Neuer Ansatz: Transformation der z-Werte
Abschneiden von Ausreißern (z.B. |z| > 1)
2
I
−2
−1
0
1
Hardy: Far from the Madding Crowd
Hardy: Tess of the d'Urbervilles
H1
Neuer Ansatz: Transformation der z-Werte
Ternarisierung: −1 (selten) / 0 (normal) / +1 (häufig)
−1.5 −1.0 −0.5
0.0
0.5
1.0
1.5
I
Hardy: Far from the Madding Crowd
Hardy: Tess of the d'Urbervilles
H2
Neuer Ansatz: Transformation der z-Werte
Ternarisierung: −1 (selten) / 0 (normal) / +1 (häufig)
−1.5 −1.0 −0.5
0.0
0.5
1.0
1.5
I
Hardy: Far from the Madding Crowd
Dickens: Oliver Twist
H2
Parameter: Transformation der z-Werte
80
60
40
# features
Abschneiden von Ausreißern (|z| > 2)
H1
10000
5000
2000
1000
500
200
100
50
20
0
20
Cosine Delta
Burrows (L1) Delta
L1 2−Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (z−scores clamped to range [−2, 2])
Parameter: Transformation der z-Werte
80
60
40
Ternarisierung (je 33%)
H2
10000
# features
5000
2000
1000
500
200
100
50
20
0
20
Cosine Delta
Burrows (L1) Delta
L1 2−Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (ternarized z−scores)
Parameter: Transformation der z-Werte
80
60
40
Ternarisierung (je 33%, ohne 200 MFW)
5000
10000
# features
2000
1000
500
200
100
50
20
0
20
Cosine Delta
Burrows (L1) Delta
L1 2−Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (ternarized, skipping 200 MFW)
Fazit
I
Empirische Befunde stützen „Schlüsselprofil“-Hypothese 2
I
Ternarisierte Vektoren sehr robust und ∆∠ ebenbürtig
I
Abschneiden von Ausreißern
I
Simulationsexperiment: Erzeugen von zufälligen Ausreißern als
„noise“ verschlechtert die Ergebnisse kaum
Ü
nur leichte Verbesserung
Nächste Schritte
I
Einfluss unterschiedlicher Clusteringverfahren
I
Experimente mit Textfragmenten (Textlänge, Konsistenz)
I
Wortartenfilter (z.B. Funktionswörter), Lemmatisierung, . . .
I
Relevanz einzelner Wörter (Beitrag zu Abstandsmaßen)
I
Anwendung auf interpretierbare stilometrische Merkmale?
Dank & Diskussion
Auswirkung der Transformationen auf Verteilung
2
4
6
1.5
0
2
4
6
−2
0
2
4
6
−2
0
2
4
6
ternarized after 1000 MFW
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
1.0
0.5
0.0
distribution of feature values
0.5
−2
ternarized z−scores
1.5
0
0.0
0.5
0.0
−2
quantile transformation
z−scores w/o outliers
1.0
1.5
normalized vectors
1.0
1.5
1.0
0.5
0.0
distribution of feature values
z−scores (German)
−2
0
2
4
6
−2
0
2
4
6
Vergleich von Clustering-Verfahren
80
60
40
5000
2000
10000
# features
1000
500
200
100
50
20
0
20
k−medoids (PAM)
single link
complete
Ward
Ward (hclust)
10
adjusted Rand index (%)
100
German (Burrows Delta)
Clustering-Verfahren: PAM vs. Ward
80
60
40
5000
2000
10000
# features
1000
500
200
100
50
20
0
20
Cosine Delta
L1 2−Delta
Burrows (L1) Delta
Quadratic (L2) Delta
L4−Delta
10
adjusted Rand index (%)
100
German (z−scores, Ward clustering)
Learning curves
I
I
Experimente wurden mit den ganzen Romanen durchgeführt
Funktioniert Delta auch bei kürzeren Texten?
+ zwei Fallstudien mit Cosine Delta ∆∠ und nw = 2000 MFW
Learning curves: Clustering
alle Texte auf die angegebene Zahl von Token gekürzt
Learning curves: Klassifikation
ein Text gekürzt, andere Romane ungekürzt als Trainingsdaten
References I
Argamon, Shlomo (2008). Interpreting Burrows’s Delta: Geometric and Probabilistic
Foundations. Literary and Linguistic Computing, 23(2), 131 –147.
Burrows, John (2002). ‘Delta’: a Measure of Stylistic Difference and a Guide to Likely
Authorship. Literary and Linguistic Computing, 17(3), 267 –287.
Evert, Stefan; Proisl, Thomas; Jannidis, Fotis; Pielström, Steffen; Schöch, Christof;
Vitt, Thorsten (2015). Towards a better understanding of Burrows’s Delta in
literary authorship attribution. In Proceedings of the Fourth Workshop on
Computational Linguistics for Literature, Denver, CO.
Hoover, David L. (2004). Delta Prime? Literary and Linguistic Computing, 19(4), 477
–495.
Hubert, Lawrence and Arabie, Phipps (1985). Comparing partitions. Journal of
Classification, 2, 193–218.
Jannidis, Fotis; Pielström, Steffen; Schöch, Christof; Vitt, Thorsten (2015). Improving
Burrows’ Delta - An empirical evaluation of text distance measures. In Digital
Humanities Conference 2015, Sydney.
Juola, Patrick (2006). Authorship attribution. Foundations and Trends in Information
Retrieval, 1(3), 233–334.
Koppel, M.; Schler, J.; Argamon, S. (2008). Computational methods in authorship
attribution. Journal of the American Society for information Science and
Technology, 60(1), 9–26.
References II
Mosteller, Frederick and Wallace, David L. (1963). Inference in an authorship problem.
Journal of the American Statistical Association, 58(302), 275–309.
Smith, Peter W. H. and Aldridge, W. (2011). Improving authorship attribution:
Optimizing Burrows’ Delta method. Journal of Quantitative Linguistics, 18(1),
63–88.
Stamatatos, Efstathios (2009). A survey of modern authorship attribution methods. J.
Am. Soc. Inf. Sci. Technol., 60(3), 538–556.