Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 11. January 2015 18:37

I had the great pleasure to speak at CodeMash this week, and, on my way back, ended up spending a couple of hours at the Atlanta airport waiting for my connecting flight back to the warmer climate of San Francisco – a perfect opportunity for some light-hearted coding fun. A couple of days earlier, I came across this really nice tweet, rendering the results of an L-system:

I ended up looking up L-systems on Wikipedia, and thought this would make for some fun coding exercise. In a nutshell, a L-system is a grammar. It starts with an alphabet of symbols, and a set of rules which govern how each symbol can be transformed into another chain of symbols. By applying these rules to a starting state (the initial axiom), one can evolve it into a succession of states, which can be seen as the growth of an organism. And by mapping each symbol to operations in a logo/turtle like language, each generation can then be rendered as a graphic.

So how could we go about coding this in F#? If you are impatient, you can find the final result as a gist here.

First, I started with representing the core elements of an L-System with a couple of types:

type Symbol = | Sym of char

type State = Symbol list

type Rules = Map<Symbol,State>

type LSystem = 
    { Axiom:State
      Rules:Rules }

A symbol is a char, wrapped in a single-case discriminated union, and a State is simply a list of Symbols. We define the Rules that govern the transformation of Symbols by a Map, which associates a particular Symbol with a State, and an L-System is then an Axiom (the initial State), with a collection of Rules.

Let’s illustrate this on the second example from the Wikipedia page, the Pythagoras tree. Our grammar contains 4 symbols, 0, 1, [ and ], we start with a 0, and we have 2 rules, (1 → 11), and (0 → 1[0]0). This can be encoded in a straightforward manner in our domain, like this:

let lSystem =
    { Axiom = [ Sym('0') ]
      Rules = [ Sym('1'), [ Sym('1'); Sym('1') ]
                Sym('0'), [ Sym('1'); Sym('['); Sym('0'); Sym(']'); Sym('0') ]]
              |> Map.ofList }

Growing the organism by applying the rules is fairly straightforward: given a State, we traverse the list of Symbols, look up for each of them if there is a matching rule, and perform a substitution if it is found, leaving it unchanged otherwise:

(*
Growing from the original axiom
by applying the rules
*)

let applyRules (rs:Rules) (s:Symbol) =
    match (rs.TryFind s) with
    | None -> [s]
    | Some(x) -> x

let evolve (rs:Rules) (s:State) =
    [ for sym in s do yield! (applyRules rs sym) ]

let forward (g:LSystem) =
    let init = g.Axiom
    let gen = evolve g.Rules
    init |> Seq.unfold (fun state -> Some(state, gen state))

// compute nth generation of lSystem
let generation gen lSystem =
    lSystem
    |> forward 
    |> Seq.nth gen
    |> Seq.toList

What does this give us on the Pythagoras Tree?

> lSystem |> generation 1;;
val it : Symbol list = [Sym '1'; Sym '['; Sym '0'; Sym ']'; Sym '0']

Nice and crisp – that part is done. Next up, rendering. The idea here is that for each Symbol in a State, we will perform a substitution with a sequence of instructions, either a Move, drawing a line of a certain length, or a Turn of a certain Angle. We will also have a Stack, where we can Push or Pop the current position of the Turtle, so that we can for instance store the current position and direction on the stack, perform a couple of moves with a Push, and then return to the previous position by a Pop, which will reset the turtle to the previous position. Again, that lends itself to a very natural model:

(*
Modelling the Turtle/Logo instructions
*)

type Length = | Len of float
type Angle = | Deg of float

// override operator later
let add (a1:Angle) (a2:Angle) =
    let d1 = match a1 with Deg(x) -> x
    let d2 = match a2 with Deg(x) -> x
    Deg(d1+d2)

type Inst =
    | Move of Length
    | Turn of Angle
    | Push
    | Pop

let Fwd x = Move(Len(x))
let Lft x = Turn(Deg(x))
let Rgt x = Turn(Deg(-x))

We can now transform our L-system state into a list of instructions, and convert them into a sequence of Operations, in that case Drawing lines between 2 points:

type Pos = { X:float; Y:float; }
type Dir = { L:Length; A:Angle }

type Turtle = { Pos:Pos; Dir:Dir }
type ProgState = { Curr:Turtle; Stack:Turtle list }

let turn angle turtle = 
    let a = turtle.Dir.A |> add angle
    { turtle with Dir = { turtle.Dir with A = a } }

type Translation = Map<Symbol,Inst list>

type Ops = | Draw of Pos * Pos

let pi = System.Math.PI

let line (pos:Pos) (len:Length) (ang:Angle) =
    let l = match len with | Len(l) -> l
    let a = match ang with | Deg(a) -> (a * pi / 180.)
    { X = pos.X + l * cos a ; Y = pos.Y + l * sin a }

let execute (inst:Inst) (state:ProgState) =
    match inst with
    | Push -> None, { state with Stack = state.Curr :: state.Stack }
    | Pop -> 
        let head::tail = state.Stack // assumes more Push than Pop
        None, { state with Curr = head; Stack = tail }
    | Turn(angle) -> 
        None, { state with Curr =  state.Curr |> turn angle }
    | Move(len) -> 
        let startPoint = state.Curr.Pos
        let endPoint = line startPoint len state.Curr.Dir.A
        Some(Draw(startPoint,endPoint)), { state with Curr = { state.Curr with Pos = endPoint } }

let toTurtle (T:Translation) (xs:Symbol list) =

    let startPos = { X = 400.; Y = 400. }
    let startDir = { L = Len(0.); A = Deg(0.) }
    let init = 
        { Curr = { Pos = startPos; Dir = startDir }
          Stack = [] }
    xs 
    |> List.map (fun sym -> T.[sym]) 
    |> List.concat
    |> Seq.scan (fun (op,state) inst -> execute inst state) (None,init)
    |> Seq.map fst
    |> Seq.choose id

We simply map each Symbol to a List of instructions, transform the list of symbols into a list of instructions, and maintain at each step the current position and direction, as well as a Stack (represented as a list) of positions and directions. How does it play out on our Pythagoras Tree? First, we define the mapping from Symbols to Instructions:

let l = 1.
let T = 
    [ Sym('0'), [ Fwd l; ]
      Sym('1'), [ Fwd l; ]
      Sym('['), [ Push; Lft 45.; ]
      Sym(']'), [ Pop; Rgt 45.; ] ]
    |> Map.ofList

… and we simply send that toTurtle, which produces a list of Draw instructions:

> lSystem |> generation 1 |> toTurtle T;;
val it : seq<Ops> =
  seq
    [Draw ({X = 400.0;
            Y = 400.0;},{X = 401.0;
                         Y = 400.0;}); Draw ({X = 401.0;
                                              Y = 400.0;},{X = 401.7071068;
                                                           Y = 400.7071068;});
     Draw ({X = 401.0;
            Y = 400.0;},{X = 401.7071068;
                         Y = 399.2928932;})]

Last step – some pretty pictures. We’ll simply generate a html document, rendering the image using SVG, by creating one SVG line per Draw instruction:

let header = """
<!DOCTYPE html>
<html>
<body>
<svg height="800" width="800">"""

let footer = """
</svg>
</body>
</html>
"""

let toSvg (ops:Ops seq) =
    let asString (op:Ops) = 
        match op with
        | Draw(p1,p2) -> sprintf """<line x1="%f" y1="%f" x2="%f" y2="%f" style="stroke:rgb(0,0,0);stroke-width:1" />""" p1.X p1.Y p2.X p2.Y 

    [ yield header
      for op in ops -> asString op
      yield footer ]
    |> String.concat "\n"

open System.IO

let path = "C:/users/mathias/desktop/lsystem.html"
let save template = File.WriteAllText(path,template)

And we are pretty much done:

> lSystem |> generation 8 |> toTurtle T |> toSvg |> save;;
val it : unit = ()

… which produces the following graphic:

image

Pretty neat! Just for fun, I replicated the Sierpinski Triangle example as well:

let sierpinski () =

    let lSystem =
        { Axiom = [ Sym('A') ]
          Rules = [ Sym('A'), [ Sym('B'); Sym('>'); Sym('A'); Sym('>'); Sym('B') ]
                    Sym('B'), [ Sym('A'); Sym('<'); Sym('B'); Sym('<'); Sym('A') ]]
                  |> Map.ofList }

    let l = 1.
    let T = 
        [ Sym('A'), [ Fwd l; ]
          Sym('B'), [ Fwd l; ]
          Sym('>'), [ Lft 60.; ]
          Sym('<'), [ Rgt 60.; ] ]
        |> Map.ofList

    lSystem 
    |> generation 9
    |> toTurtle T
    |> toSvg 
    |> save

… which results in the following picture:

image

That’s it for tonight! I had a lot of fun coding this (it certainly made the flight less boring), and found the idea of converting code to turtle instructions, with a stack, pretty interesting. Hope you enjoyed it, and if you end up playing with this, share your creations on Twitter and ping me at @brandewinder!

Gist for the whole code here

by Mathias 31. December 2014 10:59

Well, we are in the last hours of 2014, and I am nearly recovered from the craziness that was the F# Europa Tour 2014, so here we go – the Tour, in cold, hard facts (after all, I am a numbers’ guy):

  • 40 days of travelling across Europe.
  • 16 talks.
  • 5 workshops (about 50 hours total).
  • 9 countries.
  • 6991 miles (11,250 kilometers) travelled, roughly (this is straight-line city to city, so the actual number is probably a good deal larger).
  • 14 hours of bus.
  • roughly 50 hours of train.
  • roughly 28 hours of plane.
  • 12 cities visited (and spoken at!).
  • I lost track of how many gallons of beer were ingested. This is big data.
  • 500 attendees? Maybe more? See previous data point.
  • Delivered hundreds of shiny fsharp.org stickers to F# Communities across Europe. [btw, in case you didn't hear - the F# Software Foundation is now a full-fledged, legally established entity, and YOU can be a member. Check it out!]

Now for the important qualitative questions:

  • Where did I eat the best bacon? This came as a surprise to me, but I have to say, the bacon I ate in Dublin, Ireland was amazing. Twice.
  • Where does one find the best beer in Europe? This is a hard one – I had a chance to sample great beers from all over the place. I would say, Munich and its Biergarten rules, but the live beers at BuildStuff in Vilnius, Lithuania, were a very nice surprise.
  • What’s the weirdest thing I ate? This one goes to Norway and its Lutefisk, a traditional Christmas fish dish. It’s definitely a regional specialty, as in, a specialty which didn’t expand beyond a limited regional area, for good reasons. For the record, I actually enjoyed it!
  • What was the worst travelling mistake? Booking a last minute train ticket from Paris to Aarhus, Denmark, to realize in the train that instead of a nice sleeping car, I would be spending 22 hours sitting in a train with no food on board.
  • Biggest scare: every person who has given a talk will tell you, relying on the internet and anything live in a presentation is a rookie mistake. This is great advice, which is why I completely ignored it. It all worked just fine, but learning that Azure had been down for a couple of hours, right before a talk at BuildStuff which 100% required a live deployment to Azure to work, did give me some cold sweat.

Would I do it again? In a heartbeat! It was a bit crazy, and definitely exhausting, but a ton of fun. All of you who helped out making this happen, from the bottom of my heart, thank you! The F# Community is absolutely fantastic, packed with energy and a good, friendly vibe, and everywhere I went felt like family. You all kept me going, so again, thank you (you know who you are)! In the meanwhile, I wish you all a happy year 2015 ahead, let’s make that one even better than 2014, and I hope to see many of you again this year! And, as always, feel free to ping me on Twitter as @brandewinder.

by Mathias 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...

by Mathias 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...

by Mathias 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:

https://twitter.com/brandewinder/status/429698353203396609/photo/1

https://twitter.com/adamskjold/status/429695835467554816/photo/1

https://twitter.com/logan_mcgrath/status/429113418667134976

https://twitter.com/NickSardo/status/429111103394570240/photo/1

https://twitter.com/orlandpm/status/429106993022779392/photo/1

https://twitter.com/calvinb/status/423677489106276352/photo/1

https://twitter.com/kimsk/status/423646284600184832/photo/1

https://twitter.com/luketopia/status/423649400372486145/photo/1

https://twitter.com/rachelreese/status/423648840466837504/photo/1

https://twitter.com/adamskjold/status/429695835467554816/photo/1

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

Comments

Comment RSS