可逆ニューラルネットのSobolev空間
における普遍性について
Takeshi Teshima1 2, Isao Ishikawa3 2
1The University of Tokyo, Japan

2RIKEN, Japan

3 Ehime University, Japan

Joint work with Koichi Tojo, Kenta Oono, Masahiro Ikeda, and Masashi Sugiyama.

Self-introduction
Isao Ishikawa
Assistant professor@Center for Data Science, Ehime University

Supported by CREST JPMJCR1913
Recent Research Interests:
Mathematical analysis of theoretical backgrounds of machinelearning and data analysis• Analysis of representation power of neural networks• Data analysis via Koopman operator

2

Today's talk structurePart 1

Part 2Introduction.

Details of the theory.

Overview of what we did
and why it's important.

Theoretical preliminaries
and proof machinery.

3

Today's talk structurePart 1

Part 2Introduction.

Details of the theory.

Overview of what we did
and why it's important.

Theoretical preliminaries
and proof machinery.

4

Invertible Neural Networks (INNs)
Goal

Understand theoretical props of invertible neural networks (INNs).
Invertible Neural Networks (INNs) generated byCompositions of ow maps/layers

and af ne transforms A .

f = W1 ∘ g1 ∘ ⋯ ∘ Wk ∘ gk

g1 W1 ⋯ gk Wk(gi ∈, Wi ∈ A )ℝd ℝd ⋯ ⋯ ⋯ ℝd
is parametrized ("trainable") but designed to be invertible.

ff

𝒢

is often rather simple → Composed to model complex f)
fi

fl

ff

𝒢

𝒢

(
𝒢
𝒢

5

Example1: Coupling Flows
Coupling flows (CFs)6[DKB14, PNRML19, KPB19]

Idea: Keep some dimensions unchanged. (Strong constraint!)
CF-INN = Coupling- ow based INN.
Affine-coupling flows (ACFs)[DKB14,DSB17,KD18]

One of the simplest CFs using coordinate-wise af ne transformation:fiflΨs,t,k :Example 2: Neural Ordinary Differential Equations 7
Lip(ℝd) := {f : ℝd → ℝd | f is Lipschitz}

NODE layer

For each f ∈ Lip(ℝd), we de ne an invertible map x ↦ z(1)via an initial value problem [DJ76]
Solve for z(t):z(0) = x,· = f(z(t)) (t ∈ ℝ) .
{z(t)

x

z(1)

NODE layers [CRBD18]
Then, for ℋ ⊂ Lip(ℝd), consider the set of NODEs:

fi

NODEs(ℋ) := {x ↦ z(1) | f ∈ ℋ}

Applications of INNs
Useful properties of INNs (for nicely designed

8)✓ Explicit and ef cient invertibility.
✓ Tractability of Jacobian determinant (for nicely designed).

Usages of INNs

• Approximate distributions (normalizing ows).
μ(g2)* μ(g1)* μ(g3)* μν

[KD18]• Approximate invertible maps (feature extraction & manipulation).

fl

fi

𝒢

𝒢

[DSB17]

Application 1: Distribution Modeling9fNormalizing Flows[KD18]

ux
Express x as a transformation f of a real vector u sampled from pu:

Examplesx = f(u) where u ∼ pu

• Generative modeling [DSB17,KD18,OLB+18,KLSKY19,ZMWN19]• Probabilistic inference [BM19,WSB19,LW17,AKRK19]• Semi-supervised learning [IKFW20]
Training by Maximum Likelihood (Invertibility+Tractable Jacobian!)

By change of variables formula:↓ easily invertible
log px(x) = log pu( f −1(x)) + log detJf −1(x)↑ known↑ tractable(Jf −1: Jacobian of f −1)

Application 2: Function Modeling
Feature Extraction & Manipulation

f −1

u

f

[DSB17]x

1. Extract latent representation u from x by f.

2. Modify u in the latent space (e.g., interpolation).
3. Map back to the data space by f −1.

Examples• Generative modeling [DSB17,KD18,OLB+18,KLSKY19,ZMWN19]• Semi-supervised learning [IKFW20]• Transfer learning [TSS20]

10

How flexible are INNs?

11

INN f is used for distribution modeling (application 1)
and invertible function modeling (application 2).

BUT...
relies on special designs to maintain good properties.
(e.g., CF layers keep some dimensions unchanged)

Complications• The layers have clever speci c designs (e.g., ACFs).
• Function composition is the only way to build complex models.

fi

𝒢(Operations such as addition or multiplications are not allowed.)

Research question

Can these INNs have suf cient
representation power?

fi(Restricted function form → restricted representation power?)

12

This talk is based on the following paper 13
arXiv: 2204.07415
based on the following paper
Paper 1: Coupling-based invertible neural networks are universal
diffeomorphism approximators (NeurIPS 2020)[TIT+20]• Proposed a general theoretical framework to analyze

Oral paper!

the representation power (universalities) of invertible models.

• Analyzed CF-INNs (ACFs and more advanced ones).
Paper 2: Universal Approximation Property of Neural Ordinary
Differential Equations (NeurIPS 2020 DiffGeo4DL Workshop) [TTI+20]• Analyzed NODEs, building on the general framework.

fi• (with minor modi cation to the general framework)

What is "representation power"?
Here,"Representation power" = Universal approximation property.
Definition (informal) [C89,HSW89]f

W r,p-universal approximator:

the model can approximate any target functiong<εw.r.t. W r,p-norm on a compact set.

1/p∥∂α( f − g)(x)∥pdx
( ∫K
)
|α|≤r

W r,p-norm：∥f − g∥r,p,K = ∑KDefinition (informal)
A model is a distributional universal approximator if it cantransform one distribution arbitrarily close to any distribution.
(gn)*μ ⟶ ν
n→∞

ff

ff

(convergence).

μ(g2)*μ(g1)*μ(g3)*μ

ν

14

𝒟
𝒟
𝒟

Target Class
Definition (Approximation targetr)

Fairly large set of smooth invertible maps.
r:= {C r-diffeo of the form f : Uf → f(Uf )}(Uf ⊂ ℝd : open C r-diffeomorphic to ℝd)r

General∞dC-diffeoonℝ{}...and more15

Main Result
Theorem (Theoretical Framework)r,pW -univ.
for

2

r,p

16

(under mild regularity conditions)r,pW -univ.
W -univ.
⇔
⇔
∞
for
for Ξ
c

Ξ : " ow endpoints"∞
c := {τ : コンパクト台微分同相 τ(x, y) = (x, u(x, y))}

𝒮

𝒟

fi

fl

𝒮

𝒮

𝒟

u : ℝd−1 × ℝ → ℝ, (x, y) ∈ ℝd−1 × ℝ

Dist. univ.

⇒ weak top. if r = 0
total var. top. if r ≥ 1

rGeneralΞ

Speci c∞c

Corollariesr,pW -univ.
for

2

r,p

r,p

W -univ.
W -univ.
⇔
⇔
for ∞
for Ξ
c

17
Dist. univ.

⇒ weak top if r = 0
total var top if r ≥ 1
rExamples of Universal Coupling Flows• Sum-of-squares polynomial• Deep sigmoidal

Generalow (SoS- ow) [JSY19]

Speci cow (DSF; aka. NAF) [HKLC18]

yield W r,∞-univ. INNs for∞c (and hence forr

Affine Coupling Flows yield universal INNs

𝒮

𝒟

𝒟
𝒟

𝒮
𝒟

𝒮

fl

fl

fl

fi

fi

𝒮

∞
c

, and also dist-univ.).

(stronger than in [JSY19, HKLC18]).

Af ne Coupling Flows yield L p-univ. INNs for(and hence for 0, and also dist-univ.).

Ξ

∞
c

𝒮

𝒟

𝒟

Corollariesr,pW -univ.
for

2

r,p

r,p

W -univ.
W -univ.
⇔
⇔
for ∞
for Ξ
c

18

⇒ weak top if r = 0
total var top if r ≥ 1

Universality of NODEs
NODEs yield W r,∞-univ. INNs for Ξ(and hence sup-univ. forrDist. univ.

. Also Dist-univ.).

Overview and Recap
What did we do?

Theoretically investigated:
Are our INNs expressive enough?
INNs = Invertible neural networks

Why important?

Models without a representation
power guarantee are hard to rely on.

What is the result?

"Coupling-based INNs (CF-INNs)" and"NODE-based INNs (NODE-INNs)" are"universal function approximators"
despite their special architectures.

Message
CF-INNs and NODE-INNs can be relied on in modelinginvertible functions and probability distributions.

19

Today's talk structurePart 1

Part 2Introduction.

Details of the theory.

Overview of what we did
and why it's important.

Theoretical preliminaries
and proof machinery.

20

𝒟
𝒟

Idea of Proof21

We assume d ≥ 7
Difficulty• We cannot use techniques of functional analysis!
- INNs andr

are not linear spaces

Recall :r:= {C r-diffeo of the form f : Uf → f(Uf )}(r ≥ 0)(Uf ⊂ ℝd : open C r-diffeo to ℝd)- Existing methods do not work….(e.g. Hahn-Banachtheorem, Fourier transform, Stone-Weirestrass theorem,
e.t.c)

Idea• Utilize a concrete structure of the diffeomorphism group !

𝒟

r,p

W -Universal approximatorsℳ: model, set of measurable bijection from ℝd to ℝd (e.g. INNs)ℱ: target functions f : Uf → f(Uf ) (e.g.

r)ℳ is an W r,p-universal approximator for ℱ if
∀f ∈ ℱ, ∀ε > 0, ∀K ⊂ Uf : compact , ∃g ∈ ℳ∥f − g∥r,p,K :=

∑ (∫

|α|≤r

K

∥∂α( f − g)(x)∥pdx

f

g

<ε
K

)

1/p

<ε

22

Relation of universalities

Proposition
For ∞ ≥ r > r′,
A model ℳ is a W r,p-universal approximator for a target ℱ

⟹

￼

￼

A model ℳ is an W r′,p-universal approximator a target ℱ

23

A structure theorem of diffeomorphism groups
Definition (compactly supported diffeomorphisms)
∞
d
d
Di ∞
C
f
:
ℝ
→
ℝ
:
the
set
of
-diffeomorphisms
such thatcf(x) = x outside a compact subset

r

Di ∞
c
(Uf = ℝd )Theorem (Herman, Thurston, Epstein, and Mather)Di ∞c is a simple group (does not have any proper normal
ff
ff

ff

𝒟

subgroup except {Id})24Extension ofr

25

Proposition
For f ∈

r(f : Uf → ℝd) and compact subset K ⊂ Uf

(assume d ≥ 7

if(p, r) = (∞, r)), there exist an af ne transform W ∈ A and g ∈ Di ∞c such thatf |K ∼ W ∘ g |K (with any precision in W r,p-norm)

f

Uf

ii

g (W = 1)

K

RemarkIf (p, r) = (∞,0) , we use Annulus Theorem by Kirby (1969, d ≥ 5 )needs the condition d ≥ 7).
fi

ff

ff

𝒟

𝒟

and an approximation theorem by Cornell (1963) (Cornell's result

Flow endpoints
Definition (flow endpoints Ξ)g ∈ Di ∞c :ow endpoint if there exists a continuous and"additive" map ϕ : [0,1] → Di ∞c such that ϕ(0) = Id and ϕ(1) = g
Ξ := { ow endpoints}

Proposition
The set of nite compositions of ow endpoints (the group
generated by Ξ) is a nontrivial normal subgroup of Di ∞c .
CorollaryFor g ∈ Di ∞c , there exist nite ow endpoints g1, …, gm ∈ Ξ such thatg = g1 ∘ ⋯ ∘ gm.
In particular,

W r,p-univ.

ff

ff

fl

fl

fi

fi

fl

ff

fl

ff

𝒟

for

⟺

r

W r,p-univ.
for Ξ

26

Universality of NODErf∈: target, K ⊂ Uf : compact

∼

f |K

approximate f |K

∃W ∘ h (A & compactly supported C ∞-diffeomorphism)
structure theorem of diffeomorphism group≈∃h1 ∘ h2 ∘ ⋯ ( ow endpoints)
element of NODEs(ℋ)

NODEs(ℋ) := {x ↦ z(1) | f ∈ ℋ}

Paper 2 Result (Analysis of NODEs)(and hence W r,∞-univ. for
fl

ff

𝒟

𝒟

NODEs yield W r,∞-univ. INNs for Ξr. Also Dist-univ. for tot. var.).

27

Proof outline of result in Paper 1r,pW -univ.
for

∞
c

for

u : ℝd−1 → ℝ, (x, y) ∈ ℝd−1 × ℝ

f |K

approximate f |K

f∈r

: target, K ⊂ Uf : compact∃W ∘ h (A & compactly supported C ∞-diffeomorphism)
structure theorem of diffeomorphism group∃h1 ∘ h2 ∘ ⋯ ( ow endpoints Ξ)
Decompose f |K into
simpler mappings
∞
c )
ff

σ1 ∘ τ1 ∘ ⋯ (permutations &
fl

𝒟

ff

𝒮

∃g1 ∘ g2 ∘ ⋯ (nearly Ids)
𝒟𝒮⟺

W r,p-univ.

∞
∞
:=
τ
:
compactly
supported
τ(x,
y)
=
(x,
u(x,
y))
⊂
Di
{
}
c
c

∼

𝒮

r

28

Nearly Id

29Definition (nearly-Id elements)dg ∈ Di ∞Id∥dg(x)
−
I∥
<
1
x
∈
ℝ
:
nearlyelement
if
for
c

Proposition
For a ow endpoint g ∈ Di ∞c , there exist nearly-Id elements
g1, …, gm ∈ Di ∞c such thatg = g1 ∘ ⋯ ∘ gm.
∵ g = ϕ(1) (ϕ : [0,1] → Di ∞c : "additive" and continuous)
Thus, we de ne g1 = g2 = … = gm = ϕ(1/m) for suf ciently large m
fi

ff

fi

fl

ff

ff

ff

Then, g = ϕ(1/m)m and ϕ(1/m) → Id as m → ∞∎Decomposition of nearly Id’s

30

Proposition
For a nearly-Id element g ∈ Di ∞c , there exist τ1, …, τd ∈and σ1, …, σd ∈ d such that∞cg = σ1 ∘ τ1 ∘ ⋯ ∘ σm ∘ τm.
Lemma for this proposition
For g = (gi)di=1 ∈ Di ∞c , if for any k = 1,…, d, the submatrix of its
jacobian(x)( ∂xj+k−1 )∂gi+k−1

ff

𝔖

𝔖

𝒮

is invertible for all x , then there exit τ1, …, τd ∈σ1, …, σd ∈ d such thatg = σ1 ∘ τ1 ∘ ⋯ ∘ σm ∘ τm.
𝒮

ff

i,j=1,…,d−k−1
∞
c

and

Compatibility of approximations and compositions 31• Is a composition of approximations an approximation of thecomposition ?

• We may reduce the problem to approximations of small constituents
Propositionℳ: a set of piecewise C 1-diffeomorphisms
F1, …, Fr : linearly increasing piecewise C 1-diffeomorphims
Assume ∃Hi ∈ ℳ such thatHi ≈ Fi (L p-approximation on any compact sets)
Then, for compact set K ⊂ ℝd, there exist G1, …, Gr ∈ ℳ such that

Gr ∘ ⋯ ∘ G1 ≈ Fr ∘ ⋯ ∘ F1 (L p-approximation on K)

RemarkIf ℳ is composed of locally bounded maps and Fi’s are continuous,
we have a similar proposition for sup-universal approximators.

Proof outline of Main resultr,p

W -univ.
for

∞
c

for

u : ℝd−1 → ℝ, (x, y) ∈ ℝd−1 × ℝ

f |K

approximate f |K

f∈r

: target, K ⊂ Uf : compact∃W ∘ h (A & compactly supported C ∞-diffeomorphism)
structure theorem of diffeomorphism group∃h1 ∘ h2 ∘ ⋯ ( ow endpoints Ξ)
Decompose f |K into
simpler mappings
∞
c )
ff

σ1 ∘ τ1 ∘ ⋯ (permutations &
fl

𝒟

ff

𝒮

∃g1 ∘ g2 ∘ ⋯ (nearly Ids)
𝒟𝒮⟺

W r,p-univ.

∞
∞
:=
τ
:
compactly
supported
τ(x,
y)
=
(x,
u(x,
y))
⊂
Di
{
}
c
c

∼

𝒮

r

32

How the result can be used
You showW r,∞-univ. for

You get∞c⟹

W r,∞-univ. for∞c⟹

W r,p-univ. forr
General

∞
c

fi

𝒟

𝒮

𝒟

𝒮

𝒟

Speci c𝒮r⟹⟹
W r,p-univ. for33rUpgrade Existing Guarantees
Regrading guarantees for existing INN architectures:• Sum-of-squares polynomial• Deep sigmoidal

ow (SoS- ow)

ow (DSF; aka. NAF)

Previously known/claimed [JSY19, HKLC18]:

L ∞-universality for∞c↝
W r,p-universality forr
General
∞
c

𝒟

fl

fl

fl

fi

𝒮

𝒮

𝒟

Speci cr

for r ≥ 034

Definition (distributional universal approximator)ℳ: model, set of measurable bijection from ℝd to ℝd (e.g. INNs): absolutely continuous probability measures with a topologyℳ is a distributional universal approximator w.r.t. the topologyofif∀μ, ν ∈, ∃{gn}∞n=1 ⊂ ℳ(gn)*μ ⟶ ν (convergence inn→∞μ(g1)*μ𝒫

𝒫𝒫𝒫Distributional universal approximators(g2)*μ(g3)*μ

).
ν

35

𝒮

𝒟

36

Proposition
A model ℳ is a W r,p-universal approximator for a target

r

⟹

𝒟

Relation of universalities

A model ℳ is a distributional universal approximator w.r.t- weak topology if r = 0- total variation topology if r > 0
In summary, we obtainr,pW -univ.
for

2

r,p

r,p

W -univ.
W -univ.
⇔
⇔
for ∞
for Ξ
c

Dist. univ.

⇒ weak top if r = 0
total var top if r ≥ 1

Universality of CF-INNs
L p-/sup-univ.
for2

L p-/sup-univ.
L p-/sup-univ.
⇔
⇔
for ∞
for Ξ
c

Distributional⇒
univ.

Affine Coupling Flows yield universal INNs
Af ne Coupling Flows yield L p-univ. INNs for ∞c(and hence for 0, and also Dist-univ. w.r.t weak topology).
Remark
The representation power of invertible neural networks basedon af ne coupling ow is empirically known, and they wereconjectured distributional universal approximator. We
𝒟

fl

fi

fi

fi

𝒮

𝒟

𝒮

af rmatively answer this question.

37

Conclusion & Future Work
Conclusion

Future work

• Proposed a general theoretical• Quantitative analysis:

framework to analyze therepresentation power(universalities) of invertiblemodels.

Estimate the number of layers
required for the approximation
given the smoothness of thetarget.

• Guarantee the representation
power of CF-INNs as an L p-universal approximator.

• Guarantee the representation
power of NODE-INNs as a
W r,∞-universal approximator.

Message
CF-INNs and NODE-INNs can be relied on in modelinginvertible functions and probability distributions.

38

Appendix

References

40[C89] Cybenko, G. (1989).
Approximation by superpositions of a sigmoidal function.
Mathematics of Control, Signals, and Systems, 2, 303–314.
[HSW89] Hornik, K., Stinchcombe, M., & White, H. (1989).
Multilayer feedforward networks are universal approximators.
Neural Networks, 2(5), 359–366.
[JSY19] Jaini, P., Selby, K. A., & Yu, Y. (2019).
Sum-of-squares polynomial ow.
Proceedings of the 36th International Conference on Machine Learning, 97, 3009–3018.
[HKLC18] Huang, C.-W., Krueger, D., Lacoste, A., & Courville, A. (2018).
Neural autoregressive ows.
Proceedings of the 35th International Conference on Machine Learning, 80, 2078–2087.
[KD18] Kingma, D. P., & Dhariwal, P. (2018).
Glow: Generative ow with invertible 1x1 convolutions.
In Advances in Neural Information Processing Systems 31 (pp. 10215–10224).
[PNRML19] Papamakarios, G., Nalisnick, E., Rezende, D. J., Mohamed, S., & Lakshminarayanan, B. (2019).
Normalizing ows for probabilistic modeling and inference.
ArXiv:1912.02762 [Cs, Stat].

fl

fl

fl

fl

fl

[KPB19] Kobyzev, I., Prince, S., & Brubaker, M. A. (2019).
Normalizing ows: An introduction and review of current methods.
ArXiv:1908.09257 [Cs, Stat].

References

41[DKB14] Dinh, L., Krueger, D., & Bengio, Y. (2014).
NICE: Non-linear independent components estimation.
ArXiv:1410.8516 [Cs.LG].
[DSB17]Dinh, L., Sohl-Dickstein, J., & Bengio, S. (2017).
Density estimation using Real NVP.
Fifth International Conference on Learning Representations (ICLR)[AKRK19] Ardizzone, L., Kruse, J., Rother, C., & Köthe, U. (2019).
Analyzing inverse problems with invertible neural networks.
7th International Conference on Learning Representations.
[BM19] Bauer, M., & Mnih, A. (2019).
Resampled priors for variational autoencoders.
In Proceedings of machine learning research, 89, 66–75.
[LW17] Louizos, C., & Welling, M. (2017).
Multiplicative normalizing ows for variational Bayesian neural networks.
In Proceedings of the 34th International Conference on Machine Learning,70, 2218–2227.
[NMT+19] Nalisnick, E. T., Matsukawa, A., Teh, Y. W., Görür, D., & Lakshminarayanan, B. (2019).
Hybrid models with deep and invertible features.
In Proceedings of the 36th International Conference on Machine Learning, 97, 4723–4732.

fl

fl[IKFW20] Izmailov, P., Kirichenko, P., Finzi, M., & Wilson, A. G. (2020).
Semi-supervised learning with normalizing ows.
Proceedings of the 37th International Conference on Machine Learning.

References

42[OLB+18] Oord, A., Li, Y., Babuschkin, I., Simonyan, K., Vinyals, O., Kavukcuoglu, K., Driessche, G.,
Lockhart, E., Cobo, L., Stimberg, F., Casagrande, N., Grewe, D., Noury, S., Dieleman, S.,
Elsen, E., Kalchbrenner, N., Zen, H., Graves, A., King, H., … Hassabis, D. (2018).
Parallel WaveNet: Fast high- delity speech synthesis.
Proceedings of the 35th International Conference on Machine Learning, 80, 3918–3926.
[TSS20] Teshima, T., Sato, I., & Sugiyama, M. (2020).
Few-shot domain adaptation by causal mechanism transfer.
Proceedings of the 37th International Conference on Machine Learning.
[KLSKY19] Kim, S., Lee, S.-G., Song, J., Kim, J., & Yoon, S. (2019).
FloWaveNet: A generative ow for raw audio.
In Proceedings of the 36th International Conference on Machine Learning, 97, 3370–3378.
[ZMWN19] Zhou, C., Ma, X., Wang, D., & Neubig, G. (2019).
Density matching for bilingual word embedding.
Proceedings of the 2019 Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies, Volume 1 (Long andShort Papers), 1588–1598.

fl

fi

fl

[WSB19] Ward, P. N., Smofsky, A., & Bose, A. J. (2019).
Improving exploration in soft-actor-critic with normalizing ows policies.
ArXiv:1906.02771 [Cs, Stat].

References

43[CRBD18] R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud. (2018).
Neural ordinary differential equations.
Advances in Neural Information Processing Systems 31, 6571–6583.
[LLS20] Q. Li, T. Lin, and Z. Shen. (2020).
Deep learning via dynamical systems: an approximation perspective.
arXiv:1912.10382 [cs, math, stat].
[DJ76] W. Derrick and L. Janos. (1976).
A global existence and uniqueness theorem for ordinary differentialequations.
Canadian Mathematical Bulletin, 19(1), 105–107.
[LBH15]

Y. LeCun, Y. Bengio, and G. Hinton. (2015).
Deep learning.
Nature, 521(7553), 436–444.

[ALG19]

C. Anil, J. Lucas, and R. Grosse. (2019).
Sorting out Lipschitz function approximation.
Proceedings of the 36th International Conference on Machine Learning, PMLR 97, 291–301.

[PPMF20]

Pumarola, A., Popov, S., Moreno-Noguer, F., & Ferrari, V. (2020).
C-Flow: Conditional Generative Flow Models for Images and 3D Point Clouds.
2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 7946–7955.