<jupyter_start><jupyter_text>Quiz Question. What is the document id of Barack Obama's article?ANS: 35817Quiz Question. Which bin contains Barack Obama's article? Enter its integer index. ANS: 50194<jupyter_code>print (wiki[wiki['name'] == '<NAME>'])
Biden_doc = corpus[24478,:]
Biden_index_bits = (Biden_doc.dot(model['random_vectors']) >= 0)
powers_of_two = (1 << np.arange(15, -1, -1))
print (Biden_index_bits)
print (powers_of_two)          # [32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
print (Biden_index_bits.dot(powers_of_two))
print (Obama_index_bits.flatten() == Biden_index_bits.flatten())
print(sum(Obama_index_bits.flatten() == Biden_index_bits.flatten()))<jupyter_output>False<jupyter_text>Recall from the previous assignment that <NAME> was a close neighbor of Barack Obama. Quiz Question. Examine the bit representations of the bins containing Barack Obama and <NAME>. In how many places do they agree?ANS: 14Compare the result with a former British diplomat, whose bin representation agrees with Obama's in only 8 out of 16 places.<jupyter_code>print (wiki[wiki['name']=='<NAME>'])

print (np.array(model['bin_index_bits'][22745], dtype=int)) # list of 0/1's
print (model['bin_index_bits'][35817] == model['bin_index_bits'][22745])
print (model['table'][model['bin_indices'][35817]])
doc_ids = list(model['table'][model['bin_indices'][35817]])
doc_ids.remove(35817) # display documents other than Obama

docs = wiki.iloc[doc_ids]
print(docs['name'])
print ("It turns out that <NAME> is much closer to Barack Obama than any of the four documents, even though Biden's bin representation differs from Obama's by 2 bits.")
def cosine_distance(x, y):
    xy = x.dot(y.T)
    dist = xy/(norm(x)*norm(y))
    return 1-dist[0,0]

obama_tf_idf = corpus[35817,:]
biden_tf_idf = corpus[24478,:]

print ('================= Cosine distance from Barack Obama')
print ('Barack Obama - {0:24s}: {1:f}'.format('<NAME>',
                                             cosine_distance(obama_tf_idf, biden_tf_idf)))
for doc_id in doc_ids:
    doc_tf_idf = corpus[doc_id,:]
    print ('Barack Obama - {}: {}'.format(wiki.iloc[doc_id]['name'], cosine_distance(obama_tf_idf, doc_tf_idf)))<jupyter_output>================= Cosine distance from Barack Obama
Barack Obama - <NAME>               : 0.703139
Barack Obama - <NAME>: 0.9508667575252789
Barack Obama - <NAME> (politician): 0.975966004109956
Barack Obama - <NAME>: 0.9782561630406376
Barack Obama - <NAME>: 0.9930921484244789<jupyter_text>Moral of the story. Similar data points will in general tend to fall into nearby bins, but that's all we can say about LSH. In a high-dimensional space such as text features, we often get unlucky with our selection of only a few random vectors such that dissimilar data points go into the same bin while similar data points fall into different bins. Given a query document, we must consider all documents in the nearby bins and sort them according to their actual distances from the query. 1. Let L be the bit representation of the bin that contains the query documents.2. Consider all documents in bin L.3. Consider documents in the bins whose bit representation differs from L by 1 bit.4. Consider documents in the bins whose bit representation differs from L by 2 bits.To obtain candidate bins that differ from the query bin by some number of bits, we use itertools.combinations, which produces all possible subsets of a given list. See this documentation for details.1. Decide on the search radius r. This will determine the number of different bits between the two vectors.2. For each subset (n_1, n_2, ..., n_r) of the list [0, 1, 2, ..., num_vector-1], do the following:   * Flip the bits (n_1, n_2, ..., n_r) of the query bin to produce a new bit vector.   * Fetch the list of documents belonging to the bin indexed by the new bit vector.   * Add those documents to the candidate set.<jupyter_code>from itertools import combinations

num_vector = 16
search_radius = 0
trynerr = [1,2,3,4,5]
for diff in combinations(range(num_vector), search_radius):
    print (diff)
    print(1)
    
def search_nearby_bins(query_bin_bits, table, search_radius=2, initial_candidates=set()):
    """
    For a given query vector and trained LSH model, return all candidate neighbors for
    the query among all bins within the given search radius.
    
    Example usage
    -------------
    >>> model = train_lsh(corpus, num_vector=16, seed=143)
    >>> q = model['bin_index_bits'][0]  # vector for the first document
  
    >>> candidates = search_nearby_bins(q, model['table'])
    """
    num_vector = len(query_bin_bits)
    powers_of_two = 1 << np.arange(num_vector-1, -1, -1)
    
    # Allow the user to provide an initial set of candidates.
    candidate_set = initial_candidates.copy()
    
    for different_bits in combinations(range(num_vector), search_radius):       
        # Flip the bits (n_1,n_2,...,n_r) of the query bin to produce a new bit vector.
        ## Hint: you can iterate over a tuple like a list
        alternate_bits = query_bin_bits.copy()
        
        for i in different_bits:
            alternate_bits[i] = not query_bin_bits[i] # YOUR CODE HERE 
        
        # Convert the new bit vector to an integer index
        nearby_bin = alternate_bits.dot(powers_of_two)
       
        # Fetch the list of documents belonging to the bin indexed by the new bit vector.
        # Then add those documents to candidate_set
        # Make sure that the bin exists in the table!
        # Hint: update() method for sets lets you add an entire list to the set
        if nearby_bin in table:
            candidate_set.update(table[nearby_bin]) # YOUR CODE HERE: Update candidate_set with the documents in this bin.
            
    return candidate_set
import types
import weakref
from copyreg import dispatch_table
obama_bin_index = model['bin_index_bits'][35817] # bin index of Barack Obama

candidate_set = search_nearby_bins(obama_bin_index, model['table'], search_radius=0)
if candidate_set == set([35817, 21426, 53937, 39426, 50261]):
    print ('Passed test')
else:
    print(candidate_set)
    print ('Check your code')
print ('List of documents in the same bin as Obama: 35817, 21426, 53937, 39426, 50261')
candidate_set = search_nearby_bins(obama_bin_index, model['table'], search_radius=1, initial_candidates=candidate_set)
if candidate_set == set([39426, 38155, 38412, 28444, 9757, 41631, 39207, 59050, 47773, 53937, 21426, 34547,
                         23229, 55615, 39877, 27404, 33996, 21715, 50261, 21975, 33243, 58723, 35817, 45676,
                         19699, 2804, 20347]):
    print ('Passed test')
else:
    print(candidate_set)
    print(len(candidate_set))
    print ('Check your code')
def query(vec, model, k, max_search_radius):
  
    data = model['data']
    table = model['table']
    random_vectors = model['random_vectors']
    num_vector = random_vectors.shape[1]
    
    
    # Compute bin index for the query vector, in bit representation.
    bin_index_bits = (vec.dot(random_vectors) >= 0).flatten()
    
    # Search nearby bins and collect candidates
    candidate_set = set()
    for search_radius in range(max_search_radius+1):
        candidate_set = search_nearby_bins(bin_index_bits, table, search_radius, initial_candidates=candidate_set)
    
    # Sort candidates by their true distances from the query
    nearest_neighbors = pd.DataFrame({'id' : list(candidate_set)})
    candidates = data[np.array(list(candidate_set)),:]
    nearest_neighbors['distance'] = pairwise_distances(candidates, vec, metric='cosine').flatten()
    
    return nearest_neighbors.sort_values(by=['distance'], ascending=True)[:k],len(candidate_set)
print (query(corpus[35817,:], model, k=10, max_search_radius=3))
wiki['id'] = wiki.index
#wiki['id'].astype(str).astype(int)
wiki[['id', 'name']]
result, num_candidates_considered = query(corpus[35817,:], model, k=10, max_search_radius=3)
print (num_candidates_considered)
result['id']
pd.merge(result, wiki[['id', 'name']], how='inner', on='id').sort_values(by=['distance'])<jupyter_output><empty_output><jupyter_text>Effect of nearby bin searchHow does nearby bin search affect the outcome of LSH? There are three variables that are affected by the search radius:1. Number of candidate documents considered2. Query time3. Distance of approximate neighbors from the queryLet us run LSH multiple times, each with different radii for nearby bin search. We will measure the three variables as discussed above.<jupyter_code>num_candidates_history = []
query_time_history = []
max_distance_from_query_history = []
min_distance_from_query_history = []
average_distance_from_query_history = []
import time

for max_search_radius in range(17):
    start=time.time()
    # Perform LSH query using Barack Obama, with max_search_radius
    result, num_candidates = query(corpus[35817,:], model, k=10,
                                   max_search_radius=max_search_radius)
    end=time.time()
    query_time = end-start  # Measure time
    
    print ('Radius:', max_search_radius)
    # Display 10 nearest neighbors, along with document ID and name
    print (result.merge(wiki[['id', 'name']], how='inner', on='id').sort_values(by=['distance']))
    
    # Collect statistics on 10 nearest neighbors
    average_distance_from_query = result['distance'][1:].mean()
    max_distance_from_query = result['distance'][1:].max()
    min_distance_from_query = result['distance'][1:].min()
    
    num_candidates_history.append(num_candidates)
    query_time_history.append(query_time)
    average_distance_from_query_history.append(average_distance_from_query)
    print(average_distance_from_query)
    max_distance_from_query_history.append(max_distance_from_query)
    min_distance_from_query_history.append(min_distance_from_query)

plt.figure(figsize=(7,4.5))
plt.plot(num_candidates_history, linewidth=4)
plt.xlabel('Search radius')
plt.ylabel('# of documents searched')
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(query_time_history, linewidth=4)
plt.xlabel('Search radius')
plt.ylabel('Query time (seconds)')
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(average_distance_from_query_history, linewidth=4, label='Average of 10 neighbors')
plt.plot(max_distance_from_query_history, linewidth=4, label='Farthest of 10 neighbors')
plt.plot(min_distance_from_query_history, linewidth=4, label='Closest of 10 neighbors')
plt.xlabel('Search radius')
plt.ylabel('Cosine distance of neighbors')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()<jupyter_output><empty_output><jupyter_text>Some observations:As we increase the search radius, we find more neighbors that are a smaller distance away.With increased search radius comes a greater number documents that have to be searched. Query time is higher as a consequence.With sufficiently high search radius, the results of LSH begin to resemble the results of brute-force search.<jupyter_code>print('the smallest search radius that yielded the correct nearest neighbor, namely <NAME> is 2')
print('the smallest search radius for <NAME> that produced an average distance of 0.78 or bette is 11')
def brute_force_query(vec, data, k):
    num_data_points = data.shape[0]
    
    # Compute distances for ALL data points in training set
    nearest_neighbors = pd.DataFrame({'id':range(num_data_points)})
    nearest_neighbors['distance'] = pairwise_distances(data, vec, metric='cosine').flatten()
    
    return nearest_neighbors.sort_values(by=['distance'], ascending=True)[:k]
max_radius = 17
precision = {i:[] for i in range(max_radius)}
average_distance  = {i:[] for i in range(max_radius)}
query_time  = {i:[] for i in range(max_radius)}

np.random.seed(0)
num_queries = 10
for i, ix in enumerate(np.random.choice(corpus.shape[0], num_queries, replace=False)):
    print('%s / %s' % (i, num_queries))
    ground_truth = set(brute_force_query(corpus[ix,:], corpus, k=25)['id'])
    # Get the set of 25 true nearest neighbors
    
    for r in range(1,max_radius):
        start = time.time()
        result, num_candidates = query(corpus[ix,:], model, k=10, max_search_radius=r)
        end = time.time()

        query_time[r].append(end-start)
        # precision = (# of neighbors both in result and ground_truth)/10.0
        precision[r].append(len(set(result['id']) & ground_truth)/10.0)
        average_distance[r].append(result['distance'][1:].mean())
plt.figure(figsize=(7,4.5))
plt.plot(range(1,17), [np.mean(average_distance[i]) for i in range(1,17)], linewidth=4, label='Average over 10 neighbors')
plt.xlabel('Search radius')
plt.ylabel('Cosine distance')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(range(1,17), [np.mean(precision[i]) for i in range(1,17)], linewidth=4, label='Precison@10')
plt.xlabel('Search radius')
plt.ylabel('Precision')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(range(1,17), [np.mean(query_time[i]) for i in range(1,17)], linewidth=4, label='Query time')
plt.xlabel('Search radius')
plt.ylabel('Query time (seconds)')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()
precision = {i:[] for i in range(5,20)}
average_distance  = {i:[] for i in range(5,20)}
query_time = {i:[] for i in range(5,20)}
num_candidates_history = {i:[] for i in range(5,20)}
ground_truth = {}

np.random.seed(0)
num_queries = 10
docs = np.random.choice(corpus.shape[0], num_queries, replace=False)

for i, ix in enumerate(docs):
    ground_truth[ix] = set(brute_force_query(corpus[ix,:], corpus, k=25)['id'])
    # Get the set of 25 true nearest neighbors

for num_vector in range(5,20):
    print('num_vector = %s' % (num_vector))
    model = train_lsh(corpus, num_vector, seed=143)
    
    for i, ix in enumerate(docs):
        start = time.time()
        result, num_candidates = query(corpus[ix,:], model, k=10, max_search_radius=3)
        end = time.time()
        
        query_time[num_vector].append(end-start)
        precision[num_vector].append(len(set(result['id']) & ground_truth[ix])/10.0)
        average_distance[num_vector].append(result['distance'][1:].mean())
        num_candidates_history[num_vector].append(num_candidates)
plt.figure(figsize=(7,4.5))
plt.plot(range(5,20), [np.mean(average_distance[i]) for i in range(5,20)], linewidth=4, label='Average over 10 neighbors')
plt.xlabel('# of random vectors')
plt.ylabel('Cosine distance')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(range(5,20), [np.mean(precision[i]) for i in range(5,20)], linewidth=4, label='Precison@10')
plt.xlabel('# of random vectors')
plt.ylabel('Precision')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(range(5,20), [np.mean(query_time[i]) for i in range(5,20)], linewidth=4, label='Query time (seconds)')
plt.xlabel('# of random vectors')
plt.ylabel('Query time (seconds)')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()

plt.figure(figsize=(7,4.5))
plt.plot(range(5,20), [np.mean(num_candidates_history[i]) for i in range(5,20)], linewidth=4,
         label='# of documents searched')
plt.xlabel('# of random vectors')
plt.ylabel('# of documents searched')
plt.legend(loc='best', prop={'size':15})
plt.rcParams.update({'font.size':16})
plt.tight_layout()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1309335192344255, 'fraction_numerical': 0.04151086887635465, 'mean_word_length': 4.805739514348786, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '219014', 'license': 'MIT', 'n_tokens_mistral': 5683, 'n_tokens_neox': 5077, 'n_words': 1425, 'path': 'Week 2-2.ipynb', 'repo_name': 'Interesante875/Machine_Learning_Specialization_Washington', 'size': '15863'}