Metadata-Version: 2.4
Name: trosna-kalman
Version: 0.0.1
Summary: Adaptive Kalman filter that chooses when to poll next: uncertainty-driven monitoring intervals for virtual machine memory, with scalar, matrix and level-trend Kalman filters
Keywords: kalman-filter,adaptive-kalman-filter,state-estimation,adaptive-sampling,monitoring,polling-interval,time-series,virtualization,kvm,memory-ballooning
Author: Andrey Ferubko, Oleg Kazakov
Author-email: Andrey Ferubko <ferubko1999@yandex.ru>, Oleg Kazakov <kazakov@bgitu.ru>
License-Expression: MIT
License-File: LICENSE
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: System Administrators
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: System :: Monitoring
Classifier: Typing :: Typed
Requires-Dist: numpy>=1.26
Requires-Dist: scikit-learn>=1.6 ; extra == 'sklearn'
Requires-Python: >=3.11
Project-URL: Homepage, https://github.com/89605502155/trosna-kalman
Project-URL: Documentation, https://github.com/89605502155/trosna-kalman/tree/main/docs
Project-URL: Repository, https://github.com/89605502155/trosna-kalman
Project-URL: Issues, https://github.com/89605502155/trosna-kalman/issues
Project-URL: Changelog, https://github.com/89605502155/trosna-kalman/blob/main/CHANGELOG.md
Provides-Extra: sklearn
Description-Content-Type: text/markdown

# trosna-kalman

[![PyPI](https://img.shields.io/pypi/v/trosna-kalman.svg)](https://pypi.org/project/trosna-kalman/)
[![Python](https://img.shields.io/pypi/pyversions/trosna-kalman.svg)](https://pypi.org/project/trosna-kalman/)
[![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](https://github.com/89605502155/trosna-kalman/blob/main/LICENSE)

**An adaptive Kalman filter that decides when to measure next.**

trosna-kalman estimates a value seen only through noisy measurements, for
example the memory use of a virtual machine, and tells you when to measure
it again: when the uncertainty of the estimate reaches the error you accept.
The filter learns how fast the value changes from its own innovations. Calm
periods are polled rarely and bursts often, and every estimate comes with its
standard deviation.

[Русская версия](https://github.com/89605502155/trosna-kalman/blob/main/README.ru.md) ·
[Guide](https://github.com/89605502155/trosna-kalman/blob/main/docs/guide.md) ·
[Method](https://github.com/89605502155/trosna-kalman/blob/main/docs/method.md) ·
[API reference](https://github.com/89605502155/trosna-kalman/blob/main/docs/api.md) ·
[Examples](https://github.com/89605502155/trosna-kalman/tree/main/examples) ·
[Changelog](https://github.com/89605502155/trosna-kalman/blob/main/CHANGELOG.md)

The library implements the method of A. O. Ferubko and O. D. Kazakov for the
adaptive memory management system of the KVM hypervisor, the classical
filters it is built on, and the tools to evaluate it:

* **`AdaptiveKalmanMonitor`**, the method: a one-dimensional Kalman filter
  that adapts the intensity of changes `q` by its innovations and chooses the
  next polling interval from the uncertainty of the estimate. It reproduces
  the reference implementation of the paper bit for bit.
* **`RandomWalkKalmanFilter`**, **`KalmanFilter`**, **`LevelTrendKalmanFilter`**:
  the scalar filter for irregular sampling, the general matrix filter
  (Joseph form, missing values, log-likelihood) and the "level plus growth
  rate" model with forecasts and the "forecast plus 2σ" allocation. All of
  them have an optional maximum-correntropy (MCC) update for heavy-tailed
  noise.
* **Baselines**: the original interval heuristic of the system
  (0 → 10 s … 5 redistributions in the last five cycles → 1 s) and polling
  at a fixed interval.
* **`RebalancingTrigger`**: decisions on memory redistribution by filter
  estimates instead of raw measurements, so a single outlier does not start
  a costly redistribution cycle.
* **Noise estimation**: `R` from calm segments of logs; `q` and `R` by
  maximum likelihood (the Kalman filter likelihood) or the method of moments.
* **`trosna_kalman.simulation`**: the model experiment of the paper (load
  scenarios, simulated polling, Monte Carlo, parameter sweeps).
* **`run_monitoring`** and **`trosna_kalman.kvm`**: the polling loop of a
  monitoring service and `virsh dommemstat`.
* **`trosna_kalman.sklearn.KalmanDenoiser`**: causal Kalman filtering as a
  scikit-learn transformer.

## Installation

```sh
pip install trosna-kalman              # NumPy only
pip install "trosna-kalman[sklearn]"   # + scikit-learn transformer

uv add trosna-kalman                   # with uv
```

Python 3.11–3.14 is supported.

## Quick start

```python
from trosna_kalman import AdaptiveKalmanMonitor

# Memory in GB: measurement noise 80 MB, admissible error of the estimate 150 MB.
monitor = AdaptiveKalmanMonitor(z0=2.0, r=0.08**2, eps=0.15, interval_step=1.0)

t = 0.0
for z in [2.03, 1.97, 2.02, 2.95, 3.01, 2.98, 3.02]:
    dt = monitor.interval  # wait this long, then measure z
    t += dt
    x, sigma, dt_next = monitor.update(z, dt)
    print(
        f"t={t:4.0f} s  z={z:.2f}  estimate={x:.3f} ± {sigma:.3f} GB  next poll in {dt_next:.0f} s"
    )
```

```text
t=   1 s  z=2.03  estimate=2.017 ± 0.059 GB  next poll in 10 s
t=  11 s  z=1.97  estimate=1.982 ± 0.069 GB  next poll in 10 s
t=  21 s  z=2.02  estimate=2.011 ± 0.070 GB  next poll in 10 s
t=  31 s  z=2.95  estimate=2.929 ± 0.079 GB  next poll in 1 s
t=  32 s  z=3.01  estimate=2.993 ± 0.071 GB  next poll in 1 s
t=  33 s  z=2.98  estimate=2.984 ± 0.066 GB  next poll in 2 s
t=  35 s  z=3.02  estimate=3.009 ± 0.066 GB  next poll in 4 s
```

While the memory use is steady the monitor polls every 10 s. A jump of
almost 1 GB raises the estimated intensity of changes, the filter accepts the
new level at once and polls every second until it is sure of the new level.

## How it works

The memory use follows a random walk: over `Δt` seconds its variance grows by
`q·Δt`. Each poll goes through the stages of the flow chart of the paper:

```text
stage 3   ν = z − x̂                                             innovation
stage 4   q̂ ← clip((1 − β)·q̂ + β·(ν² − P − R)/Δt, q_min, q_max)   (6)
stage 5   P⁻ = P + q̂·Δt                                         (1)
          K = P⁻/(P⁻ + R),  x̂ ← x̂ + K·ν,  P = (1 − K)·P⁻         (2)–(4)
stage 6   x̂ and σ = √P go to the redistribution block
stage 7   Δt = clip((ε² − P)/q̂, Δt_min, Δt_max)                 (5)
```

Under the model `E[ν²] = P + q·Δt + R`, so every innovation gives an
instantaneous estimate of `q` (6); a surprise makes `q̂` grow before the
prediction, so `P⁻` and the gain `K` grow at once. The next poll is due when
the variance `P + q̂·Δt` reaches `ε²` (5). See
[docs/method.md](https://github.com/89605502155/trosna-kalman/blob/main/docs/method.md)
for the derivation, the parameters and the limitations.

## The model experiment of the paper

```python
from trosna_kalman.simulation import adaptive_factory, evaluate, make_scenarios, paper_config

scenarios = make_scenarios(50, seed=0)  # 300 s each: a load starts, grows and ends
for eps in (0.10, 0.15):
    result = evaluate(adaptive_factory(paper_config(eps)), scenarios)
    print(
        f"ε = {eps * 1000:.0f} MB: {result.mean_polls:.1f} polls, MAE {result.mean_mae * 1000:.1f} MB"
    )
every_second = evaluate(adaptive_factory(paper_config(0.1, dt_max=1.0)), scenarios)
print(
    f"every second: {every_second.mean_polls:.0f} polls, MAE {every_second.mean_mae * 1000:.1f} MB"
)
```

```text
ε = 100 MB: 97.8 polls, MAE 52.0 MB
ε = 150 MB: 43.4 polls, MAE 79.1 MB
every second: 300 polls, MAE 40.6 MB
```

The paper reports 97 polls and 51 MB, 44 polls and 76 MB, and 41 MB for the
same experiment.

## Polling a virtual machine

```py
from trosna_kalman import MonitorConfig, run_monitoring
from trosna_kalman.kvm import make_reader

read = make_reader("vm1", uri="qemu:///system")  # GiB used in the guest, via virsh dommemstat


def decide_rebalancing(
    x: float, sigma: float
) -> None: ...  # the redistribution block of your system


run_monitoring(
    read, decide_rebalancing, config=MonitorConfig(r=0.08**2, eps=0.15, interval_step=1.0)
)
```

`run_monitoring` passes the time that actually elapsed between measurements
to the filter and stops on a `threading.Event`.

## Classical filters, forecasts and decisions

```python
import numpy as np
from trosna_kalman import LevelTrendKalmanFilter, RandomWalkKalmanFilter, count_rebalancings

# Section 2 of the paper: the forecast 2.0 ± 0.1 GB meets the measurement 2.6 GB ± 0.3 GB.
kf = RandomWalkKalmanFilter(x0=2.0, p0=0.1**2, q=0.0, r=0.3**2)
print(round(kf.update(2.6).gain, 3), round(kf.x, 3), round(kf.std, 3))  # 0.1 2.06 0.095

# "Level plus growth rate": forecast 30 s ahead and the allocation "forecast + 2σ".
rng = np.random.default_rng(0)
lt = LevelTrendKalmanFilter(2.0, r=0.08**2, q_trend=1e-7)
for t in range(1, 61):
    lt.step(2.0 + 0.004 * t + rng.normal(0.0, 0.08), dt=1.0)
forecast = lt.forecast(30.0)
print(f"{forecast.mean:.2f} ± {forecast.std:.2f} GB, allocate {lt.upper_bound(30.0):.2f} GB")

# Redistribution decisions by the estimate instead of the raw measurement.
noisy = 2.0 + rng.normal(0.0, 0.08, 300)
smooth, _ = RandomWalkKalmanFilter(noisy[0], 0.0064, 1e-5, 0.0064).filter(noisy)
print(count_rebalancings(noisy, window=0.15), "cycles vs", count_rebalancings(smooth, window=0.15))
```

## scikit-learn

```python
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.pipeline import make_pipeline
from trosna_kalman.sklearn import KalmanDenoiser

rng = np.random.default_rng(1)
level = 2.0 + np.cumsum(rng.normal(0.0, 0.01, 500))
X = (level + rng.normal(0.0, 0.08, level.size)).reshape(-1, 1)  # rows are moments of time

model = make_pipeline(KalmanDenoiser(), LinearRegression())
model.fit(X[:-1], level[1:])  # denoise, then forecast the next level
print(model.predict(X)[-1])  # pass the whole history: each transform starts from row 0
```

`KalmanDenoiser` estimates the noise of every column in `fit` (`R` robustly,
`q` by maximum likelihood) and filters the columns causally in `transform`,
so it does not look into the future inside a pipeline or cross-validation.
Every `transform` call filters its rows from the first one, without state
from earlier calls; pass the whole history and take the last rows.
`adaptive=True` adapts `q` by formula (6); it pays off when the intensity of
changes differs by orders of magnitude between long regimes.

## Documentation

* [Guide](https://github.com/89605502155/trosna-kalman/blob/main/docs/guide.md): every feature with examples.
* [Method](https://github.com/89605502155/trosna-kalman/blob/main/docs/method.md): the formulas, their derivation, the experiment, the limitations and the literature.
* [API reference](https://github.com/89605502155/trosna-kalman/blob/main/docs/api.md).
* [Examples](https://github.com/89605502155/trosna-kalman/tree/main/examples): runnable scripts.
* [Publishing](https://github.com/89605502155/trosna-kalman/blob/main/docs/publishing.md): releasing to PyPI.

Every document is available in Russian as well.

## Development

```sh
uv sync                      # Python 3.14 by default; any of 3.11–3.14 works
uv run ruff check .
uv run ruff format --check .
uv run mypy
uv run pytest                # with coverage: uv run pytest --cov
```

## Citing

Use the "Cite this repository" button on GitHub
([CITATION.cff](https://github.com/89605502155/trosna-kalman/blob/main/CITATION.cff)) or:

```bibtex
@software{trosna_kalman,
  author  = {Ferubko, Andrey O. and Kazakov, Oleg D.},
  title   = {trosna-kalman: adaptive Kalman filter with uncertainty-driven monitoring intervals},
  year    = {2026},
  version = {0.0.1},
  url     = {https://github.com/89605502155/trosna-kalman},
  license = {MIT}
}
```

## Authors

* Andrey O. Ferubko (А. О. Ферубко), [ORCID 0009-0006-5625-137X](https://orcid.org/0009-0006-5625-137X)
* Oleg D. Kazakov (О. Д. Казаков), scientific advisor, [ORCID 0000-0001-9665-8138](https://orcid.org/0000-0001-9665-8138)

Bryansk State Technological University of Engineering (BGITU), Bryansk,
Russia — ФГБОУ ВО «Брянский государственный инженерно-технологический
университет».

## License

MIT, see [LICENSE](https://github.com/89605502155/trosna-kalman/blob/main/LICENSE).
