Я столкнулся со следующей проблемой:
- есть две непересекающиеся группы,
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 изset A соответствует элементу b из набора B, а затем запускает максимальное взвешенное двустороннее сопоставление, чтобы найти максимальную сумму.Логарифм объясняется тем, что я хочу максимизировать общую вероятность множественного сопоставления, и поскольку одиночные совпадения (представленные в виде пар сопоставляемых элементов a - b) образуют цепочку событий, которая является продуктом вероятностей, принимаяВ логарифме мы преобразуем это в сумму вероятностей, которая затем легко максимизируется с помощью алгоритма взвешенного двудольного сопоставления, такого как венгерский алгоритм.Но я почему-то сомневаюсь, что этот подход обеспечит наилучшее сопоставление с точки зрения ожидаемого статистического максимума.
После небольшого поиска ближайшей проблемой, которую я обнаружил, была двухэтапная стохастическая задача сопоставления с максимальным взвешенным соответствием, которая является NP-сложной, но мне на самом деле нужна какая-то «одноэтапная» стохастическая задача о максимальном весовом сопоставлении.