=Paper=
{{Paper
|id=Vol-323/paper-5
|storemode=property
|title=Using Spreading Activation through Ontologies to Support Personal Information Management
|pdfUrl=https://ceur-ws.org/Vol-323/paper05.pdf
|volume=Vol-323
|dblpUrl=https://dblp.org/rec/conf/iui/KatiforiVD08
}}
==Using Spreading Activation through Ontologies to Support Personal Information Management==
https://ceur-ws.org/Vol-323/paper05.pdf
Using Spreading Activation through Ontologies to Support
Personal Information Management
Akrivi Katifori Costas Vassilakis Alan Dix
Dept. of Informatics & Telecommu- Dept. of Computer Science and Computing Department,
nications, University of Athens Technology, University of Peloponnese Lancaster University,
Panepistimioupolis , Ilissia, 15784, Terma Karaiskaki, 22100, Tripoli, LA1 4WA UK,
Athens, Greece Greece a.dix@comp.lancs.ac.uk
vivi@di.uoa.gr costas@uop.gr
ABSTRACT applications (word processing, address management,
Recent research in the domain of Personal Information internet browsing) and on the storage, organisation and
Management has recognized the need for a paradigm shift retrieval of information in files or databases, the content
towards a more activity-oriented system. Ontologies, as types and structure of which are determined by the units of
semantic networks with a structure not dissimilar to the one operation of the applications. However, real activity,
used by the human brain for storing long-term knowledge, whether for work or leisure, crosses application boundaries,
may be very useful as the basis of such a system. This work may involve portions of files, and interlinks fragments of
proposes the use of spreading activation over ontologies in both. Users should not have to focus on managing their
order to provide to a task-based system and its associated information but rather on performing the tasks this
tools with methods to record semantics related to information is to be used for.
documents and tasks and to support user context inference.
Recent research in the domain of Personal Information
Author Keywords Management (PIM) and Task-centered Information
Personal ontology, spreading activation, context inference. Management (TIM) has recognized the need for a paradigm
shift towards more task- and activity-oriented systems [21].
ACM Classification Keywords Ontologies, as semantic networks with a structure very
H5.m. Information interfaces and presentation (e.g., HCI): similar to the one used by the human brain for storing long
Miscellaneous, H3.0 Information Storage and Retrieval: term knowledge, may be very useful as the basis of such a
General. system. They offer a flexible and expressive layer of
abstraction, very useful for capturing the semantics of
INTRODUCTION information repositories and facilitating their retrieval either
As a direct result of the rapid technological progress of the by the user or by the system to support user tasks. To this
last few decades, personal computers have become end, if combined with appropriate “intelligent”
repositories for company information and scientific data, mechanisms, they may become useful tools to record
documents, electronic mail as well as personal collections semantics related to documents and tasks and function as an
of media, like photographs, video or music. Computer extension to the user’s own memory, available both for the
users, however, in order to take advantage of this memory user and the system.
complement offered to them, have to invest more and more This work explores the application of the spreading
time into managing and organizing their collections and activation theory of the human memory [1] [2] on
repositories because, if they don’t, retrieving information ontologies in order to create a context inference model for
from them when necessary will be nearly impossible. an ontology-based PIM/TIM prototype system. The
Furthermore, in current computer systems the user following section briefly outlines the architecture of this
interaction paradigm is based on functionally defined system, focusing on the ontology and context inference
module, whereas the next describes briefly the human
memory theories that have been the basis of this work,
along with an example of spreading activation. The
following section describes the creation of a personal
ontology for the user domain, followed by the description
of the spreading activation algorithm. The next section
discusses briefly the results of a preliminary evaluation of
the spreading activation module. Finally, after a brief
outline of related work, the last section presents the
conclusions and outlines future work.
© 2008 for the individual papers by the papers' authors. Copying permitted for private and academic purposes.
Re-publication of material from this volume requires permission by the copyright owners.
TOWARDS A PERSONAL INTERACTION MANAGEMENT Both of these require inference mechanisms which sit
SYSTEM outside this picture, using the information from the personal
The motivation of our work on personal ontologies and ontology and history and then feeding this in to modify the
spreading activation has been the vision of more activity- recognition and action selection. For task inference we are
centric computing and the general aim of moving from using a bottom up approach described in more detail in [23]
systems focusing on the management of personal and prototyped over actions on web forms. For context
information (i.e. PIM) to systems focusing on the inference we are using spreading activation over the
management of personal interaction. We define Personal Personal Ontology, which is the focus of this work. The
Interaction Management System (PIMS) to be a system that PIMS system architecture and individual components are
supports the user in executing tasks in an interactive and discussed in more detail in [21] and [22], whereas this work
efficient way, providing at the same time effective and focuses on spreading activation for context inference.
transparent mechanisms for maintaining the user’s personal
document collection. ONTOLOGIES AND PERSONAL INFORMATION
MANAGEMENT
In order for a PIMS to be effective, it should provide
According to [5], an ontology is an explicit specification of
effective mechanisms for user profiling, semantic storage of
a conceptualization. The term “conceptualization” is
documents and context inference. Figure 1 shows a sketch
defined as an abstract, simplified view of the world that
view of the main components a PIMS must include to
needs to be represented for some purpose. It contains the
support this functionality. The information side (documents,
concepts (classes) and their instantiations (instances) that
emails etc.) is linked to the computation side (actions)
are presumed to exist in some area of interest and their
through two main components:
properties and relations that link them (slots). The term
1. A recogniser finding suitable fragments of the raw “ontology” is borrowed from philosophy, where an
information that are semantically meaningful and that can ontology is a systematic account of Existence. This section
be used to initiate or feed into actions presents the creation of a personal ontology to be the basis
of the intelligent context inference mechanism of our PIMS
2. A personal ontology that contains knowledge specific to
system.
the user (people, projects, etc.).
Ontologies in PIM systems
Using an ontology to model semantics related to the user
personal domain has already been proposed for various
applications like web search [12], [13]. Most of these
approaches use ontologies only as concept hierarchies, like
hierarchies of user interests, without particular semantic
complexity. The value of ontologies for personal
information management has also been recognized and
there is on-going research on incorporating them in PIM
systems like OntoPIM [14], GNOWSIS [15] and the
semantic desktop search environment proposed in [16].
Figure 1. Basic outline of a PIMS system
In the context of our proposed PIMS system the personal
These two feed into one another. The various terms, names, ontology has a very important part to play. On one hand, it
emails, etc, in a personal ontology can yield keywords to be may constitute a useful repository of information related to
matched against text or semi-structured sources. So an many aspects of the user’s personal and professional life.
increasingly rich personal ontology will lead to better There the user will be able to store and access information
identification of suitable loci for action. Furthermore, as on contacts (friends, colleagues, etc), activities (like a
users perform actions the way in which they use research project or a hobby), events (like project meetings,
information, the results of their activities can be used to conferences, etc), documents (collected books and research
enrich the ontology. For example, if a piece of text is used papers, etc) and tasks. With the appropriate interface, the
to search in a gazetteer it suggests that (i) it is a place name ontology may become an easily customizable repository of
- that is we know more about its type and (ii) it is a place information that may serve as a memory complement for
name that is important to the user - so will be suggested to the user. On the other hand, coupled with intelligent
be added into the personal ontology. mechanisms, the ontology may become invaluable for
Figure 1 also shows a history sub-component related to the context inference in the process of supporting the user tasks
personal ontology. We need to record what is done in order through task inference.
to both (a) establish a sense of context and (b) be able to To this end, we have created an ontology for the user's
allow the system to gain some understanding of the user’s personal collection domain. This ontology has been created
ongoing activities. taking into account existing profile models in applications
as well as related research in the area of profiling.
Figure 2 Overview of the Personal Ontology with the upper levels expanded
Ontology Creation separate entities. These among others include dates, URLs,
Creating a personal ontology, either automatically, telephone numbers, zip codes and names and may be used
manually or semi-automatically is not an easy task. In order as slot types for the concepts of the “Thing” sub-hierarchy.
for such an ontology to be truly personal, it should be able Instances of these concepts may serve as information items
identified automatically by a PIM or TIM application.
to reflect the user individuality, but, it should do so in the
context of a specific general model that will enable Class “Thing” (Figure 2) contains both abstract and tangible
exchange of information between users and will be usable things, which may be objects, living organisms and
by computers. This is the main reason why the personal concepts. Classes “Interest Type” and “Preference Type”
ontology model we propose encompasses a basic core of model interest and preference hierarchies as the ones
general concepts that may be enriched to accommodate suggested in [12] and [13]. Class “Self” (highlighted in Fig.
several user stereotypes or individual profiles. The addition 2), a direct subclass of “Person”, models the profiled user.
of new classes may be accomplished both at the ontology
designer and the end user level. The ontology has been modeled using Protégé [7], a widely
used open source ontology management tool with a well-
Details on the creation of the personal ontology may be defined API for creating plug-ins. To this end it was
found in [6]. The version of the personal ontology used in selected for the implementation and testing of the spreading
this work is an extension of the one in [6], as it has been activation algorithm over the personal ontology. The
enriched with more user-related classes for the user following section describes human memory theories on
stereotype of “Researcher” in order to be used for the fine which our work has been based, along with a brief example
tuning and evaluation of the spreading activation algorithm. of spreading activation.
The ontology, along with example instances may be found
in [8]. Figure 2 presents an overview of the upper levels of SPREADING ACTIVATION IN THE HUMAN BRAIN AND
the class hierarchy. IN ONTOLOGIES
The personal ontology attempts to encompass a wide range Different Timescales of Human Memory
of user characteristics, including personal information as The human memory operates on multiple timescales.
well as relations to other people, preferences and interests. According to the model that Atkinson and Shiffrin proposed
The ontology may be extended through inheritance and the in 1968 [4], there are two distinct memory stores:
addition of more classes, as well as concept instantiation · Short term memory– the things we are currently
according to the needs of user stereotypes or individuals. thinking about. This is short lived (10-30 secs) unless it
The personal ontology classes are divided in two main is constantly rehearsed.
groups, which comprise the two upper levels of the
· Long term memory – the things we have learnt and
ontology, “Value class” and “Thing” (Figure 2).
stay with us for years (possibly forever), but may be
“Value Class” contains a description of information items more or less easy to retrieve.
that are more complex than simple data types but are not
Short term memory is held in patterns of electrical activity
self-contained enough to be included in the ontology as
whereas long term memories are formed by actual synapse
growth. However, there are things that stay around longer and Vivi both work for UoA which is in Athens, Greece
than the 10-30 seconds of the short term memory, but are and George works for UoP which is in Tripolis, Greece.
related to the current moment and task. These include the
Suppose that there is some sort of initial reason for focusing
context of “what am I doing now” as well as recent episodic
on Vivi, perhaps she has been selected by the user for
memory of “what has happened in the last few minutes”.
interaction or has appeared in a recent email. Vivi is
This in-between or 'mezzanine' memory is not well dealt
therefore given a high initial activation level. The entities
with in the literature as it is too 'fast' for neuron growth. It
directly connected to Vivi (in this case Costas and UoA) are
may be in part due to more maintained electrical states or
then also given activation, less than Vivi’s though. Because
chemical changes in neurons called long term potentiation
UoA receives activation entities connected with it, in
or LTP, which are known to last for anything from seconds
particular the City it is in, Athens, are given a small share of
to hours.
its activation. This then further spreads to Greece, the
schema country in which the City of Athens is situated.
m 1 m 1 m 1
Person Univ City Country
This activation will also flow backwards through relations
Long term modification of
schema relation weights
so that Tripolis becomes activated because Greece is, and
so on. When activation spreads through a 1–m relation it
Spreading activation
through relations
will be weaker than through an m–1 relation, as there are
Vivi many things to which it is spreading. Also note that some
e UoA
entities may receive activation through multiple routes. For
initial
activation Costas
Athens
example, UoA receives activation because it is the place
through use Greece Costas works as well as because of its direct link to Vivi.
UoP
This may then lead to cycles of activation, hence the
Tripolis importance of 'throttling' the spread of activation where
George there is large fan out (as in 1–m relations).
Weaker spreading through
instances 1-m links than m-1 Some relations may be deemed more important than others
and hence given a weighting in the schema, which can then
Figure 3. An example of spreading activation over the
be used when computing the activation spread. In addition,
personal ontology
over time these could be adjusted so that where entities in
The spreading activation theory [1] has proven to provide a either side of a relation are often active together the relation
model with a high degree of explanatory power in cognitive may grow in weight. The amount of activation an entity
psychology [2]. The main advantage of this model is that it receives is also related to (1) if the entity was activated by
captures both the way knowledge is represented and also an external factor (i.e. being detected in an e-mail), (2) if
the way it is processed. According to this theory, the entity was recently active (i.e. detected very recently in
knowledge in the long term memory is represented in terms the user’s tasks), (3) if the entity has long term importance
of nodes and associative pathways between nodes, which to the user.
form a semantic network of concepts. A hierarchical
structure is also present in this network, classifying The result of the spreading activation will be a set of
concepts in more generic and more specific ones [2]. entities that have been found relevant to the user’s current
task and therefore given priority during the task inference
Connection strength and node distance are determined by stage. The context inference module, based on spreading
the semantic relations or associative relations between the activation, has been inspired by the human memory
conceptual nodes. This model assumes that activation spreading activation model, which is briefly presented in
spreads from one conceptual node to those around it, with the following section.
greater emphasis to the closer ones [3].
DIFFERENT TIMESCALES FOR TASK-BASED
An Example of Spreading Activation through the INTERACTION
Personal Ontology In user interaction with a system multiple timescales can be
To provide a clearer view of the use of spreading activation noted, which roughly correspond to the ones apparent in the
over the personal ontology, consider Figure 3. It presents an human memory model. First, there are the contents of the
ontology schema with classes for Persons, Universities, personal ontology and the available information sources
Cities and Countries and a number of relationships that roughly correspond to human long-term memory. Not
(unlabelled, but all obvious except that the Person to Person all things in this long-term system memory are equally
relationship is PhD supervisor). important and it should be recorded that some things (such
as the user's own address) are more important than others
In the lower part of the figure are a number of instances on
(the address of the plumber). Corresponding to the
the classes and their relationships: from the class Person the
instances Vivi, Costas and George have been added to the short/working memory are the things the system has to
personal ontology. Costas supervises Vivi’s PhD. Costas store regarding the current user task – for example, the
contents of the email the user has just opened, the text the OntologyState º OS Ì S
user has just selected, the web page just visited, or the form
field being completed. Finally, there are the things the user An activation state over such an ontology is then an
has been recently doing (other pages visited, documents activation level (real number) assigned to each entity:
seen, etc.) that roughly correspond to the mezzanine ActivationState: E ® R
memory. This recent history is important as, for example, if
the user has recently viewed a web site about an upcoming The set of all possible activation states over an entity set E
event and then goes to a travel website it is likely that the will be denoted as AS(E). We will refer to the three time
place to be visited is that of the event. scales of system activation as STA, MTA and LTA. STA
(Short Term Activation) refers to things that are currently
These different levels could be dealt with in a spreading active, MTA (Medium Term Activation) to things that have
activation framework by simply fading memories over time been recently active (and most probably still are), whereas
so that entities frequently encountered become increasingly LTA (Long Term Activation) to things that are important to
highly 'activated'. However, with a single mechanism it is the user in the long term. There is also a 'trigger' activation,
hard to create a balance between having recent things be IA (Immediate Activation), corresponding to the things that
more active (the place just mentioned in an email) than are in some way important directly due to the current
important general things (the user’s address), whilst on the task/interaction; for example, the things that are in the
other hand not having them crowd out the longer-term currently viewed e-mail or web page.
things.
STA, MTA, LTA, IA Î AS(E)
Because of this it seems more appropriate to explicitly code
these different levels using multiple activations with 'rules' Also we assume that each relation, r, has a long-term
for passing activation between short-term to longer-term weight LTW(r) that is initialized according to the
memories. The simplest such rule would be to define cardinality of the relationship (1-1, 1-m, m-1, m-n).
thresholds so that if the short-term activation exceeds some The basic steps of the algorithm may be summarized as
value then the medium-term activation is incremented and follows:
similarly if the medium term memory exceeds its own
threshold (signalling that something has been repeatedly of 1. Initialize appropriate weights and activations
high relevance), then the long-term activation grows. In 2. Create a set with the currently active entities (entities e
addition, certain events (e.g. explicitly interacting with an with IA(e) > 0), Active Set
entity) may be regarded as sufficiently important to increase
the long-term memory directly (just as significant events 3. Repeat:
are easily remembered). Compute STA(e) for the entities in the Active Set
The following section presents the algorithm and as well as their related ones
implementation inspired by the human memory model For the related entities whose STA exceeds a
through spreading activation on the personal ontology threshold, place them in the Active Set
Spreading Activation Algorithm Until
The spreading activation through the personal ontology
4. Update MTA and LTA activation weights if appropriate
algorithm assumes, to avoid repetition in the formulae, that
the inverse of each relation is explicitly recorded in the We envision that the spreading activation algorithm will be
ontology schema. For a real schema this means that all triggered after each “event” in a PIMS system. With the
qualifiers would have to range over relations and their term “event” in this case we refer to a user action that has
inverses. Also the weight (strength) of a relation is resulted in the identification of ontology entities related to
directional, so that there is a difference between the weights the current action. For example, the user opens an e-mail,
depending on which direction the relation is traversed. and in it the sender name has been detected as well as the
Again to simplify the formulae, property values will be name of a research project the user currently participates in.
ignored. Bearing this in mind, the following sections present in
details the algorithm steps.
Given this we have a set of relations L, of entities
(instances) E and instances of relationships (statements) S.
Updating Short Term Activation
Every statement is a relation between specific entities: Given a particular state of the STA, each entity e has an
S=Lx Ex E incoming activation IN given by
So a typical statement is of the form r(e1,e2), where r is a IN(e) = å LTW’(r) ´ STA(e'), r Î R Ù $ e' Î E: r(e, e' )
relation and e1 and e2 are instances. Î OntologyState
The current state of the ontology is then simply a set of
statements:
The value of LTW’(r) is in fact the relation LTW value As a result, for the needs of our implementation of
divided by the number of entities e' is related with through spreading activation we opted for constrained spreading
this relation, i.e. the “fan out” of the relation. activation, also suggested in [10]. We feel that this variation
of the algorithm is closer to the human memory spreading
The formula for the STA then becomes:
activation process where the finite rate of firing and tome
STA(e) = f (IA(e), IN(e), MTA(e), LTA(e)) available means that only a limited number of 'steps' are
taken. To this end, we apply spreading activation on the
The function will typically count IA strongly, and only take ontology for a specific number of iterations. Futrhermore, if
into account MTA and LTA where either IA or IN(e) is
the personal ontology is a 'small world' then it may be that
non-zero. For example, a possible function might be:
activation can in principle spread across the network in a
f(ia, in, mta, lta) = (A ´ ia + B ´ in) * (1 + ( C ´ mta + very few iterations, before feedback loops become too
D ´ lta)) powerful. The optimum number of iterations is still an issue
for experimentation and it is directly related to the needs of
The non-linear term means that long- or medium-term the specific application as well as the ontology weights and
activation are not in themselves sufficient to cause short- parameters.
term activation, but do strengthen the effect of STA.
The result of the STA update function is passed through a Updating Medium and Long Term Activation
1 At the end of the spreading activation cycle, MTA and LTA
sigmoid function ( S ( sta ) = ) to emphasise the
1 + e - sta are updated.
difference between large and small activations and to cap We simply increment MTA if the STA exceeds a value:
the largest.
if (STA(e) > threshold STA) MTA'(e) = MTA(e) + dMTA
The equation for STA is recursive and is applied on the set
of activated entities of each step. And similarly for LTA:
if (MTA(e) > thresholdMTA) LTA'(e) = LTA(e) + dLTA
Spreading Activation Termination Conditions
For the number of iterations during the spreading activation However, there are several issues to consider here. One is
algorithm step for STA computation, two options have been the exact values of dMTA and dLTA. Furthermore, each entity
considered: MTA and LTA apart from being incremented when active,
1. Full Spreading of Activation: Repeat spreading it should also be decayed when inactive. This gradual decay
computations for the whole ontology, until it reaches a should reflect the fact that memories tend to fade or become
stable state. less readily accessible when they fall into disuse for a
sufficient period of time. Due to the differences of medium
2. Constrained Spreading of Activation: Repeat for a and long term activations, however, their update
specific number of iterations. mechanisms should be examined separately.
The first option was not selected for a number of reasons
MTA Increase and Decay
Firstly, bearing in mind that a personal ontology serving as
MTA expresses the number of things that are recently and
memory aid for a user may contain thousands of instances,
currently “active” and may involve the user’s current tasks.
applying spreading activation on the whole ontology would
This suggests that the total amount of MTA weights in the
not be very efficient, especially in applications like task
ontology should remain relatively steady, in order to reflect
information management where access to the ontology is
the fact that the user’s divided attention among many tasks
very frequent.
(and, subsequently, entities), results in less attention paid to
Furthermore, the existence of cyclic paths in the ontology each particular task/entity.
graph means that the spreading activation process won’t
To this end, we define a constant, MaxMTATotal, which
end because of the loops. A way to go around this would be
represents the maximum value for the sum of all MTA
to detect already visited entities and avoid loops by not
weights in the ontology.
spreading activation to them again. However, this could be
a problem as well, as an entity may be related to more than The decay of MTA is accomplished with the following
one active entities. For example, an entity e1 may receive process:
activation from the directly connected to it e2 during the
Every T steps:
first iteration step and from the entity e3 that is related to e1
through e4 during the second iteration step (e1à e2 and 1. The total amount of MTA increase over the T steps,
e1à e4 à e3). So excluding already visited entities has sMTA, is recorded
also been rejected.
2. We set λMTA = sMTA / MaxMTATotal as the decay
factor
3. For every entity e, the new MTA is computed: (2) Weights on the precise instance of a relation, that is for
MTA'(e) = (1 – lMTA) * MTA(e) a specific e1, e2 with a relation r between them, we
could assign a weight dependent on:
The frequency of the MTA decay as well as the maximum
total of MTA weights should be adjusted according to the (a) Whether the relation was important in spreading
needs of the specific application. For a TIM system MTA activation
probably should be updated after each “event”.
(b) Whether both e1 and e2 have received high
In special cases when IA on its own exceeds some value or activation
was caused by some specific effect, MTA could be (3) Weights on the relation for an individual entity, that is
increased directly.
given an entity e1 for the specific instance of the
relation r in e1, the LTW’ is computed as the relation
LTA Increase and Decay
LTW/k, where k is the relation fan-out for the specific
LTA reflects the long term importance of entities: it
entity, i.e. the number of entities with which e1 is
represents the fact that some things have been important to
connected through the specific relation r.
the user several times in the past. Even if currently or in the
recent past they may not have been active, they most For the moment, the spreading activation algorithm has
probably will be again in the future. Entities like the user’s been implemented with the third option for LTW weights.
address or parents can never be entirely forgotten. As an example, if we look at the class-students relationship,
then if a particular class has many students we may want to
As a result, when decaying LTA weights, it should be made
reduce the spread accordingly, closer to an activation
sure that the decay does not result in important things
budget model where if a node has so much activation it
having their LTA weight value gradually returning to zero.
spreads some of it to other nodes, but has to share amongst
A way to accomplish this is to make sure that the LTA of
the ones connected to it. A model of this form could
an entity never decays to less than a percentage (n%) of its
penalise well-connected entities (which are likely to be
maximum value.
central and generally important ones), but without some
We define as maxLTA(e) the maximum LTA value an bias of this form such entities might just become 'fixations'
entity e has ever received Furthermore, we define two of the ontology.
constants, λLTA as the decay constant that depends on the
A well-connected entity bound to be a fixation in the
time interval between each decay and minPerc as the
ontology is the instance of “Self”, which represents the user
minimum percentage of the entity maxLTA value that the
in the ontology. As this is the user’s personal ontology, it is
LTA of an entity may reach when decayed. The LTA decay
natural for it to be the best-connected one, a focal point
is computed using the following process:
related to almost all entities in the ontology. This special
At the designated time points, for every entity e: characteristic of the “Self” instance affects the spreading of
activation, so it has been treated as a special case and we
if (LTA(e) > maxLTA(e)) {maxLTA(e) = LTA(e)}
have experimenting both with its inclusion and exclusion
minLTA_e = minPerc * maxLTA(e);
during the execution of the spreading activation algorithm.
if (LTA(e) > minLTA_e ) {
delta_e = λLTA * (LTA(e) - minLTA_e) Working with weights on relation instances remains an
LTA’(e) = LTA(e) - delta_e open issue that requires further research, as it is not yet
} clear what would their interaction would be with LTW
An issue here is the definition of the time interval between weights.
consecutive decays. For the moment, events are considered
As a final point, LTW weights could also be adjusted to
as a time unit in order to measure the passage of time. The
reflect the fact that if it appears that usually when an entity
LTA decay time intervals in a TIM application should take
is active so are all those it is related to through a particular
into account other factors like the real time elapsed and the
relationship r, then this would suggest that that relationship
computer usage time elapsed.
should be given a higher weight.
LTW and Relation Weights IF foreach e Î dom(r),
(i) MTA(e) > thresholdR1
Relation weights are a very important issue in the spreading AND
activation framework.
(ii) for most e': r(e, e') Î OntologyState, MTA(e') >
Three levels of relation weights may be distinguished: thresholdR2 ´ MTA(e)
THEN
(1) The relation as a whole, which is expressed by the
increase LTW(r)
relation Long Term Weight – LTW.
However, this needs to be applied with some care as it is a
positive feedback loop – stronger LTW leads to stronger
incoming activation and hence makes it more likely that
related things are active together, further increasing the 3. All slots should conform to a meta-slot with an LTW
LTW of the relation. Until the exact implications of LTW slot of type String.
update have been identified, it has not been included in the
As an example, the personal ontology in [8] may be used.
spreading activation algorithm.
The plug-in offers the possibility to include or exclude the
LTA, STA and MTA Initialization
“Self” instance at will in the execution of the spreading
activation algorithm, by appropriately setting or clearing a
For the spreading activation algorithm to yield useful and relevant checkbox.
meaningful results, there are two very important factors.
The first is a rich personal ontology and the second the
correct weight and parameter adjustment and initialization. Preliminary Evaluation
For testing the algorithm and after preliminary As a first step, we asked a researcher of our group to aid us
experimentation, we concluded at a set of default values for in evaluating the plug-in. The researcher was asked to
these parameters and weights. These are set as default populate his personal ontology with instances relevant to
values in the Protégé plug-in for the evaluation of the his work and computer-related activities in general for the
algorithm, described in the following section. It is obvious past six months.
that a different set could be used according to the needs of
the application that would use the algorithm.
PRELIMINARY EVALUATION
In order to fully evaluate the spreading activation
algorithm, it should be integrated in a TIM prototype and
observe its effectiveness in the working environment of the
user. For the moment, in order to achieve the fine-tuning of
the algorithm parameters and locate problems and flaws, a
testing platform has been created in Java in the form of a
plug-in for the Protégé ontology editor [7].
This section presents the evaluation platform as well as the
results of the preliminary evaluation.
Figure 4. Part of the plug-in window showing the STA, MTA
and LTA values for the entities that received STA activation
The ActiveOnto Protégé Plug-in value greater than 12, when entity “Alan Dix” got IA = 1.
The ActiveOnto plug-in allows the initialization and setting Then, we asked him to go through his e-mail for the same
of all the algorithm parameters and allows the user to duration and for each e-mail to set in the plug-in the IA
simulate the functionality of the algorithm in a PIM/TIM activation of the instances that appeared in the e-mail and
system. update STA, MTA and LTA weights.
In the plug-in the user may select instances as “Immediately Although the STA update seemed to generally produce
Active”, simulating thus their appearance in an e-mail, relevant concepts and with meaningful activation values,
document or web page. Then, by pressing the “update” the update of the MTA and LTA weights showed that using
button, the STA, MTA and LTA activations are computed the e-mail in this way did not produce interesting results
and the user may view the instances that received an STA concerning these two weights. This is to be expected, as the
value greater than a specific user-defined threshold (Fig. 4). e-mails constitute a series of, most of the time, irrelevant
The plug-in may be found in [24] along with its installation “events”. Consequently, entities unrelated to one another
instructions. In order for the plug-in to function, an followed in succession, resulting in constantly increasing
ontology with specific characteristics must be used, as slots and decreasing MTA values that never surpassed the
representing the activation weights are needed. More appropriate threshold for increasing the LTA weight.
specifically, the ontology to be used with the plug-in should These results have lead us to construct more realistic usage
have the following characteristics: scenarios than going through a continuous series of e-mails.
1. All classes should conform to a meta-class having the We have decided to proceed with another non-formal
slots IA, IN, STA, MTA, LTA and MAXLTA of type evaluation that would be more task-oriented. This
String. evaluation procedure is currently being designed.
2. All instances should have the slots IA, IN, STA, MTA, RELATED WORK
LTA and MAXLTA of type String. Spreading activation is not a new concept in semantic
networks related research. There is a number of proposed
applications of spreading activation, especially in the area the existence of weighted relations to be defined as slot
of information retrieval [11]. types [26]. At the moment, the incorporation of these
weights in the algorithm is being investigated, in order to
Crestani [19] proposes the use of spreading activation on
decide if they offer some added value to the algorithm
automatically constructed hypertext networks in order to
effectiveness
support web browsing. In this case, constrained spreading
activation is used in order to avoid spreading through the LTW update. The LTW relation weights are at the moment
whole network, as is the case with our implementation. Liu static. Their update according to occurring events and/or
et al [18] use spreading activation on a semantic network of connected entities’ STA, MTA and LTA variations, is being
automatically extracted concepts in order to identify investigated.
suitable candidates for expanding a specific domain
Automatic tuning of spreading activation parameters,
ontology. Xue et al [19] propose a mining algorithm to
e.g. automatic alteration for the number of iterations.
improve web search performance by utilizing the user click-
through data. Weighted relations between user queries and Dealing with topics/contexts – People often do two
selected web pages are created and spreading activation is interleaved –but not relevant to each other– tasks nearly
performed on the resulting network in order to re-rank the simultaneously, e.g. someone works on a project and opens
search results of a specific query. a window to see the latest football news. The task inference
mechanism should be extended to recognize such cases and
Hasan in [20] proposes an indexing structure and
produce two distinct and specific tasks, instead of a single
navigational interface which integrates an ontology-driven
task consisting of irrelevant activities
knowledge-base with statistically derived indexing
parameters, and the experts' feedback into a single Results of the preliminary, informal evaluation of the
spreading activation framework to harness knowledge from algorithm have shown it to be effective in inferring the
heterogeneous knowledge assets. context of user tasks. A more effective and thorough task-
based evaluation is being designed in order to evaluate the
Neural networks and in particular Hopfield Networks [9]
update of MTA and LTA weights. However, in order to
attempt to approach and simulate the associative memory
fully evaluate the algorithm, it should be incorporated in the
again by using weighted nodes but at a different level. In
PIMS prototype under development. There are various
this case, the individual network nodes are not separate
issues relevant to this incorporation, such as:
concepts by themselves, but rather, in their whole, are used
to represented memory states. This approach corresponds to User interaction with the weighted ontology. Bearing in
the neuron functions of the human brain, whereas ours mind that the ontology will be a simplification of the user’s
attempts to simulate the human memory conceptual semantic network on some aspects of his/her life, his/her
network functions. contribution on defining the ontology entities and relations,
as well as fine-tuning the weights will be invaluable.
Although for an experienced user doing this directly on an
CONCLUSIONS AND FUTURE WORK
ontology editor like Protégé would not be difficult, non-
This work outlines a spreading activation over a personal expert users would have trouble coping with such an editor
ontology framework to be used in the context of a Personal interface, as well as the concept of the ontology itself.
Interaction Management System. The human brain and the Furthermore, editing the ontology would add to the user’s
theories related to the different levels of human memory work a substantial overhead. To this end, semi-automatic
and spreading activation have been the incentive of this methods for visualizing, updating and personalizing the
work. ontology along with the weights are being investigated [25].
The proposed personal ontology model along with the Representation of tasks/activities. Should ‘types’ of tasks
mechanism that implements the spreading activation will be and actual instances of things done be represented within
incorporated in the PIMS prototype currently under the ontology as concepts, just like a friend's name, or should
development to provide context inference to support user they be placed in some parallel but linked representation?
actions, as well as act as a memory supplement for the user.
Scaling – the spreading activation so far has been created
Very important for the algorithm effectiveness in and tested for a personal ontology, but the personal
identifying “active” entities that are relevant to the ones ontology may well include links to external ontologies,
appearing in the user’s current task are the parameters for even the whole web. Should we and how do we do this
updating the weights. These parameters have been fine form of reasoning over very large ontologies?
tuned to an extent through a process of preliminary testing,
but there is still work to be done in this direction. REFERENCES
There is also a number of issues to be further investigated: 1. Anderson, J. R.. A spreading activation theory of
memory. Journal of Verbal Learning and Verbal
Weights on relation instances. To this end, an extension Behaviour, 22 (1983) 261-295
for the Protégé ontology model has been created, allowing
2. Sharifian, F., Samani, R. Hierarchical Spreading of 15. Leo Sauermann. The Gnowsis Semantic Desktop for
activation, in Proc. of the Conference on Language, Information Integration, Proceedings of the 3rd
Cognition and Interpretation, Isfahan (1997), 1-10 Conference Professional Knowledge Management
3. Gazzaniga, M. S., Ivry, R. B., Mangun, G. R., Cognitive (2005)
Neuroscience, The Biology of the Mind, pp 289-294, W. 16. Paul – Alexandru Chirita, Rita Gavriloai, Stefania Ghita,
W. Norton & Company, New Ed edition (1998) Wolfgang Nejdl, Raluca Paiu, Activity Based Metadata
4. Atkinson, R.C. & Shiffrin, R.M. Human memory: A for Semantic Desktop Search, Proceedings of the 2nd
proposed system and its control processes. In K.W. European Semantic Web Conference (2005)
Spence and J.T. Spence (Eds.), The psychology of 17. A. Maedche, S. Staab, “Mining Ontologies from Text”,
learning and motivation, vol. 8. London: Academic Proceedings of EKAW 2000 (2000) 189-202
Press (1968) 18. W. Liu, A. Weichselbraun, A. Scharl, E. Chang. Semi-
5. Gruber, Thomas R., A Translation Approach to Portable Automatic Ontology Extension Using Spreading
Ontology Specifications, Knowledge Acquisition, Activation, Journal of Universal Knowledge
Special issue: Current issues in knowledge modelling, Management, vol. 0, no. 1 (2005), 50 - 58
Vol 5, Issue 2 (1993) 199-220 19. Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Wei-Ying
6. Golemati M., Katifori A., Vassilakis C., Lepouras G., Ma, Wensi Xi, Weiguo Fan, Yong Yu. Optimizing Web
Halatsis C.: Creating an Ontology for the User Profile: Search Using Web Click-through Data. (2004): 118-126
Method and Applications, Proceedings of the First RCIS 20. Hasan, Md Maruf (2003) A Spreading Activation
Conference (2007) 407-412, April 23-26, Ouarzazate, Framework for Ontology-enhanced Adaptive
Morocco Information Access within Organisations. In
7. Protégé, http://protege.stanford.edu/ Proceedings of the Spring Symposium on Agent
8. Katifori, A., Vassilakis, C., Dix, A., Daradimos, I., Mediated Knowledge Management 2003 (2003)
Lepouras, G., Spreading activation user profile Stanford University, California, USA
ontology, Available from 21. T. Catarci, A. Dix, A. Katifori, G. Lepouras and A.
http://oceanis.mm.di.uoa.gr/pened/?category=pub#ontos Poggi. Task-Centered Information Management. In
9. Hopfield, J. Neural networks and physical systems with DELOS Conference 2007 on Working Notes, 13-14
emergent collective computational properties. February 2007, Tirrenia, Pisa (Italy), C. Thanos and F.
Proceedings of the National Academy of Sciences of the Borri (eds.) (2007), 253-263
USA, 79 (1982), 2554 - 2588 22. G. Lepouras, A. Dix, A. Katifori, T. Catarci, B.
10. Crestani, F. Retrieving documents by constrained Habegger, A. Poggi, Y. Ioannidis (2006). OntoPIM:
spreading activation on automatically constructed From Personal Information Management to Task
hypertexts. In Proceedings of EU- FIT 97- Fifth Information Management, Personal Information
International Congress on Intelligent Techniques and Management, SIGIR 2006 workshop, August 10-11,
Soft Computing, pages (1997), 1210-1214, Aachen, (2006), Seattle, Washington
Germany 23. T. Catarci, B. Habegger, A. Poggi, A. Dix, Y. Ioannidis,
11. Crestani F. Application of spreading activation A. Katifori, and G. Lepouras. Intelligent user task
techniques in information retrieval. Artificial oriented systems. In In Proc. of the Second SIGIR
Intelligence Review, 11(6) (1997), 453–482 Workshop on Personal Information Management (PIM
2006), 2006
12. J. Trajkova, S. Gauch. Improving Ontology-based User
Profiles, Proc. of RIAO 2004, University of Avignon 24. Katifori, A., Dix, A., Vassilakis, C., Spreading
(Vaucluse), France, April 26-28 (2004), 380-389 activation Protégé plugin, available from
http://oceanis.mm.di.uoa.gr/pened/?c=pub#plugins
13. S. Gauch, J. Chaffee, A. Pretschner. Ontology-Based
User Profiles for Search and Browsing, User Modeling 25. A. Katifori , E. Torou, C. Halatsis, G. Lepouras and C.
and User-Adapted Interaction: The Journal of Vassilakis, A Comparative Study of Four Ontology
Personalization Research”, Special Issue on User Visualization Techniques in Protégé: Experiment Setup
Modeling for Web and Hypermedia Information and Preliminary Results, Proceedings of the IV 06
Retrieval (2003) Conference (2006)
14. V. Katifori, A. Poggi,. M. Scannapieco, T. Catarci, & Y. 26. C. Vassilakis, G. Lepouras, A. Katifori, wt-Protégé – An
Ioannidis. OntoPIM: how to rely on a personal ontology Extension for Protégé Supporting Temporal and
for Personal Information Management, In Proc. of the Weighted Data, Technical Report TR-SSDBL-07-001,
1st Workshop on The Semantic Desktop (2005) (2007), http://wt-protege.uop.gr