Categories for AI 2: Essential building blocks: Categories and Functors - Petar Veličković

Motivated by the recent emergence of category theory in machine learning, we teach a course on its philosophy, applications and outlook from the perspective of machine learning!
Sign up for the course at: cats.for.ai/
In the second seminar, you will:
Understand the key building blocks of categories: objects, morphisms and functors.
Leverage these concepts to explain several standard mathematical constructs: sets, relations, and groups.
Get comfortable manipulating these concepts through several worked exercises.
Ground all of the above in relevant deep learning context, with links to functional programming.
Show how we can build an effective "type checker" for deep learning using the category of sets.
These lectures will help explain key parts of Graph Neural Networks are Dynamic Programmers (NeurIPS 2022) arxiv.org/abs/...

[@mikejennings3921]

Thanks Petar, I found this a really clear exposition of the core elements of category theory. I understood more from your lecture than I have from many hours of other online material. Well done. I think it is because you rooted in concrete examples and application which clicked for me, even if my AI familiarity is quite basic.

[@NoNTr1v1aL]

Absolutely brilliant introduction to Category Theory!

[@kevon217]

excellent lecture.!

[@simonahrendt9069]

28:00 As a theologian (as well as deep learning enthusiast), the terminal set seems to me to be analogous to the concept of (monotheistic) "God". And it is fascinating that the terminal set can be identified simply in virtue of all arrows pointing to it, without knowing the "nature" of the objects/sets - i.e. in particular, without knowing the "nature of the One". This is a line of thought that definitely bears fruit theologically, when you consider the claim that all manifestation in the world points to God himself (and indeed, that God is exactly He who all manifestation points to). It is also interesting that the different pagan cultures of the past, once they converted to (monotheistic) Christianity, they provided connections to elements of or figures in scripture, e.g. connecting the ancestry of their traditional gods to some specific, lesser known descendant of Noah. This way it seems they provided arrows into the framework of references (in language) that themselves were understood to point to "God", i.e. to biblical scriptures or associated traditions. When you think about it, if compositionality holds in the realm of language/thought, then in virtue of connecting one's culture to an aspect of the story that explicitly contains (or rather points to) "God", one is simultanously providing the composition, i.e. an arrow from one's culture to "God". The desire to do this underlines the notion that (at least for these ancient people, but definitely still today with regard to people who take the concept of "God" serious in either a philosophically or religious way) this concept "God" was seen to serve a role similar to the notion of "terminal set"/"top" or whatever the more general category-theoretical term is (limit?). Also wondering whether the claim that Christ is "alpha and omega" and that the "first shall be last" point to some sort of mathematical structure in which "top" and "bottom" (or "limit" and "colimit"?) are in some sense indistinguishable from one another. Just recording my thoughts here for future reference. But maybe I am not the only one interested in rather arcane topics, considering the topic of this lecture series :D

[@JTan-fq6vy]

15:10 we are talking about commutative diagram, but I was not convinced by the name "commutative". Does the "commutative" have anything to do with the "commutative property" in abstract algebra? If not, what exactly is the meaning of "commutative" in this context regarding the diagram?

[@JTan-fq6vy]

In time 26:44, it was mentioned that there is only one morphism uniquely defined from any set A to (), ie., the function returning () for every element in A. However, could it be possible that for some of the elements in A, there is no return, ie., no arrows from some of the elements to ()? In this way, it seems the morphism (function) is not unique and there can be many different ones.

[@quonxinquonyi8570]

If there is no return for some of elements of A then it will not be a function to start with….in order to be function the whole domain of A must be mapped

[@stayinthepursuit8427]

Sorry am just a beginner, but at 35:08 when we say number of functions between two sets A and B , we specifically mean from A to B , and not the other way around right? Cause the other way would have a cardinality |A|^^|B|

[@petarvelickovic6033]

This is correct, and a slight lapse of language on my side. Indeed, we specifically mean "from A to B" in this case :)

[@devon9374]

Great lecture

[@alexanderlim4586]

Thanks Petar for the amazing intro!. At time 49:10, how can we tell, from the commutative diagram, that f is both monomorphic and epimorphic? Is f being so by stipulation? Or we can read off from the diagram directly?

[@alexanderlim4586]

This is my attempt to show f being epimorphic: From the axioms of categories, we have id_B o f = f, which is also f = id_B o f. So, id_B o f = id_B o f. Since id_B = id_B, f satisfies being an epimorphic. But, I believe, this argument can be applied to any morphism in any categories. This makes any morphism epimorphic.

[@vinhchucky]

@alexanderlim4586 in that specific category the only morphisms than be composed on either side of f are the identities So the properties of mono and epimorphism are trivially verified (it's a bit absurd in a way) f o g = f o h always implies g = h because g = h = id you have no other choice there no other morphisms

[@HelloWorld-qs1du]

Hi Petar, great lecture. I have a question about the "type checking" GNN example. I understand it doesn't type check because V^2 is send to two output, but it will type check if the output is written as a product (V x V^2) instead of disjoint union (V+V^2). Also as you pointed out, it will type check using REL instead of Set, then I'm confused how category theory is helping in this example

[@petarvelickovic6033]

Thank you! To explain why the points you raised would still be an issue, note the following: * The size of tensors backed by (V x V^2) vs. (V + V^2). For a graph with n nodes, the first object has n^3 slots, the other has n + n^2. Clearly, the first output is much worse to support from a memory perspective. * If we assume that deep learning implements functional programming (which many recent frameworks, like JAX, embody!), then it is most natural to assume that transformations in deep learning are _functions_, and not relations. As I discuss in the lecture, the fact that we cannot make it work with functions implies that there is "representational pressure" on the message vectors to be used for two potentially wildly different purposes. I hope this is potentially of use! Happy to discuss further if you would like.

[@ハェフィシェフ]

Hi! I love your series but I don't know how to access the zulip page can you share the link?

[@AyanDasACDee]

Hi, how do i register for the course now, it's not showing on the website

[@rylaczero3740]

Instead of naming them 'Chapter X', can you them such that they convey more information about the content the specific segment cover.

[@simonahrendt9069]

36:03 Perfect, creatio ex nihilo now^^

[@miregal-xj5xv]

I am trying to understand precisely what you mean by "the unit set" and "the terminal object" wrt. to Set. So, I understand that for Set we happen to have a single "initial set", as per the lecture - the empty set. I also understand that a certain set (containing only a certain element) is uniquely defined by a single morphism. But clearly there are many such "unit" sets, and many such morphisms. However, you speak consistently as if there is a single terminal object for Set. Can you explain the level of abstraction here? Is "the" "terminal object" in Set an abstract object that stands for ALL sets with a single object, and they share properties such as having each a single morphism defining them... or are we in fact speaking about a collection of terminal objects, each with a specific morphism defining them? The former would work with the language of "up to isomorphism" perhaps.

[@petarvelickovic6033]

Thanks for your question! Strictly speaking, as you said, in a category like Set there are infinitely many terminal objects (namely, all single-element sets). However, it is a general assumption in CT that, for all intents and purposes, we can assume we know the terminal object "up to isomorphism"; put differently, for any two terminal objects, we are guaranteed an isomorphism between them, so, at least from the point of view of mathematical structure, we can assume them to be the same object.

[@0Tsutsumi0]

Great content! :)