-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathchaos-game-fractal-foliage.html
306 lines (290 loc) · 17.8 KB
/
chaos-game-fractal-foliage.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
<!DOCTYPE html>
<html>
<head>
<link rel="canonical" href="https://hardmath123.github.io/chaos-game-fractal-foliage.html"/>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>Learning to Play the Chaos Game - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<link rel="alternate" type="application/rss+xml" title="Comfortably Numbered" href="/feed.xml" />
<!--
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
-->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
renderMathInElement(document.body, {
// customised options
// • auto-render specific keys, e.g.:
delimiters: [
{left: '$$', right: '$$', display: true},
{left: '$', right: '$', display: false},
{left: '\\begin{align}', right: '\\end{align}', display: true},
{left: '\\(', right: '\\)', display: false},
{left: '\\[', right: '\\]', display: true}
],
// • rendering keys, e.g.:
throwOnError : false
});
});
</script>
</head>
<body>
<header id="header">
<script src="static/main.js"></script>
<div>
<a href="/"><span class="left-word">Comfortably</span> <span class="right-word">Numbered</span></a>
</div>
</header>
<article id="postcontent" class="centered">
<section>
<h1>Learning to Play the Chaos Game</h1>
<center><em><p>I, Thomasina Coverly, have found a truly wonderful method whereby all the forms of nature must give up their numerical secrets and draw themselves through number alone…</p>
</em></center>
<h4>Friday, December 25, 2020 · 7 min read</h4>
<p>It’s Christmastime again! Shall we talk about trees? This post is about my new
holiday hobby: hallucinating tree-shaped fractals using our old friend,
gradient descent.</p>
<p><img src="static/chaos-game/tree-building.gif" alt="Christmas tree"></p>
<hr>
<p>But — let me start at the beginning. For a variety of reasons, the cover
image of Douglas Hofstadter’s <a href="https://en.wikipedia.org/wiki/I_Am_a_Strange_Loop"><em>I am a Strange
Loop</em></a> has been on my mind
this month. I have been thinking a lot about this wonderful image created by
pointing a camera at a projector that displays what the camera is seeing. In
modern terms: what happens if you screen-share the screen sharing window? This
happens:</p>
<p><img src="static/chaos-game/strange-loop.png" alt="from the cover of the book"></p>
<p>Such “feedback loop” recursions often rapidly converge to breathtaking
fixed-points. The NYC MoMath even has an <a href="https://momath.org/25-feedback-fractals-1/">art
installation</a> that lets you play
with a camera-and-projector setup to make <a href="https://twitter.com/momath1/status/824740594564075520">wonderful
patterns</a>.</p>
<p>As you can imagine, there is a mathematical theory here. At risk of ruining the
mystery, I will tell you about it, though without writing any equations. :-)
The theory is the theory of <a href="https://en.wikipedia.org/wiki/Iterated_function_system">Iterated Function
Systems</a>, which is
almost exactly what it sounds like. Start with a set of affine functions
(affine because that’s what camera-projector-systems do) and repeatedly apply
them to a set of points, taking the union at each step. Regardless of where you
start, you will soon end up with a fractal structure which is the fixed point
of the system. Why fractal? —because the self-similarity comes from the
infinitely-nested composition of the affine functions.</p>
<p><img src="static/chaos-game/Ifs-construction.png" alt="from Wikipedia"></p>
<p>There are theorems that ensure convergence towards and uniqueness of this fixed
point in the limit, but… it’s believable enough, don’t you think? Following
your intuition, you can build Sierpinski Triangles and <a href="https://en.wikipedia.org/wiki/Barnsley_fern">Barnsley
Ferns</a> and all sorts of other
beautiful structures using an IFS. I refer you to Section 8.2 of <a href="http://algorithmicbotany.org/papers/#abop"><em>The
Algorithmic Beauty of Plants</em> by Prusinkiewicz and Lindenmayer (yes, <em>that</em>
Lindenmayer)</a> for more botanical
connections.</p>
<p><img src="static/chaos-game/Fractal_fern_explained.png" alt="from Wikipedia"></p>
<hr>
<p>Now here is the question that has been on my mind: if I give you a picture of a
fractal-fern, can you give me a set of affine functions whose fixed point is
that fern? This is the <a href="https://en.wikipedia.org/wiki/Iterated_function_system#The_inverse_problem"><em>inverse
problem</em></a>
for IFSes. According to Wikipedia, this problem has real-world applications in
image compression, but it is <em>hard</em> to do in general.</p>
<p>Hmm. Interesting. Can our favorite tool, gradient descent, come to the rescue?
At least in an approximate sense? Recall that a two-dimensional affine function
is really just a 3x3 matrix (with 6 free parameters) that encodes the details
of the transformation. If we could easily compute images of IFS fixed points
from a set of matrices, then perhaps we could try to optimize the parameters of
these matrices to make the fixed point look the way we want it to.</p>
<p>The challenge, of course, is efficiently <em>finding</em> the fixed point —
repeatedly rasterizing and compositing affine transformations on images sounds
expensive — and doing so differentiably sounds like a scalability nightmare!
But there is a wonderful solution to this problem, which is to play the
so-called “<a href="https://en.wikipedia.org/wiki/Chaos_game">chaos game</a>.” Instead of
<em>densely</em> applying all the functions to all the points on the plane, you can
<em>sparsely</em> approximate the fixed point as follows: Start with a point — any
point! — and <em>randomly</em> select one of the affine functions of the IFS and
apply it to the point. Repeat this process with the new point. It turns out
that in the limit, the “trail” left behind by this wandering point converges to
the fixed point of the IFS. (This, too, is a theorem, but again I think it is
believable enough that I will not demand a proof.) This is what the “chaos
game” looks like for the Sierpinski triangle; notice how the salt-and-pepper
spattering of points soon converges boldly into the fractal we know and love
(it’s an animation — stare for a few seconds).</p>
<p><img src="static/chaos-game/Sierpinski_chaos_animated.gif" alt="from Wikipedia"></p>
<p>So here is the plan: we start with a point, and play the chaos game with our
current IFS matrices to obtain a <em>point cloud</em> that stochastically approximates
the fixed-point. Then, we compare this <em>point cloud</em> to our target fern-image
to obtain a “loss.” Finally, we update our IFS matrix parameters to minimize
this loss, until at last the fixed-point converges to the target image. It’s
just “machine learning,” really: we’re learning to play the chaos game!</p>
<p>Here is an outline of the algorithm (with some details elided):</p>
<pre><code class="lang-python"># initialize IFS
F = [random_3x3_affine() for _ in range(4)]
o = torch.optim.Adam(F, lr=0.0001)
for step in range(100_000):
o.zero_grad()
# start at origin
v = torch.tensor([0., 0., 1.])
# play the chaos game once
trace = []
for _ in range(200):
# applying an affine function is just
# a matrix multiplication!
v = torch.matmul(random.choice(F), v)
trace.append(v)
# treat the trace as a point cloud
loss = compare(target_image, trace)
# update parameters
loss.backward()
o.step()
</code></pre>
<p>Ah! Actually, there is <em>one</em> detail that I <em>should</em> explain: how do you compare
a point cloud and an image? My idea is to convert the target image to a
<em>second</em> point cloud by uniformly sampling points from it, for example by
rejection-sampling. Then you can compare the two point clouds by the so-called
“chamfer distance,” which is the mean distance from each point to its nearest
neighbor in the opposite point cloud. This is quadratic-time to compute, and
the most expensive part of the whole operation, but with ~100 points in each
set it is quite doable.</p>
<blockquote>
<p>A pedagogical aside: notice that the “trick” here is really a <em>change in
representation.</em> This optimization problem is easier to solve on point clouds
than on raster images! An important lesson, that applies across the
ML-for-graphics domain… and more broadly to all differentiable programming
enterprises.</p>
</blockquote>
<hr>
<p>Remarkably, this zany scheme works quite well! Let’s try it with a heart. (A
heart, because it’s an easy low-entropy shape, but also because it felt
symbolically appropriate in relation to Hofstadter’s broader philosophical
project of souls-within-souls-within-souls.)</p>
<p>When we initialize the system with 4 random affine transformations, the trail
left behind by the chaos game is very unimpressive. The sparsity is because I
simulate only 200 steps of the chaos game for each step of gradient descent —
there’s a tradeoff between noise and computation time, of course, as there is
with any form of SGD.</p>
<p><img src="static/chaos-game/heart-samples-early.png" alt="chaos game on a heart"></p>
<p>Okay. Time to optimize! Here is what it looks like after 100K steps of
optimization with an Adam optimizer (that’s about 40 minutes of wall-time
computation on my old MacBook). It looks pretty good, don’t you think? The
chamfer distance scheme works!</p>
<p><img src="static/chaos-game/heart-samples.png" alt="chaos game on a heart"></p>
<p>Now we can export the four affine matrices out from PyTorch and work out the
“true” fixed point with a more expensive offline computation (for example, by
simulating a few <em>million</em> steps of the chaos game). It looks like this — not
perfect, and indeed quite crayon-scribble-ey, but clearly <em>something</em>
interesting has happened, and the result is convincingly heartlike.</p>
<p><img src="static/chaos-game/heart-fractal.png" alt="extended chaos game on a heart"></p>
<p>Where is the fractal structure hidden in this heart? This needs some
vizualization tooling to see clearly. After a bit of JS-canvas-hacking: here is
a GIF of the heart that reveals its fixed-point structure.
Hearts-in-hearts-in-hearts!</p>
<p><img src="static/chaos-game/heart.gif" alt="Heart"></p>
<p>I will admit to blinking a few times when I first saw this animation play out
in full — I did <em>not</em> expect it to work, and even now I find myself marveling
at this creation? discovery? of a heart encoded in 24 numbers.</p>
<hr>
<p>But it still doesn’t look <em>quite right</em> — the fractalness isn’t <em>obvious</em>.
How come? It’s because our affine transformations stretch and squash the heart
into almost unrecognizable blobs. A final, natural improvement is to force our
affine transformations to be <em>rigid</em>, so that there isn’t any squishing or
skewing in the fractal. This is actually not too bad to implement: the solution
to problems of constraint are typically reparametrizations, and indeed in this
case we can simply reparametrize the matrices in terms of a rotation, an
(isotropic) scale, and a translation. Now we’re down from 6 parameters per
matrix to just 4 — even more magical! The result is a much more “obviously”
fractal-ey fixed point, simply because your eye can more easily pick out the
structural recursion when it is made of rigid motions.</p>
<p>Let’s take it for a — pardon — <em>spin!</em></p>
<p>Since I promised you trees, here is some fractal foliage. The target image was
a picture of a maple leaf! I’d never thought about this before, but indeed a
maple leaf contains within it an echo of the whole tree. (Full disclosure: it
takes a couple of randomized restarts to get a really impressive result — the
low dimensionality of the fractal’s parametrization leads to the same
stuck-in-a-local-optimum woes that differentiable rendering folks face all the
time…)</p>
<p><img src="static/chaos-game/foliage.gif" alt="Leaf"></p>
<p>This one uses just three matrices — experimentally, three matrices tend to be
enough to get really good results, and more just lead to very busy and crowded
fractals. (I don’t know if there is a word for number-of-maps–in-an-IFS, but
let’s call it the IFS’s <em>arity</em>. In this terminology, I like <em>ternary</em> IFSes.)</p>
<p>And finally, since I promised you Christmas trees…</p>
<p><img src="static/chaos-game/christmas-tree.gif" alt="Christmas tree"></p>
<p>This last animation is actually absolutely <em>baffling</em> to me. In part, this is
because of how <em>treelike</em> the fractal turned out — here it is overlayed
against the silhouette I optimized against. Can you imagine this is encoded by
just 12 parameters? Odd.</p>
<p><img src="static/chaos-game/christmas-tree-match.png" alt="Tree vs. silhouette"></p>
<p>But even more bafflingly: the actual geometry of the recursion is <em>nothing</em>
like the tree recursion geometry you and I are used to from CS106! Compare the
GIF above to Barnsley’s Fern: while Barnsley turns each full leaf into two
smaller leaves with “semantic” affine maps, this Christmas tree does all sorts
of <em>bizarre</em> uninterpretable cartwheels and somehow almost magically works
itself out in the end. It is mesmerizing to me, I can stare at it for minutes
at a time.</p>
<p>When you think about it, it is quite shocking that a Christmas tree is the
<em>unique</em> fixed point of these 3 rigid affine maps. “Beautiful” isn’t the word
for it — neither is “grotesque” (though both words have been used by various
people I have shared this with). There is something just unsettlingly
fascinating about the way something magical <em>pops out</em> from three rectangles.
Maybe I should have demanded a proof of that theorem after all…</p>
<hr>
<p>There is so much more to say about all of this. What shapes are easiest to
IFSify, and why? In higher dimensions, can we treat the IFS as a kind of
SVD-esque dimensionality reduction scheme for data (i.e. literal point clouds)?
What kind of data would it make sense to do this for — where do you find
spatial self-similarity? Do point clouds have an inherent IFS “dimensionality”
(in terms of, say, the number of affine transformations you need to get a good
approximation)? With some more work, could SGD be a legitimate solution to the
open problem of fractal compression?</p>
<p>It’s a lot to think about — but for now… well, there is a Calvin and Hobbes
gag that begins with Calvin saying “I’ve been thinking” and Hobbes interrupting
“On a weekend?” That’s how I’ve been feeling this winter break! Now it is time
to shutdown the jupyter kernel and get some rest — Comfortably Numbered will
return in 2021!</p>
<p>(Jupyter notebook for this blog post available <a href="https://github.com/kach/chaos-game-fractal-foliage">on
Github</a>.)</p>
<hr>
<p>Update (Dec 27): Check out some
<a href="https://news.ycombinator.com/item?id=25551557">improvements</a> made by a reader!</p>
<p>Update (Dec 29): I was pointed to <a href="http://demo.cs.brandeis.edu/papers/wcci98.pdf">a 1998
paper</a> (Melnik and Pollack) that
(independently!) tells <em>exactly</em> the same story. I’m struck by how closely the
two expositions align. There is something deeply comforting about rediscovering
a place someone else has visited once-upon-a-time, like finding a flag buried
under the snow on a mountaintop — a kind of storybook enchantment that sits
across the table from loneliness.</p>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
</article>
<footer id="footer">
<div>
<ul>
<li><a href="https://github.com/kach">
Github</a></li>
<li><a href="feed.xml">
Subscribe (RSS feed)</a></li>
<li><a href="https://twitter.com/hardmath123">
Twitter</a></li>
<li><a href="https://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
CC BY-NC 3.0</a></li>
</ul>
</div>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>