Расширение Qbayes, методы статистического анализа на основе условных вероятностей Байеса

Назначение расширения

Расширение QHB Qbayes — это созданный командой разработчиков QHB инструментарий для задач расчета вероятностных моделей с применением сетей Байеса.

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

После предварительной статистической обработки исторических фактов (обучения), модель позволяет рассчитывать условные вероятности тех же самых гипотез при новых условиях (новых значениях параметров).

Алгоритмы Байесовского предсказания

В настоящее время в расширении используются следующие алгоритмы.

Наивный байесовский классификатор

Простой классификатор, основанный на предположении о независимости параметров.

Этот тип модели используется при обучении с параметром model_type = 'naive' (Naive Bayesian classificator).

Классификатор, основанный на функции взаимной информации

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

Метод позволяет определить для гипотез зависимые параметры и в дальнейшем использовать эти зависимости для предсказания гипотез.

Этот тип модели используется при обучении с параметром model_type = 'mi' (Mutual Information).

Методы Монте-Карло с цепями Маркова

Класс алгоритмов, моделирующих некоторое распределение вероятностей. В расширении Qbayes один из таких алгоритмов семплирования применяется для установления зависимых параметров для гипотез.

В расширении Qbayes предполагается использовать различные алгоритмы, в релизе QHB 1.4.0 используется одна из реализаций алгоритма Метрополиса — Гастингса.

Этот тип модели используется при обучении с параметром model_type = 'mcmc' (Markov chain Monte Carlo).

Методы расширения

При создании модели создается таблица описания моделей:

CREATE TABLE IF NOT EXISTS qbayes_model_description (
    имя_модели VARCHAR NOT NULL,
    параметры_модели json NOT NULL,
    CONSTRAINT qbayes_model_un UNIQUE (model_name)
);

Затем, после обучения статистической выборкой, создается таблица с данными:

CREATE TABLE IF NOT EXISTS qbayes_model_data (
    имя_модели VARCHAR NOT NULL,
    имя_графа VARCHAR NOT NULL,
    данные json,
    CONSTRAINT qbayes_model_graph_un UNIQUE (model_name, graph_name)
);

Примечание
Указанные таблицы создаются автоматически при вызове соответствующих методов в текущей схеме базы данных по умолчанию. Если таблицы уже существуют, они дополняются. При этом действуют ограничения уникальности на имя модели в первой таблице и имя модели с именем графа во второй.

Определение модели

Для определения модели используется метод:

CREATE OR REPLACE FUNCTION qbayes_create_model(
    имя_модели cstring,
    описание json)
returns BIGINT AS 'MODULE_PATHNAME' language c volatile security definer;

Возвращаемое значение

При успешном выполнении возвращается 0 или генерируется ошибка при неуспешном.

Параметры:

имя_модели задает имя модели, которое должно быть уникальным в рамках таблицы описания моделей.
описание описывает параметры и гипотезы модели. Каждый параметр или гипотеза описываются json-выражением.

Его поля:

"name" — символическое имя параметра или гипотезы,
"type" — тип параметра или гипотезы в исходном представлении; поддерживаются только типы bool (логический), discrete_integer (дискретный при перечислении) или float8 (с плавающей запятой, при создании диапазонов значений),
"distrib" — тип параметра или гипотезы в модели; поддерживаются только типы bool (логический) или discrete (дискретный),
"ranges" — границы разделения на интервалы для создания дискретного параметра, используется только вместе с параметром с типом float8,
"acceptable" - значения, допустимые при перечислении, используется только вместе с параметром с типом discrete_integer,
"is_hypothesis" — признак гипотезы, по умолчанию имеет значение false.

Типы параметров и гипотез

Все алгоритмы Байеса в расширении используют только бинарные и дискретные типы параметров моделей, а гипотезы - только бинарные типы.

Для обеспечения возможности оперирования различными типами в исходном представлении, допустимы различные комбинации полей "type" и "distrib" в определении модели.

Бинарные параметры

...
"type": "bool",
"distrib": "bool",
...

В этом случае параметр считается бинарным и во внешнем представлении, и во внутреннем преставлении модели. И при обучении модели, и при расчёте прогнозных значений гипотез, допустимые входные значения - true и false.

Дискретные параметры при разбиении на диапазоны

...
"type": "float8",
"distrib": "discrete",
"ranges": [r0, r1, ... ,rN]

В этом случае параметр считается дискретным во внутреннем преставлении модели. В качестве значения во внешнем представлении выступают числа типа float8, которые затем разбиваются на диапазоны по границам r0, r1, ..., rN и во внутреннем представлении обозначают номер диапазона, в который попадает значение.

Диапазоны задаются полем ranges. Перечисление значений в его массиве указывают на границы диапазонов, причём создаётся N+1 диапазонов по следующим правилам:

0: (-infinity; r0)
1: [r0; r1)
...
N: [r{N-1}; rN)
N+1: [rN; +infinity)

И при обучении модели, и при расчёте прогнозных значений гипотез, на вход параметров передаются значения типа float8, методы расширения уже сами определяют номер диапазона.

Дискретные параметры при перечислении

...
"type": "discrete_integer",
"distrib": "discrete",
"acceptable": [m0, m1, ... ,mN]

В этом случае параметр считается дискретны во внутреннем преставлении модели. В качестве значения во внешнем представлении выступают дискретные значения от 0 до N из поля acceptable. Сами значения параметра могут быть произвольными целыми числами, из перечисленных m0, m1, ..., mN, необязательно идущими подряд или начинающимися с 0.

И при обучении модели, и при расчёте прогнозных значений гипотез, на вход параметров передаются значения из поля acceptable, методы расширения уже сами определяют дискретное значение, соответствующее значению параметра. Если внешнее значение не соответствует ни одному из перечисленных m0, m1, ... mN, то генерируется ошибка.

Внешнее и внутреннее представление гипотез

Для гипотез допустима только одна комбинация "type" и "distrib":

...
"type": "bool",
"distrib": "bool",
...

Обучение модели

Данные (факты) с выделенными параметрами могут содержаться либо в уже подготовленных таблицах (relation), либо в представлении (view), созданном на основе этих таблиц.

Ограничения для таблиц и представлений:

Они должны содержать поле value типа json, в котором содержатся по крайней мере такие же поля, какие были объявлены при определении модели. Могут существовать и другие поля, однако они не принимаются в расчет при обучении.
Поддерживаются бинарные или дискретные параметры (предполагается независимость параметров; используемый тип модели — наивная модель Байеса).

Обучение производится следующим методом:

CREATE OR REPLACE FUNCTION qbayes_learn(
  имя_модели cstring,
  имя_графа cstring,
  тип_модели cstring,
  имя_отношения cstring,
  число_итераций BIGINT)
returns BIGINT AS 'MODULE_PATHNAME' language c volatile security definer;

Возвращаемое значение

При успешном выполнении возвращается 0 или генерируется ошибка при неуспешном.

Параметры:

имя_модели указывает имя модели;
имя_графа указывает имя графа;
тип_модели указывает тип модели ('naive', 'mi' или 'mcmc'; см. Алгоритмы Байесовского предсказания);
имя_отношения указывает на подготовленные исходные данные с фактами и гипотезами;
число_итераций задает количество шагов алгоритма для сходимости к стационарному распределению с приемлемой ошибкой.

Примечание
Параметр число_итераций имеет значения только для модели типа mcmc, для остальных он просто игнорируется.

Дообучение модели

Примечание
Дообучение имеет смысл проводить только для модели типа mcmc, для остальных типов функция дообучения просто ничего не делает.

CREATE OR REPLACE FUNCTION qbayes_learn_again(
  имя_модели cstring,
  имя_графа cstring,
  тип_модели cstring,
  имя_отношения cstring,
  число_итераций BIGINT)
returns DOUBLE PRECISION AS 'MODULE_PATHNAME' language c volatile security definer;

Возвращаемое значение

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

При неуспешном выполнении генерируется ошибка.

Параметры

Параметры аналогичны функции qbayes_learn, но происходит уточнение распределения на число_итераций.

Предсказание

Вычисление вероятностей гипотез при заданных параметрах производится следующим образом:

CREATE OR REPLACE FUNCTION qbayes_solve(
  имя_модели cstring,
  имя_графа cstring,
  элементарное_событие json)
returns json AS 'MODULE_PATHNAME' language c volatile security definer;

Возвращаемое значение

При успешном выполнении возвращается json, в котором перечисляются пары:

символическое имя гипотезы,
вероятность, с которыми эти гипотеза сбудется.

При неуспешном выполнении генерируется ошибка.

Параметры:

имя_модели указывает имя модели.
имя_графа указывает имя графа.
элементарное_событие задает вектор параметров для расчета гипотез в виде json-выражения.

Для расчета вероятностей гипотез для множества векторов параметров имеется дополнительный метод. Ему на вход предается набор параметров в таком же виде, как при обучении модели:

CREATE OR REPLACE FUNCTION qbayes_solve_view(
  имя_модели cstring,
  имя_графа cstring,
  имя_отношения cstring)
returns setof json AS 'MODULE_PATHNAME' language c volatile security definer;

Примечание
Дополнительно предлагается группа методов для обработки большого количества гипотез: qbayes_learn_mt, qbayes_solve_mt и qbayes_solve_view_mt. Они выполняются в многопоточном режиме и позволяют ускорить обучение и расчет. По параметрам эти методы полностью совпадают с соответствующими однопоточными версиями.
Следует отметить, что на малом количестве гипотез ускорение может не произойти, более того, из-за накладных расходов на организацию многопоточной обработки может наблюдаться замедление.
В ранних, экспериментальных реализациях расширения Qbayes некоторые многопоточные методы реализованы точно так же, как и однопоточные. Сигнатуры для многопоточных методов зарезервированы для реализации оптимизированных алгоритмов при стабилизации расширения.

Очистка

Дополнительно предлагаются методы очистки данных и моделей:

CREATE OR REPLACE FUNCTION qbayes_drop_graph(имя_модели cstring, имя_графа cstring)
returns BIGINT AS 'MODULE_PATHNAME' language c volatile security definer;

CREATE OR REPLACE FUNCTION qbayes_drop_model(имя_модели cstring)
returns BIGINT AS 'MODULE_PATHNAME' language c volatile security definer;

Возвращаемое значение

При успешном выполнении возвращается 0 или генерируется ошибка при неуспешном.

Ограничения и параметры

Ограничения

Как правило, вероятностные модели содержат большое количество различных параметров и гипотез. На небольших моделях, где число параметров и гипотез исчисляется десятками, скорее всего не возникнет каких либо затруднений. При работе же с большими моделями полезно знать некоторые факты.

Для различных данных в расширении Qbayes намерено выбран типа данных json.

Этот тип описания выбран потому, что позволяет передать большее количество параметров, по сравнению, например, с таблицами СУБД. В таблице можно задать не более 1600 столбцов (см. Ограничения QHB), в то время, как в одной строке json можно разместить несколько тысяч и даже несколько десятков тысяч описаний параметров и гипотез.

Тем ни менее, и у типа данных json есть свои ограничения.
Длина строки не должна превышать размер 1 Гбайт, если она символьная (определяется ограничениями varlena). Если же в ней содержатся бинарные данные, то этот лимит установлен для символьного представления данных, а фактически, бинарные данные ограничены вдвое меньшим лимитом.

Этим ограничениям должны соответствовать строки json с описаниями параметров модели, данными для обучения, обученные модели (поля data таблицы qbayes_model_data) и результаты предсказания.

В некоторых случаях, при работе алгоритмов создаётся ситуация, когда происходит экспоненциальный рост количества ресурсов, требуемых для расчетов. Иногда такая ситуация называется комбинаторным взрывом. Она может быть вызвана, например, слишком большим количеством вариантов значений у зависимых переменных (параметров), хотя для качественного определения вероятностей гипотез и достаточно их основных значений, которые вносят наибольший вклад. Для предотвращения таких ситуаций, в расширении Qbayes есть возможность ограничения расходования ресурсов с помощью параметров.

Параметры

qbayes.max_dependencies

Параметр qbayes.max_dependencies применим для алгоритмов mi (Mutual Information) и mcmc (Markov chain Monte Carlo). Обозначает максимальное количество зависимых переменных, которые может иметь гипотеза.
Значение по умолчанию 5.

qbayes.max_variants

Параметр qbayes.max_variants применим для алгоритмов mi (Mutual Information) и mcmc (Markov chain Monte Carlo). Используется для дополнительного ограничения количества зависимых переменных, которое может иметь гипотеза: если количество комбинаций значений зависимых переменных превышает qbayes.max_variants, то количество зависимых переменных уменьшается до той поры, пока количество комбинаций их значений не станет укладываться в qbayes.max_variants. Рекомендации по установке параметра следующие: фактически qbayes.max_variants вносит максимальный вклад в занимаемую память, потребляя qbayes.max_variants × "количество гипотез" × 16 байт.
Значение по умолчанию 50000 (пятьдесят тысяч).

Замечание
Параметры устанавливаются в файле конфигурации. См. Настройка параметров

Пример использования

Необходимо установить расширение Qbayes:

CREATE EXTENSION IF NOT EXISTS qbayes cascade;

Создадим данные для обучения модели (в примере указан всего один вектор параметров и гипотез, в действительности их должно быть много):

CREATE OR REPLACE VIEW view1 AS SELECT
'{"size": 15, "volume": 18.35, "is_roundy": true, "h1": false}'::json AS value;

Опишем модель:

SELECT qbayes_create_model('MyModel',
  '[{
    "name": "size",
    "type": "discrete_integer",
    "distrib": "discrete",
    "acceptable": [1, 2, 15]
  }, {
    "name": "volume",
    "type": "float8",
    "distrib": "discrete",
    "ranges": [0.1, 1, 10, 100, 1000, 1e4, 1e5, 1e6, 1e7, 1e8]
  }, {
    "name": "is_roundy",
    "is_hypothesis": true,
    "type": "bool",
    "distrib": "bool"
  }, {
    "name": "h1",
    "is_hypothesis": true,
    "type": "bool",
    "distrib": "bool"
  }]'::json);

Можем просмотреть описание модели:

SELECT * FROM qbayes_model_description;

Обучение:

SELECT qbayes_learn('MyModel', 'MyGraph', 'naive', 'view1', 0);

Можем просмотреть данные модели:

SELECT * FROM qbayes_model_data;

Предсказание одного события:

SELECT qbayes_solve('MyModel', 'MyGraph', '{ "size": 15, "volume": 1e6 }'::json );

Предсказание нескольких событий (в примере используется тот же массив данных, на самом деле он может быть другим):

SELECT qbayes_solve_view('MyModel', 'MyGraph', 'view1');

Очистка:

SELECT qbayes_drop_graph('MyModel', 'MyGraph');

SELECT qbayes_drop_model('MyModel');

Примечание
В поставке расширения Qbayes прилагаются и другие примеры с расширенными наборами параметров и гипотез, с использованием различных методов.
Эти примеры можно найти в SQL-скриптах, прилагаемых к расширению.

Замечания, примеры и варианты работы с расширением Qbayes

Предсказания по большому набору параметров

С точки зрения получения результата, два представленных ниже способа выборки вероятностей гипотез равнозначны.

Первый способ:

select qbayes_solve_view('Model1', 'Graph1', 'input_data');

Здесь предполагается, что Model1 и Graph1 некоторые модель и граф. То есть, этап обучения уже прошёл. И совершенно не важно, с каким алгоритмом мы имели дело.

А input_data - это набор параметров, по которому и производится расчёт вероятностей гипотез.

Второй способ:

create function solve_loop() returns setof json
language plpgsql
as $$
declare
  r record;
  rr json;
begin
  for r in (select value from input_data) loop
    select qbayes_solve('Model1', 'Graph1', r.value) into rr;
  return next rr;
end loop;
end
$$

select solve_loop();

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

При выборке первым способом, сокращается время на чтение описания модели, десериализацию описаний параметров и гипотез, это происходит один раз. Во втором же случае, чтение и десериализация происходит при каждом вызове функции qbayes_solve. Если объём модели не очень большой, а объём input_data не запредельный, это сокращение может оказаться несущественным.

Но, в первом случае, можно учесть особенности работы некоторых клиентов при работе с большими выборками. Бывает так, что они ограничивают выборку, "оборачивая" запрос указаниями LIMIT и OFFSET, формируя таким образом порции результата. Иногда это может приводить к повторному расчёту вероятностей при каждом скроллинге к следующей порции. Кроме того, такие ограничения неэффективно работают с контекстом памяти процесса на сервере. Скроллинг может сопровождаться сообщением "transaction left non-empty SPI stack" в системном логе сервера QHB.