Logic and Applications – Tough Exam!

I took the Logic and Applications exam last Friday. I think I’m ready now to talk about the ordeal…

It wasn’t so bad really, I guess. I made a bad call as to which questions to answer (it was one of those answer three of four kind-of-things) and ran out of time. One of the questions I initially chose had what was for me a brick wall towards the midway point, and on a two hour exam, spending 20-25 mins heading down a dead end isn’t the best idea!

I guess the two frustrations I felt with this exam were firstly that the course covered so much material so quickly, but each of the topics turned out to be a bit of a rabbit-hole when I got to thinking about it during the revision process – the more I thought about it, the more questions I found!

On top of that, one of the key aspects of a course like this is transformation of formulae into alternative forms which have properties we want – usually, more efficient solving algorithms. These transformations are rather like the algebraic manipulation of mathematical formulae we did at school – progressing in unit steps, painstakingly copying out each new form as you go. That consumes a lot of time, especially when the formulae don’t give out easily, but it doesn’t really seem to prove much about the student’s skills – the pages-of-transforms kind of work was all hammered pretty hard in the coursework, after all. Then again, maybe I just screwed something up early doors and that led to the extensive transform.

The course was new this year anyway, so maybe it takes a little time for the exams to settle in terms of difficulty. Or I’m just a dumbass. Anyway, it’s too late to worry about all that now. Hopefully, I passed – that’s the main thing, right?


Preparing for the Logic and Applications Exam

It feels like a long time between finishing the Logic and Applications course back in early November and the exam, which is next week on the 27th January. In between, I’ve done a little work on my project proposal in the meantime, but certainly since late December I’ve been focussing more on preparing for the exam.

It’s always a bit surprising when I start revising how much stuff we covered in a five-week course and this one was no exception. The syllabus is here on the UoM CS website. It’s also a new course this year, so there aren’t any specific past papers (exam papers from previous years) to get a feel for how the exam will be phrased and what kind of content has been examined before.

The nearest course in previous years was the Automated Reasoning course, which covered similar stuff but also included some aspects of logic programming in Prolog. In this course we used theorem provers SPASS and MiniSAT for the small amount of experimental work involved. Hopefully there won’t be any ‘remember-the-syntax’ style questions…

Logic and Applications Coursework Catch-Up

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!

Logic and Applications Day 5

So I’ve finished the Logic and Applications module now – the last coursework has been submitted and I’ve been enjoying a couple of days of doing things other than schoolwork!

The course was very focused on satisfiability – given a set of logical statements, is it possible to find an interpretation, a set of assignments for the logical statements, that satisfies them? That might not sound particularly useful, but it’s easy to express a question about a system this way.

As an example, consider the Minesweeper game. (Sorry if you’ve not come across this game before, check out the Wikipedia page for an example if so) Initially, we know very little and what we do know isn’t directly useful – how many squares there are. Once we’ve tried a couple of random clicks, we have some information we can use and express in these logics.

Perhaps we know that the square at 7 across and 12 up contains a mine and that the square at 8 across and 12 up has one adjacent mine. The question we might ask is whether 8,12 contains a mine and this is where satisfiability comes into play. Given logical statements encoding the rules of minesweeper, and the two details we mentioned specific to this game, is it possible that 8,12 contains a mine?

In other words, is the set of logical statements describing the rules, this game (to this point) and a statement expressing that 8,12 contains a mine satisfiable? The answer of course is easy for human to figure out.

The ability to automate the search for satisfiability allows these kinds of problems to be solved quickly and accurately using tried and tested reasoning tools. The general approach we used on the course was to search for a satisfying interpretation, which quickly leads to a problem – combinatorial explosion. The number of possible interpretations of a set of logical statements grows exponentially as the number of logical variables grows.

As such, a big focus on the course was algorithms and approaches to battle this exponential complexity – there are many techniques to reduce the space of possible interpretations and bring the complexity problem under control. That said, one of the impressions I come away with is that for a given problem no generalized technique will be able to guarantee to determine satisfiability in a reasonable time.

A final point, and an important one, is that the techniques we used were based almost entirely on mathematical proofs, that is to say that we are able to deduce that the techniques are correct and have certain other properties using formal methods. Of course, mathematical proof is formed by logical deduction too, so there’s a certain recursive nature to all this.

It’ll be good to get started on a fairly relaxed process of revision for all this stuff. The sheer volume of information thrown at us on these modules is huge, and it always feels a little like riding a rollercoaster, so it’s good to get back in there and review the material at a more relaxed pace.

Logic and Applications Days 2-4

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!

Logic and Applications Day 1

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.

Getting Ready for Year 3 2010-11

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.

Logic for Dummies – Part 1

It seems like one of the things I really have to get my head round if I want to understand some of the principles of computer science is logic. Now, I figured that would be easy. I mean, I can remember truth tables for AND, OR, NOT, NOR, NAND, etc. from school, so how hard can it be?

Yup, how hard can it be – the classic sign of someone who doesn’t know enough about the problem to know that they don’t know enough about the problem. Continue reading “Logic for Dummies – Part 1”