Monday notes from 8 June 2020

(updated 2020-06-08)

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:

(a) online-go.com — via https

(b) online-go.com — via https

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.

(a) forums.online-go.com — via https

(b) online-go.com — via https

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.

(a) senseis.xmp.net — via https

(b) senseis.xmp.net — via https

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!

(a) senseis.xmp.net — via https

(b) sente.ch — via http

(d) senseis.xmp.net — via https

(e) senseis.xmp.net — via https

(f) hoylesoxford.com — via https

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.

(a) cis.upenn.edu — via https

(b) en.wikibooks.org — via https

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.

(a) learnyouahaskell.com — via http

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.

(a) hackage.haskell.org — via https

(b) wiki.haskell.org — via https

(d) wiki.haskell.org — via https

(e) hackage.haskell.org — via https

(f) hackage.haskell.org — via https

(g) hackage.haskell.org — via https

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.

(a) blog.sigfpe.com — via http

(b) faculty.math.illinois.edu — via https

(d) en.wikibooks.org — via https

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⁽ᶜ⁾.

(a) en.wikipedia.org — via https

(b) cs.cmu.edu — via https

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.

(a) en.wikipedia.org — via https

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) en.wikipedia.org — via https

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.

(a) people.cs.bris.ac.uk — via http

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.

(a) ams.org — via http

(b) doi.org — via https

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.

(a) en.wikipedia.org — via https

(b) en.wikipedia.org — via https

(d) en.wikipedia.org — via https

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.

(a) en.wikipedia.org — via https

(b) doi.org — via https

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 `algebra` and `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.

(a) math.usm.edu — via https

(b) hackage.haskell.org — via https

(d) hackage.haskell.org — via https

(e) hackage.haskell.org — via https

(f) github.com — via https

(g) hackage.haskell.org — via https

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.

(a) hackage.haskell.org — via https

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:

(a) staff.fnwi.uva.nl — via https

(b) staff.fnwi.uva.nl — via https

The purpose of this book is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with computer programming.

and later,

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.

(a) thorne.co.uk — via https

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⁽ᶜ⁾.

(a) soundcloud.com — via https

(b) someplacenice.co.uk — via https

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⁽ᵇ⁾.

(a) bfi.org.uk — via https

(b) lynchnet.com — via http

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!

(a) twitter.com — via https

(b) a24films.com — via https

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!)

▣

You are here: