After studying this material, you should be able to:

1. Explain what non-parametric trajectory prediction is and why it differs from deep learning approaches
2. Describe how a transition table is built and queried using a product kernel
3. Distinguish between diversity-penalized sampling and beam search inference modes
4. Evaluate when this approach is preferable over transformer-based models
5. Interpret evaluation metrics (ADE, top-1, best-of-k) used in trajectory prediction

---

Step-by-Step Teaching

Step 1: The Core Problem — What is Trajectory Prediction?

Trajectory prediction asks: Given where something has been, where will it go next?

Past positions → [Model] → Future positions
(observed)                  (predicted)

Real-world example: A ship is sailing northeast at 12 knots. Where will it be in 3 hours?

The challenge is that the future is multi-modal — meaning there are multiple plausible futures, not just one:

                    → Port A (route 1)
Ship position now → → Open sea (route 2)
                    → Port B (route 3)

---

Step 2: The Traditional Approach vs. This Paper's Approach

Traditional Deep Learning Approach

• Train a massive neural network (e.g., 57M parameters)
• Requires GPU, weeks of training, large datasets
• Acts as a black box — hard to interpret why it predicts something

This Paper's Approach: Non-Parametric

• Zero learned parameters
• Runs on CPU, fits in seconds
• Predictions are directly grounded in historical observations
• Interpretable: "This prediction exists because ships in similar states did this before"

💡 Key Concept: "Non-parametric" does NOT mean "no math." It means the model doesn't learn fixed parameters — instead, it grows with data and retrieves answers from stored examples.

---

Step 3: Building the Transition Table

This is the foundation of the entire method.

What is a Transition Table?

A transition table stores historical records of the form:

(current state) → (next position)

What defines a "state"?

The state captures everything relevant about a moving object at a moment in time:

Building the Table (Conceptually)

Historical AIS data (ship GPS logs):
─────────────────────────────────────
Time T:   state_1 → position at T+Δt  ← stored as row 1
Time T+1: state_2 → position at T+1+Δt ← stored as row 2
...
Millions of such rows form the transition table

💡 Analogy: Think of it like a massive lookup table of "what happened next" for every situation ever observed.

---

Step 4: Querying the Table — The Product Kernel

When you want to predict from a new state, you can't just look it up exactly (it probably never occurred identically). Instead, you find similar states using a product kernel.

What is a Kernel?

A kernel is a similarity function — it scores how similar two states are, returning values between 0 and 1.

kernel(state_query, state_stored) → similarity score [0, 1]

What is a Product Kernel?

A product kernel combines multiple individual similarity scores by multiplying them:

K_total = K_spatial × K_bearing × K_speed × K_temporal

Each component:

K_spatial:  Are the positions geographically close?
            → High score if within a few km, low score if far away

K_bearing:  Are the headings similar?
            → High score if both heading northeast, low if one goes north, other south

K_speed:    Are the speeds similar?
            → High score if both ~12 knots, low if one is 2 knots vs 20 knots

K_temporal: Is the time context similar?
            → High score if both Tuesday afternoon, low if one is Sunday midnight

Why multiply?

Multiplication enforces that ALL dimensions must match for a high score:

Example:
K_spatial = 0.9 (very close geographically)
K_bearing = 0.8 (similar heading)
K_speed   = 0.1 (very different speed!)
K_temporal = 0.9

K_total = 0.9 × 0.8 × 0.1 × 0.9 = 0.065  ← LOW overall similarity

💡 Intuition: A ship in the same location but going twice as fast is in a fundamentally different state — it shouldn't be treated as a close neighbor.

---

Step 5: Two Inference Modes

Once you can query similar historical transitions, you need a strategy to generate predictions. The paper offers two modes for different use cases.

---

Mode 1: Beam Search (Best Single Prediction)

Goal: Find the single most likely future trajectory.

How it works:

Step 1: Start at current state
Step 2: Query transition table → get weighted neighbors
Step 3: Keep top-K most likely next positions ("beams")
Step 4: From each beam, repeat steps 2-3
Step 5: After N steps, return the highest-likelihood complete path

Visualization:

Start
  ├── Position A (prob: 0.6) ──→ A1 (0.5) ──→ A1a ✓ BEST PATH
  │                          └─→ A2 (0.1)
  └── Position B (prob: 0.3) ──→ B1 (0.2)
      (pruned if beam width = 1)

Result: One trajectory — the most probable route.

Use case: When you need a single definitive answer (e.g., collision avoidance system).

---

Mode 2: Diversity-Penalized Sampling (Multiple Plausible Trajectories)

Goal: Generate multiple trajectories that cover distinct plausible futures.

The Problem with Naive Sampling:

If you just sample randomly from the transition table, you might get:

Trajectory 1: Ship goes to Port A
Trajectory 2: Ship goes to Port A (slightly different path)
Trajectory 3: Ship goes to Port A (almost identical)

This is redundant — you haven't explored the space of possibilities.

The Diversity Penalty Solution:

When generating trajectory N, penalize next positions that are too similar to positions already chosen in trajectories 1 through N-1:

Score(candidate) = Likelihood(candidate) - λ × Similarity(candidate, previous trajectories)

Where λ controls the diversity-likelihood tradeoff.

Result:

Trajectory 1:  → Port A (northeast route)
Trajectory 2:  → Open sea (east route)      ← penalized from going near Port A
Trajectory 3:  → Port B (southeast route)   ← penalized from previous two
...
Trajectory 16: → (another distinct route)

Use case: When you want to understand the full range of possibilities (e.g., search and rescue planning).

---

Step 6: Evaluation Metrics

ADE — Average Displacement Error

Measures the average distance between predicted and actual positions:

ADE = (1/N) × Σ distance(predicted_position_t, actual_position_t)

Lower ADE = better prediction.

Top-1 ADE vs. Best-of-K ADE

💡 Analogy:

• Top-1 ADE = "How accurate is your one guess?"
• Best-of-16 ADE = "If you make 16 guesses, how close does your best one get?"

---

Step 7: Results and When to Use This Method

Performance Summary

                    Top-1 ADE (3hr)    Best-of-16 ADE (3hr)
─────────────────────────────────────────────────────────────
TrAISformer (57M)      9.51 km              2.80 km
This method            9.13 km ✓            2.38 km ✓

The non-parametric method wins despite having zero learned parameters.

The Data-Scarce Advantage

This is where the method truly shines:

Training data available:
100% → Both methods perform similarly
 10% → This method: stable | TrAISformer: degrades
  2% → This method: still works | TrAISformer: catastrophic failure

Why? Neural networks need massive data to learn generalizable patterns. This method directly uses whatever data exists — no generalization required.

---

Step 8: Putting It All Together

Here's the complete pipeline:

OFFLINE (one-time setup):
Historical GPS logs → Extract (state, next_position) pairs → Transition Table

ONLINE (at prediction time):
New vessel state
       ↓
Query transition table with product kernel
       ↓
Retrieve weighted similar historical transitions
       ↓
       ├── Beam Search → Single best trajectory
       └── Diversity Sampling → 16 diverse trajectories

---

Summary Table

---

Self-Check Questions

1. Why does multiplying kernel components (rather than adding) make physical sense?
2. What would happen to diversity-penalized sampling if λ = 0?
3. Why does this method outperform the transformer when training data is scarce?
4. A ship is at position X heading north at 10 knots on a Monday morning. Another historical record shows position X heading north at 10 knots on a Saturday morning. Would the product kernel give this a high or low similarity score? Why?
5. When would you prefer beam search over diverse sampling in a real application?