File size: 3,792 Bytes
d14d984
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
"""Next Ask: pool-based active learning with a label budget.

Classifier: multinomial logistic regression trained by full-batch gradient descent
from zero weights (deterministic, mirrored exactly in web/core.js).
Strategies:
  random      - uniform sample from the unlabeled pool (Mulberry32 PRNG)
  uncertainty - smallest top-2 probability margin
  hybrid      - uncertainty + diversity: shortlist the 4*B most uncertain points, then
                greedily pick the point maximising (1 - margin) * distance to everything
                already labeled or picked (farthest-first on the shortlist)
"""
import numpy as np

from nlrt import Mulberry32

STRATEGIES = ("random", "uncertainty", "hybrid")


def features(pixels):
    x = np.asarray(pixels, dtype=np.float64) / 16.0
    return np.hstack([x, np.ones((x.shape[0], 1))])


def train(X, y, n_classes=10, steps=150, lr=0.5, l2=1e-3):
    n, d = X.shape
    W = np.zeros((d, n_classes))
    Y = np.zeros((n, n_classes))
    Y[np.arange(n), y] = 1.0
    reg = np.ones((d, 1))
    reg[-1] = 0.0
    for _ in range(steps):
        Z = X @ W
        Z -= Z.max(axis=1, keepdims=True)
        P = np.exp(Z)
        P /= P.sum(axis=1, keepdims=True)
        G = X.T @ (P - Y) / n + l2 * reg * W
        W -= lr * G
    return W


def proba(W, X):
    Z = X @ W
    Z -= Z.max(axis=1, keepdims=True)
    P = np.exp(Z)
    return P / P.sum(axis=1, keepdims=True)


def margins(P):
    s = np.sort(P, axis=1)
    return s[:, -1] - s[:, -2]


def select(strategy, W, X, labeled, B, seed):
    """Return B pool indices (ordered) to request labels for next."""
    labeled_set = set(int(i) for i in labeled)
    unl = [i for i in range(X.shape[0]) if i not in labeled_set]
    if strategy == "random":
        rng = Mulberry32(seed)
        arr = list(unl)
        picks = []
        for k in range(min(B, len(arr))):
            j = k + rng.randint(len(arr) - k)
            arr[k], arr[j] = arr[j], arr[k]
            picks.append(arr[k])
        return picks
    m = margins(proba(W, X[unl]))
    order = sorted(range(len(unl)), key=lambda k: (m[k], unl[k]))
    if strategy == "uncertainty":
        return [unl[k] for k in order[:B]]
    if strategy != "hybrid":
        raise ValueError(strategy)
    short = order[:4 * B]
    feats = X[:, :-1]
    anchors = feats[sorted(labeled_set)] if labeled_set else np.zeros((0, feats.shape[1]))
    cand = feats[[unl[k] for k in short]]
    if len(anchors):
        dmin = ((cand[:, None, :] - anchors[None, :, :]) ** 2).sum(-1).min(axis=1)
    else:
        dmin = np.full(len(short), np.inf)
    dmin = np.sqrt(dmin)
    picks, used = [], np.zeros(len(short), dtype=bool)
    for _ in range(min(B, len(short))):
        score = np.where(used, -np.inf, (1.0 - m[short]) * dmin)
        k = int(np.argmax(score))
        used[k] = True
        picks.append(unl[short[k]])
        dnew = np.sqrt(((cand - cand[k]) ** 2).sum(-1))
        dmin = np.minimum(dmin, dnew)
    return picks


def initial_set(n_pool, n_init, seed):
    rng = Mulberry32(seed * 7919 + 1)
    arr = list(range(n_pool))
    for k in range(n_init):
        j = k + rng.randint(n_pool - k)
        arr[k], arr[j] = arr[j], arr[k]
    return arr[:n_init]


def simulate(strategy, Xp, yp, Xt, yt, seed, hyper, n_init=10, B=10, budget=200):
    labeled = initial_set(len(Xp), n_init, seed)
    curve = []
    W = None
    rnd = 0
    while True:
        W = train(Xp[labeled], yp[labeled], **hyper)
        acc = float((proba(W, Xt).argmax(1) == yt).mean())
        curve.append((len(labeled), acc))
        if len(labeled) >= budget:
            break
        picks = select(strategy, W, Xp, labeled, min(B, budget - len(labeled)), seed * 100003 + rnd)
        labeled = labeled + picks
        rnd += 1
    return curve, labeled, W