framework for retaining ambiguous experiential knowledge from which cases can be extracted at retrieval time. This framework is compared to and aligned with related approaches to managing complex cases and explained through the specification of a work in progress CBR system for form understanding.
go with chili but knows there will be several vegetarians at the dinner. Looking through recipes for vegetarian chili, he chooses one that features beans and smoked peppers. He is now unsure what desert would go well with his choice of main. He recalls the last dinner party he had been to with a smoky, earthy main dish (burritos, in this case) had a desert, churros, that worked well. Finally, he notes that his chili recipe contains coriander – an ingredient at least one of his guests has an aversion to. Searching for advice, he finds a blog post for a curry recipe that suggests substituting cumin for coriander.
Computer aided cooking has been a popular domain with the CBR community, perhaps not because we are all such bad cooks that we need a lot of computer assistance, but more so the opposite: it serves as a salient example for applying the CBR cycle to problems with complex case representations because we are mostly all familiar with the reasoning process. In this example, we can see the complexity and inherent structure of the cases: dinner plans involve individual recipes which involve individual ingredients and cooking techniques. However, in Simon’s reasoning process, we also see how traditional notions of CBR may be challenged.
The prior experience that Simon seeks to leverage comes in a number of formats. He recalls a memory of an overall dinner plan (a case encompassing several dishes). He reads recipes for single dishes, some he reuses entirely where the ‘solution’ of the case appears to be the recipe itself, and others he extracts just a small element from; the ‘solution’ for his coriander problem is simply to replace one ingredient. Simon is able to evaluate all of this experiential knowledge and distill from it the relevant case details he needs to develop his dinner plans, but the structure and boundaries of the ‘cases’ he leverages are not just complex (cannot be represented with a simple feature vector), they are ambiguous (able to be interpreted in multiple ways). Why was cumin of interest in the curry recipe and not coconut milk? Why wasn’t the curry a solution to all of his constraints with the main dish – it also can be prepared vegetarian. These cases could be reused in multiple ways with diferent problem descriptions to consider and diferent solutions ofered, but these case details aren’t apparent until Simon views them through the lens of a particular sub-task within his dinner plan that he is working on.
Although this example is perhaps most relevant to case-based design, the ambiguity involved in the scenario is apparent in many CBR domains involving complex cases, especially where tasks are complex and involve multiple sub-tasks, or when multiple problem solving episodes are related and directly influenced by solutions provided in prior episodes. This paper, for example, will examine the role of ambiguity in case representations in the domain of form understanding. However, even if this phenomenon was unique to case-based design, this paper makes the argument that the benefit of loosening our restrictions on what it means to be a case is beneficial. Put simply, for many problem domains involving complex cases, it is better to take a more abstract view of the case base as a knowledge container holding experiences whose interpretation as cases may be dependent on details of the problem to be solved.
This paper isn’t introducing ambiguous cases as a brand new idea. There are many examples of what would qualify as ambiguous cases in existing CBR literature. Furthermore, this paper isn’t intended to be an authoritative review of ambiguous cases in prior CBR projects. However, this paper makes several contributions: • Several related projects are referenced to provide a broad view of ambiguous cases.
Readers will be better versed in determining ambiguity present in their own CBR projects and how to connect this ambiguity with the complexity of the task their system performs. • This view is applied in an abstract framework intended to be compatible with and improve existing approaches and frameworks dealing with ambiguous cases. Overall, this framework presents a new perspective in CBR that encourages CBR researchers using complex cases to consider how an ambiguous case representation could broaden the applicability of their work and improve their problem solving capabilities. • The abstract framework is illustrated through its application to the domain of document understanding within a work in progress digitization project.
The following section reviews other prior work that recommends modifications to traditional CBR frameworks to address complex case structures and distinguishes these approaches from our proposed perspective. In the third section, a unifying view over ambiguous cases is developed through examination of the ambiguous qualities of complex cases used in other prior work. The fourth section develops an abstract framework that provides a focus for implementations or CBR frameworks looking to adopt this perspective. The fifth section introduces form understanding as a problem domain for CBR and details how the proposed perspective will be applied through an ongoing CBR research project implementing a case-based form understanding system. The last section outlines conclusions and directions for future work.
It is not uncommon for CBR researchers, particularly those using complex case representations,
to consider frameworks with significant alterations to the traditional “4 R” case-based reasoning
cycle (Retrieval, Reuse, Revision, and Retention) [
Eisenstadt et al. introduced FLEA-CBR to address a number of applications, but notably
case-based design tasks (in particular floor plan design with MetisCBR) [
Such a focus on the knowledge containers of a CBR system to accommodate complex cases
is also not unprecedented. Cordier et al. implement an approach to acquiring adaptation
knowledge both from users and from data mining [
For the purposes of this paper, the concept of complexity in case representations will be
considered broadly to mean any significant divergence from a feature vector representation
in which a case is composed of a fixed-size vector of atomic values. In this sense, any of the
structured or semi-structured categories of representations recognized by Bergmann et al. would
be considered “complex” [
Conceptually ambiguous cases contain syntactically atomic abstractions that make the case
ambiguous – that is, they contain symbols that cannot be decomposed but can be interpreted
in multiple ways, semantically. For example, in the workflow domain, Bergmann and Gil
developed a framework used in several workflow management CBR applications that provides
for a conceptual hierarchy of labels applied to graph elements [
Compositionally ambiguous cases do not necessarily contain such abstractions, but the
boundaries of these cases may not neatly line up with a problem/solution pair. A compositionally
ambiguous case may contain multiple problems with one solution, multiple solutions with one
problem, or multiple cases entirely. They are distinct from conceptually ambiguous cases in that
the case knowledge is represented concretely and not abstractly and the source of ambiguity is
the boundary of the case rather than the concepts within it. One example is the Phala project
(Kendall-Morwick and Leake) which did not have a strict delineation between problem and
solution components of a case and instead extracted these components during the reuse phase
[
Some case representations contain elements of both types of ambiguity. For example, semantic
traces of stroke management episodes used by Montani et al. contained frequent series of actions
that were abstracted in to a single “macro-action”, making the case ambiguous both in terms of
its content and concepts [
Cases involving semi-structured data can typically be both conceptually ambiguous (using
more abstract terms and concepts in its descriptions) or compositionally ambiguous (conveying
numerous or otherwise structured concepts within the text). Berg et al. developed the
FEATURETAK framework to automate knowledge acquisition in the aviation domain [
Distinct from prior work, this paper suggests a framework that views the case base as a more generalized knowledge container than a collection of discrete cases with distinct problem and solution components. From this perspective we could instead view this knowledge container as the experience base. This experience base (pictured in Figure 1) is the source of case knowledge leveraged in latter phases of the 4R (or modified) cycle. This name “experience base” perhaps implies the presence of discrete ‘experiences’; however, this framework does not require that the content of the container necessarily be segmented in this way, nor does it require that elements of this container also have distinct problem and solution components. However it also does not forbid such structure. That is to say, a traditional case base still fits this framework. The perspective simply requires that discrete cases with distinct problem and solution components can be retrieved by some means from the experience base. The framework is considered abstract in the sense that fewer constraints are placed on representations of experience than for a traditional case representation, however this change does carry important implications for retrieval and retention as described below.
Retrieval within a system using a more generalized experience base involves not only finding
the case knowledge necessary to present cases to the reuse phase, but also assembling it in to
coherent cases. Commonly this will involve extracting cases from more ambiguous experiences,
similar to the approach taken by Kendall-Morwick and Leake [
Retention is also complicated by this perspective. The case to be retained may not comprise a new experience in the experience base and may instead involve an alteration of existing experiences within this knowledge container. For example, a conceptually ambiguous case that subsumes the most recent reasoning episode (as well as several prior reasoning episodes) may be updated to better reflect a world in which the most recent case occurred (perhaps a concept in the case becomes further abstracted). As another example, a compositionally ambiguous case may be updated to include a portion or all of the most recent case. Or perhaps retention is deferred to a time in which multiple cases have been resolved and are ready to be retained collectively as a new experience in the experience base. This component of the retention phase is referred to as “generalization”, and again, traditional case retention could fit this perspective by simply performing no generalization on revised cases.
This perspective on CBR is explored through early work to develop a case-based form understanding system. This system is being developed as part of a project to digitize four decades of physical documents used by the Computer Information Sciences department at Washburn University and organize the information contained in these documents in a database. Forms are the focus of this efort due to the structural nature of these documents that can be exploited by CBR techniques.
It’s worth noting that a project of this nature undertaken by an organization such as the CIS department will benefit from the frequent occurrence of common document formats (for example, internal course enrollment permission forms), allowing for carefully developed domainspecific solutions and limiting the need for a sophisticated case-based approach. However, the department’s records are primarily a test case for a project intended for personal use by the general public. Individuals in their own personal lives collect a large number of disparate forms containing important information for that individual that can be dificult to retrieve in situations where that information can be important (medical issues, tax audits, etc), making for a more compelling problem to which CBR can be brought to bear. Furthermore, unlike a computer science department, most individuals do not have access to professional programmers that can tailor software solutions to digitizing their personal files, thus highlighting the public benefit of such an open source software project.
This project is a work in progress. As of the time of this writing, scanning is currently ongoing and source code for the form understanding system is being developed. The abstract framework introduced in this paper, however, has been implemented through the development of sub-problem specifications described in later subsections.
While document scanning at Washburn University is ongoing, initial work in this project
is being performed with the FUNSD data set developed by Jaume et al. [
Jaume et al. additionally recognize three primary sub-tasks for which the data set provides training and testing data: text detection, text recognition, and form understanding, the last of which is split in to word grouping, semantic entity labeling, and entity linking. While various ML techniques are also applicable to these tasks, the opportunities for CBR, particularly utilizing the framework presented in this paper, are identified for two components of the form understanding problem along with two additional sub-tasks (document grouping and document classification).
Each sub-task will be performed either entirely manually (for evaluation purposes, the training data of the FUNSD data set is considered manually developed cases), interactively (the system provides a confidence score for a particular annotation and a user confirms or rejects it), or automatically (annotations with high enough confidence scores are automatically accepted). Results from reasoning episodes of each sub-task are retained within the experience base through an ambiguous experience record (an ordered collection of annotated scans, henceforth refereed to as a “document”) and reused in potentially any of the other sub-task scenarios. Tasks can be performed in any order as the decisions recorded from any task can aid in the execution of any other task. The diversity of sub-tasks coupled with the universal reliance on the same experiential knowledge structure through each sub-task makes this form understanding domain a good candidate for the implementation of the framework proposed in this paper.
Documents within the FUNSD data set do well to capture most of the types of noise one would encounter in a digitization project, however current progress through the Washburn CIS digitization project has uncovered an additional sources of noise: multi page forms that are split across several scans, forms that are duplicated in multiple scans, and multi-page scans that contain several diferent forms. Therefore “document reconstruction” was added as an additional task in which the page structure of the original documents is recovered from the scans of those documents.
For eficiency reasons, large stacks of physical documents are often scanned together in duplex. After scanning, all PDFs are split in to single page files (from this point forward a “scan” will refer to a one page file), but metadata conserving the order and grouping of the scans is retained. A problem solving episode consists of comparing two scans not known to be related and considering whether they are the same page, sequential pages in the same document, or unrelated.
Duplicate detection is fairly straightforward and can be performed successfully by comparing the raw data in the scans. However, determining whether two scans are part of the same physical document and the order they come in is more subtle and can benefit from the metadata recorded from scanning but also annotations retained from this and other form understanding sub-tasks described below. Cases are pairs of documents and are derived from the experience base by splitting existing documents in to two. Queries can be generated by considering any pair of existing documents in the experience base.
The current plan is to implement these tasks with deep learning baselines evaluated through the FUNSD project (such as Tesseract or the Google Vision API). The baselines perform well for text detection and recognition. Word grouping involves determining what words recognized in the scan should be considered as part of a group. FUNSD baselines consider this a clustering problem but perform poorly against the ground truth assessment. Although there are not current plans for a case-based approach to this task, a method improving on the baselines by incorporating layout data and semantic annotations from other sub-tasks would be warranted in future work.
This task is to assign semantic labels to known groups of words (question, answer, etc) and determine which questions and answers are associated with each other. The first task is a straightforward classification task. Given correctly annotated word groupings, cases are derived from the experience base by extracting labeled word groupings along with contextual details of the containing document. Queries can be generated from any unlabeled word grouping in any document in the experience base.
Linking labeled semantic entities involves generating cases by extracting existing linked pairs of question-labeled and answer-labeled semantic entities as positive cases in a binary classification task. Unlinked pairs will not be considered negative cases since, initially, most needed labels will not be present. Confidence in linking two question and answer semantic entities as a query will be determined from the similarity of the retrieved cases.
Classifications for documents associate them with known form types to facilitate information extraction. Cases and queries for this task are straightforward: classified and unclassified documents. Once word groupings are semantically labeled and linked in an unclassified document, they can collectively be used as a basis of comparison to other classified documents for case retrieval and reuse.
This paper has outlined the subtle diference between complexity and ambiguity in case representations and presented an abstract framework augmenting case representation, retrieval, and retention that is designed to take advantage of this ambiguity in problem domains involving complex and varied sub-tasks. The framework is explained through its relationship to prior work and its integration in an ongoing form understanding project. As this framework only involves a shift in how experiential knowledge is stored and retrieved, it is also compatible with most existing alternative frameworks to the traditional 4R CBR cycle that are popular in domains involving complex case representations. This framework is expected to enhance the flexibility of CBR systems working in these problem domains and provide inspiration for developers of full-featured frameworks used for design and other complex tasks.
As the form understanding project is ongoing, future work will involve an analysis of the results of the tasks described in section 5, comparing case-based approaches to machine learning baselines. Additional work on this project is expected to further automate the process of information extraction (for example, detecting hierarchical elements of forms and object detection). Other future work could include a wider literature review of ambiguity in case representations. As this framework is intended for CBR tasks with complex problem descriptions, additional comparison of the extraction phase to problem elaboration methods as well as conversational retrieval methods is warranted. Additionally, given that this framework involves frequent updates to existing experiential data, rather than simply the addition and/or deletion of cases, a comparison against studies of case base maintenance is important, as well as consideration of the implications of managing the provenance of experiential data under this perspective. Finally, although the form understanding project along with prior work in POCBR represents significant diversity of application of this framework, application to new domains (potentially creative applications, health CBR, or other design domains not mentioned) would be beneficial.