#  Fairer Software Made Easier (using “Keys”)

Tim Menzies, Kewen Peng, Andre Lustosa
Computer Science, NC State, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Can we simplify explanations for software analytics? Maybe. Recent results
show that systems often exhibit a “keys effect”; i.e. a few key features
control the rest. Just to say the obvious, for systems controlled by a few
keys, explanation and control is just a matter of running a handful of “what-
if” queries across the keys. By exploiting the keys effect, it should be
possible to dramatically simplify even complex explanations, such as those
required for ethical AI systems.

##  I Introduction

Sometimes, AI must be explainable. If some model learned by an AI is to be
used to persuade someone to change what they are doing, it needs to be
explainable such that humans can debate the merits of its conclusions. Tan et
al. [1] argue that for software vendors, managers, developers and users,
explainable insights are the core deliverables of analytics. Sawyer et al.
comment that explainable (and actionable) insights are the key driver for
businesses to invest in analytics [2].

Recently, the requirements for explainable AI have become quite complex. The
European Union, Microsoft, and the IEEE have all released white papers
discussing ethical AI [3, 4, 5]. While these documents differ in the details,
they all agree that ethical AI must be “FAT”; i.e. fair, accountable and
transparent. Such “FAT” systems support five “FAT” items:

  1. 1.

Integration with human agency;

  2. 2.

Accountability, where old conclusions can be challenged;

  3. 3.

Transparency of how conclusions are made;

  4. 4.

Oversight on what to change so as to change conclusions;

  5. 5.

Inclusiveness, such that no specific segment of society is especially and
unnecessarily privileged or discriminated against by the actions of the AI.

This list may seem like a complex set of requirements for explainable ethical
AI. However, as seen in this paper, software systems often have a “keys
effect” by which a few key features control the rest. Just to say the obvious,
when systems are controlled by a few keys, then explanation and control is
just a matter of running a few “what-if” queries over the keys. The rest of
this paper discusses (a) how to implement the five “FAT” items; and (b) how
the keys effect simplifies all those implementations.

##  II But First, What is “Explanation”?

Cognitive science argues that models comprising small rules are more
explainable. Larkin et al. [6] characterize human expertise in terms of very
small short term memory, or STM (used as a temporary scratch pad for current
observation) and a very large long term memory, or LTM. The LTM holds separate
tiny rule fragments that explore the contents of STM to say “when you see
THIS, do THAT”. When an LTM rule triggers, its consequence can rewrite STM
contents which, in turn, can trigger other rules. Short term memory is very
small, perhaps even as small as four to seven items [7, 8]. Experts are
experts, says Larkin et al. [6] because the patterns in their LTM dictate what
to do, without needing to pause for reflection. Novices perform worse than
experts, says Larkin et al., when they fill up their STM with too many to-
do’s. Since, experts post far fewer to-do’s in their STMs, they complete their
tasks faster because (a) they are less encumbered by excessive reflection and
(b) there is more space in their STM to reason about new information.

First proposed in 1981, this theory still remains relevant111Recently, Ma et
al. [9] used evidence from neuroscience and functional MRIs to argue that STM
capacity might be better measured using other factors than “number of items”.
But even they conceded that “the concept of a limited (STM) has considerable
explanatory power for behavioral data”.. Humans best understand a model which
can “fit” it into their LTM; i.e., when that model comprises many small
fragments. Phillips et al. [10] and others [11, 12, 13] discuss how models
containing tiny rule fragments can be quickly comprehended by doctors in
emergency rooms making rapid decisions; or by soldiers on guard making snap
decisions about whether to fire or not on a potential enemy; or by
stockbrokers making instant decisions about buying or selling stock. This
theory-of-small-fragments explains both expert competency and incompetency in
software engineering tasks such as understanding code [14]. Specifically,
expert-level comprehension means having rules that quickly lead to decisions,
without clogging the STM.

It can be hard to find small transparent chunks of knowledge in large data
sets. To some extent, FFTtrees [10], LIME [15], and SHAP [16] addresses that
problem. But a recent literature survey by Peng et al. [17] shows that current
explanation tools just rank the influence of features on single goals. Also,
LIME and SHAP have two other limitations: they only show how single features
effect single goals. Also they rely on randomly generated instances. Such
instance creation can overlook important structural details (such as the keys
effect, described below). The explanations generated in that way might be
over-elaborate, or irrelevant [17].

Hence, we seek a better framework that (a) offers succinct explanations from
conjunctions of multiple features on multiple goals; and which (b) understands
the structure of the data.

##  III What are “Keys”?

We have said in the introduction that the keys effect means a few key features
control the rest. Another way to say the say thing is that most features in a
system can be ignored or, more formally, a system with $N$ variables with $S$
values usually visits much less than $S^{N}$ states. This section discusses
this “Druzdel effect” and shows how it impacts the number of key features that
control a system.

Imagine, in Figure 1, that we discretize the horizontal and vertical features
into ten equal-width bins. Once discretized in this way, then this data has
$(S=10)^{N=2}=100$ states. But since the distribution of these features are
skewed (particularly, the horizontal blue values), many of those states occur
at zero frequency (evidence: see the white space in Figure 1).

Figure 1: Joint distributions from software comprising two features running in
three modes (blue, yellow, grey).

This Druzdel effect (that most of the potential states within software are
never visited) has been observed in practice. For example, Druzdel’s [18]
logged the frequency of observed states in a medical diagnostic system that
monitored anesthesia patients in intensive care. Of the 525,312 observed
states, one state occurred over half the time; 49 states covered 91% of the
probabilities; and the remaining states occurred vanishingly rarely (at
frequencies ranging from $10^{-6}$ to $10^{-22}$).

One explanation for this Druzdel effect is that when code runs, it only visits
the $v$ states approved by the combination of its internal logic – and this
space can be far smaller that $S^{N}$ (so $v\ll S^{N}$). Explanations, or
controllers, of software that visits $v\ll S^{N}$ states only need to explore
$\log_{2}{v}$ “key” features. For example, Zhang et al. report that by
generating tests only for the main branches in the code, even applications
that process large cloud databases can be tested via just a few dozen inputs
[19].

The number of keys features in a data set can be inferred from the number of
examples required to model that data; e.g.

  * •

Druzdel found $v_{1}=49$ commonly reached states.

  * •

Yu et al. [20] report that security violations in 28,750 Mozilla functions can
be successfully modelled via an SVM with $v_{2}=271$ support vectors.

  * •

Tu et al. [21] report that defect labelling in $6000$ commits from Github can
be successfully modelled via a SVM with $v_{3}=300$ support vectors [21].

Assuming binary features and that the number of key features is
$N_{i}=log_{2}v_{i}$. Hence, the above systems could be controlled via
$N_{1},N_{2},N_{3}\approx 6,9,9$ key binary features.

##  IV Example

This sections shows a small example where keys find the tiny fragments of
knowledge recommended by cognitive scientists.

Suppose an analyst wants to buy a fuel efficient lightweight car with good
acceleration. The file auto93 (from the UC Irvine ML repository) has hundreds
of examples of cars that mentions those features as well as number of
cylinders $c$, horsepower $h$, displacement $d$ (a.k.a. size of car), year of
release $y$ and country of origin $o$. From this data, we could apply (e.g.)
linear regression to learn the model of Equation 1:

<EMAIL_ADDRESS>\mathit{mpg}&-0.6{\times}c+-0.1{\times}d+-0.1h+0.6{\times}y+1.2{\times}o+-12.9\\\
\mathit{accel}&0.1{\times}c+0.1{\times}d+-0.1h+0.1{\times}y+-0.2{\times}o+21.2\end{array}$
(1)

This model is not tiny chunks of instantly interpretable knowledge recommended
by cognitive scientists. In order to make recommendations about what kind of
car to buy, some further processing is required. For example, we could run a
large number of what-of queries across a large population of cars. A standard
tool for this purpose is a genetic algorithm that (a) mutates population of
cars, (b) scores the mutants on the above three equations, then (c) selects
the best scoring mutants as parents for the next generation of mutants. That
genetic algorithm approach may not not scale to large problems. Peng et al.
[17] has applied genetic algorithms to explore $C=10^{4}$ software
configuration options (in order to optimize for $G=2$ goals). In that
application, the $O(GC^{3})$ non-dominating sort procedure of the NSGA-II [22]
genetic algorithm took hours to terminate. A (much) faster approach, that
generates tiny chunks of instantly interpretable knowledge, comes from
assuming the keys effect, as follows.

  * •

If features control the output, then it follows that those features, with
different settings, appear in different outputs.

  * •

Also, if those features are few in number, then they will be a small set of
features with most effect on the results.

To say that another way, to exploit the keys effect. we only need to apply a
little data mining. The follow three points describe a baseline keys-based
algorithm called KEYS0. The algorithm assumes that there exists a small number
of feature ranges that occur with different frequencies in desired and
undesired outcomes. Hence, a little random sampling is enough to quickly find
those keys.

  1. 1.

Randomly divide the data. Select a few random points to find two distant
points $P_{1},P2$ within the data. Sort them such that point $P_{1}$ is better
than $P_{2}$ (if exploring multiple goals, use some domination predicate to
rank the two items). Mark the data best, rest depending on whether it is
closest to $P_{1},P2$ respectively.

  2. 2.

Look for feature ranges with very different frequencies in best and rest.
Divide numeric features into $\sqrt{n}$ sized ranges. Combine adjacent ranges
that have similar best,rest frequencies. Rank feature ranges, favoring those
that are more frequent in best than rest. Print the top-ranked range.

  3. 3.

Recurse. Select the data that matches that top range (discarding the rest). If
anything is discarded, loop back to step1.

When applied to the auto93 data, in 52ms, KEYS0 terminates in two loops after
evaluating just four cars. KEYS0 prints two tiny chunks of instantly
interpretable knowledge; i.e. the ranges “cylinders $\leq$ 4” and “origin==3”.

Figure 2 shows the position of the data selected by KEYS0. In a result
consistent with the presence of keys within auto93, we see that by examining
just four examples andFairer Software Made Easier (using “Keys”) asking about
two ranges, we can find a useful

Figure 2: 16 clusters of 398 examples from auto93. Arrow shows data found by
KEYS0.

region in the data. Further improvements are possible, of course (e.g. the
acceleration is still mid-range in the final selected data). Nevertheless, the
things to note here is (a) how little we had to probe the data in order to
achieve such large improvements via tiny chunks of quickly interpretable
knowledge; and (b) as far as we can tell, the model learned by KEYS0 is not
apparent within the output of standard learners such as Equation 1.

##  V What Causes Keys?

Menzies [23] speculates that keys arise from naturalness [24] and/or power-law
[25] effects. Since programs exhibit the same frequency patterns seen in human
language, then naturally we would expect that code usually contains a small
number of structures, repeated many times [24]. As to power laws, suppose
programmer2 most understands a small region of the code written by
programmer1. That programmer would tend to make most changes around that
region. If programmer3 does the same for programmer2’s code, and programmer4
does the same for programmer3’s code then that, over time, that team would
spend most of their time working on a tiny portion of the overall code base
[25]. In such natural code that is subject to those power laws, finding a
controller for any part of the code would mean that we also have a controller
for many other parts of the code (due to repetition, due to the small size of
the maintained code base).

These effects are not just theoretical speculation– they have been seen in
practice. Lin and Whitehead report power law effects they have observed in
software [25]. Hindle et al. [24] report all the application work in software
analytics that successfully exploits naturalness. Stallings [26] comments that
the design of operating systems often assumes a locality of reference; i.e.
that program execution does not dash across all the code all the time but
instead is mostly focused on a small part of the memory or instruction space.
Lumpe et al. [27] report studies tracking decades of work in dozens of open
source projects. In that code base, most classes are written once, revised
never. Also, most of the defect inducing activity is centered around a small
number of rapidly changing classes. A similar pattern (where most activity is
focused on a small part of the code base) has been reported in software from
AT&T [28], NASA [29], and within some widely used open source compiler tools
(GCC [29]).

##  VI Exploiting Keys for Ethical AI

Regardless of their cause, this section argues the keys effect can support the
five “FAT” items listed in the introduction.

Integration with human agency: Figure 3 shows human+AI interaction. For
example, active

Figure 3: Model Building. (1) initial work; (2) some progress; (3) diminishing
returns; (4) performance plateaus; (5) normal operation; (6) some problem; (7)
fixed; (8) collapse, after which the cycle might start again.

learning is where AI and humans team up to solve problems. Whenever humans
make a decision about certain example, the active learner updates a model that
predicts what humans might say about the next example. Once the AI can
adequately predict the human’s opinion, then the human can retire and the AI
can label the rest of the data. In Figure 3, one explanation system is better
than another if it leads to higher z = goals are achieved with fewer
$y=decisions$.

Figure 4: Algorithm with oversight authority can request changes that alter
conclusions. In this example, the tree on the left has median number of
defects per leaf. Using this structure, we can walk the tree looking for plans
that change the conclusion from defects = 90% probable to defects = 10%
problem (here, RFC, LOC, RBO are static code metrics that can be altered by
different refactoring activities defined in Table 2 of [30]). In this example,
there is historical data that RFC, LOC are never changed without also changing
RBO. Hence, we would propose the right-hand plan since it has most precedent
in the historical record. Example from [31].

We actually saw an example of Figure 3 in the above discussion. Yu,Tu et al.
[20, 21] incrementally updated an SVM model based on an active learner. In a
result consistent with the keys effect, they needed only a few hundred support
vectors to model their data (Firefox security violations and the labelling of
defect data in Github). We conjecture that this result could be improved even
further (using fewer questions) by combining KEYS0 with the Yu,Tu tools.

Accountability: If we cache the y-axis decisions of Figure 3, then the
decision process that leads to the current system can be replayed by a third
party. For systems demonstrating the keys effect, then the total number of
features that needs to be reviewed during an audit could be as low as a
$\log_{2}{10^{3}}$ (see the calculations at the end of §III). While this might
take days to weeks to study, such a manual audit is within the realms of
possibilities by human beings. Further, if we cache the entire rig that
generated Figure 3, then it would be possible to change some decision about
the $y$ axis, then replay the rest of the reasoning to see if that change
effect the outcomes of the rest of the system. Finally, if some part of the
Figure 3 needs to be entirely revised then the keys effect promises that that
revision would not be an arduous process.

Transparency: One issue with integrating with human agency is cognitive
overload. Humans and AI tools can cope with different amounts of data. AI
tools can readily process $10^{8}$ examples per minute, where example might
contain $10^{2}$ features, or even more [32]. Human reasoning, on the other
hand, is not so scalable. While we cannot speak for all humans, this author
asserts that reading $10^{8}$ examples is just overwhelming. Hence we say that
one explanation system is more transparent than another if it shows the user
less data; i.e if it does not lead to cognitive overload.

Here again, keys can be useful. Recall from §IV that we used keys to explore
hundreds of examples with just two questions about two features. In an even
more impressive example, Lustosa et al. [33] recently used a variant of KEYS0
to explore different options for managing an agile SCRUM project. That study
explored 10,000 examples with 128 features by asking the user $y\leq 6$
questions (where each question mentioned only 4 ranges). Note that, once
again, needing to control so few features is yet another example of how keys
can simplify explaining/controlling a system.

Human oversight: Krishna et al. [31] argues we can learn how to change
conclusions using (a) one algorithm that makes predictions; then (b) a second
algorithm that reports the delta between regions with different predictions.
His variant of KEYS0 recursively divide the whole data, without pruning any
branches. Next, he computed the mean conclusion seen in each leaf. As shown in
Figure 4, left-hand-side, we might prefer some leaf conclusions over the
others (e.g. some leaves have a 90% probability of software having defects
while other leaves predict a 0% probability of defects). In that case, we can
walk the tree from worse to better conclusions, each time querying the data
division rule at each node. If that process finds multiple ways to improve
some conclusion then, as shown in Plan2 of Figure 4, we might prefer the plan
with most precedence in the historical record. In a result consistent with the
keys effect, for data sets with 20 features, the plans generated by this
procedure only needs to change 2-4 features [31, 30].

Inclusiveness: there are many tests for checking if an AI tool is unfairly
making conclusions at (e.g.) different false positive rates for different
social groups. One way to repair an unfair learner is to change how that
learner builds its model via hyperparameter optimization [34, 35]; i.e.
planning to change the learner control parameters such that the (say) false
alarm rates are adjusted. In such optimization, the nodes of the trees in
Figure 4 would refer to control parameters of the learner while the leaves
would be scored by (e.g.) the false alarm rates for the different social
groups in the data. With those changes, the planning process described in
Figure 4 could also be applied to unfairness reduction.

##  VII Discussion and Future Work

We need to study explanation since explanation is the key to so much more;
e.g., as shown above, controlling, classification, regression, planning, and
optimization. As part of that study, we should also explore the keys effect
since, as suggested above, those keys can simplify the generation of even
complex types of explanations.

But keys does not solve all the problems of explanation and ethical AI. In
fact, reviewing the above, we can see many open issues. For example, do all
data sets have keys? Is there some graduated explanation algorithm that can
shift easily from “keys mode” (for data sets with keys) to another mode (for
other kinds of data)? KEYS0 currently divides data using a Euclidean distance
metric. But what about other dimensions as synthesised by (e.g.) some neural
autoencoder? Further, what happens to Figure 1 if humans make a wrong decision
along the y-axis? How do we detect that mistake? Furthermore, what happens
when teams work together yet team members have conflicting goals?

The above paragraph is just a short sample of the issues raised by our work on
keys-as-explanation (for other issues and research challenges raised buy this
article, see http://tiny.cc/todo21). In our experience, exploring keys-for-
explanation, we often find more research questions than what we started with.
But perhaps that is the true power of keys. Keys-based explanation systems are
so simple, so easily implemented, that they encourage experimentation and,
hence, the faster recognition of open research issues. Our belief is that
exploring those further issues will be made easier by keys (and that is our
current research direction). Time will tell if that belief is correct.

## References

  * [1] S.-Y. Tan and T. Chan, “Defining and conceptualizing actionable insight: a conceptual framework for decision-centric analytics,” _arXiv preprint arXiv:1606.03510_ , 2016.
  * [2] R. Sawyer, “Bi’s impact on analyses and decision making depends,” in _Principles & Applications of Business Intelligence_. IGI Global, 2013, pp. 83–95.
  * [3] “Ethically-aligned design: A vision for prioritizing human well-begin with autonomous and intelligence systems.” 2019.
  * [4] “Ethics guidelines for trustworthy artificial intelligence.” 2018. [Online]. Available: https://ec.europa.eu/digital-single-market/en/news/ethics-guidelines-trustworthy-ai
  * [5] “Microsoft AI principles,” 2019. [Online]. Available: http://tiny.cc/Microsoft
  * [6] J. Larkin, J. McDermott, D. P. Simon, and H. A. Simon, “Expert and novice performance in solving physics problems,” _Science_ , vol. 208, no. 4450, pp. 1335–1342, 1980. [Online]. Available: http://science.sciencemag.org/content/208/4450/1335
  * [7] G. A. Miller, “The magical number seven, plus or minus two: some limits on our capacity for processing information.” _Psychological review_ , vol. 63, no. 2, p. 81, 1956.
  * [8] N. Cowan, “The magical number 4 in short-term memory: a reconsideration of mental storage capacity,” _Behav Brain Sci_ , vol. 24, no. 1, pp. 87–114, Feb 2001.
  * [9] W. J. Ma, M. Husain, and P. M. Bays, “Changing concepts of working memory,” _Nature neuroscience_ , vol. 17, no. 3, pp. 347–356, 2014.
  * [10] N. D. Phillips, H. Neth, J. K. Woike, and W. Gaissmaier, “FFTrees: A toolbox to create, visualize, and evaluate fast-and-frugal decision trees,” _Judgment and Decision Making_ , vol. 12, no. 4, pp. 344–368, 2017.
  * [11] G. Gigerenzer, “Why heuristics work,” _Perspectives on psychological science_ , vol. 3, no. 1, pp. 20–29, 2008.
  * [12] G. Gigerenzer and W. Gaissmaier, “Heuristic decision making,” _Annual review of psychology_ , vol. 62, pp. 451–482, 2011.
  * [13] J. Czerlinski, G. Gigerenzer, and D. G. Goldstein, “How good are simple heuristics?” in _Simple Heuristics That Make Us Smart_. Oxford University Press, 1999.
  * [14] S. Wiedenbeck, V. Fix, and J. Scholtz, “Characteristics of the mental representations of novice and expert programmers: an empirical study,” _International Journal of Man-Machine Studies_ , vol. 39, no. 5, pp. 793–812, 1993.
  * [15] M. T. Ribeiro, S. Singh, and C. Guestrin, “” why should i trust you?” explaining the predictions of any classifier,” in _KDD’16_ , 2016, pp. 1135–1144.
  * [16] S. M. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” in _Advances in Neural Information Processing Systems 30_. Curran Associates, Inc., 2017, pp. 4765–4774.
  * [17] K. Peng, C. Kaltenecker, N. Siegmund, S. Apel, and T. Menzies, “Veer: Disagreement-free multi-objective configuration,” in _Submitted to ASE’21_ , 2021.
  * [18] M. J. Druzdzel, “Some properties of joint probability distributions,” in _Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994)_ , 1994\.
  * [19] Q. Zhang, J. Wang, M. A. Gulzar, R. Padhye, and M. Kim, “Bigfuzz: Efficient fuzz testing for data analytics using framework abstraction,” in _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2020, pp. 722–733.
  * [20] Z. Yu, C. Theisen, L. Williams, and T. Menzies, “Improving vulnerability inspection efficiency using active learning,” _IEEE Transactions on Software Engineering_ , pp. 1–1, 2019.
  * [21] H. Tu, Z. Yu, and T. Menzies, “Better data labelling with emblem (and how that impacts defect prediction),” _IEEE Transactions on Software Engineering_ , pp. 1–1, 2020.
  * [22] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” _IEEE Transactions on Evolutionary Computation_ , vol. 6, no. 2, pp. 182–197, 2002.
  * [23] T. Menzies, “Shockingly simple:”keys” for better ai for se,” _IEEE Software_ , vol. 38, no. 02, pp. 114–118, mar 2021.
  * [24] A. Hindle, E. T. Barr, M. Gabel, Z. Su, and P. Devanbu, “On the naturalness of software,” _Commun. ACM_ , vol. 59, no. 5, p. 122–131, Apr. 2016. [Online]. Available: https://doi.org/10.1145/2902362
  * [25] Z. Lin and J. Whitehead, “Why power laws? an explanation from fine-grained code changes,” in _Proceedings of the 12th Working Conference on Mining Software Repositories_ , ser. MSR ’15. IEEE Press, 2015, p. 68–75.
  * [26] W. Stallings, _Computer Organization and Architecture: Designing for Performance_ , 8th ed. USA: Prentice Hall Press, 2009.
  * [27] M. Lumpe, R. Vasa, T. Menzies, R. Rush, and B. Turhan, “Learning better inspection optimization policies,” _International Journal of Software Engineering and Knowledge Engineering_ , vol. 22, no. 05, pp. 621–644, 2012.
  * [28] T. J. Ostrand, E. J. Weyuker, and R. M. Bell, “Where the bugs are,” in _ISSTA ’04: Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis_. New York, NY, USA: ACM, 2004, pp. 86–96.
  * [29] M. Hamill and K. Goseva-Popstojanova, “Common trends in software fault and failure data,” _IEEE Trans. Softw. Eng._ , vol. 35, no. 4, p. 484–496, Jul. 2009. [Online]. Available: https://doi.org/10.1109/TSE.2009.3
  * [30] K. Peng and T. Menzies, “Defect reduction planning (using timelime),” _IEEE Transactions on Software Engineering_ , 2021.
  * [31] R. Krishna and T. Menzies, “Learning actionable analytics from multiple software projects,” _Empirical Software Engineering_ , vol. 25, no. 5, pp. 3468–3500, 2020.
  * [32] I. H. Witten and E. Frank, “Data mining: Practical machine learning tools and techniques with java implementations,” _SIGMOD Rec._ , vol. 31, no. 1, pp. 76–77, Mar. 2002. [Online]. Available: http://doi.acm.org/10.1145/507338.507355
  * [33] A. Lustosa and T. Menzies, “Preference discovery in large product lines,” 2021\.
  * [34] J. Chakraborty, K. Peng, and T. Menzies, “Making fair ml software using trustworthy explanation,” in _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2020, pp. 1229–1233.
  * [35] B. Johnson, J. Bartola, R. Angell, K. Keith, S. Witty, S. J. Giguere, and Y. Brun, “Fairkit, fairkit, on the wall, who’s the fairest of them all? supporting data scientists in training fair models,” 2020.
  * [36] F. Peters, T. Menzies, and L. Layman, “Lace2: Better privacy-preserving data sharing for cross project defect prediction,” in _2015 IEEE/ACM 37th IEEE International Conference on Software Engineering_ , vol. 1. IEEE, 2015, pp. 801–811.
  * [37] V. Papakroni, “Data carving: Identifying and removing irrelevancies in the data,” 2013. [Online]. Available: https://doi.org/10.33915/etd.3399
  * [38] R. C. Holte, “Very simple classification rules perform well on most commonly used datasets,” in _Machine Learning_ , 1993, pp. 63–91.
  * [39] V. Chandola, A. Banerjee, and V. Kumar, “Anomaly detection: A survey,” _ACM computing surveys (CSUR)_ , vol. 41, no. 3, pp. 1–58, 2009.
  * [40] H. Kautz and B. Selman, “Pushing the envelope: Planning, propositional logic, and stochastic search,” in _Proceedings of the Thirteenth National Conference on Artificial Intelligence - Volume 2_ , ser. AAAI’96. AAAI Press, 1996, p. 1194–1201.
  * [41] K. Zhao, Z. Xu, M. Yan, T. Zhang, D. Yang, and W. Li, “A comprehensive investigation of the impact of feature selection techniques on crashing fault residence prediction models,” _Information and Software Technology_ , vol. 139, p. 106652, 2021.
  * [42] M. A. Hall and G. Holmes, “Benchmarking attribute selection techniques for discrete class data mining,” _IEEE Transactions on Knowledge and Data engineering_ , vol. 15, no. 6, pp. 1437–1447, 2003.
  * [43] J. Chen, V. Nair, R. Krishna, and T. Menzies, ““Sampling”’ as a Baseline Optimizer for Search-based Software Engineering,” _arXiv e-prints_ , p. arXiv:1608.07617, Aug. 2016.
  * [44] J. Bergstra, D. Yamins, and D. D. Cox, “Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures,” in _ICML’13_ , ser. ICML’13. JMLR.org, 2013, p. I–115–I–123.
  * [45] J. Nam and S. Kim, “Clami: Defect prediction on unlabeled datasets (t),” in _2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2015, pp. 452–463.
  * [46] M. Harman and B. F. Jones, “Search-based software engineering,” _Information and software Technology_ , vol. 43, no. 14, pp. 833–839, 2001\.
  * [47] V. Veerappa and E. Letier, “Understanding clusters of optimal solutions in multi-objective decision problems,” in _2011 IEEE 19Th international requirements engineering conference_. IEEE, 2011, pp. 89–98.
  * [48] V. Nair, T. Menzies, N. Siegmund, and S. Apel, “Faster discovery of faster system configurations with spectral learning,” _Automated Software Engineering_ , vol. 25, no. 2, pp. 247–277, 2018.

## Appendix: Research Directions

Looking though the above, we can see numerous possibilities for future work.
Some issues relate directly to keys, while others relate more to issues with
as human cognitive and, incremental knowledge acquisition.

RQ0) How to evaluate “explanation?” Many of the following will need a way to
rank different explanation methods. Hence, our first research question is how
to certify an explanation evaluation rig. If we say that a “useful”
explanation means we know how to better build a model, then Figure 3 can be
used for that ranking purpose. Specifically, explainer1 is better than
explainer2 if more goals are achieved after making fewer decisions.

For that evaluation, there are several cases. Case1: If the $y$ axis of Figure
3 comes from some model, then the $y$ values can be scored via rerunning the
model with new constraints learned from the explanation algorithm. Case2: If
there is no model, and the $y$ values from some historical record of a
project, then that data should be divided using time stamps into before and
after data. The after data could be sorted according to its overlap with the
recommendations generated from explanations built from the before data.
Explainer1 is better than explainer2 if the after data with highest overlap is
somehow better (e.g. fewer software defects) than the rest.

RQ1) Can we build a keys detector? Research directions for such a detector
including the following. Firstly, keys could be detected if, after applying
feature and instance selection, the reduced data space generates models that
perform as well as using all the data. For a discussion on this approach, see
Papakroni, Peters et al. [36, 37].

Secondly, run some very simple and very fast data miners run over the data
building models using $N$ or $2N$ features. If any learner does no better than
another, but using only half the features, then kill the larger learner and
start a new learner that uses half the features of the smaller learner. Keys
would be defected if the final $N$ value is much smaller than the total number
of features. For a discussion on this approach, see [38].

Thirdly, researchers could (a) take some well-explore SE domain; then (b)
commission the prior state-of-the-art (SOTA) method known for that domain;
then (c) compare results from (say) KEYS0 and the SOTA; then (d) declare that
this domain has a keys effect if KEYS0 can control that domain using far fewer
features than the SOTA. Note that, of the three approaches to RQ1 listed here,
this third proposal would be the most labor intensive.

RQ2) What is the generality of keys effect? If we have an automatic method for
determining if a data set is amenable to keys, then we need to run that
detector on as many data sets as possible in order to learn the extent of the
keys effect.

RQ3) Where do keys come from? Another way to assess the generality of the keys
effect would be to understand what causes them. If we knew that, then we could
apply the methods of this paper whenever we see those causative factors. In
§V, it was speculated that power laws within programmer teams lead to keys. To
test that theory we could (e.g.) built defect predictors from projects that
evolved from small single person into large teams. If power laws cause keys,
then we would predict that algorithms like KEYS0 would be less/more effective
earlier/later in that project life cycle (respectively).

RQ4) How does keys compare to other explanation algorithms? §I and §II
depreciated standard explanation algorithms like FFTtrees [10], LIME [15], and
SHAP [16] arguing that they could only handle single goals and (in the case of
LIME and SHAP) only commented on the effects of single variables on the goal.
It is hence appropriate to check what is lost if we move from multiple
multiple variable multi-goal reasoning (with KEYS0) to single variable and
single-goal reasoning (with the other approaches). If we re-run examples like
§IV, and the net gain with KEYS0 over these other algorithms is minimal, and
those other approaches produced very small models, then that would challenge
the motivation for this work.

RQ5) Can keys simplify prior results? In the above, we speculated that the
incremental active learning work of Yu,Tu et al. [20, 21] could be simplified
via keys. This conjecture needs to be checked.

Another example of prior work that might be helped by keys is incremental
anomaly detection. Figure 3 proposed an incremental knowledge capture approach
to system construction. In such an approach, it is useful to have anomaly
detectors that understand when old ideas have become out-dated, or when new
data is “out-of-scope” of the previously generated model. There are many ways
to generate anomaly detectors [39] and we conjecture that a succinct keys-
based summary of past data might make it easier to determine when new data is
anomalous.

RQ6) What are the best algorithms for finding keys? The KEYS0 algorithm
described above in §IV is very simple, possibly even simplistic. Hence, it is
worthwhile consider different ways to code that algorithm.

The KEYS0 algorithm described above is a greedy search in that it prunes half
the data at each level of its recursive search. Lustosa et al. [33] prefers
instead a global analysis where the whole cluster tree is generated, after
which time the algorithm hunts around all nodes looking for things to prune
and things to keep. Greedy algorithms run faster but global algorithms use
more information about the data. Which works best? Or is there some way to
amalgamate the two approaches (e.g. some local search in the style of
MaxWalkSat [40])?

Also, KEYS0 cluster the data via hierarchical random projects. There are so
many other ways to cluster data (e.g. see https://scikit-
learn.org/stable/modules/clustering.html) that it would be useful to explore
other methods. For example if the data is particularly complex, is there are
any role for other algorithms such as a neural autoencoder? More generally,
can we refactor the code in steps1,2,3,4,5 into some object-oriented design
with abstract super-classes like “cluster” and concrete sub-classes for
different (e.g.) clustering algorithms? Such a refactoring would turn the
above code into a workbench within which multiple algorithms could be mixed
and matched in an effort to find better explanation algorithms.

No matter how the clusters are generated, some report must be made to the user
about the different between the clusters (this different was reported in §IV
as the constraints “cylinders $\leq$ 4” and “origin==”). KEYS0 uses a simple
greedy frequency-based method (combine adjacent ranges that have similar
best,rest frequencies; tank feature ranges, favoring those that are more
frequent in best than rest; print the top-ranked range) and there are so many
other feature and range ranking methods to try [41, 42]

For simple data sets like the auto93 data set explored in §IV, only 2
constraints are generated before the algorithm cannot find anything else of
interest. Lustosa et al. [33] reports studies in larger data sets (with 128
features) where his keys finder returns very many constraints. Is there an
early stopping rule that can be applied to find enough useful constraints, but
no more?

It is interesting to compare KEYS0 with genetic algorithms (GAs). GAs mutates
a population of, say, 100 individuals across many generations. Each generation
applies some select operator (to remove worse individuals) then combines the
survivors to create the next generation. KEYS0, on the other hand, applies its
select opertor to a much larger initial population, after which it does no
mutation (hence, no generation $i+1$). Prior results by Chen et al. [43]
suggested that this over-generate-population0 can do as well, or better, than
multi-generation mutation (also, his approach is much faster than evolutionary
methods). But evolutionary programming is a rapidly progressing field. Hence,
it would be wise to recheck Chen’s conclusions against (e.g.) Hyperopt [44].

RQ6) What is the impact of user mistakes? One cognitive issue wit the current
KEYS systems is that humans make many mistakes. What happens to Figure 1 if
humans make a wrong decision along the y-axis? How do we detect that mistake?
For example, would some unsupervised outlier detection [45] suffice? And how
do we repair those mistakes (Yu et al. have some preliminary ideas on that
[20]).

Another cognitive issue is that humans have different world views. Hence,
reasoning about teams is very different to reasoning about one or two people.
In the studies mentioned above regarding integration with human agency, Yu, Tu
et al. worked mostly with one or two oracles [20, 21]. How their methods scale
to teams? Within the space of possible explanations, would we need to (e.g.)
add in some multi-goal reasoning [46] so that we can appease the most number
of competing goals as possible? On the other hand, rather than seek
appeasement, it is better to report separate sets of conclusions where each
set satisfies a different set of goals (e.g. see the Pareto clusters in Figure
5 of [47])?

RQ7) Can visualizations replace rules? One of the more interesting results of
Lustosa et al. [33] is that large data spaces can be explored with reference
to just a few ranges from a few features. Given that, can we offer users
succinct visualizations of the data showing just the frequency counts of those
ranges? And if users examined that space, would they find their own plans for
controlling the data? And would those plans work better than the plans
generate via pure algorithmic means by Lustosa et al. [33]?

RQ8) How to maintain privacy and accountability? In the above, it was proposed
to cache the rig of Figure 1, then re-run it for accountability purposes. This
raises two data management systems issues. Firstly, if we retain some or all
the data of Figure 1, do we need some (e.g.) mutation policy to reduce the
probability of identify disclosure within that data? [36]? Secondly, how much
past data do we need to keep in order to support future accountability? If we
must keep all the past data then that could become a significant data storage
issue. On the other hand, recalling Steps 1,2,3,4,5, would it suffice to just
keep the distant points $P_{1},P_{2}$ found at each level of the recursion? Or
is the best data retention policy somewhere in-between? (Aside: see Nair and
Peters et al. [48, 36] for different proposals on selecting the most
informative prior data).