[Week 1] Statistical estimation [2]

ESC·2023년 12월 13일

2023-Spring

목록 보기

2/9

4. Chebyshev and Chernoff bounds

Chebyshev bounds

이번에는 우리가 잘 아는 확률에 관한 부등식들을 살펴보고, 이들의 더욱 일반적인 형태가 컨벡스 최적화 문제로 표현될 수 있음을 보일 것이다. 먼저 우리가 잘 아는 $\mathbb{R}$ 에서 정의된 $X$ 에 대한 Markov inequality와 Chebyshev inequality를 살펴보자.

1. Markov inequality.

확률변수 $X$ 와 non negative function $u(x)$ , 상수 $k$ 에 대해 $\mathbb{P}(u(X) \geq k) \leq \frac{E(u(X))}{k}$ 이다.

2. Chebyshev inequality.

평균이 $\mu$ , 분산이 $\sigma^2$ 인 확률변수 $X$ 와 상수 $k$ 에 대해 $\mathbb{P}(|X-\mu| \geq k) \leq \frac{\sigma^2}{k}$ 이다.

Markov inequality를 일반화해, $S\subseteq \mathbb{R}^m$ 에서 정의된 확률변수 $X$ 에 대하여 $\mathbb{P}(X \in C),\,\,C\subseteq S$ 의 upper bound를 찾고 싶다고 하자. 먼저 $C$ 에 대한 indicator function $1_C(z)=\begin{cases}1\,\,\,\,z\in C\\0\,\,\,\,z\notin C \end{cases}$ 를 정의하자. 우리가 가진 사전 정보는 $X$ 에 대한 어떤 함수들 $f_i$ 에 대한 평균 $E f_i(X) = a_i$ 이다. (이 때 $f_0(z) = 1$ 로 설정하자. 그러면 $Ef_0(X) =a_0 = 1$ 로 절편 역할을 한다.)
이제 그들의 linear combination $f(z) = \sum_{i=0}^n x_i f_i(z)$ 를 정의하자. 이때 임의의 $z\in S$ 에 대하여 $f(z) \geq 1_C(z)$ 가 되도록 linear combination을 제한하면, $E f(z)=a^Tx \geq E 1_C(z) = \mathbb{P}(X \in C)$ 임을 알 수 있다. 이때 $f(z)$ 와 $1_C(z)$ 를 최대한 가깝게 선택하면 확률에 대한 가장 타이트한 upper bound를 얻을 수 있다. 즉, 어떤 집합 $C$ 에서의 확률에 대한 upper bound는 $C$ 의 바깥쪽 경계를 linear function으로 최대한 타이트하게 근사시키는 최적화 문제와 같다. (물론 어디까지나 선형 근사이므로 다른 형태의 더 타이트한 근사가 존재할 수 있다.) 이를 수식으로 정리하면 아래와 같다.

$\text{minimize}\,\,a^Tx = x_0 + a_1 x_1 + \cdots a_n x_n$
$\text{subject to}\,\,\sum_{i=0}^n x_if_i(z) \geq 1\,\,\forall z \in C$
$\quad\quad\quad\quad\,\,\,\,\sum_{i=0}^n x_if_i(z) \geq 0\,\,\forall z\in S \backslash C$

이 문제는 constraint가 linear inequality 형태이므로 컨벡스 최적화 문제이다. 가령 여기에서 $S = \mathbb{R}_+,\,\,C = [1, \infty),\,\,f_1(z)=z,\,\,Ef_1(z) = \mu \leq 1$ 로 설정하면 objective는 $x_0 + x_1 \mu$ , 제약식은 $x_0 + x_1 \geq 1$ 과 $x_0,\,x_1 \geq 0$ 으로 축약되는 것을 알 수 있다. $0\leq \mu \leq 1$ 이므로 이 문제의 최적값은 $x_0 = 0,\,x_1=1$ 이다. 따라서 Markov inequality의 가장 단순한 형태인 $\mathbb{P}(X \geq 1) \leq \mu$ 가 도출된다.

이번에는 확률변수 $X$ 의 1, 2차 적률(moment)에 대한 정보인 $EX = a \in \mathbb{R}^m,\,\,EXX^T = \Sigma \in \mathbb{S}^m$ 를 알고 있다고 해 보자. 이것은 우리가 $m$ 개의 $z_1,\,...,z_m$ 의 평균과 $m(m+1)/2$ 개의 $z_1z_1,\,...,z_mz_m$ 의 평균에 대한 정보를 가진 것과 같다. 이번에는 이들의 결합인 $f(z) = z^TPz + 2q^Tz + r,\,P\in \mathbb{S}^m,\,q\in \mathbb{R}^m,\,\,r\in \mathbb{R}$ 의 quadratic function으로 선택하자. 그러면 $Ef(X) = E(X^TPX + 2q^TX + r) = E(\textbf{tr}(PXX^T)) + 2E(q^TX) + r = \textbf{tr}(\Sigma P) + q^Ta + r$ 이다. 이때 모든 $z$ 에 대해 $f(z) \geq 0$ 의 제약식은 linear matrix inequality $\begin{bmatrix} P & q \\ q^T & r \end{bmatrix} \succeq 0$ 과 동치이다. 이제 Chebyshev bound 문제를 다변수로 확장해 보자. 그러면 우리가 probability bound를 찾고자 하는 집합 $C$ 는 다음과 같은 polyhedron의 바깥쪽 집합으로 정의할 수 있다.
$C = \mathbb{R}^m \backslash\mathcal{P},\,\,\mathcal{P}=\{z\,|a_i^Tz < b_i,\,i=1,\,...,\,k\}$
이제 $z\in C$ 에 대해 $f(z) \geq 1$ 의 제약식은 $a_i^T z \geq b \implies z^TPz + q^Tz + r \geq 1$ 로 표현할 수 있다. 이제 아래의 S-procedure를 이용해 이 제약식 역시 convex constraint로 바꿀 수 있다. 증명은 생략하겠다.

S-procedure
$F_i\in \mathbb{S}^n,\,g_i \in \mathbb{R}^n,\,h_i\in\mathbb{R}$ 에 대하여

$x^TF_1x + 2g_1^T x + h_1 \geq 0 \implies x^TF_2x + 2g_2^T x + h_2 \geq 0 \iff \exists \lambda \geq 0\,\,\text{s.t.}\,\,\begin{bmatrix} F_2 & g_2 \\ g_2^T & h_2 \end{bmatrix} \succeq \lambda\begin{bmatrix} F_1 & g_1 \\ g_1^T & h_1 \end{bmatrix}$

이를 적용하면 이 제약식은 $\exists \tau_i,\,i=1,\,...,\,k\,\,\text{s.t.}\,\,\begin{bmatrix} P & q \\ q^T & r-1 \end{bmatrix}\succeq \tau_i \begin{bmatrix} 0 & a_i/2 \\ a_i^T/2 & -b_i \end{bmatrix}$ 로 표현될 수 있다. 이제 알아낸 사실들을 정리해 Chebyshev bound를 최적화 문제로 표현하면 아래와 같다.

$\text{minimize}\,\,\textbf{tr}(\Sigma P) + q^Ta + r$
$\text{subject to}\,\,\begin{bmatrix} P & q \\ q^T & r \end{bmatrix} \succeq 0,\,\,\begin{bmatrix} P & q \\ q^T & r-1 \end{bmatrix}\succeq \tau_i \begin{bmatrix} 0 & a_i/2 \\ a_i^T/2 & -b_i \end{bmatrix}$
$\quad\quad\quad\quad\quad\tau_i \geq 0\,\,\forall i=1,\,...,\,k$

이 문제는 $P,\,q,\,r,\tau_1,\,...,\,\tau_k$ 에 대한 SDP에 속한다. 그리고 Optimal value인 $\alpha$ 는 평균이 $a$ 이고 covariance가 $\Sigma$ 인 임의의 probability distribution에서 $\mathbb{P}(X\in C)$ 의 upper bound이다.

Chernoff bounds

3. Chernoff bounds.
$\mathbb{R}$ 에서 정의된 $X$ 에 대하여
$\mathbb{P}(X \geq u) \leq \underset{\lambda \geq 0}{\inf}\,E(e^{\lambda(X-u)}) \iff \log \mathbb{P}(X \geq u) \leq \underset{\lambda \geq 0}{\inf}\{-\lambda u + \log E e^{\lambda X}\}$

이 부등식은 사실 Markov inequality에서 $u(x) = e^{tx},\,k=e^{tu}$ 로 설정한 것에 불과하다. 그리고 mgf에 로그를 취한 형태인 $\log E e^{\lambda X}$ 를 cumulant generating function이라고 한다. 이 함수는 항상 convex이기 때문에 이 문제의 목적함수 역시 convex이다. 가령 $X$ 가 standard normal distribution일 때 $\log M(\lambda) = \frac{\lambda^2}{2}$ 이고 $-\lambda u + \lambda^2/2$ 의 infimum은 $\lambda=u$ 일 때이므로 $\mathbb{P}(X \geq u) \leq e^{-u^2/2}$ 의 bound를 얻을 수 있다.

이제 이것을 $\mathbb{R}^m$ 에서 정의된 $X$ 에 대해 확장해 보자. 아까와 같이 우리의 목표는 $\mathbb{P}(X \in C)$ 에 대한 probability bound를 찾는 것이다. 물론 수치적분이나 몬테카를로 시뮬레이션 등 $\mathbb{P}(X \in C)$ 를 계산할 방법이 없는 것은 아니지만 이는 보통 아주 많은 계산량을 요구하기 때문에 최적화의 관점에서 더 나은 방법을 찾아보자. Indicator function $1_C$ 를 아까와 동일하게 정의하고, $\lambda \in \mathbb{R}^m$ 과 $\mu \in \mathbb{R}$ 에 대해 $f(z) = e^{\lambda^Tz + \mu}$ 로 정의하자. 이전의 설정과 동일하게 $f(z) \geq 1_C(z)$ 가 만족된다면 $\mathbb{P}(X \in C) = E 1_C(X) \leq E f(X)$ 의 bound를 찾을 수 있다. 우선 모든 $z$ 에 대해 $f(z) \geq 0$ 은 항상 만족되고, $z \in C$ 에 대해 $f(z) \geq 1$ 을 만족하려면 $\lambda^T z + \mu \geq 0$ 이 만족되어야 한다. 따라서 이 조건이 만족될 경우

$\log \mathbb{P}(X \in C) \leq \mu + \log E \exp(\lambda^TX)$ 를 찾을 수 있다. 여기서부터 아래와 같이 Chernoff bound의 일반적인 형태를 얻는다.

$\begin{aligned}\log \mathbb{P}(X \in C) &\leq \inf\{\mu + \log E \exp(\lambda^TX)\,|\, -\lambda^T z \leq \mu\}\\ &= \underset{\lambda}{\inf}\left(\underset{z\in C}{\sup}(-\lambda^T z) + \log E \exp(\lambda^T X)\right)\\ &= \inf(S_C(-\lambda) + \log E \exp(\lambda^T X)) \end{aligned}$

여기에서 $S_C$ 는 $C$ 의 support function을 뜻한다. 이 문제는 컨벡스 최적화 문제이다. 밑의 예제를 통해 좀 더 살펴보자.

Example. Chernoff bound for a Gaussian variable on a polyhedron

$X \sim N_m(\mathbf{0}, I)$ 라고 가정해 보자. 그러면 cumulant generating function은 $\log E \exp(\lambda^T X) = \lambda^T \lambda /2$ 이다. 그리고 $C$ 를 $\{x\,|\,Ax \preceq b \}$ 의 polyhedron으로 잡자. 그리고 support function $S_C$ 를 dual로 표현하면 아래와 같다.

\begin{aligned} S_C(y) &= \sup\{y^T x\,|\,Ax \preceq b \}\\ &= -\inf\{-y^T x\,|\, Ax \leq b\}\\ &= -\sup\{-b^T u\,| \,A^T u = y,\,u \succeq 0\}\quad\quad\quad\text{by LP duality}\\ &= \inf\{b^T u\,| \,A^T u = y,\,u \succeq 0\} \end{aligned}

이를 위에서 얻은 식에 대입하면
$\log \mathbb{P}(X \in C) \leq \underset{\lambda}{\inf}(S_C(-\lambda) + \log E \exp(\lambda^T X)) = \underset{\lambda}{\inf}\, \underset{u}{\inf}\{b^T u + \lambda^T \lambda/2 \,|\, u \succeq 0,\,A^T u + \lambda = 0\}$
이다.

따라서 Chernoff bound는 $u,\,\lambda$ 에 대한 아래 문제의 optimal value와 같다.

$\text{minimize}\,\,b^T y + \lambda^T \lambda/2$
$\text{subject to}\,\,u \succeq 0,\,\,A^Tu + \lambda = 0$

이 문제에 대한 기하적인 해석이 가능한데, 우선 위 문제는 아래와 동치이다.

$\text{minimize}\,\,b^T u + (1/2)||A^Tu||_2^2$
$\text{subject to}\,\,u \succeq 0$

그리고 이 문제는 아래 문제의 dual이다.

$\text{maximize}\,\,-(1/2)||x||_2^2$
$\text{subject to}\,\,A^Tx \preceq b$

따라서 $\mathbb{P}(X \in C) \leq \exp(-\textbf{dist}(0,C)^2/2)$ 이다. 이 때 $\textbf{dist}(0,C)$ 는 원점에서 $C$ 까지의 Euclidean distance를 뜻한다.

5. Experiment design

Optimal experiment design이란 실험계획법의 한 분야로, 우리가 가정한 모델의 파라메터의 편향(bias)과 분산(variance)를 최소화할 수 있는 design matrix를 구성하는 것이다. 어떤 observation $a_1,\,…,a_m$ 으로부터의 linear measurement 모델인 $y_i = a_i^T x + w_i,\,i=1,\,…,\,m$ 을 고려하자. 이 때 $w_i$ 가 unit variance를 지닌 iid gaussian noise라면, 우리는 이 모델의 mle가 least-squares solution인 $\hat{x} = \left(\sum_{i=1}^m a_i a_i^T\right)^{-1} \sum_{i=1}^m y_i a_i$ 임을 알고 있다. 그리고 estimation error $e = \hat{x} - x$ 의 평균은 0이고 covariance matrix는 $E ee^T = \left(\sum_{i=1}^m a_i a_i^T \right)^{-1}$ 이다. 이제부터 이 행렬을 $E$ 라고 지칭하자.
이때 paramter $x$ 에 대한 $\alpha$ - confidence region은 $\{x\,|\,(x-\hat{x})^T E^{-1} (x-\hat{x}) \leq F_{1-\alpha}(n, m-n)\}$ 으로 나타난다. 행렬 $E$ 를 구성하는 $a_1,\,…,\,a_m$ 이 $p$ 개의 가능한 test vector $v_1,\,…,\,v_p \in \mathbb{R}^n$ 으로부터 선택되었다고 가정하자. 그리고 experiment design의 목적은 $E$ 를 가능한 한 작게 만들 수 있는 $a_i$ 들을 선택하는 것이다. 즉 가능한 $p$ 개의 실험으로부터, 최대한의 정보를 뽑아낼 수 있는(most informative) $m$ 개의 measurement를 찾아내는 것이 목적이다. $m_j$ 를 $a_i$ 가 $v_j$ 의 값을 가지도록 선택된 개수라고 하자. 그러면 $m_1 + \cdots m_p = m$ 임을 알 수 있고, $E = \left(\sum_{i=1}^m a_i a_i^T \right)^{-1} = \left(\sum_{j=1}^p m_jv_j v_j^T \right)^{-1}$ 이다. 이때 $\{v\}$ 가 알려져 있기 때문에, error covariance는 각각의 실험이 선택된 수 $\{m_j\}$ 에만 의존한다. 따라서 변수 $\{m_j\}$ 에 대한 이 최적화 문제는 아래와 같은 vector optimization 문제로 나타낼 수 있다.

$\text{minimize (w.r.t.}\,\mathbb{S}_+^n)\,\,E = \left(\sum_{j=1}^p m_jv_j v_j^T \right)^{-1}$
$\text{subject to}\,\,m_j \geq 0,\,\,m_1 + \cdots m_p = m,\,\,m_j \in \mathbb{Z}$

만일 positive semidefinite cone 상에서 $E \preceq \tilde{E}$ 라면 우리는 $E$ 를 선택했을 때, $\tilde{E}$ 보다 임의의 $q$ 에 대하여 $q^Tx$ 의 더 나은(분산이 작은) estimator를 얻을 수 있다. 이제 이 문제의 다양한 변형에 대해 알아보자.

The relaxed experiment design problem

위의 문제는 integer programming 문제이기 때문에 non-convex이고 따라서 큰 규모에서는 풀기 매우 복잡한데, 간단한 조작을 통해 이 문제에 대처할 수 있다. $\lambda_i = m_i/m$ 라고 하자. 즉 $\lambda_i$ 는 실험 $i$ 의 relative frequency를 뜻한다. 그리고 위의 문제를 $\lambda$ 에 대한 문제로 바꾸면 아래와 같다.

$\text{minimize (w.r.t.}\,\mathbb{S}_+^n)\,\,E = (1/m)\left(\sum_{j=1}^p \lambda_iv_i v_i^T \right)^{-1}$
$\text{subject to}\,\,\lambda \succeq 0,\,\,\mathbf{1}^T\lambda = 1$

이것을 relaxed experiment design problem이라고 한다. 이 문제는 위와 달리 컨벡스 최적화 문제이다. Constraint 중의 하나인 정수 조건이 빠졌기 때문에 이 문제의 optimal value는 원래 문제의 optimal value의 lower bound이다. 만약 relaxed problem으로부터 정수 조건을 다시 맞추기 위해 $m_i = \textbf{round}(m\lambda_i)$ 로 정의하면 이 솔루션은 sub-optimal solution이 된다. 그리고 sub-optimal한 $\tilde{\lambda_i} = (1/m)\textbf{round}(m\lambda_i)$ 로 정의하면 $|\lambda_i - \tilde{\lambda_i}| \leq 1/2m$ 이므로 $m$ 이 커짐에 따라, 즉 데이터가 많아짐에 따라 $\lambda$ 와 $\tilde{\lambda}$ 는 거의 동일해진다.

그리고 $\lambda$ 는 probability distribution의 관점으로도 해석될 수 있다. 우리의 $\lambda$ 에 대한 선택은 각 실험 $a_i$ 가 $\lambda_j$ 의 확률로 $v_j$ 가 된다는 것을 의미한다. 따라서 $\lambda$ 는 random experiment의 optimal probability distribution이 된다.

Scalarizations

위의 vector optimization 문제를 스칼라에 대한 문제로 바꾸는 몇가지 알려진 기준들에 대해 알아보자. 여기부터는 기본적으로 convexity를 위해 relaxed problem을 전제로 한다.

D-optimal design

이 기준은 confidence ellipsoid의 부피를 가장 작게 만들기 위한 것으로 아래와 같다.

$\text{minimize}\,\,\log \det\left(\sum_{i=1}^p \lambda_iv_i v_i^T \right)^{-1}$
$\text{subject to}\,\,\lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

E-optimal design

이 기준은 $E$ 의 norm(maximum eigenvalue)를 최소화하는 것으로, confidence ellipsoid의 지름(diameter)을 가장 짧게 만들기 위한 것이다. 또한 이 기준은 $||q||_2 = 1$ 인 임의의 $q$ 에 대하여 $q^Te$ 의 분산을 최소화하는 것으로도 해석될 수 있다. 표현은 아래와 같다.

$\text{minimize}\,\, \Big\lVert\left(\sum_{i=1}^p \lambda_iv_i v_i^T \right)^{-1}\Big\rVert_2$
$\text{subject to}\,\,\lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

이 문제는 $t\in \mathbb{R}$ 와 $\lambda\in \mathbb{R}^p$ 에 대한 아래의 SDP와 동일한 문제이다.

$\text{maximize}\,\,t$
$\text{subject to}\,\, \sum_{i=1}^p \lambda_iv_i v_i^T \succeq tI$
$\quad\quad\quad\quad\,\,\,\,\lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

A-optimal design

이 기준은 $E$ 의 대각합을 최소화하는 것으로, error의 제곱의 평균을 최소화하는 기준이며 이유는 아래와 같다.

$E||e||_2^2 = E \textbf{tr}(ee^T) = \textbf{tr}\,E.$

그리고 문제 표현은 아래와 같다.

$\text{minimize}\,\,\textbf{tr}\left(\sum_{i=1}^p \lambda_iv_i v_i^T \right)^{-1}$
$\text{subject to}\,\,\lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

이 문제 역시 E-optimal design처럼 아래와 같은 SDP로도 표현할 수 있다.

$\text{minimize}\,\,\mathbf{1}^Tu$
$\text{subject to}\,\,\begin{bmatrix} \sum_{i=1}^p \lambda_i v_i v_i^T & e_k \\ e_k^T & u_k \end{bmatrix} \succeq 0,\,\,k=1,\,…,\,n$
$\quad\quad\quad\quad\,\,\,\, \lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

Optimal experiment design and duality

위 세 문제들의 dual problem은 아래와 같다.

Dual of D-optimal, with variable $W \in \mathbb{S}^n$ , domain $\mathbb{S}_{++}^n$

$\text{maximize}\,\,\log \det W + n \log n$
$\text{subject to}\,\,v_i^T W v_i \leq 1,\,\,i=1,\,…,\,p$

Dual of E-optimal, with variable $W \in \mathbb{S}^n$

$\text{maximize}\,\,\textbf{tr}\,W$
$\text{subject to}\,\,v_i^T W v_i \leq 1,\,\,i=1,\,…,\,p$
$\quad\quad\quad\quad\,\,\,\,W \succeq 0$

Dual of A-optimal, with variable $W \in \mathbb{S}^n$

$\text{maximize}\,\,(\textbf{tr}\,W^{1/2})^2$
$\text{subject to}\,\,v_i^T W v_i \leq 1,\,\,i=1,\,…,\,p$

예시로 D-optimal design의 dual을 도출하는 과정을 살펴보자.먼저 아래와 같이 primal problem을 $X$ 에 대해 재표현한다.

$\text{minimize}\,\,\log \det X^{-1}$

$\text{subject to}\,\,X = \sum_{i=1}^p\lambda_iv_i v_i^T,\,\,\lambda \succeq 0,\,\,\mathbf{1}^T \lambda =1$

그리고 dual variable을 도입해 라그랑지안을 도출하면

$L(X,\lambda,Z,z,\nu) = \log \det X^{-1} + \textbf{tr}\left(Z \left(X - \sum_{i=1}^p \lambda_i v_i v_i^T\right)\right) - z^T \lambda + \nu(\mathbf{1}^T \lambda - 1)$

이때 $X$ 에 대해 미분한 그래디언트를 0으로 놓으면 $-X^{-1} + Z = 0$ 이고, $\lambda_i$ 에 대한 minimum은 $-v_i^T Z v_i - z_i + \nu = 0$ 일 때만 존재한다. 따라서 이 조건을 대입하면 dual problem은

$\text{maximize}\,\,n + \log \det Z - \nu$

$\text{subject to}\,\,v_i^T Z v_i \leq \nu,\,\,i=1,\,…,\,p$

이고, $W = Z/\nu$ 로 놓은 뒤 $\nu$ 에 대해 최적화해 빼내 주면 위의 문제가 도출된다.

위 문제들의 optimal solution $W^*$ 는 $v_1,\,…,\,v_p$ 를 포함하고 원점을 중점으로 갖는 minimal ellipsoid $\{x\,|\,x^T W^* x \leq 1 \}$ 을 결정한다. 또한 $W^*$ 와 $\lambda^*$ 는 complementary slackness 조건을 만족하는데, 이는 모든 $i$ 에 대해 $\lambda_i^*(1-v_i^T W^* v_i) = 0$ 을 만족하므로 optimal experiment design에서는 ellipsoid의 표면에 위치한 실험들만을 선택하게 된다는 뜻이다.