Jalal's Thesis Defense

Slide 1: 

Transaction Models for Web Accessibility A PhD Thesis Presented by Jalal Mahmud Department of Computer Science, Stony Brook University Adviser: Prof. I.V. Ramakrishnan

Why is Web Accessibility Important? : 

Why is Web Accessibility Important? 10-11 Mil. Visually Impaired People in U.S. 1.3+ Million Americans are Legally Blind 161+ Million People Visually Impaired Worldwide (37 million blind, 124 million low vision) At least 50% of Blind Americans Use Internet Source “Magnitude and causes of visual impairment”, www.who.org.

Motivating Example : 

Motivating Example Item to be Searched Step 1: Go to Bestbuy and Fill Search Form (with CD player as Search Item) Sighted Person can Easily Locate and Fill the Search Form.

Slide 4: 

Motivating Example Pick an Item Step 2: Review the Search Results Sighted Person can Quickly Pick the Desired Item and Pick an Item

Slide 5: 

Motivating Example Step 3: Review Product Details and Add to Cart Sighted Person can Easily find the Relevant Section and does the Desired Operation

Slide 6: 

Motivating Example Step 4: Review Shopping Cart and Checkout Sighted Person can Quickly find the Section Containing Shopping Cart and Checkout

Web Transaction : 

Web Transaction Objective is to accomplish a task that may span across several Web pages Examples: - Buying a book - Paying utility bills online Characteristics - A sequence of steps (like buying a book) - Each step is based on user-selected operation A Web Transaction Example Buying CD player from Bestbuy.com

Slide 8: 

Web Transaction using a Screen Reader Using Voice Interaction, items preceeding the target content are traversed sequentially After 3 minutes

Web Accessibility Divide : 

Web Accessibility Divide Fundamental Problem: - Screen Readers and Audio Browsers process Web pages sequentially resulting in severe information overload. - Information Overload Makes Web Browsing - Time-Consuming - Strenuous - Tiring This is more prominent when conducting a Web transaction that spans across multiple pages. Large divide in Web Accessibility between sighted and visually impaired users.

Slide 10: 

Bridging the Divide Big Picture: The HearSay System My Focus: Reducing Information Overload in Non-visual Web Browsing and Transaction Processing

Slide 11: 

Outline Web Transaction Transaction Models Process Model Concept Models Mining Transaction Models - Supervised Approach - Unsupervised Approach. Experiments Conclusion

Slide 12: 

Reducing Information Overload - At each step of a Web Transaction, User Needs Only Relevant Content. - Identify and Present Relevant Content. Two Aspects to a Web Transaction -Semantic Concepts: Captured by a Shallow Ontology Operation Sequences: Captured by a Process Model

Slide 13: 

Operations on Concepts add_to_cart Add to Cart check_out Check Out continue_shopping Continue Shopping update_cart Edit Cart item_select Item List select_item_category Item Taxonomy show_item_detail Item Detail Concepts are associated with Operations

Slide 14: 

item_select submit_searchform Process Model TAXONOMY CONCEPT SEARCH FORM CONCEPT 1

Slide 15: 

submit_searchform item_select Process Model SEARCH FORM CONCEPT SEARCH RESULT CONCEPT

Slide 16: 

Process Model 3 1 2 4 5 6 show_item_detail add_to_cart add_to_cart add_to_cart check_out check_out check_out continue_shopping item_select select_item_category select_item_category submit_searchform item_select view_shoppingcart view_shoppingcart, update_shoppingcart submit_searchform submit_searchform 1 - START STATE 6 - FINAL STATE Model-driven Transaction for Online Shopping Domain item_select Submit_searchform Transaction Sequence: Sequence of Operations. e.g. submit_searchform.item_select.add_to_cart.check_out Web Transaction Model has Two Components Concept Models: Identifies Semantic Concepts from Web pages Process Model: Presents Semantic Concepts at each Step

Slide 17: 

Concept Identification

Slide 18: 

Guide-O: A Prototype for Conducting Web Transaction using Constrained Modalities Process Model was learned using Automata Learning technique from Transaction Sequences labeled by sighted users. - 200 Transaction Sequences (120 for training, 80 testing) - Performance (Recall/Precision): On average 87% / 92% Concept Models were learned using Standard Bayesian technique from labeled (by sighted users) Concept instances. - On average, we got around 85% Recall. User Evaluation - Over two dozen CS graduate students (sighted) evaluators - Over 30 web sites spanning Books, Consumer Electronics and Office Supplies domains

Qualitative Evaluation Of the System : 

Qualitative Evaluation Of the System C - Concept Related Question S - System Related Questions This was a joint work. The paper from this research appeared in WWW 2006 Zan Sun, Jalal Mahmud, Saikat Mukherjee and I.V. Ramakrishnan, "Model-directed Web Transactions under Constrained Modalities”, WWW 2006, (1 of 5 Best Paper Nominee), extended version appeared in ACM Transactions on the Web, Volume 1 Issue 3, 2007. The rest of the talk is about my individual work. Quantitative Evaluation: Time Performance

Slide 20: 

We will present a framework to mine transaction models from partially labeled click stream data generated by transactions, where some or all the labels could be missing. Click Streams are Sequence of operations on links, buttons, i.e. clickable objects (with unique id generated by browser) in a Web page. We use the term “click stream” and “transaction sequence” interchangeably Relaxing the requirement of fully labeled training data to learn the models.

Slide 21: 

- Visually impaired users do not have to depend on third party (e.g., sighted users) for constructing transaction models. - Mine personalized models from transaction click streams associated with sites that visually impaired users visit regularly. - Since partially labeled data is relatively easier to generate, scaling up the construction of domain-specific transaction models (e.g., shopping, airline reservations, etc.) is feasible. - Adjusting the performance of deployed models over time with new training data is also doable. Unsupervised Mining of Transaction Models: Motivation High Level Algorithm Start with the Click Streams Get the Concept Segments that Contain the Clicked Objects. Cluster the Concept Segments Label the Unlabeled Clusters - Label the Concept Segments and Click Streams - Learn Process Model and Concept Models from Labeled Data

: 

(link.image.text.image.text)+ 145AB2D1 Segment Features Concept Segment How to get Click Streams? Record user Clicks in Web Transactions. User clicks a link, its id 145AB2D1 The page is segmented into geometric segments. Geometric Segmentation Algorithm uses the layout and alignment of elements to segment the Web page into blocks containing semantically related items Geometric Segment Containing the link is Identified. [Ref. Jalal Mahmud, Yevgen Borodin and I.V. Ramakrishnan, “CSurf: A context-driven non-visual Web Browser”, WWW 2007. ] Concept Segment Case 1: Concept instances contain a collection of objects with similar presentation style and geometric alignment in the page. In this case, Geometric Segment is the Concept Segment.

Slide 23: 

add, cart, pay, <MONEY>, add to, to cart, add to cart, ………., text, image. 05F354A1 Segment Features are words and word combinations (bi gram, trigram), their stem counterparts and patterns User clicks the button with id “05F354A1”. Special Fields (e.g., Date, Money) are tagged as Features. So $219.99 is tagged as <MONEY> Concept Segment Case 2: Concept instances contain a single clickable object. Segment containing the Context of such object is the Concept Segment. Presentation pattern of such segment is not repeated. [ Context is identified using a topic boundary detection algorithm. Ref. Jalal Mahmud, Yevgen Borodin and I.V. Ramakrishnan, “CSurf: A context-driven non-visual Web Browser”, WWW 2007. ] Concept Segment

Slide 24: 

User Clicks the Button with id “731DA231”. Geometric Segment does not contain objects with repeating patterns. Concept Segment: Segment containing the Context of the object Segment Features add, cart, add to, to cart, add to cart, MONEY, image. 731DA231

: 

subtotal, <PRICE>, edit, cart, edit cart, checkout, text, link 873A11F2 Segment Features User clicks the button with id “873A11F2”. Geometric Segment does not contain objects with repeating patterns. Concept Segment: Segment Containing the Context of the object So the Click Stream is: <145AB2D1. 05F354A1.731DA231.873A11F2> This is an example of an unlabeled Click Stream.

Manual Labeling: Click Streams can be manually labeled : 

Manual Labeling: Click Streams can be manually labeled 145AB2D1 Possible Labels Choose from domain specific fixed Set of Labels to build domain-specific models Operation(ItemList) = select_item select_item(145AB2D1) ItemList Assign Arbitrary Label to build Personalized models Labeling the Concept Segment also Labels the Web Object (contained in that segment) in the Click Stream. Each Concept is Associated with a unique operation. Now the click stream is: <select_item(145AB2D1). 05F354A1.731DA231.873A11F2> This is an example of a partially labeled click stream. This is domain specific labeling since the mapping from concept name to operation name is known and stored apriori.

Manual Labeling: Click Streams can be manually labeled : 

Manual Labeling: Click Streams can be manually labeled 145AB2D1 Possible Labels Choose from domain specific fixed Set of Labels to build domain-specific models Operation(Label_1) = label_1 label_1(145AB2D1) Label_1 Assign Arbitrary Label to build Personalized models Labeling the Concept Segment also Labels the Web Object (contained in that segment) in the Click Stream. Each Concept is Associated with a unique operation. Now the click stream is: <label_1(145AB2D1). 05F354A1.731DA231.873A11F2> This is an example of a partially labeled click stream. This is personalized labeling since the mapping from concept name to operation name is not known. So we automatically generate an Operation label for the concept name.