Framework of a Real-Time Adaptive Hypermedia System ∗ Rui Li Evelyn Rozanski Anne Haake Rochester Institute of Rochester Institute of Rochester Institute of Technology Technology Technology 102 Lomb Memorial Drive 102 Lomb Memorial Drive 102 Lomb Memorial Drive Rochester, New York Rochester, New York Rochester, New York 14623-5608 14623-5608 14623-5608 rxl5604@rit.edu rozanski@it.rit.edu arh@it.rit.edu ABSTRACT Adaptation, Cognitive Model, ACT-R Architecture, Infor- In this paper, we describe a framework for the design and de- mation Foraging, Eye Tracking, Web Services velopment of a real-time adaptive hypermedia system. The framework leverages on the integration of conventional adap- tive hypermedia techniques and ACT-R architecture which 1. INTRODUCTION serves as the theoretical background for the cognitive model Nowadays, both the amount and complexity of information that monitors the interaction process between users and the are increasing exponentially, while the limited capability of system. The users’ information seeking skills in the hyper- information processing severely hampers humans to seek, space specified by their viewing patterns within the web gather and consume valuable information efficiently [10]. pages and access patterns between the web pages are ex- From this perspective, one of the most important studies tracted from user tracing data. The user’s viewing patterns in the information technology research field is how to maxi- are discovered by analyzing their fixation sequences with mize the allocation of human’s attention to useful informa- eyePatterns. The user’s navigation strategies in the hyper- tion rather than to simply provide people with access to the space are evaluated in terms of information foraging theory continuously-changing, chaotic, and overwhelming amount to serve as their access patterns. Both of these patterns of information. Increasingly, massive amounts of informa- are transformed into the knowledge stored in the cognitive tion have been available to the average users in the form model. Based on these interaction experiences between the of hypermedia through the World Wide Web leading to the user and the system, the cognitive model will re-arrange the need for more adaptive and personalized websites. Adaptive presented information and the structure of the hyperspace hypermedia systems, as an alternative to the conventional in real time in order to facilitate the user to acquire valuable ”one-size-fits-all” websites [6], aim to augment web users’ in- information as they perform information seeking tasks. Be- formation processing capability. The basic idea of adaptive sides the flexible adaptability, this integration leads to the hypermedia systems is that by modeling individual user’s immediate feedback to assist the users’ cognitive process to particular goals, interests and preference, the system can accomplish their information seeking tasks. The effective- tailor the content and format of the presented information ness of a conventional adaptive hypermedia system has been to meet the user’s special need in order to maximize their enhanced to a great extent. rate of gaining valuable information. Adaptive hypermedia systems can be widely adopted in many application fields, Categories and Subject Descriptors such as education [15] [13], e-commerce [9], and virtual en- H.5.4 [Information Interface and Presentation]: Hy- vironments [11]. The essential commonality is that users pertext/Hypermedia—architecture, navigation, user issues; in these application fields have to explore reasonably large H.1 [Information Systems]: Models and Principles amounts of information with diverse goals and background knowledge. General Terms The information structure of adaptive hypermedia systems Design, Human Factors consists of two interconnected spaces which are knowledge space and hyperspace. Knowledge space is a network model Keywords of the knowledge in a specific domain. The set of nodes in ∗Copyright is held by the author. SIGIR’09, July 19-23, this structured domain model refer to a set of domain knowl- edge elements which can represent bigger or smaller pieces 2009, Boston, USA. of domain knowledge depending on the particular applica- tion. The links among these nodes refer to their semantic relationships [4]. The hyperspace refers to the conventional web pages and page fragments connected by hyperlinks. The connections between these two spaces should be specified by the designers in order to assign web resources to the knowl- edge. As a crucial component, one of the most important functions of the domain model is to provide a framework to model users’ domain knowledge and their goals. The major- ity of the adaptive hypermedia systems adopt overlay model to simulate user’s knowledge. The overlay model keeps a flexible manner, but also maintains trails of the users’ infor- variable with each domain knowledge element to represent mation seeking process and cognitive states. These perfor- the estimation of user’s knowledge level about this element. mances enable the adaptive hypermedia system to tailor the The user’s goal is represented by a subset of domain knowl- displayed contents and the structure of hyperspace in ways edge elements to be learned. Currently, there is a trend in that improve the efficiency of the users’ information seeking the research on adaptive hypermedia systems, especially in behaviors. Furthermore, information foraging theory [12] the online learning application field, tries to combine intelli- provides a new point of view to consider the interaction be- gent tutoring system with educational adaptive hypermedia tween users and adaptive hypermedia systems. According to by introducing ”cognitive tutors” which are computational this theory, humans can be viewed as informavores who ac- process models into adaptive hypermedia systems [5]. In the tively seek, gather, and consume information in the culture representative studies [15] [8], researchers integrated simple environment in the same way as creatures like carnivores or production systems with their adaptive hypermedia systems herbivorous seek, gather, and consume food in the physi- to guide the users’ interaction with the systems. Besides the cal environment. In this sense, how to adapt the presented student model and goal model, these production systems can information to augment users’ specific interests and needs be considered as an adaptation model. Although just in its can be converted into an optimization problem. We can premature state, these adaptation models’ effectiveness is evaluate and make sense of the user’s information seeking relatively significant. This research trend partially inspired behaviors by extracting their viewing patterns within web our study. pages and navigation strategies between web pages in order to transform these patterns into the knowledge needed by There are two major problems in the state-of-the-art adap- the ACT-R model. It should be emphasized that compared tive hypermedia relating to user modeling and adaptation to some previous attempts that focused on the learning field, technologies. From the cognitive psychology point of view, our system aims at more general applications. the commercial platforms only provide a simple way of per- sonalization and adaptation. Since the user model of the cur- rent adaptive hypermedia systems is no more than a record 2. SYSTEM OVERVIEW The overall structure of our real time dynamically adaptive of a particular user’s accumulative history visits, it fails to hypermedia system is shown in Figure 1. In this structure, include some vital cognitive components that have a great both the adaptive hyperspace and the domain knowledge effect on users’ task performing process, particularly short- space are components of the conventional adaptive hyper- term memory, visual attention and misconception. As long media system. The user tracing model is responsible for ob- as all these cognitive factors are treated appropriately, the serving and recording the interaction between users and the adaptive hypermedia system can facilitate users’ informa- system to do further analysis. Eye tracking equipment and tion seeking behaviors more efficiently. web logging software are used in this model to collect the eye movement data and the log record data respectively. Sub- Another problem hindering the further development of adap- sequently, the users’ viewing patterns extracted from their tive hypermedia systems is the lack of people with different fixation sequences within each web page will be analyzed by expertise involved into the process of arranging personalized eyePatterns [16], and their access patterns are also compiled adaptive experiences to collaborate to achieve a good quality from the log records to serve as their navigation strategies solution. Many adaptive hypermedia systems only serve as between these web pages. ACT-R Model is used to learn prototypes or research experiments without practical value. and store the users’ information seeking skills in order to Consequently, how to integrate users’ experiences into the direct the adaptation of the system to facilitate the users to hypermedia to direct the systems’ adaptation and personal- acquire valuable information. ization is still a challenge. As the production systems were combined into the adaptive hypermedia systems, the sys- The user tracing model is responsible for evaluating the ob- tem’s effectiveness has been enhanced by providing real time served data from the users. These evaluations serve as the feedback. However, these production systems are essentially users’ skills to be learned by ACT-R model in the form of committed to a particular use. This feature severely con- declarative knowledge and procedural knowledge. Based on strains the system’s ability to acquire users’ knowledge in a the observation data from user tracing model, the procedu- flexible form. ral rules stored in ACT-R model are activated to adapt the content and form of presented information dynamically to To solve these problems, we propose a computational process users’ behaviors and provide necessary feedback in real time. model built on ACT-R cognitive architecture as an embed- The advantage of the ACT-R cognitive model is that it pro- ded assistant to help users perform their tasks by adapting vides means of applying the psychological rules known from the hyperspace dynamically and providing real-time feed- the users’ cognitive behaviors to the adaptation of the inter- back. ACT-R cognitive architecture [2] aims to provide spec- face, thereby improving the system’s quality and usability. ification about human cognition. As an integration of vari- ous components of human cognition, ACT-R serves as a the- Our system’s adaptive behavior consists of two levels: adap- oretical foundation to constructing cognitive models in order tive presentation and adaptive navigation support. Adap- to produce coherent human behaviors in different environ- tive presentation refers to adapting the content of a web ments. As the basic components of ACT-R architecture, the page to the user’s goals and knowledge background. In our interaction between declarative knowledge and procedural system, the information fragments presented within a web knowledge enables our ACT-R model not only extends the page correspond to several Areas of Interest (AOI). Each of conventional adaptation systems by providing a mechanism the AOIs contains a piece of information corresponding to to acquire users’ knowledge and skills in a more rapid and the domain knowledge elements in the domain knowledge reorganize the structure of the website in real time. This algorithm not only identifies the set of web pages that are evaluated to be the most valuable to the user’s task, but also provides criteria to re-organize the structure of hyperspace. In [7], the log data shows that users spend shorter time on an index page choosing a link or topic and much longer time on a content page that they desire to read more thoroughly. We will extend this approach to distinguish index pages from content pages dynamically. In our model, the distinction between index pages and content pages is meaningful as long as it is defined for a specific user’s navigation to perform a Figure 1: Overall System Structure. specific task in the website. Moreover, besides the time spent between content pages, the time spent within a content page space. The adaptive behaviors at the adaptive presentation is considered to evaluate the efficiency of the user access level refer to hiding the AOIs which are assessed to be irrel- pattern. evant to the tasks from the users and using an alternative way to present the displayed AOIs to emphasize their dif- According to information foraging theory, information pre- ferent priorities to the user’s task. The adaptive navigation sented in the culture environment is clustered into a set of support is done in two ways: direct guidance which means patches, and each patch diffuse unique information scent. In the system highlights one of the links on the web page to our hierarchical structure hyperspace, the information dis- indicate that this is the best link to follow, and web page played in each content page is viewed as one information sorting which means that the system sorts all the web pages patch. Consequently, the time taken by the users in a spe- according to the relevance evaluation stored as knowledge cific navigation to view the content page corresponds to the in our cognitive model: the more relevant the link is to the time spent within the patch, and the total time taken by user’s goal, the closer to the top in the hierarchical structure the users in a specific navigation to get to the content page of hyperspace. is defined as the time spent between information patches. Essentially, the time spent between content pages is defined as the sum of two parts. The first part is the time spent to 3. METHODOLOGY choose links within index pages. The second part is defined 3.1 User Tracing Model as the total time taken by the user to download a series of The user tracing model consists of two operational mod- web pages at different depths in the hierarchical structure of ules: monitoring module and pattern extraction module. the hyperspace. Accordingly, the information scent for each The monitoring module plays a role as a visual sensor to of the links in the web page is specified by the activation percept the users’ interactive actions on the interface with level of the related chunks in the ACT-R model. Informa- eye tracking equipment and web log software. Pattern ex- tion diet refers to the user’s selection of links to follow in traction module is capable of evaluating and recording the order to gather valuable information efficiently [12]. The observed user’s information seeking behaviors specified by importance of information scent is that it is used by the two patterns which are the users’ viewing patterns within a users to assess the value of information gained per unit cost particular web page and the users’ access patterns between of processing the source. Based on these scent-based evalu- the web pages. ations, the users are able to decide which links to follow so as to maximize the information diet. According to this, the The patterns will be mapped into the set of production rules rate of gain of valuable information per unit cost equals to which actively detect these inputs in ACT-R model. These the ratio of the total amount of valuable information that is rules update the declarative memory to contain chunks that necessary to be accessed for a particular task and the total represent the perceived behaviors which allow the system amount of time cost within the content pages and between to adapt its displayed contents and structure of hyperspace. the content pages. These observations of data enable the ACT-R model to adapt the information presented on the websites to users’ cognitive According to information diet model, the users assumed to process to pursue specific goals or interests as well as pro- be bounded rational always attempt to find relevant web vide necessary instructions in real time to guide the users’ pages in response to a goal or interest that are expected navigation. to contain most profitable information. The user’s diet in the hyperspace refers to the rate-maximizing subset of the 3.1.1 User Access Patterns web pages that should be selected. The profitability of a content page is defined as the ratio of value gained from the The users’ access patterns between web pages refer to the content page to the cost of time within the page. Then the users’ navigation strategies in the website. These access pat- basic idea of our incremental optimized algorithm is that the terns are specified by the data recorded in web server log. users should continue to access content pages in the order Since it records the user access behaviors of the website, of increasing rank of the pages’ profitabilities as long as the web server log is still considered to be the most important profitability of the k+1 page is not less than the rate of gain source of data for the adaptive navigation support. Based on for a diet of the top k pages. The algorithm outputs an information foraging theory, we come up with a novel incre- optimized set of content web pages that should be accessed mental optimization algorithm to evaluate the users’ access by the users to perform a specific task. The cumulative patterns dynamically in order to enable ACT-R model to gain function can be specified by the number of AOIs in the content web page and their mutual relevance with the user’s goal which can be quantified by the spreading activation mechanism [1] in the declarative knowledge of the ACT-R model. The time spent in the process is recorded by web log software in the user tracing model. These optimized set of content web pages for a specific task will be transformed into declarative knowledge in ACT-R model. 3.1.2 User Viewing Patterns The user’s viewing patterns refer to the user’s fixation se- quences in the content pages and their efficiency of infor- mation seeking. According to [3], fixation sequence analysis can reveal the users’ cognitive strategies to task completion that drive their attention to move around in the web page. A new tool used to discover the similarities in fixation se- quences and identify the experimental variables that may Figure 2: Architecture of the ACT-R Model. affect their characteristics was described. This tool provides a solid practical foundation for constructing our user tracing model. Based on Yarbus’ research work [17] that revealed that the order of fixations on regions of a stimulus is influ- there are several modules within the architecture of ACT-R. enced by the relative importance of the regions to the viewer, The declarative module retrieves information from long term and that viewers exhibited repeated cycles, or patterns, of memory, and the intentional module is used for keeping track fixations on the most interesting features of a stimulus, we of current goals and intentions of the users. A central pro- assume that the users’ eye fixations in a web page determine duction system is responsible for coordinating the behaviors the efficiency of their information seeking behaviors in that of these modules. A production is a condition-action pair page. stored in the procedural memory. At a particular produc- tion cycle, once the condition parts of some productions are eyePatterns [16] will be adopted to extract the users’ viewing matched with the patterns from external world and internal patterns under a specific task in the pattern extraction mod- modules, they will be gathered into the conflicting set. The ule. A web page can be parsed into several sub-regions based conflict resolution will select only one production in each on its layout and contents. These sub-regions are defined as cycle to execute its action based on their utility. These ac- area of interest (AOI) normally labeled with different char- tions make changes to the internal states of the modules and acters. Therefore, the string representation of the fixation adaptive interface. sequence corresponds to a concatenation of the AOI codes in the order of fixations occurred within the AOIs. eyePatterns is a software tool that provides several approach to discover 3.2.2 Declarative Knowledge the patterns in fixation sequences, moreover unknown and Declarative knowledge represents the various facts that peo- specified patterns can be found through discovery and pat- ple are aware they know and can explain them in an under- tern matching. these fixation sequences are integrated with standable way, such as the contents of a web page, the func- the semantic meanings of each AOI [14]. tion of a certain button. Spreading activation mechanism is applied in the declarative memory to simulate the informa- tion retrieval process of human cognition. The declarative 3.2 ACT-R Model knowledge is grouped into a set of chunks, each of which To integrate cognitive models into the adaptive hyperme- contains a bigger or smaller piece of information depending dia system we need to keep track of the users’ information on the applications. Parts of these pieces of information are seeking process and a series of cognitive states to adapt the corresponding to the contents displayed on the web pages layout and the structure of the hyperspace in a way to fa- of the hyperspace. An important feature of a chunk is its cilitate the effectiveness of information seeking. The key activation. The activation of a chunk represents to what idea is that the cognitive model should incorporate the un- extent this piece of information is needed at a particular derlying information seeking skills that allow the users to time. The chunks connect to each other through associa- pursue their goals or interests in an expected most efficient tions which represent the co-occurrence between the pieces way. Based on the user tracing model, our system can mon- of information contained in the linked chunks. The associ- itor the users’ information seeking behaviors and infer their ations have specific strengths to determine the amount of intentions by mapping the behaviors to the components of activation flow from one chunk to the related chunk. The the model. Subsequently, immediate adaptation of the hy- users’ goals or behaviors activate a group of chunks in this perspace and real-time instructions can be generated to fa- spreading activation network, meanwhile the contents dis- cilitate the users’ information seeking behaviors. played on the web page of the hyperspace activate some other chunks. These activations spreading via the associ- 3.2.1 ACT-R Architecture ations through the network reflect the mutual relevance of The basic assumption in the ACT-R theory is that human the users’ goals or behaviors and the contents displayed on cognition emerges through an interaction between a proce- the web page. All the associated chunks have been activated dural memory and a declarative memory. Based on this, to a certain higher level. 3.2.3 Procedural Knowledge 49(4):41–46, April 2006. The procedural knowledge which specifies how the declara- [11] J. Oberlander, M. O’Donnell, A. Knott, and tive knowledge is transformed into active behaviors is repre- C. Mellish. Conversation in the museum: Experiments sented by a set of production rules stored in the procedural in dynamic hypermedia with the intelligent labelling memory system. These production rules detect activated explorer. New Review of Hypermedia and Multimedia, declarative knowledge and input patterns from the sensor. 4(260):11–32, November 1998. At any point of time, multiple rules might be fired, but only [12] P. Pirolli and S. K. Card. Information foraging. one can be selected based on its utility to be executed. Since Psychological Review, 106(4):643–675, January 1999. the user’s information seeking behavior is specified by two [13] C. Romero, S. Ventura, J. A. Delgado, and P. D. Bra. kinds of patterns, the production rules should be designed Personalized links recommendation based on data accordingly such as: mining in adaptive educational hypermedia systems. In Proceedings of the second European Conference on IF the current page is included in the optimized set of content Technology Enhanced Learning, pages 292–306. web pages and it is a leaf, THEN it should be moved up in EC-TEL, March 2007. the hierarchical structure of the hyperspace and linked to an [14] B. P. Stone and S. Dennis. Using lsa semantic fields to index page. predict eye movement on web pages. In Proceedings of the Twenty Ninth Conference of the Cognitive Science IF the AOI is with high relevance level in the current page Society, pages 665–670. Cognitive Science Society, and it is not included in the user’s viewing pattern and the August. current page is included in the optimized set of content web [15] W. Tarng, M.-Y. Chang, L.-K. Lai, S.-S. Tseng, and pages, THEN the AOI should be highlighted. J.-F. Weng. An adaptive web-based learning system for the scientific concepts of water cycle in primary These are the English equivalent forms of the production schools. In the Sixth IASTED International rules that should be designed in our system. Conference Proceedings, pages 175–184. ACM, March 2007. 4. REFERENCES [16] J. M. West, A. R. Haake, E. P. Rozanski, and K. S. [1] J. R. Anderson. A spreading activation theory of Karn. eyepatterns: Software for identifying patterns memory. Journal of Verbal Learning and Verbal and similarities across fixation sequences. In Behavior, 22(0):261–295, November 1983. Proceedings of the 2006 Symposium on Eye Tracking [2] J. R. Anderson. Act a simple theory of complex Research and Applications, pages 149–154. ACM, cognition. American Psychologist, 51(4):355–365, March 2006. November 1996. [17] A. L. Yarbus. Eye Movements and Vision. Plenum [3] J. R. Anderson and K. A. Gluck. What Role do Press, New York, NY, 1967. Cognitive Architecture Play in Intelligent Tutoring Systems? Lawrence Erlbaum Associations, Philadelphia, PA, 2001. [4] P. D. Bra and N. Stash. Aha! adaptive hypermedia for all. In Proceedings of the AACE WebNet Conference, pages 262–268. Association for the Advancement of Computing in Education, September 2001. [5] P. Brusilovsky. Adaptive Hypermedia: From Intelligent Tutoring Systems to Web-based Education. Springer, Heidelberg, Berlin, 2001. [6] P. Brusilovsky. Authoring Tools for Advanced Technology Learning Environment. Kluwer Academic Publishers, Dordrecht, 2003. [7] G. Chibing and M. Nordahl. Building an adaptive website based on user access patterns. In Proceedings of the 2005 International Conference on Cyberworlds, pages 358–362. IEEE Computer Society, November 2005. [8] F. Daniel, M. Matera, and G. Pozzi. Combining conceptual modeling and active rules for the design of adaptive web applications. In Workshop Proceedings of the Sixth International Conference on Web Engineering, pages 84–89. ACM, July 2006. [9] A. Kobsa, J. Koenemann, and W. Pohl. Personalised hypermedia presentation techniques for improving online customer relationship. The Knowledge Engineering Review, 16(2):111–155, November 2001. [10] G. Marchionini. Exploratory search: from finding to understanding. Communication of the ACM,