Traditional methods of creating explanations from complex systems involving the use of AI have resulted in a wide variety of tools available to users to generate explanations regarding algorithm and network designs. This however has traditionally been aimed at systems that mimic the structure of human thought such as neural networks. The growing adoption of AI systems in industries has led to research and roundtables regarding the ability to extract explanations from other systems such as Non-Deterministic algorithms. This family of algorithms can be analysed but the explanation of events can often be di cult for non-experts to understand. Mentioned is a potential path to the generation of explanations that would not require expert-level knowledge to be correctly understood.1
Explainable AI (XAI) Adoption has been an area of growing interest for
several years and as the adoption of AI decision making systems continues to
increase, the need for explanations of a suitable quality by the end user has also
grown. This growth in adoption of AI decision making processes in industries in
which explanations are critical, such as the medical eld, has lead to increased
awareness of the need for high quality explanations regarding the decisions and
recommendations that these systems provide. As seen in the collection of
recommendations and conclusions from PHG [
Commons License Attribution 4.0 International (CC BY 4.0). { Responsibility refers to the role of people themselves and to the capability of AI systems to answer for one's decision and identify errors or unexpected results { Transparency refers to the need to describe, inspect and reproduce the mechanisms through which AI systems make decisions and learn to adapt to its environment, and to the governance of the data used and created.
As methods of explanation generation continue to develop over time it is key that, as industry adoption and regulation grows, so does the ability to explain the solutions provided by such AI systems. This in turn may aid in the acceptance of a set of solutions generated by the end user and an overall increase in understanding of the search methods and how the solutions were arrived at by the end user. Historically, this area of research has focused on optimisation systems that mimic the thought processes of human reasoning. These processes can be traced, and the path taken by these systems, such as Arti cial Neural Networks, can be somewhat more readily derived and understood by the end users of these systems. 2
Non-Deterministic Solvers or Non-Deterministic Algorithms are a metaheuristic search method that search for a solution or set of solutions to a given problem using stochastic processes. These stochastic processes, such as those in populationbased algorithms like Genetic algorithms, capture in a series of steps the learnings of the algorithm as they solve the optimisation problem rather than through the use of prior knowledge. This method allows the algorithm to avoid an exhaustive search of the problem space with the trade-o that solutions are often near-ideal. The stochastic search processes utilised mean that the creation of explanations based on a technical description of the decision points of an NDA tend to be difcult for non-experts and most end users to understand due to their complexity and need for prior knowledge of the system itself.
As an example, consider a delivery scheduling system for packages. It may fall on a company representative to attempt to explain the order that delivery sites were placed in or why a customer's site is the last to be visited. The exact path taken by an NDA cannot be predicted in advance and so with each run, a slightly di erent schedule may be created. A signi cant barrier to explanation in this scenario would be the end users lack of detailed information on how the scheduling system algorithm operates and how each decision was arrived at in order to form the solution provided. 3
Existing approaches to the explanation of decision points within AI systems
include the use of surrogate models. This approach involves the creation of an
external and more easily understood model that is trained on the results of the
Non-Deterministic Solvers and Explainable AI through Trajectory Mining
NDA. The extraction of explanations is then performed on this surrogate model
in order to discover how solutions were arrived at. Examples of this approach
can be seen the Local Interpretable Model-Agnostic Explanations
system (LIME)[
Algorithm Trajectories represents the collective implicit knowledge gained by a population-based algorithm as it traverses the solution space for high tness solutions to a provided problem and all decision steps taken. This knowledge is comprised of the populations created throughout the search process. Each population contains a set of solutions selected by the algorithm for their tness and throughout the search the solutions are altered with the intent to increase their tness. Over time as higher tness patterns are found within any given population, these may propagate throughout, leading to an overall decrease in population diversity as the search converges in a set of similar near-optimal solutions. Collectively, these populations over the course of one or more optimisation runs can be considered the Algorithm Trajectory.
This may prove to be a rich source of features and statistical evidence that can
be mined and visualised with the aim of generating an explanation with suitable
detail as to increase the end users ability to understand the problem and how
the decision was arrived at. The results of mining this algorithm trajectory, in
the form of visualisations and statistical gures, can then be used to develop
an explanation that is more easily understood through the inclusion of Natural
Language Generation (NLG) [
One example of using the post-hoc method of algorithm trajectory mining to
generate visualisations for the purpose of algorithm comparison can be seen in
[
While it is possible to generate explanations that cover the decision points of
NDAs and their path through the search space, they often require expert-level
knowledge of the model and concepts to understand. In this position paper, we
hypothesise that it is possible to develop a method following a similar path to
the previously mentioned surrogate model and LIME / SHAP example. This
hypothesised method would draw valuable statistical evidence and information on
problem structure from the algorithm trajectories generated during an
optimisation run. This post-hoc approach would involve using NLG to convert numerical
and scienti c data into human-understandable sentences and paragraphs while
being supported by visualisation techniques such as those outlined in [