noc19-mg15 - Lecture 59: Metaheuristics techniques

[Music] [Music] welcome back my dear friends and dear students a very good morning good afternoon good evening to all of you wherever you are and this is the da d m2 which is data analysis and decision making to course under the NPT MOOC series the total duration for this course as I keep saying it before the starting of the class it is for twelve weeks and we are in the twelfth week if we see the slide later on it is we are in the last but one lecture which is the 59th lecture and with 60 we will wrap up this course and the this total duration as I mentioned was 12 weeks which is basically 60 lectures each lecture being for half an hour and each week we do five lectures of half and on each and you have already done 11 assignments with with this twelfth one you will complete the twelfth assignment and then take the final examination and my good name is reka non-dancing Gupta from Miami Department at IIT Kanpur so if you remember in the I did mention that again I will repeat in the 57th lecture the time duration was much less because it was twenty-one minutes because we wrapped up the concept of artificial immune system with an example how prediction can be done for from the financial point of view of bankruptcy and they discuss about clonal selections negative positive in combination of them then we have been into artificial neural network starting the fiftieth lecture and there I discussed very briefly though and if I have not been able to explain from the actual biologist or a doctor's point of view because that was not my intention I wanted to only give you a snapshot so there are basically even a neural system they are dendrites they pass on the information to the neurons neurons then passes on the same signals to the synapse to the connection they are not connected so they give this electrical pulses on in signals and and the been brain processes it so that can basically be analyzed using the concept of the nodes nodes has a sigma mental function they consider the weights weights w12 WN and depending on the number of nodes you have and there are different layers the first input layer then hidden layer 1 2 3 4 till the output layer and the function and for the each nodes they would marked as 1 1 2 1 in for the first layer similarly 2 1 2 2 n for the second layer and so on and so forth where n is the number of nodes so I am NOT considering than n number of nodes for each the input layer the hidden layers need not be equal this this the function based on which the inputs are analyzed the sigmoidal function and the parameters the X values can change and also remember there's a supervised learning in which the the feedback loop pumps in order to basically give a gift the whole neural network system or learning concept so that it learns itself and and basically fine tune sees is prediction values or or the output value I would not use the word prediction because if it is an objective function it's not prediction so it gives the output in such a way that we try to find out how good or bad is if it is not good then it learns itself and if it is good based on the parameters Jessie it with the threshold we have set for ourselves it basically passes on the the output into the next layer and it goes on so on and so forth till we get the final output then I had also discussed the back propagation the node functioning and then I also mentioned very briefly and I did mention it twice during the discussion during the initial discussion of a NN and also at the last few minutes of the last class about change point detection and why it is important important from the point of view of how we are trying to utilize it so the matrix which we have so the objective function was half a transpose a X transpose a into X plus B transpose in X plus C B C's and A's values of minus plus are immaterial here the objective function is more important here a we say there is a set of non zero vectors and is conjugant if the following condition is satisfied so these are the mathematical terms which we have so that a s transpose depending on n n is the size of the parameters into a into S J where N and J are the values depending on the number of parameters which you have and n ng are not the same so generally the parameters for each node are of each layer may change what will basically have corresponding nomenclature to discuss that for a given set of akon are conjugant vectors vectors s naught to s w 1 w minus 1 the corresponding conjugate direction would give me for the unconstrained minimization and the maximization in which direction we should go as i mentioned that partial derivative is generally utilized to find out the rate of change of the function and obviously the second derivative the Hessian matrix would basically give us some information that whether is the maximum the minimum obviously we are considering that the second derivative is greater than 0 or less than 0 is not equal to 0 because if it is equal to 0 it will be the point of inflection now the the quadratic error function which will basically expand depending on the functional form so it will give me in which direction we are trying to minimize or maximize I am NOT going to go into the mathematical detail this is not important because if I generally do we try to basically go into the depth then obviously a whole set of lectures about 20 to 25-foot believer attorney and and similarly for AIS and so on and so forth but this da d m2 is basically a set of lectures which only would basically give you a brief idea in a very simple way about the non parametric method of optimizations which I have considered the AHP I'll come I have you know that where HP tops is Elektra then the concept of this utility function which have been utilized for casting methods so on and so forth so we have also considered a is and the N and method is being discussed now so so in the the gradient descent method what we are doing his base basically I will repeat it we are trying to take the direction in which the maximum descent is the optimization problem from the point of view optimum problem or will go in the direction where the prediction is the best so there would be some criteria so the in this case the the actual value is extra which you have already discussed and if you consider from this point so here in a two dimension one either the tangent him in this direction or in this direction I'm trying to draw it as simply as possible simple so if it is in is a minimizing problem obviously you move in that direction where the negative change is happening the maximum and hence the distance would be for the fastest in the positive it will be just the other way round in the maximization problem and we will find the errors such that the errors which is epsilon would be found out depending on the difference so what we are trying to do is actually we find out X in the ith stage depending on way how you're moving based on the fact X minus one and we try to find out whether this value is is less than equal to epsilon naught greater than equal to Epsilon but the moment it is epsilon value has been fixed from our side so this is the epsilon value based on that we stopped the process now the residuals would be given so then that that its residual concept is something to do with the multiple linear regression concept the errors which are there so we try to basically minimize the errors in the multiple linear regression concept using the the rate of change of that values which is basically we try to differentiate with respect to all the alpha alpha beta 1 beta 2 beta K then put it to 0 and find out the values now here the the linear combinations would be given such that based on the linear combination we can the scaling factor can be found out I am NOT again I am repeating I'm not going to the each and every fundamental details of the equation I am just giving you the idea based on which I how I can build up the modelsim as I did for a yes now here the property it was a very brief discussion very very brief discussion of a NN now I'm going to utilize this concept of of a NN in change point direction so it can be solutions can be encoded with discrete variables an optimization problem you can basically have the complete an approximate solution in this case of the approximate solution we are going to use them here is stick methods the metric techniques is basically as I already said is a kind of approximate algorithm it basically tries to combine basic heuristic methods in higher level of framework aimed at efficiently and effectively finding out the solutions if you remember I did mention about plan and colony optimization simulated annealing artificial neural network genetic algorithm and all these things were there so these are particle swarm optimization so these are class of problems which we have generic algorithm taboo so similar trend naming and all these things now comes the concept of change point detection now change point detection is basically the concept which will try to utilize from the point of view of statistics so consider this you have a data set and the data set underlying distribution if it is disillusion means I am talking about the PDF or the PMF or in general the distribution function which is capital F so if I have a normal distribution the distribution function is known so the parameters are actually a distribution function or in statistics would have basically three parameters alpha beta gamma on location scale and shape parameters now the parameters which are there in the normal distribution are mu and Sigma similarly for exponential distribution it will be alpha and a or it can be theta a depending on from where it starts now fundamentally a data set which we have basically may have its underlying distribution is evolving with time so they can be two types of of evolvement one is the distribution they remain same that is it is normal it remains normal if it is exponential it remains exponential if is gamma it remains gamma if it is beta it remains beta but the parameters themselves change that means if it is a normal distribution we are getting the normal distribution but say for example alpha this mu is changing or Sigma is changing or both of them not changing so our main aim in change point detection is to basically predict the values of alpha beta or gamma which in the normal distribution cases the MU and Sigma and predict also when they are changing two things predict the values predict the time when they are changing number two problem which is one step higher is basically the distribution function by itself is changing that it was normal changing to exponential I am giving you very very simple examples so it was F 1 Xperia L u now it is changing to F 2 X PDF function so per say the parameter is also changing the functional form is also changing so we need to predict what is the PDF value of what is changing so f 1 changing to F 2 or F 2 changing to F 3 and when it is changing so change point detection is basically would be utilized in a very simple sense the points at which the change points are happening and to predict the change points we will try to utilize the artificial new neural network system along with one of the heuristic methods so this is the debating general background so consider the I'll come to this change point detect in the problems using the data point I will come to that now why change points so they are affected so consider if you are considering the finance concept or a marketing concept or the flow concept of fluid whatever it is a heat movement through two conductors so if suddenly if the heat changes is not happening because there is some congestion flow fluid flow is not happening they wear this and there's some congestion the pressure is increasing decreasing the change the distribution by itself or the rate of change is changing so you want to predict it so in this case of economics finance this change direction is heavily used so why because the effect on the marking factors could be their or interest rate we want to find out the rate of change in the interest rate the gross domestic product is changing inflation rate is changing unemployment rate is changing we want to predict when they are happening these factors make the exchange rate so this affects which are happening for the exchange rate because our main aim would be to a final exchange it for this study because exchange rates are highly flow volatile and fluctuating through thus making making extended inherently noisy non stationary and chaotic and we want to basically find out when and where the changes are happening exchange rates are not homogeneous that there are may be structural or breaks so change one direction another word for change one direction is structural buildings so in many of the books if you study obviously in the area of statistics the concept of structural breaks or change point in direction are chosen interchangeably now there are different tests for change point I just mention them without going to the mathematical details because not as a statistical course so there you have the child test which is the linear models then you have the regression methods are basically when they are utilized then you can use the linear models of this doubt test because we remember in regression model the model is linear linear in the sense of the parameters so it can be alpha into X square depending on X square has a distribution which is a normal distribution if you remember amongst the seven different assumption in multiple linear regression one of the assumptions is basically the dependent and the independent variables all should be linear and they should be independent also because if they are not independent then that concept of cook this covariance and all these things would be coming these were among those seven set of important assumptions you have the parametric methods also the likelihood ratio test which are there for the non predicting methods we have the petted test which is based on the mann-whitney type statistics depending on on non parametric values happening at the rate such that the changes of this parameter values are nonlinear in nature so they will check for the changes in the underlying distribution function of the subgroup so we will what we will try to do is that technically it may be possible that the distribution f of X or F 1 of X is changing and as it is if evolving it may so happen that the changes are happening randomly obviously they would be happening at the random points which you do not know any we want to predict at the time so they would give it they would basically given as two ideas which has discussed the change of the parameters are change of the functional form itself now if the underlying distribution function you divided into subgroups so today I find one say for example the in this foreign exchange is same and it has and it doesn't fluctuate say for example I want to predict it one year down the line but in between that one year it may have change and again come back to its origin ourselves so subgroups are important to find out predict that if I basically have the invest consider from the point of view investment if you invest and you want to go out come go enter the market or come out of the market in between that one year so what are the sub groups in the sub groups what are the change changes and what points they are changing what is the rate of change of the interest rate such that I do not enter the market where I have to pay a higher fee I do not come out on the market where I get the lower fee that means I want to basically minimize my loss in the absence of knowledge of Time series parameters in this case for the mainly for the newton this exchange rate because exchange rate are dependent on many things it can depend on the GDP it can depend on the gold price petroleum price inflation interest rate of other country's population whatever it we do not have the parametric form hence as parametric forms are not possible we will try to utilize neural net for concept along with that will also try to utilize some of the heuristic methods in order to do the optimization optimization means the prediction of the change point as good as possible now here is basically what I told you very simplistically verbally here is basic in either except of the change point in the petite test consider a sequence of random variables are X 1 X 2 X 3 till XT mark the word capital T in the suffix now what we have is basically the time so I measure X I find out x with the suffix 1 at time period 1 X 2 at the time period 2 so on and so forth so then the sequence is said to have a change point tau if X T that means T starting from 1 to peak small tau will have a common distribution of F on X this n1 doesn't mean have any significance with one two three four in the time series basically functional form and starting from tau later on that is tau plus one till capability they would be another distribution F two such that F 1 and F 2 are different that means I am considering per say the distributions also is also changing I am NOT considering per se the parameters values are changing so it is a simplistic form I am considering that normally changing to exponential or explanation is changing to gamma so on and so forth now if I have so we will try to basically have the peddit test as an hypothesis testing point where H naught would be the case that if tau is equal to T there is no change for the time period which I am considering if there is no change that H naught would be ratified or we agree with H naught depending on the test rule and if H a is ratified that means H naught is rejected you will find note that at Point tau where this point is changing we will mark that as the change point obviously it may change you may say that they can be many taos in between capital T so it can be tau 1 tau 2 tau 3 till tau N or tau K yes it is possible and we can find out using the beta test accordingly so we will basically check must say very simply mention the algorithm based on which you do you can calculate the rank Spearman rank is basically the one of the correlation coefficient we use the urban ranks would be found out associated with each random variables and we will find out the sum of the Spearman rank coefficient then we'll basically find out the running some of them see my ranks for the corresponding man weekly rank would be found out depending on the formula of U T for J is equal to 1 to t minus 1 for all the points where we are finding on the Spearman rank with values you will calculate the the values of mann-whitney ranks by finding on the maximum of them and find this I'm just mentioning the bullet points of the steps you will find the value of J where the maximum on the statistics occurs and that gives us the estimated change point of the sequence so the sequence would be divided into two subgroups one from T is equal to small T so you'll want to M and another would be from M plus 1 to team T so it will be divided two groups the first group and the second rope where the changes are happening so if I have so this is the change point so let me mark it with a different color so this is the change point we find out so the time period so this is virtually capital T this is from 1 to tau this is tau plus 1 I have trying to draw it as simple as possible is U and this is from 1 to tau so they can be more so this is one subgroup this is one subgroup and similarly this is one subgroup based on that we can do the calculations in step 5 according to the standard rank theory we will try to find will under the null hypothesis we will consider there is no change and as T becomes large we can approximate using the normal transformation so here is the normal transformation so this is the expected value and the variance so it's basically exactly the same way so you have basically in the Z test what you do X minus mu my standard deviation of X so anything I should mean write it like this so it is easier so this is the expected value of we are using this concept that is the central limit there are in the exact central limit theorem but the concept of central now considering the two tailed test the total means on the left hand side and the right hand side and the Alpha values which are there so on for various means one tail one tail test will be on to the left of the right depending on that you can find it out so if you remember in in in statistics if you have obviously done on is somebody who has done dat m1 we considered the concept of hypothesis testing greater than type less than time and not equal to and based on that we have three different rules which were busy coming from the concept of interval estimation now the parametric forecasting methods which we generally have which will try to basically incorporate mean the N n these are not to go I'm just mentioning them so you will basically the art in the arma guards math method which in the forecasting method we did consider very simply the the concept of halt linear and hot winter method halt method then moving average explanation moving average adaptive moving average so based on that we will try to predict where the prediction would happen depending on some error part and it's and it's regressed values to what level you will go so if you are predicting basically for YT you can go for regress to YT minus 1 YT minus 2 and so on and so forth again these explanations I'm omitting they are not required because the main focus for the a n n how you can utilize that for the odds guard method obviously the log likelihood function for the prediction models can for that this is basically I am considering the log likelihood function likelihood function it will be converted to log line to function the best estimates for Sigma Sigma hat and Y which is y hat would be found out using these models where the hats are the estimates of the underlying parameter values which we are trying to utilize now we basically utilize the model for the N + 1 using these what are these I will come to that later we will consider the neural network which will be trained using the conjugate gradient method simply as it is developed in a n n literature will use the change point reduction for the neural network combining two different methods one is the genetic algorithm one and one is the similar in handling so it will be mentioned as n n GA and NSA depending on n n being neural network the first towards and G and si being basically for genetic algorithm and simulator handling now you will basically have the neural network with the conjugate gradient method utilizing both GA and si that means in the first stage we are only utilizing the conjugate gradient method in the second method we are only using the a n n we with the G NSA and the third stage will combine the existing conduit gradient method being we refine more by the use of genetic algorithm and and similar training and check how the results are better or worse now with the change that was basically without the change point detection now with the change point detection concept again we utilize the change point detection along with the gradient 1 so the I'll come I'll repeat this this overall picture again so in the change point detection with those Petite tests and all these methods which we discussed the rank coefficient and all these things will consider using a conjugant method we'll use the change point detection methodology using the G NSA and then basically combine the change point detection methodology with the with the conjugant method along with G a one time and si one time so overall picture is like this no change point algorithm we utilized will use the gradient descent conjugate gradient one you can gradient method then we will use the concept of GN si separately and then combine them in the in the change pointed direction the algorithm being utilized using the statistical point of view will use the conjugate gradient method once separately will G a and separated Si and then combine them accordingly so with this I'll end the 59th lecture and in the 60th lecture I'll try to give some results for this mythology how we utilize them have a nice day and thank you very much [Music] [Music] [Music]