Установить балансировку

Проблема балансировки множеств в математике — это проблема разделения множества на два подмножества, имеющих примерно одинаковые характеристики. Оно естественным образом возникает при планировании экспериментов .

Есть группа предметов. Каждый предмет имеет несколько особенностей, которые считаются бинарными. Например: каждый субъект может быть как молодым, так и старым; либо черный, либо белый; либо высокий, либо низкий; и т. д. Цель состоит в том, чтобы разделить субъектов на две подгруппы: группу лечения (T) и контрольную группу (C), так, чтобы для каждого признака количество субъектов, имеющих этот признак в T, было примерно равно количеству у испытуемых, у которых есть эта особенность в CEg, в обеих группах должно быть примерно одинаковое количество молодых людей, одинаковое количество чернокожих, одинаковое количество высоких людей и т. д.

Матричное представление

Формально задачу балансировки множества можно описать следующим образом.

$m$ количество субъектов в общей популяции.

$n$ это количество потенциальных функций.

Предметы описаны $A$, $n\times m$ матрица с записями в ${0,1}$. Каждый столбец представляет предмет, а каждая строка представляет функцию. $a_{i,j}=1$ если предмет $j$ имеет функцию $i$, и $a_{i,j}=0$ если предмет $j$ не имеет функции $i$.

Разделение на группы описывается $b$, $m\times 1$ вектор с записями в ${-1,1}$. $b_{j}=1$ если предмет $j$ находится в группе лечения Т и $b_{j}=-1$ является предметом $j$ находится в контрольной группе С.

Баланс функций описывается $c=A\cdot b$. Это $n\times 1$ вектор. Числовое значение $c_{i}$ это дисбаланс в характеристиках $i$: если $c_{i}>0$ тогда есть еще предметы с $i$ в T и если $c_{i}<0$ тогда есть еще предметы с $i$ в С.

Дисбаланс данного раздела определяется как:

$I(b)=||A\cdot b||_{\infty }=\max _{i\in 1\dots ,n}|c_{i}|$

Задача балансировки множеств состоит в нахождении вектора $b$ что минимизирует дисбаланс $I(b)$.

Рандомизированный алгоритм

Приблизительное решение можно найти с помощью следующего очень простого рандомизированного алгоритма :

Отправьте каждого субъекта в группу лечения с вероятностью 1/2.

В матричной формулировке:

Выбери элементы из $b$ случайным образом с вероятностью 1/2 для каждого значения в {1,-1}.

Удивительно, но этот алгоритм полностью игнорирует матрицу $A$ достигается небольшой дисбаланс с высокой вероятностью , при наличии большого количества функций . Формально для случайного вектора $b$:

$Prob\left[I(b)\geq {\sqrt {4m\ln n}}\right]\leq {\frac {2}{n}}$

ДОКАЗАТЕЛЬСТВО:

Позволять $k_{i}$ быть общим количеством предметов, которые имеют особенность $i$ (эквивалентно количеству единиц в $i$-я матрица $A$). Рассмотрим следующие два случая:

Простой случай: $k_{i}\leq {\sqrt {4m\ln n}}$. Тогда с вероятностью 1 дисбаланс признака $i$ (что мы отметили $c_{i}$) не более ${\sqrt {4m\ln n}}$.

Трудный случай: $k_{i}>{\sqrt {4m\ln n}}$. Для каждого $j$, позволять $X_{j}=a_{i,j}b_{j}$. Каждый такой $X_{j}$ — случайная величина, которая может иметь значение 1 или -1 с вероятностью 1/2. Дисбаланс в характеристиках $i$ является: $c_{i}=\sum _{j=1}^{m}{X_{j}}$. Поскольку $X_{j}$ являются независимыми случайными величинами по границе Чернова для каждого $a>0$:

$Prob\left[|c_{i}|\geq a\right]\leq 2\exp(-a^{2}/2m)$

Выбирать: $a={\sqrt {4m\ln n}}$ и получите:

$Prob\left[|c_{i}|\geq {\sqrt {4m\ln n}}\right]\leq {\frac {2}{n^{2}}}$

Союзом связанным ,

$Prob\left[\exists i:|c_{i}|\geq {\sqrt {4m\ln n}}\right]\leq {\frac {2}{n}}$.