Корреляционный разрыв - Correlation gap - Wikipedia

В стохастическое программирование, то корреляционный разрыв это наихудшее соотношение между стоимостью, когда случайные величины коррелированный к стоимости, когда случайные величины независимый.^[1]

В качестве примера,^[1]:6 рассмотрим следующую задачу оптимизации. Учитель хочет знать, идти ему в класс или нет. Есть п потенциальные студенты. Для каждого ученика существует вероятность 1 /п что ученик будет посещать занятия. Если посещает хотя бы один ученик, тогда должен прийти учитель, и его стоимость составляет 1. Если ученики не приходят, то учитель может оставаться дома, и его стоимость равна 0. Цель учителя - минимизировать свои затраты. Это проблема стохастического программирования, потому что ограничения заранее не известны - известны только их вероятности. Итак, есть два случая корреляции между учениками:

• Случай №1: ученики не коррелированы: каждый ученик решает, приходить в класс или нет, с вероятностью подбрасывая монетку ${\displaystyle 1/n}$, независимо от других. Ожидаемая стоимость в этом случае составляет ${\displaystyle 1-(1-1/n)^{n}\approx 1-1/e}$.^{[требуется разъяснение ]}
• Случай № 2: ученики коррелированы: один ученик выбирается случайным образом и приходит в класс, а остальные остаются дома. Обратите внимание, что вероятность того, что каждый студент придет, все еще ${\displaystyle 1/n}$. Однако сейчас стоимость 1.

Разрыв корреляции - это стоимость в случае №2, деленная на стоимость в случае №1, т.е. ${\displaystyle e/(e-1)}$.

^[1] доказать, что корреляционный разрыв ограничен в нескольких случаях. Например, когда функция стоимости представляет собой функция субмодульного набора (как в приведенном выше примере) разрыв корреляции не превышает ${\displaystyle e/(e-1)}$ (так что приведенный выше пример - наихудший случай).

Верхняя граница разрыва корреляции подразумевает верхнюю границу потерь, возникающих в результате игнорирования корреляции. Например, предположим, что у нас есть задача стохастического программирования с субмодульной функцией стоимости. Нам известны предельные вероятности переменных, но мы не знаем, коррелированы они или нет. Если мы просто проигнорируем корреляцию и решим проблему, как если бы переменные были независимы, полученное решение будет ${\displaystyle (e-1)/e}$-приближение к оптимальному решению.

Приложения

Разрыв корреляции использовался для ограничения потери дохода при использовании Байесовская оптимальная цена вместо Байесовский оптимальный аукцион.^[2]

Смотрите также

• Надежная оптимизация
• Теория принятия решения о пропуске информации

Рекомендации

1. Агравал, Шипра; Дин, Ичуань; Сабери, Амин; Е, Инью (2010). «Корреляционная робастная стохастическая оптимизация». Материалы двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 1087. arXiv:0902.1792. Дои:10.1137/1.9781611973075.88. ISBN  978-0-89871-701-3.
2. Ян, Цици (2011). «Дизайн механизмов с помощью корреляционного разрыва». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 710. arXiv:1008.1843. Дои:10.1137/1.9781611973082.56. ISBN  978-0-89871-993-2.