J'ai besoin de trouver la phrase la plus proche possible. J'ai un tableau de phrases et une phrase utilisateur, et je dois trouver l'élément le plus proche de la phrase utilisateur du tableau.

J'ai présenté chaque phrase sous la forme d'un vecteur en utilisant word2vec:

def get_avg_vector(word_list, model_w2v, size=500):
    sum_vec = np.zeros(shape = (1, size))
    count = 0

    for w in word_list:
        if w in model_w2v and w != '':
            sum_vec += model_w2v[w]
            count +=1
    if count == 0:
        return sum_vec
    else:
        return sum_vec / count + 1

Par conséquent, l'élément de tableau ressemble à ceci:

array([[ 0.93162371,  0.95618944,  0.98519795,  0.98580566,  0.96563747,
         0.97070891,  0.99079191,  1.01572807,  1.00631016,  1.07349398,
         1.02079309,  1.0064849 ,  0.99179418,  1.02865136,  1.02610303,
         1.02909719,  0.99350413,  0.97481178,  0.97980362,  0.98068508,
         1.05657591,  0.97224562,  0.99778703,  0.97888296,  1.01650529,
         1.0421448 ,  0.98731804,  0.98349052,  0.93752996,  0.98205837,
         1.05691232,  0.99914532,  1.02040555,  0.99427229,  1.01193818,
         0.94922226,  0.9818139 ,  1.03955   ,  1.01252615,  1.01402485,
         ...
         0.98990598,  0.99576604,  1.0903802 ,  1.02493086,  0.97395976,
         0.95563786,  1.00538653,  1.0036294 ,  0.97220088,  1.04822631,
         1.02806122,  0.95402776,  1.0048053 ,  0.97677222,  0.97830801]])

Je représente la phrase de l'utilisateur également comme un vecteur, et je calcule l'élément le plus proche comme ceci:

%%cython
from scipy.spatial.distance import euclidean

def compute_dist(v, list_sentences):
    dist_dict = {}

    for key, val in list_sentences.items():
        dist_dict[key] = euclidean(v, val)

    return sorted(dist_dict.items(), key=lambda x: x[1])[0][0]

list_sentences dans la méthode ci-dessus est un dictionnaire dans lequel les clés sont une représentation textuelle des phrases et les valeurs sont vectorielles.

Cela prend beaucoup de temps, car j'ai plus de 60 millions de phrases. Comment accélérer, optimiser ce processus?

Je serai reconnaissant pour tout conseil.

3
Vladimir 12 avril 2018 à 16:49

3 réponses

Meilleure réponse

Le calcul initial des vecteurs de 60 millions de phrases est essentiellement un coût fixe que vous paierez une fois. Je suppose que vous vous souciez principalement du temps pour chaque recherche ultérieure, pour une seule phrase de requête fournie par l'utilisateur.

L'utilisation d'opérations de tableau natif numpy peut accélérer les calculs de distance plutôt que de faire vos propres calculs individuels dans une boucle Python. (Il est capable de faire des choses en masse en utilisant son code optimisé.)

Mais vous devez d'abord remplacer list_sentences par un vrai tableau numpy, accessible uniquement par array-index. (Si vous avez d'autres touches / textes que vous devez associer à chaque emplacement, vous le feriez ailleurs, avec un dict ou une liste.)

Supposons que vous ayez fait cela, de quelque manière que ce soit, ce qui est naturel pour vos données, et que vous avez maintenant array_sentences, un tableau numpy de 60 millions par 500 dimensions, avec un vecteur moyen de phrase par ligne.

Ensuite, un moyen à 1 ligne pour obtenir un tableau complet des distances est la longueur vectorielle ("norme") de la différence entre chacun des 60 millions de candidats et la requête 1 (qui donne une réponse d'entrée de 60 millions à chaque des différences):

dists = np.linalg.norm(array_sentences - v)  

Une autre méthode à 1 ligne consiste à utiliser la fonction utilitaire numpy cdist() pour calculer la distance entre chaque paire de deux collections d'entrées. Ici, votre première collection n'est qu'un seul vecteur de requête v (mais si vous aviez des lots à faire en même temps, fournir plusieurs requêtes à la fois pourrait offrir une légère accélération supplémentaire):

dists = np.linalg.cdists(array[v], array_sentences)

(Notez que de telles comparaisons vectorielles utilisent souvent la distance cosinus / similitude cosinus plutôt que la distance euclidienne. Si vous passez à cela, vous pourriez faire d'autres produits de normalisation / dot au lieu de la première option ci-dessus, ou utiliser le {{X0 }} option pour cdist().)

Une fois que vous avez toutes les distances dans un tableau numpy, l'utilisation d'une option de tri natif numpy sera probablement plus rapide que l'utilisation de Python sorted(). Par exemple, le tri indirect de argsort(), qui renvoie simplement les index triés (et évite ainsi de déplacer toutes les coordonnées vectorielles), car vous voulez juste savoir quels éléments sont la meilleure correspondance (es). Par exemple:

sorted_indexes = argsort(dists)
best_index = sorted_indexes[0]

Si vous devez rétablir cet index int dans votre autre clé / texte, vous utiliserez votre propre dict / list qui se souviendra des relations slot-to-key.

Tout cela donne toujours un résultat exact, en se comparant à tous les candidats, ce qui (même lorsqu'il est bien fait de manière optimale) prend encore beaucoup de temps.

Il existe des moyens d'obtenir des résultats plus rapides, basés sur des index de pré-construction pour l'ensemble complet des candidats - mais de tels index deviennent très délicats dans les espaces de grande dimension (comme votre espace de 500 dimensions). Ils échangent souvent des résultats parfaitement précis pour des résultats plus rapides. (Autrement dit, ce qu'ils renvoient pour «1 le plus proche» ou «N le plus proche» comportera quelques erreurs, mais ne sera généralement pas désactivé de beaucoup.) Pour des exemples de telles bibliothèques, voir ANNOY de Spotify ou FAISS de Facebook.

2
gojomo 12 avril 2018 à 18:23

Au moins, si vous effectuez cette procédure pour plusieurs phrases, vous pouvez essayer d'utiliser scipy.spatial.cKDTree (je ne sais pas si cela se paie par lui-même sur une seule requête. Aussi 500 est assez élevé, il me semble rappelez-vous que KDTrees fonctionne mieux pour pas autant de dimensions (vous devrez expérimenter).

En supposant que vous avez mis tous vos vecteurs (valeurs dict) dans un grand tableau numpy:

>>> import numpy as np
>>> from scipy.spatial import cKDTree as KDTree
>>>
# 100,000 vectors (that's all my RAM can take)
>>> a = np.random.random((100000, 500))
>>>
>>> t = KDTree(a)
# create one new vector and find distance and index of closest
>>> t.query(np.random.random(500))
(8.20910072933986, 83407)
2
Paul Panzer 12 avril 2018 à 14:27

Je peux penser à 2 façons possibles d'optimiser ce processus.

Premièrement, si votre objectif est uniquement d'obtenir le vecteur (ou la phrase) le plus proche, vous pouvez vous débarrasser de la variable list_sentences et ne garder en mémoire que la phrase la plus proche que vous avez trouvée. De cette façon, vous n'aurez pas besoin de trier la liste complète (et probablement très grande) à la fin, et de ne renvoyer que la plus proche.

def compute_dist(v, list_sentences):
    min_dist = 0

    for key, val in list_sentences.items():
        dist = euclidean(v, val)
        if dist < min_dist:
            closest_sentence = key
            min_dist = dist

    return closest_sentence

La seconde est peut-être un peu plus malsaine. Vous pouvez essayer de réimplémenter la méthode euclidean en lui donnant un troisième argument qui serait la distance minimale actuelle min_dist entre le vecteur le plus proche que vous avez trouvé jusqu'à présent et le vecteur utilisateur. Je ne sais pas comment la méthode scipy euclidean est implémentée mais je suppose qu'elle est proche de la somme des différences quadratiques le long de toutes les dimensions des vecteurs. Ce que vous voulez, c'est que la méthode s'arrête si la somme est supérieure à min_dist (la distance sera de toute façon supérieure à min_dist et vous ne la conserverez pas).

2
EtienneG 12 avril 2018 à 15:50