Nicholas Kushmerick

AAAI Conference 2006 Conference Paper

Activity-Centric Email: A Machine Learning Approach

• Nicholas Kushmerick
• Mark Dredze

Our use of ordinary desktop applications (such as email, Web, calendars) is often a manifestation of the activities with which we are engaged. Planning a conference trip involves sending travel expense forms, and visits to airline and hotel sites. Renovating a kitchen involves sketches, product specifications, emails with the architect and spreadsheets for tracking expenses. Every enterprise has (often implicit) processes for managing customer queries, requesting maintenance, hiring a new employee, purchasing equipment, and so on. Unfortunately, ordinary desktop applications do not know anything about these activities. Within an enterprise, many activities have been formalized into business workflows such as hiring or ordering equipment. However, the way people interact with these workflows is often through email and desktop applications. If these applications are not aware of the activity context, people bear the burden of organizing their information into activities, typically using crude techniques such as manual search, file directories, and email folders/threads. Email has emerged as the primary tool for people to communicate about their work and manage activities. Motivated by the importance of email in conducting activities, we have recently developed several machine learning algorithms for automatically discovering and tracking activities in email. We observe that activities come in many forms, from structured workflows to informal person-to-person communication. In this paper, we summarize our efforts to provide automated assistance with two types of activities: rigid structured activities, and unstructured conversational activities.

ICML Conference 2005 Conference Paper

Ensembles of biased classifiers

• Rinat Khoussainov
• Andreas Heß 0002
• Nicholas Kushmerick

ICML Conference 2005 Conference Paper

Evaluating machine learning for information extraction

• Neil Ireson
• Fabio Ciravegna
• Mary Elaine Califf
• Dayne Freitag
• Nicholas Kushmerick
• Alberto Lavelli

IJCAI Conference 2003 Conference Paper

Learning to Compete in Heterogeneous Web Search Environments

• Rinat Khoussainov
• Nicholas Kushmerick

AIJ Journal 2000 Journal Article

Wrapper induction: Efficiency and expressiveness

• Nicholas Kushmerick

The Internet presents numerous sources of useful information—telephone directories, product catalogs, stock quotes, event listings, etc. Recently, many systems have been built that automatically gather and manipulate such information on a user's behalf. However, these resources are usually formatted for use by people (e. g. , the relevant content is embedded in HTML pages), so extracting their content is difficult. Most systems use customized wrapper procedures to perform this extraction task. Unfortunately, writing wrappers is tedious and error-prone. As an alternative, we advocate wrapper induction, a technique for automatically constructing wrappers. In this article, we describe six wrapper classes, and use a combination of empirical and analytical techniques to evaluate the computational tradeoffs among them. We first consider expressiveness: how well the classes can handle actual Internet resources, and the extent to which wrappers in one class can mimic those in another. We then turn to efficiency: we measure the number of examples and time required to learn wrappers in each class, and we compare these results to PAC models of our task and asymptotic complexity analyses of our algorithms. Summarizing our results, we find that most of our wrapper classes are reasonably useful (70% of surveyed sites can be handled in total), yet can rapidly learned (learning usually requires just a handful of examples and a fraction of a CPU second per example).

AAAI Conference 1999 Conference Paper

Regression Testing for Wrapper Maintenance

• Nicholas Kushmerick
• University College Dublin

Recent workon Internet information integration ~sumesa library of wrappers, specialized informationextraction procedures. Maintainingwrappersis difficult, becausethe formatting regularities on whichthey rely often change. Thewrapperverification problemis to determine whethera wrapperis correct. Standard regression testing approachesare inappropriate, because both the formatting regularities anda site’s underlying content may change. Weintroduce RAPTURE, a fully-implemented, domain-independent verification algorithm. RAPTURE uses well-motivated heuristics to computethe similarity betweena wrapper’s expected and observed output. Experimentswith 27 actual Internet sites showa substantial performanceimprovementover standard regression testing.

AIJ Journal 1995 Journal Article

An algorithm for probabilistic planning

• Nicholas Kushmerick
• Steve Hanks
• Daniel S. Weld

We define the probabilistic planning problem in terms of a probability distribution over initial world states, a boolean combination of propositions representing the goal, a probability threshold, and actions whose effects depend on the execution-time state of the world and on random chance. Adopting a probabilistic model complicates the definition of plan success: instead of demanding a plan that provably achieves the goal, we seek plans whose probability of success exceeds the threshold. In this paper, we present buridan, an implemented least-commitment planner that solves problems of this form. We prove that the algorithm is both sound and complete. We then explore buridan's efficiency by contrasting four algorithms for plan evaluation, using a combination of analytic methods and empirical experiments. We also describe the interplay between generating plans and evaluating them, and discuss the role of search control in probabilistic planning.

AAAI Conference 1994 Conference Paper

An Algorithm for Probabilistic Least-Commitment Planning

• Nicholas Kushmerick

We define the probabilistic planning problem in terms of a probability distribution over initial world states, a boolean combination of goal propositions, a probability threshold, and actions whose effects depend on the execution-time state of the world and on random chance. Adopting a probabilistic model complicates the definition of plan success: instead of demanding a plan that proovably achieves the goal, we seek plans whose probability of success exceeds the threshold. This paper describes a probabilistic semantics for planning under uncertainty, and presents a fully implemented algorithm that generates plans that succeed with probability no less than a user-supplied probability threshold. The algorithm is sound (if it terminates then the generated plan is sufficiently likely to achieve the goal) and complete (the algorithm will generate a solution if one exists).

AAAI Conference 1994 Short Paper

Exploiting the Environment: Urban Navigation as a Case Study

• Nicholas Kushmerick

The Situated Action approach to AI emphasizes the role of the environment in the generation and control of behavior; see (Norman 1993) for an introduction. Work to date has focused mainly on activity within spatially and temporally localized environments such as kitchens and video games (Agre and Chapman 1987; Agre and Horswill 1992). How useful is this perspective when larger-scale activities are considered? I attempt to answer this question by considering some issues related to navigation in urban environments. identify several constraints on the structure of street grids that make navigation much easier than arbitrary graph search. The ultimate goal is a theory of the relationship between features of an urban environment and the computational complexity of navigation. This work extends the sort of analysis advocated by (Agre and Horswill 1992; Horswill 1993).