**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Using Polynomials to Forecast Univariate Time Series

1996

Conference paper

Conference paper

Abstract

Polynomial autoregressions have been most of the time discarded as being unrealistic. Indeed, for such processes to be stationary, strong assumptions on the parameters and on the noise are necessary. For example, the distribution of the latter has to have finite support. Nevertheless, the use of polynomials has been advocated by a few authors: Cox (1991), Cobb and Zacks (1988) and Chan and Tong (1994). From a model-free perspective, that is using parametric families of functions (e.g. Fourier series, wavelets, neural networks, MARS, ...) as approximators of the optimal predictor, there is no more concern about stationarity. Still, polynomials have not been used within this framework; the reason is the now well known "curse of dimensionality". Indeed, when high lag orders are used to forecast, a common situation in time series, polynomial autoregressions imply too many parameters to estimate. We will introduce a new family of predictors based on polynomials and on a projection scheme. A censoring procedure allows to solve the instability inherent to polynomials. The forecasting method is parsimonious (that is non-linearity is introduced with a small amount of parameters) and thus allows to forecast noisy time series of short to moderate length.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (3)

Related concepts (15)

Linear regression

In statistics, linear regression is a linear approach for modelling the relationship between a scalar response and one or more explanatory variables (also known as dependent and independent variable

Time series

In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. T

Linear prediction

Linear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples.
In digital signal processing, linear prediction is

Loading

Loading

Loading

This dissertation introduces traffic forecasting methods for different network configurations and data availability.Chapter 2 focuses on single freeway cases.Although its topology is simple, the non-linearity of traffic features makes this prediction still a challenging task.We propose the dynamic linear model (DLM) to approximate the non-linear traffic features. Unlike a static linear regression model, the DLM assumes that its parameters change over time.We design the DLM with time-dependent model parameters to describe the spatiotemporal characteristics of time-series traffic data. Based on our DLM and its model parameters analytically trained using historical data, we suggest the optimal linear predictor in the minimum mean square error (MMSE) sense.We compare our prediction accuracy by estimating expected travel time based on the traffic prediction for freeways in California (I210-E and I5-S) under highly congested traffic conditions with other baselines. We show significant improvements in accuracy, especially for short-term prediction.Chapter 3 aims to generalize the DLM to extensive freeway networks with more complex topologies.Most resources would be consumed to estimate unnecessary spatiotemporal correlations if the DLM was directly used for a large-scale network.Defining features on graphs relaxes such issues by cutting unnecessary connections in advance based on predefined topology information.Exploiting the graph signal processing, we represent traffic dynamics over freeway networks using multiple graph heat diffusion kernels and integrate the kernels into DLM with Bayes' rule. We optimize the model parameters using Bayesian inference to minimize the prediction errors.The proposed model demonstrates prediction accuracy comparable to state-of-the-art deep neural networks with lower computational effort. It notably achieves excellent performance for long-term prediction through the inheritance of periodicity modeling in DLM.Chapter 4 proposes a deep neural network model to predict traffic features on large-scale freeway networks.These days, deep learning methods have heavily tackled traffic forecasting problems of freeway networks because they are outstanding at learning highly complex correlations between variables both in time and space, which the linear models might be limited to.Adopting a graph convolutional network (GCN) becomes a standard to extract spatial correlations; therefore, most works have achieved great prediction accuracy by implanting it into their architecture.However, the conventional GCN has the drawback that receptive field size should be small, i.e., barely refers to traffic features of remote sensors, resulting in inaccurate long-term prediction.We suggest a forecasting model called two-level resolution deep neural network (TwoResNet) that overcomes the limitation.It consists of two resolution blocks:The low-resolution block predicts traffic on a macroscopic scale, such as regional traffic changes.On the other hand, the high-resolution block predicts traffic on a microscopic scale by using GCN to extract spatial correlations, referring to the regional changes produced by the low-resolution block.This process allows the GCN to refer to the traffic features from remote sensors.As a result, TwoResNet achieves competitive prediction accuracy compared to state-of-the-art methods, especially showing excellent performance for long-term predictions.

This thesis focuses on developing efficient algorithmic tools for processing large datasets. In many modern data analysis tasks, the sheer volume of available datasets far outstrips our abilities to process them. This scenario commonly arises in tasks including parameter tuning of machine learning models (e.g., Google Vizier) and training neural networks. These tasks often require solving numerical linear algebraic problems on large matrices, making the classical primitives prohibitively expensive. Hence, there is a crucial need to efficiently compress the available datasets. In other settings, even collecting the input dataset is extremely expensive, making it vital to design optimal data sampling strategies. This is common in applications such as MRI acquisition and spectrum sensing.
The fundamental questions above are often dual to each other, and hence can be addressed using the same set of core techniques. Indeed, exploiting structured Fourier sparsity is a recurring source of efficiency in this thesis, leading to both fast numerical linear algebra methods and sample efficient data acquisition schemes.
One of the main results that we present in this thesis is the first Sublinear-time Model-based Sparse FFT algorithm that achieves a nearly optimal sample complexity for recovery of every signal whose Fourier transform is well approximated by a small number of blocks (e.g., such structure is common in spectrum sensing). Our method matches in sublinear time the result of Baraniuk et. al. (2010), which started the field of model-based compressed sensing. Another highlight of this thesis includes the first Dimension-independent Sparse FFT algorithm that, computes the Fourier transform of a sparse signal in sublinear runtime in any dimension. This is the first algorithm that just like the FFT of Cooley and Tukey is dimension independent and avoids the curse of dimensionality inherent to all previously known techniques. Finally, we give a Universal Sampling Scheme for the reconstruction of structured Fourier signals from continuous measurements. Our approach matches the classical results of Slepian, Pollak, and Landau (1960s) on the reconstruction of bandlimited signals via Prolate Spheroidal Wave Functions and extends these results to a wide class of Fourier structure types.
Besides having classical applications in signal processing and data analysis, Fourier techniques have been at the core of many machine learning tasks such as Kernel Matrix Approximation. The second half of this thesis is dedicated to finding compressed and low-rank representations of kernel matrices, which are the primary means of computation with large kernel matrices in machine learning. We build on Fourier techniques and achieve spectral approximation guarantees to the Gaussian kernel using an optimal number of samples, significantly improving upon the classical Random Fourier Features of Rahimi and Recht (2008). Finally, we present a nearly-optimal Oblivious Subspace Embedding for high-degree Polynomial kernels which leads to nearly-optimal embeddings of the high-dimensional Gaussian kernel. This is the first result that does not suffer from an exponential loss in the degree of the polynomial kernel or the dimension of the input point set, providing exponential improvements over the prior works, including the TensorSketch of Pagh (2013) and application of the celebrated Fast Multipole Method of Greengard and Rokhlin (1986) to the kernel approximation problem.

In this thesis, we advocate that Computer-Aided Engineering could benefit from a Geometric Deep Learning revolution, similarly to the way that Deep Learning revolutionized Computer Vision. To do so, we consider a variety of Computer-Aided Engineering problems, including physics simulation, design optimization, shape parameterization and shape reconstruction. For each of these problems, we develop novel algorithms that use Geometric Deep Learning to improve the capabilities of existing systems. First, we demonstrate how Geometric Deep Learning architectures can be used to learn to emulate physics simulations. Specifically, we design a neural architecture which, given as input a 3D surface mesh, directly regresses physical quantities of interest defined over the mesh surface. The key to making our approach practical is re-meshing the original shape using a polycube map, which makes it possible to perform computations on Graphic Process Units efficiently. This results in a speed up of 2 orders of magnitude with respect to physics simulators with little loss in accuracy: our main motivation is to provide lightweight performance feedback to improve interactivity in early design stages. Furthermore, being a neural network, our physics emulator is naturally differentiable with respect to input geometry parameters, allowing us to solve shape design problems through gradient-descent. The resulting algorithm outperforms state of-the-art methods by 5 to 20% for 2D optimization tasks and, in contrast to existing methods, our approach can be further used to optimize raw 3D geometry. This could empower designers and engineers to improve the performance of a given design automatically, i.e. without requiring any specific knowledge about the physics of the problem they are trying to solve. To perform shape optimization robustly, we develop novel parametric representations for 3D surface meshes that can be used as strong priors during the optimization process. To this end, we introduce a differentiable way to produce explicit surface mesh representations from Neural Signed Distance Functions. Our key insight is that by reasoning on how implicit field perturbations impact local surface geometry, one can ultimately differentiate the 3D location of surface samples with respect to the underlying neural implicit field. This results in surface mesh parameterizations that can handle topology changes, something that is not feasible with currently available techniques. Finally, we propose a pipeline for reconstructing and editing 3D shapes from line drawings that leverages our end-to-end differentiable surface mesh representation. When integrated into a user interface that provides camera parameters for the sketches, we can exploit our latent parametrization to refine a 3D mesh so that its projections match the external contours outlined in the sketch. We show that this is crucial to make our approach robust with respect to domain gap. Furthermore, it can be used for shape refinement given only single pen strokes. This system could allow engineers and designers to translate legacy 2D sketches to real-world 3D models that can readily be used for downstream tasks such as physics simulations or fabrication, or to interact and modify 3D geometry in the most natural way possible, i.e. with a pen stroke.