A KNOWLEDGE MEDIA APPROACH
USING ASSOCIATIVE REPRESENTATIONFOR CONSTRUCTING INFORMATION BASES
Harumi Maeda, Kazuto Koujitani and Toyoaki Nishida
Graduate School of Information Science,
Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara, 630-01 Japan
Email: harumi-m@is.aist-nara.ac.jp

Abstract
In this paper, we present a new approach based on
knowledge medium using associative representation asa framework of information representation to gather
raw information from vast information sources and tointegrate it into information bases cost-e ectively.
We then present a knowledge media informationbase system called CM-2 which provides users with ameans of accumulating, sharing, exploring and re ning
conceptually diverse information gathered from vast
information sources. We describe the system's four
major facilities; (a) an information capture facility, (b)an information integration facility, (d) an information
retrieval facility and (d) an information re nement facility. We discuss the strength and weakness of ourapproach by analyzing results of experiments.
keywords: associative representation, knowledge media, knowledge media system, CM-2, information base

1 Introduction
There exist various kinds of information sources aroundus. For instance, personal memoranda, research notes,
hypertexts, image les and so on. Most of such information is conceptually diverse in the sense that its
semantics is not rigorously de ned.
In addition, widespread access to the Internet and
WWW has led to a new phase in information acquisition. There already exist large scale information resources and they are increasing rapidly. We need tointegrate a wide variety of information into personal
information space from our point of view. However, it
seems almost impossible to design a well-de ned conceptual structure for organizing diverse information

obtained from heterogeneous information sources.
In this paper, we present a new approach basedon knowledge medium [Ste k86] using associative representation as a framework of information representation. The basic recognition behind this research is atrade-o between the bene t from conceptually wellstructured information space and the cost for organizing information space. The more well-structured information representation becomes, the more useful it
is for computational manipulation, however, the more
expensive the cost of information acquisition becomes.
Associative representation is a plain and weakly structured knowledge medium which is visible and manipulatable to humans and computers. We use associative
representation to gather raw information from vast information sources and to integrate it into information
bases cost-e ectively.
We then present a knowledge media informationbase system called CM-2 which provides users with ameans of accumulating, sharing, exploring and re ning
conceptually diverse information gathered from vast
information sources. We describe the system's four
major facilities;
 an information capture facility which helps users

gather information from multiple information sources an information integration facility which allows

users to integrate heterogeneous information into
personal information space from the user's pointof view

 an information retrieval facility which gives users

access to multimedia information stored in theinformation base through associative indexing mechanisms

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

(b)

(a)
Nara

Nara & temple

Todai-jiNara Park
deer
Daibutsu

Todai-ji
Horyu-ji
Kofuku-ji

Figure 1: Example associations in CM-2

(b)
NAIST

(a)
Todai-ji
templeNara Institute of
Science andTechnology(IS-A)(dictionary)Figure 2: Example associations (special types)

 an information re nement facility which helps

users reorganize the information base to be morecomprehensive

We discuss the strength and weakness of our approachby analyzing results of experiments.
In what follows, we rst describe the role of a plain
indexing method using associative representation andoverview the CM-2 information base system. We thenpresent the system's four major facilities. Finally, weshow experimental results and make discussion.

information space for a person or a group
human-oriented
workspace

agent
comuter-oriented

protocol2 Associative Representation in Figure 3: The Architecture of the CM-2 Information
CM-2 Information Base Sys- Base System
2.2 Overview of the CM-2 InformationtemBase System

2.1 An Indexing Method Using Associative Representation

In this paper, we focus on associative representation,
which allows the user to explore a way of articulating
conceptually diverse information by aggregating conceptually relevant information. The basic entities ofassociative representation are (a) a unit which represents either a concept or an external datum, and (b)an association which connects a collection of key concepts (hereafter keys) with a collection of units (hereafter values) which is normally reminded by the given
keys. Figure 1 shows a couple of associations. Figure 1(a) says that given a concept \Nara", one may
be reminded of \Todai-ji", \Nara Park", \deer", and\Daibutsu". Figure 1(b) is an example of association with more than one key. It says that \Todaiji", \Horyu-ji", and \Kofuku-ji" are reminded when
\Nara" and \temple" are given as keys.
Users can de ne special types of associations to be
used in information integration and re nement facility.
Figure 2(a) is a \IS-A" relation which connects a unit
with other units which are reminded as a class of thegiven unit. Figure 2(b) is a \dictionary" relation which
can be used for translation.

CM-2 1 is a knowledge media information base system
which provides users with a means of accumulating,sharing, exploring, and re ning conceptually diverse
information gathered from vast information sources.
CM-2 consists of a collection of information bases.
Each CM-2 information base is possessed by an individual person or a group (Figure 3) and it consists ofa collection of workspaces and agents. Each workspaceprovides a particular view of multimedia information
stored in the information base.
Each agent manipulates information tasks and interacts with the user. The user or the agents in CM2 can interact with other, or incorporate informationfrom other kinds of information sources connected to
the Internet.
Figure 4 shows an example screen of CM-2.
In what follows, we describe four major facilities of
CM-2.
1 \CM" stands for \Contextual Media" which stands for ourlong term theoretical research goal.

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

Figure 4: An Example Screen of CM-2

3 Information Capture Facility

We have also implemented those for capturing undigitized information, such as ideas. Users can input units
using keyboard and connect them using mouse throughworkspaces.

The structure of information may well di er according
to authors, and people might give di erent names tosame concept and same names to di erent concepts.
Compare Figure 5(a) and (b). These are WWW 3.1 Information Capture for WWW pages
pages of two famous AI researchers 2 3 displayed on
WWW browsers. They are di erent in structure and We focus on capture facility for HTML documents on
use of words. We need to obtain useful information WWW. The general procedure of the facility is composed of the following steps.
from these kinds of diverse information sources.
Information capture facility helps users gather in1. generation of raw CM-2 units and associations
formation from multiple information sources and generate CM-2 associations.
(a) collection of HTML documents by analyzIt is easy to generate associative representations
ing URL
from various information sources using a simple key(b) extraction of noun phrases and generation
word extraction and text analysis algorithm.
of units using Rule Based Tagger by Eric
We have implemented capture programs for digiBrill [Brill68]
tized information, such as UNIX le system, program(c) generation of associations by analyzing theles written in Lisp, Nikkei newspaper full-text databasestructure of HTML documents
and HTML documents on WWW.
2 http://www.cs.rochester.edu/u/james/3

http://www-ksl.stanford.edu/people/bhr/index.html

2. generation of \IS-A" relations and modi cationof units using domain knowledge

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION(a) James Allen's Home Page(b) Barbara Hayes-Roth's Home Page

Figure 5: Example Home Pages(a) extraction and generation of \IS-A" relations from units(b) removal of unnecessary units and modi cation of associations
An example of domain knowledge used in step2 (a)is as follows:
it is inferred that the class of a unit \James
F. Allen" is a \people", because the unit's
label contains \James" which is one of common English names.
Figure 6 shows the overview of the algorithm whena URL of James Allen's Home Page is given.

4 Information Integration Facility
Information integration facility allows users to integrate heterogeneous information into personal information space from the user's point of view. When auser input items for reorganizing information, it generates new associations in accordance with users request
and itemizes them.
The following describes the general procedure of
the facility.
1. uni cation of units and associations using several
heuristics

2. generation of new associations according to user
input(a) extraction of keys by path nding(b) extraction of values by path nding(c) generation of new associations
HTML file<h1>James F.Allen, URCS Faculty Member </h1><p>b. 1950. Ph.D. (1979) University of Toronto.
Assistant Professor (79-84),.....; University of Rochester.
<p>James Allen's research interests.........................
These areas of research are combined in TRAINS Project,...................

James F.Allen
peopleUniversity of Toronto
university(IS-A)TRAINS
project(IS-A)
University of Rochester(IS-A)
James F.Allen(IS-A)
James F.Allen

University of Toronto
University of Rochester

university

TRAINS

Figure 6: Information Capture Facility

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

Some examples of heuristics used in step1 are statedbelow.
 uni cation of units whose labels are the same
 uni cation of units referring to user dictionaries
 generation of associations between units when aunit's label is included in another unit's label

 uni cation of associations whose keys are thesame

Let us think a case that when a user wants toknow AI researchers and their contact information andprojects concerning your research interest but there
is no such database available. The user may search
WWW pages about AI, read appropriate encyclopedia and organize the information using his/her knowledge. Information integration facility helps user's suchprocess.
Figure 7 shows how the facility answer the following question against the sets of CM-2 associations
which are mixtures of associations generated by information capture facility and those obtained by otherinformation sources.
\Display a list of researchers and related
projects concerning `reasoning' ?"Figure 8 and gure 9 illustrate example results ofthe facility.

5 Information Retrieval Facility
Information retrieval facility gives users access to multimedia information stored in the information basethrough associative indexing mechanisms. The system
has three information retrieval facilities: (a) keyword
search, (b) neighbor search and (c) intelligent associative retrieval. The rest part of this section describes
neighbor search and intelligent associative retrieval.

5.1 Neighbor Search
Neighbor search enables users to search and display
units which are linked to the selected unit by associations. For example, when an association shown in Figure 1 is given and the user selects \Nara", linked units
such as \temple", \Todai-ji", \Horyu-ji" and \Kofukuji" will be displayed. Users can execute neighbor search

User Input

keyword: reasoning
item1:
researcher item2: project

reasoningproject

researcher

James F.Allen & topic

researcher

plan reasoning
discourse

people(dictionary)
TRAINSJames F.Allen
peopleproject(IS-A)(IS-A)

James F.Allen
TRAINSJames F.Allen & project
TRAINS

Figure 7: Information Integration Facility (step2)
by pressing buttons displayed nearby units on workspaces
4.
Neighbor Search causes a problem when there are
too many values associated with the selected unit; itis very dicult to identify the displayed units. Figure
10 shows an example of workspace in such a case. To
remedy this problem, we need more intelligent and dynamic search facility to obtain the desired informationand it will be described in the next section.

5.2 Intelligent Associative Retrieval
Path nding is a powerful means of retrieving information, in particular when what is contained in an
information base is structurally di erent from the presupposition of a given query.
Figure 11 illustrates how the algorithm works toanswer a question:\are there any places in Nara that are famous for rhododendron?"
4 These buttons are displayed when units have some values
undisplayed on workspaces. A number displayed within buttons
describes the number of values of the unit.

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

Figure 8: An Example Screen of Information Integration Facility 1 (A List of AI Researchers with their
Related Information)

Figure 9: An Example Screen of Information Integration Facility 2 (A List of AI Projects with their RelatedInformation)

Intelligent associative retrieval is based on the idea
We present a couple of heuristic techniques whichof \spreading activation" on semantic networks [Quillian68]will detect inappropriate associations from CM-2 inforand composed of the steps below.
mation base and suggest a possible way of remedyingthem.
1. extraction of units by analyzing the query
2. extraction of answers by path nding
3. display of the extracted units, answers, paths
which links these concepts, and concepts which
are useful for understanding the paths
Figure 12 shows the result of the intelligent associative retrieval.

6 Information Re nement Facility
Information re nement facility helps users reorganize
the information base to be more comprehensive.
Compare two sets of associations in Figure 1 (a)and (b). The association in Figure 1(b) is more comprehensive and useful than that in Figure 1(a) because
various kinds of entities are mixed up in the association in Figure 1(a).

Figure 10: An Example Screen of Neighbor Search(Problematic Case)A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATIONAA
A
rhododendron

Are there any places in Nara which are famous for rhododendron ?
Nara

AAAAAAAAAAAAAAAAAAAAAAAA
Nara & mountain

Nara & park
Yoshino-yama
Ikoma-yama

Nara Park

Nara & temple
Todai-jiMurou-jiHase-dera
Horyu-jiiftheng])0V [fx;yg]j ;penalty j(V [fxg]\jVV3[[ffyx;yg]jsuggestion\resolve the di erence between
V3 [fxg] \ V3 [fy g] and V3 [fx; y g],
by adding z to V[fx; y g] if z 62
V3 [fx; y g] and z 2 (V3 [fxg] \V3 [fy g]) "Murou-ji & flower
rhododendron

Hase-dera & flower
rhododendron
cammelia

Figure 11: Intelligent Associative Retrieval

h for concepts x and y :V3 [fxg] \ V3 [fy g] 6= V3 [fx; y g] i

if

3

3

3

h for two sets of concepts ; ,9z [ z 2 V[ ] ^ z 2 V[ ] ] i

 :

then

penalty 1 ;suggestion \remove z from V[ ]."Figure 13: Diagnosis rules for orthogonal decompositionde ne the similarity Sim[x; y ] as shown in Figure 15.
Based on that de nition, we de ne the key similarity
Sim3 [ ; ] between keys and as the sum of maximal pairwise similarities of units in and . Namely,
Sim3 [ ; ]23XX= max 4 max[Sim[x; y ]];max[Sim[x; y ]]5
x2 y 2

Figure 12: An Example Screen of Intelligent Associative Retrieval

6.1 Orthogonal Decomposition
Orthogonal decomposition attempts to decompose agiven information base into coherent groups of associations, by analyzing how the user intersects associations. It is a technique of re ning CM-2 informationbase using diagnosis rules shown in Figure 13.
An example of orthogonal decomposition is illustrated in Figure 14.

6.2 Analogical Re nement
Analogical re nement is a less ecient but more powerful technique for further elaborating information base
based on the measurement of similarity.
Given a couple of non-orthogonal keys x and y , wey2x2

For concepts x, y , and a threshold  > 0, we denotex  y if Sim[x; y]  . Similarly, for keys , , and athreshold  ,  if Sim3 [ ; ]   .

The analogical re nement heuristic suggests to rene a CM-2 information base according to the following diagnosis rule:if

x 2 V3 [ ],y 2 V3 [ [ fag], andx 62 V3 [ [ fag]thenpenalty Sim[x; y ] + Sim3 [ ; ]suggestion add x to V[ [ fag] .
There are several interesting suggestions. For example, from \cherry blossom" 2 V[f\Ikoma park"g]and, \cherry blossom" 2 V[f\ owers"g], we obtained\cherry blossom" 2 V[f\Ikoma park"; \ owers"g];A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

parks

Nara

Kyoto

Todai-ji the Nara park
deer
Daibutsu

Gion
Ginkaku-ji
the Maruyama park

Murou-ji

templesrhododendron

the Central park
the Nara park
the Maruyama park

Kinkaku-ji

flowers

Kinkaku-ji Ginkaku-ji
Todai-ji Eihei-jiNarapeony cherry blossom
rhododendron
azaleaNara & temples
Todai-ji

Kyoto & temples
Kinkaku-ji Ginkaku-ji

Murou-ji & flowers
rhododendron

templesEihei-jiNara & parks
the Nara Park

Kyoto & parks
the Maruyama park

Murou-ji
Nara

parks
the Central park

Nara
deer

Kyoto

flowers
peony

Gion

DaibtsuazaleaFigure 14: Orthogonal decomposition of CM-2 information base
Given a couple of non-orthogonal keys x and y , we de ne the similarity Sim[x; y] between x and y fromthree perspectives and let it:
Sim[x; y ] =Sim(a) [x; y ] + Sim(b) [x; y ] + Sim(c) [x; y ]2 [0; 1].
3

Sim(a) [x; y ] measures the similarity between x and y by comparing concepts in V3 [fxg] and those in V3 [fyg].
The de nition is as follows:
Sim(a) [x; y ] =1

jV3 [fxg][V3 [fyg]j( z z V3 [ x ] z+ z z V3 [ x ]+ z z V3 [ y ]1 jf j 2 f g ^ 2 V3 [f g]gj
j f j 2 f g 0 V3 [f g] ^ 9 [ 2 V3 [f g] ^ (K3[ ] \ K3 [ ] 6= fg) ]g j
j f j 2 f g 0 V3 [f g] ^ 9 [ 2 V3 [f g] ^ (K3 [ ] \ K3 [ ] 6= fg) ]g j).
y

y

u u

y

z

u

x

u u

x

z

u

Sim(b) [x; y ] measures the rate of common keys of associations containing x and y as values. Namely,Sim(b) [x; y ] =jf j 2 K3 [ ] ^ 2 K3 [ ]gj .
jK3 [ ] [ K3 [ ]j
z

z

x

z

x

y

y

Sim(c) [x; y ] measures the rate of keys orthogonal both to x and to y. Thus,
Sim(c) [x; y ] =jf j h is orthogonal to i ^ h is orthogonal to igj
jf j h is orthogonal to ig [ f j h is orthogonal to igj .
z

z

z

z

x

x

z

z

y

z

y

Figure 15: De ning similarity between concepts
from which we in turn obtained\iris" 2 V[f\Ayameike park"; \ owers"g]\Ikoma park"  \Ayameike park"; and\cherry blossom"  \iris";as shown in Figure 16.

based on\iris" 2 V[f\Ayameike park"g];

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

Experiment 4: Information Re nement Facility

Ikoma park

flowers

cherry blossom

cherry blossom

tickets

open

rhododendron
anirissimilarIkoma park & flowers

Ayameike park
similarcherry blossom

roller coarster
boats
iris

We have tested orthogonal decomposition and analogical re nement against the information base constructed in Experiment 3. As a result of orthogonal decomposition, CM-2 has produced 212 revisions,about 80 of which have been found useful. Others areuninteresting. On the other hand, the analogical renement heuristic has generated 65 suggestions, 20 ofwhich are found useful.

8 Related Work and Discussion

The work reported in this paper is part of the Knowledgeable Community [Nishida93] project which aims
iris
to develop a computational framework of collecting,accumulating, systematizing, sharing, and creating knowledge by human-computer interaction. Crucial issues
Figure 16: An interesting suggestion obtained by or- in the Knowledgeable Community are (a) knowledge
thogonal decomposition and analogical re nement
media, (b) ontology and (c) agent-assisted mediation
technology. We focus on knowledge media and have
7 Experiments
built an information base system using associative repWe have implemented CM-2 on top of Common Lisp resentation.
Our work is related to recent work on informaand tcl/tk. We are evaluating CM-2 against accumulating various kinds of information such as research tion gathering from heterogeneous sources on Internet
memoranda, technical surveys, regional guide, personal ([Levy94],[Armstrong95],[Balabanovi'c95],[Li95]). Indiary, and so on. Besides testing against these small stead of focusing on the strategies and heuristics forexamples and the examples described so far, we have information gathering, we concentrate on how to classify information obtained from multiple information
made a couple of experiments with a nontrivial scale.
sources and integrate it into personal information base.
The basic recognition behind this research is a tradeExperiment 1: Information Capture Facility We
have gathered 22 WWW pages concerning AI researchers. o between the bene t from conceptually well-structured
CM-2 has extracted units about 7 classes such as re- information space and the cost for organizing inforsearchers, topics and universities and generated asso- mation space. The more well-structured information
ciative representations. We have evaluated that 222 representation becomes, the more useful it is for computational manipulation, however, the more expensive
units out of 272 are appropriate.
the cost of information acquisition and integration beExperiment 2: Information Integration Facility comes.
Our approach is to provide a framework of inforAfter having modi ed CM-2 associations generated inmationrepresentation with a low structural facilities
Experiment 1, we have tested information integrationandtofacilitate
raw information from vast informafacility. A sample question is: \Display AI projectstionsourcestobeincorporated without much laborwith their related researchers and universities." 60
andgraduallyrenedand elaborated as more insights
units out of 72 are extracted properly.
are obtained.
How successful is our approach? Experiment 1,2
Experiment 3: Information Retrieval Facility
and
3 have ended up in very promising results. MemWe have manually constructed a CM-2 informationbase for regional guide of Nara, Japan. It contains bers of our group have been able to use associative
about 1,850 units and 870 associations. We have tested representation to accumulate and access varieties ofintelligent associative retrieval against the above in- information taken from vast information sources andformation base. We have obtained appropriate 24 an- access relevant information.
However, Experiment 4 shows that there is muchswers out of 30 queries.
Ayameike park & flowers

A KNOWLEDGE MEDIA APPROACH USING ASSOCIATIVE REPRESENTATION

space to improve heuristics about information re nement facility, since the rate of useful suggestions fromthe heuristics seems to be low. To improve the qualityof heuristics, we are currently looking at introductionof other kinds of heuristics and domain knowledge.

9 Conclusions
In this paper, we have proposed a new approach basedon knowledge medium using associative representation
as a framework of information representation to facilitate raw information from vast information sources tobe incorporated without much labor.
We have presented CM-2 information base system
which provides users with a means of accumulating,sharing, exploring and re ning conceptually diverse
information gathered from vast information sources.
We have described the system's four major facilities:(a) an information capture facility which helps users
gather information from multiple information sources,(b) an information integration facility which allows
users integrate heterogeneous information into personal
information space from the user's point of view, (c) an
information retrieval facility which gives users accessto multimedia information stored in the informationbase through associative indexing mechanisms, and(d)an information re nement facility which helps users
reorganize the information space to be more comprehensive. We have discussed the strength and weaknessof the method on the analysis of experimental results.
We have implemented a kernel of CM-2 on top of
Common Lisp and tcl/tk. The system currently operates on the UNIX platform.

References[Armstrong95] Robert Armstrong and Dayne Freitag
and Thorsten Joachims and Tom Mitchell. A learning apprentice for the World Wide Web. In Working Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed
Environments, pages 6{12, 1995.
[Balabanovi'c95]
Marko Balabanovi'c and Yoav Shoham. Learning
information retrieval agents: Experiments with automated web browsing. In Working Notes of the
AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments,
pages 13{18, 1995.
[Brill68] Eric Brill, Some Advance in TransformationBased Part of Speech Tagging. In Proceedings of theTwelefth National Conference on Arti cial Intelligence (AAAI-94),1994.
[Levy94] Alon Y. Levy and Yehoshua Sagiv and Divesh Srivasava. Towards ecient information gathering agents. In Working Notes of the AAAI Spring
Symposium on Software Agents, pages 64{70, 1994.
[Li95] Wen-Syan Li. Knowledge gathering and matching in heterogeneous databases. In Working Notesof the AAAI Spring Symposium on Information
Gathering from Heterogeneous, Distributed Environments, pages 116{121, 1995.
[Nishida93] Toyoaki Nishida and Hideaki Takeda.
Towards the knowledgeable community. In Proceedings of International Conference on Building
and Sharing of Very Large-Scale Knowledge bases
93,pages 157{166. Japan Information Processing
Development Center, 1993.
[Quillian68] M.R.Quillian, Semantic memory. In Marvin Minsky edition, Semantic Information Processing, MIT Press, 1968.
[Ste k86] Mark Ste k, The next knowledge medium,
AI Magazine, 7(1):34{46,1986.