<jupyter_start><jupyter_text>Additional analysis and data generation is done in separate notebooks. For details, see: * `Embedding IO.ipynb`* `Creating Neighbors from a Directory.ipynb`* `adaptedKendallTau.ipynb`* `Comparing All Neighbour Sets for Workshop Summary.ipynb`* TODO: `Comparing knn metrics.ipynb`: Create one that includes comparisons of knn-metrics<jupyter_code>module_location = "/scratch/research/text_workshop_2018"
data_path = "/scratch/research/text_workshop_2018/data/embeddings"

import sys
import os
sys.path.append(module_location)

from textproc import embedding as embed

import pandas as pd
import scipy
import scipy.io
import numpy as np

from itertools import combinations as comb

#Plotting stuff
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_context("notebook")

import tqdm<jupyter_output><empty_output><jupyter_text>Comparing Vector Space EmbeddingsOne of the goals of the text analysis workshop at TIMC (January 2018) was to test out ways to **compare vector space embeddings**. The goal of the comparison is to analyze the **similarity of the local neighbourhoods** of points in the embeddings as a way of determining if an embedding techinique is similar to **itself** under multiple applications to the same data (aka. stability of the embedding technique), and to evaluate the how similar in local structure of **different** embedding techniques are.Since this was a text analysis workshop, we wanted to compare the similarity between common text embedding techniques. We used the Yelp dataset (tokenized in a standard fashion) for all the comparisons. These were the techniques that we compared (so far):* PMI+SVD (factorization of the pointwise mutual information (PMI) matrix via truncated SVD)* fastext* eigenwords* GloVe* TODO: word2vecWe proposed a way of comparing embeddings using **nearest neighbour structures** as follows:Given a point, $P$, compare the similarity of its k-nearest neighbours under two different embeddings using a set or partial order similarity metric (eg. jaccard) and call this the **local neighbourhood similarity score** of $P$. Then aggregate the local similarity scores of all the comparable points in the embeddings (say, using the mean) to produce a **(global) neighbourhood similarity score** between the two embeddings. This score will represent the similarity of two different embeddings of the same data.To test that this makes sense, we generated many different embeddings and created an infrastructure for easily computing the pairwise similarity of multiple different embeddings of the same dataset. The infrastructure can be found in the module `embedding.py`.  Generating EmbeddingsGo ahead and create an embedding of your favorite data via your favorite technique. To make your data ingestible by the similarity comparison infrastructure, save your embedding using the `save_embedding` function.<jupyter_code>help(embed.save_embedding)<jupyter_output><empty_output><jupyter_text>Here's an example embedding created on the Yelp dataset using fasttext.<jupyter_code>#embedding_basefilename = "yelp_pmi_svd_randomized"
embedding_basefilename = "yelp_fastext_dim128_min_count1"
%%time
embedding, labels, metadata = embed.read_embedding(embedding_basefilename, data_path=data_path)
metadata
embedding.shape
len(labels)
labels[-10:]<jupyter_output><empty_output><jupyter_text>Generating k-nearest neighborsThe easiest way to do this is to use `get_neighbors`, supplying the base filename of your embedding and a list of `run_numbers` you want to process.<jupyter_code>help(embed.get_neighbors)<jupyter_output><empty_output><jupyter_text>There is the option of changing the number of neighbors that you want along with the metric you want to apply to compute distance between points in your vector space. We'll explore the effects of these choices in the notebook entitled `Comparing knn metrics.ipynb`.First, generate the 100 nearest neighbours under the cosine metric for the fasttext embeddings:<jupyter_code>%%time
embed.make_neighbors(embedding_basefilename, run_numbers=[0, 1], k=100, knn_metrics=['cosine'], data_path=data_path)<jupyter_output><empty_output><jupyter_text>There is a helpful piece of code that will allow you to look for all the embedding files in a directory that don't yet have have associated neighbor sets files for a given list of k-nearest neighbour metrics, and will generate the missing k-nearest neighbour sets in parallel in this accompanying notebook: `Creating Neighbors from a Directory.ipynb`.<jupyter_code>neighbors_1, neighbors_metadata_1 = embed.read_neighbors(embedding_basefilename, metric='cosine',
                                                         run_number=0, data_path=data_path)
neighbors_metadata_1<jupyter_output><empty_output><jupyter_text>`neighbors_1[0]` is a dict keyed by label (in this case words in the Yelp dataset) with values the list of the 100 nearest neighbours to that label.<jupyter_code>label = 'ottawa'
neighbors_1[0][label][:10]<jupyter_output><empty_output><jupyter_text>`neighbors_1[1]` is a dict keyed by label (in this case words in the Yelp dataset) with values the list of the distance to the 100 nearest neighbours to that label. We don't use this in our analysis yet, but we plan to try some comparisons that may use the actual distances to compute the local similarity score in the future.<jupyter_code>neighbors_1[1][label][:15]<jupyter_output><empty_output><jupyter_text>A Single Comparison Before comparing accross embedding techniques, let's do a single comparison, of two embeddings using the exact same parameters to test for stability and to get a feel for how we're computing similarity.We need another embedding and its nearest neighbors to do a comparison, so lets take a different embedding of the same data, under the same embedding technique with the same k-nearest neighbour metric.<jupyter_code>neighbors_2, neighbors_metadata_2 = embed.read_neighbors(embedding_basefilename, metric='cosine',
                                                         run_number=1, data_path=data_path)
neighbors_metadata_2
neighbors_2[0][label][:10]<jupyter_output><empty_output><jupyter_text>The similarity score of these neighbor lists are as follows (note that we omit the "first" neighbour itself in this calculation).<jupyter_code>print("Jaccard similarity: {}".format(embed.list_similarity(label, neighbors_1[0][label][1:], neighbors_2[0][label][1:], how='jaccard')))
print("Adapted Kendall-Tau similarity: {}".format(embed.list_similarity(label, neighbors_1[0][label][1:], neighbors_2[0][label][1:], how='adapted-ktau')))<jupyter_output><empty_output><jupyter_text>The adapted Kendall-Tau similarity being larger than the Jaccard similarity suggests that the neighbours that are in common are mostly in the same order.Let's check.First off, observe that most of the neighbours of "ottawa" don't actually match (in terms of exact position).<jupyter_code>np.array(neighbors_1[0][label][1:]) == np.array(neighbors_2[0][label][1:])<jupyter_output><empty_output><jupyter_text>But there is a lot of overlap in the first 10 neighbours, and even their order, even if they aren't in the exact same positions. We'll see that the adapted Kendall-Tau score will take this into account.<jupyter_code>intersection = set(neighbors_1[0][label][1:11]).intersection(neighbors_2[0][label][1:11])
len(intersection)
intersection_1 = [x for x in neighbors_1[0][label][1:] if x in intersection]
intersection_2 = [x for x in neighbors_2[0][label][1:] if x in intersection]
list(zip(intersection_1, intersection_2))<jupyter_output><empty_output><jupyter_text>We'll continue to observe this difference between Jaccard and adapted Kendall-Tau throughout the rest of the notebook.  Comparing NeighboursTo compare neighbors between two embeddings, for each label, $w$, that belongs to both embeddings, we compare its neighbors by computing $s(n_1[w], n_2[w])$ where $n_i[w]$ are the neighbors of $w$ under the $i^{th}$ embedding ($i= 1, 2$), and $s$ is a similarity scoring function.Currently, we have two different options implemented for $s$:* `jaccard`: jaccard similarity (treating $n_1[w]$ as a set)* `adapted-ktau`: an adapted version of Kendall-Tau that computes the similarity of two partial orders. See `adaptedKendallTau.ipynb` for more details.We intend to look into other similarity scores between partial orders as described in the thesis *Metric methods for analyzing partially ranked data* by <NAME> (November 1984). However, as you will see in the results below, the adapted Kendall-Tau method may do a sufficiently good job for our purposes.<jupyter_code>help(embed.compare_neighbors)
help(embed.parallel_compare_neighbors)<jupyter_output><empty_output><jupyter_text>WARNING: the parallel version will hang with Jaccard as it is already super fast and there is likely a race somewhere in Pool(). Only use it with adapted Kendall-Tau<jupyter_code>%%time
jaccard_comparison = embed.compare_neighbors(neighbors_1[0], neighbors_2[0], how='jaccard')
jaccard_df = pd.DataFrame(list(zip(*jaccard_comparison)), columns=['label', 'similarity'])
%%time
akt_comparison = embed.parallel_compare_neighbors(neighbors_1[0], neighbors_2[0], how='adapted-ktau', n_proc=6)
akt_df = pd.DataFrame(list(zip(*akt_comparison)), columns=['label', 'similarity'])<jupyter_output><empty_output><jupyter_text>We will define the overall neighbourhood similarity score to be the mean of the local neighbourhood similarity scores.<jupyter_code>print("Jaccard neighbourhood similarity score: {}".format(scipy.mean(jaccard_df['similarity'])))
print("Adapted Kendall-Tau neighbourhood similarity score: {}".format(scipy.mean(akt_df['similarity'])))<jupyter_output><empty_output><jupyter_text>We'll want to see what's going on under the hood, as well as finding out what accounts for the difference in these neighbourhood similarity scores.  Looking at the distributions of the neighbourhood similarity scores Of course, we want to know if taking mean of the local similary scores is a reasonable thing to do. Let's actually look at the distribution of the similarity scores.<jupyter_code>stats = scipy.stats.describe(jaccard_df['similarity'])
print("Jaccard neighbourhood similarity stats:\n mean:{}\n variance:{}".format(stats.mean, stats.variance))
plt.figure(figsize=(10, 7))

plt.title("Histogram of Jaccard Local Neighbourhood Similarity Scores")
sns.distplot(jaccard_df['similarity'], axlabel='Similarity', kde=True, bins=100);
stats = scipy.stats.describe(akt_df['similarity'])
print("Adapted Kendall-Tau neighbourhood similarity stats:\n mean:{}\n variance:{}".format(stats.mean, stats.variance))
plt.figure(figsize=(10, 7))

plt.title("Histogram of adapted Kendall-Tau Neighbourhood Similarity Scores")
sns.distplot(akt_df['similarity'], axlabel='Similarity', kde=True, bins=100);<jupyter_output><empty_output><jupyter_text>The histogram of adapted Kendall-Tau neighbourhood similarity scores is a lot smoother, whereas the discrete nature of Jaccard similarity has a strong effect on the overall distribution.  What accounts for the difference in jaccard and adapted Kendall-Tau similarities?First let's compute the difference between the jaccard and adapted kendall-tau neighbourhood similarity scores.<jupyter_code>df = jaccard_df.merge(akt_df, on=['label'], suffixes=['_jac', '_akt'])
df['sim_diff'] = df.similarity_akt - df.similarity_jac
df.sort_values('sim_diff', ascending=False);<jupyter_output><empty_output><jupyter_text>Let's look at the relationship between the Jaccard and Kendall-Tau scores.<jupyter_code>g = sns.JointGrid(x='similarity_jac', y='similarity_akt', data=df, size=10)
g = g.plot_joint(plt.scatter, c=df['sim_diff'], s=3, cmap='viridis_r')
plt.plot(df['similarity_jac'], df['similarity_jac'], c='black')
g = g.set_axis_labels(ylabel='Adapted Kendall-Tau Neighbourhood Similarity', xlabel='Jaccard Neighbourhood Similarity')
g = g.plot_marginals(sns.distplot, kde=False, bins=100)
g = g.annotate(scipy.stats.pearsonr)
plt.colorbar();<jupyter_output><empty_output><jupyter_text>To get a better feel for this, let's take also plot the differences between adapted Kendall-Tau and Jaccard similarities in general.<jupyter_code>import random
N = 100
n_samples = 50
mOrd = []
mOrdR = []
mTopSh = []
p = []
mSh = []
jac = []
X = list(range(1,N+1,1))
Z = list(range(N+1,2*N+1,1))

for m in range(1,N+1,1):
    xOrd = []
    xOrdR = []
    xSh = []
    xTopSh = []
    p.append(m/N)
    for l in range(n_samples):
        ## list of length N with ordered top-m in common
        Y = X[0:m]
        Y.extend(random.sample(Z,N-m))
        xOrd.append(embed.adaptedKendallTau(X,Y))

        ## list of length N with top-m in common
        Y = X[0:m]
        Y.extend(random.sample(Z,N-m))
        random.shuffle(Y)
        xTopSh.append(embed.adaptedKendallTau(X,Y))
        
        ## list of length N with m in common
        Y = random.sample(X,m)
        Y.extend(random.sample(Z,N-m))
        random.shuffle(Y)
        xSh.append(embed.adaptedKendallTau(X,Y))
    mOrd.append(np.mean(xOrd))
    mTopSh.append(np.mean(xTopSh))
    mSh.append(np.mean(xSh))
    jac.append(embed.jaccard(set(X),set(Y)))
g = sns.JointGrid(x='similarity_jac', y='similarity_akt', data=df, size=10)
g = g.plot_joint(plt.scatter, c=df['sim_diff'], s=3, cmap='viridis_r')
plt.plot(jac,mSh, ls='dotted', label='Shuffle',color='blue')
plt.plot(jac,mOrd, ls='dotted', label='Ordered',color='purple')
plt.plot(jac,mTopSh, ls='dotted', label='Ordered',color='green')

plt.xlabel("Jaccard similarity")
plt.ylabel("Tau similarity")
g = g.set_axis_labels(ylabel='Adapted Kendall-Tau Neighbourhood Similarity', xlabel='Jaccard Neighbourhood Similarity')
g = g.plot_marginals(sns.distplot, kde=False, bins=100)
g = g.annotate(scipy.stats.pearsonr)
plt.colorbar();<jupyter_output><empty_output><jupyter_text>Here the additional lines represent the effect of ordering on the adapted Kendall-Tau similarity metric:* purple: the common elements are all in order at the beginning of the list* green: the common elements are all at the beginning of the list (shuffled)* blue: the common elements are in random orderThis suggests that the common elements are mostly at the beginning of the list, and are mostly in the correct order. The colorbar represents the value of the adapted Kendall-Tau similarity minus the Jaccard similarity. The colouring suggests that the largest differences lie in the range where the purple and blue lines differ the most.It also looks like there may be a normal distribution across the color bar. Let's check!<jupyter_code>plt.figure(figsize=(10, 7))

plt.title("Distribution of adapted Kendall-Tau minus Jaccard Neighbourhood Similarity Scores")
sns.distplot(df['sim_diff'], axlabel='Difference in Similarity', kde=False, norm_hist=False, bins=100);<jupyter_output><empty_output><jupyter_text>This is a smooth looking plot! Plus it's worth noting that the adapted Kendall-Tau similarity is almost always greater than the Jaccard similarity.<jupyter_code>stats = scipy.stats.describe(df['sim_diff'])
print("Adapted Kendall-Tau minus Jaccard neighbourhood similarity stats:\n mean: {}\n variance: {}\n minimum: {}\n maximum: {}".format(stats.mean, stats.variance, *stats.minmax))<jupyter_output><empty_output><jupyter_text>How does the choice of k affect the scores?So far we haven't looked at the effect that the size of the neighbourhood that we're comparing is having, or how this affects the Jaccard vs. adapted Kendall-Tau similarity scores.First, let's take a look at the words for which Jaccard and adapted Kendall-Tau differ the most, and compare the scores as we vary over the number of neighbours we're comparing, that is, over k.  Words whose adapted Kendall-Tau and Jaccard neighbourhood similarities differ the most<jupyter_code>def compare_similarities_varying_k(label, n1, n2):

    similarities = []
    for k in range(2, len(n1)):
        akt_k = embed.adaptedKendallTau(n1[1:k], n2[1:k])
        jac_k = embed.jaccard(set(n1[1:k]), set(n2[1:k]))
        similarities.append([k, jac_k, akt_k])

    similarities_df = pd.DataFrame(similarities, columns=['k', 'similarity_jac', 'similarity_akt'])

    plt.plot(similarities_df['k'], similarities_df['similarity_jac'], label='Jac')
    plt.plot(similarities_df['k'], similarities_df['similarity_akt'],label='aKT')
    plt.legend()
    plt.xlabel('k')
    plt.ylabel('Similarity')

    plt.title('Neighbourhood similarity of "{}" as k varies'.format(label));
plt.figure(figsize=(25, 60))
for i, label in enumerate(df.sort_values('sim_diff', ascending=False)[:6].label):
    n1 = neighbors_1[0][label]
    n2 = neighbors_2[0][label]
    plt.subplot(6, 2, i+1)
    compare_similarities_varying_k(label, n1, n2)<jupyter_output><empty_output><jupyter_text>These pictures are all roughly the same. There is some initial instability, as both measures are extremely sensitive to having different neighbours when the k value is low. There is a value of $k$ after which the neighbors mostly differ as we see the Jaccard similarity score steadily declining. However, the neighbors that have been added after the initial instability were all added in roughly the same order. It is worth noting that Jaccard similarity seems to give a stronger indication that we've left a similar "local neighborhood" than adapted Kendall-Tau does. Still, there is still a noticeable inflection point on the Kendall-Tau similarity graphs. We will return to this idea of the choosing $k$, and detecting the "local neighbourhood" structure later.  Is this typical?Of course, these were the words that exhibited the most difference between the two different similarity scores. Let's take a random sample of 6 words near the mean difference between Kendall-Tau and Jaccard similarities.<jupyter_code>most_typical_filter = (stats.mean - stats.variance < df.sim_diff) & (df.sim_diff < stats.mean + stats.variance)
sample = random.sample(list(np.where(most_typical_filter)[0]), 6)
plt.figure(figsize=(25, 80))
for i, label in enumerate(df.iloc[sample].label):
    n1 = neighbors_1[0][label]
    n2 = neighbors_2[0][label]
    plt.subplot(10, 2, i+1)
    compare_similarities_varying_k(label, n1, n2)<jupyter_output><empty_output><jupyter_text>This main difference that stands out with these examples from ones where the aKT minus Jaccard is the greatest, is that there is no pronounced drop off in the Jaccard score at some point. The difference between the two scores is almost constant beyond the initial volatility. Let's check the other extreme for completeness.<jupyter_code>plt.figure(figsize=(25, 60))
for i, label in enumerate(df.sort_values('sim_diff', ascending=True)[:6].label):
    n1 = neighbors_1[0][label]
    n2 = neighbors_2[0][label]
    plt.subplot(6, 2, i+1)
    compare_similarities_varying_k(label, n1, n2)<jupyter_output><empty_output><jupyter_text>In almost all these cases, we see that the Jaccard similarity is steadily increasing. In these cases, the bias of adapted Kendall-Tau towards matching earlier elements (and getting them in the same order) means that Jaccard increases more than adapted Kendall-Tau as new elements that match are added.   Summary of varying k (with a single comparison)In this particular example, where two fairly similar embeddings are being compared as long as k is great enough (say at least 20), both the Jaccard and adapted Kendall-Tau similarity scores are fairly stable. This is typical of all comparisons, and we'll see more evidence for this later when we do pairwise comparisons across embedding techniques while varying k.  Comparisons of neighbourhood similarity accross embedding techniquesRecall that the goal was to compare the similarity between different text embedding techniques. We used the Yelp dataset for all the comparisons. Ultimately we want to do the pairwise comparisons between:* PMI+SVD (factorization of the pointwise mutual information (PMI) matrix via truncated SVD)* fastext* eigenwords* GloVe* TODO: word2vecWe'll do this by taking 5 runs of each embedding technique, computing the 100 nearest neighbours using cosine similarity, and then computing the neighbour similarity scores using Jaccard and Kendall-Tau. We'll only using cosine similarity here, as there is no pronounced difference in using other metrics and cosine is the generally accepted default. See another notebook referenced at the top for digging into the differences that come from using different k-nearest neighbour metrics. Since it's relatively slow to generate this many pairwise comparisons, we'll simply read in some existing comparisons. However, this can be done using `embed.get_pairwise_comparisons` and `embed.parallel_get_pairwise_comparisons` as in the notebook referenced at the top.<jupyter_code>%%time
jac_comparisons, jac_metadata = embed.read_comparisons("25x25_cosine_text_workshop_jac", data_path=data_path)
%%time
akt_comparisons, akt_metadata = embed.read_comparisons("25x25_cosine_text_workshop_akt", data_path=data_path)<jupyter_output><empty_output><jupyter_text>Given a comparison, we'll want to take a look at the similarity scores; `embed.aggregate_comparison_stats` does this.<jupyter_code>help(embed.aggregate_comparison_stats)
%%time
jac_results, jac_results_mean, jac_results_variance = embed.aggregate_comparison_stats(jac_comparisons)
%%time
akt_results, akt_results_mean, akt_results_variance = embed.aggregate_comparison_stats(akt_comparisons)<jupyter_output><empty_output><jupyter_text>Jaccard Similarity ScoresFirst look at the Jaccard scores.<jupyter_code># Create simplified labels for the upcoming plots (and replace minkowski by euclidean)
def simplified_matrix_labels(metadata, knn=True):
    matrix_labels = []
    label_filter = []
    for meta in metadata:
        # manhattan and l1 are the same metric, so drop manhattan, euclidean, l2, and minkowski are the same
        if 'manhattan' in meta['k-nn Metric'] or 'hamming' in meta['k-nn Metric'] or 'euclidean' in meta['k-nn Metric'] or 'l2' in meta['k-nn Metric']:
            label_filter.append(False)
        else:
            label_filter.append(True)
            if not meta['Other Information']:
                matrix_labels.append((meta['Embedding Algorithm'], '', 'knn: ' + meta['k-nn Metric'], meta['Run Number']))
            elif 'arpack' in meta['Other Information']:
                matrix_labels.append((meta['Embedding Algorithm'], 'arpack', 'knn:' + meta['k-nn Metric'], meta['Run Number']))
            elif 'randomized' in meta['Other Information']:
                matrix_labels.append((meta['Embedding Algorithm'], 'randomized', 'knn: ' + meta['k-nn Metric'], meta['Run Number']))
            elif 'cosine' in meta['Other Information']:
                matrix_labels.append((meta['Embedding Algorithm'], 'cosine', 'knn: ' + meta['k-nn Metric'], meta['Run Number']))
            else:
                matrix_labels.append((meta['Embedding Algorithm'], '', 'knn: ' + meta['k-nn Metric'], meta['Run Number']))

    for i, label in enumerate(matrix_labels):
        if 'minkowski' in label[2]:
            matrix_labels[i] = (label[0], label[1], label[2].replace('minkowski', 'euclidean'), label[3])

    # create a permutation to group like with like
    perm_to_sort = [matrix_labels.index(tup) for tup in sorted(matrix_labels)]

    # simplify the labels for easier reading
    if knn:
        simple_labels = [(x, y, z) for x, y, z, _ in np.array(matrix_labels)[perm_to_sort]]
    else:
        simple_labels = [(x, y) for x, y, _, _ in np.array(matrix_labels)[perm_to_sort]]
        
    return simple_labels, label_filter, perm_to_sort
def display_labels(labels):
    return [' '.join(x) for x in labels]
jac_labels, jac_label_filter, jac_perm_to_sort = simplified_matrix_labels(jac_metadata, knn=False)
plt.figure(figsize=(16, 12))
plt.title("Global Jaccard Similarity Scores")
sns.heatmap(jac_results_mean[jac_label_filter,][:,jac_label_filter][jac_perm_to_sort,][:,jac_perm_to_sort], vmin=0, cmap='Blues',
            xticklabels=display_labels(jac_labels), yticklabels=display_labels(jac_labels));<jupyter_output><empty_output><jupyter_text>For completeness, let's check the variance as well:<jupyter_code>plt.figure(figsize=(16, 12))
sns.heatmap(jac_results_variance[jac_label_filter,][:,jac_label_filter][jac_perm_to_sort,][:,jac_perm_to_sort], cmap='Blues',
            xticklabels=display_labels(jac_labels), yticklabels=display_labels(jac_labels));
plt.title("Jaccard Similarity Variance", loc='center');<jupyter_output><empty_output><jupyter_text>The variance between scores of neighbourhoods is extremely low. We won't check it again as it is typically very low.  Adapted Kendall-Tau Similarity ScoresNext up, adapted Kendall-Tau scores!<jupyter_code>akt_labels, akt_label_filter, akt_perm_to_sort = simplified_matrix_labels(akt_metadata, knn=False)
plt.figure(figsize=(16, 12))
plt.title("Global Adapted Kendall-Tau Similarity Scores")
sns.heatmap(akt_results_mean[akt_label_filter,][:,akt_label_filter][akt_perm_to_sort,][:,akt_perm_to_sort], vmin=0,
            cmap='Blues', xticklabels=display_labels(akt_labels), yticklabels=display_labels(akt_labels));<jupyter_output><empty_output><jupyter_text>Every embedding techniqe seems to be similar to itself, and not at all similar to the other techniques. However, out of all the comparisons across techniques, eigenwords and PMI+SVD are the most similar.  This suggests that PMI+SVD using arpack and eigenwords are the most stable, with PMI+SVD randomized somewhat less stable, and fasttext is the most unstable, but is still comparable.   How about the difference between the two different similarity scores?The adapted Kendall-Tau similarity score is higher than the Jaccard. Let's see how much they differ.<jupyter_code>plt.figure(figsize=(16, 12))

sns.heatmap(akt_results_mean[akt_label_filter,][:,akt_label_filter][akt_perm_to_sort,][:,akt_perm_to_sort]-jac_results_mean[jac_label_filter,][:,jac_label_filter][jac_perm_to_sort,][:,jac_perm_to_sort], vmin=0,
               vmax=1, cmap='Blues', xticklabels=display_labels(akt_labels), yticklabels=display_labels(akt_labels));
plt.title("Difference of Jaccard and Adapted Kendall-Tau Similarity Scores", loc='center');
print("Maximum difference between the similarity scores: {}".format(np.max(akt_results_mean[akt_label_filter,][:,akt_label_filter][akt_perm_to_sort,][:,akt_perm_to_sort]-jac_results_mean[jac_label_filter,][:,jac_label_filter][jac_perm_to_sort,][:,jac_perm_to_sort])))<jupyter_output><empty_output><jupyter_text>In general, the Kendall-Tau score is greater than the Jaccard score. This suggests that within the neighbours that match, order is preserved enough to contribute noticeably to the Kendall-Tau score. Since the Jaccard takes about 30x longer to compute than adapted Kendall-Tau (serially) and is quite fast, it may be worth simply using Jaccard by default in general for computing a neighbourhood similarity score.  What happens as k varies?In the single comparison situation, we saw that Jaccard was more sensitive in the beginning than adapted Kendall-Tau, and it is also more sensitive to "leaving a local neighbourhood". When we did the pairwise comparison above, we only used k=100. Let's check the effect on these pairwise comparisons as k varies. There are two main questions here: * How local is local for the various methods? What size of k is too small? What size of k is too large?* What accounts for the difference between adapted Kendall-Tau and Jaccard similarity as k varies? Do we see the same picture as we saw for individual words above on a global level, where we match for a while and then start adding new elements that don't match once we get out of the local neighbourhoods.<jupyter_code>## Helper function to select off indices that we want for various stories and pictures
def get_subselected_indices(alg, knn_metric, labels):
    value_filter = [alg in " ".join(label) and knn_metric in label[2] for label in labels]
    return np.where(value_filter)[0]<jupyter_output><empty_output><jupyter_text>Similarity scores as k-varies comparing runs of an algorithm against itself<jupyter_code>algs = ['randomized', 'arpack', 'eigenwords', 'fasttext', 'GloVe']
knn_metrics = ['cosine']
similarity_metrics = ['akt', 'jac']
%%time
max_k = 100

self_labels = {}
self_scores = {}
self_comparisons = {}
filenames = []
for alg in algs:
    for knn_metric in knn_metrics:
        for similarity_metric in similarity_metrics:
            filename = "k_{}_comparisons_{}_{}_{}".format(similarity_metric, alg, knn_metric, max_k)
            filenames.append(filename)
            
for filename in tqdm.tqdm(filenames):
        comparisons, metadata = embed.read_comparisons(filename, data_path=data_path)
        _, score, _ = embed.aggregate_comparison_stats(comparisons, max_k=max_k)
        simple_labels, label_filter, perm_to_sort = simplified_matrix_labels(metadata, knn=True)
        perm_score = score[label_filter,][:,label_filter][perm_to_sort,][:,perm_to_sort]
        self_labels[filename] = simple_labels
        self_scores[filename] = perm_score
        self_comparisons[filename] = comparisons
knn_metric = 'cosine'
size = 6
width = 2 # number of plots to use across the screen

plt.figure(figsize=(20,40))

# color akt and jaccard differently
colors = {}
colors['akt'] = sns.color_palette("bright", 10)
colors['jac'] = sns.color_palette("husl", 10)

plot_num = 0
for alg in algs:
    plot_num += 1
    plt.subplot(int(size/width)+width, width, plot_num)
    for similarity_metric in similarity_metrics:
        filename = "k_{}_comparisons_{}_{}_{}".format(similarity_metric, alg, knn_metric, max_k)
        indices = get_subselected_indices(alg, knn_metric, self_labels[filename])
        color_index = 0
        for m in indices:
            for n in indices:
                if m < n:
                    color = colors[similarity_metric][color_index]
                    plt.plot(self_scores[filename][m, n], label="{}: {} vs. {}".format(similarity_metric, m, n),
                             c=color)
                    color_index += 1
                    plt.ylim(ymin=0.5, ymax = 1.01)

    plt.title("{} with knn metric {}".format(alg, knn_metric))
    plt.legend()
    plt.xlabel('k')
    plt.ylabel('Similarity')
    plt.xlim(xmin=0, xmax=max_k-1)<jupyter_output><empty_output><jupyter_text>Here we see that in each case, once k is large enough, say k=20, the neighbourhood similarity score is very stable, and in most cases slightly increasing with k. Furthermore, there is a constant difference between the Jaccard and adapted Kendall-Tau scores.   Between algorithm comparisons while varying kNow, all of these embedding techniques so far are fairly stable against themselves. Let's see what happens when we compare embeddings across techniques, as those embeddings show a lot more variation.Here, we'll only take one embedding per algorithm, as all the algorithms are fairly stable.<jupyter_code>%%time
max_k = 100

across_labels = {}
across_scores = {}
across_comparisons = {}

knn_metric = 'cosine'
for similarity_metric in similarity_metrics:
    filename = "k_{}_comparisons_across_algs_{}_{}".format(similarity_metric, knn_metric, max_k)
    #print(filename)
    comparisons, metadata = embed.read_comparisons(filename, data_path=data_path)
    _, score, _ = embed.aggregate_comparison_stats(comparisons, max_k=max_k)
    simple_labels, label_filter, perm_to_sort = simplified_matrix_labels(metadata, knn=False)
    perm_score = score[label_filter,][:,label_filter][perm_to_sort,][:,perm_to_sort]
    across_labels[filename] = simple_labels
    across_scores[filename] = perm_score
    across_comparisons[filename] = comparisons
knn_metric = 'cosine'

size = 2
width = 2 # number of plots to use across the screen

plt.figure(figsize=(15,20))
plot_num = 0

for similarity_metric in similarity_metrics:
    plot_num += 1
    plt.subplot(int(size/width)+width, width, plot_num)
    filename = "k_{}_comparisons_across_algs_{}_{}".format(similarity_metric, knn_metric, max_k)

    indices = range(len(across_scores[filename]))
    color_index = 0
    for m in indices:
        for n in indices:
            if m < n:
                color = sns.color_palette("bright", 10)[color_index]
                plt.plot(across_scores[filename][m, n], 
                         label="{} vs. {}".format(' '.join(across_labels[filename][m]),
                                                  ' '.join(across_labels[filename][n])),
                         c=color)
                color_index += 1
    plt.title("Across algorithm comparisons as k varies with {}".format(similarity_metric))
    plt.legend()
    plt.xlabel('k')
    plt.ylabel('Similarity')

    plt.xlim(xmin=0, xmax=max_k-1);<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0949025350050334, 'fraction_numerical': 0.00970074128306031, 'mean_word_length': 5.343266253869969, 'pattern_counts': {'":': 0, '<': 138, '<?xml version=': 0, '>': 134, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '33', 'dir': 'jupyter-structured-clean-dedup', 'id': '285723', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 10360, 'n_tokens_neox': 9648, 'n_words': 3242, 'path': 'Vector Space Embeddings.ipynb', 'repo_name': 'acwooding/embedding_similarity', 'size': '32792'}