résolution de problèmes d'adaptation bipartite maximale stochastique

Question

I ont été confrontés au problème suivant:

• il y a deux ensembles disjoints, A et B
• pour chaque paire d'éléments (a, b) (a appartient à l'ensemble A , où b appartient à l'ensemble B) il y a une probabilité pij est connu à l'avance. Il représente la probabilité (niveau de certitude) que a correspond à b, ou en d'autres termes, à quel point a correspond b (et vice versa, car pij == pji).
• I doivent trouver une correspondance avec la probabilité la plus élevée/la certitude et découvrir paires (a, b) qui décrivent la mise en correspondance
• chaque élément doit être adapté/couplé à un autre de l'autre jeu exactement une fois (comme dans le problème de correspondance biparti standard)
• si possible, je voudrais calculer un nombre qui exprime à peu près le niveau d'incertitude pour la mise en correspondance obtenue (disons que 0 représente estimation aléatoire et 1 représente la certitude)

un simple pratique exemple dans lequel un tel algorithme est requis est descri lit ci-dessous (ce n'est pas en fait le problème que je résous!):

• deux personnes sont invités à écrire des lettres a - z sur un morceau de papier
• pour chaque paire de lettres (a, b) nous exécutons un modèle de correspondance pour déterminer la probabilité que la lettre a écrite par la personne A représente la lettre b écrite par la personne B. Cela nous donne la matrice de probabilité qui exprime une sorte de similitude corrélation pour chaque paire de lettres (a, b)
• pour chaque lettre que personne A a écrit, nous devons trouver la lettre correspondante écrite par personne B

approche actuelle: Je me demande si je pouvais attribuer des poids qui sont proportionnels au logarithme du niveau de certitude/probabilité que l'élément a de jeu A correspond à l'élément b du jeu B, puis exécute l'appariement bipartite pondéré maximal pour trouver la somme maximale. Le logarithme est parce que je veux maximiser la probabilité totale de correspondance multiple, et puisque les correspondances simples (représentées comme des paires d'éléments appariés a - b) forment une chaîne d'événements, qui est un produit de probabilités, en prenant le logarithme que nous convertissons cette à une somme de probabilités, qui est ensuite facilement maximisée en utilisant un algorithme pour l'appariement bipartite pondéré, tel que l'algorithme hongrois. Mais je doute d'une certaine façon que cette approche assurerait le meilleur appariement en termes de maximum statistique attendu. Après avoir cherché un peu, le problème le plus proche que j'ai trouvé était un problème de pondération stochastique pondérée maximum en deux étapes, qui est NP-difficile, mais j'ai vraiment besoin d'un problème de pondération stochastique pondérée maximum en une étape.

Answer 1

Je me demande si vous pouvez utiliser MaxFlow/MinCut. Je ne peux pas prouver que c'est optimal pour le moment, mais votre problème peut être NP-difficile de toute façon. Vous pouvez utiliser MF/MC pour trouver une correspondance parfaite lorsque vous avez un graphe biparti avec V = (A, B) en créant une source connectée à tous les noeuds de A avec un poids de 1 et un puits connecté à tous les noeuds de B avec poids 1. Je vous propose de faire les poids des arêtes qui traversent de A à B les probabilités que vous avez mentionnées plus haut. Qu'est-ce que tu penses?