[Paper Review] A Deep Generative Approach to Conditional Sampling

Date : 2022.11.26 Updated : 2022.12.13

1. IntroductionPermalink

통계학과 머신러닝의 주된 주제는 $X$ 와 $Y$ 사이의 관계를 규명하는 것.
이를 $X$ 가 주어질 때의 $Y$ 의 값을 파악하는 조건부 분포(conditional distribtuion)의 문제로 이해할 수 있다.
본 논문에서는 조건부 분포 추정을 위해 a nonparametric generative approach to sampling from a conditional distribution을 제시한다.
- Generative conditional distribution sampler (GCDS)
$η$ 가 어떤 reference distribution에서 추출된 random variable이라 할 때, GCDS는 $G (η, x)$ 를 추정한다.

1.1. Generative Adversarial NetworkPermalink

GCDS의 훈련 방법은 GAN과 비슷하다. Conditional density의 functional form을 직접 추정하는 대신, GCDS는 Conditional sampler를 추정한다. 논문에 따르면, 조건부 분포를 추정할 때 연속형 조건의 경우 모든 조건에 대해서 추정을 하는 것은 현실적으로 힘들다. 대신 각 조건에 대해서 noise를 부여하여, noise의 reference distribution와 조건 X를 반응변수 Y에 매핑시키는 conditional sampler를 추정하는 것이 더 효율적이다.

이러한 conditional sample 추정은 Noise outsourcing lemma에 의해 정당화된다. 이에 따르면 Conditional density estimation과 generalised nonparametric regression 문제를 동일시 할 수 있는데, 이 generalized nonparametric regression 문제가 바로 conditional sampler 추정을 의미한다.
예를 들어, 어떤 sampler $G (x) = G_{0} (x) + η$ 를 생각하면, noise $η$ 에 따라 형성되는 sampler이며 동시에 standard nonparametric regression 문제임을 확인할 수 있다.

cGAN
$\underset{G}{a r g m i n} \underset{D}{a r g m a x} E_{X \sim P_{X}} [l o g D (X \| Y)] + E_{η \sim p_{η}} [l o g (1 - D (G (X \| Y)))]$
GCDS
$\underset{G}{a r g m i n} \underset{D}{a r g m a x} E_{(X, η) \sim P_{X}, η} [D (X, G (η, X))] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y))]$

1.2. pros of GCDSPermalink

1. No restirction on the dimensionality of the response variable

독립변수와 반응변수가 모두 고차원 이어도 추정이 가능하다.
Image 생성과 같이 고차원 데이터도 처리할 수 있다.

2. Both continuous and discrete type variables can be dealt with

3. Easy to obtain estimates of the summary measures

reference distribution 에서 $η$ 를 뽑아내 sampling을 할 수 있으므로, Monte Carlo를 통해 summary statistics를 쉽게 추정할 수 있다.

4. Consistency

생성된 샘플들은 타겟 조건부 분포에 weakly converge 한다.

1. Smoothing method

include kernel smoothing and local polynomials
esimate the joint density of $(X, Y)$ and marginal density of $X$ , then get the ratio

2. Nonparametric regression

3. Nearest neighbor

저자는 위의 introduction 이후, 크게 세가지 스텝으로 새로운 방법론을 보이고 증명한다.
1. 2절에서는 Noise outrsourcing lemma를 통해 nonparametric density estimation이 conditional sampler estimation으로 대체될 수 있고, 항상 그러한 conditional sampler가 존재할 수 있음을 보인다.
2. 3절에서는 Genrative adversarial 방법론을 모델 추정에 적용하기 위해, f-divergence를 바탕으로 generator와 discriminator를 가진 Objective function을 근사한다.
3. 4절에서는 추정된 generator가 실제의 conditional density에 점근적으로 근사(asymptotically convegent)함을 보인다.
이를 통해, GCDS를 통해 추정된 sample가 목표로 하는 conditional density의 추정에 사용할 수 있음을 이론적으로 보이고 있다. 그리고, 이를 바탕으로 마지막 5절에서는 실증 분석을 통해 GCDS가 실제로 활용될 가능성을 보이고 있다.

2. Generative Representation of Conditional DistributionPermalink

Notation

$(X, Y) \in X \times Y$ , $X \subseteq R^{d}$ is predictor , $Y \subseteq R^{q}$ response variable

Predictor $X$ can contain both continuous and categorical components

$η$ is a random variable independent of $X$ with a known distribution $P_{η}$ to be the standard normal $N (0, I_{m})$ for a given $m \geq 1$

2.1. Goal of the model

분포 $Y g i v e n X = x$ 가 조건부 분포 $G (η, X) g i v e n X = x$ 와 같아지는 $G : R^{m} \times X \to Y$ 를 찿는 것이 GCDS의 목표이다.

\begin{array}{r} (1) & G (η, x) \sim P_{Y | X = x}, x \in X \end{array}

위 조건을 만족하는 $G (η, x)$ 를 찾을 수 있다면, reference distribution에서 $η$ 를 추출한 후 $G (η, x)$ 를 통해 $P_{Y | X = x}$ 를 얻을 수 있다.

2.2. Existence of $G (η, x)$

$G$ 의 존재성은 noise-outsourcing lemma를 통해 증명할 수 있다.

Lemma 2.1. (Noise Outsourcing Lemma)

$(X, Y)$ 가 $X \times Y$ 상에서 joint distribution $P_{X, Y}$ 를 다르는 확률변수라고 하자. 이때, $X, Y$ 는 standard Borel space이다. 이때, $η \sim N (0, I)_{m}$ 가 $X$ 와 독립이고

\begin{array}{r} (2) & (X, Y) = (X, G (η, X)) A l m o s t S u r e l y \end{array}

를 만족하는 $η$ 와 Borel-measurable $G : R^{m} \times X \to Y$ 가 존재한다.

가정에 의해, $η$ 와 $X$ 는 독립이므로, (2) 를 만족하는 $G$ 는 (3)도 만족한다.

proof

저자가 참고한 원문 논문에서는

η \sim N (0, I_{m})

이 아니라

u \sim U n i f o r m [0, 1]

인 경우의 noise outsourcing lemma를 따르고 있다. (Lemma 3.1 in Austin (2015))

Basic noise outsourcing lemma에 따르면,

Y = G_{1} (u, X) a l m o s t s u r e l y

를 만족하는 measurable function

G_{1} : [0, 1] \times X \to Y

이 존재한다.

마찬가지로, 만일

u

와

η

가 독립이라면,

u = G_{2} (η) a l m o s t s u r e l y

를 만족하는 measurable function

G_{2} : R^{m} \to [0, 1]

이 존재한다.

따라서 이 둘을 결합 시,

G (η, x) = G_{1} (G_{2} (η), x), (η, x) \in R^{m} \times X

인

G

를 구할 수 있다.

symmetry
Detecting symmetries with neural networks - IOPscience

2.3. Generalized regression problem

Noise outsourcing lemma가 의미하는 것은 conditional distribution estimation 문제를 generalized regression 문제로 이해할 수 있다는 점이다.
(1) 를 다르게 이해하면 다음과 같다.

\begin{array}{r} (3) & Y | X = x \sim G (η, x), x \in X \end{array}

즉, error가 noise $η$ 에서 나왔다고 이해하면 이는 일반적인 generalized regression 문제와 동일해진다.
예를 들여, $G (η, x) = G_{0} (x) + η$ , $E (η | X) = 0$ 으로 이해하면, (3)는 전형적인 nonparametric regression 문제와 동일해진다.

2.4. a Conditional distribution, not a Unconditional distribution

Conditional distribution을 찾는것은 unconditional distribution을 찾는 것과는 명백하게 다른 문제이다.
GAN을 예시로 들자면, discrete condition이라면 각 condition에 대해서 distribution을 찾음으로써 conditional distribution을 추정할 수 있다. (cGAN, goodfellow et al, 2014)
그러나 이는 $η$ 의 함수로 만들어지는 conditional distribution을 직접 추정하는 것과는 다른 문제로, 실제로 cGAN은 continuous type random variable에 대해서는 conditional distribution 추정이 불가능하다.
대신, 저자는 Lemma 2.2.를 통해 $X, Y$ 의 Joint distribution 추정으로 conditional distribution을 추정하고자 한다.

Lemma 2.2.

$η$ 가 $X$ 와 독립이라고 하자. 이때, $G (η, X) \sim P_{Y | X = x}, x \in X$ 와 다음은 동치이다.

\begin{array}{r} (4) & (X, G (η, X)) \sim (X, Y) \end{array}

이는 $P_{T | X} = P_{Y | X} ⟷ P_{T | X} P_{X} = P_{Y | X} P_{X}$ 라는 사실에서 쉽게 알 수 있다.
따라서, (4)를 만족하는 $G$ 를 찾는다면, 이는 우리가 추정하고자 하는 conditional distribution이며, Monte Carlo 기법 등을 통해 $P_{Y | X = x}$ 의 summary measures 역시 추정할 수 있다.

\begin{array}{r} (5) & \tilde{g} (x) = \frac{1}{J} \sum_{j = 1}^{J} G (η_{j}, x) a n d \tilde{v} (x) = \frac{1}{J} \sum_{j = 1}^{J} [G (η_{j}, x) - \tilde{g} (x)]^{2} \end{array}

3. Distribution Matching EstimationPermalink

3.1. f-divergence and its variational formPermalink

Lemma 3.1. Let $D$ be a class of measurable function $D : R^{d} \to R$ . Suppose $f$ is a differentiable convex function. Then,

\begin{array}{r} (B.1) & D_{f} (q | | p) \geq \underset{D \in D}{s u p} [E_{Z \sim q} D (Z) - E_{W \sim p} f^{*} (D (W))] \end{array}

where the equality holds if and only if $f^{'} (q / p) \in D$ and the supreme is attained at $D^{*} = f^{'} (q / p)$ .

proof)

definition) Fenchel conjugate of f

f^{*} (t) = \underset{x \in R}{s u p} {t x - f (x)}, t \in R

If f is convex function,

f^{* *} = f

. First,

f^{* *} \leq f

\begin{aligned} f^{* *} (t) & = \underset{s \in R}{s u p} {s t - \underset{s \in R}{s u p}} {s t - f^{*} (s)} \\ = \underset{s \in R}{s u p} {s t - \underset{x \in R}{s u p} {t x - f (x)}} \\ = \underset{s \in R}{s u p} \underset{x \in R}{i n f} {s (t - x) + f (x)} \\ \leq \underset{x \in R}{i n f} \underset{s \in R}{s u p} {s (t - x) + f (x)} = f (t) \end{aligned}

Second, if

f

is convex, there is no

f

such that

f^{* *} < f

. Hyperplane separation theorem is needed for the contradiction, I will skip it. By fermat's rule, the maximizer

s^{*}

satisfies

t \in \partial f^{*} (s^{*}) ⟷ s^{*} \in \partial f (t)

One can obtain Lemma 3.1. by applying above result to definition of f-divergence.

3.2. Distribution matich estimation via f-divergencePermalink

Now to construct objective function, consider the KL divergence below.

D_{K L} (p_{X, G (η, X)} | | P_{X, Y}) = E_{(X, η) \sim P_{X, η}} [l o g r (X, G (η, X))], w h e r e r (z) = \frac{p_{X, G (η, X)} (z)}{p_{X, Y} (z)}

Here, the authors suggest to use $D = l o g r$ as a discriminator, since $r$ means the ratio of generator and real data.

Since the conjugacy of $f (x) = x l o g x$ is $f^{*} (t) = e x p (t - 1)$ , using lemma 3.1,

\begin{aligned} D_{K L} (p_{X, G (η, X)} | | P_{X, Y}) & = E_{(X, η) \sim P_{X, η}} [l o g r (X, G (η, X))] \\ = \underset{D}{s u p} {E_{(X, η) \sim P_{X} P_{η}} [D (X, G (η, X)] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y) - 1]} \\ = \underset{D}{s u p} {E_{(X, η) \sim P_{X} P_{η}} [D (X, G (η, X)] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y)]} + 1 \\ \approx \underset{D}{s u p} {E_{(X, η) \sim P_{X} P_{η}} [D (X, G (η, X)] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y)]} \end{aligned}

First equality holds because $x l o g x$ is measurable function. Approximation is used since constant does not affect the result.

Therefore, we can summarise the objective function approximated to :

L (G, D) = E_{(X, η) \sim P_{X} P_{η}} [D (X, G (η, X))] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y)]

, Which means that

\underset{G}{a r g m i n} \underset{D}{a r g m a x} E_{(X, η) \sim P_{X}, η} [D (X, G (η, X))] - E_{(X, Y) \sim P_{X, Y}} [e x p (D (X, Y))]

4. Weak Convergence of Conditional SamplerPermalink

4.1. NotationPermalink

증명을 시작하기에 앞서, 몇가지 노테이션을 정리한다.

\begin{array}{r} (C.1) & L (G) = \underset{D}{s u p} L (G, D) \end{array}

,라 할 때, Lemma3.1. **에 의해 **sup을 만족하는 $D$ 는 $f^{'} (q / p) = 1 + l o g x \approx D$ 에 의해 $l o g \frac{P_{X G} (z)}{P_{X Y} (z)} = l o g r (z)$ 이다.

\begin{array}{r} (C.2) & D^{*} (z) = l o g \frac{P_{X G} (z)}{P_{X Y} (z)} = l o g r (z) \end{array}

따라서, Generator가 영향을 주지 않는 부분을 제하면

\begin{array}{r} (C.3) & L (G) = E_{(X, η) \sim P_{X} P_{η}} [l o g r (X, G (η, X))] \end{array}

가 성립하며, Lemma 2.2. 에 의해 이를 극소화하는 $G^{*}$ 는 $P_{Y | X}$ 가 된다.

\begin{array}{r} (C.4) & G^{⋆} (η, X) \sim P_{Y | X = x}, x \in X \end{array}

Empirically, 이는 다음과 같이 표현한다.

\begin{aligned} (C.5) & \hat{L} (G) & = \underset{D_{ϕ} \in D}{s u p} \hat{L} (G, D) \\ (C.6) & {\hat{G}}_{θ} \in a r g & m i n_{G_{θ} \in G} \hat{L} (G_{θ}, \hat{D_{ϕ}}) \\ (C.7) & {\hat{D}}_{ϕ} \in a r g & m i n_{D_{ϕ} \in D} \hat{L} (\hat{G_{θ}}, D_{ϕ}) \end{aligned}

4.2. AssumptionsPermalink

(A1) The target conditional genearator $G^{⋆} : R^{m} \times X \to Y$ is continuous with $| | G^{⋆} | |_{\infty} \leq C_{0}$ for some constant $0 < C_{0} < \infty$

(A2) For any $G \in G$ , $r_{G} (z) = \frac{p_{X, G (η, X)} (z)}{p_{X, Y} (z)}$ : $X \times Y \to R$ is continuous and $0 < C_{1} \leq r_{G} (z) \leq C_{2}$

위의 두가지 가정은 conditional density estimation에서 많이 사용되는 가정이며, 현실적으로 가정하기에 무리는 없다.

추가적으로, 훈련에 사용되는 신경망 $G, D$ 에 대해 다음의 가정을 추가한다.

depth $H$ : number of hidden layers

width $W$ : $m a x w_{1}, \dots, w_{H}$ for $w_{i}$ is width of $i$ th layer

size $S$ : $\sum_{i = 0}^{H} [w_{i} \times (w_{i} + 1)]$ is the total number of parameters in the network.

bound $B$ : $| | G | |_{\infty} \leq B$ is the bound of neural network

(N1) The network parameters of $G$ satisfies $H W \to \infty a n d \frac{B S H l o g (S) l o g n}{n} \to 0, a s n \to \infty$

(N2) The network parameters of $D$ satisfies $\tilde{H} \tilde{W} \to \infty a n d \frac{\tilde{B} \tilde{S} \tilde{H} l o g (\tilde{S}) l o g n}{n} \to 0, a s n \to \infty$

이들 가정 역시 충분히 현실적인 가정인데, 표본 수가 무한하게 많아진다면 그만큼 뉴럴네트워크가 커져야하며, 동시에 표본의 증가속도보다는 뉴럴네트워크의 크기 확장속도가 작아야 한다.

4.3. Total Variation norm convergencePermalink

Theorem 4.1. 위의 조건들이 만족될 때, 다음이 성립한다.

\begin{array}{r} (C.8) & E_{(X_{i}, Y_{i}, η_{i})_{i = 1}^{n}} | | p_{X, {\hat{G}}_{θ} (η, X)} - p_{X, Y} | |_{L_{1}}^{2} \to 0, a s n \to 0 \end{array}

해당 부분의 proof가 길기 때문에, proof를 여러 부분으로 나누어서 설명.

proof1

Pinsker's theorem과

L (G^{⋆}) = 0

에 의해

| | p_{X, {\hat{G}}_{θ} (η, X)} - p_{X, Y} | |_{L_{1}}^{2}

는 다음이 성립한다.

\begin{array}{r} (C.9) & | | p_{X, {\hat{G}}_{θ} (η, X)} - p_{X, Y} | |_{L_{1}}^{2} \leq 2 (L (\hat{G}) - L (G^{*})) \end{array}

- Pinkser's theorem if

P

and

Q

are probability densities defined on a measurable space

(X, Ω)

| | P - Q | |_{L_{1}} \leq \sqrt{2 D_{K L} (P | | Q)}

따라서, 어떠한 generator

\bar{G} \in G

에 대하여,

L (\hat{G}) - L (G^{*})

는 다음을 만족한다.

\begin{aligned} (C.10) & L (\hat{G}) - L (G^{⋆}) & = \underset{D}{s u p} L (\hat{G}, D) - \underset{D \in D}{s u p} L (\hat{G}, D) \\ (C.11) & + \underset{D \in D}{s u p} L (\hat{G}, D) - \underset{D \in D}{s u p} \hat{L} (\hat{G}, D) \\ (C.12) & + \underset{D \in D}{s u p} \hat{L} (\hat{G}, D) - \underset{D \in D}{s u p} \hat{L} (\bar{G}, D) \\ (C.13) & + \underset{D \in D}{s u p} \hat{L} (\bar{G}, D) - \underset{D \in D}{s u p} L (\bar{G}, D) \\ (C.14) & + \underset{D \in D}{s u p} L (\bar{G}, D) - \underset{D}{s u p} L (\bar{G}, D) \\ (C.15) & + \underset{D}{s u p} L (\bar{G}, D) - \underset{D}{s u p} L (G^{⋆}, D) \end{aligned}

이때,

(C .12), (C .14)

는 0보다 크거나 같고,

(C .11), (C .13)

은

\underset{D \in D, G \in G}{s u p} | L (G, D) - \hat{L} (G, D) |

보다 작으므로, 다음이 성립한다.

\begin{aligned} L (\hat{G}) - L (G^{⋆}) & \leq \underset{D}{s u p} L (\hat{G}, D) - \underset{D \in D}{s u p} L (\hat{G}, D) \\ + 2 \underset{D \in D, G \in G}{s u p} | L (G, D) - \hat{L} (G, D) | \\ + \underset{D}{s u p} L (\bar{G}, D) - \underset{D}{s u p} L (G^{⋆}, D) \\ \equiv △_{1} + △_{2} + △_{3} \end{aligned}

이때

△_{1}, △_{3}

는 근사오류(approximation error)이며

△_{2}

는 통계적 오류(Statistical error)라고 할 수 있다.

more lemmas for proof

Lemma B.4. if

ξ_{i}, i = 1, \dots, m

are $m$ finite linear combinations of Rademacher variables $ϵ_{j}, j = 1, \dots, J$ . Then,

E_{ϵ_{j}, j = 1, \dots, J} \underset{1 \leq i \leq m}{m a x} | ξ_{i} | \leq C (l o g m)^{\frac{1}{2}} \underset{1 \leq i \leq m}{m a x} (E ξ_{i}^{2})^{\frac{1}{2}}

for some constant

C > 0

proof) This result follows from Corollary 3.2.6 and inequality 4.3.1 in De la Pena and Gine (2012) with

Φ (x) = e x p (x^{2})

Lemma B.5. Let $f$ be a uniformly continuous function defined on $E \in [- R, R]^{d}$ . For arbitrary $L \in N^{+}$ and $N \in N^{+}$ , there exists a function $R e L U$ network $f_{ϕ}$ with width $3^{d + 3} m a x {d ⌊ N^{1 / d} ⌋, N + 1}$ and depth $12 L + 14 + 2 d$ such that

| | f - f_{ϕ} | |_{L^{\infty} (E)} \leq 19 \sqrt{d} ω_{f}^{E} (2 R N^{- 2 / d} L^{- 2 / d})

where, $ω_{f}^{E} (t)$ is the modulus of continuity of $f$ satisfying $ω_{f}^{E} (t) \to 0$ as $t \to 0^{+}$

proof can be found on Theorem 4.3. in Shen et al.(2020)

proof of error3

Lemma B.1.

\begin{array}{r} (D.1.) & △_{3} \equiv i n f_{\bar{G} \in G} [L (\bar{G}) - L (G^{⋆})] = o (1), a s n \to \infty \end{array}

proof) 가정 A1에 의해

G^{⋆}

은

E_{1} = [- B, B]^{d + m}, B = l o g n

에서 연속이고,

| | G^{⋆} | |_{L^{\infty}} \leq C_{0} f o r s o m e C_{0} \geq 0

가 성립한다.

L = l o g n, N = \frac{n^{\frac{d + m}{2 (2 + d + m)}}}{l o g n}, E = E_{1}, R = B

로 보면, Lemma B.5. 에 의해 아래 (D.2.)를 만족하는 ReLU network

{\bar{G}}_{\bar{θ}} \in G

를 찾을 수 있다.

\begin{array}{r} (D.2.) & | | G^{⋆} - {\bar{G}}_{\bar{θ}} | |_{L^{\infty} (E_{1})} \leq 19 \sqrt{d + m} ω_{F}^{E_{1}} (2 (l o g n) n^{\frac{- 1}{2 + d + m}}) \end{array}

, 이때,

{\bar{G}}_{\bar{θ}}

는

d e p t h H = 12 l o g n + 14 + 2 (d + m)

w i d t h W = 3^{d + m + 3} m a x {(d + m) (\frac{n^{\frac{d + m}{2 (2 + d + m)}}}{l o g n})^{\frac{1}{d + m}}, \frac{n^{\frac{d + m}{2 (2 + d + m)}}}{l o g n} + 1}

s i z e S = \frac{n^{\frac{d + m - 2}{d + m + 2}}}{l o g^{4} n}

의 네트워크 구조를 가지는 네트워크를 의미한다.

또한

\bar{D} = l o g \frac{p_{X, {\bar{G}}_{\bar{θ} (η, X)} (z)}}{p_{X, Y} (z)}

D^{⋆} = l o g \frac{p_{X, G_{\bar{θ} (η, X)}^{⋆} (z)}}{p_{X, Y} (z)}

으로

G

의 함수이고 가정에 의해

G

는 continuity를 만족하므로,

| | D^{*} - \bar{D} | | \to 0

역시 만족된다.
따라서,

L (\bar{G}) = \underset{D}{s u p} L (\bar{G}, D) = E_{(X, η) \sim P_{X} P_{η}} [\bar{D} (X, \bar{G} (η, X))] - E_{(X, Y) \sim P_{X, Y}} [e x p (\bar{D} (X, Y)]

는

n \to \infty

에 따라

L (G^{⋆}) = \underset{D}{s u p} L (G^{⋆}, D) = E_{(X, η) \sim P_{X} P_{η}} [D^{⋆} (X, G^{⋆} (η, X))] - E_{(X, Y) \sim P_{X, Y}} [e x p (D^{⋆} (X, Y)]

에 수렴한다.

proof of error2

Lemma B.2.

\begin{array}{r} (D.3.) & △_{2} \equiv \underset{D \in D, G \in G}{s u p} | L (G, D) - \hat{L} (G, D) | \leq O (n^{\frac{- 2}{2 + d + m}} + n^{\frac{- 2}{2 + d + q}}) \end{array}

proof) 다음과 같은 노테이션을 정한다.
-

Z = (X, Y) \sim P_{X, Y}

and

Z_{i} = (X_{i}, Y_{i}), i = 1, \dots, n

are

i . i . d .

copies of

Z

η \sim P_{η}

and

η_{j}, j = 1, \dots, n

are

i . i . d .

copies of

η

η ⊥ X

W_{i} = (X_{i}, η_{i})

are

i . i . d .

copies of

W = (X, η) \sim P_{X} P_{η}

S = (W, Z) \sim (P_{X} P_{η}) \otimes P_{X, Y}

and

S_{i} = (W_{i}, Z_{i}) = ((X_{i}, η_{i}), (X_{i}, Y_{i})), i = 1, \dots, n

are

i . i . d .

copies of

S

.
-

b (G, D; S) = D (X, G (η, X)) - e x p (D (X, Y))

L (G, D) = E_{S} [b (G, D,; S)]

\hat{L} (G, D) = \frac{1}{n} \sum_{i = 1}^{n} b (G, D,; S)

ϵ_{i}, i = 1, \dots, n

를

S_{i}

와 독립인 Rademacher 확률변수라고 하면, Rademacher complexity of

D \times G

를 다음과 같이 정의한다.

\begin{array}{r} (D.4.) & C (D \times G) = \frac{1}{n} E_{{S_{i}, ϵ_{i}}_{i = 1}^{n}} [\underset{G \in G, D \in D}{s u p} | \sum_{i = 1}^{n} ϵ_{i} b (G, D,; S) |] \end{array}

이제, symmetrization technique과 law of iterated expectation을 이용하면 다음을 보일 수 있다.

\begin{aligned} \underset{D \in D, G \in G}{s u p} | L (G, D) - \hat{L} (G, D) | \\ = \underset{D \in D, G \in G}{s u p} | E_{S} b (G, D, S) - \frac{1}{n} \sum_{i = 1}^{n} b (G, D; S_{i}^{'}) | ⟵ S_{i}^{'} i s i . i . d . c o p y o f S_{i} \\ = \underset{D \in D, G \in G}{s u p} | E_{S} [\frac{1}{n} \sum_{i = 1}^{n} (b (G, D, S_{i}) - b (G, D; S_{i}^{'}))] | \\ \leq E_{S, S^{'}} [\underset{D \in D, G \in G}{s u p} | \frac{1}{n} \sum_{i = 1}^{n} (b (G, D, S_{i}) - b (G, D; S_{i}^{'})) |] \\ = E_{S, S^{'}, ϵ} [\underset{D \in D, G \in G}{s u p} | \frac{1}{n} \sum_{i = 1}^{n} ϵ_{i} (b (G, D, S_{i}) - b (G, D; S_{i}^{'})) |] \\ \leq 2 E_{S, ϵ} [\underset{D \in D, G \in G}{s u p} | \frac{1}{n} \sum_{i = 1}^{n} ϵ_{i} b (G, D, S_{i}) |] \\ = 2 C (D \times G) \\ (D.5.) & = 2 E_{S_{1}, \dots, S_{n}} {E_{ϵ_{1}, \dots, ϵ_{n}} [\underset{G \in G, D \in D}{s u p} | \frac{1}{n} \sum_{i = 1}^{n} ϵ_{i} b (G, D,; S_{i}) | | S_{1}, \dots, S_{n}]} \end{aligned}

어떤

δ > 0

에 대하여,

D_{δ} \times G_{δ}

를

D \times G

의

δ - c o v e r

라 하고,

C (D \times G, e_{n, 1}, δ)

를 다음의 empirical distnace

e_{n, 1}

을 distance로 가지는 covering set이라고 하면,

e_{n, 1} ((G, D), (\tilde{G}, \tilde{D})) = \frac{1}{n} E_{ϵ} [\sum_{i = 1}^{n} | ϵ_{i} (b (G, D; S_{i}) - b (\tilde{G}, \tilde{D}; S_{i})) |]

또한, 가정 A1, A2에 의해

b (G, D; S_{i})

가 어떤 수에 의해 bounded 되므로,

b (G, D; S_{i}) < C_{4}

라 하고, Lemma B.4. 와 함께 적용 시 다음 결과를 얻을 수 있다.

\begin{aligned} E_{S_{1}, \dots, S_{n}} {E_{ϵ_{1}, \dots, ϵ_{n}} [\underset{G \in G, D \in D}{s u p} | \frac{1}{n} \sum_{i = 1}^{n} ϵ_{i} b (G, D,; S_{i}) | | S_{1}, \dots, S_{n}]} \\ \leq δ + \frac{1}{n} E_{S_{1}, \dots, S_{n}} {E_{ϵ_{1}, \dots, ϵ_{n}} [\underset{G \in G_{δ}, D \in D_{δ}}{s u p} | \sum_{i = 1}^{n} ϵ_{i} b (G, D,; S_{i}) | | S_{1}, \dots, S_{n}]} ⟵ b y d e f i n i t i o n o f c o v e r i n g δ - c o v e r \\ \leq 2 δ + C_{5} \frac{1}{n} E_{S_{1}, \dots, S_{n}} {{[l o g C (D \times G, e_{n, 1}, δ)]}^{1 / 2} \underset{(G, D) \in D_{δ} \times G_{δ}}{m a x} {[\sum_{i = 1}^{n} b^{2} (G, D; S_{i})]}^{1 / 2}} \\ \leq 2 δ + C_{5} \frac{1}{n} E_{S_{1}, \dots, S_{n}} {{[l o g C (D \times G, e_{n, 1}, δ)]}^{1 / 2} \sqrt{n} C_{4}} ⟵ b y {[\sum_{i = 1}^{n} b^{2} (G, D; S_{i})]}^{1 / 2} \leq \sqrt{n} C_{4} \\ \leq 2 δ + C_{6} \frac{1}{\sqrt{n}} {[l o g C (D, e_{n, 1}, δ) + l o g C (G, e_{n, 1}, δ)]}^{1 / 2} ⟵ b y d e f i n i t i o n o f c o v e r i n g δ - c o v e r \\ (D.6.) & \leq 2 δ + C_{6} \frac{1}{\sqrt{n}} {[l o g C (D, e_{n, \infty}, δ) + l o g C (G, e_{n, \infty}, δ)]}^{1 / 2} ⟵ b y e_{n, \infty} \leq e_{n, 1} \end{aligned}

또한 위의 definition 하에서 neural network

G, D

에 대해 다음이 만족된다.

o g C (D, e_{n, \infty}, δ) \leq P d i m_{G} l o g \frac{2 e B n}{P d i m_{G}}

P d i m

은 PseudoDimension 이며, 다음을 만족한다.

C_{7} H S l o g S \leq P d i m \leq C_{8} H S l o g S

따라서, (D.6.) 는 다음을 따름을 보일 수 있다.

C_{6} \frac{1}{\sqrt{n}} {[l o g C (D, e_{n, \infty}, δ) + l o g C (G, e_{n, \infty}, δ)]}^{1 / 2} \leq C_{9} \frac{1}{\sqrt{n}} {[H S l o g S l o g \frac{B n}{H S l o g S} + \tilde{H} \tilde{S} l o g \tilde{S} l o g \frac{\tilde{B} n}{\tilde{H} \tilde{S} l o g \tilde{S}}]}^{1 / 2}

위의 결과를 정리 후 N1, N2 가정과

δ = \frac{1}{n}

을 가정 시 다음 결과에 도달한다.

\begin{matrix} (D.7.) & \underset{D \in D, G \in G}{s u p} | L (G, D) - \hat{L} (G, D) | \leq 2 (2 δ + C_{9} \frac{1}{\sqrt{n}} {[H S l o g S l o g \frac{B n}{δ H S l o g S} + \tilde{H} \tilde{S} l o g \tilde{S} l o g \frac{\tilde{B} n}{δ \tilde{H} \tilde{S} l o g \tilde{S}}]}^{1 / 2}) \to 0 \end{matrix}

proof of error1

Lemma B.3.

\begin{array}{r} (D.8.) & E_{(X_{i}, Y_{i}, η_{i})_{i = 1}^{n}} [△_{1}] \equiv E_{(X_{i}, Y_{i}, η_{i})_{i = 1}^{n}} [\underset{D}{s u p} L (\hat{G}, D) - \underset{D \in D}{s u p} L (\hat{G}, D)] \to 0 \end{array}

\underset{D}{s u p} L (\hat{G}, D)

는 Lemma B.2. 에 의해

L (\hat{G}, D_{\hat{G}}), w h e r e D_{\hat{G}} (z) = l o g \frac{P_{X \hat{G}} (z)}{P_{X Y} (z)} = l o g r (z)

에서 달성된다. 가정 A1, A2에 의해

D_{\hat{G}} (z)

는

E_{2} = [- B, B]^{d + q}, B = l o n n

에서 연속적이며

| | D_{\hat{G}} | |_{L^{\infty}} \leq C_{3}

를 만족한다. error3의 증명 과정과 유사하게,

L = l o g n, N = \frac{n^{\frac{d + q}{2 (2 + d + q)}}}{l o g n}, E = E_{2}, R = B

로 보면, Lemma B.5. 에 의해 아래 (D.9.) 만족하는 ReLU network

D_{\hat{G}} \in D

를 찾을 수 있다.

\begin{array}{r} (D.9.) & | | D_{\hat{G}} - {\hat{D}}_{ϕ} | |_{L^{\infty} (E_{2})} \leq 19 \sqrt{d + q} ω_{F}^{E_{2}} (2 (l o g n) n^{\frac{- 1}{2 + d + q}}) \end{array}

, 이때,

{\bar{D}}_{\bar{ϕ}}

는

d e p t h \tilde{H} = 12 l o g n + 14 + 2 (d + q)

w i d t h \tilde{W} = 3^{d + q + 3} m a x {(d + q) (\frac{n^{\frac{d + q}{2 (2 + d + q)}}}{l o g n})^{\frac{1}{d + q}}, \frac{n^{\frac{d + q}{2 (2 + d + q)}}}{l o g n} + 1}

s i z e \tilde{S} = \frac{n^{\frac{d + q - 2}{d + q + 2}}}{l o g^{4} n}

의 네트워크 구조를 가지는 네트워크를 의미한다.

따라서, continuity에 의해,

0 < \underset{D}{s u p} L (\hat{G}, D) - \underset{D \in D}{s u p} L (\hat{G}, D) \leq L (\hat{G}, D_{\hat{G}}) - L (\hat{G} - {\hat{D}}_{ϕ}) \to 0

가 성립한다.

5. experimentsPermalink

5.1. Simulation studiesPermalink

For the finite sample performance of GCDS, the authors compared the model with 3 previous methods, including the nearest neighbor kernel conditional density estimation (NNKCDE, Dalmasso et al. (2020)), the conditional kernel density estimation (CKDE, implemented in the R package np, Hall et al. (2004)), and the basis expansion method FlexCode (Izbicki et al., 2017)).

Mean and SD are estimated by Monte Carlo for GCDS. For other methods, numerical integration is used for calculation. For GCDS, conditional density is estimated using the samples generated from GCDS with kernel smoothing.

Table1 : MSE of the estimated conditional mean, estimated standard deviation

Figure1 :Comparison of density estimation

We see that GCDS yields smaller MSEs for estimation conditional mean and SD in most cases. Density plots show that GCDS yields better conditional density estimates than others. Especially, DCGS shows that it can follow multi modal densities well.

5.2. MNIST handwrittened digitPermalink

Another viewpoint for DCGS is that it can handle high-dimensional data problems as well. MNIST data is example. The images are stored in 28 $\times$ 28 matrices with gray color intensity from 0 to 1. Each image is paired with a label in {0,1, … , 9}. The authors performed two tasks: generating images from labels and reconstructing the missing part of an image.

Generating images from label

Like a standard conditional GAN, the authors input labels $[1, 0, . ., 0] \sim [0, \dots, 1]$ as a condition. The results are like below figure 2.

Figure2 : Left one is real data, right one is generated data

It is easy to see that generated image is similar to real image. Also, for each label, generated images are all different because of noise input. However, it is not especially different from conditional GAN method.

Reconstructing the missing part of an image

Special part of DCGS is that it can adopt ‘continuous condition’, which is not possible for standard GAN. Reconstructing the missing part of an image is an example.

Figure3 : Reconstruction of missing part

Reconstructed images given partial image in MNIST dataset. The first column in each panel consists of the true images, the other columns give the constructed images. In the left panel, the left lower 1/4 of the image is given; in the middle panel, the left 1/2 of the image is given; in the right panel, 3/4 of the image is given.

Here, image is conditions, which are high-dimensional conditional data. It is not available for standard GAN method. Also, when 1/4 of image is given, It does not show good reconstruction quality. However, as more part of image is given, reconstruction quality increases. Therefore, it shows that GCDS can take high-dimensional data, with continuous or discrete columns, could be handle for both predictors and responses.

Share on

Twitter Facebook LinkedIn

Insik Cho

[Paper Review] A Deep Generative Approach to Conditional Sampling

1. IntroductionPermalink

1.1. Generative Adversarial NetworkPermalink

1.2. pros of GCDSPermalink

2. Generative Representation of Conditional DistributionPermalink

3. Distribution Matching EstimationPermalink

3.1. f-divergence and its variational formPermalink

3.2. Distribution matich estimation via f-divergencePermalink

4. Weak Convergence of Conditional SamplerPermalink

4.1. NotationPermalink

4.2. AssumptionsPermalink

4.3. Total Variation norm convergencePermalink

5. experimentsPermalink

5.1. Simulation studiesPermalink

5.2. MNIST handwrittened digitPermalink

Share on

Leave a comment

최근 글 10 개 :)

Insik Cho

1. IntroductionPermalink

1.1. Generative Adversarial NetworkPermalink

1.2. pros of GCDSPermalink

1.3. Related literaturePermalink

2. Generative Representation of Conditional DistributionPermalink

3. Distribution Matching EstimationPermalink

3.1. f-divergence and its variational formPermalink

3.2. Distribution matich estimation via f-divergencePermalink

4. Weak Convergence of Conditional SamplerPermalink

4.1. NotationPermalink

4.2. AssumptionsPermalink

4.3. Total Variation norm convergencePermalink

5. experimentsPermalink

5.1. Simulation studiesPermalink

5.2. MNIST handwrittened digitPermalink

Share on

Leave a comment

최근 글 10 개 :)