写在前面：这是本人第一篇认真梳理并分享给大家的论文阅读笔记，内容均为个人理解，希望对你有帮助噢(oﾟvﾟ)ノ
原文地址：http://www.vldb.org/pvldb/vol11/p1454-ebraheem.pdf
目录
- Motivation：论文想要解决的问题
- Methodology：本文提出的方法
- experiment：实验结果
Motivation
Entity resolution (ER) 是数据集成的一个基础问题，已经有70多年的研究历史，包括许多方法：启发式规则、机器学习（ML）、众包等。
什么是ER？
举个简单的例子：有两张表T1和T2，每张表里面有一些商品的名称。T1里面有一条数据为“iphone”，T2里面有一条数据为“苹果手机”，事实上他们指的是同一件事物，如何将这些具有不同名称的同一事物匹配起来，就是ER研究的问题。
一个典型的ER 工作流程：
step1：使用标注数据集（简记为L）训练一个分类器classification
step2：在未标注数据集（简记为UL）上做blocking（不理解什么是blocking？没关系，后文会介绍什么是blocking，可以理解成将UL分成很多小集合block-1，block-2，......，block-k）
step3：在每个block里面组成pair<t1,t2>，使用classification预测pair，并打上标签（1：相同、0：不同）
存在的问题：
- 每一个环节都需要人的参与，很烦
- 专家定义的blocking规则只考虑到数据的部分特征（例如t1有两个属性<年龄，性别>，专家定义的blocking规则只考虑了年龄，没有考虑性别）
本文提出的解决方法：
- 使用distributed representations（DRs，其实就是我们常说的embedding）表示表里面的每个tuple，本文提出了tuple的embedding表示方法。
- 提出了全自动的blocking方法，不需要人工定义blocking规则。
- 本文说自己的贡献可以减少数据的标注，但我在原文中没看出哪里体现减少标注的功能（欢迎评论区补充，蟹蟹(ง •_•)ง）......
Methodology
1. tuple的DRs表示方法
本文提出生成tuple的embedding的两种方法：简单方法和基于LSTM的方法。
首先介绍 Word Embedding
每个词语表示成一个d维的向量，向量之间的距离（eg.欧氏距离）可以体现两个词语的相似程度，例如distance(cat,dog)<distance(cat,sky)。目前已经有预训练好的模型，可以直接拿到我们需要的词语的embedding，例如 GloVe（将每个词表示为300维的向量），本文就是使用了Glove。（下面是Word Embedding的示例，每个词语被转化为一个向量）
然后生成 Tuple Embedding
1）简单方法
下图是tuple的示例：一行tuple有两个属性，每个属性里面有一个或多个词语。
t1的embedding表示为“Bill”的embedding和“Gates”的embedding的均值，拼接上“Seattle”的embedding。所以每个tuple的embedding的维度是d*m（d是Word Embedding的维度，m属性的数目）
2）LSTM方法
如下图，将Word Embedding过一个LSTM模型生成最后的x维向量，此处不详细介绍LSTM了（展开说就太多了），知道此处是将tuple转化为一个x维向量就行。
2. 如何构建分类器？
下面是本文分类器的流程图，使用t1和t2的embedding计算相似度，再将相似度输入模型（例如SVM，决策树等简单模型），训练一个二分类器即可。
Similarity的计算：
1）本文定义了简单的计算规则
- tuple embedding是d*m维：计算t1和t2对应属性的cos相似度，则similarity是一个m维向量。
- tuple embedding是x维：直接将t1和t2相减，similarity是一个x维向量。
上图中，可以只训练到similarity层，前面的那些部分都使用上文定义的方法固定生成。也可以训练到Word Embedding层，不适用固定的tuple embedding生成方法和similarity计算方法。
至此，整个分类器就讲完了。上文t1和t2是两张表的完全组合，这样pair太多了（如果每张表有n个tuple，则总共有n*n个pair需要过分类器），如何减少pair，是blocking需要解决的问题。
3. Blocking：LSH（局部敏感哈希）
此处使用LSH来做blocking，这并不是新方法，只是本文第一次将其放到一个完整ER流程来实现。
blocking的目的：将尽量相似的tuple放到一个block里面，仅在block里面组成pair，放到classification里面预测。不同block里面的tuple默认为不相同。
Input：一张表T，具有n和tuple
Output：每个tuple被分配到1个哈希码（是一个k维向量），具有相同哈希码的tuple表示处于同一个block。
前提：相似的tuple有很大概率会映射到相同的block。
哈希过程：有k个哈希函数,每个函数将t映射为0/1，k个结果拼接为k维。（把这样一轮映射的结果定义为一张哈希表）
发现：如果k太小，会有很多无关的tuple映射到相同的block，起不到筛选的作用。如果k太大，可能会有相同的tuple（记为matching tuple）映射到不同的block[1]。
解决[1]：定义多张哈希表，使用另一组哈希函数，也许可以把漏掉的matching tuple映射到同一个block，从而不漏掉他们，提升recall。
举例：k=4，t1的embedding是[0.45,0.8,0.85]，h1=[-1,1,1]，h2=[1,1,1]，h3=[-1,-1,1]，h4=[-1,1,-1]，则t1和每个h点成后的结果是[0.86,1.53,-0.26,-0.39]，我们规定>0取1，<0取-1，则t1的哈希码是[1,1,-1,-1]。
experiment
本文使用了6个基础数据集：
在每个数据集上不同算法的性能如下图，DeepER还是不错的：
本文还有其他很多实验，验证了论文中的一些假设，想了解更多细节的朋友可以看论文，如果只关注ER效果，到这里就够了。
以上仅为个人读论文的体会，如有偏颇，欢迎指正！
