Lempel Ziv Complexity And Sensitivity

lempel-ziv-complexity-and-sensitivity

Assessing Simplification Levels in Neural Networks: The Impact of Hyperparameter Configurations on Complexity and Sensitivity — Guan (2024) (arXiv:2409.16086, 2024)

What this evaluates

Evaluates how neural network hyperparameters (activation functions, depth, learning rate) affect output complexity and robustness to input perturbations.

Datasets

• MNIST — total ?; splits: unspecified (-1); HF mnist

Metrics

• Lempel-Ziv Complexity (primary) — range: other
  • Calculated by compressing the network's output sequence using the zlib library and measuring the compressed length.
• Input Perturbation Sensitivity — range: other
  • Calculated as the L2 norm of the difference between network outputs before and after applying a small input perturbation (epsilon = 1e-5).

Input / output format

Input: 28x28 grayscale images standardized to mean 0.5 and std 0.5.

Output: Network output sequence (raw values) used for compression and L2 norm calculation.

Scoring recipe

output_seq = model(input_img)
compressed = zlib.compress(output_seq)
complexity = len(compressed)

perturbed = input_img + np.random.uniform(-1e-5, 1e-5, size=input_img.shape)
out_orig = model(input_img)
out_pert = model(perturbed)
sensitivity = np.linalg.norm(out_orig - out_pert)

Common pitfalls

• zlib compressed length is an approximation of true algorithmic Lempel-Ziv complexity and may not scale linearly with actual information content.
• L2 norm sensitivity scores are highly dependent on the perturbation magnitude (epsilon) and output scaling, making cross-experiment comparisons sensitive to normalization choices.
• Standardizing inputs to mean 0.5/std 0.5 before perturbation can interact with activation function ranges (e.g., Sigmoid vs ReLU), affecting baseline output magnitudes.

Evidence (verbatim from paper)

The network complexity and sensitivity were evaluated using the following steps: 1. Lempel-Ziv Complexity: We calculated the network’s output complexity by compressing the output sequence using the zlib library and measuring the compressed length. 2. Sensitivity: We applied small perturbations to the input images (epsilon = 1×10−5) and calculated the difference in network outputs before and after the perturbation using the L2 norm.

Citation

@misc{guan2024assessing,
  title={Assessing Simplification Levels in Neural Networks: The Impact of Hyperparameter Configurations on Complexity and Sensitivity},
  author={Guan (2024)},
  year={2024},
  note={arXiv:2409.16086}
}

• arXiv: 2409.16086