Эффективный способ найти объяснения метода-теста-матрицы (математическая задача)

Question

Установка:

У меня есть логическая матрица, например,

1  0
1  1
0  1

где строки имеют имена m1 , m2 , m3 (в качестве методов) и столбцы t1 и t2 (как тесты).

Определение:

Объяснение - это набор строк (методов), которые в объединении имеют по крайней мере одну "1" в любом столбце (каждый тест должен соответствовать хотя бы одному методу).

в нашем примере набор объяснений будет:

{
  {m2}, 
  {m1,m2},{m1,m3},{m2,m3},
  {m1,m2,m3}
}

Проблема:

Теперь я хочу вычислить все объяснения.

Теперь у меня уже есть две реализации, которые могут решить эту проблему, одна ищет объяснения сверху вниз, другая снизу вверх, но обе страдают от экспоненциального роста вычислительного времени (удваивается при увеличении числа строк на одну).

Это известная (может быть, эффективно решаемая) математическая задача?

Что может упростить ситуацию, так это то, что в конце мне нужно только количество случаев в объяснениях для каждого метода. В нашем примере это будет для m1 три вхождения, для m2 четыре вхождения и для m3 три вхождения.

Мои текущие алгоритмы работают нормально, пока, скажем, 26 строк. Но дальше все становится очень медленно.

Спасибо за вашу помощь!

Answer 1

Если вы можете согласиться на приблизительные вероятности и хотите что-то масштабируемое, выборка Гиббса может сработать. Основная идея довольно проста: начните с объяснения, состоящего из всех строк, и повторите следующее, чтобы получить несколько объяснений.

1. Выберите случайную строку.
2. Переверните монетку.
3. Если монета выпала из головы, добавьте строку к объяснению (ничего не делайте, если она уже есть).
4. Если монета выпала за хвост, попытайтесь убрать строку из объяснения. Если результат не является объяснением, верните строку назад.

В пределе доля выборок, содержащих данную строку, сходится к ее истинному значению. Есть несколько практических реализаций под ключевыми словами «Байесовский вывод с использованием выборки Гиббса» (у вас есть единообразный априор и вы заметите, что для каждого столбца дизъюнкция строк, инцидентных с ним, истинна). Так как я не эксперт в этом деле, я не могу посоветовать вам, как опасно кататься самостоятельно.

Answer 2

Я думаю, что это может быть экспоненциальной проблемой. Например, если один из методов имеет по одному в каждом столбце, то любое подмножество методов, содержащих этот метод, является объяснением, и поэтому, если существует M методов, существует не менее 2 ^ (M-1) объяснений; Точно так же, если у некоторой пары методов есть один в любом столбце, то есть как минимум 2 ^ (M-2) объяснения.

Вот метод, который, хотя и остается экспоненциальным, я думаю, быстрее, чем перечислять все объяснения, особенно когда есть методы со многими единицами.

Пусть T (A, B) будет количеством подмножеств A (набор методов), которые имеют по крайней мере одну единицу в каждом столбце в B (набор столбцов).

Если B пусто, T (A, B) - это число подмножеств A, то есть 2 ^ # A, где A имеет #A элементов. В противном случае, если A пусто, T (A, B) равно 0. В противном случае, если i является элементом A (например, первым),

T (A, B) = T (A \ {i}, B \ m [i]) + T (A \ {i}, B)

(здесь A \ {i} - это A без i, B \ m [i] - это B без каких-либо столбцов в методе i)

T можно довольно кратко кодировать как рекурсивную функцию.

Наконец, c [j], количество раз, которое метод j встречается в объяснении, равно

c [j] = T (A \ {j}, C \ m [j])

где C - множество всех столбцов.

Answer 3

Я не знаю, существует ли экспоненциальное число возможных объяснений (что означает, что вы не можете перечислить их быстрее, чем экспоненциальное).

Однако вы можете подойти к этому в стиле динамического программирования, чтобычтобы устранить дублирующее усилие:

• Первый уровень - это список одного элемента: набор всех методов
• цикл для каждого уровня:
  • цикл для каждогоустановите на этом уровне:
    • , если этот набор является объяснением (or объединение их тестов дает все 1 с):
      • поместите его в список результатов
      • создать все возможные подмножества этого набора, которые имеют ровно на один метод меньше, и поместить их на следующий «уровень»
  • удалить все дубликаты со следующего уровня
• пока уровень не опустеет