
\documentclass[oribibl]{llncs}

\usepackage{ecltree}
\usepackage{epic}
\usepackage{fancybox}
\usepackage{epsfig}

\newcommand{\ps}[2]{\epsfxsize=#2\epsffile{#1}\epsfxsize=0pt}

\begin{document}

\title{Cooperative Information Retrieval Dialogues
	Through Clustering}

\author{Paulo Quaresma \and Irene Pimenta Rodrigues} 

\institute{
	Departamento de Inform\'atica, \\
	Universidade de \'Evora, \\
	7000 \'Evora, Portugal \\
	\{pq$|$ipr\}@di.uevora.pt
}
 
\maketitle

\begin{abstract}
In this paper we present some aspects of a
cooperative web information retrieval system in the law domain.
Our system is able to infer the user intentions and to keep
the context of the user interaction in order to supply suggestions for
further refinement of the user query.  One important aspect of our
system is its ability to compute clusters of documents associating a
keyword to each cluster. 
A detailed example of an interaction with the system is presented.
\end{abstract}

\section{Introduction}

In this paper we present some aspects of a cooperative
web information retrieval system with juridical documents
based on
SINO, a boolean text
search engine from the AustLII Institute \cite{GMK97}.

During an interaction when a user poses a query we want
that our system will be able:

\begin{itemize}

\item To infer what are the user intentions with the queries \cite{Loc98,QR98,QL95,Pol90}.

When a user asks for documents with a particular keyword, usually he
is interested in documents that may not have that keyword and he is
not interested in all documents with that keyword.

\item To supply pertinent answers or questions as a reply to a user question.

The system must supply some information on the set of documents
selected by the user query in order to help the user in the refinement
of his query.

\end{itemize}

In order to accomplish this goals we need:

\begin{itemize}
\item  To record the previous user interaction with the system 
(user questions and the system answers).

This record will play the role of a dialogue structure
\cite{CL99,RL93}. It provides the context of sentences (questions
and answers) \cite{CCC98}, allowing the system to solve some
discourse phenomena such as anaphoras and ellipses. Since our system
is multi-modal, other user acts such as button clicks and menu choices
are also represented in our dialogue structure.

\item To obtain new partitions (clusters labelled with a topical keyword) of
 the set of documents that the user selected with his query(ies).

\item To use domain knowledge whenever the system has it.

\end{itemize}

In our system each event (utterance) is represented by logic
programming facts that are used to dynamically update the previous
model. Using this approach it is possible to represent new events as
logic programs and to obtain the new states. Moreover it is possible
to reason about past events and to represent non-monotonic behaviour
rules.

Each utterance will trigger the inference of the user intentions
taking into account the user attitudes (such as his beliefs and the
user profile). The results of the inference of the user intentions
are:

\begin{itemize}
\item A new set of user and system beliefs and intentions 
(such as the intention of the user to be informed of something by the
system)

\item A new dialogue structure. This structure keeps the dialogue context 
allowing for the interpretation of user acts in its occurrence
context. The dialogue structure constraints the interpretation of user
intentions and it is built as a result of the intentions inference.
\end{itemize}
  
\section{Information Retrieval System}

During an interaction the user wants to look for some documents and
his queries are ways of selecting sets of documents. The system
questions and answers always intends to help the user in his search of
documents by supplying information on subsets of documents in the text
database.

After a user query the system may:

\begin{itemize}
\item Show the set of documents selected by the query.

\item Present a set of keywords that may help the user to refine his query.
In order to build a set of keywords the system may build groups of
documents (clusters) from the initial set selected by the user query
(with or without expanding).

\item Present a set of concepts that may help the user to refine his query.
In cases where the system as knowledge about some of the documents
subject it is possible to build groups of documents using that
knowledge, and to provide the user concepts for refining its query.

\item Explain the user why his query does not select any document, 
providing suggestions for other queries.

\end{itemize}

\subsection{An Interaction Example}

\paragraph{Dialogue 1}

Suppose that the user his a retired fireman that has saved a
child from drowning in a river during his holidays putting his life at
risk. Since he has caught a pneumonia as a consequence, he wants to
know if he can get a pension for relevant services to his country.

[User - Q1:]  Documents about pensions for relevant services?

[System - Q2:]  There are 243 documents, listed in the right frame. For 
further refinement you may choose one (or none) option in each column:


\begin{tabular}{|c|}
\hline
\emph{Pensions that were:}\\ 
given\\
or refused\\ \hline
\end{tabular}
\begin{tabular}{|c|}
\hline
 \emph{Pensions for:}\\
militaries\\
 or civilians \\ \hline
\end{tabular}

\begin{tabular}{|c|}
\hline
 \emph{Documents with
keyword:} \\ 
drowning \\ 
 or medal \\ 
or in duty \\ 
or $\dots $ \\ \hline
\end{tabular}

Options in column 1 and 2 are obtain using rules that model legal
knowledge on legislation on pensions for relevant services. Options on
column 3 are obtained by clustering the set of 243, using the method
described in section 4.
 
[User - Q3:]  chooses: civilians and drowning.

[System - Q4:]  There are 45 documents, listed in the right frame. For further refinement you may choose one (or none) option in each column:

\begin{tabular}{|c|}
\hline
\emph{Documents with keyword:} \\ 
death \\ 
or accident \\ 
or $\dots $ \\ \hline
\end{tabular}

Options in this column are obtain by reclustering the 45 documents.

[User - Q5:]  Documents where there was a drowning in a river.

[System - Q6:] Since there are 13 documents of the 45 above that match
the concept, I've listed them in the usual frame. For further
refinement you may choose one (or none) option in each column:


\begin{tabular}{|c|}
\hline
\emph{Documents with keyword:} \\ 
car crash \\ 
or bridge \\ 
or $\dots $ \\ \hline
\end{tabular}

[User - Q7:]  Where there was someone swimming?

[System - Q8:] Since there are no documents of the 13 above that match
your new constraint. I assume that you want that your query refines
Q3, i.e. you are looking for documents with the concept swimming, and
drowning and pensions for relevant services for civilians. Do you want
to see these documents?

[User - Q9:]  Yes.
.....

\section{Interaction Context}

The interaction structure
supplies the context for the user and system actions. This
representation structure takes into account that an utterance may:
specify the information contained in a set of previous utterances; or
to open a new context, when the user does not intend to continue
refining its query and desires to start a new one.

The Interaction structure (IS) is made of segments that group sets of
acts (user and system sentences).  The Interaction structure reflects
the user intentions; it is built taking into account the user and
system intentions. The Interaction segments have precise inheritance
rules defining how segments heritage their attributes from the
attributes of their multimodal actions.  

An example of the interrogation context for dialogue 1 is shown in fig. 1.

\begin{figure}[htb]
\centerline{\ps{fig1.ps}{5.0cm}}
\caption{Interrogation context after utterance Q7}
\end{figure}

\section{Intelligent Clustering}

Clustering is a complex process \cite{Sal89} since it involves: the choice
of a representation for the documents, a function for associating
documents (measures for similarity of documents with the query or
between them) and a method with an algorithm to build the
clusters. One of the best clustering methods is the Scatter/Gather
browsing paradigm \cite{CDRKT92,CKP93,HP96} that clusters documents into
topically-coherent groups. It is able to present descriptive textual
summaries that are built with topical terms that characterise the
clusters. The clustering and reclustering can be done on-the-fly, so
that different topics are seen depending on the subcollection
clustered.

\subsection{Clustering and reclustering}

Given a set of documents selected by a user query, a structure
associating a set of descriptors to each document (the document
classification) is built, structure 1, with a linear (O(n), n is the
number of texts) procedure. This structure is transformed in another
structure, structure 2, that associates to each descriptor in the
first structure a set of documents, with a procedure that has
complexity O(n*m), m is the number of descriptors in the structure.
These structures are shown in fig. 2.

\begin{figure}[htb]
\centerline{\ps{fig2.ps}{5.0cm}}
\caption{Document structure}
\end{figure}

Finally we must must choose a set of descriptors that:

\begin{enumerate}

\item The union of the set of documents associated to the descriptors is 
the initial set of documents.

\item The intersection of the set of documents associated to any two
descriptors is empty.

\end{enumerate}

These two conditions can not be satisfied always, when this is the
case, the first one is dropped.

However there are other proprieties the set of descriptors should have:
\begin{enumerate}
\item Its cardinality should be between 10 and 20.

\item The cardinality of each document set should be similar.

\item Descriptors with only one document associated should be
  ignored.
\end{enumerate}

Our search space, for m descriptors in structure 2, will have 2m
states that should be tested. Since it is not possible to search all
the state space in a reasonable time we have to use some heuristics in
order to cut off part of the search space, and we use an informed
search algorithm, a best first search with an evaluation function
specially designed for this problem.

This procedure will start by:

\begin{itemize}

\item Sort structure 2 by descendent order of the cardinality of the documents 
set.

\item To eliminate the descriptors with only one document associated.

\item To represent each set of documents in a bit table, to simplify the test for inclusion of document (it will became O(1)). 

\end{itemize}

Then the best first search will be guided by an evaluation function
that always choose to add a descriptor that as a set of documents with
its cardinal as near as possible of the interval [10, 20].

The search ends with success when:

\begin{itemize}
\item  All documents are selected, the union of the sets associated with the selected descriptors is the set of selected documents.

\item The cardinal of the set of descriptors  reaches 30, and the cardinal of the union of the sets of documents is  greater then 70\% of the initial number of documents.

\end{itemize}

Evaluations of this algorithm grants that it will take O(n*m), n is
the number of documents, m is the number of descriptors in structure
2 without those eliminated in the first step. For 10000 documents and
2000 descriptors it will take 100 milliseconds, a reasonable time for
a search in World Wide Web.

The reclustering can be done by modifying structure 2, taking out the
documents that are not selected in the refinement, and resorting this
structure. Normally reclustering is must faster the initial
clustering, since the input is smaller, and structure 2 is already
there.

\section{Conclusions and Future work}

We aim to build a cooperative IR system for juridical information.
In order to be cooperative, to help the user to
find a specific set of documents, our system needs to represent some
knowledge about the database documents. One important source of
knowledge is obtained by clustering sets of documents and labelling each
cluster with a topical term resulting from a document juridical
analysis.

By now the evaluation of our system has been performed by a set of
users, mainly law students, that think that the systems suggestions
are helpful for their searches.  We hope to use other evaluations
criteria that may quantify how helpful can the system suggestions be,
but by know we only have a quality evaluation.
 
\begin{thebibliography}{CDRKT92}

\bibitem[CCC98]{CCC98}
J.~Chu-Carroll and S.~Carberry.
\newblock Response generation in planning dialogues.
\newblock {\em Computational Linguistics}, 24(3), 1998.

\bibitem[CDRKT92]{CDRKT92}
D.~R. Cutting, J.~O.~Pedersen D.~R.~Karger, and J.~W. Tukey.
\newblock Scatter/gather: A cluster-based approach to browsing large document
  collections.
\newblock In {\em Proc. 15th Annual Int'l ACM SIGIR Conf. on R\&D in IR}, June
  1992.

\bibitem[CKP93]{CKP93}
D.~R. Cutting, D.~Karger, and J.~Pedersen.
\newblock Constant interaction-time scatter/gathern browsing of very large
  document collections.
\newblock In {\em Proc. of the 16th Annual Int. ACM/SIGIR Conf.}, Pittsburgh,
  PA, 1993.

\bibitem[CL99]{CL99}
Sandra Carberry and Lynn Lambert.
\newblock A process model for recognizing communicative acts and modeling
  negotiation subdialogs.
\newblock {\em Computational Linguistics}, 25(1), 1999.

\bibitem[GML97]{GMK97}
G.~Greenleaf, A.~Mowbray, and G.~King. Law.
\newblock On the net via austlii – 14m hypertext links can’t be right?
\newblock In {\em In Information Online and on Disk’97 Confrence}. Sydney,
  January, 1997.

\bibitem[HP96]{HP96}
M.~A. Hearst and J.~O. Pedersen.
\newblock Reexamining the cluster hypothesis:scatter/gather on retrieval
  results.
\newblock In {\em Proceedings of the Nineteenth Annual International ACM SIGIR
  Conference}, Zurich, June 1996.

\bibitem[Loc98]{Loc98}
Karen~E. Lochbaum.
\newblock A collaborative planning model of intentional structure.
\newblock {\em Computational Linguistics}, 24(4), 1998.

\bibitem[Pol90]{Pol90}
Martha Pollack.
\newblock Plans as complex mental attitudes.
\newblock In Philip Cohen, Jerry Morgan, and Martha Pollack, editors, {\em
  Intentions in Communications}. MIT Press Cambridge, 1990.

\bibitem[QL95]{QL95}
P.~Quaresma and J.~G. Lopes.
\newblock Unified logic programming approach to the abduction of plans and
  intentions in information-seeking dialogues.
\newblock {\em Journal of Logic Programming}, 54, 1995.

\bibitem[QR98]{QR98}
P.~Quaresma and I.~P. Rodrigues.
\newblock Keeping context in web interfaces to legal text databases.
\newblock In {\em Proc. of the 2nd French-American Conf. on AI\&LAW}, Nice,
  France, 1998.

\bibitem[RL93]{RL93}
I.~P. Rodrigues and J.~G. Lopes.
\newblock Building the text temporal structure.
\newblock In {\em Progress in Artificial Intelligence: 6th EPIA}.
  Springer-Verlag, 1993.

\bibitem[Sal89]{Sal89}
Gerard Salton.
\newblock {\em Automatic text processing: the transformation, analysis, and
  retrieval of information by computer}.
\newblock Addison-Wesley, 1989.
\newblock Reading, MA.

\end{thebibliography}

\end{document}

