Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
20. December 2014 01:55

This post is December 20th' part of the English F# Advent #fsAdvent series; make sure to also check out the Japanese series, which also packs the awesome!

As I was going around Paris the other day, I ended up in the Concorde metro station. Instead of the standard issue white tiles, this station is decorated with the French constitution, rendered as a mosaic of letters.

My mind started wandering, and by some weird association, it reminded me of Calligrammes, a collection of poems by Guillaume Apollinaire, where words are arranged on the page to depict images that compliment the text itself.

After some more drifting, I started wondering if I could use this as an inspiration for some playful F# fun. How about taking a piece of text, an image, and fusing them into one?

There are many ways one could approach this; being rather lazy, I thought a reasonably simple direction would be to decompose the original image into dark and light blocks, and fill them with the desired text. As simple as it may sound, the task is not entirely trivial. First, we need to decide on an appropriate threshold to separate "dark" and "light" areas on the image, to get a contrast good enough to recognize the image rendered in black & white. Then, we also have to resize the image appropriately into a new grid, where the characters from the original text fit the mapped dark area as closely as possible.

Note: I don't think the warning "don't put this in production, kids" is useful, unless someone thinks there is a market for Calligramme as a Service. However, I'll say this: this is me on "vacation hacking fun" mode, so yes, there are quite probably flaws in that code. I put it up as a Gist here - flame away, or tell me how to make it better on Twitter ;)

Separating dark and light

So how could we go about splitting an image into dark and light pixels? First, we can using the color brightness from the System.Drawing namespace to determine how light the color of an individual pixel is:

open System.Drawing

let brightness (c:Color) = c.GetBrightness ()

let pixels (bmp:Bitmap) =
seq { for x in 0 .. bmp.Width - 1 do
for y in 0 .. bmp.Height - 1 ->
(x,y) |> bmp.GetPixel }

We still need to decide what boundary to use to separate the image between dark and light. What we want in the end is an image which is reasonably balanced, that is, it should be neither overwhelmingly dark or light. A simple way to enforce that is to arbitrarily constrain one third of the pixels at least to be either dark or light. Then, we want a boundary value that is as clear cut as possible, for instance by finding a value with a large brightness change margin. Let's do that:

let breakpoint (bmp:Bitmap) =
let pixelsCount = bmp.Width * bmp.Height
let oneThird = pixelsCount / 3
let pixs = pixels bmp
let threshold =
pixs
|> Seq.map brightness
|> Seq.sort
|> Seq.pairwise
|> Seq.skip oneThird
|> Seq.take oneThird
|> Seq.maxBy (fun (b0,b1) -> b1 - b0)
|> snd
let darkPixels =
pixs
|> Seq.map brightness
|> Seq.filter ((>) threshold)
|> Seq.length
(threshold,darkPixels)

We iterate over every pixel, sort them by brightness, retain only the middle third, and look for the largest brightness increase. Done - breakpoint returns both the threshold value (the lightness level which decides whether a pixel will be classified as dark or light), as well as how many pixels will be marked as dark.

Resizing

Now that we have a boundary value, and know how many pixels will be marked as dark, we need to determine the size of the grid where our text will be mapped. Ignoring for a moment rounding issues, let's figure out a reasonable size for our grid.

First, how many characters do we need? We know the number of dark pixels in the original image - and in our target image, we want the same ratio of text to white space, so the total number of characters we'll want in our final image will be roughly total chars ~ text length * dark pixels / (width * height).

Then, what should the width of the target image, in characters? First, we want [1] target width * target height ~ total chars. Then, ideally, the proportions of the target image should be similar to the original image, so target width / target height ~ width / height, which gives us target height ~ target width * height / width. Substituting in [1] gives us target width * target width * height / width ~ total chars, which simplifies to target width ~ sqrt (total chars * width / height).

Translating this to code, conveniently ignoring all the rounding issues, we get:

let sizeFor (bmp:Bitmap) (text:string) darkPixels =
let width,height = bmp.Width, bmp.Height
let pixels = width * height
let textLength = text.Length
let chars = textLength * pixels / darkPixels
let w = (chars * width / height) |> float |> sqrt |> int
let h = (w * height) / width
(w,h)

Rendering

Good, now we are about ready to get down to business. We have an original image, a threshold to determine which pixels to consider dark or light, and a "target grid" of known width and height. What we need now is to map every cell of our final grid to the original image, decide whether it should be dark or light, and if dark, write a character from our text.

Ugh. More approximation ahead. At that point, there is no chance that the cells from our target grid map the pixels from the original image one to one. What should we do? This is my Christmas vacation time, a time of rest and peace, so what we will do is be lazy again. For each cell in the target grid, we will retrieve the pixels that it overlaps on the original image, and simply average out their brightness, not even bothering with a weighted average based on their overlap surface. As other lazy people before me nicely put it, "we'll leave that as an exercise to the reader".

Anyways, here is the result, a mapping function that returns the coordinates of the pixels intersected by a cell, as well as a reducer, averaging the aforementioned pixels by brightness, and a somewhat un-necessary function that transforms the original image in a 2D array of booleans, marking where a letter should go (I mainly created it because I had a hard time keeping track of rows and columns):

let mappedPixels (bmp:Bitmap) (width,height) (x,y) =

let wScale = float bmp.Width / float width
let hScale = float bmp.Height / float height

let loCol = int (wScale * float x)
let hiCol =
int (wScale * float (x + 1)) - 1
|> min (bmp.Width - 1)
let loRow = int (hScale * float y)
let hiRow =
int (hScale * float (y + 1)) - 1
|> min (bmp.Width - 1)

seq { for col in loCol .. hiCol do
for row in loRow .. hiRow -> (col,row) }

let reducer (img:Bitmap) pixs =
pixs
|> Seq.map img.GetPixel
|> Seq.averageBy brightness

let simplified (bmp:Bitmap) (width,height) threshold =

let map = mappedPixels bmp (width,height)
let reduce = reducer bmp
let isDark value = value < threshold

let hasLetter = map >> reduce >> isDark

Array2D.init width height (fun col row ->
(col,row) |> hasLetter)

Almost there - wrap this with 2 functions, applyTo to transform the text into a sequence, and rebuild, to recreate the final string function:

let applyTo (bmp:Bitmap) (width,height) threshold (text:string) =

let chars = text |> Seq.toList
let image = simplified bmp (width,height) threshold

let nextPosition (col,row) =
match (col < width - 1) with
| true -> (col+1,row)
| false -> (0,row+1)

(chars,(0,0))
|> Seq.unfold (fun (cs,(col,row)) ->
let next = nextPosition (col,row)
match cs with
| [] -> Some(' ',(cs,next))
| c::tail ->
if image.[col,row]
then
Some(c,(tail,next))
else Some(' ',(cs,next)))

let rebuild (width,height) (data:char seq) =
seq { for row in 0 .. height - 1 ->
data
|> Seq.map string
|> Seq.skip (row * width)
|> Seq.take width
|> Seq.toArray
|> (String.concat "") }
|> (String.concat "\n")

Trying it out

Let's test this out, using the F# Software Foundation logo as an image, and the following text, from fsharp.org, as a filler:

F# is a mature, open source, cross-platform, functional-first programming language. It empowers users and organizations to tackle complex computing problems with simple, maintainable and robust code.

Run this through the grinder…

let path = @"c:/users/mathias/pictures/fsharp-logo.jpg"
let bmp = new Bitmap(path)

let text = """F# is // snipped // """

let threshold,darkPixels = breakpoint bmp
let width,height = sizeFor bmp text darkPixels

text
|> applyTo bmp (width,height) threshold
|> rebuild (width,height)

… and we get the following:


F#
is
a matu
re, open
source, c
ross-platfor
m, fun  ctiona
l-firs t   progr
amming  l   anguag
e. It  emp    owers
users  and      organi
zation s to     tackle
compl ex    computi
ng pro bl  ems wit
h simp l e, main
tainab le and
robust code.      

Not too bad! The general shape of the logo is fairly recognizable, with some happy accidents, like for instance isolating "fun" in "functional". However, quite a bit of space has been left empty, most likely because of the multiple approximations we did along the way.

Improved resizing

Let's face it, I do have some obsessive-compulsive behaviors. As lazy as I feel during this holiday break, I can't let go of this sloppy sizing issue. We can't guarantee a perfect fit (there might simply not be one), but maybe we can do a bit better than our initial sizing guess. Let's write a mini solver, a recursive function that will iteratively attempt to improve the fit.

Given a current size and count of dark cells, if the text is too long to fit, the solver will simply expand the target grid size, adding one row or one column, picking the one that keeps the grid horizonal/vertical proportions closest to the image. If the text fits better in the new solution, keep searching, otherwise, done (similarly, reduce the size if the text is too short to fit).

For the sake of brevity, I won't include the solver code here in the post. If you are interested, you can find it in the gist here.

Below are the results of the original and shiny new code, which I ran on a slightly longer bit of text.

Before:


F#is
amatur
eopenso
urcecross
-platformfun
ctional-firstp
rogramminglangua
geItempowersusersa
ndorganiz  ationstot
acklecomp    lexcomput
ingproble ms   withsimpl
emaintain abl    eandrobus
tcodeF#ru nson     LinuxMacO
SXAndroid iOSWi      ndowsGPUs
andbrowse rsItis       freetouse
andisope nsourc       eunderanO
SI-approv edlic      enseF#isu
sedinawid eran     geofappli
cationar eas   andissuppo
rtedbybo th   anactive
opencommu    nityandin
aniesprovidingpr
ofessionaltool
s                       

… and after:

               F #
is am
atu reo
pens ourc
ecros s-pla
tformf unctio
nal-fir stprogr
ammingla nguageIt
empowers   usersand
organiza t   ionstota
cklecomp le    xcomputi
ngproble msw     ithsimpl
emaintai nabl      eandrobu
stcodeF# runso       nLinuxMac
OSXAndro  idiOS       WindowsGP
Usandbro wsers      Itisfreet
ouseandi sope     nsourceun
deranOSI -ap    provedlic
enseF#is us   edinawide
rangeofa p  plication
areasand  issupport
edbyboth anactive
opencom munitya
ndindu stry-l
anie spro
vid ing
pr of
e s               

We still have a small mismatch, but the fit is much better.

And this concludes our F# Advent post! This was a rather useless exercise, but then, the holidays are about fun rather than productivity. I had fun doing this, and hope you had some fun reading it. In the meanwhile, I wish you all a holiday period full of fun and happiness, and… see you in 2015! And, as always, you can ping me on twitter if you have comments or questions. Cheers!

1. March 2014 14:32

During some recent meanderings through the confines of the internet, I ended up discovering the Winnow Algorithm. The simplicity of the approach intrigued me, so I thought it would be interesting to try and implement it in F# and see how well it worked.

The purpose of the algorithm is to train a binary classifier, based on binary features. In other words, the goal is to predict one of two states, using a collection of features which are all binary. The prediction model assigns weights to each feature; to predict the state of an observation, it checks all the features that are “active” (true), and sums up the weights assigned to these features. If the total is above a certain threshold, the result is true, otherwise it’s false. Dead simple – and so is the corresponding F# code:

type Observation = bool []
type Label = bool
type Example = Label * Observation
type Weights = float []

let predict (theta:float) (w:Weights) (obs:Observation) =
(obs,w) ||> Seq.zip
|> Seq.filter fst
|> Seq.sumBy snd
|> ((<) theta)

We create some type aliases for convenience, and write a predict function which takes in theta (the threshold), weights and and observation; we zip together the features and the weights, exclude the pairs where the feature is not active, sum the weights, check whether the threshold is lower that the total, and we are done.

In a nutshell, the learning process feeds examples (observations with known label), and progressively updates the weights when the model makes mistakes. If the current model predicts the output correctly, don’t change anything. If it predicts true but should predict false, it is over-shooting, so weights that were used in the prediction (i.e. the weights attached to active features) are reduced. Conversely, if the prediction is false but the correct result should be true, the active features are not used enough to reach the threshold, so they should be bumped up.

And that’s pretty much it – the algorithm starts with arbitrary initial weights of 1 for every feature, and either doubles or halves them based on the mistakes. Again, the F# implementation is completely straightforward. The weights update can be written as follows:

let update (theta:float) (alpha:float) (w:Weights) (ex:Example) =
let real,obs = ex
match (real,predict theta w obs) with
| (true,false) -> w |> Array.mapi (fun i x -> if obs.[i] then alpha * x else x)
| (false,true) -> w |> Array.mapi (fun i x -> if obs.[i] then x / alpha else x)
| _ -> w

Let’s check that the update mechanism works:

> update 0.5 2. [|1.;1.;|] (false,[|false;true;|]);;
val it : float [] = [|1.0; 0.5|]

The threshold is 0.5, the adjustment multiplier is 2, and each feature is currently weighted at 1. The state of our example is [| false; true; |], so only the second feature is active, which means that the predicted value will be 1. (the weight of that feature). This is above the threshold 0.5, so the predicted value is true. However, because the correct value attached to that example is false, our prediction is incorrect, and the weight of the second feature is reduced, while the first one, which was not active, remains unchanged.

Let’s wrap this up in a convenience function which will learn from a sequence of examples, and give us directly a function that will classify observations:

let learn (theta:float) (alpha:float) (fs:int) (xs:Example seq) =
let updater = update theta alpha
let w0 = [| for f in 1 .. fs -> 1. |]
let w = Seq.fold (fun w x -> updater w x) w0 xs
fun (obs:Observation) -> predict theta w obs

We pass in the number of features, fs, to initialize the weights at the correct size, and use a fold to update the weights for each example in the sequence. Finally, we create and return a function that, given an observation, will predict the label, based on the weights we just learnt.

And that’s it – in 20 lines of code, we are done, the Winnow is implemented.

More...

15. February 2014 12:51

My favorite column in MSDN Magazine is Test Run; it was originally focused on testing, but the author, James McCaffrey, has been focusing lately on topics revolving around numeric optimization and machine learning, presenting a variety of methods and approaches. I quite enjoy his work, with one minor gripe –his examples are all coded in C#, which in my opinion is really too bad, because the algorithms would gain much clarity if written in F# instead.

Back in June 2013, he published a piece on Amoeba Method Optimization using C#. I hadn’t seen that approach before, and found it intriguing. I also found the C# code a bit too hairy for my feeble brain to follow, so I decided to rewrite it in F#.

In a nutshell, the Amoeba approach is a heuristic to find the minimum of a function. Its proper respectable name is the Nelder-Nead method. The reason it is also called the Amoeba method is because of the way the algorithm works: in its simple form, it starts from a triangle, the “Amoeba”; at each step, the Amoeba “probes” the value of 3 points in its neighborhood, and moves based on how much better the new points are. As a result, the triangle is iteratively updated, and behaves a bit like an Amoeba moving on a surface.

Before going into the actual details of the algorithm, here is how my final result looks like. You can find the entire code here on GitHub, with some usage examples in the Sample.fsx script file. Let’s demo the code in action: in a script file, we load the Amoeba code, and use the same function the article does, the Rosenbrock function. We transform the function a bit, so that it takes a Point (an alias for an Array of floats, essentially a vector) as an input, and pass it to the solve function, with the domain where we want to search, in that case, [ –10.0; 10.0 ] for both x and y:

#load "Amoeba.fs"

open Amoeba
open Amoeba.Solver

let g (x:float) y =
100. * pown (y - x * x) 2 + pown (1. - x) 2

let testFunction (x:Point) =
g x.[0] x.[1]

solve Default [| (-10.,10.); (-10.,10.) |] testFunction 1000

Running this in the F# interactive window should produce the following:

val it : Solution = (0.0, [|1.0; 1.0|])
>

The algorithm properly identified that the minimum is 0, for a value of x = 1.0 and y = 1.0. Note that results may vary: this is a heuristic, which starts with a random initial amoeba, so each run could produce slightly different results, and might at times epically fail.

More...

2. February 2014 08:08

tl/dr: Community for F# has a brand-new page at www.c4fsharp.net – with links to a ton of recorded F# presentations, as well as F# hands-on Dojos and material. Check it out, and let us know on Twitter what you think, and what you want us to do next… and spread the word!

If you are into F# and don’t know Community for F#, you are missing out! Community for F#, aka C4FSharp, is the brainchild of Ryan Riley. Ryan has been running C4FSharp tirelessly for years, making great content available online for the F# community.

The idea of C4FSharp is particularly appealing to me, because in my opinion, it serves a very important role. The F# community is amazingly active and friendly, but has an interesting challenge: it is highly geographically dispersed. As a result, it is often difficult to attend presentations locally, or, if you organize Meetups, to find speakers.

Ryan has been doing a phenomenal job addressing that issue, by regularly organizing online live presentations, and making them available offline as well, so that no matter where you are, you can access all that great content. The most visible result is an amazing treasure trove of F# videos on Vimeo, going back all the way to 2010. While I am giving credit where credit is due, special hats off to Rick Minerich, who has been recording the NYC meetings since forever, and making them available on Vimeo as well – and also has been lending a helping hand when C4FSharp needed assistance. Long story short, Rick is just an all-around fantastic guy, so… thanks, Rick!

In any case, the question of how to help grow the F# community has been on my mind quite a bit recently, so I was very excited when Ryan accepted to try working on this as a team, and put our ideas together. The direction I am particularly interested in is to provide support for local groups to grow. Online is great, but nothing comes close to having a good old fashioned meeting with like-minded friends to discuss and learn. So one thing I would like to see happen is for C4FSharp to become a place where you can find resources to help you guys start and run your own local group. While running a Meetup group does take a bit of effort, it’s not nearly as complicated as what people think it is, and it is very fun and rewarding. So if you want to see F# meetings in your area, just start a Meetup group!

In that frame, Ryan has put together a brand-new web page at www.c4fsharp.net, where we started listing resources. The existing videos, of course, but also a repository of hands-on Dojos and presentation/workshop material. The hands-on Dojos is something we started doing in San Francisco last year with www.sfsharp.org, and  has been working really well. Instead of a classic presentation, the idea is to create a fun coding problem, sit down in groups and work on it, learn from each other, and share. It’s extremely fun, and, from a practical standpoint, it’s also very convenient, because you don’t need to fly in a speaker to present. Just grab the repository from GitHub, look at the instructions, and run with it!

Just to whet your appetite, here is a small selection of the amazing images that came out of running the Fractal Forest Dojo in Nashville and San Francisco this month:

… and special mention goes to @Luketopia, for his FunScript Fractal Generator!

What’s next? We have a ton of ideas on what we could do. We will obviously add more resources as we go – but we would really like to hear from you guys. So help us make Community for F# the resource you would like to have! Here is what we would like from you:

• Contact us on Twitter at @c4fsharp, and let us know what you like and don’t like, and want to see!
• Take a look at the Dojos, and let us know how to make them better! Pull requests are highly appreciated. We have more Dojos and presentation material coming up, stay tuned! And if you have Dojo ideas you want to contribute, we’d love to hear about it.
• If you are organizing a Presentation, talking at a user group or a conference, ping us on Twitter, and we’ll let the Community know about your event!
• If you want to broadcast a presentation live, contact us, we would love to help out and make it available to the broader community.
• If you like what we are doing, please spread the word!

In short – we intend to make C4FSharp the best resource we can make it for local F# communities, and we would love your input and help on how to make that happen!

18. January 2014 14:49

A couple of months ago, I started working on an F# decision tree & random forest library, and pushed a first draft out in July 2013. It was a very minimal implementation, but it was a start, and my plan was to keep refining and add features. And then life happened: I got really busy, I began a very poorly disciplined refactoring effort on the code base, I second and third guessed my design - and got nothing to show for a while. Finally in December, I took some time off in Europe, disappeared in the French country side, a perfect setup to roll up my sleeves and finally get some serious coding done.

And here we go - drum roll please, version 0.1 of Charon is out. You can find it on GitHub, or install it as a NuGet package.

As you can guess from the version number, this is alpha-release grade code. There will be breaking changes, there are probably bugs and obvious things to improve, but I thought it was worth releasing, because it is in a shape good enough to illustrate the direction I am taking, and hopefully get some feedback from the community.

But first, what does Charon do? Charon is a decision tree and random forest machine learning classifier. An example will probably illustrate best what it does - let's work through the classic Titanic example. Using the Titanic passenger list, we want to create a model that predicts whether a passenger is likely to survive the disaster – or meet a terrible fate. Here is how you would do that with Charon, in a couple of lines of F#.

First, we use the CSV type provider to extract passenger information from our data file:

open Charon
open FSharp.Data

type DataSet = CsvProvider<"""C:\Users\Mathias\Documents\GitHub\Charon\Charon\Charon.Examples\titanic.csv""",
SafeMode=true, PreferOptionals=true>

type Passenger = DataSet.Row

In order to define a model, Charon needs two pieces of information: what is it you are trying to predict (the label, in that case, whether the passenger survives or not), and what information Charon is allowed to use to produce predictions (the features, in that case whatever passenger information we think is relevant):

let training =
use data = new DataSet()
[| for passenger in data.Data ->
passenger, // label source
passenger |] // features source

let labels = "Survived", (fun (obs:Passenger) -> obs.Survived) |> Categorical

let features =
[
"Sex", (fun (o:Passenger) -> o.Sex) |> Categorical;
"Class", (fun (o:Passenger) -> o.Pclass) |> Categorical;
"Age", (fun (o:Passenger) -> o.Age) |> Numerical;
]

For each feature, we specify whether the feature is Categorical (a finite number of "states" is expected, for instance Sex) or Numerical (the feature is to be interpreted as a numeric value, such as Age).

The Model is now fully specified, and we can train it on our dataset, and retrieve the results:

let results = basicTree training (labels,features) { DefaultSettings with Holdout = 0.1 }

printfn "Quality, training: %.3f" (results.TrainingQuality |> Option.get)
printfn "Quality, holdout: %.3f" (results.HoldoutQuality |> Option.get)

printfn "Tree:"
printfn "%s" (results.Pretty)

… which generates the following output:

Quality, training: 0.796
Quality, holdout: 0.747
Tree:
├ Sex = male
│   ├ Class = 3 → Survived False
│   ├ Class = 1 → Survived False
│   └ Class = 2
│      ├ Age = <= 16.000 → Survived True
│      └ Age = >  16.000 → Survived False
└ Sex = female
├ Class = 3 → Survived False
├ Class = 1 → Survived True
└ Class = 2 → Survived True

Charon automatically figures out what features are most informative, and organizes them into a tree; in our example, it appears that being a lady was a much better idea than being a guy – and being a rich lady traveling first or second class an even better idea. Charon also automatically breaks down continuous variables into bins. For instance, second-class male passengers under 16 had apparently much better odds of surviving than other male passengers. Charon splits the sample into training and validation; in this example, while our model appears quite good on the training set, with nearly 80% correct calls, the performance on the validation set is much weaker, with under 75% correctly predicted, suggesting an over-fitting issue.

I won’t demonstrate the Random Forest here; the API is basically the same, with better results but less human-friendly output. While formal documentation is lacking for the moment, you can find code samples in the Charon.Examples project that illustrate usage on the Titanic and the Nursery datasets.

What I hope I conveyed with this small example is the design priorities for Charon: a lightweight API that permits quick iterations to experiment with features and refine a model, using the F# Interactive capabilities.

I will likely discuss in later posts some of the challenges I ran into while implementing support for continuous variables – I learnt a lot in the process. I will leave it at that for today – in the meanwhile, I would love to get feedback on the current direction, and what you may like or hate about it. If you have comments, feel free to hit me up on Twitter, or to open an Issue on GitHub!