Recent research in the domain of Personal Information Management has recognized the need for a paradigm shift towards a more activity-oriented system. Ontologies, as semantic networks with a structure not dissimilar to the one used by the human brain for storing long-term knowledge, may be very useful as the basis of such a system. This work proposes the use of spreading activation over ontologies in order to provide to a task-based system and its associated tools with methods to record semantics related to documents and tasks and to support user context inference.
INTRODUCTION As a direct result of the rapid technological progress of the last few decades, personal computers have become repositories for company information and scientific data, documents, electronic mail as well as personal collections of media, like photographs, video or music. Computer users, however, in order to take advantage of this memory complement offered to them, have to invest more and more time into managing and organizing their collections and repositories because, if they don’t, retrieving information from them when necessary will be nearly impossible. Furthermore, in current computer systems the user interaction paradigm is based on functionally defined applications (word processing, address management, internet browsing) and on the storage, organisation and retrieval of information in files or databases, the content types and structure of which are determined by the units of operation of the applications. However, real activity, whether for work or leisure, crosses application boundaries, may involve portions of files, and interlinks fragments of both. Users should not have to focus on managing their information but rather on performing the tasks this information is to be used for.
Recent research in the domain of Personal Information
Management (PIM) and Task-centered Information
Management (TIM) has recognized the need for a paradigm
shift towards more task- and activity-oriented systems [
This work explores the application of the spreading
activation theory of the human memory [
TOWARDS A PERSONAL INTERACTION MANAGEMENT SYSTEM The motivation of our work on personal ontologies and spreading activation has been the vision of more activitycentric computing and the general aim of moving from systems focusing on the management of personal information (i.e. PIM) to systems focusing on the management of personal interaction. We define Personal Interaction Management System (PIMS) to be a system that supports the user in executing tasks in an interactive and efficient way, providing at the same time effective and transparent mechanisms for maintaining the user’s personal document collection.
In order for a PIMS to be effective, it should provide effective mechanisms for user profiling, semantic storage of documents and context inference. Figure 1 shows a sketch view of the main components a PIMS must include to support this functionality. The information side (documents, emails etc.) is linked to the computation side (actions) through two main components: 1. A recogniser finding suitable fragments of the raw information that are semantically meaningful and that can be used to initiate or feed into actions 2. A personal ontology that contains knowledge specific to the user (people, projects, etc.). These two feed into one another. The various terms, names, emails, etc, in a personal ontology can yield keywords to be matched against text or semi-structured sources. So an increasingly rich personal ontology will lead to better identification of suitable loci for action. Furthermore, as users perform actions the way in which they use information, the results of their activities can be used to enrich the ontology. For example, if a piece of text is used to search in a gazetteer it suggests that (i) it is a place name - that is we know more about its type and (ii) it is a place name that is important to the user - so will be suggested to be added into the personal ontology.
Both of these require inference mechanisms which sit
outside this picture, using the information from the personal
ontology and history and then feeding this in to modify the
recognition and action selection. For task inference we are
using a bottom up approach described in more detail in [
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 [
To this end, we have created an ontology for the user's personal collection domain. This ontology has been created taking into account existing profile models in applications as well as related research in the area of profiling. Creating a personal ontology, either automatically, manually or semi-automatically is not an easy task. In order for such an ontology to be truly personal, it should be able to reflect the user individuality, but, it should do so in the context of a specific general model that will enable exchange of information between users and will be usable by computers. This is the main reason why the personal ontology model we propose encompasses a basic core of general concepts that may be enriched to accommodate several user stereotypes or individual profiles. The addition of new classes may be accomplished both at the ontology designer and the end user level.
Details on the creation of the personal ontology may be
found in [
The personal ontology attempts to encompass a wide range
of user characteristics, including personal information as
well as relations to other people, preferences and interests.
The ontology may be extended through inheritance and the
addition of more classes, as well as concept instantiation
according to the needs of user stereotypes or individuals.
The personal ontology classes are divided in two main
groups, which comprise the two upper levels of the
ontology, “Value class” and “Thing” (Figure 2).
“Value Class” contains a description of information items
that are more complex than simple data types but are not
self-contained enough to be included in the ontology as
Class “Thing” (Figure 2) contains both abstract and tangible
things, which may be objects, living organisms and
concepts. Classes “Interest Type” and “Preference Type”
model interest and preference hierarchies as the ones
suggested in [
SPREADING ACTIVATION IN THE HUMAN BRAIN AND
IN ONTOLOGIES
Different Timescales of Human Memory
The human memory operates on multiple timescales.
According to the model that Atkinson and Shiffrin proposed
in 1968 [
Short term memory– the things we are currently thinking about. This is short lived (10-30 secs) unless it is constantly rehearsed.
Long term memory – the things we have learnt and stay with us for years (possibly forever), but may be more or less easy to retrieve.
Short term memory is held in patterns of electrical activity whereas long term memories are formed by actual synapse growth. However, there are things that stay around longer than the 10-30 seconds of the short term memory, but are related to the current moment and task. These include the context of “what am I doing now” as well as recent episodic memory of “what has happened in the last few minutes”. This in-between or 'mezzanine' memory is not well dealt with in the literature as it is too 'fast' for neuron growth. It may be in part due to more maintained electrical states or chemical changes in neurons called long term potentiation or LTP, which are known to last for anything from seconds to hours.
schema
Person m 1 m
1 Univ m
1 City Country Long term modification of schema relation weights
Spreading activation through relations
Athens Tripolis
Greece Weaker spreading through 1-m links than m-1 initial activation through use instances
Vivi
e Costas George
UoA
UoP
The spreading activation theory [
An Example of Spreading Activation through the Personal Ontology To provide a clearer view of the use of spreading activation over the personal ontology, consider Figure 3. It presents an ontology schema with classes for Persons, Universities, Cities and Countries and a number of relationships (unlabelled, but all obvious except that the Person to Person relationship is PhD supervisor).
In the lower part of the figure are a number of instances on the classes and their relationships: from the class Person the instances Vivi, Costas and George have been added to the personal ontology. Costas supervises Vivi’s PhD. Costas and Vivi both work for UoA which is in Athens, Greece and George works for UoP which is in Tripolis, Greece. Suppose that there is some sort of initial reason for focusing on Vivi, perhaps she has been selected by the user for interaction or has appeared in a recent email. Vivi is therefore given a high initial activation level. The entities directly connected to Vivi (in this case Costas and UoA) are then also given activation, less than Vivi’s though. Because UoA receives activation entities connected with it, in particular the City it is in, Athens, are given a small share of its activation. This then further spreads to Greece, the country in which the City of Athens is situated.
This activation will also flow backwards through relations so that Tripolis becomes activated because Greece is, and so on. When activation spreads through a 1–m relation it will be weaker than through an m–1 relation, as there are many things to which it is spreading. Also note that some entities may receive activation through multiple routes. For example, UoA receives activation because it is the place Costas works as well as because of its direct link to Vivi. This may then lead to cycles of activation, hence the importance of 'throttling' the spread of activation where there is large fan out (as in 1–m relations).
Some relations may be deemed more important than others and hence given a weighting in the schema, which can then be used when computing the activation spread. In addition, over time these could be adjusted so that where entities in either side of a relation are often active together the relation may grow in weight. The amount of activation an entity receives is also related to (1) if the entity was activated by an external factor (i.e. being detected in an e-mail), (2) if the entity was recently active (i.e. detected very recently in the user’s tasks), (3) if the entity has long term importance to the user.
The result of the spreading activation will be a set of entities that have been found relevant to the user’s current task and therefore given priority during the task inference stage. The context inference module, based on spreading activation, has been inspired by the human memory spreading activation model, which is briefly presented in the following section.
DIFFERENT TIMESCALES FOR TASK-BASED INTERACTION In user interaction with a system multiple timescales can be noted, which roughly correspond to the ones apparent in the human memory model. First, there are the contents of the personal ontology and the available information sources that roughly correspond to human long-term memory. Not all things in this long-term system memory are equally important and it should be recorded that some things (such as the user's own address) are more important than others (the address of the plumber). Corresponding to the short/working memory are the things the system has to store regarding the current user task – for example, the contents of the email the user has just opened, the text the user has just selected, the web page just visited, or the form field being completed. Finally, there are the things the user has been recently doing (other pages visited, documents seen, etc.) that roughly correspond to the mezzanine memory. This recent history is important as, for example, if the user has recently viewed a web site about an upcoming event and then goes to a travel website it is likely that the place to be visited is that of the event.
These different levels could be dealt with in a spreading activation framework by simply fading memories over time so that entities frequently encountered become increasingly highly 'activated'. However, with a single mechanism it is hard to create a balance between having recent things be more active (the place just mentioned in an email) than important general things (the user’s address), whilst on the other hand not having them crowd out the longer-term things.
Because of this it seems more appropriate to explicitly code these different levels using multiple activations with 'rules' for passing activation between short-term to longer-term memories. The simplest such rule would be to define thresholds so that if the short-term activation exceeds some value then the medium-term activation is incremented and similarly if the medium term memory exceeds its own threshold (signalling that something has been repeatedly of high relevance), then the long-term activation grows. In addition, certain events (e.g. explicitly interacting with an entity) may be regarded as sufficiently important to increase the long-term memory directly (just as significant events are easily remembered).
The following section presents the algorithm and implementation inspired by the human memory model through spreading activation on the personal ontology Spreading Activation Algorithm The spreading activation through the personal ontology algorithm assumes, to avoid repetition in the formulae, that the inverse of each relation is explicitly recorded in the ontology schema. For a real schema this means that all qualifiers would have to range over relations and their inverses. Also the weight (strength) of a relation is directional, so that there is a difference between the weights depending on which direction the relation is traversed. Again to simplify the formulae, property values will be ignored.
Given this we have a set of relations L, of entities (instances) E and instances of relationships (statements) S. Every statement is a relation between specific entities:
S = L x E x E So a typical statement is of the form r(e1,e2), where r is a relation and e1 and e2 are instances.
The current state of the ontology is then simply a set of statements:
An activation state over such an ontology is then an activation level (real number) assigned to each entity: The set of all possible activation states over an entity set E will be denoted as AS(E). We will refer to the three time scales of system activation as STA, MTA and LTA. STA (Short Term Activation) refers to things that are currently active, MTA (Medium Term Activation) to things that have been recently active (and most probably still are), whereas LTA (Long Term Activation) to things that are important to the user in the long term. There is also a 'trigger' activation, IA (Immediate Activation), corresponding to the things that are in some way important directly due to the current task/interaction; for example, the things that are in the currently viewed e-mail or web page.
STA, MTA, LTA, IA Î AS(E) Also we assume that each relation, r, has a long-term weight LTW(r) that is initialized according to the cardinality of the relationship (1-1, 1-m, m-1, m-n). The basic steps of the algorithm may be summarized as follows:
2. Create a set with the currently active entities (entities e with IA(e) > 0), Active Set
Compute STA(e) for the entities in the Active Set as well as their related ones For the related entities whose STA exceeds a threshold, place them in the Active Set
4. Update MTA and LTA activation weights if appropriate We envision that the spreading activation algorithm will be triggered after each “event” in a PIMS system. With the term “event” in this case we refer to a user action that has resulted in the identification of ontology entities related to the current action. For example, the user opens an e-mail, and in it the sender name has been detected as well as the name of a research project the user currently participates in. Bearing this in mind, the following sections present in details the algorithm steps.
Updating Short Term Activation Given a particular state of the STA, each entity e has an incoming activation IN given by
IN(e) = å LTW’(r) ´ STA(e'), r Î R Ù $ e' Î E: r(e, e' ) Î OntologyState The value of LTW’(r) is in fact the relation LTW value divided by the number of entities e' is related with through this relation, i.e. the “fan out” of the relation.
STA(e) = f (IA(e), IN(e), MTA(e), LTA(e)) The function will typically count IA strongly, and only take into account MTA and LTA where either IA or IN(e) is non-zero. For example, a possible function might be: f(ia, in, mta, lta) = (A ´ ia + B ´ in) * (1 + ( C ´ mta +
D ´ lta)) The non-linear term means that long- or medium-term activation are not in themselves sufficient to cause shortterm activation, but do strengthen the effect of STA. sigmoid function ( S (sta) = The result of the STA update function is passed through a 1 ) to emphasise the difference between large and small activations and to cap the largest.
The equation for STA is recursive and is applied on the set of activated entities of each step. 1 + e -sta Spreading Activation Termination Conditions For the number of iterations during the spreading activation algorithm step for STA computation, two options have been considered:
Full Spreading of Activation: Repeat spreading computations for the whole ontology, until it reaches a stable state.
Constrained Spreading of Activation: Repeat for a specific number of iterations.
The first option was not selected for a number of reasons Firstly, bearing in mind that a personal ontology serving as memory aid for a user may contain thousands of instances, applying spreading activation on the whole ontology would not be very efficient, especially in applications like task information management where access to the ontology is very frequent.
Furthermore, the existence of cyclic paths in the ontology graph means that the spreading activation process won’t end because of the loops. A way to go around this would be to detect already visited entities and avoid loops by not spreading activation to them again. However, this could be a problem as well, as an entity may be related to more than one active entities. For example, an entity e1 may receive activation from the directly connected to it e2 during the first iteration step and from the entity e3 that is related to e1 through e4 during the second iteration step (e1à e2 and e1à e4 à e3). So excluding already visited entities has also been rejected.
As a result, for the needs of our implementation of
spreading activation we opted for constrained spreading
activation, also suggested in [
Updating Medium and Long Term Activation At the end of the spreading activation cycle, MTA and LTA are updated.
We simply increment MTA if the STA exceeds a value: if (STA(e) > thresholdSTA) MTA'(e) = MTA(e) + dMTA
if (MTA(e) > thresholdMTA) LTA'(e) = LTA(e) + dLTA However, there are several issues to consider here. One is the exact values of dMTA and dLTA. Furthermore, each entity MTA and LTA apart from being incremented when active, it should also be decayed when inactive. This gradual decay should reflect the fact that memories tend to fade or become less readily accessible when they fall into disuse for a sufficient period of time. Due to the differences of medium and long term activations, however, their update mechanisms should be examined separately.
MTA Increase and Decay MTA expresses the number of things that are recently and currently “active” and may involve the user’s current tasks. This suggests that the total amount of MTA weights in the ontology should remain relatively steady, in order to reflect the fact that the user’s divided attention among many tasks (and, subsequently, entities), results in less attention paid to each particular task/entity.
To this end, we define a constant, MaxMTATotal, which represents the maximum value for the sum of all MTA weights in the ontology.
The decay of MTA is accomplished with the following process:
The total amount of MTA increase over the T steps, sMTA, is recorded We set λMTA = sMTA / MaxMTATotal as the decay factor
MTA'(e) = (1 – lMTA) * MTA(e) MTA is computed: The frequency of the MTA decay as well as the maximum total of MTA weights should be adjusted according to the needs of the specific application. For a TIM system MTA probably should be updated after each “event”.
In special cases when IA on its own exceeds some value or was caused by some specific effect, MTA could be increased directly.
LTA Increase and Decay LTA reflects the long term importance of entities: it represents the fact that some things have been important to the user several times in the past. Even if currently or in the recent past they may not have been active, they most probably will be again in the future. Entities like the user’s address or parents can never be entirely forgotten. As a result, when decaying LTA weights, it should be made sure that the decay does not result in important things having their LTA weight value gradually returning to zero. A way to accomplish this is to make sure that the LTA of an entity never decays to less than a percentage (n%) of its maximum value.
We define as maxLTA(e) the maximum LTA value an entity e has ever received Furthermore, we define two constants, λLTA as the decay constant that depends on the time interval between each decay and minPerc as the minimum percentage of the entity maxLTA value that the LTA of an entity may reach when decayed. The LTA decay is computed using the following process:
if (LTA(e) > maxLTA(e)) {maxLTA(e) = LTA(e)} minLTA_e = minPerc * maxLTA(e); if (LTA(e) > minLTA_e ) { delta_e = λLTA * (LTA(e) - minLTA_e)
LTA’(e) = LTA(e) - delta_e } An issue here is the definition of the time interval between consecutive decays. For the moment, events are considered as a time unit in order to measure the passage of time. The LTA decay time intervals in a TIM application should take into account other factors like the real time elapsed and the computer usage time elapsed.
LTW and Relation Weights Relation weights are a very important issue in the spreading activation framework.
Three levels of relation weights may be distinguished: (1) The relation as a whole, which is expressed by the relation Long Term Weight – LTW. (2) Weights on the precise instance of a relation, that is for a specific e1, e2 with a relation r between them, we could assign a weight dependent on: (a)
Whether the relation was important in spreading activation (b) Whether both e1 and e2 have received high activation (3) Weights on the relation for an individual entity, that is given an entity e1 for the specific instance of the relation r in e1, the LTW’ is computed as the relation LTW/k, where k is the relation fan-out for the specific entity, i.e. the number of entities with which e1 is connected through the specific relation r.
For the moment, the spreading activation algorithm has been implemented with the third option for LTW weights. As an example, if we look at the class-students relationship, then if a particular class has many students we may want to reduce the spread accordingly, closer to an activation budget model where if a node has so much activation it spreads some of it to other nodes, but has to share amongst the ones connected to it. A model of this form could penalise well-connected entities (which are likely to be central and generally important ones), but without some bias of this form such entities might just become 'fixations' of the ontology.
A well-connected entity bound to be a fixation in the ontology is the instance of “Self”, which represents the user in the ontology. As this is the user’s personal ontology, it is natural for it to be the best-connected one, a focal point related to almost all entities in the ontology. This special characteristic of the “Self” instance affects the spreading of activation, so it has been treated as a special case and we have experimenting both with its inclusion and exclusion during the execution of the spreading activation algorithm. Working with weights on relation instances remains an open issue that requires further research, as it is not yet clear what would their interaction would be with LTW weights.
As a final point, LTW weights could also be adjusted to reflect the fact that if it appears that usually when an entity is active so are all those it is related to through a particular relationship r, then this would suggest that that relationship should be given a higher weight.
(i) MTA(e) > thresholdR1 AND (ii) for most e': r(e, e') Î OntologyState, MTA(e') > thresholdR2 ´ MTA(e)
increase LTW(r) 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 LTW of the relation. Until the exact implications of LTW update have been identified, it has not been included in the spreading activation algorithm.
LTA, STA and MTA Initialization For the spreading activation algorithm to yield useful and 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. For testing the algorithm and after preliminary experimentation, we concluded at a set of default values for these parameters and weights. These are set as default values in the Protégé plug-in for the evaluation of the algorithm, described in the following section. It is obvious 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 [
This section presents the evaluation platform as well as the results of the preliminary evaluation.
The ActiveOnto Protégé Plug-in The ActiveOnto plug-in allows the initialization and setting of all the algorithm parameters and allows the user to simulate the functionality of the algorithm in a PIM/TIM system.
In the plug-in the user may select instances as “Immediately
Active”, simulating thus their appearance in an e-mail,
document or web page. Then, by pressing the “update”
button, the STA, MTA and LTA activations are computed
and the user may view the instances that received an STA
value greater than a specific user-defined threshold (Fig. 4).
The plug-in may be found in [
All classes should conform to a meta-class having the slots IA, IN, STA, MTA, LTA and MAXLTA of type String.
All instances should have the slots IA, IN, STA, MTA, LTA and MAXLTA of type String.
All slots should conform to a meta-slot with an LTW slot of type String.
As an example, the personal ontology in [
Preliminary Evaluation As a first step, we asked a researcher of our group to aid us in evaluating the plug-in. The researcher was asked to populate his personal ontology with instances relevant to his work and computer-related activities in general for the past six months. Then, we asked him to go through his e-mail for the same duration and for each e-mail to set in the plug-in the IA activation of the instances that appeared in the e-mail and update STA, MTA and LTA weights.
Although the STA update seemed to generally produce
relevant concepts and with meaningful activation values,
the update of the MTA and LTA weights showed that using
the e-mail in this way did not produce interesting results
concerning these two weights. This is to be expected, as the
e-mails constitute a series of, most of the time, irrelevant
“events”. Consequently, entities unrelated to one another
followed in succession, resulting in constantly increasing
and decreasing MTA values that never surpassed the
appropriate threshold for increasing the LTA weight.
These results have lead us to construct more realistic usage
scenarios than going through a continuous series of e-mails.
We have decided to proceed with another non-formal
evaluation that would be more task-oriented. This
evaluation procedure is currently being designed.
RELATED WORK
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
of information retrieval [
Crestani [
Hasan in [
Neural networks and in particular Hopfield Networks [
CONCLUSIONS AND FUTURE WORK This work outlines a spreading activation over a personal ontology framework to be used in the context of a Personal Interaction Management System. The human brain and the theories related to the different levels of human memory and spreading activation have been the incentive of this work.
The proposed personal ontology model along with the
mechanism that implements the spreading activation will be
incorporated in the PIMS prototype currently under
development to provide context inference to support user
actions, as well as act as a memory supplement for the user.
Very important for the algorithm effectiveness in
identifying “active” entities that are relevant to the ones
appearing in the user’s current task are the parameters for
updating the weights. These parameters have been fine
tuned to an extent through a process of preliminary testing,
but there is still work to be done in this direction.
There is also a number of issues to be further investigated:
Weights on relation instances. To this end, an extension
for the Protégé ontology model has been created, allowing
the existence of weighted relations to be defined as slot
types [
Automatic tuning of spreading activation parameters,
e.g. automatic alteration for the number of iterations.
Dealing with topics/contexts – People often do two
interleaved –but not relevant to each other– tasks nearly
simultaneously, e.g. someone works on a project and opens
a window to see the latest football news. The task inference
mechanism should be extended to recognize such cases and
produce two distinct and specific tasks, instead of a single
task consisting of irrelevant activities
Results of the preliminary, informal evaluation of the
algorithm have shown it to be effective in inferring the
context of user tasks. A more effective and thorough
taskbased evaluation is being designed in order to evaluate the
update of MTA and LTA weights. However, in order to
fully evaluate the algorithm, it should be incorporated in the
PIMS prototype under development. There are various
issues relevant to this incorporation, such as:
User interaction with the weighted ontology. Bearing in
mind that the ontology will be a simplification of the user’s
semantic network on some aspects of his/her life, his/her
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
ontology editor like Protégé would not be difficult,
nonexpert users would have trouble coping with such an editor
interface, as well as the concept of the ontology itself.
Furthermore, editing the ontology would add to the user’s
work a substantial overhead. To this end, semi-automatic
methods for visualizing, updating and personalizing the
ontology along with the weights are being investigated [