2

有向非巡回グラフG = (V,E)(DAG) とします。Vは頂点の集合で、Eは辺の集合です。

ここでG、クラウドソーシングのパラダイムに従って、クラウド内の一部のアノテーターによって が破損したとします。

  • eそれらの一部は、に属するいくつかのエッジを削除することを決定する場合がありますE
  • eそれらの一部は、存在しなかったエッジを追加することを決定する場合があります

アノテーターの作業の結果は、i頂点のセットがV元のグラフと同じで、エッジのセットが元のグラフとEi異なる可能性があるグラフです。nがアノテーターの数である場合、頂点のセットは同じですが、エッジのセットが異なる、n異なるグラフが作成されます。をグラフの集合とします。VEG1 = (V,E1), ..., Gn = (V,En)

eこれらのグラフをマージして、の 2 つの頂点間で考えられる各エッジの有無についてコンセンサスを見つける方法があるかどうかを知りたいv1,v2ですV。この操作の目的はE、グラフ内のエッジのセットの構築に関する各アノテーターの意見を融合することGです。最終的なグラフは DAG でなければなりません。

4

2 に答える 2

1

各エッジについて、それを含むグラフの数を数えます。あるしきい値よりも大きい場合は、元のエッジであると想定します。

一部のアクションに偏りがある場合、いくつかの問題に直面する可能性があります。つまり、各ユーザーは特定のエッジを無作為に選んで行動するわけではありません。

于 2013-04-26T17:08:46.237 に答える
1

させて...

  • UすべてのEiセットと元のセットの別個の和集合E
  • T任意のしきい値
  • H(x)ヒューリスティック関数である
  • Fエッジの最終コンセンサス セット

擬似コード:

for each Edge e in U
   if H(e) >= T then F.Add(e)

問題はもちろん、ヒューリスティック関数をどのように定義するかです。素朴なアプローチは、投票に基づいて設定されます。エッジを含むセットの数を数え、Eそれがグラフにあることに十分な人が同意する場合は、それを含めます。これは、実装が簡単で効率的な機能です。このヒューリスティックのいくつかの弱点は、不適切なアノテーターや小規模なクラウド サイズを検出して補正できないことです。

于 2013-04-26T15:17:07.030 に答える