Feature based graph pruning for improved forecast reconciliation

3rd July 2024 @ ISF 2024

Mitchell O’Hara-Wild, Monash University

Supervised by Rob Hyndman and George Athanasopoulos

Useful links

social.mitchelloharawild.com

slides.mitchelloharawild.com/pruning-graphs

mitchelloharawild/talk-pruning-graphs

Reconciliation recap

Reconciliation adjusts related forecasts so they add up correctly (coherent).

Related time series are described in three ways:

📚 Hierarchical

One path from top to bottom.

G cluster_1 Bottom cluster_0 Upper AX AX AY AY BX BX BY BY Total Total A A Total->A B B Total->B A->AX A->AY B->BX B->BY

📚 Grouped

Many paths from top to bottom.

G cluster_2 Path AB cluster_3 Path XY cluster_0 Bottom cluster_1 Top BY BY BX BX AY AY AX AX Total Total A A Total->A B B Total->B X X Total->X Y Y Total->Y A->AY A->AX B->BY B->BX X->BX X->AX Y->BY Y->AY

💡 Graph (ISF2023)

Many paths from (many) top to (many) bottom series.

G cluster_1 Unconstrained XY cluster_2 Unconstrained AB cluster_0 Constrained X2 X2 X1 X1 Y Y B2 B2 B1 B1 A3 A3 A2 A2 A1 A1 Total Total Total->Y X X Total->X A A Total->A B B Total->B X->X2 X->X1 A->A3 A->A2 A->A1 B->B2 B->B1

Reconciliation recap

❤️ Forecasters love reconciliation

  • Widely understood to improve forecast accuracy

  • All forecasts are wrong…

    … but coherent forecasts are less wrong!

💔 At times its a love-hate relationship

  • Disaggregation can produce a lot of time series
  • Too many series is expensive to forecast

Today, I hope to help you love reconciliation more!

Forecasting textbook pageviews

Data overview

  • Google Analytics data since 1 January 2020

  • Daily page views (and users)

  • Disaggregated by many dimensions

    (e.g. location, device, returning visit, web page, …)

Illustrative example

I’ll gloss over many details specific to forecasting this data (I promise it’s not interesting or important)!

This data will illustrate how coherent pruning is useful for forecast reconciliation - far more interesting!

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

💡 Idea: graph pruning

Many time series aren’t interesting or useful.

Simply don’t forecast them!

Removing uninformative series has many benefits:

  • ✅ Less computation time
  • ✅ Less model misspecification
  • ✅ Better accuracy?

From grouped to graph

This is made possible with graph reconciliation.

Simply removing series breaks the coherency structure.

We also must remove the relevant coherency constraints.

💡 Idea: graph pruning

Maintaining coherency

Even if a series is unwanted, it can’t be removed if other useful series are used in the same disaggregation.

There are two fundamental decisions involved in pruning:

  1. The predicate: the test for ‘forecastability’.
  2. The disaggregation rule: a function that decides if the set of disaggregates are kept.

To maintain coherency, the decision at each disaggregation is all or nothing.

💡 Idea: graph pruning

Automated graph pruning with features

Starting from the top to bottom, we evaluate the ‘forecastability’ of each series with the predicate.

This can be done automatically with features, such as:

  • The average value (scale)
  • The number of zeroes (intermittency)
  • The strength of seasonality (structure)

If the disaggregated series satisfy the disaggregation rule, we disaggregate further.

Repeat this through the graph until we reach completely uninteresting data, or the bottom series.

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

deviceCategory*(continent/subContinent/country)

Graph pruning practicality

The small example

On this small example with structure:

deviceCategory*(continent/subContinent/country)

There were a total of 1305 time series.

A simple pruning with…

  • predicate: average >10, <50% zeroes
  • disaggregate rule: >50% forecastable

Was able to maintain coherent forecasting accuracy with <50% of the data (666 observations).

Graph pruning practicality

The big picture

The actual data has 100s of disaggregating dimensions.

With this slightly larger structure:

operatingSystem*userType*deviceCategory*

(pagePathLevel1/pagePathLevel2)*

(continent/subContinent/country)

There are a total of… 🥁

1,699,593,840 time series.

🗑️ A simple pruning later…

< 10,000 useful time series, minimal loss of information.

Pruned graph reconciliation

Graph pruning of coherent time series solves big problems with forecast reconcilation.

Grouped constraints

Since grouped constraints require a common bottom series, previously all disaggregates must be forecasted.

To keep the data small…

useful dimensions had to be dropped ❌

Graph constraints

With graph constraints, there can be any structure.

To keep the data small…

useless series can be dropped! ✅

Final comments

Key ideas

  1. Evaluate reconciliation on relevant forecasts
  2. Be wary of model misspecification in large hierarchies
  3. Less can be more for forecast reconciliation
  4. Prune uninformative series, keep useful dimensions

Future work

  • Refine metrics of ‘forecastability’
  • Lump uninformative series together
  • Expand pruning rules with graph concepts (e.g. depth)
  • Finish software design and implementation

Thanks for your time!

Useful links

social.mitchelloharawild.com

slides.mitchelloharawild.com/pruning-graphs

mitchelloharawild/talk-pruning-graphs

This is a student presentation, please rate it!