-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1395 lines (1193 loc) · 73.1 KB
/
Copy pathindex.html
File metadata and controls
1395 lines (1193 loc) · 73.1 KB
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
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Generator Matching without Generators (rough draft)</title>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script>
window.MathJax = {
tex: {
inlineMath: [['$', '$'], ['\\(', '\\)']],
macros: {
R: "\\mathbb{R}",
E: "\\mathbb{E}",
Var: "\\mathrm{Var}",
Prob: "\\mathbb{P}"
}
}
};
</script>
<style>
:root {
--text-color: #333;
--bg-color: #fcfcfc;
--primary-color: #0056b3;
--accent-color: #d63384;
--code-bg: #f1f3f5;
--border-color: #e9ecef;
}
body {
font-family: "Georgia", "Times New Roman", serif;
line-height: 1.6;
color: var(--text-color);
background-color: var(--bg-color);
max-width: 800px;
margin: 0 auto;
padding: 2rem 1rem;
}
h1, h2, h3 {
font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif;
color: #111;
margin-top: 2rem;
}
h1 { font-size: 2.2rem; margin-bottom: 0.5rem; text-align: center; }
h2 { border-bottom: 1px solid var(--border-color); padding-bottom: 0.5rem; }
.abstract {
background-color: var(--code-bg);
padding: 1.5rem;
border-radius: 8px;
font-style: italic;
margin: 2rem 0;
border-left: 4px solid var(--primary-color);
}
.interactive-figure {
background: white;
border: 1px solid #ddd;
border-radius: 8px;
box-shadow: 0 4px 6px rgba(0,0,0,0.05);
margin: 2rem 0;
padding: 1rem;
text-align: center;
}
canvas {
display: block;
margin: 10px auto;
background: #fff;
border: 1px solid #eee;
cursor: crosshair;
max-width: 100%;
}
.controls {
margin-top: 15px;
font-family: -apple-system, sans-serif;
font-size: 0.9rem;
display: flex;
justify-content: center;
align-items: center;
gap: 15px;
flex-wrap: wrap;
padding: 10px;
background: #f8f9fa;
border-radius: 6px;
}
button {
padding: 6px 12px;
background: var(--primary-color);
color: white;
border: none;
border-radius: 4px;
cursor: pointer;
transition: background 0.2s;
font-size: 0.85rem;
}
button:hover { background: #004494; }
button.secondary { background: #6c757d; }
button.secondary:hover { background: #5a6268; }
button.active { background: var(--accent-color); }
input[type=range] { vertical-align: middle; }
input[type=number] { width: 50px; padding: 4px; }
.caption {
font-size: 0.85rem;
color: #666;
margin-top: 0.8rem;
font-family: -apple-system, sans-serif;
line-height: 1.4;
}
</style>
</head>
<body>
<header>
<h1>Generator Matching without Generators</h1>
<div style="text-align: center; color: #666; margin-bottom: 2rem;">
or "Generator Matching for Computer Scientists"
</div>
<div style="text-align: center; color: #666;">
by Ben Murrell
</div>
</header>
<div class="abstract">
<strong>Motivation.</strong> Generator Matching (GM) is an incredible framework that subsumes nearly all flow matching and diffusion models.
Understanding it unlocks the ability to easily construct <a href="https://arxiv.org/pdf/2511.09465">entirely novel methods</a>, and let's you understand existing approaches with greater clarity.
Depending on your math background, however, it can be somewhat unapproachable, since it uses the formalism of <a href="https://en.wikipedia.org/wiki/Infinitesimal_generator_(stochastic_processes)">generators</a> to handle the generality needed to cover all kinds of stochastic processes and state spaces.
Here we use a simple reframing to attempt to explain Generator Matching without Generators, using only concepts from basic probability. Working through this should make it clear why GM works, and give you the ability to construct your own GM methods without learning measure theory and advanced stochastic processes.
<p>
Note: If you are in the target audience for this simplified presentation of GM, this will not be easy reading, and will require some work on your side. But it will be worth it. So set aside a few quiet hours, grab some coffee, and get ready to dive in.
</p>
</div>
<section>
<h2>Preliminaries</h2>
<p>
In generative modeling, you typically have a training dataset of samples from some "target" distribution, and you wish to train a model that can generate new samples from this distribution. These could be images, sequences of text, songs, proteins, etc, each with their own state space (continuous, discrete, manifold, or mixtures of these).
<p> This is what Generator Matching (GM) lets you do. Like <a href="https://mlg.eng.cam.ac.uk/blog/2024/01/20/flow-matching.html">flow matching</a> (which GM generalizes), this is done by starting from an easy-to-sample-from "prior" distribution, and learning how to transform this into the target distribution. It does this through many small steps in what we call "time" (which we denote with $t$), starting at $t=0$ (the simple prior) and ending at $t=1$ (the target distribution).
</p>
<p>
<img width="815" height="357" alt="Image" src="https://github.com/user-attachments/assets/1d156b8b-68aa-47dd-a39d-5f0e4e2b4675" />
</p>
<p>
We denote the state of the model at time $t$ as $x_t$. For example, if you are modeling images, then $x_1$ would be an image from the training dataset, and $x_0$ would be an image with random pixel values.
</p>
<p>We need to introduce the notion of a "conditional processs". GM requires that you can:</p>
<ul>
<li>sample a $z$ from some distribution $p(z)$, which controls where the process ends when $t=1$.</li>
<li>conditioned on $z$, sample $x_{t+\Delta t}$ from $p(x_{t+\Delta t} \mid x_t, z, t)$ for some small time step $\Delta t$;</li>
</ul>
<p>What is $z$? Often $z$ just holds a single training data sample (which we'll call $x_1^z$), but $z$ is an extremely flexible "latent variable", and can include other information that controls the path of the process. More about that later.</p>
<p>You can think of $p(x_{t+\Delta t} \mid x_t, z, t)$ as a function that takes the current state $x_t$, the latent $z$, and the time $t$, and returns the next state $x_{t+\Delta t}$, which may or may not involve some randomness. The only constraint is that when you repeatedly step through time by calling this function over and over, when $t$ reaches $1$, the state $x_1^z$ will be the sample from the training distribution that is associated with the latent $z$.</p>
<p>With a simple prior distribution $p(x_0)$ that governs where the process starts, $p(x_{t+\Delta t} \mid x_t, z, t)$ specifies the distribution of each subsequent step, and pins down what we call the "conditional path" (because it is conditioned on $z$ to terminate at a given $x_1$).</p>
</section>
<section>
<h2>The marginals of the process $p(x_t \mid t)$, and the conditional posterior distribution $p(z \mid x_t, t)$.</h2>
<p>Importantly, we can sample from $p(x_t \mid z, t)$, the conditional process at any $t$, by first sampling $z$, sampling $x_0$ from the prior, and then stepping through $p(x_{t+\Delta t} \mid x_t, z, t)$ for each step until $t$ is reached. A central distribution of interest is the <strong>marginal distribution</strong> of $x_t$ at each time $t$. If we have $n$ training data samples, and each $z$ has equal probability, then:
$$p(x_t \mid t) = \frac{1}{n} \sum_{i=1}^n p(x_t \mid z_i, t)$$
</p>
<p>Conceptually, you can think about this as the distribution you get when you repeatedly sample $z$ from $p(z)$ and then sample $x_t$ from $p(x_t \mid z, t)$ and accumulate the $x_t$ samples. This is the marginal distribution of $x_t$ at each time $t$. <strong>Note:</strong> by construction, since each $z$ terminates at a sample from the training distribution, this marginal distribution at $t=1$ is the same as the training data distribution $p(z)$.</p>
<p>Using Bayes theorem, we can then write the posterior distribution of $z$ given $x_t$ and $t$ as $p(z \mid x_t, t) \propto p(x_t \mid z, t)$ (since $p(z)$ is a constant). In practice we will not need to calculate it, but we do need to understand what it means to explain GM.</p>
</section>
<section>
<h2>A concrete example</h2>
<p>As a working concrete example, we'll consider the case of standard <a href="https://arxiv.org/abs/2210.02747"> flow matching</a>, where the state space is continuous, $p(x_0)$ is a Gaussian distribution, and the conditional path is simply a straight line that points towards $x_1^z$, the training data point associated with $z$. In this case, $p(x_{t+\Delta t} \mid x_t, z, t)$ is just a point mass at $x_t + \frac{(x_1^z - x_t)\Delta t}{1-t}$.</p>
<p>With this example, $p(z \mid x_t, t)$ is simple to compute. There is no noise in the conditional process, so the only source of uncertainty is in the prior $p(x_0)$. Given $x_t$ and $t$, we can thus compute $p(z \mid x_t, t)$ for each $z$ proportional to the probability of $x_0$ under the Gaussian prior $p(x_0)$, and we can get $x_0$ by extrapolating backwards from $x_1^z$ through $x_t$:
$$ x_0 = -t \cdot \frac{x_1^z - x_t}{1-t} $$
</p>
<p>The following interactive figure shows an example with a one-dimensional state, where you control $t$ and $x_t$, and $p(z \mid x_t, t)$ is shown as the opacity of the blue lines. Move around a little and understand how the training data points at $t=1$ get reweighted as $t$ and $x_t$ change.</p>
</section>
<!-- Interactive Figure 1: The Posterior -->
<div class="interactive-figure">
<h4 style="margin-top:0;">$p(z \mid x_t, t)$</h4>
<canvas id="posteriorCanvas" width="600" height="450"></canvas>
<div class="controls">
<div style="border-left:1px solid #ccc; padding-left:10px; margin-left:10px;">
<label>N: <input type="number" id="inputN" value="40" min="1" max="100"></label>
<button id="btnResampleData" class="secondary">Resample Points</button>
</div>
</div>
<div class="caption">
<strong>Instructions:</strong> Move the <span style="color:green">Green Dot</span> ($x$).
The opacity of the <span style="color:blue">Blue Lines</span> represents the posterior probability $p(z|x_t,t)$.
</div>
</div>
<section>
<h2>A “resample–$z$ process"</h2>
<p>Stepping away from the concrete straight-line example and back to the general case, recall that we can use the conditional process to draw samples from the marginal distribution $p(x_t \mid t)$ by first sampling $z$ from $p(z)$, sampling $x_0$ from the prior, and then stepping through $p(x_{t+\Delta t} \mid x_t, z, t)$ for each step until $t$ is reached. Now consider a modified version of this that repeats the following:
<blockquote>
<ol>
<li>sample a fresh latent $z_{new}$ from the posterior $p(z \mid x_t, t)$;</li>
<li>sample $x_{t+\Delta t}$ from $p(x_{t+\Delta t} \mid x_t, z_{new}, t)$;</li>
</ol>
</blockquote>
<p>I.e. at every time step, forget the old $z$, redraw $z_{new}$ using $p(z\mid x_t,t)$, and take a small step from the same conditional process, but conditioned on $z_{new}$. We'll call this the "resample–$z$ process".</p>
<p><strong>Critically,</strong> the marginal distribution of samples from the resample–$z$ process is the same as the marginal distribution of samples from the original conditional process.</p>
<p>If this is not obvious, we can argue this by induction over time steps. If we assume the marginals $p(x_t \mid t)$ will match at $t$, then they will match at $t+\Delta t$ as well.</p>
<ul>
<li><strong>Procedure A (conditional process):</strong>
Draw $x_t,z$ by first drawing $z$ from $p(z)$ and then drawing $x_t$ from $p(x_t \mid z, t)$, resulting in the distribution $p(x_t \mid z, t)p(z)$.
</li>
<li><strong>Procedure B (resample–\(z\)):</strong>
Assume we have already drawn $x_t$ from $p(x_t \mid t)$. Then draw $z$ from $p(z \mid x_t, t)$, resulting in the distribution $p(z \mid x_t, t)p(x_t \mid t)$.
</li>
<li>But $p(z \mid x_t, t)p(x_t \mid t) = p(x_t \mid z, t)p(z) = p(x_t, z \mid t)$.</li>
<li>Thus both have the same joint distribution over $(x_t, z)$ at time $t$, and use the same conditional step rule to produce the next state at time $t+\Delta t$, so the joint distribution at time $t+\Delta t$ is the same for both procedures, and the marginal distributions $p(x_t \mid t) = \sum_z p(x_t, z \mid t)$ will be the same as well.</li>
<li>Given that the starting marginal distributions are both $p(x_0)$, by induction the marginals will match for all time steps.</li>
</ul>
</div>
<p>Basically, exchanging one $z$ for another from $p(z \mid x_t, t)$ at any point in the path doesn't change the marginal distribution $p(x_t \mid t)$. It doesn't matter if we never resample $z$, resample it every tiny step, or sparsely resample it a few times over the course of the paths, you always wind up with the same marginal distribution $p(x_t \mid t)$. This is going to be crucial, so make sure you're happy with it.</p>
<p>Switching back to our concrete example (but this time with a two-dimensional state, and animating time $t$), the next interactive figure shows a sequence of paths, starting from a pure conditional process (no resampling) and then gradually increasing the resampling interval.</p>
</section>
<!-- Interactive Figure 2: Resample vs Average -->
<div class="interactive-figure">
<h4 style="margin-top:0;">Resampling faster and faster until things are smooth</h4>
<canvas id="simCanvas" width="800" height="400"></canvas>
<div class="controls">
<button id="btnAutoPlay" class="secondary">▶</button>
<!--<button id="btnResetSim">Restart Simulation</button>-->
<!--<button id="btnRandomizeSim" class="secondary">Randomize</button>-->
<button id="btnToggleMode" class="active">Mode: Conditional Process</button>
</div>
<div class="controls" id="resampleControls" style="background: #eef;">
<label>Resample Interval (Step Size):
<input type="range" id="stepSizeSlider" min="1" max="100" value="20">
</label>
<span id="stepDisplay">0.020</span>
</div>
<div class="caption" id="simCaption">
<span style="color:#d63384; font-weight:bold;">Red Example Path</span> leads towards <span style="color:#0056b3; font-weight:bold">Solid Blue Target</span>. <br/>
<strong>Mode: Conditional Process:</strong> Moves according to the sampled $z$ for the entire path. <br/>
<strong>Mode: Resampling:</strong> Periodically it picks a new $z$ and changes direction. <br/>
<strong>Mode: Averaged:</strong> Moves in the average direction of all targets, weighted by the posterior $p(z|x,t)$. <br/>
<em>Click to place the starting point of the example path.</em>
</div>
</div>
<section>
<h2>The infinite switching limit</h2>
<p>As seen above, the marginals $p(x_t \mid t)$ are the same for the conditional process (without $z$ resampling) and when repeatedly resampling $z$, even though the paths themselves look very different. Without resampling, the paths are straight lines from $x_0$ to $x_1$, and with slow resampling, the paths are more jagged, zig-zagging back and forth.</p>
<p>But something interesting happens as we increase the resampling interval. When you have a large number of switches over a small interval, the law of large numbers kicks in and the path behaves as if it were a smooth average over all of the different resampled $z$, where the average is weighted by the posterior probability $p(z \mid x_t, t)$.</p>
<p>But if switching at any rate preserves the marginal distribution $p(x_t \mid t)$, then this means that we can make the switching rate arbitrarily high and the path, which then converges to a smooth posterior-weighted average, will also preserve the marginal distribution $p(x_t \mid t)$.</p>
<p><strong>The key realization</strong> that powers GM (and flow matching, and diffusion models, etc) is that instead of trying to learn the posterior distribution $p(z \mid x_t, t)$, <em>we can train a model to directly learn this average step.</em></p>
<p>For the straight-line example used in the figures, the conditional velocity is $u_t(x\mid z) = \dfrac{x_1^z - x}{1-t}$. With a discrete set of candidates $z_1,\dots,z_N$ and posterior weights $p(z_k\mid x,t)$, the <em>posterior–averaged velocity</em> is</p>
<p style="text-align:center;">$$ \bar{u}_t(x) \;=\; \sum_{k=1}^N p(z_k\mid x,t)\,\frac{x_1^{z_k} - x}{1-t}. $$</p>
<p>The widget below is just like Interactive Figure 1, but also shows this averaged direction (extended all the way to $t=1$) as a <span style="color:#d63384; font-weight:bold;">red arrow</span>. The <span style="color:#0056b3; font-weight:bold;">blue lines</span> indicate the posterior weights over candidate $z$ values.</p>
<!-- Interactive Figure 3: Posterior with Arrow -->
<div class="interactive-figure">
<h4 style="margin-top:0;">Time-Dependent Posterior (with Averaged Velocity)</h4>
<canvas id="posteriorCanvas3" width="600" height="450"></canvas>
<div class="controls">
<div style="border-left:1px solid #ccc; padding-left:10px; margin-left:10px;">
<label>N: <input type="number" id="inputN3" value="40" min="1" max="100"></label>
<button id="btnResampleData3" class="secondary">Resample Points</button>
</div>
</div>
<div class="caption">
<strong>Instructions:</strong> Move the <span style="color:green">Green Dot</span> ($x$).
The opacity of the <span style="color:blue">Blue Lines</span> represents the posterior probability $p(z|x,t)$.
<br>
The <span style="color:red">Red Arrow</span> points to the posterior-averaged \(x_1\) (hits the $t=1$ line).
</div>
</div>
</section>
<section>
<h2>Training</h2>
<p>So we need to build a model $f_\theta(t, x)$ that takes in $(t, x_t)$ and outputs the average step $\bar{u}_t(x_t)$. How do we train it?</p>
<p>The key insight is that this is just a <strong>regression problem</strong>, and we already have everything we need to generate training data.</p>
<h3>Generating training data</h3>
<p>We can easily sample from the joint distribution $p(x_t, z \mid t)$ by:</p>
<ol>
<li>sampling $z$ from $p(z)$ (i.e., picking a random training example);</li>
<li>sampling $x_0$ from the prior $p(x_0)$;</li>
<li>running the conditional process forward to get $x_t$.</li>
</ol>
<p>For each such sample $(x_t, z)$, we know the conditional step $u_t(x_t \mid z)$ exactly—it's just a function of $x_t$, $z$, and $t$.</p>
<h3>What loss gives us the posterior average?</h3>
<p>In our "drift-only" flow matching working example, if we minimize the mean squared error (MSE) between our model's output $f_\theta(t, x_t)$ and the conditional step $u_t(x_t \mid z)$ over samples from $p(x_t, z \mid t)$, we get exactly the posterior-averaged step we want.</p>
<p>To see why, recall that minimizing MSE gives you the <em>conditional expectation</em>. If you have pairs $(x, y)$ drawn from some joint distribution and you minimize $\E[(f(x) - y)^2]$, the optimal $f$ is $f^*(x) = \E[y \mid x]$.</p>
<p>In our case, we're drawing $(x_t, z)$ from $p(x_t, z \mid t)$ and regressing against $u_t(x_t \mid z)$. The optimal model is therefore:
$$f^*(t, x_t) = \E[u_t(x_t \mid z) \mid x_t, t] = \sum_z p(z \mid x_t, t) \, u_t(x_t \mid z) = \bar{u}_t(x_t).$$
</p>
<p>This is exactly the posterior-averaged step! <strong>We never need to compute $p(z \mid x_t, t)$ explicitly.</strong> The averaging happens automatically through the regression.</p>
<h3>Bregman divergences</h3>
<p>But MSE is only one option, and it might not be ideal for the quantity we wish to average. There is a larger family of losses that can be used to learn conditional expectations: <strong><a href="https://en.wikipedia.org/wiki/Bregman_divergence"></a>Bregman divergences</a></strong>. In GM, you can use any Bregman divergence you want. Some will work better than others in practice, but they'll all be learning the right thing.
<h3>The training algorithm</h3>
<p>The training procedure is then:</p>
<ol>
<li>Sample a batch of training examples $\{z_i\}$.</li>
<li>For each $z_i$, sample $t_i$ uniformly from $[0, 1)$ and generate $x_{t_i}$ from the conditional process.</li>
<li>Compute the conditional step $u_{t_i}(x_{t_i} \mid z_i)$.</li>
<li>Update $\theta$ to minimize $\sum_i D(u_{t_i}(x_{t_i} \mid z_i), f_\theta(t_i, x_{t_i}))$, where $D(.,.)$ is a Bregman divergence.</li>
</ol>
Note: here we've written the conditional step as $u_{t_i}(x_{t_i} \mid z_i)$, which really only makes sense for the pure-flow case. But the same training procedure applies exactly to other cases, just swapping out the $u_{t_i}(x_{t_i} \mid z_i)$.
<p>At this point, consider taking a moment to <a href="https://murrellgroup.github.io/GeneratorMatchingWithoutGenerators/spiral_flow.html">try to train your own flow matching model</a> in the browser.</p>
</section>
<section>
<h2>Dimensions.</h2>
<p>In the above, we avoided discussing the dimensionality of the state space. For our 'pure-drift' running example, the state is a vector in Euclidean space, and an infinitesimal step is a vector in the same space. Here, even though the state can have many continuous elements, it is straightforward to average over steps in this space, and to have a model output an 'average step', and no further comment about dimensionality is needed.</p>
<p>But this is not the case in other spaces. Consider a sequence of discrete tokens, for example. A conditional process in this space has events that occur in continuous time and trigger changes in the sequence, and you train a model to learn the average rates of these events. But in the most general case, a single event on this space can turn any sequence into any other sequence, changing multiple tokens at once. This works in theory, but would require a neural network to output rates for $T^L-1$ events, where $T$ is the number of tokens and $L$ is the length of the sequence, which is infeasible.</p>
<p>To avoid this issue we can construct our conditional process such that events that cause discontinious changes to the state act only upon single elements of the state. When you additionally consider that events that occur stochastically in continuous time never occur at exactly the same time as each other, this means that any infintesimal step only allows a single element to change. Knowing that no two elements can simultaneously change restricts the space of 'neighbours' of the current state to 'all sequences that differ from the current one at only one element'.</p>
<p>Practically, this means that the model need only output $(T-1) \times L$ rates. If we additionally restrict our conditional process such that the rates for element $i$ of $x_t$ only depend on element $i$ of $x_1^z$ then this lets us consider the 'average step' separately for each element of the state space.</p>
<p>So in the $z$-resampling process, while each newly resampled $z$ is a whole new sequence, we can consider the smooth average of infinitely fast switching separately for each element.</p>
</section>
<section>
<h2>Different state spaces and step types</h2>
<p>The beauty of the GM framework is that this "smooth average" works for <em>any</em> kind of stochastic process—not just deterministic drift-only flows.
Using the $z$-resampling process as a guide, we can reason about what kind of object the average will be. Consider a number of steps (each switching to a new $z$) and ask: what is their cumulative effect <strong>in distribution</strong>? i.e. if we were to replace $n$ steps with a single step (but where the single step is aware of the sequence of $z$ values that was stepped through), what would the distribution of the state be at the end of the single step?</p>
<p>You can represent any useful kind of "step" as some combination of drift (continuous deterministic changes), diffusion (continuous stochastic changes), and jumps (discontinuous changes). Here are four common examples, showing exactly what gets averaged in each.</p>
<h3>Case I: Deterministic flow (pure drift)</h3>
<div class="interactive-figure">
<h4 style="margin-top:0;">Cumulative effect: Drift-only.</h4>
<img src="assets/ex1_flow.svg" alt="Drift-only flow matching case"/>
<div class="caption">
<strong>Top (blue):</strong> Four steps of the $z$-resampling process for the pure-drift case.
<br>
<strong>Bottom (red):</strong> The cumulative effect of the four steps, which is just the sum of the vectors from the top.
</div>
</div>
<p>This is the flow matching case we've been using in the examples. The dynamics are deterministic with a velocity field $u_t(\cdot \mid z)$:</p>
<p style="text-align:center;">$$ x_{t+\Delta t} = x_t + u_t(x_t\mid z)\,\Delta t. $$</p>
<p>We average the velocities directly:
$$ \bar{u}_t(x) = \sum_k p(x_1^{z_k}\mid x,t)\,u_t(x\mid z_k). $$
</p>
<p>For straight-line paths where $u_t(x\mid z)=\frac{x_1^z - x}{1-t}$, the averaged velocity points toward a weighted combination of all the training examples.</p>
<h3>Case II: Diffusion (drift + Gaussian noise)</h3>
<div class="interactive-figure">
<h4 style="margin-top:0;">Cumulative effect: Drift and diffusion.</h4>
<img src="assets/ex2_driftdiffusion.svg" alt="Drift+Diffusion case"/>
<div class="caption">
<strong>Top (blue):</strong> Four steps with $z$-resampling for a process with drift and diffusion. Each step has a deterministic component, and draws a sample from a Gaussian distribution.
<br>
<strong>Bottom (red):</strong> The cumulative effect of the four steps, which is the sum of the drift vectors, and a sample from a Gaussian with the sum of the variances of the four Gaussians above.
</div>
</div>
<p>Many processes include stochasticity. Consider a step with both drift and Gaussian noise:
$$ x_{t+\Delta t} = x_t + \mu_t(x_t\mid z)\,\Delta t + \sigma_t(x_t\mid z)\,\sqrt{\Delta t}\,\xi, \quad \xi \sim \mathcal{N}(0,I). $$
</p>
<p>The drift terms average as before. For the noise, what matters is the <em>variance per unit time</em>. If the noise is isotropic, acting upon each element independently with a vector of per-element variances $\sigma_t(x\mid z)$, the averaged quantities are:
$$ \bar{\mu}_t(x) = \sum_k p(z_k\mid x,t)\,\mu_t(x\mid z_k), \qquad \bar{\sigma}^2_t(x) = \sum_k p(z_k\mid x,t)\,\sigma^2_t(x\mid z). $$
</p>
<p><strong>Important:</strong> We average <em>variances</em> (not eg. standard deviations). This is because when you rapidly switch between noise levels, you accumulate the sum of the independant per-step Gaussian draws, and <a href="https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables">the sum of independent Gaussian variates is a Gaussian with their summed variance</a>.</p>
<h3>Case III: Discrete states</h3>
<div class="interactive-figure">
<h4 style="margin-top:0;">Cumulative effect: Discrete states.</h4>
<img src="assets/ex3_CTMC.svg" alt="Discrete state case"/>
<div class="caption">
<strong>Top (blue):</strong> Four steps with $z$-resampling for a discrete process. The depicted displacements are the probability of switching from the current state to another state in each step (in this example, the state does not change).
<br>
<strong>Bottom (red):</strong> The cumulative effect of the four steps, which is the sum of the switching probabilities.
</div>
</div>
<p>For discrete state spaces (like text tokens), the fundamental object is the transition <em>rate</em> $q_t(j\mid i, z)$: the probability per unit time of jumping from state $i$ to state $j$.</p>
<p>Over a small $\Delta t$:
$$ \Prob(x_{t+\Delta t} = j \mid x_t = i) \approx q_t(j\mid i, z)\,\Delta t \quad \text{for } j \neq i. $$
</p>
<p>We average the rates:
$$ \bar{q}_t(j\mid i) = \sum_k p(z_k\mid x_t=i,t)\,q_t(j\mid i, z_k). $$
</p>
<h3>Case IV: Jump processes in continuous space</h3>
<div class="interactive-figure">
<h4 style="margin-top:0;">Cumulative effect: Jump process.</h4>
<img src="assets/ex4_jumps.svg" alt="Jump process case"/>
<div class="caption">
<strong>Top (blue):</strong> Four steps of a $z$-resampling process with jumps. In this example, if a jump occurs in a single step, the target distribution is a nearby Gaussian (depicted). In this example, no jumps occur and the state is unchanged.
<br>
<strong>Bottom (red):</strong> The cumulative effect of the four steps, which is a <em>mixture</em> of the four Gaussian distributions.
</div>
</div>
<p>Some processes involve discontinuous jumps in continuous space. Each conditional model specifies a jump <em>intensity</em> $\lambda_t(x\mid z)$ (how often jumps occur) and a <em>destination distribution</em> $r_t(y\mid x,z)$ (where you land if you jump).</p>
<p>Averaging gives:
$$ \bar{\lambda}_t(x) = \sum_k p(z_k\mid x,t)\,\lambda_t(x\mid z_k), $$
and, given that a jump occurs, the destination is a mixture:
$$ \bar{r}_t(y\mid x) = \frac{\sum_k p(z_k\mid x,t)\,\lambda_t(x\mid z_k)\, r_t(y\mid x, z_k)}{\bar{\lambda}_t(x)}. $$
</p>
<p>The mixture weights depend on both the posterior $p(z_k\mid x,t)$ and the jump intensity—processes that jump more frequently contribute more to where you land.</p>
<h3>Closure</h3>
<p>In the first three cases (drift only, drift + diffusion, and discrete CTMC), the cumulative effect of multiple steps is the same kind of object as each of the component steps. In the jump example, however, even though the individual jumps (each conditioned on a different $z$) are Gaussian, the cumulative effect is a <em>mixture</em> of the individual jump destinations.</p>
<p>Given that the whole point of GM is to train a model to predict the posterior-averaged step, this makes the jump case particularly challenging as it requires the model to learn to predict mixtures of the jump distribution, which can be difficult to impossible to appropriately parameterize if they need to be arbitrarily flexible. In practice, jump distributions that result in trivial mixtures can be chosen, such as grids where the distribution within each grid cell is uniform, and the model can learn to output a discrete distribution over the grid cells. This enforces a closure between a conditional step for a single $z$ and the posterior-averaged step marginalizing over many $z$ values.</p>
<p>In practice, almost all generative models that fall into the GM framework have been:</p>
<ul>
<li>Continuous states, with drift-only (eg. deterministic flow matching);</li>
<li>Continuous states, with drift + diffusion, but where <em>only the drift component is learnable</em>, and the diffusion component is fixed according to some schedule, and not data dependent (eg. diffusion models or SDE flow matching);</li>
<li>Discrete state & process (i.e. a jump process, but where the jumps are to a fixed set of states);</li>
<li>Some multimodal combination of the above.</li>
</ul>
</section>
<section>
<h2>Sampling from a trained model</h2>
<p>Once we've trained a model $f_\theta(t, x)$ to predict the posterior-averaged step, generating new samples is straightforward:</p>
<ol>
<li>Sample $x_0$ from the prior $p(x_0)$.</li>
<li>Starting from $t=0$, repeatedly apply $x_{t+\Delta t} = x_t + f_\theta(t, x_t)\,\Delta t$ (or the appropriate update rule for your process type).</li>
<li>Continue until $t=1$. The result $x_1$ is a sample from (approximately) the target distribution.</li>
</ol>
<p>That's it! No need to sample or track $z$ during generation. The posterior averaging is "baked into" the learned model.</p>
<p>The core idea is simply: follow the learned averaged step from the prior to the target. In practice, the choice of step size affects both quality and speed. </p>
</section>
<section>
<h2>The complete GM recipe</h2>
<p>Let's put everything together. Here's the full Generator Matching framework in plain terms:</p>
<h3>Design phase</h3>
<ol>
<li><strong>Choose a prior:</strong> Pick an easy-to-sample distribution $p(x_0)$ (e.g., Gaussian noise for images, uniform over tokens for text).</li>
<li><strong>Design a conditional process:</strong> Specify how to step $x_{t+\Delta t}$ from $(x_t, z, t)$ such that by $t=1$, the path reaches the data point controlled by $z$. This can involve drift, diffusion, jumps, or any combination.</li>
</ol>
<h3>Training phase</h3>
<ol>
<li>Sample training examples $z$ from your dataset.</li>
<li>Sample times $t$ and generate corresponding $x_t$ from the conditional process.</li>
<li>Train a neural network to predict the conditional step $u_t(x_t \mid z)$ from $(t, x_t)$.</li>
<li>Minimizing the appropriate Bregman divergence automatically gives you the posterior-averaged step.</li>
</ol>
<h3>Sampling phase</h3>
<ol>
<li>Draw $x_0$ from the prior.</li>
<li>Integrate the learned step rule forward from $t=0$ to $t=1$.</li>
<li>The endpoint $x_1$ is your generated sample.</li>
</ol>
<h3>Why this works</h3>
<ul>
<li><strong>Marginals match by construction:</strong> The conditional paths mix to give $p(x_t\mid t)$, and we proved that the resample-$z$ process preserves these marginals.</li>
<li><strong>Infinite resampling = averaging:</strong> Taking the resampling rate to infinity gives a deterministic process that uses the posterior-averaged step.</li>
<li><strong>Regression learns the average:</strong> Training on joint samples $(x_t, z)$ with the right loss automatically computes the posterior expectation—no explicit posterior computation needed.</li>
</ul>
</section>
<section>
<h3>Linear parameterizations of conditional steps</h3>
<p>We're using a neural network to parameterize the step. The network will predict some number(s), and our step will be a function of those. Going back to our running pure-drift flow matching example, we could have:
<ul>
<li>the network aim to predict the posterior mean velocity vector $\hat{u}_t(x_t)$ directly, in which case our step is $x_{t+\Delta t} = x_t + \hat{u}_t(x_t)\,\Delta t$;</li>
<li>the network predict the posterior average $\hat{x}_1$, in which case we can take the step as $x_{t+\Delta t} = x_t + \frac{\hat{x}_1-x_t}{1-t}\,\Delta t$;</li>
</ul>
<p>The first version is clearly in line with the description of GM above, and a Bregman divergence loss will be minimized at the posterior mean. But why does the second parameterization, which we call $x$-prediction (or sometimes $x_1$-prediction) work? Because (weighted) arithmetic averages are equivariant under scale and shift transformations. So since $\hat{u}_t = \frac{\hat{x}_1-x_t}{1-t}$, using a Bregman divergence to learn the posterior average $\hat{x}_1$ will also learn the posterior mean velocity vector $\hat{u}_t$.</p>
<p>It is important to understand where this will fail. One example is on manifolds, which we haven't discussed yet, but all of the above tricks apply to manifolds as well. If you have a conditional process that keeps the state on the manifold but that terminates at a training sample point, and you use samples from this conditional process to learn the posterior average step, then your model will sample from the data distribution. The analogous example to simple flow matching is where the conditional process follows the geodesic between $x_0$ and $x_1$. This works when you minimize the squared error of the model's prediction of the velocity vector $\hat{u}_t(x_t)$ (which is tangent to the manifold), but in general this fails when you minimize the squared error of the model's prediction of the terminal point $\hat{x}_1$ (even if you have a manifold-respecting average). Why? Because with the non-linear manifold geometry, $x_1$ and $\hat{u}_t(x_t)$ are no longer related by an affine transformation!</p>
<p>But in some cases we <em>really</em> want to use $x$-prediction (eg. for protein models, which update positions and orientations through the layer stack). Fortunately, the issue isn't in what the model outputs, but in what the loss is taken against. On manifolds, the version of $x$-prediction that works is if you have the model predict $x_1$ on the manifold, then take the logarithmic map to pull $x_1$ up into the tangent space at $x_t$, and then minimize the squared error against the true $x_1$ in the tangent space. The downside of this option is that, unlike directly predicting the velocity, you now need a GPU-friendly differentiable logarithmic map, since this is sandwiched between the model's prediction and the loss, and so the gradients must flow through it.</p>
<p>The discrete case is also instructive here. Take a simple unconditional CTMC, non-absorbing, with uniform rates between all characters. If condition this process to terminate at $x_1$, the conditional outgoing probability velocities for $x_t$ at $t$ can be obtained via the Doob $h$-transform, and if you train a model, with a Bregman divergence, against these probability velocities, you get a working discrete flow matching model. However the Doob $h$-transform is not generally affine, and so e.g. predicting $x_1$ with a cross-entropy loss will fail.</p>
<p>Much of the discrete diffusion literature circumvents this by restricting themselves to processes that start in a masked state, and unmasks directly to the $x_1$ state, and <a href="https://arxiv.org/abs/2407.15595">Discrete Flow Matching</a> constrains the space of discrete processes to 'convex interpolants'. In both cases, $x_1$-prediction with cross-entropy loss is valid because an infintesimal step of the conditional process can be written as:
$$\Prob(x_{t+\Delta t} = j \mid x_t = i) \approx q_t(j\mid i, z)\,\Delta t \quad (j \neq i)$$
</p>
</section>
<section>
<h3>Efficient sampling from the conditional process, for efficient training.</h3>
<p>As described, when the conditional process is constructed via a sequence of tiny steps, it is clear how to sample from $p(x_{t+\Delta t} \mid x_t, z, t)$ for each step, and this is all that is needed to understand the principles of GM. But this is often not efficient. Given that this happens within the training loop, the sampling from the conditional process should be efficient enough to never keep the GPU waiting.</p>
<p>However there are large classes of conditional processes where $p(x_t \mid z, t)$ can be obtained in closed form, and is easy to sample from. For example the drift-only process we've been using as a working example is trivial, because it just charts a straight line between $x_0$ and $x_1$. Brownian Bridges are the drift/diffusion analog of this, where you wind up with a straight line with some variance. In general, where possible it is usually a good idea to choose a conditional process where the conditional path can be sampled from directly without stepping through all the intermediates.</p>
</section>
<section>
<h3>To do:</h3>
<ol>
<li>Multimodal, and multidimensional states.</li>
<li>Perfect learning will recover the training data only. Only succeeds where it fails.</li>
<li>Loss scaling</li>
<li>Manifolds</li>
<li>Aux losses</li>
<li>Doing more with $z$.</li>
<li>"zGM without generators"</li>
</ol>
</section>
<!-- LOGIC -->
<script>
// =========================================
// UTILS & MATH
// =========================================
// Prior Distribution Parameters (Centered on Canvas)
const PRIOR_CENTER_1 = { x: 300, y: 225 }; // Center of canvas approx
const PRIOR_SIGMA_1 = 80;
const PRIOR_CENTER_2 = { x: 120, y: 200 }; // Center of canvas approx
const PRIOR_SIGMA_2 = 40;
function distSq(p1, p2) {
return (p1.x - p2.x)**2 + (p1.y - p2.y)**2;
}
// Gaussian PDF unnormalized
function gaussianPdf(x, y, center, sigma) {
const d2 = (x - center.x)**2 + (y - center.y)**2;
return Math.exp(-d2 / (2 * sigma * sigma));
}
// We ignore the constant factor -log(sqrt(2pi)*sigma) because it cancels out
function gaussianLogPdf(x, y, center, sigma) {
const dx = x - center.x;
const dy = y - center.y;
// log(exp(-d^2 / 2s^2)) = -d^2 / 2s^2
return -(dx*dx + dy*dy) / (2 * sigma * sigma);
}
// Replacement 2: Robust Posterior Weights using Log-Sum-Exp
function getPosteriorWeights(x, targets, t, center, sigma) {
// We can get extremely close to 1.0 now without NaN
const t_safe = Math.min(t, 0.9999);
const one_minus_t = 1 - t_safe;
let logWeights = [];
let maxLogW = -Infinity;
// 1. Compute Log Weights (Project back to t=0)
for (let z of targets) {
const x0_x = (x.x - t_safe * z.x) / one_minus_t;
const x0_y = (x.y - t_safe * z.y) / one_minus_t;
const lw = gaussianLogPdf(x0_x, x0_y, center, sigma);
logWeights.push(lw);
// Track max for stability
if (lw > maxLogW) maxLogW = lw;
}
// 2. Log-Sum-Exp Trick
// We subtract maxLogW from exponents to prevent underflow to 0
// at least one term will be exp(0) = 1
let sumExp = 0;
let expWeights = [];
for (let lw of logWeights) {
const w = Math.exp(lw - maxLogW);
expWeights.push(w);
sumExp += w;
}
// 3. Normalize
return expWeights.map(w => w / sumExp);
}
// =========================================
// New 1D posterior helpers (for Viz 1 & Viz 3 only)
// Keep Viz 2's 2D helpers unchanged
// =========================================
function gaussianLogPdf1D(y, mean, sigma) {
const dy = y - mean;
return -(dy * dy) / (2 * sigma * sigma);
}
// y: current state (pixel y), targetsY: array of data states (pixel y)
// t in [0,1), prior specified by (meanY, sigmaY)
function getPosteriorWeights1D(y, targetsY, t, meanY, sigmaY) {
const t_safe = Math.min(Math.max(t, 0), 0.9999);
const one_minus_t = 1 - t_safe;
let logWeights = [];
let maxLogW = -Infinity;
for (let zy of targetsY) {
const y0 = (y - t_safe * zy) / one_minus_t;
const lw = gaussianLogPdf1D(y0, meanY, sigmaY);
logWeights.push(lw);
if (lw > maxLogW) maxLogW = lw;
}
let sumExp = 0;
const expW = [];
for (let lw of logWeights) {
const w = Math.exp(lw - maxLogW);
expW.push(w);
sumExp += w;
}
return expW.map(w => w / sumExp);
}
// Draw a vertical Gaussian "hump" along the left edge (x from 0 toward right),
// hinting that mass "comes from the left" of the y-axis.
function drawVerticalGaussianHump(ctx, height, meanY, sigmaY, maxWidth, color) {
ctx.save();
ctx.fillStyle = color;
ctx.globalAlpha = 0.15;
ctx.beginPath();
ctx.moveTo(0, 0);
for (let y = 0; y <= height; y += 2) {
const pdf = Math.exp(-((y - meanY) * (y - meanY)) / (2 * sigmaY * sigmaY));
const x = Math.min(maxWidth, maxWidth * pdf);
ctx.lineTo(x, y);
}
ctx.lineTo(0, height);
ctx.closePath();
ctx.fill();
ctx.restore();
}
function drawArrow(ctx, fromX, fromY, toX, toY, color) {
const headlen = 10;
const dx = toX - fromX;
const dy = toY - fromY;
const angle = Math.atan2(dy, dx);
ctx.strokeStyle = color;
ctx.fillStyle = color;
ctx.lineWidth = 3;
ctx.beginPath();
ctx.moveTo(fromX, fromY);
ctx.lineTo(toX, toY);
ctx.stroke();
ctx.beginPath();
ctx.moveTo(toX, toY);
ctx.lineTo(toX - headlen * Math.cos(angle - Math.PI / 6), toY - headlen * Math.sin(angle - Math.PI / 6));
ctx.lineTo(toX - headlen * Math.cos(angle + Math.PI / 6), toY - headlen * Math.sin(angle + Math.PI / 6));
ctx.fill();
}
// Styled thin arrow (for faint hero arrow in Viz 2)
function drawArrowStyled(ctx, fromX, fromY, toX, toY, color, lineWidth, alpha) {
const headlen = 8;
const dx = toX - fromX;
const dy = toY - fromY;
const angle = Math.atan2(dy, dx);
ctx.save();
ctx.globalAlpha = alpha;
ctx.strokeStyle = color;
ctx.fillStyle = color;
ctx.lineWidth = lineWidth;
ctx.beginPath();
ctx.moveTo(fromX, fromY);
ctx.lineTo(toX, toY);
ctx.stroke();
ctx.beginPath();
ctx.moveTo(toX, toY);
ctx.lineTo(toX - headlen * Math.cos(angle - Math.PI / 6), toY - headlen * Math.sin(angle - Math.PI / 6));
ctx.lineTo(toX - headlen * Math.cos(angle + Math.PI / 6), toY - headlen * Math.sin(angle + Math.PI / 6));
ctx.fill();
ctx.restore();
}
// =========================================
// AUDIO: Soft click on direction switch (Viz 2)
// =========================================
let audioCtx = null;
function playClick() {
try {
if (!audioCtx) {
audioCtx = new (window.AudioContext || window.webkitAudioContext)();
}
if (audioCtx.state === 'suspended') {
audioCtx.resume();
}
} catch (e) {
return;
}
const t0 = audioCtx.currentTime;
// Short, soft sine "tick"
const osc = audioCtx.createOscillator();
const gain = audioCtx.createGain();
const filter = audioCtx.createBiquadFilter();
filter.type = 'lowpass';
filter.frequency.setValueAtTime(2000, t0);
osc.type = 'sine';
osc.frequency.setValueAtTime(1000, t0);
// gentle envelope
gain.gain.setValueAtTime(0.0001, t0);
gain.gain.exponentialRampToValueAtTime(0.04, t0 + 0.01);
gain.gain.exponentialRampToValueAtTime(0.0001, t0 + 0.08);
osc.connect(filter).connect(gain).connect(audioCtx.destination);
osc.start(t0);
osc.stop(t0 + 0.09);
}
// =========================================
// VIZ 1: POSTERIOR FIELD
// =========================================
const cvs1 = document.getElementById('posteriorCanvas');
const ctx1 = cvs1.getContext('2d');
const inputN = document.getElementById('inputN');
const btnResampleData = document.getElementById('btnResampleData');
let v1 = {
stateY: 100,
t: 0.5,
targetsY: [],
animId: null,
showArrow: false
};
function initV1Data() {
const n = parseInt(inputN.value) || 4;
v1.targetsY = [];
for (let i = 0; i < n; i++) {
let y = (Math.random()+Math.random()+Math.random())/3 * 200 - 100;
if (Math.random() < 0.3) {
v1.targetsY.push(y + 125);
} else {
v1.targetsY.push(y + 325);
}
}
}
// Inputs
cvs1.addEventListener('mousemove', e => {
const r = cvs1.getBoundingClientRect();
v1.t = Math.min(Math.max((e.clientX - r.left) / cvs1.width, 0), 1);
v1.stateY = e.clientY - r.top;
});
cvs1.addEventListener('touchmove', e => {
e.preventDefault();
const r = cvs1.getBoundingClientRect();
v1.t = Math.min(Math.max((e.touches[0].clientX - r.left) / cvs1.width, 0), 1);
v1.stateY = e.touches[0].clientY - r.top;
}, {passive:false});
btnResampleData.addEventListener('click', initV1Data);
function loopV1() {
drawV1();
requestAnimationFrame(loopV1);
}
function drawV1() {
ctx1.clearRect(0, 0, cvs1.width, cvs1.height);
// Axes: x-axis is time [0,1], y-axis is 1D state
// Draw a vertical Gaussian hump at x ~ 0 indicating prior over X0
const priorMeanY = PRIOR_CENTER_1.y;
const priorSigmaY = PRIOR_SIGMA_1;
drawVerticalGaussianHump(ctx1, cvs1.height, priorMeanY, priorSigmaY, 60, '#888');
ctx1.fillStyle = "#777";
ctx1.fillText("Prior (t=0)", 2, 20);
ctx1.fillText("Data (t=1)", cvs1.width - 50, 20);
// Current time position on x-axis
const tPosX = v1.t * cvs1.width;
// Compute 1D posterior weights
const weights = getPosteriorWeights1D(v1.stateY, v1.targetsY, v1.t, priorMeanY, priorSigmaY);
// Draw blue worldlines: (x=1,z) -> (t,v1.stateY) -> (x=0,x0)
const t_safe = Math.min(v1.t, 0.9999);
const one_minus_t = 1 - t_safe;
v1.targetsY.forEach((zy, i) => {
const w = weights[i];
if (w <= 0.001) return;
const y0 = (v1.stateY - t_safe * zy) / one_minus_t;
ctx1.beginPath();
ctx1.moveTo(cvs1.width - 6, zy);
ctx1.lineTo(tPosX, v1.stateY);
ctx1.lineTo(6, y0);
ctx1.strokeStyle = `rgba(0, 0, 255, ${w})`;
ctx1.lineWidth = w * 4 + 1;
ctx1.stroke();
});
// Draw data points at t=1 (right edge)
v1.targetsY.forEach((zy) => {
ctx1.beginPath();
ctx1.arc(cvs1.width - 6, zy, 5, 0, Math.PI * 2);
// 50% opacity
ctx1.fillStyle = 'rgba(0, 0, 255, 0.5)';
ctx1.fill();
});
// Draw the green cursor at (t, stateY)
ctx1.beginPath();
ctx1.arc(tPosX, v1.stateY, 8, 0, Math.PI*2);
ctx1.fillStyle = 'green';
ctx1.fill();
// t overlay near the green dot
ctx1.save();
ctx1.fillStyle = '#333';
ctx1.font = '12px -apple-system, system-ui, Segoe UI, Roboto, Helvetica, Arial, sans-serif';
const tx1 = cvs1.width/2;
const ty1 = 20;
ctx1.fillText(`t=${v1.t.toFixed(2)}`, tx1, ty1);
ctx1.restore();
}
initV1Data();
loopV1();
// =========================================
// VIZ 2: SIMULATION
// =========================================
const cvs2 = document.getElementById('simCanvas');
const ctx2 = cvs2.getContext('2d');
const btnResetSim = document.getElementById('btnResetSim');
const btnRandomizeSim = document.getElementById('btnRandomizeSim');
const btnToggleMode = document.getElementById('btnToggleMode');
const btnAutoPlay = document.getElementById('btnAutoPlay');
const resampleControls = document.getElementById('resampleControls');
const stepSizeSlider = document.getElementById('stepSizeSlider');
const stepDisplay = document.getElementById('stepDisplay');
//const simCaption = document.getElementById('simCaption');
const dt = 1 / 1000; // Slow time step
const AUTO_STAGES = [
{ mode: 'resample', interval: 1000 },
{ mode: 'resample', interval: 100 },
{ mode: 'resample', interval: 10 },
{ mode: 'resample', interval: 1 },
{ mode: 'average' }
];
// Fixed Targets for Sim
//const simTargets = [
// { x: 750, y: 100 }, { x: 780, y: 120 }, { x: 740, y: 130 },
// { x: 750, y: 280 }, { x: 780, y: 260 }, { x: 730, y: 290 }
//];
//Sample these randomly from two gaussians which are ventered on the previously hardcoded points.
simTargets = [];
for (let i = 0; i < 40; i++) {
x = (Math.random()+Math.random()+Math.random())/3 * 50 + 720;
y = (Math.random()+Math.random()+Math.random())/3 * 120 + 60;
if (Math.random() < 0.3) {
y += 150;
}
simTargets.push({ x, y});
}
let sim = {
mode: 'resample',
running: false,
t: 0,
particles: [],
initialSeeds: null,
resampleInterval: 100,
animId: null,
autoPlayActive: false,
autoStageIndex: 0
};
function startSimFromSeeds() {
sim.running = false;
sim.t = 0;
sim.particles = [];
if (!sim.initialSeeds || sim.initialSeeds.length === 0) {
// Safety: if seeds missing, randomize then proceed
randomizeInitialSeeds(80);
}
// Instantiate particles from seeds
for (let i = 0; i < sim.initialSeeds.length; i++) {
const seed = sim.initialSeeds[i];
sim.particles.push({
id: i,
x: seed.x,
y: seed.y,
history: [],
currentZ: null,
timer: 0
});
}
// Restart Loop
if(sim.animId) cancelAnimationFrame(sim.animId);
sim.running = true;
simLoop();
}
function buildParticlesFromSeeds() {
sim.t = 0;
sim.particles = [];
if (!sim.initialSeeds || sim.initialSeeds.length === 0) {
randomizeInitialSeeds(80);
}
for (let i = 0; i < sim.initialSeeds.length; i++) {
const seed = sim.initialSeeds[i];
sim.particles.push({
id: i,
x: seed.x,
y: seed.y,
history: [],
currentZ: null,
timer: 0
});
}
}
function randomizeInitialSeeds(n = 80) {
sim.initialSeeds = [];
for(let i=0; i<n; i++) {
// Sample from Prior (approx) using Box-Muller
const u = 1 - Math.random();
const v = Math.random();
const z_gauss = Math.sqrt( -2.0 * Math.log( u ) ) * Math.cos( 2.0 * Math.PI * v );
const u2 = 1 - Math.random();
const v2 = Math.random();
const z_gauss2 = Math.sqrt( -2.0 * Math.log( u2 ) ) * Math.cos( 2.0 * Math.PI * v2 );
sim.initialSeeds.push({
x: PRIOR_CENTER_2.x + z_gauss * PRIOR_SIGMA_2,
y: PRIOR_CENTER_2.y + z_gauss2 * PRIOR_SIGMA_2
});
}
}
function randomizeAndStartSim() {
randomizeInitialSeeds(80);
startSimFromSeeds();
}
function setSimMode(mode, interval) {
if (mode === 'resample') {
sim.mode = 'resample';
// Must display interval in the button text
btnToggleMode.textContent = "Mode: Resampling";
if (interval === 1000) {
btnToggleMode.textContent = "Mode: Conditional Proces";
} else if (interval === 100) {
btnToggleMode.textContent = "Mode: Resampling (interval: 0.1)";
} else if (interval === 10) {
btnToggleMode.textContent = "Mode: Resampling (interval: 0.01)";
} else if (interval === 1) {
btnToggleMode.textContent = "Mode: Resampling (interval: 0.001)";
}