Hierarchical Quickest Change Detection

Changepoints are points in a time-series surrounding which the underlying time-series distribution changes significantly. Quickest Change Detection is the problem of declaring such changepoints with minimal delay under maximum allowable probability of false alarm. HQCD find changepoints for possibly inhomogeneous sources via a hierarchical framework.

HQCD Overview:

  • Sources grouped into targets and surrogates
    • Targets: sources of importance
    • Surrogates: sources which can explain targets
  • Upper bounds probability of false alarm under the source-target importance relationship - ML-PFA
  • Runs in real-time using specialized sequential Monte-Carlo simulations
  • Infers causal connections between targets and surrogates via detected changepoints

Case Study: Brazil

Brazil witnessed its largest and protest during mid-2013 - often termed as the Brazilian Spring. We analyze Brazilian spring using HQCD (and compare against several state-of-the art methods) to identify the tipping point in the protest timeline by simultaneously modeling the different protest types and protest related chatter in Twitter.

Total Protests



  • Major Events leading to Mass protests
    • Jun 21-23 : Brazilian Spring saw around 250,000 protesters on Jun 17

  • HQCD found Jun 16th as the changepoint in total protests
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 2013050100150
Changepoint in Total ProtestsTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD

Protests by Categories

Total protests aggregates different kinds of protests which masks several key events. HQCD finds those events by categories below.



  • Major Energy and Resources related events leading to Mass protests
    • Jun 02 Protest against ban of vans which were used as alternate means of transport
    • Jun 02 : Evacuation of landless people in Sao Paulo

  • HQCD declares significant change in this category to be Jun 02
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 2013020406080
Changepoint in Energy and ResourcesTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD


  • Major Housing related events leading to Mass protests
    • Jun 14 : Protests for affordable housing near the National Stadium at the Capital
    • Jun 14 : Protests against World Cup questioning evacuation of residents

  • HQCD declares significant change in this category to be Jun 16
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 2013012345
Changepoint in HousingTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD


  • Major Govt. related events leading to Mass protests
    • Jun 15 : Protests against police violance in the state of Sao Paulo

  • HQCD declares significant change in this category to be Jun 16
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 20130510152025
Changepoint in Other GovernmentTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD


  • Major Other related events leading to Mass protests
    • Jun 21 : Protestors close highways
    • Jun 21 : Violent protests in cities that hosted the Confederation cup

  • HQCD declares significant change in this category to be Jun 23
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 2013010203040
Changepoint in OtherTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD


  • Major Economic related events leading to Mass protests
    • Jun 27 : Student protests demanding better allocation of public funding towards education
    • Jun 29 : Protest marches demanding better GDP investment policies

  • HQCD declares significant change in this category to be Jun 30
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 2013051015
Changepoint in Other EconomicTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD


  • Major Employment related events leading to Mass protests
    • Aug 16 : Teachers and professionals demanding increase in wages
    • Aug 18 : Protests against ultimatum set by the municipality w.r.t. wage protests

  • HQCD declares significant change in this category to be Aug 18
Feb 2013Mar 2013Apr 2013May 2013Jun 2013Jul 2013Aug 2013Sep 20130102030
Changepoint in EmploymentTimeNumber of protestsBOCPDGLRTW-GLRTRuLSIFHQCD

Explaining Brazilian Spring

Significant changes for different protest categories occurred at different timepoints. We are interested in analysing how changes in these categories influence each other. HQCD provides a changepoint correlation matrix for target-target and target-surrogate as below. Through these matrices we can find the interaction strengths.

EmploymentEnergyHousingOtherEconomicGovernmentEmploymentEnergyHousingOtherEconomicGovernment
Changepoint through Protests10152025303540
cluster-00cluster-01cluster-02cluster-03cluster-04cluster-05cluster-06cluster-07cluster-08cluster-09cluster-10cluster-11cluster-12cluster-13cluster-14cluster-15cluster-16cluster-17cluster-18cluster-19cluster-20cluster-21cluster-22cluster-23cluster-24cluster-25cluster-26cluster-27cluster-28cluster-29EmploymentEnergyHousingOtherEconomicGovernment
Changepoint through Twitter5101520253035

Analysis

  • Other Economic and Employment were affected by Housing related protests. Although, total number of housing protests were much smaller compared to the other categories.
  • Housing and employment shares influences from similar Twitter chatter clusters(cluster 01 and 26). - Strong interaction came from social sphere
  • Housing and Other Economic are weakly related through Twitter chatter clusters - interactions manifested via category relation only.

Comments