Evolution and impact of bias in human and machine learning algorithm interaction — TEI-tagged view

Wenlong SunpersName, Olfa NasraouipersName, Patrick ShaftopersName (2020date). “Evolution and impact of bias in human and machine learning algorithm interaction.” PLOS ONEtitle·j.

Object of study — biasterm·def emerging through repeated feedback between human choices and machine-learning selection mechanismsterm·var

Research question — how filtering, active learningterm, initial imbalance, and human action change learned boundaries, inequality, and discoverability over iterations

Contribution — a dynamic iterated-learning framework and a blind-spot metric for sociotechnical human-algorithm biasterm·def

Full text — tagged

Evolution and impact of biasterm·def in human and machine learning algorithm interaction Abstract Traditionally, machine learning algorithms relied on reliable labels from experts to build predictions. More recently however, algorithms have been receiving data from the general population in the form of labeling, annotations, etc. The result is that algorithms are subject to biasterm·def that is born from ingesting unchecked information, such as biased samples and biased labels. Furthermore, people and algorithms are increasingly engaged in interactive processes wherein neither the human nor the algorithms receive unbiased data. Algorithms can also make biased predictions, leading to what is now known as algorithmic biasterm·def. On the other hand, human’s reaction to the output of machine learning methods with algorithmic biasterm·def worsen the situations by making decision based on biased information, which will probably be consumed by algorithms later. Some recent research has focused on the ethical and moral implication of machine learning algorithmic biasterm·def on society. However, most research has so far treated algorithmic biasterm·def as a static factor, which fails to capture the dynamic and iterative properties of biasterm·def. We argue that algorithmic biasterm·def interacts with humans in an iterative manner, which has a long-term effect on algorithms’ performance. For this purpose, we present an iterated-learning framework that is inspired from human language evolution to study the interaction between machine learning algorithms and humans. Our goal is to study two sources of biasterm·def that interact: the process by which people select information to label (human action); and the process by which an algorithm selects the subset of information to present to people (iterated algorithmic biasterm mode). We investigate three forms of iterated algorithmic biasterm (personalization filter, active learningterm, and random) and how they affect the performance of machine learning algorithms by formulating research questions about the impact of each type of biasterm·def. Based on statistical analyses of the results of several controlled experiments, we found that the three different iterated biasterm·def modes, as well as initial training data class imbalance and human action, do affect the models learned by machine learning algorithms. We also found that iterated filter biasterm, which is prominent in personalized user interfaces, can lead to more inequality in estimated relevance and to a limited human ability to discover relevant data. Our findings indicate that the relevance blind spotterm (items from the testing set whose predicted relevance probability is less than 0.5 and who thus risk being hidden from humans) amounted to 4% of all relevant items when using a content-based filter that predicts relevant items. A similar simulationterm·mth using a real-life rating data set found that the same filter resulted in a blind spotterm size of 75% of the relevant testing set.

Introduction Websites and online services offer large amounts of information, products, and choices. This information is only useful to the extent that people can find what they are interested in. All existing approaches aid people by suppressing information that is determined to be disliked or not relevant. Thus, all of these methods, by gating access to information, have potentially profound implications for what information people can and cannot find, and thus what they see, purchase, and learn. There are two major adaptive paradigms to help sift through information: information retrieval and recommender systems. Information retrieval techniques [ 1 – 9 ] have given rise to the modern search engines which return relevant results, following a user’s explicit query. For instance, in the probabilistic retrieval model [ 2 ], optimal retrieval is obtained when search results are ranked according to their relevance probabilities. Recommender systems, on the other hand, generally do not await an explicit query to provide results [ 10 – 17 ]. Recommender systems can be divided based on which data they use and how they predict user ratings. The first type is content-based filtering (CBF) algorithms [ 12 , 18 – 24 ]. It relies on item attributes or user demographics, but often not relations between users (i.e. social relations), as data. Collaborative Filtering (CF) [ 10 , 17 , 25 – 30 ], on the other hand, does not require item attributes or user attributes. Rather it makes predictions about what a user would like based on what other similar users liked. Both adopt algorithms, e.g. K-nearest neighbors [ 31 , 32 ] and non-negative matrix factorization (NMF) [ 33 – 37 ], that have close analogs in the psychology literatures on concept learning, e.g. exemplar models [ 38 – 40 ] and probabilistic topic models [ 41 , 42 ].

Information filtering algorithms [ 11 , 43 – 45 ] similarly provide users with a list of relevant results, but do so in response to a query. One classic example is the Rocchio filter [ 46 – 48 ], which modifies the user’s initial query after a first iteration of search to help filter less relevant results. The query is modified based on the set of initial search result documents which are labeled by the user as relevant and non-relevant, respectively. The new query (which is treated like a pseudo-document) is modified by adding and subtracting a weighted combination of relevant and non-relevant documents, respectively. This is quite similar to content-based recommendation, where information about the items is used to rank potentially relevant results.

Common to both recommender systems and information filters is: (1) selection, of a subset of data about which people express their preference, by a process that is not random sampling, and (2) an iterative learning process in which people’s responses to the selected subset are used to train the algorithm for subsequent iterations. The data used to train and optimize performance of these systems are based on human actions. Thus, data that are observed and omitted are not randomly selected, but are the consequences of people’s choices. Recommendation systems suggest items predicted to be of interest to a user (e.g. movies, books, news) based on their user profile [ 12 , 13 , 26 ]. The prediction can be based on people’s explicit (e.g. ratings) or implicit (e.g. their browsing or purchase history) data [ 49 – 54 ], or even query patterns [ 55 ]. Research into human choice suggests that both explicit and implicit choices systematically vary based on context, especially the other options that are present when choosing [ 56 – 59 ].

In addition to the simple effects of the interaction between algorithms’ recommendations and people’s choices, people may reason about the processes that underlie the algorithms. Research in cognitive science has shown that people reason about evidence selected by other people. In [ 60 ], a computational framework was proposed for modeling how people’s inferences may change as a consequence of reasoning about why data were selected. This framework has been formalized in learning from helpful and knowledgeable teachers [ 61 – 64 ], deceptive informants [ 65 ], and epistemic trust [ 66 – 68 ]. People’s reasoning about the intentional nature of the algorithms may exacerbate the effects of cyclic interaction between the algorithms’ recommendations and people’s choices.

We propose a framework for investigating the implications of interactions between human and algorithms, that draws on diverse literature to provide algorithmic, mathematical, computational, and behavioral tools for investigating human-algorithm interaction. Our approach draws on foundational algorithms for selecting and filtering of data from computer science, while also adapting mathematical methods from the study of cultural evolution [ 69 – 71 ] to formalize the implications of iterative interactions.

In our approach, we focus on the primary sources and consequences of biasterm·def in collected data. The primary sources of biasterm·def come from algorithms and humans. Algorithms, such as recommender systems, filter information in order to present humans with preferred content. After receiving more labels from humans, machine learning algorithms are trained to predict future recommendations. Unlike standard learning theory, the training data are no longer randomly sampled. This in return puts in questions the guarantees about learning from such data. The second source of biasterm·def comes from humans. In addition to receiving iterated information optimized to their preferences, humans are not required to provide labels for the presented data. Humans’ choices, when labelling data, are also highly non-random, and would reflect not only their opinions about the presented content, but also inferences about why the content was presented. Finally, the biasterm·def that is introduced into the data at any point can be amplified after retraining models and this in turn would further impact the predictions or recommendations. Either of the individual sources of biasterm·def could yield instability, thus motivating the need for a better understanding of the performance of such systems in the context of human-algorithm interactions. Specifically, there is a need for a better understanding of the conditions under which we can expect the emergence of systematic biasterm·def in the selection of information by algorithms, and for the identification of the conditions under which we can “undo” the effects of these biasesterm·def to obtain accurate estimates from biased data. We expect the findings to contribute insights back to the fundamental psychology of human reasoning, choice and learning and to the fundamental computer science of learning, recommendation and information filtering.

Related work Iterated learningterm and language evolution In language learning, humans form their own mapping rules after listening to others, and then speak the language following the rules they learned, which will affect the next learner. Language learning and machine learning have several properties in common (see Fig 1 ). For example, a ‘hypothesis’ in language is analogous to a ‘model’ in machine learning. Learning a language which gets transmitted throughout consecutive generations of humans is analogous to learning an online model throughout consecutive iterations of machine learning [ 69 ].

Language learning vs. machine learning. Language learning is analogous to machine learning in several aspects, such as ‘hypothesis’ to ‘model’ in sub-figure (a). Learning a language which gets transmitted throughout consecutive generations of human speakers is analogous to learning a model through consecutive iterations of online machine learning in sub-figure (b). In the iterative human-machine learning algorithm interaction, the output from ML affects human behavior and human also interact with the output which affects next iteration.

More specifically, we point to the work of Griffith [ 69 ] because it was the first work that showed formally, through a Markov chain mathematical framework how the iterated learningterm within a language learning scenario converges to the prior in the absence of a dependence between the previous iteration’s output and the next iteration’s input.

Although the work of Griffith is situated within the context of language evolution, or more specifically in the context of human learning of language throughout several generations, it is “analogous”, in the sense of information flow and adaptation (and not the actual application domain), to the problem of supervised machine learning, where a model (instead of language) is learned iteratively throughout several iterations (instead of generations).

Thus we consider language evolution more as an “analogous”, rather than a “similar” setting to the iterated machine learning in this paper. We further extend the derivations from Griffith et al. [ 69 ] derivations which have been done within a language learning framework, to the realistic framework of dependent interactions between a model and a human in an iterated learningterm setting, which is the setting for this paper. More specifically in our setting, there is a dependency between the previous output and the next input, and it is this dependency that can generate iterated biasterm·def.

Iterated learningterm was found to produce meaningful structure patterns in language learning [ 72 – 76 ]. Language evolution can be modeled as a Markov chain, as shown in Fig 2(A) . The first learner is exposed to linguistic data and forms an initial hypothesis, before producing their own data, that will serve as the input to the next learner. After sufficient iterations, this process generates a certain hypothesis. This iterated learningterm chain is expected to converge the hypothesis to the prior distribution of all hypotheses in case that the learner is a Bayesian learner [ 69 ]. What this means is that the knowledge learned is not accumulated during the whole process. We refer to this iterated learningterm model as pure iterated learningterm (PIL) . One problem about this iterated language learning model is the difficulty to prove the convergence or the boundary practically, even if it is proved theoretically [ 74 ]. Rafferty et al. gave an upper bound for the convergence, which is nlog ( n ) iterations for Bayesian learning of the ranking of n constraints or the n binary parameters values [ 77 ].

Markov chains for iterated learningterm with (bottom) and without (top) dependency from previous iterations.

Perfors et al. showed that, when certain assumptions about the independence of language and the world are abandoned, the learners converge to languages that depend on the structure as well as their prior biasesterm·def [ 78 ]. In Fig 2(A) , there is no dependency between current input x and the previous learned hypothesis, which represents the graphic model of PIL. While in Fig 2(B) , current input data x has dependency on the previous hypothesis, which in the modern world is more realistic.

While iterated learningterm ensembles the online learning process [ 79 ], they differ in several ways. Online learning occurs in a consecutive manner, with the learner providing an answer to a given question in each round. The learner answers the questions using a prediction model or hypothesis, that maps from sets of questions to the set of answers. After prediction, the quality is measured based on the true answers. The goal is to minimize the cumulative loss in the online learning process [ 80 ]. Meanwhile, in iterated learningterm, we are interested in investigating the given information’s effect on the learned hypothesis.

Relationship between iterated learningterm and information retrieval It is interesting to recognize how Iterated Learningterm manifests itself in the context of adaptive information filters, as exemplified by modern search engines. Based on information retrieval, modern search engines return relevant results, following a user’s explicit query [ 7 ]. For instance, in the probabilistic retrieval model, optimal retrieval is obtained when search results are ranked according to their relevance probabilities [ 2 ]. Recommender systems, on the other hand, generally do not await an explicit query to provide results [ 16 ]. Both Information retrieval and recommender system, to some extent, require information selection to get better results, thus iterated interactive learning naturally fits the purpose of studying the interaction of algorithms and humans.

Relationship between iterated algorithmic biasterm and other types of biasterm·def In statistics, biasterm·def refers to the systematic distortion of a statistic. Here we can distinguish a biased sample, which means a sample that is incorrectly assumed to be a random sample of a population, and estimator biasterm·def, which results from an estimator whose expectation differs from the true value of the parameter [ 81 ]. Within our scope, biasterm·def is closer to the sample biasterm·def and estimator biasterm·def from statistics; however, we are interested in what we call ‘iterated algorithmic biasterm‘ which is the dynamic biasterm·def that occurs during the selection by machine learning algorithms of data to show to the user to request labels in order to construct more training data, and subsequently update their prediction model, and how this biasterm·def affects the learned (or estimated) model in successive iterations.

Algorithmic biasterm·def can be categorized based on the time in which it occurs during the machine learning process [ 95 ]. Generally, selecting biased training samples leads to a biased model [ 96 ]. Training data biasterm·def may come from various sources which depend on the application, such as human labeling, sample selection and others. Several machine learning techniques have been proposed to deal with this problem [ 87 – 94 ]. The post-algorithmic biasterm·def emerges when users interpret the output of machine learning algorithms [ 97 – 100 ]. Table 1 lists several common biasesterm·def and compares them with our iterated algorithmic biasterm based on several properties.

Different biasterm·def types studied in recent research. Iterated algorithmic biasterm happens when an algorithm interacts with human response continuously, and updates its model after receiving feedback from the human. Meanwhile, the algorithm interacts with the human by showing only selected items or options. Other types of biasterm·def are static, which means they have a one-time influence on an algorithm.

Recent research pointed to the need to pay attention to biasterm·def and fairness in machine learning [ 101 – 105 ]. Some research has studied different forms of biasesterm·def, some are due to the algorithms while others are due to inherent biasesterm·def in the input data or in the interaction between data and algorithms [ 85 , 97 , 106 – 113 ]. Some research on algorithmic biasterm·def has focused on the ethical problems that machine learning algorithms might create [ 82 – 86 , 114 – 116 ]. For instance, Zook et al. [ 82 ] have recently argued that researchers must carefully check the impact of algorithms on specific groups of people (such as defined by gender and race) before deploying algorithms. Kirkpatrick [ 83 ] illustrated the ethical problems that can occur when algorithmic biasterm·def is introduced in the justice system. Garcia [ 85 ] stated that algorithmic biasterm·def may worsen racist biasterm·def in certain circumstances. More recently, Kate Crawford’s presentation related to research on the fairness of machine learning algorithms attracted more attention from the machine learning community on the problem of algorithmic biasterm·def [ 82 ]. Some work studied biasesterm·def emerging due to item popularity [ 117 – 120 ]. A recent work studied biasterm·def that is due to the assimilation biasterm·def in recommender systems [ 121 ]. Because recommender systems have a direct impact on humans, some recent research studied the impact of polarization on biasing rating data [ 122 , 123 ] and proposed strategies to mitigate this polarization in collaborative filtering recommender systems [ 124 ], while other recent research pointed to biasterm·def emerging from continuous feedback loops between recommender systems and humans [ 125 – 128 ]. Overall, the study of algorithmic biasterm·def falls under the umbrella of fair machine learning [ 129 ].

Similar research has been conducted about how model updates in machine learning algorithms affect fairness. Sinha et al. aimed to understand how the feedback loop in recommender systems affects the entire rating matrix, and developed an algorithm to deconvolve the feedback loop with multiple assumptions [ 130 ]. Patro et al. proposed an ILP (Integer Linear Programming Problem)-based online optimization to deploy changes incrementally in multiple steps of recommendation so that the transition is smooth, and leads to an efficient and fair recommendation for both the producers and the customers in two-sided platforms [ 131 ]. Milano et al. focused on ethics problems within recommender systems updates, which results from how humans react to the output of recommender systems [ 132 ]. However, our paper focuses on the interaction between algorithms and humans, and how this interaction impacts humans’ ability to see(or discover) relevant items and how this in turn impacts the algorithms’ performance, rather than proposing a cure.

Taking all the above in consideration, we observe that most previous research has treated algorithmic biasterm·def as a static factor, which fails to capture the iterative nature of biasterm·def that is borne from continuous interaction between humans and algorithms. We argue that algorithmic biasterm·def evolves with human interaction in an iterative manner, which may have a long-term effect on algorithm performance and humans’ discovery and learning.

In this study, we focus on simulating how the data that is selected to be presented to humans affects the algorithm’s performance and how human choice of action (specifically, to label or not to label the selected instance(s), that are presented to them by the algorithm), may in turn affect the algorithm’s performance (see Fig 3 ). In this work, we choose recommendation systems as the machine learning algorithm to be studied. One reason is that recommendation systems have more direct interaction options with humans, while information retrieval focuses on getting relevant information only. We further simplify the recommendation problem into a 2-class classification problem, e.g. like/relevant (class 1) or dislike/non-relevant (class 0), thus focusing on a personalized content-based filtering recommendation algorithm.

Evolution of biasterm·def between algorithm and human. In sub-figure (a), biased data from a human may lead to a biased algorithm, this is pre-algorithmic biasterm·def. In sub-figure (b), a biased algorithmic output might affect human behavior: For instance, by hiding certain items from humans, algorithms may affect human discovery, learning, and awareness in the long term. Sub-figure (c) indicates a continuous interaction between humans and algorithms that generates biasterm·def that we refer to as iterated biasterm·def , namely biasterm·def that results from repeated interaction between humans and algorithms .

Iterated algorithmic biasterm in online learning Because we are interested in studying the interaction between machine learning algorithms and humans, we adopt an efficient way to observe the effect from both sides by using iterated interaction between algorithm and human action. Researchers from behavioral science have developed frameworks for investigating the effect of iterative interactions [ 69 ]. It is known that iterated interaction can be considered to generate Markov chains in the long-run, which gives us a well-formed framework to analyze the asymptotic effects of local decision [ 72 , 74 ]. As stated before, we consider a simplified recommendation problem consisting of a 2-class classification problem. Thus we start with simple supervised machine learning to predict the ‘relevance’ class label of an item for a single user.

To begin, we consider three possible mechanisms for selecting information to present to users: Random, Active-bias, and Filter-bias . These three mechanisms simulate different regimes. Random selectionterm is unbiased and used here purely as baseline for no filtering. Active-bias selection introduces a biasterm·def whose goal is to accurately predict user’s preferences. Filter-bias selection brings a biasterm·def whose goal is to provide relevant information or preferred items.

Before we go into the three forms of iterated algorithmic biasterm, we first investigate Pure Iterated Learningterm (PIL). We adopt some of the concepts from Griffiths [ 69 ]. Consider a task in which the algorithm learns a mapping from a set of m inputs X = { x 1 , …, x m } to m corresponding outputs { y 1 , …, y m } through a latent hypothesis h . For instance, based on previous purchase or rating data ( x , y ), a recommendation system will collect a new data about purchased item ( x new , y new ) and update its model to recommend more interesting items to users. Here, x represents the algorithm’s selections and y represents people’s responses (e.g. likes/dislikes). Following Griffiths’ model for human learners, we assume a Bayesian model for prediction.

Iterated learningterm with iterated filter-bias dependency The extent of the departure that we propose from a conventional machine learning framework toward a human—machine learning framework, can be measured by the contrast between the evolution of iterated learningterm without and with the added dependency. As shown in Fig 2(a) , without the dependency, the algorithm at step n accepts input point x from a set X , which is generated from a distribution p ( x ) that is independent of all other variables. Notation q ( x ) is used to represent this independence. Specifically, q ( x ) indicates an unbiased sample from the world, and not a selection made by the algorithms. On the other hand, with the dependency as shown in Fig 2(b) , the algorithm, at iteration n , sees input x n which is generated from both the objective distribution q ( x ) and another distribution p seen ( x ) that captures the dependency on the previous hypothesis h n . This in turns implies biasterm·def that con-affect of what can be seen by the user in the future. Thus, the probability of input item x is given by: Recall that the probability of seeing an item is related to its rank in a rating based recommendation system or an optimal probabilistic information filter [ 2 ]. For a rating based recommendation system, the ranking is based on the prediction from the system, or the probability of relevance from prediction. In both situations, the selected data point x is likely to be highly rated or relevant, given h . In most circumstances, the recommendation system has a preferred goal, such as recommending relevant items (with y = 1). Then x will be chosen based on the probability of relevance p ( y = 1| x , h n ), x ∈ X . Assume that we have a candidate pool X at time n (In practice X would be the data points or items that the system can recommend at time n ), then The selection of inputs depends on the hypothesis, and therefore information is not unbiased, p ( x | h n )≠ q ( x ). The derivations of the transition probabilities in Eq 2 will be modified to take into account Eq 1 , and will become Eq 3 can be used to derive the asymptotic behavior of the Markov chain with transition matrix T ( h n +1 ) = p ( h n +1 | h n ), i.e.

Thus, iterated learningterm with filter biasterm converges to a mixture of the prior and the biasterm·def induced by filtering. To illustrate the effects of filter biasterm, we can analyze a simple and most extreme case where the filtering algorithm shows only the most relevant data in the next iteration (e.g. top-1 recommender). Hence Based on Eq 3 , the transition matrix is related to the probability of item x being seen by the user, which is the probability of belonging to class y = 1. The fact that x n t o p maximizes p ( y | x , h ) suggests limitations to the ability to learn from such data. Specifically, the selection of relevant data allows the possibility of learning that an input that is predicted to be relevant is not, but does not allow the possibility of learning that an input that is predicted to be irrelevant is actually relevant. In this sense, selection of evidence based on relevance is related to the confirmation biasterm·def in cognitive science , where learners have been observed to (arguably maladaptively) select data which they believe to be true (i.e. they fail to attempt to falsify their hypotheses) [ 133 ]. Put differently, recommendation algorithms may induce a blind spotterm where data that are potentially important for understanding relevance are never seen .

Iterated learningterm with iterated active-bias dependency Active learningterm was first introduced to reduce the number of labeled samples needed for learning an accurate predictive model, and thus accelerate the speed of learning towards an expected goal [ 134 , 135 ]. Instead of choosing random samples to be manually labeled for the training set, the algorithm can interactively query the user to obtain the desired data sample to be labeled [ 136 ].

where y ^ = arg max y ( p ( y | x , h ) ) . That is, x values are selected to be least certain about y ^ , the predicted y value.

Assuming a simplified algorithm where only the very uncertain data are selected, we can investigate the limiting behavior of an algorithm with the active learningterm biasterm·def. Assuming a mixture of random sampling and active learningterm, we obtain: Where The limiting behavior depends on the iterated active learningterm biasterm·def, x n a c t . This is, in most cases, in opposition to the goal of filtering, the algorithm will only select data point(s) which are closest to the learned model’s boundary, if we are learning a classifier for example. In contrast, the filtering algorithm is almost certain to pick items that it knows are relevant.

This is, of course, consistent with the different goals of recommendation and active learningterm. The analysis illustrates how the long-run implications of these different biasesterm·def may be analyzed: By deriving the transition matrices implied by iterated application of data selection biasesterm·def, we can see that both active learningterm and filtering have different goals, but focus on an ever more extreme (and therefore not representative) subset of data. Similar methods can be applied to more nuanced and interesting biasesterm·def to shed light on the consequences of iterative interactions on the data.

Iterated learningterm with random selectionterm The iterated random selectionterm is considered as baseline for comparison purpose. This selection mechanismterm·var randomly choose instance to pass to next learner during iterations, i.e., the selection of the input x does not depend on the model learned.

Iterated learningterm with human action biasterm The above analysis assumes that people’s response is always observed. In the following, we extend our analysis to the more realistic case where users have a choice of whether to act or not on a given input.

Assume that people have some target hypothesis, h *, which represents optimal performance for the algorithm. Data are composed of an input provided by the algorithm, x , an output, y , and an action, a . The indicator variable a takes a value of 1 when people have provided a response, and a value of 0 when people have not. When the value of y is not observed, it is notated as y = NULL . These form triples d = ( x , y , a )∈{( x 1 , y 1 , a 1 ), …, ( x n , y n , a n )}. The basic inference problem, from one iteration to the next, is then, p ( h t | d ) ∝ p ( d | h t −1 , h *) p ( h t −1 ), where y * represents the output that would be observed, if an action were taken. The main change is in people’s choice of whether to respond, p ( a | y *, x , h *). A missing at random assumption implies that p ( a | y *, x , h *) does not depend on x , y *, or h , thus p ( a | x , y *, h *) = p ( a ). If variables are missing due to a person’s choice, the probability of a missing value almost certainly depends on x , y * and/or h *. We can formalize this choice using Luce choice [ 56 ], a special case of softmax [ 137 ] (Note that both softmax and Luce choice have known issues for modeling human choice [ 56 , 138 ]), where the choice of whether to act depends on the relative utility of acting as opposed to not acting. For example, if it is especially effortful to act, then people will be biased against acting. Alternatively, the utility of acting may depend on the value of y *. For example, it may be that there is greater perceived utility in acting when the value of y * is very low, as in the case of an angry customer or disappointed user. It is interesting to study the effect of biasesterm·def in case of an imbalanced ability in acting as quantified by p ( a = 1 | y * = 1 ) p ( a = 1 | y * = 0 ) , which we call imbalanced human action ratio.

In principle, one might think that this is related to the problem of dealing with missing data that is common in statistics [ 139 ]. Indeed, in our analyses, we showed one special case that reduces to the missing at random typically assumed in statistical applications [ 139 ]. However, the framework proposed here is in fact more general; it proposes a theory of why data are missing, and formalizes the problem as one of understanding human behavior [ 66 , 140 , 141 ].

Evaluating the effect of iterated algorithmic biasterm on learning algorithms In this section, we present the metrics we will use to measure the impact of different biasterm·def types on: (1) The discoverability of items: we define the blind spot metricterm·var for this purpose and this metric is novel; (2) The model: Thus we measure the boundary shiftterm resulting from biasterm·def, which ends up being related to the proportion of items predicted as relevant by the model; (3) The inequality of the relevance predictions: We measure this using a standard metric for this purpose, namely the Gini coefficientterm·var.

Blind spotterm The blind spotterm is defined as the set of data available to a relevance filter algorithm, for which the probability of being seen by the human interacting with the algorithm, that learned the hypothesis h is less than δ : In the real world, some data can be invisible to some users because of biasterm·def either from users or from the algorithm itself. Studying blind spotsterm can enhance our understanding about the impact of algorithmic biasterm·def on humans. In addition, we define the class-1-blind spot or relevant-item-blind spot as the data in the blind spotterm, with true label y = 1 Note that the blind spotterm in Eq 16 is also called all-classes-blind spot .

Boundary shifting Boundary shifting indicates how different forms of iterated algorithmic biasterm affect the model h that is learned by an algorithm. It is defined as the number of points that are predicted to be in class y = 1 given a learned model h : Here b is the number of points that are predicted as class y = 1 given a learned model h .

Gini coefficientterm·var We also conduct a Gini coefficientterm·var analysis on how boundary shiftsterm affect the inequality of predicted relevance for the test set. Let p i = p ( y = 1| x i , h ). For a population with n values p i , i = 1 to n , that are indexed in non-decreasing order ( p ( i ) ≤ p ( i +1) ). The Gini coefficientterm·var can be calculated as follows [ 142 ]: The higher the Gini coefficientterm·var, the more unequal are the frequencies of the different labels. Given that the Gini coefficientterm·var measures the heterogeneity of the distribution of the relevance probabilities, it can be used to gauge the impact of different iterated algorithmic biasterm modes on the heterogeneity of the predicted probability in the relevant class during human-machine learning algorithm interaction.

Research questions The key issue is to show that information filtering may lead to systematic biasesterm·def in the learned model, as captured by the classification boundary. Based on three metrics, we formulate three research questions: (RQ 1) How do different iterated algorithmic biasesterm affect the behavior of models learned by a ML algorithm (with human action probabilityterm·var equal to 1)? We consider three aspects of a learned model to measure the outcome of algorithmic biasterm·def : RQ 1.1) Boundary shiftterm pre and post iteration ( Eq 18 ) ; RQ 1.2) Gini coefficientterm·var of predicted testing set labels ( Eq 19 ) ; RQ 1.3) Blind spotterm size pre and post iteration ( Eq 17 ) .

(RQ 2) How does human action (whether to label data when requested to by the machine learning algorithm) affect the boundary shiftterm? We consider the same three aspects to measure the effects as in RQ 1 .

(RQ 3) Does human preference towards labeling relevant data affect the boundary? We consider the same three aspects to measure the effects as in RQ 1 .

Experimental data sets Our preliminary results are based on both synthetic and real data. As stated in Section Iterated Algorithmic Biasterm in Online Learning 1, we mainly focus on a two-class model of recommendation in order to perform our study. The classes are relevant/non-relevant, or like/dislike. In this situation, any classical supervised classification could be used in our model, such as Bayesian classifier [ 143 ], Logistic regression [ 144 ], Support Vector Machine (SVM) [ 145 ], or Extreme Learning Machine algorithms (ELM) [ 146 , 147 ]. For the purpose of easier interpretation and visualization of the boundary and to more easily integrate with the probabilistic framework in Section Iterated Algorithmic Biasterm in Online Learning 1, we chose the Naive Bayes classifier.

Synthetic data : First, a 2D data set (see Fig 4 ) was generated from two Gaussian distributions corresponding to classes y ∈ {0, 1} for like (relevant) and dislike (non-relevant), respectively. Each class contains 1000 data points centered at {−2, 0} and {2, 0}, with standard deviation σ = 1. The data set is then split into the following parts: Original data with two classes.

Testing set: used as a global testing set (200 points from each class).

Validation set: used for the blind spotterm analysis (200 points from each class).

Initializing set: used to initialize the first boundary (we tested different initializations with class 1/class 0 ratios as follows: 10/100;100/100;100/10).

Candidate set: used as query set of data which will be gradually added to the training set (points besides from the above three groups will be added to the candidate set).

The reason why we need the four subsets is that we are simulating a real scenario with interaction between human and algorithm. Part of this interaction will include picking query data items and labeling them, thus augmenting the training set. Thus, to avoid depleting the testing set, we need to isolate these query items in the separate “candidate pool”. A similar reason motivates the remaining separate subsets in order to keep their size constant throughout all the interactions of module learning.

We are also motivated to run experiments on high dimensional synthetic data set. We thus generate 3D, 4D and 10D synthetic data to study the effects of different iterated algorithmic biasterm in Section 1.

Real-life data set : In addition to synthetic data, we are motivated to use a real data set that expresses likes/dislikes that could be used as a two-category data set similar to the synthetic data set. Here we use the movielens dataset [ 148 ], which contains 100,004 ratings on 9125 movies. These ratings were made by 671 users between January 09, 1995 and October 16, 2016. The latest dataset was generated on October 17, 2016. All 671 users had rated at least 20 movies. The ratings range in [1, 5] and include missing values. This data is a publicly available benchmark data of anonymous user ratings. No identifying demographic information is included. Each user is represented by an artificial id, and no other information is provided. The collection method complied with the terms and conditions of the website here http://files.grouplens.org/datasets/movielens/ml-latest-small-README.html . We discretized the ratings into two labels: the range [1, 3] was mapped to class 0, while (3,5] was mapped to class 1. The item content features were the movie genres. In order to perform similar experiments to the synthetic data simulationsterm·mth, we needed to focus on one user at a time. Thus we selected users who rated the highest number of movies and whose ratings are balanced between the two classes, analogously to our synthetic data. We first selected user ID = 547 to perform our study, then repeated the experiments on 7 more users. User 547 has rated 2312 movies throughout the 10 years. After removing some genres which appear across the movies less than 10 times, we end up with 18 valid genres. We then perform Principal Component Analysis (PCA) to reduce the dimensionality with component cutoff as 0.90 [ 149 ], and ended up with 11 content features. One reason we perform PCA is to be more consistent with the Naive Bayesian assumption that all features are independent.

Methods : The synthetic dataset represents a typical classification problem, it is the same for our real-life dataset after selecting one user and corresponding items. Each dataset contains two ground-truth categories of liked and disliked items. We wish to simulate the human-algorithm interaction at the heart of recommendation and information filtering. To do so, we consider three initialization possibilities: unbiased initialization in which examples are randomly selected from both categories in the same proportion; two types of biased sampling in which the relevant class (class 1) was oversampled by 10:1 or 1:10. Note that for the real-life data set, we only explore the unbiased initialization. We consider three forms of iterated algorithmic biasterm: random selectionterm, active-bias which attempts to learn the true boundary between the two categories, and filter (or recommendation) biasterm·def which attempts to recommend only preferred items (see Section 1). We simulate different types of responses by the user as action probabilities that vary from labeling each item as it is recommended (human action probabilityterm·var of 1), to two cases where the user labels only some of the items provided by the algorithm (human action probabilities of 0.5 and 0.01). Note that absent any additional information, we assume action probabilities to be 1 for the real-life data set. We then simulate runs of 200 iterations where a single iteration consists of the algorithm providing a recommendation, the user labeling (or not) the recommendation, and the algorithm updating its model of the user’s preferences. Each combination of parameters yields a data set that simulates the outcome of the human and algorithm interacting. We simulate this whole process 40 times independently, which generates the data that we will use to investigate the research questions listed in Section Research Questions 1.

Results In this section, we present results using both synthetic and real-life data. We first present results from the 2D synthetic data described in Section Experimental Data Sets 1. We also explore high dimensional synthetic data in Section Experiments on High Dimensional Synthetic Data Set 1. The real-life data set experiments are presented in Section Experimental Data Sets 1. Finally, we summarize the conclusions from all our synthetic data experiments in Table 19 , and from the real-life data experiments in Table 20 .

Summary of research question (RQs) and findings for synthetic data.

Summary of research question (RQs) and findings for real data.

Experiments on 2D synthetic data In this section, we presented results from the 2D synthetic data.

RQ 1: How does iterated algorithmic biasterm affect the learned categories?

To answer this question, we control for human action biasterm by assuming the data are labeled in each iteration, i.e. the probability of action is 1, p action = 1. We adopt four different approaches to investigating this question. First, we will compare the inferred boundaries after interaction to the ground truth boundaries. Second, we will focus on the effects of iteration alone by analyzing the boundary before interaction and after. Third, We use the Gini coefficientterm·var to measure the heterogeneity or inequality of the predicted label distribution in the testing set. Fourth, we investigate the size of the blind spotterm induced by each of the iterated algorithmic biasterm modes. Together, these will describe the outcomes of algorithmic biasterm·def, in terms of how it interacts with initialization, and the consequences of algorithmic biasterm·def in terms of the induced blind spotterm.

RQ 1.1: Do different forms of iterated algorithmic biasterm have different effects on the boundary shiftterm?

To answer this question, we control for human action biasterm by assuming the data are labeled in each iteration i.e. the probability of action is 1. And the initialization is balanced, i.e the ratio = 1:1. As shown in Eq 1 , we here assume that q ( x ) is identical for all data points, thus we can ignore the second part of the equation, i.e. the probability of being seen is only dependent on the predicted probability of candidate points. Note that we could get some prior probability of X i , in which case we could add this parameter to our framework. Here, we assume them to be the same, hence we set ϵ = 0.

We wish to quantify differences in the boundary between the categories as a function of the different algorithm biasesterm·def. To do so, we generate predictions for each test point in the test set by labeling each point based on the category that assigns it highest probability. We investigate the proportion of test points with the relevant label y = 1 at two time points: prior to human-algorithm interactions (immediately after initialization), and after human algorithm interactions.

We run experiments with each of the three forms of algorithm biasterm·def, and compare their effect on boundary shiftterm. We also report the effect size based on Cohen d algorithm [ 150 ]. In this experiment, the effect size (ES) is calculated by ES = ( Boundary t = 0 − Boundary t = 200 )/ standard . dev , here standard . dev is the standard deviation of the combined samples. We will use the same strategy to calculate the effect size in the rest of this paper. The results indicate significant differences for the filter biasterm condition ( p <.001 by Mann-Whitney test or t-test, effect size = 1.96). In contrast, neither the Active Learningterm, nor the Random conditions resulted in statistically significant differences ( p = .15 and.77 by Mann-Whitney test, or p = .84 and 1.0 by t-test; effective sizes.03 and 0.0, respectively).

To illustrate this effect, we plot the number of points assigned to the target category versus ground-truth for each iterations. Fig 5 shows that random selectionterm and active learningterm biasterm·def converge to the ground-truth boundary. Filter biasterm, on the other hand, results in decreasing numbers of points predicted in the target category class 1, consistent with an overly restrictive category boundary.

Boundary shiftterm ( Eq 18 ) based on the three iterated algorithmic biasterm forms. The y axis is the number of testing points which are predicted to be in class y = 1. This figure shows that random selectionterm and active learningterm biasterm·def converge to the ground-truth boundary. Filter biasterm, on the other hand, results in decreasing numbers of points predicted in the target category class 1, consistent with an overly restrictive category boundary.

RQ 1.2: Do different iterated algorithmic biasterm modes lead to different trends in the inequality of predicted relevance throughout the iterative learning, given the same initialization?

In order to answer this question, we run experiments with different forms of iterated algorithmic biasterm, and record the Gini coefficientterm·var when a new model is learned and applied to the testing set during the iterations. We first run the Shapiro-Wilk normality test with all groups [ 151 ]. The p-value for filter biasterm, active learningterm biasterm·def and random selectionterm are 0.91, 0.63 and 0.99 respectively. Therefore, we perform a one-way ANOVA tests [ 152 ].

Although the absolute difference between the first iteration and the last iteration is small (see Fig 6 ), a one-way ANOVA test across these three iterated algorithmic biasterm forms shows that the Gini index values are significantly different. The p-value from the ANOVA test is close to 1.0e-20 (<0.05), which indicates that the three iterated algorithmic biasterm forms have different effects on the Gini coefficientterm·var.

Box-plot of the Gini coefficientterm·var resulting from three forms of iterated algorithmic biasterm. An ANOVA test across these three iterated algorithmic biasterm forms shows that the Gini index values are significantly different. The p-value from the ANOVA test is close to 0.000 (<0.05), which indicates that the three iterated algorithmic biasterm forms have different effects on the Gini coefficientterm·var. Here, FB, AL and RM are the abbreviations of filter biasterm, active learningterm biasterm·def and random selectionterm, respectively. The ‘first’ indicates the beginning of iteration (i.e., t = 0), while the ‘last’ means the end of iteration (i.e., t = 200). Note that we use these abbreviations in the rest of our paper.

Interpretation of this result : Given that the Gini coefficientterm·var measures the inequality or heterogeneity of the distribution of the relevance probabilities, this simulated experiment shows the different impact of different iterated algorithmic biasterm forms on the heterogeneity of the predicted probability to be in the relevant class within human machine learning algorithm interaction. Despite the small effect, the iterated algorithmic biasterm forms affect this distribution in different ways, and iterated filter biasterm causes the largest heterogeneity level as can be seen in Fig 6 .

RQ 1.3: Does iterated algorithmic biasterm affect the size of the class-1-blind spot and the all-classes-blind spot, i.e. is the initial size of the blind spotterm D δ F significantly different compared to its size in the final iteration?

The blind spotterm represents the set of items that are much less likely to be shown to the user. Therefore this research question studies the significant impact of an extreme filtering on the number of items that can be seen or discovered by the user, within human—algorithm interaction. If the size of the blind spotterm is higher, then iterated algorithmic biasterm results in hiding items from the user. In the case of the blind spotterm from class 1, this means that even relevant items are affected .

Recall from section 1 that some of the validation set data points have high probability to be seen, while others have low probability to be seen, the latter make up what we refer to as the blind spotterm. We study how iterated algorithmic biasterm affects the size of the blind spotterm. Here, δ is the threshold on the probability of being seen for an item to be considered in the blind spotterm. Recall that the blind spotterm items from class y = 1 are called relevant item blind spotterm·def or class-1-blind spot and the items from both classes are called all-classes-blind spot .

We run experiments with δ = 0.5 for the class-1-blind spot, and record the size of the class-1-blind spots with three different iterated algorithmic biasterm forms. Here, we aim to check the effect of each iterated algorithmic biasterm form. Filter biasterm has significant effects on the class-1-blind spot, while random selectionterm and active learningterm do not have a significant effect on the class-1-blind spot size (see Fig 7 ). The negative effect from iterated filter biasterm implies a large increase in the class 1 blind spotterm size, effectively hiding a significant number of `relevant' items. Table 2 summarizes the result of the statistical analysis. Note that the effect size is calculated by ES = ( BlindSpot | t =0 − BlindSpot | t =200 )/ standard:dev .

Box-plot of the size of the class-1-blind spot for all three iterated algorithmic biasterm forms. In this figure, the x-axis is the index of the three forms of iterated algorithms biasesterm·def. As shown in this box-plot, the initial class-1-blind spot is centered at 7. This is because the 200 randomly selected initial points from both classes force the boundary to be similar regardless of the randomization.

Results of the Mann-Whitney U test and t-test comparing the size of the class-1-blind spot for the three forms of iterated algorithmic biasterm. Bold means significance at p<0.05. The effect size is ( BlindSpot | t = 0 − BlindSpot | t = 200 )/ standard . dev . The negative effect size shows that filter biasterm increases the class-1-blind spot size. For active learningterm biasterm·def, the p-value indicates the significance, however the effect size is small. Random selectionterm has no significant effect.

We perform a statistical test on the all-classes-blind spot with δ = 0.5. We first run the Shapiro-Wilk normality test. The p-values for the first and last iterations are respectively, 2.74e-7 and 0.037 for filter biasterm; 2.74e-7 and 1 for active learningterm biasterm·def; and 2.74e-7 and 2.9e-11 for random selectionterm. Therefore, we perform a non-parametric statistical test on the pairs of data using the Mann-Whitney U test [ 153 ]. The p-value from the Mann-Whitney U test is close to 0.000 for filter biasterm. The negative effect from iterated filter biasterm implies a large increase in the all-class blind spotterm size, effectively hiding a significant number of ‘relevant’ and irrelevant items (see Table 3 ). For AL, the effect size has the opposite sign (positive) implying a significant decrease in hidden items (both relevant and non-relevant) based on the Mann-Whitney U test. Random selectionterm results in no significant effect on the blind spotterm size.

Results of the Mann-Whitney U test and t-test comparing the size of the all-classes-blind spot for the three forms of iterated algorithmic biasterm. The effect size is conducted as ( BlindSpot | t = 0 − BlindSpot | t = 200 )/ standard . dev . The negative effect size shows that filter biasterm increases the class-1-blind spot size. On the other hand, both active learningterm and random selectionterm have no significant effect.

Interpretation of this result : Given that the blind spotterm represents the items that are much less likely to be shown to the user, this simulated experiment studies the significant impact of an extreme filtering on the number of items that can be seen or discovered by the user, within human-machine interaction. Iterated filter biasterm effectively hides a significant number of ‘relevant’ items that the user misses out on compared to AL. AL has no significant impact on the relevant blind spotterm, but increase the all-class blind spotterm to certain degree. Random selectionterm has no such effect.

However, online systems which have a very wide set of options and where users tend to provide initial ratings for items that they like or see, do suffer from initial class imbalanceterm. Class imbalance can also emerge from the algorithm intentionally asking users to rate only the most popular items, a common strategy used to collect initial ratings for new users. It is also important to notice that in different domains, initialization can have different imbalance patterns. For example in the popular Movielens-100k dataset [ 148 ], around 65% of users have rated more items with ratings higher than their own average rating. A similar phenomenon can be observed in other data sets such as Movielens-1M [ 148 ], Movelens-10M [ 148 ], Netflix Prize challenge dataset [ 154 ], and Book Crossings data set [ 155 ]. There are also users who have rated more items with lower ratings.

Here, we measure how imbalanced initialization affects the algorithm’s performance. We set up three different class imbalance initialization ratios (class0: class1): 1:10, 1:1 and 10:1. Then we compare the learned boundaries with those three ratios. As shown in Fig 8 , highly imbalanced class initialization leads to a bigger difference between the learned boundary and the ground-truth boundary. The ground-truth boundary is obtained from the Gaussian distributions that were used to generate the data points described in Section Experimental Data Sets 1. We also quantify the difference between the learned and true boundaries by measuring how initial boundaries predict the labels on the testing set. The accuracy of the ground-truth boundary and three imbalanced initial boundaries are recorded in Table 4 . We can see that the increase in initialization imbalance ratio leads to lower accuracy on the testing set. Note that accuracies are averaged from 10 independent runs.

Different initialization imbalance ratios affect the starting model boundary ax expected.

Prediction accuracy of different imbalanced initializations ratio (class 1: Class 0) on the testing set and ground-truth boundary.

We wish to understand how imbalanced initialization affects the boundary shifting during the interactive learning process. To answer this question, we run experiments 40 times with the different class imbalanced initialization ratios and record the number of points which cross the boundary during iterative learning as well as the blind spotterm size. We will consider three imbalanced initialization (class 1: class 0) ratios, namely 10:1, 1:1 and 1:10.

We record the number of points whose labels are different between the first iteration and last iterations, with imbalanced initialization ratio set to 10:1, 1:1 and 1:10. We first perform the Shapiro-Wilk normality test with all groups [ 151 ]. The p-value are 0.002, 0.001 and 0.06 for filter biasterm with four ratios; 0.01, 0.0003 and 0.001 for active learningterm biasterm·def; and 0.01, 0.0003 and 0.07 for random selectionterm. Therefore, we perform a non-parametric statistical test using the Kruskal-wallis test [ 40 ] on each form of algorithmic biasterm·def. Fig 9 show the trends of label changes. The Number of label-changed points with ratio = 10:1 is higher than 2 for ratio = 1:1 in the iterated filter biasterm mode, and a similar result can be seen with iterated active learningterm biasterm·def and iterated random selectionterm (see Fig 9 ). The p-values from the Kruskal-wallis test for all three forms of iterated algorithmic biasterm are 5.5e-19 (filter biasterm), 3.27e-17 (active learningterm biasterm·def) and 1.34e-15 (random selectionterm), close to 0.00, which indicates that the class imbalance initialization affects the boundary shiftterm for all three forms of biasterm·def. Also, the higher the class imbalanced initialization ratio, the more boundary shifting, as shown in Fig 9 . On the other hand, the boundary shiftterm of filter biasterm has a big difference when the ratio is 1:10, indicating that filter biasterm has a dramatic impact on the boundary shiftterm when the imbalanced initialization ratio is high and more points are from the irrelevant class.

The box-plots showing the distribution of the number of points that moved across the boundary in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with different class imbalanced initialization ratios. Because the number of points that move across the boundary indicates the intensity of the boundary shiftterm, this shows that for all three iterated algorithmic biasterm modes, a high imbalanced initialization results in a higher boundary shiftterm compared to a balanced initialization.

Interpretation of this result : Given that the number of label-changed points represents the number of items that move across the relevance boundary learned by the machine learning algorithm, this simulated experiment studies the impact of an initial class imbalanceterm (a ratio of 10:1 or 1:10 versus a ratio of 1:1) when an extreme filtering strategy is used within human machine interaction.

In all cases and regardless of whether extreme filtering, AL, or random selectionterm is used to collect feedback from the user, the initial class imbalanceterm has a significant impact on the shift in the learned model’s boundary between relevant and non-relevant items. This test confirms that a more drastic initial class imbalanceterm in the training data has a significant impact on the resulting boundary, and as a result on the judgment of items to be relevant or not by the learned model. Online systems which have a very wide set of options and where users tend to provide initial ratings for items that they like or see, do suffer from initial class imbalanceterm. Class imbalance can also emerge from the algorithm intentionally asking users to rate only the most popular items, a common strategy used to collect initial ratings for new users.

RQ 2: Does human action biasterm affect the boundary?

In order to test how the human reaction affects the boundary shiftterm, we set p action = 1.0, 0.5 and 0.01, and record the results with different iterated algorithmic biasterm modes.

RQ 2.1: Does human action affect the boundary shiftterm during iterative learning given a fixed iterated algorithmic biasterm mode?

We first want to compare the shift in the boundary induced by the different algorithmic biasterm·def forms, alone. We do so by analyzing the change in the boundary, i.e., the number of points in the test set which are predicted to be in class y = 1. We perform the Mann-Whitney U statistical test to see whether the different human action probabilities affect the boundary shiftterm of the learned model for each iterated algorithmic biasterm and three possible human action probabilityterm·var levels. We also record results from the t-test. Effect size is also recorded between any pair of sets of boundary shiftterm from the first iteration and last iteration. Table 5 shows that p action affects the boundary shiftterm more with iterated filter biasterm than with the other two forms of biasterm·def, which support the same conclusion as the previous experiment. The Mann-Whitney U test results agree with the t-test. Thus we conclude that human action affects the boundary shiftterm: the more frequent human action is, the more significant is the effect on the boundary shiftterm for only the iterated filter algorithmic biasterm·def. The other biasterm·def modes are not affected by different human action probabilities. Note that the effect size is calculated by the difference between the boundary of t = 0 and t = 200 divided by the standard deviation.

Results of the Mann-Whitney U test and t-test for the boundary shiftterm of the computed three forms of iterated algorithmic biasterm based on the different probability levels of human action. Here, effect size is ES = ( Boundary | t = 0 − Boundary | t = 200 )/ standard . dev . Bold means the significance at p<0.05. The more the human reacts to the system, the larger is the boundary shiftterm.

In addition, it is interesting to compare the final learned boundaries from the three iterated algorithmic biasterm forms with the ground truth. Therefore, we follow the same procedure as in RQ 1, comparing the learned boundary during the iterations with the ground truth boundary. Fig 10 shows the results for different iterated algorithmic biasterm modes with different human action probabilityterm·var. We can see that for both random selectionterm and active learningterm biasterm·def, the number of points predicted as relevant converges to the ground truth boundary when there is a high probability of human action. On the other hand, filter biasterm tends to diverge from the ground truth boundary with high human action probabilityterm·var. With p action = 0.01, there are no obvious trends for all three algorithmic biasterm·def forms.

Effect of Human action on the boundary learned during the iterations. The y-axis is the number of testing points which are predicted to be relevant. We can see that for both random selectionterm and active learningterm biasterm·def, the number of points predicted as relevant converges to the ground truth boundary when there is a high probability of human action. On the other hand, filter biasterm tends to diverge from the ground truth boundary in the presence of high human action probabilityterm·var. With p action = 0.01, there are no obvious trends for all three algorithmic biasterm·def forms.

RQ 2.2: Does human action affect the class-1-blind spot size during iterative learning given a fixed iterated algorithmic biasterm mode?

We want to compare the blind spotterm within each different iterated algorithmic biasterm mode, alone. We do so by analyzing the class-1-blind spot size. We run experiments with different human action probabilities and record the class-1-blind spot size comparing the blind spotterm sizes from the first iteration and last iteration. As shown in Table 6 , with higher human action probabilityterm·var, the class-1-blind spot size is higher through all three iterated algorithmic biasterm modes.

Results of the Mann-Whitney U test and t-test for the class-1-blind spot of the computed three forms of iterated algorithmic biasterm based on the different probability levels of human action. Here, effect size is ES = ( BlindSpot | t = 0 − BlindSpot | t = 200 )/ standard . dev . Bold means the significance at p<0.05. The more the human reacts to the system, the bigger is the class-1-blind spot size.

RQ 2.3: Does human action affect the relevance prediction inequalityterm or Gini coefficientterm·var during iterative learning given a fixed iterated algorithmic biasterm mode?

We wish to compare the inequality induced by each algorithmic biasterm·def form, alone. We do so by analyzing the Gini coefficientterm·var. We perform the Mann-Whitney U statistical test to see whether the human action will lead to different trends in the inequality of prediction. We run experiments with different human action probabilities, namely 1.0, 0.5 and 0.01, and compare the inequality between the first iteration and last iteration. Table 7 shows that higher human action probabilityterm·var leads to high inequality with the filter biasterm mode. On the other hand, active learningterm significantly decreases the inequality by querying points which are near the learned boundary.

Results of the Mann-Whitney U test and t-test for the inequality of the computed three forms of iterated algorithmic biasterm based on the different probability levels of human action. Here, effect size is computed as ES = ( Gini | t = 0 − Gini | t = 200 )/ standard . dev . Bold means the significance at p<0.05. The more the human reacts to the system, the bigger is the inequality in the prediction.

RQ 3: Does human preference towards labeling relevant data affect the boundary?

In research question 2 (RQ 2), we assumed that humans have a prior probability to act which is not dependent on the true label of the item presented. However, in a more realistic world, humans interact with the recommended items, according to their inner preference. In this section, we try to simulate this by assuming that humans have a higher probability to label or rate when the item presented is from relevant class y = 1 (see Eq 15 ). We therefore setup the class-dependent human action probabilityterm·var ratio to 10:1, i.e., p ( action | y = 1) = 10 p ( action | y = 0).

RQ 3.1: Does human preference towards labeling relevant data affect the boundary shiftterm during iterative learning given a fixed iterated algorithmic biasterm mode?

To answer this question, we run experiments and record the number of points which are predicted to be in class y = 1 before and after iterative learning. We first aim to understand how human preference changes the boundary. We do so by performing the Mann-Whitney test and t-test. Table 8 shows that the filter biasterm significantly decreases the number of points predicted to be in class y = 1. On the other hand, random selectionterm significantly increases the number of points predicted to be in class y = 1. Active learningterm has no such significant effect. We also compare the effect across different iterated algorithmic biasterm modes by performing a Kruskal-wallis test. The p-value is 1.87e-21 (<0.01), which indicates that the biasterm·def modes have different effects on the boundary shiftterm (see Fig 11 ).

Results of the Mann-Whitney U test and the t-test comparing boundary shiftterm for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 10:1. The effect size is calculated as ( Boundary | t = 0 − Boundary | t = 200 )/ standard . dev . The negative effect size for filter biasterm shows that it decreases the number of points which are predicted to be in class y = 1. Random selectionterm increases the number of points, while active learningterm does not have a significant effect.

The box-plots showing the distribution of the number of points that are predicted to be in class y = 1 in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with human action probabilityterm·var ratio 10:1. Filter biasterm significantly decreases the number of points predicted to be in class y = 1. On the other hand, random selectionterm significantly increases the number of points predicted to be in class y = 1. Active learningterm has no such significant effect.

It is also interesting to compare the effect on boundary shiftterm for different biasterm·def modes when the class-dependent human action probabilityterm·var ratios are set as 10:1 and 1:1. Table 9 shows the results. Both Filter biasterm and active learningterm biasesterm·def show no significant difference in boundary shiftterm between the two ratios. On the other hand, random selectionterm has increased the number of points predicted to be in class y = 1 when the ratio was 10:1. The results are expected, since filter biasterm already prefers points from class y = 1. Active learningterm biasterm·def shows a smaller effect since this biasterm·def already prefers points that are close to the boundary. Random selectionterm with class-dependent human action probabilityterm·var prefer points from class y = 1, however randomly. Therefore, it slightly shifts the boundary to class y = 0.

Results of the Mann-Whitney U test and the t-test comparing boundary shiftterm for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 1:1 and 10:1. The effect size is calculated as ( Boundary | ratio = 1: 1 − Boundary | ratio = 10: 1 )/ standard . dev at time t = 200. Both Filter biasterm and active learningterm biasterm·def show no significant difference between the two ratios. On the other hand, random selectionterm leads to more points predicted to be in class y = 1.

RQ 3.2: Does human preference towards labeling relevant data affect the size of the blind spotterm during iterative learning given a fixed iterated algorithmic biasterm mode?

To answer this question, we run experiments and record the size of the class-1 blind spotterm during iterative learning. Recall that the class-1 blind spotterm indicates how the interaction affects the human’s ability to discover items. We first aim to understand how human preference changes the blind spotterm size before and after iterative learning. We do so by performing the Mann-Whitney test and t-test. Table 10 shows that filter biasterm significantly increases the size of the class-1 blind spotterm. On the other hand, random selectionterm significantly decreases the size of the class-1 blind spotterm. Active learningterm has no such significant effect. We also compare the effect across different iterated algorithmic biasterm modes by performing a Kruskal-wallis test. The p-value is 3.4e-15 (<0.01), which indicates that they have different effects on the boundary shiftterm (see Fig 12 ).

Results of the Mann-Whitney U test and the t-test comparing the size of class-1 blind spotterm for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 10:1. The effect size is calculated as ( Boundary | t = 0 − Boundary | t = 200 )/ standard . dev . The negative effect size for filter biasterm shows that it increases the size of the class-1-blind spot. Random selectionterm decreases the blind spotterm size, while active learningterm does not have a significant effect.

The box-plots showing the size of the class-1 blind spotterm in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with human action probabilityterm·var ratio 10:1. Filter biasterm significantly decreases the number of points predicted to be in class y = 1. On the other hand, random selectionterm significantly increases the number of points predicted to be in class y = 1. Active learningterm has no such significant effect.

It is also interesting to compare the effect on the class-1 blind spotterm size with the class-dependent human action probabilityterm·var ratio set to 10:1 and 1:1. Table 11 shows the results for the class-1 blind spotterm size. Both Filter biasterm and active learningterm biasterm·def show no significant difference between the two ratios. On the other hand, random selectionterm has increased the number of points predicted to be in class y = 1. Filter biasterm already prefers points from class y = 1 so they do not show any significant difference. Active learningterm biasterm·def has less effect since it prefers points that are close to the boundary. Random selectionterm with class-dependent human action probabilityterm·var prefers points from class y = 1, however it is randomly. Therefore, it slightly shifts the boundary to class y = 0.

Results of the Mann-Whitney U test and the t-test comparing boundary shiftterm for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 1:1 and 10:1. The effect size is calculated as ( Boundary | ratio = 1: 1 − Boundary | ratio = 10: 1 )/ standard . dev at time t = 200. Both Filter biasterm and active learningterm biasterm·def show no significant difference between the two ratios. On the other hand, random selectionterm decreases the class-1 blind spotterm size.

RQ 3.3: Does human preference towards to relevant class affect the inequality or Gini coefficientterm·var during iterative learning given a fixed iterated algorithmic biasterm mode?

To answer this question, we run experiments and record the Gini coefficientterm·var before and after iterative learning. We first aim to understand how human preference affects the prediction inequalityterm. We do so by performing the Mann-Whitney test and t-test. Table 12 shows that the filter biasterm significantly decreases the number of points predicted to be in class y = 1. On the other hand, random selectionterm significantly increases the number of points predicted to be in class y = 1. Active learningterm has no such significant effect. We also compare the effect across different iterated algorithmic biasterm modes by performing a Kruskal-wallis test. The p-value is 3.3e-18 (<0.01), which indicates that they have different effect on the boundary shiftterm (see Fig 13 ).

Results of the Mann-Whitney U test and the t-test comparing the inequality of prediction for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 10:1. The effect size is calculated as ( Gini | t = 0 − Gini | t = 200 )/ standard . dev . The negative effect size for filter biasterm shows that it increases the inequality. Both active learningterm and random selectionterm decrease the inequality.

The box-plots showing the inequality score at the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with human action probabilityterm·var ratio 10:1. Filter biasterm significantly increases the Gini coefficientterm·var. On the other hand, random selectionterm significantly decrease the Gini coefficientterm·var, as well as the active learningterm.

It is also interesting to compare the effect on the inequality of prediction with the class-dependent human action probabilityterm·var ratio set to 10:1 and 1:1. Table 13 shows the results for the inequality of prediction. Both Filter biasterm and active learningterm biasterm·def show no significant difference between the two ratios. On the other hand, random selectionterm has increased the number of points predicted to be in class y = 1. There is no significant difference for the filter biasterm mode, since it already prefers points from class y = 1. Active learningterm biasterm·def has less effect since it prefers points that are close to the boundary. Random selectionterm with class-dependent human action probabilityterm·var prefers points from class y = 1, however this occurs randomly. Therefore, it slightly decreases the inequality.

Results of the Mann-Whitney U test and the t-test comparing the inequality for the three forms of iterated algorithmic biasterm with class-dependent human action probabilityterm·var ratio 1:1 and 10:1. The effect size is calculated as ( Boundary | ratio = 1: 1 − Boundary | ratio = 10: 1 )/ standard . dev at time t = 200. Both Filter biasterm and active learningterm biasterm·def show no significant difference between the two ratios. On the other hand, random selectionterm has decreased the class-1 blind spotterm size.

Experiments on high dimensional synthetic data set We perform similar experiments on 3D and 4D synthetic data using a similar data generation method. Our experiments produced similar results to the 2D data. We found that as long as the features are independent from each other, similar results are obtained to the 2D case above. One possible reason is that when features are independent, we can reduce them in a similar way to the 2D synthetic data set, i.e., one set of features that are highly related to the labels and another set of features that are non-related to the labels. Another possible reason is that independent features naturally fit the assumption of the Naive Bayes classifier. Finally, we generated a synthetic data with 10 dimensions, centered at (-2,0,0,0,0,0,0,0,0,0) and (2,0,0,0,0,0,0,0,0,0) with zero covariance between any two dimensions. We follow the same experimental procedure as the 2D synthetic data. Table 14 shows that the 10D synthetic data leads to similar results to the 2D synthetic data set. In order to avoid repetition, we here only report the results that show how different iterated algorithm biasterm·def modes affect the learned model during iterative learning. To conclude, repeated experiments on additional data with dimensionality ranging from 2 to 10 led to the same conclusions as the 2D data set.

Experimental results with a 10D synthetic data set. The effect size is calculated by ( Measurement | t = 0 − Measurement | t = 200 )/ std (⋅). The measurements are the three metrics presented in Section Evaluating the Effect of Iterated Algorithmic Biasterm on Learning Algorithms 1. We report the paired t-test results. For filter biasterm mode (FB), the results are identical to those of the 2D synthetic data across all three research questions. Active learningterm biasterm·def (AL) generates the same result as for the 2D synthetic data. Random selectionterm (RM) has no obvious effect, similarly to the 2D synthetic data experiments.

Experiments on the real-life data set We follow the same experimental procedure as for the synthetic data set from Section 1, but using the MovieLens data (as described in Section Experimental Data Sets 1). 200 items are randomly selected as testing set from both classes (like/dislike) for user 547. The testing set is also considered as validation set for the blind spotterm study. After that, 200 more items from the negative class (dislike) and 300 more items from the positive class (like) are randomly selected to initialize the first boundary. The reason we chose a different proportion from each is to be consistent with the proportions in the whole data set. The iterated learningterm commences after the initialization and continues for 200 iterations. With the real data, we aim to investigate how different iterated algorithmic biasesterm affect the learned model. Thus, the human action probabilityterm·var is set to p action = 1 and the preference to a certain class is not considered.

Visualizing the boundary in high-dimensional data is difficult. However most classifiers produce connected areas for each group [ 156 ]. We therefore can employ the number of data points which changed their label after applying the new model to intuitively capture the level of the boundary shiftterm and to understand how the model is affected during the iterated learningterm process. By also studying the blind spotterm evolution, we can get a sense of the items that have a very low probability to be shown to the user, because they are part of the blind spotterm when considering the probability of belonging to class y = 1.

Boundary shiftterm study Following the same procedure as in RQ 1 1, we run experiments for three different forms of iterated algorithmic biasterm and record the number of points which are predicted to be in class 1 in the first iteration and last iteration. We perform the Mann-Whitney U statistical test to see whether the different iterated algorithmic biasesterm lead to different trends of the boundary shiftterm, we also report the t-test results and effect size. Table 15 shows that there is a significant decrease in the number of points predicted to be in class y = 1 in the testing set for iterated filter biasterm. On the other hand, there is no significant difference with active learningterm biasterm·def and random selectionterm. The effect size here is calculated using ( Boundary | t = 0 − Boundary | t = 200 )/ standard . dev , we will use this setup for the rest of this section. It is also interesting that three different iterated algorithmic biasterm modes have different results of prediction given similar initialization (see Fig 14 ). All these results are consistent with the results from the synthetic data set.

Results of the Mann-Whitney U test and the t-test comparing the boundary shiftterm for the three forms of iterated algorithmic biasterm with the Movielens data set. The positive effect size indicates that filter biasterm leads to fewer points predicted to be in class y = 1. Random selectionterm and active learningterm do not have a significant impact.

The box-plots showing the distribution of the number of points that are predicted to be in class y = 1 in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with the MovieLens data set. Filter biasterm significantly decreases the number of points predicted to be in class y = 1. On the other hand, random selectionterm and Active learningterm have no such significant effect.

We conclude that both iterated filter biasterm and iterated active learningterm biasterm·def have a significantly effect on the boundary shiftterm, while random selectionterm does not have a significant effect. This means that the nature of the model, and hence which items will be judged to be relevant to the user, changes depending on the iterated algorithmic biasterm, with filtering biasterm·def exerting the biggest influence. This kind of phenomenon was found to hold based on all the statistical tests performed in this paper for synthetic and real data.

Blind spotterm size study In order to test how different iterated algorithmic biasterm modes affect the blind spotterm size, we ran experiments for three different forms of iterated algorithmic biasterm and recorded the size of the blind spotterm in the first iteration and last iteration. We performed the Mann-Whitney U statistical test and we also report the t-test results and effect size. Table 16 shows that there is a significant increase in the class-1 blind spotterm sizes in the testing set for iterated filter biasterm and active learningterm biasterm·def. On the other hand, there is no significant difference with random selectionterm (see Fig 15 ).

Results of the Mann-Whitney U test and the t-test comparing the size of the class-1-blind spot for the three forms of iterated algorithmic biasterm with the Movielens data set. The negative effect size indicates that filter biasterm leads to a bigger blind spotterm. Both random selectionterm and active learningterm do not have a significant impact.

The box-plots showing the distribution of the size of the class-1 blind spotterm in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm with the MovieLens data set. Filter biasterm significantly increases the size of the class-1 blind spotterm. On the other hand, random selectionterm and Active learningterm have no such significant effect.

It is important to note that this impact is significant enough to result in hiding even relevant items from the user . A similar impact was found when the initial labeled (training) set is class imbalanced with more relevant items than non relevant items. Optional human willingness to label items seems to have a significant impact on the resulting model and thus on which items are judged to be relevant and in turn can be discovered by the user .

Inequality study In order to test how different iterated algorithmic biasterm modes affect the inequality of predictions, we ran experiments for three different forms of iterated algorithmic biasterm and recorded the Gini coefficientterm·var in the first iteration and last iteration. We performed the Mann-Whitney U statistical test and we also report the t-test results and effect size. Table 17 shows that filter biasterm leads to a significant increase in the Gini coefficientterm·var, while both active learningterm and random selectionterm result in a significant decrease in the Gini coefficientterm·var. It is important to note that both random selectionterm and active learningterm are used to build an accurate model in machine learning. Therefore, both biasterm·def modes decrease the inequality (see Fig 16 ).

Results of the Mann-Whitney U test and the t-test comparing the inequality of prediction for the three forms of iterated algorithmic biasterm with the Movielens data set. The negative effect size indicates that filter biasterm leads to high inequality of relevance prediction. Both random selectionterm and active learningterm significant decrease on the inequality.

The box-plots showing the distribution of the Gini coefficientterm·var of the prediction in the first and last iterations of the iterated learningterm for three iterated algorithmic biasesterm on the MovieLens data set. Filter biasterm significantly increases the in equality of prediction. On the other hand, random selectionterm and Active learningterm lead to a significantly decrease in the inequality of prediction.

We also ran experiments with other 7 users. They all produced similar results (see Table 18 ).

Top 8 most active users in MovieLens data set and statistical analysis results with paired t-test. The effect size is calculated as ( Measurement | t = 0 − Measurement | t = 200 )/ standard . dev . Bold means significance, and ES means the effect size. Filter biasterm has a consistently significant and sizable effect on the three measurements across all 8 users. Random selectionterm has less impact on the boundary shiftterm and blind spotterm. However it significantly decreases the inequality. Active learningterm aims to help learn correct boundary, therefore it highly depends on the initial data points. Active learningterm affects points close to the boundary, thus it has limited effects overall.

Conclusion We investigated three forms of iterated algorithmic biasterm (filter, active learningterm, and random baseline) and how they affect the performance of machine learning algorithms by formulating research questions about the impact of each type of biasterm·def. Based on statistical analysis of the results of several controlled experiments using synthetic and real data, we found that (see the overall synthesis of findings in Tables 19 and 20 ): The three different forms of iterated algorithmic biasterm (filter, active learningterm, and random selectionterm, used as query mechanisms to show data and request new feedback/labels from the user), do affect algorithm performance when fixing the human interaction probability to 1. Different initial class imbalanceterm in the training data used to generate the initial relevance boundary, significantly affect the machine learning algorithm’s results for all three forms of iterated algorithmic biasterm, impacting boundary shiftterm which hides relevant items (class 1-blind spot) .

Iterated filter biasterm has a more significant effect on the class-1-blind spot size compared to the other two forms of algorithmic biasesterm·def. This means that iterated filter biasterm, which is prominent in personalized user interfaces, can limit humans’ ability to discover data that is relevant to them .

The iterated learningterm framework is effective for analyzing the impact of iterated algorithmic biasterm in human-algorithm interaction.

There is a long tradition in machine learning algorithms whose performance is guaranteed in the context of unbiased data. Similarly, there is a long tradition in the psychology of human learning of treating learning as inference from unbiased data. Humans and AI algorithms are both increasingly intertwined in feedback loops that end up feeding biased data to both humans and algorithms. Our research attempted to better understand how algorithm performance and human behavior depend on one another and how those dependencies affect long run performance. Our ongoing work will pave the road for a framework in which the study of human-algorithm interaction may progress.

Future work Future work will consider the following three directions: 1) extending our framework and experiments to more users in a collaborative filtering setting; 2) taking into account additional parameters and configurations when testing the impact of iterated algorithmic biasterm and human interaction on ML models, including: (A) changing the number of items recommended in top N relevant item recommendation lists and (B) applying different types of AL (we only investigated uncertainty-based AL); 3) human experiments that study research questions that are similar to the ones formulated for the simulated experiments.

Data Availability There are two sources of the data used for the paper. One is synthetic data which can be accessed through Github: https://github.com/wenlongsunuofl/Evolution-and-Impact-of-Bias-in-Human-and-Machine-Learning-Algorithm-Interaction/tree/master/data The citation for the other data used is: Harper FM, Konstan JA. The movielens datasets: History and context. ACM1289Transactions on Interactive Intelligent Systems (TiiS). 2016;5(4):19 The data can be accessed through the publication. We confirm that the authors in this work had no special access privileges to the data others would not have.

Funding Statement Author: Dr. Olfa NasraouipersName Role: PI Number: NSF-1549981 Founder: National Science Foundation Category: Division of Information & Intelligent Systems Name: Not Unbiased: The Implications of Human-Algorithm Interaction on Training Data and Algorithm Performance, Statement: The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

References Associated Data Data Availability Statement There are two sources of the data used for the paper. One is synthetic data which can be accessed through Github: https://github.com/wenlongsunuofl/Evolution-and-Impact-of-Bias-in-Human-and-Machine-Learning-Algorithm-Interaction/tree/master/data The citation for the other data used is: Harper FM, Konstan JA. The movielens datasets: History and context. ACM1289Transactions on Interactive Intelligent Systems (TiiS). 2016;5(4):19 The data can be accessed through the publication. We confirm that the authors in this work had no special access privileges to the data others would not have.