Computation Graph

Computation Graph (Optional)

Optional Content

Introduction to Computation Graphs

• Computation graphs are a key idea in deep learning
• They explain how frameworks like TensorFlow automatically compute derivatives
• Enable efficient backpropagation for neural networks

Note

A computation graph breaks down complex calculations into smaller steps, making it easier to compute derivatives through backpropagation.

Example: Simple Neural Network

Simplified Model

• One-layer neural network with a single output unit
• Linear activation function: a = wx + b
• Cost function: J = 1/2(a - y)²
• Single training example: x = -2, y = 2
• Parameters: w = 2, b = 8

Forward Propagation with Computation Graph

1. Compute w × x = c

• w = 2, x = -2
• c = -4

2. Compute a = wx + b = c + b

• c = -4, b = 8
• a = 4

3. Compute a - y = d

• a = 4, y = 2
• d = 2

4. Compute J = 1/2(a-y)² = 1/2d²

• d = 2
• J = 2

Tip

The computation graph represents forward propagation as a left-to-right calculation, breaking the complex function into simple operations at each node.

Backward Propagation (Backprop)

Right-to-Left Calculation

• While forward prop moves left-to-right, backprop moves right-to-left
• Computes derivatives by asking: “If input to this node changes by ε, how much does J change?”

Computing Derivatives Step-by-Step:

1. Derivative of J with respect to d:

• If d increases from 2 to 2.001, J increases from 2 to 2.002
• J increases by ~2 × ε
• ∂J/∂d = 2

2. Derivative of J with respect to a:

• If a increases by ε, d increases by ε (since d = a - y)
• We know when d increases by ε, J increases by 2 × ε
• Therefore, when a increases by ε, J increases by 2 × ε
• ∂J/∂a = 2

3. Derivative of J with respect to c:

• If c increases by ε, a increases by ε (since a = c + b)
• We know when a increases by ε, J increases by 2 × ε
• Therefore, when c increases by ε, J increases by 2 × ε
• ∂J/∂c = 2

4. Derivative of J with respect to b:

• If b increases by ε, a increases by ε (since a = c + b)
• We know when a increases by ε, J increases by 2 × ε
• Therefore, when b increases by ε, J increases by 2 × ε
• ∂J/∂b = 2

5. Derivative of J with respect to w:

• If w increases by ε, c changes by x × ε = -2 × ε (decreases)
• We know when c increases by -2 × ε, J changes by 2 × (-2 × ε) = -4 × ε
• Therefore, when w increases by ε, J changes by -4 × ε
• ∂J/∂w = -4

Note

For readers familiar with calculus: These calculations utilize the chain rule, where ∂J/∂w = (∂c/∂w) × (∂J/∂c). Don’t worry if you’re not familiar with the chain rule - the step-by-step reasoning achieves the same result.

Verification of Results

• We can verify our derivative calculations:
• If w increases from 2 to 2.001, J decreases from 2 to ~1.996
• J decreases by ~0.004 (4 × 0.001)
• Confirms ∂J/∂w = -4

Tip

You can pause and verify the derivatives yourself by calculating what happens when b increases by ε. You should find that ∂J/∂b = 2 as calculated.

Efficiency of Backpropagation

Computational Advantage

• Backprop is sequenced right-to-left for computational efficiency
• Each derivative calculation reuses previously computed derivatives
• For a computation graph with n nodes and p parameters:
• Backprop computes all derivatives in roughly O(n+p) steps
• Naive approach would require O(n×p) steps

Caution

For modern neural networks with thousands of nodes and millions of parameters, this efficiency is crucial. A network with 10,000 nodes and 100,000 parameters would require ~110,000 steps with backprop versus 1 billion steps with a naive approach.

Key Takeaways

• Computation graphs break down complex calculations into simple operations
• Forward propagation is a left-to-right calculation through the graph
• Backpropagation is a right-to-left calculation that efficiently computes derivatives
• This approach enables training of large neural networks with millions of parameters

Note

In the next video, we’ll apply these computation graph concepts to a larger neural network to see how backpropagation works in more realistic settings.

Computation graphs provide the foundation for how neural networks learn through efficient derivative calculations. By breaking complex functions into small, manageable operations and computing derivatives in reverse order, backpropagation enables the training of large networks that would otherwise be computationally infeasible.