炼丹秘术：给Embedding插上翅膀
作者：DOTA，炼丹笔记
在实践中，推荐系统利用Deep Learning去生成Embedding，然后通过Embedding在召回层进行召回是一种常用的方法，而且这种方法在效果和响应速度上也不比多路召回差。
同时，在局部敏感哈希方法快速近邻计算的加持下，Embedding表现亮眼，本文作为“炼丹知识点”系列的第6期，我们来聊一聊到底Embedding的相关知识点。
炼丹知识点 往期回顾
什么是局部敏感哈希?
局部敏感哈希，英文locality-sensetive hashing，常简称为LSH。主要运用到高维海量数据的快速近似查找，近似查找便是比较数据点之间的距离或者是相似度。主要思想是，高维空间中，两点若距离很近，那么设计一种哈希函数对这两点进行哈希值计算，使得他们哈希值有很大的概率是一样的。同时若两点之间的距离较远，他们哈希值相同的概率会很小。
怎么实现局部敏感哈希？
01
Document shingles
def shingle_document(string, k):
import binascii
# initialize set data structure
set_data_structure=set()
# for each position in string, extract substring of length k
for i in range (len(string)-k+1):
substring_length_k=string[i:i+k]
# hash into 32-bit integer
hash_substring=binascii.crc32( substring_length_k.encode())
# insert into set
set_data_structure.add(hash_substring)
return (set_data_structure) 02
Jaccard Similarity
def jaccard(a, b):
# compute union size
union_size = len(set(a).union(set(b)))
# compute intersection size
intersection_size=len(set(a).intersection(set(b)))
# return ratio of union and intersection
return 1.0*intersection_size/union_size03
Jaccard Documents
def jaccard_of_documents(file_name, k):
array_of_documents_tuples=parse_data (file_name)
array_of_jaccard_tuples=[]
for i in range(len(array_of_documents_tuples)):
for j in range (i+1, len(array_of_documents_tuples)):
a=shingle_document(array_of_documents_tuples[i][1], k)
b=shingle_document(array_of_documents_tuples[j][1], k)
jaccard_similarity = jaccard(a,b)
jaccard_tuples = (array_of_documents_tuples[i][0],array_of_documents_tuples[j][0],jaccard_similarity)
if jaccard_similarity>=0.8:
print (jaccard_tuples)
array_of_jaccard_tuples+=[jaccard_tuples]
return array_of_jaccard_tuples04
MinHash
def invert_shingles(shingled_documents):
# initialize list for tuples
list_of_tuples = []
# initialize list for document ids
list_of_documentid = []
# for each document in input
for shingled_document in shingled_documents:
# append document id to list
list_of_documentid.append(shingled_document[0])
# for each item in document
for item in shingled_document[1]:
# append (item, docid) tuple
list_of_tuples.append((item,shingled_document[0]))
# sort tuple list
list_of_tuples.sort()
# return sorted tuple list, and document list
return list_of_tuples, list_of_documentid
05
Generate hash functions
def make_hashes(num_hashes):
list_of_hash_fn=[]
for i in range(num_hashes):
list_of_hash_fn.append(make_random_hash_fn())
return list_of_hash_fn 06
Minhash Signature Matrix
def make_minhash_signature(shingled_data, num_hash):
inv_index, docids = invert_shingles(shingled_data)
num_docs = len(docids)
# initialize the signature matrix with infinity in every entry
sigmatrix = np.full([num_hash, num_docs], np.inf)
# generate hash functions
hash_funcs = make_hashes(num_hash)
# iterate over each non-zero entry of the characteristic matrix
for row, docid in inv_index:
# update signature matrix if needed
# THIS IS WHAT YOU NEED TO IMPLEMENT
for row1 in range(num_hash):
sigmatrix[row1,docids.index(docid)]=min(sigmatrix[row1,docids.index(docid)],hash_funcs[row1](row))
return sigmatrix, docids 07
MinHash similarity estimate
def minhash_similarity(id1, id2, minhash_sigmat, docids):
# get column of the similarity matrix for the two documents
index_id1=docids.index(id1)
index_id2=docids.index(id2)
# calculate the fraction of rows where two columns match
minhash_similarity_estimate= np.mean(minhash_sigmat[:, index_id1]==minhash_sigmat[:, index_id2])
# return this fraction as the minhash similarity estimate
return minhash_similarity_estimate 工业界怎么用Embedding？
对于电商平台而言，商品搜索服务已经是人们日常购物中重中之重的服务了，商品的召回决定了搜索系统的质量。商品搜索需要从一个巨大的语料库中找到最相关的商品，同时还要保证个性化。系统的表现主要受到搜索query和召回商品相关性，还有训练和预估不一致的影响。这篇论文就提出了一种多粒度的深度语义召回系统，保证了训练预估一致性，并使用softmax cross-entropy loss作为训练目标，使得最终召回效果更好，模型收敛速度更快。
我们先看下淘宝商品搜索系统的全貌，每个环都是一个阶段：
我们可以看到retrieval阶段有亿级别的商品，通过我们的深度语义召回系统最终召回上万个相关商品。接下来开始介绍深度语义商品召回模型，我们有用户全集U={u1,u2,...,UN}，还有query集合Q={q1, q2, ..., qN}，同时还有商品集合I={i1, i2, ..., iM}。我们把用户历史行为序列参照时间区间分到3个子集，实时集合R = {i1, i2, ..., iT}，短期集合 S = {i1, i2, ..., iT}，长期集合L = {i1, i2, ..., iT}，所以任务就是给定一个用户u的(R,S,L)，以及query，返回top-K items:
用户塔：淘宝中的query多为中文，在切词后平均长度小于3，因此我们提出了多粒度的语义单元，从不同的语义粒度挖掘query含义，提升query的表达精度。给定一个query的切词q={w1, ..., wn}(e.g. {红色，连衣裙})，每个单词可以拆成字粒度w = {c1, ..., cm}，同时我们还能拿到历史query qhis = {q1, ..., qk},所以我们可以得到6种粒度的表达：
Trm用的transformer，最后把6种粒度的embedding都concat在一起。
用户行为注意力机制: 用户历史点击购买的items，和每个item的side information，都可以通过embedding的方式将每个item都映射成固定长度的向量，这里我们用query与历史行为items做attention，找到相关items。对于实时集合，使用LSTM进行编码，然后套用个self-attention层，并在序列最前面加上0向量(以防历史行为没一个相关的)，最后用一个attention操作获得最终embedding，如下公式所示：
对于短期行为使用多头self-attention，头部添加0向量，并计算attention:
对于长期行为(一个月内)而言，分别对点击，购买，加购集合进行mean pooling，再与query进行attention：
对长期行为的item的店铺，类目，品牌做同样的操作，最后把embeding进行sum pooling:
最后再把以上所有进行融合：
商品塔：商品塔只需要把itemID和标题进行融合得到最终embedding，如下式所示:
e表示商品embedding，wi表示标题切词，wt是转移矩阵。
综上整个模型如下所示：
论文分析到hing loss只能做local的比较，由此会产生预估与训练的diff，所以该文直接用softmax cross-entropy loss，定义如下：
实践中论文使用的sampled softmax。
因为存在很多噪音数据，导致query和商品完全不相关，所以论文在softmax函数引入了一个温度:
在样本上，需要构造强负例，本文提出的强负例构造方法是在样本空间中构造，给定训练样本(qu, i+, i-)，i-是在样本池随机负采样，为了简化，i-在负样本池找到和qu点积最大的topN，并和i+进行融合成强负例，定义如下:
最终融合了强负例的softmax函数如下:
论文后面还有很多工程介绍，感兴趣可以参考原文。
参考资料
- LSH-局部敏感哈希 https://zhuanlan.zhihu.com/p/225949044
- https://github.com/elhamsharifi/Similar-Document-Searching/blob/master/Similar_Document_Searching.ipynb
- 淘宝搜索中基于embedding的召回
- https://www.zhihu.com/people/yuconan