A CASE-BASED REASONING APPROACH TO THE IDENTIFICATION OF MATERIALS FROM DIFFRACTION PATTERNS

Abstract

X-ray diffractometry, within materials engineering, is a promising area of application for case-based reasoning. A large database of spectral diffraction patterns includes entries with different quality marks; moreover, several diffraction patterns happen to be equivalent, identifying the same material (crystalline phase), even though it also happens, that a spectral diffraction pattern alone would not identify a crystalline phase, and parameters such as density also have to be involved for identification. Current practice in the scanning and processing of so-called powder diffraction files, out of a database of files (formerly cards), calls for improvements of various kinds. Arguably, case-based reasoning is a technique from within AI that appears to exhibit a very interesting potential to make the process of identification less cumbersome.

INTRODUCTION TO THE APPLICATION DOMAIN

In materials science and physical chemistry, the definition of a phase is: a portion of a material in which all the intensive properties, such as density or specific heat capacity, are continuous variables in any coordinate systems. The phases are divided into three groups: alloys, compounds, and pure elements. An alloy is a phase with more than one element existing in a wide composition range. A compound is a phase that consists of more than one element in a fixed composition. A pure element is a phase consisting of a single element.

In this article, by the concept of crystalline phases (CPs) we will be referring to any particular state of material that is defined by the exact molecular and crystallographic structure. Based on this definition, even a slight difference in composition must define two different CPs. Each CP exists in a certain temperature and pressure; otherwise the interatomic distances are not certain.

Diffraction is a special case of the scattering of wave or particles into discrete directions. The modern definition of a crystalline material is as follows: a crystalline material diffracts any radiation with a wavelength below the interatomic distances. The common radiation source is x-rays, which easily can be produced even in small laboratories. Other sources, like neutrons or synchrotron beams, are limited to central regional laboratories.

For a given monochromatic radiation with wavelength λ, the directions and intensities of the diffracted beams are strongly dependent on the atomic or ionic arrangement in the CP. For each scattering angle 2θ, it is possible to define a reflecting plane that is associated with a vector D. If we define a scalar d = |D|, the reflection angle θ is given by

The relative intensity I of the diffracted beam is linked to the d value of each reflection. Thus, for each CP a specific set of {d, I} pairs is obtained. (We will also refer to these as d-I or D-I pairs.) This set is called a Diffraction Pattern (DP). Each CP has its own DP. The DP is very sensitive to the CP structure, so even a small difference between structures of two phases results in different DP. The qualitative CP analysis is based on this background. Each DP serves as a fingerprint for a CP. Thousands of DPs are stored each year in an international database, which is managed by the International Center for Diffraction Data (ICDD). The ICDD deals only with the collection of DPs and a distribution of a database of known CPs. A selection of the CP properties, including the DP, are stored in a database of files called Powder Diffraction Files (PDFs). Most properties are defined as keys for search during navigation in the database. Historically, it used to be a database of cards, whereas in current practice, the data are stored electronically in files.

The most applicative use of the ICDD database is for CP identification. The crystalline material is tested by diffraction, and its DP is served as an input for search-match procedure in which all PDFs are searched in order to match known CPs. Considering all CPs' properties, each CP is unique. Moreover, the number of different CPs is unlimited, because in alloys even a small gap in composition defines a new phase. New CPs are also obtained via variations in temperature and pressure. Since the amount of PDFs is limited to materials that have been tested in the past, whereas the amount of CPs is unlimited, the set of PDFs is much smaller than the set of CPs. Consequently, it occasionally happens that some DP obtained from a CP does not match any PDF pattern. In this case, it is impossible to identify the material and the search-match fails.

In some cases there is also an opposite phenomenon in which several CPs can have a common DP. In this case, the search-match does not fail, but supplies several solutions. For example, tantalium (Ta) and niobium (Nb) have the same atomic radius (0.146 nm). At room temperature, Ta and Nb have the same crystal structure with almost the same interatomic distances. Thus, two PDFs with the same d-I list are in existence for Ta and Nb. The DP from each of the two CPs will also match the second one. In order to complete the identification process, additional tests should be made, for example, density measurement.

DESCRIPTION OF A PATTERN DIFFRACTION FILE (PDF)

Each PDF has an identification number from a combination of two numbers. The first of these is the set number, which corresponds to the year of data collection. For the first year of the database (1951), the set number is 1, at the second year the set number is 2, and so forth. The second number is a serial number within the set. For example, the compound TiO ₂ (Brookite) has a PDF #29-360.

There are three kinds of files with different levels of information:

	PDF-1 only contains a title and a d-I list.
	PDF-2 and PDF-4 includes many details about the crystallographic phase and a d-I list.
	PDF-3 includes the raw data of the diffraction pattern.

Only PDF-2 and PDF-4 can be utilized for search of a subgroup from a selection of conditions. Each file includes the following information in the following spaces:

1. The PDF number

2. The chemical formula and name of the specimen

3. The structural formula and mineral name

4. The experimental conditions

5. The physical data

6. The optical data

7. General comments

8. Wavelength

9. Quality mark

10. Interplanar spacings (DP)

QUALITATIVE CRYSTALLINE PHASE ANALYSIS

The qualitative crystalline phase analysis is actually an identification process of all crystalline phases in a substance, which in turn can be completely unknown or with partial information. The latter may include:

1. –chemical analysis (the elements are known but not how they are organized),

2. –origin of the substance (ash of wood, for example).

The procedure takes place in three steps:

1. formation of DP from the substance (by using x-ray diffraction);

2. creation of a subgroup of all CPs which may be included in the substance, excluding all CPs whose presence in the substance is impossible;

3. comparing of the DP with the PDFs of all CPs belonging to the subgroup formed at step b.

The ICDD database suggests several options for retrieval, of either a single PDF or a group of PDFs, by using direct query or by Boolean search.

A list of options follows:

1. PDF number

2. Subfile

3. Inorganic chemical name

4. Mineral name

5. Organic chemical elements

6. Chemical elements

7. Strongest lines

8. Chemical abstract service number

9. Inorganic chemical name fragments

10. Mineral group code

11. Reduced unit cell parameter

12. Principal authors

13. Journal year

14. Journal CODEN

15. Density

16. Reduced cell volume

17. Long lines (d-spacings)

Some of the above options are just for finding a PDF of a known CP. Some of the options are useful only for pure materials. For example, a CP with a small amount in a green powder can be a white material, and its stronger diffraction line can be weak in the sample.

The options are fixed. It is impossible to teach the database to add options. However, it is possible to create several groups or even to use the entire database.

Once an operative database was selected, the search of CPs that match the DP is made by comparing the d-Is of the operative database with the DP. At this stage, the program is blind to other characteristics apart from the diffraction patterns. Since both the DP and the PDF can have errors in their data, there is some flexibility in the comparison. A tolerance of error is always assumed. The ICDD database does not enable the user to make changes to its content. The search match procedure is provided by the analytical equipment. It is possible to update the operative database by adding external PDFs, but the principal database is not modified. The new patterns are added manually into one of the selected groups of the operative database.

On this domain, qualitative diffraction analysis, see an introduction in Lipson and Steeple (1970, Ch. 10), Wilson (1970, pp. 14–18), and Azarof (1968, Ch. 19); also see Smith (1989), and Jenkins and Smith(1987). Such qualitative analysis is a necessary step amount of quantitative x-ray diffractometry, which is the subject of Zevin and Kimmel (1995), a book by the first author named.

THE ICDD DATABASE IN ITS PRESENT FORM: INDUSTRY'S CONSTRAINTS

As mentioned earlier, thousands of DPs are stored each year in an international database, which is managed by ICDD. The ICDD deals only with the collection of DP and the distribution of a database of known CPs. Our own project was undertaken independently of ICDD, and nevertheless relies on a format determined by industry, namely, by the configuration of the products sold by ICDD (see http://www.icdd.com/products/2008SalesCatalog.pdf). In the past several years, these products have evolved. Now, the ICDD calls the databases: PDF-1, PDF-2, PDF-3, PDF-4.

	Of these, PDF-1 was used in the past, when the storage space for files was limited. Now all search match programs work directly with PDF-2 or PDF-4 databases which are stored on a single CD or DVD.
	As to PDF-2, which is currently used, the ICDD now sells the database as a license for 5 years. Annual renewal is an option.
	PDF-3 is the raw data.
	PDF-4 is an online service. The user must renew the contract every year; otherwise it expires.

Both PDF-2 and PDF-4 include the XRD data as d-I both experimental and calculated. Remember that, as explained earlier, the relative intensity I of the diffracted beam is linked to the d value of each reflection. Thus, for each CP a specific set of {d, I} pairs is obtained. These we call d-I.

PDF-2 provides only the unit cell dimension, space group, formula, density, molecular weight, and numbers of atoms and formula in the unit cell. PDF-4 provides complete crystal data, including atomic positions. As advertised by ICDD, PDF-4 also utilizes PDF-3 for comparing the diffractogram of unknown phases with the diffractograms from PDF-3 of the phases found by the search-match. In most cases, the professional user of PDF-2 can easily fill the gap between PDF-2 and PDF-4 by using free literature and software.

In this section, we have focused on what industry provides. This, of course, is paramount, as it constrains the configuration of our own project. This is an aspect of projects that is also relevant to other situations in engineering, such as the design of refuellings at nuclear plants (Nissan 1998a, 1998c).

DEFICIENCIES OF THE PRESENT METHOD AND SUGGESTIONS

The main problem is the gap between the finite number of PDFs and the unlimited number of different CPs. Other problems originated from errors in PDFs or DPs, wrong selection of operative database, and the phenomenon of multiplicity of matched CPs.

In order to reduce the gap between the PDF/CP numbers, it is necessary to set up a new search-match procedure which enables to distinguish all similar phases, with the same prototype but different unit cell dimensions, for example. Another extension of the search-match procedure is to make the procedure open to changes, to be able to learn—hence, a clear potential for machine-learning application.

Once this concept will be adopted and utilized, it will be possible to enter all crystal types or families. In order to handle the experimental errors and continuous ranges of variables, like cell parameters in alloys, the program should be equipped with tools for correcting the data instantly during the search-match procedure. For example, it should be possible to use a standard to calibrate the DP and to identify PDFs with a similar pattern, even as the d spacing is beyond the accepted tolerance.

The practitioner resorts to various heuristics when working with the database. Knowledge acquisition (on which, see Diaper (1989))—in the domain and for the task at hand—can probe into gradually deeper layers of such human knowledge, even without incorporating deep models of the physics and chemistry involved.

CASE-BASED REASONING

Case-based reasoning (CBR) is a powerful problem-solving class of techniques within AI (Leake, D.B. 1996. CBR in context: The present and future. Chapter 1 in: Case-Based Reasoning: Experiences, Lessons, and Future Directions, ed. D. Leake. Menlo Park, CA: AAAI Press/MIT Press. Watson and Marir 1994; Kolodner 1993a, 1993b; Riesbeck and Schank 1989). Early origins are associated with Roger Schank (Schank 1986; Schank and Leake 1989). CBR enables solving new cases by utilizing the experience gathered in precedent cases. Case-based reasoning is relevant for any intelligent domain where experience is important. In CBR, the assumption is that the world is consistent. Although this assumption is not always true, in many domains it is dominant and practical. Case-based reasoning has been successfully employed in a variety of domains (e.g., see Liang and Turban (1993), or then, Knight and Nissan (1999b), the latter co-edited by one of the present authors). Such domains include: mediation (Kolodner, Simpson, and Sycara-Cyranski 1985), law (Ashley 1991) (as well as in HaCohen-Kerner and Schild (1999) and HaCohen-Kerner (1997) by one of the present authors), medicine (Koton 1988), cooking (Hammond 1986), navigation of an autonomous robot (Ram and Santamaria 1997), and chess (on which see Kerner (1995a, 1995b). Kerner is HaCohen-Kerner).

CYRUS, Janet Kolodner's program, used to answer questions on the travels and meetings of Cyrus Vance from his tenure as U.S. Secretary of State under the Carter administration. While applying Roger Schank's dynamic memory model, CYRUS applies difference-based automated dynamic indexing and reorganizing; with difference-based indexing, similar cases are stored and distinguished according to automatically identified differentiating features of the given case. See Kolodner (1983a, 1983b, 1984); also see Kolodner and Riesbeck (1986). The kind of CBR model from CYRUS was to inspire, e.g., PERSUADER (Sycara 1987), a tool for negotiation in adversarial conflicts.

On occasion, one can find a merger of CBR with other major approaches—e.g., with fuzzy modelling in Yager (1996)—and this, in turn, is in line with the emergence within AI of hybrid techniques (see, e.g., Nissan (1998b)). In Schank (in this issue: (Schank 2009)), a radical critique is provided on how planning, one of the main areas of AI, has been modelled in AI throughout the history of the discipline. That article argues that if human cognition is to provide inspiration, then it stands to reason that plans out of a repertoire should be adapted; always devising plans from scratch is not the proper way to go about it. The technical framework for adopting the adaptive approach is provided by CBR indeed.

In one thriving applied area of AI, namely, AI modelling of legal reasoning (“AI & Law”), the application of CBR is sometimes legitimate, and sometimes illegitimate. Legal cases per se are not amenable to AI CBR: adjudication in court must always be on a case-by-case basis, and whereas in Continental Law, the courts go by the rules, in the Anglo-American system (sometimes called “case-based law”), precedents guide the factfinders, who nevertheless retain an ample margin of discretion in how they apply the precedents. Provided that this discretionary aspect of judicial decision-making is respected, CBR can find application in software systems intended to assist with tasks within law. Let us exemplify such applications of CBR to a task within law that are uncontroversially legitimate. A team from Portugal reported (Costa, Sousa, and Neves 1999) about an application to legal precedents of case retrieval nets (with similarity arcs and relevance arcs), within the CBR class of methods.

And here is the second example: The Judge's Apprentice, a CBR system developed by Yaakov HaCohen-Kerner as a doctoral project under Uri Schild's supervision (Schild and Kerner 1994; HaCohen-Kerner and Schild 1999; HaCohen-Kerner 1997), is intended for enhancing uniformity of sentencing in criminal cases for given categories of offenses, in a country (Israel) with a bench-trial tradition. It would suggest a sentence to the judge, based on precedents in Israeli law (which is, in the main, like the Anglo-American system, except that there is no jury, and the fact-finders are only the judges who are judging the given case). The precedents are identified by the tool among former trials judged at Israeli courts, and such that the narrative of the criminal event is similar, though possibly (and quite likely) differing by significant details, which may be aggravating or mitigating circumstances. The tool provides an explanation to justify its advice to the judge in the case at hand. The tool has been praised by members of the judiciary and related professions, and also resulted in an IPA Award for Kerner from the Information Processing Association of Israel.

Police investigation is yet another area of application of CBR. The work reported about in Oatley, Zeleznikow, and Ewart (2004) is concerned with assisting the police in detecting the perpetrators of burglary from homes, which is a high-volume crime with low detection rates; that project made use of a variety of data mining techniques, including: classification and association rules, neural network clustering, survival analysis and Bayesian belief nets, CBR, as well as ontologies, and logic programming. Besides, to say it with Nissan (2008):

Keppens and Zeleznikow (2002, 2003) have reported about a project whose application is in post-mortem inquests, with the goal of determining whether death occurred through natural causes, homicide, or suicide. In their Dead Bodies Project, a so-called “truth maintenance system,” or ATMS (a well-known AI approach to consistency) is resorted to, in order to maintain a space of “possible worlds” which correspond to hypothetical scenarios. […] The project resorts to neither conventional expert systems, nor CBR. Any case is potentially unique. Crime investigation is very difficult to proceduralize. The design solution adopted for this project was to develop a model-based reasoning system, i.e., such a system that given a problem instance, a model of the problem is constructed, and a problem-independent technique is applied. In the same project, dynamic preference orderings are assigned to uncertain events. Default orderings may be overruled by inferred orderings.

A CBS that generates explanations for unusual death stories is SWALE, whose perspective within CBR is one of explaining out anomalies (Kass 1990).

Research into formal models of argumentation, which are oftentimes applied within “AI & Law,” has also concerned itself with CBR. In logic-based research into argumentation, Prakken and Sartor remarked (2002):

The focus was first on reasoning with rules and exceptions and with conflicting rules. After a while, some turned their attention to logical accounts of CBR […]. Another shift in focus occurred after it was realized that legal reasoning is bound not only by the rules of logic but also by those of fair and effective procedure. Accordingly, logical models of legal argument have been augmented with a dynamic component, capturing that the information with which a case is decided is not somehow ‘there’ to be applied, but is constructed dynamically, in the course of a legal procedure.

INTRODUCING A BRIEF OUTLINE OF OUR PROPOSAL

What we claim as our desideratum is the construction of a prototype of the model, which would further develop into a useful system that will serve in crystalline phase identification from powder diffraction files. Our information includes a database provided by an accepted body (which in turn had disparate sources), and whose entries—that for our purposes with CBR will be the Old Cases (OCs)—are in a number of a 10⁴, possibly even 10⁵, order of magnitude. This takes into account the local record of practice on the part of the initial intended user (or the present developers), even though general validity of the tool for other potential users is a paramount requirement we set. Yet, the quantity of entries involved in the development of the project understandably will not be as high; to implement and fine tune the application, we expect to be zooming on a given class of materials. Also note that not all files in the database are ranked at the same quality level in terms of credibility. This is an extant explicit parameter (quality mark: see above, item 9 in the list of parameters as provided the Section “Description of a Pattern Diffraction File”).

A caveat is necessary. We are talking about x-ray diffractometry, a term unfamiliar to many who have heard, instead, about spectroscopy. We are dealing here with diffraction (or elastic scattering). There does exist, as well, x-ray spectroscopy, which deals with elemental analysis. This is absolutely different from x-ray diffractometry. In spectroscopy, what is unknown would eventually take its value only from the ca. 100 elements that appear in the periodic table. By contrast, the number of unknown structures (“phases”) is unlimited.

ABSTRACT CASES OR VIRTUAL, PROTOTYPE CASES?

Ram and Santamaria (1997), in their SINS system, introduce two creative kinds of cases: abstract cases and virtual cases. An abstract case is a generalization of the new case (NC) and one or more Old Cases (OCs), cases for retrieval. A virtual case is a prototype case, a representative case. In contrast to the abstract case, the virtual case is not a generalized case, but rather a weighted average of some cases. Abstract cases and virtual cases can be put in the case base instead of the OCs. This can reduce the size of the database. Furthermore, these cases can include knowledge contained in the NCs, which was not expressed before in the case base. However, replacing OCs by these new kinds of cases might cause the loss of important knowledge. Therefore, construction of abstract cases and virtual cases has to be done carefully.

Another method is to create abstract cases and virtual cases and add them to the case base in addition to the OCs, and not instead of them. This is more like our situation with the database of powder diffraction files; we can add cases by storing them separately, while not being able to modify the standard database. Creation of abstract cases and virtual cases and deletion of cases are relevant to case-based systems with a rather large number of cases, or with a big ratio of new cases being input. For our present project, it's abstract cases (rather than prototype cases) that are relevant, along with the OCs; abstract cases would be weighted according to several OCs; prototype cases that do not appear in the OCs are of lesser interest. (Note also that one of the techniques of adaptation known from the CBR literature is abstraction and respecialization, which Alterman (1988) used in his PLEXUS planning system; by contrast, we have been discussing in this paper such abstractions prestored statically for future use.)

Not being able to modify the standard database includes not being able to delete cases; yet this does not amount to preclusion of ways to ignore entries. Low values for the quality mark parameter in the database are the most obvious criterion for possible exclusion, for our purposes. Smyth and Keane (1995) describe an interesting strategy for deletion of cases. Their model finds such cases that damage the system's efficiency and delete them; the deletion is done only if it is obvious that it wouldn't damage the completeness of the system from the viewpoint of the extent of their cases.

THE CASE-BASED ALGORITHM

The following description does not include all the substages of the algorithm; it is general rather than detailed:

1. Inputting a NC and its processing.

2. Initial retrieval of relevant precedents.

3. Retrieval of the most relevant precedents by a similarity measure.

4. If a failure occurred during retrieval, that is, no precedent passed the similarity measure necessary, then the system announces that there is no relevant precedent and does not allow a solution to be constructed.

5. If the retrieval was successful, then the closest, most similar precedent is set as the OC.

6. Construct a solution for the NC by using the OC.

7. Check and evaluate the solution.

8. In a case of failure by the criteria incorporated, an opportunity to recover can be offered: the user can be made to move on to a new inference for the NC, not according to the retrieved precedent, but according to another precedent amongst those that were retrieved as relevant for the NC if it exists.

9. If another precedent is chosen, then this case is defined as the OC and the system returns to stage 6.

10. Learning, as in acquiring cases and deleting cases, may be enabled or disabled: this is a strategic decision. For local use, enablement is arguably useful, without tampering however with the standard database.

RETRIEVING SUITABLE CASES AND PREFERENCE CRITERIA

Because of the quality mark difference in the database, there is expectation of some “noise.” (A concept is not to be excluded merely because of such noise; somewhat differently, such a principle is also known from cognitive and linguistic prototypes (Nissan 1995).)

We are going to describe, here, our similarity measure. Given an NC, we retrieve all cases that include at least one index found in the NC. Then, for these retrieved cases (OCs), we compute a similarity value between the NC to each OC. Cases are retrieved only if their similarity value is at least equal to the bottom limit of the similarity value that is considered medium (say, 0.4). The case with the highest similarity value to the NC is chosen for the next stage of the algorithm. Our similarity measure is similar to Tversky's contrast measure (Tversky 1977).

Our similarity measure has a more complicated general definition, like the one used in the Judge's Apprentice (HaCohen-Kerner 1997), and defined as follows:

where α, β, γ, and δ are specific constants, whereas f(NC ∩ OC) represents the weight of the identical features found in both cases; f(NC ∼ OC) represents the weight of the features found in one of the cases with a similar feature found in the other case; f(NC − OC) represents the weight of the features that are found in the NC but are neither in the OC nor have similar features in the OC; and finally f(OC − NC) represents the weight of the features that are found in the OC but are neither in the NC nor have similar features in the NC. Vis-à-vis Tversky's contrast measure (Tversky 1977), the present similarity measure, based on the one adopted for the Judge's Apprentice, includes a component of the similarity between similar indexes from a conceptual point of view. (In the Judge's Apprentice, this refers to considering nonidentical concepts that are similar enough according to the tree of hierarchical concepts.)

CONCLUDING REMARKS

In the project under discussion, the task is one of classification, the aim being the identification of a new case, based on a given spectrum and a database of spectra with different stated qualities. The identification process itself, as currently carried out by human experts with the help of a scanner, also involves the production of an estimate of how good the identification is. Noise is a big factor affecting the data: small changes in the material lead to big changes in the spectrum. The human expert does pattern-matching relying on his experience and on the summarized data from the scanner-based system. Problems affect the instruments and the measuring time. (Arguably, it should be possible to improve time-sharing in using the scanner, at a laboratory, by enabling successive quick scans, improving quality in successive passes up to a satisfactory threshold.) The enhancement resulting from the application of CBR is expected to be considerable indeed, automating part of the process, and also improving the identification of new cases and the very classification of the data from the database. The creation of abstract cases would consist of generalizing a case on an interval in the spectrum, or creating cases with different contexts. Learning from successes is also an aim for the CBR system we have described as being a desideratum.