Решение задачи стохастического максимального двустороннего согласования

Я столкнулся со следующей проблемой:

  • есть два непересекающихся множества, A и B
  • для каждой пары элементов (a, b) (a принадлежит множеству A, где b принадлежит множеству B) вероятность pij известна заранее. Он представляет вероятность (уровень достоверности) того, что a совпадает с b, или, другими словами, насколько близко a совпадает с b (и наоборот, потому что pij == pji).
  • Мне нужно найти соответствие с наибольшей вероятностью / достоверностью и найти пары (a, b), которые описывают совпадение
  • каждый элемент должен быть сопоставлен / спарен с другим из другого набора ровно один раз (как в стандартной задаче двустороннего сопоставления)
  • если возможно, я хотел бы вычислить число, которое приблизительно выражает уровень неопределенности для полученного соответствия (скажем, 0 представляет собой случайное предположение, а 1 представляет достоверность)

Простой практический пример, в котором требуется такой алгоритм, описан ниже (на самом деле это не та проблема, которую я решаю!):

  • двух человек просят написать буквы a - z на листе бумаги
  • для каждой пары букв (a, b) мы запускаем сопоставление шаблонов, чтобы определить вероятность того, что буква a, написанная человеком A, представляет букву b, написанную человеком B. Это дает нам матрицу вероятностей, которая выражает некую корреляцию сходства для каждой пары букв (a, b)
  • для каждого письма, написанного этим человеком A, нам нужно найти соответствующее письмо, написанное этим человеком B

Текущий подход: мне интересно, могу ли я просто назначить веса, которые пропорциональны логарифму уровня достоверности / вероятности того, что элемент a из набора A соответствует элементу b из набора B, а затем выполнить максимальное взвешенное двустороннее сопоставление для найти максимальную сумму. Логарифм нужен, потому что я хочу максимизировать общую вероятность множественного совпадения, и поскольку одиночные совпадения (представленные в виде пар совпадающих элементов a - b) образуют цепочку событий, которая является продуктом вероятностей, логарифм преобразует это сумме вероятностей, которая затем легко максимизируется с помощью алгоритма взвешенного двудольного сопоставления, такого как венгерский алгоритм. Но я почему-то сомневаюсь, что такой подход обеспечит наилучшее соответствие с точки зрения ожидаемого статистического максимума.

После небольшого поиска ближайшей проблемой, которую я обнаружил, была двухэтапная задача стохастического сопоставления с максимальным взвешиванием, которая является NP-сложной, но на самом деле мне нужна какая-то «одностадийная» задача стохастического сопоставления с максимальным взвешиванием.


matching max graph-algorithm stochastic bipartite
person eold    schedule 28.02.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Интересно, можно ли использовать MaxFlow / MinCut. Я не могу доказать, что это оптимально на данный момент, но ваша проблема в любом случае может быть NP-сложной. Вы можете использовать MF / MC, чтобы найти идеальное соответствие, когда у вас есть двудольный граф с V = (A, B), создав источник, подключенный ко всем узлам в A с весом 1, и приемник, подключенный ко всем узлам в B с помощью вес 1. Я предлагаю вам сделать веса ребер, которые пересекаются от A до B, равны вероятностям, которые вы упомянули выше. Что вы думаете?

person Eli    schedule 05.04.2011
comment
Тем временем я нашел другой подход. Существует алгоритм, называемый венгерским алгоритмом, который решает проблему присваивания. Поскольку этот алгоритм максимизирует сумму вероятностей, но я действительно заинтересован в их продукте (поскольку у меня есть цепочка событий), я мог бы применить к ним функцию логарифма. Итак, мой текущий подход заключается в следующем: 1) построить матрицу вероятностей совпадения вероятностей в двудольном графе; 2) натуральный логарифм каждого элемента матрицы; 3) запустите венгерский алгоритм, чтобы максимизировать вероятность всех совпадений. Как это звучит? - person eold; 10.04.2011