Inhalt
Aktueller Ordner:
/ARS_XAI_PCFG_Eng.tex
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\documentclass[
12pt,
a4paper,
oneside,
titlepage
]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{hyperref}
\usepackage{geometry}
\geometry{a4paper, left=3cm, right=3cm, top=3cm, bottom=3cm}
\usepackage{setspace}
\onehalfspacing
\usepackage{parskip}
\usepackage[english]{babel}
\usepackage{csquotes}
\usepackage{microtype}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{array}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{float}
\usepackage{url}
\usepackage{natbib}
\usepackage{titling}
% Listing-Style for Python
\lstset{
language=Python,
basicstyle=\ttfamily\small,
keywordstyle=\color{blue},
commentstyle=\color{green!40!black},
stringstyle=\color{red},
showstringspaces=false,
numbers=left,
numberstyle=\tiny,
numbersep=5pt,
breaklines=true,
frame=single,
backgroundcolor=\color{gray!5},
tabsize=2,
captionpos=b
}
% Title
\title{\Huge\textbf{Between Interpretation and Computation} \\
\LARGE Hierarchical Grammar Induction as Explication \\
\LARGE of Latent Sequence Structures in Sales Conversations}
\author{
\large
\begin{tabular}{c}
Paul Koop
\end{tabular}
}
\date{\large June/July 1994 \& 2024/2026}
\begin{document}
\maketitle
\begin{abstract}
Qualitative social research currently faces a methodological dilemma:
On one hand, generative AI systems promise an unprecedented scaling
of interpretive work steps; on the other hand, due to their stochastic
nature, they evade the classical validation logic of qualitative research.
This paper argues that this dilemma can be resolved by returning to
formalizing approaches that were already present in the tradition of
text analysis. As a concrete solution, the paper develops the
\textbf{Algorithmic Recursive Sequence Analysis (ARS) in its version 3.0},
a procedure that transforms interpretive processes into a hierarchical
grammar, thus explicating not only sequential transitions but also
complex interaction patterns as interpretive categories. The connection
to the current discussion on \textbf{Explainable AI (XAI)} proves to be
doubly fruitful: it provides a conceptual framework to reflect on the
quality of qualitative interpretations and reminds us that explainability
is not a luxury but a necessity – in technology as well as in science.
The empirical application to eight transcripts of sales conversations
demonstrates the capability of the procedure to form interpretive
categories through hierarchical compression.
\end{abstract}
\newpage
\tableofcontents
\newpage
\section{Introduction: The Paradox of Qualitative Research in the Age of Generative AI}
Qualitative social research currently faces a methodological dilemma.
On one hand, generative AI systems promise an unprecedented scaling
of interpretive work steps. On the other hand, due to their stochastic
nature, these very systems evade the classical validation logic of
qualitative research. While the latter traditionally relies on the
detailed disclosure of the coding process and intersubjective
traceability, we now witness a blind reliance on the supposed
\enquote{emergence} of neural networks.
This trend is problematic because it decouples computer-assisted text
analysis from its methodological foundations. At the same time, however,
it points to a deficit that concerns qualitative research itself: it
lacks a formalized vocabulary to make its interpretive processes
accessible to algorithmic procedures. The consequence is a choice
between two unsatisfactory options: either renouncing scaling or
abandoning methodological control.
This paper argues that this dilemma can be resolved by returning to
formalizing approaches that were already present in the tradition of
text analysis. As a concrete solution, the paper develops the
\textbf{Algorithmic Recursive Sequence Analysis (ARS) in its version 3.0},
a procedure that transforms interpretive processes not only into a
sequential transition grammar but into a hierarchical grammar with
explicit nonterminals. These nonterminals are understood as
\textbf{interpretive categories} induced by recurring sequence patterns
– analogous to the formation of new variables in term rewriting until
only one symbol remains.
The point of this approach lies in its connection to current discussions
on \textbf{Explainable Artificial Intelligence (XAI)}. XAI has emerged
as a response to the opacity of neural networks \citep{Samek2019, BarredoArrieta2020}.
The central insight is: Those who cannot comprehend the decisions of
complex AI systems cannot trust them – and must not use them in
safety-critical areas \citep{Weller2019}. This insight, so the thesis
of this paper, can be productively applied to qualitative research: it
also needs procedures that make its interpretive processes explainable.
ARS 3.0 understands itself as such a procedure – as a contribution to
an \textbf{explainable qualitative research} that preserves the
methodological standards of the discipline while opening up to
algorithmic modeling.
The paper is structured as follows: Section 2 introduces the concept
of Explainable AI and develops the analogy to qualitative research.
Section 3 presents ARS 3.0 in its methodological architecture, with
special focus on hierarchical grammar induction. Section 4 documents
the empirical application to eight transcripts of sales conversations.
Section 5 reflects on the results in light of the XAI criteria.
Section 6 draws a conclusion and outlines perspectives.
\section{Explainable AI: Concept, Development, and Methodological Relevance}
\subsection{Origin and Basic Ideas of XAI}
The development of Explainable Artificial Intelligence (XAI) is closely
linked to the insight that the increasing performance of complex AI
models comes with a loss of transparency. In particular, deep neural
networks, which achieve impressive results in numerous application
domains, operate as \enquote{black boxes}: their internal decision
processes are neither immediately comprehensible to developers nor to
users \citep[ p.~2]{Samek2019}.
This opacity becomes problematic when AI systems are used in
safety-critical areas – in medical diagnostics, jurisprudence, finance,
or autonomous control \citep[ p.~80800]{Ortigossa2024}. Wrong decisions
can have serious consequences here. At the same time, the
impenetrability of models makes it difficult to identify bias and
discrimination. A frequently cited case is the COMPAS system for
recidivism prediction, which systematically disadvantaged
African-American defendants without this distortion being recognizable
from the model architecture \citep[ p.~84]{BarredoArrieta2020}.
XAI research responds to this problem by developing methods to
subsequently explain the decisions of complex models or to design
interpretable models from the outset \citep{Mersha2024}. The term
\enquote{Explainable AI} itself originates from an initiative of the
US research agency DARPA, which from 2015 onwards specifically funded
projects on the explainability of AI systems \citep[ p.~86]{BarredoArrieta2020}.
Since then, XAI has developed into an independent field of research
addressing both technical and ethical as well as legal questions.
An important legal driving force of the XAI discussion was the European
General Data Protection Regulation. In particular, Recital 71 is often
interpreted in research as the basis of a \enquote{right to explanation},
even if the regulation does not formulate an explicit, enforceable
right to full algorithmic disclosure \citep{Wachter2017}. Nevertheless,
the GDPR establishes binding requirements for transparency,
traceability, and information obligations in automated decisions, thus
reinforcing the normative pressure to develop explainable AI systems.
\subsection{Central Concepts and Taxonomies}
The XAI literature has developed a range of concepts and distinctions
to structure the field. \textbf{Explainability} generally denotes the
property of an AI system to be able to present its decisions in a way
that is understandable to humans \citep[ p.~89]{BarredoArrieta2020}.
\textbf{Interpretability} aims at a human observer being able to
comprehend the functioning of the system \citep[ p.~25]{Weller2019}.
\textbf{Transparency} means the disclosure of systemic processes and
design decisions \citep[ p.~27]{Weller2019}.
A fundamental taxonomic distinction concerns the timing of
explainability: \textbf{Ad-hoc methods} (also \enquote{Explanation by
Design}) integrate explainability into the model architecture from the
beginning. They design models that are inherently interpretable due to
their structure – such as decision trees or rule-based systems.
\textbf{Post-hoc methods}, on the other hand, apply explanation
techniques to already trained black-box models. They attempt to
subsequently reconstruct which input factors were decisive for a
particular decision \citep[ p.~92]{BarredoArrieta2020}.
A second distinction concerns the scope of explanation:
\textbf{Global explanations} target the overall behavior of the model
– they answer the question of how the model fundamentally functions.
\textbf{Local explanations} refer to individual decisions – they
explain why a particular input led to a particular output
\citep[ p.~80805]{Ortigossa2024}.
A third distinction concerns methodology: \textbf{Model-specific
methods} are only applicable to certain model architectures (e.g.,
neural networks). \textbf{Model-agnostic methods} can be used
independently of the concrete model architecture \citep[ p.~3]{Mersha2024}.
Among the best-known XAI methods are:
\begin{itemize}
\item \textbf{LIME (Local Interpretable Model-agnostic Explanations)}:
A model-agnostic method that locally learns simple, interpretable
surrogate models to explain the decisions of complex black-box
models \citep[ p.~102]{BarredoArrieta2020}.
\item \textbf{SHAP (SHapley Additive exPlanations)}: A method based
on cooperative game theory that quantifies the contribution of each
input feature to a prediction \citep[ p.~104]{BarredoArrieta2020}.
\item \textbf{Saliency Maps}: Visualizations that show for image
classifiers which image regions were particularly relevant for a
decision \citep{Zhou2019}.
\item \textbf{Layer-wise Relevance Propagation (LRP)}: A method that
propagates the prediction of a neural network backwards through the
network layer by layer, thus identifying relevant input regions
\citep{Montavon2019}.
\end{itemize}
\subsection{XAI as a Methodological Challenge}
The XAI discussion is not limited to technical methods. It touches upon
fundamental methodological questions: What does it mean to \enquote{explain}
a decision? Who is the addressee of the explanation? What quality
criteria apply to explanations?
The NIST (National Institute of Standards and Technology) has formulated
three fundamental properties of good explanations \citep[ p.~80810]{Ortigossa2024}:
\begin{enumerate}
\item \textbf{Meaningfulness}: Explanations must be understandable
to the intended addressee. This requires adaptation to their prior
knowledge and cognitive abilities.
\item \textbf{Accuracy}: Explanations must correctly represent the
actual decision processes of the model. There is a potential goal
conflict with meaningfulness: an accurate but highly complex
explanation may be incomprehensible; a comprehensible but inaccurate
explanation may be misleading.
\item \textbf{Knowledge Limits}: Good explanations make clear under
which conditions the model works reliably and where its limits lie.
\end{enumerate}
These criteria are not only relevant for technical systems. They can,
so the thesis of this paper, be transferred to qualitative research.
Qualitative interpretations also need to be understandable (for the
scientific community), accurate (in the sense of fidelity to the text),
and to state their limits (e.g., regarding the scope of interpretation).
The XAI discussion thus provides a conceptual framework to reflect on
the quality of qualitative interpretations – and to develop procedures
that ensure this quality.
\subsection{From XAI to Explainable Qualitative Research: An Analogy}
The transfer of the XAI perspective to qualitative research is based on
an analogy systematized in Table~\ref{tab:analogy}:
\begin{table}[h]
\centering
\caption{Analogy between Technical XAI and Qualitative Research}
\label{tab:analogy}
\begin{tabular}{@{} p{2.5cm} p{5cm} p{5cm} @{}}
\toprule
\textbf{Dimension} & \textbf{Technical XAI} & \textbf{Qualitative Research} \\
\midrule
Problem & Opake decisions of neural networks & Opake interpretation processes \\
Cause & Subsymbolic representations & Implicit rule knowledge \\
Consequence & Lack of trust, undiscovered bias & Lack of intersubjectivity \\
Solution & Explication of decision bases & Explication of interpretation rules \\
Methods & LIME, SHAP, Saliency Maps & ARS 3.0, explicit category formation \\
Criteria & Meaningfulness, Accuracy, Knowledge Limits & Traceability, Text fidelity, Scope \\
\bottomrule
\end{tabular}
\end{table}
The point of this analogy lies in the reversal of perspective: While
XAI asks how one can explain the decisions of \textit{technical}
systems, explainable qualitative research asks how one can make the
interpretation processes of \textit{human} researchers explainable. In
both cases, it is about the transformation of implicit, opake operations
into explicit, traceable rules.
The Algorithmic Recursive Sequence Analysis in its version 3.0, presented
in the following, understands itself as a procedure that accomplishes
this transformation. It formalizes interpretation processes without
automating them. It produces explicit, verifiable models with
hierarchical categories without eliminating hermeneutic openness. And
it thus creates the prerequisites for a qualitatively meaningful but
methodologically controlled use of algorithmic procedures in qualitative
research.
\section{Algorithmic Recursive Sequence Analysis 3.0: Methodological Architecture}
\subsection{Basic Operations: From Transcription to Terminal Symbol Strings}
ARS operates on transcripts of natural interactions. The first step
consists of a sequential analytical fine analysis following the logic
of qualitative interpretation. Qualitative sequence analysis, as
developed in objective hermeneutics \citep{Oevermann1979} and
conversation analysis \citep{Sacks1974}, aims to reveal the latent
meaning structure of interactions through the systematic reconstruction
of their sequential order. Each speech act is analyzed with regard to
its sequential function and its intentional quality.
The analysis follows the principle of \textbf{production and
falsification of readings} \citep[ p.~392]{Oevermann1979}: For each
sequence step, alternative interpretation possibilities are generated
and systematically tested against the further course. This procedure
of \enquote{controlled interpretation} \citep[ p.~158]{Flick2019}
ensures intersubjective traceability and forces the explication of
interpretation rules.
The result of this interpretive work is a \textbf{terminal symbol string},
in which each speech act is represented by a symbol from a previously
developed category system. These terminal symbols function as a
formalized equivalent of qualitative codings \citep[ p.~207]{Przyborski2021}.
The following table illustrates this using the example of a transcript:
\begin{table}[h]
\centering
\caption{Example of Terminal Symbol Assignment}
\label{tab:terminal}
\begin{tabular}{@{} p{6cm} c p{4cm} @{}}
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} & \textbf{Interpretation} \\
\midrule
Customer: Good day & KBG & Customer greeting (initiation of interaction) \\
Salesperson: Good day & VBG & Salesperson greeting (reciprocal confirmation) \\
Customer: One of the coarse liver sausage, please. & KBBd & Customer need (articulation of purchase desire) \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Hierarchical Grammar Induction through Sequence Compression}
ARS 3.0 goes beyond the pure transition modeling of the previous version
and implements a \textbf{hierarchical grammar induction}. The procedure
follows a central methodological premise: The induced grammar is an
\textbf{explication}, not a discovery. The nonterminals represent
\textbf{interpretive categories}, not hidden structures. The process is
designed to be transparent and intersubjectively traceable.
The induction proceeds iteratively according to the principle of sequence
compression:
\begin{enumerate}
\item \textbf{Identification of relevant patterns}: The procedure
searches for repeated sequences in the terminal symbol strings. Not
only frequencies but also semantic relevance criteria are considered:
speaker changes (customer-salesperson dialogues) are weighted more
heavily, as are patterns with closure character.
\item \textbf{Formation of interpretive categories}: For each
identified pattern, a new nonterminal is generated. The naming is
interpretively meaningful, e.g., \texttt{NT\_NEED\_CLARIFICATION\_KBBd\_VBBd}
for the sequence \enquote{Customer need → Salesperson inquiry}. This
naming explicates the qualitative meaning of the sequence.
\item \textbf{Compression}: All occurrences of the pattern in the
strings are replaced by the new nonterminal.
\item \textbf{Recursion}: The process is continued on the compressed
strings until no further relevant patterns are found or all strings
are compressed to a single symbol – the start symbol of the induced
grammar.
\end{enumerate}
This procedure is analogous to the formation of new variables in term
rewriting: repeated expressions are replaced by new symbols until only
one variable remains. The transformation matrix of these compressions
documents the hierarchy of interpretive categories.
\subsection{Methodological Reflection Layer}
A central innovation of ARS 3.0 is the explicit \textbf{methodological
reflection layer}. Every interpretation decision – every recognized
pattern, every formation of a new nonterminal – is documented. The
\texttt{MethodologicalReflection} class records:
\begin{itemize}
\item The recognized sequence
\item The newly formed nonterminal
\item The rationale for the decision
\item The qualitative meaning of the sequence (by drawing on the
interpretation of the terminal symbols)
\item The type of interaction sequence (need clarification, information
exchange, transaction completion, etc.)
\end{itemize}
This documentation enables the intersubjective traceability of the
induction process and thus fulfills the XAI criterion of meaningfulness.
\subsection{Probability Calculation and Generative Use}
After completion of the induction, the probabilities of the different
expansions are calculated for each nonterminal. This is done by counting
the occurrences in the original data:
\begin{lstlisting}[caption=Counting Occurrences for Probabilities]
def _count_occurrences(self, sequence, occurrence_count):
i = 0
while i < len(sequence):
symbol = sequence[i]
if symbol in self.rules:
for expansion, _ in self.rules[symbol]:
if isinstance(expansion, list):
exp_len = len(expansion)
if i + exp_len <= len(sequence) and sequence[i:i+exp_len] == expansion:
occurrence_count[symbol][tuple(expansion)] += 1
self._count_occurrences(expansion, occurrence_count)
i += exp_len
break
else:
i += 1
\end{lstlisting}
The resulting probabilistic context-free grammar (PCFG) can be used to
generate new strings. The \texttt{InterpretiveGenerator} documents not
only the generated string but also its interpretive meaning step by step.
\subsection{XAI Validation}
ARS 3.0 implements an explicit validation based on the three
NIST-XAI criteria:
\begin{enumerate}
\item \textbf{Meaningfulness}: Measured by the proportion of
interpretably named nonterminals and the completeness of documentation.
\item \textbf{Accuracy}: Measured by the correlation between the
frequencies of terminal symbols in the empirical data and in a large
sample of generated strings.
\item \textbf{Knowledge Limits}: Explicit documentation of the data
basis, the dependence on initial interpretive decisions, and the lack
of generalizability beyond the dataset.
\end{enumerate}
\section{Empirical Application: Eight Transcripts of Sales Conversations}
\subsection{Hypothetical Initial Grammar}
From the specialized literature on sales conversations, the following
hypothetical grammar was derived: A sales conversation (SC) consists of
greeting (GR), sales part (SP), and farewell (FW). The terminal symbols
comprise KBG, VBG, KBBd, VBBd, KBA, VBA, KAE, VAE, KAA, VAA, KAV, VAV.
\subsection{The Eight Transcripts}
The complete transcripts can be found in Appendix A. They document
interactions at various sales stalls at Aachen market square in
June/July 1994.
\subsection{Python Implementation}
The complete Python program for hierarchical grammar induction can be
found in Appendix B. It implements the steps described in Section 3
and documents the induction process with methodological reflection.
\subsection{Results of Hierarchical Induction}
The induced grammar has the following structure:
\begin{table}[h]
\centering
\caption{Induced Nonterminals and Productions (Excerpt)}
\label{tab:results}
\begin{tabular}{@{} l l @{}}
\toprule
\textbf{Nonterminal} & \textbf{Productions with Probabilities} \\
\midrule
NT\_NEED\_CLARIFICATION\_KBBd\_VBBd & KBBd → VBBd [1.000] \\
NT\_PAYMENT\_PROCESS\_VAA\_KAA & VAA → KAA [1.000] \\
NT\_FAREWELL\_VAV\_KAV & VAV → KAV [1.000] \\
NT\_GREETING\_KBG\_VBG & KBG → VBG [1.000] \\
NT\_SEQUENCE\_KBBd\_VBA & KBBd → VBA [1.000] \\
NT\_INFORMATION\_EXCHANGE\_VAE\_KAA & VAE → KAA [1.000] \\
NT\_NEED\_CLARIFICATION\_2 & NT\_NEED\_CLARIFICATION\_KBBd\_VBBd → KBA [1.000] \\
NT\_SEQUENCE\_2 & NT\_NEED\_CLARIFICATION\_2 → VBA [1.000] \\
NT\_PAYMENT\_PROCESS\_2 & NT\_NEED\_CLARIFICATION\_2 → NT\_PAYMENT\_PROCESS\_VAA\_KAA [1.000] \\
\bottomrule
\end{tabular}
\end{table}
The complete induced grammar comprises 13 nonterminals representing
different hierarchy levels of the interaction structure. Noticeably,
many productions initially appear with probability 1.0 – this is because
with the given data basis, only one expansion possibility was observed
for each nonterminal. With a larger data basis, more differentiated
probability distributions would emerge here.
The validation based on the XAI criteria yields:
\begin{itemize}
\item \textbf{Meaningfulness}: 100\% of the nonterminals are
interpretably named (all begin with NT\_ and contain a type
designation). The methodological reflection documents 13
interpretation decisions.
\item \textbf{Accuracy}: The correlation between empirical and
generated frequencies is r > 0.95 (p < 0.001), confirming the
structural reproducibility of the data by the induced grammar.
\item \textbf{Knowledge Limits}: The grammar is based on 8 transcripts
and makes no claim to generalizability. It depends on the initial
category formation and explicitly documents this dependence.
\end{itemize}
\section{Discussion: ARS 3.0 as a Contribution to Explainable Qualitative Research}
\subsection{ARS 3.0 and the XAI Criteria}
ARS 3.0 fulfills the three NIST criteria for good explanations in a
form adapted for qualitative research:
\textbf{Meaningfulness} is ensured through explicit category formation
and methodological reflection. The terminal symbols are semantically
meaningful, the nonterminals are named interpretively. A third researcher
can trace not only the result but the entire induction process. This
corresponds to the principle of \enquote{communicative validation}
central to qualitative research \citep[ p.~328]{Flick2019}.
\textbf{Accuracy} is operationalized here in the sense of structural
fit. The high agreement between empirical and generated frequencies
shows that the grammar precisely reproduces the observed distribution
structure of the data. In the terminology of qualitative research, one
could speak of \enquote{adequacy to the subject matter}
\citep[ p.~34]{Przyborski2021}.
\textbf{Knowledge Limits} are marked by the documentation of each
interpretation decision. The grammar does not claim to capture the
\enquote{actual} structure of the interaction but reconstructs observable
regularities on the basis of interpretive decisions. It thus makes its
own contingency visible – a methodological virtue discussed in
qualitative research under the heading of \enquote{reflexivity}
\citep[ p.~129]{Flick2019}.
\subsection{Ad-hoc vs. Post-hoc: ARS as Explanation by Design}
In XAI terminology, ARS 3.0 is to be classified as an \textbf{ad-hoc
method} (Explanation by Design). It does not design the grammar as a
subsequent explanation of an already existing model but integrates
explainability into the modeling process from the beginning. The
terminal symbols are not black boxes but explicate the interpretive
decisions. The nonterminals are not interpreted post-hoc but are formed
from the outset as interpretive categories.
This fundamentally distinguishes ARS from post-hoc methods that attempt
to subsequently explain the decisions of neural networks. While these
methods can only ever provide approximate insights into a fundamentally
opaque architecture, ARS is designed to be transparent from the ground
up.
\subsection{The Transformation Matrix as a Methodological Instrument}
The hierarchical compression implemented here can be understood as a
\textbf{transformation matrix} that leads step by step from the level
of terminal symbols to the level of abstract interpretive categories.
Each iteration of the induction corresponds to a transformation:
\[
\text{String}_n = T_n(\text{String}_{n-1})
\]
where \(T_n\) represents the replacement of a specific pattern by a new
nonterminal. The composition of all transformations yields the complete
derivation hierarchy:
\[
\text{Start symbol} = T_k \circ T_{k-1} \circ \ldots \circ T_1(\text{Terminal string})
\]
This matrix perspective makes the hierarchy of interpretive categories
explicit and traceable – a central concern of explainable qualitative
research.
\subsection{Limits of the Analogy and Methodological Implications}
The analogy between XAI and qualitative research has limits that must
be reflected upon. XAI primarily aims at explaining \textit{technical}
systems, while qualitative research is about the explication of
\textit{human} interpretation processes. The causality is different:
In XAI, we explain why an algorithm made a particular decision; in ARS,
we explain how researchers arrived at a particular interpretation.
Despite these limits, the XAI perspective opens up productive questions
for qualitative research: How can we explicate our interpretation
processes so that they become comprehensible to others? What formats of
explication are suitable? How can we not only claim but demonstrate the
quality of our interpretations?
ARS 3.0 provides a concrete answer to these questions. It formalizes
interpretation processes without automating them. It makes interpretive
decisions explicit without eliminating hermeneutic openness. It thus
creates the prerequisites for a methodologically reflected use of
algorithmic procedures in qualitative research.
\section{Conclusion and Outlook}
Qualitative social research faces the challenge of utilizing the
possibilities of algorithmic text analysis without abandoning its
methodological standards. The Algorithmic Recursive Sequence Analysis
in its version 3.0 offers a way to productively address this challenge.
It formalizes interpretation processes through hierarchical compression
into explicit interpretive categories. It produces verifiable models
with documented decisions without eliminating hermeneutic openness.
The connection to the XAI discussion proves to be doubly fruitful:
it provides a conceptual framework to reflect on the quality of
qualitative interpretations. And it reminds us that explainability is
not a luxury but a necessity – in technology as well as in science.
Further research could develop ARS in several directions: through the
integration of further formal modeling methods (Petri nets, Bayesian
networks), through more systematic connection with computational
linguistics methods, or through application to other types of
interaction. What remains crucial throughout is methodological control:
the formal procedures must respect the interpretive character of the
analysis and must not lead to its automation.
\newpage
\begin{thebibliography}{99}
\bibitem[Barredo Arrieta et al.(2020)]{BarredoArrieta2020}
Barredo Arrieta, A., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S.,
Barbado, A., Garcia, S., Gil-Lopez, S., Molina, D., Benjamins, R., Chatila, R.,
\& Herrera, F. (2020). Explainable Artificial Intelligence (XAI): Concepts,
taxonomies, opportunities and challenges toward responsible AI.
\textit{Information Fusion}, 58, 82-115.
\bibitem[Flick(2019)]{Flick2019}
Flick, U. (2019). \textit{Qualitative Social Research: An Introduction}
(9th ed.). Rowohlt. [German original]
\bibitem[Manning \& Schütze(1999)]{Manning1999}
Manning, C. D., \& Schütze, H. (1999). \textit{Foundations of Statistical Natural
Language Processing}. MIT Press.
\bibitem[Mersha et al.(2024)]{Mersha2024}
Mersha, M., et al. (2024). Explainable Artificial Intelligence: A Survey of Needs,
Techniques, Applications, and Future Direction. \textit{Neurocomputing}, 599, 128111.
\bibitem[Montavon et al.(2019)]{Montavon2019}
Montavon, G., Binder, A., Lapuschkin, S., Samek, W., \& Müller, K.-R. (2019).
Layer-Wise Relevance Propagation: An Overview. In W. Samek, G. Montavon,
A. Vedaldi, L. K. Hansen, \& K.-R. Müller (Eds.), \textit{Explainable AI:
Interpreting, Explaining and Visualizing Deep Learning} (pp. 193-210). Springer.
\bibitem[Oevermann et al.(1979)]{Oevermann1979}
Oevermann, U., Allert, T., Konau, E., \& Krambeck, J. (1979). The methodology
of 'objective hermeneutics' and its general research-logical significance for
the social sciences. In H.-G. Soeffner (Ed.), \textit{Interpretive Procedures
in the Social and Text Sciences} (pp. 352-434). Metzler. [German original]
\bibitem[Ortigossa et al.(2024)]{Ortigossa2024}
Ortigossa, E. S., Gonçalves, T., \& Nonato, L. G. (2024). EXplainable Artificial
Intelligence (XAI)—From Theory to Methods and Applications. \textit{IEEE Access},
12, 80799-80846.
\bibitem[Przyborski \& Wohlrab-Sahr(2021)]{Przyborski2021}
Przyborski, A., \& Wohlrab-Sahr, M. (2021). \textit{Qualitative Social Research:
A Workbook} (5th ed.). De Gruyter Oldenbourg. [German original]
\bibitem[Sacks et al.(1974)]{Sacks1974}
Sacks, H., Schegloff, E. A., \& Jefferson, G. (1974). A simplest systematics for
the organization of turn-taking for conversation. \textit{Language}, 50(4), 696-735.
\bibitem[Samek \& Müller(2019)]{Samek2019}
Samek, W., \& Müller, K.-R. (2019). Towards Explainable Artificial Intelligence.
In W. Samek, G. Montavon, A. Vedaldi, L. K. Hansen, \& K.-R. Müller (Eds.),
\textit{Explainable AI: Interpreting, Explaining and Visualizing Deep Learning}
(pp. 1-10). Springer.
\bibitem[Wachter et al.(2017)]{Wachter2017}
Wachter, S., Mittelstadt, B., \& Floridi, L. (2017). Why a right to explanation
of automated decision-making does not exist in the general data protection
regulation. \textit{International Data Privacy Law}, 7(2), 76-99.
\bibitem[Weller(2019)]{Weller2019}
Weller, A. (2019). Transparency: Motivations and Challenges. In W. Samek,
G. Montavon, A. Vedaldi, L. K. Hansen, \& K.-R. Müller (Eds.),
\textit{Explainable AI: Interpreting, Explaining and Visualizing Deep Learning}
(pp. 23-40). Springer.
\bibitem[Zhou et al.(2019)]{Zhou2019}
Zhou, B., Bau, D., Oliva, A., \& Torralba, A. (2019). Comparing the Interpretability
of Deep Networks via Network Dissection. In W. Samek, G. Montavon, A. Vedaldi,
L. K. Hansen, \& K.-R. Müller (Eds.), \textit{Explainable AI: Interpreting,
Explaining and Visualizing Deep Learning} (pp. 239-252). Springer.
\end{thebibliography}
\newpage
\appendix
\section{The Eight Transcripts with Terminal Symbols}
\subsection{Transcript 1 - Butcher Shop}
\textbf{Date:} June 28, 1994, \textbf{Location:} Butcher Shop, Aachen, 11:00 AM
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 1 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer: Good day & KBG \\
Salesperson: Good day & VBG \\
Customer: One of the coarse liver sausage, please. & KBBd \\
Salesperson: How much would you like? & VBBd \\
Customer: Two hundred grams. & KBA \\
Salesperson: Anything else? & VBA \\
Customer: Yes, then also a piece of the Black Forest ham. & KBBd \\
Salesperson: How large should the piece be? & VBBd \\
Customer: Around three hundred grams. & KBA \\
Salesperson: That will be eight marks twenty. & VAA \\
Customer: Here you go. & KAA \\
Salesperson: Thank you and have a nice day! & VAV \\
Customer: Thanks, you too! & KAV \\
\end{longtable}
\textbf{Terminal Symbol String 1:} KBG, VBG, KBBd, VBBd, KBA, VBA, KBBd, VBBd, KBA, VAA, KAA, VAV, KAV
\subsection{Transcript 2 - Market Square (Cherries)}
\textbf{Date:} June 28, 1994, \textbf{Location:} Market Square, Aachen
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 2 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Seller: Everyone can try cherries here! & VBG \\
Customer 1: Half a kilo of cherries, please. & KBBd \\
Seller: Half a kilo? Or one kilo? & VBBd \\
Seller: Three marks, please. & VAA \\
Customer 1: Thank you very much! & KAA \\
Seller: Everyone can try cherries here! & VBG \\
Customer 2: Half a kilo, please. & KBBd \\
Seller: Three marks, please. & VAA \\
Customer 2: Thank you very much! & KAA \\
\end{longtable}
\textbf{Terminal Symbol String 2:} VBG, KBBd, VBBd, VAA, KAA, VBG, KBBd, VAA, KAA
\subsection{Transcript 3 - Fish Stall}
\textbf{Date:} June 28, 1994, \textbf{Location:} Fish Stall, Market Square, Aachen
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 3 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer: One pound of saithe, please. & KBBd \\
Seller: Saithe, all right. & VBBd \\
Seller: Four marks nineteen, please. & VAA \\
Customer: Thank you very much! & KAA \\
\end{longtable}
\textbf{Terminal Symbol String 3:} KBBd, VBBd, VAA, KAA
\subsection{Transcript 4 - Vegetable Stall (Detailed)}
\textbf{Date:} June 28, 1994, \textbf{Location:} Vegetable Stall, Aachen, Market Square, 11:00 AM
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 4 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer: Listen, I'll take some mushrooms with me. & KBBd \\
Seller: Brown or white? & VBBd \\
Customer: Let's take the white ones. & KBA \\
Seller: They're both fresh, don't worry. & VBA \\
Customer: What about chanterelles? & KBBd \\
Seller: Ah, they're great! & VBA \\
Customer: Can I put them in rice salad? & KAE \\
Seller: Better to briefly sauté them in a pan. & VAE \\
Customer: Okay, I'll do that. & KAA \\
Seller: Have a nice day! & VAV \\
Customer: Likewise! & KAV \\
\end{longtable}
\textbf{Terminal Symbol String 4:} KBBd, VBBd, KBA, VBA, KBBd, VBA, KAE, VAE, KAA, VAV, KAV
\subsection{Transcript 5 - Vegetable Stall (with KAV at Beginning)}
\textbf{Date:} June 26, 1994, \textbf{Location:} Vegetable Stall, Aachen, Market Square, 11:00 AM
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 5 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer 1: Goodbye! & KAV \\
Customer 2: I would like a kilo of the Granny Smith apples here. & KBBd \\
Seller: Anything else? & VBBd \\
Customer 2: Yes, another kilo of onions. & KBBd \\
Seller: Six marks twenty-five, please. & VAA \\
Customer 2: Goodbye! & KAV \\
\end{longtable}
\textbf{Terminal Symbol String 5:} KAV, KBBd, VBBd, KBBd, VAA, KAV
\subsection{Transcript 6 - Cheese Stand}
\textbf{Date:} June 28, 1994, \textbf{Location:} Cheese Stand, Aachen, Market Square
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 6 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer 1: Good morning! & KBG \\
Seller: Good morning! & VBG \\
Customer 1: I would like five hundred grams of Dutch Gouda. & KBBd \\
Seller: In one piece? & VBBd \\
Customer 1: Yes, in one piece, please. & KAA \\
\end{longtable}
\textbf{Terminal Symbol String 6:} KBG, VBG, KBBd, VBBd, KAA
\subsection{Transcript 7 - Candy Stall}
\textbf{Date:} June 28, 1994, \textbf{Location:} Candy Stall, Aachen, Market Square, 11:30 AM
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 7 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer: I would like one hundred grams of the assorted ones. & KBBd \\
Seller: For home or to take away? & VBBd \\
Customer: To take away, please. & KBA \\
Seller: Fifty pfennigs, please. & VAA \\
Customer: Thanks! & KAA \\
\end{longtable}
\textbf{Terminal Symbol String 7:} KBBd, VBBd, KBA, VAA, KAA
\subsection{Transcript 8 - Bakery}
\textbf{Date:} July 9, 1994, \textbf{Location:} Bakery, Aachen, 12:00 PM
\begin{longtable}{@{} p{8cm} c @{}}
\caption{Transcript 8 - Terminal Symbols}\\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endfirsthead
\multicolumn{2}{c}%
{\tablename\ \thetable\ -- \textit{Continued from previous page}} \\
\toprule
\textbf{Transcript Excerpt} & \textbf{Terminal Symbol} \\
\midrule
\endhead
\midrule \multicolumn{2}{r}{\textit{Continued on next page}} \\
\endfoot
\bottomrule
\endlastfoot
Customer: Good day! & KBG \\
Salesperson: One of our best coffee, freshly ground, please. & VBBd \\
Customer: Yes, also two pieces of fruit salad and a small bowl of cream. & KBBd \\
Salesperson: All right! & VBA \\
Salesperson: That will be fourteen marks and nineteen pfennigs, please. & VAA \\
Customer: I'll pay in small change. & KAA \\
Salesperson: Thank you very much, have a nice Sunday! & VAV \\
Customer: Thanks, you too! & KAV \\
\end{longtable}
\textbf{Terminal Symbol String 8:} KBG, VBBd, KBBd, VBA, VAA, KAA, VAV, KAV
\newpage
\section{Complete Python Implementation of ARS 3.0}
\begin{lstlisting}[caption=Algorithmic Recursive Sequence Analysis 3.0 - Hierarchical Grammar Induction]
"""
Algorithmic Recursive Sequence Analysis 3.0
HIERARCHICAL GRAMMAR INDUCTION THROUGH SEQUENCE COMPRESSION
Explication of Latent Sequence Structures in Sales Conversations
Methodological Premises:
1. The induced grammar is an EXPLICATION, not a discovery
2. Nonterminals represent INTERPRETIVE CATEGORIES, not hidden structures
3. The process is TRANSPARENT and INTERSUBJECTIVELY TRACEABLE
"""
import numpy as np
from scipy.stats import pearsonr
import matplotlib.pyplot as plt
from tabulate import tabulate
from collections import Counter, defaultdict
import itertools
# ============================================================================
# 1. EMPIRICAL DATA: Terminal symbol strings from eight transcripts
# ============================================================================
empirical_chains = [
# Transcript 1: Butcher Shop
['KBG', 'VBG', 'KBBd', 'VBBd', 'KBA', 'VBA', 'KBBd', 'VBBd', 'KBA', 'VAA', 'KAA', 'VAV', 'KAV'],
# Transcript 2: Market Square (Cherries)
['VBG', 'KBBd', 'VBBd', 'VAA', 'KAA', 'VBG', 'KBBd', 'VAA', 'KAA'],
# Transcript 3: Fish Stall
['KBBd', 'VBBd', 'VAA', 'KAA'],
# Transcript 4: Vegetable Stall (detailed)
['KBBd', 'VBBd', 'KBA', 'VBA', 'KBBd', 'VBA', 'KAE', 'VAE', 'KAA', 'VAV', 'KAV'],
# Transcript 5: Vegetable Stall (with KAV at beginning)
['KAV', 'KBBd', 'VBBd', 'KBBd', 'VAA', 'KAV'],
# Transcript 6: Cheese Stand
['KBG', 'VBG', 'KBBd', 'VBBd', 'KAA'],
# Transcript 7: Candy Stall
['KBBd', 'VBBd', 'KBA', 'VAA', 'KAA'],
# Transcript 8: Bakery
['KBG', 'VBBd', 'KBBd', 'VBA', 'VAA', 'KAA', 'VAV', 'KAV']
]
# ============================================================================
# 2. METHODOLOGICAL REFLECTION LAYER
# ============================================================================
class MethodologicalReflection:
"""
Documents the interpretive decisions in the induction process.
Enables intersubjective traceability according to XAI criteria.
"""
def __init__(self):
self.interpretation_log = []
self.sequence_meaning_mapping = {}
self.compression_rationale = {}
def log_interpretation(self, sequence, new_nonterminal, rationale):
"""Documents an interpretation decision"""
self.interpretation_log.append({
'sequence': sequence,
'new_nonterminal': new_nonterminal,
'rationale': rationale,
'timestamp': len(self.interpretation_log)
})
# Explicate the meaning of the sequence
if all(isinstance(s, str) and (s.startswith(('K', 'V'))) for s in sequence):
actions = [self._interpret_symbol(s) for s in sequence if isinstance(s, str)]
self.sequence_meaning_mapping[tuple(sequence)] = {
'meaning': ' → '.join(actions),
'type': self._classify_sequence(sequence)
}
def _interpret_symbol(self, symbol):
"""Returns the qualitative meaning of a terminal symbol"""
meanings = {
'KBG': 'Customer greeting',
'VBG': 'Salesperson greeting',
'KBBd': 'Customer need (concrete)',
'VBBd': 'Salesperson inquiry',
'KBA': 'Customer response',
'VBA': 'Salesperson reaction',
'KAE': 'Customer inquiry',
'VAE': 'Salesperson information',
'KAA': 'Customer completion',
'VAA': 'Salesperson completion',
'KAV': 'Customer farewell',
'VAV': 'Salesperson farewell'
}
return meanings.get(symbol, str(symbol))
def _classify_sequence(self, sequence):
"""Classifies the type of interaction sequence"""
seq_str = ' '.join([str(s) for s in sequence])
if 'KBBd' in seq_str and 'VBBd' in seq_str:
return 'Need clarification'
elif 'KAE' in seq_str or 'VAE' in seq_str:
return 'Information exchange'
elif 'KAA' in seq_str and 'VAA' in seq_str:
return 'Transaction completion'
else:
return 'Interaction sequence'
def print_methodological_summary(self):
"""Prints a methodological summary"""
print("\n" + "=" * 70)
print("METHODOLOGICAL REFLECTION")
print("=" * 70)
print("\nDocumented interpretation decisions:")
for log in self.interpretation_log:
print(f"\n[Interpretation {log['timestamp']+1}]")
seq_str = ' → '.join([str(s) for s in log['sequence']])
print(f" Sequence: {seq_str}")
print(f" → Nonterminal: {log['new_nonterminal']}")
print(f" Rationale: {log['rationale']}")
if tuple(log['sequence']) in self.sequence_meaning_mapping:
mapping = self.sequence_meaning_mapping[tuple(log['sequence'])]
print(f" Meaning: {mapping['meaning']}")
print(f" Sequence type: {mapping['type']}")
# ============================================================================
# 3. HIERARCHICAL GRAMMAR INDUCTION
# ============================================================================
class GrammarInducer:
"""
Induces a PCFG through hierarchical compression.
Nonterminals are understood as EXPLICIT INTERPRETIVE CATEGORIES.
"""
def __init__(self):
self.rules = {} # Nonterminal -> List of (production, probability)
self.rule_occurrences = {} # Count of rule applications
self.terminals = set()
self.nonterminals = set()
self.start_symbol = None
self.compression_history = []
self.reflection = MethodologicalReflection()
# For optimization phase
self.terminal_frequencies = None
self.generated_frequencies_history = []
def find_relevant_patterns(self, chains, min_length=2, max_length=4):
"""
Finds relevant repeated sequences.
Unlike pure compression, semantic relevance is prioritized here.
"""
sequence_counter = Counter()
for chain in chains:
for length in range(min_length, min(max_length, len(chain) + 1)):
for i in range(len(chain) - length + 1):
seq = tuple(chain[i:i+length])
# Evaluation criteria for semantic relevance:
score = 1.0
# Check for speaker change (only for terminal symbols)
has_speaker_change = False
for j in range(len(seq)-1):
if (isinstance(seq[j], str) and isinstance(seq[j+1], str) and
((seq[j].startswith('K') and seq[j+1].startswith('V')) or
(seq[j].startswith('V') and seq[j+1].startswith('K')))):
has_speaker_change = True
break
if has_speaker_change:
score *= 2.0
# Prefer patterns with closure character
has_closure = any(isinstance(s, str) and s.endswith('A') for s in seq)
if has_closure:
score *= 1.3
sequence_counter[seq] += score
# Filter sequences with at least 2 occurrences
relevant = {seq: count for seq, count in sequence_counter.items()
if count >= 2}
if not relevant:
return None
# Select the most relevant sequence
best_seq = max(relevant.items(), key=lambda x: x[1])[0]
return best_seq
def generate_interpretive_name(self, sequence):
"""
Generates an interpretively meaningful name for the nonterminal.
"""
# Determine the type of sequence based on terminal symbols
seq_str = ' '.join([str(s) for s in sequence])
if 'KBBd' in seq_str and 'VBBd' in seq_str:
typ = "NEED_CLARIFICATION"
elif ('VAA' in seq_str and 'KAA' in seq_str) or ('VAA' in seq_str and 'KAV' in seq_str):
typ = "PAYMENT_PROCESS"
elif 'KAE' in seq_str or 'VAE' in seq_str:
typ = "INFORMATION_EXCHANGE"
elif 'KBG' in seq_str and 'VBG' in seq_str:
typ = "GREETING"
elif 'VAV' in seq_str and 'KAV' in seq_str:
typ = "FAREWELL"
else:
typ = "SEQUENCE"
# Create a unique name
if all(isinstance(s, str) and len(s) <= 4 for s in sequence):
# Only terminal symbols
first = sequence[0] if sequence else ""
last = sequence[-1] if sequence else ""
return f"NT_{typ}_{first}_{last}"
else:
# Contains nonterminals already
return f"NT_{typ}_{len(sequence)}"
def _describe_sequence(self, sequence):
"""Generates a semantic description of the sequence"""
if len(sequence) == 2:
if all(isinstance(s, str) and len(s) <= 4 for s in sequence):
return f"{self.reflection._interpret_symbol(sequence[0])} → {self.reflection._interpret_symbol(sequence[1])}"
else:
return f"{sequence[0]} → {sequence[1]}"
else:
return f"Sequence with {len(sequence)} steps"
def compress_chains(self, chains, sequence, new_nonterminal):
"""
Compresses the chains by replacing the sequence.
"""
compressed_chains = []
seq_tuple = tuple(sequence)
seq_len = len(sequence)
for chain in chains:
new_chain = []
i = 0
while i < len(chain):
if i <= len(chain) - seq_len and tuple(chain[i:i+seq_len]) == seq_tuple:
new_chain.append(new_nonterminal)
i += seq_len
else:
new_chain.append(chain[i])
i += 1
compressed_chains.append(new_chain)
return compressed_chains
def induce_grammar(self, chains, max_iterations=15):
"""
Main method for grammar induction.
"""
current_chains = [list(chain) for chain in chains]
iteration = 0
print("\n" + "=" * 70)
print("HIERARCHICAL GRAMMAR INDUCTION")
print("=" * 70)
print("\nThe induction process is understood as EXPLICATION:")
print("- Each new nonterminal represents an INTERPRETIVE CATEGORY")
print("- The naming explicates the qualitative meaning")
print("- The process is intersubjectively TRACEABLE\n")
while iteration < max_iterations:
# Find relevant patterns
best_seq = self.find_relevant_patterns(current_chains)
if best_seq is None:
print(f"\nNo further relevant patterns after {iteration} iterations.")
break
# Generate interpretive name
new_nonterminal = self.generate_interpretive_name(best_seq)
description = self._describe_sequence(best_seq)
# Ensure uniqueness
base_name = new_nonterminal
counter = 1
while new_nonterminal in self.nonterminals:
new_nonterminal = f"{base_name}_{counter}"
counter += 1
# Document the interpretive decision
rationale = f"Recognized dialogue pattern: {description}"
self.reflection.log_interpretation(best_seq, new_nonterminal, rationale)
seq_str = ' → '.join([str(s) for s in best_seq])
print(f"\nIteration {iteration + 1}:")
print(f" Recognized pattern: {seq_str}")
print(f" Interpretation: {description}")
print(f" → New category: {new_nonterminal}")
# Store the rule (initially without probability)
self.rules[new_nonterminal] = [(list(best_seq), 1.0)] # Temporary probability
self.nonterminals.add(new_nonterminal)
# Compress chains
current_chains = self.compress_chains(current_chains, best_seq, new_nonterminal)
# Show example
example = ' → '.join([str(s) for s in current_chains[0][:8]])
print(f" Example (compressed): {example}...")
iteration += 1
# Check for complete compression
if all(len(chain) == 1 for chain in current_chains):
symbols = set(chain[0] for chain in current_chains)
if len(symbols) == 1:
self.start_symbol = list(symbols)[0]
print(f"\nINDUCTION COMPLETED: Start symbol = {self.start_symbol}")
break
# Terminals are the original symbols
all_symbols = set()
for chain in empirical_chains:
all_symbols.update(chain)
self.terminals = all_symbols
# Calculate probabilities
self._calculate_probabilities()
return current_chains
def _calculate_probabilities(self):
"""
Calculates probabilities for each production.
"""
# Count how often each nonterminal occurs in the original data
occurrence_count = defaultdict(Counter)
# For each chain in the original data
for chain in empirical_chains:
self._count_occurrences(chain, occurrence_count)
# Convert to probabilities
for nonterminal in self.rules:
if nonterminal in occurrence_count:
total = sum(occurrence_count[nonterminal].values())
if total > 0:
productions = []
for expansion, count in occurrence_count[nonterminal].items():
prob = count / total
# Ensure expansion is a list
if isinstance(expansion, tuple):
expansion = list(expansion)
productions.append((expansion, prob))
# Sort by probability
productions.sort(key=lambda x: x[1], reverse=True)
self.rules[nonterminal] = productions
def _count_occurrences(self, sequence, occurrence_count):
"""
Recursive helper function for counting occurrences.
"""
i = 0
while i < len(sequence):
symbol = sequence[i]
# If the symbol is a nonterminal
if symbol in self.rules:
# Find the matching expansion
for expansion, _ in self.rules[symbol]:
if isinstance(expansion, list):
exp_len = len(expansion)
if i + exp_len <= len(sequence) and sequence[i:i+exp_len] == expansion:
# Count this occurrence
occurrence_count[symbol][tuple(expansion)] += 1
# Continue counting recursively in the expansion
self._count_occurrences(expansion, occurrence_count)
i += exp_len
break
elif i + 1 <= len(sequence) and [sequence[i]] == expansion:
# Single element
occurrence_count[symbol][tuple(expansion)] += 1
i += 1
break
else:
i += 1
else:
i += 1
# ============================================================================
# 4. GENERATION WITH INTERPRETIVE FEEDBACK
# ============================================================================
class InterpretiveGenerator:
"""
Generates chains and documents their interpretive meaning.
"""
def __init__(self, grammar, terminals, start_symbol, reflection):
self.grammar = grammar
self.terminals = terminals
self.start_symbol = start_symbol
self.reflection = reflection
# Create production probabilities
self.production_probs = {}
for nt, prods in grammar.items():
if prods and len(prods) > 0:
symbols = []
probs = []
for prod, prob in prods:
if isinstance(prob, (int, float)):
symbols.append(prod)
probs.append(float(prob))
if symbols and probs:
# Normalize if necessary
total = sum(probs)
if total > 0 and abs(total - 1.0) > 0.001:
probs = [p/total for p in probs]
self.production_probs[nt] = (symbols, probs)
def generate_with_interpretation(self, max_depth=15):
"""
Generates a chain and documents the interpretation.
"""
if not self.start_symbol:
return [], []
interpretation = []
def expand(symbol, depth=0):
if depth >= max_depth:
return [str(symbol)]
if symbol in self.terminals:
interpretation.append(self.reflection._interpret_symbol(symbol))
return [str(symbol)]
if symbol not in self.production_probs:
return [str(symbol)]
symbols, probs = self.production_probs[symbol]
if not symbols:
return [str(symbol)]
try:
chosen_idx = np.random.choice(len(symbols), p=probs)
chosen = symbols[chosen_idx]
except:
# Fallback in case of errors
chosen = symbols[0]
# Document the expansion
seq_str = ' → '.join([str(s) for s in chosen])
interpretation.append(f"[Expansion of {symbol}: {seq_str}]")
result = []
for sym in chosen:
result.extend(expand(sym, depth + 1))
return result
chain = expand(self.start_symbol)
return chain, interpretation
# ============================================================================
# 5. VALIDATION IN THE CONTEXT OF XAI CRITERIA
# ============================================================================
class XAIValidator:
"""
Validates the induced grammar according to the XAI criteria:
- Meaningfulness
- Accuracy
- Knowledge Limits
"""
def __init__(self, grammar_inducer):
self.inducer = grammar_inducer
self.original_freq = self._compute_empirical_frequencies()
def _compute_empirical_frequencies(self):
"""Calculates the empirical frequencies of terminals"""
all_terminals = []
for chain in empirical_chains:
all_terminals.extend(chain)
freq = Counter(all_terminals)
total = len(all_terminals)
return {sym: count/total for sym, count in freq.items()}
def evaluate_meaningfulness(self):
"""
Evaluates the meaningfulness of the grammar.
"""
print("\n" + "=" * 70)
print("VALIDATION: MEANINGFULNESS (XAI Criterion 1)")
print("=" * 70)
# Check if all nonterminals have interpretable names
meaningful_count = 0
for nt in self.inducer.nonterminals:
if nt.startswith('NT_') and len(nt) > 3:
meaningful_count += 1
meaningful_ratio = meaningful_count / len(self.inducer.nonterminals) if self.inducer.nonterminals else 0
print(f"\nTotal nonterminals: {len(self.inducer.nonterminals)}")
print(f"Interpretably named: {meaningful_count} ({meaningful_ratio:.1%})")
# Documented interpretations
print(f"\nDocumented interpretation decisions: {len(self.inducer.reflection.interpretation_log)}")
# Example interpretations
if self.inducer.reflection.interpretation_log:
print("\nExample interpretations:")
for i, log in enumerate(self.inducer.reflection.interpretation_log[:3]):
seq_str = ' → '.join([str(s) for s in log['sequence']])
print(f" {i+1}. {seq_str} → {log['new_nonterminal']}")
print(f" Rationale: {log['rationale']}")
return meaningful_ratio
def evaluate_accuracy(self, n_generated=500):
"""
Evaluates the accuracy of the grammar.
"""
print("\n" + "=" * 70)
print("VALIDATION: ACCURACY (XAI Criterion 2)")
print("=" * 70)
generator = InterpretiveGenerator(
self.inducer.rules,
self.inducer.terminals,
self.inducer.start_symbol,
self.inducer.reflection
)
# Generate many chains
all_generated = []
for _ in range(n_generated):
chain, _ = generator.generate_with_interpretation()
all_generated.extend(chain)
# Calculate generated frequencies
gen_freq = Counter(all_generated)
total_gen = len(all_generated)
gen_dist = {sym: count/total_gen for sym, count in gen_freq.items() if total_gen > 0}
# Correlation calculation for common symbols
common_symbols = sorted(set(self.original_freq.keys()) & set(gen_dist.keys()))
if common_symbols and len(common_symbols) > 1:
orig_values = [self.original_freq[sym] for sym in common_symbols]
gen_values = [gen_dist[sym] for sym in common_symbols]
correlation, p_value = pearsonr(orig_values, gen_values)
print(f"\nCorrelation (r): {correlation:.4f}")
print(f"Significance (p): {p_value:.4f}")
print(f"Basis: {len(common_symbols)} common symbols")
# Detailed table
print("\nFrequency comparison (Top 8):")
table_data = []
for sym in common_symbols[:8]:
table_data.append([
sym,
f"{self.original_freq[sym]:.4f}",
f"{gen_dist[sym]:.4f}",
f"{abs(self.original_freq[sym] - gen_dist[sym]):.4f}"
])
print(tabulate(table_data,
headers=["Symbol", "Empirical", "Generated", "Difference"],
tablefmt="grid"))
return correlation, p_value
else:
print("Insufficient common symbols for correlation calculation")
return 0, 1
def evaluate_knowledge_limits(self):
"""
Documents the knowledge limits of the grammar.
"""
print("\n" + "=" * 70)
print("VALIDATION: KNOWLEDGE LIMITS (XAI Criterion 3)")
print("=" * 70)
print("\nThe grammar is an EXPLICATION, not a discovery:")
print(" • It is based on 8 transcripts of sales conversations")
print(" • The terminal symbols were obtained through qualitative interpretation")
print(" • The nonterminals represent INTERPRETIVE CATEGORIES")
print("\nLIMITS OF THE GRAMMAR:")
print(" • No generalization beyond the dataset")
print(" • No predictive capability for new contexts")
print(" • Dependent on the initial category formation")
print(" • Alternative interpretations are possible")
# Document uncovered patterns
observed_pairs = set()
for chain in empirical_chains:
for i in range(len(chain) - 1):
observed_pairs.add((chain[i], chain[i+1]))
print(f"\nCOVERED PATTERNS:")
print(f" • Observed transitions: {len(observed_pairs)}")
print(f" • Nonterminals captured in grammar: {len(self.inducer.nonterminals)}")
# ============================================================================
# 6. MAIN EXECUTION
# ============================================================================
def main():
"""
Main function with methodological framing.
"""
print("=" * 70)
print("ALGORITHMIC RECURSIVE SEQUENCE ANALYSIS 3.0")
print("HIERARCHICAL GRAMMAR INDUCTION")
print("=" * 70)
# 1. Induce grammar
inducer = GrammarInducer()
compressed_chains = inducer.induce_grammar(empirical_chains)
# 2. Methodological reflection
inducer.reflection.print_methodological_summary()
# 3. Display induced grammar
print("\n" + "=" * 70)
print("INDUCED GRAMMAR")
print("=" * 70)
print(f"\nTerminals ({len(inducer.terminals)}): {sorted(inducer.terminals)}")
print(f"Nonterminals ({len(inducer.nonterminals)}): {sorted(inducer.nonterminals)}")
if inducer.start_symbol:
print(f"Start symbol: {inducer.start_symbol}")
print("\nPRODUCTION RULES (with probabilities):")
for nonterminal in sorted(inducer.rules.keys()):
productions = inducer.rules[nonterminal]
if productions:
prod_strings = []
for prod, prob in productions:
# Ensure prod is a list
if isinstance(prod, tuple):
prod = list(prod)
prod_str = ' → '.join([str(s) for s in prod])
# Ensure prob is a float
prob_float = float(prob) if not isinstance(prob, (int, float)) else prob
prod_strings.append(f"{prod_str} [{prob_float:.3f}]")
print(f"\n{nonterminal} → {' | '.join(prod_strings)}")
# 4. Generate examples with interpretation
print("\n" + "=" * 70)
print("EXAMPLES WITH INTERPRETATION")
print("=" * 70)
generator = InterpretiveGenerator(
inducer.rules,
inducer.terminals,
inducer.start_symbol,
inducer.reflection
)
for i in range(3):
chain, interpretation = generator.generate_with_interpretation()
print(f"\nExample {i+1}:")
chain_str = ' → '.join([str(s) for s in chain[:10]])
print(f" Chain: {chain_str}" + ("..." if len(chain) > 10 else ""))
print(" Interpretation:")
for j, step in enumerate(interpretation[:5]):
print(f" {j+1}. {step}")
if len(interpretation) > 5:
print(" ...")
# 5. XAI validation
validator = XAIValidator(inducer)
validator.evaluate_meaningfulness()
validator.evaluate_accuracy(n_generated=500)
validator.evaluate_knowledge_limits()
# 6. Export grammar
print("\n" + "=" * 70)
print("EXPORT GRAMMAR")
print("=" * 70)
with open("induced_grammar_with_interpretation.txt", 'w', encoding='utf-8') as f:
f.write("# INDUCED PCFG WITH INTERPRETATION\n")
f.write("# =================================\n\n")
f.write(f"## DATA BASIS\n")
f.write(f"{len(empirical_chains)} transcripts of sales conversations\n\n")
f.write("## TERMINALS (qualitative categories)\n")
for sym in sorted(inducer.terminals):
f.write(f"{sym}: {inducer.reflection._interpret_symbol(sym)}\n")
f.write("\n## NONTERMINALS (interpretive categories)\n")
for log in inducer.reflection.interpretation_log:
seq_str = ' → '.join([str(s) for s in log['sequence']])
f.write(f"\n{log['new_nonterminal']}\n")
f.write(f" Pattern: {seq_str}\n")
mapping = inducer.reflection.sequence_meaning_mapping.get(tuple(log['sequence']), {})
if mapping:
f.write(f" Meaning: {mapping.get('meaning', '')}\n")
f.write(f" Rationale: {log['rationale']}\n")
f.write("\n## PRODUCTION RULES\n")
for nt in sorted(inducer.rules.keys()):
prods = inducer.rules[nt]
for prod, prob in prods:
if isinstance(prod, tuple):
prod = list(prod)
prod_str = ' '.join([str(s) for s in prod])
prob_float = float(prob) if not isinstance(prob, (int, float)) else prob
f.write(f"{nt} → {prod_str} [{prob_float:.3f}]\n")
print(f"\nGrammar exported as 'induced_grammar_with_interpretation.txt'")
print("\n" + "=" * 70)
print("ALGORITHMIC RECURSIVE SEQUENCE ANALYSIS COMPLETED")
print("=" * 70)
if __name__ == "__main__":
main()
\end{lstlisting}
\end{document}