OMML - Appunti corso

What is data mining?

Data mining is the core of Knowledge Discovery in Databases (KDD): this is the full research knowledge process from data selection Prepiscusing1 1 DataDataData processedINPUT Target f TrasformiDataoutput PatternsKnowledge Transformede 1 DataInterpretation Mining.

So KDD includes formulation of the problems, data collection, data cleaning and preprocessing, data mining and analysis of the results produced by the model, so it transforms raw data into understandable information.

However, the data mining step constitutes such an important phase in the overall KDD process to be often identified with the full KDD process.

In this course, we will focus on Data Mining in Machine Learning. Its main task is to define a learning model to be used in prediction, description, classification, regression and clustering.

First of all, we have to understand that not everything can be learned or is foreseeable: a good prediction, in some cases, can't be produced by any model or tools. But, on the other hand, when a prediction may be produced, a learning model should be rich enough to capture important aspects of the problem... We have to be able to collect enough data.

Data and learning

Data are a collection of objects and their attributes (also called features) and are composed of several instances. They are useful for different goals:

• Predict some attributes for the unknown (Supervised learning)
• Find some features and predict for the unknown (Unsupervised learning)

A supervised learning algorithm analyzes the training data and produces an inferred function (a model), which can be used for mailing new examples. forused checkingthe accuracy

The training set can be incrementally or batch learning: the first one (called also online learning) is obtained incrementally during the training process; the second one is available in advance before entering the training process (offline process).

The learning system can be mapped as:

The formal neuron and training process

The formal neuron (perceptron) is a simple learning machine with implements the class of functiongi sogniexfa dig.

The output is 1 if the sum is greater than the threshold ( ), or -1 otherwise. The algorithm finds the value of weights and the athreshold (so the hyperplane).

The training process is:

It consists in finding a particular value of the parameters which selects a special function in the chosen class. Its aim is fasi property) to model the process in a way that it is able to give the right answer in instances never seen before (generalization rather than interpolating on the training set. loss function

We need a function that gives us a “distance” between the output value and the real value: it is called and they are several. 44.4Ily ITyet i iOUTPUTREAL Il1yfaIOUTPUTest Ilyl

We want to minimize the expected error: ylpcxlpcxiyidxs.lyLI faRINmin

But we can't, because we don't know the probability density of input. So we can use the empirical risk: it is like risk expected error but evaluated on the sample data that we have: È yixiL ffamin Rcmp

Overfitting and empirical risk

How can we understand how much data we have to consider for fitting the model? If we use so much of them (overfitting) we will have an error on training data around zero, but the error will be high for validation set; however, if we use few of them the error on training set will be huge. We can use some tools for solving this problem: ERM, early stopping rule... The main rule is try and error!

Does exist a relation between expected error and empirical risk?

We just saw last time the Empirical Risk minimization: f

Empirical risk depends only on data and on the functon . We introduced it because we cannot use the expected risk a: in generalRCfa

Does a relationship exist between empirical risk and expected one? Yes, and it is possible to prove that:

Where “l” is the length of data set and “h” is the complexity of the class function. In particular C_VC is called VC confidence term and increasing “h” the first term will decrease and instead the second one will increase.

So we want to minimize the upper bound of the expected risk:

The learning machinehould be chosen by minimizing both terms. By the way the second one depends only on the number of samples in the training set, “l”, and on “h”: fixed che class of function, h*, and minimizating the empirical risk, we can evaluate the upper bound as

Repeating this process for all n class of function h^j, finding for each one:

We can choose the class of functions which minimizes the upper bound:

This principle is called Structural Risk Minimization (SRM). To apply this, we need to be able to calculate the VC confidance (the measure of the powerful of the class of functions in classifying data).

VC dimension

The VC dimension h is equal to the maximum number of vectors x_i that can be shattered, namely tha ca be separated using this set of functions { } into two different classes when labeled as In all the Possible ways. An example is:

ifa 2flinearefa xfa fa.infa Ix

So stating that the VC dimension of a class is “h” means that we can find at least a set (it is not necessary that we be able for any set) of “h” points that can be shattered.

Theorem: È The VC dimension of linear functions (hyperlanes) in is n+1, it means also that all the coulpe of the points EIRXpare linearly indipendent and all points are. Affinely indipendend.

Proof: Xi'ER

For each points with we associete the value for classifying them. Correctly classified means: i yiet.i.ite m

So we can rewrite the theorem as:

Assuming that the points are linearly indipendent, we have that the linear systemXin Yi i vniInownviHas full rank, so that admits at least a solution 112 Xi'citù i eil inV yyi.cl i m1i

So we get, assouming that O 4lb solii bci4 b ob isisi yy

So to satisty it, a solution of b can be: beco.isobel i

Vice versa, by contradiction assume that all the points i=2...m are linearly dependent. So we have that a linear combination from 2 to m points exists: mao

Assign that:

Fixing and such that: cieli bEIR is bE

We get a contraddiction, inft assuming that :O I15m l'itb co5 Èdi diticadci X og'b so Hyperplane with marginh x:

Hyperplane with margin

The VC dimension may depend on the dimension of the inputh=n+1.we saw that for the class of linear functions we have thatn?

But what happen if we reduce the number of dimensionReducing the number of features of the training data may indirectlyhdecreases and in turn limits the VC confidence term. On the other hand it may lead to an increase of the empirical risk. Entin,

So, understanding that the VC dimension of class of function of hyperplanes is how can we choose "the better" one? Let's introduce the hyperplane with margin. Consider the hyperplane: wtxtb.esd( )

And call with the distance of a point from the hyperplane: ID.

Assume that data stay in a sphere with diameter p: D,

The VC dimension depends on the value of tollerence if it is small with respect to the diameter it is still possible to shatter 3 points in 2-dimension; if it grows, the number of points that can be shattered decreases. So we can write that: p, h F.

Increasing the value of we are decreasing and so we are finding a smaller class of function.

So the SRM that use the hyperplane with tolerance gap is:

The SRM paradigm is used in two main approches:

• Support Vector Machines: it fixes the empirical risk to a given value and minimize the VC confidence;
• Deep Neural Network: it fixes the architecture (like the complexity and VC confidence) and minimize the empirical risk.

In both cases, we need to set up some hyperparametes that can control the trade off between the two terms in the true objecrive function. We will try different values and see which return the best predicted outcome.

Learning process

The data that we use to start the learning process could be splitted in 2 different sets:

• Training set, the data used for defining the optimization problem and finding the parameters;
• Validation set, the data used to check the predictive performance and to adjust the hyperparameters.

We can have a huge number of data to use for learning process: some of the available data can be used as training set and the second set of independent data (validation set) to check the predictive performance. How to choose how many goes in the training or validation set?

k-fold cross validation: We can use the all the data is divided into k groups; k-1 groups are used as training set and the remaining group as validation; this procedure is then repeated for all k possible combination. The performances to use in the model are averaged from the scores of the k runs.

To optimizate the enters we can use:

• For Support Vector Machines, the Constrained optimization (the optimization problem is linear constrained with a convex quadratic function);
• For Deep Neural Network, the Unconstrained optimization (the optimizaion problem is uncostrained highly nonconvex).

Perceptron

Perceptronnii i

We have a training set {(x , y ): x R ,y {-1,1} i=1,...l} and we have to find an hyperplane that separate the sets in 2: e wtxxb.atlire112H iii giletIii yi eBgilet1 yiA

With the function: if wtx.bafsgnlwtx.totw.blxt otherwise

So the perceptron graphically is:

The goal of learning is to determinate w and b using data that we have avaible. To find it we can use the on-line learning alghoritm:

This alghoritm is on-line because it uses a small set for training: even if it is arraving new data, the algorithm uses the first set for training and doesn't wait all the data for start iterations. The perceptron algorithm no updates itself if imput is already Pclassified correctly and the classified is linear combination of the inner products (it values 0 if they are ortogonal, namely they are similar): Perceptron

We just saw the perceptron algorithm, and it is an On-line one: it doesn't consider the entire data set at the same time, it only ever looks at one exaple; training exaples appear sequentially. With the exaples of logic AND and OR, we saw that it is convergent for linearly separable sets. Let's see the theorem that demonstates it.

What we want to do with this algorithm is find: f f iniziowtxtb vitebe RWEIR oy

And to do that we update: csnvllx.y.tlvent ypz.iow E

The existence condition of the hyperplane with w and b is that the sets A and B should not overlap: il PER1131 iEIR yyA A 0Bncs.nucon edi didi 202Znuca

The theoreis: È3 5 stepsPiù finiteafterso perceptiony convergezioyp o bluiR 040 4K minFi ER11i 1011

The proof is by contraddiction, namely zioJp PHk sowyE cosaviii 11W11W viii ilil Il unIl ilEwe P tz.PEIt twktypw liPz 1ktw w ww xpy puntilli EE 11wKai PzPz PllIl w11W Il w2 yy 2 zyPwktzpypz.siIl11W liI Ix'llyou i11Wli It11W EzEoHpliniRiti11W RE Il E k i

So we have thatt R11211W kE i R tiK'plHK Il RK11 KEE iEwIlIl 2 Kai pw p

So it exists a k finite for the stop of the algorithm. But what can we do if these isn't linearly separeble? Like an example, if the training set is the logic XOR. A way to generalize a no linearly separable set is another algorithm:

• Voting Perceotron, voting the hyperplane for how much it survived;
• Average Perceptron, it is a modification of the voting one and it votes the vectors w and b (instead the hyperplane).

The outcomes of algorithms are:

Feed Forward Neural Network

We want to define a function defined by parameters w EIRfix cnp wsuch that it is close to the true y . The algorith has to find to minimize empirical risk.

The large-scale supervised machine learning takes like input Big Data (P couple. x , y ), dimension of each sample (features of x ) and the parametres (d): it chooces a function and minimize approximatibely the empirical riskwifiMÌ Rcmp

Output is the extimate empirical risk incinta regularization term:

To find the "correct" function we can penalize its complexity, using a È sÈ 21inyillfcxi.ws wWpmia diluitoltypically the losses function for regression is quadratic square loss, hinge loss or logistic loss: È lui xD AllaÈ 11y'llHIP yRamp p 411WIIWta10È10,1 I yymax maxRamp perlogli texpl ypy.si units

A FFN (Feed Forward Neural Network) is composed into (= neurons) that are organized into layers with one-way connections (top-down): e leiL N l j l.

A FFN has 3 parameters: number of layer, number of units in layer and the activation function of unit in layer9J

There are different models depending on: eL N

• Number of layers and/or number of neurons per layer (it affects the dimension of the optimaztion problem)g w):
• Hidden Unit type (activation function and its hyper-parametersMultiplayer Perceptron Networks;
• Radial Basis Function Networks.
• Multiplayer Perceptron NetworksgUnits are generalization of the formal neuron and the activation function acts a trigger (on/off) and may depend on hyper-parameters:
• L=1 for shallow networks and L>1 for deep networkw
• Are the weights on the arcs connecting units and the bias in the unitsj l,

Let's see the generalization of an unit. Its internal structure, of neuron of layer is: leiNe ilzie 2l-1as input from layer there is ori isum to the input the bias bytethe output of sum is a.ieit trasforms the sum with g.ie ej lthe output of the unit of layer is zg

As activation function we can use: etceItexpectegiti 9 Cte1et et