Monday notes from 8 June 2020
It's a bit of a long one this week. I think I've just had a lot of coffee!
Go. I had my second 13×13 go game over the course of the last week. Like no other game I've played, go has this property of unfolding itself to you as you play, and each game is an education. Compared to my first 13×13 game, the main lessons — whether from mistakes or from successes — were:
- to try to determine whether a group is dead, and if so, start playing elsewhere instead of continuing to surround it;
- to not be intimidated by stronger players, and not rely on them to explain every move;
- the importance of wall-building, connectedness and territory;
- how the game changes at the edge or the corners;
- sacrificing groups in order to make more valuable moves elsewhere.
I am improving at reading ahead, especially when using the analyser. Doing so seems to reveal small patterns and move sequences that act as little lessons. Chris is open to undoing moves if we would learn something from the undoing, and we've now rewound and started playing a fork of the second game from a critical point.
Given these lessons, the next goal for me is to learn a few of the basic eye shapes. There are a few hundred strong eye shapes, but at my level, apparently, the basic five will make a big difference.
I've also tried to get my nephew into go by introducing him to atari go via the Goban app on my computer. He internalised and applied the basic rules within minutes, doing well in a game or two of atari go on a 7×7 board, but after I called it 'the board game' (a paraphrasing of BoardSpace's opinion), he declared it 'the worst board game... with pebbles'. I still have a bit of work to get him into it. I have ordered an simple go set from Hoyle's, since I think maybe it'll be more enjoyable to play away from the computer. We'll see — I won't give up!
Haskell. My simple GPS trails app is plodding along. I'm not really adding much in the way of features, more that I'm trying to prune and tweak the code — AST topiary — to make it more concise and functional. As an erstwhile Prolog guy, I'm used to recursion, but converting things to folds where possible really made things look nice.
I wanted to go somewhere else with my Haskell, though, and on Sunday afternoon I started experimenting with algebra in Haskell. I'd enjoyed learning about structures like monoids, and I wanted to see how some other algebraic structures could be defined and implemented.
The Haskell Prelude is a module which contains the basic, standard definitions. They are seen by many as not ideal for working with abstract structures. It's imported by default, but fortunately you can disable that and use your own Prelude — your own custom Prelude to suit your application and your philosophy on the structure of types within it. Numeric Prelude provided a re-orientation toward abstract structures, in the words of its package description, 'an experimental alternative hierarchy of numeric type classes'. Algebraic Prelude is another drop-in replacement for Prelude based based on the algebraic hierarchy provided by the
algebra package for constructive abstract algebra.
More generally, Haskell is sometimes recommended for mathematical work, or at least for mathematicians, even though purpose-built languages like Macaulay2 are out there. And functional programming is most often connected with logic — not least because of the Curry-Howard isomorphism — and category theory, but I'm more talking about using Haskell to explore mathematics, rather than using mathematics to understand Haskell. So it's time for another project.
Machine learning. I think I should start with something simple and familiar, so I'm going to try to code up, in a general way, a version space learner, a concept learner. It's a binary classifier, that is, a learner that decides whether an instance is to be labelled as one thing or the other. This kind of learning was the first topic in the first textbook we studied in my machine learning MSc course twenty years ago! It's summarised well in the slides for that chapter.
So, a quick overview of the ideas:
- When we're doing classifier learning, we're learning something from a set of observations or instances. A concept is just a subset of the set of these instances. We know the set of subsets of a set — its power set — form a lattice when the power set is equipped with the containment relation ⊆. In the world of concepts, the subset and superset relations mean specialisation and generalisation respectively. By taking subsets of the instance set, we're getting more specific about a concept covers, and by taking supersets, we're getting more general.
- When we do inductive machine learning, we want to get a general rule from a set of observations, so, rather than learning the subset itself, we want to get a description — or hypothesis — of the set in some logical language. That is, a logical sentence. That description then characterises the subset of the instance set — the observations for which the description is true. Say, for example, we have information about the weather on each day in April and information about whether Alice decided to play tennis that day. An inductive machine learning task of this kind would try to find a general rule for the weather conditions in which Alice decided to play tennis, for example, 'Alice plays tennis when it is not raining'. Here, 'not raining' is a concept description, describing all the days on which there was no rain.
- A version space is the set of all concept descriptions consistent with the observations. They are ordered by generality too — some of the descriptions can be said to be more general then others. That is, you can take some pairs of descriptions and one description in the pair describes a superset of the instances that the other one in the pair does. An example (from Tim) is that all ducks are also birds, and the description 'is a bird' is a more general thing to say about an animal than the description 'is a duck'. We can also say 'is a duck' is more specific than 'is a bird'. When you learn with a version space, you start with your lattice of concept descriptions structured by this generality, and narrow down the set as you go.
- There might be a huge number of concept descriptions, especially if we haven't been selective in the ones we want to search among! There's a trick, though. We don't need to explicitly keep track of every concept description, because of the magic of lattices. We just need to track the concepts which are the most general concepts of the version space, and the most specific. These form two boundaries, demarking the limits of the version space on the lattice. Everything between the boundaries is in the version space. With this established, you can apply, for example, the candidate elimination algorithm to find the descriptions consistent with the observations.
The logical language in the most basic implementation of all this would be just propositional. That is, the examples are just yes/no values describing aspects of the weather (sunny? rainy? snowing?). However, you could use any suitable logical language, as long as you could decide generality between the descriptions. Inductive logic programming, one of the focuses of my PhD thesis, commonly uses first-order Horn clauses instead.
Learning in this way isn't exactly popular, and one reason for that is that version space learning doesn't handle noise. It fits the data perfectly, and that means encountering any two examples which are inconsistent just result in an empty version space. From there you can't really learn anything! Although this learning strategy has been generalised to noisy data, the setting I lay out above is far too limited to be useful for real-world learning. But, it's a start.
So, coming back to my Haskell mini-project, I'm going to be basically playing with lattices or partially ordered sets at one level, and propositional and perhaps other logics at another. Lattices are modelled by the
Algebra.Lattice module inside Numeric Prelude, but, playing around a bit, it seems that the
Ord class is the only way of representing an order, and it must be total.
algebra supports partial orders, but there's a purpose-built
lattices package which looks more fine-grained and useful for this application. I plan to try both
lattices, just to get a feel for things. The basic mechanics of the logic can be handled by, for example,
logic-classes, though I could just code up the propositional case myself. If I can keep the two layers separate I might be able to do some cool tricks.
And, as you'd expect, all this has been done already in
AI.VersionSpaces, so none of this is remotely ground-breaking except for me. But I hope it'll serve as a familiar place from which to explore working with algebraic structures with Haskell, from which I can head out into less familiar territory.
To support this interest in maths and logic with Haskell, I'm also going to try to read at least a couple of chapters of The Haskell Road to Logic, Maths and Programming by Jan van Eijck and Kees Doets. In the preface it states:
The purpose of this book is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with computer programming.
The subject of this book is the use of logic in practice, more in particular the use of logic in reasoning about programming tasks. Logic is not taught here as a mathematical discipline per se, but as an aid in the understanding and construction of proofs, and as a tool for reasoning about formal objects like numbers, lists, trees, formulas, and so on. As we go along, we will introduce the concepts and tools that form the set-theoretic basis of mathematics, and demonstrate the role of these concepts and tools in implementations. These implementations can be thought of as representations of the mathematical concepts.
This sounds ideal.
Beekeeping. I've been looking after my nephew on some of the afternoons this week, too. We've slowly been working our way through building a Bees on a Budget hive for the next swarm. It may require only a basic level of carpentry to assemble one of these, but it's good practice for both me and him.
We hope it'll be put in the apiary early this week, or later this week if we opt to stain it.
Screen time. The pandemic lockdown is still mostly in force in England, and is even stricter in the other countries of the United Kingdom. Since its sixth day, a few friends (initially me, Holly and Red) have been holding a virtual cinema.
Using streaming services synchronised by a countdown, we'll watch one or two films a week, with a beer or wine in one hand and in the other, a device connected to our chatroom. The films have so far formed thematic triples (or quadruples): folk horror, neon noir, gems of the Hollywood left, or Lynch.
So far we've watched a dozen films, but by far the favourites have been those by Ari Aster. We are all fans of horror, and for us, these were absolute cinematic nightmares. So far Aster has made two feature-length films, Hereditary (2018) and Midsommar (2019). Both are beautifully paced, shot and performed. Neither gives away everything on the first viewing, but enough to creep you out, so you won't necessarily want to watch either again right away!
When the lockdown began, we half-joked that we'd like to put on a folk horror film festival in an old creepy country pub somewhere in the middle of nowhere. I hope we do that.
(I updated some of the explanations in this note thanks to some feedback from Tim — thanks, Tim!)