GNTMC001 問題1

皆さんはお分かりだろうか?問題文がどこかで見たことがある問題だということに...

解説

問題の構造

逆拡散ドリフトが大きい向きを直接比較するだけでは不十分です。

評価する量は画素ベクトルそのものではなく、

$$R(\boldsymbol{y})=\|\boldsymbol{y}\|^2$$R(y)=∥y∥2

の期待値の初期変化率です。そのため、逆拡散のドリフト項だけでなく、ウィーナー過程の二次変分が生む伊藤補正も含める必要があります。

また、$\|\boldsymbol{y}\|=3$∥y∥=3 という条件のもとで変化率を最大化・最小化するため、最終的には共分散行列の固有方向を判定する必要があります。

前向き拡散後の共分散行列

前向き過程の平均を $\boldsymbol{m}_t=\mathbb{E}[\boldsymbol{X}_t]$mt​=E[Xt​] とすると、

$$\frac{d\boldsymbol{m}_t}{dt} = -\frac{\beta}{2}\boldsymbol{m}_t$$dtdmt​​=−2β​mt​

です。

初期平均が $\boldsymbol{0}$0 なので、

$$\boldsymbol{m}_t=\boldsymbol{0}$$mt​=0

となります。

したがって、共分散行列は

$$\boldsymbol{C}_t = \mathbb{E} \left[ \boldsymbol{X}_t\boldsymbol{X}_t^{\mathsf T} \right]$$Ct​=E[Xt​XtT​]

です。

行列値過程 $\boldsymbol{X}_t\boldsymbol{X}_t^{\mathsf T}$Xt​XtT​ に伊藤の積公式を適用すると、

$$\begin{aligned} d\left( \boldsymbol{X}_t\boldsymbol{X}_t^{\mathsf T} \right) &= d\boldsymbol{X}_t\,\boldsymbol{X}_t^{\mathsf T} + \boldsymbol{X}_t\,d\boldsymbol{X}_t^{\mathsf T}\\ &\quad+ d\boldsymbol{X}_t\,d\boldsymbol{X}_t^{\mathsf T} \end{aligned}$$d(Xt​XtT​)​=dXt​XtT​+Xt​dXtT​+dXt​dXtT​​

です。

二成分のウィーナー過程は独立なので、

$$d\boldsymbol{W}_t\,d\boldsymbol{W}_t^{\mathsf T} = \boldsymbol{I}\,dt$$dWt​dWtT​=Idt

であり、

$$d\boldsymbol{X}_t\,d\boldsymbol{X}_t^{\mathsf T} = \beta\boldsymbol{I}\,dt$$dXt​dXtT​=βIdt

となります。

期待値を取ると、

$$\frac{d\boldsymbol{C}_t}{dt} = -\beta\boldsymbol{C}_t+\beta\boldsymbol{I}$$dtdCt​​=−βCt​+βI

を得ます。

初期条件 $\boldsymbol{C}_0=\boldsymbol{\Sigma}_0$C0​=Σ0​ より、

$$\boldsymbol{C}_t = e^{-\beta t}\boldsymbol{\Sigma}_0 + \left(1-e^{-\beta t}\right)\boldsymbol{I}$$Ct​=e−βtΣ0​+(1−e−βt)I

です。

時刻 $t_*$t∗​ では、

$$e^{-\beta t_*} = e^{-\ln 16} = \frac{1}{16}$$e−βt∗​=e−ln16=161​

なので、

$$\begin{aligned} \boldsymbol{C}_{t_*} &= \frac{1}{16} \begin{pmatrix} 41&40\\ 40&41 \end{pmatrix} + \frac{15}{16} \begin{pmatrix} 1&0\\ 0&1 \end{pmatrix}\\ &= \begin{pmatrix} \frac{7}{2}&\frac{5}{2}\\ \frac{5}{2}&\frac{7}{2} \end{pmatrix} \end{aligned}$$Ct∗​​​=161​(4140​4041​)+1615​(10​01​)=(27​25​​25​27​​)​

となります。

確率密度のスコア

前向き過程は線形であり、初期分布も正規分布なので、$\boldsymbol{X}_{t_*}$Xt∗​​ は平均 $\boldsymbol{0}$0、共分散行列 $\boldsymbol{C}_{t_*}$Ct∗​​ の正規分布に従います。

したがって、

$$\nabla_{\boldsymbol{y}} \log\rho_{t_*}(\boldsymbol{y}) = -\boldsymbol{C}_{t_*}^{-1}\boldsymbol{y}$$∇y​logρt∗​​(y)=−Ct∗​−1​y

です。

逆拡散開始時のドリフトベクトルを $\boldsymbol{b}(\boldsymbol{y})$b(y) とすると、

$$\begin{aligned} \boldsymbol{b}(\boldsymbol{y}) &= \frac{\beta}{2}\boldsymbol{y} - \beta\boldsymbol{C}_{t_*}^{-1}\boldsymbol{y}\\ &= \beta \left( \frac{1}{2}\boldsymbol{I} - \boldsymbol{C}_{t_*}^{-1} \right) \boldsymbol{y} \end{aligned}$$b(y)​=2β​y−βCt∗​−1​y=β(21​I−Ct∗​−1​)y​

です。

画素偏差エネルギーに対する伊藤の公式

逆拡散過程を成分表示すると、

$$dY_i=b_i(\boldsymbol{Y})\,d\tau+\sqrt{\beta}\,d\overline{W}_i$$dYi​=bi​(Y)dτ+β​dWi​

です。

$R(\boldsymbol{Y})=Y_1^2+Y_2^2$R(Y)=Y12​+Y22​ に伊藤の公式を適用します。

勾配とヘッセ行列は、

$$\nabla R(\boldsymbol{y})=2\boldsymbol{y}, \qquad \nabla^2R(\boldsymbol{y})=2\boldsymbol{I}$$∇R(y)=2y,∇2R(y)=2I

です。

したがって、

$$dR = 2\boldsymbol{Y}^{\mathsf T}\boldsymbol{b}(\boldsymbol{Y})\,d\tau + 2\sqrt{\beta}\, \boldsymbol{Y}^{\mathsf T}d\overline{\boldsymbol{W}} + 2\beta\,d\tau$$dR=2YTb(Y)dτ+2β​YTdW+2βdτ

となります。

最後の $2\beta\,d\tau$2βdτ は、二つの独立なウィーナー成分から生じる伊藤補正です。

期待値を取ると確率積分の項は消えるので、

$$G(\boldsymbol{y}) = 2\boldsymbol{y}^{\mathsf T}\boldsymbol{b}(\boldsymbol{y}) + 2\beta$$G(y)=2yTb(y)+2β

です。

ドリフトを代入すると、

$$\begin{aligned} G(\boldsymbol{y}) &= 2\beta \boldsymbol{y}^{\mathsf T} \left( \frac{1}{2}\boldsymbol{I} - \boldsymbol{C}_{t_*}^{-1} \right) \boldsymbol{y} + 2\beta\\ &= \beta \left[ \boldsymbol{y}^{\mathsf T} \left( \boldsymbol{I} - 2\boldsymbol{C}_{t_*}^{-1} \right) \boldsymbol{y} + 2 \right] \end{aligned}$$G(y)​=2βyT(21​I−Ct∗​−1​)y+2β=β[yT(I−2Ct∗​−1​)y+2]​

となります。

最大・最小となる画素パターン

$\boldsymbol{C}_{t_*}$Ct∗​​ は $\boldsymbol{\Sigma}_0$Σ0​ と単位行列の線形結合なので、両者の固有ベクトルは共通です。

まず、$\boldsymbol{\Sigma}_0$Σ0​ の固有値を求めます。

$$\det \left( \boldsymbol{\Sigma}_0-\lambda\boldsymbol{I} \right) = \begin{vmatrix} 41-\lambda&40\\ 40&41-\lambda \end{vmatrix}$$det(Σ0​−λI)=​41−λ40​4041−λ​​

より、

$$\begin{aligned} 0 &= (41-\lambda)^2-40^2\\ &= (41-\lambda-40)(41-\lambda+40)\\ &= (1-\lambda)(81-\lambda) \end{aligned}$$0​=(41−λ)2−402=(41−λ−40)(41−λ+40)=(1−λ)(81−λ)​

です。

したがって、$\boldsymbol{\Sigma}_0$Σ0​ の固有値は $81$81 と $1$1 です。

$\boldsymbol{C}_{t_*}$Ct∗​​ の対応する固有値は、

$$c = \frac{1}{16}\lambda+\frac{15}{16}$$c=161​λ+1615​

で与えられるため、

$$c_+=\frac{81}{16}+\frac{15}{16}=6, \qquad c_-=\frac{1}{16}+\frac{15}{16}=1$$c+​=1681​+1615​=6,c−​=161​+1615​=1

です。

$\boldsymbol{C}_{t_*}$Ct∗​​ の固有値が $c$c である方向では、$\boldsymbol{C}_{t_*}^{-1}$Ct∗​−1​ の固有値は $1/c$1/c です。

$\|\boldsymbol{y}\|=3$∥y∥=3 より、その方向に沿うベクトルでは、

$$\boldsymbol{y}^{\mathsf T} \left( \boldsymbol{I} - 2\boldsymbol{C}_{t_*}^{-1} \right) \boldsymbol{y} = 9\left(1-\frac{2}{c}\right)$$yT(I−2Ct∗​−1​)y=9(1−c2​)

となります。

関数 $1-2/c$1−2/c は $c>0$c>0 で単調増加するため、$G$G は大きい共分散固有値 $c_+=6$c+​=6 の方向で最大となり、小さい固有値 $c_-=1$c−​=1 の方向で最小となります。

固有値 $81$81 に対する固有ベクトルは、

$$\begin{pmatrix} 41&40\\ 40&41 \end{pmatrix} \begin{pmatrix} 1\\ 1 \end{pmatrix} = 81 \begin{pmatrix} 1\\ 1 \end{pmatrix}$$(4140​4041​)(11​)=81(11​)

なので、

$$\boldsymbol{y}_{\max} = \frac{3}{\sqrt{2}} \begin{pmatrix} 1\\ 1 \end{pmatrix}$$ymax​=2​3​(11​)

です。

固有値 $1$1 に対する固有ベクトルは、

$$\begin{pmatrix} 41&40\\ 40&41 \end{pmatrix} \begin{pmatrix} 1\\ -1 \end{pmatrix} = \begin{pmatrix} 1\\ -1 \end{pmatrix}$$(4140​4041​)(1−1​)=(1−1​)

なので、

$$\boldsymbol{y}_{\min} = \frac{3}{\sqrt{2}} \begin{pmatrix} 1\\ -1 \end{pmatrix}$$ymin​=2​3​(1−1​)

です。

最大値と最小値

$c_+=6$c+​=6 の方向では、

$$\begin{aligned} G(\boldsymbol{y}_{\max}) &= \beta \left[ 9\left( 1-\frac{2}{6} \right)+2 \right]\\ &= \beta \left[ 9\left(\frac{2}{3}\right)+2 \right]\\ &= 8\beta \end{aligned}$$G(ymax​)​=β[9(1−62​)+2]=β[9(32​)+2]=8β​

です。

$c_-=1$c−​=1 の方向では、

$$\begin{aligned} G(\boldsymbol{y}_{\min}) &= \beta \left[ 9(1-2)+2 \right]\\ &= -7\beta \end{aligned}$$G(ymin​)​=β[9(1−2)+2]=−7β​

です。

したがって、

$$\frac{ G(\boldsymbol{y}_{\max}) }{ \left|G(\boldsymbol{y}_{\min})\right| } = \frac{8\beta}{7\beta} = \frac{8}{7}$$∣G(ymin​)∣G(ymax​)​=7β8β​=78​

となります。

よって、

$$p=8, \qquad q=7$$p=8,q=7

であり、入力すべき自然数は、

$$10p+q=10\cdot8+7=\boxed{87}$$10p+q=10⋅8+7=87​

です。