Metadata-Version: 2.1
Name: hlucb
Version: 0.1.2
Summary: Hamming-LUCB algorithm implementation
Home-page: https://github.com/gregorybchris/hlucb
License: Apache Software License
Keywords: hlucb,hamming,lucb,approximate,ranking,pairwise,comparisons
Author: Chris Gregory
Author-email: christopher.b.gregory@gmail.com
Requires-Python: >=3.8,<3.10
Classifier: Development Status :: 4 - Beta
Classifier: License :: Other/Proprietary License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Requires-Dist: numpy (>=1.21.5,<2.0.0)
Project-URL: Repository, https://github.com/gregorybchris/hlucb
Description-Content-Type: text/markdown

# Hamming-LUCB

The `hlucb` package is a Python implementation of the paper [Approximate ranking from pairwise comparisons](http://proceedings.mlr.press/v84/heckel18a.html).

> Heckel, R., Simchowitz, M., Ramchandran, K., & Wainwright, M. (2018, March). Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics (pp. 1057-1066). PMLR.

## Installation

`hlucb` is installable with pip:

```bash
$ pip install hlucb
```

## Usage

### Ranking with a comparator

```python
from hlucb import HammingLUCB

items = [4, 1, 2, 6, 5, 8, 9, 3]
k = 5
h = 2
delta = 0.9

def compare(item_a: int, item_b: int) -> bool:
    return item_a > item_b

scores, bounds = HammingLUCB.from_comparator(items, k, h, delta, compare, seed=42)

print("Scores: ", scores)
print("Bounds: ", bounds)
```

### Ranking with a generator

```python
from hlucb import HammingLUCB

items = [4, 1, 2, 6, 5, 8, 9, 3]
n = len(items)
k = 5
h = 2
delta = 0.9

generator = HammingLUCB.get_generator(n, k, h, delta, seed=42)
scores = None
bounds = None
for (i, j), (scores, bounds) in generator:
    comparison = items[i] > items[j]
    generator.send(comparison)

print("Scores: ", scores)
print("Bounds: ", bounds)
```

## Intuition

The Hamming-LUCB algorithm approximately ranks $n$ items, estimates the score of each item, and provides confidence bounds for each score. The intuition behind the approximate ranking is that it's easier to compare items with very different scores, so it should be possible to separate high-scoring items from low-scoring items with few comparisons and high confidence even if the exact ranking is not discovered.

The sets of high- and low-scoring items are designated $S_1$ and $S_2$ respectively. Hamming-LUCB extracts $S_1$ and $S_2$ such that all items in $S_1$ are expected to have higher scores than all items in $S_2$.

Parameters:

- $n$ - the total number of items
- $k$ - the number of items to extract as high-scoring items
- $h$ - the number of ranking mistakes permitted
- $\delta$ - confidence parameter for the probability of achieving $h$-Hamming accuracy

Definitions:

- The Hamming distance between two sets: $D_H(S_1, S_2) = \lvert (S_1 \cup S_2) \setminus (S_1 \cap S_2) \rvert$
- A ranking $\hat{S_1}$, $\hat{S_2}$ is $h$-Hamming accurate if: $D_H(\hat{S_l}, S_l) \leq 2h$ for
  - $\lvert \hat{S_l} \rvert = \lvert S_l \rvert$
  - $l \in \{1, 2\}$
- A ranking algorithm is $(h, \delta)$-accurate if the ranking returned is $h$-Hamming accurate with probability at least $1 - \delta$.

