Coda

メモ WebTables: Exploring the Power of Tables on the Web

October 31, 2019

概要

表題の論文は、Web上の表から抽出した大量の関係モデルを対象にした検索を提案・評価した 。検索の他にも、一部の属性を入力とするスキーマの補完、入力した属性ないしスキーマに類似のものを推定するアルゴリズムの議論もある。 ここのスキーマは属性のリストである。論文の著者らは研究時にGoogleに在籍しており、論文で使われたコーパスはグーグルの汎用ウェブクローラで集めた141億のHTMLの表から抽出した高精度な154百万の関係モデルである。 コーパスに使うものはHTML形式の表から抽出した関係モデルのみである。 手法の新規性は、1億以上もの大量のテーブルを対象にしていることにある。

準備

アルゴリズムの説明の準備のために、ASCDb (attribute correlation astatistics database)というスキーマの出現回数の統計情報を紹介する。これらは、\(\mathcal{R}\)関係モデル\(R\)の集合、\(R.u\)を\(R\)のあるURL、\(R.S\)をRのスキーマとすると、次のアルゴリズムでASCDbを求めることができる。また、属性の生起確率\(p\)は、ASCDbで集計した出現回数をもとに、属性を含むスキーマの数をスキーマの総数で割った値で定義される。 ascdb

ランキング

本論文におけるランキングは、クエリ\(q\)と出力数\(k\)を入力として、関連する関係モデルを順序つき\(k\)関係モデルを順序付きで出力する。 ここでの\(q\)は、私たちが普段検索エンジンに入力するような検索キーワードをさし、実際にアルゴリズムの中で検索エンジンに入力される。

提案されているランキングのうち最も検索性能のよいアルゴリズムはschemaRankといい、以下に示すベースラインのアルゴリズムのひとつfeatureRankとの違いは\(\mathcal{score}\)の計算方法のみである。 なお、最も単純なベースラインは、\(q\)を検索エンジンにかけて得られたURLにある表を返す。

feature_rank featureRankのアルゴリズムにおける\(\mathcal{score}\)の計算には、以下の特徴量を使う。各特徴には重みが与えられ、重みの値は人が作成した正解データと線形回帰を使って決められている。 feature_rank schemaRankの\(\mathcal{score}\)の計算には、これらの特徴量に加えて次の\(\mathcal{cohere}\)も使用する。 cohere

アルゴリズムの評価には、クエリと関係モデルの組に対して人手でつけられた5段階評価が使われた。 実験は、\(k\)の値が大きくなるほどschemaRankとベースラインとの検索性能の差が広がることを示していた。

感想

提案手法はWebサイトにある表から関係モデルを抽出する手段を研究のスコープに含めていないので、大量の関係モデルを検索するための手法として考えられる余地があるように感じる。 ただし、ランキングの基準になる特徴量はWeb上の表の観察によって選ばれたものなので、Web上の表以外に由来する関係モデルに適用する場合は、特徴量を再考する必要があるかもしれない。