UNIT II

Instance based learning, Feature reduction, Collaborative filtering based recommendation,

Probability and Bayes learning.

 Instance-based learning

In machine learning, instance-based learning (sometimes called memory-based learning) is a family

of learning algorithms that, instead of performing explicit generalization, compares new problem
instances with instances seen in training, which have been stored in memory.

It is called instance-based because it constructs hypotheses directly from the training instances
themselves. This means that the hypothesis complexity can grow with the data: in the worst case, a
hypothesis is a list of n training items and the computational complexity of classifying a single new
instance is O(n). One advantage that instance-based learning has over other methods of machine
learning is its ability to adapt its model to previously unseen data. Instance-based learners may
simply store a new instance or throw an old instance away.

Examples of instance-based learning algorithm are the k-nearest neighbors algorithm, kernel
machines and RBF networks. These store (a subset of) their training set; when predicting a
value/class for a new instance, they compute distances or similarities between this instance and the
training instances to make a decision.

To battle the memory complexity of storing all training instances, as well as the risk of overfitting to
noise in the training set, instance reduction algorithms have been proposed.

Gagliardi applies this family of classifiers in medical field as second-opinion diagnostic tools and as
tools for the knowledge extraction phase in the process of knowledge discovery in databases. One of
these classifiers (called Prototype exemplar learning classifier (PEL-C) is able to extract a mixture
of abstracted prototypical cases (that are syndromes) and selected atypical clinical cases.

 k-nearest neighbor classification

K-nearest neighbors (KNN) algorithm is a type of supervised ML algorithm which can be used
for both classification as well as regression predictive problems. However, it is mainly used for
classification predictive problems in industry. The following two properties would define KNN
well −
A. Lazy learning algorithm − KNN is a lazy learning algorithm because it does not have a
specialized training phase and uses all the data for training while classification.
B. Non-parametric learning algorithm − KNN is also a non-parametric learning algorithm
because it doesn‟t assume anything about the underlying data.

 Working of KNN Algorithm

K-nearest neighbors (KNN) algorithm uses „feature similarity‟ to predict the values of new
datapoints which further means that the new data point will be assigned a value based on how
closely it matches the points in the training set. We can understand its working with the help of
following steps −
Step 1 − For implementing any algorithm, we need dataset. So during the first step of KNN, we
must load the training as well as test data.
 Step 2 − Next, we need to choose the value of K i.e. the nearest data points. K can be any integer.
Step 3 − For each point in the test data do the following −

3.1 − Calculate the distance between test data and each row of training data with the help of
any of the method namely: Euclidean, Manhattan or Hamming distance. The most commonly
used method to calculate distance is Euclidean.
3.2 − Now, based on the distance value, sort them in ascending order.
3.3 − Next, it will choose the top K rows from the sorted array.
3.4 − Now, it will assign a class to the test point based on most frequent class of these rows.
Step 4 − End

EXAMPLE

 Nearest-Neighbor Classifiers
o Require three things
 The set of stored examples
 Distance Metric to compute distance between examples
  The value of k, the number of nearest neighbors to retrieve
o To classify an unknown example:
 Compute distance to other training examples
 Identify k nearest neighbors
 Use class labels of nearest neighbors to determine the class label of unknown
example (e.g., by taking majority vote)

 Choosing the right value for K

To select the K that‟s right for your data, we run the KNN algorithm several times with different
values of K and choose the K that reduces the number of errors we encounter while maintaining
the algorithm‟s ability to accurately make predictions when it‟s given data it hasn‟t seen before.
 Large k:
 less sensitive to noise (particularly class noise)
 better probability estimates for discrete classes
 larger training sets allow larger values of k
 Small k:
 captures fine structure of problem space better
 may be necessary with small training sets
 Balance must be struck between large and small k
 As training set approaches infinity, and k grows large, kNN becomes Bayes optimal
 In cases where we are taking a majority vote (e.g. picking the mode in a classification
problem) among labels, we usually make K an odd number to have a tiebreaker.

 Distance Functions
o Computes the distance between two examples so that we can find the “nearest neighbor” to a
given example
o General Idea: reduce the distance d (x1, x2) of two examples to the distances d A (v1, v2)
between two values for attribute A
o Popular choices

1. Euclidean Distance : straight-line between two points

2. Manhattan or City-block Distance: sum of axis-parallel line segments

 Advantages of Memory-Based Methods/ KNN / Instance Based Learning

o Lazy learning: don‟t do any work until you know what you want to predict (and from what
variables!)
o never need to learn a global model
o many simple local models taken together can represent a more complex global model
o better focussed learning
 o handles missing values, time varying distributions, ...
o Very efficient cross-validation
o Intelligible learning method to many users
o Nearest neighbors support explanation and training
o Can use any distance metric: string-edit distance, …

 Weaknesses of Memory-Based Methods/ KNN / Instance Based Learning

o Curse of Dimensionality:
 often works best with 25 or fewer dimensions
o Run-time cost scales with training set size
o Large training sets will not fit in memory
o Many MBL methods are strict averagers
o Sometimes doesn‟t seem to perform as well as other methods such as neural nets
o Predicted values for regression not continuous

 Curse of Dimensionality
The curse of dimensionality refers to the phenomena that occur when classifying, organizing, and
analyzing high dimensional data that does not occur in low dimensional spaces, specifically the issue
of data sparsity and “closeness” of data. The size of the data space grows exponentially with the
number of dimensions. This means that the size of your data set must also grow exponentially in
order to keep the same density. If you don‟t, then data points start getting farther and farther apart.

Consider an example in which we have a set of images, each of which depicts either a cat or a dog.
We would like to create a classifier that is able to distinguish dogs from cats automatically. To do so,
we first need to think about a descriptor for each object
class that can be expressed by numbers, such that a
mathematical algorithm, i.e. a classifier, can use these
numbers to recognize the object. We could for instance
argue that cats and dogs generally differ in color.
However, these three color-describing numbers, called
features, will obviously not suffice to obtain a perfect
classification. To obtain an even more accurate
classification, we could add more features, based on
color or texture Maybe we can obtain a perfect classification by carefully defining a few hundred of
these features? The answer to this question might sound a bit counter-intuitive: no we can not!. In
fact, after a certain point, increasing the dimensionality of the problem by adding new features would
actually degrade the performance of our classifier. This is illustrated by figure 1, and is often referred
to as „The Curse of Dimensionality‟.
Why is this especially problematic for k-nearest neighbors?
The special challenge with k-nearest neighbors is that it requires a point to be close in every single
dimension. Some algorithms can create regressions based on single dimensions, and only need points
to be close together along that axis. k-nearest neighbors doesn‟t work that way. It needs all points to
be close along every axis in the data space. And each new axis added, by adding a new dimension,
makes it harder and harder for two specific points to be close to each other in every axis.

The solution of curse of dimensionality is to use feature selection method

 Feature Reduction in ML
In machine learning classification problems, there are often too many factors on the basis of
which the final classification is done. These factors are basically variables called features. The
higher the number of features, the harder it gets to visualize the training set and then work on it.
Sometimes, most of these features are correlated, and hence redundant. This is where
dimensionality reduction algorithms come into play. Dimensionality reduction is the process of
reducing the number of random variables under consideration, by obtaining a set of principal
variables.
It can be divided into
1. feature selection and
2. feature extraction.

 Why is Feature Reduction important in Machine Learning

An intuitive example of Feature reduction can be discussed through a simple e-mail classification
problem, where we need to classify whether the e-mail is spam or not. This can involve a large
number of features, such as whether or not the e-mail has a generic title, the content of the e-
mail, whether the e-mail uses a template, etc. However, some of these features may overlap. In
another condition, a classification problem that relies on both humidity and rainfall can be
collapsed into just one underlying feature, since both of the aforementioned are correlated to a
high degree. Hence, we can reduce the number of features in such problems. A 3-D classification
problem can be hard to visualize, whereas a 2-D one can be mapped to a simple 2 dimensional
space, and a 1-D problem to a simple line. The below figure illustrates this concept, where a 3-D
feature space is split into two 1-D feature spaces, and later, if found to be correlated, the number
of features can be reduced even further.

There are two components of feature reduction:

1. Feature selection: In this, we try to find a subset of the original set of variables, or features,
to get a smaller subset which can be used to model the problem.

Importance of Feature Selection in Machine Learning

Machine learning works on a simple rule – if you put garbage in, you will only get garbage to
come out. By garbage here, It mean noise in data.
This becomes even more important when the number of features are very large. You need not
use every feature at your disposal for creating an algorithm. You can assist your algorithm by
feeding in only those features that are really important.
Top reasons to use feature selection are:
 It enables the machine learning algorithm to train faster.
 It reduces the complexity of a model and makes it easier to interpret.
 It improves the accuracy of a model if the right subset is chosen.
 It reduces overfitting.

Feature Selection Steps

Feature selection is an optimization problem.
o Step 1: Search the space of possible feature subsets.
o Step 2: Pick the subset that is optimal or near-optimal with respect to some objective
function.

It usually involves three ways:

A. Filter Methods

Filter methods are generally used as a preprocessing step. The selection of features is
independent of any machine learning algorithms. Instead, features are selected on the basis
of their scores in various statistical tests for their correlation with the outcome variable.
The correlation is a subjective term here. For basic guidance, you can refer to the following
table for defining correlation co-efficients.
 Pearson’s Correlation: It is used as a measure for quantifying linear dependence between
two continuous variables X and Y. Its value varies from -1 to +1. Pearson‟s correlation is
given as:

OR

 LDA: Linear discriminant analysis is used to find a linear combination of features that
characterizes or separates two or more classes (or levels) of a categorical variable.
 ANOVA: ANOVA stands for Analysis of variance. It is similar to LDA except for the fact
that it is operated using one or more categorical independent features and one continuous
dependent feature. It provides a statistical test of whether the means of several groups are
equal or not.
 Chi-Square: It is a is a statistical test applied to the groups of categorical features to evaluate
the likelihood of correlation or association between them using their frequency distribution.

B. Wrapper Methods

In wrapper methods, we try to use a subset of features and train a model using them. Based
on the inferences that we draw from the previous model, we decide to add or remove features
from your subset. The problem is essentially reduced to a search problem. These methods are
usually computationally very expensive.
Some common examples of wrapper methods are forward feature selection, backward feature
elimination, recursive feature elimination, etc.
 Forward Selection: Forward selection is an iterative method in which we start with
having no feature in the model. In each iteration, we keep adding the feature which best
improves our model till an addition of a new variable does not improve the performance
of the model.
 Backward Elimination: In backward elimination, we start with all the features and
removes the least significant feature at each iteration which improves the performance of
the model. We repeat this until no improvement is observed on removal of features.
 Recursive Feature elimination: It is a greedy optimization algorithm which aims to find
the best performing feature subset. It repeatedly creates models and keeps aside the best
or the worst performing feature at each iteration. It constructs the next model with the left
features until all the features are exhausted. It then ranks the features based on the order
of their elimination.
It works in the following steps:
1. Firstly, it adds randomness to the given data set by creating shuffled copies of all
features (which are called shadow features).
 2. Then, it trains a random forest classifier on the extended data set and applies a
feature importance measure (the default is Mean Decrease Accuracy) to evaluate
the importance of each feature where higher means more important.
3. At every iteration, it checks whether a real feature has a higher importance than the
best of its shadow features (i.e. whether the feature has a higher Z-score than the
maximum Z-score of its shadow features) and constantly removes features which
are deemed highly unimportant.
4. Finally, the algorithm stops either when all features get confirmed or rejected or it
reaches a specified limit of random forest runs.

C. Embedded Methods

Embedded methods combine the qualities‟ of filter and wrapper methods. It‟s
implemented by algorithms that have their own built-in feature selection methods.
Some of the most popular examples of these methods are LASSO and RIDGE regression
which have inbuilt penalization functions to reduce overfitting.
 Lasso regression performs L1 regularization which adds penalty equivalent to
absolute value of the magnitude of coefficients.
 Ridge regression performs L2 regularization which adds penalty equivalent to square
of the magnitude of coefficients.

Difference between Filter and Wrapper methods

The main differences between the filter and wrapper methods for feature selection are:
 Filter methods measure the relevance of features by their correlation with dependent
variable while wrapper methods measure the usefulness of a subset of feature by actually
training a model on it.
 Filter methods are much faster compared to wrapper methods as they do not involve
training the models. On the other hand, wrapper methods are computationally very
expensive as well.
 Filter methods use statistical methods for evaluation of a subset of features while wrapper
methods use cross validation.
 Filter methods might fail to find the best subset of features in many occasions but wrapper
methods can always provide the best subset of features.
 Using the subset of features from the wrapper methods make the model more prone to
overfitting as compared to using subset of features from the filter methods.
 2. Feature extraction: This reduces the data in a high dimensional space to a lower dimension
space, i.e. a space with lesser no. of dimensions.

 Methods of Feature Reduction

The various methods used for feature reduction include:
Feature reduction may be both linear or non-linear, depending upon the method used. The
prime linear method, called Principal Component Analysis, or PCA.

 Principal Component Analysis (PCA)

This method was introduced by Karl Pearson. It works on a condition that while the data in a
higher dimensional space is mapped to data in a lower dimension space, the variance of the data
in the lower dimensional space should be maximum.

Algebraic definition of PCs

Given a sample of p observations on a vector of N variables
x , x ,, x  
1 2 p
N
 define the first principal component of the sample by the linear transformation

N
z1  a1T x j   ai1 xij , j  1,2,, p.
i 1

where the vector a1  (a11 , a21 ,, aN1 )

x j  ( x1 j , x2 j ,, xNj )

is chosen such that var[ z1 ] is maximum

It involves the following steps:

 Construct the covariance matrix of the data.
 Compute the eigenvectors of this matrix.
 Eigenvectors corresponding to the largest eigenvalues are used to reconstruct a large
fraction of variance of the original data.
Hence, we are left with a lesser number of eigenvectors, and there might have been some data
loss in the process. But, the most important variances should be retained by the remaining
eigenvectors.

 Linear Discriminant Analysis (LDA)

Listed below are the 5 general steps for performing a linear discriminant analysis.

 Compute the d-dimensional mean vectors for the different classes from the dataset.
 Compute the scatter matrices (in-between-class and within-class scatter matrix).
 Compute the eigenvectors and corresponding eigenvalues for the scatter matrices.
 Sort the eigenvectors by decreasing eigenvalues and k eigenvectors with the largest
eigenvalues to form a d×k dimensional matrix WW (where every column represents
an eigenvector).
 Use this d×k eigenvector matrix to transform the samples onto the new subspace. This
can be summarized by the matrix multiplication: YY=XX×WW (where XX is a n×d-
dimensional matrix representing the n samples, and yy are the transformed n×k-
dimensional samples in the new subspace).

 Generalized Discriminant Analysis (GDA)

 Principal Component Analysis vs. Linear Discriminant Analysis
Both Linear Discriminant Analysis (LDA) and Principal Component Analysis (PCA) are linear
transformation techniques that are commonly used for dimensionality reduction.
PCA can be described as an “unsupervised” algorithm, since it “ignores” class labels and its
goal is to find the directions (the so-called principal components) that maximize the variance in a
dataset. In contrast to PCA, LDA is “supervised” and computes the directions (“linear
discriminants”) that will represent the axes that that maximize the separation between multiple
classes.
Although it might sound intuitive that LDA is superior to PCA for a multi-class classification
task where the class labels are known, this might not always the case.
For example, comparisons between classification accuracies for image recognition after using
PCA or LDA show that PCA tends to outperform LDA if the number of samples per class is
relatively small
In practice, it is also not uncommon to use both LDA and PCA in combination: E.g., PCA for
dimensionality reduction followed by an LDA.

Advantages of Feature Reduction

 It helps in data compression, and hence reduced storage space.
 It reduces computation time.
 It also helps remove redundant features, if any.

Disadvantages of Feature Reduction

 It may lead to some amount of data loss.
 PCA tends to find linear correlations between variables, which is sometimes undesirable.
 PCA fails in cases where mean and covariance are not enough to define datasets.
 We may not know how many principal components to keep- in practice, some thumb rules
are applied.

Introduction to Recommender System

Like many machine learning techniques, a recommender system makes prediction based on users’
historical behaviors. Specifically, it’s to predict user preference for a set of items based on past
experience. To build a recommender system, the most two popular approaches are Content-based
and Collaborative Filtering.

Content-based approach requires a good amount of information of items’ own features, rather than
using users’ interactions and feedbacks. For example, it can be movie attributes such as genre, year,
director, actor etc., or textual content of articles that can extracted by applying Natural Language
Processing.
Collaborative Filtering, on the other hand, doesn’t need anything else except users’ historical
preference on a set of items. Because it’s based on historical data, the core assumption here is that the
users who have agreed in the past tend to also agree in the future. In terms of user preference, it
usually expressed by two categories.

Explicit Rating, is a rate given by a user to an item on a sliding scale, like 5 stars for Titanic.
This is the most direct feedback from users to show how much they like an item.

Implicit Rating, suggests users preference indirectly, such as page views, clicks, purchase
records, whether or not listen to a music track, and so on. In this article, I will take a close
look at collaborative filtering that is a traditional and powerful tool for recommender systems.

Collaborative Filtering Method : Nearest Neighborhood

The standard method of Collaborative Filtering is known as Nearest Neighborhood algorithm.

There are

user-based CF and

item-based CF.

Let‟s first look at User-based CF. We have an n × m matrix of ratings, with user uᵢ, i = 1, ...n and
item pⱼ, j=1, …m. Now we want to predict the rating rᵢⱼ if target user i did not watch/rate an item j.
The process is to calculate the similarities between target user i and all other users, select the top X
similar users, and take the weighted average of ratings from these X users with similarities as
weights.

Source: [Link]

While different people may have different baselines when giving ratings, some people tend to give
high scores generally, some are pretty strict even though they are satisfied with items. To avoid this
bias, we can subtract each user’s average rating of all items when computing weighted average, and
add it back for target user, shown as below.
 Two ways to calculate similarity are Pearson Correlation and Cosine Similarity.

Basically, the idea is to find the most similar users to your target user (nearest neighbors) and weight
their ratings of an item as the prediction of the rating of this item for target user.
Without knowing anything about items and users themselves, we think two users are similar when
they give the same item similar ratings . Analogously, for Item-based CF, we say two items are
similar when they received similar ratings from a same user. Then, we will make prediction for a
target user on an item by calculating weighted average of ratings on most X similar items from this
user. One key advantage of Item-based CF is the stability which is that the ratings on a given item
will not change significantly overtime, unlike the tastes of human beings.
There are quite a few limitations of this method. It doesn‟t handle sparsity well when no one in the
neighborhood rated an item that is what you are trying to predict for target user. Also, it‟s not
computational efficient as the growth of the number of users and products.

Matrix Factorization

Since sparsity and scalability are the two biggest challenges for standard CF method, it comes a more
advanced method that decompose the original sparse matrix to low-dimensional matrices with latent
factors/features and less sparsity. That is Matrix Factorization.

Beside solving the issues of sparsity and scalability, there‟s an intuitive explanation of why we need
low-dimensional matrices to represent users‟ preference. A user gave good ratings to movie Avatar,
Gravity, and Inception. They are not necessarily 3 separate opinions but showing that this users might
be in favor of Sci-Fi movies and there may be many more Sci-Fi movies that this user would like.
Unlike specific movies, latent features is expressed by higher-level attributes, and Sci-Fi category is
one of latent features in this case. What matrix factorization eventually gives us is how much a user is
aligned with a set of latent features, and how much a movie fits into this set of latent features. The
advantage of it over standard nearest neighborhood is that even though two users haven‟t rated any
same movies, it‟s still possible to find the similarity between them if they share the similar underlying
tastes, again latent features.

To see how a matrix being factorized, first thing to understand is Singular Value
Decomposition(SVD). Based on Linear Algebra, any real matrix R can be decomposed into 3
matrices U, Σ, and V. Continuing using movie example, U is an n × r user-latent feature matrix, V is
an m × r movie-latent feature matrix. Σ is an r × r diagonal matrix containing the singular
values of original matrix, simply representing how important a specific feature is to predict
user preference.

To sort the values of Σ by decreasing absolute value and truncate matrix Σ to first k dimensions( k
singular values), we can reconstruct the matrix as matrix A. The selection of k should make sure that
A is able to capture the most of variance within the original matrix R, so that A is the approximation
of R, A ≈ R. The difference between A and R is the error that is expected to be minimized. This is
exactly the thought of Principle Component Analysis.

When matrix R is dense, U and V could be easily factorized analytically. However, a matrix of movie
ratings is super sparse. Although there are some imputation methods to fill in missing values , we will
turn to a programming approach to just live with those missing values and find factor matrices U and
V. Instead of factorizing R via SVD, we are trying find U and V directly with the goal that when U
and V multiplied back together the output matrix R‟ is the closest approximation of R and no more a
sparse matrix. This numerical approximation is usually achieved with Non-Negative Matrix
Factorization for recommender systems since there is no negative values in ratings.

See the formula below. Looking at the predicted rating for specific user and item, item i is noted as a
vector qᵢ, and user u is noted as a vector pᵤ such that the dot product of these two vectors is the
predicted rating for user u on item i. This value is presented in the matrix R‟ at row u and column i.
How do we find optimal qᵢ and pᵤ? Like most of machine learning task, a loss function is defined to
minimize the cost of errors.

rᵤᵢ is the true ratings from original user-item matrix. Optimization process is to find the optimal matrix
P composed by vector pᵤ and matrix Q composed by vector qᵢ in order to minimize the sum square
error between predicted ratings rᵤᵢ‟ and the true ratings rᵤᵢ. Also, L2 regularization has been added to
prevent overfitting of user and item vectors. It‟s also quite common to add bias term which usually
has 3 major components: average rating of all items μ, average rating of item i minus μ(noted as bᵤ),
average rating given by user u minus u(noted as bᵢ).

Model-based Collaborative Filtering

Now that we have concrete method for defining the similarity between vectors, we can now discuss
how to use this method to identify similar users. The problem set-up is as follows:
1.) We have an n X m matrix consisting of the ratings of n users and m items. Each element of the
matrix (i, j) represents how user i rated item j. Since we are working with movie ratings, each rating
can be expected to be an integer from 1-5 (reflecting one-star ratings to five-star ratings) if user i has
rated movie j, and 0 if the user has not rated that particular movie.
2.) For each user, we want to recommend a set of movies that they have not seen yet (the movie
rating is 0). To do this, we will effectively use an approach that is similar to weighted K-Nearest
Neighbors.
3.) For each movie j user i has not seen yet, we find the set of users U who are similar to user i and
have seen movie j.
For each similar user u, we take u„s rating of movie j and multiply it by the cosine similarity of
user i and user u. Sum up these weighted ratings, divide by the number of users in U, and we get a
weighted average rating for the movie j.
4.) Finally, we sort the movies by their weighted average rankings. These average rankings serve as
an estimate for what the user will rate each movie. Movies with higher average rankings are more
likely to be favored by the user, so we will recommend the movies with the highest average rankings
to the user.
 Bayes Theorem
 Bayes Theorem provides a principled way for calculating a conditional probability.
 It is a deceptively simple calculation, although it can be used to easily calculate the conditional
probability of events where intuition often fails.
 Although it is a powerful tool in the field of probability, Bayes Theorem is also widely used in
the field of machine learning. Including its use in a probability framework for fitting a model to a
training dataset, referred to as maximum a posteriori or MAP for short, and in developing models
for classification predictive modeling problems such as the Bayes Optimal Classifier and Naive
Bayes.

 Bayes Theorem of Conditional Probability

Before we dive into Bayes theorem, let‟s review marginal, joint, and conditional probability.

Recall that marginal probability is the probability of an event, irrespective of other random
variables. If the random variable is independent, then it is the probability of the event directly,
otherwise, if the variable is dependent upon other variables, then the marginal probability is the
probability of the event summed over all outcomes for the dependent variables, called the sum
rule.

 Marginal Probability: The probability of an event irrespective of the outcomes of other

random variables, e.g. P(A).

The joint probability is the probability of two (or more) simultaneous events, often described in
terms of events A and B from two dependent random variables, e.g. X and Y. The joint
probability is often summarized as just the outcomes, e.g. A and B.

 Joint Probability: Probability of two (or more) simultaneous events, e.g. P(A and B) or
P(A, B).

The conditional probability is the probability of one event given the occurrence of another event,
often described in terms of events A and B from two dependent random variables e.g. X and Y.

 Conditional Probability: Probability of one (or more) event given the occurrence of
another event, e.g. P(A given B) or P(A | B).

The joint probability can be calculated using the conditional probability; for example:

 P(A, B) = P(A | B) * P(B)

This is called the product rule. Importantly, the joint probability is symmetrical, meaning that:

 P(A, B) = P(B, A)

The conditional probability can be calculated using the joint probability; for example:

 P(A | B) = P(A, B) / P(B)

 The conditional probability is not symmetrical; for example:

 P(A | B) != P(B | A)

 An Alternate Way To Calculate Conditional Probability

Now, there is another way to calculate the conditional probability.

Specifically, one conditional probability can be calculated using the other conditional probability; for
example:

 P(A|B) = P(B|A) * P(A) / P(B)

The reverse is also true; for example:

 P(B|A) = P(A|B) * P(B) / P(A)

This alternate approach of calculating the conditional probability is useful either when the joint
probability is challenging to calculate (which is most of the time), or when the reverse conditional
probability is available or easy to calculate.

This alternate calculation of the conditional probability is referred to as Bayes Rule or Bayes
Theorem, named for Reverend Thomas Bayes, who is credited with first describing it. It is
grammatically correct to refer to it as Bayes‟ Theorem (with the apostrophe), but it is common to
omit the apostrophe for simplicity.

 Bayes Theorem: Principled way of calculating a conditional probability without the joint
probability.

It is often the case that we do not have access to the denominator directly, e.g. P(B).

We can calculate it an alternative way; for example:

 P(B) = P(B|A) * P(A) + P(B|not A) * P(not A)

This gives a formulation of Bayes Theorem that we can use that uses the alternate calculation of
P(B), described below:

 P(A|B) = P(B|A) * P(A) / P(B|A) * P(A) + P(B|not A) * P(not A)

Or with brackets around the denominator for clarity:

 P(A|B) = P(B|A) * P(A) / (P(B|A) * P(A) + P(B|not A) * P(not A))

Note: the denominator is simply the expansion we gave above.

As such, if we have P(A), then we can calculate P(not A) as its complement; for example:

 P(not A) = 1 – P(A)
 Additionally, if we have P(not B|not A), then we can calculate P(B|not A) as its complement; for
example:

 P(B|not A) = 1 – P(not B|not A)

Now that we are familiar with the calculation of Bayes Theorem, let‟s take a closer look at the
meaning of the terms in the equation.

Naming the Terms in the Theorem

The terms in the Bayes Theorem equation are given names depending on the context where the
equation is used.

It can be helpful to think about the calculation from these different perspectives and help to map your
problem onto the equation.

Firstly, in general, the result P(A|B) is referred to as the posterior probability and P(A) is referred
to as the prior probability.

 P(A|B): Posterior probability.

 P(A): Prior probability.

Sometimes P(B|A) is referred to as the likelihood and P(B) is referred to as the evidence.

 P(B|A): Likelihood.
 P(B): Evidence.

This allows Bayes Theorem to be restated as:

 Posterior = Likelihood * Prior / Evidence

We can make this clear with a smoke and fire case.

Bayes Theorem for Modeling Hypotheses

Bayes Theorem is a useful tool in applied machine learning.

It provides a way of thinking about the relationship between data and a model.

A machine learning algorithm or model is a specific way of thinking about the structured
relationships in the data. In this way, a model can be thought of as a hypothesis about the
relationships in the data, such as the relationship between input (X) and output (y). The practice of
applied machine learning is the testing and analysis of different hypotheses (models) on a given
dataset.

Bayes Theorem provides a probabilistic model to describe the relationship between data (D) and a
hypothesis (h); for example:

 P(h|D) = P(D|h) * P(h) / P(D)

Breaking this down, it says that the probability of a given hypothesis holding or being true given
some observed data can be calculated as the probability of observing the data given the hypothesis
multiplied by the probability of the hypothesis being true regardless of the data, divided by the
probability of observing the data regardless of the hypothesis.
 Under this framework, each piece of the calculation has a specific name; for example:

 P(h|D): Posterior probability of the hypothesis (the thing we want to calculate).

 P(h): Prior probability of the hypothesis.

This gives a useful framework for thinking about and modeling a machine learning problem.

If we have some prior domain knowledge about the hypothesis, this is captured in the prior
probability. If we don‟t, then all hypotheses may have the same prior probability.

If the probability of observing the data P(D) increases, then the probability of the hypothesis holding
given the data P(h|D) decreases. Conversely, if the probability of the hypothesis P(h) and the
probability of observing the data given hypothesis increases, the probability of the hypothesis
holding given the data P(h|D) increases.

The notion of testing different models on a dataset in applied machine learning can be thought of as
estimating the probability of each hypothesis (h1, h2, h3, … in H) being true given the observed
data.

The optimization or seeking the hypothesis with the maximum posterior probability in modeling is
called maximum a posteriori or MAP for short.

Under this framework, the probability of the data (D) is constant as it is used in the assessment of
each hypothesis. Therefore, it can be removed from the calculation to give the simplified
unnormalized estimate as follows:

 max h in H P(h|D) = P(D|h) * P(h)

If we do not have any prior information about the hypothesis being tested, they can be assigned a
uniform probability, and this term too will be a constant and can be removed from the calculation to
give the following:

 max h in H P(h|D) = P(D|h)

That is, the goal is to locate a hypothesis that best explains the observed data.

Fitting models like linear regression for predicting a numerical value, and logistic regression for
binary classification can be framed and solved under the MAP probabilistic framework. This
provides an alternative to the more common maximum likelihood estimation (MLE) framework.

Bayes Theorem for Classification

Classification is a predictive modeling problem that involves assigning a label to a given input data
sample.

The problem of classification predictive modeling can be framed as calculating the conditional
probability of a class label given a data sample, for example:

 P(class|data) = (P(data|class) * P(class)) / P(data)

Where P(class|data) is the probability of class given the provided data.

This calculation can be performed for each class in the problem and the class that is assigned the
largest probability can be selected and assigned to the input data.
 In practice, it is very challenging to calculate full Bayes Theorem for classification.

The priors for the class and the data are easy to estimate from a training dataset, if the dataset is
suitability representative of the broader problem.

The conditional probability of the observation based on the class P(data|class) is not feasible unless
the number of examples is extraordinarily large, e.g. large enough to effectively estimate the
probability distribution for all different possible combinations of values. This is almost never the
case, we will not have sufficient coverage of the domain.

As such, the direct application of Bayes Theorem also becomes intractable, especially as the number
of variables or features (n) increases.

Naive Bayes Classifier

The solution to using Bayes Theorem for a conditional probability classification model is to simplify
the calculation.

The Bayes Theorem assumes that each input variable is dependent upon all other variables. This is a
cause of complexity in the calculation. We can remove this assumption and consider each input
variable as being independent from each other.

This changes the model from a dependent conditional probability model to an independent
conditional probability model and dramatically simplifies the calculation.

This means that we calculate P(data|class) for each input variable separately and multiple the results
together, for example:

 P(class | X1, X2, …, Xn) = P(X1|class) * P(X2|class) * … * P(Xn|class) * P(class) / P(data)

We can also drop the probability of observing the data as it is a constant for all calculations, for
example:

 P(class | X1, X2, …, Xn) = P(X1|class) * P(X2|class) * … * P(Xn|class) * P(class)

This simplification of Bayes Theorem is common and widely used for classification predictive
modeling problems and is generally referred to as Naive Bayes.

The word “naive” is French and typically has a diaeresis (umlaut) over the “i”, which is commonly
left out for simplicity, and “Bayes” is capitalized as it is named for Reverend Thomas Bayes.

Bayes Optimal Classifier

The Bayes optimal classifier is a probabilistic model that makes the most likley prediction for a new
example, given the training dataset.

This model is also referred to as the Bayes optimal learner, the Bayes classifier, Bayes optimal
decision boundary, or the Bayes optimal discriminant function.

 Bayes Classifier: Probabilistic model that makes the most probable prediction for new examples.

This is different from the MAP framework that seeks the most probable hypothesis (model). Instead,
we are interested in making a specific prediction.
 The equation below demonstrates how to calculate the conditional probability for a new instance (vi)
given the training data (D), given a space of hypotheses (H).

 P(vj | D) = sum {h in H} P(vj | hi) * P(hi | D)

Where vj is a new instance to be classified, H is the set of hypotheses for classifying the
instance, hi is a given hypothesis, P(vj | hi) is the posterior probability for vi given hypothesis hi,
and P(hi | D) is the posterior probability of the hypothesis hi given the data D.

Selecting the outcome with the maximum probability is an example of a Bayes optimal
classification.

Any model that classifies examples using this equation is a Bayes optimal classifier and no other
model can outperform this technique, on average.

We have to let that sink in. It is a big deal.

Because the Bayes classifier is optimal, the Bayes error is the minimum possible error that can be
made.

 Bayes Error: The minimum possible error that can be made when making predictions.

It is a theoretical model, but it is held up as an ideal that we may wish to pursue.

The Naive Bayes classifier is an example of a classifier that adds some simplifying assumptions and
attempts to approximate the Bayes Optimal Classifier.

More Uses of Bayes Theorem in Machine Learning

Developing classifier models may be the most common application on Bayes Theorem in machine
learning.

Nevertheless, there are many other applications. Two important examples are optimization and
causal models.

Bayesian Optimization

Global optimization is a challenging problem of finding an input that results in the minimum or
maximum cost of a given objective function.

Typically, the form of the objective function is complex and intractable to analyze and is often non-
convex, nonlinear, high dimension, noisy, and computationally expensive to evaluate.

Bayesian Optimization provides a principled technique based on Bayes Theorem to direct a search of
a global optimization problem that is efficient and effective. It works by building a probabilistic
model of the objective function, called the surrogate function, that is then searched efficiently with
an acquisition function before candidate samples are chosen for evaluation on the real objective
function.

Bayesian Optimization is often used in applied machine learning to tune the hyperparameters of a
given well-performing model on a validation dataset.
Bayesian Belief Networks

Probabilistic models can define relationships between variables and be used to calculate
probabilities.

Fully conditional models may require an enormous amount of data to cover all possible cases, and
probabilities may be intractable to calculate in practice. Simplifying assumptions such as the
conditional independence of all random variables can be effective, such as in the case of Naive
Bayes, although it is a drastically simplifying step.

An alternative is to develop a model that preserves known conditional dependence between random
variables and conditional independence in all other cases. Bayesian networks are a probabilistic
graphical model that explicitly capture the known conditional dependence with directed edges in a
graph model. All missing connections define the conditional independencies in the model.

As such Bayesian Networks provide a useful tool to visualize the probabilistic model for a domain,
review all of the relationships between the random variables, and reason about causal probabilities
for scenarios given available evidence.

The networks are not exactly Bayesian by definition, although given that both the probability
distributions for the random variables (nodes) and the relationships between the random variables
(edges) are specified subjectively, the model can be thought to capture the “belief” about a complex
domain.