Neural Dual Bounds: Valid-by-Construction JGLP Warm-Starts for MAP and Constrained MAP
Organizations: Department of Computer Science, The University of Texas at Dallas · Department of Computer Science, New Jersey Institute of Technology
Abstract
We present Neural Dual Bounds, a calibration-free framework that produces deterministic upper bounds for MAP inference in probabilistic graphical models using a single neural-network forward pass. The framework trains a network to output the edge messages of a mini-bucket style upper bound on a given join-graph decomposition in a self-supervised manner by directly minimizing a smooth dual objective. The output of this network can be used at test time to warm-start a standard JGLP optimizer. Across diverse benchmarks, this warm start yields dual gaps that are orders of magnitude tighter than those from zero initialization, with the largest gains in the early-iteration regime. We also apply our framework for the constrained MAP (CMPE) task, where neural warm starts with test-time adaptation are comparable to the adaptive baseline on Bayesian networks and achieve the tightest dual gaps, by one to two orders of magnitude, on the grid and segmentation families.
Figures & tables
| iter=10 | iter=50 | iter=100 | ||||
|---|---|---|---|---|---|---|
| PGM | J | N | J | N | J | N |
| BN_12 | 0.525 0.248 | 0.304 0.178 | 0.150 0.131 | 0.095 0.093 | 0.065 0.078 | 0.042 0.056 |
| BN_13 | 0.469 0.129 | 0.267 0.103 | 0.113 0.071 | 0.089 0.070 | 0.055 0.050 | 0.047 0.048 |
| BN_14 | 0.305 0.142 | 0.191 0.113 | 0.058 0.060 | 0.045 0.051 | 0.015 0.028 | 0.013 0.024 |
| BN_9 | 0.047 0.061 | 0.039 0.055 | 2.96e-03 9.89e-03 | 3.09e-03 0.011 | 6.27e-04 2.63e-03 | 6.97e-04 3.07e-03 |
| Grids_26 | 2.70 2.11 | 2.71 2.10 | 0.237 0.500 | 0.237 0.500 | 0.036 0.159 | 0.037 0.160 |
| iter=10 | iter=50 | iter=100 | ||||
|---|---|---|---|---|---|---|
| PGM | JGLP | NN | JGLP | NN | JGLP | NN |
| BN_12 | 0.622 0.152 | 0.523 0.136 | 0.207 0.068 | 0.164 0.065 | 0.107 0.052 | 0.087 0.047 |
| BN_13 | 0.461 0.127 | 0.351 0.123 | 0.121 0.109 | 0.063 0.051 | 0.055 0.107 | 0.025 0.028 |
| BN_14 | 0.305 0.126 | 0.240 0.121 | 0.050 0.082 | 0.024 0.033 | 0.020 0.076 | 6.60e-03 0.014 |
| BN_9 | 0.179 0.090 | 0.167 0.074 | 0.053 0.062 | 0.027 0.035 | 0.026 0.055 | 9.18e-03 0.019 |
| Grids_26 | 36.07 52.99 | 37.03 52.82 | 4.42 11.52 | 4.43 11.51 | 0.664 2.63 | 0.663 2.63 |
| iter=10 | iter=50 | iter=100 | ||||
|---|---|---|---|---|---|---|
| PGM | JGLP+WS | NN+TTA | JGLP+WS | NN+TTA | JGLP+WS | NN+TTA |
| BN_12 | 0.082 0.095 | 0.097 0.126 | 0.030 0.038 | 0.046 0.054 | 0.019 0.026 | 0.029 0.034 |
| BN_13 | 0.065 0.096 | 0.044 0.082 | 0.015 0.030 | 0.014 0.027 | 7.20e-03 0.015 | 6.93e-03 0.015 |
| BN_14 | 0.072 0.110 | 0.027 0.071 | 7.09e-03 0.022 | 4.80e-03 0.018 | 1.76e-03 9.29e-03 | 1.61e-03 8.25e-03 |
| BN_9 | 0.028 0.046 | 0.021 0.046 | 2.47e-03 7.30e-03 | 4.63e-03 0.016 | 5.32e-04 2.85e-03 | 1.72e-03 8.12e-03 |
| Grids_26 | 428.95 370.99 | 16.02 34.12 | 13.75 13.29 | 2.13 7.35 | 1.30 2.84 | 0.337 1.86 |
Appendix figures & tables41 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Dimension | Meaning |
|---|---|---|
| — | clusters and edges of the join graph | |
| — | separator of edge | |
| log-potential table of cluster | ||
| all cluster tables concatenated into one vector | ||
| scalar | , total number of cluster-table entries | |
| directed edge message, constrained by |
| original | reparameterized | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| max | max | ||||||||
| 2 | 5 | 5 | 7 | ||||||
| 1 | 7 | 7 | 4 | 9 | 9 | ||||
| max | max | ||||||||
| 8 | 1 | 8 | 7 | 1 | |||||
| 4 | 6 | 4 | 7 | 7 | |||||
| iter=0 | iter=10 | iter=50 | iter=100 | conv | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PGM | J | N | J | N | J | N | J | N | J | N | win@10 | |
| BN_12 | -0.02 | -0.17 | -0.22 | -0.48 | -0.74 | -1.05 | -1.65 | -2.04 | -6.79 | -6.77 | 100% | |
| BN_13 | -0.04 | -0.19 | -0.29 | -0.60 | -0.97 | -1.15 | -1.34 | -1.55 | -7.17 | -6.98 | 100% | |
| BN_14 | -0.34 | -0.39 | -0.66 | -0.83 | -1.23 | -1.33 | -4.22 | -4.52 | -6.49 | -6.42 | 100% | |
| Seg_12 | 0.21 | -0.05 | -0.01 | -1.01 | -4.13 | -4.94 | -7.10 | -6.69 | -7.10 | -6.69 | 100% | |
| Seg_14 | 0.18 | -0.42 | -0.73 | -2.00 | -6.34 | -4.62 | -6.34 | -6.13 | -6.34 | -6.19 | 100% | |
| PGM | MBE | JGLP | CMPE LR | Improvement |
|---|---|---|---|---|
| BN_12 (90v) | ||||
| BN_9 (105v) | ||||
| BN_14 (115v) | ||||
| Seg_12 | ||||
| Seg_14 | ||||
| grid10 10 |
| PGM | Our LR | CMPE_UB (JG) | Our time | UB time |
|---|---|---|---|---|
| BN_12 | 48.8s | 112.6s | ||
| BN_9 | 30.1s | 54.7s | ||
| BN_14 | 41.7s | 88.4s |
| PGM | Bin | % Better | |
|---|---|---|---|
| BN_12 | 0 | 2,130 | 94% |
| 1 | 1,076 | 84% | |
| 2 | 298 | 0% | |
| BN_9 | 0 | 1,354 | 80% |
| 1 | 828 | 72% | |
| 2 | 220 | 0% |
| PGM | MBE | JGLP-200 | Grad-200 | N+Grad | CMPE LR |
|---|---|---|---|---|---|
| BN_12 | |||||
| BN_9 | |||||
| BN_14 |
| PGM | MBE | JGLP | Neural | CMPE LR | CMPE_UB |
|---|---|---|---|---|---|
| BN_12 | 41.30 | 40.60 | 40.71 | 6.64 | 29.70 |
| BN_9 | 46.84 | 46.54 | 46.62 | 6.96 | 32.80 |
| BN_14 | 52.72 | 52.23 | 52.35 | 8.02 | 34.89 |
| JGLP | NN | |||||
|---|---|---|---|---|---|---|
| PGM | time | time | Speedup | |||
| BN_12 | 22.8s | 1.8s | 12.9 | |||
| BN_9 | 17.3s | 1.5s | 11.5 | |||
| BN_14 | 21.7s | 1.7s | 12.6 | |||
| Seg_12 | 31.2s | 4.1s | 7.7 | |||
| Seg_14 | 37.3s | 4.3s | 8.8 | |||
| JGLP | NN | |||||
|---|---|---|---|---|---|---|
| PGM | time | time | Speedup | |||
| BN_12 | 22.7s | 1.9s | 11.9 | |||
| BN_9 | 17.3s | 1.5s | 11.6 | |||
| BN_14 | 21.9s | 1.8s | 12.4 | |||
| Seg_12 | 31.7s | 4.1s | 7.7 | |||
| Seg_14 | 37.1s | 4.2s | 8.8 | |||
| M1 | median iters | paired win% | censored (%) | break-even (queries) | ||||||
| PGM | iters | M2 | M3 | M2 | M3 | M1 | M3 | M2 | M3 | |
| BN_12 | 120 | 201 | 206 | 136 | 66 | 31 | 60 | 43 | 15,278 | |
| BN_13 | 120 | 69 | 69 | 18 | 66 | 1 | 2 | 2 | 26,968 | |
| BN_14 | 120 | 109 | 41 | 50 | 98 | 43 | 1 | 0 | 3,215 | |
| BN_9 | 120 | 49 | 26 | 8 | 58 | 0 | 0 | 0 | 19,805 | |
| Grids_26 | 120 | 52 | 76 | 40 | 0 | 10 | 0 | 0 | ||
| (a) Cost of one TTA step | |||||
|---|---|---|---|---|---|
| PGM | size | ||||
| (ms) | (ms) | (ms) | (ms) | ||
| grid10 10.f5 | small | 0.29 | 63 [29] | 81 [15] | 95 [28] |
| Seg_18 | large | 0.35 | 232 [49] | 267 [52] | 276 [50] |
| PGM | Vars | % Neural Better | Fwd Time | |
|---|---|---|---|---|
| BN_12 | 90 | 2,130 | 94% | 0.26ms |
| BN_9 | 105 | 1,354 | 80% | 0.24ms |
| BN_14 | 68 | 1,812 | 92% | 0.25ms |
| grid10 10 | 100 | 808 | 68% | 0.23ms |
| grid20 20.f5 | 400 | 2,988 | 20% | 0.28ms |
| grid20 20.f10 | 400 | 5,002 | 98% | 0.32ms |
| PGM | % Neural Tighter | Mean | Neural Time |
|---|---|---|---|
| BN_12 | 100% | 0.66 | 0.35ms |
| BN_9 | 85% | 0.18 | 0.37ms |
| BN_14 | 100% | 0.46 | 0.41ms |
| Seg_12 | 100% | 2.24 | 0.47ms |
| Seg_14 | 100% | 1.62 | 0.48ms |
| Seg_18 | 70% | 0.60 | 0.49ms |
| PGM | Category | MBE–JGLP gap | |||
|---|---|---|---|---|---|
| BN_9 | BN | 105 | 1,354 | 3,122 | 0.26 |
| BN_12 | BN | 90 | 2,130 | 4,346 | 0.71 |
| BN_13 † | BN | 125 | 2,130 | 4,574 | 0.56 |
| BN_14 | BN | 115 | 1,812 | 3,974 | 0.78 |
| BN_126 † | BN | 512 | 5,268 | 11,414 | 0.23 |
| Seg_12 | Segmentation | 231 | 3,998 | 8,460 | 0.40 |
| Variant | M1 (zero) | M2 (NN off) | M3 (NN+adapt) | win@10 |
|---|---|---|---|---|
| Loss weight (main is C=1.0 pure MSE): | ||||
| loss C=0.0 (pure ) | -0.60 | -0.73 | -0.93 | 81% |
| loss C=0.5 (combined) | -0.60 | -0.75 | -0.91 | 80% |
| Gradient steps on (main is 100): | ||||
| = 30 | -0.52 | -0.20 | -0.58 | 61% |
| = 200 | -0.62 | -0.21 | -1.49 | 86% |
| PGM | J (iter=0 ) | N | win% | J (iter=10 ) | N | win% | J (iter=50 ) | N | win% | J (iter=100 ) | N | win% | J (iter=500 ) | N | win% |
| BN_12 | 9.66 | 6.79 | 100 | 60.9 | 32.9 | 100 | 1820 | 964 | 90 | 50375 | 20465 | 100 | 1.80 | 1.90 | 100 |
| BN_126 | 2.94 | 5.29 | 0 | 9.33 | 8.69 | 89 | 83.9 | 75.1 | 56 | 2.88 | 2.92 | 67 | 4.96 | 6.05 | 67 |
| BN_13 | 9.08 | 6.54 | 100 | 50.8 | 25.2 | 100 | 1078 | 733 | 100 | 45571 | 33649 | 60 | 0.70 | 1.05 | 80 |
| BN_14 | 4.63 | 4.12 | 90 | 22.0 | 15.0 | 100 | 592 | 478 | 80 | 1241 | 33.0 | 80 | 3.27 | 3.87 | 90 |
| BN_9 | 2.58 | 2.50 | 30 | 12.2 | 2.93 | 70 | 34.8 | 0.02 | 70 | 0.21 | 0.12 | 100 | 2.08 | 1.05 | 100 |
| Grids_18 | 696 | 685 | 90 | 1382 | 1350 | 100 | 22276 | 21575 | 90 | 1121910 | 1094359 | 80 | 92624 | 98491 | 60 |
| iter=10 | iter=50 | iter=100 | iter=500 | |||||
|---|---|---|---|---|---|---|---|---|
| PGM | J | N | J | N | J | N | J | N |
| BN_12 | 0.638 0.238 | 0.373 0.179 | 0.184 0.147 | 0.116 0.105 | 0.0878 0.0971 | 0.0595 0.0723 | 0.00828 0.0170 | 0.00699 0.0145 |
| BN_126 | 0.248 0.342 | 0.239 0.338 | 0.0647 0.147 | 0.0639 0.146 | 0.0150 0.0389 | 0.0149 0.0388 | 1.01e-06 1.16e-06 | 1.08e-06 1.14e-06 |
| BN_13 | 0.474 0.115 | 0.255 0.0878 | 0.116 0.0731 | 0.0884 0.0715 | 0.0584 0.0525 | 0.0503 0.0538 | 0.00197 0.00502 | 0.00263 0.00556 |
| BN_14 | 0.278 0.173 | 0.174 0.128 | 0.0937 0.137 | 0.0420 0.0368 | 0.0546 0.143 | 0.00575 0.00800 | 0.0483 0.145 | 8.25e-06 1.59e-05 |
| BN_9 | 0.162 0.156 | 0.0607 0.0701 | 0.126 0.169 | 0.00680 0.0188 | 0.125 0.170 | 0.00147 0.00442 | 0.125 0.170 | 1.35e-07 6.90e-08 |
| iter=0 | iter=10 | iter=50 | iter=100 | iter=500 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| PGM | J | N | J | N | J | N | J | N | J | N |
| BN_12 | 0.872 0.289 | 0.675 0.222 | 0.525 0.248 | 0.304 0.178 | 0.150 0.131 | 0.095 0.093 | 0.065 0.078 | 0.042 0.056 | 3.27e-03 9.33e-03 | 2.82e-03 8.32e-03 |
| BN_13 | 0.856 0.205 | 0.705 0.174 | 0.469 0.129 | 0.267 0.103 | 0.113 0.071 | 0.089 0.070 | 0.055 0.050 | 0.047 0.048 | 4.97e-03 0.015 | 4.78e-03 0.015 |
| BN_14 | 0.566 0.210 | 0.626 0.198 | 0.305 0.142 | 0.191 0.113 | 0.058 0.060 | 0.045 0.051 | 0.015 0.028 | 0.013 0.024 | 3.18e-04 1.36e-03 | 2.62e-04 1.14e-03 |
| BN_9 | 0.219 0.137 | 0.265 0.124 | 0.047 0.061 | 0.039 0.055 | 2.96e-03 9.89e-03 | 3.09e-03 0.011 | 6.27e-04 2.63e-03 | 6.97e-04 3.07e-03 | 2.09e-06 1.96e-05 | 8.27e-07 6.99e-06 |
| Grids_26 | 14.01 5.51 | 13.48 5.23 | 2.70 2.11 | 2.71 2.10 | 0.237 0.500 | 0.237 0.500 | 0.036 0.159 | 0.037 0.160 | 3.05e-06 2.70e-05 | 3.21e-06 2.82e-05 |
| zero-init | neural-init | ratio | s.e. shrink | ||||
|---|---|---|---|---|---|---|---|
| PGM | |||||||
| BN_12 | 0.525 0.248 | 0.502 0.250 | 0.304 0.178 | 0.294 0.173 | 1.005 | 0.975 | 3.15 |
| BN_13 | 0.469 0.129 | 0.467 0.136 | 0.267 0.103 | 0.261 0.111 | 1.054 | 1.078 | 3.00 |
| BN_14 | 0.305 0.142 | 0.304 0.166 | 0.191 0.113 | 0.188 0.134 | 1.170 | 1.188 | 2.70 |
| Seg_14 | 0.345 0.265 | 0.349 0.254 | 0.123 0.165 | 0.137 0.182 | 0.959 | 1.103 | 3.30 |
| Seg_16 | 1.88 0.514 | 1.83 0.489 | 0.381 0.379 | 0.380 0.386 | 0.951 | 1.019 | 3.32 |
| iter=10 | iter=50 | iter=100 | iter=500 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PGM | M1 | M2 | M3 | M1 | M2 | M3 | M1 | M2 | M3 | M1 | M2 | M3 |
| BN_12 | 0.760 0.301 | 0.635 0.227 | 0.0633 0.144 | 0.256 0.420 | 0.124 0.0978 | 0.0226 0.0456 | 0.200 0.433 | 0.0598 0.0534 | 0.0135 0.0261 | 0.162 0.443 | 0.0135 0.0143 | 0.00377 0.00771 |
| BN_13 | 0.465 0.186 | 0.426 0.175 | 0.0407 0.0988 | 0.108 0.0741 | 0.0990 0.0697 | 0.0108 0.0314 | 0.0206 0.0300 | 0.0188 0.0276 | 0.00386 0.0128 | 0.00101 0.00314 | 0.000953 0.00297 | 0.000323 0.00193 |
| BN_14 | 0.533 0.142 | 0.466 0.137 | 0.0387 0.0991 | 0.145 0.0626 | 0.131 0.0602 | 0.0120 0.0361 | 0.0410 0.0418 | 0.0358 0.0397 | 0.00361 0.0158 | 0.000117 0.00117 | 0.000180 0.00120 | 6.95e-05 0.00114 |
| BN_9 | 0.135 0.0978 | 0.111 0.0986 | 0.0131 0.0388 | 0.0658 0.0684 | 0.0305 0.0490 | 0.00363 0.0154 | 0.0488 0.0644 | 0.0122 0.0262 | 0.00145 0.00748 | 0.0366 0.0659 | 0.000115 0.000370 | 1.24e-05 0.000213 |
| Grids_26 | 15.6 23.8 | 15.6 23.8 | 4.76 14.1 | 1.36 4.08 | 1.36 4.08 | 0.533 2.51 | 0.0554 0.172 | 0.0554 0.172 | 0.00901 0.0606 | 8.08e-06 3.50e-05 | 8.21e-06 3.50e-05 | 3.61e-06 1.15e-05 |
| iter=10 | iter=50 | iter=100 | iter=500 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PGM | M1 | M2 | M3 | M1 | M2 | M3 | M1 | M2 | M3 | M1 | M2 | M3 |
| BN_12 | 0.622 0.152 | 0.523 0.136 | 0.0966 0.126 | 0.207 0.0678 | 0.164 0.0652 | 0.0456 0.0536 | 0.107 0.0517 | 0.0869 0.0472 | 0.0287 0.0344 | 0.0232 0.0282 | 0.0196 0.0191 | 0.00762 0.0125 |
| BN_13 | 0.461 0.127 | 0.351 0.123 | 0.0441 0.082 | 0.121 0.109 | 0.0632 0.0513 | 0.0141 0.027 | 0.055 0.107 | 0.0252 0.0284 | 0.00693 0.0148 | 0.0171 0.105 | 0.00163 0.00398 | 0.000534 0.00208 |
| BN_14 | 0.305 0.126 | 0.24 0.121 | 0.027 0.0712 | 0.0498 0.0822 | 0.0243 0.033 | 0.0048 0.0184 | 0.0196 0.0758 | 0.0066 0.0143 | 0.00161 0.00825 | 0.0101 0.074 | 4.36e-05 0.000532 | 3.92e-05 0.000519 |
| BN_9 | 0.179 0.0896 | 0.167 0.0742 | 0.0207 0.0456 | 0.0529 0.0624 | 0.0271 0.0353 | 0.00463 0.0157 | 0.0256 0.0555 | 0.00918 0.0185 | 0.00172 0.00812 | 0.0105 0.0529 | 3.98e-05 0.000526 | 2.19e-05 0.000485 |
| Grids_26 | 36.1 53 | 37 52.8 | 16 34.1 | 4.42 11.5 | 4.43 11.5 | 2.13 7.35 | 0.664 2.63 | 0.663 2.63 | 0.337 1.86 | 0.0114 0.114 | 0.0115 0.114 | 0.00931 0.0947 |
| iter=0 | iter=10 | iter=50 | iter=100 | conv | ||||||||
| PGM | J | N | J | N | J | N | J | N | J | N | win@10 | |
| BN_12 | -0.02 | -0.17 | -0.22 | -0.48 | -0.74 | -1.05 | -1.65 | -2.04 | -6.79 | -6.77 | 100% | |
| BN_13 | -0.04 | -0.19 | -0.29 | -0.60 | -0.97 | -1.15 | -1.34 | -1.55 | -7.17 | -6.98 | 100% | |
| BN_14 | -0.34 | -0.39 | -0.66 | -0.83 | -1.23 | -1.33 | -4.22 | -4.52 | -6.49 | -6.42 | 100% | |
| Seg_12 | 0.21 | -0.05 | -0.01 | -1.01 | -4.13 | -4.94 | -7.10 | -6.69 | -7.10 | -6.69 | 100% | |
| Seg_14 | 0.18 | -0.42 | -0.73 | -2.00 | -6.34 | -4.62 | -6.34 | -6.13 | -6.34 | -6.19 | 100% | |
| PGM | iter=10 | iter=50 | iter=100 | iter=500 | ||||
|---|---|---|---|---|---|---|---|---|
| win N | win A | win N | win A | win N | win A | win N | win A | |
| BN_126 | 89 | 52 | 56 | 56 | 78 | 44 | 78 | 56 |
| BN_12 | 100 | 100 | 90 | 97 | 100 | 93 | 100 | 100 |
| BN_13 | 100 | 100 | 100 | 100 | 60 | 73 | 80 | 77 |
| BN_14 | 100 | 100 | 80 | 80 | 80 | 77 | 90 | 90 |
| BN_9 | 70 | 67 | 70 | 60 | 100 | 100 | 100 | 100 |
| PGM | no-LP M2 | no-LP M3 | main M2 | main M3 | M2 | M3 | note |
|---|---|---|---|---|---|---|---|
| BN_9 | 97.6 | 95.2 | 75.2 | 92.8 | |||
| BN_14 | 100 | 100 | 100 | 99.2 | |||
| Segmentation_18 | 78.7 | 92.4 | 52.6 | 89.6 | |||
| Segmentation_19 | 46.4 | 80.0 | 7.2 | 72.0 | |||
| grid10 10 | 10.0 | 10.0 | 10.0 | 10.0 | degenerate | ||
| grid40 40.f10 | 0.0 | 0.0 | 0.0 | 0.0 | degenerate |
| message source | min | min rel. | median | max | |
|---|---|---|---|---|---|
| margin | margin | ||||
| zero ( , the MBE bound) | 1598 | -6.07e-8 | -1.22e-10 | 1.86e+0 | 0.00e+0 |
| trained network | 1598 | 8.31e-2 | 1.25e-4 | 1.47e+0 | 9.09e-13 |
| untrained network (random init) | 1598 | 6.25e+1 | 4.01e-2 | 1.54e+2 | 9.09e-13 |
| anti-trained ( ) | 1598 | 1.01e+1 | 1.29e-2 | 4.20e+1 | 1.36e-12 |
| adversarial Gaussian ( ) | 1598 | 3.47e+1 | 6.16e-2 | 2.10e+2 | 9.09e-12 |
| PGM | M1 | M2 | M3 | M4 | M5 |
|---|---|---|---|---|---|
| BN_12 | 0.6589 | 0.5693 | 0.007023 | 1.872e-06 | 0.3061 |
| BN_13 | 0.4128 | 0.3782 | 0.004231 | 5.975e-07 | 0.368 |
| BN_14 | 0.5343 | 0.4731 | 0.0009809 | 2.039e-07 | 0.2535 |
| BN_9 | 0.1388 | 0.1029 | 0.001156 | 3.118e-07 | 0.2148 |
| Grids_26 | 6.021 | 5.987 | 0.0428 | 147.4 | 9066 |
| PGM | iter=0 | iter=10 | iter=50 | iter=100 | iter=500 |
|---|---|---|---|---|---|
| median [95% CI] | median [95% CI] | median [95% CI] | median [95% CI] | median [95% CI] | |
| BN_12 | 0.105 † [0.094, 0.112] | 0.230 † [0.212, 0.258] | 0.206 † [0.180, 0.240] | 0.152 † [0.122, 0.193] | -0.000 [-0.000, -0.000] |
| BN_13 | 0.103 † [0.077, 0.112] | 0.244 † [0.231, 0.273] | 0.129 † [0.099, 0.186] | 0.062 † [0.035, 0.093] | -0.000 † [-0.000, -0.000] |
| BN_14 | -0.039 † [-0.082, -0.026] | 0.200 † [0.157, 0.232] | 0.104 † [0.080, 0.151] | -0.000 [-0.020, 0.040] | -0.000 † [-0.000, -0.000] |
| BN_9 | -0.081 † [-0.124, -0.052] | 0.070 [-0.014, 0.100] | -0.914 † [-1.354, -0.540] | -0.002 † [-0.006, -0.001] | -0.000 † [-0.000, -0.000] |
| Grids_26 | 0.008 † [0.001, 0.024] | 0.000 [-0.001, 0.002] | -1.121 † [-2.928, -0.022] | -1.902 † [-2.264, -1.362] | -0.028 † [-0.054, -0.015] |
| PGM | iter=0 | iter=10 | iter=50 | iter=100 | iter=500 | |
|---|---|---|---|---|---|---|
| BN_12 | 100 | 97% [91, 99] | 100% [96, 100] | 91% [84, 96] | 93% [86, 97] | 96% [90, 99] |
| BN_13 | 100 | 89% [81, 94] | 100% [96, 100] | 90% [82, 95] | 72% [62, 81] | 84% [75, 91] |
| BN_14 | 100 | 31% [22, 41] | 96% [90, 99] | 78% [69, 86] | 54% [44, 64] | 96% [90, 99] |
| BN_9 | 100 | 28% [19, 38] | 59% [49, 69] | 13% [7, 21] | 79% [70, 87] | 100% [96, 100] |
| Grids_26 | 100 | 62% [52, 72] | 54% [44, 64] | 25% [17, 35] | 12% [6, 20] | 97% [91, 99] |
| Grids_28 | 100 | 62% [52, 72] | 43% [33, 53] | 24% [16, 34] | 7% [3, 14] | 97% [91, 99] |
| PGM | iter=10 | iter=50 | iter=100 | |
|---|---|---|---|---|
| median [95% CI] | median [95% CI] | median [95% CI] | ||
| BN_12 | 1 | -3.06 † [-3.54, -1.37] | -1.00 † [-1.61, -0.47] | -0.15 † [-0.56, -0.05] |
| BN_13 | 1 | -3.91 † [-4.54, -3.43] | -1.95 † [-2.85, -0.58] | -0.47 † [-1.04, -0.26] |
| BN_14 | 1 | -3.86 † [-4.40, -3.26] | -1.71 † [-2.81, -0.51] | -0.31 † [-1.23, -0.10] |
| BN_9 | 1 | -3.91 † [-4.40, -3.37] | -1.33 † [-1.80, -0.75] | -0.11 † [-0.26, -0.04] |
| PGM | Gate | median gap at iter=10 | gated worse than J (#seeds) | ||||
| fires | J | N | gated | it=10 | it=100 | it=500 | |
| BN_12 | 97% | 0.54 | 0.299 | 0.299 | 0 | 7 | 4 |
| BN_13 | 89% | 0.449 | 0.249 | 0.26 | 0 | 24 | 12 |
| BN_14 | 31% | 0.3 | 0.169 | 0.232 | 0 | 15 | 0 |
| BN_9 | 28% | 0.0291 | 0.0161 | 0.0214 | 7 | 5 | 0 |
| Grids_26 | 62% | 2.21 | 2.22 | 2.21 | 20 | 52 | 3 |
| PGM | depth | w=128 | w=256 | w=512 | w=1024 | params (w=512) | fwd (ms) |
|---|---|---|---|---|---|---|---|
| BN_13 | 2 | +0.346 | +0.358 | +0.330 | +0.332 | 1.42M | 0.64 |
| 3 | +0.322 | +0.316 | +0.290 | +0.294 | 1.01M | 0.66 | |
| 4 | +0.271 | +0.259 | +0.262 | +0.267 | 1.07M | 0.70 | |
| Grids_29 | 2 | +0.022 | +0.022 | +0.019 | +0.015 | 2.00M | 0.76 |
| 3 | +0.023 | +0.013 | +0.010 | +0.011 | 1.37M | 0.75 | |
| 4 | +0.018 | +0.013 | +0.011 | +0.010 | 1.44M | 0.97 |
| PGM | 250 | 500 | 1000 | 2000 | 4000 | 8000 | 16000 |
|---|---|---|---|---|---|---|---|
| held-out standalone gap | |||||||
| BN_13 | 0.694 | 0.6744 | 0.6815 | 0.6646 | 0.6664 | 0.6648 | 0.6724 |
| Grids_29 | 7.5 | 7.457 | 7.424 | 7.387 | 7.374 | 7.423 | 7.417 |
| Segmentation_14 | 0.4442 | 0.4148 | 0.4084 | 0.4114 | 0.4361 | 0.4842 | 0.4588 |
| iteration-10 paired improvement | |||||||
| BN_13 | +0.318 | +0.305 | +0.312 | +0.291 | +0.305 | +0.304 | +0.301 |
| PGM | knee | ||||||
|---|---|---|---|---|---|---|---|
| held-out standalone gap at iteration 0 (lower is tighter) | |||||||
| BN_13 | 1.78 | 1.24 | 0.94 | 0.77 | 0.73 | 0.69 | |
| Seg_14 | 2.89 | 1.50 | 1.04 | 0.65 | 0.54 | 0.43 | |
| Grids_29 | 19.43 | 13.15 | 9.42 | 8.05 | 7.68 | 7.56 | |
| paired iteration-10 improvement over zero-init, (higher favours the network) | |||||||
| BN_13 | 0.357 | 0.377 | 0.377 | 0.353 | 0.334 | 0.316 | already flat |
| PGM | T4 | range | ||||
|---|---|---|---|---|---|---|
| Seg_18 | +0.21 | 0.208 | 0.200 | 0.189 | 0.184 | 0.024 |
| BN_14 | +0.17 | 0.144 | 0.146 | 0.152 | 0.152 | 0.008 |
| Grids_23 | +0.02 | 0.035 | 0.029 | 0.031 | 0.029 | 0.006 |
| Grids_18 | +0.01 | 0.015 | 0.018 | 0.016 | 0.017 | 0.002 |
| Seg_19 | -2.26 | 0.086 | 0.081 | 0.091 | 0.106 | 0.025 |
| grid80 80.f5 | -3.83 | -6.115 | -5.976 | -5.992 | -5.917 | 0.198 |
| PGM | train size | train gap | test gap | difference |
|---|---|---|---|---|
| BN_13 | 250 | 0.66629 | 0.72039 | +0.054108 |
| BN_13 | 500 | 0.67301 | 0.68346 | +0.010447 |
| BN_13 | 1000 | 0.62922 | 0.66779 | +0.038565 |
| BN_13 | 2000 | 0.78199 | 0.68431 | -0.097674 |
| BN_13 | 4000 | 0.62562 | 0.66762 | +0.042 |
| BN_13 | 8000 | 0.80683 | 0.66225 | -0.14459 |
Probabilistic Graphical Models
Probabilistic graphical models represent joint distributions with graphs to support structured inference, learning, and reasoning under uncertainty.
See all 58 papers