Metadata-Version: 2.4
Name: qubo-wisard
Version: 0.1.1
Summary: QUBO-based structural compression and RAM-node selection for WiSARD classifiers
Author: Natasha Costa Fonseca
License-Expression: MIT
Project-URL: Repository, https://github.com/AstroNatasha/QUBO-WiSARD
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Requires-Dist: dwave-neal>=0.6
Provides-Extra: tabular
Requires-Dist: scikit-learn>=1.3; extra == "tabular"
Requires-Dist: scipy>=1.10; extra == "tabular"
Provides-Extra: progress
Requires-Dist: tqdm>=4.65; extra == "progress"
Provides-Extra: quantum
Requires-Dist: openjij; extra == "quantum"
Provides-Extra: dev
Requires-Dist: pytest>=7.4; extra == "dev"
Requires-Dist: jupyter>=1.0; extra == "dev"
Requires-Dist: ipykernel>=6.0; extra == "dev"
Dynamic: license-file

# QUBO-WiSARD

QUBO-WiSARD is a research-oriented Python package for QUBO-based structural compression and RAM-node selection in WiSARD classifiers, a class of Weightless Neural Networks. This repository is also the reproduction package for the manuscript **"Structural Compression of Weightless Neural Networks: A QUBO
Formulation and Its Operating Range"** (in [`paper_neurocomputing/`](paper_neurocomputing/)):
the reusable package lives under `src/qubo_wisard/`, and everything needed to reproduce the paper's experiments, results and manuscript lives alongside it.

## Research status

| Status | Component |
|---|---|
| Implemented, experimentally validated (30 seeds, 8 tabular datasets) | `WiSARD`, thermometer encoding, the QUBO RAM-selection formulation, `SimulatedAnnealingSolver`, sparse inference, random baseline |
| Implemented, not experimentally validated in this environment | `OpenJijSASolver`, `OpenJijSQASolver` (the `openjij` dependency is not installed or tested here) |
| Experimental research prototype, not a package solver backend | The QAOA proof of concept in [`experiments/qaoa_poc/`](experiments/qaoa_poc/): maps the same QUBO to an Ising/QAOA problem for research purposes, separate from `QUBOSelector` |
| Stub, not implemented | `QiskitSamplerSolver`, which raises `NotImplementedError` |
| Out of scope for this package | The bit-to-RAM-assignment course project (flat modules under `src/`; see [Repository structure](#repository-structure)): a different problem, kept in this repository for research continuity |

No quantum advantage is claimed, measured, or implied anywhere in this repository.

## Installation

QUBO-WiSARD is available on PyPI:

```bash
pip install qubo-wisard
```


## Quick start

```python
from qubo_wisard import WiSARD, QUBOSelector

# X_train, y_train, X_val, y_val, X_test: pre-binarized uint8 arrays.
model = WiSARD(input_size=64, address_size=8, seed=1, response="binary", bleach=1)
model.fit(X_train, y_train)

selector = QUBOSelector(alpha=3.0, beta=0.2, lam=1.5, k_ratio=0.6, solver="neal")
selector.fit(model, X_val, y_val)

preds = selector.predict(model, X_test)
```

A complete, runnable example on synthetic data (no download) is at
[`examples/basic_usage.py`](examples/basic_usage.py).

## Method overview

A trained WiSARD classifier is a collection of interchangeable RAM nodes. This work
formulates the choice of *which nodes to keep* as a Quadratic Unconstrained Binary
Optimization problem, solved once per class discriminator after training. The classifier
is never retrained and the stored memories are never modified: the optimizer produces only
a binary mask applied at inference. The uncompressed model is therefore an upper reference
rather than a competitor, and the decisive comparison is against random selection at the
same budget, which isolates the quality of the selection from the effect of shrinking the
model.

## QUBO formulation

The objective implemented in `qubo_wisard.qubo`, solved independently per class $c$:

```math
E_c(w_c)=
-\alpha \sum_{r=1}^{R}\tilde{U}_{c,r}w_{c,r}
+\beta \sum_{r<s}\rho_{r,s}w_{c,r}w_{c,s}
+\lambda\left(\sum_{r=1}^{R}w_{c,r}-k\right)^2
```

which expands (using $w_r^2=w_r$ for binary variables) to the QUBO coefficients built by
`build_qubo_matrix`:

```text
Q[r,r] = -alpha * U_tilde[r]  +  lambda * (1 - 2k)
Q[r,s] = beta  * rho[r,s]      +  2 * lambda            (r < s)
```

- $\tilde{U}_{c,r}$: discriminative utility of RAM $r$ for class $c$
  (`compute_margin_utility`). The difference between the RAM's mean activation on samples
  of class $c$ and on samples of every other class, normalized to $[0, 1]$ per class.
- $\rho_{r,s}$: redundancy between RAM $r$ and RAM $s$ (`compute_redundancy_matrix`), the
  **absolute Pearson correlation of their activation profiles, averaged across classes**.
  This is the metric currently implemented, not a placeholder for an arbitrary interaction
  term; a different redundancy metric would need its own function.
- $k=\lfloor \kappa R\rfloor$: the retention budget, `k_ratio` in `QUBOSelector`.

Setting $\beta = 0$ collapses the problem to a ranking by utility alone, so the quadratic
term is what the formulation has to justify; `experiments/beta_sweep/` and
`experiments/redundancy_check/` test exactly this.

## Structural-selection pipeline

`QUBOSelector.fit` composes the following, in order, keeping every intermediate result on
the instance rather than discarding it:

```text
build_activation_tensor -> compute_margin_utility -> compute_redundancy_matrix
      -> build_qubo_for_all_classes -> QUBOSolver.solve (one call per class)
```

`QUBOSelector.predict` then calls `predict_sparse`, which looks up only the RAMs selected
for each class.

## Public API

```python
from qubo_wisard import WiSARD, QUBOSelector
```

Lower-level functions remain directly importable and are what the two classes above
compose:

```python
from qubo_wisard.encoding import fit_thresholds, apply_thresholds, load_tabular_splits
from qubo_wisard.activation import build_activation_tensor
from qubo_wisard.utility import compute_margin_utility
from qubo_wisard.redundancy import compute_redundancy_matrix
from qubo_wisard.qubo import build_qubo_matrix, build_qubo_for_all_classes
from qubo_wisard.solver import SimulatedAnnealingSolver, QUBOSolver
from qubo_wisard.inference import predict_sparse, random_baseline_weights
```

After `fit`, `QUBOSelector` exposes its intermediate quantities rather than hiding them:
`utility_`, `redundancy_`, `qubo_matrices_`, `weights_`, `energies_`, `k_`, `solve_time_s_`.

## Solvers

| Solver | Status |
|---|---|
| `SimulatedAnnealingSolver` (`dwave-neal`) | Working, verified; used for every reported result |
| `OpenJijSASolver`, `OpenJijSQASolver` | Implemented against the same `QUBOSolver` interface; `openjij` is an optional dependency (`pip install qubo-wisard[quantum]`), not installed or tested in this environment |
| `QiskitSamplerSolver` | Stub; calling `.solve()` raises `NotImplementedError` |

`QUBOSelector(solver=...)` accepts `"neal"`, `"openjij_sa"`, `"openjij_sqa"`, `"qiskit"`, or
a `QUBOSolver` instance directly.

The QAOA proof of concept in [`experiments/qaoa_poc/`](experiments/qaoa_poc/) maps the same
QUBO to an Ising Hamiltonian and runs a statevector QAOA emulation for research purposes.
It is experiment code, not a `QUBOSolver` backend: it is not installed by the package and
should not be read as supported QAOA solver support.

## Encoding

`qubo_wisard.encoding` implements thermometer encoding for tabular features: `uniform`,
`quantile`, and `gaussian` threshold placement, all emitting exactly `T` bits per feature
so comparisons across methods are cost-controlled. Thresholds are always fit on the
training split only, then applied unchanged to validation/test. `load_tabular_splits`
additionally fetches an OpenML dataset and applies the stratified split used by the
tabular experiments (requires the `tabular` extra: `scikit-learn`, `scipy` for the
gaussian method).

## Headline results

Over 30 seeds per configuration, paired Wilcoxon signed-rank:

| | |
|---|---|
| Significant wins over random selection | 22 of 27 (encoding, dataset, $\kappa$) cells |
| Advantage at $\kappa = 0.2$ (Letter Recognition) | $+0.1427$ |
| Advantage at $\kappa = 0.6$ / $0.8$ / $0.9$ (mean) | $+0.0168$ / $+0.0084$ / $+0.0021$ |
| Memory retained at $\kappa = 0.6$ | $54.8\%$–$56.0\%$ |
| Inference speedup | up to $1.99\times$ |
| Solver optimality at $R=16$ | exact optimum in 140 of 140 cells (exhaustive enumeration) |

The advantage grows monotonically as compression tightens; see [Limitations](#limitations)
for where it does not hold.

## Experiments and reproducibility

**Environment.** The reported numbers were produced under Python 3.14.4 on Ubuntu 26.04,
16 CPU cores, no GPU:

```bash
python3.14 -m venv .venv
.venv/bin/python -m pip install -r requirements-lock.txt
.venv/bin/python -m pip install -e .
```

Use `requirements-lock.txt`, not `requirements.txt`: the latter carries loose lower bounds
and will resolve to different versions than the ones the results depend on.

The editable install (`pip install -e .`) makes `import qubo_wisard` work from any working
directory; it is required by newly written or migrated experiment scripts. Older scripts
still add `src/` to `sys.path` directly and work without it, but the underlying
implementation is the same package either way, imported either as `qubo_wisard` (current
name) or `qubo_wizard` (a compatibility alias kept only for those older research scripts;
see [Research status](#research-status) and `src/qubo_wizard/__init__.py`. It is not a
second supported public API: new code should always use `qubo_wisard`).

**Data.** Nothing is versioned here. The tabular datasets are fetched from OpenML with
pinned versions and the image datasets through `torchvision`, both automatically on first
run. See [`analysis/DATA_SETUP.md`](analysis/DATA_SETUP.md).

**Experiments.** Each directory under `experiments/` is self-contained: a `run_*.py` that
produces `*_detailed.csv`, and where applicable an `analyze_*.py` that produces the
statistical tables. The entry points behind the main claims:

| claim | entry point |
|---|---|
| Main tabular results, 30 seeds, encoding ablation | `experiments/tabular_encoding_ablation_T20_a20_seeds30/run_ablation.py` then `analyze_ablation.py` |
| Sweep to $\kappa = 0.2$ and solver-optimality check | `experiments/aggressive_kappa/run_aggressive.py` |
| Pairwise term vs. greedy top-$k$ | `experiments/redundancy_check/run_redundancy_check.py` |
| Redundancy-weight sensitivity and leakage-free calibration | `experiments/beta_sweep/run_beta_sweep.py`, `run_beta_calibrated.py` |
| Memory, latency and optimization cost | `experiments/cost_metrics/run_cost_metrics.py` |
| Transfer to random forest pruning | `experiments/generalization_rf/run_rf_pruning.py` |
| Reference context against MLP and random forest | `experiments/reference_context/run_reference_models.py` |

Runs are deterministic given the seed: `dwave-neal` receives an explicit seed and the data
split is fixed by `random_state=42` independently of the model seed.

Appendix C of the manuscript is the authoritative checklist: it records the splits, the
objective coefficients ($\alpha = 3.0$, $\beta = 0.2$, $\lambda = 1.5$), the solver budget
(500 reads, 2000 sweeps), the software versions, and the caveats.

**Building the manuscript.** See [`paper_neurocomputing/README.md`](paper_neurocomputing/README.md).

**Package tests.** `pytest tests/` runs the package unit tests (fast, deterministic, no
network access, no dataset downloads); this is a check on the software, distinct from the
`experiments/` scripts that reproduce the paper's numbers.

## Repository structure

```text
.
├── src/qubo_wisard/        the reusable package: encoding, WiSARD, QUBO construction,
│                           solvers, and QUBOSelector (see qubo_wisard/__init__.py)
├── src/qubo_wizard/        compatibility alias kept for older research scripts;
│                           re-exports qubo_wisard, holds no implementation of its own
├── src/*.py (flat)         a separate course project on bit-to-RAM assignment
│                           (see README_course.md); a different problem from RAM
│                           selection, not part of the qubo_wisard package and not
│                           built into the PyPI distribution
├── experiments/            one directory per experiment: runner, results, figures
├── analysis/               shared statistical machinery and dataset setup
├── configs/                default.yaml is an older EMNIST-protocol configuration
│                           used only by the legacy exp0X_*.py scripts; the tabular
│                           protocol backing the manuscript sets its parameters
│                           directly in each experiment script, not from this file
├── paper_neurocomputing/   the manuscript (Elsevier CAS)
├── tests/                  package unit tests (pytest)
├── examples/                minimal usage examples
├── requirements-lock.txt   exact resolved environment (reproduces the numbers)
├── requirements.txt        loose bounds (development)
├── pyproject.toml
├── CITATION.cff
└── LICENSE
```

The flat course-project modules and the `qubo_wizard` alias remain in this repository, on
this branch and on `main`, for research continuity. Earlier manuscript drafts, superseded
result sets and presentation material are kept out of `main` and preserved on the
`archive/pre-submission` branch instead.

## Limitations

- The advantage over random selection is not established for mild compression: at
  $\kappa=0.9$, four of nine cells are indistinguishable from random selection, and one is
  significantly worse. The method targets aggressive compression.
- The contribution is RAM-node reduction under a fixed accuracy budget, not an accuracy
  gain; see the manuscript for the accuracy-per-byte framing.
- A memory-aware knapsack constraint, input-bit selection, and transfer to random-forest
  pruning were tested and did not outperform simpler baselines. These negative results are
  reported in the manuscript and are not pursued further in this package.
- `OpenJijSASolver` and `OpenJijSQASolver` are implemented but not verified in this
  environment; `QiskitSamplerSolver` is a stub.
- `rho` (redundancy) is the absolute Pearson correlation of activation profiles, averaged
  across classes. This is the metric the formulation was validated with; it is not
  generalized to an arbitrary interaction metric.

## Citation

This software can currently be cited using the metadata in
[`CITATION.cff`](CITATION.cff) (GitHub renders a "Cite this repository" option from it
automatically). The associated manuscript is not yet published; once it is, the citation
metadata will be updated with the venue and DOI.

## License

MIT. See [`LICENSE`](LICENSE).

## Authors

Natasha Costa Fonseca (software; see [`CITATION.cff`](CITATION.cff)). 
