<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Scampbell on Medium]]></title>
        <description><![CDATA[Stories by Scampbell on Medium]]></description>
        <link>https://medium.com/@scampbell2792?source=rss-989127a57a06------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*zBZo6cHLGtrDjELM</url>
            <title>Stories by Scampbell on Medium</title>
            <link>https://medium.com/@scampbell2792?source=rss-989127a57a06------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 10:51:10 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@scampbell2792/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Neural ODEs and robotic motion]]></title>
            <link>https://medium.com/correll-lab/neural-odes-and-robotic-motion-70d84808c69f?source=rss-989127a57a06------2</link>
            <guid isPermaLink="false">https://medium.com/p/70d84808c69f</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[hopper]]></category>
            <category><![CDATA[neural-ode]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[inverted-pendulum]]></category>
            <dc:creator><![CDATA[Scampbell]]></dc:creator>
            <pubDate>Thu, 01 May 2025 21:45:22 GMT</pubDate>
            <atom:updated>2025-05-01T21:45:22.524Z</atom:updated>
            <content:encoded><![CDATA[<h4>Training a model for an inverted pendulum and a hopper and using it in RL</h4><h4>Motivation: Robot dynamics are hard</h4><p>Modeling robot motion is notoriously difficult: deriving closed-form dynamics is error-prone and simulators struggle with contact, friction, flexible links and environmental effects (wind, water, terrain…). A data-driven alternative would let us collect input–output trajectories and learn a continuous-time model automatically. A good dynamics model could then power faster planning, safer model-based RL or robust control. Because much of robot movement is really a continuous physics problem (think a quadrotor flying in wind), Neural ODEs might offer a natural inductive bias for capturing the smooth, time-varying dynamics. Of course, for the non-smooth bits, we expect neural ODEs to struggle.</p><p>Previously, I wrote a <a href="https://medium.com/correll-lab/neural-odes-a-review-35457d66ea2b">short review of Neural ODE</a>s.</p><p><a href="https://medium.com/correll-lab/neural-odes-a-review-35457d66ea2b">Neural ODEs: A review</a></p><h4>The Inverted Pendulum with Neural ODEs</h4><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FfXbqDDaJDvg%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DfXbqDDaJDvg&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FfXbqDDaJDvg%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/60a32168573e1e9a77ce2e0dff8a94b1/href">https://medium.com/media/60a32168573e1e9a77ce2e0dff8a94b1/href</a></iframe><p>Before moving on to a hard robotics problem, let’s start with a classic control problem. If we can’t solve this, we’re doing something wrong or this approach is a bad idea. The goal of the <a href="https://gymnasium.farama.org/environments/mujoco/inverted_pendulum/">inverted pendulum problem</a> is to balance a vertically oriented pendulum on a cart by controlling the horizontal position of the cart via left/right motor commands. If the pendulum angle from the vertical exceeds 0.2 radians, we consider the pendulum to have fallen. The actions are 2 dimensional continuous variables that control the force that the motor exerts to move the car left or right and the observations (or state) is 4 dimensional and includes the angular position/velocity of the pendulum and the x position and velocity of the cart.</p><p>Can we quickly learn a model for how the pendulum moves in response to the cart and then use that model to achieve our goal of balancing the pendulum? Yes.</p><p>The following simple scheme works. Note that I use the term “trajectory” to refer to a sequence of states and actions until the pendulum falls over.</p><p>1. Move the pendulum randomly for bit to collect a trajectory. Fit a neural ODE model that predicts the next state given the current state and motor inputs.</p><p>2. Use that model to try to keep the pendulum upright by making predictions about which motor inputs will keep the pendulum angle minimized (i.e. backpropagate through the dynamics model to find actions that minimize the angle). This will fail until we have collected enough trajectories to train a good model. However, each time that we fail, we collect another sample to train our neural ODE model.</p><p>3. Retrain the neural ODE model on all the trajectories collected thus far.</p><p>4. Repeat steps 2 and 3 until we can balance the pendulum (defined as balancing the pendulum for 1k steps).</p><p>In code, this looks like</p><pre>class StatePredictor(nn.Module):<br>    def __init__(self, state_dim, action_dim, hidden_dim=64):<br>        super(StatePredictor, self).__init__()<br>        self.net = nn.Sequential(<br>            nn.Linear(state_dim + action_dim, hidden_dim),<br>            nn.Tanh(),<br>            nn.Linear(hidden_dim, hidden_dim),<br>            nn.Tanh(),<br>            nn.Linear(hidden_dim, state_dim)<br>        )<br><br>    def forward(self, state, action):<br>        t = torch.tensor([0.0, 1.0], dtype=state.dtype, device=state.device)<br>        def f(t, s):<br>            return self.net(torch.cat([s, action], dim=-1))<br>        out = odeint(f, state, t, method=&#39;euler&#39;)<br>        return out[-1]<br><br>def train_model(data_loader, state_dim, action_dim, epochs=50, lr=5e-4, hidden_dim=128):<br>    dynamics_model = StatePredictor(state_dim, action_dim, hidden_dim=hidden_dim)<br>    optimizer = torch.optim.Adam(dynamics_model.parameters(), lr=lr, weight_decay=1e-3)<br>    criterion = nn.MSELoss()<br>    for epoch in range(epochs):<br>        total_loss = 0.0<br>        for states_seq, actions_seq, next_states_seq in data_loader:<br>            optimizer.zero_grad()<br>            batch_size, seq_len = states_seq.shape[0], states_seq.shape[1]<br>            loss_seq = 0<br>            curr = states_seq[:, 0]<br>            for t in range(seq_len):<br>                act = actions_seq[:, t]<br>                target = next_states_seq[:, t]<br>                pred = dynamics_model(curr, act)<br>                loss_seq += criterion(pred, target)<br>                curr = pred<br>            loss_seq = loss_seq / seq_len<br>            loss_seq.backward()<br>            optimizer.step()<br>            total_loss += loss_seq.item()<br>   <br>    return dynamics_model<br><br>def learn_pendulum_balancing():<br>    max_iterations = 100<br>    all_trajectories = []<br>    all_data_points = []<br>    total_env_steps = 0<br>    <br>    initial_trajectories, steps = collect_data(num_episodes=10)<br>    all_trajectories.extend(initial_trajectories)<br>    total_env_steps += steps<br>    print(f&quot;Collected {len(initial_trajectories)} random trajectories, Total steps: {total_env_steps}&quot;)<br>    <br>    traj_sample = all_trajectories[0]<br>    state_dim = traj_sample[&#39;states&#39;].shape[1]<br>    action_dim = traj_sample[&#39;actions&#39;].shape[1]<br>    <br>    for iteration in range(max_iterations):<br>        print(f&quot;\nIteration {iteration+1}/{max_iterations}&quot;)<br>        # Can train on longer sequence lengths but it&#39;s not helpful here<br>        sequence_length = 2<br>        data_loader = prepare_training_data(all_trajectories, batch_size=512, sequence_length=sequence_length)<br>        model = train_model(data_loader, state_dim, action_dim, epochs=10, lr=5e-4, hidden_dim=64)<br>        # Collect new trajectories using predictions from our model.<br>        avg_reward, std_reward, new_trajectories, eval_steps = eval_model(<br>            model, horizon=1, iterations=20, lr=1e-2, n_evals=1<br>        )<br>        <br>        all_trajectories.extend(new_trajectories)<br>        all_data_points.append({<br>            &#39;total_steps&#39;: total_env_steps,<br>            &#39;avg_reward&#39;: avg_reward,<br>            &#39;std_reward&#39;: std_reward<br>        })<br><br>        total_env_steps += eval_steps<br>        if avg_reward == 1000:<br>            break<br>        <br>        print(f&quot;Total environment steps: {total_env_steps}&quot;)</pre><p>Our action selection could be performed in a variety of ways but minimizing the predicted angle using gradient descent worked fine here.</p><pre>def optimize_actions(model, init_state, horizon=10, iterations=100, lr=1e-4):<br>    init_state_tensor = torch.tensor(init_state, dtype=torch.float32).unsqueeze(0)<br>    actions = nn.Parameter(torch.randn(horizon, 1) * 0.1)<br>    optimizer = torch.optim.Adam([actions], lr=lr)<br>    <br>    for i in range(iterations):<br>        optimizer.zero_grad()<br>        current_state = init_state_tensor.clone()<br>        total_angle_cost = 0.0<br>        discount = 1.0<br>        for t in range(horizon):<br>            action = torch.tanh(actions[t]) * 3.0<br>            action = action.unsqueeze(0)<br>            next_state = model(current_state, action)<br>            angle = next_state[0, 1]<br>            angle_cost = torch.abs(angle)*10<br>            total_angle_cost *= discount<br>            total_angle_cost += angle_cost<br>            current_state = next_state.detach().clone()<br>        <br>        total_angle_cost.backward()<br>        optimizer.step()<br>    <br>    with torch.no_grad():<br>        # Actions are in the range [-3, 3]<br>        final_actions = torch.tanh(actions) * 3.0<br>    <br>    return final_actions</pre><p>This generally works well and we can learn to balance the pendulum after 1–5k environment steps. The full code is <a href="https://colab.research.google.com/drive/1Oe5AfoCTGw1hptfN8PlduJy8MfrEc_qK?usp=sharing">here</a>.</p><p>That said, I did have to spend more time tuning hyperparameters than I would have liked. In particular, as we gather more trajectories and retrain the model, it appears that the model will frequently overfit to a particular trajectory and the performance will decrease drastically. I had to add quite bit of regularization in the form of weight decay. Additionally, for action selection (i.e backpropagating through the neural ODE to find the best action), I had to spend time tuning the learning rate and initial action distribution which was tedious. Finally, not all activation functions seem to work well: ReLUs and SiLUs were significantly harder to use than Tanh activations.</p><p>Despite these annoyances, the hope is that this setup for learning the pendulum balancing will extend to more complex control problems.</p><h4>Modeling the Hopper with neural ODEs</h4><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FjtXiTP96wow%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DjtXiTP96wow&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FjtXiTP96wow%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/818cb64f57b2e1c93a0aa83d070d8bc1/href">https://medium.com/media/818cb64f57b2e1c93a0aa83d070d8bc1/href</a></iframe><p>While we can solve the pendulum problem easily, that’s not very interesting. Thus, we move to much harder problem: the <a href="https://gymnasium.farama.org/environments/mujoco/hopper/">MuJoCO Hopper robot </a>available in Gymnasium. This is a simulator for a one legged pogo stick robot. To control it, we provide 3 continuous motor inputs while our state consists of 11 continuous variables that represent the positions and velocities of various joints. This is unrealistic for many reasons. Namely, you’d likely not have noise free access to all of the joint positions/velocities but, again, we just want to see if Neural ODEs are useful in a simplified setting before spending time on more complex and realistic problems.</p><p>To begin, <a href="https://colab.research.google.com/drive/1v28w1iAt55-16-O7pssMCqaNaRDjmOIC?usp=sharing">I train an RL agent</a> using a standard model free RL algorithm (PPO) to learn a good gait. I collect a 1000 examples of it rapidly hopping. I then run a series of experiments where I look at how far into the future I can accurately predict various states.</p><p>I wanted to answer the following questions:</p><ul><li>Given a set of good trajectories from a learned policy (i.e. not random actions), can neural ODEs learn to predict far enough into the future to be useful without significant error or instabilities? (Yes)</li><li>Do neural ODEs do a better job than a naive baseline like just predicting the change in state? (Yes)</li><li>Do we get any benefit from using smaller step sizes or more advanced solvers like RK4 vs Euler? (Slightly)</li><li>Do the dynamics models generalize? Can we learn the dynamics of the ODEs from pure random actions well enough to model a good trajectory? Can we learn the dynamics of the ODEs from learned trajectories well enough to model random trajectories (i.e. taking random actions)? (No)</li><li>Can we use a trained dynamics model to control the robot and learn new gaits? Sadly, I could not get this to work despite major simplifications and lots of effort but maybe someone else can.</li></ul><p>Below, I walk through a series of experiments. While I focus on visualizing a few states of a single trajectory and qualitatively evaluating them, the aggregate statistics (i.e. average multistep error across all samples and states) support the claims I end up making. I omit them for the sake of brevity and clarity.</p><p>Variations on <a href="https://colab.research.google.com/drive/1mvYSN5Qr-nH8vgz5k2UM29SAM3oKE101#scrollTo=5IStoR5AXnjA">this code</a> were used to run the following experiments. I don’t go into it here because it’s straight forward and similar to the pendulum code above.</p><p><strong>Experiment 1: Baseline</strong></p><p>As a baseline, I trained a model (2 layers, 128 units w/ SiLU activations) that predicted state changes between pairs of collected states and visualized the predictions on a single trajectory.</p><p>Technically, this is a neural ODE but for trajectories of length 2 and solved with Euler integration. This is a common approach people have used and so it’s a fair baseline. Below are multistep predictions for the first state variable which represents the height of the torso. Each step is 0.008 seconds in the simulator and so this is a 5.6 second long episode.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xi12xtd90b0qrwZVUarpVw.png" /></figure><p>While the 10 step predictions appear fine, it looks like the 20 steps predictions are unstable and explode. I investigated this for a bit and found that that I should use tanh activations (like I found for the pendulum) and also normalize my inputs (as is usually good practice). Doing so, I got a much more reasonable result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X4ZpN8hEn23Xufljm1U7Pg.png" /></figure><p>And here’s the second state (the angle of the torso in radians) which contains more abrupt transitions and is harder to learn.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kOe3ClEXb2GYNaWMCAbqdw.png" /></figure><p>The first thing about these plots are that they are periodic (the robot is hopping) with periods of about 100 and thus, we probably need to predict about 100 steps into the future (about 0.8 seconds) if we want our dynamics model to be useful. Secondly, the multistep predictions aren’t that bad. The 100 step prediction is not great but the shorter time horizons line up with the ground truth. We also don’t see any exploding instabilities.</p><p><strong>Experiment 2: Can we do better with ODEs?</strong></p><p>Next, I trained this as an ODE (same network) with Euler on trajectory lengths of up to 6. Why 6? Well, training on long trajectories is painfully slow and the goal here is to just learn if using more of the trajectory actually gives us any benefit. Here’s the same state dimensions after training:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-witpxj-wKhFwxIjKiXoOg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WtARc9Kab0XwFOAGRXkkJQ.png" /></figure><p>The 100 step predictions are looking a lot better. Similarly, here’s state 4 which represents the x velocity of the torso which also looks excellent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-7jZCzLPo2SGA8zzygmizg.png" /></figure><p>As a comparison, I also tried training the same ODE but using RK4 instead of Euler to integrate the ODE. RK4 theoretically gets a better estimate of the derivative by taking several steps. The results appear to be a mixed bag. For most of the states, the RK4 100 step predictions are a bit better and for a handful they’re a little worse. In aggregate, RK4 seems marginally better (especially for states that have abrupt changes) but it’s significantly slower to train. For example, RK4 for the second state which is one of the harder ones to learn produces this (compare to the State 1 graph above)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vss4zDNonxGN5ISsQ9ESsQ.png" /></figure><p>Finally, to test whether or not training on even longer trajectories helps, I trained the Euler model on sequence lengths of up to length 12. This further improved long term horizon predictions. Here is State 1 yet again where we see that the pink curve (100 step prediction) aligns with the ground truth even better.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m27PYQr3Rt1k6Y-NrHrt4A.png" /></figure><p><strong>Experiment 3: Do the dynamics generalize?</strong></p><p>I collected some trajectories from a policy that was much worse than the PPO one. This policy falls over after 140 steps. Can the dynamics we’re learning from the good PPO model be used here? Sadly no. Below, we see that the short horizon predictions up to about 5 steps are reasonably accurate but the longer term predictions are garbage.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7G8JUwm9qPJN0pP4Os72ig.png" /></figure><p>Similarly, we can try the reverse experiment. Train on data collected from a random policy (i.e. take random motor actions and collect trajectories) and see if that can be used to produce accurate predictions for a good model. The results are similar to the above which is disappointing. I tried a several variations on data collection and other tweaks to no avail.</p><h3>Parting thoughts</h3><p>So, are we just overfitting then? I think the answer is not quite yes. Rather, the neural ODEs don’t contain a strong enough inductive bias to help model dynamics in regions they’ve never seen before. It’s worth noting that I tried a number of variations on networks / regularization / data collection / curriculum learning / etc to be sure that this wasn’t just an artifact of vanilla overfitting and got similarly poor results when testing on out of distribution trajectories.</p><p>What does this mean from a practical standpoint? Well it means that we can certainly learn good dynamics models for a particular hopping gait which might be useful but we shouldn’t expect these to be particularly helpful when making predictions for different hopping gaits (i.e. out of distribution data which is the story of all neural networks).</p><p>To me, this suggests that neural ODEs might be useful if you already have a robot that has a learned gait (or your robot is extremely simple) and need to make predictions for safety or control reasons. There are also may be some work where you could combine the dynamics learning with a model free algorithm like PPO and learn them in tandem.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=70d84808c69f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/correll-lab/neural-odes-and-robotic-motion-70d84808c69f">Neural ODEs and robotic motion</a> was originally published in <a href="https://medium.com/correll-lab">Toward Humanoids</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Neural ODEs: A review]]></title>
            <link>https://medium.com/correll-lab/neural-odes-a-review-35457d66ea2b?source=rss-989127a57a06------2</link>
            <guid isPermaLink="false">https://medium.com/p/35457d66ea2b</guid>
            <category><![CDATA[neural-ode]]></category>
            <category><![CDATA[differential-equations]]></category>
            <category><![CDATA[dynamical-systems]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Scampbell]]></dc:creator>
            <pubDate>Sat, 26 Apr 2025 22:29:38 GMT</pubDate>
            <atom:updated>2025-05-01T21:53:12.651Z</atom:updated>
            <content:encoded><![CDATA[<h3>Neural ODEs: A Step-by-Step Example</h3><h4>Static example: generating a simple spiral pattern</h4><p>Many phenomena in the universe are continuous processes which are modeled with ordinary differential equations. This is common in all scientific disciplines. Specific examples include topics like weather prediction, fluid flow modeling, and disease spread.</p><p>Finding closed form solutions for most of these problems is not possible and thus we numerically solve these ODEs; however, we don’t always even know the correct way to write these equations down. We may just have data and know that the process we’re trying to model is continuous. We’d like to learn such an ODE from the data.</p><p>Neural networks are exceptionally good at learning from data; however, vanilla neural networks tend to operate in a discrete space. Thus is the idea behind neural ODEs: let’s learn how a system <em>changes</em> continuously over time rather than predicting discrete steps directly. This idea was first introduced in the paper “<a href="https://arxiv.org/pdf/1806.07366">Neural Ordinary Differential Equations</a>” introduced by Chen et al. and they show it works to model a variety of simple phenomena. We won’t review this here but instead will focus on how the idea works.</p><h3>Basic idea</h3><p>The key idea of Neural ODEs is to learn a function that predicts the derivative — the rate of change — rather than the future state itself.<br>Once we have a model for the derivative, we can recover trajectories by integrating it over time, just like in traditional ODE solving.</p><p>Euler’s method is the simplest numerical integration scheme: given a current state, we step forward a small amount of time using the estimated derivative.</p><p>In a Neural ODEs, we apply the same principle, but the derivative function is parameterized by a neural network, allowing it to flexibly model complex, unknown dynamics.<br> This continuous-time formulation naturally handles irregular time series, where measurements could be taken at nonuniform intervals, and provides an inductive bias toward smooth, continuous system evolution. Much like Convolutional Neural Nets have an inductive bias that makes them suitable for images, Neural ODEs have an inductive bias towards modeling continuous systems.</p><p>Mathematically, this is given below where h is your neural network.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*dDklu6plFDxUW5g4" /></figure><p>If we integrate this using Euler’s method, we end up with a prediction for the next state:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/824/0*lWnfXpK1wd_FYB3p" /></figure><p>where h is your step size and z is your state at time t. By reducing your step size you can obtain more accurate solutions. Or you can use standard ODE solvers that dynamically adjust step size based on how “fast” your derivative function is changing. This lets you take big steps when your derivative is boring and slow ones when it rapidly changes.</p><h3>How do we train these?</h3><p>The simplest and often the fastest method is to simply “unroll” each step of the ODE (just like you would with an RNN) and backpropagate through the network (i.e. if you do 2 steps of Euler integration, just pretend like you have a network with 2 layers). However, if your network is large, this is memory intensive thus Chen et al. invent something called the adjoint method which allows memory efficient backpropagation. For smaller networks, this is often much slower than the “dumb” unrolling method.</p><h3>A code example</h3><p>In the code below is a (simplified) implementation of Euler’s method using Torch. See a full code example <a href="https://colab.research.google.com/drive/17kBvuIeXwVgrRwsi27_rqXjiBxZKYx--?usp=sharing">here</a>. We use a spiral dataset (visualized below) and our goal is to predict the spiral datapoints given just the initial data point. Intuitively, we have a point at the origin and it gets pushed around by some mysterious forces over time and we’d like to figure out what that trajectory looks like. We set up our loss function to be the MSE between the predicted datapoints and the ground truth.</p><p>For simplicity, we assume a fixed step size that is equal to the difference between input time points; however, in practice it is good to be able to control the step size explicitly. You may wish to take multiple steps between time points though this adds incidental code complexity and so I omit it here.</p><pre>class ODEFunc(nn.Module):<br>    def __init__(self, hidden_dim, input_dim):<br>        super(ODEFunc, self).__init__()<br>        self.net = nn.Sequential(<br>            nn.Linear(input_dim, hidden_dim),<br>            nn.ELU(),<br>            nn.Linear(hidden_dim, hidden_dim),<br>            nn.ELU(),<br>            nn.Linear(hidden_dim, input_dim)<br>        )<br><br>    def forward(self, t, x):<br>        return self.net(x)<br><br>class ODESolver(nn.Module):<br>    def __init__(self, func):<br>        super(ODESolver, self).__init__()<br>        self.func = func<br>        self.method = method<br><br>    def forward(self, x0, t):<br>        # t is vector of time points to evaluate (i.e. [1, 2, 3, ...])<br>        h = t[1] - t[0]  # Assuming uniform time steps<br>        trajectory = [x0]<br>        x = x0<br><br>        for i in range(len(t) - 1):<br>            # Simple Euler method<br>            dx = self.func(t[i], x) * h<br>            x = x + dx<br>            trajectory.append(x)<br><br>        return torch.stack(trajectory)<br><br>def main():<br>    n_points = 50<br>    spiral_data = generate_spiral_data(n_points=n_points, noise=0.1)<br>    spiral_data = torch.tensor(spiral_data, dtype=torch.float32)<br><br>    t = torch.linspace(0, 1, n_points)<br><br>    func = ODEFunc(hidden_dim=100, input_dim=2)<br>    ode_solver = ODESolver(func)<br><br>    x0 = spiral_data[0]<br><br>    optimizer = optim.Adam(func.parameters(), lr=0.01)<br><br>    # Training loop<br>    n_epochs = 300<br>    losses = []<br><br>    for epoch in tqdm(range(n_epochs)):<br>        optimizer.zero_grad()<br>        pred_trajectory = ode_solver(x0, t)<br><br>        # Loss is MSE between predicted and true trajectory (only for original dimensions)<br>        loss = nn.MSELoss()(pred_trajectory[:, :, :2].squeeze(), spiral_data)<br><br>        loss.backward()<br>        optimizer.step()<br><br>        losses.append(loss.item())</pre><p>The dataset, the training loss, and the vector field (i.e. what direction the neural network predicts that a point should move) are visualized below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*DrEbW8s4ufzz1S7Z" /></figure><p>There’s a couple things to note here. One, the loss is a bit unstable which is common for Neural ODEs and two, this takes a long time to train given that this is a toy problem. These and several other considerations are addressed in the next section.</p><p>As we will see, vanilla neural ODEs on their own are really not that great. They need to be extended in many cases in order to be used effectively.</p><h3>Practical tips and considerations</h3><h4>Batching</h4><p>In the example, above we are trying to predict a single trajectory given an initial point. However, usually we want to learn from a dataset of many trajectories of different lengths and we’d like to batch them together during training to expedite it. To batch them, we need to add masking to our losses. Furthermore, if the trajectories are of vastly different lengths, we may wish to group them by sequence length in order to best make use of computational resources.</p><h4>Activation functions (avoid ReLUs)</h4><p>Since these networks are attempting to predict continuous phenomena, they tend to do poorly with activation functions that have sharp discontinuities. It’s recommended to avoid ReLUs.</p><h4>Curriculum learning</h4><p>Like RNNs, Neural ODEs may struggle with vanishing or exploding gradients as either the step size decreases or the trajectory length increases. This causes the loss to jump around wildly. One way to mitigate this is to gradually increase the sequence length that your network is trained on. For example, you might initially just predict the difference between pairs of points. Then every epoch you might increase the trajectory length (e.g. first train on sequences of lengths 4 then 8 then 16) that the neural ODE is being trained on until you reach the full trajectory length.</p><h4>Augmented neural ODES</h4><p>This is an incredibly simple extension. The idea is that your state (suppose it’s just the position of a particle) may not include everything that you want to know to predict the next state (maybe you should also have velocity and acceleration) . Thus, you add extra state dimensions that the network can learn. This is just appending zeros to your initial state dimension. As the state evolves over time those state dimensions will get filled in with numbers that are useful for the neural network. This often speeds learning as well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/669/0*IG-kGCqR7y75rVps" /></figure><h3>Extensions</h3><h4>Neural Event Functions and Neural Jump ODEs</h4><p>Many phenomena are continuous but have sharp discontinuities. These are also known as hybrid systems. Neural ODEs are not great at learning these. For example, image a ball bouncing. When it is in the air, we can model its next state easily. However, when it hits the ground, it abruptly reverses the direction of its velocity. Knowing exactly when it hits the ground will greatly impact the Neural ODE’s predictions. Small errors here will vastly change the result. Thus, you want to find the event time at which this state change occurs.</p><p><a href="https://arxiv.org/abs/2011.03902">Neural Event functions</a> solve this problem by allowing you to specify a condition under which they should abruptly change the state. They then find the exact time that the event triggers. In the case of the bouncing ball example, you might have the event trigger when the center of the ball is near the ground. At this point, a search will be run to find exactly when the ball intersects the ground. Then the ball’s state will be set to reflect that it is now bouncing up.</p><p><a href="https://arxiv.org/abs/2006.04727">Neural Jump ODEs</a> are a similar approach to solve this problem but can learn when the state transitions occur and were originally designed for more stochastic processes.</p><p>Examples where these techniques are useful include ground contact in robotic locomotion or sudden state changes in a control system (e.g. a thermostat turning off/on).</p><h4>Physics informed Neural networks</h4><p><a href="https://www.sciencedirect.com/science/article/abs/pii/S0021999118307125">Physics-Informed Neural Networks</a> (PINNs) embed known physical laws into the loss function or Neural ODE derivative function and encourage the neural network to satisfy conservation laws or force balances. In short, physics constraints can be added as an inductive bias that improves learning.</p><h3>Successful applications</h3><p>While incredibly cool, Neural ODEs have remained a relatively niche topic For example, they’ve seen some success for problems such as time series forecasting with extremely irregularly spaced data. Probably, their biggest application today is for Flow Matching in Generative image models which sometimes outperforms diffusion modeling. That said, there are many folks playing around with them still so perhaps that will change.</p><p>Keep on reading for some robotic applications:</p><p><a href="https://medium.com/correll-lab/neural-odes-and-robotic-motion-70d84808c69f">Neural ODEs and robotic motion</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=35457d66ea2b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/correll-lab/neural-odes-a-review-35457d66ea2b">Neural ODEs: A review</a> was originally published in <a href="https://medium.com/correll-lab">Toward Humanoids</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving mazes with an encoder decoder transformer]]></title>
            <link>https://medium.com/correll-lab/solving-mazes-with-an-encoder-decoder-transformer-2bfffcf2ab54?source=rss-989127a57a06------2</link>
            <guid isPermaLink="false">https://medium.com/p/2bfffcf2ab54</guid>
            <category><![CDATA[transformers]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Scampbell]]></dc:creator>
            <pubDate>Sun, 16 Feb 2025 19:49:08 GMT</pubDate>
            <atom:updated>2025-02-24T23:55:58.976Z</atom:updated>
            <content:encoded><![CDATA[<h3>An intro to encoder/decoder architectures via maze solving</h3><h4>Combining image and text encodings with code</h4><p>Transformers are shockingly impressive tools but the vanilla versions struggle with simple algorithmic and planning tasks such as adding 50 digit numbers, sorting long sequences, and solving mazes of sufficient size. There’s been interest in figuring out how to train such models on small instances of algorithmic problems and then get them to generalize to larger instances that they’ve never seen before. Terms such as “length generalization”, “algorithm synthesis”, and “test time compute” are often used (e.g. <a href="https://arxiv.org/abs/2502.05171">1</a> and <a href="https://arxiv.org/abs/2202.05826">2</a>). With this in mind, I walk through building a ViT encoder connected to a standard LLM style decoder. Then I test how this model does on several sizes of maze tasks. Next, I check that attention in the decoder is actually important for solving mazes by limiting its context window and find that, as expected, you get much worse performance if the model cannot attend to the full sequence that it is producing. Finally, I test if a minor modification (“<a href="https://arxiv.org/abs/2501.19399">Scalable-Softmax Is Superior for Attention</a>”) to the attention mechanism improves results. Maybe.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/892/1*Yv5pwTgQfSHZ1xp44ZJOFw.png" /><figcaption>Solution to a 27x27 maze, entirely generated by using an encoding of the image to drive a decoder to produce a string of commands.</figcaption></figure><p>In short, vanilla transformer models do well (99%+ accuracy) at solving mazes with solution paths of 200+ nodes which was contrary to what I expected. In future work, I would like to look at solving length generalization for harder problems with longer sequence lengths using some form of “test-time compute”.</p><p>I base my model on the implementation of MNIST ViT described in the tutorial <a href="https://medium.com/correll-lab/building-a-vision-transformer-model-from-scratch-a3054f707cc6">here</a> and <a href="https://www.youtube.com/watch?v=kCc8FmEb1nY&amp;list=PL5jy_XLCvJTU54FrQ6y5nnjA_yrxRGn7L&amp;index=10&amp;ab_channel=AndrejKarpathy">Karpathy’s NanoGPT</a>. Minor modifications are made to combine them into a single model. The <a href="https://colab.research.google.com/drive/1QB2iGSEQZWa5XKBiMiQ5TzllYHDwE1aJ?usp=sharing">full code is here</a>.</p><p><a href="https://medium.com/correll-lab/building-a-vision-transformer-model-from-scratch-a3054f707cc6">Building a Vision Transformer Model From Scratch</a></p><h4>Aside</h4><p>Why are mazes (somewhat) interesting as a toy problem?</p><ol><li>To solve a big maze with transformer, your attention mechanism needs to be able to handle the full length of the output sequence without too much error. We know that vanilla attention is both computationally (O(N²)) expensive but also diffuse at longer sequence lengths. This means we quickly and cheaply test attention mechanisms and see their effects. Furthermore, errors compound quickly. For example, if the model outputs a correct step 99.99% (assume independence between steps) of the time and the output length is 1000, the model will fail 10% of the time.</li><li>We can play around a lot with the input and output representations. The inputs and outputs could both be images or they could both be text. Mazes can be represented as graphs with directed edges and outputs could be nodes or actions.</li><li>It’s straightforward to test new algorithmic learning approaches by varying the maze size and difficulty and seeing if it scales.</li></ol><h4>Problem setup</h4><p>The input to our model will be a fixed size NxN binary image with the maze entrance in the top left and the exit in the bottom right. There is only a single solution to each maze. The output will be a sequence of L, R, U, D (left, right, up, down) tokens that represent the action sequence needed to exit (solve)the maze.</p><p>For example the input might be something like</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*nQ7jCUYHH0FQrcx7zu3evw.png" /><figcaption>27x27 maze</figcaption></figure><p>and the output (solution) might be “rddddddddddddrrrru…”.</p><p>Mazes are generated using a custom generator (created with the help of Claude) that uses a simple DFS strategy. You can see this code <a href="https://colab.research.google.com/drive/1nqdOOxhGxB1G86WXjUT5AJqS66cEWINl?usp=sharing">here</a>. I opted to avoid some of the datasets used in other papers because I wanted the flexibility to easily vary the dataset sizes, maze sizes, input and output formats, and tune difficulty.</p><h4>ViT</h4><p>I use the basicViT architecture <a href="https://colab.research.google.com/drive/10ZbVkgTaCaPIBaDZfJtJj5DfAEdbU8YR?usp=sharing">here</a> (see <a href="https://medium.com/correll-lab/building-a-vision-transformer-model-from-scratch-a3054f707cc6">tutorial</a> for details) but modify it in the following ways:</p><ol><li>Remove the MLP layer on top of the CLS token</li><li>Using learned position embeddings instead of sinusoidal. This choice is fine for a fixed size input but if I wanted to vary the maze input size, I would need to switch to a different embedding such relative positional embeddings.</li><li>Removing the CLS token as it provides no predictive value. I actually did not do this but it shouldn’t hurt the model.</li></ol><p>This results in a ViT encoder that outputs a tensor with shape [batch, seq length, model dim] where the sequence length is determined by the patch size and image dimensions.</p><h4>Decoder</h4><p>The basic decoder model presented in Karpathy’s NanoGPT must be modified in the following ways:</p><ol><li>Allow it to attend to the encoder output from the ViT model using so called “Cross Attention”.</li><li>Add special tokens to our vocab and inputs.<br>- Add a special padding (PAD) so that the model can be trained on multiple sequence lengths. Note that these padding tokens must be masked out in the loss.<br>- Add start of sequence (SOS) token. The SOS token is technically not needed but it is convenient to start the model this way and it makes the unpadded inputs/outputs the same length (b/c they’d differ by 1 otherwise).<br>- Add end of sequence tokens (EOS). This is needed so that the model can indicate when it is done solving the maze.<br>Putting these together mean that our decoder token inputs and outputs end up looking like (for a batch of size 2 and maximum sequence length of 10):</li></ol><pre>inputs = [[sos, l, r, u, d,   eos, pad, pad, pad, pad], <br>          [sos, r, r, r, r,   d,   r,   eos, pad, pad]]<br>outputs = [[l,  r, u, d, eos, pad, pad, pad, pad, pad], <br>          [r,   r, r, r, d,   r,   eos, pad, pad, pad]]</pre><p>3. Allow the model to generate new sequences using the maximum predicted token rather than sampling. For language generation, we might want diversity and a range of outputs. For this task, there is only one correct solution.</p><p>4. Mask out padding tokens in the loss. We don’t want our model to be predicting and learning padding tokens. Padding is often masked out inside the model when computing logits (we can just add another mask to the attention) but in this case it is simpler to just do it at the end when we compute losses.</p><h4>Cross Attention</h4><p>In self attention, we generate weighted embeddings for a sequence via 3 tensors: Q, K, and V (queries, keys, and values) which we use to “attend” to elements of the same sequence. In other words, the token you’re generating looks at the previous tokens.</p><p>In contrast, cross attention is a way for one sequence to “attend” to another sequence. In this case, we want our next direction token to attend to the sequence of image embeddings produced by our ViT encoder.</p><p>This means that we use the decoders’ tokens to produce queries while the encoder’s outputs are used to used produce keys and values.</p><p>Together, the overall architecture looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TAbIigpSXnSBnKmG3pR8zg.png" /><figcaption>Using the encoder/decoder architecture, we use image encodings of a maze to generate appropriate solution paths using a decoder.</figcaption></figure><p>Here’s what this looks like in python:</p><pre>class AttentionHead(nn.Module):<br>    def __init__(self, d_model, head_size, causal=False):<br>        super().__init__()<br>        self.head_size = head_size<br>        self.causal = causal<br><br>        self.query = nn.Linear(d_model, head_size)<br>        self.key = nn.Linear(d_model, head_size)<br>        self.value = nn.Linear(d_model, head_size)<br><br>    def forward(self, x, encoder_output=None):<br>        B, T, C = x.shape  # batch size, sequence length, embedding dimension<br>        device = x.device  # Get the device from input tensor<br><br>        # The so called cross attention.<br>        if encoder_output is not None:<br>            K = self.key(encoder_output)<br>            V = self.value(encoder_output)<br>        else:<br>            K = self.key(x)    # (B, T, head_size)<br>            V = self.value(x)  # (B, T, head_size)<br><br>        Q = self.query(x)<br>        attention = Q @ K.transpose(-2, -1)  # (B, T, T)<br>        attention = attention / (self.head_size ** 0.5)<br><br>        if self.causal:<br>            mask = torch.triu(torch.ones(T, T, device=device), diagonal=1).bool()<br>            attention = attention.masked_fill(mask, float(&#39;-inf&#39;))<br><br><br>        attention = F.softmax(attention, dim=-1)<br>        output = attention @ V  # (B, T, head_size)<br>        return output</pre><p>Putting this together into full decoder layer that uses both self attention and cross attention, we get this:</p><pre>class DecoderLayer(nn.Module):<br>    def __init__(self, d_model, n_heads):<br>        super().__init__()<br>        self.self_attention = MultiHeadAttention(d_model, n_heads, causal=True)<br>        self.cross_attention = MultiHeadAttention(d_model, n_heads)<br>        self.feed_forward = FeedForward(d_model)<br>        self.ln1 = nn.LayerNorm(d_model)<br>        self.ln2 = nn.LayerNorm(d_model)<br>        self.ln3 = nn.LayerNorm(d_model)<br><br>    def forward(self, x, encoder_output):<br>        x = x + self.self_attention(self.ln1(x))<br>        x = x + self.cross_attention(self.ln2(x), encoder_output)<br>        x = x + self.feed_forward(self.ln3(x))<br>        return x</pre><p>Note that our attention to the ViT embeddings does not need to (and should not) be causal.</p><p>Thus, our decoder looks like this</p><pre>class Decoder(nn.Module):<br>    def __init__(self, vocab_size, d_model, n_heads, n_layers, max_seq_length):<br>        super().__init__()<br>        self.token_embedding_table = nn.Embedding(vocab_size, d_model)<br>        self.position_embedding_table = nn.Embedding(max_seq_length, d_model)<br>        self.blocks = nn.ModuleList([DecoderLayer(d_model, n_heads=n_heads) for _ in range(n_layers)])<br>        self.ln_f = nn.LayerNorm(d_model)<br>        self.lm_head = nn.Linear(d_model, vocab_size)<br>        self.max_seq_length = max_seq_length<br><br>    def forward(self, idx, encoder_output):<br>        B, T = idx.shape<br><br>        # Get the device from the input tensor<br>        device = idx.device<br><br>        tok_emb = self.token_embedding_table(idx) # (B,T,C)<br>        pos_emb = self.position_embedding_table(torch.arange(T, device=device)) # (T,C)<br>        x = tok_emb + pos_emb # (B,T,C)<br>        for layer in self.blocks:<br>            x = layer(x, encoder_output) # (B,T,C)<br>        x = self.ln_f(x) # (B,T,C)<br>        logits = self.lm_head(x) # (B,T,vocab_size)<br><br>        return logits</pre><p>And our full encoder decoder model looks like</p><pre>class EncoderDecoder(nn.Module):<br>    def __init__(self,<br>                 tgt_vocab_size,<br>                 img_size,<br>                 patch_size,<br>                 n_channels,<br>                 d_model,<br>                 n_heads,<br>                 n_encoder_layers,<br>                 n_decoder_layers,<br>                 max_seq_length):<br>        super().__init__()<br><br>        self.encoder = VisionTransformer(d_model, img_size, patch_size, n_channels, n_heads, n_encoder_layers)<br><br>        self.decoder = Decoder(<br>            vocab_size=tgt_vocab_size,<br>            d_model=d_model,<br>            n_heads=n_heads,<br>            n_layers=n_decoder_layers,<br>            max_seq_length=max_seq_length<br>        )<br><br>    def forward(self, maze, idx):<br>        encoder_output = self.encoder(maze)<br>        decoder_output = self.decoder(idx, encoder_output)<br><br>        return decoder_output<br><br>    def generate(self, mazes, max_length):<br>        encoder_output = self.encoder(mazes)<br><br>        # Start with SOS token (6)<br>        current_output = torch.ones((mazes.shape[0], 1),<br>                                  dtype=torch.long,<br>                                  device=mazes.device) * SOS<br><br>        for _ in range(max_length - 1):<br>            logits = self.decoder(current_output, encoder_output)<br>            logits = logits[:,-1, :]<br>            probs = torch.softmax(logits, dim=-1)<br>            next_token = torch.argmax(logits, dim=-1, keepdim=True)<br>            current_output = torch.cat([current_output, next_token], dim=1)<br><br>        return current_output</pre><p>Note that during generation, we use torch.argmax to select the most likely direction rather than using multinomial sampling as you would in an LLM.</p><p>The final change we need is to be sure to mask out the padding token in the loss during training which can be done like so:</p><pre>    def _compute_loss(self, logits, targets, input_mask):<br>        batch_size, seq_len, vocab_size = logits.shape<br>        logits = logits.view(-1, vocab_size)<br>        targets = targets.view(-1)<br><br>        # Compute loss with mask for padding<br>        loss = F.cross_entropy(logits, targets, reduction=&#39;none&#39;)<br>        mask = (input_mask != self.pad_token_id).view(-1)<br>        masked_loss = loss * mask<br>        return masked_loss.sum() / mask.sum()</pre><p>The <a href="https://colab.research.google.com/drive/1QB2iGSEQZWa5XKBiMiQ5TzllYHDwE1aJ?usp=sharing">full code is here</a>.</p><h4>Scalable-Softmax Attention</h4><p>We test this modification below in the decoder against regular attention. The idea of <a href="https://arxiv.org/pdf/2501.19399">this paper</a> is simple. It scales the attention logits in the following way because as they show, attention to the maximum element in a sequence quickly diffuses when the sequence gets long.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/370/1*4aNfgkroa9Au73OkAte93g.png" /><figcaption>Scale logits by number of items attended to</figcaption></figure><p>Z are logits, s and b and learnable parameters, and n is the number of things being attended. So in, causal attention, if you are token number 10, n is 10 while if you are token 100, n =100. Thus, N is different across a single sequence and IS NOT just the sequence length which is what I first thought when reading the paper.</p><p>The paper looks at sequences much longer than what I investigated here so perhaps this is silly. Here’s what this looks like in code:</p><pre>class AttentionHead(nn.Module):<br>    def __init__(self, d_model, head_size, causal=False):<br>        super().__init__()<br>        self.head_size = head_size<br>        self.causal = causal<br><br>        self.query = nn.Linear(d_model, head_size)<br>        self.key = nn.Linear(d_model, head_size)<br>        self.value = nn.Linear(d_model, head_size)<br>        # --&gt; Add two params per attention head. Initialization is important<br>        # for s.<br>        self.s = torch.nn.Parameter(torch.ones(1) * 1.0/math.log(150))<br>        self.b = torch.nn.Parameter(torch.ones(1) * 0.0))<br><br>    def forward(self, x, encoder_output=None):<br>        B, T, C = x.shape  # batch size, sequence length, embedding dimension<br>        device = x.device  # Get the device from input tensor<br><br>        # The so called cross attention.<br>        if encoder_output is not None:<br>            K = self.key(encoder_output)<br>            V = self.value(encoder_output)<br>        else:<br>            K = self.key(x)    # (B, T, head_size)<br>            V = self.value(x)  # (B, T, head_size)<br><br>        Q = self.query(x)<br>        attention = Q @ K.transpose(-2, -1)  # (B, T, T)<br>        attention = attention / (self.head_size ** 0.5)<br><br>        if self.causal:<br>            # --&gt; Scalable softmax attention. Yup, this is it. &lt;-----------<br>            attention = (self.s * torch.log(torch.arange(1,T + 1, device=device).unsqueeze(1)) + self.b) * attention<br>            mask = torch.triu(torch.ones(T, T, device=device), diagonal=1).bool()<br>            attention = attention.masked_fill(mask, float(&#39;-inf&#39;))<br><br><br>        attention = F.softmax(attention, dim=-1)<br>        output = attention @ V  # (B, T, head_size)<br>        return output</pre><h4>Context limited attention</h4><p>I wanted to test how important attention in the decoder was. To do this, we can limit how many previous tokens that the decoder looks at using at simple mask. In the AttentionHead class, we replace the logic for causal masking with:</p><pre>        if self.causal:<br>            # For causal, mask out future tokens and limit to k previous tokens<br>            mask = torch.triu(torch.ones(T, T, device=device), diagonal=1).bool()<br>            # Also mask tokens that are more than k positions away (in the past)<br>            past_mask = torch.tril(torch.ones(T, T, device=device), diagonal=-k).bool()<br>            mask = mask | past_mask<br>            attention = attention.masked_fill(mask, float(&#39;-inf&#39;))</pre><p>The key line is torch.tril(torch.ones(T, T, device=device), diagonal=-k) which just creates a lower triangular matrix offset from the diagonal. To make this more concrete, lets look at an example:</p><pre>T = 10<br>k=3<br>mask = torch.triu(torch.ones(T, T), diagonal=1).bool()<br># Also mask tokens that are more than k positions away (in the past)<br>past_mask = torch.tril(torch.ones(T, T), diagonal=-k).bool()<br>mask = mask | past_mask<br>print(mask)<br># This produces the following where the True entries get filled with -inf during the softmax<br>tensor([[False,  True,  True,  True,  True,  True,  True,  True,  True,  True],<br>        [False, False,  True,  True,  True,  True,  True,  True,  True,  True],<br>        [False, False, False,  True,  True,  True,  True,  True,  True,  True],<br>        [ True, False, False, False,  True,  True,  True,  True,  True,  True],<br>        [ True,  True, False, False, False,  True,  True,  True,  True,  True],<br>        [ True,  True,  True, False, False, False,  True,  True,  True,  True],<br>        [ True,  True,  True,  True, False, False, False,  True,  True,  True],<br>        [ True,  True,  True,  True,  True, False, False, False,  True,  True],<br>        [ True,  True,  True,  True,  True,  True, False, False, False,  True],<br>        [ True,  True,  True,  True,  True,  True,  True, False, False, False]])</pre><h4>Experiments</h4><p>I generated 3 datasets and trained models on them. I wanted to test 3 things, maze size, dataset size, and different attention mechanisms in order to partly answer the following questions:</p><p>How big does our training set need to be to get “decent” performance? (Answer: 100k)</p><p>Can the model reliably solves mazes with long-ish paths (say 200+ nodes) (Answer: Yes).</p><p>Does context limited attention hurt maze solving? (Answer: Quite a bit.)</p><p>Does Scalable-Softmax Attention help? (Answer: maybe slightly at these maze sizes. I don’t think I tested mazes with long enough path sequences to really see a big effect).</p><p><a href="https://docs.google.com/spreadsheets/d/10ZFN2NsPdOCK8qYmoxnjtG9_tTJgpotw3qrQZ4tKJKM/edit?pli=1&amp;gid=1037515222#gid=1037515222">Sheets with more detailed results</a></p><h4>Experiment 1</h4><p>60k 20 x 20 mazes = training, 5k = validation. Max path length is 150. Used cosine learning rate schedule and default Adam params. Trained for 15 epochs. Did minor hyperparam exploration to ensure the network was large enough to actually learn.</p><p><strong>Results</strong>: Context limiting severely hurts accuracy and scalable attention was slightly but consistently better than regular attention over several runs. Specifically, accuracy increases for attention with a context of 10 from 7%, to 69% with 40, to 89% with 80, and to 94.1% with full context. Scalable attention got the best accuracy with 95.5%.</p><h4>Experiment 2</h4><p>100k 20 x 20 mazes = training, 5k = validation. Everything is the same from the previous experiment except we increase the training set size.</p><p><strong>Results</strong>: The training and validation loss basically go to 0 unlike in experiment 1 and we get much better accuracy with scalable attention getting 99.22% of all mazes correct and regular attention getting 98.96%. Though the difference is tiny, oddly, the scalable attention did very slightly better for repeated runs.</p><p>I was a bit suspicious of the validation loss being nearly 0 and triple checked that my training data did not include any of it.</p><h4>Experiment 3</h4><p>100k 28 x 28 mazes = training, 10k = validation. Everything is the same from the previous experiment except the model dimension is doubled, the maze size is much bigger, and the maximum solution path length is a bit under 300.</p><p><strong>Results</strong>: The training and validation loss basically go to 0 and Scalable Attention gets 98.7% and regular gets 98.5% accuracy. The biggest differences seem to come at the longer solution lengths but, again, the differences are minuscule overall.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2bfffcf2ab54" width="1" height="1" alt=""><hr><p><a href="https://medium.com/correll-lab/solving-mazes-with-an-encoder-decoder-transformer-2bfffcf2ab54">Solving mazes with an encoder decoder transformer</a> was originally published in <a href="https://medium.com/correll-lab">Toward Humanoids</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>