Explaining Decisions: On Problem Solving and Analogical Reasoning in Human-Centered Explainable AI

Many problems humans face require making consecutive decisions while gathering information about the problem, its states, possible actions and goals. These sequential decisions can be done under uncertainty or in changing environments. Algorithms are often used to help people find good solutions, especially when the problem requires the optimization of certain aspects like finding the cheapest, fastest or most profitable solution. These problems are often too complex to be solved by humans alone, but also include weak constraints or preferences that are hard to pin down, so they cannot be done entirely by machines and humans have to work with machine assistance to solve them. Such collaboration requires a good understanding of the suggested solutions, and can be greatly improved when machines use similar representations and reasonings to their human coworkers and provide adequate explanations. The first step towards generating such explanations is to analyze different problem-solving tasks. A task’s states, actions, transitions and goals can have various features of how the task presents itself to the problem solver. We looked at different tasks that were used in problem-solving and sequential decision-making experiments and defined ten descriptive features. These determine the structure of the search space and subsequently influence how humans and algorithms can solve the task and what heuristics and representations are used by participants. We compared 22 sequential decision-making tasks using these ten features. One such decision-making paradigm is the Furniture Factory, a management task we designed based on a resource allocation Mixed Integer Linear Program. We used the task in two different forms, an exploration task and a more gamified version with sequential decisions that could not be reversed. Participants had to use a given amount of various resources to build four kinds of furniture items with the goal of maximizing the resulting profit. Participants performed well in general and often found satisfactory solutions, but had a hard time finding or recognizing optimal solutions. We gathered participants’ concurrent reasoning and their post-hoc explanations in two qualitative studies. We formalized the heuristics participants mentioned and analyzed their complexities, to use them as the basis for automated explanations. A third behavioral study was conducted to gather a larger dataset to compare the found heuristics to participants’ action trajectories. Here, we could match 87% of participants’ decisions with at least one heuristic. The heuristics were used in a generalized form to generate a step-by-step rationale for the optimal solution for resource allocation and requirement satisfaction Linear Programs (LPs). We implemented a tool, SimplifEx, that uses various simplification and preprocessing methods to structure an LP and provides post-hoc explanations based on the heuristics for the different items in an optimal solution. Additionally, it produces a graph representation of the different steps and dominance relations between variables. These relations add valuable structure to an LP and its optimal solution, so we generalized the definition of dominance to include more cases. The comparison of variables based on their values can add structure and give valuable insights on the relation of the variables in an LP. Humans often use comparisons in their reasoning and explanations. They do not just compare single entities based on their features, but also draw sophisticated analogies between known and novel problems to solve them. Analogies are a staple of human cognition and a common tool in conveying and explaining novel concepts. We introduced two novel approaches of formalizing domains and combining them using Category Theory (CT). The first approach uses colored directed multigraphs, while the second approach represents the base and the target domain of an analogy as separate categories. The CT concept of a pullback is used to generate a representation of possible matches between two domains, and pushouts are used to combine the two domains to a new blended domain. In summary, this thesis combines several approaches of analyzing and comparing sequential decision-making problems and how people represent and solve them with the goal of using this knowledge to generate cognitively adequate explanations. Such explanations can build the basis for making assistant tools more accessible and improving the collaboration of humans and machines.

Bei der Lösung vieler Probleme müssen Menschen aufeinanderfolgende Entscheidungen treffen und dabei Informationen über das Problem, seine Zustände, mögliche Maßnahmen und Ziele sammeln. Diese sequenziellen Entscheidungen werden oft unter Unsicherheit oder in sich verändernden Umgebungen getroffen. Algorithmen werden häufig eingesetzt, um Menschen bei der Suche nach guten Lösungen zu unterstützen, besonders wenn das Problem die Optimierung bestimmter Aspekte erfordert, wie z. B. die Suche nach der günstigsten, schnellsten oder profitabelsten Lösung. Solche Probleme sind oft zu komplex, um von Menschen allein gelöst zu werden, beinhalten aber auch schwache Einschränkungen oder Präferenzen, die sich schwer formalisieren lassen und eine vollständige maschinelle Lösung verhindern. Daher müssen Menschen gemeinsam mit Maschinen an der Lösung arbeiten. Eine solche Zusammenarbeit erfordert ein gutes Verständnis der vorgeschlagenen Lösungen und kann erheblich verbessert werden, wenn Maschinen ähnliche Darstellungen und Argumentationsweisen wie ihre menschlichen Kolleg*innen verwenden und angemessene Erklärungen liefern. Der erste Schritt zur Erstellung solcher Erklärungen besteht in der Analyse verschiedener Problemlöseaufgaben. Die Zustände, Aktionen, Übergänge und Ziele einer Aufgabe können verschiedene Merkmale aufweisen, die beeinflussen, wie sich die Aufgabe den Problemlösenden präsentiert. Wir untersuchten verschiedene Aufgaben, die in Experimenten zur Problemlösung und sequenziellen Entscheidungsfindung verwendet wurden, und definierten zehn beschreibende Merkmale. Diese bestimmen die Struktur des Suchraums und beeinflussen damit, wie Menschen und Algorithmen die Aufgabe lösen können und welche Heuristiken und Darstellungen die Teilnehmenden verwenden. Anhand dieser zehn Merkmale verglichen wir 22 sequenzielle Entscheidungsaufgaben miteinander. Ein solches Entscheidungsparadigma ist die Möbelfabrik, eine Managementaufgabe, die wir auf Basis eines gemischt-ganzzahligen linearen Programms zur Ressourcenallokation entwickelten. Wir verwendeten die Aufgabe in zwei Varianten: als Explorationsaufgabe und als spielerische Version mit sequenziellen, nicht rückgängig zu machenden Entscheidungen. Die Teilnehmenden mussten eine festgelegte Menge verschiedener Ressourcen verwenden, um vier Arten von Möbelstücken zu bauen, mit dem Ziel, den resultierenden Gewinn zu maximieren. Sie schnitten im Allgemeinen gut ab und fanden oft zufriedenstellende Lösungen, hatten jedoch Schwierigkeiten, optimale Lösungen zu finden oder als solche zu erkennen. In zwei qualitativen Studien erfassten wir die Überlegungen der Teilnehmenden während der Bearbeitung sowie ihre nachträglichen Erklärungen. Wir formalisierten die genannten Heuristiken und analysierten ihre Komplexität, um sie als Grundlage für automatisierte Erklärungen zu verwenden. In einer dritten Verhaltensstudie wurde ein größerer Datensatz erhoben und die identifizierten Heuristiken mit den Handlungstrajektorien der Teilnehmenden verglichen. Hier konnten wir 87% der Entscheidungen der Teilnehmenden mindestens einer Heuristik zuordnen. Die Heuristiken wurden in verallgemeinerter Form verwendet, um eine schrittweise Begründung für die optimale Lösung linearer Programme (LPs) zur Ressourcenallokation und Bedarfsdeckung zu generieren. Wir implementierten ein Tool namens SimplifEx, welches verschiedene Vereinfachungs- und Vorverarbeitungsmethoden verwendet, um ein LP zu strukturieren, und das auf Basis der Heuristiken nachträgliche Erklärungen für die verschiedenen Elemente einer optimalen Lösung liefert. Darüber hinaus erstellt es eine grafische Darstellung der einzelnen Schritte und der Dominanzbeziehungen zwischen den Variablen. Da diese Beziehungen einem LP und seiner optimalen Lösung eine nützliche Struktur verleihen, verallgemeinerten wir die Definition der Dominanz, um weitere Fälle einzubeziehen. Analogien sind ein fester Bestandteil menschlichen Denkens und ein gängiges Mittel, um neue Konzepte zu vermitteln und zu erklären. Wir erstellten zwei neuartige Ansätze, um Domänen mithilfe der Kategorientheorie (KT) zu formalisieren und zu kombinieren. Der erste Ansatz verwendet farbige gerichtete Multigrafen, während der zweite Ansatz die Basis- und die Zieldomäne einer Analogie als separate Kategorien darstellt. Das KT-Konzept eines Pullbacks wird verwendet, um mögliche Übereinstimmungen zwischen zwei Domänen darzustellen, während Pushouts dazu verwendet werden, beide Domänen zu einer neuen gemischten Domäne zu kombinieren. Zusammenfassend verbindet diese Arbeit verschiedene Ansätze zur Analyse und zum Vergleich sequenzieller Entscheidungsprobleme und der Art, wie Menschen diese darstellen und lösen, mit dem Ziel, dieses Wissen für die Entwicklung kognitiv adäquater Erklärungen zu nutzen. Solche Erklärungen können dazu beitragen, Assistenzwerkzeuge zugänglicher zu gestalten und die Zusammenarbeit zwischen Mensch und Maschine zu verbessern.