Transcript ppt
ADAPTIVE HYPERMEDIA Presented By:Debraj Manna Raunak Pilani Gada Kekin Dhiraj OUTLINE Introduction What is Hypermedia? ‘Lost in Hyperspace’ Syndrome Adaptive Hypermedia AntWeb WebWatcher Conclusion HYPERMEDIA Hypertext Text, displayed on a computer, with references (hyperlinks) to other text that the reader can immediately access Hypermedia The use of text, data, graphics, audio and video (i.e. multimedia) as elements of an extended hypertext system All elements are linked so that the user can move between them at will CURRENT SCENARIO Search Engine helps in finding web pages. But not link within the websites. ‘Lost in Hyperspace’ syndrome Too many links to choose But little knowledge about appropriate ones EXAMPLE EXAMPLE EXAMPLE ADAPTIVE HYPERMEDIA It tries to answer the ‘lost in hyperspace’ syndrome. It tries to select a set of links appropriate for a current user. E.g. www.amazon.com Recommends books based on prior history and preferences of other users ADAPTIVE V/S ADAPTABLE HYPERMEDIA Primary difference between the two is the degree to which the adaptation process occurs autonomously Adaptive Hypermedia is a system driven personalization and modifications. Adaptable Hypermedia is user-driven. E.g. e-mail inbox Adaptable is a-priori but adaptive is a-posterior. FRAMEWORK General Framework of Adaptive Hypermedia Systems [3] AntWeb WHAT IS ANTWEB? • Acts as an extended Web Server • Treats Web Users as Artificial ants • Doesn't modify content on page, instead just directs user to his/her most probable destination WHY ANTS? • Drawbacks of ants: • No vision, thus no Global View • Essentially no intelligence in single ants • Despite this: • They are capable of finding shortest path from food to source • They are adaptable to a changing environment HOW DO THEY DO THIS? • Ants use chemical substance called “Pheromone” to communicate with one another • Ants display intelligence as swarms rather than single units CHOOSING THE SHORTEST PATH Image taken from: http://blog.vettalabs.com USERS AS ARTIFICIAL ANTS • AntWeb System treats users as ants and an information source as the goal (food) • Server deposits “Pheromone” on users behalf • Maintains large Database of all pheromone values at each page • Tries to estimate what page an Ant wants to visit based on pheromone left by previous Ants BASIC APPROACH • Pheromone value depends on quality of solution • Heuristic value (estimate of time spent at a page) is also used • Probability is calculated based on both these values • AntWeb then chooses the page with the highest probability of being the one the Ant wants MATHEMATICALLY Probability of moving from node i to node j: j Where, τi,j is the amount of pheromone on edge i,j α is a parameter to control the influence of τi,j ηi,j is the desirability of edge i,j (a priori knowledge, typically 1 / di,j) β is a parameter to control the influence of ηi,j MATHEMATICALLY(contd.) Pheromone Depositing: Where, is the amount of pheromone deposited on page ‘i’ by ant ‘k’ at iteration ‘p’ for destination ‘d’ is the tour done by ant ‘k’ at iteration ‘p’ to get to destination ‘d’ is the distance of i from d in T is a parameter that represents how the distance of ‘i’ until d in T affects decrease in pheromone deposited MATHEMATICALLY (contd.) Pheromone Update: Where, τi,j is the amount of pheromone on a given edge i,j ρ is the rate of pheromone evaporation Δτi,j is the amount of pheromone deposited EXAMPLE Let, a visitor make the following trajectory to arrive to his target page 9 1A, 2A, 3A, 2C, 9 Page 1A 2A 3A 2C 9 Pheromone Deposited 1/5 1/4 1/3 1/2 1 ADAPTING TO CHANGE IN ENVIRONMENT • A pheromone decay coefficient is used • So AntWeb will also consider other paths as time passes and choose better ones, if found • New system also has provision for multiple solutions at a time thus providing more flexibility ANTWEB IN ACTION [1] WebWatcher A TOUR GUIDE FOR MUSEUM Need for a Museum Tour Guide Poorly Defined Initial Interests of the visitor Museum contents not known to the visitor Help from someone who is familiar with the museum Steps Visitor describes initial interest to the guide Guide points out items of interest that refine the interests of the visitor Guide in turn refines its guidance through every such experience A TOUR GUIDE FOR WWW Acts as a Web Tour Guide Accompanies user from page to page Suggests appropriate links Learns from experience Different from keyword based search engine Search can not learn that “machine learning” matches “neural networks” TOUR WITH WEBWATCHER Home Page of CMU Image taken from http://www.cs.cmu.edu/~webwatcher/wwdemo.html TOUR WITH WEBWATCHER The user can now type in an interest Image taken from http://www.cs.cmu.edu/~webwatcher/wwdemo.html TOUR WITH WEBWATCHER WebWatcher's tour begins from the same page Image taken from http://www.cs.cmu.edu/~webwatcher/wwdemo.html INTERFACE WebWatcher Interface [2] LEARNING Keyword accumulation at hyperlinks [2] SUGGESTING A LINK Hyperlink is annotated with the interest of the users. Hyperlink description and interests are stored as TFIDF feature vector. Suggest hyperlinks by calculating similarity between user’s interest & hyperlink description Cosine similarity is used. CONCLUSION Adaptive Hypermedia (AH) is a new but quickly developing area of research. Currently only 20 such systems are developed. [3] Generally used in e-commerce & IR hypermedia. It comes at the cost of efficiency. Experimental testing of AH system isn’t as developed. REFERENCES [1] W. M. Teles, L. Weigang, and C. G. Ralha AntWeb –The Adaptive Web Server Based on the Ants’ Behavior, wi, pp.558, 2003 IEEE/WIC International Conference on Web Intelligence (WI'03), 2003 [2] T. Joachims, D. Freitag, T. Mitchell, WebWatcher: A Tour Guide for the World Wide Web , Proceedings of IJCAI97, August 1997 [3] P. Brusilovsky, Methods and Techniques of Adaptive Hypermedia, User Modeling and User Adapted Interaction. V.6, n.23, pp.87-129. Special issue on adaptive hipertext and hypermedia, 1996. [4] M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics--Part B , volume 26, numéro 1, pages 29-41, 1996 END Questions? EXTRA SLIDES Example to explain TF. IDF Document containing 100 words wherein the word cow appears 3 times TF for cow= 0.03 (3 / 100) Now, assume 10 million documents and cow appears in one thousand of these Inverse Document Frequency (IDF) of cow= ln(10 000 000 / 1 000) = 9.21 TF-IDF score is the product of these quantities: 0.03 * 9.21 = 0.28. Slide taken from cs626-449 ‘s Lecture 7