\subsubsection{Vorwort}
Der vorliegende Abschnitt dient zur Lernenden Suchmaschinen. Und er
basiert auf einem Paper von Thorsten Joachims  \cite{Joachims/2002a}. Das klassische
Anwendungsgebiet der Lernenden Suchmaschinen sind
Literaturdatenbanken, die heute in Form Digitaler Bibliotheken
zunehmend an Bedeutung gewinnen. Lernenden Suchmaschinen sind
besonders populär geworden durch die Anwendung in
Internet-Suchmaschinen; dadurch kommt jeder Internet-Nutzer mit
IR-Methoden in Berührung. Jeder, der eine dieser Anwendungen
wiederholt genutzt hat, wird die wesentlichen Unterschiede zwischen
Suchmaschinen-Anwendungen und denen klassischer Datenbanksysteme
leicht erkennen:
 \begin{itemize}
    \item Meistens durchläuft der Prozess der Anfrageformulierung mehrere Iterationen, bis passende Antworten gefunden werden.
    \item Anfragen liefern potentiell sehr viele Antworten, aber nur wenige davon sind für den Nutzer interessant.
    \item Das vorgenannte Problem entschärft sich durch die vom System bereitgestellte Rangordnung der Antworten, wodurch potentiell relevante Antworten gehäuft am Anfang der Rangliste auftauchen (z.B. betrachten bei Internet-Suchmaschinen mehr als 90% aller Nutzer nur die ersten 10 Antworten)
    \end{itemize}
%---------------
\subsubsection{Was ist eine lernende Suchmaschine?}
Zur Definition des Gebietes legen wir hier die Beschreibung der
Aufgaben und Ziele. Eine lernende Suchmaschine ist eine Suchmaschine
mit künstlicher Intelligenz, die selbständig lernt, für wen etwas
interessant sein könnte, indem sie die Benutzer befragt.
%-------------
\subsubsection{Trainingsdaten}
Lernende Suchmaschine braucht Trainingsdaten, damit sie lernen kann.
Die Trainingsdaten können durch die Befrage der Besuchern
automatisch erzeugen. Sie werden durch eine Datengruppe
$Trio(q,r,c)$ dargestellt.
 \begin{itemize}
  \item $q$: Anfrage \\
  \item $r$: Die Rangliste der Suchergebnisse\\
  \item $c$: URL-Liste, die der Benutzer gewählt hat.\\
 \end{itemize}
Um die Definition von $Trio(q,r,c)$ besser zu verstehen, sehen wir
ein Beispiel mit Anfrage 'support vector machine'. Die Anfrage
'support vector machine' liefert 10 Antworten, aber nur $1,3,7$ sind
für den Nutzer interessant (siehe Abb.\ref{BildF1}).
\begin{figure}[h!]
    \centering
      \includegraphics[width=1\textwidth]{bilder_qingchui/F1.png}
    \caption{die Suchergebnisse mit der Anfrage 'support vector machine'}
    \label{BildF1}
\end{figure}\\
Bei dem Beispiel sind:
    \begin{itemize}
    \item q: 'support vector machine'
    \item r: Liste (1,2,3,4,5,6,7,8,9,10)
    \item c: (1,3,7)
    \end{itemize}
\subsubsection{Welche Informationen sind relevant?}
Was können die lernenden Suchmaschinen durch die Trainingsdaten
lernen. Bei dem Beispiel (Abb.\ref{BildF1}) hat der Benutzer $1,3,7$
gewählt. Es ist aber nicht sicher, dass $1,3,7$ absolut relevant
Sind. Aber man kann die relativ relevanten Dokumente bestimmen. Der
benutzter hat nach dem Rang2 den Rang3 gelesen. Ja, der Rang3 ist
wahrscheinlich relevanter als dem Rang2. man kann ihm mit einem
Relation $r^*$ darstellen link3 $<r^*$ link2. Analog kann man die
ganz Relation $r^*$ bei dem Beispiel (Abb.\ref{BildF1}) bestemmen:\\
\ \\
link3 $<r^*$ link2 \ \ \  link7 $<r^*$ link2\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ link7 $<r^*$ link4\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ link7 $<r^*$ link5\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ link7 $<r^*$
link6.\\
Die Relation $r^*$ hat also partielle Information der gesuchte
Sortierung der Suchergebnisse.
%---------------
\subsubsection{Darstellung der Relation $<r^*$}
Für eine Suchergebnisliste gibt es $m$ Dokumente
$D=\{d_1,\dots,d_m\}$. Die Relation $r^*$ kann man mit einer
Matrix $M$ darstellen.\\
($(M \subset D\times D)$)\\
($d_i <r^*\ \ d_j) \Longrightarrow (M_{ij}=1$ und $M_{ji}=0$)\\
Bei dem Beispiel (Abb.\ref{BildF1})\\
     $M$= $\left(
        \begin{smallmatrix}
          -& * & * & *& *& *&  * & *& *& *\\
          * & - & 1  &* &* &* & 1 & *&* & *\\
           *& 0 &  - &* &* &* &  * & *& *&* \\
           *& * &  * & -& *& *& 1 &* & *& *\\
          * & * & *  & *&- & *& 1 &* & *& *\\
          * & * & *  &* & *&- & 1 &* & *&* \\
          * & 0& *  &0&0&0& -  & *& *& *\\
           *& * & *  & *& *& *&  * &- & *& *\\
          * & * &  * &* &* & *&*   & *& -&* \\
          * & * & *  & *&* & *& *  &* & *&-
        \end{smallmatrix}\right)  $.\\
        (* unbekannt)
\subsubsection{Die Funktion für lernende Suchmaschinen}
Mit den Trainingsdaten müssen die lernenden Suchmaschinen eine
Funktion finden, damit die Dokumente gut sortiert werden können. Um
die Suchergebnisse zu verbessern, muss die Qualität der Funktion zu
beurteilen. In Statistik ist Kendall's $\tau$ sehr oft benutzt, um 2
Range zu vergleichen.\\
Für 2 Range $(r_a \subset D\times D)$ und $(r_b \subset D\times
D)$,\\
$P$ ist die Anzahl der übereinstimmenden Paare,\\
$Q$ ist die Anzahl der nicht übereinstimmenden Paare, ist dann
Kendall's $\tau$ definiert durch:\\
\begin{eqnarray}
\tau=\frac{P-Q}{P+Q}=1-\frac{2Q}{\left(_2^m\right)} \label{tau2} 
\end{eqnarray}
Um die Kendall's $\tau$ besser zu verstehen, sehen wir folgendes
Beispiel für 2 Rangen $r_a$ und $r_b$:\\
$r_a : d_1<$$r_a\ d_2 <$$r_a\ d_3 <$$r_a\ d_4 <$$r_a\ d_5$ \\
$r_b : d_3<$$r_b\ d_2 <$$r_b\ d_1 <$$r_b\ d_4 <$$r_b\ d_5$.\\
Die Anzahl der nicht übereinstimmenden Paare $Q$ ist 3 $(\{d_2,
d_3\}, \{d_1, d_2\}, \{d_1, d_3\})$.  Und die Anzahl der
übereinstimmenden Paare $P$ ist 7. Damit kann man $\tau$ durch die
Definition errechnen:
\begin{eqnarray}
\tau=\frac{P-Q}{P+Q}=\frac{7-3}{7+3}=0,4.
\end{eqnarray}
Wenn Q=0, hat $\tau$ die Maximum 1. Und umgekehrt hat $\tau$ die Minimum -1.  $r_{f(q)}$ ist das System mit der Frage $q$ liefert Rangliste. $\tau(r_{f(q)}, r*)$ ist dann die Qualität der Suchergebnisse mit einer Funktion $f$ nach die Anfrage $q$. Man kann die $\tau(r_{f(q)}, r*)$ als die Präzision der Suchergebnisse betrachten. Ist $\tau(r_{f(q)}, r*)$ groß, ist  die Präzision der Suchergebnisse dann groß.\\
Wir sind jetzt in einer Position das Problem der zu definieren. Das Ziel ist die Funktion für die zu erwartenden Kendall's $\tau$
\begin{eqnarray}
\tau_{p(f)}= \int \tau(r_{f(q)}, r^*)d_{Pr(q,r^*)}
\end{eqnarray}
für eine feste, aber unbekannte Verteilung $Pr(q,r^*)$ von Abfragen und Zielgruppen Rangliste auf ein Dokument Sammlung D mit m Dokumenten maximal. Während das Ziel der Lerner ist nun definiert, bleibt die Frage, ob es möglich ist, um die Funktion zu optimieren?

\subsubsection{Der  Algorithmus für lernende Suchmaschinen}
Die meiste Arbeit der lernenden Suchmaschinen im Information Retrieval
ist nicht die Formulierung von Dokumente, aber die vereinfachte Aufgabe, eine binäre Klassifikation Problem mit den beiden Klassen "relevante" und "nicht relevant". Eine solche Vereinfachung hat mehrere Nachteile.\\
Die "nicht relevanten" Dokumente haben eine starke Mehrheit. Ein Lernender muss eine Regel haben, um die Dokumente maximale automatische  genau zu klassifizieren. Aber es ist noch wichtig, und gezeigte, dass solche absoluten Relevanz Urteile nicht existiert ist, so dass ist sie einfach nicht verfügbar. Deshalb sollen wir einen Algorithmus finden.\\
Für identische $q$ und ihre $r^*$:
\begin{eqnarray}
(q_1,r_1^*),\cdots,(q_n,r_n^*)
\end{eqnarray}
wählt Lerner $L$ eine Funktion $f$, so dass 
\begin{eqnarray}
\tau_s(f)=\frac{1}{n}\sum_{i=1}^n\tau(r_{f(q_i)},r_i^*) \label{Zhu8} 
\end{eqnarray} 
 maximiert wird. Ist es möglich, einen Algorithmus und eine Familie von Rang Funktionen $F$ zu entwerfen, so dass eine Funktion $f \in F$ Maximierung effiziente gefunden wird, und diese Funktion weit über den Trainingsdaten verallgemeinert werden kann. Betrachten Sie die linearen Funktionen
\begin{eqnarray}
(d_i,d_j) \in f_{\bar{\omega}}(q) \Leftrightarrow \bar{\omega}\phi(q,d_i)>\bar{\omega}\phi(q,d_j). \label{Zhu9} 
\end{eqnarray}
$\omega$ ist ein Gewichtsvektor, und $\phi(q,d)$ ist ein Diagramm mit der Dimension, die die Eigenschaft
zwischen Anfrage q und Dokument d beschreibt.\\
\begin{figure}[h!]
\centering
\includegraphics[width=0.7\textwidth]{bilder_qingchui/F2.png}
\caption{}
    \label{BildF2}
\end{figure}
Mit unterschiedlichen Gewichtsvektoren $\omega$ werden die Dokument
unterschiedlich sortiert (siehe Abb.\ref{BildF2}). Jetzt haben wir sofort eine Frage, wie kann man die Dokumenten als Punkte auf einem Diagramm zeichnen? Das folgende Beispiel illustriert die Anwendung der Gewichtsvektoren bei Suchergebnissen.\\
\begin{table}[h!]
    \centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline
       $t_i$ &        $\omega_i$ &     $d_{1i}$ &     $d_{2i}$ &     $d_{3i}$ &     $d_{4i}$ \\
\hline
side effect &          2 &          1 &        0,5 &          1 &          1 \\

     drugs &          2 &          1 &          1 &          1 &          1 \\

    memory &          1 &          1 &            &          1 &            \\

cognitive ability &          1 &            &          1 &          1 &        0,5 \\

 not aging &         -2 &            &          1 &            &            \\
\hline
Retrivalgewicht &            &          5 &          2 &          6 &        4,5 \\
\hline
\end{tabular}
\end{table}
Beispiel-Frage: 'side effect of drugs on memory and cognitive abilities, not aging'\\
Entsprechend den Retrivalgewichten werden die Dokumente in der
Reihenfolge $d_3; d_1; d_4; d_2$ ausgegeben.\\
Die Maximierung (Formel \ref{Zhu8}) ist direkt äquivalent zu minimieren die Zahl der $Q$ der nicht übereinstimmenden Paare  in der Formel (\ref{tau2}). Für die Klasse der linearen Rangfunktionen (\ref{Zhu9}), dies ist äquivalent das Gewicht Vektor zu finden, so dass die maximale Anzahl der folgenden Ungleichungen erfüllt ist.\\
$\forall(d_i,d_j) \in r_i^*: \bar{\omega}\phi(q_1,d_i)>\bar{\omega}\phi(q_1,d_j)$\\
$\cdots$\\
$\forall(d_i,d_j) \in r_n^*: \bar{\omega}\phi(q_n,d_i)>\bar{\omega}\phi(q_n,d_j)$\\
Es ist leid NP-Schwer Problem. Aber genau wie bei der Klassifizierung SVMs ist es möglich durch die Einführung (nicht negativ) Schlupfvariablen $\xi_{i,j,k}$ und Minimierung $\sum \xi_{i,j,k}$ der zu Lösen.\\
\ \ \\
\emph{\textbf{(RANKING SVM)}}
\begin{eqnarray}
\textnormal{Min.} V(\bar{\omega},\bar{\xi})=\frac{1}{2}\bar{\omega}\cdot\bar{\omega}+C\sum\xi_{i,j,k}
\end{eqnarray}
\emph{\textbf{mit Nebenbedingung:}}
\begin{eqnarray}
\forall(d_i,d_j) \in r_i^*: \bar{\omega}\phi(q_1,d_i)\geq\bar{\omega}\phi(q_1,d_j)+1-\xi_{i,j,1} \label{Zhu13}\\
\cdots\\
\forall(d_i,d_j) \in r_n^*: \bar{\omega}\phi(q_n,d_i)\geq\bar{\omega}\phi(q_n,d_j)+1-\xi_{i,j,n}\\
\forall i,j,k: \xi_{i,j,k}\geq 0
\end{eqnarray}
C ist positiv Konstante, die den Ausgleich zwischen der Minimierung  von $\frac{1}{2}\bar{\omega}\cdot\bar{\omega}$ und der korrekten Klassifizierung der Trainingsbeispiele regelt. Durch die Neuordnung der Ungleichung (\ref{Zhu13}) als 
\begin{eqnarray}
\bar{\omega}\phi(q_1,d_i)-\bar{\omega}\phi(q_1,d_j)\geq 1-\xi_{i,j,1} \label{Zhu15}
\end{eqnarray} 
wird deutlich, dass die Optimierung Problem ist äquivalent
zu einer Klassifikation SVM auf paarweise Unterschied
Vektoren $\bar{\omega}\phi(q_1,d_i)-\bar{\omega}\phi(q_1,d_j)$. Es kann gezeigt werden, dass die erlernten Retrieval Funktion $f_{\bar{\omega}^*}$  immer als eine lineare Kombination der Vektoren kann.
\begin{eqnarray}
(d_i,d_j) \in  f_{\bar{\omega}^*}(q)\\
\Longleftrightarrow \bar{\omega}^*\phi(q,d_i)>\bar{\omega}^*\phi(q,d_j)\\
\Longleftrightarrow \sum\alpha_{k,l}^*\phi(q_k,d_l)\phi(q,d_i)>\sum\alpha_{k,l}^*\phi(q_k,d_l)\phi(q,d_j)
\end{eqnarray}
 Der Vektorraum und die zugehörigen Trainingsdaten sind durch eine Kernelfunktion $\sum\alpha_{k,l}^*\phi(q_k,d_l)\phi(q,d_i)$ in einen Raum mit so hoher Dimension zu überführen, dass sich die Trainingsdaten dort linear trennen lassen.
\subsubsection{Experiment}
Um in der Lage die Qualität der verschiedenen Retrieval Funktionen zu vergleichen, wird die Methode beschrieben in [T. Joachims 2002] verwendet. Die zentrale Idee ist es, zwei Rankings in der gleichen Zeit zu vergleichen. Man kombiniert zwei Rangliste $A$ und $B$ zu C. Es muss die folgende Bedingung gelten. Die oben $L$ Links der kombinierten Rang $C$ enthalten die oben $K_a$ Links von $A$ und der oben $K_b$ Links von $B$ mit $|K_a-K_b|\leq 1$. Mit anderen Worten, wenn der Benutzer die Links von C von oben nach unten scannt, hat er an einem beliebigen Punkt fast ebenso viele Links von der Spitze von A wie von der Spitze des B gesehen.\\
\begin{figure}[h!]
    \centering
     \includegraphics[width=1\textwidth]{bilder_qingchui/F3.png}
     \caption{}
    \label{BildF3}
\end{figure}
Ein Beispiel ist in Abb.\ref{BildF3}.  Die von zwei Retrieval Funktionen kombiniert Ergebnisse $C$ wird an den Benutzer. In diesem Beispiel hat der Benutzer auf den Links 1, 3 und 7 angeklickt. In dem Beispiel muss der Benutzer die oben 4 Links aus einzelnen Rankings gesehen haben, da er auf den Link 7 in der kombinierte Ranglist $C$ angeklickt hat. Er hat auf 3 Links in der oberen 4 im Ranking A (1, 2 und 4) angeklickt, sondern nur auf 1 Link in Rang B (1). Es ist deshalb zu dem Schluss, dass die oben 4 Links von $A$ besser als jene von $B$ für diese Anfrage sind.\\
Am Paper von Thorsten Joachims  \cite{Joachims/2002a} wird die lernende Funktion von SVM mit Google, MSNSearch und Toprank vergleicht. Die Ergebnisse siehe man im Tab.\ref{TABZhu3}.
\begin{table}[h!]
    \centering

\begin{tabular}{|c|c|c|c|}
\hline
Comparison & more clicks on learned & \multicolumn{ 2}{|c|}{less clicks on learned} \\
\hline
Learned vs. Google &         29 & \multicolumn{ 2}{|c|}{13} \\
\hline
Learned vs. MSNSearch &         18 & \multicolumn{ 2}{|c|}{4} \\
\hline
Learned vs. Toprank &         21 & \multicolumn{ 2}{|c|}{9} \\
\hline
                            \multicolumn{ 4}{r}{} \\
\hline
Comparison & tie(with clicks) &  no clicks &      total \\
\hline
Learned vs. Google &         27 &         19 &         88 \\
\hline
Learned vs. MSNSearch &          7 &         11 &         40 \\
\hline
Learned vs. Toprank &         11 &         11 &         52 \\
\hline
\end{tabular}
\caption{}
\label{TABZhu3}
\end{table}