Module -4

Multi-Arm Bandit Algorithm

Multi-arm bandits offer an approach to testing, especially web testing, that allows
explicit optimization and more rapid decision making than the traditional statistical
approach to designing experiments.

A traditional A/B test involves data collected in an experiment, according to a

specified design, to answer a specific question such as, “Which is better,
treatment A or treatment B?” The presumption is that once we get an answer to
that question, the experimenting is over and we proceed to act on the results.

You can probably perceive several difficulties with that approach. First, our
answer may be inconclusive: “effect not proven.” In other words, the results from
the experiment may suggest an effect, but if there is an effect, we don’t have a big
enough sample to prove it (to the satisfaction of the traditional statistical
standards). What decision do we take? Second, we might want to begin taking
advantage of results that come in prior to the conclusion of the experiment. Third,
we might want the right to change our minds or to try something different based on
additional data that comes in after the experiment is over. The traditional
approach to experiments and hypothesis tests dates from the 1920s, and is rather
inflexible. The advent of computer power and software has enabled more
powerful flexible approaches. Moreover, data science (and business in general) is
not so worried about statistical significance, but more concerned with optimizing
overall effort and results.

1 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Bandit algorithms, which are very popular in web testing, allow you to test
multiple treatments at once and reach conclusions faster than traditional statistical
designs. They take their name from slot machines used in gambling, also termed
one-armed bandits (since they are configured in such a way that they extract
money from the gambler in a steady flow). If you imagine a slot machine with
more than one arm, each arm paying out at a different rate, you would have a
multi-armed bandit, which is the full name for this algorithm.

Your goal is to win as much money as possible, and more specifically, to identify
and settle on the winning arm sooner rather than later. The challenge is that you
don’t know at what rate the arms pay out — you only know the results of pulling
the arm. Suppose each “win” is for the same amount, no matter which arm. What
differs is the probability of a win. Suppose further that you initially try each arm
50 times and get the following results:

Arm A: 10 wins out of 50

Arm B: 2 win out of 50
Arm C: 4 wins out of 50

One extreme approach is to say, “Looks like arm A is a winner — let’s quit trying
the other arms and stick with A.” This takes full advantage of the information from
the initial trial. If A is truly superior, we get the benefit of that early on. On the
other hand, if B or C is truly better, we lose any opportunity to discover that.
Another extreme approach is to say, “This all looks to be within the realm of
chance — let’s keep pulling them all equally.” This gives maximum opportunity
for alternates to A to show themselves. However, in the process, we are deploying
what seem to be inferior treatments. How long do we permit that? Bandit
algorithms take a hybrid approach: we start pulling A more often, to take
advantage of its apparent superiority, but we don’t abandon B and C. We just pull
them less often. If A continues to outperform, we continue to shift resources
(pulls) away from B and C and pull A more often. If, on the other hand, C starts to
do better, and A starts to do worse, we can shift pulls from A back to C. If one of
them turns out to be superior to A and this was hidden in the initial trial due to
chance, it now has an opportunity to emerge with further testing.

Now think of applying this to web testing. Instead of multiple slot machine arms,
you might have multiple offers, headlines, colors, and so on, being tested on a
website. Customers either click (a “win” for the merchant) or don’t click. Initially,
the offers are shown randomly and equally. If, however, one offer starts to
outperform the others, it can be shown (“pulled”) more often. But what should the
2 by Vidyashree.R (Assistant prof. POP)
CSE(DS)
parameters of the algorithm that modifies the pull rates be? What “pull rates”
should we change to, and when should we change?

Here is one simple algorithm, the epsilon-greedy algorithm for an A/B test:
1. Generate a random number between 0 and 1.

2. If the number lies between 0 and epsilon (where epsilon is a number

between 0 and 1, typically fairly small), flip a fair coin (50/50
probability), and:
a. If the coin is heads, show offer A.
b. If the coin is tails, show offer B.

3. If the number is ≥ epsilon, show whichever offer has had the highest
response rate to date.

Epsilon is the single parameter that governs this algorithm. If epsilon is 1, we end
up with a standard simple A/B experiment (random allocation between A and B
for each subject). If epsilon is 0, we end up with a purely greedy algorithm — it
seeks no further experimentation, simply assigning subjects (web visitors) to the
best-performing treatment.

A more sophisticated algorithm uses “Thompson’s sampling.” This procedure

“samples” (pulls a bandit arm) at each stage to maximize the probability of
choosing the best arm. Of course you don’t know which is the best arm — that’s
the whole problem! — but as you observe the payoff with each successive draw,
you gain more information. Thompson’s sampling uses a Bayesian approach: some
prior distribution of rewards is assumed initially, using what is called a beta
distribution (this is a common mechanism for specifying prior information in a
Bayesian problem). As information accumulates from each draw, this information
can be updated, allowing the selection of the next draw to be better optimized as
far as choosing the right arm.

Bandit algorithms can efficiently handle 3+ treatments and move toward optimal
selection of the “best.” For traditional statistical testing procedures, the
complexity of decision making for 3+ treatments far outstrips that of the traditional
A/B test, and the advantage of bandit algorithms is much greater.

3 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Power and Sample Size
Power in statistics, is crucial for conducting reliable and valid hypothesis testing.
Power is the probability that a statistical test will correctly reject a false null
hypothesis, giving you confidence in your results.
What is Statistical Power?
Statistical power is the probability that a statistical test will correctly reject a false
null hypothesis. In other words, it's the likelihood that the test will detect an effect
or difference when there is one.
Mathematically it is represented as 1−β where β is the probability of the
committing a Type II error. Higher power indicates a higher probability of the
detecting an effect when there is one.
Statistical power is important because it helps researchers determine the sample
size needed for a study. A test with high power means there is a greater chance of
detecting a true effect, reducing the risk of a Type II error (failing to reject a false
null hypothesis).
Importance of Statistical Power in Hypothesis Testing
Understanding and calculating the statistical power is essential because:
 Validity of Results: Ensures that the study results are reliable and not due to
the chance.
 Study Design: Helps in designing the experiments with the adequate sample
sizes to the detect meaningful effects.
 Resource Efficiency: The Prevents wasting resources on studies that are
unlikely to the yield conclusive results.
 Ethical Considerations: The Minimizes the risk of the exposing subjects to
the ineffective treatments.
Factors Influencing Statistical Power
The Several factors affect the power of the statistical test including:
 Sample Size : The Larger sample sizes generally increase the power of the
test. This is because larger samples provide more accurate estimates of the
population parameters reducing the standard error.
 Effect Size : The Effect size measures the magnitude of the difference
between groups or the strength of the relationship between the variables. The
Larger effect sizes make it easier to the detect a true effect increasing power.
 Significance Level (α) : The significance level usually set at 0.05 is the
probability of the rejecting the null hypothesis when it is true. The Lower α
values reduce power while higher α values increase power but also increase
the risk of the Type I errors.
 Variability : The Lower variability within the data increases power as it
makes it easier to the detect differences between the groups. Reducing the

4 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
 measurement error and controlling the extraneous variables can help achieve
lower variability.
 Test Type : The type of the statistical test used also affects power. Some
tests are more powerful than others in the detecting effects under certain
conditions.
How to Increase Statistical Power?
Increasing statistical power is important for ensuring that a study is capable of
detecting true effects. Here are several strategies to increase statistical power:
 Increase Sample Size: The most direct way to increase power is to increase
the number of participants or observations in the study. Larger sample sizes
reduce the standard error and make it easier to detect an effect.
 Increase Effect Size: While effect size is often determined by the nature of
the phenomenon being studied, it can sometimes be increased by:
o Using more precise measurement instruments.
o Reducing measurement error.
o Focusing on stronger interventions or manipulations.
 Reduce Variability: Reducing the variability in the data can increase power.
This can be achieved by:
o Using more homogeneous groups or conditions.
o Controlling for confounding variables that add noise to the data.
o Improving the consistency and accuracy of measurement tools.
 Solved Problems on Statistical Power
 Problem 1: A researcher wants to test the effect of the new drug on blood
pressure. The expected effect size is 0.5 the significance level is 0.05 and
sample size is 100. What is the power of the study?
 Solution:
 Using a power analysis tool or formula input the given parameters to the
calculate the power. The power is found to be approximately 0.80 indicating
an 80% chance of the detecting a true effect.
 Problem 2: In a study comparing two teaching methods the sample size is
50 per group the significance level is 0.05 and variability is low. If the
observed effect size is 0.3 what is the power?
 Solution:
 With the given parameters the power analysis yields a power of the
approximately 0.60 indicating a 60% chance of the detecting a true effect.

Sample Size

5 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
The number of observations chosen from the population when the statistical
estimate for the entire population is made is referred to as the sample size in
statistics.

For example, suppose you are looking at click-through rates (clicks as a

percentage of exposures), and testing a new ad against an existing ad. How many
clicks do you need to accumulate in the study? If you are only interested in results
that show a huge difference (say a 50% difference), a relatively small sample
might do the trick. If, on the other hand, even a minor difference would be of
interest, then a much larger sample is needed. A standard approach is to establish
a policy that a new ad must do better than an existing ad by some percentage, say
10%; otherwise, the existing ad will remain in place. This goal, the “effect size,”
then drives the sample size.

For example, suppose current click-through rates are about 1.1%, and you are
seeking a 10% boost to 1.21%. So we have two boxes, box A with 1.1% ones
(say 110 ones and 9,890 zeros), and box B with 1.21% ones (say 121 ones and
9,879 zeros). For starters, let’s try 300 draws from each box (this would be like
300 “impressions” for each ad). Suppose our first draw yields the following:
 Box A: 3 ones
 Box B: 5 ones

Right away we can see that any hypothesis test would reveal this difference (5
versus 3) to be well within the range of chance variation. This combination of
sample size (n = 300 in each group) and effect size (10% difference) is too small
for any hypothesis test to reliably show a difference.
So we can try increasing the sample size (let’s try 2,000 impressions), and require
a larger improvement (30% instead of 10%).

For example, suppose current click-through rates are still 1.1%, but we are now
seeking a 50% boost to 1.65%. So we have two boxes: box A still with 1.1% ones
(say 110 ones and 9,890 zeros), and box B with 1.65% ones (say 165 ones and
9,868 zeros). Now we’ll try 2,000 draws from each box. Suppose our first draw
yields the following:
 Box A: 19 ones
 Box B: 34 ones

A significance test on this difference (34–19) shows it still registers as “not

significant” (though much closer to significance than the earlier difference of 5–3).
To calculate power, we would need to repeat the previous procedure many times,
6 by Vidyashree.R (Assistant prof. POP)
CSE(DS)
or use statistical software that can calculate power, but our initial draw suggests
to us that even detecting a 50% improvement will require several thousand ad
impressions.
In summary, for calculating power or required sample size, there are four moving
parts:
 Sample size
 Effect size you want to detect
 Significance level (alpha) at which the test will be conducted
 Power
Specify any three of them, and the fourth can be calculated. Most commonly, you
would want to calculate sample size, so you must specify the other three.

factor variables in regression

In regression analysis, factor variables (also known as categorical or qualitative
variables) represent groupings or categories rather than continuous numerical
values. They need to be handled differently than continuous variables because
regression models require numerical inputs. To use factor variables in regression,
they are typically converted into a set of dummy variables (also called indicator
variables), where each dummy variable represents a specific level or category.

Here's a more detailed explanation:

What are Factor Variables?

 Factor variables represent qualitative data that can be grouped into
categories, such as "color" (red, blue, green), "gender" (male, female), or
"region" (North, South, East, West).
 They have a limited and fixed number of possible values or levels.
 Unlike continuous variables that can take any value within a range, factor
variables have distinct categories.

Why Convert Factor Variables?

 Regression models, like linear regression, are typically designed to work
with numerical data.
 Factor variables, in their original form, cannot be directly used in these
models because they don't have a natural numerical ordering or scale.
 Therefore, they need to be transformed into a numerical representation that
the model can understand.

7 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Dummy Variable Encoding
 The most common method for handling factor variables in regression is to
create dummy variables (also known as indicator variables or one-hot
encoding).
 For a factor variable with k levels, k-1 dummy variables are created.
 Each dummy variable represents one level of the factor variable, and it takes
a value of 1 if the observation belongs to that level and 0 otherwise.
 One level is typically chosen as the reference level, and it's not included in
the dummy variables. The reference level is the one that is excluded from
the dummy variable coding. It's essentially the baseline against which the
other levels are compared.
Example:
Let's say you have a factor variable "color" with levels "red", "green", and
"blue". You would create two dummy variables:
 is_red: 1 if the color is red, 0 otherwise
 is_green: 1 if the color is green, 0 otherwise
The "blue" level would be the reference level, and it would not have a
corresponding dummy variable.

Benefits of Using Factor Variables:

 Clearer Interpretation:
By using dummy variables, you can interpret the coefficients of the regression
model as the effect of being in a particular category compared to the reference
category.
 Accurate Modeling:
It allows you to incorporate categorical information into your regression models,
which can lead to more accurate predictions and insights.
 Flexibility:
Dummy variables can be used with various regression techniques, including linear
regression, logistic regression, and more.
 Memory Efficiency:
Saving categorical variables as factors can save memory compared to storing them
as strings
 Software and Implementation:
Most statistical software packages (like R, Python's statsmodels, Stata) have built-
in functions to handle factor variables and automatically create dummy variables.

Interpreting the regression equation

8 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Linear regression is a cornerstone technique in statistical modeling, used
extensively to understand relationships between variables and to make predictions.
At the heart of linear regression lies the interpretation of its coefficients. These
coefficients provide valuable insights into the nature of the relationships between
the dependent variable and the independent variables. This article will guide you
through understanding and interpreting these coefficients effectively.

Linear Regression Equation

The basic form of a linear regression equation is:

The intercept (β0) represents the expected value of Y when all X variables are zero.
It serves as the baseline level of the dependent variable. However, its practical
interpretation can sometimes be limited, especially if zero values for all
independent variables are unrealistic or outside the scope of the data.

9 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
10 by Vidyashree.R (Assistant prof. POP)
CSE(DS)
11 by Vidyashree.R (Assistant prof. POP)
CSE(DS)
Regression diagnostics

Regression diagnostics are a set of techniques used to assess how well a regression
model fits the data and to identify potential problems with the model or the data
itself. These techniques help ensure the reliability and accuracy of the model's
predictions and inferences.

Outliers
Generally speaking, an extreme value, also called an outlier, is one that is distant
from most of the other observations. Just as outliers need to be handled for
estimates of location and variability (see “Estimates of Location” and “Estimates
of Variability”), outliers can cause problems with regression models. In
regression, an outlier is a record whose actual y value is distant from the
predicted value. You can detect outliers by examining the standardized residual,
which is the residual divided by the standard error of the residuals.

12 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
There is no statistical theory that separates outliers from nonoutliers. Rather, there
are (arbitrary) rules of thumb for how distant from the bulk of the data an
observation needs to be in order to be called an outlier. For example, with the
boxplot, outliers are those data points that are too far above or below the box
boundaries (see “Percentiles and Boxplots”), where “too far” = “more than 1.5
times the inter-quartile range.” In regression, the standardized residual is the
metric that is typically used to determine whether a record is classified as an
outlier. Standardized residuals can be interpreted as “the number of standard
errors away from the regression line.”
Let’s fit a regression to the King County house sales data for all sales in zip code
98105:

The biggest overestimate from the model is more than four standard errors above
the regression line, corresponding to an overestimate of $757,753. The original
data record corresponding to this outlier is as follows:

In this case, it appears that there is something wrong with the record: a house of
that size typically sells for much more than $119,748 in that zip code. Figure 4-4
shows an excerpt from the statuatory deed from this sale: it is clear that the sale
involved only partial interest in the property. In this case, the outlier corresonds to
a sale that is anomalous and should not be included in the regression. Outliers
could also be the result of other problems, such as a “fat-finger” data entry or a
mismatch of units (e.g., reporting a sale in thousands of dollars versus simply
dollars).

13 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
For big data problems, outliers are generally not a problem in fitting the regression
to be used in predicting new data. However, outliers are central to anomaly
detection, where finding outliers is the whole point. The outlier could also
correspond to a case of fraud or an accidental action. In any case, detecting outliers
can be a critical business need.

14 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Heteroskedasticity, Non-Normality and Correlated Errors

Heteroskedasticity, non-normality, and correlated errors are all violations of

assumptions in linear regression models, potentially leading to inaccurate statistical
inferences. Heteroskedasticity refers to unequal variances of errors across different
observations. Non-normality implies that the error terms do not follow a normal
distribution. Correlated errors, or autocorrelation, occur when errors are correlated
with each other across different observations.
1. Heteroskedasticity:
 Definition:
Heteroskedasticity means that the variance of the error terms is not constant across
all levels of the independent variables.
 Impact:
It leads to biased standard errors, making hypothesis tests unreliable and
potentially overestimating the significance of results.
 Detection:

15 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Residual plots (plotting residuals against predicted values) can reveal patterns
indicative of heteroskedasticity. Formal tests like the Breusch-Pagan test or White's
test can also be used.
 Remedies:
Weighted least squares regression, robust standard errors (e.g., White's robust
standard errors), or transformations of the dependent variable (e.g., logarithmic
transformation) can be used to address heteroskedasticity.
2. Non-Normality:
 Definition:
Non-normality means that the distribution of the error terms deviates from a
normal distribution.
 Impact:
While OLS estimators remain unbiased under non-normality, it can affect the
reliability of hypothesis tests, especially with smaller sample sizes.
 Detection:
QQ plots of residuals can visually assess normality. Statistical tests like the
Shapiro-Wilk test or Jarque-Bera test can be used.
 Remedies:
In many cases, non-normality is not a major issue, especially with large sample
sizes, due to the Central Limit Theorem. However, if non-normality is severe,
transformations of the dependent variable or robust regression methods might be
considered.
3. Correlated Errors (Autocorrelation):
 Definition:
Autocorrelation occurs when the error terms are correlated with each other across
different observations, often in time series data.
 Impact:
Similar to heteroskedasticity, autocorrelation leads to biased standard errors,
affecting hypothesis testing.
 Detection:
Residual plots can reveal patterns, and formal tests like the Durbin-Watson test or
Breusch-Godfrey test can be used.
 Remedies:
Techniques like Generalized Least Squares (GLS), Prais-Winsten estimation, or
introducing lagged variables as predictors can address autocorrelation.

In summary: These three violations of assumptions in linear regression models can

lead to inaccurate statistical inferences if not addressed. Understanding the nature
of these issues, how to detect them, and potential remedies is crucial for reliable
regression analysis.
16 by Vidyashree.R (Assistant prof. POP)
CSE(DS)
You can see an example of this cone shaped pattern in the residuals by fitted value
plot below. Note how the vertical range of the residuals increases as the fitted
values increases. Later in this post, we’ll return to the model that produces this plot
when we try to fix the problem and produce homoscedasticity.

What Causes Heteroscedasticity?

Heteroscedasticity, also spelled heteroskedasticity, occurs more often in datasets
that have a large range between the largest and smallest observed values. While
there are numerous reasons why heteroscedasticity can exist, a common
explanation is that the error variance changes proportionally with a factor. This
factor might be a variable in the model.
In some cases, the variance increases proportionally with this factor but remains
constant as a percentage. For instance, a 10% change in a number such as 100 is
much smaller than a 10% change in a large number such as 100,000. In this
scenario, you expect to see larger residuals associated with higher values. That’s
why you need to be careful when working with wide ranges of values!
Because large ranges are associated with this problem, some types of models are
more prone to heteroscedasticity.

17 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Polynomial and Spline Regression

Polynomial regression and spline regression are both used to model non-linear
relationships between variables. Polynomial regression fits a polynomial equation
to the data, while spline regression uses piecewise polynomials (splines) to model
more complex curves, particularly when the relationship isn't well-represented by a
single polynomial.
Polynomial regression and spline regression are both used to model non-linear
relationships between variables, but they achieve this in different ways. Polynomial
regression fits a polynomial equation to the data, while spline regression uses
piecewise polynomials (splines) to model the relationship, offering more
flexibility.

Polynomial Regression:

Polynomial regression extends linear regression by adding polynomial terms (e.g.,

x², x³, etc.) to the model. This allows for capturing curved relationships between
the independent and dependent variables.
 Equation:
A simple polynomial regression model of degree 'd' can be represented as: y = β₀ +
β₁x + β₂x² + ... + βᵤxᵈ + ε, where 'y' is the dependent variable, 'x' is the independent
variable, βᵢ are the coefficients, and ε is the error term.
Advantages:
Can model a wide range of non-linear relationships and is relatively
straightforward to implement.
Disadvantages:
Can be prone to overfitting if the degree of the polynomial is too
high. Extrapolating beyond the range of the training data can be unreliable.

The partial residual plot (see “Partial Residual Plots and Nonlinearity”) indicates
some curvature in the regression equation associated with SqFtTotLiving. The
fitted line more closely matches the smooth (see “Splines”) of the partial residuals
as compared to a linear fit (see Figure 4-10)

18 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
Spline Regression:

Spline regression uses piecewise polynomials to model the relationship between

variables. The data is divided into intervals, and a separate polynomial is fit to each
interval. These intervals are joined at points called knots, which can be chosen to
ensure smoothness of the fitted curve.
 Types of Splines:
 Piecewise Polynomials: The simplest form, where different
polynomials are fit to different segments of the data, but may not be
smooth at the knots.
 Cubic Splines: Ensure smoothness by requiring the first and second
derivatives to be continuous at the knots.
 Natural Splines: Further constrain the splines to be linear beyond the
boundary knots, improving reliability in those regions.
 Smoothing Splines: Introduce a regularization term to balance model
complexity and goodness of fit, helping to prevent overfitting.

19 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
 Advantages:
More flexible than polynomial regression, can model complex non-linear
relationships with fewer parameters, and can provide smoother curves, especially
with cubic and natural splines.

Disadvantages:
Requires choosing the number and placement of knots, which can be
computationally intensive. Interpretation can also be challenging.

Choosing between Polynomial and Spline Regression:

 Complexity of the relationship:

If the relationship is relatively simple and can be well-represented by a low-degree
polynomial, polynomial regression might be sufficient.
 Need for flexibility:
If the relationship is complex and requires a more flexible model, spline regression
is often a better choice.
 Interpretability:
Polynomial regression is generally easier to interpret than spline regression,
especially with higher-degree polynomials or multiple knots.
 Overfitting:
Spline regression with too many knots can lead to overfitting. Regularization
techniques (like smoothing splines) can help mitigate this.
 Computational Cost:
Choosing the optimal number and placement of knots in spline regression can be
computationally intensive.
In contrast to a linear term, for which the coefficient has a direct meaning, the
coefficients for a spline term are not interpretable. Instead, it is more useful to use
the visual display to reveal the nature of the spline fit. Figure 4-12 displays the
partial residual plot from the regression. In contrast to the polynomial model, the
spline model more closely matches the smooth, demonstrating the greater
flexibility of splines. In this case, the line more closely fits the data. Does this
mean the spline regression is a better model? Not necessarily: it doesn’t make
economic sense that very small homes (less than 1,000 square feet) would have
higher value than slightly larger homes. This is possibly an artifact of a
confounding variable; see “Confounding Variables”.

20 by Vidyashree.R (Assistant prof. POP)

CSE(DS)
21 by Vidyashree.R (Assistant prof. POP)
CSE(DS)