=Paper=
{{Paper
|id=Vol-105/paper-15
|storemode=property
|title=Specifying Semantic Email Processes
|pdfUrl=https://ceur-ws.org/Vol-105/mcdowell-submission.pdf
|volume=Vol-105
|dblpUrl=https://dblp.org/rec/conf/www/McDowellEH04
}}
==Specifying Semantic Email Processes==
https://ceur-ws.org/Vol-105/mcdowell-submission.pdf
Specifying Semantic Email Processes
Luke McDowell, Oren Etzioni, and Alon Halevy
University of Washington
E-mail: {lucasm,etzioni,alon}@cs.washington.edu
Abstract in many common cases. Applying this theory to real prob-
lems, however, requires the ability to create a SEP specifi-
Prior work has shown that semantic email processes cation that corresponds to an originator’s goals. Ideally, we
(SEPs) can be an effective tool for automating email- would like an originator who is untrained in the usage of
mediated tasks that are currently performed manually in RDF and semantic email to be able to easily construct such
a tedious, time-consuming, and error-prone manner. How- a specification. Unfortunately, without appropriate support
ever, specifying a SEP can be difficult to accomplish, even this task may be challenging even for trained users, because
for users familiar with RDF and semantic email. In re- the specification must fully describe the originator’s goals
sponse, this paper considers an approach for specifying in terms of some RDF content to collect, express how and
SEP templates that can be authored once but then instanti- when to use interventions in order to achieve these goals,
ated many times by untrained users. We describe the tem- and support the explanation of these interventions to the
plate language and provide a complete example, highlight- participants.
ing the key features needed to enable general SEPs. We The contributions of this paper are as follows. First, we
then examine a number of challenges related to SEP au- describe how to specify SEPs via templates. This approach
thoring. In particular, we discuss the problem of verifying addresses the difficulties described above by enabling a
that a given template will always produce a valid instantia- SEP template to be authored once by a user familiar with
tion and give the computational complexity of this problem. semantic email but then instantiated many times by un-
In addition, we discuss how to simplify the task of SEP au- trained originators. We describe the key primitives of our
thoring (and improve execution quality) by automatically declarative template language, which allows authors to eas-
generating explanations for the actions performed in pur- ily express complex goals but also raises several authoring
suit of a SEP’s goals. Finally, we report on practical expe- challenges. In particular, to avoid frustrating the originator
rience with our fully deployed system.1 we must ensure that every possible instantiation of a tem-
plate is executable, yet checking this property manually can
1 Introduction very difficult for the SEP author. Thus, we examine how to
automate this task by formally defining the problem of test-
In previous work [2, 7], we introduced semantic email ing instantiation safety, describing its computational com-
processes (SEPs) and demonstrated how they can effec- plexity, and providing an approximate solution. Likewise,
tively manage a number of tasks that are currently per- to secure the participants’ cooperation the manager’s inter-
formed via email in a tedious, time-consuming, and error- ventions must be clearly explained, yet providing these ex-
prone way. These processes support the common task planations in the template can be challenging or impossible
where an originator wants to ask a set of participants some for the author. Consequently, we examine how to automat-
questions, collect their responses, and ensure that the re- ically generate these explanations in terms of why a par-
sults satisfy some set of goals. In order to achieve these ticular response could not be accepted and what responses
goals, the semantic email manager may utilize a number would be more acceptable, and describe both approximate
of interventions (e.g., rejecting a participant’s response or and optimal algorithms for computing these quantities.
suggesting changes).
The next section gives a brief overview of SEPs while
McDowell et al. [7] demonstrated that SEPs can be used Section 3 describes our template language and a complete
for a wide range of useful interactions and that important example. Sections 4 and 5 examine the problems of in-
reasoning problems for SEPs are computationally tractable stantiation safety and explanation generation that were dis-
1 See www.cs.washington.edu/research/semweb/email cussed above. Finally, Section 6 discusses our experience
for a publicly accessible server (no installation required); source code is with a deployed semantic email system, Section 7 exam-
also available from the authors. ines related work, and Section 8 concludes.
"!$#&% ' !
021 3 " 5 6 " (
)!+* '$,'-/. $
78!+9
: , #
021 34
Figure 1. The creation of a semantic email process. Initially, a SEP template is authored by the “Author”, then is later instantiated
by the “Originator”. Typically, a template is authored once and then instantiated many times.
2 Overview of SEP Creation and Execution executes the declaration, using appropriate algorithms to
decide how to direct the process via message rejections and
We illustrate SEPs with the running example of a “bal- suggestions.
anced potluck.” The originator of the process initially sends In our implementation, the manager is a central server.
out a message announcing the potluck and asking each par- When invoked, this server sends initial messages to the
ticipant whether they are bringing an Appetizer, En- participants announcing the process. These messages also
tree, or Dessert (or Not-Coming). The originator contain a plain text form that can be handled by any mail
also expresses a set of goals for the potluck, which may be client. Participants reply via mail directly to the server,
specified in two different ways. For a logical SEP, the orig- rather than to the originator, and the originator receives sta-
inator specifies a set of constraints that should be satisfied tus messages from the server when appropriate. The origi-
by any process outcome. For example, the originator may nator can query or alter the process via additional emails or
specify that the difference in the number of appetizers, en- a web interface.
trees, or desserts should be at most two. Alternatively, for a
decision-theoretic SEP, the originator provides a function 3 SEP Templates
representing the utility of possible process outcomes (e.g.,
This section defines the parts of a SEP template and then
a function that becomes more negative as the potluck be-
examines a detailed example for the balanced potluck.
comes more unbalanced).
Conceptually, the semantic email system acts as a man- 3.1 Components of a SEP template
ager that uses interventions to direct the process towards
an outcome consistent with the originator’s goals. For in- SEP templates (as well as SEP declarations) are com-
stance, if the manager detects that the potluck is becoming posed of four primary parts:
too unbalanced, the manager can reject a participant’s re- Preamble: general information describing the process
sponse or suggest that a participant modify his response. originator, the set of participants, and explanatory text to be
Figure 1 demonstrates how a template is used to create a sent with the initial request (e.g., “You have been invited to
new SEP. Initially, a user, who is assumed to have some ba- the following potluck...”).
sic knowledge of RDF and semantic email, authors a new
template using an editor (most likely by modifying an ex- Queries: the set of queries to ask each participant. For in-
isting template). We call this user the SEP author. The stance, a potluck SEP might query each participant for the
template is written in OWL based on a SEP ontology that food item and the number of guests that they are bringing.
describes the possible queries, goals, and messages for a Each query defines a variable name for later use and the
process. For instance, the “balanced potluck” template de- type of valid responses to that query (e.g., integer, boolean,
fines the general balance constraints for the process, but etc.). Queries may also specify further restrictions on what
has placeholders for parameters such as the participants’ responses are considered valid (e.g., NumGuests must be
addresses, the specific choices to offer, and how much im- non-negative). Finally, each query item provides an RDQL
balance to permit. To enable an originator to provide these query that specifies the semantic meaning of the requested
values later, the author also constructs a simple web form information and is used to map the participant’s textual re-
that prompts the originator for each parameter. Section 4 sponse to RDF. This RDQL portion also enables a suitably
describes how to automatically generate such forms. equipped participant to have an agent respond to some re-
quests automatically (e.g., “Decline all invitations for Fri-
An untrained originator finds a SEP template from a
day evening”).
public library and instantiates the template by filling out
the corresponding web form, yielding a SEP declaration Goals: the originator’s goals for the process. These goals
(also in OWL). The originator then invokes the process by may be expressed either as constraints that must be satis-
submitting this declaration to the manager. The manager fied at every point in time (a MustConstraint) or con-
straints that should, if possible, be ultimately satisfied by ipant; adding ProcessSummary notifications is useful
the final process outcome (a PossiblyConstraint). for displaying further summary information over this data
Alternatively, the goals can be expressed via a utility func- (e.g., to show the most popular response to a vote).
tion over the eventual process outcome, along with descrip- A notification may be triggered by a number of con-
tions of the costs (social or otherwise) of asking partici- ditions including OnResponseReceived, OnAllRe-
pants to switch and the probabilities of expected participant sponsesReceived, OnDateTime, or the most general
behavior (see [7] regarding the estimation of these values). OnConditionSatisfied. In addition to the notifica-
This type of goal is referred to as a TradeoffGoal be- tions specified in the template, our implementation allows
cause it strives to balance the utility of the expected process the originator to easily create an arbitrary number of On-
outcome against the costs of actions taken to achieve that DateTime “reminders” when instantiating the process.
outcome.
The manager uses the process’s goals to decide when 3.2 Template Example
to make a rejection or suggestion. Goals may also spec-
Figure 2 shows a complete SEP template for our ex-
ify some text to explain these interventions to the partic-
ipants. This text may be static or dynamically generated ample balanced potluck. Parameters that must be instan-
tiated by the originator are shown in bold; other variables
based on the current state (e.g., “Sorry, we already have 5
more Appetizers than Desserts”). Providing enough detail such as NumGuests will be evaluated as the SEP is ex-
ecuted. The declaration follows the four main parts de-
in the messages so that they are understandable to the par-
scribed above. First, the template specifies the participants
ticipants (and hence yield the desired cooperation) can be
a challenge for the SEP author. Section 5 discusses tech- and a suitable prompt for the initial message. Second, the
template defines two queries. The Bringing query in-
niques for automatically constructing these explanations.
dicates that a valid response to this query must be in the
The constraints or utility functions are written as ex-
the (originator-provided) set Choices. The NumGuests
pressions involving arbitrary arithmetic functions over con-
query is “guarded” so that applies only if the parameter
stants and variables. There are three classes of variables:
AskForNumGuests is true; if so, this query will accept
• Parameters: a value provided by the originator when
only non-negative integers. In both cases the query prop-
instantiating the template (e.g., Choices, the options
erty provides the aforementioned RDQL query.
to offer the participants).
Third, the template specifies one MustConstraint
• Author-defined: any variable explicitly defined by the
goal. The constraint is evaluated over every possible (x,y)
SEP author. These variables may represent common
where x and y are in the set (Choices - OptOut);
subexpressions or may be used to iterate over some set
OptOut is for choices such as “Not Coming” that should
(e.g., to loop through each value of Choices, veri-
be excluded from the constraints. The constraint requires
fying that none violate the constraints). In addition,
that the number of responses x (e.g., Appetizer) must dif-
these variables may be queries over a supporting data
fer from the number of responses y (e.g., Dessert) by
set that contains the responses of each participant to
no more than MaxImbalance. The message prop-
the originator’s request. For convenience, these RDF
erty provides an explanation to send to a participant
responses are mapped to a virtual relational table that
if their response is rejected because of this constraint.
may be queried via SQL.
This message utilizes the predefined variable Bring-
• Pre-defined: variables automatically computed by the
ing.acceptable(), which is explained in Section 5.
manager (e.g., NumResponses, the total number of
Finally, the template specifies two notifications. The
responses received so far). The system also provides
first notifies the originator as soon as the total number of
a few common queries over the supporting data set
expected guests (computed via a SQL query over the sup-
(e.g., Bringing.Entree.count() is the number
porting data set) reaches GuestThreshold. The other
of “Entree” responses received).
notification updates the process summary to include counts
Notifications: a set of email messages to send when some of each type of response received. Notice the use of the
condition is satisfied. The target of a notification may be forAll property to iterate over the possible responses,
an arbitrary list of email recipients (possibly from a query similar to its use in the MustConstraint.
over the underlying data set). Alternatively, the target may The above example demonstrated the use of a Must-
be the Originator, Responders, NonResponders Constraint goal; the same properties may be used to
(particularly useful for sending a reminder to respond after define a PossiblyConstraint instead. A Tradeof-
a few days), or AllParticipants. Finally, sending a fGoal follows the same general form but instead of an
notification to the virtual target ProcessSummary adds enforce property it provides a utility expression via an
the notification text to a process-specific web page. This optimize property, along with additional properties to
web page contains a table with the response of each partic- describe the associated costs and probabilities.
:participants "$ParticipantsList$";
:prompt
"You have been invited to the following potluck. Please use the form below to indicate what you are
bringing. To ensure that our meal selection is balanced, you may be asked to modify your choice.
Description: $PromptDescription$
Location: $PromptLocation$
Date and Time: $PromptDateTime.toUserFriendly()$";
:queries (
[a :StringQuery;
:name "Bringing";
:query "WHERE (?process, , ?x1),
(?x1, , ?EMAIL),
(?x1, , ?Bringing)
USING rdfcal FOR ,
uw FOR ";
:enumeration "$Choices$" ]
[a :IntegerQuery;
:guard "$AskForNumGuests$";
:name "NumGuests";
:query "WHERE (?process ....";
:minInclusive "0"; ] );
:goals (
# Reject the message if it results in too much inbalance between any two pairs
[a :MustConstraint;
:forAll ([:name "x"; :range "$Choices$-$OptOut$"]
[:name "y"; :range "$Choices$-$OptOut$"]);
:suchThat "$x$ != $y$";
:enforce "abs($Bringing.{$x$}.count()$ - $Bringing.{$y$}.count()$) <= $MaxImbalance$";
:message "Your request to bring a $Bringing.last()$ could not be accepted.
Choices that could be accepted right now are $Bringing.acceptable()$.";] );
:notifications (
# Notify the owner if the number of guests crosses a threshold (ignore if $GuestThreshold$ is zero)
[a :OnConditionSatisfied;
:guard "$GuestThreshold$ != 0";
:define ([:name "TotalGuests"; :value "[SELECT SUM(NumGuests) FROM CURR_STATE]"]);
:condition "$TotalGuests$ >= $GuestThreshold$";
:notify :Originator;
:message "Currently, $TotalGuests$ guests are expected.";]
# Update the process summary
[a :OnMessageReceived;
:notify :ProcessSummary;
:message ( "Here’s how many of each choice confirmed so far:"
[ :forAll ([:name "x"; :range "$Choices$"]);
:evaluate "$x$: $Bringing.{$x$}.count()$"; ] ) ] )
Figure 2. SEP template for a “Balanced Potluck” process, shown in N3 format. Variables in bold (e.g., $Choices$) are param-
eters provided by the originator when instantiating the template. Other variables are defined inside the declaration (e.g., $x$,
$TotalGuests$) or are automatically computed by the system (e.g., $Bringing.acceptable()$).
4 Template Instantiation and Verification of strings that must be a subset of Choices. The last two
parameters relate to asking participants about the number
This section describes how parameter descriptions can of guests that they will bring to the potluck.
be used to generate and validate a web form for instantiat- The form generator tool takes a parameter description
ing templates, then examines the problem of templates that, and template as input and outputs a form for the originator
when instantiated, may yield invalid declarations. to fill out and submit. If the submitted variables comply
with all parameter restrictions, the template is instantiated
4.1 Parameter Descriptions with the corresponding values and the resulting declaration
is forwarded to the manager for execution. Otherwise, the
Each SEP template must be accompanied by a web form tool redisplays the form with errors indicated and asks the
that enables originators to provide the parameters needed originator to try again.
to instantiate the template into a declaration. To automate
this process, our implementation provides a tool that con-
4.2 Instantiation Safety
verts a simple OWL parameter description into such a web
form. Figure 3 shows a partial example for our example
balanced potluck. The description provides a name, type, This section considers the problem of templates which,
and prompt for each parameter, along with any restrictions when instantiated, may yield invalid declarations, explores
on the legal values of that parameter. For instance, the first the significance of this problem, and describes the solutions
parameter block specifies that Choices is a set of strings, adopted in our system. There are a number of possible er-
while the second parameter indicates that OptOut is a set rors that might render a declaration invalid, including:
:parameters (
[a :TypeList;
:name "Choices";
:prompt "Choices for the recipients to choose from (enter a comma-separated list)" ]
[a :TypeList;
:name "OptOut";
:prompt "Choices to exclude from these restrictions (enter a comma-separated list)";
:subset "$Choices$" ]
[a :TypeSelectOne;
:name "AskForNumGuests";
:choices ([:value :True; :prompt "Yes, ask how many guests each person is bringing" ]
[:value :False; :prompt "No, don’t ask about guests"] ) ]
[a :TypeInteger;
:name "GuestThreshold";
:prompt "Notify the originator when the number of guests reaches (enter 0 to ignore):";
:minInclusive "0" ]
)
Figure 3. Part of a parameter description for the potluck template of Figure 2. Additional elements for variables such as
MaxImbalance are not shown.
1. Missing/multiple properties: e.g., each MustCon- This problem is of significant practical interest for two
straint must have exactly one enforce property. reasons. First, because errors are detected in the declara-
2. Wrong object type: e.g., the name property must tion, any error message is likely to be very confusing to
point to a literal string, not a resource. the originator (who knows only of the web form, not the
declaration). Thus, an automated tool to ensure that a de-
3. Ambiguous names: e.g., the same variable or query ployed template is instantiation safe is desirable. Second,
name must not be defined twice. constructing instantiation-safe templates can be very oner-
4. Expression errors: e.g., "x ++ y" is not permitted. ous for authors, since it may require considering a large
number of possibilities. Even when this is not too difficult,
5. Undefined symbols: e.g., a condition property
having an automated tool to ensure that a template remains
must refer only to variables that have been defined.
instantiation safe after a modification would be very useful.
6. Empty set: e.g., properties such as enumeration
require that their argument is not the empty set. Theorem 4.1 Let τ be a template and φ a parameter de-
scription for τ . If τ is an arbitrary SEP template, then
Errors 1 and 2 above can be detected automatically by
validating the template against the corresponding OWL on- instantiation safety is co-NP-complete in the size of φ.
tology, while errors 3, 4, and sometimes 5 can be automat-
Thus, in general determining instantiation safety is dif-
ically detected by a static analysis of the template. How-
ever, some occurrences of errors 5 and 6 will only occur ficult, though in practice φ may be small enough that the
for particular instantiations of the template and thus cannot problem is tractable. In our implementation, we provide a
be detected by examining the template alone. For instance, tool that approximates instantiation safety testing via lim-
considering instantiating the potluck template in Figure 2 ited model checking. The tool operates by instantiating τ
with the following (partial list of) parameters: with all possible parameters in φ with type boolean or enu-
AskForNumGuests = False
meration (these most often correspond to general configu-
GuestThreshold = 50 ration parameters). For each possibility, the tool chooses
random values that satisfy φ for the remaining parameters.
In this case the first notification in Figure 2 is invalid, If any instantiation is found to be invalid, then τ is known
since it refers to a query NumGuests that does not exist to be not instantiation safe. We conjecture that an exact,
because AskForNumGuests is false. Thus, the declara- polynomial time algorithm exists for most common cases;
tion is not executable and must be refused by the manager. this will be considered in future work.
This particular template problem could be addressed either
by adding an additional guard on the first notification or 5 Automatic Explanation Generation
by adding a parameter restriction on GuestThreshold.
However, this leaves open the general problem of ensuring While executing the process, the manager utilizes rejec-
that no instantiation results in an invalid declaration: tions or suggestions to influence the eventual SEP outcome.
However, the usefulness of these interventions depends on
Definition 4.1 (instantiation safety) Let τ be a template the extent to which they are understood by the participants.
and φ a parameter description for τ . τ is instantiation safe For instance, the rejection “Sorry, only 2 tickets left” is a
w.r.t. φ if, for all parameter sets ξ that satisfy φ, instantiat- much more helpful response to a request for 4 tickets than a
ing τ with ξ yields a valid SEP declaration. 2 simple “No.” Likewise, the suggestion “Please consider an
Appetizer instead” is much more likely to elicit the desired would not be after adding response r, we say that E ⊆ CD
cooperation than a suggestion with no hint as to a more ac- is a sufficient explanation for rejecting r iff no sequence of
ceptable potluck dish. As previously mentioned, the SEP responses from the participants, beginning with r, will put
author may provide such messages in the template, but pro- D in a state that satisfies E. 2
viding them in sufficient detail can be a challenging and
time-consuming task. Intuitively, a sufficient explanation E justifies rejecting
Below we consider techniques for simplifying the task r, because accepting r precludes ever satisfying E. Using
of the SEP author by automatically computing such ex- a modified form of our ultimate satisfiability theorem [7],
planations. We focus first on explaining the reasons for testing if any particular E is a sufficient explanation can
a particular intervention and then briefly consider comput- be done in polynomial time. We could use this procedure
ing the set of currently acceptable responses. Note that in repeatedly to compute the minimum-size sufficient expla-
some cases these methods can also be viewed as improving nation, but this might require time exponential in the num-
the quality of explanations that are possible for a SEP. For ber of constraints. Alternatively, we could use an approx-
instance, because the decision about whether to suggest a imate, greedy algorithm that first ranks each constraint by
different response due to a TradeoffGoal depends on a the number of possible future states for which it is not sat-
complex balance of possible future states vs. action costs, isfied, then incrementally adds to E the constraint with the
an automatically-generated explanation can provide much largest rank until every possible state is covered. Note that,
more detail than the manually-encoded explanation of even in the particularly useful case where |Eminimum | = 1, this
the most thorough SEP author. Finally, the discussions be- algorithm is guaranteed to find the optimal solution.
low relate to all SEPs, but specific complexity results ap- TradeoffGoal: In this case, it is more difficult to single out
ply only when the constraints/utilities are bounded or K- specific terms that are responsible for a manager’s sugges-
partitionable [7]; this includes many common cases and tion, because every term contributes to the process utility
all SEPs discussed in this paper. to some extent, either positively or negatively. However,
if the manager decides to make a suggestion, then the ex-
5.1 Explaining Interventions pected improvement must outweigh the certain cost of this
action. Thus, for non-zero costs, there must be a signifi-
In this subsection we consider how to generate expla-
cant difference in the utility of the state where the manager
nations for an intervention based on identifying the con-
requested a switch (Ssw ) vs. where the manager did not
straint(s) or utility term(s) that led to the intervention. We
(S0 ).
do not discuss the additional problem of translating these
We seek to identify the terms that explain most of this
terms into a natural language suitable for sending to a par-
difference. In particular, given a n-term utility function
ticipant, but note that even fairly simple explanations (e.g.,
“Appetizer Count (10) too high vs. Dessert Count (3)”) are U (s) = u1 (s) + ... + un (s)
much better than no explanation.
In our implementation the manager intervenes only with we define the change δu in each utility term as
rejections for a MustConstraint or PossiblyCon-
straint, and only with suggestions for a Tradeoff- δu = u(Ssw ) − u(S0 ).
Goal(cf., [7]). We consider each of these in turn.
We wish to identify a set E ⊆ {u1 , .., ..un } such that:
MustConstraint: In this case all constraints must be ini-
tially satisfied, so any constraint that is not satisfied after X
δu ≥ β[U (ssw ) − U (S0 )]
adding a response r to state D is an explanation for reject-
u∈E
ing r. Note that, for explanations, we treat each forAll
possibility as a separate constraint; otherwise, the sample i.e., so that the terms in E explain at least β of the change.
potluck of Figure 2 would always produce the same (com- Note that, when generating an explanation, we are pri-
plex) constraint for an explanation. marily interested in terms indicating that a switch is bene-
PossiblyConstraint: For a PossiblyConstraint, ficial, i.e., where δu > 0. If we only consider such terms,
there is no guarantee that the constraints are satisfied, only then a greedy algorithm suffices to identify the explanation
that it is possible for them to be ultimately satisfied when E of guaranteed minimal size: set E to ∅, then incremen-
more responses are received. In this case an explanation tally add to E the term with the largest δu until E explains
should satisfy the following definition: at least β of the total change. If we wish to consider util-
ity terms with both positive and negative changes, then this
Definition 5.1 (sufficient explanation) Given a data set D problem becomes more challenging (cf., Klein and Short-
and constraints CD such that D is ultimately satisfiable but liffe [5]).
Procedural approach Declarative approach Size Reduction
SEP name Java code Forms (HTML) Total Template Forms (Params) Total for Declarative
Balanced Potluck 1283 397 1680 113 57 170 90%
First-come, First-served 301 235 536 66 33 99 82%
Meeting Coordination 471 272 743 60 22 82 89%
Request Approval 772 286 1058 80 29 109 90%
Auction 392 111 503 55 43 98 81%
Table 1. Comparison of the size (in number of lines) of different ways of specifying a SEP. For the procedural prototype, the first
numerical section displays the size of the Java code for encoding the SEP functionality, size of the HTML for acquiring parameters
from the originator, and the total of these two. For the declarative approach, the second section displays the size of the template
(OWL, in N3 format), size of the parameter description, and the total. The final column shows the percentage reduction in the size
of a SEP when changing from the procedural approach to the declarative approach.
5.2 Acceptable Responses away, scheduling meetings, and balancing a potluck. De-
spite very limited publicity, our semantic email server has
In addition to explaining the reasons why a particular seen growing interest. For instance, a DARPA working
response led to an intervention, we would also like to be group has adopted semantic email for all of its meeting
able to inform participants about what responses would be scheduling and RSVP needs, students have used semantic
more “acceptable.” (One could also ask for an explanation email to schedule seminars and Ph. D. exams, and semantic
of why a given response is acceptable, but we do not con- email has been used to organize our annual database group
sider that problem here.) For a constraint-based SEP, if and departmental-wide potlucks.
adding a response r to the current state D still permits the Our experience has led to a number of observations re-
constraint to be satisfied (either immediately or ultimately, garding SEP authoring and instantiation. First, our tem-
as appropriate) then r is acceptable. We previously proved plate language is sufficient for specifying a wide range of
that computing whether a specific response r is acceptable useful SEPs. Second, these declarative specifications are
with respect to a set of MustConstraints or Possi- much simpler and more concise than corresponding spec-
blyConstraints could be done in polynomial time [7]. ifications written in Java. For instance, Table 1 displays
A corollary is that it is also possible to compute in polyno- the number of lines of OWL needed for a number of sam-
mial time the entire set of responses which are acceptable ple SEP templates vs. the number of lines of Java/HTML
from state D. Our system currently computes and makes needed in our original prototype (which utilized process-
available this result for MustConstraints (e.g., the use specific procedures). Overall, the declarative approach re-
of Bringing.acceptable() in Figure 2). quires about 80-90% fewer lines than the procedural ap-
For a TradeoffGoal, we define an “acceptable” re- proach. These figures are approximate – neither approach
sponse as one that is “good enough” so that the manager had a goal of using as few lines as possible – but give a
will not respond with a change suggestion. We might also flavor for the conciseness of the declarative approach.
be interested in computing responses that are “better” than Second, despite the usage we have seen, the group of
others, e.g., those which result in an expected utility in the people instantiating new SEPs seems to be much smaller
top 25% compared to other possible responses. This infor- than the group of people who have learned about and shown
mation could be used when making a suggestion (“Please enthusiasm for the system. While some of this effect is to
consider one of these values...”, or could be displayed as be expected, we also believe that a significant cause is that
part of the process summary to assist participants that have the system still requires too much initial work to launch a
yet to respond. Given a particular state D, both such prob- new SEP. In spite of SEPs’ advantages, when faced with a
lems can be solved in polynomial time by comparing the particular data-collection task it is easier in the short-term
expected utility of states before and after an additional re- to just send a non-semantic email message and deal with
sponse is received. the consequences later. Essentially, originators need more
instant gratification to motivate them to use the semantic
6 Experience and Future Work system, as we have also described in the web context [6].
One way to address this problem would be to have authors
Our semantic email system is deployed and may be provide basic versions of their SEPs that provide defaults
freely used by anyone without any software installation; for almost all parameters, akin to how modern search en-
the source code for deploying other instances of the server gines hide most of their functionality behind an “advanced”
is also available. So far we have developed simple pro- interface. An additional improvement would be to allow
cesses for functions like collecting RSVPs, giving tickets originators to easily modify the default parameters while a
process is executing. This both eliminates the need for up- 8 Conclusions
front work and simplifies appropriate parameter selection,
This paper has described our template-based approach
since the originator can delay this task until a few illustra-
to specifying SEPs. Templates greatly increase the usabil-
tive responses have arrived.
ity of SEPs by shifting most of the complexity of specify-
ing a SEP from untrained originators onto a much smaller
7 Related Work set of trained SEP authors. In addition, our template lan-
guage enables authors to easily express complex goals in a
Some hardcoded email processes, such as the meeting way that can be automatically pursued by the manager via
request feature in Outlook and invitation management via interventions. We also examined a number of challenges to
Evite have made it into popular use already. Our work pro- authoring high-quality templates that arise in this context.
vides a general, declarative infrastructure for SEPsand an- In particular, we explored the problem of verifying that a
alyzes the inference problems it needs to solve to manage given template will always yield a valid instantiation, de-
processes effectively and guarantee their outcome. Like- scribed the computational complexity of this problem, and
wise, workflow and collaboration systems such as Lotus presented an approximate solution. We also discussed mul-
Notes/Domino and Zaplets offer scripting capabilities and tiple ways in which the manager can automatically gener-
some graphical tools that could be used to implement so- ate useful explanations for its interventions. Collectively,
phisticated email processes. However, these systems lack these techniques both simplify the task of the SEP author
support for reasoning about data collected from a number and improve the overall execution quality for the originator
of participants (e.g., as required to balance a potluck or en- and the participants of a SEP. Future work will consider
sure that a collected budget satisfies aggregate constraints). additional ways to make SEP authoring and instantiation
In addition, such processes are constructed from arbitrary even easier and continue to promote SEP adoption by a
pieces of code, and thus lack the formal properties that our wide range of users.
declarative model provides.
Recent work on the Inference Web [8] has focused on References
the need to explain a Semantic Web system’s conclusions [1] M. Druzdzel. Qualitative verbal explanations in bayesian be-
in terms of base data and reasoning procedures. In con- lief networks. Artificial Intelligence and Simulation of Be-
trast, we deal with explaining the manager’s actions in haviour Quarterly, 94:43–54, 1996.
terms of existing responses and the expected impact on [2] O. Etzioni, A. Halevy, H. Levy, and L. McDowell. Semantic
the SEP’s goals. In this sense our work is more similar email: Adding lightweight data manipulation capabilities to
to prior research that sought to explain decision-theoretic the email habitat. In Sixth Int. Workshop on the Web and
advice (cf., Horvitz et al. [3]). For instance, Klein and Databases, 2003.
Shortliffe [5] describe the VIRTUS system that can present [3] E. J. Horvitz, J. S. Breese, and M. Henrion. Decision the-
users with an explanation for why one action is provided ory in expert systems and artificial intelligence. International
over another. Note that this work focuses on explaining the Journal of Approximate Reasoning, 2:247–302, 1988.
relative impact of multiple factors on the choice of some [4] N. Jussien and S. Ouis. User-friendly explanations for con-
action, whereas we seek to compute the simplest possi- straint programming. In ICLP’01 11th Workshop on on Logic
ble reason why some action could not be chosen (i.e., ac- Programming Environments, Paphos, Cyprus, 1 Dec. 2001.
cepted). Other relevant work includes Druzdzel [1], which [5] D. A. Klein and E. H. Shortliffe. A framework for explaining
addresses the problem of translating uncertain reasoning decision-theoretic advice. Artificial Intelligence, 67(2):201–
into qualitative verbal explanations. 243, 1994.
For constraint satisfaction problems, a nogood [9] is [6] L. McDowell, O. Etzioni, S. D. Gribble, A. Halevy, H. Levy,
a reason that no current variable assignment can satisfy W. Pentney, D. Verma, and S. Vlasseva. Mangrove: Entic-
all constraints. In contrast, our notion of a sufficient ex- ing ordinary people onto the semantic web via instant grati-
planation for a PossiblyConstraint is a reason that fication. In Second International Semantic Web Conference,
October 2003.
no future assignment can satisfy the constraints, given the
set of possible future responses. Potentially, our problem [7] L. McDowell, O. Etzioni, A. Halevey, and H. Levy. Semantic
could be reduced to nogood calculation, but this would not email. In World Wide Web, 2004.
exploit the special structure of SEPs that ensures that a [8] D. L. McGuinness and P. Pinheiro da Silva. Infrastructure
candidate explanation can be checked in polynomial time. for web explanations. In Second International Semantic Web
Conference, October 2003.
Jussien and Ouis [4] describe how to generate user-friendly
nogood explanations, though they require that a designer [9] T. Schiex and G. Verfaillie. Nogood Recording fot Static
and Dynamic Constraint Satisfaction Problems. International
explicitly model a user’s perception of the problem as
Journal of Artificial Intelligence Tools, 3(2):187–207, 1994.
nodes in some constraint hierarchy.