[3주차] Computation of the NPMLE for type-I interval censored data

참고교재

• Groeneboom and Jongbloed (2014), Nonparametric Estimation under Shape Constraints, Cambridge University Press.

 

1. Review

지난 2.1절에서는 단조 증가하는 함수 $r$을 추정하는 방법을 알아보았다.

Lemma 2.1
$\hat{r}$이 convex cone $C=\{(r_1,~r_2,~\cdots,~r_n)\in\reals^n ~|~ r_1 \le r_2 \le ~\cdots r_n\}$에서 strictly convex function

을 최소화하는 것의 필요충분조건은

이다.

$r$의 추정함수 $\hat{r}$을

의 convex minorant의 left derivative로 정의한다면 Lemma 2.1의 등식/부등식 조건을 만족하여, $Q(r)$의 최소화원으로서 역할을 할 수 있었다. 여기서 기억해야 할 점은, 우리가 $Q(r)$과 같은 quadratic form의 최소화원을 알고 있다는 것이다.

 

2. Newton Algorithm

Newton Algorithm은 (convex) function의 최소화원을 찾기 위한 알고리즘이다. 즉, 어떤 (convex) function $\phi : \reals^n \rightarrow \reals$를 최소화하는 $\hat{\theta} \in \reals^n$를 찾는 알고리즘이다. 알고리즘은 $\theta^{(0)},~\theta^{(1)}, \theta^{(2)}, \cdots$와 같이 점진적으로 $\hat{\theta}$를 찾아가게 된다.

• 1. 초기값 $\theta^{(0)}$를 설정
• 2. $k\ge0$에 대하여, $~\theta^{(k+1)}=A(\theta^{(k)})$
     $= \argmin_{\theta} \bigg( \phi(\theta^{(k)})+(\theta-\theta^{(k)})^\mathrm{T}\nabla\phi(\theta^{(k)})+{1\over2}(\theta-\theta^{(k)})^\mathrm{T}\nabla^2\phi(\theta^{(k)})(\theta-\theta^{(k)}) \bigg)$
     으로 정의
• 3. 종료조건 달성 시까지 2를 반복

하지만 Newton Algorithm은 $\phi$의 실제 최소화원으로 수렴을 보장하지 못한다는 단점이 있다. 이는 $\phi$가 convex function이더라도 보장되지 않는다.

 

3. Iterative Convex Minorant Algorithm

Newton Algorithm을 보완할 새로운 알고리즘을 알아보자. 이 알고리즘은 convex function이 유일한 최소화원을 갖는다면, 반드시 그 최소화원으로의 수렴성을 보장하는 알고리즘이다. 다음과 같이 용어를 정의하고, 3가지를 가정하자.

$\phi$ : 목적함수(objective funtion) - 최소화되길 원하는 함수
$C=\{r \in \reals^n~:~r_1 \le r_2 \le \cdots \le r_n\}$ : convex set

• $\phi$ : convex, continuous on $C$
• $\phi$ : continuously differentiable on $\{\beta \in \reals^n ~:~\phi(\beta)< \infin \}$
• $\hat{\beta}$ : unique minimum of $\phi$ on $C$ exist

이로부터 다음 동치관계가 성립한다.

이는 왼쪽과 같이 convex set 내부에 global minimum이 존재한다면 $\nabla\phi(\hat{\beta})=\mathbf{0}$이 되어 등식/부등식이 성립하고, 오른쪽과 같이 convex set 외부에 있더라도 최소화원은 convex set의 경계에 위치하게 되어 등식/부등식이 성립한다.

위 동치조건은 추후 Modified Iterative Convex Minorant Algorithm의 종료 조건으로 사용된다.

Iterative Convex Minorant Algorithm (이하 ICM)은 Newton Method와 유사한 방식으로 최소화원을 찾아간다.

• 1. 초기값 $\beta^{(0)}$을 설정
• 2. 이전 값$(\beta^{(k)})$에서의 함수 $\phi$의 근사 함수의 최소화원을 다음 값$(\beta^{(k+1)})$으로 설정
• 3. 종료조건 달성 시까지 2를 반복

2번에서의 근사함수는 다음과 같이 정의된다. $\gamma \in C$ 근방의 임의의 $\beta$에 대하여, $\phi(\gamma+(\beta-\gamma))$의 근사함수는

이고, 이러한 근사 함수를 최소화하는 최소화원 $B(\gamma)$는

이다. $B(\gamma)$는 quadratic form이므로, 앞선 Lemma 2.1에서와 같이 convex minorant를 이용하면 $B(\gamma)$를 구할 수 있다.

이러한 알고리즘은 $\phi$를 최소화하는 것이 아닌, $\phi$의 근사함수를 최소화하는 과정을 나타낸다. 그렇다면 근사함수를 최소화하는 것이 $\phi$를 최소화하는 것에 도움이 될까? Lemma 7.1은 그에 대한 일부 답변을 제시한다.

Lemma 7.1
앞선 가정을 만족하는 $\phi$와, $\phi(\beta)<\infin$을 만족하는 모든 $\beta \in C \setminus\{\hat{\beta}\}$에 대하여, 충분히 작은 $\lambda>0$가 존재하여

가 성립한다.

즉, ICM의 방법이 $\phi$를 최소화하는 방향임은 보장한다.

Lemma 7.1 Proof
$\psi~:~[0, 1] \rightarrow \reals$를 다음과 같이 정의하자.

[Claim] : $\psi'(0+)=(B(\beta)-\beta)^\mathrm{T}\nabla\phi(\beta)<0$
만약 위 Claim이 증명된다면

와 같이 Lemma 7.1이 증명된다.

다음 두 사실로부터,

다음 부등식이 성립한다.

하지만 $\beta \in C \setminus \{\hat{\beta}\}$이므로 $D(\beta)$는 positive definite이고, 따라서

가 성립한다.

Lemma 7.1은 감소 방향에 대한 해답은 주지만, $\hat{\beta}$까지 감소하는지에 (=최소화원으로의 수렴성) 대해서는 보장하지 않는다. 이를 보완하는 알고리즘을 소개한다.

 

4. Modified Iterative Convex Minorant Algorithm

Modified Iterative Convex Minorant Algorithm (이하 MICM)은 ICM의 알고리즘에 $\hat{\beta}$으로의 수렴성을 더한 방법이다. ICM에서의 방법과 같이 $\beta^{(0)}, \beta^{(1)}, \beta^{(2)}, \cdots$으로 $\hat{\beta}$를 점진적으로 찾아가며, 그 관계는 다음과 같다.

위 관계식을 그림으로 살펴보자. $\phi$를 최소화하는 것이 목표지만, 이를 $\psi$ 관점에서 살펴볼 것이다.

1) $\phi(B(\beta^{(k)})) < \phi(\beta^{(k)})+(1-\epsilon)\nabla\phi(\beta^{(k)})^\mathrm{T}(B(\beta^{(k)})-\beta^{(k)})$
부등식의 오른쪽 항은 $\phi(\beta^{(k)})+(1-\epsilon)\psi'(0)$과 같다. 이는 아래와 같이 기울기가 $(1-\epsilon)\psi'(0)$이고 $(0, \phi(\beta^{(k)}))$를 지나는 직선이 $\lambda=1$에서의 함숫값과 같다.

이 직선은 항상 감소하며, 기울기에 $1-\epsilon$을 곱함으로써 그래도 이 직선보다는 더 감소했으면 좋겠다의 정도로 해석할 수 있다. 부등식 조건에서는 $\phi(B(\beta^{(k)}))$가 직선보다 아래에 위치하므로 충분히 감소했다고 판단하여 $\beta^{(k+1)} = \phi(B(\beta^{(k)}))$로 정의하였다고 볼 수 있다.

2) $\phi(B(\beta^{(k)})) \ge \phi(\beta^{(k)})+(1-\epsilon)\nabla\phi(\beta^{(k)})^\mathrm{T}(B(\beta^{(k)})-\beta^{(k)})$
1)의 해석에 따라, 기대한 만큼 충분히 감소하지 못했을 경우다. 아래 그림은 그럼에도 $\phi(B(\beta^{(k)}))<\phi(\beta{(k)})$인 상황이지만, 일반적으로 이렇다고 보장할 수 없다. 따라서 어떤 적절한 $0<\lambda<1$을 선택하여, 그 때의 $\psi(\lambda)$를 $\beta^{(k+1)}$로 선정할 것이다.

기대한 만큼 충분히 감소한 결과를 원하므로, 기울기가 $(1-\epsilon)\psi'(0)$이고 $(0, \phi(\beta^{(k)}))$을 지나는 직선보다 아래 영역에서 $\lambda$를 선택할 것이다. 대신 너무 조금 감소하는 경우를 배제하기 위해 기울기가 $\epsilon\psi'(0)$이고 $(0, \phi(\beta^{(k)}))$을 지나는 직선보다 위 영역으로 $\lambda$ 범위를 제한한다. 아래 그림에서의 연두색 영역과 같다.

해당 영역 내의 아무 $\lambda_k$를 선택하여 $\beta^{(k+1)}=\psi(\lambda_k)=\beta^{(k)}+\lambda_k(B(\beta^{(k)})-\beta^{(k)})$로 정의한다.

이러한 알고리즘의 종료 조건은 다음과 같다.

이는 다음 동치관계를 기반으로 결정되었다.

Theorem 7.3은 MICM에 의해 $\hat{\beta}$으로 수렴함을 보인다.

Theorem 7.3
앞선 조건을 만족하는 $\phi:\reals^n \rightarrow(-\infin,\infin]$와, $\phi(\beta^{(0)})<\infin$을 만족하는 $\beta^{(k)} \in C$에 대하여, mapping $\beta \mapsto D(\beta)$이 집합 $K=\{\beta\in C~:~\phi(\beta) \le \phi(\beta^{(0)})\}$에서 연속이 되도록 하는 positive definite diagonal matrix $D$를 선택하면, Iterative Convex Minorant Algorithm은 $\hat{\beta}$로 수렴한다.

Theorem 7.3 Proof
모든 $k \ge 0$에 대하여 $\beta^{(k)} \in K$고, K는 compact이다.
$\rArr~~$[Enough to Show] : 모든 $\beta \in K\setminus\{\hat{\beta}\}$에서 Modified ICM 함수 $C$가 닫혀있다.

만약 닫힘성(closedness)가 증명되면 7.1절의 Theorem 7.1에 의해 수렴성이 보장된다. (교재 참고)

임의의 $\beta \in K \setminus\{\hat{\beta}\}$와 $\beta^{(k)} \rightarrow \beta$인 $\beta^{(k)} \in K$에 대하여, $\gamma^{(k)}$를

로 정의하자.
$\rArr~~$[Enough to Show] : $\gamma \in C(\beta)$

다음 사실로부터,

1) $\phi(B(\beta^{(k)})) \le \phi(\beta^{(k)})+(1-\epsilon)\nabla\phi(\beta^{(k)})^\mathrm{T}(B(\beta^{(k)})-\beta^{(k)})$

가 성립하므로

가 성립한다.

2) $\phi(B(\beta^{(k)})) > \phi(\beta^{(k)})+(1-\epsilon)\nabla\phi(\beta^{(k)})^\mathrm{T}(B(\beta^{(k)})-\beta^{(k)})$
MICM에 의해

이고, 충분히 큰 $k$에 대하여

가 성립하므로

이고, 따라서

가 성립한다.

MICM의 전체 과정은 다음과 같다.