DEIM Forum 2023 2a-6-2

公理系を用いた Human-in-the-loop エンティティマッチング
小泉 崇裕†

伊藤 寛祥††

吉本 龍司†††

福島 幸宏††††

原田 隆史†††††

森嶋 厚行††† 筑波大学 情報学群 情報メディア創成学類 〒 305–0821 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系 〒 305–0821 茨城県つくば市春日 1–2††† 株式会社カーリル 〒 509–9232 岐阜県中津川市坂下 1645–15†††† 慶應義塾大学 文学部 〒 108–8345 東京都港区三田 2–15–45††††† 同志社大学 免許資格課程センター 〒 602–8580 京都府京都市上京区今出川通新町上ル
E-mail: †koizumi.takahiro.qg@alumni.tsukuba.ac.jp, ††{ito,mori}@slis.tsukuba.ac.jp, †††ryuuji@calil.jp,††††fukusima-y@keio.jp, †††††ushi@slis.doshisha.ac.jp
あらまし エンティティマッチングは，データベースの中から同一実体を参照するレコードの統合を行う問題として広く知られる．この課題へのアプローチに，機械学習とクラウドソーシングを掛け合わせた Human-in-the-loop による
レコードペアの同定を行う手法がある．既存手法では，機械学習における判断の確信度が低い場合に人間の判断を仰ぐ手法が一般的であった．本研究では，機械学習における判断とエンティティマッチングにおける公理の矛盾を手がかりに人間に判断を求める手法を提案する．また，そのデータを教師データとして再学習させることで，同定精度をより高める事を試みる．全国 963 の公立図書館の書誌データの一部を用いた実験により，提案手法の効果を確認した．
キーワード エンティティマッチング，公理系，Human-in-the-loop，データ統合技術

1 はじめに複数のデータベースを統合する際に，各データベースに格納

3. 公理矛盾の検知されるレコード間で互いに識別可能な固有番号がないことが×

しばしばある．この状態で単純に結合してしまうと，重複した

2. 距離学習によるグラフ構築

レコードが格納され，データの実情把握や情報検索の観点で不++利になることが予想される．この問題は，同じ実体を参照する
レコードを，項目内容の比較により発見し統合する「エンティティマッチング問題」として広く研究されている．
エンティティマッチングには，データ規模が大きくなると計

4. 人間による修正

1. レコード

5. 教師データに追加

図 1

提案フレームワークの概要: 公理系によって AI の推論の矛盾を発見し，人間が修正したものを再度 AI の学習に用いる Human-in-

the-Loop のフレームワークを提案する

算機の誤判定とクラウドソーシングコストが急増するという問題がある．一般にエンティティマッチングは組み合わせの問題

ンティティマッチングにおける公理系との矛盾を手がかりに人であるから，n 個の同定対象データが k 倍になると比較対象と間の判断を求める手法を提案する．また，そのデータを教師なるペアは kn C2 となり k 2 オーダーで増加する．

データとして再学習させることで，学習精度をより高める事を

エンティティマッチングの問題は長年の研究にも関わらず，試みる．公理系に矛盾したグループは，推論器が誤判定したペ依然として困難な問題として指摘 [1] されており，当初は計算アが確実に含まれていることから，再学習に対し価値の高い機のみで解決を図る手法 [2] [3] が研究されてきたが，その困難

データと考えられる．このグループをクラウドソーシングで問さから，Human-in-the-loop を用いた手法の研究が近年盛んにい合わせることで，信頼性の高いデータを獲得することができ，行われている．Human-in-the-loop とは，各々得意とするタス

このデータを教師データとして推論器にフィードバックするこ

クを計算機と人間に割り当てて相互補完しながら動作するシスとで，既存モデルとの差異が減少し，より精度の高い推論を行テムのことを指し，機械学習とクラウドソーシングの組み合わえることが期待できる．

せで注目を集めている．例えば，固有番号のないペアのみクラ

図 1 に，本研究の新規性にあたるフィードバックループを示

ウドソーシングを行う手法 [4] が提案されており，また，機械す．従来手法で実装された「学習フェーズ」と「同定フェーズ」

学習での判定をベースに，確信度が低いデータペアを人間が修に加えて，公理による推論機の誤判定を自己検出する「公理矛正することで，コストを抑えつつ高精度なエンティティマッチ

盾検出フェーズ」と，そのデータを推論器にフィードバックすングを実現する手法 [5] [6] が提案されている．

る「再学習フェーズ」を追加した図 2 の手法を提案する．

本研究では，既存研究と異なり，機械学習における判断とエ

本研究は，データの規模を大きくした場合に再学習が与える機械学習層

依頼主
ドグラマグラ 1935
ドグラ・マグラ日蝕1998.8

Mistake...

but I cannot fix them.

夢野久作
夢野久作/著
平野啓一郎

1. データ集合 を入力する

3. 推論器の誤判定を公理系の矛盾により検知しクラウドソーシングで問い合わせる

2. 機械学習により候補ペアの枝刈りを行い近傍グラフ を構築する

計算機だけでは判定できないペア
ペアに対する回答

6.1. 近傍グラフを再構築し同定処理を行う
図2

本研究の貢献公理系矛盾検出と再学習による同定手法の提案: エンティ
ティマッチングのドメインの公理系との矛盾による学習
データの獲得を試みる手法を提案している．

•

6.2. 計算機が不明(Unknown)と判定したペアを人間が判定する

提案手法概略

推論器精度の影響の検証を目的とした実験を行った．

•

4. 計算機の判定では公理に矛盾したグループを人間が修正する修正されたペア

5. 矛盾したグループを修正するために再学習する

7. グループ化が完了した同定結果を得る

人間層(クラウドソーシング)

公理層

計算機

ると考えられる書誌ペアの特定を試み，クラウドソーシングによる該当ペアの修正と計算機による自動化手法の改善を行った．
また，類似度計算には Okapi BM25 [7] を利用した．実験の結果，8 人以上の人間の介入が行われると信頼できる結果を得られたとしている．この研究はクラウドソーシングの効果について主眼を置いているため，コストの考慮や，計算機が同定した実データによる実験: 実際の公立図書館の書誌データ統合

ペアに対する検証は行われていない．

における実験結果により，提案手法が有望であることを示

2. 3 Human-in-the-loop によるエンティティマッチング

しており，クラウドソーシングコストと精度の関係についても調査した結果を報告する．

Li [5] は，エンティティマッチングの重要な問題として，「2 つのレコードが同じ実体かを評価することは容易ではない」こと，

この成果は，比較的大きなデータ群に対し高精度かつ低コスト「レコードペアを全て確認することはコストが大きい」ことを挙にエンティティマッチングを行えることを示唆したものである．

げている．このことを踏まえ，まず大量の非一致ペアを計算機
が刈り込み，誤同定を防ぐためにクラウドソーシングを利用す

2 関連研究る．さらに，コスト減少のために公理系による推論を取り入れており，一致と考えられるペアから問い合わせることで，3 つ本章では，本研究に関連の深い研究を紹介し，その手法の問のタスクを 2 つに減少できる可能性があることに言及している．

題点や提案手法との比較について述べる．

大沢ら [6] は，距離学習による候補ペアの枝刈りとベイズ推

2. 1 計算機のみのエンティティマッチング

論，クラウドソーシングによる高精度な同定フレームワークを

エンティティマッチングの基礎として，属性値に着目したブ
ロッキング手法 [2] が提案された．ある 1 つの属性と一致しない候補を大幅に削除する手法であるが，入力ミスや欠損，表記揺れ等により，対象の属性を決めるのが難しい．
上田ら [3] は SVM(support-vector machine) を使った固有識
別情報を持たない書誌同定手法を提案しており，計算機による提案している．できる限り計算機が判定する手法で，コストを最小化する工夫も見られる．一方で，複数の評価指標を束ねる
推論方法は，評価指標が拮抗した場合に正しく判定できない問題がある．本研究では，指標が拮抗した際に値が大きくなる「Unknown(不明) 領域」を考慮した SUN 推論を提案する．

2. 4 エンティティアラインメント半教師あり学習モデル

同定および検索において精度向上を図った．この手法はデータ

Zhu ら [8] は，異なる知識グラフから同じ意味を示す実体

により向き不向きがあり，15% から 81% と F 値に揺れが見らを探す為に，半教師あり学習モデルを提案する．GCN(Graph

れる．本研究は，旧 Facebook 社が提供する Fasttext 1 から成Convolutional Networks) を利用し，エンティティとリレーショ

る特徴ベクトルを利用し，SVM ではなく距離学習を利用する．

ンのグラフ構築に対する再学習を行うことで精度向上を図った．

2. 2 クラウドソーシングを利用した書誌同定

本研究とは学習方法が異なるが，エンティティアラインメント

クラウドソーシングは，不特定多数の人にタスクを割り振るシステムのことを指す．原田ら [4] は，誤入力やデータの欠損などにより計算機だけでの自動同定処理は限界があると提起し，分野では半教師あり学習モデルの効果が示された．

3 準備

計算機が判定困難な書誌データペアを，人の介入が可能なクラ

本章では記号定義を行い，さらに提案手法の軸となる「距離ウドソーシングを活用した手法を提案した．計算機が誤判定す

学習器」と「SUN 推論器」，「近傍グラフ」について説明する．

1：https://fasttext.cc/

3. 1 記 号 定 義

距離学習器の実装にあたっては Keras 2 を利用し，3 つの全結合

本論文において使用する記号を表 1 に示す．一部の記号は

Dmatch のように添字が付されている場合があるが，添字付き記号については適宜説明する．
表1

層と 3 つのドロップアウト層により構成される．
3. 2. 2 推論

推論時に得られる 2 つのデータ間の距離は，式 (3) からユー
クリッド距離で算出できる．

記号の定義

S = {si }同定対象のターゲットデータベース

si

各データ (レコード)

D = {(si , sj )}データペア

SUN 推論器は，各類似度の確率密度関数の値を束ねて，そのT = {(si , sj , sk )}データトリオ

データペアがどの程度一致しているかを推論するものである．

M Θ : s i → Rn

距離学習による埋め込みm∈R

距離学習時の不一致ペアのためのマージンΣ ∈ RnSUN 推論器を構築するパラメータ集合

SUN 推論器の構築にあたっては，Bubble [6] の手法を参G = (V, E)

ノードとエッジで構成される近傍グラフ

考 に ，事 前 に 用 意 さ れ た 一 致・不 一 致 ペ ア の 教 師 デ ー タ

V = {vi }近傍グラフにおけるノード集合

Dmatch , Dmismatch を利用し，各類似度指標から出力される

各ノード

値を基に確率密度関数を構成するパラメータを取得する．本研

vi = (si , group : {si })(si : データ，group: 同定済データ集合)

E = {(vi , vj )}近傍グラフにおけるエッジ集合τ閾値

3. 3 SUN 推論器

3. 3. 1 学

習

究では，表 2 の類似度指標を使用する．
表2
指標

Fasttext vectorγ

距離学習によるデータ間の距離

Jaro-winkler [11]β

文字列間の置換の必要度合い

Levenshtein [12]γ

置換や削除などの編集距離

Gestalt Pattern Matching 3β

文字列長と一致文字数から算出

データとノードのインデックスは共有するものとし，si ≡vj (i = j), si ̸≡ vj (i =| j) が成り立つ.
3. 2 距離学習器

類似度指標
分布

距離学習器は，主に比較対象のペアの枝刈りを目的としており，後述する SUN 推論器の指標の 1 つとしても利用する．
3. 2. 1 学

値を一致ペアと不一致ペアに分け，β 分布または γ 分布を基と習

まずデータ si が持つ各属性値について，旧 Facebook 社が提供する Fasttext によって，各々を 300 次元のベクトルに変換する．日付など数値しか持たない属性値は，One-hot ベクトルを利用し，300 次元になるよう不足分は 0 埋めした．これらのベクトルを連結し距離学習を行う．ここで，一致ペアを含む教
師データを Dmatch ，不一致ペアを含む教師データを Dmismatchとする．
距離学習は Siamese N etwork [9] を利用し，Θ を最小化する問題として，式 (1) より定義される．

∑

Θ = arg minΘ

率密度関数へのフィッティングは scipy 4 を利用した．
2

1.5

1.5

1

1
0.5

0.5
0

0

0.2

0.4

0.6

0.8

一致ペア (Dmatch )図3

Dist1 (MΘ (si ), MΘ (sj ))Dist2 (MΘ (si ), MΘ (sj ))

(1)

1

0

0

0.2

0.4

0.6

0.8

1

不一致ペア (Dmismatch )確率密度関数へのフィッティング

損失関数には Contrasive Loss [10] を利用する．
∑
1
Loss =
Disteuc (si , sj )22(si ,sj )∈Dmatch∑

これら各々の確率密度関数を表現するためのパラメータ全てを総称して Σ とする．

(si ,sj )∈Dmismatch+

する確率密度関数へのフィッティングを図 3 のように行う．確(si ,sj )∈Dmatch∑−

教師データを入力とし，これらの各類似度指標から得られる

3. 3. 2 推

推論時は，複数の類似度指標に基づく確率密度関数の値を束ねることにより，Same 領域，U nknown 領域，N ot − samemax(m − Disteuc (si , sj ), 0)2 (si ,sj )∈Dmismatch(2)
なお Disteuc (si , sj ) は式 (3) として定義される．

Disteuc (si , sj ) = ∥MΘ (si ) − MΘ (sj )∥2

論

領域の各々の値を算出する．例えば類似度 A から得られる値
を xA とする時，一致ペアの確率密度関数の値と不一致ペアの確率密度関数の値を，それぞれ a(xA )，ā(xA ) とする (図 4)．

xA の値を取った時，類似度 a においてそのペアが一致する

2：https://keras.io/(3)

3：https://docs.python.org/3/library/diﬄib.html
4：https://scipy.org

3. 4. 2 スコアの計算

1.5

2
1.5 a(xA )スコアは，2 つのノードについて共有している接続ノードの1個数と定義する．N (vi ) ⊆ V がノード vi と接続されているノー

1
0.5
0

ド集合とするとき，式 (9) で計算される．

0.5
ā(xA )

xA
0

0.2

0.4

0.6

0.8

1

0

0

一致ペア (Dmatch )
図4

0.2

xA
0.4

0.6

0.8

Score(vi , vj ) = |N (vi ) ∩ N (vj )|1

不一致ペア (Dmismatch )(9)

3. 4. 3 縮 約 操 作

類似度指標 A において xA = 0.8 の確率密度関数の値

SUN 推論器およびクラウドソーシングによって，一致と考えれられるペアに対して縮約する．例えば (vi , vj ) が一致と考えられるペアで vi に集約する場合，まず，vi .group に vj .group

確率 Pa (xA ) を式 (4) のように定義する．

が属することを記録する．次に vj に張られているエッジを vi

Pa (xA ) =a(xA )a(xA ) + ā(xA )(4)

3. 4. 4 切 断 操 作

不一致確率も同様に定義できる．

Pā (xA ) =ā(xA )a(xA ) + ā(xA )に張り直し，ノード vj を削除する．

SUN 推論器およびクラウドソーシングによって，不一致と(5)考えれられるペアに対しては切断処理を行う．例えば (vi , vj )が一致と考えられるペアの場合，この 2 つのノードに張られた

なお， Pa (xA ) + Pā (xA ) = 1 であることに留意する．

エッジを削除する．

本研究では類似度指標を 4 つ使うため，各指標の一致確率については Pa (xA ), Pb (xB ), Pc (xC ), Pd (xD )，不一致確率は

構築

Score計算

縮約操作

切断操作

Pā (xA ), Pb̄ (xB ), Pc̄ (xC ), Pd¯(xD ) と表現できる．各指標の一致確率の積，すなわち式 (6) の値が大きくなる時，全指標において一致確率が高い時であり，これを Same 領域と定義する．

Psame = Pa (xA )Pb (xB )Pc (xC )Pd (xD )(6)

反対に不一致確率の積，式 (7) の値が大きくなる場合は，すべての指標において不一致確率が高い時であるから，これをN ot − same 領域と定義する．
Pnot same = Pā (xA )Pb̄ (xB )Pc̄ (xC )Pd¯(xD )

図5

(7)

近傍グラフの操作

Pa (xA )Pb̄ (xB )Pc (xC )Pd (xD ) のような値が大きくなる場合，A, C, D 指標の一致確率が高く，B 指標の不一致確率が高い時である．このように指標が拮抗している積の和を U nknown 領域と定義し，式 (8) が成り立つ．

Punknown = 1 − Psame − Pnot same

4 提案手法
提案手法は「学習フェーズ」「公理矛盾検出フェーズ」「再学習フェーズ」「同定フェーズ」の 4 段階のワークフローによっ(8)

U nknown 領域が大きい場合は，計算機のみでの判定が困難なペアであり，人間による介入が必要と考えられる．

て構成される．これら一連のワークフロー，Algorithm，デー
タ入出力の関係を図 6 にまとめた．図中の (∗) は，既存手法のワークフローの再現であり，再学習しない手法として比較検証時に利用する．

3. 4 近傍グラフ
近傍グラフは，データを表すノードと候補ペアを表すエッジで構成され，そのグラフを操作することで同定処理を進める．

公理矛盾検出フェーズ

学習フェーズ一致と考えられるペアを 1 つのノードに集約し，不一致と考えられるペアのエッジを切断する．エッジがなくなった段階で同定処理は終了となり，残ったノード群が同定結果となる．
3. 4. 1 構

築再学習フェーズ

同定フェーズ近傍グラフの構築時は，書誌データを全てノードとして配置
し，距離学習器で出力される距離が一定の距離よりも小さい
ノードペアに対しエッジを張る．

図6

提案ワークフロー概要

4. 1 学習フェーズ

よって，公理矛盾の可能性がある組み合わせの優先順は，SUNこ の フェー ズ で は Algorithm 1 を 基 に ，教 師 デ ー タ

Dmatch , Dmismatch を用いて，距離学習器と SUN 推論器のパ推論器が判定した Same, U nknown, N ot − same ペアをそれぞれ S, U, N と表す時，式 (10) となる．

ラメータ Θ, Σ を学習する．

S−S−N ≽S−S−U ≽S−N −U≽S−U −U ≽N −U −U ≽U −U −U

Algorithm 1 Training
Input: Same pairs (teaching data) Dmatch andNot-same pairs (teaching data) Dmismatch
Output: Metric learning parameters Θ and
SUN reasoner parameters Σ
1: Θ ← MetricLearning(Dmatch , Dmismatch )2: Σ ← FittingToPDF(Dmatch , Dmismatch )3: return Θ, Σ

4. 2 公理矛盾検出フェーズ
このフェーズでは Algorithm 2 を基に，近傍グラフを構築
し，その近傍グラフ内のエッジで接続された 3 つのノードについて，公理に矛盾した推論器の判定パターンを検出する．矛盾
した組み合わせについて，修正の必要順にランク付けをし，クラウドソーシングの上限 τcs limit に到達するまで問い合わせる．
公理に矛盾するパターンとは，図 7 のことであり，例えば 3 つのデータの関係について si = sj , sj = sk but sk =| si のような現実世界に存在しない推論パターンを指す．

Sameと推論したペア

Not-sameと推論したペア(10)

クラウドソーシングの問い合わせにより得られた一致ペアを

Dcs same ，不一致ペアを Dcs not same と表す．
Algorithm 2 Discover and correct axiomatic inconsistency
Input: Target database S, Metric learning parameters Θ,
SUN reasoner parameters Σ, andCrowdsourcing limit τcs limit
Output: Same pairs obtained by crowdsourcing Dcs same andNot same pairs obtained by crowdsourcing Dcs not same
1: G ← NN-GraphConstructor(S, Θ)
2: Terror ← AxiomaticError(G, Θ, Σ)
3: Sort Terror based on priority rules using Eq.(10);4: cs counter ← 0
5: for (si , sj , sk ) in Terror do
6:
if cs counter >= τcs limit then break7:
for (a, b) in Combination(i, j, k) do
8:
if Crowdsourcing(sa , sb ) = True then9:
Dcs same ← Dcs same ∪ {(sa , sb )}
10:
else
11:
Dcs not same ← Dcs not same ∪ {(sa , sb )}12:
end if13:
end for14:
cs counter ← cs counter + 1
15: end for
16: return Dcs same , Dcs not same17:
18: function Combination(i, j, k)
19:

return {(i, j), (i, k), (j, k)}

20: end function

無矛盾グループ
図7

公理矛盾グループ公理に矛盾しているグループ

4. 3 再学習フェーズ
このフェーズでは公理矛盾検出フェーズでクラウドソーシン
グにより得られた一致ペア Dcs same と不一致ペア Dcs not same

本研究では 3 つのノードによって構成される 3 つのエッジのみに着目し，それ以外の多角形については考慮しない．また，
グラフ上ではノード 3 つに対して 2 つしかエッジが存在しない
場合も，エッジがあるものとみなして検出の対象とする．
推論器の修正において，情報量が多いと考えられる以下の戦略によりクラウドソーシングに問い合わせて修正を行うペアを決定する．

について，人間の介入によって得られた信頼度の高いデータとして教師データに追加し，距離学習器と SUN 推論器のパラ
メータ Θ, Σ の更新を行う．Algorithm 1 の一致ペアの入力を

Dmatch +Dcs same ，不一致ペアの入力を Dmismatch +Dcs not sameにし，パラメータ Θ′ ，
Σ′ として更新する．

4. 4 同定フェーズ
このフェーズでは Algorithm 3 を基にターゲットデータ
ベース S のエンティティマッチングを行う．距離学習器および

I. Same 領域の大きい不一致ペアや，Not-same 領域の大きい一致ペアを検出し修正する

II. 絶対数が少ないと考えられる一致ペアは情報量が多いことを考慮し，一致ペアが多く含まれていると考えられるペアから検出する

SUN 推論器には，再学習フェーズで更新したパラメータ Θ′ , Σ′を使用し，更新した Θ′ で，近傍グラフ G を再構築する．
クラウドソーシング数の上限に達するまで，計算機は Psame >τsame を満たす場合に縮約操作し，Pnot same > τnot same を満たす場合に切断操作をする．この条件をどちらも満たさないペ
アは，クラウドソーシングにより人間に判断を仰ぐ．τsame とτnot same は，要求する精度に応じて決定する．

ク ラ ウ ド ソ ー シ ン グ 数 の 上 限 に 達 し た 後 は ， Psame >Pnot same を満たす場合に縮約し，満たさない場合を切断する．

5 実近傍グラフ G の全てのエッジが 0(|E| = 0) になると終了となり，グラフに残ったノード群 V が成果物となる．

Algorithm 3 Identiﬁcation験

提案手法に基づき，ターゲットデータベース S の規模とクラウドソーシング数 τcs limit を変更しながら同定処理を行うこと
で，公理系による矛盾検出および再学習の効果を示す．5. 1〜5. 4

Input: Target database S, Metric learning parameters Θ,
SUN reasoner parameters Σ,
Crowdsourcing limit τcs limit ,Same pairs obtained by crowdsourcing Dcs same , andNot same pairs obtained by crowdsourcing Dcs not same
Output: A set of nodes in the NN-Graph V
1: G ← NN-GraphConstructor(S, Θ)

は，利用するデータや検証方法等を記述し，5. 5 以降は，実験

2:

データとする．ワークフローで利用するデータの属性は，「書誌

3: for (si , sj ) in Dcs same doContraction(vi , vj )5: end for
6: for (si , sj ) in Dcs not same do
7:
Remove(vi , vj )8: end for4:9:
10: cs counter ← 0
11: while E =| ∅ do12:(vi , vj ) ← arg max Score (vi , vj )(vi ,vj )∈E

Psame , Pnot same ← SunResoner((si , sj ), Θ, Σ)14:
if cs counter < τcs limit then15:
if Psame > τsame then16:
Contraction(vi , vj )17:else if Pnot same > τnot same then18:
Remove(vi , vj )
19:
else
20:
if Crowdsourcing(sa , sb ) = True then21:
Contraction(vi , vj )
22:
else
23:
Remove(vi , vj )24:
end if25:
cs counter ← cs counter + 1
26:
end if27:
else
28:
if Psame > Pnot same then29:
Contraction(vi , vj )
30:
else
31:
Remove(vi , vj )32:
end if33:
end if34: end while
35: return V
13:

36:
37: function Score(vi , vj )38:

return |N (vi ) ∩ N (vj )|39: end function
40:
41: function Contraction(vi , vj )vi .group ← vi .group ∪ vj .groupfor v in N (vj ) do
44:
E ← E ∪ {(vi , v)}
45:
end for46:
V ← V \ {vj }47: end function

内容と結果を示す．

5. 1 利用データ
本実験では，全国 963 の公立図書館が保有する書誌データ約1211 万件が格納されたデータベースから抽出した一部を実験名」「著者名」「出版社名」「出版年」の 4 つのみを利用する．書誌の固有識別番号である「ISBN」は，•

Sn , Dmatch , Dmismatch の生成 (入力データの生成)•同定完了後の V の検証 (出力データの検証)•

クラウドソーシングの回答生成のみ利用し，計算機が係わるワークフローの処理に利用しない．
教師データに用いる一致ペア Dmatch と不一致ペア Dmismatch
を無作為に各 30000 ペア抽出する．ターゲットデータベー
スは，500 件の書誌データで構成されるデータベース 10 個

(Si (0 <=i<= 9))，2000 件の書誌データで構成されるデータベー
ス 10 個 (Sj (10 <=j<= 19)) をそれぞれ抽出する．なお，ター
ゲットデータベースに含まれる書誌データは，表 (3) の条件を満たすようにランダムに抽出する．カッコ外は S0 〜S9 ，カッコ内は S10 〜S19 の内訳である．
表3

ターゲットデータベース D の内訳
グループ数

一致ペア数

データ数

3 件一致グループ

75 (300)

225 (900)

225 (900)

2 件一致グループ

125 (500)

125 (500)

250 (1000)

1 件独立

25 (100)0 (0)25 (100)

計

225 (900)

350 (1400)

500 (2000)

5. 2 SUN 推論器のパラメータ
SUN 推論器で必要なパラメータを τsame = 0.7, τnot same =0.5 と設定し，計算機が一致ペアと判定する条件を厳しくした．
5. 3 クラウドソーシング
本実験では実際のクラウドソーシングは行わず，問い合わせには必ず正解を返すシミュレーション実験として検証した．

42:
43:

48:
49: function Remove(vi , vj )E ← E \ {(vi , vj )}51: end function50:

5. 4 結果の検証方法
検証には，F1 値と完全一致率の 2 つの指標を用いる．いずれの指標も 1 に近いほど精度が高いことを示す．

F1 値は「再現率」と「適合率」によって計算が可能．
F1 =2 · precision · recall
precision + recall(11)

完全一致率は，グルーピングが正しく成功した程度を表す．

1

データベースのノード集合 Vcorrect と，ワークフロー完了後に0.8得られるノード集合 V を用いて，式 (12) により定義される．

0.6|V ∩ Vcorrect |FullAgreementRate =|Vcorrect |

(12)

F1 値

正解一致ペアを使って正しく縮約した際に得られるターゲット

0.4

0
0

再学習の有無により，縮約結果の違いについて混同行列，F1

Retraining

推論

推論

一致ペア

不一致ペア

一致ペア

不一致ペア

一致ペア

307

43

307

43

不一致ペア

31

12436935

0.8977

再現率

0.87710.8771F1 値

0.89240.8873

完全一致率

0.8133 (183 / 225)

0.8222 (185 / 225)

0
0

600

800

1,000

S0 の F1 値と完全一致率の推移

0.8
0.6
0.4
Retraining
No-retraining

0.2

S10 の同定処理結果

00Retraining

2,000

4,000

6,000

8,000

10,000

総クラウドソーシング数上限 τcs limit

推論

1

一致ペア

不一致ペア

一致ペア

不一致ペア

一致ペア

1102

298

1197

203

不一致ペア

11096

196850420

1997580

適合率0.09034

0.9836

再現率

0.78710.8550F1 値

0.16210.9148

完全一致率

0.3789 (341 / 900)

0.8444 (760 / 900)

0.8

完全一致率

推論
正解

400

総クラウドソーシング数上限 τcs limit

くてもさほど悪く無く，ほとんど変わらない．

No-retraining

200

1

表 4 より，データが 500 件の場合，精度について再学習が無

表5

Retraining
No-retraining

図80.90831,000

0.4124365

適合率

800

0.6

0.2

F1 値

正解

No-retraining

600

0.8

完全一致率

S0 の同定処理結果

400

1

いて，ターゲット書誌データ D0 は，τcs limit = 600，D10 は，

τcs limit = 5000 とする．

200

総クラウドソーシング数上限 τcs limit

値および完全一致率で示す．クラウドソーシングの上限につ

表4Retraining
No-retraining

0.2

5. 5 再学習の有無による精度の検証 (実験 1)

0.6
0.4
Retraining
No-retraining

0.2
0
0

2,000

4,000

6,000

8,000

10,000

総クラウドソーシング数上限 τcs limit

表 5 より，データが 2000 件の場合，再学習しない場合は著図9S10 の F1 値と完全一致率の推移

しく性能が低下するが，再学習を行った場合は低下しない．

5. 6 総クラウドソーシング上限数変動と精度の検証 (実験 2)

5. 7 複数のデータベース比較による有意性の検証 (実験 3)

再学習の有無により，クラウドソーシング数の上限 τcs limit

ターゲットデータベース S0 〜S19 の 20 個について，各シスを変更することによる F1 値と完全一致率の変動を検証する．

テムの精度がデータベースにどの程度依存しているかを検証すターゲット書誌データは S0 と S10 を利用し，S0 についてはる．クラウドソーシングの上限を，500 件のデータを持つ S0

100 ずつ，S10 については 1000 ずつ τcs limit を変動させる．

〜S9 は τcs limit = 600 ，2000 件のデータを持つ S10 〜S19 は

図 8 より，データ数が 500 件の場合は，再学習の有無に関わτcs limit = 5000 で固定する．

らずクラウドソーシング上限数を 600 件に設定したあたりで性

図 10 より，データ数が 500 件の場合は，精度の最高値は再能が頭打ちしており，結果も有意に差があるとは言えない．

学習の有無に起因しないが，再学習なしに比べて再学習ありの

図 9 より，データ数が 2000 件の場合は，顕著に差が出てい方が，様々なデータベースに対し安定的である．

る．再学習しない場合は 6000 件強の問い合わせでアルゴリズ

図 11 より，データ数が 2000 件の場合は，より顕著であり，

ムが終了しており，精度も大きくは上がらない．一方で，再学再学習ありの場合は，データベースに依らず安定的に高精度な習ありの場合は 5000 件ほどで性能は頭打ちになるものの，精同定を行うことができる．

度の高い同定処理を行うことができる．

今後の展望として，「公理矛盾検出フェーズ」と「再学習フェー

Retraining

ズ」を複数回繰り返すことによる精度とクラウドソーシングコ

No-retraining
0

0.2

0.4

0.6

0.8

1

ストの検証と，シミュレーションを脱したクラウドワーカの回
答精度および手法全体の精度の検証を行いたい．前者は，再学

F1 値

習を複数回行うことで，更新の度に効果的な公理矛盾ペアを少Retraining
No-retraining

ない問い合わせ回数で得ることができ，精度は維持しつつも，
0

0.2

0.4

0.6

0.8

1

完全一致率

は，実際のクラウドソーシングの利用により，タスクの難易度

S0 〜S9 の F1 値と完全一致率の統計

図 10

クラウドソーシング数の減少に繋がることが期待される．後者
や結果の信頼性を含めた提案手法全体の検証を行いたい．
謝Retraining辞

本 研 究 の 一 部 は JSPS 科 研 費 (JP22H00508) と JST

No-retraining
0

0.2

0.4

0.6

0.8

1

F1 値

CREST(Grant Number JPMJCR22M) の支援を受けたものである．ここに謝意を示す．

Retraining

文

No-retraining
0

0.2

0.4

0.6

0.8

1

完全一致率
図 11

6 議

S10 〜S19 の F1 値と完全一致率の統計論

6. 1 公理系矛盾の問い合わせ戦略
本研究では，公理系矛盾の問い合わせを，式 (10) の戦略により行った．U nknown のほとんどが不一致ペアであることなどを踏まえて決定したが，これに捉われず，戦略の違いによる精度とクラウドソーシング数の差については検討の余地がある．

6. 2 パラメータの設定
このワークフローは，動作のために τsame , τnot same , τcs limitなど事前に決めなければならないパラメータが存在する．これ
らの適切な値はターゲット S に依存していると考えられ，現段階では実験を行うまで適切な値が得られない問題がある．デー
タ特性の事前分析による，適切なパラメータを事前に得られるような評価指標の考案，あるいは，ワークフロー中に適切なパラメータに修正できるシステムの構築に取り組みたい．

7 ま と め
本論文では，Human-in-the-loop を用いた同定処理において，規模の増加に伴い組み合わせ爆発を引き起こし，精度低下およびコストの大幅に増加について問題を提起した．その解決にあたり，再学習を取り入れた Human-in-the-loop エンティティ
マッチング手法，および再学習に効果的なデータを発見するための公理系矛盾を利用した手法を提案した．
実験では，データセットの規模とクラウドソーシング上限数に着目し，再学習の有無による違いを検証した．提案手法は，
データセットの規模を拡大しクラウドソーシング上限を課しても，安定的な精度を維持できることが示唆された．一方で，公理矛盾の問い合わせ戦略など改善の余地が見られる点もある．

献[1] Vassilis Christophides, Vasilis Efthymiou, Themis Palpanas,
George Papadakis, and Kostas Stefanidis. An overview of
end-to-end entity resolution for big data. ACM Comput.
Surv., Vol. 53, No. 6, dec 2020.
[2] Matthew A. Jaro. Advances in record-linkage methodology
as applied to matching the 1985 census of tampa, ﬂorida.
Journal of the American Statistical Association, Vol. 84,
No. 406, p. 414, 06 1989.
[3] 上田洋, 村上晴美, 辰巳昭治. 集中型横断検索システムのための自動書誌同定処理の検討. 第 57 回日本図書館情報学会研究大会
発表要綱, pp. 29–32, 2009.
[4] Harada Takashi, Fukushima Yukihiro, Sato Sho, Tsuruta
Misato, Yoshimoto Ryuji, and Morishima Atsuyuki. Advancement of bibliographic identiﬁcation using a crowdsourcing system.
Proceedings of the 9th Asia-Paciﬁc
Conference on Library & Information Education andPractice(A-LIEP 2019), pp. 71–82, 11 2019.
[5] Guoliang Li. Human-in-the-loop data integration. VLDB
Endowment, Vol. 10, No. 12, pp. 2006–2017, August 2017.
[6] Naofumi Osawa, Hiroyoshi Ito, Yukihiro Fukushima,
Takashi Harada, and Atsuyuki Morishima. Bubble : A
quality-aware human-in-the-loop entity matching framework. In The The 5th IEEE Workshop on Human-in-theloop Methods and Future of Work in BigData (IEEE HMData2021), pp. 3557–3565, December 2021.
[7] Stephen Robertson, S. Walker, S. Jones, M. M. HancockBeaulieu, and M. Gatford. Okapi at trec-3, January 1995.
[8] Yao Zhu, Hongzhi Liu, Zhonghai Wu, and Yingpeng Du.
Relation-aware neighborhood matching model for entityalignment, 2020.
[9] Jane Bromley, Isabelle Guyon, Yann LeCun, EduardSäckinger, and Roopak Shah. Signature veriﬁcation using a ”siamese” time delay neural network. In J. Cowan,
G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, Vol. 6. MorganKaufmann, 1993.
[10] R. Hadsell, S. Chopra, and Y. LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern
Recognition (CVPR’06), Vol. 2, pp. 1735–1742, 2006.
[11] William Winkler. String comparator metrics and enhanced
decision rules in the fellegi-sunter model of record linkage.
Proceedings of the Section on Survey Research Methods, pp.
354–359, 01 1990.
[12] Vladimir I Levenshtein, et al. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics
doklady, Vol. 10, pp. 707–710. Soviet Union, 1966.