Program Transformations for Information Personalization Saverio Perugini Department of Computer Science University of Dayton 300 College Park, Dayton, OH 45469–2160, USA Naren Ramakrishnan Department of Computer Science Virginia Tech Blacksburg, VA 24061–0106, USA Abstract Personalization constitutes the mechanisms necessary to automatically cus- tomize information content, structure, and presentation to the end-user to reduce information overload. Unlike traditional approaches to personaliza- tion, the central theme of our approach is to model a website as a program and conduct website transformation for personalization by program transfor- mation (e.g., partial evaluation, program slicing). The goal of this paper is study personalization through a program transformation lens, and develop a formal model, based on program transformations, for personalized interaction with hierarchical hypermedia. The specific research issues addressed involve identifying and developing program representations and transformations suit- able for classes of hierarchical hypermedia, and providing supplemental in- teractions for improving the personalized experience. The primary form of personalization discussed is out-of-turn interaction – a technique which em- powers a user navigating a hierarchical website to postpone clicking on any of the hyperlinks presented on the current page and, instead, communicate the Email addresses: label of a hyperlink nested deeper in the hierarchy. When the user supplies out-of-turn input we personalize the hierarchy to reflect the user’s informa- tional need. While viewing a website as a program and site transformation as program transformation is non-traditional, it offers a new way of thinking about personalized interaction, especially with hierarchical hypermedia. Our use of program transformations casts personalization in a formal setting and provides a systematic and implementation-neutral approach to designing sys- tems. Moreover, this approach helped connect our work to human-computer dialog management and, in particular, mixed-initiative interaction. Putting personalized web interaction on a fundamentally different landscape gave birth to this new line of research. Relating concepts in the web domain (e.g., sites, interactions) to notions in the program-theoretic domain (e.g., pro- grams, transformations) constitutes the creativity in this work. Key words: hierarchical hypermedia, information personalization, navigation, out-of-turn interaction, program transformations, partial evaluation, program slicing, web interaction, web mining, website transformation “The important thing in science is not so much to obtain new facts as to discover new ways of thinking about them.” Sir William Lawrence Bragg, the youngest-ever recipient of the Nobel Prize. 1. Introduction Information personalization constitutes the mechanisms necessary to au- tomatically customize information content, structure, and presentation to the end-user to reduce information overload (Perugini and Ramakrishnan, 2003a). Personalization technologies are now ubiquitous on the web and critical to retaining customers (e.g., eBay, Amazon). Our view of personalization is oriented toward personalizing user interac- tion. Specifically, we have developed an interaction technique which empow- ers a user navigating a hierarchical website to postpone clicking on any of the hyperlinks presented on the current page and, instead, communicate the label of a hyperlink nested deeper in the hierarchy. We call this technique out-of-turn interaction and when the user supplies out-of-turn input (i.e., a 2 hyperlink label) we re-organize (or, in other words, personalize) the hierarchy to reflect the user’s informational need. Consider a user, interacting with an automobile website, such as Ed- munds, interested in manufacturers offering hybrid automobiles. If the site’s hierarchical structure requires the user to select a manufacturer at the top level, make at the following level, and so on, then to fulfill the information- seeking goal, this user would need to drill-down through each manufacturer and manually aggregate all hybrid automobiles discovered at the lower levels of the site. However, using out-of-turn interaction, this user could say ‘hy- brid’ at the top level of the site and in response the system would prune out all manufacturer hyperlinks on the root page which do not lead to hybrid au- tomobiles and, therefore, only present hyperlink representing manufacturers which offers hybrid models. With this set of reduced manufacturers the user has the option of browsing (i.e., clicking on one of the presented hyperlinks) or, again, interacting out-of-turn (e.g., by saying ‘manual transmission’). Out-of-turn interaction permits the user to circumvent any intended flows of navigation hardwired into a hyperlink structure by the designer and, in this manner, flexibly reconciles any mismatch between the site’s one-size-fits-all organization and the user’s model of information seeking. Out-of-turn input can be communicated to a site either through text using a browser toolbar plugin (Perugini and Ramakrishnan, 2003b) or through speech using a voice user interface (Narayan et al., 2004). Unlike traditional approaches to personalization, the central theme of our approach is to model information-seeking interactions with hierarchical hypermedia explicitly in a programmatic representation and use program transformations (e.g., partial evaluation, program slicing) to stage the inter- action (Perugini and Ramakrishnan, 2005). A program transformation is an automatic, closed operation mapping one program to another. Converting a n 2 program which computes x to one which computes x is a simple example of a transformation (in this case, partial evaluation). Program slicing (Binkley and Gallagher, 1996) is a program transformation used to extract statements which may affect or be affected by the values of variables from a program. A website such as the Yahoo! directory may be viewed as a DAG, with vertices representing webpages, edges representing hyperlinks, edge labels representing hyperlink labels or search terms, and leaves representing content pages (destinations) (e.g., see Fig. 1). We support the user in experiencing a personalized traversal of such a website by permitting her to enter a search term out-of-turn and adjusting the graph accordingly, e.g., by retaining only 3 the subgraph leading to leaves which have an occurrence of the search term on a path from the root to each leaf (e.g., see Fig. 2). A DAG may also be represented by a program, where each search term corresponds to a boolean variable in a branch in a nested conditional representation (e.g., see Table 4). In that representation, the out-of-turn adjustment described above is mod- eled by slicing the program. Thus, the essence of this paper is an equivalence between rooted DAGs and programs, such that some operations of interest on a DAG (such as adjustment to out-of-turn search terms) correspond to operations of interest on a program (such as slicing). In summary, the central theme of our research is to pose website person- alization and, particularly, website transformation, as the application of a program transformation technique to a programmatic representation of in- teraction based on (often partial) user input. This approach offers a new way of thinking about personalized interaction, especially with hierarchical hypermedia. Decoupling the logic into a program (representation, trans- 1 formation) pair provides a clean separation of concerns and allows us to personalize a hierarchy to individual users without explicitly enumerating a specialized hierarchy (or building a user model) for each individual user. It also fosters the attractive possibility of exploring alternate representations and transformations and studying the resulting forms of personalization en- abled. The creativity in this research arises from relating concepts in the web domain (e.g., sites, links) to notions in the program-theoretic domain (e.g., programs, transformations) (see Table 1). 1.1. Objectives We have built a software framework based on the theoretical ideas pre- sented in this paper (Narayan et al., 2004) and have conducted human- computer interaction studies with users to evaluate specific systems designed with it (Perugini, 2004, Ch. 6) (Perugini et al., 2007). The goal of this paper is study personalization through a program transformation lens, and develop a formal model, based on program transformations, for personalized inter- action with hierarchical hypermedia. The primary form of personalization 1 The representation in a program (representation, transformation) pair specifies how to model a website as a program, such as the nested conditionals representation used in the programs shown in Table 4, while the transformation is a program transformation, i.e., a closed, source-to-source operation mapping a program to another program, such as partial evaluation or program slicing. 4 Table 1: Analogs between the web interaction and program-theoretic domains. Web interaction: Transformation(· · · Transformation (Website, Hyperlink label), · · ·, Hyperlink label) ⇒ Personalized website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Program-theoretic: Transformation(· · · Transformation (Program, Program construct), · · ·, Program construct) ⇒ Specialized program discussed here is out-of-turn interaction. The objectives of this paper are to 1. develop graph-theoretic interpretations of out-of-turn interaction with a general class of websites, 2. illustrate how these interpretations can be supported by a program (rep- resentation, transformation) pair (called a model), often involving pro- gram slicing, 3. evaluate the soundness and completeness (as well as other properties) of a model wrt a target interaction paradigm (e.g., browsing or out-of-turn interaction), 4. identify a partial order of classes of hierarchical hypermedia and explain its implications on the program transformation approach to personaliza- tion, 5. introduce web functional dependencies and describe how they can be mined from websites and used for automatic query expansion to person- alize the user experience further, 6. illustrate program transformation techniques based on program slicing to mine web functional dependencies, 7. demonstrate that an alternate program transformation technique, which employs web functional dependencies, can achieve the same effect as the original transformation technique, 8. develop specialized program transformation techniques for some specific classes of hierarchical hypermedia, and 9. demonstrate how the program transformation formalism can be used to support supplementary personalized interactions. 1.2. Research Methodology When a user says something out-of-turn, we ask: what can be reasonably pruned out of the website? Answers to this question lead to interpretations of out-of-turn interaction, e.g., when a user says something out-of-turn, 5 Table 2: Our research methodology. Develop a graph-theoretic definition of an interpretation of personalized interaction. ↓ Model interaction with a hierarchical website as a program (never to be executed, but only to be transformed). ւտ [design a mapping from user input to program constructs to capture requirements] ցր Develop a program transformation technique capable of realizing the interpretation. ↓ Evaluate the model. ↓ Study the enabled personalized interaction with users. 1. (a) first identify leaf webpages reachable by a path involving a hyperlink labeled with the out-of-turn input, and (b) prune all paths through the site that do not lead to any of these leaf pages. 2. prune all paths through the site which do not involve a hyperlink labeled with the out-of-turn input. Both interpretations assume that the input supplied by the user is legal. An interaction using illegal input may either be undefined or cause an er- ror. Interpretation 2 entails interpretation 1 because every path retained by interpretation 2 is retained under interpretation 1. In other words, interpre- tation 2 prunes all paths pruned under interpretation 1, but the converse does not hold. Next we ask: how can we support (i.e., model and realize) the interpretation of out-of-turn interaction using program-theoretic principles. This suggests an iterative process, illustrated in Table 2, of developing a programmatic representation of interaction with an instance of hierarchi- cal hypermedia and developing a program transformation technique, often involving a composition of program transformations, capable of supporting the desired personalized interactions from the model. Moreover, we must de- sign a mapping from user requests (often partial input) to program constructs 6 Table 3: Graph-theoretic constructs and web analogs. Graph-theoretic construct Web analog Graph Website Vertex Webpage Edge Hyperlink Edge-label Hyperlink label Root Homepage (often variables) to direct the transformation. We next evaluate the model by computing various metrics. We evaluate the personalized interaction en- abled by conducting studies with users (Perugini, 2004, Ch. 6) (Perugini et al., 2007) which often reveal insights into new interpretations, interaction paradigms, and interaction techniques and, thus, help close the loop. While some parts of this paper have been previously reported upon by the authors (Narayan et al., 2004; Perugini and Ramakrishnan, 2005), the present paper builds upon these foundations to develop a unifying theory for personalization using program transformations. Where necessary, key results from the above papers (e.g., Table 1, taken from (Perugini and Ra- makrishnan, 2005); Table 5, taken from (Narayan et al., 2004); Table 6, taken from (Perugini and Ramakrishnan, 2005), and Section 8, taken from (Perug- ini and Ramakrishnan, 2005)) are reported to ensure that the discussion here is self-contained. 2. Graph-theoretic View of Personalized Interaction We begin by developing syntactic notions from graph theory and progres- sively attach web interaction semantics to develop a theory of representing and reasoning about interaction with hierarchical hypermedia. 2.1. Syntactic and Semantic Notions Fig. 1 illustrates a DAG model of a hierarchical website with charac- teristics similar to web directories such as Yahoo! at http://dir.yahoo. com or the Open Directory Project (ODP) at http://dmoz.org. Table 3 is an abridged mapping from graph-theoretic notions to web analogs. Edges help model paths through a website a user follows to access leaf vertices. Leaf vertices model leaf webpages which contain content. We refer to a leaf 7 1 arts computers 2 3 theatre music speakers software hardware 5 4 7 6 drama music theatre classical jazz software music business memory 10 11 9 8 13 14 12 Figure 1: Example of a DAG model of a hypothetical hierarchical website with character- istics similar to those in the Yahoo! directory 8 content page as terminal information and the terms therein as units of ter- minal information. Edge-labels, which we refer to as structural information, model hyperlink labels or, in other words, choices made by a navigator en route to a leaf. An edge-label, a unit of structural information, is therefore a term of information-seeking (simply a term hereafter) which a user may bring to bear upon information seeking. Structural information thus helps make distinctions among terminal information. A set of terms is complete when it determines a particular leaf webpage; otherwise it is partial. An interaction set of a DAG D is the complete set of the terms along a path from the root of D to a leaf vertex of D. An interaction set constitutes complete information; any proper subset of it is partial information. An interaction set of D classifies a leaf vertex of D, but does not capture any order of the terms. We now provide definitions which pertain to a user’s interaction with a website. A term is in-turn information if it appears as a hyperlink label on the user’s current webpage and is, thus, currently solicited by the system. On the other hand, a term is out-of-turn information if it represents a hyperlink label nested somewhere deeper in the site and is, thus, currently unsolicited from the system, but relevant to information seeking. Each term from D which is not in-turn information is out-of-turn information. Several partial orders can be defined over an interaction set wrt the time at which the user communicates the term to the system, called arrival time. When a user clicks on a hyperlink, she implicitly communicates the hyperlink label to the underlying system. For instance, when a user clicks on the hyperlink labeled ‘arts’ followed by that labeled ‘music,’ she communicates the ≺arts, music≻ terms, in that order. Similarly, when the user supplies out-of-turn input (using a textual or speech modality), he is communicating terms to the system. These partial orders can be summarized with partially ordered sets or posets. Each linear extension of such a poset is a total order called an interaction sequence. A browsing interaction sequence of D is a total order on an interaction set of D wrt the parenthood relation of D. An out-of- turn interaction sequence of D is a total order on an interaction set of D wrt the arrival time relation implied by out-of-turn interaction. Interestingly, both interpretations of out-of-turn interaction introduced above imply the same arrival time relation – a partial order containing only the reflexive tuples of terms from the interaction set. In other words, none of the terms from the interaction set are required to be ordered. The linear extensions of the posets associated with these partial orders are out-of-turn interaction 9 sequences. An interaction paradigm P for D is given by the union of all linear exten- sions of posets defined over interaction sets of D. In other words, an inter- action paradigm is a complete set of realizable interaction sequences from D wrt an interaction technique. When an edge-label labels more than one edge in a path from the root of D to a leaf vertex of D, it is advantageous to think of an interaction sequence as a finite effective enumeration of an interaction set of D, where the order of the terms in the enumeration corresponds to the arrival time relation afforded by the interaction technique wrt D. The brows- ing paradigm of D in Fig. 1 is {≺arts, music, jazz≻, ≺arts, music, classical≻, ≺arts, music, theatre≻, . . . , ≺computers, hardware, memory≻}. Likewise, an out-of-turn paradigm is {≺arts, music, jazz≻, ,≺music, arts, jazz≻, [the remaining 4 permutations of {arts, music, jazz}], ≺arts, music, classical≻, ≺music, arts, classical≻, [the remaining 4 permutations of {arts, music, classical}], . . . , ≺computers, hardware, memory≻, ≺hardware, computers, memory≻, [the remaining 4 permutations of {computers, hardware, memory}]}. While there can be only one browsing paradigm, there are multiple out-of- turn paradigms. Moreover, the browsing paradigm for a DAG D is a subset of any out-of-turn paradigm for D. 2.2. Support Terms and Tools We use the symbol D to represent the universal set of DAGs, the symbol T to represent the universal set of terms, and L to denote the universal set of leaf webpages. Before we can expand this discussion to functions over D×T to realize the sequences of a particular interaction paradigm, we must develop some support terms and tools. Sequencize is a total function SQ : D → P(I) which given D returns the browsing paradigm of D. We use the symbol I to represent the universal set of interaction sequences. P (·) denotes the power set function. Term extraction is a total function TE : D → P(T ) which given D returns the set of all unique terms in D. A term-co-occurrence set of D is a set T ⊆ TE(D). Let the level of an edge-label in D be the depth of the source vertex of the edge it labels. If a given edge-label occurs multiple times in D, a level is associated with every occurrence. A term-level set of D is a term-co-occurrence set comprising all unique terms in D with the same level. Term-level extraction is a total function TLE : (D×N) → P(TE(D)) which 10