Web Page Segmentation Revisited: Evaluation Framework and Dataset

[e4exp]

• https://webis.de/data/webis-webseg-20.html#kiesel_2020b
• CIKM 2020

各ウェブページは、特定の目的を達成するために、意味的に一貫したユニットにセグメント化することができます。 ウェブページの自動分割というタスクは、ウェブコンテンツ分析へのいくつかの応用とともに、20年前に導入されましたが、その基礎はまだ不足しています。 特に、開発された評価方法やデータセットは、ある下流のタスクを前提としているため、様々な互換性のないデータセットや評価方法になっています。 この欠点を解決するために、我々は2つのリソースを提供します。 (1)視覚的、構造的、テキスト的な要素に関するセグメンテーションの類似性を測定することで、下流のタスクに対応できる評価フレームワークであり、アノテーターの一致度、セグメンテーションの品質、セグメンテーションフュージョンのアルゴリズムを含む。 Webis-WebSeg-20データセットは、8,490のウェブページに対して、42,450のクラウドソースによるセグメンテーションから構成されており、既存のソースを一桁上回っています。 この結果は、人間のアノテーターの「メンタル・セグメンテーション・モデル」の理解を深めるのに役立ちます。 特に、ウェブページのあらゆる要素（視覚的、構造的、テキスト的）のセグメンテーションについて、アノテーターはほぼ同意していることがわかりました。 意見の相違は、主に適切な粒度のレベルに関してであり、ウェブページの視覚的構造に関しては一般的に合意していることを示しています。

[e4exp]

結論

本論文では、ウェブページのセグメンテーションというタスクを再検討し、一般的なウェブページセグメンテーションアルゴリズムの評価を妨げていたギャップを埋める。 これまでの研究とは異なり、我々の評価フレームワークは、ウェブページセグメンテーションの様々な下流のタスクのうちの1つに焦点を当てるものではありません。 その代わりに、クラスタリング理論に基づいたウェブページセグメンテーションのための統一された類似性測定を用いて、異なる下流のタスクを説明しています。 さらに、この尺度が、アノテーターの合意の計算、グランドトゥルースの融合、セグメンテーションの品質評価の基礎となることを示しています。 この手法を用いて、Webis Web Segmentation Corpus 2020を構築した。 このデータセットは、4,824サイトの8,490ページに対する人間のアノテーターによる42,450件のセグメンテーションからなる。 我々の評価フレームワークとこのデータセットにより、異なる下流のタスクに対するウェブページ・セグメンテーション・アルゴリズムを一貫して評価することが初めて可能になりました。 このような一般的なアルゴリズムのベンチマークは、論理的な次のステップであり、アルゴリズムのタスク固有の強みと弱みについての洞察を提供することで、アルゴリズムの共通の問題点を明らかにし、今後の研究の指針となる可能性がある。

ウェブページのセグメンテーションの後、多くの下流のアプリケーションは、セグメントのラベル付けを必要とします。 したがって、セグメントラベルを使ってデータセットを拡張することは、この研究を継続するためのさらなるステップです。 できるだけ多くの下流のタスクと互換性を持たせるために、セグメントラベルの有望な選択は、Webページ上で果たす機能である[10]。 このような機能ラベルは特定の意味を持っているので、システム開発者は、このようなラベルを目下のタスクにマッチさせ、対応するセグメントを選ぶことができ、また、拡張されたデータセットを使って、どのアルゴリズムがそれぞれの機能を持つセグメントに最も適しているかを評価することができます。

[e4exp]

5.1 Preprocessing and Web Page Analysis

我々のデータセットのウェブページはすでにオリジナルのウェブ・アーカイブに含まれていますが，ウェブページ・セグメンテーションのためのすべてのリソースが容易に利用できるわけではなく，また，アーカイブ内のすべてのページがウェブページ・セグメンテーションのデータセットに適しているわけでもありません。 具体的には，すべてのページをブラウザ内で再現し，レンダリングされたページからすべてのDOMノード，そのテキストコンテンツ，添付のスクリーンショット上の位置（すなわちバウンディングボックス）を抽出した． 100ページのスポットチェックでは、位置が正確であることを手動で確認しました。 今回の検証では，セグメンテーションの観点から問題のあるページとして，「シンプルページ」と「エラーページ」の2つのケースを確認しました。 ここでいう「シンプル」とは，セグメンテーションを行うのに十分なコンテンツを持たず，データセットから除外したウェブページのことです。同様に，エラーページとは，明らかにメインコンテンツを欠いていたり，間違っていたりするページである． ページ分析パイプラインでは、このようなページはセグメンテーションの前に識別され、再クロールされることが期待されます。 これらのページは、後述するページの複雑さの分析と、オリジナル・アーカイブのマニュアル・エラー・アノテーションの公開リスト[20]によってそれぞれ特定された。 データセットがウェブページの幅広いサンプルを表していることを確認し，ページの複雑さを調査するために，DOM ノードの量とピクセルの高さを分析した6． 図3aは，シンプルさの境界線上にあるページを示しています． 図 3a は，シンプルさの境界にあるページを示しています． 図 3b と図 3c では，DOM ノードの数とピクセルの高さの両方のページについて，一見自然な対数正規分布が観察されます． 16,384ピクセルの高さを持つページが例外的に多いのは、アーカイブツールがスクロールを停止した、無限スクロールのページによるものです。 エラーページは、ページの全体的な分布にやや従っています。 推測されるように、DOM ノード数とピクセルの高さの相関関係（図 3d）は、適合した対数線形モデル（直線）とピアソン相関によって示されるように、かなり強いものです。

[e4exp]

5.2 Human Annotation

人間にとって、1つのウェブページを分割することは非常に簡単なことです。 Kreuzerら[24]は次のように述べています。"人間は分割するのが非常に得意です。 ウェブサイトが馴染みのない言語で書かれていたとしても、何が広告で、何がメニューなのかなどは明確です。 " このような手作業によるセグメンテーションを，アノテーターの偏り（システマティックエラーなど）を避けながら8,490のウェブページに拡張するために，我々はクラウドソーシングを採用した． AmazonのMechanical Turkを利用して，ウェブページのスクリーンショットにバウンディングボックスを描くことができるアノテーターインターフェイスと，セグメンテーションを可視化して品質管理を行うことができるレビュアーインターフェイスを開発した． さらに、手書きのセグメントを対応するDOMノードに確実にマッピングする方法を開発し、アノテーター間の一致度を測定することでアノテーションの品質を評価しました。 タスクの設定 AmazonのMechanical Turkは，クラウドソーシング市場であり，我々のような依頼者は，いわゆる「ヒューマン・インテリジェンス・タスク」（HIT）をワーカーに広告し，成功したときにタスクごとに報酬を得ることができる． パイロット実験の結果、私たちのタスクは専門家を必要としないことがわかったので、ワーカーには、過去に承認されたHITを100件以上持っていることを要求しました。

スクリーンショットのピクセルの高さが大きく異なるにもかかわらず，HITごとに均等な作業量を確保するために，ビンパッキングアルゴリズムを用いてウェブページを分散させ，すべてのHITに，スクリーンショットの最大ピクセルの高さである約16,384ピクセルのウェブページが含まれるようにしました． 平均して，1つのHITには5つのウェブページが含まれていました． パイロット実験では，ワーカーが1HITあたり平均11.2分を必要とすることがわかった． この金額は，インドの最低賃金の 13 倍，発展途上国の労働者の出身国の上位 2 カ国であるフィリピンの最低賃金の 3 倍である[14]． ウェブページのセグメンテーションでは，粒度の違いによる曖昧さが生じる可能性があるため，この現象を調べるために，すべてのウェブページに5人の独立したアノテーターがアノテーションを行った． 5,231件のアサインメントを行い、8,490ページに対して42,450のセグメンテーション（627,080のセグメントを含む）を収集しました。 この作業には976人のアノテーターが参加し、総コストは約8,500ドルでした。

[e4exp]

アノテーターインターフェイス。

図4は、アノテーターに与えられた指示書で、セグメントの作成と調整を例示するアニメーションが含まれています。 その下にはスクリーンショットが表示され，アノテーターはアニメーションと同じように半透明の青い四角形でセグメントを描かなければならない。 アノテーターインターフェイスのデザインは、パイロット実験において、シンプルさと操作性を考慮して最適化されました。 最初はDOMノードを直接選択してセグメントを指定していましたが、このインターフェースでは複雑な複数選択が必要で、HTMLの知識がないアノテーターは混乱してしまいました。 そこで、アノテーターに自由に矩形を描いてもらうことにしました。この場合、描いた矩形の不正確さを解消したり、アノテーションをDOMにマッピングしたりするための次のステップが必要になります。 描画を容易にするために、人差し指をほとんど動かさないクリック・ムーブ・クリックの動作を採用し、長時間の高速作業を可能にした。 アノテーターは長方形を入れ子にすることができるが、これはアノテーションの3％以下であった。

[e4exp]

レビュアーインターフェース

図5は、アノテーションの進捗と品質をモニターするために構築したレビューアインターフェースである8。 アノテーターを素早くチェックするために、各HITに1つのテストページを導入し、レビューアインターフェースにはリファレンスとアノテーターの両方のセグメントを表示した。 テストページは、まず自分で作成したセグメンテーションを使用し、その後、アノテーターの意見がほぼ一致したテストページを繰り返し追加していった。 あるアノテーターがテストページのセグメンテーションが悪かった場合、他のアノテーションやメタデータを調べて、タスクを解決するために努力したかどうかを判断しました。 そうであれば、そのアノテーションはデータセットから除外しましたが、アノテーターの公正な仕事に対して報酬を支払いました（「内部棄却」）。 また、特に優秀なアノテーターを集めるために、すべてのアノテーターは、タスクを確認するまでは10個のタスクに制限され、ほとんどのタスクが承認されないと続けることができませんでした。 合計で、5,231件の課題を承認し、6,152件を内部リジェクトし、540件を公開リジェクトしました。

[e4exp]

DOMノードへのあてはめ。

不正確に描かれたセグメントの矩形をDOMノードにマッピングするために、我々は各DOMノードの可視領域の少なくとも一部𝜃𝑐が矩形と重なっている場合、各DOMノードをセグメントの一部として扱う。 𝜃𝑐を最適化することで、セグメントの全てのDOMノードの可視領域（多角形）が、面積の𝐹1-scoreの観点から元の矩形と最もよく一致するようにする（図6aを参照）。 これは、 (1)アノテーターがスピードを上げるために必要以上に大きな長方形を描く傾向があること、 (2)複数の多角形が1つの長方形よりもDOMノードにぴったりとフィットすることから、理にかなっている。 一方、精度は0.94と非常に高く、長方形が少し小さすぎるように描かれているケースはわずかであることがわかります。 しかし、長方形にほぼ含まれるDOMノードを追加することで、DOMノードを含まないために廃棄される空のセグメントの数は、7％からわずか2％に減少します。 図6bは、これらの平均値の背後にある分布を示しています。ほとんどの多重多角形は、描かれた長方形と実に正確に一致しています。

[e4exp]

アノテーション品質の評価

表2は、セクション4.3で開発した合意指標の観点から、アノテーション品質を示している。charsの非常に高い𝐹𝐵3 (0.78)に示されるように、どのテキストノードが一緒に属しているかについて、アノテーターはほぼ同意している。 実際、ピクセル(𝐹𝐵3 0.65)とエッジ(両方とも0.73)の間のかなり大きな差は、不一致のかなりの部分が、ほとんどの下流のアプリケーションには無関係な空白(つまり背景)のセグメンテーションの違いによるものであることを示している。 さらに、max(𝑃𝐵3 , 𝑅𝐵3 )を用いた値の比較で明らかになったように、ほぼ全ての不一致はアノテーターが異なる粒度で作業していることによるものであり、セグメンテーションが大きく異なることによるものではない。 このように、我々のデータセットはウェブページのセグメンテーションのための高品質なリソースを提供し、将来的には階層的なグランドトゥルースセグメンテーションを提供するように拡張することも可能であると結論付けた。

[e4exp]

5.3 Segmentation Fusion

セグメンテーション・アルゴリズムの評価と学習ベースのアルゴリズムのトレーニングを容易にするために、セクション4.3で説明したように、ウェブページごとの5つのセグメンテーションを1つの一貫したグランドトゥルースに融合します。 ここでは、アノテーションに合わせて、ピクセルを要素として使用しています。図7に示すように、大多数のアノテーターがセグメントに入れた要素（閾値3）だけを融合すると、グランドトゥルースのピクセル数は20％減少しますが、エッジ（6-7％）、ノード（5％）、特に文字（2％）は減少します。 このように、どの要素がセグメントに含まれるかについて、アノテーターの意見はほぼ一致しています。 ピクセルの減少が大きいのは、より粗いレベルで作業するアノテーターが少ないためで、セグメントには当然、より多くのブランクスペースが含まれます。 図8aとbは融合の例です。図8cは、様々な𝜃𝑠について融合前と融合後のセグメント数を比較したものである。 大雑把に言うと、𝜃𝑠 = 0.9の場合は全てのアノテーターがそうした場合に要素が1つのセグメントにまとめられ、𝜃𝑠 = 0.1の場合は全てのアノテーターがそうした場合に要素がまとめられる。 望ましいことだが、図を見ると、採用された多数決（𝜃𝑠 = 0.5）の分布も元の平均化された分布と非常によく似ている。