iterative-reasoning-as-energy-minimization/index.html at main · energy-based-model/iterative-reasoning-as-energy-minimization · GitHub

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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description"
          content="Learning Iterative Reasoning through Energy Minimization">
    <meta name="author"
          content="Yilun Du, Shuang Li, Joshua B. Tenenbaum, Igor Mordatch">

    <title>Learning Iterative Reasoning through Energy Minimization</title>
    <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css"
          integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">

    <!-- Custom styles for this template -->
    <link href="offcanvas.css" rel="stylesheet">
    <!--    <link rel="icon" href="img/favicon.gif" type="image/gif">-->
</head>

<style type="text/css">
.move-up {margin-top:-1.4cm}
.move-up-small {margin-top:-0.4cm}
.move-up-more {margin-top:-0.7cm}
</style>

<body>
<div class="jumbotron jumbotron-fluid">
    <div class="container"></div>
    <h2>Learning Iterative Reasoning through Energy Minimization</h2>
    <h3>ICML 2022</h3>
    <hr>
    <p class="authors">
        <a href="https://yilundu.github.io">Yilun Du</a>,
        <a href="https://shuangli59.github.io/"> Shuang Li</a>,
        <a href="https://mitibmwatsonailab.mit.edu/people/joshua-tenenbaum/"> Joshua B. Tenenbaum</a>,
        <a href="">Igor Mordatch</a>
    </p>
    <div class="btn-group" role="group" aria-label="Top menu">
        <a class="btn btn-primary" href="https://arxiv.org/abs/2206.15448">Paper</a>
        <a class="btn btn-primary" href="https://github.com/yilundu/irem_code_release">Code</a>
    </div>
</div>


<div class="container">
    <div class="section move-up">
        <div class="row align-items-center justify-content-center col text-left">
            <video width="80%" playsinline="" autoplay="" loop="" preload="" muted="">
                <source src="img/video.mp4" type="video/mp4">
            </video>
            <p>
            <b>Reasoning as Energy Minimization:</b> We formulate reasoning as an optimization process on a learned energy landscape. Above, we illustrate intermediate optimized solutions as we compute the shortest path in a densely connected graph, compute the summation of two 20x20 input matrices, and denoise a noisy input image.
            </p>
        </div>

        <br>
        <div class="move-up-small">
        <p>
        Deep learning has excelled on complex pattern recognition tasks such as image classification and object recognition. However, it
        struggles with tasks requiring nontrivial reasoning, such as algorithmic computation. Humans are able to solve such tasks through iterative reasoning
        -- spending more time to think about harder tasks. Most existing neural networks, however, exhibit a fixed computational budget controlled by the neural
        network architecture, preventing additional computational processing on harder tasks. In this work, we present a new framework for iterative reasoning with neural networks.
        We train a neural network to parameterize an energy landscape over all outputs, and implement each step of the iterative reasoning as an energy minimization
        step to find a minimal energy solution. By formulating reasoning as an energy minimization problem, for harder problems that lead to more complex energy landscapes,
        we may then adjust our underlying computational budget by running a more complex optimization procedure. We empirically illustrate that our iterative reasoning approach can
        solve more accurate and generalizable algorithmic reasoning tasks in both graph and continuous domains. Finally, we illustrate that our approach can recursively solve algorithmic problems
        requiring nested reasoning.
        </p>
        </div>


    </div>

    <div class="section">
        <h2>Reasoning through Energy Minimization</h2>
        <hr>
        <p>
           Existing approaches torwards iterative reasoning typically rely on the iterative application of a neural
           network module. In this work, we propose an alternative iterative reasoning approach, Iterative Reasoning
           as Energy Minimization (IREM), where iterative reasoning is implemented as a iterative optimization process
           on a learned neural energy landscape parameterized using an EBM. Below, we illustrate this conversion,
           where the algorithmic operation of addition is converted to an optimization process on a learned
           energy landscape. The solution of the algorithmic task corresponds to the minimum of the energy landscape.
           By formulating iterative reasoning in this manner, we obtain a natural termination criteria for reasoning
           (corresponding to a minimum the energy function). Furthermore, we illustrate how this enables us to
           adaptively reasoning dependent on the inherent difficulty of the task, and generalize to more complex
           variants of the task.
        </p>

        <div class="row align-items-center justify-content-center text-center">
            <video width="50%" playsinline="" autoplay="" loop="" preload="" muted="">
                <source src='img/teaser.mp4' type='video/mp4'>
            </video>
        </div>

    </div>

    <div class="section">
        <h2>Graphical Reasoning</h2>
        <hr>
        <p>
         First, we illustrate how IREM enables iterative reasoning on graphs. We consider graphical tasks such
         as shortest path and connected components computation. On the <b>bottom left</b>, we illustrate the computation of
         shortest path using IREM. As sequential optimization steps are run, IREM is able to gradually recover the
         ground truth shortest path between start node (pictured in green) to a goal node (pictured in blue).
         On the <b>bottom right</b>, we find that IREM is able to generalize discrete algorithmic computations to significantly
         larger graphs at test time (performance on up size 30 graphs is shown), when only trained on up to size 10 graphs.
         IREM exhibits superior performance by utilizing more underlying algorithmic computation steps for more complex
         problems. In constrast, a recurrent approach is unable to extend algorithmic
         computation to large graphs, with increased iterative computation failing to improve final performance.
        </p>

        <div class="row justify-content-left">
            <div class="col-sm-6">
                <video width="100%" playsinline="" autoplay="" loop="" preload="" muted="">
                    <source src='img/opt_vis.mp4' type='video/mp4'>
                </video>
			</div>
            <div class="col-sm-6">
                <img width="100%" src='img/graph_reason.png' class='img-fluid'>
            </div>
        </div>

    </div>

    <div class="section">
        <h2>Matrix Reasoning </h2>
        <hr>
        <p>
         Next, we further illustrate how IREM enables us to solve algorithmic reasoning tasks on matrix inputs.
         In the figure below, we illustrate the optimization process on the task of <b>matrix addition</b>, where we seek to add all elements
         in a 20x20 matrix together. We plot the predicted matrix sum over the course of optimization, as well as the associated error map.
         Over sequential reasoning steps, we find that IREM is able to compute addition across elements in the matrix <b>nearly perfectly</b>. We find that
         IREM significantly outperforms baselines across tasks such as matrix addition, matrix inverse,
         and low-rank matrix completion. We further find that IREM is able to generalize better to harder problem instances
         than baselines.
        </p>

        <div class="row align-items-center">
            <div class="col justify-content-center text-left">
                <video width="100%" playsinline="" autoplay="" loop="" preload="" muted="">
                    <source src='img/continuous.mp4' type='video/mp4'>
                </video>
                <p>
                <b>Matrix Addition:</b> Illustration of predicted solutions from IREM when adding Matrix A and B, both of size 20x20. As optimization is run, predictions (third column) converge to the correct answer, and the error map (fourth column), consisting of the L1 error of the predicted answer and ground truth answer, decreases to 0.
                </p>
            </div>
        </div>

    </div>


    <div class="section">
        <h2>Recursive Reasoning</h2>
        <hr>

        <!---
        <div class="row align-items-center">
            <div class="col justify-content-center text-center">
                <img width="30%" src='img/recursive.png' class='img-fluid'>
            </div>
        </div>
        --->

        <div class="row justify-content-left">
            <div class="col-sm-8">
                Finally, we illustrate how IREM enables us to recursively apply learned algorithmic computations on
                multiple inputs. On the right, we consider the addition task, and recursively apply a learned
                addition operation on up to 10 different 20x20 matrices. As each input is recursively added,
                the underlying error of intermediate computations increase, and to perform well on this task,
                models must be able to generalize well to out-of-distribution intermediate computations.
                Compared to baselines, IREM generalizes substantially better to recursive algorithmic application,
                exhibiting low computation error and sensible solutions even when up to 10 different matrices are
                added (see example below on 4 input matrices).
			</div>
            <div class="col-sm-4">
                <img width="100%" src='img/recursive.png' class='img-fluid'>
            </div>
        </div>

        <div class="row align-items-center">
            <div class="col justify-content-center text-left">
                <p>
                <b>Qualitative Composition:</b> Illustration of predicted solutions from IREM when recursively adding four 20x20 matrices. First 9 entries of the predicted 20x20 matrix are shown. Predictions are close to ground truth answer.
                </p>
                <div class="move-up-more">
                <img width="100%" src='img/recursive_qualitative.png' class='img-fluid'>
                </div>
            </div>
        </div>

    </div>

        <div class="section">
            <h2>Related Projects</h2>
            <hr>
            <p>
            Check out our related projects on energy based models! A full list can be found <a href="https://energy-based-model.github.io/">here</a>. <br>
            </p>

          <div class="row vspace-top">
                <div class="col-sm-3">
                    <img src="img/comet_teaser.gif" class="img-fluid" alt="comet" style="width:100%">
                </div>

                <div class="col-sm-9">
                    <div class="paper-title">
                        <a href="https://energy-based-model.github.io/comet/">Unsupervised Learning of Compositional Energy Concepts</a>
                    </div>
                    <div>
                       We present a framework to decompose images into energy functions representing  both global factors
                        of variation as well as local factors of variation. We show such decomposed components
                         generalize well, and are amenable to compositions across different modes of data, and can
                        be further composed with separate energy functions discovered on other datasets.
                    </div>
                </div>
          </div>

            <div class='row vspace-top'>
                <div class="col-sm-3">
                    <img src='img/comp_cartoon.png' class='img-fluid'>
                </div>

                <div class="col">
                    <div class='paper-title'>
                        <a href="https://energy-based-model.github.io/compositional-generation-inference/">Compositional Visual Generation with Energy Based Models</a>
                    </div>
                    <div>
                        We show how EBMs enable <b>zero-shot compositional</b> visual generation, enabling us to compose visual concepts
                        (through operators of conjunction, disjunction, or negation) together in a zero-shot manner.
                        Our approach enables us to generate faces given a  description
                        ((Smiling AND Female) OR (NOT Smiling AND Male)) or to combine several different objects together.
                    </div>
                </div>
            </div>

            <div class='row vspace-top'>
                <div class="col-sm-3">
                    <video width="100%" playsinline="" autoplay="" loop="" preload="" muted="">
                        <source src="img/half.mp4" type="video/mp4">
                    </video>
                </div>

                <div class="col">
                    <div class='paper-title'>
                        <a href="https://openai.com/blog/energy-based-models/">Implicit Generation and Generalization with Energy Based Models</a>

                    </div>
                    <div>
                        We introduce a method to scale EBM training to modern neural network architectures.
                        We show that such trained EBMs have a set of unique properties, enabling model robustness,
                        image and trajectory modeling, continual learning and compositional visual generation.
                    </div>
                </div>
            </div>


            <div class="section">
                <h2>Paper</h2>
                <hr>
                <div>
                    <div class="list-group">
                        <a href=""
                           class="list-group-item">
                            <img src="img/paper_thumbnail.png"
                                 style="width:100%; margin-right:-20px; margin-top:-10px;">
                        </a>
                    </div>
                </div>
            </div>

            <div class="section">
                <h2>Bibtex</h2>
                <hr>
                <div class="bibtexsection">
                    @inproceedings{du2022irem,
                      title={Learning Iterative Reasoning through Energy Minimization},
                      author={Du, Yilun and Li, Shuang and Tenenbaum, B. Joshua
                      and Mordatch, Igor},
                      booktitle={Proceedings of the 39th International Conference on Machine
                    Learning (ICML-22)},
                      year={2022}
                    }
                </div>
            </div>

            <hr>

            <footer>
                <p>Send feedback and questions to <a href="https://yilundu.github.io">Yilun Du</a></p>
            </footer>
        </div>

</body>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
</html>