Category: Logic

The lecturers and demonstrators for the Logic and Applications course held a ‘coursework catch-up’ today, the idea being that we can see where we went wrong in the assessed coursework pieces we submitted.

I think a big thank-you is warranted to the demonstrators on the course, Adam and Mohammad. These guys have been really helpful over e-mail as I’ve been doing the coursework pieces at home. It’s a little tricky because they can’t answer questions that are too open, nor can they confirm whether an answer is right or wrong. What seems to have worked this time is asking whether a coursework answer suggests that I’ve understood a specific concept.

I could have understood it and still made some small error and so got the answer wrong, so there’s no big reveal about what the answer is. The couple of times where there was a problem with my understanding, the demonstrators could just suggest that I review the relevant concept. Lots of thanks to those guys anyway for their patience and help!

After reviewing my marked coursework, I found that where I’ve lost marks it’s because of nothing more serious than typos which is nice to know. Now the revision process starts and there’s plenty to chew on with this one!

I normally manage to get a post out each day I’m studying a module, but I’ve really struggled for time this time round. I’ve had a few items in my personal calendar that I didn’t want to miss, but over and above that the workload on this module is pretty intense.

There’s a coursework assignment each week, which constitutes a whole lot of work, but I’ve also chosen to switch from handwritten assignments to preparing my work in LaTeX. It’s made me pretty uncomfortable preparing extensive handwritten documents (on the order of 6-12 pages) for a few reasons. A mistake I make could involve wasting a lot of time re-writing a document, backing up a paper document regularly kinda doesn’t work, and handing in paper documents involves either physical locality or the good old Royal Mail. An electronic version has none of these drawbacks.

On the other hand, preparing this kind of material electronically is non-trivial, as there’s a lot of odd tabular layouts and logic formulae involved. I discounted anything other than LaTeX out of hand, as word processors aren’t really designed for that kind of material. Preparing this stuff electronically is more time consuming initially, but I console myself with the thought that I can correct a mistake very easily!

Anyway, Logic and Applications. We covered the relatively simple Propositional Logic in the first two weeks, and moved onto First Order Logic in weeks three and four, on into week five. So far, the idea seems to be to encode knowledge and deduce from that knowledge more information using rules that can be proven to derive correct conclusions.

Why different types of logic? Propositional logic is simplest, has certain helpful properties as a result, and has limitations you run into pretty quickly .

For example, in Propositional logic, we can encode explicit facts, like “Paul’s Mother is Helen” and “Helen is Female” and work with those facts, but we can’t generalise from there. For example, we can’t add “Jo’s Mother is Sylvia” to our system and deduce that Sylvia is female. To do that would require an ability to say something like “Mothers are Female”. We can’t do that without variables and quantifiers, so we need something more expressive. First Order logic gives us that additional expressivity, for the price of it being more difficult to learn and understand, and being undecidable. That last bit means that in general, no algorithm exists that can be guaranteed to give a yes or no answer as to the truth of a formula expressed in First Order Logic in a finite amount of time.

So, lots of fun to be had with proofs, algorithms and understanding some really abstract stuff!

It’s the start of year three, and I visited UoM last Friday to got through my options and choices for what will almost certainly be the most important year of my MSc.

As usual, I need to choose taught modules. I need to get at least two done, but three would wrap up the taught part of the course completely, which would be a great place to be at the end of the year. I’m going for a bit of an AI flourish to finish with “Logic and Applications” to start in September, followed by “Ontology Engineering for the Semantic Web” Starting November, with a gap in March and then potentially “Text Mining” in April.

I also need to choose a final project, which I’ll need to complete over the course of a year, do some original work in the field of Computer Science and produce a dissertation on the order of 60-100 pages. The big question is do I want to put forward a project of my own devising, or take one that has been proposed by the CS School or a company? In order to complete this part of the course (which counts 50% of the final grade), I need to complete a further special module called “Research Skills and Professional Issues” which runs between November and March. It’s a big decision on a piece of work that’ll sink a huge chunk of my time over the next two years, so I’ll be getting in touch with the project organiser to help me evaluate my choices. One way or another though, it needs to start this year to be do-able in the remaining time.

So there’s a lot of stuff to do – and to pay for. I hadn’t thought about it, but this setup essentially means that I’ll be paying for the remainder of the course this year – well, pretty much now – which is just over £3,000. Ouch!

So anyway, whilst all that’s going on, the first module has started – Logic and Applications. This is a new module this year which seems to have at least partially replaced the Knowledge Representation and Reasoning course that I naively attempted back in 2008… having not fully understood the pre-requisites, I crashed and burned hard and ended up dropping it, as a result achieving nothing for the whole first half of my first year.

This time, the course doesn’t have any pre-reqs, but I’ve spent the last couple of months reading up on Propositional Logic, Resolution, Theorem Provers and First Order Logic, and last week implemented a satisfiability checking algorithm called DPLL and an implementation of a logic-based game called Hunt The Wumpus (specifically because there’s great reference material in AIMA to check my approach) to prove to myself that I understood the concepts. As a result, it looks like I’m pretty much covered up to at least week/day three, which is a good thing.

So, Logic and Applications Day 1 – propositional logic, set theory, mathematical proofs and satisfiability went pretty well. It introduced a couple of gaps in my knowledge, more on the mathematics side of things – what is a reflexive-transitive closure and how would I create and use one, for example. Now to get the week one coursework done… after all, the weekly coursework counts 50% of the marks for this module.

As an aside, the Blackboard system that we used in the first SSD&X module hasn’t resurfaced in any other modules so far. In fact, the preferred method for submission based on my experience is…. wait for it… paper. It’s a bit odd, having spent the last ten years passing papers and documents around pretty much exclusively in a digital medium.

I can sort of see why for this module, at least – the mathematical content means that there’s a lot of symbolic stuff going on, and they’re testing the ability to do the maths, not use tools like LaTeX. That said, those tools seem to be essential for anyone working in CS, so maybe you could make the case that all the CS modules should teach and promote their use.

It will present me with a problem, as it always does. There will be a coursework set in the last lecture day to be handed in during reading week, and I’m not taking time off work to get over to Manchester purely to hand in a piece of paper.

It’s that time again.

The results came in for last year and everything’s comfortably over the 70% mark so it’s past time to get cracking on module choices and learning ready for year three. It seems like it was a very long time ago that I applied to Manchester!

So to recap, so far I’ve studied “XML and Semi-Structured Data”, “Machine Learning” and “Patterns for e-Business Applications”. Has what I learnt come in useful yet? I can honestly say that it has.

The deep dive on XML comes in useful as I now have a fair idea of the toolkit available to me for XML processing and I have an idea as to why XML is constrained in the ways that it is. Knowing the basics of some common XML formats like RDF and RSS also comes in pretty handy when the topic comes up.

Learning about machine learning blew my fragile little mind. I have to admit right now that I haven’t actually used what I learnt here yet – I think it’s quite specialist and you’re either exposed to it or you’re not. Maybe my future plans will take me more into this kind of technology. The possibilities certainly seem endless!

Even just knowing about IBM’s patterns for e-business is helpful in that I now know of a new set of resources and I can put names to some of the patterns I’ve used before now.

So, looking forward. What am I considering this year?

Well, for a start it’s rematch time. The first module I tried (and failed) to take was called Knowledge Representation and Reasoning. I found that I didn’t understand the pre-requisites (in particular First Order Logic) and so was unprepared for the material. This year I plan on taking Logic and Applications, and I’ve been studying here and there for the past couple of months. I’ve gone so far as to write a satisfiability checker using the DPLL algorithm. It even works!

I’d also like to take Ontologies and OWL. Ontologies are a way of representing knowledge and relationships, allowing computers to reason about things and OWL is a language for defining ontologies. It’s an intersection between the semi-structured data stuff and logic. To do the pair would need me to take two consecutive modules and exams between October and January which would be pretty tough going… we’ll see.

That would be five of six modules. I wish there was a module teaching the principles behind functional programming… but there is not. There is mention of a Natural Language Processing in the course modules which for some reason sparked my curiosity, but there’s no details as to the content or when it will be taught so we’ll have to wait and see on that one.