寫在前面：這是本人第一篇認真梳理并分享給大家的論文閱讀筆記市咆，內(nèi)容均為個人理解犁享，希望對你有幫助噢(o?v?)ノ

原文地址：http://www.vldb.org/pvldb/vol11/p1454-ebraheem.pdf

????????舉個簡單的例子：有兩張表T1和T2，每張表里面有一些商品的名稱湘换。T1里面有一條數(shù)據(jù)為“iphone”宾舅，T2里面有一條數(shù)據(jù)為“蘋果手機”统阿，事實上他們指的是同一件事物，如何將這些具有不同名稱的同一事物匹配起來筹我，就是ER研究的問題扶平。

一個典型的ER 工作流程：

step1：使用標(biāo)注數(shù)據(jù)集（簡記為L）訓(xùn)練一個分類器classification

step2：在未標(biāo)注數(shù)據(jù)集（簡記為UL）上做blocking（不理解什么是blocking？沒關(guān)系蔬蕊，后文會介紹什么是blocking结澄，可以理解成將UL分成很多小集合block-1，block-2岸夯，......麻献，block-k）

step3：在每個block里面組成pair<t1,t2>，使用classification預(yù)測pair猜扮，并打上標(biāo)簽（1：相同勉吻、0：不同）

存在的問題：

- 每一個環(huán)節(jié)都需要人的參與，很煩

- 專家定義的blocking規(guī)則只考慮到數(shù)據(jù)的部分特征（例如t1有兩個屬性<年齡旅赢，性別>齿桃，專家定義的blocking規(guī)則只考慮了年齡，沒有考慮性別）

本文提出的解決方法：

- 使用distributed representations（DRs煮盼，其實就是我們常說的embedding）表示表里面的每個tuple短纵，本文提出了tuple的embedding表示方法。

- 提出了全自動的blocking方法僵控，不需要人工定義blocking規(guī)則香到。

- 本文說自己的貢獻可以減少數(shù)據(jù)的標(biāo)注，但我在原文中沒看出哪里體現(xiàn)減少標(biāo)注的功能（歡迎評論區(qū)補充报破，蟹蟹(? ?_?)?）......

Methodology

1.? tuple的DRs表示方法

????????本文提出生成tuple的embedding的兩種方法：簡單方法和基于LSTM的方法养渴。

首先介紹 Word Embedding

????????每個詞語表示成一個d維的向量，向量之間的距離（eg.歐氏距離）可以體現(xiàn)兩個詞語的相似程度泛烙，例如distance(cat,dog)<distance(cat,sky)。目前已經(jīng)有預(yù)訓(xùn)練好的模型翘紊，可以直接拿到我們需要的詞語的embedding蔽氨，例如 GloVe（將每個詞表示為300維的向量），本文就是使用了Glove帆疟。（下面是Word Embedding的示例鹉究，每個詞語被轉(zhuǎn)化為一個向量）

然后生成 Tuple?Embedding

1）簡單方法

下圖是tuple的示例：一行tuple有兩個屬性，每個屬性里面有一個或多個詞語踪宠。

????????t1的embedding表示為“Bill”的embedding和“Gates”的embedding的均值自赔，拼接上“Seattle”的embedding。所以每個tuple的embedding的維度是d*m（d是Word Embedding的維度柳琢，m屬性的數(shù)目）

2）LSTM方法

????????如下圖绍妨，將Word Embedding過一個LSTM模型生成最后的x維向量润脸，此處不詳細介紹LSTM了（展開說就太多了），知道此處是將tuple轉(zhuǎn)化為一個x維向量就行他去。

2.? 如何構(gòu)建分類器毙驯？

????????下面是本文分類器的流程圖，使用t1和t2的embedding計算相似度灾测，再將相似度輸入模型（例如SVM爆价，決策樹等簡單模型），訓(xùn)練一個二分類器即可媳搪。

Similarity的計算：

1）本文定義了簡單的計算規(guī)則

- tuple embedding是d*m維：計算t1和t2對應(yīng)屬性的cos相似度铭段，則similarity是一個m維向量。

- tuple embedding是x維：直接將t1和t2相減秦爆，similarity是一個x維向量序愚。

????????上圖中，可以只訓(xùn)練到similarity層鲜结，前面的那些部分都使用上文定義的方法固定生成展运。也可以訓(xùn)練到Word Embedding層，不適用固定的tuple embedding生成方法和similarity計算方法精刷。

????????至此拗胜，整個分類器就講完了。上文t1和t2是兩張表的完全組合怒允，這樣pair太多了（如果每張表有n個tuple埂软，則總共有n*n個pair需要過分類器），如何減少pair纫事，是blocking需要解決的問題勘畔。

3. ? Blocking：LSH（局部敏感哈希）

????????此處使用LSH來做blocking，這并不是新方法丽惶，只是本文第一次將其放到一個完整ER流程來實現(xiàn)炫七。

????????blocking的目的：將盡量相似的tuple放到一個block里面，僅在block里面組成pair钾唬，放到classification里面預(yù)測万哪。不同block里面的tuple默認為不相同。

Input：一張表T抡秆，具有n和tuple

Output：每個tuple被分配到1個哈希碼（是一個k維向量）奕巍，具有相同哈希碼的tuple表示處于同一個block。

前提：相似的tuple有很大概率會映射到相同的block儒士。

哈希過程：有k個哈希函數(shù) $h1,...,h_k$ ,每個函數(shù)將t映射為0/1的止，k個結(jié)果拼接為k維。（把這樣一輪映射的結(jié)果定義為一張哈希表）

發(fā)現(xiàn)：如果k太小着撩，會有很多無關(guān)的tuple映射到相同的block诅福，起不到篩選的作用匾委。如果k太大，可能會有相同的tuple（記為matching tuple）映射到不同的block[1]权谁。

解決[1]：定義多張哈希表剩檀，使用另一組哈希函數(shù)，也許可以把漏掉的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點成后的結(jié)果是[0.86,1.53,-0.26,-0.39]锈锤，我們規(guī)定>0取1怕品，<0取-1，則t1的哈希碼是[1,1,-1,-1]。

experiment

本文使用了6個基礎(chǔ)數(shù)據(jù)集：

在每個數(shù)據(jù)集上不同算法的性能如下圖，DeepER還是不錯的：

本文還有其他很多實驗尝艘，驗證了論文中的一些假設(shè)，想了解更多細節(jié)的朋友可以看論文姿染，如果只關(guān)注ER效果背亥，到這里就夠了。

以上僅為個人讀論文的體會悬赏，如有偏頗狡汉，歡迎指正！

閱讀筆記1：（DeepER）Distributed Representations of Tuples for Entity Resolution

閱讀筆記1：（DeepER）Distributed Representations of Tuples for Entity Resolution

目錄

Motivation

什么是ER淘邻？

一個典型的ER 工作流程：

Methodology

1.? tuple的DRs表示方法

experiment