상관격차

확률형 프로그래밍에서 상관관계 격차는 랜덤 변수가 독립적일 때 비용과 상관관계가 있을 때 비용 사이의 최악의 경우 비율이다.^[1]

예를 들어 다음과 같은 최적화 문제를 생각해 보십시오.^[1]^{: 6} 선생님은 수업에 올지 안 올지 알고 싶어 한다. 잠재 학생이 없다. 학생 한 명당 출석 확률은 1/n이다. 만약 적어도 한 명의 학생이 출석한다면, 선생님은 반드시 오셔야 하며 비용은 1이다. 만약 학생들이 참석하지 않는다면, 선생님은 집에 있을 수 있고 그의 비용은 0이다. 선생님의 목표는 비용을 최소화하는 것이다. 이는 제약조건을 미리 알 수 없기 때문에 확률적 프로그래밍 문제다. 그 확률만 알 수 있다. 현재, 학생들 간의 상관관계에 관한 두 가지 경우가 있다.

사례 #1: 학생들은 무관심하다: 각각의 학생들은 다른 학생들과 독립적으로 $1/n$ 1 $1/n$ / $1/n$ $1/n$ 의 동전을 던짐으로써 수업에 올지 말지를 결정한다. 이 경우에 예상되는 비용은 $1-(1-1/n)^{n}\approx 1-1/e$ - $1-(1-1/n)^{n}\approx 1-1/e$ ( $1-(1-1/n)^{n}\approx 1-1/e$ - $1-(1-1/n)^{n}\approx 1-1/e$ / n $1-(1-1/n)^{n}\approx 1-1/e$ ) $1-(1-1/n)^{n}\approx 1-1/e$ $1-(1-1/n)^{n}\approx 1-1/e$ 1 $1-(1-1/n)^{n}\approx 1-1/e$ - $1-(1-1/n)^{n}\approx 1-1/e$ / e ${\displaystyle 1-(1-1/n)^{n}\$ 약 $1-1/e}$ 입니다 $1-(1-1/n)^{n}\approx 1-1/e$ ^{[clarification needed]}
사례 #2: 학생들은 상관관계가 있다: 한 학생은 무작위로 선발되어 수업에 오는 반면, 다른 학생들은 집에 머무른다. 각 학생이 올 확률은 여전히 $1/n$ / $1/n$ $1/n$ 이지만, 이제 비용은 1이다 $1/n$

상관관계 격차는 #2를 사례 #1의 비용으로 나눈 $e/(e-1)$ 이다. e $e/(e-1)$ / $e/(e-1)$ ( $e/(e-1)$ - $e/(e-1)$ ) ${\displaystyle$ e $/(e-1)}$ 이다 $e/(e-1)$

^[1] 여러 경우에서 상관관계 격차가 한정되어 있음을 증명한다. 예를 들어, 비용 함수가 서브모듈라 집합 함수인 경우( $e/(e-1)$ 의 예와 같이) 상관관계 격차는 최대 $e/(e-1)$ / $e/(e-1)$ ( e $e/(e-1)$ - $e/(e-1)$ ) $e/(e-1)$ 이다( $e/(e-1)$ 따라서 위의 예는 최악의 경우).

상관관계 간격의 상한은 상관관계를 무시한 결과 발생하는 손실에 대한 상한을 의미한다. 예를 들어, 서브모듈러 비용 함수에 확률적 프로그래밍 문제가 있다고 가정해 보십시오. 변수의 한계 확률은 알고 있지만 상관관계가 있는지는 알 수 없다. 상관 관계를 무시하고 변수가 독립된 것처럼 $(e-1)/e$ 를 해결하면 결과 해결책은 최적 솔루션에 대한 ( $(e-1)/e$ - $(e-1)/e$ ) $(e-1)/e$ / e $(e-1)/e$ - 근사치가 $(e-1)/e$ 된다.

적용들

상관관계 격차는 베이시안 최적 경매 대신 베이시안 최적 가격을 사용할 때 수익 손실을 막는데 사용되었다.^[2]

참고 항목

참조

^ ^a ^b ^c Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "Correlation Robust Stochastic Optimization". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1087. arXiv:0902.1792. doi:10.1137/1.9781611973075.88. ISBN 978-0-89871-701-3.
^ Yan, Qiqi (2011). "Mechanism Design via Correlation Gap". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 710. arXiv:1008.1843. doi:10.1137/1.9781611973082.56. ISBN 978-0-89871-993-2.

[adsy10-1] Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "Correlation Robust Stochastic Optimization". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1087. arXiv:0902.1792. doi:10.1137/1.9781611973075.88. ISBN 978-0-89871-701-3.

[y10-2] Yan, Qiqi (2011). "Mechanism Design via Correlation Gap". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 710. arXiv:1008.1843. doi:10.1137/1.9781611973082.56. ISBN 978-0-89871-993-2.

[1]

[2]

Search

상관격차

네임스페이스

더

적용들

참고 항목

참조