Module 3 Discussion Topics

Strong answers will draw the naturality squares explicitly and verify (or refute) the naturality condition for specific morphisms.

Discussion 1: Polymorphism as Naturality

In Haskell or any parametrically polymorphic language, a function of type forall a. F a -> G a (where F and G are type constructors / functors) is a natural transformation η: F ⟹ G. The theorem that "all parametrically polymorphic functions are natural" is called the free theorem.

• Consider length :: [a] -> Int. What are F and G? Is the output category Set or something else? Draw the naturality square for a specific function f: a → b and verify commutativity.
• Consider reverse :: [a] -> [a]. Same questions. Verify the naturality square.
• Consider head :: [a] -> Maybe a. Same questions. What happens when the list is empty? Does this change whether the function is natural?
• Now consider a non-polymorphic function sort :: [Int] -> [Int]. Why is this NOT a natural transformation? Construct a specific function f and morphism that breaks naturality.

Discussion 2: Equivariance as Naturality

A function f: X → Y between spaces with a group G acting on them is equivariant if f(g · x) = g · f(x) for all g ∈ G, x ∈ X. Equivariance is the condition that "applying the group action commutes with applying the function."

• Write down the naturality square for equivariance. What are the two functors? What is the category C (hint: it is the one-object category corresponding to the group G)? What is the category D?
• A convolutional neural network layer is equivariant to translation. Draw the naturality square for this: what are the two functors (applied to images), what is the morphism f (a translation), and what does naturality say?
• Data augmentation (applying random rotations to training images) is the empirical approximation to encoding rotational equivariance. What is the categorical failure of data augmentation as a method for achieving equivariance? (Hint: what does "approximately natural" mean?)
• A model that is equivariant by construction (via a group-equivariant architecture) versus a model that achieves approximate equivariance via data augmentation — which has smaller hypothesis space? Why?

Discussion 3: What Is a Neural Network as a Functor?

If categories are the correct setting for ML models, then a neural network should be (or approximate) a functor. But between which categories?

• Propose a source category C for a neural network image classifier. What are the objects? What are the morphisms? (Be specific: what structure do you want the morphisms to encode?)
• Propose a target category D. Is it Set? A poset? Something else?
• The network is then a functor F: C → D. What does the functor law F(g ∘ f) = F(g) ∘ F(f) say about the classifier? Is this law satisfied by a typical neural network? Give a specific example of a violation.
• If the functor law is violated, the network is not a true functor — it is an "approximate functor." What would it mean to enforce the functor laws exactly during training? Is this feasible?

Discussion 4: The Three Levels

Category theory operates at three levels simultaneously: objects, morphisms (between objects), and natural transformations (between functors between categories). Each level has a notion of "sameness": isomorphism of objects, natural isomorphism of functors, and equivalence of categories.

• In a database system: what is an isomorphism of tables? What is a natural isomorphism between two database instances? What would an equivalence of database schemas mean?
• In ML: what is an isomorphism of models? (Two models that compute the same function.) What is a natural isomorphism between two families of models parameterized by the same category?
• The Yoneda Lemma (next module) says that the three levels are not independent — the functor level determines the object level. Can you state what this means informally, before seeing the proof?