gistfile1.py

def hit_and_run(X, Y, N=100, T=10, sub_sample_size=100, eps=0.5):
    """
    @param N hypothesis of points wanted
    @param T number of mixing iterations
    @param sub_sample_size how many samples of hypothesis take on the ray.
    @param eps noise level. Note that i should be pretty big
    """
    
    X = X[Y.known_ids]
    Y = Y[Y.known_ids]
    
    m = Perceptron(alpha=0, n_iter=100).fit(X, Y)
    # Start with point close to hypothesis ! Very important
    w0 = m.coef_
    
    assert accuracy_score(m.predict(X), Y) > 0.98, "fucking hit and run in this formulation works only for almost \
            separable cases"
    if X.shape[0] > 100:
        means = X.mean(axis=0).reshape(-1)
        assert all(abs(m) < 0.1 for m in means), "hit_and_run assumes mean 0 features"
    
    
    def _solve_quadratic_safe(a,b,c):
        # calculate the discriminant
        d = (b**2) - (4*a*c)
        
        if d <= 0:
            return -1, 1 # Should be relatively rare and is ok to return this
        
        # find two solutions
        sol1 = (-b-math.sqrt(d))/(2*a)
        sol2 = (-b+math.sqrt(d))/(2*a)

        return sol1, sol2
    
    # In regular hit and run we do bound calculation in every turn
    # Here it is approximated becuase we are always inside a sphere
    MIN_DELTA = -2
    MAX_DELTA = 2
    
    d = X.shape[1]
    w = w0
    alpha = (eps / (1.0 - eps))
    out = []
    
    for i in range(N*T):
        theta = np.random.uniform(-1,1,size=(1,d))
        theta = theta/np.linalg.norm(theta)

        # Find max and min ro (quadratic equation, trust me)
        
        a = 1
        b = (2*w[0,0]*theta[0,0] + 2*w[0,1]*theta[0,1])/(theta[0,0]**2 + theta[0,1]**2)
        c =(w[0,0]**2 + w[0,1]**2 - 1)/(theta[0,0]**2+theta[0,1]**2)
        ro_min, ro_max = sorted(_solve_quadratic_safe(a,b,c))
        
        # Simple way to make sure that w is always inside circle after step (S^d \intersection L)
        L = np.vstack([w + delta * theta for delta in np.linspace(ro_min, ro_max, sub_sample_size)])
        missed_for_sample = (np.abs(np.sign(L.dot(X.T)) - Y)).sum(axis=1)/2.0
        weights = np.array([alpha**m for m in missed_for_sample])
        #TODO: filter very weak probabilities or do some min?
        w = L[np.random.choice(range(len(L)), 1, p=weights/sum(weights))]

        if i>0 and i%T == 0:
            out.append(w)
            
    return np.vstack(out)

def chen_krause_strategy(X, Y, current_model, rng, N=100, T=10, sub_sample_size=100, eps=0.5):
    """
    @param current_model Not used, but kept for consistency with interface of strategy
    @param N hypothesis of points wanted
    @param T number of mixing iterations
    @param sub_sample_size how many samples of hypothesis take on the ray.
    @param eps noise level. Note that i should be pretty big
    """
    # Sample hypotheses
    H = hit_and_run(X, y, N=100, T=10, eps=0.3)
    k=0
    picked = []
    
    # For hypothesis dict
    def key(a):
        return hashlib.sha1(a.view(np.uint8)).hexdigest()
    
    # Construct k-batch
    for k in range(batch_size):
        
        # 1. Construct hypothesis codes
        preds_picked = (preds_unknown[:, picked]).copy()
        if len(picked):
            h_codes = np.hstack([preds_known, preds_picked])
        else:
            h_codes = preds_known
        counted_same = []
        
        for i in range(X_unknown.shape[0]):
            if i not in picked:
                counts = defaultdict(int)
                # 2. Count hypothesis by adding to dict
                for j in range(H.shape[0]):
                    hypothesis_key = key(h_codes[j]) + str(preds_unknown[j,i])  
                    counts[hypothesis_key] += 1        
                    
                # 3. Count removing 1 to obtain needed value
                counted_same.append(sum(counts.values()) - len(counts))
            else:
                counted_same.append(np.inf)
        picked.append(np.argmin(counted_same))
    return picked