Abstract: Collections of documents filed in courts are potentially a rich source of information for citizens, attorneys, and courts, but courts typically lack the ability to interpret them automatically. This paper presents technical approaches to two applications of judicial document interpretation: detection of document filing errors; and matching orders with the motions that they rule on. An empirical evaluation identified several techniques that exploit genre-specific aspects of judicial documents to improve performance on these two tasks, including vocabulary reduction to task-specific terms, excision of the portion of documents unlikely to contain relevant text, and optimizing error detection by separating document classification into two stages: classification of the document’s text followed by interpretation of this text classification based on procedural context.

Abstract: Collections of documents filed in courts are potentially a rich source of information for citizens, attorneys, and courts, but courts typically lack the ability to interpret them automatically. This paper presents technical approaches to two applications of judicial document interpretation: detection of document filing errors; and matching orders with the motions that they rule on. An empirical evaluation identified several techniques that exploit genre-specific aspects of judicial documents to improve performance on these two tasks, including vocabulary reduction to task-specific terms, excision of the portion of documents unlikely to contain relevant text, and optimizing error detection by separating document classification into two stages: classification of the document’s text followed by interpretation of this text classification based on procedural context.

Abstract: Citations, as in when a certain statute is being cited in another statute, differ in meaning, and we aim to annotate each edge with a semantic label that expresses this mean- ing or purpose. Our efforts involve defining, annotating and automatically assigning each citation edge with a specific semantic label. In this paper we define a gold set of la- bels that cover a vast majority of citation types that appear in the United States Code (US Code) but still specific enough to meaningfully group each citation. We proposed a Linear-Chain CRF based model to extract the useful features needed to label each citation. The extracted features were then mapped to a vector space using a word embed- ding technique and we used clustering methods to group the citations to their corresponding labels. This paper analyzes the content and structure of the US Code, but most of the techniques used can be easily generalized to other legal documents. It is worth mentioning that during this process we also collected a human labeled data set of the US Code that can be very useful for future research.

Abstract: This paper describes an algorithm, Distributed Pivot Clustering (DPC), that differs from prior distributed clustering algorithms in that it requires neither an inexpensive approximation of the actual distance function nor that pairs of elements in the same cluster share at least one exact feature value. Instead, DPC requires only that the distance function satisfy the triangle inequality and be of sufficiently high-granularity to permit the data to be partitioned into canopies of optimal size based on distance to reference elements, or pivots. An empirical evaluation demonstrated that DPC can lead to accurate distributed hierarchical agglomerative clustering provided that the triangle inequality and granularity requirements are met.

Abstract: This paper describes an algorithm, Distributed Pivot Clustering (DPC), that differs from prior distributed clustering algorithms in that it requires neither an inexpensive approximation of the actual distance function nor that pairs of elements in the same cluster share at least one exact feature value. Instead, DPC requires only that the distance function satisfy the triangle inequality and be of sufficiently high-granularity to permit the data to be partitioned into canopies of optimal size based on distance to reference elements, or pivots. An empirical evaluation demonstrated that DPC can lead to accurate distributed hierarchical agglomerative clustering provided that the triangle inequality and granularity requirements are met.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.