=Paper=
{{Paper
|id=Vol-99/paper-8
|storemode=property
|title=Incremental Development of Browsing for Domain-Specific Document Retrieval Systems
|pdfUrl=https://ceur-ws.org/Vol-99/Mihye_Kim-et-al.pdf
|volume=Vol-99
|dblpUrl=https://dblp.org/rec/conf/kcap/KimC01
}}
==Incremental Development of Browsing for Domain-Specific Document Retrieval Systems==
https://ceur-ws.org/Vol-99/Mihye_Kim-et-al.pdf
Incremental Development of Browsing
for Domain-Specific Document Retrieval Systems
Mihye Kim and Paul Compton
School of Computer Science and Engineering
University of New South Wales
Sydney NSW 2052 Australia
+61 2 9385 6531
{mihyek, compton}@cse.unsw.edu.au
ABSTRACT setting up an appropriate query is a difficult process,
Browsing is being supported in many information retrieval especially for novice users and when the users do not know
systems to supplement Boolean querying. We have exactly what they want and how to get it.
implemented a web-based browsing mechanism for a The browsing approach is being supported in many
domain-specific document retrieval system based on the information retrieval systems to resolve this problem. The
concept lattice of Formal Concept Analysis. In this paper, obvious advantage of this method is that the users can
we have proposed and implemented an incremental quickly explore the search domains and can easily acquire
development of browsing by combing Formal Concept the domain knowledge (Marchionini and Shneiderman
Analysis (FCA) and Ripple Down Rules (RDR) as well as 1988). Typically, browsing is formulated in a hierarchy
incorporating a domain ontology. It allows a user to using some sort of clustering algorithm. Thus, the
formulate browsing in a more systematic and general way effectiveness of browsing depends deeply on how well the
for the domain by discovering relevant concepts when a used algorithm groups the relevant documents into the same
new document is added and an existing document is cluster. Hierarchical Agglomerative Clustering (HAC)
refined. The user can fairly easily add new documents and algorithms are probably the most commonly used clustering
annotate these so that they can be readily retrieved and also algorithms in information retrieval. However, this paradigm
distinguished from less relevant documents. The mechanism can cause the problem of category mismatch (Furnas et al.
incorporates an ontology for the documents which emerges 1983; Godin et al 1993) where a wrong decision can be
over time rather than having to be defined from the outset. critical in failing to find the right documents and contributes
A part of experimental evaluation of the system shows good to the low performance of the approach. This is because the
retrieval performance and a significant improvement after clustering only formulates relationships between parent and
the introduction of an incremental knowledge acquisition child cluster, but not other relationships between clusters in
mechanism. the different branches of the hierarchy.
Keywords To solve the problem a new browsing mechanism has been
Information retrieval system, document retrieval system, introduced based on the concept lattice of the Formal
browsing, incremental knowledge acquisition, formal Concept Analysis (FCA) (Godin et al. 1993; Carpineto and
concept analysis, ripple down rules Romano 1996; Priss 1997, 2000; Kim and Compton 2001).
INTRODUCTION Godin et al (1993) and, Carpineto and Romano (1996) have
In information retrieval processes, the degree of user addressed the advantage of the lattice method against the
interaction is typically twofold. In general, a user sends a hierarchical classification. The significant advantage of this
Boolean query to the system and the system returns a result. approach is that the mathematical formulas of FCA can
Then the user can refine or reformulate the query construct the conceptual structure which has generalisation
corresponding to the result until he/she is satisfied with the and specialisation relationships among the concept nodes.
result. In a second style of interaction, the user simply This lattice structure allows one to reach a concept node via
navigates a hierarchical classification scheme or subject one path, but then rather than going back up the same
categories displayed by the system using hyperlinks menus hierarchy and guessing another starting point, one can go to
or some direct representation of the hierarchy. one of the other parents of the present node.
The method of direct query formulation is most useful when The effectiveness of browsing also depends on whether the
the user knows what she/he is looking for and has some relationships between the clusters are constructed in a
background knowledge of the search domain. However, systematic and general way. Hence, most of the clustering
incorporates the use of subject categories or thesauri, rather
than only using the document information itself. It is quite important concepts for the cases as well as discover the
natural that the hierarchy can be structured more domain ontology from the situated cognition view. It has
systematically when domain terms are involved. been facilitated by combining the FCA browsing and RDR
For the same reason, information retrieval based on FCA knowledge acquisition techniques.
often incorporates the use of thesauri or classification for 2. Discovery of a domain ontology
the domains (Carpineto and Romano 1996; Cole and Here, an ontology can be a thesaurus or a taxonomical
Eklund 1996; Stumme 1999; Priss 2000; Kim and ontology for the domain1. Typically, thesauri are used for
Compton), even though the formulas of FCA construct indexing (browsing) to select the most appropriate thesaural
generalised and specialised relationships in the lattice. entries for representing the document. They are also used
Carpineto and Romano (1996) used a thesaurus as for background knowledge to expand the users’ query to
background knowledge to formulate browsing and enhance the retrieval process. In general, ontologies for the
presented experimental evidence that adding a thesaurus to domain are established prior to developing information
a concept lattice improves its retrieval performance. Others retrieval systems.
(Cole and Eklund 1996; Stumme 1999; Priss 2000) also use
a domain thesaurus for their retrieval processes. In this approach, we can anticipate that there will be the
typical problems of software engineering methodologies in
Following this paradigm, we have been implemented a web- building and maintaining the ontologies, even though the
based browsing mechanism for a domain-specific document approach has certain benefits. Moreover, new cases
retrieval system (Kim and Compton 2000, 2001). We have (documents) are added into the system in continually and
demonstrated the system with a test domain (URL: http:// the domain knowledge is in a dynamically changing
pokey.cse.unsw.edu.au/servlets/Search). The key difference environment. Hence, in our view the ontologies should be
in our approach was that we focused on developing a web- discovered from the domain knowledge as documents are
based user interface which can be very natural for Web added, or when documents fail to be retrieved, by the
users. Thus, we simplify the lattice display by showing only domain experts adding concepts rather than simply using a
direct neighbours in the lattice using Hyperlinks, rather than predefined ontology. Of course, in the pre-defined
focusing on visualising the lattice graph itself. We also approach, the ontology can be refined, but the maintenance
integrated the browsing with a standard query interface. of ontology is still ongoing research (Benjamins et al.
However, through our experiments and implementation, we 1999). An interesting fact is that none of the thesaurus or
have identified three key requirements for domain-specific classification schemes is the same for the same domain.
information retrieval systems. From this fact we can anticipate that the situated cognition
1. Incremental knowledge acquisition view of knowledge acquisition also applies to building an
ontology, with more emphasis on the significance of
It is essential to be able to incrementally construct a context.
concept lattice by adding a new document and refining the
existing information in the system. The set of documents The incremental concept formation called learning from
can be added in a batch, but it is more likely that documents observation is also a fundamental process of human
will be added individually. Thus, Godin et al (1995), learning since the concepts to learn are not pre determined
Carpineto and Romano (1996), and Kim and Compton by an expert and the instances are not pre-classified with
(2001) proposed incremental algorithms for updating the respect to these concepts.
concept lattice. All these approaches simply reconstruct the In the involvement of thesauri or ontologies, a more critical
lattice incrementally to cover the new case with the given situation is as follows: In building an ontology, the
keyword set. relationship between terms are defined with an equivalent
However, none of studies has been done in regard to (synonym) relationship, part-of and part-whole (non-
incremental knowledge acquisition. When an expert assigns hierarchical) relationship, is-a (hierarchical) relationship
the set of keywords for a document, some concepts may not and so on. Here, we will only look at this problem in the
be made up in just the context of the input case but also can hierarchy. Let C = (D, K, I) be a formal context as in
be prompted in regard to the stored cases. The expert also Definition 1 in the following section. We start from the
tends to ignore the most general concepts (keywords) of the subsumption hierarchy of an ontology with a partially
domain, even if they (or authors) are the most appropriate ordered set (K, ≤) and a context (D, K, I). D is a set of
agents to assign meaningful concepts for the documents. documents which are collected from the set D and K is the
Thus, it is necessary to have certain knowledge acquisition
mechanisms to be able to extract the concepts which are 1
We use the term ‘ontology’, ‘taxonomical ontology’, and
missed or unknown when concepts are assigned, enabling ‘thesaurus’ interchangeably, even these have a slightly
experts to constantly improve the system’s retrieval. different definition. But we prefer to use the term
Thus, we have proposed and developed an incremental ‘ontology’, even though there is a tendency to have a
knowledge acquisition mechanism to extract some meaning of ‘taxonomical ontology’ and '
thesaurus'
.
set of terms in the ontology. When a thesaurus is involved mechanism. Finally we will outline future directions for this
in an information retrieval process, the following work.
compatibility condition is assumed for a subsumption
METHODS
hierarchy (Carpineto and Romano 1996; Cole and Eklund
One of the very complex tasks in AI is known as knowledge
1996; Stumme 1999)
acquisition accompanied by the knowledge acquisition
∀d ∈ D, k, i ∈ K: (d, k) ∈ I, k ≤ i ⇒ (d, i) ∈ I 2 bottleneck. To improve the bottleneck problem, a new
However, the compatibility condition is not always modern approach (Richard and Compton 1998; Tecuci
transitive or inheritable for the instances in ontologies, even 1998) emerged with an emphasis on the situated cognition
the terms themselves (k, i ∈ K) have is-a relations in the view to incremental construction of knowledge in the
context of its use, rather than transfer of knowledge. RDR
hierarchy. For example, we suppose there is a document d
uses these approaches and attempts to address incremental
∈ D and two terms (Web servers, Java) ∈ K with the
knowledge acquisition from a situated cognition perspective
relationship of ‘Java < Web servers’ from Figure 4 and
(Compton and Jansen 1990).
suppose the document d is associated with the term ‘Java”
((d, Java) ∈ I). But the document d may be in connection FCA is used for a knowledge acquisition process (Wille
with the term ‘Web servers’ or may not ((d, Web servers) ∈ 1992; Erdmann 1998; Stumme 1998) to discover concepts
and rules related to the objects and their attributes. This
I) or ((d, Web servers) ∉ I)).
approach is based on a strong idea of context with its use of
Again, the ontologies should be discovered from the parent child-relations between concepts.
domain knowledge in connection with adding a new case
However, the general principle is still to give the expert a
and refining stored cases. We propose an approach to solve
view of the whole domain so that all relevant concepts will
this problem by combining the knowledge acquisition
be included. Despite that, we have argued that experts
process for the documents. We also provide a tool for
more easily provide concepts that distinguish between cases
experts to develop a domain ontology to cover the stored
(Compton and Jansen 1990). The expert’s attention is
documents of the knowledge base by re-using keywords if
focussed on relevant cases by the system misapplying a
required.
concept to a case. The expert is then asked to distinguish
3. More generalised browsing structure between this case and a case the system retrieves where the
We already mentioned that effectiveness of browsing concept was appropriate. This is a more strongly situated
depends closely on how well the relationships between the view of knowledge acquisition with more emphasis on the
clusters are constructed in the hierarchy in a more general significance of context. Thus, we tried to accomplish the
and specific way. Hence, most of the clustering knowledge acquisition process from the FCA features based
incorporates the use of classification schemes or thesauri. on the basic philosophy of RDR. By combining the RDR
We have observed that our knowledge acquisition and FCA techniques the expert is able to achieve
mechanism allows the construction of a more generalised incremental maintenance of the system’s knowledge
and structured browsing scheme improving its retrieval improving the quality of the retrieval over time.
performance. Such a browsing structure can also represent Ripple Down Rules (RDR)
the domain ontology in the longer term. RDR is an effective knowledge acquisition and
We have implemented a browsing mechanism and an maintenance methodology which allows a domain expert to
incremental knowledge acquisition mechanism for a build and maintain knowledge based systems very simply
domain-specific document retrieval system on the Web with and to acquire domain knowledge easily and quickly. The
a test domain of papers at the Banff Knowledge Acquisition approach was initially developed in dealing with the
Workshops in recent years (URL: http://pokey.cse.unsw. problems found in the maintenance of the medical expert
edu.au/servlets/Search). We have also observed that the system GARVAN-ESI (Compton et al. 1989). The main
system allows enabling experts to constantly improve the observation in this study was that experts never gave a
system' s retrieval. In this paper, we focus on explaining the comprehensive explanation of why one conclusion should
incremental knowledge acquisition mechanism we have be given rather than another. Rather they are good at
developed, rather than demonstrating the system. creating justifications for their decision in the context.
In the next section, we will explain methods we have used. Taking this experience to address knowledge acquisition
Then we will present the incremental knowledge acquisition from a situated view of the nature of knowledge, the
development of RDR was started (Compton and Jansen
1990).
In the RDR method, the expert is only required to identify
2
Gerd Stumme describes this problem in the paper features that differentiate between a new case being added
(Stumme 1999). We explain the problem following the and the other stored cases already correctly handled. That is
notion of the paper. the main technique of knowledge acquisition in RDR which
is very similar to the use of differences in personal is a binary relation which indicates where a document d has
construct psychology (Gains and Shaw 1990). A rule is a keyword k by the relationship dIk (also by (d, k) ∈ I).
only added to the system when a case has been given a
For example, Figure 1 shows the formal context of C where
wrong conclusion. Any cases that have prompted
D is {1, 2, 3, 4}, Κ is {artificial intelligence, expert
knowledge acquisition are stored along with the knowledge
systems, information retrieval, machine learning, decision
base. RDR does not allow the expert to add any rules
tree, natural language processing, discourse analysis,
which would result in any of these stored cases being given
speech recognition, signal representation} and the relation I
different conclusions from those stored. It means that the
is {(1, artificial intelligence), (1, information retrieval),...,
existing rules’ consistency is kept in RDR and that there is
(4, natural language process), (4,speech recognition), (4,
incremental improvement in the system.
signal representation)}.
It has been applied to a range of tasks: multiple
Representation
classification, control, knowledge reuse, heuristic search,
Recognition
Information
Intelligence
Processing
Retrieval
Language
Artificial
Learning
Decision
Machine
Speech
Signal
configuration and information retrieval. There are a number
Natural
Tree
of other lines of RDR research integrating RDR with
machine learning and fuzzy reasoning.
Formal Concept Analysis (FCA)
1 X X
FCA is a data analysis method for explicitly investigating
2 X X X
and processing given information based on a mathematical
3 X X X
theory (Wille 1982; Ganter and Wille 1998). It has been 4 X X X X
applied to a variety of areas for data analysis, information
retrieval, knowledge acquisition and knowledge discovery Figure 1. Part of formal context in our application.
in databases. The following derivation is used to cultivate formal
The extension of a concept is formed by all objects to concepts of a formal context. A formal concept is defined
which the concept applies and the intension consists of all as a pair (X, Y) such that X ⊆ D, Y ⊆ Κ, X'= Y and Y'=
attributes existing in those objects. All formal concepts are X where X and Y are called the extend and the intend of
found using given mathematic formulas. Then the the concept (X, Y).
subconcept-superconcept relationships between formal X ⊆ D : X |→ X ′ := {k ∈ | ∀d ∈ X : (d , k ) ∈ I}
concepts are expressed in a concept lattice. The concept
Y ⊆ : Y |→ Y ′ := {d ∈ D | ∀k ∈ Y : (d, k ) ∈ I}
lattice can be seen as a semantic net providing "hierarchical
conceptual clustering of the objects… and a representation Concept Lattice
of all implications between the attributes" (Wille 1992). The formal concepts of C are expressed in a concept lattice
More detailed definitions and examples can be found in which is the basic conceptual structure of FCA and ordered
(Ganter and Wille 1999). Here, we briefly explain it by by the smallest set of attributes as shown in Figure 2.
applying it to our system.
Artificial intelligence
Formal Contexts and Formal Concepts
/ {1, 2, 3, 4}
The most basic data structure of FCA is a formal context.
The set of objects and their attributes constitute a formal
context (Κ) = (G, M, I). G is a set of objects, M is a set of Artificial intelligence Artificial intelligence Artificial intelligence
attributes and I is a binary relation between G and M Machine learning Information retrieval Natural language -
which indicates where an object g has an attribute m by Decision tree / {2} / {1, 3} processing / {3, 4}
the relationship gIm (also by (g, m) ∈ I).
In our application we suppose that documents correspond Artificial intelligence Artificial intelligence
to objects and the keywords of the documents constitute Information retrieval Natural language -
attribute sets. Then we define a formal context (C) as Natural language- processing,
follows in our document retrieval system: processing / {3} Speech recognition
Signal representation /{4}
Definition 13: A formal context is a triple C = (D, Κ, I)
where D is a set of documents, Κ is a set of keywords and I
{All set of keywords}
/ {}
3
This definition follows the Basic Theorem of FCA
(Ganter and Wille 1999). The notion of a formal concept Figure 2. Concept lattice of the formal context in Figure1.
and concept lattice described in this paper also follow
Basic Theorem of FCA.
To build a concept lattice we need to find the subconcept- Definition 5: We define a function Freq from 2K × Κ to the
superconcept relationship between the formal concepts. set of natural numbers 1 as follows: Freq: 2K × Κ È 1
This is formalised by such that Freq (Γ, k) = ∑ | ƒ (d ) ∩ Γ | where |X| is the
d ∈∆k
(X 1, Y1 ) ≤ (X 2, Y2 ) ⇔ X 1 ⊆ X 2 ( ⇔ Y2 ⊆ Y1 ) cardinality of X.
Where (X 1, Y1 ) is called a subconcept of (X 2, Y2 ) Table 1: Knowledge acquisition: adding a document
(X 2, Y2 ) is called a superconcept of (X 1, Y1 ) Begin
Input a new case (document d with a set of keywords Γ)
INCREMENTAL KNOWLEDGE ACQUISITION Step1 (knowledge acquisition based on
The knowledge acquisition for the system is achieved by the lattice structure)
adding new cases and refining the existing cases. Another Step2 (knowledge acquisition based on the ontology)
way of knowledge acquisition is carried out in connection Step3 (knowledge acquisition based on
with an ontology when a new case or a new class of the the RDR techniques)
ontology is added. In our system, a case consists of a Add the new case into the knowledge base
document, a set of keywords and other information such as Reconstruct the concept lattice incrementally to cover
authors, publication year, proceeding title and so on. - the new case
End
When a New Document is Added
Through the given user interface, the expert/user can add a
new case and refine the stored cases. Table 1 shows the In the first step, an ordered set of documents and a set of
knowledge acquisition mechanism when a new document is keywords which are relevant to the new document are
added to the system. The formalised definitions are used in obtained. This step is divided into two stages. In the first
the mechanism, which is explained in detail in the following stage, the ordered documents are shown to the user along
example. with the different features between the new document and
each of the set of documents. In the next stage, the
Definition 2: Let C = (D, Κ, Ι) be a formal context, and d frequency of each of relevant keywords is computed. Then,
be a new document (d ∉D) and Γ be the set of keywords of the ordered relevant keywords are presented to the user
d. The set of keywords is not necessarily a subset of Κ. with their frequency.
Then, the extended formal context of C is defined as C+ = To process this step, a sub-lattice £(D′, K′, I′) of the formal
(D+, Κ+, I+) where D+ = D ∪ {d}, Κ+ = Κ ∪ Γ and I+ = I ∪
context C′ is constructed. The similarity relation between
{(d, k) | k ∈ Γ}. concepts can be easily observed through the lattice. Given a
Definition 3: Let C = (D, Κ, Ι) be a formal context and Γ new document d, we are interested in finding the set of
be a set of keywords (Γ ⊆ Κ). Then the set of documents documents Dd that share some commonalties. We formulate
associated with Γ is defined to be ∆Γ = {d ∈ D | ∃k ∈ Γ a formal concept ζ ({d}, Γ) with the newly added document
such that (d, k) ∈ Ι}. d and its set of keywords Γ. Informally, starting from the
concept ζ we recursively go up to the direct superconcepts
We introduced ∆Γ to get a set of documents which has at
of its subconcept in the lattice to find the next level of the
least one keyword of Γ. If Γ is a singleton (i.e. Γ= {γ}), relevant documents. This procedure is done until the
then we will abbreviate ∆γ ∆Γ = {d ∈ D | (d, γ) ∈ Ι}. superconcept reaches the top node of the lattice.
Definition 4: Let C = (D, Κ, Ι) be a formal context. We For example, we suppose that there is a concept lattice as
define a function ƒ from D to 2K as ƒ: DÈ 2K such that ƒ shown in Figure 2 and, a new document d (5) is added
(d) = {k ∈ Κ | (d, k) ∈ Ι}. together with and its set of keywords Γ {natural language
That is, ƒ (d) returns the set of keywords of d. Let the new processing, speech recognition, verbal interference}. Then,
document be d (∉D) with the set of keywords Γ. We we formulate the sub-context C′ = (D′, K′, I′) where D′ = ∆Γ
+ {d} = {3, 4, 5}, K′ = U f (d ) = {artificial intelligence,
formulate the sub-formal context C′ = (D′, K′, I′) with D′= d ∈D′
information retrieval, natural language processing, speech
∆Γ + {d} where ∆Γ is in definition 3 andK′ = U f (d ) where
∈D ′ recognition, signal representation, verbal interference} and
ƒ is the function in definition 4. In order dto get a set of I′ is a binary relation between D′ and K′. The sub-lattice
relevant keywords of d, we obtain a set of keywords which
£(D′, K′, I′) of the context C′ can be constructed as shown
are associated with ∆Γ as ƒ(∆Γ) = U f (d ) from the context
d ∈∆ r in Figure 3. The gray coloured box indicates the formal
C′. Now the set of relevant keywords is defined as ℜ = concept ζ. From the lattice we can get the document ’4’ at
ƒ(∆Γ) - Γ. Then, the function Freq introduced below is used first. Because it exists in the direct superconcept of ζ in the
for each keyword of ℜ (k) to compute the number of lattice which indicates the most relevant of the document
common keywords of Γ with the keywords of all the ’5’. Next the document ’3’ is obtained. Finally, we get an
documents that have the keyword k from the context C′. ordered set of documents {4, 3} by the relevancy of the
document ’5’ in the lattice. The ordered documents are then The next step of knowledge acquisition is based on an
suggested to the user along with the different features ontology. This mechanism will be explained in detail in the
between the new document and each of the relevant following section.
documents. At this stage the user can look at the lattice In the final stage of knowledge acquisition when a new
structure itself using browsing mechanisms supported by document is added, we use the RDR techniques using a flat
the system. The result obtained by this process is equivalent RDR rule tree. In the RDR approach, when a new rule is
to k-nearest neighbour algorithms. added, all stored cases that can be reached by the parent
At the next stage, we elicit the relevant keywords from rule (=cornerstone cases) are retrieved. Then the expert is
which are associated with the newly added document d. required to construct a rule which distinguishes between the
Then, a frequency for each relevant keyword is calculated new case and the cornerstone cases until it excludes all
by definition 5. Following this, the keywords are ordered by cornerstone cases. In our document retrieval system, a case
their frequency and the system suggests the keywords to the which has the same set of keywords of the new document,
user with their frequency. After that, the system asks the becomes a cornerstone case of the new case. If a
user the relevancy for each extracted keyword and the user cornerstone case exists, the system elicits a relevant
can simply answer by clicking the check box located in the keyword set of the new case in the same way used in the
front of each keyword. For example, let a new document d step1 of Table 1. Then, the extracted relevant keywords
be ’5’ and the set of keywords (Γ) of d be {natural language become available to the expert. The expert has to select at
processing, speech recognition, verbal interference}. Then, least one different feature (keyword) from the deployed
we can get a set of documents associated with Γ (∆Γ) ={3, keywords or specify a new word to distinguish the
4} by definition 3 from the sub-context C′ = (D′, K′, I′) cornerstone case and the new case. Another cornerstone
shown in figure 3. After that, the set of keywords which are case can be prompted by new added keywords. Thus, this
associated with ∆Γ is obtained: that of ƒ(∆Γ) = {artificial process is continued until there is no cornerstone case.
intelligence, information retrieval, natural language When a New Class is added in the Ontology
processing, speech recognition, signal representation} by We support a tool to develop a domain ontology to cover
definition 4. Finally we define the set of relevant keywords the stored documents of the knowledge base. Here the
as ℜ = ƒ(∆Γ) - Γ = {artificial intelligence, information ontology can be a set of hierarchies of terms where a term is
retrieval, signal representation}. Because the set of either a single word or a phrase along with the relationship
keywords in ℜ are candidates of expanding the keywords between terms. Figure 4 shows a possible example in our
already associated with d. Then, for each element of ℜ, a document retrieval system. The structure of the ontology is
frequency is calculated by definition 5 as follows: Freq(Γ, also a lattice (graph), even if it presents in a hierarchy. It
means the number of entries for each term exists in the
artificial intelligence)=3, Freq(Γ, information retrieval)=1
structure and a term can have multi parents. For the
and Freq(Γ, signal representation)=1. Through this process,
convenience of explanation, we use the term ' class'and
experts can capture some relevant concepts (here, the
'attribute'to describe a concept node in the ontology. For
keyword ‘artificial intelligence’ or may others) in adding a
example, the term ' Internet'is a class with a set of attributes
new document.
{Web browser, Web servers} in Figure 4. ' Web servers'is
{Natural language processing} also a class with an attribute set {Apache, Java}. It means
/ {3, 4, 5} an attribute of a class can be a class of another set of
attributes. As we already mentioned in the introduction, we
developed a mechanism to discover new concepts when a
Artificial intelligence Natural language processing new case is added by connecting to the process that is to be
Natural language processing Speech recognition
able to hold the compatibility condition in the ontological
/ {3, 4} / {4, 5}
hierarchy.
Artificial intelligence Artificial intelligence Natural language – Internet Programming
Natural language- Natural language - processing Language
processing processing, Speech recognition
Information retrieval Speech recognition Verbal interference
/ {3} Signal representation / {5}
/ {4} Web browser Web servers
Apach Java C++ Visual Basic
{All set of keywords}
e
/ {}
JigSaw Soma
Figure 3. Lattice £(D′, K′, I′) of the formal context C′
from the Figure 2. Figure 4. Part of a hierarchy of a possible ontology.
At any stage the expert/user can set up or change the Validate the values of the classes for each class path
hierarchy. Table 2 shows the algorithm of knowledge If validation is ok then
acquisition incorporating the ontology when a new Rebuild the set Γ by adding the classes which are set
document is added. When a document d with a set of '
true';
keywords (Γ) is added, the system gets all class paths which Else
the set Γ belongs to. For each class of each class-path if the Ask the class value which is not valid again
document includes the class, a class is set to a value ‘true’ End if
for the document, otherwise to the default value ‘unknown’. Modify the knowledge base
For each class whose value is 'unknown'the system asks the End
user about inheritance between the class and the associated Table 3: Algorithm of adding a class in ontology
keyword. Then the user should answer with one of the Begin
values; 'true', '
false'or 'unknown' . After that, the system Input a class with a set of attributes
validates the assigned values of the classes for each path as Get a set of documents that is associated with at least
follows: Let G = (V, E) be the directed graph representing - one of the attributes;
the ontology and T be the set of all class paths found. Then, For each document do
T is valid if and only if there does not exist any pair of If the class name exist in the keyword of
nodes u, v ∈ V such that for each path of T(v1, …, vn) in G the document then
the following conditions hold: Set the value of the class Ç ' true'
Else
(i ) v1 = u and vn = v Set the value of the classÇ ' unknown'
(ii ) n > 2 End if
(iii ) v1 = ’true’ and vn = ’true’ End for
(iv) there exists i such that 1 < i < n and (vi = ’false’or ’unknown’) For {the whole set of documents}
- {the set of documents} do
The problem with this is not the removal of a class node in Set the value of the class Ç ' false'
the hierarchy, but a new class (a concept node). It is End for
probably tool costly to go through every case where the End
new node may apply. Thus, we just set the value of class
with 'unknown'in all cases where the change in hierarchy
Experimental Evaluation of Retrieval
says it might apply. Table 3 shows the algorithm of adding In our experiment, we evaluated how the retrieval
a new class node in ontology. Then, in any given browsing effectiveness of browsing can shift when the compatibility
the user can choose to temporarily assign ' unknown'to condition is held in the ontological hierarchy. Other
either 'true'or '
false'
. In other words, when the user browses incremental knowledge acquisition factors developed still
the nested attributes, the system shows menu items with remain to be empirically evaluated.
‘true’, 'false'and ‘unknown’ for each attribute of the class. The experiments were carried out on a collection of
When the user looks at the document which belongs to the documents, which belongs to the domain of the knowledge
‘unknown’ menu item, the system will ask the inheritance of acquisition area. The collection consists of 200 documents
the class in regard to the document with ‘true’, ' false'or and its taxonomical ontology. Then, we reformulated the
‘unknown’. The knowledge base will then be changed ontology into three different hierarchies which have the
according to the user’s selection. average number of entries for each thesaural term with 1.12,
Table 2: Algorithm of step 2 in Table1 1.23 and 1.35 respectively by adding and pruning each
Begin term' s parents. Next, we constructed three different
Get all class path (T) that the set Γ belong to ontologies which hold the compatibility condition with the
For each class path do percentage of ' unknown' value 80%, 50% and 10%
For each class in the path do respectively for each reformulated ontology. It has been
If the new document d includes the class name then conducted by relevance judgements manually. We also built
Set the value of the class with ' true'for d a set of 40 queries which are related to the ontological
Else terms by conjunctive and disjunctive keywords. For each
Set the class value with the default ‘unknown’; query, relevance decisions with documents were also given
Ask inheritance between the class and the in advance. Someone may argue with the size of the
associated keyword to the user; documents. But we believe the size is quite enough for the
(with the value of 'true', ‘false’ and '
unknown'
) test to be considered significant for our approach. Currently
End if we are evaluating a quite large set of documents obtained
End for from INSPEC. The documents consist of a title, an abstract
End for and a set of keywords with an average of 6.15. Table 4
Until validation is ok shows the results of our experiment.
Average number of entries for each term
1.12 1.23 1.35
Recall Precision Recall Precision Recall Precision
Case 1: Retrieval without an ontology 0.71 0.78 0.71 0.78 0.71 0.78
Case 2: Retrieval with an ontology 0.80 0.76 0.81 0.71 0.82 0.66
Case 3: Retrieval with an ontology 80% 0.73 0.80 0.74 0.80 0.73 0.79
which holds the compatibility condition 50% 0.76 0.82 0.75 0.83 0.75 0.82
(percentage of ’unknown’ value) 10% 0.79 0.85 0.81 0.84 0.81 0.85
Table 4. Average values of retrieval performance in recall and precision.
Clearly, the findings indicate that the effectiveness of performance and a significant improvement after the
retrieval both in recall and precision has improved when the introduction of an incremental knowledge acquisition
ontology, which holds the compatibility condition, mechanism.
incorporates the retrieval against Case 1. The retrieval Although FCA and RDR seem an attractive solution to
performance is improved when the ’unknown’ values of incrementally develop a browsing mechanism for a
terms are revealed. That is, the quality of the retrieval is specialised domain, we have not yet fully evaluated this
improved by incremental maintenance of the system’s approach and not yet carried out knowledge acquisition in a
knowledge over time. In the comparison with Case 2 and timely manner based on the proposed mechanism. We need
Case 3 in Table 4, the results show Case 3 has a better to evaluate this approach in routine use with reasonably
performance in precision, but a lower effectiveness in large data sets. At a more fundamental level, the value of
recall. However, we already pointed out that the FCA for IR is based on the assumption that when you enter
incremental maintenance of the system increases the a keyword, and the documents retrieved are inappropriate,
performance in recall. The results also reveal that the then these documents will have other keywords that will
retrieval performance is proportional to the average number eventually lead you to the desired documents. This is a
of ontological entries for each term in Case 2. It means that central but hidden assumption in proposing that a lattice-
the precision of retrieval is getting worse, even though the browsing scheme will have advantages over a hierarchical
recall is improved. In other words, the bigger the average approach. In a hierarchical scheme you simply go back to
number of entries for each term becomes, the more the top and start again. With a lattice approach you assume
irrelevant documents will be. that there are other features of the retrieved document that
SUMMARY will also occur in the documents you really want to retrieve.
In previous work (Kim and Compton 2000, 2001), we have This is a central and critical assumption that needs to be
demonstrated a browsing mechanism that enables the user explored further.
to more easily explore documents appropriate to specialised In summary, we have not yet fully developed and evaluated
domains and based on the involvement of experts in this form of expert-centred information retrieval. However,
assigning concepts to documents. We observed that experts this prototype at least suggests the possibility of a new way
can examine the relationships of the concepts in the lattice of information retrieval associated with browsing where an
along with the existing document to decide whether the expert can rapidly build and maintain an information
keywords used are appropriate and they can refine concepts retrieval system in his or her area of expertise which will be
of the document. We see the method as applying only to easy for domain users. We believe that these highly
fairly small sets of keywords attached to documents by specialised, ’disposable’ systems will be critical in making
experts. In this paper, we have proposed and implemented full use of the enormous amounts of knowledge appearing
an incremental development of browsing by combining the in Intranets and the Internet itself.
FCA and RDR techniques as well as incorporating a
domain ontology. It allows the user to formulate browsing ACKNOWLEDGMENTS
in a more systematic and general way for the domain by The authors would like to thank Bao Vo and Dr. Rex B. H.
discovering relevant concepts when a new document is Kwok for helping in formalising of mathematical formulas
added and an existing document is refined. The user fairly used in definitions.
easily adds new documents and annotates these so that they REFERENCES
can be readily retrieved and also distinguished from less 1. Benjamins, V. R., Fensel, D., Decker, S. and Perez, A.
relevant documents. The mechanism incorporates an G. (KA)²: building ontologies for the Internet: a mid-
ontology for the documents to emerge over time rather than term report. International journal of human computer
having to be defined from the outset. A part of studies, Vol. 51, No. 3, 687-712, 1999.
experimental evaluation of the system shows good retrieval
2. Carpineto, C. and Romano, G. A Lattice Conceptual 14. Kim, M. and Compton, P. A Web-based Browsing
Clustering System and Its Application to Browsing Mechanism Based on Conceptual Structure. will be
Retrieval. Machine Learning, 24(2), 95-122, 1996. appeared in Proceedings of 9th International
3. Cole, R. and Eklund, P. Application of Formal Concept Conference on Conceptual Structures (ICCS’01), 2001.
Analysis to Information Retrieval using a Hierarchically 15. Marchionini, G. and Shneiderman, B. Finding facts vs.
Structured Thesaurus. International Conference on browsing knowledge in hypertext systems, IEEE
Conceptual Graphs, ICCS ’96, University of New South Computer, 21, 70-80, 1988.
Wales, Sydney, 1-12, 1996. 16. Richards, D. and Compton, P. Taking up the Situated
4. Compton, P., Horn, K., Quinlan, J. R., Lazarus, L. and Cognition Challenge with Ripple Down Rules.
Ho, K. (1989). Maintaining an Expert System, In J. R. International Journal of Human-Computer Studies
Quinlan (Eds.). Application of Expert Systems, London, 49:895-926, 1998.
Addition Wesley, 366-385, 1989. 17. Priss, U. E. A Graphical Interface for Document
5. Compton, P. and Jansen, R. A Philosophical Basis for Retrieval Based on Formal Concept Analysis.
Knowledge Acquisition. Knowledge Acquisition 2:241- Proceedings of the 8th Midwest Artificial Intelligence
257, 1990. and Cognitive Science Conference, AAAI Technical
6. Erdmann, E. Formal Concept Analysis to Learn from the Report CF-97-01, 66-70, 1997.
Sisyphus-III Material. Eleventh Workshop on 18. Priss, U. Faceted Information Representation, In:
Knowledge Acquisition, Modeling and Management Stumme, Gerd (de.), Working with Conceptual
(KAW’98), Banff, Alberta, Canada, 1998. Structures. Proceedings of the 8th International
7. Furnas, G. W. Generalized fisheye views, Proceedings Conference on Conceptual Structures, Shaker-Verlag,
of the Human Factors in Computing Systems, North Aachen, 84-94, 2000.
Holland, 16-23, 1986. 19. Stumme, G. Distributive Concept Exploration: a
8. Furnas, G. W., Landauer, T. K., Gomez, L. M. and knowledge acquisition tool in formal concept analysis.
Dumais, S. T. Statistical semantics: analysis of the In: O. Herzog, A. Gunter (eds.): KI-98: Advances in
potential performance of key-word information systems, Artificial Intelligence. LNAI 1504, Springer, Berlin-
Bell System Technical Journal, 62, 1753-1806, 1983. Heidelberg, 117-128, 1998.
9. Gaines, B. and Shaw, M. Cognitive and Logical 20. Stumme, G. Hierarchies of Conceptual Scales. 12th
Foundation of Knowledge Acquisition. The 5th Banff Knowledge Acquisition, Modelling and
Knowledge Acquisition for Knowledge Based Systems Management, Eds. B Gaines; R Kremer; M Musen,
Workshop, Banff, 9.1-9.25, 1990. Banff Canada, 16-21 Oct., SRDG Publication,
University of Calgary, 1999.
10. Ganter, B. and Wille, R. Formal Concept Analysis:
mathematical foundations. Springer, Heidelberg, 1999. 21. Tecuci, G. Building Intelligent Agents: An
Apprenticeship Multistrategy Learning Theory,
11. Godin, R., Missaoui, R. and April, A. Experimental Methodology, Tool and Case Studies. Sydney,
comparison of navigation in a Galois lattice with Academic Press, 1998.
conventional information retrieval methods.
International Journal of Man-Machine Studies, 38, 747- 22. Wille, R. Restructuring lattice theory: an approach
767, 1993. based on hierarchies of concepts. In: Ivan Rival (ed.),
Ordered sets, Reidel, Dordrecht-Boston, 445-470, 1982.
12. Godin, R., Missaoui, R. and Alaoui, H. Incremental
concept formulation algorithms based on Galois 23. Wille, R. Knowledge acquisition by methods of formal
(concept) lattices. Computational Intelligence, 11(2), concept analysis. In: E. Diday (ed.): Data analysis,
246-267, 1995. learning symbolic and numeric knowledge. Nova
Science Publisher, New York, Budapest, 365-380, 1989.
13. Kim, M. and Compton, P. Developing a domain-specific
Information Retrieval Mechanism. Proceedings of the 24. Wille, R. Concept lattices and conceptual knowledge
6th Pacific Knowledge Acquisition Workshop (PKAW systems. Computers and Mathematics with
2000), Eds. P. Compton; A. Hoffmann; H. Matoda; T. Applications, 23, 493-515, 1992.
Yamaguchi, Sydney Australia, 189-206, 2000.