Dictionary Based Pattern Entropy for Causal Direction Discovery

This paper introduces Dictionary Based Pattern Entropy (DPE), a novel framework that combines Algorithmic and Shannon Information Theories to infer causal directions and identify driving subpatterns in symbolic sequences by quantifying how compact, rule-based patterns in a cause systematically reduce uncertainty in an effect, demonstrating robust performance across diverse synthetic and real-world datasets.

The Gist

Imagine you are a detective trying to solve a mystery: Who is influencing whom?

You have two friends, let's call them Alex and Jamie. You watch them for a day. Every time Alex sneezes, Jamie jumps. Every time Jamie claps, Alex smiles. But who is causing the reaction? Is Alex sneezing because Jamie clapped? Or is Jamie jumping because Alex sneezed?

In the world of data science, this is called Causal Discovery. Usually, computers need to know the "rules of the game" (like physics equations) or have massive amounts of data to figure this out. But what if the data is just a string of symbols (like 0s and 1s) and you don't know the rules? That's where this paper comes in.

The authors propose a new method called Dictionary Based Pattern Entropy (DPE). Here is how it works, explained simply:

1. The Core Idea: "The Rulebook"

Imagine Alex and Jamie are playing a secret code game.

• The Old Way: Most methods try to guess the whole mathematical formula connecting them. It's like trying to solve a complex equation without knowing the variables.
• The DPE Way: This method says, "Let's just look for repeating patterns."

It assumes that if Alex is truly the boss (the cause), there will be specific, compact "chunks" of Alex's behavior that always trigger a specific reaction in Jamie. These chunks are like secret handshakes.

2. Step-by-Step: How the Detective Works

Step A: Build the Dictionary (The "Cheat Sheet")

The computer watches the two streams of data (Alex and Jamie).

• It looks at every time Jamie changes their behavior (e.g., goes from calm to jumping).

• It looks backwards at what Alex was doing just before that change.

• It writes down those specific "Alex patterns" in a Dictionary.

• Analogy: Imagine you are a chef. Every time the oven beeps (the change), you look at what you did 5 minutes ago. You write down: "When I put the dough in, the oven beeps." You build a dictionary of "Dough In" $\rightarrow$ "Beep."

Step B: The "Flip" Test (The "Did it work?" Check)

Now, the computer takes every pattern in its dictionary and asks: "Does this pattern always cause a change?"

• If the pattern "Dough In" appears 10 times, and the oven beeps 10 times, that's a perfect rule. (High certainty).
• If the pattern appears 10 times, but the oven only beeps 3 times, that's a weak rule. (High uncertainty).

The method calculates a score called Response Determinism.

• Score of 1.0: "Whenever I see this pattern, the change always happens." (Very strong cause).
• Score of 0.5: "Sometimes it happens, sometimes it doesn't." (Weak cause).
• Score of 0.0: "This pattern has nothing to do with the change."

Step C: The Entropy Score (The "Confusion Meter")

This is the magic part. The method calculates Entropy, which is basically a measure of confusion or surprise.

• Low Entropy (Low Confusion): The pattern is a reliable rule. "If A, then B." The future is predictable.
• High Entropy (High Confusion): The pattern is random. "If A, maybe B, maybe C." The future is a mystery.

The Verdict:
The computer compares the two directions:

1. Alex $\rightarrow$ Jamie: How much confusion is there when we try to predict Jamie based on Alex's patterns?
2. Jamie $\rightarrow$ Alex: How much confusion is there when we try to predict Alex based on Jamie's patterns?

The Winner: The direction with the lowest confusion (lowest entropy) is the true cause. Why? Because the true cause usually has a clear, rule-based structure. The effect is often messy and noisy.

3. Why is this special?

Most other methods are like trying to guess the weather by looking at the whole sky at once. They get confused easily.
DPE is like looking for specific cloud shapes that always mean rain.

• It doesn't need to know the physics of clouds.
• It doesn't need millions of years of data.
• It just finds the specific sub-patterns that drive the change.

4. Real-World Examples from the Paper

The authors tested their "Detective" on several scenarios:

• Delayed Bit-Flips: Like a game of "Red Light, Green Light" where the reaction is slightly delayed. DPE figured it out 99% of the time.
• Predator-Prey: In nature, predators eat prey, which then changes the predator's population. DPE correctly identified that the predator drives the prey's movement more than the other way around.
• Virus Evolution: They looked at SARS-CoV-2 virus sequences to see if the global virus caused local mutations or vice versa. DPE gave competitive results, helping scientists understand how the virus spreads.

The Big Takeaway

This paper introduces a tool that finds cause and effect by looking for reliable patterns rather than complex math.

• If you see a pattern that consistently triggers a change, you've found the cause.
• If the relationship is messy and unpredictable, it's likely just a correlation, not a cause.

It's a way to cut through the noise and find the "secret handshakes" that govern how things influence each other in our chaotic world.

Technical Summary

Here is a detailed technical summary of the paper "Dictionary Based Pattern Entropy for Causal Direction Discovery."

1. Problem Statement

The paper addresses the challenge of discovering causal directions from temporal observational data, specifically focusing on symbolic sequences (e.g., binary strings or discretized time series).

• Limitations of Existing Methods: Traditional causal discovery methods often rely on:
  • Functional Causal Models (FCMs): Require explicit assumptions about noise distributions (e.g., additive noise) or functional forms, which are often unavailable for symbolic data.
  • Graph-Based Methods: Rely on conditional independence, which can be difficult to estimate accurately in short or highly structured sequences.
  • Information-Theoretic Measures: Standard Shannon entropy or compression-based approaches (like Lempel-Ziv) often require large sample sizes for accurate probability estimation and may fail to capture specific mechanistic sub-patterns driving the causality.
• The Gap: There is a need for a framework that can infer causality without assuming explicit probabilistic models, handles noise robustly, and identifies the specific sub-patterns (algorithmic units) responsible for driving changes in the effect variable.

2. Methodology: Dictionary Based Pattern Entropy (DPE)

The proposed DPE framework integrates Algorithmic Information Theory (AIT) and Shannon Information Theory. It treats causation not merely as statistical correlation but as the emergence of compact, rule-based patterns in a candidate cause that systematically constrain the effect.

The methodology proceeds in seven distinct steps:

A. Dictionary Construction (Pattern Extraction)

1. Bit-Flip Detection: The algorithm scans the "effect" sequence ($Y$) to identify positions where a bit flip (state change) occurs ($y_k \neq y_{k-1}$).
2. Segment Extraction: For every bit flip in $Y$, the corresponding historical segment of the "cause" sequence ($X$) ending at that position is extracted.
3. Dictionary Formation: These segments form a directed dictionary ($G_{X \to Y}$). A symmetric process constructs $G_{Y \to X}$.

B. Pattern Refinement (XNOR Comparison)

To identify the specific recurring sub-patterns within the extracted segments that drive the change:

• The algorithm performs a sliding XNOR comparison between all pairs of segments in the dictionary.
• If two segments share a region of strong similarity (consecutive XNOR matches of '1'), these common subsequences are extracted.
• This creates a refined set of Causal Patterns ($P_{X \to Y}$) representing the latent mechanistic units.

C. Response Determinism ($R_{flip}$)

For each extracted pattern $p$, the framework calculates a Response Determinism metric:
$$R_{flip} = \frac{N_{flip}}{N_{occ}}$$

• $N_{occ}$: Total occurrences of pattern $p$ in the candidate cause sequence.
• $N_{flip}$: Number of times the pattern is followed by a bit flip in the effect sequence.
• Interpretation: $R_{flip} \approx 1$ implies a deterministic trigger; $R_{flip} \approx 0$ implies the pattern preserves the state; intermediate values indicate stochastic influence.

D. Weighted Entropy Calculation

The framework quantifies the uncertainty of the causal influence using Weighted Binary Entropy:

1. Binary Entropy ($H_b$): Calculated based on $R_{flip}$.
   $$H_b(r_p) = -[r_p \log_2 r_p + (1-r_p) \log_2 (1-r_p)]$$
2. Weight ($W_p$): Normalized frequency of the pattern in the sequence.
3. Weighted Entropy ($H_w$): $H_w(p) = W_p \times H_b(r_p)$.
4. Average Weighted Entropy ($\bar{H}$): The mean of $H_w$ across all patterns in the dictionary for a specific direction.

E. Causal Verdict

The causal direction is determined by the Minimum Uncertainty Criterion:

• If $\bar{H}_{X \to Y} < \bar{H}_{Y \to X}$, then $X \to Y$ is inferred as the causal direction.
• The logic is that the true causal direction exhibits more deterministic, rule-based patterns (lower entropy) compared to the reverse direction.

3. Key Contributions

1. Novel Framework: Introduction of DPE, which uniquely combines AIT (pattern extraction/dictionaries) with Shannon entropy (uncertainty quantification) for causal discovery.
2. Pattern-Level Attribution: Unlike black-box methods, DPE identifies specific sub-patterns (e.g., "1101") that drive changes, offering interpretability.
3. Robustness to Noise: By using $R_{flip}$ and weighted entropy, the method handles stochastic components in real-world data without requiring explicit noise models.
4. No Functional Assumptions: The method operates directly on symbolic sequences without assuming linearity, Gaussian noise, or specific functional forms.

4. Experimental Results

The authors evaluated DPE against competing AIT-based methods: ETCE, ETCP, and LZP (Lempel-Ziv Penalty).

Experiment Type	DPE Performance	Competitors (ETCE, ETCP, LZP)	Key Finding
Delayed Bit-Flip (Synthetic)	99% Accuracy	LZP (97.9%), ETCP (57%), ETCE (Fail)	DPE handles time delays and specific pattern triggers exceptionally well.
AR(1) Coupling (Linear)	>98% Accuracy (for $\phi > 0.2$)	LZP similar; ETCE/ETCP fail	DPE scales well with coupling strength in linear processes.
Sparse Processes	100% Accuracy	Competitors fail (predict independence)	DPE excels in sparse, event-driven data where global statistics fail.
1D Skew-Tent Maps (Non-linear)	90-100% Accuracy	LZP (62%), ETCP (49%), ETCE (22%)	DPE outperforms others in chaotic, non-linear systems, even at high coupling (synchronization).
SARS-CoV-2 Genomics	Mixed	ETCP/LZP showed advantages	In complex genomic data, pattern-based alternatives sometimes outperform DPE, though DPE remains competitive.
Predator-Prey (Real World)	Correct Direction	All models correct	DPE correctly identified the dominant direction (Predator $\to$ Prey) with lower entropy than the reverse.

Summary of Reliability: DPE was the only method to achieve $\ge 80\%$ reliability across all synthetic experiments tested.

5. Significance and Conclusion

• Interpretability: The ability to pinpoint which patterns cause which changes makes the causal inference explainable, a critical feature for scientific and biological applications.
• Bridging Theories: DPE successfully bridges the gap between the deterministic view of AIT (compression/complexity) and the probabilistic view of Shannon Information Theory.
• Applicability: The framework is particularly effective for systems where causality manifests through identifiable algorithmic sub-patterns rather than global statistical correlations.
• Limitations: The current method struggles to distinguish between very weak causal influence and true independence (false positives in independence regimes) and does not yet account for latent confounders. Future work aims to incorporate counterfactual analysis and surrogate data testing.

In conclusion, DPE offers a robust, interpretable, and broadly applicable framework for causal discovery in symbolic time series, outperforming existing compression-based methods in diverse synthetic and real-world scenarios.