Browsing is being supported in many information retrieval systems to supplement Boolean querying. We have implemented a web-based browsing mechanism for a domain-specific document retrieval system based on the concept lattice of Formal Concept Analysis. In this paper, we have proposed and implemented an incremental development of browsing by combing Formal Concept Analysis (FCA) and Ripple Down Rules (RDR) as well as incorporating a domain ontology. It allows a user to formulate browsing in a more systematic and general way for the domain by discovering relevant concepts when a new document is added and an existing document is refined. The user can fairly easily add new documents and annotate these so that they can be readily retrieved and also distinguished from less relevant documents. The mechanism incorporates an ontology for the documents which emerges over time rather than having to be defined from the outset. A part of experimental evaluation of the system shows good retrieval performance and a significant improvement after the introduction of an incremental knowledge acquisition mechanism.
INTRODUCTION In information retrieval processes, the degree of user interaction is typically twofold. In general, a user sends a Boolean query to the system and the system returns a result. Then the user can refine or reformulate the query corresponding to the result until he/she is satisfied with the result. In a second style of interaction, the user simply navigates a hierarchical classification scheme or subject categories displayed by the system using hyperlinks menus or some direct representation of the hierarchy.
The method of direct query formulation is most useful when the user knows what she/he is looking for and has some background knowledge of the search domain. However, setting up an appropriate query is a difficult process, especially for novice users and when the users do not know exactly what they want and how to get it.
The browsing approach is being supported in many
information retrieval systems to resolve this problem. The
obvious advantage of this method is that the users can
quickly explore the search domains and can easily acquire
the domain knowledge
To solve the problem a new browsing mechanism has been
introduced based on the concept lattice of the Formal
Concept Analysis (FCA)
The effectiveness of browsing also depends on whether the relationships between the clusters are constructed in a 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 natural that the hierarchy can be structured more systematically when domain terms are involved.
For the same reason, information retrieval based on FCA
often incorporates the use of thesauri or classification for
the domains
Following this paradigm, we have been implemented a
webbased browsing mechanism for a domain-specific document
retrieval system
It is essential to be able to incrementally construct a concept lattice by adding a new document and refining the existing information in the system. The set of documents can be added in a batch, but it is more likely that documents will be added individually. Thus, Godin et al (1995), Carpineto and Romano (1996), and Kim and Compton (2001) proposed incremental algorithms for updating the concept lattice. All these approaches simply reconstruct the lattice incrementally to cover the new case with the given keyword set.
However, none of studies has been done in regard to incremental knowledge acquisition. When an expert assigns the set of keywords for a document, some concepts may not be made up in just the context of the input case but also can be prompted in regard to the stored cases. The expert also tends to ignore the most general concepts (keywords) of the domain, even if they (or authors) are the most appropriate agents to assign meaningful concepts for the documents. Thus, it is necessary to have certain knowledge acquisition mechanisms to be able to extract the concepts which are missed or unknown when concepts are assigned, enabling experts to constantly improve the system’s retrieval. Thus, we have proposed and developed an incremental knowledge acquisition mechanism to extract some important concepts for the cases as well as discover the domain ontology from the situated cognition view. It has been facilitated by combining the FCA browsing and RDR knowledge acquisition techniques.
Here, an ontology can be a thesaurus or a taxonomical ontology for the domain1. Typically, thesauri are used for indexing (browsing) to select the most appropriate thesaural entries for representing the document. They are also used for background knowledge to expand the users’ query to enhance the retrieval process. In general, ontologies for the domain are established prior to developing information retrieval systems.
In this approach, we can anticipate that there will be the
typical problems of software engineering methodologies in
building and maintaining the ontologies, even though the
approach has certain benefits. Moreover, new cases
(documents) are added into the system in continually and
the domain knowledge is in a dynamically changing
environment. Hence, in our view the ontologies should be
discovered from the domain knowledge as documents are
added, or when documents fail to be retrieved, by the
domain experts adding concepts rather than simply using a
predefined ontology. Of course, in the pre-defined
approach, the ontology can be refined, but the maintenance
of ontology is still ongoing research
The incremental concept formation called learning from observation is also a fundamental process of human learning since the concepts to learn are not pre determined by an expert and the instances are not pre-classified with respect to these concepts.
In the involvement of thesauri or ontologies, a more critical
situation is as follows: In building an ontology, the
relationship between terms are defined with an equivalent
(synonym) relationship, part-of and part-whole
(nonhierarchical) relationship, is-a (hierarchical) relationship
and so on. Here, we will only look at this problem in the
hierarchy. Let C = (D, K, I) be a formal context as in
Definition 1 in the following section. We start from the
subsumption hierarchy of an ontology with a partially
ordered set (K, ≤) and a context (D, K, I). D is a set of
documents which are collected from the set D and K is the
1 We use the term ‘ontology’, ‘taxonomical ontology’, and
‘thesaurus’ interchangeably, even these have a slightly
different definition. But we prefer to use the term
‘ontology’, even though there is a tendency to have a
meaning of ‘taxonomical ontology’ and 'thesaurus '.
set of terms in the ontology. When a thesaurus is involved
in an information retrieval process, the following
compatibility condition is assumed for a subsumption
hierarchy
Again, the ontologies should be discovered from the domain knowledge in connection with adding a new case and refining stored cases. We propose an approach to solve this problem by combining the knowledge acquisition process for the documents. We also provide a tool for experts to develop a domain ontology to cover the stored documents of the knowledge base by re-using keywords if required.
We already mentioned that effectiveness of browsing depends closely on how well the relationships between the clusters are constructed in the hierarchy in a more general and specific way. Hence, most of the clustering incorporates the use of classification schemes or thesauri. We have observed that our knowledge acquisition mechanism allows the construction of a more generalised and structured browsing scheme improving its retrieval performance. Such a browsing structure can also represent the domain ontology in the longer term.
We have implemented a browsing mechanism and an
incremental knowledge acquisition mechanism for a
domain-specific document retrieval system on the Web with
a test domain of papers at the Banff Knowledge Acquisition
Workshops in recent years (URL: http://pokey.cse.unsw.
edu.au/servlets/Search). We have also observed that the
system allows enabling experts to constantly improve the
system 's retrieval. In this paper, we focus on explaining the
incremental knowledge acquisition mechanism we have
developed, rather than demonstrating the system.
In the next section, we will explain methods we have used.
Then we will present the incremental knowledge acquisition
2 Gerd Stumme describes this problem in the paper
METHODS
One of the very complex tasks in AI is known as knowledge
acquisition accompanied by the knowledge acquisition
bottleneck. To improve the bottleneck problem, a new
modern approach
FCA is used for a knowledge acquisition process
However, the general principle is still to give the expert a
view of the whole domain so that all relevant concepts will
be included. Despite that, we have argued that experts
more easily provide concepts that distinguish between cases
Ripple Down Rules (RDR)
RDR is an effective knowledge acquisition and
maintenance methodology which allows a domain expert to
build and maintain knowledge based systems very simply
and to acquire domain knowledge easily and quickly. The
approach was initially developed in dealing with the
problems found in the maintenance of the medical expert
system GARVAN-ESI
In the RDR method, the expert is only required to identify
features that differentiate between a new case being added
and the other stored cases already correctly handled. That is
the main technique of knowledge acquisition in RDR which
is very similar to the use of differences in personal
construct psychology
It has been applied to a range of tasks: multiple classification, control, knowledge reuse, heuristic search, configuration and information retrieval. There are a number of other lines of RDR research integrating RDR with machine learning and fuzzy reasoning.
Formal Concept Analysis (FCA)
FCA is a data analysis method for explicitly investigating
and processing given information based on a mathematical
theory
The extension of a concept is formed by all objects to
which the concept applies and the intension consists of all
attributes existing in those objects. All formal concepts are
found using given mathematic formulas. Then the
subconcept-superconcept relationships between formal
concepts are expressed in a concept lattice. The concept
lattice can be seen as a semantic net providing "hierarchical
conceptual clustering of the objects… and a representation
of all implications between the attributes"
Formal Contexts and Formal Concepts 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 attributes and I is a binary relation between G and M which indicates where an object g has an attribute m by the relationship gIm (also by (g, m) ∈ I).
In our application we suppose that documents correspond
to objects and the keywords of the documents constitute
attribute sets. Then we define a formal context (C) as
follows in our document retrieval system:
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
3 This definition follows the Basic Theorem of FCA
Definition 2: Let C = (D, Κ, Ι) be a formal context, and d be a new document (d ∉D) and Γ be the set of keywords of d. The set of keywords is not necessarily a subset of Κ. Then, the extended formal context of C is defined as C+ = (D+, Κ+, I+) where D+ = D ∪ {d}, Κ+ = Κ ∪ Γ and I+ = I ∪ {(d, k) | k ∈ Γ}.
Definition 3: Let C = (D, Κ, Ι) be a formal context and Γ be a set of keywords (Γ ⊆ Κ). Then the set of documents associated with Γ is defined to be ΔΓ = {d ∈ D | ∃k ∈ Γ such that (d, k) ∈ Ι}.
We introduced ΔΓ to get a set of documents which has at least one keyword of Γ. If Γ is a singleton (i.e. Γ= {γ}), then we will abbreviate Δγ ΔΓ = {d ∈ D | (d, γ) ∈ Ι}. Definition 4: Let C = (D, Κ, Ι) be a formal context. We define a function ƒ from D to 2K as ƒ: DÈ 2K such that ƒ (d) = {k ∈ Κ | (d, k) ∈ Ι}.
That is, ƒ (d) returns the set of keywords of d. Let the new document be d (∉D) with the set of keywords Γ. We formulate the sub-formal context C′ = (D′, K′, I′) with D′= ΔΓ + {d} where ΔΓ is in definition 3 andK′ = U f (d ) where ƒ is the function in definition 4. In order dt∈oDg′et a set of relevant keywords of d, we obtain a set of keywords which are associated with ΔΓ as ƒ(ΔΓ) = U f (d ) from the context C′. Now the set of relevant keydw∈Δorrds is defined as ℜ = ƒ(ΔΓ) - Γ. Then, the function Freq introduced below is used for each keyword of ℜ (k) to compute the number of common keywords of Γ with the keywords of all the documents that have the keyword k from the context C′. Definition 5: We define a function Freq from 2K × Κ to the set of natural numbers 1 as follows: Freq: 2K × Κ È 1 such that Freq (Γ, k) = ∑ | ƒ(d ) ∩ Γ | where |X| is the cardinality of X. d ∈Δk In the first step, an ordered set of documents and a set of keywords which are relevant to the new document are obtained. This step is divided into two stages. In the first stage, the ordered documents are shown to the user along with the different features between the new document and each of the set of documents. In the next stage, the frequency of each of relevant keywords is computed. Then, the ordered relevant keywords are presented to the user with their frequency.
To process this step, a sub-lattice £(D′, K′, I′) of the formal context C′ is constructed. The similarity relation between concepts can be easily observed through the lattice. Given a new document d, we are interested in finding the set of documents Dd that share some commonalties. We formulate a formal concept ζ ({d}, Γ) with the newly added document d and its set of keywords Γ. Informally, starting from the concept ζ we recursively go up to the direct superconcepts of its subconcept in the lattice to find the next level of the relevant documents. This procedure is done until the superconcept reaches the top node of the lattice.
For example, we suppose that there is a concept lattice as shown in Figure 2 and, a new document d (5) is added together with and its set of keywords Γ {natural language processing, speech recognition, verbal interference}. Then, we formulate the sub-context C′ = (D′, K′, I′) where D′ = ΔΓ + {d} = {3, 4, 5}, K′ = U f (d ) = {artificial intelligence, d∈D′ information retrieval, natural language processing, speech recognition, signal representation, verbal interference} and I′ is a binary relation between D′ and K′. The sub-lattice £(D′, K′, I′) of the context C′ can be constructed as shown in Figure 3. The gray coloured box indicates the formal concept ζ. From the lattice we can get the document ’4’ at first. Because it exists in the direct superconcept of ζ in the lattice which indicates the most relevant of the document ’5’. Next the document ’3’ is obtained. Finally, we get an ordered set of documents {4, 3} by the relevancy of the document ’5’ in the lattice. The ordered documents are then suggested to the user along with the different features between the new document and each of the relevant documents. At this stage the user can look at the lattice structure itself using browsing mechanisms supported by the system. The result obtained by this process is equivalent to k-nearest neighbour algorithms.
At the next stage, we elicit the relevant keywords from which are associated with the newly added document d. Then, a frequency for each relevant keyword is calculated by definition 5. Following this, the keywords are ordered by their frequency and the system suggests the keywords to the user with their frequency. After that, the system asks the user the relevancy for each extracted keyword and the user can simply answer by clicking the check box located in the front of each keyword. For example, let a new document d be ’5’ and the set of keywords (Γ) of d be {natural language processing, speech recognition, verbal interference}. Then, we can get a set of documents associated with Γ (ΔΓ) ={3, 4} by definition 3 from the sub-context C′ = (D′, K′, I′) shown in figure 3. After that, the set of keywords which are associated with ΔΓ is obtained: that of ƒ(ΔΓ) = {artificial intelligence, information retrieval, natural language processing, speech recognition, signal representation} by definition 4. Finally we define the set of relevant keywords as ℜ = ƒ(ΔΓ) - Γ = {artificial intelligence, information retrieval, signal representation}. Because the set of keywords in ℜ are candidates of expanding the keywords already associated with d. Then, for each element of ℜ, a frequency is calculated by definition 5 as follows: Freq(Γ, artificial intelligence)=3, Freq(Γ, information retrieval)=1 and Freq(Γ, signal representation)=1. Through this process, experts can capture some relevant concepts (here, the keyword ‘artificial intelligence’ or may others) in adding a new document.
{Natural language processing} / {3, 4, 5} Artificial intelligence Natural language processing / {3, 4}
Natural language processing Speech recognition / {4, 5} The next step of knowledge acquisition is based on an ontology. This mechanism will be explained in detail in the following section.
In the final stage of knowledge acquisition when a new document is added, we use the RDR techniques using a flat RDR rule tree. In the RDR approach, when a new rule is added, all stored cases that can be reached by the parent rule (=cornerstone cases) are retrieved. Then the expert is required to construct a rule which distinguishes between the new case and the cornerstone cases until it excludes all cornerstone cases. In our document retrieval system, a case which has the same set of keywords of the new document, becomes a cornerstone case of the new case. If a cornerstone case exists, the system elicits a relevant keyword set of the new case in the same way used in the step1 of Table 1. Then, the extracted relevant keywords become available to the expert. The expert has to select at least one different feature (keyword) from the deployed keywords or specify a new word to distinguish the cornerstone case and the new case. Another cornerstone case can be prompted by new added keywords. Thus, this process is continued until there is no cornerstone case. When a New Class is added in the Ontology We support a tool to develop a domain ontology to cover the stored documents of the knowledge base. Here the ontology can be a set of hierarchies of terms where a term is either a single word or a phrase along with the relationship between terms. Figure 4 shows a possible example in our document retrieval system. The structure of the ontology is also a lattice (graph), even if it presents in a hierarchy. It means the number of entries for each term exists in the structure and a term can have multi parents. For the convenience of explanation, we use the term 'class'and 'attribute'to describe a concept node in the ontology. For example, the term 'Internet'is a class with a set of attributes {Web browser, Web servers} in Figure 4. 'Web servers'is also a class with an attribute set {Apache, Java}. It means 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 new case is added by connecting to the process that is to be able to hold the compatibility condition in the ontological hierarchy.
Artificial intelligence Natural languageprocessing Information retrieval / {3}
Artificial intelligence Natural language processing, Speech recognition Signal representation / {4} At any stage the expert/user can set up or change the hierarchy. Table 2 shows the algorithm of knowledge acquisition incorporating the ontology when a new document is added. When a document d with a set of keywords (Γ) is added, the system gets all class paths which the set Γ belongs to. For each class of each class-path if the document includes the class, a class is set to a value ‘true’ for the document, otherwise to the default value ‘unknown’. For each class whose value is 'unknown'the system asks the user about inheritance between the class and the associated keyword. Then the user should answer with one of the values; 'true ', 'false'or 'unknown '. After that, the system validates the assigned values of the classes for each path as follows: Let G = (V, E) be the directed graph representing the ontology and T be the set of all class paths found. Then, T is valid if and only if there does not exist any pair of nodes u, v ∈ V such that for each path of T(v1, …, vn) in G the following conditions hold: (i) v1 = u and vn = v (iv) there exists i such that 1 < i < n and (vi = ’false’or ’unknown’) The problem with this is not the removal of a class node in the hierarchy, but a new class (a concept node). It is probably tool costly to go through every case where the new node may apply. Thus, we just set the value of class with 'unknown'in all cases where the change in hierarchy says it might apply. Table 3 shows the algorithm of adding a new class node in ontology. Then, in any given browsing the user can choose to temporarily assign 'unknown'to either 'true'or 'false '.In other words, when the user browses the nested attributes, the system shows menu items with ‘true’, 'false'and ‘unknown’ for each attribute of the class. When the user looks at the document which belongs to the ‘unknown’ menu item, the system will ask the inheritance of the class in regard to the document with ‘true’, 'false'or ‘unknown’. The knowledge base will then be changed according to the user’s selection.
Rebuild the set Γ by adding the classes which are set 'true ';
End if
Modify the knowledge base End Experimental Evaluation of Retrieval In our experiment, we evaluated how the retrieval effectiveness of browsing can shift when the compatibility condition is held in the ontological hierarchy. Other incremental knowledge acquisition factors developed still remain to be empirically evaluated.
The experiments were carried out on a collection of documents, which belongs to the domain of the knowledge acquisition area. The collection consists of 200 documents and its taxonomical ontology. Then, we reformulated the ontology into three different hierarchies which have the average number of entries for each thesaural term with 1.12, 1.23 and 1.35 respectively by adding and pruning each term 's parents. Next, we constructed three different ontologies which hold the compatibility condition with the percentage of 'unknown' value 80%, 50% and 10% respectively for each reformulated ontology. It has been conducted by relevance judgements manually. We also built a set of 40 queries which are related to the ontological terms by conjunctive and disjunctive keywords. For each query, relevance decisions with documents were also given in advance. Someone may argue with the size of the documents. But we believe the size is quite enough for the test to be considered significant for our approach. Currently we are evaluating a quite large set of documents obtained from INSPEC. The documents consist of a title, an abstract and a set of keywords with an average of 6.15. Table 4 shows the results of our experiment.
which holds the compatibility condition (percentage of ’unknown’ value) 80% 50% 10% Clearly, the findings indicate that the effectiveness of retrieval both in recall and precision has improved when the ontology, which holds the compatibility condition, incorporates the retrieval against Case 1. The retrieval performance is improved when the ’unknown’ values of terms are revealed. That is, the quality of the retrieval is improved by incremental maintenance of the system’s knowledge over time. In the comparison with Case 2 and Case 3 in Table 4, the results show Case 3 has a better performance in precision, but a lower effectiveness in recall. However, we already pointed out that the incremental maintenance of the system increases the performance in recall. The results also reveal that the retrieval performance is proportional to the average number of ontological entries for each term in Case 2. It means that the precision of retrieval is getting worse, even though the recall is improved. In other words, the bigger the average number of entries for each term becomes, the more irrelevant documents will be.
SUMMARY
In previous work
Although FCA and RDR seem an attractive solution to incrementally develop a browsing mechanism for a specialised domain, we have not yet fully evaluated this approach and not yet carried out knowledge acquisition in a timely manner based on the proposed mechanism. We need to evaluate this approach in routine use with reasonably large data sets. At a more fundamental level, the value of FCA for IR is based on the assumption that when you enter a keyword, and the documents retrieved are inappropriate, then these documents will have other keywords that will eventually lead you to the desired documents. This is a central but hidden assumption in proposing that a latticebrowsing scheme will have advantages over a hierarchical approach. In a hierarchical scheme you simply go back to the top and start again. With a lattice approach you assume that there are other features of the retrieved document that will also occur in the documents you really want to retrieve. This is a central and critical assumption that needs to be explored further.
In summary, we have not yet fully developed and evaluated this form of expert-centred information retrieval. However, this prototype at least suggests the possibility of a new way of information retrieval associated with browsing where an expert can rapidly build and maintain an information retrieval system in his or her area of expertise which will be easy for domain users. We believe that these highly specialised, ’disposable’ systems will be critical in making full use of the enormous amounts of knowledge appearing in Intranets and the Internet itself.
ACKNOWLEDGMENTS The authors would like to thank Bao Vo and Dr. Rex B. H. Kwok for helping in formalising of mathematical formulas used in definitions.