Lalor and Guo measuring algorithmic interpretability

Measuring algorithmic interpretability:
A human-learning-based framework and
the corresponding cognitive complexity score John P. Lalor, Hong Guo IT,
Analytics, and Operations Department
Mendoza College of Business
University of Notre Dame, Notre Dame, IN 46556<EMAIL_ADDRESS><EMAIL_ADDRESS>
Algorithmic interpretability is necessary to build trust, ensure fairness, and
track accountability. However, there is no existing formal measurement method
for algorithmic interpretability. In this work, we build upon programming
language theory and cognitive load theory to develop a framework for measuring
algorithmic interpretability. The proposed measurement framework reflects the
process of a human learning an algorithm. We show that the measurement
framework and the resulting cognitive complexity score have the following
desirable properties – universality, computability, uniqueness, and
monotonicity. We illustrate the measurement framework through a toy example,
describe the framework and its conceptual underpinnings, and demonstrate the
benefits of the framework, in particular for managers considering tradeoffs
when selecting algorithms.

algorithmic interpretability, human learning, cognitive complexity,
programming language theory, cognitive load theory

##  1 Introduction

> If you can’t measure it, you can’t improve it.
>
> —Peter Drucker (apocryphal)

Algorithms built on artificial intelligence (AI) and machine learning
technologies are being deployed in a wide variety of areas such as healthcare,
criminal justice, and financial services (Lucas et al. 2013, Chouldechova
2017, De-Arteaga et al. 2019, McKinney et al. 2020, Strickland 2021). With
this widespread deployment has also come calls for these algorithms to be more
interpretable in order to build trust, ensure fairness, and track
accountability (Hardt et al. 2016, Xiao et al. 2018, Kearns and Roth 2019,
Mittelstadt et al. 2019, Zhang et al. 2020). Such calls have even risen to the
level of legislation, for example the European Union’s General Data Protection
Regulation (GDPR) requiring “meaningful information about the logic involved”
in algorithmic decision making.

Despite these concerns across a wide range of stakeholders including managers,
users, policymakers, learners, and educators, there is presently no formal
measurement method for algorithmic interpretability (Li et al. 2021).
Measurement “is the assignment of numbers to objects or events according to
rule” (Stevens 1958). Algorithmic interpretability refers to the
understandability and sensemaking for a particular human with respect to a
specific algorithm (Berente et al. 2021).111In the existing literature, the
concept of algorithmic interpretability is often intertwined with concepts
such as transparency and explainability. We refer readers to Berente et al.
(2021) for a detailed discussion of the concepts and their similarities and
differences. Interpretability is often assumed based on intuitive
understanding of algorithms or estimated based on model characteristics (e.g.,
tree depth or weight sparsity) or outputs of downstream user studies.222Some
researchers argue that inherently interpretable models are the way forward, as
interpretation methods for the output of so-called “black-box” models generate
interpretations that are not faithful to what the original model computes and
can potentially mislead (Lipton 2018, Rudin 2019). Even the GDPR regulations
do not specify the level of detail required to meet the standard of
“meaningful information” and do not account for different individuals’
expectations for the same algorithm (Goodman and Flaxman 2017). Without a
formal framework, we can’t measure, compare, or manage algorithmic
interpretability.

In this work we build upon programming language theory and cognitive load
theory to develop a framework for measuring algorithmic interpretability. The
proposed measurement framework reflects the process of a human learning an
algorithm. We show that the measurement framework and the resulting cognitive
complexity score have the following desirable properties – universality,
computability, uniqueness, and monotonicity. As our opening quote indicates,
having a framework for measuring interpretability sets a foundation for
improving algorithmic interpretability across algorithms.

Figure 1: Algorithmic interpretability: A new dimension of algorithm
performance

Measuring algorithmic interpretability bridges the gap between human and
machine evaluation (Figure 1). Computational complexity (such as runtime
complexity and space complexity) measure an algorithm’s mechanical, machine-
oriented nature.333Here, “machine-oriented” should not be confused with
“machine-dependent.” Computational complexity is not machine-dependent, i.e.,
it is the same for a state-of-the-art machine and an old computer.
Computational complexity is machine-oriented, measuring how difficult it is
for computers to run the algorithm.  Predictive algorithms are also measured
by their performance on specific tasks, e.g., accuracy or
precision/recall/F-score metrics. Cognitive complexity represents the
intrinsic, human-oriented difficulty of understanding an algorithm. When
choosing an algorithm for a task and group of users, tradeoffs among all
performance dimensions must be carefully evaluated. In this work (indicated by
the double-lined rectangle in Figure 1), we measure this as yet unexplored
dimension of algorithmic performance – cognitive complexity.

The rest of the paper is organized as follows. In Section 2, we describe
related work on interpretability. In Section 3, we discuss the necessary
theoretical background in programming language theory from computer science
and cognitive load theory from cognitive science. In Section 4, we walk
through a toy example to detail the specifics of our framework. In Section 5,
we describe the details of our framework. In Section 6, we discuss the
important properties of the framework. In Section 7, we show a detailed real-
world business example of the framework as applied to recommender systems,
which are widely used in a number of business contexts (e.g., Lee and
Hosanagar 2021). In Section 8, we conclude with a detailed discussion of our
contributions to research, including promising areas for future work (§8.1),
and contributions to practice for specific stakeholders such as managers,
users, policymakers, learners, and educators (§8.2). To offer a consolidated
point of reference for readers, in Appendix 9, we summarize the key concepts
from the theories we build upon (programming language theory and cognitive
load theory).

##  2 Related Work

In this section, we first discuss the prior research on algorithmic
interpretability broadly, then focus on the question of how algorithmic
interpretability is measured.

###  2.1 Algorithmic Interpretability

Algorithmic interpretability refers to the understandability and sensemaking
for a particular human with respect to a specific algorithm (Berente et al.
2021). Put another way, “for a system to be interpretable, it must produce
descriptions that are simple enough for a person to understand using a
vocabulary that is meaningful to the user” (Gilpin et al. 2018).444For a
discussion on how algorithmic interpretability relates to concepts such as
explainable AI (xAI) and algorithmic transparency, we refer the reader to
existing surveys and overviews on the topic (Doshi-Velez and Kim 2017, Adadi
and Berrada 2018, Lipton 2018, Murdoch et al. 2019).

During the development of new interpretable algorithms, there are three key
considerations concerning what a human is meant to interpret and how he or she
should do so. The first dimension involves that which is being interpreted:
the algorithm or the algorithm’s output. This dimension of interpretability
can be categorized into intrinsic interpretability or post-hoc
interpretability (Lipton 2018, Murdoch et al. 2019). The target for intrinsic
interpretability is the algorithm itself, while the target for post-hoc
interpretability is the output (e.g., a model prediction). Most existing
methods provide post-hoc interpretability (e.g., Abdul et al. 2018, Ross et
al. 2021).

The second dimension covers the scope of the interpretation, and can be
categorized into global interpretability versus local interpretability. Global
interpretability methods describe model behavior in the average case and
therefore cannot be example-specific (Lage et al. 2018). Local
interpretability methods allow for interpreting the outputs of a model for
specific inputs (Poursabzi-Sangdeh et al. 2021).

The last dimension involves the generality of the method. Universal methods
are applicable to all algorithms (e.g., Lage et al. 2018, provide a universal
framework for measurement, but it requires model-specific proxies for use.).
Model-specific methods only apply to specific algorithms, typically because of
the inputs required for calculation (e.g., linear model sparsity as a
quantification of interpretability, Abdul et al. 2020).

###  2.2 Measuring Algorithmic Interpretability

In recent years, there has been a swell of research on making algorithms more
interpretable. The vast majority of work covers designing “more interpretable”
algorithms (Doshi-Velez and Kim 2017, Adadi and Berrada 2018, Lipton 2018,
Murdoch et al. 2019). However, there is little consensus on how to measure
algorithmic interpretability.

Murdoch et al. (2019) propose five types of model-based interpretability
(sparsity, simulatability, modularity, domain-based feature engineering, and
model-based feature engineering) but do not include any information on how to
measure each type. Similarly, Axis 2 in the framework of Adadi and Berrada
(2018) covers “XAI Measurement” but it only considers the evaluation of output
explanations and not of the interpretability of the models themselves.555In
addition, works cited by Adadi and Berrada (2018) consider downstream
explanations, and do not include measurements of the algorithm.

There is presently no formal framework for the rigorous measurement of
algorithmic interpretability. The existing work either uses intuition-driven
proxies or user studies to quantify interpretability, but does not formally
measure the interpretability of an algorithm (see Table 1 for a summary of
related studies). Abdul et al. (2020) count the visual chunks in line chart
repesentations of models to estimate the visual load of processing the
explanation. Ross et al. (2021) operationalize understandability as the
ability for humans to reconstruct input images based on different
dimensionality reduction techniques. Lage et al. (2018) take an optimization
approach to include response time from user study outputs in an estimation
task for identifying an interpretable model. Poursabzi-Sangdeh et al. (2021)
conduct extensive user studies to assess how model changes affect how well a
human can predict a model’s output.

Table 1: Review of Existing Literature on Measuring Algorithmic Interpretability Paper |  Measurement |  |  |
---|---|---|---|---
Type |  Measure |  Intrinsic or post-hoc |  Universal or specific |
Lage et al. (2018) |  Reflective |  Simulatability speed |  Post-hoc |  Universal
Abdul et al. (2020) |  Reflective |  Simulatability speed |  Post-hoc |  Specific
Poursabzi-Sangdeh et al. (2021) |  Reflective |  Simulatability accuracy |  Intrinsic and Post-hoc |  Specific
Ross et al. (2021) |  Reflective |  Reconstruction accuracy |  Post-hoc |  Specific
This paper |  Formative |  Cognitive complexity |  Intrinsic |  Universal

Intrinsic interpretability is itself a latent construct. To measure it, we
rely on observable values. It is important to consider the relationship
between the observed values and the latent construct. If a change in the
latent variable is likely to change the measure, then the measure is
reflective. For example, replacing a decision tree with a neural network
presumably decreases the latent interpretability, which leads to changes in
downstream observed values (such as longer simulation speed times or lower
reported understanding). However, if a change in the measure causes changes in
the latent variable, then the measure is formative. Using a decision tree as
an example, if the measure of interpretability is tree depth, changing the
depth of the tree will change the latent interpretability. Most measures used
in xAI research are reflective (e.g., simulatability, output prediction,
accuracy, etc.). If you change the latent variable (intrinsic
interpretability), then that will affect the measures. Our cognitive
complexity, on the other hand, is a formative measure. As you modify an
algorithm to change its cognitive complexity score or change the user group,
this will affect the interpretability. In other words, our cognitive
complexity measure is determined by the algorithm and the user group involved.

At present, most work on measuring interpretability relies on user studies.
For a given algorithm, a user study is designed to measure some human-related
construct (e.g., simulation speed, reported ease of use, or human accuracy on
a downstream task). These results give insights into how users perceive
algorithms, or how algorithms affect user performance and behavior. This
approach has a number of benefits. As humans are central to the question of
algorithmic interpretability, it makes sense for human evaluation with user
studies to be a key consideration for system design and tracking improvements
in the field (Peffers et al. 2007). User studies where a system is evaluated
in the task it was designed for by the true end-users allow researchers to
ensure “that the system delivers on its intended task” (Doshi-Velez and Kim
2017). However, user studies also have several downsides. A salient downside
of user studies is the high cost of recruiting and engaging subjects. In
addition, such a data-driven approach in user studies cannot answer the
question of why one algorithm is more interpretable than another. What’s more,
user-studies are inherently “task-driven” evaluations (Doshi-Velez and Kim
2017).

On the other hand, a theory-driven approach can address these downsides.
First, a model of interpretability could answer the “why” question. Instead of
using humans to provide the measure (in the form of user study data), a
theory-driven approach seeks to model human behavior or other characteristics
(such as expertise). This type of theory-driven approach complements the
existing data-driven approach in user studies, and is the focus of our work.
Unlike the existing literature on algorithmic interpretability, we directly
model the human learning process. Our framework does not require user studies,
which is beneficial for two reasons. First, any algorithm and any user group
can be operationalized according to the framework, which gives it broader
applicability than work driven by specific user studies. Second, the framework
is automatically computable, making it more cost-effective than user studies.

##  3 Theoretical Background

Our framework for measuring algorithmic interpretability builds upon
programming language theory from computer science and cognitive load theory
from cognitive science.666We provide a table of relevant concepts and
descriptions in Appendix 9. In this section, we discuss the necessary
theoretical background before presenting a toy example to illustrate our
approach in Section 4 and eventually proposing our theoretical framework in
Section 5.

###  3.1 Programming Language Theory

We must have a universal representation of algorithms so that our framework
can present a consistent representation to end users for interpretation. For
this we turn to control flow graphs. The control flow graph (CFG) is a common
tool in computer science. CFGs are visual representations of computer program
executions (Allen 1970, McCabe 1976).777A control flow graph is a “directed
graph in which the nodes represent basic blocks, sequences of program
instructions having one entry point (the first instruction executed) and one
exit point (the last instruction executed), and the edges represent control
flow paths” (Allen 1970). CFGs are used to visualize the possible paths
through a program’s execution for tasks such as code debugging (Allen and
Cocke 1976), compiler optimization (Shivers 1991), and program tracing for
automatic differentiation (Baydin et al. 2017).

CFGs can include a variety of control structures as nodes in the graph, such
as sequences, goto statements, and others. For our purposes we would like to
restrict the possible types of nodes in the graph to avoid overwhelming the
users. The structured program theorem from computer science states that every
algorithm can be represented as a control flow graph built with three types of
control structures: sequences, where one block follows another; selections,
where a boolean expression determines the subsequent sequence; and iterations,
where a sequence is repeated while some boolean holds true (Böhm and Jacopini
1966). The proof shows that complex control structures (e.g., recursion) can
be decomposed to a combination of the above basic control structures.
Therefore, any algorithm for solving a computable function, including complex
machine learning models, recommender systems, and other algorithms involved in
business decisions, can be represented as a control flow graph.

Algorithms for solving problems have existed for millenia (Barbin et al. 2012,
Cooke 2011), and are typically (informally) defined as “procedure[s] for
solving a mathematical problem$\dots$in a finite number of steps that
frequently involves repetition of an operation.”888https://www.merriam-
webster.com/dictionary/algorithm A more technical definition of an algorithm
is any computable function, as per the Church-Turing thesis (Church 1936,
Turing 1936). These computable functions are functions that, given any input,
halt eventually and output the expected function output for the given input
(Turing 1936, Agarwal et al. 2020). This definition encompasses any algorithm
that would be developed and applied in a production environment and is,
therefore, suitable for our purposes.

The structured program theorem and the Church-Turing thesis give us a
foundation for our framework. They provide two desirable properties (namely,
universality and computability) that we can leverage for our construction of a
measurement for algorithmic interpretability. We have a precise definition of
algorithms that applies to their standard use-case, and we have a
representation (CFGs) that can apply to any algorithm that might be used in
practice, from regression models to neural networks and complex pipelines.

###  3.2 Cognitive Load Theory

Cognitive load theory (CLT), an instructional design theory in cognitive
science, builds upon the characteristics of human cognitive architecture and
develops guidelines for instructional design (Sweller 1994). Human cognitive
architecture involves limited-capacity working memory and effectively
unlimited long-term memory (Baddeley 1983, Sweller 2003, Cowan 2005).

Working memory can only process a few elements at any time and may become
overloaded when more than a few elements are processed simultaneously, leading
to cognitive overflow. In contrast, long-term memory can hold knowledge in the
form of schemas, which are knowledge structures used to store and organize
information (Paas et al. 2003). The human schematic knowledge base in long-
term memory represents the major critical factor influencing how we learn new
information (Kalyuga 2014). A schema, regardless of its complexity, is
processed as a single entity in working memory. Thanks to schema construction,
although the number of elements that can be processed in working memory is
limited, the amount of information that can be processed in working memory is
unlimited. For example, simple operations used in algorithms such as addition
and multiplication are constructed schemas available in long-term memory for
most users, which require minimal conscious effort. Furthermore, lower-level
schemas can be incorporated into higher-level schemas and consequently further
reduce working memory load. For example, users with high algorithmic literacy
may have the dot product schema, which is a higher-level schema compared to
the addition schema and the multiplication schema. Users with low algorithmic
literacy may not have acquired the dot product schema yet and, thus, have to
rely on addition and multiplication (lower-level schemas) to learn dot
product. When trying to make sense of new information (e.g., a new algorithm),
users typically resort to the highest-order schemas available to reduce
working memory load (Sweller et al. 1998).

According to CLT, there are three sources of cognitive load: extraneous,
germane, and intrinsic cognitive load (Sweller 1994, Paas et al. 2003).
Extraneous cognitive load refers to the unnecessary demand on working memory
capacity often caused by ineffective instructional procedures. In contrast,
germane cognitive load refers to the necessary demand on working memory
capacity. CLT further provides instructional design guidelines to eliminate
extraneous cognitive load. The focus of this paper is intrinsic cognitive
load, i.e., the demand on working memory capacity that is intrinsic to the
material being learned and determined by its information structure.

In this paper, we measure intrinsic algorithmic interpretability by measuring
the intrinsic cognitive load of an algorithm, i.e., how hard it is for users
to understand the algorithm. According to CLT, intrinsic cognitive load is
determined by both the nature of the materials being learned and the learner’s
expertise. Furthermore, intrinsic cognitive load can be characterized in terms
of element interactivity (van Merrienboer and Sweller 2005). Intrinsic
cognitive load is higher if the number of interacting elements is higher
because more elements have to be processed simultaneously to understand the
material fully.999Throughout the rest of this paper, we will refer to
intrinsic cognitive load as simply “cognitive load.” Understanding a new
algorithm is a complex task with high element interactivity. Due to working
memory limitations, users cannot assimilate all of the elements if all of the
interacting elements are presented simultaneously. Instead, users rely on
gradually building increasingly complex knowledge structures in long-term
memory to manage cognitive load.

Our framework considers the three determinants of intrinsic load including
number of elements, interactivity of these elements, and prior knowledge of
the learner. Since we do not explicitly model the learning process of users,
we do not consider the determinants for germane and extraneous loads, such as
instructional approach and learning style.

##  4 Illustrative Toy Example: Revenue Calculation

Before formally presenting our theoretical framework of measuring algorithmic
interpretability, in this section we discuss a simple toy example of revenue
calculation to illustrate the main ideas in the framework. Given the price and
quantity sold for a list of items, we would like to compute the total revenue
of these items. Specifically, we consider three tasks in this example. In Task
1, as indicated in Figure 2, the total revenue of all items in the list is
computed. In Task 2, as indicated in Figure 3, the total revenue of items with
a price higher than $\$10$ is computed. In Task 3, as indicated in Figure 4,
the total revenue of items with a price higher than $\$10$ and a quantity sold
higher than $100$ is computed. Next, we elaborate on the detailed process of
deriving the cognitive complexity scores in these three tasks.

Task 1: Total revenue of all items. Figure 2 shows the control flow graph of
Task 1, which starts with initializing a variable and then iteratively adding
to the variable the product of price and quantity for each item. Figures 2 and
2 show the operation context graphs of Task 1 for users with low and high
algorithmic literacy respectively. In Task 1, addition and multiplication are
relevant schemas available for users with low algorithmic literacy and thus
are the appropriate abstraction level in Figure 2. For users with high
algorithmic literacy, they have dot product (a higher-level schema) available
in their schematic knowledge base. Thus, dot product is the appropriate
abstraction level in Figure 2.

Figure 2(): Task 1 control flow graph

Figure 2(): Task 1 operation context graph for users
with low algorithmic literacy

Figure 2(): Task 1 operation context graph for users
with high algorithmic literacy

Figure 2: Task 1: Total revenue of all items

It is important to note that the variable initialization step and the while
loop in the control flow graph do not show up in the operation context graph
because, unlike computers, humans process information through concepts such as
addition and multiplication, instead of going through a loop.101010For
example, 1000 additional iterations would add more computational complexity
for computers. However, the cognitive complexity for humans remains the same.
Additionally, since the concept of all (i.e., all items in the list) is an
automated schema for the users, there is no specific context for the user to
process in Task 1. Therefore, the number of interacting elements (the key
determinant of cognitive load) is 1 for the multiplication operation (the
focal operation itself only) and 2 for the addition operation (the parent
operation and the focal operation). Since the increase in the number of
interacting elements results in a nonlinear increase in the cognitive load
imposed on working memory, we use an exponential function to capture such
nonlinear growth patterns.111111Our framework can be extended/adapted to other
nonlinear functional forms. Consequently, the resulting cognitive complexity
score is $e+e^{2}$ for users with lower algorithmic literacy and $e$ for users
with higher algorithmic literacy.

Task 2: Total revenue of items with price higher than $10. As shown in Figure
3, different from Task 1, the selection criterion of items with a price higher
than $\$10$ is a context-specific condition in Task 2. This additional
condition requires extra effort for users to process. Such additional
conditions are extracted as contexts in our framework (indicated as rectangles
in operation-context graphs), which also impose extra cognitive load and,
thus, add to the final cognitive complexity score. Specifically, the resulting
cognitive complexity score is $e^{2}+e^{3}$ for users with lower algorithmic
literacy (Figure 3) and $e^{2}$ for users with higher algorithmic literacy
(Figure 3).

Figure 3(): Task 2 control flow graph

Figure 3(): Task 2 operation context graph for users
with low algorithmic literacy

Figure 3(): Task 2 operation context graph for users
with high algorithmic literacy

Figure 3: Task 2: Total revenue of items with price higher than $10

Task 3: Total revenue of items with price higher than $10 and quantity sold
higher than 100. In Task 3, as shown in Figure 4, we have an additional piece
of contextual information to consider. Two criteria must be met instead of
one. This second criterion further increases cognitive load and the cognitive
complexity score, which is indicated in Figures 4 and 4 by adding another
context rectangle to the graphs. Specifically, the resulting cognitive
complexity score is $e^{3}+e^{4}$ for users with lower algorithmic literacy
(Figure 4) and $e^{3}$ for users with higher algorithmic literacy (Figure 4).

Figure 4(): Task 3 control flow graph

Figure 4(): Task 3 operation context graph for users
with low algorithmic literacy

Figure 4(): Task 3 operation context graph for users
with high algorithmic literacy

Figure 4: Task 3: Total revenue of items with price higher than $10 and
quantity sold higher than 100

##  5 A Framework for Measuring Intrinsic Algorithmic Interpretability

In this section, we propose a human-learning-oriented theoretical framework
for measuring algorithmic interpretability (Figure 5). Our framework consists
of four major components: representing algorithms as control flow graphs
(§5.2); characterizing user expertise with schemas (§5.3); constructing the
operation context graphs (§5.4); and scoring for cognitive complexity (§5.5).
Before we discuss these components in detail, we first introduce the necessary
notation for consistent exposition of the framework.

Figure 5: Research framework of measuring algorithmic interpretability

###  5.1 Notation

For a given algorithm $a$ and a user group $u$, we aim to measure the
interpretability of the algorithm to the user group through measuring the
cognitive complexity for the user group to learn the algorithm. For a specific
algorithm $a$, we use $CFG(a)$ to represent the control flow graph of $a$. Let
$U$ be the set of user groups, where user group $u\in U$ is defined as the set
of users that share the same level of algorithmic literacy (i.e., the same set
of available schemas). For a specific user group $u$, we use $S_{u}$ to
represent the schematic knowledge base of $u$. For a given algorithm $a$ and a
user group $u$, we use $OCG(a,u)$ to represent the operation context graph of
$a$ appropriate for user group $u$.

###  5.2 Representing Algorithms as Control Flow Graphs

Based on programming language theory, a given algorithm can be represented by
a control flow graph (§3.1). And by the structured program theorem, we know
that these graphs only include a small set of flow types; namely, sequences,
selections, and iterations. This result allows for a universal, graphical
representation of algorithms that is simple in terms of allowable
components.121212Certain algorithms may have large, complex control flow
graphs, but they can still be represented as such. By restricting acceptable
components, we can standardize how the graphs are generated, making downstream
analyses consistent.

###  5.3 Characterizing User Expertise with Schemas

Different users have different levels of expertise for understanding
algorithms. User expertise needs to be abstracted so that the measurement can
be applied according to some pre-set criteria. Consider the logistic
regression classifier as an example. A machine learning researcher can
abstract more concepts related to the classifier to higher-order
representations than a legislator because the researcher has higher expertise
than the legislator.131313Expertise can take many forms. Later we explicitly
discuss technical knowledge such as algorithmic literacy, but other forms of
expertise are relevant as well and are context- and algorithm-dependent. Both
are interested in the interpretability of the model for different reasons
(e.g., research, policy).

To characterize expertise, we resort to schemas from cognitive load theory.
When an individual learns a new concept, that concept is internalized in long-
term memory as a schema, which can be recalled and applied when learning new,
complex concepts (Paas et al. 2003). A schema, regardless of its complexity,
is processed as a single entity in working memory. Thanks to schema
construction, although the number of elements that can be processed in working
memory is limited,141414According to Miller’s law, the “magic number” of
objects one can hold in working memory is $7\pm 2$ (Miller 1994); the amount
of information that a human can process in working memory is unlimited.
through (often extensive) practice, humans can learn and understand more
complex concepts by building on existing internalized schemas. In the context
of algorithms, every block in a control flow graph can be learned and
internalized as a schema.

A user group’s internalized schemas can be summarized in their schematic
knowledge base. The schematic knowledge base then determines if any
transformations have to be made to the control flow graph. For example, if a
user has a schema for taking an average, a basic block for calculating an
average can be abstracted away as a single operation (i.e., TakeAverage) and
will be processed as a single entity in working memory. However, if the user
does not have a schema for taking an average, the operation would be
decomposed into its parts. Each part would be considered a separate operation:
one for the addition schema, connected to one for the division schema,
resulting in a larger graph. The schematic knowledge base impacts the level of
abstraction involved in the transformation from control flow graph to
operation context graph.

###  5.4 Construction of Operation Context Graphs

With the necessary pieces in place, we now describe the process of
transforming control flow graphs to account for human expertise and cognitive
load restrictions. Control flow graphs provide a consistent, universal
representation of algorithms where subgraphs in a user’s internalized schemas
in long-term memory can be abstracted away and replaced with a single
operation node in the operation context graph.

The structured program theorem allows for sequences, selections, and
iterations as control structures. Selections are involved in extracting
contexts; they involve the evaluation of boolean conditions to determine which
block to execute next. The blocks can be transformed into operations according
to acquired schemas. Once the appropriate operations are identified, the
additional cognitive load of tracking the boolean condition is represented by
context. Iterations over a full list do not affect context. However, if there
are conditionals embedded in the list (e.g., only certain elements), then that
selection is taken into account when extracting context.

Operations and contexts give us the framework’s building blocks. To generate a
graph appropriate for a given user level, we start at the fully decomposed
level, where it is assumed that the entire algorithm has been decomposed
according to the structured program theorem so that only the most basic
operations are included in the graph. Each subgraph is a possible
decomposition of an internalized schema in the user’s schematic knowledge
base. If so, that subgraph can be abstracted away and replaced in the graph by
the higher-level schema. The process continues until each block in the graph
is a schema in long-term memory, and no subgraphs are decompositions of
higher-level internalized schemas; then any selections are accounted for with
contexts. This process generates a concrete, visual representation of an
appropriate algorithm, given the schemas that a user has internalized in long-
term memory. It also takes into account the cognitive costs of tracking
contexts.

For a fully decomposed control flow graph representation of an algorithm and a
data table of the schematic knowledge base, an appropriate graph can be
constructed by abstracting subsections of the graph based on a user group’s
schematic knowledge base until each block is an operation in the schema set,
and each selection has been extracted into context.

###  5.5 Cognitive Complexity Scoring

We have shown that it is possible to generate a universal, human-oriented
representation of any algorithm. We next address the question of quantifying
the interpretability of the operation context graphs for measuring algorithmic
interpretability. Understanding a new algorithm is a complex task with high
element interactivity. Intrinsic cognitive load (hereafter “cognitive load”)
is higher if the number of interacting elements is higher because more
elements have to be processed simultaneously to understand the material fully.
Due to working memory limitations, users first learn isolated elements with a
partial understanding of the material and then learn interacting elements to
understand the material fully (van Merrienboer and Sweller 2005).

Based on the operation context graph, the cognitive complexity score for the
algorithm can be computed as:

$\displaystyle CC(a,u)$ $\displaystyle=\sum_{n\in OCG(a,u)}e^{CL(n)}$
$\displaystyle CL(n)$ $\displaystyle=C(n)+P(n)+1$

Here, $CC(a,u)$ is the cognitive complexity score of algorithm $a$’s
representation appropriate for user group $u$. $C(n)$ is the contextual state
of node $n$, $P(n)$ is the number of parent nodes for $n$, and $1$ is the
operational cost of the node itself. $CL(n)$ is the congnitive load of node
$n$, which tells us how many interacting elements must be considered at one
time in working memory for a given operation. The cognitive complexity
associated with increasing interacting elements is exponential, which can be
extended/adapted to other nonlinear functional forms. For an algorithm, the
cognitive complexity is then the sum of the cognitive complexity scores of all
operations in the graph.

For an algorithm and a group of users, the cognitive complexity score is an
inverse measure of interpretability. The higher the score, the more difficult
it is for users to interpret the algorithm. Cognitive complexity captures two
critical elements of intrinsic interpretability: algorithm complexity and
prior human knowledge. If someone wants to understand a particular algorithm,
they cannot simply take it all in at once. An algorithm consists of many
steps, each of which must be processed to go from input to output. Each
operation involves interacting elements of parent nodes and contexts, which
affect the cost of processing the node in working memory. In addition, a block
in an algorithm can only be understood if the user has an internalized schema
for it. If not, the block must be decomposed until the blocks are part of the
user’s schemas in long-term memory.

In Section 6, we will investigate the properties of the measurement framework
and their implications. In Section 7, we will discuss a real-life business
example with recommender system algorithms (Adomavicius and Tuzhilin 2005,
2011) as an application of the proposed measurement framework.

##  6 Framework Properties and Implications

The measurement framework and the corresponding cognitive complexity score
have four desirable properties: universality, computability, uniqueness, and
monotonicity. Two properties (universality and computability) follow from our
theoretical grounding, while two (uniqueness and montonicity) are new results
from our formulation. Proofs for all four properties are provided in Appendix
10.

######  Property 1 (Universality)

For any algorithm $a$ and user group $u$, the proposed measurement framework
is applicable to the $(a,u)$ pair.

######  Property 2 (Computability)

For any algorithm $a$ and user group $u$, the proposed measurement framework
is machine-computable.

######  Property 3 (Uniqueness)

For a given algorithm $a$ and a given user group $u$, the proposed measurement
framework generates a unique cognitive complexity score $CC(a,u)$.

######  Property 4 (Monotonicity)

For a given algorithm $a$, and two user groups $u_{1}$ and $u_{2}$, if user
group $u_{1}$ has lower algorithmic literacy than user group $u_{2}$, then the
cognitive complexity score is higher for $u_{1}$ than $u_{2}$, (i.e.,
$\text{if }S_{u_{1}}\subset S_{u_{2}},\text{then }CC(a,u_{1})\geq
CC(a,u_{2}))$.

With these properties, our framework can be used as a general measure of the
cognitive complexity of algorithms. These properties reduce ambiguity and
enforce consistency in how algorithms are represented, transformed, and
scored.

The framework is universal and can be applied to any algorithm. For any
algorithm, a user either does or does not understand each “step.” The steps
are themselves algorithms that can be decomposed into step-by-step procedures.
This universality applies to simple algorithms such as those for taking an
average and algorithms for training and deploying complex neural network
models.

Because generating the operation context graph is computable, the process of
creating an operation-context graph and generating a cognitive complexity
score can be automated. This automation is much less costly than user studies.
Cognitive complexity scores can be automatically generated for a large number
of algorithms so that they can be compared simultaneously without the need for
large amounts of human response data.

For a given algorithm and user group pairing, there is precisely one way to
generate a representation. Only certain operations are available to the user
at a certain level of expertise in a schematic knowledge base. Therefore, all
of the individual components in the operation context graph are fixed. For the
same reason, the cognitive complexity score is also unique for the algorithm
and user level. This gives consistency to the framework.

Monotonicity is an important measurement property for ordinal comparisons
(Freeman 1986). In particular, when measuring a latent construct via observed
data (in this case, algorithms and schemas are observed, and cognitive
complexity is latent), monotonicity ensures that as one observed trait
changes, the latent trait changes in a consistent direction. For a given
algorithm, it should always be the case that a group with more relevant
expertise can more readily understand and interpret a particular algorithm.

##  7 Real-life Business Example: Recommender Systems

To illustrate the framework, we walk through an example using two algorithms
from Recommender Systems (RecSys, Adomavicius and Tuzhilin 2005, 2011,
Ekstrand et al. 2011, Kluver et al. 2018, Lee and Hosanagar 2021). RecSys
models have seen wide adoption in recommending items to shoppers, movies to
viewers, and songs to listeners, among many other use cases. We follow the
steps outlined in our framework (Figure 5) to go from problem formulation
through to cognitive complexity scores for each algorithm under consideration.

###  7.1 Problem Formulation

For a set of users $U$, a set of items $I$, and a (potentially sparse) matrix
of user-item ratings $R$, a given user (e.g., user $u$ or $v$) and a given
item (e.g., item $i$ or $j$), the goal is to predict a rating score for a
specific user to a specific item:

$\hat{S}_{u,i}=RecSys(R,u,i)$ (1)

where $RecSys$ is an algorithm for calculating the predicted rating of $u$ for
$i$. Estimated scores can inform item-ranking decisions, e.g., which products
or movies to display to the user.

###  7.2 Algorithm Selection

We consider two standard algorithms for RecSys tasks: the user-item bias (or
personalized mean) algorithm (UIB) and the user-user $k$-nearest neighbors
(KNN) algorithm (Ekstrand et al. 2011, Kluver et al. 2018). It is commonly
accepted that the user item bias algorithm is “more interpretable” than the
KNN algorithm. Our goal is to validate this claim with our framework.

UIB is a common baseline RecSys model due to its simplicity and is often used
for setting a performance lower bound (Kluver et al. 2018). The predicted
rating for a particular user and item is the sum of a global average rating,
an item bias, and a user bias:

$\displaystyle\mu$ $\displaystyle=\frac{\sum_{r_{ui}\in R}r_{ui}}{|R|}$ (2)
$\displaystyle b_{i}$ $\displaystyle=\frac{\sum_{u\in
U_{i}}(r_{ui}-\mu)}{|U_{i}|}$ (3) $\displaystyle b_{u}$
$\displaystyle=\frac{\sum_{i\in I_{u}}(r_{ui}-b_{i}-\mu)}{|I_{u}|}$ (4)
$\displaystyle\hat{S}_{u,i}$ $\displaystyle=\mu+b_{i}+b_{u}$ (5)

For KNN, user $u$’s rating for item $i$ is estimated as the weighted average
of $u$’s $k$-most similar users’ (neighbors’) ratings for $i$, according to
some pre-defined similarity metric. The critical component to KNN is
identifying neighbors for some user $u$. For our example, we use Pearson’s $r$
as the similarity metric (Equation 7, Herlocker et al. 2002, Kluver et al.
2018). After calculating and sorting similarity scores for all possible $v$’s,
the top-$k$ are selected, and the predicted score is the weighted average of
the neighbors’ scores for item $i$. Weights are based on the neighbors’
similarity to $u$, so more similar users will have a more significant
influence on the predicted rating (Equation 9).

$\displaystyle\mu_{u}$ $\displaystyle=\frac{\sum_{r_{ui}\in
R_{u}}r_{ui}}{|R_{u}|}$ (6) $\displaystyle sim(u,v)$
$\displaystyle=\frac{\sum_{i}(r_{ui}-\mu_{u})(r_{vi}-\mu_{v})}{\sqrt{\sum_{i}(r_{ui}-\mu_{u})^{2}}\times\sqrt{\sum_{i}(r_{vi}-\mu_{v})^{2}}}$
(7) $\displaystyle N_{u}$ $\displaystyle=\\{v_{i}\in V_{sorted}|1\leq i\leq
k\\}$ (8) $\displaystyle\hat{S}_{u,i}$ $\displaystyle=\frac{\sum_{v\in
N_{u}}sim(u,v)\times r_{vi}}{\sum_{v\in N_{u}}|sim(u,v)|}$ (9)

Certain operations can be combined to present an appropriate representation
for a high algorithmic literacy user. Here we can treat $u$’s and $v$’s
ratings for items that they have both rated as vectors ($\mathbf{r}_{u}$ and
$\mathbf{r}_{v}$). $sim(u,v)$ can be re-written as the dot product of $u$’s
and $v$’s adjusted ratings vectors divided by the product of the L2-norms of
$u$’s and $v$’s adjusted ratings vectors (Equation 12). For both algorithms,
there are extensions and modifications for improving performance (e.g., the
selection of similarity score for KNN). In our framework, these are simply
additional operations that can be added to the graph for each algorithm,
affecting the cognitive complexity score.

$\displaystyle\mu_{u}$ $\displaystyle=\frac{\sum_{r_{ui}\in
R_{u}}r_{ui}}{|R_{u}|}$ (10) $\displaystyle\tilde{\mathbf{r}}_{u}$
$\displaystyle=\mathbf{r}_{u}-\mu_{u}\mathbf{I}$ (11) $\displaystyle sim(u,v)$
$\displaystyle=\frac{\tilde{\mathbf{r}}_{u}\cdot\tilde{\mathbf{r}}_{v}}{||\tilde{\mathbf{r}}_{u}||_{2}\times||\tilde{\mathbf{r}}_{v}||_{2}}$
(12) $\displaystyle N_{u}$ $\displaystyle=\\{v_{i}\in V_{sorted}|1\leq i\leq
k\\}$ (13) $\displaystyle\hat{S}_{u,i}$ $\displaystyle=\frac{\sum_{v\in
N_{u}}sim(u,v)\times r_{vi}}{\sum_{v\in N_{u}}|sim(u,v)|}$ (14)

###  7.3 Capturing User Expertise with Schemas

Building schematic knowledge bases for users requires making certain
assumptions about what operations are internalized as schemas in long-term
memory. For this example we consider a relatively coarse delineation of user
expertise: low and high expertise levels in terms of users’ algorithmic
literacy. We set these two algorithmic-literacy levels using testing
information for a U.S. high school equivalency examination
(HiSET),151515https://hiset.ets.org/about/content which does not include
vector and matrix multiplication, and the GRE mathematics subject test used in
graduate school
admissions,161616https://www.ets.org/gre/subject/about/content/mathematics/
which does. We can assume that vector and matrix multiplication operations,
which are relevant for our analyses, are not part of the expected schemas of
low expertise individuals, but are part of the expected schemas of high
expertise individuals.

###  7.4 Incorporating Schemas to a Control Flow Graph to Generate an
Operation Context Graph

Figures 6 and 7 show the operation context graphs for the two algorithms. The
operation context graph for UIB is appropriate for both high and low skill
users based on our schematic knowledge base (Figure 6). This algorithm is
simpler than the KNN algorithm, therefore it is possible to construct a clear
representation for both high and low algorithmic literacy users using high-
school level mathematical operations.

Legend for Figure 6
---
| Node | Description
---|---
A |  Calculate average: $b_{i}$
B |  Calculate average: $b_{u}$
C |  Calculate global average: $\mu$
D |  Subtract $\mu$ and $b_{i}$ from user ratings
E |  Subtract $\mu$ from item ratings
F | Sum global average, user bias, and
| item bias values

Figure 6: Operation context graph of the user-item bias algorithm for users at
two algorithmic literacy levels

For KNN, the representation for low algorithmic literacy users is complex
(Figure 7). Incorporating the vector and matrix multiplication abstractions
for high algorithmic literacy users allows for a more interpretable graph.
However, these schemas are not available to the low algorithmic literacy
users, who must instead use the decomposed graph to understand the algorithm.

Context is key to our framework as it marks selections and iterations where
additional information must be dealt with. In the mathematical formulation,
context is implicitly defined according to notation. For example, calculating
item bias in UIB requires subtracting the global average from each rating in
$U_{i}$ (Equation 3). In the graphical representation context is explicit. A
rectangle surrounds nodes that share context. For UIB there are two local
contexts to consider: calculating item bias $b_{i}$ by iterating over all
users who have rated item $i$ and calculating user bias $b_{u}$ by iterating
over all items rated by user $u$. For KNN there are four contexts for
iterations involving different subsets of data involved in certain operations.

Figure 7(): Operation context graph of user-user $k$-nearest neighbors
algorithm for users with high algorithmic literacy

Figure 7(): Operation context graph of user-user $k$-nearest neighbors
algorithm for users with low algorithmic literacy

Legend for Figure 7 and Figure 7
---
| Node |  Description |  Algorithmic Literacy Level
---|---|---
A |  Calculate the dot product of the two adjusted ratings vectors | High
B |  Calculate the L2 norm of $u$’s adjusted ratings | High
C |  Calculate the L2 norm of $v$’s adjusted ratings | High
D |  Calculate the weighted average of the neighbors’ ratings for $i$, using the similarity scores as the weights | Low
E |  Calculate $u$’s average rating | Low
F |  Calculate $v$’s average rating | Low
G |  Divide the dot product value by the product of L2 norms | High
H |  Divide the numerator by the denominator for similarity score | Low
I |  Multiply the L2 norm values together | High
J |  Multiply the square rooted values together | Low
Node |  Description |  Algorithmic Literacy Level
---|---|---
K |  Multiply $u$’s and $v$’s adjusted ratings together for each item | Low
L |  Select the top-$k$ users based on similarity as $u$’s neighbors | Low
M |  Sort the similarity scores for all users | Low
N |  Square root $u$’s sum | Low
O |  Square root $v$’s sum | Low
P |  Square $u$’s adjusted ratings | Low
Q |  Square $v$’s adjusted ratings | Low
R |  Subtract $u$’s average rating from $u$’s rating for each item | Low
S |  Subtract $v$’s average rating from $v$’s rating for each item | Low
T |  Sum the products of adjusted ratings | Low
U |  Sum $u$’s squared adjusted ratings | Low
V |  Sum $v$’s squared adjusted ratings | Low

Figure 7: Operation context graph of the user-user $k$-nearest neighbors
algorithm for users at two levels

After selections have been replaced with contexts, the operation context graph
is complete. From here cognitive complexity can be calculated (§5.5). The
levels of complexity in the graphs are reflected in the cognitive complexity
scores (Table 2).

###  7.5 Using Cognitive Costs to Derive a Cognitive Complexity Score

To empirically assess the tradeoffs of cognitive complexity and other
performance metrics we ran both RecSys algorithms on the MovieLens 100K data
set (Harper and Konstan 2015). Table 2 includes cognitive complexity scores as
well as computational complexity and predictive performance metrics. Table 2
confirms what is anecdotally evident: the user-item bias algorithm is more
interpretable (i.e., lower score) than the user-user KNN algorithm; also, a
given algorithm is more interpretable (lower score) for high algorithmic
literacy users than for low algorithmic literacy users. None of the other
metrics consider both the algorithm and the user as part of the scoring
process.

Table 2: Cognitive complexity scores as compared to computational complexity and performance metrics. Metric |  user-item bias |  user-user $k$-nearest neighbors
---|---|---
Cognitive Complexity (Low Expertise) | $2e^{4}+3e^{3}+e=172.17$ | $2e^{4}+11e^{3}+4e^{2}=359.69$
Cognitive Complexity (High Expertise) | $2e^{4}+3e^{3}+e=172.17$ | $2e^{4}+6e^{3}+4e^{2}=259.27$
Runtime Complexity, Actual (Upper Bound) |  $2,700$ ($O(n+d))$ |  $1,705,492$ ($O(nd+n\log n)$)
Space Complexity, Actual (Upper Bound) |  $1,700,000$ ($O(nd))$ |  $1,701,700$ ($O(nd+n)$)
Net Discounted Cumulative Gain (nDCG) | 0.073 | 0.093
F1 | 0.057 | 0.064
RMSE | 0.872 | 0.791

###  7.6 Tradeoffs between Cognitive Complexity and other Performance Metrics

Managers must consider multiple metrics when making decisions about which
algorithms to deploy. Table 2 shows the scores of all measures in the three
key performance dimensions (algorithmic interpretability, computational
complexity, and predictive performance). Among all measures in these three
dimensions, user-item bias outperforms user-user $k$-nearest neighbors in
terms of cognitive complexity and runtime complexity. The two algorithms have
similar predictive performance although user-user $k$-nearest neighbors scores
slightly better in F1 and Net Discounted Cumulative Gain (nDCG). Given the
salient gain in interpretability, user-item bias may be a better option for
managers. As shown in this example, the measurement framework gives managers a
quantitative metric of interpretability against which they can assess the
performance of the candidate algorithms under consideration.

##  8 Conclusion

In this work we present a framework for measuring algorithmic
interpretability. We build upon programming language theory and cognitive load
theory to model algorithm intrinsic complexity and human cognitive
constraints. In this section, we discuss our contributions to both research
and practice.

###  8.1 Contributions to Research

The first measurement framework for quantifying algorithmic interpretability,
a new dimension for analyzing algorithms. In the 1960s, to assess the
efficiency of running computer programs and storing data, scholars in the
field of programming language theory recognized the need for studying the
computational complexity of algorithms (Hartmanis and Stearns 1965, Knuth
2000). Researchers developed methods to “make quantitative assessments of the
goodness of various algorithms” (Knuth 2000). Today, in order to build trust,
ensure fairness, and track accountability, there is a need to study a new
dimension of goodness in algorithms – algorithmic interpretability (Hardt et
al. 2016, Xiao et al. 2018, Kearns and Roth 2019, Mittelstadt et al. 2019,
Zhang et al. 2020).

Just as scholars developed measurement frameworks for computational complexity
to quantify how hard it is for computers to compute algorithms, in this study
we are among the first to propose a measurement framework for algorithmic
interpretability to quantify how hard it is for humans to understand
algorithms. Based on these measurement frameworks, metrics such as runtime
complexity and space complexity are derived for computational complexity; in
this work, we derive the cognitive complexity score for algorithmic
interpretability.

#### Foundation for future downstream research in quantitative algorithmic
interpretability.

Computational complexity frameworks served as the foundation for later
research such as program optimization in software engineering (Knuth 1997,
2000). Our measurement framework and the corresponding cognitive complexity
score serve as a theoretical foundation for emerging research areas in
information systems such as algorithmic fairness, accountability,
transparency, and ethics. On the technical side, IS researchers develop and
analyze interpretable algorithms (e.g., Wang and Lin 2021). This research
stream can use cognitive complexity to quantify model interpretability,
instead of intuition-driven proxies for quantifying interpretability.

More broadly, within the ESG-ICE (environmental, social, and governance-
individual well-being, community welfare, and economic resilience) framework
for using analytics to address societal challenges proposed in Ketter et al.
(2020), effective measurement of algorithmic interpretability helps identify
obscure components in analytics projects and subsequent effort can be exerted
to improve transparency. Inscrutability is identified as an important facet of
AI (Berente et al. 2021). The formal measurement framework proposed in this
paper serves as a theoretical foundation to quantify this important facet of
AI.

Basis for improving the algorithm and the user learning process. Because we
characterize expertise using specific operations, users with low expertise can
see an appropriate representation of an algorithm and a list of operations
associated with a high expertise representation. The framework takes into
account what an individual has already learned when identifying appropriate
operations. Characterizing levels of expertise also provides a specific
learning opportunity for users with low expertise. If they can understand
those operations, they can understand a more compact, higher-level
representation of the algorithm. For our toy example, if a low expertise user
wants to understand revenue calculation better, he or she could learn how to
calculate dot products. This framework provides a benefit to educators. It
offers a reliable, unique representation of an algorithm at a particular level
of expertise to facilitate instruction. As user expertise increases, the
cognitive complexity of the algorithm monotonically decreases.

Potential implementation of a widely applicable and cost-effective measurement
method. Because of the structured program theorem, the framework presented is
general enough to account for any algorithm, even complex ones such as deep
neural networks. This universal property means that complex algorithms can be
broken down into operations and contexts and represented as (complex)
operation context graphs. It has long been assumed that such algorithms were
less interpretable than simpler algorithms (or not interpretable at all). Now
such comparisons can be quantified and tested to illustrate how wide the
intrinsic interpretability gap is. This will inform discussions of algorithmic
interpretability beyond notions of “black-box” algorithms and intuition-based
distinctions between interpretable and not interpretable algorithms (Rudin
2019, Leavitt and Morcos 2020). The framework is also computable.
Implementations of the framework are cost-effective ways to automatically
calculate algorithmic interpretability, as opposed to more costly user
studies.

###  8.2 Contributions to practice

Measuring algorithmic interpretability can benefit a variety of stakeholders.
Managers, users, policymakers, learners, and educators can use this framework
to explicitly quantify intrinsic interpretability instead of relying on
heuristics, intuition-driven categorizations, or post-hoc human assessments.

#### Managers:

When selecting the best algorithm for a task at hand, managers have to balance
several key tradeoffs, such as predictive performance, computational
complexity, and interpretability. The cognitive complexity score quantifies
how interpretable each candidate algorithm is to a specific user group.
Considering all related user groups, managers can accurately assess the
interpretability of the algorithms and then balance it against other
performance measures to make an informed decision.

#### Users:

With more algorithms being used in consumer products, external users such as
suppliers and customers want to know how and why certain algorithmic decisions
are being made. Interpretability can also affect how much a user trusts a
particular firm. Users can request an algorithmic representation at an
appropriate level for them and compare firms in terms of how interpretable
their algorithmic processes are. Users may not want to see the operation
context graphs for algorithms, although they are available, and may instead be
simply interested in comparing cognitive complexity scores.

With algorithms being implemented in business processes, internal users will
want a level of understanding regarding the new tools available in their
workflows (e.g., a recruiter using an AI-powered resume screener). An
understanding of the algorithm will be useful for them in making sense of the
decisions and providing feedback based on domain knowledge to make
improvements to the algorithm.

#### Policymakers:

Recently passed laws that require a “right to explanation” from algorithmic
decision systems do not specify the level of detail required for an
explanation to suffice (Goodman and Flaxman 2017). Some understanding of how
the algorithms generate outputs is needed. Policymakers and regulators could
set specific cognitive complexity guidelines for certain tasks, where an
algorithm used in a particular context must have a score below a certain
threshold. For example, regulation could be passed stating that for user
groups with a high school education, algorithms used for loan processing
decisions cannot have a cognitive complexity score above a certain threshold.
This gives a concrete user group (and therefore schematic knowledge base) and
specific score for firms to evaluate their models against. This score can also
serve as a proxy for cost, as a more complex algorithm may require hiring a
subject matter expert to assess the algorithm’s internal operations.171717 A
quantitative interpretability score can inform discussions on algorithm
accountability and ethical considerations (Abbasi et al. 2018, Martin 2019,
Berente et al. 2021). For certain high-stakes decision areas, one could
consider an interpretability ceiling, where a deployed model cannot be too
complex so that decisions made can be interpreted in the context of the
underlying algorithm. Additionally, cognitive complexity scores can help
policy makers to clarify requirements. For example, GDPR requires data
controllers to provide the data subjects with meaningful information about the
logic of model decision-making.

#### Learners and Educators:

Operation context graphs are a useful pedagogical device that implicitly
encode a curriculum for those who would like to better understand particular
algorithms. Each operation node is something that can potentially be
internalized as a schema. If a user wants to understand an algorithm better,
then the operation context graph provides a clear roadmap for what to learn
next.

Our framework also identifies bottlenecks for learners. Because of the
cognitive cost of high element interactivity, certain nodes in an operation
context graph are more cognitively demanding than others. Educators can
identify these complex sections of the graph and teach the schematic knowledge
needed to abstract them to a higher-level schema.

This framework provides a much-needed theoretical grounding for measuring
algorithmic interpretability. Our hope is that this work acts as a call to the
research community to motivate work on quantitative, theoretically grounded
algorithmic interpretability and incorporate it into broader research in
algorithmic fairness, accountability, transparency, and ethics.

## References

  * Abbasi et al. (2018) Abbasi A, Li J, Clifford G, Taylor H (2018) Make “fairness by design” part of machine learning. _Harvard Business Review_ .
  * Abdul et al. (2018) Abdul A, Vermeulen J, Wang D, Lim BY, Kankanhalli M (2018) Trends and Trajectories for Explainable, Accountable and Intelligible Systems: An HCI Research Agenda. _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_ , 582:1–582:18, CHI ’18 (New York, NY, USA: ACM), ISBN 978-1-4503-5620-6, URL http://dx.doi.org/10.1145/3173574.3174156.
  * Abdul et al. (2020) Abdul A, von der Weth C, Kankanhalli M, Lim BY (2020) COGAM: Measuring and moderating cognitive load in machine learning model explanations. _Conference on Human Factors in Computing Systems (CHI ’20)_.
  * Adadi and Berrada (2018) Adadi A, Berrada M (2018) Peeking Inside the Black-Box: A Survey on Explainable Artificial Intelligence (XAI). _IEEE Access_ 6:52138–52160.
  * Adomavicius and Tuzhilin (2005) Adomavicius G, Tuzhilin A (2005) Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. _IEEE Transactions on Knowledge and Data Engineering_ 17(6):734–749.
  * Adomavicius and Tuzhilin (2011) Adomavicius G, Tuzhilin A (2011) Context-aware recommender systems. _Recommender Systems Handbook_ , 217–253 (Springer).
  * Agarwal et al. (2020) Agarwal S, Ananthakrishnan N, Ben-David S, Lechner T, Urner R (2020) On Learnability wih Computable Learners. _Algorithmic Learning Theory_ , 48–60.
  * Allen (1970) Allen FE (1970) Control Flow Analysis. _Proceedings of a Symposium on Compiler Optimization_ , 1–19 (New York, NY, USA: Association for Computing Machinery), ISBN 978-1-4503-7386-9, URL http://dx.doi.org/10.1145/800028.808479.
  * Allen and Cocke (1976) Allen FE, Cocke J (1976) A program data flow analysis procedure. _Communications of the ACM_ 19(3):137.
  * Baddeley (1983) Baddeley AD (1983) Working memory. _Philosophical Transactions of the Royal Society of London. B, Biological Sciences_ 302\.
  * Barbin et al. (2012) Barbin E, Borowczyk J, Chabert JL, Guillemot M, Michel-Pajus A, Djebbar A, Martzloff JC (2012) _A History of Algorithms: From the Pebble to the Microchip_ (Springer Science & Business Media).
  * Baydin et al. (2017) Baydin AG, Pearlmutter BA, Radul AA, Siskind JM (2017) Automatic differentiation in machine learning: A survey. _The Journal of Machine Learning Research_ 18(1):5595–5637.
  * Berente et al. (2021) Berente N, Gu B, Recker J, Santhanam R (2021) Special issue editor’s comments: Managing artificial intelligence. _Management Information Systems Quarterly_ 45(3):1433–1450.
  * Böhm and Jacopini (1966) Böhm C, Jacopini G (1966) Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules. _Communications of the ACM_ 9(5):366–371, ISSN 0001-0782, URL http://dx.doi.org/10.1145/355592.365646.
  * Carletti et al. (2017) Carletti V, Foggia P, Saggese A, Vento M (2017) Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 40(4):804–818.
  * Chouldechova (2017) Chouldechova A (2017) Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. _Big Data_ 5(2):153–163.
  * Church (1936) Church A (1936) A note on the Entscheidungsproblem. _Journal of symbolic logic_ 1(1):40–41.
  * Cook (1971) Cook SA (1971) The Complexity of Theorem-Proving Procedures. _Proceedings of the Third Annual ACM Symposium on Theory of Computing_ , 151–158, STOC ’71 (New York, NY, USA: Association for Computing Machinery), ISBN 978-1-4503-7464-4, URL http://dx.doi.org/10.1145/800157.805047.
  * Cooke (2011) Cooke RL (2011) _The History of Mathematics: A Brief Course_ (John Wiley & Sons).
  * Cowan (2005) Cowan N (2005) _Working Memory Capacity_ (Psychology Press).
  * De-Arteaga et al. (2019) De-Arteaga M, Romanov A, Wallach H, Chayes J, Borgs C, Chouldechova A, Geyik S, Kenthapadi K, Kalai AT (2019) Bias in bios: A case study of semantic representation bias in a high-stakes setting. _proceedings of the Conference on Fairness, Accountability, and Transparency_ , 120–128.
  * Doshi-Velez and Kim (2017) Doshi-Velez F, Kim B (2017) Towards A Rigorous Science of Interpretable Machine Learning. _arXiv preprint_ 1702.08608.
  * Ekstrand et al. (2011) Ekstrand MD, Riedl JT, Konstan JA, et al. (2011) Collaborative filtering recommender systems. _Foundations and Trends in Human–Computer Interaction_ 4(2):81–173.
  * Freeman (1986) Freeman LC (1986) Order-based statistics and monotonicity: A family of ordinal measures of association. _Journal of Mathematical Sociology_ 12(1):49–69.
  * Gilpin et al. (2018) Gilpin LH, Bau D, Yuan BZ, Bajwa A, Specter M, Kagal L (2018) Explaining explanations: An overview of interpretability of machine learning. _2018 IEEE 5th International Conference on Data Science and Advanced Analytics (DSAA)_ , 80–89 (IEEE).
  * Goodman and Flaxman (2017) Goodman B, Flaxman S (2017) European Union regulations on algorithmic decision-making and a “right to explanation”. _AI Magazine_ 38(3):50–57.
  * Hardt et al. (2016) Hardt M, Price E, Srebro N (2016) Equality of opportunity in supervised learning. _Advances in Neural Information Processing Systems_ 29\.
  * Harper and Konstan (2015) Harper FM, Konstan JA (2015) The movielens datasets: History and context. _ACM Transactions on Interactive Intelligent Systems_ 5(4):1–19.
  * Hartmanis and Stearns (1965) Hartmanis J, Stearns RE (1965) On the computational complexity of algorithms. _Transactions of the American Mathematical Society_ 117:285–306.
  * Herlocker et al. (2002) Herlocker J, Konstan JA, Riedl J (2002) An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms. _Information Retrieval_ 5(4):287–310.
  * Kalyuga (2014) Kalyuga S (2014) Critical Thinking and Higher Order Thinking: A Current Perspective. chapter Critical thinking: A cognitive load perspective, 245–258 (Nova Science Publishers).
  * Kearns and Roth (2019) Kearns M, Roth A (2019) _The Ethical Algorithm: The Science of Socially Aware Algorithm Design_ (Oxford University Press).
  * Ketter et al. (2020) Ketter W, Padmanabhan B, Pant G, Raghu T (2020) Special Issue Editorial: Addressing Societal Challenges through Analytics: An ESG ICE Framework and Research Agenda. _Journal of the Association for Information Systems_ 21(5):9.
  * Kluver et al. (2018) Kluver D, Ekstrand MD, Konstan JA (2018) Rating-based collaborative filtering: Algorithms and evaluation. _Social Information Access_ , 344–390 (Springer).
  * Knuth (1997) Knuth D (1997) _The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition_ (Reading, Mass: Addison-Wesley Professional), 3rd edition, ISBN 978-0-201-89683-1.
  * Knuth (2000) Knuth DE (2000) _Selected Papers on Analysis of Algorithms_ (CSLI Publications).
  * Lage et al. (2018) Lage I, Ross AS, Kim B, Gershman SJ, Doshi-Velez F (2018) Human-in-the-Loop Interpretability Prior. _Conference on Neural Information Processing Systems (NeurIPS 2018)_.
  * Leavitt and Morcos (2020) Leavitt ML, Morcos A (2020) Towards falsifiable interpretability research. _arXiv preprint_ 2010.12016.
  * Lee and Hosanagar (2021) Lee D, Hosanagar K (2021) How do product attributes and reviews moderate the impact of recommender systems through purchase stages? _Management Science_ 67(1):524–546.
  * Li et al. (2021) Li X, Xiong H, Li X, Wu X, Zhang X, Liu J, Bian J, Dou D (2021) Interpretable deep learning: Interpretation, interpretability, trustworthiness, and beyond. _arXiv preprint_ 2103.10689.
  * Lipton (2018) Lipton ZC (2018) The Mythos of Model Interpretability. _Communications of the ACM_ 61(10):36–43, ISSN 0001-0782, URL http://dx.doi.org/10.1145/3233231.
  * Lucas et al. (2013) Lucas H Jr, Agarwal R, Clemons EK, El Sawy OA, Weber B (2013) Impactful research on transformational information technology: An opportunity to inform new audiences. _Management Information Systems Quarterly_ 371–382.
  * Martin (2019) Martin K (2019) Ethical implications and accountability of algorithms. _Journal of Business Ethics_ 160(4):835–850.
  * McCabe (1976) McCabe TJ (1976) A Complexity Measure. _IEEE Transactions on Software Engineering_ SE-2(4):308–320, ISSN 1939-3520, URL http://dx.doi.org/10.1109/TSE.1976.233837.
  * McKinney et al. (2020) McKinney SM, Sieniek M, Godbole V, Godwin J, Antropova N, Ashrafian H, Back T, Chesus M, Corrado GS, Darzi A, et al. (2020) International evaluation of an AI system for breast cancer screening. _Nature_ 577(7788):89–94.
  * Miller (1994) Miller GA (1994) The magical number seven, plus or minus two: Some limits on our capacity for processing information. _Psychological review_ 101(2):343.
  * Mittelstadt et al. (2019) Mittelstadt B, Russell C, Wachter S (2019) Explaining Explanations in AI. _Proceedings of the Conference on Fairness, Accountability, and Transparency - FAT* ’19_ 279–288, URL http://dx.doi.org/10.1145/3287560.3287574.
  * Murdoch et al. (2019) Murdoch WJ, Singh C, Kumbier K, Abbasi-Asl R, Yu B (2019) Definitions, methods, and applications in interpretable machine learning. _Proceedings of the National Academy of Sciences (PNAS)_.
  * Paas et al. (2003) Paas F, Renkl A, Sweller J (2003) Cognitive Load Theory and Instructional Design: Recent Developments. _Educational Psychologist_ 38(1):1–4.
  * Peffers et al. (2007) Peffers K, Tuunanen T, Rothenberger MA, Chatterjee S (2007) A design science research methodology for information systems research. _Journal of Management Information Systems_ 24(3):45–77.
  * Poursabzi-Sangdeh et al. (2021) Poursabzi-Sangdeh F, Goldstein DG, Hofman JM, Vaughan JW, Wallach H (2021) Manipulating and Measuring Model Interpretability. _Conference on Human Factors in Computing Systems (CHI ’21)_.
  * Ross et al. (2021) Ross AS, Chen N, Hang EZ, Glassman EL, Doshi-Velez F (2021) Evaluating the Interpretability of Generative Models by Interactive Reconstruction. _CHI Conference on Human Factors in Computing Systems (CHI ’21)_.
  * Rudin (2019) Rudin C (2019) Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead. _Nature Machine Intelligence_ 1(5):206–215, ISSN 2522-5839, URL http://dx.doi.org/10.1038/s42256-019-0048-x.
  * Shivers (1991) Shivers O (1991) _Control-Flow Analysis of Higher-Order Languages_. Ph.D. thesis, PhD thesis, Carnegie Mellon University.
  * Solnon (2010) Solnon C (2010) AllDifferent-based filtering for subgraph isomorphism. _Artificial Intelligence_ 174(12-13):850–864.
  * Stevens (1958) Stevens SS (1958) Measurement and man. _Science_ 127(3295):383–389.
  * Strickland (2021) Strickland E (2021) OpenAI’s GPT-3 Speaks!(Kindly Disregard Toxic Language). _IEEE Spectrum_ 1\.
  * Sweller (1994) Sweller J (1994) Cognitive load theory, learning difficulty, and instructional design. _Learning and Instruction_ 4:295–312.
  * Sweller (2003) Sweller J (2003) The Psychology of Learning and Motivation: Advances in Research and Theory. volume 43, chapter Evolution of human cognitive architecture, 215–266 (Academic Press).
  * Sweller et al. (1998) Sweller J, Van Merrienboer JJ, Paas FG (1998) Cognitive architecture and instructional design. _Educational psychology review_ 10(3):251–296.
  * Turing (1936) Turing AM (1936) On computable numbers, with an application to the Entscheidungsproblem. _Journal of Math_ 58(345-363):5.
  * van Merrienboer and Sweller (2005) van Merrienboer JJG, Sweller J (2005) Cognitive load theory and complex learning: Recent developments and future directions. _Educational Psychology Review_ 17:147–177.
  * Wang and Lin (2021) Wang T, Lin Q (2021) Hybrid Predictive Models: When an Interpretable Model Collaborates with a Black-box Model. _Journal of Machine Learning Research_ 22(137):1–38.
  * Xiao et al. (2018) Xiao C, Choi E, Sun J (2018) Opportunities and challenges in developing deep learning models using electronic health records data: A systematic review. _Journal of the American Medical Informatics Association_ 25(10):1419–1428.
  * Zhang et al. (2020) Zhang Y, Liao QV, Bellamy RKE (2020) Effect of Confidence and Explanation on Accuracy and Trust Calibration in AI-Assisted Decision Making. _ACM Conference on Fairness, Accountability, and Transparency (ACM FAT)_ .

##  9 Relevant Theoretical Concepts

Table 3: Key concepts in programming language theory (PLT) and cognitive load theory (CLT) Theory |  Concept |  Description
---|---|---
PLT |  Control flow |  Control flow refers to the order in which program operations are executed by a computer.
|  Control flow graph |  Graphical representation of the operations and flow of a program execution.
|  Sequence |  A sequence is a control flow where one block follows another.
|  Selection |  A selection is a control flow where the computer must evaluate a boolean expression before moving to the next block.
|  Iteration |  An iteration is a control flow where the computer repeats a set of blocks until some boolean becomes true.
|  Structured program theorem |  The structured program theorem states that every algorithm can be represented as a control flow graph using only sequences, selections, and operations to define the control flow.
CLT |  Working memory |  Working memory has limited capacity and may become overloaded.
|  Long-term memory |  Long-term memory can hold knowledge in the form of schemas and is effectively unlimited.
|  Schema |  Schema is a knowledge structure used in long-term memory. Lower-level schemas can be incorporated into high-level schemas. Each schema, regardless of its complexity level, is processed as a single entity in working memory.
|  Human schematic knowledge base |  Human schematic knowledge base represents human expertise and is the major critical factor influencing how we learn new information.
|  Intrinsic cognitive load |  Intrinsic cognitive load is determined by both the nature of the materials being learned and the learner’s expertise. Intrinsic cognitive load can be characterized in terms of element interactivity. Intrinsic cognitive load is higher if the number of interacting elements is higher because more elements have to be processed simultaneously to fully understand the material.
|  Germane cognitive load |  Germane cognitive load refers to the necessary demand on working memory capacity.
|  Extraneous cognitive load |  Extraneous cognitive load refers to the unnecessary demand on working memory capacity often caused by ineffective instructional procedures.

##  10 Proofs of Framework Properties

######  Property 1 (Universality)

For any algorithm $a$ and user group $u$, the proposed measurement framework
is applicable to the $(a,u)$ pair.

Proof: By the structured program theorem, any algorithm can be represented as
a control flow graph (Böhm and Jacopini 1966). For a user group with no
internalized schemas (or no relevant schemas), then the representation is a
fully-decomposed version of the algorithm (i.e., machine level code). For any
schema that is added and relevant, it will reduce the graph size. For a user
group that has fully internalized the algorithm as a schema, the graph will be
fully abstracted. $\blacksquare$

######  Property 2 (Computability)

For any algorithm $a$ and user group $u$, the proposed measurement framework
is machine-computable.

Proof: Once $a$ and $u$ are known, then the process of constructing an
operation-context graph is fully automated. By the definition of computable
functions, the conversion to operation-context graph can be computed as a
sequence of steps. Specifically, from the fully decomposed graph
representation, the problem of identifying the appropriate schemas for
abstraction reduces to a subgraph isomorphism problem, a well-studied problem
in computer science (Cook 1971).181818Graph isomorphism is an NP-Hard problem
in computer science, for which a number of solvers exist (e.g., Solnon 2010,
Carletti et al. 2017). $\blacksquare$

######  Property 3 (Uniqueness)

For a given algorithm $a$ and a given user group $u$, the proposed measurement
framework generates a unique cognitive complexity score $CC(a,u)$.

Proof: Here we assume that $u$ will rely on the highest-level schemas
available in the internalized knowledge base. This is due to the fact that the
users will rely on the higher-level schemas when available and, therefore,
will not have a situation where there is a conflict between two possible
lower-level schemas that can replace a subgraph in $G$. $\blacksquare$

######  Property 4 (Monotonicity)

For a given algorithm $a$, and two user groups $u_{1}$ and $u_{2}$, if user
group $u_{1}$ has lower algorithmic literacy than user group $u_{2}$, then the
cognitive complexity score is higher for $u_{1}$ than $u_{2}$, (i.e.,
$\text{if }S_{u_{1}}\subset S_{u_{2}},\text{then }CC(a,u_{1})\geq
CC(a,u_{2}))$.191919This applies to cases where expertise is single-
dimensional, i.e., a lay person and physician or a low algorithmic literacy
and high algorithmic literacy individual. In this case $S_{u_{1}}$ is a
superset of $S_{u_{2}}$.

Proof: If $S_{u_{1}}=S_{u_{2}}$, then the result is trivial. In the case where
$S_{u_{1}}$ is a proper superset of $S_{u_{2}}$, then the starting point of
our operation-context graph is $OCG(a,u_{1})$. Therefore, if we use any new
operations in $S_{u_{2}}$ to change the graph, it will be to further abstract
away subsections. This reduction will reduce the number of nodes in the graph
and, therefore, the cognitive complexity of the graph. $\blacksquare$