Selected Publications

Books

• L. Karl Branting, Reasoning with Rules and Precedents: A Computational Model of Legal Analysis, Kluwer Academic Publishers, Dordrecht, ISBN 0-7923-6105-9, 2000.

  This book proposes a computational framework for the integration of rules and cases for analytic tasks typified by legal analysis, sets forth a new model of legal precedent based upon the framework, and shows how this model satisfies key jurisprudential criteria for precedent-based legal reasoning.

  
  

Edited collections

• Klaus-Dieter Althoff, Ralph Bergmann, and L. Karl Branting, Case-Based Reasoning Research and Development, Proceedings of the Third International Conference on Case-Based Reasoning, Seeon Monastery, Germany, July 27-30, 1999. Springer Verlag 598 pp., ISBN 3-540-66237-5.

  This book presents mature work and innovative ideas on fundamental and applied research in case-based reasoning. The topics addressed cover the whole spectrum of CBR from formal logics and knowledge-based systems to software engineering, workflow management, and decision making.

  
  
• G. Sartor and L. Karl Branting (Eds.), Judicial Applications of Artificial Intelligence, Kluwer Academic Publishers, Dordrecht, ISBN 0-7923-5472-9, 1998.

  The judiciary is in the early stages of a transformation in which AI (Artificial Intelligence) technology will help to make the judicial process faster, cheaper, and more predictable without compromising the integrity of judges' discretionary reasoning. Flexible AI tools for decision support may promote uniformity and efficiency in judicial practice, while supporting rational judicial discretion. Similarly, AI may promote flexibility, efficiency and accuracy in other judicial tasks, such as drafting various judicial documents. The contributions in this volume exemplify some of the directions that the AI transformation of the judiciary will take.

Refereed Book Chapters

• James Lester, L. Karl Branting, and Brad Mott, Conversational Agents, Practical Handbook to Internet Computing, Munindar Singh (Ed.), CRC Press, 2004.

  Abstract: Conversational agents integrate computational linguistics techniques with the communication channel of the Web to interpret and respond to statements made by users in ordinary natural language. Web-based conversational agents deliver high-volumes of interactive text-based dialogs. Recent years have seen significant activity in enterprise-class conversational agents. This chapter describes the principal applications of conversational agents in the enterprise and the technical challenges posed by their design and large-scale deployments. These technical challenges fall into two categories: accurate and efficient natural-language processing; and the scalability, performance, reliability, integration, and maintenance requirements posed by enterprise deployments.

  Pdf (627K, 19 pages)

Journal Articles

• L. Karl Branting, Information Theoretic Criteria for Community Detection, Lecture Notes in Computer Science LNCS 5498, Proceedings of SNA-KDD 2008, to appear 2010.

  Abstract: Many algorithms for finding community structure in graphs search for a partition that maximizes modularity. However, recent work has identified two important limitations of modularity as a community quality criterion: a resolution limit; and a bias towards finding equal-sized communities. Information-theoretic approaches that search for partitions that minimize description length are a recent alternative to modularity. This paper shows that two information-theoretic algorithms are them- selves subject to a resolution limit, identifies the component of each approach that is responsible for the resolution limit, proposes a variant, SGE (Sparse Graph Encoding), that addresses this limitation, and demonstrates on three artificial data sets that (1) SGE does not exhibit a resolution limit on sparse graphs in which other approaches do, and that (2) modularity and the compression-based algorithms, including SGE, behave similarly on graphs not subject to the resolution limit.

  pdf (273K, 17 pages)

• L. Karl Branting, A Reduction-Graph Model of Precedent in Legal Analysis, Artificial Intelligence , 150(1-2):59-95, (November 2003).

  Abstract: Legal analysis is a task underlying many forms of legal problem solving. In the Anglo-American legal system, legal analysis is based in part on legal precedents, previously decided cases. This paper describes a reduction-graph model of legal precedents that accounts for a key characteristic of legal precedents: a precedent's relevance to subsequent cases is determined by the theory under which the precedent is decided. This paper identifies the implementation requirements for legal analysis using the reduction-graph model of legal precedents and describes GREBE, a program that satisfies these requirements.

  ACM portal

• L. Karl Branting, Learning Feature Weights from Customer Return-Set Selections, The Journal of Knowledge and Information Systems (KAIS) 6(2) March (2004).

  Abstract: This paper describes LCW, a procedure for learning customer preferences represented as feature weights by observing customers' selections from return sets. An empirical evaluation on simulated customer behavior indicated that uninformed hypotheses about customer weights lead to low ranking accuracy unless customers place some importance on almost all features or the total number of features is quite small. In contrast, LCW's estimate of the mean preferences of a customer population improved as the number of customers increased, even for larger numbers of features of widely differing importance. This improvement in the estimate of mean customer preferences led to improved prediction of individual customer's rankings, irrespective of the extent of variation among customers and whether a single or multiple retrievals were permitted. The experimental results suggest that the return set that optimizes benefit may be smaller for customer populations with little variation than for customer populations with wide variation.

  postscript (1,199K, 16 pages)

• L. Karl Branting, Name-Matching Algorithms for Legal Case-Management Systems, The Journal of Information, Law and Technology (JILT) 2002(1).

  Abstract: Name matching - recognizing when two different strings are likely to denote the same entity, is essential for automatic detection of conflicts of interest in legal case-management systems (LCMSs). Unfortunately, most name-matching algorithms developed for LCMSs are proprietary and are therefore not amenable to independent evaluation, improvement, or comparison. This paper proposes a three-step framework for name matching in LCMSs, identifies how each step in the framework addresses the naming variations that typically arise in LCMSs, describes several alternative approaches to each step, and evaluates the performance of various combinations of the alternatives on a representative collection of names drawn from a United States District Court LCMS. The best tradeoff between accuracy and efficiency in this LCMS was achieved by algorithms that standardize capitalization, spacing, and punctuation; filter redundant terms; index using an abstraction function that is both order-insensitive and tolerant of small numbers of omissions or additions; and compare names in a symmetrical, word-by-word fashion.

  HTML

• L. Karl Branting, An Advisory System for Pro Se Protection Order Applicants, International Review of Law, Computers & Technology 14(3), (2000).

  Abstract: Pro se litigants constitute a growing burden to the judiciary. Advisory systems designed to help litigants understand the available legal remedies and satisfy the substantive and procedural requirements to obtain those remedies have the potential to reduce this burden. This paper presents a four-component model of advisory systems for pro se litigants. This model was implemented in the Protection Order Advisory (POA), an advisory system for pro se Protection Order applicants. POA illustrates how existing inference, document-drafting, and interface-design techniques can be used to construct advisory systems for pro se litigants in a wide range of legal domains for which (1) determining whether a prima facie case is satisfied does not require open-textured reasoning, and (2) the documents required to initiate an action are characterized by homogeneity and simple structure.

  Postscript (5,180K, 21 pages)

• L. Karl Branting, Techniques for Automated Judicial Document Drafting, International Journal of Law & Information Technology, 6(2):214-229 (1998).

  Abstract: Document drafting is an essential component of judicial problem solving. This paper distinguishes several classes of judicial documents based on (1) the stage of the judicial process in which they are created, (2) the complexity of the documents, and (3) the party who drafts the documents: a judge, judicial support personnel, or a litigant. Three approaches to automated document drafting are identified and the applicability of the these approaches to each class of judicial document is described. The paper concludes with a description of several implemented prototype systems for drafting judicial documents at various stages of the judicial process.

  Postscript (743K, 11 pages)

• L. Karl Branting, James C. Lester, and Charles B. Callaway, Automating Judicial Document Drafting: A Discourse-Based Approach, Artificial Intelligence and Law, 6(2-4):105-110 (1998).

  Abstract: Document drafting is a central judicial problem-solving activity. Development of automated systems to assist judicial document drafting has been impeded by the absence of an explicit model of (1) the connection between the document drafter's goals and the text intended to achieve those goals, and (2) the rhetorical constraints expressing the stylistic and discourse conventions of the document's genre. This paper proposes a model in which the drafter's goals and the stylistic and discourse conventions are represented in a discourse structure consisting of a tree of illocutionary and rhetorical operators with document text as leaves. A document grammar based on the discourse structures of a representative set of documents can be used to synthesize a wide range of additional documents from sets of case facts. The applicability of this model to a representative class of judicial orders---jurisdictional show-cause orders---is demonstrated by illustrating (1) the analysis of show-cause orders in terms of discourse structures, (2) the derivation of a ocument grammar from discourse structures of two typical show-cause orders, and (3) the synthesis of a new show-cause order from the document grammar.

  Postscript (634K, 49 pages)

• L. Karl Branting, John D. Hastings, and Jeffrey A. Lockwood, Integrating Cases and Models for Prediction in Biological Systems, AI Applications 11(1):29-48 (1997).

  Abstract: Many complex biological systems are characterized both by incomplete models and limited empirical data. Accurate prediction of the behavior of such systems requires exploitation of multiple, individually incomplete, knowledge sources. Model-based adaptation is a technique for integrating case-based reasoning with model-based reasoning to predict the behavior of biological systems. This approach is implemented in CARMA, a system for rangeland grasshopper management advising that implements a process model derived from protocol analysis of human expert problem-solving episodes. CARMA's ability to predict the forage consumption judgments of expert pest managers was empirically compared to that of case-based and model-based reasoning techniques in isolation. This evaluation provided initial confirmation for the hypothesis that an integration of model-based and case-based reasoning can lead to more accurate predictions than either technique individually.

  Postscript (255K, 31 pages)

• L. Karl Branting and Pat Broos, Automated Acquisition of User Preferences. International Journal of Human-Computer Studies, 46:55-77 (1997).

  Abstract: Decision support systems often require knowledge of users' preferences. However, preferences may vary among individual users or be difficult for users to articulate. This paper describes how user preferences can be acquired in the form of preference predicates by a learning apprentice system and proposes two new instance-based algorithms for preference predicate acquisition: 1ARC and Compositional Instance-Based Learning (CIBL). An empirical evaluation using simulated preference behavior indicated that the instance-based approaches are preferable to decision-tree induction and perceptrons as the learning component of a learning apprentice system if representation of the relevant characteristics of problem-solving states requires a large number of attributes, if attributes interact in a complex fashion, or if there are very few training instances. Conversely, decision-tree induction or perceptron learning is preferable if there are a small number of attributes and the attributes do not interact in a complex fashion unless there are very few training instances. When tested as the learning component of a learning apprentice system used by astronomers for scheduling astronomical observations, both CIBL and decision-tree induction rapidly achieved useful levels of accuracy in predicting the astronomers' preferences.

  Postscript (436K, 43 pages)

• John Hastings, Karl Branting, and Jeff Lockwood, A Multi-Paradigm Reasoning System for Rangeland Management. Computers and Electronics in Agriculture, 16(1):47-67 (1996).

  Abstract: Polycultural agroecosystems, such as rangelands, are too complex and poorly understood to permit precise numerical simulation. Management decisions that depend on predictions of the behavior of such systems therefore require a variety of knowledge sources and reasoning techniques. Our approach to designing a computer system to provide advice concerning such systems is to incorporate a variety of reasoning paradigms, permitting the computer system to apply whatever reasoning paradigm is most appropriate to each task as it arises in the process of giving advice. This approach is based on a process description of expert human problem solving that uses four different reasoning paradigms: model-based reasoning; case-based reasoning; rule-based reasoning; and probabilistic reasoning. The process description is implemented in CARMA, a computer system for advising ranchers about the best response to rangeland grasshopper infestations. CARMA reflects an approach that attempts to emulate the human ability to integrate multiple knowledge sources and reasoning techniques in a flexible and opportunistic fashion. The goal of this approach is to enable computer systems to optimize the use of the diverse and incomplete knowledge sources and to produce patterns of reasoning that resemble those of human decision makers.

  Postscript (896K, 23 pages)

• L. Karl Branting, A Computational Model of Ratio Decidendi. Artificial Intelligence and Law , 2(1):1-31 (1994).

  Abstract: This paper proposes a model of ratio decidendi as a justification structure consisting of a series of reasoning steps, some of which relate abstract predicates to other abstract predicates and some of which relate abstract predicates to specific facts. This model satisfies an important set of characteristics of ratio decidendi identified from the jurisprudential literature. In particular, the model shows how the theory under which a case is decided controls its precedential effect. By contrast, a purely exemplar-based model of ratio decidendi fails to account for the dependency of precedential effect on the theory of decision.

  Postscript (474K, 54 pages)

Refereed Conference and Workshop Papers

• L. Karl Branting, Incremental Detection of Local Community Structure, Proceedings of the The 2010 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2010), Odense, Denmark, August 9-11, 2010.

  Abstract: Incremental methods for detecting community structure are necessary when a graph's size or node-expansion cost makes global community-detection methods infeasible. Previous approaches to local community detection, which conflate edges between vertices in the immediate neighborhood of a partially- known community with edges to more distant vertices, often select vertices in an order that is suboptimal with respect to the actual community structure. This paper describes two new algorithms--MaxActivation and MaxDensity--whose vertex-selection policies focus on edges among the vertices in the partially-known community and its immediate neighborhood, ignoring edges to more distant vertices. In an empirical evaluation on a collection of natural and artificial graphs of varying degrees of community cohesion, the relative performance of alternative algorithms depended upon the degree distribution of each graph. These results demonstrate that the selection of an algorithm for incremental community detection should be guided by the characteristics of the graph to which it will be applied.

  Pdf (159K, 8 pages)

• L. Karl Branting, Overcoming Resolution Limits in MDL Community Detection 2nd SNA-KDD Workshop (SNA-KDD2008), Las Vegas, Nevada, USA, August 24, 2008.

  Abstract: A popular approach to community detection in networks is to search for partitions that maximize modularity \cite{newman-2004-69}. However, recent work has identified two important limitations of modularity as a community quality criterion: a resolution limit; and a bias towards finding equal-sized communities. Compression-based approaches that search for partitions that minimize description length are a recent alternative to modularity. This paper shows that two compression-based algorithms are themselves subject to a resolution limit, identifies the aspect of each approach that is responsible for the resolution limit, proposes a variant, SGE (Sparse Graph Encoding), that addresses this limitation, and demonstrates on three artificial data sets that (1) SGE does not exhibit a resolution limit on graphs in which other approaches do, and that (2) modularity and the compression-based algorithms, including SGE, behave similarly on graphs not subject to the resolution limit.

  Pdf (226K, 8 pages)

  PPT(896K)

• L. Karl Branting, Inducing Search Keys for Name Filtering Conference on Empirical Methods in Natural Language Processing Prague, Czech Republic, June 28-30, 2007

  Abstract: This paper describes ETK (Ensemble of Transformation based Keys) a new algorithm for inducing search keys for name filtering. ETK has the low computational cost and ability to filter by phonetic similarity characteristic of phonetic keys but is adaptable to alternative similarity models. A preliminary empirical evaluation suggests that ETK may be well-suited for phonetic filtering applications such as recognizing alternative cross-lingual transliterations

  Pdf (115K, 9 pages)

  PPT(161K)

• L. Karl Branting, Efficient Name Variation Detection AAAI Fall Symposium on Capturing and Using Patterns for Evidence Detection, Arlington, VA, October 13-15, 2006.

  Abstract: Semantic integration, link analysis and other forms of evidence detection often require recognition of multiple occurrences of a single name. However, names frequently occur in orthographic variations resulting from phonetic variations and transcription errors. The computational expense of similarity assessment algorithms usually precludes application to all pairs of strings. Instead, it is typically necessary to use a high-recall, low-precision index to retrieve a smaller set of candidate matches to which the similarity assessment algorithm is then applied. This paper describes five algorithms for efficient candidate retrieval: Burkhart-Keller trees (BKT); filtered Burkhart-Keller trees (FBKT); partition filtering; ngrams; and Soundex. An empirical evaluation showed that no single algorithm performed best under all circumstances. When the source of name variations was purely orthographic, partition filtering generally performed best. When similarity assessment was based on phonetic similarity and the phonetic model was available, BKT and FBKT performed best. When the pronunciation model was unavailable, Soundex was best for k=0 (homonyms), and partition filtering or BKT were best for k>0. Unfortunately, the high-recall retrieval algorithms were multiple orders of magnitude more costly than the low-recall algorithms.

  Pdf (82K, 6 pages)

• Bradford Mott, James Lester, and L. Karl Branting, The Role of Syntactic Analysis in Textual Case Retrieval, Proceedings of the Textual Case-Based Reasoning Workshop at the Sixth International Conference on Case-Based Reasoning (TCBR 2005), Chicago, IL, 24 August 2005.

  Abstract: In this paper, we argue that syntactic analysis is most likely to improve retrieval accuracy in textual case-based reasoning when the task of the system is well-defined and the relationship between queries and cases is specified in terms of this task. We illustrate this claim with an implemented system for syntax-based answer-indexed retrieval, RealDialog.

  Pdf (109K, 7 pages)

• L. Karl Branting, The Role of Mixed-Initiative Agent Interfaces in Intelligence Analysis: Extended Abstract, Proceedings of the AAAI 2005 Fall Symposium on Mixed-Initiative Problem-Solving Assistants, Arlington, VA, November 3-6, 2005.

  Abstract: The task of intelligence analysts is to derive information useful for law enforcement or security from diverse and heterogeneous data sources. Two assumptions support the position that mixed-initiative agent interfaces are desirable for automated systems to assist analysts. The first is that intelligent systems are most beneficial when they help analysts to do their jobs better, rather than to replacing analysts or supplanting their expert judgment. The second idea is that the relationship between analysts and intelligent systems should be governed by the metaphor of a collaborator who works with the analyst, rather than of an idiot savant who slavishly carries out calculations without any idea of whether they make any sense given the analyst's goals and the current problem-solving context. This paper identifies opportunities to apply mixed-initiative interface design techniques to improve intelligence analysis. The focus is not on technical solutions, but rather on potential applications in which successful mixed-initiative techniques might lead to significant benefits. This paper sets forth several important factors that contribute to the difficulty of intelligence analysis and proposes a range of automation options addressing these factors.

  Pdf (71K, 3 pages)

• L. Karl Branting, An Agenda for Empirical Research in AI and Law, Working Papers of the ICAIL'03 Workshop on Evaluation of Legal Reasoning and Problem-Solving Systems, Edinburgh, UK, June 28, 2003, pages 28-35.

  Abstract: Market forces have fueled a rapid growth in practical systems for legal problem solving. Unfortunately, the AI and Law research community has been relatively disengaged from this process. This paper argues that the AI and Law community could make a larger contribution to practical legal system development by focusing more on task analysis and empirical validation to insure that computational and formal models correspond to actual problem-solving behavior. In particular, the absence of task and corpus analysis has led to models of precedent-based legal reasoning that are inconsistent with actual problem-solving behavior in the Anglo-American legal system.

  Postscript (131K, 8 pages)

• L. Karl Branting, A Comparative Evaluation of Name-Matching Algorithms, Proceedings of the Ninth International Symposium on Artificial Intelligence and Law (ICAIL-03), University of Edinburgh, Scotland, June 24-28, 2003.

  Abstract: Name matching-recognizing when two different strings are likely to denote the same entity-is an important task in many legal information systems, such as case-management systems. The naming conventions peculiar to legal cases limit the effectiveness of generic approximate string-matching algorithms in this task. This paper proposes a three-stage framework for name matching, identifies how each stage in the framework addresses the naming variations that typically arise in legal cases, describes several alternative approaches to each stage, and evaluates the performance of various combinations of the alternatives on a representative collection of names drawn from a United States District Court case management system. The best tradeoff between accuracy and efficiency in this collection was achieved by algorithms that standardize capitalization, spacing, and punctuation; filter redundant terms; index using an abstraction function that is both order-insensitive and tolerant of small numbers of omissions or additions; and compare names in a symmetrical, word-by-word fashion.

  Word (180K, 9 pages)

• John Hastings, L. Karl Branting, Jeffrey Lockwood, and Scott Schell, CARMA+: A General Architecture for Pest Management, Proceedings of the IJCAI 2003 Workshop on Environmental Decision Support Systems (EDSS'2003), Acapulco, Mexico, August 10, 2003.

  Abstract: CARMA is a decision-support system for rangeland pest infestations that has been used successfully in Wyoming counties since 1996. CARMA is limited to the specific task for which it was designed: providing advice to ranchers concerning insect infestations on rangeland. This paper describes CARMA+, an architecture that permits CARMA's design to be applied to other pest-management tasks. A task analysis is described for a crop protection module for CARMA+ that is currently under development.

  Pdf (364K, 4 pages)

• L. Karl Branting, Optimizing Return-Set Size for Requirements Satisfaction and Cognitive Load, Proceedings of the Third International Symposium on Electronic Commerce (ISEC), Raleigh, NC, October 18-19, 2002.

  Abstract: This paper proposes a framework for determining the return-set size that optimizes the tradeoff between requirements satisfaction (the degree to which the customer's requirements are satisfied by the best inventory item presented to the customer) and cognitive load (the number of actions a customer must perform and the number of choices from which these are actions are selected). This framework is based on LCW (Learning Customer Weights), a procedure for learning customer preferences represented as feature weights by observing customers' selections from return sets. An empirical evaluation on simulated customer behavior indicated that LCW's estimate of the mean preferences of a customer population improved as the number of customers increased, even for larger numbers of features of widely differing importance. This improvement in the estimate of mean customer preferences led to improved prediction of individual customer's rankings, irrespective of the extent of variation among customers and whether a single or multiple retrievals were permitted. The experimental results suggest that the return set that optimizes benefit may be smaller for customer populations with little variation than for customer populations with wide variation.

  Postscript (451K, 7 pages)

• L. Karl Branting, Acquiring Customer Preferences from Return-Set Selections, Proceedings of the Fourth International Conference on Case-Based Reasoning (ICCBR01), Vancouver, British Columbia, Canada 30 July - 2 August 2001.

  Abstract: This paper describes LCW, a procedure for learning customer preferences by observing customers' selections from return sets. An empirical evaluation on simulated customer behavior indicated that an uninformed hypothesis about customer weights leads to low ranking accuracy unless customers place some importance on almost all features or the total number of features is quite small. In contrast, LCW's estimate of the mean preferences of a customer population improved as the number of customers increased, even for larger numbers of features of widely differing importance. This improvement in the estimate of mean customer preferences led to improved prediction of individual customer's rankings, irrespective of the extent of variation among customers and whether a single or multiple retrievals were permitted. The experimental results suggest that the return set that optimizes benefit may be smaller for customer populations with little variation than for customer populations with wide variation.

  Postscript (1,141K, 15 pages)

• L. Karl Branting, John Hastings, and Jeffrey Lockwood, CARMA: A Case-Based Range Management Advisor, Proceedings of The Thirteenth Innovative Applications of Artificial Intelligence Conference (IAAI-2001), August 7-9, 2001, Seattle, Washington.

  Abstract: CARMA is an advisory system for rangeland grasshopper infestations that demonstrates how AI technology can deliver expert advice to compensate for cutbacks in public services. CARMA uses two knowledge sources for the key task of predicting forage consumption by grasshoppers: cases obtained by asking a group of experts to solve representative hypothetical problems; and a numerical model of rangeland ecosystems. These knowledge sources are integrated through the technique of model-based adaptation, in which CBR is used to find an approximate solution and the model is used to adapt this approximate solution into a more precise solution. CARMA has been used in Wyoming counties since 1996. The combination of a simple interface, flexible control strategy, and integration of multiple knowledge sources makes CARMA accessible to inexperienced users and capable of producing advice comparable to that produced by human experts. Moreover, because CARMA embodies diverse forms of expertise, it has been used in ways that its developers did not anticipate, including pest management research, development of industry strategies, and in state and federal pest management policy decisions.

  Postscript (1,563K, 8 pages)

• L. Karl Branting, Advisory Systems for Pro Se Litigants Proceedings of The Eighth International Conference on Artificial Intelligence and Law (ICAIL-2001), May 21-25, 2001, St. Louis, Missouri.

  Abstract: Increasing numbers of litigants represent themselves in court. Advisory systems designed to help litigants understand the available legal remedies and satisfy the substantive and procedural requirements to obtain those remedies have the potential to assist these litigants and thereby reduce the burden that they impose on the courts. This paper presents a four-component model of advisory systems for pro se litigants. This model was implemented in the Protection Order Advisory (POA), an advisory system for pro se Protection Order applicants. POA illustrates how existing inference, document-drafting, and interface-design techniques can be used to construct advisory systems for pro se litigants in a wide range of legal domains for which (1) determining whether a prima facie case is satisfied does not require open-textured reasoning, and (2) the documents required to initiate an action are characterized by homogeneity and simple structure.

  Postscript (3040K, 8 pages)

• L. Karl Branting, William A. Reiners, and Hongyan Wang, Induction of Landtype Classification Rules form GIS Data, Proceedings of BESAI 2000 Workshop on Binding Environmental Sciences and Artificial Intelligence, August 21, 2000, Berlin, Germany.

  Abstract: The feasibility of inducing classification rules for Landtype Associations (LTAs) from instances of human-expert classifications was tested by evaluating the accuracy of 3 rule-induction algorithms on data drawn from a GIS coverage of Southeast Wyoming. In 10-fold cross-validation tests, the accuracy of rules using precipitation, vegetation, geology, elevation, slope, and aspect as features achieved over 87% accuracy. Adding position as a feature increased accuracy to over 95%. Pruning rule sets to increase comprehensibility caused only a slight decrease in accuracy, particularly for the most accurate induction algorithm, RIPPER. The evaluation indicates that human expert LTA classification rules can be effectively induced from examples and applied to large GIS coverages.

  Postscript (404K, 6 pages)

• Rosina Weber, David W. Aha, L. Karl Branting, J. Robert Lucas, and Irma-Becerra Fernandez, Active Case-Based Reasoning for Lessons Delivery Systems, Proceedings of the The 13th International FLAIRS Conference (FLAIRS 2000), Hotel Royal Plaza, Orlando, Florida May 22-24, 2000.

  Abstract Exploiting lessons learned is a key knowledge management (KM) task. Currently, most lessons learned systems are passive, stand-alone systems. In contrast, practical KM solutions should be active, interjecting relevant information during decision-making. We introduce an architecture for active lessons delivery systems, an instantiation of it that serves as a monitor, and illustrate it in the context of the conversational case-based plan authoring system HICAP (Muñoz-Avila et al., 1999). When users interact with HICAP, updating its domain objects, this monitor accesses a repository of lessons learned and alerts the user to the ramifications of the most relevant past experiences. We demonstrate this in the context of planning noncombatant evacuation operations.

  Postscript (543K, 5 pages)

• L. Karl Branting, Active Exploration in Instance-Based Preference Modeling, Proceedings of the Third International Conference on Case-Based Reasoning (ICCBR-99), Monastery Seeon, Germany, July 27-30, 1999.

  Abstract: Knowledge of the preferences of individual users is essential for intelligent systems whose performance is tailored for individual users, such as agents that interact with human users, instructional environments, and learning apprentice systems. Various memory-based, instance-based, and case-based systems have been developed for preference modeling, but these system have generally not addressed the task of selecting examples to use as queries to the user. This paper describes UGAMA, an approach to learning preference criteria through active exploration. Under this approach, Unit Gradient Approximations (UGAs) of the underlying quality function are obtained at a set of reference points through a series of queries to the user. Equivalence sets of UGAs are then merged and aligned (MA) with the apparent boundaries between linear regions. In an empirical evaluation with artificial data, use of UGAs as training data for an instance-based ranking algorithm (1ARC) led to more accurate ranking than training with random instances, and use of UGAMA led to greater ranking accuracy than UGAs alone.

  Postscript (118K, 15 pages)

• L. Karl Branting and Yi Tao, A Multiple-Domain Evaluation of Stratified CBR, Proceedings of the Third International Conference on Case-Based Reasoning (ICCBR-99), Monastery Seeon, Germany, July 27-30, 1999.

  Abstract: Stratified case-based reasoning (SCBR) is a technique in which case abstractions are used to assist case retrieval, matching, and adaptation. Previous work has shown that SCBR can significantly decrease the computationalexpense required for retrieval, matching, and adaptation under a variety ofdifferent problem conditions. This paper extends this work to two new domains: a problem in combinatorial optimization, sorting by prefix reversal; and logistics planning. An empirical evaluation in the prefix-reversal problem showed that SCBR reduced search cost, but severely degraded solution quality. By contrast, in logistics planning, use of SCBR as an indexing mechanism led to faster solution times and permitted more problems to be solved than either hierarchical problem solving (by ALPINE) or ground level CBR alone. The primary factor responsible for the difference in SCBRs performance in these two domains appeared to be that the optimal-case utility was low in the prefix-reversal task but high in logistics planning.

  Postscript (480K, 15 pages)

• L. Karl Branting, A Generative Model of Narrative Cases, Proceedings of the Seventh International Conference on Artificial Intelligence & Law (ICAIL-99), Oslo, Norway, July 14-17, 1999.

  Abstract: Effective case-based reasoning in complex domains requires a representation that strikes a balance between expressiveness and tractability. For cases in temporal domains, formalization of event transitions in a narrative grammar can simplify both the user's task of problem formulation and the system's indexing, matching, and adaptation tasks without compromising expressiveness. This paper sets forth a model of temporal cases based on narrative grammars, demonstrates its applicability to several different domains, distinguishes two different similarity metrics---sequence overlap and tree overlap---and shows how the choice between these metrics depends on whether nonterminals in the narrative grammar correspond to abstract domain states or merely represent constraints on event transitions. The paper shows basic-level and legal-event narrative grammars can be used together to model how human lawyers interleave fact elicitation and analysis.

  Postscript (281K, 12 pages)

• L. Karl Branting, Charles B. Callaway, Bradford W. Mott, and James C. Lester, Integrating Discourse and Domain Knowledge for Document Drafting Proceedings of the Seventh International Conference on Artificial Intelligence & Law (ICAIL-99), Oslo, Norway, July 14-17, 1999.

  Abstract: Document drafting is a key component of legal expertise. Effective legal document drafting requires knowledge both of legal domain knowledge and of the structure of legal discourse. Automating the task of legal document drafting therefore requires explicit representation of both these types of knowledge. This paper proposes an architecture that integrates these two disparate knowledge sources in a modular architecture under which representation and control are optimized for each task. This architecture is being implemented in DocuPlanner 2.0, a system for interactive document drafting.

  Postscript (842K, 8 pages)

• L. Karl Branting. Stratified Case-Based Reasoning in Non-Refinable Abstraction Hierarchies. Proceedings of the Second International Conference on Case-Based Reasoning (ICCBR-97), Providence, Rhode Island, July 25-27, 1997, Lecture Notes in Artificial Intelligence 1266, pp. 519-530.

  Abstract: Stratified case-based reasoning (Scbr) is a technique in which case abstractions are used to assist case retrieval, matching, and adaptation. Previous work showed that Scbr can significantly decrease the computational expense required for retrieval, matching, and adaptation in a route-finding domain characterized by abstraction hierarchies with the downward refinement property. This work explores the effectiveness of Scbr in hierarchies without the downward refinement property. In an experimental evaluation using such hierarchies (1) Scbr significantly decreased search cost in hierarchies without the downward refinement property, although the speedup over ground-level A* was not as great as in refinable hierarchies, (2) little difference was observed in Scbr search costs between case libraries created top-down in the process of Refinement and those created bottom-up from a valid ground solution, and (3) the most important factor in determining speedup appeared to be a priori likelihood that a previous solution can be usefully applied to a new problem.

  Postscript (281K, 12 pages)

• L. Karl Branting, James C. Lester, and Charles B. Callaway. A Framework for Self-Explaining Legal Documents. Proceedings of the Sixth International Conference on Artificial Intelligence and Law (ICAIL-97), June 30-July 3, 1997, University of Melbourne, Melbourne, Australia, pp. 72-81

  Abstract: The capacity for self-explanation can make computer-drafted documents more credible, assist in the retrieval and adaptation of archival documents, and permit comparison of documents at a deep level. We propose a knowledge-based model of documents that makes explicit the underlying goals that documents are intended to achieve and the stylistic conventions to which they must conform. These goals and conventions are expressed in a dual justification structure that represents the illocutionary and rhetorical dependencies underlying documents. After demonstrating how a document grammar derived from dual justification structures can be used to automate document drafting, we show how documents can exploit dual justification structures to ``explain themselves'' by answering queries about (1) the purposes for inclusion of text in the document and (2) the justification for propositions expressed in the text. This self-explanation framework has been implemented in the Docu-Planner, a prototype document generation system that produces ``queryable'' documents.

  Postscript (402K, 10 pages)

• L. Karl Branting and James Lester. A Framework for Self-Explaining Legal Documents. Proceedings of the Ninth International Conference on Legal Knowledge-Based Systems (JURIX-96), Tilburg University, the Netherlands, December 13, 1996.

  Abstract: Legal document drafting is an essential professional skill for attorneys and judges. To maintain stylistic and substantive consistency and decrease drafting time, new documents are often created by modifying previous documents. This paper proposes a framework for document reuse based on an explicit representation of the illocutionary and rhetorical structure underlying documents. Explicit representation of this structure facilitates (1) interpretation of previous documents by enabling them to ``explain themselves,'' (2) construction of documents by enabling document drafters to issue goal-based specifications and rapidly retrieve documents with similar intentional structure, and (3) maintenance of multi-generation documents. The applicability of this framework to a representative class of judicial orders---jurisdictional show-cause orders---is demonstrated.

  Postscript (155K, 15 pages)

• L. Karl Branting and James Lester. Justification Structures for Document Reuse. Proceedings of the Third European Workshop on Case-Based Reasoning (EWCBR-96), Lausanne, Switzerland, November 14-16, 1996, Lecture Notes in Artificial Intelligence 1168, pp. 76-90.

  Abstract: Document drafting---an important problem-solving task of professionals in a wide variety of fields---typifies a design task requiring complex adaptation for case reuse. This paper proposes a framework for document reuse based on an explicit representation of the illocutionary and rhetorical structure underlying documents. Explicit representation of this structure facilitates (1) interpretation of previous documents by enabling them to ``explain themselves,'' (2) construction of documents by enabling document drafters to issue goal-based specifications and rapidly retrieve documents with similar intentional structure, and (3) maintenance of multi-generation documents.

  Postscript (180K, 15 pages)

• L. Karl Branting and David W. Aha. Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, Montreal, Canada, August 20-25, 1995.

  Abstract: Stratified case-based reasoning is a technique in which abstract solutions produced during hierarchical problem solving are used to assist case-based retrieval, matching, and adaptation. We describe the motivation for the integration of case-based reasoning with hierarchical problem solving, exemplify its benefits, detail a set of algorithms that implement our approach, and present their comparative empirical evaluation on a path planning task. Our results show that stratified case-based reasoning significantly decreases the computational expense required to retrieve, match, and adapt cases, leading to performance superior both to simple case-based reasoning and to hierarchical problem solving ab initio.

  Postscript (195K, 7 pages)

• John D. Hastings, L. Karl Branting, and Jeffrey A. Lockwood, Case Adaptation Using an Incomplete Causal Model Proceedings of the First International Conference on Case-Based Reasoning, Sesimbra, Portugal, October 23-26. 1995.

  Abstract: This paper describes a technique for integrating case-based reasoning with model-based reasoning to predict the behavior of biological systems characterized both by incomplete models and insufficient empirical data for accurate induction. This technique is implemented in CARMA, a system for rangeland pest management advising. CARMA's ability to predict the forage consumption judgments of 15 expert entomologists was empirically compared to that of CARMA's case-based and model-based components in isolation. This evaluation confirmed the hypothesis that integrating model-based and case-based reasoning through model-based adaptation can lead to more accurate predictions than the use of either technique individually.

  Postscript (230K, 12 pages)

• John D. Hastings, L. Karl Branting, Global and Case-Specific Model-based Adaptation Proceedings of the AAAI 1995 Fall Symposium on Adaptation of Knowledge for Reuse Cambridge, MA, November 10-12, 1995.

  Abstract: CARMA (CAse-based Range Management Adviser) is a system that integrates case-based reasoning with model-based reasoning for rangeland pest management. CARMA's predictions of rangeland forage loss by grasshoppers were compared to predictions by 15 expert entomologists using either global or case-specific adaptation weights. Under both conditions, CARMA's predictions were more accurate than CARMA's case-based and model-based components in isolation. However, CARMA's case-specific adaptation weights were consistently more accurate than global adaptation weights. The experimental results suggest that case-specific adaptation weights are more appropriate in domains that are poorly approximated by a linear function.

  Postscript (261K, 7 pages)

• Patrick Broos and L. Karl Branting, Compositional Instance-Based Learning. Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94), Seattle, Washington, July 31-August 4, 1994.

  Abstract: This paper proposes a new algorithm for acquisition of preference predicates by a learning apprentice, termed Compositional Instance-Based Learning (CIBL). CIBL permits multiple instances of a preference predicate to be composed, directly exploiting the transitivity of preference predicates. In an empirical evaluation, CIBL was consistently more accurate than a 1-NN instance-based learning strategy unable to compose instances. The relative performance of CIBL and decision tree induction was found to depend upon (1) the complexity of the preference predicate P(Q) being acquired as measured by the underlying evaluation function Q and (2) the dimensionality of the feature space.

  Keyphrases: knowledge acquisition, case-based reasoning, machine learning

  Postscript (202K, 8 pages)

• L. Karl Branting and Bruce W. Porter, Rules and Precedents as Complementary Warrants, Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), Anaheim, California, July 14-19, 1991.

  Abstract: This paper describes a model of the complementarity of rules and precedents in the classification task. Under this model, precedents assist rule-based reasoning by operationalizing abstract rule antecedents. Conversely, rules assist case-based reasoning through case elaboration, the process of inferring case facts in order to increase the similarity between cases, and term reformulation, the process of replacing a term whose precedents only weakly match a case with terms whose precedents strongly match the case. Fully exploiting this complementarity requires a control strategy characterized by impartiality, the absence of arbitrary ordering restrictions on the use of rules and precedents. An impartial control strategy was implemented in GREBE in the domain of Texas worker's compensation law. In a preliminary evaluation, GREBE's performance was found to be as good or slightly better than the performance of law students on the same task.

  Postscript (151K, 8 pages)

• L. Karl Branting and John D. Hastings, An Empirical Evaluation of Model-Based Case Matching and Adaptation, Proceedings of the Workshop on Case-Based Reasoning, Twelfth National Conference Conference on Artificial Intelligence (AAAI-94), Seattle, Washington, July 31-August 4, 1994.

  Abstract: Rangeland ecosystems typify physical systems having an incomplete causal theory. This paper describes CARMA, a system for rangeland pest management advising that uses model-based matching and adaptation to integrate case-based reasoning with model-based reasoning for prediction in rangeland ecosystems. An ablation study showed that removing any part of the CARMA's model-based knowledge dramatically degraded CARMA's predictive accuracy. By contrast, any of several prototypical cases could be substituted for CARMA's full case library without significantly degrading performance. This indicates that the completeness of the model-based knowledge used for matching and adaptation is more important to CARMA's performance than the coverage of the case library.

  Postscript (175K, 7 pages)

• L. Karl Branting, A Reduction-Graph Model of Ratio Decidendi. Proceedings of the Fourth International Conference on Artificial Intelligence and Law, Vrije Universiteit, Amsterdam, The Netherlands, June 15-18, 1993.

  Abstract:This paper proposes a model of ratio decidendi as a justification structure consisting of a series of reasoning steps, some of which relate abstract predicates to other abstract predicates and some of which relate abstract predicates to specific facts. This model satisfies four adequacy criteria for ratio decidendi identified from the jurisprudential literature. In particular, the model shows how the theory under which a case is decided controls its precedential effect. By contrast, a purely case-based model of ratio fails to account for the dependency of precedential effect on the theory of decision.

  Postscript (163K, 11 pages, figures missing)

• L. Karl Branting, An Issue-Oriented Approach to Judicial Document Assembly. Proceedings of the Fourth International Conference on Artificial Intelligence and Law, Vrije Universiteit, Amsterdam, The Netherlands, June 15-18, 1993.

  Abstract: This paper describes an issue-oriented approach to document assembly under which text is associated with assignments of truth values to the legal predicates occurring in the rules. The system uses the rules to build a justification reflecting a judge's rulings on each issue relevant to the ultimate decision. A document is generated by assembling the text associated with the truth value assignment of each legal predicate occurring in the justification.

  Postscript (142K, 8 pages)

• L. Karl Branting, Reasoning with Portions of Precedents, Proceedings of the Third International Conference on Artificial Intelligence and Law, Oxford, England, June 25-28, 1991.

  Abstract: This paper argues that the task of matching in case-based reasoning can often be improved by comparing new cases to portions of precedents. An example is presented that illustrates how combining portions of multiple precedents can permit new cases to be resolved that would be indeterminate if new cases could only be compared to entire precedents. A system that uses of portions of precedents for legal analysis in the domain of Texas worker's compensation law, GREBE, is described, and examples of GREBE's analysis that combine reasoning steps from multiple precedents are presented.

  Postscript (175K, 10 pages)

Non-Refereed Papers

• L. Karl Branting, Name Matching in Law Enforcement and Counter-Terrorism, ICAIL 2005 Workshop on Data Mining, Information Extraction, and Evidentiary Reasoning for Law Enforcement and Counter-Terrorism June 11, 2005 Bologna, Italy

  Abstract: Name matching is an important task in law enforcement and counter-terrorism. This paper briefly describes the nature of the name-matching task, enumerates typical name-matching applications, explains the technical challenges posed by name-matching, and sets forth several important approaches to these technical challenges.

  Postscript (89K, 4 pages)

• Klaus-Dieter Althoff, Ralph Bergmann, and Karl Branting, Conference Report on the Third International Conference on Case-Based Reasoning, AI Magazine 22:1, Spring 2001. (ICCBR'99)}

  Abstract: The Third International Conference on Case-Based Reasoning was held at the Seeon Monastery, Bavaria, July 27-30, 1999. About 120 researchers from 21 countries attended. The conference included four workshops, three invited talks, 24 technical presentations, a poster session, and an Industry Day, where the focus was on mature technologies and applications in industry.

  Postscript (108K, 8 pages)

• L. Karl Branting, Four Challenges for Computational Models of Legal Precedent. Appearing in special issue of THINK (magazine of the Institute for Language Technology and Artificial Intelligence at Katholike Universiteit Tilburg) on legal knowledge-based systems, Volume 3, June 1994.

  Abstract: Identifying the open research issues in a field is a necessary step for progress in that field. This paper describes four open research problems in computational models of precedent-based legal reasoning: relating case representation to precedent use; modeling the selection and construction of both arguments based on pairwise case comparison and multiple-precedent arguments; modeling the process whereby purposes, policies, and principles are used in case similarity assessment; and extending the applicability of precedents to tasks other than classification.

  Postscript (140K, 18 pages)

Technical Reports

• L. Karl Branting, William Reiners, and Yulan Wei (2000). Induction for Ecological Hypothesis Evaluation: A Case Study, University of Wyoming Department of Computer Science Technical Report.

  Abstract: Identification of the processes that produce patterns of life is a central objective of ecology. This paper explores how machine learning techniques can help evaluate ecological hypotheses. Seven features were derived from GIS coverages of a portion of the Wyoming Snowy Range. The ability of these featues to predict occurrence of trees was tested using various induction algorithms. Wind velocity was found to be a weaker determinant of tree occurrence than topographical features.

  Word (414K, 4 pages)

• Branting, L. K., & Aha, D. W. (1995). Stratified case-based reasoning: Reusing hierarchical problem solving episodes (Technical Report AIC-95-001). Washington, DC: Naval Research Laboratory, Navy Center for Applied Research in Artificial Intelligence.

  Abstract: Stratified case-based reasoning is a technique in which abstract solutions produced during hierarchical problem solving are used to assist case-based retrieval, matching, and adaptation. We describe the motivation for the integration of case-based reasoning with hierarchical problem solving, exemplify its benefits, detail a set of algorithms that implement our approach, and present their comparative empirical evaluation on a path planning task. Our results show that stratified case-based reasoning significantly decreases the computational expense required to retrieve, match, and adapt cases, leading to performance superior both to simple case-based reasoning and to hierarchical problem solving ab initio.

  Keyphrases: Case-based reasoning, hierarchical problem solving, learning, search

  Postscript (224K, 15 pages)

  Postscript compressed (83K, 15 pages)