Steven Gardiner
email: sgardine@cs.cmu.edu

Anthony Tomasic
email: tomasic@cs.cmu.edu

John Zimmerman
email: johnz@cs.cmu.edu

Rafae Aziz
email: raziz@cs.cmu.edu

Kathryn Rivard
email: krivard@cs.cmu.edu

Mixer: Mixed-initiative Data Retrieval and Integration by Example

Keywords: programming by demonstration, end user programming, mixed initiative, data integration

, and incorporates insights from mixed-initiative researchers into collaboration between end users and software agents. This paper justifies the design decisions that drive Mixer, focusing on general lessons for designers of programming-by-demonstration systems targeting nonprogrammers.

We evaluate Mixer by performing a user study showing that administrators are able to accomplish programming tasks without needing to understand programming concepts for data retrieval and integration.

Introduction

As the size and richness of the web has steadily increased over the last decade, users have ratcheted up their expectations for the scope of information easily available from the web. Web interfaces, in contrast, usually permit access to the information they expose in a highly constrained manner. The gap between the form of the information required and the form provided by the deployed interfaces is bridged in practice by human intelligence. In particular, office workers in an administrative capacity are regularly assigned mundane, repetitive data integration tasks, entailing the gathering of information from several sources into an ad hoc report, often in response to an email [START_REF] Tomasic | User Constructed Data Integration via Mixed-Initiative Design[END_REF]. Administrators do not consider these tasks difficult, but they do consider them very tedious. The repetitive and procedural structure of the tasks makes them ripe for automation; however, the actions taken in response to the retrieved information generally require human judgment. This combination of automation and human judgment invites a mixed-initiative approach that weds the administrator's understanding of the desired report with a programmatic agent actually performing the bulk of the mundane retrieval.

As an example, suppose a university dean wishes to investigate previous collaborations between her university and a certain research lab, and further that she has assigned her assistant the task of finding all professors in the university who have published a paper with someone from the lab. The straightforward solution is to look up in turn each professor's publications in a digital library and store all of their collaborators from the lab in some intermediate location, such as a column of a spreadsheet. This solution, while effective, illustrates well the tedium involved, as it requires the administrator to perform the same series of clicks and copies and pastes, each time with different input, until the output report is complete.

The tedious, repetitive nature of the tasks evokes the concept of programming by demonstration (PBD). The application of PBD to administrative data integration tasks follows from the insight that once the user has shown how to look up a single example, the system has sufficient information about the procedure to look up the rest of the examples. In an effort to realize the promise of PBD in facilitating administrative data integration tasks, we developed Mixer, a Mixed-Initiative PBD system that allows users to train an agent to perform the tasks. Our current implementation builds on our previous Wizard-of-Oz study, which demonstrates the effectiveness of a spreadsheet-like user-created form as a medium of communication between a human user and a simulated computer agent. Users were quite successful in using the mocked-up system, but they struggled with the following issues: [START_REF]Mixed-Initiative Interaction[END_REF] specifying 1-to-many relationships in a manner useable by the agent, (2) specifying precision in the retrieved report, and (3) selecting meaningful segments of text on the page. Mixer as presented here addresses these shortcomings, and also incorporates insights from other explorations of web PBD [START_REF] Leshed | CoScripter: automating & sharing how-to knowledge in the enterprise[END_REF][START_REF] Lin | End-user programming of mashups with vegemite[END_REF]. Mixer presents several innovations over previous approaches. First, Mixer presents a unified modeless interface for integrating data, whether that data come from one or several data sources. Additionally, Mixer leverages the insights of Mixed-Initiative design to facilitate collaboration between the user and the agent to accomplish the user's goal.

To evaluate our design decisions, we conducted an evaluation with real administrators. The administrators were asked to retrieve multiple items from a single data source and to link information across multiple data sources. The evaluation results show that: (i) Using the Mixer table based interface, administrators can conceive of, create, and use forms that effectively communicate to the Mixer agent both the information they want and the information the agent needs to automate the task; and (ii) administrators recognized the value of automating this type of mundane task and indicated they would incorporate a mixed-initiative tool like Mixer into their work practices.

The remainder of this paper is organized as follows. First, we describe the design of Mixer. We then describe the study performed and the results obtained. Next, we discuss the implications of the present study. Lastly, we situate this work within the related work in the literature, and conclude.

At a high-level, interaction with Mixer requires the user to construct the first row of a table, and in doing so, the user demonstrates to the agent what information they want and where this information can be found. When this row is complete, the user releases the agent to follow the pattern until the retrieval is complete. If the user desires a subset of this information, they can export the resulting table to a spreadsheet and use the spreadsheet to make the subset they desire selectable. Below we detail an example, depicted in Figure 1, of how the interaction works. In the example, the user looks up the names and affiliations of the coauthors of a particular researcher using an online interface which allows accessing this information for one publication at a time.

Users begin using Mixer by navigating their browser to the first page they wish to retrieve information from (referred to as the target page). In this example the page contains a listing of the publications of the researcher, with a brief description of each publication and a link to a detailed record of the publication. Once there, the user clicks on the Mixer button appearing within the browser's chrome. This click causes two actions. First, the Mixer workspace (referred to as workspace) appears in a frame to the right of the target page. Second, Mixer augments the target page, highlighting any element the agent can accept as an input in orange.

To add an element to the workspace, the user right-clicks the element and selects "Copy to Mixer" in a context menu. In response, Mixer constructs a new column in the workspace, gives it a heading, fills in the first row with the element the user selected, and fills in the remaining rows with all elements that match the user's selection (Figure 1A). In this case the user selects the title of the first publication on the list and the agent adds the title "paper title", adds the user-selected publication, and adds all of the remaining publications to the column. The cell at the top of the filled-in column has a white background, indicating a human selection while the cells below have an orange background, indicating that the agent selected these elements. In this example, the user only needs the publication title from the first page; however, if the user required additional elements from this page, right-clicking and selecting "Copy to Mixer" would cause the agent to create additional columns. Earlier Mixer interface designs allowed users to simply copy and paste elements from the target page to the workspace. However, we observed that people had trouble understanding what was "legally" selectable since they could never see the underlying data scheme. In addition, they had trouble copying and pasting text that appeared as a link. In the current design, the highlighted elements on the target page are intended to clarify what can be selected and the right-click action allows users to add an element that is a link, without navigating away from the target page.

In our previously reported evaluation of the Mixer interaction design, we noted that some participants struggled to create an effective table . Using the example of the publications, many would copy and paste the first publication title into the top of the first column and then they would copy and paste the second title on the list to the top of the second column. To prevent users from making this mistake, Mixer automatically fills in the first column as soon as the first element is selected. Now that the user has a column with all of the publication titles, the user next needs to demonstrate that they also want authors to go with each publication. To advance the task, the user navigates through the publication link causing the target page to change from the publication listing to the publication detail page.

Mixer detects that the user's action depends on the contents of a cell in the workspace, i.e. the link corresponds to the first publication. Accordingly, Mixer begins an implicit loop over all publications in the column. An additional wrinkle which does not appear in the demonstrated task, is when a user must type input from the workspace into a query form on a separate page. In such cases, Mixer prevents direct typing because the agent needs to be shown an explicit connection between the contents of a cell in the workspace and the input to a query. When a cell's contents are copied to the clipboard and then pasted into a form's widget, Mixer is able to deduce the connection. When the cell's contents are simply typed into the widget, however, Mixer cannot be certain that the query input in fact comes from the workspace entry rather than from elsewhere in the page; to avoid this problem, Mixer issues a warning to the user when directly typing into a query form. In a more extreme case, the administrator might modify the contents (e.g. stripping off the first name and using only the last name), making the matching of the contents to the workspace quite difficult. This tension between re-using a variable by value and by reference has a long history in PBD, see e.g. the discussion of distinguishing constants from variables in Myers [START_REF] Myers | Peridot: Creating User Interfaces by Demonstration[END_REF].

Mixer augments the publication detail page: selectable elements are highlighted in orange. These elements include the publication's authors' names, as well as the venue where the publication appeared (Figure 1B). The user right-clicks the author's name and selects "Add to Mixer." In response, Mixer creates a new column, adds the title "author name", fills in the first row with the selected author name, fills in subsequent cells with additional coauthor names available from the current page, and fills in the remaining rows with a dashed line, indicating that the agent thinks the user wants this information for subsequent publications. Similarly, the user adds "author affiliation" information to the table from the same page.

To release the agent to complete the table, the administrator clicks the "Fill Table" button to the right of the last column. In response, Mixer infers and executes a program. In this example the program contains a loop over all publications in the publication listing. Mixer iterates over each publication, one by one. For each publication, Mixer navigates through the link using exactly the same action sequence which the administrator demonstrated, modified only to correspond to the present publication. As each detail page is visited and its result integrated, the browser view shows exactly what is happening, giving the administrator confidence that the result is the same as if the task were performed manually. When the table is complete, Mixer plays a chime, letting the user know the agent is finished (Figure 1C).

Administrators frequently want to collect information about a subset of items that meet some criterion, for example the students who were currently failing a particular course. Since administrators are familiar with spreadsheets, we postulated that they would be able to conceptualize the filtering task as composed of the subtasks of retrieving the desired information about the whole group, then sorting on the selection attribute and cutting out all nonqualifying rows. This functionality is present and familiar in modern spreadsheets, so Mixer does not re-implement it, but rather expects the user to use a separate spreadsheet tool (our experiments used Google Docs).

Our previous simulation of the Mixer interface illuminated the way for the present implementation; however, as noted by Sundström et al [START_REF] Sundström | Inspirational Bits: Towards a shared understanding of the digital material[END_REF], the Wizard-of-Oz methodology only allowed a certain level of familiarity with the algorithmic material. The actual implementation explored some new design potential and constraints. One notable example is that the implementation must take into consideration the time taken for the actual retrieval, balancing the time consumed by the network latency inherent in retrieving information from the web with the user's valuable time and attention. The implemented system, unlike the Wizard-of-Oz mockup, does not begin with access to the retrieved data. Instead the user must wait while Mixer replays the demonstrated actions necessary for retrieval. The present design replays the actions in front of the user's eyes; this furthers communication between the user and the agent in that the user understands what is happening and why it is taking time.

Relatedly, the present design fills in as much of the table as it can as soon as the user selects a piece of data for inclusion. This refinement allows Mixer to communicate more effectively its understanding of the table as the table is constructed. We thereby lessen some of the issues participants encountered with our previous design, as to how to construct the table.

Additionally, constructing the table as soon as data is available allows more efficient use of the user's time. Specifically, in the previous design users engaged a tool we called the "resolver" to help specify if they wanted a single element, a subset of element, or all elements within a column. In an actually executing system, however, this means the user must make resolver decisions periodically throughout the retrieval process, with lags of unknown length between decisions. In addition, in designing the resolver tool we struggled to find a way for users to precisely specify what they specifically wanted that did not feel like programming. The current design takes a different tack. It drives users to collect a complete set of data, and then allows them to export the table they have made to a spreadsheet, where they can use the familiar tools of spreadsheets to sort and perform calculations. This design choice gains significant ease of use at the cost of making precision more laborious.

Two other changes from the previous design bear mention. First, whereas the previous design presented the user with the target page and invited her to select any page element, the current design instead pre-highlights the selectable elements on the page. This clearly communicates to the user which actions Mixer will understand, but decreases the ability of a user to apply Mixer to novel pages. Second, we constrain the user to copy and paste data from the workspace into a query page, rather than typing.

Wrappers

Mixer augments the target page with orange highlights to indicate selectable elements. The agent performs this augmentation by applying a wrapper to the page. A wrapper is a small piece of code that identifies the types and location of data within the page. Each time a new web page is visited, Mixer consults a database of wrappers, selects the most appropriate wrapper for the page, and applies the wrapper to the page. Based on the application of the wrapper to the page, Mixer highlights the wrapped data on the page, as shown in Figure 1, and adds the appropriate user interaction bindings. The use of wrappers represents a departure from the previous Mixer interface. The wrapper directly encodes the hierarchical relationship among the potential columns, allowing the agent to automatically fill in the first column as soon as the first element has been selected.

An obvious bottleneck for the applicability of Mixer is the coverage of its database of wrappers, raising the question of how this database would be populated. The present work makes the simplifying assumption that the database is pre-populated with all necessary wrappers. For real world usage, several possibilities exist. First, IT shops who are interested in offering Mixer capability to their customers might code wrappers for their internal websites and distribute a version of Mixer with access to those wrappers. Alternately, a crowd of third-party developers might contribute wrappers for web pages to an internet-wide repository for use internet-wide, as is done with public GreaseMonkey [START_REF] Boodman | Greasemonkey[END_REF] or CoScripter [START_REF] Leshed | CoScripter: automating & sharing how-to knowledge in the enterprise[END_REF] scripts. An extension of this approach is to deploy tools (e.g. Mash Maker [START_REF] Ennals | Intel Mash Maker: join the web[END_REF] or reform [START_REF] Toomim | Attaching UI enhancements to websites with end users[END_REF]) enabling end users to participate in this crowd-sourcing construction of the wrapper repository. Mash Maker [START_REF] Ennals | Intel Mash Maker: join the web[END_REF] maintains exactly such a repository of wrappers contributed by end users. The Accessibilities Commons [START_REF] Kawanaka | Accessibility commons: a metadata infrastructure for web accessibility[END_REF] maintains a similar database of web accessibility enhancements, designed to crowd-source a solution to the accessibility problem.

More formally, a wrapper overlays a relation, i.e. a list of one or more tuples, over the page. The wrapper specifies the type of the tuple as an unordered list of text fields and subrelations (with tuples specified in the same way1 ). Each tuple and "leaf" field is located with an XPath expression [START_REF] Clark | XML Path Language (XPath) Version 1[END_REF], interpreted relative to its parent tuples; thus the addressing is similar to that in the Accessibilities Commons [START_REF] Kawanaka | Accessibility commons: a metadata infrastructure for web accessibility[END_REF]. To minimally overcome the limitations of identifying fields with DOM elements (see e.g. Dontcheva et al [START_REF] Dontcheva | Summarizing personal web browsing sessions[END_REF]), fields may optionally refer to a regular expression matching some of the tokens within the chosen element. Thus the Mixer wrapper formalism is sufficiently expressive to wrap pages with a uniformly repeating tuple-type where tuples and fields are contiguous within DOM elements. Partly as a tradeoff for this expressivity, Mixer wrappers are nontrivial to specify; thus the sheer number of wrappers required for widespread Mixer usage seems to present a more limiting bottleneck than the limitations of the expressivity of the wrapper formalism.

Mixer Program Induction

Generally, program induction is the task of constructing a program based on a small number of example executions of the program. Mixer performs program induction by observing the browser actions as the user performs the demonstration, and forming a program which will be executed when the user asks to complete the table.

In order to reduce the prohibitively large search space [START_REF] Lau | Programming by Demonstration Using Version Space Algebra[END_REF] of programs consistent with the demonstration, Mixer leverages relatively strong assumptions about the Mixer domain to decompose the induction problem into several smaller subproblems 2 . The assumptions about the domain are:

 Universality: All loops are repeated over all instances in their scope  Quantification: All loops are scoped over the values in a workspace column  Task Focus: Only actions which change the workspace can affect the program The learning mechanism records all browser actions in a log of actions. The log contains the user's actions without modification or generalization of any kind. Parallel to the log, Mixer constructs the program, which represents the best guess about the repeatable procedure whose output the user desires. The instruction set contained in the program are the same as the browser actions contained in the log, with the addition of parameterized versions of each action as well as a looping foreach structure. Additionally, a program begins with a preamble which loads the starting page where the replayed browsing actions will commence.

The learning mechanism appends each observed browser action to an accumulated list of steps. The first sub-problem is to classify a given sequence of steps as to whether it forms a complete unit of action, which should affect the program in some way. The Mixer implementation presented here uses a simple heuristic, considering only step sequences terminated by a step inserting new content into the workspace.

Given that a unit does affect the program, Mixer next decides how it does so. The sequence of steps in the unit is decomposed into the transition, the query, and the selection. The query determines how data from previous columns drives widgets to perform the web lookup, and the selection selects information to be inserted into the workspace; the transition contains any preparatory steps which are not datadependent 3 . The steps in the transition are simply appended to the program at the current insertion point, and afterward a new loop is appended, quantified over the entity type used by the query. The steps of the query are parameterized to depend on data from columns in the workspace, then appended inside the new loop. Finally, the insertion point is advanced to the current end of the loop. The current implementation of Mixer makes no effort to track previous positions of the insertion point; as a consequence the "undo" operation only functions back to the insertion point. Beyond the insertion point, the user cannot effect any changes to the underlying program, so in case of error must restart the session.

The selection is converted into a single atomic command for extracting all content from the visited page. While inserting new content into the workspace always appears to the user to change the workspace, only the first piece of data taken from a visited page actually affects the underlying program. The workspace, meanwhile, contains all the data from the page but only displays the pieces the user has demonstrated so far. Upon demonstration of the addition of subsequent pieces of information to the workspace, the program is unchanged; only the visibility flag for the affected column is toggled. This low-level distinction is made invisible to the user.

Evaluation

We recruited administrators to perform a user study aimed at substantiating the following hypotheses:

 H1: Mixer's table-based workspace interface provides an effective method of communication between the human and the agent for data integration tasks:  Administrators can conceive of and express information demands through designing and demonstrating the form of the information in the workspace.

 Administrators can make sense of, and work with, information retrieved in collaboration with an agent and presented in the workspace.  H2: Administrators will recognize the benefit of automated data integration and would be interested in using this interface for their work. In order to test these hypotheses we culled administrative tasks from the suggestions of participants in our previous Wizard-of-Oz study of the Mixer interface [START_REF] Zimmerman | User-created Forms as an Effective Method Of Human-agent Communication[END_REF]. To accommodate privacy concerns, we shifted the tasks to different real-world domains, where we selected isomorphic tasks which pilot participants demonstrated could realistically complete within a 90 minute experiment. Because Mixer is not intended as a walk-up-and-use system, participants were provided with a grounding introductory spiel and an experimenter-directed training task. After the completion of those tasks, the participants were asked to think-aloud while completing the remaining experimental tasks. The experimenter provided no assistance to the participants during the completion of the tasks.

We recruited N=12 administrator volunteers for an experimental session lasting about 90 minutes. They were paid $15/hour for their time. Volunteers were asked if they had experience with programming, and those who did were disqualified from participation. We began by introducing the tool and acquainting the users with its goals and concepts. The experimenter then introduced participants to the concept of the thinkaloud experimental setup.

Next users completed a preliminary survey detailing their background level of computer usage and expertise. To ensure that users understood the task we asked them to take three minutes to complete as much of a task as they could manually, specifically by copying and pasting directly from the Association for Computing Machinery (ACM) website into a spreadsheet.

Then, to illustrate the use of the system, the participant performed a representative Mixer task with minute direction from the experimenter. The training task was:

 Task 0: Find all researchers from Institution X who published in the latest conference of Conference Z Then, one by one, we asked them to respond to messages in a pre-loaded email account. Each message contained a request from a contrived boss for the completion of an experimental task; users indicated completion of the task by replying to the email with their best attempt at the answer. During the completion of the tasks, the participants' actions and audio were recorded using Camtasia for later analysis.

 Task 1: Find all researchers from Institution Y who published in the latest conference of Conference W  Task 2: Find all coauthors of Researcher R in the last three years  Task 3: Find email addresses for all members of Club C  Task 4: Find all coauthors of Researcher S in the last three years The tasks were mostly from the ACM domain in order to minimize the amount of domain knowledge presupposed or learned in-experiment on the part of the participant. Task 1 was chosen as an isomorph of the demonstration task to cement the participant's understanding of the process of extracting a subset, then using spreadsheet functionality to select the appropriate subset. Task 2 has the same form, but the web interactions are novel, sometimes changing which pieces of information require a new server response. Task 4 is a repeat of Task 2 with different parameters, but introduces a minor complicated factor that Researcher S's first paper is published alone (i.e. the only coauthor is the first author). Task 3 is completely novel in the sense that the output of one website is used as the input of another. Participants were not instructed how to use Mixer to combine data from multiple websites, nor were they alerted that Task 3 had any characteristic different from the rest.

Additionally, Tasks 2 and 4 had two different solution paths. The ACM listing of an author's publications lists all publications with links to pages about the individual papers; alongside the link is a listing of metadata about the paper including authors and publication date. Thus the problem may be solved within a single page, since all needed information is present in the page. Alternately, the problem can be solved by extracting the required metadata from each publication's page in turn.

Following completion of the tasks, participants answered a post-study questionnaire containing the TAM3 [START_REF] Venkatesh | Technology Acceptance Model 3 and a Research Agenda on Interventions[END_REF] (Technology Acceptance Model 3) instrument. TAM3 measures a new technology's perceived usefulness and perceived ease of use. Previous research shows a strong relationship between these two perceptions and eventual system use. TAM3 responses were made on a 7-point Likert scale (1 = "extremely unlikely to use," 4 = "neither," 7 = "extremely likely to use").

Findings

After the participant had correctly communicated the desired behavior to Mixer, Mixer turned control back over with a filled table of data. In 42 (about 88%) of the tasks the participant was able to correctly filter the data and direct the completed form to the experiment's simulated boss. In one case, a participant was unable to do so for Task 1 and gave up; that same participant was able to correctly marshal the data in the subsequent tasks. In four cases, participants needed one or two more attempts to effect the correct answer. In one case, a participant needed five attempts.

Our 12 participants successfully completed all tasks. They eventually constructed all of the necessary tables with the agent's help. Because the experiment required the participants to thinkaloud as they worked, the amount of time participants took to accomplish the task is not meaningful; instead, we record the number of attempts they made before they were able to productively turn control over to Mixer. We counted an attempt every time the participant started over with a fresh workspace during the completion of a task. All participants' number of attempts are presented in Figure 2.

Participants exhibited some difficulty constructing a workspace table containing all of the information required to complete the task. 17 task attempts failed due to missing query attributes, for example by failing to include students' names when only email addresses were strictly required. Two participants successfully extracted a spreadsheet, only to find that missing selection attributes precluded them from sorting and filtering down to the correct answer. They immediately re-demonstrated the correct workspace without error.

Two participants constructed a table without an attribute explicitly requested, then corrected their oversight. Of the overlooked attributes of all categories, only one instance occurred in the final task. Several participants appeared to struggle with Mixer's expectation that the user would only provide information in the first row, leaving Mixer in charge of filling subsequent rows. Three participants, all in Task 3, tried to continue filling subsequent rows before clicking on "Fill Table ."

Two participants, again in Task 3, attempted to search multiple email addresses at once by pasting all the names, separated by spaces, into the search box; in response, the directory application returned no results and the participants started over. One participant attempted to explicitly select a column of attributes from the target page.

Another common breakdown occurred with respect to participants' decision to invoke the program by pressing the "Fill Table " button. One participant chose to restart Task 1 after exporting a table with unfilled cells, i.e. failing to invoke the program at all. Four participants discovered a solution to Task 2 that did not require the use of the "Fill Table" button to complete the task. They then expressed confusion that the "Fill Table" button was inactive. Two of the confused participants precipitously restarted after encountering the confusion. All four participants used the same approach on Task 4 and did not hesitate to complete the task without using the "Fill Table" button. Three additional users discovered this approach while completing Task 4. Each expressed confusion that the invocation button had no effect, but all pressed onward and successfully completed the task.

Eight participants encountered the dialog box warning against typing in a query field. One successfully circumvented the dialog, typing in the information and thereby causing the task attempt to fail. One user attempted to select data not recognized by the wrapper and send it to Mixer.

Figure 3 shows participants' responses to the TAM instrument. The Cronbach alpha scores, all above 0.8, indicate that the scores are internally reliable, in the sense that answers to multiple questions seem to measure the same underlying construct.

Many users expressed pleasant surprise at the capabilities of Mixer, using adjectives like "cool", "awesome", and "brilliant." One user said "I want this program. Even if it can't find everybody" and another asked "When can I get this?" All of these laudatory quotes came immediately after the user was able to successfully complete Task 3. Two users praised the visibility of Mixer's practice of showing each visited page as the table is filled. Two participants expressed displeasure at the use of Google Docs for the spreadsheet export; they claimed to be more proficient with Microsoft Excel. During the closing interview, several participants inquired when Mixer would be available to them for their jobs. Administrators could successfully use Mixer to automate tedious information retrieval tasks. They were successful at creating the first row of a table as a way of communicating to an agent the information they wanted. At first, many administrators struggled to complete a task. Sometimes this was caused by software bugs in Mixer, and sometimes it was caused by participants struggling to conceive of tables the agent could act upon. The agent often needs more context (additional columns) to complete an action than the administrator strictly needs to complete their task. Administrators struggled with including this context, indicating that, initially, they had trouble seeing the problem from the agent's perspective. However, the reduction in the number of attempts needed to successfully complete a task from the first task to the fourth task (Figure 2) provides some evidence that administrators can quickly learn to conceive of the tables in a way that allows the agent to assist them with their task.

Mixer supports two types of tasks: repeated retrieval from within a single data source, and retrieval from across more than one data source. We expected that working with more than one data source would be more difficult, but we did not see evidence for this. A comparison of the number of attempts made on Task 3, which required participants to connect two data sources, to the other three tasks that all use a single data source (Figure 2) does not indicate that participants found the multiple data-source task more difficult. In addition, we see nothing in the utterances during the thinkaloud to indicate that participants made any kind of distinction between these tasks. Though administrators struggled with the fact that Mixer requires copying and pasting into forms instead of typing, they did not seem to find demonstrating a link between data sources challenging. This finding is especially interesting in the light that, as indicated above, participants were not supplied with any hints to how to effect a link between multiple data sources.

The use of wrappers to augment the target page with a highlight indicating a legally selectable element provides a design advance. The highlights were intended to help users understand the limitations of the agent's communication ability and to help negotiate the problem space between human and agent. In our previous iterations of the interface, we allowed users to copy and paste from the target page directly into the workspace table, and this often lead to breakdowns. Participants seemed to have no trouble understanding how to use these highlights and never expressed any utterances or opinions that this limited their ability to use Mixer to automate their work. We think this technique could be used in many other mixed-initiative interfaces, where users struggle to understand the scope of what the agent can do.

Mixer's interaction design specifically avoids the challenge of precise specification: the need to communicate that the user wants only a subset from within a larger set of data. Instead, the agent retrieves the larger set and encourages users to use a spreadsheet to filter down to the precise information. The fact that participants were able to correctly do so using a spreadsheet corroborates the notion that end users can conceive of the task as a nested table, and furthermore that the unnesting of the table into a spreadsheet table is an intuitive concept for administrators.

TAM produced very high ratings for Mixer for Perceived Ease of Use, Perceived Usefulness, and Behavioral Intention (to use). Scores of 6 or above on a seven-point scale give us confidence that administrators recognize the value of automating their tedious information retrieval tasks and that they would likely use Mixer in their work. Additionally, users gave a high TAM score to the quality of Mixer's output. This may be due in part to Mixer showing exactly which pages contributed to the result as it filled in the table. Several participants singled out this aspect independently for praise.

Mixer's interaction design specifically deemphasizes and to a certain extent even hides the fact that users are engaged in a programming task when they construct the first row of the table. This is a radical departure from most work in the web PBD community. We speculate that systems that similarly deemphasize the programming aspect of the task will generally be more likely to succeed with nonprogrammers. Much more work would need to be done to rigorously evaluate this speculation, though the fact that administrators with no programming experience could successfully use Mixer and their high TAM scores reflect positively, as does the fact that nonprogrammers have struggled with other PBD systems. In the same vein, more work would need to be done to show that the administrators' resistance to programming stems from the sense that the work is perceived to fall outside the scope of what their job should be. We can suggest that this is a rich direction for further research on PBD interfaces.

In terms of PBD, Mixer embraces the notion that administrators would be disinclined to use a tool that feels like programming. The most obvious Mixer design decision in this line is that the user does not see the program as lines of code, nor as an equivalent data-flow representation of the procedure. A more subtle example is the way Mixer enforces copying and pasting as, from the user's perspective, an arbitrary constraint, rather than asking the user to understand the programming concept of using a variable as opposed to its value. Consequently, in terms of PBD systems, Mixer is near one extreme of the spectrum, ranging from those that expect the user to construct an explicit model of the program as a sequence of low-level actions, to those that do not. The success of our participants in using Mixer, as well as their recognition of its relevance and applicability to their jobs, seems to lend credence to this notion: the less end users feel like they are engaging in "programming" while using a PBD system, the less likely they seem to be to eschew the system as unrelated to their realm of responsibility.

Related Work

Nardi [START_REF] Nardi | A small matter of programming: perspectives on end user computing[END_REF] notes the widespread use of sophisticated forms in human-human interaction, and the surprising facility of nontechnical people in rapidly learning and making use of them. She also observes that users can more readily assimilate new formal representations when they have a preexisting interest or job-related requirement to do so. Rode et al [START_REF] Rode | The fuzzy felt ethnography--understanding the programming patterns of domestic appliances[END_REF] note the same phenomenon. They note the similarity between ovens and VCRs in terms of programming. Abstractly, both devices allow users to instruct a device to turn on at a specified time and run for a specified duration, and to set the state of a specific feature: the channel of the VCR and the temperature of the oven. Surprisingly, despite the indistinguishability of the tasks at the abstract level, they found a pronounced gender difference in users' abilities to perform the tasks. Women, who generally exert more control over the kitchen, had more success programming ovens, and conversely, men, who generally exert more control over entertainment devices in the home, had more success programming VCRs. These research results lead us to speculate that one reason office workers have not readily accepted PBD systems is that they cast the task as "programming": a type of work that generally falls outside the common social role description for an administrator. Mixer addresses this by specifically disguising the fact that the administrator is programming when interacting with the tool.

Malone et al note the potential of semi-structured forms as a means of expressing human practice and intention in a manner that is amenable to agent assistance [START_REF] Malone | Semistructured Messages Are Surprisingly Useful for Computer-Supported Coordination[END_REF]. Their work focuses on structuring email conversations so that agents can assist in the coordination of human activities, essentially providing a mechanism for the agent to eavesdrop on the human communication. VIO [START_REF] Zimmerman | VIO: a mixed-initiative approach to learning and automating procedural update tasks[END_REF] complements Malone by providing the reverse: a form mechanism whereby users are given insight into the actions of the agent, and hence the opportunity to identify and repair agent errors.

Nardi and Miller [START_REF] Nardi | The Spreadsheet Interface: A Basis for End User Programming[END_REF] build on the work of Lewis and Olson [START_REF] Lewis | Can principles of cognition lower the barriers to programming?[END_REF] in singling out spreadsheets, which can be viewed as frameworks for the creation of ad hoc forms, as an emblematic context where people routinely "program", in the sense that they induce nontrivial computational behavior. Nardi and Miller delineate several specific aspects of spreadsheets which render them particularly acceptable to end user interviewees. First, the computational paradigm of spreadsheets matches the way the end user conceptualizes the task; Norman [START_REF] Norman | Cognitive Engineering. In: User centered system design: new perspectives on human-computer interaction[END_REF] characterizes this alignment as bridging the "Gulf of Execution" between the user's conceptualization of the goal and the system's formalism. In particular, the high-level functions provided by the spreadsheet shield the user from the difficult task of "synthesizing" the desired functionality from simpler primitives. Secondly, spreadsheets compactly represent the entire task in a single tabular view, often on a single screen.

Our previous Wizard-of-Oz study of Mixer demonstrated that these advantages of spreadsheets apply to administrators approaching data integration tasks, specifically pointing out the conceptual alignment between user and agent as well as the unified nature of the shared table representation. Several other systems settle on a similar tabular interface between the user and an observing PBD web data integration agent. Vegemite [START_REF] Lin | End-user programming of mashups with vegemite[END_REF] asks the user to create a set of "VegeTables," each of which corresponds to a script for combining two websites. Karma [START_REF] Tuchinda | Building Mashups by example[END_REF], Dontcheva et al [START_REF] Dontcheva | Relations, cards, and search templates: user-guided web data integration and layout[END_REF] and Mashroom [START_REF] Wang | Mashroom: end-user mashup programming using nested tables[END_REF] build separate tables for each extracted website; additionally, Mashroom explicitly uses nested tables (specifically with an eye towards comprehensibility by end users). Each of these systems asks the user to explicitly "merge" extractions from different websites into a coherent table. In contrast, Mixer encourages the user to construct the single, unified table that seems to match her underlying conceptualization of the task. This spares the user the confusion inherent in synthesizing, or merging, the results of the various subtasks together. As a consequence, Mixer enables users to construct integration tasks over one website, or over several websites, without necessarily observing the distinction.

Mixed-initiative research focuses on advancing methods for collaboration between computer agents and people where each party has its own knowledge, ways of reasoning, and abilities to understand and act in order to advance toward a common goal [START_REF]Mixed-Initiative Interaction[END_REF][START_REF] Horvitz | Reflections on Challenges and Promises of Mixed-Initiative Interaction[END_REF]. Many issues remain to be answered, including several interrelated needs with respect to interaction between agent assistants and people [START_REF] Tecuci | Seven Aspects of Mixed-Initiative Reasoning: An Introduction to this Special Issue on Mixed-Initiative Assistants[END_REF]:

 Awareness: knowledge of problem and goal must be shared by human and agent  Task: roles and responsibilities must be shared between human and agent  Communication: both human and agent must be able to express knowledge and needs. PBD interfaces present a particular challenge with respect to the awareness issue: the user and the system have a fundamental mismatch with respect to the goal of the interaction. The central goal of a PBD system is to infer a program from the user's actions; for the user the construction of the program is subsidiary, at best, to the goal of completing some task. As noted above, Rode et al [START_REF] Rode | The fuzzy felt ethnography--understanding the programming patterns of domestic appliances[END_REF] observe that users are far less successful in performing programming tasks outside their perceived area of responsibility. Consequently, Mixer explicitly attempts to avoid presenting the user with tasks that feel like programming.

The task issue concerns the division of action between humans and agents. The principal actions of a PBD session [START_REF] Kosbie | PBD Invocation Techniques: A Review and Proposal[END_REF] are program demonstration (or creation), program invocation, and program execution. Mixer incrementally constructs a program by observing all actions taken within the browser, from the time that the user invokes Mixer to the time that the user presses a button to invoke the demonstrated program. Mixer then executes the program. Thus Mixer presents a strong distinction between user actions (before invocation) and system actions (after invocation). This separation of activity is stricter in Mixer than in some PBD systems, such as Eager [START_REF] Cypher | Eager: Programming Repetitive Tasks by Demonstration[END_REF], which assist the user in deciding when to invoke the observed behavior.

The communication issue arises in a couple of ways from what Cypher [START_REF] Cypher | End User Programming on the Web[END_REF] calls the classic challenges of PBD: (1) inferring the user's intent; and (2) presenting the created program to the user. The first challenge concerns the user communicating with the system via the demonstrated actions, and the second challenge concerns the system communicating the recorded action sequence to the user.

The first challenge arises because the user's actions usually insufficiently delineate a unique program, a point illustrated by Lau et al with an explicit version space argument [START_REF] Lau | Programming by Demonstration Using Version Space Algebra[END_REF]. PLOW [START_REF] Allen | PLOW: A Collaborative Task Learning Agent[END_REF] receives richer input from the user by eliciting and utilizing natural language explanations for the user's actions. Wrangler [START_REF] Kandel | Wrangler: Interactive Visual Specification of Data Transformation Scripts[END_REF] asks the user to select after each action the statement in the implementation language corresponding to the level of generalization required. Rather than eliciting additional input from the user, Mixer overcomes the problem by exploiting rather strong simplifying assumptions about the types of problems Mixer is expected to solve.

The user has the responsibility to demonstrate their knowledge of a single row of the table, and Mixer assumes full responsibility for inferring the best possible procedure from that demonstration. Although the user need not understand the workings (or even the existence) of the program, the user does need to be aware that the agent is observing; in other words, the user is expected to take an "intentional stance" [START_REF] Dennett | The Intentional Stance[END_REF][START_REF] Maulsby | Metamouse: An Instructible Agent for PBD[END_REF] with respect to showing Mixer how to perform the desired task. Mixer asks the user to intentionally demonstrate similar information to that detected automatically by TX2 [START_REF] Bigham | Mining web interactions to automatically create mash-ups[END_REF].

As to the second challenge, Modugno and Myers [START_REF] Modugno | Graphical Representation and Feedback in a PBD System[END_REF] further delineate the communication role played by the program in PBD systems, as a list of opportunities presented to the user:

1. the user can confirm that the program will behave as desired; 2. the user can correct or generalize the program; and 3. the user can store all or part of the program for later use or modification. Mixer provides limited information about the inferred program through the intermediate depiction of the workspace, giving the user implicit confirmation responsibility as well as some ability to correct unexpected columns in the workspace.

Although many PBD systems outside the web context communicate the program in forms other than as lines of code, the code approach is the most common in web PBD systems. Chickenfoot [START_REF] Bolin | End-User Programming for the Web[END_REF] records web actions as general JavaScript. CoScripter [START_REF] Leshed | CoScripter: automating & sharing how-to knowledge in the enterprise[END_REF] chooses a slightly more user-friendly approach, representing the program in a "sloppy" or natural programming language. Query-by-Example and Office-by-Example [START_REF] Zloof | QBE/OBE: A Language for Office and Business Automation[END_REF] utilize a form as a shared communication structure, but require a user to understand and specify programmatic variable structure within the forms. Mixer uses a single nested table form as the principal communication medium between the human and the agent, which diminishes the variety of programs Mixer can produce but dramatically simplifies the user's interaction with the system.

Over the last few years there has been a great amount of research interest in streamlining the process of creating web mashups [START_REF] Beemer | Mashups: A Literature Review and Classification Framework[END_REF]. By focusing on ad hoc reports rather than mashups (i.e. the output rather than the program), Mixer differs philosophically from many mashup projects; in particular, Mixer aims to allow users to conceptualize data integration problems uniformly, whether or not some pieces of information lie across web server boundaries. Whereas mashup systems emphasize reusability and generality, Mixer focuses on how administrators can retrieve and integrate the types of data they need for their jobs.

Nevertheless, Mixer shares some overlap with mashup systems in that Mixer presents a user-friendly solution to the source modeling and data integration problems, with particular attention to the database joins. Thus, Mixer could coexist in a mashup ecosystem with user-appropriate solutions to wrapper generation (e.g. reform [START_REF] Toomim | Attaching UI enhancements to websites with end users[END_REF] or the summaries of Dontcheva et al [START_REF] Dontcheva | Summarizing personal web browsing sessions[END_REF]) or data cleaning (e.g. Potters Wheel [START_REF] Raman | Potter's Wheel: An Interactive Data Cleaning System[END_REF] or Potluck [START_REF] Huynh | Potluck: Data Mash-Up Tool for Casual Users[END_REF]). Mash Maker [START_REF] Ennals | Intel Mash Maker: join the web[END_REF] provides a representative mashup ecosystem, distinguishing between end user-specified wrappers and developerprovided widgets, which combine and visualize the wrapped data. In this perspective, Mixer presents a mechanism for nonprogrammers to create useful widgets without developer intervention.

Conclusion

Mixer advances mixed-initiative PBD interaction through a novel user-constructed nested table communication method that allows users to declare the outcome they want while implicitly demonstrating how the agent should programmatically perform the task. Mixer specifically allows administrators to automate repetitive web data retrieval and integration tasks they find to be tedious to perform. Our evaluation of the system shows specifying the table to be an effective method for people and the agent to communicate their varying knowledge and needs. The evaluation also reveals a strong likelihood that administrators would use Mixer if it were available to them. The interaction presented in Mixer represents a transition in how office workers engage in computing. Instead of forcing workers to rely on their ability to adapt to the

Figure 1 :

 1 Figure 1: A user interacting with Mixer to extract the coauthors of a researcher based on the researcher's papers on the ACM Digital Library

Figure 2 .

 2 Figure 2. Number of attempts to construct the correct workspace

Figure 3 .

 3 Figure 3. Participants' ratings of Mixer along TAM constructs

The allowance for subrelations expands the expressivity of Mixer wrappers to nested tables, also known as non-first normal form relations (see e.g.[START_REF] Wang | Mashroom: end-user mashup programming using nested tables[END_REF])

This decomposition was chosen to be amenable to Machine Learning classification.

The transition would contain interactions with widgets of a form which are universal to the tuple, but not to any particular value of a field. For example, checking a checkbox choosing to search for people rather than, say, departments, would be included in the transition; the query would continue by specifying which person to search for.

design of IT systems, Mixer empowers workers to leverage their expertise in web data retrieval to train agents to undertake tedious information integration tasks for them. This work is supported by grant number H133E080019 from the United States Department of Education through the National Institute on Disability and Rehabilitation Research.


Juan F Mancilla-Caceres

Eyal Amir

Evaluating Commonsense Knowledge with a Computer Game

Collecting commonsense knowledge from freely available text can reduce the cost and effort of creating large knowledge bases. For the acquired knowledge to be useful, we must ensure that it is correct, and that it carries information about its relevance and about the context in which it can be considered commonsense. In this paper, we design, and evaluate an online game that classifies, using the input from players, text extracted from the web as either commonsense knowledge, domain-specific knowledge, or nonsense. A continuous scale is defined to classify the knowledge as nonsense or commonsense and it is later used during the evaluation of the data to identify which knowledge is reliable and which one needs further qualification. When comparing our results to other similar knowledge acquisition systems, our game performs better with respect to coverage, redundancy, and reliability of the commonsense acquired.

Introduction

A vast amount of information about the world is needed to create an artificial commonsensical agent [START_REF] Mccarthy | Programs with common sense[END_REF]. This kind of knowledge, which includes facts about events, and objects, is what we call commonsense knowledge. Collecting commonsense knowledge is difficult because it is dynamic and dependent on context. This makes it impossible to generate it randomly and to verify it automatically, which implies that humans are needed to either collect the commonsense knowledge or to verify it.

The main difficulty of needing humans is that they need to be encouraged to participate. As previous studies show [START_REF] Downs | Are your participants gaming the system?: screening mechanical turk workers[END_REF], contributors tend to produce noisy data even when they are paid for their services because they are trying to maximize the reward, whether they are producing the right data or not.

In this paper we introduce a game that takes text extracted automatically from the Web and uses input from players to verify it as commonsense. The main difficulty of this approach lies in the fact that the game needs to encourage players to supply the correct information. With the help of the players, our game classifies the knowledge as commonsense, domain-specific, or meaningless. It also reports if more information about a given fact is needed in order to classify it correctly. Correctness of the data is ensured through the design of several stages within the game, and through restricting communication among players. Also, we create a continuous scale that ranges from nonsensical (or unknown) sentences to commonly known facts. A discretization of such scale can be used to classify the sentences as commonsense or not. This scale also allows us to clearly identify which knowledge needs revision.

The focus of this paper is to present a method that provides guarantees on the correctness of the data collected through a game. Although the design of the game does not constrain the source of the input data, we are currently obtaining it from Simple Wikipedia [START_REF]Simple Wikipedia[END_REF] because some of its policies regarding the content of the articles are appropriate for commonsense extraction. For example, unverified research is not allowed in any article. Within a period of five weeks, more than 150 people played the game and more than 3,000 sentences were evaluated.

Related Work

The best known approaches to gather commonsense are Cyc [START_REF] Lenat | Cyc: toward programs with common sense[END_REF] and OpenMind [START_REF] Singh | Open mind common sense: Knowledge acquisition from the general public[END_REF]. Cyc uses experts to input the knowledge, whereas OpenMind used volunteers. Some issues with these approaches are that Cyc requires the user to be familiar with their language, and OpenMind lacks a way to motivate volunteers to participate.

Another effort to collect common knowledge from contributors is LEARNER2 [START_REF] Chlovski | An analysis of knowledge collected from volunteer contributors[END_REF]. It collected data about part-of relations. Unlike our game, LEARNER2 lacks the capability of redirecting the user's effort to improve the reliability of data already collected. There are also several games that encourage participation of users to enter data into knowledge bases. Among these, Cyc released the game FACTory which is similar in format to the first stage of our game but does not include any way to guarantee the correct behavior of players. Verbosity [START_REF] Von Ahn | Verbosity: a game for collecting commonsense facts[END_REF], uses two players to fill in templates, and Common Consensus [START_REF] Lieberman | Common Consensus: a web-based game for collecting commonsense goals[END_REF] asks two players questions about achieving a given goal.

Combining the computational power of machines and humans has been addressed in [START_REF] Shahaf | Towards a theory of AI completeness[END_REF]. The use of a continuous scale to reason about commonsense knowledge was explored before in [START_REF] Druzdzel | Probabilistic reasoning in decision support systems: from computation to common sense[END_REF].

Game Design

The initial input information for the game comes from an off-the-shelf parser [START_REF] Hadidi | Automated knowledge extraction from wikipedia[END_REF] that extracts a sentence from an article in Simple Wikipedia and, together with the action of the user, produces an update to the knowledge base as the output.

The simplest implementation of the game would have a single user classifying sentences as either commonsense or not. This is not enough because it would be impossible to evaluate the answers of the player as correct or incorrect. Also having several players evaluating the same sentence and accepting the input only if they agree amongst one another is not appropriate because it would be easy for a group of players to act in collusion and agree on entering the same answer, regardless of the question.

The basic problem is that human players can always agree on a fixed strategy, and yes/no questions are not enough to correctly classify the knowledge. To solve this, we add a non-human player to the set of players and classify the input text in four different categories: Nonsense, Unknown, True, False. 1We devised a three player game in which the purpose of the player is to distinguish between another human and a machine. Both humans will give the same answer on the sentence while the machine will guess its answer. The design of the game solves the problem outlined before: The two humans can no longer agree on any strategy because the identity of the players is unknown. Also, if the answer of one player does not follow commonsense, the other human might erroneously identify the player as a machine, which results in a penalization on the player's score.

Because commonsense depends on the context, it is necessary to consider context explicitly. In [START_REF] Mccarthy | Artificial intelligence, logic and formalizing common sense[END_REF], the author proposes a formula Holds(p,c) to assert that the proposition p holds in context c. Using this idea, the appropriate task for the player is to answer a question based on that formula. In our case, the context is handled by the name of the Simple Wikipedia article used as source for the sentence. The context can be used by the player to answer correctly, while addressing the problem of uninstantiated sentences that may be produced by the parser.

Figure 1 shows snapshots of the game in all its stages. The game works as follows:

• In the first stage, the player chooses a topic (which matches the title of the Wikipedia article from which a sentence is to be retrieved). • A sentence is randomly selected from the article. The system chooses either a new sentence or a sentence that has been verified before. This balances the coverage and reliability of the data by increasing the times a sentence has been verified. Then, the player indicates whether the fact expressed by the sentence is true in the context of the article using the four options previously described. • In the second stage, the player sees the answer of the other two players and identifies which of the two is the machine that is answering randomly. In the case of a single player playing the game, the other answer comes from recorded games. If it is impossible to distinguish between the two players, there is an option to pass and avoid making a decision. If the player identifies the human as the machine, points are deducted; otherwise, points are awarded. • After this, the player gets the opportunity to play again.

Identifying Commonsense Knowledge

A majority vote is not enough to identify a fact as commonsense, because we have more confidence if a sentence was evaluated by a large amount of players rather than by a few. Thus, we create a scale of commonsense that describes how common a specific fact is. The scale needs to be proportional to the ratio of people who know the given fact, and also contain information about the confidence of such ratio. We first define four quantities, t count , f count , u count , n count , that hold the number of times a sentence s has been classified as true, false, unknown, and nonsense, respectively.

Definition 1. Let P σ (s) be the ratio of people that have answered true, false, and unknown over the total number of instances the sentence s has been verified. Let m(s)=t count (s)+ f count (s)+u count (s)+n count (s).

( ) ( ) ( ) ( ) ( )

s m s u s f s t s P count count count + + = σ . (1)
Under the assumption of independence, each instance of the game can be considered a Bernoulli trial. P σ (s) is then an estimator of the real proportion of people that understand the sentence. Our null hypothesis is that the ratio of people classifying the sentence as nonsense should be 0.5. If we fail to reject the null hypothesis, we must con-clude that we don't have enough information to identify the sentence as meaningful or nonsense.

Definition 2. Let e n (s) be the effect size, the difference between the actual and expected number of times the sentences have been marked as nonsense.

) ( ) ( ) ( ) ( )      + > +       - < = s e s m X P s e s m X P s p n n n 2 2 . ( 3
)
The p-value p n (s) is the probability of observing the current counters given the null hypothesis. The lower its value, the more confident we are about their values.

Table 1 shows some sentences with their corresponding P σ (s) and p n (s). Notice that P σ (s) and the p-value cannot distinguish amongst all sentences because one only considers the ratio of people that agree on the sentence, whereas the other only considers the amount of people that has evaluated the sentence. With this in mind we define π s (s), which allows us to easily classify sentences as meaningful or nonsense.

Table 1. The Id is used to refer to each sentence in the paper. Eval refers to the number of times that the sentence has been evaluated. P σ (s) and P γ (s) are the proportion of people who didn't answer nonsense, or who answer true or false, respectively. The value of π s (s) and π c (s) represents the confidence that we have when classifying the sentence as meaningful or known, respectively. The last column is the decision made with a significance of 0.1.

Id

( ) ( ) ( ) ( ) ( )    ≤ > - = 5 . 0 2 5 . 0 2 1 s P if s p s P if s p s n n s σ σ π . ( 4
)
To classify the sentence as meaningful, we only need to define a threshold α against which we can compare π s (s). If π s (s) < α we have a confidence of 1-α that the sentence is nonsense and if π s (s) > 1-α, we have a confidence of 1-α that the sentence is meaningful. Otherwise, we can only conclude that we need more players to evaluate the sentence. We perform a similar analysis to the one described previously to define a scale π c (s) that represents the fact that a given sentence s is commonly known. In order to classify a sentence as commonsense we combine both π s (s) and π c (s). Definition 5. Let π(s) represent the confidence about a sentence being commonsense.

( ) ( ) ( )

s s s c s π π π = . ( 5
)
Table 2 shows the corresponding value of π(s) of the sentences from Table 1. Notice that to classify a sentence as commonsense it requires both π s (s) and π c (s) to be high.

Evaluation

Coverage, reliability, and identifying the presence of knowledge that needs further classification are of primary interest to knowledge acquisition systems, especially when the knowledge comes from volunteer contributors. In contrast to other systems, our game offers an explicit way to detect knowledge that should be discarded due to errors or noise in the input of contributors. Also, all other previous games do not provide any way to distinguish the data that need further qualification. These features are achieved by the use of our scale π(s). If a sentence is not nonsense, commonsense or domain-specific, then the game can be directed to present it to players more often until enough data has been collected to make a decision regarding such sentence.

Among the reviewed systems, only LEARNER2 reports data about redundancy. Out of 6658 entries, only 2088 are different statements and 4416 entries yielded only 350 distinct statements. This means that they collected 1.29 entries per statement. These few entries per statement produce unreliable data, which means that only 350 statements can actually be trusted. In contrast, our game collected 6763 entries and generated 3011 evaluated sentences, with an average of 3.46 entries per statement. Therefore, our data is more reliable than that of LEARNER2. Figure 2 shows the comparison of coverage and reliability between LEARNER2 and our game. For the evaluation, we asked 4 judges to classify a random sample of 50 sentences from our knowledge base. The judges evaluated the knowledge by classifying it in these categories: "Generally/Definitively True", "Sometimes/Probably True", "Unknown" and "Nonsense/Incomplete", which correspond to Commonsense, Domain-Specific, Unknown, and Nonsense, respectively. This categories are similar to the ones used by [START_REF] Schubert | Extracting and evaluating general world knowledge from the brown corpus[END_REF]. When comparing the answers of the judges to the ones from the game, the average agreement between players and judges was 94% (α=0.1).

In comparison to the other systems, Verbosity asked the judges to rate each input as correct or incorrect; the judges reported 0.85 of the data to be correct. LEARNER2 used a scale similar to ours and reported that 89.8% of the data that was entered by at least 2 people was correctly common knowledge. Our game outperforms the previous systems.

Conclusions and Future Work

We presented the design of a game that evaluates and classifies sentences extracted automatically from the Web. The main advantage of our design is that it classifies commonsense knowledge in a continuous scale, which allows us to talk about how common a commonsense fact is. Our analysis gives us confidence about the results even when some of the players disregard the rules and create noisy data. Also, we distinguish between data that needs to be evaluated further and data that has been classified with certainty. Although the game has already provided data that shows that our approach is viable, improvements in the design of the game are possible. One feature that will be further explored in future work is the demographics of the players.

Each answer given by the player is stored according to their age group and location. This is useful because we will not only be able to classify commonsense knowledge, but we will also be able to cluster commonsense knowledge according to demographic information.

Fig. 1 .

 1 Fig. 1. Snapshot of the game. All the stages of the game are shown one below the other.

Definition 3 .

 3 Let p n (s) be the p-value of the Binomial Hypothesis Test, the probability of observing a difference in the value of a random variable of at least the size of the effect size e n (s).

(

Fig. 2 .

 2 Fig. 2. Comparison between LEARNER2 and our game

  Let π s (s) be the value that represents how much confidence we have on a sentence s being meaningful.

	Definition 4.
		Sentence	Article	Eval P σ (s) p-value π s (s) Meaningful
	1	People are known acting in	Comedy	1	1	1	0.5	Unknown
		comedies are comedians
	2 Computer can use many bits Computer	6	1	0.03	0.98	Yes
	3 For example some languages	Verb	6	0.17	0.03	0.02	No
		(e.g.Chinese,Indonesian)
	Id	Sentence	Article	Eval P γ (s) p-value π c (s)	Known
	4 It is a county in the U.S. state	Anson	9	0	0.004 0.002	No
		of North Carolina	County
	5	The level experience is	Diablo II	1	1	1	0.5	Unable
		needed to level
	6	Chess is a very complex	Chess	9	1	0.004	0.99	Yes

Table 2 .

 2 Id, Eval, π s (s), and π c (s) are defined as in Table1. π(s) represents the confidence that we have on identifying each sentence as commonsense.

	Id Eval. π s (s) π c (s)	Π(s)	Commonsense
	1	1	0.5	0.5	0.25	Unknown
	2	6	0.98	0.98	0.97	Yes
	3	6	0.02	0.5	0.01	No
	4	9	0.99 0.002 0.002 Domain-specific
	5	8	0.004	0.5	0.002	No
	6	9	0.99	0.99	0.99	Yes

If the parser extracted an incomplete sentence or any other nonsensical data, the sentence is nonsense, if the sentence was extracted correctly the content may either be known (true or false), or unknown.


Abdullah Al Mahmud
email: a.al-mahmud@tue.nl

Idowu I B I Ayoola

Jean-Bernard Martens

Designing a Playful Communication Support Tool for Persons with Aphasia

Keywords: Aphasia, Accessibility, Storytelling, Contextual interview, Assistive technology

Many studies have investigated ways to leverage communication with people with aphasia. Here, a new concept is developed for people with non-severe aphasia in a way that accesses the emotional and unaware layer of a conversation and then communicates certain information to the partner hence; introducing new dynamics and structure to a conversation. We present the concept with detailed design and expert evaluation results.

Introduction

Aphasia is an acquired communication disorder that impairs a person's ability to process language or to understand others often caused by brain injury or trauma. Aphasia affects language comprehension and generation, such that people's ability to express themselves verbally suffers [START_REF] Hillis | Aphasia: progress in the last quarter of a century[END_REF]. People with Broca's aphasia or expressive aphasia usually can understand or read what other people say or write but they have problems in expressing themselves verbally and in writing. The consequence of aphasia is that people have problems maintaining contacts with their friends cannot participate in social exchange and eventually become passive and socially isolated.

There has been a growing interest in improving the quality of life for people with aphasia through technology intervention [START_REF] Egan | Accessible internet training package helps people with aphasia cross the digital divide[END_REF][START_REF] Koppenol | When words fall short: helping people with aphasia to express[END_REF]. It has been observed that the use of assistive technology can reduce social isolation and improve independence. Therefore, new tools are emerging for specific purposes such as helping aphasics while cooking [START_REF] Tee | A visual recipe book for persons with language impairments[END_REF], using internet [START_REF] Egan | Accessible internet training package helps people with aphasia cross the digital divide[END_REF] etc. These applications support higher-level communication needs of aphasics. However, people have several other communication needs such as social closeness and information transfer [START_REF] Light | Interaction involving individuals using augmentative and alternative communication systems: State of the art and future directions[END_REF]. Up to now augmentative and alternative communication (AAC) devices have focused mainly on helping aphasics with basic communication needs [START_REF] Hux | Language Intervention Strategies in Adult Aphasia[END_REF]. Though these AACs are mostly used during therapy period they are however not conversation tools. Therefore, we see an opportunity in assisting aphasics to participate in conversations by our proposed design.

In this paper we focus on the development of a supportive device to help leverage communication with a target group of aphasic people besides using online strategies. We explore possibilities for a new communication support tool and present a final design that creates a new layer of interaction within a conversation and hopes to reconstruct the flow of information and enhance the overall experience derived from a dialogue in an unobtrusive way. This was achieved with the use of a monitored stress ball to stimulate an unaware interaction and then providing a constructive feedback to the partner. An iteration approach is observed to investigate the topic and to further develop into a final design. In understanding the problem domain, the researcher began with literature research to know ways of aiding communication or social activities for people with Aphasia. Furthermore the psychological needs for the target groups were briefly identified to settle on an approach for creating a new product for them. Lastly, an experiment was conducted to observe the kind of behaviors that may emerge in a group with limited communication abilities similar to aphasia. Certain design interventions were derived from these investigations and a final design opportunity was selected for development.

Understanding the Problem Domain

At the start of the project we investigated several questions such as a) How can we aid communication or social activities for aphasic patients? b) Can a group of people with impaired communication problems perform a common goal and how? An experiment designed for 15 participants was conducted to answer the questions. The objective was to make people work together using a square game by allowing them to perform physical tasks that oblige them to communicate and cooperate. All participants were students in their early twenties and had no impaired ability however the were not allowed to talk during the experiment depending on the type they belonged.

Each participant was allocated as member of type "A" or "B". Members of type "A" were not allowed to talk throughout the activities while those in type "B" were allowed to talk. The experiment was divided into three groups with sorted members. Group 1 had five members belonging to type "B". Group 2 had three members of type "A" and two of type "B". Group three had four members as type "A". The table below summarizes the division.

Table 1. Group division and number of members Group ID Members of type "A" Members of type "B" Group 1 -5 Group 2 3 2 Group 3 4 (omitted one person) -After experimenting, a questionnaire was handed out to members of groups to obtain both quantitative and qualitative data. The questions emphasized on their experience in the group as different types and to know how they improvised in order to communicate with other members. Also, by observing a video of the experiment, more information was obtained. Results from the experiment shows that even if members of a group is not allowed to talk, the group can still perform certain activity together given a common goal. Members are able to work together using gestures, pointing, etc, to communicate with one another and still retain a level of involvement/satisfaction. Eye contact was hardly sustained especially with people that were not allowed to talk. As a result, communication between members was shallow but rather focused their attention on the given task. Furthermore, participants who were not allowed to talk appeared less dominant hence, the social cohesion within the group may be improved by providing clues to help them properly take turns in a dialogue. Pointing gestures was the most effective method used to communicate especially with members who were not allowed to talk. In chapter 3, these insights are developed into actual concepts.

Design interventions and development

An idea generation session was conducted to obtain more ideas from certain directions. Below are three design opportunities that were identified and the third was selected to be further developed. Recap. This idea attempts to bring an aphasic in contact with others to talk about their daily experiences. A sound recording device is used to record sound in a daily context and later replayed to stimulate discussion with friends or family. At the instance of recording the sound, pictures related to the subject matter or context can be captured and are automatically tagged to the sound sample to support future discussion when sharing. Figure 1(top) illustrates this idea; two individuals used the device to record their daily activity and later met with others for social discussions. Information Schema. In this concept a person with aphasia may re-create or organize photos / illustrations on a timeline to generate or represent stories which may support future communication with others as illustrated on figure 1(middle). By pointing at the pictures on the board, he may be able to tell his stories easily without having to recall the words. The picture shows an aphasic creating his story on his playground, and later used them to tell his story to a friend. The mediator concept. The design opportunity here is to enhance the flow or contributions of members in a conversation that may be between a person with aphasia and his partner. The partner in this case can be a therapist, family or friend. Having identified "turn taking" as an important aspect of communication, the concept attempts to provide feedback to partners in order to establish a convenient moment to interrupt or give clues. This is conceptualized with the use of objects that affords tinkering like in a stress ball in order to cause subconscious interaction with the object. According to the mental activity or state of a person, their interaction with the object changes and this information can be abstracted and used to provide feedback to the partner. Hopefully, this information flow would introduce a new dynamics/structure into their conversation. Figure 1(bottom) illustrates two people talking and holding different objects each. Through the objects, partners can receive impulse from the other and may as well initiate certain impulse to the other.

Final concept

The design opportunity further developed is the mediator concept because it provides a rare opportunity in design for aphasics. It deviates from the traditional photo and sound often capitalized or abused within this context however, it is aimed to focus on a rich and interactive experience that may be derived from a dialogue. The following subtopics present the steps of developments. A user test and concept evaluation was made to know how people unconsciously interact with objects in their hands and how much this interaction changes depending on the state on thinking. The prototype used for this investigation consists of two balloons inter-connected using a plastic tube. When one end is pressed, the pressure at the other end increases causing an instant feedback to the person holding at the other end. The first test was with two people, where one asked questions to the other. Different questions were asked and the difficulty level of the questions varied. It was observed that people unconsciously play with the balloon when they are relaxed. However, when the question demands more concentration, they momentarily stop playing with the ball.

Material explorations

Throughout the design process, various materials were explored for building the ball. This is important to select the best material that would trigger the kind of interaction we need and to provide optimum comfort for the user. Examples of the materials created are silicon ball, balloon filled with powder, balloon filled with tinny wooden balls, tightly dense stress ball, PU ball, etc. PU ball was preferred over other materials because it allows full compression yet does not strain the hands. It is a perforated material and allows air to escape when pressed and then return to its original shape immediately after release. However due to unavailability of this material, silicon material was used. The silicon material provided similar affordances however do not allow full compression, as it is airtight.

Digitizing Interaction and Feedback

A silicon ball was made and monitored through the change in air pressure when pressed. A vibrator motor was used to provide instant feedback according to the results of the analysis. The prototype provides feedback in a way that makes the device seem invisible to users. Different feedback modalities were investigated however, haptic feedback was quickly settled upon in order to avoid visual distractions and to retain eye contact during the conversation. From empirical analysis, feedback in the rhythm of heartbeat was preferred over continuous vibration as it may create empathy amongst the partners. In essence, the harder the ball is pressed, the stronger the heartbeat, and when the user freezes while squashing the ball, the ball beats faster. A pilot test was done with some design students to ensure the prototype was robust enough for future testing and evaluations.

Introducing a Desktop Interface

A desktop interface (Fig. 2 top-left) is introduced and prototyped as part of the concept in order to provide visual cues to support the conversation. An example of the programs that may be installed may be a photo album organized in events. This way when a conversation began, a photo album can be opened to provide picture support. Another example may be a Phonetic & Alphabet Chat to be used to scramble letters or sounds that may serve as clues. The purpose for linking the handheld device and the desktop devise is to strengthen the use of computers as visual or auditory cues. The handheld device provides information abstracted from the conversation in order to invite users to use the desktop device when needed. This may cause the desktop device and similar other computer applications built for support to have better utilitarian purpose. Fig. 2 The Desktop interface (top-left), the form of the desktop tool (top-right), the electronic prototype (bottom-left, and the prototype setup with balls (bottom-right)

Expert Evaluation

Having created a preliminary prototype to evaluate the design unity and rationale, a discussion session with an interaction expert was organized. The preliminary prototype was used to experience the design. The evaluation took place in an open office area. The working prototype was placed on a desk together with the desktop device. A computer was used to show the interface of the desktop device. Two chairs were placed closely apart to motivate a close proximity conversation. The goal was to enable the expert to experience the prototype in order to evaluate the rationale of the concept. This is aimed to inspire new insight for the design development. Results: Interaction with objects of the design is classified into aware and unaware layers. The expert identifies interaction with the ball devices as unaware layer of communication as it is non-obtrusive to the users but yet would influence them. He believes it would change the quality of their conversation. However, when attention moves to the desktop device, the interaction with the system changes phase and causes the devices to become visible. He recommends developing the interaction and feedback with the ball devices because it may change people's expressive attitude and satisfaction in a dialogue.

ii.

The feedback received in form of heartbeat may have positive influence on users because it initiates the feeling of contact without physical touch. This may cause the partners to become more connected both physically and emotionally. He thinks there might be information overload if the person with aphasia regularly receives dynamic response from the device. This reveals the potential need to provide the users with some control; i.e., to choose to receive dynamic feedback from the device. His advice is to investigate the potentials of this design firstly within a therapeutic or structured conversation before moving on to general applications.

iii. The expert points out that users are constrained in movement especially because of the visible wires/connections. This may have psychological effect on users and the designed effect may be limited.

Redesigning the Final Prototype: Mediator Concept

The final prototype incorporates a wireless module and two ball devices for initiating and receiving impulse. It does not include the desktop device because the current line of development focus on the interaction and influence with the ball devices. Figure 3 is an overview of the final design. The wireless module includes a ball device and a case to hold the extended part of the electronics. It is implemented in a decentralized way, which makes it more sustainable, or standalone. On the casing is a button and a light source which shows the current state of the device. There are two selectable modes implemented on each module, one allows full functionality and the other allows the user to deactivate dynamic impulse meaning they would not receive regular impulse from the partner.

Each module includes an air pressure sensor that measures the relative pressure in the ball to the atmospheric pressure. This signal is amplified within a range of 0-3.3 volts for analogue to digital conversion on an ATMega328 micro-controller chip. An interval routine that runs on the micro-controller processes this signal and outputs a modulation scheme/command through a wireless protocol to the second module. An interrupt routine is called when data arrives at the wireless port. Depending on the current mode of the device, the data is used to modulate the vibration motor embedded in the ball to stimulate haptic feedback.

Conclusion and Future Steps

Certain design interventions were derived and a course of development was settled upon which introduces a new dimension of a product for people with aphasia. The prospective product is a pair of wireless modules, which includes a ball in form of a stress ball, and a casing that holds parts of the electronics and controls. The end product was designed to access the unaware layer of a conversation in order to provide partners with a constructive feedback that may enrich the social experience of users.

Fig. 3 The final prototype Prototypes were created to validate certain design steps and later developed into a more experiential and advanced prototype, momentarily as a final design. Further investigations should be made to quantify the influence of the new product within a conversation. This would provide more insight for developments. In future, PU rubber material should be adopted, as it would enhance the interaction with the ball. Furthermore, investigations should be made to know if people are more likely to use a desktop application when the ball device is introduced. At this point, it is essential to evaluate the prototype with an aphasia therapist/expert to gain contextual insight; afterwards, a user test with actual users like aphasics may commence. An initial test between a person with aphasia and his/her therapist should be done before trying out in more dynamic situations. The design concept developed in this paper can eventually serve as an intervention tool, which can be integrated into application interfaces already built for people with aphasia.

Figure 1 .

 1 Figure 1. Scenario of Audio Recap concept (top), scenario of Information Schema Recap concept (middle), scenario of Information Schema Recap concept (bottom).