次の問題に直面しました。
- 互いに素な集合が 2 つあり
A、B - 要素の各ペア (
a,b) (aset に属し、 setAにb属するB) の確率pijは事前にわかっています。aこれは、 と一致する確率 (確実性レベル)、bつまり、どの程度a一致するか (および==bであるため、その逆も同様) を表します。pijpji - 確率/確実性が最も高いマッチングを見つけ、マッチングを説明するペア (
a、b) を見つける必要があります。 - すべての要素は、他のセットの別の要素と1回だけ一致/ペアにする必要があります（標準の2部一致問題のように）
- 可能であれば、得られたマッチングの不確実性レベルを近似的に表す数値を計算したいと思います (0 はランダムな推測を表し、1 は確実性を表すとしましょう)。
そのようなアルゴリズムが必要とされる簡単な実用的な例を以下に示します (これは実際に私が解決しようとしている問題ではありません!):
- 2 人が紙に a ～ z の文字を書くように求められる
- 文字 (
a, ) の各ペアに対して、パターン マッチャーを実行して、人によって書かれた文字が人によって書かれた文字を表すb確率を決定します。これにより、文字の各ペア ( , )に対するある種の類似性相関を表す確率行列が得られます。aAbBab - その人が書いた各文字について、その人
Aが書いた対応する文字を見つける必要がありますB
現在のアプローチ:セットの要素がaセットの要素とA一致する確実性レベル/確率の対数に比例する重みを割り当ててから、最大加重二部マッチングを実行して最大合計を見つけること
ができるかどうか疑問に思っています。対数は、複数の一致の合計確率を最大化したいためであり、単一の一致 (一致した要素のペアとして表される-bBab) 確率の積である一連のイベントを形成します。対数を取ることにより、これを確率の合計に変換します。これは、ハンガリーのアルゴリズムなどの加重二部マッチングのアルゴリズムを使用して簡単に最大化されます。しかし、私は、このアプローチが統計上の期待最大値の点で最良のマッチングを保証するとはどういうわけか疑問に思っています。
少し検索した後、私が見つけた最も近い問題は、NP困難である2段階の確率的最大加重マッチング問題でしたが、実際にはある種の「1段階」の確率的最大加重マッチング問題が必要です。