'D' is for Darn it, I have to write a blog entry!

eheh, eheh, eheh!

So, eek! Fifteen minutes left to today, and I have yet to complete my entry on 'D' is for dependent types.

*sigh*

SO, 'D' is now for 'Darn it, I have to write a blog entry!'

AND, since this is a math blog, I darn well tootin' better write some math in it.

Well:

1 + 1 = 2.

And, okay, here's a taste of dependent types.

Types tell us what kind of objects are in that set of like-things.

The type, or class, of chickens in the coop lay eggs.

But dependent types go one further: the type depends on the thing it describes.

So the dependent type of even-numbered things are the sets of things that only have even numbers of things in them. How do we know the type? The type depends on the things. How do we know the things? The things are described by the type.

What do dependent types give us, beside circularity?

Clarity.

If I know I have an even number of things I'm working with, I don't need to as is_even. Or if I do, I know my answer, from the type itself.

For the type of even-numbered things, is_even always is true and is_odd is always false.

So, one thing I don't need to do is to check what I'm working with, or how many I have, odd or even, because I already know from the type itself.

Dependent types are from a new kind of logic called intuitionistic logic developed by Per Martin-Löf. The math for it is rather heady, and using dependent types in programming is 'harder' at the get-go than using ordinary types, but, being very restrictive, they also give a much stronger correlation between knowing that your program is correct: that it's doing what it's supposed to be doing, or what you want it to be doing, and, with dependent types, I find I am able to express things, correctly and safely that I am not able to do (correctly and safely) using ordinary types.

...

My working draft for this blog entry had started out as follows:

'D' is for Dependent Type

We're all familiar with types, right? They're classes, or classifiers, telling us what something in (into which class it belongs).  One example is this weekend I'm going to be running a 5k with my family, which is a very different thing than running a 5 miler or running just 5 feet. Kilometers, miles, feet, these are units of measure, and they type or classify what we're talking about. 'Units of measure,' also, in fact, is a type, so the types 'kilometers,' 'miles' and 'feet' all fall into the type 'units of measure.' Just like our pets are a type of animal: cats. 'Cats' is a type, and itself is a type of something else: 'animal,' or 'pet,' ... depending.

Programming with types is an on-again off-again kind of thing, some programming languages require all things/objects to be typed, some languages require none to be typed and some fall in the middle somewhere between those extremes.

And, as you may guess, different programming languages have different kinds of types or different ways of typing things or different ways of creating types.

What do types give you?

Some say they give you a pain in the ... neck, and nothing more; others say that, by putting things into categories, they provide a distinction of objects operated on, so you know what you can do, and can't do, with the object at hand, simplifying the programming task.

Me, I'm a typeful person, if you hadn't surmised this from the title of the blog which contains this entry. Types are wonderful! They provide a way for me to declare what things are, and, from simply knowing the types of the data I'm working with, I now know a lot about the system and what it does and what its usefulness is.

'C' is for continuation-function

Today, let's look at the continuation-function.

Now, here is an interesting bird, if there ever was one.

And there is, and it's call the continuation-function. So there!

First of all, let's define what a function does. A function is simply an arrow that points from one thing to another.

Let's tighten that up, a bit.

A function from A -> B maps a value in the A-category to the B-category, and, in some cases, the B-category doesn't even have to be a different category. For example, the successor function maps a integer value to an integer value:

succ 5 = 6

succ 41 = 42

etc.

But a function can map from one type to another type:

number_of_letters "foo" = 3

number_of_letters "bar" = 3

number_of_letters "food" = 4

etc.

So, let's talk about the 'types' of the functions as things unto themselves.

So, succ is a function that maps integers to integers, e.g.: 5 -> 6 and 41 -> 42, etc, and we show this mapping of types thus:

succ :: Integer -> Integer

And number_of_letters maps strings to integers, and so we represent that as:

number_of_letters :: String -> Integer

Now there are generalization of functions. We can say, for example, that we have a function, f, that takes an object of type a and maps that object to a different kind of object of type b. We show this representation thusly:

f :: a -> b

We don't specify the types when we declare the function here, the definition of the function may flesh that out, or, when we actually come down to applying the function to an actual object, then the object will specify the input type and the actual result of the function will specify the output.

This generalization or abstraction is a very powerful tool in the right hands.

And even in the wrong hands.

For it allows us to express truths of objects regardless of what kind of object they are: you can express universal truths in mathematics. Or, you can even, if you wish, partially constrain the types of the objects, and therefore express more specific, or more existential, truths, and there are various ways of going about doing that.

(This type-constraining may or may not be the subject of some future entry. Type-constraints are not the point of this entry.)

(So I do not digress. In this case.)

(Or I do digress, in that I am stating I'm not digressing.)

(As always.)

So, some functions operate with specific kinds of objects (and are not of general interest here) and some functions operate with universals.

Now, there are special kinds of functions that, simply by their types, their declarations, express a truth. The truth-expressing function we'll examine here is the continuation-function.

The continuation function's type is as follows:

c :: (p -> r) -> r

What is this type declaration? And what does it declare, actually?

The type declaration says this:

Given that I'm operating with an object that, itself, is a function from p -> r, I give an r result.

This sounds something like a syllogism (you can look that up if you're a bit rusty on syllogisms), and that's what it is, but it's also rather (or very) reductionist.

In other words it says: If I'm given something that proves r from a given p, then I can prove (or provide you) r.

But wait!

No, really: wait. You're saying I give you p proves r and you'll give me r? What's the point?

Actually, there is not, from proof theory. If you already have p -> r then you also have r, too, don't you?

Yes.

The kicker is this: in certain domains.

Because, what if I give you a function p -> r but p is false? Well then p -> r gives you nothing, nada, zip, zitch! So you can just take your r and ...

Well, you may not even have an r in that case, anyway, so the rest of my statement can remain unsaid.

So in the domain where there is no 'false' or no negation, the (p -> r) -> r works, and it is intuitively obvious: I've got p -> r so I've also got r, given that I've got p.

Math is hard. 

The obvious has to be stated, or else falsehood and inconsistency rears it's ugly, nondeterministic head, and we have to wake up and smell the coffee.

But, okay, we're in the continuum of truths, were I do have a p, and p is true, and I have a p -> r, so I've got me an r, so what's the point of continuations?

Well, not that I've got p -> r, I can get my r out any time I want to: now, or later, and 'later' being that the context has entirely changed and the world has moved on, but, if I want to 'reset the clock' or 'turn back time' I now can! All I do is feed my p into my p -> r function and I get my r out in the state when I originally got them.

Importantly, not now messed up by everything else that's come along after.

And therefore the name of the continuation-function, because at time

(p -> r) -> r

I create a continuation from that point, and then I go along and do something else, but then I have my p and I continue from the continuation point in the context of the state of the prior continuation.

The classic, humorous example:

I buy chocolate mousse cake and a latte, create the continuation, eat the cake, drink the coffee, gain weight after eating and drinking.

But then.

I take my little continuation function, my weight goes right back down (because I'm now in the old context of 'before I ate the cake'), and there, lo, and behold! is the cake, all ready to be eaten. So, I sit down, and enjoy my cake. Again. As often as I'd like.

With continuation-functions, you can have your cake, and eat it, too.

But it gets better than even that!

How? you demand.

Thank you for asking.

Because there's this little thing calle the 'continuation-passing style.' When you're working with continuations, you never really ... activate continuations. You just pass them around, as if they're arguments, composing them together, and eventually you pass in your activation function after you're all done and your whole system gets executed or proved all in one go.

Great.

But here comes the better.

Because, usually, continuation-functions are of some generic types p -> r, you can exercise your system with one set of types, then, when you find that wasn't exactly what you were looking for, you just simply ...

... do nothing.

You don't change one thing in your proof system, you just feed in the new, or desired, type at the beginning of the proof, and all the types adjust themselves along the way.

Here's what a coding effort is, in the traditional sense. You code a solution, or so you thought, but somewhere in the middle, you wanted to do something different.

If, instead, you were using the continuation-passing style, instead of changing that middle bit, you just simply pass in the continuation you actually wanted instead. Zero code change.

Or, you code a solution, or so you thought, but you were using the wrong types, and it could be something as simple as changing from British Imperial to Metric (and therefore you just lose a satellite at launch, is all), or it could be something as drastic as using plowshares instead of swords, I don't know.

But the thing is, in the traditional coding paradigm, you're stuck, you have to change all the functions, what type of arguments they take and what value-types they return.

Seventy-two hours. A team in the Nation's Capital spent seventy-two hours recoding an integer to a string because the two-billionth row was reached and the entire system crashed with the computer couldn't index higher than that, and some frikken genius notice the indices weren't being used as numbers, they were just row identifiers, so they could be arbitrarily-lengthed strings instead of integers with an artificial maximum.

Frikken brilliant.

Seventy-two frikken hours of everybody's life wasted on that snafu. A whole weekend.

I'm a consultant. I got paid for my trouble. Some other folks didn't.

That system was coded in the traditional sense.

If the continuation-passing style had been used, how much recoding would we had to have done?

None.

Why?

Because p, the input type, whereas before was (arbitrarily) designated as an integer now could simply be a string. There were no counting functions used against the indices, just simply identifying functions: "Are you row x?" "Why, yes, I am." "Well, then, we're done."

That would have been our seventy-two hours: a simply "well, then, we're done."

Okay, smarty-pants, if continuations are so hot, then why isn't everyone using them?

Actually, everybody coding in the language Scheme is using continuations, and transparently at that. A joke from the BrainF community is that they have continuations built into their language: it's called the enter key.

So why isn't everybody else?

I don't know.

Actually, I do.

Continuations require you work with functions-as-arguments as a coding style, so instead of just coding the for-loop or the if-statement, you actually have to think, and to think strategically, about what you're doing with the system. Meaning you have to know what you're doing, not only right here and right now, but with entire system or subsystem. You have to know the details, but you also have to know the overall plan.

And having a good grasp of everything is just too much for some people. For most people who just want to code that for-loop.

But what are you actually doing with that for-loop? Why do you have that if-statement? Why are you adding those two numbers? What story is your code telling the reader, be it the customer who will use the system or you, again, months later, when you come back to that part of the system and try to decipher what the heck you were doing, and why ...

Well, then, looking at code that I've looked at, that's just way too hard for most. That for-loop? It's tight! What need is it supposed to be addressing? I have no idea. And all the unit tests on the code (which for most coders, is 'none') are so helpful in clearing up these open questions.

But, now, with continuations, does teasing out the meaning of a particular piece of code become harder or easier?

Well, it actually becomes much harder, and in most cases. Why? Because this particular piece of code depends on a continuation passed in (or injected) from elsewhere, and depending (a 'dependency') on what's injected, the entire behavior changes.

This is the dependency-injection style of coding, or, instead of object-oriented, it becomes aspect-oriented, and most traditional, imperative-style coders simply loathe the aspect-oriented approach for it's dearth of for-loops and if-statements.

Most software projects fail. Spectacularly, with huge cost overruns and a complete failure to deliver on promised feature sets.

Spectacularly as in 'billions of dollars' spectacularly. I'm not speaking hypothetically.

Two projects that used generic typing and the continuation-function passing style made over forty million dollars, and the problem with these projects is that they overdelivered on promised feature sets and the users got accustomed to working with software that actually worked. I talked with both product owners of those projects. Nice guys. Really relaxed outlook on life.

Eh. But I digress. As always.

The continuation, it's a function c :: (p -> r) -> r that gives you the power 'to rewind time,' as it were. And what does that give you?

Freedom.

You have the freedom to experiment, because if a particular approach doesn't work, you hit the continuation-'button' and try again with something else, ...

... without having to retool.

Or, if you were working with one set of types, and the situation or the story changes and you now have to work with an entirely new set of things doing a similar set of processes in the work-flow, you hit the continuation-'button' with the new types, ... without having to retool ... and try it with the new types. Got your solution? Great! Need to change something in the middle? Okay, just pass in a new continuation and try again.

'Programming,' ... 'coding' is considered brittle and expensive, and for the most part it is, but there's one thing that just works and works sweet.

The World-wide Web.

There's this very flexible style of coding to web-programming called functional-reactive programming. Web-frameworks have been prototyped, stood up, changed on-the-fly, what have you, using this functional-reactive style.

Guess what's under the hood of this approach.

The little, plain-old continuation-function.

See you tomorrow.

Unless I reset my continuation-function from before I wrote this article.

But then I'd have to rewrite this article. Oops! Let's press forward, then!

'B' is for Bayesian Classifiers

So. B.

Bayes was this little guy, way back when who happened to notice something that most people just naturally assume to be true. It's not, but people assume this.

And this observation that Bayes noticed was this.

"Hey, look, guys, something seems to happen because of everything else that's happening!"

Stunning revelation, isn't it?

But then he, unlike everybody else at that time (prior and even unto now), codified that belief.

('Belief.' Heh. The Bayesian network is also called the belief network).

He said, the likelihood of something is dependent on the likelihood of all the other factors you've observed.

So, for example, the probability of you picking the bracket perfectly is a (more than a few) billion (plus) to your one guess. Double your odds? Guess twice.

Yeah, right.

But I digress.

As usual.

So, formulized, Bayes said

p(x | X) = p(a | x) * p(b | x) * p(c | x) ... * p(z | x)

Or, that is:

The probability of x in the set of X's happening (like the probability of the Red Sox winning this game), is equivalent to the set of probabilities of everything else happening, given that the Red Sox won before.

So, was it raining when the Red Sox won?
Was it Tuesday when the Red Sox won?
Did you wear your lucky shirt when the Red Sox won?

You take all that historical data, compute the probabilities of each, multiply them all together, and you come up with some probability.

Then, you do the same for all cases (Red Sox winning is one case, Red Sox losing is what we don't even want to consider, but it is a case, too, so just deal with that ... for eighty-six years), and the case with the highest probable outcome is ... well, the one most likely to occur.

... according to Bayes.

How does this work in practice?

Well, pretty darn good, but that's dependent upon what other systems you're comparing it against and what you're using it for.

For example (or 'fer realz'), a Bayesian classifier we built against a transactional system that ran one hundred thousand transactions per day was able to sniff out more than ninety-nine percent of the transactions that were ... 'fishy': erroneous or malicious. Compared to what other system? A rule-based system made up of rules composed by subject-matter experts and analysts familiar with the transactions.

Another for example, a little Bayesian classifier I built to pick winning football teams worked ... pretty well. We had ten or so members of that pool, and I walked away a winner three or four times. Not stellar, but not bad; not bad at all.

The beauty of a Bayesian classifier is that it's simplicity itself to implement. The probabilities run away from you on a computer, because multiplying small probabilities will get you into the IEEE math error zone so quickly your head will spin, and your system gets all weirded out, but instead of multiplying probabilities, just use a little bit of seventh grade math (in my day) and simply sum their logarithms:

p(x | X) = p(a | x) * p(b | x) * p(c | x) ...

can be re-represented as:

log p(x | X) = log p(a | x) + log p(b | x) + log p(c | x) ...

And this way we (greatly) reduce going off into la-la land for your ALU.

'A' is for Aleph-null

'A' is for ℵ0

Read: "'A' is for Aleph-null"

ℵ0 is a symbol for infinity. The first one, that is, as there are many infinities in mathematics, and many kinds of infinities, depending on which number system you choose to use (there are ... more than several kinds of numbers, but that may be the entry for 'N,' as in: "'N' is for 'Number.' But I digress, ...

... as usual).

My introductory post to my A-to-Z blog-writing challenge, or my Α-to-Ω blog-writing challenge, but that may be all Greek to you.

An appropriate entry because mathematics, itself, is as big as you want to make of it, or as small as you want to focus in on it. For example, infinity, one of them, ℵ0, is countably infinite. You take the first number (which happens to be 0 (zero)), and add one to it, and you get:

0, 1, 2, 3, ...

... and you keep going until you (don't) reach ℵ0.

The thing is, you can count this infinity. You just did.

But there are other infinities, including one you can't even count, because a 'bigger' infinity (it actually is bigger), is C, the continuum, because there numbers, such as:

π, τ, e, ...

Numbers that can't even be represented by a series of digits or by any function, even. They are the transcendental numbers, and are 'irrational.'

There is no way to rationalize the number π, for example; you just have to live with it, with all its quirkiness and all its irrationality.

So, how do you go along the numberline that includes irrational numbers? You can't. Why? Well, what's the 'next number' after π? There isn't one. It's not that we don't know what's the next number after π, it's just that there is no such thing, there is no 'very next number adjacent to π.'

Unless you invent a number system that counts along the continuum.

Good luck with that.

But, on the other hand, 4,000 years after Euclid, with his celebrated (or infamous) fifth postulate, said something along the lines of 'if two lines are extended into infinity on a plane and they never cross, then they kinda hafta be parallel,' people were still nodding their heads to that.

(The Ancient Greeks said 'kinda hafta' when they were dead serious about stuff like that.)

Then along came conic sections, and, lo, and behold, on those planes, it is possible, easily so, for two non-parallel lines, extended into infinity never to cross.

And the conics opened up whole new vistas of mathematics for us to explore.

So, one could say mathematics is a confining view; limiting, but the constraints are artificial: they are there because we put them there, and we put them there for some set of reasons, even if we don't know it or even if we forgot those reasons. If a particular set of mathematics doesn't do what we want it to do, or does it in an unforgivably cumbersome way, then, ... simply invent a new set of mathematics, see that it does do what we need it to do, and that, importantly, it doesn't do what we don't want it to do, and then we're good, right?

It's just that ... sometimes mathematics, being not particularly tiny — like our tiny, little, rigid brains — does things we don't expect and never look for, and so we get into trouble if we aren't rigorous. That happened to people who thought they invented complete and consistent systems. Frege invented a mathematics based on pure (predicate) logic, except it allowed the paradox of the 'set that has all sets (including itself)' Russell showed him this error.

So Russell invented the mathematics described in the Principia Mathematica, which most of think of, when we think of mathematics, and was rigorous about it, too. It took two-hundred pages of axioms and theories to prove that

1 + 1 = 2

And that holds, meaning that '1' is actually 1, '2' is actually 2, and '+' and '=' are what we'd like to think they are.

When Russell did that, he chorkled with glee, "Ha, we're good!" he shouted, "We have the big TOE! [theory of everything] Nothing that is inconsistent exists in this system."

Then, more than several years later, a little mathematician named Gödel did something amazing.

He said, "Really? Are you sure? Because ..."

And then he proved the system inconsistent.

How?

Well, it involves a little 50-page paper he published. Essentially what he did was, working entirely in Russell's system, he modelled mathematical formulae as numbers. He proved his modelling was consistent in that system, in that a Gödel-number mapped to a formula and that a formula mapped to that number, and that the numbers worked the way you expected the formulae to work.

Then he wrote a number that said: 'This formula (of truth) cannot be proved (is inconsistent) in Russell's system.'

And showed that number existed in Russell's system, a system that Russell showed, empirically, was consistent.

Russell's system, using Russell's axioms and theories, was provably inconsistent.

And Russell never saw that one coming.

Nor did most anyone else.

But Gödel accidentally showed that a system is either incomplete or inconsistent, or: a system cannot be both complete and consistent.

And that proof, way back when, opened the door to mathematics as we are wrestling with today, giving us Quantum theory, allowing us to do neat things, like write blog entries on this little thing we call a laptop.

So, that's that caveat to us mathematicians: we're working with a model that we created. We can stand up and say: 'Ha! This proves everything!' And it may be good for what we wanted, but all somebody has to do is remove the limits we've set to explode our neat, little rigorous system.

The good news is the explosion may be a good thing.

'A' is for ℵ0, but that (infinity) is just the start ...

Bayesian Football Picker: an implementation

Some time ago I wrote an article about applying Bayes to pick winners for the weekly football pool we had at our office. So, that pool went on for seventeen weeks, and I came out as one of the winners. Success!

So, how did that all work? 

I'll give you the business process of it and provide a high level overview of my Bayesian system. After that, I'll get down into the guts of the implementation.

I wrote this entire system in Haskell. It was something less than a day's effort.

Business Process/Big Picture

Each week, our boss, Dharni, provided the USA Today's predictions for the teams as a spreadsheet, which I saved in CSV format ('comma-separated values'). The weekly input spreadsheet (as CSV) looked like this:

,Wed Sep 5,

NYG GIANTS,3½ ,Dallas

,Sun Sep 9,

CHICAGO,10 ,Indianapolis

Philadelphia,7½ ,CLEVELAND

NYJ JETS,2½ ,Buffalo

NEW ORLEANS,7 ,Washington

New England,5 ,TENNESSEE

MINNESOTA,3½ ,Jacksonville

HOUSTON,11 ,Miami

DETROIT,6½ ,St. Louis Rams

Atlanta,2½ ,KANSAS CITY

GREEN BAY,5 ,San Francisco

Carolina,2½ ,TAMPA BAY

Seattle,2½ ,ARIZONA

DENVER,2½ ,Pittsburgh

,Mon Sep 10,,,,,,,

BALTIMORE,6 ,Cincinnati,TS,35-20,,,,

OAKLAND,2½ ,San Diego,,,,,,

where the number (e.g.: '2½') was the predicted point-spread, the team on the left was  the team predicted to win by the point-spread, and the capitalized team was the home team. The 'TS' indicator was if there were ties of people in the pool who guess the same number of picks correctly, then the TS was a tie-breaker: you had to guess the 'Total Score' for that game and the person who got the closest total score won the tie-breaker. I didn't worry my head over this particular aspect, so I just had my system predict the winner for that game and threw out a random total score.

I fed these data to my system which took each data point as a class-value for the Bayesian classifier, and my system spit out ('spit out' is a technical term, just like: 'run off') its own predictions which I turned right around back to Dharni: "I've highlighted the teams my system picked to win, Dharni."

The output result from the system was something like this:

Thursday,NYGGIANTS,Home,3.5,DALLAS,RIGHT

Saturday,CHICAGO,Home,10.5,INDIANAPOLIS,LEFT

Saturday,PHILADELPHIA,Away,7.5,CLEVELAND,LEFT

Saturday,NYJJETS,Home,2.5,BUFFALO,LEFT

Saturday,NEWORLEANS,Home,7.5,WASHINGTON,RIGHT

....

Just as before, right? Well, sort of. In this case my system output teams as (discriminated type) values, the spreads were floats, and the Home/Away indicator told me where the left team played. 'LEFT' or 'RIGHT' indicated which team the system predicted would win that game.

My coworkers were enchanted that I wrote myself a little football-picker. They'd exclaim in mock-dismay: "Something only geophf would come up with!"

Then my system won, and won, and won again. Not consistently, nor convincingly, but, to my satisfaction (that it even ever won at all): profitably. Pretty good. Pretty darn good enough!

Then, with what really happened that week (you know: that pesky ITRW result-set messing with my conceptual-frameworks!), I'd feed the results back into my system (the feedback look), training it with what were good and bad guesses on its part. Week after week my system accumulated the historical data and results into a data-set I named basis/training-set.csv. 

As the season progressed, my historical training data set grew, and I did, indeed, win pools more often later in the season rather than earlier. Which was nice: my predictive system was predicable.

The Guts/Little Picture

It's actually embarrassing how small my baby classifier is, and really, it'd be a lot smaller if Haskell natively read football spread predictions: it'd just be the Bayesian classifier.

But since Haskell doesn't natively read CSV files nor football spreads, I wrote those modules, too.

Here's the system.

The football picker is in the Football (parent) module and contains the module named Go:

> module Football.Go where

> import Football.Data.Week

> import Football.Analytics.Bayes

> import Football.Trainer

> go picks training = snarf training >>= \basis ->

>                     slurp picks >>= readWrite pick Thursday basis writeln

> choose picks = putStrLn "<table border='1'>" >>

>              slurp picks >>= readWrite justShow Thursday () writeRow >>

>              putStrLn "</table>"

> writeRow (match, _) = writeWeek HTML match >> putStrLn ""

What you do is load the Go module and say "go" to Haskell with the teams to be picked for this week with their data (the 'picks') and the training data set, both in CSV-format.

The system then 'snarfs' the training data, training the Bayesian classifier, yielding a training 'basis,' then 'slurps' in the teams for this week to give the picks.

As to the names of the functions: don't look at me. I don't know. The dude who wrote system had an oddball sense of humor.

And the 'choose' and 'writeRow' functions. Eh. I had made my system both CSV and HTML (output) friendly. I had this grandiose plan to have everything printed out all prettily in HTML and have an HTML input interface, setting this up as a web service with micro-transactions and everything so I could eventually sell the system off to Microsoft for 1.21 gigabucks, but in practice I just 'go'ed with the console-output results and highlighted the winning teams on the spreadsheet Dharni provided, and never really used the HTML functionality beyond some initial prototyping. Idle hands, lesson learned, simplicity, ... you know: all that.

So, the 'Go' module is just an entry-point to the 'readWrite' function which reads the input UTF-8 data, converts it to Haskell types and then writes the results out as CSV. Let's look at that function, then, and keep digging down until we're all dig-dugged out.

readWrite

The 'readWrite' function is in module Football.Trainer, its definition is as follows:

> readWrite _ _ _ _ [] = return ()

> readWrite fn day basis w (row:rows) = if   length (csv row) == 1

>                                       then readWrite fn (succ day) basis w rows 

>                                       else w (fn day row basis) >>

>                                            readWrite fn day basis w rows

... the whole if-clause is to handle whether this row is a football match row or a row declaring the day of the week.

If we query the type of readWrite from the Haskell system we get this 'interesting' type-value:

readWrite

  :: (Monad m, Enum a) =>

     (a -> String -> t -> t1)

     -> a

     -> t

     -> (t1 -> m a1)

     -> [String]

     -> m ()

which is my lovely way of making this generalized function that reads an enumerable type and puts it out to some monadic domain.

Bleh!

But, since I'm not working with HTML any more, readWrite is always called with the higher-order function arguments of

readWrite pick day basis writeln

where the functions pick and writeln are declared as:

> pick :: DayOfWeek -> String -> ([Match], [Match]) -> (Match, Call)

and

> writeln :: (Show t) => (Match, t) -> IO ()

> writeln (match, winner) = writeWeek CS match >> putStrLn (show winner)

which reduces readWrite, once the higher-order function arguments are applied, to a more compact type of:

> justDoIt :: DayOfWeek -> ([Match], [Match]) -> [String] -> IO ()

> justDoIt day basis rows = readWrite pick day basis writeln rows

which, of course, means we need to explain the function pick now, with its calls, but let's first clarify the types used, now that the function readWrite has been reduced to its used form.

Types

DayOfWeek is an example right out of the book for a disjoint type:

> data DayOfWeek = Thursday | Sunday | Monday

>      deriving (Show, Read, Eq, Ord, Enum)

(apparently there are only three days of the week ... in football, anyway, and that's all that matters, right?)

And the Match-type is the representation of a row of data (a football match):

> data Match = Match DayOfWeek Team Field Float Team deriving Show

Team is just simply the teams as disjoint enumerated values (e.g.: GREENBAY, STLOUISRAMS, etc.), The Field-type is Home or Away, and there you go!

There is a bit of a hex reading in the floating point value from, e.g.  '2½' and for that particular hack I created a separate type in a separate module:

> module Football.Data.Spread where

eh.

So, the spread is a number but represented in unicode ... do we wish to

capture the original datum as it was represented in the picks sheet for any

reason? Mucking with data always leads to sorrow, but ... well, this module

provides a Num interface to Spread, so you can swing either way with it.

> import Data.Char

> data Spread = Spread String

>      deriving Show

> toNum :: Spread -> Float

> toNum (Spread x) = toNum' x 0.0

> toNum' [] x = x

> toNum' (c:rest) x | c == ' ' = x

>                   | c > '9' = x + 0.5

>                   | otherwise = toNum' rest (10 * x

>                                              + fromIntegral (ord c - ord '0'))

> instance Read Spread where

>    readsPrec _ datum = [(Spread datum, "")]

> instance Eq Spread where

>    x == y = toNum x == toNum y

You'll note that the Spread-type isn't actually a Num instance, as the spread is a typed class value, I don't care, in my Bayesian system, whether the spread is lesser or greater; I just care if it's different from another spread.

Algorithm

Okay, back to the program!

So readWrite slurps in training data and the matches for this week and sends it to the 'pick' function which we've declared above, and we now define as:

> pick day row basis = let (match, _) = mkWeek day row

>                          winner = classify match basis

>                      in (match, winner)

The mkWeek function just slurps in the row as a string and converts it to a Match-type and with that reified typed value we ask the Bayesian system to classify this n-tuple as a Left or Right (predicted-to-)win.

So, let's look at the classify-function.

> classify :: Match -> ([Match], [Match]) -> Call

> classify query basis@(l, r) = let ll  = fromIntegral $ length l

>                             lr  = fromIntegral $ length r

>                             tot = ll + lr

>                         in  if (bayes query l + log (ll / tot)) >

>                                (bayes query r + log (lr / tot))

>                             then LEFT

>                             else RIGHT

The classify-function is your classic Bayes algorithm: classify the n-tuple as the type with the greatest probabilistic outcome. In our case we have two possible results, LEFT and RIGHT, so if the probablistic (logarithmic) sum for LEFT is greater, then it's LEFT, otherwise it's RIGHT.

Very 'Either'escque ... without the packaged data. So, actually, not very 'Either'escque at all but more 'Boolean'escque. Kinda. Sorta.

Our bayes-function is just summing the logarithms of the probabilities:

> bayes :: Match -> [Match] -> Float

> bayes (Match dow fav field spred dis) side = 

>       let pdow =   logp (\(Match d _ _ _ _) -> d == dow) side

>           pfav =   logp (\(Match _ f _ _ _) -> f == fav) side

>           pfield = logp (\(Match _ _ f _ _) -> f == field) side

>           psprd =  logp (\(Match _ _ _ s _) -> s == spred) side

>           pdis   = logp (\(Match _ _ _ _ d) -> d == dis) side

>       in sum [pdow, pfav, pfield, psprd, pdis]

We need a fix here for 0% match ... the log return -infinite, skewing the results, so let's just return 0 for 0, okay?[1]

> logp :: (Match -> Bool) -> [Match] -> Float

> logp fn matches = let num = fromIntegral (length $ filter fn matches)

>                       dem = fromIntegral (length matches)

>                   in  if (num == 0.0 || dem == 0.0)

>                       then 0.0

>                       else log (num / dem) 

That's basically everything, just some window-dressing functions of reading in the training set, which requires us to read in CSV files, so I present these functions here for completeness.

To read a CSV file, we simply rewrite the words-function from the Prelude to allow separators other than spaces:

> module CSV where

> import Char

-- I modified Prelude.words to accept a set of alternative delimiters to space

> wordsBy :: String -> String -> [String]

> wordsBy delims line

>        = let isDelim = flip elem delims

>          in  case dropWhile isDelim line of

>                           "" -> []

>                           s' -> w : wordsBy delims s''

>                                 where (w, s'') =

>                                        break isDelim s'

> csv = wordsBy ","

The CSV module is useful not only here for picking football teams, but also for anywhere you need to parse in CSV data as linearized Haskell-types.

and then readResults (the results of the training data, that is) is as follows:

> readResults :: ([Match], [Match]) -> [String] -> ([Match], [Match])

> readResults map [] = map

> readResults map (row:rows) = let [dow, fav, field, spred, dis, call] = csv row

>                                  day = read dow

>                                  match = Match day (read fav) (read field)

>                                                (read spred) (read dis)

>                                  winner = read call

>                                  res = Result match winner

>                              in  readResults (addmap winner map match) rows

where addmap is the obvious add-to-left-or-right-branch-of-the-training-data-function:

> addmap :: Call -> ([a], [a]) -> a -> ([a], [a])

> addmap LEFT (l, r) m = (m:l, r)

> addmap RIGHT (l, r) m = (l, m:r)

The 'a'-type here is invariably a Match-(Row)-type that I use as my training-set basis, but the addmap-function works with any set of paired-lists.

The readResults-function is used by the snarf-function:

> snarf :: FilePath -> IO ([Match], [Match])

> snarf file = readFile file >>=

>              return . lines >>=

>              return . readResults ([], [])

So that just leaves the slurp-function for reading in this week's matches:

> slurp :: FilePath -> IO [String]

> slurp file = readFile file >>= return . tail . lines

(we skip, or 'tail', by the first line, because that's the day of the first football games, which we invariably call Thursday)

Conclusion, or: please send your 1.21 gigabuck checks to geophf

And there you have it, folks: a little Bayesian system that picks (we hope) winning football teams from a set of accumulating historical data. The 'we hope'-caveat is the usual standard disclaimer when using Bayesian systems: as one of my colleagues pointed out, using such a system for classification is like driving your car with the only guidance being the view in the rear-mirror, but, for me, such guidance paid off. I walked away from this experience building yet another (naïve) Bayesian classifier, and my little pet project helped me walk away from this pool with a few dollars more than I invested into it. Yay!

('Yay!' is a technical term, c.f. Despicable Me 2)

-----

Endnotes:

[1] There was a comment on my original blog entry about normalizing the absent probability instead of what I do here, which is to zero it out. My system worked okay without linearization, so it would be an area of further research to see how the results are improved from linearization.