Data Science - Part XVI - Fourier Analysis

hello and thank you for joining my name is Derrick cane and today we're going to dive into the topic Fourier analysis for machine learning this lecture is just one lecture in a broader series of lectures Titan topics of data science predictive analytics statistics and machine learning the overview of topics that we're going to get into today we're first going to start with an introduction to fourier analysis you know what is the concept how does it work in more importantly how can we leverage it from machine learning concepts we will then move into the topic of the Fourier transform we'll discuss how we can use Fourier analysis in econometrics and time series modeling concepts then we will conclude with a practical application example where we will create a time series prediction using Fourier analysis on manufacturing order volume and we're also going to incorporate the use of artificial neural networks so the example here is actually a really interesting way to use machine learning and time series concepts and it's really a very cool one to look into before we dive into the topics in detail we first need to have an introduction to what the Fourier analysis actually is in Fourier analysis is a mathematical method used to break down and transform a periodic function into a set of simpler functions these simpler functions can then be summed and transformed back into the original form a period function is a mathematical relationship between a quantity and variable or variables whose relative values consistently repeat over some regular period of time so we're looking at frequencies as a function of time let's now talk a little bit about the history of Fourier analysis Fourier analysis it was invented in the early 19th century by French physicist and mathematician Joseph Fourier from Joseph Fourier transformed the partial differentiation equation representing the propagation of heat into a series of similar trigonometric wave functions so sines and cosines if you remember back to trigonometry and you hope we work with angles science cosines and tangents for a very significant impact in this particular area these wave functions could be superimposed to reconstitute the original function thereby providing a simpler general solution to the problem the Fourier transform in for years law were named after his contributions and Joseph Fourier is also generally credited with the discovery of the greenhouse effect so this concept of a Fourier analysis and later when we get into the Fourier transform and how the mechanics work really is one of the greatest mathematical ideas we've had in the early 19th century it does quite a lot and it really is the foundation of a lot of mathematical concepts in terms of number theory and as significant applications speaking of which here are some of the applications of a Fourier analysis we use it for acoustics for signal processing so if you're looking at mp3s or JPEGs or any type of general audio processing you know so if you're mixing your trouble your base and your mid-range and you're using your stereo receivers chances are there is some element of a Fourier analysis of being incorporated we can use it in terms of modern econometrics work so option pricing now in mathematics the technique is very deeply rooted in number theory and Fourier analysis also has applications in statistics and probability theory as well we get into the concepts of harmonic analysis so for musicians and looking at sound waves there's a lot of applications in terms of how a Fourier analysis can can work in that particular space as well and of course it can be used in image processing and in electrical engineering amongst its many applications now one important note that I want to put here is our exploration of the Fourier analysis in the Fourier transform will be more conceptual in nature in order to prepare for the practical application of the technique so I'm not really going to get into too much of the mathematical concepts I mean we'll see some elements of it but I think it's important that we have an expectation what we're actually going to get out of this particular presentation so if you're looking for more mathematical proofs you know I would I would suggest get the foundations of you know what the technique is actually applying and then you know run some searches on the internet and you will find some really fantastic resources to draw from so why is the Fourier transform so great at the heart of the seemingly intimidating mathematical formula is a beautiful concept so when we look at this mathematical formula it's a fairly intimidating the formula and we'll break it down into its sub components coming up but let's just think conceptually what the Fourier transform actually is doing what it was doing is this function is essentially transforming a function of time into a function of frequency so let that sink in a little bit so we're going to take a function of time something which is occurring over time and we're going to convert it into a frequency this transformation has profound impact on the nature of reality itself due to the relationship it draws between these two variables so when we look at you know how is it applied in mathematics and in some of the Natural Sciences this relationship between converting from a function of time into a function of frequency has some profound impact and influences I like to think of this equation as the mathematical bridge between time and frequency and much like Maxwell's equations governing electricity and magnetism one of the weirdest results in quantum physics is the Heisenberg uncertainty principle this principle states that for a given particle the more precisely its position is defined the more uncertain its momentum is and vice-versa in quantum mechanics frequency is interchangeable with energy and therefore the energy of a particle is uncertain over arbitrarily small time frame this allows particles in the quantum regime to borrow enough energy to tunnel through a potential barrier so long as they pay a picnic in a small enough time frame to be keeping it with Heisenberg the Heisenberg uncertainty principle is essentially a theorem about Fourier transformations so if you're interested in the Heisenberg uncertainty principle and understanding the roots of this equation after you have an understanding of Fourier transformations you can kind of look at it in a different lens but the Heisenberg uncertainty principle is a remarkable concept in physics and at the heart of it it's drawing from Fourier transformations well what is this Fourier transformation we're talking about a Fourier analysis begins with a Fourier transform the Fourier transform breaks down or decomposes a single more complicated periodic wave function into a set of simpler elements called a Fourier series that takes the form of sine and cosine waves or complex exponential equations these can then be softies in simpler mathematics and superimposed or we combined to yield a solution to the original function via a linear combination the decomposed elements of fourier series are sometimes referred to as harmonics so when we use the term harmonics in the context of a Fourier transformation this is what we're talking about these decomposed elements and it's not to be confused with the musical terminology of harmonics narrowly defined Fourier analysis refers to the process of decomposing the original function into a series of simpler components more generally it can also include Fourier synthesis which is the process by which the original function is reconstituted by performing an inverse transform Fourier synthesis essentially runs the Fourier analysis in Reverse so we're taking the smaller wave components were combining them in order to recreate the original wave Fourier transformations are like musical notation we can sing a song from memory but we can also write down what to play if you play the right Keys together it sounds exactly like the original song in other words we are adding up frequencies to recreate the original waveform musical notation is what you might call a time result Fourier transform you're creating slices in time and at each time step you are specifying the frequency spectrum in this case the court another example which fits this idea is related to cooking of recipes we can describe a dish by what a tastes like so when I take a bite of something I can taste the sugar I can taste the salt I taste a pecan I taste raisins baking soda however we can also describe it by the ingredients used to cook the dish if we add the right amount of ingredients in the right amount we can actually recreate the taste so we can taste a food item deconstruct it into its fundamental components if you will and if we understand exactly the right quantities of these fundamental components it is then theoretically possible to rebuild back up to the original dish in this case and that's the essence of the Fourier transform now there's some other really interesting features to the before you transform we can apply it to recreate the shapes of two-dimensional objects so here what we're looking at is an image where we have an original shape which is it's a two-dimensional shape but it's it's complicated you can see I mean it's got a curved edge on one side and then there's these protrusions that are like legs coming out on the other end and through a series of harmonics we can see that as we progress to higher harmonics that the shape itself is being reconstructed through the combination of all these harmonics so in in our example if we look at 200 harmonics and down in the bottom right hand side we see then we can built up back to the original shape here's another example we're taking an outline of the leaf at the right summarize using 1 5 and 10 harmonics which in this case we're using an elliptic Fourier analysis here is a representation of a complex image processing approach through a Fourier transformation so we talked about being able to look at images and process information out of images through the Fourier transform and we can see that we can break it down into high and low spatial frequencies and from these frequencies that were working with we can then apply the Fourier transform Stewart riffle has a really elegant explanation in a single sentence which describes the Fourier transform so we have this intimidating formula earlier and now we're actually going to break it down into something that's a little more palatable what's nice about this is the different functions here are color coded so when we look at this you know there are imaginary numbers pi is in there we have all sorts of sub components you know numbers you know along a particular path but essentially what is the same is that in order to find the energy at a particular frequency we spin the signal around a circle in this case this is the 2 pi that we see in the equation at that frequency and then we average a bunch of points along that path so this donking formula involves imaginary numbers complex summations but the idea really is fundamentally simple one way to think of it is imagine an enormous speaker mounted on a pole plane a repeating sound the speaker is so large you can see the cone move back and forth with the sound we mark a point on the cone and now rotate the pole we trace the point from an above ground view if the resulting squiggly curve is off-center there is frequency corresponding the poles rotational frequency is represented in the sound so here is an image that that depicts what we're talking about to hear the upper signal is made up of three frequencies or knowns but only the bottom right squiggle is generated by a rotational frequency matching one of the component frequencies in this signal so if you search online you will actually find some really nice animations from a number of different folks that walk through and show the Fourier transform as it's developing over time there's some really fantastic resources out there and I would highly recommend you check them out well brace yourselves for the Fourier series are coming now we're going to get into some of the heavier stuff starting with the fast Fourier transformation and what the fast Fourier transform or the FFT it's an algorithm to compute the discrete Fourier transform and it's inverse a fast Fourier transform rapidly computes such transformations by factoring the discrete Fourier transform matrix into a product of sparse mostly 0 factors as a result fast Fourier transforms are widely used for many applications in engineering science and mathematics in 1994 Gilbert strain described the fast Fourier transform as the most important numerical algorithm of our lifetime and it was included in top 10 algorithms of 20th century by the OEE garel of computing and science and engineering so the fast Fourier transform is a remarkable algorithm and is very versatile in terms of what it can do let's now go back into history a little bit and discuss the development of the fast Fourier transformation the development of the fast algorithm for dfts can be traced back to Gauss's unpublished work in 1805 when he needed it to interpolate the orbit of asteroids paleis and Juno from sample observations his method was very similar to the one published in 1965 by Cooley and 2p who are generally credited for the invention of the modern generic fast fourier transform algorithm while else's work predated even for EAS results in 1822 he did not analyze the computation time and eventually use other methods to achieve his goal John to Keith who worked at IBM's Watson labs came up with the idea during a meeting of President Kennedy's Science Advisory Committee where a discussion topic involved detecting nuclear tests from the Soviet Union by setting up sensors that surrounds the country from the outside it to analyze the output of these sensors a fast Fourier transform algorithm was needed to keys idea was given to Cooley for implementation while hyping the original purpose from Cooley for security reasons as Cooley didn't work at IBM the patentability of the idea was doubted and the algorithm went to the public domain which through the computing revolution of the next step decade made fast Fourier transforms one of them indispensable algorithms in digital signal processing by far the most commonly used fast fourier transform is the Cooley Tookie algorithm although there are many other forms of the fast Fourier transformation a fast Fourier transform computes the DFT and produces exactly the same result as evaluating the DFT definition directly the most important difference is that the FFT is much faster the FFT approach is a divide-and-conquer algorithm that recursively breaks down a DFT of any composite size into many smaller dfts of sizes and 1 and n 2 along with multiplications by complex roots of unity traditionally called twiddle factors these swittel factors are named after a gentleman and sand in 1966 and the depiction that we have on the left hand side is of a twiddle factor which to me it kind of looks like a snowflake or a tiny star if you will or the spokes of a wheel improved expanded upon in the core of what has come to be known as the field of harmonic analysis fourier analysis has evolved and progressed to include the study of more abstract and general phenomenon fourier analysis is now used actively regularly and widely in econometrics and financial market theory by researchers and practitioners to forecast so if we think about econometrics time series essentially we're looking at the development of markets over time so since we know the time component is a critical element of Fourier analysis and the the fast Fourier transform we can think about any type of application involving time in this construct of a Fourier analysis Fourier analysis also is used to analyze and vetericyn understand the nature and behavior a wide range of time series data and parameters that exhibit nonlinear relationships and repeating wave-like patterns over time that's kind of one of the key attributes of a Fourier analysis in econometrics research or financial market research is we have to look at time series data that is nonlinear in nature but having patterns repeating over time among its many applications it has been used to model long term economic cycles the relationship between inflation and the demand for money and patterns and trends and stock foreign exchanges and housing markets and cycles in the semiconductor industry it has also been used to measure the efficiency of a national economy fast Fourier transforms are also useful as a high-pass to remove low frequency periodic variations so hourly daily weekly and then what we can do is then we can back transform to the time domain and then use that as the input for your monitoring tools so we can combine the use of a Fourier analysis with other machine learning and predictive analytics techniques in our data science arsenal so not only can it be applied in econometrics in kind of this novel sort of way but we can think of taking time series information deconstructing it into certain components through with a Fourier transform and then putting models on top of those deconstructed components spec includes our introduction to fourier analysis in the fast fourier transform now we're going to shift gears and move into a practical example but before we do I wanted to show this image because I think this is just absolutely fantastic it is he was sending me mixed signals so I did a Fourier analysis which to me is funny on so many levels of it and I think after watching the first part of the presentation it now makes sentence and if you actually go back to the overview page the second slide in the presentation and you look at that joke about the Fourier transform on the cat it's actually quite funny so our practical example that we're going to get into today is going to be related to manufacturer's order volume and this is a very relatable business problem that I think many of us will be facing when we're working in data science if we're working in a business context we can think of it as manufacturing is a field where predictive analytics can have a significant impact on operational efficiency and risk if we can plan our production volumes with greater degree of precision then we can work on advanced topics such as utilization capacity we can address working capital type of constraints we can optimize our revenue our margins ultimately bringing this to higher return on sales and higher a bit without trustworthy guidance on the expected amount orders to be fulfilled in the near future usually a significant stockpile of parts for raw materials and spare capacities are necessary in order to compensate for the variances in the volume of incoming orders so if we don't know when our customers are gonna be placing our orders we can either allow them to be back ordered or we can bring in a lot of inventory which is tying up our capital so it's increasing our overall working capital and that's not good for business you want to be a little more liquid in terms of your cash in this example our goal is going to be to devise we're going to develop a time series prediction to determine the projected order volume for a manufacturer in this we're going to utilize the fast Fourier transform and artificial neural networks to create the algorithm before we begin I think it's important that we have an understanding of the data that we're working with so when I look at the the raw input data here it's very simple four columns of information I have the year the quarter the week and the amount of orders and we're working on these weekly advocates of the worldwide amount of orders normalized in between zero one interval in this case the value of the week and quarter columns is relative with respect to the year and this data set contains values from the first quarter of 2009 through the first quarter of 2011 and before we move into the next sections this analysis is all being constructed using the our language now I know you can use this in Python and other techniques but I just wanted to let you know as we're walking through this example even though I'm not posting the code it is our based in nature and I do have that code or readily available so one of the first things that we do is we're gonna invoke ggplot2 in this case and we're going to review the order volume to see if there's a frequency of the pattern let's remember our time series we want to look for frequencies and regular intervals in the time series so we're just doing an exploratory data analysis trying to understand if this time series is something that fits into a fast Fourier transform and it is apparent that there is a lot of similarity between the two for years and the one quarter we have data before we can see as each week is progressing throughout the year there's a normal Abbot inflow to the business and then and this is an important characteristic that we have to hone in it and to me there actually seems to be a very strong periodic or ters as well and what this does is this suggests that there is an underlying structure in the data that can be used for forecasting however there seems to be a strange one-week difference between the apparent peaks of the two full years by changing the graph into a by quarter histogram of the week values it uncovers the cause very quickly there was one more Business Week in the first quarter of 2009 then in the first quarter of 2010 and 2011 so having a longer time frame to look for more orders were stacked in that one particular quarter which is essentially skewing the data but we can see this very quickly through an effective EDA consequently there is a consistent one-week difference between the last weeks of the quarters however due to the sudden surge of new orders from the business point of view this is exactly the week that counts the most so this lag of one week going from quarter to quarter normally wouldn't be too much of a concern we can address it in certain ways however this is where we have the big Spyke and this is the one that we have to look at in the greatest amount of detail the model building approaches we will use later can usually cope with such a one-week offset discrepancy here is what we can tell now from these plots so let's go back to each one of these quarters and let's see what we can infer from it at the very end of the quarter there is always a significant spike in the orders for q3 and q4 even the exact amounts are very close during the quarters there's also significant similarity between the orders on the whole the time series seems to be stationary in a highly periodic therefore it should be worthwhile to analyze as characteristics in the frequency domain a visual inspection and hinted at a strong periodicity in a time series at the quarter half year in year intervals in order to prove this suspicion we now perform a brief power spectrum analysis of the first two years of the data 2011 q1 is omitted here we would like to look at full years to uncover possibly yearly curiosity also this analysis will lead us to the training data for the forecasting approach and 2011 q1 is kept for back testing purposes so remember with time series and general statistical time series predictions we want to validate our results up against a set of actual known data so in this case we're going to hold a ha q1 2011 to validate these models up against we apply the common fast Fourier transformation extend the results with the frequency member index and plot the value of the complex modulus the frequency index note that the zero frequency component is omitted here also as the input signal is real valued it is symmetric in the remaining frequencies therefore only the lower half of the spectrum is potted this results in the following power spectrum plot that uses the complex modulus to measure magnitude so this is essentially we can think of these as our frequency wave patterns no it is apparent that a number of these frequencies have significantly higher amplitude than the others hinting as strong underlying periodic nature in the data let's identify these Peaks so if I'm looking at this chart and I'm looking where the major Peaks are it we see home at 0 18 16 24 32 40 and 48 most notably right here what we see is that a component with the frequency of 8 divided by 104 which is 2 times 4 quarters in the two full years and it's harmonics an important note is the exact difference of 8 between the peaks seem to dominate the signal so when I'm looking at this particular frequency pattern these Peaks are so significant with difference of 8 between each one of the signals here however these frequencies alone are insufficient to capture the time series to the precision we would like to to demonstrate this we eliminate the frequencies with small magnitudes in the copy of the Fourier transform the remaining ones are transferred back to the time domain an inverse fast Fourier transform call in order to be compared it to the original time series so this is the concept of who were now taking this wave deconstructing it into the smaller components and then were reconstructing it back to its original function and now we're comparing it against the actual data in this case the signal we deal with shows strong regularity but is at the same time highly complex and it's decidedly nonlinear so when we look at the time series and how it is evolving over time in this case we see that there is a nonlinear pattern therefore for forecasting purposes we split it into simpler periodic time series and then we train artificial neural networks for the finite time window forecasting of each simplified component the splitting is based on a non-threatening partitioning of the frequency domain and this is some nice way of saying that when we're taking our complex wave signal and we're breaking it down into its components that we're just looking for components that aren't interfering with other components therefore our prediction approach is the following new time series data is concatenated to the training set as it becomes available this new extended time series is again split with the same band pass filtering utilized for the training data the new simplified time series set the elements of which are extended with the images of the new observations is used to exercise the corresponding forecasting neural network the key point is that the order forecast for the unsplit signal is reached by summing the outputs of the component forecasting neural networks so we're taking our time series and as new information is becoming available then we're evaluating the entire series breaking it down into simpler subcomponents and then we are forecasting on these smaller subcomponents after these forecasts have been created then we're going to aggregate them and build back up to our final prediction of the time series so let's talk a little bit about the signal decomposition so we split the frequency domain of the time series into intervals and this is what I was talking about before where we can see each one of the seven sub series are breakdowns and they're waves at different interval levels each interval contains either the fundamental frequency of the strong periodic signal or one harmonic of it this is effectively a bandpass filtering based decomposition for the two year time series in harmonic sent this produces the following decomposition in the time domain we use the multi-layer perceptron fleet forward artificial neural network model to map a finite time window of order observations on to predictions about the orders that can be expected in the future we will have a number of neural networks each one responsible for learning and predicting a frequency band of the original we assume that cutting up the original signal by using frequency bands results in sub signals that are fundamentally easier to predict and that's why we we are basically breaking these signals into smaller components because we're trying to simplify the signal through each iteration of the bandpass filtering note in the following section where we're training it we're working actually with a slightly different time series so we're only looking at 105 observations and the main frequency harmonics in this case are slightly different there at 917 25 33 so on and so forth in our Fourier series the results of the neural network trainings for the different D composed signals can be seen on the figure to the right the red line is the response of the network and the black is the original time series all training data fits very well and the response of the neural networks at the training samples is accurate so when we're looking at the black line versus a red line we see that it's mimicking the structure quite well the mean squared error for all the training is smaller than 10 to the negative 5 so as expected just from a visual observation we expect the error to be very low and we actually see that it's very low in this case through the mean squared error metric or statistic because the Fourier transform is a linear operation the sum of the individual predictions will give the full time series prediction back to us so when we add up all of these various decomposed elements we should return to an aggregate prediction we mentioned earlier that we have used only the first eight quarters as training data so we left out q1 of 2011 now we will use that data for the last ninth quarter and check how well we can predict with a one quarter horizon so so we're taking our original data and now we're building our model off a bit more prick'd predicting forward 1/4 in this approach we predict one week use the results of the prediction to augment the historical data and then exercise the predictor with this new input again so we're kind of layer by layer building out our prediction in this case theoretically this feedback strategy can be used to predict to arbitrarily long horizons in the future let's look at our prediction results so here the error is calculated as the root mean square error statistic for the predicted time series the root mean squared error value is 0.08 which is a relatively low error rate we can actually see when we're looking visually at the the red and the black lines in this case we see that the error metric follows ensued fairly well now we may also want to know what kind of data should be predicted by the single neural networks thus what kind of forecast would result in a perfect prediction so in this example the training data signals are black the predicted signals are red and the blue lines are the signals that would have belonged to the perfect prediction so we can see how our actual data was developing over time through our through our feed-forward strategy in the training this particular time series and we can compare our prediction against the art observed against the perfect prediction in this case highlighted is blue the signals that were predicted more accurately where where the signal was periodic and those signals had the highest errors where the trend was dominant the first and the second signals here is the final recombination of the prediction for the next fourteen periods so we talked about we have these different harmonic series that are built and remember we have to add them all together because they're linear in nature to get to our final prediction so if I take the sum of each one of these harmonics I have my prediction and then I can now bring the data back to the data frame I can you see behind our bind and our full suite of tools in our you know I can create you know comparison metrics between actual and the predictive performance well that concludes our tutorial on the Fourier analysis thank you very much for joining it was a pleasure walking through these concepts with you and make sure to check out some of my other videos and you know if these are concepts that you like feel free you know to comment on them or you know send me a message on YouTube or to my gmail account and best of luck you

Channel: Derek Kane

Views: 19,816

Rating: 4.8644066 out of 5

Keywords: Data (Website Category), Fourier Analysis, Machine Learning, Econometrics, Statstics, Neural Network, Fourier Transform, Predictive Analytics, Operations, Time Series, Harmonics, Fourier, Data Science, Software

Id: DTOWsoM__HI

Length: 43min 38sec (2618 seconds)

Published: Wed Jul 01 2015