Какая комбинация структур данных эффективно хранит дискретные байесовские сети?

22

Я понимаю теорию, лежащую в основе байесовских сетей, и мне интересно, что нужно для ее создания на практике. Скажем для этого примера, что у меня есть байесовская (направленная) сеть из 100 дискретных случайных величин; каждая переменная может принимать одно из 10 значений.

Сохраняю ли я все узлы в группе обеспечения доступности баз данных, а для каждого узла - свою таблицу условной вероятности (CPT)? Существуют ли другие структуры данных, которые я должен использовать для обеспечения эффективного вычисления значений при изменении некоторых CPT (кроме тех, которые используются группой обеспечения доступности баз данных)?

data-structures machine-learning ясень
источник
Я использую в памяти базу данных sqlite для хранения таблиц CP, поскольку ожидается, что в БД будут эффективные алгоритмы и структуры данных для работы с таблицами. Работает отлично! :)
Pratik Deoghare
Пожалуйста, определите, что вы подразумеваете под эффективностью (память, производительность и т. Д.), И включите ваши ограничения. Без них это может легко закончиться соревнованием на самое эффективное, которое превратится в загадочный код, с которым мне никогда не захочется иметь дело в повседневной работе.
Джастин Бозонье
1
@JustinBozonier требует меньше памяти и работает быстро?
Pratik Deoghare

Ответы:

12

«Лучшая» структура данных, вероятно, зависит от того, какую именно проблему вы пытаетесь решить. Вот один из подходов, который я видел (и использовал сам), который просто хранит всю информацию и оставляет алгоритму, что с ним делать.

  1. Сначала вы индексируете узлы уникальными целыми числами, от 0 до n-1. Затем вы просто сохраняете для каждого узла список его родителей в виде массива целых чисел - например, в C ++ вы можете иметь std::vector<std::vector<int> >: первый вектор над узлами, второй вектор перечисляет соответствующих родителей). Это отражает всю структуру DAG.

  2. Кроме того, поскольку каждый узел имеет ровно одну таблицу условных вероятностей, связанную с ним, вы можете индексировать их с одинаковыми целочисленными идентификаторами. Для каждой таблицы вероятностей вам нужно хранить ее область видимости, то есть набор случайных величин, для которых она определена. Во-вторых, у вас, вероятно, будет один большой список чисел с плавающей запятой, который содержит фактические условные вероятности (и вы захотите убедиться в правильности индексации). Чтобы снова привести пример C ++, можно сделать что-то вроде этого:

    struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

    При этом вы можете использовать std::vector<CondProbTable>для хранения всех ваших CPT.

Опять же, это в основном хранит байесовскую сеть, но не предполагает, что вы хотите с ней делать. Включение области CPT в CondProbTable несколько избыточно, поскольку оно может быть выведено из списка родительских узлов, описанного в пункте 1.

много
источник
0

В основном дискретные CPT являются гиперматрицами, и вы должны смотреть на них таким образом.

Довольно распространенный способ представления гиперматрицы - использование хеш-таблицы с использованием строкового индекса. например, в двух измерениях t [1] [2] будет t.get ("1_2")

Возможны более эффективные по памяти решения: если гиперматрица разрежена, вы можете использовать специальное разреженное представление (например, Fuchs 72), если у него есть структура, вы можете использовать ADD (алгебраическую диаграмму решений) или логические правила.

Ваш последний вопрос не очень ясен, однако, если вы ожидаете, что ваш CPT будет часто меняться, то, вероятно, вам лучше будет использовать плоское представление CPT с таблицей или хеш-таблицей.

никола
источник