<jupyter_start><jupyter_text>Pick data that hopefully isn't that seperable, subset it so we're doing linear classification<jupyter_code>chosenLabels = set([3,8])
label_dict = {3: -1, 8: 1}
X_train, Y_train = subsetData(mnist.train.images, 
                              mnist.train.labels,
                              chosenLabels, 
                              label_dict)

X_test, Y_test = subsetData(mnist.test.images, 
                            mnist.test.labels,
                            chosenLabels, 
                            label_dict)

X_train, Y_train, _ = shuffleArraysInUnison(X_train, Y_train)
X_test, Y_test, _ = shuffleArraysInUnison(X_test, Y_test)<jupyter_output><empty_output><jupyter_text>Train a couple of linear models<jupyter_code>models = [LinearSVC(C=5), 
          LinearSVC(loss='hinge', C=.1), 
          LinearSVC(loss='hinge', C=.01)]
X_test.shape
for i, model in enumerate(models):
    lb, ub = i * 1000, (i + 1) * 1000
    model.fit(X_train[lb: ub], Y_train[lb: ub])
    print "Model, Accuracy on Test Set"
    print i, model.score(X_test, Y_test)
    print 
# def subsetCorrect(num_pts, X, Y, models):
#     num_selected = 0
#     num_models = len(models)
#     resX = []
#     resY = []
#     for i in xrange(len(X)):
#         allCorrect = sum([model.score(X[i:i+1], Y[i:i+1]) for model in models]) == num_models
#         if allCorrect:
#             resX.append(X[i])
#             resY.append(Y[i])
#             num_selected += 1
#         if num_selected == num_pts:
#             break
#     if num_selected < num_pts:
#         print "Not enough points were correctly predicted by all models"
#     return np.array(resX), np.array(resY)
evalX, evalY = generate_data(300, X_test, Y_test, models)<jupyter_output><empty_output><jupyter_text>Select points that are correctly classified by all the models<jupyter_code>[model.score(evalX, evalY) for model in models]
def computeDistsToPlanes(models, X, Y):
    dists = []
    min_max = []
    num_models = len(models)
    num_points = len(X)
    norms = [np.linalg.norm(model.coef_) for model in models]
    for i in xrange(num_points):
        d = []
        for j in xrange(num_models):    
            # the reshaping happens so sklearn doesn't complain
            isCorrect = models[j].predict(X[i].reshape(1,-1))[0] == Y[i] 
            if isCorrect:
                d.append(abs((np.dot(models[j].coef_, X[i]) + models[j].intercept_)) / norms[j])
            else:
                d.append(np.nan)
        min_max.append((min(d), max(d)))
        dists.append(d)
    return np.array(dists).reshape(num_points, num_models), np.array(min_max).reshape(num_points, 2)
dists, min_max = computeDistsToPlanes(models, evalX, evalY)
print np.mean(dists, axis=0)<jupyter_output>[ 0.66828733  0.95834482  1.43564241]<jupyter_text>Evaluates the loss function in a particular region on $n$ dimensional space as determined by the signs list (what side of each hyperplane)<jupyter_code>def tryRegionBinary(models, signs, x, delta=1e-11):
    P = matrix(np.identity(x.shape[0]))
    q = matrix(np.zeros(x.shape[0]))
    h = []
    G = []
    num_models = len(models)
    for i in xrange(num_models):
        coef, intercept = models[i].coef_, models[i].intercept_
        ineq_val  = -1.0 * delta + signs[i] * (np.dot(coef, x) + intercept) 
        h.append(ineq_val[0])
        G.append(-1.0 * signs[i] * coef.reshape(-1,))   
    h = matrix(h)
    G = matrix(np.array(G))
    solvers.options['show_progress'] = False
    sol = solvers.qp(P, q, G, h)
    if sol['status'] == 'optimal':
        v = np.array(sol['x']).reshape(-1,)
        perturbed_x = np.array(x + v).reshape(1, -1)
        is_desired_sign = [models[i].predict(perturbed_x)[0] == signs[i] for i in xrange(num_models)]
        if sum(is_desired_sign) == num_models:
            return v
        else:
            return tryRegionBinary(models, signs, x, delta * 1.5)
    else:
        return None
test = 14
print evalY[test]
print dists[test]
# the labels that you specify for the region should match the labels predicted by the models
sol = tryRegionBinary(models, [-1, -1, -1], evalX[test])
print np.linalg.norm(sol)
for model in models:
    print model.predict(evalX[test].reshape(1,-1) + sol)[0]<jupyter_output>1.2663893147
-1
-1
-1<jupyter_text>Tries all $2^n$ possible regions of space to find the maximum value of the function while respecting the constraint that the noise vector $||v|| < \alpha $<jupyter_code>def findExampleBinary(weights, models, x, y, alpha):
    candidates = []
    
    # we should only take into consideration models that we could feasibly trickm
    dists, _ = computeDistsToPlanes(models, x.reshape(1, -1), y.reshape(1, -1))
    feasible_models = [models[i] for i in xrange(len(models)) if dists[0][i] < alpha]
    
    num_models = len(feasible_models)
    # can't trick anything
    if num_models == 0:
        return np.zeros(x.shape)
    
    rel_weights = np.array([weights[i] for i in xrange(len(models)) if dists[0][i] < alpha])
    
    signs_values = []
    for signs in product([-1.0, 1.0], repeat=num_models): # iterate over all possible regions
        is_misclassified = np.equal(-1.0 * y * np.ones(num_models), signs) # y = -1, or 1
        value = np.dot(is_misclassified, rel_weights)
        signs_values.append((signs, value))
    
    values = sorted(set([value for signs, value in signs_values]), reverse=True)
    for value in values:
        feasible_candidates = []
        for signs in [sign for sign, val in signs_values if val == value]:
            v = tryRegionBinary(feasible_models, signs, x)
            if v is not None:
                norm = np.linalg.norm(v)
                if norm <= alpha:
                    feasible_candidates.append((v, norm))
        # amongst those with the max value, return the one with the minimum norm
        if feasible_candidates:
            # break out of the loop since we have already found the optimal answer
            return min(feasible_candidates, key=lambda x: x[1])[0]<jupyter_output><empty_output><jupyter_text>Finds adversarial noise vectors for each data point<jupyter_code>v = findExampleBinary(np.array([0.2, 0.2, 0.6]), models, X_test[0], Y_test[0], 5)
print np.linalg.norm(v)
for model in models:
    print model.predict(X_test[0].reshape(1,-1) + v)[0]
def Oracle(weights, models, X, Y, alpha, findExample):
    return np.array([findExample(weights, models, x, y, alpha) for x, y in zip(X,Y)])<jupyter_output><empty_output><jupyter_text>Gets the costs of each model<jupyter_code>def evaluateCosts(models, V, X, Y):
    return np.array([1 - model.score(X + V, Y) for model in models])
def runMWU(models, T, X, Y, alpha, findExample, epsilon=None):
    
    num_models = len(models)
    
    if epsilon is None:
        delta = np.sqrt(4 * np.log(num_models) / float(T))
        epsilon = delta / 2.0
    else:
        delta = 2.0 * epsilon

    
    print "Running MWU for {} Iterations with Epsilon {}\n".format(T, epsilon)

    print "Guaranteed to be within {} of the minimax value \n".format(delta)
    
    loss_history = []
    costs = []
    max_acc_history = []
    v = []
    w = []
    
    w.append(np.ones(num_models) / num_models)

    for t in xrange(T):
        print "Iteration ", t
        print 
        start_time = time.time()
        
        v_t = Oracle(w[t], models, X, Y, alpha, findExample)
        v.append(v_t)
        
        cost_t = evaluateCosts(models, v_t, X, Y)
        costs.append(cost_t)
        
        print "Shape of costs matrix", np.array(costs).shape
        avg_acc = np.mean((1 - np.array(costs)), axis=0)  
        max_acc = max(avg_acc)
        max_acc_history.append(max_acc)
        
        loss = np.dot(w[t], cost_t)
    
        print "Weights, ", w[t], sum(w[t])
        print "Maximum (Average) Accuracy of Classifier ", max_acc
        print "Cost (Before Noise), ", np.array([1 - model.score(X, Y) for model in models])
        print "Cost (After Noise), ", cost_t
        print "Loss, ", loss
        
        loss_history.append(loss)
        
        new_w = np.copy(w[t])
        
        # penalize experts
        for i in xrange(num_models):
            new_w[i] *= (1.0 - epsilon) ** cost_t[i]
        
        # renormalize weights
        w_sum = new_w.sum()
        for i in xrange(num_models - 1):
            new_w[i] = new_w[i] / w_sum
        new_w[-1] = 1.0 - new_w[:-1].sum()
        
        w.append(new_w)
        
        print
        print "time spent ", time.time() - start_time
        print
        
    return w, v, loss_history, max_acc_history
dists, minmax = computeDistsToPlanes(models, evalX, evalY)
# confirm that these are all points that are correctly predicted by all the models
[model.score(evalX, evalY) for model in models]
minmax.shape
np.mean(dists, axis=0)
res = runMWU(models, 100, evalX, evalY, .95, findExampleBinary)
w, v, loss_history, max_acc_history = res
exp_dir = "binary_oracle2"
if not os.path.exists(exp_dir):
    os.mkdir(exp_dir)
w, v, loss_history, max_acc_history = np.array(w), np.array(v), np.array(loss_history), np.array(max_acc_history)
np.save(exp_dir+"/w.npy", w)
np.save(exp_dir+"/v.npy", v)
np.save(exp_dir+"/loss_history.npy", loss_history)
np.save(exp_dir+"/max_acc_history.npy", max_acc_history)
plt.title("Expected Loss of the Learner - Binary Classification")
plt.ylabel("Loss")
plt.xlabel("Rounds")
plt.plot(range(len(loss_history)), loss_history)
plt.title("Maximum Accuracy of Hypothesis - Binary Classication")
plt.ylabel("Accuracy")
plt.ylim((.75,.79))
plt.xlabel("Rounds")
plt.plot(range(len(max_acc_history)), max_acc_history)
def selectImage(i, evalX, v):
    images = []
    originalImage = evalX[i].reshape(28,28)
    images.append(originalImage)
    for j in xrange(len(v)):
        images.append(v[j][i].reshape(28,28) + originalImage)
    return images
images = selectImage(0, evalX, v)
i =20
plt.imshow(evalX[0].reshape(28,28) + v[i][0].reshape(28,28))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13066080175947214, 'fraction_numerical': 0.01759472158352494, 'mean_word_length': 2.8154080854309687, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '537177', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 3624, 'n_tokens_neox': 3466, 'n_words': 850, 'path': 'Binary Oracle.ipynb', 'repo_name': 'jcperdomo/universal_noise', 'size': '10003'}