Table: Test data

The notion classifier

Besides for regression applications, most supervised algorithms are known as classifiers.

Classifiers

A classifier learns a model in the form of a function, a set of logic rules, the parameters of a probabilistic model, the parameters of a neural network, a set of prototypes, etc.

The classifier will use the model it learned to label new and previously unknown data.

When the target attribute is an integer number, we usually refer to it as a class.

When the target attribute is categorical, we talk about labels.

When the target attribute is a real number, the process involved is a regression.

Formalism

Let us denote X = {x 1 , • • • , x N }, x i ∈ X be the matrix the N observed examples of the training set.

The x i are vectors containing the attributes of each object.

Let Y = {y 1 , • • • , y N }, y i ∈ [1..K ] be the vector containing the labels/classes associated to the observed examples.

We note L = {(x i , y i ), i ∈ [1.

.N]} the training set.

A classifier induced from the traning set L will be denoted ψ(•, L). It is a function that for any vector x i from X associates a class:

ψ(•, L) : X → [1..K ]
Applying ψ on a new object x from the test set will therefore return a class prediction: ŷ = ψ(x, L)

How are patterns and models expressed ? There are 2 extremes: Black box representation: The model, structure or function is impossible to grasp for a human unfamiliar with the generating algorithm.

Examples: Deep learning algorithms

White box representation:

The model and its construction process are easy to understand and reveal which kind of structure to expect.

Examples: Decision trees, K-Nearest neighbors

The different types of models come from various fields such as AI, statistics and research in databases.

The 5 steps of supervised learning The bias-variance trade-off Supervised learning faces several challenges.

The bias-variance trade-off in supervised learning The bias-variance trade-off is a problem in which a supervised algorithm has to achieve simultaneously two seemlingly incompatible goals:

Building a model that gives good results on the validation set.

Building a model that can generalize beyond de training set.

The bias is the error from erroneous assumptions in the learning algorithm or model that usually results in the algorithms missing important links between the input variables and the output, thus leading to underfitting.

The variance is the error caused by a too high sensitivity of the model toward small variations in the training set. This results in overfitting and the model being unable to generalize to data outside of the training set.

Function complexity and amount of training data

The second issue is the available amount of training data when compared to the relative complexity of the real model to be learned:

If the model is simple, a learning algorithm with a high bias and a low variance should be able to learn it from a small amount of data.

If the model is complex, it will only be learnable from a very large amount of training data and using a learning algorithm with a low bias and a high variance.

Remark

Good learning algorithms should be able to adjust their bias-variance tradeoff based on the amount of available data and the apparent complexity of the model to be learned.

Picking the right input variables

The problem with too many input variables Even if the real learning model depends only on a very small number of variables, the algorithm may never figure it out if it is flooded with a very high number of input variables.

The result may end up being a very complex and overfitting model.

Models with too many variables cannot easily be understood and interpreted.

A good understanding of your data and of the problem that you want to modelize will help remove irrelevant features.

Scaling your data may have a huge influence on the results.

It is important to check for correlation between the attributes and to remove redundant variables. Types of trees Decisions trees can be categorized according to three criteria:

The type of data: Numerical, Categorical, Mixed

The type of nodes: Binary leaves, multiple leaves

The overall shape of the tree

Types of trees

Deep trees are usually very biased, can't generalize much outside of their training set and are difficult to interpret.

Setting the right Depth for your tree Most Decision trees algorithms will allow you to choose the maximum depth of your tree.

How Deep is too deep will depend on the complexity of the problem Deeper trees tend towards overfitting, while less deep trees will tend towards underfitting.

The best option is to start from a deep tree and to prune it in a way that minimizes the error on the training set.

While balanced-trees are usually the most preferable option, bushy trees should not be frowned upon in problems with a lot of classes, or when they can help reducing the depth of the tree.

Examples

The Weather Problem The goal of this problem is to determine which weather conditions are the most favorable to let your kids go play outside.

From the resulting tree, we can see that temperature is not among the most relevant parameters here.

Examples

The Weather Problem The same problem can be processed with mixed attributes. A similar tree can be found.

Remark

It usually takes more time to compute a decision tree with numerical values, because of the time required to find the optimal cut value. This example would be labeled Yes by the decision tree.

Examples

The Contact Lenses Data

Intuition

To find out the probability of the previously unseen instance belonging to each class, simply pick the "most probable" class.

These probability are assessed using Bayes theorem applied on the training data.

Introduction

Naive Bayes Classifiers: Introduction

Bayes Theorem p(c j |x) = p(x|c j )p(c j ) p(x)
p(c j |x) The probability of instance x belonging to class c j .

It is the posterior probability. We want to compute it.

p(x|c j ) The probability of generating instance x knowing class c j .

Knowing the distribution function of class c j and the features of x, what is the likelihood of x ?

p(c j ) The a priori probability of class c j .

How frequent is class c j in the training set ?

p(x) The occurrence probability of instance x, also called evidence.

This can often be ignored for a given instance because it is independent from c j , and is often intractable.

Naive Bayes Classifiers: Simple example

One year ago, on my way back from Holland, I was arrested by a police officer names "Claude". I was a bit high and can't remember whether Officer Claude was a male or a female ... Using a bayesian classifier, and a police data base with names and sex, we can try to guess whether it is more likely that officer Claude was a male or a female. We have two classes: c 1 =male and c 1 =female.

Naive Bayes Classifiers: Simple example Naive Bayes with several features

In the previous example there was only one features: the name. What happens when there are more ?

To make the problem simpler, naive Bayes classifiers assume that the attributes have independent distributions (which is not always true).

Independence Hypothesis

Let us note x = {x 1 , ..., x d } a data with d features.

Under the hypothesis that all attributes are independent, we can write:

p(x|c j ) = p(x 1 |c j ) × p(x 2 |c j ) × • • • × p(x d |c j )
Therefore, we have:

p(c j |x) = p(c j ) d i=1 p(x i |c j ) p(x) ∝ p(c j ) d i=1 p(x i |c j )
Naive Bayes with several features

Note that Naive Bayes is not sensitive to irrelevant features.

Naive Bayes with several features

Note that Naive Bayes is not sensitive to irrelevant features.

Remark

This assumes that the estimates of the probabilities are good enough. Therefore the training set must be as big and as unbiased as possible.

Naive Bayes: Properties

Pros

The only things to store are the probabilities: The training data need not be kept in memory and a single scan of the data is necessary to acquire the probabilities.

The model is quite simple to understand.

One of the fastest prediction model.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Naive Bayes: Properties

Pros

The only things to store are the probabilities: The training data need not be kept in memory and a single scan of the data is necessary to acquire the probabilities.

The model is quite simple to understand.

One of the fastest prediction model.

Cons

Naive Bayes assumes that the features are fully independent. It is usually not true and can lead to more or less bias when several of them are too correlated.

Naive Bayes tend to be biased toward the training data and can't generalize easily (e.g. It is impossible to classify a new instance with a single -or more-attribute values the occurrence of which is 0 in the training set).

Mosquito identification

In this example we consider 3 species of mosquitoes:

Culex Pipiens, the common house mosquito Anopheles Stephensi, a common mosquito from the middle East Aedes Aegypti, the yellow fever mosquito (may also carry Dengue fever, Zika, or Chikungunya) Suppose I see a mosquito with a wing frequency of 500Hz, which one is it? Remark It is P(wingbeat|mosquitoe) that follows the normal law and not the other way around !

Mosquito identification

Suppose I see a mosquito with a wing frequency of 500Hz, which one is it?

p(Culex|wingbeat = 500) ∝ exp - (500-390) 2 2×14 2 14 √ 2π ≈ 0 p(Anopheles|wingbeat = 500) ∝ exp - (500-475) 2 2×30 2 30 √ 2π = 0.0094 p(Aedes|wingbeat = 500) ∝ exp - (500-576) 2 2×43 2 43 √ 2π = 0.0019
Without further information, it is most likely an Anopheles.

Mosquito identification: More features

We now have additional informations in the form of a chart representing how many mosquitoes are active depending on the time of the day.

Suppose I am savagely attacked by a mosquito with a wingbeat frequency of 420Hz at 11:30am. Which one is the most likely culprit knowing that Culex are 30% of the population in France, Anopheles 50% and Aedes 20% ?

Remarks

At this point you should be wondering where was the training set in this example.

You

1-Nearest Neighbor

The simplest and laziest classifier consists in using the training set itself as a model without building or computing anything.

1-NN Classifier "Learning" process: Remember all the observed examples.

Classification process: When a new data arrives, find the most similar registered example (distance-wise) and assign it to the same class.

1-Nearest Neighbor

The 1-Nearest Neighbor classifier is sensitive to noise and prone to overfitting.

Figure : The 1-NN algorithm would assign this data to the red class. On the other hand, a majority vote would assign it to the blue class.

K-Nearest Neighbors

The K-Nearest Neighbors algorithm (KNN) considers the K closest observed data from the training set to decide on a class for an unlabeled data. K is a parameter chosen by the user. Because the distance between instances is based on all the attributes, less relevant attributes and even the irrelevant ones are used in the classification of a new instance.

Because the algorithm delays all processing until a new classification/prediction is required, significant processing is needed to make the prediction.

Learning without remembering all the data

The main issues of the KNN algorithm is that all data have to be kept in memory and that it is unstable when classes that are not well separated: It's a problem with both large and complex datasets.

Idea

Instead of using all the data, we could use a prototype representing each class (like in the mean-shift and K-Means algorithm).

Can be learned incrementally.

Helps building a model.

Issues

Works only with spherical classes Doesn't work with classes that aren't well separated.

Learning without remembering all the data Learning Vector Quantization algorithm

The LVQ algorithm (Kohonen) is a primitive neural network classifier that represents the classes from the training set using several prototypes per class.

It is closely related to both the K-Means and the KNN algorithm.

It is an early ancestor to the Self-Organizing Maps

Remark

In many neural networks algorithms, prototypes learned from an iterative process are called neurons due to their evolutive behavior and the fact that thay do not represent a cluster or class on their own.

Learning Vector Quantization algorithm : Training

1 Initialization: Set up the initial M prototypes Z = {z 1 , • • • , z M }.
It can be done randomly or using an initialization with the K-Means algorithm. Then use a majority vote to assign each of prototype to a class C (z m ). Choose a learning rate ∈ [0, 1].

2 Go through the training set and update Z for each observation:

For each observation x i , find the nearest prototype

z m . If C (x i ) = C (z m ), move z m towards x i : z m ← z m + (x i -z m ). If C (x i ) = C (z m ), move z m away from x i : z m ← z m -(x i -z m )
3 Repeat step 2 until convergence.

Optional: Reduce after each step 2 to enhance convergence.

Remark

The learning rate is a critical parameter that can change drastically the outcome of the classification.

Learning Vector Quantization: Classification

Once the prototypes have been learned, the LVQ classifier behaves like the 1-NN algorithm using the prototypes instead of the training data.

The class of each presented unlabeled data is determined based on the class of the closest prototype.

Remark

Using LVQ, the prototype can be trained (updated) in real time while being use on unlabeled data. This algorithm is therefore great for online learning.

LVQ vs KNN

Use KNN when: You have a relatively small data set, you don't need to build a model, you don't need to generalize from your training set.

Use LVQ when: You have a large data set, you need to build a model, you are dealing with a semi-supervised problem, you need to learn data incrementaly or on-line, you can afford a slightly lower accuracy or want a higher variance.

Remark

For simple problems, both will work just fine.

Support Vector Machines (1/2)

The Support Vector Machine algorithm is another somewhat distance-based algorithm proposed by Vapnik in the 90's and whose aim is to find a hyperplane of space that separates different classes.

Let us suppose that the training data are linearly separable: There is at least 1 hyperplane (or a line in 2D) that can separate the data. But which one is the best ?

SVMs : 3 Key ideas Use optimization to find the solutions (the best hyperplane) with as few errors as possible.

Seek large margin separators to improve the generalization Use kernel trick to make large feature spaces computationally efficient or to tackle non-linear cases.

Linear case optimization

For each point (x t , y t ), with y t = {-1; +1}, we want:

w .x t + b ≥ 1 if y t = +1 w • x t + b ≤ -1 if y t = -1
Equivalently, we have : ∀t, y t (w • x t + b) ≥ 1.

Linear case optimization

For each point (x t , y t ), with y t = {-1; +1}, we want:

w .x t + b ≥ 1 if y t = +1 w • x t + b ≤ -1 if y t = -1
Equivalently, we have : ∀t, y t (w • x t + b) ≥ 1.

Simple optimization

So long as the linear separator exists, this can easily be solved using methods such as the simplex algorithm, or other optimization algorithms.

The non-linear case

Without linear separation, if we formulate the problem with a 0-1 loss, we have:

min w ,b t 0,1 (y t , w • x t + b) where 0,1 (y , ŷ ) = 1[y = sign(ŷ )]
Can we solve it ? Unfortunately, this is a NP-hard problem in the worst cases.

Using the hinge loss hinge (y , ŷ ) = max(0, 1 -y • ŷ ) simplifies the problem.

Soft margins and slack variables (1/2)

Modeling potential errors

In real problems, a perfect classification is not feasible. Some instances are in the wrong side of the margins.

ξ i = 0 instance is in the right side of the hyperplane and the margin. We leave it alone ! ξ i ≤ 1 instance is within the margin but on the wrong side of the hyperplane.

ξ i > 1 instance is misclassified and on the wrong side of the margin.

Soft margins and slack variables (2/2)

The system to minimize with the slack variables

min w ,b,ξ 1 2 ||w || 2 + C i ξ i
With C a margin parameter, y i (w • x i + b) ≥ 1 -ξ i , and ξ i ≥ 0.

Influence of the margin parameter A C too high will lead to overfitting.

A C too low will lead to underfitting.

SVMs: Kernel trick

A Kernel trick consists in applying a mathematical function to the original data (or data space) in order to transform them into data more easy to tackle.

Creating extra variables from the original ones can help finding a higher dimension hyperplane that may separate otherwise non-separable data.

Space transformations using kernel tricks makes it possible to tackle separators with shapes other than lines.

Many Kernel functions exists, but only a few have interesting properties.

Introduction Decision trees

Naive Bayes Classifiers

Distance-based approaches

Validation Criteria

Bibliography

Evaluating classifiers

The evaluation of a classifier is usually done using the validation set, the labels of which are known.

There are several ways to validate classifier results depending on their type and the number of classes. The specificity (or TNR) is a statistical measure of how well a binary classifier correctly identifies the negative cases.

Evaluating binary classifiers

Precision or Positive Predictive Value (PPV) precision = TP TP + FP The precision is the probability that a predicted positive case is really positive.

F-Measure

F-Measure = 2 × precision × recall precision + recall

The F-Measure is the harmonic mean of the precision and the recall.

It can be used as a single measure to evaluate the performances of a binary classifier.

Evaluating binary classifiers

Generalizing to non-binary classifiers

Generalizing to classifiers that have more than 2 classes is often complicated.

Criteria exist in the literature but they are often quite complex and restricted to specific cases.

It is possible to do some basic analysis using confusion matrices between the expected classes and the found classes.

Otherwise, indexes such as the accuracy, or vector comparing measures (e.g. Rand Index and Adjusted Rand Index) are good solutions.

Introduction

  (c) Example of a binary tree (d) Example of a numerical nonbinary tree

  Suppose that we are trying to classify persons gender based on several features, including eye color (which is irrelevant):p(Jessica|c j ) = p(eye = brown|c j ) × p(wears dress = yes|c j ) × • • • p(Jessica|female) = 9000/10000 × 7500/10000 × • • • p(Jessica|male) = 9001/10000 × 3/10000 × • • •p(eye = brown|female) and p(eye = brown|male) should be almost identical and won't affect the outcome much. Wearing a dress however ...

  Suppose that we are trying to classify persons gender based on several features, including eye color (which is irrelevant):p(Jessica|c j ) = p(eye = brown|c j ) × p(wears dress = yes|c j ) × • • • p(Jessica|female) = 9000/10000 × 7500/10000 × • • • p(Jessica|male) = 9001/10000 × 3/10000 × • • •p(eye = brown|female) and p(eye = brown|male) should be almost identical and won't affect the outcome much. Wearing a dress however ...

  N (µ = 390, σ = 14) Anopheles Stephensis: N (µ = 475, σ = 30) Aedes Aegypti: N (µ = 567, σ = 43)

Figure :

 : Figure: For K>1, the KNN algorithm would assign this unlabeled data to the blue class.

Figure : A

 : Figure: A single prototype per class will never work here ...

AccuracyFP:

  Binary classifiers (with 2 classes: True and False) have specific validations measures that assess different parameters. Let us consider the following notations: TP: True positive (data classified True and that are really in this class) False positive (data classified True but are not) TN: True negative (data classified False and are really in this class) FN: False negative (data classified False but are actually True) Remark Accuracy = TP + TN TP + TN + FP + FN Fall-out or False Positive Rate (FPR) FPR = FP TN + FP specificity (SPC) or True Negative Rate specificity = TN TN + FP = 1 -FPR

  Supervised data are described by several attributes and a target class (or label), which is known in the training and validation set, but unknown in the test set.

	Supervised Learning data sets examples
	Introduction
	Decision trees Size Weight Shoe size Sex	Size Weight Shoe size Sex
	176	72	43	M	205	85	47	?
	Naive Bayes Classifiers 159 61 37	F	172	60	40	?
	180	66	39	F	164	57	38	?
	Distance-based approaches 185 85 44	M	169	52	36	?
	177	70	41	F	183	78	42	?
	155	88	38	M	175	65	44	?
	210	110	45	M	191	77	41	?
		Table: Training data

  They are mostly applied to categorical data, but not only. They decompose the feature space according to the most discriminating variable at each stage. There are usually more than one possible tree per data set.

		Introduction Introduction Introduction
	Decision trees Decision trees Decision tree: Classification Process
	Introduction Decisions trees are very common classifiers that mine rules from the A decision tree is a tree of a function-discrete representation. It can be training set: used as a decision support tool that uses a tree-like graph or model of
	decisions and their possible consequences. Learning decision trees are
	Decision trees among the most commonly used classification methods. The main
	algorithms are ID3, ID4, C4.5 and C5.0
	Naive Bayes Classifiers Properties
	Expressiveness: It can represent disjunctions of conjunctions Distance-based approaches Readability: It can be translated as a set of decision rules
	Validation Criteria Notae
	Bibliography Disjunction : A or B
	Conjunction : A and B
	J. Sublime	Data Analysis -Lecture 7	ISEP 2021/2022

  never saw the training set, you only saw the model: Wing beat frequencies distributions and mosquito activity diagram. The training set was used to build the wing beat frequencies laws and the distribution diagram. Once you have them, you don't need the training set anymore.

	Introduction
	Decision trees
	Naive Bayes Classifiers
	Important remark Distance-based approaches
	You saw normalization constants pretty much everywhere in the calculi. You don't need them to classify new items. Unless you really want Validation Criteria
	probabilities, you don't have to normalize your results. In most cases, you don't compute anything and the algorithm does it for you ! Bibliography

  TP, FP, TN and FN provide relevant informationNo single measure tells the whole story A classifier with 90% accuracy can be useless if 90% of the population does not have cancer and the 10% that do are misclassified.If possible, use multiple measures. Beware of the obscure terminological confusion in the literature ! Depending on the field, specificity is sometimes refers to precision Different name exist for the same thing Always provide the formula when you use terms such as FP, TP, etc.

J. SublimeData Analysis -Lecture 7 ISEP 2021/2022

Cons

The process to build the tree is complex There are always several possible trees Choosing the depth of the tree is a complex decision Does not work well with datasets that have too many attributes.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Mosquito identification

Suppose I see a mosquito with a wing frequency of 500Hz, which one is it?

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Mosquito identification: Getting the probability

Similarity and distance

Very much like in clustering, the distance function is a key element for many supervised classifiers.

Creating custom distance functions is sometimes required.

Weighted Nearest Neighbors

The Weighted Nearest Neighbors solves 2 of the previous problems by adding a weight w k to each neighbor.

Examples:

Remark

The real Weighted Nearest Neighbors classifier uses a much more complex weight system that satisfies N n=1 w ni = 1.

K-Nearest Neighbors: Summary

LVQ vs KNN

In the bias variance trade-off, 1-NN tends toward bias while LVQ tends toward variance. KNN is somewhere in between depending on the value of K .

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Support Vector Machines (2/2)

The goal of the SVM algorithm is to fine the linear separator with the largest margin.

Good according to intuition, theory and practice. SVM became famous when, using images as input, it gave accuracy comparable to neural-network with hand-designed features in a handwriting recognition task. Evaluating binary classifiers: ROC space

The ROC space (Receiver operating characteristic) is a type of graph based on the fall-out and the sensitivity and that can be used to evaluate a classifier.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Evaluating binary classifiers: ROC curves A ROC curve plots uses the ROC space to assess the quality of a classifier. It is plotted using different parameters as reference points to draw the curb.

Useful to find the right parameters Useful to compare binary classifiers

Building a model and complexity issues

The complexity of a model is an important criterion to evaluate a model: When comparing several models/classifiers that show similar performances in term of accuracy (or error), and have similar bias and variance, the simplest models are usually considered the best.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Building a model and complexity issues

The complexity of a model is an important criterion to evaluate a model: When comparing several models/classifiers that show similar performances in term of accuracy (or error), and have similar bias and variance, the simplest models are usually considered the best.

Examples of complexity measures

The Bayesian Information Criterion (BIC)

The Akaike Information Criterion (AIC)

For both criteria, the lower the better.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Building a model and complexity issues

The complexity of a model is an important criterion to evaluate a model: When comparing several models/classifiers that show similar performances in term of accuracy (or error), and have similar bias and variance, the simplest models are usually considered the best.

Examples of complexity measures

The Bayesian Information Criterion (BIC)

The Akaike Information Criterion (AIC)

For both criteria, the lower the better.

Remark: Models that are too simple tend to have a low accuracy (high error), while models that are too complex tend too overfit.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Bias-variance trade-off and complexity

The bias tends to decrease with the complexity of the model

The variance tends to increase with the complexity of the model

The mean square error (MSE) on validation data first decreases when the model gets more complex, and then increases again when the model gets too complex and overfit.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022

Bias-variance trade-off and complexity

The bias tends to decrease with the complexity of the model

The variance tends to increase with the complexity of the model

The mean square error (MSE) on validation data first decreases when the model gets more complex, and then increases again when the model gets too complex and overfit.

Deciding between several models relies on finding the one(s) with the best variance-bias trade-off, and the lowest complexity.

J. Sublime Data Analysis -Lecture 7 ISEP 2021/2022


Why do we need stationarity ? From regression to auto-regressive processes

Stochastic process x 1 x 2 • • • x t • • • x T Realization 1 x 1 1 x 1 2 • • • x 1 t • • • x 1 T . . . Realization m x m 1 x m 2 • • • x m t • • • x m T . . . Realization M x M 1 x M 2 • • • x M t • • • x M T Without
In linear regressions, we try to find regressions coefficients to solve an equation of form y = a • x + b + .

For time series predictions, the model is more like x t = ρx t-1 + t ρ is a coefficient to be found t is an error term between the prediction and the real value.

This is what we call an auto-regressive process of order one: AR(1)

Auto-regressive processes

Auto-regressive process of order p An auto-regressive process of order p is defined as follows:

AR(p) :

X t = p i=1 ρ i X t-i + t
the ρ i are parameters t is a white noise term (random noise i.i.d(0, σ 2 ))

Auto-regressive process of order 1 AR(1) :

X t = c + ρX t-1 + t
Auto-regressive processes of order 1: Example (1/2)

Let us consider an oil price problem. The oil price change at a moment t ∆O t is linked to the oil price change at the instant t -1:

∆O t = 0.7 × ∆O t-1 + t J. Sublime Data Analysis -Lecture 8 ISEP 2020/2021

Auto-regressive processes of order 1: Example (1/2)

Let us consider an oil price problem. The oil price change at a moment t ∆O t is linked to the oil price change at the instant t -1:

∆O t = 0.7 × ∆O t-1 + t
If some event occurs, the oil price will suddenly change, resulting in a spike in the oil price change ( spikes).

Auto-regressive processes of order 1: Example (1/2)

Let us consider an oil price problem. The oil price change at a moment t ∆O t is linked to the oil price change at the instant t -1:

∆O t = 0.7 × ∆O t-1 + t
If some event occurs, the oil price will suddenly change, resulting in a spike in the oil price change ( spikes).

Then following this model, the event has some persistent effect until the market stabilizes and the price stops changing.

Auto-regressive processes of order 1: Example (2/2)

The oil price change at a moment t ∆O t is linked to the oil price change at the instant t -1:

∆O t = 0.7 × ∆O t-1 + t

Remark

This is an AR(1) model for the Oil Price Change, but since we use the first derivation of the Oil Price, we will see later that this model is an ARIMA(1,1,0) model of the Oil Price.

Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 )
Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t
Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t X t = ρ 2 X t-2 + ρ t-1 + t ⇒ X t = ρ t X 0 + t-1 i=0 ρ i t-i
Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t X t = ρ 2 X t-2 + ρ t-1 + t ⇒ X t = ρ t X 0 + t-1 i=0 ρ i t-i
The first condition for stationarity is :

E[X t ] = Cte
Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t X t = ρ 2 X t-2 + ρ t-1 + t ⇒ X t = ρ t X 0 + t-1 i=0 ρ i t-i
The first condition for stationarity is :

E[X t ] = Cte E[X t ] = ρ t E[X 0 ] + t-1 i=0 ρ i E[ t-i ] = ρ t E[X 0 ]
Stationarity conditions of an AR(1) Process 1/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t X t = ρ 2 X t-2 + ρ t-1 + t ⇒ X t = ρ t X 0 + t-1 i=0 ρ i t-i
The first condition for stationarity is :

E[X t ] = Cte E[X t ] = ρ t E[X 0 ] + t-1 i=0 ρ i E[ t-i ] = ρ t E[X 0 ]
Condition on the mean For this term to be constant, we need E[X 0 ] = 0 and therefore E[X t ] = 0.

Stationarity conditions of an AR(1) Process 2/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) Var (X t ) = ρ 2 Var (X t-1 ) + Var ( t ) NB: var (aX ) = a 2 var (X )
Stationarity conditions of an AR(1) Process 2/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) Var (X t ) = ρ 2 Var (X t-1 ) + Var ( t ) NB: var (aX ) = a 2 var (X )
We want the variance to be constant:

Var (X t ) = Var (X t-1 )
Stationarity conditions of an AR(1) Process 2/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) Var (X t ) = ρ 2 Var (X t-1 ) + Var ( t ) NB: var (aX ) = a 2 var (X )
We want the variance to be constant:

Var (X t ) = Var (X t-1 )
We substitute in the previous expression, and we get:

Var (X t ) = ρ 2 Var (X t ) + σ 2
Stationarity conditions of an AR(1) Process 2/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) Var (X t ) = ρ 2 Var (X t-1 ) + Var ( t ) NB: var (aX ) = a 2 var (X )
We want the variance to be constant:

Var (X t ) = Var (X t-1 )
We substitute in the previous expression, and we get:

Var (X t ) = ρ 2 Var (X t ) + σ 2 ⇒ (1 -ρ 2 )Var (X t ) = σ 2
Stationarity conditions of an AR(1) Process 2/2

X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) Var (X t ) = ρ 2 Var (X t-1 ) + Var ( t ) NB: var (aX ) = a 2 var (X )
We want the variance to be constant:

Var (X t ) = Var (X t-1 )
We substitute in the previous expression, and we get:

Var (X t ) = ρ 2 Var (X t ) + σ 2 ⇒ (1 -ρ 2 )Var (X t ) = σ 2
Conditions on the variance and on ρ

Var

(X t ) = σ 2 1 -ρ 2
Since we don't want a negative variance or a null denominator, we deduce that |ρ| < 1

Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i J. Sublime Data Analysis -Lecture 8 ISEP 2020/2021
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i )
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i ) = Cov (X t , ρ h X t )
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i ) = Cov (X t , ρ h X t ) = ρ h Cov (X t , X t ) = ρ h Var (X t )
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i ) = Cov (X t , ρ h X t ) = ρ h Cov (X t , X t ) = ρ h Var (X t ) = ρ h σ 2 1 -ρ 2
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i ) = Cov (X t , ρ h X t ) = ρ h Cov (X t , X t ) = ρ h Var (X t ) = ρ h σ 2 1 -ρ 2 Cor (X t , X t+h ) = Cov (X t , X t+h ) Var (X t ) = ρ h
Stationary covariance and weak dependence of an AR(1) process

From our previous calculi, we know that:

X t+h = ρ h X t + h-1 i=0 ρ i t+h-i Cov (X t , X t+h ) = Cov (X t , ρ h X t + h-1 i=0 ρ i t+h-i ) = Cov (X t , ρ h X t ) = ρ h Cov (X t , X t ) = ρ h Var (X t ) = ρ h σ 2 1 -ρ 2 Cor (X t , X t+h ) = Cov (X t , X t+h ) Var (X t ) = ρ h

Weak dependence condition

We want lim h→∞ Cor (X t , X t + h) = 0, so once we find once again that we need |ρ| < 1.

Stationary VS non Stationary AR(1)

Figure: ρ = 0.5
Stationary VS non Stationary AR(1)

Figure: ρ = 0.95
Stationary VS non Stationary AR(1)

Figure: ρ = 1
Stationary VS non Stationary AR(1)

Figure: ρ = -1.002
Moving average processes A moving average mode is a common approach for modeling univariate time series. In this model, the output variable depends linearly on the current and various past values of a stochastic (imperfectly predictable term).

Moving average model of order q: MA(q) MA(q) :

X t = µ + t + q i=1 θ i • t-i
µ is the mean of the series (often assumed to be 0)

The θ i are the parameters t , • • • , t-q are white noise error terms.

Moving average model of order 1: MA(1)

MA(1) :

X t = µ + t + θ • t-1
Example of MA processes 1/2 Let us consider an example in which we want a model for the daily demand for soda bottles in a grocery store:

Demand = 25 + t -0.5 • t-1
25 is the average number of bottles usually sold in a day.

In this example, t could be the change in temperature: t = ∆ temp (t)

Example of MA processes 1/2 Let us consider an example in which we want a model for the daily demand for soda bottles in a grocery store:

Demand = 25 + t -0.5 • t-1
25 is the average number of bottles usually sold in a day.

In this example, t could be the change in temperature: t = ∆ temp (t)

The explanation for the "-0.5 • t-1 " term is that, if the temperature already increased yesterday, the customers already bought soda and don't need to buy more today.

Example of MA processes 1/2 Let us consider an example in which we want a model for the daily demand for soda bottles in a grocery store:

Demand = 25 + t -0.5 • t-1
25 is the average number of bottles usually sold in a day.

In this example, t could be the change in temperature: t = ∆ temp (t)

The explanation for the "-0.5 • t-1 " term is that, if the temperature already increased yesterday, the customers already bought soda and don't need to buy more today.

Further terms could be added:

Demand = 25 + t -0.5 • t-1 -0.25 t-2
Example of MA processes 2/2

We go back to an oil price example:

OilPrice = 45 + t + 0.5 t-1
45$ is the usual average price for a barrel t here could be used for modeling issues in oil delivery (hurricane at sea, blockade, strikes, armed conflicts, etc.)

Example of MA processes 2/2

We go back to an oil price example:

OilPrice = 45 + t + 0.5 t-1
45$ is the usual average price for a barrel t here could be used for modeling issues in oil delivery (hurricane at sea, blockade, strikes, armed conflicts, etc.) If there is a hurricane at sea at time t, the price will increase.

If there was an issue at time t -1, the supply may still be recovering so the prices are still higher than usual, hence the "+0.5 t-1 " term.

Example of MA processes 2/2

We go back to an oil price example:

OilPrice = 45 + t + 0.5 t-1
45$ is the usual average price for a barrel t here could be used for modeling issues in oil delivery (hurricane at sea, blockade, strikes, armed conflicts, etc.) If there is a hurricane at sea at time t, the price will increase.

If there was an issue at time t -1, the supply may still be recovering so the prices are still higher than usual, hence the "+0.5 t-1 " term.

Remark

Unlike in the previous oil price example, we study the oil price, and not the oil price change ! It is not the same model.

MA(1) process: stationarity and weak dependency 1/2

X t = µ + t + θ • t-1 with t ∼ iid(0, σ 2 ) E[X t ] = E[µ + t + θ • t-1 ] = µ + E[ t ] + θE[ t-1 ] = µ Var (X t ) = Var (µ + t + θ • t-1 ) = Var ( t ) + θ 2 Var ( t-1 ) = σ 2 (1 + θ 2 )
Stationarity: conditions on the mean and variance The condition for a weak stationarity are always respected since we have both the mean and the variance that are constant.

MA(1) process: stationarity and weak dependency 2/2

For the third stationarity hypothesis, we want Cov (X t , X t+h ) to be a function of h independent from t.

MA(1) process: stationarity and weak dependency 2/2

For the third stationarity hypothesis, we want Cov (X t , X t+h ) to be a function of h independent from t.

Cov

(X t , X t-1 ) = Cov ( t + θ • t-1 , t-1 + θ • t-2 ) = θCov ( t-1 , t-1 ) = θσ 2
because the t are iid MA(1) process: stationarity and weak dependency 2/2

For the third stationarity hypothesis, we want Cov (X t , X t+h ) to be a function of h independent from t.

Cov

(X t , X t-1 ) = Cov ( t + θ • t-1 , t-1 + θ • t-2 ) = θCov ( t-1 , t-1 ) = θσ 2 because the t are iid
From there we can infer that:

∀τ > 1 Cov (X t , X t-τ ) = Cov ( t + θ • t-1 , t-τ + θ • t-1-τ ) = 0
MA(1) process: stationarity and weak dependency 2/2

For the third stationarity hypothesis, we want Cov (X t , X t+h ) to be a function of h independent from t.

Cov

(X t , X t-1 ) = Cov ( t + θ • t-1 , t-1 + θ • t-2 ) = θCov ( t-1 , t-1 ) = θσ 2 because the t are iid
From there we can infer that:

∀τ > 1 Cov (X t , X t-τ ) = Cov ( t + θ • t-1 , t-τ + θ • t-1-τ ) = 0

Stationarity and dependency

With the 3 conditions being respected, we can conclude that an MA(1) process is always stationary. Furthermore, with the third condition, the weak dependence hypothesis is easily verified. Telling MA(1) from AR(1)

MA(1) process: Example

Sometimes, just looking at the time series curb is not enough to tell whether it follows an AR(1) model, a MA(1) model, or something else.

The best solution to guess MA(1) from AR( 1) is to look at the correlation Corr (X t , X t+h )

MA(1) : Corr (X t , X t+h ) = θ 1-θ 2 if h = 1 0 if h > 1 AR(1) : Corr (X t , X t+h ) = ρ h ARMA model ARMA(p,q)
An ARMA(p,q) process, is a model that contain an AR(p) process and and MA(q) process:

X t = µ + t + p i=1 ρ i X t-i + q i=1 θ i • t-i
The constant µ is the expectation of X t (often assumed to be 0 and not taken into consideration in the regressive term).

The ρ i and θ i are the parameters from the auto-regressive and moving average process respectively.

The i are white error terms.

ARMA(1,1)

ARMA(1, 1) :

X t = µ + t + ρX t-1 + θ • t-1 ARMA(1,1), Example 1
Let us consider a good sales problem:

Sales t = t + ρSales t-1 + θ • t-1
ρ is a loyalty effect from the customer to the good. Let's take ρ = 0.9 t represents free coupons given at a time t. θ is a negative effect due to the fact that people already bought the product at time t -1. Let's take θ = -0.3

ARMA(1,1), Example 1

We see that at the beginning the MA process causes a rapide decline in sales.

Then, once the MA effect is over, the sales decrease following an AR process.

ARMA(1,1), Example 1

We see that with θ > 0, there is a huge initial boost on the sale. It is again followed by an AR type decay process which takes more time due to the initial higher boost effect. Guessing the parameters of any ARMA(p,q) model (1/5)

ARMA(1,1) behavior examples

Lagged values

The lagged values of a time series are its values of tx considered at time t.

Lagged values are often used for correlation analysis between a series at time t and tx.

ACF: Autocorrelation function

The autocorrelation function is the value of the correlation between the series at time t and each of its values at time tx.

Guessing the parameters of any ARMA(p,q) model (1/5)

Lagged values

The lagged values of a time series are its values of tx considered at time t.

Lagged values are often used for correlation analysis between a series at time t and tx.

ACF: Autocorrelation function

The autocorrelation function is the value of the correlation between the series at time t and each of its values at time tx.

PACF: Partial autocorrelation functions

The partial autocorrelation is like the autocorrelation, but controlled for smaller lags. For example: the PACF at t -2 discards any correlation that might have shown at t -1.

ACF and PACF are usually similar for the first lag, but diverge afterwards.

Guessing the parameters of any ARMA(p,q) model (2/5)

The values p and q of any ARMA model can be guessed using two tools:

The autocorrelogram for the q of the MA model.

The partial autocorrelogram for p of the AR model.

Partial autocorrelation

In time series analysis, the partial autocorrelation function (PACF) gives the partial correlation of a time series with its own lagged values, controlling for the values of the time series at all shorter lags. It contrasts with the autocorrelation function, which does not control for other lags.

α(h) = Cor (x t+h -P t,h (x t+h ), x t -P t,h (x t ))
with P t,h (x) the projection of x onto the space spanned by

x t+1 , • • • , x t+h-1 .
Guessing the parameters of any ARMA(p,q) model (3/5)

Autocorellation and partial autocorrelation confidence intervals.

Under the null hypothesis that we expect 0 autocorrelation, the confidence interval for 95% is:

P0.95 = 0 ± 2 √ T
Anything outside of these intervals denotes an autocorrelation and can be used to identify the type of ARMA(p,q) model. Guessing the parameters of any ARMA(p,q) model (4/5)

ACF and PACF: how to read ?

The ACF of a stationary AR(p) model goes to zero at an exponential rate, while the PACF becomes zero after lag p.

For an MA(q) model, it is the opposite: the ACF cuts off brutally after lag q and the PACF goes to zero relatively quickly. Guessing the parameters of any ARMA(p,q) model (5/5) Tips to interpret PACF and ACF High values for p and q are highly suspicious. Check if your result makes sense depending on the application field.

AR model may have echo phenomenons: An AR( 2) models may show echoes on lags 4 and 6. Once again, high values are suspicious.

An isolated spike on a high value lag out of the confidence interval is probably just noise.

Important remarks

Depending on your software, your ACF and PACF graphs may look very different and it can be confusing : Lag 0 should have an auto-correlation of 1.

In R, the PACF starts at lag = the number of time the series was differentiated.

ACF and PACF readings are not enough, and several models still need to be tested based on their likelihood and performances.

Guessing the parameters of any ARMA(p,q) model: Example

Guessing the parameters of any ARMA(p,q) model: Example

The autocorrelations are significant for a large number of lags. But perhaps the autocorrelations beyond lag 1 are merely due to the propagation of autocorrelation at lag 1. This is confirmed by the PACF: This could be an ARMA(1,0)

Guessing the parameters of any ARMA(p,q) model: Example

The autocorrelations are significant for a large number of lags. But perhaps the autocorrelations beyond lag 1 are merely due to the propagation of autocorrelation at lag 1. This is confirmed by the PACF: This could be an ARMA(1,0) Remark: The ACF does not go down exponentially which means that the series may need to be differenciated (see ARIMA)

From ARMA to ARIMA

We have seen that with time series we are not always working directly with the original series, but quite often with its differentiated version.

ARIMA : definiton

The ARIMA(p,d,q) model is an ARMA(p,q) model applied to the d-th derivation of a time series.

From ARMA to ARIMA

We have seen that with time series we are not always working directly with the original series, but quite often with its differentiated version.

ARIMA : definiton

The ARIMA(p,d,q) model is an ARMA(p,q) model applied to the d-th derivation of a time series.

The parameter d is usually found by trying several values incrementally until fitting model is found.

Parameters p and q are found using the same methods (acf and pacf) than for classical ARMA models on a given d-th derivation.

From ARMA to ARIMA

We have seen that with time series we are not always working directly with the original series, but quite often with its differentiated version.

ARIMA : definiton

The ARIMA(p,d,q) model is an ARMA(p,q) model applied to the d-th derivation of a time series.

The parameter d is usually found by trying several values incrementally until fitting model is found.

Parameters p and q are found using the same methods (acf and pacf) than for classical ARMA models on a given d-th derivation.

Remark: Unless you are dealing with a very complicated phenomenon, d rarely goes beyond 2.

Rules to Guess the number d parameter in ARIMA (1/2)

Rule 1 : If a series has a positive autocorrelation out to a high number of lags, then it probably needs a higher order of differencing.

Rule 2 : If the lag-1 autocorrelation is 0 or negative, or the autocorrelations are all small and patternless, then the series does not need a higher order of differencing. If the lag-1 autocorrelation is -0.5 or more negative, the series may be overdifferenced. BEWARE OF OVERDIFFERENCING !

Rule 3: The optimal order of differencing is often the order of differencing at which the standard deviation is lowest.

Rules to Guess the number d parameter in ARIMA (2/2)

Rule 4:

A model without differencing assumes that the original series is stationary (mean-reverting).

A model with one order of differencing assumes that the original series has a constant average trend (e.g. a random walk or SES-type model, with or without growth).

A model with two orders of total differencing assumes that the original series has a time-varying trend (e.g. a random trend).

Rule 5:

A model without differencing normally includes a constant term (which allows for a non-zero mean value). A model with two orders of total differencing normally does not include a constant term.

In a model with one order of total differencing, a constant term should be included if the series has a non-zero average trend.

Limits of the ARIMA model ARIMA models have several limits:

They can only handle univariate data

The parameters are quite complex to guess and the properties difficult to assess when the parameters p and q grow beyond 2.

These models do not allow for an in depth analysis of a time series (series segmentation event detection, state detection, etc.)

  stationarity, these two measures are different:Ensemble Mean: E(x t ) = 1

Figure :

 : Figure: Example of a MA(1) process (θ = -0.3)

Figure

  Figure: ρ = 0.95 and θ = 3

  Figure: A possible ARMA(1,2) or ARMA(11,2)

  Figure: A possible ARMA(1,2) or ARMA(11,2)

J. SublimeData Analysis -Lecture 8 ISEP 2020/2021

Stationarity conditions of an AR(1) Process 1/2 X t = ρX t-1 + t with t ∼ iid(0, σ 2 ) X t = ρ (ρX t-2 + t-1 ) + t X t = ρ 2 X t-2 + ρ t-1 + t J. Sublime Data Analysis -Lecture 8 ISEP 2020/2021

Stationarity conditions of an AR(1) Process 2/2 X t = ρX t-1 + t with t ∼ iid(0, σ 2 )

J. Sublime Data Analysis -Lecture 8 ISEP 2020/2021

Stationarity conditions of an AR(1) Process 2/2 X t = ρX t-1 + t with t ∼ iid(0, σ 2 )

ARMA(1,1) properties ARMA processes have the same properties than AR processes when it comes to stationarity and the weak dependence hypothesis:

The mean value of the series should be 0.

J. Sublime Data Analysis -Lecture 8 ISEP 2020/2021

Guessing the parameters of any ARMA(p,q) model (1/5)

Lagged values

The lagged values of a time series are its values of tx considered at time t.

Lagged values are often used for correlation analysis between a series at time t and tx.


Thomas C Mendenhall

Word2vec Conclusion

Roughly summed up:

Text Mining is statistics oriented.

NLP is analysis oriented. Sentiment Analysis is also known as "opinion mining"

Outline

It determines the attitude, polarity, or emotions from documents Polarity : positive, negative, neutral Emotions: angry, sad, happy, bored, afraid, etc.

Method

Document Summarization

Extract the major key points of a document to create a summary Methods Extraction: select a subset of existing words, phrases, or sentences to build a summary Abstraction: use natural language generation techniques to build a summary that is similar to natural language Tokenization: Bag of words (1/2)

Tokenization is the process of splitting a stream of characters intos sentences, symbols, or words. For text mining, we are particularly interested in words.

Tokenization: Bag of words (1/2)

Tokenization is the process of splitting a stream of characters intos sentences, symbols, or words. For text mining, we are particularly interested in words.

I) Identifying the words (tokens) of a document

The word delimiter identification is important. It will often be spaces or punctuation.

Some characters are less obvious : e.g. "-" might be a delimiter in English language, but not always in French.

Tokenization: Bag of words (1/2)

Tokenization is the process of splitting a stream of characters intos sentences, symbols, or words. For text mining, we are particularly interested in words.

I) Identifying the words (tokens) of a document

The word delimiter identification is important. It will often be spaces or punctuation.

Some characters are less obvious : e.g. "-" might be a delimiter in English language, but not always in French.

II) Creating a dictionary

Potentially, the number of words is very important and there may be redundancies.

It will be necessary to treat the redundancies. For instance using stemming or lemmatization : Putting all words to their root form.

Tokenization: Bag of words (1/2)

Tokenization is the process of splitting a stream of characters intos sentences, symbols, or words. For text mining, we are particularly interested in words.

I) Identifying the words (tokens) of a document

The word delimiter identification is important. It will often be spaces or punctuation.

Some characters are less obvious : e.g. "-" might be a delimiter in English language, but not always in French.

II) Creating a dictionary

Potentially, the number of words is very important and there may be redundancies.

It will be necessary to treat the redundancies. For instance using stemming or lemmatization : Putting all words to their root form.

III) From text to vector

The absence or presence of a word is then assessed in each text, thus creating a binary vector.

You can also count the number of appearance of a word. We are then talking about weighting words. Tokenization: The lexical database issue

Even with tokenization or lemmatization, covering a whole language requires very large lexical databases with some semantic structures.

For English language, WORDNET lists, classifies and relates the semantic and lexical content of the language.

A Synset (synonym set) is a database with groups of interchangeable words.

Example: car, automobile, machine, motorcar, etc.

In the bag of word representation, it can significantly reduce dimensionality.

Ontologies are a representation based on concept trees and hierarchical relationships.

Lemmatization

Lemmatization: Definition

Lemmatization consists in analyzing a term in order to identify its canonical form (lemma). The idea is to ignore all modifications due to conjugations or declinations to keep a single form of the word.

Unlike stemming, lemmatization has to return an actual word.

Example: the boy's cars are different colors → the boy car be different color

Part of speech

Part of Speech: Definition Part of speech (POS) proposes to distinguish the words of a sentence according to their lexical categories (e.g. noun, verb, adjective, etc.).

Example:

They refuse to permit us to obtain the refuse permit.

The first refuse is a verb, synonym of denying. The second refuse is a noun, synonym of trash.

They refuse to permit us to obtain the refuse permit.

(they,PRP), (refuse,VBP), (to,TO), (permit,VB), (us, PRP), (to, TO), (obtain,VB), (the,DT), (refuse, NN), (permit,NN)

POS with lemmatization and stemming

Part of Speech must be used before lemmatization or stemming :

1 Use POS to determine the lexical category and if possible grammatical form of the words. 2 Use lemmatization or stemming for tokenization or lexical database search Lemmatization algorithms are more complex than stemming, but they often prove more effective for text mining.

In some languages, stemming and lemmatization give the same results: Chinese and Japanese for instance.

Remark

For translation applications, stemming is still more commonly used than lemmatization.

Stems are more often the same across languages than normalized words.

Lemmatization requires extensive databases in both languages

POS and stemming for basic translation

Use part of speech to determine the lexical category and if possible grammatical form of the words in the source language Apply stemming to the text in the source language Search for equivalent stems in the target language Reverse part of speech in the target language to reassign lexical roles and grammatical functions

Additional Text Cleaning Considerations

Handling large documents and large collections of text documents may cause memory issues.

Some formats such as HTML, XML or PDF have there own structurations that require specific splitting methods.

Languages other than English may cause issues:

Accents, apostrophes and cedillas Non latin based characters and ideograms

Unicode characters may need to be normalized in formats such as UTF8.

Handling of domain specific words, phrases, and acronyms may prove useful and could require specific dictionaries.

Handling or removing numbers, such as dates and amounts can be considered.

Typos and misspellings happen and should be considered ! The Inverse Document Frequency (IDF) for t i is :

idf i = ln |D| |{d|t i ∈ d}|
With |{d|t i ∈ d}| the number of documents where t i appears The Term Frequency Inverse Document Frequency (TF-IDF) :

tfidf ij = tf ij • idf i
The TF-IDF is used to know the importance of a term t i inside a document d j relatively to its importance in the whole corpus D.

Since some terms may be a lot more frequent than others in large corpuses, there are several possible normalizations of the TF to reduce scaling issues. binary 0, 1 raw frequency t i log normalization 1 + log(t i ) 0.5 max normalization 0.5 + 0.5 Alongside distance functions, they characterize the similarities or dissimilarities between objects.

• t i argmax d∈D t d i max normalization K + (1 -K ) • t i argmax d∈D t d
In the particular case of text mining, we need to measure similarities between sentences, documents, or even corpuses of documents.

We have seen that texts can be turned into numerical vectors.

Similarity measures are key for a lot of Machine Learning and Data Mining methods : visualization, clustering, classification, etc.

Alongside distance functions, they characterize the similarities or dissimilarities between objects.

In the particular case of text mining, we need to measure similarities between sentences, documents, or even corpuses of documents.

We have seen that texts can be turned into numerical vectors.

Now, which similarity measure should we use ?

A similarity measure between 2 vectors u and v must have the following properties:

Non-negativity :

s(u, v ) ≥ 0 ∀u, v Symmetry : s(u, v ) = s(v , u) ∀u, v Maximality : s(u, u) = s(v , v ) = 1 ∀u, v Normalization : s(u, v ) = 1 ⇔ u = v ∀u, v s(u, v ) < 1
From similarity to distance

The dissimilarity between 2 objects can be seen as the distance between them. Therefore, distance and similarity are directly linked.

d(u, v ) = 1 -s(u, v )
In addition to the non-negativity and symmetry properties that are the same than for similarities, distances also have the following properties:

Identity of indiscernibles : d(u, v ) = 0 ⇔ u = v ∀u, v Triangle inequality : d(u, w ) ≤ d(u, v ) + d(v , w ) ∀u, v , w
Similarity measures: Indian Cricket example (1/3)

Let u and v be 2 vectors with word counts for 2 documents.

Euclidian Distance:

|| u -v || 2 = n i=1 (u i -v i ) 2

Further considerations on similarity indexes

There are a lot of similarity measures and distance functions that can be used for text mining.

Like for any data analysis task, some will work better than other depending on the data features and the type of study.

For instance, Euclidian distance is perfectly fine when using TF weighting and documents of similar sizes.

Further considerations on similarity indexes

There are a lot of similarity measures and distance functions that can be used for text mining.

Like for any data analysis task, some will work better than other depending on the data features and the type of study.

For instance, Euclidian distance is perfectly fine when using TF weighting and documents of similar sizes.

Some extra indexes for binary analysis

Dice :

s(u, v ) = 2×|u∩v | |u|+|v | Overlap index : s(u, v ) = 2×|u∩v | min(|u|,|v |) Tanimoto index : s(u, v ) = |u∩v | |u|+|v |-|u∩v |
Similarity measures: Chi square (1/3)

In Lecture 3, we saw that the Chi square could be used for the correlation analysis of categorical data. Let's see how to use it for similarity between texts.

Corpus of 3 documents (Grossman, page 71) D1 : "shipment of gold damaged in a fire" D2 : "delivery of silver arrived in a silver truck" D3 : "shipment of gold arrived in a truck"

D1 D2 D3 arrived 0 1 1 damaged 1 0 0 delivery 0 1 0 fire 1 0 0 gold 1 0 1 shipment 1 0 1 silver 0 2 0 truck 0 1 1 J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022
Similarity measures: Chi square (2/3)

Terms D1 D2 D3 Sum arrived 0 1 1 2 damaged 1 0 0 1 delivery 0 1 0 1 fire 1 0 0 1 gold 1 0 1 2 shipment 1 0 1 2 silver 0 2 0 2 truck 0 1 1 2 Sum 4 5 4 13
Computing the χ 2 can give you an idea of the potential association between documents by testing the independence hypothesis.

χ 2 = K k=1 L l=1
(o kl -e kl ) 2 e kl = 13.65 0.25 < p < 0.5

We can also compute the Total Inertia (total amount of information):

φ 2 = χ 2 N = 13.65 13 = 1.05
Similarity measures: Chi square (3/3)

The matrix of standardized residuals identifies attractions and repulsions between terms and documents: From there, the contribution to the χ 2 can be computed to assess the impact of associations in the global information quantity. From there, the contribution to the χ 2 can be computed to assess the impact of associations in the global information quantity. We can see that most of the information comes from the attractions (D2,silver) and (D1,[damaged,fire])

r kl = o kl -
c kl = 100 × r 2 kl χ 2
c kl = 100 × r 2 kl χ 2

Principle of Correspondence Analysis

Let us consider R the matrix of standard residual r kl = o kl -e kl √ e kl , and M a standardized matrix so that M = R |D| , with |D| the number of documents. The Correspondence Analysis (CA) consists in computing the singular value decomposition (SVD) of M, so that : M = U∆V T U (K ×K ) contains the K left eigenvectors (for the lines) ∆ (K ×L) is a matrix whose diagonal elements are the singular values (eigenvalues can be acquired by squaring them) V (L×L) contains the L right eigenvectors (for the columns) Each singular value δ h is defined so that:

M v k = δ k u k M T u k = δ k v k
Then we get the eigenvalues:

λ k = δ 2 k K -1

Goal

From there, CA aims at finding projections of the terms (or documents) that maximizes the dispersion. It is similar to PCA and correlation circles.

Correspondence Analysis: Example

The projection is made possible thanks to the transition relationship (almost barycentric), meaning: The coordinates of a column term can be obtained based on all lines terms and vice versa.

Coordinates of term k on the 1st component:

F k1 = 1 √ λ 1 L l=1 o kl n k × G l1
Coordinates of document l on the 1st component:

G l1 = 1 √ λ 1 K k=1 o kl n l × F k1
Correspondence Analysis: Example

The projection is made possible thanks to the transition relationship (almost barycentric), meaning: The coordinates of a column term can be obtained based on all lines terms and vice versa.

Coordinates of term k on the 1st component:

F k1 = 1 √ λ 1 L l=1 o kl n k × G l1
Coordinates of document l on the 1st component:

G l1 = 1 √ λ 1 K k=1 o kl n l × F k1

Remark

Each term is located based on all the documents (and vice versa). Thus, a cross-reading between documents and terms may be misleading ! For instance it would be wrong to conclude that D3 is linked to (truck) ... (see the χ 2 contribution table ).

We have seen that the document-term matrix can be considered as a contingency table.

The total quantity of information can be measured using the total inertia :

φ 2 = χ 2 N .
CA makes it possible to make a projection of the terms and their relationships (based on the documents).

CA makes it possible to make a projection of the documents and their relationships (based on the terms).

It also helps to visualize term-documents associations, while keeping in mind χ 2 results.

CA relies on Singular Value Decomposition and the matrix of standardized residuals from the χ 2 .

Introduction

Text The issue with trivial encoding "Have a good day" and "Have a great day" → V={Have, good, great, day} One-hot encoded vector:

Have=[1,0,0,0,0] ; a=[0,1,0,0,0] ; good=[0,0,1,0,0] ; great=[0,0,0,1,0] ; day=[0,0,0,0,1]

If we try to visualize these encodings, we can think of a 5 dimensional space, where each word occupies one of the dimensions and has nothing to do with the rest (no projection along the other dimensions).

It means that "great" and "good" are as different as "day" and "have", which is not true !

The issue with trivial encoding "Have a good day" and "Have a great day" → V={Have, good, great, day} One-hot encoded vector:

Have=[1,0,0,0,0] ; a=[0,1,0,0,0] ; good=[0,0,1,0,0] ; great=[0,0,0,1,0] ; day=[0,0,0,0,1]

If we try to visualize these encodings, we can think of a 5 dimensional space, where each word occupies one of the dimensions and has nothing to do with the rest (no projection along the other dimensions).

It means that "great" and "good" are as different as "day" and "have", which is not true ! This representation does not show similarities between words ! Direct word counts or trivial embedding are therefore not a good encoding method as it loses a lot of information, in particular semantic information.

Word2vec

Word2vec: how to ?

Word2Vec: The Skip-Gram model

We have seen that the notion of similarity may be important for word embedding.

The question is : How to train a neural networks and teach it word similarities ?

Feeding a large database of similarities is a bad idea !

The skip-Gram model The skip-gram model consists in feeding the neural networks with pairs of words that may be similar based on their close positions in the source text.

The skip-Gram model uses window sizes :

What we learned

We have seen some of the basics of text mining:

How to turn text data into numerical data so that they can be processed by any Machine Learning algorithms

We have studied various similarity and distances measures that can be used with text mining.

Introduction

  Text mining tasks and processesAnalyzing similarities between and within texts Introduction Text mining tasks and processesAnalyzing similarities between and within textsExamples of text analysis tasks The most common uses of text mining include but are not limited to: Machine translation Part-of-speech tagging Information extraction Sentiment analysis from text Automatic quizz answering Text categorization Stylometry and plagiarism analysis Some of these applications are very important for world leaders.

  Similarity measures are key for a lot of Machine Learning and Data Mining methods : visualization, clustering, classification, etc.

  Let us consider D = {d1, • • • , d j , • • • } a set of document. Then for any term t i , we have: tf ij the number of occurence of t i in a document d j . It is the Term Frequency (TF).

IDF & TF-IDF

Tools to count word occurences: IDF & TF-IDF

J. SublimeData Analysis -Lecture 10 ISEP 2021/2022

Processing text data

Identify individual keywords and phrases and map them to different emotions/sentiment scales

Adjust the sentiment value of a concept based on modifications surrounding it J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022

Word2vec: how to ? Training Word2Vec (2/8) J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022

Word2vec: how to ? Training Word2Vec (4/8) J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022

Text mining tasks

We are going to take a look at some key tasks in text mining : Sentiment Analysis Document Summarization Entity and Relationship Extraction Tokenization and vectorization of texts J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022

We have seen two different methods that can link close words together in text corpuses: Correspondance Analysis and Word Embedding with Word2Vec.

Similarity measures: Indian Cricket example (1/3) Let u and v be 2 vectors with word counts for 2 documents.

Euclidian Distance:

Cosine Similarity:

Similarity measures: Indian Cricket example (3/3)

3D projection in space Jaccard index and Jaccard distance

The Jaccard index is very popular and assesses co-occurences between documents with a normalization mecanism.

Jaccard index and Jaccard distance

The Jaccard index is very popular and assesses co-occurences between documents with a normalization mecanism.

Jaccard Distance

Deducing the distance from the Jaccard Index is very easy :

Word2Vec: Conclusion

We have seen that Word2Vec is a neural network tool that can be used for smart word embedding that detects similarities and links between words.

Word2Vec generated vectors are better inputs for Machine Learning Algorithms than regular "one-hot encoded" texts.

On the importance of Parameters for Word2Vec

The Window size for the N-Gram model matters:

Too small and it may miss some key links Too big and the complexity explode and artificial links may be created

The size of the hidden layer is important too: It determines the encoding size

Too small and the embedding compression will fail Too big and it may not converge J. Sublime Data Analysis -Lecture 10 ISEP 2021/2022