\documentclass[utf8]{beamer}

% \usetheme{Hannover}
 \usetheme[left]{sidebar}

% \usetheme{Berkeley}
% \usetheme{classic}
% \usetheme{default}
% \usetheme{Boadilla}
% \usetheme{boxes}
% \usetheme{Madrid}
% \usetheme{Marburg}
% \usetheme{Pittsburgh}
%\usetheme{Singapore}

\usepackage{graphics}
\usepackage[ngerman]{babel}
\usepackage{url}
\usepackage{colortbl}
\usepackage{pstricks}

\definecolor{lightgray}{rgb}{0.9, 0.9, 0.9}

\title{WikiWord}
\subtitle{Diplomarbeit:
Automatischer Aufbau eines
multilingualen Thesaurus
durch Extraktion semantischer 
und lexikalischer Relationen
aus Wikipedia}
\date{31. Januar 2008}
\author{Daniel Kinzler}
\institute{Universität Leipzig}

\begin{document}
\setbeamertemplate{footline}
{%  
\begin{beamercolorbox}[wd=\paperwidth,ht=0.25ex,dp=1ex,right,rightskip=1ex]{empty}%
\usebeamercolor[fg]{subsection in sidebar shaded}%
\usebeamerfont{subsection in sidebar shaded}%
\insertframenumber{} / \inserttotalframenumber%
\end{beamercolorbox}%
}

\frame{\titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Zielsetzung}
\subsection{Ziele} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Überblick}

	\large
	Ziel ist der automatische Aufbau eines Thesaurus. Schritte:
	\begin{itemize}
		\item	Ziele genauer spezifizieren
		\item	Methode entwerfen und anwenden
			\begin{itemize}
				\item	Sprachspezifische Daten
				\item	Heuristiken zur Extraktion
				\item	Sprachunabhängige Daten
				\item	Merging-Verfahren
				\item	Datenaustausch
			\end{itemize}
		\item	Ergebnis bewerten
	\end{itemize}
}

\frame
{
	\frametitle{Ziel: Aufbau eines Thesaurus}
	Zu erhebende Daten:
	\begin{itemize}
		\item	Term-Konzept-Beziehung $\rightarrow$ Synonyme, Homonyme
		\item	Sprachübergreifende Konzepte
		\item	Ober/Unterbegriffe ("`weich"')
		\item	Definitionen
		\item	evtl "`semantischer Kontext"' (z.B. Kookkurrenzen)
	\end{itemize}
}

\subsection{Motivation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Nutzen}
	Hilfreich für:
	\begin{itemize}
		\item	Überwinden der \textit{Semantic Gap}
		\item	Zusammenführen sprachspezifischer Wissensstrukturen zu sprachunabhängigen
		\item	Basis für manuelle Arbeit an Thesauri, Dictionaries, etc
		\item	Suchindex (Information Retrieval)
		\item	Disambiguierung
		\item	Query-Expansion
	\end{itemize}

	Aber: keine formale \textit{Taxonomie}, zu schwach für \textit{Reasoning}
}

\frame
{
	\frametitle{Nutzer}
	Beispiele für Projekte, die diese Daten nutzen könnten:
	\begin{itemize}
		\item	Wortschatz: Bedeutungen, Übersetzungen, Oberbegriffe
		\item	OmegaWiki: SynSets, Oberbegriffe
		\item	DBPedia, FreeBase: Mehrsprachigkeit, Suche
		\item	WordNet (YAGO): SynSets, Mehrsprachigkeit
		\item	Wikipedia: Suchindex
	\end{itemize}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Methode}
\subsection{Sprachspezifische Daten} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{LocalConceptStore}

	\includegraphics[width=1\textwidth]{LocalConceptStore-ER}

	\scriptsize
	\begin{itemize}
		\item "`Bedeutung"' modelliert als Interpretation einer "`Referenz"'
		\item Nicht jede Resource beschreibt ein Konzept
	\end{itemize}
}
\frame
{
	\frametitle{Ablauf der Datenextraktion}
	
	\includegraphics[width=1\textwidth]{ConceptImport-Flow}
}
\subsection{Heuristiken} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Heuristiken: Typen}

	Heuristiken modellieren \textit{Konventionen} der Wikipedia.
	\vspace{0.4cm}
	
	Typen von Seiten:

	\begin{itemize}
		\item Konzept ("`Richtiger"' Artikel)
		\item Redirect, Disambiguierung, Kategorie
		\item Löschkandidaten, ...
	\end{itemize}

	Typen von Konzepten:

	\begin{itemize}
		\item Ort, Person, Datum
		\item Zahl, Name, ...
		\item Nützlich als Filter
	\end{itemize}

	Bestimmt durch Pattern-Matching (Kategorien, Templates, etc)
}
\frame
{
	\frametitle{Heuristiken: Broader und Alias}

	Zuordnung von Oberbegriffen:
	\vspace{0.4cm}

 	\begin{itemize}
		\item Category: {\scriptsize \texttt{[[Category:Physik]]}}
		\item Titel: {\scriptsize \textit{Leiter\_(Physik)}}
 	\end{itemize}
 
	Definition von Aliasen 
 
	\begin{itemize}
		\item Redirects: {\scriptsize in \textit{Elektrischer\_Leiter}:\\ \texttt{\#REDIRECT [[Leiter\_(Physik)]]}}
		\item Sort-Key von "`Hauptartikeln"': {\scriptsize in \textit{Book}: \texttt{[[Category:Books|*]]}}\\
			\scriptsize (Nützlich vor allem, wenn Kategorien im Plural benannt sind)
	\end{itemize}
 
	Alias-Einträge bedingen Verschmelzen von Konzepten in der Datenank
}
\frame
{
	\frametitle{Heuristiken: Terme}

	Zuordnung von Termen zu Konzepten

	\begin{itemize}
		\item Links: {\scriptsize \texttt{[[Leiter\_(Physik)|\underline{Leitern}]]}} \textit("`implizite"' Zuordnung)
		\item Titel: {\scriptsize \textit{\underline{Leiter}\_(Physik)}}
		\item Sort-Key: {\scriptsize in \textit{Albert Einstein}: \\
			 \texttt{[[Category:Physiker|\underline{Einstein, Albert}]]}}
		\item Redirects: {\scriptsize in \textit{\underline{Elektrischer\_Leiter}}: \\
			\texttt{\#REDIRECT [[Leiter\_(Physik)]]}}
		\item Disambiguierung: {\scriptsize in \textit{\underline{Leiter}}: \\
			\texttt{* [[Leiter (Gerät)]], ein Gerät mit Sprossen zum Hinauf- und Hinabsteigen\\
			* [[Leiter (Physik)]], Stoffe, die Energie oder Teilchen weiterleiten können\\
			\{\{Begriffsklärung\}\}
		}}
	\end{itemize}
}
\frame
{
	\frametitle{Term-Konzept-Beziehung: Evaluation}

	Evaluation der Akkuratheit der Zuordnung von Termen zu Konzepten:
	\begin{itemize}
		\item Wähle zufälliges Konzept 
		\item Bewerte jeden Term, der diesem Konzept zugeordnet ist: 
			\textit{Exakt, Variante, Verallgemeinerung, Unterbegriff, Fehler}
		\item Berechne Anteile a) direkt pro Term, und b) skaliert mit Frequenz der Verwendung
		\item Betrachte Auswirkung von Cut-Off
		\item Bzw. betrachte die Auswirkung der Heuristiken, die die Terme geliefert haben
		\item Stichprobe: ca. 200 Konzepte, deutsche Wikipedia
%		\item "`nebenbei"' zu Bewerten: Definitions, Typ
	\end{itemize}

}
\frame
{
	\frametitle{Term-Konzept-Beziehung: Akkuratheit}

	\vspace{0.6cm}

	\begin{tabular}{|l||r|r||r|r|}
		\hline
		\textbf{Bewertung} & 
		\textbf{types} & 
		\textbf{\%} & 
		\textbf{tokens} & 
		\textbf{\%} \\
		\hline
		\hline
		\textit{Gesamt}     & 647 & 100 & 3449 & 100 \\
		\hline
		\hline
		\textit{Exakt}      & 398 &  62 & 2967 & 86 \\
		\hline
		\textit{Variante}   & 87  &  13 &  218 & 6 \\
		\hline
		\textit{Verallg.}   & 52  &   8 &  75  & 2 \\
		\hline
		\hline
		\textit{Unterbeg.}  & 83  &  13 & 112  & 3 \\
		\hline
		\textit{Fehler}     & 27  &   4 &  77  & 2 \\
		\hline
	\end{tabular}
	
	% mode		types	tokens	%types	%tokens
	% TOTAL		647	3449	100.0	100.0
	% GOOD		398	2967	61.5	86.0
	% VARIANT	87	218	13.4	06.3
	% BROADER	52	75	08.0	02.2
	% NARROWER	83	112	12.8	03.2
	% BAD		27	77	04.2	02.2

	\vspace{0.4cm}
	\scriptsize
	\begin{itemize}
		\item \textit{Verallgemeinerung} problematisch: \textit{"`Amerika"'} für \textit{"`USA"'}
		\item \textit{Unteerbegriff}: Anteil vermutlich abhängig von der Granularität, also Größe des Wikis
	\end{itemize}
}
\frame
{
	\frametitle{Term-Concept Beziehung: Cut-Off}

	Effekte verschiedener Cut-Off Methoden, Einfluss von Ankertexten 
	({\scriptsize \texttt{[[Leiter\_(Physik)|Leitern]]}})

	\vspace{0.6cm}

	\footnotetext[1]{types}
	\footnotetext[2]{tokens}
	\footnotetext[3]{cover, also Anteil an der Anzahl für "`Alle"'}
	\footnotetext[4]{inklusive Varianten (Flexion, Großschreibung)}
	\footnotetext[5]{inklusive Varianten und Verallgemeinerungen (\textit{totum pro parte})}
	\begin{tabular}{|l||r|r||r|r||r|r|}
		\hline
		 & 
		\multicolumn{2}{|c|}{\textbf{\%cover\footnotemark[3]}} & 
		\multicolumn{2}{|c|}{\textbf{\%good\footnotemark[4]}} &
		\multicolumn{2}{|c|}{\textbf{\%good+\footnotemark[5]}} \\ 
		\hline
		\textbf{Cut-off} & 
		\textbf{t\footnotemark[1]} & 
		\textbf{n\footnotemark[2]} & 
		\textbf{t\footnotemark[1]} & 
		\textbf{n\footnotemark[2]} & 
		\textbf{t\footnotemark[1]} & 
		\textbf{n\footnotemark[2]} \\
		\hline
		\hline
		\textit{$\text{ohne cut-off}$} & 100 & 100 & 74 & 92 & 79 & 93\\
		\hline
		\textit{$fq>1$}                  & 53 & 91 & 90 & 95 & 92 & 96\\
		\hline
		\rowcolor[gray]{.9} \textit{$fq>2$}                  & 31 & 83 & 93 & 96 & 95 & 97\\
		\hline
		\rowcolor[gray]{.9} \textit{$fq>1 \vee \text{exp.}$} & 71 & 94 & 83 & 93 & 86 & 95\\
		\hline
		\textit{$fq>2 \vee \text{exp.}$} & 65 & 92 & 82 & 94 & 86 & 95\\
		\hline
		\textit{$\text{nur exp.}$}       & 60 & 88 & 81 & 94 & 85 & 95\\
		\hline
	\end{tabular}

	% 211 concepts:
	% all		100.0	100.0	74.2	91.5	79.7	93.3
	% >1		52.5	90.9	89.5	94.9	91.8	96.0
	% >2		30.8	82.5	93.0	95.9	94.6	96.8
	% >1 or exp	70.9	94.4	80.8	93.4	85.5	94.9
	% >2 or exp	64.9	92.1	81.6	94.0	86.0	95.3
	% only exp	60.4	88.1	80.6	94.0	85.4	95.3
}
\frame
{
	\frametitle{Retrieval: Evaluation}

	\begin{itemize}
		\item Suchindex für Bedeutungen von Termen
		\item Verglichen mit Volltext-Suche (Google, Wikipedia/Lucene), bestimme Precision/Recall
	\end{itemize}


	\begin{itemize}
		\item Suche zufälligen Term mittels Google, Wikipedia, und WikiWord
		\item Vereinige Ergebnisse, Bewerte für jede gefundene Seite, ob sie eine Bedeutung des Terms beschreibt
		\item Gold-Standard: alle "`guten"' Seiten, die von Google+Wikipedia gefunden wurden
		\item Recall: "`guten"' Seiten, die WikiWord auch gefunden hat.
	\end{itemize}

	\vspace{0.2cm}
	\small
	Problem: Precision von Google+Wikipedia ist (bezgl der Fragestellung) extrem schlecht.
}
\subsection{Sprachunabhängige Daten} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Sprachunabhängige Daten}
	\begin{itemize}
		\item Idee: Kopieren und Vereinigen
		\item Kopieren aller Konzepte aus allen Sprachen
		\item Vereinigen "`passender"' Konzepte, anhand der LangLink-Relation
		\item Zwei Konzepte der selben Sprache dürfen nie vereinigt werden
		\item Unterschiedliche Granularität der Wikis sorgt für ungenaue LangLinks
		\item Zwei Algorithmen: \textit{Reciprocal Link} und \textit{Translation Set Similarity}	
	\end{itemize}
}
\frame
{
	\frametitle{GlobalConceptStore}
	\includegraphics[width=1\textwidth]{GlobalConceptStore-ER}
}
\frame
{
	\frametitle{Greedy Reciprocal Link Merging}
	\includegraphics[width=1\textwidth]{ConceptMerging-Greedy-1}

	Sprachübergreifende Konzepte: \textit{Reciprocal Link} Methode
}
\frame
{
	\frametitle{Translation Set Similarity Merging}
	\includegraphics[width=0.8\textheight]{ConceptMerging-Similarity-1}

	\textit{Set Similarity} Methode: betrachtet auch "`externe"' Ähnlichkeit und "`externe"' Konflikte. Ist aber aufwändiger.
}
% \frame
% {
% 	\frametitle{Ähnlichkeitsmaße}
% 
% 	\begin{tabular}{|l||l|l|c|}
% 		\hline
% 		\textbf{d} & 
% 		$\frac{|A \cap B|}{min(|A|,|B|)}$ & 
% 		$\frac{|A \cap B|}{|A \cup B|}$ & \\
% 		\hline
% 		\hline
% 		xx, yy & 0.666\ldots & 0.333\ldots & \\
% 		\hline
% 		xx, yy & 0.75 & 0.333\ldots & \textit{Konflikt} \\
% 		\hline
% 		yy, zz & 0.333\ldots & 0.1666\ldots & \\
% 		\hline
% 		\hline
% 		xx+yy, zz & 0.75 & 0.4286\ldots & \textit{Konflikt} \\
% 		\hline
% 	\end{tabular}
% 
% 	\begin{itemize}
% 		\item Verzeiht bzw. bestraft "`fehlende"' Einträge
% 		\item evtl Kombination sinnvoll:
% 		\begin{math}
% 			{\displaystyle d(A,B) 
% 			= \alpha \cdot \frac{|A \cap B|}{min(|A|,|B|)} 
% 			+ (1 - \alpha) \cdot \frac{|A \cap B|}{|A \cup B|}}
% 		\end{math}
% 	\end{itemize}
% }
\frame
{
	\frametitle{Merging: Testlauf}

	Testlauf auf thematischem Auszug ("`Berge"') aus fünf Wikipedias, Greedy Reciprocal Link Merging.

	\vspace{0.4cm}

	\small

	\begin{columns}[t]
		\column[T]{0.4\textwidth}
		\begin{tabular}{|l||r|}
			\hline
			\textbf{Seiten} & 31969\\
			\hline
			\textbf{L. Konzepte} & 28543\\
			\hline
			\hline
			\textbf{G. Konzepte} & 25412\\
			\hline
			\textbf{Verbl. Links} & 2124\\
			\hline
			\textbf{Konflikte} & 2\\
			\hline
		\end{tabular}
		\column[T]{0.4\textwidth}
		\begin{tabular}{|l||r|}
			\hline
			\textbf{1er-Gruppen} & 23367	\\ 
			\hline
			\textbf{2er-Gruppen} & 1331	\\
			\hline
			\textbf{3er-Gruppen} & 415	\\
			\hline
			\textbf{4er-Gruppen} & 228	\\
			\hline
			\textbf{5er-Gruppen} & 71	\\
			\hline
		\end{tabular}
	\end{columns}

	\vspace{0.4cm}

	\begin{tabular}{|l||r|r|r|r|r|r|r|}
		\hline
		\textbf{Lang}  & \textbf{Cncpts} & \textbf{Links} & \textbf{fr} & \textbf{en} & \textbf{de} & \textbf{nl} & \textbf{no}      \\
		\hline
		\textbf{fr} & 15115 & 59418 & -  &  5369  &  3573  &  5169  &  877  \\ 
		\hline
		\textbf{en} & 7805 & 13752 & 1147  &  - &  1621  &  740  & 494    \\
		\hline
		\textbf{de} & 3692 & 7841 & 808  &  1110  &  - &  597  & 208     \\
		\hline
		\textbf{nl} & 1111 & 5075 & 404   &  455  &  602  &  - &    143     \\
		\hline
		\textbf{no} & 820 & 5030 & 238  &  508  &  339  &  241  &  -      \\
		\hline
	\end{tabular}
}
\frame
{
	\frametitle{Merging: Evaluation}

	\begin{itemize}
		\item Frage nach "`bestem Cluster"'
		\item Bewertung schwierig, ggf. viele alternative Kombinationen ("`Konflikte"')
		\item Möglich: "`saubere"' Cluster zählen
		\item Möglich: "`einsame"' Konzepte finden
	\end{itemize}
}
\subsection{Datenaustausch} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{SKOS}
	\begin{itemize}
		\item Austauschformat für \textit{strukturierte und maschinenlesbare Vokabulare}
		\item W3C Draft. Basiert auf RDF (Semantik: OWL)
		\item \texttt{skos:Concept} - eindeutige URI (Achtung Identitätskrise!)
		\item \texttt{skos:definition} - erster Satz und URL der Wikipedia-Seite (pro Sprache)
		\item \texttt{skos:prefLabel} 1x, \texttt{skos:altLabel} beliebig (pro Sprache)
		\item \texttt{skos:broader}, \texttt{skos:narrower} und \texttt{skos:related} (Konflikt mit Broader!)
		\item \textit{Reifikation} ist umständlich (z.B. Frequenzen), \textit{Link}-Relation fehlt
	\end{itemize}
}
\frame
{
	\frametitle{Topic Maps}
	\begin{itemize}
		\item Abstaktes Datenmodell für Wissensstrukturen
		\item ISO Standard, XML Binding (XTM)
		\item \texttt{Topic}: mit \textit{Subject Indicators} (URLs von Wiki-Seiten)
		\item \texttt{Scope}: Sprachen
		\item \texttt{Name}: \textit{Base Name} 1x pro Scope, \textit{Variant Names} beliebig
		\item \texttt{Occurance}: z.B. für die Definition
		\item \texttt{Relations}: typisiert, \textit{Similar, Broader, Links, ...} (Standard?)
		\item \textit{Reifikation}: wird direkt unterstützt, auch für Names
	\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bewertung}

\subsection{Abgrenzung} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Abgrenzung}
	\begin{itemize}
		\item Term-Konzept-Relation - die meisten anderen betrachten nur eines oder unterscheiden nicht.
		\item Sprachübergreifend - die meisten anderen betrachten nur eine Sprache
		\item Heuristiken modellieren direkt Wikipedia Konventionen
%		\item Arbeitet auf Wikitext - keine Probleme mit redaktionellen Kategorien etc
		\item Kein Language Processing, kein Volltext - keine Stoppwörter etc
		\item Kein Fakten-Extraktion, keine Taxonomie (nur "`weiche"' Kategorisierung)
		\item Effizient (besser als Quadratisch, im Wesentlichen linear);
			effektiv ca. 50 Seiten/Sekunde (Import: ca. 150/Sekunde)
	\end{itemize}
}

\subsection{Ergebnis} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Fazit}
	\begin{itemize}
		\item Substantive, Eigennamen
		\item Mehrwort-Begriffe
		\item Häufige Varianten (Flexion)
		\item keine Stoppwörter
	\end{itemize}
	\begin{itemize}
		\item Hochwertige SynSets
		\item Geeignet als Such-Index
		\item Geeignet als Wörterbuch
	\end{itemize}
}

\subsection{Ausblick} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Ausblick}
	\begin{itemize}
		\item Information-Retrieval: Query-Expansion? PageRank?
		\item Netzwerk-Analyse: Clustern über Link-Struktur? Kohyponyme aus Kookkurrenzen n-ter Ordnung...
		\item Disambiguierung: Kontext-Vergleich (InLinks + OutLinks + Broader + Narrower + Kookkurrenten + ...)
		\item Vergleich mit WordNet etc
	\end{itemize}
}

\subsection{Danke} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
	\frametitle{Danke}

	\begin{center}
		\large
		Ende

		\vspace{2cm}
	
		{\scriptsize
		\url{http://brightbyte.de/page/WikiWord}\\
		\url{http://brightbyte.de/repos/papers/2008/}
		}
	\end{center}
}

\end{document}
